[upstream-challenge] [Anul 4] Apache Mahout 1162

[Valentin Gosu]

Adaugat.

Mersi


2013/5/9 Dan Filimon <dfilimon at apache.org>

> Acest commit [1] (care de fapt e acum un review request și va fi comituit
> în scurt timp) rezolvă issue-ul [2].
>
> Este o mare parte parte (inima chiar :) proiectului meu de licență.
>
> Adaugă 2 noi algoritmi de clustering în Mahout: BallKMeans și
> StreamingKMeans.
>
> BallKMeans este similar cu KMeans obișnuit, dar pe lângă k-means obișunit
> adaugă următoarele:
>
> - 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ă;
> Efectul este că durează mai mult, dar obține clustere mai bune.
>
> - 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.
>
> - 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)
>
> 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.
>
> - la verificarea costului unei clusterizări, există 2 variante:
> a. setul de date de clusteruit este folosit ca atare, în întregime pentru
> clustering și suma e calculat din tot
> 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ă.
>
> 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:
>
> - punctele vin unul câte unul (sau în batch-uri)
>
> - 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.
> dC reprezeintă distața maximă la care poate fi un punct ca să fie încă
> parte dintr-un cluster.
>
> - 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;
> cele O(k log n) clustere pot fi apoi aglomerate în k clustere cu un run de
> ball k-means.
>
> Probabil că nu e prea clar ce-am încercat să explic dintr-un foc, așă că
> pentru orice întrebări, mail. :)
>
> 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
> Din păcate, mai am încă de lucru un pic la cod acum și oricum UC se
> termină înainte.
>
> [1] https://reviews.apache.org/r/10194/
> [2] https://issues.apache.org/jira/browse/MAHOUT-1162
> [3] http://berlinbuzzwords.de/sessions/clustering-real-time-data-scale
>
> _______________________________________________
> upstream-challenge mailing list
> upstream-challenge at lists.rosedu.org
> http://lists.rosedu.org/listinfo/upstream-challenge
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.rosedu.org/pipermail/upstream-challenge/attachments/20130509/d6a9f59c/attachment.html>