Кто изобрел дерево решений?

Я пытаюсь отследить, кто изобрел структуру данных и алгоритм дерева решений.

В статье в Википедии об изучении дерева решений есть утверждение, что «ID3 и CART были изобретены независимо примерно в одно и то же время (между 1970 и 1980 годами)». ID3 был представлен позже в:

• Quinlan, JR 1986. Индукция деревьев решений. Мах. Учиться. 1, 1 (март 1986 г.), 81-106

поэтому я не уверен, что претензия верна.

Используя книги Google, я нашел ссылку на серию Статистических решений 1959 года и сборник Рабочих документов 1958 года . Контекст не ясен, и они, кажется, не представляют алгоритм. Тем не менее, они не определяют структуру данных и обрабатывают ее как хорошо известную.

Используя Google Scholar, я нашел цитаты, начиная с 1853 года, но это были ошибки синтаксического анализа, а не реальные цитаты с той даты.

Хороший вопрос. @ G5W находится на правильном пути, ссылаясь на статью Вей-Инь Ло. В статье Лоха обсуждаются статистические предшественники деревьев решений и, верно, прослеживается их местоположение до статьи Фишера (1936) о дискриминантном анализе - по существу, регрессии, классифицирующей несколько групп в качестве зависимой переменной - и оттуда через AID, THAID, CHAID и Модели CART.

Короткий ответ заключается в том, что первая статья, которую мне удалось найти, которая развивает подход «дерева решений», датируется 1959 годом, и британский исследователь Уильям Белсон в статье под названием « Сопоставление и прогнозирование по принципу биологической классификации» ( JRSS). , Серия C, Прикладная статистика, том 8, № 2, июнь 1959 г., стр. 65-75), в аннотации которого описан его подход как один из подходящих выборок населения и разработка критериев для этого:

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

«Длинный» ответ состоит в том, что другие, даже более ранние потоки мысли кажутся здесь актуальными. Например, простые разбивки по возрасту и полу, используемые в актуарных таблицах смертности, дают основу для размышлений о решениях, которые датируются несколькими столетиями. Можно также утверждать, что в усилиях, восходящих к вавилонянам, использовались квадратные уравнения, которые были нелинейными по переменным (не по параметрам, http://www-history.mcs.st-and.ac.uk/HistTopics/Quadratic_etc_equations. html ) имеют значение, по крайней мере, поскольку они предопределяют параметрические модели логистического роста (я признаю, что это натяжениекомментарий, пожалуйста, читайте дальше для более полной мотивации). Кроме того, философы давно признали и теоретизировали о существовании иерархически упорядоченной, качественной информации, например, книги Аристотеля о категориях . Концепция и допущение иерархии является ключевым здесь. Другие важные, гораздо более поздние открытия были направлены на то, чтобы выйти за границы трехмерного евклидова пространства в бесконечном развитии Дэвида Гильберта Гильбертапространство, комбинаторика, физические открытия, связанные с 4-мерным пространством Минковского, расстоянием и временем, статистическая механика теории специальной теории относительности Эйнштейна, а также инновации в теории вероятностей, связанные с моделями цепей Маркова, переходов и процессов. Дело в том, что между любой теорией и ее применением может быть значительный разрыв - в этом случае разрыв между теориями о качественной информации и разработками, связанными с их эмпирической оценкой, предсказанием, классификацией и моделированием.

Наилучшим предположением является то, что эти события могут быть связаны с историей возрастающей изощренности статистиков, в основном в XX веке, при разработке моделей, использующих типы шкал, отличные от непрерывных (например, номинальная или, проще говоря, категориальная информация), моделей подсчета данных. (пуассон), перекрестные классифицированные таблицы сопряженности, непараметрическая статистика без распределения, многомерное масштабирование (например, Дж. Г. Кэрролл), модели с качественными зависимыми переменными, такими как логистическая регрессия двух групп, а также анализ соответствия (в основном в Голландии и Франции) в 70-х и 80-х годах).

Существует обширная литература, в которой обсуждается и сравнивается логистическая регрессия двух групп с дискриминантным анализом двух групп, и, для полностью номинальных признаков, находит, что они обеспечивают эквивалентные решения (например, Dillon and Goldstein's Multivariate Analysis , 1984).

Статья Дж. С. Крамера об истории логистической регрессии ( The History of Logistic Regression , http://papers.tinbergen.nl/02119.pdf ) описывает ее как возникновение с развитием одномерной логистической функции или классической S-образной кривой :

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

Детерминированные модели логистической кривой возникли в 1825 году, когда Бенджамин Гомпертц ( https://en.wikipedia.org/wiki/Benjamin_Gompertz ) опубликовал документ, в котором была разработана первая действительно нелинейная логистическая модель (нелинейная по параметрам, а не только переменные, как в случае с вавилоняне) - модель и кривая Гомперца

Я бы предположил, что другим важным звеном в этой цепочке, ведущей к изобретению деревьев решений, была работа социолога из Колумбии Пола Лазарсфельда над моделями скрытой структуры. Его работа началась в 30-х годах, продолжилась во время Второй мировой войны с его анализа содержания немецких газет для зарождающейся OSS (позже ЦРУ, как обсуждалось в книге Джона Найсбетта « Мегатенденции» ) и, наконец, опубликована в 1950 году. Андерсен описывает это следующим образом ( Анализ скрытой структуры: Обзор , Эрлинг Б. Андерсен, Скандинавский журнал статистики , том 9, № 1, 1982, стр. 1-12):

Основа классической теории анализа скрытой структуры была разработана Полом Лазарсфельдом в 1950 году в ходе исследования этноцентризма американских солдат во время Второй мировой войны. Лазарсфельд был в первую очередь заинтересован в разработке концептуальной основы моделей скрытой структуры ... Однако статистические методы, разработанные Лазарсфельдом, были довольно примитивными ... Ранняя попытка получить эффективные методы оценки и процедуры испытаний была предпринята коллегой Лазарсфельда в Колумбийском университете. , TW Андерсон, который в статье ( Psychometrika , март 1954, том 19, выпуск 1, стр. 1–10, об оценке параметров в анализе скрытой структуры), разработал эффективный метод оценки параметров модели скрытого класса ... Чтобы представить структуру (моделей скрытого класса), мы кратко изложим основные понятия ... и используем систему обозначений, разработанную Гудманом значительно позже. (1974a) ... Данные приведены в форме таблицы нескольких непредвиденных обстоятельств ...

Здесь следует провести полезное различие, поскольку оно может быть связано с переходом от AID к CHAID (позднее CART), между моделями на основе таблиц сопряженности (все переменные в модели номинально масштабированы) и более поздними моделями скрытых классов (больше точнее, модели конечных смесей на основе «смесей» шкал и распределений, например, Камакура и Рассел, 1989, Вероятностная модель выбора для сегментации рынка и структуры эластичности) как они создают остатки модели. Для более старых моделей таблиц сопряженности количество ячеек, свойственное полностью перекрестно классифицированной таблице, послужило основой для «репликаций» и, следовательно, неоднородности остатков модели, используемых при разбиении на классы. С другой стороны, более поздние модели смеси основаны на повторных измерениях по одному объекту в качестве основы для распределения неоднородности по остаточным значениям. Этот ответ непредполагая прямую связь между скрытыми моделями классов и деревьями решений. Отношение к AID и CHAID можно суммировать в статистике, используемой для оценки моделей, AID использует непрерывное F-распределение, а CHAID использует распределение хи-квадрат, подходящее для категориальной информации. Скорее в своем анализе и моделировании таблиц непредвиденных обстоятельств, по моему мнению, LCM являются важной частью головоломки или повествования, приводящего к разработке деревьев решений, наряду со многими другими уже отмеченными нововведениями.

CHAID был более поздней разработкой, впервые предложенной в 1980 году докторской диссертацией южноафриканским Гордоном Кассом, как описано в этой статье в Вики о CHAID ( https://en.wikipedia.org/wiki/CHAID ). Конечно, CART появился несколькими годами позже, в 80-х годах, вместе с Брейманом и его коллегами, теперь известной книгой « Деревья классификации и регрессии» .

AID, CHAID и CART позиционируют древовидные иерархические структуры как оптимальное представление реальности. Они просто делают это, используя разные алгоритмы и методы. Для меня следующие шаги в этой прогрессивной цепочке инноваций - это появление гетерархических теорий структуры. Как определено в этой вики-статье, гетерархии «представляют собой систему организации, в которой элементы организации не ранжируются (не иерархически) или где они могут быть ранжированы различными способами» ( https: //en.wikipedia .org / wiki / Heterarchy или для более глубокого, более философского взгляда на гетерархию см. Kontopoulos, Логика социальной структуры). С эмпирической точки зрения анализ и моделирование сетевых структур наиболее характерны для этого исторического развития в понимании структуры (например, книга Фримена « Развитие анализа социальных сетей» ). Хотя многие сетевые аналитики будут пытаться навязать иерархию в получающейся сети, это скорее выражение укоренившихся и бессознательных предположений, чем утверждение об эмпирической реальности структуры мультиплексной сети в сложном мире.

Этот ответ предполагает, что дуга эволюции, ведущая к разработке деревьев решений, создавала новые вопросы или неудовлетворенность существующими «современными» методами на каждом этапе или этапе процесса, требуя новых решений и новых моделей. В этом случае неудовлетворенность проявляется в ограниченности моделирования двух групп (логистическая регрессия) и признании необходимости расширения этой структуры более чем на две группы. Недовольство непредставительными предположениями о базовом нормальном распределении (дискриминантный анализ или AID), а также сравнением с относительной «свободой», которую можно найти при использовании непараметрических допущений и моделей без распределения (например, CHAID и CART).

Как и предполагалось, происхождение деревьев решений почти наверняка имеет долгую историю, уходящую в глубь веков и географически рассредоточенную. Многочисленные потоки в истории человечества, науке, философии и мышлении можно проследить в изложении повествования, ведущего к развитию множества разновидностей деревьев решений, существующих сегодня. Я буду первым, кто признает существенные ограничения моего краткого очерка этой истории.

/ ** Дополнения ** /

1. Эта статья 2014 года в New Scientist называется Почему мы любим организовывать знания в деревья? ( https://www.newscientist.com/article/mg22229630-800-why-do-we-love-to-organise-knowledge-into-trees/ ), Это обзор книги гуру визуализации данных Мануэля Лимы Книга Деревья, которые прослеживают тысячелетнее использование деревьев в качестве визуализации и мнемонической помощи для познания. Кажется, мало сомнений в том, что светские и эмпирические модели и графики, присущие таким методам, как AID, CHAID и CART, представляют собой продолжающуюся эволюцию этой изначально религиозной традиции классификации.

2. В этом видео (опубликованном онлайн компанией Salford Systems, разработчиками программного обеспечения CART), посвященной Лео Брейману , Брейман рассказывает о развитии своего мышления, которое привело к методологии CART. Все началось со стены, оштукатуренной силуэтами различных линкоров времен Второй мировой войны.

https://www.salford-systems.com/videos/conferences/cart-founding-fathers/a-tribute-to-leo-breiman?utm_source=linkedin&utm_medium=social&utm_content=3599323

3. Читая вступление к « Теории конечных и бесконечных графов» Дениса Кенига 1936 года , широко рассматриваемой как предоставление первого строгого математического обоснования области, ранее рассматриваемой как источник развлечения и загадки для детей, Тутте отмечает (стр. 13) эту главу 4 (начало на стр. 62) книги Кенига посвящена деревьям в теории графов. Tutte объясняет определение дерева Konig следующим образом: «где« ациклический »граф является графом без схемы, дерево является конечным связным ациклическим графом ... другими словами, в дереве есть один и только один путь из отдать вершину другому ... "Для меня (и я не теоретик графов и не математик) это говорит о том, что теория графов и ее предшественники в" Ситусе анализа Пуанкаре " или" Веблене " лекции по комбинаторной топологии, возможно, обеспечили ранние интеллектуальные и математические предпосылки для того, что позже стало темой для статистиков.

4. Первое Древо Знаний широко приписывается неоплатоническому философу Порфирию, который около 270 г. н.э. написал Введение в логику, в котором использовалось метафорическое древо для описания и организации знаний ... http://www.historyofinformation.com/expanded.php? ID = 3857

5. Только что обнаружил еще более раннюю ссылку на Древо познания в Книге Бытия в Библии, обсуждаемую в этой вики-статье ... https://en.wikipedia.org/wiki/Tree_of_life_(biblical) . Бытие, вероятно, восходит к 1400 г. до н.э. на основании этой ссылки ... https://www.biblica.com/bible/bible-faqs/when-was-the-bible-written/ Несмотря на это, Книга Бытия появилась много веков назад Порфирий.

Большая ссылка на CART:

Деревья классификации и регрессии
Лео Брейман, Джером Фридман, Чарльз Дж. Стоун, Р.А. Ольшен (1984)

но это определенно была не самая ранняя работа по этому вопросу.

В своей статье 1986 года « Внедрение деревьев решений» Куинлан сам определяет систему обучения понятий Ханта (CLS) как предшественник ID3. Он встречается с CLS в 1963 году, но ссылки

Э. Б. Хант, Дж. Марин, П. Дж. Стоун,
Эксперименты в индукционной
академической прессе, Нью-Йорк, 1966

Вей-Инь Ло из Висконсинского университета написал об истории деревьев решений. Есть бумага

Пятьдесят лет деревьев классификации и регрессии Международный статистический обзор Wei-Yin Loh (2014), 82, 3, 329–348 дои: 10.1111 / insr.12016

Существует также слайд-колода из доклада, который он дал на эту тему.