《第15章复杂对象数据挖掘课件.ppt》由会员分享，可在线阅读，更多相关《第15章复杂对象数据挖掘课件.ppt（111页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据挖掘原理与数据挖掘原理与SPSSClementine应用宝典应用宝典元昌安元昌安主编主编邓松李文敬刘海涛编著邓松李文敬刘海涛编著电子工业出版社电子工业出版社1第第1515章章 复杂对象数据挖掘复杂对象数据挖掘 215.1 15.1 空间数据库挖掘空间数据库挖掘 15.2 15.2 多媒体数据挖掘多媒体数据挖掘 15.3 15.3 文本挖掘文本挖掘15.4 15.4 挖掘万维网挖掘万维网15.5 15.5 挖掘数据流挖掘数据流15.6 15.6 时间序列数据挖掘时间序列数据挖掘 15.7 15.7 挖掘事务数据库中的序列模式挖掘事务数据库中的序列模式15.8 15.8 挖掘生物学数据中的序列
2、模式挖掘生物学数据中的序列模式315.1 15.1 空间数据库挖掘空间数据库挖掘 空间数据库挖掘（SDM）实质上是空间信息技术发展的必然结果，它是数据库挖掘（DM）的一个重要分支，面对的都是空间数据库（spatial database,SDB）。空间实体之间又具有空间拓扑、空间距离、空间方位这3种关系415.1.1 15.1.1 空间数据概述空间数据概述空间数据是指与二维、三维或更高维空间的空间坐标及空间范围相关的数据 空间数据的复杂性特征有：空间属性之间的非线性关系空间数据的多尺度特征空间信息的模糊性空间维数的增高空间数据的缺值515.1.1.2 15.1.1.2 空间查询工作空间查询工作
3、空间查询及其操作的主要特点有：空间操作相对复杂和不精确空间连接（Spatial Join）问题相同的地理区域经常有不同的视图一个空间实体可用空间和非空间的属性来描述6很多基本空间查询是数据挖掘行为的基础，这些查询包括：区域查询或范围查询：寻找那些与在查询中指定区域相交的实体。最邻近查询：寻找与指定实体相邻的实体距离扫描：寻找与指定的实体相距一段确定距离的实体，这个距离是逐渐增大的。小提示：所有这些查询都可以用来辅助空间聚类或分类操作。15.1.1.2空间查询工作空间查询工作 715.1.2 15.1.2 空间数据挖掘中的基础计算模型空间数据挖掘中的基础计算模型 空间关系计算 (1)常用的两个空
4、间实体之间的距离有：最小值方法最小值方法：定义实体A和B的距离为A中的所有点与和B中的所有点之间的欧氏或曼哈顿距离中最小的，即 （15-1）8大值方法大值方法：定义实体A和B的距离为A中的所有点与和B中的所有点之间的欧氏或曼哈顿距离中最大的，即 （15-2）平均值方法平均值方法：定义实体A和B的距离为A中的所有点与和B中的所有点之间的欧氏或曼哈顿距离的平均值，即 （15-3）空间关系计算空间关系计算9中心方法中心方法：定义实体A和B的距离为A中的中心点与和B中的中心点之间的欧氏或曼哈顿距离的平均值，即 (15-4)其中最简单的方法就是取实体A的中心点和B的中心点，该中心点可以通过查找实体的几何
5、中心来识别。空间关系计算空间关系计算1015.1.2 15.1.2 空间数据挖掘中的基础计算模型空间数据挖掘中的基础计算模型（2）两个空间实体之间存在若干拓扑关系。这些关系基于两个实体的位置：分离（Disjoint）：A与B分离，表示B中任何点都不在A中，反之亦然。重叠/相交：A与B重叠或相交表示至少有一个点既在A里也在B里。等价：A与B这两个实体的所有点都是共有的。11l包含于：A包含于B，表示A的所有点都在B里，反之不一定。l覆盖/包含：A覆盖或包含B，当且仅当B包含于A。(3)方位是描述两个点状实体位置关系的一种度量，如果要分析面状实体间的方位关系，则应把多边形转换为重心点或其它点状实体
6、。15.1.2 15.1.2 空间数据挖掘中的基础计算模型空间数据挖掘中的基础计算模型1215.1.2.215.1.2.2空间实体信息模型空间实体信息模型 空间场模型空间场模型空间场模型主要用于模拟在空间上连续分布的地理现象，属性取值既可以式连续的，也可以是离散的。空间场数据模型的优点是数据结构简单，便于空间法分析与模拟。缺点是不利于表达空间实体，数据量也大。1315.1.215.1.2空间数据挖掘中的基础计算模型空间数据挖掘中的基础计算模型 空间要素模型图15-3 基于要素的空间信息模型对现实世界的抽象基于要素的空间信息模型对现实世界的抽象现实世界现实世界专题要素专题要素1实体实体1专题要素
7、专题要素2专题要素专题要素n实体实体2实体实体n时间特征时间特征属性特征属性特征空间关空间关 系特征系特征几何特征几何特征1415.1.2 15.1.2 空间数据挖掘中的基础计算模型空间数据挖掘中的基础计算模型小提示：实体必须符合三个条件：可被识别，重要（与问题相关），可被描述（有特征）。表15-2 现实世界与信息世界的对应关系 1515.1.215.1.2空间数据挖掘中的基础计算模型空间数据挖掘中的基础计算模型空间网络模型空间网络模型空间网络结构模型中地理现象被抽象为链、结点以及它们之间的连通关系（图15-4 对空间网络的抽象）。图的形式化定义为 （15-10）图15-4 对空间网络的抽象A
8、CDB1615.1.215.1.2空间数据挖掘中的基础计算模型空间数据挖掘中的基础计算模型位置位置属性一体化的空间实体信息模型属性一体化的空间实体信息模型 一般空间实体的形式化模型为一个四元组，分别代表空间实体四个方面的特征。其中位置特征数据为 （15-11）1715.1.3 15.1.3 空间数据挖掘基础空间数据挖掘基础 空间数据挖掘（SDM）是指对空间数据库中非明确存在的知识，空间关系，或其它有意义的模式等的提取。15.1.3.1 15.1.3.1 空间数据挖掘的框架体系空间数据挖掘的框架体系 一般认为可以大致分为三 层结构，如图15-5空间数据挖掘的体系结构所示。其中，第一层是数据源；第
9、二层是挖掘器；第三层是用户界面。18图15-5 空间数据挖掘的体系结构1915.1.3.2 15.1.3.2 空间数据挖掘的方法体系空间数据挖掘的方法体系空间评价。空间分类与聚类。空间分布计算。空间优化。空间回归分析。空间动态模拟与预测。空间与时序关联知识归纳。2015.1.415.1.4几种空间数据挖掘算法几种空间数据挖掘算法15.1.4.1 空间关联分析 空间关联规则挖掘是传统关联规则挖掘的延伸，常用最小支持度和最小可信度来作为基本的统计参数，由于空间数据的特点，往往是在多层概念上进行归纳。21 挖掘空间关联规则的有效方法是自上而下、逐步加深的搜索技术。首先在高的概念层次进行搜索，在较粗的
10、精度级别查找频繁发生的模式和在这些模式中较强的隐含关系；然后，对频繁发生的模式加深搜索至较低的概念层次，这种处理持续到找不到频繁发生的模式为止。空间关联分析空间关联分析2215.1.4.115.1.4.1空间关联分析空间关联分析典型的五步算法：典型的五步算法：Step1：通过给定的查询抽取出相关的数据。Step2：应用一个粗的空间运算方法，计算整个相关数据的集合。Step3：过滤出那些支持度小于最小支持度阈值的1阶谓词。Step4：应用一个细化的空间计算方法，从所导出的粗的谓词集合中计算谓词。Step5：向低层深入，在多个概念层次上找到关联规则的完整集合。2315.1.4.215.1.4.2空
11、间分类算法和空间趋势分析空间分类算法和空间趋势分析空间分类指分析空间对象导出与一定空间特征有关的分类模式 小小提提示示：空间因素可以是非空间属性和空间属性，也可以是二者同时使用。(1)对于样本数据的训练可以通过改造传统的分类算法来完成 (2)空间决策树 空间分类技术建构决策树采用两步方法。这个方法的思想基础是空间实体可以与其接近的实体来描述。假设类的描述是基于与实体相近最相关的谓词的集合。建造一个决策树24空间决策树有五个主要步骤：根据已知的分类，从数据D中找到例子S。确定最佳谓词p用来分类。一般首先在较粗的层次中寻找相关谓词，然后再在较为细化的层次。空间决策树空间决策树25找到最佳的缓冲区大
12、小和形状。对于取样中的每个实体，它周围的区域被称为缓冲区。目标是选择一个能产生对测试集中的类型进行最不同的缓冲区。使用p和C，对每个缓冲区归纳谓词。使用泛化的谓词和ID3建造二叉树T。2615.1.4.3 15.1.4.3 空间聚类方法空间聚类方法 空间聚类分析是空间模式识别和空间数据挖掘的重要手段之一。它的目的是要在一个较大的多维数据集中根据距离的计算找出簇，或稠密区域。小提示：空间聚类找到的聚类不应该依赖于检验空间中的点的顺序，而且聚类也不应该受不相干的点影响。本节介绍的空间聚类方法是基于坐标属性一体化的空间信息模型，2715.1.4.3 15.1.4.3 空间聚类方法空间聚类方法从两类直
13、至每个样本为一类的系统聚类算法步骤如下：对地理特征向量中的每一个元素进行无量纲化。令类别数k=2，置迭代误差阈值emin=0.100001(可根据需要设置)。置迭代次数t=0，k 个初始聚类中心为：对第t 次迭代,若有 则把样本Si 分配到第j0 个聚类域 。如此，所有的m 个样本可以被划分到k 个聚类域 中.28计算新的聚类中心 式中Nj 为第j个聚类域中包含的样本个数。若 则停止迭代，第t 次迭代结果为划分为k 个类别的聚类方案，转向(7)；否则,t=t+1，转向(4)。当k m 时，k=k+1，转向(3)；否则，系统聚类结束。聚类算法步骤聚类算法步骤(续）续）2915.2 15.2 多媒
14、体数据挖掘多媒体数据挖掘15.2.1 多媒体数据挖掘的特点多媒体数据复杂。多媒体信息语义关联性强。多媒体信息具有时空相关性。知识的表达和解释比较困难，多媒体挖掘所得出的模式往往比较隐晦。3015.2.2 15.2.2 多媒体数据挖掘概述多媒体数据挖掘概述多媒体数据挖掘典型系统结构 多媒体数据挖掘系统是在基于内容的多媒体数据检索系统发展的基础上出现的。它的一般结构图如图15-8所示。图图15-8多媒体数据挖掘系统结构多媒体数据挖掘系统结构挖掘任务媒体数据库多媒体数据集知识库挖掘引擎数据立方体媒体属性特征数据预处理用户挖掘接口3115.2.2.2 15.2.2.2 多媒体数据挖掘的内容多媒体数据挖
15、掘的内容 关于多媒体数据挖掘的内容一般包括图像数据挖掘、音频数据挖掘、关于多媒体数据挖掘的内容一般包括图像数据挖掘、音频数据挖掘、视频数据挖掘等。视频数据挖掘等。图像挖掘图像挖掘 图像包含着丰富的视觉特性和空间特性。视频挖掘视频挖掘 视频包括丰富的内容特性，除了图像具有的视觉特性和空间特性外,还具有时间特性、视频对象特性和运动特性等。32多媒体数据挖掘的内容多媒体数据挖掘的内容音频挖掘音频挖掘 音频挖掘通常有两种途径:运用语音识别技术将语音识别成文字，将音频挖掘转换成文本挖掘；直接从音频中提取声音特征，如音调、韵律等,运用聚类的方法分析声音模式。Web Web 挖掘挖掘多媒体综合挖掘多媒体综合
16、挖掘 多媒体概念与单媒体的区别在于，它是一个集成的系统概念，媒体之间有联系。3315.2.3 15.2.3 多媒体数据挖掘方法多媒体数据挖掘方法在图像和视频数据库中可以挖掘涉及多媒体对象的关联规则，至少包含以下三类：图像内容和非图像内容特征间的关联与空间关系无关的图像内容的关联与空间关系有关的图像内容的关联3415.2.3.2 15.2.3.2 多媒体数据的相似搜索多媒体数据的相似搜索对多媒体数据相似性搜索，主要考虑两种多媒体标引和检索系统：（1）基于描述的检索系统，主要是在图像描述之上建立标引和执行对象检索，如关键字、标题、尺寸、创建时间等；（2）基于内容的检索系统，它支持基于图像内容的检索
17、，如颜色构成、质地、形状、对象和小波变换等。35两种查询两种查询在基于内容的检索系统中,通常有两种查询：基于图像样本的查询（image sample-based queries）。图像样本查询是指找出所有与给定图像样本相似的图像。图像特征描述查询(image feature specification queries)。图像特征描述查询是指给出图像的特征描述或概括3615.2.3.2 15.2.3.2 多媒体数据的相似搜索多媒体数据的相似搜索 到目前为止人们已经提出了几种在图像数据库中基于图像特征标识的相似检索方法：基于颜色直方图的特征标识多特征构成的特征标识基于小波的特征标识带有区域粒度的小
18、波特征标识3715.2.3.3 15.2.3.3 多媒体数据的分类和预测分析多媒体数据的分类和预测分析 我们也可以对多媒体数据进行分类和预测分析，尤其用在如天文学、地震学、地理科学等的研究中。分类是多媒体数据的一种分析形式,它根据媒体某一特征(或一组特征)将数据分成不同的类。它是一个两步过程：第1步，建立一个模型，用来描述预定义类集。第2步，使用模型进行分类。3815.3 15.3 文本挖掘文本挖掘15.3.1文本挖掘概述 数据库挖掘处理的对象是结构化的数据，目的是从结构化数据源中发现不同属性之间的关联规则，或者是对数据对象进行聚类及分类处理，或者是构造数据的预测模型。39文本挖掘的一般过程文
19、本挖掘的一般过程文本挖掘的一般过程文本挖掘过程一般包括文本准备、特征标引、特征集缩减、知识模式的提取、知识模式的评价、知识模式的输出等过程.文本特征标引特征集缩减知识模型的提取知识模型的评价知识模型的输出4015.3.1.2 15.3.1.2 文本挖掘的主要任务文本挖掘的主要任务文本挖掘的主要目标是获得文本的主要内容特征文本挖掘的主要目标是获得文本的主要内容特征 特征提取 主题标引 文本分类 文本聚类 自动摘要4115.3.1.3 15.3.1.3 文本挖掘与信息检索文本挖掘与信息检索文本的预处理 目前，人们在对文本集进行自动分类、自动聚类、自动摘要或更深层次的挖掘处理时常常采用这样的策略:先
20、用一个高度概括的向量来表示一篇文本，将文本集概括成一个向量集，这个向量集等同于一个二维表格，然后通过对文本集对应的向量集进行相关的分析，达到对文本集进行自动分类、自动聚类、自动产生文摘或自动挖掘出更深层的隐含知识的目的。42文本的表示文本的表示 文本表示是指用文本的特征信息集合来代表原来的文本.向量空间模型的基本思想是以向量来表示文本，其中为第i个特征项的权重。相对词频的计算方法主要运用TF-IDF公式。公式如下：（15-15）4315.3.2.2 15.3.2.2 文本特征标引文本特征标引所谓标引，是指给出信息内容特征的过程。汉语自动分词方法有多种，主要有词典法、切分标记法等。1词典分词法
21、2.切分标记分词法 小提示：切分标记法的典型代表是非用词后缀表法。该法将汉字分为“非用字”、“条件用字”、“表内用字”、“表外用字”。主要利用“非用字”和“条件用字”进行词语的切分。4415.3.2.3 15.3.2.3 文本维度规约文本维度规约1 1基于评估函数的方法基于评估函数的方法 基于评估函数的特征集缩减算法使用特征独立性假设以简化特征选择。2 2潜在语义标引潜在语义标引潜在语义标引法利用矩阵理论中的“奇异值分解”技术，将词频矩阵转化为维数大大减小的奇异矩阵。4515.3.3.1 15.3.3.1 文本的自动分类文本的自动分类文本自动分类的一般过程如下：首先，取一个预分类的文本集作为训
22、练集。然后，分析训练集以导出分类模型。通常，需要用一个检验过程对该分类模型求精。所导出的分类模型可以用于其它联机文本分类。46文本分类的典型的分类方法文本分类的典型的分类方法 下面介绍几种已经成功应用于文本分类的典型的分类方法。1简单向量距离分类 具体步骤如下:(1).根据训练集文本向量空间模型计算每类文本集的中心向量；(2).将新文本表示为特征向量；(3).计算新文本特征向量和每类中心向量间的相似度；(4).比较每类中心向量与新文本的相似度，将文本分到相似度最大的那个类别中。47文本分类的典型的分类方法（续）文本分类的典型的分类方法（续）2简单贝叶斯分类算法算法具体步骤如下：计算特征词属于每
23、个类别的概率向量 。对于新文本di，计算该文本属于类Cj 的概率。比较新文本属于所有类的概率，将文本分到概率最大的那个类别中。48文本分类的典型的分类方法（续）文本分类的典型的分类方法（续）3 3K K最近邻居（最近邻居（KNNKNN）算法）算法 该算法的基本思路是:在给定新文本后，考虑在训练文本集中与该新文本距离最近(最相似)的K篇文本，根据这几篇文本所属的类别判定新文本所属的类别，该算法具体的步骤如下:49K K最近邻居（最近邻居（KNNKNN）算法）算法(1).根据特征项集合重新描述训练文本向量；(2).将新文本表示为特征向量；(3).比较类的权重，将文本分到权重最大的那个类别中 (4)
24、.在训练文本集中选出与新文本最相似的K个文本，计算公式为：.(15-16)50 (5).在新文本的K个邻居中，依次计算每类的权重，计算公式：.(15-17)其中，为新文本的特征向量，为相似度计算公式，为类别属性函数，即如果 属于类 ，那么函数值为1，否则为0。K K最近邻居（最近邻居（KNNKNN）算法）算法5115.3.3.2 15.3.3.2 文本聚类文本聚类1 1光谱聚类方法光谱聚类方法 首先，对原始数据进行光谱嵌入（维度归约），然后对维度归约后的文本空间运用传统的聚类算法（如k均值）。52文本聚类文本聚类(续续)2 2混合模型聚类方法混合模型聚类方法 用混合模型对文本数据聚类包括两个步
25、骤：(1)基于文本数据和附加的先验知识估计模型参数；(2)基于估计的模型参数推断聚类。5315.3.3.3 15.3.3.3 基于遗传算法（基于遗传算法（GAGA）的文本聚类）的文本聚类 遗传算法(GA)为文本聚类提供了一种非层次的聚类方法，其核心思想是使簇内文本间的相似度最大化。其核心思想是使簇内文本间的相似度最大化。5415.4 15.4 挖掘互联网挖掘互联网 15.4.1 15.4.1 挖掘挖掘WebWeb页面布局结构页面布局结构 Web结构挖掘属于信息结构（IA）方面的研究内容。对对于一个站点而言，按结构层次高低可以分出三种结构：站于一个站点而言，按结构层次高低可以分出三种结构：站点结
26、构、页面（框架）结构、页内结构。点结构、页面（框架）结构、页内结构。5515.4.2 15.4.2 挖掘挖掘WebWeb链接结构识别权威链接结构识别权威WebWeb页面页面 15.4.2.1 Page-rank15.4.2.1 Page-rank方法方法 大量的Web链接信息提供了丰富的关于Web内容相关性、质量和结构方面的信息，这对Web挖掘是可以利用的一个重要资源。5615.4.2 15.4.2 挖掘挖掘WebWeb链接结构识别权威链接结构识别权威WebWeb页面页面基于以上考虑，人们提出了如下的概念：基于以上考虑，人们提出了如下的概念：Web可以用一个有向图来表示，G=（V，E），V是页
27、面的集合，E是页面之间的超链接集合。页面抽象为图中的顶点，而页面之间的超链接抽象为图中的有向边。顶点V的入边表示对V的引用，出边表示V引用了其他的页面。所以Web页面之间的超链接揭示了Web结构。5715.4.2 15.4.2 挖掘挖掘WebWeb链接结构识别权威链接结构识别权威WebWeb页面页面 链接文本（Anchor Texts）可以用来对被引用的页面进行索引（例如：Webor,WWW，Google）。超链接可以用来计算页面的rankings core,通过超链接可以将一个页面的ranking core传递到相邻的页面。5815.4.2 15.4.2 挖掘挖掘WebWeb链接结构识别权威
28、链接结构识别权威WebWeb页面页面 Page-rank的基本思想如下：页面被多次引用，则这个页面很可能是重要的。一个页面尽管没有被多次引用，但被一个重要页面引用，则这个页面很可能是重要的。一个页面的重要性被均分并被传递到它所引用的页面。5915.4.2 15.4.2 挖掘挖掘WebWeb链接结构识别权威链接结构识别权威WebWeb页面页面 Hub/authority方法 挖掘Web上的多媒体数据 关于多媒体的数据挖掘一般包括图像数据挖掘、音频数据挖掘、视频数据挖掘等。60挖掘挖掘WebWeb链接结构识别权威链接结构识别权威WebWeb页面页面15.4.3.1图像挖掘 图像挖掘（Image M
29、ining）指对图形图像数据信息的自动处理和知识发现，包含模式识别、图像检索以及特征分析等。图像的空间特性是非常重要的特性，包括图像中各种对像的模式、布局、空间层次等。6115.4.3.2 15.4.3.2 音频挖掘音频挖掘音频挖掘（Audio Mining）指对音频信息的自动处理和分析过程。语音挖掘的另外一个用途在于将语音对应到个人6215.4.3.2 15.4.3.2 音频挖掘音频挖掘15.4.3.3 15.4.3.3 视频挖掘视频挖掘15.4.4 Web15.4.4 Web文档的自动分类文档的自动分类 15.4.5 Web15.4.5 Web使用挖掘使用挖掘6315.4.3.2 15.4
30、.3.2 音频挖掘音频挖掘15.4.5.115.4.5.1模式发现模式发现 要解决的问题就是数据的预处理，它主要包括两个部分：（1）数据清洗（Data Cleaning）:包括无关记录的剔除、判断是否有重要的访问没有被记录、用户的识别等问题。（2）事务识别（Transaction Identification）:是指将页面访问序列划分为代表Web事务或用户会话的逻辑单元。如路径分析、关联规则挖掘、时序模式以及聚类和分类技术。6415.4.5.15.4.5.模式的分析模式的分析相关分析方法如下相关分析方法如下：(1)可视化技术对于理解Web用户的行为模式来讲是一个自然的选择。(2)联机分析处理（
31、OLAP）技术也可以应用到模式的分析中来。(3)计划挖掘（plan mining）挖掘通常的存取规律，可以调整Web连接，改善性能。65相关分析方法相关分析方法(4)相关序列存取模式分析，可以对服务器的缓存、预取和交换参数进行调整。(5)趋势分析，可以了解Web下在发生的变化，用户的个性化分析可以为用户提供定制的服务。6615.4.5.15.4.5.使用记录挖掘的基本流程使用记录挖掘的基本流程 对Web访问日志（Web Log）进行分析和挖掘要经过一系列的数据准备工和和建模工作。一个基本的流程包括如下步骤。（1）首先要对Web Log进行清洗、过滤和转换，从中抽取感兴趣的数据。6715.4.5
32、.15.4.5.使用记录挖掘的基本流程使用记录挖掘的基本流程（2）将资源的类型、资源的大小、请求的时间、在资源上停留的时间、请求次数、来自不同Internet域的请求次数、事件、会话、错误次数作为在这些维变量下的度量变量建立数据立方体（Data Cube）。（3）利用成熟的数据挖掘技术（如特征、分类、关联、预测、时间序列分析、趋势分析）6815.5 15.5 挖掘数据流挖掘数据流 为了从数据流中发现知识或模式，有必要开发单遍扫描的、联机的、多层的、多维的流处理和分析方法。单遍扫描的联机数据分析方法，不应该只限于流数据，它对于处理海量的非数据流也是至关重要的。6915.5.1 15.5.1 流数
33、据处理方法和流数据系统流数据处理方法和流数据系统 本节，我们考虑一些常用的大纲数据结构和技术。1 1随机抽样随机抽样 一种叫做水库抽样，可以用来无放回的选取一个无偏的S个元素的随机样本，没有更换。水库抽样的想法相对简单。2 2滑动窗口滑动窗口 基本的思想是：仅仅基于最近的数据做出决策，而不是对目前为止看到的所有数据或对某个样本进行计算。7015.5.1 15.5.1 流数据处理方法和流数据系统流数据处理方法和流数据系统 3.3.直方图直方图 直方图是一种大纲的数据结构，可以用来近似数据流中元素值的频率分布。4.4.多分辨方法多分辨方法 处理大量数据的一种常见方式是使用数据归约方法。一种流行的数
34、据归约方法是采用分治策略，如多分辨率数据结构5.5.数据流管理系统和流查询数据流管理系统和流查询 流数据的查询处理结构包括三个部分：终端用户，查询处理器和临时空间（这可能由主存和磁盘构成）。71流流OLAPOLAP和流数据立方体（续）和流数据立方体（续）1 1压缩时间尺度的时间维：倾斜时间框架压缩时间尺度的时间维：倾斜时间框架 这种模型对许多分析任务来说是足够的，也能保证驻留在内存或存储在硬盘上的数据总量很小。2.2.关键层关键层 第一层称作最小兴趣层（minimal interesting layer），是分析人员想要研究的最小兴趣层。第二层称观察层（observation layer），是
35、分析人员（或自动化系统）希望不断研究数据的层。723.3.流立方体的部分物化流立方体的部分物化 常用路径立方体计算（popular path cubing）,它通过一条常用下钻路径，从最小兴趣层到观察层执行上卷操作，仅仅物化该路径中的层次，其它层仅在需要的时候计算。这种方法在空间，计算时间和灵活性上取得了适度平衡，并具有快速增量聚集时间，快速下钻时间，并且空间需求很小。流流OLAPOLAP和流数据立方体（续）和流数据立方体（续）7315.5.3 15.5.3 数据流中的频繁模式挖掘数据流中的频繁模式挖掘 1.1.数据流频繁模式挖掘数据流频繁模式挖掘2.2.数据流频繁模式挖掘算法数据流频繁模式挖
36、掘算法 数据流频繁模式挖掘的关键问题就是如何快速对数据流中所出现的模式进行计数。74数据流所出现的模式数据流所出现的模式数据流所出现的模式分成三类数据流所出现的模式分成三类:(1)当sup(X)s 时,称X 为频繁模式；(2)当sup(X)s 时,称X 为潜在频繁模式；(3)当sup(X)s 时,称X 为非频繁模式,并在算法中舍弃非频繁的模式以减少算法的空间复杂度。7515.5.4 15.5.4 动态数据流的分类动态数据流的分类 增量式方法又称为在线式、连续式或序列式方法等,定义为S t=(x,y)|y=f(x),t=1,2,。数据流挖掘的增量式方法一般都假设取得的样本是由平稳分布的数据中所获
37、得。很多研究者提出了解决数据流上概念漂移问题的分类技术。7615.5.4 15.5.4 动态数据流的分类动态数据流的分类 1.1.数据平稳分布的分类方法数据平稳分布的分类方法 VFDT(very fast decision tree)是一种基于Hoeffding 不等式建立决策树的方法,它通过不断地将叶节点替换为决策节点而生成。其中每个叶节点都保存有关于属性值的统计信息,这些统计信息用于计算基于属性值的测试。7715.5.4 15.5.4 动态数据流的分类动态数据流的分类信息增益用于表达计算分类到达该节点的样本所需要的信息,其计算公式为 属性j 的熵为 ,其中 表示类别k 已知的情况下属性值取
38、i 的概率。VFDT 的另一重要性质是它所产生的决策树在大量减少处理样本数目的同时,能够保证和使用全部样本所产生的决策树具有无限接近的精度。7815.5.4 15.5.4 动态数据流的分类动态数据流的分类2.数据带概念漂移的分类方法数据带概念漂移的分类方法下面介绍各种概念漂移学习方法。下面介绍各种概念漂移学习方法。FLORA FLORA 框架框架 由于FLORA 算法每次只能处理一个样本,所以它对数据到达的速度是有限制的。79 CVFDTCVFDT 该算法在叶节点可能会产生概念漂移时产生一棵备选子树,并且在新子树变得更精确时用新子树替代原先的子树,从而解决了概念漂移所导致的预测性能下降的问题。
39、离线离线C4.5C4.5 Harries 和Sammut基于C4.5 开发了一个离线学习系统,该系统将数据流分为一个关于时间的“概念聚类”集合。8015.5.5 15.5.5 聚类演变数据流聚类演变数据流 为了对数据流进行有效的聚类，几个新的方法已制定，具体情况如下：计算和存储过去汇总的数据应用分治策略增量聚类传入的数据流进行微聚类以及宏聚类分析利用多个时间粒度为分析集群的演变把流聚类划分为联机和脱机处理81聚类演变数据流聚类演变数据流 已开发了几个算法为聚类数据流的算法。这里介绍其中两个，即STREAMSTREAM和和CluStreamCluStream。1.STREAM1.STREAM：基
40、于：基于k k中位数的流聚类算法中位数的流聚类算法 STREAM是一种单遍扫描，常数因子的近似算法，是为K-中位数问题开发的。STREAM源于k中位数聚类，使用有限的时间和空间。8215.5.5 15.5.5 聚类演变数据流聚类演变数据流 2.CluStreamCluStream：聚类演变的数据流：聚类演变的数据流 CluStream是一种基于用户指定的、联机聚类查询的演变数据流聚类算法。联机微簇的处理分为两个阶段进行：联机微簇的处理分为两个阶段进行：（1）收集统计数据 （2）更新微簇。8315.6 15.6 时间序列数据挖掘时间序列数据挖掘 15.6.115.6.1趋势分析趋势分析 “如何处
41、理时序数据？”目前一般有四种主要的变化成分用于特征化时序数据：1长期或趋势变化(trend movement)2循环运动或循环变化(cyclic movement or cyclic variations)3季节性运动或季节性变化(seasonal movements or seasonal variations)4非规则或随机变化（irregular or random movements）84时间序列数据挖掘时间序列数据挖掘 “怎样确定数据的趋势?”一个确定的趋势的常用方法是用下面的算数均值序列计算n阶移动平均：8515.6.2 15.6.2 时间序列分析中的相似性搜索时间序列分析中的相似
42、性搜索 “什么是相似搜索（similarity search）？”通常数据库查询是要找出符合查询的精确数据，相似搜索与之不同，它是找出与给定查询序列最接近的数据序列。8615.6.2 15.6.2 时间序列分析中的相似性搜索时间序列分析中的相似性搜索 数据变换(data transformation)：从时间域(time domain)到频率域(frequency domain)对时序数据的相似分析，通常采用欧氏距离作为相似计算的依据。两个常见的独立于数据的变换是离散傅立叶变换（DFT）和离散小波变（DWT）。8715.6.2 15.6.2 时间序列分析中的相似性搜索时间序列分析中的相似性搜索
43、能够处理存在间隙和偏移与振幅差异的相似搜索的执行步骤如下：1原子匹配（atomic matching）2窗口结合(window stitching)3子序列排序(subsequence ordering)8815.6.2 15.6.2 时间序列分析中的相似性搜索时间序列分析中的相似性搜索下图是子序列S(sequence S)和子序列T(sequence T)的原始序列（Original sequence）、删除间隙（Removing gap）、偏移变换（offset translation）和振幅变换（Amplitude scaling）的差别。此图是在时序数据中的子序列匹配：原始序列形状相同
44、，但需要调整以处理存在于间隙、偏移和振幅中的差异。这些调整允许子序列在一定宽度的范围内匹配。899015.7 15.7 挖掘事务数据库中的序列模式挖掘事务数据库中的序列模式 15.7.1 15.7.1 序列模式挖掘：概念和原语序列模式挖掘：概念和原语 “什么是序列模式挖掘？”序列模式挖掘是指挖掘相对时间或其它模式出现频率高的模式。举个例子，顺序模式是“顾客在购买佳能数码相机有可能在一个月以内购买HP彩色打印机”。项集是一个非空的商品名的集合,D 的第三个属性便是项集。9115.7 15.7 挖掘事务数据库中的序列模式挖掘事务数据库中的序列模式序列是一个向量,这个向量的每一维均为项集。用(s1，
45、s2，sn)表示向量,其中sj 为项集；对于两个向量S1=、S2=,若存在整数0i1i2inm+1 使得 ,则称S1 包含于S2,记作在一个序列集中,若序列S 不包含于任何其它的序列,我们称S 是极大的；在D 中,我们可以将某个顾客的项集按时间顺序排成一个序列,我们称这个序列为这个顾客的顾客序列；92若一个序列包含于某个顾客的顾客序列中,则称此顾客支持此序列；支持某序列的顾客数与总顾客数之比称为此序列的支持率；当一个序列的支持率不小于一个给定的值时,称这个序列为频繁序列；而这个值称为最小支持,记作min_sup；序列所拥有的项集个数称为序列的长度。一个长度为k 的序列称为k 序列；设为1 序列
46、,I 为其中唯一项集。若某客户支持,则称此客户支持项集I；若为频繁序列,则称I 为频繁项集。9315.7.2 15.7.2 挖掘序列模式的可伸缩方法挖掘序列模式的可伸缩方法 对于序列模式挖掘，如何开发有效的和可伸缩的方法？最近的研究在这两方面取得了进展：（1）挖掘序列模式完全集的有效方法，（2）仅挖掘序列模式闭集的有效方法 第一类是基于R.Agrawal等人提出的Apriori特性的算法，主要包括AprioriAll算法、GSP算法、SPADE算法等.94挖掘序列模式的可伸缩方法挖掘序列模式的可伸缩方法 AprioriAll算法将序列的长度定义为序列中包含的项集的数量。该算法将序列模式挖掘过程
47、分为五个阶段。(1)排序阶段 (2)频繁项集阶段 (3)转换阶段 (4)序列阶段 (5)最大序列阶段9515.7.2 15.7.2 挖掘序列模式的可伸缩方法挖掘序列模式的可伸缩方法 第二类是J.Han等人提出的基于模式增长的算法，包括FreeSpan算法、PrefixSpan算法等。PrefixSpan(Prefix-projected equential Pattern Mining)算法和FreeSpan算法都是基于模式增长的挖掘方法。9615.7.3 15.7.3 基于约束的序列模式挖掘基于约束的序列模式挖掘 约束可以用多种形式表示。可能是属性，属性质之间的联系或者结果模式中的聚集。第一
48、个约束是时间序列的持续时间（duration）T。第二个约束是事件重叠窗口（event folding window），w。第三个约束是被发现的模式中时间之间的时间间隔（interval）int。9715.7.4 15.7.4 时间相关序列数据的周期性分析时间相关序列数据的周期性分析 “什么是周期分析？”周期分析（periodicity analysis）是指对周期模式的挖掘，即在时序数据库中找出重复出现的模式。98 周期模式挖掘可以从不同的角度观察，基于模式覆盖，可以把模式周期分为三类：挖掘全周期模式（full periodic pattern）挖掘部分周期模式(partial period
49、ic pattern)挖掘循环或周期关联规则(cyclic or periodic association rule)9915.8 15.8 挖掘生物学数据中的序列模式挖掘生物学数据中的序列模式 挖掘生物学数据中的序列模式 生物信息学是一个充满活力的新兴的研究领域，它将计算机技术应用分子生物学，并开发新的算法和方法来管理和分析生物学数据。生物学序列比对 生物序列比对的问题可以描述如下：对于给定的两个或多个输入生物序列，识别具有长的恒定子序列的相似序列。10015.8 15.8 挖掘生物学数据中的序列模式挖掘生物学数据中的序列模式 双比对 有两个有影响的启发式比对程序：(1)BLAST (2)F
50、ASTA。二者都在查询序列和目标数据库之间寻找最高得分的局部比对。它们的基本思想是：首先确定最高得分的短段，然后扩展它们得到最优比对。10115.8.1.2 15.8.1.2 局部比对算法局部比对算法BLASTBLAST BLAST算法是Altschul,Gish,Miller等人1990年左右在美国国家生物技术信息中心首先提出的。BLAST算法通过把比较序列分裂成序列断片并在这些词中开始寻找匹配，从而提高查询的整体速度。10215.8.1.2 15.8.1.2 局部比对算法局部比对算法BLASTBLAST多序列比对方法 多序列比对通常对氨基酸序列集进行，该序列集被认为具有相似的结构，其目标是