DBSCAN

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 11. joulukuuta 2021 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

Tiheyspohjainen kohinasovellusten spatiaalinen klusterointi ( DBSCAN ) on Maritin Esterin , Hans-Peter Kriegelin, Jörg Sanderin ja Xiaowei Sun vuonna 1996 ehdottama dataklusterointialgoritmi [1] . Tämä on tiheyteen perustuva klusterointialgoritmi - kun annetaan joukon pisteitä jossain tilassa, algoritmi ryhmittelee pisteet, jotka ovat lähellä toisiaan (pisteet, joissa on monia lähinaapureita ) ja merkitsee poikkeaviksi pisteet, jotka ovat yksinäisiä pienitiheyksisille alueilla. (lähin jonka naapurit ovat kaukana). DBSCAN on yksi yleisimmin käytetyistä klusterointialgoritmeista ja se on useimmin mainittu tieteellisessä kirjallisuudessa [2] .

Algoritmi sai vuonna 2014 "time-tested" -palkinnon (palkinto, joka myönnetään teoriassa ja käytännössä merkittävää huomiota saaneille algoritmeille) johtavassa tiedonlouhintakonferenssissa KDD [3] .

Varhaiset versiot

Vuonna 1972 Robert F. Ling oli jo julkaissut artikkelin The Theory and Construction of k-Clusters [4] The Computer Journalissa , jossa oli samanlainen algoritmi laskennallisen monimutkaisuuden arvioinnilla [4] . DBSCAN on pahimman tapauksen monimutkaisuus ja sanamuoto DBSCAN tietokantasuuntautuneilla aluekyselyillä $O(n^{3})$ $O(n^{2})$ [ Clear ] mahdollistaa nopeuttamisen indeksillä. Algoritmit eroavat toisistaan reunapisteiden käsittelyssä.

Valmistelu

Harkitse pistejoukkoa jossain tilassa, joka vaatii klusterointia. DBSCAN-klusteroinnin suorittamiseksi pisteet jaetaan ydinpisteisiin, jotka ovat saavutettavissa pistetiheydellä , ja poikkeaviin arvoihin seuraavasti:

Piste p on pääpiste, jos vähintään minPts pisteitä on etäisyydellä, joka ei ylitä ( on suurin naapurusäde p : stä) (mukaan lukien itse piste p ). Näiden pisteiden sanotaan olevan saavutettavissa suoraan p: stä . $\epsilon$ $\epsilon$
Piste q on saavutettavissa suoraan p :stä, jos q on enintään p:n etäisyydellä p :stä ja p on oltava kantapiste. $\epsilon$
Piste A q on saavutettavissa p :stä, jos on polku , jossa on ja , josta kaikkiin pisteisiin pääsee suoraan (kaikkien polun pisteiden on oltava ensisijaisia paitsi q ). ${\displaystyle p_{1},\dots ,p_{n))$ $p_{1}=p$ $p_{n}=q$ $p_{{i+1}}$ $p_{i}$
Kaikki kohdat, joita ei saavuteta ydinpisteistä, katsotaan poikkeaviksi .

Nyt, jos p on ydinpiste, se muodostaa klusterin kaikkien siitä pisteestä saavutettavien pisteiden (ydin tai ei-ydin) kanssa. Jokainen klusteri sisältää vähintään yhden pääkohdan. Ei-olennaiset pisteet voivat olla osa klusteria, mutta ne muodostavat sen "reunan", koska niitä ei voida käyttää muiden pisteiden saavuttamiseen.

Saavutettavuus ei ole symmetrinen suhde, koska määritelmän mukaan ei-ydinpisteestä ei päästä mihinkään pisteeseen etäisyydestä riippumatta (siis ei-ydinpisteeseen voi päästä, mutta siitä ei päästä mihinkään). Siksi liitettävyyden lisäkäsite on välttämätön DBSCAN-algoritmin löytämän klusterialueen muodollisessa määrittelyssä. Kaksi pistettä p ja q liittyvät tiheyteen , jos on sellainen piste o , että sekä p että q ovat saavutettavissa pisteestä o . Tiheysyhteys on symmetrinen.

Sitten klusteri täyttää kaksi ominaisuutta:

Kaikki klusterin pisteet ovat pareittain toisiinsa tiheydeltään.
Jos pisteen tiheys on saavutettavissa jostain pisteestä klusterissa, se kuuluu myös klusteriin.

Algoritmi

Alkuperäinen kyselypohjainen algoritmi

DBSCAN vaatii kahden parametrin määrittämisen: ja pisteiden vähimmäismäärän, joiden tulee muodostaa tiheä alue [5] (minPts). Algoritmi alkaa mielivaltaisesta pisteestä, jota ei ole vielä katsottu. Pisteelle valitaan -naapuri ja jos siinä on tarpeeksi pisteitä, muodostetaan klusteri, muuten piste merkitään kohinaksi. Huomaa, että tämä piste voidaan myöhemmin löytää toisen pisteen -naapurustosta ja sisällyttää johonkin klusteriin. $\epsilon$ $\epsilon$ $\epsilon$

Jos piste löytyy klusterin tiheäksi pisteeksi, myös sen -naapuri on osa tätä klusteria. Siksi kaikki tämän pisteen -naapurustosta löydetyt pisteet lisätään klusteriin. Tämä prosessi jatkuu, kunnes tiheyteen yhdistetty klusteri löytyy. Sitten valitaan ja käsitellään uusi vierailematon piste, mikä johtaa seuraavan klusterin tai kohinan löytämiseen. $\epsilon$ $\epsilon$

DBSCAN:ia voidaan käyttää minkä tahansa etäisyysfunktion [1] [6] (sekä samankaltaisuusfunktion tai loogisen ehdon) kanssa [7] . Etäisyysfunktiota (dist) voidaan siksi pitää lisäparametrina.

Algoritmi voidaan kirjoittaa pseudokoodilla seuraavasti [6] :

DBSCAN(DB, distFunc, eps, minPts) { C=0 /* Cluster count */ jokaiselle pisteelle P tietokannassa DB { if label(P) ≠ määrittelemätön sitten jatka /* Piste etsittiin sisäsilmukasta */ Naapurit N=RangeQuery(DB, distFunc, P, eps) / * Etsi naapureita */ if |N|< minPts then { /* Tiheystarkistus */ label(P)=Noise /* Merkitse kohinaksi */ jatka } C=C + 1 /* seuraava klusterin otsikko */ etiketti(P)=C /* Tunnisteen aloituspiste */ Siemenjoukko S=N \ {P} /* Laajennettavat naapurit */ jokaiselle pisteelle Q S { /* Käsittele jokainen siemenpiste */ jos etiketti(Q)=kohina , sitten etiketti(Q)=C /* Muuta otsikko Kohina reunaksi */ jos etiketti(Q) ≠ määrittelemätön niin jatka /* On katsottu */ etiketti(Q)= C /* Merkitse naapuri */ Naapurit N=RangeQuery(DB, distFunc, Q, eps) /* Etsi naapureita */ jos |N|≥ minPts sitten { /* Tarkista tiheys */ S=S ∪ N /* Lisää naapureita aseta alkeellisia kohtia */ } } } }

jossa RangeQuery voidaan toteuttaa käyttämällä tietokantaindeksiä suorituskyvyn parantamiseksi tai lineaarista hidasta hakua voidaan käyttää:

RangeQuery(DB, distFunc, Q, ) {

\epsilon

Naapurit = tyhjä lista jokaiselle pisteelle P tietokannassa DB { /* Tarkista kaikki tietokannan pisteet */ if then { /* Laske etäisyys ja tarkista epsilon */ Naapurit=Naapurit ∪ {P} /* Lisää tulokseen */

distFunc(Q,P)\leqslant \epsilon

} } palauta naapurit }

Abstrakti algoritmi

DBSCAN-algoritmi voidaan jakaa seuraaviin vaiheisiin [6] :

Etsimme pisteet jokaisen pisteen läheisyydestä ja valitsemme pääpisteet, joissa on enemmän kuin minPts naapureita. $\epsilon$
Löydämme pääpisteiden yhdistetyt komponentit naapurikaaviosta jättäen huomioimatta kaikki ei-peruspisteet.
Määritä jokainen ei-ensisijainen lähin klusteri, jos klusteri on -naapuri, muussa tapauksessa pidä pistettä kohinana. $\epsilon$

Algoritmin naiivi toteutus vaatii naapurien muistamista vaiheessa 1, joten se vaatii huomattavaa muistia. Alkuperäinen DBSCAN-algoritmi ei vaadi tätä tekemällä nämä vaiheet piste kerrallaan.

Vaikeus

DBSCAN vierailee jokaisessa tietokantapisteessä, ehkä useita kertoja (esimerkiksi ehdokkaina muihin klustereihin). Käyttökokemuksen perusteella aika monimutkaisuus määräytyy kuitenkin pääasiassa regionQuery-kyselyiden määrän perusteella. DBSCAN suorittaa täsmälleen yhden tällaisen kyselyn jokaiselle pisteelle, ja jos käytetään indeksirakennetta, joka suorittaa -naapurustokyselyn O(log n ) -ajassa, kokonaiskeskimääräinen aikamonimutkaisuus on O( n log n ) (jos parametri on valittu järkevästi, niin se on sellainen, että vain O(log n ) pistettä palautetaan keskimäärin). Ilman kiihtyvän indeksirakenteen käyttöä tai degeneroituneessa datassa (esimerkiksi kun kaikki pisteet ovat pienempiä kuin ), pahimman tapauksen ajoaika säilyy . Koon etäisyysmatriisi voidaan laskea etäisyyksien uudelleenlaskemisen välttämiseksi, mutta tämä vaatii muistia , kun taas DBSCAN-toteutus ilman etäisyysmatriisia vaatii vain O( n ) muistia. $\epsilon$ $\epsilon$ $O(n^{2})$ $(n^{2}-n)/2$ $O(n^{2})$

Edut

DBSCAN ei edellytä datassa olevien klusterien määrän määrittämistä etukäteen , toisin kuin k-means- menetelmässä .
DBSCAN voi löytää mielivaltaisen muotoisia klustereita. Se voi jopa löytää klustereita, jotka ovat täysin muiden klustereiden ympäröimiä (mutta ei niihin kytkettyjä). MinPts-parametrin ansiosta yhden yhteyden ns. vaikutus (erilaisten klustereiden yhdistäminen ohuella pisteviivalla) vähenee.
DBSCANilla on käsitys kohinasta ja se sietää poikkeavuuksia .
DBSCAN vaatii vain kaksi parametria ja on enimmäkseen epäherkkä tietokannan pisteiden järjestykselle . (Kahden eri klusterin rajalla olevat pisteet voivat kuitenkin päätyä toiseen klusteriin, jos pisteiden järjestystä muutetaan, ja klusterien osoitus on yksilöllinen isomorfismiin asti.)
DBSCAN on suunniteltu käytettäväksi tietokantojen kanssa, jotka voivat nopeuttaa kyselyitä useilla arvoilla, kuten R*-puulla .
MinPt:t ja parametrit voivat asettaa alan asiantuntijat, jos tiedot ymmärretään hyvin. $\epsilon$

Haitat

DBSCAN ei ole täysin yksiselitteinen - reunapisteet, jotka voidaan saavuttaa useammasta kuin yhdestä klusterista, voivat kuulua mihin tahansa näistä klustereista riippuen siitä, missä järjestyksessä pisteitä tarkastellaan. Useimmissa tietojoukoissa näitä tilanteita esiintyy harvoin ja niillä on vain vähän vaikutusta klusteroinnin tulokseen [6] - DBSCAN käsittelee pääkohdat ja kohinan yksilöllisesti. DBSCAN* [8] on variantti, joka käsittelee reunapisteitä kohinana ja saavuttaa siten täysin yksiselitteisen tuloksen sekä yhtenäisemmän tilastollisen tulkinnan tiheysliittyneistä komponenteista.
DBSCANin laatu riippuu regionQuery(P,ε)-funktiossa käytetystä etäisyysmittauksesta . Yleisimmin käytetty etäisyysmittari on euklidinen metriikka . Tämä mittari voi olla lähes hyödytön erityisesti korkeaulotteisen datan klusteroinnissa ns. "ulottuvuuden kirouksen" vuoksi, mikä vaikeuttaa sopivan arvon löytämistä . Tämä vaikutus on kuitenkin läsnä kaikissa muissa euklidiseen etäisyyteen perustuvissa algoritmeissa. $\epsilon$
DBSCAN ei voi hyvin klusteroida tietojoukkoja, joissa on suuria tiheyseroja, koska se ei voi valita yhdistelmää, joka on hyväksyttävä kaikille klustereille [9] . $minPts-\epsilon$
Jos tietoja ja mittakaavaa ei ymmärretä hyvin, merkityksellisen etäisyyskynnyksen valitseminen voi olla vaikeaa. $\epsilon$

Katso alla olevasta osiosta laajennuksista näitä ongelmia käsitteleviä algoritmisia muutoksia.

Parametriarvio

Kaikissa tiedonlouhintatehtävissä on parametriongelma. Jokaisella parametrilla on erityinen vaikutus algoritmiin. DBSCAN-algoritmi tarvitsee parametrit ja minPts . Käyttäjän on määritettävä parametrit. Ihannetapauksessa arvon määrittää ratkaistava ongelma (esim. fyysiset etäisyydet), ja minPts määrittää sitten halutun pienimmän klusterin koon [5] . $\epsilon$ $\epsilon$

MinPts : Kuten kokemus osoittaa, minPts:n vähimmäisarvo voidaan saada tietojoukon D -ulottuvuudesta muodossa . Pieni arvo minPts =1 ei ole järkevää, koska silloin mikä tahansa piste on klusteri. Sillä tulos on sama kuin hierarkkinen klusterointi , jossa on yksi yhteysmetriikka ja dendrogrammin karsiminen korkeudessa . Siksi minPts :n tulisi olla vähintään 3. Kuitenkin kohinaisilla tietojoukoilla suuremmat arvot ovat yleensä parempia ja tuottavat merkittävämpiä klustereita. Kokemus viittaa siihen, että arvoa [7] voidaan käyttää , mutta voi olla tarpeen valita suurempi arvo suurille tietojoukoille, kohinaisille tiedoille tai tiedoille, jotka sisältävät useita kaksoiskappaleita [6] . $minPts\geqslant D+1$ $minPts\leqslant 2$ $\epsilon$ $minPts=2\cdot dim$
$\epsilon$ : Arvo voidaan valita k-etäisyyden kuvaajalla , piirtämällä etäisyys ( ) lähimpään naapuriin järjestyksessä suurimmasta pienimpään [6] . Hyviä arvoja ovat ne, joissa kaaviossa on "taivutus" [1] [7] [6] - jos se valitaan liian pieneksi, suurin osa tiedoista ei klusteroidu, ja liian suurilla arvoilla klusterit yhdistyvät ja useimmat kohteista on samassa klusterissa. Yleensä pienet arvot ovat suositeltavia [6] ja kokemus osoittaa, että vain pienen osan pisteistä tulisi olla tällä etäisyydellä toisistaan. Vaihtoehtoisesti voidaan valita [6] OPTICS -kaaviolla, mutta tällöin voidaan käyttää itse OPTICS-algoritmia klusterointiin. $\epsilon$ $k=minPts-1$ $\epsilon$ $\epsilon$ $\epsilon$ $\epsilon$ $\epsilon$
Etäisyysfunktio: Etäisyysfunktion valinta liittyy vahvasti valintaan ja sillä on suuri vaikutus tuloksiin. Yleensä on ensin määritettävä kohtuulliset mittaukset tietojoukon samankaltaisuudesta ennen kuin valitset . Tälle parametrille ei ole arvioita, mutta etäisyysfunktiot tulee valita tietojoukon mukaan. Esimerkiksi maantieteellisille tiedoille suuri ympyräetäisyys on usein hyvä valinta. $\epsilon$ $\epsilon$

OPTICS voidaan ajatella DBSCANin yleistyksenä, jossa parametri korvataan maksimiarvolla, jolla on eniten vaikutusta suorituskykyyn. MinPtsistä tulee sitten klusterin vähimmäiskoko. Vaikka algoritmi on oleellisesti yksinkertaisempi parametrien valintaalueella kuin DBSCAN, sen tuloksia on vaikeampi käyttää, koska se yleensä tuottaa hierarkkista klusterointia DBSCANin tuottaman yksinkertaisen osioinnin sijaan. $\epsilon$

Äskettäin yksi DBSCANin kirjoittajista muutti DBSCANia ja OPTICSia ja julkaisi tarkistetun version hierarkkisesta DBSCANista (HDBSCAN*) [8] , jossa ei enää ole reunapisteiden käsitettä. Vain pääkohdat muodostavat klusterin.

Laajennukset

Yleistetty DBSCAN (GDBSCAN) [7] [10] on samojen tekijöiden yleistys mielivaltaisille loogisille lausekkeille "naapuruus" ja "tiheys". Parametrit ja minPts poistetaan algoritmista ja siirretään loogisiin ehtoihin. Esimerkiksi monikulmioiden tiedoissa "naapuruus" voi olla mikä tahansa monikulmioiden leikkauspiste, kun taas tiheysehto käyttää aluetta piirteiden määrän sijaan. $\epsilon$

DBSCAN-algoritmille on ehdotettu erilaisia laajennuksia, mukaan lukien menetelmät rinnakkaisuun, parametrien estimointi ja kyseenalaisten tietojen tuki. Perusidea on laajennettu hierarkkiseen klusterointiin OPTICS -algoritmin avulla . DBSCAN-algoritmia on käytetty myös osana aliavaruusklusterointialgoritmeja, kuten PreDeCon ja SUBCLU . HDBSCAN [8] on hierarkkinen versio DBSCANista, joka on myös nopeampi kuin OPTICS ja jossa hierarkiasta voidaan poimia litteä osio, joka koostuu näkyvimmistä klustereista [11] .

Saatavuus

Algoritmin eri toteutuksia löydettiin valtavalla suorituskyvyllä, nopein suoritti testidatan työskentelyn 1,4 sekunnissa ja hitain 13 803 sekunnissa [12] . Ero johtuu toteutuksen laadusta, eroista kielissä ja kääntäjissä sekä indeksien käytöstä asioiden nopeuttamiseksi.

Apache Commons Math sisältää Java -toteutuksen algoritmista, joka suoritetaan neliössä.
ELKI tarjoaa DBSCAN-, GDBSCAN- ja muiden vaihtoehtojen toteutuksen. Tämä toteutus voi käyttää erilaisia indeksirakenteita subquadratic runtimeen tarjoamiseksi. Tässä toteutuksessa voidaan käyttää mielivaltaisia etäisyysfunktioita ja mielivaltaisia tietotyyppejä , ja kiihdytystä voidaan saavuttaa matalan tason optimoinnilla ja erityismenetelmillä pienissä tietokokonaisuuksissa.
PostGIS sisältää ST_ClusterDBSCANin, kaksiulotteisen DBSCAN-toteutuksen, joka käyttää R-puuta indeksinä. Mitä tahansa geometriatyyppiä tuetaan, kuten piste, viiva, monikulmio jne.
R - kielellä fpc - paketti sisältää DBSCANin, joka tukee mielivaltaista etäisyysfunktiota etäisyysmatriisien kautta. Toteutus ei kuitenkaan tue indeksejä (ja siksi sillä on neliöllinen ajoaika ja aika monimutkaisuus), ja on sanottava, että toteutus on hidasta johtuen R-tulkin käytöstä. Nopeampi C ++ -toteutus kd-puita käyttäen (vain euklidisille etäisyyksille) on R-paketissa dbscan .
scikit-learn sisältää DBSCANin Python -toteutuksenmielivaltaisille Minkowski-metriikalle , jota voidaan nopeuttaa kd-puilla ja pallopuilla , mutta joka käyttää pahimmassa tapauksessa neliömuistia. Scikit-learnin lisäosapaketti tarjoaa HDBSCAN*-algoritmin toteutuksen.
Pyklosterointikirjasto sisältää Python- ja C++-toteutuksen DBSCANista vain euklidiselle etäisyydelle sekä OPTICS-algoritmin toteutuksen.
SPMF sisältää DBSCAN-algoritmin toteutuksen kd-puutuella vain euklidiselle etäisyydelle.
Weka sisältää (valinnaisena pakettina uusimmassa versiossa) DBSCAN-perustoteutuksen, joka vaatii lineaarista muistia ja toimii kvadraattisessa ajassa.

Muistiinpanot

↑ 1 2 3 Ester, Kriegel, Sander, Xu, 1996 , s. 226–231.
↑ Microsoft Academic Search, 2010 .
↑ Test of Time -palkinto, 2014 .
↑ 12 Ling , 1972 , s. 326-332.
↑ 1 2 Vaikka minPts on intuitiivisesti pienin klusterin koko, joissain tapauksissa DBSCAN voi tuottaa pienempiä klustereita ( Schubert, Sander, Ester, Kriegel, Xu 2017 ). DBSCAN-klusteri koostuu vähintään yhdestä ydinpisteestä . Koska muut pisteet voivat olla useamman kuin yhden klusterin reunapisteitä, ei ole takeita siitä, että jokaiseen klusteriin sisältyy vähintään minPts pisteitä.
↑ 1 2 3 4 5 6 7 8 9 Schubert, Sander, Ester, Kriegel, Xu, 2017 , s. 19:1–19:21.
↑ 1 2 3 4 Sander, Ester, Kriegel, Xu, 1998 , s. 169-194.
↑ 1 2 3 Campello, Moulavi, Zimek, Sander, 2015 , s. 1–51.
↑ Kriegel, Kröger, Sander, Zimek, 2011 , s. 231-240.
↑ Sander, 1998 .
↑ Campello, Moulavi, Zimek, Sander, 2013 , s. 344.
↑ Kriegel, Schubert, Zimek, 2016 , s. 341.

Kirjallisuus

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 .
Jörg Sander, Martin Ester, Hans-Peter Kriegel, Xiaowei Xu. Tiheyspohjainen klusterointi paikkatietokantoissa: Algoritmi GDBSCAN ja sen sovellukset // Tiedonlouhinta ja tiedonhaku. - Berlin: Springer-Verlag , 1998. - Vol. 2 , no. 2 . - S. 169-194 . - doi : 10.1023/A:1009745219419 .

Microsoft Academic Search . - 2010. Arkistoitu 21. huhtikuuta 2010. Microsoftin akateemisen haun siteeratut tiedon louhintaartikkelit; DBSCANissa on 24 asemaa.
2014 SIGKDD Test of Time -palkinto . – ACM SIGKDD, 2014.
Ling RF K-klusterien teoriasta ja rakentamisesta // The Computer Journal. - 1972. - T. 15 , no. 4 . — ISSN 0010-4620 . - doi : 10.1093/comjnl/15.4.326 .
Erich Schubert, Jörg Sander, Martin Ester, Hans Peter Kriegel, Xiaowei Xu. DBSCAN Revisited, Revisited: Miksi ja miten sinun pitäisi (vielä) käyttää DBSCANia // ACM Trans. Database Syst.. - 2017. - Heinäkuu ( osa 42 , numero 3 ). — ISSN 0362-5915 . - doi : 10.1145/3068335 .
Hans-Peter Kriegel, Peer Kröger, Jörg Sander, Arthur Zimek. Tiheyspohjainen klusterointi // WIREs Data Mining and Knowledge Discovery. - 2011. - Osa 1 , numero. 3 . — S. 231–240 . - doi : 10.1002/leveys.30 .
Ricardo JGB Campello, 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 . — ISSN 1556-4681 . - doi : 10.1145/2733381 .
George Sander. Yleistetty tiheyteen perustuva klusterointi paikkatiedon louhintaan. - Herbert Utz Verlag, 1998. - ISBN 3-89675-469-6 .
Campello RJGB, Moulavi D., Zimek A., Sander J. Puoliksi valvotun ja valvomattoman optimaalisen klustereiden poimimisen puitteet hierarkioista // Data Mining and Knowledge Discovery. - 2013. - T. 27 , nro 3 . - doi : 10.1007/s10618-013-0311-4 .
Hans-Peter Kriegel, Erich Schubert, Arthur Zimek. Ajonaikaisen arvioinnin (musta) taide: Vertaillaanko algoritmeja vai toteutuksia? // Tieto ja tietojärjestelmät. - 2016. - T. 52 , no. 2 . - S. 341 . — ISSN 0219-1377 . - doi : 10.1007/s10115-016-1004-2 .

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