Оценка эффективности метода параллельной реализации процесса кластеризации электронных документов на основе алгоритма FRiS-Cluster♣ © В.Б. Барахнин, Д.А. Ткачев Институт вычислительных технологий СО РАН, Новосибирский государственный университет bar@ict.nsc.ru, relk-tda@yandex.ru Аннотация схожей с документом характеристикой, которая, вполне возможно, имеет довольно низкий В работе представлен вариант приоритет. С другой стороны, периодическое параллельного выполнения некоторых выполнение процесса разбиения на кластеры этапов кластеризации документов с является задачей, сложность которой возрастает с использование алгоритма FRiS-Cluster. ростом количества обрабатываемых документов. Приведены количественные оценки В настоящее время большой интерес времени выполнения процесса, наглядно представляет использование в процессе решения демонстрирующие преимущества задач кластеризации вычислительных систем, внедрения параллельной реализации на состоящих из множества вычислительных узлов. различных этапах обработки: при Но, очевидно, при использовании таких систем предварительном анализе документов, необходимо иметь версии алгоритмов, которые включающем вычисление мер схожести, а могут эффективно работать на системах с также частично при выполнении параллельной архитектурой. непосредственно процесса кластеризации. Принцип многопроцессорной обработки, как способ повышения общей эффективности можно 1. Введение описать следующим образом: распределить вычислительный процесс на N вычислительных Интенсивный рост объема генерируемой узлов, осуществляющих отдельные фрагменты информации, представленной в электронном виде, в вычислительного алгоритма. Хорошо том числе и научных документов, делает распараллеливаемыми являются вычислительные актуальным решение задачи кластеризации задачи с многократно повторяемыми вычислениями документов, т.е. разбиения множества документов при вариациях некоторых начальных условий для на заранее неизвестное количество подмножеств каждого цикла вычислений. При этом желательно, различных тематик. При вовлечении в процесс чтобы в таких задачах параметры последующих нового документа необходимо выполнить его циклов вычислений имели бы минимально отнесение к одной из существующих групп, либо выраженную зависимость от результатов создать новую, где добавляемый документ будет предыдущих циклов. являться центроидом. Добавление нового документа Алгоритмы, которые используются в настоящее не является задачей с большой вычислительной время для задач кластеризации и категоризации сложностью при известных метриках, на основе документов, являются последовательными и которых выполняется расчет меры сходства используют имеющиеся вычислительные ресурсы документа с документами из групп известных далеко не в полную мощность. В них присутствуют тематик. Но данный способ вовлечения документов следующие ограничения, не позволяющие имеет свои недостатки: нельзя бесконечно долго выполнять процесс обработки данных в несколько добавлять новые элементы без учета параметров вычислительных потоков. Во-первых, строгая всех документов, имеющихся в разделяемой последовательность выполняемых операций и выборке. При полной рекластеризации имеющихся обязательное завершение предыдущего логического документов удается избежать ложного отнесения этапа обработки до начала последующего. Во- нового материала к уже сформированной группе, вторых, все вычисления производятся на основе данных, полученных при анализе всего массива обрабатываемых документов, что, в свою очередь, Труды 13й Всероссийской научной конференции «Электронные библиотеки: перспективные методы и довольно сильно усложняет реализацию, а также технологии, электронные коллекции» - RCDL’2011, повышает накладные расходы, связанные с Воронеж, Россия, 2011. передачей информации между узлами системы. 184 2. Цели и задачи пределах от +1 до −1. Если контрольный объект Z совпадает с объектом a, то Ra = 0 и F(a) = 1, а Цель работы заключается в создании F(b) = −1. При расстояниях Ra = Rb значения математического обеспечения и на его основе F(a) = F(b) = 0, что указывает на границу между вычислительного комплекса, обеспечивающего образами. При использовании алгоритма FRiS- решение задачи кластеризации входящего Cluster на его первых шагах все N объектов множества документов при помощи алгоритма заданного множества A принадлежат одному FRiS-Cluster, на основе функции конкурентного кластеру. сходства. Процесс разбиения должен быть разбит на В связи с этим вводится конкурирующее этапы, которые будут эффективно выполняться множество из виртуальных объектов, отстоящих от параллельно на N вычислительных узлах системы. каждого объекта множества на расстояние R*. Основные задачи работы можно сформулировать Произвольный объект Mi множества A назначается следующим образом: центром первого кластера, оцениваются расстояния 1. Реализация варианта алгоритма кластеризации Rj до него от всех остальных объектов Mj и FRiS-Cluster с возможностью его выполнения определяются значения функции параллельно на некотором количестве F(i) = (R* − Rj )/(R* + Rj). вычислительных узлов. Вычисляется сумма значений функций сходства 2. Оценка эффективности реализации, Fs всех объектов первого кластера со своим показывающая, в какой мере данный метод дает центром. Затем в качестве центра второго кластера прирост производительности, т.е. уменьшение выбирается объект, набравший наибольшее времени выполнения процесса, в зависимости от значение Fs в конкуренции с центром первого добавляемого количества вычислительных узлов. кластера. Процесс увеличения числа кластеров k 3. Тестирование методики на множестве останавливается, когда достигается первый научных статей, находящихся в рамках узкой локальный максимум функции Fs(k), либо специализированной тематики. достигнуто максимальное количество кластеров, 4. Создание интерфейса для работы с которое задается исходным параметром [1, 2]. предложенным комплексом в интерактивном режиме, что обеспечит решение практических задач, а также позволит выполнять дальнейшие 4. Вычисление меры сходства исследования на реальной выборке большого В качестве шкал для определения меры сходства объема при оценивании как качества процесса между двумя документами можно использовать разделения на кластеры, так и скорости выполнения атрибуты библиографического описания данных данного процесса. документов (метаданные): авторы, издание, аннотация, предопределенные ключевые слова. Но 3. Алгоритм кластеризации даже такие структурированные документы, как научные статьи, не всегда имеют определенный В качестве алгоритма, на основе которого набор метаданных [3]. Наиболее точно отражают выполняется разработка параллельной реализации тематику материала такие характеристики, как методики кластеризации документов выбран ключевые слова и ключевые выражения, алгоритм FRiS-Cluster, автором которого является полученные из основного текста документа. Это Н.Г.Загоруйко В основе данного алгоритма влечет за собой проблемы, связанные с находится функция конкурентного сходства или морфологическим анализом содержания документа FRiS-функция – мера сходства двух объектов, для определения списка ключевых одиночных слов вычисляемая относительно некоторого иного и составных многословных ключевых выражений, объекта [1, 2]. наиболее точно описывающих действительную FRiS-функция, в отличие от других тематику документа. Причем данный анализ должен существующих мер сходства, позволяет не просто производиться без априорного знания тематики оценивать понятия «далеко» или «близко», «похож» материала и, соответственно, без использования или «не похож», но и давать количественную предметных тезаурусов и словарей словоформ для оценку схожести. Такой подход дает возможность них. учитывать большее число факторов при Ввиду того, что в русском языке имена классификации. Исследования показали, что FRiS- существительные и прилагательные при склонении функция хорошо имитирует человеческий механизм изменяют свою форму, разработка эффективного восприятия сходства и различия. Это позволяет алгоритма автоматизации извлечения ключевых использовать ее как базовый элемент для различных слов является нетривиальной задачей, так как типов задач, включая задачи кластеризации необходимо учитывать и те случаи, когда слова, документов. образующие термин (т.е. ключевое слово), Методику кластеризации можно описать находятся не только в именительном, но и в следующим образом. Если расстояния от объекта Z косвенных падежах. до двух ближайших объектов a и b равны Ra и Rb , Для решения этой задачи мы опирались на то сходство Z с объектом a равно морфологический анализ текстов и производили F(a) = (Rb − Ra)/(Ra + Rb). Значения F меняются в 185 выделение ключевых словосочетаний по коромантийный 7 морфологическим шаблонам с использованием оболочка программного продукта компании Яндекс (http://company.yandex.ru/technology/mystem/), надрифтовой 6 который является бесплатным для некоммерческих депрессия целей. При фильтрации и разборе производился земной кора 6 отсев стоп-слов. Ключевые словосочетания отбираются по морфологическим шаблонам с нефтегазоносный 5 учетом словоформ языка [4, 5]. Подробно методика бассейн выделения ключевых слов и ключевых глубинный 5 словосочетаний описана в статье [6]. Для строение демонстрации эффективности работы методики выделения значимой информации из текстовых переходный 4 документов в таблице 1 приведены результаты комплекс работы по одной из статей экспериментальных бассейн земля 4 данных: Астафьев Д.А. «Общие и индивидуальные особенности эволюции, регионального и столбчатый тело 3 глубинного строения осадочных и нефтегазоносных размещение зона 3 бассейнов Земли». Бассейн 19 Как видим из приведенных данных, качество анализа содержания документа находится на Чехол 16 хорошем уровне. Список значащих слов и Строение 14 выражений достаточно точно описывает тематику анализируемого документа. Кроме того, с помощью Зона 14 фильтрации в список не попадают не значащие стоп формирование 11 слова, которые могут существенно ухудшить качество оценки меры сходства между Земля 10 документами. Модель 9 Также на основе сделанных ранее экспериментов можно утверждать, что смешанный критерий сходства документов, вычисленный на основе оправдана цель ускорения обработки. В нашем данных о ключевых словах и словосочетаниях, случае можно выделить следующие этапы работы: является оптимальным для решения задач 1. Сбор и загрузка исходных данных. кластеризации документов заранее неизвестной Данное действие зависит от источника данных. Это тематики. На основе анализа содержания могут быть данные в текстовых форматах, хорошо вычислялась мера сходства m между каждого поддающиеся обработке и загрузке, импорт из документа с каждым, которая может принимать внешних веб-ресурсов, который зависит от значение в интервале от 0 до 1. Причем, значение производительности внешнего веб-сервера а также меры равняется 0 при полном отличии документов и от пропускной способности сети, либо импорт из равняется 1, при полном их сходстве. В алгоритме форматов, обработка которых имеет некоторую FRiS-Cluster с помощью данной меры специфику, например pdf. Оценивать трудоемкость производилось вычисление расстояния между данного действия нужно в каждом конкретном документами, которое вычислялось как (1 — m). случае. В данной работе не использовалась Иными словами, чем меньше мера сходства между параллельная реализация на этом этапе. сравниваемыми документами, тем на большем 2. Подготовительный этап. Включает в себя расстоянии они находятся. первичную обработку документов. В нашем случае сюда входят процессы выделения ключевых термов и ключевых словосочетаний из текста документов, а 5. Использование параллельности в также, вычисление меры сходства каждого реализации документа с каждым. На этом этапе внедрение При большом количестве обрабатываемых параллельной обработки может дать существенный документов время выполнения процесса выигрыш в производительности. Причем действия кластеризации очень сильно растет и вполне по анализу содержания являются независимыми Таблица 1. Пример полученных ключевых слов друг от друга и не требуют наличия полной и словосочетаний. информации на всех вычислительных узлах. 3. Процесс кластеризации. Исходя из Ключевое Ключевое Количество методики работы алгоритма FRiS-Cluster, можно слово словосочетание вхождений сделать вывод, что самым сложным осадочный чехол 16 вычислительным процессом является обход всех объектов выборки и проверка каждого на роль осадочный 8 столпа. Понятно, что данный процесс может бассейн 186 хорошо выполнять параллельно, хотя и требует области, так как обрабатываемые материалы не наличия информации о расстояниях между имеют кодов принадлежности к уровням того или объектами на всех вычислительных узлах. иного классификатора. Неэксперту трудно 4. Визуализация результата. Является произвести точную оценку корректности разбиения вспомогательным действием, облегчающим работу даже после ознакомления с заголовками и с исходными данными и полученными кластерами. короткими аннотациями статей. Не требуется больших вычислительных мощностей Измерение времени выполнения выполнялось для работы, независимо от количества документов в следующим образом. Были произведены измерения выборке. Оптимизация работы на данном этапе времени процессов подготовки данных (анализ достигается оптимизацией на уровне хранения содержания и вычисление мер близости) и данных, т.е. на уровне сервера базы данных. непосредственно кластеризации для 10, 20 и 30 Исходя из вышеизложенного описания, для формируемых кластеров на одном вычислительном использования параллельной реализации подходят узле и на нескольких вычислительных узлах для этап подготовки данных и часть действий этапа параллельной реализации. Причем структура непосредственной кластеризации. вычислительной сети при выполнении измерений параллельной реализации алгоритма не была 6. Вычислительные эксперименты однородной и состояла из трех рабочих станций различной конфигурации (в том числе В качестве исходных данных для выполнения отличающихся производительностью), связанных в анализа и кластеризации использовались материалы единую сеть. Понятно, что данная сеть не может трудов международной конференции «Современное быть бесконечно расширена, для ускорения состояние наук о Земле», посвященной памяти процесса, так как накладные расходы, связанные с Виктора Ефимовича Хаина, проходящей 1-4 передачей информации будут расти с ростом февраля 2011 года в Москве. Исходная выборка количества вычислительных узлов. включает в себя 488 документов. Выбор исходных Результаты измерения времени выполнения данных обусловлен двумя причинами. Во-первых, последовательной однопоточной реализации проверить работу методики выделения ключевых приведены в таблице 2, а параллельной реализации, термов из текстов геологической тематики без выполняемой на трех вычислительных узлах, в использования тезауруса предметной области. таблице 3. Данная область знаний достаточно сильно На рис. 4 наглядно представлена зависимость насыщена специфическими терминами и времени выполнения процесса кластеризации в определениями, проблемы с анализом которых зависимости от количества вычислительных узлов, потенциально могли выявиться в процессе работы. а также итогового количества кластеров. Во-вторых, все документы находятся в рамках Так как разбиение выборки производилась без одной, уже достаточно узкой тематики, и учета производительности каждого из дальнейшее их разбиение вызывает сложности, при вычислительных узлов, сложилась ситуация, что использовании мер сходимости, основанных только время выполнения не может быть быстрее, чем на библиографических описаниях, либо заголовках обработка 1/N части выборки на самом медленном документов. узле. Тем не менее, приведенные данные наглядно В первую очередь, производилась разбивка демонстрируют целесообразность использования исходного множества на установленное количество параллельной реализации различных стадий кластеров — на 10, 20, 30. Этот параметр обработки данных в процессе кластеризации. (количество результирующих кластеров) является опциональным в алгоритме работы, и 7. Заключение устанавливается перед началом процесса кластеризации. На рис. 1−3 изображено Реализация алгоритма выполнялась в рамках распределение документов по результирующим навигационной системы, которая упрощает работу кластерам. по добавлению исходных документов и дальнейшей Как видно из представленных графиков, навигации по ним, по итоговым кластерам. Поиск несмотря на очевидную близость документов документов через пользовательских интерфейс внутри узкой тематики, алгоритм успешно возможен по полному тексту статьи, по ключевым справился с разбиением выборки на части. Кластер словам или словосочетаниям, по схожести с номером центроида, равным 0, включает в себя просматриваемой статьи с другими документами, на документы, которые не удалось отнести ни к одной основе меры сходства. Вид навигации по ключевым из формируемых групп. Количество таких словам можно увидеть на рис 5. Для удобства и документов, в зависимости от количества кластеров, понимания наиболее смежных ключевых слов варьируется в интервале 7,3% − 12,7%, что является размер шрифта становится больше с ростом приемлемым для работы алгоритмов кластеризации. количества вхождений терма в документах Разумеется, наиболее точно оценить качество обрабатываемой выборки. разбиения выборки настолько узкой тематики возможно только с помощью эксперта в предметной 187 80 70 Количество документов 60 50 40 30 20 10 0 236 0 4 391 418 114 364 297 153 245 Номер центроида Рис. 1. Количество документов в результирующих кластерах, 10 кластеров. 60 50 Количество документов 40 30 20 10 0 4 0 418 236 114 364 391 319 297 10 153 245 432 435 375 81 148 25 342 62 Номер центроида Рис. 2. Количество документов в результирующих кластерах, 20 кластеров. 40 35 Количество документов 30 25 20 15 10 5 0 4 114 391 10 245 81 435 432 319 227 375 196 148 239 62 0 236 418 151 153 297 367 364 395 30 454 25 51 411 342 Номер центроида Рис. 3. Количество документов в результирующих кластерах, 30 кластеров. 188 Таблица 2. Время последовательного выполнения процесса. Количество кластеров 10 20 30 Предварительный анализ данных 290 290 290 Подбор столпов 31 сек. 96 сек. 200 сек. Итоговое уточнение столпов 8 сек. 13 сек. 19 сек. Итоговое время 329 399 509 Таблица 3. Время параллельного выполнения процесса. Количество кластеров 10 20 30 Предварительный анализ данных 99 99 99 Подбор столпов 11 сек. 33 сек. 68 сек. Итоговое уточнение столпов 8 сек. 13 сек. 19 сек. Итоговое время 118 145 186 600 509 500 время выполнения, сек. 399 400 329 300 1 поток 186 3 потока 200 145 118 100 0 10 20 30 количество кластеров Рис. 4. График зависимости времени выполнения от количества вычислительных узлов Рис. 5. Вид навигационной системы 189 Предложенная методика автоматической documents using the algorithm FRiS-Cluster. We give кластеризации документов в электронном виде quantitative values of time the process takes to позволяет выполнять процесс обработки на demonstrate the benefits of implementing the parallel системах, состоящих из более чем одного implementation of various stages of processing: a вычислительного узла. В работе приводятся preliminary analysis of documents, which includes количественные величины оценок времени calculation of similarity measures, and partly in the выполнения при различных исходных данных. performance of the clustering process itself. Оценка эффективности процесса при использовании параллельной реализации алгоритма ♣ FRiS-Cluster на основе функции конкурентного Работа выполнена при частичной поддержке РФФИ сходства, по сравнению с классическим линейным (проекты 09-07-00277, 10-07-00302), президентской методом интеллектуальной обработки данных, программы «Ведущие научные школы РФ» (грант НШ 6068.2010.9) и интеграционных проектов СО РАН. демонстрирует неоспоримый выигрыш в производительности, даже несмотря на то, что не все этапы обработки данных в процессе кластеризации могут выполняться параллельно на наборе вычислительных узлов. Литература [1] Борисова И.А., Загоруйко Н.Г. Функции конкурентного сходства в задаче таксономии // Материалы Всероссийской конференции с международным участием “Знания - Онтологии –Теории» (ЗОНТ-07). Новосибирск, 2007. – Т. 2. – С. 67-76. [2] Борисова И. А., Загоруйко Н. Г. Использование FRiS-функций для решения задачи SDX // International Conference «Classification, Forecasting, Data Mining» CFDM 2009, Varna, Bulgaria, June-July 2009. – P. 110-116. [3] Барахнин В.Б., Нехаева В.А., Федотов А.М. О задании меры сходства для кластеризации текстовых документов // Вестник НГУ. Серия: Информационные технологии. – 2008. – Т. 6. – Вып. 1. – С. 3-9. [4] Шаров С. А. Частотный словарь русского языка // Электронный ресурс http://www.artint.ru/projects/frqlist.asp. [5] Киселев М. Метод кластеризации текстов, основанный на попарной близости термов // В: Сборник работ участников конкурса «Интернет- математика 2007». Екатеринбург: Изд-во Уральского университета, 2007. – С. 74-83. [6] Барахнин В.Б., Ткачев Д.А. Кластеризация текстовых документов на основе составных ключевых термов // Вестник НГУ. Сер.: Информационные технологии. – 2010. – Т. 8. – Вып.: 2. – С. 5-14. Evaluating the Effectiveness of the Method of the Parallel Implementation of the Process of Clustering Text Documents on the Basis of the Algorithm FRiS-Cluster © V.B. Barakhnin, D.A. Tkachev This paper presents a variant of the parallel execution of certain phases of the clustering of 190