时间序列挖掘聚类课件

时间序列挖掘●聚类山西财经大学信息管理学院常新功第六章时间序列挖掘●聚类山西财经大学信息管理学院常新功第六章目录聚类的概念聚类算法的评价标准时间序列聚类概述k-mediods时间序列聚类基于LB_Hust距离的时间序列聚类基于SAX表示的聚类目录聚类的概念聚类的概念聚类（Clustering）是数据挖掘领域中的一个重要分支。所谓聚类，是指将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过程。聚类是依据事物的某些属性将其聚集成类，使类间相似性尽量小，类内相似性尽量大。2015.4.19，的深圳举办的新一代信息技术产业发展高峰论坛上，中国工程院院士李德毅在发言中指出，尽管目前对于大数据的认知存在挑战，但聚类将会成为大数据认知的突破口。通过大数据聚类即时发现价值，要充分认识大数据中的不确定性和价值的隐蔽性。聚类的概念聚类（Clustering）是数据挖掘领域中的一个聚类算法的评价标准1)可伸缩性：可伸缩性考察聚类算法对于目标对象集合的规模以及目标集合潜在的模式数量的适应性。2)处理不同类型属性的能力：除了通常处理的数值型数据，应用当中可能要求聚类其它类型的数据，如：二元类型，分类/标称类型，序数型，时间序列、图数据或者不同数据类型的混合。3)发现任意形状的聚类：许多聚类算法基于欧几里德距离或者曼哈顿距离度量来决定聚类。基于这种距离度量的算法趋向于发现具有相近尺度和密度的球状簇。但是一个簇可能是任意形状的，提出能发现任意形状簇的算法是很重要的。4)交互可视化：高维数据和复杂对象常常使可视化变得困难，而交互性则使算法与人结合有利于提高聚类的质量。聚类算法的评价标准1)可伸缩性：可伸缩性考察聚类算法对于目聚类算法的评价标准5)最小化用于决定输入参数的领域知识和数据记录敏感性：一方面要求降低算法对输入参数的敏感程度，另一方面要求输入记录顺序对算法的结果影响小。要求用户输入参数不仅会加重用户的负担，也使得聚类的质量难以控制。6)处理噪声数据的能力：绝大多数现实世界中的数据库都包含了孤立点，空缺，未知或者错误的数据。一些聚类算法对于这样的数据敏感，导致聚类质量不高。7)高维性：许多聚类算法只擅长处理低维数据。在高维空间中聚类数据对象是一个挑战，特别是在数据有可能非常稀疏和偏斜时。8)可解释性和可用性：知识发现过程中，聚类结果总是需要表现为一定的知识，这就要求聚类结果可解释，易理解。聚类算法的评价标准5)最小化用于决定输入参数的领域知识和数时间序列聚类概述时间序列聚类是时间序列数据挖掘的一个非常基础且非常活跃的研究方向，被广泛应用于包括模式识别、数据分析、图像处理、市场分析等各个领域：零售数据的季节模式聚类、国家能源消耗聚类分析、心电图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-medoids时间序列聚类k-mediods时间序列聚类1、k-中心点聚类基本原理：k-均值的缺点：对离群点敏感k-中心点：挑选实际对象来代表簇，每个簇使用一个代表对象。实现：围绕中心点划分（PartitioningAroundMedoids,PAM)算法算法:k-中心点。PAM输入：

k：结果簇的个数

D：包含n个对象的数据集合输出：

k个簇的集合k-mediods时间序列聚类1、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时间序列聚类方法：k-mediods时间序列聚类2、基于k中心点方法的时间序列聚类

见kmedoidtsclustering.cppk-mediods时间序列聚类2、基于k中心点方法的时间序列基于LB_Hust距离的时间序列聚类层次聚类方法对给定数据对象集合进行层次分解。根据层次的分解如何形成，层次的方法可以分为凝聚的（agglomerativeormerging）和分裂的（divisiveorsplitting）两种类型。凝聚的方法，也称为自底向上的方法，初始化将每个对象作为单独的一个簇，然后相继地合并相近的对象或簇，直到所有的簇合并为一个，或者达到一个终止条件。分裂的方法，也成为自顶向下的方法，初始化将所有的对象置于一个簇中。在迭代的每一步中，一个簇被分裂为更小的簇，直到最终每个对象在单独的一个簇中，或者达到一个终止条件。层次方法的缺陷在于，一旦一个步骤完成，就不能够被撤销。基于LB_Hust距离的时间序列聚类层次聚类方法对给定数基于LB_Hust距离的时间序列聚类层次聚类算法在聚类算法中不必确定初始聚类中心，对聚类过程中数据的输入顺序不敏感，同时对用户输入参数要求较低，本文中层次聚类算法采用设定聚类最终簇数的方法终止聚类，从而自发形成聚类，保证了聚类过程中根据数据之间相似程度进行归并，人为影响因素较小。输入：时间序列数据库：TSDB；允许的弯曲路径时间窗：w；最大的簇数：K；输出：K个簇：{C1，C2、，······CK}；基于LB_Hust距离的时间序列聚类层次聚类算法在聚类算

LB_Keogh：一种考虑弯曲路径限制的DTW计算方法对于弯曲路径限制为w的时间序列DTW距离计算，定义两个序列U和L，其中对于第i个元素我们有如下的上下界定义：U和L作为在2w时间窗内，对于原时间序列的每个元素所对应的上下界，表现在图形上实际上是形成了一个带状的域将原始时间序列包裹在这个域中，如图3-4所示。LB_Keogh：一种考虑弯曲路径限制的DTW计算方法对第六章时间序列挖掘聚类课件此时，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距离定义为：定理：对于长度为n的LB_Keogh的Matlab实现LB_Keogh=sqrt(sum([[Q

>

U].*[Q-U];[Q

<

L].*[L-Q]].^2));LB_Keogh的Matlab实现LB_Keogh=sqrtLB_Hust

距离---对LB_Keogh距离的改进针对LB_Keogh距离计算的非对称性其中，Lxi和Uxi分别对应时间序列X的第i个元素在2w时间域内的最小值和最大值。Lyi和Uyi同理。距离产生方式如图3-5所示。LB_Hust距离---对LB_Keogh距离的改进针对第六章时间序列挖掘聚类课件定理：对于长度为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)。定理：对于长度为n的任何两个时间序列X和Y，限定弯基于LB_Hust距离的时间序列聚类算法流程：1)初始状态下所有有时间序列数据自成一簇，每条时间序列数据为各自的簇中心，循环2）到4）。2)根据时间序列数据上下界曲线形成方法求取当前簇中心的上下界序列Us和Ls。3)计算两两簇之间的距离，记录具有最小距离的两个簇，将两个簇归并，根据归并算法更新聚类中心。4)若当前聚类簇数达到K，则终止，否则转到2)。分析上述算法，存在的两个关键的函数是计算两个序列的LB_Hust距离和求取新的簇中心两个函数。基于LB_Hust距离的时间序列聚类算法流程：基于LB_Hust距离矩阵的层次聚类基于距离矩阵的层次聚类算法是以牺牲空间换取时间的算法，存放n条记录两两之间的距离，在距离函数计算具有对称性的情况下，实际的矩阵只需存放上三角或下三角n*(n+1)/2个数据。这也是应用LB_Hust距离计算函数的一个重要原因。输入：时间序列数据库：TSDB；允许的弯曲路径时间窗：w；最大的簇数：K；输出：K个簇：{C1，C2、，······CK}；基于LB_Hust距离矩阵的层次聚类基于距离矩阵的层次聚基于LB_Hust距离矩阵的层次聚类算法流程：1)初始状态下所有时间序列数据自成一簇，每条时间序列数据为各自的簇中心，初始化距离矩阵，计算任意两条时间序列数据间的距离，循环2）到5）。2)找到距离矩阵中的最小距离对应的两个簇，合并，形成新的簇中心。3)根据时间序列数据上下界曲线形成方法求取当前簇中心的上下界索引序列Us、Ls。4)重新计算当前簇中心和其余簇的距离，更新距离矩阵。5)若当前聚类簇数达到K，则终止，否则转到2)。对于上述采用距离矩阵的层次聚类，相比前面算法，每一层合并时，距离计算次数为c(n,2)次，其中n表示当前层中的簇数，时间复杂度为o(n2)，采用距离矩阵方法则每次仅需计算n次距离。基于LB_Hust距离矩阵的层次聚类算法流程：应用---股票数据聚类股票数据作为典型的时间序列数据，被众多时间序列挖掘方法作为实验性数据。典型的股票行情原始数据包括股票的开盘价、最高价、最低价、收盘价、成交量、成交金额等，所有属性的值对应着一个特定时刻，在固定时间段内形成了典型的时间序列数据。对于多支股票的聚类是从控股公司间的经营状况、经营手段及外界影响因素的相似程度进行聚类。通过对多支股票的聚类，可以发现股票运动规律相似的企业，对中长期股票投资者选股提供一些参考。应用---股票数据聚类股票数据作为典型的时间序列数据，被众多股票数据聚类：数据准备采用搜狐财经网(/)的股票历史行情数据作为实验数据，从中选择29支股票作为实验数据：宝钢股份、包钢股份、上海电力、招商轮船、中国石油、中国银行、中海油服、武钢股份、东湖高新、万东医疗、林海股份、中视传媒等。在数据库中，存储股票的名称采用字母代号表示，将29支股票对应到A~A3的29个字母串。抽取从2010年3月份到2010年五月份的股票历史行情数据，将其中的每日收盘价作为实验数据。在提取的数据中发现，股票数据存在如下两个特点：一、由于股市的休市，股票数据存在空值；二、股票之间的收盘价存在很大差异。股票数据聚类：数据准备采用搜狐财经网(http://q.st股票数据聚类：数据准备股票数据普遍存在空值，主要是基于两种情况：一、正常的股市休市。二、个别控股公司由于内部整合或者公司内部事件出现停开。每支股票数据在休市时都是空值，因此可采用直接删除的方法不会影响到时间序列的时间对等性。针对公司内部事件引起的空值采取填补处理。填补数据根据线性化函数取得，对每个空值，以空值上下非空数据为端点得到一次线性化函数，通过线性化函数可以取得空值对应时间点的股价。股票数据聚类：数据准备股票数据普遍存在空值，主要是基于两种情股票数据聚类：数据准备采用线性化函数进行填补处理是基于两点考虑：首先，基于对LB_Hust距离计算的过程，对于时间序列曲线，趋势的变动和时间序列的连续能够增强相似性比较效果，所以，对空值数据进行线性的平滑处理可以更好地应用LB_Hust距离计算方法。其次，从实际意义来看，在空值出现前的阶段和空值结束后，两者股价一般不同，可见在股价为空值的阶段，实际上隐藏着一些影响股价变动的因素发生着作用，通过线性化函数，将期间出现的变化过程连续的表达出来，函数中的斜率保持了股价在空值出现阶段的趋势变动变化规律，通过这种填补方法使得股价波动曲线更连续和平滑股票数据聚类：数据准备采用线性化函数进行填补处理是基于两点考股票数据聚类：数据的归一化除了空值问题，股票数据另一典型的特点就是不同公司的股价在数值上差异很大。股票数据聚类：数据的归一化除了空值问题，股票数据另一典型的特股票数据聚类：数据的归一化针对股票数据间的股价差距大的问题，采用归一化处理，归一化处理主要解决比较数据间量纲不统一的问题，在对股票进行聚类分析中，股票的相似性集中于股价变化趋势的相似性，而非股价之间的相似性，所以采用以下公式对数据进行归一化处理。股票数据聚类：数据的归一化针对股票数据间的股价差距大的问题，股票数据聚类：聚类结果运行层次聚类算法时初始设定聚类簇数为4个，同时设定时间弯折窗口w为3。股票数据聚类：聚类结果运行层次聚类算法时初始设定聚类簇数为4股票数据聚类：聚类结果运行层次聚类算法时初始设定聚类簇数为4个，同时设定时间弯折窗口w为3。股票数据聚类：聚类结果运行层次聚类算法时初始设定聚类簇数为4股票数据聚类：聚类结果运行层次聚类算法时初始设定聚类簇数为4个，同时设定时间弯折窗口w为3。股票数据聚类：聚类结果运行层次聚类算法时初始设定聚类簇数为4股票数据聚类：聚类结果运行层次聚类算法时初始设定聚类簇数为4个，同时设定时间弯折窗口w为3。股票数据聚类：聚类结果运行层次聚类算法时初始设定聚类簇数为4基于SAX表示的聚类HierarchicalClusteringComputepairwisedistance,mergesimilarclustersbottom-upComparedwithEuclidean,IMPACTS,andSDA基于SAX表示的聚类HierarchicalCluster基于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

=

baabccbc

Cˆ

=

babcacca

QˆEuclideanDistancedist()canbeimplementedusingatablelookup.基于SAX表示的距离PAAdistancelower-b第六章时间序列挖掘聚类课件第六章时间序列挖掘聚类课件HierarchicalClusteringWecanobjectivelystatethatSAXissuperior,sinceitcorrectlyassignseachclasstoitsownsubtree.数据类别事先已知：decreasingtrend,upwardshiftandnormalclassesHierarchicalClusteringWecanClusteringHierarchicalClusteringComputepairwisedistance,mergesimilarclustersbottom-upComparedwithEuclidean,IMPACTS,andSDAPartitionalClusteringK-meansOptimizetheobjectivefunctionbyminimizingthesumofsquaredintra-clustererrorsComparedwithRawdata比层次聚类具有更好的可伸缩性ClusteringHierarchicalClusterPartitional(K-means)ClusteringWorkingwithanapproximationofthedatagivesbetterresultsthanworkingwiththeoriginaldata.Ithasbeenshownthatinitializingtheclusterscentersonalowdimensionapproximationofthedatacanimprovethequality,thisiswhatclusteringwithSAXimplicitlydoes.Acomparisonofthek-meansclusteringalgorithmusingSAXandtherawdata.ThedatasetwasSpaceShuttletelemetry,1,000subsequencesoflength512.Surprisingly,workingwiththesymbolicapproximationproducesbetterresultsthanworkingwiththeoriginaldataPartitional(K-means)Clusteri动态时间序列聚类TimeSeriesEpenthesis:ClusteringTimeSeriesStreamsRequiresIgnoringSomeData动态时间序列聚类TimeSeriesEpenthesis动态时间序列聚类所谓流数据，是指按照一定的时间顺序，以较快的速度连续到达的数据序列，也称为动态时间序列。流数据聚类的难点在于：数据流随着时间的推移近似地等效于一个无限的数据集合，因此对流数据的随机访问几乎是不可能实现的，因此流数据聚类通常都要求“一次性扫描数据”。流数据聚类算法首先对每个新到达的数据进行访问处理，之后数据即被放入随机访问代价较高的存储设备，或者直接被丢弃。流数据聚类算法通常会维护一个“概要数据结构”，用来保存数据的摘要信息，当需要输出聚类结果时，以概要数据结构中保存的信息作为目标对象集合，生成所需要的结果。动态时间序列聚类所谓流数据，是指按照一定的时间顺序，以较快的流数据实例商业领域中，大型仓储超市的交易数据。超市的数据中心每天收到各个分店大量的交易记录，包括顾客购买物品，消费金额等属性，按照时间顺序排列。电信行业中，移动公司可采集到用户的通话记录，包括主叫号码，被叫号码，通话时间，收费金额等若干属性。大量的通话记录以时间顺序排列，汇集到移动公司的数据中心，也可以被抽象为是一种“流”。医疗行业中，使用生理信号采集仪器对患者进行监控，心跳，脉搏，血压等一系列生理信号实时地传送到分析模块，从中推测出患者每一时段的健康状况。工业生产中，一些大型设备的安全检测仪器每时每刻将设备的各项运转参数采集出来，作为数据信号进行分析处理。流数据实例商业领域中，大型仓储超市的交易数据。超市的数据中心流数据特点首先，数据量十分庞大，这些数据随着时间的增长数量急剧上升，如沃尔玛超市的日交易次数可达数十万。其次，这些数据均按照时间顺序连续到达。另外，数据流速很快，以广东省移动公司的通话记录为例，高峰时间每小时可达数千条。流数据特点首先，数据量十分庞大，这些数据随着时间的增长数量急流数据聚类问题模型假设流数据由一系列按照时间顺序连续到达的数据点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)同时，算法对时间效率的要求非常高，当需要在某一个特定时刻输出聚类结果时，如果处理过程的时间开销过大，则有可能会造成新到数据的遗漏或丢失，这种信息缺损随着数据流的不断进行而加剧。流数据聚类问题模型3)流数据算法的目标集合是数据流中截取的某早期的流数据聚类早期的流数据聚类努力将数据流的动态特性转化为传统的静态模式，从而能够应用成熟的传统方法解决问题。在这一阶段，算法研究的重点是改进传统算法的性能，使之能够适应流数据的动态特性。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算法输入：按时间顺序到达的流数据序列Small-Space算法的问题算法需要累积数据点，当数据量达到一定限度时进行统一处理，而通常处理算法较为复杂，造成了数据流在处理节点上的延迟。另一方面，在累积数据点的过程中，算法处于空闲状态，在一定程度上降低了算法的效率，增加了时间开销。Small-Space算法的问题算法需要累积数据点，当数据双层流数据聚类J.Han提出双层结构算法CluStream[12]双层聚类算法将处理工作分为两个层面：在线层算法负责对数据进行粗糙但快速的处理，并负责保存中间结果；离线层算法在中间结果的基础上进行精确而复杂的分析，此时目标集合已成为静态集合，因此通常情况下不必考虑数据流速的影响，并得到最终结果。双层流数据聚类J.Han提出双层结构算法CluStreCluStream基本思想在线层维护一系列的“微簇”(Micro-Cluster)作为保存数据概要信息的数据结构。每个微簇用五元组(SS，LS，ST，LT，N)来表示，其中N为微簇中包含的数据点个数，若数据维度为d，则LS，与SS均为d维向量，LS为微簇中数据点的线性加和，SS为微簇中数据点的平方和，LT为各个数据点时间标签的线性加和，ST为各个数据点时间标签的平方和。以上统计变量分别是关于数据集合的零阶矩，一阶矩和二阶矩。这些信息可以被用来推演数据的分布状态，可以用如下公式计算数据集合的方差J：CluStream基本思想在线层维护一系列的“微簇”(MicCluStream基本思想算法在初始化时，首先吸收足够的数据点，利用k-均值方法对这些初始数据点进行聚类得到k个微簇。每当新的数据点到达时，在线算法首先尝试找到一个其均值中心点距离该新到数据点最近的微簇，如果这个距离小于给定的阈值，则微簇将该点吸收，修改代表微簇的五元组中每个变量的值；否则，为该数据点开辟新的微簇。为了开辟新的微簇，需要通过删除现有微簇或合并两个现有微簇的方式释放内存空间。如果能够找到两个距离最近的微簇，并且其距离在一定的阈值之内，则将其合并；否则，删除一个最久未更新的微簇，这是通过检查微簇的ST与LT属性得到的。易见用户对最近数据更感兴趣。CluStream基本思想算法在初始化时，首先吸收足够的数据CluStream基本思想在适当的时刻对内存中的所有微簇进行“快照”(snapshots)保存。这些快照保存在外存上，作为离线算法的输入，可以用来进行数据流演化分析。CluStream基本思想在适当的时刻对内存中的所有微簇进行CluStream基本思想用户在离线部分可以在不同时间幅度内发现簇。所用的数据是在线部分形成的统计信息，这可以满足内存有限的需求。用户需提供两个参数h和k，h是时间幅度，k是预定义的需要形成的簇的数目。离线部分采用改进的k-means算法（1）初始阶段 不再随机地选取种子，而是选择可能被划分到给定簇的种子，这些种子其实是对应微簇的中心。（2）划分阶段 一个种子到一个“伪数据点”（也就是微簇）的距离就等于它到“伪数据点”中心的距离。（3）调整阶段 一个给定划分的新种子被定义成那个划分中带权重的微簇中心。CluStream基本思想用户在离线部分可以在不同时间幅度内CluStream示意图CluStream示意图CluStream算法优缺点优点： 提出了两阶段聚类框架，算法能适应数据流快速、有序无限、单遍扫描的特点。能够发掘数据流潜在的演化特性。缺点： 1、不能发现任意形状的簇； 2、不能很好地识别离群点； 3、对高维数据聚类质量下降；CluStream算法优缺点优点：谢谢！谢谢！时间序列挖掘●聚类山西财经大学信息管理学院常新功第六章时间序列挖掘●聚类山西财经大学信息管理学院常新功第六章目录聚类的概念聚类算法的评价标准时间序列聚类概述k-mediods时间序列聚类基于LB_Hust距离的时间序列聚类基于SAX表示的聚类目录聚类的概念聚类的概念聚类（Clustering）是数据挖掘领域中的一个重要分支。所谓聚类，是指将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过程。聚类是依据事物的某些属性将其聚集成类，使类间相似性尽量小，类内相似性尽量大。2015.4.19，的深圳举办的新一代信息技术产业发展高峰论坛上，中国工程院院士李德毅在发言中指出，尽管目前对于大数据的认知存在挑战，但聚类将会成为大数据认知的突破口。通过大数据聚类即时发现价值，要充分认识大数据中的不确定性和价值的隐蔽性。聚类的概念聚类（Clustering）是数据挖掘领域中的一个聚类算法的评价标准1)可伸缩性：可伸缩性考察聚类算法对于目标对象集合的规模以及目标集合潜在的模式数量的适应性。2)处理不同类型属性的能力：除了通常处理的数值型数据，应用当中可能要求聚类其它类型的数据，如：二元类型，分类/标称类型，序数型，时间序列、图数据或者不同数据类型的混合。3)发现任意形状的聚类：许多聚类算法基于欧几里德距离或者曼哈顿距离度量来决定聚类。基于这种距离度量的算法趋向于发现具有相近尺度和密度的球状簇。但是一个簇可能是任意形状的，提出能发现任意形状簇的算法是很重要的。4)交互可视化：高维数据和复杂对象常常使可视化变得困难，而交互性则使算法与人结合有利于提高聚类的质量。聚类算法的评价标准1)可伸缩性：可伸缩性考察聚类算法对于目聚类算法的评价标准5)最小化用于决定输入参数的领域知识和数据记录敏感性：一方面要求降低算法对输入参数的敏感程度，另一方面要求输入记录顺序对算法的结果影响小。要求用户输入参数不仅会加重用户的负担，也使得聚类的质量难以控制。6)处理噪声数据的能力：绝大多数现实世界中的数据库都包含了孤立点，空缺，未知或者错误的数据。一些聚类算法对于这样的数据敏感，导致聚类质量不高。7)高维性：许多聚类算法只擅长处理低维数据。在高维空间中聚类数据对象是一个挑战，特别是在数据有可能非常稀疏和偏斜时。8)可解释性和可用性：知识发现过程中，聚类结果总是需要表现为一定的知识，这就要求聚类结果可解释，易理解。聚类算法的评价标准5)最小化用于决定输入参数的领域知识和数时间序列聚类概述时间序列聚类是时间序列数据挖掘的一个非常基础且非常活跃的研究方向，被广泛应用于包括模式识别、数据分析、图像处理、市场分析等各个领域：零售数据的季节模式聚类、国家能源消耗聚类分析、心电图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-medoids时间序列聚类k-mediods时间序列聚类1、k-中心点聚类基本原理：k-均值的缺点：对离群点敏感k-中心点：挑选实际对象来代表簇，每个簇使用一个代表对象。实现：围绕中心点划分（PartitioningAroundMedoids,PAM)算法算法:k-中心点。PAM输入：

k：结果簇的个数

D：包含n个对象的数据集合输出：

k个簇的集合k-mediods时间序列聚类1、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时间序列聚类方法：k-mediods时间序列聚类2、基于k中心点方法的时间序列聚类

见kmedoidtsclustering.cppk-mediods时间序列聚类2、基于k中心点方法的时间序列基于LB_Hust距离的时间序列聚类层次聚类方法对给定数据对象集合进行层次分解。根据层次的分解如何形成，层次的方法可以分为凝聚的（agglomerativeormerging）和分裂的（divisiveorsplitting）两种类型。凝聚的方法，也称为自底向上的方法，初始化将每个对象作为单独的一个簇，然后相继地合并相近的对象或簇，直到所有的簇合并为一个，或者达到一个终止条件。分裂的方法，也成为自顶向下的方法，初始化将所有的对象置于一个簇中。在迭代的每一步中，一个簇被分裂为更小的簇，直到最终每个对象在单独的一个簇中，或者达到一个终止条件。层次方法的缺陷在于，一旦一个步骤完成，就不能够被撤销。基于LB_Hust距离的时间序列聚类层次聚类方法对给定数基于LB_Hust距离的时间序列聚类层次聚类算法在聚类算法中不必确定初始聚类中心，对聚类过程中数据的输入顺序不敏感，同时对用户输入参数要求较低，本文中层次聚类算法采用设定聚类最终簇数的方法终止聚类，从而自发形成聚类，保证了聚类过程中根据数据之间相似程度进行归并，人为影响因素较小。输入：时间序列数据库：TSDB；允许的弯曲路径时间窗：w；最大的簇数：K；输出：K个簇：{C1，C2、，······CK}；基于LB_Hust距离的时间序列聚类层次聚类算法在聚类算

LB_Keogh：一种考虑弯曲路径限制的DTW计算方法对于弯曲路径限制为w的时间序列DTW距离计算，定义两个序列U和L，其中对于第i个元素我们有如下的上下界定义：U和L作为在2w时间窗内，对于原时间序列的每个元素所对应的上下界，表现在图形上实际上是形成了一个带状的域将原始时间序列包裹在这个域中，如图3-4所示。LB_Keogh：一种考虑弯曲路径限制的DTW计算方法对第六章时间序列挖掘聚类课件此时，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距离定义为：定理：对于长度为n的LB_Keogh的Matlab实现LB_Keogh=sqrt(sum([[Q

>

U].*[Q-U];[Q

<

L].*[L-Q]].^2));LB_Keogh的Matlab实现LB_Keogh=sqrtLB_Hust

距离---对LB_Keogh距离的改进针对LB_Keogh距离计算的非对称性其中，Lxi和Uxi分别对应时间序列X的第i个元素在2w时间域内的最小值和最大值。Lyi和Uyi同理。距离产生方式如图3-5所示。LB_Hust距离---对LB_Keogh距离的改进针对第六章时间序列挖掘聚类课件定理：对于长度为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)。定理：对于长度为n的任何两个时间序列X和Y，限定弯基于LB_Hust距离的时间序列聚类算法流程：1)初始状态下所有有时间序列数据自成一簇，每条时间序列数据为各自的簇中心，循环2）到4）。2)根据时间序列数据上下界曲线形成方法求取当前簇中心的上下界序列Us和Ls。3)计算两两簇之间的距离，记录具有最小距离的两个簇，将两个簇归并，根据归并算法更新聚类中心。4)若当前聚类簇数达到K，则终止，否则转到2)。分析上述算法，存在的两个关键的函数是计算两个序列的LB_Hust距离和求取新的簇中心两个函数。基于LB_Hust距离的时间序列聚类算法流程：基于LB_Hust距离矩阵的层次聚类基于距离矩阵的层次聚类算法是以牺牲空间换取时间的算法，存放n条记录两两之间的距离，在距离函数计算具有对称性的情况下，实际的矩阵只需存放上三角或下三角n*(n+1)/2个数据。这也是应用LB_Hust距离计算函数的一个重要原因。输入：时间序列数据库：TSDB；允许的弯曲路径时间窗：w；最大的簇数：K；输出：K个簇：{C1，C2、，······CK}；基于LB_Hust距离矩阵的层次聚类基于距离矩阵的层次聚基于LB_Hust距离矩阵的层次聚类算法流程：1)初始状态下所有时间序列数据自成一簇，每条时间序列数据为各自的簇中心，初始化距离矩阵，计算任意两条时间序列数据间的距离，循环2）到5）。2)找到距离矩阵中的最小距离对应的两个簇，合并，形成新的簇中心。3)根据时间序列数据上下界曲线形成方法求取当前簇中心的上下界索引序列Us、Ls。4)重新计算当前簇中心和其余簇的距离，更新距离矩阵。5)若当前聚类簇数达到K，则终止，否则转到2)。对于上述采用距离矩阵的层次聚类，相比前面算法，每一层合并时，距离计算次数为c(n,2)次，其中n表示当前层中的簇数，时间复杂度为o(n2)，采用距离矩阵方法则每次仅需计算n次距离。基于LB_Hust距离矩阵的层次聚类算法流程：应用---股票数据聚类股票数据作为典型的时间序列数据，被众多时间序列挖掘方法作为实验性数据。典型的股票行情原始数据包括股票的开盘价、最高价、最低价、收盘价、成交量、成交金额等，所有属性的值对应着一个特定时刻，在固定时间段内形成了典型的时间序列数据。对于多支股票的聚类是从控股公司间的经营状况、经营手段及外界影响因素的相似程度进行聚类。通过对多支股票的聚类，可以发现股票运动规律相似的企业，对中长期股票投资者选股提供一些参考。应用---股票数据聚类股票数据作为典型的时间序列数据，被众多股票数据聚类：数据准备采用搜狐财经网(/)的股票历史行情数据作为实验数据，从中选择29支股票作为实验数据：宝钢股份、包钢股份、上海电力、招商轮船、中国石油、中国银行、中海油服、武钢股份、东湖高新、万东医疗、林海股份、中视传媒等。在数据库中，存储股票的名称采用字母代号表示，将29支股票对应到A~A3的29个字母串。抽取从2010年3月份到2010年五月份的股票历史行情数据，将其中的每日收盘价作为实验数据。在提取的数据中发现，股票数据存在如下两个特点：一、由于股市的休市，股票数据存在空值；二、股票之间的收盘价存在很大差异。股票数据聚类：数据准备采用搜狐财经网(http://q.st股票数据聚类：数据准备股票数据普遍存在空值，主要是基于两种情况：一、正常的股市休市。二、个别控股公司由于内部整合或者公司内部事件出现停开。每支股票数据在休市时都是空值，因此可采用直接删除的方法不会影响到时间序列的时间对等性。针对公司内部事件引起的空值采取填补处理。填补数据根据线性化函数取得，对每个空值，以空值上下非空数据为端点得到一次线性化函数，通过线性化函数可以取得空值对应时间点的股价。股票数据聚类：数据准备股票数据普遍存在空值，主要是基于两种情股票数据聚类：数据准备采用线性化函数进行填补处理是基于两点考虑：首先，基于对LB_Hust距离计算的过程，对于时间序列曲线，趋势的变动和时间序列的连续能够增强相似性比较效果，所以，对空值数据进行线性的平滑处理可以更好地应用LB_Hust距离计算方法。其次，从实际意义来看，在空值出现前的阶段和空值结束后，两者股价一般不同，可见在股价为空值的阶段，实际上隐藏着一些影响股价变动的因素发生着作用，通过线性化函数，将期间出现的变化过程连续的表达出来，函数中的斜率保持了股价在空值出现阶段的趋势变动变化规律，通过这种填补方法使得股价波动曲线更连续和平滑股票数据聚类：数据准备采用线性化函数进行填补处理是基于两点考股票数据聚类：数据的归一化除了空值问题，股票数据另一典型的特点就是不同公司的股价在数值上差异很大。股票数据聚类：数据的归一化除了空值问题，股票数据另一典型的特股票数据聚类：数据的归一化针对股票数据间的股价差距大的问题，采用归一化处理，归一化处理主要解决比较数据间量纲不统一的问题，在对股票进行聚类分析中，股票的相似性集中于股价变化趋势的相似性，而非股价之间的相似性，所以采用以下公式对数据进行归一化处理。股票数据聚类：数据的归一化针对股票数据间的股价差距大的问题，股票数据聚类：聚类结果运行层次聚类算法时初始设定聚类簇数为4个，同时设定时间弯折窗口w为3。股票数据聚类：聚类结果运行层次聚类算法时初始设定聚类簇数为4股票数据聚类：聚类结果运行层次聚类算法时初始设定聚类簇数为4个，同时设定时间弯折窗口w为3。股票数据聚类：聚类结果运行层次聚类算法时初始设定聚类簇数为4股票数据聚类：聚类结果运行层次聚类算法时初始设定聚类簇数为4个，同时设定时间弯折窗口w为3。股票数据聚类：聚类结果运行层次聚类算法时初始设定聚类簇数为4股票数据聚类：聚类结果运行层次聚类算法时初始设定聚类簇数为4个，同时设定时间弯折窗口w为3。股票数据聚类：聚类结果运行层次聚类算法时初始设定聚类簇数为4基于SAX表示的聚类HierarchicalClusteringComputepairwisedistance,mergesimilarclustersbottom-upComparedwithEuclidean,IMPACTS,andSDA基于SAX表示的聚类HierarchicalCluster基于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

=

baabccbc

Cˆ

=

babcacca

QˆEuclideanDistancedist()canbeimplementedusingatablelookup.基于SAX表示的距离PAAdistancelower-b第六章时间序列挖掘聚类课件第六章时间序列挖掘聚类课件HierarchicalClusteringWecanobjectivelystatethatSAXissuperior,sinceitcorrectlyassignseachclasstoitsownsubtree.数据类别事先已知：decreasingtrend,upwardshiftandnormalclassesHierarchicalClusteringWecanClusteringHierarchicalClusteringComputepairwisedistance,mergesimilarclustersbottom-upComparedwithEuclidean,IMPACTS,andSDAPartitionalClusteringK-meansOptimizetheobjectivefunctionbyminimizingthesumofsquaredintra-clustererrorsComparedwithRawdata比层次聚类具有更好的可伸缩性ClusteringHierarchicalClusterPartitional(K-means)ClusteringWorkingwithanapproximationofthedatagivesbetterresultsthanworkingwiththeoriginaldata.Ithasbeenshownthatinitializingtheclusterscentersonalowdimensionapproximationofthedatacanimprovethequality,thisiswhatclusteringwithSAXimplicitlydoes.Acomparisonofthek-meansclusteringalgorithmusingSAXandtherawdata.ThedatasetwasSpaceShuttletelemetry,1,000subsequencesoflength512.Surprisingly,workingwiththesymbolicapproximationproducesbetterresultsthanworkingwiththeoriginaldataPartitional(K-means)Clusteri动态时间序列聚类TimeSeriesEpenthesis:ClusteringTimeSeriesStreamsRequiresIgnoringSomeData动态时间序列聚类TimeSeriesEpenthesis动态时间序列聚类所谓流数据，是指按照一定的时间顺序，以较快的速度连续到达的数据序列，也称为动态时间序列。流数据聚类的难点在于：数据流随着时间的推移近似地等效于一个无限的数据集合，因此对流数据的随机访问几乎是不可能实现的，因此流数据聚类通常都要求“一次性扫描数据”。流数据聚类算法首先对每个新到达的数据进行访问处理，之后数据即被放入随机访问代价较高的存储设备，或者直接被丢弃。流数据聚类算法通常会维护一个“概要数据结构”，用来保存数据的摘要信息，当需要输出聚类结果时，以概要数据结构中保存的信息作为目标对象集合，生成所需要的结果。动态时间序列聚类所谓流数据，是指按照一定的时间顺序，以较快的流数据实例商业领域中，大型仓储超市的交易数据。超市的数据中心每天收到各个分店大量的交易记录，包括顾客购买物品，消费金额等属性，按照时间顺序排列。电信行业中，移动公司可采集到用户的通话记录，包括主叫号码，被叫号码，通话时间，收费金额等若干属性。大量的通话记录以时间顺序排列，汇集到移动公司的数据中心，也可以被抽象为是一种“流”。医疗行业中，使用生理信号采集仪器对患者进行监控，心跳，脉搏，血压等一系列生理信号实时地传送到分析模块，从中推测出患者每一时段的健康状况。工业生产中，一些大型设备的安全检测仪器每时每刻将设备的各项运转参数采集出来，作为数据信号进行分析处理。流数据实例商业领域中，大型仓储超市的交易数据。超市的数据中心流数据特点首先，数据量十分庞大，这些数据随着时间的增长数量急剧上升，如沃尔玛超市的日交易次数可达数十万。其次，这些数据均按照时间顺序连续到达。另外，数据流速很快，以广东省移动公司的通话记录为例，高峰时间每小时可达数千条。流数据特点首先，数据量十分庞大，这些数据随着时间的增长数量急流数据聚类问题模型假设流数据由一系列按照时间顺序连续到达的数据点X1,...,Xi...构成，其中，每个数据点拥有d个属性，用d维向量的形式来表示：那么流数据聚类问题，就是将数据流中的某个特定的子对象集合{X1,X2,...,XN}划分成k个簇区间(每个簇用其均值中心点来表示),使目标函数值:达到最小。其中Ci是Xi所在簇的中心点，D(Xi,Ci)表示两个数据点之间