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

Размещено на http://www.allbest.ru/

Ульяновский государственный технический университет

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

Островский А.А.

e-mail: a.ostrovsky@ulstu.ru



Введение

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



1. Алгоритм FCM

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

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

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

, (1)

где: N - количество документов; С - количество кластеров; u_ij - степень принадлежности объекта i кластеру j; m - любое действительное число, большее 1, x_i - i-ый объект набора объектов; c_j - j-ый кластер набора кластеров; | x_i - c_j | - норма, характеризующая расстояние от центра кластера j до объекта i.

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

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

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

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

1. экспоненциальный вес (m);

2. мера расстояний - . Мера расстояний характеризует степень близости документа кластеру. Как правило, выбирается евклидова норма:

=,(2)

где q - количество значимых термов набора документов; x_jⁱ - количество терма j в i-ом документе; v_j^k - значение, соответствующее терму j в k-ом кластере;

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

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

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

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

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

, (3)

где c_j - значение j-ого терма кластера; N - количество документов; x_i - значение терма j i-го документа; u_ij - степень принадлежности документа i кластеру j.

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

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

(4)

где u_ij - степень принадлежности объекта i кластеру j, c_j - вектор центра j - го кластера, c_j - вектор центра l - го кластера.

При этом, если для некоторого кластера j и некоторого объекта i, =0, тогда полагаем, что степень принадлежности u_ij равна 1, а для всех остальных кластеров степень принадлежности этого документа равна нулю.

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

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

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

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

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

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

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

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

}

}

}

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

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

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

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

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

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

}

}

}

}

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

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

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

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

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

}

}

}

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

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

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

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

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

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

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

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

4. Эксперимент

Исходные данные:

Документов: 265

Уникальных термов: 4713

Кластеров: 10

Итераций: 50

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

Таблица 1. Результаты экспериментов

Число потоков	Время, мин Linux	Время, мин WinXP
1	~72	~74
2	~32	~42
3	~32	~42
10	~32	~42

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

5. Реализация

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

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

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

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

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

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

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

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

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

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

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

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

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

l просмотр изменяющегося дерева кластеров;

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

l просмотр изменения матрицы принадлежности ресурсов кластерам;

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

l просмотр изменения центров каждого кластера, и степеней принадлежности ресурсов;

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

l текущие параметры процесса;

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

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

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

Приложение позволяет сохранять результаты экспериментов в БД и формировать подробный XML отчет о проделанных экспериментах. Ниже представлена схема БД для результатов разбиений и окно выбора параметров формирования XML отчета.

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

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

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

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

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



Литература

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

2. A Tutorial on Clustering Algorithms. http://home.dei.polimi.it/matteucc/Clustering/tutorial_html/index.html

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

...