A K-Means fürtözési algoritmus a Java-ban

1. Áttekintés

A fürtözés egy átfogó kifejezés a felügyelet nélküli algoritmusok osztályához felfedezhet egymással szorosan összefüggő dolgok, emberek vagy ötletek csoportját.

Ebben a látszólag egyszerű, egyvonalas meghatározásban néhány hívószót láttunk. Mi is pontosan a klaszterezés? Mi az a felügyelet nélküli algoritmus?

Ebben az oktatóanyagban először rávilágítunk ezekre a fogalmakra. Majd meglátjuk, hogyan tudnak megnyilvánulni a Java-ban.

2. Felügyelet nélküli algoritmusok

Mielőtt a legtöbb tanulási algoritmust használnánk, valamilyen módon hozzá kell adnunk néhány mintaadatot hozzájuk, és lehetővé kell tennie, hogy az algoritmus tanuljon ezekből az adatokból. A gépi tanulás terminológiájában ezt az adatkészlet mintát képzési adatoknak hívjuk. Is, az egész folyamat képzési folyamat néven ismert.

Egyébként is, osztályozhatjuk a tanulási algoritmusokat a képzési folyamat során szükséges felügyelet mértéke alapján. A tanulási algoritmusok két fő típusa ebben a kategóriában:

  • Felügyelt tanulás: Felügyelt algoritmusokban a képzési adatoknak tartalmazniuk kell az egyes pontok tényleges megoldását. Például, ha a spamszűrő algoritmusunkat ki akarjuk képezni, akkor a minta e-maileket és azok címkéjét, azaz spam vagy nem spam-et is betápláljuk az algoritmusba. Matematikailag nézve arra következtetünk f (x) mindkettőt tartalmazó edzéskészletből xs és ys.
  • Felügyelet nélküli tanulás: Ha nincsenek címkék az edzésadatokban, akkor az algoritmus felügyelet nélküli. Például rengeteg adat áll rendelkezésünkre a zenészekről, és hasonló zenészek csoportjait fedezzük fel az adatokban.

3. Csoportosítás

A fürtözés egy felügyelet nélküli algoritmus hasonló dolgok, ötletek vagy emberek csoportjainak felfedezésére. A felügyelt algoritmusokkal ellentétben nem fürtöző algoritmusokat oktatunk ismert címkék példáival. Ehelyett a fürtözés olyan struktúrákat próbál megkeresni egy képzési készleten belül, ahol az adatok egyetlen pontja sem a címke.

3.1. K-klaszterezés

A K-Means egy klaszterező algoritmus, amelynek egyik alapvető tulajdonsága van: a klaszterek számát előre meghatározzák. A K-Means mellett léteznek más típusú fürtözési algoritmusok is, mint például a hierarchikus fürtözés, az affinitás terjedése vagy a spektrális fürtözés.

3.2. Hogyan működik a K-Means

Tegyük fel, hogy a célunk néhány hasonló csoport megtalálása egy olyan adatkészletben, mint például:

A K-jelentés k véletlenszerűen elhelyezett centridákkal kezdődik. A centroidok, amint a nevük is mutatja, a klaszterek középpontjai. Például itt négy véletlenszerű centridet adunk hozzá:

Ezután minden meglévő adatpontot hozzárendelünk a legközelebbi centroidjához:

A hozzárendelés után a centridákat a hozzá rendelt pontok átlagos helyére mozgatjuk. Ne feledje, hogy a centridák állítólag a klaszterek középpontjai:

Az aktuális iteráció minden alkalommal befejeződik, amikor a centridákat áthelyezzük. Addig ismételjük ezeket az iterációkat, amíg a több egymást követő iteráció közötti hozzárendelés nem változik:

Amikor az algoritmus leáll, akkor a négy klaszter a várakozásoknak megfelelően megtalálható. Most, hogy tudjuk, hogyan működik a K-Means, valósítsuk meg Java-ban.

3.3. Funkcióábrázolás

Különböző képzési adatkészletek modellezéséhez szükségünk van egy adatszerkezetre, amely a modell attribútumait és azok megfelelő értékeit ábrázolja. Például egy zenésznek lehet olyan műfaji attribútuma, amelynek értéke olyan, mint a Rock. A feature kifejezést általában egy attribútum és annak értéke kombinációjára használjuk.

Adatkészlet előkészítéséhez egy adott tanulási algoritmushoz általában egy közös numerikus attribútumkészletet használunk, amely felhasználható a különböző elemek összehasonlítására. Például, ha hagyjuk, hogy a felhasználóink ​​minden egyes előadót megcímkézzenek egy műfajjal, akkor a nap végén megszámolhatjuk, hogy az egyes művészeket hányszor címkézik meg egy adott műfajjal:

A Linkin Parkhoz hasonló művész jellemzővektora az [rock -> 7890, nu-metal -> 700, alternatív -> 520, pop -> 3]. Tehát ha megtalálnánk a módját, hogy az attribútumokat számértékként ábrázoljuk, akkor egyszerűen összehasonlíthatunk két különböző elemet, pl. művészek, összehasonlítva a hozzájuk tartozó vektor bejegyzéseket.

Mivel a numerikus vektorok olyan sokoldalú adatstruktúrák, az ezeket használó jellemzőket fogjuk ábrázolni. Az alábbiakban olvashatjuk el, hogyan valósítjuk meg a szolgáltatásvektorokat a Java-ban:

public class Record {private final String description; privát végleges Térkép jellemzők; // konstruktor, getter, toString, egyenlő és hashcode}

3.4. Hasonló elemek keresése

A K-Means minden iterációjában szükségünk van arra, hogy megtaláljuk az adatkészlet minden eleméhez legközelebbi centroidot. Két jellemzővektor közötti távolság kiszámításának egyik legegyszerűbb módja az euklideszi távolság használata. Az euklideszi távolság két vektor között hasonló [p1, q1] és [p2, q2] egyenlő:

Vezessük be ezt a függvényt Java-ban. Először is, az absztrakció:

nyilvános felület Távolság {dupla számítás (f1 térkép, f2 térkép); }

Az euklideszi távolság mellett vannak más megközelítések a különböző elemek közötti távolság vagy hasonlóság kiszámítására, például a Pearson-korrelációs együttható. Ez az absztrakció megkönnyíti a különböző távolságmérők közötti váltást.

Lássuk az euklideszi távolság megvalósítását:

nyilvános osztály EuclideanDistance megvalósítja a távolságot {@Orride public duplaszámítás (f1 térkép, f2 térkép) {double summa = 0; for (String kulcs: f1.keySet ()) {Double v1 = f1.get (kulcs); Dupla v2 = f2.get (kulcs); if (v1! = null && v2! = null) {összeg + = Math.pow (v1 - v2, 2); }} return Math.sqrt (összeg); }}

Először kiszámoljuk a megfelelő bejegyzések közötti négyzetbeli különbségek összegét. Ezután a sqrt függvény, kiszámoljuk a tényleges euklideszi távolságot.

3.5. Centroid képviselet

A centroidok ugyanabban a térben vannak, mint a normál jellemzők, így a jellemzőkhöz hasonlóan tudjuk őket ábrázolni:

nyilvános osztály Centroid {privát végleges Térkép koordinátái; // konstruktorok, getter, toString, egyenlő és hashcode}

Most, hogy van néhány szükséges absztrakció, itt az ideje megírni a K-Means megvalósításunkat. Itt van egy rövid áttekintés a módszer aláírásunkról:

nyilvános osztály KMeans {privát statikus végleges Random random = new Random (); nyilvános statikus térkép fit (Rekordok felsorolása, int k, Távolság távolsága, int maxIterációk) {// kihagyva}}

Bontjuk le ezt a metódus aláírást:

  • A adatkészlet jellemzővektorok halmaza. Mivel minden jellemzővektor a Rekord, akkor az adatkészlet típusa az Lista
  • A k A paraméter meghatározza a klaszterek számát, amelyet előre meg kell adnunk
  • távolság összefoglalja a két jellemző közötti különbség kiszámításának módját
  • A K-Means akkor szűnik meg, amikor a hozzárendelés néhány egymást követő iterációra leáll. Ezen felmondási feltétel mellett az iterációk számának felső határát is elhelyezhetjük. A maxIterációk argumentum határozza meg azt a felső határt
  • Amikor a K-Means megszűnik, minden centroidnak rendelkeznie kell néhány hozzárendelt funkcióval, ezért a-t használjuk Térképmint visszatérési típus. Alapvetően minden térképbejegyzés megfelel egy fürtnek

3.6. Centroid Generation

Az első lépés a generálás k véletlenszerűen elhelyezett centridok.

Bár minden centroid teljesen véletlenszerű koordinátákat tartalmazhat, ez jó gyakorlat generál véletlenszerű koordinátákat az egyes attribútumok minimális és maximális lehetséges értéke között. Ha véletlenszerű centrideket hoz létre anélkül, hogy figyelembe venné a lehetséges értékek tartományát, az algoritmus lassabban konvergálna.

Először ki kell számolnunk az egyes attribútumok minimális és maximális értékét, majd létre kell hoznunk a véletlenszerű értékeket az egyes párok között:

privát statikus List randomCentroids (List rekordok, int k) {List centroids = new ArrayList (); Map maxs = new HashMap (); Térkép percek = új HashMap (); for (Rekordrekord: rekordok) {record.getFeatures (). forEach ((kulcs, érték) ->); } Set attribútumok = records.stream () .flatMap (e -> e.getFeatures (). KeySet (). Stream ()) .collect (toSet ()); for (int i = 0; i <k; i ++) {Térkép-koordináták = új HashMap (); for (String attribútum: attribútumok) {double max = maxs.get (attribútum); dupla min = mins.get (attribútum); coordinates.put (attribútum, random.nextDouble () * (max - min) + min); } centroids.add (új Centroid (koordináták)); } visszatérő centroidok; }

Most minden rekordot hozzárendelhetünk ezekhez a véletlenszerű centridek egyikéhez.

3.7. Feladat

Először is, adott egy Rekord, meg kell találnunk a hozzá legközelebb eső centroidot:

privát statikus Centroid legközelebbiCentroid (Rekordrekord, Centroidok felsorolása, Távolság távolsága) {double minimumDistance = Double.MAX_VALUE; Centroid legközelebbi = null; mert (Centroid centroid: centridák) {double currentDistance = distance.calculate (record.getFeatures (), centroid.getCoordinates ()); if (currentDistance <minimumDistance) {minimumDistance = currentDistance; legközelebbi = centroid; }} visszatér a legközelebbi; }

Minden rekord a legközelebbi centroid fürtjéhez tartozik:

privát statikus void assignToCluster (Térkép clusters, Record record, Centroid centroid) {clusters.compute (centroid, (kulcs, lista) -> {if (list == null) {list = new ArrayList ();} list.add (rekord); visszatérési lista;} ); }

3.8. Centroid áthelyezés

Ha egy iteráció után egy centroid nem tartalmaz hozzárendeléseket, akkor nem helyezzük át. Ellenkező esetben az egyes attribútumok centroid koordinátáit áthelyezzük az összes hozzárendelt rekord átlagos helyére:

privát statikus Centroid-átlag (Centroid centroid, List-rekordok) {if (rekordok == null || rekordok.isEmpty ()) {visszatérési centroid; } Térképátlag = centroid.getCoordinates (); records.stream (). flatMap (e -> e.getFeatures (). keySet (). stream ()) .forEach (k -> átlagos.put (k, 0.0)); for (Rekordrekord: rekordok) {record.getFeatures (). forEach ((k, v) -> átlagos.számítás (k, (k1, currentValue) -> v + currentValue)); } average.forEach ((k, v) -> átlagos.put (k, v / records.size ())); visszatér az új Centroid (átlag); }

Mivel egyetlen centroidot áthelyezhetünk, most már lehetséges a relocateCentroids módszer:

privát statikus lista relocateCentroids (Map klaszterek) {return clusters.entrySet (). stream (). map (e -> átlag (e.getKey (), e.getValue ())). collect (toList ()); }

Ez az egyszerű egy vonalhajózás végigvezet minden centridon, áthelyezi és visszaadja az új centridákat.

3.9. Összedobva az egészet

Minden iterációban, miután az összes rekordot a legközelebbi centroidhoz rendeltük, először össze kell hasonlítanunk az aktuális hozzárendeléseket az utolsó iterációval.

Ha a hozzárendelések azonosak voltak, akkor az algoritmus megszűnik. Ellenkező esetben, mielőtt a következő iterációra ugranánk, át kell helyeznünk a centridákat:

nyilvános statikus térkép illeszkedés (Lista-rekordok, int k, Távolság, int maxIterációk) {Lista-centridek = randomCentroids (rekordok, k); Térkép klaszterek = új HashMap (); Térkép lastState = új HashMap (); // ismétlés előre meghatározott számú alkalommal a (int i = 0; i <maxIterations; i ++) {logikai isLastIteration = i == maxIterations - 1; // minden iterációban meg kell találnunk a legközelebbi centroidot az egyes rekordokhoz a (Record record: records) {Centroid centroid = legközelebbiCentroid (rekord, centroidok, távolság); assignToCluster (fürtök, rekord, centroid); } // ha a hozzárendelések nem változnak, akkor az algoritmus leállítja a logikai értéket shouldTerminate = isLastIteration || klaszterek.egyenlőség (lastState); lastState = klaszterek; if (kelleneTerminate) {break; } // minden iteráció végén át kell helyeznünk a centridákat centroids = relocateCentroids (clusters); klaszterek = új HashMap (); } return lastState; }

4. Példa: Hasonló művészek felfedezése a Last.fm oldalon

A Last.fm részletes profilt készít az egyes felhasználók zenei ízléséről, rögzítve a felhasználó által hallgatott részletek részleteit. Ebben a részben hasonló művészek klasztereit fogjuk megtalálni. A feladathoz megfelelő adatkészlet létrehozásához három API-t fogunk használni a Last.fm-től:

  1. API a legnépszerűbb művészek gyűjteményének megszerzéséhez a Last.fm webhelyen.
  2. Egy másik API a népszerű címkék megtalálásához. Minden felhasználó megcímkézhet egy előadót valamivel, pl. szikla. Tehát a Last.fm adatbázist tart fenn ezekről a címkékről és azok gyakoriságáról.
  3. És egy API, amellyel előadóhoz lehet kapni a legnépszerűbb címkéket, népszerűség szerint rendezve. Mivel sok ilyen címke létezik, csak azokat a címkéket tartjuk meg, amelyek a legfontosabb globális címkék közé tartoznak.

4.1. A Last.fm API-ja

Ezen API-k használatához meg kell szereznünk egy API kulcsot a Last.fm-től, és el kell küldenünk minden HTTP-kérésben. A következő Retrofit szolgáltatást fogjuk használni az API-k hívására:

nyilvános felület LastFmService {@GET ("/ 2.0 /? method = chart.gettopartists & format = json & limit = 50") Hívja a topArtistákat (@Query ("oldal") int oldal); @GET ("/ 2.0 /? Method = artist.gettoptags & format = json & limit = 20 & autocorrect = 1") Hívja a topTagsFor (@Query ("artist") karakterlánc előadót); @GET ("/ 2.0 /? Method = chart.gettoptags & format = json & limit = 100") Hívja a topTags () parancsot; // Néhány DTO és egy elfogó}

Tehát keressük meg a Last.fm legnépszerűbb előadóit:

// az utólagos szolgáltatás szolgáltatásának statikus listájának beállítása a getTop100Artists () dobja az IOException {List Artists = new ArrayList (); // Az első két oldal beolvasása, mindegyik 50 rekordot tartalmaz. for (int i = 1; i <= 2; i ++) {művészek.addAll (lastFm.topArtists (i) .execute (). body (). all ()); } visszatérő művészek; }

Hasonlóképpen lekérhetjük a legfelső címkéket:

privát statikus set getTop100Tags () dobja az IOException {return lastFm.topTags (). végrehajtani (). body (). all (); }

Végül elkészíthetünk egy előadókból álló adatsort a címkék gyakoriságával együtt:

privát statikus List datasetWithTaggedArtists (List művészek, Set topTags) dobja az IOException {List records = new ArrayList (); for (Vonós művész: művészek) {Map tags = lastFm.topTagsFor (artist) .execute (). body (). all (); // Csak a népszerű címkéket őrizze meg. tags.entrySet (). removeIf (e ->! topTags.contains (e.getKey ())); records.add (új rekord (előadó, címkék)); } visszatérési rekordok; }

4.2. Művész klaszterek létrehozása

Az elkészített adatkészletet betáplálhatjuk a K-Means megvalósításunkba:

Művészek listája = getTop100Artists (); Set topTags = getTop100Tags (); Lista bejegyzések = datasetWithTaggedArtists (előadók, topTags); Térkép klaszterek = KMeans.fit (rekordok, 7, új EuclideanDistance (), 1000); // A fürtkonfigurációs fürtök nyomtatása.forEach ((kulcs, érték) -> {System.out.println ("------------------------- - CLUSTER ---------------------------- "); // A koordináták rendezése a legfontosabb címkék első megtekintéséhez. System.out. println (sortedCentroid (kulcs)); String tagok = String.join (",", value.stream (). map (Record :: getDescription) .collect (toSet ())); System.out.print (tagok); System.out.println (); System.out.println ();});

Ha ezt a kódot futtatjuk, akkor a fürtöket szövegkimenetként jeleníti meg:

------------------------------ CLUSTER ------------------- ---------------- Centroid {klasszikus rock = 65.58333333333333, rock = 64.41666666666667, brit = 20.333333333333332, ...} David Bowie, Led Zeppelin, Pink Floyd, Down of System, Queen , villog-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, a Teremtő, 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, A fekete kulcsok - ---------------------------- CLUSTER --------------------- -------------- Centroid {pop = 81.96428571428571, női énekesek = 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ív = 70.61538461538461, indie rock = 64.46153846153847, ...} Huszonegy pilóta, The Smiths, Firenze + a gép, Kétajtós moziklub, The 1975, Imagine Dragons, The Killers, Vampire Hétvége, Foster the People, The Strokes, Cage the Elephant, Arcade Fire, Arctic Monkeys ------------------------------ CLUSTER - ---------------------------------- Centroid {electronic = 91.6923076923077, House = 39.46153846153846, dance = 38.0, .. .} Charli XCX, The Weeknd, Daft Punk, Calvin Harris, MGMT, Martin Garrix, Depeche Mode, The Chainsmokers, Avicii, Kygo, Marshmello, David Guetta, Lazer őrnagy ------------------------------ CLUSTER ----- ------------------------------ Centroid {rock = 87.38888888888889, alternatív = 72.11111111111111, alternatív rock = 49.16666666, ...} Weezer , A fehér csíkok, a Nirvana, a Foo Fighters, a Maroon 5, az oázis, a pánik! a diszkóban, Gorillaz, Green Day, The Cure, Fall Out Boy, OneRepublic, Paramore, Coldplay, Radiohead, Linkin Park, Red Hot Chili Peppers, Muse

Mivel a centroid koordinációkat az átlagos címke gyakoriság szerint rendezik, az egyes klaszterekben könnyen észrevehetjük a domináns műfajt. Például az utolsó klaszter egy jó öreg rock-zenekar klasztere, vagy a második tele van rapsztárokkal.

Bár ennek a klaszterezésnek van értelme, többnyire nem tökéletes, mivel az adatokat csupán a felhasználói viselkedésből gyűjtik össze.

5. Megjelenítés

Néhány perccel ezelőtt algoritmusunk terminálbarát módon vizualizálta a művészek klaszterét. Ha a fürtkonfigurációnkat JSON-vá konvertáljuk, és a D3.js-be tápláljuk, akkor néhány JavaScript-sorral egy szép emberbarát Radial Tidy-fa lesz:

Át kell alakítanunk Térkép egy hasonló sémájú JSON-hoz, mint ez a d3.js példa.

6. Klaszterek száma

A K-Means egyik alapvető tulajdonsága, hogy előre meg kell határoznunk a klaszterek számát. Eddig a statikus értéket használtuk k, de ennek az értéknek a meghatározása kihívást jelenthet. Két klasszikus módja van a fürtök számításának:

  1. Tartományismeret
  2. Matematikai heurisztika

Ha olyan szerencsénk van, hogy ennyit tudunk a domainről, akkor képesek vagyunk egyszerűen kitalálni a megfelelő számot.Ellenkező esetben alkalmazhatunk néhány heurisztikát, mint például az Elbow Method vagy a Silhouette Method, hogy megértsük a klaszterek számát.

Mielőtt tovább mennénk, tudnunk kell, hogy ezek a heurisztikák, bár hasznosak, csak heurisztikák, és nem biztos, hogy egyértelmű válaszokat adnak.

6.1. Könyök módszer

A könyök módszer alkalmazásához először ki kell számolnunk az egyes klaszter centroidok és az összes tag közötti különbséget. Ahogy több független tagot csoportosítunk egy klaszterbe, a centroid és tagjai közötti távolság növekszik, ezért a klaszter minősége csökken.

A távolság kiszámításának egyik módja a Négyzetbeli hibák összege. A négyzetes hibák vagy az SSE összege megegyezik a centroid és az összes tagja közötti négyzetbeli különbségek összegével:

nyilvános statikus kettős sse (Térkép csoportosítva, Távolság távolság) {kettős összeg = 0; a (Map.Entry bejegyzés: clustered.entrySet ()) {Centroid centroid = entry.getKey (); for (Rekordrekord: entry.getValue ()) {double d = distance.calculate (centroid.getCoordinates (), record.getFeatures ()); összeg + = Math.pow (d, 2); }} visszatérési összeg; }

Azután, futtathatjuk a K-Means algoritmust a kés számítsa ki mindegyikük SSE-jét:

List rekordok = // az adatkészlet; Távolság távolság = új euklideszi távolság (); List sumOfSquaredErrors = new ArrayList (); mert (int k = 2; k <= 16; k ++) {Térkép klaszterek = KMeans.fit (rekordok, k, távolság, 1000); double sse = Errors.sse (fürtök, távolság); sumOfSquaredErrors.add (sse); }

A nap végén lehetséges megtalálni a megfelelőt k az SSE-vel szembeni klaszterek számának megrajzolásával:

Általában a klaszterek számának növekedésével a klasztertagok közötti távolság csökken. Azonban nem választhatunk tetszőleges nagy értékeket k, mivel több, csak egy taggal rendelkező klaszter meghiúsítja a klaszterezés teljes célját.

A könyök módszer ötlete az, hogy megfelelő értéket találjon a k oly módon, hogy az SSE drámaian csökken ezen érték körül. Például, k = 9 jó jelölt lehet itt.

7. Következtetés

Ebben az oktatóanyagban először a gépi tanulás néhány fontos fogalmát ismertettük. Ezután akvintintáltuk a K-Means klaszterező algoritmus mechanikájával. Végül írtunk egy egyszerű megvalósítást a K-Means számára, teszteltük algoritmusunkat a Last.fm valós adataival, és szép grafikus módon vizualizáltuk a fürtözés eredményét.

Szokás szerint a mintakód elérhető a GitHub projektünkön, ezért mindenképpen ellenőrizze!