基于特征模式提取的时间序列分类系统课堂PPT

1Classification System for Time Series Data Based on Feature PatternExtraction基于特征模式提取的时间序列分类系统Hiroshi Sugimura,Kazunori Matsumoto2引言 文献1：将频率模式作为特征模式，但很多情况下频率与感兴趣对象不相关 文献2：基于背景知识，通过可 视化查询语言获得相似模式 文献3：SVM分类（分类难以理解）文献4：聚类法(一个用户难以确认所有的提取集群）文献6：提取了一种决策树方法3基于特征模式提取的时间序列分类系统v系统特点：获取特征模式和分类时不需要使用者具备背景知识v研究目的：通过提取特征模式获取每个数据的特征4基于特征模式提取的时间序列分类系统v系统构成：代表性序列特征模式创建决策树时间序列数据加窗子序列聚类T5对时间序列加窗v滑动窗v窗的长度为20个数据6基于特征模式提取的时间序列分类系统v系统构成：代表性序列特征模式创建决策树时间序列数据加窗子序列聚类T7聚类v采用K均值聚类法 聚类准则：每个数据与质心的距离（即类内误 差）为数据 和数据 之间的距离 为包含 的子集的 质心整个聚类空间的误差为：kjNijjicxDXErr11)(),()(jcjC)(jix),(qpDpq8聚类v（转载）K均值法的步骤：选取聚类数目K选择一个含有随机选择样本的K个类的初始分区，然后计算这些类的质心。通过将样本分配给与其质心距离最近的类生成一个新分区。重新计算新类的质心。重复前两部的过程直到满足收敛标准9基于特征模式提取的时间序列分类系统v系统构成：代表性序列特征模式创建决策树时间序列数据加窗子序列聚类T10)log()(nNwidfi)(*),(),(*ikikiwidftwtftwIDFTFNnIDFTF/),(kitwtfiw逆文本频率指数：为文档总数目为单词至少出现一次的文档数目权重定义为：为词在该文档中出现的次数11 在文档挖掘中，被公认为一种重要的统计测量方法 在数据库中广泛存在的特征模式是对分类来说是不重要的 认为序列为文档，则其子序列可视为短句（term)12基于特征模式提取的时间序列分类系统v系统构成：代表性序列特征模式创建决策树时间序列数据加窗子序列聚类T13动态时间规整（DTW）DTW用于计算两个序列之间的距离，获取两个序列采样点之间的最优化路线 一个计算两序列距离的简单方法是对他们中的一个进行重复取样，然后一个样本一个样本的比较14DTW(转载)注：假设测试和参考模板分别用T和R表示，为了比较它们之间的相似度，可以计算它们之间的距离 DT，R，距离越小则相似度越高syxDryxDqyxDyxDyxDjijijijiji),(),(),(min),(),(111111rq,s11,jiyxji,两个不等长的两个时间序列长度为：),(jiyxD它们的相似度函数 为：为序列最新的移除值为序列减小和拓展的序列数为距离值15分类-步骤 基于特征模式制作分类器 评价分类器1.改进特征模式16决策树学习17遗传算法GA-基因表达基因表达（基因与特征模式相关联）一个特征模式可用一组数值表示18遗传算法GA-适应度函数 适应度函数（该系统利用信息增益比评价基因）T为k个训练实例的一个序列，T属于类Cj,识别T中一个实例所属类别所需的信息量为：给予测试X的结果T分为n个子集，类似所需的信息量为：通过划分T和测试X一致部分，所获得的信息：19遗传算法GA-适应度函数适应度函数增益的准则偏向于高频数据，为了改进这一问题，对信息增益规范化信息增益比定义为：20遗传算法GA-选择 采用轮转法轮转法步骤：对群体成员的适应度累加求和，记为n 在0-n间产生一个随机数 返回第一个累加值大于该随机数的群体成员21遗传算法GA-复制 复制（繁殖）通过交换和变异产生产生新一代（转载）GA的流程图http:/ 利用金融股票价格数据来测试该方法20genes时准确性大大提高，GA法改进后准确性更高23（转载）遗传过程24（转载）轮转法（适应度比例法）用适应度比例法进行选择时，首先计算每个染色体的适应度，然后按比例于各染色体适应度的概率进入交换（匹配）集的染色体，其具体步骤如下：计算每个染色体的适应度值f(xi)；累加所有染色体的适应度值，得最终累加值SUM=，记录对应于每个染色体的中间累加值g(xi)；产生一个随机数N，0NSUM；选择其对应的中间累加值满足g(xi-1)N=g(xi)的染色体进入交换集。重复（3），（4），直到交换集中包含足够多的染色体数字串为止。重复上述过程，直到交换集中包含足够多的染色体为止。http:/