(30) Типы классификаторов текстов в рамках синтагматического подхода. В настоящее время практическое применение получили классификаторы следующие типов:

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

2. Классификаторы, основанные на функциях подобия. В терминах введенной модели (2.3) характерной чертой данного метода является универсальность описанийF, которые с одной стороны используются для представления содержания рубрик, а с другой стороны – содержания анализируемых текстов. Процедура классификацииfиспользует меру подобия (семантическое расстояние) видаE: FxF→[0;1], позволяющую количественно оценивать тематическую близость описанийи, где описаниеF_tпредставляет содержание анализируемого текста, аF_i– содержание некоторой рубрики. Действия процедуры классификацииf сводятся к преобразованию анализируемого текстаtв представление, оценке подобия описанияF_tс описаниями рубрикF_i, и заключение по результатам сопоставления о принадлежности текста одой или нескольким рубрикам. Последнее заключение выполняется либо на основе сравнения с пороговой величинойE_min, так что текст относится ко всем рубрикамc_i, для которыхE(F_t,F_i)>E_min, либо из всехE(F_t,F_i)выбирается максимальная величина, которая и указывает на результирующую рубрику. Наиболее характерными для таких классификаторов является использование лексических векторов модели терм-документ в описанияхF, которые так же применяются и в нейронных классификаторах. В качестве меры подобия обычно берется косинус угла между векторами, вычисляемый через скалярное произведение

3. Классификаторы, построенные с использованием методов детерминистского подхода: искусственные нейронные сети, метод опорных векторов и т.п. Нейросети хорошо зарекомендовали себя в задачах распознавания изображений, однако, с большим успехом применяются в обработке ЕЯ-текстов. Описания классов F, как правило, представляют собой многомерные вектора действительных чисел, заложенные в синаптических весах искусственных нейронов, а процедура классификации f характеризуется способом преобразования анализируемого текста t к аналогичному вектору, видом функции активации нейронов, а так же топологией сети. Процесс обучение классификатора в данном случае совпадает с процедурой обучения сети и зависит от выбранной топологии.

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

2.1.2.5. (31) Кластеризация текстов

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

Кластерный анализ занимает одно из центральных мест среди методов анализа данных и представляет собой совокупность методов, подходов и процедур, разработанных для решения проблемы формирования однородных классов (кластеров) в произвольной проблемной области.

Задача кластеризации заключается в следующем. Заданы:

• коллекция тестов D, подлежащих кластеризации;

• множество описаний Fдокументов этой коллекции в признаковом пространстве;

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

• функция расстояния между объектами ;

• множество номеров кластеров Y.

• процедура кластеризации (алгоритм кластеризации) f:D→Y, которая заключается в разбиении обучающей выборки на подмножества, называемые кластерами, так, чтобы каждый кластер состоял из объектов, близких по метрикеρ, а объекты разных кластеров существенно отличались. При этом каждому документуприписывается метка (номер) кластера _{(см. Рис. 3.2)}.

Рис. 3.2.

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

,

При кластеризации документов возникают некоторые сложности, связанные с множественностью выбора алгоритмов этого процесса. Разные методологии используют разные алгоритмы подобия документов при наличии большого количества признаков. Механизм классификации обычно обучается на отобранных документах только после того, как заканчивается стадия обучения путем автоматической кластеризации - разбиения множества документов на классы (кластеры), смысловые параметры которых заранее неизвестны. При этом для каждого кластера находится центроид - документ, чей образ расположен наиболее близко к геометрическому центру кластера. Количество кластеров может быть произвольным или фиксированным. Если классификация допускает приписывание документам определенных, известных заранее признаков, то кластеризация более сложный процесс, который допускает не только приписывание документам некоторых признаков, но и выявление самых этих признаков как основ формирования классов. Цель методов кластеризации массивов документов состоит в том, чтобы подобие документов, которые попадают в кластер, было максимальным. Поэтому методы кластерного анализа базируются на таких определениях кластера, как множества документов, значение семантической близости, т.е. функции, обратной функции расстояния ρ(x,x′), для любых двух элементов этого множества (или значение близости между любым документом этого множества и центром кластера) не меньше определенного порога.

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

,

где x и y — образы документов в признаковом пространстве, представляющие собой векторы, элементами которых являются весовые значения термов, которые, как правило, определяются в результате анализа большого массива документов. Частным случаем при р=2 метрики Минковского является Евклидова метрика. Для группирования документов, представленных в виде векторов весовых значений входящих в них термов, часто используется скалярное произведение весовых векторов.

Решение задачи кластеризации текстов выдвигает ряд требований к алгоритму кластеризации:

• применимость сильно сгруппированных данных;

• автоматическое определение оптимального числа кластеров;

• не более чем логлинейный рост времени работы кластеризатора с увеличением количества текстов;

• минимальная (в лучшем случае отсутствующая) настройка со стороны пользователя.

Задача кластеризации текстов с трудом поддается формализации. Оценка адекватности разбиения множества D, как правило, основывается на мнении эксперта и трудно выразима в виде одной численной характеристики. Возникает требование интерпретируемости результата: кластерам должны быть присвоены некоторые метки, отражающие их семантику. Следовательно, процедура кластеризации должна еще обладать свойством интерпретируемости найденных кластеров в терминах смысла содержания относящихся к ним документов.

(32) Рассмотрим наиболее распространенные алгоритмы кластеризации. В общем виде методы кластеризации могут быть разбитына две группы:представляющие тексты в виде векторов в многомерном пространстве признаков (и использующие метрику близости между векторами) и применяющие другие представления анализируемых текстов. Первая группа использует неиерархические алгоритмы: метод k-средних — модификация метода k ближайших соседей, латентно-семантический анализ, и которые позволяют выявить достаточно чётко выделяемыекластеры), а также большое число других базирующихся на них методов. Примером алгоритмов второй группы является алгоритм Suffix Tree Clustering (STC – древовидные структуры).

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

Иерархические методы строят полное дерево вложенных кластеров (см. Рис. 3.5). Сложности данных методов кластеризации – ограничение объема набора данных, выбор меры близости, негибкость полученных классификаций. В частности, недостатками метода STC являются обязательное наличие первоначального дерева, значительное время работы при больших размерах первоначального дерева.

Рис. 3.5.

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

Недостатком метода является то, что каждый документ может попасть всего лишь в один кластер.

Литература

1. Spark Jones, K, Kay, M. Linguistic and Information Science, Academic Press. - New York and London: 1973

2. Salton, G. Automatic Text Analysis, Science, 168, 335-343 (1970)

3. Patwardhan S., Pedersen T. Using WordNet-based context vectors to estimate the semantic relatedness of concepts//EACL 2006 Workshop Making Sense of Sense. — 2006. P.1–8

4. Schutze H. Automatic word sense discrimination // Computational Linguistics. — 1998. — V. 24. P.97–123

5. Шаров С.А. Частотный словарь русского языка [Электронный ресурс]. – Режим доступа: http://www.artint.ru/projects/frqlist.asp, свободный

6. D.A. Hull. Stemming Algorithms – A Case Study for Detailed Evaluation, JASIS, 47(1): 70-84, 1996

7. M.F.Porter. An algorithm for suffix stripping, Program, 14(3) :130-137, 1980

8. Леонтьева Н. Н. Неполнота и смысловое сжатие в текстовом корпусе // Международная конференция MegaLing'2005 «Прикладная лингвистика в поиске новых путей». Материалы конференции. Меганом, Крым, Украина. Симферополь: Изд-во «Осипов». СПб, 2005. C. 67-73

9. Deerwester, S., Dumais, S.T., Furnas, G.W., Landauer, T.K. and Harshman, R.A. 1990. Indexing by Latent Semantic Analysis. Journal of the American Society for Information Science, 41: 391-407

10. Веб-сайт Pearson Knowledge Technologies – http://www.k-a-t.com

11. Тыртышников Е.Е. Курс линейной алгебры. − М., 2004

12. Леонтьева Н.Н. Автоматическое понимание текста: системы, модели, ресурсы: учебное пособие – М.: Издательский центр «Академия», 2006

13. Перцова Н.Н. К построению глубинно-семантического компонента модели понимания текста // Проблемы вычислительной лингвистики и автоматической обработки текста на естественном языке – М., 1980

14. Шенк 1980

15. Новиков А.И. Семантика текста и ее формализация, – М.: Наука, 1983

16. Файн В.С. Распознавание образов и машинное понимание естественного языка – М.: Наука, 1987