Kumar och Kannan [KK10] hade som mål att förena kända resultat med kluster av distributionsblandningar under separationsförhållanden och införde ett deterministiskt villkor för att samla dataset. De visade att detta enda deterministiska tillstånd omfattar många tidigare studerade klusterantaganden. Mer specifikt, deras närhet villkor kräver att i målet k-klustering, projektionen av en punkt x på linjen som förenar dess kluster center μ och några andra centrum μ ′, är en stor additiv faktor närmare μ än μ ′. Denna tillsatsfaktor kan grovt beskrivas som k gånger spektralnormen för matrisen som representerar skillnaderna mellan den givna (kända) datauppsättningen och den (okända) målhopningens medel. Det är tydligt att närheten innebär centrum separation - avståndet mellan två centra måste vara lika stort som ovan nämnda bundna. I detta dokument förbättrar vi Kumars och Kannans [KK10] arbete längs flera axlar. För det första försvagar vi den mittseparation som är bunden av en faktor av k, och för det andra försvagar vi närhetstillståndet med en faktor av k (med andra ord är det reviderade separationstillståndet oberoende av k). Med hjälp av dessa svagare gränser uppnår vi fortfarande samma garantier när alla punkter uppfyller närhetsvillkoret. Under samma svagare gränser, uppnår vi ännu bättre garantier när endast (1- på)-fraktion av punkterna uppfyller villkoret. Specifikt, vi korrekt klumpar alla utom en (- + O(1/c 4 ))-fraktion av punkterna, jämfört med O (k 2 -)-fraktion av [KK10], vilket är meningsfullt även i den särskilda inställningen när -är en konstant och k = -(1). Viktigast av allt är att vi avsevärt förenklar analysen av Kumar och Kannan. I själva verket, i huvuddelen av vår analys vi bortser från närheten villkor och använder endast center separation, tillsammans med den enkla triangeln och Markov ojämlikheter. Men dessa grundläggande verktyg räcker för att producera en klustering som (i) är korrekt på alla utom en konstant bråkdel av punkterna, (ii) har k-medel kostnad jämförbar med k-medel kostnaden för målet kluster, och (iii) har centra mycket nära målcentra. Vårt förbättrade separationstillstånd gör att vi kan matcha resultaten av Planted Partition Model av McSherry [McS01], förbättra resultaten av Ostrovsky et al [ORSS06], och förbättra separation resultat för blandning av Gaussian modeller i en viss inställning.
Det mest kända resultatet är genom REF som kräver att medelvärdet av gaussianerna separeras av Õ(σ ε k) där σ 2 är en övre gräns på variansen av k gaussianerna.
Improved Spectral-Norm Bounds for Clustering
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}