朱颖雯，陈松灿

（1.南京航空航天大学计算机科学与技术学院，南京 211106；2.三江学院计算机科学与工程学院，南京 210012）

引 言

随着技术的发展，包括传感器在内的越来越多的设备正在成为互联设备，并不断地生成数据流［1-3］。例如：每天Google 都要处理超过35 亿的搜索；NASA 卫星产生约4 TB 的图片；沃尔玛超市每天产生超过2 000 万笔交易。数据流不事先存放在存储介质中，具有快速、时序和海量等特征。数据流的特性使得传统数据挖掘方法无法用于数据流［4］。挖掘数据流即从连续不间断的流数据中提取隐藏的知识/模式的过程，如图1 所示。数据流挖掘包括数据流分类、数据流聚类和数据流上的关联规则挖掘等［5-7］。其中，数据流聚类是将数据对象集合中的相似对象划分为一个或多个“簇”的过程［8-18］，划分后同一簇中元素彼此相似，不同簇中元素彼此相异。

图1 数据流挖掘过程Fig.1 Data stream mining process

不同于传统静态数据聚类问题，数据流聚类因数据本身的特性造成了诸多限制，影响了传统算法的直接使用。例如：森林中安放了数千个传感器，气象站从所有传感器连续不断、高速地接收有关温度、风速、方向、湿度和传感器位置等天气状况信息。由于数据流是无界且不断发展的，采用传统聚类算法进行批处理不可行。同时，它也无法全部存储在内存中，而是需要增量存储并对数据进行快速处理。此外，现实场景中，传感器暴露在各种不同的天气条件下，极有可能出现故障，如因电池电量不足、无网络连接或火灾引起的数据缺失或者数据异常。……