1、1/87目录o 第一章第一章绪论绪论o 第二章搜索技术第二章搜索技术o 第三章第三章知识表示知识表示o 第四章推理技术第四章推理技术 o 第五章第五章 机器学习机器学习o 第六章第六章 计算智能计算智能o 第七章数据挖掘第七章数据挖掘 o 第八章第八章 智能体技术智能体技术2/87o 数据挖掘定义与发展o 数据挖掘方法数据挖掘方法o 数据挖掘技术数据挖掘技术o Web数据挖掘数据挖掘o 大数据大数据3/87数据挖掘定义与发展数据库知识发现（Knowledge Discovery in Databases， KDD）数据挖掘(Data Mining DM) 数据分析（Data Analysis）
2、数据融合(Data Fusion)决策支持（Decision Supporting） 4/87数据挖掘定义与发展数据挖掘的数据挖掘的产生和发展产生和发展 苦恼: 淹没在数据中 ; 不能制定合适的决策! 数据n模式n趋势n事实n关系n模型n关联规则n序列n目标市场n资金分配n贸易选择n在哪儿做广告n销售的地理位置n金融n经济n政府nPOS.n人口统计n生命周期数据爆炸，知识贫乏数据爆炸，知识贫乏5/87数据挖掘定义与发展o1989 IJCAI会议： 数据库中的知识发现讨论专题nKnowledge Discovery in Databases (G. Piatetsky-Shapiro and W
3、. Frawley, 1991)o1991-1994 KDD讨论专题nAdvances in Knowledge Discovery and Data Mining (U. Fayyad, G. Piatetsky-Shapiro, P. Smyth, and R. Uthurusamy, 1996)o1995-1998 KDD国际会议 (KDD95-98)nJournal of Data Mining and Knowledge Discovery (1997)o1998 ACM SIGKDD, SIGKDD1999-2002 会议,以及SIGKDD Explorationso数据挖掘方面更
4、多的国际会议nPAKDD, PKDD, SIAM-Data Mining, (IEEE) ICDM, DaWaK, SPIE-DM, etc.6/87数据挖掘定义与发展知识发现的定义知识发现的定义 7/87数据挖掘定义与发展 （1）数据集：是指一个有关事实）数据集：是指一个有关事实F的集合，它是用来描述事物的集合，它是用来描述事物有关方面的信息，是进一步发现知识的原材料。数据可以是一个有关方面的信息，是进一步发现知识的原材料。数据可以是一个或一组数据库、数据仓库、电子表格或其他类型的信息库，在数或一组数据库、数据仓库、电子表格或其他类型的信息库，在数据上往往需要进行数据清理、集成和规约等预处理
5、。据上往往需要进行数据清理、集成和规约等预处理。 （2）新颖：经过知识发现提取出的模式必须是新颖的，至）新颖：经过知识发现提取出的模式必须是新颖的，至少对系统来说应该如此。模式是否新颖可以通过两个途径来衡量少对系统来说应该如此。模式是否新颖可以通过两个途径来衡量：其一是在所得到的数据方面，通过对比当前得到的数据和以前：其一是在所得到的数据方面，通过对比当前得到的数据和以前的数据或期望得到的数据之间的比较，来判断该模式的新颖程度的数据或期望得到的数据之间的比较，来判断该模式的新颖程度；其二是在其内部所包含的知识方面，通过对比，发现的模式与；其二是在其内部所包含的知识方面，通过对比，发现的模式与已
6、有的模式的关系来进行判断。已有的模式的关系来进行判断。8/87数据挖掘定义与发展 （3）潜在有用：提取出的模式应该是有意义的，有潜在的）潜在有用：提取出的模式应该是有意义的，有潜在的应用价值。这可以通过某些函数的值来衡量。应用价值。这可以通过某些函数的值来衡量。（4）可理解：知识发现的一个目标就是将数据库中隐含的）可理解：知识发现的一个目标就是将数据库中隐含的模式以容易被人理解的形式表现出来，从而帮助人们更好地了解模式以容易被人理解的形式表现出来，从而帮助人们更好地了解数据库中所包含的信息。数据库中所包含的信息。 （5）模式：模式是指用语言来表示的一个表达式，它可用）模式：模式是指用语言来表示
7、的一个表达式，它可用来描述数据集的特性，根据某种兴趣度度量，并于数据挖掘模块来描述数据集的特性，根据某种兴趣度度量，并于数据挖掘模块中进行交互挖掘，以便识别和表示知识的真正有趣的模式。中进行交互挖掘，以便识别和表示知识的真正有趣的模式。9/87数据挖掘定义与发展 （6）过程：过程是在）过程：过程是在KDD中包含的步骤，如数据的预处理中包含的步骤，如数据的预处理、模式搜索、知识表示及知识评估、过程优化等。、模式搜索、知识表示及知识评估、过程优化等。 （7）非平凡：是对数据进行更深层处理的过程，已经超越）非平凡：是对数据进行更深层处理的过程，已经超越了一般封闭形式的数量计算，包括对结构、模式和参数
8、的搜索。了一般封闭形式的数量计算，包括对结构、模式和参数的搜索。 （8）有效性：通过）有效性：通过KDD从当前数据所发现的模式必须有一从当前数据所发现的模式必须有一定的正确程度，否则定的正确程度，否则KDD就毫无作用。就毫无作用。10/87数据挖掘定义与发展知识知识发现的处理过程发现的处理过程 11/87数据挖掘定义与发展 （1）数据选择。根据用户的需求从数据库中提取与）数据选择。根据用户的需求从数据库中提取与KDD相相关的数据。关的数据。 （2）数据预处理。主要是对上述数据进行再加工，检查数）数据预处理。主要是对上述数据进行再加工，检查数据的完整性及数据的一致性，对丢失的数据利用统计方法进行
9、填据的完整性及数据的一致性，对丢失的数据利用统计方法进行填补，形成发掘数据库。补，形成发掘数据库。 （3）数据转换。从发掘数据库里选择数据，即根据知识发）数据转换。从发掘数据库里选择数据，即根据知识发现的任务对数据进行再处理，主要通过投影或数据库中的其他操现的任务对数据进行再处理，主要通过投影或数据库中的其他操作减少数据量。作减少数据量。 12/87数据挖掘定义与发展 （4）数据挖掘：）数据挖掘：n 确定确定KDD目标：目标： 根据用户要求，确定根据用户要求，确定KDD发现的知识类型，因发现的知识类型，因为对为对KDD的不同要求，会在具体的知识发现过程中采用不同的知的不同要求，会在具体的知识发
10、现过程中采用不同的知识发现算法。识发现算法。n 确定知识发现算法：确定知识发现算法： 根据阶段根据阶段5所确定的任务，选择合适的数据所确定的任务，选择合适的数据挖掘算法，包括选取合适的模型和参数，并使得挖掘算法与整个挖掘算法，包括选取合适的模型和参数，并使得挖掘算法与整个KDD的评判标准相一致。的评判标准相一致。n 数据挖掘：数据挖掘： 运用选定的挖掘算法，搜索或产生一个特定的感兴运用选定的挖掘算法，搜索或产生一个特定的感兴趣的模式或数据集，从数据中提取出用户所需要的知识，这些知趣的模式或数据集，从数据中提取出用户所需要的知识，这些知识可以用某种特定的方式表示或使用一些常用的表示方式，如产识可
11、以用某种特定的方式表示或使用一些常用的表示方式，如产生式规则等。生式规则等。13/87数据挖掘定义与发展 （5）模式解释：）模式解释： 对发现的模式进行解释，去掉多余的不切题对发现的模式进行解释，去掉多余的不切题意的模式，转换成某个有用的模式，以使用户理解。在此过程中意的模式，转换成某个有用的模式，以使用户理解。在此过程中，为了取得更为有效的知识，可能会返回前面处理中的某些步骤，为了取得更为有效的知识，可能会返回前面处理中的某些步骤，以便反复提取，从而提取出更有效的知识。，以便反复提取，从而提取出更有效的知识。 （6）知识评价：这一过程主要用于对所获得的规则进行价）知识评价：这一过程主要用于对
12、所获得的规则进行价值评定，以决定所得的规则是否存入基础知识库。值评定，以决定所得的规则是否存入基础知识库。上述上述KDD全过程的几个步骤可以进一步归纳为三个步骤，即全过程的几个步骤可以进一步归纳为三个步骤，即数据挖掘预处理（数据挖掘前的准备工作）、数据挖掘、数据挖数据挖掘预处理（数据挖掘前的准备工作）、数据挖掘、数据挖掘后处理（数据挖掘后的处理工作）。掘后处理（数据挖掘后的处理工作）。 14/87数据挖掘定义与发展 数据数据挖掘软件挖掘软件 典型数据挖掘系统有：典型数据挖掘系统有：SAS 公司的公司的Enterprise Miner、IBM 公司的公司的Intelligent Miner、SG
13、I 公司的公司的SetMiner、SPSS 公司的公司的Clementine、Sybase公司的公司的Warehouse Studio、RuleQuest Research 公司的公司的See5 、还有、还有CoverStory、EXPLORA、Knowledge Discovery Workbench、DBMiner、Quest、Microsoft SQL Server 2005等。等。 15/87数据挖掘的方法1. 统计方法统计方法统计方法是从事物的外在数量上的表现去推断该事物可能的统计方法是从事物的外在数量上的表现去推断该事物可能的规律性。规律性。 （1）传统方法）传统方法 渐近理论：当
14、样本趋于无穷多时的统计性质渐近理论：当样本趋于无穷多时的统计性质 三个阶段：搜集数据、分析数据、推理三个阶段：搜集数据、分析数据、推理 常用常用方法：方法： 回归分析（多元分析、自回归回归分析（多元分析、自回归）、）、 判别分析（贝叶斯判别、费歇尔判判别分析（贝叶斯判别、费歇尔判别、非参数判别别、非参数判别）、聚类分析）、聚类分析（系统聚类、动态聚类（系统聚类、动态聚类）、探索性）、探索性分析（主分析（主元分析法、相关分析法）元分析法、相关分析法）16/87数据挖掘的方法（2）模糊集）模糊集 开发数据的不确定性模型开发数据的不确定性模型 （3）支持向量机）支持向量机 支持向量机（支持向量机（s
15、upport vector machine, SVM）建立在统计）建立在统计学习理论和结构风险最小化原则之上，其主要思想是针对两类学习理论和结构风险最小化原则之上，其主要思想是针对两类分类问题，在高维空间中寻找一个超平面作为两类的分割，以分类问题，在高维空间中寻找一个超平面作为两类的分割，以保证最小的分类错误。保证最小的分类错误。 17/87数据挖掘的方法（3）支持向量机）支持向量机 不同的分类超平面 最优分类超平面及其间隔 线性不可分18/87数据挖掘的方法（4）粗糙集）粗糙集 粗糙集合理论粗糙集合理论(Rough Set, 也称为也称为RS理论理论)由波兰数学家由波兰数学家Pawlak.Z
16、于于1982年提出。粗糙集对不精确概念的描述是通过上年提出。粗糙集对不精确概念的描述是通过上近似（近似（upper approximation）和下近似（）和下近似（lower approximation）这两个精确概念来实现的。一个概念（或集合）的下近似是）这两个精确概念来实现的。一个概念（或集合）的下近似是指其中的元组肯定属于该概念；一个概念（或集合）的上近似指其中的元组肯定属于该概念；一个概念（或集合）的上近似是指其中的元组可能属于该概念是指其中的元组可能属于该概念。 粗糙粗糙集方法优点：不需要预先知道的额外信息，如统计中集方法优点：不需要预先知道的额外信息，如统计中要求的先验概率和模糊
17、集中要求的隶属度，算法简单，易于操要求的先验概率和模糊集中要求的隶属度，算法简单，易于操作。作。19/87数据挖掘的方法 集合的上、下近似概念示意集合的上、下近似概念示意 XAprA XAprAX20/87数据挖掘的方法2. 机器学习方法机器学习方法可能用于机器发现的机器学习方法有：可能用于机器发现的机器学习方法有：（1） 规则归纳。规则归纳。 规则反映数据项中某些属性或数据集中某些数据项之间的统规则反映数据项中某些属性或数据集中某些数据项之间的统计相关性。计相关性。（2）决策树。）决策树。 决策树的每一个非终叶节点表示所考虑的数据项的测试或决决策树的每一个非终叶节点表示所考虑的数据项的测试或
18、决策。策。（3）范例推理。）范例推理。 范例推理是直接使用过去的经验或解法来求解给定的问题。范例推理是直接使用过去的经验或解法来求解给定的问题。21/87数据挖掘的方法（4） 贝叶斯网络。贝叶斯网络。 贝叶斯信念网络是概率分布的图表示。贝叶斯网络基于后验贝叶斯信念网络是概率分布的图表示。贝叶斯网络基于后验概念的贝叶斯定理，是建立在数据进行统计处理基础上的方法，概念的贝叶斯定理，是建立在数据进行统计处理基础上的方法，将不确定事件通过网络连接起来，可以对其他相关事件的结果进将不确定事件通过网络连接起来，可以对其他相关事件的结果进行预测，其网络变量可以是可见的，也可隐藏在训练样本中。贝行预测，其网络
19、变量可以是可见的，也可隐藏在训练样本中。贝叶斯网络具有分类、聚类、预测和因果关系分析的功能，其优点叶斯网络具有分类、聚类、预测和因果关系分析的功能，其优点是易于理解，预测效果较好，缺点是对发生频率很低的事件预测是易于理解，预测效果较好，缺点是对发生频率很低的事件预测效果不好。效果不好。 22/87数据挖掘的方法 （5）遗传算法。遗传算法。 在求解过程中，通过最好解的选择和彼此组合，使期望解的在求解过程中，通过最好解的选择和彼此组合，使期望解的集合愈来愈好。集合愈来愈好。 3. 神经计算方法神经计算方法 4. 可视化方法可视化方法可视化（可视化（visualization）就是把数据、信息和知识
20、转化为可）就是把数据、信息和知识转化为可视的表示形式的过程。视的表示形式的过程。23/87数据挖掘技术 按数据按数据挖掘任务分类挖掘任务分类n描述（描述（Description）：了解数据中潜在的规律）：了解数据中潜在的规律n预言（预言（Predication）：用历史预测未来）：用历史预测未来 数据挖掘技术数据挖掘技术n概念概念/类描述类描述n关联规则分析关联规则分析n分类（分类（预言预言）n聚类聚类n序列模式序列模式n异常检测异常检测24/87数据挖掘技术1. 概念概念/类描述（类描述（Concept Description) 特征化和区分（特征化和区分（Characterization
21、and Comparision) 概念或类别描述使用汇总的、简洁的、精确的方式描述每概念或类别描述使用汇总的、简洁的、精确的方式描述每个类和概念，可通过前面的方法得到：个类和概念，可通过前面的方法得到： （1）数据特征化，一般地汇总所研究类的数据；）数据特征化，一般地汇总所研究类的数据； （2）数据区分，将目标类与一个或多个比较类进行比较；）数据区分，将目标类与一个或多个比较类进行比较； （3）数据特征化和比较，两者的结合。）数据特征化和比较，两者的结合。 数据特征的输出可以用多种形式输出，包括扇形图、条图、数据特征的输出可以用多种形式输出，包括扇形图、条图、曲线、多位数据立方体和交叉表在内的
22、多维表。结果描述也可以曲线、多位数据立方体和交叉表在内的多维表。结果描述也可以用概括关系或关联规则形式来表示。用概括关系或关联规则形式来表示。25/87数据挖掘技术2. 关联分析关联分析(Association Rules) 关联规则分析就是发现关联规则，关联规则分析就是发现关联规则，在交易数据、关系数据或在交易数据、关系数据或其他信息载体中，查找存在于项目集合或对象集合之间的频繁模其他信息载体中，查找存在于项目集合或对象集合之间的频繁模式、关联、相关性、或因果结构。式、关联、相关性、或因果结构。 规则形式：规则形式： Body Head support, confidence例：例：buys
23、(x, “diapers”) buys(x, “beers”) 0.5%, 60%major(x, “CS”) takes(x, “DB”) grade(x, “A”) 1%, 75%26/87数据挖掘技术支持支持度度s， 一次交易中包含一次交易中包含A,B的可能性的可能性 Support(AB)= P(A B)； 可信度可信度 c， 包含包含A的交易中也包含的交易中也包含B的条件概率的条件概率 Confidence (AB)=P(B|A) 同时满足大于等于最小支持度阈值（同时满足大于等于最小支持度阈值（min_support）和最小）和最小可信度（可信度（min_confidence）的规则
24、称作强规则。）的规则称作强规则。 满足大于等于最小支持度满足大于等于最小支持度(min_support), 称项目集称项目集X I是频是频繁项目集繁项目集(Frequent Itemset)。27/87数据挖掘技术 对于对于 A C：support = support(A 、C) = 50%confidence = support(A 、C)/support(A) = 66.6%交易ID购买商品2000A,B,C1000A,C4000A,D5000B,E,F频繁项集支持度A75%B50%C50%A,C50%最小支持度 50%最小可信度 50%28/87数据挖掘技术 Apriori算法算法 基本
25、思想基本思想: 频繁项集的任何子集也一定是频繁的。频繁项集的任何子集也一定是频繁的。 算法的核心算法的核心: 用频繁的用频繁的(k 1)-项集生成候选的频繁项集生成候选的频繁 k-项集项集 用数据库扫描和模式匹配计算候选集的支持度用数据库扫描和模式匹配计算候选集的支持度算法瓶算法瓶颈颈: 候选集生成候选集生成 巨大的候选集巨大的候选集: 多次扫描数据库：多次扫描数据库：29/87数据挖掘技术 TID Items100 1 3 4200 2 3 5300 1 2 3 5400 2 5数据库 Ditemset sup.1223334153itemset sup.12233353扫描 DC1L1it
26、emset1 21 31 52 32 53 5itemset sup1 211 321 512 322 533 52itemset sup1 322 322 533 52L2C2C2扫描 DC3L3itemset2 3 5扫描 Ditemset sup2 3 5230/87数据挖掘技术3. 分类分类(Classification) 分类是找出描述并区分数据类或概念的分类函数或分类模型分类是找出描述并区分数据类或概念的分类函数或分类模型(也常常称作分类器也常常称作分类器)，该模型能把数据库中的数据项映射到给定，该模型能把数据库中的数据项映射到给定类别中的某一个，以便能使用模型预测类标记未知的对象
27、类。类别中的某一个，以便能使用模型预测类标记未知的对象类。 常用的分类方法常用的分类方法： （1） 信息论信息论方法方法 ID3方法方法 -决策树方法决策树方法 利用信息论中信息增益寻找数据库中具有最大信息量的字利用信息论中信息增益寻找数据库中具有最大信息量的字段，建立决策树的一个节点，并根据字段的不同取值建立树的分段，建立决策树的一个节点，并根据字段的不同取值建立树的分枝，在每个分枝子集中重复建树的下层节点。枝，在每个分枝子集中重复建树的下层节点。31/87数据挖掘技术 （2） 集合论方法集合论方法 粗集方法、概念格方法粗集方法、概念格方法 （3） 人工神经网络方法人工神经网络方法 前馈网络
28、：含感知机前馈网络：含感知机.反向传输模型反向传输模型.函数式网络。函数式网络。 反馈式网络：用于联想记忆和优化计算。反馈式网络：用于联想记忆和优化计算。 自组织网络：用于聚类。自组织网络：用于聚类。 （4）遗传算法：模拟生物进化过程的方法。）遗传算法：模拟生物进化过程的方法。 （5）统计分析方法：贝叶斯网，线性回归分析，线性判别分）统计分析方法：贝叶斯网，线性回归分析，线性判别分析，聚类分析，差异分析，因子分析等。析，聚类分析，差异分析，因子分析等。32/87数据挖掘技术4. 聚类聚类(Clustering) 聚类是把数据按照相似聚类是把数据按照相似性归纳成若干类别，同一类性归纳成若干类别，
29、同一类中的数据彼此相似，不同类中的数据彼此相似，不同类中的数据相异。中的数据相异。 聚类是一种无监督分类聚类是一种无监督分类法，法， 没有预先指定的类。没有预先指定的类。X值聚类示例33/87数据挖掘技术 与与分类的区别：分类的区别： 分类依赖于预先定义的类和带类标号的训练实例，是一种分类依赖于预先定义的类和带类标号的训练实例，是一种观察式观察式 的学习；而聚类是找到这个簇的特征或者标号的过程。的学习；而聚类是找到这个簇的特征或者标号的过程。 一个有效的聚类算法必须满足两个条件：一个有效的聚类算法必须满足两个条件： 类内数据对象的强相似性，通常用紧致度描述；类内数据对象的强相似性，通常用紧致度
30、描述； 类间数据对象的弱相似性，常采用分离度描述。类间数据对象的弱相似性，常采用分离度描述。34/87数据挖掘技术 聚类算法的分类聚类算法的分类 聚类分析算法取决于数据的类型、聚类的目的和应用。聚类分析算法取决于数据的类型、聚类的目的和应用。 （1）基于划分方法）基于划分方法 给定一个包含给定一个包含n个对象的数据集和要构建的划分数目个对象的数据集和要构建的划分数目k，划，划分方法首先创建一个初始划分，然后采用一种迭代的重定位技分方法首先创建一个初始划分，然后采用一种迭代的重定位技术，尝试通过对象在划分间的移动来改进划分术，尝试通过对象在划分间的移动来改进划分 （2）基于层次方法）基于层次方法
31、 层次聚类是将数据集分解成几级进行聚类，层的分解可以层次聚类是将数据集分解成几级进行聚类，层的分解可以用树形图来表示以任一样本用树形图来表示以任一样本35/87数据挖掘技术 （3）基于密度的方法基于密度的方法 点为基础，当该点的给定邻域内包含的数据点个数超过某点为基础，当该点的给定邻域内包含的数据点个数超过某一给定阈值时，就以其邻域中的数据点为基础继续进行广度或一给定阈值时，就以其邻域中的数据点为基础继续进行广度或深度探索，扩展簇的大小。深度探索，扩展簇的大小。 （4）基于网格的方法）基于网格的方法 基于网格的聚类算法的特点是采用一个多分辨率的网格数基于网格的聚类算法的特点是采用一个多分辨率的
32、网格数据结构，从而在该网格结构上进行聚类。据结构，从而在该网格结构上进行聚类。 （5）基于模型的方法）基于模型的方法 基于模型的方法为每个类假定了一个模型，并试图寻找数基于模型的方法为每个类假定了一个模型，并试图寻找数据对给定模型的最佳拟合。据对给定模型的最佳拟合。36/87数据挖掘技术 K-means算法算法 （1）从）从D中随机取中随机取k个元素，作为个元素，作为k个簇的各自的中心。个簇的各自的中心。 （2）分别计算剩下的元素到）分别计算剩下的元素到k个簇中心的相似度，将这些个簇中心的相似度，将这些元素分别划归到相似度最高的簇。元素分别划归到相似度最高的簇。 （3）根据聚类结果，重新计算）
33、根据聚类结果，重新计算k个簇各自的中心。个簇各自的中心。 （4）将）将D中全部元素按照新的中心重新聚类。中全部元素按照新的中心重新聚类。 （5）重复第）重复第4步，直到聚类结果不再变化。步，直到聚类结果不再变化。 （6）将结果输出。）将结果输出。37/87数据挖掘技术 例：现有一个数据集例：现有一个数据集1，2，30，15，10，18，3，9，8，25，用，用K-means算法将这些数据聚类。算法将这些数据聚类。 解：设解：设k=3，即将数据集聚成，即将数据集聚成3类。随机选取类。随机选取3个数作为初始簇均值：个数作为初始簇均值：m1=9，m2=8，m3=25，开始迭代。，开始迭代。 相似度度
34、量采用的距离值为两个数的差的绝对值。相似度度量采用的距离值为两个数的差的绝对值。第一次迭代得到第一次迭代得到3个簇是个簇是 K1=1，2，3，8， k2=9，10，15 ， k3=18，25，30 重新计算每个簇的均值，则均值更新为重新计算每个簇的均值，则均值更新为m1=3.5，m2=11.3，m3=24.3第二次迭代第二次迭代 得到得到3个簇个簇 K1=1，2，3， k2=8， 9，10，15 ， k3=18，25，30 新的均值为新的均值为m1=3.5，m2=11.3，m3=24.338/87数据挖掘技术 第三次迭代得到第三次迭代得到3个簇是个簇是 K1=1，2，3， k2=8， 9，10
35、，15，18 ， k3=25，30 新新的均值为的均值为m1=2，m2=12，m3=27.5第四次迭代第四次迭代 得到得到3个簇个簇 K1=1，2，3， k2=8， 9，10，15，18 ， k3=25，30 每个簇的数据不再变化，达到稳定，算法终止。每个簇的数据不再变化，达到稳定，算法终止。39/87数据挖掘技术 相似性度量相似性度量(1)欧几里德距离欧几里德距离(Euclidean Distance)(2)曼哈顿距离曼哈顿距离(Manhattan Distance)40/87数据挖掘技术(3)明考斯基距离明考斯基距离(Minkowski Distance)(4)夹角余弦距夹角余弦距Ig(C
36、osine Distance)41/87数据挖掘技术5.序列序列(Sequence)模式模式 序列模式是指通过时间序列搜索出的重复发生概率较高的序列模式是指通过时间序列搜索出的重复发生概率较高的模式。模式。 时间序列模式根据数据随时间变化的趋势预测将来的值。时间序列模式根据数据随时间变化的趋势预测将来的值。这里要考虑到时间的特殊性质，像一些周期性的时间定义如星这里要考虑到时间的特殊性质，像一些周期性的时间定义如星期、月、季节、年等，以及不同的日子如节假日可能造成的影期、月、季节、年等，以及不同的日子如节假日可能造成的影响，日期本身的计算方法，还有一些需要特殊考虑的地方如时响，日期本身的计算方法
37、，还有一些需要特殊考虑的地方如时间前后的相关性间前后的相关性(过去的事情对将来有多大的影响力过去的事情对将来有多大的影响力)等等。 42/87数据挖掘技术 例例：顾客租借影碟的一个典型的顺序是先租顾客租借影碟的一个典型的顺序是先租“星球大战星球大战”，然后是然后是“帝国反击战帝国反击战”，再是，再是“杰达武士归来杰达武士归来”(这三部影片是这三部影片是以故事发生的时间先后而情节连续的以故事发生的时间先后而情节连续的)。值得注意的是租借这三。值得注意的是租借这三部电影的行为并不一定需要是连续的。在任意两部之间插租了部电影的行为并不一定需要是连续的。在任意两部之间插租了任何电影，仍然满足这个序列模
38、式，并且扩展一下，序列模式任何电影，仍然满足这个序列模式，并且扩展一下，序列模式的元素也可以不只是一个物品的元素也可以不只是一个物品(如一部电影如一部电影)，它也可以是一个，它也可以是一个物品的集合。物品的集合。 43/87数据挖掘技术6.异常异常(Outlier)检测检测 异常检测是用来发现异常检测是用来发现”小的模式小的模式”(相对于聚类相对于聚类)，即数据，即数据集中间显著不同于其它数据的对象。集中间显著不同于其它数据的对象。 常用方法：常用方法： 基于统计（基于统计（statistical-based)的方法的方法 基于距离基于距离 (distance-based)的方法的方法 基于偏
39、差基于偏差(deviation-based)的方法的方法 基于密度基于密度(density-based)的方法的方法44/876.8 知识发现6.8.7 Web数据挖掘 1. Web数据挖掘定义 网络数据资源种类： 第一类是内容(Content)，即网页上的真正数据； 第二类是结构(Structure)，即描述内容组织的数据；结构信息包括各种HTML或XML标记及其出现的序列等，其中最主要的结构信息是网页之间的超链接； 第三类是使用(Usage)，是网页被人浏览的记录，如IP地址、访问时间等，这些信息可以从Web服务器的日志文件获得。 第四类是用户资料(User Profile)，是某个网站中
40、记录的用户资料。 45/87Web数据挖掘1. Web数据挖掘定义数据挖掘定义 定义：定义： Web挖掘是对挖掘是对Web文档的内容、文档的内容、Web上可利用资源的使用上可利用资源的使用情况以及资源之间的关系进行分析，从中发现有效的、新颖的情况以及资源之间的关系进行分析，从中发现有效的、新颖的、潜在有用的、并且最终可理解的模式。、潜在有用的、并且最终可理解的模式。 46/87Web数据挖掘2. Web数据挖掘流程数据挖掘流程 查找资源、信息选择及预处理、模式发现、模式分析。查找资源、信息选择及预处理、模式发现、模式分析。 查找资源查找资源 从各种从各种Web数据源中得到数据，数据可以来自于数
41、据源中得到数据，数据可以来自于Web文档、电子邮件、新闻组或文档、电子邮件、新闻组或Web日志等；日志等； 信息选择及预处理信息选择及预处理 从查找得来的资源中除去无用信息，保从查找得来的资源中除去无用信息，保留有用信息，并将信息进行必要的整理；留有用信息，并将信息进行必要的整理； 模式发现模式发现 在一个站点内部或在多个站点间自动进行模式发在一个站点内部或在多个站点间自动进行模式发现；现； 模式分析模式分析 验证、解释所发现的模式，它可以通过与分析人验证、解释所发现的模式，它可以通过与分析人员进行交互或者由机器自动完成。员进行交互或者由机器自动完成。 47/87Web数据挖掘3. Web数据
42、挖掘分类数据挖掘分类 Web挖掘Web内容挖掘Web结构挖掘Web使用挖掘文本挖掘多媒体挖掘超链接挖掘结构挖掘访问日志挖掘48/87Web数据挖掘 Web内容挖掘内容挖掘 从从Web文档内容或其描述中发现有用信息的过程文档内容或其描述中发现有用信息的过程。 常用的常用的Web内容挖掘方法：内容挖掘方法： （1）改进的）改进的WWW的搜索引擎，包括的搜索引擎，包括Web Crawler,Lycos； （2）数据库方法：把半结构化的）数据库方法：把半结构化的Web信息重构，使得信息重构，使得Web信息更信息更结构化，然后就可以使用标准化的数据库查询机制和数据挖掘方法结构化，然后就可以使用标准化的数
43、据库查询机制和数据挖掘方法进行分析进行分析； （3）对页面中的文本进行特征描述，特征描述的模型有很多种）对页面中的文本进行特征描述，特征描述的模型有很多种，向量空间模型（，向量空间模型（VSM），布尔逻辑模型，概率模型等等。继而对），布尔逻辑模型，概率模型等等。继而对特征向量进行挖掘，对页面中的多媒体信息进行多媒体信息挖掘，特征向量进行挖掘，对页面中的多媒体信息进行多媒体信息挖掘，具体方法有页面内容摘要、分类、聚类以及关联规则发现等。具体方法有页面内容摘要、分类、聚类以及关联规则发现等。49/87Web数据挖掘 Web结构挖掘结构挖掘 从从web结构中发现潜在链接模式的过程。由于结构中发现潜在
44、链接模式的过程。由于文档之间存在着超链接，文档之间存在着超链接，WWW可以通过这种超链接揭示出文档可以通过这种超链接揭示出文档内容之外的一些有价值的信息。例如指向一个页面的超链接数目内容之外的一些有价值的信息。例如指向一个页面的超链接数目就表明了该文档受欢迎的程度，而其包含的超链接数目就表明该就表明了该文档受欢迎的程度，而其包含的超链接数目就表明该文档主题的丰富程度。文档主题的丰富程度。 结构挖掘的功能是通过分析一个结构挖掘的功能是通过分析一个Web页面链接和被链接数量页面链接和被链接数量以及链接对象的重要性来建立以及链接对象的重要性来建立Web的链接结构模式，并为户提供的链接结构模式，并为户
45、提供与请求相关度较大的与请求相关度较大的Web页面，提高搜索引擎的精度和查全率。页面，提高搜索引擎的精度和查全率。主要有主要有PageRank和和Hub/Authority两种算法。两种算法。 50/87Web数据挖掘 Web使用挖掘使用挖掘 通过对用户在访问通过对用户在访问WWW服务器时留下的访问服务器时留下的访问记录进行挖掘，从而获得有关用户的访问模式。服务器日志包括记录进行挖掘，从而获得有关用户的访问模式。服务器日志包括访问日志、引用日志和代理日志。访问日志、引用日志和代理日志。 访问日志访问日志记录了用户的标识、访问时间、方法、请求的页面记录了用户的标识、访问时间、方法、请求的页面、协
46、议、服务器状态及传输字节数等；、协议、服务器状态及传输字节数等； 引用日志引用日志记录的是被请求页面的存放位置；记录的是被请求页面的存放位置； 代理日志代理日志记录了用户使用的浏览器和操作系统的类型。根据记录了用户使用的浏览器和操作系统的类型。根据三者的内在关系，可以将它们拼接成完整的日志纪录并以关系表三者的内在关系，可以将它们拼接成完整的日志纪录并以关系表形式保存在数据库中。形式保存在数据库中。51/87Web数据挖掘 这些这些信息中隐含着用户对特定内容的需要。信息中隐含着用户对特定内容的需要。Web使用记录挖使用记录挖掘是通过处理服务器日志文件，以发现用户的浏览模式，如序掘是通过处理服务器
47、日志文件，以发现用户的浏览模式，如序列模式、关联规则、用户聚类和页面聚类等，理解用户的行为列模式、关联规则、用户聚类和页面聚类等，理解用户的行为，从而实现：（，从而实现：（1）寻找用户的兴趣，进行网页预测推荐，为用）寻找用户的兴趣，进行网页预测推荐，为用户提供个性化服务；（户提供个性化服务；（2）改进和优化）改进和优化Web站点结构。站点结构。 52/87大数据价值发现大数据价值发现2008年全球产生的数据量为年全球产生的数据量为0.49ZB(250MB)2009年的数据量为年的数据量为0.8ZB2010年增长为年增长为1.2ZB2011年的数量更是高达年的数量更是高达1.82ZB2012年为
48、止，人类所有印刷材料的数据量是年为止，人类所有印刷材料的数据量是200PB预计到预计到2020年，全世界的数据规模将达今天的年，全世界的数据规模将达今天的44倍。倍。 Farecast: 飞机票价格预测购票时机与机票价格的关系? 怎样预测机票价格? 只求关系，不求因果不要相信经验，一切以数据说话大数据53/87大数据价值发现大数据价值发现n华尔街金融家利用电脑程序分析全球华尔街金融家利用电脑程序分析全球3.4亿微博账户的留言，亿微博账户的留言，根据民众情绪抛售股票：根据民众情绪抛售股票：n银行根据求职网站的岗位数量，推断就业率；银行根据求职网站的岗位数量，推断就业率； n投资机构搜集并分析上市
49、企业声明，从中寻找破产的蛛丝马迹；投资机构搜集并分析上市企业声明，从中寻找破产的蛛丝马迹； n美国总统奥巴马的竞选团队依据选民的微博，实时分析选民对美国总统奥巴马的竞选团队依据选民的微博，实时分析选民对总统竞选人的喜好，基于数据对竞选议题的把握，成功赢得总总统竞选人的喜好，基于数据对竞选议题的把握，成功赢得总统大选。统大选。n中国网民发动的中国网民发动的“人肉搜索人肉搜索”，已成功地使若干，已成功地使若干“表哥表哥”“”“表表叔叔”“”“房叔房叔”“”“房妹房妹”等腐败官员落入法网。等腐败官员落入法网。n大数据54/87大数据特点大数据特点 3 个个“V”：o 数据体量巨大（数据体量巨大（ V
50、olume ）：从）：从TB级别，跃升到级别，跃升到PB级别；级别；o 数据类型繁多（数据类型繁多（ Variety ）：日志、视频、图片、位置信息等）：日志、视频、图片、位置信息等等。等。o 处理速度快（处理速度快（ Velocity ）：）：1秒定律，实时分析与处理。秒定律，实时分析与处理。o 价值密度低（价值密度低（ Value ），商业价值高：如连续不间断视频监控），商业价值高：如连续不间断视频监控过程中，可能有用的数据仅仅有一两秒。过程中，可能有用的数据仅仅有一两秒。o 真实性（真实性（Veracity）：数据质量对于分析和决策相当重要。）：数据质量对于分析和决策相当重要。大数据4
