0 写在前面（数据集和源代码）
本文章涉及到的数据集合所有代码均上传在此处：https://download.csdn.net/download/zhouzhuo_csuft/10494273；点击此处直接打开链接；一共有四个代码文件，分别是Kmeans、Kmeans++、Birch和KNN算法，四个算法对同一个数据集聚类分析进行对比试验。（本代码是本人自己书写，全部可用！）


1 引言
近年来，机器学习已成为计算机前沿中火热的研究点之一。我国政府也将机器学习纳入了国家级战略。目前，机器学习已广泛用于各种数据挖掘、模式识别、语音识别及图像处理等各领域。本文以机器学习中四个经典的聚类算法进行对比介绍和对比实验，得出四个算法对相同实验数据集的聚类效果。
2聚类算法
聚类在学术界并没有一个确切的定义，此处给出1974年Everitt对聚类的定义：一个类簇内的实体是相似的,不同类簇的实体是不相似的;一个类簇是测试空间中点的会聚,同一类簇的任意两个点间的距离小于不同类簇的任意两个点间的距离[1];类簇可以描述为一个包含密度相对较高的点集的多维空间中的连通区域,它们借助包含密度相对较低的点集的区域与其他区域(类簇)相分离。
简单地说，聚类是根据其自身特征将数据集进行划分成若干类的过程，划分的结果是相同类哈哈内数据相似度尽可能大、不同类间数据相似度尽可能小，从而发现数据集的内在结构。
聚类在不同应用领域有不同的特殊要求，聚类算法的典型性能要求有以下几个方面：
（1）伸缩性
（2）兼容性
（3）有效处理噪声数据
（4）能处理基于约束的聚类
（5）可解释性和可用性
典型的聚类过程主要包括数据（样本）准备、特征选择和特征提取、相似度计算、聚类、对聚类结果进行有效性评估[1]。
聚类过程：
（1）数据准备：包括特征标准化和降维。
（2）特征选择，从最初的特征中选取最有效的特征，并将其存储于向量中。
（3）特征提取：通过对所选择的特征进行转换形成新的突出特征。
（4）聚类：首先选择合适特征类型的某种离函数 ( 或构造新的距离函数 ) 进行接近程度的度量，而后执行聚类或分组。 .
（5）聚类结果评估 : 是指对聚类结果进行评估 . 评估主要有 3 种 : 外部有效性评估、内部有效性评估和相关性测试评估。

3 典型聚类及其变种算法介绍
3.1 K-Means聚类
3.2.1 K-Means聚类介绍
1967 年 ,MacQueen 首次提出了 K 均值聚类算法 (K-Means 算法 )。 迄今为止 , 很多聚类任务都选择该经典算法[2]。该算法的核心思想是找出 k个聚类中心c1 ,c2 ,…,ck使得每一个数据点 xi 和与其最近的聚类中心 cv 的平方距离和被最小化 ( 该平方距离和被称为偏差 D)。
3.1.2 K-means聚类算法步骤
（1）初始化，随机指定 K 个聚类中心 (c1 ,c2 ,…,ck );
（2）分配 xi, 对每一个样本 xi，找到离它最近的聚类中心 cv，并将其分配到 cv 所标明类;
（3）修正 c w，将每一个 cw 移动到其标明的类的中心；
（4）计算偏差 ；
（5）判断D是否收敛，如果D收敛，则return(c1,c2,……,ck)，并终止本算法；否则返回步骤2。
3.1.3 K-means 算法的优点与不足
优点: 能对大型数据集进行高效分类, 其计算复杂性为 O(tkmn), 其中 ,t 为迭代次数，k为聚类数，m 为特征属性数，n 为待分类的对象数，通常k,m,t<<n[3]. 在对大型数据集聚类时，K-means 算法比层次聚类算法快得多。 
不足: 通常会在获得一个局部最优值时终止；仅适合对数值型数据聚类；只适用于聚类。
3.2 K-Means++算法
3.2.1 K-Means++简介
由于 K-means 算法的分类结果会受到初始点的选取而有所区别，因此后来有人针对这个问题对K-Means算法进行改进，于是产生了 K-means++算法 。K-Means++算法只是对初始点的选择有改进而已，其他步骤都一样。初始质心选取的基本思路就是，初始的聚类中心之间的相互距离要尽可能的远。
3.2.2  K-Means++算法步骤[4]
（1）从数据集中随机选取一个样本作为初始聚类中心c1;
（2）首先计算每个样本与当前已有聚类中心之间的最短距离（即最近的一个聚类中心的距离），用D(x)表示；接着计算每个样本被选为下一个聚类中心的概率  。按照轮盘法选出下一个聚类中心;
（3）重复第2步，直到选择出共K个聚类中心；
（4）后面与K-Means聚类算法的2-4步相同。
3.3 BIRCH聚类算法
3.3.1 BIRCH聚类简介
　BIRCH的全称是利用层次方法的平衡迭代规约和聚类（Balanced Iterative Reducing and Clustering UsingHierarchies），它利用了一个类似于B+树的聚类特征树(ClusteringFeature Tree，简称CF Tree)快速的聚类。如图1所示，这颗树的每一个节点是由若干个聚类特征(Clustering Feature，简称CF)组成。每个节点包括叶子节点都有若干个CF，而内部节点的CF有指向孩子节点的指针，所有的叶子节点用一个双向链表链接起来。
不同于K-Means算法，BIRCH算法可以不用输入类别数K值。如果不输入K值，则最后的CF元组的组数即为最终的K，否则会按照输入的K值对CF元组按距离大小进行合并。一般来说，BIRCH算法适用于样本量较大的情况，除了聚类还可以额外做一些异常点检测和数据初步按类别规约的预处理。
 


图 1 CF Tree模型
3.3.2 BIRCH聚类算法步骤[5]

（1）扫描所有数据，建立初始化的CF树，把稠密数据分成簇，稀疏数据作为孤立点对待；
（2）这个阶段是可选的，阶段（3）的全局或半全局聚类算法有着输入范围的要求，以达到速度与质量的要求，所以此阶段在阶段步骤（1）的基础上，建立一个更小的CF树；
（3）补救由于输入顺序和页面大小带来的分裂，使用全局/半全局算法对全部叶节点进行聚类
（4）这个阶段也是可选的，把阶段（3）的中心点作为种子，将数据点重新分配到最近的种子上，保证重复数据分到同一个簇中，同时添加簇标签。
3.3.4 BIRCH聚类的优缺点
主要优点有：
（1）节约内存，所有的样本都在磁盘上，CF Tree仅仅存了CF节点和对应的指针。
（2）聚类速度快，只需要一遍扫描训练集就可以建立CF Tree，CF Tree的增删改都很快。
（3）可以识别噪音点，还可以对数据集进行初步分类的预处理
主要缺点有：
（1）由于CF Tree对每个节点的CF个数有限制，导致聚类的结果可能和真实的类别分布不同.
（2）对高维特征的数据聚类效果不好。此时可以选择Mini Batch K-Means
（3）如果数据集的分布簇不是类似于超球体，或者说不是凸的，则聚类效果不好。
3.4 KNN聚类算法
3.4.1 KNN聚类简介
KNN（K-Nearest Neighbor），代表 k 个最近邻分类法，通过k个与之最相近的历史记录的组合来辨别新的记录。KNN 是一个众所周知的统计方法，在过去的 40 年里在模式识别中集中地被研究。KNN 在早期的研究策略中已被应用于文本分类[6]，是基准 Reuters 主体的高操作性的方法之一。其它方法，如 LLSF、决策树和神经网络等。
3.4.2 KNN聚类算法步骤[7]
（1）准备数据，对数据进行预处理；
（2） 选用合适的数据结构存储训练数据和测试元组；
（3）设定参数，如元组数目k；
（4）维护一个大小为k的按距离由大到小的优先级队列，用于存储最近邻训练元组。随机从训练元组中选取k个元组作为初始的最近邻元组，分别计算测试元组到这k个元组的距离，将训练元组标号和距离存入优先级队列；
（5）遍历训练元组集，计算当前训练元组与测试元组的距离，将所得距离L 与优先级队列中的最大距离Lmax；
（6）进行比较。若L>=Lmax，则舍弃该元组，遍历下一个元组。若L < Lmax，删除优先级队列中最大距离的元组，将当前训练元组存入优先级队列；
（7）遍历完毕，计算优先级队列中k 个元组的多数类，并将其作为测试元组的类别；
（8） 测试元组集测试完毕后计算误差率，继续设定不同的k值重新进行训练，最后取误差率最小的k 值。
3.4.3KNN聚类的优缺点
主要优点有
（1）简单，易于理解，无需建模与训练，易于实现；
（2）适合对稀有事件进行分类；
（3）适合与多分类问题，例如根据基因特征来判断其功能分类，KNN比SVM的表现要好。
主要缺点有：
（1）惰性算法，内存开销大，对测试样本分类时计算量大，性能较低；
（2）可解释性差，无法给出决策树那样的规则。
4 实验
4.1 实验环境
本实验拟将对第二节中的4个算法进行测试，实验系统采用Ubuntu16.04TLS版本（也可以用windows下pycharm等IDE），内存8G，CPU为4核心AMD芯片（两个），主频2.4GHZ。实验代码使用Python2.7.2版本。
4.2实验测试
      为测试4个算法的聚类效果，实验将使用4个算法对同一个数据集进行聚类测试。该数据集是一个存放80个二维坐标点的文本文件，文件每行有两个数据，以制表符分割，分别表示二维坐标的X轴数据和Y轴数据。
      经测试，4个算法对数据集聚类的结果图示如图2、图3、图4、图5所示：
                                      
                                                                      图 2 K-Means聚类结果
                                 
图 3 K-Means++聚类结果
                                            
图 4 BIRCH聚类结果

图 5 KNN聚类结果
4.3 对比结论
上述四组图为实验对比，可以看出，四种算法对数据集的分类效果相当，只有在个别点的划分有所不同，即数据集中的(-0.392370  -3.963704)坐标点，在K-Means聚类和KNN聚类中，该点被聚类到左下方簇中，而在K-Means++聚类和BIRCH聚类中，该点被划分到了右下方簇中。
5总结
      本文首先介绍了聚类算法定义和聚类算法的基本步骤，然后分别对K-Means、K-Means++、BIRCH和KNN四个经典的聚类算法作了详细介绍，最后通过对同一个数据集进行对比实验，得出四个聚类效果。从实验中反映了四个聚类算法对数据集的聚类效果较好。四种聚类算法在本实验中达到了的聚类效果几乎一样，但四类聚类算法在实际生活中仍将有其不同的使用背景，故在实际生活中需要结合特定的实际环境采用不同聚类算法，以达到最好的效果[8]。
6参考文献
[1] 孙吉贵，刘杰，赵连宇.聚类算法研究[J].软件学报,2008
[2] 张建萍,刘希玉.基于聚类分析的 K-means算法研究及应用[J].计算机应用研究,2007,5
[3] 杨善林,李永森,胡笑旋,潘若愚.K-means 算法中的 k 值优化问题研究[J].系统工程理论与实践，2006,2
[4] David Arthur and Sergei Vassilvitskii.k-means++:[J].TheAdvantages of Careful Seeding，2007
[5] BIRCH:An Efficient Data 3Clustering Method forVery Large Databases[J].1996
[6]张宁,贾自艳,史忠植.使用 KNN算法的文本分类[J].计算机工程，2005.4
[7]KNN算法综述,https://wenku.baidu.com/view/d84cf670a5e9856a561260ce.html,2018.5.10
 [8]贺玲,吴玲达,蔡益朝.数据挖掘中的聚类算法综述[J].计算机应用研究,2007

几种聚类算法的对比实验
 
聚类方法是属于无标签的无监督学习方法。其他常见的无监督学习还有密度估计，异常检测等。聚类就是对大量未知标注的数据集，按照数据的内在相似性将数据集划分为多个类别（在聚类算法中称为簇），使类别内的数据相似度高，二类别间的数据相似度低，我们可以使用聚类分析从我们的数据中获得一些有价值的见解，本文我们将研究几种常见的聚类算法，并讨论他们的优缺点。
 
kmeans
 
from copy import deepcopy
import numpy as np
import pandas as pd
import matplotlib
matplotlib.use('TkAgg')
from matplotlib import pyplot as plt

plt.rcParams['figure.figsize'] = (16, 9)
plt.style.use('ggplot')

# 导入数据集
data = pd.read_csv('xclara.csv')
# print(data.shape)
# data.head()

# 将csv文件中的数据转换为二维数组
f1 = data['V1'].values
f2 = data['V2'].values

# 按行的方式计算两个坐标点之间的距离
def dist(a, b, ax=1):
    return np.linalg.norm(a - b, axis=ax)
X = np.array(list(zip(f1, f2)))

# 设定分区数
k = 4
# 随机获得中心点的X轴坐标
C_x = np.random.randint(0, np.max(X)-20, size=k)
# 随机获得中心点的Y轴坐标
C_y = np.random.randint(0, np.max(X)-20, size=k)
C = np.array(list(zip(C_x, C_y)), dtype=np.float32)
# 用于保存中心点更新前的坐标
C_old = np.zeros(C.shape)
print(C)
# 用于保存数据所属中心点
clusters = np.zeros(len(X))
# 迭代标识位，通过计算新旧中心点的距离
iteration_flag = dist(C, C_old, 1)

fig, ax = plt.subplots()
plt.scatter(f1, f2, c='black', s=6)
ax.scatter(C[:, 0], C[:, 1], marker='*', s=200, c='blue')

tmp = 1
# 若中心点不再变化或循环次数不超过20次(此限制可取消)，则退出循环
while iteration_flag.any() != 0 and tmp < 20:
    # 循环计算出每个点对应的最近中心点
    for i in range(len(X)):
        # 计算出每个点与中心点的距离
        distances = dist(X[i], C, 1)
        # print(distances)
        # 记录0 - k-1个点中距离近的点
        cluster = np.argmin(distances)
        # 记录每个样例点与哪个中心点距离最近
        clusters[i] = cluster

    # 采用深拷贝将当前的中心点保存下来
    # print("the distinct of clusters: ", set(clusters))
    C_old = deepcopy(C)
    # 从属于中心点放到一个数组中，然后按照列的方向取平均值
    for i in range(k):
        points = [X[j] for j in range(len(X)) if clusters[j] == i]
        # print(points)
        # print(np.mean(points, axis=0))
        C[i] = np.mean(points, axis=0)

    # 计算新旧节点的距离
    print('循环第%d次' % tmp)
    tmp = tmp + 1
    iteration_flag = dist(C, C_old, 1)
    print("新中心点与旧点的距离：", iteration_flag)

    # 最终结果图示
    colors = ['r', 'g', 'b', 'y', 'c', 'm']
    fig, ax = plt.subplots()
    # 不同的子集使用不同的颜色
    for i in range(k):
        points = np.array([X[j] for j in range(len(X)) if clusters[j] == i])
        ax.scatter(points[:, 0], points[:, 1], s=7, c=colors[i])
    ax.scatter(C[:, 0], C[:, 1], marker='*', s=200, c='black')

plt.show()



 
优点：
 
简单直观，抑郁理解实现；
复杂度相对比较低，在K不是很大的情况下，Kmeans的计算时间相对很短；
Kmean会产生紧密度比较高的簇，反映了簇内样本围绕质心的紧密程度的一种算法。
 缺点：
很难预测到准确的簇的数目；
对初始值设置很敏感（Kmeans++）；
Kmeans主要发现圆形或者球形簇，对不同形状和密度的簇效果不好；
Kmeans对噪声和离群值非常敏感（Kmeadians对噪声和离群值不敏感）
 
LVQ
 
# -*- coding: utf-8 -*-
"""
Created on Tue Jan 29 20:22:18 2019

@author: zmddzf
"""
import numpy as np
import random
from tqdm import tqdm
import matplotlib.pyplot as plt


class LVQ:
    """
    学习向量化算法实现
    attributes:
        train:LVQ
        predict: 预测一个样本所属的簇
    """

    def __init__(self, D, T, lr, maxEpoch):
        """
        初始化LVQ, 构造器
        :param D: 训练集, 格式为[[array, label],...]
        :param T: 原型向量类别标记
        :param lr: 学习率，0-1之间
        :param maxEpoch: 最大迭代次数
        """
        self.D = D
        self.T = T
        self.lr = lr
        self.maxEpoch = maxEpoch
        self.P = []
        # 初始化原型向量，随机选取
        for t in T:
            while True:
                p = random.choice(self.D)
                if p[1] != t:
                    pass
                else:
                    self.P.append(p)
                    break

    def __dist(self, p1, p2):
        """
        私有属性，计算距离
        :param p1: 向量1
        :param p2: 向量2
        :return dist: 距离
        """
        dist = np.linalg.norm(p1 - p2)
        return dist

    def train(self):
        """
        训练LVQ
        :return self.P: 训练后的原型向量
        """
        for epoch in tqdm(range(self.maxEpoch)):
            x = random.choice(self.D)  # 从训练集随机选取样本
            dist = []
            for p in self.P:
                dist.append(self.__dist(p[0], x[0]))  # 计算距离列表

            t = self.P[dist.index(min(dist))][1]  # 确定对应最小距离原型向量的类别
            if t == x[1]:
                # 若类别一致, 则靠拢
                self.P[dist.index(min(dist))][0] = self.P[dist.index(min(dist))][0] + self.lr * (
                            x[0] - self.P[dist.index(min(dist))][0])
            else:
                # 若类别不同, 则远离
                self.P[dist.index(min(dist))][0] = self.P[dist.index(min(dist))][0] - self.lr * (
                            x[0] - self.P[dist.index(min(dist))][0])
        return self.P

    def predict(self, x):
        """
        预测样本所属的簇
        :param x: 样本向量
        :return label: 样本的分类结果
        """
        dist = []
        for p in self.P:
            dist.append(self.__dist(p[0], x))
        label = self.P[dist.index(min(dist))][1]
        return label


# 生成实验数据集，数据集是两个正态分布二维点集
mu1 = 2;
sigma1 = 1
mu2 = 4;
sigma2 = 1
# 生成第一个正态分布
samples1 = np.array([np.random.normal(mu1, sigma1, 50), np.random.normal(mu1, sigma1, 50)])
samples1 = samples1.T.tolist()
label1 = [1 for i in range(50)]
# 生成第二个正态分布
samples2 = np.array([np.random.normal(mu2, sigma2, 50), np.random.normal(mu2, sigma2, 50)])
samples2 = samples2.T.tolist()
label2 = [0 for i in range(50)]
# 合并生成数据集
samples = samples1 + samples2
labels = label1 + label2

# 修改数据格式
data = []
for s, l in zip(samples, labels):
    data.append([np.array(s), l])

# 开始训练
lvq = LVQ(data, [0, 1], 0.1, 5000)
vector = lvq.train()

# 使用lvq分类
prediction = []
for i in data:
    prediction.append(lvq.predict(i[0]))

# 计算accuracy
accuracy = 0
for pred, label in zip(prediction, labels):
    if pred == label:
        accuracy += 1
accuracy = accuracy / len(data)
print("accuracy of LVQ:", accuracy)

# 画图展示原型向量和散点
plt.figure(figsize=(15, 10))
plt.scatter(np.array(samples).T[0], np.array(samples).T[1], c=labels)
plt.scatter(vector[0][0][0], vector[0][0][1], marker='*', s=300)
plt.scatter(vector[1][0][0], vector[1][0][1], marker='*', s=300)

plt.show()

 
LVQ算法其实也是一种基于竞争的学习，这点和无监督的SOM算法挺像的。LVD算法可以被视为一种网络，由输入层、竞争层、输出层组成。输入层很容易理解，就是接受样本的输入；竞争层可以被视为神经元之间的竞争，也就是原型向量之间的竞争，离得最近的神经元（原型向量）获胜，赢者通吃（winner-take-all）；输出层负责输出分类结果。不论是如何理解这个算法，其实本质都是一样的，也就是同类靠拢、异类远离。
 
高斯混合聚类
 
import matplotlib.pyplot as plt
import numpy as np
import math

# 原始数据
x = [0.697, 0.774, 0.634, 0.608, 0.556, 0.403, 0.481, 0.437, 0.666, 0.243,
     0.245, 0.343, 0.639, 0.657, 0.360, 0.593, 0.719, 0.359, 0.339, 0.282,
     0.748, 0.714, 0.483, 0.478, 0.525, 0.751, 0.532, 0.473, 0.725, 0.446]

y = [0.460, 0.376, 0.264, 0.318, 0.215, 0.237, 0.149, 0.211, 0.091, 0.267,
     0.057, 0.099, 0.161, 0.198, 0.370, 0.042, 0.103, 0.188, 0.241, 0.257,
     0.232, 0.346, 0.312, 0.437, 0.369, 0.489, 0.472, 0.376, 0.445, 0.459]


# 矩阵测试
def test_matrix():
    sigma = np.mat([[0.2, 0.1], [0.0, 0.1]])
    sigma_Trans = sigma.T
    sigma_inverse = sigma.I
    print("sigma: {}".format(sigma))
    print("sigma Inverse: {}".format(sigma_inverse))
    print("sigma Transform: {}".format(sigma_Trans))

def gauss_density_probability(n, x, mu, sigma):
    sigma_det = np.linalg.det(sigma)
    divisor = pow(2 * np.pi, n / 2) * np.sqrt(sigma_det)
    exp = np.exp(-0.5 * (x - mu) * sigma.I * (x - mu).T)
    p = exp / divisor
    return p


# 后验概率测试
def test_posterior_probability():
    xx = np.mat([[x[0], y[0]]])
    mu_datasets = [np.mat([[x[5], y[5]]]), np.mat([[x[21], y[21]]]), np.mat([[x[26], y[26]]])]
    sigma = np.mat([[0.1, 0.0], [0.0, 0.1]])
    det = np.linalg.det(sigma)
    print("det: {}".format(det))
    p_all = []
    for mu in mu_datasets:
        p = gauss_density_probability(2, xx, mu, sigma)
        p = p / 3
        p_all.append(p)
    p_mean = []
    for p in p_all:
        p_sum = np.sum(p_all)
        p = p / p_sum
        p_mean.append(p)
    print("probability: {}".format(p_mean[0]))


def posterior_probability(k, steps):

    alpha_datasets = [np.mat([1 / k]) for _ in range(k)]
    xx = [np.mat([[x[i], y[i]]]) for i in range(len(x))]
    mu_rand = np.random.randint(0, 30, (1, k))
    print("random: {}".format(mu_rand[0]))
    #     mu_datasets = [np.mat([[x[i], y[i]]]) for i in mu_rand[0]]
    mu_datasets = [np.mat([[x[5], y[5]]]), np.mat([[x[21], y[21]]]), np.mat([[x[26], y[26]]])]
    sigma_datasets = [np.mat([[0.1, 0.0], [0.0, 0.1]]) for _ in range(k)]
    #     det = np.linalg.det(sigma_datasets[0])
    for step in range(steps):
        p_all = []
        # create cluster
        classification_temp = locals()
        for i in range(k):
            classification_temp['cluster_' + str(i)] = []
        # 后验概率分组
        for j in range(len(x)):
            p_group = []
            for i in range(k):
                mu = mu_datasets[i]
                p = gauss_density_probability(2, xx[j], mu, sigma_datasets[i])

                p = p * alpha_datasets[i].getA()[0][0]
                p_group.append(p)
            p_sum = np.sum(p_group)
            # 取最大后验概率
            max_p = max(p_group)
            max_index = p_group.index(max_p)
            # 最大后验概率聚类
            for i in range(k):
                if i == max_index:
                    classification_temp['cluster_' + str(max_index)].append(j)

            p_group = [p_group[i] / p_sum for i in range(len(p_group))]
            p_all.append(p_group)

        # 更新 mu, sigma, alpha
        mu_datasets = []
        sigma_datasets = []
        alpha_datasets = []

        for i in range(k):
            mu_temp_numerator = 0
            mu_temp_denominator = 0
            sigma_temp = 0
            alpha_temp = 0
            mu_numerator = [p_all[j][i] * xx[j] for j in range(len(x))]
            for mm in mu_numerator:
                mu_temp_numerator += mm

            mu_denominator = [p_all[j][i] for j in range(len(x))]
            for nn in mu_denominator:
                mu_temp_denominator += nn

            mu_dataset = mu_temp_numerator / mu_temp_denominator
            mu_datasets.append(mu_dataset)

            sigma = [p_all[j][i].getA()[0][0] * (xx[j] - mu_dataset).T * (xx[j] - mu_dataset) for j in range(len(x))]
            for ss in sigma:
                sigma_temp += ss
            sigma_dataset = sigma_temp / mu_temp_denominator
            sigma_datasets.append(sigma_dataset)

            alpha_new = [p_all[j][i] for j in range(len(x))]
            for alpha_nn in alpha_new:
                alpha_temp += alpha_nn
            alpha_dataset = alpha_temp / len(x)
            alpha_datasets.append(alpha_dataset)
    return p_all, mu_datasets, sigma_datasets, alpha_datasets, classification_temp


def cluster_visiualization(k, steps):
    post_probability, mu_datasets, sigma_datasets, alpha_datasets, classification_temp = posterior_probability(k, steps)
    plt.figure(figsize=(8, 8))
    markers = ['.', 's', '^', '<', '>', 'P']
    plt.xlim(0.1, 0.9)
    plt.ylim(0, 0.9)
    plt.grid()
    plt.scatter(x, y, color='r')

    plt.figure(figsize=(8, 8))
    for i in range(k):
        # 依据聚类获取对应数据，并显示
        xx = [x[num] for num in classification_temp['cluster_' + str(i)]]
        yy = [y[num] for num in classification_temp['cluster_' + str(i)]]

        plt.xlim(0.1, 0.9)
        plt.ylim(0, 0.9)
        plt.grid()
        plt.scatter(xx, yy, marker=markers[i])
    plt.savefig("./images/gauss_cluster.png", format="png")

if __name__ == "__main__":
    cluster_visiualization(3, 100)

 
算法本身不复杂，可能涉及到矩阵求导的部分会麻烦一点。西瓜数据集太小了，收敛非常快。然后，这个算法同样对于初值敏感。
 
DBSCAN
 
import numpy as np
from sklearn.cluster import DBSCAN
from sklearn import metrics
from sklearn.datasets.samples_generator import make_blobs
from sklearn.preprocessing import StandardScaler


# #############################################################################
# 产生样本数据
centers = [[1, 1], [-1, -1], [1, -1]]  # 生成聚类中心点
X, labels_true = make_blobs(n_samples=750, centers=centers, cluster_std=0.4,random_state=0) # 生成样本数据集

X = StandardScaler().fit_transform(X) # StandardScaler作用：去均值和方差归一化。且是针对每一个特征维度来做的，而不是针对样本。

# #############################################################################
# 调用密度聚类  DBSCAN
db = DBSCAN(eps=0.3, min_samples=10).fit(X)
# print(db.labels_)  # db.labels_为所有样本的聚类索引，没有聚类索引为-1
# print(db.core_sample_indices_) # 所有核心样本的索引
core_samples_mask = np.zeros_like(db.labels_, dtype=bool)  # 设置一个样本个数长度的全false向量
core_samples_mask[db.core_sample_indices_] = True #将核心样本部分设置为true
labels = db.labels_

# 获取聚类个数。（聚类结果中-1表示没有聚类为离散点）
n_clusters_ = len(set(labels)) - (1 if -1 in labels else 0)

# 模型评估
print('估计的聚类个数为: %d' % n_clusters_)
print("同质性: %0.3f" % metrics.homogeneity_score(labels_true, labels))  # 每个群集只包含单个类的成员。
print("完整性: %0.3f" % metrics.completeness_score(labels_true, labels))  # 给定类的所有成员都分配给同一个群集。
print("V-measure: %0.3f" % metrics.v_measure_score(labels_true, labels))  # 同质性和完整性的调和平均
print("调整兰德指数: %0.3f" % metrics.adjusted_rand_score(labels_true, labels))
print("调整互信息: %0.3f" % metrics.adjusted_mutual_info_score(labels_true, labels))
print("轮廓系数: %0.3f" % metrics.silhouette_score(X, labels))

# #############################################################################
# Plot result
import matplotlib.pyplot as plt

# 使用黑色标注离散点
unique_labels = set(labels)
colors = [plt.cm.Spectral(each) for each in np.linspace(0, 1, len(unique_labels))]
for k, col in zip(unique_labels, colors):
    if k == -1:  # 聚类结果为-1的样本为离散点
        # 使用黑色绘制离散点
        col = [0, 0, 0, 1]

    class_member_mask = (labels == k)  # 将所有属于该聚类的样本位置置为true

    xy = X[class_member_mask & core_samples_mask]  # 将所有属于该类的核心样本取出，使用大图标绘制
    plt.plot(xy[:, 0], xy[:, 1], 'o', markerfacecolor=tuple(col),markeredgecolor='k', markersize=14)

    xy = X[class_member_mask & ~core_samples_mask]  # 将所有属于该类的非核心样本取出，使用小图标绘制
    plt.plot(xy[:, 0], xy[:, 1], 'o', markerfacecolor=tuple(col),markeredgecolor='k', markersize=6)

plt.title('Estimated number of clusters: %d' % n_clusters_)
plt.show()
 
DBSCAN的主要优点有：
 1） 可以对任意形状的稠密数据集进行聚类，相对的，K-Means之类的聚类算法一般只适用于凸数据集。
 2） 可以在聚类的同时发现异常点，对数据集中的异常点不敏感。
 3） 聚类结果没有偏倚，相对的，K-Means之类的聚类算法初始值对聚类结果有很大影响。
 DBSCAN的主要缺点有：
 1）如果样本集的密度不均匀、聚类间距差相差很大时，聚类质量较差，这时用DBSCAN聚类一般不适合。
 2）如果样本集较大时，聚类收敛时间较长，此时可以对搜索最近邻时建立的KD树或者球树进行规模限制来改进。
 3） 调参相对于传统的K-Means之类的聚类算法稍复杂，主要需要对距离阈值ϵ，邻域样本数阈值MinPts联合调参，不同的参数组合对最后的聚类效果有较大影响。
 
AGNES
 
 #-*- coding:utf-8 -*-

import math
import pylab as pl

#数据集：每三个是一组分别是西瓜的编号，密度，含糖量
data = """
1,0.697,0.46,2,0.774,0.376,3,0.634,0.264,4,0.608,0.318,5,0.556,0.215,
6,0.403,0.237,7,0.481,0.149,8,0.437,0.211,9,0.666,0.091,10,0.243,0.267,
11,0.245,0.057,12,0.343,0.099,13,0.639,0.161,14,0.657,0.198,15,0.36,0.37,
16,0.593,0.042,17,0.719,0.103,18,0.359,0.188,19,0.339,0.241,20,0.282,0.257,
21,0.748,0.232,22,0.714,0.346,23,0.483,0.312,24,0.478,0.437,25,0.525,0.369,
26,0.751,0.489,27,0.532,0.472,28,0.473,0.376,29,0.725,0.445,30,0.446,0.459"""

#数据处理 dataset是30个样本（密度，含糖量）的列表
a = data.split(',')
dataset = [(float(a[i]), float(a[i+1])) for i in range(1, len(a)-1, 3)]

#计算欧几里得距离,a,b分别为两个元组
def dist(a, b):
    return math.sqrt(math.pow(a[0]-b[0], 2)+math.pow(a[1]-b[1], 2))

#dist_min
def dist_min(Ci, Cj):
    return min(dist(i, j) for i in Ci for j in Cj)
#dist_max
def dist_max(Ci, Cj):
    return max(dist(i, j) for i in Ci for j in Cj)
#dist_avg
def dist_avg(Ci, Cj):
    return sum(dist(i, j) for i in Ci for j in Cj)/(len(Ci)*len(Cj))

#找到距离最小的下标
def find_Min(M):
    min = 1000
    x = 0; y = 0
    for i in range(len(M)):
        for j in range(len(M[i])):
            if i != j and M[i][j] < min:
                min = M[i][j];x = i; y = j
    return (x, y, min)

#算法模型：
def AGNES(dataset, dist, k):
    #初始化C和M
    C = [];M = []
    for i in dataset:
        Ci = []
        Ci.append(i)
        C.append(Ci)
    for i in C:
        Mi = []
        for j in C:
            Mi.append(dist(i, j))
        M.append(Mi)
    q = len(dataset)
    #合并更新
    while q > k:
        x, y, min = find_Min(M)
        C[x].extend(C[y])
        C.remove(C[y])
        M = []
        for i in C:
            Mi = []
            for j in C:
                Mi.append(dist(i, j))
            M.append(Mi)
        q -= 1
    return C
#画图
def draw(C):
    colValue = ['r', 'y', 'g', 'b', 'c', 'k', 'm']
    for i in range(len(C)):
        coo_X = []    #x坐标列表
        coo_Y = []    #y坐标列表
        for j in range(len(C[i])):
            coo_X.append(C[i][j][0])
            coo_Y.append(C[i][j][1])
        pl.scatter(coo_X, coo_Y, marker='x', color=colValue[i%len(colValue)], label=i)

    pl.legend(loc='upper right')
    pl.show()

C = AGNES(dataset, dist_avg, 3)
draw(C)




 
AGNES算法比较简单，但一旦一组对象被合并，下一步的处理将在新生成的簇上进行。已做处理不能撤消，聚类之间也不能交换对象。增加新的样本对结果的影响较大。
 假定在开始的时候有nn个簇，在结束的时候有11个簇，因此在主循环中有nn次迭代，在第ii次迭代中，我们必须在n−i+1n−i+1个簇中找到最靠近的两个进行合并。另外算法必须计算所有对象两两之间的距离，因此这个算法的复杂度为 O(n2)O(n2)，该算法对于nn很大的情况是不适用的。

因为实验中要用到聚类效果的对比，没有时间自己来实现算法，所以Kmeans就用到了sklearn中的Kmeans类，FCM用到了skfuzzy.cmeans。
 
 
 
几个概念
 
1、Kmeans
 
Kmeans是聚类算法中较为经典的算法之一，由于其效率高，所以一般大规模的数据进行聚类的时候都会被广泛应用。
 
算法的目的是，先指定聚类的数目c，然后将输入的数据划分为c类，值簇内的数据之间具有较高的相似程度，而簇之间的相似程度较低。
 
下面简单介绍下Kmeans算法的实现，具体的网上都可以找到。
 
Kmeans的目标函数是：
 
c是聚类的中心，目的就是让每个点到它所属于的中心的距离之和最小。
 
 
因此对目标函数求偏导可以得到如下，其中Nj是第j类中数据点的个数。
 
 
然后就是对所有数据进行repeat直到中心点不再发生变化或者达到了最大的遍历次数。
 
2、FCM
 
FCM是一种基于模糊集合为基础的聚类方法，它是以隶属度来确定每个数据点从属于某个中心。像Kmeans这类算法称为硬聚类，而FCM则称为软聚类，是传统硬聚类的一种改进。为什么叫软跟硬，因为FCM在聚类的时候，会计算每个样本点到中心的隶属度，这个隶属度是一个0~100%的数值，而硬聚类则只有0%和100%，FCM通过这个隶属度可以使我们更加直观的了解一个数据点到中心的可信度。
 
因而这里就要提到一个隶属度矩阵了，为了对比Kmeans，也给Kmeans设置了一个隶属度的矩阵：
 
 
通过上面的对比就可看出关于这个隶属度矩阵的作用了。
 
下面说一下关于FCM算法的思路：
 
FCM的目标函数如下：
 
 
其中m是加权指数，一般的应用区间是[1.5,2.5]。网上也有很多研究是关于FCM中这个m的优化的。
 
可以看出，FCM目标函数就是在Kmeans中目标函数的基础中加入了一个隶属度矩阵。
 
算法训练的过程就是求目标函数的极小值以及此时的隶属度函数，最终的聚类中心就通过最后的隶属度函数来确定。
 
 
 
前提准备
 
 
 
没有安装skfuzzy的话，可以先pip install -U scikit-fuzzy。其中skfuzzy是python中用于研究模糊推理、模糊神经网络的模块，其中有很多实现好的算法和函数。
 
 
 
sklearn.KMeans
 
先看一下Kmeans这个类的参数：
 
    def __init__(self, n_clusters=8, init='k-means++', n_init=10, max_iter=300,
                 tol=1e-4, precompute_distances='auto',
                 verbose=0, random_state=None, copy_x=True, n_jobs=1):
 
1、n_clusters就是k值，一般需要通过测试来选择最好的聚类数目。
 
2、max_iter最大迭代数目，如果是凸函数的话，求导可以得到极值，因而可以不用管，但是如果是非凸函数的话，可能会不收敛，此时可以指定最大的迭代次数。
 
3、init即初始值选择的方式，可以是radom随机选择，或者优化过的k-means++，或者自己指定的初始化的质心。
 
创建了Kmeans对象之后，接着调用fit()函数来训练模型，然后通过predict()可以得到每个数据对应的label。
 
import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans
from skfuzzy.cluster import cmeans


cp = np.random.uniform(1, 100, (100, 2))

train = cp[:50]
test = cp[50:]
km = KMeans(n_clusters=3)
km.fit(train)
result = km.predict(train)
for i in range(50):
    if result[i] == 0:
        plt.scatter(train[i,0],train[i,1], c='r')
    elif result[i] == 1:
        plt.scatter(train[i, 0],train[i,1], c='g')
    elif result[i] == 2:
        plt.scatter(train[i, 0],train[i,1], c='b')
plt.show()
 
 
 
 
 
 
skfuzzy.cmeans
 
 
 
先看一下这个函数的参数跟返回值：
 
def cmeans(data, c, m, error, maxiter, init=None, seed=None):
 
data : 2d array, size (S, N)
        Data to be clustered.  N is the number of data sets; S is the number
        of features within each sample vector.
    c : int
        Desired number of clusters or classes.
    m : float
        Array exponentiation applied to the membership function u_old at each
        iteration, where U_new = u_old ** m.
    error : float
        Stopping criterion; stop early if the norm of (u[p] - u[p-1]) < error.
    maxiter : int
        Maximum number of iterations allowed.
    init : 2d array, size (S, N)
        Initial fuzzy c-partitioned matrix. If none provided, algorithm is
        randomly initialized.
    seed : int
        If provided, sets random seed of init. No effect if init is
        provided. Mainly for debug/testing purposes.
 
 
 
1、data就是训练的数据。这里需要注意data的数据格式，shape是类似（特征数目，数据个数），与很多训练数据的shape正好是相反的。
 
 
 
2、c是需要指定的聚类个数。
 
3、m也就是上面提到的隶属度的指数，是一个加权指数。
 
4、error就是当隶属度的变化小于此的时候提前结束迭代。
 
5、maxiter最大迭代次数。
 
 
 
Returns
    -------
    cntr : 2d array, size (S, c)
        Cluster centers.  Data for each center along each feature provided
        for every cluster (of the `c` requested clusters).
    u : 2d array, (S, N)
        Final fuzzy c-partitioned matrix.
    u0 : 2d array, (S, N)
        Initial guess at fuzzy c-partitioned matrix (either provided init or
        random guess used if init was not provided).
    d : 2d array, (S, N)
        Final Euclidian distance matrix.
    jm : 1d array, length P
        Objective function history.
    p : int
        Number of iterations run.
    fpc : float
        Final fuzzy partition coefficient.
 
返回值：
 
1、cntr聚类的中心。
 
2、u是最后的的隶属度矩阵。
 
3、u0是初始化的隶属度矩阵。
 
4、d是最终的每个数据点到各个中心的欧式距离矩阵。
 
5、jm是目标函数优化的历史。
 
6、p是迭代的次数。
 
7、fpc全称是fuzzy partition coefficient，是一个评价分类好坏的指标。它的范围是0到1，1是效果最好。后面可以通过它来选择聚类的个数。
 
 
 
代码如下：
 
train = train.T
center, u, u0, d, jm, p, fpc = cmeans(train, m=2, c=3, error=0.005, maxiter=1000)

for i in u:
    label = np.argmax(u, axis=0)
print(label)

for i in range(50):
    if label[i] == 0:
        plt.scatter(train[0][i], train[1][i], c='r')
    elif label[i] == 1:
        plt.scatter(train[0][i], train[1][i], c='g')
    elif label[i] == 2:
        plt.scatter(train[0][i], train[1][i], c='b')

plt.show()
 
 
 
 
 
 
 
 
 
 
 
 
还有一个问题就是关于如何选择最好的聚类个数，篇幅的原因，这个打算有时间再写一篇来好好整理下。
 
 
 
 
 
 
 
 

 
实验五:层次聚类实验报告
 
一、实验目的
二、代码框架
三、代码详解
四、实验结果
  
 

 
一、实验目的
 
 
 
了解聚类的概念和层次聚类的方法
实现三种不同的层次聚类算法
对比三种不同算法在不同的数据集的情况下的性能
 
 
二、代码框架
 
 
本次实验使用的函数框架如下:
 
1.create_sample(mean, cov, num, label)
  #生成样本均值向量为mean，协方差矩阵为cov的，数量为num，标签为label的数据集
2.PoMinkowski(x1,x2,dimension,p=2)
  #两样本点之间Minkowski距离，dimension表示样本的特征维数，p=2时，计算的是欧氏距离
3.clusingle(clu1,clu2,dimension,p=2)
  #最短距离/单连接 (single linkage)
4.clucomplete(clu1,clu2,dimension,p=2)
  #最⻓距离/全连接 (complete linkage)
5.cluaverage(clu1,clu2,dimension,p=2)
  #平均距离 (average linkage)
6.discluster(cluster,dimension,kind=0,p=2)
  #类距离矩阵的生成,kind表示使用3,4,5中的哪种方法生成类距离矩阵
7.dismin(distance)
  #根据类距离矩阵确定距离最近的两个类
8.update(cluster,res)
  #更新类，将cluster中的res编号的两个类合并
9.datastat(cluster)
  #数据统计，统计合并完成后生成的三个类的数据
10.aggregation(cluster,dimension,kind=0,p=2)
  #聚合操作
11.makeplt3D(List)
  #根据List绘制三维点空间分布图
12.makeplt2D(List,label1)
  #根据List和label绘制分布直方图
 
 
三、代码详解
 
 
产生数据
 
# 生成数据
def create_sample(mean, cov, num, label):
    '''
    :param mean: 均值向量
    :param cov: 协方差矩阵
    :param num: 数量
    :param label: 标签
    :return: 最终生成的数据前三列表示特征，后一列表示便签
    '''
    x,y,z=np.random.multivariate_normal(mean,cov,num).T
    L = np.ones(num)*label
    X=np.array([x,y,z,L])
    return X.T
 
使用np.random.multivariate_normal函数生成均值向量为mean，协方差矩阵为cov，数量为num，标签为label的样本数据。
 
 
两点之间的距离计算
 
   def PoMinkowski(x1,x2,dimension,p=2):
       '''
       :param x1: 点x1
       :param x2: 点x2
       :param dimension: 两个点所在的空间维度
       :param p: 参数p=2时为欧氏距离
       :return: 距离
       '''
       dis = 0
       for i in range(dimension):
           dis = dis + math.pow(x1[i]-x2[i],p)
       return math.sqrt(dis)
 

 在本次试验中使用闵可夫斯基距离进行计算，默认使用p=2，即计算两个点之间的欧氏距离
 
 
三种层次聚类算法(基本要求和中级要求)
 
# 最短距离single linkage
def clusingle(clu1,clu2,dimension,p=2):

    Min = float("inf")
    for i in range(len(clu1)):
        for j in range(len(clu2)):
            d=PoMinkowski(clu1[i],clu2[j],dimension,p)
            Min = d if d < Min else Min
    return Min

# 最长距离complete linkage
def clucomplete(clu1,clu2,dimension,p=2):

    Max = float("-inf")
    for i in range(len(clu1)):
        for j in range(len(clu2)):
            d = PoMinkowski(clu1[i],clu2[j],dimension,p)
            Max = d if d>Max else Max
    return Max

# 平均距离average linkage
def cluaverage(clu1,clu2,dimension,p=2):
    
    d = 0
    for i in range(len(clu1)):
        for j in range(len(clu2)):
            d = d + PoMinkowski(clu1[i],clu2[j],dimension,p)
    ans = d/(len(clu1)*len(clu2))
    return ans
 
 
使用三种不同的方法(如上图)计算两个类之间的距离，类中两个点之间的距离还是使用欧式距离
 
 
生成类距离矩阵
 
# 类距离矩阵生成
def discluster(cluster,dimension,kind=0,p=2):
    '''
    :param cluster: 类组成的集合
    :param dimension: 点的维度
    :param p: p=2 表示欧式距离
    :param kind: 使用哪种方法求类距离
    :return: 类距离矩阵
    '''
    if kind == 0:
        func = clusingle
    elif kind == 1:
        func = clucomplete
    elif kind == 2:
        func = cluaverage
    else:
        print("para:'kind' error")
        exit(0)

    templist = np.zeros((len(cluster),len(cluster)))
    for i in range(len(cluster)):
        for j in range(len(cluster)):
            templist[i][j]=func(cluster[i],cluster[j],dimension,p)
    return templist
 
kind表示使用哪一种层次聚类方法，定义func为函数指针，templist[i][j]表示第i个类和第j个类的距离
 
 
找到距离最近的两个类的下标，便于后面的合并
 
# 找到类集合中距离最近的两个类
def dismin(distance):
    '''
    :param distance: 类距离矩阵
    :return: 距离最近的两个类的坐标
    '''
    Min = float("inf")
    res=[0,0]
    for  i in range(len(distance)):
        for j in range(len(distance)):
            if i!=j and distance[i][j] < Min:
                Min = distance[i][j]
                res = [i,j]
    return res
 
当i=j时表示的是类和自身的距离，始终为零，当i=j时不需要合并，所以排除j=i的情况，当迭代过类距离矩阵之后，res中储存的是距离最小的两个类的编号
 
 
合并两个类
 
# 聚合操作，更新类
def update(cluster,res):
    a = cluster[res[0]]
    b = cluster[res[1]]
    a.extend(b)
    cluster.remove(b)
 
使用extend将b合并到a中，使用remove从cluster中移除b，实现a和b的合并
 
 
数据统计
 
# 数据统计
def datastat(cluster):
    '''
    :param cluster: 合并之后的类
    :return: count 统计结果 label三类的标签
    '''
    # count统计合并聚类后的三个类中分别含有三种类别样本集合的数量
    count = [[0,0,0],[0,0,0],[0,0,0]]
    for i in range(3):
        for j in range(len(cluster[i])):
            count[i][int(cluster[i][j][3]-1)]+=1
    count=np.array(count)
    # 数量最多的类作为合并后这一类的类标签
    label = count.argmax(axis=1)+1
    return count,label
 
统计合并之后每一类中不同类标签的数量储存在count中，count[0][2]表示cluster[0]中类标签为3的样本数量，列表label中储存合并后每一类是什么标签(根据这一类中最多的类标签)，label[0]储存着cluster[0]是哪一类
 
 
聚合聚类
 
# 聚合聚类
def aggregation(cluster,dimension,kind=0,p=2):
    '''
    :param cluster: 样本空间
    :param dimension: 维度
    :param kind: 求类距离的方法
    :param p: 欧氏距离
    :return: 聚合后的样本空间
    '''
    i = 0
    # 当类的个数多与3时合并继续
    while(len(cluster)>3):
        # 每一次迭代都重新产生类距离矩阵
        distance = discluster(cluster, dimension, kind, p)
        # 求出距离最近的两个类的下标
        res = dismin(distance)
        # 合并两个类
        update(cluster,res)
 
 
绘图函数
 
# 绘制三维空间分布图
def makeplt3D(List):
    point = np.array(List)
    fig = plt.figure()
    ax = fig.add_subplot(111,projection='3d')
    print(point)

    n=len(point)
    #print(n)
    clu = []
    for i in range(3):
        clu.append(list(point[point[:,3]==i+1]))
    #print(clu)

    # symbol中储存点的形状和颜色等
    symbol = [['r','o'],['b','^'],['g','p']]
    for i in range(3):
        temp=[list(c) for c in clu[i]]
        temp=np.array(temp)
        x = temp[:,0]
        y = temp[:,1]
        z = temp[:,2]
        ax.scatter(x,y,z,c=symbol[i][0],marker=symbol[i][1])
    ax.set_xlabel('X')
    ax.set_ylabel('Y')
    ax.set_zlabel('Z')
    plt.show()

# 绘制分布直方图
def makeplt2D(List,label1):
    plt.bar([0.6, 1.7, 2.7], List[0], width=0.2, label=str(label1[0]))
    plt.bar([1, 2, 3], List[1], width=0.2, label=str(label1[1]))
    plt.bar([1.3, 2.3, 3.3], List[2], width=0.2, label=str(label1[2]))

    plt.legend()
    plt.xlabel('预测类别')
    plt.ylabel('数量')
    plt.title(u'预测类别-数量条形图')

    plt.show()
 
 
主体函数
 
   if __name__ == "__main__":
       # 参数设置
       mean = np.array([[1,1,1],[2,2,2],[3,3,3]])
       cov = [[0.7,0,0],[0,0.7,0],[0,0,0.7]]
       n = 501
       P = 1/3
       num = [round(n*P) for i in range(3)]
       total = 0
       # clus储存合并后的矩阵
       clus1 = []
       # 数据生成并集合
       for i in range(3):
           total += num[i]
           clus1.extend(create_sample(mean[i],cov,num[i],i+1))
       # 将矩阵转为类
       clus=[[list(c)] for c in clus1]
       print("总共产生了{}个样本".format(total))
   
       for i in range(3):
           cor = 0
           # 深拷贝
           cluster = copy.deepcopy(clus)
           # 打乱顺序(没什么用)
           random.shuffle(cluster)
           # 聚合聚类
           aggregation(cluster,3,i)
           # string中储存了三个字符串
           print("使用{}-linkage层次聚类算法".format(string[i]))
           # 返回统计信息
           count, label = datastat(cluster)
           
           # 输出每一种层次聚类方法的统计信息
           for i in range(3):
               print("cluster[{}]标签为{}".format(i,label[i]))
           print("每一类的构成及错误率如下:")
           print("cluster\t类\t类1\t类2\t类3\t错误率\n")
           for i in range(3):
               print("  ",i,"\t",label[i],end="")
               for j in range(3):
                   print("\t{}".format(count[i][j],j+1),end="")
               cor += count[i][label[i]-1]
               print("\t{}\n".format(1-count[i][label[i]-1]/sum(count[i])),end="")
           print("综上:总的错误率为{}".format(1-cor/total))
 
在这里，要注意的点是
 
  
 
在生成数据的时候，我们要将每一个数据转换为二维列表：因为
 
在第一次产生类距离矩阵的时候，我们计算两个类之间的距离，在这个过程中需要计算两个类中每个点之间的距离，如果类是一个一维列表，如下
 
 
此时每个列表中的样本数据为一个array数组，可以认为是一维数组。然后运行，结果报错如下:
 
 
显示无效的下标，这是因为在层次聚类函数中，我们需要对每个类中的每个点进行计算，遍历过程如下：
 
    Min = float("inf")
    for i in range(len(clu1)):
        for j in range(len(clu2)):
            d=PoMinkowski(clu1[i],clu2[j],dimension,p)
            Min = d if d < Min else Min
    return Min
 
两重循环遍历两个类中的所有点，但是在第一次遍历的过程中，每个类只有一个点，此时我们每个类是一维向量，range(len(clu1))却是等于4(三个特征值，一个标签)，所以在计算点距离的时候x1和x2不是点而是float型的特征值，所以会报错。
 
 
  
 
除此之外，我们在生成数据的时候数据不能为array类型，只能为基本的list类型否则会报错如下:
 
 
这是因为在使用list.remove(arg)的过程中，程序首先在list中匹配和arg相等的元素，相等为true，不等为false，涉及到了数据的比较运算。但是，array类型元素的比较不太一样，它返回的是一组的bool值示例如下:
 
a = np.array([1,2,3])
b = np.array([1,2,4])
print(type(a),type(b))
print(a == b)
 

 比较两个array类型的数据，可以使用any和all，如下：
 
print(any(a==b))
print(all(a==b))
 

 综上两点使用如下方法转换数据为我们需要的数据:
 
clus=[[list(c)] for c in clus1]
 
 
 
四、实验结果
 
(在这里使用不同的协方差矩阵进行对比分析)
 
(1) 实现 single-linkage 层次聚类算法
 
(2) 实现complete-linkage 层次聚类算法
 
(3) 实现average-linkage层次聚类算法
 
在这里使用生成102个样本(2000个样本运行有些慢)
 
 
 
当协方差矩阵为[[5, 0, 0], [0, 5, 0], [0, 0, 5]]时:
 
 
 
当协方差为5时，三种类别的层次聚类算法的错误率都很高，都到了50%以上，而且我们发现此时的样本聚类都是聚集在某一类中，PS:我们的数据集中三类数据是平均产生的，相比较而言，此时的average-linkage层次聚类算法的性能比较好。
 
 
 
当协方差矩阵为[[0.5, 0, 0], [0, 0.5, 0], [0, 0, 0.5]]时:
 
 
 
当协方差为0.5时，single和average算法仍然出现了严重的分类不均问题。single-linkage算法的错误率并没有明显的下降，仍然为65%上下，complete-linkage算法下降为了14.7%，average-link算法的错误率下降为了33%，此时性能最好的仍然是complete-link层次聚类算法
 
 
 
当协方差矩阵为[[0.05, 0, 0], [0, 0.05, 0], [0, 0, 0.05]]时
 
 
 
当协方差为0.05时，三者的分类准确率均为100%，没有可比性，因为当协方差为0.05时，三类数据都是泾渭分明的，如下图：
 
 
(4) 绘图聚类前后样本分布情况
 
 
 
聚类前后样本点在空间中的位置并没有改变(以协方差为0.5为例)，如下图:
 
 
 
 
 
聚类后三类的分布直方图(以协方差=0.5为例)如下:
 
 此时的数据如下