数据挖掘原理与SPSS Clementine应用宝典第15章 复杂对象数据挖掘.ppt

《数据挖掘原理与SPSS Clementine应用宝典第15章 复杂对象数据挖掘.ppt》由会员分享，可在线阅读，更多相关《数据挖掘原理与SPSS Clementine应用宝典第15章 复杂对象数据挖掘.ppt（111页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据挖掘原理与数据挖掘原理与SPSSClementine应用宝典应用宝典第第15章章复杂对象数据复杂对象数据挖掘挖掘第第1515章章 复杂对象数据挖掘复杂对象数据挖掘 2Copyright 2003-12,SPSS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.15.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

2、挖掘事务数据库中的序列模式挖掘事务数据库中的序列模式15.8 15.8 挖掘生物学数据中的序列模式挖掘生物学数据中的序列模式3Copyright 2003-12,SPSS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.15.1 15.1 空间数据库挖掘空间数据库挖掘 空间数据库挖掘（SDM）实质上是空间信息技术发展的必然结果，它是数据库挖掘（DM）的一个重要分支，面对的都是空间数据库（spatial database,SDB）。空间实体之间又具有空间拓扑、空间距离、空间方位这3种关系4Copyright 2003-12,SPSS Taiwan C

3、orp.Copyright 2003-12,SPSS Taiwan Corp.15.1.1 15.1.1 空间数据概述空间数据概述空间数据是指与二维、三维或更高维空间的空间坐标及空间范围相关的数据 空间数据的复杂性特征有：空间属性之间的非线性关系空间数据的多尺度特征空间信息的模糊性空间维数的增高空间数据的缺值5Copyright 2003-12,SPSS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.15.1.1.2 15.1.1.2 空间查询工作空间查询工作 空间查询及其操作的主要特点有：空间操作相对复杂和不精确空间连接（Spatial Joi

4、n）问题相同的地理区域经常有不同的视图一个空间实体可用空间和非空间的属性来描述6Copyright 2003-12,SPSS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.很多基本空间查询是数据挖掘行为的基础，这些查询包括：区域查询或范围查询：寻找那些与在查询中指定区域相交的实体。最邻近查询：寻找与指定实体相邻的实体距离扫描：寻找与指定的实体相距一段确定距离的实体，这个距离是逐渐增大的。小提示：所有这些查询都可以用来辅助空间聚类或分类操作。15.1.1.2空间查询工作空间查询工作 7Copyright 2003-12,SPSS Taiwan Co

5、rp.Copyright 2003-12,SPSS Taiwan Corp.15.1.2 15.1.2 空间数据挖掘中的基础计算模型空间数据挖掘中的基础计算模型 空间关系计算 (1)常用的两个空间实体之间的距离有：最小值方法最小值方法：定义实体A和B的距离为A中的所有点与和B中的所有点之间的欧氏或曼哈顿距离中最小的，即 （15-1）8Copyright 2003-12,SPSS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.大值方法大值方法：定义实体A和B的距离为A中的所有点与和B中的所有点之间的欧氏或曼哈顿距离中最大的，即 （15-2）平均值方

6、法平均值方法：定义实体A和B的距离为A中的所有点与和B中的所有点之间的欧氏或曼哈顿距离的平均值，即 （15-3）空间关系计算空间关系计算9Copyright 2003-12,SPSS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.中心方法中心方法：定义实体A和B的距离为A中的中心点与和B中的中心点之间的欧氏或曼哈顿距离的平均值，即 (15-4)其中最简单的方法就是取实体A的中心点和B的中心点，该中心点可以通过查找实体的几何中心来识别。空间关系计算空间关系计算10Copyright 2003-12,SPSS Taiwan Corp.Copyrigh

7、t 2003-12,SPSS Taiwan Corp.15.1.2 15.1.2 空间数据挖掘中的基础计算模型空间数据挖掘中的基础计算模型（2）两个空间实体之间存在若干拓扑关系。这些关系基于两个实体的位置：分离（Disjoint）：A与B分离，表示B中任何点都不在A中，反之亦然。重叠/相交：A与B重叠或相交表示至少有一个点既在A里也在B里。等价：A与B这两个实体的所有点都是共有的。11Copyright 2003-12,SPSS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.l包含于：A包含于B，表示A的所有点都在B里，反之不一定。l覆盖/包含：

8、A覆盖或包含B，当且仅当B包含于A。(3)方位是描述两个点状实体位置关系的一种度量，如果要分析面状实体间的方位关系，则应把多边形转换为重心点或其它点状实体。15.1.2 15.1.2 空间数据挖掘中的基础计算模型空间数据挖掘中的基础计算模型12Copyright 2003-12,SPSS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.15.1.2.215.1.2.2空间实体信息模型空间实体信息模型 空间场模型空间场模型空间场模型主要用于模拟在空间上连续分布的地理现象，属性取值既可以式连续的，也可以是离散的。空间场数据模型的优点是数据结构简单，便于

9、空间法分析与模拟。缺点是不利于表达空间实体，数据量也大。13Copyright 2003-12,SPSS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.15.1.215.1.2空间数据挖掘中的基础计算模型空间数据挖掘中的基础计算模型 空间要素模型图15-3 基于要素的空间信息模型对现实世界的抽象基于要素的空间信息模型对现实世界的抽象现实世界现实世界专题要素专题要素1实体实体1专题要素专题要素2专题要素专题要素n实体实体2实体实体n时间特征时间特征属性特征属性特征空间关空间关 系特征系特征几何特征几何特征14Copyright 2003-12,SP

10、SS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.15.1.2 15.1.2 空间数据挖掘中的基础计算模型空间数据挖掘中的基础计算模型小提示：实体必须符合三个条件：可被识别，重要（与问题相关），可被描述（有特征）。表15-2 现实世界与信息世界的对应关系 15Copyright 2003-12,SPSS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.15.1.215.1.2空间数据挖掘中的基础计算模型空间数据挖掘中的基础计算模型空间网络模型空间网络模型空间网络结构模型中地理现象被抽象为链、结点以及

11、它们之间的连通关系（图15-4 对空间网络的抽象）。图的形式化定义为 （15-10）图15-4 对空间网络的抽象ACDB16Copyright 2003-12,SPSS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.15.1.215.1.2空间数据挖掘中的基础计算模型空间数据挖掘中的基础计算模型位置位置属性一体化的空间实体信息模型属性一体化的空间实体信息模型 一般空间实体的形式化模型为一个四元组，分别代表空间实体四个方面的特征。其中位置特征数据为 （15-11）17Copyright 2003-12,SPSS Taiwan Corp.Copyri

12、ght 2003-12,SPSS Taiwan Corp.15.1.3 15.1.3 空间数据挖掘基础空间数据挖掘基础 空间数据挖掘（SDM）是指对空间数据库中非明确存在的知识，空间关系，或其它有意义的模式等的提取。15.1.3.1 15.1.3.1 空间数据挖掘的框架体系空间数据挖掘的框架体系 一般认为可以大致分为三 层结构，如图15-5空间数据挖掘的体系结构所示。其中，第一层是数据源；第二层是挖掘器；第三层是用户界面。18Copyright 2003-12,SPSS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.图15-5 空间数据挖掘的体系

13、结构19Copyright 2003-12,SPSS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.15.1.3.2 15.1.3.2 空间数据挖掘的方法体系空间数据挖掘的方法体系空间评价。空间分类与聚类。空间分布计算。空间优化。空间回归分析。空间动态模拟与预测。空间与时序关联知识归纳。20Copyright 2003-12,SPSS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.15.1.415.1.4几种空间数据挖掘算法几种空间数据挖掘算法15.1.4.1 空间关联分析 空间关联规则挖掘是传统关

14、联规则挖掘的延伸，常用最小支持度和最小可信度来作为基本的统计参数，由于空间数据的特点，往往是在多层概念上进行归纳。21Copyright 2003-12,SPSS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.挖掘空间关联规则的有效方法是自上而下、逐步加深的搜索技术。首先在高的概念层次进行搜索，在较粗的精度级别查找频繁发生的模式和在这些模式中较强的隐含关系；然后，对频繁发生的模式加深搜索至较低的概念层次，这种处理持续到找不到频繁发生的模式为止。空间关联分析空间关联分析22Copyright 2003-12,SPSS Taiwan Corp.Cop

15、yright 2003-12,SPSS Taiwan Corp.15.1.4.115.1.4.1空间关联分析空间关联分析典型的五步算法：典型的五步算法：Step1：通过给定的查询抽取出相关的数据。Step2：应用一个粗的空间运算方法，计算整个相关数据的集合。Step3：过滤出那些支持度小于最小支持度阈值的1阶谓词。Step4：应用一个细化的空间计算方法，从所导出的粗的谓词集合中计算谓词。Step5：向低层深入，在多个概念层次上找到关联规则的完整集合。23Copyright 2003-12,SPSS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.1

16、5.1.4.215.1.4.2空间分类算法和空间趋势分析空间分类算法和空间趋势分析空间分类指分析空间对象导出与一定空间特征有关的分类模式 小小提提示示：空间因素可以是非空间属性和空间属性，也可以是二者同时使用。(1)对于样本数据的训练可以通过改造传统的分类算法来完成 (2)空间决策树 空间分类技术建构决策树采用两步方法。这个方法的思想基础是空间实体可以与其接近的实体来描述。假设类的描述是基于与实体相近最相关的谓词的集合。建造一个决策树24Copyright 2003-12,SPSS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.空间决策树有五个主

17、要步骤：根据已知的分类，从数据D中找到例子S。确定最佳谓词p用来分类。一般首先在较粗的层次中寻找相关谓词，然后再在较为细化的层次。空间决策树空间决策树25Copyright 2003-12,SPSS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.找到最佳的缓冲区大小和形状。对于取样中的每个实体，它周围的区域被称为缓冲区。目标是选择一个能产生对测试集中的类型进行最不同的缓冲区。使用p和C，对每个缓冲区归纳谓词。使用泛化的谓词和ID3建造二叉树T。26Copyright 2003-12,SPSS Taiwan Corp.Copyright 2003-

18、12,SPSS Taiwan Corp.15.1.4.3 15.1.4.3 空间聚类方法空间聚类方法 空间聚类分析是空间模式识别和空间数据挖掘的重要手段之一。它的目的是要在一个较大的多维数据集中根据距离的计算找出簇，或稠密区域。小提示：空间聚类找到的聚类不应该依赖于检验空间中的点的顺序，而且聚类也不应该受不相干的点影响。本节介绍的空间聚类方法是基于坐标属性一体化的空间信息模型，27Copyright 2003-12,SPSS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.15.1.4.3 15.1.4.3 空间聚类方法空间聚类方法从两类直至每个样

19、本为一类的系统聚类算法步骤如下：对地理特征向量中的每一个元素进行无量纲化。令类别数k=2，置迭代误差阈值emin=0.100001(可根据需要设置)。置迭代次数t=0，k 个初始聚类中心为：对第t 次迭代,若有 则把样本Si 分配到第j0 个聚类域 。如此，所有的m 个样本可以被划分到k 个聚类域 中.28Copyright 2003-12,SPSS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.计算新的聚类中心 式中Nj 为第j个聚类域中包含的样本个数。若 则停止迭代，第t 次迭代结果为划分为k 个类别的聚类方案，转向(7)；否则,t=t+1，

20、转向(4)。当k m 时，k=k+1，转向(3)；否则，系统聚类结束。聚类算法步骤聚类算法步骤(续）续）29Copyright 2003-12,SPSS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.15.2 15.2 多媒体数据挖掘多媒体数据挖掘15.2.1 多媒体数据挖掘的特点多媒体数据复杂。多媒体信息语义关联性强。多媒体信息具有时空相关性。知识的表达和解释比较困难，多媒体挖掘所得出的模式往往比较隐晦。30Copyright 2003-12,SPSS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp

21、.15.2.2 15.2.2 多媒体数据挖掘概述多媒体数据挖掘概述多媒体数据挖掘典型系统结构 多媒体数据挖掘系统是在基于内容的多媒体数据检索系统发展的基础上出现的。它的一般结构图如图15-8所示。图图15-8多媒体数据挖掘系统结构多媒体数据挖掘系统结构挖掘任务媒体数据库多媒体数据集知识库挖掘引擎数据立方体媒体属性特征数据预处理用户挖掘接口31Copyright 2003-12,SPSS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.15.2.2.2 15.2.2.2 多媒体数据挖掘的内容多媒体数据挖掘的内容 关于多媒体数据挖掘的内容一般包括图像数

22、据挖掘、音频数据挖掘、关于多媒体数据挖掘的内容一般包括图像数据挖掘、音频数据挖掘、视频数据挖掘等。视频数据挖掘等。图像挖掘图像挖掘 图像包含着丰富的视觉特性和空间特性。视频挖掘视频挖掘 视频包括丰富的内容特性，除了图像具有的视觉特性和空间特性外,还具有时间特性、视频对象特性和运动特性等。32Copyright 2003-12,SPSS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.多媒体数据挖掘的内容多媒体数据挖掘的内容音频挖掘音频挖掘 音频挖掘通常有两种途径:运用语音识别技术将语音识别成文字，将音频挖掘转换成文本挖掘；直接从音频中提取声音特征，

23、如音调、韵律等,运用聚类的方法分析声音模式。Web Web 挖掘挖掘多媒体综合挖掘多媒体综合挖掘 多媒体概念与单媒体的区别在于，它是一个集成的系统概念，媒体之间有联系。33Copyright 2003-12,SPSS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.15.2.3 15.2.3 多媒体数据挖掘方法多媒体数据挖掘方法在图像和视频数据库中可以挖掘涉及多媒体对象的关联规则，至少包含以下三类：图像内容和非图像内容特征间的关联与空间关系无关的图像内容的关联与空间关系有关的图像内容的关联34Copyright 2003-12,SPSS Taiwa

24、n Corp.Copyright 2003-12,SPSS Taiwan Corp.15.2.3.2 15.2.3.2 多媒体数据的相似搜索多媒体数据的相似搜索对多媒体数据相似性搜索，主要考虑两种多媒体标引和检索系统：（1）基于描述的检索系统，主要是在图像描述之上建立标引和执行对象检索，如关键字、标题、尺寸、创建时间等；（2）基于内容的检索系统，它支持基于图像内容的检索，如颜色构成、质地、形状、对象和小波变换等。35Copyright 2003-12,SPSS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.两种查询两种查询在基于内容的检索系统中,

25、通常有两种查询：基于图像样本的查询（image sample-based queries）。图像样本查询是指找出所有与给定图像样本相似的图像。图像特征描述查询(image feature specification queries)。图像特征描述查询是指给出图像的特征描述或概括36Copyright 2003-12,SPSS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.15.2.3.2 15.2.3.2 多媒体数据的相似搜索多媒体数据的相似搜索 到目前为止人们已经提出了几种在图像数据库中基于图像特征标识的相似检索方法：基于颜色直方图的特征标识多

26、特征构成的特征标识基于小波的特征标识带有区域粒度的小波特征标识37Copyright 2003-12,SPSS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.15.2.3.3 15.2.3.3 多媒体数据的分类和预测分析多媒体数据的分类和预测分析 我们也可以对多媒体数据进行分类和预测分析，尤其用在如天文学、地震学、地理科学等的研究中。分类是多媒体数据的一种分析形式,它根据媒体某一特征(或一组特征)将数据分成不同的类。它是一个两步过程：第1步，建立一个模型，用来描述预定义类集。第2步，使用模型进行分类。38Copyright 2003-12,SPS

27、S Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.15.3 15.3 文本挖掘文本挖掘15.3.1文本挖掘概述 数据库挖掘处理的对象是结构化的数据，目的是从结构化数据源中发现不同属性之间的关联规则，或者是对数据对象进行聚类及分类处理，或者是构造数据的预测模型。39Copyright 2003-12,SPSS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.文本挖掘的一般过程文本挖掘的一般过程文本挖掘的一般过程文本挖掘过程一般包括文本准备、特征标引、特征集缩减、知识模式的提取、知识模式的评价、知识模式的

28、输出等过程.文本特征标引特征集缩减知识模型的提取知识模型的评价知识模型的输出40Copyright 2003-12,SPSS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.15.3.1.2 15.3.1.2 文本挖掘的主要任务文本挖掘的主要任务文本挖掘的主要目标是获得文本的主要内容特征文本挖掘的主要目标是获得文本的主要内容特征 特征提取 主题标引 文本分类 文本聚类 自动摘要41Copyright 2003-12,SPSS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.15.3.1.3 15.3.1

29、.3 文本挖掘与信息检索文本挖掘与信息检索文本的预处理 目前，人们在对文本集进行自动分类、自动聚类、自动摘要或更深层次的挖掘处理时常常采用这样的策略:先用一个高度概括的向量来表示一篇文本，将文本集概括成一个向量集，这个向量集等同于一个二维表格，然后通过对文本集对应的向量集进行相关的分析，达到对文本集进行自动分类、自动聚类、自动产生文摘或自动挖掘出更深层的隐含知识的目的。42Copyright 2003-12,SPSS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.文本的表示文本的表示 文本表示是指用文本的特征信息集合来代表原来的文本.向量空间模型

30、的基本思想是以向量来表示文本，其中为第i个特征项的权重。相对词频的计算方法主要运用TF-IDF公式。公式如下：（15-15）43Copyright 2003-12,SPSS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.15.3.2.2 15.3.2.2 文本特征标引文本特征标引所谓标引，是指给出信息内容特征的过程。汉语自动分词方法有多种，主要有词典法、切分标记法等。1词典分词法 2.切分标记分词法 小提示：切分标记法的典型代表是非用词后缀表法。该法将汉字分为“非用字”、“条件用字”、“表内用字”、“表外用字”。主要利用“非用字”和“条件用字”进

31、行词语的切分。44Copyright 2003-12,SPSS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.15.3.2.3 15.3.2.3 文本维度规约文本维度规约1 1基于评估函数的方法基于评估函数的方法 基于评估函数的特征集缩减算法使用特征独立性假设以简化特征选择。2 2潜在语义标引潜在语义标引潜在语义标引法利用矩阵理论中的“奇异值分解”技术，将词频矩阵转化为维数大大减小的奇异矩阵。45Copyright 2003-12,SPSS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.15.3.3

32、.1 15.3.3.1 文本的自动分类文本的自动分类文本自动分类的一般过程如下：首先，取一个预分类的文本集作为训练集。然后，分析训练集以导出分类模型。通常，需要用一个检验过程对该分类模型求精。所导出的分类模型可以用于其它联机文本分类。46Copyright 2003-12,SPSS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.文本分类的典型的分类方法文本分类的典型的分类方法 下面介绍几种已经成功应用于文本分类的典型的分类方法。1简单向量距离分类 具体步骤如下:(1).根据训练集文本向量空间模型计算每类文本集的中心向量；(2).将新文本表示为特征

33、向量；(3).计算新文本特征向量和每类中心向量间的相似度；(4).比较每类中心向量与新文本的相似度，将文本分到相似度最大的那个类别中。47Copyright 2003-12,SPSS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.文本分类的典型的分类方法（续）文本分类的典型的分类方法（续）2简单贝叶斯分类算法算法具体步骤如下：计算特征词属于每个类别的概率向量 。对于新文本di，计算该文本属于类Cj 的概率。比较新文本属于所有类的概率，将文本分到概率最大的那个类别中。48Copyright 2003-12,SPSS Taiwan Corp.Copy

34、right 2003-12,SPSS Taiwan Corp.文本分类的典型的分类方法（续）文本分类的典型的分类方法（续）3 3K K最近邻居（最近邻居（KNNKNN）算法）算法 该算法的基本思路是:在给定新文本后，考虑在训练文本集中与该新文本距离最近(最相似)的K篇文本，根据这几篇文本所属的类别判定新文本所属的类别，该算法具体的步骤如下:49Copyright 2003-12,SPSS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.K K最近邻居（最近邻居（KNNKNN）算法）算法(1).根据特征项集合重新描述训练文本向量；(2).将新文本表示

35、为特征向量；(3).比较类的权重，将文本分到权重最大的那个类别中 (4).在训练文本集中选出与新文本最相似的K个文本，计算公式为：.(15-16)50Copyright 2003-12,SPSS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.(5).在新文本的K个邻居中，依次计算每类的权重，计算公式：.(15-17)其中，为新文本的特征向量，为相似度计算公式，为类别属性函数，即如果 属于类 ，那么函数值为1，否则为0。K K最近邻居（最近邻居（KNNKNN）算法）算法51Copyright 2003-12,SPSS Taiwan Corp.Cop

36、yright 2003-12,SPSS Taiwan Corp.15.3.3.2 15.3.3.2 文本聚类文本聚类1 1光谱聚类方法光谱聚类方法 首先，对原始数据进行光谱嵌入（维度归约），然后对维度归约后的文本空间运用传统的聚类算法（如k均值）。52Copyright 2003-12,SPSS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.文本聚类文本聚类(续续)2 2混合模型聚类方法混合模型聚类方法 用混合模型对文本数据聚类包括两个步骤：(1)基于文本数据和附加的先验知识估计模型参数；(2)基于估计的模型参数推断聚类。53Copyright

37、2003-12,SPSS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.15.3.3.3 15.3.3.3 基于遗传算法（基于遗传算法（GAGA）的文本聚类）的文本聚类 遗传算法(GA)为文本聚类提供了一种非层次的聚类方法，其核心思想是使簇内文本间的相似度最大化。其核心思想是使簇内文本间的相似度最大化。54Copyright 2003-12,SPSS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.15.4 15.4 挖掘互联网挖掘互联网 15.4.1 15.4.1 挖掘挖掘WebWeb页面布局结构页

38、面布局结构 Web结构挖掘属于信息结构（IA）方面的研究内容。对对于一个站点而言，按结构层次高低可以分出三种结构：站于一个站点而言，按结构层次高低可以分出三种结构：站点结构、页面（框架）结构、页内结构。点结构、页面（框架）结构、页内结构。55Copyright 2003-12,SPSS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.15.4.2 15.4.2 挖掘挖掘WebWeb链接结构识别权威链接结构识别权威WebWeb页面页面 15.4.2.1 Page-rank15.4.2.1 Page-rank方法方法 大量的Web链接信息提供了丰富的关

39、于Web内容相关性、质量和结构方面的信息，这对Web挖掘是可以利用的一个重要资源。56Copyright 2003-12,SPSS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.15.4.2 15.4.2 挖掘挖掘WebWeb链接结构识别权威链接结构识别权威WebWeb页面页面基于以上考虑，人们提出了如下的概念：基于以上考虑，人们提出了如下的概念：Web可以用一个有向图来表示，G=（V，E），V是页面的集合，E是页面之间的超链接集合。页面抽象为图中的顶点，而页面之间的超链接抽象为图中的有向边。顶点V的入边表示对V的引用，出边表示V引用了其他的页面

40、。所以Web页面之间的超链接揭示了Web结构。57Copyright 2003-12,SPSS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.15.4.2 15.4.2 挖掘挖掘WebWeb链接结构识别权威链接结构识别权威WebWeb页面页面 链接文本（Anchor Texts）可以用来对被引用的页面进行索引（例如：Webor,WWW，Google）。超链接可以用来计算页面的rankings core,通过超链接可以将一个页面的ranking core传递到相邻的页面。58Copyright 2003-12,SPSS Taiwan Corp.Co

41、pyright 2003-12,SPSS Taiwan Corp.15.4.2 15.4.2 挖掘挖掘WebWeb链接结构识别权威链接结构识别权威WebWeb页面页面 Page-rank的基本思想如下：页面被多次引用，则这个页面很可能是重要的。一个页面尽管没有被多次引用，但被一个重要页面引用，则这个页面很可能是重要的。一个页面的重要性被均分并被传递到它所引用的页面。59Copyright 2003-12,SPSS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.15.4.2 15.4.2 挖掘挖掘WebWeb链接结构识别权威链接结构识别权威WebW

42、eb页面页面 Hub/authority方法 挖掘Web上的多媒体数据 关于多媒体的数据挖掘一般包括图像数据挖掘、音频数据挖掘、视频数据挖掘等。60Copyright 2003-12,SPSS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.挖掘挖掘WebWeb链接结构识别权威链接结构识别权威WebWeb页面页面15.4.3.1图像挖掘 图像挖掘（Image Mining）指对图形图像数据信息的自动处理和知识发现，包含模式识别、图像检索以及特征分析等。图像的空间特性是非常重要的特性，包括图像中各种对像的模式、布局、空间层次等。61Copyright

43、 2003-12,SPSS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.15.4.3.2 15.4.3.2 音频挖掘音频挖掘音频挖掘（Audio Mining）指对音频信息的自动处理和分析过程。语音挖掘的另外一个用途在于将语音对应到个人62Copyright 2003-12,SPSS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.15.4.3.2 15.4.3.2 音频挖掘音频挖掘15.4.3.3 15.4.3.3 视频挖掘视频挖掘15.4.4 Web15.4.4 Web文档的自动分类文档的自动分

44、类 15.4.5 Web15.4.5 Web使用挖掘使用挖掘63Copyright 2003-12,SPSS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.15.4.3.2 15.4.3.2 音频挖掘音频挖掘15.4.5.115.4.5.1模式发现模式发现 要解决的问题就是数据的预处理，它主要包括两个部分：（1）数据清洗（Data Cleaning）:包括无关记录的剔除、判断是否有重要的访问没有被记录、用户的识别等问题。（2）事务识别（Transaction Identification）:是指将页面访问序列划分为代表Web事务或用户会话的逻辑单

45、元。如路径分析、关联规则挖掘、时序模式以及聚类和分类技术。64Copyright 2003-12,SPSS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.15.4.5.15.4.5.模式的分析模式的分析相关分析方法如下相关分析方法如下：(1)可视化技术对于理解Web用户的行为模式来讲是一个自然的选择。(2)联机分析处理（OLAP）技术也可以应用到模式的分析中来。(3)计划挖掘（plan mining）挖掘通常的存取规律，可以调整Web连接，改善性能。65Copyright 2003-12,SPSS Taiwan Corp.Copyright 20

46、03-12,SPSS Taiwan Corp.相关分析方法相关分析方法(4)相关序列存取模式分析，可以对服务器的缓存、预取和交换参数进行调整。(5)趋势分析，可以了解Web下在发生的变化，用户的个性化分析可以为用户提供定制的服务。66Copyright 2003-12,SPSS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.15.4.5.15.4.5.使用记录挖掘的基本流程使用记录挖掘的基本流程 对Web访问日志（Web Log）进行分析和挖掘要经过一系列的数据准备工和和建模工作。一个基本的流程包括如下步骤。（1）首先要对Web Log进行清洗、

47、过滤和转换，从中抽取感兴趣的数据。67Copyright 2003-12,SPSS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.15.4.5.15.4.5.使用记录挖掘的基本流程使用记录挖掘的基本流程（2）将资源的类型、资源的大小、请求的时间、在资源上停留的时间、请求次数、来自不同Internet域的请求次数、事件、会话、错误次数作为在这些维变量下的度量变量建立数据立方体（Data Cube）。（3）利用成熟的数据挖掘技术（如特征、分类、关联、预测、时间序列分析、趋势分析）68Copyright 2003-12,SPSS Taiwan Corp

48、.Copyright 2003-12,SPSS Taiwan Corp.15.5 15.5 挖掘数据流挖掘数据流 为了从数据流中发现知识或模式，有必要开发单遍扫描的、联机的、多层的、多维的流处理和分析方法。单遍扫描的联机数据分析方法，不应该只限于流数据，它对于处理海量的非数据流也是至关重要的。69Copyright 2003-12,SPSS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.15.5.1 15.5.1 流数据处理方法和流数据系统流数据处理方法和流数据系统 本节，我们考虑一些常用的大纲数据结构和技术。1 1随机抽样随机抽样 一种叫做水库

49、抽样，可以用来无放回的选取一个无偏的S个元素的随机样本，没有更换。水库抽样的想法相对简单。2 2滑动窗口滑动窗口 基本的思想是：仅仅基于最近的数据做出决策，而不是对目前为止看到的所有数据或对某个样本进行计算。70Copyright 2003-12,SPSS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.15.5.1 15.5.1 流数据处理方法和流数据系统流数据处理方法和流数据系统 3.3.直方图直方图 直方图是一种大纲的数据结构，可以用来近似数据流中元素值的频率分布。4.4.多分辨方法多分辨方法 处理大量数据的一种常见方式是使用数据归约方法。一

50、种流行的数据归约方法是采用分治策略，如多分辨率数据结构5.5.数据流管理系统和流查询数据流管理系统和流查询 流数据的查询处理结构包括三个部分：终端用户，查询处理器和临时空间（这可能由主存和磁盘构成）。71Copyright 2003-12,SPSS Taiwan Corp.Copyright 2003-12,SPSS Taiwan Corp.流流OLAPOLAP和流数据立方体（续）和流数据立方体（续）1 1压缩时间尺度的时间维：倾斜时间框架压缩时间尺度的时间维：倾斜时间框架 这种模型对许多分析任务来说是足够的，也能保证驻留在内存或存储在硬盘上的数据总量很小。2.2.关键层关键层 第一层称作最小