Презентация на тему SAS ENTERPRISE MINER КЛАСТЕРИЗАЦИЯ

SAS ENTERPRISE MINER
КЛАСТЕРИЗАЦИЯ

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 .

Sample

Explore Modify

Model

Assess

КОНЦЕПЦИЯ SEMMA

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 .

ЧТО ЕСТЬ КЛАСТЕР?

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 .

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

ПРИМЕНЕНИЕ МЕТОДОВ КЛАСТЕРИЗАЦИИ В
ЗАДАЧАХ АНАЛИЗА ДАННЫХ

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 .

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

Алгоритмы кластерного анализа

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

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

Применение кластеризации – группировка объектов

Применение кластеризации – распознавание образов

Применение кластеризации – классификация результатов поиска

Кластерный анализ – как инструмент интегральной оценки коммерческих банков

Кластерный анализ – как инструмент интегральной оценки коммерческих банков

Кластерный анализ – как инструмент интегральной оценки коммерческих банков

Кластерный анализ – как инструмент интегральной оценки коммерческих банков

Кластерный анализ – как инструмент интегральной оценки коммерческих банков

КАЧЕСТВО КЛАСТЕРИЗАЦИИ

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 .

Хороший метод кластеризации находит кластеры
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 .

ИЕРАРХИЧЕСКАЯ КЛАСТЕРИЗАЦИЯ - DEMO

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 .

УРОВНИ КЛАСТЕРИЗАЦИИ

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 .

ОЦЕНКА БЛИЗОСТИ КЛАСТЕРОВ

Расчет расстояния на основе попарных расстояний между элементами различных кластеров:
Полное связывание: наибольшее попарное расстояние. Дает компактные сферические кластеры.
Среднее связывание: усредненное попарное
расстояние. Редко используется.
Единственное связывание: наименьшее попарное расстояние. Дает «растянутые» кластеры сложной формы.
Центроидное связывание: расстояние между центрами (мат. ожидание) кластеров.
Другие методы (например метод 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 .

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 .

Пример

КЛАСТЕРИЗАЦИЯ НА ОСНОВЕ СТРОГОЙ ГРУППИРОВКИ (PARTITIONING):
Основная задача:
Найти такое разбиение C исходного множества 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-MEANS В ENTERPRISE MINER
Шаг 0. Инициализация:
произвольное разбиение на заданное число кластеров 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.

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

Training Data

Выбор переменных.
Выбор k центров
кластеров.
Выбор ближайшего центра для каждого примера.
Пересчет центров.
Переход на шаг 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

Training Data

Выбор переменных.
Выбор k центров
кластеров.
Выбор ближайшего центра для каждого примера.
Пересчет центров.
Переход на шаг 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 .

Training Data

...

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

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

Training Data

...

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

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

Training Data

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

...

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 центров
кластеров.
Выбор ближайшего центра для каждого примера.
Пересчет центров.
Переход на шаг 3 пока процесс не сошелся

Training Data

...

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 центров
кластеров.
Выбор ближайшего центра для каждого примера.
Пересчет центров.
Переход на шаг 3 пока процесс не сошелся

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

Training Data

Выбор переменных.
Выбор k центров
кластеров.
Выбор ближайшего центра для каждого примера.
Пересчет центров.
Переход на шаг 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

Training Data

...

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

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

Training Data

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

...

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 центров
кластеров.
Выбор ближайшего центра для каждого примера.
Пересчет центров.
Переход на шаг 3 пока процесс не сошелся

Training Data

...

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

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

Training Data

...

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

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

Training Data

Выбор переменных.
Выбор k центров
кластеров.
Выбор ближайшего центра для каждого примера.
Пересчет центров.
Переход на шаг 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

Training Data

...

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 центров
кластеров.
Выбор ближайшего центра для каждого примера.
Пересчет центров.
Переход на шаг 3 пока процесс не сошелся

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

ОПРЕДЕЛЕНИЕ ЧИСЛА КЛАСТЕРОВ

•

•

SAS Cubic Clustering Criterion (CCC) (Sarle, 1983)
Основная идея: сравнение R2 (для отображения матрицы данных с помощью индикаторной матрицы в прототипы кластеров) для заданной модели кластеризации с 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 

ОПРЕДЕЛЕНИЕ ЧИСЛА КЛАСТЕРОВ

1.

2.

3.

4.

Случайно выбираются центры для большого (50 по умолчанию) числа кластеров Все наблюдения объединяются в эти случайные кластеры Решается задач восходящей иерархической кластеризации, на каждом шаге считается CCC
По определенным правилам выбирается оптимальное число кластеров:
Первый локальный пик …

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 .