基于三支决策的重叠聚类方法研究

摘要

聚类分析是挖掘数据中潜在结构的重要工具之一，它被广泛应用在模式识别、生物科学、社会科学、心理学和数据挖掘等领域中。在网络结构分析、无线传感器网络和生物信息处理等领域中，普遍存在着类与类重叠的现象，即一个元素可能属于多个类中。特别是在社交网络中，一个用户根据不同的兴趣爱好，可能会是多个社区的成员，不同社区之间普遍存在重叠现象。因此，本文主要针对类与类之间存在重叠现象的聚类问题进行了研究。
　　 本研究基于决策粗糙集模型的三支决策，借助区间集的表示形式对聚类的概念进行了重新描述。一个类（簇）被定义为一个区间集的形式，即由上界集合和下界集合描述;元素相应地被分为正域元素、边界域元素和负域元素。也就是说，一个类（簇）不再是一个集合表示，而是由一对集合表示。处于正域的对象是肯定属于该类的成员，处于负域的成员对象肯定不属于该类，处于边界域的成员可能属于该类。基于三支决策的聚类，有利于解释类与类之间的重叠现象，比如处于某个类的正域或边界域的对象很可能也是另一个类的正域或边界域对象。因此，类与类之间的重叠分类情况将更加多样化。本文详细分析了类与类之间可能存在的各种重叠情况，并且根据不同的重叠情况，定义了重叠度，根据重叠度给出不同情况下的类与类的合并策略。考虑到数据既有网络型数据，也有关系型的数据，提出了一种两步聚类思想，即:首先针对不同类型的数据提出不同的初始化聚类方法;再根据类与类之间的不同重叠类型，根据前面提出的聚类合并策略得到三支决策的聚类结果。随后，根据网络型数据和关系型数据不同的特点，分析其聚类结果的基础上，提出了检测数据集中的特殊点的方法。实验采用了常见的社交网络数据集跆拳道俱乐部数据集(Karate)、海豚交友数据集(Dolphins)等，以及UCI(the UC Irvine Machine Learning Repository)中的一些关系型数据集。实验结果表明，基于三支决策的聚类新思想不仅较好地解决了重叠聚类问题，而且在任意形状聚类、聚类数目确定和特殊点挖掘等方面也是有效的。

目录

声明

摘要

第一章 绪论

1．1 引言

1．2 研究现状与分析

1．3 研究内容

1．4 组织结构

第二章 相关基础理论

2．1 三支决策

2．2 基于决策粗糙集的三支决策

2．2．1 经典粗糙集

2．2．2 基于最小风险的Bayes决策

2．2．3 决策粗糙集模型

2．3 区间集

2．4 小结

第三章 基于三支决策的聚类描述

3．1 决策粗糙集模型的扩展

3．2 基于三支决策的聚类描述

3．3 类与类重叠分析

3．3．1 类与类重叠类型

3．3．2 类与类重叠度

3．4 小结

第四章 基于三支决策的聚类算法

4．1 关系型数据集

4．2 网络型数据集

4．3 两步聚类算法

4．3．1 算法框架

4．3．2 关系型聚类初始化

4．3．3 网络型聚类初始化

4．3．4 三支决策聚类

4．4 特殊点检测

4．4．1 关系型数据集的特殊点检测

4．4．2 网络型数据集的特殊点检测

4．5 三支决策聚类算法分析

4．6 小结

第五章 仿真实验

5．1 重叠现象

5．1．1 关系型数据

5．1．2 网络型数据

5．2 聚类数目

5．3 任意形状

5．4 特殊点检测

5．4．1 关系型数据集

5．4．2 网络型数据集

第六章 总结与展望

6．1 总结

6．2 未来工作

致谢

攻硕期间从事的科研工作及取得的研究成果

参考文献