Spektrální shlukování

Techniky spektrálního shlukování používají spektrum ( vlastní čísla ) matice podobnosti dat k provedení redukce rozměrů před shlukováním v prostorech nižších rozměrů. Matice podobnosti je uvedena jako vstup a skládá se z kvantitativních odhadů relativní podobnosti každé dvojice bodů v datech.

Při aplikaci na segmentaci obrazu je spektrální shlukování známé jako shlukování vlastností založené na segmentaci .

Algoritmy

Daný výčetný soubor datových bodů, podobnostní matice může být definována jako symetrická matice , kde prvky představují míru podobnosti mezi datovými body s indexy a . Obecným principem spektrálního shlukování je použití standardní metody shlukování (takových metod je mnoho, metoda k-means je diskutována níže ) na významných vlastních vektorech Kirchhoffovy matice matice . Existuje mnoho různých způsobů, jak definovat Kirchhoffovu matici, která má různé matematické interpretace, takže shlukování bude mít také různé interpretace. Významné vlastní vektory jsou ty, které odpovídají několika nejmenším vlastním hodnotám Kirchhoffovy matice, s výjimkou vlastních čísel 0. Pro efektivitu výpočtu jsou tyto vlastní vektory často počítány jako vlastní vektory odpovídající některým z největších vlastních čísel funkce Kirchhoffovy matice. $A$ $A_{ij}\geq 0$ $i$ $j$ $A$

Jednou z technik pro spektrální shlukování je algoritmus normalizované sekce (nebo algoritmus Shi-Malik ) navržený Jiambo Shi a Jitendra Malik [1] , široce používaná metoda pro segmentaci obrazu . Algoritmus rozdělí body do dvou množin na základě vlastního vektoru odpovídajícího druhému největšímu vlastnímu číslu symetricky normalizované Kirchhoffovy matice dané vzorcem $(B_{1},B_{2})$ $proti$

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

kde je diagonální matice $D$

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

Matematicky ekvivalentní algoritmus [2] používá vlastní vektor odpovídající největší vlastní hodnotě normalizované Kirchhoffovy matice náhodné procházky . Algoritmus Meil–Shi byl testován v kontextu difúzních map , u kterých bylo zjištěno, že mají spojitost s výpočetní kvantovou mechanikou [3] . $P=D^{-1}A$

Další možností je použití Kirchhoffovy matice dané výrazem

L:=DA

spíše než symetricky normalizovaná Kirchhoffova matice.

Rozdělení lze provést různými způsoby, jako je výpočet mediánu složek druhého nejmenšího vlastního vektoru a umístění všech bodů do , jejichž složky v jsou větší než , zbytek bodů je umístěn do . Algoritmus lze použít pro hierarchické shlukování postupným rozdělením podmnožin podobným způsobem. $m$ $proti$ $B_1$ $proti$ $m$ $B_{2}$

Pokud matice podobnosti ještě nebyla zkonstruována algebraicky, lze účinnost spektrálního shlukování zlepšit, pokud se řešení odpovídajícího problému - hledání vlastních čísel - provádí metodou bez matic (bez explicitní manipulace nebo dokonce výpočtu matice podobnosti), jako je Lanczosův algoritmus . $A$

U grafů velké velikosti je druhá vlastní hodnota (normalizované) Kirchhoffovy matice grafu často špatně podmíněná , což vede k pomalé konvergenci iterativních metod hledání vlastních hodnot. Předběžná úprava je klíčovou technikou pro zlepšení konvergence, například v bezmaticové metodě LOBPCG . Spektrální shlukování bylo úspěšně aplikováno na velké grafy nejprve rozpoznáním struktury síťové komunity a poté shlukováním komunity [4] .

Spektrální shlukování úzce souvisí s nelineární redukcí dimenzionality a techniky redukce dimenzionality, jako je lokálně lineární vnoření, lze použít ke snížení chyby způsobené šumem nebo odlehlými hodnotami v pozorováních [5] .

Svobodný software pro implementaci spektrálního shlukování je dostupný ve velkých open source projektech, jako je Scikit-learn [6] , MLlib pro shlukování založené na pseudovlastních hodnotách pomocí metody power iterace [7] , jazyk R [8] .

Vztah s k - znamená

Problém k -means s nelineárním jádrem je rozšířením problému k -means, ve kterém jsou vstupní body mapovány nelineárně do vysokorozměrného prostoru funkcí pomocí funkce jádra . Problém váženého k -means s nelineárním jádrem tento problém dále rozšiřuje tím, že určuje váhu pro každý shluk jako hodnotu nepřímo úměrnou počtu prvků shluku, $k(x_{i},x_{j})=\varphi ^{T}(x_{i})\varphi (x_{j})$ $w_{r}$

\max _{\{C_{s}\}}\součet _{r=1}^{k}w_{r}\součet _{x_{i},x_{j}\v C_{r }}k(x_{i},x_{j}).

Nechť je matice normalizovaných koeficientů pro každý bod libovolného shluku, kde , if , a 0 jinak. Nechť je matice jádra pro všechny body. Problém váženého k -means s nelineárním jádrem s n body a k shluky je definován jako problém maximalizace $F$ ${\displaystyle F_{ij}=w_{r))$ ${\displaystyle i,j\in C_{r))$ $K$

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

za podmínek

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

G^{T}G=E

Ve stejnou dobu . Kromě toho existuje omezení na koeficienty $\operatorname {rank} (G)=k$ $F$

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

kde je vektor jednotek. $\mathbf{1}$

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

Úkol lze převést na

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

Tento problém je ekvivalentní problému spektrálního shlukování, když je omezení na uvolněné. Konkrétně problém vážených k -means s nelineárním jádrem může být přeformulován jako problém spektrálního shlukování (rozdělení grafu) a naopak. Výstupem algoritmu jsou vlastní vektory, které nesplňují omezení pro proměnné indikátoru definované vektorem . Proto je nutné následné zpracování vlastních vektorů, aby úlohy byly ekvivalentní [9] . Transformace problému spektrálního shlukování na vážený problém k -means s nelineárním jádrem výrazně snižuje výpočetní náklady [10] . $F$ $F$

Opatření pro porovnávání shlukování

Ravi Kannan, Santosh Vempala a Adrian Wetta [11] navrhli bikriteriální měřítko pro určení kvality shlukování. Říkají, že shlukování je (α, ε)-shlukování, pokud vodivost každého shluku je alespoň α a váha mezishlukových hran nepřesahuje ε zlomek hmotnosti všech hran v grafu. Ve stejném článku také zvažují dva aproximační algoritmy.

Viz také

Metoda šíření blízkosti
Metoda jaderné hlavní součásti
shluková analýza
Teorie spektrálních grafů

Poznámky

↑ Shi, Malik, 2000 .
↑ Meilă, Shi, 2001 , str. 873–879.
↑ Scott, Therani, Wang, 2017 , str. 1-17.
↑ Zare, Shooshtari, Gupta, Brinkman, 2010 , str. 403.
↑ Arias-Castro, Chen, Lerman, 2011 , str. 1537–1587
↑ 2.3. Clustering - dokumentace scikit-learn 0.20.2 . Získáno 28. června 2017. Archivováno z originálu 15. května 2015. (neurčitý)
↑ Clustering – API založené na RDD – Dokumentace Spark 2.4.0 . Získáno 28. června 2017. Archivováno z originálu 3. července 2017. (neurčitý)
↑ CRAN - Package kernlab . Získáno 28. června 2017. Archivováno z originálu 27. června 2017. (neurčitý)
↑ Dhillon, Guan, Kulis, 2004 , str. 551–556.
↑ Dhillon, Guan, Kulis, 2007 , str. 1-14.
↑ Kannan, Vempala, Vetta, 2000 , str. 497–515.

Literatura

Marina Meila, Jianbo Shi. Segmentace učení náhodnými procházkami // Systémy zpracování neuronových informací . - 2001. - V. 13 (NIPS 2000). Archivováno 10. prosince 2015 na Wayback Machine
Jianbo Shi, Jitendra Malik. Normalizované řezy a segmentace obrazu // Transakce IEEE na PAMI. - 2000. - Srpen ( díl 22 , číslo 8 ).
T. C. Scott, Madhusudan Therani, Xing M. Wang. Shlukování dat pomocí kvantové mechaniky // Matematika. - 2017. - V. 5 , č.p. 1 . — S. 1–17 . doi : 10,3390 / matematický 5010005 .
Habil Zare, P. Shooshtari, A. Gupta, R. Brinkman. Redukce dat pro spektrální shlukování pro analýzu dat z průtokové cytometrie s vysokou propustností // BMC Bioinformatics. - 2010. - T. 11 . - S. 403 . - doi : 10.1186/1471-2105-11-403 . — PMID 20667133 .
E. Arias-Castro, G. Chen, G. Lerman. Spektrální shlukování založené na lokálních lineárních aproximacích. // Electronic Journal of Statistics. - 2011. - T. 5 . - S. 1537-1587 . - doi : 10.1214/11-ejs651 .
IS Dhillon, Y. Guan, B. Kulis. Kernel k -means: spectral clustering and normalized cuts // Sborník z desáté mezinárodní konference ACM SIGKDD o Knowledge discovery and data mining. - 2004. - S. 551-556.
Inderjit Dhillon, Yuqiang Guan, Brian Kulis. Váhové řezy grafů bez vlastních vektorů: Víceúrovňový přístup // Transakce IEEE na analýze vzorů a strojové inteligenci. - 2007. - Listopad ( díl 29 , číslo 11 ). - doi : 10.1109/tpami.2007.1115 .
Ravi Kannan, Santosh Vempala, Adrian Vetta. Na shlucích: Dobrý. Bad and Spectral // Journal of the ACM. - 2000. - T. 51 . - doi : 10.1145/990308.990313 .