Силует у кластерному аналізі відноситься до методу інтерпретації та перевірки узгодженості елементів кластерів даних. Цей метод забезпечує стисле графічне представлення того, наскільки добре класифіковано кожен об'єкт. Цей підхід запропонував бельгійський статистик [en] в 1987 році.
Величина силуету є мірою того, наскільки об'єкт схожий на власний кластер (згуртованість) порівняно з іншими кластерами (відокремлення). Значення силуету коливається від −1 до +1, де високе значення вказує на те, що об'єкт добре збігається з власним кластером і погано збігається з сусідніми кластерами. Якщо більшість об'єктів мають високе значення, то конфігурація кластеризації відповідає природі даних. Якщо багато точок мають низьке або від'ємне значення, тоді конфігурація кластеризації може мати забагато або замало кластерів.
Силует можна розрахувати за допомогою будь-якої метрики відстані, наприклад евклідової відстані або манхеттенської відстані.
Визначення
Припустімо, що дані були згруповані за допомогою будь-якого методу, наприклад [en] або k-середніх, у k кластерів.
Для точки даних (точка даних i в кластері ), обчислимо
яке є середньою відстанню між i та всіма іншими точками даних у тому самому кластері, де — це кількість точок, що належать кластеру i, а d(i,j) — це відстань між точками даних i та j у кластері (ділимо на оскільки ми не включаємо відстань d(i,i) у суму). Ми можемо інтерпретувати a(i) як міру того, наскільки добре i припасовоно до кластеру (чим менше значення, тим краще припасування).
Потім ми визначаємо середню несхожість точки i на деякий кластер , який міг би бути найкращим кластером для точки i, як середнє значення відстані від i до всіх точок (де ).
Для кожної точки даних , тепер визначимо
найменший (тому, оператор у формулі), бо маємо порівнювати з найближчим кластером, означає відстань i до всіх точок у будь-якому іншому кластері (тобто в будь-якому кластері, членом якого i не є). Кластер із цією найменшою середньою різницею називають «сусіднім кластером» i, оскільки він є наступним найкращим кластером для точки i.
Тепер ми визначаємо силует (значення) однієї точки даних i
- , якщо
і
- , якщо
Що також можна записати так:
З наведеного визначення зрозуміло, що
Зауважте, що a(i) не є чітко визначеним для кластерів із розміром в одну точку, у цьому випадку ми встановлюємо . Цей вибір довільний, але нейтральний у тому сенсі, що він знаходиться в середині меж: -1 і 1.
Щоб s(i) було близьке до 1, нам потрібно . Оскільки a(i) є мірою того, наскільки i відрізняється від власного кластера, мале значення означає, що воно добре припасоване. Крім того, велике b(i) означає, що i погано узгоджується з сусіднім кластером. Таким чином, s(i), близьке до 1, означає, що дані належним чином згруповані. Якщо s(i) близьке до -1, то за тією ж логікою ми бачимо, що i було б більш відповідним, якби воно було кластеризоване в сусідньому кластері. Значення s(i) біля нуля означає, що елемент знаходиться на межі двох природних кластерів.
Середнє s(i) для всіх точок кластера є мірою того, наскільки тісно згруповані всі точки в кластері. Таким чином, середнє значення s(i) для всіх даних усього набору даних є мірою того, наскільки правильно дані були згруповані. Якщо кластерів занадто багато або занадто мало, як це може статися, коли в алгоритмі кластеризації використовується невдалий вибір k (наприклад, у методі k-середніх), то, одним з наслідків, може бути суттєва відмінність у кількість точок різних кластерів. На графіку це виглядає так, що деякі з кластерів зазвичай відображатимуть набагато вужчі силуети, ніж решта (див. малюнок вище). Таким чином, діаграми з силуетами та середніми значеннями можна використовувати для визначення натуральної кількості кластерів у наборі даних. Можна також збільшити ймовірність максимізації силуету при правильній кількості кластерів шляхом повторного масштабування даних за допомогою вагових коефіцієнтів, які залежать від кластерів.
Кауфман та ін. ввели термін силуетний коефіцієнт для максимального значення середнього s(i) для всіх даних набору даних, тобто,
де представляє середнє s(i) по всім даним усього набору при заданій кількості кластерів k.
Спрощений силует і медоїд-силует
Для обчислення коефіцієнта силуету потрібно обчислювати всі O(N2) попарних відстаней, що робить це оцінювання набагато дорожчим, ніж кластеризація з k-середніми. Для кластеризації з центрами для кожного кластера , ми можемо використовувати наступний спрощений силует для кожної точки замість цього, який можна обчислити, використовуючи лише O(Nk) відстаней:
- і ,
який має додаткову перевагу в тому, що a'(i) завжди визначено, тоді відповідно можна визначити спрощений силует і коефіцієнт спрощеного силуету
- .
Якщо центри кластерів є медоїдами (як при кластеризації k-медоїдами), а не середніми арифметичними (як при кластеризації k-середніми), це також називається силуетом на основі медоїда або медоїд-силуетом.
Якщо кожен об'єкт присвоєно найближчому медоїду (як при кластеризації k-медоїдами), ми знаємо, що , і отже .
Кластеризація силуету
Замість використання середнього силуету для оцінки кластеризації, отриманої, наприклад, з k-медоїдів або k-середніх, ми можемо спробувати безпосередньо знайти рішення, яке максимізує значення силуету. Ми не маємо готового рішення, яке дозволяло б максимізувати силует, але зазвичай найкраще призначати точки найближчому кластеру, як це робиться за допомогою цих методів. Ван дер Лаан та ін. запропонував адаптувати стандартний алгоритм для k-медоїдів, [en], для цієї мети та назвати цей алгоритм PAMSIL:
- Виберіть початкові медоїди за допомогою PAM
- Обчисліть середній силует цього початкового рішення
- Для кожної пари медоїда m і не медоїда x
- поміняти місцями m і x
- обчислити середній силует отриманого рішення
- запам'ятати найкращу заміну
- Виконати найкращу заміну та повернутися до п. 3, інакше, якщо покращення не знайдено, закінчити.
Цикл на кроці 3 виконується для O(Nk) пар і включає обчислення силуету для O(N2) пар точок, отже, цей алгоритм потребує O(N3ki) часу, де i — кількість ітерацій.
Оскільки це досить дорога операція, автори пропонують також використовувати силует, заснований на медоїді, і назвати отриманий алгоритм PAMMEDSIL. Для цього потрібно O(N2k2i) часу.
Батул та ін. запропонували подібний алгоритм під назвою OSil і запропонували подібну до CLARA стратегію вибірки для більших наборів даних, яка вирішує проблему лише для підвибірки.
Застосувавши останні вдосконалення алгоритму PAM, FastMSC скорочує час роботи за допомогою силуету медоїда лише до O(N2i).
Див. також
- [en]
- [en]
Примітки
- (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; (1990). Finding groups in data : An introduction to cluster analysis. Hoboken, NJ: Wiley-Interscience. с. 87. doi:10.1002/9780470316801. ISBN .
- 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.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
U Vikipediyi ye statti pro inshi znachennya cogo termina Siluet znachennya Siluet u klasternomu analizi vidnositsya do metodu interpretaciyi ta perevirki uzgodzhenosti elementiv klasteriv danih Cej metod zabezpechuye stisle grafichne predstavlennya togo naskilki dobre klasifikovano kozhen ob yekt Cej pidhid zaproponuvav belgijskij statistik en v 1987 roci Velichina siluetu ye miroyu togo naskilki ob yekt shozhij na vlasnij klaster zgurtovanist porivnyano z inshimi klasterami vidokremlennya Znachennya siluetu kolivayetsya vid 1 do 1 de visoke znachennya vkazuye na te sho ob yekt dobre zbigayetsya z vlasnim klasterom i pogano zbigayetsya z susidnimi klasterami Yaksho bilshist ob yektiv mayut visoke znachennya to konfiguraciya klasterizaciyi vidpovidaye prirodi danih Yaksho bagato tochok mayut nizke abo vid yemne znachennya todi konfiguraciya klasterizaciyi mozhe mati zabagato abo zamalo klasteriv Siluet mozhna rozrahuvati za dopomogoyu bud yakoyi metriki vidstani napriklad evklidovoyi vidstani abo manhettenskoyi vidstani ViznachennyaDiagrama sho pokazuye ocinki siluetiv troh tipiv tvarin iz naboru danih Zoo vidtvorenogo paketom analizu danih en U nizhnij chastini diagrami vid yemne znachennya siluetu viznachaye delfina ta morsku svinyu yak vinyatki u grupi ssavciv Takozh do nedolikiv klasterizaciyi mozhna zarahuvati zanadto veliku zelenu grupu tvarin Pripustimo sho dani buli zgrupovani za dopomogoyu bud yakogo metodu napriklad en abo k serednih u k klasteriv Dlya tochki danih i CI displaystyle i in C I tochka danih i v klasteri CI displaystyle C I obchislimo a i 1 CI 1 j CI i jd i j displaystyle a i frac 1 C I 1 sum j in C I i neq j d i j yake ye serednoyu vidstannyu mizh i ta vsima inshimi tochkami danih u tomu samomu klasteri de CI displaystyle C I ce kilkist tochok sho nalezhat klasteru i a d i j ce vidstan mizh tochkami danih i ta j u klasteri CI displaystyle C I dilimo na CI 1 displaystyle C I 1 oskilki mi ne vklyuchayemo vidstan d i i u sumu Mi mozhemo interpretuvati a i yak miru togo naskilki dobre i pripasovono do klasteru chim menshe znachennya tim krashe pripasuvannya Potim mi viznachayemo serednyu neshozhist tochki i na deyakij klaster CJ displaystyle C J yakij mig bi buti najkrashim klasterom dlya tochki i yak serednye znachennya vidstani vid i do vsih tochok CJ displaystyle C J de CJ CI displaystyle C J neq C I Dlya kozhnoyi tochki danih i CI displaystyle i in C I teper viznachimo b i minJ I1 CJ j CJd i j displaystyle b i min J neq I frac 1 C J sum j in C J d i j najmenshij tomu operator min displaystyle min u formuli bo mayemo porivnyuvati z najblizhchim klasterom oznachaye vidstan i do vsih tochok u bud yakomu inshomu klasteri tobto v bud yakomu klasteri chlenom yakogo i ne ye Klaster iz ciyeyu najmenshoyu serednoyu rizniceyu nazivayut susidnim klasterom i oskilki vin ye nastupnim najkrashim klasterom dlya tochki i Teper mi viznachayemo siluet znachennya odniyeyi tochki danih i s i b i a i max a i b i displaystyle s i frac b i a i max a i b i yaksho CI gt 1 displaystyle C I gt 1 i s i 0 displaystyle s i 0 yaksho CI 1 displaystyle C I 1 Sho takozh mozhna zapisati tak s i 1 a i b i if a i lt b i 0 if a i b i b i a i 1 if a i gt b i displaystyle s i begin cases 1 a i b i amp mbox if a i lt b i 0 amp mbox if a i b i b i a i 1 amp mbox if a i gt b i end cases Z navedenogo viznachennya zrozumilo sho 1 s i 1 displaystyle 1 leqslant s i leqslant 1 Zauvazhte sho a i ne ye chitko viznachenim dlya klasteriv iz rozmirom v odnu tochku u comu vipadku mi vstanovlyuyemo s i 0 displaystyle s i 0 Cej vibir dovilnij ale nejtralnij u tomu sensi sho vin znahoditsya v seredini mezh 1 i 1 Shob s i bulo blizke do 1 nam potribno a i b i displaystyle a i ll b i Oskilki a i ye miroyu togo naskilki i vidriznyayetsya vid vlasnogo klastera male znachennya oznachaye sho vono dobre pripasovane Krim togo velike b i oznachaye sho i pogano uzgodzhuyetsya z susidnim klasterom Takim chinom s i blizke do 1 oznachaye sho dani nalezhnim chinom zgrupovani Yaksho s i blizke do 1 to za tiyeyu zh logikoyu mi bachimo sho i bulo b bilsh vidpovidnim yakbi vono bulo klasterizovane v susidnomu klasteri Znachennya s i bilya nulya oznachaye sho element znahoditsya na mezhi dvoh prirodnih klasteriv Serednye s i dlya vsih tochok klastera ye miroyu togo naskilki tisno zgrupovani vsi tochki v klasteri Takim chinom serednye znachennya s i dlya vsih danih usogo naboru danih ye miroyu togo naskilki pravilno dani buli zgrupovani Yaksho klasteriv zanadto bagato abo zanadto malo yak ce mozhe statisya koli v algoritmi klasterizaciyi vikoristovuyetsya nevdalij vibir k napriklad u metodi k serednih to odnim z naslidkiv mozhe buti suttyeva vidminnist u kilkist tochok riznih klasteriv Na grafiku ce viglyadaye tak sho deyaki z klasteriv zazvichaj vidobrazhatimut nabagato vuzhchi silueti nizh reshta div malyunok vishe Takim chinom diagrami z siluetami ta serednimi znachennyami mozhna vikoristovuvati dlya viznachennya naturalnoyi kilkosti klasteriv u nabori danih Mozhna takozh zbilshiti jmovirnist maksimizaciyi siluetu pri pravilnij kilkosti klasteriv shlyahom povtornogo masshtabuvannya danih za dopomogoyu vagovih koeficiyentiv yaki zalezhat vid klasteriv Kaufman ta in vveli termin siluetnij koeficiyent dlya maksimalnogo znachennya serednogo s i dlya vsih danih naboru danih tobto SC maxks k displaystyle SC max k tilde s left k right de s k displaystyle tilde s left k right predstavlyaye serednye s i po vsim danim usogo naboru pri zadanij kilkosti klasteriv k Sproshenij siluet i medoyid siluetDlya obchislennya koeficiyenta siluetu potribno obchislyuvati vsi O N2 poparnih vidstanej sho robit ce ocinyuvannya nabagato dorozhchim nizh klasterizaciya z k serednimi Dlya klasterizaciyi z centrami mCI displaystyle mu C I dlya kozhnogo klastera CI displaystyle C I mi mozhemo vikoristovuvati nastupnij sproshenij siluet dlya kozhnoyi tochki i CI displaystyle i in C I zamist cogo yakij mozhna obchisliti vikoristovuyuchi lishe O Nk vidstanej a i d i mCI displaystyle a i d i mu C I i b i minCJ CId i CJ displaystyle b i min C J neq C I d i C J yakij maye dodatkovu perevagu v tomu sho a i zavzhdi viznacheno todi vidpovidno mozhna viznachiti sproshenij siluet i koeficiyent sproshenogo siluetu s i b i a i max a i b i displaystyle s i frac b i a i max a i b i SC maxk1N is i displaystyle SC max k frac 1 N sum i s left i right Yaksho centri klasteriv ye medoyidami yak pri klasterizaciyi k medoyidami a ne serednimi arifmetichnimi yak pri klasterizaciyi k serednimi ce takozh nazivayetsya siluetom na osnovi medoyida abo medoyid siluetom Yaksho kozhen ob yekt prisvoyeno najblizhchomu medoyidu yak pri klasterizaciyi k medoyidami mi znayemo sho a i b i displaystyle a i leqslant b i i otzhe s i b i a i b i 1 a i b i displaystyle s i frac b i a i b i 1 frac a i b i Klasterizaciya siluetuZamist vikoristannya serednogo siluetu dlya ocinki klasterizaciyi otrimanoyi napriklad z k medoyidiv abo k serednih mi mozhemo sprobuvati bezposeredno znajti rishennya yake maksimizuye znachennya siluetu Mi ne mayemo gotovogo rishennya yake dozvolyalo b maksimizuvati siluet ale zazvichaj najkrashe priznachati tochki najblizhchomu klasteru yak ce robitsya za dopomogoyu cih metodiv Van der Laan ta in zaproponuvav adaptuvati standartnij algoritm dlya k medoyidiv en dlya ciyeyi meti ta nazvati cej algoritm PAMSIL Viberit pochatkovi medoyidi za dopomogoyu PAM Obchislit serednij siluet cogo pochatkovogo rishennya Dlya kozhnoyi pari medoyida m i ne medoyida x pominyati miscyami m i x obchisliti serednij siluet otrimanogo rishennya zapam yatati najkrashu zaminu Vikonati najkrashu zaminu ta povernutisya do p 3 inakshe yaksho pokrashennya ne znajdeno zakinchiti Cikl na kroci 3 vikonuyetsya dlya O Nk par i vklyuchaye obchislennya siluetu dlya O N2 par tochok otzhe cej algoritm potrebuye O N3ki chasu de i kilkist iteracij Oskilki ce dosit doroga operaciya avtori proponuyut takozh vikoristovuvati siluet zasnovanij na medoyidi i nazvati otrimanij algoritm PAMMEDSIL Dlya cogo potribno O N2k2i chasu Batul ta in zaproponuvali podibnij algoritm pid nazvoyu OSil i zaproponuvali podibnu do CLARA strategiyu vibirki dlya bilshih naboriv danih yaka virishuye problemu lishe dlya pidvibirki Zastosuvavshi ostanni vdoskonalennya algoritmu PAM FastMSC skorochuye chas roboti za dopomogoyu siluetu medoyida lishe do O N2i Div takozh en en Primitki 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 1990 Finding groups in data An introduction to cluster analysis Hoboken NJ Wiley Interscience s 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 s 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 angl 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 angl s 190 204 doi 10 1007 978 3 031 17849 8 15 Procitovano 20 zhovtnya 2022 Batool Fatima Hennig Christian 2021 Clustering with the Average Silhouette Width Computational Statistics amp Data Analysis angl 158 107190 doi 10 1016 j csda 2021 107190 PosilannyaVibir kilkosti klasteriv za dopomogoyu analizu siluetiv u klasterizaciyi KMeans scikit learn angl Procitovano 28 zhovtnya 2022