Реализация параллельного выполнения алгоритма FCM-кластеризации

^ № 2(20) 2009 А. А. Островский

Реализация параллельного выполнения алгоритма РСМ-кластеризации

Огромные объемы информации зачастую провоцируют немалое количество объектов, выдаваемых по запросу пользователя. Однако в большинстве случаев информацию можно сделать более доступной, если разбить ее источники на тематические группы. Такой процесс группировки данных осуществляется с помощью кластеризации. Рассмотрим один из подобных методов — ГОИ и его модификацию для параллельного выполнения.

Алгоритм FCM

Целью FCM (Fuzzy Classifier Means) — алгоритма кластеризации — является автоматическая классификация множества объектов, которые задаются векторами признаков в пространстве признаков. Другими словами, такой алгоритм определяет кластеры и соответственно классифицирует объекты. Кластеры представляются нечеткими множествами, и, кроме того, границы между кластерами также являются нечеткими.

Алгоритм FCM предполагает, что объекты принадлежат всем кластерам, причем с определенной функцией принадлежности. Степень принадлежности определяется расстоянием от объекта до соответствующего кластерного центра. По данному алгоритму итерационно вычисляются центры кластеров и новые степени принадлежности объектов.

Алгоритм основан на минимизации целевой функции:

С N

i=1У='

где N — количество документов; С— количество кластеров; и-ц — степень принадлежности объекта / кластеру у;

т — любое действительное число, большее 1;

х, — /-й объект набора объектов; с] — у-й кластер набора кластеров;

||х, -с,-1|— норма, характеризующая расстояние от центра кластера у до объекта /.

Объектами кластеризации являются электронные текстовые документы. Задачей РСМ-алгоритма является разбиение этого набора на заданное количество кластеров. Для каждого документа составлен частотный портрет входящих в него значимых терминов. Эти частотные портреты и являются векторами признаков объектов (электронных документов) кластеризации.

Алгоритм нечеткой кластеризации выполняется по шагам.

Шаг 1. Инициализация

Задаются параметры кластеризации и инициализируется первоначальная матрица принадлежности электронных документов кластерам. Выбираются значения следующих параметров:

• экспоненциальный вес (т);

• мера расстояний — ||х, —С;||. Мера расстояний характеризует степень близости документа кластеру. Как правило, выбирается евклидова норма:

х;

и=1

где q — количество значимых термов набора документов;

х]— количество терма} в /-м документе; — значение, соответствующее терму

j в /с-м кластере;

101

№2(20)2009

• уровень точности е;

• количество итераций алгоритма.

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

Шаг 2. Вычисление центров кластеров

Каждому у-му терму всех документов ставится в соответствие действительное число, вычисляемое следующим образом:

Уит -х,

¿—I ч 1

_ ;=1_

N '

/=1

где с]— значениеу-го терма кластера; N — количество документов; х, — значениеу-го терма /-го документа; и-д— степень принадлежности документа / кластеру у.

Шаг 3. Формирование новой матрицы принадлежности

Новая матрица принадлежности формируется с учетом вычисленных на предыдущем шаге центров кластеров:

1

Е /=1

\х> —С/1

2 ' т-1

где и,?— степень принадлежности объекта /

кластеру у;

с]— вектор центрау-го кластера;

с, — вектор центра /-го кластера.

При этом, если для некоторого кластера) и некоторого объекта/,||х, — с] || = 0, то полагаем, что степень принадлежности и,? равна единице, а для всех остальных кластеров степень принадлежности этого документа равна нулю.

Шаг 4. Вычисление целевой функции

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

зация завершена. В противном случае переходим ко второму шагу алгоритма.

Примерная оценка сложности алгоритма

Для обоснования распараллеливания алгоритма выполним примерную оценку его временной сложности.

Если записать структуру циклов для выполнения этапа вычисления центров кластеров по формуле (3) псевдокодом, получим:

Для каждого кластера!

Для каждого терма кластера!

Для каждого объекта!

}

}

}

Время выполнения линейно зависит от количества кластеров, количества термов и количества объектов. Для разбиения массива данных из 100 документов, 10ОО уникальных термов на 10 кластеров потребуется 10-1 ООО• 100 =1 • 10б ите-раций. Для разбиения на 15 кластеров для этого же набора объектов потребуется уже 15 • 1000 • 100 = 1,5 • 10б. Количество итераций возрастает линейно.

Структура циклов для этапа вычисления матрицы принадлежности по формуле (4):

Для каждого объекта {

Для каждого кластера {

Для каждого кластера {

Для каждого терма{

}

}

}

}

Как видно из этого кода, время его выполнения линейно зависит от количества объектов и термов и имеет квадратичную зависимость от числа кластеров. Для выполнения этого этапа необходимы вложенные циклы до третьего уровня. Таким образом, например, для разбиения массива данных из 100 документов, 1000 уникальных термов на 10 кластеров потребуется 1000 • 10 • 10 • 100= 1 • 107

102

№2(20)2009

итераций. Для разбиения на 15 кластеров для этого же набора объектов потребуется уже 10ОО • 15 • 15 • 100 = 2,25 • 107. Количество итераций возрастает более чем в 2 раза.

И наконец, вычисление целевой функции по формуле (1):

Для каждого кластера!

Для каждого ресурса{

Для каждого терма{

}

}

}

Время выполнения линейно зависит от количества кластеров, количества объектов.

Как следует из приведенных выше формул, в каждом из этапов присутствуют вложенные циклы до 3-4-го уровня вложенности.

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

Алгоритм параллельного выполнения РСМ-кластеризации

На рис. 1 показан алгоритм параллельного выполнения РСМ-кластеризации.

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

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

ди. Для подтверждения целесообразности распараллеливания данного алгоритма был проведен небольшой эксперимент.

Создание фиксированного пула потоков

Вычисление

центра кластера 1

т

Вычисление \

центра кластера 2 I

I Вычисление

центра \ кластера 3

Вычисление \ степени \ принадлежности объекта 1 / кластерам /

i Вычисление \ / степени \

принадлежности \ объекта Я / \ кластерам /

Вычисление целевой функции

Вычисление целевой функции

Вычисление целевой функции

[Выполняется условие завершения алгоритма]

Рис. 1. Алгоритм параллельного выполнения FCM-кластеризации

Эксперимент

Исходные данные Документы — 265 Уникальные термы — 4713 Кластеры — 10 Итерации — 50

Компьютер — Intel 2.4 ГГц 2-ядерный

103

№2(20)2009

Как показывают результаты эксперимента, последовательное выполнение занимает около 72 минут в ОС Linux и около 74 минут в Windows ХР. При этом параллельное выполнение в Linux сокращает время более чем в 2 раза (табл.).

Таблица

Результаты экспериментов

Число потоков Время, мин Linux Время, мин WinXP

1 -72 -74

2 -32 -42

3 -32 -42

10 -32 -42

Реализация

В качестве входных данных кластеризатор использует набор ресурсов с термами и веса-

ми этих термов в документе. На выходе должно быть построено дерево кластеров.

Кластеризатор реализован на JAVA. Ниже представлена диаграмма вариантов применения пользователем приложения (рис. 2).

Рассмотрим только основные возможности приложения.

Кластеризатор

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

Информация о документах и термах загружается из БД MSSQL. После загрузки ресурсов формируется набор уникальных термов из термов загруженных ресурсов, который будет характеризовать центры кластеров. Затем пользователь выбирает параметры кластеризации, на основе которых происходит формирование первоначальной матрицы принадлежности ресурсов кластерам (рис. 3).

Рис. 2. Диаграмма вариантов использования

104

№2(20)2009

Ресурсы Н а

СТП АБЕИ.459_2-2004.doc & 0 0 0 0 1 0 ж

ПП АБЕИ. 163-2005.doc 0,096 0,006 0,498 0,179 0,001 0,22

ЕМАИ. 468 6 2 9.00 lTS.doc 0,064 0,001 0,612 0,15 0 0,173

ЕМАИ.464426.005 Д^ОС 0,235 0 0,14 0,32 с 0,305

МД АБЕИ.010.doc 0,16 0 0,103 0,331 0 0,406

ИУ .АБЕИ _032-2003.doc 0,054 0 0,511 0,182 0 0,253

ЕМАИ. 11508-01 32 01.doc 0,226 0 0,061 0,412 0 0,301

ЕМАИ. 11507-01 32 01.doc 0,176 0 0,083 0,406 0 0,335

ЕМАИ. 461269.033PP2.dOC 0,014 0 0,888 0,045 0 0,054

ЕМАИ. 11507-01 34 01.doc 0,27 0 о.озб 0,41 0 0,284

СТП АБЕИ.467-2005.doc 0,116 0 0,026 0,291 0 0,567

ИУ АБЕИ 033-2004.DOC 0,147 0 0,073 0,404 0 0,376

ЕМАИ. 4612 6903 3P31.doc 0,006 0 0,941 0,023 0 0,03

ИУ АБЕИ_025-2006.гА 0,003 0 0,963 0,014 0 0,02

СТП АБЕИ.281-2005.rtf 0,224 0 0,009 0,332 0 0,435

СТП АБЕИ.2 82-2 006.doc 0,05 0 0,042 0,246 0 0,663

ЕМАИ. 11480-01 32 01.doc 0,291 0 0,018 0,455 € 0,237

КР АБЕИ.2.03.08.060-2004.doc 0,307 0 0,008 0,344 с 0,341

СТП АБЕИ. 007-2 005.doc 0,061 0 0,02 0,317 0 0,601

КР АБЕИ.2.13.01.058 - 2004.doc 0,621 0 0,004 0,23 0 0,145

СТП АБЕИ.283.l-2005.rtf 0,058 0 0,009 0,3 0 0,633 „

М Укажите параметры модели

Параметры ((пастеризатора

Количество кластеров Количество итераирй Уровень ючнос1и Экспоненциальный вес

мИН от 2-ух до количества ресурсов

100И~| максимальное число итерация до остановки

1_| предел разности целевых функций

_| >1, обычно 1,3-1,6

1 Информация о кластере

Код: 1

Наименование: таблица,подразделение,создание.

Параметр Значение Ресурс Степень принадлежно..

серебро 0,004 - ПП ЕМАИ.9001(4.28)... 0.317 -

защита 0,073 ПП АБЕИ.9001(4.2б).... 0,131

принтер 0,214 СТП АБЕИ.467-2005..,. 0,18

количество 1,492 СТП АБЕИ.462-2004... 0,175

коробка 0,043 СТП АБЕИ.461- 2004.... 0,275

заключение 0,228 СТП АБЕИ.459.2-200... 0,049 =

земля 0,043 СТП АБЕИ.45 9-2 005.... 0,268

управление 1,627 СТП АБЕИ.283.2-200... 0,092

перевод 0,098 СТП АБЕИ.2 83 Л-2 00... 0,203

зона 0,017 СТП АБЕИ.2 83 .0-2 00... 0,417

кожух 0,085 СТП АБЕИ.2 82-2 006.... 0,022

поступление 0,002 СТП АБЕИ.281-2005.rtf 0,291

течение 0,184 СТП АБЕИ. 455-2004.... 0.199

управляющая 0,079 СТП АБЕИ. 453-2004.... 0,062

сторона 0,203 СТП АБЕИ, 177-2005.... 0,282

набор 0,003 П АБЕИ.127-2003.dOC 0,238

И

Параметры многопоточности Число потоков для вычисления алгоритма

3

Принять

Рис. 3. Параметры РСМ-модели кластеризации

СЭ данные,подразделение,создание. ПЗ жгут, кабель, создание.

ЕМАИ.464426.005 РЭ.сЮс Л наименование,производить,создание.

ЕМАИ. 46862 9.00 lTB.doc

ЕМАИ. 461269.033PP2.doc

ЕМАИ. 4612 69033 P31.doc

ИУ АБЕИ.025-2006.ПГ

ИУ.АБЕИ.032-2003^ос

ПП АБЕИ. 163-2005.doc

е- СЭ подразделение,проведение,создание. П выполнение,проведение,создание.

СТП АБЕИ.459_2-2004.doc Л гост,подразделение,создание.

Рис. 4. Дерево кластеров и документов

серебро

количество

Информация о кластере Код: 1

Наименование: таблица,подразделение,создание.

Параметр

коробка

заключение

кожух

поступление

управляющая

набор

Значение

0,004

0,043

0,098

0,017

0,184

0,079

СТП АБЕИ 467-2005..

СТП АБЕИ.462-2004..

СТП АБЕИ.461- 2004..

СТП АБЕИ 459.2-200.

СТП АБЕИ.459-2005..

Ресурс

ПП ЕМАИ_9001(4.28).

Степень принадлежно.

ПП АБЕИ. 9001(4.2 6)..

СТП АБЕИ.283 .2-200.

СТП АБЕИ.283.1-200.

СТП АБЕИ.2 83 .0-2 00.

СТП АБЕИ.2 82-2 006..

СТП АБЕИ.281-2005.rtf

СТП АБЕИ. 455-2004..

СТП АБЕИ. 453-2004..

СТП АБЕИ 177-2005,

П АБЕИ.127-2003.doc

0,317

0,131

0,275

0,203

0,417

0.199

0,062

0,282

Рис. 6. Информация о кластере

>э

I

со

0

1

СТП АБЕИ.459_2-2004.doc

ПП АБЕИ. 163-2005.doc

ЕМАИ. 468 6 2 9.001TB.doc

ЕМАИ.464426.005 Д^ОС

МД АБЕИ.010.doc

ИУ _АБЕИ_032-2003.йос

ЕМАИ. 11508-01 32 01.doc

ЕМАИ. 11507-01 32 01.doc

ЕМАИ. 4612 69.033PP2.doc

Ресурсы

ЕМАИ. 11507-01 34 01.doc

СТП АБЕИ 467-2005.doc

ИУ АБЕИ Q33-2004.DOC

ЕМАИ. 4612 6903 3P31.doc

ИУ АБЕИ 025-2006.rtf

СТП АБЕИ 2Bl-2005.rtf

СТП АБЕИ 282-2006 (1ос

ЕМАИ. 11480-01 32 01.doc

КР АБЕИ.2.03.08.060-2004.doc

СТП АБЕИ.007-2005 йос

КР АБЕИ.2 13.01.058 - 2004.doc

СТП АБЕИ 283 l-2005.rtf

0,226

0.006

о.ооз

0,224

0.05

0.307

0,621

0,05 8

0.941

0,963

0,009'

0,042

0,009

0,32

0,331.

0,182

0,412

0.404

0.023

0,014

0,332

0,246

0,3

0,02

0,435

0.633

Рис. 5. Матрица принадлежности модели кластеризации

Кроме стандартных параметров алгоритма РСМ, пользователь также может задать параметры формирования имен кластеров, способ формирования дерева кластеров и число потоков, которое будет выделено для выполнения алгоритма.

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

Уникальны...|Подкластер

Кластер подразделе..

Ресурсов

Экс. вес

¡Уровень та

Итерация

Макс, итера...

100

Разность целев. 10

Статус

31

514

1.3

1Е-4

ЫЕШ

Корень

623

бПТГ

Рис. 7. Параметры процесса кластеризации

105

№2(20)2009

fcm.experiroent (Эксперимент по кластеризацию

id INTEGER SIGNED NOT NULL (AUTO) (код) description TEXT SIGNED NULL (описание)_

/|\ / Гст_ model (Модель класт \ ериэациЮ

id integer SIC "о experiment.ld integer SIC name varchar

fem, du я« г

Id INTEGER SIGNED NOT NULL

name VARCHAR

L'nfcm_model_ld INTEGER SIGNED NOT NULL (

T

L

fan.user.param (Параметры модели, заданные пользователем)_

id INTEGER SIGNED NOT NULL

fcm.model.id INTEGER SIGNED NOT NULL

count.iterations INTEGER SIGNED NOT NULL

precisslonjevel FLOAT SIGNED NOT NULL

ex p.weight FLOAT SIGNED NOT NULL

level.Include FLOAT SIGNED NOT NULL

fcm.process.param (параметры процесса кластеризацию_

id INTEGER SIGNED NOT NULL (AUTO) (код) fcm.model.id INTEGER SIGNED NOT NULL (код fcm-модели) precisslon.level FLOAT SIGNED NOT NULL (достигнутый уровень точности) count Jterailons INTEGER SIGNED NOT NULL (количество выполненных итераций) exec.iime_BIGINT SIGNED NULL (время выполнения модели)_

fem.duster.center

id BIGINT SIGNED NOT NULL

cluster.ld INTEGER SIGNED NOT NULL

fcm.res.duster

id INTEGER SIGNED NOT NULL

"о duster.id INTEGER SIGNED NOT NULL

grade FLOAT SIGNED NOT NULL

Рис. 8. Схема БД для результатов кластеризации

§

5Г

<3 §

I

I

<3 i

! I

5

i s s

I g-

с:

s

ST i

метры. Программа позволяет выполнять одновременно несколько процессов кластеризации на одном уровне иерархии. Каждая модель запускается отдельным потоком.

Пользователю также предоставляется возможность самому редактировать сформированное дерево кластеров (добавлять кластеры, перемещать ресурсы).

Визуализатор

Для наблюдения за процессом кластеризации, а также для анализа результатов реализован визуализатор кластеризации. Он отображает динамику изменения разбиения. Имеет возможности просмотра:

• изменяющегося дерева кластеров (рис. 4);

• изменения матрицы принадлежности ресурсов кластерам (рис. 5);

• изменения центров каждого кластера, и степеней принадлежности ресурсов (рис. 6);

• текущих параметров процесса (рис. 7).

Визуализатор доступен для каждого запущенного потока кластеризации.

Сохранение результатов

Приложение позволяет сохранять результаты экспериментов в БД и формировать подробный ХМЬотчет о проделанных экспериментах. Выше представлена схема БД для результатов разбиений и окно выбора параметров формирования ХМЬотчета (рис. 8,9).

И ¡Экспоненциальный вес| 0 Количество выполненных итераций 0 Разность целевых функций 0 Порог включения в дерево Параметры кластеров

0 Идентификатор 0 Имя

Параметры ресурсов-

0 Идентификатор 0 Имя

0 Степень принадлежности

Рис. 9. Параметры формирования XML-отчета о кластеризации

Поиск документов

Для поиска документов в уже сформированном кластеризатором наборе кластеров реализована поисковая система. Поиск осуществляется по ключевым словам документов.

Результатом поиска является список документов с описанием количества включения искомого слова и перечислением кластеров, к которым относится этот документ в процентном отношении.

СПИСОК ЛИТЕРАТУРЫ

1. Ярушкина Н. Г. Основы теории нечетких и гибридных систем. М.: Финансы и статистика, 2004.

2. A Tutorial on Clustering Algorithms

106