Текстовая кластеризация
алгоритмом ROCK
Введение
Большой рост количества информации в электронном виде привел к серьезным проблемам, связанным с ее структуризацией. По данным корпорации EMC[1] на сегодняшний день более 95% цифровой среды состоит из неструктурированной информации. В организациях неструктурированные данные составляют свыше 80% всей информации. Наибольшая часть этих данных содержится в виде текстовых документов.
Структуризация наборов текстовых документов может потребоваться для поиска и сравнения похожих текстов, поиска дубликатов, составления списка документов смежной тематики или просто списка рекомендуемых документов.
Решением этих задач занимается кластерный анализ текстовых документов. Так как документы написаны на человеческом языке, из которого машине трудно выявлять полезную информацию, одной из важных задач кластерного анализа является представление документов в удобном виде для последующей машинной обработки. Текстовые данные практически в любом представлении имеют свою специфику по сравнению с наборами числовых данных, что необходимо учитывать при выборе алгоритма кластеризации.
Целью данной работы является разработка анализатора на основе алгоритма ROCK для последующей кластеризации кафедральной базы знаний, работающей на популярном для использования в образовании движке MediaWiki[2]. Результатом работы является комплекс программного обеспечения, состоящий из программ подготовки текстовых документов и кластеризации, а также расширений для MediaWiki, позволяющих управлять кластеризацией, задавать различные параметры анализа и просматривать результаты анализа.
Подготовка текстовых документов
Теоретическая часть
Текстовый документ с точки зрения машины представляет собой объект, из которого достаточно сложно выявить какие-либо полезные данные кроме размера документа и его метаданных для последующего кластерного анализа. Чтобы это стало возможным, необходимо для начала подготовить текстовый документ, привести его в вид наиболее удобный для анализа машиной.
Существует две наиболее распространенные модели представления текстовых документов: древовидная[3] и векторная модели[4]. Древовидная представляет собой наборы цепочек следующих друг за другом слов. Это позволяет затем машинным анализом выявлять среди нескольких документов похожие цепочки и таким образом выявлять их схожесть. Однако, такой вид представления документа наиболее востребован при проверке на плагиат. В случае же с кластеризацией текстовых документов наилучшим представлением документа является векторная модель.
Векторная модель документа представляет собой таблицу частоты употребления слов в документе. Такое представление позволяет хотя и с некоторой погрешностью, но достаточно быстро определить ключевые слова текста, а значит и его тематику. В особенности такое правило действует для технической литературы, которая и является основным предметом кластеризации данной работы.
В человеческих языках и особенно в русском языке слова имеют достаточно много аффиксов (то есть вспомогательных частей слова, присоединяемых к корню для образования новых однокоренных). Так при составлении векторной модели документа в таблице могут попадаться однокоренные слова с разными окончаниями, которые можно было бы учитывать как одно слово при рассмотрении его тематического значения. Следует заметить, что некоторые аффиксы достаточно сильно меняют смысл слова, поэтому нельзя их рассматривать как незначащие при определении тематического значения (например, «сложный» - «несложный», «использующий» - «используемый»). Значимая часть слова, очищенная от незначащих аффиксов, называется термом. Терм – это основной элемент таблица частоты слов. Таким образом, чтобы векторная модель документа наиболее точно отображала тематику текста, необходимо каждое слово в тексте преобразовывать в терм и только потом считать статистику его употребления.
Говоря о технической литературе, следует заметить, что она обычно имеет некоторую структуру заголовков и элементов форматирования для удобства использования человеком. Заголовки обычно содержат наиболее значимые слова текстового документа. Также заголовки документа обычно имеют иерархию, то есть подзаголовки различного уровня, слова в них также имеют различный тематический вес. Эту особенность также следует учитывать при построении векторной модели документа. Кроме того, в тексте могут встречаться различные другие элементы форматирования, придающие словам в них больший или меньший вес.
После построения векторной модели документа, используя все выше изложенные правила, возникает вопрос о хранении этой модели. Так как модель представляет собой таблицу, наиболее удобно хранить ее с помощью любой реляционной СУБД. Это позволит разумно использовать место на жестком диске и быстро получать доступ к данным модели любого документа. Также следует учесть, что в разных документах встречаются одни и те же слова. Для большей экономии ресурсов машины следует нормализовать данную таблицу, приведением ее к третьей нормальной форме (3NF)[5]. После преобразования получится таблица с уникальными словами всех документов, участвующих в кластеризации и таблица с идентификаторами записей из таблицы слов и частотой этих слов. Таким образом, при работе с векторной моделью, мы будем использовать только относительно небольшие целочисленные значения, что позволит снизить место в оперативной памяти, требуемое для работы программы.
Практическая часть
Реализация подготовки текстовых данных из базы, используемой движком MediaWiki, имеет ряд особенностей. Структура данных движка представлена следующим образом: имеется таблица с идентификаторами, названиями всех ресурсов имеющихся на сайте (в том числе текстовых, изображений, других медиа, служебных страниц), и ссылкой на сам ресурс. Ресурсы же распределены по таблицам в зависимости от типа данных. Например, все текстовые ресурсы, включая страницы обсуждений, некоторые служебные страницы, элементы дизайна хранятся в одной таблице с основными статьями движка. Однако, благодаря распределению текстовых ресурсов по пространствам имен, можно сделать выборку только среди нужных разделов (основное пространство, порталы, страницы пользователей). Также следует учитывать, что помимо актуальной версии текстового ресурса, в базе содержатся все когда-либо существовавшие его версии. Таким образом, прежде всего, необходимо было грамотно составить запрос к базе, чтобы получить только актуальные версии статей определенных разделов и связать их со своими заголовками.
В данной реализации для экономии оперативной памяти программа сначала получает список идентификаторов на текстовые ресурсы, которые должны быть приведены к векторной модели, а затем по одному производит выборку самого текстового ресурса, обрабатывает его, производит действия по сохранению результатов и очищает память от обработанного ресурса, заменяя его следующим.
Рассмотрим подробнее алгоритм преобразования текста в векторную модель. В данной реализации для экономии времени разбор текста происходит посимвольно один раз на каждый текст. В процессе этого разбора отсеиваются все незначимые символы (знаки препинания, незначащая разметка) и происходит выделение отдельных слов для последующего анализа и занесения во временный список термов статьи.
При разборе слова сначала происходит проверка его языка и регистра. На данный момент, так как англоязычные статьи не являются предметом кластеризации в данной работе, то разбор проходит только русских слов, однако, при желании дописать необходимую часть не составляет труда. Если длина слова в нижнем регистре не превышает 3 символов, то скорее всего это предлог и тратить время на его разбор нерационально. Такие короткие слова отбрасываются на этом этапе. Если полученное слово записано в верхнем регистре, то оно считается аббревиатурой и также без более глубокого анализа заносится во временный список термов.
Анализ слова производится с помощью стемминга, то есть преобразованием его в терм, определяя часть речи и удаляя присущие этой части речи аффиксы, не меняющие смысла слова сильно. В данной реализации используется достаточно простой, но наиболее быстрый алгоритм Портера[6], адаптированный под русский язык.
После составления списка термов документа производится подсчет статистики употребления слов. Также для экономии времени вычислений в цикле подсчета статистики происходит проверка, входит ли терм в список стоп-слов.
Стоп-слова – слова, не несущие в себе смысла и не влияющие на его тематику. Такими словами чаще всего являются предлоги, союзы и другие части речи, предназначенные для связи слов в предложениях. Также стоп-словами являются расширения графических файлов, элементы оформления ссылок(“http”, “www”,”net” и т. д.) Также для некоторого набора статей могут существовать свои стоп-слова, например адрес сайта или названия вспомогательных ресурсов, не определяющих тему статьи. На данный момент список стоп-слов задается разработчиком, но в будущем планируется частично перенести эту функцию на администратора, тем самым сделав инструмент более гибким в настройке.
После всех описанных выше процессов статистика употребления слов заносится в таблицу векторной модели. При этом до занесения происходит попытка также внести новую запись в таблицу уникальных слов. Средства СУБД MySQL позволяют не делать проверку уникальности слова перед занесением его в таблицу, выставив соответствующий атрибут полю на этапе проектирования базы. Если слово уже есть в базе, то оно не заносится в нее снова. Затем извлекается идентификатор слова и в таблицу векторной модели заносятся: этот идентификатор, частота слова и идентификатор статьи.
В данной реализации отдельно происходит разбор заголовков. Это обосновывается желанием в дальнейшем иметь инструмент регулировки значимости слов в заголовках. Все процессы, производимые с обычным текстом, также проводятся и с заголовками, отличием является лишь подсчет частоты употребления слов: здесь происходит умножение на коэффициент с учетом уровня заголовка, в котором встречается слово.
Вычислительная сложность процесса подготовки данных достаточно невелика и линейно зависит от размеров статей. Так как заголовки значительно меньше по объему основной части статьи, то вычислительная сложность процесса близка к O(N).
В реализации расширения для движка MediaWiki имеется параметр «Минимальный размер статьи», задаваемый администратором и позволяющий более гибко проводить подготовку текста. Этот параметр устанавливает минимальный размер документов, участвующих в кластеризации. Некоторые документы могут быть слишком малы, чтобы можно было определить их тематику по частоте употребления слов. Также этот параметр рекомендуется задавать ненулевым и не слишком малым, чтобы не учитывать перенаправляющие статьи и статьи-заглушки (например, «Здесь нужно написать о …»)
Кластеризация текстовых документов
Теоретическая часть
Для того чтобы кластеризовать некоторый набор объектов данных, необходимо выбрать меру близости и собственно алгоритм кластеризации. Мера близости это функция определяющая степень похожести двух объектов данных между собой. Эта функция выбирается на основании типов и количества атрибутов у каждого объекта, а также требований к вычислительной сложности. Также при выборе меры близости следует учитывать некоторые особенности набора объектов данных в целом, например, разброс значений которых атрибутов. В задачу алгоритма кластеризации сходит непосредственно распределение объектов данных между кластерами разделением больших кластеров, объединением малых или перераспределением объектов между кластерами, не меняя их количество.
Наиболее популярными и простыми алгоритмами кластеризации является иерархический алгоритм ближайшего соседа и неиерархический k-means.
K-means – один из самых простых с точки зрения вычислительной сложности алгоритмов, также его достоинством является простота восприятия процесса и результата человеком. Центроиды, формирующиеся при кластеризации, могут быть использованы для характеристики кластера, что также способствует лучшему восприятию результата и быстрому извлечению важных знаний о данном наборе. Однако, данный алгоритм имеет серьезный недостаток: набор объектов данных должен четко разбиваться на кластеры. Предъявить такое требование к объектам векторной модели текстовых документов нельзя. Еще одним недостатком является чувствительность алгоритма к выбросами данных. То есть один или несколько объектов данных, имеющих слишком отличающиеся от средних значения некоторых характеристик, сильно сдвигают центроид в свою сторону и делают представление о кластере в целом искаженным. Также имеется недостаток на стадии подготовки данных для кластеризации алгоритмом k-means. Суть его в случайном распределении объектов по заданному количеству кластеров. Этот процесс иногда может способствовать увеличению скорости кластеризации, но вероятность этого уменьшается с возрастанием количества объектов в наборе. Таким образом, при большом наборе этот процесс, занимая некоторое время, не способствует уменьшению времени кластеризации.
Иерархическим алгоритмам не требуется предварительное случайное распределение объектов по кластерам. При использовании подкласса агломеративных алгоритмов, к которому относится алгоритм ближайшего соседа, на стадии подготовки каждый объект данных имеет свой кластер. Составляется матрица попарной близости кластеров. Впоследствии, при каждой итерации цикла кластеризации наиболее похожие на основании матрицы соседства кластеры объединяются в один. Недостатком алгоритма является иногда сложный перерасчет атрибутов новых кластеров, так как для этого необходимо заново вычислять попарную близость имеющихся кластеров с новым с помощью выбранной функции меры близости. Алгоритм ближайшего соседа также имеет те же недостатки, что и k-means, предъявляя требование четкого разделения к набору данных и являясь чувствительным к выбросам данных.
Используемый в реализации алгоритм ROCK (Robust Clustering using Links)[7] является иерархическим алгомеративным алгоритмом, сочетающим в себе достоинства k-means и алгоритма ближайшего соседа, а также решающий их описанные выше недостатки. Основная идея алгоритма заключается во введении каждой паре объектов нового параметра – количество общих соседей (ссылок). Этот параметр получается из матрицы соседства путем выяснения в цикле по каждому объекту, является ли он соседями двух рассматриваемых. Благодаря учету ссылок алгоритм становится нечувствительным к выбросам и не требует четкого разделения объектов на кластеры. Также работая в цикле кластеризации со ссылками, объединяя кластеры, легко получить новые значения параметров ссылок с другими кластерами: для этого достаточно сложить соответствующие значения параметра ссылок двух объединяемых кластеров.
Алгоритм был разработан для кластеризации объектов данных с большим количеством числовых и номинальных атрибутов. Типичными задачами кластеризации алгоритмом ROCK является прогнозирование свойств сложных объектов по неполным наборам атрибутов у некоторых из них. Похожими свойствами обладают и объекты в задаче данной работы. Так как не во всех статьях есть все слова встречающиеся в данном наборе, то при сравнении параметров двух объектов атрибут, отвечающий за частоту употребления определенного слова, можно рассматривать как булевый (то есть частный случай номинального): «встречается» или «не встречается». Таких атрибутов при попарном сравнении будет достаточно много. Оставшиеся атрибуты, имеющиеся у обоих рассматриваемых объектов, сравниваются как числовые. Такой набор атрибутов удовлетворяет требованиям для кластеризации алгоритмом ROCK.
При всех своих достоинствах и решении проблем предшественников алгоритм ROCK имеет один серьезный недостаток. Он заключается в увеличении вычислительной сложности при добавлении нового параметра. Процесс подсчета ссылок является самым долгим во всей кластеризации. По сравнению с алгоритмом ближайшего соседа вычислительная сложность увеличивается в полтора раза. Однако, следует заметить, что подсчет ссылок происходит лишь один раз на этапе подготовки данных, процесс кластеризации занимает значительно меньше времени. В данной работе имеются некоторые средства оптимизации процесса вычисления ссылок, а одним из ключевых направлений дальнейшей разработки является аппроксимация матриц соседства и ссылок, которая позволит значительно уменьшить время вычислений.
Теперь подробнее рассмотрим выбор метрики близости двух объектов данных. Во всех описанных выше алгоритмах для начала нужно выбрать функцию, которая по атрибутам объектов определяет степень их соседства. Одной из популярных функций для сравнения объектов является Евклидово расстояние. Чтобы с помощью нее узнать, насколько два объекта близки, нужно сложить квадраты разности значений соответствующих атрибутов и взять корень. Эта метрика имеет ряд недостатков при использовании в данной задаче. С ростом числа атрибутов у объектов растет и сложность вычислений Евклидова расстояния. Но главным недостатком этой метрики является неправильный учет атрибутов, отсутствующих у одного объекта и имеющихся у другого. Например, есть три объекта данных представленных в виде следующих векторов:
A = (1,0,0,0,0) B = (0,0,0,0,1) C = (1,1,1,1,0)
Вычислив Эвклидово расстояние, получаем:
|A-B|=v2|A-C|=v3 |B-C|= v5
Хотя объекты А и В не имеют общих атрибутов, по данной метрике они ближе чем объекты А и С.
Более правдоподобно мера близости двух объектов будет выглядеть, если использовать коэффициент Жаккарда. Он считается значительно проще Евкидового расстояния и его вычисление интуитивно понятнее для данной задачи. Чтобы вычислить по нему схожесть двух объектов, нужно представить все их атрибуты как точки двух множеств. Эти множества пересекаются в точках, где объекты имеют общие атрибуты. Коэффициент Жаккарда это отношение пересечения данных множеств к их объединению. В случае, когда у обоих объектов имеется атрибут с разными значениями, в числитель прибавляется меньшее из двух, а в знаменатель сумма значений этого атрибута. Для выше описанного примера:
sim(A, B)=0 sim(A, C)=1/5 sim(B, C)=0
Для кластеризации алгоритмом ROCK вовсе не важно, насколько два объекта являются соседями. Для последующего подсчета общих соседей важен сам факт соседства. Поэтому, чтобы использовать коэффициент Жаккарда как метрику близости, нужно задать пороговое значение этого коэффициента. Если для данной пары объектов значение коэффициента больше выбранного порогового, значит, объекты являются соседями.
Рассмотрим более подробно использование ссылок в алгоритме ROCK. Текстовые документы обычно имеют сильный разброс в своих размерах. Это означает, что очень большой документ содержит много атрибутов и, скорее всего, имеет много соседей, в отличие от маленьких документов. Таким образом, при использовании в качестве меры близости количество ссылок, в один кластер могут попасть все большие статьи, имея при этом сильно различную тематику. Чтобы этого избежать, необходимо использовать относительное количество ссылок в качестве меры близости двух объектов. Эта величина характеризуется следующей формулой:
[real num cross links / expected num cross links]
Подсчет количества прогнозируемых ссылок – одна из наиболее важных задач при работе с алгоритмом ROCK. Так как количество ссылок изначально зависит от порогового коэффициента при определении соседей среди объектов набора, размеров кластеров (а вернее от размеров объектов в нем), эти два параметра являются входными данными функции прогнозирования количества ссылок. Также нужна функция такая, что точка, принадлежащая к кластеру размером n, будет иметь n^f(th) в кластере, где th – пороговый коэффициент соседства. Одной из наиболее простых и удачных таких функций является f(th) = 1-th/1+th. Итоговая функция меры близости будет выглядеть так:
[Вывод формулы]
Полученная форума и есть итоговая мера близости, используемая в алгоритме ROCK.
Практическая часть
Работа программы кластеризации начинается с загрузки данных, полученных из программы подготовки текста. Так как работа происходит только с небольшими числовыми данными и благодаря особенностям работы Python с памятью, весь объем подготовленных текстов занимает немного оперативной памяти и может быть полностью в него загружен. Хотя для очень больших (порядка миллиона статей), все векторные представления документов могут не уместиться в оперативной памяти, для данной реализации это действие приемлемо, так как она предназначена для работы с менее крупными наборами. Загрузка производится из двух таблиц: моделей основного текста и моделей заголовков. На странице администрирования кластеризации можно регулировать коэффициент значимости термов в заголовках при определении тематики текста. Также на этом этапе для каждого объекта данных создается свой одиночный кластер, размер которого совпадает с размером объекта данных, который он содержит. Во время загрузки также происходит вычисление среднего размера статьи в векторах. Это будет нужно затем для предсказания количества ссылок. Финальным этапом загрузки является составление модели для каждого документа с учетом веса заголовков.
На следующем этапе происходит выявление соседства объектов данных по правилам, описанным выше. Этот процесс занимает небольшую часть от общего времени кластеризации. Для экономии места и увеличения скорости работы программы матрица соседства записывается в виде списка для каждого объекта данных, содержащего только соседей с бóльшим порядковым номером.
На следующем этапе подготовки к кластеризации происходит вычисление количества общих соседей для каждого объекта, имеющего хотя бы одного соседа. Как было замечено выше, этот процесс имеет наибольшую вычислительную сложность во всем процессе кластеризации – O(3N). Однако, при увеличении порогового коэффициента определяющего соседство, можно значительно уменьшить время работы этого процесса. Таким образом, задачи нахождения нескольких кластеров с наиболее крепко связанными между собой объектам выполняются относительно быстро.
Затем для каждой пары объектов, имеющих хотя бы одного общего соседа, вычисляется мера близости g.
[Дописать щас]
На этом этап подготовки данных завершается.
Далее начинается цикл кластеризации, в каждой итерации которого сливаются в один кластеры с наибольшим значением g. На каждой итерации также происходит проверка условий выхода из цикла. Основным условием выхода является отсутствие ненулевых связей между кластерами. Также пользователь через страницу администрирования кластеризации может задать дополнительные условия выхода, а именно: количество проведенных итераций, общее количество полученных кластеров и получение кластера заданного размера. После выбора двух кластеров с наиболее сильной связью происходит формирование нового кластера, который содержит объекты данных двух сливаемых. Затем происходит подсчет количества общих соседей нового кластера с другими. Если у кластера были общие соседи с одним из сливаемых кластеров, то у этого значения меняется идентификатор принадлежности к кластеру на идентификатор нового кластера. Если у кластера были общие соседи с обоими сливаемыми кластерами, то под соответствующим идентификатором записывается сумма значений. Затем значения ссылок со сливаемыми кластерами удаляются из матрицы ссылок. Далее происходит вычисление g для нового кластера и всех других. После этого новый кластер имеет все необходимые параметры. Вся информация о слитых кластерах окончательно удаляется из памяти.
После выхода из цикла кластеризации происходит формирование отчета с результатами. В базе данных обновляется таблица с индексом статей, куда заносится принадлежность к определенному кластеру. Список кластеров затем доступен на странице статистики расширения MediaWiki.
Результаты работы
При задании различных коэффициентов соседства можно использовать данное расширение в кафедральной базе знаний для следующих целей: поиск одинаковых статей, поиск похожих отчетов по различным работам, поиск материалов по определенной дисциплине и поиск материалов смежных для нескольких дисциплин. Наиболее востребованными являются задачи поиска похожих отчетов (востребовано студентами, использующими отчеты в качестве примера) и поиск смежных материалов различных дисциплин для последующего учета уже имеющихся у студентов знаний.
На данный момент разработка имеет некоторые погрешности при выполнении последней задачи, однако достаточно хорошо справляется с остальными.
Скорость работы во многом зависит от настроек программ, но с наиболее стандартными параметрами для 1500 статей при 128Мб оперативной памяти: подготовка текста занимает 15-20 минут, кластеризация 20-25 минут. При этом большую часть времени кластеризации занимает подготовка данных (построение матрицы ссылок), работа же цикла кластеризации занимает 5-7 минут с условием работы, пока есть ненулевые связи.
Эффективность алгоритма во многом зависит от формулы предсказания количества ссылок. Получение наиболее точной формулы и является основной задачей дальнейших исследований модели. Одним из важных направлений также является улучшение нормализации текстовых документов, оптимизация и улучшение качества стемминга. Также направлениями дальнейших разработок являются: учет сложных текстовых конструкций (формул, кода программ), аппроксимация матриц для уменьшения времени подготовки к кластеризации.
[1] John F. Gantz "A Forecast of Worldwide Information Growth Through 2010" The Expanding Digital Universe. March 2007
[2] Schacht P. "The Collaborative Writing Project", "Using Wiki in Education" 2007
[3] Cao G., Song D., Bruza P. "Suffix Tree Clustering on Post-retrieval Documents Information." The University of Queensland, 2003
[4] G. Salton, A. Wong, and C. S. Yang (1975), "A Vector Space Model for Automatic Indexing," Communications of the ACM, T. 18, № 11, C. 613–620.
[5] Codd, E. F. "Further Normalization of the Data Base Relational Model." Courant Computer Science Symposia Series 6, "Data Base Systems," New York City, May 24th-25th, 1971.
[6] M. F. Porter "An algorithm for suffix stripping" Program. — 1980. — Т. 14. — № 3. — С. 130—137.
[7] Sudipto G., Rajeev R., Kyuseok S. "ROCK: A Robust Clustering Algorithm for Categorical Attributes" Korea Advanced Institute of Science and Technology and Advanced Information Technology Research Center, 2000
