簡介
k-means算法是1967年由MacQueen首次提出的一種經(jīng)典算法市怎，它是一種基于質(zhì)心的劃分方法，這種方法將簇中所有對象的平均值看作是簇的質(zhì)心，根據(jù)一個(gè)數(shù)據(jù)對象與簇質(zhì)心的距離，將該對象賦予最近的簇苇瓣。在此類方法中，需要給定劃分的簇個(gè)數(shù)k偿乖，首先得到k個(gè)初始劃分的集合击罪，然后采用迭代重定位技術(shù)，通過將對象從一個(gè)簇移到另一個(gè)簇來改進(jìn)劃分的質(zhì)量汹想。
算法
誤差函數(shù)
對于k-means算法外邓，通常使用SSE作為度量質(zhì)量的目標(biāo)函數(shù)，對于相同的k值古掏，更小的SSE表示簇中對象越集中损话。對于不同的k值，越大的k值應(yīng)該對應(yīng)越小的SSE
Python實(shí)現(xiàn)
任意選擇k個(gè)對象作為初始質(zhì)心槽唾，并建立k個(gè)簇
def init_cluster(self):
for i in range(self.k):
c = clusterUnit()
initCentroid = random.choice(self.data)
c.add_node(initCentroid)
self.clusterList.append(c)
定義clusterChange變量丧枪，監(jiān)控聚類是否變化
clusterChange = True
循環(huán)讀取數(shù)據(jù)，通過比對每個(gè)數(shù)據(jù)到k個(gè)簇簇心的距離找出該數(shù)據(jù)所屬的簇庞萍，并使用與數(shù)據(jù)等長的列表來記錄該數(shù)據(jù)所屬的簇拧烦。
for j in range(self.k):
distance = clusterUnit.distance(self.clusterList[j].centroid, data)
if distance < minDist:
minDist = distance
minIndex = j
if int(self.note[i]) != minIndex:
clusterChange = True
if int(self.note[i]) != -1:
self.clusterList[int(self.note[i])].remove_node(data)
self.clusterList[minIndex].add_node(data)
self.note[i] = minIndex
使用鳶尾花的數(shù)據(jù)，調(diào)用可視化方法钝计，可視化每個(gè)循環(huán)后的結(jié)果
輸出SSE值
def calcualte_SSE(self):
sum_SSE = 0
for i in self.clusterList:
sum_SSE += i.SSE()
return sum_SSE
分析
K-means算法描述容易债沮，實(shí)現(xiàn)簡單炼吴，快速，但存在以下不足：
- k需要提前給定
- 算法對初始值選取依賴性極大以及算法常陷入局部最優(yōu)解
- 離群點(diǎn)和噪聲點(diǎn)會(huì)影響簇質(zhì)心偏離
- 不能處理分類屬性的簇
變體
為了解決K-means算法的缺點(diǎn)疫衩，還提出了包括二分-K-means算法硅蹦，k-modes算法，k-prototypes算法闷煤，k-summary算法童芹，k-medoids算法等。
Ref
深入淺出聚類算法之k-means算法
- https://blog.csdn.net/llh_1178/article/details/81633396
- 《數(shù)據(jù)挖掘原理與實(shí)踐》
