论文部分内容阅读
随着计算机和互联网技术的飞速发展,各种类型的数据呈爆炸式增长。如何在海量数据中进行准确有效地信息挖掘和知识获取,已成为当今社会亟待解决的重点问题。聚类分析作为数据挖掘技术中非常有效的手段之一,其目的是发现隐藏在数据集中的内部结构。近年来越来越多的学者关注聚类分析,但是对类边界信息的关注度不够,另外聚类分析与其他学科交叉结合也日益频繁,其中的生物视觉系统计算模型为聚类分析提供了一种新颖的生物观点。本文针对现有聚类算法存在的缺陷展开研究,设计一种利用边界信息进行聚类的算法。另外,将生物视觉系统的尺度空间理论应用于聚类分析,提出一种基于视觉系统的网格聚类算法。本文的主要创新工作包括以下两个部分:(1)针对K-means聚类算法不适用于非凸数据集以及Affinity Propagation(AP)算法不能准确区分类边界的缺点,本文通过分析类边界信息,提出一种利用边界信息进行聚类的算法。本算法采用传递性聚类不断扩展当前集合直至形成完整的类,由于使用传递性聚类方法使得本算法对凸型和非凸型数据集都能取得很好的聚类结果。因为边界点描述了潜在的数据结构,对聚类分析具有十分重要的意义,所以本算法首先统计每个数据点邻域内包含数据点的个数作为其密度,然后定义密度低于平均密度的数据点为边界点并统计边界点的数目。如果边界点的数目小于给定的阈值,则用边界点勾勒出各类的轮廓,然后任意选择一个非边界点开始传递性聚类,在传递聚类过程中遇到边界点则停止往类外传递,这有效地避免了将不同类的数据点聚为一类的情况发生。否则,说明数据集过于稀疏,此时边界点与非边界点差别不明显即无法用边界点准确划分类边界,所以不再区分边界点与非边界点,直接进行传递聚类。根据边界点的数目不同采取不同的聚类方案使本算法对稀疏和非稀疏数据集都能得到理想的聚类结果,从而扩大了算法的适用范围。在人造数据集和标准数据集上的实验结果表明本文提出的算法是有效的。(2)针对网格聚类算法中网格宽度难以确定的问题,本文设计一种计算网格宽度的方法,并将视觉系统中的尺度空间理论应用于聚类分析,提出一种基于视觉系统的网格聚类算法。通过对传统网格聚类算法的时间复杂度和准确度进行分析,确定合理的网格宽度,使得在减小算法时间复杂度的同时保证算法的准确度。根据Weber定律来增大网格宽度,从而达到视觉尺度空间理论中连续增大观察尺度的效果,对于每个网格宽度都有一个聚类结果,定义出现次数最多的聚类结果作为最终聚类结果。本算法将视觉系统中的尺度空间理论应用于聚类分析中,因此能够准确地发现数据集中的类结构。在人造数据集和标准数据集上的实验结果证明了基于视觉系统的网格聚类算法是有效和高效的。