簡介
由于傳統(tǒng)的KMeans算法的聚類結(jié)果易受到初始聚類中心點(diǎn)選擇的影響集峦，因此在傳統(tǒng)的KMeans算法的基礎(chǔ)上進(jìn)行算法改進(jìn)，對初始中心點(diǎn)選取比較嚴(yán)格藐吮，各中心點(diǎn)的距離較遠(yuǎn)呼猪，這就避免了初始聚類中心會選到一個(gè)類上，一定程度上克服了算法陷入局部最優(yōu)狀態(tài)怔锌。
二分KMeans(Bisecting KMeans)算法的主要思想是：首先將所有點(diǎn)作為一個(gè)簇寥粹，然后將該簇一分為二变过。之后選擇能最大限度降低聚類代價(jià)函數(shù)（也就是誤差平方和）的簇劃分為兩個(gè)簇。以此進(jìn)行下去排作，直到簇的數(shù)目等于用戶給定的數(shù)目k為止牵啦。以上隱含的一個(gè)原則就是：因?yàn)榫垲惖恼`差平方和能夠衡量聚類性能，該值越小表示數(shù)據(jù)點(diǎn)越接近于他們的質(zhì)心妄痪，聚類效果就越好哈雏。所以我們就需要對誤差平方和最大的簇進(jìn)行再一次劃分，因?yàn)檎`差平方和越大衫生，表示該簇聚類效果越不好裳瘪，越有可能是多個(gè)簇被當(dāng)成了一個(gè)簇，所以我們首先需要對這個(gè)簇進(jìn)行劃分罪针。
二分K-means算法是基于層次的聚類算法
算法
誤差函數(shù)
SSE作為度量質(zhì)量的目標(biāo)函數(shù)彭羹，衡量的是簇的聚類效果，值越小表明簇的中元素分布越緊密
Python實(shí)現(xiàn)
基于K-means的算法進(jìn)行改進(jìn)泪酱，便可以實(shí)現(xiàn)二分K-means算法
脫離循環(huán)的條件變更為獲得k個(gè)簇
while len(self.clusterList) != self.k:
每次都選擇SSE值最大的簇進(jìn)行分裂
for i in self.clusterList:
if i.SSE() > maxSSE:
maxSSE = i.SSE()
tmp_c = i
對該簇進(jìn)行m次K-means算法聚類派殷，分裂成兩個(gè)簇，并從m次聚類中選出生成最小SSE的兩個(gè)簇
# 嘗試ｍ次ＫＭＥＡＮＳ算法
for i in range(self.m):
tmpList = []
tmpNote = np.zeros(tmp_c.node_num) - 1
for i in range(2):
c = clusterUnit()
initcentroid = random.choice(tmp_c.get_node_list())
c.add_node(initcentroid)
tmpList.append(c)
clusterChange = True
while clusterChange == True:
clusterChange = False
for i, data in enumerate(tmp_c.get_node_list()):
minDist = 100000
minIndex = -1
for j in range(2):
distance = clusterUnit.distance(tmpList[j].centroid, data)
if distance < minDist:
minDist = distance
minIndex = j
if int(tmpNote[i]) != minIndex:
clusterChange = True
if int(tmpNote[i]) != -1:
tmpList[int(tmpNote[i])].remove_node(data)
tmpList[minIndex].add_node(data)
tmpNote[i] = minIndex
tmpSSE = sum(i.SSE() for i in tmpList)
# 選出生成最心狗АＳＳＥ的兩個(gè)簇
if tmpSSE < minSSE:
min_cluster_list = tmpList
minSSE = tmpSSE
輸出得到的聚類效果圖
分析
可以發(fā)現(xiàn)毡惜，與K-means相比，二分K-means聚類效果更好斯撮，算法不再受初始化節(jié)點(diǎn)的影響经伙，但算法花銷也更大，對于K值以及m值需要多次調(diào)整才可獲得更好的聚類效果勿锅。
Ref
- https://www.cnblogs.com/eczhou/p/7860435.html
- 《數(shù)據(jù)挖掘原理與實(shí)踐》
