一种改进的DBSCAN密度算法

一种改进的DBSCAN密度算法 一种改进的DBSCAN密度算法 第21卷第2期 2011年2月 计算机技术与发展 COMPUTERTECHNOLOGYANDDEVELOPMENT Vo1.21No.2 Feb.20ll 一 种改进的DBSCAN密度算法 于亚飞,周爱武 (安徽大学计算机科学与技术学院,安徽合肥230039) 算法存在许多优点,也存在一些摘要:DBSCAN算法是一种基于密度的聚类算法, 不足.比如对输入参数Eps敏感,DB— SCAN由于采用全局Eps值.昕以在数据密度均匀和类间距离相差比较大的情况下,聚类质量会受到很大影响.文中主 要针对算法输入参数Eps以及数据密度不均匀问题加以改进,提出了一种新的数据分区方法,通过对k-dist图纵坐标距离 值单维度聚类,然后对比横坐标实现分区,使每个分区的数据尽可能均匀.实验证明,改进算法明显缓解了全局Eps导致 的聚类质量恶化问题,聚类结果更加准确. dist图 关键词:DBSCAN算法;Eps;数据分区;K— 中图分类号:TP301.6文献标识码:A文章编号:1673-629X(2011)02-0030-04 AnImprovedAlgorithmofDBSCAN YUYa—fei.ZHOUAi—wu (CollegeofComputerScienceandTechnology,AnhuiUniversity,Hefei230039,China) Abstract:ThealgorithmofDBSCANisaFtalgorithmbasedondensity,includingbothmanyp ointsandalsoshortages.Forexamplethe algorithmissensitivetotheinputparameters,becausethealgorithmusestheglobalEps,theref oreinthecascofunevendataandthefar- gerdistancebetweenclasses,theclusteringqualitywillbegreatlyaffectedMainlyimprovedt hechoiceofEps,andsolvedthepmblemof unevendata.Proposedanewmethodofdatapartition,byclusteringthevalueofk— distverticalaxis,thealgorithmcompletedpartition. Eachdatapartitionwasuniform.Experimentalresultsshowthatimprovedalgorithmeasesth eproblemofdeteriorationclusteringquality significantly.Theimprovedalgorithmhasamoreaccurateresultofclustering. Keywords:DBSCAN;Eps;datapartition;K—dist ?5l置 数据挖掘就是对观测到的数据集(经常是很庞大 的)进行分析,目的是发现未知的关系和以数据拥有 者可以理解并对其有价值的新颖方式来总结数据…. 聚类分析是数据挖掘的一个重要方向.聚类是在预先 不知道数据样本有多少类的情况下,使所有数据组成 不同的类,类内元素相似性最大,类间元素相似性最 小.聚类有很多种算法,传统的聚类方法包括划分方 法,层次方法,基于密度的方法,基于网格的方法和基 于模型的方法. DBSCAN是一种经典的基于密度的聚类算法, 可以在带有噪声的环境下发现任意形状的类,所以在 图像处理等许多领域有着广泛的应用.但是算法 本身也存在许多问题.文中主要针对DBSCAN算法 收稿日期:2010—06,O1;修回日期:2010,09—17 基金项目:安徽省教育科研重点项目(KJ2009A57) 作者简介:于亚飞(1986一),男,硕t'生,研究方向为数据库与web技 术,数据挖掘;周爱武,副教授,研究方向为数据库与web技术,数据 仓库与数据挖掘,信息系统安全 存在的问题加以改进. lDBSCAN算法 1.1DBSCAN算法 DBSCAN算法是将密度足够大的数据组成类. DBSCAN需要由用户主观来选择参数从而影响了最终 的聚类结果,对于数据量为n的样本集合,DBSCAN的 计算复杂度为O(/2).一般采用空间索引的方法降低 时间复杂度,复杂度为O(nlogn). DBSCAN算法用到的定义如下: 定义l(数据点的Eps邻域)以数据样本中任意一 点为圆心,Eps为半径的球形区域内包含的点的集合, 叫做该数据点的Eps邻域. 定义2(数据点的密度)数据样本中任意一点的 Eps邻域内包含的点数,叫做该数据点的密度. 定义3(核心数据点)核心数据点是指在Eps半径 范围之内包含等于Minpts或大于Minpts个点的数据 样本中任意一点. 定义4(边界数据点)边界数据点是指在某个核心 数据点的邻域内,但自身不是核心数据点的数据样本 第2期于亚飞等:一种改进的DBSCAN密度算法?31? 中任意一点. 定义5(直接密度可达)已知Eps,Minpts,对于点 和点Y,如果Y是核心点,而且属于Y的Eps邻域,则 点从点Y直接密度可达. 定义6(密度可达)如果对于给定的Eps,Minpts 存在点链X1,X2,X3…Xn,其中X1=X,Xn=Q,而且 从+1直接密度可达,那么点从点Q密度可达. 定义7(密度相连)如果在给定Eps,Minpts的情 况下,存在点P,使得点和点Y都从p密度可达,则点 和点Y是密度相连的. 定义8事先给定Eps和Minpts,基于密度聚类中 的一个聚类就是可以密度连接所能包含的最多数据点 的集合.不属于任何聚类的数据点的集合称为噪声. 假定输入参数为Eps和Minpts,DBSCAN的算法 描述如下: (1)输入聚类数据,然后任意选取一个数据点, 检查数据点的Eps邻域. (2)如果是核心点而且没有被划分到某一个 类,则找出所有从密度可达的点,最终形成一个包含 的类. (3)如果不是核心点,则被当做噪声处理. (4)转到第一步,重复执行算法;如果数据集合中 所有的点都被处理,则算法结束. 1.2DBSCAN算法的优缺点 DBSCAN是一种基于密度的聚类算法,可以发现 不受噪声的影响.但算法需要事先 任意形状的聚类, 确定Eps,Minpts两个全局变量.一般事先确定Minpts 值比较容易.在数据样本不多的情况下,Minpts在二 维空间中的聚类中一般取4.另外取数据集合的1/ 25作为Minpts的值也是一种有效的方法.确定 Minpts之后,算法通过一个启发式方法来确定Eps参 数值.首先在给定k数值的情况下,将每个点映射为 该点与其第k个最邻近点间的距离,即k-dist.然后绘 制排序k-dist图.图中横坐标表示各个点,纵坐标表 示每个点对应的k-dist.接着在排序k-dist图中寻找 第一个凹陷,也叫做阈值点.因为通常来说,阈值点所 对应的数据点处于类的边界附近,所以当k等于 Minpts时,所求的Eps值就是阈值点所对应的k—dist 值.另外算法可以通过用户对数据中噪音水平的估 ps的值. 计更加客观的确定E 聚类之前建立R树和绘制k-dist图都是非常耗 时的工作.另外为了有更好的聚类效果,用户必须通 过反复试验选择合适的k-dist值. 难以发现密度相差较大的类是DBSCAN算法的 另一个缺点.由于参数Eps和Minpts是全局唯一的, 所以DBSCAN只能发现密度近似类.此外,如果类间 距离差别比较大,算法结果也会受到很大的影响,容易 产生偏差. 2改进的DBSCAN算法 近年来已经出现了很多的DBSCAN改进算法,比 较着名的是OVFICS算法.由于DBSCAN算法使用 了全局性的参数Eps,因此当各个类的密度不均匀,或 者类间的距离相差很大时,聚类的质量较差.文献 [9]提出了一种基于密度标记的聚类算法DTBC,DT— BC算法对所输入的参数不敏感,比较适合处理密度不 均匀的聚类问题.文献[10]中算法根据基于网格 与基于密度的聚类算法问的等效规则计算各个密度层 次的密度阂值,解决了DBSCAN算法参数选取困难和 难以发现密度相差较大的簇的问题.文献[11]中 提出了"分而治之"和高效的并行方法改进DBSCAN 算法,使聚类效果明显改善….周水庚等人提出了基 于数据分区的PDBSCAN算法.PDBSCAN算法有效解 决了密度不均匀问题,但是当类之间存在包含和交叉 关系的时候,比如互相缠绕的螺旋状类和互相包含的 环状类时,PDBSCAN方法难以见效. 文中主要讨论二维空问数据的分区问题.提出一 种新的数据分区方法,根据K—dist图的思想,计算每 个数据第K个最近邻居之间的距离,然后对距离聚类, 实现数据分区.因为原数据集的密度分布情况,和K— dist距离图比较相似,密度大的数据K-dist距离普遍 较小,稀疏的数据K—dist距离普遍比较大.一般K取 整个数据集的1/25I61.因为K—dis距离是基于密度概 念,跟每个类的位置无关.所以当类之间存在包含和 交叉关系的时候,基于K—dist距离的分区方法可以适 用. 建立K—dist图,横坐标为每个数据点,分别用数 据点的输入顺序表示,即1,2,3,4,5,6…t/,.自然数列 与原数据集形成一个映射.纵坐标为每个数据点和它 第K个最近邻居的距离.对K—dist图纵坐标距离值 单维度聚类. 单维度聚类,即将所有点的第K最近距离集合聚 类.用最简单的K—Means算法实现聚类.单维度聚 类之后,对比横坐标,就可以使原数据实现分区.当然 K—Means算法本身存在许多不足,合理选取初始聚类 中心,才能使每个分区的数据尽可能均匀. 分类完成之后,对于每一个数据分区,重新计算所 有K—dist值进行排序.然后,按原DBSCAN启发式方 法寻找K—dist排序图的第一个凹陷(阈值点),从而确 定每个分区的Eps值. 排序用到MATLAB函数一sort(一)形成降序序 列,为k—dist值矩阵. - 32?计算机技术与发展第2l卷 输入参数Eps和K,运行I)BSCAN算法得到一个 分区的聚类结果.然后对所有分区的结果进行合并即 可. k—dist图具体建立过程: (1)运行距离矩阵输出程序,输出数据集中所有 点之间的距离,大小为N的cid矩阵.每一行代表 一 个数据点与其他所有数据点的距离. (2)运行matlab数[v,2]=rain(cid,f],2),求 出矩阵cid每一行元素的最小值,筇一次找到的足仝0 数据,因为矩阵cid足对角线伞为0的矩阵. (3然后运行大数替换程学[cidn]=DBS(cid, f),12为数据点个数.最小值兀素用一个大数100替 换,得到矩阵cidn.同时保持矩阵中的数据位置不变. (4)对矩阵cidn求[,,,j=min(c,[],2)会 得到所有数据点的最近邻距离 (5)然后执行cid=cid1~,把cid重新赋值.返回第 3步,再次输入替换矩阵程事,循环执行=找到第二个 最近距离. (6)循环执行第3到5步,求出所有数据的第个 最近邻居距离,建立k-dist图. 3实验分析 实验使用MATLAB环境,采用二维数据,且数据 类型为实型.数据属性分别对应平面直角坐标系的横 轴和纵轴.分别利用原DBSCAN算法和改进后的算 法进行聚类. 3.1一般数据 利用人工方法构造规则的130个数据,,一般取 样本数据的1/25比较合适,所以K=5. 根据K—dist图建立过程,计算所有数据的第5个 最近邻居之间的距离.然后对距离进行聚类,选取最 远的两个点0.0860和0.9000作为仞始聚类中心,执 行K—Means算法进行聚类.距离分成两类,第一类90 个点,第二类40个点.对比横坐标,确定2个分区,分 别为90个点和40个点. 首先分析第一个分?9O个点,K=4.汁算所有 数据的第4个最近邻居之问的距离,绘制分区K—dist 图.对排序后的K—dist图查找第一个凹陷(阈值点), 确定Eps值为0.1503. 输入参数Eps和K值.运行DBSCAN算法,数据分 为3类,加号4O个点,圆形3O个点,五角星2O个点. 实验结果如图1所示.即左侧的i类数据. 然后分析第2个分区,40个点.因为点比较少, 所以直接用K—Means聚类更方便.如果用DBSCAN 算法,K=2计算所有数据的第2个最近邻居之间的 距离.在排序之后的K—dist中查找第一个凹陷(闽 值点),确定分区Eps值为0.5036.结果分为2类,加 号20个点,圆形20个点.即右侧的两类数据. 图1第一分区90个点聚类图 每个分区聚类完成后,对2个分区的聚类结果进 行合并.聚类结果符合数据实际分布,聚类效果较好. 如果开始不分区,要先建立全局排序的K-dist 图,然后根据启发式方法查找Eps值.. K—dist距离0.8043是第一个凹陷选取Eps=0. 8043,从聚类图2中可以看到,结果有明显偏差.因为 Eps太大,所以左边的2类被合并了.如图3所示. 第一类圆形,第二类五角星,第三类加号,第四类向下 的三角形 图2130个点Eps=0.8043聚类图 如果Eps=0.5590,从聚类图中可以看出右面2 类被合并,成为噪声.噪声用实心点表示.如图3所 示.第一类圆形,第二类五角星,第三类加号. 图3130个点Eps=0.5590聚类图 通过聚类图可以看出,改进算法由于运用了数据 分区,使每个分区的数据尽可能均匀,然后选取分区 第2期于亚飞等:一种改进的DBSCAN密度算法?33 Eps值进行聚类,所以聚类结果更接近实际数据分布. 原算法由于采用全局Eps值,所以聚类质量难以保证, 与实际数据分布相差很大. 3.2环绕型数据 人工构造环绕型数据集220个点,K=9.对于环 绕型数据,PDBSCAN算法难以见效,因为无论是在 轴或者y轴上分区,都是基于数据分布特性,跟类的相 对位置有关.在直方图的同一矩形区域内会存在大量 不同密度的点.改进方法基于密度概念,可以有效分 区,使分区内数据尽可能均匀. 首先计算220个点的第9最近距离集合,建立K, dist图.不考虑噪声,选取K—dist最远的两个点作为 初始聚类中心,即0.1800和0.9000.分成2类,分别 为40和180个数据.对比横坐标,确定2个分区,分 别为40个点和180个点. 首先分析第一个分区40个点,因为点比较少,可 以用K—Means算法直接聚类.分成2类,每一类20个 点. 然后分析第二个分区180个点,计算所有点K, dist值,K取7.执行DBSCAN算法,最后分成2类,每 一 类90个点,如图4所示.2类分别为五角星和实心 图4第二分区180个点聚类图 如果不分区,则要建立全局排序的K—dist图,然 后确定全局Eps. 首先选取Eps=O.6798,结果如图5所示.左侧2 类被合并为加号类,右侧2类被合并为五角星类,与实 际数据分布差别很大. 图5220个点Eps=0.6798聚类图 然后选取Eps=0.3000,噪声为三角形,结果如图 6所示.外围密度比较小的2类数据被当成噪声,明 显偏差. 守可7守 可口V甲守 口守苛口VV甲可 口可 可可vV 善季群曼季可可7 审可审 可7节 图6220个点Eps=0.3000聚类图 通过聚类图可以看出,Eps距离分区方法使环绕 型数据很好的实现分区,聚类结果更接近实际数据分 布.原算法由于采用全局Eps值.所以聚类质量难以 保证. 4结束语 DBSCAN算法是一种基于密度的算法,可以发现 任意形状的聚类,不受噪声影响.但是算法本:身对输 人参数Eps非常敏感,而日.对于密度分布不均匀的数 据集不适用.文中提出了一种新的数据分区方法,实 验结果表明,改进算法有效解决了数据密度不均匀的 问题,聚类结果更接近实际数据分布,准确性较高. 参考文献: [1]HandD,MannilaI{,SmythP.数据挖掘原理【M].张银奎, 廖丽,宋俊,等译.北京:机械:【业出版社,2003. [2东波.聚类/分类理论研究及其在文本挖掘中的应用 [D].北京:中国科学院技术研究所,2000. 3]Ester,Martin,KriegelHP,eta1.ADensityBasedAlgorithm forDiscoveringClustersinLargeSpatialDatabaseswithNoise [C]//Proceedingsofthe2ndInternationalConferenceon KnowledgeDiscoveryandDataMining(KDD一96).Ortland, Oregon:[S.n.],1996. [4]李莉平,沈俊媛.基于数据挖掘的DBSCAN算法及其应用 [J].科技创业月刊,2009(8):134—135. [5]孙凌燕.基于密度的聚类算法研究[D].太原:叶1北大学, 2009. [6]DaszykowskiM,WalczakB,MassartDL.LookingforNatural PattemsInDataJ].ChemometricsandIntelligentLaboratory Systems,2001,56:83-92. [7j仃必平,何忠龙,盂增辉.改进DBSCAN算法中参数Eps 值的确定[J.现代电了技术,2007(11):120—121 8]Ankers!M,BreunigM,KriegelHP,eta1.Optics:Ordering pointsIdentifytheCIusteringStructure[C://Proceedingsof ACMSIGMODInternationalConferenceonManagementof Data.Philadephia:ACMPless.1999:49—60. (下转第38页) 口v甲可 寸7可『)I>v 【>【)可下v{>L)守 f_:褥 可可口v 【>7了【)F可v可 vv【)v 口口口口审 ? 38?计算机技术与发展第2l卷 对;在任务处于完成状态,表示u1已经完成了对数据 的录入,u2在校对时,除了删除和修改已有的数据项 外还可以对u1遗漏的数据项进行添加;在任务处于提 交状态,用户u1和"2对数据项都只有读的权限.在数 据录入任务不同状态下用户1和u2的权限如表1所 示. 表1ul和u2在数据录入任务不同状态下 的对数据库数据项的操作权限 \.用户u1用户u2 权限 _\\霎蠢霎桨萎 读×,/x/,/,/×x,/,/x/,/ 添加×,/×××××××,/×× 删除×x/×××××,/x/x/× 修改×,/×××××,/x/x/×× 即数据录入任务t=({O,x},{O,"read,add,de— lete,modify"},{O,"read"},{0,"read"},{0, " read"},{O,x}), assigned— permissions(t)={read,add,delete,modi— fy}, ul向转授权服务器提出转授权 申请 关于撤销行政处分的申请关于工程延期监理费的申请报告关于减免管理费的申请关于减租申请书的范文关于解除警告处分的申请 del'egate(ul,u2,O,"read,delete,modify",1,1,t, sf1). delegate(ul,u2,O,"read,delete,modify",1,1,t, st2), delegate(ul,u2,0,"read,add,delete,modify",1, 1,t,st3), delegate(ul,u2,O,"read",I,I,t,st4), 其中0表示数据库的数据项对象,用stO,s,】,st2, st3,st4,s分别表示任务的初始态,执行态,挂起态, 完成态,提交态和夭折态.转授权服务器根据转授权 规则对这些转授权的合法性进行判定,经判定,这些转 授权合法,同意转授权.当数据录入任务运行到不同 的状态时,就获得对数据库数据项对象的对应的权 限,从而可以进行相应的操作. 4结束语 转授权技术作为访问控制的重要内容,在工作流 系统中得到广泛的应用,文中提出了一种基于任务状 态的用户一用户部分权限转授权模型,可以实现多步 和多重转授权.对该模型进行了形式化定义,同时提 出了转授权规则,冲突消解和转授权撤销等问题,最后 举例说明了该模型在工作流系统中的应用.该转授权 模型实际上是将任务的权限按照任务状态不同分别授 予合作用户各自相应的权限,实现了多个用户协作完 成某个任务而不相互干扰和冲突. 参考文献: [1]范玉顺.工作流管理技术基础[M].北京:清华大学出版 社.2001:31—32. [2]ZhangX,OhS,SandhuR.PBDM:aflexibledelegationmod— elinRBAC[C]//SACMAT'03:ProceedingsoftheEighth ACMsymposiumonAccessControlModelsandTechnologies. NewYork:ACMPress,2003:149-157. 31BarkaE.SandhuR.ARole—BasedDelegationModeland SomeExtensions[CJ//Proe.of23rdNationalInformation SystemsSecurityConference.Baltimore,MD,USA:NI, 2000:101—114. [4]ZhangLonghua,AhnGall—Joon,ChuBei—Tseng.ARule— basedFrameworkforRole—basedDelegation[C]//Proc.of the6thACMSymposiumonAccessControlModelsandTech— nologies(SACMAT2001).NewYork:ACMPress,2001: 153一l62. [5]张黎明,王小明,李黎.几种基于角色的代理授权模型特 征比较[J].微机发展,2004,14(11):126-129. [6]董光宇,卿斯汉,刘克龙.带时间特性的角色授权约束[J]. 软件,2002,13(8):1521—1527. [7]孙波,赵庆松,孙玉芳.TRDM一具有时限的基于角色的 转授权模型[J].计算机研究与发展,2004,41(7):lIo4— 1109. [8]廖旭,张力.工作流管理系统中一种基于任务的委托模 型[J].计算机工程与应用,2005,41(7):44—46. [9]洪帆,段素娟,黎成冰.基于图的委托授权模型[J].jB京 邮电大学,2005,28(6):5—7. [10]张润莲,武小年,董小社.基于委托的分布式动态授权模型 [J].计算机应用,2008,28(6):1365-1368. 『11]BarkaE.SandhuR.FrameworkforRole—BasedDelegation Models[C]//Procof16thAnnualComputerSecurityAppli- cationConference.IEEEComputerSociety.Washington,DC, USA:[S.n.],2000:168—176. [12]魏永合,王成恩,马明旭.工作流系统中的委托授权机制研 究[J].计算机集成制造系统,2009,15(1):160-165. (上接第33页) [9]高舁.基于密度聚类算法的改进方法研究[D].大连:大[11]冯少荣,肖文俊.DBSCAN聚类算法的研究与改进[J].中 连理工大学,2007.国矿业大学,2008,37(1):105—111. [1O]谭颖,胡瑞飞,殷国富.多密度阈值的DBSCAN改进算[12]周水庚,周傲英,曹品.基于数据分区的DBSCAN算法 法[J].计算机应用,2008,28(3):745—748.[J].计算机研究与发展,2000,37(10):1153一l159.