logo资料库

SA2DBSCAN:一种自适应基于密度聚类算法.pdf

发布时间：2022-05-30 发布人：admin 分类：说明书 资料大小：0.26M 资料格式：pdf 举报 版权申诉
第1页 / 共9页
第2页 / 共9页
第3页 / 共9页
第4页 / 共9页
第5页 / 共9页
第6页 / 共9页
第7页 / 共9页
第8页 / 共9页
资料共9页，剩余部分请下载后查看
    第 26 卷第 4 期 2009 年 7 月 中 国 科 学 院 研 究 生 院 学 报 Journal of the Graduate School of the Chinese Academy of Sciences Vol. 26 July 　No. 4 2009 文章编号 :1002 1175 (2009) 04 0530 09 3  2 SA DBSCAN :一种自适应基于密度聚类算法 夏鲁宁 　荆继武 (中国科学院研究生院 , 信息安全国家重点实验室 ,北京 100049) (2008 年 6 月 26 日收稿 ; 2008 年 12 月 25 日收修改稿) Xia L N,Jing JW. SA Chinese Academy of Sciences ,2009 ,26( 4) :530～538. DBSCAN :A self adaptive density based clustering algorithm[ J] . Journal of the Graduate School of the 摘 　要 　DBSCAN 是一种经典的基于密度聚类算法 ,能够自动确定簇的数量 ,对任意形状的簇 都能有效处理. DBSCAN 算法需要人为确定 Eps 和 minPts 2 个参数 ,导致聚类过程需人工干预 才能进行. 在 DBSCAN 的基础上提出了 SA DBSCAN 聚类算法 ,通过分析数据集统计特性来自 动确定 Eps 和 minPts 参数 ,从而避免了聚类过程的人工干预 ,实现聚类过程的全自动化. 实验 表明 ,SA 关键词 　数据挖掘 ,聚类 ,DBSCAN ,SA 中图分类号 　TP181 DBSCAN 能够选择合理的 Eps 和 minPts 参数并得到较高准确度的聚类结果. DBSCAN 1 　概述 数据挖掘作为一种从大量数据中发现感兴趣信息的技术 ,已经得到日益广泛的应用. 聚类是一种重 要的数据挖掘技术 ,其任务是将数据集分成若干个簇 ,同一个簇中的数据具有较高的相似性 ,而不同簇 中的数据之间的相似性较低. 目前已经存在的聚类算法大致可以分为 4 种 类 型 : ( 1) 基 于 划 分 的 聚 类 算 法 , 如 k means[1 ] 、 medoids[2 ] 等. 这种算法需要设定簇的数量 ,根据对象间的相似性将每个对象划归最近的簇. 这种算法 k 能够发现超球状的簇. (2) 层次聚类算法. 层次聚类可以从 2 个方向产生 ,第一是凝聚 ,首先将所有对象 标记为簇 ,然后逐次合并距离最小的簇 ;第二是分裂 ,先将整个数据集视为一个簇 ,然后逐次分裂样本较 多的簇. 层次聚类需要人为设定终止条件 ,即凝聚或分裂到何种程度为止. 根据簇相似性的不同定义 ,层 link) 、组平均 (group average) 、Ward 方法 、BIRCH 和 CURE[3 ] 次聚类算法有单链 (single 等. (3) 基于统计模型的算法 ,如期望最大化 ( EM) [3 ] 算法. 这类算法基于数理统计理论 ,假定数据集是由 一个统计过程产生的 ,并通过找出最佳拟合模型来描述数据集. (4) 基于密度的算法 ,其中心思想是寻找 数据集中被低密度区域隔开的高密度区域 ,并将每个独立的高密度区域作为一个簇. 根据对密度的不同 定义 ,典型算法有 DBSCAN[4 ] 、OPTICS[5 ] 、DENCLULDE[6 ] 等. link) 、全链 (complete 基于密度的聚类方法以数据集在空间分布上的稠密程度为依据进行聚类 ,无需预先设定簇的数量 , 因此特别适合于对未知内容的数据集进行聚类. DBSCAN 是一种经典的基于密度聚类算法 ,它以超球状 区域内数据对象的数量来衡量此区域密度的高低. DBSCAN 算法能够发现任意形状的簇 ,并有效识别离 群点 ,但聚类之前需要人工选择 Eps 和 minPts 2 个参数. 已有文献提出了若干方法用于判定 Eps 参数 ,但 国家高技术研究发展计划 (863) 项目 (2003AA144050) 资助 mail : halk @is. ac. cn E © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
    　第 4 期 夏鲁宁 ,荆继武 :SA DBSCAN :一种自适应基于密度聚类算法 　　 　 135 并不能适应不同统计特性的数据集 ,对于 minPts 参数的使用也缺乏讨论. 本文在 DBSCAN 的基础上 ,提 出一种通过分析数据集的统计特性来自适应确定 Eps 和 minPts 的新方法 ,从而做到聚类过程的全自动 化. 我们将这种方法称为自适应 DBSCAN ( self based spatial clustering of applications with noise ,简称 SA adaptive density DBSAN) . 本文中定义的主要符号如表 1 : 符号 N Eps ( p) | N Eps ( p) | dist ( i , j) DISTn ×n dist k ( p) Dist k 表 1 　符号定义 含义 对象 p 的 Eps 邻域 ,即以对象 p 为中心 ,Eps 为半径的超球状区域内的对象集合 集合 N Eps ( p) 中的对象个数 对象 i 和对象 j 之间的距离 对象间距离矩阵 ,其元素 dist ij = dist ( i , j) 对象 p 到第 k 个最近的对象之间的距离( k 最近邻距离) 数据集中所有对象的 k 最近邻距离集合 KNNn ×( n - 1) 最近邻距离矩阵 ,Dist k 位于 KNNn ×( n - 1) 第 k 列 Eps k noise k Noise minPts = k 时的 Eps 值 minPts = k ,Eps = Eps k 时的噪声点数量 以 noise k 为第 k 个分量的向量 　　本文第 2 节介绍 DBSCAN 算法及其相关研究工作 ,第 3 节描述 SA 了 SA DBSCAN 算法的实验结果 ,第 5 节就存在的一些问题做进一步讨论 ,最后总结全文. DBSCAN 的算法细节 ,第 4 节给出 2 　相关工作情况 2. 1 　DBSCAN 算法 DBSCAN 是一种经典的基于密度聚类算法 ,可以自动确定簇的数量 ,并能够发现任意形状的簇. DBSCAN 的主要定义如下. (1) 定义 1 ( Eps 邻域) 　给定一个数据对象 p , p 的 Eps 邻域 N Eps ( p) 定义为以 p 为核心 ,以 Eps 为半 径的 d 维超球体区域 ,即 N Eps ( p) = { q ∈ D | dist ( p , q) ≤Eps} , (1) 其中 , D Rd 为 d 维实空间上的数据集 ,dist ( p , q) 表示 D 中的 2 个对象 p 和 q 之间的距离. (2) 定义 2 (核心点与边界点) 　对于数据对象 p ∈D ,给定一个整数 minPts ,如果 p 的 Eps 邻域内的 对象数满足| N Eps ( p) | ≥minPts ,则称 p 为 ( Eps , minPts) 条件下的核心点 ;不是核心点 ,但落在某个核心 点的 Eps 邻域内的对象称为边界点. (3) 定 义 3 ( 直 接 密 度 可 达) 　给 定 ( Eps , minPts) , 如 果 对 象 p 和 q 满 足 : ( a) p ∈N Eps ( q) ; (b) | N Eps ( q) | ≥minPts (即 q 是核心点) ,则称对象 p 是从对象 q 出发 ,直接密度可达的. (4) 定义 4 (密度可达) 　给定数据集 D ,当存在一个对象链 p1 , p2 , p3 , …, pn ,其中 , p1 = q , pn = p ,对 于 pi ∈D ,如果在条件 ( Eps , minPts) 下 pi + 1 从 pi 直接密度可达 ,则称对象 p 从对象 q 在条件 ( Eps , minPts) 下密度可达. 密度可达是非对称的 ,即 p 从 q 密度可达不能推出 q 也从 p 密度可达. (5) 定义 5 (密度相连) 　如果数据集 D 中存在一个对象 o ,使得对象 p 和 q 是从 o 在 ( Eps , minPts) 条件下密度可达的 ,那么称对象 p 和 q 在 ( Eps , minPts) 条件下密度相连. 密度相连是对称的. (6) 定义 6 (簇和噪声) 　由任意一个核心点对象开始 ,从该对象密度可达的所有对象构成一个簇. 不属于任何簇的对象为噪声. © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
    235 中国科学院研究生院学报 第 26 卷 2. 2 　已有改进工作 DBSCAN 聚类的准确性与 Eps 和 minPts 2 个参数的选择有关. 给定 minPts ,选择的 Eps 越小 ,发现的 簇的密度越高. 如果选择过小的 Eps ,则会导致大量对象被错误地标记为噪声 ,而一个自然簇也被错误 地拆分成多个簇 ;如果选择了过大的 Eps ,则很多噪声被错误地归入簇 ,而分离的若干个自然簇也被错 误地合并为一个簇. 给定 Eps ,选择的 minPts 越大 ,发现簇的密度越高. 过小的 minPts 会导致大量对象被 标记为核心点 ,从而将噪声归入簇 ;过大的 minPts 会导致核心点数量减少 ,使得一些包含对象数较少的 自然簇被丢弃. DBSCAN 算法描述[4 ] 中给出的参数选择方法是设定 minPts = 4 ,通过观察法来判断 Eps. 对于 p ∈D 查找与 p 最近的第 minPts 个对象的距离 distminPts ( p) , p 遍历 D 得到集合 DistminPts = {distminPts ( p) | p ∈D} ,对 DistminPts 排序并绘图. 对于簇密度差异 不明显的数据集 ,DistminPts 的排序图一般为图 1 的形状. 观察图 中曲线的平缓部分 ,将处在 A 位置的值设定为 Eps. 显然 ,这种 方法需要用户的参与. Feng P. J . 等 人[7 ] 将 Halkidi M. 提 出 的 方 法[8 ] 采 用 到 DBSCAN 上. 仍假定 minPts ,而使用多个不同的 Eps 参数值进行 试聚类 ,然后评估各次聚类的有效性 (clustering validity) ,从中 选取最优的. 这种方法解决了自动选取 Eps 参数的问题 ,但时间复杂度增大 ,相当于做了多次 DBSCAN 运算. 而且 ,试聚类时 Eps 在多大范围内取多少个值也难以界定. 图 1 　排序后的 DistminPts集合 Yue S. H. 的研究中引入了距离分布的概念[9 ] . 仍假定 minPts = 4 ,计算数据集中每 2 个对象之间的距 n 个点对应的值. 这种方法仍需设定簇个数 c 的值 ,或者使用 离并排序 ,并取 Eps 为排序后第δ2 / (4 c) C2 Halkidi M 的方法来判断 c 值. Xu X. 等人则引入了密度分布的概念[10 ] . 假定每个自然簇中的对象都服从平均分布 ,通过网格取高 密度区域 ,并以原分布模型是否仍有效来衡量一个对象是否属于某个簇. 这种方法无需使用 Eps 和 minPts ,事实上是有别于 DBSCAN 的一种新聚类算法. 但是这种方法需要选择网格的大小 ,过大或过小的 网格都会造成结果失真. 在其他相关工作中 ,Ankerst M. 提出的 OPTICS 方法[5 ] 对所有对象按照密度可达距离排序 ,使得同一 个簇的对象相邻 ,从而在分布图中可以看到明显的簇特征 ,但未给出确定簇的算法 ;Lin C. Y. 采用了遗 传算法来估算 Eps[11 ] ,但时间复杂度较大 ,且仍假定 minPts 参数 ;蔡颖琨等人通过增加簇连接信息使得 DBSCAN 对输入参数的敏感性降低[12 ] ,但未能解决自动确定参数的问题 ;苏中等人则提出了逐级细化聚 类的方法[13 ] ,每次聚类动态调整参数 ,但初始参数仍需使用观察法[4 ] 确定. 基于以上描述 ,现有改进工作的局限在于无法真正自适应地确定合适的 minPts 和 Eps 参数. 本文在 DBSCAN 的基础上 ,提出一种通过分析数据集的统计特征来自适应确定 Eps 和 minPts 的新方法 ,从而做 到聚类过程的全自动化. 我们将这种方法称为 SA DBSCAN 算法. 3 　SA DBSCAN 算法细节 本节所有的绘图都基于一个包含 240 个对象的二维示例数据集 SampleD ,见图 5. SA DBSCAN 根据数据集本身的统计特性来判断 Eps 和 minPts 的取值. 首先需要计算距离分布矩阵 DISTn ×n : (2) ,表示数据集中的对象个数. DISTn ×n是 n 行 n 列的实对称阵 ,每个元素表示 D 中第 i 个对 DISTn×n = {dist ( i , j) | 1 ≤ i ≤ n ,1 ≤ j ≤ n} , 其中 , n = | D| 象到第 j 个对象的距离. © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
    　第 4 期 夏鲁宁 ,荆继武 :SA DBSCAN :一种自适应基于密度聚类算法 3. 1 　Eps 参数的自适应判别 　　 　 335 对 DISTn ×n的每一列排序并转置得到矩阵 KNN0 n ×n = sort (DISTn ×n )′. KNN0 n ×n 的每一列向量代表 数据集中所有对象到最近的第 k - 1 ( k 是列下标 , k = 1 ,2 , …, n) 个对象的距离集合. 其中第 1 列为全零 集合 , 因为每个对象到第 0 个最近对象的距离是到它自身的距离. 为了计算和绘图的方便 , 删除 KNN0 n ×n的第 1 列并对列向量排序 ,得到 KNNn ×( n - 1) : Π KNNn×( n- 1) = sort ( KNN0 n×n (1 :end ;2 :end) ) , 这样 , KNNn ×( n - 1) 的第 k ( k = 1 ,2 , …, n - 1) 列即数据集中所有对象的 k Sample D 数据集的 KNNn ×( n - 1) 矩阵的每一列 (排序后的 Dist k ) 绘图 ,得到图 2. (3) 最近邻距离集合 Dist k . 对 图 2 中可以看到 ,随着 k 的增加 ,排序后的 Dist k 曲线大致沿纵轴向上平移. 直观上理解 ,对于数据 集中的每个点 ,到第 k + 1 个最近邻的距离总是不小于到第 k 个最近邻的距离. 可以看到 ,任何一条曲 线都基本符合图 1 的形状. 事实上 ,图 1 就是图 2 中 k = 4 的曲线. 使用数学方法无法直接对 Dist k 曲线寻找图 1 的 A 点[6 ] . 但观察图 1 和图 2 ,可以发现任何一条曲线 都是在平缓变化后急剧上升 ,因此可以判断 Dist k 中大部分值应落在一个比较密集的区域内 (曲线平缓 段) . 仍取 k = 4 ,绘制 Dist k 的概率分布图如图 3 中的柱状图所示. 图 2 　KNN绘图 图 3 　Dist k( k = 4) 的概率分布 和 Inverse Gaussian 拟合曲线 　　由图 3 可以看到 Dist k 的概率分布情况. 假如能够通过数学方法找到分布曲线的峰值 ,则可以以峰 值点所对应的 k 最近邻距离值 (横坐标刻度) 为 Eps. 对于概率分布 ,可以用统计模型进行拟合. 经过多次实验发现使用 Inverse Gaussian 拟合的效果最 好 ,如图 3 中的拟合曲线所示. Inverse Gaussian 分布的概率密度公式为 P ( x) = λ 2πx3 e - λ( x - μ) 2 (2 xμ2) ,其 中λ和μ可以用最大似然估计[14 ] 获得. 为了获得峰值点 ,解微分方程 d P ( x) d x = 0 得到一个正数解 : x = μ 9μ2 + 4λ2 - 3μ2 2λ . 因此 ,当取 minPts = k 时 ,对 Dist k 进行 Inverse Gaussian 拟合 ,从而得到 μk Eps k = 9μ2 k + 4λ2 2λk k - 3μ2 k . (4) 3. 2 　minPts 参数的自适应判别 需要注意的是 ,使用上述的 Inverse Gaussian 拟合方法得到的 Epsk 并非处在图 1 的 A 处 ,而是大致 处在曲线平缓部分的中段 ,这个值要小于 A 处的取值. 如果仍假定 minPts = 4 进行聚类 ,很可能因为 Eps 取值过小而造成偏差. 因此 ,聚类时不宜再设置 minPts 为固定值. 为了确定 minPts 的合理取值 ,参考 Dist k 和 Eps k ( k = © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
    2 3 第 26 卷 3 中国科学院研究生院学报 3 3 3 3 435 3 3 3 3 3 1 ,2 , …, n - 1) ,计算当 minPts = k 时的噪声数量 ,记为 noise k . 噪声可以根据定义判断 :对于数据集 D 中 的对象 p ,当 minPts = k ,Eps = Eps k ,如果 p 满足 (1) | N Eps ( p) | < minPts ,即 p 不是核心点 ; (2) N Eps ( p) 内不 存在核心点 ,则 p 为噪声. 由此得到分别对应于 k = 1 ,2 , …, n - 1 的噪声数量 noise k . 将其按照 k 由小到大排列得到向量 Noise. 对 Noise 绘图如图 4 (a) 所示 : 图 4 　( a) Noise 曲线 ;( b) 等刻度后的 Noise 曲线 可以看到 , Noise 曲线是一条由急剧下降变化到平缓的曲线 , k 取值越大越贴近 0 ,也可能等于 0. 当 k = 1 时 ,因 Eps k 过小而导致大量对象被标记为噪声 ;随着 k 的增大 ,Eps k 逐渐增大至合理值 ,噪声数量 急剧减少 ;而随着 k 的变大 ,特别是超过了最小自然簇中对象个数以后 ,Epsk 将增大到几乎可以将所有 点合并到同一个簇中 ,噪声数量将逐渐趋于 0. 因此对于 Noise 曲线来说 ,并非噪声数量最少的就是合理 的 ,而应该取急剧下降部分到平缓部分的拐点 ,即图 4 (a) 中 C 点. 与图 1 中的 A 点类似 ,很难有数学方法精确定位 C 点. 观察图 4 (a) 可以发现 , Noise 曲线大致沿 45° 直线对称 ,而横 、纵坐标轴物理含义均是“对象个数”, 且取值范围相差不大. 构造等差数列 : K k 得到图 4 (b) . 根据图 4 (b) ,有 2 种方法可以大致确定 C 点 : = 为横坐标 , Noise 为纵坐标重新绘图 , n - 1 = max(noise k ) . 以 K 1 = min (noise k ) , k , …, k n - 1 ,其中 k , k 2 1 (1) Noise 对 K 数值求导 ,得到每个 noise i 处的导数 (实际上是曲线在横轴第 i 个点上的斜率) : noise i + 1 - noise i i + 1 - k i (noise i )′= k i0 点处的切线. . 寻找 i0 使得 (noise i 0 )′最接近 - 1 ,取 minPts = i0 . 图 4 (b) 中的 Line A 显示了在 (2) 寻找 i0 点使得 noise i 和 k i 0 0 近似相等 ,即图 4 ( b) 中 45°直线 Line B 与 Noise 曲线的交点. 取 minPts = i0 . 经过多次实验发现方法 (1) 受到曲线不规则变化的影响比较大 ,而方法 (2) 虽然简单 ,但在多数情况 下都能取到合适的值. 因此在 SA DBSCAN 中使用方法 (2) 确定 minPts. 4 　验证 4. 1 　聚类结果 使用 SA DBSCAN 算法对 SampleD 进行聚类的结果如图 5 所示. 为了验证 SA DBSCAN 的效果 ,实验 中我们使用了另外 2 个数据集. DS1 是一个 520 个对象的二维数据集 ,DS2 是一个 300 个对象的二维数 据集 ,二者以及他们的聚类结果如图 6 、图 7 所示. 由图 5 、图 6 、图 7 可以看到 ,SA DBSCAN 能够发现数据 集中的高密度区域并做出适当的簇划分. 这表明第 3 节所描述的算法能够有效选择合适的 Eps 和 minPts 参数. © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
    2 DBSCAN :一种自适应基于密度聚类算法 　　 　 535 Π Π 夏鲁宁 ,荆继武 :SA 图 5 　SampleD 和 SA DBSCAN聚类结果 图 6 　DS1 数据集和 SA DBSCAN聚类结果 图 7 　DS2 数据集和 SA DBSCAN聚类结果 　第 4 期 ΠΠ 　 　 　 为了测试 SA DBSCAN 应用在二维以上数据集的效果 ,我们还使用了美国加州大学信息与计算机科 DBSCAN 学系的 Iris 数据集 ①进行实验. 因多维空间绘图不便 ,本文不给出图形结果. Iris 数据集的 SA 聚类结果见表 2. ① http : www. ics. uci. edu mlearn MLSummary. html © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
    2 635 中国科学院研究生院学报 第 26 卷 4. 2 　时间特性分析和聚类准确度 DBSCAN 算法使用 R 树伸展算法进行搜索 ,时间复杂度为 O ( nlog n) . R 主要体现在对象间距离和 k 了这些计算结果 ,因此在聚类过程中不必重复计算. 相比于 DBSCAN ,SA 用于计算 Eps 和 minPts 参数的取值 ,这主要由 Inverse Gaussian 拟合引起. 最近邻距离的计算上. 在 SA 树伸展算法的时间复杂度 DBSCAN 中 DIST 矩阵和 KNN 矩阵已经包含 DBSCAN 需要额外的时间开销 我们采用有监督的 F 度量 (F Measure) 方法[15 ] 检测聚类的准确性. SampleD、DS1 、DS2 和 Iris 数据集的 means 和传统 DBSCAN 算 means 聚类的 k 参数取数据集中自然簇的个数 ,DBSCAN 取 minPts = 4 ,Eps = Eps4 . 所有的 0 + 512M DDR memory + Windows XP 平台上 ,使用 Matlab2006b 计算并测得. 各项聚类结果和准确度指标在表 1 给出 ,为了比较 ,对以上数据集同时进行 k 法聚类. 其中 k 实验数据都是在 Pentium IV3 表 2 　算法运算时间与聚类准确度对比 数据集 维数 对象个数 聚类算法 minPts Eps 运算时间 ms 准确度 ( %) SampleD DS1 DS2 Iris 2 2 2 4 240 SA DBSCAN DBSCAN k means 520 SA DBSCAN DBSCAN k means 300 SA DBSCAN DBSCAN k means 150 SA DBSCAN DBSCAN k means 9 4 \ 12 4 \ 12 4 \ 7 4 \ 0. 4032 0. 2347 \ 0. 1461 0. 0711 \ 0. 2798 0. 1548 \ 0. 4003 0. 3194 \ 1543 907 436 5758 3541 1269 2054 1232 488 669 342 229 93. 09 45. 41 61. 23 97. 78 41. 68 70. 27 96. 37 63. 95 100 88. 03 69. 5 89. 18 　　从表 2 可以看到 ,在时间性能方面 SA means ,这是由于增加了 Inverse Gaussian 拟合的计算量而引起的. 但也可以看出 ,SA DBSCAN 与 DBSCAN 的运算时间并不存在数 量级的差别 ;另外由于聚类过程仍与 DBSCAN 相同 ,所以任何对 DBSCAN 算法的优化也能用于改善 SA DBSCAN 的性能. DBSCAN 确实慢于 DBSCAN 和 k 从表 2 还可以看出 ,直接取 minPts = 4 ,Eps = Eps4 进行 DBSCAN 聚类的准确度不高 ,因此对 minPts 参 数进行判断而不是取固定值是必要的. 另外从准确度指标来看 ,在处理包含超球状簇的数据集 (DS2 、 Iris) 的时候 ,SA 簇的数据集 (SampleD、DS1) ,SA means 的能力 ;而对于 k DBSCAN 同样具有很高的准确度. means 不能有效处理的包含任意形状 DBSCAN 提供了不逊于 k 5 　进一步讨论 SA DBSCAN 算法对于簇密度差别很大的数据集聚类效果不理想. 这是 DBSCAN 本身存在的问题 , 由于使用了全局单一的参数 Eps 和 minPts ,导致在聚类过程中只有一个密度衡量指标. 如果 Eps 选择得 大 ,会导致高密度的自然簇被合并 ;而选择得小则导致低密度的自然簇被丢弃. SA DBSCAN 中根据噪声 点数量选择 minPts 的方法能够确保不会出现低密度自然簇被大面积丢弃的情况 ,但有可能造成高密度 自然簇的合并. 解决这个问题的可能方法是重新定义“密度”的概念 ,文献[3 ]提出了用 SNN 相似度代替 欧几里德距离来定义密度的方法 ,能够缓解这个问题. SA DBSCAN 在处理高维数据集 ,例如文本数据集时 ,效果不理想. 这是因为高维空间中数据对象的 分布更加随机 ,彼此之间欧几里德距离的差异变得不明显 ,很可能导致整个数据集被聚成单一的一个 簇. 对于文本数据集 ,使用余弦相似性来代替欧几里德距离一般可以达到理想效果 ;而使用 SNN 相似度 © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
    2 2 2 2 2 DBSCAN :一种自适应基于密度聚类算法 2 2 2 2 2 2 2 　第 4 期 夏鲁宁 ,荆继武 :SA 　　 　 735 也能够显著改善这方面性能. 6 　结束语 DBSCAN 是一种经典的基于密度聚类算法. 能够发现任意形状的簇 ,并能够自动确定簇的数量. DBSCAN 算法需要输入 Eps 和 minPts 2 个参数 ,导致聚类过程需人工干预才能进行. 本文在 DBSCAN 的 DBSCAN 聚类算法 ,通过 Inverse Gaussian 拟合判断 Eps 参 基础上 ,提出了自适应确定 Eps 和 minPts 的 SA 数 ,并通过分析噪声点数量的分布特征选择合适的 minPts. 使用 SA DBSCAN 无需人工输入参数 ,能够实 现聚类过程的全自动化 ;能够有效处理任意形状的簇 ,在超球状簇的处理上准确度不逊于 k means ;时间 复杂度稍高于 DBSCAN ,但不存在数量级差别. SA DBSCAN 聚类算法不需要用户输入参数 ,也无需任何有关当前数据集的先验知识 ,在自动聚类 的各个应用领域能够发挥重要作用 ,尤其对于在线数据的实时聚类有重要意义. 参考文献 [ 1 ] 　MacQueen J . Some methods for classification and analysis of multivariate observations[ C] ∥LeCam L , Neyman J , eds. Proceedings of the Fifth Berkeley Symposium on Mathematics , Statistics and Probability. Berkeley : University of California Press , 1967 :281 297. [ 2 ] 　Leonard Kaufman , Peter J Rousseeuw. Finding groups in data : An introduction to cluster analysis[M] . New York : Wiley Press , 2005. [ 3 ] 　Tan P N , Steinbach M , Kumar V 著 , 范 　明 ,范宏建 ,等译. 数据挖掘导论 ( Introduction to Data Mining) . 北京 : 人民邮电出版社 , 2006. [ 4 ] 　Ester M , Kriegel H P ,Sander J . A density based algorithm for discovering clusters in large spatial databases with noise [ C] ∥Simoudis E , Han JW , Fayyad UM , eds. Proceedings of the 2nd International Conference on Knowledge Discovery and Data Mining. Portland : AAAI Press , 1996 : 226 231. [ 5 ] 　Ankerst M ,Breunig M M , Kriegel H P. OPTICS : ordering points to identify the clustering structure[ C] ∥Alex Delis , Christos Faloutsos ,Shahram Ghandeharizadeh eds. Proceedings of the ACM SIGMOD’99 Int Conf on Management of Data. Philadelphia Pennsylvania : ACM Press , 1999 : 49 60. [ 6 ] 　Hinneburg A , Keim D A. An efficient approach to clustering in large multimedia databases with noise [ C] ∥Rakesh Agrawal , Paul Stolorz ,eds. Proceedings of the 4th Int Conf on Knowledge Discovery and Data Mining. New York : AAAI Press , 1998 : 58 65. [ 7 ] 　Feng P J , Ge L D. Adaptive DBSCAN based algorithm for constellation reconstruction and modulation identification [ C] ∥Keyun Tang , Dayong Liu ,eds. Proceedings of Radio Science Conference 2004. Beijing : Pub House of Electronics Industry , 2004 : 177 180. [ 8 ] 　Halkidi M , Vazirgiannis M. Clustering validity assessment : finding the optimal partitioning of a data set [ C] ∥Nick Cercone , Tsau Young Lin , 194. Xindong Wu eds. Proceedings of the 2001 IEEE International Conference on Data Mining. California : IEEE Computer Society , 2001 : 187 [ 9 ] 　Yue S H , Li P , Guo J D , et al . A statistical information based clustering approach in distance space[J ] . Journal of Zhejiang University Science , 2005 , 6A(1) : 71 78. [10 ] 　Xu X , Ester M , Kriegel H P , et al . A distribution based clustering algorithm for mining in large spatial databases [ C ] ∥Philip S Yu , eds. Proceedings of the 14th international conference on data engineering ( ICDE’98) . Orlando : IEEE Computer Society Press , 1998 : 324 331. [11 ] 　Lin C Y, Chang C C , Lin C C. A new density based scheme for clustering based on genetic algorithm[J ] . Fundamenta Informaticae , 2005 , 68 (4) : 315 331. [12 ] 　Cai Y K, Xie K Q , Ma X J . An improved DBSCAN algorithm which is insensitive to input parameters [J ] . Acta Scientiarum Naturalium Universitatis Pekinensis , 2004 , 40 (3) : 480 486 (in Chinese) . 　　　蔡颖琨 , 谢昆青 , 马修军. 屏蔽了输入参数敏感性的 DBSCAN 改进算法[J ] . 北京大学学报 :自然科学版 , 2004 , 40 (3) : 480 [13 ] 　Su Z , Ma S P , Yang Q , et al . Document clustering based on web 　　　苏 　中 , 马少平 , 杨 　强 ,等. 基于 Web [14 ] 　吴梅村编著. 数理统计学基本原理和方法[M] . 成都 : 西南财经大学出版社 , 2006. [15 ] 　Steinbach M , Karypis G, Kumar V. A comparison of document clustering techniques :technical report [ R ] . Minnesota : University of Minnesota Log Mining 的 Web 文档聚类[J ] . 软件学报 , 2002 , 13 (1) : 99 486. log mining[J ] . Journal of Software , 2002 , 13 (1) : 99 104 (in Chinese) . 104. Computer Science and Engineering , 2000. © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
    分享到：
    赞 收藏

    相关推荐

    资料库

    开发技术

    共收录19306份资料，累计14个分类，关注成员有19位，主要包括：Actionscript,Javascript,PHP,VB,Perl,Delphi,Python,C#,C,Java,C++,Web开发,硬件开发,其它

    热门标签

    Actionscript Javascript PHP VB Perl Delphi Python C# C Java C++ Web开发 硬件开发 其它

    最新资料