<div dir="ltr">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].<div><br></div><div>Î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.</div>

<div><br></div><div style>Asta e important fiindcă algoritmul de clustering k-means funcționează pe bază de iterații:</div><div style>[0. la început se aleg centrele inițiale cumva]</div><div style>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</div>

<div style>2. se trece prin toate clusterele și centrele sunt recalculate ca media punctelor asignate clusterului (asta e partea de "means")</div><div style><br></div><div style>Î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).</div>

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

<div style><br></div><div style>StreamingKMeansDriver implementează un job MR astfel:</div><div style>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ă.</div>

<div style>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ă).</div>

<div style>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.</div>

<div style><br></div><div style>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.</div>

<div style>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.</div>

<div style><br></div><div style>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ă.</div>

<div style><br></div><div style>Urmează să facem teste mai mari amănunțite dar testele preliminare sunt bune.</div><div><div><br></div><div>[1] <a href="https://reviews.apache.org/r/10193/">https://reviews.apache.org/r/10193/</a></div>

<div>[2] <a href="https://issues.apache.org/jira/browse/MAHOUT-1181">https://issues.apache.org/jira/browse/MAHOUT-1181</a></div><div>[3] <a href="https://issues.apache.org/jira/browse/MAHOUT-1154">https://issues.apache.org/jira/browse/MAHOUT-1154</a></div>

</div></div>