一种改进和实现密度聚类的算法

【 摘 要 】 聚类是一种智能算法，该技术在数据挖掘中的一个重要分支技术。在现有的各种聚类算法中，密度聚类算法有着广泛的应用。密度算法具有与其他聚类算法聚类时的不同之处是密度聚类是否聚类成功决定于参数Eps和MinPts的取值。因此目前对于密度聚类算法的研究仍然是基于对聚类参数Eps和MinPts的研究。论文参考了MMTD算法和粗糙集中的决策系统之后，采用这两种算法对密度聚类法中的MinPts参数进行研究。论文对DBSCAN算法的研究思路是：当进行密度聚类时首先使用MMTD算法对参数MinPts时进行估量，其次再使用决策系统对MMTD做出的估量做出决策判断，最后根据决策判断的结果来判断这次聚类是否成功。

【 关键词 】 DBSCAN算法；MMTD；决策系统

1 引言

聚类算法能够使得人们对未知的数据进行识别。数据聚类技术能够强化机器的智能性，因此聚类算法在的各个科学领域都有广泛的应用，该技术有着广泛的应用前景。聚类的1算法思想是使用一定的规则将属性最为相似的数据聚成一个族，不同族之间的差异性达到最大值是聚类的目标。划分聚类算法、层次聚类算法、密度聚类算法等聚类算法是不同的算法。每种算法都有各自的特点，但同时也有不足之处。密度聚类算法最大特点优势是能够与任意形状的族进行聚类，该聚类算法在当今有各个方面的应用。目前有多种算法来改进已有的DBSCAN算法、OPTICS算法、DENCLUE算法。本文根据已有的算法：MMTD算法和粗糙集中的决策系统，对DBSCAN算法进行实现和改进。

2 DBSCAN算法

密度聚类算法是一种聚类算法，此算法能够在聚类空间中发现任意形状的族。常用的密度聚类算法有DBSCAN算法、OPTICS算法、DENCLUE算法。DBSCAN算法是根据的区域密度的MinPts值的大小决定是否聚类。在DBSCAN算法聚类过程中，如果点P在点Q的Eps邻域中点并且P的密度大于等于minPtS，那么进行聚类，否则就不进行聚类。DBSCAN算法聚类的过程也就是该类族不断扩大的过程，也就是将所有符合条件的样本加入该族之时。当聚类的条件满足时，则继续进行聚类，直到形成一个完整更大的族为止。

以下是DBSCAN算法的一些定义：

定义1 空间中任意一点P的Eps邻域：以该点P为圆心，以Esp为半径的球形区域。

定义2 空间中任意一点P的密度；点P的Eps邻域内包含的点的目的。

定义3直接密度可达：给定Esp和MinPts，若点Q在点P的Eps邻域内，且点P的密度大于MinPts，则点Q从点P直接密度可达。

定义4核心点与边界点：给Esp，其密度不低于MinPts的点，称为核心点；不是核心点，但是从核心点密度可达的点，称为边界点。

定义5族和噪声：基于密度可达性的最大密度相连对象的集合称为族，数据集D中不属于任何族的点称为噪声点。

3 MMTD算法技术

3.1 中介真值程度度量知识

中介逻辑将事物的属性描述成三种状态，事物属性的两个对立面和对立面的中间过渡状态。在中介真值程度度量方法中，提出了事物超态属性概念，该方法符合中介思想事物的属性并且被划分为五种状态：事物的两个对立面，对立面的中间过渡状态和事物超态对立面。这里用符号表示为～P，P与┑P，超态+P与超态┑+P。现用数轴将以上的描述的概念表达如下：

对数轴y=f（x）表示的含义有以下说明：

数轴上用符号P与┑P分别表示事物对立面的两个属性，符号～P表示反对对立面的中间过渡状态达事物的属性。

①如果数轴上数值点的位置逐步接近P，则事物A所具有P的属性逐步增强。

②如果该数值点的位置落在真值┑P和P的取范围之间，则事物A的属性就部分地具有┑P的属性，同时又部分地具有P的属性。

③如果数轴上数值点的位置逐步接近┑P，则事物A所具有┑P的属性逐步增强。

3.2 中介真值程度度量中的距离比率函数

在中介真值程度度量的方法中，数轴上某数值点通过距离比率函数来计算事物所具有属性的强弱。

定理1 给定y= f（x）∈f（X），ξ（h（y）） = h（y） ， 则有

（1） 当αF+εF < y< αT -εT时，gT（x）∈（0，1），gF（x）∈（0，1）；（2） 当y >αT +εT 时，gT（x）>1；当y1；（3） 当y

①相对于P的距离比率函数

②相对于┑P的距离比率函数

4 MMTD算法在密度聚类上的应用

4.1 基于MMTD的密度聚类函数：

f（x）=MinPtsQ -MinPtsP

函数中的变量MinPts的含义是：密度聚类算法DBSCAN算法中的点数阈值。DBSCAN算法中的MinPts值与密度聚类进行聚类时有关。

分析和讨论：

（1）如果MinPtsQ > MinPtsP，则有f（x）=MinPtsQ -MinPtsP > 0。

根据定义3有以下的结论：

①当函数f（x）>0，点Q从点P直接密度可达，这时聚类成功。

②当MinPtsQ > MinPtsP时，如果MinPtsQ的值比 MinPtsP大多，那么这时点Q从点P直接密度可达，聚类成功，MinPtsQ的值比 MinPtsP越大，密度聚类成功性强。

（2）如果MinPtsQ < MinPtsP，则有f（x）=MinPtsQ -MinPtsP < 0。

根据定义3有以下的结论：

如果当函数f（x）>0时，表述这时聚类成功，点Q从点P直接密度可达，那么：

当函数f（x）

（3）如果MinPtsQ ≈ MinPtsP，则有f（x）=MinPtsQ -MinPtsP ≈ 0

根据定义3以及（1）与（2）的分析和讨论有以下的结论：

当MinPtsQ ≈ MinPtsP时，点Q从点P部分具有密度可达的性质同时部分具有密度不达的性质，这时密度聚类成功性部分强部分差。

4.2 中介对密度聚类的描述

（1）现在用中介逻辑对密度聚类是否成功做以下的分析和说明：

数轴y=f（x）上有P，～P，┑P三个数据区域，P代表强，┑P代表差，～P代表部分强部分差。

（2）距离比率函数

从数轴y=f（x）上可以知道，在数轴上以～P为对称中心，左右分别为┑P和P。

y=f（x）的值落在三个值域范围（αr+εr ，αl-εl），（αr-εr ，αr+εr），（αl-εl，αl+εl）。～P的区域为（αr+εr ，αl-εl），┑P的区域为（αr-εr ，αr+εr），P的区域为（αl-εl，αl+εl）。P的真值为1，┑P的真值为0。

①相对于P的距离比率函数

通过距离比率函数hT（x）对y值的计算，如果有

①若函数hT（x）=1，y值落在区域（αl-εl，αl+εl），则代表聚类成功性强。

②若函数hT（x）=0，y值落在区域（αr-εr ，αr+εr），则代表聚类成功性差。

③若函数hT（x）= ，y值落在区域（αr+εr ，αl-εl），则代表聚类成功性部分强部分差。

5 粗糙集的决策系统

在实际应用中存在一大类任务：给定一组有特征描述的样本和样本的类别，需要通过一个学习算法从该组本文中学习一个分类函数，实现从特征到分类的映射。粗糙集理论中称该数据集为信息系统。

定义3.1 信息系统可形式化为如下的四元组：IS=，其中U={x1，x2，x3，…，xn}为研究对象的有限集合，即论域；A={a1，a2，a3，…，an}为描述对象的全部属性所组成的集合，即属性集；V=Va为属性集A的值域，其中Va为属性a∈A值域； f：U×AV为信息函数，表示对每一个x∈U，a∈A，f（x，a）∈Va 。当系统中属性集A=C∪D，C∩D=Φ，其中C为条件属性集，D为决策属性时，该信息系统也被称为决策表。

6 决策系统在密度聚类中的应用

6.1 密度聚类的属性

由于决策条件属性的属性值的不同，因此能够产生不同的决策属性的属性值，事实上正是由于不同的决策属性的属性值，产生了不同的决策结果，这些不同的决策结果能够将不同属性的样例进行有效的分类。条件属性的属性值决策规则的内涵，是决策系统做出决策结果的重要决定因数。

（1）域：U={x1，x2，x3，…，xn}，其中x1，x2，x3，…，xn分别表示密度聚类的Q点。

（2）属性集：A={a1，a2，a3}，其中a1表示Q的MinPts的值，a2表示函数y=f（x）的值，a2表示密度聚类的结果。

（3）值域：V={Y，N}。

6.2 密度聚类的决策表

在一个决策系统中如果把每一条样例的条件属性值部分作为规则的前件，把决策属性值部分作为规则的后件，那么每一条样例都可以看成一条规则。在决策系统中每一条样例都对应着一条具体的决策规则。在以下的决策表中可将决策属性分为条件属性和决策属性。信息系统中的属性集合可以分成两部分，一部分为条件属性集合，另一部分为决策属性，这种信息系统通常称为决策系统或决策表。

在以下的系统决策表中，条件属性为：Q的MinPts的值，函数y=f（x）的值。决策属性为：密度聚类的结果。

说明：

①当Q的MinPts值为某个值时：决策条件的属性值为Y。

②当函数f（x）的值大于0时，点Q从点P直接密度可达：决策条件属性值为Y。

③当函数f（x）的值小于0时，点Q从点P直接密度不可达：决策条件属性值为N。

④当密度聚类成功：决策条件属性值为Y。

⑤当密度聚类成功：决策条件属性值为N。

⑥密度聚类是否成功的决策规则：

（Q的MinPts，Y）∧（函数f（x）的值，Y）?（密度聚类的结果，Y）；（Q的MinPts，Y）∧（函数f（x）的值，N）?（密度聚类的结果，N）。

7 密度聚类的算法

（1）使用MMTD算法对密度聚类是否成功做出估量。（2）使用决策系统对MMTD的估量做出正确的决策。（3）如果密度聚类条件满足则聚类成功，并且这时决策系统的决策成功，否则为决策为不成功。

8 结束语

MMTD算法和粗糙集中的决策系统是两种智能算法，这两种算法在别的算法中进行应用能够改进和提高其他算法的智能性。决策系统和MMTD算法在各个研究领域都有广泛的应用。因此本文将这两种算法在密度聚类的参数进行首次的应用，这是本文的创新点之处。密度聚类算法是一种特殊聚类的算法，同时也是一种有广泛应用的聚类算法。MMTD算法和决策系统算法在密度聚类算法上的应用是否成功还需要在实际应用进行检验。

参考文献

[1] 赵文，夏桂书，苟智坚，闫挣兴.一种改进的DBSCAN算法[J].四川师范大学，201336（2）：312-316.

[2] 李双庆，慕升弟.一种改进的DBSCAN算法及其应用[J].计算机工程与应用，2014 50（2）：72-76.

[3] 冯少荣，肖文俊.DBSCAN聚类算法的研究与改进[J].中国矿业大学学报，2008 37（1）：105-111.

[4] 朱梧，肖奚安.数学基础与模糊数学基础[J].自然杂志，1980（7）：723-726.

[5] 洪龙，肖奚安，朱梧.中介真值程度的度量及其应用（I）[J].计算机学报，2006（12）：2186-2193.

[6] 胡清华，于达仁.应用粗糙集计算[M].北京：科学出版社，2012年6月.

[7] 陈德刚著.模糊粗糙集理论与方法[M].北京：科学出版社，2013年11月.

基金项目：

北京航空航天大学软件开发环境国家重点实验室开放基金资助项目（SKLSDE-2013KF-02）。

作者简介：

朱俚治（1980-），男，江苏宜兴人，南京航空航天大学，计算机科学与技术专业，本科，工学学士，南京航空航天大学信息中心，工程师。