【機器學習】k-means聚類原理及python實現

【機器學習】k-means聚類原理及python實現

【機器學習】k-means聚類原理及python實現

1、k-means原理

2、改進的kmenas——-二分k-means

3、例項—-對地圖上的點進行聚類

              本節完整程式碼可戳:https://github.com/LisaPig/machineLearning/tree/master/k_means

        聚類是一種無監督的學習,它將相似的物件歸到同一個簇中。它有點像全自動分類。聚類方法幾乎可以應用於所有物件,簇內的物件越相似,聚類的效果越好。本章要學習一種稱為K-均值( K-means)聚類的演算法。之所以稱之為K-均值是因為它可以發現k個不同的簇,且每個簇的中心採用簇中所含值的均值計算而成。下面會逐步介紹該演算法的更多細節。
 

一、k-means原理

        K-均值是發現給定資料集的k個簇的演算法。簇個數k是使用者給定的,每一個簇通過其質心( 即簇中所有點的中心)來描述。

1. K-均值演算法的工作流程?

        首先,隨機確定k個初始點作為質心。然後將資料集中的每個點分配到一個簇中,具體來講,為每個點找距其最近的質心,並將其分配給該質心所對應的簇。這一步完成之後,每個簇的質心更新為該簇所有點的平均值。
        上述過程的虛擬碼表示如下:
                       建立k個點作為起始質心(經常是隨機選擇)
                       當任意一個點的簇分配結果發生改變時
                                對資料集中的每個資料點
                                        對每個質心
                                                計算質心與資料點之間的距離
                                        將資料點分配到距其最近的簇
                                對每一個簇,計算簇中所有點的均值並將均值作為質心

程式碼實現:


 

2、K-均值聚類的優缺點
        優點:容易實現。
        缺點:可能收斂到區域性最小值,在大規模資料集上收斂較慢。
        適用資料型別:數值型資料。

3、聚類和分類的區別?

         聚類與分類的最大不同在於,分類的目標事先已知,而聚類則不一樣。因為其產生的結果與分類相同,而只是類別沒有預先定義,聚類有時也被稱為無監督分類( unsupervisedclassification)。
 

4.最基本的k-means函式實現聚類:

# -*- coding:utf-8 -*-
"""
@author:Lisa
@file:k_means.py
@time:2018/7/14 0014下午 8:27
"""
from numpy import *
import numpy as np
import matplotlib.pyplot as plt
import matplotlib
"""
函式:讀取資料集檔案
輸出:讀取到的資料集(列表形式)
"""
def loadDataSet(filename):
dataMat=[]
fr=open(filename)
for line in fr.readlines():
curLine=line.strip().split('\t')
floatLine=list(map(float,curLine) )   #將每一行的資料對映成float型
dataMat.append(floatLine)
return dataMat
"""
函式:計算歐式兩個向量之間的距離
輸入:兩個向量vecA、vecB
"""
def distEclud(vecA,vecB):
return np.sqrt(np.sum(np.power(vecA-vecB , 2)))
"""
函式:k個質心隨機初始化
返回值:隨機初始化的k個質心資料點
說明:此函式為k-means函式初始化k個質心
注意:質心的每一維度的取值範圍應 確保在資料的邊界之內
"""
def randCentroids(dataSet,k):
m,n=np.shape(dataSet)
centroids=np.mat(np.zeros( (k,n)))
for i in range(n):
minI=np.min(dataSet[:,i])
rangeI=float( np.max(dataSet[:,i]) - minI)
centroids[:,i]=minI  rangeI*np.random.rand(k,1)
return centroids
"""
函式:k-means函式
說明:此為kmeans最基本的函式,後續會在此基礎上有改進版----二分K-Means
"""
def k_means(dataSet,k,distCompute=distEclud,creatCentroids=randCentroids):
m,n=np.shape(dataSet)
clusterAssign=np.mat(np.zeros( (m,2))) #儲存分配的簇和誤差
centroids=creatCentroids(dataSet,k)
clusterChanged=True
clusChangedCount=0
#為每個樣本分配簇,直到簇分配不發生變化-》穩定態
while clusterChanged:
clusterChanged =False
clusChangedCount =clusChangedCount 1
for i in range(m):
minDist = np.Inf
minIndex = -1
for j in range(k):
dist=distCompute(centroids[j,:],dataSet[i,:])
if dist<minDist:
minDist=dist
minIndex=j
if clusterAssign[i,0]!=minIndex:
clusterChanged = True
clusterAssign[i,0]=minIndex
clusterAssign[i,1]=minDist**2  #SSE:均方誤差
print("第%d次分配簇的結果為:" %(clusChangedCount))
print(centroids)
#重新計算質心:每一次有樣本簇變化,都要重新計算質心
# 1.找到所有屬於第i簇的樣本
# 2.計算該簇的樣本均值,作為質心
for i in range(k):
samplesI = dataSet[ np.nonzero(clusterAssign[:,0].A== i )[0] ]
centroids[i,:]=np.mean(samplesI,axis=0)  #按列求均值
print( '\n')
# draw(dataSet,centroids,clusterAssign,clusChangedCount)
return centroids,clusterAssign
"""
函式:繪製簇分類結果
"""
def draw(dataMat,centroids,clusterAssign,k):
# 指定預設字型
matplotlib.rcParams['font.sans-serif'] = ['SimHei']  # 顯示漢字
matplotlib.rcParams['axes.unicode_minus'] = False  # 能夠顯示符號(負號)
colors=['r','g','b','yellow','black','pink']
plt.figure(1)
#繪製質心
for i in range(k):
plt.scatter(x=centroids[i,0],y=centroids[i,1],marker='*',color=colors[i])
#繪製資料點
m=np.shape(dataMat)[0]
for j in range(m):
colorJ=int( clusterAssign[j, 0] )
plt.scatter(x=dataMat[j,0],y=dataMat[j,1],c=colors[colorJ])
plt.show()
if __name__ =="__main__":
dataSet=loadDataSet("data\\testSet.txt")
dataMat=np.mat(dataSet)
centroids,clusterAssign=k_means(dataMat,k=4)#bi_K_means(dataMat,3)
draw(dataMat,centroids,clusterAssign,4)

分類結果:

                                         

 

         考慮上圖中testSet.txt(4類)的聚類結果,還是挺好的。但是在一個包含三個簇的資料集上執行K-均值演算法之後的結果,點的簇分配結果值沒有那麼準確,如下圖。 K-均值演算法收斂但聚類效果較差的原因是, K-均值演算法收斂到了區域性最小值,而非全域性最小值(區域性最小值指結果還可以但並非最好結果,全域性最小值是可能的最好結果)。
 

                                          

      5、那麼,如何評價聚類結果好壞?

      一種用於度量聚類效果的指標是SSE( Sum of Squared Error,誤差平方和),對應程式中clusterAssment矩陣的第一列之和。 SSE值越小表示資料點越接近於它們的質心,聚類效果越好。因為對誤差取了平方,因此更加重視那些遠離中心的點。

       一種肯定可以降低SSE值的方法是增加簇的個數,但這違背了聚類的目標。聚類的目標是在保持簇數目不變的情況下提高簇的質量。
 

      6、那麼,如何解決k-means不能收斂到全域性最小值的問題?

     那麼如何對上圖的結果進行改進?可以對生成的簇進行後處理,一種方法是將具有最大SSE值的簇劃分成兩個簇。具體實現時可以將最大簇包含的點過濾出來並在這些點上執行K-均值(k=2)
 

二、改進版kmeans——–二分k-means

          為克服K-均值演算法收斂於區域性最小值的問題,有人提出了另一個稱為二分K-均值( bisecting K-means)的演算法。該演算法首先將所有點作為一個簇,然後將該簇一分為二。之後選擇其中一個簇繼續進行劃分,選擇哪一個簇進行劃分取決於對其劃分是否可以最大程度降低SSE的值。上述基於SSE的劃分過程不斷重複,直到得到使用者指定的簇數目為止。
        二分K-均值演算法的虛擬碼形式如下:
             將所有點看成一個簇
             當簇數目小於k時

                     對於每一個簇
                               計算總誤差
                               在給定的簇上面進行K-均值聚類( k=2)
                               計算將該簇一分為二之後的總誤差
                      選擇使得誤差最小的那個簇進行劃分操作

程式碼實現:

"""
函式:二分K-Means聚類演算法
說明:是在基本k-means演算法的基礎上改進的二分k-means演算法->優點是可以避免陷入區域性最小值,而非全域性最小值
演算法步驟: 
1.將所有點看成一個簇,求質心
2.當簇數目小於k時
對於每一個簇
計算總誤差
在給定的簇上面進行k-均值聚類(k=2),即一分為2
計算將該簇一分為二後的總誤差
選擇使得誤差最小的那個簇進行劃分操作
"""
def bi_K_means(dataSet,k,distCompute=distEclud):
m,n=np.shape(dataSet)
#初始化
clusterAssign=np.mat(np.zeros( (m,2) ))
#建立初始的一個簇
centroid0=np.mean(dataSet,axis=0).tolist()[0]
centroidList=[centroid0]
#繪製初始劃分簇
draw(dataSet, np.mat(centroidList), clusterAssign, k=len(centroidList))
for i in range(k):
clusterAssign[i,1]=distCompute(np.mat(centroid0), dataSet[i,:]) **2
while (len(centroidList)<k ):
sseMin=np.inf
for i in range(len(centroidList)):
curCluster=dataSet[np.nonzero(clusterAssign[:,0].A== i)[0],:]
#為每一簇進行二分類
centroidMat,splitClustAssign=k_means(curCluster,k=2)
sseSplit=sum(splitClustAssign[:,1])   #當前劃分簇的sse誤差
sseNotSplit=sum(clusterAssign[np.nonzero(clusterAssign[:,0].A!= i)[0],1]) #非當前劃分簇的sse誤差
print("sseSplit: %d, sseNotSplit: %d" %(sseSplit,sseNotSplit))
if (sseSplit sseNotSplit) < sseMin:
bestClustToSplit=i
bestCentroid=centroidMat
bestClustAssign=splitClustAssign.copy()
sseMin=sseSplit sseNotSplit
#根據誤差最小的那個簇進行劃分操作
#print(bestClustToSplit,bestCentroid)
bestClustAssign[np.nonzero(bestClustAssign[:,0].A ==1)[0],0]=len(centroidList)
bestClustAssign[np.nonzero(bestClustAssign[:,0].A ==0)[0],0]= bestClustToSplit
#print("the best clust to split is: %d" %(bestClustToSplit))
#print('the len of bestClustAssign is: ' ,(bestClustAssign))
centroidList[bestClustToSplit]=bestCentroid[0,:].tolist()[0]  #caution!
#centroidList.append(bestCentroid[0,:].tolist()[0])  #error
centroidList.append(bestCentroid[1,:].tolist()[0])
print('len of centroids is : %d' %(len(centroidList)))
clusterAssign[np.nonzero(clusterAssign[:,0].A==bestClustToSplit)[0],:]=bestClustAssign
#繪製劃分過程
draw(dataSet,np.mat(centroidList),clusterAssign,k=len(centroidList))
return np.mat(centroidList),clusterAssign

實現聚類的結果:

              

二分k_means分類過程展示:(完整劃分過程)

完整程式碼可戳:https://github.com/LisaPig/machineLearning/tree/master/k_means

三、例項—-對地圖上的點進行聚類

例項—-對俄勒岡州波特蘭市夜生活娛樂地點進行聚類

            有一個包含格式化地理座標的列表(places.txt),接下來可以對這些俱樂部進行聚類。(此處省去了《機器學習實戰》中的獲取地理座標等步驟,直接從書中得到places.txt這一處理後的包含地理座標的列表檔案)。

           注意:繪製結果圖時,為了畫出這些簇,首先建立一幅圖和一個矩形,然後使用該矩形來決定繪製圖的哪一部分。接下來構建一個標記形狀的列表用於繪製散點圖。後邊會使用唯一的標記來標識每個簇。下一步使用imread()函式基於一幅影象來建立矩陣 ,然後使用imshow()繪製該矩陣。接下來,在同一幅圖上繪製一張新的圖,這允許你使用兩套座標系統並且不做任何縮放或偏移。緊接著,遍歷每一個簇並將它們一一畫出來。標記型別從前面建立的scatterMarkers列表中得到。使用索引i % len(scatterMarkers)來選擇標記形狀 ,這意味著當有更多簇時,可以迴圈使用這些標記。最後使用十字標記來表示簇中心並在圖中顯示

程式碼:

# -*- coding:utf-8 -*-
"""
@author:Lisa
@file:cluster_example.py
@note:利用k-means實現地理座標的聚類
@time:2018/7/16 0016下午 9:39
"""
import numpy as np
import matplotlib
import matplotlib.pyplot as plt
from k_means import *
"""
函式:球面距離計算
原理:利用球面餘弦定理計算球面上兩點的距離
"""
def distSLC(vecA,vecB):
a=np.sin(vecA[0,1]*np.pi/180) *np.sin(vecB[0,1]*np.pi/180)
b=np.cos(vecA[0,1]*np.pi/180) *np.cos(vecB[0, 1] * np.pi /180)*\
np.cos(np.pi*vecB[0,0]-vecA[0,0])/180
return np.arccos(a b)*6371.0
"""
函式:從檔案中讀取資料列表
注意:要根據文字格式來讀取
"""
def loadSet(fileName):
dataList=[]
fr=open(fileName)
for line in fr.readlines():
curLine=line.split('\t')
dataList.append([ float(curLine[4]),float(curLine[3])]) #第4和5列分別代表緯度和經度
return np.mat(dataList)
"""
函式:繪製聚類點分佈
"""
def draw(dataMat,centroids,clustAssign,k):
fig = plt.figure()
rect = [0.1, 0.1, 0.8, 0.8]  # 建立矩形
# 建立不同標記圖案
scatterMarkers = ['s', 'o', '^', '8', 'p', \
'd', 'v', 'h', '>', '<']
axprops = dict(xticks=[], yticks=[])
ax0 = fig.add_axes(rect, label='ax0', **axprops)
imgP = plt.imread('data\\Portland.png')  # 匯入地圖
ax0.imshow(imgP)
ax1 = fig.add_axes(rect, label='ax1', frameon=False)
for i in range(k):
ptsInCurrCluster = dataMat[np.nonzero(clustAssign[:, 0].A == i)[0], :]
markerStyle = scatterMarkers[i % len(scatterMarkers)]
ax1.scatter(ptsInCurrCluster[:, 0].flatten().A[0], ptsInCurrCluster[:, 1].flatten().A[0], marker=markerStyle,
s=90)
ax1.scatter(centroids[:, 0].flatten().A[0], centroids[:, 1].flatten().A[0], marker=' ', s=300)
plt.show()
if __name__=='__main__':
dataMat=loadSet('data\\places.txt')
k=3
centroids,clusterAssign=bi_K_means(dataMat,k)
draw(dataMat,centroids,clusterAssign,k)

聚類結果:(k=5)

                            

(K=3):

                             

      k值不同,聚類結果不同,可多試幾次,尋找最佳k值。

—————————————————————-    end    ——————————————————————

參考:

1、《機器學習實戰》

2、https://blog.csdn.net/sinat_17196995/article/details/70332664