11复杂数据类型的挖掘课件

Chapter10：

复杂数据类型的挖掘广东商学院信息学院胡建军数据仓库与数据挖掘1Chapter10：

复杂数据类型的挖掘广东商学院信息学院1CourseOutline复杂数据对象的多维分析和描述性挖掘空间数据库挖掘多媒体数据库挖掘时序数据和序列数据的挖掘文本数据库挖掘Web挖掘2CourseOutline复杂数据对象的多维分析和描述性挖2CourseOutline复杂数据对象的多维分析和描述性挖掘空间数据库挖掘多媒体数据库挖掘时序数据和序列数据的挖掘文本数据库挖掘Web挖掘3CourseOutline复杂数据对象的多维分析和描述性挖3数据挖掘的对象简单数据关系数据库、事务数据库、数据仓库复杂类型数据复杂对象、空间数据、多媒体数据、时间序列数据、文本数据、Web数据等

挖掘技术：基本挖掘技术的扩展 针对复杂数据类型的新技术 实施知识挖掘的方法4数据挖掘的对象简单数据44复杂数据对象的多维分析 和描述性挖掘商品化数据仓库和OLAP工具用于多维分析的局限： 维———非数字数据 度量———聚集值复杂数据对象的概化及其概化数据的应用复杂数据的组织及存储方法类、类/子类对象：对象标识、属性、方法5复杂数据对象的多维分析 和描述性挖掘商品化数据仓库和OLA5复杂结构数据的概化复杂结构数据：集合、元组、列表、树、记录等及其组合；概化方法：保持原结构不变，概化其属性把原结构扁平化，概化扁平化的结构用高层概念或聚集汇总低沉结构返回原结构的类型或概貌6复杂结构数据的概化复杂结构数据：66集合值集合值一般概化方法：将集合中的每个值概化为其对应的更高级别的概念导出集合的一般特征（元素个数、区间、平均值、最大值等）示例：业余爱好{网球，曲棍球，国际象棋，小提琴，任天堂游戏

}概化：{体育，音乐，电子游戏}{体育（3），音乐（1），电子游戏（1）}7集合值集合值77列表值/序列值列表值/序列值类似于集合值属性的概化，要求保持元素的次序。一般概化方法：将列表中的每个值概化为对应的高层概念导出列表的一般特征（长度、元素类型、平均值、最大值等）8列表值/序列值列表值/序列值88空间和多媒体数据的概化聚集和近似计算空间数据 例：土地规划多媒体数据图像：尺寸、颜色、形状、纹理、方位等音乐：音调、节拍、乐器等文本：摘要、关键词等9空间和多媒体数据的概化聚集和近似计算99对象的概化对象标识符 沿类/子类层次结构概化继承特性 数据概化对直接数据与继承数据同等对待方法方法本身不能概化，但是可以对方法导出的数据进行概化10对象的概化对象标识符1010CourseOutline复杂数据对象的多维分析和描述性挖掘空间数据库挖掘多媒体数据库挖掘时序数据和序列数据的挖掘文本数据库挖掘Web挖掘11CourseOutline复杂数据对象的多维分析和描述性挖11空间数据库挖掘空间数据库及其一般特点存储了大量与空间有关的数据包含拓扑/距离信息复杂的、多维的索引结构访问通过空间数据的方法，通常需要空间推理、地理计算、空间知识表示技术空间数据挖掘：要综合数据挖掘与空间数据库技术12空间数据库挖掘空间数据库及其一般特点1212空间数据库挖掘传统空间数据分析（统计方法）的不足统计方法通常假设空间分布的数据间是统计上独立的，但现实是空间对象间是相互关联的；大部分统计模型只有具有相当丰富领域知识和统计方面经验的统计专家才用得起来；统计方法不适用符号值，或不完整或非确定的数据，对大规模数据库其计算代价也十分昂贵。空间数据挖掘将对传统的空间分析方法加以扩展，重点解决其高效性，可伸缩性，与数据库系统的紧密结合，改进与用户的交互，以及新的知识的发现。

13空间数据库挖掘传统空间数据分析（统计方法）的不足1313空间关联分析

空间关联规则形如:AB[s%，c%]其中A和B空间和非空间谓词的集合，s%表示规则的支持度，c%表示规则的的可信度。例：Is_a(X,”school”)∧close_to(X,“sports_center”)⇒close_to（X,“park”）[0.5%,80%]此规则表明80%靠近体育中心的学校同时也靠近公园，并且有0。5%的数据符合这一规则。

14空间关联分析空间关联规则形如:AB14空间聚类方法

空间数据聚类是要在一个较大的多维数据集中根据距离的计算找出簇，或稠密区域。

15空间聚类方法空间数据聚类是要在一个较大的多维15空间分类和空间趋势分析空间分类指分析空间对象导出与一定空间特征有关的分类模式，如郊区，高速公路，河流的邻接。空间趋势分析处理的是另一类问题：根据某空间维找出变化趋势。

例如，当离城市中心越来越远时，我们要分析经济形势的变化趋势，或离海洋越来越远时，气候与植物的变化趋势。

16空间分类和空间趋势分析空间分类指分析空间对象导出与一定空间特16CourseOutline复杂数据对象的多维分析和描述性挖掘空间数据库挖掘多媒体数据库挖掘时序数据和序列数据的挖掘文本数据库挖掘Web挖掘17CourseOutline复杂数据对象的多维分析和描述性挖17多媒体数据库挖掘多媒体数据库是指存储和管理大量多媒体对象的数据库，如音频数据，图象数据，视频数据，序列数据，以及超文本数据，包含文本，文本标记(textmarkup)，和链接(linkage)。多媒体数据的相似搜索

主要考虑两种多媒体标引和检索系统：（1）基于描述的检索系统，主要是在图象描述之上建立标引和执行对象检索，如关键字，标题，尺寸，创建时间等；（2）基于内容的检索系统，它支持基于图象内容的检索，如颜色构成，质地，形状，对象，和小波变换等。多媒体数据的分类和预测分析

多媒体数据中的关联规则挖掘

18多媒体数据库挖掘多媒体数据库是指存储和管理大量多媒体对象的数18CourseOutline复杂数据对象的多维分析和描述性挖掘空间数据库挖掘多媒体数据库挖掘时序数据和序列数据的挖掘文本数据库挖掘Web挖掘19CourseOutline复杂数据对象的多维分析和描述性挖19时序数据库和序列数据库时序数据库：由随时间变化的序列或事件组成的数据库等时间间隔测得的数据(regularintervals)时序数据库是一种序列数据库序列数据库：由有序事件序列组成的数据库可有时间标记，也可以没有时间标记可以是时序数据库，也可以不是。如WEB遍历。20时序数据库和序列数据库时序数据库：由随时间变化的序列或事件组20时序数据例子Time-seriesplot21时序数据例子Time-seriesplot2121时序数据和序列数据的挖掘（一）趋势分析

通过对趋势，循环，季节和非规则成分的运动的系统分析，使人们可以在较合理的情况下，制定出长期或短期的预测（即预报时序）

相似搜索

找出与给定查询序列最接近的数据序列。子序列匹配（subsequencematching）是找出与给定序列相似的所有数据序列，整体序列匹配（wholesequencematching）是找出彼此间相似的序列。

例 如：对金融市场的分析（如股票数据分析），医疗诊断（如心电图分析），和科学与工程数据库（如能量消耗分析）等

22时序数据和序列数据的挖掘（一）趋势分析2222时序数据和序列数据的挖掘（一）序列模式挖掘（sequencepatternmining）是指挖掘相对时间或其它模式出现频率高的模式。

周期分析（periodicityanalysis）

对周期模式的挖掘，即在时序数据库中找出重复出现的模式。

例如:

季节，潮汐，行星轨道，每日能源消耗，每日交通模式

23时序数据和序列数据的挖掘（一）序列模式挖掘（sequence23CourseOutline复杂数据对象的多维分析和描述性挖掘空间数据库挖掘多媒体数据库挖掘时序数据和序列数据的挖掘文本数据库挖掘Web挖掘24CourseOutline复杂数据对象的多维分析和描述性挖24文本数据库和信息检索（IR）文本数据库半结构化数据：它既不是完全无结构的也不是完全结构的。例如，一个文档可能包含结构字段，如标题，作者，出版日期，长度，分类，等等，也可能包含大量的非结果化的文本成分，如摘要和内容。典型的信息检索问题是基于用户的输入（如关键字或样例文档）定位相关的文档。典型的信息检索系统联机图书馆目录联机文档管理系统信息检索与数据库系统DB：并发控制、恢复、事务管理、更新IR：非结构化文档、基于关键字的近似搜索25文本数据库和信息检索（IR）文本数据库2525文本检索的基本度量查准率:反映正确性查全率:反映全面性RelevantRelevant&RetrievedRetrievedAllDocuments应该被检索到的26文本检索的基本度量查准率:反映正确性RelevantRele26文本检索的基本度量查准率:反映正确性查全率:反映全面性RelevantRelevant&RetrievedRetrievedAllDocuments实际被检索到的27文本检索的基本度量查准率:反映正确性RelevantRele27文本检索的基本度量查准率:反映正确性查全率:反映全面性RelevantRelevant&RetrievedRetrievedAllDocuments28文本检索的基本度量查准率:反映正确性RelevantRele28基于关键字的检索在关键字检索中，文档被看作字符串，可用一组关键字识别查询由关键字表达式构成例子,汽车and

修理店查询应考虑同义词问题,如：修理和维修困难同义词问题（Synonymy）:文档与Key相关，但Key在文档中不出现多义词问题（Polysemy）:同一Key在不同的上下文有不同的含义，如Mine。29基于关键字的检索在关键字检索中，文档被看作字符串，可用一组关29基于相似性的检索（1）相似检索是指基于一组共同的关键字找出相似的文档检索结果基于相关度，即：与关键词的近似性，关键词的出现频率等。非用词表（Stoplist）无关的高频词，如：a,the,of,for,etc.文档不同时，非用词表也不同30基于相似性的检索（1）相似检索是指基于一组共同的关键字找出相30基于相似性的检索（2）

由于相似文档具有相似的相对词频，因此我们可以基于频率表中的相对词频，计算一组文档的相似性。

词频矩阵相似度:基于一组关键词的文档相似性相关词的出现次数余弦距离：缺点：当词数T和文档数目D很大时，高的维数导致低的计算效率，且出现大的稀疏向量。用奇异值分解(SVD)技术减小词频矩阵大小保留词频矩阵中最有意义的K行和K列，K值为几百。词/文档d1d2d3d4d5d6d7t13218431687215430t2354917156826392t32232167462892251731基于相似性的检索（2）由于相似文档具有相似的相对词频，因此31文本数据挖掘的类型1.基于关键字的关联分析2.文档分类分析32文本数据挖掘的类型1.基于关键字的关联分析3232基于关键字的关联分析动机收集经常一起出现的关键字或词汇，然后找出其关联或相互关系关联分析过程文档预处理：文本数据分解，词根处理，过滤非用词等调用关联挖掘算法将每一文档看作一个事务将文档中的关键词组看作事务中的一组事务项33基于关键字的关联分析动机3333文档分类动机自动对大量联机文档（web页面，e－mail等）进行分类组织，以便于对文档进行检索和分析。分类过程数据预处理：提出关键字和词汇定义训练集和测试集调用分类算法创建分类模式测试分类模式应用导出的分类模式对其他新的、未知的联机文档分类文档分类与关系数据库中的数据分类之间的区别文档数据库是非结构化的，没有“属性－值”对34文档分类动机3434CourseOutline复杂数据对象的多维分析和描述性挖掘空间数据库挖掘多媒体数据库挖掘时序数据和序列数据的挖掘文本数据库挖掘Web挖掘35CourseOutline复杂数据对象的多维分析和描述性挖35Web挖掘挑战对数据仓库和数据挖掘而言，Web太庞大了Web页面数据太复杂：没有结构，不标准不断增长，不断变化广泛的用户群体仅有很小部分的Web数据是有用的或相关的99%的Web信息对99%的Web用户是无用的36Web挖掘挑战3636Web搜索引擎基于索引:搜索Web页面,对Web页面作索引，建立和存储大量的基于关键字的索引，定位包含关键字的Web页面不足之处：对任一范围的话题，返回的文档数太庞大很多与话题相关的文档并不包含相应的关键字（多义问题）37Web搜索引擎基于索引:3737如何高效地发现和利用因特网上的资源？Web挖掘38如何高效地发现和3838Web挖掘

Web挖掘可分为三类：Web内容挖掘(Webcontentmining)，Web结构挖掘(Webstructuremining)，Web使用记录的挖掘(Webusagemining)。39Web挖掘Web挖掘可分为三类：3939挖掘Web链接结构权威Web页面：不仅相关，而且高质量，或针对该话题具有权威性超链能够推断权威页面Web页面包含指向其他页面的超链超链包含了大量人类潜在的注释超链可以看作是作者对链接页面的认可Web超链结构存在的问题并不是每一个超链都代表对寻找内容的认可导航、广告因竞争、商业等原因而不链接权威广告权威页面很少具有特别的描述40挖掘Web链接结构权威Web页面：不仅相关，而且高质量，或针40Web使用记录的挖掘Web日志记录提供了有关Web动态的丰富信息典型的Web日志记录条目包含了所请求的URL，发出请求的IP地址，时间戳等在Weblog记录上可以进行数据挖掘，用于找出关联模式，序列模式，和Web访问趋势等。

41Web使用记录的挖掘Web日志记录提供了有关Web动态的丰41EndQuestions?Let’sdiscussit!Thankyou!!!ProfessorJiaweiHan42EndQuestions?Thankyou!!!Prof42Chapter10：

复杂数据类型的挖掘广东商学院信息学院胡建军数据仓库与数据挖掘43Chapter10：

复杂数据类型的挖掘广东商学院信息学院43CourseOutline复杂数据对象的多维分析和描述性挖掘空间数据库挖掘多媒体数据库挖掘时序数据和序列数据的挖掘文本数据库挖掘Web挖掘44CourseOutline复杂数据对象的多维分析和描述性挖44CourseOutline复杂数据对象的多维分析和描述性挖掘空间数据库挖掘多媒体数据库挖掘时序数据和序列数据的挖掘文本数据库挖掘Web挖掘45CourseOutline复杂数据对象的多维分析和描述性挖45数据挖掘的对象简单数据关系数据库、事务数据库、数据仓库复杂类型数据复杂对象、空间数据、多媒体数据、时间序列数据、文本数据、Web数据等

挖掘技术：基本挖掘技术的扩展 针对复杂数据类型的新技术 实施知识挖掘的方法46数据挖掘的对象简单数据446复杂数据对象的多维分析 和描述性挖掘商品化数据仓库和OLAP工具用于多维分析的局限： 维———非数字数据 度量———聚集值复杂数据对象的概化及其概化数据的应用复杂数据的组织及存储方法类、类/子类对象：对象标识、属性、方法47复杂数据对象的多维分析 和描述性挖掘商品化数据仓库和OLA47复杂结构数据的概化复杂结构数据：集合、元组、列表、树、记录等及其组合；概化方法：保持原结构不变，概化其属性把原结构扁平化，概化扁平化的结构用高层概念或聚集汇总低沉结构返回原结构的类型或概貌48复杂结构数据的概化复杂结构数据：648集合值集合值一般概化方法：将集合中的每个值概化为其对应的更高级别的概念导出集合的一般特征（元素个数、区间、平均值、最大值等）示例：业余爱好{网球，曲棍球，国际象棋，小提琴，任天堂游戏

}概化：{体育，音乐，电子游戏}{体育（3），音乐（1），电子游戏（1）}49集合值集合值749列表值/序列值列表值/序列值类似于集合值属性的概化，要求保持元素的次序。一般概化方法：将列表中的每个值概化为对应的高层概念导出列表的一般特征（长度、元素类型、平均值、最大值等）50列表值/序列值列表值/序列值850空间和多媒体数据的概化聚集和近似计算空间数据 例：土地规划多媒体数据图像：尺寸、颜色、形状、纹理、方位等音乐：音调、节拍、乐器等文本：摘要、关键词等51空间和多媒体数据的概化聚集和近似计算951对象的概化对象标识符 沿类/子类层次结构概化继承特性 数据概化对直接数据与继承数据同等对待方法方法本身不能概化，但是可以对方法导出的数据进行概化52对象的概化对象标识符1052CourseOutline复杂数据对象的多维分析和描述性挖掘空间数据库挖掘多媒体数据库挖掘时序数据和序列数据的挖掘文本数据库挖掘Web挖掘53CourseOutline复杂数据对象的多维分析和描述性挖53空间数据库挖掘空间数据库及其一般特点存储了大量与空间有关的数据包含拓扑/距离信息复杂的、多维的索引结构访问通过空间数据的方法，通常需要空间推理、地理计算、空间知识表示技术空间数据挖掘：要综合数据挖掘与空间数据库技术54空间数据库挖掘空间数据库及其一般特点1254空间数据库挖掘传统空间数据分析（统计方法）的不足统计方法通常假设空间分布的数据间是统计上独立的，但现实是空间对象间是相互关联的；大部分统计模型只有具有相当丰富领域知识和统计方面经验的统计专家才用得起来；统计方法不适用符号值，或不完整或非确定的数据，对大规模数据库其计算代价也十分昂贵。空间数据挖掘将对传统的空间分析方法加以扩展，重点解决其高效性，可伸缩性，与数据库系统的紧密结合，改进与用户的交互，以及新的知识的发现。

55空间数据库挖掘传统空间数据分析（统计方法）的不足1355空间关联分析

空间关联规则形如:AB[s%，c%]其中A和B空间和非空间谓词的集合，s%表示规则的支持度，c%表示规则的的可信度。例：Is_a(X,”school”)∧close_to(X,“sports_center”)⇒close_to（X,“park”）[0.5%,80%]此规则表明80%靠近体育中心的学校同时也靠近公园，并且有0。5%的数据符合这一规则。

56空间关联分析空间关联规则形如:AB56空间聚类方法

空间数据聚类是要在一个较大的多维数据集中根据距离的计算找出簇，或稠密区域。

57空间聚类方法空间数据聚类是要在一个较大的多维57空间分类和空间趋势分析空间分类指分析空间对象导出与一定空间特征有关的分类模式，如郊区，高速公路，河流的邻接。空间趋势分析处理的是另一类问题：根据某空间维找出变化趋势。

例如，当离城市中心越来越远时，我们要分析经济形势的变化趋势，或离海洋越来越远时，气候与植物的变化趋势。

58空间分类和空间趋势分析空间分类指分析空间对象导出与一定空间特58CourseOutline复杂数据对象的多维分析和描述性挖掘空间数据库挖掘多媒体数据库挖掘时序数据和序列数据的挖掘文本数据库挖掘Web挖掘59CourseOutline复杂数据对象的多维分析和描述性挖59多媒体数据库挖掘多媒体数据库是指存储和管理大量多媒体对象的数据库，如音频数据，图象数据，视频数据，序列数据，以及超文本数据，包含文本，文本标记(textmarkup)，和链接(linkage)。多媒体数据的相似搜索

主要考虑两种多媒体标引和检索系统：（1）基于描述的检索系统，主要是在图象描述之上建立标引和执行对象检索，如关键字，标题，尺寸，创建时间等；（2）基于内容的检索系统，它支持基于图象内容的检索，如颜色构成，质地，形状，对象，和小波变换等。多媒体数据的分类和预测分析

多媒体数据中的关联规则挖掘

60多媒体数据库挖掘多媒体数据库是指存储和管理大量多媒体对象的数60CourseOutline复杂数据对象的多维分析和描述性挖掘空间数据库挖掘多媒体数据库挖掘时序数据和序列数据的挖掘文本数据库挖掘Web挖掘61CourseOutline复杂数据对象的多维分析和描述性挖61时序数据库和序列数据库时序数据库：由随时间变化的序列或事件组成的数据库等时间间隔测得的数据(regularintervals)时序数据库是一种序列数据库序列数据库：由有序事件序列组成的数据库可有时间标记，也可以没有时间标记可以是时序数据库，也可以不是。如WEB遍历。62时序数据库和序列数据库时序数据库：由随时间变化的序列或事件组62时序数据例子Time-seriesplot63时序数据例子Time-seriesplot2163时序数据和序列数据的挖掘（一）趋势分析

通过对趋势，循环，季节和非规则成分的运动的系统分析，使人们可以在较合理的情况下，制定出长期或短期的预测（即预报时序）

相似搜索

找出与给定查询序列最接近的数据序列。子序列匹配（subsequencematching）是找出与给定序列相似的所有数据序列，整体序列匹配（wholesequencematching）是找出彼此间相似的序列。

例 如：对金融市场的分析（如股票数据分析），医疗诊断（如心电图分析），和科学与工程数据库（如能量消耗分析）等

64时序数据和序列数据的挖掘（一）趋势分析2264时序数据和序列数据的挖掘（一）序列模式挖掘（sequencepatternmining）是指挖掘相对时间或其它模式出现频率高的模式。

周期分析（periodicityanalysis）

对周期模式的挖掘，即在时序数据库中找出重复出现的模式。

例如:

季节，潮汐，行星轨道，每日能源消耗，每日交通模式

65时序数据和序列数据的挖掘（一）序列模式挖掘（sequence65CourseOutline复杂数据对象的多维分析和描述性挖掘空间数据库挖掘多媒体数据库挖掘时序数据和序列数据的挖掘文本数据库挖掘Web挖掘66CourseOutline复杂数据对象的多维分析和描述性挖66文本数据库和信息检索（IR）文本数据库半结构化数据：它既不是完全无结构的也不是完全结构的。例如，一个文档可能包含结构字段，如标题，作者，出版日期，长度，分类，等等，也可能包含大量的非结果化的文本成分，如摘要和内容。典型的信息检索问题是基于用户的输入（如关键字或样例文档）定位相关的文档。典型的信息检索系统联机图书馆目录联机文档管理系统信息检索与数据库系统DB：并发控制、恢复、事务管理、更新IR：非结构化文档、基于关键字的近似搜索67文本数据库和信息检索（IR）文本数据库2567文本检索的基本度量查准率:反映正确性查全率:反映全面性RelevantRelevant&RetrievedRetrievedAllDocuments应该被检索到的68文本检索的基本度量查准率:反映正确性RelevantRele68文本检索的基本度量查准率:反映正确性查全率:反映全面性RelevantRelevant&RetrievedRetrievedAllDocuments实际被检索到的69文本检索的基本度量查准率:反映正确性RelevantRele69文本检索的基本度量查准率:反映正确性查全率:反映全面性RelevantRelevant&RetrievedRetrievedAllDocuments70文本检索的基本度量查准率:反映正确性RelevantRele70基于关键字的检索在关键字检索中，文档被看作字符串，可用一组关键字识别查询由关键字表达式构成例子,汽车and

修理店查询应考虑同义词问题,如：修理和维修困难同义词问题（Synonymy）:文档与Key相关，但Key在文档中不出现多义词问题（Polysemy）:同一Key在不同的上下文有不同的含义，如Mine。71基于关键字的检索在关键字检索中，文档被看作字符串，可用一组关71基于相似性的检索（1）相似检索是指基于一组共同的关键字找出相似的文档检索结果基于相关度，即：与关键词的近似性，关键词的出现频率等。非用词表（Stoplist）无关的高频词，如：a,the,of,for,etc.文档不同时，非用词表也不同72基于相似性的检索（1）相似检索是指基于一组共同的关键字找出相72基于相似性的检索（2）

由于相似文档具有相似的相对词频，因此我们可以基于频率表中的相对词频，计算一组文档的相似性。

词频矩阵相似度:基于一组关键词的文档相似性相关词的出现次数余弦距离：缺点：当词数T和文档数目D很大时，高的维数导致低的计算效率，且出现大的稀疏向量。用奇异值分解(SVD)技术减小词频矩阵大小保留词频矩阵中最有意义的K行和K列，K值为几百。词/文档d1d2d3d4d5d6d7t13218431687215430t2354917156826392t32232167462892251773基于相似性的检索（2）由于相似文档具有相似的相对词频，因此73文本数据挖掘的类型1.基于关键字的关联分析2.文档分类分析74文本数据挖掘的类型1.基于关键字的关联分析3274基于关键字的关联分析动机收集经常一起出现的关键字或词汇，然后找出其关联或相互关系关联分析过程文档预处理：文本数据分解，词根处理，过滤非用词等调用关联挖掘算法将每一文档看作一