K-means-metoden är en allmänt använd klusteralgoritm. Ett av dess utmärkande drag är dess hastighet i praktiken. Dess värsta drifttid är emellertid exponentiell och lämnar ett gap mellan praktiska och teoretiska prestationer. Arthur och Vassilvitskii [3] syftade till att minska detta gap, och de visade sig vara bundet av poly(n k, σ −1 ) på den utjämnade körtiden för k-means-metoden, där n är antalet datapunkter och σ är standardavvikelsen för Gaussian perturbation. Denna gräns, även om den är bättre än det värsta, är fortfarande mycket större än den i praktiken observerade löptiden. Vi förbättrar den släta analysen av k-means-metoden genom att visa två övre gränser på den förväntade körtiden för k-means. För det första bevisar vi att den förväntade körtiden begränsas av ett polynom i n ε k och σ −1. För det andra visar vi en övre gräns av kkd · poly(n, σ −1 ), där d är dimensionen av datarymden. Polynomet är oberoende av k och d, och vi får ett polynom som är bundet till den förväntade körtiden för k, d och O( log n/ log log n). Slutligen visar vi att k-medel går i slät polynom tid för endimensionella instanser.
Mande och Röglin förbättrade den utjämnade körtiden bunden genom att ta fram två gränser REF: Den första är polynom i n ε k och 1/σ.
Improved Smoothed Analysis of the k-Means Method
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}