基于数据分区的OPTICS聚类算法*

周传华， 鲁 勇， 于 猜

(1.中国科学技术大学 计算机科学与技术学院，安徽 合肥 230026； 2.安徽工业大学 管理科学与工程学院，安徽 马鞍山 243002)

0 引 言

聚类算法是一种无监督的学习方法，在图像处理、模式识别等方面有着广泛的应用[1,2],其主要目的是从大量数据中提取出潜在的、有价值的信息。聚类算法的中心思想是依据数据自身的特性，将数据对象自动地归类到相应的簇中，使得簇间相似度尽可能小而簇内相似度尽可能大。目前常用的聚类算法主要包括：层次聚类(balanced iterative reducing and clustering using hierarchies，BIRCH)[3]、划分聚类(K-Means)[4]、密度聚类(density-based spatial clustering of applications with noise，DBSCAN)以及网格聚类(statistical information grid，STING)等[3～6]，其中基于密度的聚类算法更是近年来学者们的研究重点。

周水庚等人[7]率先提出了基于数据分区的DBSCAN算法,根据数据空间分布情况，将数据集划分为若干个子区域，并在各个子区域内实现聚类。Rodriguez A等人[8]随后提出基于密度峰值的聚类算法,可以实现对凹数据集的聚类。刘沧生等人[9]利用密度峰值算法对模糊C均值聚类>算法进行优化，使其能够自适应产生初始聚类中心。于彦伟等人[10]在研究面向位置大数据聚类问题时，提出了一种高效的密度聚类算法(CBSCAN)，能够对任意形状的簇类及噪声实现快速定位。侯思祖等人[11]提出了一种适合多密度的DBSCAN改进算法。该算法首先识别出每个数据对象周围的密度，之后自动生成适合本区域密度的密度阈值。李蓟涛等人[12]将密度聚类算法与图论知识相结合，依照数据密度特征进行分块后合并处理，解决了传统密度聚类算法使用全局参数的局限性。但密度聚类算法依然存在着对于密度不均匀以及高维数据聚类效果差的问题。

为了解决上述问题，本文提出了一种基于数据分区的OPTICS算法(DP-OPTICS)，并通过实验得出，该算法对密度不均匀和高维数据集都有不错的聚类效果。

1 OPTICS算法

OPTICS算法是一种基于密度的聚类算法，是对传统密度聚类算法DBSCAN的一种改进，既继承了密度聚类算法的优点，同时也解决了密度聚类算法参数难以确定的问题[13]。DBSCAN算法需要确定两个参数，即邻域半径ε以及点数阈值(minimum point threshold，MinPts)。目前，大部分学者认为MinPts在二维空间聚类中一般取4[14]，或者取数据集合的1/25[15]，但邻域半径ε的数值却需要在实验过程中不断地调试，为算法的实现带来一定的困扰。但OPTICS算法不直接显示聚类结果，而是生成一个含有可达距离信息的增广簇排序，从这个排序中可以观察得到基于任何参数ε和MinPts的DBSCAN算法的聚类结果，大大提高了算法的执行效率。

定义1核心对象：对∀mp∈D，若在mp的ε邻域内的样本点个数等于或大于MinPts，则称mp为核心对象。

定义2核心距离：使得mp成为核心对象的最小邻域半径ε称为mp的核心距离，记为cd(mp)。

定义3可达距离：对于∀mp,mq∈D，则其可达距离记为

(1)

定义4直接密度可达：若mq在mp的ε邻域内，且mp是核心对象，则称mq是从mp直接密度可达的。

OPTICS算法的具体步骤如下：

Step1 标记数据集D中所有样本点均为未处理点，设置参数邻域半径ε以及点数阈值MinPts。

Step2 创建有序队列和结果队列，其中结果队列用来存储样本的输出顺序。

Step3 若样本数据集D中的所有样本点均被标记为已处理，则算法结束。否则选取一个核心对象，将其直接密度可达点放入有序队列中，并依据可达距离升序排序。

Step4 若有序队列中已无样本点，则跳转步骤Step2,否则将有序队列的第一个点放入结果队列中，并做以下操作：1)如果该点不是核心对象则返回Step4，反之则记录该点所有的密度可达点；2)若直接密度可达点已在结果队列中，则忽略；若在有序队列中，则在新旧可达距离中选择更小的可达距离记录，并按距离远近依次排序；若不在两个队列中，则在有序队列中插入该点并排序。

Step5 迭代Step3、Step4直至算法结束，按顺序输出结果队列中的所有样本点及其对应的可达距离。

2 数据分区的OPTICS算法

OPTICS算法虽然以输出有序决策图的方式解决了DBSCAN算法参数ε难以确定的问题，但对数据密度不均匀以及高维数据进行聚类时，输出的有序决策图比较杂乱，难以选择一个合适的邻域半径ε将簇精准地分隔开。基于上述考虑，本文提出DP-OPTICS聚类算法,通过计算样本点之间的K-dist距离，利用改进的K均值算法对样本点的K-dist距离进行单维度聚类，实现数据分区。数据分区完成后，在各个子区域内进行用OPTICS算法进行局部聚类，最后再按照一定规则合并分区并对局部聚类过程中产生的噪声点作相应处理。

2.1 数据分区

2.1.1 K-dist图

K-dist图是由Ester等人于1996年首次提出的，基本思想是计算数据集中每个样本点与其第K个临近点之间的距离，并输出以样本点序列号为横坐标，K-dist值为纵坐标的散点图，将这些点连接起来就形成了K-dist图。如图1所示，曲线A，B分别对应两个不同数据集的K-dist曲线。曲线A中平缓的部分对应数据集中的大多数样本点，这些点的K-dist值差距不大，说明样本点分布较均匀；曲线A后半部分K-dist值突然增大，说明所对应的样本点是边界点或噪声点。曲线B分为6个阶段，其中a，b，c三个阶段较为平缓且依次上升，分别代表数据集的三个密度水平；曲线d，e段则是连接a，b以及b，c的密度转折曲线，曲线f代表边界点或噪声点。研究表明，k>4时的K-dist曲线图与k=4时的曲线图几乎完全一致，因此在实际应用中k值一般取4[16]。

图1 K-dist曲线

K-dist图能够反映数据集的空间分布情况，紧密的簇类K-dist值普遍较小，稀疏的簇类K-dist值则相对较大，因此对K-dist值进行单维度聚类，对比横坐标所代表的样本点的序列号，即可依据数据密度差实现数据分区。同时，由于K-dist是一种基于密度的概念，与每个簇类所处的位置无关，所以，即使簇类之间存在包含或交叉等关系，K-dist图也能够很好地实现数据分区[17]。

2.1.2 改进的K均值算法

本文选用简单快速的K均值算法实现对K-dist图的单维度聚类，以实现初步的数据分区。算法基本步骤是随机选取K个样本点作为初始聚类中心，计算每个样本点与各个聚类中心之间的距离，并将样本点归类到与其距离最小的聚类中心，之后不断更新迭代，直至所有样本点均划分到相应的簇中。K均值算法在实际运用过程中需要预先设置K值(即簇类数)，同时初始聚类中心的选取也至关重要。

1)K值的确定

使用误差平方和(SSE)建立肘图，以此确定K均值算法中K值的大小，具体定义如下

(2)

式中ml为某个簇的各个样本点，p为聚类中心。肘图以K值为横坐标，以SSE为纵坐标，随着K值的增大，簇内聚合越紧密，SSE将逐渐变小并趋于0。若K值小于真实簇类数，则随着K值增大，簇内聚合程度将大幅增加，SSE快速减小；而如果K值大于真实簇类数，继续增大K值所得到的聚合程度回报会迅速变小，SSE的下降幅度也会骤减，因此肘图拐点处所对应的K值就应当是数据的真实簇类数。

2)初始聚类中心的选取

改进的K均值算法虽然在计算K值和初始聚类中心时需要耗费一定的时间，但在整个迭代过程中，算法能够更加快速地收敛，因此实际上提高了算法运行效率。

2.2 分区合并

1)合并类别

在局部聚类完成后，需要对各个数据分区进行合并，进而完成对整个数据集的聚类。考虑到利用K-dist图分区时，可能会出现同一个簇被划分到两个相邻的数据分区中，因此在合并分区时，不能简单地将分区中的簇的种类数叠加，而要考虑分区合并后，两个簇是否能合并为一个簇。为了提高数据分区的合并效率，在局部聚类的过程中，标记了分区内的噪声点以及簇的边界点，并记录其信息。对于两个类X和Y的合并，给出如下定义：a.类X和类Y分别被分割在两个相邻的数据分区Rx和Ry中；b.存在任意两个样本点mp∈X，mq∈Y，且dist(mp,mq)≤min{ε(Rx),ε(Ry)}。若满足上述两种情况，在分区合并后，选用Rx和Ry两个分区中更小的邻域半径ε，类X和类Y将会合并为一类，故此认为X，Y同属一个簇类。

2)归并噪声点

在实现数据分区时，某些较小的簇类可能被划分到不同的数据分区中，而在各个数据分区中由于其样本点太少，导致在局部聚类的过程中可能会被判定为噪声点，因此在合并分区时同样需要对分区内的噪声点进行归并处理，判断这些噪声点在全局中是否属于某一簇类，进而将其归类到该簇中。对于一个噪声点mi能否被归类到某一个簇类Z中，定义如下：a.噪声点mi和簇类Z分别处于两个相邻的数据分区中；b.∃pi∈Z，且dist(mi,pi)≤ε(Rz)，其中,ε(Rz)为类C所在分区Rz的邻域半径。

3 实验结果与分析

3.1 实验数据

本文在UCI真实数据集和人工数据集上分别进行实验测试，将DP-OPTICS算法聚类结果与K均值算法、AP(affi-nity propagation)算法以及OPTICS算法进行比较分析。K均值算法是目前应用范围最广的聚类算法，而AP算法擅长处理高维数据，因此与上述三种算法进行对比实验，可以很好地体现本文算法的有效性。

选取的实验数据集为人工数据集Jain,Spiral以及UCI真实数据集Iris,Seeds和Glass，五个数据集常用于聚类算法的测试且均具有一定的代表性。Jain数据集有2个簇，簇间距离较近且样本点密度不均，使得聚类难度较大；Spiral数据集包含3个类别，该数据集最大的特点就是簇间差异大、簇的形状呈螺旋状且含有噪声点。Iris,Seeds,Glass数据集来源于UCI真实数据集，数据维度分别为4，7，9维，可以用于检验算法处理高维数据的能力。各数据集具体的属性描述见表1。

3.2 评价指标

聚类算法常用的评价标准包括准确率、兰德指数(Rand index，RI)、调整兰德指数(adjusted Rand index,ARI)、以及轮廓系数等。考虑到使用单一的评价指标可能会导致评价结果过于片面，因此，本文选取上述指标对4种算法的聚类结果进行综合评价。

准确率指正确聚类样本数占总样本数的比例，计算方法简单且评价效果直观，是最常用的评价指标，适用于已知样本标签的数据集。轮廓系数结合了内聚度和簇间分离度两种评价因素，是较为客观全面的评价指标，轮廓系数的具体定义如下

(3)

式中a(i)为点mi到所属簇的其他点的平均距离，表示簇内不相似度；b(i)为点mi到其他簇中的样本点的平均距离最小值，表示簇间不相似度。s(mi)的取值范围为[-1,1]，-1表示该样本应该被归为其他簇，0代表该样本在两簇的边界上，轮廓系数越接近1则表明聚类效果越好。所有样本点轮廓系数的平均值即为该数据集的总轮廓系数s(i)。

ARI表示聚类结果的类别信息与正确类别相符的程度。ARI取值范围为[-1,1]，值越大意味着聚类结果与真实情况吻合度越高，具体定义如下

(4)

(5)

3.3 性能分析

本文的实验环境配置：CPU为Intel®CoreTMi7—4720HQ@2.60 GHz，16.0 GB内存，采用Python语言在PyCharm环境下编程实现。首先使用3种对比算法和DP-OPTICS算法对密度不均匀的人工数据集Jain,Spiral进行聚类，聚类的具体效果如图2所示。

图2 4种算法聚类效果

由图2可知，K均值聚类算法和AP聚类算法不能识别Spiral数据集中螺旋状的簇，同时对于密度不均的Jain数据集也很难处理，聚类效果相对较差；而OPTICS算法和DP-OPTICS算法，两者虽然都可以识别出螺旋状簇类，但是OPTICS密度聚类算法在Jain和Spiral数据集上的聚类效果明显弱于DP-OPTICS算法，尤其是在Jain数据集两个簇接近的部分，OPTICS算法未能将簇完全区分正确，而DP-OPTICS算法则只有一个样本点没有归类正确。4种算法在各数据集上聚类的具体实验结果数据见表2。

表2 不同算法在各数据集上评价指标准确率、轮廓系数、ARI对比

由表2可知，本文提出的DP-OPTICS算法在各个数据集上表现均佳，尤其是在密度不均匀的人工数据集上有着较大的优势，准确率分别达到了99.73 %和100 %，轮廓系数和ARI也更高。

传统的密度聚类OPTICS算法在Jain，Spiral数据集上表现不错，但在高维数据集上聚类效果则有明显下降，而经过改进后的DP-OPTICS算法不仅对密度不均匀的人工数据集有着更好的聚类效果，在其他三个高维数据集上的聚类结果也明显更优，准确率均达到90 %以上，ARI也稳定在0.8左右。

由于AP算法不能识别螺旋状的簇，导致对Spiral数据集聚类效果差，各项评价指标均远小于DP-OPTICS算法。而在Iris数据集上，由于数据集本身簇类之间差别较小，用K-dist图进行分区时，可能会破坏聚类的自然结构，因此DP-OPTICS算法在Iris数据集上的表现不如擅长处理高维数据集的AP算法，但聚类效果仍要强于K-Means算法和OPTICS算法。

4 结束语

本文通过对OPTICS密度聚类算法的分析，针对其局限性，提出了结合K-dist图和K均值算法进行数据分区的DP-OPTICS算法。实验结果表明：DP-OPTICS算法在对密度不均匀的Jain数据集进行聚类时，明显缓解了密度聚类算法因采用全局参数ε而导致的聚类效果不佳的问题，聚类精准性相较于传统聚类算法有显著提高，聚类的结果更接近于数据的实际分布情况。同时，对于高维数据集，DP-OPTICS算法也有着不错的处理能力，但对于高维数据中簇类差距较小的数据集，其聚类效果不如擅长处理高维数据集的AP聚类算法，尚有改进的空间。