K-Means Clustering Algorithm in Java

1. Prehľad

Klastrovanie je zastrešujúcim pojmom pre triedu nekontrolovaných algoritmov objavte skupiny vecí, ľudí alebo myšlienok, ktoré spolu úzko súvisia.

V tejto zjavne jednoduchej definícii jedného riadku sme videli niekoľko módnych slov. Čo je to klastrovanie? Čo je to algoritmus bez kontroly?

V tomto tutoriále najskôr objasníme tieto koncepty. Potom uvidíme, ako sa môžu prejaviť v Jave.

2. Algoritmy bez dozoru

Predtým, ako použijeme väčšinu výučbových algoritmov, mali by sme im nejako vložiť niekoľko vzorových údajov a umožniť algoritmu, aby sa z týchto údajov poučil. V terminológii strojového učenia sa nazývame to vzorové školiace údaje. Tiež celý proces sa nazýva tréningový proces.

Každopádne môžeme klasifikovať algoritmy učenia na základe množstva dohľadu, ktoré potrebujú počas tréningového procesu. Dva hlavné typy učebných algoritmov v tejto kategórii sú:

  • Učenie pod dohľadom: V kontrolovaných algoritmoch by tréningové údaje mali obsahovať skutočné riešenie pre každý bod. Napríklad, ak sa chystáme trénovať náš algoritmus filtrovania nevyžiadanej pošty, dodáme tomuto algoritmu vzorové e-maily aj ich štítky, t. J. Nevyžiadanú poštu alebo nevyžiadanú poštu. Matematicky vzaté, z toho vyvodíme f (x) z tréningovej zostavy vrátane oboch xs a ys.
  • Učenie bez dozoru: Ak v tréningových dátach nie sú žiadne štítky, potom je algoritmus bez dozoru. Napríklad máme veľa údajov o hudobníkoch a v dátach objavíme skupiny podobných hudobníkov.

3. Zhlukovanie

Zhlukovanie je nekontrolovaný algoritmus na objavovanie skupín podobných vecí, nápadov alebo ľudí. Na rozdiel od supervidovaných algoritmov necvičíme klastrové algoritmy s príkladmi známych značiek. Namiesto toho sa klastrovanie snaží nájsť štruktúry v rámci tréningovej sady, kde štítkom nie je žiadny bod údajov.

3.1. K-znamená zhlukovanie

K-Means je klastrový algoritmus s jednou základnou vlastnosťou: počet klastrov je definovaný vopred. Okrem K-Means existujú aj iné typy klastrových algoritmov, ako napríklad hierarchické klastrovanie, afinitné šírenie alebo spektrálne klastrovanie.

3.2. Ako K-prostriedky fungujú

Predpokladajme, že našim cieľom je nájsť niekoľko podobných skupín v množine údajov, ako napríklad:

K-Znamená, že K začína náhodne umiestnenými centroidmi. Centroidy, ako už ich názov napovedá, sú stredovými bodmi zhlukov. Napríklad tu pridávame štyri náhodné centroidy:

Potom priradíme každý existujúci údajový bod k jeho najbližšiemu ťažisku:

Po zadaní presunieme centroidy na priemerné umiestnenie bodov, ktoré sú im priradené. Pamätajte, že centroidy majú byť stredovými bodmi klastrov:

Aktuálna iterácia sa končí vždy, keď skončíme s premiestnením centroidov. Tieto iterácie opakujeme, kým sa priradenie medzi viacerými po sebe nasledujúcimi iteráciami prestane meniť:

Po ukončení algoritmu sa tieto štyri klastre nájdu podľa očakávania. Teraz, keď vieme, ako K-Means funguje, implementujme ho do Javy.

3.3. Reprezentácia funkcií

Pri modelovaní rôznych výcvikových údajových súborov potrebujeme dátovú štruktúru, ktorá predstavuje atribúty modelu a im zodpovedajúce hodnoty. Napríklad hudobník môže mať žánrový atribút s hodnotou ako Rock. Termín vlastnosť zvyčajne používame na označenie kombinácie atribútu a jeho hodnoty.

Na prípravu súboru údajov pre konkrétny výučbový algoritmus zvyčajne používame bežnú sadu číselných atribútov, ktoré sa dajú použiť na porovnanie rôznych položiek. Ak napríklad umožníme používateľom označiť každého interpreta žánrom, potom na konci dňa môžeme spočítať, koľkokrát je každý interpret označený konkrétnym žánrom:

Vektor funkcií pre umelca ako Linkin Park je [rock -> 7890, nu-metal -> 700, alternatíva -> 520, pop -> 3]. Ak by sme teda našli spôsob, ako reprezentovať atribúty ako číselné hodnoty, potom môžeme jednoducho porovnať dve rôzne položky, napr. umelcov porovnaním ich zodpovedajúcich vektorových vstupov.

Pretože číselné vektory sú také všestranné dátové štruktúry, budeme reprezentovať funkcie, ktoré ich používajú. Tu je príklad, ako implementujeme vektory funkcií v Jave:

public class Record {private final Popis reťazca; súkromné ​​konečné prvky mapy; // konštruktor, getter, toString, rovná sa a hashcode}

3.4. Hľadanie podobných položiek

V každej iterácii K-Means potrebujeme spôsob, ako nájsť najbližší ťažisko každej položky v množine údajov. Jedným z najjednoduchších spôsobov výpočtu vzdialenosti medzi dvoma vektormi prvkov je použitie euklidovskej vzdialenosti. Euklidovská vzdialenosť medzi dvoma vektormi ako [p1, q1] a [p2, q2] rovná sa:

Implementujme túto funkciu v Jave. Po prvé, abstrakcia:

verejné rozhranie Vzdialenosť {dvojnásobný výpočet (Mapa f1, Mapa f2); }

Okrem euklidovskej vzdialenosti existujú aj iné prístupy k výpočtu vzdialenosti alebo podobnosti medzi rôznymi položkami, napríklad Pearsonov korelačný koeficient. Táto abstrakcia uľahčuje prepínanie medzi rôznymi metrikami vzdialenosti.

Pozrime sa na implementáciu pre euklidovskú vzdialenosť:

verejná trieda EuclideanDistance implementuje vzdialenosť {@Override verejný dvojitý výpočet (mapa f1, mapa f2) {dvojnásobný súčet = 0; pre (Reťazcový kľúč: f1.keySet ()) {Double v1 = f1.get (kľúč); Double v2 = f2.get (kľúč); if (v1! = null && v2! = null) {sum + = Math.pow (v1 - v2, 2); }} vratit Math.sqrt (suma); }}

Najskôr vypočítame súčet štvorcových rozdielov medzi zodpovedajúcimi položkami. Potom aplikáciou štvorcový funkcie, vypočítame skutočnú euklidovskú vzdialenosť.

3.5. Zastúpenie ťažísk

Centroidy sú v rovnakom priestore ako bežné objekty, takže ich môžeme reprezentovať podobne ako objekty:

verejná trieda Centroid {súkromné ​​konečné súradnice mapy; // konštruktory, getter, toString, rovná sa a hashcode}

Teraz, keď máme zavedených niekoľko nevyhnutných abstrakcií, je čas napísať našu implementáciu K-Means. Tu je rýchly pohľad na náš podpis metódy:

public class KMeans {private static final Random random = new Random (); verejná statická mapa fit (Zoznam záznamov, int k, vzdialenosť, int maxIterations) {// vynechané}}

Rozoberme si tento podpis metódy:

  • The množina údajov je sada vektorov funkcií. Pretože každý vektor funkcií je a Záznam, potom je typ množiny údajov Zoznam
  • The k parameter určuje počet klastrov, ktoré by sme mali vopred poskytnúť
  • vzdialenosť obsahuje spôsob, akým budeme počítať rozdiel medzi dvoma vlastnosťami
  • K-Means končí, keď sa zadanie prestane meniť na niekoľko po sebe idúcich iterácií. Okrem tejto podmienky ukončenia môžeme umiestniť aj hornú hranicu počtu iterácií. The maxIterácie argument určuje túto hornú hranicu
  • Keď sa K-Means ukončí, každé ťažisko by malo mať niekoľko priradených funkcií, preto používame a Mapaako návratový typ. V zásade každý záznam na mape zodpovedá klastru

3.6. Generácia ťažísk

Prvým krokom je generovanie k náhodne umiestnené centroidy.

Aj keď každé ťažisko môže obsahovať úplne náhodné súradnice, je dobrým zvykom generovať náhodné súradnice medzi minimálnou a maximálnou možnou hodnotou pre každý atribút. Generovanie náhodných centroidov bez zohľadnenia rozsahu možných hodnôt by spôsobilo, že algoritmus bude konvergovať pomalšie.

Najskôr by sme mali vypočítať minimálnu a maximálnu hodnotu pre každý atribút a potom vygenerovať náhodné hodnoty medzi každou dvojicou z nich:

private static Zoznam randomCentroids (Zoznam záznamov, int k) {Zoznam centroidov = nový ArrayList (); Maximálne hodnoty mapy = nová HashMap (); Min. Mapy = nová HashMap (); pre (Záznam záznamu: záznamy) {record.getFeatures (). forEach ((kľúč, hodnota) ->); } Nastaviť atribúty = records.stream () .flatMap (e -> e.getFeatures (). KeySet (). Stream ()) .collect (toSet ()); pre (int i = 0; i <k; i ++) {súradnice mapy = nový HashMap (); pre (Atribút reťazca: atribúty) {double max = maxs.get (atribút); double min = mins.get (atribút); Coordinates.put (atribút, random.nextDouble () * (max - min) + min); } centroids.add (nový ťažisko (súradnice)); } vrátiť centroidy; }

Teraz môžeme každý záznam priradiť k jednému z týchto náhodných centroidov.

3.7. Postúpenie

Najprv dostal a Záznam, mali by sme nájsť ťažisko najbližšie k nemu:

private static Centroid nearestCentroid (Záznam záznamu, Zoznam centroidů, Vzdálenost vzdálenost) {double minimumDistance = Double.MAX_VALUE; Najbližší ťažisko = null; for (Centroid centroid: centroids) {double currentDistance = distance.calculate (record.getFeatures (), centroid.getCoordinates ()); if (currentDistance <minimumDistance) {minimumDistance = currentDistance; najbližšie = ťažisko; }} návrat najbližšie; }

Každý záznam patrí do jeho najbližšieho ťažiska:

private static void assignToCluster (mapa klastre, záznam záznamu, ťažisko centroidov) {clusters.compute (ťažisko, (kľúč, zoznam) -> {if (list == null) {list = nový ArrayList ();} list.add (záznam); návratový zoznam;} ); }

3.8. Ťažisko premiestnenia

Ak po jednej iterácii ťažisko neobsahuje žiadne priradenia, potom ho nepresunieme. V opačnom prípade by sme mali premiestniť súradnicu ťažiska pre každý atribút do priemerného umiestnenia všetkých priradených záznamov:

súkromný statický priemer ťažiska (ťažisko ťažiska, záznamy záznamu) {if (records == null || recordss.isEmpty ()) {návrat ťažiska; } Priemer mapy = centroid.getCoordinates (); records.stream (). flatMap (e -> e.getFeatures (). keySet (). stream ()) .forEach (k -> average.put (k, 0,0)); pre (Záznam záznamu: záznamy) {record.getFeatures (). forEach ((k, v) -> average.compute (k, (k1, currentValue) -> v + currentValue)); } average.forEach ((k, v) -> average.put (k, v / records.size ())); vrátiť nový ťažiskový priemer (priemer); }

Pretože môžeme premiestniť jediné ťažisko, teraz je možné implementovať premiestniťCentroidy metóda:

súkromný statický zoznam relocateCentroids (mapa klastre) {návratové klastre.entrySet (). prúd (). mapa (e -> priemer (e.getKey (), e.getValue ())). collect (toList ()); }

Táto jednoduchá jednoriadková linka prechádza všetkými centroidmi, premiestňuje ich a vracia nové centroidy.

3.9. Dávať to všetko dokopy

V každej iterácii by sme po priradení všetkých záznamov k ich najbližšiemu ťažisku mali najskôr porovnať súčasné priradenia s poslednou iteráciou.

Ak boli priradenia identické, algoritmus sa ukončí. V opačnom prípade by sme pred prechodom na ďalšiu iteráciu mali premiestniť centroidy:

verejná statická mapa fit (Zoznam záznamov, int k, Vzdialenosť, int maxIterácie) {Zoznam centroidov = randomCentroids (záznamy, k); Mapa klastre = nový HashMap (); Mapa lastState = new HashMap (); // iterácia pre vopred definovaný počet opakovaní pre (int i = 0; i <maxIterations; i ++) {boolean isLastIteration = i == maxIterations - 1; // v každej iterácii by sme mali nájsť najbližší centroid pre každý záznam pre (Record record: records) {Centroid centroid = nearestCentroid (záznam, centroidy, vzdialenosť); assignToCluster (klastre, záznam, ťažisko); } // ak sa priradenia nezmenia, potom sa algoritmus ukončí boolean shouldTerminate = isLastIteration || clusters.equals (lastState); lastState = klastre; if (shouldTerminate) {break; } // na konci každej iterácie by sme mali premiestniť centroidy centroids = relocateCentroids (clusters); klastre = nový HashMap (); } návrat lastState; }

4. Príklad: Objavovanie podobných umelcov na Last.fm

Last.fm vytvára podrobný profil hudobného vkusu každého používateľa zaznamenávaním podrobností o tom, čo používateľ počúva. V tejto časti nájdeme zhluky podobných umelcov. Na zostavenie množiny údajov zodpovedajúcej tejto úlohe použijeme tri rozhrania API z Last.fm:

  1. API na získanie zbierky najlepších umelcov na Last.fm.
  2. Ďalšie API na vyhľadanie populárnych značiek. Každý užívateľ môže umelca niečím označiť, napr. skala. Last.fm teda udržuje databázu týchto značiek a ich frekvencií.
  3. A API na získanie najlepších značiek pre umelcov zoradené podľa popularity. Pretože existuje veľa takýchto značiek, ponecháme iba tie značky, ktoré patria medzi top globálne značky.

4.1. Last.fm API

Aby sme mohli tieto API používať, mali by sme dostať kľúč API z Last.fm a poslať ho v každej požiadavke HTTP. Na volanie týchto rozhraní API použijeme nasledujúcu službu Retrofit:

verejné rozhranie LastFmService {@GET ("/ 2.0 /? method = chart.gettopartists & format = json & limit = 50") Volať topArtists (@Query ("page") int page); @GET ("/ 2.0 /? Method = artist.gettoptags & format = json & limit = 20 & autocorrect = 1") Volať topTagsFor (@Query ("artist") String artist); @GET ("/ 2.0 /? Method = chart.gettoptags & format = json & limit = 100") Volať topTags (); // Niekoľko DTO a jeden zachytávač}

Poďme teda nájsť najpopulárnejších umelcov na Last.fm:

// nastavenie súkromnej statickej služby Retrofit služby getTop100Artists () vyvolá IOException {List Artists = new ArrayList (); // Načítanie prvých dvoch stránok, z ktorých každá obsahuje 50 záznamov. pre (int i = 1; i <= 2; i ++) {Artists.addAll (lastFm.topArtists (i) .execute (). body (). all ()); } návrat umelci; }

Podobne môžeme načítať najlepšie značky:

private static Set getTop100Tags () hodí IOException {return lastFm.topTags (). execute (). body (). all (); }

Na záver môžeme zostaviť množinu umelcov spolu s ich frekvenciami značiek:

private static List datasetWithTaggedArtists (List Artists, Set topTags) throws IOException {List records = new ArrayList (); pre (String artist: Artists) {Map tags = lastFm.topTagsFor (artist) .execute (). body (). all (); // Ponechať iba populárne značky. tags.entrySet (). removeIf (e ->! topTags.contains (e.getKey ())); records.add (nový záznam (umelec, štítky)); } návratové záznamy; }

4.2. Tvoriace sa zoskupenia umelcov

Teraz môžeme pripravený súbor dát vložiť do našej implementácie K-Means:

Zoznam umelcov = getTop100Artists (); Nastaviť topTags = getTop100Tags (); Zoznam záznamov = datasetWithTaggedArtists (umelci, topTags); Mapa klastre = KMeans.fit (záznamy, 7, nová EuclideanDistance (), 1000); // Tlač konfigurácie klastra clusters.forEach ((kľúč, hodnota) -> {System.out.println ("------------------------- - CLUSTER ---------------------------- "); // Triedenie súradníc tak, aby sa najskôr zobrazili najvýznamnejšie značky. System.out. println (triedenýCentroid (kľúč)); členovia reťazca = String.join (",", value.stream (). mapa (Record :: getDescription) .collect (toSet ())); System.out.print (členovia); System.out.println (); System.out.println ();});

Ak spustíme tento kód, zoskupenia by sa zobrazili ako textový výstup:

------------------------------ CLUSTER ------------------- ---------------- Centroid {classic rock = 65.58333333333333, rock = 64.41666666666667, britský = 20.333333333333332, ...} David Bowie, Led Zeppelin, Pink Floyd, System of a Down, Queen , blink-182, The Rolling Stones, Metallica, Fleetwood Mac, The Beatles, Elton John, The Clash ---------------------------- - CLUSTER ---------------------------------- Centroid {Hip-Hop = 97.21428571428571, rap = 64,85714285714286, hip hop = 29.285714285714285, ...} Kanye West, Post Malone, Childish Gambino, Lil Nas X, A $ AP Rocky, Lizzo, xxxtentacion, Travi $ Scott, Tyler, tvorca, Eminem, Frank Ocean, Kendrick Lamar, Nicki Minaj , Drake ------------------------------ CLUSTER ----------------- ------------------ Centroid {indie rock = 54,0, rock = 52,0, Psychedelic Rock = 51,0, psychedelic = 47,0, ...} Tame Impala, The Black Keys - ---------------------------- CLUSTER --------------------- -------------- Centroid {pop = 81.96428571428571, speváčky = 41,2857142 85714285, indie = 22.785714285714285, ...} Ed Sheeran, Taylor Swift, Rihanna, Miley Cyrus, Billie Eilish, Lorde, Ellie Goulding, Bruno Mars, Katy Perry, Khalid, Ariana Grande, Bon Iver, Dua Lipa, Beyoncé, Sia, P! Nk, Sam Smith, Shawn Mendes, Mark Ronson, Michael Jackson, Halsey, Lana Del Rey, Carly Rae Jepsen, Britney Spears, Madonna, Adele, Lady Gaga, Jonas Brothers ------------ ------------------ CLUSTER ------------------------------- ---- Centroid {indie = 95.23076923076923, alternatíva = 70.61538461538461, indie rock = 64.46153846153847, ...} Twenty One Pilots, The Smiths, Florence + the Machine, Two Door Cinema Club, The 1975, Imagine Dragons, The Killers, Vampire Víkend, Foster the People, The Strokes, Cage the Elephant, Arcade Fire, Arctic Monkeys ------------------------------ CLUSTER - ---------------------------------- Centroid {electronic = 91.6923076923077, House = 39.46153846153846, tanec = 38.0, .. .} Charli XCX, The Weeknd, Daft Punk, Calvin Harris, MGMT, Martin Garrix, Depeche Mode, The Chainsmokers, Avicii, Kygo, Marshmello, David Guetta, Major Lazer ------------------------------ CLUSTER ----- ------------------------------ Centroid {rock = 87.38888888888889, alternatíva = 72.11111111111111, alternatíva rock = 49.16666666, ...} Weezer , The White Stripes, Nirvana, Foo Fighters, Maroon 5, Oasis, Panic! na diskotéke, Gorillaz, Green Day, The Cure, Fall Out Boy, OneRepublic, Paramore, Coldplay, Radiohead, Linkin Park, Red Hot Chili Peppers, múza

Pretože koordinácie centroidov sú zoradené podľa priemernej frekvencie značiek, môžeme ľahko zistiť dominantný žáner v každom klastri. Napríklad posledný zhluk je zhluk starých dobrých rockových kapiel alebo druhý je plný rapových hviezd.

Aj keď má toto zoskupovanie zmysel, väčšinou nie je dokonalé, pretože údaje sa zhromažďujú iba z správania používateľov.

5. Vizualizácia

Pred niekoľkými okamihmi náš algoritmus vizualizoval skupinu umelcov terminálovo priateľským spôsobom. Ak prevedieme našu konfiguráciu klastra na JSON a zavedieme ju do D3.js, potom pomocou niekoľkých riadkov JavaScriptu získame pekný ľudsky priateľský Radial Tidy-Tree:

Musíme previesť naše Mapa do formátu JSON s podobnou schémou, ako je tento príklad d3.js.

6. Počet klastrov

Jednou zo základných vlastností K-Means je skutočnosť, že by sme mali vopred definovať počet zhlukov. Doteraz sme používali statickú hodnotu pre k, ale stanovenie tejto hodnoty môže byť náročným problémom. Existujú dva bežné spôsoby výpočtu počtu klastrov:

  1. Znalosti domény
  2. Matematická heuristika

Ak budeme mať to šťastie, že o doméne vieme toľko, potom by sme možno mohli jednoducho uhádnuť správne číslo.V opačnom prípade môžeme použiť niekoľko heuristík ako Elbow Method alebo Silhouette Method, aby sme zistili počet klastrov.

Než pôjdeme ďalej, mali by sme vedieť, že tieto heuristiky, aj keď sú užitočné, sú iba heuristikou a nemusia poskytovať jasné odpovede.

6.1. Metóda lakťa

Ak chcete použiť metódu lakťa, mali by sme najskôr vypočítať rozdiel medzi každým ťažiskom klastra a všetkými jeho členmi. Keď zoskupujeme viac nesúvisiacich členov v klastri, vzdialenosť medzi ťažiskom a jeho členmi stúpa, a preto klesá kvalita klastra.

Jedným zo spôsobov vykonania tohto výpočtu vzdialenosti je použitie Súčtu štvorcových chýb. Súčet štvorcových chýb alebo SSE sa rovná súčtu štvorcových rozdielov medzi ťažiskom a všetkými jeho členmi:

verejná statická dvojitá sse (mapa zoskupený, vzdialenosť vzdialenosť) {dvojnásobný súčet = 0; pre (Map.Entry entry: clustered.entrySet ()) {Centroid centroid = entry.getKey (); for (Record record: entry.getValue ()) {double d = distance.calculate (centroid.getCoordinates (), record.getFeatures ()); sum + = Math.pow (d, 2); }} návratná suma; }

Potom, môžeme spustiť algoritmus K-Means pre rôzne hodnoty ka vypočítajte SSE pre každú z nich:

Zoznam záznamov = // množina údajov; Vzdialenosť vzdialenosť = nová EuclideanDistance (); Zoznam sumOfSquaredErrors = nový ArrayList (); pre (int k = 2; k <= 16; k ++) {Mapa klastre = KMeans.fit (záznamy, k, vzdialenosť, 1000); double sse = Errors.sse (klastre, vzdialenosť); sumOfSquaredErrors.add (sse); }

Na konci dňa je možné nájsť vhodný prostriedok k vynesením počtu klastrov proti SSE:

Zvyčajne s rastúcim počtom klastrov sa vzdialenosť medzi členmi klastra zmenšuje. Nemôžeme však zvoliť ľubovoľné veľké hodnoty k, pretože mať viac klastrov iba s jedným členom ruší celý účel klastra.

Myšlienkou metódy lakťa je nájsť zodpovedajúcu hodnotu pre k spôsobom, že SSE okolo tejto hodnoty dramaticky klesá. Napríklad, k = 9 môže byť tu dobrým kandidátom.

7. Záver

V tomto tutoriáli sme sa najskôr venovali niekoľkým dôležitým konceptom v strojovom učení. Potom sme sa oboznámili s mechanikou klastrového algoritmu K-Means. Nakoniec sme napísali jednoduchú implementáciu pre K-Means, otestovali náš algoritmus so skutočnou množinou údajov z Last.fm a pekným grafickým spôsobom sme vizualizovali výsledok klastrovania.

Ako obvykle je vzorový kód k dispozícii v našom projekte GitHub, takže si ho určite pozrite!


$config[zx-auto] not found$config[zx-overlay] not found