Большакова Е.И. и др. - Автоматическая обработка текстов на естественном языке и компьютерная лингвистика (1027379), страница 53
Текст из файла (страница 53)
Например, имеемдокумент с текстом «Китай лидирует по темпам роста ВВП среди развитых стран»,тогда образом документа является {китай, лидировать, темп, рост, ввп, развитый,страна}.Целью классификации является поиск наилучшего класса для документа, то естьимеющего наибольшую апостериорную вероятность `+ | .:∗(10)arg l2∈ max `+ | .,где ∈ ‚, ∈ .По формуле Байеса:(11)`+ .`+ | .w `+ .`+ | .,`X Zгде `+ . – априорная вероятность, что документ принадлежит ;`+ | . – вероятность встретить документ типа среди документов, класса .Поскольку `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) превращается в равенство.
Из (24) и (23)Vследует, что геометрический зазор равен · ‖0.##$‖Таким образом, задача алгоритма опорных векторов заключается в поискепараметров 5##$ и b, удовлетворяющих следующим условия:а) величина5##$ / 5##$ достигает минимума;VVб) при всех X¤$ , ° Z ∈ Ω выполняется неравенство (24).Имеем задачу минимизации квадратичной функции при линейныхограничениях. Для решения задачи квадратичной оптимизации разработаномножество алгоритмов, рассмотрение, которых выходит за рамки наших лекций.Однако для понимания алгоритма опорных векторов необходимо привестиследующую информацию о её решении.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
