Файл: Кластеризация "Some of the figures in this presentation are taken from "An Introduction to Statistical.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 12.12.2023
Просмотров: 34
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Кластеризация "Some of the figures in this presentation are taken from "An Introduction to Statistical
Learning, with applications in R" (Springer,
2013) with permission from the authors: G.
James, D. Witten, T. Hastie and R. Tibshirani "
Обучение «без учителя»
•
Регрессия и классификация – методы обучения «с учителем». При
обучении «с учителем» у нас обычно есть набор характеристик
X
1
,X
2
,...,X
p
, измеренных в n наблюдениях, и отклик Y, также
измеренный в тех же n наблюдениях. Цель – предсказать Y, используя
X
1
,X
2
,...,X
p
.
•
Обучение «без учителя» -- набор статистических инструментов, в
которых входными данными является набор характеристик
X
1
,X
2
,...,X
p
, измеренных в n наблюдениях. Здесь мы не заинтересованы
в прогнозировании, потому что нет ассоциированной переменной
отклика Y. Целью является обнаружение новых неизвестных знаний
об измерениях X
1
,X
2
,...,X
p
.
Примерами методов обучения «без
учителя» являются кластеризация, поиск ассоциативных правил и
анализ главных компонент.
•
Кластеризация – широкий класс методов для обнаружения
неизвестных подгрупп в данных.
•
Поиск ассоциативных правил – поиск закономерностей в
транзакционных данных.
•
Анализ главных компонент – процесс , при котором вычисляются
главные компоненты данных, а затем используются для понимания
данных.
Трудности обучения «без учителя»
•
В методах обучения «без учителя» нет простой цели –
прогнозирования поведения отклика Y. Обучение «без
учителя» часто выполняется как часть объясняющего
анализа данных. Также нет методов проверки
результатов этих методов.
•
Но методы обучения «без учителя» являются очень
важными.
•
Например, исследователь, занимающийся проблемой
рака, может искать подгруппы среди образцов
опухолей или среди генов, которые помогут ему лучше
понять природу рака.
•
Поисковая система может определять, какие
результаты выводить конкретному пользователю,
основываясь на истории запросов пользователей с
похожими шаблонами поиска.
Кластеризация
•
Кластеризацией называют очень широкое
множество методик для нахождения подгрупп или
кластеров в множестве данных. Когда мы
кластеризуем наблюдения в множестве данных, мы
ищем такое их разбиение на отдельные группы,
что наблюдения в каждой группе похожи, а в
разных группах сильно отличаются. Поэтому
нужно определить, что для двух или большего
наблюдений обозначает быть похожими или быть
различными. Часто это определяется областью
определения, и основывается на изучаемых данных.
Но очень важно то, что кластеризация ищет
однородные подгруппы наблюдений.
Основные методы кластеризации
•
Метод кластеризации К-средних (K-means) и иерархическая
кластеризация являются наиболее популярными методами.
При кластеризации методом К-средних, мы ищем разделение
множества наблюдений на предопределенное число кластеров.
С другой стороны, в иерархической кластеризации мы не знаем
заранее, сколько кластеров хотим получить. Фактически,
алгоритм заканчивается дерево-подобным визуальным
представлением наблюдений, называемым дендрограммой,
которая позволяет нам увидеть разбиения, полученные для
каждого возможного числа кластеров, от 1 до n. Каждый из
подходов имеет свои преимущества и недостатки.
•
Можно кластеризовать наблюдения на основе характеристик,
т.е. находить подгруппы среди наблюдений. Также можно
кластеризовать нахарактеристики на основе наблюдений, т.е.
находить подгруппы среди характеристик. Далее будем
обсуждать кластеризацию наблюдений, т.к. второй вариант
достигается транспонированием матрицы данных.
Кластеризация К-средних
•
Кластеризация К-средних – простой метод разделения
множества данных на К различных непересекающихся
кластеров. Для выполнения кластеризации сначала
нужно определить желаемое число кластеров К, затем
алгоритм К-средних будет относить каждое
наблюдение в точности к одному из К кластеров.
Математические основания для кластеризации
•
Пусть C
1
, . . ., C
K
–
множества, содержащие индексы
наблюдений в каждом кластере. Эти множества
удовлетворяют двум свойствам:
• 1. C
1
∪
C
2
∪
. . .
∪
C
K
= {1, . . ., n}.
Т.е. каждое наблюдение
принадлежит по крайней мере одному из К кластеров.
• 2. C
k
∩ C
k’
=
∅
для всех k ≠ k’. Другими словами, кластеры не
пересекаются.
•
Например, если i-е наблюдение принадлежит k-му кластеру, то
i
∈
C
k
.
Идея, которая стоит за кластеризацией К-средних
состоит в том, что хорошей является та кластеризация, для
которой внутри-кластерная вариация настолько мала,
насколько это возможно. Внутри-кластерная вариация для
кластера C
k
это мера W(C
k
)
количества, на которое
наблюдения внутри кластера отличаются друг от друга.
Следовательно, нам нужно решить задачу
(1)
Внутри-кластерная вариация
•
Есть много возможных способов определения
этого понятия, но пока самым общим является
использование квадрата Евклидова расстояния,
т.е. внутри-кластерную вариацию определяют как
(2)
где |C
k
|
обозначает число наблюдений в k-м
кластере. Объединение (1) и (2) дает задачу
оптимизации, которая определяет кластеризацию
К-средних
(3)
Алгоритм K-средних
Следующий алгоритм находит локальный
минимум задачи (3) – достаточно хорошее
решение.
1.
Произвольным образом присваиваем номер от 1 до
К каждому из наблюдений. Это послужит
начальным разделением на классы.
2.
Повторяем, пока разбиение на классы не
перестанет меняться:
(a)
Для каждого из К кластеров вычисляем
кластерный центроид. Центроид k-го кластера –
это вектор средних p характеристик для
наблюдений в k-м кластере.
(b)
Относим каждое наблюдение к тому кластеру,
чей центроид ближайший (где ближайший
определяется с использованием Евклидова
расстояния).
Алгоритм К-средних
•
Приведенный алгоритм гарантирует
уменьшение целевой функции (3) на каждом
шаге. Это происходит в силу следующего
тождества:
•
где - это среднее
характеристики j в классе C
k
. Это значит,
что при использовании алгоритма К-средних
целевая функция (3) будет невозрастать, и
когда результат перестанет меняться, будет
достигнут локальный минимум.
Процесс кластеризации для K=3. В правом нижнем углу – результат кластеризации после
10 итераций.
Выбор начальных кластеров
•
Так как алгоритм К-средних находит
локальный, а не глобальный минимум, его
результат зависит от выбора начальных
(случайных) кластеров. Поэтому важно
запустить алгоритм несколько раз для
различных случайных начальных
конфигураций. Затем выбирается
наилучшее решение, т.е. то, для которого
значение целевой функции (3) будет
минимальным.
Различные итоговые кластеры
На картинке – итоги
кластеризации К-
средних для К=3,
выполненная 6 раз с
разными начальными
кластерами. Над
каждым рисунком –
значение целевой
функции. Найдены
три локальных
минимума, один из
которых
выражается в
наименьшем
значении целевой
функции, и дает
наилучшее
разделение на
кластеры.
Иерархическая кластеризация
•
Потенциальный недостаток кластеризации К-
средних – предопределение числа кластеров К.
Иерархическая кластеризация – это
альтернативный подход, который не требует
выбора К. Результат иерархической кластеризации
представляется в древообразном представлении
наблюдений, называемом дендрограммой. Будем
рассматривать агломеративную кластеризацию.
Это наиболее общий тип иерархической
кластеризации. Дендрограмма строится, начиная с
листьев, и объединяет кластеры к корню дерева.
Интерпретация дендрограммы
•
Рассмотрим искусственно
сгенерированные 45
наблюдений в 2-мерном
пространстве, в реальности
разделенные на 3 класса.
•
Предположим, что мы
наблюдаем данные без
метки класса и применяем
для них метод
иерархической
кластеризации.
Рисунок 1. Дендрограмма
Интерпретация дендрограммы
•
В левой части рис. 1 каждый лист дендрограммы
представляет одно из 45 исходных наблюдений. Но по мере
того, как мы продвигаемся вверх к корню, некоторые листья
начинают сливаться в ветви. Они соответствуют
наблюдениям, которые похожи друг на друга. При
продвижении вверх по дереву ветви сливаются с листьями или
с другими ветвями. Чем раньше (ниже на дереве) происходит
слияние, тем больше похожи группы наблюдений друг на друга.
С другой стороны, наблюдения, которые сливаются позже
(возле верхушки дерева), могут сильно отличаться. Это
утверждение можно сформулировать точно: для любых двух
наблюдений можно найти точку на дереве, где ветви ,
содержащие эти наблюдения, впервые сливаются. Высота
этой точки слияния, измеренная по вертикальной оси,
указывает, насколько различаются эти наблюдения. Таким
образом, наблюдения, которые сливаются в самом низу дерева,
очень похожи друг на друга, в то время как наблюдения,
которые сливаются близко к верху дерева, будут скорее всего
сильно различаться.
Интерпретация простой дендрограммы
•
Слева на рисунке изображена дендрограмма, построенная с
использованием Евклидова расстояния с полной связью. Наблюдения 5
и 7 подобны, также, как и наблюдения 1 и 6. Однако наблюдение 9 не
более подобно наблюдению 2, чем наблюдениям 8, 5 и 7, несмотря на
то, что наблюдения 9 и 2 близки по горизонтали. Это происходит
потому, что все наблюдения 2, 8, 5 и 7 сливаются с наблюдением 9 на
одинаковой высоте, примерно 1.8.
•
Справа на рисунке изображены исходные данные для дендрогаммы.
На этом рисунке видно, что наблюдение 9 не ближе к 2, чем к 8, 5 и 7.
Определение кластеров на основе дендрограммы
•
Разрежем дендрограмму по горизонтали, как это
показано в центре и справа на рис. 1. Отдельные
множества наблюдений, которые находятся снизу от
разреза могут рассматриваться в качестве кластеров.
В центре рис. 1 разрез дендрограммы на высоте 9 дает
2 кластера, показанных разными цветами. Справа
разрез дендрограммы на высоте 5 дает 3 кластера.
Можно сделать и другие разрезы дендрограммы. 1
кластер получится, если не разрезать, а на высоте 0
будет n кластеров, т.е. каждое измерение будет
отдельным кластером. Другими словами, высота
разреза дендрограммы играет ту же роль, что и К в
кластеризации К-средних: контролирует число
полученных кластеров.
Выбор числа кластеров
•
Таким образом, одна дендрограмма может использоваться для
получения любого числа кластеров. На практике, часто приемлемое
число кластеров выбирается визуально на основе высоты слияния и
желаемого числа кластеров. В случае рис.1 таким будет выбор 2 или
3 кластеров. Однако, не всегда выбор так очевиден.
•
Например, предположим, что множество наблюдений
соответствует группе людей 50/50 состоящей из мужчин и женщин,
и содержащей поровну американцев, японцев и французов. Можно
представить сценарий, при котором наилучшее деление на 2 группы
разделит этих людей по гендерному признаку, а лучшее деление на 3
группы разделит их по национальности. Но в этой ситуации
кластеры не будут объединяться, в том смысле, что лучшее деление
на 3 группы не происходит из лучшего деления на 2 группы и деления
одной из этих групп. Следовательно, эта ситуация не может быть
хорошо представлена иерархической кластеризацией. Поэтому
иерархическая кластеризация иногда может давать худшие (менее
точные) результаты, чем кластеризация К-средних для данного числа
кластеров.
Алгоритм иерархической кластеризации
•
Начнем с определения меры отличия (несхожести)
между каждой парой наблюдений. Чаще всего
используется Евклидово расстояние. Алгоритм
продолжается итеративно. Начиная с дна
дендрограммы каждое из n наблюдений
рассматриваются свой собственный кластер. Два
кластера, которые наиболее подобны, сливаются,
так что становится n-1 кластер. Затем опять
наиболее подобные 2 кластера сливаются, и
становится n-2 кластера. Алгоритм
продолжается, пока не получится 1 кластер, и
дендрограмма не станет завершенной.