Кластеризация

Немного истории Первые публикации по кластерному анализу появились в конце 30-х гг. прошлого столетия. Активное развитие и широкое использование началось в конце 60-х- начале 70-х гг. Первоначально методы многомерной классификации использовалось в психологии, археологии, биологии, а теперь активно применяется в социологии, экономике, статистике, в исторических исследованиях.

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

Задача кластеризации состоит в разделении исследуемого множества объектов на группы «похожих» объектов, называемых кластерами. англ. «cluster» - сгусток, пучок, группа.

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

Формальная постановка задачи ДАНО - набор данных со следующими свойствами: каждый экземпляр данных выражается четким числовым значением; класс для каждого конкретного экземпляра данных неизвестен. НАЙТИ: способ сравнения данных между собой (меру сходства); способ кластеризации; разбиение данных по кластерам.

Формально задача описывается следующим образом Дано множество объектов данных I, каждый из которых представлен набором атрибутов. Требуется построить множество кластеров C и отображение F множества I на множество C, т. е. F : I C. Отображение F задает модель данных, являющуюся решением задачи. Качество решения задачи определяется количеством верно классифицированных объектов данных. где - исследуемый объект

Табл. 1

Каждый из объектов характеризуется набором параметров

Задача кластеризации состоит в построении множества: –– кластер. где σ величина, определяющая меру близости для включения объектов в один кластер; мера близости между объектами, называемая расстоянием.

называется расстоянием, если выполняется следующее условие: 1. 2., когда = Если расстояние < σ, то говорят, что элементы близки и помещаются в один кластер, в противном случае говорят, что элементы отличны друг от друга и их помещают в разные кластеры.

Большинство популярных алгоритмов используют в качестве формата входных данных матрицу отличия D.

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

Евклидово расстояние Иногда может возникнуть желание возвести в квадрат стандартное евклидово расстояние, чтобы придать большие веса более отдаленным друг от друга объектам.

Расстояние по Хеммингу Это расстояние является просто средним разностей по координатам. В этом случае влияние отдельных больших разностей (выбросов) уменьшается (т. к. они не возводятся в квадрат).

Расстояние Чебышева Это расстояние может оказаться полезным, когда желают определить два объекта как "различные", если они различаются по какой- либо одной координате (каким-либо одним измерением).

Расстояние Махаланобиса Данная мера расстояния плохо работает, если ковариационная матрица высчитывается на всем множестве входных данных. В то же время, будучи сосредоточенной на конкретном классе (группе данных), данная мера расстояния показывает хорошие результаты:

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

Разделение ирисов на кластеры линиями Элементы Линии разделяющие кластеры

Разделение ирисов на кластеры с использованием Венских диаграмм

Дендрограмма, построенная для данных из табл.1

Базовые алгоритмы кластеризации Классификация алгоритмов Алгоритмы кластеризации строятся как некоторый способ перебора числа кластеров и определения его оптимального значения в процессе перебора.

Методы разбиения множеств на кластеры Неиерархические Иерархические Дивизимные Агломеративные

Иерархические алгоритмы. Агломеративные алгоритмы

Иерархические алгоритмы. Дивизимные алгоритмы В отличии от агломеративных на первом шаге представляют все множество элементов I как единственный кластер. На каждом шаге алгоритма один из существующих кластеров рекурсивно делится на два дочерних. Среднее значение вычисляется по формуле:

Неиерархические алгоритмы Алгоритмы построения разбиения пытаются сгруппировать данные (в кластеры) таким образом, чтобы целевая функция алгоритма разбиения достигла экстремума (минимума). Обучающее множество (входное множество данных) М, на котором строится разбиение; Метрика расстояния:

Алгоритм k-means (Hard-c-means)

Алгоритм: Шаг 1. Проинициализировать начальное разбиение (например, случайным образом), выбрать точность δ (используется в условии завершения алгоритма), проинициализировать номер итерации l = 0. Шаг 2. Определить центры кластеров по следующей формуле:

Шаг 3. Обновить матрицу разбиения с тем, чтобы минимизировать квадраты ошибок, используя формулу

Шаг 4. Проверить условие. Если условие выполняется, завершить процесс, если нет – перейти к шагу 2 с номером итерации I=I+1

Алгоритм Fuzzy С-Means Шаг 1. Выбрать количество кластеров 2 cd. Шаг 2. Выбрать скалярную метрику для отображения векторов данных на вещественную ось. Шаг 3. Выбрать параметр остановки δ.

Шаг 4. Выбрать коэффициент нечеткости w (1, ), например w = 2. Шаг 5. Проинициализировать матрицу разбиения (например, случайными значениями).

Шаг 6. Вычислить прототипы (центры) кластеров по формуле:

Шаг 7. Для всех элементов данных высчитать квадраты расстояний до всех (центров) кластеров по формуле:

Шаг 8. Обновить матрицу разбиения по следующей формуле: для всех 1ic, 1jd.

Шаг 9. Проверить условие. Если условие выполняется, завершить процесс, если нет перейти к шагу 7 с номером итерации l=l+1.

Кластеры сферической формы

Кластеризация по Гюстафсону-Кесселю

Конструктивно алгоритм выглядит следующим образом. Шаг 1. Определить количество кластеров 2 cd. Шаг 2. Определить критерий остановки δ>0. Шаг 3. Определить параметр нечеткости w (1, ), например 2. Шаг 4. Проинициализировать матрицу разбиения, например случайными значениями.

Шаг 5. Рассчитать прототипы кластеров по формуле:

Шаг 6. Рассчитать ковариационные матрицы кластеров по формуле:

Шаг 7. Рассчитать расстояния по формуле:

Шаг 8. Обновить матрицу разбиения по формуле:

Шаг 9. Проверить условие. Если условие выполняется, завершить процесс, если нет перейти к шагу 5 с номером итерации l=l+1.

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

Использование формальных критериев качества в адаптивной кластеризации Формальные критерии оценивают качество кластеризации по некоторому показателю, вычисленному на основании результатов кластеризации. Наилучшим является решение, для которого значение критерия достигает экстремального значения. Ключевым элементом в адаптивной кластеризации является выбор критерия, по которому будет оцениваться качество кластеризации.

Показатели четкости Коэффициент разбиения : Модифицированный коэффициент разбиения:

Индекс четкости:

Энтропийные критерии Энтропия разбиения: Модифицированная энтропия:

Показатель компактности и изолированности: Индекс эффективности.

меж кластерные отличия (велики при оптимальном K ): внутри кластерные отличия (малы при оптимальном K ):

Комбинируя эти части, получаем критерий:

Выводы Задача кластеризации состоит в разделении исследуемого множества объектов на группы похожих объектов, называемых кластерами. Для определения "похожести" объектов вводится мера близости, называемая расстоянием. Существуют разные способы вычисления расстояний: евклидово, махаланобиса, Чебышева и др.

Результаты кластеризации могут быть представлены разными способами. Одним из наиболее популярных является дендрограмма отображение последовательного процесса кластеризации.

Базовые методы кластеризации делятся на иерархические и неиерархические. Первые строят дендрограммы или снизу вверх (агломеративные), или сверху вниз (дивизимные).

популярный из неиерархических алгоритмов алгоритм k -средних и его разновидности. Идея метода заключается в определении центров k кластеров и отнесения к каждому кластеру объектов, наиболее близко находящихся к этим центрам.

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

Проверка пройденного материала Утверждение верно? Кластерный анализ позволяет рассматривать достаточно большой объем информации, делать их компактными и наглядными. ДАНЕТ

Слово кластер с английского переводится как …? Ответ: сгусток, пучок, группа

Правильно ли подписаны графики? Венская диаграмма Дендрограм- ма

Правильно? Методы разбиения множеств на кластеры Неиерархические Иерархические Дивизимные Агломеративные

Один метод не верный, какой? Существуют различные методы вычисления расстояний: Евклидово Махаланобиса Фишера Чебышева