3. Модели синтагматического подхода

Синтагматический подход предполагает измерение семантических расстояний в тексте и между текстами. Исходный тезис таков: обращение к корпусу позволяет использовать данные о значении слова, хранящиеся «вне» языкового знака, и определять содержательную близость лексических единиц, сопоставляя их синтагматические свойства.

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

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

3.1. Способы представления текста

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

Классической алгебраической моделью в рамках такого представления текста является векторно-пространственная (Vector Space Model) модель.

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

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

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

w_ij = tf(t_i,d_j)/ |d_j|

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

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

w_ij = tf(t_i,d_j) *log |D|/n_j = tf_ij *idf(t_j),

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

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

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

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

Необходимо учесть различную длину документов коллекции. Поэтому, обычно, веса w_ij нормируются [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. ]: дополнительно делятся на квадратный корень из суммы весов всех термов, входящих в документ, что позволяет рассматривать документ как ортонормированный вектор.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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