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

[Dan Filimon]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.rosedu.org/pipermail/upstream-challenge/attachments/20130509/d4885a0b/attachment.html>