Кластерный анализ SAS

2 , S A S I n s t i t u t e I n c . A l l r i g h t s r es er v e d .

0 1 2 , S A S I n s t i t u t e I n c . A l l r i g h t s r es er v e d .

Кластер: группа «похожих» объектов
«похожих» между собой в группе (внутриклассовое расстояние)
«не похожих» на объекты других групп
Определение неформальное, формализация зависит от метода
Кластерный анализ
Разбиение множество объектов на группы (кластеры)
Тип моделей:
«описательный» (descriptive) Data mining => одна из задач - наглядное представление кластеров
«прогнозный» (predictive) Data mining => разбиение на кластеры, а затем «классификация» новых объектов
Тип обучения:
всегда «без учителя» (unsupervised) => тренировочный набор не размечен

t © 2 0 1 2 , S A S I n s t i t u t e I n c . A l l r i g h t s r es er v e d .

Кластеризация ради кластеризации:
Выявление и описание групп (человек не способен «осознать» более 10 объектов в одной задаче, как обработать выборку с миллионами?)
«Сжатие» информации (особенно в обработке мультимедиа)
Построение различных поисковых индексов (сравниваем не со всеми, а начинаем с прототипов кластеров)
Мощнейшее средство предобработки данных:
Дискретизация
Уменьшение размера выборки (от больших объемов к «реальным»)
Обработка пропущенных значений (инициализируем и итерационно
«улучшаем» пропуски)
Поиск исключений и артефактов (что не в кластере, то под
«подозрением»)

классификации для организации наблюдаемых данных в наглядные структуры.

Термин
«Кластерный анализ» впервые введен
в 1939 году

1 2 , S A S I n s t i t u t e I n c . A l l r i g h t s r es er v e d .

Хороший метод кластеризации находит кластеры
c высоким «внутриклассовым» сходством объектов
и низким «межклассовым» сходством объектов
Оценка качества кластеризации (нет понятия «точность»)
необходима, так как влияет на выбор параметров метода
определяется либо экспертом – субъективная величина
либо «перекрестной» проверкой целевой функции кластеризации
Качество кластеризации зависит:
от метода кластеризации
от меры сходства (или расстояния)

числа кластеров)
«Пошаговое» объединение ближайших кластеров (восходящая) или разбиение наиболее удаленных (нисходящая)

Step Step Step Step 1 2 3 4
a b

d e

a b c d e c d e

Step 0
a
b c d e
Step
4

Step Step Step Step 3 2 1 0

восходящая agglomerative

C op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c . A l l r i g h t s r es er v e d .

нисходящая divisive

общий кластер,
листья - элементы
«Высота» ветвей (до пересечения) – порог расстояния «склейки» («разделения»)
Результат кластеризации
– «срез» дендрограммы

C op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c . A l l r i g h t s r es er v e d .

2 0 1 2 , S A S I n s t i t u t e I n c . A l l r i g h t s r es er v e d .

1 2 , S A S I n s t i t u t e I n c . A l l r i g h t s r es er v e d .

кластеров:
Полное связывание: наибольшее попарное расстояние. Дает компактные сферические кластеры.
Среднее связывание: усредненное попарное
расстояние. Редко используется.
Единственное связывание: наименьшее попарное расстояние. Дает «растянутые» кластеры сложной формы.
Центроидное связывание: расстояние между центрами (мат. ожидание) кластеров.
Другие методы (например метод Ward’а – минимизирует внутрикластерные дисперсии или другую целевую функцию)

C op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c . A l l r i g h t s r es er v e d .

2 , S A S I n s t i t u t e I n c . A l l r i g h t s r es er v e d .

Пример

множества X из N объектов на K непересекающихся подмножеств Ck, покрывающих X, чтобы внутриклассовое расстояние было минимальным:

Точное решение – перебор с отсечением
метод «ветвей и границ», но число комбинаций неприемлемо даже для 100 объектов:

Эвристические методы:

K-means (прототип кластера – мат. ожидание m), K-medoids
(прототип кластера – средний элемент)

ищется локальный минимум

K

Ci C j =∅, Ci = X

d (x, x′)

min Σ Σ

i=1 x∈Ci Σx′∈Ci

1

K

K ! i=1

⎛ K ⎞

S(N , K ) =

⎟ K N

⎝ i ⎠

∑(−1)K −i ⎜

i

i=1 x∈Ci

min
Ci C j =∅, Ci = X

ΣK Σ d (m , x)

C op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c . A l l r i g h t s r es er v e d .

кластеров K (где значение K выбирается по ССС на основе иерархической кластеризации) по

Шаг 1. Поиск центров:
Для всех K кластеров

Шаг 2. Расчет расстояний до центров:

и K кластеров

i

i

x C

x∈C

m =

i ∑

i

C op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c . A l l r i g h t s r es er v e d .

i

C

x∈Ci

Для всех N объектов d (m , x) = ∑ x

Шаг 3. Выбор ближайшего кластера:
x ∈Ci ⇔ i = min d (mj , x)
j
Если были перестановки, то Шаг 1.

примера.
Пересчет центров.
Переход на шаг 3 пока процесс не сошелся

C op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c . A l l r i g h t s r es er v e d .

примера.
Пересчет центров.
Переход на шаг 3 пока процесс не сошелся

C op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c . A l l r i g h t s r es er v e d .

1 2 , S A S I n s t i t u t e I n c . A l l r i g h t s r es er v e d .

АЛГОРИТМ КЛАСТЕРИЗАЦИИ K-MEANS

Выбор переменных.
Выбор k центров
кластеров.
Выбор ближайшего центра для каждого примера.
Пересчет центров.
Переход на шаг 3 пока процесс не сошелся

1 2 , S A S I n s t i t u t e I n c . A l l r i g h t s r es er v e d .

АЛГОРИТМ КЛАСТЕРИЗАЦИИ K-MEANS

Выбор переменных.
Выбор k центров
кластеров.
Выбор ближайшего центра для каждого примера.
Пересчет центров.
Переход на шаг 3 пока процесс не сошелся

2 0 1 2 , S A S I n s t i t u t e I n c . A l l r i g h t s r es er v e d .

Выбор переменных.
Выбор k центров
кластеров.
Выбор ближайшего центра для каждого примера.
Пересчет центров.
Переход на шаг 3 пока процесс не сошелся

1 2 , S A S I n s t i t u t e I n c . A l l r i g h t s r es er v e d .

Выбор переменных.
Выбор k центров
кластеров.
Выбор ближайшего центра для каждого примера.
Пересчет центров.
Переход на шаг 3 пока процесс не сошелся

АЛГОРИТМ КЛАСТЕРИЗАЦИИ K-MEANS

на шаг 3 пока процесс не сошелся

...

C op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c . A l l r i g h t s r es er v e d .

АЛГОРИТМ КЛАСТЕРИЗАЦИИ K-MEANS

1 2 , S A S I n s t i t u t e I n c . A l l r i g h t s r es er v e d .

АЛГОРИТМ КЛАСТЕРИЗАЦИИ K-MEANS

Выбор переменных.
Выбор k центров
кластеров.
Выбор ближайшего центра для каждого примера.
Пересчет центров.
Переход на шаг 3 пока процесс не сошелся

2 0 1 2 , S A S I n s t i t u t e I n c . A l l r i g h t s r es er v e d .

Выбор переменных.
Выбор k центров
кластеров.
Выбор ближайшего центра для каждого примера.
Пересчет центров.
Переход на шаг 3 пока процесс не сошелся

1 2 , S A S I n s t i t u t e I n c . A l l r i g h t s r es er v e d .

АЛГОРИТМ КЛАСТЕРИЗАЦИИ K-MEANS

Выбор переменных.
Выбор k центров
кластеров.
Выбор ближайшего центра для каждого примера.
Пересчет центров.
Переход на шаг 3 пока процесс не сошелся

1 2 , S A S I n s t i t u t e I n c . A l l r i g h t s r es er v e d .

АЛГОРИТМ КЛАСТЕРИЗАЦИИ K-MEANS

Выбор переменных.
Выбор k центров
кластеров.
Выбор ближайшего центра для каждого примера.
Пересчет центров.
Переход на шаг 3 пока процесс не сошелся

на шаг 3 пока процесс не сошелся

...

C op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c . A l l r i g h t s r es er v e d .

АЛГОРИТМ КЛАСТЕРИЗАЦИИ K-MEANS

1 2 , S A S I n s t i t u t e I n c . A l l r i g h t s r es er v e d .

Выбор переменных.
Выбор k центров
кластеров.
Выбор ближайшего центра для каждого примера.
Пересчет центров.
Переход на шаг 3 пока процесс не сошелся

АЛГОРИТМ КЛАСТЕРИЗАЦИИ K-MEANS

(для отображения матрицы данных с помощью индикаторной матрицы в прототипы кластеров) для заданной модели кластеризации с E(R2) для равномерно распределенного множества прототипов кластеров (как наихудший возможный вариант):

2

C op yr i g h t © 2 0 1 2 , S A S I n s t i t u t e I n c . A l l r i g h t s r es er v e d .

⎡1 − E(R2 ) ⎤

⎥ × K

CCC = ln ⎢ 1 − R

⎣

clust ⎦