K-Means Clustering Algorithm i Java

1. Oversigt

Clustering er et paraplyudtryk for en klasse af ikke-overvågede algoritmer at opdage grupper af ting, mennesker eller ideer, der er tæt knyttet til hinanden.

I denne tilsyneladende enkle one-liner-definition så vi et par buzzwords. Hvad er præcis klyngedannelse? Hvad er en ikke-overvåget algoritme?

I denne vejledning skal vi først kaste lys over disse begreber. Derefter ser vi, hvordan de kan manifestere sig i Java.

2. Uovervågede algoritmer

Før vi bruger de fleste indlæringsalgoritmer, skal vi på en eller anden måde give dem nogle eksempler på data og lade algoritmen lære af disse data. I maskinlæring terminologi, vi kalder det eksempler på træningsdata for datasæt. Også, hele processen er kendt som træningsprocessen.

Alligevel, Vi kan klassificere læringsalgoritmer baseret på den mængde tilsyn, de har brug for under træningsprocessen. De to hovedtyper af læringsalgoritmer i denne kategori er:

Overvåget læring: I overvågede algoritmer skal træningsdataene indeholde den aktuelle løsning for hvert punkt. For eksempel, hvis vi er ved at træne vores spamfiltreringsalgoritme, føder vi både prøve-e-mails og deres etiket, dvs. spam eller ikke-spam, til algoritmen. Matematisk set vil vi udlede f (x) fra et træningssæt, der inkluderer begge dele xs og ys.
Uovervåget læring: Når der ikke er nogen mærker i træningsdata, så er algoritmen en ikke-overvåget. For eksempel har vi masser af data om musikere, og vi vil opdage grupper af lignende musikere i dataene.

3. Klyngedannelse

Clustering er en ikke-overvåget algoritme til at opdage grupper af lignende ting, ideer eller mennesker. I modsætning til overvågede algoritmer træner vi ikke klyngealgoritmer med eksempler på kendte etiketter. I stedet forsøger klyngedannelse at finde strukturer i et træningssæt, hvor intet punkt i dataene er etiketten.

3.1. K-betyder klyngedannelse

K-Means er en klyngealgoritme med en grundlæggende egenskab: antallet af klynger er defineret på forhånd. Ud over K-Means er der andre typer klyngealgoritmer som Hierarkisk klyngedannelse, Affinitetsforplantning eller Spektral klyngedannelse.

3.2. Sådan fungerer K-Means

Antag at vores mål er at finde et par lignende grupper i et datasæt som:

K-midler begynder med k tilfældigt placerede centroider. Centroids er, som deres navn antyder, klyngernes centrum. For eksempel tilføjer vi her fire tilfældige centroider:

Derefter tildeler vi hvert eksisterende datapunkt til dets nærmeste centroid:

Efter tildelingen flytter vi centroiderne til den gennemsnitlige placering af point, der er tildelt den. Husk, at centroider formodes at være klyngens centrum:

Den aktuelle iteration afsluttes, hver gang vi er færdige med at flytte centroiderne. Vi gentager disse gentagelser, indtil tildelingen mellem flere på hinanden følgende gentagelser holder op med at ændre sig:

Når algoritmen ophører, findes disse fire klynger som forventet. Nu hvor vi ved, hvordan K-Means fungerer, lad os implementere det i Java.

3.3. Feature Repræsentation

Når vi modellerer forskellige træningsdatasæt, har vi brug for en datastruktur til at repræsentere modelattributter og deres tilsvarende værdier. For eksempel kan en musiker have en genreattribut med en værdi som Rock. Vi bruger normalt udtrykket funktion til at henvise til kombinationen af en attribut og dens værdi.

For at forberede et datasæt til en bestemt indlæringsalgoritme bruger vi normalt et fælles sæt numeriske attributter, der kan bruges til at sammenligne forskellige emner. For eksempel, hvis vi lader vores brugere tagge hver kunstner med en genre, kan vi i slutningen af dagen tælle, hvor mange gange hver kunstner er tagget med en bestemt genre:

Funktionsvektoren for en kunstner som Linkin Park er [rock -> 7890, nu-metal -> 700, alternativ -> 520, pop -> 3]. Så hvis vi kunne finde en måde at repræsentere attributter som numeriske værdier, så kan vi simpelthen sammenligne to forskellige emner, f.eks. kunstnere ved at sammenligne deres tilsvarende vektorindgange.

Da numeriske vektorer er så alsidige datastrukturer, repræsenterer vi funktioner, der bruger dem. Sådan implementerer vi funktionsvektorer i Java:

offentlig klasse Record {private final String description; private endelige kortfunktioner; // konstruktør, getter, toString, er lig med og hashcode}

3.4. Finde lignende emner

I hver iteration af K-midler har vi brug for en måde at finde den nærmeste centroid til hvert element i datasættet. En af de enkleste måder at beregne afstanden mellem to funktionsvektorer er at bruge euklidisk afstand. Den euklidiske afstand mellem to vektorer som f.eks [p1, q1] og [p2, q2] er lig med:

Lad os implementere denne funktion i Java. For det første abstraktionen:

offentlig grænseflade Afstand {dobbelt beregne (kort f1, kort f2); }

Ud over euklidisk afstand, der er andre tilgange til at beregne afstanden eller ligheden mellem forskellige emner som Pearson korrelationskoefficient. Denne abstraktion gør det let at skifte mellem forskellige afstandsmålinger.

Lad os se implementeringen for euklidisk afstand:

offentlig klasse EuclideanDistance implementerer Distance {@ Override offentlig dobbelt beregning (kort f1, kort f2) {dobbelt sum = 0; for (String key: f1.keySet ()) {Double v1 = f1.get (key); Dobbelt v2 = f2.get (nøgle); hvis (v1! = null && v2! = null) {sum + = Math.pow (v1 - v2, 2); }} returner Math.sqrt (sum); }}

Først beregner vi summen af kvadratiske forskelle mellem tilsvarende poster. Derefter ved at anvende sqrt funktion beregner vi den faktiske euklidiske afstand.

3.5. Centroid-repræsentation

Centroids er i samme rum som normale funktioner, så vi kan repræsentere dem svarende til funktioner:

offentlig klasse Centroid {privat endelig Kortkoordinater; // konstruktører, getter, toString, er lig med og hashcode}

Nu hvor vi har et par nødvendige abstraktioner på plads, er det tid til at skrive vores K-Means implementering. Her er et hurtigt kig på vores metodesignatur:

offentlig klasse KMeans {privat statisk endelig Tilfældig tilfældig = ny tilfældig (); offentligt statisk kort fit (Listeoptegnelser, int k, Distance distance, int maxIterations) {// udeladt}}

Lad os nedbryde denne metodesignatur:

Det datasæt er et sæt funktionsvektorer. Da hver funktionsvektor er en Optage, derefter er datasættypen Liste
Det k parameter bestemmer antallet af klynger, som vi skal give på forhånd
afstand indkapsler den måde, vi skal beregne forskellen på to funktioner
K-Means ophører, når opgaven holder op med at ændre sig i nogle få på hinanden følgende gentagelser. Ud over denne opsigelsesbetingelse kan vi også placere en øvre grænse for antallet af iterationer. Det maxIterations argument bestemmer den øvre grænse
Når K-Means ophører, skal hver centroid have et par tildelte funktioner, derfor bruger vi en Kortsom returtype. Dybest set svarer hver kortindgang til en klynge

3.6. Centroid generation

Det første trin er at generere k tilfældigt placerede centroider.

Selvom hver centroid kan indeholde helt tilfældige koordinater, er det en god praksis at generere tilfældige koordinater mellem minimums- og maksimumværdierne for hver attribut. At generere tilfældige centroider uden at overveje rækkevidden af mulige værdier ville få algoritmen til at konvergere langsommere.

Først skal vi beregne minimums- og maksimumsværdien for hver attribut og derefter generere tilfældige værdier mellem hvert par af dem:

privat statisk Liste randomCentroids (List records, int k) {List centroids = new ArrayList (); Kortmaks = ny HashMap (); Kortminer = ny HashMap (); for (Record record: records) {record.getFeatures (). forEach ((key, value) ->); } Indstil attributter = records.stream () .flatMap (e -> e.getFeatures (). KeySet (). Stream ()) .collect (toSet ()); for (int i = 0; i <k; i ++) {Map koordinater = ny HashMap (); for (String attribut: attributter) {dobbelt max = maxs.get (attribut); dobbelt min = min.get (attribut); coordinates.put (attribut, random.nextDouble () * (max - min) + min); } centroids.add (nyt Centroid (koordinater)); } returnere centroider; }

Nu kan vi tildele hver post til en af disse tilfældige centroider.

3.7. Opgave

Først og fremmest, givet en Optage, skal vi finde den centroid, der er tættest på den:

privat statisk Centroid nærmesteCentroid (Record record, List centroids, Distance distance) {dobbelt minimumDistance = Double.MAX_VALUE; Centroid nærmeste = null; for (Centroid centroid: centroids) {double currentDistance = distance.calculate (record.getFeatures (), centroid.getCoordinates ()); hvis (currentDistance <minimumDistance) {minimumDistance = currentDistance; nærmeste = centroid; }} returner nærmest; }

Hver post tilhører sin nærmeste centroid-klynge:

privat statisk ugyldig tildelerToCluster (kort klynger, Record record, Centroid centroid) {clusters.compute (centroid, (key, list) -> {if (list == null) {list = new ArrayList ();} list.add (record); return list;} ); }

3.8. Centroid flytning

Hvis en centroid efter en iteration ikke indeholder nogen opgaver, flytter vi den ikke. Ellers skal vi flytte centroid-koordinaten for hver attribut til den gennemsnitlige placering af alle tildelte poster:

privat statisk Centroid-gennemsnit (Centroid centroid, List records) {if (records == null || recordss.isEmpty ()) {return centroid; } Kortgennemsnit = centroid.getCoordinates (); records.stream (). flatMap (e -> e.getFeatures (). keySet (). stream ()) .forEach (k -> average.put (k, 0.0)); for (Record record: records) {record.getFeatures (). forEach ((k, v) -> average.compute (k, (k1, currentValue) -> v + currentValue)); } gennemsnit.forEach ((k, v) -> gennemsnit.put (k, v / records.størrelse ())); returner nyt Centroid (gennemsnit); }

Da vi kan flytte en enkelt centroid, er det nu muligt at implementere relocateCentroids metode:

privat statisk liste relocateCentroids (kort klynger) {return clusters.entrySet (). stream (). map (e -> average (e.getKey (), e.getValue ())) collect (toList ()); }

Denne enkle en-linie gentager alle centroider, flytter dem og returnerer de nye centroider.

3.9. Samler det hele

Efter at have tildelt alle poster til deres nærmeste centroid, skal vi i hver iteration først sammenligne de aktuelle opgaver med den sidste iteration.

Hvis opgaverne var identiske, afslutter algoritmen. Ellers skal vi flytte centroiderne, inden vi hopper til næste iteration:

offentligt statisk kort fit (List records, int k, Distance distance, int maxIterations) {List centroids = randomCentroids (records, k); Kort klynger = ny HashMap (); Kort lastState = ny HashMap (); // iterate for et foruddefineret antal gange for (int i = 0; i <maxIterations; i ++) {boolean isLastIteration = i == maxIterations - 1; // i hver iteration skal vi finde den nærmeste centroid for hver post for (Record record: records) {Centroid centroid = nærmesteCentroid (record, centroids, distance); assignToCluster (klynger, rekord, centroid); } // hvis opgaverne ikke ændres, afslutter algoritmen boolsk børTerminere = isLastIteration || clusters.equals (lastState); lastState = klynger; if (shouldTerminate) {pause; } // i slutningen af hver iteration skal vi flytte centroids centroids = relocateCentroids (klynger); klynger = ny HashMap (); } returner lastState; }

4. Eksempel: Opdag lignende kunstnere på Last.fm

Last.fm bygger en detaljeret profil af hver brugers musikalske smag ved at optage detaljer om, hvad brugeren lytter til. I dette afsnit finder vi klynger af lignende kunstnere. For at oprette et datasæt, der passer til denne opgave, bruger vi tre API'er fra Last.fm:

API for at få en samling af topkunstnere på Last.fm.
En anden API til at finde populære tags. Hver bruger kan tagge en kunstner med noget, f.eks. klippe. Så Last.fm opretholder en database med disse tags og deres frekvenser.
Og en API til at få de bedste tags til en kunstner, sorteret efter popularitet. Da der er mange sådanne tags, beholder vi kun de tags, der er blandt de øverste globale tags.

4.1. Last.fms API

For at bruge disse API'er skal vi hente en API-nøgle fra Last.fm og sende den i hver HTTP-anmodning. Vi bruger følgende eftermonteringstjeneste til at ringe til disse API'er:

offentlig grænseflade LastFmService {@GET ("/ 2.0 /? method = chart.gettopartists & format = json & limit = 50") Ring til topArtists (@Query ("side") int side); @GET ("/ 2.0 /? Method = artist.gettoptags & format = json & limit = 20 & autocorrect = 1") Ring topTagsFor (@Query ("artist") Stringartner); @GET ("/ 2.0 /? Method = chart.gettoptags & format = json & limit = 100") Ring til topTags (); // Et par DTO'er og en interceptor}

Så lad os finde de mest populære kunstnere på Last.fm:

// opsætning af retrofit-tjenesten privat statisk liste getTop100Artists () kaster IOException {Liste kunstnere = ny ArrayList (); // Henter de to første sider, der hver indeholder 50 poster. for (int i = 1; i <= 2; i ++) {artists.addAll (lastFm.topArtists (i). execute (). body (). all ()); } returnere kunstnere; }

På samme måde kan vi hente de øverste tags:

privat statisk sæt getTop100Tags () kaster IOException {return lastFm.topTags (). execute (). body (). all (); }

Endelig kan vi oprette et datasæt af kunstnere sammen med deres tagfrekvenser:

privat statisk liste datasætWithTaggedArtists (Liste kunstnere, Set topTags) kaster IOException {Liste poster = ny ArrayList (); for (String artist: artists) {Map tags = lastFm.topTagsFor (artist) .execute (). body (). all (); // Opbevar kun populære tags. tags.entrySet (). removeIf (e ->! topTags.contains (e.getKey ())); records.add (ny Record (kunstner, tags)); } returnere poster }

4.2. Forming Artist Clusters

Nu kan vi føde det forberedte datasæt til vores implementering af K-Means:

Liste kunstnere = getTop100Artists (); Set topTags = getTop100Tags (); Liste poster = datasætWithTaggedArtists (kunstnere, topTags); Kort klynger = KMeans.fit (poster, 7, ny EuclideanDistance (), 1000); // Udskrivning af klyngekonfigurationsklynger.forEach ((nøgle, værdi) -> {System.out.println ("------------------------- - CLUSTER ---------------------------- "); // Sortering af koordinaterne for at se de mest betydningsfulde tags først. System.out. println (sortedCentroid (key)); String members = String.join (",", value.stream (). map (Record :: getDescription) .collect (toSet ())); System.out.print (medlemmer); System.out.println (); System.out.println ();});

Hvis vi kører denne kode, vil det visualisere klyngerne som tekstoutput:

------------------------------ CLUSTER ------------------- ---------------- Centroid {klassisk rock = 65.58333333333333, rock = 64.41666666666667, britisk = 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, the Creator, 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 - ---------------------------- KLUSTER --------------------- -------------- Centroid {pop = 81,96428571428571, kvindelige vokalister = 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 ------------ ------------------ KLUSTER ------------------------------- ---- Centroid {indie = 95.23076923076923, alternativ = 70.61538461538461, indie rock = 64.46153846153847, ...} Enogtyve piloter, The Smiths, Florence + the Machine, Two Door Cinema Club, 1975, Imagine Dragons, The Killers, Vampire Weekend, Foster folket, The Strokes, Cage the Elephant, Arcade Fire, Arctic Monkeys ------------------------------ CLUSTER - ---------------------------------- Centroid {elektronisk = 91,6923076923077, Hus = 39,46153846153846, dans = 38,0, .. .} Charli XCX, The Weeknd, Daft Punk, Calvin Harris, MGMT, Martin Garrix, Depeche Mode, Chainsmokers, Avicii, Kygo, Marshmello, David Guetta, Major Lazer ------------------------------ CLUSTER ----- ------------------------------ Centroid {rock = 87.38888888888889, alternativ = 72.11111111111111, alternativ rock = 49.16666666, ...} Weezer , The White Stripes, Nirvana, Foo Fighters, Maroon 5, Oasis, Panic! ved diskoteket, Gorillaz, Green Day, The Cure, Fall Out Boy, OneRepublic, Paramore, Coldplay, Radiohead, Linkin Park, Red Hot Chili Peppers, Muse

Da centroid-koordinationer er sorteret efter den gennemsnitlige tagfrekvens, kan vi let få øje på den dominerende genre i hver klynge. For eksempel er den sidste klynge en klynge af gode gamle rockbands, eller den anden er fyldt med rapstjerner.

Selvom denne gruppering giver mening, er den for det meste ikke perfekt, da dataene kun indsamles fra brugeradfærd.

5. Visualisering

For få øjeblikke siden visualiserede vores algoritme klyngen af kunstnere på en terminalvenlig måde. Hvis vi konverterer vores klyngekonfiguration til JSON og fodrer den til D3.js, så har vi med et par linjer JavaScript et dejligt menneskeligt venligt Radial Tidy-Tree:

Vi er nødt til at konvertere vores Kort til en JSON med et lignende skema som dette d3.js-eksempel.

6. Antal klynger

En af de grundlæggende egenskaber ved K-Means er, at vi på forhånd skal definere antallet af klynger. Indtil videre har vi brugt en statisk værdi til k, men at bestemme denne værdi kan være et udfordrende problem. Der er to almindelige måder at beregne antallet af klynger på:

Domæne viden
Matematiske heuristikker

Hvis vi er heldige nok til, at vi ved så meget om domænet, kan vi måske bare gætte det rigtige nummer.Ellers kan vi anvende et par heuristikker som Elbow Method eller Silhouette Method for at få en fornemmelse af antallet af klynger.

Inden vi går videre, skal vi vide, at disse heuristikker, selvom de er nyttige, kun er heuristik og muligvis ikke giver klare svar.

6.1. Albue metode

For at bruge albue-metoden skal vi først beregne forskellen mellem hver klynge-centroid og alle dens medlemmer. Når vi grupperer flere ikke-relaterede medlemmer i en klynge, stiger afstanden mellem centroid og dens medlemmer, hvorfor klyngekvaliteten falder.

En måde at udføre denne afstandsberegning på er at bruge summen af kvadrerede fejl. Summen af kvadrerede fejl eller SSE er lig med summen af kvadratiske forskelle mellem en centroid og alle dens medlemmer:

offentlig statisk dobbelt sse (kort grupperet, Afstandsafstand) {dobbelt sum = 0; for (Map.Entry post: clustered.entrySet ()) {Centroid centroid = entry.getKey (); for (Record record: entry.getValue ()) {double d = distance.calculate (centroid.getCoordinates (), record.getFeatures ()); sum + = Math.pow (d, 2); }} returneringssum; }

Derefter, vi kan køre K-Means algoritmen for forskellige værdier af kog bereg SSE for hver af dem:

List records = // datasættet; Afstandsafstand = ny EuclideanDistance (); Liste sumOfSquaredErrors = ny ArrayList (); for (int k = 2; k <= 16; k ++) {Kort klynger = KMeans.fit (poster, k, distance, 1000); dobbelt sse = Errors.sse (klynger, afstand); sumOfSquaredErrors.add (sse); }

I slutningen af dagen er det muligt at finde en passende k ved at plotte antallet af klynger mod SSE:

Når antallet af klynger stiger, falder afstanden mellem klyngemedlemmer normalt. Vi kan dog ikke vælge nogen vilkårlige store værdier til k, siden at have flere klynger med kun ét medlem besejrer hele formålet med klynger.

Ideen bag albue-metoden er at finde en passende værdi til k på en måde, at SSE falder dramatisk omkring denne værdi. For eksempel, k = 9 kan være en god kandidat her.

7. Konklusion

I denne vejledning dækkede vi først et par vigtige begreber i Machine Learning. Derefter blev vi vandet med mekanikken i K-Means-klyngealgoritmen. Endelig skrev vi en simpel implementering til K-Means, testede vores algoritme med et reelt datasæt fra Last.fm og visualiserede grupperingsresultatet på en flot grafisk måde.

Som sædvanlig er prøvekoden tilgængelig på vores GitHub-projekt, så sørg for at tjekke det ud!

streamalism.org