Vi anser att följande kluster problem: vi har en komplett graf på n hörn (punkter), där varje kant (u, v) är märkt antingen + eller − beroende på om u och v har ansetts vara liknande eller annorlunda. Målet är att producera en partition av hörnen (en klunga) som överensstämmer så mycket som möjligt med kantetiketterna. Det vill säga, vi vill ha ett kluster som maximerar antalet + kanter inom kluster, plus antalet − kanter mellan kluster (motsvarande minimerar antalet meningsskiljaktigheter: antalet − kanter inuti kluster plus antalet + kanter mellan kluster). Denna formulering är motiverad från ett dokument kluster problem där man har en parvis likhet funktion f lärt sig från tidigare data, och målet är att partitionera den nuvarande uppsättningen dokument på ett sätt som korrelerar med f så mycket som möjligt; det kan också ses som en typ av "agnostiskt lärande" problem. Ett intressant inslag i denna klusterformulering är att man inte behöver ange antalet kluster k som en separat parameter, som i åtgärder som k-median eller min-sum eller min-max kluster. I stället, i vår formulering, kan det optimala antalet kluster vara något värde mellan 1 och n, beroende på kantetiketter. Vi tittar på approximationsalgoritmer för både att minimera meningsskiljaktigheter och för att maximera avtal. För att minimera meningsskiljaktigheter, ger vi en konstant faktor approximation. För att maximera avtal ger vi en PTAS, bygger på idéer från Goldreich, Goldwasser, och Ron (1998) och de la Vega (1996). Vi visar också hur man utvidgar några av dessa resultat till grafer med eggetiketter i [−1, +1], och ger några resultat för fall av slumpmässigt buller.
Med tanke på ett problem med dokumentkluster formaliserade REF den oviktade versionen av CC-problemet och diskuterade också dess NP-fullständighetsbevis.
Correlation Clustering
{'venue': 'Machine Learning', 'journal': 'Machine Learning', 'mag_field_of_study': ['Computer Science', 'Mathematics']}