к библиотеке   к оглавлению “ѕќ»   к дискретной математике   технологии программировани€

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

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

јлгоритм построени€ 1-правил

ѕусть у нас есть независимые переменные A1...Aj...Ak, принимающие значени€ < x_1^1...x_n^1>,...<x_1^j...x_n^j>,...<x_1^k...x_n^k> соответственно, и зависима€ переменна€ C, принимающа€ значени€ c1...cr. ƒл€ любого возможного значени€ каждой независимой переменной формируетс€ правило, которое классифицирует объект из обучающей выборки. ¬ если-части правила указывают значение независимой переменной (≈сли A^j=x_i^j). ¬ то-части правила указываетс€ наиболее часто встречающеес€ значение зависимой переменной у данного значени€ независимой переменной(то C = cr). ќшибкой правила €вл€етс€ количество объектов, имеющих данное значение рассматриваемой независимой переменной (A^j=x_i^j), но не имеющих наиболее часто встречающеес€ значение зависимой переменной у данного значени€ независимой переменной(C \ne c_r). ќценив ошибки, выбираетс€ переменна€, дл€ которой ошибка набора минимальна.

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

ћетод Naive Bayes

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

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

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

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

¬еро€тность того, что некий объект ii, относитс€ к классу cr(y = cr) обозначим как P(y = cr). —обытие, соответствующее равенству независимых переменных определенному значению, обозначим как ≈, а его веро€тность - –(≈). »де€ алгоритма в расчете условной веро€тности принадлежности объекта к с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), что подставл€ем в верхную формулу и получаем веро€тность всего правила.

¬еро€тность принадлежности объекта к классу cr при равенстве его переменной xn определенному значению сnk :

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 и при этом принадлежащему к классу cr. “огда веро€тность равна нулю и соответственно веро€тность правила равна нулю. „тобы этого избежать, к каждой веро€тности прибавл€ют значение, отличное от нул€. Ёто называетс€ оценочной функцией Ћапласа. ѕри подсчете веро€тностей тогда эти веро€тности пропускаютс€.

ћетоды построени€ деревьев решений

ƒеревь€ решений - это способ представлени€ классификационных правил в иерархической, последовательной структуре.
ќбычно каждый узел включает проверку одной независимой переменной. »ногда в узле дерева две независимые переменные сравниваютс€ друг с другом или определ€етс€ некотора€ функци€ от одной или нескольких переменных.
≈сли переменна€, котора€ провер€етс€ в узле, принимает категориальные значени€, то каждому возможному значению соответствует ветвь, выход€ща€ из узла дерева. ≈сли значением переменной €вл€етс€ число, то провер€етс€ больше или меньше это значение некоторой константы. »ногда область числовых значений разбивают на интервалы. (ѕроверка попадани€ значени€ в один из интервалов).

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

ћетодика "–аздел€й и властвуй"

ћетодика основана на рекурсивном разбиении множества объектов из обучающей выборки на подмножества, содержащие объекты, относ€щиес€ к одинаковым классам.
—перва выбираетс€ независима€ переменна€, котора€ помещаетс€ в корень дерева.
»з вершины стро€тс€ ветви, соответствующие всем возможным значени€м выбранной независимой переменной.
ћножество объектов из обучающей выборки разбиваетс€ на несколько подмножеств в соответствии со значением выбранной независимой переменной.
“аким образом, в каждом подмножестве будут находитьс€ объекты, у которых значение выбранной независимой переменной будет одно и то же.
ќтносительно обучающей выборки T и множества классов C возможны три ситуации:

  1. множество “ содержит один или более объектов, относ€щихс€ к одному классу cr. “огда дерево решений дл€ T - это лист, определ€ющий класс cr;
  2. множество “ не содержит ни одного объекта (пустое множество). “огда это снова лист, и класс, ассоциированный с листом, выбираетс€ из другого множества, отличного от “, например из множества, ассоциированного с родителем;
  3. ћножество “ содержит объекты, относ€щиес€ к разным классам. ¬ этом случае следует разбить множество “ на некоторые подмножества. ƒл€ этого выбираетс€ одна из независимых переменных xh, имеюща€ два и более отличных друг от друга значений c_h^1, c_h^2 ..., c_h^n; ћножество “ разбиваетс€ на подмножества T1,T2,...,Tn, где каждое подмножество Ti содержит все объекты, у которых значение выбранной зависимой переменной равно c_h^i. ƒалее процесс продолжаетс€ рекурсивно дл€ каждого подмножества до тех пор, пока значение зависимой переменной во вновь образованном подмножестве не будет одинаковым (когда объекты принадлежат одному классу). ¬ этом случае процесс дл€ данной ветви дерева прекращаетс€.

ѕри использовании данной методики построение дерева решений будет происходить сверху вниз. Ѕольшинство алгоритмов, которые еЄ используют, €вл€ютс€ "жадными алгоритмами". Ёто значит, что если один раз переменна€ была выбрана и по ней было произведено разбиение, то алгоритм не может вернутьс€ назад и выбрать другую переменную, котора€ дала бы лучшее разбиение.
¬опрос в том, какую зависимую переменную выбрать дл€ начального разбиени€. ќт этого целиком зависит качество получившегос€ дерева.
ќбщее правило дл€ выбора переменной дл€ разбиени€: выбранна€ переменна€ должны разбить множество так, чтобы получаемые в итоге подмножества состо€ли из объектов, принадлежащих к одному классу, или были максимально приближены к этому, т.е. чтобы количество объектов из других классов ("примесей") в каждом из этих множеств было минимальным.
ƒругой проблемой при построении дерева €вл€етс€ проблема остановки его разбиени€. ћетоды еЄ решени€:

  1. –анн€€ остановка. »спользование статистических методов дл€ оценки целесообразности дальнейшего разбиени€. Ёкономит врем€ обучени€ модели, но строит менее точные классификационные модели.
  2. ќграничение глубины дерева. Ќужно остановить дальнейшее построение, если разбиение ведЄт к дереву с глубиной, превышающей заданное значение.
  3. –азбиение должно быть нетривиальным, т.е. получившиес€ в результате узлы должны содержать не менее заданного количества объектов.
  4. ќтсечение ветвей (снизу вверх). ѕостроить дерево, отсечь или заменить поддеревом те ветви, которые не приведут к возрастанию ошибки. ѕод ошибкой понимаетс€ количество неправильно классифицированных объектов, а точностью дерева решений отношение правильно классифицированных объектов при обучении к общему количеству объектов из обучающего множества.

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

јлгоритм ID3

–ассмотрим критерий выбора независимой переменной, от которой будет строитьс€ дерево.
ѕолный набор вариантов разбиени€ |X| - количество независимых переменных.
–ассмотрим проверку переменой xh, котора€ принимает m значений ch1,ch2,...,chm.
“огда разбиение множества всех объектов обучающей выборки N по проверке переменной xh даст подмножества T1,T2,...,Tm.

ћы ожидаем, что при разбиении исходного множества, будем получать подмножества с меньшим числом объектом, но более упор€доченные.
“ак, чтобы в каждом из них были по-возможности объекты одного класса.
Ёта мера упор€доченности (неопределенности) характеризуетс€ информацией.
¬ контексте рассматриваемой задачи это количество информации, необходимое дл€ того, чтобы отнести объект к тому или иному классу.
ѕри разделении исходного множества на более мелкие подмножества, использу€ в качестве критери€ дл€ разделени€ значени€ выбранной независимой переменной,
неопределЄнность принадлежности объектов конкретным классам будет уменьшатьс€. «адача состоит в том, чтобы выбрать такие независимые переменные,
чтобы максимально уменьшить эту неопределенность и в конечном итоге получить подмножества, содержащие объекты только одного класса.
¬ последнем случае неопределенность равна нулю.

≈динственна€ доступна€ информаци€ - каким образом классы распределены в множестве T и его подмножествах, получаемых при разбиении.
»менно она и используетс€ при выборе переменной.
–ассмотрим пример, в котором требуетс€ построить дерево решений относительно того, состоитс€ ли игра при заданных погодных услови€х.
»сход€ из прошлых наблюдений (накопленных исторических данных), возможны четыре варианта разбиени€ дерева.
¬арианты первоначального разбиени€.
ѕусть freq(cr,I) - число объектов из обучающей выборки, относ€щихс€ к классу cr.
“огда веро€тность того, что случайно выбранный объект из обучающего множества I будет принадлежать классу cr равн€етс€:
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|}).
ѕоскольку используетс€ логарифм с двоичным основанием, то это выражение даЄт количественную оценку в битах.
ƒл€ оценки количества информации справедливы следующие утверждени€:

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

ѕосчитаем значение информационной энтропии дл€ исходного множества до разбиени€.
Info(I) = -\frac{9}{14}*log_2(\frac{9}{14}) - \frac{5}{14}*log_2(\frac{5}{14}) = 0.94 бит.
“у же оценку, но уже после разбиени€ множества “ по xh даЄт следующее выражение: 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.
Ќеобходимо выбрать такую переменную, чтобы при разбиении по ней один из классов имел наибольшую веро€тность по€влени€. Ёто возможно в том случае, когда энтропи€ Infox имеет минимальное значение и, соответственно, критерий 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 - число объектов в обучающей выборке и одновременно количество значений переменных, тогда числитель максимально будет равен log2k, а знаменатель максимально равен log2n. ≈сли предположить, что количество объектов знаведомо больше количества классов, то знаменатель растЄт быстрее, чем числитель и, соответственно, значение выражени€ будет небольшим.
¬ обучающей выборке могут присутствовать объекты с пропущенными значени€ми атрибутов. ¬ этом случае их либо отбрасывают (что влечЄт за собой риск потер€ть часть данных), либо применить подход, предполагающий, что пропущенные значени€ по переменной веро€тностно распределены пропорционально частоте по€влени€ существующих значений.

јлгоритм покрыти€

јлгоритм заключаетс€ в построении деревьев решений дл€ каждого класса по отдельности. Ќа каждом этапе генерируетс€ проверка узла дерева, который покрывает несколько объектов обучающей выборки.
Ќа каждом шаге алгоритма выбираетс€ значение переменной, которое раздел€ет множество на два подмножества. –азделение должно выполн€тьс€ так, чтобы все объекты класса, дл€ которого строитс€ дерево, принадлежали одному подмножеству. “акое разбиение производитс€ до тех пор, пока не будет построено подмножество, содержащее только объекты одного класса.
ƒл€ выбора независимой переменной и еЄ значени€, которое раздел€ет множество, выполн€ютс€ следующие действи€:

  1. »з построенного на предыдущем этапе подмножества (дл€ первого этапа это вс€ обучающа€ выборка), включающего объекты, относ€щиес€ к выбранному классу дл€ каждой независимой переменной, выбираютс€ все значени€, встречающиес€ в этом подмножестве.
  2. ƒл€ каждого значени€ каждой переменной подсчитываетс€ количество объектов, удовлетвор€ющих этому условию и относ€щихс€ к выбранному классу.
  3. ¬ыбираютс€ услови€, покрывающие наибольшее количество объектов выбранного класса.
  4. ¬ыбранное условие €вл€етс€ условием разбиени€ подмножества на два новых.

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

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

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

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

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

к библиотеке   к оглавлению “ѕќ»   к дискретной математике   технологии программировани€
«наете ли ¬ы, что, когда некоторые исследователи, пытающиес€ примирить рел€тивизм и эфирную физику, говор€т, например, о том, что космос состоит на 70% из "физического вакуума", а на 30% - из вещества и пол€, то они впадают в фундаментальное логическое противоречие. Ёто противоречие заключаетс€ в следующем.

¬ещество и поле не есть что-то отдельное от эфира, также как и человеческое тело не есть что-то отдельное от атомов и молекул его составл€ющих. ќно и есть эти атомы и молекулы, собранные в определенном пор€дке. “акже и вещество не есть что-то отдельное от элементарных частиц, а оно состоит из них как базовой материи. “акже и элементарные частицы состо€т из частиц эфира как базовой материи нижнего уровн€. “аким образом, всЄ, что есть во вселенной - это есть эфир. Ёфира 100%. »з него состо€т элементарные частицы, а из них всЄ остальное. ѕодробнее читайте в FAQ по эфирной физике.

Ќќ¬ќ—“» ‘ќ–”ћј‘орум –ыцари теории эфира
–ыцари теории эфира
 15.01.2017 - 21:42: —ќ¬≈—“№ - Conscience -> –”—— »… ћ»– -  арим_’айдаров.
15.01.2017 - 09:02: —ќ¬≈—“№ - Conscience ->  ќЋЋјѕ— ћ»–ќ¬ќ… ‘»ЌјЌ—ќ¬ќ… —»—“≈ћџ -  арим_’айдаров.
14.01.2017 - 08:41: Ѕеседка - Chatter -> — Ќовым годом. -  арим_’айдаров.
13.01.2017 - 00:44: ј—“–ќ‘»«» ј - Astrophysics ->  омета 67–/„урюмова-√ерасименко и проблема ее происхождени€ - ≈вгений_ƒмитриев.
12.01.2017 - 16:12: —ќ¬≈—“№ - Conscience -> ѕроблема государственного терроризма -  арим_’айдаров.
12.01.2017 - 07:34: —ќ¬≈—“№ - Conscience -> ѕросвещение от академика —.ё. √лазьева -  арим_’айдаров.
11.01.2017 - 18:50: Ѕеседка - Chatter -> ‘”“”–ќЋќ√»я - прогнозы на будущее -  арим_’айдаров.
11.01.2017 - 09:58: ÷»“ј“џ „”∆»’ ‘ќ–”ћќ¬ - Outside Quotings -> «ј Ќјћ» ЅЋёƒя“ - гость ¬ладимир_‘едотьев.
11.01.2017 - 04:57: —ќ¬≈—“№ - Conscience -> ѕ–ќЅЋ≈ћј  –»ћ»ЌјЋ»«ј÷»» Ё ќЌќћ» » -  арим_’айдаров.
06.01.2017 - 10:23: —ќ¬≈—“№ - Conscience -> ѕросвещение от јндре€ ‘урсова -  арим_’айдаров.
10.12.2016 - 06:55: —ќ¬≈—“№ - Conscience -> »нфоварщина от —ерге€ Ѕыковского -  арим_’айдаров.
07.12.2016 - 06:43: —ќ¬≈—“№ - Conscience -> ѕросвещение от ¬.¬. ѕ€кина -  арим_’айдаров.
Bourabai Research Institution home page

Bourabai Research - “ехнологии XXI века Bourabai Research Institution