k-means算法比較簡單。在k-means算法中，用cluster來表示簇;容易證明k-means算法收斂等同于所有質(zhì)心不再發(fā)生變化。基本的k-means算法流程如下：

簡介

又叫K-均值算法，是非監(jiān)督學(xué)習(xí)中的聚類算法。

基本思想

k-means算法比較簡單。在k-means算法中，用cluster來表示簇;容易證明k-means算法收斂等同于所有質(zhì)心不再發(fā)生變化。基本的k-means算法流程如下：

選取k個初始質(zhì)心(作為初始cluster，每個初始cluster只包含一個點(diǎn));

repeat：

• 對每個樣本點(diǎn)，計算得到距其最近的質(zhì)心，將其類別標(biāo)為該質(zhì)心所對應(yīng)的cluster;
• 重新計算k個cluster對應(yīng)的質(zhì)心(質(zhì)心是cluster中樣本點(diǎn)的均值);
• until 質(zhì)心不再發(fā)生變化 12345

repeat的次數(shù)決定了算法的迭代次數(shù)。實際上，k-means的本質(zhì)是最小化目標(biāo)函數(shù)，目標(biāo)函數(shù)為每個點(diǎn)到其簇質(zhì)心的距離的平方和：

• N是元素個數(shù)，x表示元素，c(j)表示第j簇的質(zhì)心
• 算法復(fù)雜度
• 時間復(fù)雜度是O(nkt) ,其中n代表元素個數(shù)，t代表算法迭代的次數(shù)，k代表簇的數(shù)目

優(yōu)缺點(diǎn)

• 優(yōu)點(diǎn)
• 簡單、快速;
• 對大數(shù)據(jù)集有較高的效率并且是可伸縮性的;
• 時間復(fù)雜度近于線性，適合挖掘大規(guī)模數(shù)據(jù)集。

缺點(diǎn)

• k-means是局部***，因而對初始質(zhì)心的選取敏感;
• 選擇能達(dá)到目標(biāo)函數(shù)***的k值是非常困難的。

代碼

代碼已在github上實現(xiàn)，這里也貼出來

測試數(shù)據(jù)集獲取地址為testSet