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

Шаблон:Otheruses Силует у кластерному аналізі відноситься до методу інтерпретації та перевірки узгодженості елементів кластерів даних. Цей метод забезпечує стисле графічне представлення того, наскільки добре класифіковано кожен об'єкт. Цей підхід запропонував бельгійський статистик Шаблон:Нп в 1987 році.

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

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

Визначення

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

Припустімо, що дані були згруповані за допомогою будь-якого методу, наприклад Шаблон:Нп або k-середніх, у Шаблон:Math кластерів.

Для точки даних $i\in C_I$ (точка даних Шаблон:Math в кластері $C_I$), обчислимо

$a(i)=\frac{1}{|C_I|-1}\sum _{j\in C_I,i\ne j}d(i,j)$

яке є середньою відстанню між Шаблон:Math та всіма іншими точками даних у тому самому кластері, де $|C_I|$ — це кількість точок, що належать кластеру Шаблон:Math, а Шаблон:Math — це відстань між точками даних Шаблон:Math та Шаблон:Math у кластері $C_I$ (ділимо на $|C_I|-1$ оскільки ми не включаємо відстань Шаблон:Math у суму). Ми можемо інтерпретувати Шаблон:Math як міру того, наскільки добре Шаблон:Math припасовоно до кластеру (чим менше значення, тим краще припасування).

Потім ми визначаємо середню несхожість точки Шаблон:Math на деякий кластер $C_J$, який міг би бути найкращим кластером для точки Шаблон:Math, як середнє значення відстані від Шаблон:Math до всіх точок $C_J$ (де $C_J\ne C_I$).

Для кожної точки даних $i\in C_I$, тепер визначимо

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

найменший (тому, оператор $\min$ у формулі), бо маємо порівнювати з найближчим кластером, означає відстань Шаблон:Math до всіх точок у будь-якому іншому кластері (тобто в будь-якому кластері, членом якого Шаблон:Math не є). Кластер із цією найменшою середньою різницею називають «сусіднім кластером» Шаблон:Math, оскільки він є наступним найкращим кластером для точки Шаблон:Math.

Тепер ми визначаємо силует (значення) однієї точки даних Шаблон:Math

$s(i)=\frac{b(i)-a(i)}{\max \{a(i),b(i)\}}$, якщо $|C_I|>1$

і

$s(i)=0$, якщо $|C_I|=1$

Що також можна записати так:

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

З наведеного визначення зрозуміло, що

$-1⩽s(i)⩽1$

Зауважте, що Шаблон:Math не є чітко визначеним для кластерів із розміром в одну точку, у цьому випадку ми встановлюємо $s(i)=0$. Цей вибір довільний, але нейтральний у тому сенсі, що він знаходиться в середині меж: -1 і 1.

Щоб Шаблон:Math було близьке до 1, нам потрібно $a(i)\ll b(i)$. Оскільки Шаблон:Math є мірою того, наскільки Шаблон:Math відрізняється від власного кластера, мале значення означає, що воно добре припасоване. Крім того, велике Шаблон:Math означає, що Шаблон:Math погано узгоджується з сусіднім кластером. Таким чином, Шаблон:Math, близьке до 1, означає, що дані належним чином згруповані. Якщо Шаблон:Math близьке до -1, то за тією ж логікою ми бачимо, що Шаблон:Math було б більш відповідним, якби воно було кластеризоване в сусідньому кластері. Значення Шаблон:Math біля нуля означає, що елемент знаходиться на межі двох природних кластерів.

Середнє Шаблон:Math для всіх точок кластера є мірою того, наскільки тісно згруповані всі точки в кластері. Таким чином, середнє значення Шаблон:Math для всіх даних усього набору даних є мірою того, наскільки правильно дані були згруповані. Якщо кластерів занадто багато або занадто мало, як це може статися, коли в алгоритмі кластеризації використовується невдалий вибір Шаблон:Math (наприклад, у методі k-середніх), то, одним з наслідків, може бути суттєва відмінність у кількість точок різних кластерів. На графіку це виглядає так, що деякі з кластерів зазвичай відображатимуть набагато вужчі силуети, ніж решта (див. малюнок вище). Таким чином, діаграми з силуетами та середніми значеннями можна використовувати для визначення натуральної кількості кластерів у наборі даних. Можна також збільшити ймовірність максимізації силуету при правильній кількості кластерів шляхом повторного масштабування даних за допомогою вагових коефіцієнтів, які залежать від кластерів.

Кауфман та ін. ввели термін силуетний коефіцієнт для максимального значення середнього Шаблон:Math для всіх даних набору даних, тобто,

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

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

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

Для обчислення коефіцієнта силуету потрібно обчислювати всі Шаблон:Math попарних відстаней, що робить це оцінювання набагато дорожчим, ніж кластеризація з Шаблон:Math-середніми. Для кластеризації з центрами ${\mu }_{C_I}$ для кожного кластера $C_I$, ми можемо використовувати наступний спрощений силует для кожної точки $i\in C_I$ замість цього, який можна обчислити, використовуючи лише Шаблон:Math відстаней:

$a^{\prime }(i)=d(i,{\mu }_{C_I})$ і $b^{\prime }(i)=\underset{C_J\ne C_I}{\min }d(i,C_J)$,

який має додаткову перевагу в тому, що Шаблон:Math завжди визначено, тоді відповідно можна визначити спрощений силует і коефіцієнт спрощеного силуету

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

$S{C}^{\prime }=\underset{k}{\max }\frac{1}{N}\sum _i{s}^{\prime }\left(i\right)$.

Якщо центри кластерів є медоїдами (як при кластеризації Шаблон:Math-медоїдами), а не середніми арифметичними (як при кластеризації Шаблон:Math-середніми), це також називається силуетом на основі медоїда або медоїд-силуетом.

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

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

Замість використання середнього силуету для оцінки кластеризації, отриманої, наприклад, з Шаблон:Math-медоїдів або Шаблон:Math-середніх, ми можемо спробувати безпосередньо знайти рішення, яке максимізує значення силуету. Ми не маємо готового рішення, яке дозволяло б максимізувати силует, але зазвичай найкраще призначати точки найближчому кластеру, як це робиться за допомогою цих методів. Ван дер Лаан та ін. запропонував адаптувати стандартний алгоритм для Шаблон:Math-медоїдів, Шаблон:Нп, для цієї мети та назвати цей алгоритм PAMSIL:

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

Цикл на кроці 3 виконується для Шаблон:Math пар і включає обчислення силуету для Шаблон:Math пар точок, отже, цей алгоритм потребує Шаблон:Math часу, де Шаблон:Math — кількість ітерацій.

Оскільки це досить дорога операція, автори пропонують також використовувати силует, заснований на медоїді, і назвати отриманий алгоритм PAMMEDSIL. Для цього потрібно Шаблон:Math часу.

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

Застосувавши останні вдосконалення алгоритму PAM, FastMSC скорочує час роботи за допомогою силуету медоїда лише до Шаблон:Math.

Див. також

• Шаблон:Нп
• Шаблон:Нп

Посилання

• Шаблон:Cite web