電子發(fā)燒友App
KMeans算法是最常用的聚類算法，主要思想是：在給定K值和K個(gè)初始類簇中心點(diǎn)的情況下，把每個(gè)點(diǎn)（亦即數(shù)據(jù)記錄）分到離其最近的類簇中心點(diǎn)所代表的類簇中，所有點(diǎn)分配完畢之后，根據(jù)一個(gè)類簇內(nèi)的所有點(diǎn)重新計(jì)算該類簇的中心點(diǎn)（取平均值），然后再迭代的進(jìn)行分配點(diǎn)和更新類簇中心點(diǎn)的步驟，直至類簇中心點(diǎn)的變化很小，或者達(dá)到指定的迭代次數(shù)。
KMeans算法本身思想比較簡(jiǎn)單，但是合理的確定K值和K個(gè)初始類簇中心點(diǎn)對(duì)于聚類效果的好壞有很大的影響。
1. 確定K個(gè)初始類簇中心點(diǎn)
最簡(jiǎn)單的確定初始類簇中心點(diǎn)的方法是隨機(jī)選擇K個(gè)點(diǎn)作為初始的類簇中心點(diǎn)，但是該方法在有些情況下的效果較差，如下（下圖中的數(shù)據(jù)是用五個(gè)二元正態(tài)高斯分布生成的，顏色代表聚類效果）：
《大數(shù)據(jù)》一書中提到K個(gè)初始類簇點(diǎn)的選取還有兩種方法：
1）選擇彼此距離盡可能遠(yuǎn)的K個(gè)點(diǎn)
2）先對(duì)數(shù)據(jù)用層次聚類算法或者Canopy算法進(jìn)行聚類，得到K個(gè)簇之后，從每個(gè)類簇中選擇一個(gè)點(diǎn)，該點(diǎn)可以是該類簇的中心點(diǎn)，或者是距離類簇中心點(diǎn)最近的那個(gè)點(diǎn)。
1） 選擇批次距離盡可能遠(yuǎn)的K個(gè)點(diǎn)
首先隨機(jī)選擇一個(gè)點(diǎn)作為第一個(gè)初始類簇中心點(diǎn)，然后選擇距離該點(diǎn)最遠(yuǎn)的那個(gè)點(diǎn)作為第二個(gè)初始類簇中心點(diǎn)，然后再選擇距離前兩個(gè)點(diǎn)的最近距離最大的點(diǎn)作為第三個(gè)初始類簇的中心點(diǎn)，以此類推，直至選出K個(gè)初始類簇中心點(diǎn)。
該方法經(jīng)過我測(cè)試效果很好，用該方法確定初始類簇點(diǎn)之后運(yùn)行KMeans得到的結(jié)果全部都能完美區(qū)分五個(gè)類簇：
2） 選用層次聚類或者Canopy算法進(jìn)行初始聚類，然后利用這些類簇的中心點(diǎn)作為KMeans算法初始類簇中心點(diǎn)。
常用的層次聚類算法有BIRCH和ROCK，在此不作介紹，下面簡(jiǎn)單介紹一下Canopy算法，主要摘自Mahout的Wiki：
首先定義兩個(gè)距離T1和T2，T1》T2.從初始的點(diǎn)的集合S中隨機(jī)移除一個(gè)點(diǎn)P，然后對(duì)于還在S中的每個(gè)點(diǎn)I，計(jì)算該點(diǎn)I與點(diǎn)P的距離，如果距離小于T1，則將點(diǎn)I加入到點(diǎn)P所代表的Canopy中，如果距離小于T2，則將點(diǎn)I從集合S中移除，并將點(diǎn)I加入到點(diǎn)P所代表的Canopy中。迭代完一次之后，重新從集合S中隨機(jī)選擇一個(gè)點(diǎn)作為新的點(diǎn)P，然后重復(fù)執(zhí)行以上步驟。
Canopy算法執(zhí)行完畢后會(huì)得到很多Canopy，可以認(rèn)為每個(gè)Canopy都是一個(gè)Cluster，與KMeans等硬劃分算法不同，Canopy的聚類結(jié)果中每個(gè)點(diǎn)有可能屬于多個(gè)Canopy。我們可以選擇距離每個(gè)Canopy的中心點(diǎn)最近的那個(gè)數(shù)據(jù)點(diǎn)，或者直接選擇每個(gè)Canopy的中心點(diǎn)作為KMeans的初始K個(gè)類簇中心點(diǎn)。
K值的確定。
《大數(shù)據(jù)》中提到：給定一個(gè)合適的類簇指標(biāo)，比如平均半徑或直徑，只要我們假設(shè)的類簇的數(shù)目等于或者高于真實(shí)的類簇的數(shù)目時(shí)，該指標(biāo)上升會(huì)很緩慢，而一旦試圖得到少于真實(shí)數(shù)目的類簇時(shí)，該指標(biāo)會(huì)急劇上升。
類簇的直徑是指類簇內(nèi)任意兩點(diǎn)之間的最大距離。
類簇的半徑是指類簇內(nèi)所有點(diǎn)到類簇中心距離的最大值。
廢話少說，上圖。下圖是當(dāng)K的取值從2到9時(shí)，聚類效果和類簇指標(biāo)的效果圖：
左圖是K取值從2到7時(shí)的聚類效果，右圖是K取值從2到9時(shí)的類簇指標(biāo)的變化曲線，此處我選擇類簇指標(biāo)是K個(gè)類簇的平均質(zhì)心距離的加權(quán)平均值。從上圖中可以明顯看到，當(dāng)K取值5時(shí)，類簇指標(biāo)的下降趨勢(shì)最快，所以K的正確取值應(yīng)該是5.為以下是具體數(shù)據(jù)：
《span style=“background-color： white;”》2 個(gè)聚類
所有類簇的半徑的加權(quán)平均值 8.51916676443
所有類簇的平均質(zhì)心距離的加權(quán)平均值 4.82716260322
3 個(gè)聚類
所有類簇的半徑的加權(quán)平均值 7.58444829472
所有類簇的平均質(zhì)心距離的加權(quán)平均值 3.37661824845
4 個(gè)聚類
所有類簇的半徑的加權(quán)平均值 5.65489660064
所有類簇的平均質(zhì)心距離的加權(quán)平均值 2.22135360453
5 個(gè)聚類
所有類簇的半徑的加權(quán)平均值 3.67478798553
所有類簇的平均質(zhì)心距離的加權(quán)平均值 1.25657641195
6 個(gè)聚類
所有類簇的半徑的加權(quán)平均值 3.44686996398
所有類簇的平均質(zhì)心距離的加權(quán)平均值 1.20944264145
7 個(gè)聚類
所有類簇的半徑的加權(quán)平均值 3.3036641135
所有類簇的平均質(zhì)心距離的加權(quán)平均值 1.16653919186
8 個(gè)聚類
所有類簇的半徑的加權(quán)平均值 3.30268530308
所有類簇的平均質(zhì)心距離的加權(quán)平均值 1.11361639906
9 個(gè)聚類
所有類簇的半徑的加權(quán)平均值 3.17924400582
所有類簇的平均質(zhì)心距離的加權(quán)平均值 1.07431888569《/span》
uk是第k 個(gè)類的重心位置。成本函數(shù)是各個(gè)類畸變程度（distortions）之和。每個(gè)類的畸變程度等于該類重心與其內(nèi)部成員位置距離的平方和。若類內(nèi)部的成員彼此間越緊湊則類的畸變程度越小，反之，若類內(nèi)部的成員彼此間越分散則類的畸變程度越大。求解成本函數(shù)最小化的參數(shù)就是一個(gè)重復(fù)配置每個(gè)類包含的觀測(cè)值，并不斷移動(dòng)類重心的過程。
#-*- coding:utf-8 -*-
import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans
from scipy.spatial.distance import cdist
import sys
reload（sys）
sys.setdefaultencoding（‘utf-8’）
x = np.array（［1， 2， 3， 1， 5， 6， 5， 5， 6， 7， 8， 9， 7， 9］）
y = np.array（［1， 3， 2， 2， 8， 6， 7， 6， 7， 1， 2， 1， 1， 3］）
data = np.array（list（zip（x， y）））
# 肘部法則 求解最佳分類數(shù)
# K-Means參數(shù)的最優(yōu)解也是以成本函數(shù)最小化為目標(biāo)
# 成本函數(shù)是各個(gè)類畸變程度（distortions）之和。每個(gè)類的畸變程度等于該類重心與其內(nèi)部成員位置距離的平方和
‘’‘’‘a(chǎn)a=［］
K = range（1， 10）
for k in range（1，10）：
kmeans=KMeans（n_clusters=k）
kmeans.fit（data）
aa.append（sum（np.min（cdist（data， kmeans.cluster_centers_， ’euclidean‘），axis=1））/data.shape［0］）
plt.figure（）
plt.plot（np.array（K）， aa， ’bx-‘）
plt.show（）’‘’
#繪制散點(diǎn)圖及聚類結(jié)果中心點(diǎn)
plt.figure（）
plt.axis（［0， 10， 0， 10］）
plt.grid（True）
plt.plot（x，y，‘k.’）
kmeans=KMeans（n_clusters=3）
kmeans.fit（data）
plt.plot（kmeans.cluster_centers_［：，0］，kmeans.cluster_centers_［：，1］，‘r.’）
plt.show（）
工商網(wǎng)監(jiān)
評(píng)論