簡單介紹：
k-means聚類屬于無監督學習的一種，在沒有給與labels的情況下，将資料分成指定的K類。
它将相似的對象歸到一個簇中，将不相似的對象歸到不同簇中，相似這一概念，取決于所選擇的相似度計算方法。
K-means是發現給定資料集的K個簇的聚類算法，之是以稱之為K均值，是因為他可以發現K個不同的簇，且每個簇的中心采用簇中所含值得均值計算而成。
簇的個數是使用者指定的，每一個簇通過其質心，即簇中所有點的中心來描述。
聚類于分類算法最大的差別在于，分類的目标類别已知，但是聚類目标類别是未知的。
思想：
對于第一張圖一樣的散亂的資料樣本的聚類，首先，假設要聚成兩大團，那麼，随機給兩個點的坐标，如同第二張圖的兩個十字mark,然後第一步就是幫所有點認領歸屬的團，站第一次隊。認領方法是，每個點都算一算自己到這兩個十字mark的距離，認領距離小的那個mark,作為自己的歸屬。好了，第一次站隊完後，形成了第三張圖的局勢。很明顯，現在的十字mark位置已經不合适了，需要重新設定各自陣營自己的mark。遊戲規則是，紅隊陣營所有的點的坐标都來加和求出橫坐标和縱坐标的平均值，這個平均後的坐标位置就是新的mark。當然，藍隊陣營也一樣的進行，選出新的mark。
這次mark和上一次不一樣吧？那說明這次細分有效果了
接下來，進行第二次站隊，也就是所有的點再一次計算和兩個mark的距離，認領新的mark歸屬，好了，新的局勢再次形成，接下來繼續選擇合适的mark新位置，和上次對比發現，依然後變化，恩！那就對了，不斷重複這兩個步驟，直到mark位置幾乎不變，那就完成了聚類過程。
1.載入資料
def loadDataSet(fileName):
'''
加載資料集
:param fileName:
:return:
'''
# 初始化一個空清單
dataSet = []
# 讀取檔案
fr = open(fileName)
# 循環周遊檔案所有行
for line in fr.readlines():
# 切割每一行的資料
curLine = line.strip().split('\t')
# 将資料轉換為浮點類型,便于後面的計算
# fltLine = [float(x) for x in curLine]
# 将資料追加到dataMat
fltLine = list(map(float,curLine)) # 映射所有的元素為 float（浮點數）類型
dataSet.append(fltLine)
# 傳回dataMat
return mat(dataSet)
2.求向量距離
K均值聚類中需要計算資料和質心的距離，常見的距離有歐氏距離(Euclidean distance)和曼哈頓距離(Manhattan distance)，本處采用歐式距離。
def distEclud(vecA, vecB):
'''
歐氏距離計算函數
:param vecA:
:param vecB:
:return:
'''
return sqrt(sum(power(vecA - vecB, 2)))
3.随機生成k個點作為初始質心
def randCent(dataMat, k):
'''
為給定資料集建構一個包含K個随機質心的集合,
随機質心必須要在整個資料集的邊界之内,這可以通過找到資料集每一維的最小和最大值來完成
然後生成0到1.0之間的随機數并通過取值範圍和最小值,以便確定随機點在資料的邊界之内
:param dataMat:
:param k:
:return:
'''
# 擷取樣本數與特征值
m, n = dataMat.shape
# 初始化質心,建立(k,n)個以零填充的矩陣
centroids = mat(zeros((k, n)))
# 循環周遊特征值
for j in range(n):
# 計算每一列的最小值
minJ = min(dataMat[:, j])
# 計算每一列的範圍值
rangeJ = float(max(dataMat[:, j]) - minJ)
# 計算每一列的質心,并将值賦給centroids
centroids[:, j] = mat(minJ + rangeJ * random.rand(k, 1))
# 傳回質心
return centroids
4.K均值聚類算法實作
def kMeans(dataMat, k, distMeas=distEclud, createCent=randCent):
'''
建立K個質心,然後将每個店配置設定到最近的質心,再重新計算質心。
這個過程重複數次,直到資料點的簇配置設定結果不再改變為止
:param dataMat: 資料集
:param k: 簇的數目
:param distMeans: 計算距離
:param createCent: 建立初始質心
:return:
'''
# 擷取樣本數和特征數
m, n = dataMat.shape
# 初始化一個矩陣來存儲每個點的簇配置設定結果
# clusterAssment包含兩個列:一列記錄簇索引值,
# 第二列存儲誤差(誤差是指目前點到簇質心的距離,後面會使用該誤差來評價聚類的效果)
clusterAssment = mat(zeros((m, 2)))
# 建立質心,随機K個質心
centroids = createCent(dataMat, k)
# 初始化标志變量,用于判斷疊代是否繼續,如果True,則繼續疊代
clusterChanged = True
while clusterChanged:
clusterChanged = False
# 周遊所有資料找到距離每個點最近的質心,
# 可以通過對每個點周遊所有質心并計算點到每個質心的距離來完成
for i in range(m):
minDist = inf
minIndex = -1
for j in range(k):
# 計算資料點到質心的距離
# 計算距離是使用distMeas參數給出的距離公式,預設距離函數是distEclud
distJI = distMeas(centroids[j, :], dataMat[i, :])
# 如果距離比minDist(最小距離)還小,更新minDist(最小距離)和最小質心的index(索引)
if distJI < minDist:
minDist = distJI
minIndex = j
# 如果任一點的簇配置設定結果發生改變,則更新clusterChanged标志
if clusterAssment[i, 0] != minIndex: clusterChanged = True
# 更新簇配置設定結果為最小質心的index(索引),minDist(最小距離)的平方
clusterAssment[i, :] = minIndex, minDist ** 2
# print(centroids)
# 周遊所有質心并更新它們的取值
for cent in range(k):
# 通過資料過濾來獲得給定簇的所有點
ptsInClust = dataMat[nonzero(clusterAssment[:, 0].A == cent)[0]]
# 計算所有點的均值,axis=0表示沿矩陣的列方向進行均值計算
centroids[cent, :] = mean(ptsInClust, axis=0)
# 傳回所有的類質心與點配置設定結果
return centroids, clusterAssment
5.資料可視化
def showCluster(dataSet, k, clusterAssment, centroids):
fig = plt.figure()
plt.title("K-means")
ax = fig.add_subplot(111)
data = []
for cent in range(k): #提取出每個簇的資料
ptsInClust = dataSet[nonzero(clusterAssment[:,0].A==cent)[0]] #獲得屬于cent簇的資料
data.append(ptsInClust)
for cent, c, marker in zip( range(k), ['r', 'g', 'b', 'y'], ['^', 'o', '*', 's'] ): #畫出資料點散點圖
ax.scatter(data[cent][:, 0], data[cent][:, 1], s=80, c=c, marker=marker)
ax.scatter(np.array(centroids)[:, 0], np.array(centroids)[:, 1], s=1000, c='black', marker='+', alpha=1) #畫出質心點
ax.set_xlabel('X Label')
ax.set_ylabel('Y Label')
plt.show()
使用K均值算法對測試資料進行聚類，一般情況下效果不錯，各個簇差別明顯，如圖所示：
但是有時候效果就不好了，因為K均值聚類收斂的是局部最小值，而不是全局最小值，如圖所示：
下面的兩類幾乎分到了一起，左上的一類又被分成了兩類，如何解決這個問題呢？二分K均值算法。
一些說明：
- 每次疊代中都要對每一個簇進行劃分，在其中選擇最大程度降低誤差平方和簇進行聚類
- 當使用KMeans()函數且指定的聚類數目為2時，會得到編号為0和1的兩個簇，将編号為0的簇編号改為輸入簇的編号，編号為1的簇編号改為所有簇的數目len(centList)，即在原先簇上追加一個簇
def biKmeans(dataMat, k, distMeas=distEclud):
'''
在給定資料集,所期望的簇數目和距離計算方法的條件下,函數傳回聚類結果
:param dataMat:
:param k:
:param distMeas:
:return:
'''
m, n = dataMat.shape
# 建立一個矩陣來存儲資料集中每個點的簇配置設定結果及平方誤差
clusterAssment = mat(zeros((m, 2)))
# 計算整個資料集的質心,并使用一個清單來保留所有的質心
centroid0 = mean(dataMat, axis=0).tolist()[0]
centList = [centroid0]
# 周遊資料集中所有點來計算每個點到質心的誤內插補點
for j in range(m):
clusterAssment[j, 1] = distMeas(mat(centroid0), dataMat[j, :]) ** 2
# 對簇不停的進行劃分,直到得到想要的簇數目為止
while (len(centList) < k):
# 初始化最小SSE為無窮大,用于比較劃分前後的SSE
lowestSSE = inf
# 通過考察簇清單中的值來獲得目前簇的數目,周遊所有的簇來決定最佳的簇進行劃分
for i in range(len(centList)):
# 對每一個簇,将該簇中的所有點堪稱一個小的資料集
ptsInCurrCluster = dataMat[nonzero(clusterAssment[:, 0].A == i)[0], :]
# 将ptsInCurrCluster輸入到函數kMeans中進行處理,k=2,
# kMeans會生成兩個質心(簇),同時給出每個簇的誤內插補點
centroidMat, splitClustAss = kMeans(ptsInCurrCluster, 2, distMeas)
# 将誤內插補點與剩餘資料集的誤差之和作為本次劃分的誤差
sseSplit = sum(splitClustAss[:, 1])
sseNotSplit = sum(clusterAssment[nonzero(clusterAssment[:, 0].A != i)[0], 1])
print('sseSplit, and notSplit: ', sseSplit, sseNotSplit)
# 如果本次劃分的SSE值最小,則本次劃分被儲存
if (sseSplit + sseNotSplit) < lowestSSE:
bestCentToSplit = i
bestNewCents = centroidMat
bestClustAss = splitClustAss.copy()
lowestSSE = sseSplit + sseNotSplit
# 找出最好的簇配置設定結果
# 調用kmeans函數并且指定簇數為2時,會得到兩個編号分别為0和1的結果簇
bestClustAss[nonzero(bestClustAss[:, 0].A == 1)[0], 0] = len(centList)
# 更新為最佳質心
bestClustAss[nonzero(bestClustAss[:, 0].A == 0)[0], 0] = bestCentToSplit
print('the bestCentToSplit is: ', bestCentToSplit)
print('the len of bestClustAss is: ', len(bestClustAss))
# 更新質心清單
# 更新原質心list中的第i個質心為使用二分kMeans後bestNewCents的第一個質心
centList[bestCentToSplit] = bestNewCents[0, :].tolist()[0]
# 添加bestNewCents的第二個質心
centList.append(bestNewCents[1, :].tolist()[0])
# 重新配置設定最好簇下的資料(質心)以及SSE
clusterAssment[nonzero(clusterAssment[:, 0].A == bestCentToSplit)[0], :] = bestClustAss
return mat(centList), clusterAssment
二分K均值之是以穩定，是由于初始質心不再是随機生成K個，而是基于全部資料的平均值先生成一個質心，然後基于最優的方法分裂成2個質心，然後再對現有的2個判斷下哪個簇的誤差較大，将其再分裂成2個。如此n+1+1+1每次優化分裂一個簇，直到達到k個簇結束優化。
機器學習實戰中最後給了一個案例介紹聚類的一個應用場景，小夥伴們要出去遊玩，選擇了幾個地方，想打車到幾個地方的中心點後步行前往，給出最優路線。
采用二分K-均值法本身不難，我卻被其中另一個問題給考倒了，因為獲得的地點是經緯度坐标，如何求地球媽媽球面積上坐标之間的距離？
https://www.cnblogs.com/softfair/p/distance_of_two_latitude_and_longitude_points.html
這個小夥伴講的很透徹了，基本是就是利用平面的問題去求解立體的問題，原理圖如下：
代碼中需要添加一個求坐标距離的輔助函數：
def distSLC(vecA, vecB):
'''
傳回地球表面兩點間的距離,機關是英裡
給定兩個點的經緯度,可以使用球面餘弦定理來計算亮點的距離
:param vecA:
:param vecB:
:return:
'''
# 經度和次元用角度作為機關,但是sin()和cos()以弧度為輸入.
# 可以将江都除以180度然後再誠意圓周率pi轉換為弧度
a = sin(vecA[0, 1] * pi / 180) * sin(vecB[0, 1] * pi / 180)
b = cos(vecA[0, 1] * pi / 180) * cos(vecB[0, 1] * pi / 180) * cos(pi * (vecB[0, 0] - vecA[0, 0]) / 180)
return arccos(a + b) * 6371.0
利用二分K-均值求質心，然後将結果展示到地圖上：
def clusterClubs(fileName, imgName, numClust=5):
'''
将文本檔案的解析,聚類以及畫圖都封裝在一起
:param fileName: 文本資料路徑
:param imgName: 圖檔路徑
:param numClust: 希望得到的簇數目
:return:
'''
# 建立一個空清單
datList = []
# 打開文本檔案擷取第4列和第5列,這兩列分别對應次元和經度,然後将這些值封裝到datList
for line in open(fileName).readlines():
lineArr = line.split('\t')
datList.append([float(lineArr[4]), float(lineArr[3])])
datMat = mat(datList)
# 調用biKmeans并使用distSLC函數作為聚類中使用的距離計算方式
myCentroids, clustAssing = biKmeans(datMat, numClust, distMeas=distSLC)
# 建立一幅圖和一個舉行,使用該矩形來決定繪制圖的哪一部分
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)
# 使用imread函數基于一幅圖像來建立矩陣
imgP = plt.imread(imgName)
# 使用imshow繪制該矩陣
ax0.imshow(imgP)
# 再同一幅圖上繪制一張新圖,允許使用兩套坐标系統并不做任何縮放或偏移
ax1 = fig.add_axes(rect, label='ax1', frameon=False)
# 周遊每一個簇并将它們一一畫出來,标記類型從前面建立的scatterMarkers清單中得到
for i in range(numClust):
ptsInCurrCluster = datMat[nonzero(clustAssing[:, 0].A == i)[0], :]
# 使用索引i % len(scatterMarkers)來選擇标記形狀,這意味這當有更多簇時,可以循環使用這标記
markerStyle = scatterMarkers[i % len(scatterMarkers)]
# 使用十字标記來表示簇中心并在圖中顯示
ax1.scatter(ptsInCurrCluster[:, 0].flatten().A[0], ptsInCurrCluster[:, 1].flatten().A[0], marker=markerStyle,
s=90)
ax1.scatter(myCentroids[:, 0].flatten().A[0], myCentroids[:, 1].flatten().A[0], marker='+', s=300)
plt.show()
fileName='./kmeans/places.txt'
imgName='./kmeans/Portland.png'
clusterClubs(fileName, imgName, numClust=5)
sklearn中的K-Means
sklearn.cluster
sklearn.cluster
sklearn.cluster.
k_means
-
Parameters: X : array-like or sparse matrix, shape (n_samples, n_features) The observations to cluster.
n_clusters : intThe number of clusters to form as well as the number of centroids to generate.
init : {‘k-means++’, ‘random’, or ndarray, or a callable}, optional
precompute_distances : {‘auto’, True, False}Method for initialization, default to ‘k-means++’:
‘k-means++’ : selects initial cluster centers for k-mean clustering in a smart way to speed up convergence. See section Notes in k_init for more details.
‘random’: generate k centroids from a Gaussian with mean and variance estimated from the data.
If an ndarray is passed, it should be of shape (n_clusters, n_features) and gives the initial centers.
If a callable is passed, it should take arguments X, k and and a random state and return an initialization.
n_init : int, optional, default: 10Precompute distances (faster but takes more memory).
‘auto’ : do not precompute distances if n_samples * n_clusters > 12 million. This corresponds to about 100MB overhead per job using double precision.
True : always precompute distances
False : never precompute distances
Number of time the k-means algorithm will be run with different centroid seeds. The final results will be the best output of n_init consecutive runs in terms of inertia.
max_iter : int, optional, default 300Maximum number of iterations of the k-means algorithm to run.
verbose : boolean, optionalVerbosity mode.
tol : float, optionalThe relative increment in the results before declaring convergence.
random_state : int, RandomState instance or None, optional, default: NoneIf int, random_state is the seed used by the random number generator; If RandomState instance, random_state is the random number generator; If None, the random number generator is the RandomState instance used by np.random.
copy_x : boolean, optionalWhen pre-computing distances it is more numerically accurate to center the data first. If copy_x is True, then the original data is not modified. If False, the original data is modified, and put back before the function returns, but small numerical differences may be introduced by subtracting and then adding the data mean.
n_jobs : int
algorithm : “auto”, “full” or “elkan”, default=”auto”The number of jobs to use for the computation. This works by computing each of the n_init runs in parallel.
If -1 all CPUs are used. If 1 is given, no parallel computing code is used at all, which is useful for debugging. For n_jobs below -1, (n_cpus + 1 + n_jobs) are used. Thus for n_jobs = -2, all CPUs but one are used.
K-means algorithm to use. The classical EM-style algorithm is “full”. The “elkan” variation is more efficient by using the triangle inequality, but currently doesn’t support sparse data. “auto” chooses “elkan” for dense data and “full” for sparse data.
return_n_iter : bool, optionalWhether or not to return the number of iterations.
Returns: centroid : float ndarray with shape (k, n_features) Centroids found at the last iteration of k-means.
label : integer ndarray with shape (n_samples,)label[i] is the code or index of the centroid the i’th observation is closest to.
inertia : floatThe final value of the inertia criterion (sum of squared distances to the closest centroid for all observations in the training set).
best_n_iter : intNumber of iterations corresponding to the best results. Returned only if return_n_iter is set to True.
import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans
# 加載資料集
dataMat = []
fr = open("E:\python_code\Python_algorithm\ml\MachineLearning-master\input/10.KMeans/testSet.txt") # 注意，這個是相對路徑，請保證是在 MachineLearning 這個目錄下執行。
for line in fr.readlines():
curLine = line.strip().split('\t')
fltLine = list(map(float,curLine)) # 映射所有的元素為 float（浮點數）類型
dataMat.append(fltLine)
# 訓練模型
km = KMeans(n_clusters=4) # 初始化
km.fit(dataMat) # 拟合
km_pred = km.predict(dataMat) # 預測
print(km_pred)
centers = km.cluster_centers_ # 質心
# 可視化結果
plt.scatter(np.array(dataMat)[:, 1], np.array(dataMat)[:, 0], c=km_pred)
plt.scatter(centers[:, 1], centers[:, 0], c="r")
plt.show()