Clustering

În statistici , clusterizarea sau analiza de grup (din termenul englezesc cluster analysis introdus de Robert Tryon în 1939 ) este un set de tehnici de analiză a datelor multivariate care vizează selectarea și gruparea elementelor omogene într-un set de date. Tehnicile de grupare se bazează pe măsuri legate de asemănarea dintre elemente. În multe abordări, această asemănare, sau mai degrabă diferență, este concepută în termeni de distanță într-un spațiu multidimensional. Bunătatea analizelor obținute de algoritmii de grupare depinde foarte mult de alegerea metricei și, prin urmare, de modul în care este calculată distanța. Algoritmii de grupare grupează elementele pe baza distanței lor reciproce și, prin urmare, dacă aparțin sau nu unui set depinde de cât de departe este elementul luat în considerare de setul în sine.

Tehnici

Tehnicile de grupare se pot baza în principal pe două „filozofii”:

De jos în sus ( metode agregative sau de jos în sus ):

Această filozofie prevede că inițial toate elementele sunt considerate clustere în sine, iar apoi algoritmul se alătură celor mai apropiate clustere . Algoritmul continuă să unească elemente la cluster până când se obține un număr predeterminat de clustere sau până când distanța minimă dintre clustere nu depășește o anumită valoare sau din nou în raport cu un anumit criteriu statistic predeterminat.

De sus în jos ( metode de divizare sau de sus în jos ):

La început, toate elementele sunt un singur cluster și apoi algoritmul începe să împartă clusterul în mai multe clustere mai mici. Criteriul care ghidează împărțirea este în mod firesc acela de a obține grupuri din ce în ce mai omogene. Algoritmul continuă până când este îndeplinită o regulă de oprire, în general legată de realizarea unui număr predeterminat de clustere .

Există diverse clasificări ale tehnicilor de clusterizare utilizate în mod obișnuit. O primă clasificare depinde dacă un element poate fi sau nu atribuit mai multor clustere:

clustering exclusiv : fiecare element poate fi atribuit unui singur și unui singur grup. Prin urmare, grupurile rezultate nu pot avea elemente în comun. Această abordare este, de asemenea, numită hard clustering .
clusterizare neexclusivă , în care un element poate aparține mai multor clustere cu grade diferite de apartenență. Această abordare este, de asemenea, cunoscută sub numele de clusterizare soft sau clusterizare fuzzy, de la termenul folosit pentru a indica logica fuzzy .

O altă subdiviziune a tehnicilor de grupare ia în considerare tipul de algoritm utilizat pentru a împărți spațiul:

partiționare (numită și non-ierarhică sau k-clustering) , în care se utilizează o distanță față de un punct reprezentativ al clusterului (centroid, medioid etc.) pentru a defini apartenența la un grup, având prefixat numărul de partiții rezultate ale grupurilor . Acestea sunt derivări ale celui mai cunoscut algoritm de clusterizare, cel cunoscut sub numele de k-means , introdus de MacQueen în 1967.
Clusterizare ierarhică , în care este construită o ierarhie de partiții caracterizate printr-un (de) număr tot mai mare de grupuri, vizualizată printr-o reprezentare în arbore (dendrogramă), în care sunt reprezentați pașii de fuziune / divizare a grupurilor.

Aceste două subdiviziuni sunt complet transversale, iar mulți algoritmi născuți ca „exclusivi” au fost adaptați ulterior cazului „neexclusiv” și invers.

Clusterare parțială

Algoritmii de grupare din această familie creează o partiție a observațiilor prin minimizarea unei anumite funcții de cost:

\sum _{j=1}^{k}E(C_{j}),

{\ displaystyle \ sum _ {j = 1} ^ {k} E (C_ {j}),}

{\ displaystyle \ sum _ {j = 1} ^ {k} E (C_ {j}),}

unde este $k$ ${\ displaystyle k}$ $k$ este numărul de clustere, $C_{j}$ ${\ displaystyle C_ {j}}$ $C_ {j}$ si $j$ ${\ displaystyle j}$ $j$ -clusterul e $E\colon C\rightarrow \mathbb {R} ^{+}$ ${\ displaystyle E \ colon C \ rightarrow \ mathbb {R} ^ {+}}$ ${\ displaystyle E \ colon C \ rightarrow \ mathbb {R} ^ {+}}$ este funcția de cost asociată clusterului unic. Cel mai faimos algoritm aparținând acestei familii este k-means , propus de MacQueen în 1967 . Un alt algoritm destul de cunoscut care aparține acestei clase este Partitioning Around Medioid (PAM).

Gruparea ierarhică

Tehnicile de grupare ierarhică nu produc o partiționare plană a punctelor, ci o reprezentare ierarhică a arborelui.

La rândul lor, acești algoritmi sunt împărțiți în două clase:

Aglomerativ - Acești algoritmi presupun că inițial fiecare grup (frunză) conține un singur punct; la fiecare pas, atunci, clusterele „cele mai apropiate” sunt îmbinate până se obține un singur cluster mare. Acești algoritmi au nevoie de măsuri pentru a evalua similitudinea dintre clustere, pentru a alege perechea de clustere de fuzionat la fiecare pas.
Diviziv - Pe de altă parte, acești algoritmi încep prin a lua în considerare spațiul organizat într-un singur cluster mare care conține toate punctele și îl împarte treptat în două. La fiecare pas, un cluster este selectat pe baza unei măsuri și este împărțit în două clustere mai mici. În mod normal, se stabilește un număr minim de puncte sub care clusterul nu mai este subdivizat (în cazul extrem, această valoare este 1). Aceste tipuri de algoritmi trebuie să definească o funcție pentru a alege clusterul de împărțit.

O reprezentare grafică a procesului de grupare este furnizată de dendrogramă .

Măsuri utilizate în clusterizarea ierarhică

În ambele tipuri de clustere ierarhice, sunt necesare funcții pentru a selecta perechea de clustere de fuzionat („aglomerativ”) sau clusterul de divizat („diviziv”).

În primul caz, sunt necesare funcții care măsoară asemănarea (sau, fără discriminare, distanța ) dintre două clustere, pentru a fuziona cele mai similare. Funcțiile utilizate în cazul aglomerativ sunt:

Proximitate cu o singură legătură

Calculați distanța dintre cele două clustere ca distanță minimă între elementele aparținând clustere diferite:

D(C_{i},C_{j})=\min _{x\in C_{i},y\in C_{j}}d(x,y)

{\ displaystyle D (C_ {i}, C_ {j}) = \ min _ {x \ în C_ {i}, y \ în C_ {j}} d (x, y)}

D (C_ {i}, C_ {j}) = \ min _ {{x \ în C_ {i}, y \ în C_ {j}}} d (x, y)

Apropiere medie a legăturii

Această funcție calculează distanța dintre cele două clustere ca medie a distanțelor dintre elementele individuale:

D(C_{i},C_{j})={\frac {1}{|C_{i}||C_{j}|}}\sum _{x\in C_{i},y\in C_{j}}d(x,y)

{\ displaystyle D (C_ {i}, C_ {j}) = {\ frac {1} {| C_ {i} || C_ {j} |}} \ sum _ {x \ în C_ {i}, y \ în C_ {j}} d (x, y)}

D (C_ {i}, C_ {j}) = {\ frac {1} {| C_ {i} || C_ {j} |}} \ sum _ {{x \ in C_ {i}, y \ in C_ {j}}} d (x, y)

Apropiere completă a legăturii

Această funcție calculează distanța dintre cele două clustere ca distanță maximă între elementele aparținând celor două clustere:

D(C_{i},C_{j})=\max _{x\in C_{i},y\in C_{j}}d(x,y)

{\ displaystyle D (C_ {i}, C_ {j}) = \ max _ {x \ în C_ {i}, y \ în C_ {j}} d (x, y)}

D (C_ {i}, C_ {j}) = \ max _ {{x \ în C_ {i}, y \ în C_ {j}}} d (x, y)

Distanța dintre centroizi

Distanța dintre cele două clustere coincide cu distanța calculată între centroizi (sau medioizi):

D(C_{i},C_{j})=d({\hat {c_{i}}},{\hat {c_{j}}})

{\ displaystyle D (C_ {i}, C_ {j}) = d ({\ hat {c_ {i}}}, {\ hat {c_ {j}}})}

D (C_ {i}, C_ {j}) = d ({\ hat {c_ {i}}}, {\ hat {c_ {j}}})

.

În cele 4 cazuri anterioare, $d(x,y)$ ${\ displaystyle d (x, y)}$ $d (x, y)$ indică orice funcție de distanță pe un spațiu metric.

Pe de altă parte, în gruparea divizorie este necesar să se identifice clusterul care urmează să fie împărțit în două subgrupuri. Din acest motiv, sunt necesare funcții care măsoară compactitatea clusterului, densitatea sau raritatea punctelor atribuite unui cluster. Funcțiile utilizate în mod normal în cazul diviziunii sunt:

Similitudine internă medie

Această funcție evaluează similitudinea medie între documentele dintr-un cluster: cu cât sunt mai diferite (valori de similaritate reduse), cu atât clusterul va fi împărțit în subgrupuri:

D(C_{i})={\frac {1}{|C_{i}|(|C_{i}|-1)}}\sum _{x,y\in C_{i},x\neq y}d(x,y)

{\ displaystyle D (C_ {i}) = {\ frac {1} {| C_ {i} | (| C_ {i} | -1)}} \ sum _ {x, y \ în C_ {i}, x \ neq y} d (x, y)}

D (C_ {i}) = {\ frac {1} {| C_ {i} | (| C_ {i} | -1)}} \ sum _ {{x, y \ in C_ {i}, x \ neq y}} d (x, y)

Distanța maximă internă

Această funcție evaluează distanța maximă dintre două puncte din interiorul unui cluster. Această valoare este, de asemenea, cunoscută sub numele de „diametrul clusterului”: cu cât această valoare este mai mică, cu atât clusterul este mai compact:

D(C_{i})=\max _{x,y\in C_{i}}d(x,y)

{\ displaystyle D (C_ {i}) = \ max _ {x, y \ în C_ {i}} d (x, y)}

D (C_ {i}) = \ max _ {{x, y \ în C_ {i}}} d (x, y)

Clusterizare bazată pe densitate

În Clustering bazat pe densitate , gruparea are loc analizând vecinătatea fiecărui punct al spațiului. În special, se ia în considerare densitatea punctelor dintr-un cartier cu o rază fixă.

Un exemplu este metoda de grupare Dbscan .

Algoritmi

Algoritmii de clusterizare utilizați pe scară largă sunt:

Clusterizarea QT

Clusterizarea QT ( Quality Threshold ) (Heyer și colab., 1999) este o metodă alternativă de partiționare a datelor, inventată pentru gruparea genelor . Necesită mai multă putere de calcul decât K- Means, dar nu necesită să specificați numărul de clustere a priori și întotdeauna returnează același rezultat atunci când se repetă de mai multe ori.

Algoritmul este:

Utilizatorul alege un diametru maxim pentru clustere;
Construirea unui cluster candidat pentru fiecare punct, inclusiv cel mai apropiat punct, următorul cel mai apropiat și așa mai departe, până când diametrul clusterului depășește pragul;
Salvarea clusterului candidat cu cele mai multe puncte ca primul cluster adevărat și eliminarea tuturor punctelor din cluster din alte considerente;
Recursivitate cu setul redus de clustere.

Distanța dintre un punct și un grup de puncte este calculată utilizând concatenarea completă, adică ca distanță maximă de la punctul fiecărui membru al grupului (vezi „Clustering ierarhic aglomerativ” pe distanța dintre clustere în secțiunea Clustering ierarhic ).

Bibliografie

Roberto Todeschini, Introducere în chimiometrie, ediția I, Napoli, EdiSES, 2003, ISBN 88-7959-146-0 .
G.Susinno, MAMiceli, Ultrametricity in Fund of Fund Diversification , Physica A 344 (1-2) (2004) 95-99

Elemente conexe

Alte proiecte

Wikimedia Commons conține imagini sau alte fișiere despre cluster

linkuri externe

Clustering , pe Sapienza.it , De Agostini .
( EN ) Clustering , în Encyclopedia Britannica , Encyclopædia Britannica, Inc.
(IT) Articol informativ privind clusterizarea și extragerea datelor.
Gaetano Zazzaro, Angelo Martone, „ECF-means - Ensemble Clustering Fuzzification Means. Un nou algoritm pentru agregarea, fuzzificarea și optimizarea clusteringului” [1] , a VIII-a Conferință internațională privind progresele în gestionarea informațiilor și gestionarea informațiilor, IMMM 2018, Barcelona, Spania , 22 - 26 iulie 2018.

Controlul autorității	Tezaur BNCF 43938 · LCCN (EN) sh85027250 · BNF (FR) cb12124521b (data)

Portal IT

Portalul de matematică

V · D · M Învățare automată
Probleme	Clasificarea · Regresie · asociere Reguli · Învățare nesupravegheați · Supravegheat de învățare · Reinforcement Learning · învățare profundă
Învățare nesupravegheată	Clustering · clustering Ierarhica · K mijloace · Așteptarea maximizare · DBSCAN · schimbare medie · antagonist generativă rețea (CGAN · cycleGAN VAE-GAN)
Învățare supravegheată	Arborele decizional · Pădure aleatorie · CRF · HMM · KNN · Clasificator bayesian · Rețea neuronală artificială · Regresie liniară · Regresie logistică · PGM · SVM
Consolidarea învățării	Q-learning · SARSA · TD
Reducerea dimensiunii	Analiza factorilor · CCA · ICA · LDA · PCA · Selecția caracteristicilor · Extragerea caracteristicilor · t-SNE
Rețele neuronale artificiale	Perceptron · RBF · N · FFN · Rețea Hopfield · MLP · RNN ( LSTM ) · RBM · SOM · CNN · TDNN · SNN
Software	Keras · Microsoft Cognitive Toolkit · scikit-learn · TensorFlow · Theano · Torch · Weka
Alte	Algoritm genetic · PSO · Caracteristic