Spektral klynging i Python

Clustering er et mye brukt maskinlæringsproblem der lignende datapunkter er gruppert sammen for å danne et sett med klynger. Det er mye brukt i applikasjoner som anbefalingssystemer, anomalideteksjon og kundesegmentering. Vi vil gå gjennom en moderne grupperingsteknikk kjent som Spektral klynging og implementeringen av den i Python ved å bruke Sklearn bibliotek.

Hva er klynging?

Clustering er et uovervåket maskinlæringsproblem der man må dele "M" observasjoner i "K" -klynger, med punkter i den samme klyngen som er ekstremt like og punkter i forskjellige klynger som er veldig forskjellige. Problemer som kundesegmentering, anbefalingssystemer, anomalideteksjon osv., løses fra klynging. Du er kanskje kjent med K-Means Clustering Algoritme, der vi ikke har etiketter og må plassere hvert datapunkt i klyngen. Den spektrale klyngemetoden brukes til å oppnå samme mål som K-Means Clustering Method, men med en grafbasert tilnærming. Bildet nedenfor viser de tre klyngene atskilt fra hverandre og har lignende punkter sammen.

Hva er k-middel klynging?

K-betyr klynging innebærer å identifisere datasettets K-klynger som er forskjellige fra hverandre. Bare uavhengige variabler brukes til å lage klynger. K betyr gruppering er en uovervåket læringsalgoritme. Datapunktene i samme klynge er ganske like, mens datapunktene i forskjellige klynger er veldig forskjellige. Du begynner med K tilfeldige sentre og tildeler elementer til de som er nærmest dem. Senteret for hver samling blir deretter beregnet på nytt, noe som resulterer i nye K -sentre. Du fortsetter å gjøre dette til antallet iterasjoner når en forhåndsbestemt terskel eller sentrum av klynger knapt beveger seg. Albuemetoden brukes ofte for å bestemme verdien av k.

Klassifisering vs. Gruppering

Klassifisering er resultatet av overvåket læring, noe som betyr at du vil at systemet skal generere en kjent etikett. For eksempel, hvis du konstruerte en bildeklassifiserer, vil det si: "Dette er en hund, dette er en katt," basert på prøver av hunder og katter du viste den.

Clustering er konsekvensen av ikke -overvåket læring, noe som innebærer at du har sett mange prøver, men ikke har fått etiketter for dem. For eksempel kan vi bruke klynging til å segmentere kundene av samme art fra kundene av forskjellige slag. Dette er en mye brukt problemstilling som løses ved hjelp av klynging.

Hva er spektral klyngelgoritme?

Spektral klynging er en moderne grupperingsalgoritme basert på grafteori. Det har overgått flere klassiske grupperingsmetoder og utvikler seg fortsatt. Denne algoritmen tar hvert datapunkt som en grafnode og bruker grafpartisjonering for å løse klyngeproblemet.

Arbeid av spektral klynging

Opprette en grafdatastruktur

Du kan visualisere et hvilket som helst datasett som en punktsky, med m peker inn n dimensjoner. Du kan lage en graf ut av disse punktene, med nodene som er punktene og kantene (representert av w) blir vektet av hvor like poengene er. Når vi har dataene våre i form av en graf, kan vi generere en adjacency -matrise ved å bare legge inn vekten på kanten mellom noder “I” og “J” i hver kolonne i matrisen. Dette er en m x m Symmetrisk matrise. W er navnet på adjacency -matrisen.

Projisere dataene

I dette trinnet blir dataene projisert inn i et lavere dimensjonalt rom for å gjøre poengene nærmere hverandre i det nedre dimensjonale rommet. Formelen gir graden av hver node:

Gradmatrisen blir deretter beregnet ved å bruke formelen:

Grafens Laplacian kan beregnes ved å bruke formelen L = D-W. Vi kan beregne spekteret av denne matrisen, eller dens egenvektorer ordnet fra mest betydningsfulle til minst viktig, nå som vi har laplacian på grafen. Å ta "k" minst viktige egenvektorer gir deg en representasjon av hver node i grafen i "k" -dimensjoner, som representerer hvert punkt i datasettet. De minste egenverdiene er relatert til de minst betydningsfulle egenvektorene. Dette er en type dimensjonalitetsreduksjon som ikke er lineær.

Gruppere dataene

Dette trinnet innebærer for det meste gruppering av de reduserte dimensjonsdataene ved bruk av K-betyr klynging eller annen klassisk klyngeteknikk. Den normaliserte grafen Laplacian Matrix blir først tilordnet hver node. Dataene blir deretter gruppert ved hjelp av en hvilken som helst standardmetode.

I et ideelt scenario vil du forvente at dataene dine ikke er helt koblet sammen, med distinkte tilkoblede komponenter for hver klynge. I praksis er dette imidlertid sjelden tilfelle: det avhenger av forskjellige ting, inkludert selve dataene og hvordan du designer adjacency -grafen. Når det gjelder effektivitet, blir de bedre klyngene separert, jo mer spektral klynging oppfører seg forutsigbart: grafen vil ha mer enn en tilkoblet komponent (ideelt k, antall klynger i datasettet), den første k egenverdiene vil være null og løpe K-midler i rommet som er opprettet ved å ta de første K-egenvektorene i grafen Laplacian vil gi ganske tilfredsstillende resultater. Jo nærmere klyngene er, jo lenger er egenverdiene fra 0, og jo nærmere punktene i egenområdet er til forskjellige klynger.

K-betyr vs. Spektral klynging

Tenk på dataene gitt nedenfor.

Selv når det sanne antallet klynger k er kjent for algoritmen, vil K-betyr ikke klarer å gruppere dataene ovenfor. Dette er fordi K-Means er en god dataklyngealgoritme for å finne kuleformet grupper som de nedenfor:

Der alle klyngemedlemmer er nær hverandre (i euklidisk forstand). Grafklyngende tilnærminger som spektral klynging, derimot, ikke klynger datapunkter direkte i deres opprinnelige datarom, men bygger i stedet en likhetsmatrise med (i, j)_th rad som representerer en viss likhetsavstand mellom i_th og j_th Datapunkter i datasettet ditt.

På noen måter er spektral klynging mer generell (og kraftig) enn K-midler siden spektral klynging er aktuelt når K-betyr ikke er (bare bruk en enkel euklidisk avstand som likhetstiltak). Det motsatte er imidlertid ikke sant. Når du velger en av disse strategiene fremfor den andre, er det noen praktiske bekymringer å huske på. Inngangsdatamatrisen er faktorisert med K-midler, mens den laplaciske matrisen er faktorisert med spektral klynging (en matrise avledet fra likhetsmatrisen).

Implementering av spektral klynging ved bruk av python

Importere bibliotekene

Fra Sklearn.Cluster Import SpectralClustering
Importer numpy som NP
Leser dataene
X = np.Array ([[1, 1], [2, 1], [1, 0],
[4, 7], [3, 5], [3, 6]])

Legg merke til at i dette eksemplet har vi tatt dataene med mindre dimensjoner. Hvis du har større dimensjonsdata, kan du bruke hovedkomponentanalyse (PCA) for å redusere datadimensjonene.

Initialisere modellen vår

modell = spektralklustering (n_clusters = 2,
tilordne_labels = 'Discretize',
random_state = 0).passform (x)

Få etiketter av hvert datapunkt

trykk (modell.Etiketter_)

Produksjon

Array ([1, 1, 1, 0, 0, 0])

Fordeler med spektral klynging

• Spektral klynging antar ikke dataformen. Det fungerer bra på alle slags datafordelinger. Andre klassiske algoritmer som K-middel antar formen til data som sfærisk.
• Det fungerer ganske bra når relasjoner er omtrent transitive (som likhet).
• Vi trenger ikke hele datasettet for å klynge; Bare en likhet/avstandsmatrise, eller kanskje bare Laplacian, vil være tilstrekkelig.

Ulemper ved spektral klynging

• Beregning av egenvektorer er flaskehalsen; Derfor er det dyrt for virkelig store datasett.
• Fungerer ikke bra med støyende datasett.
• Antall klynger (k) må avgjøres på forhånd.

Bruk tilfeller av spektral klynging

• Bildesegmentering
• Kundesegmentering
• Enhetsoppløsning
• Proteinsekvenser spektral klynging

Konklusjon

Vi så hvordan vi kan bruke spektral klynge for å gruppere datapunktene våre. Vi projiserer først datapunktene i en grafdatastruktur, reduserer dimensjonene til dataene og bruker deretter den tradisjonelle grupperingsteknikken på reduserte data. Vi så senere hvor lett denne komplekse algoritmen kunne implementeres i Python ved å bruke noen få kodelinjer.