基于时间序列聚类和ARMA模型的检索量预测

模型的检索量预测*基于时间序列聚类和ARMA孙承杰刘丰林磊刘秉权( 哈尔滨工业大学 计算机科学与技术学院，黑龙江 哈尔滨 150001)摘 要: 为了通过预测分析检索量数据来指导商家调整产品开发及经营策略，将检索量数据组织为时间序列，对其用自回归滑动平均( ARMA) 模型进行建模预测 先将时间序列 进行聚类，仅对聚类中心序列进行 ARMA 模型识别，同类序列用该模型进行近似建模预 测; 经过数据预处理、相似性分析、基于相似度的聚类、时间序列预测等过程，得到检索量 数据的预测值，并将其与检索量的实际值做比较 结果表明，用同一个 ARMA 模型拟合相 似时间序列的方法具有可行性，且有较高的预测准确率 从聚类结果还可看出，同品牌产 品的检索量数据趋于聚成一类，这为检索词关系的挖掘提供了参考关键词: 时间序列; 检索量; ARMA 模型; 动态时间弯曲距离; k-medoid 算法中图分类号:TP 391doi: 10 3969 / j issn 1000-565X 2011 04 004测方法3需要估计大量的参数，神经网络的结构过于复杂且难以选择，所以这些方法都不能很好地应 用于文中的数据 ARMA 模型是一种传统模型，对数 据的平稳性要求较高，检索量序列大多不满足平稳 性，在其上建立 ARMA 模型的过程较为复杂 鉴于 某些检索量序列具有形态相似性，文中假定形态相 似的时间序列可以用相同的 ARMA 模型建模预测 首先对检索量序列按曲线相似性聚类，而后仅对聚 类中心进行模型识别，将得到的模型应用于该类中 所有检索量序列的预测在互联网高速发展的今天，对网络用户行为的研究具有很高的商业价值 搜索引擎是网站建设中 针对用户使用网站的便利性所提供的必要功能，同 时也是研究网站用户行为的一个有效工具 通过对 搜索引擎中检索词词频的统计分析，可以发现、共享 和挖掘互联网上最有价值的信息和资讯，直接且客 观地反映社会热点、网民的兴趣和需求 因此，文中 对检索量数据进行数据预测及规律分析，以发掘产 业信息，指导商家决策检索量数据是用户输入“检索框”的检索词数 量的统计值，同一检索词的检索量数据按时间顺序 排列形成一个时间序列，检索量的预测抽象为时间 序列的预测问题 时间序列的预测1方法有传统的 基于数理统计的自回归滑动平均( ARMA) 模型及采 用嵌入空间法和神经网络法等的非线性预测技术 非线性预测方法具有较强的适应性，但应用过程复 杂 嵌入空间法2 中向空间重构的质量非常关键， 将直接影响模型的建立和预测; 基于神经网络的预1检索量预测研究方案及算法本研究的目的是预测检索量数据的未来数值，预测过程采用 ARMA 统计模型 为减少建模次数，提出了用一种模型近似拟合一类时间序列的方法 对时间序列进行预测前，先将序列聚类，每类时间序 列进行一次 ARMA 模型识别，而后用该模型近似拟 合这类中的其他序列 研究过程如图 1 所示收稿日期: 2011-01-10* 基金项目: 国家自然科学基金资助项目( 60973076，61073127) ; 哈尔滨工业大学中央高校基本科研业务费专项资金资助1 3动态时间弯曲算法及其改进时间序列的相似性是通过距离度量来确定的，最常用的是欧式距离 但欧式距离仅适用于两个等长序列的比较，且对时间轴变形很敏感 动态时间弯图 1 互联网检索量数据预测流程图Fig 1 Flow chart of prediction of search data volume in Internet8曲 ( DTW) 技术 于 1994 年被引入数据挖掘领域，用于计算两个序列经时间轴变形后的最小距离 设ARMA 模型ARMA4模型由 Box 和 Jenkins 创立，其基本思 想是: 某些时间序列是依赖于时间 t 的一组随机变 量，构成该时序的单个序列值虽然具有不确定性，但 整个序列的变化却有一定的规律性，可以用相应的 数学模型近似描 述 其 3 种 基 本 类 型 是: 自 回 归 ( AR) 模型、滑动平均( MA) 模型以及自回归滑动平 均( ARMA) 模型，前两者是后者的特殊情况 ARMA 模型中，时间序列值 yt 是其当期和前期的随机误差 项以及前期值的线性函数，可表示为 yt = 1 yt 1 +1 1两个时间序列 Q 和 C 表示为 Q = Q ，Q ，Q ，12IQn 和 C = C1 ，C2 ，CJ ，Cm 定义一个 P 行 m 列的距离矩阵 D = ( dis( Q ，C ) ) ，其中 dis( Q ，C ) 为I JI J两序列中 Q 、C 两点的距离 在距离矩阵中，定义时I J间序列相似关系的一组连续的矩阵元素的集合为弯曲路径，记为 W = w ，w ，w ，w 弯曲路径必12kK须满足有界性、边界条件和单调性条件 一般仅关心具有最小长度的路径，计算过程采用迭代方法:r( I，J) = dis( Q ，C ) + min r( I 1，J 1) ，I Jr( I 1，J) ，r( I，J 1) ( 2)2 yt 2+ + p yt p+ ut 1 ut 1 2 ut 2 式中: r( I，J) 代表至 QI 和 J 两点的弯曲路径的最小长度根据两个序列的最小路径长度 r( P，m) 计算它 们的 DTW 距离 DTW 距离公式为Cq ut q ，记为 ARMA( p，q) 其中: 1 ，2 ，p 为自回归系数，1 ，2 ，q 为滑动平均系数，它们都是 模型的待估参数; p、q 为系数的阶数; ut ，ut 1 ，ut q 是相互独立的白噪声序列 如果原序列非平稳， 经过 d 阶逐期差分后平稳，则原序列可表示为 ARI- MA( p，d，q) 模型KDTW( Q，C) = min 槡wk / K ( 3)k = 1式中: K 为弯曲路径的长度 DTW 距离越小，两序列相似程度越大 为降低计算的时间复杂度9，通常 将弯曲路径限制在一定宽度的窗口内，或限定在斜 率确定的平行四边形内 另外，对时间维度过长、或 存在异常点的时间序列，常用时间序列近似方法10 将其表示为长度较短的序列k-medoid 算法及其评价指标聚类算法5 主要有划分方法、层次方法、基于 密度的方法、基于网格的方法和基于模型的方法 文 中的聚类对象具有维度高、相似度计算复杂等特点， 聚类过程选用基于划分的 k-medoid6 算法 k-me- doid 算法在 k-means 算法的基础上，选择数据对象 作为聚 类 中 心 当 存 在“噪 声”和孤立点数据 时k-medoid 算法比 k-means 算法更健壮 这是因为中 心点不像平均值那么容易被极端数据影响由于聚类数目通常是未知的，聚类之后需要对 聚类结果进行评价 基于样本的类内散度与各聚类 中心间距的测度的 DB( Davies-Bouldin) 7指标 R珔可用于相同聚类数和不同聚类数的聚类结果之间的比较，计算公式如下:1 2文中研究方法文中研究过程分为数据预处理、相似度计算、聚 类分析和 ARMA 模型预测几个部分 在数据预处理 部分，将检索量数据按时序排列，并进行分段、最大 最小规范化处理，将检索量的预测转化为时间序列 的预测; 在相似度计算部分，采用限制窗口的 DTW 算法计算任意两个时间序列的相似度，得到时间序 列的相似度矩阵，既保证了准确度又降低了时间复 杂度; 在聚类分析部分，设定不同聚类数目多次进行 k-medoid 聚类，计算各聚类结果的 DB 指标，选择最 优的聚类结果作为 ARMA 模型预测的基础; 最后对 每类的中心序列进行 ARMA 建模，该类中的序列用 同一模型进行建模预测1 4N1R珔 =N i( 1)Ri = 1Si + Sj式中: N 代表聚类数目; Ri = max Rij ，Rij =，SiMijji代表第 i 类的所有样本到其聚类中心的平均距离，Mij 表示第 i 类聚类和第 j 类聚类的中心的距离 DB指标越小则聚类结果越优1 4 1数据预处理文中研究的检索量数据为互联网公布的部分检索词的检索量，由于互联网的检索量公布数量有限，考察范围内的检索词的检索量可能在某些天不公 布，即数据缺失，检索量序列还呈现以 7 天为周期波 动、不同检索词的检索量相差大等特点 所以文中以 周为单位将数据分段，每周的均值按周次组成新的 时间序列 另外，为解决序列数值相差过大的问题， 对原序列做归一化处理，映射到区间0，1 原序列 为 A = a11 ，a12 ，a17 ，aef ，其中 aef 表示第 e 周的第1 4 4ARMA 模型预测过程确定序列的最佳聚类后，对每一类的中心序列进行 ARMA 模型识别，并用该模型建模预测这类中的 时间序列，具体步骤如下:步骤 1 平稳性检验及平稳化处理 绘制聚类 中心序列的自相关和偏相关分析图，若序列不满足 平稳性条件则对序列差分或对数差分使其自相关系 数和偏相关系数都很快趋于零，确定差分阶数 d步骤 2 模型识别 若序列的自相关系数、偏 自相关系数均呈衰减正弦波并趋向于零，表现为拖 尾性，则根据其拖尾起始位置，估计 p 和 q 的可能取 值，初选模型 ARIMA( p，d，q) 步骤 3参数估计及检验 用步骤 2 中满足过f 天; 新 序 列 为 B = b1 ，b2 ，bg ，其 中 bg=7a min( A) ef bgf /7，bgf，min( A) 、max( A) min( A)= max( A)f = 1分别为 A 中元素的最小值和最大值 映射区间的选择不是唯一的，但计算时间序列相似度时要进行多 点距离的累加，区间值不宜过大1 4 2相似度计算采用限定窗口的 DTW 算法计算时间序列相似 度 假设曲线的平移对齐在一个月内是允许的，已知 时间序列每个值代表的时间跨度为 7 天，这样得到 窗口宽度约为 4，即 v = 4 仅计算式( 2 ) 中这样的 r( I，J) ，其中 | I J | v 注意边界值的计算如下:r( I，I + v) = dis( I，I + v) + min r( I，I + v 程平稳要求的初选 模 型 建 模，并 确 定 AdjustedR-squared 值 最 小、AIC ( AkaikeInfo Criterion )和 SC( Schwartz Criterion) 值最大的模型为该序列的最佳模型步骤 4模型检验 对模型的残差序列进行白 噪声检验，验证残差序列的随机性步骤 5模型预测分析扩展样本期至预测期，得到预测期内样本的预测值步骤 6同类序列建模预测 该类中的其他时 间序列用同一 ARMA 模型进行建模预测1) ，r( I 1，I + v 1) ( 4)计算至 r( P，m) 结束，由 r( P，m) 和路径长度 K计算 DTW 值 由于文中的时间序列等长，且有窗口 宽度的限制，可以忽略路径长度的不同，将式( 3) 近 似为实验过程及结果分析实验数据为 95 个数码产品检索词的检索量 数据，时 间 范 围 为 2009-05-17 至 2010-07-11，共421 天 检索量数据进行预处理后，计算相应时间序 列的 DTW 距离，得到时间序列的相似度矩阵 根据 相似度矩阵进行聚类数为 2 9 的 k-medoid 聚类各200 次，统计出最高频和次高频结果并进行 DB 指标 评价，结果如表 1、2 所示表 1 不同聚类数出现频率最高的结果Table 1 The most high-frequency clustering results of different cluster numbers2KDTW( Q，C) = min 槡wk / L ( 5)k = 1式中: L 为序列的长度，它在文中数据集上是个常量1 4 3时间序列聚类以相似度矩阵为基础进行聚类，聚类过程采用k-medoid 算法，以聚类结果的稳定性作为终止条件 根据聚类数目选取的规则，一般聚类数目小于样本 数的平方根11 以每个聚类数进行多次聚类，统计 聚类结果，选取出现频率最高和次高的聚类结果，计 算每一聚类结果的误差 选取误差最小的聚类结果 为最佳聚类结果 式( 1) 中涉及到的 Si 、Mij 值分别用 以下公式计算:聚类数聚类中心出现次数DB 值 10，53 5，40，41 0，10，53，91 0，10，11，53，91 10，11， ，76 0，3， ，91 8，16， ，4 0，10， ，92234567891013718787751 121 590 961 191 271 554 011 46 T ，Ai ) ，Ti1Si =dis( xji j = 1式中: Ti 为第 i 类的元素个数Mij= dis( Ai ，Aj ) 式中: Ai 和 Aj 分别代表第 i 类和第 j 类的聚类中心表 2 不同聚类数出现频率次高的结果Table 2The second high-frequency clustering results of diffe- rent cluster numbers聚类数聚类中心出现次数DB 值23456789 75，92 10，11，69 8，10，38，91 8，10，11，38，91 8，11， ，82 8，11， ，38 11，38， ，76 0，3， ，77993113675541 462 091 421 441 521 746 871 53由表 1、2 可见，聚类误差在聚类数为 2 和 4 时较小，聚类数为 4 时达到最小值 为直观地体现聚类 数及聚类结果出现频率对聚类误差的影响，绘制聚 类误差曲线如图 2 所示图 3 同类别序列相似性示例Fig 3Examples of similarity between time series of the same class表 3 同品牌产品检索量类别的分布规律Table 3 Distribution regularities of products with the same brand图 2 聚类数及聚类结果出现频率对聚类误差的影响Fig 2 Effects of clustering number and frequency of clustering results on clustering error品牌数在同一类别的比例同类分布464100%100% 70%70% 50%2 /2，3 /34 /5，3 /4，5 /71 /2，2 /4图 2 显示，相同聚类数的聚类结果中，出现频率最高的结果比出现频率次高的结果拥有更小的误 差，所以在 k-medoid 聚类中，聚类结果出现的频率 也可以作为衡量聚类质量的一个指标按照误差最小原则，将时间序列划分为 4 类，为 验证同类序列之间存在形态相似性，绘制不同类 时间序列如图 3 所示，其中“戴尔”、“尼康”对应的 序列为第 2 类，“pocketpc”、“掌上电脑”对应的序列 为第 3 类 由图 3 可明显地观察到同类序列确实有 更大的相似性通过观察还发现，同类别的曲线不只在形态上 具有相似性，其对应的关键词在词义上也存在一定 联系 例如同一品牌产品的检索量曲线更多的聚为 一类，如苹果公司有五个产品在对象集 里，其 中 “iphone”、“ipod touch”、“macbook”、“苹果笔记本” 对应的 4 个序列都被划分为第 3 类 抽样 10 个品牌 的产品数据，统计其聚类情况，结果见表 3，从中可 看出同一品牌的产品检索量的变化规律很可能是相 似的序列聚类的有效性经过验证后，计算出每类序列的中心值( 均值) ，对该均值序列进行 ARMA 模型 识别，并对该类中所有序列采用该模型建模预测，得 到所有序列的预测值 最后采用趋势准确率12来评 价预测结果的准确性，预测值与实际值相对于上期 值同为增加或同为减少则认为预测结果准确，结果 如表 4 所示 由表 4 可知，不同类别的序列模型各不 相同，这体现了分类建模的必要性 而各模型对相应 类别的预测准确率也较高，初步证明了同类序列用 相同模型拟合的可行性表 4 ARMA 模型及其对应的预测结果Table 4 ARMA models and their corresponding predication results时间序列类别对象个数 ARMA 模型 趋势准确数趋势准确率第 1 类( 对数)第 2 类 第 3 类 第 4 类340429ARIMA( 2，1，2)ARIMA( 1，1，2) ARIMA( 1，1，1) ARIMA( 2，1，2)329306100%72 5%71 4%66 7%出版社，2002: 106-132Han Jiawei，Kamber M 数据挖掘: 概念与技术 M范明，孟小峰，译 北京: 机械工业出版社，2000Kaufman L，Rousseeuw P J Clustering by means of me- doids C Proc of Statistical Data Analysis Based on the L1-Norm and Related Methods Amsterdam: North- Holland，1987: 405-416Davies D L，Bouldin D W A cluster separation measureJ IEEE Transaction on Pattern Analysis and MachineIntelligence，1979，1( 4) : 224-227Berndt D J，Clifford J Using dynamic time warp to find patterns in time series CProc of AAAI-94 Workshop on Knowledge Discovery in Database Washington: AAAI Press，1994: 359-370Keogh E J，Pazzani M J Derivative dynamic time warpingCProc of the First SIAM International Conference onData Mining Chicago: SDM，2001Das G，Lin K I，Mannila H Rule discovery from time se- ries C Proc of the 3rd International Conference of Knowledge Discovery and Data Mining New York: ACM SIGKDD，1998: 16-22Dimitriadou E，Dolnicar S，Weingessel A An examina- tion of indexes for determining the number of cluster in binary data sets J Psychomctrika，2002，67 ( 1 ) : 137-160Armstrong J S，Collopy F Error measures for generalizing about forecasting methods: empirical comparisons J International Journal of Forecasting，1992，8( 1) : 69-803结语文中从实际应用出发，以互联网数码产品检索56量为源数据，经过数据预处理、相似性分析、基于相似度的聚类、时间序列预测过程，得到检索量数据的 预测值，并与检索量的实际值做比较，得到了较高的 准确率，证明用同一个 ARMA 模型拟合相似时间序 列的方法具有可行性 此外，聚类结果体现出同品牌 产品的检索量数据趋于聚成一类，为检索词关系挖 掘提供了参考 检索量预测除了与历史数据有关外， 还会受季节、突发事件等因素的影响，而呈现以年为 周期的波动或由突发事件引起的剧烈变化 未来的 研究可以围绕挖掘检索量的影响因素开展，以期进 一步提高预测的准确率789参考文献:101Weigend A S，Gershenfeld N A Time series prediction:forecasting the future and understanding the past C Proc of the NATO Advanced Research Workshop on Com- parative Time Series Analysis MA: Addison-Wesley，1994Taken S F Detecting strange attractors in turbulence J Lecture Notes in Mathematics，1981，898( 2) : 366-381 Maguire L P，Roche B，Mcginnity T M Predicting a chao- tic time series using a fuzzy neural network J Informa- tion Sciences，1998，112( 1 /2 /3 /4) : 125-136易丹辉 数据分析与 Eviews 应用 M 北京: 中国统计1123124Prediction of SearchData Volume Based onTime-Series Clustering and ARMA ModelsSun Cheng-jieLiu FengLin LeiLiu Bing-quan( School of Computer Science and Technology，Harbin Institute of Technology，Harbin 150001，Heilongjiang，China)Abstract: In order to guide the adjustment of product development and business strategy by predicting and analy-zing the search data volume，the data of search volume are organized into time series that is modeled and predicted using the autoregressive moving average ( ARMA) models Then，the set of time series is modeled by clustering; the cluster centers are modeled using ARMA models; and the same-class series is fitted with the models approxi- mately to obtain the predicted values Moreover，after such operations as data preprocessing，similarity analysis， similarity-based clustering and time-series prediction，the search data volume is predicted and is compared with the actual one Experimental results show that it is feasible and accurate to model similar time series with the same AR- MA model In addition，clustering results indicate that the search data volume of the products with the same brand tends to be clustered together，which provides a reference for the relationship mining of search termsKey words: time series; search data volume; ARMA model; dynamic time-warping distance; k-medoid algorithmfile:/D|/我的资料/Desktop/新建文本文Appliance Error (configuration_error)Your request could not be processed because of a configuration error: Could not connect to LDAP server.For assistance, contact your network support team.file:/D|/我的资料/Desktop/新建文本文 20:42:52