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