streamalism.org

1. Pregled

Klasteriranje je krovni pojam za klasu nenadziranih algoritama otkrijte skupine stvari, ljudi ili ideja koje su usko povezane.

U ovoj naizgled jednostavnoj definiciji s jednom linijom vidjeli smo nekoliko modnih riječi. Što je zapravo klasteriranje? Što je algoritam bez nadzora?

U ovom uputstvu prvo ćemo osvijetliti ove koncepte. Zatim ćemo vidjeti kako se mogu manifestirati na Javi.

2. Algoritmi bez nadzora

Prije nego što upotrijebimo većinu algoritama za učenje, trebali bismo im nekako dostaviti neke uzorke podataka i dopustiti algoritmu da uči iz tih podataka. U terminologiji strojnog učenja, taj uzorak nazivamo podacima o obuci skupa podataka. Također, cijeli proces poznat je kao proces treninga.

U svakom slučaju, možemo klasificirati algoritme učenja na temelju količine nadzora koji im je potreban tijekom procesa treninga. Dvije glavne vrste algoritama učenja u ovoj kategoriji su:

• Nadzirano učenje: U nadziranim algoritmima podaci o treningu trebaju sadržavati stvarno rješenje za svaku točku. Na primjer, ako ćemo trenirati naš algoritam za filtriranje neželjene pošte, algoritmu unosimo i uzorke e-adresa i njihovu oznaku, tj. Neželjenu ili neželjenu poštu. Matematički gledano, zaključit ćemo o f (x) iz seta za obuku koji uključuje oboje xs i god.
• Učenje bez nadzora: Kada u podacima o vježbanju nema oznaka, tada je algoritam nenadgledan. Na primjer, imamo puno podataka o glazbenicima i u podacima ćemo otkriti skupine sličnih glazbenika.

3. Grupiranje

Klasteriranje je nenadgledani algoritam za otkrivanje skupina sličnih stvari, ideja ili ljudi. Za razliku od nadziranih algoritama, mi ne treniramo algoritme klasteriranja na primjerima poznatih oznaka. Umjesto toga, klasteriranje pokušava pronaći strukture unutar skupa treninga gdje niti jedna točka podataka nije oznaka.

3.1. K-znači klasteriranje

K-Means je algoritam klasterizacije s jednim temeljnim svojstvom: broj klastera je unaprijed definiran. Uz K-sredstva, postoje i druge vrste algoritama klasteriranja poput hijerarhijskog klasteriranja, širenja afiniteta ili spektralnog klasteriranja.

3.2. Kako K-Means djeluje

Pretpostavimo da je naš cilj pronaći nekoliko sličnih grupa u skupu podataka poput:

K-znači započinje s k nasumično postavljenih centroida. Centroidi su, kako im samo ime govori, središnje točke nakupina. Na primjer, ovdje dodajemo četiri slučajna centroida:

Zatim dodijelimo svaku postojeću podatkovnu točku njenom najbližem centroidu:

Nakon dodjele centroide premještamo na prosječno mjesto dodijeljenih točaka. Zapamtite, centroidi bi trebali biti središnje točke nakupina:

Trenutna iteracija završava svaki put kad završimo s premještanjem centroida. Ponavljamo ove ponavljanja sve dok se dodjeljivanje između više uzastopnih ponavljanja ne prestane mijenjati:

Kad se algoritam završi, te četiri skupine nalaze se prema očekivanjima. Sad kad znamo kako K-Means radi, primijenimo ga na Javi.

3.3. Zastupljenost obilježja

Pri modeliranju različitih skupova podataka za obuku trebamo strukturu podataka koja će predstavljati atribute modela i njihove odgovarajuće vrijednosti. Na primjer, glazbenik može imati žanrovski atribut s vrijednošću poput Rock. Pojam značajka obično koristimo za označavanje kombinacije atributa i njegove vrijednosti.

Da bismo pripremili skup podataka za određeni algoritam učenja, obično koristimo zajednički skup numeričkih atributa koji se mogu koristiti za usporedbu različitih stavki. Na primjer, ako dopustimo našim korisnicima da označe svakog umjetnika žanrom, na kraju dana možemo izbrojati koliko je puta svaki umjetnik označen određenim žanrom:

Značajni vektor za umjetnika poput Linkin Parka je [rock -> 7890, nu-metal -> 700, alternativa -> 520, pop -> 3]. Dakle, ako bismo mogli pronaći način da atribute prikažemo kao numeričke vrijednosti, onda jednostavno možemo usporediti dvije različite stavke, na pr. umjetnika, uspoređujući njihove odgovarajuće vektorske unose.

Budući da su numerički vektori tako svestrane strukture podataka, predstavit ćemo značajke pomoću njih. Evo kako implementiramo vektore značajki u Javi:

zapis javne klase {privatni konačni Opis niza; privatne konačne značajke karte; // konstruktor, getter, toString, jednako i hashcode}

3.4. Pronalaženje sličnih predmeta

U svakoj iteraciji K-značenja potreban nam je način da pronađemo najbliži centroid svakoj stavci u skupu podataka. Jedan od najjednostavnijih načina izračuna udaljenosti između dva značajna vektora je upotreba euklidske udaljenosti. Euklidska udaljenost između dva vektora poput [p1, q1] i [p2, q2] jednako je:

Primijenimo ovu funkciju u Javi. Prvo, apstrakcija:

javno sučelje Udaljenost {dvostruko izračunaj (karta f1, karta f2); }

Pored euklidske udaljenosti, postoje i drugi pristupi za izračunavanje udaljenosti ili sličnosti između različitih stavki poput Pearsonovog koeficijenta korelacije. Ova apstrakcija olakšava prebacivanje između različitih mjerila udaljenosti.

Pogledajmo primjenu za euklidsku udaljenost:

javna klasa EuclideanDistance provodi Udaljenost {@Preuzmi javni dvostruki izračun (karta f1, karta f2) {dvostruka suma = 0; for (String key: f1.keySet ()) {Double v1 = f1.get (key); Dvostruko v2 = f2.get (ključ); if (v1! = null && v2! = null) {sum + = Math.pow (v1 - v2, 2); }} return Math.sqrt (zbroj); }}

Prvo izračunavamo zbroj kvadrata razlika između odgovarajućih unosa. Zatim, primjenom sqrt funkcija, izračunavamo stvarnu euklidsku udaljenost.

3.5. Prikaz Centroida

Centroidi se nalaze u istom prostoru kao i normalne značajke, tako da ih možemo predstaviti slične značajkama:

javna klasa Centroid {privatni konačni koordinate karte; // konstruktori, getter, toString, equals i hashcode}

Sad kad imamo nekoliko potrebnih apstrakcija, vrijeme je da napišemo našu K-Means implementaciju. Evo kratkog pogleda na potpis naše metode:

javna klasa KMeans {privatni statički konačni Random random = novi Random (); javna statička karta fit (popis zapisa, int k, udaljenost udaljenosti, int maxIteracije) {// izostavljeno}}

Razdvojimo potpis ove metode:

• The skup podataka je skup vektora obilježja. Budući da je svaki vektor obilježja a Snimiti, tada je vrsta skupa podataka Popis
• The k parametar određuje broj klastera, koji bismo trebali osigurati unaprijed
• udaljenost enkapsulira način na koji ćemo izračunati razliku između dviju značajki
• K-Means prestaje kad se dodjeljivanje prestane mijenjati nekoliko uzastopnih ponavljanja. Uz ovaj uvjet prekida, možemo postaviti i gornju granicu za broj ponavljanja. The maxIteracije argument određuje gornju granicu
• Kad se K-Means završi, svaki centroid trebao bi imati nekoliko dodijeljenih značajki, stoga koristimo Kartakao povratni tip. U osnovi, svaki unos karte odgovara grupi

3.6. Generacija centroida

Prvi korak je generiranje k nasumično postavljeni centroidi.

Iako svaki centroid može sadržavati potpuno slučajne koordinate, dobra je praksa generirati slučajne koordinate između minimalne i maksimalne moguće vrijednosti za svaki atribut. Generiranje slučajnih centroida bez razmatranja raspona mogućih vrijednosti uzrokovalo bi sporije konvergiranje algoritma.

Prvo bismo trebali izračunati minimalnu i maksimalnu vrijednost za svaki atribut, a zatim generirati slučajne vrijednosti između svakog njihova para:

privatni statički popis randomCentroids (Popis zapisa, int k) {Centroids popisa = novi ArrayList (); Maksi mape = novi HashMap (); Karte min = nova HashMap (); for (Record record: records) {record.getFeatures (). forEach ((key, value) ->); } Postavi atribute = zapise.stream () .flatMap (e -> e.getFeatures (). KeySet (). Stream ()) .collect (toSet ()); za (int i = 0; i <k; i ++) {Koordinate mape = novo HashMap (); for (Atribut niza: atributi) {double max = maxs.get (atribut); dvostruko min = mins.get (atribut); koordinate.put (atribut, random.nextDouble () * (max - min) + min); } centroids.add (novi Centroid (koordinate)); } povratni centroidi; }

Sada svaki zapis možemo dodijeliti jednom od ovih slučajnih centroida.

3.7. Zadatak

Prvo, s obzirom na a Snimiti, trebali bismo pronaći najbliži centroid:

privatni statički Centroid najbližiCentroid (zapis zapisa, popis centroida, udaljenost udaljenosti) {double minimumDistance = Double.MAX_VALUE; Centroid najbliži = null; za (Centroid centroid: centroids) {double currentDistance = distance.calculate (record.getFeatures (), centroid.getCoordinate ()); if (currentDistance <minimumDistance) {minimumDistance = currentDistance; najbliži = centroid; }} povratak najbliži; }

Svaki zapis pripada svom najbližem centroidnom skupu:

privatna statička praznina assignToCluster (Map klasteri, zapis zapisa, Centroid centroid) {clusters.compute (centroid, (ključ, popis) -> {if (list == null) {list = new ArrayList ();} list.add (record); return list;} ); }

3.8. Premještanje centroida

Ako nakon jedne iteracije centroid ne sadrži zadatke, nećemo ga premjestiti. U suprotnom, trebali bismo premjestiti koordintu centroida za svaki atribut na prosječno mjesto svih dodijeljenih zapisa:

privatni statički prosjek Centroid (Centroid centroid, Popis zapisa) {if (records == null || recordss.isEmpty ()) {return centroid; } Prosjek karte = centroid.getCoordinate (); records.stream (). flatMap (e -> e.getFeatures (). keySet (). stream ()) .forEach (k -> prosjek.put (k, 0,0)); for (Record record: records) {record.getFeatures (). forEach ((k, v) -> average.compute (k, (k1, currentValue) -> v + currentValue)); } prosjek.zaEach ((k, v) -> prosjek.put (k, v / records.size ())); vrati novi Centroid (prosjek); }

Budući da možemo premjestiti jedan centroid, sada je moguće implementirati premjestitiCentroids metoda:

privatni statički popis relocateCentroids (Map klasteri) {return clusters.entrySet (). stream (). map (e -> prosjek (e.getKey (), e.getValue ())). collect (toList ()); }

Ova jednostavna jednoslojna linija prolazi kroz sve centroide, premješta ih i vraća nove centroide.

3.9. Sve to zajedno

U svakoj iteraciji, nakon dodjele svih zapisa najbližem centroidu, prvo bismo trebali usporediti trenutne zadatke s posljednjom iteracijom.

Ako su zadaci identični, algoritam se prekida. Inače, prije skoka na sljedeću iteraciju, trebali bismo premjestiti centroide:

javna statička karta fit (Popis zapisa, int k, Udaljenost udaljenosti, int maxIteracije) {Popis centroids = randomCentroids (zapisi, k); Karta klasteri = novi HashMap (); Karta lastState = nova HashMap (); // ponavljanje unaprijed definiranog broja puta za (int i = 0; i <maxIterations; i ++) {boolean isLastIteration = i == maxIterations - 1; // u svakoj iteraciji trebali bismo pronaći najbliži centroid za svaki zapis za (Record record: records) {Centroid centroid = najbližiCentroid (zapis, centroidi, udaljenost); assignToCluster (klasteri, zapis, centroid); } // ako se dodjele ne promijene, tada algoritam završava boolean shouldTerminate = isLastIteration || klasteri.equals (lastState); lastState = klasteri; if (shouldTerminate) {break; } // na kraju svake iteracije trebali bismo premjestiti centroids centroids = relocateCentroids (nakupine); klasteri = novi HashMap (); } return lastState; }

4. Primjer: Otkrivanje sličnih umjetnika na Last.fm

Last.fm gradi detaljan profil glazbenog ukusa svakog korisnika bilježeći detalje onoga što korisnik sluša. U ovom ćemo odjeljku pronaći skupine sličnih umjetnika. Za izgradnju skupa podataka prikladnog za ovaj zadatak koristit ćemo tri API-ja iz Last.fm:

1. API za dobivanje kolekcije vrhunskih umjetnika na Last.fm.
2. Još jedan API za pronalaženje popularnih oznaka. Svaki korisnik može umjetnika nečim označiti, npr. stijena. Dakle, Last.fm održava bazu podataka o tim oznakama i njihovim frekvencijama.
3. I API za dobivanje glavnih oznaka za umjetnika, poredanih prema popularnosti. Budući da takvih oznaka ima mnogo, zadržat ćemo samo one oznake koje su među glavnim globalnim oznakama.

4.1. API Last.fm-a

Da bismo koristili ove API-je, trebali bismo dobiti API ključ od Last.fm-a i poslati ga u svaki HTTP zahtjev. Za pozivanje tih API-ja koristit ćemo sljedeću uslugu nadogradnje:

javno sučelje LastFmService {@GET ("/ 2.0 /? method = chart.gettopartists & format = json & limit = 50") Pozovite topArtists (@Query ("page") int page); @GET ("/ 2.0 /? Method = artist.gettoptags & format = json & limit = 20 & autocorrect = 1") Pozovite topTagsFor (@Query ("artist") String artist); @GET ("/ 2.0 /? Method = chart.gettoptags & format = json & limit = 100") Pozovite topTags (); // Nekoliko DTO-a i jedan presretač}

Pa, pronađimo najpopularnije izvođače na Last.fm:

// postavljanje privatnog statičkog popisa usluge Retrofit getTop100Artists () baca IOException {Popis izvođača = novi ArrayList (); // Dohvaćanje prve dvije stranice, od kojih svaka sadrži 50 zapisa. for (int i = 1; i <= 2; i ++) {artists.addAll (lastFm.topArtists (i) .execute (). body (). all ()); } povratak umjetnika; }

Slično tome, možemo dohvatiti gornje oznake:

privatni statički set getTop100Tags () baca IOException {return lastFm.topTags (). izvršiti (). body (). all (); }

Napokon, možemo stvoriti skup umjetnika zajedno s njihovim frekvencijama oznaka:

privatni statički popis podatakaWithTaggedArtists (Popis izvođača, Postavi gornje oznake) baca IOException {Popis zapisa = novi ArrayList (); for (String artist: artists) {Oznake karte = lastFm.topTagsFor (artist) .execute (). body (). all (); // Zadržite samo popularne oznake. tags.entrySet (). removeIf (e ->! topTags.contens (e.getKey ())); records.add (novi Record (izvođač, oznake)); } povrat podataka; }

4.2. Formiranje klastera umjetnika

Sada pripremljeni skup podataka možemo uvesti u našu implementaciju K-Means-a:

Popis izvođača = getTop100Artists (); Postavi topTags = getTop100Tags (); Popis zapisa = skup podatakaWithTaggedArtists (umjetnici, topTagovi); Karta klasteri = KMeans.fit (zapisi, 7, novo EuclideanDistance (), 1000); // Ispis klastera za konfiguraciju klastera.forEach ((ključ, vrijednost) -> {System.out.println ("------------------------- - CLUSTER ---------------------------- "); // Sortiranje koordinata kako bi se prvo vidjele najznačajnije oznake. System.out. println (sortedCentroid (ključ)); Članovi niza = String.join (",", value.stream (). map (Record :: getDescription) .collect (toSet ())); System.out.print (members); System.out.println (); System.out.println ();});

Ako pokrenemo ovaj kod, on bi vizualizirao klastere kao izlaz teksta:

------------------------------ KLASTERA ------------------- ---------------- Centroid {klasični rock = 65,58333333333333, rock = 64,41666666666667, british = 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 ---------------------------- - KLASTER ----------------------------------- 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, Creator, Eminem, Frank Ocean, Kendrick Lamar, Nicki Minaj , Drake ------------------------------ KLASTER ----------------- ------------------ Centroid {indie rock = 54,0, rock = 52,0, Psychedelic Rock = 51,0, psychedelic = 47,0, ...} Tame Impala, The Black Keys - ---------------------------- KLASTERA --------------------- -------------- Centroid {pop = 81.96428571428571, vokalistice = 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 ------------ ------------------ KLASTERA ------------------------------- ---- Centroid {indie = 95.23076923076923, alternative = 70.61538461538461, indie rock = 64.46153846153847, ...} Dvadeset jedan pilot, The Smiths, Florence + the Machine, Kino klub s dva vrata, 1975, Imagine Dragons, The Killers, Vampire Vikend, udomite ljude, udari, slon u kavezu, arkadna vatra, arktički majmuni ------------------------------ KLASTER - ---------------------------------- Centroid {elektronički = 91.6923076923077, Kuća = 39.46153846153846, ples = 38.0, .. .} Charli XCX, The Weeknd, Daft Punk, Calvin Harris, MGMT, Martin Garrix, Depeche Mode, Chainsmokers, Avicii, Kygo, Marshmello, David Guetta, Major Lazer ------------------------------ KLASTER ----- ------------------------------ Centroid {rock = 87.38888888888889, alternative = 72.11111111111111, alternative rock = 49.16666666, ...} Weezer , Bijele pruge, Nirvana, Foo Fighters, Maroon 5, Oasis, Panic! u diskoteci, Gorillaz, Green Day, The Cure, Fall Out Boy, OneRepublic, Paramore, Coldplay, Radiohead, Linkin Park, Red Hot Chili Peppers, Muse

Budući da su koordinacije centroida poredane prema prosječnoj učestalosti oznaka, lako možemo uočiti dominantni žanr u svakom klasteru. Na primjer, posljednji klaster je nakupina starih dobrih rock-bendova, ili je drugi ispunjen rap zvijezdama.

Iako ovo grupiranje ima smisla, većinom nije savršeno jer se podaci prikupljaju samo iz ponašanja korisnika.

5. Vizualizacija

Prije nekoliko trenutaka, naš algoritam vizualizirao je skup umjetnika na terminal-friendly način. Ako pretvorimo našu konfiguraciju klastera u JSON i uvedemo je u D3.js, tada ćemo s nekoliko redaka JavaScript-a dobiti lijepo radijalno uredno drvce prilagođeno čovjeku:

Moramo pretvoriti naše Karta u JSON sa sličnom shemom poput ovog primjera d3.js.

6. Broj klastera

Jedno od temeljnih svojstava K-sredstva je činjenica da bismo trebali unaprijed definirati broj klastera. Do sada smo koristili statičku vrijednost za k, ali određivanje ove vrijednosti može biti izazovni problem. Postoje dva uobičajena načina za izračunavanje broja klastera:

1. Poznavanje domene
2. Matematička heuristika

Ako imamo dovoljno sreće da znamo toliko puno o domeni, tada bismo mogli jednostavno pogoditi pravi broj.Inače, možemo primijeniti nekoliko heurističkih metoda poput metode lakta ili metode siluete da bismo stekli uvid u broj skupina.

Prije nego što nastavimo dalje, trebali bismo znati da su ove heuristike, iako korisne, samo heuristike i možda neće pružiti jasne odgovore.

6.1. Metoda lakta

Da bismo koristili metodu lakta, prvo bismo trebali izračunati razliku između svakog centroida nakupine i svih njegovih članova. Kako grupiramo više nepovezanih članova u nakupinu, udaljenost između centroida i njegovih članova raste, stoga kvaliteta klastera opada.

Jedan od načina za izvođenje ovog izračuna udaljenosti je upotreba zbroja kvadrata pogrešaka. Zbroj kvadrata pogrešaka ili SSE jednak je zbroju kvadrata razlika između centroida i svih njegovih članova:

javni statični dvostruki sse (karta skupljeno, Udaljenost udaljenosti) {dvostruka suma = 0; za (Map.Entry entry: clustered.entrySet ()) {Centroid centroid = entry.getKey (); for (Record record: entry.getValue ()) {double d = distance.calculate (centroid.getCoordinate (), record.getFeatures ()); zbroj + = Math.pow (d, 2); }} povratna suma; }

Zatim, možemo pokrenuti K-Means algoritam za različite vrijednosti ki izračunajte SSE za svakog od njih:

Popis zapisa = // skup podataka; Udaljenost udaljenosti = novo EuclideanDistance (); Popis sumOfSquaredErrors = novi ArrayList (); za (int k = 2; k <= 16; k ++) {Karta klasteri = KMeans.fit (zapisi, k, udaljenost, 1000); double sse = Pogreške.sse (klasteri, udaljenost); sumOfSquaredErrors.add (sse); }

Na kraju dana moguće je pronaći odgovarajuće k crtanjem broja klastera prema SSE:

Kako se broj klastera povećava, udaljenost između članova klastera opada. Međutim, ne možemo odabrati bilo koje proizvoljne velike vrijednosti za k, budući da posjedovanje više klastera sa samo jednim članom pobjeđuje cijelu svrhu klastera.

Ideja iza metode lakta je pronaći odgovarajuću vrijednost za k na način da se SSE dramatično smanjuje oko te vrijednosti. Na primjer, k = 9 ovdje može biti dobar kandidat.

7. Zaključak

U ovom smo tutorijalu prvo obradili nekoliko važnih koncepata strojnog učenja. Tada smo se upoznali s mehanikom algoritma klasteriranja K-Means. Na kraju, napisali smo jednostavnu implementaciju za K-Means, testirali svoj algoritam sa stvarnim podacima iz Last.fm-a i vizualizirali rezultat klasterizacije na lijep grafički način.

Kao i obično, uzorak koda dostupan je na našem GitHub projektu, zato ga provjerite!