содержание

1. Изучение концепции
2. Поиск пространства версий
3. Дерево решений

1. Концептуальное обучение

1.1 Распространенный метод обучения — обобщение

Определение обобщения
- С точки зрения множеств: выражение P является более общим, чем выражение Q, тогда и только тогда, когда P ⊇ Q
- Например, мы можем
  Волейбол, баскетбол, футбол == (в обобщенном виде) ==> мяч или спорт
Основными операциями обобщения в машинном обучении являются:
- константа подстановки переменной
- удалить некоторые условия из выражений конъюнкции
- добавить дизъюнкт к выражению
- Замена свойства его суперклассом

1.2 Изучение концепций через обобщение

Что покрывает?
Если мы говорим, что понятие P более общее, чем понятие q, мы говорим, что p покрывает q
Определение понятийного пространства
- Концептуальное пространство какое-тоосновная концепцияизсобирать
- Потенциальные концепции (потенциальные концепции / концепции-кандидаты) генерируются с помощью таких методов обучения, как обобщение и специализация.
  На следующем рисунке представлено концептуальное пространство объекта со следующими атрибутами и значениями.
  Size = {small, large}
  Color = {red, white, blue}
  Shape = {ball, brick, cube}

концептуальное пространство

Восхождение — это процесс обобщения.Например, Obj(X, Y, мяч) может охватывать Obj(X, красный, мяч) и Obj(маленький, X, мяч) и т. д., что также является воплощением концепции обучения через обобщение.

2. Поиск пространства деформации

Version space search (Mitchell 1978, 1979, 1982) illustrates the implementation of inductive learning as search through a concept space.

Грубо говоря, можно создатьконцептуальное пространство, как на картинке выше. а затем из концептуального пространствапоискможнообложкаПонятие всех понятий. Например, Obj(X, Y, Z) на рисунке выше.

2.1 Определение пространства версий

2.2. Три алгоритма поиска пространства понятий

特殊到一般 (specific to general)
一般到特殊 (general to specific)
候选解排除 (candidate elimination)

Эти алгоритмы основаны надеформационное пространствоконцепция, есть ещепример, размер деформационного пространства может быть уменьшен.
Цель:Выученных понятий достаточно не только для охвата всех положительных примеров, но и для исключения всех отрицательных примеров.. Хотя упомянутое выше Obj(X, Y, Z) может охватывать все положительные примеры, оно может быть слишком обобщенным.
Способы избежать чрезмерного обобщения:
- Используйте как можно меньшее обобщение, чтобы оно охватывало только положительные примеры.
- Используйте контрпримеры, чтобы исключить чрезмерно обобщенные концепции
  
  Роль контрпримеров в предотвращении гипергенерализации

2.2.1 От специального к общему

Поддерживать набор гипотез S (т. е. набор возможных определений концепций)
Максимально конкретное обобщение
Понятие c является наиболее особенным, если:
① Укажите все положительные примеры, но не отрицательные.
② Для всех остальных понятий c', охватывающих положительные примеры, c ≤ c'

Поиск от частного к общему

2.2.2 От общего к особому

Поддерживать набор гипотез G (т. е. набор концепций-кандидатов)
Максимально общая концепция
Концепция c является наиболее общей, если:
① Укажите все положительные примеры, но не отрицательные.
② Для любой другой концепции c', которая не охватывает контрпримеры, c ≥ c'

Фон изображения ниже:
size = {large, small}
color = {red, white, blue}
shape = {ball, brick, cube}
Итак, из первого встречного примера мы можем специализироваться:
размер не может быть маленьким => obj(большой, Y, Z)
цвет не может быть красным => obj(X, белый, Z) и obj(X, синий, Z)
форма не может быть кирпичом => obj(X, Y, шар) и obj(X, Y, куб)

Поиск от общего к специальному

2.2.3 Исключение решения-кандидата

Метод исключения решения-кандидата сочетает в себе два вышеуказанных метода,двусторонний поиск
Поддерживать два набора концептов-кандидатов S и G
Алгоритм специализируется на G и обобщает S до тех пор, пока они не сойдутся на целевой концепции.

Screenshot at May 04 00-40-53.png

2.3 Оценка алгоритма исключения решения-кандидата

2.3.1 Преимущества

Алгоритм исключения решения-кандидата является инкрементным, поэтому в отличие от других алгоритмов, которые требуют, чтобы все обучающие примеры были даны перед обучением.

2.3.2 Недостатки

Как и другие проблемы поиска, обучение на основе поиска должно иметь дело со слиянием проблемных пространств.
Алгоритм исключения решения-кандидата не может иметь шума

3. Дерево решений

3.1 Что такое дерево решений?

В машинном обучении,Древо решенийявляется прогностической моделью; она представляет отношение сопоставления между свойствами объекта и значениями объекта. каждый в деревеузелуказатьобъект, и каждыйразветвленный путьпредставляет собой возможныйзначение атрибута, и каждыйлистовой узелТогда соответствует значение объекта, представленного путем от корневого узла к конечному узлу. Дерево решений имеет только один выход.Если вы хотите иметь несколько выходов, вы можете построить независимое дерево решений для обработки разных выходов.
- через Википедию

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

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

Выборка лиц с известным кредитным риском

На основании приведенной выше информации мы можем получить следующеедва разныхДрево решений.

дерево решений А

дерево решений Б

Мы видим, что хотя оба дерева решений могут правильно классифицировать данный набор экземпляров,дерево решений Бчемдерево решений АГораздо проще. Видно, что размер дерева, необходимый для классификации заданного набора экземпляров,С порядком тестовых свойстви разные.

3.2 Общие алгоритмы построения деревьев решений

3.2.1 ID3

ID3 was developed in 1986 by Ross Quinlan. The algorithm creates a multiway tree, finding for each node (i.e. in a greedy manner) the categorical feature that will yield the largest information gain for categorical targets. Trees are grown to their maximum size and then a pruning step is usually applied to improve the ability of the tree to generalise to unseen data.

Далее мы сосредоточимся на алгоритме ID3.

3.2.2 C4.5

C4.5 является преемником ID3 и убрал ограничение, согласно которому объекты должны быть категориальными, путем динамического определения дискретного атрибута (на основе числовых переменных), который разбивает непрерывное значение атрибута на дискретный набор интервалов.C4.5 преобразует обученные деревья ( то есть вывод алгоритма ID3) в наборы правил "если-то". Затем точность каждого правила оценивается для определения порядка, в котором они должны применяться. Сокращение выполняется путем удаления предварительного условия правила, если точность правила улучшается. без этого.

3.2.3 C5.0

C5.0 – это последняя версия Quinlan, выпущенная под частной лицензией. Она использует меньше памяти и создает меньшие наборы правил, чем C4.5, но при этом является более точной.

3.2.4 CART

CART (Classification and Regression Trees) is very similar to C4.5, but it differs in that it supports numerical target variables (regression) and does not compute rule sets. CART constructs binary trees using the feature and threshold that yield the largest information gain at each node.

3.3 Подробное объяснение алгоритма ID3

3.3.1 Бритва Оккама

Бритва Оккама была впервые предложена математиком-логиком Уильямом Оккамом в 1324 году:

It is vain to do with more what can be done with less. . . . Entities should not be multiplied beyond necessity.

Проще говоря, найти что-то, что соответствует даннымпростейшийразвязать!

3.3.2 Основная идея алгоритма ID3

Учитывая набор обучающих экземпляров и набор различных деревьев решений, которые могут их правильно классифицировать, мы хотим знать, какое дерево с наибольшей вероятностью правильно классифицирует будущие экземпляры. Алгоритм ID3предполагаемыйНаиболее вероятное дерево — это то, которое охватывает все обучающие экземпляры.Простейшее дерево решений.
Примечание. ID3 не гарантирует, что наименьшее дерево будет генерироваться каждый раз.эвристический алгоритм.

ID3 принимает индукцию дерева решений сверху вниз:

Сначала определите, какое свойство используется в качествекорневой узел(корневой узел) тест
Выберите атрибут с наилучшей способностью классификации (максимальный прирост информации) кактекущий узел(текущий узел) тест
Используйте этот тест, чтобы разделить набор экземпляров, где каждое возможное значение атрибута становитсяразделять(partition)
Повторите описанный выше процесс для каждого раздела, чтобы построить его поддерево.
Пока все элементы раздела не принадлежат к одному классу, класс становится деревом.листовой узел(leaf node)

Примечание. Набор всех возможных деревьев решений можно рассматривать как определение пространства версий. ID3 реализует один в пространстве всех возможных деревьевЖадный поиск, добавить поддерево к текущему дереву и продолжить поиск, абез возврата.

3.3.3 Как определить лучший атрибут классификации

Алгоритм ID3 был впервые предложен Куинланом и основан натеория информацииНа основе (теории информации) ID3 измеряет прирост информации, рассматривая каждый атрибут как корневой узел текущего дерева, а затем алгоритм выбирает атрибут, обеспечивающий наибольший прирост информации.

① Показатели получения информации -энтропия(Entropy)
Энтропия в основном относится к степени путаницы информации.Чем больше неопределенность переменных, тем больше значение энтропии.
Неопределенность переменных может в основном отражаться в двух аспектах:

объем возможной информации
Проще говоря, есть две возможные информации (орел или решка) для подбрасывания монеты и шесть возможных информации для подбрасывания сита (1, 2, 3, 4, 5, 6), поэтому правильно предсказать информацию о сите более сложно. ценный для нас: бросьте сито, чтобы выиграть больше денег.
Вероятность появления каждого сообщения
Проще говоря, если мы предположим, что мошенничество при подбрасывании монеты выпадет орлом с вероятностью 3/4. Затем, поскольку я уже знаю, что вероятность выпадения орла составляет 3/4, новость, сообщающая мне о результате подбрасывания монеты, не так ценна, как новость о неподсчитанной монете. (Конкретный расчет будет рассмотрен позже)

Подводя итог, учитывая пространство сообщений M = {m1, m2, .....} и соответствующую вероятность P(mi), формула для энтропии:

формула для энтропии

Энтропия для необманутых и обманутых рассчитывается следующим образом:

Расчет энтропии без обмана

Расчет энтропии после читерства

Для мошенничества с более высокой энтропией сообщение о подбрасывании монеты более ценно! ! !

② Получение информации
Предположим, что имеется обучающий набор экземпляров C. Если мы передаем атрибут P в качестве корневого узла текущего дерева, C будет разделен на подмножества {C1, C2, C3 .....}. Ожидание принятия P в качестве информации, необходимой для завершения дерева с узлом, таково:

ожидания информации, необходимой для завершения дерева

Таким образом, выигрыш от атрибута P передается через деревообщий объем информацииминусИнформационные ожидания для деревьев завершениявычислять:

получение информации

Или возьмем в качестве примера кредитный риск: P(низкий)=5/14, P(умеренный)=3/14, P(высокий)=6/14. Таким образом, общий объем информации рассчитывается следующим образом:

общий объем информации

Если в качестве корневого узла дерева используется доход, экземпляры в таблице делятся на C1 = {1,4,7,11}, C2 = {2,3,12,14} и C3 = {5,6 ,8,9,10,13}.

часть дерева решений

Ожидаемые значения, необходимые для завершения дерева:

Желаемое значение, необходимое для завершения дерева

Наконец, усиление (доход) = 1,531 - 0,564 = 0,967 бит.
Аналогично можно получить:

Атрибуты	Прирост информации (бит)
gain(credit history)	0.266
gain(debt)	0.063
gain(collateral)	0.206

Поскольку доход обеспечивает наибольшую информационную выгоду, ID3 выберет его в качестве корневого узла.

3.3.4 Оценка ID3

Хотя алгоритм ID3 создает простые деревья решений (включая корневые узлы, узлы решений и конечные узлы), такие деревья не обязательно эффективны для предсказания классификации неизвестных экземпляров.

3.4 Оценка деревьев решений

Деревья решений подходят для дискретных данных, а результат переменной — конечное множество.
преимущество
- Сложность расчета дерева решений невелика, проста в использовании, эффективна!
- Деревья решений могут обрабатывать данные с нерелевантными функциями.
- С помощью деревьев решений можно легко построить ряд простых для понимания правил.
недостаток
- Сложность работы с отсутствующими данными, неверными данными и непрерывными данными.
- Большие наборы данных могут привести к очень большим деревьям решений.
- Связи между атрибутами в наборе данных игнорируются.
- переоснащение(включая обрезку)

использованная литература

Искусственный интеллект, 6-е издание
От обучения дерева решений к алгоритму байесовской классификации, EM, HMM
Подробное объяснение классических алгоритмов машинного обучения и реализации Python — Дерево решений
Scikit-Learn документация