Gaussiska blandningsmodeller (GMM) är den mest använda statistiska modellen för k-means kluster problem och bildar en populär ram för klusterbildning i maskininlärning och dataanalys. I detta papper föreslår vi en naturlig semi-random modell för k-means klustering som generaliserar Gaussian blandning modell, och som vi tror kommer att vara användbart för att identifiera robusta algoritmer. I vår modell, en semi-random motståndare tillåts att göra godtyckliga "monoton" eller hjälpsamma förändringar av data som genereras från Gaussian blandningsmodell. Vårt första bidrag är en polynom tid algoritm som bevisligen återställer mark-sanningen upp till små klassificeringsfel w.h.p., förutsatt viss separation mellan komponenterna. Kanske överraskande, algoritmen vi analyserar är den populära Lloyd algoritm för k-medel klustering som är metoden-av-val i praktiken. Vårt andra resultat kompletterar den övre gränsen genom att ge en nästan matchande informationsteori lägre gräns på antalet felklassificerade punkter som uppstår av någon k-medel kluster algoritm på semi-random modellen.
Robusthet i Lloyds algoritm under en semi-slump GMM studeras i REF.
Clustering Semi-Random Mixtures of Gaussians
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}