Инкрементное дерево решений

Алгоритм инкрементного дерева решений — это онлайн- алгоритм машинного обучения , который выводит дерево решений . Многие методы дерева решений , такие как C4.5 , строят дерево, используя полный набор данных. Методы поэтапного дерева решений позволяют обновлять существующее дерево, используя только новые отдельные экземпляры данных, без необходимости повторной обработки прошлых экземпляров. Это может быть полезно в ситуациях, когда весь набор данных недоступен при обновлении дерева (т. е. данные не были сохранены), исходный набор данных слишком велик для обработки или характеристики данных меняются со временем.

Приложения

Онлайн обучение
Потоки данных
Концептуальный дрейф
Данные, которые можно хорошо смоделировать с помощью иерархической модели.
Системы, в которых требуется интерпретируемый пользователем вывод.

Методы

Вот краткий список методов инкрементного дерева решений, организованных по их (обычно неинкрементным) родительским алгоритмам.

Семья КАРТ

КОРЗИНА ^[1] (1984) представляет собой неинкрементальный индуктор дерева решений как для задач классификации, так и для задач регрессии. разработанные в сообществах математиков и статистиков. CART берет свое начало от AID (1963). ^[2]

дополнительная ТЕЛЕГА (1989) ^[3] Кроуфорд модифицировал CART для постепенного включения данных.

Семейство ID3/C4.5

ИД3 (1986) ^[4] и C4.5 (1993) ^[5] были разработаны Куинланом и уходят корнями в Концептуальную систему обучения Ханта (CLS, 1966). ^[6] Семейство индукторов деревьев ID3 было разработано в сообществах инженеров и информатиков.

ИД3’ (1986) ^[7] предложили Шлиммер и Фишер. Это был грубый метод сделать ID3 инкрементальным; после получения каждого нового экземпляра данных с использованием ID3 создается совершенно новое дерево.
ИД4 (1986) ^[7] может включать данные постепенно. Однако некоторые концепции невозможно было выучить, поскольку ID4 отбрасывает поддеревья, когда для узла выбирается новый тест.
ИД5 (1988) ^[8] не отбрасывал поддеревья, но и не гарантировал, что будет создано то же дерево, что и ID3.
ИД5Р (1989) ^[9] выведите то же дерево, что и ID3, для набора данных независимо от порядка дополнительного обучения. Это было достигнуто путем рекурсивного обновления подузлов дерева. Он не обрабатывал числовые переменные, задачи многоклассовой классификации или пропущенные значения.
ИД6МДЛ (2007) ^[10] расширенная версия алгоритмов ID3 или ID5R.
ИТИ (1997) ^[11] является эффективным методом постепенного создания деревьев решений. Одно и то же дерево создается для набора данных независимо от порядка представления данных, а также от того, создается ли дерево инкрементально или неинкрементно ( пакетный режим ). Он может работать с числовыми переменными, многоклассовыми задачами и пропущенными значениями. Код доступен в сети. [1]

примечание: ID6NB (2009 г.) ^[12] не является инкрементальным.

Другие системы дополнительного обучения

Существовало несколько систем поэтапного концептуального обучения, которые не строили деревья решений, но которые предшествовали и повлияли на развитие самых ранних обучающих систем поэтапного дерева решений, особенно ID4. ^[7] Среди них следует отметить «СТАГГЕР» Шлиммера и Грейнджера (1986), ^[13] которые постепенно изучали дизъюнктивные концепции. STAGGER был разработан для изучения концепций, которые со временем менялись ( дрейф концепций ). До STAGGER, Михальски и Ларсон (1978) ^[14] исследовал инкрементальный вариант AQ (Michalski, 1973), ^[15] контролируемая система изучения понятий в дизъюнктивной нормальной форме (ДНФ). Опыт работы с этими более ранними и другими системами, включающий поэтапное древовидное обучение без учителя, способствовал созданию концептуальной основы для оценки учащихся с инкрементным деревом решений в частности и поэтапного концептуального обучения в целом по четырем измерениям, которые отражают присущий компромисс между стоимостью обучения и качеством: ^[7] (1) стоимость обновления базы знаний, (2) количество наблюдений, необходимых для сходимости в базе знаний с заданными характеристиками, (3) общие усилия (как функция первых двух измерений), которые прилагает система, и (4) качество (часто последовательность) окончательной базы знаний. Некоторые исторические контексты, в которых возникли поэтапные деревья решений, описаны у Фишера и Шлиммера (1988): ^[16] и который также расширяет четырехфакторную структуру, которая использовалась для оценки и разработки систем поэтапного обучения .

Алгоритм VFDT

Обучающийся с использованием очень быстрых деревьев решений сокращает время обучения для больших дополнительных наборов данных за счет субдискретизации входящего потока данных.

ВФДТ (2000) ^[17]
КВФДТ (2001) ^[18] может адаптироваться к изменению концепции , используя скользящее окно для входящих данных. Старые данные за окном забыты.
ВФДТц (2006) ^[19] расширяет VFDT для непрерывных данных, отклонения понятий и применения классификаторов Наивного Байеса в листьях.
VFML (2003 г.) представляет собой набор инструментов, доступный в Интернете. [2] . Он был разработан создателями VFDT и CVFDT.

Алгоритм EFDT

Учащийся чрезвычайно быстрого дерева решений ^[20] статистически более мощный, чем VFDT, что позволяет ему изучать более подробные деревья из меньшего количества данных. Он отличается от VFDT методом принятия решения о том, когда вставлять новую ветвь в дерево. VFDT ждет, пока не будет уверен, что лучшая доступная ветвь лучше любой альтернативы. Напротив, EFDT разделяется, как только становится уверенным, что лучшая доступная ветвь лучше, чем текущая альтернатива. Изначально текущей альтернативой является отсутствие ветвей. Это позволяет EFDT вставлять ветки гораздо быстрее, чем VFDT. В ходе постепенного обучения это означает, что EFDT может развертывать полезные деревья гораздо быстрее, чем VFDT.

Однако новый метод выбора ветвей значительно увеличивает вероятность выбора неоптимальной ветви. В результате EFDT продолжает следить за производительностью всех филиалов и заменит филиал, как только будет уверена, что существует лучшая альтернатива.

ОЛИН и ИФН

Я БЫЛ (2002) ^[21]
ИОЛИН (2008) ^[22] - на основе Info-Fuzzy Network (IFN) ^[23]

ГАЕНАРИ

Гаэнари

См. также

Ссылки

^ Брейман, Л.; Фридман, Дж. Х.; Ольшен, РА; Стоун, CJ (1984). Деревья классификации и регрессии . Бельмонт, Калифорния: Wadsworth International. ISBN 978-1-351-46048-4 .
^ Морган, JN; Сондквист, Дж. А. (1963). «Проблемы анализа данных опроса и предложение» (PDF) . Дж. Амер. Статист. доц . 58 (302): 415–434. дои : 10.1080/01621459.1963.10500855 .
^ Кроуфорд, СЛ (1989). «Расширения алгоритма CART» . Международный журнал человеко-машинных исследований . 31 (2): 197–217. дои : 10.1016/0020-7373(89)90027-8 .
^ Куинлан, младший (1986). «Индукция деревьев решений» (PDF) . Машинное обучение . 1 (1): 81–106. дои : 10.1007/BF00116251 . S2CID 13252401 .
^ Куинлан, младший (2014) [1993]. C4.5: Программы для машинного обучения . Эльзевир. ISBN 978-1-55860-238-0 .
^ Хант, Э.Б.; Марин, Дж.; Стоун, ПиДжей (1966). Эксперименты по индукции . Академическая пресса. ISBN 978-0-12-362350-8 .
^ Перейти обратно: ^а ^б ^с ^д Шлиммер, Дж. К.; Фишер, Д. (1986). «Пример поэтапного введения понятий» . AAAI'86: Материалы Пятой национальной конференции по искусственному интеллекту . Морган Кауфманн. стр. 496–501.
^ Утгофф, ЧП (1988). «ID5: инкрементальный ID3» (PDF) . Материалы машинного обучения 1988 г. Материалы Пятой международной конференции по машинному обучению . Морган Кауфманн. стр. 107–120. дои : 10.1016/B978-0-934613-64-4.50017-7 . ISBN 978-0-934613-64-4 . Издательства.
^ Утгофф, ЧП (1989). «Поэтапная индукция деревьев решений» (PDF) . Машинное обучение . 4 (2): 161–186. дои : 10.1023/A:1022699900025 . S2CID 5293072 .
^ Крун, М., Коржец, С., Адриани, П. (2007) ID6MDL: Поэтапные деревья решений после обрезки.
^ Утгофф, ЧП; Беркман, Северная Каролина; Клаус, Дж. А. (1997). «Индукция дерева решений на основе эффективной реструктуризации дерева» (PDF) . Машинное обучение . 29 : 5–44. дои : 10.1023/А:1007413323501 . S2CID 2743403 .
^ Аппаву, С.; Раджарам, Р. (2009). «Научная система классификации текста с использованием алгоритма ID6NB]» . Системы, основанные на знаниях . 22 (1): 1–7. дои : 10.1016/j.knosys.2008.04.006 .
^ Шлиммер, Дж. К.; Грейнджер-младший, Р.Х. (1986). «Поэтапное обучение на зашумленных данных» . Машинное обучение . 1 (3): 317–354. дои : 10.1007/BF00116895 . S2CID 33776987 .
^ Михальский, Р.С.; Ларсон, Дж. Б. (1978). Выбор наиболее репрезентативных примеров обучения и поэтапная генерация гипотез VL: основная методология и описание программ ESEL и AQ11 (PDF) (Технический отчет). Университет Иллинойса, факультет компьютерных наук. HDL : 1920/1544/78-03 . UIUCDCS-R-78-867.
^ Михальский, Р.С. (1973). «Обнаружение правил классификации с использованием системы логики с переменными значениями VL1» (PDF) . IJCAI'73: Материалы Третьей международной совместной конференции по искусственному интеллекту . Стэнфорд, Калифорния: Морган Кауфманн. стр. 162–172. HDL : 1920/1515/73-01 .
^ Фишер, Д.; Шлиммер, Дж. (1988). Модели поэтапного концептуального обучения: совместное исследовательское предложение (технический отчет). Университет Вандербильта. CS-88-05.
^ Домингос, П.; Хультен, Г. (2000). «Майнинг высокоскоростных потоков данных» (PDF) . Материалы KDD Материалы шестой международной конференции ACM SIGKDD по обнаружению знаний и интеллектуальному анализу данных . АКМ Пресс. стр. 71–80. дои : 10.1145/347090.347107 . ISBN 1-58113-233-6 . S2CID 8810610 .
^ Хультен, Г.; Спенсер, Л.; Домингос, П. (2001). «Анализ потоков изменяющихся во времени данных» (PDF) . Материалы седьмой международной конференции ACM SIGKDD по обнаружению знаний и интеллектуальному анализу данных . АКМ Пресс. стр. 97–106. дои : 10.1145/502512.502529 . ISBN 978-1-58113-391-2 . S2CID 6416602 .
^ Гама, Дж.; Фернандес, Р.; Роча, Р. (2006). «Дерево решений для анализа потоков данных» . Интеллектуальный анализ данных . 10 : 23–45. дои : 10.3233/IDA-2006-10103 .
^ Манапрагада, К.; Уэбб, Дж.И.; Салехи, М. (2018). «Чрезвычайно быстрое дерево решений». KDD '18: Материалы 24-й Международной конференции ACM SIGKDD по обнаружению знаний и интеллектуальному анализу данных . АКМ Пресс. стр. 1953–62. arXiv : 1802.08780 . дои : 10.1145/3219819.3220005 . ISBN 978-1-4503-5552-0 . S2CID 3513409 .
^ Последний, М. (2002). «Онлайн-классификация нестационарных потоков данных» (PDF) . Интел. Анал данных . 6 (2): 129–147. дои : 10.3233/IDA-2002-6203 .
^ Коэн, Л.; Авраами, Г.; Последний, М.; Кандель, А. (2008). «Информационно-нечеткие алгоритмы для анализа динамических потоков данных» (PDF) . Прикладные мягкие вычисления . 8 (4): 1283–94. дои : 10.1016/j.asoc.2007.11.003 .
^ Маймон, О.; Последний, М. (2000). Методология информационно-нечеткой сети (IFN). Обнаружение знаний и интеллектуальный анализ данных . Клювер. дои : 10.1007/978-1-4757-3296-2 . ISBN 978-1-4757-3296-2 . S2CID 41520652 .

Внешние ссылки

код ИТИ. http://www-lrn.cs.umass.edu/iti/index.html
Код ВФМЛ. http://www.cs.washington.edu/dm/vfml/
Инкрементное дерево решений C++. https://github.com/greenfish77/gaenari

[1] Брейман, Л.; Фридман, Дж. Х.; Ольшен, РА; Стоун, CJ (1984). Деревья классификации и регрессии . Бельмонт, Калифорния: Wadsworth International. ISBN 978-1-351-46048-4 .

[2] Морган, JN; Сондквист, Дж. А. (1963). «Проблемы анализа данных опроса и предложение» (PDF) . Дж. Амер. Статист. доц . 58 (302): 415–434. дои : 10.1080/01621459.1963.10500855 .

[3] Кроуфорд, СЛ (1989). «Расширения алгоритма CART» . Международный журнал человеко-машинных исследований . 31 (2): 197–217. дои : 10.1016/0020-7373(89)90027-8 .

[4] Куинлан, младший (1986). «Индукция деревьев решений» (PDF) . Машинное обучение . 1 (1): 81–106. дои : 10.1007/BF00116251 . S2CID 13252401 .

[5] Куинлан, младший (2014) [1993]. C4.5: Программы для машинного обучения . Эльзевир. ISBN 978-1-55860-238-0 .

[6] Хант, Э.Б.; Марин, Дж.; Стоун, ПиДжей (1966). Эксперименты по индукции . Академическая пресса. ISBN 978-0-12-362350-8 .

[Schlimmer,_J._C._1986_pp._496-501-7] Перейти обратно: ^а ^б ^с ^д Шлиммер, Дж. К.; Фишер, Д. (1986). «Пример поэтапного введения понятий» . AAAI'86: Материалы Пятой национальной конференции по искусственному интеллекту . Морган Кауфманн. стр. 496–501.

[8] Утгофф, ЧП (1988). «ID5: инкрементальный ID3» (PDF) . Материалы машинного обучения 1988 г. Материалы Пятой международной конференции по машинному обучению . Морган Кауфманн. стр. 107–120. дои : 10.1016/B978-0-934613-64-4.50017-7 . ISBN 978-0-934613-64-4 . Издательства.

[9] Утгофф, ЧП (1989). «Поэтапная индукция деревьев решений» (PDF) . Машинное обучение . 4 (2): 161–186. дои : 10.1023/A:1022699900025 . S2CID 5293072 .

[10] Крун, М., Коржец, С., Адриани, П. (2007) ID6MDL: Поэтапные деревья решений после обрезки.

[11] Утгофф, ЧП; Беркман, Северная Каролина; Клаус, Дж. А. (1997). «Индукция дерева решений на основе эффективной реструктуризации дерева» (PDF) . Машинное обучение . 29 : 5–44. дои : 10.1023/А:1007413323501 . S2CID 2743403 .

[12] Аппаву, С.; Раджарам, Р. (2009). «Научная система классификации текста с использованием алгоритма ID6NB]» . Системы, основанные на знаниях . 22 (1): 1–7. дои : 10.1016/j.knosys.2008.04.006 .

[13] Шлиммер, Дж. К.; Грейнджер-младший, Р.Х. (1986). «Поэтапное обучение на зашумленных данных» . Машинное обучение . 1 (3): 317–354. дои : 10.1007/BF00116895 . S2CID 33776987 .

[MichalskiLarson78-14] Михальский, Р.С.; Ларсон, Дж. Б. (1978). Выбор наиболее репрезентативных примеров обучения и поэтапная генерация гипотез VL: основная методология и описание программ ESEL и AQ11 (PDF) (Технический отчет). Университет Иллинойса, факультет компьютерных наук. HDL : 1920/1544/78-03 . UIUCDCS-R-78-867.

[Michalski,_1973-15] Михальский, Р.С. (1973). «Обнаружение правил классификации с использованием системы логики с переменными значениями VL1» (PDF) . IJCAI'73: Материалы Третьей международной совместной конференции по искусственному интеллекту . Стэнфорд, Калифорния: Морган Кауфманн. стр. 162–172. HDL : 1920/1515/73-01 .

[FisherSchlimmer88a-16] Фишер, Д.; Шлиммер, Дж. (1988). Модели поэтапного концептуального обучения: совместное исследовательское предложение (технический отчет). Университет Вандербильта. CS-88-05.

[17] Домингос, П.; Хультен, Г. (2000). «Майнинг высокоскоростных потоков данных» (PDF) . Материалы KDD Материалы шестой международной конференции ACM SIGKDD по обнаружению знаний и интеллектуальному анализу данных . АКМ Пресс. стр. 71–80. дои : 10.1145/347090.347107 . ISBN 1-58113-233-6 . S2CID 8810610 .

[18] Хультен, Г.; Спенсер, Л.; Домингос, П. (2001). «Анализ потоков изменяющихся во времени данных» (PDF) . Материалы седьмой международной конференции ACM SIGKDD по обнаружению знаний и интеллектуальному анализу данных . АКМ Пресс. стр. 97–106. дои : 10.1145/502512.502529 . ISBN 978-1-58113-391-2 . S2CID 6416602 .

[19] Гама, Дж.; Фернандес, Р.; Роча, Р. (2006). «Дерево решений для анализа потоков данных» . Интеллектуальный анализ данных . 10 : 23–45. дои : 10.3233/IDA-2006-10103 .

[20] Манапрагада, К.; Уэбб, Дж.И.; Салехи, М. (2018). «Чрезвычайно быстрое дерево решений». KDD '18: Материалы 24-й Международной конференции ACM SIGKDD по обнаружению знаний и интеллектуальному анализу данных . АКМ Пресс. стр. 1953–62. arXiv : 1802.08780 . дои : 10.1145/3219819.3220005 . ISBN 978-1-4503-5552-0 . S2CID 3513409 .

[21] Последний, М. (2002). «Онлайн-классификация нестационарных потоков данных» (PDF) . Интел. Анал данных . 6 (2): 129–147. дои : 10.3233/IDA-2002-6203 .

[22] Коэн, Л.; Авраами, Г.; Последний, М.; Кандель, А. (2008). «Информационно-нечеткие алгоритмы для анализа динамических потоков данных» (PDF) . Прикладные мягкие вычисления . 8 (4): 1283–94. дои : 10.1016/j.asoc.2007.11.003 .

[23] Маймон, О.; Последний, М. (2000). Методология информационно-нечеткой сети (IFN). Обнаружение знаний и интеллектуальный анализ данных . Клювер. дои : 10.1007/978-1-4757-3296-2 . ISBN 978-1-4757-3296-2 . S2CID 41520652 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]