聚类算法综述

[聚类算法综述蝎子no1--------来自沙漠2012.6.4搜集整理，感谢原作者]聚类算法综述引用请注明出处：聚类方法概述聚类方法是将物理或抽象对象的集合组成为由类似的对象组成的多个类的过程被成为聚类。由聚类所组成的簇是一组数据对象的集合，这些对象与同一簇中的对象彼此类似，与其他簇中的对象相异。在许多应用中，可以将一些簇中的数据对象作为一个整体来对待。聚类是研究数据间逻辑上或物理上的相互关系的技术，其分析结果不仅可以揭示数据间的内在联系与区别，还可以为进一步的数据分析与知识发现提供重要依据。它是数据挖掘技术中的重要组成部分。作为统计学的重要研究内容之一，聚类分析具有坚实的理论基础，并形成了系统的方法学体系。数据挖掘中聚类算法的应用很广泛。在商务上，聚类能帮助市场分析人员从客户基本库中发现不同的客户群，并且用不同的购买模式来刻画不同的消费群体的特征。在生物学上，聚类能用于帮助推导植物和动物的种类，基因和蛋白质的分类，获得对种群中固定结构的认识。聚类在地球观测数据中相似地区的确定，根据房屋的类型、价值和位置对一个城市中房屋的分类发挥作用。聚类也能用来对web上的文档进行分类，以发现有用的信息。聚类分析能作为一种独立的工具来获得数据分布的情况，观察每个簇的特点，并对某些特定的节点进一步分析。此外，聚类还可以作为其他方法的预处理步骤。数据聚类正在蓬勃的发展，有贡献的领域包括数据挖掘，统计学，机器学习，空间数据库技术，生物学以及市场营销。现在数据聚类分析已经成为一个非常活跃的研究课题。作为统计学的一个分支，聚类分析已经被广泛地研究若干年，主要集中在基于距离的聚类分析。基于k-means（k-平均值）、k-medoids（k-中心点）和其他一些的聚类分析工具已经被加入到许多统计分析的软件中，例如S-Plus、SPSS和SAS。在机器学习领域，聚类分析是无指导学习的例子。与分类不同，聚类不需要依赖事先定义的类和带符号的训练实践。所以聚类分析是观察式学习，而不是示例式学习。在数据挖掘领域，研究工作已经集中在为大型数据库的有效和实际的聚类分析寻找适当的方法。活跃的研究课题集中在聚类方法的可伸缩性，方法对聚类复杂形状和类型的数据的有效性，高维聚类分析技术，以及针对大型数据库中混合数值和分类数据的聚类方法。由于研究的需要，现在将重点放在数据挖掘中聚类方法的应用上。数据挖掘中对聚类的典型要求如下：（1）可伸缩性。一般的聚类算法使用鱼规模小于200的数据集合上，而现在很多大型数据库的数据量达到百万个，这就要求聚类有好的可伸缩性。[聚类算法综述蝎子no1--------来自沙漠2012.6.4搜集整理，感谢原作者]（2）处理不同类型属性的能力。应用的多元化，可能要求一个聚类能处理多种数据类型，像二元类型、分类/标称类型、序数型数据，或者这些类型的混合。（3）发现任意形状的聚类。基于距离的聚类算法趋向于发现相近尺度和密度的球状簇。但一个簇的形状是任意的，所以就要求聚类能发现这些被忽略的聚类。（4）用于决定输入参数的领域知识的最小化。由于聚类结果对输入参数的要求很敏感，但参数通常很难确定，特别是对于高维对象的数据来说。所以输入参数的质量直接影聚类的结果，这就加重了用户的负担。（5）处理噪声数据的能力。绝大多数数据集中存在很多孤立点、空缺、未知数据或错误数据。一些聚类算法对于这样的数据敏感，导致低质量聚类结果。（6）对输入数据的顺序不敏感。（7）高维性。一个数据库或是数据仓库可能只包含若干维，很多聚类算法只涉及两到三维。人类对于三维以内的数据有判断性，高于三维的数据聚类的挑战性很高，数据可能很稀疏，也可能高度偏斜。（8）基于约束的聚类。现实世界可能要在约束条件下进行聚类，这就要求既要满足客户特定的约束，又具有良好聚类特性的数据分组。（9）可理解行和可用性。用户希望聚类结果是可解释的，可理解的，并且是可用的。也就是，聚类与最后的应用相联系。应用目标对聚类方法的影响也是一个重要的课题。2聚类方法基础2.1聚类过程简述聚类是一个将数据集划分为若干组或簇的过程，使得同一类的数据对象之间的相似度较高，而不同类的数据对象之间的相似度较低。聚类问题的关键是把相似的事物聚集在一起。聚类的一般步骤的细节如下：（1）特征选择。必须适当地选择特征，尽可能多的包含任务关心的信息。在特征中，信息多余减少和最小化是主要目的。（2）相似性度量。用于定量度量两个特征向量之间如何“相似”或“不相似”。一个简单的度量如欧氏距离经常被用来反应两个特征向量之间的非相似性。（3）聚类算法。已经选择了合适的相似性度量，这步涉及到选择特定的聚类算法，用于揭示数据集中的聚类结构。（4）结果验证。一旦用聚类算法得到结果，就需要验证其正确性。（5）结果判定。在许多情况下，应用领域的专家必须用其他实验数据和分析判定聚类结果，最后做出正确的结论。[聚类算法综述蝎子no1--------来自沙漠2012.6.4搜集整理，感谢原作者]聚类分析有很多种算法，每种算法都是优化了某一方面或某几方面的特征。聚类算法的优劣标准本身就是一个值得研究的问题，对于聚类的评价有不同的标准。现在通用的聚类算法都是从几个方面来衡量的，而没有完全使用量化的客观标准。下面给出六条关于聚类的主要标准:（1）处理大的数据集的能力。（2）处理任意形状，包括有间隙的嵌套的数据的能力。（3）算法处理的结果与数据输入的顺序是否相关，也就是说算法是否独立于数据输入顺序。（4）处理数据噪声的能力。（5）是否需要预先知道聚类个数，是否需要用户给出领域知识。（6）算法处理有很多属性数据的能力，也就是对数据维数是否敏感。2.2聚类方法的数据结构基于内存的聚类算法有以下两种代表性的数据结构：数据矩阵（对象与变量结构）：它用p个变量表现n个对（1）象下边这种数据结构是关系表的形式，或看成n×p的矩阵。x11…x1f…x1p:::::xi1…xif…xip:::::xn1…xnf…xnp（2）相异度矩阵（对象-对象结构）：存储n个对象两两之间的近似性，表现形式是一个n×n维的矩阵。0d（2，1）0d（3，1）d（3，2）0:::[聚类算法综述蝎子no1--------来自沙漠2012.6.4搜集整理，感谢原作者]d（n，1）d（n，2）……0这里d（i，j）是对象i和对象j之间相异性的量化表示，通常为非负值，当两个对象i，j越相似，其值越接近0；反之，则值越大。2.2.1区间标度变量区间标度变量是一个粗略线性标度的连续变量。用来计算相异度d（i，j），其距离度量包括欧几里德距离，曼哈坦距离和明考斯基距离。首先实现数据的标准化，给定一个变量f的度量值，可以进行一下转化：（1）计算平均的绝对偏差Sf：Sf=（|x1f-mf|+|x2f-mf|+……+|xnf-mf|）/n这里x1f，……，xnf是f的n个度量值，mf是f的平均值。（2）计算标准化的度量值：Zif=（xif-mf）/sf我们知道对象之间的相异度是基于对象间的距离来计算的。最常用的度量方法是欧几里德距离，其形式如下：d(i,j)=(|xi1-xj1|2+|xi2-xj2|2+……+|xip-xjp|2)1/2这里i=（xi1,xi2,……,xip）和j=（xj1,xj2,……，xjp）是两个p维的数据对象。曼哈坦距离的公式如下：d(i,j)=|xi1-xj1|+|xi2-xj2|+……|xip-xjp|上面的两个公式必须满足下面的条件：[聚类算法综述蝎子no1--------来自沙漠2012.6.4搜集整理，感谢原作者]d(i,j)≧0:距离非负。d(i,i)=0:对象与自身的距离为0。d(i,j)=d(j,i):距离函数具有对称性。d(i,j)≦d(i,h)+d(h,j):对象i到对象j的距离小于等于途经其他任何对象h的距离之和。明考斯基距离是以上两中距离计算公式的概括，其具体的公式如下：d(i,j)=(|xi1-xj1|q+|xi2-xj2|q+……+|xip-xjp|q)1/q当q=1时该公式就是欧几里得距离公式；当q=2时，是曼哈坦距离公式。2.2.2二元变量二元变量只有0、1两个状态,0表示变量为空，1表示该变量存在。对象j10Sum对象i1qrq+r0sts+tSumq+sr+tpp=q+r+s+t二元变量中基于对称的二元变量的相似度称为恒定相似度，这里有最著名的简单匹配系数来评价两个对象之间的相似度，其定义如下：d（i，j）=（r+s）/（q+r+s+t）基于不对称的二元变量的相似度称为非恒定相似度，最著名的评价系数是Jaccard系数，形式如下：d（i，j）=（r+s）/（q+r+s）这里负匹配的数目t被认为是不重要的，所以省略。2.2.3标称型、序数型和比例标度型变量[聚类算法综述蝎子no1--------来自沙漠2012.6.4搜集整理，感谢原作者](1)标称变量标称变量是二元变量的推广，具有多于两个的状态值。如，draw_color是一的标称变量，状态有很多：红色、黄色、绿色、棕色、黑色、白色……。标称变量之间的相异度可以用简单匹配方法来计算：d（i，j）=（p-m）/p这里m是匹配的数目，即对i和j取值相同的变量数目，而p是全部变量的数目。p是全部变量的数目。(2)序数型变量序数型变量分离散的序数型变量和连续的序数型变量。其相似度的计算可以用2.1中提到的任何一个距离公式计算。(3)比例标度型变量比例标度型变量在非线性的标度取正的度量值，如AeBt或Ae-Bt这里A、B是正常数。(4)混合型变量现实中在一个系统数据库中可能有标度变量、二元变量、标称变量、序数型变量或比例标度变量。可取的方法是将所有的变量一起处理，只进行一个聚类分析。一种技术将不同类型的变量组合在单个相异度矩阵中，把所有意义的变量转换到共同的至于区间[0.0,1.0]上。3主要聚类方法的分类目前聚类算法有很多种。算法的选择取决于数据的类型、聚类的目的和应用。由于各种聚类算法之间存在很多交集，它们之间并不是完全独立的，所以很难对聚类算法进行严格意义上的划分，现就聚类算法的发展进程分为两类：传统的聚类算法和新发展的聚类算法。3.1传统聚类算法3.1.1层次方法层次法对给定的数据对象集合进行层次似的分解。按层次分解的形成方式，层次法可分为凝聚和分裂两大类。凝聚的方法，也称为自底向上的方法，一开始将每个对象作为单独的一个类，然后相继地合并相近的类，直到所有的类合并为一个（层次的最上层），或者达到一个终止条件为止。分裂的方法，也称为自顶[聚类算法综述蝎子no1--------来自沙漠2012.6.4搜集整理，感谢原作者]向下的方法，一开始将所有的对象置于一个类中。在迭代的每一步中，类被分裂为更小的类，直到每个类只包含一个对象，或者达到一个终止条件为止。在凝聚或者分裂层次聚类方法中，通常以用户定义的希望得到的类的数目作为结束条件。在类的合并或分裂过程中，需要考察类间的距离。类间距离的度量广泛采用如下四种方法：最小距离：dmin（Ci，Cj）=minp∈Ci,p'∈Cj|p-p'|最大距离：dmax（Ci，Cj）=maxp∈Ci,p'∈Cj|p-p'|平均值距离：dmcan（Ci，Cj）=|mi-mj|平均距离：层次方法(HierarchicalMethod)中代表算法有BIRCH、CURE、ROCK、CHAMELEON算法等。3.1.2划分方法给定一个包含n个数据对象的数据集，划分法构建数据的k个划分，每个划分表示一个类，并且k≤n。同时满足如下的要求：①每个组至少包含一个对象；②每个对象属于且仅属于一个组。给定要构建的划分的数目k，创建一个初始划分。然后采用一种迭代的重定位技术，尝试通过对象在划分间移动来改进划分。判定一个好的划分的一般准则是：在同一个类中的对象之间尽可能“接近”或相关，在不同类中的对象之间尽可能“远离”或不同，即使下列准则函数最小：式中的E是数据集中所有对象的平方误差的总和；mi是类Ci的平