火龙果数据挖掘概念与技术

1、2021年11月19日2 /72Course Outline挖掘复杂的数据数据挖掘的其他方法数据挖掘的应用数据挖掘与社会2021年11月19日3 /72数据挖掘的对象简单数据简单数据 关系数据库、事务数据库、数据仓库复杂类型数据复杂类型数据 复杂对象、空间数据、多媒体数据、时间序列数据、符号序列数据、生物学序列、文本数据、Web数据等 复杂的数据类型复杂的数据类型序列数据图与网络其他类型数据n 时间序列数据n 符号序列数据n 生物学序列n 同质数据或异质数据n 例子n 空间数据n 时间空间数据n 物流网系统数据n 多媒体数据n 文本数据n Web数据n 数据流挖掘序列数据序列是事件的有序列表。

2、根据事件的特征，序列数据可以分为三类（1）时间序列数据；（2）符号序列数据；（3）生物学序列。时间序列数据时间序列数据由相等时间间隔记录的数值数据的长序列组成。符号序列数据符号序列数据由事件或标称数据的长序列组成，通常不是相等的时间间隔观测。生物学序列生物学序列包括DNA序列和蛋白质序列。这种序列通常很长，携带重要的、复杂的、隐含的语义。2021年11月19日6 /72时序数据库和序列数据库时序数据库：时序数据库：由随时间变化的序列或事件组成的数据库等时间间隔测得的数据 (regular intervals)时序数据库是一种序列数据库序列数据库序列数据库：由有序事件序列组成的数据库可有时间标记

3、，也可以没有时间标记可以是时序数据库，也可以不是。如WEB遍历。2021年11月19日7 /72时序数据例子Time-series plot2021年11月19日8 /72时序数据和序列数据的挖掘（一） 趋势分析趋势分析 通过对趋势，循环，季节和非规则成分的运动的系统分析，使人们可以在较合理的情况下，制定出长期或短期的预测（即预报时序） 相似搜索相似搜索 找出与给定查询序列最接近的数据序列。 子序列匹配子序列匹配（subsequence matching）是找出与给定序列相似的所有数据序列， 整体序列匹配整体序列匹配（whole sequence matching）是找出彼此间相似的序列。 例

4、例 如：如：对金融市场的分析（如股票数据分析），医疗诊断（如心电图分析），和科学与工程数据库（如能量消耗分析）等 2021年11月19日9 /72时序数据和序列数据的挖掘（一）序列模式挖掘（序列模式挖掘（sequence pattern mining） 是指挖掘相对时间或其它模式出现频率高的模式。 周期分析周期分析 （periodicity analysis） 对周期模式的挖掘，即在时序数据库中找出重复出现的模式。 例如例如: 季节，潮汐，行星轨道，每日能源消耗，每日交通模式 符号序列中的序列模式挖掘序列模式序列模式是一个存在于单个序列或一个序列集中的频繁子序列。序列模式挖掘是挖掘在一个序列或

5、序列集中频繁的子序列。序列分类 基于特征的分类 基于序列距离的分类 基于模型的分类把序列转换成特征向量，然后使用传统的方法分类度量序列之间相似性的距离函数决定分类的质量如使用隐马尔科夫模型(HMM)或其他统计学模型来对2021年11月19日11 /722021年11月19日12 /72生物学序列对比序列对比基于如下事实：所有活的生物体都是进化相关的。这意味着进化中相近物种的核苷酸和蛋白质序列应该表现出更多的相似性。比对是对学列排列以便获取最大程度的一致性，它也表示序列之间的相似程度。同源：两个序列具有共同的祖先。生物学序列比对生物序列比对：对于给定的两个或多个输入生物序列，识别具有长保守子序列

6、的相似序列。局部比对：仅有部分序列进行比对。全局比对：在序列的整个长度上进行比对。图模式挖掘是在一个图或者一个图集中挖掘频繁子图（又称（子）图模式）。图模式挖掘的应用：产生图的索引结构，用于搜索；用频繁的和有区别力的子图作为特征，可有效地进行图分类。挖掘图和网络同质网络：所有的节点和边都具有相同的类型。异质网络：节点和边具有不同的类型。网络的统计建模通过网络分析，可以探查网络中的信息冗余，以进行高质量的数据清理、数据集成、信息验证和可信性分析。网络大型图和同质网络具有内聚结构，通常隐藏在大量互连的节点和链接中。异质网络包含不同类型的互联的节点和链接。这种互连结构包含丰富的信息，可以用来相互加强

7、节点和链接，从一种类型到另一种类型传播知识。网络的监督分类和半监督分类是当前的热门课题。图和网络的聚类、秩评定和分类2021年11月19日19 /72空间数据库挖掘空间数据库及其一般特点存储了大量与空间有关的数据包含拓扑/距离信息复杂的、多维的索引结构访问通过空间数据的方法，通常需要空间推理、地理计算、空间知识表示技术空间数据挖掘：要综合数据挖掘与空间数据库技术2021年11月19日20 /72空间数据库挖掘传统空间数据分析（统计方法）的不足 统计方法通常假设空间分布的数据间是统计上独立的，但现实是空间对象间是相互关联的； 大部分统计模型只有具有相当丰富领域知识和统计方面经验的统计专家才用得起

8、来； 统计方法不适用符号值，或不完整或非确定的数据，对大规模数据库其计算代价也十分昂贵。空间数据挖掘空间数据挖掘将对传统的空间分析方法加以扩展，重点解决其高效性，可伸缩性，与数据库系统的紧密结合，改进与用户的交互，以及新的知识的发现。 2021年11月19日21 /72空间聚类方法 空间数据聚类是要在一个较大的多维数据集中根据距离的计算找出簇，或稠密区域。 2021年11月19日22 /72空间分类和空间趋势分析空间分类空间分类指分析空间对象导出与一定空间特征有关的分类模式，如郊区，高速公路，河流的邻接。空间趋势分析空间趋势分析处理的是另一类问题：根据某空间维找出变化趋势 。 例如，当离城市中

9、心越来越远时，我们要分析经济形势的变化趋势，或离海洋越来越远时，气候与植物的变化趋势。 集成在物联网系统中的数据是动态的、异变的、含噪声的、不一致的和相互依赖的，包含丰富而复杂的信息，并且对于实事决策是至关重要的。 需要把当前环境与大型信息库联系，进行实时计算并准时返回响应。 该领域的研究包括物联数据流中稀有事件监测和异常分析，物联数据分析的可靠性，网联网中有效的时空数据分析，以及数据流挖掘与实时自动控制过程的集成。挖掘物联网系统数据2021年11月19日24 /72多媒体数据库挖掘 多媒体数据库多媒体数据库是指存储和管理大量多媒体对象的数据库，如音频数据，图象数据，视频数据，序列数据，以及超

10、文本数据，包含文本，文本标记(text markup)，和链接(linkage)。n 多媒体数据的相似搜索多媒体数据的相似搜索 主要考虑两种多媒体标引和检索系统： （1）基于描述的检索系统，主要是在图象描述之上建立标引和执行对象检索，如关键字，标题，尺寸，创建时间等；（2）基于内容的检索系统，它支持基于图象内容的检索，如颜色构成，质地，形状，对象，和小波变换等。n 多媒体数据的分类和预测分析多媒体数据的分类和预测分析 n 多媒体数据中的关联规则挖掘多媒体数据中的关联规则挖掘 2021年11月19日25 /72文本数据库和信息检索（IR） 文本数据库 半结构化数据： 它既不是完全无结构的也不是完

11、全结构的。例如，一个文档可能包含结构字段，如标题，作者，出版日期，长度，分类，等等，也可能包含大量的非结果化的文本成分，如摘要和内容。 典型的信息检索问题是基于用户的输入（如关键字或样例文档）定位相关的文档。 典型的信息检索系统 联机图书馆目录 联机文档管理系统 信息检索与数据库系统 DB：并发控制、恢复、事务管理、更新 IR：非结构化文档、基于关键字的近似搜索2021年11月19日26 /72文本检索的基本度量查准率:反映正确性查全率: 反映全面性| | |RelevantRetrievedRelevantrecall| | |RetrievedRetrievedRelevantprecis

12、ionRelevantRelevant & RetrievedRetrievedAll Documents应该被检索到的2021年11月19日27 /72文本检索的基本度量查准率:反映正确性查全率: 反映全面性| | |RelevantRetrievedRelevantrecall| | |RetrievedRetrievedRelevantprecisionRelevantRelevant & RetrievedRetrievedAll Documents实际被检索到的2021年11月19日28 /72文本检索的基本度量查准率:反映正确性查全率: 反映全面性| | |Rele

13、vantRetrievedRelevantrecall| | |RetrievedRetrievedRelevantprecisionRelevantRelevant & RetrievedRetrievedAll Documents2021年11月19日29 /72基于关键字的检索在关键字检索关键字检索中，文档被看作字符串，可用一组关键字识别查询由关键字表达式构成 例子, 汽车 and 修理店 查询应考虑同义词问题, 如： 修理 和 维修困难 同义词问题（Synonymy）:文档与Key相关，但Key在文档中不出现 多义词问题（Polysemy）:同一Key在不同的上下文有不同的含义

14、，如Mine。2021年11月19日30 /72基于相似性的检索（1）相似检索相似检索是指基于一组共同的关键字找出相似的文档检索结果基于相关度，即：与关键词的近似性，关键词的出现频率等。非用词表（Stop list）无关的高频词，如：a, the, of, for, etc.文档不同时，非用词表也不同2021年11月19日31 /72基于相似性的检索（2）n 由于相似文档相似文档具有相似的相对词频相对词频，因此我们可以基于频率表中的相对词频，计算一组文档的相似性。 词频矩阵n相似度: 基于一组关键词的文档相似性H相关词的出现次数H余弦距离：n缺点：缺点：当词数T和文档数目D很大时，高的维数导致

15、低的计算效率，且出现大的稀疏向量。用奇异值分解 (SVD)技术减小词频矩阵大小保留词频矩阵中最有意义的K行和K列，K值为几百。|),(212121vvvvvvsim词/文档d1d2 d3d4d5d6d7t132184 31687215430t235491 7156826392t32232 16746289225172021年11月19日32 /72文本数据挖掘的类型1.基于关键字的关联分析2.文档分类分析2021年11月19日33 /72基于关键字的关联分析动机 收集经常一起出现的关键字或词汇，然后找出其关联或相互关系关联分析过程 文档预处理：文本数据分解，词根处理，过滤非用词等 调用关联挖掘

16、算法 将每一文档看作一个事务 将文档中的关键词组看作事务中的一组事务项2021年11月19日34 /72文档分类 动机 自动对大量联机文档（web页面，email等）进行分类组织，以便于对文档进行检索和分析。 分类过程 数据预处理：提出关键字和词汇 定义训练集和测试集 调用分类算法创建分类模式 测试分类模式 应用导出的分类模式对其他新的、未知的联机文档分类 文档分类与关系数据库中的数据分类之间的区别 文档数据库是非结构化的，没有“属性值”对2021年11月19日35 /72 Web挖掘挑战 对数据仓库和数据挖掘而言，Web太庞大了 Web页面数据太复杂：没有结构，不标准 不断增长，不断变化 广

17、泛的用户群体 仅有很小部分的Web数据是有用的或相关的 99%的Web 信息对99% 的Web用户是无用的Internet growth0500000010000000150000002000000025000000300000003500000040000000Sep-69Sep-72Sep-75Sep-78Sep-81Sep-84Sep-87Sep-90Sep-93Sep-96Sep-99Hosts2021年11月19日36 /72Web 搜索引擎基于索引: 搜索Web页面,对Web页面作索引，建立和存储大量的基于关键字的索引，定位包含关键字的Web页面不足之处：对任一范围的话题，返回的文

18、档数太庞大很多与话题相关的文档并不包含相应的关键字（多义问题）2021年11月19日37 /72如何高效地发现和利用因特网上的资源？Web挖掘2021年11月19日38 /72Web挖掘 Web挖掘可分为三类：Web内容挖掘(Web content mining)，Web结构挖掘(Web structure mining)，Web使用记录的挖掘(Web usage mining)。 2021年11月19日39 /72挖掘Web链接结构权威Web页面：不仅相关，而且高质量，或针对该话题具有权威性超链能够推断权威页面 Web页面包含指向其他页面的超链 超链包含了大量人类潜在的注释 超链可以看作是作

19、者对链接页面的认可Web超链结构存在的问题 并不是每一个超链都代表对寻找内容的认可 导航、广告 因竞争、商业等原因而不链接权威广告 权威页面很少具有特别的描述2021年11月19日40 /72Web 使用记录的挖掘n Web日志记录提供了有关Web动态的丰富信息 典型的Web日志记录条目包含了所请求的URL，发出请求的IP地址，时间戳等n 在Weblog记录上可以进行数据挖掘，用于找出关联模式，序列模式，和Web访问趋势等。 数据挖掘的其他方法其他数据挖掘方法统计学数据挖掘数据挖掘基础可视与可听数据挖掘n 回归n 广义线性模型n 方差分析n 混合效应模型n 因素分析n 判别式分析n 生存分析n

20、 数据归约n 数据压缩n 概率统计理论n 微观经济学观点n 模式发现和归纳数据库n 数据可视化n 数据挖掘结果可视化n 数据挖掘过程可视化n 交互式可视数据挖掘n 听觉数据挖掘统计学分析方法统计学分析方法在数据挖掘中，统计学可应用于预测、聚类规则挖掘和时序数在数据挖掘中，统计学可应用于预测、聚类规则挖掘和时序数据的趋势分析等。据的趋势分析等。预测是数据分析的一种重要形式，通过建立连续值函数模型，预测是数据分析的一种重要形式，通过建立连续值函数模型，可以预测数据的未来变化趋势。连续值的预测可以使用统计学可以预测数据的未来变化趋势。连续值的预测可以使用统计学中的回归统计技术建模，如线性回归、多元回归、非线性回归、中的回归统计技术建模，如线性回归、多元回归、非线性回归、广义线性回归（对数回归、泊松回归等）。许多问题可以用线广义线性回归（对数回归、泊松回归等）。许多问题可以用线性回归方法解决，而更多的问题则可以对变量进行变换，使得性回归方法解决，而更多的问题则可以对变量进行变换，使得非线性的问题转换为线性的问题加以处理。非线性的问题转换为线性的问题加以处理。统计学分析方法统计学分析方法预测预测l 在数据属性之间存在两种关系：在数据属性之间存在两种关系： 函数关系：能用函数公式表