面向不确定数据的近似骨架启发式聚类算法

摘要

不确定数据聚类是传统数据挖掘的扩展，具有广泛的应用背景和研究价值，受到研究者们广泛的关注。不确定数据聚类问题属于典型的NP难解问题，并表现出了典型的NP难解问题的特点。通常很难在多项式时间内获得NP难解问题的全局最优解，研究者们经常把聚类问题描述成组合优化问题，并设计启发式聚类算法对不确定数据聚类进行求解。现有的启发式不确定数据聚类算法中，UK-means和UK-Med oids算法都属于基于切割不确定数据聚类算法，它们具有容易理解和实现简单等特点，得到广泛的关注和应用，但同时它们也具有对初始解敏感的缺点，这严重影响了聚类质量。为了解决基于切割的不确定数据算法对初始解敏感的问题，本文深入研究了不确定数据聚类问题表现出的NP难解性质，分析了该问题的解空间的特征，并在近似骨架理论的基础上，提出了一种近似骨架启发式聚类算法APPGCU(APProximate backbone Guided heuristic Clustering algorithm for Uncertaindata)。该算法流程如下:首先对原不确定数据集完成M次采样，在采样后的规模较小的M个不确定数据集上分别执行随机初始簇心的UK-Medoids算法得到M个局部最优解;然后通过对M个局部最优解求交集得到近似骨架，并从中提取出初始簇心;最后从初始簇心开始，使用UK-Medoids算法启发式搜索出聚类结果。该算法充分利用了近似骨架在启发式算法设计中表现出的优异性能，根据不确定数据聚类的特点设计了高效聚类算法。在充足的仿真和实际数据集中的实验结果表明，算法APPGCU的聚类结果明显高于现有的不确定数据启发式聚类算法，提高了聚类结果的质量。

目录

声明

摘要

1 绪论

1．1 背景知识

1．2 本文工作

1．3 本文组织结构

2 不确定数据模型

2．1 包含概率型记录的数据库定义

2．2 简化的不确定数据模型

3 不确定数据聚类介绍

3．1 基于切割的不确定数据聚类算法

3．2 基于密度的不确定数据聚类算法

3．2 不确定数据聚类的NP难解性质

4 骨架结构分析

4．1 骨架结构的应用分析

4．2 骨架结构的基本概念

4．3 骨架结构的获取方法和应用分析

5 不确定数据聚类问题中的骨架结构分析

5．1 不确定数据聚类的特点

5．2 基于不确定数据的近似骨架定义

6 面向不确定数据的近似骨架启发式聚类算法

6．1 数据集采样

6．2 算法框架

6．2．1 近似骨架发现算法

6．2．2 初始解生成算法

6．2．3 APPGCU算法框架

7 实验设计和结果分析

7．1 不确定数据集

7．1．1 人工不确定数据集的生成

7．1．2 标准UCI不确定数据集的生成

7．2 对比算法

7．3 结果及分析

结论

参考文献

攻读硕士学位期间发表学术论文情况

致谢