Силуэт (кластеризация)

Силуэт относится к методу интерпретации и проверки согласованности кластеров данных . Этот метод обеспечивает краткое графическое представление того, насколько хорошо был классифицирован каждый объект. Его предложил бельгийский статистик Питер Русси в 1987 году.

Значение силуэта — это мера того, насколько объект похож на собственный кластер (сплоченность) по сравнению с другими кластерами (разделение). Силуэт находится в диапазоне от -1 до +1, где высокое значение указывает на то, что объект хорошо соответствует собственному кластеру и плохо соответствует соседним кластерам. Если большинство объектов имеют высокое значение, то конфигурация кластеризации подходит. Если многие точки имеют низкое или отрицательное значение, возможно, в конфигурации кластеризации слишком много или слишком мало кластеров. Кластеризация со средней шириной силуэта более 0,7 считается «сильной», значение более 0,5 — «разумной», а более 0,25 — «слабой», но с увеличением размерности данных становится затруднительно достичь столь высоких значений из-за проклятие размерности , поскольку расстояния становятся более похожими. Оценка силуэта предназначена для измерения качества кластеров, когда кластеры имеют выпуклую форму, и может не работать должным образом, если кластеры данных имеют неправильную форму или разные размеры. Силуэт можно рассчитать с помощью любой метрики расстояния , например евклидова расстояния или манхэттенского расстояния .

Определение

График, показывающий оценки силуэтов трех типов животных из набора данных Zoo, полученные с помощью пакета интеллектуального анализа данных Orange . В нижней части графика силуэт идентифицирует дельфинов и морских свиней как выпадающие из группы млекопитающих.

Предположим, что данные были кластеризованы с помощью любого метода, такого как k-medoids или k-means , в $k$ кластеры.

Для точки данных $i\in C_{I}$ (точка данных $i$ в кластере $C_{I}$), позволять

$a(i)={\frac {1}{|C_{I}|-1}}\sum _{j\in C_{I},i\neq j}d(i,j)$

быть средним расстоянием между $i$ и все остальные точки данных в том же кластере, где $|C_{I}|$ количество точек, принадлежащих кластеру $C_{I}$, и $d(i,j)$ расстояние между точками данных $i$ и $j$ в кластере $C_{I}$ (делим на $|C_{I}|-1$ потому что мы не учитываем расстояние $d(i,i)$ в сумме). Мы можем интерпретировать $a(i)$ как мера того, насколько хорошо $i$ присваивается его кластеру (чем меньше значение, тем лучше назначение).

Затем мы определяем среднее различие точек $i$ в какой-то кластер $C_{J}$ как среднее расстояние от $i$ во все точки в $C_{J}$ (где $C_{J}\neq C_{I}$).

Для каждой точки данных $i\in C_{I}$, мы теперь определим

$b(i)=\min _{J\neq I}{\frac {1}{|C_{J}|}}\sum _{j\in C_{J}}d(i,j)$

быть наименьшим (отсюда и $\min$ оператор в формуле) среднее расстояние $i$ ко всем точкам любого другого кластера (т. е. любого кластера, в котором $i$ не является членом). Кластер с наименьшим средним различием называется «соседним кластером» $i$ потому что это следующий наиболее подходящий кластер для точки $i$.

Теперь мы определяем силуэт (значение) одной точки данных. $i$

$s(i)={\frac {b(i)-a(i)}{\max\{a(i),b(i)\}}}$, если $|C_{I}|>1$

и

$s(i)=0$, если $|C_{I}|=1$

Что также можно записать как:

$s(i)={\begin{cases}1-a(i)/b(i),&{\mbox{if }}a(i)<b(i)\\0,&{\mbox{if }}a(i)=b(i)\\b(i)/a(i)-1,&{\mbox{if }}a(i)>b(i)\\\end{cases}}$

Из приведенного выше определения ясно, что

$-1\leq s(i)\leq 1$

Обратите внимание, что $a(i)$ не определено четко для кластеров с размером = 1, и в этом случае мы устанавливаем $s(i)=0$. Этот выбор произволен, но нейтрален в том смысле, что он находится в середине границ -1 и 1.

Для $s(i)$ чтобы быть близким к 1, нам нужно $a(i)\ll b(i)$. Как $a(i)$ является мерой того, насколько различны $i$ относится к своему кластеру, небольшое значение означает, что он хорошо согласован. Кроме того, большое $b(i)$ подразумевает, что $i$ плохо согласован с соседним кластером. Таким образом, $s(i)$ близкое к 1 означает, что данные правильно кластеризованы. Если $s(i)$ близко к -1, то по той же логике мы видим, что $i$ было бы более подходящим, если бы он был сгруппирован в соседнем кластере. Ан $s(i)$ близкое к нулю означает, что данные находятся на границе двух естественных кластеров.

Среднее $s(i)$ по всем точкам кластера — это мера того, насколько плотно сгруппированы все точки в кластере. Таким образом, среднее значение $s(i)$ по всем данным всего набора данных является мерой того, насколько правильно данные были кластеризованы. Если кластеров слишком много или слишком мало, что может произойти при неудачном выборе $k$ используется в алгоритме кластеризации (например, k-means ), некоторые кластеры обычно отображают гораздо более узкие силуэты, чем остальные. Таким образом, силуэтные графики и средства можно использовать для определения натурального числа кластеров в наборе данных. Можно также повысить вероятность максимизации силуэта при правильном количестве кластеров, повторно масштабируя данные с использованием весов признаков, специфичных для кластера.

Кауфман и др. ввел термин «коэффициент силуэта» для максимального значения среднего значения. $s(i)$ по всем данным всего набора данных, то есть,

$SC=\max _{k}{\tilde {s}}\left(k\right),$

где ${\tilde {s}}\left(k\right)$ представляет собой среднее значение $s(i)$ по всем данным всего набора данных для определенного количества кластеров $k$.

Упрощенный силуэт и медоидный силуэт

Для расчета коэффициента силуэта нужны все ${\mathcal {O}}(N^{2})$ попарные расстояния, что делает эту оценку намного более дорогостоящей, чем кластеризация с помощью k-средних. Для кластеризации с центрами $\mu _{C_{I}}$ для каждого кластера $C_{I}$, мы можем использовать следующий упрощенный силуэт для каждой точки $i\in C_{I}$ вместо этого, который можно вычислить, используя только ${\mathcal {O}}(Nk)$ расстояния:

$a'(i)=d(i,\mu _{C_{I}})$ и $b'(i)=\min _{C_{J}\neq C_{I}}d(i,\mu _{C_{J}})$,

что имеет дополнительное преимущество, заключающееся в том, что $a'(i)$ всегда определен, затем определите соответственно упрощенный силуэт и коэффициент упрощенного силуэта.

$s'(i)={\frac {b'(i)-a'(i)}{\max\{a'(i),b'(i)\}}}$

$SC'=\max _{k}{\frac {1}{N}}\sum _{i}s'\left(i\right)$.

Если центрами кластеров являются медоиды (как при кластеризации k-медоидов), а не средние арифметические значения (как при кластеризации k-средних), это также называется силуэтом на основе медоидов. или медоидный силуэт.

Если каждый объект присвоен ближайшему медоиду (как при кластеризации k-медоидов), мы знаем, что $a'(i)\leq b'(i)$, и, следовательно, $s'(i)={\frac {b'(i)-a'(i)}{b'(i)}}=1-{\frac {a'(i)}{b'(i)}}$.

Кластеризация силуэтов

Вместо использования среднего силуэта для оценки кластеризации, полученной, например, из k-медоидов или k-средних, мы можем попытаться напрямую найти решение, которое максимизирует силуэт. У нас нет решения в замкнутой форме, позволяющего максимизировать это, но обычно лучше всего назначать точки ближайшему кластеру, как это делается с помощью этих методов. Ван дер Лаан и др. предложил адаптировать для этой цели стандартный алгоритм для k-медоидов PAM и назвать этот алгоритм PAMSIL:

1. Выберите начальные медоиды с помощью PAM.
2. Вычислите средний силуэт этого первоначального решения.
3. Для каждой пары медоида m и немедоида x
   1. поменять местами м и х
   2. вычислить средний силуэт полученного решения
   3. вспомни лучший обмен
   4. поменяйте местами m и x для следующей итерации
4. Выполните лучший обмен и вернитесь к пункту 3, в противном случае остановитесь, если улучшения не обнаружено.

Цикл на шаге 3 выполняется в течение ${\mathcal {O}}(Nk)$ пар и включает в себя вычисление силуэта в ${\mathcal {O}}(N^{2})$, следовательно, этот алгоритм нуждается ${\mathcal {O}}(N^{3}ki)$ время, где i — количество итераций.

Поскольку это достаточно дорогостоящая операция, авторы предлагают также использовать силуэт на основе медоида и называть полученный алгоритм PAMMEDSIL. Это требует ${\mathcal {O}}(N^{2}k^{2}i)$ время.

Батул и др. предложите аналогичный алгоритм под названием OSil и предложите стратегию выборки, подобную CLARA, для больших наборов данных, которая решает проблему только для подвыборки.

Приняв последние улучшения алгоритма PAM, FastMSC сокращает время выполнения с использованием медоидного силуэта до всего ${\mathcal {O}}(N^{2}i)$.

Начав с максимального количества кластеров k _max и итеративно удаляя худший центр (с точки зрения изменения силуэта) и повторно оптимизируя, можно автоматически определить лучшую кластеризацию (самый высокий медоидный силуэт). Поскольку структуры данных можно использовать повторно, это существенно снижает затраты на вычисления при многократном запуске алгоритма для различного количества кластеров. Этот алгоритм требует попарных расстояний и обычно реализуется с помощью матрицы попарных расстояний. ${\mathcal {O}}(N^{2})$ Требования к памяти являются основным ограничивающим фактором для применения этого метода к очень большим наборам данных.

См. также

• Кластерный анализ
• Индекс Дэвиса-Булдина
• Индекс Калинского-Харабаша
• Индекс Данна
• Определение количества кластеров в наборе данных