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

У Вікіпедії є статті про інші значення цього терміна: Силует (значення).

Силует у кластерному аналізі відноситься до методу інтерпретації та перевірки узгодженості елементів кластерів даних. Цей метод забезпечує стисле графічне представлення того, наскільки добре класифіковано кожен об'єкт.^[1] Цей підхід запропонував бельгійський статистик Пітер Руссеу^[en] в 1987 році.

Величина силуету є мірою того, наскільки об'єкт схожий на власний кластер (згуртованість) порівняно з іншими кластерами (відокремлення). Значення силуету коливається від −1 до +1, де високе значення вказує на те, що об'єкт добре збігається з власним кластером і погано збігається з сусідніми кластерами. Якщо більшість об'єктів мають високе значення, то конфігурація кластеризації відповідає природі даних. Якщо багато точок мають низьке або від'ємне значення, тоді конфігурація кластеризації може мати забагато або замало кластерів.

Силует можна розрахувати за допомогою будь-якої метрики відстані, наприклад евклідової відстані або манхеттенської відстані.

Визначення

Діаграма, що показує оцінки силуетів трьох типів тварин із набору даних Zoo, відтвореного пакетом аналізу даних Orange^[en]. У нижній частині діаграми від'ємне значення силуету визначає дельфіна та морську свиню як винятки у групі ссавців. Також, до недоліків кластеризації можна зарахувати занадто велику зелену групу тварин.

Припустімо, що дані були згруповані за допомогою будь-якого методу, наприклад k-медоїдів^[en] або k-середніх, у $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}|$ — це кількість точок, що належать кластеру $i$ , а $d(i,j)$ — це відстань між точками даних $i$ та $j$ у кластері $C_{I}$ (ділимо на $|C_{I}|-1$ оскільки ми не включаємо відстань $d(i,i)$ у суму). Ми можемо інтерпретувати $a(i)$ як міру того, наскільки добре $i$ припасовоно до кластеру (чим менше значення, тим краще припасування).

Потім ми визначаємо середню несхожість точки $i$ на деякий кластер $C_{J}$ , який міг би бути найкращим кластером для точки $i$ , як середнє значення відстані від $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\leqslant s(i)\leqslant 1

Зауважте, що $a(i)$ не є чітко визначеним для кластерів із розміром в одну точку, у цьому випадку ми встановлюємо $s(i)=0$ . Цей вибір довільний, але нейтральний у тому сенсі, що він знаходиться в середині меж: -1 і 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-середніх), то, одним з наслідків, може бути суттєва відмінність у кількість точок різних кластерів. На графіку це виглядає так, що деякі з кластерів зазвичай відображатимуть набагато вужчі силуети, ніж решта (див. малюнок вище). Таким чином, діаграми з силуетами та середніми значеннями можна використовувати для визначення натуральної кількості кластерів у наборі даних. Можна також збільшити ймовірність максимізації силуету при правильній кількості кластерів шляхом повторного масштабування даних за допомогою вагових коефіцієнтів, які залежать від кластерів.^[2]

Кауфман та ін. ввели термін силуетний коефіцієнт для максимального значення середнього $s(i)$ для всіх даних набору даних,^[3] тобто,

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

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

Спрощений силует і медоїд-силует

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

a'(i)=d(i,\mu _{C_{I}})

і

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

,

який має додаткову перевагу в тому, що $a'(i)$ завжди визначено, тоді відповідно можна визначити спрощений силует і коефіцієнт спрощеного силуету^[4]

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$ -середніми), це також називається силуетом на основі медоїда^[5] або медоїд-силуетом.^[6]

Якщо кожен об'єкт присвоєно найближчому медоїду (як при кластеризації $k$ -медоїдами), ми знаємо, що $a'(i)\leqslant b'(i)$ , і отже $s'(i)={\frac {b'(i)-a'(i)}{b'(i)}}=1-{\frac {a'(i)}{b'(i)}}$ .^[6]

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

Замість використання середнього силуету для оцінки кластеризації, отриманої, наприклад, з $k$ -медоїдів або $k$ -середніх, ми можемо спробувати безпосередньо знайти рішення, яке максимізує значення силуету. Ми не маємо готового рішення, яке дозволяло б максимізувати силует, але зазвичай найкраще призначати точки найближчому кластеру, як це робиться за допомогою цих методів. Ван дер Лаан та ін.^[5] запропонував адаптувати стандартний алгоритм для $k$ -медоїдів, PAM^[en], для цієї мети та назвати цей алгоритм PAMSIL:

Виберіть початкові медоїди за допомогою PAM
Обчисліть середній силует цього початкового рішення
Для кожної пари медоїда $m$ і не медоїда $x$
1. поміняти місцями $m$ і $x$
2. обчислити середній силует отриманого рішення
3. запам'ятати найкращу заміну
Виконати найкращу заміну та повернутися до п. 3, інакше, якщо покращення не знайдено, закінчити.

Цикл на кроці 3 виконується для $O(Nk)$ пар і включає обчислення силуету для $O(N 2)$ пар точок, отже, цей алгоритм потребує $O(N 3 ki)$ часу, де $i$ — кількість ітерацій.

Оскільки це досить дорога операція, автори пропонують також використовувати силует, заснований на медоїді, і назвати отриманий алгоритм PAMMEDSIL.^[5] Для цього потрібно $O(N 2 k 2 i)$ часу.

Батул та ін. запропонували подібний алгоритм під назвою OSil і запропонували подібну до CLARA стратегію вибірки для більших наборів даних, яка вирішує проблему лише для підвибірки.^[7]

Застосувавши останні вдосконалення алгоритму PAM, FastMSC скорочує час роботи за допомогою силуету медоїда лише до $O(N 2 i)$ .^[6]

Див. також

Примітки

↑ ^а ^б Peter J. Rousseeuw (1987). Silhouettes: a Graphical Aid to the Interpretation and Validation of Cluster Analysis. Computational and Applied Mathematics. 20: 53—65. doi:10.1016/0377-0427(87)90125-7.
↑ R.C. de Amorim, C. Hennig (2015). Recovering the number of clusters in data sets with noise features using feature rescaling factors. Information Sciences. 324: 126—145. arXiv:1602.06989. doi:10.1016/j.ins.2015.06.039. S2CID 315803.
↑ Leonard Kaufman; Peter J. Rousseeuw (1990). Finding groups in data : An introduction to cluster analysis. Hoboken, NJ: Wiley-Interscience. с. 87. doi:10.1002/9780470316801. ISBN 9780471878766.
↑ Hruschka, E.R.; de Castro, L.N.; Campello, R.J.G.B. (2004). Evolutionary Algorithms for Clustering Gene-Expression Data. Fourth IEEE International Conference on Data Mining (ICDM'04). IEEE. с. 403—406. doi:10.1109/ICDM.2004.10073.
↑ ^а ^б ^в Van der Laan, Mark; Pollard, Katherine; Bryan, Jennifer (2003). A new partitioning around medoids algorithm. Journal of Statistical Computation and Simulation (англ.). 73 (8): 575—584. doi:10.1080/0094965031000136012. ISSN 0094-9655.
↑ ^а ^б ^в Lenssen, Lars; Schubert, Erich (2022). Clustering by Direct Optimization of the Medoid Silhouette. International Conference on Similarity Search and Applications (англ.). с. 190—204. doi:10.1007/978-3-031-17849-8_15. Процитовано 20 жовтня 2022.
↑ Batool, Fatima; Hennig, Christian (2021). Clustering with the Average Silhouette Width. Computational Statistics & Data Analysis (англ.). 158: 107190. doi:10.1016/j.csda.2021.107190.

Посилання

Вибір кількості кластерів за допомогою аналізу силуетів у кластеризації KMeans. scikit-learn (англ.). Процитовано 28 жовтня 2022.

[Rousseeuw_1987-1] а ^б Peter J. Rousseeuw (1987). Silhouettes: a Graphical Aid to the Interpretation and Validation of Cluster Analysis. Computational and Applied Mathematics. 20: 53—65. doi:10.1016/0377-0427(87)90125-7.

[2] R.C. de Amorim, C. Hennig (2015). Recovering the number of clusters in data sets with noise features using feature rescaling factors. Information Sciences. 324: 126—145. arXiv:1602.06989. doi:10.1016/j.ins.2015.06.039. S2CID 315803.

[3] Leonard Kaufman; Peter J. Rousseeuw (1990). Finding groups in data : An introduction to cluster analysis. Hoboken, NJ: Wiley-Interscience. с. 87. doi:10.1002/9780470316801. ISBN 9780471878766.

[4] Hruschka, E.R.; de Castro, L.N.; Campello, R.J.G.B. (2004). Evolutionary Algorithms for Clustering Gene-Expression Data. Fourth IEEE International Conference on Data Mining (ICDM'04). IEEE. с. 403—406. doi:10.1109/ICDM.2004.10073.

[Van_der_Laan-5] а ^б ^в Van der Laan, Mark; Pollard, Katherine; Bryan, Jennifer (2003). A new partitioning around medoids algorithm. Journal of Statistical Computation and Simulation (англ.). 73 (8): 575—584. doi:10.1080/0094965031000136012. ISSN 0094-9655.

[Lenssen-6] а ^б ^в Lenssen, Lars; Schubert, Erich (2022). Clustering by Direct Optimization of the Medoid Silhouette. International Conference on Similarity Search and Applications (англ.). с. 190—204. doi:10.1007/978-3-031-17849-8_15. Процитовано 20 жовтня 2022.

[7] Batool, Fatima; Hennig, Christian (2021). Clustering with the Average Silhouette Width. Computational Statistics & Data Analysis (англ.). 158: 107190. doi:10.1016/j.csda.2021.107190.

[1]

[2]

[3]

[4]

[5]

[6]

[7]