k-means算法比較簡(jiǎn)單。在k-means算法中，用cluster來(lái)表示簇;容易證明k-means算法收斂等同于所有質(zhì)心不再發(fā)生變化?；镜膋-means算法流程如下：

簡(jiǎn)介

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

基本思想

k-means算法比較簡(jiǎn)單。在k-means算法中，用cluster來(lái)表示簇;容易證明k-means算法收斂等同于所有質(zhì)心不再發(fā)生變化?；镜膋-means算法流程如下：

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

repeat：

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

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

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

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

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

缺點(diǎn)

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

代碼

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

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