Spektral klustring

Spektralklustringstekniker använder spektrumet ( egenvärden ) för likhetsmatrisen för data för att utföra dimensionsreduktion innan klustring i lägre dimensionella utrymmen . Likhetsmatrisen ges som indata och består av kvantitativa uppskattningar av den relativa likheten mellan varje par av punkter i data.

När den tillämpas på bildsegmentering kallas spektralklustring som segmenteringsbaserad funktionsklustring .

Algoritmer

Givet en uppräknad uppsättning datapunkter kan likhetsmatrisen definieras som en symmetrisk matris där elementen representerar ett mått på likhet mellan datapunkter med index och . Den allmänna principen för spektralklustring är att använda standardklustringsmetoden ( det finns många sådana metoder, k-medelmetoden diskuteras nedan ) på de signifikanta egenvektorerna för matrisens Kirchhoff - matris . Det finns många olika sätt att definiera Kirchhoff-matrisen, som har olika matematiska tolkningar, så klustring kommer också att ha olika tolkningar. Signifikanta egenvektorer är de som motsvarar de minsta få egenvärdena i Kirchhoff-matrisen, med undantag för egenvärdena 0. För beräkningseffektivitet beräknas dessa egenvektorer ofta som egenvektorer motsvarande några av de största egenvärdena av en Kirchhoff-matrisens funktion. $A$ $A_{ij}\geq 0$ $i$ $j$ $A$

En teknik för spektral klustring är den normaliserade sektionsalgoritmen (eller Shi-Malik-algoritmen ) som föreslås av Jiambo Shi och Jitendra Malik [1] , en allmänt använd metod för bildsegmentering . Algoritmen delar upp punkterna i två uppsättningar baserat på egenvektorn som motsvarar det näst största egenvärdet för den symmetriskt normaliserade Kirchhoff-matrisen som ges av formeln $(B_{1},B_{2})$ $v$

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

var är den diagonala matrisen $D$

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

Den matematiskt ekvivalenta algoritmen [2] använder en egenvektor som motsvarar det största egenvärdet för den normaliserade Kirchhoff slumpmässiga gångmatrisen . Meil-Shi-algoritmen har testats i samband med diffusionskartor , som har visat sig ha kopplingar till beräkningskvantummekanik [3] . $P=D^{-1}A$

En annan möjlighet är att använda Kirchhoff-matrisen som ges av uttrycket

L:=DA

snarare än en symmetriskt normaliserad Kirchhoff-matris.

Partitionering kan göras på olika sätt, som att beräkna medianen av komponenterna i den näst minsta egenvektorn och placera alla punkter i , vars komponenter i är större än , resten av punkterna placeras i . Algoritmen kan användas för hierarkisk klustring genom att sekventiellt partitionera delmängder på liknande sätt. $m$ $v$ $B_1$ $v$ $m$ $B_{2}$

Om likhetsmatrisen ännu inte har konstruerats algebraiskt kan effektiviteten av spektralklustring förbättras om lösningen av motsvarande problem - sökningen efter egenvärden - utförs med en matrisfri metod (utan explicit manipulation eller ens beräkning av likhetsmatrisen), såsom Lanczos-algoritmen . $A$

För grafer av stor storlek är det andra egenvärdet för grafens (normaliserade) Kirchhoff-matris ofta dåligt konditionerat , vilket leder till långsam konvergens av iterativa egenvärdesökningsmetoder. Förkonditionering är en nyckelteknik för att förbättra konvergens, till exempel i den matrislösa LOBPCG- metoden . Spektral klustring har framgångsrikt tillämpats på stora grafer först genom att känna igen strukturen hos en nätverksgemenskap och sedan genom att gruppera gemenskapen [4] .

Spektral klustring är nära besläktad med icke-linjär dimensionalitetsreduktion och dimensionsreduktionstekniker som lokalt linjär kapsling kan användas för att minska felet från brus eller extremvärden i observationer [5] .

Fri programvara för att implementera spektralklustring är tillgänglig i stora projekt med öppen källkod som Scikit-learn [6] , MLlib för klustring baserad på pseudoeigenvärden med hjälp av power iteration-metoden [7] , R-språket [8] .

Förhållande med k -means

k -means-problemet med en icke-linjär kärna är en förlängning av k -means-problemet där indatapunkter mappas icke-linjärt till ett högdimensionellt funktionsutrymme med hjälp av en kärnfunktion . Det viktade k -medelproblemet med en icke-linjär kärna utökar problemet ytterligare genom att ange vikten för varje kluster som ett värde omvänt proportionellt mot antalet klusterelement, $k(x_{i},x_{j})=\varphi ^{T}(x_{i})\varphi (x_{j})$ $w_{r}$

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

Låta vara en matris med normaliserade koefficienter för varje punkt i ett kluster, där , om , och 0 annars. Låt vara kärnmatrisen för alla punkter. Ett viktat k -medelproblem med en icke-linjär kärna med n punkter och k-kluster definieras som ett maximeringsproblem $F$ ${\displaystyle F_{ij}=w_{r))$ ${\displaystyle i,j\in C_{r))$ $K$

\max _{F}\operatörsnamn {spår} \left(KF\right)

under förhållanden

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

G^{T}G=E

Samtidigt . Dessutom finns det en begränsning på koefficienterna $\operatörsnamn {rank} (G)=k$ $F$

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

var är en vektor av enheter. $\mathbf{1}$

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

Uppgiften kan konverteras till

\max _{G}\operatörsnamn {spår} (G^{T}G).

Detta problem är ekvivalent med problemet med spektral klustring när begränsningen är avslappnad. I synnerhet kan ett viktat k -medelproblem med en icke-linjär kärna omformuleras som ett problem med spektralklustring (grafpartitionering) och vice versa. Algoritmens utdata är egenvektorer som inte uppfyller begränsningarna för de indikatorvariabler som definieras av vektorn . Därför krävs efterbearbetning av egenvektorer för att uppgifterna ska vara likvärdiga [9] . Omvandlingen av det spektrala klustringsproblemet till ett viktat k -medelproblem med en olinjär kärna minskar avsevärt beräkningskostnaderna [10] . $F$ $F$

Åtgärder för att jämföra klustring

Ravi Kannan, Santosh Vempala och Adrian Wetta [11] föreslog ett kriteriummått för att bestämma kvaliteten på klustring. De säger att en klustring är (α, ε)-klustring om konduktiviteten för varje kluster är minst α och vikten av interklusterkanter inte överstiger ε bråkdel av vikten av alla kanter i grafen. I samma artikel tar de också hänsyn till två approximationsalgoritmer.

Se även

Proximity propagation method
Nuclear Principal Component Method
klusteranalys
Spektralgrafteori

Anteckningar

↑ Shi, Malik, 2000 .
↑ Meilă, Shi, 2001 , sid. 873–879.
↑ Scott, Therani, Wang, 2017 , sid. 1-17.
↑ Zare, Shooshtari, Gupta, Brinkman, 2010 , sid. 403.
↑ Arias-Castro, Chen, Lerman, 2011 , sid. 1537–1587
↑ 2.3. Clustering - scikit-learn 0.20.2 dokumentation . Hämtad 28 juni 2017. Arkiverad från originalet 15 maj 2015. (obestämd)
↑ Clustering - RDD-baserad API - Spark 2.4.0-dokumentation . Hämtad 28 juni 2017. Arkiverad från originalet 3 juli 2017. (obestämd)
↑ CRAN - Package kernlab . Hämtad 28 juni 2017. Arkiverad från originalet 27 juni 2017. (obestämd)
↑ Dhillon, Guan, Kulis, 2004 , sid. 551–556.
↑ Dhillon, Guan, Kulis, 2007 , sid. 1-14.
↑ Kannan, Vempala, Vetta, 2000 , sid. 497–515.

Litteratur

Marina Meila, Jianbo Shi. Lärande segmentering genom slumpmässiga promenader // Neural Information Processing Systems . - 2001. - V. 13 (NIPS 2000). Arkiverad 10 december 2015 på Wayback Machine
Jianbo Shi, Jitendra Malik. Normaliserade klipp och bildsegmentering // IEEE-transaktioner på PAMI. - 2000. - Augusti ( vol. 22 , nummer 8 ).
T.C. Scott, Madhusudan Therani, Xing M. Wang. Datakluster med kvantmekanik // Matematik. - 2017. - V. 5 , nr. 1 . — S. 1–17 . doi : 10.3390 / math5010005 .
Habil Zare, P. Shooshtari, A. Gupta, R. Brinkman. Datareduktion för spektralklustring för att analysera data från flödescytometri med hög genomströmning // BMC Bioinformatics. - 2010. - T. 11 . - S. 403 . - doi : 10.1186/1471-2105-11-403 . — PMID 20667133 .
E. Arias-Castro, G. Chen, G. Lerman. Spektral klustring baserad på lokala linjära approximationer. // Electronic Journal of Statistics. - 2011. - T. 5 . - S. 1537-1587 . - doi : 10.1214/11-ejs651 .
IS Dhillon, Y. Guan, B. Kulis. Kernel k -betyder: spektral klustring och normaliserade skärningar // Proceedings of the tionth ACM SIGKDD international conference on Knowledge discovery and data mining. - 2004. - S. 551-556.
Inderjit Dhillon, Yuqiang Guan, Brian Kulis. Viktade grafklipp utan egenvektorer: en strategi på flera nivåer // IEEE-transaktioner på mönsteranalys och maskinintelligens. - 2007. - November ( vol. 29 , nummer 11 ). - doi : 10.1109/tpami.2007.1115 .
Ravi Kannan, Santosh Vempala, Adrian Vetta. Om kluster: Bra. Dålig och spektral // Journal of the ACM. - 2000. - T. 51 . - doi : 10.1145/990308.990313 .