Авт. обработка текстов на естественном языке и комп. лингвистика. Большакова (2014) (1185448), страница 52
Текст из файла (страница 52)
п. Вдобавок, каждой встреченной форме слова, например, вразных падежах и числах, будет соответствовать один и тот же термин, например,данное слово в начальной форме. В результате получаем множество всех терминовколлекции '() , * 1, |'|.Образом документа как вектора в пространстве терминов является вектор/действительных чисел ###$% + , , … , |'| . , где каждое действительное число являетсякоординатой вектора, соответствующей конкретному термину, и равняется весутермина в данном документе. Наиболее часто используют следующий подход квычислению веса термина:012|"|(1),5(6789,‖0####$‖4:;2где (6 – частота термина в документе, то есть количество раз, которое j-ыйтермин встретился в i-ом документе; 6 – документная частота, то есть количестводокументов, в которых встретился j-ый термин; ‖5####$% ‖ – евклидова норма 5####$.% Такиеназывают нормированными весами по формуле «TF-IDF» («частота терминавеса– обратная документная частота»), 0 == 1.
Они обладают следующимисвойствами: (а) имеют высокие значения, если термин часто встречается в небольшомчисле документов, тем самым усиливая отличие этих документов от других, (б)имеют низкие значения, если термин редко встречается в каком-то документе иливстречается во многих документов, тем самым снижая различие между документами.Процесс классификации документов как векторов основан на гипотезе о том, чтотематически близкие документы окажутся в пространстве терминов геометрическиблизко расположенными. Поэтому в основе алгоритмов классификации лежитпонятие сходства или расстояния между документами в пространстве терминов.Меры сходства и различий между образами документов.
В данном случаепонятия расстояния и сходства являются взаимнообратными, расстояние можно былобы называть различием. Выбор способа вычисления расстояния влияет на результатклассификации. Часто применяют следующие варианты:,(2)|'|D?(+ $ , $ .@AB)E,)CD)B F,где r – это параметр, заданный пользователем, G ∈ H, G I 0. Распространённыепримеры:а) при r = 1: манхэттенское расстояние, или расстояние городских кварталов;б) при r = 2: евклидово расстояние;в) при r → ∞ получим расстояние Чебышева, которое вычисляется какмаксимум модуля разности компонент этих векторов ?(+ $ , $ .max)E,,.,|'| B ) C ) B.Другой часто используемой на практике мерой сходства является косинуснаямера:171? M+ $ , $ .cos Q∠+ $ , $ .S∑|'|)E,U∑|'|)E,V)))U∑|'|)E,V).(3)Если вектора весов документов нормированы как в (1), то косинусная мера естьскалярное произведение векторов. Если векторы ортогональны, то мера близостиравна 0, если совпадают, то 1.Заметим, что в случае, когда вектора весов терминов нормированы, значенияевклидова расстояния и косинусной меры соответствуют друг другу.§ 1.2.Отбор терминов для классификацииБольшое количество терминов (признаков) документов в задаче классификацииприводит к ряду проблем, среди которых: (1) высокие вычислительные затраты,связанные, например, с получение значений меры близости между документами и др.,(2) низкое качество классификации, вызванное наличием большого числа признаковсо слабой классификационной способностью.
Такие признаки часто называютшумовыми, при их добавлении к представлению документа ошибка классификациина новых данных возрастает.В частности, (2) в классификации с учителем может привести к переобучениюклассификатора, то есть эффекту, возникающему, когда классификатор настраивалсяв большей степени на случайных (шумовых) характеристиках документов, а не насущественных для их тематик (категорий). В такой ситуации алгоритм хорошоработает на тех данных, на которых он был обучен, и значительно хуже на новых.Таким образом, стремятся сократить число термином из множества T так, чтобыновое (редуцированное) множество терминов ' W X|' W | ≪ |'|Z содержало наиболееинформативные в некотором смысле термины.Техники сокращения размерности пространства терминов (редукции)применяют двумя способами: локально (сокращают множество терминов для каждойкатегории в отдельности) и глобально (работают с общим множеством термином длявсех документов).
Первый случай применим для классификации с учителем, второй –как для классификации с учителем, так и без него. Мы рассмотрим такие техники,которые пригодны для обоих подходов – локального и глобального.Другое существенное различие между техниками редукции заключается вприроде итоговых терминов. Одни техники достигают сокращения числа терминовпутём отсева некоторого числа исходных терминов, руководствуясь заданнымкритерием отсева, - техники отбора признаков. Тогда ' W ⊂ '. Другие техникиформируют новые термины путём комбинации или преобразования исходныхтерминов, другими словами извлекают из итоговые признаки из исходных данных –техники извлечения признаков. Тогда элементы множества [ W имеют тип, отличный отэлементов множества T.
Отбор и извлечение терминов реализуются различнымитехниками. Мы рассмотрим только техники отбора признаков (терминов).Отбор признаков документов. Итак, необходимо отобрать такие термины,которые повысят качество классификатора. Для этого поместим в ' W все термины из' , которые имеют высокое значение «важности для разбиения покатегориям/классам». Для определения «важности» термина и способа её вычисленияиспользуют разные подходы.172Документная частота (DF).
Самая простая и вполне эффективная техникаоценки «важности терминов для классификации» основана на наблюдении того, чтозначительное число терминов коллекции встречаются в малом числе документов, анаибольшую информативность имеют термины со средней или даже высокойчастотой, если предварительно были удалены стоп-слова. На практике частоиспользуют пороговое значение \, равное 1-5 документам. Таким образом, '() ∈ ': ]^ X() Z I \ , где ]^ X() Z – это количество документов, в которых встречаетсятермин () .
Данная техника может применяться как единственная, так ипредшествовать другой технике отбора признаков.Следующие техники берут своё начало из теории информации: взаимнаяинформация, информационная выгода и критерий хи-квадрат. Мы рассмотрим ихлокальные значения 6X() , Z, чтобы получить значение глобально (вне зависимости|_|от конкретной категории), следует вычислить либо простую сумму ∑ E, 6X() , Z, либовзвешенную сумму ∑ E, `X Z6X() , Z, либо найти максимум max E,,|_| 6X() , Z.Взаимная информация (MI).
Величина взаимной информации термина t икатегории с:`X() , Z(4)ab+() , . log V.`X() Z `X ZПусть A – количество документов, принадлежащих категории c и содержащихтермин t;B – количество документов, не принадлежащих категории c и содержащихтермин t;C – количество документов, принадлежащих категории с и не содержащихтермин t.Тогда выражение (4) можно записать следующим образом:e |Ω|(5)ab+() , . log V,Xe f g Z Xe f hZгде Ω – обучающее множество документов.ab+() , . принимает значение 0, если термин t и категория c независимы.Недостаток взаимной информации заключается в том, что её значение сильноподвержено влиянию безусловной вероятности терминов, так как ab+() , .log V `X() | Z C log V `X() Z (это следует из (4)).
Если два термина имеют одинаковуюусловную вероятность, более высокое значение ab будет у более редкого.Следовательно, значения взаимной информации несравнимы для терминов ссущественно различающейся частотой встречаемости в документах.Информационная выгода (IG).Информационную выгоду часто называютожидаемой взаимной информацией (EMI). Этот показатель измеряет количествоинформации о принадлежности категории c, которое несёт наличие/отсутствиетермина t.(6)`X(, ZAA `X(, Z log Vbi+() , .,`X(Z `X Z|_|l∈ l2 ,l2 j∈ jk ,jkгде – все категории, кроме ; () , () – признаки наличия и отсутствия термина() соответственно.На практике формула (6) эквивалентна следующей:173bi+() , .e|Ω|log V|Ω| egfXe f hZ Xe f g Z |Ω|log V|Ω| gfXg f ] Z Xe f g Z(7)h|Ω| h]|Ω| ]log Vflog V,Xe f hZ Xh f ]Z |Ω|Xg f ] Z Xh f ]Z|Ω|где D – количество документов, не принадлежащих категории c и несодержащих термин t.Мера информационной выгоды достигает своего максимум, когда терминявляется идеальных индикатором категории, то есть присутствует в документе тогдаи только тогда, когда документ принадлежит классу.
Если распределение термина вкатегории соответствует распределению термина в коллекции, то информационнаявыгода равна 0.При заданном обучающем множестве для каждого термина вычисляют значениеIG и удаляют из m такие термины, значение информационной выгоды которых ниженекоторого заранее выбранного порогового значения.Критерий хи-квадрат (CHI). Критерий n V используется для проверкинезависимости двух случайных событий: появление термина X и появление класса Y.Если X и Y независимы, то P(XY)=P(X)P(Y).
Критерий n V вычисляется по формуле:V(8)+`X(, Z C `pqr X(, Z.AAgob+() , .,`pqr X(, Zl∈ l2 ,l2 j∈ jk ,jkгде `X(, Z – наблюдаемая на обучающем множестве, `pqr X(, Z – ожидаемая приусловии, что термин и класс являются независимыми. Величина критерия n Vпозволяет судить о том, насколько ожидаемая и наблюдаемая вероятностиотклоняются друг от друга, и принимает значение 0, если термин и категориянезависимы.
Критерий вычисляют локально (для каждой категории), затем получаютего глобальное значение, по которому ранжируют признаки коллекции документов.На практике формула (8) эквивалентна следующей:|Ω| Xe ] C g hZV(9)gob+() , .,Xe f g Z Xh f ] Z Xe f hZ Xg f ]ZВ отличие от взаимной информации критерий n V нормализован, что позволяетсравнивать между собой его значения для разных термов одной категории,исключением являются только редкие термы.Пример.s tMI(китайский, ) = log V XsuvZ0.Xsu,Z, tMI(китайский, ) = log V X,uvZ, tMI(пекин, ) = log V X,uVZX,uvZv tMI(пекин, ) = log V XvuVZIG(китайский,vtt vlog V XvuvZX,uvZ)0.=Xvu,Zst0.X,usZw 0,41.не опр.t slog V Xsu,ZXsuvZIG(китайский, ) = 0.174vt vf log V XvuvZtXsuvZ,t ,f log V Xsu,ZtX,uvZfIG(пекин, c) = log V X,uvZ,tt ,X,uVZt ,IG(пекин, ) = 0f log V X,uVZ,tf log V XVu,ZVtXvu,Zt VX,uVZt ,f log V Xvu,Z,tf 0 f log V XVu,ZX,uVZ,tVCHI(китайский, ) = X,uvZCHI(пекин, ) = X,uVZCHI(пекин, ) = Xvu,Zt Xs v~v ,Z•X,uvZ Xsu,Z XvuvZt X, v~v sZ•XsuvZ X,usZ XvuvZt X, ,~V vZ•Xvu,Z X,uvZ XVu,Zt Xv V~, ,Z•X,uVZ Xvu,Z X,uVZXvu,Zt Vf log V X,uVZtПринято читать, что при p = 0 выражение } log } равно нулю.CHI(китайский, ) = XsuvZt ,X,uVZ0,21.0,12.не опр.не опр.w 0,44.w 0,44.Видим, что по всем критериям термин «китайский» – шумовой для нашихкатегорий и обучающего множества.Извлечение признаков документов.
Необходимо синтезировать новые(искусственные) признаки документов так, чтобы повысить качество классификации,например, путём разрешения неоднозначностей естественного языка, например,синонимии, омонимии, полисемии. Затем следует отобразить документы коллекции вновое признаковое пространство, которое лишено старых проблем и лучше, чемисходное, представляет содержание документов. Примерами техник извлеченияпризнаков документов являются латентно-семантическое индексирование икластеризация терминов документов.Техники данной группы мы рассматривать не будем.§ 1.3.Алгоритм "наивной" байесовской классификацииАлгоритм наивной байесовской классификации использует формулу Байеса дляоценки вероятности принадлежности документа классу на обучающем множестве.Образ документа рассматривается как мультимножество терминов. Например, имеемдокумент с текстом «Китай лидирует по темпам роста ВВП среди развитых стран»,тогда образом документа является {китай, лидировать, темп, рост, ввп, развитый,страна}.Целью классификации является поиск наилучшего класса для документа, то естьимеющего наибольшую апостериорную вероятность `+ | .:∗(10)arg l2∈ max `+ | .,где ∈ ‚, ∈ .По формуле Байеса:(11)`+ .`+ | .w `+ .`+ | .,`X Zгде `+ .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
