Большакова Е.И. и др. - Автоматическая обработка текстов на естественном языке и компьютерная лингвистика (1027379), страница 54
Текст из файла (страница 54)
Для решения данной задачи формулируютдвойственную задачу, в которой с каждым ограничением вида (24) прямой задачисвязан соответствующий множитель Лагранжа ¸ , и задача заключается в поиске‖0##$‖,182значений ¸, , … , ¸|¹| при которых величина ∑ ¸ C ∑ ∑ ¸ ¸ ° ° ¤$ ¤$ достигаетмаксимума, ∑ ¸ °0, ¸ ¶ 0 для всех 1 = = |Ω|.Решение задачи имеет следующий вид:¥,V/|Ω|A ¸ ° ¤$ ,5##$(25)E,°) C 5##$ / ¤$) , для ∀¤$) , таких что ¸) » 0,6X¤$ Z|Ω|? 9± XA ¸ ° ¤$ ¤$ f ¥Z,/E,(26)Большинство параметров ¸ равны нулю, ненулевое значение означает, чтосоответствующий вектор ¤$ является опорным.Пример.Обучение. С помощью статистического программного пакета получим значенияпараметров ¸, , … , ¸|¹| :¸, w 0,31; ¸V w 0,23; ¸s w 0,23; ¸t w 0,78.
Все обучающие документы сталиопорными.C1; °VC1; °s C1; °t1.°,Из (25):5##$0,31XC1Z¥01¾ 0Á½0À f 0,230¼ 0¿Å1 ¾ÄXC1Z C X04 ½ÄļÃXC1ZC0,3100¾ 1Á½0À f 0,230¼ 0¿C0,2300¾ ÁXC1Z ½0À f 0,78 Xf1Z10¼ 0¿01 Ⱦ 0Á ÇC0,23 0,55 0,55Z ½ ÀÇ00 Ǽ 0¿ Æ00¾0Á½0À0,7¼0,7¿00 Ⱦ 1Á ÇC0,31 C0,23 C0,23 0,55 0,55Z ½ ÀÇ00 Ǽ 0¿ Æ0Å0 Ⱦ 0Á ÇÄf ÄXC1Z C X0 C0,31 C0,23 C0,23 0,55 0,55Z ½ ÀÇ1Ä0 Çü 0¿ Æ0Å0 Èľ 0 ÁÇ Áf ÄX1Z C X0 C0,31 C0,23 C0,23 0,55 0,55Z ½ ÀÇÀ0 ÇÄ0,7 ÇÄü0,7¿Æ¿1XC0,69 C 0,77 C 0,77 f 0,23Z C0,5.4ÅÄf ÄXC1Z C X0ÄÃТестирование. Из (26):1830C0,31¾C0,23Á.½½C0,23ÀÀ0,55¼ 0,55 ¿6+####$‘ .¾X0? 9± ½½C0,31C0,23C0,23¼Следовательно, с∗ с, то есть «не Китай».Вычислительная сложность.Обучение: œX|ž||•|V Z.Тестирование: œX|ž|Z.§ 1.7.0,550,55Z0Á¾ 00 ÁC0,5À½0ÀÀ0,7¼0,7¿¿1.Алгоритм деревьев принятия решенийАлгоритм деревьев принятия решений наглядно демонстрируют человекупроцесс и результат классификации.
На основе обучающего множества строитсядерево, узлами которого являются термины документов, листьями – метки классов, аребра помечены весами терминов.На рис. 4 представлен пример деревапринятиярешений,вкоторомиспользуются бинарные веса терминов.Тестовый документ прогоняется по дереву,выбираютсяветви,соответствующиетерминамдокумента.Врезультатедокументуприсваиваетсякласс,соответствующий достигнутому листу.Приобучениииспользуютследующую стратегию: рассматриваютмножество документов, проверяют, все лиРис. 4.
Пример дерева принятиядокументы данного множества имеютрешений с бинарными весамиодинаковую метку класса (категорию);терминовесли нет, то ищут термин, обладающийнаибольшей различительной способностьюдля разделения этих документов на классы; получают два подмножества документови строят их поддеревья, повторяя всё сначала, пока не получат подмножестводокументов одного класса, тогда добавляют в соответствующее поддерево лист сметкой этого класса.Для выбора очередного разделяющего термина используется понятиеинформационной энтропии – меры неопределенности. Предположим, имееммножество A из n элементов, обладающих атрибутом Q, который может приниматьодно из m значений. Тогда мера неопределенности множества A по отношению катрибуту Q вычисляется следующим образом:Ì(27)MMXZÊ e, ËCAlog V ,±±E,где M – число случаев, когда реализуется i-ое значение.Иначе выражение (27) можно записать так:Ê Xe, ËZÊ X}, , … , }Ì ZÌCA}E,184log V } .(28)Максимальное значение энтропия достигает, когда m значений атрибута Qравновероятны, Ê Xe, ËZ log V M.
Если значения атрибута Q не равновероятны, тоэнтропия понижается, а информационная выгода от описания элементов множества Ас помощью атрибута Q возрастает.Теперь представим, что имеем множество A из n элементов, характеризующихсясвойством S и обладающих атрибутом Q, который может принимать одно из mзначений. Тогда информационная выгода (прирост информации) от классификации(по свойству S) посредством атрибута Q имеет следующее значение:Ì(29)|e |bXe, ËZ Ê Xe, «Z C AÊ Xe , « Z,|e|E,где e – множество элементов A, на которых атрибут Q имеет i-ое значение.Применительно к задаче классификации коллекции документов по двум классамисходная энтропия вычисляется следующим образом:(30)Ê Xe, «Z Ê X", Z C}X Z log }X Z C }X Z log }X Z,VВыражение (29) принимает вид:b Xe, ËZ Ê X", Z C Q}X() Z Ê X() , Z f }+() .VÊ+() , .SÊ X", Z C +}X() Z ŠC}X() | Z log V }X() | Z C }X() | Z log V }X() | Z‹ f }+() .ÍC}+() | .
log V }+() | . C }+() | . log V }+() | .Î.,(31)Текущим разделяющим атрибутом становится тот, при котором приростинформации наибольший (а энтропия наименьшая).Алгоритм в общем виде.Обучение.Вход: иΩ.Шаг 1. Дерево <G,E>, где G := Ø; E := Ø;{G – множество вершин, E –множество рёбер}Шаг 2. G := G + {x};{создать «безымянную» вершину (корень дерева)}Шаг 3. Вызвать ПостроитьУровень( , x, G, E, m);Выход: Дерево <G,E>.ПостроитьУровень(A, x, G, E, T):Вход: A, x, G, E, T.Шаг 1. Если для ∀ » , ∈ e и ∈ e,∈ ) и ∈ r : * }, тоШаг 2.x := ) ;{если все документы имеют одинаковую меткукласса,то поместить её в вершину}Шаг 3.Выход;Шаг 4. ИначеШаг 5.для каждого () ∈ [Ñ :{[Ñ – множество терминов документов измножества A}Шаг 6.вычислить b X() Z по формуле (31);∗Шаг 7.() ∶ arg max b X() Z ;{поместитьразделяющийтерминвШаг 8.x := ()∗ ;«безымянную» вершину}Шаг 9.A1 := : ∈ e, ()∗ ∈;185Шаг 10.G := G + {y}; E := E + <x=()∗ , y, true>; {y–«безымянная» вершина}Шаг 11.Вызвать ПостроитьУровень(A1, y, G, E, T – {()∗ });Шаг 12.A2 :={ : ∈ e, ()∗ ∉ };Шаг 13.G := G + {z}; E := E + <x=()∗ , z, false>; {z–«безымянная» вершина}Шаг 14.Вызвать ПостроитьУровень(A2, z, G, E, T – {()∗ });Выход: Дерево <G,E>.Пример.Обучение.s,s,1) Исходная энтропия Ê X" •, Z C log V C log V w 0,81.2) b XкитайскийZ0,81 0.3) b XпекинZstVt0,81 C Ôtb XшанхайZV,,QC log V C log V SÕs4) b XтокиоZsssssbXяпонияZvvtsst,ttv,QC log V C log V S ftbXмакаоZt,tt,0,81 C Ô0,81 C 0,690,81 C ÔtvX… ZÕt,новая0,81 C,vvtQC log V C log V S fv,0,12.,,,,,,QC log V C log V S f,новая,,stQC log V C log V SÕ 0,81 C 0 0,81.ssssСледовательно, разделять будем по термину «токио».
Дальнейшего разделенияне требуется, так как все документы обоих выделенных подмножеств имеютодинаковые метки класса (внутри подмножеств). Полученное дерево принятиярешений представлено на рис.5.Рис.5. Дерево принятия решений для коллекции из пяти документовТестирование. Тестовый документ d5 содержит термин «токио».Следовательно, с∗ с, то есть «не Китай».Вычислительная сложность.Обучение: œX|Ω| log|Ω|Z.§ 1.8.Алгоритм наименьших квадратовАлгоритм наименьших квадратов (LLSF, Linear Least Squares Fit), относящийся котряду алгоритмов регрессионного анализа, ищет линейную функциональнуюзависимость между средним значением наблюдаемой случайной величины(зависимой) и другими наблюдаемыми случайными величинами (независимыми).Зависимой случайной величиной является класс документа, а независимымислучайными величинами – термины документов обучающего множества.Пусть A – матрица |Ω|x|m|, строки которой являются документами впространстве терминов; B – матрица |Ω|x| |, строки которой являются документами впространстве меток классов (категорий).
Тогда метод наименьших квадратов ищет186способ преобразования исходного пространства (терминов) в целевое пространство(классов). Для этого вычисляется матрица преобразования ^Ù¯ (| |x|m|) так, чтобыминимизировать регрессионные остатки, то есть разность между фактическимзначением зависимой величины и восстановленным:|Ω||Ω|(32)V//VV//#$‖^e C h ‖ÛD ,A‖Ž$ ‖A£^Ú$ C ¥ £^Ù¯ arg Ü min‖^e/ C h/ ‖VÛD ,где Ú$ и ¥#$ – i-ая пара в обучающем множестве; Ž$ – ошибка отображения Ú$посредством F;E,‖a‖ÛDU∑ E, ∑|Ω|E,|_|VE, aв ¥#$– фробениусова норма матрицы М (|C|x|Ω|).Матрица преобразования ^Ù¯ показывает степени ассоциации между терминамии классами; 6 ∈ H – это оценка (вес) связи термина и класса.
Метод наименьшихквадратов взвешивает ассоциации так, чтобы минимизировать ошибкипреобразования на всём обучающем множестве. Из анализа значений элементов этойматрицы можно получить информацию о важных/неважных терминах для всейколлекции документов. Более информативные термины имеют веса, «смещённые» кконкретным классам; менее информативные термины имеют относительноодинаковые веса ассоциаций для всех классов.Итоговая матрица преобразований вычисляется следующим образом:(33)^Ù¯ h/ Xeu Z/ ,uгде e – матрица, псевдообратная матрице А.Таким образом, классификационным правилом алгоритма является вычислениепроекции $ исходного образа тестового документа $ в целевое пространство классов:/(V34)$ +^Ù¯ $/ .
,Пример. Для нашей коллекции из 5 документов:0 1 0 0 0 0100 0 1 0 0 010Þ ; h Ý Þ.e Ý0 0 0 1 0 0100 0 0 0 0,7 0,701На обучающем множестве веса классов бинарные, для тестового документа –вещественные.Обучение. Из (33):0 1 1 1 0 0Õ^Ù¯ Ô0 0 0 0 0,72 0,72Тестирование./ /Š0 1‹.###$‘ Q^Ù¯ ####$‘ SСледовательно, с∗ с, то есть «не Китай».Вычислительная сложность.Обучение: вычислительная сложность алгоритма наименьших квадратов зависитот реализации вычисления псевдообратной матрицы и может быть кубическойœX|ˆ|s Z или квадратичной œX|ˆ|V Z.Тестирование: œX|ˆ| log |ˆ|Z.187§ 1.9.ЭкспериментальнаяучителемоценкарезультатаклассификациисКачество построенного классификатора оценивается по его ошибке на тестовомподмножестве обучающего множества документов.
Ошибка – это доля неправильныхрешений классификатора. Решения классификатора сравнивают с решениямиэкспертов, формирующих обучающее множество.Для вычисления ошибки и других классических мер качества в задачахинформационного поиска – полноты, точности и F1-меры – необходимо составитьследующую таблицу категорий принятых решений, для каждого∈ Ωßàáß , Ωßàáß ⊂ Ωи ⊂ :эксперт решилклассификатор решил∈∉∈ac∉bdТогда меры качества вычисляются следующим образом:Ú(35)`,Úf¥Ú(36)â,Úf¥f(37)Ê,Úf¥f fÚf(38)e, e 1 C Ê,Úf¥f fгде P – точность, то есть доля истинно принадлежащих классу документов извсех, что классификатор записал в данный класс;R – полнота, то есть доля истинно принадлежащих классу документов изаписанных в этот класс классификатором среди всех документов, которые истинноему принадлежат;E – ошибка классификатора;A – правильность (аккуратность) классификатора.Заметим, что правильность (ошибка) не пригодны для оценки результата, еслиесть небольшие классы, то есть классы, доля документов которых меньше 10%,поскольку в этом случае высокой правильности можно достичь, всегда отвечая «непринадлежит».
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
