С.Д.Штовба "Введение в теорию нечетких множеств и нечеткую логику"

В оглавление книги \ К следующему разделу \ К предыдущему разделу

12. Нечеткая кластеризация

Кластеризация - это объединение объектов в группы (кластеры) на основе схожести признаков для объектов одной группы и отличий между группами. Большинство алгоритмов кластеризации не опираются на традиционные для статистических методов допущения; они могут использоваться в условиях почти полного отсутствия информации о законах распределения данных. Кластеризацию проводят для объектов с количественными (числовыми), качественными или смешанными признаками. В этой работе рассматривается кластеризация только для объектов с количественными признаками. Исходной информацией для кластеризации является матрица наблюдений:

,

каждая строчка которой представляет собой значения n признаков одного из M объектов кластеризации.

Задача кластеризации состоит в разбиении объектов из на несколько подмножеств (кластеров), в которых объекты более схожи между собой, чем с объектами из других кластеров. В метрическом пространстве "схожесть" обычно определяют через расстояние. Расстояние может рассчитываться как между исходными объектами (строчками матрицы ), так и от этих объектов к прототипу кластеров. Обычно координаты прототипов заранее неизвестны - они находятся одновременно с разбиением данных на кластеры.

Существует множество методов кластеризации, которые можно классифицировать на четкие и нечеткие. Четкие методы кластеризации разбивают исходное множество объектов на несколько непересекающихся подмножеств. При этом любой объект из принадлежит только одному кластеру. Нечеткие методы кластеризации позволяют одному и тому же объекту принадлежать одновременно нескольким (или даже всем) кластерам, но с различной степенью. Нечеткая кластеризация во многих ситуациях более "естественна", чем четкая, например, для объектов, расположенных на границе кластеров.

Методы кластеризации также классифицируются по тому, определено ли количество кластеров заранее или нет. В последнем случае количество кластеров определяется в ходе выполнения алгоритма на основе распределения исходных данных. В начале рассмотрим алгоритм c-средних, разбивающий данные на наперед заданное число кластеров, а затем алгоритм горной кластеризации, который не требует задания количества кластеров.

12.1 Кластеризация при заданном числе кластеров

В начале рассмотрим ключевые идеи четкой кластеризации алгоритмом c-средних, затем базовый нечеткий алгоритм c-средних и в заключении основные пути улучшения нечеткой кластеризации.

12.1.1. Четкая кластеризация алгоритмом c-средних

При кластеризации алгоритмом c-средних множество разбивается на подмножества , со следующими свойствами:

,

(12.1)

, ,

(12.2)

, .

(12.3)

Условие (12.1) указывает, что все объекты должны быть распределены по кластерам. При этом, каждый объект должен принадлежать только одному кластеру (условие (12.2) ) и ни один из кластеров не может быть пустым или содержать все объекты (условие (12.3) ). Количество кластеров задается до начала работы алгоритма.

Задачу кластеризации удобно формулировать использую характеристическую функцию. Характеристическая функция может принимать два значения: 0 - если элемент не принадлежит кластеру, и 1 - если элемент принадлежит кластеру. Используя характеристическую функцию, опишем кластеры следующей матрицей разбиения:

,

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

Матрица должна обладать следующими свойствами:

;

(12.4)

.

(12.5)

Для оценки качества разбиения используется критерий разброса, показывающий сумму расстояний от объектов до центра своего кластера. Для евклидового пространства этот критерий записывается так [1]:

,

(12.6)

где  - к-й объект кластеризации;

 - i-й кластер;

 - центр i-го кластера.

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

12.1.2. Базовый алгоритм нечетких c-средних

Нечеткие кластера опишем следующей матрицей нечеткого разбиения:

в которой k-ая строчка содержит степени принадлежности объекта к кластерам . Единственным отличием матриц и является то, что при нечетком разбиении степень принадлежности объекта к кластеру принимает значения из интервала [0, 1], а при четком - из двухэлементного множества {0, 1}. Аналогичные (12.4) - (12.5), условия для матрицы нечеткого разбиения записываются так [2]:

;

(12.7)

.

(12.8)

Нечеткое разбиение позволяет просто решить проблему объектов, расположенных на границе двух кластеров - им назначают степени принадлежностей равные 0.5. Недостаток нечеткого разбиения проявляется при работе с объектами, удаленными от центров всех кластеров. Удаленные объекты имеют мало общего с любым из кластеров, поэтому интуитивно хочется назначить для них малые степени принадлежности. Однако, по условию (12.7) сумма их степеней принадлежностей такая же, как и для объектов, близких к центрам кластеров, т.е. равна единице. Для устранения этого недостатка можно использовать возможностное разбиение, которое требует, только чтобы произвольный объект из принадлежал хотя бы одному кластеру. Возможностное разбиение получается следующим ослаблением условия (12.7): .

Для оценки качества нечеткого разбиения используется такой критерий разброса [2]:

,

(12.9)

где  - центры нечетких кластеров;

 - экспоненциальный вес, определяющий нечеткость, размазаность кластеров.

Предложено множество алгоритмов нечеткой кластеризации, основанных на минимизации критерия (12.9). Нахождение матрицы нечеткого разбиения с минимальным значение критерия (12.9) представляет собой задачу нелинейной оптимизации, которая может быть решена разными методами. Наиболее известный и часто применяемый метод решения этой задачи алгоритм нечетких c-средних, в основу которого положен метод неопределенных множителей Лагранжа. Он позволяет найти локальный оптимум, поэтому выполнение алгоритма из различных начальных точек может привести к разным результатам.

Алгоритм нечетких c-средних [2]

Шаг 1. Установить параметры алгоритма: c - количество кластеров; m - экспоненциальный вес;  - параметр останова алгоритма.

Шаг 2. Случайным образом сгенерировать матрицу нечеткого разбиения , удовлетворяющую условия (12.7) - (12.8).

Шаг 3. Рассчитать центры кластеров: , .

Шаг 4. Рассчитать расстояния между объектами из и центрами кластеров: , , .

Шаг 5. Пересчитать элементы матрицы нечеткого разбиения (, ):

если : ;

если : , .

Шаг 6. Проверить условие , где  - матрица нечеткого разбиения на предыдущей итерации алгоритма. Если "да", то перейти к шагу 7, иначе  - к шагу 3.

Шаг 7. Конец.

В приведенном алгоритме самым важным параметром является количество кластеров (c). Правильно выбрать количество кластеров для реальных задач без какой-либо априорной информации о структурах в данных достаточно сложно. Существует два формальных подхода к выбору числа кластеров.

Первый подход основан на критерии компактности и разделимости полученных кластеров. Логично предположить, что при правильном выборе количества кластеров данные будут разбиты на компактные и хорошие отделимые друг от друга группы. В противном случае, кластеры, вероятно, не будут компактными и хорошо отделимыми. Существует несколько критериев оценки компактности кластеров, однако вопрос о том, как формально и достоверно определить правильность выбора количества кластеров для произвольного набора данных все еще остается открытым. Для алгоритма нечетких c-средних в [3] рекомендуется использовать индекс Хие-Бени, предложенный в [4]:

.

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

Вторым параметром алгоритма кластеризации является экспоненциальный вес (m). Чем больше , тем конечная матрица нечеткого разбиения становится более "размазанной", и при она примет вид , что является очень плохим решением, т. к. все объекты принадлежат ко всем кластерам с одной и той же степенью. Кроме того, экспоненциальный вес позволяет при формировании координат центров кластеров усилить влияние объектов с большими значениями степеней принадлежности и уменьшить влияние объектов с малыми значениями степеней принадлежности. На сегодня не существует теоретически обоснованного правила выбора значения экспоненциального веса. Обычно устанавливают .

В оглавление книги \ К следующему разделу \ К предыдущему разделу