python實現(xiàn)kMeans算法
聚類是一種無監(jiān)督的學習,將相似的對象放到同一簇中,有點像是全自動分類,簇內的對象越相似,簇間的對象差別越大,則聚類效果越好。
1、k均值聚類算法
k均值聚類將數(shù)據(jù)分為k個簇,每個簇通過其質心,即簇中所有點的中心來描述。首先隨機確定k個初始點作為質心,然后將數(shù)據(jù)集分配到距離最近的簇中。然后將每個簇的質心更新為所有數(shù)據(jù)集的平均值。然后再進行第二次劃分數(shù)據(jù)集,直到聚類結果不再變化為止。
偽代碼為
隨機創(chuàng)建k個簇質心
當任意一個點的簇分配發(fā)生改變時:
對數(shù)據(jù)集中的每個數(shù)據(jù)點:
對每個質心:
計算數(shù)據(jù)集到質心的距離
將數(shù)據(jù)集分配到最近距離質心對應的簇
對每一個簇,計算簇中所有點的均值并將均值作為質心
python實現(xiàn)
import numpy as np import matplotlib.pyplot as plt def loadDataSet(fileName): dataMat = [] with open(fileName) as f: for line in f.readlines(): line = line.strip().split('\t') dataMat.append(line) dataMat = np.array(dataMat).astype(np.float32) return dataMat def distEclud(vecA,vecB): return np.sqrt(np.sum(np.power((vecA-vecB),2))) def randCent(dataSet,k): m = np.shape(dataSet)[1] center = np.mat(np.ones((k,m))) for i in range(m): centmin = min(dataSet[:,i]) centmax = max(dataSet[:,i]) center[:,i] = centmin + (centmax - centmin) * np.random.rand(k,1) return center def kMeans(dataSet,k,distMeans = distEclud,createCent = randCent): m = np.shape(dataSet)[0] clusterAssment = np.mat(np.zeros((m,2))) centroids = createCent(dataSet,k) clusterChanged = True while clusterChanged: clusterChanged = False for i in range(m): minDist = np.inf minIndex = -1 for j in range(k): distJI = distMeans(dataSet[i,:],centroids[j,:]) if distJI < minDist: minDist = distJI minIndex = j if clusterAssment[i,0] != minIndex: clusterChanged = True clusterAssment[i,:] = minIndex,minDist**2 for cent in range(k): ptsInClust = dataSet[np.nonzero(clusterAssment[:,0].A == cent)[0]] centroids[cent,:] = np.mean(ptsInClust,axis = 0) return centroids,clusterAssment data = loadDataSet('testSet.txt') muCentroids, clusterAssing = kMeans(data,4) fig = plt.figure(0) ax = fig.add_subplot(111) ax.scatter(data[:,0],data[:,1],c = clusterAssing[:,0].A) plt.show() print(clusterAssing)
2、二分k均值算法
K均值算法可能會收斂到局部最小值,而非全局最小。一種用于度量聚類效果的指標為誤差平方和(SSE)。因為取了平方,更加重視原理中心的點。為了克服k均值算法可能會收斂到局部最小值的問題,有人提出來二分k均值算法。
首先將所有點作為一個簇,然后將該簇一分為二,然后選擇所有簇中對其劃分能夠最大程度減低SSE的值的簇,直到滿足指定簇數(shù)為止。
偽代碼
將所有點看成一個簇
計算SSE
while 當簇數(shù)目小于k時:
for 每一個簇:
計算總誤差
在給定的簇上進行k均值聚類(k=2)
計算將該簇一分為二的總誤差
選擇使得誤差最小的那個簇進行劃分操作
python實現(xiàn)
import numpy as np import matplotlib.pyplot as plt def loadDataSet(fileName): dataMat = [] with open(fileName) as f: for line in f.readlines(): line = line.strip().split('\t') dataMat.append(line) dataMat = np.array(dataMat).astype(np.float32) return dataMat def distEclud(vecA,vecB): return np.sqrt(np.sum(np.power((vecA-vecB),2))) def randCent(dataSet,k): m = np.shape(dataSet)[1] center = np.mat(np.ones((k,m))) for i in range(m): centmin = min(dataSet[:,i]) centmax = max(dataSet[:,i]) center[:,i] = centmin + (centmax - centmin) * np.random.rand(k,1) return center def kMeans(dataSet,k,distMeans = distEclud,createCent = randCent): m = np.shape(dataSet)[0] clusterAssment = np.mat(np.zeros((m,2))) centroids = createCent(dataSet,k) clusterChanged = True while clusterChanged: clusterChanged = False for i in range(m): minDist = np.inf minIndex = -1 for j in range(k): distJI = distMeans(dataSet[i,:],centroids[j,:]) if distJI < minDist: minDist = distJI minIndex = j if clusterAssment[i,0] != minIndex: clusterChanged = True clusterAssment[i,:] = minIndex,minDist**2 for cent in range(k): ptsInClust = dataSet[np.nonzero(clusterAssment[:,0].A == cent)[0]] centroids[cent,:] = np.mean(ptsInClust,axis = 0) return centroids,clusterAssment def biKmeans(dataSet,k,distMeans = distEclud): m = np.shape(dataSet)[0] clusterAssment = np.mat(np.zeros((m,2))) centroid0 = np.mean(dataSet,axis=0).tolist() centList = [centroid0] for j in range(m): clusterAssment[j,1] = distMeans(dataSet[j,:],np.mat(centroid0))**2 while (len(centList)<k): lowestSSE = np.inf for i in range(len(centList)): ptsInCurrCluster = dataSet[np.nonzero(clusterAssment[:,0].A == i)[0],:] centroidMat,splitClustAss = kMeans(ptsInCurrCluster,2,distMeans) sseSplit = np.sum(splitClustAss[:,1]) sseNotSplit = np.sum(clusterAssment[np.nonzero(clusterAssment[:,0].A != i)[0],1]) if (sseSplit + sseNotSplit) < lowestSSE: bestCentToSplit = i bestNewCents = centroidMat.copy() bestClustAss = splitClustAss.copy() lowestSSE = sseSplit + sseNotSplit print('the best cent to split is ',bestCentToSplit) # print('the len of the bestClust') bestClustAss[np.nonzero(bestClustAss[:,0].A == 1)[0],0] = len(centList) bestClustAss[np.nonzero(bestClustAss[:,0].A == 0)[0],0] = bestCentToSplit clusterAssment[np.nonzero(clusterAssment[:,0].A == bestCentToSplit)[0],:] = bestClustAss.copy() centList[bestCentToSplit] = bestNewCents[0,:].tolist()[0] centList.append(bestNewCents[1,:].tolist()[0]) return np.mat(centList),clusterAssment data = loadDataSet('testSet2.txt') muCentroids, clusterAssing = biKmeans(data,3) fig = plt.figure(0) ax = fig.add_subplot(111) ax.scatter(data[:,0],data[:,1],c = clusterAssing[:,0].A,cmap=plt.cm.Paired) ax.scatter(muCentroids[:,0],muCentroids[:,1]) plt.show() print(clusterAssing) print(muCentroids)
代碼及數(shù)據(jù)集下載:K-means
以上就是本文的全部內容,希望對大家的學習有所幫助,也希望大家多多支持腳本之家。
相關文章
Keras自定義實現(xiàn)帶masking的meanpooling層方式
這篇文章主要介紹了Keras自定義實現(xiàn)帶masking的meanpooling層方式,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧2020-06-06使用python設置Excel工作表網(wǎng)格線的隱藏與顯示
Excel表格界面的直觀性很大程度上得益于表格中的網(wǎng)格線設計,這些線條幫助用戶精確對齊數(shù)據(jù),清晰劃分單元格,本文將介紹如何使用Python設置隱藏或顯示Excel工作表的網(wǎng)格線,實現(xiàn)自動話及批量處理,感興趣的朋友可以參考下2024-06-06