K均值聚類算法概述

<i id='kLXLe'></i>

K-means算法是硬聚類算法，是典型的基于原型的目標函數聚類方法的代表，它是數據點到原型的某種距離作為優化的目標函數，利用函數求極值的方法得到迭代運算的調整規則。

K-means算法是很典型的基于距離的聚類算法，采用距離作為相似性的評價指標，即認為兩個對象的距離越近，其相似度就越大。該算法認為簇是由距離靠近的對象組成的，因此把得到緊湊且獨立的簇作為最終目標。

聚類算法與分類算法最大的不同在于，分類的類別是事先已知的，而聚類則不同，因為它產生的結果與分類相同，只是沒有預先定義的類別，因此也可稱聚類為無監督分類。

K均值聚類算法分析

k-means算法是一種基于樣本間相似性度量的間接聚類方法，此算法以k為參數，把n 個對象分為k個簇，以使簇內具有較高的相似度，而且簇間的相似度較低。

相似度的計算根據一個簇中對象的平均值（被看作簇的重心）來進行。此算法首先隨機選擇k個對象，每個對象代表一個聚類的質心。對于其余的每一個對象，根據該對象與各聚類質心之間的距離，把它分配到與之最相似的聚類中。然后，計算每個聚類的新質心。重復上述過程，直到準則函數會聚。

k-means算法是一種較典型的逐點修改迭代的動態聚類算法，其要點是以誤差平方和為準則函數。逐點修改類中心：一個象元樣本按某一原則，歸屬于某一組類后，就要重新計算這個組類的均值，并且以新的均值作為凝聚中心點進行下一次象元素聚類；逐批修改類中心：在全部象元樣本按某一組的類中心分類之后，再計算修改各類的均值，作為下一次分類的凝聚中心點。

K均值聚類算法步驟

算法過程如下：

1）從N個文檔隨機選取K個文檔作為質心
2）對剩余的每個文檔測量其到每個質心的距離，并把它歸到最近的質心的類
3）重新計算已經得到的各個類的質心
4）迭代2～3步直至新的質心與原質心相等或小于指定閾值，算法結束

具體如下：

輸入：k, data[n];
（1） 選擇k個初始中心點，例如c[0]=data[0],…c[k-1]=data[k-1]；
（2） 對于data[0]….data[n]，分別與c[0]…c[k-1]比較，假定與c[i]差值最少，就標記為i；
（3） 對于所有標記為i點，重新計算c[i]={ 所有標記為i的data[j]之和}/標記為i的個數；
（4） 重復(2)(3)，直到所有c[i]值的變化小于給定閾值。

K均值聚類算法使用示例

接下來使用python編寫k-means算法例子 首先從文件加載數據集

# 從文本中構建矩陣，加載文本文件，然后處理
def loadDataSet(fileName):    # 通用函數，用來解析以 tab 鍵分隔的 floats（浮點數），例如: 1.658985	4.285136
    dataMat = []
    fr = open(fileName)
    for line in fr.readlines():
        curLine = line.strip().split('\t')
        fltLine = map(float,curLine)    # 映射所有的元素為 float（浮點數）類型
        dataMat.append(fltLine)
    return dataMat

然后計算兩個向量的歐氏距離

# 計算兩個向量的歐式距離（可根據場景選擇）
def distEclud(vecA, vecB):
    return sqrt(sum(power(vecA - vecB, 2))) # la.norm(vecA-vecB)

構建一個包含 K 個隨機質心的集合

# 為給定數據集構建一個包含 k 個隨機質心的集合。隨機質心必須要在整個數據集的邊界之內，這可以通過找到數據集每一維的最小和最大值來完成。然后生成 0~1.0 之間的隨機數并通過取值范圍和最小值，以便確保隨機點在數據的邊界之內。
def randCent(dataSet, k):
    n = shape(dataSet)[1] # 列的數量
    centroids = mat(zeros((k,n))) # 創建k個質心矩陣
    for j in range(n): # 創建隨機簇質心，并且在每一維的邊界內
        minJ = min(dataSet[:,j])    # 最小值
        rangeJ = float(max(dataSet[:,j]) - minJ)    # 范圍 = 最大值 - 最小值
        centroids[:,j] = mat(minJ + rangeJ * random.rand(k,1))    # 隨機生成
    return centroids

K-Means 聚類算法

# k-means 聚類算法
# 該算法會創建k個質心，然后將每個點分配到最近的質心，再重新計算質心。
# 這個過程重復數次，直到數據點的簇分配結果不再改變位置。
# 運行結果（多次運行結果可能會不一樣，可以試試，原因為隨機質心的影響，但總的結果是對的， 因為數據足夠相似，也可能會陷入局部最小值）
def kMeans(dataSet, k, distMeas=distEclud, createCent=randCent):
    m = shape(dataSet)[0]    # 行數
    clusterAssment = mat(zeros((m, 2)))    # 創建一個與 dataSet 行數一樣，但是有兩列的矩陣，用來保存簇分配結果
    centroids = createCent(dataSet, k)    # 創建質心，隨機k個質心
    clusterChanged = True
    while clusterChanged:
        clusterChanged = False
        for i in range(m):    # 循環每一個數據點并分配到最近的質心中去
            minDist = inf; minIndex = -1
            for j in range(k):
                distJI = distMeas(centroids[j,:],dataSet[i,:])    # 計算數據點到質心的距離
                if distJI < minDist:    # 如果距離比 minDist（最小距離）還小，更新 minDist（最小距離）和最小質心的 index（索引）
                    minDist = distJI; minIndex = j
            if clusterAssment[i, 0] != minIndex:    # 簇分配結果改變
                clusterChanged = True    # 簇改變
                clusterAssment[i, :] = minIndex,minDist**2    # 更新簇分配結果為最小質心的 index（索引），minDist（最小距離）的平方
        print centroids
        for cent in range(k): # 更新質心
            ptsInClust = dataSet[nonzero(clusterAssment[:, 0].A==cent)[0]] # 獲取該簇中的所有點
            centroids[cent,:] = mean(ptsInClust, axis=0) # 將質心修改為簇中所有點的平均值，mean 就是求平均值的
    return centroids, clusterAssment