论文研究-基于小波变换的Ad Hoc网络改进型资源分配算法.pdf

所需积分/C币:9 2019-09-08 18:47:24 1.2MB .PDF
收藏 收藏
举报

传统的密度聚类算法不能识别并聚类多个不同密度的簇。对此提出了变密度聚类算法VDBSCAN,针对密度不稳定的数据集,可有效识别并同时聚类不同密度的簇,避免合并和遗漏。VDBSCAN算法的基本思想是:根据k-dist图和DK分析,对数据集中的不同密度层次自动选择一组Eps值,分别调用DBSCAN算法。不同的Eps值,能够找到不同密度的簇。4个二维数据集实验验证了VDBSCAN算法的有效性,表明VDBSCAN算法可以有效地聚类密度不均匀的数据集,且参数Eps的自动选择方法也是有效的和健壮的。
周董,刘鹏: VDBSCAN:变密度聚类算法 2009,45(11)139 约定:本文描述的算法中,仅考虑参数取整数的情况 线L与密度转折线L。的连接处附近,是Ln纵坐标区间的子集 VDBSCAN首先计算数据集中的对象的第k个最近邻距 自动选择参数Eps(i≤n)的具体方法是:首先区分k-dist 离,画出k-dis图,通过观察、分析k-dist曲线,判断数据集中图中平缓曲线和密度转折线上的点。计算k-dist图中的相邻点 出现的密度层次,并对不同密度层次自动选择参数Eps的值组的纵坐标之差,即它们的k-dist之差。 (一组值,而不是 DBSCAN算法中的一个值);然后扫描数据 定义5DKn,记h-dist图中相邻两点Pn、Pm的k-dist差 集,用相应的Eps依次对不同层次的密度簇进行聚类;最后实为DKn=k- disp-k- distent 现不同密度的簇均得到有效的聚类。 DK值接近的连续邻近点处于k-dist图的同一条平缓曲线 VDBSCAN算法如下所示,总体划分为两个步骤:Eps选择上,即处于同一个密度层次;隔断密度层次的点处于密度转折 和变密度聚类实现。 线上,它们的DK值突然增大。将各点的DK值绘制成DK分析 步骤1画k-dist图 图。图2是DK分析图的一个例子。 DK图分析; 确定参数EpBs(i=1,2,…,n)的值; 步骤2对于Eps;(i=1,2,…,n) Eps=El 对未标记的点,调用 DBSCAN算法; 标记聚类结果为簇C; Points Sorted by Distance to hth Nearest Neighbor 显示聚类结果。 图2DK分析图的样例 步骤1Eps选择 首先画出k-dist图。在Ⅴ DBSCAN算法中,k-dist图可以判 接着,将DK(m=1,2,…)从小到大排序。取前面一定比例 断数据集密度层次,初步判定数据集的密度分布。对于密度交(如80%的DK值,计算它们的平均值Ave(p%)(如Ave8%) 化的数据集,h-dist图中会出现若干段平缓曲线,它们的纵轴 ve(p%)表示p%比例的值较小的DK值的平均值;这样,尽量 值,即第k个最近邻距离,明显不等这是因为在同一密度层次排除了密度转折线和异常点曲线上的点。给定一个阙值y,以 内的点的第k个最近邻的距离都很接近,它们反映在k-dist图 Ave(p%)为中心的阈值范围,即Ave(p%)±Y,作为平缓曲线上 上为平缓的曲线;而不同密度层次中的点到第k个最近邻的距 的点的DK值的标准范围。若存在一个点,它的DK值在标准 范围Ave(p%)±Y内,且至少和某给定数量(如20个)这样的点 离有明显差异,所以在k-dist图中出现若干段纵轴值不等的平 缓曲线。 连续相邻,则认为该点在位于k-dit图的平缓曲线上。不符合 定义2数据集中空间对象的k-dist图中含有若干条纵轴上述条件的点,位于密度转折线上。该步骤确定了所有点的 值不等的平缓曲线,则认为数据集密度存在变化,称其为变密 h-dist曲线性质 度型的。若k-dist图中出现n(n为自然数)条这样的平缓曲线, 定义6称某个点在k-dist图上属于平缓曲线或密度转折 则表示数据集含有n个密度层次。特别的,当n=1时,数据集只线这一性质为该点的k-dist曲线性质。 含一个密度层次,是单一密度型的。单一密度型数据集是变密 最后,确定参数Epsi≤n)的取值范围。DK分析图中,未 度数据集的一个特例。 被平缓曲线上分割的非平缓曲线上的点处于k-dist图上的同 图1是以k=4为例的k-dist图,曲线A表示单一密度型数 条密度转折线上。取该密度转折线连接的不同平缓曲线的最 据集的k-dist曲线样例,曲线B是n=3(存在3个密度层次)的接近的两个点,用这两点的k-dit值作为参数bps值域的两端。 变密度型数据集的k-dist曲线样例。 密度转折线上所有点的k-dist值均在这个值域内。参数Eps;的 在密度聚类中,没有被放到任何一个簇中的点被认为是噪值只需在这个值域中取即可。从左至右依次选择确定Eps:o 声点或异常点。这些噪声点和异常点在k-dist图上反映为呈快 步骤2变密度聚类实现 速上升趋势的曲线,如图1中的曲线段b、d和f。其中曲线段b 由于k-dist曲线是递增的,所以Eps;在选择过程中已经 和d的点是噪声点,f上的点是异常点。 按从小到大排序(Eps<Epsm,i<n)。依次用Eps作为参数调用 定义3k-dist图中的非平缓曲线为密度转折线,记为 DBSCAN算法。每次调用后,为聚类成功的点添加簇标记C, L1(i<n)。 表示密度层次D中的第t个簇。且标记过的点不再在以后的 定义4只连接一个密度层次的密度转折线为异常点曲 DBSCAN调用中处理。对所有的Eps:都处理过后,剩下的没有 线,记为Ln。 处理过的点即是异常点。C(i=1,2,…,n;t为自然数)为最后的 在变密度型数据集中,噪声点组成的密度转折线连接两条聚类结果 平缓曲线(即两个相邻的密度层次),如图1中,b连接a和c,d 连接c和e。异常点曲线只与一段平缓曲线相连,如曲线段4实验 图2中,L1=b,L2=1,L÷n=3。密度转折线分隔开不同的密度层41实验数据 次。对于不同的密度层次D,存在合适的Es,从而可以找到不 实验数据集1、∏、Ⅲ、ⅣV,是具有不同密度分布特征的二维 同密度层次中的簇。 数据集。需要指出的是,Ⅴ DBSCAN算法并不要求知道数据集 基于选定后的Ep值的 DBSCAN算法调用,应能够区分密数据分布的特点,也不要求数据集满足均一的分布。实验的各 度层次D和D(in)中的簇,既不会合并也不会遗漏。因此,数据集旨在模拟典型的密度分布情况,验证不同密度分布下算 Eps(i<n)的取值范围是密度转折线L1的纵坐标范围。特别的,法的有效性。二维数据集使得算法有效性的分析更加简便、直 密度层次D中的簇对应的参数Es,它的有效取值在异常点曲观。各数据集的属性特征如表2所示图5、8-10分别显示了各 1402009,45(11) Computer Engineering and Applications计算机工程与应用 数据集的点集。 [0.277438-0.6,0.277438+06=-0.322562,0.877438]。由于所 4.2实验过程 有DK值非负,所以平缓曲线上点的DK值标准范围实际为 实验环境为Ⅴ isual c#2005。以数据集I为例。取k值为0,0.877438,如图4中虚线与x轴之间的范围在该范围之外 3,-dist图和DK分析图分别如图3和图4所示。将点列按照的点有P25~P29、P35、P37、P38和P50,对照 k-dist图,如图3 h-dist值(k=3)从小到大排序,依次记为点P1~P50。 所示。 表2实验数据集描述 检查与这些标准范围之外的点相邻的点。P36的DK值虽 然在标准范围以内,但与它相邻的点P35、P37均不在标准范围 数据集取值范取值范围点个数 密度分布特征 内,因此P36不是平缓曲线上的点。 Ⅰ⑩0,210⑩0,21050密度大的簇与密度小的簇左右放置 依次检查各点的k-dist曲线性质后,最终确定k-dist图的 I1「-100,2001-100,2001400大致呈圆形:圆形内部密度大,圆形边框密度小 密度转折线是由点P25~P29连接的曲线、由点P35~P38连接的 I1p0,2000.200410大致呈矩形矩形边框密度大矩形部密度小曲线,以及点P50所在曲线。又因为P50位于k-dist图最右端, IV0,3600,30011500纵向密度大致相同;密度从左向右渐变小 所以它的k-dist曲线性质属于异常点曲线。 点P25和P29的k-dist值为k- dist=8260662,k- dist= y=0.9974x-60788 R=0.88627P50 29.054628。因为仅考虑参数取整数,四舍五入,Eps1的取值范 P38 P36 围为[8,29]。同理,k- dist3=32.189930,k- disp=35.790060, Eps2的取值范围为32,36]。k-dist-=43.345594,Es3的取值 20 是43。 当 Minpts=k=3时,取Eps1=8,调用 DBSCAN算法聚类,记 录标记聚类成功的点;取E2=36,调用 DBSCAN算法聚类未 ⊥⊥⊥⊥⊥L⊥L 三二28防导守导子 被标记的点,同样记录聚类成功的点;最后取Eps3=43,调用 DBSCAN算法。结果见4.3节。 图3数据集I的k-dist图(k=3) 43实验结果 12 数据集I在k=3时,调用 VDBSCAN的结果如图5~图7所 示,分别显示了Eps=8、Eps2=36、EPS3=43时调用 DBSCAN的聚 类情况。 6 图8-~图10分别显示了数据集I、IIV的Ⅴ DBSCAN聚 4 类结果。由于在 Visual c#205环境中用不同的颜色标识不 0.877- 个“ 同的簇,为更清晰地展示实验结果,在图中添加了辅助标记以 一mM=c988可扮所守乎导导守 区分不同的簇和噪音点。 图4数据集I的DK分析图(k=3) 44结果分析 计算Ave(p%),取p=80,则Ave(80%)=0.277438。取阈值 根据实验结果,用k-dit曲线斜率分析验证参数组Fs选 Y=0.6,则平缓曲线上点的DK值的标准范围Ave(p%)±Y,即择方法的有效性,及Ⅴ DBSCAN算法的有效性。事实上,k-dist E DBSCAN Algorithms Demo (均为噪音点) 图5数据集I在Es=8时的聚类结果 图6数据集I在Eps=36时的聚类结果 图7数据集I在Ep=43时的聚类结果 (除▲标识的点外,其余点均包含于簇C21) 通 DRSCAN AIgorithm 噪声点 CI isa F C 噪声点被点 C 图8数据集Ⅲ(h= MinPts=7) 图9数据集II(k= Minpts=7) 图10数据集I(k= MinPts=7) 周董,刘鹏: VDBSCAN:变密度聚类算法 2009,45(11)141 I DBSCAN AIRorithmB Dono i DBSCAN AI C1(除▲标识的点)M CI 图11数据集I在Eps=29时的聚类结果 图12数据集I在Es1=7时的聚类结果 图13数据集I在Es1=30时的聚类结果 图中相邻点间的横坐标均相隔一个单位距离,表示的是点的排 综上,实验验证了Ⅴ DBSCAN算法的有效性。同时,验证了 序,因此,DK值(即相邻点纵坐标k-dist差)的比较与k-dist曲Eps参数组值的自动选择方法是有效的,并且,Es值的选取是 线斜率的比较是等价的。 不敏感的,取值范围是一个区间。 仍以数据集Ⅳ(k=3)为例。分别计算点P1-~P26、P29-P50和 P26-P29(如图3中标示)组成的k-dit曲线的线性拟合函数及5总结和展望 其拟合度和斜率,并与所有点的k-dist曲线比较。如表3所示。 提出了一种基于 DBSCAN算法的改进密度聚类算法 表3k-dist曲线比较 VDBSCAN,以实现对密度不均匀的数据集进行更有效的密度 点范围 线性拟合函数 斜率 聚类。Ⅴ DBSCAN算法能够有效发现数据集中不同密度的簇, 全部点y=09974x-607880.88620.9974 这是 DBSCAN算法无法做到的。且两种算法的时间复杂度相 P1~P26y=0.2038x+2.56440.90020.2038 同,均为O( m log m)。 P29~150y=0.6949x+8.40720.94880.6949 实验证眀, VDBSCAN在聚类变密度数据集时取得了较好 P26~P29y=68151x-167.550.96936.8151 的效果,且时间复杂度没有增加。自动选择的Eps参数组的值 在线性拟合度R2都大于090的情况下,P26P29的线性拟敏感度不高,其中各个值的取值范围都是一个区间此外,为更 合函数的斜率为68151,分别是P-P26和P29P50的线性拟好地实现聚类效果,可以考虑用斜率检查的方法检查k-dit曲 合函数斜率的334倍和9.8倍,即P26~m29曲线段比P1-~P26和 线的分段斜率,剔除多余的密度层次,简化聚类步骤。 P29~P50曲线段都更陡峭。且点P26~P29介于点P1~P26和 但是, VDBSCAN算法仍有其局限,如需要主观确定两个参 P29~P50中间,形成的曲线段连接两段相对平缓的曲线。因此,参 数 Minpts和h。虽然 Minpts和k的值相等,但在实验时发现,h 数Es1在P26-P29的k-dist值范围.7490,29.0546内取值。 的取值(即 Minpts)应在有效范围内尽量大。尤其是在数据集中 实验中, DBSCAN方法选择的Eps1取值范围为8,29,与点的k-dist值范围不是很大时,k值越大(在一定范围内),Eps 上述分析结果吻合。事实上,在区间8,29取值,均可得到参数的取值越明显,聚类效果越好。如何科学地实现该参数的 理想的结果,如图5(Eps=8)和图11Eps=29所示,得到簇C1- 自动选择是下一步要进行的研究。另外,本文所研究的参数Eps 在直观上,这个结果也满足变密度数据集聚类的要求,将密度和k的取值只限于整数。参数取值为实数的情况还有待进一步 不同的簇分开,且成功聚类得到了密度大的簇C1,没有产生的研究和实验证明吗 缺失或合并。当参数Es的取值不在Ⅴ DBSCAN算法分析选 定的8,29范围内时,聚类结果会发生变化,如图12(Ep=7)和 参考文献: 图13(Eps1=30)所示。直观上,这不是理想的密度聚类结果 [1PetersonJD.cLusteringovervieweb/ol-2008.http://www.cs.ndsu 同理,表4对数据集中未聚类为C1的点进行了斜率分 nodak.edu/-jasonpet/CSCI779/Clustering.pdf. 析。斜率比较显示,P35~P38曲线的线性拟合函数斜率1607,(2ErM, Kriegel H P, Sander J,etl.A. density- - based algorithm for 分别是P29~P34和P38~P50曲线段斜率的8.30和3.52倍。该 discovering clusters in large spatial databases with noise[C]pro- 倍数较小,且斜率1.607的绝对值也不大。因此,P35~P38曲 ceeding of 2nd International Conference on Knowledge discover 线段与它连接的左右两段曲线的平缓度差别不大,可以考虑按 and Data Mining, Portland: AAAI Press, 1996: 226-231 相同的密度层次聚类。而实验中,参数EpS2在P35~P38段的k- [3] Ankerst M, Breunig MM, Kriegel H P, et al.OPTICS: ordering points to identify the clustering structure[C]//proceeding of 1999 ACM dist值范围为32.1899,36.7982]。但是,Es2取值为333435 SIGMOD International Conference. S1.: ACM Press, 1999: 49-60 或36时,直观上聚类效果(图6)都不是理想情况,即所有点聚41XuX, Ester M, Kriegel H F,tal. a distribution- based clustering 类成一个簇。这样的误差不排除实验数据的特殊性原因。从整 algorithm for mining in large spatial databases[C]//Proceedings of 体上来说, VDBSCAN的聚类效果在较高的可接受范围内是有 the 14th International Conference on data engineering Orlando 效的。 IEEE Computer Society Press, 1998: 324-331 表4k-dist曲线比较 [5 Sander J, Ester M, Kriegel H P, et al. Density-based clustering in 点范围 线性拟合函数 R 斜率 spatial databases: the algorithm gDBSCan and its applications JI P29~P50y=0.6949x+8.40720.94880.6949 Data Mining and Knowledge Discovery, 1998, 2(2): 169-194 P29~P34y=0.2002x+28.8930.92770.2002 6]贺玲,吴玲达,蔡遆朝.数据挖掘屮的聚类算法综述J-计算机应用 P38~50y=0.472x+35.95 0.94110.4720 研究,2007,24(1):10-13 P35~P38 1.6607x+30.2950.95111.6607 (下转153页)

...展开详情
试读 5P 论文研究-基于小波变换的Ad Hoc网络改进型资源分配算法.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    weixin_38743506 你的留言是对我莫大的支持
    2019-09-08
    • 至尊王者

      成功上传501个资源即可获取
    关注 私信 TA的资源
    上传资源赚积分,得勋章
    最新推荐
    论文研究-基于小波变换的Ad Hoc网络改进型资源分配算法.pdf 9积分/C币 立即下载
    1/5
    论文研究-基于小波变换的Ad Hoc网络改进型资源分配算法.pdf第1页
    论文研究-基于小波变换的Ad Hoc网络改进型资源分配算法.pdf第2页

    试读已结束,剩余3页未读...

    9积分/C币 立即下载 >