幾張GIF理解K-均值聚類原理
k均值聚類數(shù)學推導與python實現(xiàn)
前文說了k均值聚類，他是基于中心的聚類方法，通過迭代將樣本分到k個類中，使每個樣本與其所屬類的中心或均值最近。

今天我們看一下無監(jiān)督學習之聚類方法的另一種算法，層次聚類：

層次聚類前提假設類別直接存在層次關系，通過計算不同類別數(shù)據(jù)點間的相似度來創(chuàng)建一棵有層次的嵌套聚類樹。在聚類樹中，不同類別的原始數(shù)據(jù)點是樹的最低層，樹的頂層是一個聚類的根節(jié)點。創(chuàng)建聚類樹有聚合聚類（自下而上合并）和分裂聚類（自上而下分裂）兩種方法，分裂聚類一般很少使用，不做介紹。

聚合聚類

聚合聚類具體過程

對于給定的樣本集合，開始將每個樣本分到一個類，然后再按照一定的規(guī)則（比如類間距最?。?，將滿足規(guī)則的類進行合并，反復進行，直到滿足停止條件。聚合聚類三要素有：

①距離或相似度（閔可夫斯基距離，相關系數(shù)、夾角余弦）

②合并規(guī)則（最長/短距離，中心距離，平均距離）

③停止條件（類個數(shù)或類直徑達到或超過閾值）

聚合聚類算法

輸入：n個樣本組成的樣本集合及樣本間距離

輸出：樣本集合的層次化聚類

(1)計算n個樣本兩兩之間歐氏距離{dij}

(2)構造n個類，每個類只包含一個樣本

(3)合并類間距最小的兩個類，構造一個新類

(4)計算新類與其他各類的距離，若類的個數(shù)為1，終止計算，否則回到(3)

動畫表示：

python實現(xiàn)及案例

import queue
import math
import copy
import numpy as np
import matplotlib.pyplot as plt

class clusterNode:

def __init__(self, value, id=[],left=None, right=None, distance=-1,  count=-1, check = 0):
    '''
    value: 該節(jié)點的數(shù)值，合并節(jié)點時等于原來節(jié)點值的平均值
    id：節(jié)點的id，包含該節(jié)點下的所有單個元素
    left和right：合并得到該節(jié)點的兩個子節(jié)點
    distance：兩個子節(jié)點的距離
    count：該節(jié)點所包含的單個元素個數(shù)
    check：標識符，用于遍歷時記錄該節(jié)點是否被遍歷過
    '''
    self.value = value
    self.id = id
    self.left = left
    self.right = right
    self.distance = distance
    self.count = count
    self.check = check

def show(self):
    #顯示節(jié)點相關屬性
    print(self.value,' ',self.left.id if self.left!=None else None,' ',/
        self.right.id if self.right!=None else None,' ',self.distance,' ',self.count)

class hcluster:

def distance(self,x,y):
    #計算兩個節(jié)點的距離，可以換成別的距離
    return math.sqrt(pow((x.value-y.value),2))

def minDist(self,dataset):
    #計算所有節(jié)點中距離最小的節(jié)點對
    mindist = 1000
    for i in range(len(dataset)-1):
        if dataset[i].check == 1:
            #略過合并過的節(jié)點
            continue
        for j in range(i+1,len(dataset)):
            if dataset[j].check == 1:
                continue
            dist = self.distance(dataset[i],dataset[j])
            if dist < mindist:
                mindist = dist
                x, y = i, j
    return mindist, x, y
    #返回最小距離、距離最小的兩個節(jié)點的索引

def fit(self,data):
    dataset = [clusterNode(value=item,id=[(chr(ord('a')+i))],count=1) for i,item in enumerate(data)]
    #將輸入的數(shù)據(jù)元素轉化成節(jié)點，并存入節(jié)點的列表
    length = len(dataset)
    Backup = copy.deepcopy(dataset)
    #備份數(shù)據(jù)
    while(True):
        mindist, x, y = self.minDist(dataset)
        dataset[x].check = 1
        dataset[y].check = 1
        tmpid = copy.deepcopy(dataset[x].id)
        tmpid.extend(dataset[y].id)
        dataset.append(clusterNode(value=(dataset[x].value+dataset[y].value)/2,id=tmpid,/
            left=dataset[x],right=dataset[y],distance=mindist,count=dataset[x].count+dataset[y].count))
        #生成新節(jié)點
        if len(tmpid) == length:
            #當新生成的節(jié)點已經(jīng)包含所有元素時，退出循環(huán)，完成聚類
            break
    for item in dataset:
        item.show()
    return dataset

def show(self,dataset,num):
    plt.figure(1)
    showqueue = queue.Queue()
    #存放節(jié)點信息的隊列
    showqueue.put(dataset[len(dataset) - 1])
    #存入根節(jié)點
    showqueue.put(num)
    #存入根節(jié)點的中心橫坐標
    while not showqueue.empty():
        index = showqueue.get()
        #當前繪制的節(jié)點
        i = showqueue.get()
        #當前繪制節(jié)點中心的橫坐標
        left = i - (index.count)/2
        right = i + (index.count)/2
        if index.left != None:
            x = [left,right]
            y = [index.distance,index.distance]
            plt.plot(x,y)
            x = [left,left]
            y = [index.distance,index.left.distance]
            plt.plot(x,y)
            showqueue.put(index.left)
            showqueue.put(left)
        if index.right != None:
            x = [right,right]
            y = [index.distance,index.right.distance]
            plt.plot(x,y)
            showqueue.put(index.right)
            showqueue.put(right)
    plt.show()

def setData(num):

#生成num個隨機數(shù)據(jù)
Data = list(np.random.randint(1,100,size=num))
return Data

if name == '__main__':

num = 20
dataset = setData(num)
h = hcluster()
resultset = h.fit(dataset)
h.show(resultset,num)

本文由博客一文多發(fā)平臺 OpenWrite 發(fā)布！

審核編輯 黃昊宇