'

Кластеризация данных нечеткими методами

Понравилась презентация – покажи это...





Слайд 0

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


Слайд 1

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


Слайд 2

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


Слайд 3

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


Слайд 4

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


Слайд 5

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


Слайд 6

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


Слайд 7

8


Слайд 8

9


Слайд 9

10


Слайд 10

11


Слайд 11

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


Слайд 12

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


Слайд 13

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


Слайд 14

15


Слайд 15

16 FCM algorithm GK-algorithm Результаты для окружностей С-elliptotypes Shell-clustering


Слайд 16

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


Слайд 17

18 Результаты для эллипсов FCM algorithm GK-algorithm С-elliptotypes Shell-clustering


Слайд 18

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


Слайд 19

20 Библиографический список 1. Осовский С. Нейронные сети. М.: Финансы и статистика, 2002. 2. Сокал Р.Р. Кластер-анализ и классификация: предпосылки и основные направления [Текст]/ Р.Р.Сокал. Под ред. Дж. Вэн Райзина. – М.:Мир, Классификация и кластер, 1980. 3. Bezdek J.C. Pattern recognition with fuzzy objective function algorithms. – Plenum Press, New York. – 1982. 4. Gustafson D.E., Kessel W.C. Fuzzy clustering with a fuzzy covariance matrix - http://www.egr.uh.edu/ece/faculty/karayiannis/Karayiannis_tnn_16(2)_05.pdf 5. Jain А. К. Data Clustering: A Review [Текст] / А. К. Jain, M. N. Murty, P. J. Flynn - http://www.csee.umbc.edu/nicholas/clustering/p264-jain.pdf, 2006. 6. Ahmed Ismail Shihab. Fuzzy clustering algorithmes and their application to medical image analysis, PhD dissertation, 2000.


Слайд 20

21 Волкова Елена Петровна Блюмин Семен Львович Шуйкова Инесса Анатольевна volkova.lenochka@mail.ru sabl@lipetsk.ru shujkova_i_a@inbox.ru Спасибо за внимание!


×

HTML:





Ссылка: