Для реализации описанного выше интерфейса использовалась Python-библиотека для создания 2-D графики и анимации - NodeBox for OpenGL.

3. Экспериментальный анализ алгоритмов бикластеризации

В данной главе представлены экспериментальные результаты сравнения трёх алгоритмов бикластеризации - BBox, GreedyBBox и алгоритма спектрального разложения двудольного графа (Spectral).

3.1 Мемоизация в BBox

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

Таблица 2. Ускорение алгоритма BBox за счёт техники мемоизации

Таблица 2 показывает общее внутренних количество итераций по всем входным строкам, которое потребовалось алгоритму BBox (без мемоизации) для нахождения бикластеров. Столбец «сохранённые итерации» - показывает количество внутренних итераций, которое удалось избежать за счёт мемоизации. В качестве входных данных алгоритму подавались квадратные матрицы размером от 50 до 250 строк и столбцов. Каждый элемент матрицы генерировался с помощью генератора псевдослучайных числе из полуинтервала [0, 1) в случае вещественных матриц и из множества {0, 1} в случае бинарных матриц.

Из таблицы видно, что количество сохранённых итераций много меньше общего числа выполненных итераций. Вдобавок, отношение этих величин падает с ростом размера входной матрицы: для входной матрицы размеров 250x250 сохранённые итерации составляют всего 0.3% от общего числа итераций как для вещественной матрицы, так и для бинарной.

Нужно также заметить, что в результате проведённых экспериментов, количество сохранённых итераций оказалось равным порядку входной матрицы минус один. Это связано с тем, что алгоритм для всех входных строк матрицы сходился к одному и тому же оптимальному бикластеру. При этом «сохранённой» итерацией оказывалась всегда последняя, то есть алгоритму не приходилось проверять, является ли полученный бикластер оптимальным, так как он был уже получен для первой начальной строки и содержался в хеш-множестве. Аналогичная ситуация наблюдалась и для «реальных» данных, то есть матриц релевантности и матриц схожести между ключевыми фразами. Несмотря на то, что для ключевых слов алгоритм находил более одного локально-оптимального бикластера, «сохранёнными» всегда оказывались финальные итерации для различных начальных строк.

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

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

3.2 Сравнение алгоритмов бикластеризации

Сравнение алгоритмов бикластеризации проводилось по двум основным направлениям: скорость работы и общий «вклад» найденных алгоритмами бикластеров в исходную матрицу. Для подсчёта «вклада» использовалась бикластерная модель, предложенная Миркиным и Крамаренко вместе с алгоритмом BBox.

В данной модели матрица «остатков» (residuals) для набора бикластеров и исходной матрицы определяется по следующей формуле:

где - бинарные векторы принадлежности строк к множеству и столбцов к множеству соответственно. Таким образом, для подсчёта элемента матрицы остатков, нужно найти бикластер с наибольшей плотностью, который содержит данный элемент, то есть . Говоря менее формально, мы рассчитываем для каждого элемента исходной матрицы степень его «присутствия» в полученных бикластерах.

Далее, для подсчёта общего «вклада» мы считаем сумму квадратов остатков по всей матрице и делим на сумму квадратов элементов исходной матрицы:

.

1) Время выполнения

Время работы алгоритмов бикластеризации сравнивалось на квадратных входных матрицах разного размера.

Как и в случае с мемоизацией, тестовые матрицы генерировались при помощи генератора случайных чисел.

Таблица 3. Сравнение алгоритмов спектрального разложения и жадного алгоритма Greedy BBox. Время представлено в секундах

В связи с тем, что алгоритм спектральной бикластеризации требует указания количества бикластеров, на которое нужно разбить входную матрицу, в таблице представлены результаты анализа времени работы по выделению 10, 50 и 100 бикластеров данным методом. Из таблицы видно, что время работы жадного алгоритма матрицы растёт намного быстрее времени работы спектрального метода по мере увеличения размера входной. В таблице не приведено время работы алгоритма BBox, так как он значительно проигрывает по скорости конкурентам (обработка матрицы размеров 200x200 занимает около 440 секунд). Также стоит отметить, что алгоритм Greedy BBox работает быстрее на бинарных матрицах, чем на вещественных, чего нельзя с однозначностью сказать про спектральный метод.

Рисунок 2. Время работы алгоритма GreedyBBox в секундах на случайных входных данных

2) «Вклад» бикластеров.

В данном разделе для экспериментирования с алгоритмами для бикластерного анализа использовалась коллекция аннотаций к научным статьям, содержащая 2971 аннотацию. Данная коллекция была получена при помощи выгрузки аннотаций из электронной библиотеки IEEE Xplore. Для поиска данных аннотаций в электронной библиотеке использовался текстовый запрос “cluster analysis”, поэтому данная коллекция связана с темой «кластерного анализа». Ключевые словосочетания из этой коллекции были выделены по гибридному алгоритму (модифицированный TextRank в сочетании с частотным анализом), представленному во второй главе.

Также для этой коллекции были загружены ключевые слова, предоставляемые самой библиотекой IEEE Xplore, включая термины, использованные для индексирования в базе данных Inspec (удалось получить для 2622 статей), и авторские ключевые слова (удалось получить для 1777 статей).

Таблица 4. Сравнение алгоритмов по общему «вкладу»

Для составления таблицы 4 было проведено 5 испытаний с различными параметрами:

1) Анализ матрицы схожести между ключевыми фразами, составленной по метрике релевантности Okapi BM25 и пороговым значением релевантности равным 0,15;

2) Анализ матрицы схожести между ключевыми фразами, составленной по методу АСД и пороговым значением релевантности равным 0,2;

3) Анализ матрицы схожести между ключевыми фразами, полученными из библиотеки IEEE Xplore для коллекции статей по кластерному анализу. Использовались фразы из тезауруса базы данных Inspec - controlled Inpsec terms. Здесь не указано пороговое значение, так как составленные вектора релевантности являются бинарными (фраза релевантна для статьи, если так указано в базе данных Inspec);

4) Анализ матрицы релевантности, составленной по метрике Okapi BM25;

5) Анализ бинарной матрицы релевантности для авторских ключевых фраз.

Из таблицы 4 можно видеть, что разработанный жадный алгоритм бикластеризации и алгоритм BBox сильно превосходят по точности («вкладу») алгоритм спектрального разложения. В таблице также представлены результаты для бикластеров, найденных по алгоритму GreedyBBox и отфильтрованных на основе схожести между собой (см. раздел 2.5.). Можно видеть, что фильтрация бикластеров не только не ухудшила показателей «вклада», но даже улучшила его в некоторых случаях - фильтрация производилась при пороге схожести по коэффициенту Жаккарда равном 0,7. Это связано с тем, что после фильтрации в итоговой матрице остатков получается меньшее количество отрицательных элементов, чем при учёте всех бикластеров.

Что касается сравнения алгоритмов BBox и GreedyBBox, таблица 4 показывает неоднозначные результаты: в двух случаях BBox заметно опережает жадный алгоритм, в одном лучший показатель у алгоритма GreedyBBox, а в двух других показатели примерно равны. Эти результаты отражают различие в подходах к выделению бикластеров: BBox находит только локально-оптимальные бикластеры, тогда как GreedyBBox находит новые бикластеры практически на каждой итерации, но многие из них могут сильно отличаться от оптимальных, а значит, скорее всего, вносят малый «вклад» в общий результат. Всё же, полученный результат показывает, что новый жадный алгоритм способен конкурировать с BBox, при этом значительно превосходя его по скорости работы.

4. Программная реализация

4.1 Описание программы

Описанные во второй главе алгоритмы и методы собраны и реализованы в программном модуле Bianalyzer для языка Python. Данный модуль может быть загружен из репозитория на портале GitHub. Установка модуля на машину требует предварительной установки среды исполнения Python. Сам модуль может быть установлен командой $ python setup.py install,

выполненной в корневой директории загруженного с GitHub модуля. После установки модуля Bianalyzer, можно приступить к его использованию внутри Python-кода при помощи команды “import bianalyzer”. Данный программный продукт распространяется под свободной лицензией MIT и может быть использован в целях анализа текстовых данных.

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

В дополнение к программному модулю нами был разработан Веб-интерфейс для демонстрации работы реализованных алгоритмов и удобного представления результатов анализа - бикластеров. Данный Веб-интерфейс может быть найден по ссылке: http://54.68.4.14/. При разработке Веб-интерфейса использовался фреймворк для языка Python - Flask. В качестве базы данных для хранения данных для анализа, использовалась система MySQL, а для взаимодействия с базой из Python-кода использовался фреймворк SQLAlchemy.

4.2 Архитектура программного модуля

Python-модуль Bianalyzer разбит на следующие основные пакеты:

· abstracts - предоставляет методы для загрузки аннотаций к научным статьям из электронных библиотек IEEE Xplore и Springer;

· keywords - предоставляет функции по выделению ключевых слов и словосочетаний из набора текстов. Сюда входит метод выделения ключевых фраз по модифицированному или гибридному алгоритму TextRank и метод выделения ключевых слов на основе их частоты встречаемости в текстах;

· relevance - предоставляет методы для подсчёта матриц релевантности фраза/текст на основе коллекции текстов, набора ключевых фраз и метрики релевантности. Также пакет предоставляет метод вычисления матрицы схожести между ключевыми фразами по заданной матрице релевантности фраза/текст и пороговому значению релевантности;

· biclustering - предоставляет методы для бикластерного анализа матриц. В данном пакете реализовано три алгоритма бикластеризации - BBox, GreedyBBox и SpectralGraphCoclustering (алгоритм Диллона). В дополнение, пакет предоставляет метод подсчёта матрицы остатков по заданной входной матрице и полученным бикластерам (что может использоваться для формальной оценки полученных результатов) и метод фильтрации биакластеров на основе их схожести между собой по коэффициенту Жаккарда;

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

· Для использования этого модуля необходимо дополнительно установить Python-пакет nodebox-opengl. Установка этого пакета может быть произведена с помощью пакетного менеджера Python - pip - командой pip install nodebox-opengl.

Структура классов алгоритмов для бикластерного анализа матриц имеет вид, соответствующий рисунку 3.

Рисунок 3. Структура классов для алгоритмов бикластеризации

Стоит отметить, что точки входа для алгоритмов BBox и GreedyBBox отличаются от алгоритма SpectralGraphCoclustering. Если в первых двух поиск бикластеров происходит итеративно по всем строкам матрицы (метод find_biclusters), то спектральный алгоритм устроен иначе и требует задания пользователем количества бикластеров, которое необходимо найти (метод find_disjoint_biclusters).

4.3 Иллюстрация работы программы

1) Работа с программным модулем Bianalyzer

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

1. Загрузка аннотаций к научным статьям из электронной библиотеки;

2. Получение набора ключевых словосочетаний по приобретённой коллекции и модифицированному методу TextRank;

3. Подсчёт матрицы релевантности по загруженным аннотациям и полученному набору фраз (в качестве метрики, например, используется Okapi BM25);

4. Вычисление матрицы схожести между ключевыми фразами на основе матрицы релевантности;

5. Бикластеризация матрицы схожести ключевых фраз и визуализация полученных бикластеров в виде графа.

Такая последовательность действий может быть выполнена при помощи следующего небольшого Python-скрипта, использующего модуль Bianalyzer:

from bianalyzer.keywords import extract_keywords_via_textrank

from bianalyzer.abstracts import download_abstracts

from bianalyzer import BianalyzerText

from bianalyzer.relevance import construct_relevance_matrix, construct_similarity_matrix, RelevanceMetric

from bianalyzer.biclustering import get_keyword_biclusters, GreedyBBox

if __name__ == "__main__":

articles = download_abstracts('IEEE', 'cluster analysis', 3000)

bianalyzer_texts = [BianalyzerText(article.abstract_text) for article

in articles]

keywords = extract_keywords_via_textrank(bianalyzer_texts, keyword_limit=300,

concatenation_occurrences=3)

relevance_matrix = construct_relevance_matrix(keywords, bianalyzer_texts,

RelevanceMetric.bm25)

similarity_matrix = construct_similarity_matrix(relevance_matrix, 0.15)

keyword_biclusters = get_keyword_biclusters(similarity_matrix, GreedyBBox)

В результате исполнения этого скрипта пользователь увидит графическое окно, как представлено на рисунке 4.

Рисунок 4. Граф связей между ключевыми фразами, полученный на основе бикластеров ключевых фраз

2) Работа с Веб-интерфесом.

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

Для запуска новой работы по бикластеризации пользователю необходимо перейти на вкладку “Biclustering” и указать необходимые параметры работы, как-то:

· тип работы - бикластерный анализ матрицы релевантности фраза/текст или анализ матрицы схожести между фразами;

· коллекция текстов для анализа - выбирается из списка доступных вариантов, для которых указывается источник (IEEE или Springer), тематика коллекции и количество текстов в коллекции;

· источник ключевых фраз - это может быть искусственно составленный список словосочетаний из области кластерного анализа, ключевые словосочетания, выделенные из выбранной коллекции на основе модифицированного метода TextRank или гибридного метода (модифицированный TextRank с совместно с частотной фильтрацией); или ключевые словосочетания, предоставляемые электронной библиотекой (доступно только для коллекций текстов из библиотеки IEEE Xplore);

· метрика релевантности - TF-IDF, Okapi BM25, метод АСД, частота вхождения или нормализованная частота вхождений (делённая на длину текста без учёта стоп-слов);

· пороговое значение релевантности (только при анализе матрицы схожести) - число из полуинтервала ;

· алгоритм бикластеризации - Greedy BBox, BBox или Spectral Graph Coclustering;

· максимальное число бикластеров для отображения;

· параметр л0 - используется для управления средним размером получаемых бикластеров (этот параметр вычитается из всех элементов матрицы до начала работы).

Рисунок 5. Ход работы по бикластеризации текстовых данных

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

Рисунок 6. Полученные бикластеры ключевых фраз

Заключение

кластеризация иерархический таксономия

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

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

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

В дополнение, мы представили новый жадный алгоритм GreedyBBox, основанный на алгоритме BBox, представленным Миркины и Крамаренко в 2012 году. Если алгоритм BBox имеет экспоненциальную сложность, то GreedyBBox обладает полиномиальной сложностью, что делает его использование более выгодным при анализе матриц большого размера. Нами было также показано, что новый алгоритм сравним по «качеству» находимых им бикластеров с алгоритмом BBox, а в некоторых экспериментах даже показывает лучший результат.

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

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

Литература

1. Aggarwal C. Mining text data / Charu C. Aggarwal, Checng X. Zha. - USA: Springer Publisher Company, 2012 - 522с.

2. Agrawal S. Dbxplorer: a system for keyword-based search over relational databases / S. Agrawal, S. Chaudhuri, and G. Das // Proceeding of the 18th Intl. Conference on Data Engineering. - IEEE Computer Society - 2002 - С. 5-16.

3. Banerjee A.A generalized maximum entropy approach to Bregman co-clustering and matrix approximation / A. Banerjee, I. Dhillon, J. Ghosh, S. Merugu, D. Modha // Journal of Machine Learning Research - 2007 - vol. 8 - С. 1919-1986.

4. Bekkerman R. Distributional word clusters vs. Words for text categorization / R. Bekkerman, R. El-Yaniv, N. Tishby, Y. Winter // Journal of Machine Learning Research - 2003 - vol. 3 - С. 1183-1208.

5. Crouch C. A cluster-based approach to thesaurus construction. / C.J. Crouch // Proceedings of the 11th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval - New York, NY, USA: ACM - 1988 - С. 309-320.

6. Dhillon I. Co-clustering documents and words using bipartite spectral graph partitioning / I. Dhillon // Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining - New York, NY, USA: ACM - 2001 - С. 269-274.

7. Hulth A. Improved automatic keyword extraction given more linguistic knowledge / A. Hulth // Proceedings of the 2003 Conference on Empirical Methods in Natural Language Processing -Association for Computational Linguistics - 2004 - С. 216-223.

Размещено на Allbest.ru