论文研究-自动确定聚类中心的密度峰值算法.pdf

所需积分/C币:46 2019-09-10 10:00:21 743KB .PDF
收藏 收藏 1
举报

密度峰值聚类算法(Density Peaks Clustering,DPC),是一种基于密度的聚类算法,该算法具有不需要指定聚类参数,能够发现非球状簇等优点。针对密度峰值算法凭借经验计算截断距离[dc]无法有效应对各个场景并且密度峰值算法人工选取聚类中心的方式难以准确获取实际聚类中心的缺陷,提出了一种基于基尼指数的自适应截断距离和自动获取聚类中心的方法,可以有效解决传统的DPC算法无法处理复杂数据集的缺点。该算法首先通过基尼指数自适应截断距离[dc],然后计算各点的簇中心权值,再用斜率的变化找出临界点,这一策略有效避免了通过决策图人工选取聚类中心所带来的误差。实验表明,新算法不仅能够自动确定聚
王淖,张桂珠:自动确定聚类中心的密度峰值算法 法对非聚类中心点的一步归并策略也会造成迕锁反应, 自动选择聚类中心 旦一个数据点分配错误可能会造成一系列的样本数定义为了综合考虑a2和的影响,定义y=9 据集类簇错误 e!Ny值越大越有可能是聚类中心。对于{y,进 自适应距离自动获取聚类申心的密度峰值行降序排列对排序后的点进行标号,川来表示标号 然后绘制γ关于i的函数图像,称之为y的排序图”。 法() 定义临界点p是y的排序图中y-与y前 在算法屮截断距离的进取是计算局部密度,点/湾是条件 基于基尼不纯度的自适应截断距离 后整体变化最大的点。本文采用斜率k来表示变化程 度ρ的关健。局部密度的大小将直接影响最终的聚类 效果。传统的密度峰值算法仅仅考虑每个数据点的局 D=mx2-111:=1.2…,n=2 部密度,没有考虑整个数据集的分布情况。导致 =a(m=2 算法不能够有效地应对复杂的数捃集,为了改进 a()=>4-|k 算法的这一缺陷,必须找到一种描述数据集整体分布情 况的指标。文献提出了一种用熵优化点势能的方其中k表示第个点和第+1个点之间线段的斜率, 法来找到最优截断距离d。本文提出利用基尼不纯度()表示在y排序图中相邻两点之间斜率差的总和, 求出最优截断距离d,对比传统的算法其有更好表示在y排序图中相邻点的斜率差的平均值,当z是大 的聚类效果。 于等于β斜率差的平均值的点中,序号最大的点时, 在文献中提出了一种用高斯函数计算点势能是临界点。 的方法如公式()所示,在数据集中,势能较大的点位于 定义疑似聚类中心点的定义为 密集区域,势能较小的点位于稀疏区域,这说明数据城 p2={q>yp9=1,2,…,P 的势能和数据屮的点局部密度具有类似的效果。因此 疑似聚类中心包含了实际的聚类中心,但也包含了 利用每个点的势能来佔算整体数据集的势能,以此作为其他非聚类屮心点。如图所示,图是 数 衡量数据集整体分布情况的指标。对J数据集{1,x2…,据集由于将疑似的聚类中心作为实际聚类中心,导致右 xn},每一个点的势能计算公式为: 下角本来属于一类的数据变成了两类。因此在用疑似 聚类中心点得到聚类结果后,还需要判断是否一个簇被 错误地分为多个子簇 在数据域屮,如果数据的势能分布较均匀,数据分 布的不确定性较大,数据的不纯度较大。如果数据的势 能分布不均匀,数据分布的不确定性较小,数据的不纯 度较小。数据的不纯度可以由基尼指数表示,数据域中 基尼指数的计算公式为 其中z=26表示数据域总的势能大小,6,表示每 点的势能。对比公式()和公式(),发现计算点势能的 方法与算法屮计算局部密度的方法相似,为了取 图 错误的聚类结果 得最优的截断距离d,等价于取得最优的a(称之为影 在算法中,实际的聚类中心往往分布在相对 响因子)。联合公式()和公式(),可得当σ从逐渐高密度区域内,并且实际聚类中心间的相对距离较远。 增人,基尼指数G随着影响囚子a的变化而变化。当因此在个高密度区城屮,如果存在多个疑似聚类屮 基尼指数值G取最小值时,反映了数据的不纯度最小,心,则这些疑似聚类中心通常会比较接近。基于密度峰 不确定性最小,数据势能分布不均勺,数据的势能差别值算法的这种特点,把查找到属于某个簇的第一个疑似 最大,更易于聚类,这是理想的结果。因此基尼指数值聚类中心(y:值最大),作为该簇的唯一实际聚类中 最小时取得最优影响因子a的值。以最优的a值作为心。进行聚类,依次判断剩余的点与第一个点的最短距 截断距离d的值,从而达到白适应截断距离的效果。 离和截断距离d2的大小,如果小于a,则将该点作为错 () 计算机工程与应用 选的聚类中心点,当作簇成员处理,如果大于,则该 点作为其他簇的聚类中心。最终可以剔除多余的聚类 中心,从而准确地选择出实际的聚类中心 实验结果与分析 为了验证算法的效果,分别在人工数据集和 数据集上进行测试,对比传统的密度峰值算法。实 验环境为 位操作系统, 内存,使用 进行仿 真实验 人工数据集 算法在的决策图 仿真实验用到的人工数据集共有个,如表所 示。和用表的数据,分别运行算法和算 法,实验结果如图至图所示。 表人工数据集 数据集样本数维数 图 算法在上错误的聚类结果 辱 癟兴 图 算法在上错误的聚类结果 算法在上正确的聚类结果 图 算法在上正确的聚类结果 人工数据集的样本数、类别数最少,理论上聚类 难度最低。但由于其数据集整体分布较为特姝(线性环 状分布)增加了聚类难度。如图所示,用传统的 算法并不能得到正确的聚类结果。利用本文提出的 算法在的决策图 王淖,张桂珠:自动确定聚类中心的密度峰值算法 将算法用于人⊥数据集,得到图所示 的聚类结果,可以看到 算法准确地判断出数据 集的个类。 y 算法和算法在数据集上造成了不 同的聚类结果。分析有三方面原因:其一,数据集 较复杂(样本数较多),生成的决策图较复杂,如图所 示,人工选取难以准确选取聚类中心,因此导致图错 误的聚类结果而算法根据斜率差的变化自动 选取潜在聚类屮心,避免了对于复杂数据集人工难以准 确选取聚类中心的问题。其二,算法凭经验选取截 算法在上错误的聚类结果 跑时nB返应复数性对于数 不恰 显。而 算法利用基尼指数自适应截断距离不仅 仅考虑了点的局部密度,而且考虑了数据集整体的分布 情况,计算出的截断距离更合理,合适的截断距离更有 利于聚类。这是 算法的另个优势。其三 算法一口选取聚类中心锖误,就会导致聚类结果的错 误。如图所示,决策图中人工选取的错误的聚类中心 点,直接导致图聚类结果错误。而算法剔除潜 在聚类中心的方法,能有效避免算法一步归并产 生错误的连锁反应。因此对于数据集 算法 有更好的聚类效果。 图 算法在上正确的聚类结果 数据集 算法对人工数据集进行聚类,得到正确的聚类 实殓采用的数据集是机器学习数据库的 结果如图所示。造成两种算法聚类结果差异的原因 。详细信息如表所示 是该数据集分布特殊,算法选取的截断距离不当, 表 数据集 步归并的策略造成连锁反应,没有考虑到数据集整体 数据集 样本数维数类数 分布情况。 人L数据集类簇间的间隔较大,有利于聚类 但是相对于,样本数量较大,类别数较多,增加了聚 将算法和算法应用于上述数据集,并且 类难度。图是算法对人工数据集聚类后所 比较聚类结果。本文采用 和 作为聚 得到的决策图,图是算法人工选取聚类中心之后类结果评判标准。数据所属的类可看作是集合N中 所得到的聚类结果,如图所示,中心部分的个应该等待查询的项;由算法产生的族C可看作是集合N中 是属于不同的类,但由于人T选取聚类中心有主 检索到的项;N是簇C中类i的数量。类i和簇Cb 观性,导致了错误的聚类结果。 的精确率和召回率如下。 图是利用本文提出优化截断距离自动选取聚类 精确率: Precision.C=N/N 屮心的 算法对人工数据集聚类结果,如 召回率: Recall.o=N/N 图所示,算法准确地识别出了数据集的类 F measures, Ck= 别数,排除人工选取聚类中心的主观因素,得到正确的 (a+l)Precision(i, CkyRecall(i, Ck 聚类结果 a Precision(i, C: ) Recall(i, Cy 对于人工数据集,相对于和样本数和类 由公式()可知, 是精确率和召回率的 别数最多,数据集整体分布最复杂,聚类难度最大。用加权调和平均值,其中a是参数。 算法对其进行聚类时,生成的决策图比较复杂,人 为了考察算法与传统的算法的聚类效 选取聚类中心可能会导致错误的聚类结果。如图果,本文采用上述类数据集进行测试,实验统计 所示,图是算法村数据集的决策图,人L选了准确率 和 实验结果如图、图 取聚类中心十分困难,得到的错误结果如图所示 所示 () 计算机工程与应用 法具有更高的准确率。 参考文献 图 谢娟英,鲁肖肖,屈亚楠,等粒计算优化初始聚类中心的 聚类算法计算机科学与探索, 冯振华,钱雪忠,赵娜娜 种针对多密 度聚类的 改进算法计算机应用研究,() 谭颖,胡瑞《,殷国富多密度阈值的 改进算法 图 计算机应用,,() 算法在数据集 上的准 陈刚.刘秉权,吴岩一种基于高斯分布的自适应 确率与算法相比有明显的提升。在 算法微电子学与计算机, 方 刘淑芬,孟冬雪,工晓燕基于网格单元的 算法 面,对于数据集 算法提升效果明显,对 吉林大学学报:工学版,() 于数据集 算法相对于算法略有 提升。通过分析可知 算法克服了传统算法 人工选取聚类中心的主观性和不确定性,同时改善了 刘颛莹,刘培玉,王智吴,等一种基于密度峰值发现的文 算法选取截断距离d′无法应用亍多个复杂场景这 本聚类算法山东大学学报:理学版 一缺陷,因此算法在大部分数据集中效果提升 蒋礼青,张眀新,郑金龙,等快速搜索与发现密度峰值 明显。 聚类算法的优化研究计算机应用研究,() 结语 马春来,单洪,乌涛一种基于簇中心点自动选择策略的 针对于传统的密度峰值算法(算法)选取截断 密度峰值聚类算法计算机科学,( 距离d难以适应复杂的数据集,并且算法人工难 谢娟英,高红超,谢维信近邻优化的密度峰值快速搜 以准确地选取聚类中心的缺陷,本文提出了一种白动选 索聚类算法中国科学:信息科学,(): 择聚类屮心的 算法,该算法不仅保留了算法 简单高效的特点,还克服了算法的缺点。在人工 数据集和数据集卜的实验结果证明,算法具 有更好的适应性,对于复杂的数据集,能够更好地计算 出合适的截断距离d和聚类中心点,并且对比算

...展开详情
试读 6P 论文研究-自动确定聚类中心的密度峰值算法.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    weixin_38743481 如果觉得有用,不妨留言支持一下
    2019-09-10
    • 至尊王者

      成功上传501个资源即可获取
    关注 私信 TA的资源
    上传资源赚积分,得勋章
    最新推荐
    论文研究-自动确定聚类中心的密度峰值算法.pdf 46积分/C币 立即下载
    1/6
    论文研究-自动确定聚类中心的密度峰值算法.pdf第1页
    论文研究-自动确定聚类中心的密度峰值算法.pdf第2页

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

    46积分/C币 立即下载 >