文档视界 最新最全的文档下载
当前位置:文档视界 › 聚类算法介绍

聚类算法介绍

聚类算法
百科名片
聚类(Cluster)分析是由若干模式(Pattern)组成的,通常,模式是一个度量(Measurement)的向量,或者是多维空间中的一个点。聚类分析以相似性为基础,在一个聚类中的模式之间比不在同一聚类中的模式之间具有更多的相似性。
目录
概述
对聚类的典型要求如下
聚类算法分类
K-MEANS算法
K-MEDOIDS算法
Clara算法
Clarans算法
聚类的用途
编辑本段概述
俗话说:“物以类聚,人以群分”,在自然科学和社会科学中,存在着大量的分类问题。所谓类,通俗地说,就是指相似元素的集合。聚类分析又称群分析,它是研究(样品或指标)分类问题的一种统计分析方法。聚类分析起源于分类学,在古老的分类学中,人们主要依靠经验和专业知识来实现分类,很少利用数学工具进行定量的分类。随着人类科学技术的发展,对分类的要求越来越高,以致有时仅凭经验和专业知识难以确切地进行分类,于是人们逐渐地把数学工具引用到了分类学中,形成了数值分类学,之后又将多元分析的技术引入到数值分类学形成了聚类分析。聚类分析内容非常丰富,有系统聚类法、有序样品聚类法、动态聚类法、模糊聚类法、图论聚类法、聚类预报法等。
编辑本段对聚类的典型要求如下
可伸缩性:许多聚类算法在小于 200 个数据对象的小数据集合上工作得很好;但是,一个大规模数据库可能包含几百万个对象,在这样的大数据集合样本上进行聚类可能会导致有偏的结果。我们需要具有高度可伸缩性的聚类算法。
处理不同类型属性的能力:许多算法被设计用来聚类数值类型的数据。但是,应用可能要求聚类其他类型的数据,如二元类型(binary),分类/标称类型(categorical/nominal),序数型(ordinal)数据,或者这些数据类型的混合。
发现任意形状的聚类:许多聚类算法基于欧几里得或者曼哈顿距离度量来决定聚类。基于这样的距离度量的算法趋向于发现具有相近尺度和密度的球状簇。但是,一个簇可能是任意形状的。提出能发现任意形状簇的算法是很重要的。
用于决定输入参数的领域知识最小化:许多聚类算法在聚类分析中要求用户输入一定的参数,例如希望产生的簇的数目。聚类结果对于输入参数十分敏感。参数通常很难确定,特别是对于包含高维对象的数据集来说。这样不仅加重了用户的负担,也使得聚类的质量难以控制。
处理“噪声”数据的能力:绝大多数现实中的数据库都包含了孤立点,缺失,或者错误的数据。一些聚类算法对于这样的数据敏感,可能导致低质量的聚类结果。
对于输

入记录的顺序不敏感:一些聚类算法对于输入数据的顺序是敏感的。例如,同一个数据集合,当以不同的顺序交给同一个算法时,可能生成差别很大的聚类结果。开发对数据输入顺序不敏感的算法具有重要的意义。
高维度(high dimensionality):一个数据库或者数据仓库可能包含若干维或者属性。许多聚类算法擅长处理低维的数据,可能只涉及两到三维。人类的眼睛在最多三维的情况下能够很好地判断聚类的质量。在高维空间中聚类数据对象是非常有挑战性的,特别是考虑到这样的数据可能分布非常稀疏,而且高度偏斜。
基于约束的聚类:现实世界的应用可能需要在各种约束条件下进行聚类。假设你的工作是在一个城市中为给定数目的自动提款机选择安放位置,为了作出决定,你可以对住宅区进行聚类,同时考虑如城市的河流和公路网,每个地区的客户要求等情况。要找到既满足特定的约束,又具有良好聚类特性的数据分组是一项具有挑战性的任务。
可解释性和可用性:用户希望聚类结果是可解释的,可理解的,和可用的。也就是说,聚类可能需要和特定的语义解释和应用相联系。应用目标如何影响聚类方法的选择也是一个重要的研究课题。
记住这些约束,我们对聚类分析的学习将按如下的步骤进行。首先,学习不同类型的数据,以及它们对聚类方法的影响。接着,给出了一个聚类方法的一般分类。然后我们详细地讨论了各种聚类方法,包括划分方法,层次方法,基于密度的方法,基于网格的方法,以及基于模型的方法。最后我们探讨在高维空间中的聚类和孤立点分析(outlier analysis)。
编辑本段聚类算法分类
聚类分析计算方法主要有如下几种:
1. 划分法(partitioning methods):给定一个有N个元组或者纪录的数据集,分裂法将构造K个分组,每一个分组就代表一个聚类,K 2. 层次法(hierarchical methods):这种方法对给定的数据集进行层次似的分解,直到某种条件满足为止。具体又可分为“自底向上”和“自顶向下”两种方案。例如在“自底向上”

方案中,初始时每一个数据纪录都组成一个单独的组,在接下来的迭代中,它把那些相互邻近的组合并成一个组,直到所有的记录组成一个分组或者某个条件满足为止。代表算法有:BIRCH算法、CURE算法、CHAMELEON算法等;
3. 基于密度的方法(density-based methods):基于密度的方法与其它方法的一个根本区别是:它不是基于各种各样的距离的,而是基于密度的。这样就能克服基于距离的算法只能发现“类圆形”的聚类的缺点。这个方法的指导思想就是,只要一个区域中的点的密度大过某个阀值,就把它加到与之相近的聚类中去。代表算法有:DBSCAN算法、OPTICS算法、DENCLUE算法等;
4. 基于网格的方法(grid-based methods):这种方法首先将数据空间划分成为有限个单元(cell)的网格结构,所有的处理都是以单个的单元为对象的。这么处理的一个突出的优点就是处理速度很快,通常这是与目标数据库中记录的个数无关的,它只与把数据空间分为多少个单元有关。代表算法有:STING算法、CLIQUE算法、WAVE-CLUSTER算法;
5. 基于模型的方法(model-based methods):基于模型的方法给每一个聚类假定一个模型,然后去寻找能个很好的满足这个模型的数据集。这样一个模型可能是数据点在空间中的密度分布函数或者其它。它的一个潜在的假定就是:目标数据集是由一系列的概率分布所决定的。通常有两种尝试方向:统计的方案和神经网络的方案。
编辑本段K-MEANS算法
k-means 算法接受输入量 k ;然后将n个数据对象划分为 k个聚类以便使得所获得的聚类满足:同一聚类中的对象相似度较高;而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”(引力中心)来进行计算的。
k-means 算法的工作过程说明如下:首先从n个数据对象任意选择 k 个对象作为初始聚类中心;而对于所剩下其它对象,则根据它们与这些聚类中心的相似度(距离),分别将它们分配给与其最相似的(聚类中心所代表的)聚类;然后再计算每个所获新聚类的聚类中心(该聚类中所有对象的均值);不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数. k个聚类具有以下特点:各聚类本身尽可能的紧凑,而各聚类之间尽可能的分开。
编辑本段K-MEDOIDS算法
K-MEANS有其缺点:产生类的大小相差不会很大,对于脏数据很敏感。 改进的算法:k—medoids 方法。这儿选取一个对象叫做mediod来代替上面的中心的作用,这样的一个medoid就标识了这个类。步骤:
1,任意选取K个对象作为medoids(O1,O2,…Oi…Ok)。

下是循环的:
2,将余下的对象分到各个类中去(根据与medoid最相近的原则);
3,对于每个类(Oi)中,顺序选取一个Or,计算用Or代替Oi后的消耗—E(Or)。选择E最小的那个Or来代替Oi。这样K个medoids就改变了,下面就再转到2。
4,这样循环直到K个medoids固定下来。
这种算法对于脏数据和异常数据不敏感,但计算量显然要比K均值要大,一般只适合小数据量。
编辑本段Clara算法
上面提到K-medoids算法不适合于大数据量的计算。现在介绍Clara算法,这是一种基于采用的方法,它能够处理大量的数据。
Clara算法的思想就是用实际数据的抽样来代替整个数据,然后再在这些抽样的数据上利用K-medoids算法得到最佳的medoids。Clara算法从实际数据中抽取多个采样,在每个采样上都用K-medoids算法得到相应的(O1,O2…Oi…Ok),然后在这当中选取E最小的一个作为最终的结果。
编辑本段Clarans算法
Clara算法的效率取决于采样的大小,一般不太可能得到最佳的结果。
在Clara算法的基础上,又提出了Clarans的算法,与Clara算法不同的是:在Clara算法寻找最佳的medoids的过程中,采样都是不变的。而Clarans算法在每一次循环的过程中所采用的采样都是不一样的。与上面所讲的寻找最佳medoids的过程不同的是,必须人为地来限定循环的次数。
编辑本段聚类的用途
聚类的用途是很广泛的。在商业上,聚类可以帮助市场分析人员从消费者数据库中区分出不同的消费群体来,并且概括出每一类消费者的消费模式或者说习惯。它作为数据挖掘中的一个模块,可以作为一个单独的工具以发现数据库中分布的一些深层的信息,并且概括出每一类的特点,或者把注意力放在某一个特定的类上以作进一步的分析;并且,聚类分析也可以作为数据挖掘算法中其他分析算法的一个预处理步骤。聚类分析的算法可以分为划分法(Partitioning Methods)、层次法(Hierarchical Methods)、基于密度的方法(density-based methods)、基于网格的方法(grid-based methods)、基于模型的方法(Model-Based Methods)。
CLARA 算法的步骤(2006-11-28 10:47:10)转载标签: clara算法步骤 分类: 计算机的秘密

CLARA(Clustering LARge Applications,大型应用中的聚类方法)(Kaufmann and Rousseeuw in 1990):不考虑整个数据集, 而是选择数据的一小部分作为样本.
它从数据集中抽取多个样本集, 对每个样本集使用PAM, 并以最好的聚类作为输出
CLARA 算法的步骤:
(1) for i = 1 to v (选样的次数) ,重复执行下列步骤( (2) ~ (4) ) :
(2) 随机地从整个数据库中抽取一个N(例如:(40 + 2 k))个对象的样本,调用PAM方

法从样本中找出样本的k个最优的中心点。
(3)将这k个中心点应用到整个数据库上, 对于每一个非代表对象Oj ,判断它与从样本中选出的哪个代表对象最近.
(4) 计算上一步中得到的聚类的总代价. 若该值小于当前的最小值,用该值替换当前的最小值,保留在这次选样中得到的k个代表对象作为到目前为止得到的最好的代表对象的集合.
(5) 返回到步骤(1) ,开始下一个循环.
算法结束后,输出最好的聚类结果
优点: 可以处理的数据集比 PAM大
缺点:
1有效性依赖于样本集的大小
2基于样本的好的聚类并不一定是整个数据集的好的聚类, 样本可能发生倾斜
例如, Oi是整个数据集上最佳的k个中心点之一, 但它不包含在样本中, CLARA将找不到最佳聚类

相关文档
相关文档 最新文档