Авт. обработка текстов на естественном языке и комп. лингвистика. Большакова (2014) (1185448), страница 53
Текст из файла (страница 53)
– априорная вероятность, что документ принадлежит ;`+ | . – вероятность встретить документ типа среди документов, класса .Поскольку `X Z не влияет на выбор класса, итоговое ранжирование классов поаприорной вероятности можно провести без учёта знаменателя в формуле (11).Наивным данный алгоритм называют потому, что он использует наивноедопущение, что слова, входящие в текст документа, не зависят друг от друга.`+ | .175Следовательно, `+ | . можно вычислить как произведение вероятностей встретитьтермин () документах класса :|'„ |(12)1`+ | .ƒ `+() | .,)E,где ':1 – множество терминов документа ; `+() | . – оценка термина () вкладав то, что ∈ .Тогда решающее правило (10) принимает окончательный вид:|'„ |(13)1∗arg l2∈ max `+ .
ƒ `+() | .,)E,На практике может наблюдаться потеря значащих разрядов при умножении |':1 |условных вероятностей. Тогда в выражении (13) вместо самих оценок вероятностейиспользуют логарифм этих вероятностей. Поскольку логарифм – монотонновозрастающая функция, то класс с наибольшим значением логарифма вероятностиостанется наиболее вероятным. Тогда|'„ |(14)1∗arg l2∈ max …log `+ .
f A log `+() | .†,)E,Оценки вероятностей на обучающем множестве:(15)‡ l2 ‡`+ .,| |(6+() , .`+() | .,∑|m|.(6+(,E,где l2 – множество документов в классе ;– количество всех документов(ˆ);(6+() , . – количество вхождений термина () в документе класса ;m – словарь всей коллекции документов.Поскольку обучающее множество не может быть достаточно большим, чтобысодержать все термины, которые могут встретиться в новых документах, тогда еслиновый документ, содержит новый (редкий) термин, то вероятность принадлежностисвоему классу будет равна нулю (следует из (15) и (12)).
Для решения этой проблемына практике применяют сглаживание, например, следующего вида:(16)(6+() , . f 1(6+() , . f 1`+() | .,∑|m|∑|m|| |E,+(6+( , . f 1.E, (6+( , . f mДобавление единицы к каждой частоте встречаемости термина можноинтерпретировать как априорное равномерное распределение (каждый терминвстречается в каждом классе по одному разу), которое затем на обучающеммножестве уточняется.Алгоритм в общем виде.Обучение.Вход: иΩ.Шаг 1. Составить словарь m из .176∈ :Шаг 2. Для каждогоШаг 3.prior[ j ] := ‡ l2 ‡ /| |;Шаг 4.text[ j ] := <склеить тексты всех документов ∈ : ∈ с >;Шаг 5.Для каждого () ∈ m:Шаг 6.tf[ k ][ j ] := <вычислить количество вхождений термина () вtext[ j ]>;Шаг 7.Для каждого () ∈ m:|m|Шаг 8.cp[ k ][ j ] := X(6Š * ‹Š ‹ f 1Z⁄+∑ E, (6Š ‹Š ‹ f |m|.;Выход: m, prior, cp.Тестирование (применение).Вход: ; m; prior; cp; ∈ .Шаг 1.
terms := <извлечь термины из d с учётом m и дополнениями cp>;Шаг 2. Для каждого ∈ :Шаг 3.score[ j ] := log prior[ j ];Шаг 4.Для каждого () ∈ (ŽGM?:Шаг 5.score[ j ] := score[ j ] + log cp[ k ][ j ];Шаг 6. c* := arg max score[ j ];Выход: c*.Пример. Определим класс документа d5 для коллекции документов, заданной вразделе 1.Обучение:s,1) `X Z; `X Z;t2) `Xкитайский| Z3) `Xкитайский| ZПрименение:t‘u,s’u“”; `Xтокио| Z`Xтокио| Z34`Xяпония| Z`Xяпония| Z3 s 1˜ š`X ‘ | Z714s122˜ š`X ‘ | Z499∗Следовательно, сс, то есть «Китай».,u,su“1w 0,0003;142w 0,0001.9V–.vu,’u“,,t;Вычислительная сложность.Обучение: линейная сложность относительно размера коллекции документовœX|•|Z.Тестирование: линейная сложность относительно числа категорий œX|ž|Z.§ 1.4.Алгоритм РоккиоАлгоритм Роккио рассматривает документы в векторном пространстве терминови ищет границы между классами как множества точек, равноудалённых отцентроидов этих классов.
Центроидом класса называется усреднённый вектор, илицентр масс членов класса:177Ÿ$l2|1l2 |A ###$% ,: :1 ∈l2(17)где l2 – множество документов в классе .Граница между двумя классами в многомерном пространстве терминов имеетвид гиперплоскости:(18)5##$ / ¤$ ¥,5##$ Ÿ$, C Ÿ$V ,1X‖Ÿ$, ‖V C ‖Ÿ$V ‖V Z,¥2где 5##$ – вектор нормали; b – константа.Правило классификации заключается вопределении области, в которую попадаетновый документ, то есть в поиске центроида,к которому образ нового документа ближе,чем к остальным центроидам.
На рис. 1 кдокументу «звёздочка» ближе всех центроидкласса «кружков».Алгоритм Роккио предполагает, что классыимеют форму сфер с примерно одинаковымирадиусами. Если это предположение неРис. 1. Иллюстрация работывыполняется, то алгоритм может привести калгоритма Роккионеудовлетворительнымрезультатам.Например, на рис.
1 документ «квадрат»больше подходит классу «крестиков», аалгоритмотнесётегокклассу«треугольников».Алгоритм в общем виде.Обучение.Вход: иΩ.Шаг 1. Для каждого ∈ :,∑ : :1 ∈l2 ###$% ;Шаг 2.Ÿ$Выход: Ÿ$, , … , Ÿ$|||2|.Тестирование (применение).Вход: Ÿ$, , … , Ÿ$| | ; ∈ ./Шаг 1. $ := + , , … , |'| . по формуле (1);Шаг 2. c* := arg min£Ÿ$ C $£;Выход: c* .178Пример. Рассчитаем веса терминов для нашей коллекции из 5 документов: 4документа – обучающее множество Ω, и 1 документ из тестового множества.t1t2t3t4t5t6китайский пекиншанхаймакаояпониятокиоdf на Ω411111tf=2 | w=0| 01 | 0,6 | 1d100002|0|01 | 0,6 | 1d200001|0|01 | 0,6 | 1d300001 | 0,6 | 0,71 | 0,6 | 0,71|0|0000d43 | 0 |01 | 0,6 | 0,71 | 0,6 | 0,7d5000Обучение. Вычислим центроиды классов с и с:t1t2t3t4t5t6китайский пекин шанхай макао япония токио00,330,330,3300Ÿс00000,70,7ŸсТестирование.¦0 f 0,33V f 0,33V f 0,33V f 0,7V f 0,7V w 1,14,£####$‘ C Ÿ####$£l£####$‘ C Ÿ####$£√0 f 0 f 0 f 0 f 0 f 0 0,00.lСледовательно, с* = с, то есть «не Китай».Разделяющая гиперплоскость имеет следующий вид:5##$ w X0; 0,33; 0,33; 0,33; C0,7; C0,7Z/ ;1X0,33 C 0,98Z w C0,33¥w2Документы класса c и с лежат по разные стороны от гиперплоскости:5##$ / ####$, 5##$ / ####$V 5##$ / ####$s w 0,33 I ¥;##$ / ####$‘ w C0,98 © ¥.5##$ / ####$t 5Вычислительная сложность.Обучение: линейная сложность относительно размера коллекции документовœX|•|Z.Тестирование: линейная сложность относительно числа категорий œX|ž|Z.§ 1.5.Алгоритм k-ближайших соседейАлгоритм k-ближайших соседей использует гипотезу компактности векторногопространства, которая заключается в том, что документы одного класса образуют впространстве терминов компактную область, причём области разных классов непересекаются.
Тогда можно ожидать, что тестовый документ будет иметь такую жеметку класса, как и окружающие его документы из обучающего множества. Алгоритмk-ближайшего соседа относит тестовый документ к преобладающему классу его kсоседей. При k = 1 алгоритм относит документ к классу, самого ближайшего емудокумента.179Данный алгоритм лучше справляется снесферическимиилинесвязнымиклассами,чемалгоритмРоккио,поскольку определяет границы междуклассамилокально.Длявсехдокументов обучающего множествапространство терминов представляетсяразделенным на ячейки (выпуклыемногогранники), состоящие из точек,которые ближе к данному объекту, чем кРис. 2.
Иллюстрация работы алгоритма другим. Это в случае k = 1. В случае k >k-ближайших соседей при k = 11 внутри ячеек также множество kближайшихсоседейостаётсяинвариантным.На рис. 2 видно, что новый документ «звёздочка» попадает в ячейку объектакласса «треугольников», и при k = 1 будет отнесён к этому же классу. Однако при k =3 «звёздочка» будет отнесён к классу «кружочков».При k = 1 алгоритм неустойчив, так как классификация зависит всего от одногообучающего документа, а он может быть нетипичным или иметь неверную меткукласса.
На практике значение k выбирают на основе опыта эксперта и имеющихсязнаний о решаемой задаче. Кроме того, число соседей можно подобрать наобучающем множестве так, чтобы максимизировать качество классификации.На практике для повышения точности выбора класса могут учитываться веса«голосов» соседей, которые используются для ранжирования классов:(19)W###$$ранг+ , .
= A bl2 X Z? M Q ′, S,где bl2 X W Z 1, если W ∈ , иначе bl2 X W Z 0;? M Q###$′, $S – косинусная мера близости (см. (3)).Документ приписывается классу с наибольшим рангом. Так, например, еслиодинаковое число соседей принадлежит двум разным классам, то выбирается класс сболее близкими соседями.Алгоритм в общем виде.Обучение.Вход: иΩ.Шаг 1. k := <подходящее значение числа соседей>;Выход: k .:W∈¯kТестирование (применение).Вход: ; Ω;; ∈ , k.Шаг 1.
«) := <множество k ближайших соседей для d>;Шаг 2. Для каждого ∈ :Шаг 3.}Š ‹ ≔ ‡«) ∩∈ }Шаг 4. c* := arg max }Š ‹;Выход: c* .l2 ‡⁄* ;{где }Š ‹ – оценка вероятности того, что180Пример. Пусть k = 1. Тогда£ $‘ C $, £ £ $‘ C $V £ £ $‘ C $s £ w 1,92;£ $‘ C $t £ 0,00.Следовательно, с* = с, то есть «не Китай».Вычислительная сложность.Обучение: сложность œX1Z в случае, если не используются никакиедополнительные техники подбора значения k.Тестирование: линейная сложность относительно числа документов œX|ˆ|Z.§ 1.6.Алгоритм опорных векторовАлгоритм опорных векторов (SVM, Support Vector Machines), разработанный В.Н.
Вапником в 1990-е годы, ищет в векторном пространстве документовразделяющую поверхность между двумя классами, максимально удалённую от всехточек обучающего множества. Расстояние между найденной поверхностью иближайшей точкой данных называется зазором классификации. В алгоритме опорныхвектороврешающаяповерхностьполностьюопределяетсянебольшимподмножеством документов. Элементы данного подмножества называются опорнымивекторами.Итак, пусть алгоритм ищет разделяющую поверхность заданную уравнением:(20)5##$ / ¤$ C¥,где 5##$ – вектор нормали к разделяющей поверхности, или вектор весов; b – параметрсдвига.X¤$ , ° Z , где ¤$ –Обучающее множество представляет собой множество пар Ωэто документы обучающего множества, а ° – это соответствующая метка класса,причём в алгоритме опорных векторов метка принимает одно из двух значений +1и -1.Тогда линейный классификатор описывается следующей формулой:(21)6 X¤$Z ? 9± X5##$ / ¤$ f ¥Z,где значение классификатора -1 соответствует одному классу, а +1 – другому; ¤$ –тестовый документ.181Рис.
3. Опорные вектора и разделяющая поверхностьРазделяющая поверхность ищется таким образом, чтобы максимизировать зазорклассификации. Геометрически зазор – это максимальная ширина полосы, которуюможно провести между опорными векторами двух классов, то есть значение, вдвоепревышающее минимальное значение r (рис. 3). Значение r вычисляется так: пусть ¤$′– документ, лежащий на разделяющей гиперплоскости и ближайший к точке ¤$;перпендикуляр из ¤$′ в ¤$ параллелен вектору 5##$; единичный вектор в этом направленииимеет вид 5##$⁄‖5##$‖; тогда ##############################$¤$ W ¤$ C °GX5 ²‖5##$‖Z, где умножение на y просто меняетзнак. Точка ¤$′ лежит на поверхности, следовательно:(22)5##$´ f ¥ 0,5##$ / ³¤$ C °G‖5##$ ‖(23)5##$ / ¤$ f ¥G °.‖5##$‖Потребуем, чтобы для всеx точек X¤$ , ° Z ∈ µ выполнялось следующеенеравенство:(24)° X5##$ / ¤$ f ¥Z ¶ 1.На опорных векторах неравенство (24) превращается в равенство.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
