к библиотеке к оглавлению ТПОИ к дискретной математике технологии программирования

Методы и средства анализа данных

1. Методы построения правил классификации
- 1.2. Алгоритм построения 1-правил
- 2.2.2 Метод Naive Bayes
2. Методы построения деревьев решений
3. Методы построения математических функций
- 3.1 Корреляционный анализ
  - 3.1.1 Для двух переменных
  - 3.1.2 Для произвольного числа переменных
- 3.2 Регрессионный анализ
4. Поиск ассоциативных правил
5. Секвенциальный анализ
6. Кластеризация. Типы алгоритмов
7. Кластеризация. Итеративные и плотностные алгоритмы
- 7.1 Итеративные алгоритмы
  - 7.1.1 Алгоритм k-means
  - 7.1.2 Алгоритм Fuzzy C-Means
- 7.2 Плотностные алгоритмы
  - 7.2.1 Алгоритм DBSCAN
8. Кластеризация. Модельные, концептуальные, сетевые алгоритмы

Методы построения правил классификации

Алгоритм построения 1-правил

Пусть у нас есть независимые переменные $A 1 ... A j ... A k$ , принимающие значения $< x_1^1...x_n^1>,...<x_1^j...x_n^j>,...<x_1^k...x_n^k>$ соответственно, и зависимая переменная C, принимающая значения $c 1 ... c r$ . Для любого возможного значения каждой независимой переменной формируется правило, которое классифицирует объект из обучающей выборки. В если-части правила указывают значение независимой переменной (Если $A^j=x_i^j$ ). В то-части правила указывается наиболее часто встречающееся значение зависимой переменной у данного значения независимой переменной(то $C = c r$ ). Ошибкой правила является количество объектов, имеющих данное значение рассматриваемой независимой переменной ( $A^j=x_i^j$ ), но не имеющих наиболее часто встречающееся значение зависимой переменной у данного значения независимой переменной( $C \ne c_r$ ). Оценив ошибки, выбирается переменная, для которой ошибка набора минимальна.

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

Метод Naive Bayes

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

Свойства наивной классификации:

1. Использование всех переменных и определение всех зависимостей между ними.

2. Наличие двух предположений относительно переменных:

все переменные являются одинаково важными;
все переменные являются статистически независимыми, т.е. значение одной переменной ничего не говорит о значении другой.

Вероятность того, что некий объект $i i$ , относится к классу $c r (y = c r)$ обозначим как $P (y = c r)$ . Событие, соответствующее равенству независимых переменных определенному значению, обозначим как Е, а его вероятность - Р(Е). Идея алгоритма в расчете условной вероятности принадлежности объекта к сr при равенстве его независимых переменных определенным значениям. Из тервера:

$P(y=c_r|E)=\frac{P(E|y=c_r) * P(y=c_r)}{P(E)}$

Таким образом формулируются правила, в условных частях которых сравниваются все независимые переменные с соответсввующими возможными значениями. В заключительной части - все возможные значения зависимой переменной: ${x_1=c_1^k, ..., x_n=c_n^k, y=c_r}$ ....{и так для все наборов} Для каждого из этих правил по формуле Байеса определяется его вероятность. Так как независимые переменные независимы друг от друга, то :

$P(E|y=c_r)=P(x_1=c_1^k|y=c_r)*...*P(x_n=c_n^k|y=c_r),$ что подставляем в верхную формулу и получаем вероятность всего правила.

Вероятность принадлежности объекта к классу c_r при равенстве его переменной x_n определенному значению с_n^k :

$P(x_n=c_n^k|y=c_r)=\frac{P(x_n=c_n^k \And y=c_r)}{P(y=c_r)}$

Нормализованная вероятность вычисляется по формуле:

$P'(y=cr|E) = \frac {P(y=c_r|E)} {\sum_{c_r} P(y=c_r|E)}$

и является вероятностью наступления данного исхода вообще, а не только при E. P(E) просто сокращается.

Проблема: в обучающей выборке может не быть объекта с $x_n=c_n^k$ и при этом принадлежащему к классу $c r$ . Тогда вероятность равна нулю и соответственно вероятность правила равна нулю. Чтобы этого избежать, к каждой вероятности прибавляют значение, отличное от нуля. Это называется оценочной функцией Лапласа. При подсчете вероятностей тогда эти вероятности пропускаются.

Методы построения деревьев решений

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

Листья деревьев соответствуют значениям зависимой переменной, т.е. классам.

Методика "Разделяй и властвуй"

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

множество Т содержит один или более объектов, относящихся к одному классу $c r$ . Тогда дерево решений для T - это лист, определяющий класс $c r$ ;
множество Т не содержит ни одного объекта (пустое множество). Тогда это снова лист, и класс, ассоциированный с листом, выбирается из другого множества, отличного от Т, например из множества, ассоциированного с родителем;
Множество Т содержит объекты, относящиеся к разным классам. В этом случае следует разбить множество Т на некоторые подмножества. Для этого выбирается одна из независимых переменных $x h$ , имеющая два и более отличных друг от друга значений $c_h^1, c_h^2 ..., c_h^n$ ; Множество Т разбивается на подмножества $T 1, T 2,..., T n$ , где каждое подмножество $T i$ содержит все объекты, у которых значение выбранной зависимой переменной равно $c_h^i$ . Далее процесс продолжается рекурсивно для каждого подмножества до тех пор, пока значение зависимой переменной во вновь образованном подмножестве не будет одинаковым (когда объекты принадлежат одному классу). В этом случае процесс для данной ветви дерева прекращается.

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

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

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

Алгоритм ID3

Рассмотрим критерий выбора независимой переменной, от которой будет строиться дерево.
Полный набор вариантов разбиения |X| - количество независимых переменных.
Рассмотрим проверку переменой $x h$ , которая принимает m значений $c h 1, c h 2,..., c h m$ .
Тогда разбиение множества всех объектов обучающей выборки N по проверке переменной $x h$ даст подмножества $T 1, T 2,..., T m$ .

Мы ожидаем, что при разбиении исходного множества, будем получать подмножества с меньшим числом объектом, но более упорядоченные.
Так, чтобы в каждом из них были по-возможности объекты одного класса.
Эта мера упорядоченности (неопределенности) характеризуется информацией.
В контексте рассматриваемой задачи это количество информации, необходимое для того, чтобы отнести объект к тому или иному классу.
При разделении исходного множества на более мелкие подмножества, используя в качестве критерия для разделения значения выбранной независимой переменной,
неопределённость принадлежности объектов конкретным классам будет уменьшаться. Задача состоит в том, чтобы выбрать такие независимые переменные,
чтобы максимально уменьшить эту неопределенность и в конечном итоге получить подмножества, содержащие объекты только одного класса.
В последнем случае неопределенность равна нулю.

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

Пусть freq( $c r$ ,I) - число объектов из обучающей выборки, относящихся к классу $c r$ .
Тогда вероятность того, что случайно выбранный объект из обучающего множества I будет принадлежать классу $c r$ равняется:
$P=\frac{freq(c_r,I)}{|I|}$ .
Подсчитаем количество информации, основываясь на числе объектов того или иного класса, получившихся в узле дерева после разбиения исходного множества.
Согласно теории информации оценку среднего количества информации, необходимого для определения класса объекта из множества Т, даёт выражение:
$H(x)=-\sum_{i=1}^np(i)\log_2 p(i)$ (понятие информационной энтропии)
Подставляя в эту формулу полученное значение для P, получим: $Info(I)=-\sum_{r=1}^k\frac{freq(c_r,I)}{|I|}\log_2(\frac{freq(c_r,I)}{|I|})$ .
Поскольку используется логарифм с двоичным основанием, то это выражение даёт количественную оценку в битах.
Для оценки количества информации справедливы следующие утверждения:

Если число объектов того или иного класса в получившемся подмножестве равно нулю, то количество информации также равно нулю.
Если число объектов одного класса равно числу объектов другого класса, то количество информации максимально.

Посчитаем значение информационной энтропии для исходного множества до разбиения.
$Info(I) = -\frac{9}{14}*log_2(\frac{9}{14}) - \frac{5}{14}*log_2(\frac{5}{14}) = 0.94$ бит.
Ту же оценку, но уже после разбиения множества Т по $x h$ даёт следующее выражение: $Info_{x_h}(T)=\sum_{i=1}^m\frac{T_i}{|T|}Info(T_i)$ или $Info_{x_h}(T)=\sum_{i=1}^m\frac{T_i}{|T|}(-\sum_{r=1}^k\frac{freq(c_r,T_i)}{|T_i|}\log_2(\frac{freq(c_r,T_i)}{|T_i|}))$ .
Например, для переменной "Наблюдение", оценка будет следующей:

$Info_{sun} = -\frac{2}{5} *log_2(\frac{2}{5}) - \frac{3}{5}*log_2(\frac{3}{5}) = 0.971$ бит.

$Info_{clouds} = -\frac{4}{4}*log_2(\frac{4}{4}) - \frac{0}{4}*log_2(\frac{0}{4}) = 0$ бит.

$Info_{rain} = -\frac{3}{5}*log_2(\frac{3}{5}) - \frac{2}{5}*log_2(\frac{2}{5}) = 0.971$ бит.

$Info_{condition} = \frac{5}{14}*0.971 + \frac{4}{14}*0 + \frac{5}{14}*0.971 = 0.693$ бит.

Критерием для выбора атрибута (зависимой переменной) будет являться следующая формула: $Gain(x_h)=Info(I)-Info_{x_h}(T).$
Критерий Gain рассчитывается для всех независимых переменных после чего выбирается переменная с максимальным значением Gain.
Необходимо выбрать такую переменную, чтобы при разбиении по ней один из классов имел наибольшую вероятность появления. Это возможно в том случае, когда энтропия $I n f o x$ имеет минимальное значение и, соответственно, критерий Gain(X) достигает своего максимума.
В нашем примере значение Gain для независимой переменной "Наблюдение" (перспектива) будет равно:

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

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

Gain(наблюдение) = 0.247 бит.

Gain(температура) = 0.029 бит.

Gain(влажность) = 0.152 бит.

Gain(ветер) = 0.048 бит.

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

Аналогичным образом можно посчитать значение Gain для каждого разбиения:

Gain(температура) = 0.571 бит.

Gain(влажность) = 0.971 бит.

Gain(ветер) = 0.02 бит.

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

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

Алгоритм C4.5

Представляет собой усовершенствованный вариант алгоритма ID3. Среди улучшений стоит отметить следующие:

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

Один из недостатков алгоритма ID3 является то, что он некорректно работает с атрибутами, имеющими уникальные значения для всех объектов из обучающей выборки. Для таких объектов информационная энтропия равна нулю и никаких новых данных от построенного дерева по данной зависимой переменной получить не удасться. Поскольку получаемые после разбиения подмножества буду содержать по одному объекту.
Алгоритм C4.5 решает эту проблему путём введения нормализации.
Оценивается не количество объектов того или иного класса после разбиения, а число подмножеств и их мощность (число элементов).
Выражение $split info(x_h)=-\sum_{i=1}^m\frac{T_i}{T}\log_2(\frac{T_i}{T})$ оценивает потенциальную информацию, получаемую при разбиении множества Т на m подмножеств.
Критерием выбора переменной для разбиения будет выражение: $gain ratio(x_h)=\frac{Gain(x_h)}{split info(x_h)}$ или $gain ratio(x_h)=\frac{Gain(x_h)}{-\sum_{i=1}^m\frac{T_i}{T}\log_2(\frac{T_i}{T})}$ .
При условии, что имеется k классов и n - число объектов в обучающей выборке и одновременно количество значений переменных, тогда числитель максимально будет равен $l o g 2 k$ , а знаменатель максимально равен $l o g 2 n$ . Если предположить, что количество объектов знаведомо больше количества классов, то знаменатель растёт быстрее, чем числитель и, соответственно, значение выражения будет небольшим.
В обучающей выборке могут присутствовать объекты с пропущенными значениями атрибутов. В этом случае их либо отбрасывают (что влечёт за собой риск потерять часть данных), либо применить подход, предполагающий, что пропущенные значения по переменной вероятностно распределены пропорционально частоте появления существующих значений.

Алгоритм покрытия

Алгоритм заключается в построении деревьев решений для каждого класса по отдельности. На каждом этапе генерируется проверка узла дерева, который покрывает несколько объектов обучающей выборки.
На каждом шаге алгоритма выбирается значение переменной, которое разделяет множество на два подмножества. Разделение должно выполняться так, чтобы все объекты класса, для которого строится дерево, принадлежали одному подмножеству. Такое разбиение производится до тех пор, пока не будет построено подмножество, содержащее только объекты одного класса.
Для выбора независимой переменной и её значения, которое разделяет множество, выполняются следующие действия:

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

После построения дерева для одного класса таким же образом строятся деревья для других классов.

Преимущества использования деревьев решений

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

Области применения деревьев решений

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

Деревья решений успешно применяются для решения практических задач в следующих областях:

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

к библиотеке к оглавлению ТПОИ к дискретной математике технологии программирования

Знаете ли Вы, что релятивизм (СТО и ОТО) не является истинной наукой? - Истинная наука обязательно опирается на причинность и законы природы, данные нам в физических явлениях (фактах). В отличие от этого СТО и ОТО построены на аксиоматических постулатах, то есть принципиально недоказуемых догматах, в которые обязаны верить последователи этих учений. То есть релятивизм есть форма религии, культа, раздуваемого политической машиной мифического авторитета Эйнштейна и верных его последователей, возводимых в ранг святых от релятивистской физики. Подробнее читайте в FAQ по эфирной физике.

НОВОСТИ ФОРУМА

Рыцари теории эфира