各种聚类算法及改进算法的研究

各种聚类算法及改进算法的研究 各种聚类算法及改进算法的研究 各种聚类算法及改进算法的研究

论文关键词:数据挖掘;聚类算法;聚类分析

论文摘要:该文详细阐述了数据挖掘领域的常用聚类算法及改进算法,并比较分析了其优缺点,提出了数据挖掘对聚类的典型要求,指出各自的特点,以便于人们更快、更容易地选择一种聚类算法解决特定问题和对聚类算法作进一步的研究。并给出了相应的算法评价标准、改进建议和聚类分析研究的热点、难点。上述工作将为聚类分析和数据挖掘等研究提供有益的参考。

1 引言

随着经济社会和科学技术的高速发展,各行各业积累的数据量急剧增长,如何从海量的数据中提取有用的信息成为当务之急。聚类是将数据划分成群组的过程,即把数据对象分成多个类或簇,在同一个簇中的对象之间具有较高的相似度,而不同簇中的对象差别较大。它对未知数据的划分和分析起着非常有效的作用。通过聚类,能够识别密集和稀疏的区域,发现全局的分布模式,以及数据属性之间的相互关系等。为了找到效率高、通用性强的聚类方法人们从不同角度提出了许多种聚类算法,一般可分为基于层次的,基于划分的,基于密度的,基于网格的和基于模型的五大类。

2 数据挖掘对聚类算法的要求 3 各种聚类算法介绍

随着人们对数据挖掘的深入研究和了解,各种聚类算法的改进算法也相继提出,很多新算法在前人提出的算法中做了某些方面的提高和改进,且很多算法是有针对性地为特定的领域而设计。某些算法可能对某类数据在可行性、效率、精度或简单性上具有一定的优越性,但对其它类型的数据或在其他领域应用中则不一定还有优势。所以,我们必须清楚地了解各种算法的优缺点和应用范围,根据实际问题选择合适的算法。

3.1 基于层次的聚类算法

基于层次的聚类算法对给定数据对象进行层次上的分解,可分为凝聚算法和分裂算法。

(2)自顶向下分裂聚类方法。与凝聚法相反,该法先将所有对象置于一个簇中,然后逐渐细分为越来越小的簇,直到每个对象自成一簇,或者达到了某个终结条件。其主要思想是将那些成员之间不是非常紧密的簇进行分裂。跟凝聚式方法的方向相反,从一个簇出发,一步一步细化。它的优点在于研究者可以把注意力集中在数据的结构上面。一般情况下不使用分裂型方法,因为在较高的层很难进行正确的拆分。

3.2 基于密度的聚类算法

很多算法都使用距离来描述数据之间的相似性,但对于非凸数据集,只用距离来描述是不够的。此时可用密度来取代距离描述相似性,即基于密度的聚类算法。它不是基于各种各样的距离,所以能克服基于距离的算法只能发现“类圆形”的聚类的缺点。其指导思想是:只要一个区域中的点的密度(对象或数据点的数目)大过某个阈值,就把它加到与之相近的聚类中去。该法从数据对象的分布密度出发,把密度足够大的区域连接起来,从而可发现任意形状的簇,并可用来过滤“噪声”数据。常见算法有DBSCAN,DENCLUE等。

3.3 基于划分的聚类算法 3.4 基于网格的聚类算法

首先将数据空间量化为有限个单元的网格结构,然后对量化后的单个的单元为对象进行聚类。典型的算法有STING,CLIQUE等。网格聚类法处理速度快,处理时间与数据对象的数目无关,一般由网格单元的数目决定。缺点是只能发现边界是水平或垂直的聚类,不能检测到斜边界。该类算法也不适用于高维情况,因为网格单元的数目随着维数的增加而呈指数增长。另外还有下列问题: 一是如何选择合适的单元大小和数目,二是怎样对每个单元中对象的信息进行汇总,三是存在量化尺度的问题。

3.5 基于模型的聚类算法

基于模型的方法给每一个聚簇假定了一个模型,然后去寻找能够很好满足这个模型的数据集。这个模型可能是数据点在空间中的密度分布函数,它由一系列的概率分布决定,也可能通过基于标准的统计数字自动决定聚类的数目。它的一个潜在假定是:目标数据集是由一系列的概率分布所决定的。一般有2种尝试方向:统计的方案和神经网络的方案。COBWEB是一种流行的简单增量概念聚类算法,以一个分类树的形式来创建层次聚类,它的输入对象用分类属性-值对来描述。COBWEB的优点为:可以自动修正划分中类的数目;不需要用户提供输入参数。缺点为:COBWEB基于这样一个假设:在每个属性上的概率分布是彼此独立的。但这个假设并不总是成立。且对于偏斜的输入数据不是高度平衡的,它可能导致时间和空间复杂性的剧烈变化,不适用于聚类大型数据库的数据。

3.6 模糊聚类算法 3.6.1 模糊C-均值聚类算法

FCM算法用隶属度确定每个样本属于某个聚类的程度。它与K平均算法和中心点算法等相比,计算量可大大减少,因为它省去了多重迭代的反复计算过程,效率将大大提高。同时,模糊聚类分析可根据数据库中的相关数据计算形成模糊相似矩阵,形成相似矩阵之后,直接对相似矩阵进行处理即可,无须多次反复扫描数据库。根据实验要求动态设定m值,以满足不同类型数据挖掘任务的需要,适于高维度的数据的处理,具有较好的伸缩性,便于找出异常点。但m值根据经验或者实验得来,具有不确定性,可能影响实验结果。并且,由于梯度法的搜索方向总是沿着能量减小的方向,使得算法存在易陷入局部极小值和对初始化敏感的缺点。为克服上述缺点,可在FCM算法中引入全局寻优法来摆脱FCM聚类运算时可能陷入的局部极小点,优化聚类效果。

3.6.2 免疫进化算法

该算法借鉴生命科学中的免疫概念和理论在保留原算法优良特性的前提下,力图有选择、有目的地利用待求问题中的一些特征或知识来抑制其优化过程中出现的退化现象。免疫算法的核心在于免疫算子的构造,通过接种疫苗或免疫选择两个步骤来完成。免疫进化算法能提高个体的适应度和防止群体的退化,从而达到减轻原有进化算法后期的波动现象和提高收敛速度。例如IFCM、IFCL算法。它们既较大地提高了获取全局最优的概率,又减轻了基于遗传聚类算法在遗传后期的波动现象。进一步的工作是参数的适当选取和减小运行时间等。人对于客观事物的识别往往只通过一些模糊信息的综合,便可以获得足够精确的定论。

3.7 其它聚类算法

3.7.1 基于群的聚类方法

该法是进化计算的一个分支,模拟了