数据流挖掘中的聚类技术

程军锋



数据流挖掘中的聚类技术

程军锋

(陇南师范高等专科学校 物理与信息技术系，甘肃 陇南 742500)

在动态数据流挖掘过程中，对数据流进行聚类，把未知的数据流划分或者生成到一个簇中．发现隐含的知识、价值和模式，是一种非常有效的数据流挖掘技术．分析和研究了数据流挖掘的聚类算法，并对数据流聚类技术发展进行了展望，提出了数据流挖掘的研究方向．

数据流；挖掘；聚类；算法

随着监控设备、网络点击和交易等网络应用，数据流挖掘已经成为一个研究的热点．数据流是指随时间源源不断到达的数据，通常有数据量大、连续达到等特点．对于这些海量的数据，通过数据挖掘的聚类技术找出隐藏的类和模式，已经被应用到商业和金融等领域．

聚类是一种非监督学习的数据挖掘技术，聚类是一个把数据对象划分成多个组或簇的过程，使得簇内的对象具有很高的相似性，但与其他簇中对象尽可能相异，也就是说最大化类内部的相似性，最小化类之间的相似性[1]．在数据流的挖掘中聚类分析技术在许多环境下非常有用．传统的聚类算法通常通过对数据进行反复多次扫描，以发现数据流中隐含的类，但由于数据流数据随时间不断到达，数据量大，不会被存储，不能进行多次扫描．因此，使用传统的数据挖掘聚类算法在数据流挖掘中并不适合．

对于数据流的挖掘聚类，通常要采用全新的数据结构和技术．在数据流的聚类过程中，已经有许多比较著名的算法，这些算法有的是对传统的聚类算法进行得改进，使得它们更适合数据流的挖掘，还有一些是根据数据流的特点设计出来的全新算法，这些算法在数据流的处理和分析中都非常有用，可以产生用户感兴趣的结果．

1 主要的数据流聚类算法

1.1 一趟数据流聚类算法

一趟数据流聚类算法基于最小距离，将新到达的数据和原有的数据进行求熵，看这个数据和原有数据之间的相似度，如果相似度不大于某一个指定的阈值，则认为这个数据和某个已有的簇比较相似，就把该数据归为一个已有的最相似的簇中去．如果当前数据和原有数据的相似度都比较小，则认为该数据和已有的簇都不相似，该数据将作为一个新的簇并进行构建．通常数据间的相似度可通过簇心和该数据求它们的距离，比较著名的有欧几里德距离和曼哈顿距离等．其中最简单一趟聚类算法是基于k-means算法，k-means算法是通过计算一个数据对象与簇的质心距离，来确定它们时间的相似度，把该对象赋予相似度最大的簇．一趟数据流聚类算法实现简单，算法的时间复杂度和问题规模成线性变化，在处理高速变化的数据流时效率不是很高，而且由于采用距离来衡量数据之间的相似度，因此对球形数据比较敏感．基于高维的一趟数据聚类Squeezer算法也可以用于数据流的聚类，而ID-Squeezer[2]是一种改进的应用于数据流文本聚类方面的算法．

1.2 STREAM算法

STREAM算法[3]是基于中位数的数据流聚类算法，它是一种单遍扫描，接近常数因子的近似聚类算法，是以中位数问题开发的．中位数问题是把个数据点聚类成个簇或组，使得点与它的簇的中心点之间误差平方和(SSQ)最小．STREAM在工作时把处理的个桶中的数据流，由于每个桶较小，都可以放在内存．对于每个桶，STREAM把每个桶的点分成簇．然后，仅通过保留个中心信息来汇总桶的信息．一旦收集到足够的中心，加权中心将再次聚类，以产生另外()个簇中心集合．如此重复，以便在每个层最多保留个点．这种方法导致单次扫描，时间复杂度为()，空间复杂度为()、数据流的中位数常量因子近似算法．

STREAM算法源于中位数聚类，使用有限时间和空间可得到不错的聚类效果．然而它没有考虑数据的演变和时间粒度的变化．聚类可能受控于旧的、过期的数据流，不能反映数据流的动态性，而在实际应用中，数据流应该是随着时间而变化的．

1.3 CluStream算法

CluStream算法[4]由Aggarwal于2003年提出的一个解决数据流聚类问题的框架，CluStream是一种基于用户指定的，联机聚类查询的演变数据流聚类算法．它将聚类的过程分成联机和脱机2部分．联机部分使用微簇计算和存储数据流的汇总统计信息，并进行增量联机计算和维护微簇．在CluStream算法中，微簇拥聚类特征表示，它扩展了BIECH聚类特征树的聚类特征概念．通常微簇是一个由(2d+3)的元组组成的，用(,,,,)，来表示微簇中包含的数据点个数，表示为微簇中数据点的平均值，表示微簇中数据点的平方和，若数据维度为，则与均为维向量，表示各个数据点时间标签的平均值，表示各个数据点时间标签的平方和．脱机部分进行宏聚类，并且利用存储的基于倾斜时间框架模型的汇总统计信息来回答用户的各种应答．

联机微簇分成2个阶段．1) 收集统计：维护由内存大小决定的个微簇M1，M2，M3，…，Mn；2) 更新微簇：把每个数据点加到一个已有的簇和一个新的簇中去．为了判断是否需要定义一个新簇，为每个簇定义了一个最大边界，如果新点落在这个边界内，将它加到簇中；否则，它将成为新簇的第一个数据点建立簇．聚类特征有可加性，这个特征在流聚类中非常有用，在聚类过程中通过可加就可以把一些微簇进行合并，尽量使得在内存中有少量的微簇．当数据点添加到已有簇中时，由于簇的可加性，它就被吸收了．当某个数据点添加为一个新簇时，依赖于特定的标准，删除最近最少使用的簇或合并2个已有的簇，以便为新的簇提供内存空间．

脱机部分可以执行用户的宏聚类或演绎演变分析．宏聚类允许用户探索不同的时间范围内的流聚类，演绎分析考虑新增的数据和现有的数据之间的演变性质，比如是否有原来的簇出现位置和信息的漂移等．

CluStream算法可以产生高质量的簇，特别当数据剧烈变化时，它为用户提供了丰富的功能，因为它存储了关于簇演变的基本历史信息，倾斜时间框架和微聚类结构为真实数据提供更好的精确性和效率．它在流大小、维度和簇方面保持了可伸缩性．

针对CluStream的两点不足，Aggarwal等在次年提出了HPStream算法框架．HpStream算法是CluStream算法的一个改进，主要使用投影聚类处理高维数据，并使用衰减结构来保存历史数据，实现了数据的集成，使得它适合处理高维数据．但它没有考虑数据的衰减性问题，不能体现近期数据的重要性，在被应用于处理高维数据流时效率一般．

1.4 其他数据流聚类算法

E-stream算法通过定义5种不同演化类型来表示数据流的演化行为，能够反映数据流的变化特性，比较适合数据流挖掘．Den-stream算法是一种基于密度的数据流聚类算法，改进了STREAM、CluStream等算法基于距离的度量，对球状数据流比较敏感，可以发现任意形状的数据流．D-stream是一种基于密度和网格的算法，也是用于解决任意形状的数据流聚类，也是分成2部分，联机部分接收数据并把它们映射到网格空间的对应网格单元中，脱机部分根据密度，在网格空间中进行聚类．而CFR算法是一个基于回归分析的数据流聚类的方法，通过相关评价函数来实现聚类，采用Mahalanobis距离度量簇之间的相似度．

2 数据流聚类挖掘算法研究展望

2.1 数据流聚类算法的改进和提高

对于海量的数据流进行聚类，应根据其动态变化特点对现有数据流聚类算法进行改进，并设计出新的数据流聚类算法，提高对数据流聚类的处理效率，使得它们具有较强的扩展性，能够完成数据流聚类的各种任务．同时，把其他的新技术和一些其他领域的算法应用到数据流聚类当中来，改进挖掘的质量，也是一个重要的研究方向．有文献[5]提出一种基于免疫原理的数据流聚类算法(AIN-STREAM)，该算法能够动态适应数据流的变化，并能有效抑制噪声．还有文献[6]提出了一种基于关联函数的数据流聚类算法，通过建立解决问题所需要的关联函数，计算关联函数的值，通过此值的大小来判断数据点属于某个簇的程度．

2.2 数据流聚类算法处理能力的研究

随着网络接入设备的增多、应用范围的扩大．当前数据流类型越来越复杂，这些数据流来自于不同的数据源，数据丰富，而且这些数据又是异构的，这就对数据流聚类挖掘算法提出了新的要求，要求数据流聚类算法必须要有一定的扩展性和适应性，能够对复杂的数据进行聚类，并产生良好的结果．有文献[7]针对多条数据流的聚类算法质量和效率的矛盾，提出了基于相关系数的多条数据流的聚类算法，实现固定长度的在线动态聚类．

2.3 数据流聚类算法的应用研究

数据流应用系统的大量应用，对数据流聚类算法的应用提供了广阔的空间，聚类算法对于动态变化，不可预知类的分类有着一定的优势，如何把聚类算法应用到实际当中去，也是一个数据流聚类研究的重要方面．如在网络的入侵检测系统、电信通话数据流、金融交易数据流和超市购物中等．而且在不同的应用场合，对数据流聚类算法有不同的要求，但总有一种聚类算法能够体现数据流聚类算法的应用价值，满足实际的需要．有文献[8]研究了数据流聚类在入侵检测系统的应用，提出DC-stream算法，采用在线离线两阶段聚类，通过一套缓冲式异常点处理机制，在保证数据流聚类效率和精度的同时，能够过滤噪音数据．

3 结束语

随着云计算、物联网技术的发展，大数据时代即将来临．如何在这些由监控设备、互联设备等传来的持续数据流中发现有价值的知识和模式，必将是一项严峻的挑战．同时，这也为数据流聚类处理技术发展提供了良好的机遇．

[1] 范明,孟小峰.数据挖掘概念与技术[M].2版.北京:机械工业出版社.2007:251-305.

[2] 尤薇佳,刘鲁,刘丹,等.基于Squeezer算法的文本数据流聚类[J].控制与决策,2012(5):542-546.

[3] O’CALLAGHAN L, MISHRA N, MEYERSON A, et al. Streaming-data algorithms for high-quality clustering[C]//IEEE International Conference on Data Engineering. San Jose:IEEE Computer Society,2002:685-694.

[4] AGGARWAL C C, HAN Jiawei, WANG Jianyong, et al. A framework for clustering evolving data streams[C]//29th International Conference on Very Large Data Bases. Berlin: Morgan Kaufmann Publishers,2003:81-92.

[5] 王述云,张成洪,郝秀兰,等.基于免疫原理的数据流聚类算法[J].模式识别与人工智能,2009(2):246-254.

[6] 潘丽娜,王治和,党辉.基于关联函数的数据流聚类算法[J].计算机应用,2013(1):202-206.

[7] 陈崚,邹凌君,屠莉.多数据流的实时聚类算法[J].计算机应用,2007(8):1976-1979.

[8] 黄红艳,安素芳.数据流聚类算法在入侵检测中的应用[J].计算机工程与应用,2012(20):112-116.

The Clustering Technology in Data Stream Mining

CHENG Jun-feng

(Department of Physics and Information Technology, Longnan Teachers College, Longnan, Gansu 742500, China)

In the process of dynamic data stream mining, the data stream is divided and the unknown data stream is classified into a cluster. The implicit knowledge, values and mode are found. It is a kind of very effective data stream mining technology. It has analyzed andstudied the clustering algorithm of data stream mining, and prospected the development of clustering technology in data stream and put forward the direction of data stream mining.

data stream; mining; cluster; algorithm

(责任编校：李建明 英文校对：李玉玲)

10.3969/j.issn.1673-2065.2015.01.005

TP311

A

1673-2065(2015)01-0016-03

2014-09-25

程军锋(1980-)，男，甘肃礼县人，陇南师范高等专科学校物理与信息技术系讲师．