Файл: Кластеризация "Some of the figures in this presentation are taken from "An Introduction to Statistical.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 12.12.2023
Просмотров: 35
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Алгоритм иерархической кластеризации
1.
Начинаем с n наблюдений и меры (например,
Евклидова расстояния) всех C
n
2
= n(n
−1)/2 попарных
расстояний между кластерами. Рассматриваем
каждое наблюдение как отдельный кластер.
2.
Для i = n, n − 1, . . . , 2:
(a)
Рассматриваем все попарные межкластерные
расстояния между i кластерами и определяем пару
кластеров, которые наименее неподобны (т.е.
наиболее подобны, с наименьшим расстоянием).
Объединяем эти два кластера. Расстояние между
этими двумя кластерами указывает на высоту в
дендрограмме, на которой это слияние должно быть
расположено.
(b)
Вычисляем новые попарные межкластерные
расстояния между i − 1 оставшимися кластерами.
Межкластерное расстояние
•
Как определить расстояние между кластерами,
содержащими несколько наблюдений?
•
Концепция расстояния между парами наблюдений
должна быть расширена на пары групп
наблюдений. Это расширение достигается с
помощью разработки понятия связи (linkage),
которое определяем расстояние между группами
наблюдений. Четыре наиболее общих типа связей --
полная, средняя, одиночная и центроидная –
приведены в следующей таблице.
Связь
Описание
Полная
Максимальное межкластерное расстояние. Вычисляются все
попарные расстояния между наблюдениями кластера А и
наблюдениями кластера В, и записывается наибольшее из этих
расстояний.
Одиночная
Минимальное межкластерное расстояние. Вычисляются все
попарные расстояния между наблюдениями кластера А и
наблюдениями кластера В, и записывается наименьшее из этих
расстояний. Одиночная связь может приводить к расширенным,
протяженным кластерам, в которых одиночные наблюдения
объединяются по одному за раз.
Средняя
Среднее межкластерное расстояние. Вычисляются все
попарные расстояния между наблюдениями кластера А и
наблюдениями кластера В, и записывается среднее этих
расстояний.
Центроидная Расстояние между центроидом кластера А (вектором средних
длины p) и центроидом кластера В. Центроидная связь может
приводить к нежелательным инверсиям.
Выбор типа связи
•
Средняя, полная и одиночная связи наиболее популярны у
статистиков. Средней и полной связям отдается
предпочтение перед одиночной связью, т.к. они
приводят к более сбалансированным дендрограммам.
Центроидная связь часто используется в работе с
генами, но имеет существенный недостаток –
появление инверсий. Инверсия – это объединение двух
кластеров на высоте более низкой, чем каждый из этих
отдельных кластеров в дендрограмме. Это приводит к
трудностям с визуализацией и интерпретацией
дендрограммы. Расстояния, вычисляемые на шаге 2(b)
алгоритма иерархической кластеризации, зависят как
от от типа используемой связи, так и от выбора меры
расстояния (несхожести). Следовательно, итоговая
дендрограмма очень сильно зависит от типа
используемой связи.
Иллюстрация первых шагов алгоритма иерархической кластеризации, использующего
Евклидово расстояние и полную связь
Применение полной, средней и одиночной связи к данным из примера. Средняя и полная связи приводят к более сбалансированным кластерам.
Выбор меры расстояния
(несхожести)
•
До сих пор в примерах использовалось Евклидово расстояние в
качестве меры несхожести. Но иногда предпочтительнее
использовать другие меры. Например, расстояние, основанное
на корреляции, считает, что два наблюдения подобны, если их
характеристики высоко коррелированы, даже если
наблюдаемые значения находятся далеко в терминах Евклидова
расстояния. Это необычное использование корреляции,
которая обычно вычисляется между переменными, а здесь
вычисляется между профилями наблюдений для каждой пары
наблюдений. Расстояние, основанное на корреляции,
фокусируется на форме профилей наблюдений, а не на их
величинах.
•
В общем, нужно очень внимательно относиться к типу
кластеризуемых данных и вопросу, на который мы хотим
получить ответ с помощью кластеризации. Это поможет
выбрать тип расстояния, используемого в иерархической
кластеризации.
Использование Евклидова и основанного на корреляции расстояния
•
Показаны 3 наблюдения из 20 переменных. Наблюдения 1 и 3 имеют
похожие значения для каждой переменно, поэтому между ними будет
маленькое Евклидово расстояние. Но они слабо коррелируют, поэтому
между ними будет большое расстояние, основанное на корреляции. С
другой стороны, наблюдения 1 и 2 имеют совершенно различные значения
для каждой переменной, поэтому Евклидово расстояние между ними будет
большим. Но они сильно коррелируют, поэтому расстояние, основанное на
корреляции, будет маленьким.
Пример
Интерпретация примера
•
Эклектичный онлайновый розничный продавец продает 2 вида товаров:
носки и компьютеры.
•
Слева изображено количество пар носков и компьютеров, приобретенных 8
онлайновыми покупателями. Покупатели показаны разным цветом. Если
использовать Евклидово расстояние для межкластерного расстояния, не
изменяя переменные, то число купленных компьютеров почти не будет
влиять на результат. Это может быть нежелательно, т.к. (1) компьютеры
более дорогие, чем носки, и продавец может быть более заинтересован в
том, чтобы покупатели покупали компьютеры, а не носки, и (2) большая
разница в числе носков, купленных двумя покупателями, может быть менее
информативно в отношении общих предпочтений покупателя, чем маленькая
разница в числе купленных компьютеров.
•
В центре показаны те же самые данные после масштабирования каждой
переменной на СКО. Теперь число купленных компьютеров будет иметь
значительно больший эффект на межкластерные расстояния.
•
Справа изображены те же данные, но теперь ось y представляет сумму в
долларах, потраченную каждым покупателем на носки и на компьютеры. Так
как компьютеры значительно дороже носков, теперь история покупок
компьютеров будет влиять на полученные межкластерные расстояния.
Маленькие решения с большими последствиями
•
Чтобы применять алгоритм кластеризации, нужно сначала принять
несколько решений.
1.
Нужно ли сначала стандартизировать наблюдения или характеристики?
Например, возможно переменные нужно центрировать, чтобы у них было
нулевое мат. ожидание, и масштабировать, чтобы получить единичное
СКО.
2.
В случае иерархической кластеризации
•
Какую меру расстояния использовать?
•
Какой тип связи использовать?
•
Где разрезать дендрограмму, чтобы получить кластеры?
3.
В случае кластеризации К-средних, какое число кластеров мы будем
искать?
Каждое из этих решений сильно влияет на результат. На практике пробуют
несколько вариантов, а затем выбирают тот, которые дает наиболее полезное
или объяснимое решение. Нет единственного правильного ответа – каждое
решение может раскрывать какие-нибудь интересные факты в данных.