商务智能原理与方法（第3版）-课件 Lecture8-Temporal pattern

数据挖掘——时态模式挖掘主要内容时态数据类型与模式时态关联规则挖掘序列相似性时态数据模式分析时态模式数据代表的事实或对应的事件经常与时间相关将包含以显性形式表达时间状态的数据称为时态数据e.g.商品购买时间、疾病症状出现时间、银行交易时间、气候变化时间、客户服务时间、销售时间趋势、经济运行时序、股票价格变化、网页浏览日志……时态数据挖掘从大规模时态数据中发现具有时态特征的知识，具有时态特征的知识称为时态知识，或时态模式TID购

买

商

品购

买

时

间TID气

象

发

生开

始

时

间结

束

时

间T100旅游鞋，浴巾，MP32008.10.2001大雾01:0022:30T200浴巾，跑步机2008.10.9002中雨10:1515:20…………………时态关联规则X

Y表示“事件X发生的情况下，事件Y同时发生”时态关联规则是具有显性时间元素的关联规则，T为延迟时间“事件X发生的情况下，事件Y在T时间单位后发生”“购买猪肉两天后购买白菜”时态关联规则

数据项集合I={I1,I2,…,Im}，项集X，Y

I，称延迟项集的支持度可以定义为表示含X的记录后第个t时间单位的记录包含Y的记录个数

时态关联规则延迟规则的支持度和置信度为表示前个记录中包含X的记录个数延迟时态关联规则的挖掘，可以把各属性复制并去掉前t个记录，并入原数据集，形成新的数据集，再直接利用Apriori方法进行挖掘。

时态关联规则DayStockAStockBStockCStockA'StockB'StockC'111001120011003011111410001151111116011

7111

序列相似性反映了数据序列之间的类似程度子序列匹配：发现与要查询序列相似的数据序列根据滑动窗口在给定序列中查找相似的局部序列全序列匹配：发现彼此相似的序列序列相似性对于任意两个时间序列：和

，其序列相似性作为时态模式，可记为序列相似性序列匹配与传统数据库查询的不同之处在于：传统数据库查询要求查询条件与数据库数据之间精确匹配序列匹配采用近似匹配，即要发现那些与查询序列轻微不同的数据序列，较多用于金融分析、医疗诊断、信息检索和文本挖掘等距离测度法海明（Hamming）距离序列相似性对于两个时间序列

和欧氏（Euclidean）距离闵可夫斯基（Minkowski）距离距离测度法切比雪夫距离序列相似性对于两个时间序列

和兰氏距离（用于非负指标）距离测度法夹角余弦法序列相似性Pearson相关系数法也可以直接定义序列之间的近似度动态时间变形法（DynamicTimeWarping）寻求序列在不同时间点的动态距离匹配，以获得最佳匹配效果模式匹配法基于近邻的协同过滤采用“自下而上”的动态规划思路，利用一个滑动窗口对子序列分别进行比较可根据需要对子序列的局部数值进行复制而调整序列长度，可得到调整后的序列，最后计算得到其相似水平。语音识别领域广泛应用的经典方法之一。DTW方法原理需要比较相似性的两段时间序列的长度可能并不相等例如语音序列，不同人的语速不同，不同发音的长度不同欧式距离无法有效计算DTW方法原理DTW通过时间序列进行延伸和缩短，计算两个时间序列性之间的距离DTW使用所有相似点之间的距离的和，称之为归整路径距离(WarpPathDistance)来衡量两个时间序列之间的相似性两个时间序列X和Y，长度分别为|X|和|Y|，其归整路径为：wk是指第k步X和Y中两个坐标点之间的距离(i,j)，其中i是X中的i坐标，j表示的是Y中的j坐标DTW方法原理DTW方法的思想是是把两个时间序列进行延伸和缩短，来得到两个时间序列性距离最短也就是最相似的那一个warping，这个最短的距离也就是这两个时间序列的最后的距离度量。假设序列X为ABCDEF，序列Y为1234。XY之间所有归整路径的可能：归整路径的距离为：2+3+5+4+7+2+1+7+5=36DTW方法原理归整路径需要满足如下几个约束：边界条件：w1=(1,1)和wK=(|X|,|Y|)。所选的路径必定是从左下角出发，在右上角结束。连续性：如果wk-1=(i*,j*)，那么对于路径的下一个点wk=(i,j)需要满足(i-i*)<=1和(j-j*)<=1。只能和自己相邻的点匹配。单调性：如果wk-1=(i*,j*)，那么对于路径的下一个点wk=(i,j)需要满足0<=(i-i*)和0<=(j-j*)。W必须是随着时间单调进行的。以保证匹配不会相交。DTW方法原理结合连续性和单调性约束，每一个格点的路径就只有三个方向了。例如如果路径已经通过了格点(i,j)，那么下一个通过的格点只可能是下列三种情况之一：(i+1,j)，(i,j+1)或者(i+1,j+1)。归整路径的距离可以表示为：时态关系模式通过时态逻辑表达事件之间的联系时态逻辑有先后（before/after）、包含（contain/during）、同时（equal）、重叠（overlap）等，表达了事件发生之间的时间限定关系。时态关系模式时态关系模式设

为状态集合，每条记录对应一个事件

，可表达为一个三元组（状态

，起始时间

，结束时间.,

事

件

标

号状

态起

始

时

间st结

束

时

间ete1a1110e2a228e3a358e4a11215e5a11925e6a21920e7a32224时态关系模式

如果两个事件的起始时间和结束时间满足

，且，则称，表示事件的发生时间包含事件，记做长度为2的包含事件序列对于

中的任意两个不同状态

和

，状态关系

表示状态

的发生时间包含

，称为长度为2的包含时态序列，简记为

对于事件，如果

的状态为,的状态为，且，则称为序列的一个实例，或称支持时态关系模式事

件

标

号状

态起

始

时

间结

束

时

间e1a1110e2a228e3a358e4a11215e5a11925e6a21920e7a32224是的一个实例和和的一个实例进一步的，长度为

的DTS表示为

，如果对于中的任意状态都存在一个事件，且事件序列成立，则称

支持时态序列

时态关系模式对于时态序列，支持计数support为事

件

标

号状

态起

始

时

间结

束

时

间e1a1110e2a228e3a358e4a11215e5a11925e6a21920e7a32224如果的支持数不小于事先设定的最小支持阈值，则称为一个频繁包含时态序列e.g.

给定两个包含时态序列和,设

和

分别表示两个序列中的状态集合，且，则称

为包含时态模式，表示时态序列

发生期间时态序列

也发生

时态关系模式与关联规则类似，时态模式的支持度和置信度为对于预先设定的最小支持数阈值ms和最小置信度阈值mc，若

则称为符合要求的包含时态模式时态关系模式事

件

标

号状

态起

始

时

间结

束

时

间e1a1110e2a228e3a358e4a11215e5a11925e6a21920e7a32224时态关系模式挖掘剪枝策略是否依然成立？首先根据时态数据库计算出所有的长度为2的包含时态序列，形成以任意状态为根，包含状态为叶子节点的二层树状结构从一个状态开始深度优先搜索深度优先搜索vs广度优先搜索搜索过程中每新增一个状态均计算support，对于support小于阈值的分支提前剪枝时态关系模式挖掘如果从状态a4开始，处理和找到时态关系如下：a4a2,a4a2a5,a4a2a6,a4a2a6a5,a4a2a9,a4a2a10,a4a2a11a4a2a11a5,a4a2a11a6,a4a2a11a6a5,a4a2a11a7,a4