子空间聚类改进方法研究

论文摘要

聚类分析作为数据挖掘的核心任务,具有广泛的应用领域。研究人员根据不同应用提出了大量算法,其中包括划分方法、层次方法、基于网格的方法、基于密度的方法等。目前,大规模、高维数据集的聚类算法是聚类分析领域的热点和难点之一。由于高维数据的稀疏性,传统聚类算法在对高维数据聚类时不能获得理想效果。子空间聚类算法致力于解决传统聚类算法在对高维数据聚类时遇到的困难,是聚类算法的一个新的分支。高维数据的聚类是聚类算法能否适用于更多领域的关键,子空间聚类是实现高维数据聚类的有效途径,它是在高维数据空间中对传统聚类算法的一种扩展,其思想是将搜索局部化在相关维中进行,代表性算法包括CLIQUE、SUBCLU等。在真实数据集中随着数据维数的不同,子空间的密集程度也有所不同,而上述的子空间聚类算法在分析真实高维数据集时效果往往不令人满意,同时由于处理数据类型的单一性上述算法难以解决实际问题。为解决上述难题,本文通过对几种子空间聚类算法的分析研究,提出了一种基于k最相似聚类的子空间聚类算法-KSCSCfSubspace Clustering Base on K-most SimilarCluster)。算法使用一种新的聚类间相似度度量方法,通过保留k最相似聚类来确定子空间搜索方向,并将子空间聚类算法处理的数据类型扩展到连续型数据和分类型数据。算法针对以往子空间聚类算法采用全局密度阈值导致算法伸缩性不好以及聚类准确度不高的问题,在不同的子空间上采用不同的局部密度阈值,更加符合真实数据集的实际分布情况,在保持了子空间聚类算法优点的同时,避免了其他算法主观地给定参数所具有的缺陷。理论分析和基于不同数据集的实验证明,KSCSC算法能够有效地处理高维数据集和分类数据集聚类的问题,并且其聚类效果优于CLIQUE、SUBCLU和ROCK算法。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 研究背景及意义
• 1.2 国内外研究现状
• 1.3 本文研究内容及组织
• 2 聚类问题
• 2.1 聚类的定义及构成
• 2.2 样本表示
• 2.3 相似性度量
• 2.3.1 区间标度型
• 2.3.2 二元型和标称型
• 2.3.3 序数型
• 2.3.4 比例标度型
• 2.3.5 混合型
• 2.4 聚类算法
• 2.4.1 层次方法
• 2.4.2 划分方法
• 2.4.3 基于密度的算法
• 2.4.4 基于网格的算法
• 2.5 聚类评价
• 3 子空间聚类算法研究
• 3.1 高维数据聚类
• 3.1.1 高维数据的特点
• 3.1.2 数据稀疏性
• 3.1.3 维度效应
• 3.1.4 高维数据对传统聚类算法的影响
• 3.1.5 特征选择
• 3.1.6 特征变换
• 3.1.7 子空间聚类的必要性
• 3.2 子空间聚类算法研究
• 3.2.1 子空间聚类原理
• 3.2.2 CLIQUE算法
• 3.2.3 PROCLUS算法
• 3.2.4 SUBCLU算法
• 4 基于k最相似聚类的子空间聚类算法
• 4.1 子空间聚类算法的改进
• 4.1.1 子空间聚类算法性能分析
• 4.1.2 经典子空间聚类算法的优点
• 4.1.3 经典子空间聚类算法的缺陷
• 4.1.4 子空间聚类的改进方向
• 4.2 相关概念
• 4.2.1 子空间聚类
• 4.2.2 问题描述
• 4.3 算法描述
• 4.3.1 算法框架
• 4.3.2 基本聚类计算
• 4.3.3 基本聚类间相似度计算
• 4.3.4 k最相似聚类计算
• 4.3.5 子空间聚类
• 4.3.6 局部密度阈值的选取
• 4.3.7 子空间搜索
• 4.3.8 子空间合并
• 4.3.9 处理剩余数据点
• 4.3.10 参数确定
• 4.4 复杂度分析
• 5 实验验证
• 5.1 实验设置
• 5.2 实验数据集
• 5.3 结果评价
• 5.3.1 算法精确度
• 5.3.2 算法伸缩性
• 5.3.3 参数对算法准确度的影响
• 参考文献
• 攻读硕士学位期间发表学术论文情况
• 致谢