Векторно-пространственная модель

 

Согласно веденной ранее трехосновной алгебраической системе (1.1) обозначим D- коллекцию документов (текстов), T - множество всех термов (словарь коллекции), tf(ti,dj) — число вхождений терма ti в документ dj, df(ti) - число документов коллекции D, содержащих терм ti. В рамках этой модели каждому терму ti в документе dj сопоставляется некоторый неотрицательный вес wij. Следовательно, образ каждого документа может быть представлен в виде многомерного вектора W(d_j)ϵF, W(d_j) =( w1j, w2j,...,wij, …,w|T|j), где |T| - общее количество различных термов во всех документах (мощность множества Т). Согласно векторной модели, близость документов оценивается как корреляция между векторами их описаний. Эта корреляция может быть вычислена как скалярное произведение соответствующих векторов описаний.

Один из возможных подходов - использовать в качестве веса терма w_ij в документе d_i нормализованную частоту его использования в данном документе:

 

wij= tf(ti,dj)/ | dj|

где |dj| - число термов в документе

Этот подход не учитывает частоту отдельного терма во всем информационном массиве, так называемую, дискриминационную силу терма. Поэтому в случае, когда доступна статистика использования термов во всем информационном массиве, более эффективно следующее правило вычисления весов:

 

wij = tf(ti,dj) *log |D|/nj= tfij*idf(tj),

где nj - число документов, в которых содержащих терм tj, |D| - мощность множества D (общее число документов в массиве), величина idf(t) получила название инверсная частота терма (inverse document frequency).

В случае, если терм t_i не входит в документ d_j, вес терма wij =0.

По поводу приведенной формулы можно заметить следующее: вес терма t_i тем выше, чем чаще встречается этот терм в данном документе d_j, и чем реже в остальных документах коллекции. Таким образом, делается попытка присвоить больший вес тем терминам, которые «отличают» данный текст от остальных текстов коллекции C.

Такой метод взвешивания термов имеет стандартное обозначение - TF*IDF, где TF указывает на частоту встречаемости терма в документе (term frequency), а IDF на величину, обратную числу документов массива, содержащих данный терм (inverse document frequency).

Необходимо учесть различную длину документов коллекции. Поэтому, обычно, веса wij нормируются [F. Debole and F. Sebastiani, Supervised term weighting for automated text categorization. In the Proceedings of SAC-03, 18th ACM Symposium on Applied Computing, Melbourne, US: ACM Press, New York, US, 2003, pp. 784—788. ]: дополнительно делятся на квадратный корень из суммы весов всех термов, входящих в документ, что позволяет рассматривать документ как ортонормированный вектор.

В качестве меры близости документов d1 и d2можно взять скалярное произведение sim(d1,d2) = W(d1)∙W(d2) равное косинусу угла между векторами - образами документов d1и d2. Величина sim(d1,d2) принадлежит диапазону [0,1]. При этом для любого документа d имеем sim(d,d) = 1. Таким образом, чем больше величина sim(d1,d2) тем ближе считаются документы d1и d2.

Аналогично, мерой близости темы q документу d считается величина sim(q,d).

Векторно-пространственная модель представления данных обеспечивает системам, построенным на ее основе, такие возможности:

· обработку сколь угодно больших запросов;

· простую реализацию режима поиска документов, подобных уже найденным;

· сохранение результатов поиска в некотором виртуальном массиве, с последующим уточняющим поиском в нем.

В зависимости от выбора терма можно обеспечить такие возможности:

· возможный учет морфологии, когда все формы одного слова соответствуют одному термину;

· возможный учет синонимии, так что слова - синонимы, объявляются одним термином словаря;

· возможность учета устойчивых словосочетаний, так что в качестве термина может выступать не отдельное слово,а несколько связанных слов, образующих единое понятие.

 

Одним из эффективных алгоритмов классификации, использующих представление документа в виде многомерного вектора является метод k-ближайших соседей.

Метод k-ближайших соседей - один из самых изученных и высокоэффективных алгоритмов, используемых при создании автоматических классификаторов. Впервые он был предложен еще в 1952 году для решения задач дискриминантного анализа. В исследованиях, посвященных анализу работы различных алгоритмов машинного обучения для задачи классификации текстов, этот метод показал одни из наилучших результатов.

В основе метода лежит очень простая идея: находить в отрубрицированной коллекции самые похожие на анализируемый текст документы и на основе знаний об их категориальной принадлежности классифицировать неизвестный документ.

Рассмотрим алгоритм подробнее. При классификации неизвестного документа находится заранее заданное число k текстов из обучающей выборки, которые в пространстве признаков расположены к ближе всего. Иными словами находятся k-ближайших соседей. Принадлежность текстов к распознаваемым классам считается известной. Параметр k обычно выбирают от 1 до 100. Близость классифицируемого документа и документа, принадлежащего категории, определяется как косинус угла между их векторами признаков. Чем значение ближе к 1, тем документы больше друг на друга похожи.

Решение об отнесении документа к тому или иному классу принимается на основе анализа информации о принадлежности k его ближайших соседей. Например, коэффициент соответствия рубрики анализируемому документу, можно выяснить путем сложения для этой рубрики значений.

При монотематической классификации выбирается рубрика с максимальным значением. Если же документ может быть приписан к нескольким рубрикам (случай мультитематической классификации), классы считаются соответствующими, если значение превосходит некоторый, заранее заданный порог.

Главной особенностью, выделяющей метод k- ближайших соседей среди остальных, является отсутствие у этого алгоритма стадии обучения. Иными словами, принадлежность документа рубрикам определяется без построения классифицирующей функции.

Основным преимуществом такого подхода является возможность обновлять обучающую выборку без переобучения классификатора. Это свойство может быть полезно, например, в случаях, когда обучающая коллекция часто пополняется новыми документами, а переобучение занимает слишком много времени.

Классический алгоритм предлагает сравнивать анализируемый документ со всеми документами из обучающей выборки и поэтому главный недостаток метода k-ближайших соседей заключается в длительности времени работы рубрикатора на этапе классификации.

 

В качестве недостатков векторно-пространственной модели выделим следующее:

· при отсутствии простейшей дополнительной обработки, такой как морфологический анализ, существенно снижается качество классификатора, поскольку разные формы одного слова считаются разными терминами, вместе с тем морфологический анализ – весьма нетривиальная задача, требующая для ее решения привлечения лингвистов;

· размерность векторов признаков зависит от общего количества терминов в обучающей выборке текстов, что в реальных задачах приводит к необходимости разрабатывать альтернативные структуры данных, отличные от векторов;

· словарь терминов может не охватывать всех документов, подлежащих классификации, так что анализируемые документы могут содержать значимые термины, не вошедшие в обучающую выборку, что отрицательно сказывается на адекватности модели.

Следует отметить, что анализ структуры текста усложняется при использовании признаков более высоких уровней иерархии и с каждым новым уровнем труднее поддается автоматизации. Так, в процессе морфологического анализа используется информация, полученная на этапе лексического анализа, на этапе синтаксического анализа – информация, полученная на этапе морфологического анализа, и т.д. На каждом из этапов могут возникнуть неточности, например из-за зашумленности анализируемого текста, особенностей русского языка (морфологическая, синтаксическая омонимия) и т.д., которые далее приведут к серьезным ошибкам на более высоких уровнях анализа. Поэтому разработаны подходы к представлению текста, которые ограничиваются характеристиками уровней символов и слов.

В отличие от векторно-пространственной модели модель n-грамм в качестве информативных элементов текстов использует частотные характеристики различных фрагментов слов текстов документов. Одно из основных преимуществ такого подхода состоит в том, что он применим для любого естественного языка и не требует участия специалистов в конкретном языке. Вторым немаловажным фактором является то, что при использовании фрагментов постоянной длины возможно установить максимальное количество фрагментов (n-грамм) для данного языка.

 

Модель n-грамм

 

В полиграммной модели со степенью n и основанием M текст представляется вектором {fi}, i=1..Mn, где fi – частота встречаемости i -ой n -граммы в тексте. n -грамма является последовательностью подряд идущих n – символов вида a1…an-1an, причем символы ai принадлежат алфавиту, размер которого совпадает с M. Непосредственно номер n -граммы определяется как

 

Mⁿ r(a_n) + M^n-1 r(a_n-1) +...+r(a₁),

 

где r(ai) ϵ [1,M] – порядковый номер символа ai в алфавите.

Предполагается, что частота появления n -граммы в тексте несет важную информацию о свойствах документа, поэтому является информативным признаком при представлении текстов документов. Кроме того, максимальное количество n -грамм постоянной длины для данного языка фиксировано и не зависит от объема обучающего корпуса текстов. Так, например, для русского языка, как правило, используется модель со степенью n =3 (триграммная модель) и основанием M =33, при этом применяется русский алфавит с естественной нумерацией символов r("А") = 1, r("Б") = 2,..., r("Я") = 32. Все остальные символы считаются пробелами с нулевыми номерами. Несколько подряд идущих пробелов считаются одним. С учетом этого размерность вектора для произвольного текста жестко фиксирована и составляет 333= 35937 элемента. Однако, как показывает практика, в реальных текстах реализуется не более 25-30 процентов n-грамм от общего допустимого их числа, т.е. для русского языка их не более 7000. Кроме того, сведения о биграммах и триграммах символов наиболее частых слов русского языка существуют в электорнном виде и находятся в свободном доступе [Шаров С.А. Частотный словарь русского языка [Электронный ресурс]. – Режим доступа: http://www.artint.ru/projects/frqlist.asp, свободный ].

Достоинствами полиграммной модели являются:

· отсутствие необходимости дополнительной лингвистической обработки;

· фиксированная размерность векторов и простота получения векторного описания текста.

К недостаткам отнесем следующее:

· отражение векторами {fi} содержания текста не всегда адекватно (такой моделью плохо отражается содержание небольших текстов; модель больше подходит для определения языка текста, чем для классификации по тематике),

· в соответствии с предыдущим пунктом возникает необходимость более тщательного подбора обучающей выборки текстов.

Количественное описание семантических связей, наблюдаемых в языке и в тексте, построение классификаторов на их основе невозможно без обращения к методам теории вероятностей, математической статистики, теории множеств, теории информации, теории распознавания образов и предполагает разработку специализированных алгоритмов и программ.