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

[Dan Filimon]

Acest commit [1] (un code review pentru moment, commit în curând) rezolvă
[2] și închide astfel seria de issue-uri care descrie proiectul meu de
licență [3].

În acest commit, adaug în principal clasele StreamingKMeansMapper,
StreamingKMeansReducer și StreamingKMeansDriver. Acestea implementează o
variantă de clustering peste Hadoop pentru a putea clusteriza seturi cu
adevărat mari de date.

Asta e important fiindcă algoritmul de clustering k-means funcționează pe
bază de iterații:
[0. la început se aleg centrele inițiale cumva]
1. se trece prin toate punctele și se calculează distanța de la fiecare
punct la fiecare cluster și fiecare punct este clasificat ca aparținând
clusterului celui mai apropiat de el
2. se trece prin toate clusterele și centrele sunt recalculate ca media
punctelor asignate clusterului (asta e partea de "means")

În implementările existente, fiecare iterație de k-means este un map-reduce
întreg, unde pasul 1 (clasificarea) se face în mappere care împart setul de
date între ele și fiecare clasifică o parte din puncte și pasul 2
(repoziționarea centrelor) se face în reducere, fiecare reducer ocupându-se
de o parte dintre centre (sau poate fi doar unul care se ocupă de toate).

Problemele cu asta sunt:
1. pentru k-means: trebuie trecut prin toate punctele și calculate
distanțele la toate clusterele
2. sunt mai multe map-reduce-uri, fiecare implicând scrierea centrelor
intermediare pe disc, recitirea datelor, transferul între calculatoare...

StreamingKMeansDriver implementează un job MR astfel:
1. mapperele rulează StreamingKMeans pe fragmentele lor din date, generând
un clustering aproximativ; algoritmul nu generează un număr fix de
clustere, este random și calitatea clusterizării variază.
Dar, e nevoie de o singură trecere prin date (excluzând un număr relativ
mic de ori în care se trec prin centre fiindcă trebuie agregate fiind prea
multe) și în cod se poate folosi un alt searcher pentru afarea celui mai
apropiat cluster (tot aproximativ, dar funcționează foarte bine în
practică).
StreamingKMeans e folosit pentru construcția unei aproximări (al unui
sketch îi zicem noi :) al clusterizării finale. Scopul esențial e să
reducem dimensiunea datelor din n puncte în O(k log n) puncte ca să poată
intra în memoria unui calculator. Acesta va fi Reducer-ul.

2. reducer-ul (da, este unul singur!) rulează BallKMeans pe sketch-ul
generat de mappere. E necesară această implementare fiindcă ține seama de
greutățile punctelor de clusterizat spre deosebire de ce exista anterior.
BallKMeans, așa cum am scris într-un mail anterior e mult mai flexibil
decât implementările existente (cu rulări multiple cu evaluare a
costurilor, inițializare k-means++, căutări aproximative mai rapide) și
tunat, poate produce rezultate aproximativ la fel de bune ca KMeans.

Am verificat calitatea (MAHOUT 1162 adaugă și niște metrici de calitate) pe
o serie de seturi de date de test (mai mult pe mașina locală) și este
comparabilă cu k-means, uneori chiar un pic mai bună.

Urmează să facem teste mai mari amănunțite dar testele preliminare sunt
bune.

[1] https://reviews.apache.org/r/10193/
[2] https://issues.apache.org/jira/browse/MAHOUT-1181
[3] https://issues.apache.org/jira/browse/MAHOUT-1154
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.rosedu.org/pipermail/upstream-challenge/attachments/20130510/e9c9ab24/attachment.html>