Agruparea spectrală

Tehnicile de grupare spectrală utilizează spectrul ( valorile proprii ) ale matricei de similaritate a datelor pentru a efectua reducerea dimensionalității înainte de gruparea în spații dimensionale inferioare. Matricea de similaritate este dată ca intrare și constă în estimări cantitative ale similitudinii relative a fiecărei perechi de puncte din date.

Când este aplicată la segmentarea imaginii, gruparea spectrală este cunoscută sub denumirea de clustering de caracteristici bazate pe segmentare .

Algoritmi

Având în vedere un set enumerat de puncte de date, matricea de similaritate poate fi definită ca o matrice simetrică în care elementele reprezintă o măsură a similitudinii între punctele de date cu indici și . Principiul general al grupării spectrale este de a folosi metoda standard de grupare (există multe astfel de metode, metoda k-means este discutată mai jos ) pe vectorii proprii semnificativi ai matricei Kirchhoff a matricei . Există multe moduri diferite de a defini matricea Kirchhoff, care are interpretări matematice diferite, astfel încât gruparea va avea și interpretări diferite. Vectorii proprii semnificativi sunt cei care corespund celor mai mici valori proprii ale matricei Kirchhoff, cu excepția valorilor proprii 0. Pentru eficiența computațională, acești vectori proprii sunt adesea calculați ca vectori proprii corespunzători unora dintre cele mai mari valori proprii ale unui funcţia matricei Kirchhoff. $A$ $A_{ij}\geq 0$ $i$ $j$ $A$

O tehnică de grupare spectrală este algoritmul de secțiune normalizată (sau algoritmul Shi-Malik ) propus de Jiambo Shi și Jitendra Malik [1] , o metodă utilizată pe scară largă pentru segmentarea imaginilor . Algoritmul împarte punctele în două seturi pe baza vectorului propriu corespunzător celei de-a doua valori proprii ca mărime a matricei Kirchhoff normalizate simetric, dată de formula $(B_{1},B_{2})$ $v$

L^{\text{norm}}:=ID^{-1/2}AD^{-1/2},

unde este matricea diagonală $D$

D_{ii}=\sum _{j}A_{ij}.

Algoritmul echivalent matematic [2] folosește un vector propriu corespunzător celei mai mari valori proprii a matricei Kirchhoff normalizate de mers aleator . Algoritmul Meil–Shi a fost testat în contextul hărților de difuzie , care s-au descoperit că au conexiuni cu mecanica cuantică computațională [3] . $P=D^{-1}A$

O altă posibilitate este folosirea matricei Kirchhoff dată de expresie

L:=DA

mai degrabă decât o matrice Kirchhoff normalizată simetric.

Partiționarea se poate face în diferite moduri, cum ar fi calcularea medianei componentelor celui de-al doilea cel mai mic vector propriu și plasarea tuturor punctelor în , ale căror componente în sunt mai mari decât , restul punctelor sunt plasate în . Algoritmul poate fi utilizat pentru gruparea ierarhică prin partiționarea secvenţială a submulţilor într-un mod similar. $m$ $v$ $B_1$ $v$ $m$ $B_{2}$

Dacă matricea de similitudine nu a fost încă construită algebric, eficiența grupării spectrale poate fi îmbunătățită dacă rezolvarea problemei corespunzătoare - căutarea valorilor proprii - este efectuată printr -o metodă fără matrice (fără manipulare explicită sau chiar calcul ). a matricei de similaritate), cum ar fi algoritmul Lanczos . $A$

Pentru graficele de dimensiuni mari, a doua valoare proprie a matricei Kirchhoff (normalizate) a graficului este adesea prost condiționată , ceea ce duce la o convergență lentă a metodelor iterative de găsire a valorilor proprii. Precondiționarea este o tehnică cheie pentru îmbunătățirea convergenței, de exemplu în metoda LOBPCG fără matrice . Agruparea spectrală a fost aplicată cu succes la grafice mari, mai întâi prin recunoașterea structurii unei comunități de rețea și apoi prin gruparea comunității [4] .

Agruparea spectrală este strâns legată de reducerea neliniară a dimensionalității și tehnicile de reducere a dimensionalității, cum ar fi imbricarea liniară locală, pot fi utilizate pentru a reduce eroarea de la zgomot sau valorile aberante din observații [5] .

Software-ul gratuit pentru implementarea grupării spectrale este disponibil în proiecte open source mari, cum ar fi Scikit-learn [6] , MLlib pentru clustering bazat pe pseudovalori proprii folosind metoda iterației puterii [7] , limbajul R [8] .

Relația cu k -means

Problema k - means cu un nucleu neliniar este o extensie a problemei k - means în care punctele de intrare sunt mapate neliniar într-un spațiu de caracteristici cu dimensiuni mari folosind o funcție de nucleu . Problema k -means ponderată cu un nucleu neliniar extinde problema mai mult prin specificarea ponderii fiecărui cluster ca valoare invers proporțională cu numărul de elemente ale clusterului, $k(x_{i},x_{j})=\varphi ^{T}(x_{i})\varphi (x_{j})$ $w_{r}$

\max _{\{C_{s}\}}\sum _{r=1}^{k}w_{r}\sum _{x_{i},x_{j}\in C_{r }}k(x_{i},x_{j}).

Fie o matrice de coeficienți normalizați pentru fiecare punct al oricărui cluster, unde , dacă și 0 în caz contrar. Fie matricea nucleului pentru toate punctele. O problemă ponderată k -means cu un nucleu neliniar cu n puncte și k clustere este definită ca o problemă de maximizare $F$ $F_{ij}=w_{r)$ $i,j\in C_{r)$ $K$

\max _{F}\operatorname {urmă} \left(KF\right)

in conditii

F=G_{n\times k}G_{k\times n}^{T)

G^{T}G=E

In acelasi timp . În plus, există o constrângere asupra coeficienților $\operatorname {rank} (G)=k$ $F$

F\cdot \mathbf {1} =\mathbf {1}

unde este un vector de unități. $\mathbf{1}$

F^{T}\mathbf {1} =\mathbf {1}

Sarcina poate fi convertită în

\max _{G}\operatorname {urmă} (G^{T}G).

Această problemă este echivalentă cu problema grupării spectrale atunci când constrângerea este relaxată. În special, o problemă ponderată k -means cu un nucleu neliniar poate fi reformulată ca o problemă de grupare spectrală (partiționare grafică) și invers. Ieșirea algoritmului este reprezentată de vectori proprii care nu îndeplinesc restricțiile privind variabilele indicator definite de vector . Prin urmare, este necesară post-procesarea vectorilor proprii pentru ca sarcinile să fie echivalente [9] . Transformarea problemei de clustering spectral într-o problemă ponderată de k -means cu un nucleu neliniar reduce semnificativ costurile de calcul [10] . $F$ $F$

Măsuri pentru compararea grupării

Ravi Kannan, Santosh Vempala și Adrian Wetta [11] au propus o măsură bicriterială pentru determinarea calității grupării. Ei spun că o grupare este (α, ε)-clustering dacă conductivitatea fiecărui cluster este de cel puțin α și greutatea muchiilor interclusterelor nu depășește ε fracțiune din greutatea tuturor muchiilor din grafic. În același articol, ei iau în considerare și doi algoritmi de aproximare.

Vezi și

Metoda de propagare prin proximitate
Metoda componentei principale nucleare
analiza grupului
Teoria grafurilor spectrale

Note

↑ Shi, Malik, 2000 .
↑ Meilă, Shi, 2001 , p. 873–879.
↑ Scott, Therani, Wang, 2017 , p. 1-17.
↑ Zare, Shooshtari, Gupta, Brinkman, 2010 , p. 403.
↑ Arias-Castro, Chen, Lerman, 2011 , p. 1537–1587
↑ 2.3. Clustering - documentația scikit-learn 0.20.2 . Preluat la 28 iunie 2017. Arhivat din original la 15 mai 2015. (nedefinit)
↑ Clustering - API bazat pe RDD - Documentație Spark 2.4.0 . Preluat la 28 iunie 2017. Arhivat din original la 3 iulie 2017. (nedefinit)
↑ CRAN - Pachetul kernlab . Consultat la 28 iunie 2017. Arhivat din original pe 27 iunie 2017. (nedefinit)
↑ Dhillon, Guan, Kulis, 2004 , p. 551–556.
↑ Dhillon, Guan, Kulis, 2007 , p. 1-14.
↑ Kannan, Vempala, Vetta, 2000 , p. 497–515.

Literatură

Marina Meila, Jianbo Shi. Segmentarea învățării prin plimbări aleatorii // Sisteme de procesare a informațiilor neuronale . - 2001. - V. 13 (NIPS 2000). Arhivat pe 10 decembrie 2015 la Wayback Machine
Jianbo Shi, Jitendra Malik. Tăieri normalizate și segmentare a imaginii // Tranzacții IEEE pe PAMI. - 2000. - August ( vol. 22 , numărul 8 ).
T.C. Scott, Madhusudan Therani, Xing M. Wang. Clustering de date cu mecanica cuantică // Matematică. - 2017. - V. 5 , nr. 1 . — S. 1–17 . doi : 10.3390 / math5010005 .
Habil Zare, P. Shooshtari, A. Gupta, R. Brinkman. Reducerea datelor pentru gruparea spectrală pentru a analiza datele de citometrie în flux de mare capacitate // BMC Bioinformatics. - 2010. - T. 11 . - S. 403 . - doi : 10.1186/1471-2105-11-403 . — PMID 20667133 .
E. Arias-Castro, G. Chen, G. Lerman. Agruparea spectrală bazată pe aproximări liniare locale. // Jurnalul Electronic de Statistică. - 2011. - T. 5 . - S. 1537-1587 . - doi : 10.1214/11-ejs651 .
IS Dhillon, Y. Guan, B. Kulis. Kernel k - înseamnă: clustering spectral și tăieturi normalizate // Proceedings of the zeth ACM SIGKDD international Conference on Knowledge discovery and data mining. - 2004. - S. 551-556.
Inderjit Dhillon, Yuqiang Guan, Brian Kulis. Tăieri ponderate de grafice fără vectori proprii: o abordare pe mai multe niveluri // Tranzacții IEEE privind analiza modelelor și inteligența mașinii. - 2007. - Noiembrie ( vol. 29 , numărul 11 ). - doi : 10.1109/tpami.2007.1115 .
Ravi Kannan, Santosh Vempala, Adrian Vetta. Pe clustere: Bun. Rău și spectral // Jurnalul ACM. - 2000. - T. 51 . - doi : 10.1145/990308.990313 .