论文研究-基于数据场的改进DBSCAN聚类算法 .pdf

所需积分/C币:15 2019-08-15 10:49:09 782KB .PDF
收藏 收藏
举报

基于数据场的改进DBSCAN聚类算法,杨静,高嘉伟,DBSCAN算法是一种典型的基于密度的聚类算法。该算法可以识别任意形状的类簇,但聚类结果依赖于参数Eps和MinPts的选择,而且对于一些密
山国武花论文在丝 理论借鉴物理学中场的思想,将物质粒了间的相互作用及其场描述方法引入到抽象的数域 空间中。该理论克服了传统算法中只考虑数据对象间一对一作用关系的弊端,用势函数米描 述数据对象间的相互关系,认为任一数据对象的状态是其他数据对象共同作用的结果,并利 用数据势场中等势线面的自然嵌套结构来实现数据对象的划分。 考虑到高斯分布的普适性及短程场更适合反映数据分布,数据场将势函数定义如下: 已知数据空间9Ra上的刘象集D={xx2…xn及其产生的数据场,m:≥0是对象 x:(=1,2…n)的质量,即对象x:对其他对象的影响力,一般情况下认为各个对象的影响力 是相等的,可以令m1=1:σ∈(0,+∞)是用来控制对象间的相互作用力程,称为影响因子 则任一场点处的势值可以定义为所有对象在该点处产生的势值的叠加: 为了说明单数据对象产生的数据场中场强与距离的分布关系,不妨令m:,J=1,由此可 得到图。由图可知,在距离数据对象处,场强达到了最高值,即在以场源对象为中 ,半径为的球面上存在很强的指向场源对象的作用力。结合数据具有自组织聚集的 特性,可以认为在数据对象邻域内的数据对象同属于一类的可能性较大。在下文计算 Eps和四时会用到这一内容,文中不再赘述。 Rn705 25 15 05 图1单数据对象数据场中场强函数与距离的分布关系 数据场理论具冇较好地刻画数据分布、反映数据间多对一的作用关系的优势。该优势对 聚类算法中—些参数的确定有着较好的指导作用 一种基于数据场的改进 聚类算法 算法中的相关定义及计算 数据对象x:的R邻域N2(x 对于数据对象x:∈D,其R邻域M2(x)是以x:为核心,以R为半径的d维超球体区域内包 含的点的集合,即M2(x2={xdst(x,x)≤Rxx∈D},其中,D为d维空间上的数据集, dist(x1,x)表示D中数据对象x和x之间的距离。 Eps的计算 对于数据对象x:∈D,由x确定的Eps计算方法如卜:先计算M。zas(x:)中每个数据与其 第 Minpts近的数据对象的距离,最后将这些距离的平均值赋给Eps 山国武花论文在丝 Vd 为了将数据场与 融合,本文引入平均势差vφ来辅助 聚类,定义V 是邻域R内任意两个数据对象的势差的平均值。从等势线的分布可以看出,如果两个数据对 象问的势差较小,那这两个数据对象同属一类的叮能性较大。 对于数据对象x:∈D,由x确定的Vφ的计算方法如下:先计算Nos(x)中任意两个数 据的势差的绝对值,然后将这些势差的平均值作为v的值,其形式化描述如下 Vop 2x62y5814)-yx,其中M表示集合N02030(x所包含的元素个数, 即M=1M705(x计 如果某个数捃对象的0.705σ邻域内没有其他数据,或者满足山该数据确定的Eps和Vq这 两个指标得到的数据集包含的数据个数小于 MinPts,那么则认为该数据是噪声。 算法描述: 输入:数据集D={x2x2…xn},类内最小对象数 Minpts; 输出:聚类结果。 步骤 :初始化未处理数据对象集合U=D,临时存放属于某一类的数据对象集合A=0。 计算各数据对象的势值q(x)==(m1已 x1x∈D,其中 1i=1,2,…n :根据势值为极值的数据对象,寻找与其同属于一类的数据对象。 确定xp,x满足条件:q(x2)=max(q(x),x1,xp∈U且xp不为噪声,将x放入集 合A 计算由x2确定的Ep和Vq 对」集合A中的任一元素A,i=1,2,…,|A,计算A:确定的Eps邻域Np(4),对」 XE NE(A),若x满足条件:3x:ENBp2(x2)nA使得p(x)-9(x≤Vp,则将x放 入A中。 将A中数据对象划分为一类,U=U-A,若U≠,令A=,转,否则 输出聚类结果 实验结果 为了验证算法的有效性,本文分别在人工数据集和数据集上做了对比实验 在人工数据集上的实验结果 测试数据集如图所示,其中 和 来自文献,不同类的密度差距较 是人⊥构造的数据集,不同类的密度差距较大。 包含个数据,由 个不规则的类构成,有型、型、型及对勾型 也包含个数据,包含个 类,个型、个椭圆形及个大小不同的圆形类,并且数据集含有的噪声数据 包含个数据点,数据分布呈现类,包含个不同大小、形状、密度的类和个相嵌套 的环形类。图示中分别用绿色的实心点、红色的加号、青色的三角符、蓝色的空心圆圈及品 山国武花论文在丝 红色的义号来表示不同的类,用黑色的米字符来表示噪声数据。 1 日 基 石 卡 998088 10 1012 10 E 图测试数据集 本文通过将提出的算法与标准 算法、数据场聚类算法和 算 进行比较,从而验证算法的有效性。 的实验结果 10 E 4L s82 4 数据场聚类算法 山国武技论文在丝 。岸 E ★ 要 4 命命章 算法 图四个聚类算法在 上的聚类结果 如图所示: 算法不能有效地区分这些不规则的型、型、型、对勾型的 类;利用等势线嵌套结构得到聚类结果的数据场聚类算法自适应得到σ=4,25可以较好地 划分这些不规则的类,其中图的坐标是标称距离,下文中由数据场聚类算法得到的实 验图的哗标也都是标称距离,以下不再赘述; 算法在选择合理的Eps和 Min Pts的情 况下,可以较好地划分这些不规则的类;提岀的算法只需输入 MinPts,就可以将这些不规则 的类簇合理地区分,其聚类效果与数据场聚类算法和 算法相当。 的实验结果 1u凵 日 染 2 100 数据场聚类算法 10 十 的* 卡 12 算法 图四个聚类算法在 上的聚类结果 山国武花论文在丝 如图所示 算法不仅对不规则形状类的聚类效果不太理想,而且对噪声数据 较为敏感,噪声数据会影响类中心的选择,导致聚类结果不佳:数据场聚类算法自适应得 到σ=4.41可以较好地处理不规则形状类,但对于一些相距较近的类不能很好地区分,也 容易把一些距离类簇较近的噪声数据划分到类中; 算法在选择合理的Eps和 MinPts 的情况下,既能较好地划分不规则形状类,也能较好得将噪声数据区分出来;提出的算法只 需输入 MinPts,便可以在较好划分不规则形状类的同吋,也可以较好地区分噪声数据,其聚 类效果与 算法相当。 的实验结果 10 100r. 风阵 十十十十十十十十十 题 粪丰丰丰丰+ 30-,?千*+ 十十+十十十十十 bU 少丰丰 8888883 十十十 4 2043 0100 数据场聚类算法 礫捕‖ 寺章幸章中章争 专中卡 10 10 8888888 IRR 4 算法 山国武花论文在丝 图四个聚类算法在 上的聚类结果 如图所示: 算法不能有效地区分环形数据和密度差别较人的数据集;数据场 聚类算法自适应得到σ〓482不能有效区分环形数据,而且对于相距较近但密度差别较人 的数据不能较好的区分,较容易将这些数据划分为一类;通过选择合适的Eps和 Minpts, 算法可以得到图中的两种结果,其中图的聚类结果拥有正确的聚类个数, 但是将右上角的密度较小的方形类以及左上角的圆形类中的一部分数据划分成噪声数据,由 于在这种情况下,选择的Eps较小 将左上角同属于圆形类的数据划分成了类; 图的聚类结果有着较高的聚类精度,但是类簇个数是错误的,将类问题错分为类, 将个环形数据划分为一类;只需给定 Min pts,提出的算法就可以较好地划分包含不同大小 形状且密度相差较大的数据集,从而得到较好的聚类结果。 在数据集上的实验结果 冋时,我们从数据集中挑选了组数据、 和 ,数据描述如表所示。由」所选薮据集的属性个数较多,不使 于数据场等势线的可视化显示,在此仅将提出的算法同标准 和 算法 进行比较,考虑到 算法初始类中心选择的随机性,文中 的聚类指标均选 择次聚类结果的平均值。表~分别给出了在上述个数据集上各聚类算法的性能比较。 文中采用多个评价指标对聚类结果进行分析评价,指标有:分类正确率AC、 RI 和 ARI,其中AC的计算公式和文献定义的一致,P计算公式和文 献定义的相同,ARⅠ的计算公式与文献定义的一致。 表数据描述 数据集 样木数 属性数 表在下算法的性能比较 算法 算法 表在下算法的性能比较 算 算法 表在 下算法的性能比较 山国武花论文在丝 算法 表在下算法的性能比较 算法 算法 表在 下算法的性能比较 算法 算法 表在下算法的性能比较 算法 算法 通过比较表~,可以看出提出的算法在和 数据集上的裹类结果较好 均优于 算法和 算法;在和 数据集上的 聚类结果和 算法相当,但优于 算法;在 和 数据集上的聚 类结果比 算法略差一些,但也优于 算法得到的聚类结果。就整体而言, 提出的算法的聚类结果在各个评价指标下均高于 算法 结论 本文通过将数据场考虑全局信息的优势结合到 算法中,并引入势差的概念, 在聚类过程中动态的确定每个类的,使得改进后的 算法不仅可以较好识别 些不规则的类簇,还可以较好地识别一些密度差别较人的数据集。山于算法中的 需要人为给定,如何合理的给定 并减小时间复杂度,以使得算法更加完善将是下 个讨论的问题 参考文献 李徳毅杜鹢不确定性人工智能北京国防工业岀版社 浍文燕李德毅王建民一种基于数据场的层次聚类方沄电子学报 余建桥基丁数据场改进的聚类算法计算机科学 王海军邓羽王丽关兴良基丁数据场的均值聚类方法研究武汉大学学报.信息科学 版 山国武花论文在丝 李学苗夺谦冯琴荣基于数据场的粗糙亵类算法计算机科学 李春芳刘连忠陆震基于数据场的概率神经网络算法电子学报 梁吉业白亮曹付元基于新的距离度量的 聚关算法计算机研究与发展

...展开详情
试读 10P 论文研究-基于数据场的改进DBSCAN聚类算法 .pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    img

    关注 私信 TA的资源

    上传资源赚积分,得勋章
    最新推荐
    论文研究-基于数据场的改进DBSCAN聚类算法 .pdf 15积分/C币 立即下载
    1/10
    论文研究-基于数据场的改进DBSCAN聚类算法 .pdf第1页
    论文研究-基于数据场的改进DBSCAN聚类算法 .pdf第2页
    论文研究-基于数据场的改进DBSCAN聚类算法 .pdf第3页

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

    15积分/C币 立即下载 >