第1期 周治平，等：一种改进的自适应快速AF-DBSCAN聚类算法 ·95· 图1中，k=1,2,…,45,根据k-dist分布曲线可 其中，高斯曲线拟合方法的效果最佳，但是由 以看出，k=4的dist,曲线可以反映出其他dist曲线 于概率分布的拟合精度过低，不可用于全局参数 的形状。本文选择k=4的dist(k-最近邻距离)的 Eps的估计。拟合结果为SSE:312.7,R-square: 数据进行统计分析，dist,的概率分布图2所示。 0.6755,调整R-square:0.6514,RMSE:3.403,参数 SSE和RMSE越接近0拟合越准确；R-square和调 0.20 整后的R-square越接近于1越准确；高斯拟合曲线 0.18 0.16 如式(4)所示： 0.14 f(x)=a x exp(-((x-b)/c)2) (4) 0.12 0.10 根据KNN升序排列曲线确定Eps,对dist,曲线 0.08 进行拟合。对于升序排列得到KNN分布数据，采用 0.06 0.04 3种拟合方法进行曲线拟合。实验发现高斯拟合精 0.02 02030405000700 度高，但拟合阶数高，计算复杂度高：傅里叶拟合精 0.1 度不高：而多项式拟合不仅拟合阶数低，而且拟合精 归一化k-dist值 度高，计算复杂度低，拟合结果为SSE:0.04636,R 图2dist,(k=4)概率分布 square:0.9883,调整R-square:0.988,RMSE: Fig.2 Probability distribution of dist (k=4) 从图1可以看出，任何一条曲线都是在平缓变 0.01788,如图4所示。多项式曲线拟合如式(5) 化后急剧上升，dist中大部分值落在一个比较密集 所示。 f(x)=ax bx cx2+dx +e (5) 的区域内，因此可以判断ds,中大部分值应落在一 个比较密集的区域内（曲线平缓段）。如果可以通 1.0 ·isk升序排列数据点· 0.9 一多项式拟合 过数学方法找出dist,中平缓变化到急剧上升处的 0.8 点，或者dist概率分布最为密集的区域，则可确定扫 描半径参数Eps,所以本文选择图1中dist拐点处 的值为Eps。由图2可以得到dist的概率分布情 单0.5 况，假如能够通过数学方法找到分布曲线的峰值，也 04 可以用峰值点所对应的k-最近邻距离值（横坐标刻 0.3 度)作为Eps。 0.2 对于概率分布数据，通过分析数据集的统计特 0.1 50 100 150 性，建立统计模型对数据集进行曲线拟合[4。本文 升序排列数据点个数 通过实验对概率分布使用傅里叶、高斯和多项式3 图4多项式拟合曲线 种典型曲线拟合方法，如图3所示。 Fig.4 Polynomial fitting curves 25 归一化KNN距离分布 根据多项式拟合曲线，求解曲线的拐点，对y 多项式拟合 20 傅里叶拟合 求二次导可得f(x)”=12ax2+6bx+2c,求解二次导方 高斯拟合 15 程得x的解为，=-6±V36-96a 。由于较小的 24a 10 值为靠近边界的点，取x解中较大的值，舍去较小的 值，将其带入式(5)，可以得到Eps=f八xo)。Eps确 定后，需要确定MinPts的值。根据每个点邻域数据 点的统计分布特性，依次计算出每个点的Es邻域 的对象数量：计算数据对象的数学期望，即MinPts, 0.2 0.40.6 0.8 1.0 如式(6)所示： 归一化k-dist值 (6) 图3归一化KNN分布拟合曲线 n i=1 Fig.3 Fitting curves of normalized KNN distribution 式中：P,表示在点i的Eps邻域的点数。图 １ 中，ｋ ＝ １，２，…，４５，根据 ｋ⁃ｄｉｓｔ 分布曲线可 以看出，ｋ ＝ ４ 的 ｄｉｓｔ ４曲线可以反映出其他 ｄｉｓｔ ｋ曲线 的形状。 本文选择 ｋ ＝ ４ 的 ｄｉｓｔ ｋ（ ｋ⁃最近邻距离） 的 数据进行统计分析，ｄｉｓｔ ４ 的概率分布图 ２ 所示。 图 ２ ｄｉｓｔｋ（ｋ＝ ４）概率分布 Ｆｉｇ．２ Ｐｒｏｂａｂｉｌｉｔｙ ｄｉｓｔｒｉｂｕｔｉｏｎ ｏｆ ｄｉｓｔｋ（ｋ＝ ４） 从图 １ 可以看出，任何一条曲线都是在平缓变 化后急剧上升，ｄｉｓｔ ｋ中大部分值落在一个比较密集 的区域内，因此可以判断 ｄｉｓｔ ｋ中大部分值应落在一 个比较密集的区域内（曲线平缓段）。 如果可以通 过数学方法找出 ｄｉｓｔ ｋ中平缓变化到急剧上升处的 点，或者 ｄｉｓｔ ｋ概率分布最为密集的区域，则可确定扫 描半径参数 Ｅｐｓ，所以本文选择图 １ 中 ｄｉｓｔ ｋ拐点处 的值为 Ｅｐｓ。 由图 ２ 可以得到 ｄｉｓｔ ｋ 的概率分布情 况，假如能够通过数学方法找到分布曲线的峰值，也 可以用峰值点所对应的 ｋ⁃最近邻距离值（横坐标刻 度）作为 Ｅｐｓ。 对于概率分布数据，通过分析数据集的统计特 性，建立统计模型对数据集进行曲线拟合［１４］ 。 本文 通过实验对概率分布使用傅里叶、高斯和多项式 ３ 种典型曲线拟合方法，如图 ３ 所示。 图 ３ 归一化 ＫＮＮ 分布拟合曲线 Ｆｉｇ．３ Ｆｉｔｔｉｎｇ ｃｕｒｖｅｓ ｏｆ ｎｏｒｍａｌｉｚｅｄ ＫＮＮ ｄｉｓｔｒｉｂｕｔｉｏｎ 其中，高斯曲线拟合方法的效果最佳，但是由 于概率分布的拟合精度过低，不可用于全局参数 Ｅｐｓ 的 估 计。 拟 合 结 果 为 ＳＳＥ： ３１２． ７， Ｒ⁃ｓｑｕａｒｅ： ０．６７５ ５，调整 Ｒ⁃ｓｑｕａｒｅ：０．６５１ ４，ＲＭＳＥ：３．４０３，参数 ＳＳＥ 和 ＲＭＳＥ 越接近 ０ 拟合越准确；Ｒ⁃ｓｑｕａｒｅ 和调 整后的 Ｒ⁃ｓｑｕａｒｅ 越接近于 １ 越准确；高斯拟合曲线 如式（４）所示： ｆ（ｘ） ＝ ａ × ｅｘｐ（ － （（ｘ － ｂ） ／ ｃ） ２ ） （４） 根据 ＫＮＮ 升序排列曲线确定 Ｅｐｓ，对 ｄｉｓｔ ４ 曲线 进行拟合。 对于升序排列得到 ＫＮＮ 分布数据，采用 ３ 种拟合方法进行曲线拟合。 实验发现高斯拟合精 度高，但拟合阶数高，计算复杂度高；傅里叶拟合精 度不高；而多项式拟合不仅拟合阶数低，而且拟合精 度高，计算复杂度低，拟合结果为 ＳＳＥ：０．０４６ ３６，Ｒ⁃ ｓｑｕａｒｅ： ０．９８８ ３， 调 整 Ｒ⁃ｓｑｕａｒｅ： ０．９８８， ＲＭＳＥ： ０．０１７ ８８，如图 ４ 所示。 多项式曲线拟合如式（ ５） 所示。 ｆ（ｘ） ＝ ａｘ ４ ＋ ｂｘ ３ ＋ ｃｘ ２ ＋ ｄｘ ＋ ｅ （５） 图 ４ 多项式拟合曲线 Ｆｉｇ．４ Ｐｏｌｙｎｏｍｉａｌ ｆｉｔｔｉｎｇ ｃｕｒｖｅｓ 根据多项式拟合曲线，求解曲线的拐点，对 ｙ 求二次导可得 ｆ（ｘ）″＝ １２ａｘ ２＋６ｂｘ＋２ｃ，求解二次导方 程得 ｘ 的解为 ｘ０ ＝ －６ｂ± ３６ｂ ２－９６ａｃ ２４ａ 。 由于较小的 值为靠近边界的点，取 ｘ 解中较大的值，舍去较小的 值，将其带入式（５），可以得到 Ｅｐｓ ＝ ｆ（ ｘ０ ）。 Ｅｐｓ 确 定后，需要确定 ＭｉｎＰｔｓ 的值。 根据每个点邻域数据 点的统计分布特性，依次计算出每个点的 Ｅｐｓ 邻域 的对象数量；计算数据对象的数学期望，即 ＭｉｎＰｔｓ， 如式（６）所示： ＭｉｎＰｔｓ ＝ １ ｎ ∑ ｎ ｉ ＝ １ Ｐｉ （６） 式中：Ｐｉ 表示在点 ｉ 的 Ｅｐｓ 邻域的点数。 第 １ 期 周治平，等：一种改进的自适应快速 ＡＦ⁃ＤＢＳＣＡＮ 聚类算法 ·９５·