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

Пусть у нас есть независимые переменные

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 при равенстве его независимых переменных определенным значениям. Из тервера:

Таким образом формулируются правила, в условных частях которых сравниваются все независимые переменные с соответсввующими возможными значениями. В заключительной части - все возможные значения зависимой переменной: ${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 :

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

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

Проблема: в обучающей выборке может не быть объекта с $x_n=c_n^k$ и при этом принадлежащему к классу

c r

. Тогда вероятность равна нулю и соответственно вероятность правила равна нулю. Чтобы этого избежать, к каждой вероятности прибавляют значение, отличное от нуля. Это называется оценочной функцией Лапласа. При подсчете вероятностей тогда эти вероятности пропускаются.

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

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

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

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

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

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

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

Алгоритм 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 для каждого разбиения:

Видно, что следующей переменной, по которой будет разбиваться подмножество 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). В состав многих пакетов, предназначенных для интеллектуального анализа данных, уже включены методы построения деревьев решений.

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

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