复杂对象数据挖掘

复杂对象数据挖掘1第1页，共111页，2023年，2月20日，星期一第15章复杂对象数据挖掘

2第2页，共111页，2023年，2月20日，星期一15.1空间数据库挖掘

15.2多媒体数据挖掘

15.3文本挖掘15.4挖掘万维网15.5挖掘数据流15.6时间序列数据挖掘15.7挖掘事务数据库中的序列模式15.8挖掘生物学数据中的序列模式3第3页，共111页，2023年，2月20日，星期一15.1空间数据库挖掘

空间数据库挖掘（SDM）实质上是空间信息技术发展的必然结果，它是数据库挖掘（DM）的一个重要分支，面对的都是空间数据库（spatialdatabase,SDB）。空间实体之间又具有空间拓扑、空间距离、空间方位这3种关系

4第4页，共111页，2023年，2月20日，星期一15.1.1空间数据概述空间数据是指与二维、三维或更高维空间的空间坐标及空间范围相关的数据空间数据的复杂性特征有：

空间属性之间的非线性关系空间数据的多尺度特征空间信息的模糊性空间维数的增高空间数据的缺值5第5页，共111页，2023年，2月20日，星期一

空间查询工作

空间查询及其操作的主要特点有：空间操作相对复杂和不精确空间连接（SpatialJoin）问题相同的地理区域经常有不同的视图一个空间实体可用空间和非空间的属性来描述6第6页，共111页，2023年，2月20日，星期一很多基本空间查询是数据挖掘行为的基础，这些查询包括：区域查询或范围查询：寻找那些与在查询中指定区域相交的实体。最邻近查询：寻找与指定实体相邻的实体距离扫描：寻找与指定的实体相距一段确定距离的实体，这个距离是逐渐增大的。小提示：所有这些查询都可以用来辅助空间聚类或分类操作。

空间查询工作

7第7页，共111页，2023年，2月20日，星期一15.1.2空间数据挖掘中的基础计算模型

空间关系计算

(1)常用的两个空间实体之间的距离有：最小值方法：定义实体A和B的距离为A中的所有点与和B中的所有点之间的欧氏或曼哈顿距离中最小的，即（15-1）8第8页，共111页，2023年，2月20日，星期一大值方法：定义实体A和B的距离为A中的所有点与和B中的所有点之间的欧氏或曼哈顿距离中最大的，即（15-2）平均值方法：定义实体A和B的距离为A中的所有点与和B中的所有点之间的欧氏或曼哈顿距离的平均值，即（15-3）空间关系计算9第9页，共111页，2023年，2月20日，星期一中心方法：定义实体A和B的距离为A中的中心点与和B中的中心点之间的欧氏或曼哈顿距离的平均值，即(15-4)

其中最简单的方法就是取实体A的中心点和B的中心点，该中心点可以通过查找实体的几何中心来识别。

空间关系计算10第10页，共111页，2023年，2月20日，星期一15.1.2空间数据挖掘中的基础计算模型（2）两个空间实体之间存在若干拓扑关系。这些关系基于两个实体的位置：分离（Disjoint）：A与B分离，表示B中任何点都不在A中，反之亦然。重叠/相交：A与B重叠或相交表示至少有一个点既在A里也在B里。等价：A与B这两个实体的所有点都是共有的。11第11页，共111页，2023年，2月20日，星期一包含于：A包含于B，表示A的所有点都在B里，反之不一定。覆盖/包含：A覆盖或包含B，当且仅当B包含于A。(3)方位是描述两个点状实体位置关系的一种度量，如果要分析面状实体间的方位关系，则应把多边形转换为重心点或其它点状实体。15.1.2空间数据挖掘中的基础计算模型12第12页，共111页，2023年，2月20日，星期一空间实体信息模型

空间场模型空间场模型主要用于模拟在空间上连续分布的地理现象，属性取值既可以式连续的，也可以是离散的。空间场数据模型的优点是数据结构简单，便于空间法分析与模拟。缺点是不利于表达空间实体，数据量也大。13第13页，共111页，2023年，2月20日，星期一15.1.2空间数据挖掘中的基础计算模型空间要素模型图15-3基于要素的空间信息模型对现实世界的抽象现实世界专题要素1实体1专题要素2专题要素n实体2实体n时间特征属性特征空间关系特征几何特征14第14页，共111页，2023年，2月20日，星期一15.1.2空间数据挖掘中的基础计算模型小提示：实体必须符合三个条件：①可被识别，②重要（与问题相关），③可被描述（有特征）。表15-2现实世界与信息世界的对应关系

15第15页，共111页，2023年，2月20日，星期一15.1.2空间数据挖掘中的基础计算模型空间网络模型

空间网络结构模型中地理现象被抽象为链、结点以及它们之间的连通关系（图15-4对空间网络的抽象）。

图的形式化定义为

（15-10）

图15-4对空间网络的抽象ACDB16第16页，共111页，2023年，2月20日，星期一15.1.2空间数据挖掘中的基础计算模型位置—属性一体化的空间实体信息模型一般空间实体的形式化模型为一个四元组，分别代表空间实体四个方面的特征。其中位置特征数据为

…（15-11）

17第17页，共111页，2023年，2月20日，星期一15.1.3空间数据挖掘基础

空间数据挖掘（SDM）是指对空间数据库中非明确存在的知识，空间关系，或其它有意义的模式等的提取。

空间数据挖掘的框架体系

一般认为可以大致分为三层结构，如图15-5空间数据挖掘的体系结构所示。其中，第一层是数据源；第二层是挖掘器；第三层是用户界面。18第18页，共111页，2023年，2月20日，星期一图15-5空间数据挖掘的体系结构19第19页，共111页，2023年，2月20日，星期一

空间数据挖掘的方法体系空间评价。空间分类与聚类。空间分布计算。空间优化。空间回归分析。空间动态模拟与预测。空间与时序关联知识归纳。20第20页，共111页，2023年，2月20日，星期一15.1.4几种空间数据挖掘算法

空间关联分析

空间关联规则挖掘是传统关联规则挖掘的延伸，常用最小支持度和最小可信度来作为基本的统计参数，由于空间数据的特点，往往是在多层概念上进行归纳。21第21页，共111页，2023年，2月20日，星期一挖掘空间关联规则的有效方法是自上而下、逐步加深的搜索技术。首先在高的概念层次进行搜索，在较粗的精度级别查找频繁发生的模式和在这些模式中较强的隐含关系；然后，对频繁发生的模式加深搜索至较低的概念层次，这种处理持续到找不到频繁发生的模式为止。空间关联分析22第22页，共111页，2023年，2月20日，星期一空间关联分析典型的五步算法：Step1：通过给定的查询抽取出相关的数据。Step2：应用一个粗的空间运算方法，计算整个相关数据的集合。Step3：过滤出那些支持度小于最小支持度阈值的1阶谓词。Step4：应用一个细化的空间计算方法，从所导出的粗的谓词集合中计算谓词。Step5：向低层深入，在多个概念层次上找到关联规则的完整集合。23第23页，共111页，2023年，2月20日，星期一空间分类算法和空间趋势分析空间分类指分析空间对象导出与一定空间特征有关的分类模式小提示：空间因素可以是非空间属性和空间属性，也可以是二者同时使用。

(1)对于样本数据的训练可以通过改造传统的分类算法来完成(2)空间决策树空间分类技术建构决策树采用两步方法。这个方法的思想基础是空间实体可以与其接近的实体来描述。假设类的描述是基于与实体相近最相关的谓词的集合。建造一个决策树24第24页，共111页，2023年，2月20日，星期一空间决策树有五个主要步骤：根据已知的分类，从数据D中找到例子S。确定最佳谓词p用来分类。一般首先在较粗的层次中寻找相关谓词，然后再在较为细化的层次。空间决策树25第25页，共111页，2023年，2月20日，星期一找到最佳的缓冲区大小和形状。对于取样中的每个实体，它周围的区域被称为缓冲区。目标是选择一个能产生对测试集中的类型进行最不同的缓冲区。使用p和C，对每个缓冲区归纳谓词。使用泛化的谓词和ID3建造二叉树T。26第26页，共111页，2023年，2月20日，星期一

空间聚类方法

空间聚类分析是空间模式识别和空间数据挖掘的重要手段之一。它的目的是要在一个较大的多维数据集中根据距离的计算找出簇，或稠密区域。小提示：空间聚类找到的聚类不应该依赖于检验空间中的点的顺序，而且聚类也不应该受不相干的点影响。本节介绍的空间聚类方法是基于坐标—属性一体化的空间信息模型，27第27页，共111页，2023年，2月20日，星期一

空间聚类方法从两类直至每个样本为一类的系统聚类算法步骤如下：对地理特征向量中的每一个元素进行无量纲化。令类别数k=2，置迭代误差阈值emin=0.100001(可根据需要设置)。置迭代次数t=0，k个初始聚类中心为：对第t次迭代,若有则把样本Si分配到第j0个聚类域。如此，所有的m个样本可以被划分到k个聚类域中.28第28页，共111页，2023年，2月20日，星期一计算新的聚类中心式中Nj为第j个聚类域中包含的样本个数。若则停止迭代，第t次迭代结果为划分为k个类别的聚类方案，转向(7)；否则,t=t+1，转向(4)。当k<m时，k=k+1，转向(3)；否则，系统聚类结束。聚类算法步骤(续）29第29页，共111页，2023年，2月20日，星期一15.2多媒体数据挖掘15.2.1多媒体数据挖掘的特点多媒体数据复杂。多媒体信息语义关联性强。多媒体信息具有时空相关性。知识的表达和解释比较困难，多媒体挖掘所得出的模式往往比较隐晦。30第30页，共111页，2023年，2月20日，星期一15.2.2多媒体数据挖掘概述多媒体数据挖掘典型系统结构

多媒体数据挖掘系统是在基于内容的多媒体数据检索系统发展的基础上出现的。它的一般结构图如图15-8所示。图15-8多媒体数据挖掘系统结构挖掘任务媒体数据库多媒体数据集知识库挖掘引擎数据立方体媒体属性特征数据预处理用户挖掘接口31第31页，共111页，2023年，2月20日，星期一

多媒体数据挖掘的内容关于多媒体数据挖掘的内容一般包括图像数据挖掘、音频数据挖掘、视频数据挖掘等。

图像挖掘

图像包含着丰富的视觉特性和空间特性。视频挖掘视频包括丰富的内容特性，除了图像具有的视觉特性和空间特性外,还具有时间特性、视频对象特性和运动特性等。

32第32页，共111页，2023年，2月20日，星期一多媒体数据挖掘的内容音频挖掘音频挖掘通常有两种途径:①运用语音识别技术将语音识别成文字，将音频挖掘转换成文本挖掘；②直接从音频中提取声音特征，如音调、韵律等,运用聚类的方法分析声音模式。Web挖掘多媒体综合挖掘多媒体概念与单媒体的区别在于，它是一个集成的系统概念，媒体之间有联系。33第33页，共111页，2023年，2月20日，星期一15.2.3多媒体数据挖掘方法

在图像和视频数据库中可以挖掘涉及多媒体对象的关联规则，至少包含以下三类：图像内容和非图像内容特征间的关联与空间关系无关的图像内容的关联与空间关系有关的图像内容的关联34第34页，共111页，2023年，2月20日，星期一

多媒体数据的相似搜索对多媒体数据相似性搜索，主要考虑两种多媒体标引和检索系统：（1）基于描述的检索系统，主要是在图像描述之上建立标引和执行对象检索，如关键字、标题、尺寸、创建时间等；（2）基于内容的检索系统，它支持基于图像内容的检索，如颜色构成、质地、形状、对象和小波变换等。35第35页，共111页，2023年，2月20日，星期一两种查询在基于内容的检索系统中,通常有两种查询：基于图像样本的查询（imagesample-basedqueries）。图像样本查询是指找出所有与给定图像样本相似的图像。图像特征描述查询(imagefeaturespecificationqueries)。图像特征描述查询是指给出图像的特征描述或概括36第36页，共111页，2023年，2月20日，星期一

多媒体数据的相似搜索

到目前为止人们已经提出了几种在图像数据库中基于图像特征标识的相似检索方法：基于颜色直方图的特征标识多特征构成的特征标识基于小波的特征标识带有区域粒度的小波特征标识37第37页，共111页，2023年，2月20日，星期一

多媒体数据的分类和预测分析我们也可以对多媒体数据进行分类和预测分析，尤其用在如天文学、地震学、地理科学等的研究中。分类是多媒体数据的一种分析形式,它根据媒体某一特征(或一组特征)将数据分成不同的类。它是一个两步过程：第1步，建立一个模型，用来描述预定义类集。第2步，使用模型进行分类。38第38页，共111页，2023年，2月20日，星期一15.3文本挖掘15.3.1文本挖掘概述数据库挖掘处理的对象是结构化的数据，目的是从结构化数据源中发现不同属性之间的关联规则，或者是对数据对象进行聚类及分类处理，或者是构造数据的预测模型。

39第39页，共111页，2023年，2月20日，星期一文本挖掘的一般过程文本挖掘的一般过程文本挖掘过程一般包括文本准备、特征标引、特征集缩减、知识模式的提取、知识模式的评价、知识模式的输出等过程

.文本特征标引特征集缩减知识模型的提取知识模型的评价知识模型的输出40第40页，共111页，2023年，2月20日，星期一

文本挖掘的主要任务文本挖掘的主要目标是获得文本的主要内容特征

特征提取主题标引文本分类文本聚类自动摘要41第41页，共111页，2023年，2月20日，星期一

文本挖掘与信息检索文本的预处理目前，人们在对文本集进行自动分类、自动聚类、自动摘要或更深层次的挖掘处理时常常采用这样的策略:先用一个高度概括的向量来表示一篇文本，将文本集概括成一个向量集，这个向量集等同于一个二维表格，然后通过对文本集对应的向量集进行相关的分析，达到对文本集进行自动分类、自动聚类、自动产生文摘或自动挖掘出更深层的隐含知识的目的。42第42页，共111页，2023年，2月20日，星期一文本的表示

文本表示是指用文本的特征信息集合来代表原来的文本.向量空间模型的基本思想是以向量来表示文本，其中为第i个特征项的权重。相对词频的计算方法主要运用TF-IDF公式。公式如下：

…（15-15）43第43页，共111页，2023年，2月20日，星期一

文本特征标引

所谓标引，是指给出信息内容特征的过程。汉语自动分词方法有多种，主要有词典法、切分标记法等。1．词典分词法2.切分标记分词法

小提示：切分标记法的典型代表是非用词后缀表法。该法将汉字分为“非用字”、“条件用字”、“表内用字”、“表外用字”。主要利用“非用字”和“条件用字”进行词语的切分。44第44页，共111页，2023年，2月20日，星期一

文本维度规约1．基于评估函数的方法基于评估函数的特征集缩减算法使用特征独立性假设以简化特征选择。2．潜在语义标引潜在语义标引法利用矩阵理论中的“奇异值分解”技术，将词频矩阵转化为维数大大减小的奇异矩阵。

45第45页，共111页，2023年，2月20日，星期一

文本的自动分类

文本自动分类的一般过程如下：首先，取一个预分类的文本集作为训练集。然后，分析训练集以导出分类模型。通常，需要用一个检验过程对该分类模型求精。所导出的分类模型可以用于其它联机文本分类。46第46页，共111页，2023年，2月20日，星期一文本分类的典型的分类方法

下面介绍几种已经成功应用于文本分类的典型的分类方法。1．简单向量距离分类具体步骤如下:(1).根据训练集文本向量空间模型计算每类文本集的中心向量；(2).将新文本表示为特征向量；(3).计算新文本特征向量和每类中心向量间的相似度；(4).比较每类中心向量与新文本的相似度，将文本分到相似度最大的那个类别中。47第47页，共111页，2023年，2月20日，星期一文本分类的典型的分类方法（续）2．简单贝叶斯分类算法算法具体步骤如下：计算特征词属于每个类别的概率向量。对于新文本di，计算该文本属于类Cj的概率。比较新文本属于所有类的概率，将文本分到概率最大的那个类别中。48第48页，共111页，2023年，2月20日，星期一文本分类的典型的分类方法（续）

3．K最近邻居（KNN）算法

该算法的基本思路是:在给定新文本后，考虑在训练文本集中与该新文本距离最近(最相似)的K篇文本，根据这几篇文本所属的类别判定新文本所属的类别，该算法具体的步骤如下:49第49页，共111页，2023年，2月20日，星期一K最近邻居（KNN）算法(1).根据特征项集合重新描述训练文本向量；(2).将新文本表示为特征向量；(3).比较类的权重，将文本分到权重最大的那个类别中

(4).在训练文本集中选出与新文本最相似的K个文本，计算公式为：

….(15-16)50第50页，共111页，2023年，2月20日，星期一(5).在新文本的K个邻居中，依次计算每类的权重，计算公式：…..(15-17)其中，为新文本的特征向量，为相似度计算公式，为类别属性函数，即如果属于类，那么函数值为1，否则为0。K最近邻居（KNN）算法51第51页，共111页，2023年，2月20日，星期一

文本聚类1．光谱聚类方法首先，对原始数据进行光谱嵌入（维度归约），然后对维度归约后的文本空间运用传统的聚类算法（如k均值）。52第52页，共111页，2023年，2月20日，星期一文本聚类(续)2．混合模型聚类方法用混合模型对文本数据聚类包括两个步骤：(1)基于文本数据和附加的先验知识估计模型参数；(2)基于估计的模型参数推断聚类。53第53页，共111页，2023年，2月20日，星期一

基于遗传算法（GA）的文本聚类

遗传算法(GA)为文本聚类提供了一种非层次的聚类方法，其核心思想是使簇内文本间的相似度最大化。

54第54页，共111页，2023年，2月20日，星期一15.4挖掘互联网

15.4.1挖掘Web页面布局结构

Web结构挖掘属于信息结构（IA）方面的研究内容。对于一个站点而言，按结构层次高低可以分出三种结构：站点结构、页面（框架）结构、页内结构。55第55页，共111页，2023年，2月20日，星期一15.4.2挖掘Web链接结构识别权威Web页面

rank方法

大量的Web链接信息提供了丰富的关于Web内容相关性、质量和结构方面的信息，这对Web挖掘是可以利用的一个重要资源。56第56页，共111页，2023年，2月20日，星期一15.4.2挖掘Web链接结构识别权威Web页面

基于以上考虑，人们提出了如下的概念：

Web可以用一个有向图来表示，G=（V，E），V是页面的集合，E是页面之间的超链接集合。页面抽象为图中的顶点，而页面之间的超链接抽象为图中的有向边。顶点V的入边表示对V的引用，出边表示V引用了其他的页面。所以Web页面之间的超链接揭示了Web结构。57第57页，共111页，2023年，2月20日，星期一15.4.2挖掘Web链接结构识别权威Web页面

链接文本（AnchorTexts）可以用来对被引用的页面进行索引（例如：Webor,WWW，Google）。超链接可以用来计算页面的rankingscore,通过超链接可以将一个页面的rankingcore传递到相邻的页面。58第58页，共111页，2023年，2月20日，星期一15.4.2挖掘Web链接结构识别权威Web页面

rank的基本思想如下：页面被多次引用，则这个页面很可能是重要的。一个页面尽管没有被多次引用，但被一个重要页面引用，则这个页面很可能是重要的。一个页面的重要性被均分并被传递到它所引用的页面。59第59页，共111页，2023年，2月20日，星期一15.4.2挖掘Web链接结构识别权威Web页面Hub/authority方法挖掘Web上的多媒体数据

关于多媒体的数据挖掘一般包括图像数据挖掘、音频数据挖掘、视频数据挖掘等。60第60页，共111页，2023年，2月20日，星期一挖掘Web链接结构识别权威Web页面图像挖掘图像挖掘（ImageMining）指对图形图像数据信息的自动处理和知识发现，包含模式识别、图像检索以及特征分析等。图像的空间特性是非常重要的特性，包括图像中各种对像的模式、布局、空间层次等。61第61页，共111页，2023年，2月20日，星期一

音频挖掘音频挖掘（AudioMining）指对音频信息的自动处理和分析过程。语音挖掘的另外一个用途在于将语音对应到个人62第62页，共111页，2023年，2月20日，星期一

音频挖掘

视频挖掘15.4.4Web文档的自动分类15.4.5Web使用挖掘

63第63页，共111页，2023年，2月20日，星期一

音频挖掘模式发现

要解决的问题就是数据的预处理，它主要包括两个部分：（1）数据清洗（DataCleaning）:包括无关记录的剔除、判断是否有重要的访问没有被记录、用户的识别等问题。（2）事务识别（TransactionIdentification）:是指将页面访问序列划分为代表Web事务或用户会话的逻辑单元。如路径分析、关联规则挖掘、时序模式以及聚类和分类技术。64第64页，共111页，2023年，2月20日，星期一15.4.5.２模式的分析相关分析方法如下：(1)可视化技术对于理解Web用户的行为模式来讲是一个自然的选择。(2)联机分析处理（OLAP）技术也可以应用到模式的分析中来。(3)计划挖掘（planmining）挖掘通常的存取规律，可以调整Web连接，改善性能。65第65页，共111页，2023年，2月20日，星期一相关分析方法(4)相关／序列存取模式分析，可以对服务器的缓存、预取和交换参数进行调整。(5)趋势分析，可以了解Web下在发生的变化，用户的个性化分析可以为用户提供定制的服务。66第66页，共111页，2023年，2月20日，星期一15.4.5.３使用记录挖掘的基本流程

对Web访问日志（WebLog）进行分析和挖掘要经过一系列的数据准备工和和建模工作。一个基本的流程包括如下步骤。（1）首先要对WebLog进行清洗、过滤和转换，从中抽取感兴趣的数据。67第67页，共111页，2023年，2月20日，星期一15.4.5.３使用记录挖掘的基本流程

（2）将资源的类型、资源的大小、请求的时间、在资源上停留的时间、请求次数、来自不同Internet域的请求次数、事件、会话、错误次数作为在这些维变量下的度量变量建立数据立方体（DataCube）。（3）利用成熟的数据挖掘技术（如特征、分类、关联、预测、时间序列分析、趋势分析）68第68页，共111页，2023年，2月20日，星期一15.5挖掘数据流

为了从数据流中发现知识或模式，有必要开发单遍扫描的、联机的、多层的、多维的流处理和分析方法。单遍扫描的联机数据分析方法，不应该只限于流数据，它对于处理海量的非数据流也是至关重要的。69第69页，共111页，2023年，2月20日，星期一15.5.1流数据处理方法和流数据系统

本节，我们考虑一些常用的大纲数据结构和技术。1．随机抽样一种叫做水库抽样，可以用来无放回的选取一个无偏的S个元素的随机样本，没有更换。水库抽样的想法相对简单。2．滑动窗口基本的思想是：仅仅基于最近的数据做出决策，而不是对目前为止看到的所有数据或对某个样本进行计算。70第70页，共111页，2023年，2月20日，星期一15.5.1流数据处理方法和流数据系统

3.直方图直方图是一种大纲的数据结构，可以用来近似数据流中元素值的频率分布。4.多分辨方法处理大量数据的一种常见方式是使用数据归约

方法。一种流行的数据归约方法是采用分治策略，如多分辨率数据结构5.数据流管理系统和流查询流数据的查询处理结构包括三个部分：终端用户，查询处理器和临时空间（这可能由主存和磁盘构成）。71第71页，共111页，2023年，2月20日，星期一流OLAP和流数据立方体（续）1．压缩时间尺度的时间维：倾斜时间框架

这种模型对许多分析任务来说是足够的，也能保证驻留在内存或存储在硬盘上的数据总量很小。2.关键层

第一层称作最小兴趣层（minimalinterestinglayer），是分析人员想要研究的最小兴趣层。

第二层称观察层（observationlayer），是分析人员（或自动化系统）希望不断研究数据的层。72第72页，共111页，2023年，2月20日，星期一3.流立方体的部分物化常用路径立方体计算（popularpathcubing）,它通过一条常用下钻路径，从最小兴趣层到观察层执行上卷操作，仅仅物化该路径中的层次，其它层仅在需要的时候计算。这种方法在空间，计算时间和灵活性上取得了适度平衡，并具有快速增量聚集时间，快速下钻时间，并且空间需求很小。流OLAP和流数据立方体（续）73第73页，共111页，2023年，2月20日，星期一15.5.3数据流中的频繁模式挖掘

1.数据流频繁模式挖掘2.数据流频繁模式挖掘算法数据流频繁模式挖掘的关键问题就是如何快速对数据流中所出现的模式进行计数。74第74页，共111页，2023年，2月20日，星期一数据流所出现的模式数据流所出现的模式分成三类:

(1)当sup(X)≥s时,称X为频繁模式；

(2)当ε≤sup(X)<s时,称X为潜在频繁模式；

(3)当sup(X)<s时,称X为非频繁模式,并在算法中舍弃非频繁的模式以减少算法的空间复杂度。75第75页，共111页，2023年，2月20日，星期一15.5.4动态数据流的分类

增量式方法又称为在线式、连续式或序列式方法等

,定义为St={(x,y)|y=f(x)},t=1,2,⋯,∞。数据流挖掘的增量式方法一般都假设取得的样本是由平稳分布的数据中所获得。很多研究者提出了解决数据流上概念漂移问题的分类技术。

76第76页，共111页，2023年，2月20日，星期一15.5.4动态数据流的分类

1.数据平稳分布的分类方法

VFDT(veryfastdecisiontree)是一种基于Hoeffding不等式建立决策树的方法,它通过不断地将叶节点替换为决策节点而生成。其中每个叶节点都保存有关于属性值的统计信息,这些统计信息用于计算基于属性值的测试。

77第77页，共111页，2023年，2月20日，星期一15.5.4动态数据流的分类信息增益用于表达计算分类到达该节点的样本所需要的信息,其计算公式为属性j的熵为,其中

表示类别k已知的情况下属性值取i的概率。

VFDT的另一重要性质是它所产生的决策树在大量减少处理样本数目的同时,能够保证和使用全部样本所产生的决策树具有无限接近的精度。78第78页，共111页，2023年，2月20日，星期一15.5.4动态数据流的分类2.数据带概念漂移的分类方法下面介绍各种概念漂移学习方法。①FLORA框架

由于FLORA算法每次只能处理一个样本,所以它对数据到达的速度是有限制的。

79第79页，共111页，2023年，2月20日，星期一②CVFDT

该算法在叶节点可能会产生概念漂移时产生一棵备选子树,并且在新子树变得更精确时用新子树替代原先的子树,从而解决了概念漂移所导致的预测性能下降的问题。③离线C4.5

Harries和Sammut基于C4.5开发了一个离线学习系统,该系统将数据流分为一个关于时间的“概念聚类”集合。80第80页，共111页，2023年，2月20日，星期一15.5.5聚类演变数据流

为了对数据流进行有效的聚类，几个新的方法已制定，具体情况如下：计算和存储过去汇总的数据应用分治策略增量聚类传入的数据流进行微聚类以及宏聚类分析利用多个时间粒度为分析集群的演变把流聚类划分为联机和脱机处理81第81页，共111页，2023年，2月20日，星期一聚类演变数据流

已开发了几个算法为聚类数据流的算法。这里介绍其中两个，即STREAM和CluStream。

1.STREAM：基于k中位数的流聚类算法

STREAM是一种单遍扫描，常数因子的近似算法，是为K-中位数问题开发的。

STREAM源于k中位数聚类，使用有限的时间和空间。

82第82页，共111页，2023年，2月20日，星期一15.5.5聚类演变数据流

2.CluStream：聚类演变的数据流

CluStream是一种基于用户指定的、联机聚类查询的演变数据流聚类算法。联机微簇的处理分为两个阶段进行：（1）收集统计数据（2）更新微簇。

83第83页，共111页，2023年，2月20日，星期一15.6时间序列数据挖掘

15.6.1趋势分析“如何处理时序数据？”目前一般有四种主要的变化成分用于特征化时序数据：

1．长期或趋势变化(trendmovement)2．循环运动或循环变化(cyclicmovementorcyclicvariations)3．季节性运动或季节性变化(seasonalmovementsorseasonalvariations)4．非规则或随机变化（irregularorrandommovements）84第84页，共111页，2023年，2月20日，星期一时间序列数据挖掘“怎样确定数据的趋势?”一个确定的趋势的常用方法是用下面的算数均值序列计算n阶移动平均：85第85页，共111页，2023年，2月20日，星期一15.6.2时间序列分析中的相似性搜索

“什么是相似搜索（similaritysearch）？”通常数据库查询是要找出符合查询的精确数据，相似搜索与之不同，它是找出与给定查询序列最接近的数据序列。86第86页，共111页，2023年，2月20日，星期一15.6.2时间序列分析中的相似性搜索

数据变换(datatransformation)：从时间域(timedomain)到频率域(frequencydomain)对时序数据的相似分析，通常采用欧氏距离作为相似计算的依据。两个常见的独立于数据的变换是离散傅立叶变换（DFT）和离散小波变（DWT）。87第87页，共111页，2023年，2月20日，星期一15.6.2时间序列分析中的相似性搜索

能够处理存在间隙和偏移与振幅差异的相似搜索的执行步骤如下：

1．原子匹配（atomicmatching）

2．窗口结合(windowstitching)3．子序列排序(subsequenceordering)88第88页，共111页，2023年，2月20日，星期一15.6.2时间序列分析中的相似性搜索下图是子序列S(sequenceS)和子序列T(sequenceT)的原始序列（Originalsequence）、删除间隙（Removinggap）、偏移变换（offsettranslation）和振幅变换（Amplitudescaling）的差别。此图是在时序数据中的子序列匹配：原始序列形状相同，但需要调整以处理存在于间隙、偏移和振幅中的差异。这些调整允许子序列在一定宽度∈的范围内匹配。89第89页，共111页，2023年，2月20日，星期一90第90页，共111页，2023年，2月20日，星期一15.7挖掘事务数据库中的序列模式

15.7.1序列模式挖掘：概念和原语“什么是序列模式挖掘？”序列模式挖掘是指挖掘相对时间或其它模式出现频率高的模式。举个例子，顺序模式是“顾客在购买佳能数码相机有可能在一个月以内购买HP彩色打印机”。项集是一个非空的商品名的集合,D的第三个属性便是项集。

91第91页，共111页，2023年，2月20日，星期一15.7挖掘事务数据库中的序列模式序列是一个向量,这个向量的每一维均为项集。用(s1，s2，⋯，sn)表示向量,其中sj为项集；对于两个向量S1=<a1，a2，⋯，an>、S2=<b1，b2，⋯，bm>,若存在整数0<i1<i2<⋯<in<m+1使得,则称S1包含于S2,

记作在一个序列集中,若序列S不包含于任何其它的序列,我们称S是极大的；在D中,我们可以将某个顾客的项集按时间顺序排成一个序列,我们称这个序列为这个顾客的顾客序列；92第92页，共111页，2023年，2月20日，星期一若一个序列包含于某个顾客的顾客序列中,则称此顾客支持此序列；支持某序列的顾客数与总顾客数之比称为此序列的支持率；当一个序列的支持率不小于一个给定的值时,称这个序列为频繁序列；而这个值称为最小支持,记作min_sup；序列所拥有的项集个数称为序列的长度。一个长度为k的序列称为k序列；设<i>为1序列,I为其中唯一项集。若某客户支持<i>,则称此客户支持项集I；若<i>为频繁序列,则称I为频繁项集。93第93页，共111页，2023年，2月20日，星期一15.7.2挖掘序列模式的可伸缩方法

对于序列模式挖掘，如何开发有效的和可伸缩的方法？最近的研究在这两方面取得了进展：（1）挖掘序列模式完全集的有效方法，（2）仅挖掘序列模式闭集的有效方法第一类是基于R.Agrawal等人提出的Apriori特性的算法，主要包括AprioriAll算法、GSP算法、SPADE算法等.

94第94页，共111页，2023年，2月20日，星期一挖掘序列模式的可伸缩方法

AprioriAll算法将序列的长度定义为序列中包含的项集的数量。该算法将序列模式挖掘过程分为五个阶段。

(1)排序阶段

(2)频繁项集阶段

(3)转换阶段

(4)序列阶段

(5)最大序列阶段95第95页，共111页，2023年，2月20日，星期一15.7.2挖掘序列模式的可伸缩方法

第二类是J.Han等人提出的基于模式增长的算法，包括FreeSpan算法、PrefixSpan算法等。PrefixSpan(Prefix-projectedequentialPatternMining)算法和FreeSpan算法都是基于模式增长的挖掘方法。96第96页，共111页，2023年，2月20日，星期一15.7.3基于约束的序列模式挖掘

约束可以用多种形式表示。可能是属性，属性质之间的联系或者结果模式中的聚集。第一个约束是时间序列的持续时间（duration）T。第二个约束是事件重叠窗口（eventfoldingwindow），w。第三个约束是被发现的模式中时间之间的时间间隔（interval）int。97第97页，共111页，2023年，2月20日，星期一15.7.4时间相关序列数据的周期性分析

“什么是周期分析？”周期分析（periodicityanalysis）是指对周期模式的挖掘，即在时序数据库中找出重复出现的模式。

98第98页，共111页，2023年，2月20日，星期一

周期模式挖掘可以从不同的角度观察，基于模式覆盖，可以把模式周期分为三类：挖掘全周期模式（fullperio