高维混合类型数据聚类算法研究

论文摘要

在很多领域中，用于数据挖掘的数据集通常具有较高的维度。现有大多数经典聚类算法在较低维度运行时效果很好，但是，随着维度的增加，性能和效率就会明显的下降，因为算法的复杂度随着数据集维数的增加而成指数级增长；另一方面，目前的聚类算法大都是处理数值型的数据，对于混合类型数据的处理效果往往不佳，因此，亟需寻找一种新的有效的聚类算法。然而国内外对适用于高维混合类型数据集的聚类算法的研究非常匮乏，为了解决这种高维混合类型数据集的聚类问题，必须从理论上及算法上对聚类算法进行研究。为了研究高维混合类型数据的聚类问题，首先，对数据对象间的最大距离和平均距离随维数增加的变化进行了实验，得出了变化趋势：当数据集的维数小于30的时候，最大距离和平均距离增加的比较快；当数据集的维数大于30的时候，最大距离和平均距离增加的比较慢，甚至趋向于直线，曲线有一个拐点，即维数=30。最大距离和平均距离随维数的增加而增大表明数据对象间的距离随维数的增加而增大。其次，对聚类算法的聚类精度随数据维数增加的变化进行了实验，得出了维数对聚类算法精度的影响：当数据集的维数小于30的时候，聚类算法的性能很好，当数据集的维数大于30的时候，聚类算法的精度随维数的增加而降低。实验结果表明：当数据集的维数小于30的时候，像K-means和层次聚类算法这种基于距离的聚类算法是有效的，但是当维数大于30的时候它们的聚类结果很不理想。再次，提出了一种新方法把混合类型数据里的非数值属性的值转化成数值型，使得K-means、层次聚类、基于密度和自适应密度可达聚类算法（ClusteringAlgorithm Based on Density and Density reachable, CADD）等聚类算法能够对混合类型的数据进行聚类。实验结果证明，此方法能有效地使聚类算法对混合类型的数据进行聚类，尤其是CADD的聚类效果更好。最后，对基于密度和自适应密度可达聚类算法（Clustering Algorithm Based onDensity and Density reachable, CADD）的相异度公式进行了改进：利用复相关系数的倒数作为权值为相异度公式加权。实验结果证明，改进后的算法能够有效处理高维数据。另外，将复相关系数的倒数赋权法作为一种特征选择方法为数据集降维，并验证了此方法的有效性。

论文目录

• 摘要
• Abstract
• 引言
• 1 绪论
• 1.1 课题研究背景
• 1.2 课题研究现状及意义
• 1.3 课题主要工作
• 1.4 论文的结构和组织
• 2 数据挖掘技术
• 2.1 数据挖掘定义
• 2.2 数据挖掘系统的组成
• 2.3 数据挖掘的具体实施步骤
• 2.4 数据挖掘对聚类分析的要求
• 2.5 数据挖掘的应用
• 2.6 小结
• 3 高维混合类型数据聚类技术分析
• 3.1 聚类分析的数据基础
• 3.1.1 数据属性
• 3.1.2 聚类分析的数据结构
• 3.1.3 不同变量的相异度计算方式
• 3.2 主要的聚类算法
• 3.2.1 基于划分的方法
• 3.2.2 基于层次的方法
• 3.2.3 基于密度的方法
• 3.2.4 基于网格的方法
• 3.2.5 基于模型的方法
• 3.3 高维数据的处理方法
• 3.3.1 属性转换
• 3.3.2 子空间聚类
• 3.3.3 协同聚类
• 3.4 混合类型数据的处理方法
• 3.5 小结
• 4 维数对聚类算法精度影响的实验研究
• 4.1 高维聚类
• 4.2 聚类算法和数据集
• 4.2.1 聚类算法
• 4.2.2 实验数据集
• 4.2.3 相关定义
• 4.3 实验结果及分析
• 4.3.1 维数对数据对象间距离的影响
• 4.3.2 维数对算法聚类精度的影响
• 4.3.3 降维实验
• 4.4 小结
• 5 高维混合类型数据聚类算法的设计与实现
• 5.1 混合类型数据聚类算法的设计与实现
• 5.1.1 聚类算法
• 5.1.2 处理混合类型数据的方法
• 5.1.3 度量标准
• 5.1.4 实验结果及分析
• 5.2 高维数据聚类算法的设计与实现
• 5.2.1 CADD 算法的整体思路
• 5.2.2 相关的定义
• 5.2.3 CADD 算法描述
• 5.2.4 CADD 算法的改进
• 5.2.5 实验结果及分析
• 5.3 小结
• 结论
• 参考文献
• 在学研究成果
• 致谢