时间序列挖掘聚类

1、时间序列挖掘聚类山西财经大学信息管理学院常新功山西财经大学信息管理学院常新功第六章目 录 聚类的概念 聚类算法的评价标准 时间序列聚类概述 k-mediods时间序列聚类 基于 LB_Hust 距离的时间序列聚类 基于SAX表示的聚类聚类的概念 聚类（Clustering）是数据挖掘领域中的一个重要分支。所谓聚类，是指将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过程 。 聚类是依据事物的某些属性将其聚集成类，使类间相似性尽量小，类内相似性尽量大。 2015.4.19，的深圳举办的新一代信息技术产业发展高峰论坛上，中国工程院院士李德毅在发言中指出，尽管目前对于大数据的认知存在挑战，但

2、聚类将会成为大数据认知的突破口。通过大数据聚类即时发现价值，要充分认识大数据中的不确定性和价值的隐蔽性。 聚类算法的评价标准 1) 可伸缩性：可伸缩性考察聚类算法对于目标对象集合的规模以及目标集合潜在的模式数量的适应性。 2) 处理不同类型属性的能力：除了通常处理的数值型数据，应用当中可能要求聚类其它类型的数据，如：二元类型，分类/标称类型，序数型，时间序列、图数据或者不同数据类型的混合。 3) 发现任意形状的聚类：许多聚类算法基于欧几里德距离或者曼哈顿距离度量来决定聚类。基于这种距离度量的算法趋向于发现具有相近尺度和密度的球状簇。但是一个簇可能是任意形状的，提出能发现任意形状簇的算法是很重要

3、的。 4)交互可视化：高维数据和复杂对象常常使可视化变得困难，而交互性则使算法与人结合有利于提高聚类的质量。聚类算法的评价标准 5) 最小化用于决定输入参数的领域知识和数据记录敏感性：一方面要求降低算法对输入参数的敏感程度，另一方面要求输入记录顺序对算法的结果影响小。要求用户输入参数不仅会加重用户的负担，也使得聚类的质量难以控制。 6) 处理噪声数据的能力：绝大多数现实世界中的数据库都包含了孤立点，空缺，未知或者错误的数据。一些聚类算法对于这样的数据敏感，导致聚类质量不高。 7) 高维性：许多聚类算法只擅长处理低维数据。在高维空间中聚类数据对象是一个挑战，特别是在数据有可能非常稀疏和偏斜时。

4、8) 可解释性和可用性：知识发现过程中，聚类结果总是需要表现为一定的知识，这就要求聚类结果可解释，易理解。时间序列聚类概述 时间序列聚类是时间序列数据挖掘的一个非常基础时间序列聚类是时间序列数据挖掘的一个非常基础且非常活跃的研究方向，被广泛应用于包括模式识且非常活跃的研究方向，被广泛应用于包括模式识别、数据分析、图像处理、市场分析等各个领域：别、数据分析、图像处理、市场分析等各个领域：零售数据的季节模式聚类、国家能源消耗聚类分析、零售数据的季节模式聚类、国家能源消耗聚类分析、心电图心电图ECGECG信号聚类分析、股票序列的模式发现以信号聚类分析、股票序列的模式发现以及个人收入数据的聚类等等及个

5、人收入数据的聚类等等(Valk and Pinheiro, (Valk and Pinheiro, 2012, Rodrigues et al., 2008, Costa Santos 2012, Rodrigues et al., 2008, Costa Santos et al., 2006, Berkhin, 2006, Warren Liaoet al., 2006, Berkhin, 2006, Warren Liao，2005, Bagnall and Janacek, 2005)2005, Bagnall and Janacek, 2005)。国内外许多。国内外许多研究者提出了很

6、多时间序列聚类方法，这些方法大研究者提出了很多时间序列聚类方法，这些方法大致可以分为三种：致可以分为三种：基于原始序列基于原始序列、基于特征数据基于特征数据和和基于模型参数基于模型参数(Warren Liao, 2005)(Warren Liao, 2005)。基于原始序列数据的时间序列聚类 直接运行在原始时间序列上的聚类称为基于原始数直接运行在原始时间序列上的聚类称为基于原始数据的聚类据的聚类(Zhang et al., 2011, Rodrigues et al., (Zhang et al., 2011, Rodrigues et al., 2008, Warren Liao, 2005

7、)2008, Warren Liao, 2005)。 但在实践中，由于但在实践中，由于时间序列的高维特点，会导致大时间序列的高维特点，会导致大部分的聚类方法失效部分的聚类方法失效，具体表现为：，具体表现为： (1)(1)时间序列被看成高维空间中的一个点，所以数据分布时间序列被看成高维空间中的一个点，所以数据分布会呈现会呈现稀疏性稀疏性，从而导致欧氏距离不能正确测度对象间的，从而导致欧氏距离不能正确测度对象间的相似程度相似程度(Wang et al., 2005, Domeniconi et al., (Wang et al., 2005, Domeniconi et al., 2004)200

8、4)； (2)(2)多数算法的性能受参数设置的影响，在缺乏背景知识多数算法的性能受参数设置的影响，在缺乏背景知识时，用户可以根据反馈的算法结果精调参数，但时，用户可以根据反馈的算法结果精调参数，但高维数据高维数据造成聚类结果无法可视化造成聚类结果无法可视化，使得用户很难判断聚类结果的，使得用户很难判断聚类结果的质量，所以很难合理设置参数（质量，所以很难合理设置参数（Jain, 2010, Chen, 2007, Jain, 2010, Chen, 2007, Lin et al., 2004Lin et al., 2004，Ding and He, 2004)Ding and He, 2004

9、)。基于特征数据的时间序列聚类 基于特征的表示方法是基于特征的表示方法是把原始时间序列转换到一个把原始时间序列转换到一个低维的特征空间，然后用传统的聚类方法对特征向低维的特征空间，然后用传统的聚类方法对特征向量进行聚类量进行聚类(Yang et al., 2009, Xiaozhe et al., (Yang et al., 2009, Xiaozhe et al., 2007,Keogh et al., 2007, Chen, 2007, Zhang et 2007,Keogh et al., 2007, Chen, 2007, Zhang et al., 2006, Wang et al.

10、, 2006al., 2006, Wang et al., 2006，Costa Santos et Costa Santos et al., 2006al., 2006，Wang et al., 2005Wang et al., 2005，Bagnall and Bagnall and Janacek, 2005Janacek, 2005，Domeniconi et al., 2004)Domeniconi et al., 2004)。 由于基于特征的聚类方法中提取的特征来自序列本由于基于特征的聚类方法中提取的特征来自序列本身，且具有特定的含义，所以身，且具有特定的含义，所以该聚类方法不仅实

11、现该聚类方法不仅实现对序列的降维，又使得聚类结果具有可解释性对序列的降维，又使得聚类结果具有可解释性。这。这里，常用的传统的聚类算法有如下几种：划分聚类、里，常用的传统的聚类算法有如下几种：划分聚类、层次聚类和密度聚类等等层次聚类和密度聚类等等(Jain, 2010(Jain, 2010，Chawla and Chawla and Gionis, 2013, Rodrigues et al., 2008Gionis, 2013, Rodrigues et al., 2008，Labini, Labini, 2008, Schikuta, 1996, Kriegel et al., 2011)2

12、008, Schikuta, 1996, Kriegel et al., 2011)。基于模型的时间序列聚类 基于模型的聚类的基本思想是把原始时间序列转换基于模型的聚类的基本思想是把原始时间序列转换成模型的几个参数，比如成模型的几个参数，比如ARAR模型或模型或HMMHMM模型等，然模型等，然后用模型参数进行聚类后用模型参数进行聚类(Jie and Qiang, 2005(Jie and Qiang, 2005，Camastra and Verri, 2005, Xiong and Yeung, Camastra and Verri, 2005, Xiong and Yeung, 2004,

13、Panuccio et al., 2002)2004, Panuccio et al., 2002)。这种方法的不足这种方法的不足之处在于需要对数据的分布进行预先假设，此外，之处在于需要对数据的分布进行预先假设，此外，对参数的聚类结果无法进行解释，使得聚类缺乏可对参数的聚类结果无法进行解释，使得聚类缺乏可理解性。理解性。小 结 现有时间序列聚类方法大致可分成：基于原始序列、基于特征值和基于模型参数三种。 基于原始序列的聚类方法由于“维灾难”很难产生较好的聚类效果，而基于模型参数的方法由于需要对数据做预先假设也使得应用受到限制，基于特征值的聚类方法是最有前景的时间序列聚类算法。静态时间序列聚类

14、k-medoids时间序列聚类 基于 LB_Hust 距离的时间序列数据聚类 基于SAX表示的聚类k-mediods时间序列聚类1、k-中心点聚类基本原理：中心点聚类基本原理：k-均值的缺点：对离群点敏感均值的缺点：对离群点敏感k-中心点：挑选实际对象来代表簇，每个中心点：挑选实际对象来代表簇，每个簇使用一个代表对象。簇使用一个代表对象。实现：围绕中心点划分（实现：围绕中心点划分（Partitioning Around Medoids, PAM)算法算法算法算法:k-中心点。中心点。PAM输入：输入： k：结果簇的个数：结果簇的个数 D：包含：包含n个对象的数据集合个对象的数据集合输出：输出：

15、 k个簇的集合个簇的集合k-mediods时间序列聚类方法：方法： （1）从）从D中随机选择中随机选择k个对象作为初始的代表对象或种子个对象作为初始的代表对象或种子 （2）repeat （3）将每个剩余的对象分配到最近的代表对象所代表的簇）将每个剩余的对象分配到最近的代表对象所代表的簇 （4）随机地选择一个非代表对象）随机地选择一个非代表对象Orandom （5）计算用）计算用Orandom代替代表对象代替代表对象Oj的总代价的总代价S（代价函数（代价函数就是计算绝对误差值的差）就是计算绝对误差值的差） （6）if S U.* Q-U; Q L.* L-Q.2); LB_Hust 距离-对LB

16、_Keogh距离的改进 针对针对 LB_KeoghLB_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 距离是对称的。即距

17、离是对称的。即 LB_Hust (X,Y) =LB_Hust (Y,X)。这可以减少距离计算的次数。这可以减少距离计算的次数。 性质性质2：在：在 LB_Hust 距离计算方式下，时间复杂度距离计算方式下，时间复杂度由传统的由传统的 DTW 距离计算的距离计算的 O(nm)缩减到缩减到 O(n)。基于 LB_Hust 距离的时间序列聚类 算法流程：算法流程： 1) 初始状态下所有有时间序列数据自成一簇，每条时间初始状态下所有有时间序列数据自成一簇，每条时间序列数据为各自的簇中心，循环序列数据为各自的簇中心，循环 2）到）到 4）。）。 2) 根据时间序列数据上下界曲线形成方法求取当前簇中根据时

18、间序列数据上下界曲线形成方法求取当前簇中心的上下界序列心的上下界序列 Us和和 Ls。 3) 计算两两簇之间的距离，记录具有最小距离的两个簇，计算两两簇之间的距离，记录具有最小距离的两个簇，将两个簇归并，根据归并算法更新聚类中心。将两个簇归并，根据归并算法更新聚类中心。 4) 若当前聚类簇数达到若当前聚类簇数达到 K，则终止，否则转到，则终止，否则转到 2)。 分析上述算法，存在的两个关键的函数是计算两个序列分析上述算法，存在的两个关键的函数是计算两个序列的的 LB_Hust 距离和求取新的簇中心两个函数。距离和求取新的簇中心两个函数。基于 LB_Hust 距离矩阵的层次聚类 基于距离矩阵的层

19、次聚类算法是以牺牲空间换取时间的基于距离矩阵的层次聚类算法是以牺牲空间换取时间的算法，存放算法，存放 n 条记录两两之间的距离，在距离函数计算条记录两两之间的距离，在距离函数计算具有对称性的情况下，实际的矩阵只需存放上三角或下具有对称性的情况下，实际的矩阵只需存放上三角或下三角三角 n*(n+1)/2 个数据。这也是应用个数据。这也是应用 LB_Hust 距离计算距离计算函数的一个重要原因。函数的一个重要原因。 输入：时间序列数据库：输入：时间序列数据库：TSDB； 允许的弯曲路径时间窗：允许的弯曲路径时间窗：w； 最大的簇数：最大的簇数：K； 输出：输出：K 个簇：个簇：C1， C2、，、，

20、 CK；基于 LB_Hust 距离矩阵的层次聚类 算法流程：算法流程： 1) 初始状态下所有时间序列数据自成一簇，每条时间序列初始状态下所有时间序列数据自成一簇，每条时间序列数据为各自的簇中心，初始化距离矩阵，计算任意两条时数据为各自的簇中心，初始化距离矩阵，计算任意两条时间序列数据间的距离，循环间序列数据间的距离，循环 2）到）到 5）。）。 2) 找到距离矩阵中的最小距离对应的两个簇，合并，形成找到距离矩阵中的最小距离对应的两个簇，合并，形成新的簇中心。新的簇中心。 3) 根据时间序列数据上下界曲线形成方法求取当前簇中心根据时间序列数据上下界曲线形成方法求取当前簇中心的上下界索引序列的上下

21、界索引序列 Us、Ls。 4) 重新计算当前簇中心和其余簇的距离，更新距离矩阵。重新计算当前簇中心和其余簇的距离，更新距离矩阵。 5) 若当前聚类簇数达到若当前聚类簇数达到 K，则终止，否则转到，则终止，否则转到 2)。 对于上述采用距离矩阵的层次聚类，相比前面算法，每一对于上述采用距离矩阵的层次聚类，相比前面算法，每一层合并时，距离计算次数为层合并时，距离计算次数为c(n,2)次，其中次，其中 n 表示当前层中表示当前层中的簇数，时间复杂度为的簇数，时间复杂度为 o(n2)，采用距离矩阵方法则每次仅，采用距离矩阵方法则每次仅需计算需计算 n 次距离。次距离。应用应用-股票数据聚类股票数据聚类

22、 股票数据作为典型的时间序列数据，被众多时间股票数据作为典型的时间序列数据，被众多时间序列挖掘方法作为实验性数据。典型的股票行情序列挖掘方法作为实验性数据。典型的股票行情原始数据包括股票的开盘价、最高价、最低价、原始数据包括股票的开盘价、最高价、最低价、收盘价、成交量、成交金额等，所有属性的值对收盘价、成交量、成交金额等，所有属性的值对应着一个特定时刻，在固定时间段内形成了典型应着一个特定时刻，在固定时间段内形成了典型的时间序列数据。的时间序列数据。 对于多支股票的聚类是从控股公司间的经营状况、对于多支股票的聚类是从控股公司间的经营状况、经营手段及外界影响因素的相似程度进行聚类。经营手段及外界

23、影响因素的相似程度进行聚类。通过对多支股票的聚类，可以发现股票运动规律通过对多支股票的聚类，可以发现股票运动规律相似的企业，对中长期股票投资者选股提供一些相似的企业，对中长期股票投资者选股提供一些参考。参考。股票数据聚类：数据准备股票数据聚类：数据准备 采用搜狐财经网采用搜狐财经网(http:/ 29 29 支股票作为实验数据：宝钢股份、包钢股份、上支股票作为实验数据：宝钢股份、包钢股份、上海电力、招商轮船、中国石油海电力、招商轮船、中国石油 、中国银行、中海、中国银行、中海油服、武钢股份、东湖高新、万东医疗、林海股油服、武钢股份、东湖高新、万东医疗、林海股份、中视传媒等。在数据库中，存储股票

24、的名称份、中视传媒等。在数据库中，存储股票的名称采用字母代号表示，将采用字母代号表示，将 29 29 支股票对应到支股票对应到 AA3 AA3 的的 29 29 个字母串。个字母串。 抽取从抽取从 20102010年年3 3月份到月份到20102010年五月份的股票历史年五月份的股票历史行情数据，将其中的每日收盘价作为实验数据。行情数据，将其中的每日收盘价作为实验数据。在提取的数据中发现，股票数据存在如下两个特在提取的数据中发现，股票数据存在如下两个特点：点：一、由于股市的休市，股票数据存在空值一、由于股市的休市，股票数据存在空值；二、股票之间的收盘价存在很大差异二、股票之间的收盘价存在很大差

25、异。股票数据聚类：数据准备股票数据聚类：数据准备 股票数据普遍存在空值，主要是基于两种情况：股票数据普遍存在空值，主要是基于两种情况：一、正常的股市休市。二、个别控股公司由于内一、正常的股市休市。二、个别控股公司由于内部整合或者公司内部事件出现停开。部整合或者公司内部事件出现停开。 每支股票数据在休市时都是空值，因此可采用直每支股票数据在休市时都是空值，因此可采用直接删除的方法不会影响到时间序列的时间对等性。接删除的方法不会影响到时间序列的时间对等性。 针对公司内部事件引起的空值采取填补处理。填针对公司内部事件引起的空值采取填补处理。填补数据根据线性化函数取得，对每个空值，以空补数据根据线性化

26、函数取得，对每个空值，以空值上下非空数据为端点得到一次线性化函数，通值上下非空数据为端点得到一次线性化函数，通过线性化函数可以取得空值对应时间点的股价。过线性化函数可以取得空值对应时间点的股价。股票数据聚类：数据准备股票数据聚类：数据准备 采用线性化函数进行填补处理是基于两点考虑：采用线性化函数进行填补处理是基于两点考虑： 首先，基于对首先，基于对 LB_Hust LB_Hust 距离计算的过程，对于时距离计算的过程，对于时间序列曲线，趋势的变动和时间序列的连续能够间序列曲线，趋势的变动和时间序列的连续能够增强相似性比较效果，所以，对空值数据进行线增强相似性比较效果，所以，对空值数据进行线性的

27、平滑处理可以更好地应用性的平滑处理可以更好地应用 LB_Hust LB_Hust 距离计算距离计算方法。方法。 其次，从实际意义来看，在空值出现前的阶段和其次，从实际意义来看，在空值出现前的阶段和空值结束后，两者股价一般不同，可见在股价为空值结束后，两者股价一般不同，可见在股价为空值的阶段，实际上隐藏着一些影响股价变动的空值的阶段，实际上隐藏着一些影响股价变动的因素发生着作用，通过线性化函数，将期间出现因素发生着作用，通过线性化函数，将期间出现的变化过程连续的表达出来，函数中的斜率保持的变化过程连续的表达出来，函数中的斜率保持了股价在空值出现阶段的趋势变动变化规律，通了股价在空值出现阶段的趋势

28、变动变化规律，通过这种填补方法使得股价波动曲线更连续和平滑过这种填补方法使得股价波动曲线更连续和平滑股票数据聚类：数据的归一化股票数据聚类：数据的归一化 除了空值问题，股票数据另一典型的特点就是不除了空值问题，股票数据另一典型的特点就是不同公司的股价在数值上差异很大。同公司的股价在数值上差异很大。股票数据聚类：数据的归一化股票数据聚类：数据的归一化 针对股票数据间的股价差距大的问题，采用归一针对股票数据间的股价差距大的问题，采用归一化处理，归一化处理主要解决比较数据间量纲不化处理，归一化处理主要解决比较数据间量纲不统一的问题，在对股票进行聚类分析中，股票的统一的问题，在对股票进行聚类分析中，股

29、票的相似性集中于股价变化趋势的相似性，而非股价相似性集中于股价变化趋势的相似性，而非股价之间的相似性，所以采用以下公式之间的相似性，所以采用以下公式 对数据进行归对数据进行归一化处理。一化处理。minmaxminiixxxxx股票数据聚类：聚类结果股票数据聚类：聚类结果 运行层次聚类算法时初始设定聚类簇数为运行层次聚类算法时初始设定聚类簇数为4个，同个，同时设定时间弯折窗口时设定时间弯折窗口w为为3。股票数据聚类：聚类结果股票数据聚类：聚类结果 运行层次聚类算法时初始设定聚类簇数为运行层次聚类算法时初始设定聚类簇数为4个，同个，同时设定时间弯折窗口时设定时间弯折窗口w为为3。股票数据聚类：聚类

30、结果股票数据聚类：聚类结果 运行层次聚类算法时初始设定聚类簇数为运行层次聚类算法时初始设定聚类簇数为4个，同个，同时设定时间弯折窗口时设定时间弯折窗口w为为3。股票数据聚类：聚类结果股票数据聚类：聚类结果 运行层次聚类算法时初始设定聚类簇数为运行层次聚类算法时初始设定聚类簇数为4个，同个，同时设定时间弯折窗口时设定时间弯折窗口w为为3。基于SAX表示的聚类 Hierarchical Clustering Compute pairwise distance, merge similar clusters bottom-up Compared with Euclidean, IMPACTS, an

31、d SDA 基于基于SAX表示的距离表示的距离PAA distance lower-bounds the Euclidean Distance 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 QniiicqCQD12,Euclidean DistancewiiiwncqCQDR12),(wiiiwncqdistCQMINDIST12) ,(),(dist() can be implemented

32、 using a table lookup.Hierarchical Clustering E u c lid e a n IM P A C T S ( a lp h a b e t= 8 ) S D A S A X We can objectively state that SAX is superior, since it correctly assigns each class to its own subtree. 数据类别事先已知：数据类别事先已知：decreasing trend, upward shift and normal classesClustering Hierarch

33、ical Clustering Compute pairwise distance, merge similar clusters bottom-up Compared with Euclidean, IMPACTS, and SDA Partitional Clustering K-means Optimize the objective function by minimizing the sum of squared intra-cluster errors Compared with Raw data 比层次聚类具有更好的可伸缩性比层次聚类具有更好的可伸缩性Partitional (K

34、-means) ClusteringWorking with an approximation of the data gives better results than working with the original data. It has been shown that initializing the clusters centers on a low dimension approximation of the data can improve the quality, this is what clustering with SAX implicitly does. Numbe

35、r of Iterations 220000 225000 230000 235000 240000 245000 250000 255000 260000 265000 1 2 3 4 5 6 7 8 9 10 11 Raw data Our Symbolic Approach Objective Function Raw data SAX A comparison of the k-means clustering algorithm usingSAX and the raw data. The dataset was Space Shuttle telemetry,1,000 subse

36、quences of length 512. Surprisingly, working with thesymbolic approximation produces better results than working with theoriginal data动态时间序列聚类 Time Series Epenthesis: Clustering Time Series Streams Requires Ignoring Some Data动态时间序列聚类 所谓流数据，是指按照一定的时间顺序，以较快的速所谓流数据，是指按照一定的时间顺序，以较快的速度连续到达的数据序列，也称为动态时间序列

37、。度连续到达的数据序列，也称为动态时间序列。 流数据聚类的难点在于：数据流随着时间的推移近似流数据聚类的难点在于：数据流随着时间的推移近似地等效于一个地等效于一个无限无限的数据集合，因此对流数据的随机的数据集合，因此对流数据的随机访问几乎是不可能实现的，因此流数据聚类通常都要访问几乎是不可能实现的，因此流数据聚类通常都要求求“一次性扫描数据一次性扫描数据”。流数据聚类算法首先对每个。流数据聚类算法首先对每个新到达的数据进行访问处理，之后数据即被放入随机新到达的数据进行访问处理，之后数据即被放入随机访问代价较高的存储设备，或者直接被丢弃。访问代价较高的存储设备，或者直接被丢弃。 流数据聚类算法通

38、常会维护一个流数据聚类算法通常会维护一个“概要数据结构概要数据结构”，用来保存数据的摘要信息，当需要输出聚类结果时，用来保存数据的摘要信息，当需要输出聚类结果时，以概要数据结构中保存的信息作为目标对象集合，生以概要数据结构中保存的信息作为目标对象集合，生成所需要的结果。成所需要的结果。流数据实例 商业领域中，大型仓储超市的交易数据。超市的数据商业领域中，大型仓储超市的交易数据。超市的数据中心每天收到各个分店大量的交易记录，包括顾客购中心每天收到各个分店大量的交易记录，包括顾客购买物品，消费金额等属性，按照时间顺序排列。买物品，消费金额等属性，按照时间顺序排列。 电信行业中，移动公司可采集到用户

39、的通话记录，包电信行业中，移动公司可采集到用户的通话记录，包括主叫号码，被叫号码，通话时间，收费金额等若干括主叫号码，被叫号码，通话时间，收费金额等若干属性。大量的通话记录以时间顺序排列，汇集到移动属性。大量的通话记录以时间顺序排列，汇集到移动公司的数据中心，也可以被抽象为是一种公司的数据中心，也可以被抽象为是一种“流流”。 医疗行业中，使用生理信号采集仪器对患者进行监控医疗行业中，使用生理信号采集仪器对患者进行监控，心跳，脉搏，血压等一系列生理信号实时地传送到，心跳，脉搏，血压等一系列生理信号实时地传送到分析模块，从中推测出患者每一时段的健康状况。分析模块，从中推测出患者每一时段的健康状况。

40、 工业生产中，一些大型设备的安全检测仪器每时每刻工业生产中，一些大型设备的安全检测仪器每时每刻将设备的各项运转参数采集出来，作为数据信号进行将设备的各项运转参数采集出来，作为数据信号进行分析处理。分析处理。流数据特点 首先，首先，数据量十分庞大数据量十分庞大，这，这些数据随着时间的增长数量些数据随着时间的增长数量急剧上升，如沃尔玛超市的急剧上升，如沃尔玛超市的日交易次数可达数十万。日交易次数可达数十万。 其次，这些数据均其次，这些数据均按照时间按照时间顺序连续到达顺序连续到达。 另外，另外，数据流速很快数据流速很快，以广，以广东省移动公司的通话记录为东省移动公司的通话记录为例，高峰时间每小时可

41、达数例，高峰时间每小时可达数千条。千条。流数据聚类问题模型 假设流数据由一系列按照时间顺序连续到达的数据假设流数据由一系列按照时间顺序连续到达的数据点点 X X1 1,.,X,.,Xi i.构成，其中，每个数据点拥有构成，其中，每个数据点拥有 d d 个个属性，用属性，用d d 维向量的形式来表示：维向量的形式来表示： 那么流数据聚类问题，就是将数据流中的某个特定那么流数据聚类问题，就是将数据流中的某个特定的子对象集合的子对象集合XX1 1,X,X2 2,.,X,.,XN N 划分成划分成 k k 个簇区间个簇区间( (每每个簇用其均值中心点来表示个簇用其均值中心点来表示),),使目标函数值使

42、目标函数值: : 达到最小。其中达到最小。其中C Ci i是是X Xi i所在簇的中心点，所在簇的中心点，D(XD(Xi i,C,Ci i) )表表示两个数据点之间的距离。示两个数据点之间的距离。12X(,.,)diiiixxx21(,)NiiiDXC流数据聚类问题模型 对该问题模型，有几点需要说明：对该问题模型，有几点需要说明： 1)1)目标集合中数据对象的个数目标集合中数据对象的个数 N N 通常在数量级上远通常在数量级上远远大于传统算法中的数据集合，通常无法将全部数远大于传统算法中的数据集合，通常无法将全部数据读入内存进行分析，因此难以利用传统的聚类算据读入内存进行分析，因此难以利用传统

43、的聚类算法解决这类问题。法解决这类问题。 2)2)在流数据聚类问题中，数据通常只能按照它们到在流数据聚类问题中，数据通常只能按照它们到达的顺序访问，此后，数据即被存放于外存或丢弃达的顺序访问，此后，数据即被存放于外存或丢弃，内存中只能保存已访问数据的概要信息。也就是，内存中只能保存已访问数据的概要信息。也就是说，流数据算法为了避免高昂的系统开销应该尽可说，流数据算法为了避免高昂的系统开销应该尽可能少地重复访问数据。事实上，能少地重复访问数据。事实上，“一次扫描数据一次扫描数据”已经成为几乎所有流数据算法都需要实现的目标。已经成为几乎所有流数据算法都需要实现的目标。流数据聚类问题模型 3)3)流

44、数据算法的目标集合是数据流中截取的某一个流数据算法的目标集合是数据流中截取的某一个时间段时间段( (时间窗时间窗) )的对象集合。定义一个时间窗需要的对象集合。定义一个时间窗需要两个重要的输入参数：起始时刻两个重要的输入参数：起始时刻 t t 和时间窗口宽度和时间窗口宽度 h h，一个时间窗口可用，一个时间窗口可用 W(t, h)W(t, h)来表示。算法的目标来表示。算法的目标集合即由落入窗口集合即由落入窗口W(t, h)W(t, h)的数据对象组成。的数据对象组成。 4)4)在流数据算法中，任何一个时刻的较小的误差，在流数据算法中，任何一个时刻的较小的误差，都有可能随着时间的推移而急速扩大

45、，最终造成错都有可能随着时间的推移而急速扩大，最终造成错误或质量较低的算法结果。因此，在每一个阶段都误或质量较低的算法结果。因此，在每一个阶段都要将误差严格控制在一个较小的区间之内。要将误差严格控制在一个较小的区间之内。 5)5)同时，算法对时间效率的要求非常高，当需要在同时，算法对时间效率的要求非常高，当需要在某一个特定时刻输出聚类结果时，如果处理过程的某一个特定时刻输出聚类结果时，如果处理过程的时间开销过大，则有可能会造成新到数据的遗漏或时间开销过大，则有可能会造成新到数据的遗漏或丢失，这种信息缺损随着数据流的不断进行而加剧丢失，这种信息缺损随着数据流的不断进行而加剧。早期的流数据聚类 早

46、期的流数据聚类努力将数据流的动态特性转化早期的流数据聚类努力将数据流的动态特性转化为传统的静态模式，从而能够应用成熟的传统方为传统的静态模式，从而能够应用成熟的传统方法解决问题。在这一阶段，算法研究的重点是改法解决问题。在这一阶段，算法研究的重点是改进传统算法的性能，使之能够适应流数据的动态进传统算法的性能，使之能够适应流数据的动态特性。特性。 Small-Space Small-Space 算法正是这类算法的典型代表。算法正是这类算法的典型代表。Small-Space 算法 输入：按时间顺序到达的流数据序列输入：按时间顺序到达的流数据序列 输出：输出：k个聚类中心点个聚类中心点 算法过程：算

47、法过程： 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)

48、输出聚类结果时，对当前所有中心点进行聚类，输出聚类结果时，对当前所有中心点进行聚类，得到最终的得到最终的 k个聚类中心。个聚类中心。Small-Space 算法的问题 算法需要累积数据点，当数据量达到一定限度时进算法需要累积数据点，当数据量达到一定限度时进行统一处理，而通常处理算法较为复杂，造成了数行统一处理，而通常处理算法较为复杂，造成了数据流在处理节点上的延迟。据流在处理节点上的延迟。 另一方面，在累积数据点的过程中，算法处于空闲另一方面，在累积数据点的过程中，算法处于空闲状态，在一定程度上降低了算法的效率，增加了时状态，在一定程度上降低了算法的效率，增加了时间开销。间开销。双层流数据聚类

49、 J. Han 提出双层结构算法提出双层结构算法 CluStream12 双层聚类算法将处理工作分为两个层面：在线层双层聚类算法将处理工作分为两个层面：在线层算法负责对数据进行粗糙但快速的处理，并负责算法负责对数据进行粗糙但快速的处理，并负责保存中间结果；离线层算法在中间结果的基础上保存中间结果；离线层算法在中间结果的基础上进行精确而复杂的分析，此时目标集合已成为静进行精确而复杂的分析，此时目标集合已成为静态集合，因此通常情况下不必考虑数据流速的影态集合，因此通常情况下不必考虑数据流速的影响，并得到最终结果。响，并得到最终结果。CluStream基本思想 在线层维护一系列的在线层维护一系列的“微簇微簇”(Micro-Cluster)作为作为保存数据概要信息的数据结构。每个微簇用五元组保存数据概要信息的数据结构。每个微簇用五元组(SS，LS，ST，LT，N)来表示，其中来表示，其中 N 为微簇中包为微簇中包含的数据点个数，若数据维度为含的数据点个数，若数据维度为 d，则，则 LS，与，与 SS 均为均为 d