- •Вариант параллельного выполнения алгоритма fcm – кластеризации
- •1. Введение
- •2. Алгоритм fcm
- •Шаг 1. Инициализация.
- •Шаг 2. Вычисление центров кластеров.
- •Шаг 3. Формирование новой матрицы принадлежности.
- •Шаг 4. Вычисление целевой функции.
- •3. Примерная оценка сложности алгоритма
- •4. Алгоритм параллельного выполнения fcm–кластеризации
- •Fcm алгоритма
- •5. Эксперимент
- •6. Реализация
- •7. Кластеризатор
- •8. Визуализатор
- •9. Сохранение результатов
- •10. Поиск документов
Вариант параллельного выполнения алгоритма fcm – кластеризации
Островский А.А.
Ульяновский государственный технический университет
e-mail: a.ostrovsky@ulstu.ru
1. Введение
Огромные объёмы информации зачастую приводят к тому, что количество объектов, выдаваемых по запросу пользователя, очень велико. Однако, в большинстве случаев, ее можно сделать доступными для восприятия, если уметь разбивать источники информации на тематические группы. Такой процесс группировки данных осуществляется с помощью кластеризации. Рассмотрим один из таких методов – FCM и его модификацию для параллельного выполнения.
2. Алгоритм fcm
Целью FCM (Fuzzy Classifier Means) – алгоритма кластеризации является автоматическая классификация множества объектов, которые задаются векторами признаков в пространстве признаков. Другими словами, такой алгоритм определяет кластеры и соответственно классифицирует объекты. Кластеры представляются нечеткими множествами, и, кроме того, границы между кластерами также являются нечеткими.
FCM–алгоритм предполагает, что объекты принадлежат всем кластерам с определенной функцией принадлежности. Степень принадлежности определяется расстоянием от объекта до соответствующих кластерных центров. Данный алгоритм итерационно вычисляет центры кластеров и новые степени принадлежности объектов.
Алгоритм основан на минимизации целевой функции:
, (1)
где: N – количество документов; С – количество кластеров; uij – степень принадлежности объекта i кластеру j; m – любое действительное число, большее 1, xi – i-ый объект набора объектов; cj – j-ый кластер набора кластеров; | xi – cj | – норма, характеризующая расстояние от центра кластера j до объекта i.
Объектами кластеризации являются электронные текстовые документы. Задачей FCM – алгоритма является разбиение этого набора на заданное количество кластеров. Для каждого документа составлен частотный портрет входящих в него значимых терминов. Эти частотные портреты и являются векторами признаков объектов (электронных документов) кластеризации.
Алгоритм нечеткой кластеризации выполняется по шагам.
Шаг 1. Инициализация.
Задаются параметры кластеризации и инициализируется первоначальная матрица принадлежности электронных документов кластерам. Выбираются значения следующих параметров:
экспоненциальный вес (m);
мера расстояний – . Мера расстояний характеризует степень близости документа кластеру. Как правило, выбирается евклидова норма:
=, (2)
где q – количество значимых термов набора документов; xji – количество терма j в i-ом документе; vjk – значение, соответствующее терму j в k-ом кластере;
уровень точности ε;
количество итераций алгоритма.
После выбора параметров генерируется случайным образом первоначальная матрица принадлежности объектов кластерам.
Шаг 2. Вычисление центров кластеров.
Каждому j-ому терму всех документов ставиться в соответствие действительное число, вычисляемое следующим образом:
, (3)
где cj – значение j-ого терма кластера; N – количество документов; xi – значение терма j i-го документа; uij – степень принадлежности документа i кластеру j.