论文部分内容阅读
随着网络信息技术的不断革新,数据收集变的非常便捷,对数据的分析和研究也越来越受到重视,数据挖掘已经成为众多领域的研究热点。聚类分析是数据挖掘的主要任务之一,也是数据挖掘任务中研究的重点。聚类分析的目的是将具有极大相似性的数据对象划分为一组,而尽量使不相似的数据对象属于不同组。聚类分析研究的内容主要包括获得正确的聚类数目、设计数据对象之间相似性度量函数、高效的聚类算法以及聚类结果评价函数等几个方面。通常,聚类的数目会受到数据集复杂分布结构、样本重叠,噪声等因素的影响。特别地,从不同的领域、不同的角度对数据进行聚类,聚类数目往往也是不同的。在实际应用中,数据相似性度量函数会受到数据特征值缺失、类别特征、高维特征的影响。目前,面对大规模的高维数据集,开发可扩展的、高效的聚类算法具有很大的挑战性。对聚类结果进行评价要考虑聚类数目、样本大小、类簇形状、类内紧致性、类间分离性等因素。本文基于邻域技术对具有复杂结构的数据集中的离群点检测、高效的聚类算法、确定聚类数目三个方面进行了研究。归纳起来,本文主要创新成果包括:(1)提出了基于逆k最近邻的离群点检测算法。本算法结合了密度和距离方法的优势进行离群点检测。对目前存在的邻域技术,k最近邻、逆k最近邻、互k最近邻、共享k最近邻、自然最近邻做了对比分析。对数据集逆k最近邻数目的分布、稳定性进行了实验分析。提出的离群点检测算法计算每个数据对象的逆k最近邻数目,利用逆k最近邻数目来估计数据对象的邻域密度。为了进一步体现数据对象与数据主体的距离程度,对具有相同邻域密度的数据对象计算其k最近邻的距离,距离值越大,则认为更离群。实验结果表明,本文提出的离群点检测算法能够有效地发现全局和局部离群点。(2)提出了基于邻域密度划分的聚类算法。提出的聚类算法包含四个处理流程,首先对数据对象的邻域密度进行估计,根据密度阈值把数据集划分成核心数据集和非核心数据集。其次,利用最小生成树聚类算法对核心数据集进行初始聚类;再次,根据邻域的密度和紧致度对非核心数据集中的数据对象进行优先级排序;最后,采用最近邻算法按优先级依次把非核心数据集中的数据对象划分到初始聚类。实验结果表明,本文提出的基于邻域密度划分的聚类方法能够消除噪声、类间重叠的影响,能够识别不同形状的类簇。(3)提出了基于邻域重要性的启发聚类算法。本方法首先构建k邻域图,通过邻域图生成转移概率矩阵,利用随机游走模型对转移概率矩阵进行迭代计算,计算收敛后得到特征向量,该向量反映了数据对象的邻域重要性。其次,利用第k最近邻距离图谱确定重要数据对象的数目,基于重要数据对象运用启发规则找出正确的聚类数目,并且获得数据集的初始聚类。最后,将非重要数据对象划分到初始聚类。实验结果表明,邻域重要性排序算法可以发现重要的数据对象,提出的启发规则能够获得正确的聚类数目和初始聚类,聚类算法取得了较好的聚类效果。