Классификация. Гипотезы компактности и непрерывности

Август 10, 2022

Главная
Биология
Классификация. Гипотезы компактности и непрерывности

Содержание

2. Гипотезы компактности и непрерывности
3. Гипотеза компактности
4. Постановка задачи классификации Исторически возникла из задачи машинного зрения, поэтому часто употребляемый синоним – распознавание образов.
5. Метод k ближайших соседей
6. Меры близости
7. Метод k ближайших соседей Выбор k
8. Пример
10. 1-правило Алгоритм построения 1-правил Простейший алгоритм формирования элементарных правил для классификации объекта. Он строит правила по
11. Example Let T be the following table Then BestRule(Vote,Office,T) is "case (X.Office) { House: predict (X.Vote==Yes);
12. Если переменная имеет вещественный тип, то количество возможных значений может быть бесконечно. Для решения этой проблемы
13. Томас Байес — английский математик, священник, член Лондонского королевского общества. Автор теоремы Байеса — одной из
14. Теорема Байеса и классификация (1)
15. Принцип максимума апостериорной вероятности
16. Байесовский классификатор
17. Наивный байесовский классификатор Naive bayes
18. Оценка вероятностей в наивном байесовском классификаторе
20. Пример Naive bayes y x
21. Метод Naive bayes. Необходимо определить, состоится ли игра при следующих значениях независимых переменных (событие Е):
22. Определяем условные вероятности
23. Метод Naive bayes. Априорные Вероятности есть отношение объектов из обучающей выборки, принадлежащих классу , к общему
24. Метод Naive bayes. Вычислим следующие апостериорные вероятности:
25. Метод Naive bayes. Подставляя соответствующие вероятности получим следующие значения: Вероятность не учитывается, т.к. при нормализации вероятностей
26. Метод Naive bayes. В данном случае можно утверждать, что при указанных условиях игра состоится с вероятностью:
27. Использование многомерного нормального распределения в задаче распознавания образов В статистической теории распознавания образов используется аппроксимация плотности
30. где В результате решающее правило распознавания имеет вид В случае линейного классификатора и рещающее правило примет
31. Сэр Ро́налд Э́йлмер Фи́шер (или Рональд, англ. Sir Ronald Aylmer Fisher, 17 февраля, 17 февраля 1890,
32. Линейный дискриминант Фишера
37. Классификация с использованием деревьев решений Лекция 3
38. Деревья решений
39. Пример дерева классификации (Выдавать ли кредит?)
40. Деревья решений Деревья решений - это способ представления классификационных правил в иерархической, последовательной структуре. Области применения
41. Обычно каждый узел дерева решений включает проверку одной независимой переменной. Иногда в узле дерева две независимые
42. Методика "Разделяй и властвуй" Методика основана на рекурсивном разбиении множества объектов из обучающей выборки на подмножества,
43. Множество Т содержит объекты, относящиеся к разным классам. В этом случае следует разбить множество Т на
44. Вопрос в том, какую зависимую переменную выбрать для начального разбиения. От этого целиком зависит качество получившегося
45. Конструирование дерева решений Процесс конструирования дерева решений Рассматриваемая нами задача классификации относится к стратегии обучения с
46. Критерии расщепления Процесс создания дерева происходит сверху вниз, т.е. является нисходящим. В ходе процесса алгоритм должен
47. Алгориты построения деревьв Есть различные способы выбирать очередной атрибут: Алгоритм ID3Алгоритм ID3, где выбор атрибута происходит
48. Алгоритмы ID3 и С4.5 Алгоритм ID3 [32] был предложен Россом Куинланом в 1986 г. и основывался
49. Алгоритм ID3 ID3 (Iterative Dichotomiser 3) is an algorithm) is an algorithm invented by Ross Quinlan
50. Критерий расщепления ID3
51. Единственная доступная информация - каким образом классы распределены в множестве T и его подмножествах, получаемых при
52. Пусть freq(cr,I) - число объектов из обучающей выборки, относящихся к классу cr. Тогда вероятность того, что
53. Пример y x
54. Поскольку используется логарифм с двоичным основанием, то это выражение даёт количественную оценку в битах. Для оценки
55. Например, для переменной "Наблюдение", оценка будет следующей: бит. бит. бит. бит. Критерием для выбора атрибута (зависимой
56. В нашем примере значение Gain для независимой переменной "Наблюдение" (перспектива) будет равно: Gain(перспектива) = Info(I) -
57. Аналогичным образом можно посчитать значение Gain для каждого разбиения: Gain(температура) = 0.571 бит. Gain(влажность) = 0.971
58. ID3 Final tree
59. Алгоритм C4.5 C4.5 is an algorithm used to generate a decision tree is an algorithm used
60. Один из недостатков алгоритма ID3 является то, что он некорректно работает с атрибутами, имеющими уникальные значения
61. При условии, что имеется k классов и n - число объектов в обучающей выборке и одновременно
62. Алгоритм CART
63. Обучение дерева решений относится к классу обучения с учителем, то есть обучающая и тестовая выборки содержат
64. Если набор Т разбивается на две части Т1 и Т2 с числом примеров в каждом N1
65. Процедура разбиения CART Вектор предикторных переменных, подаваемый на вход дерева может содержать как числовые (порядковые) так
66. Процедура разбиения CART
67. Механизм отсечения дерева Механизм отсечения дерева, оригинальное название minimal cost-complexity tree pruning, – наиболее серьезное отличие
68. Определим полную стоимость (оценку/показатель затраты-сложность) дерева Т как: где |T| – число листов (терминальных узлов) дерева,
69. Определим Tmax – максимальное по размеру дерево, которое предстоит обрезать. Если мы зафиксируем значение α тогда
71. Скачать презентацию

Слайд 2

Гипотезы компактности и непрерывности

Слайд 3

Гипотеза компактности

Слайд 4

Постановка задачи классификации
Исторически возникла из задачи машинного зрения, поэтому часто употребляемый синоним

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

Слайд 5

Метод k ближайших соседей

Слайд 6

Меры близости

Слайд 7

Метод k ближайших соседей
Выбор k

Слайд 8

Пример

Слайд 9

Слайд 10

1-правило
Алгоритм построения 1-правил
Простейший алгоритм формирования элементарных правил для классификации объекта. Он

строит правила по значению одной независимой переменной, поэтому в литературе его часто называют "1-правило" (1-rule) или кратко 1R-алгоритм.
Идея алгоритма :
Для любой независимой переменной формируется правило, которое классифицирует объекты из обучающей выборки. При этом указывается значение зависимой переменной, которое наиболее часто встречается у объектов с выбранным значением независимой переменной. В этом случае ошибкой правила является количество объектов, имеющих то же значение рассматриваемой переменной, но не относящихся к выбранному классу.
Таким образом, для каждой переменной будет получен набор правил (для каждого значения). Оценив степень ошибки каждого набора, выбирается переменная, для которой построены правила с наименьшей ошибкой.

Слайд 11

Example
Let T be the following table
Then BestRule(Vote,Office,T) is "case (X.Office)

{ House: predict (X.Vote==Yes); Senate: predict(X.Vote==No); }" with an accuracy of 6/10.
BestRule(Vote,Party,T) is "case (X.Party)
{ Dem: predict (X.Vote==No); Rep: predict(X.Vote==Yes); }" with an accuracy of 6/10.
BestRule(Vote,State,T) is "case (X.State)
{ NY: predict (X.Vote==No); NJ: predict (X.Vote==No); CT: predict(X.Vote==Yes) }" with an accuracy of 8/10.
The 1R algorithm therefore returns the rule "case (X.State) { NY: predict (X.Vote==No); NJ: predict (X.Vote==No); CT: predict(X.Vote==Yes) }"

Vote - избирательный голос
House - палата

Слайд 12

Если переменная имеет вещественный тип, то количество возможных значений может быть

бесконечно. Для решения этой проблемы всю область значений такой переменной разбивают на интервалы таким образом, чтобы каждый из них соответствовал определенному классу в обучающей выборке.
Проблема 1R-алгоритма — это сверхчувствительность (overfitting). Дело в том, что алгоритм будет выбирать переменные, принимающие наибольшее количество возможных значений, т. к. для них ошибка будет наименьшей. Например, для переменной, являющейся ключом (т. е. для каждого объекта свое уникальное значение), ошибка будет равна нулю. Однако для таких переменных правила будут абсолютно бесполезны, поэтому при формировании обучающей выборки для данного алгоритма важно правильно выбрать набор независимых переменных. В заключение необходимо отметить, что 1R-алгоритм, несмотря на свою простоту, во многих случаях на практике оказывается достаточно эффективным. Это объясняется тем, что многие объекты действительно можно классифицировать лишь по одному атрибуту. Кроме того, немногочисленность формируемых правил позволяет легко понять и использовать полученные результаты.

Слайд 13

Томас Байес — английский математик, священник, член Лондонского королевского общества. Автор

теоремы Байеса — одной из основных теорем элементарной теории вероятностей.
Биография
Байес родился в Лондоне в 1702 году. Его отец — Джошуа Байес — был пресвитерианским священником, представителем известного нонконформистского рода из Шеффилда. Умер в 1761 году.
Математические интересы Байеса относились к теории вероятностей. Он сформулировал и решил одну из основных задач этого раздела математики (теорема Байеса). Работа Байеса была опубликована уже после его смерти, в 1763 году.
За всю жизнь Томас Байес опубликовал только две работу — одну богословскую и одну математическую:
Divine Benevolence, or an Attempt to Prove That the Principal End of the Divine Providence and Government is the Happiness of His Creatures (1731г.)
An Introduction to the Doctrine of Fluxions, and a Defence of the Mathematicians Against the Objections of the Author of The Analyst (опубликовано анонимно в 1736г.)

Слайд 14

Теорема Байеса и классификация
(1)

Слайд 15

Принцип максимума апостериорной вероятности

Слайд 16

Байесовский классификатор

Слайд 17

Наивный байесовский классификатор Naive bayes

Слайд 18

Оценка вероятностей в наивном байесовском классификаторе

Слайд 19

Слайд 20

Пример Naive bayes
y
x

Слайд 21

Метод Naive bayes.
Необходимо определить, состоится ли игра при следующих значениях независимых

переменных (событие Е):

Слайд 22

Определяем условные вероятности

Слайд 23

Метод Naive bayes.
Априорные Вероятности есть отношение объектов из обучающей выборки,

принадлежащих классу , к общему количеству объектов в выборке. В данном примере это:

Слайд 24

Метод Naive bayes.
Вычислим следующие апостериорные вероятности:

Слайд 25

Метод Naive bayes.
Подставляя соответствующие вероятности получим следующие значения:
Вероятность не

учитывается, т.к. при нормализации вероятностей для каждого из возможных правил она исчезает. Нормализованная вероятность для правила вычисляется по формуле:

Слайд 26

Метод Naive bayes.
В данном случае можно утверждать, что при указанных

условиях игра состоится с вероятностью:
и не состоится с вероятностью:
Таким образом, при указанных условиях более вероятно, что игра не состоится.

Слайд 27

Использование многомерного нормального распределения в задаче распознавания образов
В статистической теории распознавания

образов используется аппроксимация плотности с помощь многомерного нормального распределения.
При решении задач распознавания с помощью формулы Байеса в форме (1) могут использоваться плотности вероятности p1(x),….,pn(x), в которых переменные X1,…,Xn не обязательно являются независимыми. Чаще всего используется многомерное нормальное распределения. Плотность данного распределения в общем виде представляется выражением
где

Слайд 28

Слайд 29

Слайд 30

где
В результате решающее правило распознавания имеет вид
В случае линейного классификатора и

рещающее
правило примет вид

где

Слайд 31

Сэр Ро́налд Э́йлмер Фи́шер (или Рональд, англ. Sir Ronald Aylmer Fisher, 17

февраля, 17 февраля 1890, 17 февраля 1890 — 29 июля, 17 февраля 1890 — 29 июля 1962, 17 февраля 1890 — 29 июля 1962) — английский, 17 февраля 1890 — 29 июля 1962) — английский статистик, 17 февраля 1890 — 29 июля 1962) — английский статистик, биолог-эволюционист, 17 февраля 1890 — 29 июля 1962) — английский статистик, биолог-эволюционист и генетик, 17 февраля 1890 — 29 июля 1962) — английский статистик, биолог-эволюционист и генетик. Член Лондонского королевского общества, 17 февраля 1890 — 29 июля 1962) — английский статистик, биолог-эволюционист и генетик. Член Лондонского королевского общества (1929) и Королевского статистического общества, почётный член многих академий и научных обществ.
В математической статистикеВ математической статистике Фишер, разработал фундамент теории оценок параметровВ математической статистике Фишер, разработал фундамент теории оценок параметров, статистических решенийВ математической статистике Фишер, разработал фундамент теории оценок параметров, статистических решений, планирования экспериментаВ математической статистике Фишер, разработал фундамент теории оценок параметров, статистических решений, планирования эксперимента и проверки гипотез.
Фишер перечислил требования к статистическим оценкам: состоятельностьФишер перечислил требования к статистическим оценкам: состоятельность, эффективностьФишер перечислил требования к статистическим оценкам: состоятельность, эффективность, достаточностьФишер перечислил требования к статистическим оценкам: состоятельность, эффективность, достаточность. Для выбора наилучших оценок Фишер предложил метод максимального правдоподобия[11]. Фундаментальный в теории вероятностей термин «дисперсия» также был введен Фишером в 1916 году.
Использованный им для демонстрации дискриминантного анализаИспользованный им для демонстрации дискриминантного анализа набор данных стал известен под названием «Ирисы Фишера».
Фундаментальные труды Фишера:
1922: «О математических основах теоретической статистики»
1925: «Статистические методы для исследователей»
1930: «Генетическая теория естественного отбора»
1935: «Планирование экспериментов»
1956: «Статистические методы и научный вывод»

Слайд 32

Линейный дискриминант Фишера

Слайд 33

Слайд 34

Слайд 35

Слайд 36

Слайд 37

Классификация с использованием деревьев решений
Лекция 3

Слайд 38

Деревья решений

Слайд 39

Пример дерева классификации (Выдавать ли кредит?)

Слайд 40

Деревья решений
Деревья решений - это способ представления классификационных правил в иерархической,

последовательной структуре.
Области применения деревьев решений
Деревья решений являются прекрасным инструментом в системах поддержки принятия решений, интеллектуального анализа данных (data mining). В состав многих пакетов, предназначенных для интеллектуального анализа данных, уже включены методы построения деревьев решений.
Деревья решений успешно применяются для решения практических задач в следующих областях:
Банковское дело. Оценка кредитоспособности клиентов банка при выдаче кредитов.
Промышленность. Контроль за качеством продукции (выявление дефектов), испытания без разрушений (например проверка качества сварки) и т.д.
Медицина. Диагностика различных заболеваний.
Молекулярная биология. Анализ строения аминокислот.
Телекоммуникации.

Слайд 41

Обычно каждый узел дерева решений включает проверку одной независимой переменной. Иногда

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

Слайд 42

Методика "Разделяй и властвуй"
Методика основана на рекурсивном разбиении множества объектов из

обучающей выборки на подмножества, содержащие объекты, относящиеся к одинаковым классам. Сперва выбирается независимая переменная, которая помещается в корень дерева. Из вершины строятся ветви, соответствующие всем возможным значениям выбранной независимой переменной. Множество объектов из обучающей выборки разбивается на несколько подмножеств в соответствии со значением выбранной независимой переменной. Таким образом, в каждом подмножестве будут находиться объекты, у которых значение выбранной независимой переменной будет одно и то же. Относительно обучающей выборки T и множества классов C возможны три ситуации:
множество Т содержит один или более объектов, относящихся к одному классу cr. Тогда дерево решений для T - это лист, определяющий класс cr;
множество Т не содержит ни одного объекта (пустое множество). Тогда это снова лист, и класс, ассоциированный с листом, выбирается из другого множества, отличного от Т, например из множества, ассоциированного с родителем;

Слайд 43

Множество Т содержит объекты, относящиеся к разным классам. В этом случае

следует разбить множество Т на некоторые подмножества. Для этого выбирается одна из независимых переменных xh, имеющая два и более отличных друг от друга значений
Множество Т разбивается на подмножества T1,T2,...,Tn, где каждое подмножество Ti содержит все объекты, у которых значение выбранной зависимой переменной равно
Далее процесс продолжается рекурсивно для каждого подмножества до тех пор, пока значение зависимой переменной во вновь образованном подмножестве не будет одинаковым (когда объекты принадлежат одному классу). В этом случае процесс для данной ветви дерева прекращается.
При использовании данной методики построение дерева решений будет происходить сверху вниз. Большинство алгоритмов, которые её используют, являются "жадными алгоритмами". Это значит, что если один раз переменная была выбрана и по ней было произведено разбиение, то алгоритм не может вернуться назад и выбрать другую переменную, которая дала бы лучшее разбиение

Слайд 44

Вопрос в том, какую зависимую переменную выбрать для начального разбиения. От

этого целиком зависит качество получившегося дерева. Общее правило для выбора переменной для разбиения: выбранная переменная должны разбить множество так, чтобы получаемые в итоге подмножества состояли из объектов, принадлежащих к одному классу, или были максимально приближены к этому, т.е. чтобы количество объектов из других классов ("примесей") в каждом из этих множеств было минимальным. Другой проблемой при построении дерева является проблема остановки его разбиения. Методы её решения:
Ранняя остановка. Использование статистических методов для оценки целесообразности дальнейшего разбиения. Экономит время обучения модели, но строит менее точные классификационные модели.
Ограничение глубины дерева. Нужно остановить дальнейшее построение, если разбиение ведёт к дереву с глубиной, превышающей заданное значение.
Разбиение должно быть нетривиальным, т.е. получившиеся в результате узлы должны содержать не менее заданного количества объектов.
Отсечение ветвей (снизу вверх). Построить дерево, отсечь или заменить поддеревом те ветви, которые не приведут к возрастанию ошибки. Под ошибкой понимается количество неправильно классифицированных объектов, а точностью дерева решений отношение правильно классифицированных объектов при обучении к общему количеству объектов из обучающего множества.

Слайд 45

Конструирование дерева решений
Процесс конструирования дерева решений
Рассматриваемая нами задача классификации относится к

стратегии обучения с учителем, иногда называемого индуктивным обучением. В этих случаях все объекты тренировочного набора данных заранее отнесены к одному из предопределенных классов.
Алгоритмы конструирования деревьев решений состоят из этапов "построение" или " создание " дерева (tree building) и " сокращение " дерева (tree pruning).
В ходе создания дерева решаются вопросы выбора критерия расщепления и остановки обучения (если это предусмотрено алгоритмом).
В ходе этапа сокращения дерева решается вопрос отсечения некоторых его ветвей.

Слайд 46

Критерии расщепления
Процесс создания дерева происходит сверху вниз, т.е. является нисходящим. В ходе процесса

алгоритм должен найти такой критерий расщепления, иногда также называемый критерием разбиения, чтобы разбить множество на подмножества, которые бы ассоциировались с данным узлом проверки. Каждый узел проверки должен быть помечен определенным атрибутом.
Существует правило выбора атрибута: он должен разбивать исходное множество данных таким образом, чтобы объекты подмножеств, получаемых в результате этого разбиения, преимущественно являлись представителями одного класса. Последняя фраза означает, что количество объектов из других классов, так называемых "примесей", в каждом классе должно стремиться к минимуму.
Существуют различные критерии расщепления. Наиболее известные - мера энтропии и индекс Gini.

Слайд 47

Алгориты построения деревьв
Есть различные способы выбирать очередной атрибут:
Алгоритм ID3Алгоритм ID3, где

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

Слайд 48

Алгоритмы ID3 и С4.5
Алгоритм ID3 [32] был предложен Россом Куинланом в

1986 г. и основывался на алгоритме Ханта, учеником которого был Куинлан. Алгоритм ID3 был основан на использовании критерия информационного выигрыша для выбора вершины и переменной для ветвления. Синтез решающего дерева завершался либо в случае достижения его корректности относительно выборки, либо когда ветвление ни в одной некорректной вершине не приводило к увеличению информационного выигрыша.
Алгоритм C4.5 [31]. Этот алгоритм явился развитием идей, реализованных в ID3, был разработан Р. Куинланом в 1993 г. и использовал отношение выигрыша (gain ratio) как критерий ветвления. Процесс синтеза (добавления вершин) в алгоритме C4.5 прекращался, когда число точек для разбиения становилось меньше некоторого порога.

Слайд 49

Алгоритм ID3
ID3 (Iterative Dichotomiser 3) is an algorithm) is an algorithm

invented by Ross Quinlan
Quinlan, J. R. 1986. Induction of Decision Trees. Mach. Learn. 1, 1 (Mar. 1986), 81–106
Рассмотрим критерий выбора независимой переменной, от которой будет строиться дерево. Полный набор вариантов разбиения |X| - количество независимых переменных. Рассмотрим проверку переменой xh, которая принимает m значений ch1,ch2,...,chm. Тогда разбиение множества всех объектов обучающей выборки N по проверке переменной xh даст подмножества T1,T2,...,Tm.
Мы ожидаем, что при разбиении исходного множества, будем получать подмножества с меньшим числом объектом, но более упорядоченные. Так, чтобы в каждом из них были по-возможности объекты одного класса. Эта мера упорядоченности (неопределенности) характеризуется информацией. В контексте рассматриваемой задачи это количество информации, необходимое для того, чтобы отнести объект к тому или иному классу.
При разделении исходного множества на более мелкие подмножества, используя в качестве критерия для разделения значения выбранной независимой переменной, неопределённость принадлежности объектов конкретным классам будет уменьшаться. Задача состоит в том, чтобы выбрать такие независимые переменные, чтобы максимально уменьшить эту неопределенность и в конечном итоге получить подмножества, содержащие объекты только одного класса. В последнем случае неопределенность равна нулю.

Слайд 50

Критерий расщепления ID3

Слайд 51

Единственная доступная информация - каким образом классы распределены в множестве T

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

Слайд 52

Пусть freq(cr,I) - число объектов из обучающей выборки, относящихся к классу

cr. Тогда вероятность того, что случайно выбранный объект из обучающего множества I будет принадлежать классу cr равняется:

Подсчитаем количество информации, основываясь на числе объектов того или иного класса, получившихся в узле дерева после разбиения исходного множества. Согласно теории информации оценку среднего количества информации, необходимого для определения класса объекта из множества Т, даёт выражение:

(понятие информационной энтропии)

Подставляя в эту формулу полученное значение для P, получим:

Слайд 53

Пример
y
x

Слайд 54

Поскольку используется логарифм с двоичным основанием, то это выражение даёт количественную

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

Ту же оценку, но уже после разбиения множества Т по xh даёт следующее выражение:

Слайд 55

Например, для переменной "Наблюдение", оценка будет следующей:
бит.
бит.
бит.
бит.
Критерием для выбора атрибута (зависимой

переменной) будет являться следующая формула:

Критерий Gain рассчитывается для всех независимых переменных после чего выбирается переменная с максимальным значением Gain. Необходимо выбрать такую переменную, чтобы при разбиении по ней один из классов имел наибольшую вероятность появления. Это возможно в том случае, когда энтропия Infox имеет минимальное значение и, соответственно, критерий Gain(X) достигает своего максимума.

Слайд 56

В нашем примере значение Gain для независимой переменной "Наблюдение" (перспектива) будет

равно:

Gain(перспектива) = Info(I) - Info(перспектива) = 0.94 - 0.693 = 0.247 бит.

Аналогичные расчеты можно провести для других независимых переменных. В результате получаем:

Gain(наблюдение) = 0.247 бит. Gain(температура) = 0.029 бит. Gain(влажность) = 0.152 бит. Gain(ветер) = 0.048 бит.

Таким образом, для первоначального разбиения лучше всего выбрать независимую переменную "Наблюдение". Далее требуется выбрать следующую переменную для разбиения. Варианты разбиения представлены на рисунке.

Gain (гейн) - прирост

Слайд 57

Аналогичным образом можно посчитать
значение Gain для каждого разбиения:
Gain(температура) = 0.571 бит. Gain(влажность)

= 0.971 бит. Gain(ветер) = 0.02 бит.
Видно, что следующей переменной,
по которой будет разбиваться
подмножество T
(солнечно) будет "Влажность".
Дальнейшее разбиение этой ветви
уже не потребуется, т.к. в получившихся
подмножествах все объекты относятся
только к одному классу.

Если в процессе работы алгоритма получен узел, ассоциированный с пустым множеством (ни один объект не попал в данный узел), то он помечается как лист, и в качестве решения листа выбирается наиболее часто встречающийся класс у непосредственного предка данного листа.

Слайд 58

ID3 Final tree

Слайд 59

Алгоритм C4.5
C4.5 is an algorithm used to generate a decision tree

is an algorithm used to generate a decision tree developed by Ross Quinlan.[1] C4.5 is an extension of Quinlan's earlier ID3 algorithm.
Quinlan, J. R. C4.5: Programs for Machine Learning. Morgan Kaufmann Publishers, 1993.
Представляет собой усовершенствованный вариант алгоритма ID3. Среди улучшений стоит отметить следующие:
Возможность работать не только с категориальными атрибутами, но также с числовыми. Для этого алгоритм разбивает область значений независимой переменной на несколько интервалов и делит исходное множество на подмножества в соответствии с тем интервалом, в который попадает значение зависимой переменной.
После построения дерева происходит усечение его ветвей. Если получившееся дерево слишком велико, выполняется либо группировка нескольких узлов в один лист, либо замещение узла дерева нижележащим поддеревом. Перед операцией над деревом вычисляется ошибка правила классификации, содержащегося в рассматриваемом узле. Если после замещения (или группировки) ошибка не возрастает (и не сильно увеличивается энтропия), значит замену можно произвести без ущерба для построенной модели.

Слайд 60

Один из недостатков алгоритма ID3 является то, что он некорректно работает

с атрибутами, имеющими уникальные значения для всех объектов из обучающей выборки. Для таких объектов информационная энтропия равна нулю и никаких новых данных от построенного дерева по данной зависимой переменной получить не удасться. Поскольку получаемые после разбиения подмножества буду содержать по одному объекту. Алгоритм C4.5 решает эту проблему путём введения нормализации. Оценивается не количество объектов того или иного класса после разбиения, а число подмножеств и их мощность (число элементов).
Выражение

оценивает потенциальную информацию, получаемую при разбиении множества Т на m подмножеств. Критерием выбора переменной для разбиения будет выражение:

Split (сплет)- расщепление

Ratio (рейдже) - отношение

Слайд 61

При условии, что имеется k классов и n - число объектов

в обучающей выборке и одновременно количество значений переменных, тогда числитель максимально будет равен log2k, а знаменатель максимально равен log2n. Если предположить, что количество объектов заведомо больше количества классов, то знаменатель растёт быстрее, чем числитель и, соответственно, значение выражения будет небольшим. В обучающей выборке могут присутствовать объекты с пропущенными значениями атрибутов. В этом случае их либо отбрасывают (что влечёт за собой риск потерять часть данных), либо применить подход, предполагающий, что пропущенные значения по переменной вероятностно распределены пропорционально частоте появления существующих значений.

Слайд 62

Алгоритм CART

Слайд 63

Обучение дерева решений относится к классу обучения с учителем, то есть

обучающая и тестовая выборки содержат классифицированный набор примеров. Оценочная функция, используемая алгоритмом CART, базируется на интуитивной идее уменьшения нечистоты (неопределённости) в узле. Рассмотрим задачу с двумя классами и узлом, имеющим по 50 примеров одного класса. Узел имеет максимальную "нечистоту". Если будет найдено разбиение, которое разбивает данные на две подгруппы 40:5 примеров в одной и 10:45 в другой, то интуитивно "нечистота" уменьшится. Она полностью исчезнет, когда будет найдено разбиение, которое создаст подгруппы 50:0 и 0:50. В алгоритме CART идея "нечистоты" формализована в индексе Gini. Если набор данных Т содержит данные n классов, тогда индекс Gini определяется как:
где pi – вероятность (относительная частота) класса i в T.

Слайд 64

Если набор Т разбивается на две части Т1 и Т2 с

числом примеров в каждом N1 и N2 соответственно, тогда показатель качества разбиения будет равен:

Наилучшим считается то разбиение, для которого Ginisplit(T) минимально. Обозначим N – число примеров в узле – предке, L, R – число примеров соответственно в левом и правом потомке, li и ri – число экземпляров i-го класса в левом/правом потомке. Тогда качество разбиения оценивается по следующей формуле:

или, что эквивалентно,

Слайд 65

Процедура разбиения CART
Вектор предикторных переменных, подаваемый на вход дерева может содержать

как числовые (порядковые) так и категориальные переменные. В любом случае в каждом узле разбиение идет только по одной переменной. Если переменная числового типа, то в узле формируется правило вида xi <= c. Где с – некоторый порог, который чаще всего выбирается как среднее арифметическое двух соседних упорядоченных значений переменной xi обучающей выборки. Если переменная категориального типа, то в узле формируется правило xi V(xi), где V(xi) – некоторое непустое подмножество множества значений переменной xi в обучающей выборке. Следовательно, для n значений числового атрибута алгоритм сравнивает n-1 разбиений, а для категориального (2n-1 – 1). На каждом шаге построения дерева алгоритм последовательно сравнивает все возможные разбиения для всех атрибутов и выбирает наилучший атрибут и наилучшее разбиение для него.

Слайд 66

Процедура разбиения CART

Слайд 67

Механизм отсечения дерева
Механизм отсечения дерева, оригинальное название minimal cost-complexity tree pruning,

– наиболее серьезное отличие алгоритма CART от других алгоритмов построения дерева. CART рассматривает отсечение как получение компромисса между двумя проблемами: получение дерева оптимального размера и получение точной оценки вероятности ошибочной классификации.
Основная проблема отсечения – большое количество всех возможных отсеченных поддеревьев для одного дерева.
Базовая идея метода – не рассматривать все возможные поддеревья, ограничившись только "лучшими представителями" согласно приведённой ниже оценке.
Обозначим |T| – число листов дерева, R(T) – ошибка классификации дерева, равная отношению числа неправильно классифицированных примеров к числу примеров в обучающей выборке.

Слайд 68

Определим полную стоимость (оценку/показатель затраты-сложность) дерева Т как:
где |T| – число

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

Слайд 69

Определим Tmax – максимальное по размеру дерево, которое предстоит обрезать. Если

мы зафиксируем значение α тогда существует наименьшее минимизируемое поддерево, которое выполняет следующие условия:
Первое условие говорит, что не существует такого поддерева дерева Tmax , которое имело бы меньшую стоимость, чем T(α) при этом значении α. Второе условие говорит, что если существует более одного поддерева, имеющего данную полную стоимость, тогда мы выбираем наименьшее дерево.

Классификация. Гипотезы компактности и непрерывности

Содержание

Гипотезы компактности и непрерывности

Гипотеза компактности

Постановка задачи классификацииИсторически возникла из задачи машинного зрения, поэтому часто употребляемый синоним

Метод k ближайших соседей

Меры близости

Метод k ближайших соседейВыбор k

Пример

1-правило Алгоритм построения 1-правилПростейший алгоритм формирования элементарных правил для классификации объекта. Он

Example Let T be the following tableThen BestRule(Vote,Office,T) is "case (X.Office)

Если переменная имеет вещественный тип, то количество возможных значений может быть

Томас Байес — английский математик, священник, член Лондонского королевского общества. Автор

Теорема Байеса и классификация(1)

Принцип максимума апостериорной вероятности

Байесовский классификатор

Наивный байесовский классификатор Naive bayes

Оценка вероятностей в наивном байесовском классификаторе

Пример Naive bayesyx

Метод Naive bayes.Необходимо определить, состоится ли игра при следующих значениях независимых

Определяем условные вероятности

Метод Naive bayes. Априорные Вероятности есть отношение объектов из обучающей выборки,

Метод Naive bayes.Вычислим следующие апостериорные вероятности:

Метод Naive bayes. Подставляя соответствующие вероятности получим следующие значения: Вероятность не

Метод Naive bayes. В данном случае можно утверждать, что при указанных

Использование многомерного нормального распределения в задаче распознавания образов В статистической теории распознавания

гдеВ результате решающее правило распознавания имеет видВ случае линейного классификатора и