OPTICS Clustering Algorithm

Pisteiden järjestäminen klusterointirakenteen tunnistamiseksi ( OPTICS ) on algoritmi [1] klustereiden löytämiseksi paikkatiedoista tiheyden perusteella . Algoritmin esittelivät Michael Ankerst, Markus M. Breunig, Hans-Peter Kriegel ja Jörg Sander [2] . Algoritmin perusidea on samanlainen kuin DBSCAN [3] , mutta algoritmi on suunniteltu pääsemään eroon yhdestä DBSCAN-algoritmin tärkeimmistä heikkouksista - ongelmasta havaita merkityksellisiä klustereita tiedoissa, joilla on eri tiheydet. Tätä varten tietokantapisteet järjestetään (lineaarisesti) siten, että spatiaalisesti läheisistä pisteistä tulee järjestyksen naapureita. Lisäksi jokaiselle pisteelle tallennetaan erityinen etäisyys, joka edustaa tiheyttä, joka on oletettava klusterille, jotta pisteet kuuluvat samaan klusteriin. Tämä esitetään dendrogrammina .

Pääidea

Kuten DBSCAN , OPTICS-algoritmi vaatii kaksi parametria - ε -parametri kuvaa huomioon otettavan enimmäisetäisyyden (säteen) ja MinPts- parametri kuvaa klusterin muodostamiseen tarvittavien pisteiden määrää. Piste p on ydinpiste , jos sen ε -naapurissa on vähintään MinPts pisteitä . Toisin kuin DBSCAN , OPTICS-algoritmi ottaa huomioon myös pisteet, jotka ovat osa tiheämpää klusteria, joten jokaiselle pisteelle on määritetty perusetäisyys , joka kuvaa etäisyyttä MinPts :n lähimpään pisteeseen: $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}}

Tässä core-dist = ydinetäisyys, = -th etäisyyden nousevassa järjestyksessä . ${\mathit {MinPts}}{\text{-th}}N_{\varepsilon }(p)$ ${\mathit {MinPts))$ $N_{\varepsilon }(p)$

Pisteen o saavutettavissa oleva etäisyys pisteestä p on joko pisteiden o ja p välinen etäisyys tai pisteen p perusetäisyys sen mukaan , kumpi on suurempi:

{\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}}

Tässä tavoitettavuus-dist = tavoitettavissa oleva etäisyys.

Jos p ja o ovat lähimmät naapurit ja , voimme olettaa, että p ja o kuuluvat samaan klusteriin. $\varepsilon '<\varepsilon$

Sekä perus- että saavutettavat etäisyydet ovat määrittelemättömiä, ellei ole riittävän tiheää klusteria ( soveltuen ε :lle ). Riittävän suurella ε :llä tätä ei koskaan tapahdu, mutta silloin mikä tahansa ε -naapurustokysely palauttaa koko tietokannan, mikä johtaa ajoaikaan . Parametria ε tarvitaan poistamaan löysät klusterit, jotka eivät enää ole kiinnostavia, ja siten nopeuttamaan algoritmia. $O(n^{2})$

Parametri ε on tarkasti ottaen valinnainen. Se voidaan yksinkertaisesti asettaa suurimmalle mahdolliselle arvolle. Kuitenkin, kun spatiaalinen indeksi on saatavilla, se vaikuttaa laskennan monimutkaisuuteen. OPTICS eroaa DBSCANista siinä, että tätä parametria ei oteta huomioon, jos ε voi vaikuttaa, niin vain asettamalla maksimiarvon.

Pseudokoodi

OPTICS-algoritmin peruslähestymistapa on sama kuin DBSCAN , mutta sen sijaan, että tuettaisiin monia tunnettuja, mutta ei vielä käsiteltyjä klusterin jäseniä, käytetään prioriteettijonoa (eli indeksoitua kasaa ).

OPTIIKA (DB, eps, MinPts) jokaiselle pisteelle p DB:stä p.reachable_distance=undefined jokaiselle raakapisteelle p DB:stä N=getNaapurit (p, eps) merkitse p käsitellyksi laita p järjestettyyn luetteloon if (perusetäisyys(p, eps, minpts) != määrittelemätön) Seeds=tyhjä prioriteettijono päivitä (N, p, Siemenet, eps, Minpts) jokaista seuraavaa q:ta varten Seedsistä N'=getNeighbors(q, eps) merkitse q käsitellyksi laita q järjestetylle listalle if (perusetäisyys(q, eps, minpts) != määrittelemätön) päivitys (N', q, siemenet, eps, minpts)

Update()-proseduurissa Seeds-prioriteettijono päivitetään pisteiden -naapureiden toimesta ja vastaavasti: $\varepsilon$ $s$ $q$

päivitys (N, p, Seeds, eps, Minpts) coredist=base_distance(p, eps, MinPts) jokaiselle o:lle N:ssä jos (ei käsitelty) new_dist_dist=max(coredist, dist(p,o)) if (o.reachable_distance == undefined) // piste o ei ole Seedsissä o.reach_distance=new_reach_distance Seeds.insert(o, new_delivery_dist) muussa tapauksessa // piste o siemenissä, tarkista parannukset jos (uusi_tavoittavuuden_etäisyys < o.tavoittavuuden_etäisyys) o.reach_distance=new_reach_distance Seeds.move_up(o, new_advance_growth)

OPTICS sijoittaa pisteet tiettyyn järjestykseen ja merkitsee ne pienimmällä saavutettavalla etäisyydellä (alkuperäisessä algoritmissa pääetäisyys myös muistetaan, mutta sitä ei tarvita jatkokäsittelyyn).

Klusterien purkaminen

Saavutettavuuskaavion (erityinen puukaavio ) avulla on helppo saada hierarkkinen klusterirakenne. Tämä on 2D-kaavio, jossa pisteet piirretään x-akselille siinä järjestyksessä, jossa ne on käsitelty OPTICS-algoritmilla, ja saavutettava etäisyys piirretään y-akselille. Koska klusteriin kuuluvilla pisteillä on pieni tavoitettavissa oleva etäisyys lähimpään naapuriinsa, klusterit näyttävät laaksoilta saavutettavuuskuvaajalla. Mitä syvempi laakso, sitä tiheämpi klusteri.

Yllä oleva kuva havainnollistaa tätä käsitettä. Kuvan vasemmassa yläkulmassa näkyy simuloitu tietojoukko. Kuvan oikea yläosa visualisoi OPTICS-algoritmilla saatua virittävää puuta ja kuvan alaosassa on OPTICSilla saatu saavutettavuuskäyrä. Tämän kaavion värit ovat otsikoita, eikä algoritmi laske niitä. On kuitenkin selvästi nähtävissä, kuinka kaavion laaksot vastaavat annetun tietojoukon klustereita. Tämän kuvan keltaisia pisteitä pidetään kohinaina, eivätkä ne vastaa laaksoja. Niitä ei yleensä osoiteta millekään klusterille, paitsi hierarkkisen tuloksen kattavalle "kaikki tiedot" -klusterille.

Klusterien purkaminen tällaisesta kaaviosta voidaan tehdä manuaalisesti valitsemalla aikavälit x-akselilta kaavion katselun jälkeen, valitsemalla kynnys y-akselilta (silloin tulos on samanlainen kuin DBSCAN-klusterointi samoilla parametriarvoilla ja minPts, meidän tapauksessamme arvo 0,1 voi antaa hyviä tuloksia), tai käyttämällä erilaisia algoritmeja, jotka yrittävät määrittää laaksot kaavion jyrkkyyden, mutkan tai paikallisten maksimien perusteella. Tällä tavalla saadut klusterit ovat yleensä hierarkkisia , eikä niitä voida saada yhdellä DBSCAN-algoritmin ajolla. $\varepsilon$

Vaikeus

Kuten DBSCAN , OPTICS algoritmi käsittelee jokaisen pisteen vain kerran ja suorittaa yhden naapurikyselyn tämän käsittelyn aikana. Kun annetaan spatiaalinen indeksi , joka varmistaa, että naapurustokysely suoritetaan ajallaan , saadaan kokonaiskestoaika . Alkuperäisen OPTICS-artikkelin kirjoittajat raportoivat jatkuvasta 1,6-kertaisesta hidastumisesta DBSCANiin verrattuna. Huomaa, että arvo voi vaikuttaa suuresti algoritmin kustannuksiin, koska liian suuri arvo voi lisätä naapurustokyselyn monimutkaisuuden lineaariseksi. $O(\log n)$ $O(n\cdot\log n)$ $\varepsilon$

Erityisesti valinta (suurempi kuin tietojoukon enimmäisetäisyys) on mahdollista, mutta se johtaa luonnollisesti neliölliseen monimutkaisuuteen, koska naapuriluettelokysely palauttaa koko tietojoukon. Vaikka spatiaalista indeksiä ei olisi saatavilla, tämä johtaa ylimääräiseen keon ylläpitoon. Siksi tietojoukolle tulisi valita oikein. $\varepsilon >\max _{x,y}d(x,y)$ $\varepsilon$

Laajennukset

OPTICS-OF [4] on OPTISIIN perustuva poikkeamien havaitsemisalgoritmi . Sitä käytetään pääasiassa poikkeamien poimimiseen olemassa olevasta OPTICS-algoritmin ajosta alhaisin kustannuksin verrattuna muihin poikkeavien erotusmenetelmiin. Tunnetuin versio paikallisten outlier-ilmaisualgoritmista perustuu samoihin käsitteisiin.

DeLi-Clu [5] ( Density -Link-Clustering ) yhdistää ideat yksittäisestä klusterointimenetelmästä ja OPTICS-algoritmista eliminoiden parametrin ja lisäämällä tehokkuuden parannuksia OPTICSiin verrattuna. $\varepsilon$

HiSC [6] on OPTIIKKAAN perustuva hierarkkinen aliavaruusklusterointimenetelmä (akselien rinnalla).

HiCO [7] on OPTIIKKAAN perustuva hierarkkinen korrelaatioklusterointialgoritmi

DiSH [8] on parannus HiSC-algoritmiin, joka pystyy löytämään monimutkaisempia hierarkioita.

FOPTICS [9] on nopea toteutus, jossa käytetään satunnaisia projektioita.

HDBSCAN* [10] perustuu DBSCAN-algoritmin parannukseen jättämällä rajapisteet pois klustereista ja siten tiukempaan tiheystasojen määritelmään (Hartiganin mukaan) [11] .

Saatavuus

ELKI tiedonlouhintajärjestelmässä on saatavilla OPTICSin, OPTICS-OF:n, DeLi-Clu:n, HiSC:n, HiCO:n ja DiSH:n Java-toteutuksia (joillekin etäisyysfunktioille kiihdytetyllä indeksillä ja automaattisella klusteroinnilla ξ-menetelmällä). Toinen Java-toteutus sisältää laajennuksen Weka-työkalupakettiin (ei tukea klusterointia ξ:n kanssa). R - kielipaketti "dbscan" sisältää OPTICS-algoritmin C++-toteutuksen (sekä perinteisen klusteroinnin, kuten dbscanin ja ξ:n kanssa), käyttämällä K-ulotteista puuta nopeuttamaan euklidisen etäisyyden indeksiä.

Python-kielellä on seuraavat toteutukset. OPTICS on saatavilla PyClustering-kirjastossa . HDBSCAN on saatavilla hdbscan-kirjastossa , joka on rakennettu scikit learningin päälle .

Muistiinpanot

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

Kirjallisuus

Hans-Peter Kriegel, Peer Kröger, Jörg Sander, Arthur Zimek. Tiheyspohjainen klusterointi // Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery. - 2011. - toukokuu ( osa 1 , numero 3 ). — S. 231–240 . - doi : 10.1002/leveys.30 .
Mihael Ankerst, Markus M. Breunig, Hans-Peter Kriegel, Jörg Sander. OPTIIKA: Tilauspisteet klusterointirakenteen tunnistamiseksi // =ACM SIGMOD kansainvälinen tiedonhallintakonferenssi . - ACM Press , 1999. - S. 49-60.
Martin Ester, Hans-Peter Kriegel, Jörg Sander, Xiaowei Xu. Tiheyteen perustuva algoritmi klusterien löytämiseen suurista paikkatietokannoista kohinalla // 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: Paikallisten poikkeavien tekijöiden tunnistaminen // Tiedon louhinnan ja tiedon löytämisen periaatteet . - 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: Hierarkkisen klusteroinnin kestävyyden, täydellisyyden, käytettävyyden ja tehokkuuden lisääminen lähimmän parin luokituksen avulla. - 2006. - T. 3918. - S. 119-128. — (Luentomuistiinpanot tietojenkäsittelytieteestä). - 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. kansainvälinen tieteellisen ja tilastollisen tietokannan hallinnan konferenssi (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. Alitilan klusterihierarkioiden havaitseminen ja visualisointi // LNCS: Advances in Databases: Concepts, Systems and Applications. - 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. Nopea parametriton tiheyteen perustuva klusterointi satunnaisten projektioiden avulla // 22. ACM International Conference on Information and Knowledge Management (CIKM). – ACM, 2013.
Campello RJGB, Davoud Moulavi, Arthur Zimek, Jörg Sander. Hierarkkiset tiheysarviot tietojen klusteroinnista, visualisoinnista ja poikkeamien havaitsemisesta // ACM-tapahtumat tiedon löytämisestä tiedosta. - 2015. - T. 10 , nro 1 . - S. 1-51 . - doi : 10.1145/2733381 .
John A Hartigan klusterointialgoritmit. - John Wiley & Sons, 1975. - (Wiley-sarja todennäköisyyslaskennassa ja matemaattisissa tilastoissa). — ISBN 0-471-35645-X .

Koneoppiminen ja tiedon louhinta
Tehtävät	Luokitteluongelma Oppiminen ilman opettajaa Opettajan avustama oppiminen Taantumisanalyysi AutoML Yhdistyksen säännöt Ominaisuuksien erottaminen Ominaisuuksien koulutus Ranking koulutus Kieliopillinen johtaminen Verkko-oppiminen
Opettajan kanssa oppimista	k-lähimmän naapurin menetelmä Naiivi Bayesin luokitin päätöspuu Tuki vektorikonetta Lineaarinen regressio Logistinen regressio perceptron Mallien kokoonpanot Pussittaminen tehostaa satunnainen metsä Asiaankuuluva vektorimenetelmä
ryhmäanalyysi	k-keinomenetelmä Sumea klusterointimenetelmä Hierarkkinen klusterointi EM-algoritmi KOIVU PARANTAA DBSCAN OPTIIKKA Keskimääräinen siirto
Mittasuhteiden vähentäminen	Tekijäanalyysi Pääkomponenttimenetelmä CCA ICA LDA Ei-negatiivinen matriisin laajennus t-SNE
Rakenteellinen ennustaminen	Graafinen todennäköisyysmalli Bayesin verkko Piilotettu Markovin malli CRF
Anomalian havaitseminen	k-lähimmän naapurin menetelmä Paikallinen päästötaso
Piirrä todennäköisyysmallit	Bayesin verkko Markovin verkko Piilotettu Markovin malli
Neuroverkot	Rajoitettu Boltzmann-kone itseorganisoituva kartta Aktivointitoiminto Sigmoidi softmax Radiaalinen kantafunktio Takaisin lisäysmenetelmä Syväoppiminen Monikerroksinen perceptroni Toistuva neuroverkko pitkä lyhytaikainen muisti Hallittu toistuva esto Konvoluutiohermoverkko U-Net Autoenkooderi
Vahvistusoppiminen	Markovin prosessi Bellmanin yhtälö Ahne algoritmi Q-oppiminen SARSA Aikaero (TD)
Teoria	Vapnik-Chervonenkis teoria Bias-dispersion dilemma Laskennallinen oppimisteoria Empiirinen riskin minimointi Occam oppii PAC-oppiminen Tilastollinen oppimisteoria
Lehdet ja konferenssit	NeurIPS ICML ML JMLR ArXiv:cs.LG