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

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

Графеева Н.Г.
2016

2. Что такое кластеризация?

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

3. Пример 1

4. Пример 1(продолжение)

• В примере явно просматриваются 4
кластера. В качестве критерия подобия
можно использовать расстояние. Два или
более объектов принадлежат одному
кластеру, если они ‘близко’ расположены
друг от друга в соответствии с выбранным
критерием (расстоянием). Такая
кластеризация называется кластеризацией
на основе расстояния.

5. Виды кластеризации

• Различают 2 вида кластеризации:
• жесткая (hard clastering)
• мягкая (soft clastering)
• При жесткой кластеризации каждый
элемент исходного data set принадлежит
только к одному кластеру, при мягкой –
может принадлежать к нескольким.

6. Как определить качество кластеризации?

• Нет никаких универсальных критериев,
которые в общем случае могут оценить
качество кластеризации (однако активные
исследования в этом направлении ведутся).
Качество кластеризации всегда привязано к
специфике конкретной задачи и, как
правило, выражается в виде какой-то
целевой
функции,
которую
надо
минимизировать или максимизировать.

7. Сферы применения кластеризации

• Маркетинг: определение групп клиентов с похожим
поведением.
• Биология: кластеризация растений и животных с
учетом их особенностей.
• Страхование: выявление групп держателей
страховых полисов в соответствии со степенью
риска.
• Землетрясения: кластеризация эпицентров с целью
выявления опасных зон.
• И т.п.

8. Проблемы кластеризации

• Не все методы кластеризации в состоянии
учитывать некоторые свойства атрибутов
кластеризуемых объектов;
• Для методов, основанных на расстояниях,
эффективность сильно зависит от
определения расстояния, которое может
определяться неоднозначно;
• Результаты кластеризации могут
трактоваться неоднозначно.

9. Нормализация значений атрибутов объектов

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

10. Пример 2

11. MinMax нормализация

• Существует много подходов для нормализации данных. Один из
наиболее распространенных - нормализация на основе минимумамаксимума. Для такого типа нормализации используется
следующая формула:
где X* — это нормализованное значение,
min(X),max(X) – минимальное и максимальное значение атрибута
X.
Примечание:данная формула располагает все координаты на
отрезке [0;1]

12. Измерение расстояний

• Для многомерных случаев популярной мерой расстояния
является метрика Минковского:
• При p=2 – метрика Евклида:
• При p=1 – Манхэттенское расстояние (расстояние
городских кварталов):

13. Как проверить качество кластеризации на основе расстояния?

• После получений результатов кластерного
анализа можно проверить правильность
кластеризации (т.е. оценить, насколько
кластеры отличаются друг от друга).
• Для этого рассчитываются средние значения
для каждого кластера. При хорошей
кластеризации должны быть получены
сильно отличающиеся средние для всех
измерений или хотя бы большей их части.

14. Алгоритм K-means

• Простейший
алгоритм
кластеризации,
основанный на определении расстояний. В
основе алгоритма – определение k центроидов
(по одному для каждого кластера). В дальнейшем
центроиды
переопределяются,
однако
их
начальное местоположение может сильно
повлиять на конечный результат. Весь смысл
алгоритма – минимизация целевой функции:

15. Шаги алгоритма K-means

1. Определить количество кластеров и выбрать начальные
центроиды для каждого кластера.
2. Сопоставить каждый анализируемый объект кластеру с
ближайшим выбранным расстоянием до центроида.
3. В каждом сформированном кластере пересчитать
местоположение центроида на основе объектов,
вошедших в кластер.
4. Повторять шаги 2 и 3 пока местоположение центроидов
не перестанет изменяться.
5. Оценить качество кластеризации. Если плохо –
вернуться к шагу 1 и изменить количество кластеров.

16. Как пересчитать местоположение центроида?

• Простейший вариант – среднее арифметическое
соответствующих координат всех объектов
кластера. Например, в двумерном случае с
координатами x и y:

17. Пример перерасчета местоположения центроидов

До перерасчета
После перерасчета

18. Недостатки k-means

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

19. Есть ли подходящие алгоритмы в готовом виде в современных СУБД?

• Практически во всех СУБД, претендующих
на Data Mining, реализован алгоритм Kmeans. Разумеется, есть аналогичная
реализация и в СУБД ORACLE.

20. ORACLE К-means

• Процесс построения соответствующей
модели разбивается на два шага:
1. Задание параметров кластеризации.
2. Построение модели кластеризации.

21. Как выглядит задание параметров кластеризации?

Создаем таблицу с параметрами:
CREATE TABLE km_settings (setting_name VARCHAR2(30), setting_value VARCHAR2(30));
Заполняем таблицу подходящими параметрами алгоритма:
BEGIN
INSERT INTO km_settings (setting_name, setting_value)
VALUES (dbms_data_mining.kmns_distance, dbms_data_mining.kmns_euclidean);
INSERT INTO km_settings (setting_name, setting_value) VALUES
(dbms_data_mining.prep_auto, dbms_data_mining.prep_auto_on);
INSERT INTO km_settings (setting_name, setting_value)
VALUES (dbms_data_mining.clus_num_clusters, '7');
END;

22. Построение модели кластеризации

declare
m_name varchar2(32) :='km';
input_tbl varchar2(32) :='points';
rec_id varchar2(32) :='rec_id';
BEGIN
DBMS_DATA_MINING.CREATE_MODEL(
model_name
=> m_name,
mining_function => dbms_data_mining.clustering,
data_table_name => input_tbl,
case_id_column_name => rec_id,
settings_table_name => 'km_settings');
END;

23. Можно ли простым пользователям облачного сервиса APEX создавать модели?

24. А где можно?

Мат-меховский APEX:
вход для администратора:
http://195.19.241.198:8080/apex/apex_admin
вход для разработчика:
http://195.19.241.198:8080/apex
Только разработчикам надо договориться о
создании account с администратором. Кто готов
быть администратором?

25. Проблема

• Есть реальные данные метеослужб о
погоде в Санкт-Петербурге в 2010 году.
Нужно проанализировать эти данные и
кластеризовать все дни 2010 года в
зависимости от погодных условий на
категории.
Оценить
качество
кластеризации.

26. Как выглядят исходные данные?

27. Какие данные имеет смысл использовать?

Как минимум следующие:
• Температура
• Скорость ветра
• Нижняя граница облачности
Может быть что-нибудь еще…

28. На что следует обратить внимание?

• Данные представляют собой различные
единицы измерения и имеют сильно
различающиеся диапазоны возможных
значений. Это означает, что нормализация
– обязательна.

29. Задание 4

На основе метеоданных Санкт-Петербурга 2010 года
требуется кластеризовать дни по погодным условиям и
• отобразить результаты кластеризации по дням
• агрегировать результаты кластеризации по месяцам
• Исходные данные – файл Saint-Petersburg_2010.xml.
• Ссылку на приложение, логин и пароль для входа
отправлять по адресу: [email protected]
• Тема - Data_Mining_2016_job4