技术人生,  机器学习

层次聚类算法之聚合聚类

层次聚类是一种无监督学习中的聚类方法,它将样本聚合到层次化的类中。层次聚类又可以分为聚合聚类(自下而上)和分裂聚类(自上而下)两种,本文主要讨论聚合聚类。

聚合聚类开始时将每个样本分到一个类,之后将相距最近的两类合并,重复此操作直到满足停止条件。

本文采用欧式距离来计算各个样本之间的距离,类间距离可以采用最短距离、最长距离和中心距离三种。

直接看代码。

导入所需库。

import numpy as np
from sklearn.datasets import load_iris
import matplotlib.pyplot as plt

导入数据集,数据集使用鸢尾花数据集的前一百条数据的中间两维特征。其中前50条数据属于一类,后50条属于一类,共两类。选用中间两维特征是由于这两个特征可以很清楚的区分两类数据。所以,我们的目标是把数据集分成两类。

dataSet = load_iris().data[:100,1:3]
#dataSet = np.delete(dataSet,41,axis=0)
size = dataSet.shape
categories_number = 2

为了避免数据的某个维度的值过大而主宰了样本间距离的计算结果,将数据进行归一化处理。

#归一化
mx = np.max(dataSet,axis=0)
mn = np.min(dataSet,axis=0)
dataSet = (dataSet - mn) / (mx - mn)

采用欧式距离计算两两样本之间的距离,提前保存所有的计算值。

#计算所有样本点间的欧氏距离(采用最小/最大/平均距离时使用)
distance = np.zeros((size[0],size[0]))
for i in range(size[0]):
    for j in range(size[0]):
        distance[i,j] = np.linalg.norm(dataSet[i] - dataSet[j])

根据聚合聚类自下而上的思想,使每个样本各自成为一类。

#将每个样本点(序号)加入到一个类中
categories = []
for i in range(size[0]):
    categories.append({i})

下面开始循环聚合的过程,首先判断终止条件:若剩余类别数等于所需分类的数,则停止。

while True:
    #若剩余类的数量满足条件,则退出循环
    if len(categories) == categories_number:
        break

计算类间距离,其中可以使用三种方法计算,分别是最短距离,最长距离和中心距离。

  • 最短距离:两类中最近的两个样本之间的距离。
  • 最长距离:两类中最远的两个样本之间的距离。
  • 中心距离:两个类别的中心之间的距离。(所有样本点各个维度的均值即为类中心)
    #计算类间距离
    d_c = {}                                        #类间距离
    for c1 in range(len(categories) - 1):
        d_c[c1] = {}
        for c2 in range(c1 + 1, len(categories)):
            d_s = []                                #样本间距离
            def min_max_distance(flag):
                #最小(flag=False)或最大(flag=True)距离
                for s1 in categories[c1]:
                    for s2 in categories[c2]:
                        d_s.append(distance[s1,s2])
                d_s.sort(reverse=flag)
                d_c[c1][c2] = d_s[0]
            def centeral_distance():
                #中心距离
                center_c1 = np.zeros(size[1])
                for s1 in categories[c1]:
                    center_c1 += dataSet[s1]
                center_c1 /= len(categories[c1])
                center_c2 = np.zeros(size[1])
                for s2 in categories[c2]:
                    center_c2 += dataSet[s2]
                center_c2 /= len(categories[c2])
                d_c[c1][c2] = np.linalg.norm(center_c1 - center_c2)
            #min_max_distance(False)
            centeral_distance()

合并类间距离最小的两类。

    #排序找到最小的类间距离
    d_c_list = []
    for i in d_c.items():
        for j in i[1].items():
            d_c_list.append((i[0],)+j)
    d_c_list.sort(key=lambda a: a[-1])

    #合并类间距离最小的两个类
    nearest = [d_c_list[0][0],d_c_list[0][1]]
    categories[nearest[0]] = categories[nearest[0]].union(categories[nearest[1]])
    categories.pop(nearest[1])

循环结束后即可输出聚类的结果。

#输出结果
for i in range(len(categories)):
    print('第'+str(i+1)+'类:',categories[i])

为了更清晰的展示结果,绘制散点图。

#绘制散点图
for i in categories[0]:
    plt.plot(dataSet[i][0],dataSet[i][1],'rx')
for i in categories[1]:
    plt.plot(dataSet[i][0],dataSet[i][1],'bo')
plt.show()

分类结果如下:

可见数据集被清楚的聚成了两类,聚类结果也是正确的。

当使用鸢尾花数据集的全部4个维度150条数据进行计算,此时结果因被分为3类。

由于4维数据难以清楚的图像化表示,因此只能取前两维绘图。

由于其中一个点可能是干扰数据或者噪音数据,其欧式距离较其他各个点更远,因此出现了某种极端的局部最优的结果,该点单独成为了一类,显然这与我们的期望是差别很大的。

聚合聚类对所有样本点间的距离都进行了细致的计算,并且聚类过程中不会进行整体的优化和二次计算,类别被不断地聚合扩充,导致很容易出现个别的噪声数据影响全局的情况发生。因此,对于距离区分不明显或含有噪音数据的数据集,聚合聚类很难很好的发挥作用,这是一大缺陷。

A WindRunner. VoyagingOne

留言

您的电子邮箱地址不会被公开。 必填项已用*标注