针对非均匀数据集自适应聚类算法的研究论文
摘 要：传统DBSCAN算法需要输入两个特定的参数（minPts和Eps），这对于没有经验的使用者是很困难的。同时，如果在多密度的数据集中使用全局的Eps参数，也会对聚类结果的质量造成大的影响。所以，针对以上两个问题，结合密度层次分层和聚类效果指数CEI的思想提出一种改进的DBSCAN算法。实验结果表明，改进的DBSCAN算法要优于传统的DBSCAN算法。
关键词：DBSCAN；多密度；自适应；密度层次划分
数据挖掘是关于数据分析的技术，它能够从大量的数据中提取隐藏和有意义的关系和模式。聚类分析作为一种重要的数据分析方法，主要用于将数据集中的对象分成多个类或者簇，使得同一个类和簇中的对象之间有较高的相似度，而不同对象之间的差别很大。DBSCAN作为经典的基于密度的聚类算法，它能够在包含有噪声和边界点的数据集中发现任意形状的簇。但是DBSCAN算法需要输入两个特定的参数（minPts和Eps），并且其无法处理多密度的数据集。针对这两个问题，笔者提出一种基于DBSCAN—DLP算法的针对非均匀数据集的自适应聚类算法SADBSCSAN—DLP（A Self—Adaptive Density—Based Spatial Clustering of Application with Noise based on Density Levels Partitioning）。实验结果表明，该算法在对参数敏感性和在多密度环境下聚类的准确性两方面要优于传统的DBSCAN算法。
1 传统DBSCAN算法
DBSCAN算法作为一种经典的基于中心的密度聚类算法，DBSCAN算法的定义如下：
定义1：（Eps—邻域）给定某个对象q，q的邻域 定义为以p为核心，以Eps为半径的d维超球体的区域，公式表示为： 其中，d为空间R的维度。dist（q，p）表示对象q和p之间的直线距离。
定义2：（核心点、边界点，噪音点）对于数据对象q，且，如果以q为中心， 以为半径，若内的.点数超过给定MinPts，则称q为核心点，若q不是核心点，但在某个核心点的邻域内，则称为边界点，其余为噪声点和离群点。
定义3：（直接密度可达），如果q属于r的Eps—邻域，且r是核心对象，则称q从r直接密度可达。
定义4：（密度可达）密度存在对象链，，若所有的对象从对象关于Eps和MinPts直接密度可达，则称q从p关于Eps和MinPts密度可达。
定义5：（密度连接）给定对象r，若p和q都是从r出发，关于Eps和MinPts密度可达的，则称p和q是关于Eps和MinPts密度连接的。
定义6：（聚类）对象集D的非空集合C是一个关于MinPts和Eps的聚类，当且仅当满足下面条件： 最大性：：若，且q是从p关于Eps和MinPts密度可达的，那么； 连通性：：p与q是关于Eps和MinPts密度连接的。
2 SADBSCAN—DLP算法
SADBSCSAN—DLP算法的思想：为了能直观的描述改进算法，我们构造了带有三个不同密度层次的样本数据集，如图2（a）。并计算出其对应的KNN矩阵，对KNN矩阵中的某一列进行曲线拟合得到distk图，如图2（b），再计算每一列的密度变化率DenVar，然后可以得到每一列的密度变化率的一个序列DenVarList，然后再以DenVarList序列的下标作为横坐标，对应的DenVar值作为纵坐标，绘出DenVar图，如图2（c）。 根据DenVarList序列的统计特性，β的定义如下： 改进算法的具体步骤如下： 根据阈值β定义计算出KNN矩阵中每一列的β； 通过β和KNN中每一列的DenVarList序列对每一列进行密度层次分层； 根据分层结果计算出KNN中能使CEI到达最大值所对应的第k列，将k作为minPts； 根据分层结果，计算出每一层的Epsi，Epsi的计算方法如下： 在不同的DLSi上进行聚类，最后合并聚类结果。
3 实验结果
为了分析和观察实验结果，我们使用了来自UCI的两组不同的数据集。实验在Matlab V7。1软件下实现进行。使用Rand—Index来比较三种聚类算法的效果。 表1 结果比较 数据集 算法参数 Rand—Index Iris （Cluster = 3， Attribute = 4） DBSCAN （minPts = 4， Eps = 0.3194） 69.1% DBSCAN—DLP （k = 4， ω=0.5） 84.1% SADBSCAN—DLP （ω= 0.5） 88.03% Wine （Cluster = 2， Attribute = 13） DBSCAN （minPts = 4， Eps = 0.3194） 73.1% DBSCAN—DLP （k = 4，ω= 1） 72.3% SADBSCAN—DLP （ω= 0.5） 72.1% 表1给出了三个算法的实验对比结果。可以看出，在数据集Iris中使用所改进的算法的准确度要高于其它两个算法
4 结 语
本文针对DBSCAN算法和DBSCAN—DLP算法的不足提出了改进。实验结果表明改进的算法SADBSCAN—DLP算法有效减少了传统DBSCAN聚类算法对参数的敏感度，对聚类效果有很大的提升。
参考文献 [1]Xutao Li， Yunming Ye， Mar
【针对非均匀数据集自适应聚类算法的研究论文】相关文章：