第12期 高兵等：基于共享最近邻密度的演化数据流聚类算法 ·1709· 4.2聚类有效性 聚簇和随机的离群点，同时簇之间有条状的数据点； 为了测试算法聚类大小形状不同的簇和密度分 DS2包含10000个数据点，有九个不同大小和形状 布不同的聚簇的能力，使用了文献5]中的二维合 的聚簇，同样包含随机的离群点和条状数据点，但出 成数据集DS1、DS2和DS3,如图8所示，DS1包含 现聚簇的多种环绕情况：DS3包含8000个数据点， 8000个数据点，其中有六个不同大小、不同形状的 有八个不同密度且间距更近的聚簇， (c) 图8数据分布.(a)DS1:(b)DS2:(c)DS3 Fig.8 Distribution of three datasets:(a)DS1;(b)DS2:(c)DS3 图9给出了三种算法的运行结果.SNDStream 接的簇，不能正确识别离群点.这是因为Rep- 算法的参数设置为k=14,k,=6,R4=50,a=1.5. Stream算法仅考虑数据对象的k近邻，会将大部分 从图9(a)~(c)可以看出本文的算法能够得到良 的离群点和簇之间的桥接错误的分到簇中.基于 好的聚类结果，正确地在三个数据集中聚类出大 网格的D-Stream算法（图9（g))能够正确识别离 小、形状和密度不同的簇，能够识别出环绕且距离 群点，但同样不能正确识别桥接的簇，也不能正确 接近的簇，不受簇间桥接数据对象的影响，能够正 识别密度不同的簇.这是因为D-Stream算法采用 确识别离群点.这是因为本文算法定义的共享最 一致的网格密度参数，密度阈值过小导致稀疏簇 近邻密度更好地考虑了数据点所处的当前环境. 的分裂（如图9(h)所示），密度阈值过大导致簇的 RepStream算法（图9(d)~（f))不能正确识别桥 错误合并 ) (g) (h) 图9聚类结果比较.(a)SNDStream,DSl:(b)SNDStream,DS2:(c)SNDStream,DS3:(d)RepStream,DSl:(e)RepStream,DS2:(0 RepStream,DS3:(g)D-Stream,DS1:(h)D-Stream,DS2:(i)D-Stream,DS3 Fig.9 Comparison of clustering results:(a)SNDStream,DS1:(b)SNDStream,DS2:(c)SNDStream,DS3:(d)RepStream,DS1:(e)Rep- Stream,DS2:(f)RepStream,DS3;(g)D-Stream,DS1:(h)D-Stream,DS2;(i)D-Stream,DS3第 12 期 高 兵等: 基于共享最近邻密度的演化数据流聚类算法 4. 2 聚类有效性 为了测试算法聚类大小形状不同的簇和密度分 布不同的聚簇的能力，使用了文献［15］中的二维合 成数据集 DS1、DS2 和 DS3，如图 8 所示，DS1 包含 8000 个数据点，其中有六个不同大小、不同形状的 聚簇和随机的离群点，同时簇之间有条状的数据点; DS2 包含 10000 个数据点，有九个不同大小和形状 的聚簇，同样包含随机的离群点和条状数据点，但出 现聚簇的多种环绕情况; DS3 包含 8000 个数据点， 有八个不同密度且间距更近的聚簇． 图 8 数据分布． ( a) DS1; ( b) DS2; ( c) DS3 Fig． 8 Distribution of three datasets: ( a) DS1; ( b) DS2; ( c) DS3 图 9 聚类结果比较． ( a) SNDStream，DS1; ( b) SNDStream，DS2; ( c) SNDStream，DS3; ( d) ＲepStream，DS1; ( e) ＲepStream，DS2; ( f) ＲepStream，DS3; ( g) D-Stream，DS1; ( h) D-Stream，DS2; ( i) D-Stream，DS3 Fig． 9 Comparison of clustering results: ( a) SNDStream，DS1; ( b) SNDStream，DS2; ( c) SNDStream，DS3; ( d) ＲepStream，DS1; ( e) Ｒep￾Stream，DS2; ( f) ＲepStream，DS3; ( g) D-Stream，DS1; ( h) D-Stream，DS2; ( i) D-Stream，DS3 图 9 给出了三种算法的运行结果． SNDStream 算法的参数设置为 k = 14，ks = 6，Ｒdi = 50，α = 1. 5． 从图 9( a) ～ ( c) 可以看出本文的算法能够得到良 好的聚类结果，正确地在三个数据集中聚类出大 小、形状和密度不同的簇，能够识别出环绕且距离 接近的簇，不受簇间桥接数据对象的影响，能够正 确识别离群点． 这是因为本文算法定义的共享最 近邻密度更好地考虑了数据点所处的当前环境． ＲepStream 算法( 图 9 ( d) ～ ( f) ) 不能正确识别桥 接 的 簇，不能正确识别离群点． 这 是 因 为 Ｒep￾Stream 算法仅考虑数据对象的 k 近邻，会将大部分 的离群点和簇之间的桥接错误的分到簇中． 基于 网格的 D-Stream 算法( 图 9 ( g) ) 能够正确识别离 群点，但同样不能正确识别桥接的簇，也不能正确 识别密度不同的簇． 这是因为 D-Stream 算法采用 一致的网格密度参数，密度阈值过小导致稀疏簇 的分裂( 如图 9( h) 所示) ，密度阈值过大导致簇的 错误合并． · 9071 ·