图的聚类算法

㈠ 聚类算法有哪些分类

聚类算法的分类有：

1、划分法

划分法(partitioning methods)，给定一个有N个元组或者纪录的数据集，分裂法将构造K个分组，每一个分组就代表一个聚类，K小于N。而且这K个分组满足下列条件：

（1） 每一个分组至少包含一个数据纪录；

（2）每一个数据纪录属于且仅属于一个分组（注意：这个要求在某些模糊聚类算法中可以放宽）；

2、层次法

层次法(hierarchical methods)，这种方法对给定的数据集进行层次似的分解，直到某种条件满足为止。具体又可分为“自底向上”和“自顶向下”两种方案。

例如，在“自底向上”方案中，初始时每一个数据纪录都组成一个单独的组，在接下来的迭代中，它把那些相互邻近的组合并成一个组，直到所有的记录组成一个分组或者某个条件满足为止。

3、密度算法

基于密度的方法(density-based methods)，基于密度的方法与其它方法的一个根本区别是：它不是基于各种各样的距离的，而是基于密度的。这样就能克服基于距离的算法只能发现“类圆形”的聚类的缺点。

4、图论聚类法

图论聚类方法解决的第一步是建立与问题相适应的图，图的节点对应于被分析数据的最小单元，图的边（或弧）对应于最小处理单元数据之间的相似性度量。因此，每一个最小处理单元数据之间都会有一个度量表达，这就确保了数据的局部特性比较易于处理。图论聚类法是以样本数据的局域连接特征作为聚类的主要信息源，因而其主要优点是易于处理局部数据的特性。

5、网格算法

基于网格的方法(grid-based methods)，这种方法首先将数据空间划分成为有限个单元（cell）的网格结构,所有的处理都是以单个的单元为对象的。这么处理的一个突出的优点就是处理速度很快，通常这是与目标数据库中记录的个数无关的，它只与把数据空间分为多少个单元有关。

代表算法有：STING算法、CLIQUE算法、WAVE-CLUSTER算法；

6、模型算法

基于模型的方法(model-based methods)，基于模型的方法给每一个聚类假定一个模型，然后去寻找能够很好的满足这个模型的数据集。这样一个模型可能是数据点在空间中的密度分布函数或者其它。它的一个潜在的假定就是：目标数据集是由一系列的概率分布所决定的。

通常有两种尝试方向：统计的方案和神经网络的方案。

(1)图的聚类算法扩展阅读：

聚类算法的要求：

1、可伸缩性

许多聚类算法在小于 200 个数据对象的小数据集合上工作得很好；但是，一个大规模数据库可能包含几百万个对象，在这样的大数据集合样本上进行聚类可能会导致有偏的结果。

我们需要具有高度可伸缩性的聚类算法。

2、不同属性

许多算法被设计用来聚类数值类型的数据。但是，应用可能要求聚类其他类型的数据，如二元类型(binary)，分类/标称类型（categorical/nominal），序数型（ordinal）数据，或者这些数据类型的混合。

3、任意形状

许多聚类算法基于欧几里得或者曼哈顿距离度量来决定聚类。基于这样的距离度量的算法趋向于发现具有相近尺度和密度的球状簇。但是，一个簇可能是任意形状的。提出能发现任意形状簇的算法是很重要的。

4、领域最小化

许多聚类算法在聚类分析中要求用户输入一定的参数，例如希望产生的簇的数目。聚类结果对于输入参数十分敏感。参数通常很难确定，特别是对于包含高维对象的数据集来说。这样不仅加重了用户的负担，也使得聚类的质量难以控制。

5、处理“噪声”

绝大多数现实中的数据库都包含了孤立点，缺失，或者错误的数据。一些聚类算法对于这样的数据敏感，可能导致低质量的聚类结果。

6、记录顺序

一些聚类算法对于输入数据的顺序是敏感的。例如，同一个数据集合，当以不同的顺序交给同一个算法时，可能生成差别很大的聚类结果。开发对数据输入顺序不敏感的算法具有重要的意义。

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

本文共计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算法等。 

㈢ 聚类算法有哪些

聚类算法有：划分法、层次法、密度算法、图论聚类法、网格算法、模型算法。

1、划分法

划分法(partitioning methods)，给定一个有N个元组或者纪录的数据集，分裂法将构造K个分组，每一个分组就代表一个聚类，K<N。使用这个基本思想的算法有：K-MEANS算法、K-MEDOIDS算法、CLARANS算法。

2、层次法

层次法(hierarchical methods)，这种方法对给定的数据集进行层次似的分解，直到某种条件满足为止。具体又可分为“自底向上”和“自顶向下”两种方案。代表算法有：BIRCH算法、CURE算法、CHAMELEON算法等。

3、密度算法

基于密度的方法(density-based methods)，基于密度的方法与其它方法的一个根本区别是：它不是基于各种各样的距离的，而是基于密度的。这样就能克服基于距离的算法只能发现“类圆形”的聚类的缺点。代表算法有：DBSCAN算法、OPTICS算法、DENCLUE算法等。

4、图论聚类法

图论聚类方法解决的第一步是建立与问题相适应的图，图的节点对应于被分析数据的最小单元，图的边（或弧）对应于最小处理单元数据之间的相似性度量。因此，每一个最小处理单元数据之间都会有一个度量表达，这就确保了数据的局部特性比较易于处理。图论聚类法是以样本数据的局域连接特征作为聚类的主要信息源，因而其主要优点是易于处理局部数据的特性。

5、网格算法

基于网格的方法(grid-based methods)，这种方法首先将数据空间划分成为有限个单元（cell）的网格结构,所有的处理都是以单个的单元为对象的。代表算法有：STING算法、CLIQUE算法、WAVE-CLUSTER算法。

6、模型算法

基于模型的方法(model-based methods)，基于模型的方法给每一个聚类假定一个模型，然后去寻找能够很好的满足这个模型的数据集。通常有两种尝试方向：统计的方案和神经网络的方案。

(3)图的聚类算法扩展阅读：

聚类分析起源于分类学，在古老的分类学中，人们主要依靠经验和专业知识来实现分类，很少利用数学工具进行定量的分类。随着人类科学技术的发展，对分类的要求越来越高，以致有时仅凭经验和专业知识难以确切地进行分类，于是人们逐渐地把数学工具引用到了分类学中，形成了数值分类学，之后又将多元分析的技术引入到数值分类学形成了聚类分析。聚类分析内容非常丰富，有系统聚类法、有序样品聚类法、动态聚类法、模糊聚类法、图论聚类法、聚类预报法等。

在商业上，聚类可以帮助市场分析人员从消费者数据库中区分出不同的消费群体来，并且概括出每一类消费者的消费模式或者说习惯。它作为数据挖掘中的一个模块，可以作为一个单独的工具以发现数据库中分布的一些深层的信息，并且概括出每一类的特点，或者把注意力放在某一个特定的类上以作进一步的分析；并且，聚类分析也可以作为数据挖掘算法中其他分析算法的一个预处理步骤。

㈣ 各类聚类算法的特点和优缺点

聚类算法是数据分析和机器学习中的重要工具，它们能够将相似的数据点分组在一起。在众多聚类算法中，K-means、均值漂移（MeanShift）、DBSCAN、高斯混合（Mixture-of-Gaussian）、层次聚类（Hierarchical clustering）以及图团体检测（Graph community Detection）是常见且具有代表性的方法。每种算法都有其独特的特点、优点与局限性。

在众多聚类算法中，K-means算法以其快速的计算速度和简单的实现方式而着称。然而，K-means算法依赖于随机种子点的选取，不同种子点可能导致截然不同的结果，这增加了算法的不确定性。

均值漂移（MeanShift）聚类是一种基于密度的算法，与K-means相比，它更少受到均值的影响，更加稳健。但选择合适的窗口半径r仍然是一个挑战。

DBSCAN算法是一种着名的密度聚类方法，通过设置距离r和minPoints参数来定义密度的聚集。然而，选择合适的这些参数是其实践中的关键挑战。

高斯混合（Mixture-of-Gaussian）聚类通过拟合数据为多个正态分布的混合模型，以实现聚类。它提供了强大的模型拟合能力，但缺乏直接的可视化结果和明确的聚类数量估计。

层次聚类算法通过构建聚类树（或称为层次聚类树）来显示数据之间的关系。合并中止条件是区分不同层次聚类算法的关键，而基于链接的聚类算法则从细小的聚类逐步合并，形成树状结构。然而，该算法的效率较低，且时间复杂度较高。

图团体检测（Graph community Detection）则关注于图数据的聚类，通过识别图中的紧密连接的子图来实现聚类。聚类间的距离度量不同，如单链接、完全链接、中心链接、平均链接和组平均等，每种度量都有其优缺点，如敏感性、紧凑性等。

总的来说，每种聚类算法都有其独特的优势和适用场景。选择合适的算法需要根据具体的数据特性和应用需求来决定，同时充分考虑算法的局限性以避免潜在的误判。

㈤ 多视图谱聚类算法介绍

假设给出了具有多个视图的数据 。

视图v的相似度矩阵：

视图v的拉普拉斯矩阵：

单视图聚类算法解决了归一化图拉普拉斯算子 如下的优化问题：

其中的tr代表求矩阵的迹。

矩阵 的行是数据点的嵌入，就是说一行对应一个数据，一共有n行，然后用k均值算法进行聚类。

作者的多视图谱聚类框架建立在标准谱聚类基础上，增加了半监督学习中的共正则化框架增加单一视图。

半监督学习中的共正则化基本上是通过使不同数据视图中的学习的假设在未标记数据上一致。

框架成功采用了两个主要假设：(a)每个视图中的真实目标函数应该就未标记数据的标签(兼容性)达成一致;(b)视图在类标签(条件独立性)下是独立的。

兼容性假设允许我们通过进搜索通过仅搜索兼容的函数来缩小可能的目标假设的空间。

作者提出了两种基于共正则化的方法，使得不同视图的聚类假设彼此一致。同时作者构建包含所有数据视图的拉普拉斯算子，同时在拉普拉斯算子的基础上进行了规范化，使得每个拉普拉斯算子得到的聚类结构在每个视图中一致。

第一个共正则化强制一个视图对 的特征向量应该具有高度的成对相似性(使用成对的正则化标准)。第二个共正则化方案是通过将他们规范化为共同的共识(基于中心的共正则化)来强制使视图特定的特征向量看起来相似。

在多视图的情况下，我们希望每个视图的特征向量矩阵是相似的。相当于在强制使所有视图中的谱聚类假设相同。

先讨论双视图情况。

提出以下损失函数作为两个视图之间聚类结果是否一致性的度量。

其中的 是 的相似矩阵。

进行除法的意义在于进行归一化使得两个视图具有可比较性。

然后作者选择了线性核作为相似性的度量方式。

从而得出：

选择线性核的原因：

因为 对上面的代价函数进行化简最终的到

然后我们在其中增加各个视图之间的谱聚类目标函数，得到以下的最大化问题：

然后我们可以通过不断的进行迭代去最大化上面的式子。

例如当给定 时，上式的优化目标就变成了：

这时候就化简成了普通的单视图的优化目标函数的形式。它的拉普拉斯矩阵为 。

上面的拉普拉斯矩阵是一种自适应(随着每次迭代，拉普拉斯算子会改变)的，结合内核和拉普拉斯算子的方法。

然后我们可以交替最大化使得算法得到最大值。但是同时要注意选择合适的初始化值从而避免陷入局部最大值。迭代开始时，可以选择最具有信息性的视图开始进行迭代。

对固定的 和 ，可以保证算法收敛。实践中通过观察连续迭代之间的目标值的差值来监视是否收敛，当低于某一阈值时，停止迭代。

我们扩展上一节中提出的共正则化谱聚类。对于m个视图，我们有：

在这里，对所有的共正则化部分使用了共同的 进行平衡。然后优化方法和双视图情况类似。

给定一个视图的 ，优化目标如下所示：

然后我们可以通过迭代对它进行不断优化。

这里提出的正则化方案是对上面的正则化方案的一种替代。将所有视图的特征向量 朝向共同的中心 (类似一组共同的特征向量)。这样可以减少正则化项的对数(m对)。

目标函数可以写为：

这个目标函数平衡各个谱聚类目标与每个视图特定特征向量 和共有特征向量 之间的折中。同时与第一种共正则化方法不同的是，我们可以对每一个正则化项设置一个参数来反映它的重要性。

这里的优化方法和上面的还是一样的，通过固定其他特征向量对单个特征向量进行优化。不同的地方在于需要对 进行优化，我们可以固定其他变量，然后对他进行优化。

只有对 进行优化时，和第一种共正则化方法不同，需要优化以下式子：

然后由矩阵的迹的性质tr(AB)=tr(BA)和tr(mA+nB)=mtr(A)+ntr(B)可以得到：

然后就又将这个问题转化成了单视图谱聚类的目标函数形式。对应的拉普拉斯矩阵为：

使用第二种基于中心的共正则化和第一种共正则化的另一个差别在于这种方法可以直接得到最终的特征向量集合 ，然后可以直接对他应用k均值等聚类算法进行聚类。而第一种共正则化方法需要对得出的所有特征向量集合进行拼接等处理步骤。

基于中心的共正则化方法一个缺点是容易受到有噪声的视图的影响，为了解决这个问题，需要仔细的选择每个视图对应的权重 。

参考论文：Co-regularized Spectral Clustering，Abhishek Kumar∗，Piyush Rai∗，Hal Daum ́e III.