Vi introducerar ett nytt tillvägagångssätt för att hitta överlappande kluster givet parvis likheter med objekt. I synnerhet löser vi problemet med korrelationskluster genom att låta ett föremål tilldelas mer än ett kluster. Kärnan i vår strategi är ett optimeringsproblem där varje datapunkt kartläggs till en liten uppsättning etiketter som representerar medlemskap i olika kluster. Målet är att hitta en kartläggning så att de givna likheterna mellan objekten så mycket som möjligt överensstämmer med likheter som tagits över deras etikettuppsättningar. Antalet etiketter kan variera mellan olika objekt. För att definiera en likhet mellan etikettuppsättningar, vi överväger två åtgärder: i) en 0-1 funktion som anger om de två etikettuppsättningar har nonzero skärningspunkt och ii) Jaccard koefficienten mellan de två etikettuppsättningar. Algoritmen vi föreslår är en iterativ lokalsöksmetod. Definitionerna av etikettuppsättning likhet ger upphov till två icke-triviala optimeringsproblem, som, för åtgärder av set-intersektion och Jaccard, vi löser med hjälp av en girig strategi respektive icke-negativa minst kvadrater, respektive. Vi utvecklar också en distribuerad version av vår algoritm baserad på BSP-modellen och implementerar den med hjälp av ett Pregel-ramverk. Vår algoritm använder som ingång parvis likheter av objekt och kan därmed tillämpas när kluster strukturerade objekt för vilka funktion vektorer inte är tillgängliga. Som ett bevis på konceptet tillämpar vi våra algoritmer på tre olika och komplexa tillämpningsområden: banor, aminosyrasekvenser och textdokument.
Vi har nyligen utökat korrelationskluster för att möjliggöra överlappningar, dvs. objekt som tillhör mer än ett kluster REF.
Overlapping correlation clustering
{'venue': 'Knowledge and Information Systems', 'journal': 'Knowledge and Information Systems', 'mag_field_of_study': ['Computer Science']}