时序空间挖掘

时序空间挖掘 内容 什么是时序数据时序数据挖掘的现状利用反馈的时序数据相似性挖掘什么是时序数据相似性挖掘利用反馈的时序数据相似性挖掘 时序数据 一类数据集的数据之间存在着时间上的关系 这类数据被称为时序数据 从时间序列的角度来看 每个数据单元可以被抽象为一个二元组 t o 其中 t为时间变量 O为数据变量 反映数据单元的实际意义 时序挖掘的现状 时间序列近似表示是将原始时间序列用某个维数更低的时间序列在一定的误差范围内代替 这样可以实现数据压缩 减少计算代价时间序列数据变换将原始时间序列映射到某个特征空间中 并用它在这个特征空间中的映像来描述原始的时间序列 傅立叶变换等时间序列聚类分类分析对时间序列进行聚类的算法有基于相似性 或距离 基于特征 基于模型和基于分割的聚类分析 相似性搜索 在数据库中找出与给定查询序列最接近的数据序列 该问题可描述为 给定某个时间序列 要求从一个大型时间序列数据库中找出与之最相似的序列衡量时间序列的相似性 通常先给定相似度量 相似度量是指两个时间序列之间的相似标准 通常以欧氏距离作为两个时间序列之间的相似度量 欧式距离 数据变换法 时间序列数据变换就是将原始时间序列映射到某个特征空间中 并用它在这个特征空间中的映像来描述原始的时间序列 这样可以实现数据压缩 减少计算代价基于离散傅里叶变换的方法离散傅里叶变换在时间序列分析方面具有独特的优点 对于给定的时间序列 先用离散傅里叶变换把其从时域空间变换到频域空间 再根据Parseval理论 时域能量函数与频域能量函数相同 且频域空间的大部分能量集中在前几个系数上 因此可以不考虑离散傅里叶变换得到的其他系数 把这些被保留的系数看作从时间序列上提取的特征 这样从每个序列获得k个特征 并进一步把它们映射到k维空间上 利用反馈的时序数据相似性挖掘 时序数据相似性挖掘就是在数据库中发现与给定时序序列的模式很相似的序列 在进行序列相似性挖掘之前给定一个相似性评价函数和一个阈值e 如果函数值小于等于e 则表明序列相似 通常用X与Y之间的距离函数D X Y 作为序列X与Y的相似性判别函数 距离函数D X Y 常用X与Y之间的欧几里德空间距离等来代替 如果计算结果小于等于给定的阈值e 则表明X与Y相似 时序数据的相似性挖掘的步骤 依据应用要求将时序数据划分为一系列子序列 用离散傅立叶变换将子序列时序数据从时域空间变换到频域空间时域能量函数与频域能量函数相同 且频域空间的大部分能量集中在前几个系数上 因此可以考虑只选用傅立叶变换得到的前k个系数 将这些系数看作从时间序列上提取的特征 于是从每个序列获得k个特征 进一步将它们作为k维空间上的一个映射 即将时序数据的子序列映射为k维空间上的点 这样便保留了时序数据的主要特征 而且降低了时序数据的维数 减小了计算的复杂性 时序数据的相似性挖掘的步骤 针对k维空间上的时序数据点 该算法采用多维索引方法R树来存储这些多维空间的点通过范围查询检索与给定序列相似的时序序列 将检索的相似时序序列展现给用户 由用户赋予其感兴趣的序列相应的权值 并通过反馈与给定序列叠加产生新的查询序列 再次进行范围查询 获得相似序列 傅立叶变换 傅立叶变换 相似性函数 算法 计算反馈时序数据点计算经过反馈得到的相似时序点computSimSeq Root P r 集合e 输入 待查询的时序点集合P 给定时序序列点r e 输出 相似时序点集合SimSet Step1 设置集合SimSet和SimSettmp初始值为空 Step2 将P中的每个点p和MBR插入R Tree 建立一链表nodelist Step3 当链表非空时 若结点为叶子结点 对于结点中的每个点p Step4 计算点p与点r的距离Dist p r 若Dist p r e 则将点p插入相似时序点集合SimSettmp Step5 对相似时序点集合SimSettmp 调用算computFeedbackSeq SimSettmp W r 计算由相似时序点集合中的点经用户赋予相应权重后与r叠加获得的时序点C Step6 对于P中的每个点p 计算点p与点C的距离Dist p r 若Dist p r e 则将点p插入相似时序点集合SimSet Step7 返回SimSet 算法 计算反馈时序点C computFeedbackSeq SimSettmp W r 输入 由初始范围查询获得的相似时序点集合SimSettmp 用户设定的权值W 给定时序序列点r 输出 由反馈获得的时序点C Step1 对由初始范围查询获得的相似时序点集合的点进行傅立叶反变换 得到时序数据曲线 由用户根据对各时序数据曲线的感兴趣程度赋予各相似