《机器学习与数据挖掘》由会员分享，可在线阅读，更多相关《机器学习与数据挖掘（57页珍藏版）》请在金锄头文库上搜索。
1、机器学习与数据挖掘基础11.1 机器学习的概念心理学中对学习的解释是：学习是指（人或动物）依靠经验的获得而使行为持久变化的过程。Simon认为：如果一个系统能够通过执行某种过程而改进它的性能，这就是学习。 Minsky认为：学习是在人们头脑中（心理内部）进行有用的变化。Tom M. Mitchell在机器学习一书中对学习的定义是：对于某类任务T和性能度P，如果一个计算机程序在T上以P衡量的性能随着经验E而自我完善，那么，我们称这个计算机程序从经验E中学习。当前关于机器学习的许多文献中也大都认为：学习是系统积累经验以改善其自身性能的过程。1 机器学习概述2 总之总之： 学习与经验有关； 学习可以
2、改善系统性能； 学习是一个有反馈的信息处理与控制过程。因为经验是在系统与环境的交互过程中产生的，而经验中应该包含系统输入、响应和效果等信息。因此经验的积累、性能的完善正是通过重复这一过程而实现的。31.2 机器学习系统的基本模型模型中包含学习系统的四个基本组成环节。环境和知识库是以某种知识表示形式表达的信息的集合，分别代表外界信息来源和系统具有的知识。学习环节和执行环节代表两个过程。学习环节处理环境提供的信息，以便改善知识库中的显式知识。执行环节利用知识库中的知识来完成某种任务，并把执行中获得的信息回送给学习环节。41.2 机器学习系统的基本模型环境可以是系统的工作对象，也可以包括工作对象和外
3、界条件。例如在医疗系统中，环境就是病人当前的症状、检验的数据和病历。在模式识别中，环境就是待识别的图形或景物。 5学习环节通过获得外部信息，并将这些信息与执行环节所反馈回的信息进行比较。一般情况下环境提供的信息水平与执行环节所需的信息水平之间往往有差距，经分析、综合、类比、归纳等思维过程，学习环节就要从这些差距中获取相关对象的知识，并将这些知识存入知识库中。1.2 机器学习系统的基本模型6知识库用于存放由学习环节所学到的知识。影响学习系统设计的第二个因素是知识库的形式和内容。知识库的形式就是知识表示的形式（一阶谓词逻辑、产生式规则、框架、语义网络、类和对象、模糊集合、贝叶斯网络、脚本、过程等）
4、。选择知识表示方法要考虑下列准则：可表达性、推理难度、可修改性和可扩充性。1.2 机器学习系统的基本模型7执行环节是整个机器学习系统的核心。执行环节用于处理系统面临的现实问题，即应用知识库中所学到的知识求解问题，并对执行的效果进行评价，将评价的结果反馈回学习环节，以便系统进一步的学习。1.2 机器学习系统的基本模型81. 基于学习策略的分类基于学习策略的分类机械学习传授学习类比学习归纳学习基于解释的学习1.3 机器学习的分类9机械学习 机械学习(Rote Learning)又叫做记忆学习，或死记硬背学习。机械学习就是记忆，把新知识储存起来，需要时对储存的知识进行检索，而不再需要计算和推理。机械
5、学习模式：设系统的输入模式为(X1，X2，Xn)，对应的输出模式为(Y1，Y2 ，Ym)。把每次的输入输出数据存储起来，形成输入输出模式集合(X1，X2，Xn)，(Y1，Y2，Ym)，使用时根据给定的输入数据，直接查找、检索输出。10传授式学习传授学习(Learning by Being Told或Learning by Instruction)又称为指点学习。这时，环境提供的信息较抽象，水平较高，学习环节把这些信息变换成执行环节使用的较低水平的信息。11传授式学习McCarthy 1958年计划建立一个接收建议的系统，系统可以接受专家的建议并用于规划某一领域的行动。20世纪70年代后期，开始
6、研究接收专家建议，改进专家系统的工作。1980-1981年Hayes Roth提出自动接收建议过程。12传授式学习1.要求请求专家提出建议。有时对专家的要求是简单的，即请专家提供一般的建议。有时，对专家的要求是复杂的，即请专家识别知识库的欠缺，并提出修改方法。有些系统是被动的，它消极等待专家提出建议。有些系统是主动的，它把专家注意力引向特定的问题。2.解释这是把专家建议转成内部表示，是知识表示问题。内部表示应包含建议的全部信息。如果用自然语言提出建议，解释过程应包括自然语言理解。 13传授式学习3. 实用化这是传授学习的信息变换过程，它把抽象的建议转成具体的知识。实用化过程类似于自动程序设计。
7、前者由建议得到实用的规则，后者由程序说明得到程序。二者也存在差别。后者要求得到完全正确的程序，强调程序的正确性。前者往往使用弱方法，不保证完全正确。实用化过程有时作试探性的假设和近似，只能要求其合理性。得到的假设还要经过检验和修改。14传授式学习4. 归并将新知识加入知识库。学习系统往往是非单调系统，新知识加入知识库时，需要检查并保证知识的相容性。5. 评价实用化过程得到的新知识往往只是假设，要经过验证和修改，即需要进行评价。如果评价中发现了问题，就需要进行间题分析和知识库修改。实用化是整个学习过程的核心。15类比学习类比学习(Learning by Analogy)是获取新概念或新技巧的方法
8、，它把类似这些新概念或新技巧的已知知识转换为适于新情况的形式。类比学习的第一步是从记忆中找到类似的概念或技巧，第二步是把它们转换为新形式以便用于新情况。例如人类的一种学习方式是先由老师教学生解例题(先例)，再给学生留习题。学生寻找在例题和习题间的对应关系，利用解决例题的知识去解决习题中的问题。学生经过一般化归纳推出原理，以便以后使用。这种类比学习方式是人类常用的。16归纳学习归纳学习的定义（1）归纳（induction）是人类拓展认识能力的重要方法，是一种从个别到一般的，从部分到整体的推理行为。（2）归纳推理是应用归纳方法，从足够多的具体事例中归纳出一般性知识，提取事物的一般规律；它是一种从个
9、别到一般的推理。（3）归纳学习（induction learning）是应用归纳推理进行学习的一种方法。根据归纳学习有无教师指导，可把它分为示例学习和观察与发现学习。前者属于有导师学习，后者属于无导师学习。17归纳学习示例学习示例学习(Learning From Examples)，也叫做实例学习，从例子中学习。实例学习是典型的归纳学习，是目前较成熟的学习方法之一。实例学习能从环境获取一些关于某个概念的实例，实例由老师准备好，并根据需要划分为正例和反例，学习系统根据这些实例进行归纳推理，得出关于这个概念的一般性规则(知识)。提供给系统的实例通常是非常具体的、低级的信息，系统经过学习环节归纳出概
10、括的、高水平的信息，即规则(知识)，并能使用学到的知识指导以后的执行行为。18归纳学习示例学习例如，如果我们用一批动物作为实例，并且告诉学习系统哪一个动物是“马”，哪一个动物不是，当实例足够多时，学习系统就能一般出关于“马”的概念模型，使自己能识别马，并且能把马与其它动物区别开来，这一学习过程就是实例学习。Simon和Lea 1974年提出实例学习的两空间模型：例子空间和规则空间19归纳学习观察与发现学习观察发现学习又称为描述性概括，其目标是确定一个定律或理论的一般性描述，刻画观察集，指定某类对象的性质。观察发现学习可分为观察学习与机器发现两种。前者用于对事例进行聚类，形成概念描述；后者用于发
11、现规律，产生定律或规则。20归纳学习观察与发现学习概念聚类概念聚类就是一种观察学习；人类观察周围的事物，对比各种物体的特性，把它们划分成动物、植物和非生物，并给出每一类的定义。这种把观察的事物划分成几类并建立相应概念的过程就是概念聚类。发现学习发现学习是由系统的初始知识和观察的数据学习数学、物理和化学等方面的概念和规律。它也使用归纳推理，但是在学习过程中除了初始知识外施教者不进行指导，所以它也是无导师的归纳学习。21基于解释的学习基于解释学习(ExplanationBased Learning)：通过运用相关的领域知识及一个训练实例，对某个目标概念进行学习，最终得到这个目标概念的一般描述(形式
12、化表示的一般知识)。22基于解释的学习提出基于解释学习的动因：(1)人们经常能从观察或执行的单个实例中得到一个一般性的概念或规则(2)归纳学习是人类常用的学习方法，但由于归纳方法在学习中，靠领域知识来帮助分析、判断实例的的属性，仅仅通过实例间的比较来提取共性，这是无法保证推理的正确性的原因之一。而基于解释学习在学习过程中运用领域知识对实例进行分析、解释从而避免类似问题的发生。(3)由于基于解释学习只需要一两个实例，有望提高学习的效率。232. 基于学习方式的分类基于学习方式的分类（1）有导师学习（监督学习）：有导师学习（监督学习）：输入数据中有导师信号，以概率函数、代数函数或人工神经网络为基函
13、数模型，采用迭代计算方法，学习结果为函数。（2）无导师学习（非监督学习）：无导师学习（非监督学习）：输入数据中无导师信号，采用聚类方法，学习结果为类别。典型的无导师学习有发现学习、聚类、竞争学习等。（3）强化学习（增强学习）：强化学习（增强学习）：以环境反馈（奖/惩信号）作为输入，以统计和动态规划技术为指导的一种学习方法。243. 基于数据形式的分类基于数据形式的分类（1）结构化学习结构化学习：以结构化数据为输入，以数值计算或符号推演为方法。典型的结构化学习有神经网络学习、统计学习、决策树学习、规则学习。（2）非结构化学习非结构化学习：以非结构化数据为输入，典型的非结构化学习有类比学习、案例学
14、习、解释学习、文本挖掘、图像挖掘、Web挖掘等。25 4. 基于学习目标的分类基于学习目标的分类 （1）概念学习概念学习：即学习的目标和结果为概念，或者说是为了获得概念的一种学习。典型的概念学习有示例学习。 （2）规则学习规则学习：即学习的目标和结果为规则，或者说是为了获得规则的一种学习。典型的规则学习有决策树学习。 （3）函数学习函数学习：即学习的目标和结果为规则，或者说是为了获得函数的一种学习。典型的函数学习有神经网络学习。 （4）类别学习类别学习：即学习的目标和结果为对象类，或者说是为了获得类别的一种学习。典型的类别学习有聚类分析。 （5）贝叶斯网络学习贝叶斯网络学习：即学习的目标和结果
15、是贝叶斯网络，或者说是为了获得贝叶斯网络的一种学习。其又可分为结构学习和参数学习。262 知识发现与数据挖掘数据挖掘（Data Mining）从大量的、不完全的、有噪声的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在有用的信息和知识的过程。与之相似的概念称为知识发现。知识发现（Knowledge Discovery in Databases）是用数据库管理系统来存储数据，用机器学习的方法来分析数据，挖掘大量数据背后隐藏的知识，称为数据库中的知识发现。27Data Mining: A KDD ProcessData miningcore of knowledge
16、discovery process（数据挖掘知识挖掘的核心）Data Cleaning数据清洗数据清洗Data Integration（数据集成）（数据集成）Databases（数据库）（数据库）Data Warehouse数据仓库数据仓库Task-relevant Data任务相关数据任务相关数据Selection选择选择Data Mining数据挖掘数据挖掘Pattern Evaluation模式评估模式评估28Steps of a KDD Process了解应用领域创建目标数据集:选择数据数据清理和预处理:(这个可能要占全过程60%的工作量)数据缩减和变换选择数据挖掘的功能选择挖掘算法数
17、据挖掘:寻找感兴趣的模式模式评估和知识表示运用发现的知识29数据挖掘功能数据挖掘任务有两类： 第一类是描述性挖掘任务：刻划数据库中数据的一般特性； 第二类是预测性挖掘任务：在当前数据上进行推断，以进行预测。30概念 / 类描述：特征化和区分概念 / 类描述 (class / concept description)：用汇总的、简洁的、精确的方式描述每个类和概念。数据特征化 (data characterization) ：是目标类数据的一般特征或特性的汇总。其中数据特征的输出形式有：饼图、条图、曲线、多维数据立方体、多维表等。数据区分 (Data discrimination) ：是将目标类对
18、象的一般特性与一个或多个对比类对象的一般特性比较。31关联分析（1）定义：关联分析 (association analysis)：发现关联规则，这些规则展示“属性值”频繁地在给定数据集中一起出现的条件。（2）实例 age(x, “20.29”) income(X, “20K.29K”) buys(X, “CD_player”) support = 2%, confidence = 60%Diaper Beer 0.5%, 75%32分类和预测（1）定义分类 (classification)：通过构造模型(或函数)用来描述和区别类或概念，用来预测类型标志未知的对象类。（2）分类模型的导出方式分类
19、规则（IF-THEN）、决策树、数学公式、神经网络等。33聚类分析（1）定义聚类 (clustering)：将类似的数据归类到一起，形成一个新的类别进行分析。（2）聚类或分组的原则“最大化类内的相似性、最小化类间的相似性”对象的簇（聚类）的形成办法为：使得在一个簇中的对象具有很高的相似性，而与其它簇中的对象很不相似。所形成的每个簇可以看作一个对象类，由它可以导出规则。3411 August 2024Data Mining: Concepts and Techniques35分类分类一个两步的过程一个两步的过程Step 1: 建立描述预先定义的数据类或概念集的分类器假设每一元组/样本属于一个预定
20、的类,由一个类标号属性的属性确定用来建立模型的元组集被称为训练样本集模型可用分类规则,决策树或数学公式表示Step 2:模型的使用: : 为了分类将来或未知的对象评估模型的准确性对于每个测试样本, ,将已知的的类标号和该样本的模型分类结果进行比较准确率是正确被模型分类的测试样本的百分比测试集独立于样本集, ,否则会出现过分适合的现象3511 August 2024Data Mining: Concepts and Techniques36分类过程分类过程(1):建立模型建立模型训练数据分类算法IF rank = professorOR years 6THEN tenured = yes 分类规
21、则(模型)3611 August 2024Data Mining: Concepts and Techniques37分类过程分类过程(2):使用模型进行分类使用模型进行分类分类规则训练数据新数据(Jeff, Professor, 4)Tenured?37用决策树归纳分类用决策树归纳分类决策树一个类似于流程图的数结构内部节点表示一个属性上的测试每个分支代表一个测试的输出叶结点代表类或类分布决策树的生成包括两个过程树的建构首先所有的训练样本都在根结点基于所选的属性循环的划分样本树剪枝识别和删除哪些反应映噪声或孤立点的分支决策树的使用:为一个未知的样本分类在决策树上测试样本的属性值11 Augus
22、t 2024Data Mining: Concepts and Techniques383811 August 2024Data Mining: Concepts and Techniques39训练数据集训练数据集This follows an example of Quinlans ID3 (Playing Tennis)3911 August 2024Data Mining: Concepts and Techniques40概念概念“buys_computer”的决策树的输出的决策树的输出age?overcaststudent?credit rating?40noyesyesyes31
23、.40nofairexcellentyesno4011 August 2024Data Mining: Concepts and Techniques41决策树归纳的算法决策树归纳的算法基本算法以自顶向下递归的各个击破方式构造决策树首先, ,所有的训练样本都在根结点所有属性都是分类的( (如果值是连续的, ,它们应预先被离散化) )基于所选属性递归的划分样本在启发式或统计度量的基础上选择测试属性( (例如, ,信息增益) )停止划分的条件给定节点的所有样本属于同一个类没有剩余属性可以用来进一步划分样本- -使用多数表决来分类叶节点没有剩余的样本41属性选择度量属性选择度量信息增益(ID3/C4
24、.5)所有的属性值被假定为分类的修正后可以用在连续值属性上Giniindex (IBM IntelligentMiner)所有的属性被假定为连续值假定对每个属性存在一些可能的分裂(split)值需要一些其他的工具,像聚类,来得到可能的分裂值修正后可以用在分类属性上4211 August 2024Data Mining: Concepts and Techniques43信息增益信息增益(ID3/C4.5)n选择具有高信息增益的属性n假定有两个类,P和Nn假定样本集S包含类P的p个元素和类N的n个元素n如果S中任意的例子属于P或N，则需要决定的信息数量被定义为43决策树归纳的信息增益决策树归纳的
25、信息增益假设用属性A将集合S被划分为V个子集S1, S2, , Sv 如果Si包含P中的pi个样本和N中的ni个样本, 则熵, 或所有用来分类所有子树Si中对象的期望信息由以下式给出：由A上分支将获得编码信息4411 August 2024Data Mining: Concepts and Techniques45Attribute Selection: Information Gaing类 P: buys_computer = “yes”g类 N: buys_computer = “no” means “age =30” has 5 out of 14 samples, with 2 yes
26、es and 3 nos. HenceSimilarly,4511 August 2024Data Mining: Concepts and Techniques46贝叶斯定理: Basics设 X 是数据样本 (“证据”): 类标号未知令 H 为X属于类C的某种假设分类就是确定P(H|X)给定“证据”或观察数据元组X，假设H成立的概率P(H) (先验概率), the initial probabilityE.g., X will buy computer, regardless of age, income, P(X): X的先验概率P(X|H) (后验概率), 假设H成立的条件下，观察数据
27、样本X后验概率E.g., Given that X will buy computer, the prob. that X is 31.40, medium income4611 August 2024Data Mining: Concepts and Techniques47贝叶斯定理Given training data X, posteriori probability of a hypothesis H, P(H|X), follows the Bayes theorem如果概率P(Ci|X) 是K类的所有P(Ck|X)中最高的，则可预测 X 属于 Ci4711 August 2024
28、Data Mining: Concepts and Techniques48朴素贝叶斯分类设D是训练元组和相关联的类标号的集合。每个元组用一个n维属性向量 X = (x1, x2, , xn)表示假定有m个类 C1, C2, , Cm.分类法将预测X属于具有最高后验概率（条件X下）的类, i.e., 最大化 P(Ci|X)根据贝叶斯定理由于 P(X) 对于所有类为常数, 只需要 最大即可4811 August 2024Data Mining: Concepts and Techniques49朴素贝叶斯分类 朴素假定: 假定属性值有条件地相互独立 (i.e., 属性间不存在依赖关系):这大大减
29、少了计算开销，如果 Ak 是分类属性, 则P(xk|Ci) 是D中属性Ak的值为xk 的Ci类的元组除以D中Ci类的元组数|Ci, D|4911 August 2024Data Mining: Concepts and Techniques50朴素贝叶斯分类: 训练集Class:C1:buys_computer = yesC2:buys_computer = noData sample X = (age =30,Income = medium,Student = yesCredit_rating = Fair)5011 August 2024Data Mining: Concepts and
30、Techniques51Nave Bayesian Classifier: An ExampleP(Ci): P(buys_computer = “yes”) = 9/14 = 0.643 P(buys_computer = “no”) = 5/14= 0.357Compute P(X|Ci) for each class P(age = “=30” | buys_computer = “yes”) = 2/9 = 0.222 P(age = “= 30” | buys_computer = “no”) = 3/5 = 0.6 P(income = “medium” | buys_comput
31、er = “yes”) = 4/9 = 0.444 P(income = “medium” | buys_computer = “no”) = 2/5 = 0.4 P(student = “yes” | buys_computer = “yes) = 6/9 = 0.667 P(student = “yes” | buys_computer = “no”) = 1/5 = 0.2 P(credit_rating = “fair” | buys_computer = “yes”) = 6/9 = 0.667 P(credit_rating = “fair” | buys_computer = “
32、no”) = 2/5 = 0.4 X = (age = 30 , income = medium, student = yes, credit_rating = fair) P(X|Ci) : P(X|buys_computer = “yes”) = 0.222 x 0.444 x 0.667 x 0.667 = 0.044 P(X|buys_computer = “no”) = 0.6 x 0.4 x 0.2 x 0.4 = 0.019P(X|Ci)*P(Ci) : P(X|buys_computer = “yes”) * P(buys_computer = “yes”) = 0.028 P
33、(X|buys_computer = “no”) * P(buys_computer = “no”) = 0.007Therefore, X belongs to class (“buys_computer = yes”)5111 August 2024Data Mining: Concepts and Techniques52什么是聚类分析?聚类（簇）：数据对象的集合在同一个聚类（簇）中的对象彼此相似不同簇中的对象则相异聚类分析将物理或抽象对象的集合分组成为由类似的对象组成的多个类的过程聚类是一种无指导的学习：没有预定义的类编号聚类分析的数据挖掘功能作为一个独立的工具来获得数据分布的情况作为
34、其他算法（如：特征和分类）的预处理步骤5211 August 2024Data Mining: Concepts and Techniques53主要聚类方法 (I)划分算法（Partitioning approach ）构造各种各样的划分,并用一些标准来评估它们Typical methods: k-means, k-medoids, CLARANS层次算法（Hierarchical approach ）: 使用一些策略来进行数据(或对象)集的层次分解Typical methods: Diana, Agnes, BIRCH, ROCK, CAMELEON基于密度的方法（ Density-bas
35、ed approach）基于连续和密度函数Typical methods: DBSACN, OPTICS, DenClue5311 August 2024Data Mining: Concepts and Techniques54主要聚类方法(II)基于网格的方法（Grid-based approach ） :基于多层粒度结构Typical methods: STING, WaveCluster, CLIQUE基于模型的方法（Model-based ） :为每个聚类假设一个模型,寻找数据对给定模型的最佳拟合Typical methods: EM, SOM, COBWEB基于频繁模式的方法（Fr
36、equent pattern-based ） :Based on the analysis of frequent patternsTypical methods: pCluster用户指导或基于约束的方法 （ User-guided or constraint-based ） :结合用户指定和面向应用的约束进行聚类的方法Typical methods: COD (obstacles), constrained clustering5411 August 2024Data Mining: Concepts and Techniques55划分算法:基本概念划分方法:把具有n个对象的数据库D构造
37、成具有k个簇的集合的划分给定k，找出有k个簇的一个划分使得所选择的划分准则最优全局最优: 穷举所有可能的划分启发式方法: k-平均算法和k-中心点算法k-平均算法（ k-means ）(MacQueen67): 每个簇用簇的中心表示k-中心点算法（k-medoids）或围绕中心点的划分PAM (Partition around medoids) (Kaufman & Rousseeuw87): 每一个簇用接近聚类中心的一个对象表示5511 August 2024Data Mining: Concepts and Techniques56K-平均聚类算法给定k, k-平均算法由以下四步来完成:把
38、对象划分为k个非空的子集随机的选择一些种子点作为目前划分的簇的质心。质心是簇的中心（平均点）把每一个对象赋给最近的种子点重复第二步，直到没有新的分配5611 August 2024Data Mining: Concepts and Techniques57K-平均聚类方法Example012345678910012345678910012345678910012345678910K=2Arbitrarily choose K object as initial cluster centerAssign each objects to most similar centerUpdate the cluster meansUpdate the cluster meansreassignreassign57
