多元时序模糊聚类分段挖掘算法

第36卷第2期 北京科技大学学报 Vol.36 No.2 2014年2月 Journal of University of Science and Technology Beijing Feb.2014 多元时序模糊聚类分段挖掘算法 于重重12四，吴子琚”，谭励”，涂序彦，杨扬”，王璐” 1)北京工商大学计算机与信息工程学院，北京1000482)北京科技大学计算机与通信工程学院，北京100083 ☒通信作者，E-mail:chongzhy@vip.sina.com 摘要工业监控系统所采集到的多元时间序列在利用数据挖掘技术获取内部存在的未知模式的过程中，经常会出现原始 数据庞杂、分段结果重复、交集过多和界限不清晰等问题，导致含有突变变量或数据间相关性差的数据集进行模式挖掘结果 不理想.针对上述问题，本文提出了一种新的多元时序模糊聚类分段挖掘算法.实验结果表明，该算法克服了Gath-Geva算法 聚类精度易受初始值影响的不足，能够较好地反映出原始数据中潜在的过程变化，从而有效地处理时间序列的分段问题并得 到理想的挖掘结果 关键词多元系统：时间序列：聚类算法：数据挖掘：主成分分析 分类号TP391 Multivariate time series fuzzy clustering segmentation mining algorithm YU Chong-chong'2a,WU Zi-jun',TAN Li”,TUXu-yan2》,YANG Yang,WANG Lu” 1)School of Computer&Information Engineering,Beijing Technology and Business University,Beijing 100048,China 2)School of Computer and Communication Engineering,University of Science and Technology Beijing,Beijing 100083,China Corresponding author,E-mail:chongzhy@vip.sina.com ABSTRACT Multivariate time series collected by industrial monitoring systems often have problems such as numerous raw data, repeated segmentation results,redundant intersections and blurry boundaries in the process of using data mining technologies to acquire internal existing unknown patterns,leading to unsatisfied mining results when the dataset involves mutation variables or inferior relevance among the data.To resolve these problems,this article introduces a new multiple time sequence clustering algorithm.Experi- mental results show that this algorithm can overcome the shortage that the accuracy of clustering is often affected by initial values in the Gath-Geva algorithm.It can exhibit the potential variation of raw data and thus efficiently deal with segmentation in multivariate time series to get ideal mining results. KEY WORDS multivariable systems:time series;clustering algorithms;data mining:principal component analysis 时间序列是指按照时间顺序取得的一系列的观 目前对于子序列的处理主要采用聚类方法，而在工 测值四.在工业监控过程中，观测值往往是多变量 业领域中广泛使用的聚类算法为均值法四，虽然其 相互影响和相互联系的，并且每个变量均为时间序 聚类过程比较简单，效率较高，但在使用中存在需要 列数据，因此为了寻求原始数据中所蕴含的未知模 事先确定聚类数目，容易陷入局部最优等问题.本 式，预测未来的变化趋势，多元时间序列作为一种数 文提出了一种以Gath-Geva聚类算法为基础的多 据对象逐渐受到人们的重视.由于多元时间序列具 元时序模糊分段的聚类算法（multiple timing 有多变量、序列长度长、数据容量大、局部含有隐藏 sequence clustering algorithm,MTSCA),通过在数据 结构变化等特点，需对其行分段处理并对分段后的 处理阶段进行归一化、等长度子序列分割以及主成 子序列进行聚类、分类、异常检测等相关处理习 分分析，实现对多元时间序列的聚类挖掘和聚类合 收稿日期：2012-12-30 基金项目：国家自然科学基金资助项目(61070182)：北京市组织部优秀人才资助项目(2010D005003000008) DOI:10.13374/j.issn1001-053x.2014.02.019:http://journals.ustb.edu.cn

第 36 卷 第 2 期 2014 年 2 月 北京科技大学学报 Journal of University of Science and Technology Beijing Vol． 36 No． 2 Feb． 2014 多元时序模糊聚类分段挖掘算法 于重重1，2) ，吴子珺1) ，谭 励1) ，涂序彦2) ，杨 扬2) ，王 璐1) 1) 北京工商大学计算机与信息工程学院，北京 100048 2) 北京科技大学计算机与通信工程学院，北京 100083  通信作者，E-mail: chongzhy@ vip． sina． com 摘 要 工业监控系统所采集到的多元时间序列在利用数据挖掘技术获取内部存在的未知模式的过程中，经常会出现原始 数据庞杂、分段结果重复、交集过多和界限不清晰等问题，导致含有突变变量或数据间相关性差的数据集进行模式挖掘结果 不理想． 针对上述问题，本文提出了一种新的多元时序模糊聚类分段挖掘算法． 实验结果表明，该算法克服了 Gath-Geva 算法 聚类精度易受初始值影响的不足，能够较好地反映出原始数据中潜在的过程变化，从而有效地处理时间序列的分段问题并得 到理想的挖掘结果． 关键词 多元系统; 时间序列; 聚类算法; 数据挖掘; 主成分分析 分类号 TP 391 Multivariate time series fuzzy clustering segmentation mining algorithm YU Chong-chong1，2)  ，WU Zi-jun1) ，TAN Li1) ，TU Xu-yan2) ，YANG Yang2) ，WANG Lu1) 1) School of Computer ＆ Information Engineering，Beijing Technology and Business University，Beijing 100048，China 2) School of Computer and Communication Engineering，University of Science and Technology Beijing，Beijing 100083，China  Corresponding author，E-mail: chongzhy@ vip． sina． com ABSTＲACT Multivariate time series collected by industrial monitoring systems often have problems such as numerous raw data， repeated segmentation results，redundant intersections and blurry boundaries in the process of using data mining technologies to acquire internal existing unknown patterns，leading to unsatisfied mining results when the dataset involves mutation variables or inferior relevance among the data． To resolve these problems，this article introduces a new multiple time sequence clustering algorithm． Experi￾mental results show that this algorithm can overcome the shortage that the accuracy of clustering is often affected by initial values in the Gath-Geva algorithm． It can exhibit the potential variation of raw data and thus efficiently deal with segmentation in multivariate time series to get ideal mining results． KEY WOＲDS multivariable systems; time series; clustering algorithms; data mining; principal component analysis 收稿日期: 2012--12--30 基金项目: 国家自然科学基金资助项目( 61070182) ; 北京市组织部优秀人才资助项目( 2010D005003000008) DOI: 10． 13374 /j． issn1001--053x． 2014． 02． 019; http: / /journals． ustb． edu． cn 时间序列是指按照时间顺序取得的一系列的观 测值［1］． 在工业监控过程中，观测值往往是多变量 相互影响和相互联系的，并且每个变量均为时间序 列数据，因此为了寻求原始数据中所蕴含的未知模 式，预测未来的变化趋势，多元时间序列作为一种数 据对象逐渐受到人们的重视． 由于多元时间序列具 有多变量、序列长度长、数据容量大、局部含有隐藏 结构变化等特点，需对其行分段处理并对分段后的 子序列进行聚类、分类、异常检测等相关处理［2--3］． 目前对于子序列的处理主要采用聚类方法，而在工 业领域中广泛使用的聚类算法为均值法［4］，虽然其 聚类过程比较简单，效率较高，但在使用中存在需要 事先确定聚类数目，容易陷入局部最优等问题． 本 文提出了一种以 Gath-Geva 聚类算法［5］为基础的多 元时序模糊分段的聚类算法 ( multiple timing sequence clustering algorithm，MTSCA) ，通过在数据 处理阶段进行归一化、等长度子序列分割以及主成 分分析，实现对多元时间序列的聚类挖掘和聚类合

第2期 于重重等：多元时序模糊聚类分段挖掘算法 ·261· 并.为验证算法有效性，本文以“可再生能源与建筑 …,xnN）. 集成”项目中实时监测到的海量数据为对象，进行 1.1.3主成分分析 多元时序模糊聚类分段挖掘，并对实验结果进行了 在对多变量数据进行研究时，变量的增加会导 分析比较，结果表明该算法能够较为快速地检测出 致数据分析工作的难度和复杂性成倍增加.因此， 多元时间序列中隐藏结构的变化 将原有的多变量经过一系列的运算和变换变成较少 的变量是十分必要的.为保证这些变量能够尽可能 1多元时序模糊分段聚类算法 地保留原有变量所反应的信息，同时满足上述要求， 由于时间序列具有大长度、多数据点等特性，为 因此引入主成分分析网 了描述其在某个时间段内的局部特征，提高数据挖 通过使用马氏距离来调整变量之间的相关性， 掘的效率，需要先根据用户指定的模式长度和时间 并得到相应的协方差矩阵F: 粒度，完成原始时间序列的分割，分割时一般将其分 割成等长度的子序列或不重叠的子序列集合，为后 (u(x-）)(x4-）T F.= (2) 续计算降低复杂程度.由于变量的变化具有模糊 ∑（μ.）m 性，所以在对时间序列进行分段过程中给出清晰的 界定是不切实际的因.考虑到在时间序列中数据聚 式中：u.4表示第k个数据点属于第i次聚类的先验 类中的点必须来自于连续的时间点，因此在聚类的 概率，即初始隶属值；m表示模糊参数：表示聚类 过程中要同时考虑数据的时间坐标.本文提出的算 中心 法，其主体思想是把数据建模为一个混合的多元高 通过协方差矩阵F得到其特征值和特征向量， 斯分布，并采用高斯隶属函数来表示时间序列的模 并根据数据变化的贡献在陡坡图上有序的绘制出特 糊分段. 征值入，然后分析陡坡图上特征值贡献率C0的幅 多元时序模糊聚类分段挖掘的具体步骤为： 度和综合的累积率CU以选择合适的主成分数目. (1)多元时间序列归一化、等长度子序列分段分割 其中： 处理；(2)时间序列的主成分分析；(3)算法实现聚 C0= (3) 类合并：(4)时间序列模糊分段 1.1多元时间序列预处理 台 i 1.1.1时间序列分段描述 SA = 定义1时间序列为T={x1≤k≤N},其中 CU= (4) N为时间序列的数据长度，x=x,x2k,…,x] ∑AH = 为按时间点t,2,…,tw标记的N个样本的有限集， 若协方差矩阵F:有q个非零的特征值，则可以 则连续时间点S(a,b)=a≤k≤b,x。,xa+1,…,x6表 被分解为 示为T中的任意一个分段团. F=UAU =0I+WW. (5) 定义2S={S:(a,b:)I1≤i≤c}定义为对时 式中， 间序列T分段成不重叠的c个时间片段，其中a,= 1,b.=V,a:=b:-1+1. 入时 由于一个时间序列分段可以看作为一个具有约 因此，在使用主成分分析方法对协方差矩阵F, 束的聚类，因此可以在连续的条件下对所取得的数 进行降维处理后的观测向量x:转变为 据按照其相似性进行聚类处理 y.k=W1(x)=W(x). (6) 1.1.2时间序列归一化 式中，W为权重矩阵，W=U.,(Ag-σ.I)nR, 为了保证时间序列在聚类处理的收敛速度，增 R,是一个任意q×q正交旋转矩阵. 加样本间的统计分布性，采用归一化来完成数据的 1.2多元时间序列聚类挖掘 预处理，公式如下： 由于要考虑实际时间序列与拟合分段片段函数 x.-minx (1) 之间的距离，根据数据点与聚类原型的加权距离平 x=- maxx minx 方和的标准来对目标函数进行定义回 式中：xn=n1,xn.2,,xaN],n为数据维度：minx. 定义3数据点与聚类原型的加权距离平方和 为min(xn1,xn,2,…,xnN）;marn为max（xa1'xa2, J的计算公式为

第 2 期 于重重等: 多元时序模糊聚类分段挖掘算法 并． 为验证算法有效性，本文以“可再生能源与建筑 集成”项目中实时监测到的海量数据为对象，进行 多元时序模糊聚类分段挖掘，并对实验结果进行了 分析比较，结果表明该算法能够较为快速地检测出 多元时间序列中隐藏结构的变化． 1 多元时序模糊分段聚类算法 由于时间序列具有大长度、多数据点等特性，为 了描述其在某个时间段内的局部特征，提高数据挖 掘的效率，需要先根据用户指定的模式长度和时间 粒度，完成原始时间序列的分割，分割时一般将其分 割成等长度的子序列或不重叠的子序列集合，为后 续计算降低复杂程度． 由于变量的变化具有模糊 性，所以在对时间序列进行分段过程中给出清晰的 界定是不切实际的［6］． 考虑到在时间序列中数据聚 类中的点必须来自于连续的时间点，因此在聚类的 过程中要同时考虑数据的时间坐标． 本文提出的算 法，其主体思想是把数据建模为一个混合的多元高 斯分布，并采用高斯隶属函数来表示时间序列的模 糊分段． 多元时序模糊聚类分段挖掘的具体步骤为: ( 1) 多元时间序列归一化、等长度子序列分段分割 处理; ( 2) 时间序列的主成分分析; ( 3) 算法实现聚 类合并; ( 4) 时间序列模糊分段． 1. 1 多元时间序列预处理 1. 1. 1 时间序列分段描述 定义 1 时间序列为 T = { xk | 1≤k≤N} ，其中 N 为时间序列的数据长度，xk =［x1，k，x2，k，…，xn，k］T 为按时间点 t1，t2，…，tN 标记的 N 个样本的有限集， 则连续时间点 S( a，b) = a≤k≤b，xa，xa + 1，…，xb 表 示为 T 中的任意一个分段［7］． 定义 2 Sc T = { Si ( ai，bi ) | 1≤i≤c} 定义为对时 间序列 T 分段成不重叠的 c 个时间片段，其中 a1 = 1，bc = N，ai = bi － 1 + 1． 由于一个时间序列分段可以看作为一个具有约 束的聚类，因此可以在连续的条件下对所取得的数 据按照其相似性进行聚类处理． 1. 1. 2 时间序列归一化 为了保证时间序列在聚类处理的收敛速度，增 加样本间的统计分布性，采用归一化来完成数据的 预处理，公式如下: x' n = xn － minxn maxxn － minxn ． ( 1) 式中: xn =［xn，1，xn，2，…，xn，N］，n 为数据维度; minxn 为 min( xn，1，xn，2，…，xn，N ) ; maxxn 为 max ( xn，1，xn，2， …，xn，N) ． 1. 1. 3 主成分分析 在对多变量数据进行研究时，变量的增加会导 致数据分析工作的难度和复杂性成倍增加． 因此， 将原有的多变量经过一系列的运算和变换变成较少 的变量是十分必要的． 为保证这些变量能够尽可能 地保留原有变量所反应的信息，同时满足上述要求， 因此引入主成分分析［8］． 通过使用马氏距离来调整变量之间的相关性， 并得到相应的协方差矩阵 Fi : Fi = ∑ N k = 1 ( μi，k ) m ( xk － vx i ) ( xk － vx i ) T ∑ N k = 1 ( μi，k ) m ． ( 2) 式中: μi，k表示第 k 个数据点属于第 i 次聚类的先验 概率，即初始隶属值; m 表示模糊参数; vx i 表示聚类 中心． 通过协方差矩阵 Fi 得到其特征值和特征向量， 并根据数据变化的贡献在陡坡图上有序的绘制出特 征值 λk，然后分析陡坡图上特征值贡献率 CO 的幅 度和综合的累积率 CU 以选择合适的主成分数目． 其中: CO = λi ∑ p k = 1 λk ， ( 3) CU = ∑ i k = 1 λk ∑ p k = 1 λk ． ( 4) 若协方差矩阵 Fi 有 q 个非零的特征值，则可以 被分解为 Fi = UiΛiUT i = σ2 i，x I + WiWT i ． ( 5) 式中， σ2 i，x = 1 n － q ∑ n j = q +1 λi，j ． 因此，在使用主成分分析方法对协方差矩阵 Fi 进行降维处理后的观测向量 xk 转变为 yi，k = W － 1 i ( xk ) = WT i ( xk ) ． ( 6) 式中，Wi 为权重矩阵，Wi = Ui，q ( Λi，q － σ2 i，x I) 1 /2 Ｒi， Ｒi 是一个任意 q × q 正交旋转矩阵． 1. 2 多元时间序列聚类挖掘 由于要考虑实际时间序列与拟合分段片段函数 之间的距离，根据数据点与聚类原型的加权距离平 方和的标准来对目标函数进行定义［9］． 定义 3 数据点与聚类原型的加权距离平方和 J 的计算公式为 · 162 ·

·262· 北京科技大学学报 第36卷 (7) p()p() p(zln:)×p(n)]= 式中表示观察点z4=,x门T在第i聚类(i= p(x,h)= 1,2,…,c）的隶属程度，m∈1，）是决定所产生模 名p,）= 糊聚类的加权指数；D(z,n:)表示数据点和聚类原 (n)xp(e.In)p(n). (13) 型的距离.通过此方法，令时间作为一个变量，将数 即 据建模为一个混合多元高斯分布，以此来减少数据 (14) 点z4=,x]T和聚类原型n:间的加权距离平 p(zln)=p(tln:)xp(xn:). 定义4由于距离D(z4,n:)和隶属概率p(zI 方和. n:)存在反比关系，则定义距离函数为 为了避免出现局部最优现象，达到聚类结果所 产，n)=a:xp4ln,）×p(x.In）.(15) 1 要求的效率和精度，文中选择基于均值标准差的定 心法作为MTSCA聚类算法初始聚类中心，公式为 其中：第一项a:表示为聚类的先验概率；第二项p m=u-o+2-）, (4ln:)表示为第k个数据点到第i次时间聚类中心 i=1,2,…,k:l=1,2,…,9. (8) 的距离，用公式表示为 式中，μ为均值，σ为标准差，k为第k个聚类，q为 多维数据的维度. )w." (16) 在主成分分析完成后，可以得到初始聚类原型 n:={,F:,t,σxp(n)},并通过最小化目标函数 第三项p(xk|n:)表示聚类原型到特征空间数据之 间的距离，用公式表示为 (7)获得聚类原型的最佳参数.其约束条件为： [U=μ.t]exyI u.k∈0,1]，i,k; p(xn)=(2m)x det(F )x =1,: (9) ep[2(x-)'px-]}. (17) 式中，为特征空间中第i次时间聚类中心的坐标， l0<∑<N,i. r表示与i次聚类相关的距离所表示的模糊协方差 由此，聚类原型n:中的各个参数如下 矩阵F,的秩 聚类的先验概率： 通过上述公式，计算出D(z4,n),并通过迭代 (10) 更新矩阵： 聚类中心： a0= (18) D(zn:)/D(z,n]2-) ∑(u.)"(x4-W,y.) 式中，1≤i≤c,1≤k≤N.对l=1,2,…,进行迭代， V= (11) ( 当满足收敛条件‖U0-U1-)‖<ε时，迭代停止. 1.3多元时间序列聚类合并 时间模型参数，中心和标准差： 通过计算相邻分段之间的目标函数，反复合并 N 两个最低目标段并使其满足条件为止.通过采用递 、，)2 归聚类合并方法来评估相邻聚类之间的相似性，并 (i.)m 以此来合并相互相似的聚类.在这个合并和重新聚 类的过程中，聚类的数目逐渐减少，直到找到一个适 (12) 当的聚类数.这个合并过程基于主成分分析模型之 根据Gath-Geva聚类算法由p(z.ln:)表示隶属 间相似性模糊决策算法来进行控制. 于第i次聚类中数据点z4的概率，数据点z4=, 两个主成分模型的相似性可以通过主成分相似 x门T,则联合密度函数p(z)=p(x4,l4)中的两个相 因子SA来决定.数据集的两个部分S,和S的 互独立变量t:和x:可建模为一个n+1维的高斯混 PCA模型都由g个主成分构成，则相似因子S可 合函数，则有 表示为

北 京 科 技 大 学 学 报 第 36 卷 J = ∑ c i = 1 ∑ N k = 1 ( μi，k ) m D2 ( zk，ηi ) ． ( 7) 式中: μi，k表示观察点 zk =［tk，xT k］T 在第 i 聚类( i = 1，2，…，c) 的隶属程度，m∈［1，∞ ) 是决定所产生模 糊聚类的加权指数; D2 ( zk，ηi ) 表示数据点和聚类原 型的距离． 通过此方法，令时间作为一个变量，将数 据建模为一个混合多元高斯分布，以此来减少数据 点 zk = ［tk，xT k］T 和聚类原型 ηi 间的加权距离平 方和． 为了避免出现局部最优现象，达到聚类结果所 要求的效率和精度，文中选择基于均值标准差的定 心法作为 MTSCA 聚类算法初始聚类中心，公式为 mil = ( μl － σl ) + 2σl k － 1( i － 1) ， i = 1，2，…，k; l = 1，2，…，q． ( 8) 式中，μ 为均值，σ 为标准差，k 为第 k 个聚类，q 为 多维数据的维度． 在主成分分析完成后，可以得到初始聚类原型 ηi = { vx i ，Fi，v t i，σ2 i，x，p( ηi ) } ，并通过最小化目标函数 ( 7) 获得聚类原型的最佳参数． 其约束条件为: U = ［μi，k ］c ×N | μi，k ∈［0，1］，i，k; ∑ c i = 1 μi，k = 1，k; 0 ＜ ∑ c i = 1 μi，k ＜ N，        i． ( 9) 由此，聚类原型 ηi 中的各个参数如下． 聚类的先验概率: p( ηi ) = 1 N ∑ N k = 1 μi，k ． ( 10) 聚类中心: vx i = ∑ N k = 1 ( μi，k ) m ( xk － Wi ，〈yi，k〉) ∑ N k = 1 ( μi，k ) m ． ( 11) 时间模型参数，中心和标准差: v t i = ∑ N k = 1 ( μi，k ) m tk ∑ N k = 1 ( μi，k ) m ，σ2 i，x = ∑ N k = 1 ( μi，k ) m ( tk － vt k ) 2 ∑ N k = 1 ( μi，k ) m ． ( 12) 根据 Gath-Geva 聚类算法由 p( zk | ηi ) 表示隶属 于第 i 次聚类中数据点 zk 的概率，数据点 zk =［tk， xT k］T ，则联合密度函数 p( zk ) = p( xk，tk ) 中的两个相 互独立变量 tk 和 xk 可建模为一个 n + 1 维的高斯混 合函数，则有 p( zk ) = ∑ c i = 1 p( zk，ηi ) = ∑ c i = 1 ［p( zk | ηi ) × p( ηi ) ］= p( xk，tk ) = ∑ c i = 1 p( xk，tk，ηi ) = ∑ c i = 1 ［p( tk | ηi ) × p( xk | ηi ) p( ηi ) ］． ( 13) 即 p( zk | ηi ) = p( tk | ηi ) × p( xk | ηi ) ． ( 14) 定义 4 由于距离 D2 ( zk，ηi ) 和隶属概率 p( zk | ηi ) 存在反比关系，则定义距离函数为 1 D2 ( zk，ηi ) = ai × p( tk | ηi ) × p( xk | ηi ) ． ( 15) 其中: 第一项 ai 表示为聚类的先验概率; 第二项 p ( tk | ηi ) 表示为第 k 个数据点到第 i 次时间聚类中心 v t i 的距离，用公式表示为 p( tk | ηi ) = 2 { πσ2 槡 i，t × exp [ 1 2 ·( tk － v t i ) 2 σ2 i， ] } t － 1 ; ( 16) 第三项 p( xk | ηi ) 表示聚类原型到特征空间数据之 间的距离，用公式表示为 p( xk | ηi ) = { ( 2π) r 2 × det 槡 ( Fi ) × [ exp 1 2 ( xk － v x i ) T F － 1 i ( xk － v x i ) ] } － 1 ． ( 17) 式中，v x i 为特征空间中第 i 次时间聚类中心的坐标， r 表示与 i 次聚类相关的距离所表示的模糊协方差 矩阵 Fi 的秩． 通过上述公式，计算出 D2 ( zk，ηi ) ，并通过迭代 更新矩阵: μ ( l) i，k = 1 ∑ c j = 1 ［D( zk，ηi ) /D( zk，ηj ) ］2 /( m －1) ． ( 18) 式中，1≤i≤c，1≤k≤N． 对 l = 1，2，…，进行迭代， 当满足收敛条件‖U( l) － U( l － 1) ‖ ＜ ε 时，迭代停止． 1. 3 多元时间序列聚类合并 通过计算相邻分段之间的目标函数，反复合并 两个最低目标段并使其满足条件为止． 通过采用递 归聚类合并方法来评估相邻聚类之间的相似性，并 以此来合并相互相似的聚类． 在这个合并和重新聚 类的过程中，聚类的数目逐渐减少，直到找到一个适 当的聚类数． 这个合并过程基于主成分分析模型之 间相似性模糊决策算法来进行控制． 两个主成分模型的相似性可以通过主成分相似 因子 SPCA 来决定． 数据集的两个部分 Si 和 Sj 的 PCA 模型都由 q 个主成分构成，则相似因子 Si，j PCA可 表示为 · 262 ·

第2期 于重重等：多元时序模糊聚类分段挖掘算法 ·263· S=(UL,U..U.,U.). (19) 若聚类所对应的O+1值高于阈值y,则对最相似的 0 一组相邻聚类进行合并，当上述算法在到达终止容 式中，U,和U,为数据集中占最大变化的g个主成 限ε或不再需要聚类合并时即完成了对多元时间序 分的子空间. 列的模糊分段 为了检测出变量平均值的变化，同时也需要考 虑聚类中心之间的距离： 2实验 D(,)=I-I. (20) 为了验证MTSCA算法在数据挖掘中的有效 因此，相似性标准要考虑两个因子c=S兕和= 性，以“可再生能源与建筑集成”项目中实时监测到 D(,) 的海量数据为基础，选取其中两组具有代表性的数 由于相似性标准量化了聚类各方面的相似性， 据进行测试.在此过程中所选取的测试样本如表1 应通过聚合过程获得整体的聚类的相似性，因此还 所示.其中，宁夏“清水湾”住宅区一期工程中所选 要用到一个模糊决策方法.在这里引入包含有并行 取的数据参数为一号机补水温度、一号机用水温度、 度，和临近度，的隶属函数，其中和的值 二号机补水温度、二号机用水温度、一号机水泵功率 由平均相似性给出： (W)、二号机水泵功率(W)、太阳辐照度(W·m2)、 =e(e-1) 累计辐照量(M·m2)和风速(m·s1).河北建设 服务中心办公楼工程中所选取的数据参数为主机供 (21) 水温度、主机回水温度、主机瞬时温度、循环温度、循 而整体聚类相似性通过上述两个参数来确定的.决 环湿度和主机功率.上述指标在研究开发可再生能 策过程的结果为整体聚类相似性矩阵O,其元素 源与建筑集成技术中尤为重要，能够直接体现节能 0为 建筑预期效果与实际情况的差异，因此针对不同能 112 源类型的两组实验结果为采用时序分析法对经济指 0 )2+（u)2 (22) 标的预测奠定了基础。 表1可再生能源与建筑集成项目数据表 Table 1 Renewable energy and building integrated project data sheet 数据项目 项目类型 选取时段 监测领率样本数目点 样本类型 宁夏“清水湾”住宅区一期工程 太阳能光热利用工程2010-07-16T00:00:00一13：20：00 1s1 47345 数据相关性较好 河北建设服务中心办公楼 地源热泵应用工程 2009-08-01-2009-08-09 I min- 12674 数据相关性较差 2.1实验数据准备 15000 2.1.1数据间相关性较好的数据 5000 选取宁夏“清水湾”住宅区一期工程中的数据 -5000 (共47345点，相关性较好)，并将其输入程序，预设 1.0 初始化被测数据的分段数，c=10,则通过初始环节 0.6 协方差矩阵的特征值绘出陡坡图，如图1所示.要 456 7 主成分数目 满足98%的准确度近似条件，则由图可确定出主成 图1宁夏“清水湾”住宅区一期工程协方差矩阵陡坡图 分数目q=3,并设定模糊参数m=2,终止容限ε≤ Fig.I Covariance matrix steep slope graph of a residential area of 10-4,由时间序列的均匀性可定矩阵0相似性阈值 Ningxia Qing Shui Wan 0.3<y<0.75. 2.1.2数据间相关性较差的数据 由时间序列的均匀性可定矩阵0相似性阈值0.3< 选取河北建设服务中心办公楼工程中的数据 y<0.75. (共12674点，相关性较差)，并将其输入程序，初始 2.2实验结果及分析 化被测数据的分段数，c=10,并通过初始环节协方 宁夏“清水湾”住宅区一期工程中数据采用多 差矩阵的特征值绘出陡坡图如图2所示.要满足 元时序模糊聚类分段的聚类算法所得分段结果，如 98%的准确度近似条件，则由图可确定出主成分数 图3所示.同时计算出相邻聚类的相似因子S” 目g=3,并设定模糊参数m=2,终止容限e≤10-4， 分别为0.6273、0.0961、0.6013和0.6341，相似性指

第 2 期 于重重等: 多元时序模糊聚类分段挖掘算法 Si，j PCA = 1 q tr( UT i，qUj，qUT j，qUi，q ) ． ( 19) 式中，Ui，q和 Uj，q为数据集中占最大变化的 q 个主成 分的子空间． 为了检测出变量平均值的变化，同时也需要考 虑聚类中心之间的距离: D( vx i ，vx j ) = ‖vx i － vx j ‖． ( 20) 因此，相似性标准要考虑两个因子 c 1 i，j = Si，j PCA和 c 2 i，j = D( vx i ，vx j ) ． 由于相似性标准量化了聚类各方面的相似性， 应通过聚合过程获得整体的聚类的相似性，因此还 要用到一个模糊决策方法． 在这里引入包含有并行 度 μ1 i，j和临近度 μ2 i，j的隶属函数，其中 μ1 i，j和 μ2 i，j的值 由平均相似性给出: μ1 i，j = 1 c( c － 1) ∑ c i = 1 ∑ c j = 1 j≠i c 1 ij，μ2 i，j = 1 c( c － 1) ∑ c i = 1 ∑ c j = 1 j≠i c 2 ij． ( 21) 而整体聚类相似性通过上述两个参数来确定的． 决 策过程的结果为整体聚类相似性矩阵 O，其元素 Oi，j为 Oi，j = [ ( μ1 i，j ) 2 + ( μ2 i，j ) 2 ] 2 1 /2 ． ( 22) 若聚类所对应的 Oi，i + 1值高于阈值 γ，则对最相似的 一组相邻聚类进行合并，当上述算法在到达终止容 限 ε 或不再需要聚类合并时即完成了对多元时间序 列的模糊分段． 2 实验 为了验证 MTSCA 算法在数据挖掘中的有效 性，以“可再生能源与建筑集成”项目中实时监测到 的海量数据为基础，选取其中两组具有代表性的数 据进行测试． 在此过程中所选取的测试样本如表 1 所示． 其中，宁夏“清水湾”住宅区一期工程中所选 取的数据参数为一号机补水温度、一号机用水温度、 二号机补水温度、二号机用水温度、一号机水泵功率 ( W) 、二号机水泵功率( W) 、太阳辐照度( W·m － 2 ) 、 累计辐照量( MJ·m － 2 ) 和风速( m·s － 1 ) ． 河北建设 服务中心办公楼工程中所选取的数据参数为主机供 水温度、主机回水温度、主机瞬时温度、循环温度、循 环湿度和主机功率． 上述指标在研究开发可再生能 源与建筑集成技术中尤为重要，能够直接体现节能 建筑预期效果与实际情况的差异，因此针对不同能 源类型的两组实验结果为采用时序分析法对经济指 标的预测奠定了基础． 表 1 可再生能源与建筑集成项目数据表 Table 1 Ｒenewable energy and building integrated project data sheet 数据项目 项目类型 选取时段 监测频率 样本数目点 样本类型 宁夏“清水湾”住宅区一期工程 太阳能光热利用工程 2010--07--16T00: 00: 00—13: 20: 00 1 s － 1 47345 数据相关性较好 河北建设服务中心办公楼 地源热泵应用工程 2009--08--01—2009--08--09 1 min － 1 12674 数据相关性较差 2. 1 实验数据准备 2. 1. 1 数据间相关性较好的数据 选取宁夏“清水湾”住宅区一期工程中的数据 ( 共 47345 点，相关性较好) ，并将其输入程序，预设 初始化被测数据的分段数，c = 10，则通过初始环节 协方差矩阵的特征值绘出陡坡图，如图 1 所示． 要 满足 98% 的准确度近似条件，则由图可确定出主成 分数目 q = 3，并设定模糊参数 m = 2，终止容限 ε≤ 10 － 4，由时间序列的均匀性可定矩阵 O 相似性阈值 0. 3 ＜ γ ＜ 0. 75． 2. 1. 2 数据间相关性较差的数据 选取河北建设服务中心办公楼工程中的数据 ( 共 12674 点，相关性较差) ，并将其输入程序，初始 化被测数据的分段数，c = 10，并通过初始环节协方 差矩阵的特征值绘出陡坡图如图 2 所示． 要满足 98% 的准确度近似条件，则由图可确定出主成分数 目 q = 3，并设定模糊参数 m = 2，终止容限 ε≤10 － 4， 图 1 宁夏“清水湾”住宅区一期工程协方差矩阵陡坡图 Fig． 1 Covariance matrix steep slope graph of a residential area of Ningxia Qing Shui Wan 由时间序列的均匀性可定矩阵 O 相似性阈值 0. 3 ＜ γ ＜ 0. 75． 2. 2 实验结果及分析 宁夏“清水湾”住宅区一期工程中数据采用多 元时序模糊聚类分段的聚类算法所得分段结果，如 图 3 所示． 同时计算出相邻聚类的相似因子 Si( i + 1) PCA 分别为 0. 6273、0. 0961、0. 6013 和 0. 6341，相似性指 · 362 ·

·264 北京科技大学学报 第36卷 15000 5000 -5000 鳞1.00e 0.95 50001000015000200002500030000350004000045000 时间/ 0.85 图4基于Hotelling T算法的“清水湾”住宅区一期工程分段结 主成分数目 果图 Fig.4 Segmentation result of Ningxia Qing Shui Wan residential area 图2河北建设服务中心办公楼工程协方差矩阵陡坡图 Fig.2 Covariance matrix steep slope graph of Hebei Construction project based on Hotelling T2 algorithm Service Center Office Building engineering 在4800min附近，相邻聚类的相似因子最小且相似 数分别为0.6341、0.0168、0.4706和0.6306.从图3 性指数为0.3745，在图5中可以清晰地看出在这附 可以看出最终的分段数目为5.在第二段与第三段 近无交集，表明在该点附近变量之间的相似性发生 之间，即在32000s附近，相邻聚类的相似因子最小 了最大的改变，变量间突变现象较严重：而在第七段 且相似性指数为0.0168，在图2中可以清晰地看出 与第八段(9000min点左右)之间相似因子较大，相 在这附近无交集，表明在该点附近变量之间的相似 似性指数高，说明变量间的变化趋势基本一致，主要 性发生了最大的改变，变量间突变现象较严重：而在 是平均值发生了变化. 第一段与第二段、第四段与第五段(23000s、44000s 1.0 左右)之间相似因子较大，相似性指数高，说明变量 间的变化趋势基本一致，主要是平均值发生了变化. 0 2000 4000 6000 8000 10000 12000 时间/min 68 图5基于MTSCA算法的河北建设服务中心办公楼工程分段结 04 果图 Fig.5 Segmentation result of Hebei Construction Service Center Of- 50001000015000200002500030000350004000045000 时间/s fice Building projeet based on MTSCA algorithm 图3基于MTSCA算法的宁夏“清水湾”住宅区一期工程分段结 同样与基于多元统计分析Hotelling T算法的 果图 自底向上分段方法进行比较，基于Hotelling T的自 Fig.3 Segmentation result of Ningxia Qing Shui Wan residential area 底向上算法的分段结果如图6所示 project based on MTSCA algorithm 为了进一步验证分段结果的准确性，本文将结 果与基于多元统计分析Hotelling T2算法的自底向 上分段方法no进行比较.基于Hotelling T2的自底 0 2000 4000600080001000012000 向上算法的分段结果如图4所示. 时间/min 经过对比发现MTSCA算法在处理相关性较 图6基于Hotelling T2算法的河北建设服务中心办公楼工程分 好的数据时不仅可以得到基于Hotelling T的自底 段结果图 向上方法获得的分段结果且能够同时发现检测到 Fig.6 Segmentation result of Hebei Construction Service Center Of- 潜在过程变化和数据点的突变，如在32000s和 fice Building project based on Hotelling T2 algorithm 39000s处. 通过比较可以发现基于模糊分段算法开发的聚 河北建设服务中心办公楼工程中数据采用多元 类分析大体上不仅可以得到基于Hotelling T的自 时序模糊聚类分段的聚类算法所得分段结果，如图 底向上方法获得的分段结果（在数据点3200min、 5所示.计算出相邻聚类的相似因子S”分别为 4100min、4700min和6900min左右)：且能够同时发 0.4137、0.5929、0.5602、0.3640、0.6273、0.6399、 现检测到潜在过程变化和数据点的突变，如在300 0.9283和0.4062，相似性指数分别为：0、0、0、 min和9200min左右处 0.3745、0.6844、0.6922、0.7236和0.从图中可以看 通过上述两组不同相关性数据的实验可以得出 出最终的分段数目为9.在第四段与第五段之间，即 结论：无论数据间是否具有相关性，多元时序模糊分

北 京 科 技 大 学 学 报 第 36 卷 图 2 河北建设服务中心办公楼工程协方差矩阵陡坡图 Fig． 2 Covariance matrix steep slope graph of Hebei Construction Service Center Office Building engineering 数分别为 0. 6341、0. 0168、0. 4706 和 0. 6306． 从图 3 可以看出最终的分段数目为 5． 在第二段与第三段 之间，即在 32000 s 附近，相邻聚类的相似因子最小 且相似性指数为 0. 0168，在图 2 中可以清晰地看出 在这附近无交集，表明在该点附近变量之间的相似 性发生了最大的改变，变量间突变现象较严重; 而在 第一段与第二段、第四段与第五段( 23000 s、44000 s 左右) 之间相似因子较大，相似性指数高，说明变量 间的变化趋势基本一致，主要是平均值发生了变化． 图 3 基于 MTSCA 算法的宁夏“清水湾”住宅区一期工程分段结 果图 Fig． 3 Segmentation result of Ningxia Qing Shui Wan residential area project based on MTSCA algorithm 为了进一步验证分段结果的准确性，本文将结 果与基于多元统计分析 Hotelling T2 算法的自底向 上分段方法［10］进行比较． 基于 Hotelling T2 的自底 向上算法的分段结果如图 4 所示． 经过对比发现 MTSCA 算法在处理相关性较 好的数据时不仅可以得到基于 Hotelling T2 的自底 向上方法获得的分段结果且能够同时发现检测到 潜在过程变化和数据点的突变，如 在 32000 s 和 39000 s 处． 河北建设服务中心办公楼工程中数据采用多元 时序模糊聚类分段的聚类算法所得分段结果，如图 5 所示． 计算出相邻聚类的相似因子 Si( i + 1) PCA 分别为 0. 4137、0. 5929、0. 5602、0. 3640、0. 6273、0. 6399、 0. 9283 和 0. 4062，相似性指数分别为: 0、0、0、 0. 3745、0. 6844、0. 6922、0. 7236 和0． 从图中可以看 出最终的分段数目为 9． 在第四段与第五段之间，即 图 4 基于 Hotelling T2 算法的“清水湾”住宅区一期工程分段结 果图 Fig． 4 Segmentation result of Ningxia Qing Shui Wan residential area project based on Hotelling T2 algorithm 在 4800 min 附近，相邻聚类的相似因子最小且相似 性指数为 0. 3745，在图 5 中可以清晰地看出在这附 近无交集，表明在该点附近变量之间的相似性发生 了最大的改变，变量间突变现象较严重; 而在第七段 与第八段( 9000 min 点左右) 之间相似因子较大，相 似性指数高，说明变量间的变化趋势基本一致，主要 是平均值发生了变化． 图 5 基于 MTSCA 算法的河北建设服务中心办公楼工程分段结 果图 Fig． 5 Segmentation result of Hebei Construction Service Center Of￾fice Building project based on MTSCA algorithm 同样与基于多元统计分析 Hotelling T2 算法的 自底向上分段方法进行比较，基于 Hotelling T2 的自 底向上算法的分段结果如图 6 所示． 图 6 基于 Hotelling T2算法的河北建设服务中心办公楼工程分 段结果图 Fig． 6 Segmentation result of Hebei Construction Service Center Of￾fice Building project based on Hotelling T2 algorithm 通过比较可以发现基于模糊分段算法开发的聚 类分析大体上不仅可以得到基于 Hotelling T2 的自 底向上方法获得的分段结果( 在数据点 3200 min、 4100 min、4700 min 和6900 min 左右) ; 且能够同时发 现检测到潜在过程变化和数据点的突变，如在 300 min 和 9200 min 左右处． 通过上述两组不同相关性数据的实验可以得出 结论: 无论数据间是否具有相关性，多元时序模糊分 · 462 ·

第2期 于重重等：多元时序模糊聚类分段挖掘算法 ·265· 段方法均能够有效地区分各个分段之间的模糊界 B]Jia P T,He H C,Liu L,et al.Overview of time series data min- 限，检测到其潜在过程变化和数据点的突变，为“可 ing.Appl Res Comput,2007,24(11)15 (贾澎涛，何华灿，刘丽，等.时间序列数据挖掘综述.计算机 再生能源与建筑集成”项目中技术经济指标的预测 应用研究，2007,24(11)：15) 奠定了基础. [4]Gao Y,Liu D Y,Qi H,et al.Semi-supervised K-means cluste- 3结论 ring algorithm for multi-ype relational data.Softcare,2008,19 (11):2814 (1)通过实验证明MTSCA算法在处理多变量 (高滢，刘大有，齐红，等。一种半监督K均值多关系数据聚类 算法.软件学报，2008,19(11)：2814) 时序数据时具有良好的效果，能够较清晰地显示出 [Abonyi J,Feil B,Nemeth S,et al.Modified Gath-Geva clustering 分段结果并发现其模式 for fuzzy segmentation of multivariate time-series.Fuzzy Sets Syst, (2)MTSCA算法能够有效地减小Gath-Geva算 2005,149(1):39 法对于初始值的敏感性，从而根本上保证分段结果 6]Keogh E.Data mining and machine learning in time series data- 的准确性. bases /Tenth ACM SIGKDD International Conference Knowledge (3)MTSCA算法能够清晰地反映出原始数据 Discovery and Data Mining.Seattle,2004 Li A C.Qin Z.On-ine segmentation of time-series data.I Sofi- 中潜在的过程变化，为“可再生能源与建筑集成”项 re,2004,15(11):1671 目中技术经济指标的预测提供了可行的分段保障， (李爱国，覃征.在线分割时间序列数据.软件学报，2004， 说明该算法在多元时序模糊聚类分段挖掘的实际应 15(11):1671) 用中具有较高的应用价值. [8]Hua J Z,Wang J G,Yang J Y.A novel approach to edge detec- tion based on PCA.J Image Graph,2009,14(5):912 (华继钊，王建国，杨静宇.基于PCA的边缘检测方法.中国 参考文献 图象图形学报，2009,14(5)：912) Mao Y J.Research and Implementation of Multidimensional Time- ] Li M,Xu J W,Yang JH,et al.Prediction for chaotic time series Series Data Mining Methods [Dissertation].Shanghai:Shanghai based on phase reconstruction of multivariate time series.Uni Jiao Tong University,2007 Sci Technol Beijing,2008,32(2):208 (毛云建.多维时间序列数据挖掘的方法研究及应用[学位论 (黎敏，徐金梧，阳建宏，等.基于多变量相重构的混沌时间 文].上海：上海交通大学，2007) 序列预测.北京科技大学学报，2008,32(2)：208) Chen XT,Li M L,Chen Y J.Summaly of application research [10]Chen X L,Yang L M.Partitioning machine learning sample set based on clustering of time series similarity.Comput Eng Des, using similarity to mean vector.J Cent South Univ Sci Technol, 2010,31(3):577 2009,40(6)：1636 (陈湘涛，李明亮，陈玉娟.基于时间序列相似性聚类的应用 (陈先来，杨路明.基于均矢量相似性的机器学习样本集划 研究综述.计算机工程与设计，2010,31(3)：577) 分.中南大学学报：自然科学版，2009,40(6)：1636)

第 2 期 于重重等: 多元时序模糊聚类分段挖掘算法 段方法均能够有效地区分各个分段之间的模糊界 限，检测到其潜在过程变化和数据点的突变，为“可 再生能源与建筑集成”项目中技术经济指标的预测 奠定了基础． 3 结论 ( 1) 通过实验证明 MTSCA 算法在处理多变量 时序数据时具有良好的效果，能够较清晰地显示出 分段结果并发现其模式． ( 2) MTSCA 算法能够有效地减小 Gath-Geva 算 法对于初始值的敏感性，从而根本上保证分段结果 的准确性． ( 3) MTSCA 算法能够清晰地反映出原始数据 中潜在的过程变化，为“可再生能源与建筑集成”项 目中技术经济指标的预测提供了可行的分段保障， 说明该算法在多元时序模糊聚类分段挖掘的实际应 用中具有较高的应用价值． 参 考 文 献 ［1］ Mao Y J． Ｒesearch and Implementation of Multidimensional Time￾Series Data Mining Methods ［Dissertation］． Shanghai: Shanghai Jiao Tong University，2007 ( 毛云建． 多维时间序列数据挖掘的方法研究及应用［学位论 文］． 上海: 上海交通大学，2007) ［2］ Chen X T，Li M L，Chen Y J． Summaly of application research based on clustering of time series similarity． Comput Eng Des， 2010，31( 3) : 577 ( 陈湘涛，李明亮，陈玉娟． 基于时间序列相似性聚类的应用 研究综述． 计算机工程与设计，2010，31( 3) : 577) ［3］ Jia P T，He H C，Liu L，et al． Overview of time series data min￾ing． Appl Ｒes Comput，2007，24( 11) : 15 ( 贾澎涛，何华灿，刘丽，等． 时间序列数据挖掘综述． 计算机 应用研究，2007，24( 11) : 15) ［4］ Gao Y，Liu D Y，Qi H，et al． Semi-supervised K-means cluste￾ring algorithm for multi-type relational data． J Software，2008，19 ( 11) : 2814 ( 高滢，刘大有，齐红，等． 一种半监督 K 均值多关系数据聚类 算法． 软件学报，2008，19( 11) : 2814) ［5］ Abonyi J，Feil B，Nemeth S，et al． Modified Gath-Geva clustering for fuzzy segmentation of multivariate time-series． Fuzzy Sets Syst， 2005，149( 1) : 39 ［6］ Keogh E． Data mining and machine learning in time series data￾bases / / Tenth ACM SIGKDD International Conference Knowledge Discovery and Data Mining． Seattle，2004 ［7］ Li A G，Qin Z． On-line segmentation of time-series data． J Soft￾ware，2004，15( 11) : 1671 ( 李爱国，覃征． 在线分割时间序列数据． 软件学报，2004， 15( 11) : 1671) ［8］ Hua J Z，Wang J G，Yang J Y． A novel approach to edge detec￾tion based on PCA． J Image Graph，2009，14( 5) : 912 ( 华继钊，王建国，杨静宇． 基于 PCA 的边缘检测方法． 中国 图象图形学报，2009，14( 5) : 912) ［9］ Li M，Xu J W，Yang J H，et al． Prediction for chaotic time series based on phase reconstruction of multivariate time series． J Univ Sci Technol Beijing，2008，32( 2) : 208 ( 黎敏，徐金梧，阳建宏，等． 基于多变量相重构的混沌时间 序列预测． 北京科技大学学报，2008，32( 2) : 208) ［10］ Chen X L，Yang L M． Partitioning machine learning sample set using similarity to mean vector． J Cent South Univ Sci Technol， 2009，40( 6) : 1636 ( 陈先来，杨路明． 基于均矢量相似性的机器学习样本集划 分． 中南大学学报: 自然科学版，2009，40( 6) : 1636) · 562 ·