streamalism.org

1. Oversikt

Klynging er et paraplybegrep for en klasse uten tilsyn med algoritmer å oppdage grupper av ting, mennesker eller ideer som er nært knyttet til hverandre.

I denne tilsynelatende enkle definisjonen av en linje, så vi noen få buzzwords. Hva er egentlig klynging? Hva er en algoritme uten tilsyn?

I denne opplæringen skal vi først kaste lys over disse konseptene. Så får vi se hvordan de kan manifestere seg i Java.

2. Uovervåket algoritmer

Før vi bruker de fleste læringsalgoritmer, bør vi på en eller annen måte mate noen eksempeldata til dem og la algoritmen lære av disse dataene. I maskinlæring terminologi, vi kaller det eksempler på treningsdata for datasett. Også, hele prosessen er kjent som treningsprosessen.

Uansett, vi kan klassifisere læringsalgoritmer basert på hvor mye tilsyn de trenger under opplæringsprosessen. De to hovedtyper av læringsalgoritmer i denne kategorien er:

• Veiledet læring: I overvåkede algoritmer bør treningsdataene inneholde den faktiske løsningen for hvert punkt. For eksempel, hvis vi er i ferd med å trene spamfiltreringsalgoritmen vår, tilfører vi både eksemplene på e-post og deres etikett, dvs. spam eller ikke-spam, til algoritmen. Matematisk sett kommer vi til å utlede f (x) fra et treningssett med begge deler xs og ys.
• Uovervåket læring: Når det ikke er noen etiketter i treningsdata, så er algoritmen en uten tilsyn. For eksempel har vi mange data om musikere, og vi skal oppdage grupper av lignende musikere i dataene.

3. Klynging

Clustering er en ikke-overvåket algoritme for å oppdage grupper av lignende ting, ideer eller mennesker. I motsetning til algoritmer som overvåkes, trener vi ikke grupperingsalgoritmer med eksempler på kjente etiketter. I stedet prøver klynger å finne strukturer i et treningssett der ingen poeng med dataene er merkelappen.

3.1. K-Means Clustering

K-Means er en klyngealgoritme med en grunnleggende egenskap: antall klynger er definert på forhånd. I tillegg til K-Means er det andre typer klyngealgoritmer som Hierarkisk klynging, Affinitetsforplantning eller Spektral klynging.

3.2. Hvordan K-Means fungerer

Anta at målet vårt er å finne noen få lignende grupper i et datasett som:

K-Means begynner med k tilfeldig plasserte sentroider. Centroids er, som navnet antyder, midtpunktene i klyngene. For eksempel, her legger vi til fire tilfeldige sentroider:

Deretter tilordner vi hvert eksisterende datapunkt til nærmeste sentrum:

Etter oppgaven flytter vi sentroidene til den gjennomsnittlige plasseringen av poeng som er tildelt den. Husk at sentroider skal være midtpunktene for klynger:

Den nåværende iterasjonen avsluttes hver gang vi er ferdig med å flytte sentroidene. Vi gjentar disse gjentakelsene til oppgaven mellom flere påfølgende gjentakelser slutter å endres:

Når algoritmen avsluttes, blir disse fire klyngene funnet som forventet. Nå som vi vet hvordan K-Means fungerer, la oss implementere det i Java.

3.3. Feature Representasjon

Når vi modellerer forskjellige treningsdatasett, trenger vi en datastruktur for å representere modellattributter og deres tilsvarende verdier. For eksempel kan en musiker ha et sjangerattributt med en verdi som Rock. Vi bruker vanligvis begrepet funksjon for å referere til kombinasjonen av et attributt og dets verdi.

For å forberede et datasett for en bestemt læringsalgoritme bruker vi vanligvis et vanlig sett med numeriske attributter som kan brukes til å sammenligne forskjellige elementer. For eksempel, hvis vi lar brukerne våre merke hver artist med en sjanger, kan vi på slutten av dagen telle hvor mange ganger hver artist er merket med en bestemt sjanger:

Funksjonsvektoren for en artist som Linkin Park er [rock -> 7890, nu-metal -> 700, alternativ -> 520, pop -> 3]. Så hvis vi kunne finne en måte å representere attributter som numeriske verdier, kan vi ganske enkelt sammenligne to forskjellige elementer, f.eks. kunstnere, ved å sammenligne deres tilsvarende vektoroppføringer.

Siden numeriske vektorer er så allsidige datastrukturer, skal vi representere funksjoner som bruker dem. Slik implementerer vi funksjonsvektorer i Java:

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

3.4. Finne lignende gjenstander

I hver iterasjon av K-Means trenger vi en måte å finne nærmeste sentrum for hvert element i datasettet. En av de enkleste måtene å beregne avstanden mellom to funksjonsvektorer er å bruke euklidisk avstand. Den euklidiske avstanden mellom to vektorer som [p1, q1] og [p2, q2] er lik:

La oss implementere denne funksjonen i Java. For det første abstraksjonen:

offentlig grensesnitt Avstand {dobbel beregne (Kart f1, Kart f2); }

I tillegg til euklidisk avstand, det er andre tilnærminger for å beregne avstanden eller likheten mellom forskjellige elementer som Pearson korrelasjonskoeffisient. Denne abstraksjonen gjør det enkelt å bytte mellom forskjellige avstandsmetoder.

La oss se implementeringen for euklidisk avstand:

offentlig klasse EuclideanDistance implementerer Distance {@Override public double double (Map f1, Map f2) {double sum = 0; for (strengnøkkel: f1.keySet ()) {Dobbel v1 = f1.get (nøkkel); Dobbelt v2 = f2.get (nøkkel); hvis (v1! = null && v2! = null) {sum + = Math.pow (v1 - v2, 2); }} returner Math.sqrt (sum); }}

Først beregner vi summen av kvadratiske forskjeller mellom tilsvarende oppføringer. Deretter, ved å bruke sqrt funksjon beregner vi den faktiske euklidiske avstanden.

3.5. Centroid Representasjon

Centroids er i samme rom som normale funksjoner, så vi kan representere dem som funksjoner:

offentlig klasse Centroid {privat finale Kartkoordinater; // konstruktører, getter, toString, er lik og hashcode}

Nå som vi har noen få nødvendige abstraksjoner på plass, er det på tide å skrive vår K-Means-implementering. Her er en rask titt på metodesignaturen vår:

offentlig klasse KMeans {privat statisk slutt Tilfeldig tilfeldig = ny Tilfeldig (); offentlig statisk kart passe (listeoppføringer, int k, avstandsavstand, int maxIterations) {// utelatt}}

La oss bryte ned denne metodesignaturen:

• De datasett er et sett med funksjonsvektorer. Siden hver funksjonsvektor er en Ta opp, så er datasettypen Liste
• De k parameter bestemmer antall klynger, som vi skal oppgi på forhånd
• avstand innkapsler måten vi skal beregne forskjellen på to funksjoner
• K-Means avsluttes når oppgaven slutter å endres i noen påfølgende iterasjoner. I tillegg til denne avslutningsbetingelsen, kan vi også plassere en øvre grense for antall iterasjoner. De maksIterasjoner argument bestemmer den øvre grensen
• Når K-Means avsluttes, bør hver centroid ha noen få tildelte funksjoner, derfor bruker vi en Kartsom returtype. I utgangspunktet tilsvarer hver kartoppføring en klynge

3.6. Centroid Generation

Det første trinnet er å generere k tilfeldig plasserte sentroider.

Selv om hver centroid kan inneholde helt tilfeldige koordinater, er det en god praksis å generere tilfeldige koordinater mellom minimums- og maksimumsverdiene for hvert attributt. Å generere tilfeldige sentroider uten å vurdere rekkevidden av mulige verdier vil føre til at algoritmen konvergerer saktere.

Først skal vi beregne minimums- og maksimumsverdien for hvert attributt, og deretter generere tilfeldige verdier mellom hvert par av dem:

private static List randomCentroids (List records, int k) {List centroids = new ArrayList (); Kartmaks = ny HashMap (); Kartminer = ny HashMap (); for (Record record: records) {record.getFeatures (). forEach ((key, value) ->); } Sett attributter = records.stream () .flatMap (e -> e.getFeatures (). KeySet (). Stream ()) .collect (toSet ()); for (int i = 0; i <k; i ++) {Map coordinates = new HashMap (); for (String attribute: attributes) {double max = maxs.get (attribute); dobbel min = mins.get (attributt); coordinates.put (attributt, random.nextDouble () * (maks - min) + min); } centroids.add (nye Centroid (koordinater)); } returnere sentroider; }

Nå kan vi tildele hver post til en av disse tilfeldige sentroidene.

3.7. Oppdrag

Først av, gitt en Ta opp, burde vi finne den midtre midten av den:

privat statisk Centroid nærmesteCentroid (Record record, List centroids, Distance distance) {double 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 ugyldighet tilordneToCluster (Map klynger, Record record, Centroid centroid) {clusters.compute (centroid, (key, list) -> {if (list == null) {list = new ArrayList ();} list.add (record); return list;} ); }

3.8. Flytting av Centroid

Hvis en centroid ikke inneholder noen oppgaver etter en iterasjon, flytter vi den ikke. Ellers bør vi flytte sentroid-koordinaten for hvert attributt til den gjennomsnittlige plasseringen av alle tildelte poster:

privat statisk Centroid-gjennomsnitt (Centroid centroid, List records) {if (records == null || recordss.isEmpty ()) {return centroid; } Kartgjennomsnitt = 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)); } gjennomsnitt.forEach ((k, v) -> gjennomsnittlig.put (k, v / records.størrelse ())); returnere nye Centroid (gjennomsnitt); }

Siden vi kan flytte en enkelt centroid, er det nå mulig å implementere relocateCentroids metode:

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

Denne enkle enlinjen går gjennom alle sentroider, flytter dem og returnerer de nye sentroidene.

3.9. Sette alt sammen

I hver iterasjon, etter å ha tilordnet alle poster til nærmeste sentroid, bør vi først sammenligne gjeldende oppdrag med den siste iterasjonen.

Hvis oppgavene var identiske, avsluttes algoritmen. Ellers, før vi hopper til neste iterasjon, bør vi flytte sentroidene:

offentlig statisk kart fit (List records, int k, Distance distance, int maxIterations) {List centroids = randomCentroids (records, k); Kart klynger = ny HashMap (); Kart lastState = ny HashMap (); // iterere for et forhåndsdefinert antall ganger for (int i = 0; i <maxIterations; i ++) {boolean isLastIteration = i == maxIterations - 1; // i hver iterasjon bør vi finne nærmeste centroid for hver post for (Record record: records) {Centroid centroid = nærmesteCentroid (record, centroids, distance); assignToCluster (klynger, post, sentroid); } // hvis oppgavene ikke endres, så avslutter algoritmen boolsk børTerminate = isLastIteration || clusters.equals (lastState); lastState = klynger; if (shouldTerminate) {pause; } // på slutten av hver iterasjon bør vi flytte sentroids centroids = relocateCentroids (klynger); klynger = ny HashMap (); } returner lastState; }

4. Eksempel: Oppdage lignende artister på Last.fm

Last.fm bygger en detaljert profil av hver brukers musikalske smak ved å registrere detaljer om hva brukeren lytter til. I denne delen skal vi finne klynger av lignende artister. For å bygge et datasett som er passende for denne oppgaven, bruker vi tre APIer fra Last.fm:

1. API for å få en samling toppartister på Last.fm.
2. En annen API for å finne populære koder. Hver bruker kan merke en artist med noe, f.eks. stein. Så, Last.fm har en database med disse kodene og deres frekvenser.
3. Og et API for å få de beste kodene for en artist, sortert etter popularitet. Siden det er mange slike koder, vil vi bare beholde de kodene som er blant de beste globale kodene.

4.1. Last.fms API

For å bruke disse API-ene, bør vi få en API-nøkkel fra Last.fm og sende den i hver HTTP-forespørsel. Vi skal bruke følgende ettermonteringstjeneste for å ringe disse API-ene:

offentlig grensesnitt LastFmService {@GET ("/ 2.0 /? method = chart.gettopartists & format = json & limit = 50") Ring topArtists (@Query ("side") int side); @GET ("/ 2.0 /? Method = artist.gettoptags & format = json & limit = 20 & autocorrect = 1") Ring topTagsFor (@Query ("artist") Stringartist); @GET ("/ 2.0 /? Method = chart.gettoptags & format = json & limit = 100") Ring topTags (); // Noen DTO og en avlytter}

Så la oss finne de mest populære artistene på Last.fm:

// sette opp retrofit-tjenesten privat statisk liste getTop100Artists () kaster IOException {List artister = ny ArrayList (); // Henter de to første sidene, som hver inneholder 50 poster. for (int i = 1; i <= 2; i ++) {artists.addAll (lastFm.topArtists (i) .execute (). body (). all ()); } returnere artister; }

På samme måte kan vi hente de øverste kodene:

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

Til slutt kan vi bygge et datasett med artister sammen med deres tagfrekvenser:

privat statisk liste datasettWithTaggedArtists (List artister, Set topTags) kaster IOException {List records = new ArrayList (); for (Stringartist: artister) {Map tags = lastFm.topTagsFor (artist) .execute (). body (). all (); // Bare hold populære koder. tags.entrySet (). removeIf (e ->! topTags.contains (e.getKey ())); records.add (ny Record (artist, tags)); } returnere poster; }

4.2. Forming Artist Clusters

Nå kan vi mate det forberedte datasettet til implementeringen av K-Means:

Liste artister = getTop100Artists (); Set topTags = getTop100Tags (); Liste poster = datasettWithTaggedArtists (artister, topTags); Kart klynger = KMeans.fit (poster, 7, nye EuclideanDistance (), 1000); // Skrive ut klyngekonfigurasjonsklyngene.forEach ((nøkkel, verdi) -> {System.out.println ("------------------------- - CLUSTER ---------------------------- "); // Sortering av koordinatene for å se de viktigste kodene først. System.out. println (sortedCentroid (key)); String members = String.join (",", value.stream (). map (Record :: getDescription) .collect (toSet ())); System.out.print (members); System.out.println (); System.out.println ();});

Hvis vi kjører denne koden, vil den visualisere klyngene som tekstutdata:

------------------------------ CLUSTER ------------------- ---------------- Centroid {classic 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 - ---------------------------- CLUSTER --------------------- -------------- Centroid {pop = 81,96428571428571, kvinnelige 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, indierock = 64.46153846153847, ...} Twenty One Pilots, The Smiths, Florence + the Machine, Two Door Cinema Club, The 1975, Imagine Dragons, The Killers, Vampire Weekend, Foster the People, 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, The 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! på Disco, Gorillaz, Green Day, The Cure, Fall Out Boy, OneRepublic, Paramore, Coldplay, Radiohead, Linkin Park, Red Hot Chili Peppers, Muse

Siden centroid-koordinasjoner er sortert etter den gjennomsnittlige tagfrekvensen, kan vi enkelt se den dominerende sjangeren i hver klynge. For eksempel er den siste klyngen en klynge av gode gamle rockband, eller den andre er fylt med rapstjerner.

Selv om denne klyngingen er fornuftig, er den for det meste ikke perfekt siden dataene bare er samlet inn fra brukeradferd.

5. Visualisering

For noen øyeblikk siden visualiserte algoritmen vår klynge av kunstnere på en terminalvennlig måte. Hvis vi konverterer klyngekonfigurasjonen vår til JSON og mater den til D3.js, vil vi med et par linjer JavaScript ha et hyggelig menneskelig vennlig Radial Tidy-Tree:

Vi må konvertere våre Kart til en JSON med et lignende skjema som dette d3.js-eksemplet.

6. Antall klynger

En av de grunnleggende egenskapene til K-Means er det faktum at vi skal definere antall klynger på forhånd. Så langt brukte vi en statisk verdi for k, men å bestemme denne verdien kan være et utfordrende problem. Det er to vanlige måter å beregne antall klynger på:

1. Domenekunnskap
2. Matematisk heuristikk

Hvis vi er heldige nok til at vi vet så mye om domenet, kan vi kanskje bare gjette riktig nummer.Ellers kan vi bruke noen få heuristikker som Elbow Method eller Silhouette Method for å få en forståelse av antall klynger.

Før vi går videre, bør vi vite at disse heuristikkene, selv om de er nyttige, bare er heuristikk og kanskje ikke gir klare svar.

6.1. Albue Metode

For å bruke albuer-metoden, bør vi først beregne forskjellen mellom hver klyngesentroid og alle dens medlemmer. Når vi grupperer flere ikke-relaterte medlemmer i en klynge, øker avstanden mellom sentroid og dens medlemmer, og dermed reduseres klyngekvaliteten.

En måte å utføre denne avstandsberegningen på er å bruke Summen av kvadrerte feil. Summen av kvadrerte feil eller SSE er lik summen av kvadratiske forskjeller mellom en centroid og alle dens medlemmer:

offentlig statisk dobbel sse (Kart gruppert, Avstandsavstand) {dobbel sum = 0; for (Map.Entry oppføring: clustered.entrySet ()) {Centroid centroid = entry.getKey (); for (Record record: entry.getValue ()) {double d = distance.calculate (centroid.getCoordinates (), record.getFeatures ()); sum + = Math.pow (d, 2); }} retur sum; }

Deretter, vi kan kjøre K-Means-algoritmen for forskjellige verdier av kog bereg SSE for hver av dem:

Liste poster = // datasettet; Avstandsavstand = ny EuclideanDistance (); Liste sumOfSquaredErrors = ny ArrayList (); for (int k = 2; k <= 16; k ++) {Map klynger = KMeans.fit (poster, k, distanse, 1000); dobbel sse = Errors.sse (klynger, avstand); sumOfSquaredErrors.add (sse); }

På slutten av dagen er det mulig å finne en passende k ved å plotte antall klynger mot SSE:

Når antall klynger øker, reduseres vanligvis avstanden mellom klyngemedlemmer. Vi kan imidlertid ikke velge noen vilkårlige store verdier for k, siden å ha flere klynger med bare ett medlem, beseirer hele formålet med klynging.

Tanken bak albuen metoden er å finne en passende verdi for k på en måte som SSE avtar dramatisk rundt den verdien. For eksempel, k = 9 kan være en god kandidat her.

7. Konklusjon

I denne veiledningen dekket vi først noen viktige konsepter i maskinlæring. Så ble vi vannet med mekanikken til K-Means-klyngealgoritmen. Til slutt skrev vi en enkel implementering for K-Means, testet algoritmen vår med et datasett fra den virkelige verden fra Last.fm, og visualiserte klyngeresultatet på en fin grafisk måte.

Eksempelkoden er som vanlig tilgjengelig på GitHub-prosjektet vårt, så sørg for å sjekke det ut!