基于ExCC算法的流数据挖掘研究

牛晨晨， 张 昪, 周 畅

(兰州财经大学信息工程学院， 甘肃兰州 730000)

基于ExCC算法的流数据挖掘研究

牛晨晨， 张 昪, 周 畅

(兰州财经大学信息工程学院， 甘肃兰州 730000)

随着现代科学技术的快速发展，出现了诸如无线通信网络的数据、传感器网络的数据、证券交易的数据等的新型数据，即流数据．流数据呈现的特点不同于传统的数据集，其所表现的是数据规模宏大、时序性、数据快速变化等．传统的聚类分析算法对于流数据挖掘已不再具有可行性，因此，本文就ExCC算法对于流数据挖掘的相关问题进行了深入研究．

流数据；聚类分析；ExCC；数据挖掘

1 流数据及其挖掘算法简介

1.1 流数据简介

流数据是一组顺序、 大量、 快速、 不断增加的数据序列， 一般情况下， 其可被看作是无限增加的动态数据集合[1]. Henzinger[2]第一次把流数据作为新型的研究对象提出来了. 参考文献[3-6]都对流数据的相关特征进行了详细的描述与深入的探讨.

综合已有文献的研究， 我们可以把流数据的特征概括为以下几点：

(1)流数据中的数据是海量的并且具有不断增加的特征[3]， 如果想将这些海量的数据全部储存起来， 那么存储这些数据所需要的空间就必须是无限的.

(2)流数据中数据的传递速度是很快的. 例如：通信收集的数据、 流量监控的数据、 证券交易的数据等， 这些数据的传递速度是很快的.

(3)流数据还具有时序的特征， 这就使得对流数据的访问是单次遍历的[4]. 也就是对数据元素的读取只能按照数据流入的时间顺序来依次进行， 而不能对那些顺序流入的数据进行随机访问.

(4)流数据一般是变化的、 不可再现的[5]. 也就是说流数据的模式并不是固定不变的， 而是随着时间的变化而不断变化着. 因为流数据是无限的， 所以不能存储所有数据， 只能存储相对重要的部分数据， 这就导致必须舍弃大部分的数据， 因此流数据通常是不可再现的.

(5)流数据还具有高维的特征[6]， 即流数据并不是由最初生成的数据聚集后才形成高维的， 而是自数据产生后就已经达到了高维的标准.

以上几点都是流数据所具备的基本特征， 人们往往根据流数据的这些基本特点， 有针对性地采取不同的数据挖掘方法来获取所需要的信息.

1.2 流数据挖掘算法简介

流数据挖掘就是在动态到达的数据上发现并提取那些有用信息的过程. 传统的数据挖掘算法通常是针对静态数据集的， 显然对于流数据已不再适用. 根据流数据自身所具有的特点， 我们可将其数据挖掘算法的特点归纳为：

(1)单次扫描. 由于流数据是无限持续到达的， 但是存储数据的容量是有限的， 这就使得我们无法把所收集到的源源不断的数据都存放在有限的内存中并进行多次的挖掘访问， 而只能相应地保存一些重要的数据. 所以流数据只能被用来分析处理一次， 而不能再次扫描过往的记录.

(2)时间复杂度低. 因为流算法是在线实时的算法， 这就要求算法能够快速地处理这些动态流数据， 从而确保数据的处理速度大于或等于数据的产生速度.

(3)数据处理后的结果极其相似. 由于内存的有限性只能存储数据的一些概要信息， 并且流数据是无法全部存储以及重复扫描的， 所以也就得不到精确的处理结果.

(4)算法本身的自适应性. 数据的流速与内容在不断地变化， 所以流数据挖掘算法能够针对不同的流数据特点做出相应的改变.

(5)能高效准确地处理例外点及噪音. 因为噪音或例外点可能会影响数据处理的结果， 所以一个具有较好鲁棒性的算法就必须具备处理这些问题的能力.

(6)在任意时间点都可以提供当前数据处理的结果. 其算法并不是间断性地来处理数据提供结果， 而是对任意时间点的数据都进行了分析处理， 而且能够提供任意时间点的处理结果.

(7)算法的处理结果具备通用性. 也就是说算法的数据结构不仅能支持算法当前的目标计算， 还能够支持其他计算.

2 聚类分析以及它在流数据挖掘中的应用

2.1 聚类分析

聚类分析(cluster analysis)简称聚类(clustering),其是把所收集到的数据元素划分成相应的类， 并组成相应的簇， 从而使得划分成的簇内之间的数据具有相似性， 而不同的簇之间具有相异性[3]. 聚类分析是数据挖掘中一种重要的分析方法， 也是一种重要的无监督学习方法. 其数学的形式化定义可以表达为：在某个数据空间S中， 数据集X是由不同的样本点所组成， 样本点Xi∈S,(i=1,2,......,m),其中xij表示样本点Xi在属性Aj(j=1,2,......,n)上的性质特征值. 假设样本集的样本总数是m， 那么数据集X就是一个m×n的矩阵. 通过定义准则函数可把数据集X划分成C个类别Ci(i=1,2,......,c),也有部分数据样本点没有划分到Ci中， 这部分数据样本点记为噪声Cs， 则所有的类别和噪声的并集便是整个数据集X， 而且类别相互之间没有交集， 即X=C1UC2U......UCn， 且Ci∩Cj=φ,(i≠j),这就是聚类的结果[7-9]. 聚类分析是数据挖掘中很重要的一部分， 它可以用来观测数据的分布状况以及每个簇的不同特征， 并能够对特定簇集合上的数据进行进一步的分析与研究.

2.2 流数据挖掘中的聚类分析

传统的数据集是静态的， 并且规模相对来说比较小， 这些数据集都储存在一个稳定的存储介质中， 而且大部分数据都是不变的， 因此一些传统的数据挖掘方法就能够很好地处理这些数据. 然而流数据却与传统静态数据是完全不同的， 它是一种流动的海量数据的集合， 这就会使传统的数据挖掘方法不能直接适用于这些流数据， 所以针对流数据的挖掘就需要采用最新的算法. 流数据聚类分析经过这么多年的发展， 已经取得了很大的进步， 例如：基于K-平均算法的Stream算法[10]. 这种算法的聚类是通过质心和权重表示得到的， 它比传统算法具备更好的性能， 并且产生的聚类结果的质量也更高； 基于BIRCH算法的CluStream算法[11]开创性地将聚类过程分为在线聚类和离线聚类， 并利用金字塔时间窗口技术来存储和处理不同时间粒度上的流数据， 提供给用户感兴趣的聚类结果； 基于DBSCAN算法的DenStream算法[12]可以发现任意形状的簇， 并着重指出了例外点的检测问题. 而这些都是解决流数据的经典的聚类分析算法. 本文所介绍的ExCC算法也是适用于流数据模型且满足其特点的高效聚类算法.

3 ExCC算法在流数据中的应用

ExCC算法是Bhatnagar等人提出的一种基于网格与密度的、 可以较好处理流数据的高效聚类算法. 该算法对簇聚类的完备性与排他性进行了深入的研究， 并在此研究的基础上提出了相完备性聚类的概念. ExCC算法分为了在线和离线两个部分， 在线部分算法的基本处理过程就是将数据元素的属性值映射到相应的网格中， 并根据每个属性到该属性所属域集的距离据此来划分网格的粒度， 离线部分则根据实际的情况形成最终的聚类簇[13]. ExCC算法的基本框架用下面的伪码来表示：

Input:All cells in grid (G);

Output:Clustering Scheme CS;

Prune G to remove non-recent cell.//剪去“旧”网格单元

Compute Ψ and store dense cells in a cell pool L//计算网格密度Ψ并将密集网格存入网格池L

Compute Ψ //算出当前的密度阈值

Let CS=NULL,K=0

While (L not empty) Do

Begin

K=K+1

CK=clustering(L,K)//然后从L中选取网格进行聚类

If([(ρK/ηK) > ω])//如果网格数量与数据点个数的比大于当前密度阈值， 更新聚类簇的描述

Compute desk

CS=CS U CIK

End

ExCC算法实际上是运用了一种全新的剪枝策略， 这种策略的核心思想是在给定的时间间隔内对簇的权值进行相应的检查， 并设置一个最低权限或规则， 将那些不满足要求的数据将被视为噪声或例外点， 并把其从所存储的队列中删除. ExCC算法常采用以下的数学公式来动态地计算密度阈值：

Ψ=[Ψ*(ln g + ln d)]/(2*ln g*ln d)

其中， Ψ是当前网格的密度阈值， g为平均网格粒度， d表示数据空间的维度.

之后将密集网格和最新收集到的数据落入的网格放入相同的“网格池”中， 在以后的每次聚类中都是从这个网格池中来选取对象. 除了网格的粒度影响聚类质量的高低之外， ExCC算法还会用多余的内部存储空间来创建“网格池”用以储存密集网格.

ExCC算法由于是基于密度与网格的高效的聚类算法， 能明显提高该算法的运行速度， 并使得空间复杂度大大下降. 因此ExCC算法能够极好的适应海量流数据的挖掘.

4 总结

随着科技的进步， 人们对流数据进行了更为深入的研究， 并由此提出了多种算法来处理. 本文所提到的ExCC算法就是其中一种能较好处理流数据的算法， 但对于这种算法的研究还有待深入探讨. 针对流数据的聚类分析仍就是一个充满挑战的领域， 但是可以预见的是， 未来一定会有更高效的算法来处理流数据， 从而可以更好地解决相关领域的问题.

[1] 胡彧， 闫巧梅． 基于滑动窗口的流数据聚类算法研究[J]． 计算机工程与设计， 2008， 29(21): 5621-5623．

[2] Henzinger M R, Raghavan P, Rajagopalan S. Computing on data streams. SRC Technical Note 1998-011.Digital systems research center: Palo Alto, California, 1998-95.

[3] 范明， 孟晓峰.数据挖掘：概念与技术[M].北京：机械工业出版社，2012:378-385.

[4] 孙玉芬，卢炎生. 流数据挖掘综述[J]. 计算机科学，2007, 34(1): 1-6,11.

[5] Babcock B.,Babu S.,Datar M.,Motwani R,Widom J. Models and issues in data stream systems[Z].In Proc.of the 2002 ACM Symp.on Principles of Database Systems(PODS’02),2002,1-16.

[6] Aggarwal C C,Han J,Yu P S. A framework for projected clustering of high dimensional data streams[Z].In Proc.of the 30thConf.on Very Large Data Bases(VLDB’04),2004,852-863.

[7] 任家东， 周玮玮， 何海涛.高维数据流的自适应子空间聚类算法[J].计算机科学与探索， 2010,4(9)：859-964.

[8] 颜晓龙， 沈鸿.一种适用于高维数据流的子空间聚类方法[J].计算机应用， 2007,27(7)：1680-1684.

[9] 周晓云， 孙志挥， 张柏礼， 杨宜东.高维数据子空间聚类发现及维护算法[J].计算机研究与发展， 2006,43(5)：834-840.

[10] Callaghan O L,Mishra N,Meyerson A,et al.Streaming-data algorithms for high-quality clustering [C]//Proc.Of ICDE Conf.of IEEE International Conference on Data Engineering,March 2002:685-694.

[11] Aggarwal C,Han J,Wwang J,et al.A framework for clusteering evolving data streams [C]//Proceedings of the 30thVLDB Conference,Berlin,Germany,2003.

[12] Udommanetanakit K,Rakthanmanon T,Waiyamai K. E-Stream:Evolution-Based Technique for Stream Clustering [M].Berlin :Springer-Verlag,2007:605-615.

[13] Bhatnagar V,Kaur S, Exclusive and Complete Clustering of Streams [M].Berlin :Springer-Verlag,2007:629-638.

[责任编辑 徐 刚]

Research on Stream Data Mining Based on ExCC Algorithm

NIU Chen-chen, Zhang Bian, Zhou Chang

(Department of information and engineering, Lanzhou University of Finance and Economics, Lanzhou 730000, China)

With the rapid development of modern network information technology and science technology, a kind of new data, such as wireless communication network, sensor network, financial stock transaction and so on daily application, has appeared. The characteristics of streaming data presentation are different from traditional data sets, which show the large-scale data, timing, rapid data changes. The traditional clustering algorithm is no longer feasible for streaming data mining, so this paper deeply studies the related problems of stream data mining in ExCC algorithm.

streaming data; cluster analysis; ExCC; data mining

2016-12-17

牛晨晨(1989—)， 男， 河南周口人，硕士研究生. 研究方向：数据挖掘.

TP311

A

1009-4970(2017)02-0055-04