K-Means算法是最古老也是應(yīng)用最廣泛的聚類算法,它使用質(zhì)心定義原型,質(zhì)心是一組點的均值,通常該算法用于n維連續(xù)空間中的對象。
K-Means算法流程
step1:選擇K個點作為初始質(zhì)心
step2:repeat
將每個點指派到最近的質(zhì)心,形成K個簇
重新計算每個簇的質(zhì)心
until 質(zhì)心不在變化
例如下圖的樣本集,初始選擇是三個質(zhì)心比較集中,但是迭代3次之后,質(zhì)心趨于穩(wěn)定,并將樣本集分為3部分
我們對每一個步驟都進行分析
step1:選擇K個點作為初始質(zhì)心
這一步首先要知道K的值,也就是說K是手動設(shè)置的,而不是像EM算法那樣自動聚類成n個簇
其次,如何選擇初始質(zhì)心
最簡單的方式無異于,隨機選取質(zhì)心了,然后多次運行,取效果最好的那個結(jié)果。這個方法,簡單但不見得有效,有很大的可能是得到局部最優(yōu)。
另一種復雜的方式是,隨機選取一個質(zhì)心,然后計算離這個質(zhì)心最遠的樣本點,對于每個后繼質(zhì)心都選取已經(jīng)選取過的質(zhì)心的最遠點。使用這種方式,可以確保質(zhì)心是隨機的,并且是散開的。
step2:repeat
將每個點指派到最近的質(zhì)心,形成K個簇
重新計算每個簇的質(zhì)心
until 質(zhì)心不在變化
如何定義最近的概念,對于歐式空間中的點,可以使用歐式空間,對于文檔可以用余弦相似性等等。對于給定的數(shù)據(jù),可能適應(yīng)與多種合適的鄰近性度量。
標簽:
K-means
Java
數(shù)據(jù)挖掘
聚類
算法
上傳時間:
2018-11-27
上傳用戶:1159474180