100天搞定机器学习|day54 聚类系列：层次聚类原理及案例

前文说了k均值聚类，他是基于中心的聚类方法，通过迭代将样本分到k个类中，使每个样本与其所属类的中心或均值最近。

今天我们看一下无监督学习之聚类方法的另一种算法，层次聚类：

层次聚类前提假设类别直接存在层次关系，通过计算不同类别数据点间的相似度来创建一棵有层次的嵌套聚类树。在聚类树中，不同类别的原始数据点是树的最低层，树的顶层是一个聚类的根节点。创建聚类树有聚合聚类（自下而上合并）和分裂聚类（自上而下分裂）两种方法，分裂聚类一般很少使用，不做介绍。

聚合聚类

聚合聚类具体过程

对于给定的样本集合，开始将每个样本分到一个类，然后再按照一定的规则（比如类间距最小），将满足规则的类进行合并，反复进行，直到满足停止条件。聚合聚类三要素有：

①距离或相似度（闵可夫斯基距离，相关系数、夹角余弦）

②合并规则（最长/短距离，中心距离，平均距离）

③停止条件（类个数或类直径达到或超过阈值）

聚合聚类算法

输入：n个样本组成的样本集合及样本间距离

输出：样本集合的层次化聚类

(1)计算n个样本两两之间欧氏距离{dij}

(2)构造n个类，每个类只包含一个样本

(3)合并类间距最小的两个类，构造一个新类

(4)计算新类与其他各类的距离，若类的个数为1，终止计算，否则回到(3)

动画表示：

python实现及案例

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: 该节点的数值，合并节点时等于原来节点值的平均值

id：节点的id，包含该节点下的所有单个元素

left和right：合并得到该节点的两个子节点

distance：两个子节点的距离

count：该节点所包含的单个元素个数

check：标识符，用于遍历时记录该节点是否被遍历过

”’

self.value = value

self.id = id

self.left = left

self.right = right

self.distance = distance

self.count = count

self.check = check

def show(self):
    #显示节点相关属性
    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):
    #计算两个节点的距离，可以换成别的距离
    return math.sqrt(pow((x.value-y.value),2))def minDist(self,dataset):
    #计算所有节点中距离最小的节点对
    mindist = 1000
    for i in range(len(dataset)-1):
        if dataset[i].check == 1:
            #略过合并过的节点
            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
    #返回最小距离、距离最小的两个节点的索引def fit(self,data):
    dataset = [clusterNode(value=item,id=[(chr(ord('a')+i))],count=1) for i,item in enumerate(data)]
    #将输入的数据元素转化成节点，并存入节点的列表
    length = len(dataset)
    Backup = copy.deepcopy(dataset)
    #备份数据
    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))
        #生成新节点
        if len(tmpid) == length:
            #当新生成的节点已经包含所有元素时，退出循环，完成聚类
            break
    for item in dataset:
        item.show()
    return datasetdef show(self,dataset,num):
    plt.figure(1)
    showqueue = queue.Queue()
    #存放节点信息的队列
    showqueue.put(dataset[len(dataset) - 1])
    #存入根节点
    showqueue.put(num)
    #存入根节点的中心横坐标
    while not showqueue.empty():
        index = showqueue.get()
        #当前绘制的节点
        i = showqueue.get()
        #当前绘制节点中心的横坐标
        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()