聚類演算法——K-Means原理、k選擇、質心初始化、Python實現
引入
聚類
是一種無監督學習，將
相似
的樣本（物件/例項）歸到同一簇（cluster）中。通常用樣本的
相似度
或
距離
來衡量。eg：天空中的星星，靠得近的星星可以被歸為一個星團，而星團之間的星星距離比較遠。（
）
簇內的物件越相似，聚類的效果越好。
硬聚類：一個樣本只能屬於一個類。
軟聚類：一個樣本可以以機率屬於多個類。
聚類與分類的不同：分類為監督，是監督學習，目標事先已知；而聚類的“類”沒有預先定義，是從資料中自動發現的，是無監督學習。也就是說，聚類問題中，給我們的樣本只用x，沒有y。
k-means表示：該演算法可以發現k個不同的簇，且每個簇的中心採用簇內所含值的均值計算而成。屬於硬聚類。。常見的聚類演算法還有：層次聚類。
K-means演算法
1967年MacQueen提出
流程
K-means缺點
K的選擇需要事先預定。
K個初始質心的位置選擇對聚類結果和執行時間都有很大影響。
不能保證全域性最優，可能是區域性最優解。
K-means改進
如何確定K？
一、手肘法
思想：隨著聚類數K的增大，樣本劃分更加精細，那麼所有樣本的聚類誤差（SSE）會逐漸變小：
——當K值小於真實聚類數時，K的增加會對聚類效果產生很大影響，故SSE下降幅度很大；
——當K值大於真實聚類數時，K的增加不會對聚類效果產生很大影響，故SSE下降幅度將會趨於平緩；整個SSE-K圖為一個手肘型。
圖片來源
二、輪廓係數法
思想：類中樣本距離越近，類間樣本距離越遠，聚類效果越好。用平均輪廓係數來衡量。
類中不相似度：ai的平均，體現凝聚度。ai表示樣本xi到同類中其他樣本的平均距離。ai越小，表明類中樣本不相似度越低，凝聚度越高，越應該聚為一類。（among）
類間不相似度：bi的最小值，體現分離度。bi表示樣本xi到其他類中所有樣本的平均距離。bi越大，表明內間不相似程度越高，分離度越高，越不應該聚為一個類。（between）。最近類：
Dk為要找的最近類，x是最近類裡的全部樣本，n是最近類裡的全部樣本的個數。
某一個樣本點xi的輪廓係數：
選SSE還是輪廓係數？
通常選用SSE：舉例和解釋可以參照這裡
如何初始化質心
K-means++
隨機初始化質心可能導致演算法迭代很慢，K-means++是對K-mean隨機初始化質心的一個最佳化，具體步驟如下：
隨機選取一個點作為第一個聚類中心。
計算所有樣本與第一個聚類中心的距離。
選擇出上一步中距離最大的點作為第二個聚類中心。
迭代：計算所有點到與之最近的聚類中心的距離，選取最大距離的點作為新的聚類中心。
終止條件：直到選出了這k箇中心。
只需要隨機取第一個聚類中心即可。
然後按照最遠優先原則來選新的聚類中心
如何克服區域性最優解
K-means例項應用——Python實現
import
numpy
as
np
def
loadDataSet
（
fileName
）：
‘’‘
：param fileName： 檔名字
：return： 矩陣
’‘’
dataMat
=
［］
fr
=
open
（
fileName
）
for
line
in
fr
。
readlines
（）：
curLine
=
line
。
strip
（）
。
split
（
‘
\t
’
）
fltLine
=
list
（
map
（
float
，
curLine
））
dataMat
。
append
（
fltLine
）
return
dataMat
def
distEclud
（
vecA
，
vecB
）：
return
np
。
sqrt
（
np
。
sum
（
np
。
power
（
vecA
-
vecB
，
2
）））
def
randCent
（
dataSet
，
k
）：
‘’‘
構建一個包含k個隨機質心的集合（k行n列，n表示資料的維度/特徵個數），
只需要保證質心在資料邊界裡面就可以了
：param dataSet： 輸入資料集
：param k： 質心個數
：return：
’‘’
# 得到資料樣本的維度
n
=
np
。
shape
（
dataSet
）［
1
］
# 初始化為一個（k，n）的全零矩陣
centroids
=
np
。
mat
（
np
。
zeros
（（
k
，
n
）））
# 遍歷資料集的每一個維度
for
j
in
range
（
n
）：
# 得到該列資料的最小值，最大值
minJ
=
np
。
min
（
dataSet
［：，
j
］）
maxJ
=
np
。
max
（
dataSet
［：，
j
］）
# 得到該列資料的範圍（最大值-最小值）
rangeJ
=
float
（
maxJ
-
minJ
）
# k個質心向量的第j維資料值隨機為位於（最小值，最大值）內的某一值
centroids
［：，
j
］
=
minJ
+
rangeJ
*
np
。
random
。
rand
（
k
，
1
）
# random。rand（行，列）產生這個形狀的矩陣，且每個元素in ［0，1）
# 返回初始化得到的k個質心向量
return
centroids
def
kMeans
（
dataSet
，
k
，
distMeas
=
distEclud
，
createCent
=
randCent
）：
‘’‘
：param dataSet： 輸入的資料集
：param k： 聚類的個數，可調
：param distMeas： 計算距離的方法，可調
：param createCent： 初始化質心的位置的方法，可調
：return： k個類質心的位置座標，樣本所處的類&到該類質心的距離
’‘’
# 獲取資料集樣本數
m
=
np
。
shape
（
dataSet
）［
0
］
# 初始化一個（m，2）全零矩陣，用來記錄沒一個樣本所屬類，距離類中心的距離
clusterAssment
=
np
。
mat
（
np
。
zeros
（（
m
，
2
）））
# 建立初始的k個質心向量
centroids
=
createCent
（
dataSet
，
k
）
# 聚類結果是否發生變化的布林型別
clusterChanged
=
True
# 終止條件：所有資料點聚類結果不發生變化
while
clusterChanged
：
# 聚類結果變化布林型別置為False
clusterChanged
=
False
# 遍歷資料集每一個樣本向量
for
i
in
range
（
m
）：
# 初始化最小距離為正無窮，最小距離對應的索引為-1
minDist
=
float
（
‘inf’
）
minIndex
=
-
1
# 迴圈k個類的質心
for
j
in
range
（
k
）：
# 計算資料點到質心的歐氏距離
distJI
=
distMeas
（
centroids
［
j
，
：］，
dataSet
［
i
，
：］）
# 如果距離小於當前最小距離
if
distJI
<
minDist
：
# 當前距離為最小距離，最小距離對應索引應為j（第j個類）
minDist
=
distJI
minIndex
=
j
# 當前聚類結果中第i個樣本的聚類結果發生變化：布林值置為True，繼續聚類演算法
if
clusterAssment
［
i
，
0
］
！=
minIndex
：
clusterChanged
=
True
# 更新當前變化樣本的聚類結果和平方誤差
clusterAssment
［
i
，
：］
=
minIndex
，
minDist
**
2
# 列印k-means聚類的質心
# print（centroids）
# 遍歷每一個質心
for
cent
in
range
（
k
）：
# 將資料集中所有屬於當前質心類的樣本透過條件過濾篩選出來
ptsInClust
=
dataSet
［
np
。
nonzero
（
clusterAssment
［：，
0
］
。
A
==
cent
）［
0
］］
# 計算這些資料的均值（axis=0：求列均值），作為該類質心向量
centroids
［
cent
，
：］
=
np
。
mean
（
ptsInClust
，
axis
=
0
）
# 返回k個聚類，聚類結果及誤差
return
centroids
，
clusterAssment
import matplotlib。pyplot as plt
def plotDataSet（filename）：
# 匯入資料
datMat = np。mat（loadDataSet（filename））
# 進行k-means演算法其中k為4
myCentroids， clustAssing = kMeans（datMat， 4）
clustAssing = clustAssing。tolist（）
myCentroids = myCentroids。tolist（）
xcord = ［［］， ［］， ［］， ［］］
ycord = ［［］， ［］， ［］， ［］］
datMat = datMat。tolist（）
m = len（clustAssing）
for i in range（m）：
if int（clustAssing［i］［0］） == 0：
xcord［0］。append（datMat［i］［0］）
ycord［0］。append（datMat［i］［1］）
elif int（clustAssing［i］［0］） == 1：
xcord［1］。append（datMat［i］［0］）
ycord［1］。append（datMat［i］［1］）
elif int（clustAssing［i］［0］） == 2：
xcord［2］。append（datMat［i］［0］）
ycord［2］。append（datMat［i］［1］）
elif int（clustAssing［i］［0］） == 3：
xcord［3］。append（datMat［i］［0］）
ycord［3］。append（datMat［i］［1］）
fig = plt。figure（）
ax = fig。add_subplot（111）
# 繪製樣本點
ax。scatter（xcord［0］， ycord［0］， s=20， c=‘b’， marker=‘*’， alpha=。5）
ax。scatter（xcord［1］， ycord［1］， s=20， c=‘r’， marker=‘D’， alpha=。5）
ax。scatter（xcord［2］， ycord［2］， s=20， c=‘c’， marker=‘>’， alpha=。5）
ax。scatter（xcord［3］， ycord［3］， s=20， c=‘k’， marker=‘o’， alpha=。5）
# 繪製質心
ax。scatter（myCentroids［0］［0］， myCentroids［0］［1］， s=100， c=‘k’， marker=‘+’， alpha=。5）
ax。scatter（myCentroids［1］［0］， myCentroids［1］［1］， s=100， c=‘k’， marker=‘+’， alpha=。5）
ax。scatter（myCentroids［2］［0］， myCentroids［2］［1］， s=100， c=‘k’， marker=‘+’， alpha=。5）
ax。scatter（myCentroids［3］［0］， myCentroids［3］［1］， s=100， c=‘k’， marker=‘+’， alpha=。5）
plt。title（‘DataSet’）
plt。xlabel（‘X’）
plt。show（）
————————————————-【補充】呼叫程式碼和資料集————————————————-
# 測試一下函式
dataMat
=
np
。
mat
（
loadDataSet
（
‘testSet。txt’
））
（
‘min x：
%f
’
%
min
（
dataMat
［：，
0
］））
（
‘min y：
%f
’
%
min
（
dataMat
［：，
1
］））
（
‘max x：
%f
’
%
max
（
dataMat
［：，
0
］））
（
‘man y：
%f
’
%
max
（
dataMat
［：，
1
］））
for
i
in
range
（
10
）：
testRandCent
=
randCent
（
dataMat
，
2
）
（
‘No
%d
random center is ’
%
i
）
（
testRandCent
）
# 測試歐幾里得距離函式
（
distEclud
（
dataMat
［
0
］，
dataMat
［
1
］））
myCentroids
，
clustAssing
=
kMeans
（
dataMat
，
4
）
（
myCentroids
）
（
clustAssing
）
dataMat2
=
np
。
mat
（
loadDataSet
（
‘testSet2。txt’
））
myCentroids2
，
clustAssing2
=
kMeans
（
dataMat2
，
4
）
（
myCentroids2
）
（
clustAssing2
）
（
‘SSE of simple k-means：
%f
’
%
sum
（
clustAssing2
［：，
1
］））
sumSSE
=
0
for
i
in
range
（
40
）：
myCentroids2
，
clustAssing2
=
kMeans
（
dataMat2
，
4
）
sumSSE
+=
sum
（
clustAssing2
［：，
1
］）
avgSSE
=
sumSSE
/
40
（
‘Avg（40） SSE of simple k-means：
%f
’
%
avgSSE
）
plotDataSet
（
‘testSet。txt’
）
plotDataSet
（
‘testSet2。txt’
）
testSet。txt
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
testSet2。txt
3。275154 2。957587
-3。344465 2。603513
0。355083 -3。376585
1。852435 3。547351
-2。078973 2。552013
-0。993756 -0。884433
2。682252 4。007573
-3。087776 2。878713
-1。565978 -1。256985
2。441611 0。444826
-0。659487 3。111284
-0。459601 -2。618005
2。177680 2。387793
-2。920969 2。917485
-0。028814 -4。168078
3。625746 2。119041
-3。912363 1。325108
-0。551694 -2。814223
2。855808 3。483301
-3。594448 2。856651
0。421993 -2。372646
1。650821 3。407572
-2。082902 3。384412
-0。718809 -2。492514
4。513623 3。841029
-4。822011 4。607049
-0。656297 -1。449872
1。919901 4。439368
-3。287749 3。918836
-1。576936 -2。977622
3。598143 1。975970
-3。977329 4。900932
-1。791080 -2。184517
3。914654 3。559303
-1。910108 4。166946
-1。226597 -3。317889
1。148946 3。345138
-2。113864 3。548172
0。845762 -3。589788
2。629062 3。535831
-1。640717 2。990517
-1。881012 -2。485405
4。606999 3。510312
-4。366462 4。023316
0。765015 -3。001270
3。121904 2。173988
-4。025139 4。652310
-0。559558 -3。840539
4。376754 4。863579
-1。874308 4。032237
-0。089337 -3。026809
3。997787 2。518662
-3。082978 2。884822
0。845235 -3。454465
1。327224 3。358778
-2。889949 3。596178
-0。966018 -2。839827
2。960769 3。079555
-3。275518 1。577068
0。639276 -3。412840
這個資料集比較理想，聚類情況比較好。但是對於有些資料集，由於K值選擇、初始點隨機選擇這些很有可能導致演算法產生區域性最優解。
這一副圖透過同一個資料集，多次呼叫上述K-means演算法，但是產生了不同的效果。
一些問題
初始設定k=4，為什麼到了後面怎麼只聚成了3個類？
為什麼有些大一點的cluster分成了兩類？有些是一類？
都是因為隨機初始點造成的！！
接下來需要解決的問題（見下一篇文章）
怎麼避免由於隨機化初始點而造成的區域性最優解問題？上面有提到K-means++是一種解決辦法。
如何實現選取最佳K的程式碼？
講解影片請移步：
參考文獻
1。 Peter Harrington。 機器學習實戰［M］。 河北： 人民郵電出版社， 2019。
2。 李航。 統計學習方法第二版。 北京： 清華大學出版社， 2019。
2。
https：//www。
cnblogs。com/pinard/p/61
64214。html
3。
https：//www。
cnblogs。com/jerrylead/a
rchive/2011/04/06/2006910。html
4。 如何選擇k：
https：//
blog。csdn。net/qq_157385
01/article/details/79036255
5。 輪廓係數：
https：//
blog。csdn。net/wangxiaop
eng0329/article/details/53542606
6。 Iris實現輪廓係數選k（R）：
http：//
studio。galaxystatistics。com
/report/cluster_analysis/article4/
7。 Python3程式碼參考：
https：//
github。com/wzy6642/Mach
ine-Learning-in-Action-Python3/blob/master/K_Means_Project1/K_Means。py