本文主要內(nèi)容：

• 聚類(lèi)算法的特點(diǎn)
• 聚類(lèi)算法樣本間的屬性(包括，有序?qū)傩浴o(wú)序?qū)傩?度量標(biāo)準(zhǔn)
• 聚類(lèi)的常見(jiàn)算法，原型聚類(lèi)(主要論述K均值聚類(lèi))，層次聚類(lèi)、密度聚類(lèi)
• K均值聚類(lèi)算法的python實(shí)現(xiàn)，以及聚類(lèi)算法與EM最大算法的關(guān)系
• 參考引用

先上一張gif的k均值聚類(lèi)算法動(dòng)態(tài)圖片，讓大家對(duì)算法有個(gè)感性認(rèn)識(shí)：

其中：N=200代表有200個(gè)樣本，不同的顏色代表不同的簇(其中 3種顏色為3個(gè)簇)，星星代表每個(gè)簇的簇心。算法通過(guò)25次迭代找到收斂的簇心，以及對(duì)應(yīng)的簇。 每次迭代的過(guò)程中，簇心和對(duì)應(yīng)的簇都在變化。

聚類(lèi)算法的特點(diǎn)

聚類(lèi)算法是無(wú)監(jiān)督學(xué)習(xí)算法和前面的有監(jiān)督算法不同，訓(xùn)練數(shù)據(jù)集可以不指定類(lèi)別(也可以指定)。聚類(lèi)算法對(duì)象歸到同一簇中，類(lèi)似全自動(dòng)分類(lèi)。簇內(nèi)的對(duì)象越相似，聚類(lèi)的效果越好。K-均值聚類(lèi)是每個(gè)類(lèi)別簇都是采用簇中所含值的均值計(jì)算而成。

聚類(lèi)樣本間的屬性(包括，有序?qū)傩?、無(wú)序?qū)傩?度量標(biāo)準(zhǔn) 1. 有序?qū)傩?/p>

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

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

2. 無(wú)序?qū)傩?/p>

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

聚類(lèi)的常見(jiàn)算法，原型聚類(lèi)(主要論述K均值聚類(lèi))，層次聚類(lèi)、密度聚類(lèi)

聚類(lèi)算法分為如下三大類(lèi)：

1. 原型聚類(lèi)(包含3個(gè)子類(lèi)算法)：

K均值聚類(lèi)算法

學(xué)習(xí)向量量化

高斯混合聚類(lèi)

2. 密度聚類(lèi)：

3. 層次聚類(lèi)：

下面主要說(shuō)明K均值聚類(lèi)算法(示例來(lái)源于，周志華西瓜書(shū))

算法基本思想：

K-Means 是發(fā)現(xiàn)給定數(shù)據(jù)集的 K 個(gè)簇的聚類(lèi)算法, 之所以稱(chēng)之為 K-均值 是因?yàn)樗梢园l(fā)現(xiàn) K 個(gè)不同的簇,且每個(gè)簇的中心采用簇中所含值的均值計(jì)算而成.簇個(gè)數(shù) K 是用戶(hù)指定的, 每一個(gè)簇通過(guò)其質(zhì)心（centroid）, 即簇中所有點(diǎn)的中心來(lái)描述.

算法流程如下：

主要是三個(gè)步驟：

• 初始化選擇K個(gè)簇心，假設(shè)樣本有 m個(gè)屬性，則相當(dāng)于k個(gè)m為向量
• 對(duì)于k個(gè)簇，求離其最近的樣本，并劃分新的簇
• 對(duì)于每個(gè)新的簇，更新簇心的向量(一般可以求簇的樣本的屬性的均值)
• 重復(fù)2~3直到算法收斂，或者運(yùn)行了指定的次數(shù)

下面給出西瓜書(shū)的示例：

西瓜包含下面兩個(gè)屬性，密度以及含糖率，這兩個(gè)屬性構(gòu)成的二維向量，作為輸入向量(具體數(shù)據(jù)如下表)

算法大致過(guò)程如下：

下圖是分類(lèi)的，每一輪簇心的更新結(jié)果，圖中橫坐標(biāo)為密度屬性，縱坐標(biāo)為含糖率屬性：

4. K均值聚類(lèi)算法的python實(shí)現(xiàn)

下面給出K-means cluster算法的實(shí)現(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
      # 求每個(gè)簇心的簇類(lèi)
      d_cluster = self._cluster_point(x)
      # 對(duì)現(xiàn)有的簇類(lèi)，更新簇心
      new_center_node = self._reevaluate_center_node(d_cluster)

      # 檢測(cè)簇心是否變化，判斷算法收斂
      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):
    # 求每個(gè)簇心的簇
    pass
    return d_cluster

  def _reevaluate_center_node(self, d_cluster):
    # 對(duì)新的簇，求最佳簇心
    return arr_center_node

  def _check_converge(self, vec):
    # 判斷簇心是否改變，算法收斂
    return np.array_equal(self._cluster_vec, vec)

具體的算法，以及見(jiàn)本人的github

下面給出程序的運(yùn)行結(jié)果, 由圖可見(jiàn)經(jīng)過(guò)三次迭代程序收斂，并且找到最佳節(jié)點(diǎn):

下面再給出，另一次運(yùn)行結(jié)果，可見(jiàn)由于初始化點(diǎn)選擇不一樣，得到的結(jié)果也是不一樣的，初始點(diǎn)的選擇對(duì)聚類(lèi)算法的影響還是很大。

K-means實(shí)際上是EM算法的一個(gè)特例，根據(jù)中心點(diǎn)(簇心)決定數(shù)據(jù)點(diǎn)歸屬是expectation，而根據(jù)構(gòu)造出來(lái)的cluster更新中心(簇心)則是maximization。理解了K-means，也就順帶了解了基本的EM算法思路。

5. 參考引用

參考引用地址

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

最新評(píng)論