<div dir="ltr"><div>Adaugat.<br><br></div>Mersi<br></div><div class="gmail_extra"><br><br><div class="gmail_quote">2013/5/9 Dan Filimon <span dir="ltr"><<a href="mailto:dfilimon@apache.org" target="_blank">dfilimon@apache.org</a>></span><br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><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>- 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>Efectul este că durează mai mult, dar obține clustere mai bune.</div>
<div><br></div><div>- 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><br></div><div>- 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><br></div><div>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><br></div><div>
- la verificarea costului unei clusterizări, există 2 variante:</div><div>a. setul de date de clusteruit este folosit ca atare, în întregime pentru clustering și suma e calculat din tot</div><div>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><br></div><div>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><br></div><div>
- punctele vin unul câte unul (sau în batch-uri)</div><div><br></div><div>- 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>dC reprezeintă distața maximă la care poate fi un punct ca să fie încă parte dintr-un cluster.</div><div><br></div><div>- 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>cele O(k log n) clustere pot fi apoi aglomerate în k clustere cu un run de ball k-means.</div><div><br></div><div>Probabil că nu e prea clar ce-am încercat să explic dintr-un foc, așă că pentru orice întrebări, mail. :)</div>
<div><br></div><div>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>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/" target="_blank">https://reviews.apache.org/r/10194/</a></div><div>[2] <a href="https://issues.apache.org/jira/browse/MAHOUT-1162" target="_blank">https://issues.apache.org/jira/browse/MAHOUT-1162</a></div>
</div><div>[3] <a href="http://berlinbuzzwords.de/sessions/clustering-real-time-data-scale" target="_blank">http://berlinbuzzwords.de/sessions/clustering-real-time-data-scale</a></div></div>
<br>_______________________________________________<br>
upstream-challenge mailing list<br>
<a href="mailto:upstream-challenge@lists.rosedu.org">upstream-challenge@lists.rosedu.org</a><br>
<a href="http://lists.rosedu.org/listinfo/upstream-challenge" target="_blank">http://lists.rosedu.org/listinfo/upstream-challenge</a><br>
<br></blockquote></div><br></div>