基于区间数的不确定数据自适应聚类算法

摘要

受硬件设备精度制约或人为干扰等因素的影响，传感网络应用收集到的数据集往往具有不确定性。不确定数据无法使用确切的数值描述事物属性的状态，导致面向确定数据的聚类算法无法完成不确定数据的聚类任务。近年来，不确定数据聚类方法被陆续提出，但仍然存在以下问题：①运行效率。不确定数据聚类算法在计算不确定对象距离的过程中进行了大量无意义的实例距离计算，导致算法的运行效率不高。②聚类精度。不确定数据模型以及聚类过程中的相关概念破坏了不确定数据信息的完整性，导致聚类对象产生精度误差，算法的聚类精度下降。③自适应性。由于密度聚类算法在发现非球形簇方面的优势，基于密度的不确定数据聚类算法被陆续提出，但关于密度聚类算法的非自适应阈值问题始终没有得到很好的解决。区间数模型是不确定性决策分析常用的一种数据模型，它基于不确定数据的上限和下限描述属性可能值的概率分布情况，最大程度地保证了数据信息的完整性。因此，本文针对上述问题，开展基于区间数的不确定数据自适应聚类算法研究。主要工作包括：　　①本文提出了一种新的不确定数据聚类算法IN-DBSCAN（DBSCAN algorithm based on Interval Number model）。算法基于区间数模型描述不确定实例的数据分布信息，保证了数据信息的完整性；然后，算法设计了一种高效的距离计算策略来计算不确定对象之间的距离，提高了算法的运行效率；最后，算法重新定义了经典密度聚类算法DBSCAN（Density-Based Spatial Clustering of Applications with Noise）的相关概念，实现了不确定数据的密度聚类。　　②在IN-DBSCAN算法基础上，本文提出了自适应聚类的改进算法IN-DBSCANa（IN-DBSCAN adaptive algorithm）。算法首先提出使用最大直接可达概率替代IN-DBSCAN算法中的固定概率阈值，然后基于Gaussian-Means算法提出了密度参数自适应策略，有效避免了人为因素对聚类结果的影响，最终实现了算法的自动聚类。　　③本文测试了所提算法与UK-Means，MMVar，FDBSCAN，FOPTICS，KKL和REP共6种不确定数据聚类算法在合成数据集、真实基准数据集以及真实世界数据集上的性能表现。实验结果表明，本文所提算法的运行效率和聚类精度均优于现有不确定数据聚类算法，算法更具有竞争力。

目录

1 绪论

1.1 研究背景及意义

1.2 研究现状

1.3 研究内容

1.4 论文组织结构

1.5 本章小结

2 不确定数据聚类研究

2.1 不确定数据

2.1.1 数据的不确定性

2.1.2 不确定数据表现形式

2.1.3 不确定数据分析面临的挑战

2.2 不确定数据聚类

2.2.1 不确定数据聚类定义

2.2.2 不确定数据聚类流程

2.2.3 传统聚类算法

2.2.4 不确定数据聚类算法

2.3 本章小结

3 基于区间数的不确定数据聚类算法设计

3.1 问题描述

①不确定距离计算导致高时间复杂度

②代表对象造成不确定数据分布信息缺失

3.2 不确定数据的区间数模型

3.2.1 区间数模型构建

3.2.2 区间数距离计算

3.3.1 算法基本流程

3.3.2 算法相关定义

3.3.3 算法设计实现

3.4 算法性能分析

②聚类精度

3.5 本章小结

4 不确定数据聚类算法的自适应改进

4.1.1 问题描述

4.1.2 IN-DBSCAN算法的概率阈值自适应改进

4.2.1 问题描述

4.2.2 常见参数阈值自适应模型

4.2.3 IN-DBSCAN算法的参数阈值自适应改进

4.3 不确定数据自适应聚类算法

4.4 算法性能分析

②聚类精度

4.5 本章小结

5 实验评估

5.1 实验环境

5.2 实验数据

5.2.1 合成数据集

5.2.2 真实基准数据集

5.2.3 真实世界数据集

5.3 实验评价指标

5.4 对比的基准算法

5.5 实验基础设置

5.6.1 运行效率比较

5.6.2 聚类精度比较

5.7 本章小结

6 总结与展望

参考文献

附录

A. 作者在攻读硕士学位期间发表的论文目录

B. 作者在攻读硕士学位期间发表的发明专利

C. 作者在攻读硕士学位期间得奖情况

D. 作者在攻读硕士学位期间参加的科研项目

E. 学位论文数据集

致谢