下列语句序列执行后，i 的值为什么是8呢？ int i=8, j=16; if( i-1 & j ) i--; else j--;_百度知道
下列语句序列执行后，i 的值为什么是8呢？ int i=8, j=16; if( i-1 & j ) i--; else j--;
我有更好的答案
以上可以么;16，很明显是假，则i--不执行，直接到else执行j--；所以i仍然是8if-else啊~在if里是8-1&gt
采纳率：46%
这个是自加自减和选择语句的问题。i-1=7不会大于16（j）,所以执行的是else语句，即j--,if语句不会执行，即i--不会被执行。i的值就不会变，自然是8了。
int i=8 后面i的值又没有发生变化 为什么不是8i-1&j false 所以i--不执行
if条件执行了后面的呀
为您推荐：
其他类似问题
换一换
回答问题，赢新手礼包
个人、企业类
违法有害信息,请在下方选择后提交
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。教程说下载了edius6.55的 正式版安装补丁以后运行会弹出机器码，为什么我的只是弹出注册序列号的提示？_百度知道
教程说下载了edius6.55的 正式版安装补丁以后运行会弹出机器码，为什么我的只是弹出注册序列号的提示？
双击打开以后就只是出现了这个，没有机器码的提示啊，不想用试用版想用正式版要怎么办？
我有更好的答案
我说，首先，扫描。之后再点刚才那个小三角。清除就可以了，不要紧，你补丁安装的位置，必须和你安装edius时的位置是一样的。有个办法很简单，就是你安装edius时，把路径复制下来。之后补丁安装的路径你粘贴就一样了。如果安装完补丁发现edius打不开。之后edius就可以正常破解了。你下载一个清除键值的软件，叫Trial-Reset4.0
打开后点击Flexent右边小三角
需要把那个安装在EDIUS的文件夹中，也就是说EDIUS安在哪了
那个补丁也安在哪
我也是这样的
那你就买序列号吧。别人不可能花钱买个序列号，送给你，对吧~
我不明白我哪步操作出现错误了啊
我只知道正版怎么激活，盗版不知道怎么做！百度知道也不会公开支持盗版吧？
1元红包 我给你发
2条折叠回答
为您推荐：
其他类似问题
edius6的相关知识
换一换
回答问题，赢新手礼包
个人、企业类
违法有害信息,请在下方选择后提交
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。一道Java题，求解题详细步骤！下列语句序列执行后，k 的值是。_百度知道
一道Java题，求解题详细步骤！下列语句序列执行后，k 的值是。
k+=2; case
default 下列语句序列执行后，k 的值是。int
i=10, j=18, k=30;switch( j - i ){ case
我有更好的答案
这时k=31然后执行K+=2选C 每个case语句后要加不然会从满足条件的那个case开始，一直运行到break。 int i = 10, 这时k=33 然后执行K+=3 这时k=36最后执行k/j 即36/18 结果为2 , j = 18;
switch (j - i) {
k++, k = 30, 如果像下面这样每个case后都有那么就是楼上的答案了;所以先执行k++ ,而每个case后面都没有break.因为j-i=8满足了第一个case
采纳率：30%
案: A首先:j-i=8;所以switch-case的条件就是:
这时候: case 8
答案：C这样的问题，一眼就可以看出来，你要记住，switch 分支选择语句 如果没有 退出语句，它会一直顺序向下执行。运行：
j - i == 8;
从 case 8: 开始一直下去。
k++ 之后是 31。
k+2 之后是 33。
。。。之后的要我说完吗?最后等于2。
C is right!
为您推荐：
其他类似问题
java的相关知识
换一换
回答问题，赢新手礼包
个人、企业类
违法有害信息,请在下方选择后提交
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。赞助商链接
当前位置： >>
时间序列数据的模式发现及预测方法研究
中国科学技术大学 博士学位论文 时间序列数据的模式发现及预测方法研究 姓名：张海勤 申请学位级别：博士 专业：计算机应用 指导教师：蔡庆生
！旦型！鱼旦翌苎塑生兰型！！垫堕塑壁型墼塑塑堡塞垄里墨塑塑查鎏堡壅摘要数据挖掘（Ｄａｔａ Ｍｉｎｉｎｇ）是人工智能领域和数据库领域相结合的热点研究课题，其 目标是在数据库中提取隐含的、先前未知的、潜在有用的知识。 时间序列数据反映了属性值在时间顺序上的特征。现实世界中大量数据的采集与时 间相关，数据具有时间上的关联性。因此，时间序列的知识发现是数据挖掘中的一类非 常重要的问题。利用时间序列的数据挖掘，可以获得数据中蕴含的与时间相关的有用信 息，实现知识的提取。在许多实际应用中，研究时间序列局部特征的变化并识别表示重 大事件发生的局部模式很有意义，比如在股市数据中识别出和股票价格骤然变化相关的 模式非常重要，模式的正确识别有助于对数据趋势的分析和对未知事件的预测。因此从 时间序列数据中挖掘时序模式并根据这些模式进行预测，是一个具有十分重要的理论与 实践意义的课题。 本文全面和深入的探讨了时间序列数据挖掘问题：讨论了该领域的研究现状、最新 技术和进展，研究了时间序列的模式匹配、规则发现、事件检测和预测问题，分析了现 有的一些算法并在此基础上提出了新的解决问题的方法。具体来说，研究内容主要包括： 模式匹配，模式的自动发现和事件预测。它们之间存在一定的依赖和关联，并且和具体 时间序列的特征表示紧密相关。 相似模式匹配的研究涉及特征提取、相似性度量、多维索引结构、查询匹配算法等。 我们分析了现有的时间序列特征抽取方法和多维索引结构的优缺点，提出了新的时序特征抽取方法一事件序列，本文的大部分工作都是基于事件序列进行的；改进了现有的式查询的精度。我们还通过实验研究了小波分析方法在时间序列模式匹配中的应用。多维索引结构，提出和实现了相应的模式匹配算法，该算法和现有方法相比能够提高模 在模式的自动发现方面，由于时间序列数据和时间紧密相关，我们对传统的基于事 务数据库的关联规则挖掘方法进行了改进，使之适用于事件序列的数据挖掘，抽取出和 事件的发生趋势和变化率相关的规则，并采用一些评估方法对规则进行过滤和排序。同 时提出了一种新的基于聚类方法的模式生成算法，挖掘出有代表性的相似模式集合，通过实验和传统的聚类方法进行了比较。在时间序列的预测研究中，传统方法预测的是下一个点的值，而我们预测下一个重 要事件的发生。提出了一种基于事件特征的预测模型：首先将事件序列转换为一个特征 序列，然后通过特征选择对未来事件的特征进行预测，同时分析和定义了时间序列在不 同尺度上的可预测性，最后将对特征的预测还原为对未来事件的预测。特征选择是很多 机器学习算法包括预测算法有效执行的前提，数据中冗余的信息直接影响到算法的性 能，文中在讨论现有特征选择方法的基础上，提出了一种改进的基于分形维数的特征选 择方法。 本论文对上述这三个方面进行了深入研究，从时间序列数据库中搜索相似的模式，中国科学技术大学博士学位论文时间序列数据的模式发现及预测方法研究自动抽取出潜在的时序模式，对时间序列的未来事件进行预测。 本文的主要工作和创新点如下：１．提出了新的时间序列特征表示方法一事件序列，基于该表示方法提出和实现了一种改进的多维索引结构和相应的相似模式匹配算法，并通过实验证明在一定程度上 提高了模式查询的精度： ２．基于事件序列，提出并实现了基于关联规则和聚类方法的模式发现算法。事件序列 是一种和时间相关的序列，需要对传统的基于事务数据的挖掘方法进行很多改进； ３．提出和实现了一种新的基于事件特征的预测模型，定义和分析了事件序列的多尺度 性和可预测性，对时间序列未来事件的发展趋势进行预测。提出了一种改进的基于 分形维数的特征选择方法，从数据集中抽取出最具有代表性的属性子集。 文中我们使用一些经典的时间序列数据和现实数据如股票数据，对上述研究结果进 行了测试和验证。同时我们开发了一个基于电力数据的负荷预测系统，通过对大量和时 间相关的历史负荷数据和气象数据进行挖掘，抽取出一些有价值的信息，并将其用到短期负荷预测中。关键词：数据挖掘，时间序列，事件序列，模式匹配，模式发现，事件预测Ⅱ！里型堂垫查奎兰堡主兰堡堡茎堕塑壁型墼塑塑堡茎垄翌墨堕塑查婆里窒ＡｂｓｔｒａｃｔＤａｔａ ｍｉｎｉｎｇ ｉｓｏｎｅｏｆｔｈｅ ｈｏｔｔｅｓｔ ｒｅｓｅａｒｃｈ ｔｏｐｉｃｓ ｉｎ ａｒｔｉｆｉｃｉａｌ ｉｎｔｅｌｌｉｇｅｎｃｅ ａｎｄ ｄａｔａｂａｓｅ．Ｉｔｓｇｏａｌ ｉｓ ｔｏ ｅｘｔｒａｃｔ ｔｈｅ ｈｉｄｄｅｎ，ｕｎｋｎｏｗｎ，ｂｕｔ ｉｍｐｌｉｃｉｔｌｙ ｕｓｅｆｕｌ ｉｎｆｏｒｍａｔｉｏｎ ｆｒｏｍ ｔｈｅ ｌａｒｇｅ ｄａｔａｂａｓｅ．Ｔｉｍｅ ｓｅｒｉｅｓ ｄａｔａ ｒｅｆｌｅｃｔｓ ｔｈｅ ｆｅａｔｕｒｅｓ ｏｆ ａｔｔｒｉｂｕｔｅ ｖａｌｕｅｓ ａｌｏｎｇ ｔｉｍｅ ｓｅｑｕｅｎｃｅ Ｔｈｅｒｅａｒｅ ａｌｏｔ ｏｆ ｄａｔａ ｒｅｌａｔｅｄ ｔｏ ｔｉｍｅ ｉｎ ｒｅａｌ ｗｏｒｌｄ；ｔｈｅｒｅｆｏｒｅ ｔｉｍｅ ｓｅｒｉｅｓ ｐｒｏｂｌｅｍ ｉｓｃａｎｏｎｅｏｆ ｔｈｅｉｍｐｏｒｔａｎｔ ｆｉｅｌｄｓ ｉｎ ｄａｔａ ｍｉｎｉｎｇ．Ｂｙ ｍｉｎｉｎｇ ｐａｔｔｅｒｎｓ ｆｒｏｍ ｔｉｍｅ ｓｅｒｉｅｓ ｄａｔａ，ｗｅｇｅｔ ｕｓｅｆｕｌｉｎｆｕｒｍａｔｉｏｎ ｒｅｌａｔｅｄ ｔｏ ｔｉｍｅ ｈｉｄｄｅｎ ｉｎ ｔｈｅ ｄａｔａｂａｓｅ，ｔｈｕｓ ｉｍｐｌｅｍｅｎｔ ｅｘｔｒａｃｔｉｏｎ ｏｆ ｋｎｏｗｌｅｄｇｅ．Ｉｎ ｍａｎｙ ｒｅａｌ ａｐｐｌｉｃａｔｉｏｎｓ，ｉｔ ｉｓ ｓｉｇｎｉｆｉｃａｎｔ ｔｏ ｓｔｕｄｙ ｔｈｅ ｃｈａｎｇｅ ｏｆ ｌｏｃａｌ ｃｈａｒａｃｔｅｒｉｚａｔｉｏｎｓ ｉｎ ｔｉｍｅｓｅｒｉｅｓ，ａｎｄｔｏ ｉｄｅｎｔｉｆｙｔｏｔｈｏｓｅ ｌｏｃａｌ ｐａｔｔｅｒｎｓ ｒｅｐｒｅｓｅｎｔｉｎｇ ｉｍｐｏｒｔａｎｔ ｅｖｅｎｔｓ，ｆｏｒ ｅｘａｍｐｌｅ，ｔｏｓｈａｒｐ ｃｈａｎｇｅ ｉｎ ｓｔｏｃｋ ｐｒｉｃｅ．Ｃｏｒｒｅｃｔ ｒｅｃｏｇｎｉｔｉｏｎｓ ｏｆ ｐａｔｔｅｒｎｓａｒｅｉｄｅｎｔｉｆｙ ｐａｔｔｅｒｎｓ ｒｅｌａｔｅｄｈｅｌｐｆｕｌ ｉｎ ｄａｔａ ｔｒｅｎｄ ａｎａｌｙｓｉｓ ａｎｄ ｐｒｅｄｉｃｔｉｏｎ ｏｆ ｆｕｔｕｒｅ ｅｖｅｎｔｓ．Ｔｈｅｒｅｆｏｒｅ，ｈｏｗ ｔｏ ｅｘｔｒａｃｔ ｔｈｅｔｅｍｐｏｒａｌ ｐａｔｔｅｒｎｓ ｐｒａｃｔｉｃｅａｎｄＵＳｅｔｈｅｍ ｆｏｒ ｐｒｅｄｉｃｔｉｏｎ ｉｓａｎｉｍｐｏｒｔａｎｔ ｒｅｓｅａｒｃｈ ｔｏｐｉｃ ｉｎ ｔｈｅｏｒｙ ａｎｄ ｉｎＷｅｅｘｐｌｏｒｅ ｔｉｍｅ ｓｅｒｉｅｓ ｄａｔａ ｍｉｎｉｎｇ ｐｒｏｂｌｅｍ ｄｅｅｐｌｙ ａｎｄ ｃｏｍｐｒｅｈｅｎｓｉｖｅｌｙ ｉｎ ｔｈｉｓ ｔｈｅｓｉｓ：ｄｉｓｃｕｓｓ ｔｈｅ ｃｕｒｒｅｎｔ ｒｅｓｅａｒｃｈ ｓｉｔｕａｔｉｏｎ，ｒｅｌａｔｅｄｗｏｒｋ，ａｎｄ ｓｏｍｅ ｕｐ―ｔｏ―ｄａｔｅ ｔｅｃｈｎｏｌｏｇｉｅｓ ａｎｄｄｅｖｅｌｏｐｍｅｎｔｓ，ａｎｄａｎａｌｙｚｅ ｐａｔｔｅｒｎ ｍａｔｃｈｉｎｇ，ｒｕｌｅ ｄｉｓｃｏｖｅｒｙ，ｅｖｅｎｔ ｄｅｔｅｃｔｉｏｎ ａｎｄ ｐｒｅｄｉｃｔｉｏｎＩｎ ａｌｌｕｓｉｏｎ ｔｏ ｔｈｅ ｐｒｏｂｌｅｍｓ ｏｆ ｃｕｒｒｅｎｔ ａｐｐｒｏａｃｈｅｓ，Ｗｅ ｓｔｕｄｙ ｔｉｍｅｍｅｔｈｏｄｓ ｏｆ ｔｉｍｅｓ ｓｅｒｉｅｓｓｅｒｉｅｓ ｄａｔａ ｍｉｎｉｎｇ ｆｒｏｍ ｔｈｒｅｅ ａｓｐｅｃｔｓ：ｐａｔｔｅｒｎ ｍａｔｃｈｉｎｇ，ａｕｔｏ－ｄｉｓｃｏｖｅｒｙ ｏｆ ｐａｔｔｅｒｎｓ ａｎｄ ｅｖｅｎｔ ｐｒｅｄｉｃｔｉｏｎ．Ｔｈｅｒｅ ｅｘｉｓｔ ｓｏｍｅ ｒｅｌａｔｉｏｎｓ ａｍｏｎｇ ｔｈｅｍ，ａｌｌ ｃｌｏｓｅｌｙ ｒｅｌａｔｅｄｔｏｆｅａｔｕｒｅｒｅｐｒｅｓｅｎｔａｔｉｏｎ ｏｆｔｉｍｅ ｓｅｒｉｅｓ． Ｓｔｕｄｙ ｏｆ ｓｉｍｉｌａｒ ｐａｔｔｅｒｎ ｍａｔｃｈｉｎｇ ｉｎｃｌｕｄｅｓ ｆｅａｔｕｒｅ ｅｘｔｒａｃｔｉｏｎ，ｓｉｍｉｌａｒｉｔｙ ｍｅａｓｕｒｅ， ｔｈｅ ｓｈｏｒｔｃｏｍｉｎｇｓ ｏｆａｍｕｌｔｉ?ｄｉｍｅｎｓｉｏｎａｌ ｉｎｄｅｘ ｓｔｒｕｃｔｕｒｅ，ａｎｄ ｑｕｅｒｙｃｕｒｒｅｎｔａｌｇｏｒｉｔｈｍｓ．Ｗｅ ａｎａｌｙｚｅｆｅａｔｕｒｅ ｅｘｔｒａｃｔｉｏｎ ａｎｄ ｍｕｌｔｉ?ｄｉｍｅｎｓｉｏｎａｌ ｉｎｄｅｘ ｍｅｔｈｏｄｓ，ａｎｄ ｐｒｏｐｏｓｅｎｅｗ ｅｘｔｒａｃｔｉｎｇｍｅｔｈｏｄ，ｔｈａｔ ｉｓ，ｅｖｅｎｔ ｓｅｒｉｅｓ，ｏｎ ｗｈｉｃｈ ｍｏｓｔ ｏｆ ｗｏｒｋ ｉｎ ｔｈｅ ｔｈｅｓｉｓ ｉｓ ｂａｓｅｄ ｏｎ．Ａｔ ｔｈｅ ｓａｍｅ ｔｉｍｅ，ｗｅ ｉｍｐｒｏｖｅｏｎｅｏｆ ｔｈｅ ｃｕｒｒｅｎｔｍｕｌｔｉ－ｄｉｍｅｎｓｉｏｎａｌ ｉｎｄｅｘ ｓｔｒｕｃｔｕｒｅｓ，ｐｒｏｐｏｓｅａｎｄｉｍｐｌｅｍｅｎｔ ｔｈｅ ｃｏｒｒｅｓｐｏｎｄｉｎｇ ｐａｔｔｅｒｎ ｍａｔｃｈｉｎｇ ｈａｓａａｌｇｏｒｉｔｈｍｓ．Ｗｅ ｓｈｏｗ ｂｙ ｅｘｐｅｒｉｍｅｎｔｓ ｔｈａｔ ｉｔｂｅｔｔｅｒ ｐｒｅｃｉｓｉｏｎ ｏｆｐａｔｔｅｒｎ ｍａｔｃｈｉｎｇ ｗｈｅｎ ｃｏｍｐａｒｅｄ ｔＯ ｏｌｄ ａｌｇｏｒｉｔｈｍｓ．Ｉｎｐａｔｔｅｒｎ ｄｉｓｃｏｖｅｒｙ，ｓｉｎｃｅ ｔｉｍｅ ｓｅｒｉｅｓ ｄａｔａｂａｓｅｓ ａｒｅ ｃｌｏｓｅｌｙ ｒｅｌａｔｅｄａｔｏ ｔｉｍｅ，ｔｒａｄｉｔｉｏｎａｌｍｉｎｉｎｇ ｍｅｔｈｏｄ ｃａｎｎｏｔ ｂｅ ｄｉｒｅｃｔｌｙ ａｐｐｌｉｅｄ ｔｏ ｔｈｅｍ，ｔｈｕｓ ｗｅ ｍａｋｅｌｏｔ ｏｆ ｍｏｄｉｆｉｃａｔｉｏｎｓ ｉｎｔｒａｄｉｔｉｏｎａｌ ａｓｓｏｃｉａｔｉｏｎ ｒｕｌｅｓ ｍｅｔｈｏｄ，ｔｏ ａｄａｐｔ ｔｏ ｍｉｎｉｎｇ ｉｎ ｅｖｅｎｔ ｓｅｒｉｅｓ ｄａｔａｂａｓｅｓ，ａｎｄ ｅｘｔｒａｃｔｒｕｌｅｓ ｃｏｒｒｅｌａｔｅｄ ｗｉｔｈ ｏｃｃｕｒｒｉｎｇ ｔｒｅｎｄｓａｎｄ ｃｈａｎｇｉｎｇｒａｔｅｓｏｆｅｖｅｎｔｓ．Ｗｅｕｓｅｓｏｍｅ ｅｖａｌｕａｔｉｏｎｍｅｔｈｏｄｓ ｔｏ ｆｉｌｔｅｒ ａｎｄ ｓｏｒｔ ｔｈｅ ｒｕｌｅｓ．Ａｌｓｏ ｄｕｅ ｔｏ ｓｏｍｅ ｐｒｏｂｌｅｍｓ ｏｆ ｃｕｒｒｅｎｔ ｃｌｕｓｔｅｒｉｎｇ ｍｅｔｈｏｄｓ， ｗｅ ｐｒｏｐｏｓｅａｎｅｗ ｃｌｕｓｔｅｒｉｎｇ ａｐｐｒｏａｃｈ ｆｏｒ ｐａｔｔｅｒｎｇｅｎｅｒａｔｉｏｎ，ａｎｄ ｇｅｔ ｔｈｅ ｒｅｐｒｅｓｅｎｔａｔｉｖｅｍ中国科学技术大学博士学位论文时间序列数据的模式发现及预测方法研究ｓｉｍｉｌａｒ ｐａｔｔｅｒｎ ｓｅｔｓ ｆｒｏｍ ｄａｔａＷｅｖａｌｉｄａｔｅｏｕｒｍｅｔｈｏｄｓ ｂｙｅｘｐｅｒｉｍｅｎｔｓ．Ｉｎ ｓｔｕｄｉｅｓ ｏｆｔｉｍｅ ｓｅｒｉｅｓ ｐｒｅｄｉｃｔｉｏｎ，ｔｒａｄｉｔｉｏｎａｌ ｍｅｔｈｏｄｓ ａｒｅ ａｉｍｅｄ ａｔ ｔｈｅ ｎｅｘｔ ｐｏｉｎｔ．ｗｈｉｌｅ ｗｅ ａｒｅ ｉｎｔｅｒｅｓｔｅｄ ｉｎ ｔｈｅ ｎｅｘｔ ｉｍｐｏｒｔａｎｔｅｖｅｎｔｓｅｖｅｎｔ．Ｗｅｐｒｏｐｏｓｅａｎｅｗ ｐｒｅｄｉｃｔｉｏｎ ｍｏｄｅｌ ｂａｓｅｄｏｎｆｅａｔｕｒｅｓ．Ｉｔ ｆｉｒｓｔｃｏｎｖｅｒｔｓ ｅｖｅｎｔｓｓｅｒｉｅｓ ｔｏ ｆｅａｔｕｒｅｓ ｓｅｒｉｅｓ；ａｐｐｌｙ ｆｅａｔｕｒｅ ｓｅｌｅｃｔｉｏｎ；ｔｈｅｎｍａｋｅｓ ｐｒｅｄｉｃｔｉｏｎｓ ｔｏ ｆｅａｔｕｒｅｓ ｏｆ ｆｕｔｕｒｅ ｔｉｍｅ ｓｅｒｉｅｓ ｉｎ ｄｉｆｆｅｒｅｎｔｅｖｅｎｔｓ．Ｗｅａｎａｌｙｚｅ ａｎｄ ｄｅｆｉｎｅ ｔｈｅ ｐｒｅｄｉｃｔａｂｉｌｉｔｙ ｏｆｓｃａｌｅｓ，ａｎｄｒｅｖｅｒｔ ｔｈｅ ｆｅａｔｕｒｅｓ ｐｒｅｄｉｃｔｉｏｎ ｔｏ ｅｖｅｎｔｓｐｒｅｄｉｃｔｉｏｎ．Ｗｅｓｔｕｄｙｆｅａｔｕｒｅ ｓｅｌｅｃｔｉｏｎ ｐｒｏｂｌｅｍｓ ｉｎ ｔｈｅ ｔｈｅｓｉｓ，ｗｈｉｃｈ ｉｓ ｔｈｅ ｐｒｅｍｉｓｅ ｏｆ ｅｆｆｅｃｔｉｖｅｎｅｓｓ ｏｆ ｍａｎｙ ｍａｃｈｉｎｅ Ｌｅａｒｎｉｎｇ ａｌｇｏｒｉｔｈｍｓ ｉｎｃｌｕｄｉｎｇ ｐｒｅｄｉｃｔｉｏｎ ｅｆｆｅｃｔｓｏｎ ａｍｅｔｈｏｄｓ，ｒｅｄｕｎｄａｎｔｉｎｆｏｒｍａｔｉｏｎ ｈａｖｅ ｂａｄａｌｇｏｒｉｔｈｍｓ’ｐｅｒｆｏｒｍａｎｃｅｓＷｅｄｉｓｃｕｓｓ ｔｈｅ ｃｕｒｒｅｎｔ ｆｅａｔｕｒｅ ｓｅｌｅｃｔｉｏｎ ａｐｐｒｏａｃｈｅｓ；ｏｎｐｒｏｐｏｓｅｒｅｆｉｎｅｄ ｖｅｒｓｉｏｎ ｏｆｏｎｅ ｓｅｌｅｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄｆｒａｃｔａｉ ｄｉｍｅｎｓｉｏｎＷｅ ｓｔｕｄｙｔｈｅ ａｂｏｖｅ ｔｈｒｅｅ ａｓｐｅｃｔｓ ｉｎ ｔｉｍｅ ｓｅｒｉｅｓ ｍｉｎｉｎｇ：ｓｅａｒｃｈｉｎｇ ｓｉｍｉｌａｒ ｐａｔｔｅｒｎｓ，ｐａｔｔｅｒｎｓｅｘｔｒａｃｔｉｎｇ ｕｓｅｆｕｌ ｔｅｍｐｏｒａｌａｕｔｏｍａｔｉｃａｌｌｙ，ａｎｄ ａｎａｌｙｚｉｎｇ ｔｈｅｅｖｅｎｔｓｐｒｅｄｉｃｔｉｏｎｐｒｏｂｌｅｍｓ．Ｔｈｅ ｍａｉｎ ｗｏｒｋ ａｎｄ ｉｎｎｏｖａｔｉｏｎｓ ｏｆｔｈｅ ｔｈｅｓｉｓ ａｒｅ：（１）Ｗｅｐｒｏｐｏｓｅ ｅｖｅｎｔ ｓｅｒｉｅｓ，ａ ｎｅｗ ｆｅａｔｕｒｅ ｒｅｐｒｅｓｅｎｔａｔｉｏｎ ｍｅｔｈｏｄ ｏｆｔｉｍｅ ｓｅｒｉｅｓ．Ｂａｓｅｄｏｎｉｔ，ｗｅ ｐｒｏｐｏｓｅａｎｄｉｍｐｌｅｍｅｎｔａｍｏｄｉｆｉｅｄ ｍｕｌｔｉ－ｄｉｍｅｎｓｉｏｎａｌ ｉｎｄｅｘ ｓｔｒｕｃｔｕｒｅ ａｎｄ ｓｉｍｉｌａｒａｐａｔｔｅｒｎ ｍａｔｃｈｉｎｇ ａｌｇｏｒｉｔｈｍｓ Ｔｈｅ ｅｘｐｅｒｉｍｅｎｔｓ ｐｒｏｖｅ ｔｈａｔ ｉｔ ｈａｓｏｌｄｅｒｏｎｅｓ． ｏｎ ｅｖｅｎｔｂｅｔｔｅｒ ｐｅｒｆｏｒｍａｎｃｅｏｖｅｒｔｈｅ（２）Ｂａｓｅｄｂａｓｅｄｏｎｓｅｒｉｅｓ，ｗｅ ｐｒｏｐｏｓｅａｎｄ ｉｍｐｌｅｍｅｎｔ ｎｅｗ ｐａｔｔｅｒｎ ｄｉｓｃｏｖｅｒｙ ａｌｇｏｒｉｔｈｍｓａｓｓｏｃｉａｔｉｏｎ ｒｕｌｅｓ ａｎｄ ｃｌｕｓｔｅｒｉｎｇ ｍｅｔｈｏｄｓ．Ｓｉｎｃｅ ｅｖｅｎｔｓ ｓｅｒｉｅｓ ａｒｅ ｔｉｍｅ ｒｅｌａｔｅｄ，ｗｅａｎｅｅｄ ｔｏ ｍａｋｅ ｄａｔａｂａｓｅｓｌｏｔ ｏｆ ｉｍｐｒｏｖｅｍｅｎｔｓｏｎｔｒａｄｉｔｉｏｎａｌ ｍｉｎｉｎｇ ａｌｇｏｒｉｔｈｍｓ ｂａｓｅｄＯｆｆｔｒａｎｓａｃｔｉｏｎａｌ（３）Ｗｅｐｒｏｐｏｓｅａｎｄ ｉｍｐｌｅｍｅｎｔａｎｅｗ ｐｒｅｄｉｃｔｉｏｎ ｍｏｄｅｌ ｔｈｒｏｕｇｈ ｅｖｅｎｔｓ ｆｅａｔｕｒｅｓ，ｔｏｆｏｒｅｃａｓｔ ｔｈｅ ｃｈａｎｇｉｎｇ ｔｒｅｎｄｓ ｏｆ ｆｕｔｕｒｅｅｖｅｎｔｅｖｅｎｔｓ．Ｗｅｄｅｆｉｎｅ ａｎｄ ａｎａｌｙｚｅ ｔｈｅ ｐｒｅｄｉｃｔａｂｉｌｉｔｙ ｏｆｓｅｒｉｅｓ ｉｎ ｍｕｌｔｉ ｓｃａｌａｂｉｌｉｔｉｅｓ．Ａｓ ａｎｏｔｈｅｒ ａｓｐｅｃｔ，ｗｅ ｓｔｕｄｙ ｔｈｅ ｆｅａｔｕｒｅ ｓｅｌｅｃｔｉｏｎ ｐｒｏｂｌｅｍ，ａａｎｄ ｐｒｏｐｏｓｅ ｔｈｅ ｄａｔａｓｅｔｒｅｆｉｎｅｄ ａｌｇｏｒｉｔｈｍ，ｗｈｉｃｈ ｉｓ ｔｏ ｅｘｔｒａｃｔ ｔｈｅ ｍｏｓｔ ｒｅｐｒｅｓｅｎｔａｔｉｖｅ ａｔｔｒｉｂｕｔｅｓ ｆｒｏｍＷｅ ｍａｋｅｅｘｐｅｒｉｍｅｎｔｓ ｂａｓｅｄｏｎｓｏｍｅ ｃｌａｓｓｉｃａｌ ｔｉｍｅ ｓｅｒｉｅｓ ｄａｔａａｎｄｒｅａｌ ｄａｔａｓｅｔｓ ｓｕｃｈａａｓｓｔｏｃｋ ｄａｔａ，ｔｏ ｖａｌｉｄａｔｅ ｔｈｅ ａｂｏｖｅ ｓｔｕｄｉｅｓ．Ａｔ ｔｈｅ ｓａｍｅ ｔｉｍｅ，ｗｅ ｄｅｖｅｌｏｐ ｐｒｅｄｉｃｔｉｏｎ ｓｙｓｔｅｍ ｂａｓｅｄｏｎｐｏｗｅｒ ｌｏａｄｅｌｅｃｔｒｉｃ ｄａｔａ．Ｂｙ ｍｉｎｉｎｇ ｔｈｒｏｕｇｈ ｌａｒｇｅ ｔｉｍｅ－ｒｅｌａｔｅｄ ｈｉｓｔｏｒｉｃａｌ ｌｏａｄｃａｌｌａｎｄ ｗｅａｔｈｅｒ ｄａｔａ，ｔｈｅ ｓｙｓｔｅｍｅｘｔｒａｃｔ ｓｏｍｅ ｖａｌｕａｂｌｅ ｉｎｆｏｒｍａｔｉｏｎ ａｎｄ ｕｔｉｌｉｚｅ ｔｈｅｍ ｆｏｒｓｈｏｒｔ－ｔｅｒｍ ｌｏａｄ ｐｒｅｄｉｃｔｉｏｎ．Ｋｅｙｗｏｒｄｓ：Ｄａｔａ ｍｉｎｉｎｇ，Ｔｉｍｅ ｓｅｒｉｅｓ，Ｅｖｅｎｔ ｓｅｒｉｅｓ，Ｐａｔｔｅｒｎ ｍａｔｃｈｉｎｇ，Ｐａｔｔｅｒｎ ｄｉｓｃｏｖｅｒｙ，Ｅｖｅｎｔｓ ｐｒｅｄｉｃｔｉｏｎ．ＩＶ中国科学技术大学博士学位论文第一章绪论第一章绪论在信息化社会的今天，现代化的社会生产和科学研究搜集了大量数据和重要信息。 与此相应的是现实世界数据库所存储和处理的数据的规模越来越大，在这些海量数据中 蕴藏着大量未知的有价值的信息，这些重要信息可以很好地支持人们的决策。目前数据 库系统所能做到的只是对数据库中已有的数据进行存取，人们通过这些数据所获得的信 息量仅仅是整个数据库所包含的信息量的一部分，隐藏在这些数据之后的更重要的信息 是关于这些数据的整体特征的描述及对其发展趋势的预测，这些信息在决策生成的过程 中具有重要的参考价值。但是超大数据量与无结构化，使得传统的手工和统计方法或者 不经济，或者在某些情况下几乎就不可能从中获得有意义的模式。 信息技术飞速发展的同时，人工智能领域的研究也取得很大进展，机器学习、智能 体和规划等分支的成功理论和技术为知识发现的研究和应用提供了强有力的工具。特别 是在机器学习领域，根据人类学习的不同模式人们提出了很多机器学习方法，如实例学习、观察和发现学习、决策树、神经网络和遗传算法等等。其中某些常用且较成熟的算法已被人们运用于实际的应用系统中。 正是由于数据库技术和机器学习技术的发展，也是为了满足人们实际工作中的需 要．数据库中的知识发现（ＫｎｏｗｌｅｄｇｅＤｉｓｃｏｖｅｒｙｉｎＤａｔａｂａｓｅ，ＫＤＤ）技术逐渐发展起来。 数据库知识发现的研究具有广阔的应用背景和深远的理论意义，是未来人工智能与数据 库研究的热点前沿课题之－－［Ｃｈｅｎ ｅｔ ａｌ，１９９６】。１．１知识发现概述知识发现是一个交叉学科，涉及到数据库、人工智能和统计学等领域。从一开始， 人们就针对ＫＤＤ的不同方面下过很多定义。随着研究的不断深入，对ＫＤＤ的理解越 来越全面。１．１．１知识发现定义定义数据库中的知识发现是从大量的实际应用数据中，提取隐含的、新颖的、潜在 有用的信息和知识的非平凡过程［Ｆａｙｙａｄ ｅｔ ａｌ，１９９６ａ】。 在这里，数据是指一个有关事实Ｆ的集合，它是用来描述事务有关方面的信息；信 息或模式是对于集合Ｆ中的数据或数据子集相对应的模型的紧致描述。ＫＤＤ是一个多 步骤的处理过程，其大部分阶段是系统自动进行的而无需人工干预。ＫＤＤ提取出的模 式必须是新颖的和可被人理解的，从而帮助人们更好地了解数据库中包含的信息。 数据挖掘（Ｄａｔａ Ｍｉｎｉｎｇ）是知识发现过程中的一个核心步骤，采用特定的算法，在可 接受的计算成本下，从数据集中搜索人们感兴趣的模式。但数据挖掘并不是知识发现的 全部，知识发现还包括其他步骤，如数据选择和预处理、对挖掘结果进行恰当的评价和解释等［Ｆａｙｙａｄ ｅｔ ａｌ，１９９６ａ；１９９６ｂ］，这些对有效的知识发现过程来说也是必不可少的。！生里型兰兰兰查２兰羔坚三兰羔竺兰塞１．１．２知识发现处理过程模型苎二兰竺笙ＫＤＤ是一个多阶段的处理过程，一个完整的知识发现的过程可分为九个处理阶段， 包括数据准备、数据选择、数据预处理、数据缩减、ＫＤＤ目标确定、挖掘算法确定、 数据挖掘、模式解释及知识评价，～个掠影如图１．１。图１．１知识发现的过程（１）数据准备：了解ＫＤＤ相关领域的有关情况，熟悉有关的背景知识，并弄清楚用户 的要求。 （２）数据选择：根据用户的要求从数据库中提取与ＫＤＤ相关的数据，ＫＤＤ将主要从 这些数据中进行知识提取，此过程中会利用一些数据库操作对数据进行处理。 （３）数据预处理：主要是对数据选择产生的数据进行再加工，检查数据的完整性和～ 致性，对其中的噪音数据进行处理，对丢失的数据可以利用统计方法进行填补。（４）数据缩减：对经过预处理的数据，根据知识发现的任务对数据进行再处理，主要通过投影或数据库中的其他操作减少数据量。 （５）确定ＫＤＤ的目标：根据用户的要求，确定ＫＤＤ是发现何种类型的知识，因为对 ＫＤＤ的不同要求需要在具体的知识发现过程中采用不同的知识发现算法。 （６）确定知识发现算法：根据所确定的任务，选择合适的知识发现算法，这包括选取 合适的模型和参数，并使得知识发现算法与整个ＫＤＤ的评判标准相一致。 （７）数据挖掘：运用选定的知识发现算法，从数据中提取出用户所需要的知识，并以 一种特定或一些常用的方式表示，如产生式规则。 （８）模式解释：对发现的模式进行解释。通常为了取得更为有效的知识，可能会返回 前面处理步骤中的某些步骤以进行反复提取。 （９）知识评价：将发现的知识以用户能了解的方式呈现给用户，也包含对知识的一致 性的检查，以确信本次发现的知识不与以前发现的知识相抵触。２中国科学技术大学博士学位论文第一章绪论在上述的每个处理阶段ＫＤＤ系统会提供处理工具完成相应的工作。在对挖掘的知 识进行评测后，根据结果可以决定是否重新进行某些处理过程，在处理的任意阶段都可 以返回以前的阶段进行再处理。 １．１．３数据挖掘技术的分类 数据挖掘技术有不同的分类标准。按发现的知识类型，可分为关联规则发现、序贯 模式发现、分类、聚类、偏差检测、时序分析等；按发现的驱动模式，可分为自治的发 现、数据驱动的、查询驱动的和交互式的数据挖掘；按使用的机器学习方法，可分为基于归纳学习、基子演绎学习和基于类比学习的数据挖掘方法。 （Ｉ）关联规则（Ａｓｓｏｃｉａｔｉｏｎ Ｒｕｌｅｓ）反映一个事件和其他事件之间依赖或关联的知识［Ｈａｌｌ＆Ｆｕ，１９９５］。如果两项或多项 属性之间存在关联，那么其中一项的属性值就可以依据其他属性值进行预测。关联规则 展示了属性．值频繁地在给定数据集中一起出现的条件，最为著名的发现方法是Ａｐｒｉｏｒｉ 算法［Ａｇｒａｗａｌ，１９９３ａ】。关联规则的发现可分为两步。第一步是迭代识别所有的频繁项目 集，要求频繁项目集的支持率不低于用户设定的最低值；第二步是从频繁项目集中构造 可信度不低于用户设定的最低值的规则。识别或发现所有频繁项目集是关联规则发现算 法的核心，也是计算量最大的部分［Ａｇｒａｗａｌ＆Ｓｒｉｋａｎｔ，１９９４】。很多工作是关于频繁项目集的计算【路＆卢，２００１；朱等，２００３】。事务数据库中每个事务是一个项（ｉｔｅｍ）的集合，关联规则发现所有满足一定条件的形如工＝》Ｙ的规则，其中Ｘ＝Ａｌ八…八Ａ。，Ｙ＝Ｂｌ八…八风是项的集合，其直观意义就是事务数据库中含有ｚ的事务也包含ｊ，。例如，９８％的购买尿布和婴儿食品的人同时会 购买啤酒。关联规则的实际应用包括市场交易分析、直销的邮购广告、医疗保险的欺诈检测以及商场的货架摆放等。 （２）分类（Ｃｌａｓｓ墒ｃａｔｉｏｎ）它反映同类事物共同性质的特征型知识和不同事物之间的差异型特征知识。最为典 型的分类方法是基于决策树的分类方法［Ｑｕｉｎｌａｎ，１９８６］。它是从实例集中构造决策树， 是一种有指导的学习方法。数据库中的每个元组有一个类的标识，通过对训练数据集的 分析，形成决策树，如果该树不能对所有对象给出正确的分类，那么选择一些例外加入 到窗口中，重复该过程直至建立每个类的一个较为精确的描述模式，可以利用该模式对 未知数据进行分类［Ｂｒｅｉｍａｎ，１９８４；Ｑｕｉｎｌａｎ，１９９３］。决策树的叶结点是类名，中间结点是 带有分枝的属性，分枝对应该属性的某一可能值。例如，通过分析以往的汽车销售情况 可以得到类描述：“年龄小于２５岁且收入大于４万的人通常是购买赛车”，这个描述可 以被用来预测新客户的购买行为。分类找出描述和区分数据类或概念的模型（或函数）， 以便能够使用模型预测未知类别的对象。分类的实际应用包括信用卡的客户分析、银行 的位置分布、疾病治疗方法的有效性分析等。决策树和规则归纳主要用于构造预测类的 模型【Ａｐｔｅ＆Ｈｏｎ８，１９９６］，也可用于构造描述型的模型。中国科学技术大学博士学位论文第一章绪论最为典型的决策树学习系统是ＩＤ３，它采用自顶向下不回溯策略，能保证产生一棵 简单的树。算法Ｃ４．５和Ｃ５．０都是ＩＤ３的扩展，它们将分类领域从类别属性扩展到数值 型属性［Ｑｕｉｎｌａｎ，１９９３；Ｃｈｅｎ ｅｔ ａｌ，１９９６］。数据分类还有归纳和演绎［Ｋａｍｂｅｒ，１９９７］、统计 ［Ｅｌｄｅｒ＆Ｐｒｅｇｉｂｏｎ，１９９６］、粗糙集（ＲｏｕｇｈＳｅｔ）【Ｐａｗｌａｋ，１９９１］等方法。线性回归和线性辨 别分析是典型的统计模型。为降低决策树生成代价，人们还提出了一种区间分类器。最 近也有人研究使用神经网络方法［Ｌｕｅｔａｌ，１９９５］和Ｂａｙｅｓｉａｎ方法［Ｈｅｃｋｅｒｍａｎ，１９９６］在数据库中进行分类和规则提取。［ＭｕＳｈｙ，１９９８１给出了构建决策树的综述。（３）聚类（Ｃｌｕｓｔｅｒｉｎｇ）对数据库中的元组进行分类，使得在同一类中的数据相似性最大，而类与类之间的 相似性最小。聚类处理的数据与分类相似，但数据没有类的标识，是一种在无导师的情 况下，根据样本间的相似程度自动地进行分类的方法。聚类的实际应用包括市场细分、 客户分类、销售数据分类和广告群体分析等。现有的聚类方法有基于层次的方法，如ＢＩＲＣＨ［Ｚｈａｎｇ【Ａｇｒａｗａｌｅｔｅｔａ１．１９９６］和ＣＬｒＲＥ［Ｇｕｈａ，１９９８］；基于密度的方法，如ＤＢＳＡＣＮ ＩＥｓｔｅｒ ｅｔｅｔａｌ，１９９６１，ＯＰＴＩＣＳ［Ａｎｋｅｒｓｔａｌ，１９９９ｂ］，ＤＥＮＣＬＵＥ［Ｈｉｎｎｅｂｕｒｇ＆Ｋｅｉｍ，１９９８］，ＣＬＩＱＵＥｅｔａｌ，１９９８］：基于网格的方法ＳＴＩＮＧ［Ｗａｎｇａｌ，１９９７］；基于模型的方法［Ｆｉｓｈｅｒ，１９８７］；基于小波的多分辨率聚类方法ＷａｖｅＣｌｕｓｔｅｒ［Ｓｈｅｉｋｈｏｌｅｓｌａｍｉ ｅｔ ａｌ，１９９Ｓ］等。 （４）序贯模式（ＳｅｑｕｅｎｔｉａｌＰａｔｔｅｒｎｓ）事务数据库中的一个事务序列是～组按事务时间排列的事务，序贯模式发现所有不 小于指定的最小支持度阈值的顺序模式。例如，１０％购买计算机的客户在随后的交易中 会升级内存。序贯模式［Ａｇｒａｗａｌ＆Ｓｒｉｋａｎｔ，１９９５；Ｓｆｉｋａｎｔ＆Ａｇｒａｗａｌ，１９９６；Ｓｅｎｏ＆Ｋａｒｙｐｉｓ， ２００２；欧阳等，１９９７】的发现方法与关联规则类似，但关联规则描述的是交易内部 （ｉｎｔｒａ－ｔｒａｎｓａｃｔｉｏｎ）的项集之间的关联，序贯模式描述的是交易之间（ｉｍｅｒ－ｔｒａｎｓａｃｔｉｏｎ）的关联。（５）时间序列分析（ＴｉｍｅＳｅｑｕｅｎｃｅｓＡｎａｌｙｓｉｓ）和预测（Ｐｒｅｄｉｃｔｉｏｎ）分析时间序列随时间变化的规律或趋势，由历史的和当前的数据去推测未来的数据。 时间序列分析包括传统的时序分析模型、序列或周期模式发现、基于类似性的数据分析 和预测等。相似时间序列分析（Ｓｉｍｉｌａｒ Ｔｉｍｅ Ｓｅｑｕｅｎｃｅｓ）在时间序列数据库中发现与给定 序列相似的所有序列，或发现所有相似的时间序列对。例如，发现具有相似销售模式的 商品。时序分析的实际应用包括金融市场分析、销售数据分析、科学数据库和医疗诊断等。目前，时间序列预测方法有经典的统计方法、神经网络【袁，１９９９］和机器学习等［Ｂａｎｓａｌｅｔａｌ，１９９８】。Ｂｏｘ和Ｊｅｎｋｉｎｓ提出了一套比较完善的时间序列建模理论和分析方法【Ｂｏｘ＆Ｊｅｎｋｉｎｓ，１９７６】，这些经典的数学方法通过建立随机模型，如自回归模型、自回归 滑动平均模型、求和自回归滑动平均模型和季节调整模型等，进行时间序列的预测。由 于大量的时间序列是非平稳的，其特征参数和数据分布随着时间的推移而发生变化。因４！鱼型堂塾查奎堂堕主兰堡垒奎苎二童竺笙此，仅仅通过对某段历史数据的训练，建立单一的神经网络预测模型，还无法完成准确 的预测任务。为此，人们提出了基于统计学和基于精确性的再训练方法，当发现现存预 测模型不再适用于当前数据时，对模型重新训练，获得新的权重参数，建立新的模型。 也有许多系统借助并行算法的计算优势进行时间序列预测。（６）广义知识发现（Ｇｅｎｅｒａｌｉｚａｔｉｏｎ） 广义知识指数据类别特征的概括性描述知识。根据数据的微观特性发现其表征的、带有普遍性的、较高层次概念的、中观和宏观的知识，反映同类事物共同性质，是对数 据的概括、精炼和抽象［Ｃｈｅｎｅｔａｌ，１９９６１。广义知识的发现方法和实现技术有很多，如数据立方体、面向属性的归约等。数据立方体还有其他一些别名，如多维数据库、实现视图、ＯＬＡＰ等。该方法的基本思想是 实现某些常用的代价较高的聚集函数的计算，诸如计数、求和、平均、最大值等，并将 这些实现视图储存在多维数据库中。既然很多聚集函数需经常重复计算，那么在多维数 据立方体中存放预先计算好的结果将能保证快速响应，并可灵活地提供不同角度和不同 抽象层次上的数据视图。另一种广义知识发现方法是加拿大Ｓｉｍｏｎ Ｆｒａｓｅｒ大学提出的面 向属性的归约方法［Ｈａｎ，１９９８］。这种方法以类ＳＱＬ语言表示数据挖掘查询，收集数据库 中的相关数据集，然后在相关数据集上应用一系列数据推广技术进行数据推广。包括属 性删除、概念树提升、属性阙值控制、计数及其他聚集函数传播等。 数据可以与类或概念相关联，例如在电子产品商店，销售的商品类包括计算机和打 印机，顾客概念包括大客户和小客户等。广义知识发现用汇总的、简洁的、精确的方式 描述每个类和概念，可通过以下方法得到：１）数据特征化，对目标类数据的一般特征 或特性进行汇总；２）数据区分，将目标类与一个或多个比较类比较；３）数据特征化和比较。（７）偏差（Ｄｅｖｉａｔｉｏｎ）和孤立点分析（ＯｕｔｌｉｅｒＤｉｓｃｏｖｅｒｙ）偏差和孤立点［Ａｒｎｉｎｇｃｔａｌ，１９９６］是那些在某些特征上与数据库中的大部分数据有显著的不同的数据，是对差异和极端特例的描述，揭示事物偏离常规的异常现象，如标准 类外的特例、数据聚类外的离群值等［Ｋｎｏｒｒ＆Ｎｇ，１９９８；Ｂａｒｎｅｔｔ＆Ｌｅｗｉｓ，１９９４；Ｒａｍａｓｗａｍｙ ｅｔａｌ，２０００１。所有这些知识都可以在不同的概念层次上被发现，并随着概念层次的提升，从微观到中观、到宏观，以满足不同用户不同层次决策的需要。 大部分数据挖掘方法将孤立点视为噪声或异常而丢弃，然后在一些应用中，罕见的 事件可能比那些正常出现的事件更让人感兴趣。孤立点分析的实际应用包括信用卡欺诈 检测、电信欺诈检测、客户分类和医学分析等。 知识发现是一个交叉学科，除了上面介绍的常用的方法之外，还可以运用人工神经 网络、遗传算法、粗糙集、基于范例的推理、模糊技术和统计分析等方法，进行知识的 提取和分析。 １．１．４知识发现的发展状况中国科学技术大学博士学位论文第一章绪论从数据库中发现知识（ＫＤＤ）一词首次出现在１９８９年举行的第十一届国际联合人 工智能学术会议上。最初由美国人工智能协会主办的ＫＤＤ国际研讨会，规模由原来的 专题讨论会发展到国际学术大会（ＡＣＭ ＳＩＧＫＤＤ，ｈｔｔｐ：／／ｗｗｗ．ａｃｍ．ｏ叫ｓｉｇｋｄｄ／），研究重 点也逐渐从发现方法转向系统应用，注重多种发现策略和技术的集成，以及多种学科之间的相互渗透。ＩＥＥＥ的Ｋｎｏｗｌｅｄｇｅ ａｎｄＤａｔａＥｎｇｉｎｅｅｒｉｎｇ会刊率先在１９９３年出版了ＫＤＤ技术专刊。并行计算、计算机网络和信息工程等其他领域的国际学会学刊也把数据挖掘 和知识发现列为专题和专刊讨论。所有这些大会和研讨会都对该领域的兴起和蓬勃发展 起了巨大的推动作用，大大促进了多领域多学科的交叉和渗透，在国际上逐渐形成了 ＫＤＤ的研究热点和高潮。 比较权威的国际会议除了ＳＩＧＫＤＤ还有：ＶＬＤＢ（ＶｅｒｙＡＣＭＣｏｎｆｅｒｅｎｃｅｏｎＬａｒｇｅ ＤａｔａｂａｓｅＣｏｎｆｅｒｅｎｃｅ），ｏｎＭａｎａｇｅｍｅｎｔ ｏｆ Ｄａｔａ，ＩＣＤＥ（Ｉｎｔｅｍａｔｉｏｎａｌ ＣｏｎｆｅｒｅｎｃｅＣｏｎｆｅｒｅｎｃｅ Ｋｎｏｗｌｅｄｇｅ Ｄｉｓｃｏｖｅｒｙ ａｎｄ ＤａｔａＤａｔａＥｎｇｉｎｅｅｒｉｎｇ），ＦＯＤＯ（ＩｎｔｅｍａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅ ｏｆ Ｆｏｕｎｄａｔｉｏｎｓ ｏｆ Ｄａｔａ Ｏｒｇａｎｉｚａｔｉｏｎ ａｎｄｏｎＡｌｇｏｒｉｔｈｍｓ），ＰＡＫＤＤ（Ｐａｃｉｆｉｃ?ＡｓｉａＭｉｎｉｎｇ）等。此外，在Ｉｎｔｅｒｎｅｔ上还有不少ＫＤＤ电子出版物，其中以半月刊ＫＤＮｕｇｇｅｔｓ最为权威（ｈｔｔｐ：／／ｗｗｗ．ｋｄｎｕｇｇｅｔｓ ｃｏｒｎ／ｓｕｂｓｃｒｉｂｅ．ｈｔｍｌ）。与国外相比，国内对ＫＤＤ的研究稍晚，１９９３年国家自然科学基金首次支持对该领 域的研究项目。一方面有很多国际会议在国内召开，如ＰＡＫＤＤ，另一方面，国内也自 发组织了很多相关的会议，如两年一次的机器学习学术会议（已召开了８届）等，这些 都大大促进了知识发现的基础理论和应用研究。ＤＭＧｒｏｕｐ（ｈｔｔｐ：／／ｗｗｗ．ｄｍｇｒｏｕｐ．ｏｒｇ．ｃｎ ／ｚｓ．ｈｔｍ）是比较有影响力的数据挖掘讨论组；［蔡，１９９６；史，１９９８］是国内人工智能界的流 行教材；【史，２００２］是国内第一批关于知识发现系统介绍的书。【Ｚｈｏｕ，２００３］是从三个角 度；数据库、机器学习和统计，对较新的三本数据挖掘书（（Ｄａｔａ Ｍｉｎｉｎｇ：Ｃｏｎｃｅｐｔｓ Ｔｅｃｈｎｉｑｕｅｓ》【Ｈａｎ＆Ｋａｍｂｅｒ，２００１］、（（Ｄａｔａ Ｍｉｎｉｎｇ：Ｐｒａｃｔｉｃａｌ Ｍａｃｈｉｎｅ Ｌｅａｒｎｉｎｇ ＴｏｏｌｓＴｅｃｈｎｉｑｕｅｓ ｗｉｔｈ Ｊａｖａ ａｎｄ ａｎｄＩｍｐｌｅｍｅｎｔａｔｉｏｎｓ））和《Ｐｒｉｎｃｉｐｌｅｓ ｏｆＤａｔａ Ｍｉｎｉｎｇ））的回顾。数据挖掘的发展虽然只有短短数年时间，但各种系统却有如雨后春笋般大量涌现。 目前，世界上比较有影响的典型数据挖掘系统有：（１）ＩｎｔｅｌｌｉｇｅｎｔＭｉｎｅｒｍＭ公司的数据挖掘产品，提供了很多数据挖掘算法，包括关联、分类、回归、预 测模型、偏离监测、序列模式和聚类。同时提供一个应用工具集，包括神经网络算法、 统计方法、数据准备模型和数据可视化工具。Ｉｎｔｅｌｌｉｇｅｎｔ Ｍｉｎｅｒ的特色有：一是数据挖掘 算法的可伸缩性；二是它与ⅢＭ ＤＢ／２关系数据库紧密地结合在一起。（２）Ｅｎｔｅｒｐｒｉｓｅ Ｍｉｎｅｒ是ＳＡＳ公司开发的产品（ｈｔｔｐ：／／ｗｗｗ．ｓａｓ ｃｏｍ），提供多种数据挖掘算法，包括回归、 分类和统计分析包。特色是具有多种统计分析工具，这得益于ＳＡＳ公司在统计分析市 场多年的经验和历史。（３）ＭｉｎｅＳｅｔ６！』堕燮查盔兰苎圭堂堡垒苎是由ＳＧＩ公司（ＳｉｌｉｃｏｎＧｒａｐｈｉｃｓ塑二兰丝笙Ｉｎｃ）开发的（ｈｔｔｐ：／／ｗｗｗ．ｓｇｉ．ｃｏｍ）。它也提供了多种数据挖掘算法，包括关联和分类以及高级统计和可视化工具。特色是具有强大的图形工具 （利用ＳＯｌ计算机强大的图形能力），包括规则可视化工具、树可视化工具、地图可视 化工具和多维数据分散可视化工具，用于实现数据和数据挖掘结果的可视化。（４）Ｃｌｅｍｅｎｔｉｎｅ由ＩＳＬ公（ＩｎｔｅｇｒａｌＳｏｌｕｔｉｏｎｓＬｔｄ）开发的（ｈｔｔｐ：／／ｗｗｗ．ｉｓｌＣＯｕｋ）。它为终端用户和开发者提供了一个集成的数据挖掘开发环境。系统集成了多种数据挖掘算法，如规则归纳、 神经网络、分类和可视化工具。特色是具有面向对象的扩展的模块接口，该接口使用户 算法和工具可以加到Ｃｌｅｍｅｎｔｉｎｅ的可视化编程环境中。ＩＳＬ已被ＳＰＳＳ公司收购。（５）ＤＢＭｉｎｅｒ是由ＤＢＭｉｎｅｒ Ｔｅｃｈｎｏｌｏｇｙ公司开发的（ｈｔｔｐ：／／ｄｂ．ｃｓ．ｓｆｕ．ｃａ），提供多种挖掘算法，包括发现驱动的ＯＬＡＰ分析、关联、分类和聚类。特色是基于立方体的联机分析挖掘，包括 多种有效的频繁模式挖掘功能和集成的可视化分类方法［Ｈａｎ １．１．５数据挖掘技术的应用 数据挖掘的应用范围非常广泛，可以说，几乎任何一个涉及到数据存储的行业，都 可以使用数据挖掘技术提高其管理水平和盈利能力。比较典型的有： （１）生物医学和ＤＮＡ数据分析的挖掘 在过去的几十年中，生物医学研究取得了迅猛的发展，其大量研究都集中在ＤＮＡ 数据的分析上，其中一个重点是ＤＮＡ序列的研究，因为这种序列构成了所有活的生物体的基因代码的基础。具有挑战性的是从中找出导致各种疾病的特定基因序列模式。由ｅｔａｌ，１９９６］。于在数据挖掘中已经有许多有意义的序列模式分析和相似模式检索技术，因此数据挖掘 成为ＤＮＡ分析的强有力的工具，并在以下几个方面做出了突出的贡献：１）异构、分布 式基因数据库的语义集成；２）ＤＮＡ序列间相似搜索和比较；对分别来自带病和健康的 基因序列，进行比较以识别两类基因间的主要差异。做法可以是首先从两类基因中检索 出基因序列，然后找出并比较每一类中频繁出现的模式。通常，在带病样本中出现频度超出健康样本的序列，可以认为是导致疾病的基因因素；另一方面，在健康样本中出现频度超出带病样本的序列，可以认为是抗疾病的因素。频繁序列模式的分析在基因序列 相似和非相似分析中非常重要；３）关联分析：同时出现的基因序列的识别；４）路径分 析：发现在疾病不同阶段的致病基因：５）可视化工具和遗传数据分析。 （２）零售业中的数据挖掘 零售业积累了大量的销售数据，是目前数据挖掘的主要应用领域。零售数据挖掘可 有助于识别顾客购买行为，发现顾客购买模式和趋势，改进服务质量，实现更好的顾客 保持力和满意程度，提高货品销量比率，设计更好的货品运输与分销策略，减少商业成 本。例如，基于数据挖掘的数据仓库的设计与构造；销售、顾客、产品和地区的多维分 析；促销活动的有效性分析；顾客保持力―顾客忠诚分析；购买推荐和商品参照等。７中国科学技术大学博士学位论文第一章绪论（３）金融和电信业中的数据挖掘 金融领域的应用包括数据仓库的构建和多维数据分析、贷款偿还预测和客户信用政策分析、对目标市场客户的分类和聚类、洗黑钱和其他金融犯罪的侦破。阻ａｌｌ，１９９６］研 究了机器学习算法在证券投资和管理中的应用。电信市场的竞争日益激烈化，利用数据挖掘技术来帮助理解商业行为，确定电信模 式和捕捉盗用行为，更好地利用资源和提高服务质量是非常必要的。数据挖掘可以从以 下几个方面改进电信服务：电信数据的多维分析。盗用模式分析和异常模式识别，多维 关联和序列模式分析等。 因此，知识发现技术无论在商业领域还是科学研究上都具有广阔的发展前景。１．２时间序列技术时间序列是～串随时间变化的数据组成的序列，反映了属性值在时间顺序上的特 征。现实世界中大量数据的采集与时间相关，数据具有时间上的关联性。因此，时间序 列问题是数据挖掘中的一类非常重要的问题。利用时间序列模式的数据挖掘，可以得到 数据中蕴含的与时间相关的有用信息，实现知识的提取。 时问序列，简称为时序，其取值一般在等时间间隔上度量［Ｈａｎ＆Ｋａｍｂｅｒ，２００１１。分 析这些序列的方法称作时间序列分析，也称时序分析。时间序列Ｘ是一个观察数据序列，肛∽，Ｏ≤ｆ＜帆其中ｔ是时间索引，Ⅳ是观察个数。时间序列分析是工程学、科学和商业应用领域的～种基本分析工具。学者们研究随 着时间进化的系统，希望发现它们潜在的规则，从而提出用来预测和控制它们的模型。 例如，时间序列分析可以用来预测焊接金属时掉下的金属液滴和股票价格市场的波动。［ＭｃＮａｍｅｓ，１９９９】研究了局部模型在时间序列预测中的应用。障，２００２］详细研究了证券市场信息的非线性特征及非线性分析方法，采用非线性动力学系统的分析方法和混沌的神 经网络模型，对证券市场进行分析。 １．２．１经典的时间序列分析 经典的时间序列分析主要有两类问题［Ｇｅｏｒｇｅ ｅｔ ａｌ，１９９７］： （１）趋势分析 时序变量ｙ，如表示股票市场中ｍＭ股票的每日收盘价，它可以表示为时间ｆ的函 数，即辟以ｆ）ｏ此函数图示为１．２，它描述了一个点随时间变化的情况。 时间序列每个观察值大小，实际上是各种不同的影响因素在同一时刻发生作用的综 合结果。时间序列数据变动具有四种类型：长期或趋势变化、循环变动或循环变化、季 节性移动或变化、不规则或随机变化Ｍａｎ＆Ｋａｍｂｅｒ，２００１］。８中国科学技术大学博士学位论文第一章绪论图１．２ＩＢＭ股票时间序列长期或趋势变化，是指时间序列在一个长的时间间隔内总的一般变化方向，这种变化反映为一种趋势血线。它表示时间序列中的数据不是由意外的冲击因素所引起的，而 是随着时间的推移逐渐发生的变动，描述了一定时间内序列中持续的潜在稳定性，即反 映观察目标（预测目标）所存在的基本发展趋向的模式。典型的方法有加权移动平均方法和最ｔＪ、－－乘法。确定趋势的常见方法是计算＂阶的移动平均值（Ｍｏｖｉｎｇｙ１＋ｙ２＋…＋ＹＨ Ｙ２＋ｙ３＋‘。。＋Ｙ。＋ｌ栉玎ａｖｅｒａｇｅ ｏｆｏｒｄｅｒ刀）：Ｊ，３＋Ｙ４＋…＋ｙＨ＋２疗移动平均可以降低数据集的变化总量。用移动平均代替时间序列，可以减少不希望 出现的波动，故也称为时序的平滑（Ｓｍｏｏｔｈｉｎｇｏｆｔｉｍｅｓｅｒｉｅｓ）。移动平均会丢失序列的头尾数据，因此有时会生成原始数据中不会出现的循环或其他变化趋势，并且可能受一些极端数据的影响。如果在上式中使用加权算术，则称为行阶的加权移动平均（Ｗｅｉｇｈｔｅｄｍｏｖｉｎｇ ａｖｅｒａｇｅ ｏｆｏｒｄｅｒ ｎ），它需要一个加权系数ｗｌ，ｗ２，…ｗ。。采用适当阶数的加权移动平均，可以消除数据中的循环、季节性和非规则的模式，而只保留趋势变化。最小二乘法以最好的拟合曲线ｃ作为最小二乘曲线，即曲线具有最小的ｙ“．彩， ●…Ｉ其中偏差或误差西是指点＠）Ｄ的值∞与对应曲线Ｃ上的值之间的差值。 循环移动或循环变化，是指时间序列在间隔固定的一段时间呈现某种摆动迹象，遵从一定规律的变化。它表现为整个序列的不断的周期性但非定期的变动，可以也可以不 是周期性的，即在等时间间隔之间，循环不需要沿着同样的模式演化。 季节性移动是周期为季度的周期移动，是指时间序列在连续几年的有关月份出现的 相同或者相似的模式，反映了一段时间内或多或少规律性的变化。季节性变动归因于一 年内的特殊季节和节假日，例如，我国每年春节期间商品零售额达到最大的数量；冷饮 销售最高峰出现在每年夏季；情人节前巧克力和鲜花的购买会突然上升。这就是说，季！墅兰茎查奎兰堡主兰垒堡塞兰二兰竺笙节性变动基本上是每年重复出现的周期性变动。季节性波动可以通过引入季节指数来识 别重复性变化。 不规则或随机移动，表现为由于随机或偶然性事件出现的零星的运动特征，指时间 序列数据在短期内由于随机事件而引起的忽大或忽小的变动。例如，战争、自然灾害、 政治的或社会的动乱等等所致的不规则变动。非规则或随机变化可以通过针对趋势、季 节和循环变化的数据调整加以估计。一般地，小偏差出现的频率高，大偏差出现的频率 低，遵从正态分布。 以上有关趋势的、循环的、季节性的和非规则的运动，可以分别用ｒ，Ｃ，Ｓ，，表 示。传统的时间序列分析法，运用统计方法和数学方法，把时间序列数据作为随机变量Ⅳ分解为Ｌ ｃ，墨，四种变动值，也就是说，Ｌ ｃ，＆，四种综合作用构成丘一般 综合作用有两种方式：乘法模型方式，即ｊ，－丁?Ｓ?Ｃ?，加法模型方式，即ｊ，＝ｎ舟ｃ＿Ｈ（２）预测根据时间序列先前的运动情况，通过对趋势、循环、季节和非规则成分的变动的系 统分析，使人们在较合理的情况下，制定出长期或短期的预测，分析序列将来可能的趋 势或者走向。经典的分析方法有自回归（ＡｕｔｏＲｅｇｒｅｓｓｉｏｎ，ＡＲ）模型、自回归移动平均（ＡｕｔｏＲｅｇｒｅｓｓｉｖｅＭｏｖｉｎｇ Ａｖｅｒａｇｅ，ＡＲＭＡ）模型、指数平滑（Ｅｘｐｏｎｅｎｔｉａｌ Ｓｍｏｏｔｈｅｎｉｎｇ）和谱分解（Ｓｐｅｃｔｒａｌ Ｄｅｃｏｍｐｏｓｉｔｉｏｎ）等【Ｐａｎｄｉｔ＆Ｗｕ，１９８３］。Ｂｏｘ－Ｊｅｎｋｉｎｓ或者自回归积分移动平均模型（ＡｕｔｏＲｅｇｒｅｓｓｉｖｅ ＩｎｔｅｇｒａｔｅｄＭｏｖｉｎｇ Ａｖｅｒａｇｅ，ＡＲＪＭＡ）［ＢＯＸ＆Ｊｅｎｋｉｎｓ，１９７６］寻找下述差分等式的解：办∞）靠（伊）‘＝占＋岛ｐ）巳（∥）口ｆ≯，（Ｂ）表示Ｐ阶的非周期自动回归算子，模拟低阶回馈效应；≯，（占‘）表示Ｐ阶的周 期自动回归算予，模拟在周期间隔发生的回馈效应，比如每年一月发生的回归效果；曰。（Ｂ）表示ｑ阶的非周期移动平均算子，模拟低阶的加权平均效应；铭（Ｂ‘）表示Ｑ阶的周期移动平均算子，模拟周期性的加权平均效应。 Ｘｔ表示时间序列，ａ．表示一个随机变量序列，万是常量。回退算子Ｂ后移时序观察的索引，比如，矿Ｚｔ＝‘一。。非周期或第一差分算子Ｖ＝卜Ｂ提供了描述第一差分的一种紧凑方式。周期算子Ｖ。＝１一Ｂ‘用来描述两个周期时序观察的差别。≯。（Ｂ）也称为格林函数，用来捕获系统对随机变量序列ａ。和之前的时序值的动态响应，以∞）是随机变１０中国科学技术大学博士学位论文第一章绪论量ｄ。的加权移动平均。办（萨）模拟周期性回归效应，比如圣诞节之前玩具销售量的大幅度增长。易（Ｂ‘）用来模拟周期性效应而不是自回归效应，提供了周期性随机变量的加 权平均。艿＝／／矿。（Ｂ）办（Ｂ）是常量，∥是平稳时间序列的均值。算子的阶数需要从时序数 据中采用如最大可能性和最小平方这样的优化方法计算得来。 ＡＩｕＭＡ方法要求时间序列的平稳性、偏差的正态性和独立性。平稳时间序列的统计 特征不随时间变化，偏差是观察时序和ＡＲＪＭＡ方法产生的模型之间的误差，必须服从独立和正态分布【Ｂｏｗｅｒｍａｎ，１９９３］。虽然积分（过滤）方法可以将非平稳时序转换为平稳时序，但并不总是能满足要求，因此ＡＲＩＭＡ不能识别数据中的复杂特征。 现实世界中的许多时间序列，比如股票市场价格不满足这些条件，它们并不遵从一 种特定的规律，一般不可以用一些简单或复杂的等式描述出来。根据过去的变化趋势预 测未来的发展，它的前提是假定事物的过去会同样延续到未来。如市场预测的时间序列 分析法，是根据客观事物发展的连续规律性，运用过去的历史数据，通过统计分析，进 一步推测市场未来的发展趋势。预测对象的发展受很多因素的制约，这些因素的变化导 致时间序列的特征也在逐渐演化，单一的等式无法反映时间序列变化的多样性。 另外，在大型数据库中很难构建ＡＫＩＭＡ模型。数据挖掘从一个全新的角度出发，绕开数据固有的一些简单的性质如平稳性等，因此避免了传统的统计方法所面临的一些问题，如超大数据量等。数据挖掘自动地对大量数据加以分析，提取出潜在的有用模式。 数据挖掘包括一系列的自动进行科学发现过程的方法。它的特点在于要解决的问题类型 含有大量数据集和复杂、隐含的关系，其目的就是为了抽取这些隐含的有用的关系，１．２．２时间序列的数据挖掘问题时间序列数据库（Ｔｉｍｅｓｅｒｉｅｓｄａｔａｂａｓｅ）是由一系列的时间序列组成。时间序列数据在商业、金融、工程、医学和社会科学数据库中都占了很大的比例。例如在超市的销售数 据库中，每种商品每天的销售数量和金额与时间是密不可分的，它们就构成了时间序列数据库。时间序列数据是数据挖掘中一类复杂的数据对象，其复杂性表现在：一般维数比较 高，往往含有噪声：在幅度方面存在拉伸和平移，在时间轴上存在伸缩；另外还有线性 漂移和不连续点［Ｋｅｏｇｈ＆Ｐａｚｚａｎｉ，１９９８］。由于这些复杂性使得时间序列的研究也充满着 挑战性，研究者在这一方向已取得许多研究成果，时间序列数据挖掘已发展成为数据挖 掘领域中的一个重要研究方向。 时间序列研究这样一些问题：相似、分类和聚类、规则发现、事件检钡ｌＪ（Ｅｖｅｎｔ ｄｅｔｅｃｔｉｏｎ） 和预测。常见的例子如：发现一定时间间隔内具有相似股票价格的公司；查找出带有相 似销售周期的产品；聚类带有相似信用卡使用行为的用户；用模式分类一个己知的时间中国科学技术大学博士学位论文第一章绪论序列；发现频繁模式；在ＤＮＡ序列中查找出相似的子序列。涉及的主要问题如下： （１）相似问题（Ｓｉｍｉｌａｒｉｔｙ）：给定一个相似性度量标准，如果两个时间序列的相似性 小于给定的阈值，则认为它们是相似的。它涉及两个方面的问题：相似性度量和相似性 匹配。相似问题是时间序列挖掘的首要问题【Ａｇｒａｗａｌ ｅｔ ａｌ，１９９３ｂ］，它可以有效支持其它 问题的解决，如索引、子序列搜索、聚类等。在时间序列搜索中存在着一些困难的因素【Ｋｅｏｇｈ＆Ｐａｚｚａｎｉ，１９９８】。［Ｇａｖｒｉｌｏｖｅｔａｌ，２０００］讨论了股票中的相似性度量。（２）索引：由于时间序列数据库一般非常庞大，因此需要对这些数据进行有结构化 的组织，提高查询的效率，同时支持相似搜索。 （３）子序列相似：给定一个较短的模式，在一个较长的时间序列中搜索和它相似的 子模式。如，在一个很长的股票序列中找出和今日的价格有相似运动的那些日子。子序 列匹配可以通过移动窗口的方法转化为序列匹配。 （４）分类：给定一个序列集合，每个序列隶属于一个事先定义好的类别，作为训练 集；通过一定的分类学习算法，自动学习每个类的特征描述，并用来对新的未知类别的序列进行归类。 （５）规则发现（Ｒｕｌｅ Ｄｉｓｃｏｖｅｒｙ）：找出时间序列随时间变化的规则。如，如果股票Ｘ ｔ升且股票ｙ保持不变，则股票Ｚ立刻下降。（６）聚类：自动发现具有相似行为的序列，如具有相似销售模式的地区。 我们将在第二章详细介绍时间序列数据挖掘的研究方法和现有成果。１．３本文的工作和内容组织时间序列的数据挖掘是ＫＤＤ研究中一类很重要的问题。利用时间序列模式的数据 挖掘，可以得到数据中蕴含的与时间相关的有用信息，实现知识的提取。本文中，我们 对时间序列的模式提取、模式自动发现和事件预测这三个方面进行了深入的研究，提出 了新的相似模式检索的方法，能够自动地抽取出潜在的时序模式，并根据这些模式分析 时间序列的可预测性并进行预测。 在第二章，我们全面探讨了时间序列的数据挖掘问题。首先介绍了时间序列的相似 模式匹配问题，具体讨论了时间序列的表示和事物间的相似性度量方法；分析了目前主 要的匹配方法及其研究现状，其中具体涉及空间变换、索引结构、查询算法等。同时我 们探讨了时间序列的规则发现、事件检测和预测问题，分析了现有的一些模式发现和预 测算法。 在第三章，我们根据前面分析的现有特征抽取方法和多维索引结构的弱点，提出新 的时序特征抽取方法，改进了现有的多维索引结构，并提出和实现了相应的模式匹配算 法；通过实现证明，该算法在一定程度上提高了模式查询的精度。同时我们也通过实验 探讨了小波方法在时间序列降维方面的应用。 在第四章，我们基于事件序列数据库研究了模式的自动发现方法。事件序列数据库 和时间紧密相关，而传统的基于事务数据库的挖掘方法无法考虑这种关联性。我们对传中国科学技术大学博士学位论文第一章绪论统的关联规则挖掘方法进行了改进，使之适用于事件序列的数据挖掘，抽取出和事件的 发生趋势和变化率相关的模式，采用了一些评估方法对规则进行过滤和排序。同时，我 们提出了一种基于聚类方法的相似模式发现算法，挖掘出有代表性的模式和模式之间的相互依赖关系。在第五章，我们研究了时间序列的预测方法，提出实现了一种新的基于事件特征的 预测模型，这里预测的目标是下一个重要事件的发生。由于时间序列受很多种甚至是未 知因素的影响，直接进行预测是不现实的，我们首先提取出一些时序特征，它们从不同的角度描述时间序列，通过空间变换和特征选择，提出了基于ｋ最近邻的预测算法。同时，基于预测的结果，我们定义和分析了时间序列在不同尺度上的可预测性。本章还提出了一种基于分形维数的特征选择算法，详细描述了算法的过程，讨论了它们的时间复杂度和空间复杂度，并进行了实验分析。 对上述三章的研究成果，我们采用了一些标准数据，进行了一定的实验并加以分析。实验环境是Ｗｉｎｄｏｗｓ ２０００下的Ｃ＋＋或者Ｍａｔｌａｂ，ＣＰＵＰＩＩＩ７３３Ｈｚ，内存１２８Ｍｂ。在第六章，我们介绍了时问序列技术在电力数据中的应用，其中重点介绍了基于电 力数据的负荷预测系统。电力数据是一种随时间变化的数据，比如负荷数据和气象数据 都和时间有关，因此可以采用时间序列的一些方法对电力数据进行处理和分析。基于电 力数据的负荷预测系统，采用数据挖掘技术分析负荷数据和气象数据之间的关系，抽取 出相应的模式和规则，对未来的负荷做出预测。 第七章总结了本文的工作和主要创新点，探讨了时间序列数据挖掘领域的进一步研究方向。中国科学技术大学博士学位论文第二章时间序列的数聚挖掘第二章时间序列的数据挖掘时间序列数据是一类普遍存在的数据，它和其它数据最大的差别是数据和时间的紧密关联性。时间序列数据的模式发现是许多领域都涉及的一个重要问题，如计算生物学、 性能分析、客户行为等。近年来在这个领域进行了很多探索，数据的超大规模、噪声的 存在和格式的多样化给挖掘过程带来了很多困难。本章研究了时间序列数据挖掘的一些 技术和进展，介绍了该领域的研究现状和相关的工作。我们首先介绍了时间序列的相似 模式匹配问题，具体讨论了时间序列的表示和事物间的相似性的度量方法、空间变换方 法、多维索引结构和目前主要的查询匹配算法等。同时探讨了时间序列的规则发现和事件检测问题，分析了现有的一些模式发现和检测算法及其优缺点。２．１相似度量时间序列的模式匹配一般分为两种： ?序列匹配：假设数据库中所有的时间序列具有同样的长度，检索和一个时间序列相 似的其它序列； ?子序列匹配：检索和己知（子）序列相似的所有时间序列中的子序列。假设检索序 列为０，长度为ｄ，对数据库中任一长度＞ｄ的序列Ｚ在ｘ中寻找一个起始位置ｆ， 使得ｘ的子序列研ｊ，ｉ＋ｄ－１］军Ｄ ａ相似。可以通过简单的移动窗Ｅｌ技术将子序列匹配 转换为序列匹配。 两个时间序列之间的“相似”通过距离函数来衡量，相似性和距离成反比关系，距 离越近，说明愈相似。相似性搜索可以用于对金融市场的分析（如股票数据分析），医 疗诊断分析（如心电图分析）和科学与工程数据分析（如能量消耗分析）等。研究者从不同的角度提出了多种相似度量方法。２．１．１欧几里德距离欧几里德（Ｅｕｃｌｉｄｅａｎ）距离，简称欧氏距离，是一种常用的相似性度量。设有时间序列Ｘ＝ｘｏ，ｘ１’．，ｋｌ和Ｙ＝ｙｏ，Ｙｌ’．，Ｍ．１，将每个序列看成是打维空间中的 一个点，这里门为序列的长度，ｘ和Ｙ之间的距离定义为：，卜１‰（ｘ，ｙ）＝（∑（薯一儿）４）“４ｉ＝０ｑ＝ｌ，为Ｍａｈａｔａｎ距离，俨２，为欧氏距离。当两个序列之间的距离小于一个给定阈值，即Ｄ陇，）≤ｒ，我们认为ｘ和ｊ，是相似的，否则称它们是不相似的。文献中采用欧几里德距离作为相似性度量的主要有（【Ａｇｒａｗａｌｅｔ ｅｔａｌ １９９３ｂ；Ｆａｌｏｕｔｓｏｓ ｅｔ ａｌ １９９４；Ｆａｌｏｕｔｓｏｓ ｅｔ ａ１．１９９７；Ｃｈａｒｔ＆Ｆｕ １９９９；Ｈｕｈｔａｌａａｌ，１９９９；Ｒａｆｉｅｉ＆ＭｅｎｄｅｌｚｏＩｌ，１９９７；Ｙｉ＆Ｆａｌｏｕｔｓｏｓ，２０００；Ｃａｒａｇａ＆Ｌｏｐｅ互２０００】）。！型兰蔓查奎堂堂圭兰堡笙茎［Ｋａｌｐａｋｉｓ，２００１］采用Ｌｉｎｅａｒｐｒｅｄｉｃｔｉｖｅ塑三童盟塑生型塑墼窭茎塑ｃｏｄｄｉｎｇ（ＬＰＣ）编码时间序列，欧氏距离聚类。这种方法的优点是容易计算，可以支持索引、聚类等问题的解决。缺点是不支持平 移，如股票ｘ在￥１００波动，而股票ｙ在￥３０波动；股票Ｘ：￡Ｅ￥９５ ５ｆ１］￥１０５之间波动，而股 票ｊ，在￥２０和￥４０之间波动。我们也可以先对序列进行标准化，即采用序列的均值（ｍｅａｎ）和方差（ｖ撕ａｎＣｅ）进行规 范化，然后采用欧几里德距离度量。设Ⅳ（的和Ｊ９ Ｃ的为序列Ｘ的均值和方差，标准化定义为：ｘ，＝（ｘ，一∥（Ｚ））／ｐ（Ｘ）序列进行标准化之后，相似性依然太严格，不允许噪声和短期波动；不允许时间轴 上的相位平移；不允许时间轴上的伸缩。图２．１时间序列的变形图２．１给出了两个时间序列，Ｓｌ是一个平滑的曲线，＆是将Ｓ。在时间幅度轴上作了 平移和伸缩，加入一些噪声和短期波动后，无法用欧几里德距离度量它们的相似性。 ２．１．２动态时间弯曲距离 动态时间弯曲（Ｄｙｎａｍｉｃｔｉｍｅｗａｒｐｉｎｇ）广泛用于语音识别领域，允许信号沿着时间轴对模式进行伸缩变换，以使查询模式Ｑ与参考模式月相匹配。它的基本思想是：考虑时间序列Ｘ＝ｚｏ，Ｘｌ，．，Ｘｎ．ｔ和Ｙ＝ｙｏ，Ｊ，ｌ＇．，蛳’ｌ’允许通过重复元素扩展每个序列，欧氏距离在扩展序列ｒ和】＾之间计算。设Ｄ（ｉｄ）表示子序列ＸＯ，Ｘ１…，靖和如，ｙ１’．，＊之间的动态弯曲距离，用公式表示：Ｄｑ，Ｊ）＝Ｉ薯一ｙ，Ｉ＋ｍｉｎ｛Ｄ（ｉ一１，Ｊ），Ｄ（ｉ―ｌ，，一１），Ｄ（ｉ，＿，一１）） 对弯曲路径作如下限制；（１）单调性：路径应该不能向下或向左：（２）连续性：在序列 中没有间断的点；（２）边界条件：弯曲路径要在矩阵的单元开始和结束。 用动态规划的解决方法，实现时间复杂度是０∽?ｍ），这里Ｉ＂７，ｎｌ是两个序列的长度， 需要计算每个ｑｄ）组合。如果弯曲窗口满足ｌｉ－ｊｌ≤ｗ，则复杂度为０∽＋Ｗ）。 采用动态时间弯曲技术进行相似度量的有：【Ｂｅｍｄｔ＆Ｃｌｉｆｆｏｒｄ，１９９４；ＹｉＰａｒｋ ｅｔ ａｌｅｔａｌ，１９９８；２０００］年ｎ基于ｂｏｏｓｔｉｎｇ算法的【Ｄｉｅｚ＆Ｇｏｎｚａｌｅｚ，２０００１． 动态时间弯曲距离的优点是：支持时间轴上的伸缩；缺点是计算的代价高。２．１．３编辑距离 编辑距离饵ｄｉｔｉｎｇ ｄｉｓｔａｌｌｃｅ）是度量一个模式近似出现的标准。两个序列Ａ和Ｂ间的编 辑距离定义为将４转换为Ｂ所需要的最小编辑步数，即将一转换为占的最小代价。有１６中国科学技术大学博士学位论文第二章时间序列的数聚挖掘如下三种形式的编辑步法：删除、插入和改变。编辑距离公式如下：Ｄ（Ｏ力＝０ｏ≤≯≤力ＩＤｑ―ｌ，Ｊ）＋ｌＤ（ｉ，Ｊ）＝｛Ｄ（ｆ一１，Ｊ―１）＋ｆ矿（ｔ＝Ｙｊ，０，１） Ｉ Ｄ（ｉ，，一１）＋１上面公式的三个部分分别对应点的删除、修改和插入。按照时间序列的上升、下降和平稳的特征，将序列转换为预定的字符串，用编辑距离作为相似标准进行串的近似匹配。（［Ｘｉａ，１９９７；蒋＆李，２０００；Ｂｏｚｋａｙａ 这种标准。计算的代价偏高。ｅｔａｌ，１９９７］）采用编辑距离的优点是支持时间轴上的伸缩：缺点是很难定义一个合适的标准字符串，２．１．４界标距离［Ｐｅｍｇｅｔａｌ，２０００１采用界标（Ｌａｎｄｍａｒｋ）来压缩表示时间序列。将时间序列看作是一个曲线，如果曲线上一个点的第疗阶倒数为０，则称它为第门阶界标。这样，局部最大和最小是第ｌ阶界标。界标距离定义为时间和幅度上的二元组，序列之间的距离也是二元 组，它满足三角不等式。己知两个界标序列Ｌ＝＜Ｌ。，Ｌ：．…，Ｌ。＞，￡＝＜厶，厶，…，ｔ＞， Ｌ，＝（Ｘｓ，Ｙ，），厶＝（ｘ０Ｙ：），第ｋ这里个界标之间的距离定义为：△。（￡，￡）＝（《ｔｉ”‘（三，￡），霹删（三，￡））：霹”＝｛（Ｉ（耳一坼一。）Ｉ＋Ｉ（ｔ―ｔ一．）Ｉ）／２。。。。一Ｊ了－―Ｋ兰生二！：；三；；｛饕矿１＜七≤门。……‘ｏｔｈｅｒｗｉｓｅｌ０ｌ０矿Ｙｋ＝ｙｌ群”２｛Ｉ（Ｉ儿Ｉ＋ｌＹｋＩ）／２！丝二錾！。ｆ＾们，括。两个序列的距离为△（厶￡）＝（忪…（厶￡圳ｌ占４”（厶￡）１１）这种相似定义更接近于人的直觉。在这个标准上，可以定义几个一致变换，如平移、幅度伸缩、时间弯曲等。＾＝‘一‘一，蜀＝咒一Ｙｉ一．，峨＝＾＋。／ｈ， Ｖ‘＝ｖｌ十ｌ／ｖｆ训峨＝ｖｆ／ｈ，ｐｑ＝ｖｉ／Ｍ 界标距离的优点是度量方法直观，支持平移、幅度伸缩、时间弯曲等。１７！垦堕堕鲨查查堂苎主兰垡笙塞２．１．５其他相似性度量Ｅａｍｏｎｎ墨三兰堕塑生型塑墼窭苎塑Ｋｅｏｇｈ等人在时间序列分段线‘｜生（ＰｉｅｃｅｗｉｓｅＬｉｎｅａｒ Ｒｅｐｒｅｓｅｎｔａｔｉｏｎ ｏｆ ＴｉｍｅＳｅｒｉｅｓ）表示方面做了许多工作。时间序列通过芷个线性片段逼近，达到数据压缩的目的， 同时允许沿时间轴伸缩。如何选择合适的Ｋ是一个关键问题，Ｋ太小导致一些有用的特 征的丢失，太大保留了冗余信息。另外一些问题是：已知足如何选择最佳合适的片段， 和最小化一些错误函数等。相似性度量采用距离等于投影片段差的加权和暇ｅｏｇｈ＆ Ｐａｚｚａｎｉ，１ ９９８】。 ［Ｓｔｒｕｚｉｋ＆Ｓｉｅｂｅｓ，１９９９］基于小波变换提出了两种相似评价标准。一种是全局上的， 根据全局伸缩的性质，用小波变换导出Ｈｕｒｓｔ指数分类时间序列的统计特征来计算相似性：另一种是面向时间序列局部细节的度量，采用小波变换的模极大尺度～位置分枝表示。欧几里德距离是基于时间轴计算的，但大部分实际应用不一定要求匹配的序列在时 间轴上完全～致。即，若子序列对具有相同的形状，但序列内存在间隙或在偏移或振幅 中存在差异，也应该认为是匹配的。一种改进的相似模型是，允许设置一些参数，如滑 动窗口尺寸、相似范围的宽度、最大间隙和匹配片断（Ｍａｔｃｈｉｎｇ ｆｒａｃｔｉｏｎ）等。具体的处理 步骤大致如下：１）原子匹配（Ａｔｏｍｉｃ ｍａｔｃｈｉｎｇ）：找出所有无间隙的较小的窗口对；２） 窗口结合（Ｗｉｎｄｏｗ ｓｔｉｔｃｈｉｎｇ）：把相同窗口结合，形成大的相似子序列，其中允许在原子 匹配间存在间隙；３）子序列排序（Ｓｕｂｓｅｑｕｅｎｃｅ ｏｒｄｅｒｉｎｇ）：线性排序子序列对，以判定是 否存在足够多的相似片段。通过以上处理，可以得到形状相似但在偏移或振幅中有间隙 或有差异的相似序列。［Ａｇｒａｗａｌｅｔ ａｌ，１９９５］提出了序列缝合技术（Ｓｕｈｓｅｑｕｅｎｃｅｓｔｉｔｃｈｉｎｇａｌｇｏｒｉｔｈｍ），对存在位置偏移和噪声的时序进行模式匹配，该模型中相似搜索的基本思想是：如果两个时间序 列具有足够长的非重叠的相似子序列，则认为它们是相似的；判断子序列相似时又可以 将子序列看作是由若干相似的原子序列拼接而成的。 Ｋｅｏｇｈ等提出基于概率论方法的快速相似模式匹配模型［Ｋｅｏｇｈ＆Ｓｍｙｔｈ，１９９７］，和基 于相似性的概率方法，采用时间序列Ｑ和尺之间的概率距离进行度量，能有效地结合 先验知识，处理噪声和匹配过程中的不确定性。ｆＤａｓｅｔａｌ，１９９７；Ｂｏｌｌｏｂａｓ ｅｔａｌ，１９９７］在度量相似性时，采用统计学的方法考虑了不同的尺度函数、采样率和离群值。 ｆＣｈｕ＆Ｗｏｎｇ，１９９９］基于尺度和平移变换定义时间序列的相似性。． ｆ蔡等。２０００］采用斜率大小作为相似度量的一个标准。 ａ１．２００１］提出一个检索和表示时间序列部分信ｇ（Ｐａｒｔｉａ］ｉｎｆｏｒｍａｔｉｏｎ）的模型和 基于部分信息评价相似度量的方法。ｅｔ［Ｊｉｎ２．２空间变换在执行实际数据挖掘操作以前，需要解决一个基本问题：数据的表示和预处理。由中国科学技术大学博士学位论文第二章时间序列的数聚挖掘ｆ时间序列可能是一个很长的序列，在进行模式匹配之前，需要对数据维度进行约简。 数据的表示对时间序列来说特别重要，直接去操作一个连续、高维的数据空间是极其困 难的。这就需要对时间序列进行降维，表示成连续或者离散的形式，再在新的数据上执 行检索。数据的降维是时序模式研究的一个重要方面［Ｆａｌｏｕｔｓｏｓｅｔａｌ，１９９４】。在许多ＫＤＤ应用中，如最近邻搜索、基于距离尺度的聚类和奇异点检测中，存在 一个潜在的ｄ维数据空问，在这个空间中每个数据对象可以表示为一个点。直接将对象 看作是多维点的一致性变换，存在很多弱点，不适合进行许多基于距离的操作［Ｋｎｏｒｒ ｅｔａｌ，２００１】。比如在一个有关人员健康资料的数据库中，有身高、体重、年龄、体温等属性， 当采用一致性变换进行基于距离的计算时，是将这些属性默认为同一个尺度下，但实际上体温变化一度和身高变化一厘米差别甚远，这样势必带来很大的误差，产生的结果或规则没有什么实际意义。一种解决方法是通过进行规范化（将属性标准化到［Ｏ，ｌ】区间） 缩小属性尺度带来的影响，但这种规范化是很粗糙的一种操作，当数据中存在噪声时，将对结果产生很大影响。空间变换一方面将数据变换到一个合适的空间，另外一个方面也进行了信息约简， 在一定程度上减少数据量，因此这种方法有时也称为维数约简。 维数约简主要思想是减小数据空间的维数，将一个弹维的时间序列投影到一个．｜｝维的空间上，其中ｔ＜嘲，这个过程中距离尽可能地保持不变，然后在新的空间上采用一种索引技术来实现检索。检索时，将查询Ｑ映射到同一个新的空间，转换为ｋ维点表示，在新的空间中查找９的最近邻。设Ｆ表示维数约简技术，最佳Ｆ变换要求Ｄ（Ｒ西，Ｈｙ））＝ＤⅨＤ。否则，将会出现下面两种情况：当ＤⅨｙ）‘Ｄ（Ｆ（的，足功出现漏报（ｆａｌｓｅ ｄｉｓｍｉｓｓａｌｓ），即有些原本相似的序列根本没有被检索到；当Ｄ（同∞，只，））＜Ｄ＠＇）出现误报（ｆａｌｓｅ ａｌａｒｍｓ），即检索出的相似的序列不一定是相似的。因此，为保证最终结果的正确性，必须保证无漏报。即，如果Ｄ（Ｘ，Ｙ）＜占，则必有Ｄ（Ｆ（ｚ），Ｆ（Ｊ，））＜占。其中这一点保证了在新的空间中检索到的序列包含了所有的正确结果，不会出现ｆａｌｓｅ ｄｉｓｍｉｓｓａｌｓ，但可能存在ｆａｌｓｅ ａｌａｒｍｓ，这些ｆａｌｓｅ ａｌａｒｍｓ可以通过进一 步的后处理（Ｐｏｓｔｐｒｅｃｅｓｓｉｎｇ）消除。 常用的维数约简技术有：主成分分析和奇异值分解、离散Ｆｏｕｒｉｅｒ变换、小波变换、ＤＳＥ变换、线性分割逼近和随机投影等。 ２．２．１主成分分析 主成分分析（Ｐｒｉｎｃｉｐｌｅ ＣｏｍｐｏｎｅｎｔＡｎａｌｙｓｉｓ，ＰｃＡ）广泛用于数据的约简和空间变换。它 将数据空间看作是一个矩阵，通过实施正交变换，提取出一组相互独立的正交向量，称为主成分。主成分的个数和原属性个数相同，每个主成分可以看作是空间中的一个轴，中国科学技术大学博士学位论文第二章时间序列的数聚挖掘当将原数据投射到第一个轴上时，形成的新的数据的方差最大；投射到第二个轴上时， 形成的新的数据的方差次大；以此类推。但一般前几个主成分的方差之和达到原数据集 总方差的８０％以上，即前几个主成分包含了数据中的大部分信息。因此，可以用主成分 分析来进行数据约简，采用前几个主成分就可以近似表示原数据。基于主成分分析的空 间变换将数据变换到一个合适的和原空间同样大小的主成分空间，使变换后的属性大致 工作在同一尺度下，方便进行基于距离函数的操作。 ｘ∈Ｊ∥是一个随机向量，Ｘ的协方差矩阵定义为：∑。＝Ｅ｛【ｘ―Ｅ（Ｘ）】［Ｘ―Ｅ（Ｘ）１１）Ｅ∞是ｘ的期望值，对∑。＝Ｒ“”进行特征值分解中７∑ｚ西＝Ａ①中７￡ｚ①①～＝∑Ｊ＝ｅｏＡｅｐ７其中，由∈Ｒｕ“是正交特征向量矩阵，Ａ∈Ｒ“”是对角特征值矩阵，其对角元素按 递降顺序排序（＾≥五≥…≥以），萌，唬，…纯是对应的特征向量，即主成分。当采用前几个 ：主成分时，ＰＣＡ也可以重构原始序列，Ｐ＝【葫，唬，…丸】，Ｙ＝Ｐ７Ｘ，ｍ＜Ⅳ，便实现了维数约简。低维向量，，实际上包含了ｘ中最重要的信息。采用主成分分析的工作有［Ｃｒｏｕｘ＆Ｒｕｉｚ．Ｇａｚｅｎ，１９９８；ＭｃＮａｍｅｓ，２００１］等。和主成分分析类似的一个概念是Ｋ．Ｌ变换咂ａｒｈｕｎｅｎ－Ｌｏｅｖｅ Ｔｒａｎｓｆｏｒｍ）。ｔＷｕ，１９９６】的约简工作在Ｋ．Ｌ变换下进行，Ｋ－Ｌ变换也成为奇异值分解（Ｓｉｎｇｕｌａｒ 变换使得在选定的维上实现方差的最大化。 Ａ是一个ｍ＊ｋ的实数矩阵，存在埘＋ｍ的正交矩阵ｕ和ｋ＊ｋ的正交矩阵儿使得： ，Ａ＝Ｕ ＡＶ，Ａ＝ｄｉａｇ（４，也，…，乃，） Ｌ…Ｊ ｍ……… ｒ＝ｍｉｎ（ｍ，妁，（＾≥五≥…≥ｔ≥０），五称为奇异值，矿称为奇异向量。当Ａ是一个／＇／＊／１的协方差矩阵，就是ＰＣＡ，因此ＰＣＡ是ＳＶＤ的一个特例。ＶａｌｕｅＤｅｃｏｍｐｏｓｉｔｉｏｎ，ＳＶＤ）【Ｋｏｍ ｅｔａｌ，１９９７］。己知一组玎维点，将它们投影到ｌｅｏｎ维的子空间，Ｋ．Ｌ变换的主要弱点是随着增量修改。索引的性能会发生退化。投影轴通过第一个 特征向量集上的协方差矩阵预先确定。尽管投影一个固定的向量集是优化的，然而当增 加新的数据时投影矩阵必须重新计算，索引结构要周期性地重新组织，以维持搜索的性能。ｆＫａｎｔｈｅｔａｌ，１９９８１提出一种有效的基于ＳＶＤ索引的增量更新方法。【Ｔｈｏｍａｓｉａｎｅｔａｌ，１９９８］中引入了带有奇异分解的聚类（ＣＳＶＤ）方法以改进标准ＳＶＤ算法。 ２．２．２离散傅立叶变换 对ｎ个点的序列Ｘ－－－－Ｘｏ，ｘｌ＇．．，Ｘｎ－１，它的离散傅立叶变换∞ｉｓｃｒｅｔｅ２０Ｆｏｕｒｉｅｒ Ｔｒａｎｓｆｏｒｍ，中国科学技术大学博士学位论文第二章时间序列的数聚挖掘ＤＦＴ）是Ｓｆ＝击∑。＾，Ⅳ哪删Ｖ＝ｏ＇１，…，州，＿，２＝－１）ＤＦＴ的时间复杂性为Ｏ（ｎｌｏｇｎ），使得它成为一个有效和实用的方法。［Ａｇｒａｗａｌｅｔａｌ，１９９３ｂ］和［Ｒａｆｉｅｉ＆Ｍｅｎｄｅｌｚｏｎ，１９９８］采用ＤＦＴ方法进行维数约简。［Ｇｏｌｄｉｎ＆Ｋａｎｅｌｌａｋｉｓ， １９９５］也采用傅里叶变换，相似性基于傅立叶序列的线性变换集合，每次搜索一种变换。根据Ｐａｒｓｅｖａｌ定理［Ｏｐｐｅｎｈｅｉｍ＆Ｓｃｈａｆｅｒ，１ ９７５１，∑。．，。一２＝∑劁…。乃２即序列在时间域内的能量等于频域的能量。由于离散傅立叶变换是线性变换，所以，∑。…。（ｔ一只）２＝∑川…。（乃一０）２这样采用变换后的ｋ＜ｎ个系数表示原序列便降低了距离值。∑。＾州（Ｓ―Ｚ）２＞∑，＝ｏ．１…。（墨一弓）２为了约简和逼近时间序列，系数一般取前ｋ个（［Ａｇｒａｗａｌｅｔ ａｌ，１９９３ｂ；Ｒａｆｉｅｉ＆Ｍｅｎｄｅｌｚｏｎ，１９９８］），因为傅立叶系数的能量是按照递降的顺序排列的。傅立叶变换是一种纯频域的分析方法，反映的是整个信号全部时间下的整体频率特征，不能提供局部时间上的频率特征。加窗傅立叶变换将一个时间窗口函数和待分析函 数相乘，再进行傅立叶变换，结果可以描述某一局部时间段上的信息，但对一个时变的 非稳态信号，很难找到一个合适的时间窗口来适合不同的时间段。 傅立叶变换将信号从时域变换到频域，但却不能将两者有机地结合起来。这是因为 傅立叶变换是整个时间域上的积分，信号的时域波形中不包含任何频域信息，没有局部 化分析信号的功能，也就是说，无法知道某一个频率是在什么时候产生的。在实际的信 号处理中，尤其是非平稳信号的处理中，信号在任一时刻附近的频域特征很重要，比如我们经常关心高频信号发生在什么时候，因此需要提供一种将时域和频域结合起来的分 析信号的方法，这就是所谓的时频分析法。２．２．３离散小波变换小波（Ｗａｖｅｌｅｔ）分析方法［ＢＵｌＴＢ￥ｅｔ ａｌ，１９９８］是在傅立叶方法的基础上发展起来的，它 同时反映了信号在时域和频域上的差异，在时域和频域上均具有良好的局部化性质，能 够将各种交织在一起的不同频率组成的混合信号分解成不同频带上的块信号。它具有多尺度性、时移不变性等特点。小波变换（Ｗａｖｅｌｅｔ Ｔｒａｎｓｆｏｒｍ）是一种非平稳信号分析方法。它通过一个满足条件ｆ ｖｚ（ｘ）ａｘ＝０的基本小波函数矿（功的平移和伸缩构成一族小波函数系去表示或逼近一个函数。二进制小波是由伸缩因子和平移因子满足一定条件的这样的一组函数：２１中国科学技术大学博士学位论文第二章时间序列的数聚挖掘弘，Ｊ。ｔ（ｘ）＝２川２∥（２’ｚ一七），／，ｋ∈Ｚ对任意平方可积函数㈣来说，其离散小波变换（Ｄｉｓｃｒｅｔｅ Ｗａｖｅｌｅｔ为：Ｔｒａｎｓｆｏｒｍ，ＤＷＴ）睨／（√，Ｊ｜｝）２［。，（工）‰（ｘ协＝＜，，‰＞，／（ｘ）∈三２（厕１９８７年，Ｍａｌｌａｔ利用多分辨分析的思想，统－－Ｙ，ｂ波函数的构造，提出了离散信号 按小波变换的分解和重构的金字塔算法［Ｂｕｒｒｕｓ ｅｔ ａｌ，１９９８］。多分辨分析先从平方可积空 间Ｌ２的某个子空间出发，在这个子空间中先建立起基底，然后用极其简单的变换，再 将基底扩展到Ｌ２中去，从而得到整个空间的基底。假设｛妒，，。｝似。：是Ｌ２的正交小波基， 则对任意，（砷∈ｒ，ｆ（ｘ）可由所有尺度下的小波信号经线性叠加而恢复：，（ｘ）＝∑。Ｗ，ｆ（ｊ，Ｊ｜｝）虬，。（ｘ）若（，（ｘ））。：有ｒ１个非零样本值，离散二进制小波变换的计算程序为：Ａ：＝去∑爿ｙｌ。噬＝去∑爿；１９ｊ－２ｎ～‘阼ｚ ～二『∈ｚ其中吩，舒是离散滤波器。对数字信号而言，上述分解形式非常有效，可以直接把 ４０定义为待分解的原信号，因而分解方式完全是离散的。 离散小波变换将时间序列分为尺度部分４和细节部分Ｄ，尺度部分通过待分析序列 卷积低通滤波器得到，反映了原序列的大致趋势和走向；而细节部分通过待分析信号卷 积高通滤波器得到，表示信号在细节上的差异。对尺度部分进一步实旌ＤＷＴ得到更详 细的尺度部分和细节部分，这个过程可以～直继续下去，所以说小波变换具有多尺度分 解的特性。对一个长度为胛的序列实施ＤＷＴ，得到两个长度为ｎ／２的尺度序列ｃＡ和细节序列ｃＤ，如图２．２。～ｎ／２ ｃｏＦ，拿图２．２离散小波变换 这样每进行一次ＤＷＴ，尺度序列的长度缩为原信号长度的１／２。如果我们进行尺度 为３的小波变换，则得到的尺度序列长度为原序列长度的Ｉ／８。尺度数越高，得到的尺 度序列的长度愈短，信号愈模糊。尺度序列很好地跟踪了原序列的趋势走向，因此可以 采用尺度序列表示原序列，达到数据量的大幅度约简，而信息量相对丢失较少。 使用小波进行维数约简，象ＤＦＴ一样将时问序列局部为一个原型函数的和，保留ｋ中国科学技术大学博士学位论文第二章时间序列的数聚挖掘个小波系数作为时间序列的逼近，相当于只使用低通滤波器，最常用的小波基是Ｈａａｒ 小波。【Ｃｈａｎ＆Ｆｕ，１９９９］提出了小波方法在时间序列模式发现中的应用，使用了基于Ｈａａｒ 小波的离散小波变换。一个长度为ｎ的序列可以进行ｌ０９２ｎ次的离散小波变换。［Ｈｕｈｔａｌａ ｅｔ ａｌ，１９９９］采用小波变换的方法抽取时间序列的特征，进行聚类，研究时间序列的相似性 随着时间和尺度进行变化的规律。采用小波变换的工作还有［Ａｕｓｓｅｍ＆Ｍｕｒｔａｇｈ．１９９７；Ｓｔｒｕｚｉｋ＆Ｓｉｅｂｅｓ，１９９９；Ｋａｈｖｅｃｉ＆Ｓｉｎｇｎ，２００１；Ｐｏｐｉｖａｎｏｖ＆Ｍｉｌｌｅｒ，２００１】等。［郑，２００２］研究了小波的多尺度性在时间序列模式匹配中的应用。 小波变换与傅立叶变换的区别在于：变换后的时间序列仍然在同一个时域，具有时 域局部化，且系数产生算法的时间复杂性为０（刀），比ＤＦＴ更有效。考虑到傅立叶具有 一定的对称性，【Ｗｕｅｔａｌ，２０００ｂ】进行了ＤＦＴ’ＤＷＴ的比较。Ｐａｒｓｅｖａｌ定ｔ里［Ｏｐｐｅｎｈｅｉｍ＆ＳｃｈａｆｅＬ １９７５］证明，对正交小波而言，如ｄｂ小波，小波域序列之间的欧氏距离将不超过原始序列之间的欧氏距离。这保证了在小波域空间检索 到的序列包含了所有的正确结果，不会出现ｆａｌｓｅ ｄｉｓｍｉｓｓａｌｓ，但可能存在ｆａｌｓｅ ２．２．４其它变换方法（１）Ｄｏｎｏｈｏ ＳｔａｈｅｌＤｏｎｏｈｏ Ｓｔａｈｅｌ ａｌａｒｍｓ。Ｅｓｔｉｍａｔｏｒ变换方法Ｅｓｔｉｍａｔｏｒ（ＤＳＥ）基于这样一种原理［Ｓｔａｈｅｌ，１９８１：Ｄｏｎｏｈｏ＆ＨｕｂｂｅＬ１９８３］：如果两个属性具有同样的尺度和可变性（Ｓｃａｌｅ＆ｖａｒｉａｂｉｌｉｔｙ），则离点Ｐ距离不超 过ｄ的点位于以Ｐ为中心，ｄ为半径的圆内：如果尺度和可变性不同，则位于一个椭圆 内。如果属性之间不相关，椭圆的轴位于标准的坐标轴，否则，需要旋转一个角度。这在高维空间也是成立的，ＤＳＥ ｅｓｔｉｍａｔｏｒ是通过寻找这样一个合适的角度来进行空间变 换。ＤＳＥ算子（Ｅｓｔｉｍａｔ００ Ａ是一个ｎ＊ｎ的ｓｃａｔｔｅｒ ｍａｔｒｉｘ，刀是数据空间的维数，原始空间 ｒ――――――――――――一ｒ――――――――――――――一 置），在新的空间定义为：中点ｘ和ｙ的欧氏距离ｄ（ｘ，Ｙ）＝ＬＩＸ―ｙｌ｝√∑：。（弓一咒）２＝√（ｘ一，ｒ，（ｘ―ｙ）（ｒ表示转以（ｘ，ｙ）＝｜｜ｘ―Ｙ Ｊｈ＝ｑ（ｘ一】，）７ Ａ（Ｘ―ｙ）ｒ―――――――＝――――――――一当ｊ，≠０时，ＸｒＡ．玲０，Ａ是一个正定矩阵，肋产生一个椭圆。ＤＳＥＥｓｔｉｍａｔｏｒ有两个特点：（１）在变换后的空间中可以采用欧氏距离；（２）稳定性：当数据更新时，无须重新计算。最初［Ｓｔａｈｅｌ，１９８１］的Ｆｉｘｅｄ ａｎｇｌｅ算法通过枚举所有的角 度得到一个误差最小的ＤＳＥ ｅｓｔｉｍａｔｏｒ，这在高维空间效果不理想，因此［Ｋｎｏｒｒ 提出了Ｈｙｂｒｉｄｅｔａｌ，２００１】ｍｏｄｎａｒ＿差误得使个一择选次每，样取和机随过通是想思本基，法算ｍａｔｒｉｘ最小的向量，最后组合为ｓｃａｔｔｅｒＡ，实验表明该算法在离群点检测应用中提高了精确度。Ｈｙｂｒｉｄ ｒａｎｄｏｍ算法的问题是需要设定的参数很多，用户可能需要很多次尝试才能得到较好的结果。研究ＤＳＥ Ｅｓｔｉｍａｔｏｒ的工作还有［Ｒｏｕｓｓｅｅｕｗ＆Ｌｅｒｏ％１９８