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

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

Автоматическая классификация документов является критическим пунктом в области Information Retrieval, и в частности, в системах поиска информации в такой слабо формализованной системе как Интернет. Такая классификация затрудняется из-за большого количества документов, их неоднородности по структуре, лексике и размерам.

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

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

Cуществующие методы кластеризации многомерных пространств могут быть разделены на иерархические и разделяющие методы. Все они страдают от специфических нелостатков при обработке больших обьёмов данных. Иерархические методы предоставляют структурную информацию, такую как дендрограммы, но применимы только для небольших наборов данных. С увеличением размеров вычислительные затраты растут вследствии необходимости считать матрицу близости где каждый сравнивается с каждым. Разделяющие методы несколько менее требовательны к ресурсам, но они страдают от методической несвободы из-за предпосылки о "правильной догадке о структуре" т.е. количества и начального положения центров кластеров. Если выбор начальных кластеров далек от идеала разделяющие методы становятся очень ресурсоемкими в вычислении новых центров кластеров.

Методы кластеризации при помощи нейронных сетей являются развитием классических методов кластеризации. Например, метод квантизации векторов с помощью сети Кохонена содержит в своей основе метод "K nearest neighbours". В то же время нейронные сети являются гораздо более гибким инструментом в применении к данным, имеющим большой обьем и избыточную размерность. В частности, это многоуровневый перцептрон, cаморганизующиеся сети Кохонена. Поскольку в случае автоматической классификации документов желаемая классификация для тренировки сети отсутствует, были выбраны самоорганизующихся сети с методом обучения типа нейронный газ.

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

Важным условием успешной кластеризации является корректная подготовка данных. Для того, чтобы преобразовать текстовые документы в вектора, необходимо идентифицировать термы, которые будут включены в сигнатуру или профайл документа. Профайл генерируется путем кодирования словаря, его последующей редукции с помощью стоп-листа, удаления часто встречающихся слов, стемминга. Слова могут быть подвержены лексическому анализу, объединены в концептуальные классы и заменены едиными синонимами. В частности в рамках проекта OASIS такая работа была проделана со словарем русского языка. Для повышения качества кодирования HTML документов, при постороении профайла учитываются HTML таги, такие как выделение жирным шрифтом, заголовки, ссылки, содержание мета-тагов и т.п.

Для последующего сокращения размерности векторов исследуется возможность применения подметода Latent Semantic Indexing (LSI) - Singular Value Decomposition (SVD), один из методов анализа компонентов. Этот метод позволяет выделить и отсортировать по степени вариантности собственные вектора на пространстве профайлов. Отбрасывание наименее значительных собственных векторов позволяет сократить размерность пространства до 50-200.

Для инициализации начальных положений нейронов использовался алгоритм типа BANG clustering позиционирующий нейроны в области с высокой ожидаемой концентрацией векторов. Этот вариант клеточной кластеризации (cell clustering), заключается в делении векторного пространства на области одинаковой величины и выделении областей с повышенной относительно среднего уровня концентрацией элементов. Затем каждая такая область делится на подобласти для которых этот процесс повторяется до тех пор пока не будет достигнута нужная концентрация. Далее в отличии от оригинальной клеточной кластеризации данный алгоритм помещает нейроны в середине этих областей, для дальнейшей тренировки.

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

Работает метод следующим образом : на каждом шаге

1. 1) случайным образом выбирается один из документов
2. 2) все нейроны сортируются по близости к выбранному документу
3. 3) все они адаптируются (т.е. меняют координаты) по отношению к выбранному документу в зависимости от ранга и прошедшего времени.
4. 5) затем разрешается нейронный конфликт путем удаления конфликтующих нейронов от победителя (т.е. ближайшего к данному документу).

Тренировка прекращается при стабилизации квадратичной ошибки на заданном уровне. (Квадратичная ошибка вычисляется как среднее расстояние документа до ближайшего нейрона.)

Анализ конечных координат нейронов позволяет локализовать кластеры документов в векторном пространстве профайлов документов методом nearest neighbours с выделением документов лежащих слишком далеко от всех центров кластеров в отдельные кластеры.

Такое однопроходное обучение применяется для функции clustering-on-fly, например для того, чтобы сгруппировать документы, образовавшиеся в результате поиска. Каждая выделенная группа или кластер будет представлена документом-центроидом, документом, наиболее "типичным" или "характерным" для данной группы документов. Документ-центроид определяется как документ, лежащий ближе всех к геометрическому центру кластера. Представление большого количества документов центроидами кластера облегает пользователю навигацию и feedback.

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

Работоспосбность NN выяснялась как на искусственно сгенерированных данных (равномерные распределения, одно и много горбые нормальные распределения), так и на реальных данных. В первом случае для облегчени анализа результататов генерировались наборы векторов с небольшой (1,2,3,10,100) размерностью. При этом были показаны весьма приемлимые результаты. (особенно это было заметно на двумерных данных). Эксперименты с реальными данными ставились следующим образом: брались выборки из нескольких (2-4) тематических коллекций. Стопроцентно удачным считалось кластеризация всех документов на кластеры так чтобы их число равнялось числу коллекций из которых производилась выборка и каждый кластер в точности соответствовал одной из выборок. При переходе к реальным данным обнаружилась сильная зависимость качества работы NN от характера и размерности кластеризуемых данных. Но после настройки сети к конкретным входным данным точность обычно повышалась с 50 до 90-100 процентов.

В данной работе был продемонстрирован метод автоматической кластеризации HTML документов с помощью самоорганизующихся нейронных сетей типа нейронный газ. Данное исследование, проведенное в рамках проекта OASIS, продемонстрировало применимость нейронных сетей как для задач кластеризации on-fly для нужд представления данных пользователю для осуществления feedback, так и для иерархической кластеризации коллекций документов для дальнейшего пропагирования запроса на этих коллекциях.

Bernd Fritzke "Some Competive Learning Methods" April 5 1997

Erich Shikta "Grid-Clustering: An Efficient Hierarchical Clustering Method for Very Large Data Sets" Technical Report N TR-96201. Institute of Applied Computer Science and Information Systems, University of Vienna, 1996

E. Schikuta, M. Erhart: The BANG-Clustering System: Grid-Based Data Analysis, in X. Liu, P. Cohen, M. Berthold (Eds.): Advances in Intelligent Data Analysis (IDA-97), LNCS 1280 pp. 513-524, 1997