Kuinka koneet tuntevat suuria tietoja: johdanto klusterointialgoritmeihin

Katso alla olevaa kuvaa. Se on kokoelma erikokoisia vikoja ja kammottavia ryömiä. Vie hetki luokitellaksesi ne samankaltaisuuden perusteella useisiin ryhmiin.

Tämä ei ole temppukysymys. Aloita hämähäkkien ryhmittely.

Google-kuvahaun kautta kuvat, jotka on merkitty uudelleenkäyttöön

Tehty? Vaikka tässä ei välttämättä ole ”oikeaa” vastausta, on todennäköistä, että jaat virheet neljään klusteriin. Hämähäkkejä yhdessä klusterissa, pari etanaa toisessa, perhoset ja koi yhdeksi ja ampiaisten ja mehiläisten kolmio yhdeksi.

Se ei ollut huono, eikö totta? Voisit todennäköisesti tehdä saman kaksinkertaisen määrän virheiden kanssa, eikö niin? Jos sinulla olisi vähän aikaa säästää - tai intohimo entomologiaan -, voisit todennäköisesti tehdä samoin sadan virheen avulla.

Koneelle kymmenen esineen ryhmittäminen kuitenkin lukuisiksi merkityksellisiksi klusteriksi ei kuitenkaan ole pieni tehtävä kiitos yhdistelmätekniikan kutsuman matematiikan haaran, joka kertoo meille, että 115 975 erilaista mahdollista tapaa, joilla olet voinut ryhmitellä nämä kymmenen hyönteistä yhteen. Jos vikoja olisi ollut kaksikymmentä, olisi ollut yli viisikymmentä biljoonaa mahdollista tapaa ryhmitellä ne.

Sata virhettä - ratkaisuja olisi monta kertaa enemmän kuin tunnetussa maailmankaikkeudessa on hiukkasia. Kuinka monta kertaa enemmän? Laskelmani mukaan noin viisisataa miljoonaa miljardia miljardia kertaa enemmän. Itse asiassa googol-ratkaisuja on yli neljä miljoonaa miljardia (mikä on googol?). Vain sata kohdetta.

Lähes kaikki näistä ratkaisuista olisivat merkityksettömiä - silti siitä kuvittelemattomasta joukosta mahdollisia valintoja, löysit melko nopeasti yhden harvoista, jotka rypälsivät virheet hyödyllisellä tavalla.

Me ihmiset, pidämme itsestäänselvyytenä sitä, kuinka hyvämme luokittelemme ja ymmärrämme suuret tietomäärät melko nopeasti. Olipa kyse tekstin kappaleesta, kuvista näytöllä tai esineiden sarjasta - ihmiset ovat yleensä melko tehokkaita ymmärtämään mitä tahansa tietoa maailma heittää meille.

Koska keskeinen näkökohta A.I. ja Koneoppiminen saa koneet nopeasti ymmärtämään suuret syöttötiedot, mitkä oikotiet ovat käytettävissä? Täältä voit lukea kolmesta klusterointialgoritmista, joita koneet voivat käyttää suurten tietojoukkojen ymmärtämiseen nopeasti. Tämä ei ole mitenkään tyhjentävä luettelo - siellä on muita algoritmeja -, mutta ne edustavat hyvää aloituspaikkaa!

Löydät jokaiselle nopean yhteenvedon siitä, milloin voit käyttää niitä, lyhyen yleiskatsauksen niiden toiminnasta ja yksityiskohtaisemman, vaihe vaiheelta toimivan esimerkin. Uskon, että se auttaa ymmärtämään algoritmia suorittamalla itse itsesi. Jos olet todella kiinnostunut, löydät parhaan tavan tehdä tämä kynällä ja paperilla. Mene eteenpäin - kukaan ei tuomitse!

Kolme epäilyttävän siistiä klusteria, joiden K = 3

K-tarkoittaa klusterointia

Käytä kun:

… Sinulla on käsitys siitä, kuinka monta ryhmää odotat löytäväsi ennakolta.

Kuinka se toimii:

Algoritmi osoittaa satunnaisesti jokaisen havainnon yhteen k-luokasta, laskee sitten kunkin luokan keskiarvon. Seuraavaksi se osoittaa jokaisen havainnon luokkaan lähimmän keskiarvon kanssa ennen keskiarvon laskemista. Tämä vaihe toistuu yhä uudelleen, kunnes uusia määrityksiä ei tarvita.

Toiminut esimerkki:

Ota ryhmä 12 jalkapallopelaajaa (tai 'jalkapallo') pelaajaa, jotka ovat jokaiset tehneet tietyn määrän maalia tällä kaudella (sanoen välillä 3–30). Jaetaan ne erillisiin klustereihin - sanotaan kolme.

Vaihe 1 vaatii meitä jakamaan pelaajat satunnaisesti kolmeen ryhmään ja laskemaan kunkin keskiarvot.

Ryhmä 1
Pelaaja A (5 maalia), pelaaja B (20 maalia), pelaaja C (11 maalia)
Ryhmän keskiarvo = (5 + 20 + 11) / 3 = 12
Ryhmä 2
Pelaaja D (5 maalia), pelaaja E (3 maalia), pelaaja F (19 maalia)
Ryhmän keskiarvo = 9
Ryhmä 3
Pelaaja G (30 maalia), pelaaja H (3 maalia), pelaaja I (15 maalia)
Ryhmän keskiarvo = 16

Vaihe 2: Määritä jokaiselle pelaajalle ryhmä, jolla on lähin keskiarvo. Esimerkiksi pelaaja A (5 maalia) on osoitettu ryhmälle 2 (keskiarvo = 9). Laske sitten ryhmäkeinot uudelleen.

Ryhmä 1 (vanha keskiarvo = 12)
Pelaaja C (11 maalia)
Uusi keskiarvo = 11
Ryhmä 2 (vanha keskiarvo = 9)
Pelaaja A (5 maalia), pelaaja D (5 maalia), pelaaja E (3 maalia), pelaaja H (3 maalia)
Uusi keskiarvo = 4
Ryhmä 3 (vanha keskiarvo = 16)
Pelaaja G (30 maalia), pelaaja I (15 maalia), pelaaja B (20 maalia), pelaaja F (19 maalia)
Uusi keskiarvo = 21

Toista vaihe 2 uudelleen ja uudelleen, kunnes ryhmä ei enää muutu. Tätä hieman keinotekoista esimerkkiä varten tämä tapahtuu seuraavassa iteraatiossa. Stop! Olet nyt muodostanut kolme klusteria tietoaineistosta!

Ryhmä 1 (vanha keskiarvo = 11)
Pelaaja C (11 maalia), pelaaja I (15 maalia)
Lopullinen keskiarvo = 13
Ryhmä 2 (vanha keskiarvo = 4)
Pelaaja A (5 maalia), pelaaja D (5 maalia), pelaaja E (3 maalia), pelaaja H (3 maalia)
Lopullinen keskiarvo = 4
Ryhmä 3 (vanha keskiarvo = 21)
Pelaaja G (30 maalia), pelaaja B (20 maalia), pelaaja F (19 maalia)
Lopullinen keskiarvo = 23

Tässä esimerkissä klusterit voisivat vastata pelaajien paikkoja kentällä - kuten puolustajat, keskikenttäpelaajat ja hyökkääjät. K-keinot toimivat täällä, koska voimme kohtuudella olettaa, että tiedot jakautuvat luonnollisesti näihin kolmeen luokkaan.

Tällä tavalla, ottaen huomioon tiedot erilaisista suorituskykytilastoista, kone voisi tehdä kohtuullisen työn estääkseen pelaajien asemat mistä tahansa joukkueurheilulajista - hyödyllinen urheilun analysoinnissa ja todellakin mihin tahansa muuhun tarkoitukseen, jossa tietojoukon luokittelu ennalta määritettyihin ryhmiin voi tarjota asiaankuuluvia tietoja.

Tarkempia tietoja:

Tässä kuvatussa algoritmissa on useita muunnelmia. Alkuperäinen klusterien siemennysmenetelmä voidaan tehdä yhdellä monista tavoista. Täällä määrittelimme jokaisen pelaajan satunnaisesti ryhmään, sitten laskettiin ryhmän keskiarvot. Tämä saa aikaan, että alkuperäisillä ryhmäkeinoilla on taipumus olla samankaltaisia ​​toistensa kanssa, mikä varmistaa suuremman toistettavuuden.

Vaihtoehto on siemenet klusterissa, joissa kussakin on vain yksi pelaaja, ja aloita sitten pelaajien osoittaminen lähimpään klusteriin. Palautetut klusterit ovat herkempiä alkuperäiselle kylvövaiheelle vähentäen toistettavuutta erittäin muuttuvissa tietojoukoissa. Tämä lähestymistapa voi kuitenkin vähentää algoritmin suorittamiseen tarvittavien iteraatioiden lukumäärää, koska ryhmien eroaminen vie vähemmän aikaa.

Ilmeinen rajoitus K-tarkoittaa klusterointia on, että sinun on annettava etukäteen oletuksia siitä, kuinka monta klusteria olet odottanut löytäväsi. Tietyn klustereiden sopivuuden arvioimiseksi on olemassa menetelmiä. Esimerkiksi klusterin sisäinen neliösumma on kunkin klusterin varianssin mitta. Mitä parempia klusterit ovat, sitä matalampi WCSS on.

Hierarkkinen klusterointi

Käytä kun:

… Haluat selvittää havaintojenne taustalla olevat suhteet.

Kuinka se toimii:

Etäisyysmatriisi lasketaan, missä solun (i, j) arvo on etäisyysmetriikka havaintojen i ja j välillä. Yhdistä sitten kaksi lähintä havaintoa ja laske niiden keskiarvo. Muodosta uusi etäisyysmatriisi yhdistämällä parilliset havainnot yhdeksi esineeksi. Parikaa tästä etäisyysmatriisista kaksi lähintä havaintoa ja laske niiden keskiarvo. Toista, kunnes kaikki havainnot on ryhmitelty yhteen.

Toiminut esimerkki:

Tässä on yksinkertaistettu aineisto valikoimasta valaiden ja delfiinien lajeja. Koulutetut biologit voin vakuuttaa teille, että käytämme yleensä paljon yksityiskohtaisempia tietoaineistoja esimerkiksi fylogenian uudelleenrakentamiseen. Toistaiseksi kuitenkin tarkastellaan vain näiden kuuden lajin tyypillisiä kehonpituuksia. Käytämme vain kahta toistettua vaihetta.

Laji Initials Pituus (m)
Pulloseosta Dolphin BD 3.0
Risso's Dolphin RD 3.6
Pilot Whale PW 6.5
Killer Whale KW 7.5
Ryhmävalas HW 15.0
Fin Whale FW 20.0

Vaihe 1: laske etäisyysmatriisi kunkin lajin välillä. Käytämme tässä euklidista etäisyyttä - kuinka kaukana toisistaan ​​ovat datapisteet? Lue tämä täsmälleen samalla tavalla kuin etäisyyskaavio tien atlasasta. Minkä tahansa lajeparin välinen pituusero voidaan tarkistaa lukemalla arvo kyseisen rivin ja sarakkeen leikkauspisteessä.

    BD RD PW KW HW
RD 0,6
PW 3,5 2,9
KW 4,5 3,9 1,0
HW 12,0 11,4 8,5 7,5
FW 17,0 16,4 13,5 12,5 5,0

Vaihe 2: Paritellaan kaksi lähintä lajia. Täältä tulee Bottlenose & Risso's Dolphins, joiden keskipituus on 3,3 metriä.

Toista vaihe 1 laskemalla etäisyysmatriisi uudelleen, mutta yhdistä tällä kertaa Bottlenose & Risso-delfiinit yhdeksi esineeksi, jonka pituus on 3,3 metriä.

    [BD, RD] PW KW HW
PW 3.2
KW 4,2 1,0
HW 11,7 8,5 7,5
FW 16,7 13,5 12,5 5,0

Toista seuraavaksi vaihe 2 tällä uudella etäisyysmatriisilla. Täällä pienin etäisyys on lentäjä- ja tappajavalaiden välillä, joten parillamme ne ja otamme keskiarvonsa - mikä antaa meille 7,0m.

Sitten toistamme vaiheen 1 - laske etäisyysmatriisi uudelleen, mutta nyt olemme yhdistäneet pilotti- ja tappajavalat yhdeksi 7,0 metrin pituiseksi esineeksi.

         [BD, RD] [PW, KW] HW
[PW, KW] 3.7
HW 11,7 8,0
FW 16,7 13,0 5,0

Seuraavaksi toistamme vaihe 2 tällä etäisyysmatriisilla. Pienin etäisyys (3,7 m) on kahden sulautuneen objektin välillä - joten nyt yhdistämme ne vielä suuremmaksi esineeksi ja otamme keskiarvon (joka on 5,2 m).

Sitten toistamme vaiheen 1 ja lasketaan uusi etäisyysmatriisi yhdistämällä Pullonaiset & Risso-delfiinit Pilot & Killer -valaisiin.

   [[BD, RD], [PW, KW]] HW
HW 9,8
FW 14,8 5,0

Seuraavaksi toistamme vaiheen 2. Pienin etäisyys (5,0 m) on ryppy- ja sorkkavalaiden välillä, joten yhdistämme ne yhdeksi esineeksi ja otamme keskiarvon (17,5m).

Sitten se on palannut vaiheeseen 1 - laske etäisyysmatriisi yhdistämällä Rypytys- ja sorkkavalat.

         [[BD, RD], [PW, KW]]
[HW, FW] 12.3

Viimeinkin toistamme vaiheen 2 - tässä matriisissa on vain yksi etäisyys (12,3m), joten pariksi kaikki muodostetaan yhdeksi suureksi esineeksi, ja nyt voimme lopettaa! Katsotaanpa lopullista sulautettua kohdetta:

[[[BD, RD], [PW, KW]], [HW, FW]]

Sillä on sisäkkäinen rakenne (ajattele JSON), jonka avulla se voidaan piirtää puumaisena kuvaajana tai dendrogrammina. Se lukee paljon samalla tavalla kuin sukupuu saattaa. Mitä lähempänä kahta havaintoa on puussa, sitä samankaltaisempia tai läheisempää sukua niiden katsotaan olevan.

R-Fiddle.org-sivustossa generoitu huono dendrogrammi

Dendrogrammin rakenne antaa meille käsityksen siitä, kuinka tietojoukkomme on rakennettu. Esimerkissämme näemme kaksi päähaaraa, joissa on Korivalas ja Fin Whale toisella puolella ja pullotettu Dolphin / Risso's Dolphin ja Pilot Whale / Killer Whale toisella.

Evoluutiobiologiassa käytetään tällä tavoin paljon suurempia tietojoukkoja, joissa on paljon enemmän näytteitä ja mittauksia, päätelmään niiden välisistä taksonomisista suhteista. Biologian ulkopuolella hierarkkisella klusteroinnilla on sovelluksia tiedon louhinnan ja koneoppimisten yhteydessä.

Hienoa on, että tämä lähestymistapa ei vaadi oletuksia etsimäsi klusterien lukumäärästä. Voit jakaa palautetun dendrogrammin klustereihin leikkaamalla puun tietylle korkeudelle. Tämä korkeus voidaan valita monin tavoin sen tarkkuuden mukaan, johon haluat ryhmitellä tiedot.

Esimerkiksi, kun tarkastellaan yllä olevaa dendrogrammia, jos piirrämme vaakasuoran viivan korkeudella = 10, leikkaamme kaksi päähaaraa jakamalla dendrogrammin kahteen osakuvaajaan. Jos leikkaamme korkeudella = 2, me jaomme dendrogrammin kolmeen klusteriin.

Tarkempia tietoja:

On olennaisesti kolme näkökohtaa, joissa hierarkkiset klusterointialgoritmit voivat vaihdella tässä annettuun.

Periaatteellisin on lähestymistapa - tässä olemme käyttäneet agglomeratiivista prosessia, jossa aloitamme yksittäisistä datapisteistä ja ryhmittelemme ne toistuvasti toisiinsa, kunnes jäljellä on yksi iso klusteri. Vaihtoehtoinen (mutta laskennallisesti intensiivisempi) lähestymistapa on aloittaa yhdellä jättiläis klusterilla ja jakaa sitten tiedot pienempiin ja pienempiin klustereihin, kunnes sinulla on eristettyjä tietopisteitä.

On myös joukko menetelmiä, joita voidaan käyttää etäisyysmatriisien laskemiseen. Moniin tarkoituksiin euklidinen etäisyys (ajattele Pythagorasin lause) riittää, mutta on vaihtoehtoja, joita voidaan soveltaa tietyissä olosuhteissa.

Lopuksi kytkentäkriteeri voi myös vaihdella. Klusterit yhdistetään sen mukaan, kuinka lähellä ne ovat, mutta tapa, jolla määrittelemme 'sulkemisen', on joustava. Yllä olevassa esimerkissä mittasimme kunkin ryhmän keskiarvojen (tai 'keskipisteiden') väliset etäisyydet ja pariksi muodostettiin lähimmät ryhmät. Voit kuitenkin käyttää eri määritelmää.

Esimerkiksi jokainen klusteri koostuu useista erillisistä pisteistä. Voimme määrittää kahden klusterin välisen etäisyyden pienimmäksi (tai suurimmaksi) etäisyydeksi niiden pisteiden välillä - kuten alla olevassa kuvassa on esitetty. On vielä muita tapoja määritellä kytkentäkriteeri, jotka saattavat olla sopivia eri tilanteissa.

Punainen / sininen: keskittymäyhteys; Punainen / vihreä: minimaalinen kytkentä; Vihreä / sininen: maksimaalinen kytkentä

Graafinen yhteisön tunnistus

Käytä kun:

… Sinulla on tietoja, jotka voidaan edustaa verkkona tai kuvaajana.

Kuinka se toimii:

Graafiyhteisö on hyvin yleisesti määritelty osaksi joukkoa huipuja, jotka ovat enemmän yhteydessä toisiinsa kuin muuhun verkkoon. Erilaisia ​​algoritmeja on olemassa yhteisöjen tunnistamiseksi erityisten määritelmien perusteella. Algoritmeihin kuuluvat, mutta niihin rajoittumatta, Edge Betweenness, Modulaarisuus-Maximisation, Walktrap, Clique Percolation, Johtava Eigenvector…

Toiminut esimerkki:

Graafiteoria tai verkkojen matemaattinen tutkimus on kiehtova matematiikan haara, jonka avulla voimme mallintaa monimutkaisia ​​järjestelmiä abstraktina kokoelmana pisteistä (tai kärkipisteistä), joita yhdistävät viivat (tai reunat).

Ehkä intuitiivisimmat tapaustutkimukset ovat sosiaalisia verkostoja. Täällä vertikaalit edustavat ihmisiä ja reunat yhdistävät kärkiä, jotka ovat ystäviä / seuraajia. Mikä tahansa järjestelmä voidaan kuitenkin mallintaa verkkoksi, jos pystyt perustelemaan menetelmän, jolla yhdistetään tarkoituksenmukaisesti eri komponentit. Graafiteorian innovatiivisempien sovellusten joukkoon klusterointiin sisältyy ominaisuuksien poimiminen kuvatiedoista ja geenisäätelyverkkojen analysointi.

Ennakkotason esimerkki, katso tämä nopeasti koottu kaavio. Se näyttää kahdeksan verkkosivustoa, joissa viimeksi kävin, linkitettynä sen mukaan, linkittävätkö heidän Wikipedia-artikkelinsa toisiinsa. Voit koota nämä tiedot manuaalisesti, mutta laajemmissa projekteissa on paljon nopeampaa kirjoittaa Python-skripti samoin. Tässä on yksi, jonka kirjoitin aiemmin.

Graafi on piirretty igraph-paketilla R-versiolle 3.3.3

Huiput värjäytyvät yhteisöjäsenyytensä mukaan ja koon mukaan keskitetysti. Katso kuinka Google ja Twitter ovat keskeisimmät?

Klusterit tekevät myös varsin hyvää järkeä tosielämässä (aina tärkeä suoritusindikaattori). Keltaiset huiput ovat yleensä viite- / hakupaikkoja; kaikkia sinisiä kärkipisteitä käytetään verkkojulkaisussa (artikkelit, tweetit tai koodi); Punaisiin kärkipisteisiin kuuluu YouTube, jonka tietysti perustivat entiset PayPalin työntekijät. Ei huonoja vähennyksiä koneelle!

Sen lisäksi, että se on hyödyllinen tapa visualisoida suuria järjestelmiä, verkkojen todellinen voima syntyy niiden matemaattisesta analyysistä. Aloitetaan kääntämällä mukava verkkokuvamme matemaattisempaan muotoon. Alla on verkon vieressä oleva matriisi.

         GH Gl M P Q T W Y
GitHub 0 1 0 0 0 1 0 0
Google 1 0 1 1 1 1 1 1
Medium 0 1 0 0 0 1 0 0
PayPal 0 1 0 0 0 1 0 1
Quora 0 1 0 0 0 1 1 0
Twitter 1 1 1 1 1 0 0 1
Wikipedia 0 1 0 0 1 0 0 0
YouTube 0 1 0 1 0 1 0 0

Kunkin rivin ja sarakkeen leikkauspisteessä oleva arvo tallentaa, onko kyseisen kärkiparin välillä reuna. Esimerkiksi Mediumin ja Twitterin välillä on reuna (yllätys, yllätys!), Joten arvo, jossa niiden rivit / sarakkeet leikkaavat, on 1. Vastaavasti Mediumin ja PayPalin välillä ei ole reunaa, joten niiden rivien / sarakkeiden leikkaus palaa 0.

Naapurimatriisiin koodatut ovat kaikki tämän verkon ominaisuudet - se antaa meille avaimen aloittaa kaikenlaisten arvokkaiden oivalluksien avaaminen. Alkua varten minkä tahansa sarakkeen (tai rivin) summaaminen antaa sinulle kunkin kärkipisteen asteen - ts. Kuinka moniin muihin se on kytketty. Tätä merkitään yleensä kirjaimella k.

Samoin summaamalla jokaisen kärkipisteen asteet ja jakamalla kahdella saadaan L, verkon reunojen (tai 'linkkien') lukumäärä. Rivien / sarakkeiden lukumäärä antaa meille N, verkkien (tai 'solmujen') määrän verkossa.

Tietäen vain k, L, N ja kunkin vierekkäisyysmatriisin A solun arvo antaa meille mahdollisuuden laskea minkä tahansa verkon klusteroinnin modulaarisuus.

Oletetaan, että olemme klusteroineet verkon useisiin yhteisöihin. Voimme käyttää modulaarisuuspistettä arvioidakseen tämän klusterin "laatua". Korkeampi pistemäärä osoittaa, että olemme jakanut verkon 'tarkkoihin' yhteisöihin, kun taas alhainen pistemäärä osoittaa, että klusterimme ovat satunnaisempia kuin oivaltavia. Alla oleva kuva kuvaa tätä.

Modulaarisuus toimii osion

Modulaarisuus voidaan laskea alla olevan kaavan avulla:

Se on kohtuullinen määrä matematiikkaa, mutta voimme hajottaa sen vähitellen ja se on järkevämpi.

M on tietysti mitä me laskemme - modulaarisuus.

1 / 2L käskee meitä jakamaan kaiken seuraavan 2L: llä, toisin sanoen kaksinkertaiseksi verkon reunojen lukumääräksi. Toistaiseksi niin hyvä.

Σ-symboli kertoo, että me summaamme kaiken oikealta, ja annamme iteroida jokaisen rivin ja sarakkeen vieressä olevassa matriisissa A. Niille, jotka eivät tunne summan merkintää, i, j = 1 ja N toimivat paljon kuin pesässä. for-silmukat ohjelmoinnissa. Pythonissa kirjoitat sen seuraavasti:

summa = 0
i: lle alueella (1, N):
    j: lle alueella (1, N):
        ans = #kappaletta indekseinä i ja j
        summa + = ans

Joten mitä #kappale on i ja j yksityiskohtaisemmin?

No, suluissa oleva bitti kertoo meidän vähentävän (k_i k_j) / 2L A_ij: stä.

A_ij on yksinkertaisesti rivin i sarakkeen j vieressä olevan matriisin arvo.

K_i: n ja k_j: n arvot ovat kunkin kärkipisteen asteita - löydetään lisäämällä rivin i ja sarakkeen j merkinnät. Kertomalla nämä yhteen ja jakamalla 2L antaa meille odotettavissa olevan reunojen lukumäärän kärkien i ja j välillä, jos verkko satunnaisesti sekoitettiin.

Kaiken kaikkiaan suluissa oleva termi paljastaa verkon todellisen rakenteen ja odotetun rakenteen välisen eron, joka sillä olisi, jos se satunnaisesti kootaan uudelleen. Arvoilla pelaaminen osoittaa, että se palauttaa suurimman arvon, kun A_ij = 1, ja (k_i k_j) / 2L on alhainen. Tämä tarkoittaa sitä, että näemme suuremman arvon, jos kärkien i ja j välillä on 'odottamaton' reuna.

Lopuksi kerrotaan haarukoitu termi millä tahansa viimeisillä symboleilla viitataan.

𝛿c_i, c_j on fancy kuulostava, mutta täysin vaaraton Kronecker-delta-toiminto. Tässä se selitetään Pythonissa:

def Kronecker_Delta (ci, cj):
    jos ci == cj:
        palauta 1
    else:
        palauta 0
Kronecker_Delta ("A", "A") #palaa 1
Kronecker_Delta ("A", "B") #palaa 0

Kyllä - se todella on niin yksinkertaista. Kronecker-delta-funktio ottaa kaksi argumenttia ja palauttaa yhden, jos ne ovat identtisiä, muuten nolla.

Tämä tarkoittaa, että jos huiput i ja j on sijoitettu samaan klusteriin, niin 𝛿c_i, c_j = 1. Muuten, jos ne ovat eri klustereissa, funktio palauttaa nollan.

Kun me kerromme hakasulkemaa tällä Kronecker-delta -funktiolla, havaitsemme, että sisäkkäisellä summalla the lopputulos on suurin, kun samaan klusteriin on osoitettu paljon 'odottamattomia' reunoja, jotka yhdistävät kärkipisteitä. Sellaisenaan modulaarisuus on mitta siitä, kuinka hyvin klusteroitu kaavio on erillisissä yhteisöissä.

Jakamalla 2L: llä rajataan modulaarisuuden yläarvo 1.: lla. Lähellä nollaa tai sen alapuolella olevat modulaarisuuspisteet osoittavat, että verkon nykyisellä klusteroinnilla ei todellakaan ole hyötyä. Mitä suurempi modulaarisuus, sitä parempi verkon ryhmittely erillisiin yhteisöihin. Maksimoimalla modulaarisuus voimme löytää parhaan tavan verrata klusterointia.

Huomaa, että joudumme ennalta määrittelemään, kuinka kaavio on ryhmitelty saadaksesi selville, kuinka ”hyvä” tämä klusterointi todella on. Valitettavasti raa'an voiman käyttäminen kaikin mahdollisin tavoin ryhmitellä kuvaaja sellaisen löytämiseksi, jolla on korkein modulaarisuuspiste, olisi laskennallisesti mahdotonta ylittää hyvin rajoitetun näytteen koon.

Combinatorics kertoo meille, että vain kahdeksan kärkipisteen verkon kohdalla on 4140 eri tapaa ryhmitellä ne. Kaksinkertaisessa verkossa olisi yli kymmenen miljardia mahdollista tapaa ryhmitellä kärkipisteitä. Verkoston kaksinkertaistaminen (erittäin vaatimattomaan 32 kärkipisteeseen) antaisi 128 seitsemän kilon mahdolli- sia tapoja, ja kahdeksankymmenen kärkipisteen verkko pystyisi klusteroimaan enemmän tavoilla kuin havaittavissa olevassa universumissa on atomeja.

Sen sijaan meidän on siirryttävä heuristiseen menetelmään, joka tekee kohtuullisen hyvää työtä arvioidessaan klusterit, jotka tuottavat korkeimman modulaarisuuspisteen, kokeilematta kaikkia mahdollisuuksia. Tämä on nopea-ahne modulaarisuus-maksimointi -niminen algoritmi, ja se on jonkin verran analoginen yllä kuvatun agglomeratiivisen hierarkkisen klusterointialgoritmin kanssa. Yhdistämisen sijaan etäisyyden mukaan 'Mod-Max' yhdistää yhteisöt modulaarisuuden muutosten mukaan. Näin se menee:

Aloita määrittämällä aluksi jokainen kärkipiste omaan yhteisöönsä ja laskemalla koko verkon modulaarisuus, M.

Vaihe 1 edellyttää, että jokaiselle ainakin yhdellä reunalla linkitetylle yhteisöparille, algoritmi laskee modulaarisuuden AM tuloksena olevan muutoksen, jos kaksi yhteisöä yhdistetään yhdeksi.

Vaihe 2 vie sitten parin yhteisöjä, jotka tuottavat suurimman lisäyksen AM: ssä, jotka sitten yhdistetään. Laske tämän klusterin uusi modulaarisuus M ja pidä siitä kirjaa.

Toista vaiheet 1 ja 2 - joka kerta yhdistämällä pari yhteisöjä, joille näin tehdään, saadaan suurin voitto ΔM: ssä, kirjataan sitten uusi klusterointikuvio ja siihen liittyvä modulaarisuuspiste M.

Pysäytä, kun kaikki huiput on ryhmitelty yhdeksi jättiläisryhmäksi. Nyt algoritmi tarkistaa säilyttämänsä tietueet kulkiessaan ja tunnistaa klusterointikuvion, joka palautti M: n korkeimman arvon. Tämä on palautettu yhteisörakenne.

Tarkempia tietoja:

Vau! Se oli laskennallisesti intensiivistä, ainakin meille ihmisille. Graafiteoria on rikas lähde laskennallisesti haastaville, usein NP-koville ongelmille - mutta sillä on myös uskomattomia mahdollisuuksia tarjota arvokkaita tietoja monimutkaisista järjestelmistä ja tietojoukoista. Kysy vain Larry Pageiltä, ​​jonka samanniminen PageRank-algoritmi, joka auttoi ajamaan Googlea aloittamisesta pohjimmiltaan maailman hallitsemiseksi alle sukupolvessa, perustui kokonaan graafiteoriaan.

Yhteisön havaitseminen on nykyisen tutkimuksen tärkein painopiste graafiteoriassa, ja modulaarisuudelle-maksimoinnille on runsaasti vaihtoehtoja, joista on hyötyä, mutta joillakin on haittoja.

Ensinnäkin sen agglomeratiivisessa lähestymistavassa pienet, hyvin määritellyt yhteisöt nielataan suuremmiksi. Tätä kutsutaan resoluutiorajaksi - algoritmi ei löydä tietyn koon alapuolella olevia yhteisöjä. Toinen haaste on, että sen sijaan, että meillä olisi yksi erillinen, helposti tavoitettavissa oleva maailmanlaajuinen huippu, Mod-Max-lähestymistapa pyrkii todella tuottamaan laajan "tasangon", joka sisältää monia samanlaisia ​​korkean modulaarisuuden pisteitä - mikä tekee jonkin verran vaikeaksi tunnistaa absoluuttisen maksimipistemäärän. .

Muut algoritmit käyttävät erilaisia ​​tapoja määritellä ja lähestyä yhteisön havaitsemista. Edge-Betweenness on jakava algoritmi, joka alkaa kaikista kärkipisteistä, jotka on ryhmitelty yhteen jättiläis klusteriin. Edelleen iteratiivisesti poistetaan verkon vähiten "tärkeät" reunat, kunnes kaikki kärjet jätetään eristettyihin. Tämä tuottaa hierarkkisen rakenteen, jossa samanlaiset huiput ovat lähempänä toisiaan hierarkiassa.

Toinen algoritmi on Clique Percolation, joka ottaa huomioon mahdolliset päällekkäisyydet kuvaajayhteisöjen välillä. Vielä yksi joukko algoritmeja perustuu satunnaisiin kävelyihin graafin poikki, ja sitten on spektrin ryhmittelymenetelmiä, jotka alkavat sukeltaa vierekkäisyysmatriisin ja muiden siitä johdettujen matriisien omahajoamiseen. Näitä ideoita käytetään ominaisuuksien poimintaan esimerkiksi sellaisilla alueilla kuin Computer Vision.

Tämän artikkelin soveltamisalan ulkopuolella olisi jokaiselle algoritmille oma syvällinen esimerkki. Riittää, kun sanotaan, että tämä on aktiivinen tutkimusalue, joka tarjoaa tehokkaita menetelmiä datan ymmärtämiseksi, jota jopa sukupolvi sitten olisi ollut vaikea käsitellä.

johtopäätös

Toivottavasti tämä artikkeli on saanut tietoa ja inspiroinut sinua ymmärtämään paremmin, kuinka koneet voivat ymmärtää Big Datan! Tulevaisuus on nopeasti muuttuva paikka, ja monia näistä muutoksista ohjaa se, mitä tekniikka kykenee seuraavan tai kahden sukupolven aikana.

Kuten johdannossa todetaan, koneoppiminen on erityisen kunnianhimoinen tutkimusala, jossa massiivisesti monimutkaiset ongelmat on ratkaistava mahdollisimman tarkasti ja tehokkaasti. Meille ihmisille luonnollisesti tulevat tehtävät vaativat innovatiivisia ratkaisuja koneiden suorittamina.

Edelleen on vielä paljon edistymistä, ja kuka tahansa seuraavan läpimurtoidean edistäjästä palkitaan epäilemättä runsaasti. Ehkä joku tätä artikkelia lukeva on seuraavan tehokkaan algoritmin takana? Kaikkien hienon idean on alkava jostakin!