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

[Dan Filimon]

Mulțumesc! Aici e linkul către commit [1].

[1]
https://github.com/apache/mahout/commit/5a7100ab8a1270a5423acf266df75148368f1d78


2013/5/9 Valentin Gosu <valentin.gosu at gmail.com>

> 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
>>
>>
>
> _______________________________________________
> 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/20130510/cacdf2c3/attachment.html>