基于密度梯度的滑动窗口数据流任意形状聚类

张 华，杨 磊

(1. 江南大学人工智能与计算机学院，江苏 无锡 214000；2. 电子科技大学，四川 成都 611731)

1 引言

聚类是实现数据流挖掘的关键技术，本质就是将没有类别标签的样本参考某种规则分成若干类，确保类内样本相似性最大，类间样本则达到最小相似度，属于一种无监督学习方式，可以作为独立工具获取数据分布情况。除此之外，聚类还可以当做其它算法的预处理步骤。在滑动窗口环境下，传统聚类方法不能适应新的变化，因此对数据流聚类研究不断进行，在传统方法基础上，相关学者提出下述算法。

文献[1]提出基于分量属性近邻传播的数据聚类方法。根据动态时间弯曲方法衡量多元时间序列数据整体距离，采用近邻传播聚类方法分析整体距离矩阵与分量近似距离矩阵，实现高质量聚类。仿真结构表明，该方法不但可以准确体现总体数据特征存在的关系，还能提高数据聚类效果。文献[2]采用基于密度峰值的聚类算法构造了一个引导树，并以粒度计算的方式将其转化为胖节点引导树，在聚类结果传递到新数据到达之间的时间间隔内，将混合数据的模糊神经网络细化为具有固定脂肪节点数的新模糊神经网络，通过混合粒化衰落机制实时维护当前数据流的FNLT，该方法显示了良好的准确性和有效性。

上述两种方法虽然可以适应数据流实时变化的特性，但是数据流聚类准确率较低，聚类效果不好。针对这些缺陷，本文提出基于密度梯度的滑动窗口数据流任意形状聚类方法。由于任意形状数据流具有不确定性，因此引入不确定概念衡量数据分布情况，最大程度降低不确定性对数据流聚类结果产生的影响，通过邻近点密度搜索不动点，再由不动点和与其相邻点组成最小聚类，对小类合并实现最终聚类任务。

2 密度梯度的滑动窗口数据流任意形状聚类研究

2.1 数据流聚类基本要求探究

一系列持续并有顺序的点构成序列x1，…，xi，…，xn，将其称作数据流[3]。数据流不同于传统数据集合，因此对其进行处理时必须符合下述条件：

1)实时性：实时且连续的输出结果是数据流处理的最根本要求。如果不能很快处理到达数据流上的任一元组，则延时会不断累积，最终降低聚类质量。在多数情况下数据流会随环境的变化发生改变。

2)低空间复杂度：为确保聚类过程持续平稳运行，数据流的空间复杂度要尽可能小。假定当前时间点数据流长度表示为N，则空间复杂度通常要求在ο(poly(logN))之内。这样即可保证算法空间占用量的增长速度低于数据流自身规模增长速度[4]。

3)准确性：由于数据流规模大、速度快，针对某些复杂问题不能经过一次遍历就能获取准确结果。而数据流的处理方法最大特征就是能够返回一个近似值，且该值较为准确[5]。算法的精准度通常取决于内存空间大小，假如具有更大内存空间时，算法准确性更高。

4)适应性：在某些应用中，数据流会发生较大变化，此种变化可能为流速变化，还可能是数据分布情况变化[6]。当外部环境发生改变时，需要结合数据流变化快速调节参数，从而提高数据流处理性能。

2.2 数据流的不确定性分析

由于任意形状数据流具有不确定性，因此在聚类过程中要考虑不确定数据元组的属性值，避免不确定性对聚类结果造成巨大影响。不确定数据流分布范围较小的元组要比分布范围大的元组存在更关键作用[7]。所以在聚类时，对于不同分布范围的数据应该采用不同处理方式。

在对不确定数据进行处理时，如果其分布范围较广，则它对聚类结果会产生较大影响。为更加清楚的表示不确定性数据流元组信息，引入不确定指数与不确定度概念，可以反映数据分布范围[8]。

数据不确定指数：假设某个具有s个实例的不确定数据e，e∈D⊆Rm。要使函数符合UI：D→R+条件，则函数UF表示为

UI(x)=FB(x)

(1)

式中，FB(x)存在多种计算公式，例如，方差评判方法如下所示

(2)

也可利用最大距离计算方法

(3)

根据数据的不确定指数即可获得如下不确定度的定义。

数据不确定度：已知某个不不确定数据集合D⊆Rm，使其函数UD符合UD：D→R+，则该函数定义式如下

(4)

通过上述不确定指数与不确定度，综合考虑数据流环境限制，则滑动窗口下聚类必须处理如下问题：及时保存有效数据摘要，保留有意义的历史数据；可以满足用户在一定时间内的查询需求[9]。

2.3 密度梯度下密度单元确定

2.3.1 核心密度单元

因为对半径大小进行限制，核心密度单元数量通常高于聚簇的数量，这样可以提高聚类准确度。此外，存在最小数量制约，因此核心密度单元数量低于数据流中点数量。

核心密度单元实质上指存在任意形状聚簇的核心目标，在演化数据流中，密度单元是不断改变的，可能变为核心密度单元，也可能变为孤立点，尤其在数据分布变化较大时，变化情况更为明显，因此，必须对候选密度单元进行分析。

2.3.2 候选密度单元

(5)

(6)

(7)

候选密度单元的作用是保留在变为核心密度单元之前的数据信息，因为其本身含有点数量少，所以计算量也相对较少，不会对增加系统操作负担，但是也可以保留有效聚类信息，对最终聚类结果产生重要作用。

2.3.3 密度单元覆盖

核心密度单元与候选密度单元都可以称作微聚类，分别表示为：M1…Mp与C1…Cq，在滑动窗口大小为W前提下，该窗口中的数据集合表示为B，则具有如下性质

性质1：M∪C⊇B；

性质2：M1∩…∩Mp=Φ，C1∩…∩Cq=Φ；

性质3：对于∀p∈D，则有∃Mi∈M，p∈Mi或者∃Ci∈C，p∈Ci。

符合上述性质的微聚类集合被称作窗口下数据流的密度单元覆盖。通过上述性质可以得出，任意窗口下数据流均存在核心密度单元与候选密度单元覆盖。

2.4 密度梯度算法模型构建

点邻域：将任意一个数据样本点Q当做中心，与此点Q的d个最近邻点是半径覆盖的点集，表示为：N(Q，d)。

密度点：将任意数据样本点Q当做中心，与该点相距的d个最近邻点平均距离表示此点密度，记为D(Q，d)。

在获取密度过程中，由于度量是距离，则样本点Q的密度越高，D(Q，d)的数值越低；反之数值越大。

不动点：将数据样本Q作为中心，将距离此点第d个近邻点距离当做半径，其中邻域范围最大的点称为不动点，描述为Kemel(Q，d)。

由于邻域增加，由大密度不动点构成的聚类中点数不断上升，而密度分布小的类中点数量持续减少，最后被大类合并。如果邻域接近上限时，全部点将组成一个类，若邻域为零时，任意一点都属于不动点，单独为一类。

d值大小会决定初始聚类后类的数量，所以d的取值成为聚类关键问题。d值越小，与其相对的初始聚类数量越多，且其中包括d取最大值时初始聚类的类中心。

边界点：如果任意类Ci中样本数据点Q的d近邻域中的点分为两个或更多的类，则称这种点为类Ci的边界点。全部边界点集合记为Boader(Ci)。

将两个聚类合并程度函数H(C1，C2)当做两类合并的判断依据，利用边界点与各类中具有点数的熵值构建算法模型

(8)

式中，c1与c2分别表示C1、C2中包含的点数量，c代表C1、C2中具有的边界点数量，如果边界点数量是零，则合并程度函数值是+∞。

2.5 数据流任意形状聚类实现

数据流演化过程通常分为三种情况：聚类消失、产生新聚类以及聚类中心点漂移。聚类演化示意图如下所示：

图1 聚类演化示意图

结合上述构建的算法模型，能够确定如下滑动窗口数据流任意形状聚类步骤如下：

1)进行初始化处理，获取密度分布情况

计算每个点的d近邻，将d近邻平均距离当做此点密度。

2)确定不动点，实现初始聚类

任意挑选一个没有经过分类的样本点Q，计算其d近邻内最大密度点R，结合点R与点Q的密度分别在两种情况下进行比较：

如果R点密度比Q点密度小，或者D(R，d)的值高于D(Q，d)，则Q点属于一个不动点，对其赋予新的类别编号。

如果R点密度高于Q点密度，则需要根据R点聚类情况做出判定，假设此点类别号已经去顶，则可以将此点聚类号当做Q点类别号，反之需要获取以点R当做起始点的不动点。

若寻找到对应的不动点后，对此路径下全部点赋予类别号；进行循环操作直至全部点均被分类。

3)调节边界点

在边界点的d个近邻点类别号中，通过多数表决手段选取该边界点类别号：

(9)

公式中，f(x)表示x的聚类号。

4)获取不同边界点分布情况

对各类中边界点分布特征进行统计，如果∃R∈Cj，Q∈Boader(Ci)，并且R∈N(Q，d)，则有：

Num(NearCluster(Ci，Cj))+1

→Num(NearCluster(Ci，Cj))

(10)

式中，Num(NearCluster(Ci，Cj))表示Ci，Cj类间边界点数量。

在聚类过程中分为下述两种情况：如果给定聚类数，则根据合并程度函数大小进行排序，将拥有最小函数值的两类合并，当符合要求或在任意两类不存在相同边界点时停止合并；在没有给定聚类数情况下，同样结合合并程度函数对其排列，在最小合并函数值高于给定值时，操作停止，反之合并拥有最小函数值的两类，与此同时重新获取和其它有关联的近邻类合并程度函数，并重复上述步骤，直至算法停止，完成数据流任意形状聚类。

3 仿真研究

为验证本文所提的基于密度梯度滑动窗口数据流聚类方法的有效性，通过Windows XP系统进行仿真。实验环境为Intel Pentium 4处理器，8GB内存。实验过程中构建8台虚拟机，虚拟机参数设置情况如表1所示。

表1 虚拟机参数配置表

通过上述环境，根据虚拟机参数设置，绘制不确定数据密度吸引点，如图2所示。

图2 不确定数据密度吸引点

由上图可以看出，从一个不确定数据出发，找到一个不确定数据密度吸引点的过程。每次它的梯度方向，都指向不确定数据稠密而且不确定数据密度大的区域，当某个不确定数据的梯度方向上数据的不确定密度值小于原先的数据点时，则停止计算数据的梯度，此时先前数据即为局部范围内的密度最大点，即不确定数据密度吸引点。此时则称不确定数据A是被不确定数据B密度吸引点吸引的。

为使仿真具有可比性，将本文方法与文献[1]方法、文献[2]方法进行对比。分别比较三种方法在聚类处理中的加速比、准确性以及滑动窗口敏感程度。对比结果分别如图3所示。

图3 不同方法加速比对比结果示意图

从图中可以看出，所提方法加速比呈线性变化趋势，且始终高于其它方法。在数据流规模较小时，启动和通信需要较长时间，随着数据规模扩大，本文方法加速比性能逐渐提高，主要因为降低节点之间通信量。利用本文方法对滑动窗口数据流任意形状聚类，如图4所示。

图4 聚类效果图

由上图4可以看出，这两个子聚类能够准确区分两个类别，不会造成各聚类所覆盖的区间重叠，同一位置的点被归入不同的聚类的情况。

聚类结果通常使用准确性作为评价指标，Jaccard系数是常用评价方法之一，其计算公式为：

JC=

(11)

利用上述公式计算得出文献[1]方法和本文方法的聚类准确性，结果如下所示：

图5 不同方法聚类效果对比图

由上图可以看出，文献[1]方法处理这个数据集的聚类问题效果较差，而本文所提算法成功地找出了数据的流形结构。具体聚类准确性结果如下。

表2 不同方法聚类准确性结果分析

由上表可知，随着数据规模增加，文献[1]方法的聚类准确性有所下降。但是所提方法下降趋势并不明显，这是由于该方法对不确定性进行分析，提高聚类精准度。

相似度矩阵是否理想直接关系到聚类结果的好坏，当相似性矩阵是分块对角矩阵这一理想情形时，聚类算法可以得到完全正确的聚类结果。则本文方法和文献[2]方法的相似度矩阵如图6所示。

图6 不同方法相似度矩阵

由上图可知，显然，文献[2]方法距离矩阵块对角分布不明显，无法体现不同流形的区别，而经过核自适应映射后的流形距离测度得到的相似度矩阵显示了明显的分块对角模式，较好地体现了整体样本集的聚类信息。这是因为在确定每个密度单元时，都引入必须具备当前窗口数据这一关键约束条件，因此即使数据规模扩大也不会对聚类结果产生太多影响。

4 结论

数据流聚类问题始终是数据挖掘领域难点，本文在密度梯度基础上对滑动窗口数据流任意形状进行聚类。综合分析不确定数据具体信息，减少对数据聚类影响，构建密度梯度模型，实现聚类。仿真结果表明，该方法聚类准确性高，加速比性能良好。但是在数据流中经常会有噪声出现，其特性和演化的数据流相似，因此怎样去除噪声、区别噪声与演化数据是今后研究的重要问题。