Тема_7 Кластерный анализ

1. Прикладной статистический анализ Тема Кластерный анализ

Прикладной статистический анализ
Тема
КЛАСТЕРНЫЙ АНАЛИЗ
1

2. Группы методов

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

3.

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

4. Примеры мер близости кластеров

4

5. Типы кластеров

5

6. Характеристики кластера

Кластер имеет следующие математические характеристики:
центр, радиус, среднеквадратическое отклонение, размер кластера.
Центр кластера - это среднее геометрическое место точек в
пространстве переменных.
Радиус кластера - максимальное расстояние точек от центра
кластера.
Спорный объект - это объект, который по мере сходства может быть
отнесен к нескольким кластерам.
Размер кластера может быть определен либо по радиусу
кластера, либо по среднеквадратичному отклонению объектов для
этого кластера.
Объект относится к кластеру, если расстояние от объекта до
центра кластера меньше радиуса кластера.
Если последнее условие выполняется для двух и более кластеров,
объект является спорным.
6

7. Принадлежность кластеру

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

8. Пример матрицы разбиения

8

9. Количество кластеров

9

10.

Стандартизация переменных
Рассмотрим пример.
Представим себе, что данные признака х в наборе данных на два
порядка больше данных признака у : значения переменной х находятся в
диапазоне от 100 до 700, а значения переменной у - в диапазоне от 0 до 1.
Стандартизация (standardization) или нормирование (normalization)
приводит значения всех преобразованных переменных к единому
диапазону значений путем выражения через отношение этих значений к
некой величине, отражающей определенные свойства конкретного
признака.
Существуют различные способы нормирования исходных данных:
10

11. Иерархические методы

11

12. Пример

12

13. Неиерархические методы

Среди неиерархических алгоритмов, не основанных на
расстоянии, следует выделить
EM-алгоритм (Expectation-Maximization).
В нем вместо центров кластеров предполагается наличие
функции плотности вероятности для каждого кластера с
соответствующим значением математического ожидания и дисперсией
13

14. Основные алгоритмы: K-means

Одной из широко используемых методик кластеризации является
разделительная кластеризация, в соответствии с которой для выборки данных,
содержащей n записей, задаётся число кластеров k, которое должно быть
сформировано. Затем алгоритм разбивает все объекты выборки на k групп (k<n),
которые и представляют собой кластеры.
К наиболее простым и эффективным алгоритмам кластеризации относится kmeans (k-средних). Он состоит из четырёх шагов:
1. Задаётся число кластеров k, которое должно быть сформировано из объектов
исходной выборки.
2. Случайным образом выбирается k записей, которые будут служить
начальными центрами кластеров.
3. Для каждой записи исходной выборки определяется ближайший к ней центр
кластера.
4. Производится вычисление центроидов - центров тяжести кластеров. Это
делается путём определения среднего для значений каждого признака всех записей
в кластере.
Шаги 3 и 4 повторяются до тех пор, пока не будет выполнено условие в
соответствии с некоторым критерием сходимости (чаще всего используется сумма
квадратов ошибок между центроидом кластера и всеми вошедшими в него записями).
Остановка алгоритма производится, когда на каждой итерации в каждом
14
кластере остаётся один и тот же набор записей.

15. Пример матрицы разбиения: K-means для нечетких множеств

15

16. K-means для нечетких множеств

16

17. Эффективность K-means для нечетких множеств

17

18. Оценка числа кластеров

18

19. Матрица отличия

19

20. Основные алгоритмы: G-means

В его основе лежит предположение о том, что кластеризуемые данные
подчиняются некоторому унимодальному закону распределения, например
гауссовскому. Тогда центр кластера, определяемый как среднее значений признаков
попавших в него объектов, может рассматриваться как мода соответствующего
распределения.
Если исходные данные описываются унимодальным гауссовским
распределением с заданными средним, то можно предположить, что все они
относятся к одному кластеру.
Если распределение данных не гауссовское, то выполняется разделение на два
кластера. Алгоритм G-means является итеративным, где на каждом шаге с
помощью обычного алгоритма k-means строится модель с определённым числом
кластеров (начальное значение k выбирается равным 1), которое увеличивается на
каждой итерации. Увеличение k производится за счёт разбиения кластеров, в
которых данные не соответствуют гауссовскому распределению.
Алгоритм «принимает решение» о дальнейшем разбиении на основе
статистического теста данных, связанных с каждым центроидом. Если при этом
будет обнаружено, что они распределены по гауссовскому закону, то дальнейшего
смысла в их разбиении нет.
Фактически в процессе работы G-means алгоритм k-means будет повторён k раз
20

21. Многоугольники Вороного-Дирихле

Большое распространение получили слои Кохонена, построенные следующим
образом: каждому (j-му) нейрону сопоставляется точка
в
m -мерном пространстве (пространстве сигналов).
Для входного вектора
вычисляются его евклидовы
расстояния
до точек
и «ближайший получает всё» — тот нейрон, для
которого это расстояние минимально, выдаёт единицу, остальные — нули. Следует
заметить, что для сравнения расстояний достаточно вычислять линейную функцию
сигнала:
Разбиение плоскости
на многоугольники Вороного-Дирихле
для случайно выбранных точек
(каждая точка указана в своём многоугольнике)
21