K-Means聚類的Python實踐
K-Means應該是最簡單的聚類算法之一了吧，理論上很簡單，就是隨即初始化幾個中心點，不斷的把他們周圍的對象聚集起來，然后根據這群對象的重置中心點，不斷的迭代，最終找到最合適的幾個中心點，就算完成了。
然后，真正實踐的時候才會思考的更加深入一點，比如本文的實踐內容就是一個失敗的案例（算法是成功的，場景是失敗的）。
什么是聚類
簡單的說，就是對于一組不知道分類標簽的數據，可以通過聚類算法自動的把相似的數據劃分到同一個分類中。即聚類與分類的區別主要在于，聚類可以不必知道源數據的標簽信息。
K-Means（K均值）
K均值是一種比較簡單的聚類算法，下圖是來自wiki：
從圖中可以看出，K-Means首先在空間中隨機選取三個點（彩色的），這些點可以是某個數據點所在的位置，也可以是純粹的空間隨機點。然后類似拉幫結派一樣，到自己附近“抓人”。第一輪抓完之后形成了三個穩定的新“幫派”，這時候每一個幫派由于成員發生了變化，大家就重新投票選擇新的“核心”，也就是中間點。選好新的核心之后，這個核心就又開始新一輪的拉幫結派。然后不斷的循環迭代，直到整個空間穩定時停止。
K-Means算法描述
上面對K-Means的介紹已經比較詳細了，現在，如果把K-Means算法總結成算法描述，其實只需要四步驟：
- 任意選擇k個點，作為初始的聚類中心。
- 遍歷每個對象，分別對每個對象求他們與k個中心點的距離，把對象劃分到與他們最近的中心所代表的類別中去，這一步我們稱之為“劃分”。
- 對于每一個中心點，遍歷他們所包含的對象，計算這些對象所有維度的和的中值，獲得新的中心點。
- 計算當前狀態下的損失(用來計算損失的函數叫做Cost Function，即價值函數)，如果當前損失比上一次迭代的損失相差大于某一值（如1），則繼續執行第2、3步，知道連續兩次的損失差為某一設定值為止（即達到最優，通常設為1）。
距離函數
計算距離有很多種方式，我這里使用的是最簡單的歐氏距離。
損失函數（Cost Function）
每一次選取好新的中心點，我們就要計算一下當前選好的中心點損失為多少，這個損失代表著偏移量，越大說明當前聚類的效果越差，計算公式稱為（Within-Cluster Sum of Squares, WCSS）：
其中，$ x_{i} $ 表示某一對象，$c_{k}$表示該對象所屬類別的中心點。整個式子的含義就是對各個類別下的對象，求對象與中心點的歐式距離的平方，把所有的平方求和就是$L(C)$。
評價標準
采用聚類的數據，通常沒有已知的數據分類標簽，所以通常就不能用監督學習中的正確率、精確度、召回度來計算了（如果有分類標簽的話，也是可以計算的）。
常用于聚類效果評價的指標為：Davies Bouldin Index，它的表達式可以寫為：
其中，$ rho_{i} $和 $ rho_{j} $ 都表示i,j兩個分類中的所有對象到中心點的平均距離。而分母中的$c_{i}$和分別表示i,j兩個分類的中心點之間的距離。整個表達式的含義就是，聚類效果越好，兩個分類間的距離應該越遠，分類內部越密集。
Python實踐
#### 一、數據準備 — 如之前所寫的樸素貝葉斯分類詳解一樣，我們的第一步依然是進行數據準備，所不同的是，由于我們不再需要對模型進行訓練，所以不必拆分原始數據為訓練和測試兩部分。
數據向量化
這部分是要格外注意的，要根據不同的數據使用不同的度量單位，比如我們現在是對新聞進行聚類，最初我使用的是，每一個單詞作為一個向量，單詞的頻度就是該維度上的值，但是后來發現結果非常差，經過請教前輩，發現對新聞聚類最好不要使用詞頻，而且要拋出新聞長度對結果的影響。
舉個例子：假如一個新聞A包含Google，Baidu兩個詞各一次，而B分別包含兩個單詞歌兩次，那么實際上他們屬于同一種分類的概率應該是一樣的，也就是距離為0才對。
另外，即便是不使用詞頻，也要注意拋棄總長度對結果的影響，比如A（Google,Baidu），而B是(Google,Baidu,Netease)，那么A、B的歐式長度分別是根號2和根號3，這也不合理，我們需要正規化操作，讓他們的歐氏距離總長度都相等（參看我代碼里的normalize函數）。
二、初始化隨機點
我們的新聞數據已知屬于5個類別，所以我們就初始設定5個隨機點，我使用了random.random()函數來隨機選擇，具體代碼在initCenters函數部分。
在初始化過程完成的工作有：
- 第一次設定初始聚類中心
- 第一次為這些中心點分配對象
- 分配對象完成之后進行重新定位中心點
- 對定位后的中心點計算損失函數
三、迭代進行K-Means優化
如上面介紹K-Means算法的時候提到的，這部分需要不斷的重新劃分對象，重新定位中心點和計算損失函數，然后根據損失函數與上一次的對比決定是不是要繼續迭代。
這部分代碼在start函數內。
四、Cost Function
具體損失函數如何計算的，之前是在costFunction內，但是我發現分配對象到中心點的時候，可以順便把損失計算出來，為了提升性能，我把costFunction的代碼合并到了split函數內。
下面是完整的程序代碼：
#!/usr/bin/env python
#coding:utf-8
import os
import random
import math
class Center(object):
def __init__(self, vector):
self.vector = vector
self.objects = []
class Vector(object):
"""單個數據記錄的向量表示"""
def __init__(self, label):
# 由于當前向量比較稀疏，所以使用字典而非數組來表示
self.words = {}
self.label = label
def loadFromFile(self, file_name, word_dict):
with open(file_name,'r') as f:
words = f.read().split()
for wordin words:
if wordnot in word_dict:
word_dict[word] = len(word_dict)
word_id = word_dict[word]
self.words[word_id] = 1
def addToNearestCenter(self, centers):
nearest = centers[0]
d = self.distance(centers[0].vector)
for centerin centers[1:]:
new_d = self.distance(center.vector)
if new_d < d:
d = new_d
nearest = center
nearest.objects.append(self)
"""
計算兩個向量之間的歐幾里得距離,注意數據維度上的值非常稀疏.
"""
def distance(self, vector):
square_sum = 0.0
for wordin vector.words:
if wordnot in self.words:
a = vector.words[word]
square_sum += math.pow(a, 2)
if wordin self.words:
a,b = vector.words[word],self.words[word]
square_sum += math.pow((a-b), 2)
for wordin self.words:
if wordnot in vector.words:
a = self.words[word]
square_sum += math.pow(a, 2)
result = math.sqrt(square_sum)
return result
class KMeans(object):
""" 準備數據，把新聞數據向量化"""
def __init__(self, dir_name):
self.word_dict = {}
self.vectors = []
self.dir_name = dir_name
# {'file_name':{word:3,word:4}}
self.centers = []
# 上一次中心點的損失
self.last_cost = 0.0
# 從指定目錄加載文件
for file_namein os.listdir(dir_name):
v = Vector(file_name)
v.loadFromFile(dir_name+'/'+file_name, self.word_dict)
self.vectors.append(v)
""" 分配初始中心點,計算初始損失，并開始聚類 """
def start(self, class_num):
# 從現有的所有文章中，隨機選出class_num個點作為初始聚類中心
for vectorin random.sample(self.vectors, class_num):
c = Center(vector)
self.centers.append(c)
# 初始劃分，并計算初始損失
print 'init center points'
self.split()
self.locateCenter()
self.last_cost = self.costFunction()
print 'start optimization'
# 開始進行優化，不斷的進行三步操作：劃分、重新定位中心點、最小化損失
i = 0
while True:
i += 1
print '第 ',i,' 次優化:'
self.split()
self.locateCenter()
current_cost = self.costFunction()
print '損失降低(上一次 - 當前)：',self.last_cost,' - ',current_cost,' = ',(self.last_cost - current_cost)
if self.last_cost - current_cost <= 1:
break
else:
self.last_cost = current_cost
# 迭代優化損失函數，當損失函數與上一次損失相差非常小的時候，停止優化
count = 0
for centerin self.centers:
count += 1
print '第', count, '組:'
for s in ['business','it','sports','yule','auto']:
s_count = 0
for vectorin center.objects:
if vector.label.find(s) > 0:
s_count += 1
print s,' = ',s_count
print '---------------------------------------'
"""
根據每個聚類的中心點，計算每個對象與這些中心的距離，根據最小距離重新劃分每個對象所屬的分類
"""
def split(self):
print '劃分對象... Objects : ', len(self.vectors)
# 先清空上一次中心點表里的對象數據，需要重新劃分
for centerin self.centers:
center.objects = []
# 遍歷所有文件并分配向量到最近的中心點區域
for vectorin self.vectors:
vector.addToNearestCenter(self.centers)
""" 重新獲得劃分對象后的中心點 """
def locateCenter(self):
# 遍歷中心點，使用每個中心點所包含的文件重新求中心點
count = 0
for centerin self.centers:
count += 1
print '計算第 ', count, ' 類的新中心點...'
files_count = float(len(center.objects))
# 新的中心點，格式為 {word1:0,word2:5...}
new_center = {}
# 遍歷所有該中心包含的文件
for vectorin center.objects:
# 遍歷該文件包含的單詞
for wordin vector.words:
if wordnot in new_center:
new_center[word] = 1
else:
# 由于不使用詞頻計算，所以出現的詞都是加1，最后再求平均
new_center[word] += 1
for wordin new_center:
new_center[word] = new_center[word]/files_count
# 中心點對象
center.vector = Vector('center')
center.vector.words = new_center
""" 損失函數 """
def costFunction(self):
print '開始計算損失函數'
total_cost = 0.0
count = 0
for centerin self.centers:
count += 1
print '計算第 ', count, ' 類的損失 objects : ', len(center.objects)
for vectorin center.objects:
# 求距離平方作為損失
total_cost += math.pow(vector.distance(center.vector),2)
print '本輪損失為：',total_cost
return total_cost
if __name__ == '__main__':
km = KMeans('allfiles')
km.start(5)
輸出結果：
2454 filesloaded
初始化隨機中心點個數: 5
劃分對象并計算損失...
計算第 1 點的新中心點...
計算第 2 點的新中心點...
計算第 3 點的新中心點...
計算第 4 點的新中心點...
計算第 5 點的新中心點...
第 1 次迭代:
劃分對象并計算損失...
計算第 1 點的新中心點...
計算第 2 點的新中心點...
計算第 3 點的新中心點...
計算第 4 點的新中心點...
計算第 5 點的新中心點...
損失(上一次 - 當前)： 4375.51247663 - 2034.9234715 = 2340.58900512
第 2 次迭代:
劃分對象并計算損失...
計算第 1 點的新中心點...
計算第 2 點的新中心點...
計算第 3 點的新中心點...
計算第 4 點的新中心點...
計算第 5 點的新中心點...
損失(上一次 - 當前)： 2034.9234715 - 2033.91112679 = 1.01234470898
第 1 組:
business = 314
it = 68
sports = 15
yule = 10
auto = 79
---------------------------------------
第 2 組:
business = 10
it = 16
sports = 26
yule = 132
auto = 10
---------------------------------------
第 3 組:
business = 4
it = 15
sports = 4
yule = 4
auto = 16
---------------------------------------
第 4 組:
business = 158
it = 226
sports = 388
yule = 281
auto = 338
---------------------------------------
第 5 組:
business = 14
it = 183
sports = 40
yule = 33
auto = 70
---------------------------------------
由于初始點是隨機選擇的，所以結果并不是很好，這點可以使用k-means++算法改進，以后再寫吧。
1、對于運算速度非常慢：
瓶頸在于兩個地方，主要就是計算歐氏距離的時候，需要所有對象分別與中心點求差平方，而中心點根據實際使用，發現維度高達2W或3W，2500個文章，相當于進行2500 * 3W次的（基本運算+乘法運算），目前網上有不少庫專門做這個事情，但總結起來還是沒法根本上解決此問題。
2、對于分類效果較差：
我選擇的場景更適合用樸素貝葉斯這種概率分類或者SVM這種間隔分類，因為K-Means的效果對初始的幾個點的依賴非常大，如果運氣不好選在了邊緣或者幾個分類的中間，那效果就會奇差。
解決辦法：
避免在新聞分類或其他高維數據下使用K-Means，除非能解決初始中心點的選擇問題，關于這點，我們后面的高斯混合模型可以部分解決這個問題。
而對于性能問題我目前無解，暫時想不到合適的數據結構來簡化計算，唯一能想到的就是用C函數替代歐氏距離和損失函數的計算部分。
如果您有好的解決辦法，請聯系我QQ：83534146 ，望不吝指導，多謝！
來自：http://python.jobbole.com/87343/