Internet Портал МЭИ(ТУ)
Июль 2019
Пн Вт Ср Чт Пт Сб Вс
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 2324 25 26 27 28
29 30 31

Методы классификации

Одними из первых в теории классификации были разработаны центроидные методы, в которых по выборке для каждого класса g (g=1,…,G) вычисляется центроид  – вектор со средними значениями весов терминов документов данного класса :

,                                                                      

где Ng – количество документов, принадлежащих классу Qg. Для классификации нового документа  определяется расстояние, например евклидово, между ним и центроидами всех классов, относится к классу с наиболее близким центроидом.

 

Наивном байесовский метод (НБМ) (Naive BayesMethod) основан на анализе частоты совместных появлений терминов документа и метки класса. Метод называется наивным, т.к. в нем предполагается независимость всех терминов. В НБМ используется вероятностная модель определения класса документов, в которой оценка  для  рассчитывается по документам обучающей выборки:

,                                                                  

где Ng – число документов обучающей выборки, принадлежащих классу Qg.

Оценка  для , условной вероятности того, что в случае выбора класса документ содержит термин , также может быть рассчитана по документам обучающей выборки:

,                                                             

где Nig – частота встречаемости слова i в документах класса Qg в обучающей выборке,  – общее количество терминов в документах класса Qg.

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

,                                                     

где М– общее количество терминов во всех документах выборки.

Апостореорная вероятность того, что при классификации документа  будет выбран класс  вычисляется по формуле:.                                             

Согласно вероятностной модели документ принадлежит к тому классу, для которого величина  максимальна.

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

 

В методе ближайшего соседа (МБС) новый документ  относится к тому классу, к которому принадлежит его ближайший сосед. Элемент выборки является ближайшим соседом для, если расстояние между ними наименьшее:

 , для "j=1…N.                       

В методе кближайших соседей (метод кБС) аналогично МБС для классификации нового наблюдения  проводится упорядочивание исходных элементов выборки по какой-либо метрике (например, евклидову расстоянию). При этом определяется не один ближайший сосед, а группа соседей, наиболее близких к новому наблюдению. Число соседей к является настраиваемым на стадии обучения (или задаваемым экспертно) параметром метода. Решение об отнесении  к классу Qg  принимается путем голосования его к–ближайших соседей с помощью простого подсчета голосов. Если более половины кБС принадлежат классу , то  также относится к этому классу (g=1,…,G, где G – количество классов).

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

 

Во взвешенном методекближайших соседей (ВКБС) те соседи, которые являются наиболее близкими к новому наблюдению имеют больший вес при голосовании. Если – новое наблюдение, которое имеет к–ближайших соседей ( j=1,…,к), пронумерованных от самого близкого до самого дальнего в соответствии с евклидовым расстоянием dj, то вес каждого соседа может быть рассчитан по формуле:

                                                         

Такая весовая функция изменяется от максимума равного единице, который соответствует ближайшему соседу, до минимума равного нулю, который соответствует наиболее отдаленному кому соседу (см. рис. 2.3–б). Новое наблюдение  относится к тому классу, который набирает наибольший вес при голосовании кБС.

 

Метод потенциальных функций (МПФ) был предложен М.А. Айзерманом, Э.М. Браверманом и Л.И. Розоноэром, в зарубежных публикациях этот подход развивался самостоятельно и потенциальные функции получили название “ядерных” функций (kernelfunction”) или “функций окна” (windowfunction”). В МПФ для классификации  определяются  “относительные потенциалы” (аналогично тому, как это делается в электротехнике), которые наводятся в новой точке признакового пространства объектами, уже распределенными по классам, и  относится к  классу, чей наведенный совокупный потенциал выше.

            Относительный потенциал в , который создается объектами g–го класса, рассчитывается по формуле:        .                     

Здесь j(d) – некоторая известная положительная функция от метрики расстояния d, стремящаяся к 0, при d®¥. Обычно  или   (здесь коэффициенты a >0 иb >0).

Таким образом, согласно методу потенциальных функций новый объект  относится к тому классу, который имеет наибольший относительный потенциал: если   Fg> > Fq, то новый объект относится к g-му классу (g,q=1,...,G; g≠q).

 

Вход для преподавателей



Мы находимся:
МЭИ, корпус М, 3-й этаж.
Телефон: (+7 495) 362-74-07
Кафедра управления и информатики МЭИ
Сайт создан и поддерживается лабораторией интеллектуальных информационных систем (ЛИИС) УиИ