论文研究-高维分类属性的子空间聚类算法 .pdf
需积分: 14 104 浏览量
2019-08-15
15:38:14
上传
评论 1
收藏 394KB PDF 举报
http://www.paper.edu.cn
- 1 -
高维分类属性的子空间聚类算法
1
王新艳
大连理工大学软件学院，大连(116620)
E-mail：xinyan20001@163.com
摘 要：高维分类数据的处理一直是数据挖掘研究所面临的巨大挑战。传统聚类算法主要针
对低维连续性数据的聚类，难以处理高维分类属性数据集。本文提出了一种处理高维分类数
据集的子空间聚类算法(FPSUB)。它利用 FP-Tree 结构存储数据集的所有信息，将聚类问题
转化为寻找属性值的频繁模式问题，得到的频繁模式即候选子空间，然后基于这些子空间进
行聚类。本文利用该算法在真实数据集上进行了实验，实验结果表明，该算法比其他算法具
有更高的准确度。
关键词：分类属性；子空间聚类；频繁模式；FP-树
中图分类号：TP311
1. 引言
聚类作为数据挖掘的一个重要领域，已经被广泛探讨与研究。之前对分类数据的工作主
要关注于二进制或事务型的数据集
[1,2]
，或将高维分类数据集进行压缩的架构
[3]
，或利用超图
对聚类项集进行分离
[4]
。传统聚类算法并不适用于日益庞大的高维分类数据集，这是因为传
统的距离测量方式不再适用于分类数据，并且在高维数据空间上，对象之间的距离变得几乎
等同。从而研究者针对高维分类数据提出了许多聚类算法
[5-9]
。
Ganti V 等针对传统聚类算法只能处理连续性数据，并且未能给定分类属性数据集的聚
类定义等问题，采用分类数据集的摘要信息进行聚类的思想，提出了 CACTUS
[5]
算法。Barbara
D 等针对大多数对分类属性数据集进行聚类的算法过多依赖于距离矩阵使用的问题，基于
“相似簇比相异簇具有更小的熵值”的思想，提出了 COOLCAT
[6]
算法，是一种增量的启发式
算法。Andritsos P 等同样针对传统聚类算法只能处理连续性数据的问题，采用基于信息瓶颈
框架的一种最近信息理论，提出了 LIMBO
[7]
聚类算法，是一种可伸缩的层次性的分类聚类
算法。Guha S 等针对传统聚类算法利用数据点间距离表示对象相似性的理论不适用于二进
制和分类数据集的问题，采用基于两条记录之间链接的数目来衡量记录之间的相似度，链接
表示了与该记录足够相似的记录数目的思想，提出了 ROCK
[8]
算法，它是一种凝聚的层次聚
类算法。该算法的时间复杂度是立方级的，不适合处理大型数据集。Darshit Parmar 等针对
聚类过程中出现的不确定性问题，利用模糊集合理论的思想，提出了 MMR
[9]
算法，从而实
现对分类数据集的聚类。
但是这些算法均从全维数据空间对数据进行分析，算法的可伸缩性较差，通过广泛的研
究证明，在分类数据集，尤其是高维分类数据集中，有很多聚类结果在全维属性空间中可能
是不相似的，但在属性子集空间中，它们却具有很高的相似性，然而这些聚类算法都不能发
现隐含在属性子集上的聚类结果，从而提出了子空间聚类算法。
Agrawal R 等人首先在 CLIQUE
[10]
中提出子空间聚类算法的思想,随后在
[11-13]
中也提到
了几个子空间聚类算法。算法 CLIQUE
[10]
依赖于有序的密集区域，将连续性数据进行离散
化，然而分类数据不存在这样的序列。算法 DOC
[11]
，PROCLUS
[12]
，ORCLUS
[13]
需要进行
数值计算（如中值，均值，方差等），也不适用于分类数据集。这些算法仅能处理连续性数
据，却不能处理分类数据集，将它们用于处理分类数据会有几个很难克服的问题。
1
本课题得到国家自然科学基金项目(70671016)、国家自然科学基金项目(60673066)的资助。
评论0
最新资源