1 Кластеризация данных нечеткими методами Выполнила: ассистент кафедры ПМиИТ, ЛГПУ Волкова Елена Научный руководитель: д.ф.-м.н., профессор Блюмин Семен Львович, к.т.н.,доцент Шуйкова Инесса Анатольевна

2 Кластеризация – это разбиение элементов некоторого множества на группы на основе их схожести. Задача кластеризации состоит в разбиении объектов из X на несколько подмножеств (кластеров), в которых объекты более схожи между собой, чем с объектами из других кластеров. В метрическом пространстве «схожесть» обычно определяют через расстояние. Алгоритмы кластеризации оперируют с объектами. Каждому объекту Х отождествляется вектор характеристик. Компоненты, являются отдельными характеристиками объекта. Количество характеристик d определяет размерность пространства характеристик. Множество, состоящее из всех векторов характеристик, обозначается, где.

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

4 Четкая (непересекающаяся) кластеризация – кластеризация, в которой каждый объект из М относится только к одному кластеру. Нечеткая кластеризация – кластеризация, при которой для каждого из М определяется - вещественное значение, показывающее степень принадлежности к кластеру. Развитие и широкое применение нечёткая кластеризация получила благодаря Бездеку и его методу нечетких k-средних (Fuzzy c-means - FCM).

5 Базовый алгоритм нечетких k-средних Самый простой алгоритм нечеткой кластеризации – это нечеткий алгоритм k-средних. Этот алгоритм находит компактные кластеры, например, сферической формы. Нечеткие кластеры опишем матрицей нечеткого разбиения,,, где -я строчка содержит степени принадлежности объекта кластерам. Единственным отличием матрицы степеней принадлежности четкого разбиения от нечеткого является то, что элементы матрицы принимают значения из двухэлементного множества {0,1}, а не из интервала [0,1].

6 В базовом алгоритме нечетких k-средних расстояние между объектом и центром кластера рассчитывается через стандартную Евклидову норму:. В результате алгоритмов кластеризации с фиксированной нормой форма всех кластеров получается одинаковой. Алгоритмы кластеризации как бы навязывают данным неприсущую им структуру, что приводит не только к неоптимальным, но иногда и к принципиально неправильным результатам. Для устранения этого недостатка предложено несколько методов, среди которых выделим алгоритм Густафсона-Кесселя (Gustafson-Kessel algorithm).

7 Алгоритм Густафсона-Кесселя(Gustafson – Kessel, GK) По отношению к обычному алгоритму k-средних главное изменение состоит во введении в формулу расчета расстояния между векторами масштабирующей матрицы A. В качестве масштабирующей обычно применяется симметричная положительно определенная матрица, т.е. матрица, у которой все собственные значения являются действительными и положительными. Алгоритм Густафсона-Кесселя использует адаптивную норму для каждого кластера, т.е. для каждого j-го кластера существует своя норм-порождающая матрица. В этом алгоритме при кластеризации оптимизируются не только координаты центров кластеров и матрица нечеткого разбиения, но также и норм-порождающие матрицы для всех кластеров. Это позволяет выделять кластера различной геометрической формы. GK – простой нечеткий алгоритм кластеризации, позволяющий обнаружить кластеры эллипсоидальной формы. В комбинации с алгоритмом нечетких k – средних он часто используется, чтобы инициализировать другие нечеткие алгоритмы кластеризации.

8 Базовый алгоритм нечетких k-средних Алгоритм Густафсона- Кесселя Шаг 1. Установить параметры алгоритма: c - количество кластеров; m - экспоненциальный вес; - параметр остановки алгоритма. Шаг 2. Случайным образом сгенерировать матрицу нечеткого разбиения. Шаг 3. Рассчитать центры кластеров:

9 Базовый алгоритм нечетких k-средних Алгоритм Густафсона- Кесселя Шаг 4. Рассчитать расстояния между объектами из X и центрами кластеров: Шаг 4.Вычисляем матрицу ковариации для j-ого кластера: Шаг 5. Рассчитать расстояния между объектами из X и центрами кластеров:

10 Базовый алгоритм нечетких k-средних Алгоритм Густафсона- Кесселя Шаг 5. Пересчитать элементы матрицы нечеткого разбиения: если если : Шаг 6. Пересчитать элементы матрицы нечеткого разбиения: если если :

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

12 Алгоритм нечетких с-эллипсоидов Шаг 1. Установить параметры алгоритма: c - количество кластеров; m - экспоненциальный вес; - параметр остановки алгоритма. Шаг 2. Случайным образом сгенерировать матрицу нечеткого разбиения. Шаг 3. Рассчитать центры кластеров: Шаг 4. Рассчитать расстояния между объектами из X и центрами кластеров: где евклидово расстояние s=1,..,r, r-количество собственных векторов, - s-ый собственный вектор ковариационной матрицы кластера j. Параметр, где max и min собственное значение матрицы.

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

14 Shell-clustering algorithm Основное новшество алгоритма состоит в том, что в данном алгоритме прототип кластера описывается помимо центра ещё и радиусом. Формула для вычисления расстояния имеет следующий вид:

15

16 Clus1Clus 2 Clus Clus 1 Clus 2 Clus Clus 1 Clus 2 Clus FCM algorithmGK-algorithm Результаты для окружностей Clus 1 Clus 2 Clus С-elliptotypesShell-clustering

17 Clus 1 Clus 2 Clus Clus 1 Clus 2 Clus Результаты для окружностей FCM algorithmGK-algorithm Clus 1 Clus 2 Clus С-elliptotypes Clus 1 Clus 2 Clus Shell-clustering

18 Результаты для эллипсов Clus 1 Clus 2 Clus Clus 1 Clus 2 Clus Clus 1 Clus 2 Clus FCM algorithmGK-algorithm Clus 1 Clus 2 Clus С-elliptotypesShell-clustering

19 Clus 1 Clus 2 Clus Clus 1 Clus 2 Clus Clus 1 Clus 2 Clus Результаты для эллипсов FCM algorithm Clus 1 Clus 2 Clus GK-algorithm С-elliptotypesShell-clustering

20 Библиографический список 1. Осовский С. Нейронные сети. М.: Финансы и статистика, Сокал Р.Р. Кластер-анализ и классификация: предпосылки и основные направления [Текст]/ Р.Р.Сокал. Под ред. Дж. Вэн Райзина. – М.:Мир, Классификация и кластер, Bezdek J.C. Pattern recognition with fuzzy objective function algorithms. – Plenum Press, New York. – Gustafson D.E., Kessel W.C. Fuzzy clustering with a fuzzy covariance matrix - pdf pdf 5. Jain А. К. Data Clustering: A Review [Текст] / А. К. Jain, M. N. Murty, P. J. Flynn Ahmed Ismail Shihab. Fuzzy clustering algorithmes and their application to medical image analysis, PhD dissertation, 2000.

21 Волкова Елена Петровна Блюмин Семен Львович Шуйкова Инесса Анатольевна Спасибо за внимание!