CLAIM – научно-образовательный кластер

Методика нейросетевой кластеризации корпуса текстов

Разработчик: Стулов В.В., руководитель Филиппович А. Ю.

Описание проекта

Цель исследования - разработка методики автоматического выявления групп семантически похожих документов

Назначение работы - методика предназначена для разработчиков систем информационного поиска.

Задачи исследования:

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

Предметная область

Приведем формальное определение задачи кластеризации. Пусть X - множество объектов, Y - множество номеров (имён, меток) кластеров. Задана функция расстояния между объектами D(x_i,x_j) . Имеется конечная обучающая выборка объектов. Требуется разбить выборку на подмножества, называемые кластерами, так, чтобы каждый кластер состоял из объектов, близких по метрике D, а объекты разных кластеров существенно отличались. При этом каждому объекту приписывается номер кластера.

Алгоритм кластеризации - это функция f: X->Y , которая любому объекту ставит в соответствие номер кластера. Множество Y в некоторых случаях известно заранее, однако чаще ставится задача определить оптимальное число кластеров, с точки зрения того или иного критерия качества кластеризации.

Кластеризация текстов может быть использована для анализа и поиска в больших текстовых коллекциях, таких как web-страницы. В качестве примера применения кластеризации, рассмотрим поиска. С увеличением количества текстов коллекции усложняется задача навигации в списке документов, релевантных тексту запроса. Кластеризация результатов поиска позволяет как выявлять среди релевантных документов группы наиболее релевантных, так и семантически группировать релевантные группы в тематические кластеры, а также образовывать иерархию кластеров (таксономию). Кластеризация результатов поиска применяется в Интернет-поисковике nigma.

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

Набор тестовых данных

В качестве тестового набора данных выбран архив Reuters-21578 состоящий из новостей агентства Reuters за 1987 год. Данный архив используется во многих исследованиях для проверки качества разработанного алгоритма кластеризации. Приведем характеристики архива. Reuters-21578 распространяется в виде xml-файла и состоит из 21578 текстов категоризованных по 135 темам, 56 организациям, 267 персоналиям, 175 географическим точкам. При этом только 9494 текста принадлежат отдельной тематической категории, в то время как остальные либо принадлежат нескольким категориям сразу, либо не категоризованы тематически. Количество категорий, содержащих хотя бы один текст, не пренадлежащий ни одной другой категории - 66.

Литература

Ronen Feldman and James Sanger: The Text Mining Handbook, Cambridge University Press, ISBN 9780521836579, 2006
Beil F., Ester M., Xu X.: "Frequent Term-Based Text Clustering", Proc. 8th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining (KDD '2002), Edmonton, Alberta, Canada, 2002
Zamir O., Etzioni O.: Web Document Clustering: A Feasability Demonstration, Proc. ACM SIGIR 98, 1998, pp.46-54
4. Bhoopesh Choudhary, Pushpak Bhattacharyya Text Clustering using Semantics, THE ELEVENTH INTERNATIONAL WORLD WIDE WEB CONFERENCE, 2002
5. А.М. Андреев, Д.В. Березкин, В.В. Морозов, К.В. Симаков: Метод кластеризации документов текстовых коллекций и синтеза аннотаций кластеров, ЭЛЕКТРОННЫЕ БИБЛИОТЕКИ: ПЕРСПЕКТИВНЫЕ МЕТОДЫ И ТЕХНОЛОГИИ, ЭЛЕКТРОННЫЕ КОЛЛЕКЦИИ, Десятая Всероссийская научная конференция, 2008
Magnus Rosell: Introduction to Information Retrieval and Text Clustering, KTH CSC, 2006
Г.С. Осипов, И.В. Смирнов, И.А. Тихомиров: "Реляционно-ситуационный метод поиска и анализа текстов и его приложения", Искусственный интеллект и принятие решений 2008 / 02
http://en.wikipedia.org/wiki/Latent_semantic_analysis
Л.Г. Комарцова, А.В. Максимов: Нейрокомпьютеры Издательство МГТУ им. Н.Э. Баумана, 2004
http://www.basegroup.ru/library/analysis/clusterization/som_mine/
Пекар В.И. Селекция признаков в дистрибутивной модели лексического значения слова, "Штучний інтелект" №.4'2004
Karypis, G.; Eui-Hong Han; Kumar, V.: CHAMELEON: A Hierarchical Clustering Algorithm Using Dynamic Modeling, IEEE Computer, Volume 32, Issue 8, Aug 1999 Page(s):68 - 75
Martin Nilsson: Hierarchical Clustering Using Non-Greedy Principal Direction Divisive Partitioning, Information Retrieval, 5, 311-321, 2002
Choon Shik Lee, Hark Hwang: A HIERARCHICAL DIVISIVE CLUSTERING METHOD FOR MACHINE-COMPONENT GROUPING PROBLEMS, Engineer-ing Optimization, Volume 17, Issue 1 & 2 February 1991 , pages 65 - 78
Nicholas O. Andrews and Edward A. Fox: Recent Developments in Document Clustering, Department of Computer Science, Virginia Tech, Blacksburg, 2007
http://modnlp.berlios.de/reuters21578.html
Описание программного пакета синтаксического разбора и машинного перевода, Cognitive Technologies, Ltd., 2006