Text Mining Libraries

Один из читателей блога спросил у меня по электронной почте про известные мне библиотеки с реализациями разных алгоритмов IR. В частности его интересовала кластеризация шинглами. Неплохая реализация шинглов на C++ есть в библиотеке ClustBoost.

Вообще хороших библиотек, а тем более open source, не так много. Среди тех с кем мне приходилось сталкиваться можно выделить:

• GATE — как они пишут про себя это "the Eclipse of Natural Language Engineering, the Lucene of Information Extraction, the leading toolkit for Text Mining". С Lucene, конечно, они себя зря сравнивают. Коротко говоря, GATE это более-менее удобная графическая среда, к которой можно плагинами подключить практически любую библиотеку для обработки текста.
  
• ANNIE — распространяется как часть GATE. Включает в себя: токенайзер, sentence splitter, part-of-speech tagger и named entity recogniser. Последний может выделять такие сущности как имена, организации, места, даты, адреса и др. Утверждается что ведутся работы по портированию ANNIE для русского языка.
  
• WEKA — в этой библиотеке реализованы многие алгоритмы классификации плюс есть хорошие визуализаторы результатов. Есть wrapper в GATE.
  
• MinorThird — позволяет работать с аннотированным текстом, используя эти аннотации можно классифицировать документы с помощью множества реализованных алгоритмов (начиная от k-nn, заканчивая SVM и voted perceptron. Что интересно, в MinorThird помимо обычной supervised классификации есть реализации и semi-supervised алгоритмов.
  
• SVM^light — хорошая и быстрая реализация SVM на C. Есть wrapper в GATE.

Буду рад добавлениям в список.

Multiword Features

В ситуациях когда различиях между категориями проявляются не на уровне различных слов, а на уровне сочетаний этих слов, классические классификаторы Байеса могут показывать не очень удовлетворительные результаты. Справиться с этой проблемой можно используя шинглы (shingles) или multiword features.

В общем случае, шинглы — это уникальные последовательности символов одинаковой длины выделенные из документа. Для задач классификации можно рассматривать последовательности не символов, а слов. Например, для документа "a rose is a rose is a rose" шинглами длиной в четыре слова будут: { (a,rose,is,a), (rose,is,a,rose), (is,a,rose,is) }. Построить все шинглы для документа можно за O(w(n-w)), где w — длина шингла. Дальше шинглы используются как обычные слова в классификаторе Байеса, за счет чего заметно вырастает точность, особенно когда мы работаем с иерархической структурой категорий.

К сожалению шинглы нам не помогут в случае, когда слова из характерных сочетаний идут в документах не подряд, а на различном расстоянии друг от друга. В таком случае можно использовать обобщение идеи шинглов: multiword features. Собственно, что это такое уже понятно, весь вопрос в том, как эффективно эффективно найти характерные для категории multiword features. Действительно, наивный алгоритм, который находит все возможные сочетания слов, скорее всего просто не влезет в память. Очевидно, что нам нужны не все возможные сочетания слов, а только наиболее характерные для категории, то есть которые встречаются, например, как минимум в 10% документов. Это позволяет нам последовательно вычислять корреляцию для очередного набора слов и хранить в памяти только удовлетворяющие условию. Тем не менее, временная сложность такого алгоритма все равно будет O(mk), где m — число слов в категории, k — число слов в наборе. Очевидно, что вычислять наборы более чем из двух слов неэффективно, да и, как правило, это не даст большого выигрыша в точности.

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

1. Каждое слово представляется вектором, элементы которого равны нулю или единице, в зависимости от присутствия слова в документе с соответствующим номером.
2. Этот вектор хранится в виде long[], длина массива равна [n / sizeof(long)] + 1, где n — число документов.
3. Вычисление корреляции между двумя документами сводится к последовательному побитовому умножению элементов двух массивов и вычислению числа единиц в результате.

Хороший практический результат на многих задачах может дать совместное использование шинглов длиной в 3-5 слов и 2-word features.