Добавил:
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Ostrovskiy.doc
Скачиваний:
35
Добавлен:
28.12.2014
Размер:
547.84 Кб
Скачать

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

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

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

e-mail: a.ostrovsky@ulstu.ru

1. Введение

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

2. Алгоритм fcm

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

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

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

, (1)

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

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

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

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

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

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

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

=, (2)

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

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

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

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

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

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

, (3)

где cj – значение j-ого терма кластера; N – количество документов; x– значение терма j i-го документа; uij – степень принадлежности документа i кластеру j.

Соседние файлы в предмете Методы обработки измерительной информации