基于邻域链条的混合聚类算法研究

发布时间：2021-07-31 12:41

　　传统的聚类分析仅可处理一些简单的数据集合,复杂的数据结构和庞大的数据规模对这些传统方法来说是一个重大的难题。由于形状不规则、密度不均匀的数据集合,使得存在明显局限性的传统方法无法解决这些问题。为了提升聚类效果及其广泛的应用性,本文围绕如何解决任意数据集合中不同类型簇的准确识别的问题展开研究,论文主要工作如下:（1）基于簇结构的有向邻域链条方法。传统聚类算法中,基于几何距离的相似度量标准,在处理任意形状、任意密度簇的聚类问题时,不符合实际情况而且丢失一些能够反映真实情况的重要信息。本文从数据点之间的邻域关系入手,建立邻域链条的最优模型,以准确刻画数据点之间的相似度。通过分析发现邻域链条具有非对称性,为了避免对称运算带来新的问题,提出了有向邻域链条,实现簇内点相似度的最大化和簇间点相似度的最小化。（2）基于簇结构的有向邻域链条聚类方法（FDNCCS）。假设相似度量为有向邻域链条,但是不同的聚类方式同样会导致大的聚类误差。为了提高聚类效果,本文在有向邻域链条的基础上提出了一种新的聚类方法:最优母点匹配法,并在有向邻域链条模型基础上改进得到新的模型。主要任务就是让每个点找到与其相似度最高的高优... 

【文章来源】：哈尔滨工业大学黑龙江省 211工程院校 985工程院校

【文章页数】：86 页

【学位级别】：硕士

【部分图文】：

基于不同邻域数，A与C的邻域可达情况

哈尔滨工业大学工程硕士学位论文-11-是同样的处理方式。最终两点0+1{,}ncc之间的相似度通过一个对称化操作定义为：(,")0+1(,)1/(e(maxs(,),maxs(,)))0,,kkniii+1iii+1CMNCccccc"c"in(2-13)式（2-13）中的可以根据不同需要定义成不同的对称化操作。图2-2给出算法流程，首先设置最近邻域点数为2，先找出起点的最近2邻域中与终点最近的点，如果存在这个点且这个点不违背公式(2-11)的约束条件2，则将该点作为链条序列中的下一个中间点，按照上述原则继续搜索下一个中间点，直到抵达终点。如果这个点违背公式(2-11)的约束条件2，则说明无法满足建立邻域链条的条件，因此最近邻域点数加一，再重复上面的过程，直到出现一条从起点到终点的邻域链条，这样的链条称为成功链条，在此之前的所有链条都为失败链条。图2-2基于不同邻域数，A与C的邻域可达情况成功链条所对应的最近邻域点数就是最小需求邻域数，这个值越大说明建立链条的复杂度越高，进而反映了起点和终点有很大的分布差异。邻域可达代价主要是由数据之间的连接性造成，连接性越差，建立成功链条所对应的最小需求邻域数越大，相应的邻域可达代价越高。这只是衡量了数据之间的连接性，只能粗略地描述数据分布特点。为了更加细致地描述数据地分布

哈尔滨工业大学工程硕士学位论文-15-1不在数据点3的最近2邻域内，这意味着基于2邻域的从点3到点1的邻域链条无法建立。注意，在有向最近4邻域图中数据点1在数据点3的邻域内，意味着基于4邻域从点3到点1的邻域链条可以建立。图3-1K邻域图大多数相似矩阵都是对称的，因此在CMNC中需要一个对称运算。如果最小化作为CMNC的对称操作，则会引入大量的连接，分离性不好的簇可能会被合并为一个簇。如果最大化作为CMNC的对称操作，则会减少簇内部的连接，存在局部变动的簇可能会被划分为很多组。为了避免对称操作带来的这些问题，本章提出了基于簇结构的有向邻域链条，这种链条可以放大簇内点的相似度和簇间点的差异度。从图3-1可以看出从数据点1到数据点3的邻域链条需要更小的邻域数相比于从数据点3到数据点1的邻域链条。很明显数据点1的密度要比数据点3的密度小，也就是说，数据点1的邻域分布更稀疏。因为簇边界点相比于簇核心点的邻域分布要稀疏，为了放大簇内部数据点的相似度，从簇边界到簇核心的有向邻域链条将是很好的一个选择。而且同时放大簇间的差异度也很重要，因此对于分离性不好的簇从高密度簇到低密度簇的有向邻域链条将是最优的选择。3.2.2簇结构在介绍有向邻域链条之前，先来介绍两种簇结构分别是从簇核心到簇边缘的结构和从低密度簇到高密度簇的结构，如图3-2到3-5所示，x轴坐标代表数据点在簇结构中的索引，y轴坐标代表数据点的所有邻域点数目n与邻域点

【参考文献】：
博士论文
[1]聚类分析及其在图像处理中的应用[D]. 肖宇.北京交通大学 2012
[2]聚类分析及其应用研究[D]. 唐东明.电子科技大学 2010

硕士论文
[1]图像聚类及其在图像检索中的应用研究[D]. 杨传慧.南京师范大学 2013



本文编号：3313488