<div dir="ltr">Acest commit [1] (care de fapt e acum un review request și va fi comituit în scurt timp) rezolvă issue-ul [2].<div><br></div><div>Este o mare parte parte (inima chiar :) proiectului meu de licență.</div><div>

<br></div><div>Adaugă 2 noi algoritmi de clustering în Mahout: BallKMeans și StreamingKMeans.</div><div><br></div><div>BallKMeans este similar cu KMeans obișnuit, dar pe lângă k-means obișunit adaugă următoarele:</div><div>

<br></div><div style>- inițializare cu k-means++, care alege centrele luând în calcul weight-urile relative ale punctelor în plus pe lângă inițializarea random obișnuită;</div><div style>Efectul este că durează mai mult, dar obține clustere mai bune.</div>

<div style><br></div><div style>- trimFraction, este partea de "ball": nu toate punctele sunt considerate în recalcularea clusterelor, ci doar acelea care sunt la mai puțin de trimFraction * distanța minimă până la cel mai apropiat alt cluster.</div>

<div style><br></div><div style>- suportă mai multe run-uri intern; se știe că la fel ca mulți algoritmi aleatori, la k-means ajută repornirea de câteva ori să nu fie vorba de o alegere "ghinionistă" a centrelor din care să rezulte clustere proaste (spre exemplu dacă centrele inițiale sunt alese în același cluster, este practic imposibil să se mai poată obține clustere separate)</div>

<div style><br></div><div style>Am implementat mai multe run-uri și în plus, verificăm costul unui run ca suma totală a distanțelor de la fiecare punct la centrul căruia îi este asignat.</div><div style><br></div><div style>

- la verificarea costului unei clusterizări, există 2 variante:</div><div style>a. setul de date de clusteruit este folosit ca atare, în întregime pentru clustering și suma e calculat din tot</div><div style>b. o fracțiune din puncte (10%) e pusă deoparte ca un fel de set de "test" (nu e chiar așa fiindcă nu e o problemă de învățarea automată supervizată). Pe această fracțiune, lăsată deoparte sunt calculate costurile, ideea fiind că ne trebuie clustere care să poată aproxima distribuția reală a datelor, nu să facă "overfitting" în cazul în care am selectat un sample mai biased din distribuția inițială.</div>

<div style><br></div><div style>StreamingKMeans este complet diferit de abordările de clustering de până acum și ar putea de fapt fi asimilat cu un algoritm aglomerativ de clustering, online:</div><div style><br></div><div style>

- punctele vin unul câte unul (sau în batch-uri)</div><div style><br></div><div style>- la fiecare punct de adăugat, punctul este adăugat la un cluster existent cu o probabilitate de d / dC unde d este distanța până la cel mai apropiat alt cluster și dC este un fel de distance cutoff.</div>

<div style>dC reprezeintă distața maximă la care poate fi un punct ca să fie încă parte dintr-un cluster.</div><div style><br></div><div style>- numărul de clustere efective și dC sunt ajustate dinamic pe parcursul execuție în ideea de a obține O(k log n) clustere unde k este numărul de clustere "cerute" și n este numărul de puncte procesate;</div>

<div style>cele O(k log n) clustere pot fi apoi aglomerate în k clustere cu un run de ball k-means.</div><div style><br></div><div style>Probabil că nu e prea clar ce-am încercat să explic dintr-un foc, așă că pentru orice întrebări, mail. :)</div>

<div style><br></div><div style>Oricum, în curând trebuie să pregătesc slide-uri ca lumea și explicații pentru o prezentare pe care o țin în iunie la Buzzwords 2013 [3]. :D</div><div style>Din păcate, mai am încă de lucru un pic la cod acum și oricum UC se termină înainte.</div>

<div><br><div>[1] <a href="https://reviews.apache.org/r/10194/">https://reviews.apache.org/r/10194/</a></div><div>[2] <a href="https://issues.apache.org/jira/browse/MAHOUT-1162">https://issues.apache.org/jira/browse/MAHOUT-1162</a></div>

</div><div>[3] <a href="http://berlinbuzzwords.de/sessions/clustering-real-time-data-scale">http://berlinbuzzwords.de/sessions/clustering-real-time-data-scale</a></div></div>