精华内容
下载资源
问答
  • 一元概率层次聚类

    2018-01-21 12:29:17
    本文依据《数据挖掘概念与技术》中的概率层次聚类算法而来,但与其略有不同。概率层次聚类是利用概率模型来度量簇之间的距离,本质是实现簇之间的合并。本算法需要一个前提条件,数据集被事先分为一些簇,并且没有...

    本文依据《数据挖掘概念与技术》中的概率层次聚类算法而来,但与其略有不同。概率层次聚类是利用概率模型来度量簇之间的距离,本质是实现簇之间的合并。本算法需要一个前提条件,数据集被事先分为一些簇,并且没有单个点簇的情况,同时,数据是符合正太分布的。另外,与原书不同的是,本文增加了一个参数:簇合并门限。

    算法的伪代码如下:

    设定簇合并门限th
    计算所有簇的最大似然值PC
    while 1 寻找可以合并的簇,直到没有为止
        for i 遍历现有的簇C
           计算第i个簇与其他簇之间的距离temp
        end
        if temp中的最小距离小于门限th
           合并第i与最小距离的簇
           重新计算i的最大似然PC(i),并做开方
        end
    end
    

    本算法的Matlab实现程序为:

    clc;
    clear;
    %加载测试数据文件
    fileID = fopen('D:\matlabFile\PHC\PHC.txt');
    DS=textscan(fileID,'%f %f ');
    fclose(fileID);
    %元组类型,为每一个对象创建一个簇
    C=cell(length(DS{1,1}),1);
    for i=1:length(DS{1,1})
        C{i,1}=[DS{1,1}(i),DS{1,2}(i)];
    end
    %设定簇合并门限
    th=1;
    %计算每一个簇的最大似然值
    PC=zeros(1,1);
    for i=1:size(C,1)
        PC(i)=CalcMLE(C{i,1});
    end
    %合并满足条件的簇
    while 1
        %遍历寻找两个簇,如满足条件就合并
        Row=size(C,1);
        if Row==1
            break;
        end
        for i=1:Row-1
            temp=zeros(Row-i,1);        
            for j=i+1:Row
                %合并第i和第j个簇,形成临时簇
                C_temp=cat(2,C{i,1},C{j,1});
                %计算合并后的临时簇的最大似然值
                PCij=CalcMLE(C_temp);            
                temp(j-i)=abs(log(PCij/(PC(i)*PC(j))));
            end
            if min(temp)<th
                %寻找最大值的下标
                index=find(temp==min(temp));
                %合并簇
                C{i,1}=cat(2,C{i,1},C{i+index,1});
                %计算合并后的簇的最大似然,并作开方处理
                PC(i)=sqrt(CalcMLE(C{i,1}));
                %删除被合并的簇和最大似然
                C(i+index,:)=[];
                PC(i+index)=[];
                break;
            end
        end
         %循环结束
        if i==Row-1
            break;
        end
    end

    CalcMLE函数的实现如下:

    function P=CalcMLE(X)
    %利用系统函数计算均值和方差
    Phat=mle(X);
    %计算最大似然值
    P=1;
    for i=1:length(X)
        P=P*exp(-(X(i)-Phat(1))^2/(2*Phat(2)^2))/sqrt(2*pi*Phat(2)^2);
    end
    end
    

    实验数据文件为,请复制后保存为txt格式:

    -2.01 -1.9
    -1.8 -1.93
    5.01 4.9
    5.4 5.32
    5.44 5.35

    展开全文
  • 提出一种基于维度概率摘要模型的凝聚层次聚类算法.实验分析发现,所提模型和算法能够产生高质量的聚类,能够避免噪声点的影响并发现离群点,能够自动发现聚类,算法稳定可靠且对高维数据集聚类效果很好.
  • 层次聚类算法(HCA)是一种聚类分析方法,它通过层次结构搜索聚类的最佳分布。层次聚类的策略通常有两种类型:使用自下而上的过程进行聚集,而使用自上而下的过程进行分裂。但是,大多数聚类方法都有两个缺点:使用...
  • 基于层次聚类方法,是对给定的数据进行层次的分解,直到某种条件满足为止。首先将数据点组成一颗聚类树,根据层次,自底向上或是自顶向下分解。层次的方法可以分为凝聚的方法和分裂的方法。 凝聚的方法,也称为自...

    基于层次的聚类方法,是对给定的数据进行层次的分解,直到某种条件满足为止。首先将数据点组成一颗聚类树,根据层次,自底向上或是自顶向下分解。层次的方法可以分为凝聚的方法和分裂的方法。
    凝聚的方法,也称为自底向上的方法,初始时每个数据点都被看成是单独的一个簇,然后通过逐步合并相近的数据点或簇,形成越来越大的簇,直到所有的数据点都在一个簇中,或者达到某个终止条件为止。
    凝聚的方法:
    步骤1:用异常侦测等方法去离群点。
    为了提高凝聚方法的分类效率和优化分类效果,首先应用异常侦测等方法去离群点。我们通常采用基于概率分布模型的方法,一元或多元正太分布分析方法,如果数据点不能很好地拟合一个概率模型,或者说它不服从该分布,则将该数据点标识为离群点。
    步骤2:用密度分类的方法将数据分成许多小类。
    采用了诸如DBSCAN的基于密度的划分算法,将数据划分足够小的类,以便减少凝聚算法的高昂成本,并且该步骤可逆,即如果后面的凝聚算法得不到一个全局优解,可以重复本步。
    步骤3:自底向上凝聚算法(AGNES-AGglomerative NESting).
    自底向上凝聚的逻辑算法如下:
    输入:包含n个数据点的数据库,终止条件簇的数目k。
    输出:k个簇,达到终止条件规定簇数目。
    将每个数据点当成一个初始簇;
    重复以下步骤:
    1)根据两个簇中最近的数据点找到最近的两个簇。
    2)合并两个簇,生成新的簇的集合。
    3)达到定义的簇的数目时终止。

    分裂的方法,也称为自顶向下的方法。它与凝聚层次聚类恰好相反,初始时将所有的数据点置于一个簇中,然后逐渐细分为更小的簇,直到最终每个数据点都在单独的一个簇中,或者达到某个终止条件为止。
    1)用异常侦测等方法去离群点。步骤同上;
    2)DIANA(DIvisive ANAlysis,自顶向下分裂算法)逻辑算法。
    自顶向下分裂算法步骤如下:
    输入:包含n个数据点的数据库,终止条件簇的数目k。
    输出:k个簇,达到终止条件规定簇数目。
    1)将所有数据点设为初始簇数目。
    2)找出S中与其他点平均相异度最大的点X1,将X1放入新簇S1。
    3)根据S中剩余点到最近的距离重新分簇,于是产生两个新簇S1和S2。
    4)将S1和S2中直径大的簇,重复2)、3)步。
    5)生成k个新簇时终止。
    6)应用轮廓系数方法对分裂方法聚类结果评估。
    分裂法在生活中也是可以看到的。例如,下火车或下公交车的人群按照目的地分裂:先按照大方向分裂,再按小方向分类,最后再到各自的目的地。

    综合层次聚类方法:
    1.BIRCH算法
    BICH(Balanced Iterative Reducing and Clustering using Hierarchies)算法是一个综合性的层次聚类方法,它利用层次方法的平衡迭代进行归约和聚类。其核心是用一个聚类特征(CF)三元组表示一个簇的有关信息,从而使簇中的点可用对应的聚类特征表示。它通过构造满足分支因子和簇直径限制的聚类特征树来求聚类。该算法通过聚类特征可以方便地进行中心、半径、直径及类内、类间距离的运算。
    聚类特征是一个三维向量,CF(n,LS,SS),其中n是数据点的个数,LS是n个点的线性和,SS是n个点的平方和。通过CF可以方便地求中心、半径、直径及类内、类间距离。CF树有两个参数:

    分支因子beta,通过它定义每个非叶子结点的子女的最大数目。
    阈值T,存储在叶节点中的子簇的最大直径。
    算法实现流程如下:
    1)用异常侦测等方法去离群点。同上;
    2)扫描数据库,建立一个初始的CF树。它可以被看做一个数据的多层压缩,试图保留数据内在的聚类结构。当一个数据点被插入到最近的叶节点(子聚类)中时,随着数据点的插入,CF树被动态地构造,不要求所有的数据读入内存,可在外存上逐个读入数据项。因此,BIRTH方法对增量或动态聚类也非常有效。
    3)采用某个聚类算法对CF树的叶节点进行聚类。在这个阶段可以执行任何聚类算法,例如典型的划分方法。BIRCH算法试图利用可用的资源来生成最好的聚类结果。通过一次扫描就可以进行比较好地聚类,故该算法的计算复杂度是O(n),n是数据点的数目。
    4)应用轮廓系数方法对分裂方法聚类结果评估。同上
    该算法的优点是数据点数目具有线性易伸缩性,并具有良好的聚类质量,一次扫描就可以进行较好的聚类。缺点是BIRCH算法只适用于类的分布呈凸形及球形的情况,对不可视的高维数据则不可行。
    BIRCH逻辑算:
    输入:包括n个数据点的数据集合D=[x1,x2,…,xn]及阈值T。
    输出:簇集合。
    过程:
    1)扫描数据集,建立初始的CF树。
    2)对每个数据点xi执行如下操作。
    3)为xi找一个正确的待插入的叶子节点。
    4)如果阈值条件不被破环,则将xi插入到叶子节点中,并从被插入的叶子节点到根节点依次更新CF三元组。
    5)否则,如果有叶子节点空间,则将xi作为单独的簇插入到树中,并更新CF三元组。
    6)否则分类叶子节点,重新安排CF三元组。
    CURE算法:
    CURE(Clustering Using Representatives)算法中既有层次部分,也有划分部分,所以CURE也是一个综合性的聚类算法。
    前面讲到的聚类算法倾向于处理簇为球形、且簇的大小相似的聚类问题,并且对孤点较为敏感。CURE采用了多个点代表一个簇的方法,可以较好地处理以上问题。并且在处理大数据量的时候采用了随机抽样、分区的方法,来提高其效率,使得其可以高效地处理大量数据。
    算法实现流程如下:
    1)用异常侦测等方法去离群点,同上;
    2)对原始数据进行随机抽样,将样本进行等量划分,划分后便形成了以这些样本点为代表的分区。
    3)对于每一个分区,再使用层次聚类算法中的凝聚算法。再凝聚算法中的每一步,距离最近的代表性点所对应的簇将被合并。它们之间的距离被定义为两个簇中代表性点之间距离的最小值。
    4)应用轮廓系数方法对分裂方法聚类结果评估。同上
    CURE算法的具体步骤如下:
    1)从原始数据集中抽取一个随机样本S。
    2)为了加速聚类,把样本划分成p份,每份大小相等。
    3)对每个划分进行局部聚类。
    4)根据局部聚类结果,通过随机抽样剔除孤立点。主要有两种措施:如果一个簇增长得太慢,就去掉它;在聚类结束的时候,非常小的类被剔除。
    5)对上一步中产生的局部的簇进一步聚类。从每个簇中选择c(常数)个数,然后通过应用收缩因子a,将这些分散的点向簇的质心方向收缩。当a为1的时候,所有点都收缩成一点,即质心。通过多个有代表性的点,簇的形状可以更好地被表达出来。
    6)用相应的簇标签来记数据。
    CURE算法的优点是它回避用所有点或单个质心来表示一个簇的传统方法,而实将一个簇用多个具有代表性的点来表示,是CURE可以适应非球形的几何形状。
    另外,收缩因子降低了噪声对聚类的影响,从而使CURE对孤点的处理更加健壮,而且能识别非球形和大小变化比较大的簇,对于大型数据库具有良好的伸缩性。缺点是参数设置对聚类结果有很大的影响,不能处理分类属性。CURE的复杂的复杂度O(n),其中n是数据点的数目。

    展开全文
  • 层次概率聚类算法

    千次阅读 2016-03-06 14:55:48
  • 提出了一种基于音素后验概率层次凝聚聚类算法的音素边界检测方法。该方法首先利用改进的TRAP结构提取语音信号的帧级音素后验概率;然后,运用层次凝聚聚类算法将提取的音素后验概率进行聚类分析;最后根据其全部的...
  • 基于连通模型(connectivited-based):如层次聚类,按照对象之间的距离聚类。(距离的定义可以有很多种)。 基于中心点(centroid-based):如K-means,每个cluster都维持有一个中心点。 基于分布模型(distribution-...

    聚类算法

    常见的聚类算法可以分为四类:

    • 基于连通模型(connectivited-based):如层次聚类,按照对象之间的距离聚类。(距离的定义可以有很多种)。
    • 基于中心点(centroid-based):如K-means,每个cluster都维持有一个中心点。
    • 基于分布模型(distribution-based):如高斯混合模型(GMM),假设数据集中的点是由一种混合的概率模型采样所得,将多有可能同属于一组分布的点聚在一起。
    • 基于密度(density-based),如DBSCAN和OPTICS,密度高的区域被分为一个cluster,不同cluster由密度低的区域分割开,低密度处的样本被视为噪音

    层次聚类(hierarchial cluster)

    层次聚类方法可以分为两类:

    • Agglomerative层次聚类(自底向上,bottom-up聚类):
      每一个对象都是一个cluster,选最近的cluster合并,最终所有的对象都属一一个cluster
    • Divisive层次聚类(自顶向下,top-botttom聚类);
      所有的对象都属一一个cluster,按一定规则将cluster划分,最终每一个对象都是一个cluster
      层次聚类示意图

    层次聚类算法是一种贪心算法(greedy algorithm),每一次执行都是某种程度上的局部最优

    Agglomerative层次聚类方法

    如存在距离矩阵D(距离可以通过不同度量方式得到)
    12345D1=12345[0.02.00.06.05.00.010.09.04.00.09.08.05.03.00.0] \qquad\qquad\quad\begin{matrix} 1&\quad 2&\quad 3 &\quad 4&\quad 5 \end{matrix} \\ D_1= \begin{matrix} 1\\2\\3\\4\\5 \end{matrix} \begin{bmatrix} 0.0 & \\ 2.0 &0.0 \\ 6.0 &5.0 &0.0 \\ 10.0 &9.0 &4.0 &0.0 &\\ 9.0 &8.0 &5.0 &3.0 &0.0 &\\ \end{bmatrix}
    最小的非零值为d(1,2))=2.0d_{(1,2))}=2.0,因此将1,2聚类,并重新计算距离矩阵D2D_2
    d(12)3=min(d13,d23)=d23=5.0d(12)4=min(d14,d24)=d24=9.0d(12)5=min(d15,d25)=d25=8.0 d_{(12)3}=min(d_{13},d_{23})=d_{23}=5.0\\ d_{(12)4}=min(d_{14},d_{24})=d_{24}=9.0\\ d_{(12)5}=min(d_{15},d_{25})=d_{25}=8.0\\

    (12)345D1=(12)345[0.05.00.09.04.00.08.05.03.00.0] \qquad\qquad\quad \begin{matrix} (12)&\quad 3 &\quad 4&\quad 5 \end{matrix} \\ D_1= \begin{matrix} (12)\\3\\4\\5 \end{matrix} \begin{bmatrix} 0.0 & \\ 5.0 &0.0 \\ 9.0 &4.0 &0.0 \\ 8.0 &5.0 &3.0 &0.0 &\\ \end{bmatrix}

    以此类推:

    (12)345D2=(12)345[0.05.00.09.04.00.08.05.03.00.0]   (12) 3 (45)D3=(12)3(45)[0.05.00.08.04.00.0](12)(3(45))D4=(12)(3(45))[0.05.00.0]D5=[0.0] \qquad\qquad\quad\begin{matrix} (12)&\quad 3 &\quad 4&\quad 5 \end{matrix} \\ D_2= \begin{matrix} (12)\\3\\4\\5 \end{matrix} \begin{bmatrix} 0.0 & \\ 5.0 &0.0 \\ 9.0 &4.0 &0.0 \\ 8.0 &5.0 &3.0 &0.0 &\\ \end{bmatrix} \longrightarrow \\ \\ \qquad\ \ \ \begin{matrix} (12)&\ 3 &\ (45) \end{matrix} \\ D_3= \begin{matrix} (12)\\3\\(45) \end{matrix} \begin{bmatrix} 0.0 & \\ 5.0 &0.0 \\ 8.0 &4.0 &0.0 \\ \end{bmatrix} \longrightarrow \\ \\ \qquad\qquad\quad\begin{matrix} (12)&\,(3(45)) \end{matrix} \\ D_4= \begin{matrix} (12)\\(3(45)) \end{matrix} \begin{bmatrix} 0.0 & \\ 5.0 &0.0 \\ \end{bmatrix} \longrightarrow \\ \\ D_5=[0.0]

    参考:Brian S. Everitt, Sabine Landau, Morven Leese, Daniel tahl. Clustering Analysis 5th Edition[M], WILEY SERIES IN PROBABILITY AND STATISTICS, 2011

    展开全文
  • 为了使 Context模型中的条件概率分布更加方便统计并且收敛于信源的实际概率分布,本文使用层次聚类算法对已经建立的Context模型中的条件概率分布按照描述长度最短的原则进行聚类合并。实验证明此方法可以解决基于K-...
  • 将社区结构中的结点看作信号源,针对信号传递过程中存在信号缺失情况,提出了一种层次聚类社区发现算法。该算法通过度中心性来度量节点接收信号的概率,用于量化节点接受信号过程中的缺失值。经过信号传递,使网络的...
  • 热图中的层次聚类

    2021-04-16 19:47:18
    首先明白相关系数这个东西 相关关系是一种非确定性的关系,相关系数是研究变量之间线性相关程度的量 简单相关系数:又叫相关系数或线性相关系数,一般用字母r表示,用来度量两个变量间...不是概率分布时协方差公式: .
  • 关于文本的Brich层次聚类

    千次阅读 2019-03-17 22:21:27
    1.文本聚类的一般性过程: ...在一个高维空间中,几千个点几乎都聚在了一起,虽说彼此之间有距离,但是距离非常之小,很明显这样聚类效果肯定非常差,实测过,跟抛硬币的概率一样。于是将矩阵稠密一...
  • 多维变量X服从高斯分布时,它的概率密度函数PDF为: x是维度为d的列向量,u是模型期望,Σ是模型方差。在实际应用中u通常用样本均值来代替,Σ通常用样本方差来代替。很容易判断一个样x本是否属于类别C。因为每个...
  • 聚类中心越远的点会有更高的概率被选为第????+1个聚类中心。只有在选取第一个聚类中心(????=1)时是通过随机的方法。该改进方法符合一般的直觉:聚类中心互相之间距离得越远越好。这个改进直观简单,也非常有效。 K...
  • 目录条件概率的拓展极大似然估计EM(Expectation-Maximization)算法聚类算法K-means(约束簇)DSCAN(非约束簇)层次聚类(非约束簇)AP(非约束簇)总结矩阵降维稀疏自编码器PCA算法ICA算法字典学习线性判别分析...
  • 详细介绍聚类分析的一些基本概念和主要的方法,并给出了一些示例进行分析。包括k-均值算法、BIRCH算法、Chameleon算法、概率层次聚类、距离度量等。适合教学和复习使用。
  • 9 聚类

    2019-09-17 22:53:54
    文章目录9.1 聚类任务9.2 性能度量9.3 距离计算9.4 原型聚类9.4.3 高斯混合聚类回顾下(多元)高斯分布的定义定义高斯混合分布9.5 密度聚类9.6 层次聚类 9.1 聚类任务 9.2 性能度量 9.3 距离计算 9.4 原型聚类 ...
  • K-means聚类算法是典型的基于距离的非层次聚类算法,在最小化误差函数的基础上将数据划分为预定的K个类,使得K个类达到类内数据距离之和最小而类间距离之和最大。它是无监督学习算法,采用距离作为相似性的度量指标...
  • 聚类方法

    2021-04-26 14:16:12
    一、原型聚类 1.k-means聚类 2.学习向量量化(Learning Vector Quantization,LVQ) LVQ针对于带有类别标记的数据样本,学习过程利用样本的监督信息(类别标记)来辅助聚类。...三、层次聚类 参考https
  • 1、层次聚类 2、原型聚类-K-means 3、模型聚类-GMM 4、EM算法-LDA主题模型 5、密度聚类-DBSCAN 6、图聚类-谱聚类 三、模型聚类-高斯混合 高斯混合的类表示是一个高斯模型,相似性度量定义为服从...
  • 用人话理解Kmeans聚类

    2020-03-24 10:53:58
    1. 层次聚类 vs 非层次聚类 不同类之间有无包含关系 2. 硬聚类 vs 软聚类 硬聚类:每个对象只属于一个类 软聚类:每个对象以概率属于某个类。比如:样本1:A-0.8,B-0.1,C-0.1 3. 各样本之间的距离 ① 将...
  • 文章目录聚类方法方法图示经典聚类算法基于模型的算法基于划分的算法基于密度的算法基于网格的算法层次聚类算法 聚类方法 方法图示 经典聚类算法 基于模型的算法 在概率模型中,其核心思想是将数据描述成一...
  • 用电负荷相关聚类算法总结(1)

    千次阅读 2018-09-09 13:41:43
    聚类算法大致可以分为划分聚类方法、层次聚类方法、密度聚类方法、网格聚类方法、模型聚类方法等。近年来,量子聚类方法、谱聚类方法、粒度聚类方法、概率图聚类方法、同步聚类方法等也流行起来。 1.1 基于划分的...
  • 一、性能度量 二、原型聚类: 1. k-means:通过最小化均方差,将数据集分成k个“簇” 2.学习向量量化(LVQ):假设数据样本带有类别标记 3.高斯混合聚类:用概率...三、层次聚类 四、DBSCAN密度聚类:剔除异常数据
  • 聚类(二)

    2016-10-19 20:31:49
    本篇文章将续接上篇博文,描述:高斯混合聚类,密度聚类和层次聚类。1.高斯混合聚类高斯混合聚类是采用概率模型来表达聚类原型。这句话太抽象了,通俗来讲就是上篇博文里面提到的kk均值算法和学习向量量化算法。是...
  • 聚类模型-EM算法

    千次阅读 2018-09-15 19:25:22
    1、层次聚类 2、原型聚类-K-means 3、模型聚类-GMM 4、EM算法-LDA主题模型 5、密度聚类-DBSCAN 6、图聚类-谱聚类 四、EM算法 一、EM算法 ​ EM算法是一种迭代算法,用于带隐变量的概率模型...
  • 基于主题模型的聚类算法

    千次阅读 2018-01-22 15:31:53
    基于主题模型的聚类算法是假定数据的分布是符合一系列的概率分布,用概率分布模型去对数据进行聚类,而不是像层次聚类和划分聚类那样基于距离来进行聚类。因此,模型的好坏就直接决定了聚类效果的好坏。目前比较常用...
  • 三类常见的聚类模型,K-Means,层次聚类,最大期望EM算法,其他的还有密度聚类 如何评价聚类结果好坏,一些常用的指标又有哪些 聚类分析的目的:让类群内观测的距离最近,同时不同全体之间的距离最大 1.聚类分析的...
  • 机器学习之聚类常用方法

    千次阅读 2019-05-25 11:52:38
    medoids算法k-prototype算法基于层次聚类BIRCH算法CURE算法基于密度聚类DBSCAN算法[参考百度百科]DENCLUE算法基于网格的聚类(STING、CLIQUE )基于模型的聚类基于概率模型的聚类基于神经网络模型的聚类 ...
  • 接下来就要说下无监督机器学习方法,所谓无监督前面也说过,就是没有标签的情况,对样本...比如K均值聚类可以扩展一下形成层次聚类(Hierarchical Clustering);也可以进入概率分布的空间进行聚类,前段时间很火的LDA

空空如也

空空如也

1 2 3 4 5 6
收藏数 105
精华内容 42
关键字:

概率层次聚类