谱聚类算法 算法简介
谱聚类算法算法简介
谱聚类算法建立在谱图理论基础上，与传统的聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解的优点。 该算法首先根据给定的样本数据集定义一个描述成对数据点相似度的亲合矩阵,并且计算矩阵的特征值和特征向量，然后选择合适的特征向量聚类不同的数据点。谱聚类算法最初用于计算机视觉、VLS I 设计等领域，最近才开始用于机器学习中，并迅速成为国际上机器学习领域的研究热点。 谱聚类算法建立在图论中的谱图理论基础上，其本质是将聚类问题转化为图的最优划分问题，是一种点对聚类算法，对数据聚类具有很好的应用前景。
算法步骤
谱聚类算法将数据集中的每个对象看作是图的顶点V，将顶点间的相似度量化作为相应顶点连接边E的权值，这样就得到一个基于相似度的无向加权图G(V, E)，于是聚类问题就可以转化为图的划分问题。基于图论的最优划分准则就是使划分成的子图内部相似度最大，子图之间的相似度最小。 虽然根据不同的准则函数及谱映射方法，谱聚类算法有着不同的具体实现方法，但是这些实现方法都可以归纳为下面三个主要步骤： 1) 构建表示对象集的相似度矩阵W； 2) 通过计算相似度矩阵或拉普拉斯矩阵的前k个特征值与特征向量，构建特征向量空间； 3) 利用K-means或其它经典聚类算法对特征向量空间中的特征向量进行聚类。 上面的步骤只是谱聚类算法的一个总体框架，由于划分准则、相似度矩阵计算方法等因素的差别，具体的算法实现同样会有所差别，但其本质依然是图划分问题的连续放松形式。
划分准则
谱聚类算法将聚类问题就可以转化为图的划分问题之后，基于图论的划分准则的优劣直接影响到聚类结果的好坏。常见的划分准则有Mini cut，Average cut，Normalized cut，Min-max cut，Ratio cut，MNcut等。最小割集准则
在对图像分割中产生了较好的效果，但是该准则容易产生分割出只包含几个顶点的较小子图的歪斜分割现象。
规范割集准则
在2000年Shi和Malik根据谱图理论建立了2-way划分的规范割目标函数，此方法通过计算分割之后的连接边损失值在各个子图与所有顶点之间的连接边权重总值中所占比例之和来衡量划分的优劣。
比例割集准则
对于超大规模集成电路设计中的电路层次设计和分支划分问题，最
大流最小割算法能够发现其中的类结构（clustering structure），但是在实际中该算法通常会产生规模非常不一致的电路分支；Kemighan-Lin算法采用固定参数的方式可以得到规模具有一定可比性的分支划分，由于电路中的分支倾向于自然结合的形成，所以通过预先设定分支规模进行划分的方法存在明显的局限。针对以上的现象Wei和Cheng提出了比例割集准则。
平均割集准则
在计算机视觉中，图像原始像素条理有序地分组可以通过寻找场景结构图(Scene Structure Graph)中松散耦合的结点来完成，于是原始像素的聚合问题就转化为场景结构图的分割。Sarkar和Soundararajan[62]提出了一种最小化两两分割之间相似度的计算方法并把它命名为平均割集准则。
最小最大割集准则
Mini cut准则容易出现分割出只包含几个顶点的较小子图的歪斜分割现象，Ratio cut和Normalized cut等在一定程度上可以避免这种现象，但是当类间重叠严重时歪斜分割现象仍旧会发生。Chris Ding等人提出的基于Min-max cut的图划分方法充分体现了“子图内部相似度最大，子图之间的相似度最小”原则，能够产生比较平衡划分。 上述五种划分都是不断地将图划分为2个子图的反复迭代运算过程，当划分函数的最小值满足一定的条件时迭代过程便会终止，相应的函数可以称为2-way 划分函数。
多路规范割集准则
Meil?和Xu[64]认为可以同时把图划分为k个子图并于2004年提出了一种k-way规范割目标函数，而且对于参数k的选取问题也作了分析说明。 我们可以发现当k=2时，MNcut与Ncut两者是等价的。
典型的算法
根据谱聚类算法所使用的划分准则，可以把算法分为二路谱聚类算法和多路谱聚类算法，前者使用2-way划分准则而后者使用k-way划分准则。
二路谱聚类算法
PF算法。Perona和Freeman提出用相似度矩阵W最大特征值所对应的特征向量进行聚类指出对于块对角相似矩阵，特征向量中非零值对应的点属于同一类，零值对应的点属于另外一类。 SM算法。Meli?指出Ncut和MNcut的差异之处仅在于所使用的谱映射不同。多路规范割集准则在实际应用中合理有效，但其优化问题通常难以解决。Shi和Malik 认为第二小特征值对应的特征向量，即Fiedler向量包含了图的划分信
息，根据启发式规则在此向量中寻找划分点i使在该点上得到的Ncut(A,B)值最小，最后把向量中的值与Ncut准则函数的最小值进行比较，大于等于该值的点划分为一类，小于该值的点则划分到另外一类。 SLH算法。SLH重定位算法计算相似度矩阵W的前k个特征向量，参数k需要事先指定。 KVV算法。根据启发式规则在Fiedler向量中寻找划分点i使在该点上得到的Rcut(A,B)值最小的划分点，与SM算法相似；不同之处仅在于SM算法是寻找使Ncut(A,B)值最小的划分点。虽然在实际问题中KVV 算法存在运行速度相对较慢的缺陷，但是算法减少了过分割的可能
性。 Mcut算法。Ding根据谱图理论将最小最大割集准则函数的最优化问题转化为下式的第二小特征值的求解。
多路谱聚类算法
NJW算法。Ng，Jordan等人选取拉普拉斯矩阵的前k个最大特征值对应的特征向量构造新的向量空间R，在这个新的空间内建起与原始数据的对应关系，然后进行聚类。 田铮和李小斌等人利用矩阵的扰动理论逐步分析了理想情形、分块情形和一般情形下权矩阵的谱和特征向量与聚类之间的关系[69]：顶点集合V的类内离散程度充分小而类间离散程度充分大时，V 中所有顶点可以划分成的数目与相似度矩阵W特征值中大于1的特征值的数目相等。同时特征值的大小可以在一定程度上反映每一类所包含顶点的个数。相似度矩阵W的前k个单位正交特征向量组成的矩阵X 的行向量之间的夹角可以用来计算两个顶点是否属于同一类，如果属于同一类，那么这对应的行向量接近于相互平行；反之对应的行向量接近于相互正交。理想情况中，V中两个顶点属于同一类时，相应的行向量相互平行；属于不同的类，相应的行向量相互正交。 MS算法[70]。Meil?把基于马尔可夫链随机游动过程的概率转移矩阵运用到相似度矩阵的构造中，研究了这种随机游动的概率转移矩阵的特征值和特征向量，在随机游动的框架下了对Ncut进行了概率解释。该算法是用随机游动矩阵P的前k个非零特征值对应的特征向量构造矩阵，然后将矩阵中的行看成R空间中的点进行聚类，步骤与NJW算法相似。MS算法在实际的图像分割中取得了良好的效果，但是度矩阵D中对角线元素值之间存在较大的差别时就会导致较差的聚类效果。
算法的新进展
Zha和Dhillon等人研究了基于二分图G=
法。同时，在这个解释框架下提出了多个特征相似矩阵组合下的谱聚类方法，在图像分割中取得了很不错的效果。 Cu等人分析了核k-means的方法，发现最小化核k-means的目标函数等同于一个由数据向量组成的Gram矩阵的迹最大化问题。同时，迹最大化问题的松散解可以通过Gram矩阵的部分特征分解获得，首次用谱松散的方法获得核k-means的目标函数的全局最优解。Dhillon[29]在此基础上，又研究了加权核k-means的目标函数，将其与Ncut目标函数建立联系，提出了一个可以单调递减Ncut值的新颖的加权核k-means算法。 Ncut是一个很好的聚类目标函数。它的求解是一个NP难问题。传统的方法是宽松的谱松散方法。Xing与Jordan[分析了对Ncut的半正定规划(SDP)模型。根据该模型，对Ncut提出了一个比谱松散更紧的下限。同时指出了Ncut本身不能得到最优的聚类，但它可以通过不同的松散方法获得合理的聚类。 谱聚类方法不仅用于无监督学习中，也用于有约束的半监督学习中。Kamvar等人将PageRank[32]的随机游动模型运用到相似度矩阵中，根据已知样本的类别修正相似度矩阵。然后根据谱聚类算法获得聚类结果。Bach与Jordan则是根据一个基于已知划分与Ncut谱松散结果的误差，提出了新的目标函数，通过最小化新的目标函数推出新的谱聚类算
法。 王玲，薄列峰，焦李成认为在聚类搜索过程中充分利用先验信息会显著提高聚类算法的性能，并分析了在聚类过程中仅利用成对限制信息存在的不足，提出利用数据集本身固有空间一致性先验信息的具体方法。在经典的谱聚类算法中同时引入两类先验信息的基础上提出一种密度敏感的半监督谱聚类算法，两类先验信息在指导聚类搜索的过程中能够起到相辅相成的作用，使得算法相对于仅利用成对限制信息的聚类算法在聚类性能上有了显著的提高。 王娜，李霞提出了一种基于监督信息特性的主动学习策略，找出同一类中距离相对较远的数据对象对和不同类中距离相对较近的数据对象对组成监督信息并将其引入谱聚类算法，构建新颖的主动半监督谱聚类算法，结果优于采用随机选取监督信息的谱聚类性能。
面临的问题
尽管谱聚类具有坚实的理论基础，相对于其它聚类方法具有许多优势，在实践中的应用领域在不断扩展，取得了不错的效果[38]，但是它仍然需要改进，尤其在下述几个方面：
如何构造相似度矩阵
如何创建相似度矩阵W，使其更加真实地反映数据点之间的近似关系，使得相近点之间的相似度更高，相异点之间的相似度更低，是谱聚类算法必须要解决的一个问题。高斯相似函数是经典谱聚类算法中计算
两点间相似度的常用方法，虽然该函数使原始的谱聚类算法取得了一些成功，但尺度参数σ的选取问题使该函数具有明显的局限性。NJW算法[7]通过预先指定几个尺度参数σ的值，分别执行谱聚类，最后选取使聚类结果最好的σ作为参数，这种做法消除了尺度参数σ选取的人为因素，却增加了运算时间。 近年来，为了避免参数的选择问题，有学者提出在计算相似度时不使用高斯核函数。如Gong 等人[41]借鉴Wang Fei和Zhang Changshui[42]在半监督中使用的方法，将每个点的k 近邻对该点进行线性近似表示时所占的权重作为两点间的相似度。通过求n 个二次规划问题，就可以求得相似度矩阵W，降低了谱聚类算法对参数的敏感性，使算法更稳定。
如何自动确定聚类数目
由相似度矩阵得到拉普拉斯矩阵后，接下来要确定所需特征向量的数目，它与最终的聚类数目相等。虽然该数目可以由人工确定，但是准确地给出对聚类效率和最终的聚类质量有直接影响的数目值是个非常困难的问题。因此，如何自动确定聚类数目成为谱聚类需要解决的关键问题之一。
如何选择特征向量
大多情况下的谱聚类算法直接选择前k 个最大特征值对应的特征向量用于新向量空间的构造。2008 年Xiang等人[44]提出了“向量相关度”的概念，在使用该定义对向量的相关度进行衡量的基础上选出相关度最高的k 个特征向量用于新向量空间的构造。实验结果表明运用此方法选取拥有较高相关度和较多信息量的特征向量可以得到更加令人满意的聚类效果。
如何解决模糊聚类的问题
尽管在文档聚类中，谱聚类取得了很好的效果。但是在文档聚类中，单个词可能属于多个类，单个文档可能是多主题的文档。这就需要我们用模糊聚类的方法解决。如何确定基于模糊聚类与谱方法的联合：如何建立模糊标准的图划分的目标函数等都是谱聚类算法在模糊聚类中所面临的问题。如何运用到大规模学习问题中：由于谱聚类算法需要求解特征值和特征向量，所以计算复杂度相对较大，针对目前强烈的大规模数据处理要求研究高效、可扩展、适宜大规模学习问题的谱聚类算法。
如何提高谱聚类的运行速度
在谱聚类算法的聚类过程中需要求解矩阵的特征值与特征向量，求解非稀疏矩阵特征向量的复杂度O(n)，所以处理大规模数据集的时候，计算中形成的矩阵空间非常大，求解过程不但会非常耗时，而且所需要
的内存空间也非常大，面临着内存溢出的危险，对计算机内存容量的要求变得较高。因此，如何提高算法的运行速度，降低运行所需的内存空间，减少算法运行的时间和空间代价是谱聚类算法在不断扩展应用领域的过程中所面临的另一关键问题。
近似谱聚类算法描述
二、近似谱聚类算法描述 本节论文阐述基于相似矩阵稀疏化方法稀疏化后离群点的优化处理，并将该处理步骤应用于谱聚类算法中。基于上述分析近似谱聚类算法整体流程总结描述如表3.2所示。 表3.2 近似谱聚类算法（ASCA） 算法：近似谱聚类算法（ASCA） 输入：数据点，待聚类数目 输出：聚类 1. 使用公式，（其中，是的个最近邻按距离排序后第个邻居，同理，），构建相似矩阵； 2. 使用稀疏化矩阵获得半正定矩阵，找出矩阵对称位置不一致的相似度，并将对称元素设置为0，调整为对称半正定矩阵； 3. 使用优化公式对矩阵进行离群点调优； 4. 计算对称半正定拉普拉斯矩阵； 5. 计算的特征向量分解，找出第k个最小非零特征特征量，并按列排列k个特征向量构建特征向量矩阵； 6. 计算标准化矩阵（）； 7. 使用粗糙集模型选择k-means初始化聚类中心位置并对矩阵进行k-means聚类，把其聚类成k组（）。 基于近似谱聚类算法整体步骤描述，为进行近似谱聚类算法Matlab辅助实验铺垫，绘制近似谱聚类算法流程示意图如图3.1所示。Matlab辅助实验主要是将示意图3.1中的所示的算法与正交化Nystr?m低阶子矩阵抽样近似相似矩阵谱聚类算法（ONSP: Orthogonalization Nystr?m Spectral Clustering）和最近邻稀疏化近似相似矩阵谱聚类算法（tNNSC: Spectral Clustering）进行对比，并验证其聚类效果。 图3.1 近似谱聚类算法流程示意图 三、近似谱聚类算法时间复杂度分析 现对基于相似矩阵稀疏化方法离群点优化的近似谱聚类算法时间复杂度简单分析，步骤1：使用高斯函数公式构建相似矩阵的时间复杂度是，其中表示数据点数目、表示数据维数，计算数据点和之间的相似度的时间复杂度是，则计算整个数据集的时间复杂度是；步骤2：使用稀疏化矩阵获得半正定矩阵并调整为对称半正定矩阵借助于最大堆，其时间复杂度是，其中是最近邻数；步骤3：优化离群点步骤是非确定性多项式困难问题NP-hard （Non deterministic Ploynomial Hard）问题，其时间复杂度随近似相似度矩阵维数按指数增长；步骤4与步骤5：计算对称半正定拉普拉斯矩阵并找出k个最小非零特征值的特征向量的时间复杂度在论文第二章第二节中已经详细分析过，即；步骤6：计算标准化矩阵的时间复杂度是；步骤7：执行k-means聚类时间复杂度是：，其中表示k-means聚类过程迭代的次数，指待聚类数目。 第三节近似谱聚类算法实验分析 一、近似谱聚类算法辅助实验 （1）Matlab辅助实验环境描述 为验证表3.2所示近似谱聚类算法与正交化Nystr?m低阶子矩阵抽样近似相似矩阵谱聚类算法和最近邻稀疏化近似相似矩阵谱聚类算法的性能，鉴于Hadoop MapReduce并行实验对
K - M e a n s 聚 类 算 法
基于K-means聚类算法的入侵检测系统的设计 基于K-means聚类算法的入侵检测系统的设计 今天给大家讲述的是K-means聚类算法在入侵检测系统中的应用首先，介绍一下 聚类算法 将认识对象进行分类是人类认识世界的一种重要方法，比如有关世界的时间进程的研究，就形成了历史学，有关世界空间地域的研究，则形成了地理学。 又如在生物学中，为了研究生物的演变，需要对生物进行分类，生物学家根据各种生物的特征，将它们归属于不同的界、门、纲、目、科、属、种之中。 事实上，分门别类地对事物进行研究，要远比在一个混杂多变的集合中更清晰、明了和细致，这是因为同一类事物会具有更多的近似特性。 通常，人们可以凭经验和专业知识来实现分类。而聚类分析（cluster analysis）作为一种定量方法，将从数据分析的角度，给出一个更准确、细致的分类工具。 （聚类分析我们说得朴实一点叫做多元统计分析，说得时髦一点叫做数据挖掘算法，因为这个算法可以在一堆数据中获取很有用的信息，这就不就是数据挖掘吗，所以大家平时也不要被那些高大上的名词给吓到了，它背后的核心原理大多数我们都是可以略懂一二的，再
比如说现在AI这么火，如果大家还有印象的话，以前我们在大二上学习概率论的时候，我也和大家分享过自然语言处理的数学原理，就是如何让机器人理解我们人类的自然语言，比如说，苹果手机上的Siri系统，当时还让杨帆同学帮我在黑板上写了三句话，其实就是贝叶斯公式+隐含马尔可夫链。估计大家不记得了，扯得有点远了接下来还是回归我们的正题，今天要讨论的聚类算法。） K-Means是常用的聚类算法，与其他聚类算法相比，其时间复杂度低，结果稳定，聚类的效果也还不错, 相异度计算 在正式讨论聚类前，我们要先弄清楚一个问题：如何定量计算两个可比较元素间的相异度。用通俗的话说，相异度就是两个东西差别有多大，例如人类与章鱼的相异度明显大于人类与黑猩猩的相异度，这是能我们直观感受到的。但是，计算机没有这种直观感受能力，我们必须对相异度在数学上进行定量定义。 要用数量化的方法对事物进行分类，就必须用数量化的方法描述事物之间的相似程度。一个事物常常需要用多个特征变量来刻画，就比如说我们举一个例证，就有一项比较神奇的技术叫面部识别技术，其实听起来很高大上，它是如何做到的，提取一个人的面部特征，比如说嘴巴的长度，鼻梁的高度，眼睛中心到鼻子的距离，鼻子到嘴巴的距离，这些指标对应得数值可以组成一个向量作为每一个个体的一个标度变量（）,或者说叫做每一个人的一个特征向量。 如果对于一群有待分类的样本点需用p 个特征变量值描述，则每
FCM聚类算法介绍
FCM 聚类算法介绍 FCM 算法是一种基于划分的聚类算法，它的思想就是使得被划分到同一簇的对象之间相似度最大，而不同簇之间的相似度最小。模糊C 均值算法是普通C 均值算法的改进，普通C 均值算法对于数据的划分是硬性的，而FCM 则是一种柔性的模糊划分。在介绍FCM 具体算法之前我们先介绍一些模糊集合的基本知识。 6.1.1 模糊集基本知识[21] 首先说明隶属度函数的概念。隶属度函数是表示一个对象x 隶属于集合A 的程度的函数，通常记做μA (x)，其自变量范围是所有可能属于集合A 的对象（即集合A 所在空间中的所有点），取值范围是[0,1]，即0<= μA (x)<=1。μA (x)=1表示x 完全隶属于集合A ，相当于传统集合概念上的x ∈A 。一个定义在空间X={x}上的隶属度函数就定义了一个模糊集合A ，或者叫定义在论域X={x}上的模糊子集~ A 。对于有限个对象x 1，x 2，……，x n 模糊集合~ A 可以表示为： }|)),({(~ X x x x A i i i A ∈=μ (6.1) 有了模糊集合的概念，一个元素隶属于模糊集合就不是硬性的了，在聚类的问题中，可以把聚类生成的簇看成模糊集合，因此，每个样本点隶属于簇的隶属度就是[0，1]区间里面的值。 6.1.2 K 均值聚类算法(HCM)介绍 K 均值聚类，即众所周知的C 均值聚类，已经应用到各种领域。它的核心思想如下：算法把n 个向量x j (1,2…,n)分为c 个组G i (i=1,2,…,c)，并求每组的聚类中心，使得非相似性（或距离）指标的价值函数（或目标函数）达到最小。当选择欧几里德距离为组j 中向量x k 与相应聚类中心c i 间的非相似性指标时，价值函数可定义为： ∑∑∑=∈=-== c i Gi x k i k c i k c x Ji J 1 ,2 1 )||||( (6.2) 这里∑∑=∈-=c i Gi x k i k k c x Ji 1 ,2 )||||(是组i 内的价值函数。这样J i 的值依赖于G i 的几何特性和c i 的位置。 一般来说，可用一个通用距离函数d(x k ,c i )代替组I 中的向量x k ，则相应的总价值函数可表示为： ∑∑∑==∈-== c i c i Gi x k i k k c x Ji J 1 1 ,))d(( (6.3) 为简单起见，这里用欧几里德距离作为向量的非相似性指标，且总的价值函数表示为（6.2）式。 划分过的组一般用一个c ×n 的二维隶属矩阵U 来定义。如果第j 个数据点x j 属于组i ，则U 中的元素u ij 为1；否则，该元素取0。一旦确定聚类中心ci ，可导出如下使式（6.2）最小u ij ：
(完整版)聚类算法总结
1.聚类定义 “聚类是把相似的对象通过静态分类的方法分成不同的组别或者更多的子集（subset）,这样让在同一个子集中的成员对象都有一些相似的属性”——wikipedia “聚类分析指将物理或抽象对象的集合分组成为由类似的对象组成的多个类的分析过程。它是一种重要的人类行为。聚类是将数据分类到不同的类或者簇这样的一个过程，所以同一个簇中的对象有很大的相似性，而不同簇间的对象有很大的相异性。”——百度百科 说白了，聚类（clustering）是完全可以按字面意思来理解的——将相同、相似、相近、相关的对象实例聚成一类的过程。简单理解，如果一个数据集合包含N个实例，根据某种准则可以将这N 个实例划分为m个类别，每个类别中的实例都是相关的，而不同类别之间是区别的也就是不相关的，这个过程就叫聚类了。 2.聚类过程: 1) 数据准备:包括特征标准化和降维. 2) 特征选择:从最初的特征中选择最有效的特征,并将其存储于向量中. 3) 特征提取:通过对所选择的特征进行转换形成新的突出特征.
4) 聚类(或分组):首先选择合适特征类型的某种距离函数(或构造新的距离函数)进行接近程度的度量;而后执行聚类或分组. 5) 聚类结果评估:是指对聚类结果进行评估.评估主要有3 种:外部有效性评估、内部有效性评估和相关性测试评估. 3聚类算法的类别 没有任何一种聚类技术(聚类算法)可以普遍适用于揭示各种多维数据集所呈现出来的多种多样的结构，根据数据在聚类中的积聚规则以及应用这些规则的方法,有多种聚类算法.聚类算法有多种分类方法将聚类算法大致分成层次化聚类算法、划分式聚类算法、基于密度和网格的聚类算法和其他聚类算法,如图1 所示 的4 个类别.
(完整word版)各种聚类算法介绍及对比
一、层次聚类 1、层次聚类的原理及分类 1）层次法（Hierarchical methods）先计算样本之间的距离。每次将距离最近的点合并到同一个类。然后，再计算类与类之间的距离，将距离最近的类合并为一个大类。不停的合并，直到合成了一个类。其中类与类的距离的计算方法有：最短距离法，最长距离法，中间距离法，类平均法等。比如最短距离法，将类与类的距离定义为类与类之间样本的最短距离。 层次聚类算法根据层次分解的顺序分为：自下底向上和自上向下，即凝聚的层次聚类算法和分裂的层次聚类算法（agglomerative和divisive），也可以理解为自下而上法（bottom-up）和自上而下法（top-down）。自下而上法就是一开始每个个体（object）都是一个 类，然后根据linkage寻找同类，最后形成一个“类”。自上而下法就是反过来，一开始所有个体都属于一个“类”，然后根据linkage排除异己，最后每个个体都成为一个“类”。这两种路方法没有孰优孰劣之分，只是在实际应用的时候要根据数据特点以及你想要的“类”的个数，来考虑是自上而下更快还是自下而上更快。至于根据Linkage判断“类” 的方法就是最短距离法、最长距离法、中间距离法、类平均法等等（其中类平均法往往被认为是最常用也最好用的方法，一方面因为其良好的单调性，另一方面因为其空间扩张/浓缩的程度适中）。为弥补分解与合并的不足，层次合并经常要与其它聚类方法相结合，如循环定位。 2）Hierarchical methods中比较新的算法有BIRCH（Balanced Iterative Reducing and Clustering Using Hierarchies利用层次方法的平衡迭代规约和聚类）主要是在数据量很大的时候使用，而且数据类型是numerical。首先利用树的结构对对象集进行划分，然后再利用其它聚类方法对这些聚类进行优化；ROCK（A Hierarchical Clustering Algorithm for Categorical Attributes）主要用在categorical的数据类型上；Chameleon（A Hierarchical Clustering Algorithm Using Dynamic Modeling）里用到的linkage是kNN（k-nearest-neighbor）算法，并以此构建一个graph，Chameleon的聚类效果被认为非常强大，比BIRCH好用，但运算复杂度很高，O(n^2)。 2、层次聚类的流程 凝聚型层次聚类的策略是先将每个对象作为一个簇，然后合并这些原子簇为越来越大的簇，直到所有对象都在一个簇中，或者某个终结条件被满足。绝大多数层次聚类属于凝聚型层次聚类，它们只是在簇间相似度的定义上有所不同。这里给出采用最小距离的凝聚层次聚类算法流程： (1) 将每个对象看作一类，计算两两之间的最小距离； (2) 将距离最小的两个类合并成一个新类； (3) 重新计算新类与所有类之间的距离； (4) 重复(2)、(3)，直到所有类最后合并成一类。
谱聚类Clustering -
聚类分析 1.聚类分析定义： 2.聚类方法： 3.谱聚类： 3.1 常见矩阵变换 3.2 谱聚类流程 3.3 谱聚类理论前提、证明 3.4 图像分割实例结果 4.总结：
聚类分析： ?聚类分析（Cluster analysis，亦称为群集分析）是对于静态数据分析的一门技术，在许多领域受到广泛应用，包括机器学习，数据挖掘，模式识别，图像分析以及生物信息。
算法分类： ?数据聚类算法可以分为结构性或者分散性。 ?结构性算法以前成功使用过的聚类器进行分类。结构性算法可以从上至下或者从下至上双向进行计算。从下至上算法从每个对象作为单独分类开始，不断融合其中相近的对象。而从上至下算法则是把所有对象作为一个整体分类，然后逐渐分小。 ?分散型算法是一次确定所有分类。K-均值法及衍生算法。 ?谱聚类（spectral clustering）
结构型：层次聚类的一个例子：
分散型：K-均值算法：
分散型k-means 及其衍生算法的比较：K-means K-Medoids K-Means算法： 1. 将数据分为k个非空子集 2. 计算每个类中心点（k-means
聚类算法分析报告汇总
嵌入式方向工程设计实验报告 学院班级：130712 学生学号：13071219 学生姓名：杨阳 同作者：无 实验日期：2010年12月
聚类算法分析研究 1 实验环境以及所用到的主要软件 Windows Vista NetBeans6.5.1 Weka3.6 MATLAB R2009a 2 实验内容描述 聚类是对数据对象进行划分的一种过程，与分类不同的是，它所划分的类是未知的，故此，这是一个“无指导的学习” 过程，它倾向于数据的自然划分。其中聚类算法常见的有基于层次方法、基于划分方法、基于密度以及网格等方法。本文中对近年来聚类算法的研究现状与新进展进行归纳总结。一方面对近年来提出的较有代表性的聚类算法，从算法思想。关键技术和优缺点等方面进行分析概括；另一方面选择一些典型的聚类算法和一些知名的数据集，主要从正确率和运行效率两个方面进行模拟实验，并分别就同一种聚类算法、不同的数据集以及同一个数据集、不同的聚类算法的聚类情况进行对比分析。最后通过综合上述两方面信息给出聚类分析的研究热点、难点、不足和有待解决的一些问题等。 实验中主要选择了K 均值聚类算法、FCM 模糊聚类算法并以UCI Machine Learning Repository 网站下载的IRIS 和WINE 数据集为基础通过MATLAB 实现对上述算法的实验测试。然后以WINE 数据集在学习了解Weka 软件接口方面的基础后作聚类分析，使用最常见的K 均值（即K-means ）聚类算法和FCM 模糊聚类算法。下面简单描述一下K 均值聚类的步骤。 K 均值算法首先随机的指定K 个类中心。然后： （1）将每个实例分配到距它最近的类中心，得到K 个类； （2）计分别计算各类中所有实例的均值，把它们作为各类新的类中心。 重复（1）和（2），直到K 个类中心的位置都固定，类的分配也固定。 在实验过程中通过利用Weka 软件中提供的simpleKmeans （也就是K 均值聚类算法对WINE 数据集进行聚类分析，更深刻的理解k 均值算法，并通过对实验结果进行观察分析，找出实验中所存在的问题。然后再在学习了解Weka 软件接口方面的基础上对Weka 软件进行一定的扩展以加入新的聚类算法来实现基于Weka 平台的聚类分析。 3 实验过程 3.1 K 均值聚类算法 3.1.1 K 均值聚类算法理论 K 均值算法是一种硬划分方法，简单流行但其也存在一些问题诸如其划分结果并不一定完全可信。K 均值算法的划分理论基础是 2 1 min i c k i k A i x v ∈=-∑∑ （1） 其中c 是划分的聚类数，i A 是已经属于第i 类的数据集i v 是相应的点到第i 类的平均距离，即
聚类算法综述
西南民族大学学报·自然科学版第37卷5月专辑 Journal of Southwest University for Nationalities ?Natural Science Edition May. 2011___________________________________________________________________ ___________________________ 收稿日期：2011-03-01 作者简介：向培素(1974-), 女, 副教授, 主要研究方向: 计算机应用, 检索技术. 基金项目：本文是“西南民族大学校级科研项目”(09NYB007)的研究成果之一. 文章编号: 1003-2843(2011)05专-0112-03 聚类算法综述 向培素 (西南民族大学电气信息工程学院, 四川成都 610041) 摘 要: 聚类分析是一种基本的数据分析方法,它在数据挖掘,统计学,空间数据库技术,人工智能,生物学研究,机器学习, 模式识别等领域都得到了广泛的应用. 论文介绍了各类主要的聚类算法,并概述了其主要应用领域. 关键词: 聚类算法; 半监督聚类 中图分类号: G642 文献标志码: A doi ：10.3969/j.issn.1003-2483.2011.05专.33 随着信息技术的发展, 人们积累了越来越多的音、视频数据, 以及文本, 图片等数据, 为了从这些海量数据中查找, 提取有用信息, 出现了数据挖掘技术. 聚类作为数据挖掘的重要技术之一, 在机器学习、工程学、神经网络、生物学、统计学、地球科学以及社会科学和经济学等许多领域起着越来越重要的作用. 传统的聚类算法大致分为两类：层次聚类算法, 分割聚类算法. 1 层次聚类算法 层次聚类是对给定的数据对象的集合进行层次的分界, 根据一些指定标准把数据排列成一个树状结构的算法. 根据层次分界的表示方式, 层次聚类方法又可以分为凝聚的和分裂的两种. 凝聚算法先将每个数据作为一个簇, 然后根据一定的规则将簇合并, 凝聚算法又有单连接(single linkage)、全连接(complete linkage)和平均连接(average linkage)方法. 单连接是指当两个簇之间存在互连的边, 并且簇中数据最小距离小于等于给定的阈值, 则认为这两个簇的距离足够小, 可以合并. 全连接和单连接类似, 不过全连接是使用簇中数据的最大距离作为簇间距离. 平均连接使用两簇中数据的两两距离的平均值作为簇间距离. 分裂聚类先将所有数据归在一个簇里, 然后对簇中联系不紧密的数据进行分裂, 分到其他簇里, 分裂聚类有一些简化的算法, 如单元分裂法和多元分裂法. 单元分裂法每一次选取一个变量对簇进行分裂, 和变量相同的数据归为一类, 和变量不同的数据归为另一类. 多元分裂则是选取一个距离其他数据最远的数据构成分离组, 然后计算簇中每一个数据距离分离组的距离并和该数据与簇中其他数据的距离进行比较, 若该数据距离分离组的距离更近, 则将该数据划入分离组. 重复这个过程, 直到找不到这样的数据为止. 2 分割聚类算法 分割聚类法先对所有数据点进行较为粗略的划分, 然后通过重复的迭代算法使某个准则达到最优化来对划分进行修正. 分割聚类法又可以分为基于密度的算法, 基于网格的算法, 基于图论的算法, 基于平方误差的迭代重分配算法.
聚类算法比较
聚类算法: 1. 划分法：K-MEANS算法、K-M EDOIDS算法、CLARANS算法； 1）K-means 算法： 基本思想是初始随机给定K个簇中心，按照最邻近原则把待分类样本点分到各个簇。然后按平均法重新计算各个簇的质心，从而确定新的簇心。一直迭代，直到簇心的移动距离小于某个给定的值。 K-Means聚类算法主要分为三个步骤： (1)第一步是为待聚类的点寻找聚类中心 (2)第二步是计算每个点到聚类中心的距离，将每个点聚类到离该点最近的聚类中去 (3)第三步是计算每个聚类中所有点的坐标平均值，并将这个平均值作为新的聚类中心 反复执行(2)、(3)，直到聚类中心不再进行大范围移动或者聚类次数达到要求为止 下图展示了对n个样本点进行K-means聚类的效果，这里k取2： (a)未聚类的初始点集 (b)随机选取两个点作为聚类中心 (c)计算每个点到聚类中心的距离，并聚类到离该点最近的聚类中去 (d)计算每个聚类中所有点的坐标平均值，并将这个平均值作为新的聚类中心 (e)重复(c),计算每个点到聚类中心的距离，并聚类到离该点最近的聚类中去 (f)重复(d),计算每个聚类中所有点的坐标平均值，并将这个平均值作为新的聚类中心 优点： 1.算法快速、简单; 2.对大数据集有较高的效率并且是可伸缩性的; 3.时间复杂度近于线性，而且适合挖掘大规模数据集。 缺点： 1. 在 K-means 算法中 K 是事先给定的，这个 K 值的选定是非常难以估计的。 2. 在 K-means 算法中，首先需要根据初始聚类中心来确定一个初始划分，然后对初始划分进行优化。这个初始聚类中心的选择对聚类结果有较大的影响。
AffinityPropagation算法介绍
AP聚类算法 1.分类与聚类 1.1 分类算法简介 分类(classification )是找出描述并区分数据类或概念的模型(或函数)，以便能够使用模型预测类标记未知的对象类。在分类算法中输入的数据，或称训练集（Training Set），是一条条的数据库记录（Record）组成的。每一条记录包含若干条属性（Attribute），组成一个特征向量。训练集的每条记录还有一个特定的类标签（Class Label）与之对应。该类标签是系统的输入，通常是以往的一些经验数据。一个具体样本的形式可为样本向量:(v1, v2, ... , vn; c)。在这里vi表示字段值,c表示类别。 分类的目的是：分析输入的数据，通过在训练集中的数据表现出来的特性，为每一个类找到一种准确的描述或者模型，这种描述常常用谓词表示。由此生成的类描述用来对未来的测试数据进行分类。尽管这些未来的测试数据的类标签是未知的，我们仍可以由此预测这些新数据所属的类。注意是预测，而不能肯定。我们也可以由此对数据中的每一个类有更好的理解。也就是说：我们获得了对这个类的知识。 下面对分类流程作个简要描述： 训练：训练集——>特征选取——>训练——>分类器 分类：新样本——>特征选取——>分类——>判决 常见的分类算法有：决策树、KNN法(K-Nearest Neighbor)、SVM法、VSM法、Bayes法、神经网络等。 1.2 聚类算法简介 聚类(clustering)是指根据“物以类聚”的原理，将本身没有类别的样本聚集成不同的组，这样的一组数据对象的集合叫做簇，并且对每一个这样的簇进行描述的过程。与分类规则不同，进行聚类前并不知道将要划分成几个组和什么样的组，也不知道根据哪些空间区分规则来定义组。它的目的是使得属于同一个簇的样本之间应该彼此相似，而不同簇的样本应该足够不相似。 聚类分析的算法可以分为：划分法（Partitioning Methods）、层次法（Hierarchical Methods）、基于密度的方法（density-based methods）、基于网格的方法（grid-based methods）、基于模型的方法（Model-Based Methods）。经典的K-means和K-centers都是划分法。 1.3 分类与聚类的区别 聚类分析也称无监督学习或无指导学习，聚类的样本没有标记，需要由聚类学习算法来自动确定;在分类中，对于目标数据库中存在哪些类是知道的，要做的就是将每一条记录分别属于哪一类标记出来。聚类学习是观察式学习，而不是示例式学习。可以说聚类分析可以作为分类分析的一个预处理步骤。 2. k-means算法 k-means算法接受输入量k；然后将n个数据对象划分为k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较低。簇的相似度是关于簇中对象的均值度量，可以看作簇的质心(centriod)或重心(center of gravity)。 k-means 算法的工作过程说明如下：首先从n个数据对象任意选择k 个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类；然后再计算每个所获新聚类的聚类中
自动确定聚类中心的势能聚类算法
自动确定聚类中心的势能聚类算法* 于晓飞1，葛洪伟1,2+ 1.江南大学物联网工程学院，江苏无锡214122 2.江南大学轻工过程先进控制教育部重点实验室，江苏无锡214122 Potential Clustering by Automatic Determination of Cluster Centers YU Xiaofei 1,GE Hongwei 1,2+ 1.School of Internet of Things Engineering,Jiangnan University,Wuxi,Jiangsu 214122,China 2.Ministry of Education Key Laboratory of Advanced Process Control for Light Industry,Jiangnan University,Wuxi,Jiangsu 214122,China +Corresponding author:E-mail:ghw8601@https://www.docsj.com/doc/cf11522754.html, YU Xiaofei,GE Hongwei.Potential clustering by automatic determination of cluster centers.Journal of Fron-tiers of Computer Science and Technology,2018,12(6)：1004-1012. Abstract:Potential-based hierarchical agglomerative clustering (PHA)uses a new similarity metric to get clustering results more efficiently.However,it suffers from the problem how to determine the number of clusters automatically.And it assigns samples according to distance measure,which ignores the influence of potential.To overcome these shortcomings,this paper proposes a new algorithm that can determine the number of clusters automatically.Firstly,two variables are used to find the clustering centers automatically:the potential of each point and the distance from points to their parent nodes.Then,the distance and the potential are used to assign the remaining points.Finally,the experiments on artificial data sets and real data sets show that the new algorithm not only determines the number of clusters automatically,but also has better clustering results. Key words:clustering;potential-based hierarchical agglomerative clustering (PHA);potential clustering;automati-cally determining the number of clustering *The National Natural Science Foundation of China under Grant No.61305017(国家自然科学基金);the Research Innovation Pro-gram for College Graduates of Jiangsu Province under Grant No.KYLX15_1169(江苏省普通高校研究生科研创新计划项目).Received 2017-02,Accepted 2017-04. CNKI 网络出版:2017-04-13,https://www.docsj.com/doc/cf11522754.html,/kcms/detail/11.5602.TP.20170413.1027.004.html ISSN 1673-9418CODEN JKYTA8 Journal of Frontiers of Computer Science and Technology 1673-9418/2018/12(06)-1004-09 doi:10.3778/j.issn.1673-9418.1702048E-mail:fcst@https://www.docsj.com/doc/cf11522754.html, https://www.docsj.com/doc/cf11522754.html, Tel:+86-10-89056056万方数据
各种聚类算法的比较
各种聚类算法的比较 聚类的目标是使同一类对象的相似度尽可能地小；不同类对象之间的相似度尽可能地大。目前聚类的方法很多，根据基本思想的不同，大致可以将聚类算法分为五大类：层次聚类算法、分割聚类算法、基于约束的聚类算法、机器学习中的聚类算法和用于高维度的聚类算法。摘自数据挖掘中的聚类分析研究综述这篇论文。 1、层次聚类算法 1.1聚合聚类 1.1.1相似度依据距离不同：Single-Link:最近距离、Complete-Link：最远距离、Average-Link：平均距离 1.1.2最具代表性算法 1）CURE算法 特点：固定数目有代表性的点共同代表类 优点：识别形状复杂，大小不一的聚类，过滤孤立点 2）ROCK算法 特点：对CURE算法的改进 优点：同上，并适用于类别属性的数据 3）CHAMELEON算法 特点：利用了动态建模技术 1.2分解聚类 1.3优缺点 优点：适用于任意形状和任意属性的数据集；灵活控制不同层次的聚类粒度，强聚类能力 缺点：大大延长了算法的执行时间，不能回溯处理 2、分割聚类算法 2.1基于密度的聚类 2.1.1特点 将密度足够大的相邻区域连接，能有效处理异常数据，主要用于对空间数据的聚类
1）DBSCAN：不断生长足够高密度的区域 2）DENCLUE：根据数据点在属性空间中的密度进行聚类，密度和网格与处理的结合 3）OPTICS、DBCLASD、CURD：均针对数据在空间中呈现的不同密度分不对DBSCAN作了改进 2.2基于网格的聚类 2.2.1特点 利用属性空间的多维网格数据结构，将空间划分为有限数目的单元以构成网格结构； 1）优点：处理时间与数据对象的数目无关，与数据的输入顺序无关，可以处理任意类型的数据 2）缺点：处理时间与每维空间所划分的单元数相关，一定程度上降低了聚类的质量和准确性 2.2.2典型算法 1）STING：基于网格多分辨率，将空间划分为方形单元，对应不同分辨率2）STING+：改进STING，用于处理动态进化的空间数据 3）ＣＬＩＱＵＥ：结合网格和密度聚类的思想，能处理大规模高维度数据4）WaveCluster：以信号处理思想为基础 2.3基于图论的聚类 2.3.1特点 转换为组合优化问题，并利用图论和相关启发式算法来解决，构造数据集的最小生成数，再逐步删除最长边 1）优点：不需要进行相似度的计算 2.3.2两个主要的应用形式 1）基于超图的划分 2）基于光谱的图划分 2.4基于平方误差的迭代重分配聚类 2.4.1思想 逐步对聚类结果进行优化、不断将目标数据集向各个聚类中心进行重新分配以获最优解
谱聚类报告
机器学习报告 一．绪论 聚类是探索性数据分析中广泛采用的一种技术，其应用范围包括统计学、计算机科学、生物学、社会科学和心理学等等。在处理经验数据的时候，我们可能倾向于根据数据的“近似表现”将数据确定到一定的类别。而本次我们小组的实验主要是基于聚类算法中的谱聚类方法，通过对两种谱聚类方法的实验和一些应用，验证算法的效果，加深对该方法的理解。 由于谱聚类的数值实现很简单，利用简单的线性代数学方法就能有效解决，而且相比传统的K 均值方法等聚类方法有很多优点，所以谱聚类方法称为了很流行的现代聚类算法之一。 以K 均值方法为例，正如我们所知，该方法主要存在这样一些问题：首先，其只适用于凸球形的样本空间，如果样本空间非凸，则会陷入局部最优，导致聚类效果不佳；再有，由于该方法计算使用的是欧氏空间中的原始数据向量，所以在样本维数很大的时候，K 均值算法的计算量会很大，导致了计算的困难；聚类数K 难以确定等等。而谱聚类则能很好地解决这些问题。 在本次实验中，我们小组根据相关文献，认真学习和讨论了谱聚类的先关概念。首先，我们研究了一般的谱聚类和标准化谱聚类的概念和它们的异同，并通过实验对比，验证了谱聚类的效果，其中标准化谱聚类有显著的优势。接下来，将谱聚类应用于图像分割问题，显示出谱聚类良好的应用价值。最后，我们查阅相关文献，尝试从另外一个角度去理解谱聚类方法。通过这次学习，我们对谱聚类的理解得到了大大加深，对于很多疑难的地方也通过查看有关文献和小组讨论得到了解决，并通过小组合作锻炼了自身的团队意识和配合工作的能力。 二．谱聚类基本思想 谱聚类是一种基于图论的聚类方法，把样本看作图的顶点，样本间的相似度对应带权值的边（其中相似度可以通过高斯核函数等方法构造），根据类间相似度最小，类内相似度最大的原则，便可以将样本聚类问题变成了图的分割问题：分割使得连接不同类之间的边的权值尽可能小，而类内点之间的边的权值尽可能高。虽然这样对应的最小化图分割问题是一个NP-HARD 问题，但是我们可以将其转化为最小化图的Laplace 矩阵的特征值问题。 具体地，给定样本特征之后，我们首先要计算样本两两之间的相似度值，并通过这些值构造出近邻矩阵。以高斯核函数为例，计算公式如下： 22||||(2)i j x x ij w e σ--= 作为第i 个样本和第j 个样本之间相似度的度量。而近邻矩阵如下： ()ij W w =。
谱聚类算法(Spectral Clustering)原理分析
谱聚类算法(Spectral Clustering) 谱聚类(Spectral Clustering, SC)是一种基于图论的聚类方法——将带权无向图划分为两个或两个以上的最优子图，使子图内部尽量相似，而子图间距离尽量距离较远，以达到常见的聚类的目的。其中的最优是指最优目标函数不同，可以是割边最小分割——如图1的Smallest cut(如后文的Min cut)，也可以是分割规模差不多且割边最小的分割——如图1的Best cut(如后文的Normalized cut)。 图1 谱聚类无向图划分——Smallest cut和Best cut 这样，谱聚类能够识别任意形状的样本空间且收敛于全局最优解，其基本思想是利用样本数据的相似矩阵(拉普拉斯矩阵)进行特征分解后得到的特征向量进行聚类。 1 理论基础 对于如下空间向量item-user matrix： 如果要将item做聚类，常常想到k-means聚类方法，复杂度为o(tknm)，t为迭代次数，k为类的个数、n为item个数、m为空间向量特征数： 1 如果M足够大呢？ 2 K的选取？ 3 类的假设是凸球形的？ 4 如果item是不同的实体呢？ 5 Kmeans无可避免的局部最优收敛？ …… 这些都使常见的聚类问题变得相当复杂。 1.1 图的表示
如果我们计算出item与item之间的相似度，便可以得到一个只有item的相似矩阵，进一步，将item看成了Graph(G)中Vertex(V)，歌曲之间的相似度看成G中的Edge(E)，这样便得到我们常见的图的概念。 对于图的表示(如图2)，常用的有： 邻接矩阵：E，e ij表示v i和v i的边的权值，E为对称矩阵，对角线上元素为0，如图2-2。 Laplacian矩阵：L = D – E，其中d i (行或列元素的和)，如图2-3。 图2 图的表示 1.2 特征值与L矩阵 先考虑一种最优化图像分割方法，以二分为例，将图cut为S和T两部分，等价于如下损失函数cut(S, T)，如公式1所示，即最小(砍掉的边的加权和)。 假设二分成两类，S和T，用q(如公式2所示)表示分类情况，且q满足公式3的关系，用于类标识。 那么：
谱聚类算法 算法简介
谱聚类算法算法简介 谱聚类算法建立在谱图理论基础上，与传统的聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解的优点。 该算法首先根据给定的样本数据集定义一个描述成对数据点相似度的亲合矩阵,并且计算矩阵的特征值和特征向量，然后选择合适的特征向量聚类不同的数据点。谱聚类算法最初用于计算机视觉、VLS I 设计等领域，最近才开始用于机器学习中，并迅速成为国际上机器学习领域的研究热点。 谱聚类算法建立在图论中的谱图理论基础上，其本质是将聚类问题转化为图的最优划分问题，是一种点对聚类算法，对数据聚类具有很好的应用前景。 算法步骤 谱聚类算法将数据集中的每个对象看作是图的顶点V，将顶点间的相似度量化作为相应顶点连接边E的权值，这样就得到一个基于相似度的无向加权图G(V, E)，于是聚类问题就可以转化为图的划分问题。基于图论的最优划分准则就是使划分成的子图内部相似度最大，子图之间的相似度最小。 虽然根据不同的准则函数及谱映射方法，谱聚类算法有着不同的具体实现方法，但是这些实现方法都可以归纳为下面三个主要步骤： 1) 构建表示对象集的相似度矩阵W； 2) 通过计算相似度矩阵或拉普拉斯矩阵的前k个特征值与特征向量，构建特征向量空间； 3) 利用K-means或其它经典聚类算法对特征向量空间中的特征向量进行聚类。 上面的步骤只是谱聚类算法的一个总体框架，由于划分准则、相似度矩阵计算方法等因素的差别，具体的算法实现同样会有所差别，但其本质依然是图划分问题的连续放松形式。 划分准则 谱聚类算法将聚类问题就可以转化为图的划分问题之后，基于图论的划分准则的优劣直接影响到聚类结果的好坏。常见的划分准则有Mini cut，Average cut，Normalized cut，Min-max cut，Ratio cut，MNcut等。最小割集准则 在对图像分割中产生了较好的效果，但是该准则容易产生分割出只包含几个顶点的较小子图的歪斜分割现象。 规范割集准则 在2000年Shi和Malik根据谱图理论建立了2-way划分的规范割目标函数，此方法通过计算分割之后的连接边损失值在各个子图与所有顶点之间的连接边权重总值中所占比例之和来衡量划分的优劣。 比例割集准则 对于超大规模集成电路设计中的电路层次设计和分支划分问题，最
谱聚类
谱聚类 七月算法邹博 2015年11月15日
9月机器学习班2/21 谱和谱聚类 ?方阵作为线性算子，它的所有特征值的全体统称方阵的谱。 ?方阵的谱半径为最大的特征值 ?矩阵A 的谱半径：(A T A)的最大特征值 ?谱聚类是一种基于图论的聚类方法，通过对样本数据的拉普拉斯矩阵的特征向量进行聚类，从而达到对样本数据聚类的目的。
9月机器学习班3/21 谱分析的整体过程 ?给定一组数据x 1,x 2,...x n ，记任意两个点之间的相似度(“距离”的减函数)为s ij =
9月机器学习班4/21 若干概念 ?无向图G=(V,E) ?邻接矩阵 ?顶点的度di →度矩阵D (对角阵)
9月机器学习班5/21 若干概念 ?子图A 的指示向量 ?A 和B 是图G 的不相交子图，则定义子图的连接权：
9月机器学习班6/21 相似度图G 的建立方法 ?全连接图 ?高斯相似度函数：距离越大，相似度越小 ?ε近邻图 ?给定参数ε ?思考：如何选择ε？ ?图G 的权值的均值 ?图G 的最小生成树的最大边 ?k 近邻图(k-nearest neighbor graph) ?若vi 的k 最近邻包含vj ，vj 的k 最近邻不一定包含vi ：有向图?忽略方向的图，往往简称“k 近邻图” ?两者都满足才连接的图，称作“互k 近邻图(mutual)”
K-means算法简介
K-means聚类算法 K-means也是聚类算法中最简单的一种了，但是里面包含的思想却是不一般。最早我使用并实现这个算法是在学习韩爷爷那本数据挖掘的书中，那本书比较注重应用。看了Andrew Ng的这个讲义后才有些明白K-means后面包含的EM思想。 聚类属于无监督学习，以往的回归、朴素贝叶斯、SVM等都是有类别标签y的，也就是说样例中已经给出了样例的分类。而聚类的样本中却没有给定y，只有特征x，比如假设 宇宙中的星星可以表示成三维空间中的点集。聚类的目的是找到每个样本x潜在的类别y，并将同类别y的样本x放在一起。比如上面的星星，聚类后结果是一个个星团，星团里面的点相互距离比较近，星团间的星星距离就比较远了。 在聚类问题中，给我们的训练样本是，每个，没有了y。 K-means算法是将样本聚类成k个簇（cluster），具体算法描述如下： 1、随机选取k个聚类质心点（cluster centroids）为。 2、重复下面过程直到收敛 { 对于每一个样例i，计算其应该属于的类 对于每一个类j，重新计算该类的质心 } K是我们事先给定的聚类数，代表样例i与k个类中距离最近的那个类，的值 是1到k中的一个。质心代表我们对属于同一个类的样本中心点的猜测，拿星团模型来解释就是要将所有的星星聚成k个星团，首先随机选取k个宇宙中的点（或者k个星星）作为k个星团的质心，然后第一步对于每一个星星计算其到k个质心中每一个的距离，然后选取 距离最近的那个星团作为，这样经过第一步每一个星星都有了所属的星团；第二步对于
每一个星团，重新计算它的质心（对里面所有的星星坐标求平均）。重复迭代第一步和第二步直到质心不变或者变化很小。 下图展示了对n个样本点进行K-means聚类的效果，这里k取2。 K-means面对的第一个问题是如何保证收敛，前面的算法中强调结束条件就是收敛，可以证明的是K-means完全可以保证收敛性。下面我们定性的描述一下收敛性，我们定义畸变函数（distortion function）如下： J函数表示每个样本点到其质心的距离平方和。K-means是要将J调整到最小。假设当 前J没有达到最小值，那么首先可以固定每个类的质心，调整每个样例的所属的类别来让J函数减少，同样，固定，调整每个类的质心也可以使J减小。这两个过程就是内循环中使J单调递减的过程。当J递减到最小时，和c也同时收敛。（在理论上，可以有多组不同的和c值能够使得J取得最小值，但这种现象实际上很少见）。