时间序列挖掘聚类

时间序列挖掘●聚类山西财经大学信息管理学院常新功第六章目录聚类的概念聚类算法的评价标准时间序列聚类概述k-mediods时间序列聚类基于LB_Hust距离的时间序列聚类基于SAX表示的聚类聚类的概念聚类（Clustering）是数据挖掘领域中的一个重要分支。所谓聚类，是指将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过程。聚类是依据事物的某些属性将其聚集成类，使类间相似性尽量小，类内相似性尽量大。，的深圳举办的新一代信息技术产业发展高峰论坛上，中国工程院院士李德毅在发言中指出，尽管目前对于大数据的认知存在挑战，但聚类将会成为大数据认知的突破口。通过大数据聚类即时发现价值，要充分认识大数据中的不确定性和价值的隐蔽性。聚类算法的评价标准1)可伸缩性：可伸缩性考察聚类算法对于目标对象集合的规模以及目标集合潜在的模式数量的适应性。2)处理不同类型属性的能力：除了通常处理的数值型数据，应用当中可能要求聚类其它类型的数据，如：二元类型，分类/标称类型，序数型，时间序列、图数据或者不同数据类型的混合。3)发现任意形状的聚类：许多聚类算法基于欧几里德距离或者曼哈顿距离度量来决定聚类。基于这种距离度量的算法趋向于发现具有相近尺度和密度的球状簇。但是一个簇可能是任意形状的，提出能发现任意形状簇的算法是很重要的。4)交互可视化：高维数据和复杂对象常常使可视化变得困难，而交互性则使算法与人结合有利于提高聚类的质量。聚类算法的评价标准5)最小化用于决定输入参数的领域知识和数据记录敏感性：一方面要求降低算法对输入参数的敏感程度，另一方面要求输入记录顺序对算法的结果影响小。要求用户输入参数不仅会加重用户的负担，也使得聚类的质量难以控制。6)处理噪声数据的能力：绝大多数现实世界中的数据库都包含了孤立点，空缺，未知或者错误的数据。一些聚类算法对于这样的数据敏感，导致聚类质量不高。7)高维性：许多聚类算法只擅长处理低维数据。在高维空间中聚类数据对象是一个挑战，特别是在数据有可能非常稀疏和偏斜时。8)可解释性和可用性：知识发现过程中，聚类结果总是需要表现为一定的知识，这就要求聚类结果可解释，易理解。时间序列聚类概述时间序列聚类是时间序列数据挖掘的一个非常基础且非常活跃的研究方向，被广泛应用于包括模式识别、数据分析、图像处理、市场分析等各个领域：零售数据的季节模式聚类、国家能源消耗聚类分析、心电图ECG信号聚类分析、股票序列的模式发现以及个人收入数据的聚类等等(ValkandPinheiro,2012,Rodriguesetal.,2008,CostaSantosetal.,2006,Berkhin,2006,WarrenLiao，2005,BagnallandJanacek,2005)。国内外许多研究者提出了很多时间序列聚类方法，这些方法大致可以分为三种：基于原始序列、基于特征数据和基于模型参数(WarrenLiao,2005)。基于原始序列数据的时间序列聚类直接运行在原始时间序列上的聚类称为基于原始数据的聚类(Zhangetal.,2011,Rodriguesetal.,2008,WarrenLiao,2005)。但在实践中，由于时间序列的高维特点，会导致大部分的聚类方法失效，具体表现为：(1)时间序列被看成高维空间中的一个点，所以数据分布会呈现稀疏性，从而导致欧氏距离不能正确测度对象间的相似程度(Wangetal.,2005,Domeniconietal.,2004)；(2)多数算法的性能受参数设置的影响，在缺乏背景知识时，用户可以根据反馈的算法结果精调参数，但高维数据造成聚类结果无法可视化，使得用户很难判断聚类结果的质量，所以很难合理设置参数（Jain,2010,Chen,2007,Linetal.,2004，DingandHe,2004)。基于特征数据的时间序列聚类基于特征的表示方法是把原始时间序列转换到一个低维的特征空间，然后用传统的聚类方法对特征向量进行聚类(Yangetal.,2009,Xiaozheetal.,2007,Keoghetal.,2007,Chen,2007,Zhangetal.,2006,Wangetal.,2006，CostaSantosetal.,2006，Wangetal.,2005，BagnallandJanacek,2005，Domeniconietal.,2004)。由于基于特征的聚类方法中提取的特征来自序列本身，且具有特定的含义，所以该聚类方法不仅实现对序列的降维，又使得聚类结果具有可解释性。这里，常用的传统的聚类算法有如下几种：划分聚类、层次聚类和密度聚类等等(Jain,2010，ChawlaandGionis,2013,Rodriguesetal.,2008，Labini,2008,Schikuta,1996,Kriegeletal.,2011)。基于模型的时间序列聚类基于模型的聚类的基本思想是把原始时间序列转换成模型的几个参数，比如AR模型或HMM模型等，然后用模型参数进行聚类(JieandQiang,2005，CamastraandVerri,2005,XiongandYeung,2004,Panuccioetal.,2002)。这种方法的不足之处在于需要对数据的分布进行预先假设，此外，对参数的聚类结果无法进行解释，使得聚类缺乏可理解性。小结现有时间序列聚类方法大致可分成：基于原始序列、基于特征值和基于模型参数三种。基于原始序列的聚类方法由于“维灾难”很难产生较好的聚类效果，而基于模型参数的方法由于需要对数据做预先假设也使得应用受到限制，基于特征值的聚类方法是最有前景的时间序列聚类算法。静态时间序列列聚类k-medoids时间序列聚类类基于LB_Hust距离的时间序序列数据聚类类基于SAX表示的聚类k-mediods时间序列聚类类1、k-中心点聚类基基本原理：k-均值的缺点：：对离群点敏敏感k-中心点：挑选选实际对象来来代表簇，每每个簇使用一一个代表对象象。实现：围绕中中心点划分（（PartitioningAroundMedoids,PAM)算法算法:k-中心点。PAM输入入：：k：结结果果簇簇的的个个数数D：包包含含n个对对象象的的数数据据集集合合输出出：：k个簇簇的的集集合合k-mediods时间间序序列列聚聚类类方法法：：（1）从从D中随随机机选选择择k个对对象象作作为为初初始始的的代代表表对对象象或或种种子子（2）repeat（3）将将每每个个剩剩余余的的对对象象分分配配到到最最近近的的代代表表对对象象所所代代表表的的簇簇（4）随随机机地地选选择择一一个个非非代代表表对对象象Orandom（5）计计算算用用Orandom代替替代代表表对对象象Oj的总总代代价价S（代代价价函函数数就就是是计计算算绝绝对对误误差差值值的的差差））（6）ifS<0,thenOrandom替换换Oj，形形成成新新的的k个代代表表对对象象的的集集合合（7）until不发发生生变变化化特点点：：在小小型型数数据据集集上上运运行行良良好好，，不不适适合合大大数数据据集集，，算算法法复复杂杂度度太太高高。为为了了处处理理大大数数据据集集，，可可以以使使用用CLARA:大型型应应用用聚聚类类，，基基于于抽抽样样的的方方法法，，使使用用数数据据集集的的一一个个随随机机样样本本，，然然后后使使用用PAM方法法由由样样本本计计算算最最佳佳中中心心点点。。（（可可能能在在随随机机抽抽样样时时错错过过最最佳佳中中心心点点而而永永远远找找不不到到最最佳佳聚聚类类））k-mediods时间间序序列列聚聚类类2、基基于于k中心心点点方方法法的的时时间间序序列列聚聚类类见kmedoidtsclustering.cpp基于于LB_Hust距离离的的时时间间序序列列聚聚类类层次次聚聚类类方方法法对对给给定定数数据据对对象象集集合合进进行行层层次次分分解解。。根根据据层层次次的的分分解解如如何何形形成成，，层层次次的的方方法法可可以以分分为为凝凝聚聚的的（（agglomerativeormerging）和和分分裂裂的的（（divisiveorsplitting）两两种种类类型型。。凝聚聚的的方方法法，，也也称称为为自自底底向向上上的的方方法法，，初初始始化化将将每每个个对对象象作作为为单单独独的的一一个个簇簇，，然然后后相相继继地地合合并并相相近近的的对对象象或或簇簇，，直直到到所所有有的的簇簇合合并并为为一一个个，，或或者者达达到到一一个个终终止止条条件件。。分裂裂的的方方法法，，也也成成为为自自顶顶向向下下的的方方法法，，初初始始化化将将所所有有的的对对象象置置于于一一个个簇簇中中。。在在迭迭代代的的每每一一步步中中，，一一个个簇簇被被分分裂裂为为更更小小的的簇簇，，直直到到最最终终每每个个对对象象在在单单独独的的一一个个簇簇中中，，或或者者达达到到一一个个终终止止条条件件。。层次次方方法法的的缺缺陷陷在在于于，，一一旦旦一一个个步步骤骤完完成成，，就就不不能能够够被被撤撤销销。。基于于LB_Hust距离离的的时时间间序序列列聚聚类类层次次聚聚类类算算法法在在聚聚类类算算法法中中不不必必确确定定初初始始聚聚类类中中心心，，对对聚聚类类过过程程中中数数据据的的输输入入顺顺序序不不敏敏感感，，同同时时对对用用户户输输入入参参数数要要求求较较低低，，本本文文中中层层次次聚聚类类算算法法采采用用设设定定聚聚类类最最终终簇簇数数的的方方法法终终止止聚聚类类，，从从而而自自发发形形成成聚聚类类，，保保证证了了聚聚类类过过程程中中根根据据数数据据之之间间相相似似程程度度进进行行归归并并，，人人为为影影响响因因素素较较小小。。输入入：：时间间序序列列数数据据库库：：TSDB；允许许的的弯弯曲曲路路径径时时间间窗窗：：w；最大大的的簇簇数数：：K；输出出：：K个簇簇：：{C1，C2、，，···········CK}；LB_Keogh：一种种考考虑虑弯弯曲曲路路径径限限制制的的DTW计算算方方法法对于于弯弯曲曲路路径径限限制制为为w的时时间间序序列列DTW距离离计计算算，，定定义义两两个个序序列列U和L，其其中中对对于于第第i个元元素素我我们们有有如如下下的的上上下下界界定定义义：：U和L作为为在在2w时间间窗窗内内，，对对于于原原时时间间序序列列的的每每个个元元素素所所对对应应的的上上下下界界，，表表现现在在图图形形上上实实际际上上是是形形成成了了一一个个带带状状的的域域将将原原始始时时间间序序列列包包裹裹在在这这个个域域中中，，如如图图3-4所示示。。此时时，，LB_Keogh距离离定定义义为为：：定理理：：对对于于长长度度为为n的任任何何两两个个时时间间序序列列X和Y，限限定定弯弯曲曲路路径径窗窗口口为为w，即即对对于于xi和yj点的的比比较较，，限限定定为为j-wij+w，存存在在如如下下不不等等式式：：LB_Keogh(X,Y)DTW(X,Y)。性质质：：LB_Keogh距离离不不是是对对称称的的。。即即LB_Keogh(X,Y)LB_Keogh(Y,X)。LB_Keogh的Matlab实现现LB_Keogh=sqrt(sum([[Q>U].*[Q-U];[Q<L].*[L-Q]].^2));LB_Hust距离离---对LB_Keogh距离离的的改改进进针对对LB_Keogh距离离计计算算的的非非对对称称性性其中中，，Lxi和Uxi分别别对对应应时时间间序序列列X的第第i个元元素素在在2w时间间域域内内的的最最小小值值和和最最大大值值。。Lyi和Uyi同理理。。距距离离产产生生方方式式如如图图3-5所示示。。定理理：：对对于于长长度度为为n的任任何何两两个个时时间间序序列列X和Y，限限定定弯弯曲曲路路径径窗窗口口为为w，即即对对于于xi和yj点的的比比较较，，限限定定为为j-wij+w，存存在在如如下下不不等等式式：：LB_Hust(X,Y)Keogh(X,Y)。性质质1：LB_Hust距离离是是对对称称的的。。即即LB_Hust(X,Y)=LB_Hust(Y,X)。这可可以减减少距距离计计算的的次数数。性质2：在LB_Hust距离计计算方方式下下，时时间复复杂度度由传传统的的DTW距离计计算的的O(nm)缩减到到O(n)。基于LB_Hust距离的的时间间序列列聚类类算法流流程：：1)初始状状态下下所有有有时时间序序列数数据自自成一一簇，，每条条时间间序列列数据据为各各自的的簇中中心，，循环环2）到4）。2)根据时时间序序列数数据上上下界界曲线线形成成方法法求取取当前前簇中中心的的上下下界序序列Us和Ls。3)计算两两两簇簇之间间的距距离，，记录录具有有最小小距离离的两两个簇簇，将将两个个簇归归并，，根据据归并并算法法更新新聚类类中心心。4)若当前前聚类类簇数数达到到K，则终终止，，否则则转到到2)。分析上上述算算法，，存在在的两两个关关键的的函数数是计计算两两个序序列的的LB_Hust距离和和求取取新的的簇中中心两两个函函数。。基于LB_Hust距离矩矩阵的的层次次聚类类基于距距离矩矩阵的的层次次聚类类算法法是以以牺牲牲空间间换取取时间间的算算法，，存放放n条记录录两两两之间间的距距离，，在距距离函函数计计算具具有对对称性性的情情况下下，实实际的的矩阵阵只需需存放放上三三角或或下三三角n*(n+1)/2个数据据。这这也是是应用用LB_Hust距离计计算函函数的的一个个重要要原因因。输入：：时间间序列列数据据库：：TSDB；允许的的弯曲曲路径径时间间窗：：w；最大的的簇数数：K；输出：：K个簇：：{C1，C2、，········CK}；基于LB_Hust距离矩矩阵的的层次次聚类类算法流流程：：1)初始状状态下下所有有时间间序列列数据据自成成一簇簇，每每条时时间序序列数数据为为各自自的簇簇中心心，初初始化化距离离矩阵阵，计计算任任意两两条时时间序序列数数据间间的距距离，，循环环2）到5）。2)找到距距离矩矩阵中中的最最小距距离对对应的的两个个簇，，合并并，形形成新新的簇簇中心心。3)根据时时间序序列数数据上上下界界曲线线形成成方法法求取取当前前簇中中心的的上下下界索索引序序列Us、Ls。4)重新计计算当当前簇簇中心心和其其余簇簇的距距离，，更新新距离离矩阵阵。5)若当前前聚类类簇数数达到到K，则终终止，，否则则转到到2)。对于上上述采采用距距离矩矩阵的的层次次聚类类，相相比前前面算算法，，每一一层合合并时时，距距离计计算次次数为为c(n,2)次，其其中n表示当当前层层中的的簇数数，时时间复复杂度度为o(n2)，采用用距离离矩阵阵方法法则每每次仅仅需计计算n次距离离。应用---股票数数据聚聚类股票数数据作作为典典型的的时间间序列列数据据，被被众多多时间间序列列挖掘掘方法法作为为实验验性数数据。。典型型的股股票行行情原原始数数据包包括股股票的的开盘盘价、、最高高价、、最低低价、、收盘盘价、、成交交量、、成交交金额额等，，所有有属性性的值值对应应着一一个特特定时时刻，，在固固定时时间段段内形形成了了典型型的时时间序序列数数据。。对于多多支股股票的的聚类类是从从控股股公司司间的的经营营状况况、经经营手手段及及外界界影响响因素素的相相似程程度进进行聚聚类。。通过过对多多支股股票的的聚类类，可可以发发现股股票运运动规规律相相似的的企业业，对对中长长期股股票投投资者者选股股提供供一些些参考考。股票数数据聚聚类：：数据据准备备采用搜搜狐财财经网网(/)的股票票历史史行情情数据据作为为实验验数据据，从从中选选择29支股票票作为为实验验数据据：宝宝钢股股份、、包钢钢股份份、上上海电电力、、招商商轮船船、中中国石石油、、中中国银银行、、中海海油服服、武武钢股股份、、东湖湖高新新、万万东医医疗、、林海海股份份、中中视传传媒等等。在在数据据库中中，存存储股股票的的名称称采用用字母母代号号表示示，将将29支股票票对应应到A~A3的29个字母母串。。抽取从从2010年3月份到到2010年五月月份的的股票票历史史行情情数据据，将将其中中的每每日收收盘价价作为为实验验数据据。在在提取取的数数据中中发现现，股股票数数据存存在如如下两两个特特点：：一、由于于股市的的休市，，股票数数据存在在空值；二、股票票之间的的收盘价价存在很很大差异异。股票数据据聚类：：数据准准备股票数据据普遍存存在空值值，主要要是基于于两种情情况：一一、正常常的股市市休市。。二、个个别控股股公司由由于内部部整合或或者公司司内部事事件出现现停开。。每支股票票数据在在休市时时都是空空值，因因此可采采用直接接删除的的方法不不会影响响到时间间序列的的时间对对等性。。针对公司司内部事事件引起起的空值值采取填填补处理理。填补补数据根根据线性性化函数数取得，，对每个个空值，，以空值值上下非非空数据据为端点点得到一一次线性性化函数数，通过过线性化化函数可可以取得得空值对对应时间间点的股股价。股票数据据聚类：：数据准准备采用线性性化函数数进行填填补处理理是基于于两点考考虑：首先，基基于对LB_Hust距离计算算的过程程，对于于时间序序列曲线线，趋势势的变动动和时间间序列的的连续能能够增强强相似性性比较效效果，所所以，对对空值数数据进行行线性的的平滑处处理可以以更好地地应用LB_Hust距离计算算方法。。其次，从从实际意意义来看看，在空空值出现现前的阶阶段和空空值结束束后，两两者股价价一般不不同，可可见在股股价为空空值的阶阶段，实实际上隐隐藏着一一些影响响股价变变动的因因素发生生着作用用，通过过线性化化函数，，将期间间出现的的变化过过程连续续的表达达出来，，函数中中的斜率率保持了了股价在在空值出出现阶段段的趋势势变动变变化规律律，通过过这种填填补方法法使得股股价波动动曲线更更连续和和平滑股票数据据聚类：：数据的的归一化化除了空值值问题，，股票数数据另一一典型的的特点就就是不同同公司的的股价在在数值上上差异很很大。股票数据据聚类：：数据的的归一化化针对股票票数据间间的股价价差距大大的问题题，采用用归一化化处理，，归一化化处理主主要解决决比较数数据间量量纲不统统一的问问题，在在对股票票进行聚聚类分析析中，股股票的相相似性集集中于股股价变化化趋势的的相似性性，而非非股价之之间的相相似性，，所以采采用以下下公式对对数据据进行归归一化处处理。股票数据据聚类：：聚类结结果运行层次次聚类算算法时初初始设定定聚类簇簇数为4个，同时时设定时时间弯折折窗口w为3。股票数据据聚类：：聚类结结果运行层次次聚类算算法时初初始设定定聚类簇簇数为4个，同时时设定时时间弯折折窗口w为3。股票数据据聚类：：聚类结结果运行层次次聚类算算法时初初始设定定聚类簇簇数为4个，同时时设定时时间弯折折窗口w为3。股票数据据聚类：：聚类结结果运行层次次聚类算算法时初初始设定定聚类簇簇数为4个，同时时设定时时间弯折折窗口w为3。基于SAX表示的聚聚类HierarchicalClusteringComputepairwisedistance,mergesimilarclustersbottom-upComparedwithEuclidean,IMPACTS,andSDA基于SAX表示的距距离PAAdistancelower-boundstheEuclideanDistance

0

20

40

60

80

100

120

-1.5

-1

-0.5

0

0.5

1

1.5

C

Q

0

20

40

60

80

100

120

-1.5

-1

-0.5

0

0.5

1

1.5C

Q

=baabccbcCˆ=babcaccaQˆEuclideanDistancedist()canbeimplementedusingatablelookup.HierarchicalClusteringWecanobjectivelystatethatSAXissuperior,sinceitcorrectlyassignseachclasstoitsownsubtree.数据类别别事先已已知：decreasingtrend,upwardshiftandnormalclassesClusteringHierarchicalClusteringComputepairwisedistance,mergesimilarclustersbottom-upComparedwithEuclidean,IMPACTS,andSDAPartitionalClusteringK-meansOptimizetheobjectivefunctionbyminimizingthesumofsquaredintra-clustererrorsComparedwithRawdata比层次聚聚类具有有更好的的可伸缩缩性Partitional(K-means)ClusteringWorkingwithanapproximationofthedatagivesbetterresultsthanworkingwiththeoriginaldata.Ithasbeenshownthatinitializingtheclusterscentersonalowdimensionapproximationofthedatacanimprovethequality,thisiswhatclusteringwithSAXimplicitlydoes.Acomparisonofthek-meansclusteringalgorithmusingSAXandtherawdata.ThedatasetwasSpaceShuttletelemetry,1,000subsequencesoflength512.Surprisingly,workingwiththesymbolicapproximationproducesbetterresultsthanworkingwiththeoriginaldata动态时间序列列聚类TimeSeriesEpenthesis:ClusteringTimeSeriesStreamsRequiresIgnoringSomeData动态时间序列列聚类所谓流数据，，是指按照一一定的时间顺顺序，以较快快的速度连续续到达的数据据序列，也称称为动态时间间序列。流数据聚类的的难点在于：：数据流随着着时间的推移移近似地等效效于一个无限的数据集合，，因此对流数数据的随机访访问几乎是不不可能实现的的，因此流数数据聚类通常常都要求“一次性扫描数数据”。流数据聚类类算法首先对对每个新到达达的数据进行行访问处理，，之后数据即即被放入随机机访问代价较较高的存储设设备，或者直直接被丢弃。。流数据聚类算算法通常会维维护一个“概要数据结构构”，用来保存数数据的摘要信信息，当需要要输出聚类结结果时，以概概要数据结构构中保存的信信息作为目标标对象集合，，生成所需要要的结果。流数据实例商业领域中，，大型仓储超超市的交易数数据。超市的的数据中心每每天收到各个个分店大量的的交易记录，，包括顾客购购买物品，消消费金额等属属性，按照时时间顺序排列列。电信行业中，，移动公司可可采集到用户户的通话记录录，包括主叫叫号码，被叫叫号码，通话话时间，收费费金额等若干干属性。大量量的通话记录录以时间顺序序排列，汇集集到移动公司司的数据中心心，也可以被被抽象为是一一种“流”。医疗行业中，，使用生理信信号采集仪器器对患者进行行监控，心跳跳，脉搏，血血压等一系列列生理信号实实时地传送到到分析模块，，从中推测出出患者每一时时段的健康状状况。工业生产中，，一些大型设设备的安全检检测仪器每时时每刻将设备备的各项运转转参数采集出出来，作为数数据信号进行行分析处理。。流数据特点首先，数据量十分庞庞大，这些数据随随着时间的增增长数量急剧剧上升，如沃沃尔玛超市的的日交易次数数可达数十万万。其次，这些数数据均按照时间顺序序连续到达。另外，数据流速很快快，以广东省移移动公司的通通话记录为例例，高峰时间间每小时可达达数千条。流数据聚类问问题模型假设流数据由由一系列按照照时间顺序连连续到达的数数据点X1,...,Xi...构成，其中，，每个数据点点拥有d个属性，用d维向量的形式式来表示：那么流数据聚聚类问题，就就是将数据流流中的某个特特定的子对象象集合{X1,X2,...,XN}划分成k个簇区间(每个簇用其均均值中心点来来表示),使目标函数值值:达到最小。其其中Ci是Xi所在簇的中心心点，D(Xi,Ci)表示两个数据据点之间的距距离。流数据聚类问问题模型对该问题模型型，有几点需需要说明：1)目标集合中数数据对象的个个数N通常在数量级级上远远大于于传统算法中中的数据集合合，通常无法法将全部数据据读入内存进进行分析，因因此难以利用用传统的聚类类算法解决这这类问题。2)在流数据聚类类问题中，数数据通常只能能按照它们到到达的顺序访访问，此后，，数据即被存存放于外存或或丢弃，内存存中只能保存存已访问数据据的概要信息息。也就是说说，流数据算算法为了避免免高昂的系统统开销应该尽尽可能少地重重复访问数据据。事实上，，“一次扫描描数据”已经经成为几乎所所有流数据算算法都需要实实现的目标。。流数据聚类问问题模型3)流数据算法的的目标集合是是数据流中截截取的某一个个时间段(时间窗)的对象集合。。定义一个时时间窗需要两两个重要的输输入参数：起起始时刻t和时间窗口宽宽度h，一个时间窗窗口可用W(t,h)来表示。算法法的目标集合合即由落入窗窗口W(t,h)的数据对象组组成。4)在流数据算法法中，任何一一个时刻的较较小的误差，，都有可能随随着时间的推推移而急速扩扩大，最终造造成错误或质质量较低的算算法结果。因因此，在每一一个阶段都要要将误差严格格控制在一个个较小的区间间之内。5)同时，算法对对时间效率的的要求非常高高，当需要在在某一个特定定时刻输出聚聚类结果时，，如果处理过过程的时间开开销过大，则则有可能会造造成新到数据据的遗漏或丢丢失，这种信信息缺损随着着数据流的不不断进行而加加剧。早期的流数据据聚类早期的流数据据聚类努力将将数据流的动动态特性转化化为传统的静静态模式，从从而能够应用用成熟的传统统方法解决问问题。在这一一阶段，算法法研究的重点点是改进传统统算法的性能能，使之能够够适应流数据据的动态特性性。Small-Space算法正是这类类算法的典型型代表。Small-Space算法输入：按时间间顺序到达的的流数据序列列输出：k个聚类中心点点算法过程：1)首先对初始到到达的m个数据点进行行聚类，得到到O(k)个1-级聚类中心点点。2)重复上述步骤骤，当处理m2/O(k)个原始数据点点时，将得到到m个1-级中心点。3)对这m个1-级中心点进行行聚类得到O(k)个2-级中心点。4)迭代执行上述述过程，每次次迭代至多保保留m个i-级中心点，否否则进行聚类类得到O(k)个(i+1)-级中心点。5)输出聚类结果果时，对当前前所有中心点点进行聚类，，得到最终的的k个聚类中心。。■Small-Space算法的问题算法需要累积积数据点，当当数据量达到到一定限度时时进行统一处处理，而通常常处理算法较较为复杂，造造成了数据流流在处理节点点上的延迟。。另一方面，，在累积数数据点的过过程中，算算法处于空空闲状态，，在一定程程度上降低低了算法的的效率，增增加了时间间开销。双层流数据据聚类J.Han提出双层结结构算法CluStream[12]双层聚类算算法将处理理工作分为为两个层面面：在线层层算法负责责对数据进进行粗糙但但快速的处处理，并负负责保存中中间结果；；离线层算算法在中间间结果的基基础上进行行精确而复复杂的分析析，此时目目标集合已已成为静态态集合，因因此通常情情况下不必必考虑数据据流速的影影响，并得得到最终结结果。CluStream基本思想在线层维护护一系列的的“微簇””(Micro-Cluster)作为保存数数据概要信信息的数据据结构。每每个微簇用用五元组(SS，LS，ST，LT，N)来表示，其其中N为微簇中包包含的数据据点个数，，若数据维维度为d，则LS，与SS均为d维向量，LS为微簇中数数据点的线线性加和，，SS为微簇中数数据点的平平方和，LT为各个数据据点时间标标签的线性性加和，ST为各个数据据点时间标标签的平方方和。以上统计变变量分别是是关于数据据集合的零零阶矩，一一阶矩和二二阶矩。这这些信息可可以被用来来推演数据据的分布状状态，可以以用如下公公式计算数数据集合的的方差J：CluStream基本思想算法在初始始化时，首首先吸收足足够的数据据点，利用用k-均值方法对对这些初始始数据点进进行聚类得得到k个微簇。每当新的数数据点到达达时，在线线算法首先先尝试找到到一个其均均值中心点点距离该新新到数据点点最近的微微簇，如果果这个距离离小于给定定的阈值，，则微簇将将该点吸收收，修改代代表微簇的的五元组中中每个变量量的值；否否则，为该该数据点开开辟新的微微簇。为了开辟新新的微簇，，需要通过过删除现有有微簇或合合并两个现现有微簇的的方式释放放内存空间间。如果能能够找到两两个距离最最近的微簇簇，并且其其距离在一一定的阈值值之内，则则将其合并并；否则，，删除一个个最久未更更新的微簇簇，这是通通过检查微微簇的ST与LT属性得到的的。易见用用户对最近近数据更感感兴趣。CluStream基本思想在适当的时时刻对内存存中的所有有微簇进行行“快照””(snapshots)保存。这些些快照保存存在外存上上，作为离离线算法的的输入，可可以用来进进行数据流流演化分析析。CluStream基本思想用户在离线线部分可以以在不同时时间幅度内内发现簇。。所用的数数据是在线线部分形成成的统计信信息，这可可以满足内内存有限的的需求。用用户需提供供两个参数数h和k，，h是时间间幅度，k是预定义义的需要形形成的簇的的数目。离线部分采采用改进的的k-means算算法（1）初始始阶段不再随机地地选取种子子，而是选选择可能被被划分到给给定簇的种种子，这些些种子其实实是对应微微簇的中心心。（2）划分分阶段一个种子到到一个“伪伪数据点””（也就是是微簇）的的距离就等等于它到““伪数据点点”中心的的距离。（3）调整整阶段一个给定划划分的新种种子被定义义成那个划划分中带权权重的微簇簇中心。CluStream示意图CluStream算法优缺缺点优点：提出了两阶阶段聚类框框架，算法法能适应数数据流快速速、有序无无限、单遍遍扫描的特特点。能够够发掘数据据流潜在的的演化特性性。缺点：1、不能发发现任意形形状的簇；；2、不能很很好地识别别离群点；；3、对高维维数据聚类类质量下降降；谢谢！9、静静夜夜四四无无邻邻，，荒荒居居旧旧业业贫贫。。。。12月月-2212月月-22Saturday,December24,202210、雨雨中中黄黄叶叶树树，，灯灯下下白白头头人人。。。。07:25:2007:25:2007:2512/24/20227:25:20AM11、以我我独沈沈久，，愧君君相见见频。。。12月月-2207:25:2007:25Dec-2224-Dec-2212、故人江海海别，几度度隔山川。。。07:25:2007:25:2007:25Saturday,December24,202213、乍乍见见翻翻疑疑梦梦，，相相悲悲各各问问年年。。。。12月月-2212月月-2207:25:2007:25:20December24,202214、他乡生白发发，旧国见青青山。。24十二月月2