您好,登錄后才能下訂單哦!
本文主要內(nèi)容:
先上一張gif的k均值聚類算法動態(tài)圖片,讓大家對算法有個感性認識:
其中:N=200代表有200個樣本,不同的顏色代表不同的簇(其中 3種顏色為3個簇),星星代表每個簇的簇心。算法通過25次迭代找到收斂的簇心,以及對應的簇。 每次迭代的過程中,簇心和對應的簇都在變化。
聚類算法的特點
聚類算法是無監(jiān)督學習算法和前面的有監(jiān)督算法不同,訓練數(shù)據(jù)集可以不指定類別(也可以指定)。聚類算法對象歸到同一簇中,類似全自動分類。簇內(nèi)的對象越相似,聚類的效果越好。K-均值聚類是每個類別簇都是采用簇中所含值的均值計算而成。
聚類樣本間的屬性(包括,有序?qū)傩?、無序?qū)傩?度量標準 1. 有序?qū)傩?/p>
例如:西瓜的甜度:0.1, 0.5, 0.9(值越大,代表越甜)
我們可以使用明可夫斯基距離定義:
2. 無序?qū)傩?/p>
例如:色澤,青綠、淺綠、深綠(又例如: 性別: 男, 女, 中性,人yao…明顯也不能使用0.1, 0.2 等表示求距離)。這些不能使用連續(xù)的值表示,求距離的,一般使用VDM計算:
聚類的常見算法,原型聚類(主要論述K均值聚類),層次聚類、密度聚類
聚類算法分為如下三大類:
1. 原型聚類(包含3個子類算法):
K均值聚類算法
學習向量量化
高斯混合聚類
2. 密度聚類:
3. 層次聚類:
下面主要說明K均值聚類算法(示例來源于,周志華西瓜書)
算法基本思想:
K-Means 是發(fā)現(xiàn)給定數(shù)據(jù)集的 K 個簇的聚類算法, 之所以稱之為 K-均值 是因為它可以發(fā)現(xiàn) K 個不同的簇,且每個簇的中心采用簇中所含值的均值計算而成.簇個數(shù) K 是用戶指定的, 每一個簇通過其質(zhì)心(centroid), 即簇中所有點的中心來描述.
算法流程如下:
主要是三個步驟:
下面給出西瓜書的示例:
西瓜包含下面兩個屬性,密度以及含糖率,這兩個屬性構成的二維向量,作為輸入向量(具體數(shù)據(jù)如下表)
算法大致過程如下:
下圖是分類的,每一輪簇心的更新結果,圖中橫坐標為密度屬性,縱坐標為含糖率屬性:
4. K均值聚類算法的python實現(xiàn)
下面給出K-means cluster算法的實現(xiàn)的大致框架:
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): # 迭代最大次數(shù) for i in xrange(self._max_iter): print 'iteration %s' % i # 求每個簇心的簇類 d_cluster = self._cluster_point(x) # 對現(xiàn)有的簇類,更新簇心 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
下面給出程序的運行結果, 由圖可見經(jīng)過三次迭代程序收斂,并且找到最佳節(jié)點:
下面再給出,另一次運行結果,可見由于初始化點選擇不一樣,得到的結果也是不一樣的,初始點的選擇對聚類算法的影響還是很大。
K-means實際上是EM算法的一個特例,根據(jù)中心點(簇心)決定數(shù)據(jù)點歸屬是expectation,而根據(jù)構造出來的cluster更新中心(簇心)則是maximization。理解了K-means,也就順帶了解了基本的EM算法思路。
5. 參考引用
參考引用地址
以上就是本文的全部內(nèi)容,希望對大家的學習有所幫助,也希望大家多多支持億速云。
免責聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權內(nèi)容。