高维数据聚类若干关键问题研究

论文摘要

聚类的发展是分类学、社会科学、心理学、生物学、统计学、数学、计算机科学等多学科交叉融合的结果,不同聚类方法的区别主要在于对象之间相互关系定义的不同。经典的聚类方法大多是针对低维数据设计的,当数据的维度很高时,原有的聚类方法将面临严峻的挑战,且其在高维空间中的聚类结果是难以预料的。论文围绕高维数据聚类算法展开,指明了为使传统聚类方法适用于高维空间的改进方向,并从高维数据相似性度量和降维两个方面进行研究,提出了合理的解决方法,具有一定的理论和现实指导意义。论文主要研究内容和创新点如下:现有的高维聚类算法中对象间的距离大多采用欧氏距离进行度量,但由于“维度效应”,传统的Lk—范数在高维空间已不适用。为了合理度量高维空间各对象间的距离或相似性,解决基于Lk—范数的距离失效问题,可以对距离或相似性度量函数进行重新设计,即重构距离或相似性度量。重构的距离或相似性度量函数,不仅要在高维空间中具有意义,同时也要方便计算。2.对利用区间划分进行高维数据相似性度量的方法进行了扩展,使各维数据在根据其分布直方图进行初始等分后,将满足相应阈值范围的邻近区间进行合并,获得最终符合数据本身分布特征的不等距区间划分,提出了基于不等距维区间划分的高维数据相似性度量函数。该函数不仅整合了不同类型数据的相似性度量,而且考虑了各数据对象间的相对距离。符合数据分布特征的不等距划分方法,改善了数据分布均匀或者十分倾斜时,以及噪声数据给高维数据相似性度量带来的影响。3.将高维空间中数据对象的二维映射过程(高维数据转化为二维数据,使二维空间中各对象间欧氏距离趋近于高维空间对象间最短路径距离)转化为优化问题,设计了利用遗传算法和RBF神经网络进行相似性保持的高维数据降维方法,并确定了高维数据到低维数据的映射关系。当有新对象输入时,利用映射关系可以快速有效地获取其低维坐标。在实际降维过程中,当数据量非常大时,为了提高遗传算法降维的效率,在原始高维空间中随机抽取若干高维数据对象进行交叉变异,获得其相应的降维后坐标,根据所抽取对象的(原高维坐标值,降维后坐标值)值对进行神经网络映射,获得降维转换器,并利用转换器计算原高维空间中未被抽取的数据对象的低维映射坐标值。4.设计并实现了基于改进相似性度量和特征变换的高维数据聚类算法。在聚类的初始阶段,利用降维后数据的可视化结果指导初始聚类中心和聚类个数的选取,有效提高了高维数据的聚类精度和速度。文中提出的改进高维数据聚类算法只要能够获取对象间的距离或相似度矩阵,便能方便的进行降维聚类,而不需重新设计和调整原有的聚类算法流程。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 数据挖掘的产生和发展
• 1.2 聚类及高维数据聚类
• 1.2.1 聚类的概念及基本方法
• 1.2.2 高维数据聚类的研究意义
• 1.2.3 高维数据聚类的研究瓶颈及面临的问题
• 1.3 论文内容和结构安排
• 第二章 高维数据聚类算法综述
• 2.1 高维聚类算法基础
• 2.2 高维聚类算法研究现状
• 2.2.1 典型的高维聚类算法
• 2.2.2 现有的改进高维聚类算法
• 2.3 高维聚类算法改进方向分析
• 2.3.1 高维空间相似性度量方法研究现状
• 2.3.2 高维空间特征选择方法研究现状
• 2.3.3 高维空间特征变换方法研究现状
• 2.4 本章小结
• 第三章 不等距划分的高维数据相似性度量方法研究
• 3.1 维度效应
• 3.2 高维空间相似性度量方法的重构
• 3.2.1 相似性度量函数Hsi m（ ）
• 3.2.2 相似性度量函数Gsim （ ）
• 3.2.3 相似性度量函数Hsimc （ ）
• d ） 和距离度量函数D （ X , Y ）'>3.2.4 相似性度量函数PIDist （ X , Y , k_d ） 和距离度量函数D （ X , Y ）
• 3.3 基于不等距划分的高维相似性度量方法
• 3.3.1 不等距划分
• 3.3.2 高维相似性度量
• 3.4 有效性分析
• 3.5 本章小结
• 第四章 基于相似性保持的高维数据降维
• 4.1 降维的定义和研究意义
• 4.2 基本理论
• 4.2.1 遗传算法
• 4.2.2 人工神经网络
• 4.3 基于相似性保持的高维数据降维分析
• 4.3.1 相似性保持和数据流形正确展开的特征变换
• 4.3.2 降维转换器的生成
• 4.4 基于相似性保持的高维数据降维可视化
• 4.4.1 iris 数据集降维可视化
• 4.4.2 zoo 数据集降维可视化
• 4.4.3 基于相似性保持的降维方法性能分析
• 4.5 本章小结
• 第五章 利用改进相似性度量和特征变换进行高维数据聚类
• 5.1 聚类
• 5.2 数据处理
• 5.3 基于改进相似性度量和特征变换的高维数据聚类算法
• 5.4 算法性能及有效性分析
• 5.4.1 仿真实验
• 5.4.2 实际应用分析
• 5.5 本章小结
• 第六章 总结与展望
• 6.1 本文研究成果
• 6.2 今后工作展望
• 参考文献
• 作者简历 攻读硕士学位期间完成的主要工作
• 致谢