流数据聚类方法

2022-03-02张宝杰陈斯羽

现代计算机 2022年23期

张宝杰，余涛，王玉，陈斯羽

（西安石油大学计算机学院，西安 710065）

0 引言

物联网（IoT）技术，智能手机和社交媒体服务的广泛使用产生了大量的高速数据流，比如，实时监控系统产生的数据，相机的图像序列（视频）数据，或社交媒体流的文本输入，等等［1］。在面对以上应用场景时，如何快速对这些数据流进行分析和处理成为首要任务。聚类通常被用于对数据进行快速探索性数据分析。然而传统的聚类方法在处理流数据时会面临两个问题：①提取有效信息效率低；②要占用大量设备内存。如何使用聚类方法从流数据中提取有用的信息成为研究热点。

流数据聚类方法解决了传统的聚类方法在处理流数据上出现的问题。常见流数据聚类的具体实现过程如下：

（1）面对流数据M={m1,m2,…,mn}，使用窗口模型对数据进行分割，获得K组数据块；

（2）对第一组数据块使用聚类方法进行聚类，获取聚类信息；

（3）提取当前的聚类信息；

（4）结合（3）中获取的聚类信息以及第i（1＜i＜K）块数据，重新进行聚类，获得聚类结果；

（5）重复（3）、（4）步骤，直到i=K，输出聚类结果。

本文首先介绍流数据聚类中的基本概念，其次对流数据聚类算法进行分类，依据分类分别介绍了当前存在的流数据聚类算法，在第三节主要介绍流数据聚类实验中常用的应用及衡量标准，最后对流数据聚类进行总结和展望。

1 基本概念

1.1 聚类

聚类是一种典型的无监督学习方式，能够将具有相似性的数据划分为一组。通常被用于进行快速探索性数据分析。假设有N个对象的集合M={m1,m2,…,mn}，那么将这N个对象依据某种特征划分为k∈{2,3,…,N-1}个子集，其中每个m由一个p维特征向量定义，xi∈Rp在X={x1,x2,…,xn}∈Rp集合中。这样的过程被称为聚类。

1.2 窗口模型

流数据在理论上是一组大量、连续没有边界的数据序列［2］。当前流数据聚类检测主要面临两个问题：①存储挑战。由于数据点不断到达，序列理论上是无穷无尽的，因此从一开始就将整个流存储在内存中是不可行的。②效率问题。在实际应用中需要立刻对当前的数据进行分析并得出聚类结果［3］。研究表明，在流数据中使用窗口模型将整个数据切割，只处理最新到达的数据对象比处理全部数据更有效，而且该方法对内存需求量少，能够加快分析效率。当前有四种主要的窗口模型（如图1所示），分别是阻尼窗口模型（damped window model）、地标窗口模型（landmark window model）、滑动窗口模型（sliding window model）和倾斜窗口模型（tilted window model）。

图1 常用流数据窗口模型

阻尼窗口模型：该模型为每一个对象分配权重，通过设置衰减函数或衰减因子，使最新到达的对象获得尽可能大的权重，随着时间变化，该权重会逐渐下降。地标窗口模型：该模型主要通过在流数据中设置聚类的起始点，从起始点开始进行聚类。滑动窗口模型：滑动窗口模型主要通过设置一个固定长度的窗口m，从t1时间开始，只有最近的m个数据对象被拿来进行聚类。倾斜窗口模型：该模型能够在整个窗口期保存主要的信息［4-6］。

2 方法概述

依据传统（批处理）聚类算法的分类对流数据聚类进行分类，主要可以分为五个类别：层次聚类、分区聚类、密度聚类、网格聚类和模型聚类［7］。依据流数据方法实现可主要分为三大类：数据汇总聚类［8-10］、在线（实时）聚类、时间序列聚类［11-12］。其分类结果如图2所示。在本文中，主要依据传统分类方法对当前提出的流数据方法进行介绍。

图2 数据流聚类算法的分类

2.1 基于层次的流数据聚类方法

流数据层次聚类方法核心和层次聚类方法类似，主要基于二叉树的数据结构。基于层次的流数据聚类方法的优点是不需要提前预估计数据中存在的簇，可以根据自己的需要直接切割从而获得聚类结果，同时基于层次聚类能够输出当前流数据块的树状结构图。然而基于层次的流数据聚类方法时间复杂度比较高，此外还容易受到异常值的影响。

ODAC方法是Rodrigues等［12］提出的时间流数据的层次聚类方法，该方法使用树结构来更新流数据中簇的变化。通过对聚类的质量进行测量，将同一簇对象之间的最大不相似度定义为簇的直径。但是由于层次聚类自身在添加或删除叶子节点时需要对树结构进行调整，所以会导致时间复杂度变高。Udommanetanakit等［13］在2007年提出E-Stream方法，该方法用一种新的聚类表示方法和距离函数来改进流聚类算法，它是基于进化的流聚类方法，支持出现、消失、自进化、合并和分裂等不同类型的聚类结构演化。对于一组数据M={m1,m2,…,mn}，最初时将每次输入的一个mi看作是一个对象，当第min个对象到达时，如果A={mi1,mi2,…}的密度足够大，那么A就是一个簇。因此，该方法根据相似度评分将新到达的对象分配给一个簇，否则可以将数据归类为孤立的数据。Meesuksabai等［14］在2011年提出HUE-Stream方法，该方法解决了E-Stream方法在异构数据上出现的不确定性问题，并且能够针对不同类型的聚类结构进行演化。

2.2 基于分区的流数据聚类方法

在批处理聚类中，常见的分区聚类方法典型代表就是K-means方法。假设有限数据集M={m1,m2,…,mn}中有K个簇，设置初始的聚类簇中心K={K1,K2,…,KK}，DiK是每个对象到Ki的距离，i={1,2,…,K}；据此将每个对象分配给具有min{DiK}的簇，找出该组数据划分为MK1={mi1,mi2,…,mib},…,MKK={mic,mic+1,…,mn}，更新簇中心。基于分区的流数据聚类方法大部分是在基于分区的批处理方法上面进行扩展，它的优点是易于实现，易于理解，但是基于分区的流数据聚类方法需要预估计当前数据对象中存在簇的个数，如果预估计的簇少于实际存在的簇的个数，这将会导致出现无效聚类。

基于分区的相关流数据聚类算法有SWClustering［15］，Streamkm++［16］，Adaptive Stream Kmeans［17］，FEAC-Stream［18］等。SWClustering方法通过使用滑动窗口和聚类特征指数直方图（exponential histogram of cluster feature,EHCF）来维护流数据中簇的特性，因此该方法能够获得最近窗口中簇的分布及其演化过程，能够根据选择的样本集合计算出聚类结果［19］。Streamkm++是K-means++［20］算法对数据流聚类的扩展，是K-means算法的扩展，该方法能够在流数据上取得很好的聚类结果。Puschmann等［17］提出Adaptive Stream K-means方法，该方法是一种基于在线分区的流数据聚类算法，Puschmann指出该方法克服了基于分区的流聚类方法需要预先确定K以及难适应输入数据中概念漂移的问题。该方法的一个局限性是需要对当前数据中存在的簇进行估计，预估计的簇数量会直接影响到聚类结果。de Andrade Silva等［18］提出基于kmeans算法的FEAC-Stream聚类方法，该方法通过使用进化方法来自动估计K值。FEACStream是完全在线的方法，使用Page-Hinkley（PH）［21］评价当前算法聚类结果的质量，通过Page-Hinkley（PH）评价方法能够协助FEACStream聚类方法自行调整到最优策略，能够直接维护最终的聚类结果。Clustream方法提出了在线-离线框架，使用倾斜窗口模型，在线通过微簇结构来获取并维护流数据的样本信息，在离线阶段，基于在线阶段总结的样本信息产生聚类结果［22］。Clustream方法能够应用于各种复杂的情况并产生较好的聚类结果。然而该方法并没有区分出过期数据与近期数据的差异性权重，因此在高维数据上聚类性能会变差。

2.3 基于密度的流数据聚类方法

基于密度的流数据聚类方法具有任意形状簇的噪声鲁棒性，它通过计算数据之间的密度，从密度低的区域进行切割，将密度高的区域划分为一个簇［23］。然而该方法在面对具有多种密度的簇的情况下，大部分基于密度的流数据聚类方法难以获得满意的聚类结果。

Cao等［10］提出DenStream算法，该方法采用了在线-离线原理。在线阶段主要通过使用一种“密集”簇（core-micro-cluster）的方法对当前流数据中的簇进行归纳，并维护和区分潜在的簇和异常点。在离线阶段通过利用在线阶段获得的结论进行聚类，从而获得聚类结果。MuDi-Stream［23］方法解决了当流数据中簇具有多密度情况时，基于密度的流数据聚类表现效果急剧下降的问题。使用基于在线-离线框架的流数据聚类方法，在线阶段通过采用基于网格的方法，获得以核心小集群的形式保存的多密度流数据的汇总样本，在离线阶段通过DBSCAN的扩展方法计算聚类结果。然而该方法没有解决历史数据样本与当前数据之间关系的问题。Chenaghlou等［3］提出了一种考虑观测时间接近性和空间接近性，以实时识别异常的算法（online clustering anomaly detection，OnCAD）。该方法不能直观展示当前数据中的簇结构，因此在乱序数据集上表现较差。Fahy等［24］提出了一种基于生物的在线聚类动态数据流的方法——蚁群流聚类（ACSC）算法，该方法极大提高了算法的聚类效率。Tareq等［25］提出了基于自适应切比切夫距离（CEC）的进化数据流聚类，该方法是一种基于密度的在线聚类算法，它解决了聚类质量受距离函数（distance）影响这一问题，当使用距离函数时，会导致聚类结果降低。DFPSclustering（the dynamic FPS-clustering algorithm）该算法引入基于密度的目标函数，采用适应度比例共享策略对聚类中心进行更有效的搜索，该方法能够应用于社交媒体分析、股票市场预测和网络入侵检测等领域，其缺点是计算成本略高［26］。

2.4 基于网格的流数据聚类

基于网格的流数据聚类方法基于网格聚类模型。首先使用网格对数据空间进行分割，将数据对象映射到网格单元［27］。获取网格单元之间的密度，从密度低的区域进行切割，获得一组密度大于周围网格单元的连接网格单元，这样获得的簇被称为网格簇。单元格的密度被定义为当前单元格中点的密度，在流数据中单元格能够保存流数据的历史信息，同时在流数据聚类中需要在线对单元格信息进行更新。然而在网格单元上进行聚类需要耗费大量的时间。

潘登等［28］提出一种能够并行处理数据和便于增量计算的智能聚类方法，该方法主要结合径向基函数（radial basis function，RBF）和网格划分，实现了流数据聚类。张东月等［29］依据在线-离线模式提出了一种基于网格耦合的流数据聚类方法。在线阶段主要实现对数据映射，以及对网格进行更新、添加和删除的操作。在离线阶段进行聚类操作获得流数据的聚类结果。

2.5 基于模型的流数据聚类方法

基于模型的流数据聚类方法主要是通过找到最适合输入数据的数据分布模型，从而利用该模型进行聚类来获得聚类结果，该方法具有噪声稳定性。其中SWEM方法就是一种基于模型的流数据聚类方法［30-31］。

此外，AutoCloud聚类方法是一种基于典型和偏心数据分析的在线数据流聚类进化方法［32］,它基于最近引入的典型性和偏心数据分析的概念，主要用于异常检测任务。evoStream［33］算法能够利用流中的空闲时间来增量地提高聚类结果。

3 评价指标及应用

3.1 评价指标

当前流数据聚类方法大多分为在线-离线方案，通过离线实现聚类并输出聚类结果。因此在大部分论文中，依旧采用和批处理聚类一样的评价指标。在批处理聚类方法上，其评价指标可以分为两类：内部评价指标和外部评价指标。内部指标是无监督的，主要是通过计算对象与簇中心的距离来衡量聚类结果的好坏。其中常用的内部指标有戴维森堡丁指数（Daviesbouldin index，DBI）、邓恩指数（Dunn validity index，DVI）、轮廓系数（silhouette coefficient）［34］。常用的外部指标有标准化互信息（normalized mutual information，NMI）、调整互信息（adjusted mutual information，AMI）、局部精度（partation accuracy，PA）等。

调整互信息的计算如下：

其中，E{M I(U,V)}为互信息M I(U,V)的期望，其计算方法如下：

其中k=(ai+bj-N)+为max(1,ai+bj-N)；ai和bj分别为列联表M的第i行和第j列和，具体为：

3.2 实际应用

表1举例了四种流数据聚类方法及其应用。

表1 流数据方法及应用

Peixoto等［35］提出一个应用于车载自组织网络（vehicular ad-hoc networks，VANETs）的流数据聚类框架，该框架定义了两种减少交通数据流的方法：其中之一为普通的交通拥塞检测方法——基线方法，并通过实验表明该方法能够有效降低通信成本，为VANETs的发展带来显著成果。textClust［36］实现了文本流的聚类算法，该方法通过使用两阶段聚类方法来识别和跟踪文本流中的主题。GMMSEQ［34］是一种能够用于管理附加在声发射信号上的连续时间戳的聚类算法。在聚类过程中利用时间戳，使人们能够获得对声发射数据流的信息。Hassan等［37］对进化聚类算法（ECA*）进行改进，称为iECA*。该方法能够用于COVID-19和医疗疾病数据集的实际应用。