K-means and KD-trees resources [Romanian]

Original in English by Dan Pelleg

K-means şi resurse de KD-copaci

  • Citiţi cartea despre K-mijloace (K-means paper (PS)), sau K-mijloace în PDF (K-means paper (PDF)).
  • Notă: un rezultat recent, similar, deşi independent a fost adus spre atenţia noastră. Aceasta precedează lucrarea noastră. Pentru a forma imagine completă, puteţi citi și pe asta (read).
  • Citiţi cartea X-means (X-means paper (PS)), sau X-means (X-means paper (PDF)).
  • Punerea în aplicare 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 utilizat numai în scopuri experimentale şi de cercetare.
    • Software-ul nu poate fi distribuit la oricine altcineva, şi nu poate fi vândut în totalitate sau ca partea a unui produs software mai mare, fie ca sursă sau în formă binară.

    Pentru al descărca, pur și simplu primiți fişierul potrivit pentru Dvs. la sectiunea de descărcare a kmeans (the kmeans download section).

  • X-means este disponibil pentru cercetători, în formă de sursă. Codul este în standartul C, şi poate fi rulat independent sau printr-un înveliş MATLAB. Este cunoscut pentru compilarea în conformitate cu GCC (pe Linux, Cygwin, OS X, Solaris şi FreeBSD) şi MSVC + +.

    • În plus la X-means, acest cod include, de asemenea, sprijin rapid de K-means. Acesta va accelera aplicația dvs. de K-means, cu condiţia că:
      • Datele dvs. nu au mai mult de 15 dimensiuni. Puteţi obţine în continuare şi să folosiți codul în cazul în care acest lucru nu se deţine, dar nu aşteptaţi ca acesta să fie deosebit de rapid. Codul include o simplă punere în aplicare a K-means care nu utilizează KD-copaci.
      • Puteţi calcula distanţe euclidiene între oricare două puncte de date, şi această distanţă este semnificativă într-un mod pentru dvs. Aceasta este de fapt o condiţie de orice algoritm de K-means.

    • Pentru a obţine acces, umpleți cîmpuri goale din acest Acord de licenţă (License Agreement), şi expediaţi-l înapoi prin e-mail la Dan Pelleg (da, există un semn de plus acolo, doar lăsaţi-l şi cuvintele înainte şi după așa cum ele sunt – totul funcționează). Practic, tot ce se spune este că nu puteţi utiliza acest program în scop comercial. Sunteţi bineveniţi să-l solicitați – am acordat în jurul valorii de 800 de licenţe deja la oameni, în mai multe instituţii şi suntem întotdeauna bucuroși să avem și mai mulţi utilizatori. Eu nu vînd, închiriez sau arunc sau altceva cu adresa dvs. de e-mail pentru orice alt scop în afară de darea instrucţiunilor de descărcare.

    • Aici este, de asemenea, K-means and X-means mailing-list.

  • Mai jos, eu am pregatit un "ghid de desene animate" pentru K-means:

Introducere în K-means

Aici este prezntat un set de date în 2 dimensiuni, cu 8000 de puncte în el. Vom rula 5-medii pe el (K-medii cu K = 5). În plus la punctele pe care le vedem K-means a selectat 5 puncte aleatorii pentru centrele de clasă. Acestea sunt culori de puncte groase de albastru, verde, roșu, negru, și violet. Observaţi că, aşa cum are șansa, ele nu corespund cu Gaussiane de bază (ca o chestiune de fapt am avut necesitatea de obliga programul de a produce aceste puncte "rele" iniţiale – aceasta este destul de bună la obtinerea puncte iniţiale "corecte").

Acum, programul trece peste puncte de date, asociind pe fiecare cu cel mai apropiat centru de clasă. Punctele pe care le vedeţi sunt colorate în conformitate cu centrul cu acestea sunt asociate. Observaţi hotarul albastru-verde în partea de sus a colţului din dreapta. Această linie de puncte(teoretică), care sunt echidistante de la centrele de verde şi albastru determină care punct îi aparţine și unde.

Următorul pas al algoritmului este de a re-poziţiona centrele de clasă. Centrul verde va fi plasat la centrul de masă al tuturor punctelor verzi, şi aşa mai departe. După cum se dovedeşte, centrul de verde se va deplasa la dreapta şi sus. Linia neagră va merge de la centru verde care arată acest lucru. Observaţi că centrele de negru şi roşu fiecare partajează aproximativ jumătate din Gaussian pe stânga (şi aproximativ o jumătate din Gaussian în care ei sunt), asa că ele ambele "trec" la stânga. Mișcarea în centrul violet este foarte mică.

Click pe imagine pentru a vedea o versiune mai mare. Puteţi să-l deschide într-o nouă fereastră de browser, astfel încât să puteţi citi în continuare textul.


Programul a mutat centrele, şi a re-colorat toate punctele în accord cu cel mai apropiat centru pentru fiecare. Din cînd centrul verde este mutat, hotarul albastru-verde trece "în afara" a Gaussianei în colţul de sus-dreapta. Şi este, probabil, undeva în zona nepopulată între albastru şi verde. Noi dorim ca acest tip de lucru să se întâmple.

Prin uitarea la vectorii de circulaţie, se poate vedea, cum negru şi roşu vor continua curse la stânga, şi violet domină acum o bună parte a împrejurimilor sale. Observaţi Gaussiană "orfană"  între violet şi verde. Acest lucru sa întâmplat deoarece negru şi roşu se află în aceaaşi Gaussiană, asa că am "scurtat" un centroid.

small


Hotarul verde-violet trece în sus şi la dreapta; pare că verde se va deţine doar la puncte de violet şi va deţine două Gaussiane. Pe partea de jos în stânga a colţului, se pare că roșu a pierdut cursa spre negru (negru este mai mult la stânga).

small


O altă repetare…

small


Acum hotarele albastru-verde si verde-violet reprezintă set de destul de mare (ceea ce ar trebui să fie). Observaţi că roşu se va schimba, fiecare dată atât de uşor, spre dreapta.

small


Roşu a plecat la dreapta. Deci, a câştigat mai multe puncte violete. Din moment ce toate punctele violete sunt la dreapta, acest effect se intensifică. Prin urmare, violet pierde puncte la roşu, şi precum şi se mută la dreapta (şi până).

small


O altă repetare …

small


Şi încă una…

small


Şi alta …


Rosu a finalizat drumul său, câştigând controlul asupra unei Gaussiane deţinute anterior de violet. Negru ajunge să deţină întreaga Gaussiană la stânga. K-means a găsit partiţie "corectă". Deoarece aceasta este o configuraţie stabilă, în următoarele repetări centrele nu se vor muta de prea mult.

small


Introducere în KD-copaci

Din nou, setul nostru de date din 8000 de puncte generate aleator, de o distributie de 5-Gaussiană. Ar trebui să vedeţi Gaussians de bază. Hotarul albastru denotă KD-nod de "rădăcină". Acesta cuprinde toate punctele.

small


Acum observați copiii a nodului rădăcină. Fiecare este un dreptunghi, cu linie de divizare paralelă cu axa Y ce trece aproximativ prin jumătate de drum.

small


Acum puteți vedea copii mari a rădăcinei. Fiecare dintre ei este o separare a părintelui său, de-a lungul axei X de data aceasta.

small


Şi aşa mai departe, împărțirea pe dimensiuni alternative…

small


small


small


small


small


small


small


Aici sunt primele şapte straturi de KD-copac, toate într-o singură imagine.

small


Producerea rapidă de K-medii cu KD-copaci

Toate explicaţiile din demo-ul K-mediilor de mai sus au fost adevărat şi pentru K-medii tradiţionale. "Tradiţionale" înseamnă că atunci când vă duceți afară şi decideți care este cel mai apropiat centru de la fiecare punct (de exemplu, determină culori), o faceți  în mod naiv: pentru fiecare punct, calculați distantele la toate centrele şi găsiți minimum. Programul nostru este mult mai inteligent cem această metodă. Ea mai întâi construiește un KD-copac pentru puncte (unul pe care ați văzut mai devreme). Acum, să presupunem că un KD- nod este deţinut în întregime de către un centru. Acest lucru înseamnă că mişcarea viitoare a centrului va fi afectată de centrul de masă al punctelor în care se află KD-nod (şi numărul lor). Deci, pre-calculînd centrul de masă al fiecărei KD-nod, şi stocînd acestd în nod, putem economisi o mulţime de muncă. [aratînd că unele noduri care sunt deţinute în întregime de către un centru pot fi, de asemenea, făcute eficient – priviți lucrarea fast K-means paper].

Acest tip de calcul rapid s-a întâmplat în spatele scenei prin întregul demo. Ori de câte ori un nod sa dovedit a fi deţinut integral de către un centru, programul a desenat nodul de a fi dreptunghiular. Pentru scopuri de vizualizare acesta, de asemenea, a desenat puncte de interior, dar un program "real" nu are nevoie de a face acest lucru. Se foloseşte doar un număr foarte mic constant de operaţii aritmetice pentru a calcula efectul pe care are un anumit KD-nod. Acest lucru este spre deosebire de însumarea coordonatelor fiecărui punct în interiorul acestui dreptunghi, care este, un cost care este liniar în numărul de puncte în dreptunghi.

Observaţi cât de uşor a fost de a calcula centre de masă lui negru şi albastru. Negru a luat doar două noduri, şi aproximativ 50 de puncte suplimentare individuale. Albastru a luat 5 noduri, plus aproximativ 10 puncte. Comparaţi acest lucru cu cele 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 se micșorează cu cît ne apropiem de linia de graniţă teoretică despre care am vorbit mai înainte. Uitați-vă la graniță roşu-violet. Aşa cum ne apropiem de ea, e mai greu şi mai greu pentru noduri mari, groase de a fi deţinuți în întregime de către fie de culoare roşie sau violet. Dacă vă gândiți la asta, vedeți vă ele nu pot fi deţinute în întregime de către oricare centru în cazul în care această limită le intersectează. Deci, cu cît mai mult apropiem de limita, cu atît mai mic devin dreptunghiuri. Şi sunt destul de multe de puncte individuale foarte apropiate de limită.

ok ok