摘要：基于大数据时代的背景下，流数据的特点导致数据聚类挖掘迎来了新的，复杂的挑战。基于密度的流数据聚类算法已经成为聚类流数据的新颖且重要的研究方向。本文主要总结了基于密度的流数据聚类算法的优缺点及核心步骤，并将其划分为四类即基于核心微集群的、基于EHCF的、基于微簇的还有传统的密度聚类算法。讨论了他们在各行业的应用以及对流数据算法发展前景的展望。
关键词：流数据；密度；聚类算法；流数据聚类算法
作者简介：曹传贵1,2，辛辰辰1；1.西北民族大学数学与计算机科学学院，2.西北民族大学动态流数据计算与应用实验室
Abstract:in the context of the era of big data,the characteristics of data flow lead to new and complex challenges in data clustering mining.Density-based stream data clustering algorithm has become a valuable research direction for clustering data streams.This paper mainly summarizes the advantages and disadvantages and core steps of density-based streaming data clustering algorithm,and divides it into core micro cluster-based,EHCF based,micro cluster-based and traditional density clustering algorithm.Their applications in various industries and prospects for the development of streaming data algorithms are discussed.
Keywords:stream data density clustering algorithm stream data clustering algorithm
引言
随着云计算、物联网、大数据等信息技术的快速发展，在众多的实际应用领域如金融市场、传感器监测、网络监控中产生大量的流数据，如何从这些应用领域大量信息中挖掘出隐藏在其中的信息及规律并加以利用，目前已成为众多学者关注的热点话题。为了从大数据中提取有用的信息，常采用数据挖掘技术。如分类技术、聚类分析及关联规则挖掘等，其中聚类分析在数据挖掘中扮演着重要角色。聚类分析是按照一组数据样本的特征将其划分为若干类（簇），使得相同簇中的数据样本相似度尽可能大，不同簇中的数据样本相似度较小。聚类分析是一种广泛应用于机器学习、模式识别、数据挖掘及图像处理等领域的重要无监督学习技术，是进一步分析和处理数据的重要方式。其中，流数据作为大数据应运而生的一类数据，与传统静态数据集相比。流数据具有高速性，连续性，时序性和数据规模宏大等特点[1]。基于此，大量传统的基于静态数据的挖掘算法已不能适应流数据处理的需要。近年来，众多学者致力于流数据挖掘算法的研究，在流数据的聚类分析方面提出了一些有效且有影响力的算法如：DenStream[2]，OPTICS[3]，Multi-DBSCAN[4]等。其中基于密度的聚类算法较为突出，本文总结了高维数据下基于密度的流数据算法对其应对方法。
1.传统聚类算法
聚类[5]是一种无监督学习技术，通过聚类能够发现研究对象的自身特征规律，是一种重要的分析和处理数据的基础方法。基于传统的聚类算法按算法原理可分为层次方法、划分方法、基于密度的方法、基于网格的方法、基于模型的方法等。
2.基于密度的聚类算法
基于密度的聚类算法将簇看作是数据空间中被低密度区域分割开的高密度对象区域。密度聚类不仅可以发现任意形状的簇，而且可以有效过滤噪声样本。基于密度的聚类算法可将其细分为基于核心微集群的、基于EHCF的、基于微簇的以及传统密度聚类算法。
目前，具有代表性的基于密度的传统聚类算法主要有DBSCAN算法(Density-Based Spatial Clustering of Applications with Noise)[6]OPTICS算法(Ordering Points to Identify the Clustering Structure)[7]DENCLUE算法（DENsity-based CLUstEring）[8]。基于这些经典算法又扩展出来许多新的算法。
3.流数据聚类算法
3.1流数据及其特点
流数据是一个以一定速度连续到达的数据项序列x1...，x2...，xi...,xn...，这个数据项序列只能按下标i的递增顺序读取一次[9]，与传统数据相比，它具有高速性、连续性、时序性、数据规模宏大的特点。
流数据聚类算法可分为两个部分，即在线部分和离线部分[10]。在线部分负责实时处理新到达的数据，并周期性的存储统计结果。离线部分充分利用这些统计结果结合用户输入得到聚类结果。对于流数据聚类算法由于流数据的特性决定了它不可能全部保留存贮，会对处理过的数据进行删除只保留其概要。对数据的存贮精度与时间有关，越早的数据粒度越粗，反之越细。
3.1.1在线聚类
最初提出的方法[11]将流数据聚类问题看作是一个单通道聚类挑战，并采用一种通用的自适应策略来维护聚类。在流数据上维护一个单一的集群模型，并在新的数据对象从流到达时对其进行更新。但这种方法不允许在不同的时间间隔研究集群结构。
3.1.2在线离线集群
为了克服在线方法的局限性，Aggarwal等人[12]引入了在线离线聚类方法。两阶段的集群包括一个在线阶段，该阶段以在线方式维护流s数据上的统计信息，以及一个离线阶段，该离线阶段基于统计信息执行实际的集群。
3.1.3微簇（Micro-cluster）
CF最初是在BIRCH中引入了静态数据[13]。他们的适应数据流由Aggarwal等完成。他们用反映他们新进度的时间信息扩展摘要。新的摘要称为微簇，定义如下:
![22~AYZ)@`VZ9QV6LX62L]~E.png](/static/upload/image/20230804/1691125955698532.png)
新定义保留了基本CF组件和通过添加2个其他组件来扩展摘要，时间戳记CF1t的和与CF2t的平方和；这些增加可以计算时间聚类量度。微簇是由CLuStream[14]和FlockStream[15]使用。
3.1.4核心微集群（Core-micro-cluster）
Cao等人[16]微型集群扩展了基于密度的聚类定义。特别地，提出了3种微簇变化，核心微簇（Core-micro-cluster）、潜在核心微簇（potential core-micro-cluster）和离群微簇（outlier microcluster）。
时间t处的核心微集群，用于一组数据对象
被定义为三个：
CMC=(W,C,R)
其中，W表示该核心微簇（CMC）的重量，R是半径，C是微团簇的中心。
3.1.5 EHCF(Exponential Histogram of Cluster Feature)
Ntoutsi等人[17]提出一种新的数据结构，称为聚类特征指数直方图（EHCF），它是用于处理聚类的指数直方图的组合。用时间聚类特征（TCF）表示聚类分布变化的演化，以记录每个聚类的演化过程并捕捉最近记录的分布。
3.2基于核心微集群的密度流数据聚类算法
图1基于密度算法的分类框架图
如图1所示基于密度的聚类算法可以分为基于核心微集群的，基于EHCF的，基于微簇的。其中核心微集群又可分为基于多密度的，基于Denstream改进的，基于高维数据的，基于网格密度的。
C-Denstream[18]是一种包含域信息的半监督方法，输入约束的选择对输出聚类模型的质量有很大影响[19]，这是首次在流数据的集群中引入包含域知识的一种方法，它是用来开发基于密度的流数据聚类算法领域的专家知识。它是一种基于DenStream扩展的流数据聚类算法，允许在满足流数据算法要求的同时包含域信息。为此，扩展了流数据的实例级约束的概念，微簇和微约束的权重将使用其衰减函数进行更新，从静态数据扩展到流数据。重点研究了基于密度的流数据聚类和演化过程。基于这样一个事实，约束中涉及的元素通常代表其局部邻域[20]。
Li-xiong[21]提出了一种DenStream算法的变体rDenStream，它扩展了DenStream的两阶段框架，增加了一个额外的阶段称为“回溯”，以提高聚类精度。IS-DBSCAN[22]是一种在减少参数数量和聚类多密度数据能力方面改进DBSCAN算法的方法。该方法提出了一种新的空间排序概念，即基于密度度量对空间中的数据点进行排序。
DBSCAN-DLP[23]（基于密度水平的多密度DBSCAN划分）确定为了自动发现具有使用密度级别划分的各种密度。它是一种二值聚类算法，具有较高的计算时间，适用于流数据。
在基于密度的算法中解决高维数据方面的算法很少，尤其是解决高维流数据的算法少之又少。该算法总结了组合在一起的数据点的维度，并在线维护更新这些数据点。
Amineh Amini等人在2013年提出了一种多密度聚类算法的流数据称为MuDi-Stream[24]。为解决边界数据丢弃问题，提出了一种基于网格和密度的聚类框架DCQ-Stream[25]。在此聚类过程中还提出了DCQ-means算法，提取网格边界上的数据点。
3.3基于EHCF的密度流数据聚类算法
SDstream[26]一种基于密度的滑动窗口流数据聚类方法。它采用clustream集群框架。它们以簇特征指数柱状图（EHCF）的形式存储在主存储器中，由EHCFS维护。
3.4基于微簇的密度流数据聚类算法
EDDS是基于增强密度的流数据算法[27]是一种新的增量算法，称为用于聚类流数据的基于增强密度的方法(enhanced densitybased Method for Clustering data Streams，EDDS)[28]，它的开发是为了克服现有解决方案的局限性。聚类算法在时间复杂度上有一定的提高。
Hdenstream算法[29]是一种基于密度中微簇的流数据聚类算法，有密度聚类算法的特点决定了它能够聚类任意形状并处理异常值。Hdenstream算法基于Denstream算法。在HDenstream中，重新定义了p-微团簇、o-微团簇、样本到样本的距离、样本到微团簇的距离以及微团到微团簇的距离。优点是发现许多基于的密度的聚类算法也有基于网格聚类算法的特点，以及基于核心微簇集的也存在EHCF的特性。
4基于密度的流数据聚类算法的应用
在社会的所有领域中信息和通信系统的快速增长和复杂性已经导致了在线和实时的应用程序，如气象监测、舆情监测、电子商务交易等相关应用的大量存在。随着时间的推移，不断高速生成大量不断变化的数据。流数据随着云计算、大数据的发展，数据总是源源不断的产生。实时跟踪任何类型的交易，如客户点击数据、患者健康数据、TCP/IP流量、GPS数据等，以支持实时决策。在医学上使用基因信息，图像病灶信息发现疾病。挖掘流数据已成为数据挖掘领域的一个热门话题。高维流数据的聚类是许多应用领域的重要问题。
5基于密度的流数据聚类算法的挑战与展望展望
大数据时代的到来给数据聚类带来更大的挑战。一方面，数据正以前所未有过的速度爆炸性增长；另一方面，算法复杂度高，带来了空间和时间上的挑战。数据类型也呈现前所未有的复杂性，多模是其中的一个特征。高维数据一直是聚类研究的一个热点问题在研究中算法需要进一步改进优化，尤其是高维子空间聚类算法有待发展。多密度聚类算法已经小有成效但还需要不断改进。基于密度的算法对噪声的处理需要更加合理。对不同的数据聚类结果会有所偏差。这都是我们现在一些聚类所存在的问题。流数据分类是一个具有挑战性的问题，因为它有两个重要特性：无限长和进化性。未来流数据聚类算法应该能处理各种数据，各种高维数据，多密度数据，噪声处理更加完善，时间复杂度更低。在极其复杂高维、多模数据的条件下，特征学习是关键。面向聚类的多层特征学习机制仍然需要大量的研究。
参考文献：
[1]Han J,Kamber M,Pei J.Data Mining:Concepts and Techniques(3rd edition)[M].Burlington Morgan Kaufmann,2011.
[2]曹锋.数据流聚类分析算法[D].复旦大学,2006.06.
[3]Ankerst M,Breuning M M,Kriegel H P,et al.OPTICS:ordering points to identify the clustering structure[C]//ACM SIGMOD International Conference on Management of Data(SIGMOD),Philadelphia,1999:49-60.
[4]Huang T Q,Yu Y Q,Li K,et al.Reckon the Parameter of DBSCAN for Multi-density Data Sets with Constraints[C]//International Conference on Artificial Intelligence&Computational Intelligence.IEEE Computer Society,2009.
[5]Zhuang Y.The PU-Tree:A Partition-Based Uncertain High-Dimensional Indexing Algorithm[C]//International Conference on Network&System Security.2010.
[6]Ester M,Kriegel H P,Xu X.A density-based algorithm for discovering clusters a density-based algorithm for discovering clusters in large spatial databases with noise[C]//International Conference on Knowledge Discovery&Data Mining.1996.
[7]Ankerst M,Breuning M M,Kriegel H P,et al.OPTICS:ordering points to identify the clustering structure[C]//ACM SIGMOD International Conference on Management of Data(SIGMOD),Philadelphia,1999:49-60.
[8]Hinneburg A,Keim D A.An efficient approach to clustering in large multimedia databases with noise[C]//International Conference on Knowledge Discovery&Data Mining.1998.
[9]Henzinger M R,Raghavan P,Rajagopalan S.Computing on data streams[A].SRC Technical Note[C]//1998-011:125-126.Digital systems research center:Palo AIto,California,1998.
[10]AGGARWAL C C,HAN Jiawei,WANG Jianyong,et al.A framework for clustering evolving data streams［C］∥Proceedings of the 29th VLDB Conference.2003:81-92.
[11]O'Callaghan L,Mishra N,Meyerson A,et al.Streamingdata algorithms for high-quality clustering[C]//International Conference on Data Engineering.IEEE,2002.
[12]Charu C,Aggarwal.A survey of stream clustering algorithms,i n Data Clustering:Algorithms and Applications,C.Aggarwal and C.Reddy,Eds.,CRC Press,Siena,Italy,2013,361–366.
[13]ESTER M,KRIEGEL H P,SANDER J,et al.A density-based algorithm for discovering clusters in large spatial database with noise[C]//KDD-96:Proceedings of the 2nd International Conference on Knowledge Discovering and Data Mining.Portland,Oregon:[s.n.],1996:226–231.
[14]Knill E,Laflamme R,Milburn G J.A scheme for efficient quantum computation with linear optics[J].Nature,2001,409(6816):46-52.
[15]Hahsler M,Bolaños M.Clustering Data Streams Based on Shared Density between Micro-Clusters[J].IEEE Transactions on Knowledge&Data Engineering,2016,28(6):1449-1461.
[16]Cao,F.,Ester,M.,Qian,W.,Zhou,A.:Density-based clustering over an evolving data stream with noise.In:SIAM 2006:SIAM Int.Conf.on Data Mining(2006)
[17]I.Ntoutsi,A.Zimek,T.Palpanas,P.Kröger,and H.-P.Kriegel,Density-based projected clustering over high dimensional data streams,Proc.12th SIAM Int.Conf.Data Mining,Anaheim,CA,USA,2012.
[18]Ruiz C,Menasalvas E,Spiliopoulou M.C-DenStream:Using Domain Knowledge on a Data Stream[C]//International Conference on Discovery Science.2009.
[19]Davidson I,Wagstaff K,Basu S.Measuring constraintset utility for partitional clustering algorithms[C]//European Conference on Principle&Practice of Knowledge Discovery in Databases.Springer-Verlag,2006.
[20]Klein D,Kamvar S D,Manning C.From instance-level constraints to spacelevel constraints:making the most of prior knowledge in data clustering.In:ICML 2002:Proc.of the 19th Int.Conf.on Machine Learning,pp.307–314(2002).
[21]Li-Xiong L,Hai H,Yun-Fei G,et al.rDenStream,A Clustering Algorithm over an Evolving Data Stream[C]//International Conference on Information Engineering&Computer Science.IEEE,2009.
[22]Cassisi C,Ferro A,Giugno R,et al.Enhancing densitybased clustering:Parameter reduction and outlier detection[J].Information Systems,2013,38(3):317-330.
[23]Xiaoyun C,Ping W,Yufang M,et al.GMDBSCAN:MultiDensity DBSCAN Cluster Based on Grid[C]//IEEE International Conference on E-business Engineering.IEEE,2008.
[24]Amini A,Saboohi H,Wah T Y.A Multi Density-Based Clustering Algorithm for Data Stream with Noise[C]//IEEE International Conference on Data Mining Workshops.IEEE,2014.
[25]Amini A,Wah T Y.A density-grid based clustering algorithm for evolving data streams over sliding window,Int.Conf.Data Mining Comput.Eng.,Las Vegas,Nevada,USA,2012.
[26]Ren J,Ma R.Density-Based Data Streams Clustering over Sliding Windows[C]//FSKD 2009,Sixth International Conference on Fuzzy Systems and Knowledge Discovery,Tianjin,China,14-16 August 2009,6 Volumes.IEEE Press,2009.
[27]Alazeez A,Jassim S,Du H.EDDS:An Enhanced DensityBased Method for Cluster ing Data Streams[C]//International Conference on Parallel Processing Workshops.IEEE,2017:103-112.
[28]Alazeez A A A,Jassim S,Du H.EDDS:An Enhanced Density-Based Method for Clustering Data Streams[C]//International Conference on Parallel Processing Workshops.2017.
[29]Lin J,Lin H.A Density-Based Clustering over Evolving Heterogeneous Data Stream[C]//Isecs International Colloquium on Computing,Communication,Control,&Management.IEEE,2009.