100天搞定機(jī)器學(xué)習(xí)：day54 聚類系列：層次聚類原理及案例

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

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

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

聚合聚類

聚合聚類具體過(guò)程

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

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

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

③停止條件（類個(gè)數(shù)或類直徑達(dá)到或超過(guò)閾值）

聚合聚類算法

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

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

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

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

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

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

動(dòng)畫表示：

python實(shí)現(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é)點(diǎn)的數(shù)值，合并節(jié)點(diǎn)時(shí)等于原來(lái)節(jié)點(diǎn)值的平均值
    id：節(jié)點(diǎn)的id，包含該節(jié)點(diǎn)下的所有單個(gè)元素
    left和right：合并得到該節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)
    distance：兩個(gè)子節(jié)點(diǎn)的距離
    count：該節(jié)點(diǎn)所包含的單個(gè)元素個(gè)數(shù)
    check：標(biāo)識(shí)符，用于遍歷時(shí)記錄該節(jié)點(diǎn)是否被遍歷過(guò)
    '''
    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é)點(diǎn)相關(guān)屬性
    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):
    #計(jì)算兩個(gè)節(jié)點(diǎn)的距離，可以換成別的距離
    return math.sqrt(pow((x.value-y.value),2))

def minDist(self,dataset):
    #計(jì)算所有節(jié)點(diǎn)中距離最小的節(jié)點(diǎn)對(duì)
    mindist = 1000
    for i in range(len(dataset)-1):
        if dataset[i].check == 1:
            #略過(guò)合并過(guò)的節(jié)點(diǎn)
            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
    #返回最小距離、距離最小的兩個(gè)節(jié)點(diǎn)的索引

def fit(self,data):
    dataset = [clusterNode(value=item,id=[(chr(ord('a')+i))],count=1) for i,item in enumerate(data)]
    #將輸入的數(shù)據(jù)元素轉(zhuǎn)化成節(jié)點(diǎn)，并存入節(jié)點(diǎn)的列表
    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é)點(diǎn)
        if len(tmpid) == length:
            #當(dāng)新生成的節(jié)點(diǎn)已經(jīng)包含所有元素時(shí)，退出循環(huán)，完成聚類
            break
    for item in dataset:
        item.show()
    return dataset

def show(self,dataset,num):
    plt.figure(1)
    showqueue = queue.Queue()
    #存放節(jié)點(diǎn)信息的隊(duì)列
    showqueue.put(dataset[len(dataset) - 1])
    #存入根節(jié)點(diǎn)
    showqueue.put(num)
    #存入根節(jié)點(diǎn)的中心橫坐標(biāo)
    while not showqueue.empty():
        index = showqueue.get()
        #當(dāng)前繪制的節(jié)點(diǎn)
        i = showqueue.get()
        #當(dāng)前繪制節(jié)點(diǎn)中心的橫坐標(biāo)
        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個(gè)隨機(jī)數(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ā)平臺(tái) OpenWrite 發(fā)布！

審核編輯 黃昊宇