OPTIK klustringsalgoritm

Ordningspunkter för att identifiera klustringsstrukturen ( OPTICS ) är en algoritm för att hitta [1] kluster i rumslig data baserat på densitet . Algoritmen presenterades av Michael Ankerst, Markus M. Breunig, Hans-Peter Kriegel och Jörg Sander [2] . Grundidén med algoritmen liknar DBSCAN [3] , men algoritmen är utformad för att bli av med en av de största svagheterna i DBSCAN-algoritmen - problemet med att upptäcka meningsfulla kluster i data med olika densiteter. För att göra detta ordnas databaspunkterna (linjärt) så att spatialt nära punkter blir grannar i ordningen. Dessutom lagras ett speciellt avstånd för varje punkt, som representerar den densitet som måste antas för klustret så att punkterna tillhör samma kluster. Detta representeras som ett dendrogram .

Huvudidé

Liksom DBSCAN kräver OPTICS-algoritmen två parametrar - parametern ε beskriver det maximala avståndet (radien) som tas med i beräkningen, och MinPts- parametern beskriver antalet punkter som krävs för att bilda ett kluster. En punkt p är en kärnpunkt om minst MinPts av punkter finns i dess ε -grannskap . Till skillnad från DBSCAN tar OPTICS- algoritmen också hänsyn till punkter som är en del av ett tätare kluster, så att varje punkt tilldelas ett grundläggande avstånd , som beskriver avståndet till MinPts :e närmaste punkt: $N_{\varepsilon }(p)$

{\text{core-dist}}_{\mathit {\varepsilon ,MinPts}}={\begin{cases}{\text{UNDEFINED}}&|N_{\varepsilon }(p)|<{ \mathit {MinPts}}\\{\mathit {MinPts}}{\text{-th}}N_{\varepsilon }(p)&|N_{\varepsilon }(p)|\geqslant {\mathit {MinPts} }\end{cases}}

Här core-dist = kärnavstånd, = -th i stigande ordning av avstånd till . ${\mathit {MinPts}}{\text{-th}}N_{\varepsilon }(p)$ ${\mathit {MinPts))$ $N_{\varepsilon }(p)$

Det uppnåbara avståndet för punkt o från punkt p är antingen avståndet mellan o och p , eller grundavståndet för punkt p , vilket som är störst:

{\text{reachability-dist}}_{\mathit {\varepsilon ,MinPts}}(o,p)={\begin{cases}{\text{UNDEFINED}}&|N_{\varepsilon }( p)|<{\mathit {MinPts}}\\\max({\text{core-dist}}_{\mathit {\varepsilon ,MinPts}}(p),{\text{dist}}(p, o))&|N_{\varepsilon }(p)|\geqslant {\mathit {MinPts}}\end{cases}}

Här nåbarhet-avstånd = nåbart avstånd.

Om p och o är närmaste grannar, och , kan vi anta att p och o tillhör samma kluster. $\varepsilon '<\varepsilon$

Både de grundläggande och nåbara avstånden är odefinierade om det inte finns ett tillräckligt tätt kluster (som tillämpat på ε ). Med en tillräckligt stor ε kommer detta aldrig att hända, men då kommer varje ε -grannskapsfråga att returnera hela databasen, vilket resulterar i körtid . Parametern ε krävs för att skära bort lösa kluster som inte längre är intressanta och därigenom påskynda algoritmen. $O(n^{2})$

Parametern ε är strängt taget valfri. Det kan helt enkelt ställas in på högsta möjliga värde. Men när ett rumsligt index är tillgängligt påverkar det beräkningskomplexiteten. OPTICS skiljer sig från DBSCAN genom att denna parameter inte beaktas, om ε kan påverka, då endast genom att sätta maxvärdet.

Pseudokod

Det grundläggande tillvägagångssättet för OPTICS-algoritmen är detsamma som DBSCAN , men istället för att stödja många kända men ännu inte bearbetade klustermedlemmar, används en prioritetskö (dvs. indexerad heap ).

OPTICS(DB, eps, MinPts) för varje punkt p från DB p.reachable_distance=odefinierad för varje råpunkt p från DB N=getNeighbors (s, eps) markera p som bearbetad sätt p i en ordnad lista if (bas_distance(p, eps, Minpts) != odefinierat) Seeds=tom prioritetskö refresh(N, p, Seeds, eps, Minpts) för varje nästa q från Seeds N'=getNeighbors(q, eps) markera q som bearbetad sätt q i en ordnad lista if (basic_distance(q, eps, Minpts) != odefinierat) update(N', q, Seeds, eps, Minpts)

I update()-proceduren uppdateras Seeds-prioritetskön av -grannar till punkterna och följaktligen : $\varepsilon$ $sid$ $q$

uppdatering (N, p, Seeds, eps, Minpts) coredist=base_distance(p, eps, MinPts) för varje o i N om (o inte behandlat) new_dist_dist=max(coredist, dist(p,o)) if (o.reachable_distance == odefinierad) // punkt o finns inte i Seeds o.reach_distance=new_reach_distance Seeds.insert(o, new_delivery_dist) annars // pricka o i Seeds, se efter förbättringar if (new_reach_distance < o.reach_distance) o.reach_distance=new_reach_distance Seeds.move_up(o, new_advance_growth)

OPTICS placerar punkter i en viss ordning och markerar dem med det minsta möjliga avståndet (i den ursprungliga algoritmen kommer huvudavståndet också ihåg, men detta krävs inte för vidare bearbetning).

Extrahera kluster

Med hjälp av en nåbarhetsgraf (en speciell typ av träddiagram ) är det lätt att få en hierarkisk struktur av kluster. Detta är en 2D-plot där punkter plottas på x-axeln i den ordning de bearbetas av OPTICS-algoritmen, och det nåbara avståndet plottas på y-axeln. Eftersom punkter som hör till ett kluster har ett litet nåbart avstånd till sin närmaste granne, ser kluster ut som dalar på en nåbarhetstomt. Ju djupare dalen är, desto tätare blir klustret.

Figuren ovan illustrerar detta koncept. Det övre vänstra området i figuren visar den simulerade datamängden. Det övre högra området av figuren visualiserar det spännande trädet som erhålls av OPTICS-algoritmen, och den nedre delen av figuren visar nåbarhetsdiagrammet som erhålls av OPTICS. Färgerna i denna graf är etiketter och beräknas inte av algoritmen. Det är dock tydligt att se hur dalarna på grafen motsvarar klustren i den givna datamängden. De gula prickarna i den här bilden anses vara brus och motsvarar inte några dalar. De är vanligtvis inte tilldelade några kluster, förutom det övergripande "all data"-klustret i det hierarkiska resultatet.

Att extrahera kluster från en sådan graf kan göras manuellt genom att välja intervall på x-axeln efter att ha tittat på grafen, genom att välja ett tröskelvärde på y-axeln (då liknar resultatet DBSCAN-klustring med samma parametervärden och minPts, i vårt fall kan ett värde på 0,1 ge bra resultat), eller genom att använda olika algoritmer som försöker bestämma dalarna genom grafens branthet, av kurvan eller med lokala maxima. Klustringar som erhålls på detta sätt är vanligtvis hierarkiska och kan inte erhållas i en enda körning av DBSCAN-algoritmen. $\varepsilon$

Svårighet

Precis som DBSCAN bearbetar OPTICS-algoritmen varje punkt endast en gång och utför en grannfråga denna bearbetning . Givet ett rumsligt index som säkerställer att grannskapsfrågan körs i tid får vi den totala körtiden . Författarna till den ursprungliga artikeln om OPTIK rapporterar en konstant nedgång på 1,6 gånger jämfört med DBSCAN. Observera att värdet i hög grad kan påverka kostnaden för algoritmen, eftersom ett för stort värde kan öka komplexiteten i grannskapsfrågan till en linjär. $O(\log n)$ $O(n\cdot\log n)$ $\varepsilon$

I synnerhet är ett urval (större än det maximala avståndet i datamängden) möjligt, men leder uppenbarligen till kvadratisk komplexitet, eftersom en grannlistasfråga returnerar hela datasetet. Även om inget rumsligt index är tillgängligt, resulterar detta i ytterligare omkostnader för att upprätthålla högen. Därför bör man välja rätt för datamängden. $\varepsilon >\max _{x,y}d(x,y)$ $\varepsilon$

Tillägg

OPTICS-OF [4] är en anomalidetekteringsalgoritm baserad på OPTICS . Den används huvudsakligen för att extrahera extremvärden från en befintlig körning av OPTICS-algoritmen till en låg kostnad jämfört med andra extraktionsmetoder. Den mest kända versionen av den lokala algoritmen för detektering av extremvärden är baserad på samma koncept.

DeLi-Clu [5] , ( Density-Link-Clustering ) kombinerar idéer från den enda klustringsmetoden och OPTICS-algoritmen, eliminerar parametern och lägger till effektivitetsförbättringar jämfört med OPTICS. $\varepsilon$

HiSC [6] är en hierarkisk subrymdklustringsmetod (parallellt med axlarna) baserad på OPTIK.

HiCO [7] är en hierarkisk korrelationsklustringsalgoritm baserad på OPTIK.

DiSH [8] är en förbättring av HiSC-algoritmen som kan hitta mer komplexa hierarkier.

FOPTIC [9] är en snabb implementering med slumpmässiga projektioner.

HDBSCAN* [10] är baserad på en förbättring av DBSCAN-algoritmen genom att utesluta gränspunkter från kluster och därmed en mer rigorös definition av densitetsnivåer (enligt Hartigan) [11] .

Tillgänglighet

Java-implementationer av OPTICS, OPTICS-OF, DeLi-Clu, HiSC, HiCO och DiSH är tillgängliga i ELKI data mining-systemet (med accelererat index för vissa avståndsfunktioner och med automatisk klustring med ξ-metoden). En annan Java-implementering inkluderar en tillägg till Weka-verktygssatsen (inget stöd för klustring med ξ). R - språkpaketet "dbscan" inkluderar en C++-implementering av OPTICS-algoritmen (med både traditionell klustring som dbscan och ξ) som använder ett K-dimensionellt träd för att påskynda indexet för euklidiskt avstånd.

Språket Python har följande implementeringar. OPTICS är tillgängligt i PyClustering-biblioteket . HDBSCAN är tillgängligt i hdbscan-biblioteket , som är byggt ovanpå scikit learning .

Anteckningar

↑ Kriegel, Kröger, Sander, Zimek, 2011 , sid. 231–240.
↑ Ankerst, Breunig, Kriegel, Sander, 1999 , sid. 49–60.
↑ Ester, Kriegel, Sander, Xu, 1996 , sid. 226–231.
↑ Breunig, Kriegel, Ng, Sander, 1999 , sid. 262–270.
↑ Achtert, Böhm, Kröger, 2006 , sid. 119–128.
↑ Achtert, Böhm, Kriegel, Kröger, Müller-Gorman, Zimek, 2006 , sid. 446–453.
↑ Achtert, Böhm, Kröger, Zimek, 2006 , sid. 119–128.
↑ Achtert, Böhm, Kriegel, Kröger, Müller-Gorman, Zimek, 2007 , sid. 152–163.
↑ Schneider, Vlachos, 2013 .
↑ Campello, Moulavi, Zimek, Sander, 2015 , sid. 1–51.
↑ Hartigan, 1975 .

Litteratur

Hans-Peter Kriegel, Peer Kröger, Jörg Sander, Arthur Zimek. Densitetsbaserad klustring // Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery. - 2011. - Maj ( vol. 1 , nummer 3 ). — S. 231–240 . - doi : 10.1002/widm.30 .
Mihael Ankerst, Markus M. Breunig, Hans-Peter Kriegel, Jörg Sander. OPTIK: Beställningspunkter för att identifiera klustringsstrukturen // =ACM SIGMOD internationell konferens om hantering av data . - ACM Press , 1999. - S. 49-60.
Martin Ester, Hans-Peter Kriegel, Jörg Sander, Xiaowei Xu. En densitetsbaserad algoritm för att upptäcka kluster i stora rumsliga databaser med brus // Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96) / Evangelos Simoudis, Jiawei Han, Usama M. Fayyad. - AAAI Press , 1996. - S. 226-231. — ISBN 1-57735-004-9 .
Markus M. Breunig, Hans-Peter Kriegel, Raymond T. Ng, Jörg Sander. OPTICS-OF: Identify Local Outliers // Principer för datautvinning och kunskapsupptäckt . - Springer-Verlag , 1999. - S. 262 -270. - ISBN 978-3-540-66490-1 . - doi : 10.1007/b72280 .
Achtert E., Böhm C., Kröger P. DeLi-Clu: Öka robusthet, fullständighet, användbarhet och effektivitet hos hierarkisk klustring genom en rankning av närmaste par. - 2006. - T. 3918. - S. 119-128. — (Föreläsningsanteckningar i datavetenskap). - ISBN 978-3-540-33206-0 . - doi : 10.1007/11731139_16 .
Achtert E., Böhm C., Kriegel HP, Kröger P., Müller-Gorman I., Zimek A. Finding Hierarchies of Subspace Clusters // LNCS: Knowledge Discovery in Databases: PKDD 2006. - 2006. - V. 4213 . — S. 446–453 . - ISBN 978-3-540-45374-1 . - doi : 10.1007/11871637_42 .
Achtert E., Böhm C., Kröger P., Zimek A. Mining Hierarchies of Correlation Clusters // Proc. 18:e internationella konferensen om vetenskaplig och statistisk databashantering (SSDBM). - 2006. - S. 119-128. — ISBN 0-7695-2590-3 . - doi : 10.1109/SSDBM.2006.35 .
Achtert E., Böhm C., Kriegel HP, Kröger P., Müller-Gorman I., Zimek A. Detektion och visualisering av subrymdklusterhierarkier // LNCS: Framsteg i databaser: koncept, system och applikationer. - 2007. - T. 4443 . — S. 152–163 . - ISBN 978-3-540-71702-7 . - doi : 10.1007/978-3-540-71703-4_15 .
Johannes Schneider, Michail Vlachos. Snabb parameterlös densitetsbaserad klustring via slumpmässiga projektioner // 22nd ACM International Conference on Information and Knowledge Management (CIKM). — ACM, 2013.
Campello RJGB, Davoud Moulavi, Arthur Zimek, Jörg Sander. Hierarkiska densitetsuppskattningar för datakluster, visualisering och detektering av extremvärden // ACM-transaktioner på kunskapsupptäckt från data. - 2015. - T. 10 , nr. 1 . — S. 1–51 . - doi : 10.1145/2733381 .
John A Hartigan klustringsalgoritmer. - John Wiley & Sons, 1975. - (Wiley-serien i sannolikhets- och matematisk statistik). — ISBN 0-471-35645-X .

Maskininlärning och datautvinning
Uppgifter	Klassificeringsproblem Lärande utan lärare Lärarassisterat lärande Regressionsanalys AutoML Föreningens regler Särdragsextraktion Egenskapsträning Ranking utbildning Grammatisk härledning Online lärande
Att lära sig med en lärare	k-närmaste granne metod Naiv Bayes klassificerare beslutsträd Stöd vektor maskin Linjär regression Logistisk tillbakagång perceptron Ensembler av modeller Säckväv förstärkning slumpmässig skog Relevant vektormetod
klusteranalys	k-betyder metod Fuzzy klustringsmetod Hierarkisk klustring EM algoritm BJÖRK BOTA DBSCAN OPTIK Genomsnittlig förskjutning
Dimensionalitetsreduktion	Faktoranalys Huvudkomponentmetoden CCA ICA LDA Icke-negativ matrisexpansion t-SNE
Strukturell prognos	Graph probabilistisk modell Bayesiskt nätverk Dold Markov-modell CRF
Anomali upptäckt	k-närmaste granne metod Lokal utsläppsnivå
Grafisk probabilistiska modeller	Bayesiskt nätverk Markov nätverk Dold Markov-modell
Neurala nätverk	Begränsad Boltzmann-maskin självorganiserande karta Aktiveringsfunktion Sigmoid softmax Radiell basfunktion Ryggförökningsmetod Djup lärning Flerskiktsperceptron Återkommande neurala nätverk långtidsminne Kontrollerat återkommande block Konvolutionellt neuralt nätverk U-nät Autokodare
Förstärkningsinlärning	Markov process Bellmans ekvation Girig algoritm Q-lärande SARSA Temporell skillnad (TD)
Teori	Vapnik-Chervonenkis teori Bias-Dispersion Dilemma Beräkningslärandeteori Empirisk riskminimering Occam lär sig PAC-inlärning Statistisk inlärningsteori
Tidskrifter och konferenser	NeurIPS ICML ML JMLR ArXiv:cs.LG