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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

15 15

16 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 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 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 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 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 21 Волкова Елена Петровна Блюмин Семен Львович Шуйкова Инесса Анатольевна Спасибо за внимание!