韩东红 , 宋明 , 张宏亮 , 王佳茜 , 王嘉兴 , 王国仁
东北大学 计算机科学与工程学院, 沈阳 110819

收稿日期：2016-09-27
基金项目：国家自然科学基金面上项目（61173029，61672144）
作者简介：韩东红(1968-), 女, 副教授。E-mail:handonghong@cse.neu.edu.cn


摘要：不确定性的出现使传统算法无法直接用于聚类不确定数据流。该文提出一种不确定数据流环境下基于密度的聚类算法，其中提出不确定度的概念以衡量不确定数据的分布信息，并在改进面向确定数据的聚类算法DENCLUE的基础上，提出一种可处理数据不确定度的UDENCLUE算法，以降低数据的不确定性对聚类结果产生的影响；提出滑动窗口下基于密度的不确定数据流聚类算法USDENCLUE，通过聚类特征指数直方图技术实现快速剪枝，可以高效处理噪音数据、演化数据流并生成任意形状的簇；采用真实数据集及人工合成数据集对USDENCLUE与CluStream聚类算法进行比较，实验结果表明了所提出算法的高效性和有效性。
关键词：不确定数据流聚类密度滑动窗口
Algorithm for clustering uncertain data streams based on density
HAN Donghong, SONG Ming, ZHANG Hongliang, WANG Jiaxi, WANG Jiaxing, WANG Guoren
School of Computer Science and Engineering, Northeastern University, Shenyang 110819, China


Abstract: Uncertainties make it impossible to cluster uncertain data streams using traditional clustering algorithms. This paper presents a density-based clustering algorithms for uncertain data stream environments. An uncertainty metric is used to measure the distribution information in the uncertain data. The uncertain data streams DENCLUE algorithm (USDENCLUE) is then modified to deal with uncertainty data to minimize the impact of the data uncertainty on the clustering results. A density-based clustering algorithm is then given for uncertain data streams with a sliding window to rapidly prune the clusters using an exponential histogram of the cluster features. This algorithm can efficiently handle noisy data in evolving data streams to generate arbitrary clusters to improve the clustering quality. Comparisons of this algorithm with the CluStream clustering algorithm on real and synthetic data sets show the efficiency and effectiveness of this algorithm.
Key words: uncertain data streamsclusteringdensitysliding window
随着计算机网络及网络接入设备的迅速发展，在诸如无线传感器网络(wireless sensor networks，WSN)^[1]、射频识别(radio frequency identification, RFID)^[2-3]等众多应用中产生了大量不确定数据流。不确定数据流作为一种典型的大数据模型，具有海量无穷、流速可变、单遍扫描、流数据存在不确定性等特点。针对不确定数据流环境的聚类分析有着重要的应用前景，但已有的面向静态数据或确定数据流的聚类算法无法直接应用于不确定数据流环境。因此，开展面向不确定数据流环境的聚类算法研究十分必要。
当前使用最多的不确定数据模型为可能世界模型，其中数据不确定性分为元组级不确定性和属性级不确定性^[4]。为不失一般性，本文的研究对象是以离散概率密度函数表示的元组级不确定数据流。
作为数据流聚类的经典算法之一，CluStream算法^[5]采用聚类演化数据流的双层框架结构，将聚类过程分为在线聚类和离线聚类两部分。在线聚类快速处理到达窗口的数据，维护固定数目的微簇(micro-clusters)并存储适当的汇总统计信息；离线聚类利用汇总统计信息进行宏聚类。针对不确定数据流，Aggarwal提出了一种聚类不确定数据流的框架^[6]和一种在映射空间上的不确定数据流聚类算法^[7]。2009年，文[8]提出通过利用不确定聚类特征的指数直方图来获取最新数据的分布特征，采用双层架构模型对不确定数据流进行聚类。2010年，文[9]针对元组级不确定数据模型，提出EMicro算法以聚类分析不确定数据流。2012年，文[10]同时考虑不确定元组期望值和不确定性，提出基于Voronoi图的聚类算法以减少滑动窗口中期望距离的计算量。文[11]提出了一种基于密度的聚类算法，以较低的时间代价发现高维不确定数据流中任意形状的簇。2014年，文[12]提出一种有效的概要数据结构，用于概括同时具有两种不确定性元组的簇。2015年，文[13]提出了一种基于密度网格的算法C_UStream，该算法利用滑动窗口对不确定数据流进行聚类，可发现任意形状的簇。
经典的面向带有噪音的确定多媒体大数据的聚类算法DENCLUE(density based clustering)^[14]的基本思想是基于所有数据点的影响函数的和进行密度分析，即根据密度吸引点来识别不同簇，而且不同形状的簇可以通过基于密度函数的简单等式进行描述。与文[14]的数据模型相似的是，在许多实际的数据流应用中流数据具有高维属性并且包含大量噪音，但不确定数据流的聚类分析所面临的主要挑战是如何对源源不断到达的流数据进行实时高效聚类处理以及算法如何反映数据流的演化问题，不确定性的引入增加了解决这些挑战的难度。作为DENCLUE算法的扩展，本文侧重基于密度的不确定数据流聚类算法研究，针对不确定数据提出数据的不确定度概念，通过对不同分布范围的不确定数据计算其不确定度，有效提取不确定数据的分布信息；通过改进面向静态环境确定数据的聚类算法DENCLUE，提出基于密度的静态不确定数据聚类算法UDENCLUE (uncertain DENCLUE)，即通过使用不确定度信息，对不同分布范围的数据给予不同处理方式，以降低不确定性对聚类结果的影响；提出滑动窗口下基于密度的不确定数据流聚类算法USDENCLUE (uncertain data streams DENCLUE)，即对特定时间窗口中的不确定数据流进行聚类分析以形成任意形状的簇，该算法因其滑动窗口的特点和密度阈值的设定可有效处理噪音点及演化数据流。
1 基于密度的不确定数据流聚类算法1.1 相关定义给定一个不确定数据集D?R^d，其中包含s个实例的不确定元组X_i∈D?R^d，X_i={(x_i1, p_i1), …, (x_ij, p_ij)}(j=1, 2, …, s)，其中p_ij∈(0, 1), 且$\sum\limits_{j = 1}^s {{p_{ij}} = 1} $，x_ij有d维，即x_ij=(x_ij¹, x_ij², …, x_ij^d)。与本文相关的定义给定如下：
定义1?元组不确定指数(uncertain index，UI)?使函数满足UI:D→R⁺，其定义为

${\text{UI}}\left( X \right) = {F_{\text{B}}}\left( X \right).$

(1)

其中：F_B(X)可有不同的计算公式，但需满足不确定元组分布范围越广其值越大、不确定元组的分布范围越小其值越小。
定义2?元组不确定度(uncertain degree, UD)?使函数满足UD:D→R⁺，函数UD定义为

${\text{UD}}\left( X \right) = 1 - {{\text{e}}^{ - \frac{{{\text{UI}}\left( X \right)}}{{2{\sigma ^2}}}}}.$

(2)

其中σ是根据不同数据集的不确定指数和数据集本身的距离值属性得出的一个参数。根据不同应用对不确定数据分布的敏感程度不同，可指定不同的σ以获得较好的聚类结果。
定义3?不确定元组与确定元组影响函数(uncertain influence function, UIF)?给定一个不确定数据集D?R^d，确定元组Y∈R^d和不确定元组X∈D，使影响函数满足UIF:R^d×D→R⁺，其定义为

$\begin{array}{*{20}{c}} {{\text{UIF}}\left( {X,Y} \right) = } \\ {\sqrt {\left( {1 - {\text{UD}}\left( X \right)} \right)} {{\text{e}}^{ - \frac{{d{{\left( {Y,X} \right)}^2}}}{{2{\sigma ^2}}}\left( {1 - {\text{UI}}\left( X \right)} \right)}}.} \end{array}$

(3)

其中d为Euclid距离或Manhattan距离。
定义4?不确定元组影响函数UIF′?给定一个不确定数据集D?R^d和两个不确定元组X, Y∈D，影响函数UIF′:D×D→R，其基本公式定义为

$\begin{array}{*{20}{c}} {{\text{UIF'}}\left( {X,Y} \right) = } \\ {\sqrt {\left( {1 - {\text{UD}}\left( X \right)} \right)\left( {1 - {\text{UD}}\left( Y \right)} \right)} \cdot } \\ {{{\text{e}}^{ - \frac{{d{{\left( {Y,X} \right)}^2}}}{{2{\sigma ^2}}}\left( {1 - {\text{UD}}\left( X \right)} \right)\left( {1 - {\text{UD}}\left( Y \right)} \right)}}.} \end{array}$

(4)

定义5?不确定元组密度(uncertain tuple density，UTD)?给定一个不确定数据集D∈R^d和一个不确定元组X∈D?R^d，X_i(i=1, 2, …, N)为X周围各点，则X的密度为

${\text{UID}}\left( X \right) = \sum\limits_{i = 1}^N {{\text{UIF'}}\left( {X,{X_i}} \right)} .$

(5)

定义6?不确定元组梯度?UF?(X)?给定一个不确定数据集D∈R^d和一个不确定元组X∈D?R^d，不确定元组的梯度为

$\nabla {\text{UF}}\left( X \right) = \sum\limits_{i = 1}^N {\left( {{X_i} - X} \right){\text{UIF}}\left( {X,{X_i}} \right)} .$

(6)

定义7?不确定元组密度吸引点?若一个不确定元组X^*是密度吸引点，那么在不确定元组影响函数作用下，不确定元组X^*的密度值是局部最大的。
定义8?不确定数据中心定义的簇?一个不确定元组密度吸引点X^*所对应的不确定数据中心定义的簇，是不确定数据集D?R^d的一个子集C?D，而且X∈C是被不确定元组密度吸引点X^*吸引的点，其中UTD(X^*)>ξ。
定义9?不确定数据任意形状的簇?对于不确定元组密度吸引点的集合XS，其不确定数据任意形状的簇是不确定元组中心定义的簇C?D?R^m的集合，满足如下条件：
1) ?X∈C，?X^*∈XS:UTD(X^*)>ξ，X是被X^*密度吸引的；
2) ?X₁^*，X₂^*∈XS:?P?D，从X₁^*到X₂^*，?p∈P:UTD(p)>ξ，其中p为X₁^*到X₂^*路径上的元组。
定义10?本地不确定元组密度(local uncertain tuple density，UTD_L)?给定一个不确定数据集D∈R^d和一个不确定元组X∈D?R^d，则本地不确定元组密度可以表示为

${\text{UT}}{{\text{D}}_{\text{L}}}\left( X \right) = \sum\limits_{Y \in {\text{near}}\left( X \right)} {{\text{UIF}}\left( {X,Y} \right)} .$

其中：$Y \in {\text{near}}\left( X \right){\text{:}}d\left( {X,Y} \right) \leqslant \frac{k}{{1 - {\text{UD}}\left( X \right)}}\sigma $, 为指定正整数。
定义11?不确定微簇结构(uncertain micro-cluster structure，UMCS)?第i个微簇中包含n个d维不确定元组X_i1, …, X_in，每个元组标记唯一的到达时间戳t₁，…，t_n，这个不确定流元组的簇结构可表示为2d+4的元组结构，即(U₁^X, U₂^X, U, density, t, n)，其中U₁^X和U₂^X分别是d维向量，每个属性的含义如下：
1) 不确定元组每一维期望值的和存储在U₁^X中，即U₁^X包含d维数据值，U₁^X中第p维的数据值可由公式$\sum\limits_{j = 1}^n {X_{{i_j}}^p} $得到，它是U₁^X中第p维的数据值的直接表示；
2) 不确定元组每一维期望值的平方和存储在U₂^X中，即U₂^X包含d维数据值，U₂^X中第p维的数据值可由公式$\sum\limits_{j = 1}^n {{{\left( {X_{{i_j}}^p} \right)}^2}} $得到，它是U₂^X中第p维的数据值的间接表示；
3) 每个UMCS结构都有类似于元组不确定度的数值并存储于U，表示该UMCS结构的不确定数据分布范围，其值可通过U₁^X、U₂^X计算；
4) 每个不确定元组的密度和存储于density中；
5) 最后一个元组加入到此微簇的时间为t，即用于保存UMCS结构最后更新的相对时间；
6) UMCS结构中不确定元组数量存储在n中。
数据流聚类算法中，微簇结构的属性需要具备可加性才可以满足数据流环境下的聚类要求，当两个微结构合并时：
U₁^X(C₁∪C₂)：根据U₁^X的定义，可以通过两个微簇的U₁^X(C₁)与U₁^X(C₂)的和得到U₁^X(C₁∪C₂)。
U₂^X(C₁∪C₂)：根据U₂^X的定义，可以通过两个微簇的U₂^X(C₁)与U₂^X(C₂)的和得到U₂^X(C₁∪C₂)。
UMCS(C₁∪C₂)：根据UMCS的定义其可通过U₁^X和U₂^X计算得到，而U₁^X和U₂^X具备可加性，故UMCS同样具有可加性。
density(C₁∪C₂)：可直接通过两个微簇中不确定元组的density相加得到，因为尽管两个微簇进行了合并，但簇中的分布信息没有发生变化。
n(C₁∪C₂)：通过两个不确定微簇元组个数相加即可满足可加性。
t(C₁∪C₂)：存储距离当前时间最远的时间戳。
1.2 算法描述在对不确定数据的聚类分析中，数据的不确定性对聚类结果有很大影响。在本文所处理的数据模型中，一个不确定元组X由s个实例组成，构成不同元组的实例有着不同的分布范围，也对聚类过程有不同的作用。如图 1所示，设不确定元组X和Y各自包含10个二维离散实例，其离散实例的分布不同但质心是相同的，即X=(0.5, 0.5)，Y=(0.5, 0.5)。在聚类处理中若只使用不确定元组的质心或期望距离进行计算，将视X和Y为同一元组，则会忽视了实例的不同分布对聚类结果的作用，影响聚类效果。

图 1 不确定元组实例

图选项

基于此，本文首先给出元组不确定度的概念，用于表示不确定元组中实例的分布范围，其次提出基于密度的不确定数据聚类算法UDENCLUE和滑动窗口下基于密度的不确定数据流聚类算法USDENCLUE。
1.2.1 基于密度的不确定数据聚类算法为解决不确定数据的任意形状簇的聚类问题，本文侧重研究基于密度的方法，目的是将密度较大即数据分布稠密的元组形成一个簇，被密度较小元组分开的其他密度较大元组形成另一个簇，以此得到最终聚类结果。
本文首先针对不确定元组的实例具有不同分布范围，通过式(1) 和(2) 计算不确定元组X的不确定度UD(X)。聚类时可通过计算元组不确定度，区别对待具有不同分布的不确定元组以提高聚类质量。其次，根据式(4) 可得到两个不确定元组之间的影响函数，根据式(5) 计算任一不确定元组的密度，即此不确定元组与其他元组的影响函数之和。然后，根据不确定元组梯度的计算，在给定任意一个不确定元组的情况下，找出该元组周围数据点分布更为密集的区域，即计算不确定元组密度吸引点，具体流程如图 2所示。

图 2 获取不确定元组密度吸引点算法getDensityAttractor

图选项

该算法采用爬山算法的思想，即为找到一个不确定元组密度吸引点，每次都要找到对其影响最大的方向并按照一定的距离前进。每到新位置时，比较X_new与X_old的不确定密度：若UTD(X_new)>UTD(X_old)，则寻找当前位置的梯度方向并循环执行下去，直至UTD(X_new)＜UTD(X_old)，即无法找到一个比X_old密度大的元组，此时X_old即为不确定元组密度吸引点。
得到不确定元组密度吸引点后，即可进行不确定数据的聚类分析，见图 3。首先，计算数据集中每个X_i的不确定度和不确定元组密度。其次，计算该元组的不确定密度吸引点：若其已存在，则把X_i合并到以此不确定元组密度吸引点生成的不确定数据中心定义的簇中。若其不存在，当X_i的不确定密度值小于阈值ξ时，说明X_i周围数据分布较为稀疏，于是判断X_i为噪音点，不把它划入任何簇中，同时继续扫描不确定数据集；若X_i的不确定元组密度值大于规定阈值ξ，则以X_i为密度吸引点，新建一个不确定数据中心定义的簇。

图 3 基于密度的不确定数据聚类算法UDENCLUE

图选项

当扫描完所有不确定元组后，则会生成一系列不同大小的中心定义的簇，每个簇都是由一个不确定数据密度吸引点和其他若干被其吸引的不确定元组组成，其中不确定数据密度吸引点的密度都大于指定的阈值ξ，而被密度吸引点吸引的点的密度则不需满足此要求。如果在某个区域，其不确定数据分布稠密，这个区域内众多不确定元组的密度都会大于阈值ξ，这表示该区域内不确定数据中心定义的簇可能是一个更大的簇，因此应该把这些不确定数据分布非常稠密的簇合并成一个更大的簇，以表示这部分元组的性质是相同的。
1.2.2 基于密度的不确定数据流聚类算法一般情况下，基于密度的聚类算法需要维护的数据信息量大于基于距离等的其他算法，而且不确定数据流环境对聚类分析有着较高的实时性要求。为减少存储空间和加快处理速度，本文使用聚类特征指数直方图(exponential histogram of cluster features, EHOCF)，即每个簇由一个EHOCF表示，每个EHOCF包含多个UMCS结构，且每个UMCS结构有自己特定的等级, 这样可以存储足够信息以满足滑动窗口删减需求及聚类需求，同时减少存储不确定流数据的数据量。
第i个簇存储结构是簇微结构UMCS的集合，它所包含的不确定流元组X_i1, X_i2, …, X_ik分别在时刻t_i1, t_i2, …, t_ik流入。假设n＜m，则时间戳t_in＜t_im，这样可以通过不确定元组流入的相对顺序，把不确定元组分成若干组G₁，G₂ …，需满足如下条件：
1) 当i＜j时，组G_i内的不确定流元组先于G_j内的不确定流元组到达；
2) 假设N(G_i)表示第i级包含微簇结构UMCS的个数，则N(G₁)=1，对任意j(j>1)，N(G_j)=N(G_j-1)或者N(G_j)=2N(G_j-1)，即后面存储的微簇结构UMCS的个数等于或是前面微簇结构数量的2倍；
3) 当N(G)=2ⁱ时，则称组G的级别为i，除了最高级别的组以外，每个级别都包含$\left\lceil {1/\varepsilon } \right\rceil $或$\left\lceil {1/\varepsilon } \right\rceil + 1$个微簇结构，这里ε为不同应用指定的误差参数，0＜ε＜1。
根据簇存储结构的定义，可以按照如下方法进行簇的维护：
1) 当一个新的不确定流元组加入到簇中时，则新建一个0级的微簇存储结构UMCS(C)，这里C表示包含特定不确定流元组的不确定数据集；
2) 将新生成的UMCS(C)存入簇存储结构中，若0级组中已经包含$\left\lceil {1/\varepsilon } \right\rceil + 2$个UMCS，则存入新生成的UMCS后，就要组合两个距离当前时间最远的0级UMCS形成一个1级UMCS，使0级UMCS数量减少到$\left\lceil {1/\varepsilon } \right\rceil $。同理，存入新生成的1级UMCS到簇存储结构，查看级别为1的UMCS个数是否需要合并，若需要合并则生成一个新的高级UMCS，至某个等级的UMCS不需合并为止。
用此结构维护每个簇的信息，每当簇中增加了一个新的不确定流数据，按照不同等级中UMCS的数量，通过UMCS可加性，合并距离当前时间较远的流元组，可避免存储大量不确定流数据，节省空间的同时提高聚类算法的速度。具体更新簇结构的流程见图 4。

图 4 更新簇结构Update

图选项

为针对特定时间窗口中的不确定数据流进行聚类分析以形成任意形状的簇，同时根据滑动窗口的特点和密度阈值的设定处理噪音点及演化数据流，本文提出滑动窗口下基于密度的不确定数据流聚类算法USDENCLUE，见图 5。当新的不确定流元组到达时，计算其不确定度、密度，通过簇结构的Update算法更新当前滑动窗口中的簇信息，并计算其密度吸引点。

图 5 滑动窗口下基于密度的不确定数据流聚类算法USDENCLUE

图选项

由于不确定流数据的聚类性质可能是随着时间的演化而变化的，因此USDENCLUE聚类算法与UDENCLUE算法在噪音点的监测方案中存在着不同的规则，即若某个不确定元组的密度吸引点小于阈值ξ，除了表明它现在可能是噪音点，另一种可能则是它代表新簇的一个开始，因此算法都会为它建立一个新簇。重复以上操作直到用户检查聚类结果时为止，此时合并临近中心定义的簇。
2 实验结果分析通过对真实数据集及人工合成数据集的实验，验证本文提出USDENCLUE算法的有效性和高效性，并与CluStream算法^[5]进行性能对比。
2.1 实验环境本实验所用的计算机内存是2 GB DDRII，硬盘为160 GB，CPU为Intel(R) Core(TM)2 Duo E8400 @3.00 GHz，操作系统采用Microsoft Windows XP SP2，开发环境为Microsoft Visual Studio 2008，编程语言选择C++。
2.2 数据集2.2.1 真实数据集该数据集来自美国麻省理工学院(MIT)林肯实验室管理的一个局域网络两周内的TCP连接记录。这些记录或者是一个正常的连接，或者是一条入侵或攻击记录。攻击的类型包含4类：DOS(拒绝服务)、R2L(未授权远程访问)、U2R(未授权访问本地超级用户)、PROBING(监视或者端口扫描)。数据集中的每条连接记录都为42维的数据。鉴于本文所对比的CluStream算法使用其中的34个连续属性，为使实验对比公平有效，本文同样使用CluStream算法中对应的34个连续属性的数据集进行聚类分析。
2.2.2 人工合成数据集为更好地描述数据流演化的情况，本文使用演化率表示数据流的演化，即连续两个不重叠的滑动窗口生成簇的差异率。一般来说，后一窗口删除了前一窗口一半的簇，增加了前一窗口一半数量的新簇，则演化率为1。为了测试算法应对离群点的能力，人工合成的数据集需要人为加入一些噪音点。本文定义在每100个元组据中加入1个噪音点，则噪音率为1%。由于上述真实数据集和人工合成数据集都是确定的，在此基础上为每个元组生成不同分布范围的不确定实例，同时本文所处理的所有数据集全部归一化到[0, 1]^d数据空间。
2.3 实验分析与CluStream算法进行性能对比时，本文通过计算不确定数据的期望值来表示确定数据，以使CluStream算法可以处理不确定数据。本文实验所用的参数如表 1所示，相关参数值的设定是在考虑其对聚类结果影响之后选取的适当值。在测量聚类质量时，本文用查准率与查全率相结合的方法，综合评判聚类效果。
表 1 相关实验参数设置

参数	值	含义
N	250 000	数据集大小
d	34	不确定元组维度
s	10	不确定元组实例数
UDmax	0.2	最大不确定度
EV	20%	数据流演化率
Noise	2%	噪音率
h	10 000	聚类窗口大小
σ	0.3	不确定度即影响函数参数
ξ	5	密度阈值
k	2	本地影响函数参数
ε	0.1	滑动窗口误差参数
δ	0.1	梯度步幅参数

表选项






2.3.1 算法有效性图 6和7分别给出了USDENCLUE算法与CluStream算法运行在真实网络入侵数据集及人工合成数据集上的查准率与查全率。

图 6 两种算法在真实网络数据集上的查准率和查全率

图选项

图 7 两种算法在人工合成数据集上的查准率和查全率

图选项

在图 6所示的两种算法在网络入侵真实数据集上的性能对比中，USDENCLUE算法的查准率与查全率均明显高于CluStream算法。其原因在于USDENCLUE是基于密度的聚类算法，将当前数据分布的稠密程度作为聚类的划分依据，聚类结果更能体现数据的分布情况，同时可以得到任意形状的簇；而CluStream算法则基于距离，不能以当前元组的实例分布情况作为划分依据。对不确定数据流聚类分析而言，USENCLUE算法可以从不确定流数据中提取其不确定信息，使元组的不确定性对聚类影响降低，因此聚类质量较高；而CluStream聚类算法仅使用不确定元组的期望而没有尽可能使用不确定数据的信息，从而影响了聚类质量。
图 7所示的是两种算法在人工合成数据集上的性能对比，人工合成数据集使用的是演化率为20%的数据集，并加入了2%的噪音点。图 7表明，CluStream算法不能很好地处理噪音点及数据分布情况变化剧烈的数据流，使得聚类质量低下；而USDENCLUE聚类算法通过不同簇的密度值有效处理噪音点，且使用滑动窗口的聚类方法及时删除过期元组，可以很好地处理演化数据流。
2.3.2 元组不确定度图 8展示了不确定元组的不确定度从0.1增大到0.5时，USDENCLUE算法与CluStream算法的聚类质量曲线。由于前者在聚类时能够针对不确定元组实例的不同分布范围，即针对不同不确定度的元组使用不同的处理策略，降低任意可能发生的实例对聚类结果的影响，因此当元组不确定度增大时依然能保证良好聚类效果；而CluStream算法在聚类过程中只使用期望距离计算元组相似度，当元组不确定度增大后依然使用相同的聚类策略，无法有效利用元组不确定信息，因此聚类质量下降较快。

图 8 两种算法性能随元组不确定度的变化

图选项

2.3.3 噪音数据本文在人工合成数据集中加入不同等级的噪音点，分别运行USDENCLUE算法与CluStream算法，并对其运行结果进行分析。图 9给出了两种算法在不同噪音率中的查准率曲线。可以看出，噪音率的增大对USDENCLUE聚类算法的影响不大，USDENCLUE算法在存在噪音的不确定数据流中同样有着较好的聚类结果；而CluStream算法则表现不理想，这是由于其标界窗口随着时间的推移会出现内存到达上限的问题。因此，CluStream算法必需人为指定微簇数量，当达到上限时，根据不同的情况删除最久未更新的微簇或合并临近的簇，因此当噪音点的数量增多时，会迫使CluStream算法大量合并不相关的微簇或删除近期活跃的微簇，造成聚类质量降低；USENCLUE算法利用高效的剪枝策略，在最终合并相近聚类时会删除密度值小于阈值的簇，故可在保持潜在簇的同时消除噪音点。

图 9 两种算法处理噪音效果比较

图选项

2.3.4 处理演化数据流数据流环境中数据的分布存在演化特征，因此一个好的数据流聚类算法应该具备处理演化数据流的能力。图 10显示的是数据演化率从10%变化到50%时，USDENCLUE算法与CluStream算法的查准率对比。可以看出，在不同的数据演化率下USDENCLUE的查准率明显高于CluStream算法。这是由于CluStream算法的思想是在滑动窗口上通过两次存储的快照信息得出结果，故在当前时刻聚类结果会受到先前信息的影响，且在出现新演化的不确定元组时，会根据不同情况删除过早簇或合并两个临近簇，导致可能删除应该保留的簇或者可能合并两个不同的微簇到一个簇中，最终会影响聚类质量；而USDENCLUE算法随着时间推移删除过期的不确定元组，消除先前元组对聚类的影响，可处理演化数据流并得到较理想的聚类结果。

图 10 两种算法处理演化数据流的查准率对比

图选项

3 结论针对当前不确定数据流聚类应用中如何处理不确定性并高效实时提供任意形状聚类结果的问题，本文首先提出不确定度的概念以衡量不确定数据的分布信息，并提出一种基于密度的面向静态不确定元组的UDENCLUE聚类算法，利用不确定度降低元组不确定性对聚类结果产生的影响；其次，提出滑动窗口下基于密度的不确定数据流聚类算法USDENCLUE，通过聚类特征指数直方图技术实现快速剪枝功能，使其高效处理噪音数据、演化数据流并生成任意形状的簇。最后，采用真实数据集及人工合成数据集将USDENCLUE与CluStream聚类算法进行比较，实验结果表明了本文所提出的USDENCLUE算法的高效性和有效性。

参考文献

[1]	Deshpande A, Guestrin C, Madden S, et al. Model-driven data acquisition in sensor networks[C]//Proceeding of the 30th International Conference on Very Large Data Bases. New York, USA:ACM Press, 2004:588-599.
[2]	GU Yu, YU Ge, ZHANG Tiancheng. RFID complex event processing techniques[J]. Journal of Frontiers of Computer Science and Technology, 2007, 1(3): 255–267.
[3]	Jeffery S R, Garofalakis M N, Frwanklin M J. Adaptive cleaning for RFID data streams[C]//Proceeding of the 32nd International Conference on Very Large Data Bases. New York, USA:ACM Press, 2006:163-174.
[4]	ZHOU Aoying, JIN Cheqing, WANG Guoren, et al. A survey on the management of uncertain data[J]. Chinese Journal of Computers, 2009, 32(1): 1–16. DOI:10.3724/SP.J.1016.2009.00001
[5]	Aggarwal C C, Han J, Wang J, et al. A framework for clustering evolving data streams[C]//Proceeding of the 29th International Conference on Very Large Data Bases. New York, USA:ACM Press, 2003:81-92.
[6]	Aggarwal C C, Yu P S. A framework for clustering uncertain data streams[C]//Proceeding of the 24th International Conference on Data Engineering. Cancún, México, 2008:150-159.
[7]	Aggarwal C C. On high dimensional projected clustering of uncertain data streams[C]//Proceeding of the 25th International Conference on Data Engineering. Shanghai, 2009:1152-1154.
[8]	Huang G Y, Liang D P, Ren J D, et al. An algorithm for clustering uncertain data streams over sliding windows[C]//Proceeding of the 6th International Conference on Digital Content, Multimedia Technology and Its Applications. Seoul, Korea, 2009:173-177.
[9]	ZHANG Chen, JIN Cheqing, ZHOU Aoying. Clustering algorithm over uncertain data streams[J]. Journal of Software, 2010, 21(9): 2173–2182.
[10]	CAO Keyan, WANG Guoren, HAN Donghong, et al. A framework for high-quality clustering uncertain data stream over sliding windows[C]//Proceeding of the 13th International Conference on Web-Age Information Management. Harbin, 2012:308-313.
[11]	YANG Yue, LIU Zhuo, ZHANG Jianpei, et al. Dynamic density-based clustering algorithm over uncertain data streams[C]//Proceeding of the 20129th International Conference on Fuzzy Systems and Knowledge Discovery (FSKD). Chongqing, 2012:2664-2670.
[12]	JIN Cheqing, Yu J X, ZHOU Aoying, et al. Efficient clustering of uncertain data streams[J]. Knowledge and Information Systems, 2014, 40(3): 509–539. DOI:10.1007/s10115-013-0657-3
[13]	Dallachiesa M, Jacques-Silva G, Gedik B, et al. Sliding windows over uncertain data streams[J]. Knowledge and Information Systems, 2015, 45(1): 159–190. DOI:10.1007/s10115-014-0804-5
[14]	Hinneburg A, Keim D A. An efficient approach to clustering in large multimedia databases with noise[C]//Proceeding of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Washington, DC, USA, 2010:58-65.