K-means

Sursă originală: http://www.cs.cmu.edu/~dpelleg/kmeans.html

Resursele K-means și KD-trees

  • Citiți hârtia K-means (PS) sau hârtia K-means (PDF) .
  • Notă: recent, un rezultat similar, deși independent, ne-a fost adus în atenție. Înainte de munca noastră. Pentru completare, puteți citi și asta.
  • Citiți hârtia cu hârtie X (PS) sau hârtia X (PDF) .
  • Implementarea X-means și K-means în formă binară este acum disponibilă pentru descărcare! În prezent, există versiuni pentru linux, OS X și MS-Windows. Acestea sunt distribuite în următoarele condiții:
    • Software-ul poate fi folosit numai în scopuri experimentale și de cercetare.
    • Software-ul nu poate fi distribuit nimănui și nu poate fi vândut în întregime sau în cadrul unei părți a unui produs software mai mare, fie în formă sursă, fie în formă binară.
    Pentru ao descărca, pur și simplu, obțineți fișierul potrivit pentru dvs. în secțiunea de download kmeans .
  • X-means este disponibil cercetătorilor în formă sursă. Codul este în standardul C și poate fi rulat independent sau printr-un pachet MATLAB. Este cunoscută compilarea sub GCC (pe Linux, Cygwin, OS X, Solaris și FreeBSD) și MSVC ++.
    • În plus față de mijloacele X, acest cod include, de asemenea, suport rapid pentru mijloacele K. Acesta va accelera aplicația K-mean, cu condiția ca:
      • Datele dvs. nu au mai mult de 15 dimensiuni. Totuși, puteți obține și utiliza codul dacă acest lucru nu este valabil, dar nu vă așteptați ca acesta să fie deosebit de rapid. Codul include o implementare simplă a mijloacelor K care nu utilizează copaci KD.
      • Puteți să calculați distanțele euclidane între oricare dintre cele două puncte de date și această distanță este semnificativă în vreun fel pentru dvs. Aceasta este de fapt o condiție prealabilă a oricărui algoritm K-means.
    • Pentru a obține acces, completați spațiile libere din acest Acord de licență și trimiteți-le înapoi lui Dan Pelleg (da, există un semn plus, lăsați-l și cuvintele înainte și după cum ar fi – funcționează). Practic, tot ce spune este că nu poți folosi acest program comercial. Puteți să o solicitați – am acordat deja aproximativ 800 de licențe persoanelor din cât mai multe instituții și am întotdeauna bucuros să am mai mulți utilizatori. Nu voi vinde, închiria, distribui sau utiliza în alt mod adresa dvs. de e-mail în alte scopuri decât să vă dau instrucțiunile de descărcare.
    • Există, de asemenea, o listă de corespondență K-means și X-means mailing-list .
  • Mai jos, am pregătit un “ghid de desene animate” pentru K-înseamnă:

Introducere în mijloacele K

Iată un set de date în 2 dimensiuni, cu 8000 de puncte în el. Vom rula 5 mijloace pe ea (K-mijloace cu K = 5). În plus față de punctele pe care le vedem, K-means a selectat 5 puncte aleatoare pentru centrele de clasă. Acestea sunt punctele de albastru, verde, rosu, negru și violet. Observați că, așa cum o are șansa, ele nu corespund gaussienilor (de fapt a trebuit să forțez programul să producă acele “prime” puncte inițiale – este destul de bine să primești punctele inițiale “corecte”) .

Acum, programul trece prin datapoints, asocierea fiecăruia cu centrul de clasă cel mai aproape de el. Punctele pe care le vedeți sunt colorate în funcție de centrul în care sunt asociate. Observați limita albastru-verde în colțul din dreapta sus. Această linie (teoretică) de puncte care sunt echidistant față de centrele verde și albastre determină locul în care aparțin.

Următorul pas al algoritmului este de a re-poziționa centrele de clasă. Centrul verde va fi plasat în centrul de masă a tuturor punctelor verzi, și așa mai departe. După cum se dovedește, centrul verde se va deplasa spre dreapta și spre în sus. Linia neagră care iese din centrul verde arată asta. Observați că centrele negre și roșii împărtășesc fiecare jumătate din Gaussianul din stânga (și aproximativ jumătate din gaussianul în care se află), așa că ambii “se cer” spre stânga. Mișcarea centrului purpuriu este foarte mică.

Faceți clic pe imagine pentru a vedea o versiune mai mare. Puteți să o deschideți într-o fereastră nouă a browserului, astfel încât să puteți citi în continuare textul.


Programul a mutat centrele și a re-colorat toate punctele în funcție de care centrul este cel mai apropiat de fiecare. De când centrul verde sa mișcat, limita albastru-verde trece “în afară” de Gaussian în colțul din dreapta sus. Și este probabil undeva în zona nepopulată între albastru și verde. Vrem ca acest lucru să se întâmple.

Privind vectorii de mișcare, puteți vedea că negrul și roșul vor continua cursele spre stânga, iar purpuriu domina acum o bună parte din împrejurimile sale. Observați Gaussianul “orfan” între purpură și verde. Acest lucru sa întâmplat deoarece negrul și roșul locuiesc în același Gaussian, deci suntem “scurți” un centroid.


Limita verde-violet se mișcă în sus și spre dreapta; arata ca verdele va detine doar “punctele sale”, iar purpurii vor detine doi Gaussieni. În colțul din stânga jos, se pare că roșu a pierdut cursa la negru (negrul este mai mult spre stânga).


O altă iterație …


Acum limitele albastru-verde și verde-violet sunt destul de mult stabilite (la ceea ce ar trebui să fie). Observați că roșul se va schimba, chiar atât de ușor, spre dreapta.


Red a mers în dreapta. Deci a câștigat mai multe puncte purpurii. Deoarece toate punctele purpurii sunt în dreapta ei, acest efect se intensifică. În consecință, purpuriu pierde puncte la roșu, și se mișcă dreapta (și sus), de asemenea.


O altă iterație …


Si inca una…


Si inca una…


Roșia și-a încheiat călătoria, obținând controlul asupra unui Gaussian deținut anterior de purpuriu. Negrul devine proprietarul întregului Gaussian din stânga. K-means a găsit partiția “corectă”. Deoarece aceasta este o configurație stabilă, următoarele iterații nu vor mișca prea mult centrele.


Introducere în copaci KD

Din nou, setul nostru de date de 8000 de puncte generate aleatoriu, dintr-o distribuție de 5-Gaussiană. Ar trebui să vezi gaussienii subiacenți. Limita albastră denotă nodul “root” kd. Acesta cuprinde toate punctele.


Acum, vezi copiii nodului rădăcină. Fiecare este un dreptunghi, cu linia de despicare paralelă cu axa Y aproximativ la jumătatea drumului.


Acum vezi bunicii rădăcinii. Fiecare dintre ele este o divizare a părintelui său, de-a lungul axei X de data aceasta.


Și așa mai departe, împărțind dimensiunile alternante …








Iată primele șapte straturi ale copacului KD, toate într-o singură fotografie.


Făcând K-mijloace rapide cu copaci KD

Toate explicațiile din demo-ul K-means de mai sus erau adevărate pentru mijloacele K tradiționale. “Tradițional” înseamnă că atunci când ieșiți și decideți ce centru este cel mai apropiat de fiecare punct (de exemplu, determinați culorile), faceți-l pe cel naiv: pentru fiecare punct, calculați distanțele la toate centrele și găsiți minimul. Programul nostru este mult mai inteligent atunci. Mai întâi construiește un kd-tree pentru punctele (cel pe care l-ați văzut mai devreme). Acum presupuneți că un nod kd este în întregime deținut de un centru. Aceasta înseamnă că următoarea mișcare centrală va fi afectată de centrul de masă al punctelor din acest kd-nod (și numărul lor). Deci, prin pre-calculul centrului de masă al fiecărui nod kd și stocarea lui în nod, putem salva o mulțime de lucruri. [care arată că un nod este în totalitate deținut de un centru poate fi făcut, de asemenea, în mod eficient – a se vedeahârtie rapidă K-înseamnă ].

Acest tip de calcul rapid a avut loc în spatele scenei pe parcursul demo-ului. Ori de câte ori un nod a fost dovedit a fi pe deplin deținut de un centru, programul a atras dreptunghiul nodului. Pentru scopuri de vizualizare a atras și ele punctele din interiorul său, însă nu este nevoie de un program “real”. Folosește doar un număr foarte mic constant de operații aritmetice pentru a calcula efectul pe care un anumit kd-nod va avea. Acest lucru se opune însumării coordonatelor fiecărui punct din interiorul acelui dreptunghi, adică un cost care este liniar în numărul de puncte din dreptunghi.

Observați cât de ușor a fost să calculați centrele de masă negre și albastre. Negrul a luat doar două noduri și aproximativ 50 de puncte individuale suplimentare. Albastrul a luat 5 noduri, plus aproximativ 10 puncte. Comparați acest lucru cu cei aproximativ 8000/5 = 1600 de puncte pe care fiecare are (și făcând 5 distanțe pentru fiecare!).

Un alt lucru interesant de observat este modul în care aceste dreptunghiuri devin mai mici pe măsură ce abordăm linia teoretică de frontieră despre care am vorbit înainte. Urmăriți limita roșu-purpuriu. Pe măsură ce ne apropiem de aceasta, este mai greu și mai greu ca nodurile mari, grase să fie deținute în întregime fie de roșu, fie de purpuriu. Dacă vă gândiți la ele, ele nu pot fi deținute în întregime de nici unul dintre centre dacă această limită le intersectează. Deci, cu cât ajungem mai aproape de graniță, cu atât sunt mai mici dreptunghiurile. Și sunt foarte multe puncte individuale foarte apropiate de graniță.

Menținută de Dan Pelleg .


Acest material se bazeaza pe munca sustinuta de National Science Foundation Grant No. 0121671.