java凝聚层次聚类算法

层次聚类

    层次聚类方法对给定的数据集进行层次的分解，直到满足某种条件为止，传统的层次聚类算法主要分为两大类算法：

1、凝聚的层次聚类： AGNES算法 (AGglomerative NESting)==采用自底向上的策略。最初将每个对象作为一个簇，然后这些簇根据某些准则被一步一步合并，两个簇间的距离可以由这两个不同簇中距离最近的数据点的相似度来确定；聚类的合并过程反复进行直到所有的对象满足簇数目。

2、分裂的层次聚类： DIANA算法 (DIvisive ANALysis)==采用自顶向下的策略。首先将所有对象置于一个簇中，然后按照某种既定的规则逐渐细分为越来越小的簇(比如最大的欧式距离)，直到达到某个终结条件(簇数目或者簇距离达到阈值)；

1、简单，理解容易。

2、合并点/分裂点选择不太容易。

3、合并/分类的操作不能进行撤销。

4、大数据集不太适合。

5、执行效率较低O(t*n2)，t为迭代次数，n为样本点数。

    两个聚簇中最近的两个样本之间的距离(single/word-linkage聚类法)。

    最终得到模型容易形成链式结构。

    两个聚簇中最远的两个样本的距离(complete-linkage聚类法)。

    如果存在异常值，那么构建可能不太稳定。

    两个聚簇中样本间两两距离的平均值(average-linkage聚类法)。

    两个聚簇中样本间两两距离的中值(median-linkage聚类法)。

     CF-Tree (Cluster Feature Tree)：每个节点是由三个聚类特征组成。这三个聚类特征构成一个三元组，用(N, LS, SS)来表示。

其中：

N 表示这个CF中包含的样本数量；

LS 表示这个CF中包含的样本点的向量和；

SS 表示这个CF中包含的样本点各个特征的平方和。

CF-Tree中父节点的某个CF值等于其指向的所有子节点CF值的总和。

CF-Tree 的几个关键超参数：

B： 每个内部节点最大的CF个数。

L： 每个叶节点最大的CF个数。

T： 新样本若被分到某一CF中，其到该CF中心的距离最大值。

CF-Tree构建步骤：

1、初始状态，CF树是空的，无任何样本。读入第一个样本x(a,b)，生成一个CF三元组，此处N=1，LS=(a,b)，SS=a2+b2，我们令其为CF1。

2、读入第二个样本，若到CF1的距离小于T，那么这个样本也归入CF1，更新三元组数据；如果大于T，则新划分出一个CF，这个样本作为CF2当中的首个样本，生成一个CF三元组。

注意：此时都是在节点内进行CF的建立，而非产生新的节点。

3、分裂：如果新数据进入该节点后，距离所有CF中心的距离都大于T，且Cf个数在生成新CF后大于B，则该节点需要进行划分。

4、找到该分支内各个CF之间的距离最大的两个CF，分别作为两个新叶子结点的CF，再计算剩余CF到这两个CF之间的距离，距离近的分到一个节点当中。

5、如果节点分裂过后叶子节点个数超过L，则该节点要进行分裂，分裂方式和上一步相同。

6、生成CF和分裂过程直至所有样本均进入CF树后停止。

     BIRCH算法 (平衡迭代削减聚类法)：聚类特征使用3元组进行一个簇的相关信息，通过构建满足分枝因子和簇直径限制的 聚类特征树(CF-Tree) 来求聚类，聚类特征树其实是一个具有两个参数 分枝因子(B、L) 和 类直径(T) 的高度平衡树；分枝因子规定了树的每个节点的子女的最多个数，而类直径体现了对这一类点的距离范围；非叶子节点为它子女的最大特征值；聚类特征树的构建可以是动态过程的，可以随时根据数据对模型进行更新操作。对应生成的结果就是一个 簇(聚类特征 – CF) ；BIRCH算法的过程就是建立CF-Tree的过程。

优缺点：

1、适合大规模数据集，线性效率；

  层次聚类算法 的复杂度为 OT(n2) ；

  优化后的 BIRCH算法 构建聚类特征树(CF-Tree)的时间复杂度为 O(n) ；

2、只适合分布呈凸形或者球形的数据集、需要给定聚类个数和簇之间的相关参数；

CURE算法 (使用代表点的聚类法)：是一种 凝聚算法(AGNES) 。该算法先把每个数据点看成一类，然后合并距离最近的类直至类个数为所要求的个数为止。但是和AGNES算法的区别是： 取消了使用所有点或用中心点+距离来表示一个类 ，而是 从每个类中抽取固定数量、分布较好的点作为此类的代表点 ，并将这些 代表点(一般10个) 乘以一个适当的 收缩因子(一般设置0.2~0.7之间) ，使它们更加靠近类中心点。代表点的收缩特性可以调整模型可以匹配那些非球形的场景，而且收缩因子的使用可以减少噪音对聚类的影响。

代表点 不是原来的点，而是那些需要重新计算的点。

层次聚类的两类方法分别是什么

层次聚类的两类方法分别是聚合及分裂。

层次聚类的定义：

层次聚类假设类别之间存在层次结构，层次聚类的目标是将样本分类聚集到不同层次的类别中。

层次聚类主要有两种方法：

1.聚合（自下而上）：聚合分类需要预先确定以下三要素：距离或相似度、合并规则、停止条件

2.分裂（自上而下）：分裂分类需要预先确定以下三要素：距离或相似度、分裂规则、停止条件

聚合分类算法：

输入：n个样本组成的样本集合、聚合分类三要素

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

计算样本集合中两两样本间的距离，形成距离矩阵 D=[dij]n×n

构造n个类，每个类只包含一个样本；

依据合并规则，判断样本类别间距离或相似度是否满足合并条件，如果满足则构建一个新类，并将相关的两个样本分配到这个新类中，否则判断当前最新的类别数是否为1（聚合），如果是1，就终止计算；

计算这个新类与其他各类之间的距离或相似度，返回步骤3。

分裂分类算法：

输入：n个样本组成的样本集合，分裂分类三要素

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

计算样本集合中两两样本间的距离，形成距离矩阵 D=[dij]n×n

将整个样本集合作为一个类别；

依据分裂规则和样本间距离，将满足分类规则的样本分配到两个新的类别中；

对每个新的类别执行步骤3，直到每个新的类别满足停止条件，则停止分裂操作，得到一个层次化的聚类类别。

数据挖掘干货总结（四）–聚类算法

本文共计2680字，预计阅读时长七分钟

聚类算法

一 、 本质

将数据划分到不同的类里，使相似的数据在同一类里，不相似的数据在不同类里

二 、 分类算法用来解决什么问题

文本聚类、图像聚类和商品聚类，便于发现规律，以解决数据稀疏问题

三 、 聚类算法基础知识

1. 层次聚类 vs 非层次聚类

– 不同类之间有无包含关系

2. 硬聚类 vs 软聚类

– 硬聚类：每个对象只属于一个类

– 软聚类：每个对象以某个概率属于每个类

3. 用向量表示对象

– 每个对象用一个向量表示，可以视为高维空间的一个点

– 所有对象形成数据空间（矩阵）

– 相似度计算：Cosine、点积、质心距离

4. 用矩阵列出对象之间的距离、相似度

5. 用字典保存上述矩阵（节省空间）

    D={(1,1):0,(1,2):2,(1,3):6…(5,5):0}

6. 评价方法

– 内部评价法（Internal Evalution）：

• 没有外部标准，非监督式

• 同类是否相似，跨类是否相异

DB值越小聚类效果越好，反之，越不好

– 外部评价法（External Evalution）：

• 准确度（accuracy）: (C11+C22) / (C11 + C12 + C21 + C22)

• 精度（Precision）: C11 / (C11 + C21 )

• 召回（Recall）: C11 / (C11 + C12 )

• F值（F-measure）：

β表示对精度P的重视程度，越大越重视，默认设置为1，即变成了F值，F较高时则能说明聚类效果较好。

四 、 有哪些聚类算法

主要分为 层次化聚类算法 ， 划分式聚类算法 ， 基于密度的聚类算法 ， 基于网格的聚类算法 ， 基于模型的聚类算法等 。

4.1 层次化聚类算法

又称树聚类算法，透过一种层次架构方式，反复将数据进行分裂或聚合。典型的有BIRCH算法，CURE算法，CHAMELEON算法，Sequence data rough clustering算法,Between groups average算法,Furthest neighbor算法,Neares neighbor算法等。

凝聚型层次聚类 ：

先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到所有对象都在一个簇中，或者某个终结条件被满足。

算法流程：

1. 将每个对象看作一类，计算两两之间的最小距离；

2. 将距离最小的两个类合并成一个新类；

3. 重新计算新类与所有类之间的距离；

4. 重复2、3，直到所有类最后合并成一类。

特点：

1. 算法简单

2. 层次用于概念聚类（生成概念、文档层次树）

3. 聚类对象的两种表示法都适用

4. 处理大小不同的簇

5. 簇选取步骤在树状图生成之后

4.2 划分式聚类算法

预先指定聚类数目或聚类中心，反复迭代逐步降低目标函数误差值直至收敛，得到最终结果。K-means,K-modes-Huang,K-means-CP,MDS_CLUSTER, Feature weighted fuzzy clustering，CLARANS等

经典K-means：

算法流程：

1. 随机地选择k个对象，每个对象初始地代表了一个簇的中心；

2. 对剩余的每个对象，根据其与各簇中心的距离，将它赋给最近的簇；

3. 重新计算每个簇的平均值，更新为新的簇中心；

4. 不断重复2、3，直到准则函数收敛。

特点：

1.K的选择

2.中心点的选择

– 随机

– 多轮随机：选择最小的WCSS

3.优点

– 算法简单、有效

– 时间复杂度：O(nkt)

4.缺点

– 不适于处理球面数据

– 密度、大小不同的聚类，受K的限制，难于发现自然的聚类

4.3 基于模型的聚类算法

为每簇假定了一个模型，寻找数据对给定模型的最佳拟合，同一”类“的数据属于同一种概率分布，即假设数据是根据潜在的概率分布生成的。主要有基于统计学模型的方法和基于神经网络模型的方法，尤其以基于概率模型的方法居多。一个基于模型的算法可能通过构建反应数据点空间分布的密度函数来定位聚类。基于模型的聚类试图优化给定的数据和某些数据模型之间的适应性。

SOM 神经网络算法 ：

该算法假设在输入对象中存在一些拓扑结构或顺序，可以实现从输入空间(n维)到输出平面(2维)的降维映射，其映射具有拓扑特征保持性质,与实际的大脑处理有很强的理论联系。

SOM网络包含输入层和输出层。输入层对应一个高维的输入向量，输出层由一系列组织在2维网格上的有序节点构成，输入节点与输出节点通过权重向量连接。学习过程中，找到与之距离最短的输出层单元，即获胜单元，对其更新。同时，将邻近区域的权值更新，使输出节点保持输入向量的拓扑特征。

算法流程：

1. 网络初始化，对输出层每个节点权重赋初值；

2. 将输入样本中随机选取输入向量，找到与输入向量距离最小的权重向量；

3. 定义获胜单元，在获胜单元的邻近区域调整权重使其向输入向量靠拢；

4. 提供新样本、进行训练；

5. 收缩邻域半径、减小学习率、重复，直到小于允许值，输出聚类结果。

4.4 基于密度聚类算法

只要邻近区域的密度（对象或数据点的数目）超过某个阈值，就继续聚类，擅于解决不规则形状的聚类问题，广泛应用于空间信息处理,SGC,GCHL，DBSCAN算法、OPTICS算法、DENCLUE算法。

DBSCAN：

对于集中区域效果较好，为了发现任意形状的簇，这类方法将簇看做是数据空间中被低密度区域分割开的稠密对象区域；一种基于高密度连通区域的基于密度的聚类方法，该算法将具有足够高密度的区域划分为簇，并在具有噪声的空间数据中发现任意形状的簇。

4.5 基于网格的聚类算法

    基于网格的方法把对象空间量化为有限数目的单元，形成一个网格结构。所有的聚类操作都在这个网格结构（即量化空间）上进行。这种方法的主要优点是它的处理 速度很快，其处理速度独立于数据对象的数目，只与量化空间中每一维的单元数目有关。但这种算法效率的提高是以聚类结果的精确性为代价的。经常与基于密度的算法结合使用。代表算法有STING算法、CLIQUE算法、WAVE-CLUSTER算法等。 

聚类算法 – 凝聚层次聚类

层次聚类 就是通过对数据集按照某种方法进行层次分解，直到满足某种条件为止。按照分类原理的不同，可以分为凝聚和分裂两种方法。

层次聚类方法对给定的数据集进行层次的分解，直到某种条件满足为止。具体又可分为 凝聚 和 分裂 的两种方案：

凝聚的层次聚类是一种自底向上的策略，首先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到所有的对象都在一个簇中，或者某个终结条件被满足，绝大多数层次聚类方法属于这一类，它们只是在簇间相似度的定义上有所不同。.

分裂的层次聚类与凝聚的层次聚类相反，采用自顶向下的策略，它首先将所有对象置于同一个簇中，然后逐渐细分为越来越小的簇，直到每个对象自成一簇，或者达到了某个终止条件。

本篇主要讨论凝聚的层次聚类。

第一步 ，将训练样本集中的每个数据点都当做一个聚类

第二步 ，计算每两个聚类之间的距离，将距离最近的或最相似的两个聚类进行合并，如同下图中的p1和p2、p5和p6

第三步 ，重复上述步骤，依旧计算每个聚类的距离，当然这次因为已经有聚合起来的簇了因此距离的计算方式有多种： 【单链】簇内的最近的点的距离、【全链】簇内的最远的点的距离、【组平均】簇的平均距离、簇的相似度等

第四步 ，直到得到的当前聚类数是合并前聚类数的10%，即90%的聚类都被合并了；当然还可以设置其他终止条件，这样设置是为了防止过度合并，此时需要几个簇，那么就可以用一条横线去截取分出的簇，如下图分出3类、4类、5类的横线截止

ps：距离在通常的情况下可以计算欧几里得距离，就是普通的直线距离，还可以计算余弦相似度

具体的动画效果可以参考视频，这是—- 传送门

1）距离和规则的相似度容易定义，限制少

2）不像kmeans，不需要预先制定聚类数

3）可以发现类的层次关系

1）计算复杂度太高

2）奇异值也能产生很大影响

3）由于根据距离来聚合数据，算法很可能聚类成链状