任一聚类边界提取算法研究

发布时间：2016-11-26 07:29

1    绪论

聚类[1]是根据数据集中数据对象之间的相似性[2]，将数据对象划分为若干个类，从而发现数据间的结构。聚类的边界[3]指的是聚类边缘处的数据对象，它代表了一种模式，对数据挖掘[4-6]有着重要的意义。当前，聚类边界的研究正处于发展阶段，提出的聚类边界检测算法并不多。但是，就已经提出的边界检测算法来讲，尽管它们通过使用不同的方法，获得了数据集中所有聚类的整体边界[7]，却无法从数据集中提取出任一聚类的边界。为了解决数据集中任一聚类的边界提取问题，本文提出了两种簇边界检测算法：基于 DBSCAN 的任一簇边界提取算法和基于 K 近邻[8]的具有聚类功能的簇边界提取算法。 本章一共分为三节：第一节概括了任一聚类边界检测的研究背景与意义；第二节叙述了聚类边界检测算法的研究现状；第三节则是对本文的组织结构进行说明。 

1.1    研究背景与意义 
聚类是将数据分类到不同的类或者簇的一个过程，所以同一个簇中的对象有很大的相似性，而不同簇间的对象有很大的相异性[9]。聚类分析[10-12]是一种非常有用的数据分析模式。在现实生活中，我们可以对商场中的消费者进行聚类，通过比较不同消费者购买物品之间的相似性，我们可以制定出“捆绑销售”的营销策略[13]。例如，通过聚类分析我们可以发现这样的一类消费群体，他们在购买了薯片之后，一般还会再购买可乐。这样，我们就可以将薯片和可乐进行捆绑销售，从而促进商品销量的增加和商场利润的增长。 聚类技术的研究是近几年研究的一个热门，并且现如今已经提出了许多聚类算法，比较经典的聚类算法如：基于密度的聚类算法 DBSCAN[14]，基于原形的聚类算法 K-MEANS[15]，等等。可是，对聚类的边界的探讨却还不够多。聚类的边界指的是聚类边缘处的数据点对象。边界点与孤立点[16-19]和噪声点[20-22]不同。对边界对象[23]来讲，它的类归属是确定的，但是，它与类中其它对象相比又具有不同的特性，代表着一种数据模式。例如，在医学领域中，恶性肿瘤患者的检测与预防一直是近年来我们比较关注的热点话题。恶性肿瘤患者的来源可能是良性肿瘤患者中的那些边界对象，也就是说良性肿瘤患者的聚类边界可能是那些易发展为恶性肿瘤的患者群体。因此，通过对良性肿瘤患者聚类边界的检测与研究，我们可以提前预判哪些良性肿瘤患者可能会发展成为恶性肿瘤患者，检测并发现发现如是的患者对恶性肿瘤的提前预防和治疗具有十分重要的应用意义。 目前，在聚类的边界检测方面，已经存在一些成熟的、使用不同方法的聚类边界提取算法。例如基于 K 近邻的聚类边界检测算法：BORDER[24]；基于K-距离的聚类边界检测算法 BAND[25]、BRINK[26]；基于密度的聚类边界检测算法：BOUND[27]、BRIM[28]；基于证据积累的聚类边界提取算法：BERGE[29]，等等。尽管以上聚类边界检测算法均可以有效的检测出数据集的整体边界，但是却无法识别出数据集中的聚类个数以及每一个聚类的边界。检测出数据集的整体边界固然重要，但是检测出数据集中的每一个聚类的边界，更加重要。文献[29]中使用 BERGE 算法成功提取出了 Mushroom（包含有毒蘑菇和无毒蘑菇）数据集中的聚类边界，这些聚类边界表示数据集中无法区分是有毒蘑菇还是无毒蘑菇的数据对象。但是如果我们能够提取出每一个聚类的边界，即有毒蘑菇的边界和无毒蘑菇的边界，我们就可以研究有毒蘑菇和无毒蘑菇之间的联系和区别，进而更加准确的区分有毒蘑菇和无毒蘑菇，这对我们的生产和生活，具有更加重要的应用意义。因此，对数据集中任一聚类的边界的检测，即：对数据集中所有单聚类边界的检测和研究具有十分重要的理论意义与实际意义。 
.........

1.2    聚类边界研究的现状
边界点的概念首先由 Ester 等在 DBSCAN 这一聚类算法中提出的。Ester等人认为，一个对象是否是边界点应该达到以下两个要求：1、它是一个非核心点对象；2、它落在某个核心点的 eps-邻域内。尽管 Ester 等人给出了边界点的定义和计算方法。但是这些定义和计算方法仅仅是针对聚类，并不涉及边界检测。也就是说，DBSCAN 算法中边界点概念的提出，可以使聚类算法的精度得到提高，但其并未给出如何计算并查找出一个给定数据集中各个聚类的具体边界的方法。 聚类的内部点[30]有别于聚类的边界点，聚类的内部点通常存在于数据空间中的密集区域，其四周均有大量的数据对象围绕着；边界点虽然也位于数据空间中的密集区域，但其仅有一侧是被大量的点对象围绕着。BORDER 算法就是借助边界点的这种特性，，利用边界点的反向 K-近邻个数小于聚类内部点的反向K-近邻个数来辨认边界点。BORDER 算法能够在不含噪声的数据集上比较完好的获得给定数据集的整体边界，但是对于含有噪声的数据集，BORDER 算法无法排除噪声的干扰，即将噪声点识别为边界点。BAND 算法提出了 K-距离的概念，它给数据集中每一个对象都定义了局部密度，而局部密度的值则定义为给定对象到其 K-距离范围内其它对象的距离和的平均值的倒数。在局部密度的基础上，BAND 算法又给数据集中每一个对象定义了变异系数，任一对象的变异系数的值为该对象 K-距离范围内其它对象的局部密度的标准差与这些对象的局部密度的平均值的比值。由于聚类内部点、噪声点的变异系数较小，边界点的变异系数较大，所以 BAND 算法能够在含有噪声的数据集上提取出数据集的整体边界。BRINK 算法在 K 距离的基础上提出了局部质变因子 LOF 的概念来识别边界点。对于给定的数据集，通常簇内对象的 LOF 值约等于 1，簇边缘对象的 LOF 值略大于 1，而且数据对象距离簇的距离越远，该对象的 LOF 值就越大。BRINK 利用 LOF 的值来提取边界点，它可以排除噪声的干扰并且实现在高维数据集上检测整体边界目的。BOUND 算法利用数据集中给定数据对象的 Eps 邻域内其它数据对象在该对象的正负半邻域内分布不均的特点来识别边界点。如果一个数据点的正半邻域中所包含的数据点的个数总和除以负半领域中所包含的数据点的个数总和的商超过给定的阈值，那么这个点就被视为边界点。BOUND 算法能够在含有噪声的且具有不同形状簇的数据集上提取出数据集的整体边界。BERGE 算法将模糊聚类引入了边界检测，它采用证据积累的思想克服了模糊 C-MEANS[31-32]随机初始化聚类中心所带来的误差，并且根据数据对象的隶属度定义了边界因子 BOF 来识别边界点。给定对象的 BOF 值越大，那么它就越有可能是边界点。BERGE 算法能够有效地从含有噪声的高维数据集中提取出边界点。 
..........

2    基于 DBSCAN 的任一簇边界提取算法 

本章在点密度、平均密度、连通距离、边界度等概念的基础上提出了一种基于 DBSCAN 的任一簇边界检测算法 DBORDER。本章主要包含 4 个部分：第一部分是相关工作，主要分析介绍 DBSCAN 算法在边界检测方面存在的不足。第 2 部分是算法定义，对 DBORDER 算法所用到的一些术语、方法或概念进行详细的解释和说明。第 3 部分是算法描述，对 DBORDER 算法执行的具体步骤进行解释和说明。第 4 部分是实验结果及分析，将 DBORDER 算法同其它边界检测算法做比较实验以及对实验结果、算法进行分析。

2.1    相关工作 
Ester 等提出了聚类算法 DBSCAN，它认为边界点是位于核心点的 eps-邻域内的非核心点对象[14]。虽然作为一种聚类算法，DBSCAN 却可以通过求边界点、聚类来获取数据集中聚类的整体边界以及数据集中各个聚类的边界。尽管如此，DBSCAN 算法在边界提取、边界点识别以及聚类个数的确定上还存在着一些不足： 第一，DBSCAN 使用全局 eps。所以，当 eps 取值较大时，DBSCAN 算法很容易将靠近聚类边缘的噪声点误识别为边界点，将相互之间比较靠近的类误识别为一个类；当 eps 取值较小时，DBSCAN 算法很容易将聚类内部点误分为噪声点或边界点，将一个类误分为若干各类。 图 2.1(a)是一个完整的簇，图 2.1(b)是图 2.1(a)中黑框部分的放大图像。图2.1(b)中，eps 取值为 3，minpts 取值为 10，A 点的点密度为 16，B 点的点密度为 9，C 点的点密度为 14。由于 A、C 两点的点密度大于 minpts，B

 点的点密度小于 minpts，所以，DBSCAN 算法根据 minpts 的取值，将 A、C 识别为核心点，B 识别为边界点。

......

2.2    算法定义
给出 eps，就意味着数据集中所有数据对象邻域范围的大小是一致的[36]。而当数据集中各个聚类的位置比较靠近，或者数据对象的点密度分布不均，或者各个聚类的内部对象分布不均时，过大的 eps 会导致本不应该合并的聚类被强行地合并成一个类，本应该排除的噪声点被强行的划分到聚类中；而过小的eps 又会导致同一个类被强行地划分成若干个类，本应该属于聚类内部中的点被强行的识别为噪声点或边界点。因此，给定连通度，求出连通半径，让核心点关于连通半径连通，而不是像 DBSCAN 算法中的那样关于 eps 连通，就可以将 eps 的取值同聚类个数以及噪声点的识别过程相互剥离，从而降低 eps 的取值对全局的影响，提高数据集中聚类数目和噪声点识别的精确性。 
............

3 基于 K 近邻的具有聚类功能的簇边界提取算法 .... 19 
3.1 背景介绍 .......... 19 
3.2 算法定义 .......... 20 
3.3 算法描述 .......... 22 
3.4 实验结果及分析 .... 23 
3.4.1 综合数据集上的对比实验 ............ 23 
3.4.2 高维真实数据集上的对比实验 ......... 27
3.5 算法时间复杂度分析 ......... 35 
3.6 参数讨论 .......... 35 
3.7 本章小结 .......... 35 
4 总结与展望 ............ 36
4.1 总结 ..... 36 
4.2 展望 ..... 36 

3    基于 K 近邻的具有聚类功能的簇边界提取算法 

本章在 K 近邻、反向 K 近邻、边界度等概念的基础上提出了一种基于 K近邻的具有聚类功能的簇边界提取算法 KBORDER。本章主要包含 3 个部分：第 1 部分是算法定义，主要是对 KBORDER 算法所用到的一些术语、方法或概念进行详细的解释和说明。第 2 部分是算法描述，主要是对 KBORDER 算法执行的具体步骤进行解释和说明。第 3 部分是实验结果及分析，主要将 KBORDER算法同其它边界检测算法做比较实验以及对实验结果进行分析。 

3.1    背景介绍

目前，在聚类方面，已经提出了很多聚类算法，如基于原型的 K-MEANS[38]算法，基于密度的  Revised DBSCAN[39]算法等。K-MEANS 算法在含有“圆形簇”或者簇间间距比较大的数据集上能够得到良好的聚类结果，但在含有噪声以及不规则簇的数据集上，K-MEANS 算法的聚类效果不佳。Revised DBSCAN算法可以在含有噪声、具有不同形状和大小的均匀簇的数据集上能够得到良好的聚类结果，但是 Revised  DBSCAN 算法由于使用全局 Eps，使得它在含有变密度的簇的数据集上无法得到理想的聚类结果[40]。K-MEANS 算法和 Revised DBSCAN 算法均可以有效的检测出数据集中的聚类个数以及聚类划分，但在数据集的整体边界模式以及各个聚类的边界模式的提取上，却缺乏相关的研究与探讨。 在聚类的边界检测方面，已经提出了一些检测算法，如 BOUND、BORDER等。BORDER 算法在不含噪声的数据集上能够得到良好的边界检测结果，但在含有噪声的数据集上，BORDER 算法无法排除噪声的干扰，会将噪声点全部识别为边界点。BOUND 算法无论在含有或者不含有噪声的数据集上都能得到良好的边界检测结果，但是 BOUND 算法只适用于低维数值属性的数据集，它无法在高维数值属性的数据集上检测出数据集的边界。BORDER 和 BOUND 算法均可以有效的检测出数据集的整体边界模式，但对某个聚类的边界模式的提取，却缺乏相关的研究与探讨，而且也无法获取数据集中的聚类个数以及聚类划分。 

.........

总结 

聚类的边界指的是聚类边缘处的数据对象，它代表了一种模式，对数据挖掘有着重要的意义。当前，聚类边界的研究正处于发展阶段，提出的聚类边界检测算法并不多。但是，就已经提出的边界检测算法来讲，尽管它们能够获得数据集的整体边界，但却不能获得数据集中任一聚类的边界。 为了提取数据集中任一聚类的边界，本文提出了 2 种簇边界提取算法：1.基于 DBSCAN 的任一簇边界提取算法，该算法在 DBSCAN 的基础上，将连通度、边界度、正负半邻域等概念引入边界处理，能够获取数据集中任一聚类的边界以及数据集的整体边界；2.基于 K 近邻的具有聚类功能的簇边界提取算法，该算法基于 K 近邻与反向 K 近邻，不但能够获取数据集中任一聚类的边界和数据集的整体边界，而且还能获取给定数据集中的聚类数目与划分。通过对这两种算法的定义、具体执行步骤、时间复杂度，参数进行说明和分析，将其同其它算法在综合数据集上以及在真实数据集上进行对比实验，并对实验结果、实验数据进行量化分析，检验了 DBORDER 算法与 KBORDER 算法在数据集上对任一聚类边界的提取能力。 
.........
参考文献(略)

本文编号：193945