Авт. обработка текстов на естественном языке и комп. лингвистика. Большакова (2014) (1185448), страница 55
Текст из файла (страница 55)
,Пример. Для нашей коллекции из 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%,поскольку в этом случае высокой правильности можно достичь, всегда отвечая «непринадлежит».
Например, если относительная частота класса коллекции составляет1%, то классификатор по принципу «всегда не принадлежит» даст правильность 99%.Надежнее использовать меры полноты и точности.Полнота и точность – меры, противоречащие друг другу в том смысле, что100%-ую полноту легко достичь, просто поместив все документы в класс (точностьбудет мала), и наоборот 100%-ую точность можно достичь, строго отбрасываядокументы, помещая в классмалое число документов (полнота будет мала).Показатель, позволяющий найти баланс между полнотой и точность называют ^ã мерой, которая вычисляется как взвешенное среднее гармоническое:XäV f 1Z`â V 1 C ¸(39)1^ã,ä,1̀1äV ` f ⸸ f X1 C ¸Zâгде ¸ ∈ Š0; 1‹, äV ∈ Š0; ∞‹, при ä I 1 предпочтение отдаётся полноте, при ä © 1– точности.188На практике чаще всего применяют сбалансированный вариант ^ã -меры – ^, меру, то есть ä 1, или ¸ 0,5:2`â(40)^,, ^, ∈ Š0; 1‹.`fâДля обобщения мер качества для всех Ωßàáß и применяют следующие подходык усреднению:а) макроусреднение – обобщение на уровне классов;б) микроусреднение – обобщение на уровне документов.Макроусреднение выполняется путём составления отдельных таблиц принятиярешений для каждого класса, вычисления мер по каждой таблице и затем обычногоусреднения значений мер по всем классам.
Микроусреднение выполняется путёмсоставления единой таблицы для всех классов, в которую сразу записываютсярешения по всем документам, затем по этой таблице вычисляют меры качества.Макроусреднение приписывает равные веса решениям классификатора длякаждого класса, а микроусреднение – равные веса решениям классификатора длякаждого документа. Классы с бОльшим числом документов (и решений по ним)вносят бОльший вклад в микроусреднение. Таким бразом, результатмикроусреднения в большей степени оценивают качество классификатора длякрупных классов коллекции документов. Чтобы оценить его на малых классахследует применять макроусреднение.§ 1.10.Выбор метода классификации с учителемОбзор экспериментальных исследований.
Исторически основным тестом дляоценки систем классификации с учителем является англоязычная коллекция Reuters21578 и её модификации. Reuters-21578 состоит из 21578 новостных сообщений, 118классов (категорий), документы могут принадлежать 0, 1 и более классам.Эксперименты на данной коллекции [2] показали, что:а) SVM > kNN >> {LLSF,NNet} >> NB, когда количество позитивныхпримеров для каждой категории мало (менее 10);б) {SVM, kNN, LLSF} >> {NB, NNet} при обычном наполнении категорий(более 300 экземпляров).Здесь «>>» и «>» означает «значительно эффективнее» и «эффективнее»соотвественно.NB – наивный байесовский классификатор; NNet – простая нейронная сеть типаперсептрона; kNN – алгоритм k-ближайшего соседа.Лабораторные эксперименты показали, что наивный байесовский классификаторне может конкурировать, например, с алгоритмом опорных векторов, еслиобучающие и тестовые данные являются независимыми и одинаковораспределёнными.
Однако в реальном мире (а) обучающие выборки извлекаются измножества данных, на которых потом будут применяться классификаторы; (б)природа данных изменяется во времени; (в) данные содержат ошибки. В итогеразница становится не такой существенной и даже может служить свидетельством впользу более простого подхода, такого как NB.Сравнение и ранжирование алгоритмов классификации зависит (а) от коллекциидокументов, (б) от рассматриваемого класса, (в) от условий эксперимента (выборатерминов/признаков, разбиения коллекции на подмножества, знания о тестовом189подмножестве и др.).
В результате сам по себе алгоритм редко является решающимфактором.Компромисс между смещением и дисперсией. Понять, почему не существуетодного оптимального алгоритма обучения, помогает концепция компромиссасмещения и дисперсии. Цель классификации текстов заключается в поиске такогооптимального классификатора, который после усреднения по всем документамколлекции гарантировал бы оценку принадлежности документов классам как можноболее близкую к истинной принадлежности документов классам. Более того,оптимальным алгоритмом обучения можно было бы назвать такой алгоритмобучения, который гарантировал бы построение этого оптимального классификаторав среднем по всем обучающим множествам, другими словами требуется алгоритмобучения с минимальной ошибкой обучения.Концепция компромисса между смещением и дисперсией говорит, что ошибкаобучения складывается из двух компонент – смещения и дисперсии –, которыеневозможно минимизировать одновременно.Смещение показывает, как в среднем по различным обучающим множествампрогноз классификатора отличается от истинной классификации данных.
Смещениевелико, если алгоритм обучения порождает плохие классификаторы. Смещение мало,если (а) порождает хорошие классификаторы, (б) разные обучающие множествапорождают разные ошибки на разных документах, (в) разные обучающие множествапорождают положительные и отрицательные ошибки на одних и тех же документах.Смещение можно интерпретировать как результат знаний о предметной области (илиих недостаток), встроенных в классификатор.Дисперсия показывает, как сильно зависит классификатор от того, на какомобучающем множестве он строился; насколько противоречивыми могут бытьрешения классификаторов независимо от того, правильные они или нет. Дисперсиявелика, если разные обучающие множества порождают совершенно разныеклассификаторы. Дисперсия мала, если обучающее множество мало влияет наклассификатор.
Дисперсию можно интерпретировать как емкость запоминанияалгоритма обучения. Емкость соответствует количеству независимых параметров,которые подгоняются на обучающем множестве. Например, для алгоритма Роккио –это | | центроидов по |m| параметров, соответствующих каждой размерностипространства терминов; такой алгоритм обучения не зависит от размера обучающейвыборки и не помнит тонкие детали распределения документов. Другой пример – этоалгоритм k-ближайших соседей, параметрами являются оценки `X |«) Z, где «) –множество соседей; каждое множество соседей порождает отдельное независимоерешение о классификации документа; емкость такого алгоритма ограничена лишьразмером обучающего множества; kNN «запоминает» обучающее множество. Длятаких рассмотренных алгоритмов как наивный байесовский классификатор, алгоритмРоккио, алгоритм k-ближайших соседей можно обобщить оценки смещения идисперсии следующим образом:190смещениелинейные (а) мало, если данные линейноалгоритмы разделимы;(б) велико, если данные неразделимы линейнонелинейные малоалгоритмыдисперсиямала (большинство случайновыбранныхобучающихмножеств порождает близкиегиперплоскости)велико (например, результатkNN зависит от наличияшумовыхдокументоввокрестности тестового)При сравнении двух алгоритмов обучения часто оказывается, что у одного изних больше смещение и меньше дисперсия, у другого – меньше смещение и большедисперсия.
Следовательно, необходимо взвесить относительные преимуществасмещения и дисперсии для конкретной прикладной задачи и на основании этойинформации выбрать алгоритм.191Глава 2.Алгоритмы классификации без учителяАлгоритмыклассификациибезучителяанализируютколлекциюполнотекстовых документов с целью разбиения их на группы так, чтобы внутриодной группы оказывались документы наиболее родственные в некотором смысле, аразличные документы попадали в различные группы. При этом отсутствует«учитель» - обучающее подмножество документов и заранее известное множествокатегорий (рубрик).
В общем случае алгоритм классификации без учителя – алгоритмкластеризации – должен самостоятельно принимать решения о количестве и составекластеров, то есть групп родственных документов. Для этого используются понятиярасстояний между документами.Кластеризация текстов основывается на кластерной гипотезе [7], говорящей, чтотесно связанные по смыслу документы стремятся быть релевантными одним и тем жезапросам, т. е. документы, релевантные запросу, отделимы от тех, которые нерелевантны этому запросу.Итак, дана коллекция документов " { },1, |"|, существует множествотематических классов, которым принадлежат документы коллекции.
Предполагается,что можно автоматически разбить множество документов на кластеры žс , 1, |ž|,и полученные кластеры будут соответствовать внутренним тематическим классам.Тогда задача автоматической кластеризации коллекции полнотекстовых документовсводится к поиску неизвестного множества ž таким образом, чтобы итоговоемножество ž являлось оптимальным в соответствии с некоторым критерием качестваразбиения документов.Далее мы рассмотрим несколько конкретных алгоритмов кластеризации,использующих различные подходы к формированию кластеров, и продолжим нашпример, начатый в разделе Глава 1, немного изменив исходные данные – добавимодин новый документ d6:docId123456Слова в документекитайский пекин китайскийкитайский китайский шанхайкитайский макаотокио япония китайскийкитайский китайский китайский токио япониятокио пекинс = «Китай»сссне с??Рассчитаем веса терминов для коллекции из 6 документов по формуле (1).192dfd1d2d3d4d5d6t1китайский5tf=2 |w=0.16|0,312 | 0,16 |0,201 | 0,08 |0,101 | 0,08 |0,253 | 0,24 |0,390§ 2.1.t2пекин21 | 0,48 |0,94t3шанхай10t4макао10t5япония20t6токио30000001 | 0,48 |0,931 | 0,48 |0,7801 | 0,30 |0,321 | 0,30 |0,491 | 0,30 |0,5701 | 0,78 |0,980001 | 0,78 |0,9800001 | 0,48 |0,84000Иерархические алгоритмыИерархические алгоритмы в отличие от плоских алгоритмов (например см.
§ 2.2и др.) создают структурированное множество кластеров – иерархию, которое можетоказаться весьма информативным для некоторых приложений. Иерархическиеалгоритмы разделяются на два вида: агломеративные (восходящие) и дивизимные(нисходящие). Первые строят кластеры снизу вверх, начиная с множества кластеров,содержащих по одному одиночному документу коллекции, затем последовательнообъединяют пары кластеров, пока не получат один кластер, содержащий вседокументы коллекции.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
