论文研究-DBSCAN算法中参数的自适应确定.pdf

所需积分/C币:14 2019-09-16 10:46:50 510KB .PDF
收藏 收藏
举报

DBSCAN算法需要人为确定[Eps]和[minPts]两个参数,导致聚类结果的准确度直接取决于用户对参数的选择,因此提出一种新的参数确定方法,采用非参数核密度估计理论分析数据样本的分布特征来自动确定[Eps]和[minPts]参数,避免了聚类过程的人工干预,实现聚类过程的自动化。理论分析和实验结果表明,该方法能够选择合理的[Eps]和[minPts]参数,并得到了较高准确度的聚类结果。
016,52(3) Computer Engineering and Applications计算机工程与应用 值,在聚类分析应用中表现为一个白然簇被错误地拆分 (17) 成多个簇。如果h太大,那么密度估计就把概率密度分 开得太散,这样会过滤掉一些重要特征,在聚类分析应 上式的思想运川在 DBSCAN算法中可以这样理 用屮表现为噪声被错误地归入簇,若干个自然簇也被错解:以对象x为中心、以h为半径的空间内存在的对象 误地合并成一个簇。 个数为 min pts,当用h替换l,就得到 min pts的值。即 依据上面的分析,假如能够通过数学方法确定h的 X-x 大小,则可以确定参数Fps的值。即 min pts=∑k h 统计学上,通常使用积分均方误差MSE()作为判4实验及结果比较 断密度估计量好坏的准则 聚类结果 MISE(h)=AMISE()+or 1+h (11) 实验环境:操作系统 Windows7,软件: Microsoft Inh Visual studio2010, Matlab2012,硬件: Intcr Corc i3 其中, jK(rdx ho JIs"(x)pdx CPU,内存4GB。为了验证本文算法的有效性和可行 Amise(h (12)性,使用本文算法对数据集 SampleD、Ds1和DS2分别 h 要最小化 AMISE(),必须把h设在某个中问值,小进行聚类。在进行算法有效性验证时,本文采用有监督 的F度量( F-Mcasuro)方法来检测。 Sampled是一个 可以避免f(x)有过大的偏差(太过光滑)。关于h最小 240个对象的二维数据集,DS1是一个520个对象的二 化AMSE(),最好是精确地平衡AMSE()中偏差项和维数据集,Ds2是一个300个对泉的二维数据集。三者 方差项的阶数 的聚类结果分别如图1~3所示。由图1~图3可以看到, 最优的窗宽是 自适应算法能够发现数据集屮的高密度区域并做岀适 K(x)dx (13)当的簇划分。这表明本文算法能够有效选择合适的Ep no["(x),'dr 和 min pts参数。 简便起见,定义 45//a噪言 R(g)=|g(z)dz (14) ▲簇2 公画 针对最小化AMSE(h)得到的最优带宽中含有未知 (Min Pts=9 量R(∫"), Liverman提出了拇指法则( rule of thumb)° 3.0Ep5=0.4032) ,2.5 把∫用方差和估计方差相匹配的正态密度替换。这就 等于用R(φ")σ估计R(f"),其中@为标准正态密度函 口 数。若取核函数为高斯密度核函数,σ使用样本方差 σ,利用拇指法则得到: 0.5101.52.02.53.03.54.04.55.0 (15) 32 min pts的自适应确定 图1 Sampled的聚类结果 根据核密度佔计理论,假设R是一个以某对黎为中 2.5 心,边长为l的极小立方体(或者半径为的极小球体) 现在要考虑的是落入立方体数据点的个数N。 定义一个核两数 噪声 (MinP=12·簇1 01461簇2 K()= (16) 1.0 簇 0,ml> 其中 该函数的意义是:数据维数为d维,当样本数据点 落入极小立方体时,函数值为1;其他情况下为0。所以 落入立方体数据点的总个数N就可以表示为 图2DS1的聚类结果 李宗林,罗可: DBSCAN算法中参数的自适应确定 2016,52(3)73 4.2进一步讨论 簇1 对于密度差别很大的数据集叫,三种算法的聚类效 簇 果都不怎么理想。这是基于密度的聚类算法本身存在 D (MinP(s= 12 AEpB=02798) 的问题。传统的 DBSCAN算法使用全局单一的参数Eps .2a s口 和 min pis,导致聚类过程中只有一个密度衡量指标,如 果Es选择过大,高密度的自然簇可能被合并;选择过 小則低密度的自然簇被丢弃。 I- DBSCAN算法虽然不会出现低密度自然簇被大 面积丢介的现象,但有可能造成高密度自然簇的合并。 本文算法虽然不会出现上述的极端情况,但核密度估计 在佔计边界区域的时候有可能出现边界效应。 图3DS2的聚类结果 本文算法利用核密度估计一组样本,f(x)的计算 SampleD、DSl和DS2数据集的各项聚类结果和准 确率在表1给出。为了测试本文算法在二维以上数据量随着样本数量的增大而增大,虽然增加了算法的准确 率,却也牺牲了时间复杂度。对于多数实际问题,可以 集的应用效果,使用Iris数据集进行实验,因多维空问 绘图不便,只给出聚类结果的数据形式,见表1。为了考虑将整个样本数据划分成多个等距网格小区间 比较,对以上数据集同时进行 I-DBSCAN算法和传虽然准确率会稍有影响,却也在准确率和复杂度之间取 DBSCAN算法聚类。其中, DBSCAN取 min pts=4 得一个平衡 EPDS=EpS4(EpS4指 min pts=4时的Eps值)。从表1可 以看出,直接取 min pts=4,E=Eps4进行 DBSCAN案5结束语 类的准确率不高,因此对参数进行判断而不是取固定值 DBSC∧N是一种经典的基于密度的聚类算法,可 是必要的 以自动确定簇的数量,并能够发现任意形状的簇。由于 DBSCAN算法需要人工输入EpS和 min pts两个参数 文达:道度导致聚类准确率低。本文在 DBSCAN的基础上,提 表聚类算法的准确度 数集维数对象数聚类算 Ep 出了自适应确定Es和 min pts参数的方法,通过核密 93.36 Sampled 2 88.23 度佔计理论建立合适的数学模型判断Eps和 min pts DBSCAN 0.2347 4 4541 此过程无需人工输入参数,能够实现聚类过程的全自动 本文算法0.146112 化。由于元需仟何有关当前数据集的先验知识,全靠数 DSI 520 I-DbSCAN 0.1435 学模型驱动,所以自动聚类的准确举较高,在各个应用 DBSCAN 0.071 1 41.68 本文算法0.279812 领域能够发挥重要作用,特别是对于在线数据的实时聚 300 I-DBSCAN0.29121291.8 类有重要意义。当然,本文算法也存在一些不足:对于 DBSCAN 0.1548 4 密度差别很大的数据集,聚类效果一般;算法计算复杂 本文算法0530489368度为O(n),对于处理大数据成本太高。因此,如何有 150I- DBSCAN0.40037 效解决这些问题将是下一步的研究方向。 DBSCAN 0.319 4 4 6950 从准确率来看,无论是处理包含超球状族的数据参考文献: 集(DS2和r还是任意形状簇的数据集(Sme和u1 Han Jiawei, Kamber M数据挖掘:概念与技术M,范明, DS1)的时候,本文算法和I- DBSCAN算法都有着不错 译北京:机械工业出版社,2012:306-309 的表现,本文算法的淮确率吏高,这得益于 DBSCAN算 [2] Fster M, Kricgcl H P, Sander J.a density-bascd algorith 法本身具有的优势。 for discovering clusters in large spatial databases with 对于较高维数据集(Iris),传统的 DBSCAN算法和 noise[C]/Simoudis E. Proceedings of the 2nd International - DBSCAN算法都显得效果不理想,这是因为高维数据 Conference on Know ledge Discovery and Data Mining 集中数据对象的分布更加随机,对象之间欧几里德距离 Portland:AAAl Iress. 1996: 226-231 的差异变得不明显,可能导致整个数据集被聚成单一的3] Yue s h,Lip, Guoj d,etal. a statistical information 个簇。而本文算法采用非参数密度估计理论,由于其 based clustering approach in distance space[J]Journal of 能够处理仁意的密度分布,无需对样本分布的形式做出 .hejiang University: Scicncc, 2005, 6(1): 71-78 假设,因此得到的聚类结果更加准确。 (下转80页)

...展开详情
试读 4P 论文研究-DBSCAN算法中参数的自适应确定.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    img
    • 至尊王者

      成功上传501个资源即可获取

    关注 私信 TA的资源

    上传资源赚积分,得勋章
    最新推荐
    论文研究-DBSCAN算法中参数的自适应确定.pdf 14积分/C币 立即下载
    1/4
    论文研究-DBSCAN算法中参数的自适应确定.pdf第1页
    论文研究-DBSCAN算法中参数的自适应确定.pdf第2页

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

    14积分/C币 立即下载 >