Abstract-Det har gjorts stora framsteg på effektiva algoritmer för kluster datapunkter som genereras av en blandning av k sannolikhetsfördelningar under antagandet att medel för distributionerna är väl åtskilda, dvs avståndet mellan medel för två distributioner är minst  på (k) standardavvikelser. Dessa resultat i allmänhet använder sig i stor utsträckning av den generativa modellen och särskilda egenskaper hos distributionerna. I den här artikeln visar vi att en enkel klusteralgoritm fungerar utan att anta någon generativ (probabilistisk) modell. Vårt enda antagande är vad vi kallar ett "närhetstillstånd": projektionen av någon datapunkt på linjen som förenar dess klustercenter till något annat klustercenter är  och (k) standardavvikelser närmare sitt eget centrum än det andra centrum. Här är begreppet standardavvikelser baserat på spektralnormen för den matris vars rader representerar skillnaden mellan en punkt och medelvärdet av den kluster som den tillhör. Vi visar att i de generativa modeller som studeras är vårt närhetstillstånd tillfredsställt och därför kan vi härleda mest kända resultat för generativa modeller som följd av vårt huvudresultat. Vi bevisar också några nya resultat för generativa modeller - t.ex. kan vi samla alla utom en liten bråkdel av punkter bara antar en gräns på variansen. Vår algoritm bygger på den välkända k-means algoritm, och längs vägen, visar vi ett resultat av oberoende intresse - att k-means algoritm konvergerar till de "sanna centra" även i närvaro av falska punkter förutsatt att de ursprungliga (uppskattade) centra är tillräckligt nära de motsvarande faktiska centra och alla utom en liten bråkdel av punkterna uppfyller närhetstillståndet. Slutligen presenterar vi en ny teknik för att öka förhållandet mellan mittseparation och standardavvikelse. Detta gör att vi kan bevisa resultat för att lära sig vissa blandning av distributioner under svagare separationsförhållanden.
Kumar och Kannan REF visar att k-means algoritm med en korrekt initiering kan korrekt kluster nästan alla datapunkter som genereras från en GMM som uppfyller en viss närhet antagande.
Clustering with Spectral Norm and the k-Means Algorithm
{'venue': '2010 IEEE 51st Annual Symposium on Foundations of Computer Science', 'journal': '2010 IEEE 51st Annual Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Mathematics', 'Computer Science']}