高维分类属性的子空间聚类算法

《高维分类属性的子空间聚类算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、小型微型计算机系统2009年10月第1O期JournalofChineseComputerSystemsV0L30No．102oo9高维分类属性的子空间聚类算法单世民，王新艳，张宪超(大连理工大学软件学院，辽宁大连116621)E—mail：ssm@dlut．edu．cn摘要：高维分类数据的处理一直是数据挖掘研究所面临的巨大挑战．传统聚类算法主要针对低维连续性数据的聚类，难以处理高维分类属性数据集．本文提出一种处理高维分类数据集的子空间聚类算法(FP—Tree—basedSUBspaeeclusteringalgorithm，FPSUB)，利用频繁模式树将聚

2、类问题转化为寻找属性值的频繁模式发现问题，得到的频繁模式即候选子空间，然后基于这些子空间进行聚类．针对真实数据集的实验结果表明，FPSUB算法比其他算法具有更高的准确度．关键词：分类属性；子空间聚类；频繁模式；FP一树中图分类号：TP301．6文献标识码：A文章编号：1000-1220(2009)10-2016-06ClusteringAlgorithmforMiningSubspaceClustersinCategoricalDatasetsSHANShi—rain，WANGXin—yan。ZHANGXian-chao(SchoolofSoftware，D

3、alianUniversityofTechnology，Dalian116621，China)Abstract．High·dimensionalcategoricaldatasetsplayanimportantrole，SOitSsignificanttoclusterthesedatasets．However，tradi-tionalclusteringalgorithmsmainlyaimatlower—dimensionalcontinuousdatasets，whereastheyaredifficulttodealwithcategoricald

4、atasets．Anewsubspaceclusteringalgorithm—FPSUBisproposed．ItstorestheinformationofdatasetswitllaFP-framework．whichtransformsclusteringclustersintofindingthefrequentpatterns．andthenuti~zesthemtoclustertheobjects．111eexperimentre-suitsdemonstratethefeasibilityandrobustnessofthisalgorit

5、hm．Keywords：categoricaldata；subspaceclustering；frequent—pattern；FP·Tre1引言聚类方法过多依赖于距离矩阵的问题，基于”相似簇比相异簇具有更小的熵值”，提出了COOLCAT算法．DarshitPar-聚类作为数据挖掘的一个重要领域，已经被广泛探讨与mar等针对聚类过程中出现的不确定性问题，利用模糊集合研究．之前对分类数据的工作主要关注于二进制或事务型的理论的思想，提出了MMRL9算法，从而实现对分类数据集的数据集l1．2J，或将高维分类数据集进行压缩的架构j，或利用聚类．超图对聚类项集进行分离

6、j．传统聚类算法并不适用于高维以上算法均从全维数据空间对数据进行分析，针对数据分类数据集，因为传统的距离测量方式不再适用于高维环境维数变化的可伸缩性较差，广泛的研究证明””，在高维数下的分类数据，在高维数据空间上，对象之间的距离亦变得几据集中，有很多聚类结果在全维属性空间中并不相似，但在某乎等同．因此，高维分类属性的聚类问题得到了研究学者的广些属性子集空间中，却具有很高的相似性．包括前述算法的全泛关注母。．维聚类算法都不能发现这种隐含在属性子集上的聚类，因此，已有工作大都在全维空间下处理高维分类属性聚类问研究者提出并开展了子空间聚类算法的相关研究．题．针对传

7、统聚类算法只能处理连续性数据的问题，GantiV，最先出现的是AgrawalR等人提出的CLIQUE-l算法．GuhaS及AndritsosP等人分别提出了不同的处理方法．GantiCLIQUE算法依赖于有序的密集网格区域，将连续性数据进V等采用分类数据集的摘要信息进行聚类，提出了CAC—行离散化，然而分类数据不存在有序性，因此无法处理分类属TUS算法．GuhaS等使用两条记录之间链接数目来衡量记性数据．而后续出现的子空间聚类算法，如DOC-l，PRO-录之间的相似度，提出了ROCK_6算法．此算法为凝聚层次聚CLUS【】，ORCLUSIJ。等，均需要进行数

8、值统计计算(如中类算法，时间复杂度为数据数量的立方级