Инкрементное дерево решений - Incremental decision tree

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

Приложения

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

Методы

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

CART семья

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

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

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

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

  • ID3 '(1986)[7] был предложен Шлиммером и Фишером. Чтобы сделать ID3 инкрементным, это был метод грубой силы; после получения каждого нового экземпляра данных с помощью ID3 создается совершенно новое дерево.
  • ID4 (1986)[7] может включать данные постепенно. Однако некоторые концепции были невыучимы, потому что ID4 отбрасывает поддеревья, когда для узла выбирается новый тест.
  • ID5 (1988)[8] не отбрасывал поддеревья, но также не гарантировал, что он создаст такое же дерево, что и ID3.
  • ID5R (1989)[9] вывести то же дерево, что и ID3 для набора данных, независимо от порядка возрастающего обучения. Это было достигнуто путем рекурсивного обновления подузлов дерева. Он не обрабатывал числовые переменные, мультиклассовая классификация задачи или отсутствующие значения.
  • ID6MDL (2007)[10] расширенная версия алгоритмов ID3 ​​или ID5R.
  • ITI (1997)[11] - эффективный метод постепенного создания деревьев решений. Одно и то же дерево создается для набора данных независимо от порядка представления данных, а также от того, создается ли дерево инкрементально или не инкрементально (пакетный режим). Он может поддерживать числовые переменные, многоклассовые задачи и пропущенные значения. Код доступен в сети. [1]

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

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

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

Алгоритм VFDT

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

  • VFDT (2000)[17]
  • CVFDT (2001)[18] может адаптироваться к дрейф концепции, используя скользящее окно для входящих данных. Забываются старые данные за окном.
  • VFDTc (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]

Смотрите также

Рекомендации

  1. ^ Брейман, Л., Фридман, Дж. Х., Ольшен, Р. А., и Стоун, К. Дж. (1984) Деревья классификации и регрессии. Бельмонт, Калифорния: Международная группа Wadsworth.
  2. ^ Морган, Дж. Н. и Сондквист, Дж. А. (1963) Проблемы при анализе данных опроса и предложения. J. Amer. Статист. Assoc., 58, 415-434.
  3. ^ Кроуфорд, С. Л. (1989) Расширения алгоритма CART. Международный журнал человеко-машинных исследований. 31, 197-217.
  4. ^ Куинлан, Дж. Р. (1986) Индукция деревьев решений. Машинное обучение 1 (1), 81-106.
  5. ^ Куинлан, Дж. Р. (1993) C4.5: Программы для машинного обучения. Сан-Матео, Калифорния: Морган Кауфманн.
  6. ^ Хант, Э. Б., Марин, Дж., И Стоун, П. Дж. (1966) Эксперименты по индукции. Нью-Йорк: Academic Press.
  7. ^ а б c d Шлиммер, Дж. К., и Фишер, Д. (1986) Пример внедрения инкрементальной концепции. Труды Пятой Национальной конференции по искусственному интеллекту (стр. 496-501). Филадельфия, Пенсильвания: Морган Кауфманн.
  8. ^ Утгофф П. (1988) ID5: инкрементный ID3. Пятая международная конференция по машинному обучению, стр. 107-120. Морган КауфманнИздатели.
  9. ^ Утгофф, П. Э. (1989) Инкрементальная индукция деревьев решений. Машинное обучение 4, 161-186.
  10. ^ Кроон, М., Коржец, С., Адриани, П. (2007) ID6MDL: Пост-обрезка инкрементных деревьев принятия решений.
  11. ^ Утгофф П. Э., Беркман Н. К. и Клаус Дж. А. (1997) Индукция дерева решений на основе эффективной реструктуризации дерева. Машинное обучение 29, 5-44.
  12. ^ Аппаву, С., и Раджарам, Р. (2009) База знаний для классификации текста с использованием алгоритма ID6NB. Системы, основанные на знаниях 22 1-7.
  13. ^ Шлиммер, Дж. К., и Грейнджер, Р. Х. младший (1986). Пошаговое обучение на основе зашумленных данных. Машинное обучение 1, 317-354.
  14. ^ Михальский, Р. С., и Ларсон, Дж. Б. (1978). Выбор наиболее репрезентативных обучающих примеров и постепенное генерирование гипотез VL: лежащая в основе методология и описание программ ESEL и AQ11 (Технический представитель № UIUCDCS-R-78-867). Урбана: Университет Иллинойса, факультет компьютерных наук.
  15. ^ Михальский, Р. С. (1973). Обнаружение правил классификации с использованием логической системы с переменными значениями VL1. Труды Третьей международной совместной конференции по искусственному интеллекту (стр. 162-172). Стэнфорд, Калифорния: Морган Кауфманн.
  16. ^ Фишер, Д. и Шлиммер, Дж. Модели постепенного концептуального обучения: совместное исследовательское предложение. Технический отчет Университета Вандербильта CS-88-05 (1988), извлеченный из http://www.vuse.vanderbilt.edu/~dfisher/tech-reports/tr-88-05/proposal.html
  17. ^ Домингос, П., Халтен, Г. (2000) Майнинг высокоскоростных потоков данных. Proceedings KDD2000, ACM Press, Нью-Йорк, Нью-Йорк, США, стр. 71–80.
  18. ^ Халтен, Г., Спенсер, Л., Домингос, П. (2001) Майнинг изменяющихся во времени потоков данных. Proceedings KDD 2001, ACM Press, Нью-Йорк, Нью-Йорк, стр. 97–106.
  19. ^ Гама, Дж., Фернандес, Р., и Роча, Р. (2006) Деревья решений для интеллектуального анализа потоков данных. Интеллектуальный анализ данных 10 23-45.
  20. ^ Манапрагада, К., Уэбб, Г. И., Салехи, М. (2018) Чрезвычайно быстрое дерево решений. Proceedings KDD2018, ACM Press, Нью-Йорк, Нью-Йорк, США, стр.1953-1962.
  21. ^ Ласт, М. (2002) Онлайн-классификация нестационарных потоков данных, Intell. Data Anal. 6 (2) 129–147.
  22. ^ Коэн, Л., Аврахами, Г., Ласт, М., Кандел, А. (2008) Информационно-нечеткие алгоритмы для интеллектуального анализа динамических потоков данных. Прикладные программные вычисления. 8 1283-1294.
  23. ^ Маймон, О., Ласт, М. (2000) Методология информационной нечеткой сети (IFN). Открытие знаний и интеллектуальный анализ данных. Бостон: Kluwer Academic Publishers

внешняя ссылка