第六章时间序列挖掘聚类

时间序列挖掘●聚类山西财经大学信息管理学院常新功第六章目录•聚类的概念•聚类算法的评价标准•时间序列聚类概述•k-mediods时间序列聚类•基于LB_Hust距离的时间序列聚类•基于SAX表示的聚类聚类的概念•聚类（Clustering）是数据挖掘领域中的一个重要分支。所谓聚类，是指将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过程。•聚类是依据事物的某些属性将其聚集成类，使类间相似性尽量小，类内相似性尽量大。•2015.4.19，的深圳举办的新一代信息技术产业发展高峰论坛上，中国工程院院士李德毅在发言中指出，尽管目前对于大数据的认知存在挑战，但聚类将会成为大数据认知的突破口。通过大数据聚类即时发现价值，要充分认识大数据中的不确定性和价值的隐蔽性。聚类算法的评价标准•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）ifS0,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-wij+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([[QU].*[Q-U];[QL].*[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-wij+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次距离。应用---股票数据聚类•股票数据作为典型的时间序列数据，被众多时间序列挖掘方法作为实验性数据。典型的股票行情原始数据包括股票的开盘价、最高价、最低价