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

第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=<d1,山2，…，dh>,表示欧式空间上的数 一致的密度参数和概要的格信息，往往不能得到更 据流S在时刻t滑动窗口h上的一个数据对象集 准确的聚类结果；随着数据维数的增长，网格数将呈 合，其中d=<d1,d2,,dm>表示一个数据对象 指数增长，由此导致处理效率的大幅下降，及数据稀 (其中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)若<d,d,>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)若<d,d>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 ·