精华内容
下载资源
问答
  • 0 写在前面(数据集和源代码)本文章...一共有四个代码文件,分别是Kmeans、Kmeans++、Birch和KNN算法,四个算法同一个数据集聚类分析进行对比试验。(本代码是本人自己书写,全部可用!)1 引言近年来,机器学习...

    0 写在前面(数据集和源代码)

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


    1 引言

    近年来,机器学习已成为计算机前沿中火热的研究点之一。我国政府也将机器学习纳入了国家级战略。目前,机器学习已广泛用于各种数据挖掘、模式识别、语音识别及图像处理等各领域。本文以机器学习中四个经典的聚类算法进行对比介绍和对比实验,得出四个算法对相同实验数据集的聚类效果。

    2聚类算法

    聚类在学术界并没有一个确切的定义,此处给出1974Everitt对聚类的定义:一个类簇内的实体是相似的,不同类簇的实体是不相似的;一个类簇是测试空间中点的会聚,同一类簇的任意两个点间的距离小于不同类簇的任意两个点间的距离[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()
    
    
    
    

    优点:

    1. 简单直观,抑郁理解实现;
    2. 复杂度相对比较低,在K不是很大的情况下,Kmeans的计算时间相对很短;
    3. Kmean会产生紧密度比较高的簇,反映了簇内样本围绕质心的紧密程度的一种算法。
      缺点:
    4. 很难预测到准确的簇的数目;
    5. 对初始值设置很敏感(Kmeans++);
    6. Kmeans主要发现圆形或者球形簇,对不同形状和密度的簇效果不好;
    7. 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很大的情况是不适用的。

    展开全文
  • skfuzzy.cmeans与sklearn.KMeans聚类效果对比以及使用方法

    万次阅读 热门讨论 2018-03-16 18:42:36
    因为实验中要用到聚类效果的对比,没有时间自己来实现算法,所以Kmeans就用到了sklearn中的Kmeans类,FCM用到了skfuzzy.cmeans。   几个概念 1、Kmeans Kmeans是聚类算法中较为经典的算法之一,由于其效率高,...

    因为实验中要用到聚类效果的对比,没有时间自己来实现算法,所以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. 了解聚类的概念和层次聚类的方法
    2. 实现三种不同的层次聚类算法
    3. 对比三种不同算法在不同的数据集的情况下的性能

    二、代码框架

    • 本次实验使用的函数框架如下:

      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绘制分布直方图
      

    三、代码详解

    1. 产生数据

      # 生成数据
      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的样本数据。

    2. 两点之间的距离计算

         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,即计算两个点之间的欧氏距离

    3. 三种层次聚类算法(基本要求和中级要求)

      # 最短距离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
      

      在这里插入图片描述

      使用三种不同的方法(如上图)计算两个类之间的距离,类中两个点之间的距离还是使用欧式距离

    4. 生成类距离矩阵

      # 类距离矩阵生成
      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个类的距离

    5. 找到距离最近的两个类的下标,便于后面的合并

      # 找到类集合中距离最近的两个类
      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中储存的是距离最小的两个类的编号

    6. 合并两个类

      # 聚合操作,更新类
      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的合并

    7. 数据统计

      # 数据统计
      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]是哪一类

    8. 聚合聚类

      # 聚合聚类
      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)
      
    9. 绘图函数

      # 绘制三维空间分布图
      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()
      
    10. 主体函数

         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型的特征值,所以会报错。

      1. 除此之外,我们在生成数据的时候数据不能为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为例)如下:
    在这里插入图片描述
    此时的数据如下
    在这里插入图片描述

    展开全文
  • 文献聚类结果可视分析方法研究1 论文概述1.1 摘要1.2 引言1.3 脉络2 可视分析框架2.1 框架概述2.2 框架组成3 可视化设计3.1 语料结构可视化3.2 语料内容可视化3.3 聚类结果调整和优化4 系统实现及案例分析4.1 选择...
  • 各种聚类算法(原理+代码+对比分析)最全总结

    万次阅读 多人点赞 2017-12-14 10:41:20
    不同类对象之间的相似度尽可能地小。 二、聚类算法分类 1.基于划分 给定一个有N个元组或者纪录的数据集,分裂法将构造K个分组,每一个分组就代表一个聚类,K<N。 特点:计算量大。很适合发现中小规模的数据库中...
  • 有一个实验要求对比两种大数据聚类算法的性能,具体的代码也不是由我实现的,我只是改了一部分,主要还是博客大佬们的代码,我这里借用了一下~~ 具体的实验报告和python源码文件在最后位置,提供百度云下载,本文...
  • 针对套用传统的聚类方法数据流的聚类是行不通的这一问题,提出一种以遗传模拟退火算法为基础的模糊C...通过将SAGA_FCM算法和FCM算法聚类数据流的实验结果进行对比,得出采用SAGA_FCM算法聚类数据流会取得较好的效果。
  • Vincent S.Tseng等人提出的基于聚类和遗传算法的时间序列分割算法中,对于适应值函数的定义存在缺陷,本文对此进行了改进:用归一化处理消除子序列幅度距离计算的影响,并引入类间距使分割结果的类间差异(模式之间的...
  • 要适应足球高密度和高水平的比赛,必须球员的各项身体素质进行评定,每个球员都有各自的优势与劣势。其中,进行评定的身体素质为: 1.2具体数据及来源 二、K-means 三、Fuzzy C-means 3.1原理讲解 模糊c-均值...
  • 聚类算法研究

    2012-09-29 15:14:44
    要从正确率和运行效率两个方面进行模拟实验, 并分别就同一种聚类算法、不同的数据集以及同一个数据集、不同聚类算法的聚类情况进行对比分析. 最后通过综合上述两方面信息给出聚类分析的研究热点、难点、不足和...
  • 一、实验项目名称: 聚类分析方法 二、实验目的与要求: 在软件方面:会用Clementine软件进行聚类分析。 在理论方面:聚类分析及其常用的聚类分析方法,数据挖掘中的聚类分析。 三、实验原理: 1、聚类分析方法 聚类...
  • 聚类

    千次阅读 2017-04-21 21:57:17
     如果说 K-means 和 GMM 这些聚类的方法是古代流行的算法的话,那么这次要讲的 Spectral Clustering 就可以算是现代流行的算法了,中文通常称为“谱聚类”。由于使用的矩阵的细微差别,谱聚类实际上可以说是...
  • 提出了一种基于二次离散小波变换(DWT)的语音增强算法。该算法首先带噪语音信号进行离散小波变换,提取离散细节信号,并其...对比实验结果表明,该方法具有良好的消除噪声的效果,提高了语音的清晰度和可懂度。
  • 检索结果聚类可以方便用户快速浏览搜索引擎返回结果。为了提取主题表达能力和可读性强的类别标签,获取高质量的聚类...算法的对比实验表明:提出方法在类别标签的可读性、有效性以及聚类性能上都优于以上3种方法。
  • Vincent S.Tseng等人提出的基于聚类和遗传算法的时间序列分割算法中,对于适应值函数的定义存在缺陷,本文对此进行了改进:用归一化处理消除子序列幅度距离计算的影响,并引入类间距使分割结果的类间差异(模式...
  • ©PaperWeekly 原创 ·作者|李云帆学校|四川大学博士生研究方向|聚类,无监督表示学习论文标题:Contrastive Clustering论文来源:AAAI 2021论文链...
  • 文章目录系列文章目录开源一、实验简介二、相关理论及知识点二、实验流程1.导入库2.载入数据集3. 在x和y坐标中采样4. 预测分类边界5. 只取前两维数据6. 构造支持向量机对比分析7. 绘制图像8.四种支持向量机分析结果9...
  • 文 | 花小花Posy大家好,我是小花。对比学习的大火???? 越来越旺了,已然从CV蔓延到NLP了。今天给大家介绍的正是一篇将对比学习应用到文本聚类上的工作,NAACL21新鲜出炉的pa...
  • 本文提出一种纠错式主动学习成约束的方法,探讨了主动学习...通过在UCI基准数据集以及人工数据集的实验表明,在该学习策略下,半监督聚类算法的性能好于对比算法;在停止条件下,每个数据集的聚类结果都是可接受的。
  • C均值聚类算法与分级聚类算法的聚类...采用C均值聚类算法男女生样本数据中的身高、体重2个特征进行聚类分析,考察不同的类别初始值以及类别数对聚类结果的影响,并以友好的方式图示化结果。 采用分级聚类算法...
  • 层次聚类算法

    万次阅读 2016-06-05 09:23:29
    层次聚类算法是一个应用广泛的算法,小编最近要做对比实验,实现了其中一个版本,为了验证实验效果,结合我国各省会城市之间的距离,省进行聚类看看效果如何。所有本文从3部分来介绍,首先简介层次聚类算法,然后...
  • C均值聚类算法

    千次阅读 多人点赞 2019-06-28 14:18:03
    请使用C均值聚类方法数据集进行聚类,给每个样本一个类别标签,并画出聚类结果(参考图trainning sample的画法),并与其真实标签(在truelabel.mat中)进行对比,计算聚类的准确率; 3.算法思想 采用距离作为...
  • 聚类算法

    2020-08-17 20:20:02
    聚类算法是我论文实验部分的对比算法,一对比发现,谱聚类真的太强了,聚类效果很好,对不同的数据分布有很强的适应性,速度还快。下文全部参考https://www.cnblogs.com/pinard/p/6221564.html,写得太棒了,自己...
  • Kmeans实现数据聚类

    2021-07-17 15:17:29
    2、已经第一个样本点X1=82,X2=63属于类别,聚类进行矫正; 3、基于数据2建立KNN模型,思考与其聚类模型对比; 4、修改Kmeans迭代次数与初始化参数,查看模型迭代过程中的结果变化。 代码实现: 数据加载 ....
  • K-means 聚类

    2020-05-29 00:07:42
    文章目录K-means 聚类实验目标算法原理算法流程图实验结果分析中心点选择方法1中心点选择方法2代码 实验目标 cluster.dat 里的数据进行聚类分析。其中,cluster.dat 包含了若干二维输入数据(但不包含其输出)...
  • 使用不同的评估方法对实验结果进行评估。 实验准备 sklearn库 自2007年发布以来,scikit-learn已经成为Python重要的机器学习库了,scikit-learn简称sklearn,支持包括分类,回归,降维和聚类四大机器学习...
  • 针对图像聚类问题,提出了一种基于图像空间关系的...该文通过实验分析了图像样本大小、图像特征维数、图像特征类型、初始类别标签对聚类结果的影响,通过与多种经典聚类算法进行对比,实验结果充分验证了该方法的有效性。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 9,621
精华内容 3,848
关键字:

对不同聚类结果对比实验