子空间聚类改进算法研究综述

《子空间聚类改进算法研究综述》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第27卷第5期计算机仿真2010年5月文章编号：1006—9348(2010)05—0174—04子空间聚类改进算法研究综述李霞，徐树维(1．同济大学建筑与城市规划学院，上海200092；2．河南大学计算中心，河南开封475001)摘要：高维数据聚类是聚类技术的难点和重点，子空问聚类是实现高维数据集聚类的有效途径。CLIQUE算法是最早提出的基于密度和网格的子空间聚类算法，自动子空间聚类算法的实用性和高效性，带来了子空间聚类算法的空前发展。深入分析CLIQUE算法的优点和局限性；介绍了一些近几年提出的子空间聚类算法，并针对CLIQUE算法的局限性作了改进，聚类的效率和精确性得到了提高；最后对

2、子空间聚类算法的发展趋势进行了讨论。关键词：数据挖掘；聚类；高位数据集；子空间中图分类号：TP311文献标识码：ASummaryofSubspaceClusteringAlgorithmsResearchBasedonCLIQUELIXiaII．XUShu—wel(1．CollegeofArchitectureandUrbanPlanning，TongjiUniversity，Shanghai200092，China；2．ComputerCenter，HenanUniversity，KaifengHenan475001，China)ABSTRACT：Theclusteringofhighdi

3、mensionaldataisakeyprobleminclusteringmethods．Subspaceclusteringisaneffectiveapproachtorealizeclusteringinhighdimensionaldata．Asapioneerdensityandgridbasedclusteringal·gorithm，CLIQUEalgorithmhas，withitspracticalityandhighefficiency，greatlyfacilitatedthedevelopmentofsub—spaceclusteringalgorithm．?Thi

4、spaper?analyzesindepththeadvantagesandlimitationsofCLIQUEalgorithmandintroducesseveralsubspaceclusteringalgorithms?putforwardinrecentyearswhichhaveallbeen?updatedto?ad—dressthelimitationsofCLIQUEalgorithmandthereforeimprovedtheeficiencyandaccuracyforclustering．?Inad—dition，thispaperalsodiscussesthe

5、developmenttrendofsubspaceclusteringalgorithm．KEYWORDS：Datamining；Clustering；Highdimensionaldatasets；Subspace1引言SCAN等。由于高维数据的稀疏性、空空间现象以及维度所谓聚类，就是将一个数据集中的数据进行分组，使得效应的影响，在高维数据空间中使用传统算法会遇到以下问每一组内的数据尽可能相似而不同组内的数据尽可能不同。题：①随着维数增长，聚类的时间和空间复杂度迅速上升从聚类分析是一项重要的研究课题，在数据挖掘、模式识别、统而导致算法的性能下降；②高维数据集中存在大量无关的属计数据分析、

6、自然语言理解等领域都有广泛的应用前景。聚性，并且在这些不相关的维上十分稀疏，这就使得在所有维类分析同时也是一个具有很强挑战性的领域，它的一些潜在中存在簇的可能性几乎为零，所以传统的聚类算法不适合对应用对算法提出了特别的要求⋯：可扩展性、处理不同数据高维数据进行聚类；③距离函数难于定义，聚类操作的基础类型的能力、发现具有任意形状的聚类的能力、输人参数对是数据对象之间相似性的度量，相似度高的对象归为一类。领域知识的最小限度的依赖性、能够处理异常数据的能力、但在高维情况下距离函数失效，因此必须通过重新定义合适数据输入顺序对聚类结果的不敏感性、处理高维数据的能的距离函数或相似性度量函数以避开“维度效

7、应”的影响。力、基于约束的聚类以及聚类结果的可解释性和可用性。子空间聚类是针对大规模高维数据聚类的有效方法。迄今为止，仅仅数据库界的研究人员就已经提出了不少近年来，国内外的研究大多集中在算法的创新与改进，提出数据聚类算法，比较著名的有CLARANS、BIRCHJ、DB一了众多的子空间聚类算法，很少有研究者对这些算法作细致的比较和分析。本文从最具代表性的CLIQUE算法人手，以基金项目：河南省教育厅自然科学研究