高维类别数据集的粗糙聚类算法的研究与应用

摘要

聚类分析是数据挖掘的重要技术之一，所处理的数据分为数值型、类别型和混合型。针对数值型数据，聚类算法已经取得了非常卓越的成果。而对于类别数据，由于不能进行传统意义上的几何距离计算，所以有很多问题需要解决:比如，设计合理的差异度函数，探求有效的聚类初始化机制。大数据时代出现了高维海量数据，其属性个数达到几十、几百乃至上千个，它们通常具有不完备、不精确、不一致性等特征，传统聚类算法很难满足这些数据的聚类需求，但是，不断丰富的数据带来了更多有价值的信息。如何从高维数据中发掘到有用的信息，已成为当今聚类分析领域最前沿的研究课题;其中，设计高维数据下的“距离”度量成为一项严峻的任务。针对高维聚类，目前最为常见的方法主要有维度约简和子空间聚类。维度约简是解决高维数据聚类分析的特别有效的方法，降维方法主要包括特征变换和特征选择，特征选择是数据挖掘中常见的降维技术。到目前为止，对类别型数据的初始化问题研究较少，如果初始类中心选择的不合理，不仅得不到最佳的聚类簇，还会增加算法的复杂度。特别是高维类别数据，初始类中心的选择尤为重要。目前仍然没有一种被广泛接受的针对类别数据的初始类中心选择算法。因此，为高维类别数据聚类提出一种初始类中心选择算法是非常必要的。经典粗糙集的扩展模型，能够很好地处理不完备的、不精确的、有噪声的数据集。将扩展粗糙集方法运用到高维不完备的数据集的处理中，已经取得了一些很好的聚类算法。
　　本文运用扩展的粗糙集模型----限制容差关系，对高维不完备的类别数据进行特征选择、设计聚类算法，主要工作包括以下两个部分：⑴针对高维类别不完备数据的特征选择:使用限制容差关系扩展粗糙集模型，重新定义信息熵以及条件信息熵，构造基于条件熵的高维类别不完备数据的维度约简算法CEHDAR。⑵基于加权重叠距离和加权平均密度的初始类中心选择算法:在算法中，我们使用限制容差关系的信息熵定义属性重要度，进而定义各属性的权重。在计算对象间的距离和对象的密度时，不同的属性被赋予相应的权重，从而体现不同属性对聚类贡献的不同。实验证明，相比于现有的聚类初始化方法，WDADI算法是最优的。

目录

声明

摘要

第1章 绪论

1．1 论文研究背景及意义

1．2 国内外研究现状

1．2．1 现有的高维类别数据粗糙降维的研究现状

1．2．2 现有的针对类别型数据的初始中心选择方法

1．3 论文的研究内容和组织结构

第2章 相关理论概述

2．1 聚类分析

2．1．1 聚类分析的基本概念

2．1．2 常用聚类方法及其特点

2．1．3 聚类分析的数据类型

2．1．4 经典聚类算法

2．2 高维数据的聚类分析

2．2．1 高维数据的特点

2．2．2 高维数据的聚类过程

2．2．3 维度约简

2．2．4 高维数据聚类算法

2．3 粗糙集理论及其扩展模型

2．3．1 粗糙集的基本概念

2．3．2 不完备信息系统产生的原因及其预处理

2．3．3 经典粗糙集理论的模型扩展

2．4 本章小结

第3章 基于条件熵的高维类别不完备数据的维度约简

3．1 限制容差关系下不完备信息系统的相关定义

3．2 基于条件熵的高维类别不完备数据的维度约简算法(CEHDAR算法)

3．3 实例分析

3．4 本章小结

第4章 一种新的初始类中心的选择算法

4．1 加权重叠距离

4．2 加权平均密度

4．3 WDADI算法

4．4 实验分析

4．5 本章小结

第5章 实验测试

5．1 实验环境及实验数据

5．2 实验设置

5．3 评价指标

5．4 实验

5．5 本章小结

第6章 总结与展望

参考文献

致谢

作者简介