基于共享最近邻密度的演化数据流聚类算法

第36卷第12期 北京科技大学学报 Vol.36 No.12 2014年12月 Journal of University of Science and Technology Beijing Dec.2014 基于共享最近邻密度的演化数据流聚类算法 高 兵12)，张健沛”，邹启杰12 1)哈尔滨工程大学计算机科学与技术学院，哈尔滨1500012)大连东软信息学院计算机系，大连116023 ☒通信作者，E-mail:gaobing(@neusoft.cdu.cn 摘要现有的基于密度的数据流聚类算法难于发现密度不同的簇，难于区分由若干数据对象桥接的簇和离群点.本文提出 了一种基于共享最近邻密度的演化数据流聚类算法.在此算法中，基于共享最近邻图定义了共享最近邻密度，结合数据对象 被类似的最近邻对象包围的程度和被其周围对象需要的程度这两个环境因素，使聚类结果不受密度变化的影响.定义了数据 对象的平均距离和簇密度，以识别离群点和簇间的桥接.设计了滑动窗口模型下数据流更新算法，维护共享最近邻图中簇的 更新.理论分析和实验结果验证了算法的聚类效果和聚类质量. 关键词数据流：聚类算法：最近邻：离群点；数据挖掘 分类号TP311 Evolving data stream clustering algorithm based on the shared nearest neighbor density GAO Bing ZHANG Jian-pei,ZOU Qijie 1)College of Computer Science and Technology,Harbin Engineering University,Harbin 150001,China 2)Department of Computer,Dalian Neusoft Information College,Dalian 116023,China Corresponding author,E-mail:gaobing@neusoft.edu.cn ABSTRACT Existing density-based data stream clustering algorithms are difficult to discover clusters with different densities and to distinguish clusters with bridges and the outliers.A novel stream clustering algorithm was proposed based on the shared nearest neigh- bor density.In this algorithm,the shared nearest neighbor density was defined based on the shared nearest neighbor graph,which con- sidered the degree of data object surrounded by the nearest neighbors and the degree of data object demanded by around data objects. So the clustering result was not influenced by the density variation.The average distance of data object and the cluster density were de- fined to identify outliers and clusters with bridges.The updating algorithm over the sliding window was designed to maintain the renewal of clusters on the shared nearest neighbor graph.Theoretical analysis and experimental results demonstrate the performance of clustering effect and a better clustering quality. KEY WORDS data streams:clustering algorithms:nearest neighbors:outliers:data mining 随着信息技术的不断发展，数据流模型在许多 的具体条件，如何识别密度和形状不同的簇，同时正 应用中广泛出现，其特征是数据到达速度快且规模 确识别离群点对数据流的聚类提出了更高的要求. 庞大，例如财经应用、网络监控和传感器网络口.如 Stream算法回将自顶向下的分治策略应用于预 何在数据流中进行数据挖掘以便发现知识正成为当 聚类过程，这种思想与BIRCH算法司很相似，只是 前的研究热点.在众多数据流挖掘任务中，聚类问 具体的分治策略选择不同.当新的数据流到达时， 题是将数据划分为若干个簇，并保证簇内元组的相 Stream算法使用一个LSEARCH子线程进行当前块 似性高，簇间元组的相似性低.结合数据流环境下 的聚类.StreamKM++算法采用非均匀取样技术 收稿日期：2013-0907 基金项目：国家自然科学基金资助项目(61370083,61073043,61073041,61402126) DOI:10.13374/j.issn1001-053x.2014.12.018:http://journals.ustb.edu.cn

第 36 卷 第 12 期 2014 年 12 月 北京科技大学学报 Journal of University of Science and Technology Beijing Vol． 36 No． 12 Dec． 2014 基于共享最近邻密度的演化数据流聚类算法 高 兵1，2) ，张健沛1) ，邹启杰1，2) 1) 哈尔滨工程大学计算机科学与技术学院，哈尔滨 150001 2) 大连东软信息学院计算机系，大连 116023  通信作者，E-mail: gaobing@ neusoft． edu． cn 摘 要 现有的基于密度的数据流聚类算法难于发现密度不同的簇，难于区分由若干数据对象桥接的簇和离群点． 本文提出 了一种基于共享最近邻密度的演化数据流聚类算法． 在此算法中，基于共享最近邻图定义了共享最近邻密度，结合数据对象 被类似的最近邻对象包围的程度和被其周围对象需要的程度这两个环境因素，使聚类结果不受密度变化的影响． 定义了数据 对象的平均距离和簇密度，以识别离群点和簇间的桥接． 设计了滑动窗口模型下数据流更新算法，维护共享最近邻图中簇的 更新． 理论分析和实验结果验证了算法的聚类效果和聚类质量． 关键词 数据流; 聚类算法; 最近邻; 离群点; 数据挖掘 分类号 TP 311 Evolving data stream clustering algorithm based on the shared nearest neighbor density GAO Bing1，2)  ，ZHANG Jian-pei1) ，ZOU Qi-jie1，2) 1) College of Computer Science and Technology，Harbin Engineering University，Harbin 150001，China 2) Department of Computer，Dalian Neusoft Information College，Dalian 116023，China  Corresponding author，E-mail: gaobing@ neusoft． edu． cn ABSTＲACT Existing density-based data stream clustering algorithms are difficult to discover clusters with different densities and to distinguish clusters with bridges and the outliers． A novel stream clustering algorithm was proposed based on the shared nearest neigh￾bor density． In this algorithm，the shared nearest neighbor density was defined based on the shared nearest neighbor graph，which con￾sidered the degree of data object surrounded by the nearest neighbors and the degree of data object demanded by around data objects． So the clustering result was not influenced by the density variation． The average distance of data object and the cluster density were de￾fined to identify outliers and clusters with bridges． The updating algorithm over the sliding window was designed to maintain the renewal of clusters on the shared nearest neighbor graph． Theoretical analysis and experimental results demonstrate the performance of clustering effect and a better clustering quality． KEY WOＲDS data streams; clustering algorithms; nearest neighbors; outliers; data mining 收稿日期: 2013--09--07 基金项目: 国家自然科学基金资助项目( 61370083，61073043，61073041，61402126) DOI: 10． 13374 /j． issn1001--053x． 2014． 12． 018; http: / /journals． ustb． edu． cn 随着信息技术的不断发展，数据流模型在许多 应用中广泛出现，其特征是数据到达速度快且规模 庞大，例如财经应用、网络监控和传感器网络［1］． 如 何在数据流中进行数据挖掘以便发现知识正成为当 前的研究热点． 在众多数据流挖掘任务中，聚类问 题是将数据划分为若干个簇，并保证簇内元组的相 似性高，簇间元组的相似性低． 结合数据流环境下 的具体条件，如何识别密度和形状不同的簇，同时正 确识别离群点对数据流的聚类提出了更高的要求． Stream 算法［2］将自顶向下的分治策略应用于预 聚类过程，这种思想与 BIＲCH 算法［3］很相似，只是 具体的分治策略选择不同． 当新的数据流到达时， Stream 算法使用一个 LSEAＲCH 子线程进行当前块 的聚类． StreamKM + + 算法［4］采用非均匀取样技术

·1704 北京科技大学学报 第36卷 获得数据流中的多个小的核心集，设计核心集树结 现簇，不需要更多的先验知识，能够发现数据中不同 构提高核心集的生成、合并和更新处理速度，较 密度和形状的簇.其后，算法7]在JP算法的基础 Stream算法有更好的聚类质量，并可以适应高维数 上，考虑了共享最近邻图中结点的邻域密度，结合 据流维度.CluStream算法提出了两阶段聚类的 DBSCAN的算法思想进行聚类.但是，以上两种算 方法，在线阶段，算法维护金字塔时间窗口内的快照 法簇的合并可能依赖于一条链，不能更好地识别离 信息，并将微聚类的信息作为汇总存储于快照中. 群点，并且都不是数据流聚类算法.算法Rep- 在离线阶段，运行宏聚类处理过程，得到最终的聚 Stream应用数据流的滑动窗口模型，首先建立稀 类.算法工作在界标窗口模型下，所使用的金字塔 疏化k近邻图，继而定义满足密度要求的点作为代 时间窗口实质上是一种抽样技术.CluStream算法 表点，将代表点作为数据流的概要.这种方法比使 随后又进行了改进以便处理不确定性数据流和 用汇总信息作为概要更为精确，能够发现不同形状 高维数据流团.上述几种数据流聚类算法都使用基 和不同大小的簇，但不能更好地识别密度的变化，不 于k-means算法的聚类思想，其缺点是对非球形状 能正确识别簇间单链和离群点. 簇分布的聚类效果不理想.此外，他们都需要先验 本文提出了一种基于共享最近邻密度的数据流 的指定簇的个数，这在动态数据流的条件下也是不 聚类算法SNDStream(shared nearest-neighbors densi-- 太现实的 ty stream).在共享最近邻图的基础上定义共享最近 基于密度的聚类算法可以发现不同形状的簇. 邻密度，查找密度大于指定阈值的连通分支，发现形 如DBSCAN算法图引入基于密度的概念，定义核心 状和密度不同的数据流聚簇：定义数据对象的平均 对象并构建环绕他们的簇，但不能适应数据流环境. 距离，与簇平均密度比较以区分离群点：设计最近邻 此后，DenStream算法改进DBSCAN以适应流的 图的更新算法，实现滑动窗口模型下演化数据流聚 特点，定义了核心微簇和离群点微簇结构来维护发 类.通过性能分析和基于真实数据集及合成数据集 现簇和离群点：SDStream算法o将簇特征存储于指 的实验表明，SNDStream算法能够发现密度和形状 数直方图结构中，同时使用时态簇特征确定待删除 不同的簇，正确识别离群点和簇间连接，具有良好的 簇；OPCluStream算法使用树拓扑结构来维护数 聚类质量，有效适应簇数不断变化的数据流场景 据间的关系，并可以映射为最终的簇.以上三种算 1共享最近邻密度与离群点 法基于DBSCAN的思想，仍然不能适应密度变化的 数据流.D-Stream算法☒使用基于网格的两阶段 1.1k最近邻图与共享最近邻相似度 算法聚类数据流，通过对数据空间的网格化，在线部 基于图的知识，可以将数据流中数据对象之间 分统计子空间网格单元信息，将格分为三类，即密集 的距离关系用图建模，对于任意数据对象，只有离它 格、稀疏格和转换格，新数据到达时更新相应的格， 最近的k个对象在求解聚类问题时具有更高的价 离线部分计算格密度并进行聚类.文献3]在此基 值.所以本文考虑在滑动窗口模型下，计算离数据 础上进一步提出了吸引格的概念，以处理D-Stream 对象最近的k个数据对象，建立数据流k最近邻图. 算法中存在的信息丢失问题.基于网格的方法使用 设S=,表示欧式空间上的数 一致的密度参数和概要的格信息，往往不能得到更 据流S在时刻t滑动窗口h上的一个数据对象集 准确的聚类结果；随着数据维数的增长，网格数将呈 合，其中d=表示一个数据对象 指数增长，由此导致处理效率的大幅下降，及数据稀 (其中m为空间维数).对于数据集合中的任意两 疏化后处理的准确性降低 个数据对象d:与d,它们的相似度越高，则它们属 算法Opossum和算法Chameleon采用基于 于同一个聚簇的概率越大 图的方法聚类，其基本方法是用结点表示数据对象， 定义1数据对象d的最近邻集合定义为 用结点之间边的权值表示两个数据对象之间的邻近 N,（d),满足条件： 度，构建数据对象的邻近度图并稀疏化，然后使用不 若HdeN.(d),HdnN.(d),(d:≠d,d≠ 同的图划分算法进行簇的合并.在稀疏化邻近度图 d):有L(d:,d)≤L(d,d),L为距离函数 的基础上，考虑基于共享的最近邻个数，可以计算两 定义2数据对象d.的最近邻个数用结点d, 数据对象间的共享最近邻(shared nearest neighbor, 的出度表示，记为0(d) SNN)相似度，生成共享最近邻相似度图，JP聚类算 定义3数据对象d被其他对象需要的程度， 法通过查找共享最近邻相似度图的连通分支发 即作为其他数据对象近邻的个数用结点d,的入度

北 京 科 技 大 学 学 报 第 36 卷 获得数据流中的多个小的核心集，设计核心集树结 构提高核心集的生成、合并和更新处理速度，较 Stream 算法有更好的聚类质量，并可以适应高维数 据流维度． CluStream 算法［5］提出了两阶段聚类的 方法，在线阶段，算法维护金字塔时间窗口内的快照 信息，并将微聚类的信息作为汇总存储于快照中． 在离线阶段，运行宏聚类处理过程，得到最终的聚 类． 算法工作在界标窗口模型下，所使用的金字塔 时间窗口实质上是一种抽样技术． CluStream 算法 随后又进行了改进以便处理不确定性数据流［6］和 高维数据流［7］． 上述几种数据流聚类算法都使用基 于 k-means 算法的聚类思想，其缺点是对非球形状 簇分布的聚类效果不理想． 此外，他们都需要先验 的指定簇的个数，这在动态数据流的条件下也是不 太现实的． 基于密度的聚类算法可以发现不同形状的簇． 如 DBSCAN 算法［8］引入基于密度的概念，定义核心 对象并构建环绕他们的簇，但不能适应数据流环境． 此后，DenStream 算法［9］改进 DBSCAN 以适应流的 特点，定义了核心微簇和离群点微簇结构来维护发 现簇和离群点; SDStream 算法［10］将簇特征存储于指 数直方图结构中，同时使用时态簇特征确定待删除 簇; OPCluStream 算法［11］使用树拓扑结构来维护数 据间的关系，并可以映射为最终的簇． 以上三种算 法基于 DBSCAN 的思想，仍然不能适应密度变化的 数据流． D-Stream 算法［12］使用基于网格的两阶段 算法聚类数据流，通过对数据空间的网格化，在线部 分统计子空间网格单元信息，将格分为三类，即密集 格、稀疏格和转换格，新数据到达时更新相应的格， 离线部分计算格密度并进行聚类． 文献［13］在此基 础上进一步提出了吸引格的概念，以处理 D-Stream 算法中存在的信息丢失问题． 基于网格的方法使用 一致的密度参数和概要的格信息，往往不能得到更 准确的聚类结果; 随着数据维数的增长，网格数将呈 指数增长，由此导致处理效率的大幅下降，及数据稀 疏化后处理的准确性降低． 算法 Opossum［14］和算法 Chameleon［15］采用基于 图的方法聚类，其基本方法是用结点表示数据对象， 用结点之间边的权值表示两个数据对象之间的邻近 度，构建数据对象的邻近度图并稀疏化，然后使用不 同的图划分算法进行簇的合并． 在稀疏化邻近度图 的基础上，考虑基于共享的最近邻个数，可以计算两 数据对象间的共享最近邻( shared nearest neighbor， SNN) 相似度，生成共享最近邻相似度图，JP 聚类算 法［16］通过查找共享最近邻相似度图的连通分支发 现簇，不需要更多的先验知识，能够发现数据中不同 密度和形状的簇． 其后，算法［17］在 JP 算法的基础 上，考虑了共享最近邻图中结点的邻域密度，结合 DBSCAN 的算法思想进行聚类． 但是，以上两种算 法簇的合并可能依赖于一条链，不能更好地识别离 群点，并且都不是数据流聚类算法． 算 法 Ｒep￾Stream［18］应用数据流的滑动窗口模型，首先建立稀 疏化 k 近邻图，继而定义满足密度要求的点作为代 表点，将代表点作为数据流的概要． 这种方法比使 用汇总信息作为概要更为精确，能够发现不同形状 和不同大小的簇，但不能更好地识别密度的变化，不 能正确识别簇间单链和离群点． 本文提出了一种基于共享最近邻密度的数据流 聚类算法 SNDStream ( shared nearest-neighbors densi￾ty stream) ． 在共享最近邻图的基础上定义共享最近 邻密度，查找密度大于指定阈值的连通分支，发现形 状和密度不同的数据流聚簇; 定义数据对象的平均 距离，与簇平均密度比较以区分离群点; 设计最近邻 图的更新算法，实现滑动窗口模型下演化数据流聚 类． 通过性能分析和基于真实数据集及合成数据集 的实验表明，SNDStream 算法能够发现密度和形状 不同的簇，正确识别离群点和簇间连接，具有良好的 聚类质量，有效适应簇数不断变化的数据流场景． 1 共享最近邻密度与离群点 1. 1 k 最近邻图与共享最近邻相似度 基于图的知识，可以将数据流中数据对象之间 的距离关系用图建模，对于任意数据对象，只有离它 最近的 k 个对象在求解聚类问题时具有更高的价 值． 所以本文考虑在滑动窗口模型下，计算离数据 对象最近的 k 个数据对象，建立数据流 k 最近邻图． 设 S = ＜ d1，d2，…，dh ＞ t 表示欧式空间上的数 据流 S 在时刻 t 滑动窗口 h 上的一个数据对象集 合，其中 di = ＜ di1，di2，…，dim ＞ 表示一个数据对象 ( 其中 m 为空间维数) ． 对于数据集合中的任意两 个数据对象 di 与 dj ，它们的相似度越高，则它们属 于同一个聚簇的概率越大． 定义 1 数 据 对 象 di 的最近邻集合定义为 Nn ( di ) ，满足条件: 若dj∈Nn ( di ) ，dxNn ( di ) ，( di ≠dj ，di ≠ dx ) ; 有 L( di，dj ) ≤L( di，dx ) ，L 为距离函数． 定义 2 数据对象 di 的最近邻个数用结点 di 的出度表示，记为 O( di ) ． 定义 3 数据对象 di 被其他对象需要的程度， 即作为其他数据对象近邻的个数用结点 di 的入度 · 4071 ·

第12期 高兵等：基于共享最近邻密度的演化数据流聚类算法 ·1705· 表示，记为I(d). (SNN图).例如，计算图1的k最近邻图的每一对 定义4k最近邻图G(D,E)是一个有向图，D 结点的共享最近邻相似度，可以得到如图2所示的 是数据对象的集合，E是边的集合，且满足如下两个 共享最近邻图(IS(d,d,)I≥1)，其中实线表示两个 条件： 结点共享最近邻相似度IS(d,d,)|=2,虚线表示两 1)Hd:∈D,0(d)=k,(k≥2)； 个结点共享最近邻相似度IS(d,d;)1=1,而1S(d4, 2)若eE,则有d,eN.(d:) d6)1=3. 如图1所示，数据对象d的入度1(d)是5，出 度O(d3)是3，N.（d3)={d2,d,ds}.数据对象d6 的入度I(d6)为4，出度0(d6)为3，N.(d。)={d, ds,d. 图2共享最近邻图(SNN图) Fig.2 Shared nearest neighbor graph 可以通过设定共享最近邻相似度大于指定值， 直接查找共享最近邻相似度图中的连通分支发现 簇，如图2所示，当1Sm(d,d)1=2时，图中的点 图1数据流k最近邻图(k=3) 将聚类得到两个簇（由图中实线组成）.但此方法存 Fig.I k-nearest neighbor graph of the data stream (k=3) 在如下问题：如果离群点与簇内的点共享相同的近 邻，在共享最近邻相似度图中通过单链与簇相连，例 定义5k最近邻图G(D,E)中，数据对象d,与 如图1和图3中d,与d的相似度链接：此外当单链 d的共享最近邻集合定义为Sm(d,d,),满足条件： 的情况出现在簇间，会造成簇的错误合并 若ydeSn(d,d)，(dn≠d,dn≠d):则dne 为克服上述问题，首先化简共享最近邻图，在此 Nn(d,)且dneN.(d). 基础上给出共享最近邻密度的定义. 观察可知，同一个簇中的两个数据对象往往具 定义7k.-共享最近邻图Gm(Dm,Em)是一个 有相同的近邻，所以可以将数据对象间的相似度定 无向图，D是数据对象的集合，E是边的集合，且满 义为它们共同拥有的最近邻的个数，即共享最近邻 足如下两个条件： 相似度. 1)D.=D; 定义6k最近邻图G(D,E)中，数据对象d:与 2)若eEm,有1Sm(d,d)I≥k(k.为 山，的相似程度由共享最近邻相似度表示，定义为 共享系数). lSm（d,d)1,即Sm(d,d)集合中元素的个数. 由定义k,一共享最近邻图中数据对象集合D ISm(d:,d)I表示数据对象间的k个最近邻中 来自于k最近邻图，E表示两个数据对象间的共享 共享近邻的计数，易知0≤ISm(d,d)I≤k.两个数 最近邻相似度大于等于k 据对象的联系越紧密，他们的共享最近邻相似度的 值越高，他们属于同一个簇的概率越高. 定理1k一共享最近邻图中边数E≤宁D· 因为共享最近邻相似度基于k近邻图计算，考 C(IDI为图中对象数). 虑的是数据对象间的k个最近邻中共享近邻的个 证明：k最近邻图中每个数据对象有k个最近 数，当数据对象分布稀疏的时候，数据对象的最近邻 邻，根据定义7有1Sm（d,d)I≥k,即在k个最近 的k个对象也一定分布的较远；当数据对象密集的 邻中至少有k。个近邻也为其他对象的近邻，所以每 时候，数据对象的最近邻的k个对象也分布的紧密. 个数据对象的共享最近邻有C种组合情况，且k,一 因此，共享最近邻相似度可以自动适应密度和形状 共享最近邻图是对象数为IDmI的无向图，结论 的变化. 得证. 1.2共享最近邻图与共享最近邻密度 定义8k,一共享最近邻图中数据对象d,的共 在k最近邻图的基础之上，通过计算数据对象 享最近邻密度Ru定义为e.×I(d,). 之间共享最近邻相似度可以得到共享最近邻图 e,(共享计数)为k.一共享最近邻图中与数据对

第 12 期 高 兵等: 基于共享最近邻密度的演化数据流聚类算法 表示，记为 I( di ) ． 定义 4 k 最近邻图 G( D，E) 是一个有向图，D 是数据对象的集合，E 是边的集合，且满足如下两个 条件: 1) di∈D，O( di ) = k，( k≥2) ; 2) 若 ＜ di，dj ＞ ∈E，则有 dj∈Nn ( di ) ． 如图 1 所示，数据对象 d3的入度 I( d3 ) 是 5，出 度 O( d3 ) 是 3，Nn ( d3 ) = { d2，d4，d6 } ． 数据对象 d6 的入度 I( d6 ) 为 4，出度 O( d6 ) 为 3，Nn ( d6 ) = { d3， d8，d7 } ． 图 1 数据流 k 最近邻图( k = 3) Fig． 1 k-nearest neighbor graph of the data stream ( k = 3) 定义 5 k 最近邻图 G( D，E) 中，数据对象 di 与 dj 的共享最近邻集合定义为 Snn ( di，dj ) ，满足条件: 若dw∈Snn ( di，dj ) ，( dw≠di，dw≠dj ) ; 则 dw∈ Nn ( di ) 且 dw∈Nn ( dj ) ． 观察可知，同一个簇中的两个数据对象往往具 有相同的近邻，所以可以将数据对象间的相似度定 义为它们共同拥有的最近邻的个数，即共享最近邻 相似度． 定义 6 k 最近邻图 G( D，E) 中，数据对象 di 与 dj 的相似程度由共享最近邻相似度表示，定义为 | Snn ( di，dj ) |，即 Snn ( di，dj ) 集合中元素的个数． | Snn ( di，dj ) | 表示数据对象间的 k 个最近邻中 共享近邻的计数，易知 0≤| Snn ( di，dj ) |≤k． 两个数 据对象的联系越紧密，他们的共享最近邻相似度的 值越高，他们属于同一个簇的概率越高． 因为共享最近邻相似度基于 k 近邻图计算，考 虑的是数据对象间的 k 个最近邻中共享近邻的个 数，当数据对象分布稀疏的时候，数据对象的最近邻 的 k 个对象也一定分布的较远; 当数据对象密集的 时候，数据对象的最近邻的 k 个对象也分布的紧密． 因此，共享最近邻相似度可以自动适应密度和形状 的变化． 1. 2 共享最近邻图与共享最近邻密度 在 k 最近邻图的基础之上，通过计算数据对象 之间共享最近邻相似度可以得到共享最近邻图 ( SNN 图) ． 例如，计算图 1 的 k 最近邻图的每一对 结点的共享最近邻相似度，可以得到如图 2 所示的 共享最近邻图( | S( di，dj ) |≥1) ，其中实线表示两个 结点共享最近邻相似度| S( di，dj) | = 2，虚线表示两 个结点共享最近邻相似度| S( di，dj) | = 1，而 | S( d4， d6 ) | = 3． 图 2 共享最近邻图( SNN 图) Fig． 2 Shared nearest neighbor graph 可以通过设定共享最近邻相似度大于指定值， 直接查找共享最近邻相似度图中的连通分支发现 簇［15］，如图 2 所示，当| Snn ( di，dj ) | = 2 时，图中的点 将聚类得到两个簇( 由图中实线组成) ． 但此方法存 在如下问题: 如果离群点与簇内的点共享相同的近 邻，在共享最近邻相似度图中通过单链与簇相连，例 如图 1 和图 3 中 d1与 d3的相似度链接; 此外当单链 的情况出现在簇间，会造成簇的错误合并． 为克服上述问题，首先化简共享最近邻图，在此 基础上给出共享最近邻密度的定义． 定义 7 ks --共享最近邻图 Gsn ( Dsn，Esn ) 是一个 无向图，Dsn是数据对象的集合，Esn是边的集合，且满 足如下两个条件: 1) Dsn = D; 2) 若 ＜ di，dj ＞ ∈Esn，有 | Snn ( di，dj) | ≥ks ( ks 为 共享系数) ． 由定义 ks --共享最近邻图中数据对象集合 Dsn 来自于 k 最近邻图，Esn表示两个数据对象间的共享 最近邻相似度大于等于 ks． 定理1 ks --共享最近邻图中边数|Esn |≤ 1 2 |Dsn |· Cks k ( |Dsn |为图中对象数) ． 证明: k 最近邻图中每个数据对象有 k 个最近 邻，根据定义 7 有 | Snn ( di，dj) | ≥ks，即在 k 个最近 邻中至少有 ks 个近邻也为其他对象的近邻，所以每 个数据对象的共享最近邻有 Cks k 种组合情况，且 ks -- 共享最近邻图是对象数为 | Dsn | 的无 向 图，结 论 得证． 定义 8 ks --共享最近邻图中数据对象 di的共 享最近邻密度 Ｒdi 定义为 es × I( di ) ． es( 共享计数) 为 ks --共享最近邻图中与数据对 · 5071 ·

·1706· 北京科技大学学报 第36卷 象d相连的边数，I(d)是数据对象d的对应于k最 定义11数据对象d,为离群点，当L>aR4 近邻图中的入边数.如图2中d。的共享最近邻密度 (a为密度系数). 为R=2×4=8,d,的共享最近邻密度为R,=3× 根据定义11，在生成数据对象的k近邻图时计 3=9(k≥2). 算并保存它与k个最近邻的平均距离，在聚类算法 根据定义，e,是数据对象的共享最近邻相似度 执行的过程中，将当前数据对象的L与当前簇的 的计数，是度量一个数据对象被类似的对象（关于 平均密度R,比较，当大于一定比值时，将当前对象 最近邻)包围的程度；1(d:)是度量一个数据对象被 设为离群点. 其周围的数据对象需要的程度.共享最近邻密度定 义同时考虑了两者，能够得到更精确的聚类结果. 2聚类算法 本文算法在k,一共享最近邻图中，计算数据对象的 本文算法广度优先遍历k.一共享最近邻图，计 共享最近邻密度，查找密度值大于指定阈值的连通 算数据对象的共享最近邻密度，查找共享最近邻密 分支发现簇，如图2所示，当R4>6(k,=2)时，图中 度大于指定阈值的连通分支以发现簇，对于符合共 的点将聚类得到两个簇，一个离群点d· 享最近邻密度条件的数据对象，根据定义11判断是 1.3离群点与簇的桥接 否为离群点. 如果一个数据对象在共享最近邻相似度图中通 设计了滑动窗口内邻接表数据结构保存数据流 过单链与簇相连，例如图1与图2中d,与d的相似 k最近邻图.邻接表1中保存了每一个数据对象的 度链接，根据共享最近邻密度的定义，可以将该数据 k个最近邻及他们之间的距离，邻接表2中保存了 对象区分为离群点.但是，如果一个离群点与簇内 指向每一个数据对象的入度及指向它的对象，另外 的对象共享相同的近邻，而且它的周边有若干相似 使用一个单独的缓冲区保存离群点的引用.通过对 距离的数据对象，根据共享最近邻密度的定义，该点 两个邻接表的遍历，可以快速计算共享最近邻相似 将会被簇吸收，如图3(a)中的点p:如果两个簇之间 度及共享最近邻密度，实现基于共享最近邻密度的 有若干相似距离的对象，那么原有的两个簇将会通 数据流聚类 过它们被错误地合并为一个簇，产生簇间的桥接问 题，如图3(b)中上下两个簇通过中间的数据对象联 3 聚簇维护 在一起.上述问题同时也在Chameleon等算法中 在数据流的滑动窗口模型中，随着流数据的不 存在. 断产生，滑动窗口不断向前移动，新数据不断加入到 (a) 窗口内，同时最久的数据从窗口内移除，在这两种情 ● 况下都需要更新k最近邻图.此外，当增加新数据 。●●●。9s2●●。0 对象时，需要进一步判断它和现有聚簇之间的关系 下面分别讨论移除数据对象和增加数据对象. ● 当删除最久的数据对象时，需要删除这个数据 图3离群点(a)与簇的桥接(b) Fig.3 Outliers (a)and bridge (b) 对象指向k最近邻的边，如图4中所示，设d,是待删 除数据对象，需要删除d,指向他的近邻d4、d和d。 观察图3中的两种情况可知，图3(a)中的离群 这三条边，并将山，从这三个数据对象的入边表中删 点P和图3(b)中的数据对象，尽管它们会被聚类到 除；同时，山，可能位于现有结点的k近邻之内，如图4 簇中，但是它们与簇中其他数据对象的密度是不相 中点虚线指向d的d2和d,删除d,后，需要重新计 同的，所以有如下定义 算他们的k最近邻，如时刻t2所示，d,和d,指向了数 定义9k近邻图中数据对象d:与其k个最近 据对象d. 邻的平均距离记为 当有新数据对象到达时，需要考虑三个步骤： L(d;,d),d;N (d) (1)计算该数据对象与现有对象之间的距离， 定义10 设簇A中包含N个数据对象，则簇A 得到这个对象的k近邻，如图5所示，设d山，是新到达 的簇密度记为 数据对象，经过计算得到d2、d,和d。是它的三个最 R=六 近邻，需要将d,加入到这三个对象的入边表 (2)d,可能位于现有数据对象的k近邻之内

北 京 科 技 大 学 学 报 第 36 卷 象 di相连的边数，I( di ) 是数据对象 di的对应于 k 最 近邻图中的入边数． 如图 2 中 d6的共享最近邻密度 为 Ｒd6 = 2 × 4 = 8，d7的共享最近邻密度为 Ｒd7 = 3 × 3 = 9( ks≥2) ． 根据定义，es 是数据对象的共享最近邻相似度 的计数，是度量一个数据对象被类似的对象( 关于 最近邻) 包围的程度; I( di ) 是度量一个数据对象被 其周围的数据对象需要的程度． 共享最近邻密度定 义同时考虑了两者，能够得到更精确的聚类结果． 本文算法在 ks --共享最近邻图中，计算数据对象的 共享最近邻密度，查找密度值大于指定阈值的连通 分支发现簇，如图 2 所示，当 Ｒdi ＞ 6( ks = 2) 时，图中 的点将聚类得到两个簇，一个离群点 d1 ． 1. 3 离群点与簇的桥接 如果一个数据对象在共享最近邻相似度图中通 过单链与簇相连，例如图 1 与图 2 中 d1与 d3的相似 度链接，根据共享最近邻密度的定义，可以将该数据 对象区分为离群点． 但是，如果一个离群点与簇内 的对象共享相同的近邻，而且它的周边有若干相似 距离的数据对象，根据共享最近邻密度的定义，该点 将会被簇吸收，如图3( a) 中的点 p; 如果两个簇之间 有若干相似距离的对象，那么原有的两个簇将会通 过它们被错误地合并为一个簇，产生簇间的桥接问 题，如图 3( b) 中上下两个簇通过中间的数据对象联 在一起． 上述问题同时也在 Chameleon 等算法中 存在． 图 3 离群点( a) 与簇的桥接( b) Fig． 3 Outliers ( a) and bridge ( b) 观察图 3 中的两种情况可知，图 3( a) 中的离群 点 p 和图 3( b) 中的数据对象，尽管它们会被聚类到 簇中，但是它们与簇中其他数据对象的密度是不相 同的，所以有如下定义． 定义 9 k 近邻图中数据对象 di 与其 k 个最近 邻的平均距离记为 Lavg di = 1 k ∑ k j = 1 L( di，dj ) ，dj∈Nn ( di ) ． 定义 10 设簇 A 中包含 N 个数据对象，则簇 A 的簇密度记为 ＲA = 1 N ∑ N i = 1 Lavg di ． 定义 11 数据对象 di 为离群点，当 Lavg di ＞ αＲA ( α 为密度系数) ． 根据定义 11，在生成数据对象的 k 近邻图时计 算并保存它与 k 个最近邻的平均距离，在聚类算法 执行的过程中，将当前数据对象的 Lavg di 与当前簇的 平均密度 ＲA 比较，当大于一定比值时，将当前对象 设为离群点． 2 聚类算法 本文算法广度优先遍历 ks --共享最近邻图，计 算数据对象的共享最近邻密度，查找共享最近邻密 度大于指定阈值的连通分支以发现簇，对于符合共 享最近邻密度条件的数据对象，根据定义 11 判断是 否为离群点． 设计了滑动窗口内邻接表数据结构保存数据流 k 最近邻图． 邻接表 1 中保存了每一个数据对象的 k 个最近邻及他们之间的距离，邻接表 2 中保存了 指向每一个数据对象的入度及指向它的对象，另外 使用一个单独的缓冲区保存离群点的引用． 通过对 两个邻接表的遍历，可以快速计算共享最近邻相似 度及共享最近邻密度，实现基于共享最近邻密度的 数据流聚类． 3 聚簇维护 在数据流的滑动窗口模型中，随着流数据的不 断产生，滑动窗口不断向前移动，新数据不断加入到 窗口内，同时最久的数据从窗口内移除，在这两种情 况下都需要更新 k 最近邻图． 此外，当增加新数据 对象时，需要进一步判断它和现有聚簇之间的关系． 下面分别讨论移除数据对象和增加数据对象． 当删除最久的数据对象时，需要删除这个数据 对象指向 k 最近邻的边，如图 4 中所示，设 d1是待删 除数据对象，需要删除 d1指向他的近邻 d4、d5和 d6 这三条边，并将 d1从这三个数据对象的入边表中删 除; 同时，d1可能位于现有结点的 k 近邻之内，如图4 中点虚线指向 d1的 d2和 d4，删除 d1后，需要重新计 算他们的 k 最近邻，如时刻 t2所示，d2和 d4指向了数 据对象 d3 ． 当有新数据对象到达时，需要考虑三个步骤: ( 1) 计算该数据对象与现有对象之间的距离， 得到这个对象的 k 近邻，如图 5 所示，设 d1是新到达 数据对象，经过计算得到 d2、d4 和 d6 是它的三个最 近邻，需要将 d1加入到这三个对象的入边表． ( 2) d1可能位于现有数据对象的 k 近邻之内， · 6071 ·

第12期 高兵等：基于共享最近邻密度的演化数据流聚类算法 ·1707· Weka6.0,算法用Java语言实现.实验测试算法的 聚类质量、算法的有效性和参数敏感性三个方面. 4.1聚类质量 为评估算法的聚类质量，使用常用的两个聚类 度量标准：纯度(purity)和交叉熵(cross entropy）. 聚簇的纯度度量该数据集中数据点聚类正确的比 例，较高的纯度值反映了较好的聚类质量.聚簇的 图4移除数据对象 交叉熵用以度量所有簇的平均纯度，较低的交叉熵 Fig.4 Delete data object 反映了较高的簇的平均纯度，也就是较好的聚类 质量. 如图5时刻t2中虚线指向d1的三个数据对象d3、d 实验使用两个真实数据集：第一个数据集是 和ds,这时需要将d,替换入这三个对象的k近邻表 KDD-CUP99网络入侵检测数据集的一个子集，共 中，并将它们加入到山的入边表 包括494020条记录，每条记录对应于一个正常的连 接或者是四种类型的网络攻击之一，实验从42维有 效属性中取34维连续属性：第二个真实数据集是 Forest CoverType森林覆盖类型数据集，选自于UCI 机器学习数据集，这个数据集包含581012条记录， 每条记录属于七种森林覆盖类型之一，实验使用全 部54维属性，其中10维连续属性，44维布尔属性. 实验使用文献I2]中D-Stream算法和文献I8]中 图5增加数据对象 RepStream算法作为比较算法. Fig.5 Add data object 图6是在网络入侵检测数据集KDD-CUP99上 (3)需要判断该数据对象是否属于现有簇，或 的聚类质量实验结果.参数设为近邻数k=10,共享 者是单独的离群点.对于数据流滑动窗口中正在出 数k,=4,密度阈值R.=4,密度系数α=1.2.可以 现的新簇，簇中初始的点由于缺少共享最近邻，会被 看出在不同的滑动窗口大小下，SNDStream算法的 分类为离群点.针对这种情况，设计缓冲区数组暂 聚类纯度都高于RepStream和D-Stream算法，算法 存离群点。算法计算新数据对象的共享最近邻密 的交叉熵低于RepStream和D-Stream算法. 度，如果新数据对象的共享最近邻密度大于阈值且 图7是在森林覆盖类型数据集Forest CoverType L不大于簇密度（根据定义11），分配这个新数据 上的聚类质量实验结果，参数设置为k=10,k,=6, 对象到相应的簇：否则，设为离群点并暂存入离群点 R4=4,a=l.2.再一次的显示出SNDStream算法具 缓冲区中，当缓冲区满时，重新执行聚簇算法生 有非常好的聚类质量 成簇 从全部的实验结果可以看出，SNDStream算法 算法采用树结构实现最近邻查找，算法构建邻 的聚类质量好于D-Stream算法，因为D-Stream算法 接表阶段的平均时间复杂度是O(1 D.llg).聚 基于一致的网格密度，对于高维稀疏数据集上的聚 类阶段采用广度优先搜索策略查找共享最近邻个数 类质量并不理想.多数情况下好于或相同于Rep- 大于指定阈值的对象，即共享最近邻相似度图中连 Stream算法，但是差距相对较小，因为两种算法都是 接每个对象的边数.根据定理1，聚类阶段的时间复 基于k近邻图的思想聚类.SNDStream算法通过定 杂度为O(IDmI·C).更新维护阶段包括查找新对 义共享最近邻密度，更多地考虑了数据对象的当前 象和受影响对象的k最近邻，并计算新数据对象的 环境下的邻域密度，相较于以上两种算法，能够取得 簇，平均时间复杂度为0(lg”+C) 更好的聚类质量. 同时，SNDStream算法的全部聚类质量度量值 4 实验结果与分析 都处于一个较平均且较高的水平上，这是因为 对所提出的基于共享最近邻密度的聚类算法性 SNDStream算法更多的考虑了数据点的当前环境， 能进行测试.实验用P℃配置如下：PⅡ-2.0GHz/2 更好地适应于数据流的动态变化，由此具有更好的 GB,Windows XP,实验平台为开源数据挖掘工具 稳定性

第 12 期 高 兵等: 基于共享最近邻密度的演化数据流聚类算法 图 4 移除数据对象 Fig． 4 Delete data object 如图 5 时刻 t2中虚线指向 d1的三个数据对象 d3、d4 和 d5，这时需要将 d1替换入这三个对象的 k 近邻表 中，并将它们加入到 d1的入边表． 图 5 增加数据对象 Fig． 5 Add data object ( 3) 需要判断该数据对象是否属于现有簇，或 者是单独的离群点． 对于数据流滑动窗口中正在出 现的新簇，簇中初始的点由于缺少共享最近邻，会被 分类为离群点． 针对这种情况，设计缓冲区数组暂 存离群点． 算法计算新数据对象的共享最近邻密 度，如果新数据对象的共享最近邻密度大于阈值且 Lavg di 不大于簇密度( 根据定义 11) ，分配这个新数据 对象到相应的簇; 否则，设为离群点并暂存入离群点 缓冲 区 中，当 缓 冲 区 满 时，重新执行聚簇算法生 成簇． 算法采用树结构实现最近邻查找，算法构建邻 接表阶段的平均时间复杂度是 O( | Dsn | lg | Dsn | ) ． 聚 类阶段采用广度优先搜索策略查找共享最近邻个数 大于指定阈值的对象，即共享最近邻相似度图中连 接每个对象的边数． 根据定理 1，聚类阶段的时间复 杂度为 O( |Dsn |·Cks k ) ． 更新维护阶段包括查找新对 象和受影响对象的 k 最近邻，并计算新数据对象的 簇，平均时间复杂度为 O ( lg | Dsn | + Cks k ) ． 4 实验结果与分析 对所提出的基于共享最近邻密度的聚类算法性 能进行测试． 实验用 PC 配置如下: PⅡ － 2. 0 GHz /2 GB，Windows XP，实验平台为开源数据挖掘工具 Weka 6. 0，算法用 Java 语言实现． 实验测试算法的 聚类质量、算法的有效性和参数敏感性三个方面． 4. 1 聚类质量 为评估算法的聚类质量，使用常用的两个聚类 度量标准: 纯度( purity) 和交叉熵( cross entropy) ． 聚簇的纯度度量该数据集中数据点聚类正确的比 例，较高的纯度值反映了较好的聚类质量． 聚簇的 交叉熵用以度量所有簇的平均纯度，较低的交叉熵 反映了较高的簇的平均纯度，也就是较好的聚类 质量． 实验使用两个真实数据集: 第一个数据集是 KDD-CUP-99 网络入侵检测数据集的一个子集，共 包括 494020 条记录，每条记录对应于一个正常的连 接或者是四种类型的网络攻击之一，实验从 42 维有 效属性中取 34 维连续属性; 第二个真实数据集是 Forest CoverType 森林覆盖类型数据集，选自于 UCI 机器学习数据集，这个数据集包含 581012 条记录， 每条记录属于七种森林覆盖类型之一，实验使用全 部 54 维属性，其中 10 维连续属性，44 维布尔属性． 实验使用文献［12］中 D-Stream 算法和文献［18］中 ＲepStream 算法作为比较算法． 图 6 是在网络入侵检测数据集 KDD-CUP-99 上 的聚类质量实验结果． 参数设为近邻数 k = 10，共享 数 ks = 4，密度阈值 Ｒdi = 4，密度系数 α = 1. 2． 可以 看出在不同的滑动窗口大小下，SNDStream 算法的 聚类纯度都高于 ＲepStream 和 D-Stream 算法，算法 的交叉熵低于 ＲepStream 和 D-Stream 算法． 图 7 是在森林覆盖类型数据集 Forest CoverType 上的聚类质量实验结果，参数设置为 k = 10，ks = 6， Ｒdi = 4，α = 1. 2． 再一次的显示出 SNDStream 算法具 有非常好的聚类质量． 从全部的实验结果可以看出，SNDStream 算法 的聚类质量好于 D-Stream 算法，因为 D-Stream 算法 基于一致的网格密度，对于高维稀疏数据集上的聚 类质量并不理想． 多数情况下好于或相同于 Ｒep￾Stream 算法，但是差距相对较小，因为两种算法都是 基于 k 近邻图的思想聚类． SNDStream 算法通过定 义共享最近邻密度，更多地考虑了数据对象的当前 环境下的邻域密度，相较于以上两种算法，能够取得 更好的聚类质量． 同时，SNDStream 算法的全部聚类质量度量值 都处于一个较平均且较高的水平上，这 是 因 为 SNDStream 算法更多的考虑了数据点的当前环境， 更好地适应于数据流的动态变化，由此具有更好的 稳定性． · 7071 ·

·1708 北京科技大学学报 第36卷 0.3 100r ( SNDStream D-Stream 90 D-Stream RepStream SNDStream 80L 42200 51000 86600371400 -0.1 42200 5100086600371400 数据流 数据流 100 RepStream SNDStream 0.3 95 D-Stream D-Stream 90 0.1 SNDStream RepStream 80 150000 250000350000 450000 -0.1 150000250000 50000450000 数据流 数据流 图6聚类质量(KDD-CUP99).(a)纯度，h=200:(b)交叉熵，h=200:(c)纯度，h=1000:(d)交叉熵，h=1000 Fig.6 Quality comparison (KDD-CUP9):(a)purity,h=200:(b)cross entropy,=00:(c)purity,h=1000:(d)cross entropy,h=1000 08断间 0.7 0.6 SNDStream D-Stream 0.5 04 D-Stream 03 0.2 3200064000128000256000512000 01 3200064000128000256000512000 数据流 数据流 100 95 10 D-Stream 85 0.8 SNDStream 0.6 70 RepStream 0.4 65 D-Strean 0.2 55 50 20000 4000080000160000320000 20000400X0080000160000320000 数据流 数据流 图7聚类质量(CoverType)).(a)纯度，h=200:(b)交叉熵，h=200:(c)纯度，h=1000:(d交叉嫡，h=1000 Fig.7 Quality comparison (CoverType):(a)purity,h=200:(b)cross entropy,h=200:(c)purity,h=1000:(d)cross entropy,h=1000

北 京 科 技 大 学 学 报 第 36 卷 图 6 聚类质量( KDD-CUP-99) ． ( a) 纯度，h = 200; ( b) 交叉熵，h = 200; ( c) 纯度，h = 1000; ( d) 交叉熵，h = 1000 Fig． 6 Quality comparison ( KDD-CUP-99) : ( a) purity，h = 200; ( b) cross entropy，h = 200; ( c) purity，h = 1000; ( d) cross entropy，h = 1000 图 7 聚类质量( CoverType) ． ( a) 纯度，h = 200; ( b) 交叉熵，h = 200; ( c) 纯度，h = 1000; ( d) 交叉熵，h = 1000 Fig． 7 Quality comparison ( CoverType) : ( a) purity，h = 200; ( b) cross entropy，h = 200; ( c) purity，h = 1000; ( d) cross entropy，h = 1000 · 8071 ·

第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 ·

·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 ·

第12期 高兵等：基于共享最近邻密度的演化数据流聚类算法 ·1711· 参考文献 [10]Ren J,Ma R.Density-based data streams clustering over sliding [Babcock B,Babu S,Datar M,et al.Models and issues data windows /Proceedings of the 6th International Conference on stream systems /Proceedings of the 21st ACM SIGACTSIGMOD- Fusy systems and Knouledge Discorery.Tianjin,009:248 SIGART Symposium on Principles of Database Systems.Madison, [11]Wang H,Yu Y,Wang Q,et al.A density-based clustering 2002:1 structure mining algorithm for data streams /Proceedings of the 2]Guha S,Meyerson A,Mishra N,et al.Clustering data streams: 1st International Workshop on Big Data,Streams and Heterogene- theory and practice.IEEE Trans Knowl Data Eng,2003,15 (3): ous Source Mining:Algorithms,Systems,Programming Models 515 and Applications.New York:Association for Computing Machin- B]Zhang T,Ramakrishnan R.BIRCH:a efficient data clustering cy,2012:69 method for very large data bases /Proceedings of ACM SIGMOD [12]Chen Y,Tu L.Density-based clustering for realtime stream data Conference on Management of Data.Montreal,1996:103 /Proceedings of the 13th ACM SIGKDD International Conference 4]Ackermann M R,Martens M,Raupach C,et al.StreamKM++: on Knowledge Discovery and Data Mining.New York:Associa- a clustering algorithm for data streams.ACM I Exp Algorithmics, tion for Computing Machinery,2007:133 2012,17(2):article2.4 [13]Tu L,Chen Y.Stream data clustering based on grid density and 5]Aggarwal C C,Han J,Wang J,et al.A framework for clustering attraction.ACM Trans Knoul Discor Data,2009,3(3):12 evolving data streams /Proceedings of the 29th International Con- [14]Strehl A,Chosh J.A scalable approach to balanced,high-i- ference on Very Large Data Bases.Berlin,2003:81 mensional clustering of market-baskets /Proceedings of the 7th Aggarwal CC.Yu P S.A framework for clustering uncertain data International Conference on High Performance Computing.Berlin, streams.Proceedings of the 24th International Conference on 2000:525 Data Engineering.Cancun,2008:150 [15]Karypis G,Han E H,Kumar V.Chameleon:hierarchical cluste- ]Aggarwal C C.Han J,Wang J,et al.A framework for projected ring using dynamic modeling.Computer,1999,32(8):68 elustering of high dimensional data streams/Proceedings of the [16]Jarvis R A,Patrick E A.Clustering using a similarity measure Thirtieth International Conference on Very Large Data Bases.To- based on shared near neighbors.IEEE Trans Comput,1973,C- omto,2004:852 22(11):1025 [8]Ester M,Kriegel H P,Sander J.A density-ased algorithm for [17]Ertoz L,Steinbach M,Kumar V.Finding clusters of different si- discovering clusters in large spatial database with noise//Proceed- zes,shapes,and densities in noisy,high dimensional data / ings of the 2nd International Conference on Knowledge Discovering Proceedings of the 2003 SIAM International Conference on Data and Data Mining.Portland,1996:226 Mining.San Francisco,2003:47 9]Cao F,Ester M,Qian W,et al.Density-based clustering over an [18]Lihr S,Lazarescu M.Incremental clustering of dynamie data evolving data stream with noise /Proceedings of SIAM Conference streams using connectivity based representative points.Data on Data Mining.Bethesda,2006:326 Knoul Eng,2009,68:1

第 12 期 高 兵等: 基于共享最近邻密度的演化数据流聚类算法 参 考 文 献 ［1］ Babcock B，Babu S，Datar M，et al． Models and issues data stream systems / / Proceedings of the 21st ACM SIGACTSIGMOD￾SIGAＲT Symposium on Principles of Database Systems． Madison， 2002: 1 ［2］ Guha S，Meyerson A，Mishra N，et al． Clustering data streams: theory and practice． IEEE Trans Knowl Data Eng，2003，15( 3) : 515 ［3］ Zhang T，Ｒamakrishnan Ｒ． BIＲCH: a efficient data clustering method for very large data bases / / Proceedings of ACM SIGMOD Conference on Management of Data． Montreal，1996: 103 ［4］ Ackermann M Ｒ，Mrtens M，Ｒaupach C，et al． StreamKM + + : a clustering algorithm for data streams． ACM J Exp Algorithmics， 2012，17( 2) : article 2． 4 ［5］ Aggarwal C C，Han J，Wang J，et al． A framework for clustering evolving data streams / / Proceedings of the 29th International Con￾ference on Very Large Data Bases． Berlin，2003: 81 ［6］ Aggarwal C C，Yu P S． A framework for clustering uncertain data streams． / / Proceedings of the 24th International Conference on Data Engineering． Cancún，2008: 150 ［7］ Aggarwal C C，Han J，Wang J，et al． A framework for projected clustering of high dimensional data streams / / Proceedings of the Thirtieth International Conference on Very Large Data Bases． To￾ronto，2004: 852 ［8］ Ester M，Kriegel H P，Sander J． A density-based algorithm for discovering clusters in large spatial database with noise / / Proceed￾ings of the 2nd International Conference on Knowledge Discovering and Data Mining． Portland，1996: 226 ［9］ Cao F，Ester M，Qian W，et al． Density-based clustering over an evolving data stream with noise / / Proceedings of SIAM Conference on Data Mining． Bethesda，2006: 326 ［10］ Ｒen J，Ma Ｒ． Density-based data streams clustering over sliding windows / / Proceedings of the 6th International Conference on Fuzzy systems and Knowledge Discovery． Tianjin，2009: 248 ［11］ Wang H，Yu Y，Wang Q，et al． A density-based clustering structure mining algorithm for data streams / / Proceedings of the 1st International Workshop on Big Data，Streams and Heterogene￾ous Source Mining: Algorithms，Systems，Programming Models and Applications． New York: Association for Computing Machin￾ery，2012: 69 ［12］ Chen Y，Tu L． Density-based clustering for realtime stream data / / Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining． New York: Associa￾tion for Computing Machinery，2007: 133 ［13］ Tu L，Chen Y． Stream data clustering based on grid density and attraction． ACM Trans Knowl Discov Data，2009，3( 3) : 12 ［14］ Strehl A，Ghosh J． A scalable approach to balanced，high-di￾mensional clustering of market-baskets / / Proceedings of the 7th International Conference on High Performance Computing． Berlin， 2000: 525 ［15］ Karypis G，Han E H，Kumar V． Chameleon: hierarchical cluste￾ring using dynamic modeling． Computer，1999，32( 8) : 68 ［16］ Jarvis Ｒ A，Patrick E A． Clustering using a similarity measure based on shared near neighbors． IEEE Trans Comput，1973，C- 22( 11) : 1025 ［17］ Ertz L，Steinbach M，Kumar V． Finding clusters of different si￾zes，shapes，and densities in noisy，high dimensional data / / Proceedings of the 2003 SIAM International Conference on Data Mining． San Francisco，2003: 47 ［18］ Lühr S，Lazarescu M． Incremental clustering of dynamic data streams using connectivity based representative points． Data Knowl Eng，2009，68: 1 · 1171 ·