Korrelationsklustring
Klustring är problemet med att dela upp datapunkter i grupper baserat på deras likhet. Korrelationskluster tillhandahåller en metod för att gruppera en uppsättning objekt i det optimala antalet kluster utan att specificera det antalet i förväg.
Beskrivning av problemet
I maskininlärning fungerar korrelationskluster eller klusterredigering i ett scenario där relationerna mellan objekten är kända istället för de faktiska representationerna av objekten . Till exempel, givet en viktad graf där kantvikten anger om två noder är lika (positiv kantvikt) eller olika (negativ kantvikt), uppgiften är att hitta en klustring som antingen maximerar överensstämmelser (summan av positiva kantvikter inom ett kluster plus det absoluta värdet av summan av negativa kantvikter mellan kluster) eller minimerar oenighet (absolutvärdet av summan av negativa kantvikter inom ett kluster plus summan av positiva kantvikter över kluster). Till skillnad från andra klustringsalgoritmer kräver detta inte att man väljer antalet kluster i förväg eftersom målet, att minimera summan av vikterna för de skurna kanterna, är oberoende av antalet kluster.
Det kanske inte är möjligt att hitta en perfekt kluster, där alla liknande objekt finns i ett kluster medan alla olika är i olika kluster. Om grafen verkligen medger en perfekt klustring, då helt enkelt radera alla negativa kanter och hitta de anslutna komponenterna i den återstående grafen kommer att returnera de nödvändiga klustren.
Men i allmänhet kanske en graf inte har en perfekt klustring. Till exempel, givet noder a,b,c så att a,b och a,c är lika medan b,c är olika, är en perfekt klustring inte möjlig. I sådana fall är uppgiften att hitta en klustring som maximerar antalet överenskommelser (antal + kanter inuti kluster plus antalet − kanter mellan kluster) eller minimerar antalet oenigheter (antalet − kanter inuti kluster plus antalet av + kanter mellan kluster). Detta problem med att maximera avtalen är NP-komplett (multiway cut-problem reduceras till maximerande viktade avtal och problemet med att dela upp i trianglar kan reduceras till den oviktade versionen).
Algoritmer
Bansal et al. diskutera NP-fullständighetsbeviset och presentera både en konstantfaktorapproximationsalgoritm och polynom-tidsapproximationsschema för att hitta klustren i denna inställning. Ailon et al. föreslå en randomiserad 3- approximationsalgoritm för samma problem.
CC-pivot (G=(V,E + ,E − )) Välj slumpmässig pivot i ∈ V Set , V'=Ø För alla j ∈ V, j ≠ i; Om (i,j) ∈ E + sedan Add j till C Annars (If (i,j) ∈ E − ) Add j till V' Låt G' vara subgrafen inducerad av V' Return klustring C,CC-Pivot(G ')
Författarna visar att ovanstående algoritm är en 3- approximationsalgoritm för korrelationsklustring. Den bästa polynom-tidsapproximationsalgoritmen som för närvarande är känd för detta problem uppnår en approximation av ~2,06 genom att avrunda ett linjärt program, som visas av Chawla , Makarychev, Schramm och Yaroslavtsev .
Karpinski och Schudy bevisade att det fanns ett polynomiskt tidsapproximationsschema (PTAS) för det problemet på kompletta grafer och ett fast antal kluster.
Optimalt antal kluster
År 2011 visade Bagon och Galun att optimeringen av korrelationsklustringsfunktionen är nära relaterad till välkända diskreta optimeringsmetoder . I sitt arbete föreslog de en probabilistisk analys av den underliggande implicita modellen som gör det möjligt för korrelationsklustringen att uppskatta det underliggande antalet kluster. Denna analys antyder att de funktionella antar en enhetlig prior över alla möjliga partitioner oavsett deras antal kluster. Sålunda uppstår en olikformig föregång över antalet kluster.
Flera diskreta optimeringsalgoritmer föreslås i detta arbete som skalas elegant med antalet element (experiment visar resultat med mer än 100 000 variabler). Bagon och Galuns arbete utvärderade också effektiviteten av återställningen av det underliggande antalet kluster i flera applikationer.
Korrelationsklustring (datautvinning)
Korrelationsklustring hänför sig också till en annan uppgift, där korrelationer mellan attribut för egenskapsvektorer i ett högdimensionellt utrymme antas existera som styr klustringsprocessen . Dessa korrelationer kan vara olika i olika kluster, så en global dekorrelation kan inte reducera detta till traditionell (okorrelerad) klustring.
Korrelationer mellan delmängder av attribut resulterar i olika rumsliga former av kluster. Därför definieras likheten mellan klusterobjekt genom att ta hänsyn till de lokala korrelationsmönstren. Med denna föreställning har termen införts samtidigt med den ovan diskuterade föreställningen. Olika metoder för korrelationsklustring av denna typ diskuteras i och relationen till olika typer av klustring diskuteras i. Se även Clustering av högdimensionell data .
Korrelationsklustring (enligt denna definition) kan visas vara nära besläktat med biclustering . Liksom vid biklustering är målet att identifiera grupper av objekt som delar en korrelation i några av sina attribut; där korrelationen vanligtvis är typisk för de enskilda klustren.