·1710 北京科技大学学报 第36卷 4.3参数敏感性 数据集CoverType则为40%~50%，对于数据集 算法运行时需要设置两个主要参数最近邻数k Cup99则为50%~70%.所以尽管数据集不同，在 和共享近邻数k,·为测试参数设置对算法执行结果 一定的比值范围内，SNDStream算法总可以取得较 的影响，实验使用前述的合成数据集和真实数据集. 好的聚簇质量.原因是当比值增大时，表示从k个 图10给出了参数设置与聚类质量之间的关系.其 近邻中选择较多的共享近邻（例如考虑从五个近邻 中横坐标是参数k。与k的比值，即0.5可以表示， 中选择四个共享近邻)，导致簇的分裂：而当比值减 数据点的最近邻数为10，那么共享近邻数应设为5. 少时，表示从k个近邻中选择较少的共享近邻，导致 从图10中可以看出，对于数据集DS1与DS2,在两 簇的合并 参数比值处于30%~40%时，聚簇质量较好，对于 100r a 100) 95 96 9 Cup99 90 DSI 88 85 DS2 80A CoverType 80 72 0.2 0.3 0.4 0.5 0.6 0.3 0.4 05 0.6 0.7 0.8 k店 图10参数与聚类质量 Fig.10 Parameters and clustering quality 图11给出了参数设置与运行时间之间的关系， 法的运行时间随k与k,的比值增大而显著增加，对 其中横坐标是参数k。与k的变化，考察在取得较好 于数据集CoverType与数据集Cup99同样如此.因 的聚簇质量时，保持k。与k的比值不变，规律性地 此，在算法实际运行时，可以在相同的k。与k比值 增加k与k的比值，算法的运行时间变化.对于数 的条件下，尽量选取较小的，与k的比值，能够在 据集DS1与DS2,在两参数比值为k,/k=30%时，算 保证聚簇质量的同时，获得更快的执行速度 10r 9 DS2 9 8 CoverType 7 6 Cup99 5 4 4 3 3 2 2/6 3/9 4/12 5/15 6/18 4/8 5/106/12 7/14 8/16 hfk 图11 参数与运行时间 Fig.11 Parameters and runtime 够克服单点和簇间单链的影响，能够正确识别离群 5结论 点和簇间的桥，具有更高的准确性.理论分析和实 提出一种基于共享最近邻密度的数据流聚类算 验结果表明：SNDStream算法在滑动窗口中相对于 法SNDStream.首先定义数据对象的共享最近邻密 现有方法具有更高的聚类质量和更精确的聚类有效 度和簇的密度，设计了滑动窗口内共享最近邻图的 性.今后的工作将对目前方法中存在的边缘对象区 簇查找和最近邻图的更新算法，得到的聚簇结果能 分问题，不确定性处理问题等做进一步的研究.北 京 科 技 大 学 学 报 第 36 卷 4. 3 参数敏感性 算法运行时需要设置两个主要参数最近邻数 k 和共享近邻数 ks． 为测试参数设置对算法执行结果 的影响，实验使用前述的合成数据集和真实数据集． 图 10 给出了参数设置与聚类质量之间的关系． 其 中横坐标是参数 ks 与 k 的比值，即 0. 5 可以表示， 数据点的最近邻数为 10，那么共享近邻数应设为 5． 从图 10 中可以看出，对于数据集 DS1 与 DS2，在两 参数比值处于 30% ～ 40% 时，聚簇质量较好，对于 数据 集 CoverType 则 为 40% ～ 50% ，对 于 数 据 集 Cup99 则为 50% ～ 70% ． 所以尽管数据集不同，在 一定的比值范围内，SNDStream 算法总可以取得较 好的聚簇质量． 原因是当比值增大时，表示从 k 个 近邻中选择较多的共享近邻( 例如考虑从五个近邻 中选择四个共享近邻) ，导致簇的分裂; 而当比值减 少时，表示从 k 个近邻中选择较少的共享近邻，导致 簇的合并． 图 10 参数与聚类质量 Fig． 10 Parameters and clustering quality 图 11 给出了参数设置与运行时间之间的关系， 其中横坐标是参数 ks 与 k 的变化，考察在取得较好 的聚簇质量时，保持 ks 与 k 的比值不变，规律性地 增加 ks 与 k 的比值，算法的运行时间变化． 对于数 据集 DS1 与 DS2，在两参数比值为 ks /k = 30% 时，算 法的运行时间随 k 与 ks 的比值增大而显著增加，对 于数据集 CoverType 与数据集 Cup99 同样如此． 因 此，在算法实际运行时，可以在相同的 ks 与 k 比值 的条件下，尽量选取较小的 ks 与 k 的比值，能够在 保证聚簇质量的同时，获得更快的执行速度． 图 11 参数与运行时间 Fig． 11 Parameters and runtime 5 结论 提出一种基于共享最近邻密度的数据流聚类算 法 SNDStream． 首先定义数据对象的共享最近邻密 度和簇的密度，设计了滑动窗口内共享最近邻图的 簇查找和最近邻图的更新算法，得到的聚簇结果能 够克服单点和簇间单链的影响，能够正确识别离群 点和簇间的桥，具有更高的准确性． 理论分析和实 验结果表明: SNDStream 算法在滑动窗口中相对于 现有方法具有更高的聚类质量和更精确的聚类有效 性． 今后的工作将对目前方法中存在的边缘对象区 分问题，不确定性处理问题等做进一步的研究． · 0171 ·