Kluster är ett grundläggande problem i oövervakat lärande, och har studerats brett både som ett problem med att lära blandningsmodeller och som ett optimeringsproblem. I denna uppsats studerar vi klustering med avseende på k-median objektiv funktion, en naturlig formulering av klustering där vi försöker minimera den genomsnittliga avståndet till klustercenter. Ett av de viktigaste bidragen i detta papper är en enkel men kraftfull provtagningsteknik som vi kallar på varandra följande provtagningar som kan vara av oberoende intresse. Vi visar att vårt provtagningsförfarande snabbt kan identifiera en liten uppsättning punkter (av storlek bara O(k log n k )) som sammanfattar indatapunkter i syfte att klustra. Med hjälp av successiv provtagning, utvecklar vi en algoritm för k-median problem som körs i O (nk) tid för ett brett spektrum av värden av k och garanteras, med hög sannolikhet, att returnera en lösning med kostnad på högst en konstant faktor gånger optimal. Vi etablerar också en lägre gräns av (nk) på någon randomiserad konstant-faktor approximation algoritm för k-median problem som lyckas med även en försumbar (säg 1 100 ) sannolikhet. Den bästa tidigare övre gränsen för problemet var Õ(nk), där Õ-notationen döljer polylogaritmiska faktorer i n och k. Den bästa tidigare nedre gränsen av (nk) tillämpades endast på deterministiska k-medianalgoritmer. Medan vi fokuserar vår presentation på k-medianmålet, alla våra övre gränser gäller för k-medelsmålet också. I detta sammanhang jämför vår algoritm gynnsamt med den allmänt använda k-means heuristic, som kräver O (nk) tid för bara en iteration och ger inga användbara approximationsgarantier.
I REF visades en approximation av O(1) för en något mer komplicerad algoritm som kallas på varandra följande provtagning med O(n(k + log n) + k 2 log 2 n) körtid, med förbehåll för en begränsad spridning av punkterna.
Optimal Time Bounds for Approximate Clustering
{'venue': 'Machine Learning', 'journal': 'Machine Learning', 'mag_field_of_study': ['Mathematics', 'Computer Science']}