一、算法介紹

聚類屬于無監(jiān)督學(xué)習(xí)，K-means算法是很典型的基于距離的聚類算法，采用距離作為相似性的評(píng)價(jià)指標(biāo)，即認(rèn)為兩個(gè)對(duì)象的距離越近，其相似度就越大。該算法認(rèn)為簇是由距離靠近的對(duì)象組成的，因此把得到緊湊且獨(dú)立的簇作為最終目標(biāo)。
k個(gè)初始類聚類中心點(diǎn)的選取對(duì)聚類結(jié)果具有較大的

二 基本概念

無監(jiān)督學(xué)習(xí)

三 實(shí)現(xiàn)過程

算法過程如下：
1）從N個(gè)文檔隨機(jī)選取K個(gè)文檔作為質(zhì)心
2）對(duì)剩余的每個(gè)文檔測量其到每個(gè)質(zhì)心的距離，并把它歸到最近的質(zhì)心的類
3）重新計(jì)算已經(jīng)得到的各個(gè)類的質(zhì)心
4）迭代2～3步直至新的質(zhì)心與原質(zhì)心相等或小于指定閾值，算法結(jié)束

四、應(yīng)用場景

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

1、優(yōu)點(diǎn)

1.收斂太慢
2.算法復(fù)雜度高O(nkt)
3.不能發(fā)現(xiàn)非凸形狀的簇，或大小差別很大的簇
4.需樣本存在均值（限定數(shù)據(jù)種類）
6.需先確定k的個(gè)數(shù)
7.對(duì)噪聲和離群點(diǎn)敏感
8.最重要是結(jié)果不一定是全局最優(yōu)，只能保證局部最優(yōu)。

2、缺點(diǎn)

1.收斂太慢
2.算法復(fù)雜度高O(nkt)
3.不能發(fā)現(xiàn)非凸形狀的簇，或大小差別很大的簇
4.需樣本存在均值（限定數(shù)據(jù)種類）
6.需先確定k的個(gè)數(shù)
7.對(duì)噪聲和離群點(diǎn)敏感
8.最重要是結(jié)果不一定是全局最優(yōu)，只能保證局部最優(yōu)。

六、常見問題

1、K如何確定

kmenas算法首先選擇K個(gè)初始質(zhì)心，其中K是用戶指定的參數(shù)，即所期望的簇的個(gè)數(shù)。這樣做的前提是我們已經(jīng)知道數(shù)據(jù)集中包含多少個(gè)簇，但很多情況下，我們并不知道數(shù)據(jù)的分布情況，實(shí)際上聚類就是我們發(fā)現(xiàn)數(shù)據(jù)分布的一種手段，這就陷入了雞和蛋的矛盾。如何有效的確定K值，這里大致提供幾種方法，若各位有更好的方法，歡迎探討。
1.與層次聚類結(jié)合
經(jīng)常會(huì)產(chǎn)生較好的聚類結(jié)果的一個(gè)有趣策略是，首先采用層次凝聚算法決定結(jié)果粗的數(shù)目，并找到一個(gè)初始聚類，然后用迭代重定位來改進(jìn)該聚類。
2.穩(wěn)定性方法
穩(wěn)定性方法對(duì)一個(gè)數(shù)據(jù)集進(jìn)行2次重采樣產(chǎn)生2個(gè)數(shù)據(jù)子集，再用相同的聚類算法對(duì)2個(gè)數(shù)據(jù)子集進(jìn)行聚類，產(chǎn)生2個(gè)具有k個(gè)聚類的聚類結(jié)果，計(jì)算2個(gè)聚類結(jié)果的相似度的分布情況。2個(gè)聚類結(jié)果具有高的相似度說明k個(gè)聚類反映了穩(wěn)定的聚類結(jié)構(gòu)，其相似度可以用來估計(jì)聚類個(gè)數(shù)。采用次方法試探多個(gè)k，找到合適的k值。
3.系統(tǒng)演化方法
系統(tǒng)演化方法將一個(gè)數(shù)據(jù)集視為偽熱力學(xué)系統(tǒng)，當(dāng)數(shù)據(jù)集被劃分為K個(gè)聚類時(shí)稱系統(tǒng)處于狀態(tài)K。系統(tǒng)由初始狀態(tài)K=1出發(fā)，經(jīng)過分裂過程和合并過程，系統(tǒng)將演化到它的穩(wěn)定平衡狀態(tài)Ki，其所對(duì)應(yīng)的聚類結(jié)構(gòu)決定了最優(yōu)類數(shù)Ki。系統(tǒng)演化方法能提供關(guān)于所有聚類之間的相對(duì)邊界距離或可分程度，它適用于明顯分離的聚類結(jié)構(gòu)和輕微重疊的聚類結(jié)構(gòu)。
4.使用canopy算法進(jìn)行初始劃分
基于CanopyMethod的聚類算法將聚類過程分為兩個(gè)階段 Stage1、聚類最耗費(fèi)計(jì)算的地方是計(jì)算對(duì)象相似性的時(shí)候，CanopyMethod在第一階段選擇簡單、計(jì)算代價(jià)較低的方法計(jì)算對(duì)象相似性，將相似的對(duì)象放在一個(gè)子集中，這個(gè)子集被叫做Canopy，通過一系列計(jì)算得到若干Canopy，Canopy之間可以是重疊的，但不會(huì)存在某個(gè)對(duì)象不屬于任何Canopy的情況，可以把這一階段看做數(shù)據(jù)預(yù)處理； Stage2、在各個(gè)Canopy內(nèi)使用傳統(tǒng)的聚類方法(如K-means)，不屬于同一Canopy 的對(duì)象之間不進(jìn)行相似性計(jì)算。從這個(gè)方法起碼可以看出兩點(diǎn)好處：首先，Canopy 不要太大且Canopy之間重疊的不要太多的話會(huì)大大減少后續(xù)需要計(jì)算相似性的對(duì)象的個(gè)數(shù)；其次，類似于K-means這樣的聚類方法是需要人為指出K的值的，通過Stage1得到的Canopy個(gè)數(shù)完全可以作為這個(gè)K值，一定程度上減少了選擇K的盲目性。
其他方法如貝葉斯信息準(zhǔn)則方法（BIC）可參看《一種基于貝葉斯信息準(zhǔn)則的k均值聚類方法》。

2、初始質(zhì)心的選取

選擇適當(dāng)?shù)某跏假|(zhì)心是基本kmeans算法的關(guān)鍵步驟。常見的方法是隨機(jī)的選取初始質(zhì)心，但是這樣簇的質(zhì)量常常很差。處理選取初始質(zhì)心問題的一種常用技術(shù)是：多次運(yùn)行，每次使用一組不同的隨機(jī)初始質(zhì)心，然后選取具有最小SSE（誤差的平方和）的簇集。這種策略簡單，但是效果可能不好，這取決于數(shù)據(jù)集和尋找的簇的個(gè)數(shù)。
第二種有效的方法是，取一個(gè)樣本，并使用層次聚類技術(shù)對(duì)它聚類。從層次聚類中提取K個(gè)簇，并用這些簇的質(zhì)心作為初始質(zhì)心。該方法通常很有效，但僅對(duì)下列情況有效：（1）樣本相對(duì)較小，例如數(shù)百到數(shù)千（層次聚類開銷較大）；（2）K相對(duì)于樣本大小較小
第三種選擇初始質(zhì)心的方法，隨機(jī)地選擇第一個(gè)點(diǎn)，或取所有點(diǎn)的質(zhì)心作為第一個(gè)點(diǎn)。然后，對(duì)于每個(gè)后繼初始質(zhì)心，選擇離已經(jīng)選取過的初始質(zhì)心最遠(yuǎn)的點(diǎn)。使用這種方法，確保了選擇的初始質(zhì)心不僅是隨機(jī)的，而且是散開的。但是，這種方法可能選中離群點(diǎn)。此外，求離當(dāng)前初始質(zhì)心集最遠(yuǎn)的點(diǎn)開銷也非常大。為了克服這個(gè)問題，通常該方法用于點(diǎn)樣本。由于離群點(diǎn)很少（多了就不是離群點(diǎn)了），它們多半不會(huì)在隨機(jī)樣本中出現(xiàn)。計(jì)算量也大幅減少。
第四種方法就是上面提到的canopy算法。

3、距離的度量

常用的距離度量方法包括：歐幾里得距離和余弦相似度。兩者都是評(píng)定個(gè)體間差異的大小的。歐幾里得距離度量會(huì)受指標(biāo)不同單位刻度的影響，所以一般需要先進(jìn)行標(biāo)準(zhǔn)化，同時(shí)距離越大，個(gè)體間差異越大；空間向量余弦夾角的相似度度量不會(huì)受指標(biāo)刻度的影響，余弦值落于區(qū)間[-1,1]，值越大，差異越小。但是針對(duì)具體應(yīng)用，什么情況下使用歐氏距離，什么情況下使用余弦相似度？
從幾何意義上來說，n維向量空間的一條線段作為底邊和原點(diǎn)組成的三角形，其頂角大小是不確定的。也就是說對(duì)于兩條空間向量，即使兩點(diǎn)距離一定，他們的夾角余弦值也可以隨意變化。感性的認(rèn)識(shí)，當(dāng)兩用戶評(píng)分趨勢一致時(shí)，但是評(píng)分值差距很大，余弦相似度傾向給出更優(yōu)解。舉個(gè)極端的例子，兩用戶只對(duì)兩件商品評(píng)分，向量分別為(3,3)和(5,5)，這兩位用戶的認(rèn)知其實(shí)是一樣的，但是歐式距離給出的解顯然沒有余弦值合理。[6]

4、質(zhì)心的計(jì)算

對(duì)于距離度量不管是采用歐式距離還是采用余弦相似度，簇的質(zhì)心都是其均值，即向量各維取平均即可。對(duì)于距離對(duì)量采用其它方式時(shí)，這個(gè)還沒研究過。

5、算法停止條件

一般是目標(biāo)函數(shù)達(dá)到最優(yōu)或者達(dá)到最大的迭代次數(shù)即可終止。對(duì)于不同的距離度量，目標(biāo)函數(shù)往往不同。當(dāng)采用歐式距離時(shí)，目標(biāo)函數(shù)一般為最小化對(duì)象到其簇質(zhì)心的距離的平方和，如下：

K-means算法簡介及常見問題

當(dāng)采用余弦相似度時(shí)，目標(biāo)函數(shù)一般為最大化對(duì)象到其簇質(zhì)心的余弦相似度和，如下：

K-means算法簡介及常見問題

6、空聚類的處理

如果所有的點(diǎn)在指派步驟都未分配到某個(gè)簇，就會(huì)得到空簇。如果這種情況發(fā)生，則需要某種策略來選擇一個(gè)替補(bǔ)質(zhì)心，否則的話，平方誤差將會(huì)偏大。一種方法是選擇一個(gè)距離當(dāng)前任何質(zhì)心最遠(yuǎn)的點(diǎn)。這將消除當(dāng)前對(duì)總平方誤差影響最大的點(diǎn)。另一種方法是從具有最大SSE的簇中選擇一個(gè)替補(bǔ)的質(zhì)心。這將分裂簇并降低聚類的總SSE。如果有多個(gè)空簇，則該過程重復(fù)多次。另外，編程實(shí)現(xiàn)時(shí)，要注意空簇可能導(dǎo)致的程序bug。

七、總結(jié)

K-means也是聚類算法中最簡單的一種了，因此存在的問題也是非常多，可以繼續(xù)學(xué)習(xí)自動(dòng)聚類已經(jīng)可以改進(jìn)后算法。
改進(jìn)算法諸如k-means++等

附錄一

基于numpy實(shí)現(xiàn)的算法程序

# -*- coding: utf-8 -*-
from numpy import *
import time
import matplotlib.pyplot as plt


# 計(jì)算距離
def euclDistance(vector1, vector2):
    return sqrt(sum(power(vector2 - vector1, 2)))


#
def initCentroids(dataSet, k):
    numSamples, dim = dataSet.shape
    centroids = zeros((k, dim))
    for i in range(k):
        index = int(random.uniform(0, numSamples))
        centroids[i, :] = dataSet[index, :]
    return centroids


# 聚類
def kmeans(dataSet, k):
    numSamples = dataSet.shape[0]
    clusterAssment = mat(zeros((numSamples, 2)))
    clusterChanged = True

    #獲取初始聚類中心
    centroids = initCentroids(dataSet, k)

    # 不斷迭代，指導(dǎo)聚類中點(diǎn)沒有變化
    while clusterChanged:
        clusterChanged = False
        for i in range(numSamples):
            minDist = 100000.0
            minIndex = 0
            for j in range(k):
                #計(jì)算出距離
                distance = euclDistance(centroids[j, :], dataSet[i, :])
                #求出最短的聚類點(diǎn)
                if distance < minDist:
                    minDist = distance
                    minIndex = j

            # 如果該點(diǎn)聚類有變化，則重新賦值
            if clusterAssment[i, 0] != minIndex:
                clusterChanged = True
                clusterAssment[i, :] = minIndex, minDist ** 2

        # 更新聚類中心點(diǎn)
        for j in range(k):
            pointsInCluster = dataSet[nonzero(clusterAssment[:, 0].A == j)[0]]
            centroids[j, :] = mean(pointsInCluster, axis=0)

    print('聚類完畢')
    return centroids, clusterAssment

#展示數(shù)據(jù)
def showCluster(dataSet, k, centroids, clusterAssment):
    numSamples, dim = dataSet.shape
    if dim != 2:
        print("Sorry! I can not draw because the dimension of your data is not 2!")
        return 1

    mark = ['or', 'ob', 'og', 'ok', '^r', '+r', 'sr', 'dr', '<r', 'pr']
    if k > len(mark):
        print("Sorry! Your k is too large! please contact Zouxy")
        return 1

    # draw all samples
    for i in range(numSamples):
        markIndex = int(clusterAssment[i, 0])
        plt.plot(dataSet[i, 0], dataSet[i, 1], mark[markIndex])

    mark = ['Dr', 'Db', 'Dg', 'Dk', '^b', '+b', 'sb', 'db', '<b', 'pb']
    # draw the centroids
    for i in range(k):
        plt.plot(centroids[i, 0], centroids[i, 1], mark[i], markersize=12)

    plt.show()


if __name__ == '__main__':
    print("加載數(shù)據(jù)")
    dataSet = []
    fileIn = open('data\\testData.txt')
    for line in fileIn.readlines():
        lineArr = line.strip().split(' ')
        dataSet.append([float(lineArr[0]), float(lineArr[1])])

    #轉(zhuǎn)化為矩陣
    dataSet = mat(dataSet)
    k = 4
    centroids, clusterAssment = kmeans(dataSet, k)
    # 最后結(jié)果
    print(centroids)
    print("顯示數(shù)據(jù)")
    showCluster(dataSet, k, centroids, clusterAssment)

附錄二

基于scikit實(shí)現(xiàn)的算法程序

# -*- coding: utf-8 -*-
from sklearn.cluster import KMeans
from sklearn.cluster import KMeans
from sklearn.cluster import MiniBatchKMeans
import matplotlib.pyplot as plt
import numpy as np
#展示數(shù)據(jù)
def showCluster(dataSet, k, clusterAssment):
    dataSet = np.array(dataSet)

    numSamples= np.shape(dataSet)[0]
    dim = np.shape(dataSet)[1]
    if dim != 2:
        print("Sorry! I can not draw because the dimension of your data is not 2!")
        return 1

    mark = ['or', 'ob', 'og', 'ok', '^r', '+r', 'sr', 'dr', '<r', 'pr']
    if k > len(mark):
        print("")
        return 1

    # draw all samples
    for i in range(numSamples):
        markIndex = int(clusterAssment[i])
        plt.plot(dataSet[i, 0], dataSet[i, 1], mark[markIndex])

    plt.show()


if __name__ == '__main__':
    print("加載數(shù)據(jù)")
    dataSet = []
    fileIn = open('data\\testData.txt')
    for line in fileIn.readlines():
        lineArr = line.strip().split(' ')
        dataSet.append([float(lineArr[0]), float(lineArr[1])])


    #轉(zhuǎn)化為矩陣
    k = 2
    # centroids = KMeans(n_clusters=k, random_state=9).fit_predict(dataSet)
    clusterAssment = MiniBatchKMeans(n_clusters=k, batch_size=200, random_state=9).fit_predict(dataSet)
    # # 最后結(jié)果
    print(clusterAssment)
    # print("顯示數(shù)據(jù)")
    showCluster(dataSet, k, clusterAssment)

附錄三

基于tensorflow實(shí)現(xiàn)的算法程序

# -*- coding: utf-8 -*-
import tensorflow as tf
import matplotlib.pyplot as plt
import numpy as np

K = 4 # 類別數(shù)目
MAX_ITERS = 1000 # 最大迭代次數(shù)
# MAX_ITERS = 2 # 最大迭代次數(shù)
N = 200 # 樣本點(diǎn)數(shù)目

centers = [[-2, -2], [-2, 1.5], [1.5, -2], [2, 1.5]] # 簇中心

print("1、加載數(shù)據(jù)")
dataSet = []
fileIn = open('data\\testData.txt')
for line in fileIn.readlines():
    lineArr = line.strip().split(' ')
    dataSet.append([float(lineArr[0]), float(lineArr[1])])

N = len(dataSet)

# print("2、數(shù)據(jù)歸一化")
# print(dataSet[0])
# # dataSet = np.mat(dataSet)
# # print(dataSet[0])

#展示數(shù)據(jù)
def showCluster(dataSet, k, clusterAssment):
    dataSet = np.array(dataSet)

    numSamples= np.shape(dataSet)[0]
    dim = np.shape(dataSet)[1]
    if dim != 2:
        print("Sorry! I can not draw because the dimension of your data is not 2!")
        return 1

    mark = ['or', 'ob', 'og', 'ok', '^r', '+r', 'sr', 'dr', '<r', 'pr']
    if k > len(mark):
        print("")
        return 1

    # draw all samples
    for i in range(numSamples):
        markIndex = int(clusterAssment[i])
        plt.plot(dataSet[i, 0], dataSet[i, 1], mark[markIndex])

    plt.show()

# 計(jì)算類內(nèi)平均值函數(shù)
def clusterMean(data, id, num):
    # 第一個(gè)參數(shù)是tensor，第二個(gè)參數(shù)是簇標(biāo)簽，第三個(gè)是簇?cái)?shù)目
    total = tf.unsorted_segment_sum(data, id, num)
    count = tf.unsorted_segment_sum(tf.ones_like(data), id, num)
    return total/count

# 構(gòu)建graph
points = tf.Variable(dataSet)
cluster = tf.Variable(tf.zeros([N], dtype=tf.int64))
# 將原始數(shù)據(jù)前k個(gè)點(diǎn)當(dāng)做初始中心
centers = tf.Variable(tf.slice(points.initialized_value(), [0, 0], [K, 2]))

# 復(fù)制操作，便于矩陣批量計(jì)算距離
repCenters = tf.reshape(tf.tile(centers, [N, 1]), [N, K, 2])
repPoints = tf.reshape(tf.tile(points, [1, K]), [N, K, 2])
# 計(jì)算距離
sumSqure = tf.reduce_sum(tf.square(repCenters-repPoints), reduction_indices=2)
# 尋找最近的簇中心
bestCenter = tf.argmin(sumSqure, axis=1)
# 檢測簇中心是否還在變化
change = tf.reduce_any(tf.not_equal(bestCenter, cluster))
# 計(jì)算簇內(nèi)均值
means = clusterMean(points, bestCenter, K)
# 將粗內(nèi)均值變成新的簇中心，同時(shí)分類結(jié)果也要更新
with tf.control_dependencies([change]):
    # 復(fù)制函數(shù)
    update = tf.group(centers.assign(means), cluster.assign(bestCenter))

with tf.Session() as sess:
    sess.run(tf.initialize_all_variables())
    changed = True
    iterNum = 0
    while changed and iterNum < MAX_ITERS:
        iterNum += 1
        # 運(yùn)行g(shù)raph
        [changed, _] = sess.run([change, update])
        [centersArr, clusterArr] = sess.run([centers, cluster])

    print(clusterArr)
    print(centersArr)
    showCluster(dataSet, K, clusterArr)
        # # 顯示圖像
        # fig, ax = plt.subplots()
        # ax.scatter(dataSet.transpose()[0], dataSet.transpose()[1], marker='o', s=100, c=clusterArr)
        # plt.plot()
        # plt.show()

附錄四

測試數(shù)據(jù)

 1.658985 4.285136
 -3.453687 3.424321
 4.838138 -1.151539
 -5.379713 -3.362104
 0.972564 2.924086
 -3.567919 1.531611
 0.450614 -3.302219
 -3.487105 -1.724432
 2.668759 1.594842
 -3.156485 3.191137
 3.165506 -3.999838
 -2.786837 -3.099354
 4.208187 2.984927
 -2.123337 2.943366
 0.704199 -0.479481
 -0.392370 -3.963704
 2.831667 1.574018
 -0.790153 3.343144
 2.943496 -3.357075
 -3.195883 -2.283926
 2.336445 2.875106
 -1.786345 2.554248
 2.190101 -1.906020
 -3.403367 -2.778288
 1.778124 3.880832
 -1.688346 2.230267
 2.592976 -2.054368
 -4.007257 -3.207066
 2.257734 3.387564
 -2.679011 0.785119
 0.939512 -4.023563
 -3.674424 -2.261084
 2.046259 2.735279
 -3.189470 1.780269
 4.372646 -0.822248
 -2.579316 -3.497576
 1.889034 5.190400
 -0.798747 2.185588
 2.836520 -2.658556
 -3.837877 -3.253815
 2.096701 3.886007
 -2.709034 2.923887
 3.367037 -3.184789
 -2.121479 -4.232586
 2.329546 3.179764
 -3.284816 3.273099
 3.091414 -3.815232
 -3.762093 -2.432191
 3.542056 2.778832
 -1.736822 4.241041
 2.127073 -2.983680
 -4.323818 -3.938116
 3.792121 5.135768
 -4.786473 3.358547
 2.624081 -3.260715
 -4.009299 -2.978115
 2.493525 1.963710
 -2.513661 2.642162
 1.864375 -3.176309
 -3.171184 -3.572452
 2.894220 2.489128
 -2.562539 2.884438
 3.491078 -3.947487
 -2.565729 -2.012114
 3.332948 3.983102
 -1.616805 3.573188
 2.280615 -2.559444
 -2.651229 -3.103198
 2.321395 3.154987
 -1.685703 2.939697
 3.031012 -3.620252
 -4.599622 -2.185829
 4.196223 1.126677
 -2.133863 3.093686
 4.668892 -2.562705
 -2.793241 -2.149706
 2.884105 3.043438
 -2.967647 2.848696
 4.479332 -1.764772
 -4.905566 -2.911070