python實現聚類演算法理

python實現聚類演算法理
1 Star2 Stars3 Stars4 Stars5 Stars 給文章打分!
Loading...

本文主要內容:

聚類演算法的特點
聚類演算法樣本間的屬性(包括,有序屬性、無序屬性)度量標準
聚類的常見演算法,原型聚類(主要論述K均值聚類),層次聚類、密度聚類
K均值聚類演算法的python實現,以及聚類演算法與EM最大演算法的關係
參考引用

先上一張gif的k均值聚類演算法動態圖片,讓大家對演算法有個感性認識:

其中:N=200代表有200個樣本,不同的顏色代表不同的簇(其中 3種顏色為3個簇),星星代表每個簇的簇心。演算法通過25次迭代找到收斂的簇心,以及對應的簇。 每次迭代的過程中,簇心和對應的簇都在變化。

聚類演算法的特點

聚類演算法是無監督學習演算法和前面的有監督演算法不同,訓練資料集可以不指定類別(也可以指定)。聚類演算法物件歸到同一簇中,類似全自動分類。簇內的物件越相似,聚類的效果越好。K-均值聚類是每個類別簇都是採用簇中所含值的均值計算而成。

聚類樣本間的屬性(包括,有序屬性、無序屬性)度量標準 1. 有序屬性

例如:西瓜的甜度:0.1, 0.5, 0.9(值越大,代表越甜)

我們可以使用明可夫斯基距離定義:

2. 無序屬性

例如:色澤,青綠、淺綠、深綠(又例如: 性別: 男, 女, 中性,人yao…明顯也不能使用0.1, 0.2 等表示求距離)。這些不能使用連續的值表示,求距離的,一般使用VDM計算:

聚類的常見演算法,原型聚類(主要論述K均值聚類),層次聚類、密度聚類

聚類演算法分為如下三大類:

1. 原型聚類(包含3個子類演算法):

K均值聚類演算法

學習向量量化

高斯混合聚類

2. 密度聚類:

3. 層次聚類:

下面主要說明K均值聚類演算法(示例來源於,周志華西瓜書)

演算法基本思想:

K-Means 是發現給定資料集的 K 個簇的聚類演算法, 之所以稱之為 K-均值 是因為它可以發現 K 個不同的簇,且每個簇的中心採用簇中所含值的均值計算而成.簇個數 K 是使用者指定的, 每一個簇通過其質心(centroid), 即簇中所有點的中心來描述.

演算法流程如下:

主要是三個步驟:

初始化選擇K個簇心,假設樣本有 m個屬性,則相當於k個m為向量
對於k個簇,求離其最近的樣本,並劃分新的簇
對於每個新的簇,更新簇心的向量(一般可以求簇的樣本的屬性的均值)
重複2~3直到演算法收斂,或者執行了指定的次數

下面給出西瓜書的示例:

西瓜包含下面兩個屬性,密度以及含糖率,這兩個屬性構成的二維向量,作為輸入向量(具體資料如下表)

演算法大致過程如下:

下圖是分類的,每一輪簇心的更新結果,圖中橫座標為密度屬性,縱座標為含糖率屬性:

4. K均值聚類演算法的python實現

下面給出K-means cluster演算法的實現的大致框架:


class KMeans(object):
def __init__(self, k, init_vec, max_iter=100):
"""
:param k:
:param init_vec: init mean vectors type: k * n array(n properties)
"""
self._k = k
self._cluster_vec = init_vec
self._max_iter = max_iter
def fit(self, x):
# 迭代最大次數
for i in xrange(self._max_iter):
print 'iteration %s' % i
# 求每個簇心的簇類
d_cluster = self._cluster_point(x)
# 對現有的簇類,更新簇心
new_center_node = self._reevaluate_center_node(d_cluster)
# 檢測簇心是否變化,判斷演算法收斂
if self._check_converge(new_center_node):
print 'found converge node'
break
else:
self._cluster_vec = new_center_node
def _cal_distance(self, vec1, vec2):
return np.linalg.norm(vec1 - vec2)
def _cluster_point(self, x):
# 求每個簇心的簇
pass
return d_cluster
def _reevaluate_center_node(self, d_cluster):
# 對新的簇,求最佳簇心
return arr_center_node
def _check_converge(self, vec):
# 判斷簇心是否改變,演算法收斂
return np.array_equal(self._cluster_vec, vec)

具體的演算法,以及見本人的github

下面給出程式的執行結果, 由圖可見經過三次迭代程式收斂,並且找到最佳節點:

下面再給出,另一次執行結果,可見由於初始化點選擇不一樣,得到的結果也是不一樣的,初始點的選擇對聚類演算法的影響還是很大。

K-means實際上是EM演算法的一個特例,根據中心點(簇心)決定資料點歸屬是expectation,而根據構造出來的cluster更新中心(簇心)則是maximization。理解了K-means,也就順帶了解了基本的EM演算法思路。

5. 參考引用

參考引用地址

相關文章

程式語言 最新文章