基金项目:河南省教育厅自然科学研究计划项目(2009B50004收稿日期:2009-03-21修回日期:2009-04-29第27卷第5期计算机仿真2010年5月文章编号:1006-9348(201005-0174-04子空间聚类改进算法研究综述李霞1,2,徐树维2(1.同济大学建筑与城市规划学院,上海200092;2.河南大学计算中心,河南开封475001摘要:高维数据聚类是聚类技术的难点和重点,子空间聚类是实现高维数据集聚类的有效途径。CLIQUE算法是最早提出的基于密度和网格的子空间聚类算法,自动子空间聚类算法的实用性和高效性,带来了子空间聚类算法的空前发展。深入分析CLIQUE算法的优点和局限性;介绍了一些近几年提出的子空间聚类算法,并针对CLIQUE,聚类的效率和精确性得到了提高;关键词:数据挖掘;聚类;高位数据集;子空间中图分类号:TP311文献标识码:AingAlgorithmsResearchBasedonCLIQUELIXia1,2,XUShu-wei2(1.CollegeofArchitectureandUrbanPlanning,TongjiUniversity,Shanghai200092,China;2.ComputerCenter,HenanUniversity,KaifengHenan475001,ChinaABSTRACT:Theclusteringofhighdimensionaldataisakeyprobleminclusteringmethods.Subspaceclusteringisaneffectiveapproachtorealizeclusteringinhighdimensionaldata.Asapioneerdensityandgridbasedclusteringal2gorithm,CLIQUEalgorithmhas,withitspracticalityandhighefficiency,greatlyfacilitatedthedevelopmentofsub2spaceclusteringalgorithm.?Thispaper?analyzesindepththeadvantagesandlimitationsofCLIQUEalgorithmandintroducesseveralsubspaceclusteringalgorithms?putforwardinrecentyearswhichhaveallbeen?updatedto?ad2dressthelimitationsofCLIQUEalgorithmandthereforeimprovedtheefficiencyandaccuracyforclustering.?Inad2dition,thispaperalsodiscussesthedevelopmenttrendofsubspaceclusteringalgorithm.KEYWORDS:Datamining;Clustering;Highdimensionaldatasets;Subspace1引言所谓聚类,就是将一个数据集中的数据进行分组,使得每一组内的数据尽可能相似而不同组内的数据尽可能不同。聚类分析是一项重要的研究课题,在数据挖掘、模式识别、统计数据分析、自然语言理解等领域都有广泛的应用前景。聚类分析同时也是一个具有很强挑战性的领域,它的一些潜在应用对算法提出了特别的要求[1]:可扩展性、处理不同数据类型的能力、发现具有任意形状的聚类的能力、输入参数对领域知识的最小限度的依赖性、能够处理异常数据的能力、数据输入顺序对聚类结果的不敏感性、处理高维数据的能力、基于约束的聚类以及聚类结果的可解释性和可用性。迄今为止,仅仅数据库界的研究人员就已经提出了不少数据聚类算法,比较著名的有CLARANS[2]、BIRCH[3]、DB2SCAN[4]等。由于高维数据的稀疏性、空空间现象以及维度效应的影响,在高维数据空间中使用传统算法会遇到以下问题:①随着维数增长,聚类的时间和空间复杂度迅速上升从而导致算法的性能下降;②高维数据集中存在大量无关的属性,并且在这些不相关的维上十分稀疏,这就使得在所有维中存在簇的可能性几乎为零,所以传统的聚类算法不适合对高维数据进行聚类;③距离函数难于定义,聚类操作的基础是数据对象之间相似性的度量,相似度高的对象归为一类。但在高维情况下距离函数失效,因此必须通过重新“”定义合适的距离函数或相似性度量函数以避开维度效应的影响。子空间聚类是针对大规模高维数据聚类的有效方法。近年来,国内外的研究大多集中在算法的创新与改进,提出了众多的子空间聚类算法,很少有研究者对这些算法作细致的比较和分析。本文从最具代表性的CLIQUE算法入手,以对CLIQUE算法局限性的改进为基础,将近年来提出的新的子空间聚类算法进行了分类介绍和分析。这些分析研究对—471—今后进一步改进CLIQUE算法以及提出新的子空间聚类算法提供了依据和指导。2子空间聚类算法CLIQUE2.1算法分析对于高维空间,由于点在空间中的分布比较分散,不太容易形成支持度较高的聚类。所以考虑在某一个子空间中执行聚类分析的任务,而那个子空间会成为要分析的对象,聚类也只能在从低维到高维的迭代过程中自动产生的。为了使计算点的密度的方法简单一些,将数据...