Vi presenterar ett enhetligt tillvägagångssätt för att samtidigt samla och upptäcka outliers i data. Vårt tillvägagångssätt formaliseras som en generalisering av k-means-problemet. Vi bevisar att problemet är NP-hård och sedan presentera en praktisk polynom tid algoritm, som garanteras att konvergera till en lokal optimal. Dessutom utvidgar vi vår strategi till alla distansåtgärder som kan uttryckas i form av en Bregman-divergens. Experiment på syntetiska och verkliga dataset visar effektiviteten i vårt tillvägagångssätt och nyttan av att utföra både kluster och avvikande detektion på ett parallellt sätt. I synnerhet på den berömda KDD cup nätverk-inträngande dataset, kunde vi öka precisionen av outlier detektion uppgiften med nästan 100% jämfört med den klassiska närmaste-grannar tillvägagångssätt.
Chawla m.fl. REF förbättrade sin tidigare metod för att garantera att den konvergerar till ett lokalt optimalt och föreslog ett nytt tillvägagångssätt för att mäta dataavstånd i form av en Bregman-divergens.
k-means--: A Unified Approach to Clustering and Outlier Detection
{'venue': 'SDM', 'journal': None, 'mag_field_of_study': ['Computer Science']}