数据挖掘算法.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据挖掘算法,Wang Ye 2006.8,一、概念和术语,1.1,数据挖掘,/,知识发现,（,1,）,数据挖掘,是从存放在数据集中的大量数据挖掘出有趣知识的过程。,（,2,）数据挖掘，又称为,数据库中知识发现,（,Knowledge Discovery in Databases,）或,知识发现,，它是一个从大量数据中抽取挖掘出未知的、有价值的模式或规律等知识的非平凡过程，它与数据仓库有着密切的联系。,（,3,）广义的数据挖掘是指知识发现的全过程；狭义的数据挖掘是指统计分析、机器学习等发现数据模式的智能方法，即偏重于模型和算法。,（,4,）数据库查询系统和专家系统,不是,数据挖掘！在小规模数据上的统计分析和机器学习过程也不应算作数据挖掘。,1.2,机器学习,（,1,）对于某类任务,T,和性能度量,P,，如果一个计算机程序在,T,上以,P,衡量的性能随着经验,E,而自我完善，那么这个计算机程序被称为在从经验,E,学习。,（,2,）机器学习是知识发现的一种方法，是指一个系统通过执行某种过程而改进它处理某一问题的能力。,1.3,数据挖掘的对象,（,1,）关系型数据库、事务型数据库、面向对象的数据库；,（,2,）数据仓库,/,多维数据库；,（,3,）空间数据（如地图信息）,（,4,）工程数据（如建筑、集成电路的信息）,（,5,）文本和多媒体数据（如文本、图象、音频、视频数据）,（,6,）时间相关的数据（如历史数据或股票交换数据）,（,7,）万维网（如半结构化的,HTML,，结构化的,XML,以及其他网络信息）,1.4,数据挖掘的步骤,（,1,）数据清理（消除噪音或不一致数据，补缺）；,（,2,）数据集成（多种数据源可以组合在一起）；,（,3,）数据选择（从数据库中提取相关的数据）；,（,4,）数据变换（变换成适合挖掘的形式）；,（,5,）数据挖掘（使用智能方法提取数据模式）；,（,6,）模式评估（识别提供知识的真正有趣模式）；,（,7,）知识表示（可视化和知识表示技术）。,1.5,支持数据挖掘的关键技术,（,1,）数据库,/,数据仓库,/OLAP,（,2,）数学,/,统计（回归分析：多元回归、自回归；判别分析：,Bayes,判别、,Fisher,判别、非参数判别；主成分分析、相关性分析；模糊集；粗糙集）,（,3,）机器学习（聚类分析；关联规则；决策树；范例推理；贝叶斯网络；神经网络；支持向量机；遗传算法）,（,4,）可视化：将数据、知识和规则转化为图形表现的形式。,1.6,数据仓库,（,1,）,数据仓库,是一个面向主题的、集成的、随时间变化的、非易失性数据的集合，用于支持管理人员的决策。,（,2,）数据仓库是一种多个异种数据源在单个站点以统一的模式组织的存储，以支持管理决策。数据仓库技术包括数据清理、数据集成和,联机分析处理,（,OLAP,）。,（,3,）数据仓库的逻辑结构是多维数据库。数据仓库的实际物理结构可以是关系数据存储或,多维数据方,（,Cube,）。,（,4,）数据方是由,维度,（,Dimension,）和,度量,（,Measure,）定义的一种数据集，度量存放在由维度索引的数据方单元中。维度对应于模式中的属性组，度量对应于与主题相关的事实数据。数据方的,物化,是指预计算并存储全部或部分单元中的度量。,1.7,数据仓库的模型,（,1,）,星形模式,：最常见模型；其中数据仓库包括一个大的、包含大批数据、不含冗余的中心表（事实表）；一组小的附属表（维表），每维一个。,（,2,）,雪花模式,：雪花模式是星型模式的变种，其中某些维表是规范化的，因而把数据进一步分解到附加的表中。,（,3,）,星系模式,：多个事实表共享维表。这种模式可以看作星形模式集，因此称为星系模式，或事实星座。,1.8,典型的,OLAP,操作,（,1,）,OLAP,是一种多维数据分析技术。包括汇总、合并和聚集等功能，以及从不同的角度观察信息的能力。,（,2,）,上卷,：从某一维度的更高概念层次观察数据方，获得更概要的数据。它通过沿维的概念分层向上或维归约来实现。,（,3,）,下钻,：下钻是上卷的逆操作。它从某一维度的更低概念层次观察数据方，获得更详细的数据。下钻可以通过沿维的概念分层向下或引入新的维来实现。,（,4,）,切片和切块,：切片操作在给定的数据方的选择一个维的部分属性，获得一个较小的子数据方。切块操作通过对选择两个或多个维的部分属性，获得一个较小的子数据方。,（,5,）,转轴,：是一种改变数据方二维展现形式的操作。它将数据方的二维展现中的某些维度由行改为列，或由列改为行。,二、数据准备,现实世界的数据是,不完整的,（有些感兴趣的属性缺少属性值，或仅包含聚集数据），,含噪音的,（包含错误，或存在偏离期望的异常值），,不一致的,（例如，用于商品分类的部门编码存在差异）。,需要,数据清理,、,数据集成,、,数据选择,、,数据变换,等技术对数据进行处理。,2.1,维归约,/,特征提取,2.1-1,决策树归约,（,1,）决策树归约构造一个类似于流程图的结构：其每个非叶子结点表示一个属性上的测试，每个分枝对应于测试的一个输出；每个叶子结点表示一个决策类。,（,2,）在每个结点，算法选择“当前对分类最有帮助”的属性，出现在树中的属性形成归约后的属性子集。,2.1-2,粗糙集归约,（,1,）粗糙集理论在数学意义上描述了知识的不确定性，它的特点是把用于分类的知识嵌入集合内，使分类与知识联系在一起。,（,2,）知识的粒度、不可分辨关系、上近似、下近似、边界等概念见下图。,2.1-2,粗糙集归约（续）,（,3,）令,Q,代表属性的集合。,q,Q,是一个属性，如果,IND,(,Q,q,)=,IND,(,Q,),，则,q,在,S,中不是独立的；否则称,q,在,S,中是独立的。,（,4,）若集合满足,IND,(,R,)=,IND,(,Q,),且,R,中的每一个属性都是独立的，则,R,被称为,Q,的一个“约简”，记作,R,=,RED,(,Q,),。,（,5,）约简可以通过删除冗余的（不独立的）属性而获得，约简包含的属性即为“对分类有帮助”的属性。,2.2,数据变换,2.2-1,归一化与模糊化,有限区间的归一化：,无限区间的归一化：,模糊隶属度：,2.2-2,核函数,（,1,）核函数的基本思想是将在,低维特征向量线性不可分,的数据映射到线性可分的,高维特征空间,中去。,（,2,）映射可以是显式的，也可以是隐式的。显式映射即找到一个映射关系,f,，使高维空间的特征向量,f,(,x,),可以被直接计算出来。,（,3,）隐式映射，即引入一个核函数进行整体处理，就避免了对的直接求,f,(,x,),的计算困难。,核函数,即某高维特征空间中向量的内积，是核矩阵中的一个元素。,（,4,）并不是所有的实值函数,f,(,x,),都可以作为空间映射的核函数，只有,f,(,x,),是某一特征空间的内积时，即符合,Mercer,条件,，它才能成为核函数。,2.2-2,核函数（续）,多项式函数：,高斯（,RBF,）函数：,多层感知机函数：,低维空间向量映射到高维空间向量举例：,2.3,数据压缩,2.3-1,离散化,离散化的用途,：（,1,）适应某些仅接受离散值的算法；（,2,）减小数据的尺度。,离散化的方法包括几下几种。,（,1,）等距分割；,（,2,）聚类分割；,（,3,）直方图分割；,（,4,）基于熵的分割；,（,5,）基于自然属性的分割。,2.3-2,回归,回归和对数线性模型可以用来近似给定的数据。,在,线性回归,中，用一条直线来模拟数据的生成规则。,多元回归,是线性回归的扩展，涉及多个预测变量。,在,多项式回归,中，通过对变量进行变换，可以将非线性模型转换成线性的，然后用最小平方和法求解。,2.3-2,回归（续）,利用线性回归可以为连续取值的函数建模。广义线性模型则可以用于对离散取值变量进行回归建模。,在广义线性模型中，因变量,Y,的变化速率是,Y,均值的一个函数；这一点与线性回归不同。常见的广义线性模型有：对数回归和泊松回归。,对数回归模型,是利用一些事件发生的概率作为自变量所建立的线性回归模型。,泊松回归模型,主要是描述数据出现次数的模型，因为它们常常表现为泊松分布。,2.3-3,主成分分析（,PCA,）,PCA,算法搜索,c,个最能代表数据的,k-,维正交向量；这里,c,k,。这样，原来的数据投影到一个较小的空间，导致数据压缩。步骤如下：,（,1,）对输入数据归一化，使得每个属性都落入相同的区间。,（,2,）,PCA,计算,c,个规范正交向量，作为归一化输入数据的基。这些是单位向量，每一个都垂直于另一个：称为主成分。输入数据是主要成分的线性组合。,（,3,）对主成分按“意义”或强度降序排列，选择部分主成分充当数据的一组新坐标轴。,2.3-4,离散小波变换（,DWT,）,离散小波变换是一种线性,信号处理技术,。该技术方法可以将一个数据向量转换为另一个数据向量（为小波相关系数）；且两个向量具有相同长度。,可以舍弃转换后的数据向量中的一些小波相关系数。保留所有大于用户指定阈值的小波系数，而将其它小波系数置为,0,，以帮助提高数据处理的运算效率。,这一技术方法可以在保留数据主要特征情况下除去数据中的噪声，因此该方法可以有效地进行数据清洗。,给定一组小波相关系数，利用离散小波变换的逆运算还可以近似恢复原来的数据。,2.3-4,离散小波变换（续）,常用的小波函数包括,Haar,系列,Daubechies,系列，,Moret,系列，,Sym,系列，,Meyer,系列，,Coif,系列。,2.3-5,潜在语义分析,潜在语义分析将样本映射到语义概念空间以发现样本数据之间的潜在语义联系。,（,1,）构造“特征,-,样本”矩阵，“特征,-,样本”矩阵中的每一列是对应于第,i,个样本特征向量；,（,2,）对该矩阵进行奇异值分解,(SVD),；,（,3,）用最大的,k,个奇异值所对应的“特征,-,语义”矩阵,U,k,和“样本,-,语义”矩阵,Vk,以及最大的,k,个奇异值重构“特征,-,样本”矩阵。,下面两式分别代表在语义空间特征与特征之间的距离和,在语义空间,样本与样本之间的距离,2.3-6,聚类分析,聚类技术将数据元组视为对象。它将对象划分为聚类，使在一个聚类中的对象“类似”，但与其它聚类中的对象“不类似”。,通常，,类似性基于距离,，用对象在空间中的“接近”程度定义。聚类的“质量”可以用“直径”表示；而直径是一个聚类中两个任意对象的最大距离。,质心距离是聚类质量的另一种度量，它定义为由聚类质心（表示“平均对象”，或聚类空间中的平均点）到每个聚类对象的平均距离。,2.3-6,聚类分析（续）,k-means,算法,k-medoids,算法,三、数据挖掘算法,数据挖掘算法按挖掘目的可分为：,（,1,）,概念描述,（总结，对比等）,（,2,）,关联规则分析,（,3,）,分类与预测,（信息自动分类，信息过滤，图像识别等）,（,4,）,聚类分析,（,5,）,异常分析,（入侵检测，金融安全等）,（,6,）,趋势、演化分析,（回归，序列模式挖掘）,按训练方式，机器学习可分为：,（,1,）,有监督的学习,；有训练样本，学习机通过学习获得训练样本包含的知识，并用其作为判断测试样本的类别的依据。,（,2,）,无监督的学习,：无训练样本，仅根据测试样本的在特征空间分布情况判断其类别。,（,3,）,半监督的学习,：有少量训练样本，学习机以从训练样本获得的知识为基础，结合测试样本的分布情况逐步修正已有知识，并判断测试样本的类别。,（,4,）,强化学习,：没有训练样本，但有对学习机每一步是否更接近目标的奖惩措施。,有监督的学习,半监督的学习,无监督的学习,3.1,关联规则挖掘,关联规则挖掘发现大量数据中项集之间有趣的关联或相关联系。设,I,=,i,1,i,2,.,i,m,是项的集合。设任务相关的数据,D,是数据库事务的集合，其中每个事务,T,是项的集合，使得,T,I,。设,A,是一个项集，事务,T,包含,A,当且仅当,A,T,。,关联规则,是形如,A,B,的蕴涵式，其中,A,I,，,B,I,，并且,A,B,=,。规则,A,B,在事务集,D,中成立，具有支持度,s,，其中,s,是,D,中事务包含,A,B,的百分比。即，,P,(,A,B),。,规则,A,B,在事务集,D,中具有置信度,c,，如果,D,中包含,A,的事务同时也包含,B,的百分比是,c,。这是条件概率,P,(,B|A,),。即,support,(,A,B,)=,P,(,A,B),confidence,(,A,B,)=,P,(,B|A,),3.1,关联规则挖掘（续）,Apriori,性质,：频繁项集的所有非空子集都必须也是频繁的。,Apriori,性质基于如下观察：根据定义，如果项集,I,不满足最小支持度阈值,s,，则,I,不是频繁的，即,P,(,I,),s,。如果项,A,添加到,I,，则结果项集（即,I,A,）不可能比,I,更频繁出现。因此，,I,A,也不是频繁的，即,P,(,I,A,),s,。,该性质表明如果一个集合不能通过测试，则它的所有超集也都不能通过相同的测试。,将,Apriori,性质应用于算法：下面算法的两个主要步过程由,连接,和,剪枝,组成。,3.1,关联规则挖掘（续）,连接步,：为找,L,k,，通过,L,k,-1,与自己连接产生候选,k,-,项集的集合。该候选项集的集合记作,C,k,。,C,k,是,L,k,的超集。扫描数据库，确定,C,k,中每个候选的计数，将令计数值不小于最小支持度计数的（频繁的）所有候选加入,L,k,。,剪枝步,：,但,C,k,可能很大，这样所涉及的计算量就很大。根据,Apriori,性质,如果一个候选,k,-,项集的,(,k,-1)-,子集不在,L,k-1,中，则该候选也不可能是频繁的，从而可以由,C,k,中删除。,Apriori,性质,(,逆反描述,),：任何非频繁的,(,k,-1)-,项集都不是可能是频繁,k,-,项集的子集。,3.2,决策树,决策树学习是归纳推理算法。它是一种逼近离散函数的方法，且对噪声数据有很好的健壮性。在这种方法中学习到的知识被表示为决策树，决策树也能再被表示为多个,if-then,的规则，以提高可读性。,基本决策树算法就是一个,贪心算法,。它采用自上而下、分而制之的递归方式来构造一个决策树,通常，决策树是一种自顶向下增长树的贪婪算法，在每个结点选取能最好地分类样例的属性。继续这个过程直到这棵树能完美分类训练样例，或所有的属性都使用过了。“信息增益”用于衡量属性的价值。熵（,entropy,）是一种度量信息增益的指标，它描述了样本的纯度（,purity,）。下面是熵的定义：,Entropy=-P,i,log2P,i,3.2,决策树（续）,注意点：,（,1,）避免过度拟合，应该适度剪枝；（,2,）连续值的离散化；（,3,）处理缺失值的方法：最常见值、按概率分配；（,4,）处理权重不同的属性,常用实现算法：,CART,、,ID3,、,ASSISTANT,、,C4.5,3.3,人工神经网络,人工神经网络（,Artificial Neural Networks,）提供了一种普遍而且实用的方法，来从样例中学习值为实数、离散或向量的函数。,反向传播（,Back Propagation,）这样的算法使用梯度下降来调节网络参数以最佳拟合由输入,/,输出对组成的训练集合。,BP,网络的,学习方法和目标：对网络的连接权值进行调整，使得对任一输入都能得到所期望的输出。,常用的非线性作用函数是,Sigmoid,函数,，即,f,(,x,)=1/(1+,e,-x,),。在神经网络模型中，大量神经元节点按一定体系结构连接成网状。神经网络一般都具有输入层，隐层和输出层。,每个神经元都是一个结构相似的独立单元，它接受前一层传来的数据，并将这些数据的加权和输入非线性作用函数中，最后将非线性作用函数的输出结果传递给后一层。,误差反向传播的过程,3.3,人工神经网络（续）,自适应共振理论模型,(ART),聚类,连续,/,离散,Hopfield,神经网络,求近似最优解，识别与分类,双向联想记忆模型,(BAM),识别,玻尔兹曼机,(BM),求最优解,脑中盒模型,(BSB),识别与分类,自组织映射模型,(SOM),识别与分类,对向传播网络模型,(CPN),识别与分类,小脑模型,(CMAC),快速识别,3.4,朴素贝叶斯（,Naive,Bayes,）分类器,朴素贝叶斯分类器是一种基于贝叶斯理论的分类器。它的特点是以概率形式表达所有形式的不确定，学习和推理都由概率规则实现，学习的结果可以解释为对不同可能的信任程度。,P(H),是,先验概率,，或,H,的先验概率。,P(H|X),是,后验概率,，或条件,X,下，,H,的后验概率。后验概率,P(H|X),比先验概率,P(H),基于更多的信息。,P(H),是独立于,X,的。,假定数据样本世界由水果组成，用它们的颜色和形状描述。假定,X,表示红色和圆的，,H,表示假定,X,是苹果，则,P(H|X),反映当我们看到,X,是红色并是圆的时，我们对,X,是苹果的确信程度。,朴素贝叶斯分类能够奏效的前提是，,P(X|H),相对比较容易计算。假定,X,表示红色和圆的，,H,表示假定,X,是苹果；则,P(X|H),表示已知苹果，它既红又圆的概率。,3.5,期望最大化（,EM,）,期望最大化（,EM,）方法和朴素贝叶斯方法有着共同的理论基础。期望最大化是一种基于循环过程的最大似然参数估计方法，用于解决带缺失数据的参数估计问题。,样本数据分为标记样本和未标记样本，按照统计的观点，对于每一个样本的产生，其背后都有一个模型，即,样本生成模型,。样本生成模型的参数先由标记样本确定，再通过标记样本和利用当前模型判断标记的未标记样本共同调整。,3.5,期望最大化（续）,如果参数适当，,EM,算法能得到较好的分类结果，但计算速度相对较慢。其具体的步骤如下：,一、初始参数估计，将未标记的样本按朴素贝叶斯分类方法进行类标注。,二、反复迭代,E,步骤和,M,步骤，直到收敛。,三、,E,步骤：对于每个未标记的样本，按下式计算类标记的期望值。,四、,M,步骤：利用,E,步骤计算出的期望值，按下式用已标记样本和未标记样本重新估计新的分类器参数。,3.6 K-,最近邻分类,K-,近邻（,K-NN,）分类是,基于范例,的分类方法，它的基本思想是：给定待分类样本后，考虑在训练样本集中与该待分类样本距离最近（最相似）的,K,个样本，根据这,K,个样本中大多数样本所属的类别判定待分类样本的类别。,它的特例是,1-NN,，即分类时选出待分类样本的最近邻，并以此最近邻的类标记来判断样本的类。,K-NN,算法的优点在于它有较高的精确程度，研究表明，,K-NN,的分类效果要明显好于朴素贝叶斯分类、决策树分类。,3.6 K-,最近邻分类（续）,最近邻分类的算法步骤如下：,一、以向量空间模型的形式描述各训练样本。,二、在全部训练样本集中选出与待分类样本最相似的,K,个样本。,K,值的确定目前没有很好的方法，一般采用先定一个,100,左右的初始值，然后再调整。,三、将待分类样本标记为其,K,个邻居中所属最多的那个类别中。,3.7,遗传算法,遗传算法易于并行处理，其依据是自然界进化和适者生存的原则。遗传学习开始如下：创建若干个由随机产生的个体组成的初始,群体,。每个个体用一个二进位串表示。,形成由当前群体中最适合的个体组成新的群体，以及这些规则的子女。个体的,适合度,用某一目标函数来评估。,子女通过使用诸如交叉和变异等遗传操作来创建。在,交叉,操作中，来自个体对的子串交换，形成新的个体对。在,变异,操作中，个体中随机选择的位被反转。,3.7,遗传算法（续）,Fitness,：适应度评分函数，为给定假设赋予一个评估得分。,Fitness,_,threshold,：指定终止判据的阈值。,p,：群体中包含的假设数量。,r,：每一步中通过交叉取代群体成员的比例。,m,：变异率。,初始化群体：,P,随机产生的,p,个假设,评估：,对于,P,中的每一个,h,，计算,Fitness,(,h,),当,Fitness,(,h,),Fitness,_,threshold,，做：,产生新的一代,P,S,：,3.7,遗传算法（续）,选择：,用概率方法选择,P,的,(1-,r,),p,个成员加入,P,S,。从,P,中选择假设,hi,的概率,P(,hi,),通过下面公式计算：,交叉：,根据上面给出的,P(,h,i,),，从,P,中按概率选择,r,p,/2,对假设。对于每一对假设,应用交叉算子产生两个后代。把所有的后代加入,P,S,。,变异：,使用均匀的概率从,P,S,中选择,m,百分比的成员。对于选出的每个成员，在它的表示中随机选择一个位取反。,更新：,P,P,S,。,评估：,对于,P,中的每一个,h,计算,Fitness,(,h,),从,P,中返回适应度最高的假设。,3.8,聚类分析,为达到全局最优，基于划分的聚类会要求穷举所有可能的划分。聚类技术将数据元组视为对象。它将对象划分为群或聚类，使得在一个聚类中的对象“类似”，但与其它聚类中的对象“不类似”。,绝大多数应用采用了以下两个比较流行的,基于划分的方法,，这些基于划分的聚类方法对在中小规模的数据库中发现球状簇很适用。,（,1,）,k-means,算法,，在该算法中，每个簇用该簇中对象的平均值来表示。,（,2,）,k-medoids,算法,，在该算法中，每个簇用接近聚类中心的一个对象来表示。,3.8,聚类分析（续）,常用的相似程度度量,余弦夹角：,Dice,系数：,Jaccard,系数：,3.8,聚类分析（续）,基于层次的方法：,层次的方法对给定数据集合进行层次的分解。根据层次的分解如何形成，层次的方法可以被分为凝聚或分裂方法。（,Chameleon,，,CURE,，,BIRCH,）,基于密度的方法：,只要临近区域的密度超过某个阈值，就继续聚类。避免仅生成球状聚类。（,DBSCAN,，,OPTICS,，,DENCLUE,）,基于网格的方法：,基于网格的方法把对象空间量化为有限数目的单元，所有的聚类操作都在这个量化的空间上进行。这种方法的主要优点是它的处理速度很快。（,STING,，,CLIQUE,，,WaveCluster,）,基于模型的方法：,为每个簇假设一个模型，发现数据对模型的最好匹配。（,COBWEB,，,CLASSIT,，,AutoClass,）,3.9,隐马尔可夫模型,对于一个随机事件，有一个观察值序列：,O,1,.,O,T,。该事件隐含着一个状态序列：,X,1,.,X,T,假设,1,：马尔可夫性，,P(X,i,|X,i-1,X,1,)=,P(X,i,|X,i-1,),假设,2,：不动性，,P(X,i+1,|X,i,)=P(X,j+1,|,X,j,),，对任意,i,j,成立,假设,3,：输出独立性，,P(O,1,.,O,T,|X,1,.,X,T,)=,P(O,t,|,X,t,),一个隐马尔可夫模型是一个五元组：,(,X,O,A,B,),其中：,X,=Q,1,.,Q,N,：状态的有限集合；,O,=V,1,.,V,M,：观察值的有限集合；,A=,a,ij,，,a,ij,=P(X,t+1,=,Q,j,|,X,t,=,Q,i,),：转移概率；,B=,b,ik,，,b,ik,=,P(O,t,=,V,k,|,X,t,=,Q,i,),：输出概率；,=,i,，,i,=P(X,1,=,Q,i,),：初始状态分布。,3.9,隐马尔可夫模型（续）,令,=A,B,为给定,HMM,的参数，,令,=O,1,.,O,T,为观察值序列，,隐马尔可夫模型的三个基本问题：,评估问题,：对于给定模型，求某个观察值序列的概率,P(,|,),。,向前,/,向后算法,：定义向前,/,向后变量。采用动态规划算法，复杂度,O(N,2,T),解码问题,：对于给定模型和观察值序列，求可能性最大的状态序列。,Viterbi,算法,：采用动态规划算法，复杂度,O(N,2,T),学习问题,：对于给定的一个观察值序列，调整参数,，使得观察值出现的概率,P(,|,),最大。向前,EM,算法的一个特例，带隐变量的最大似然估计。,Baum-Welch,算法,。,3.9,隐马尔可夫模型（续）,向前,/,向后算法：定义向前,/,向后,变量：,初始化：,递归：,终结：,3.9,隐马尔可夫模型（续）,Viterbi,算法,初始化：,递归：,终结：,求,S,序列：,3.9,隐马尔可夫模型（续）,Baum-Welch,算法,主要步骤：,1.,初始模型（待训练模型）,l,0,2.,基于,l,0,以及观察值序列,s,，训练新模型,l,；,3.,如果,logP(X|,l,)-log(P(X|,l,0,)Delta,，,说明训练已经达到预期效果，算法结束。,4.,否则，令,l,0,l,，,继续第2步工作,3.10,支持向量机,支持向量机基本模型是针对线性可分情况下的最优分界面提出的。在这一条件下，正类和反类训练样本可用,超平面,完全正确地分开。,设线性可分样本集合为,(,x,i,y,i,),，,i,=1,n,；,x,R,d,，,y,+1,-1,是类别标记。支持向量机工作的机理可描述为：寻找一个超平面,w,x,+,b,=0,，该平面把两类训练样本点完全正确地分开，即满足 且 ；同时满足两类训练点到此超平面的最近距离之和，即“,间隔,”,(Margin),，达到最大。,满足上述条件的分界面就是,最优分界面,，经过两类样本中距离最优分类面最近的点，且平行于最优分界面的超平面,H,1,、,H,2,（边界超平面）上的训练样本称为,支持向量,，即图中带圈的点。,3.10,支持向量机（续）,根据最近距离之和最大以及正确分离两类样本这两个条件，可以构造约束极值问题：见（,1,）式。,通过拉格朗日乘数法并引入拉格朗日乘数，该约束极值问题就可以转化成一个求解较为简单的对偶问题，通过寻求该对偶问题的最优解，就可以得到原问题的最优解。构造分类器判决函数：见（,2,）式。,（,2,）式中，,sgn,(.),是取符号函数，产生,+1,或,-1,两种结果。当测试无标记的测试数据时，根据上式的计算结果就可判断无标记测试数据属于正类还是反类。,（,1,）,（,2,）,3.10,支持向量机（续）,由于噪声或其他因素的影响，两类数据可能有少数的融合或交叉。引入松弛变量,x,使得分类器在训练后仍可以存在一些错分样本，不但要使两类样本之间的间隔尽量大，同时还要使错分的样本的松弛变量之和尽可能的小，即,其中，,x,为松弛变量，满足,x,i,0,；,C,为大于零的折衷因子，它调和了间隔距离和错分样本数之间的关系，,C,趋近于无穷大时即为线性可分的形式。为了提高支持向量机的推广能力，,C,通常取为较大的数。,3.10,支持向量机（续）,解决线性不可分数据问题的方法是将低维空间的线性不可分数据映射到高维的线性可分空间中。,支持向量机通过非线性映射,f,(,x,),把数据由低维空间向高维空间映射，在高维空间为低维数据构造线性分离超平面。该分离超平面对应着原特征空间上的一个分割超曲面。,在高维特征空间上所有涉及,f,(,x,),的计算及判决函数都以,f,(,x,),的内积形式出现，因而可以引入一个核函数进行整体处理从而避免了对,f,(,x,),的直接计算，使所有的计算仍在原空间进行。,3.10,支持向量机（续）,统计学习理论认为：学习机误判未知数据类别的实际风险与学习机的训练误差并不完全一致，对于两类分类问题，实际风险与学习机的训练误差之间至少以,1-,h,的概率（,0,h,1,）满足下式：,根据统计学习的理论，对于两类分类的支持向量机，在线性可分的情况下，它的推广误差的上界（以,1-,d,的概率（,0,d,1,）保证）为：,其中，,m,是连续分类正确的样本数；,g,=1/|,w,|,，是间隔距离的一半；,R,是一个特征空间球的半径，它将全部样本包含在其中。,3.11,关系学习,关系学习所涉及的问题比传统机器学习中涉及到的问题高一个层次。该类问题的假设空间庞大，结构复杂；需要加入领域知识反映问题的内在结构。,关系学习中知识的表示：原子；析取、合取、蕴含、非；验证、等价、涵蕴等。句子由上述元素组成。,一阶,Horn,子句,：仅包含一个肯定文字的子句。,有三种类型的,Horn,子句：单一原子（事实）；一个蕴涵（规则）；一个否定文字的集合（目标）。,3.11,关系学习（续）,归纳逻辑编程,(Inductive Logic Programming,ILP),是处理关系学习领域问题的重要方法。它是归纳学习和逻辑程序结合的产物。,ILP,用于一阶逻辑的概念学习和逻辑程序的合成。,ILP,系统处理分类任务时主要采用两种方式：覆盖方法和分治方法。,子句空间,由形如：,H,L,1,L,2,L,m,的一阶子句构成。,-,包容关系,：假设,c,和,c,是两个程序子句，子句,c-,包容子句,c,如果存在一个替换,使得,cc,基于,ILP,的常用方法有：,Progol,、,FOIL,、,TLIDE,、,ICL,四、模型上的模型,4.1,装袋,/,提升,给定,s,个样本的集合,S,。,装袋,（,Bagging,）过程如下。对于迭代,t,(,t,=1,2,.,T,),，训练集,S,t,采用放回选样，由原始样本集,S,选取。,由于使用放回选样，,S,的某些样本可能不在,S,t,中，而其它的可能出现多次。,由每个训练集,S,t,学习，得到一个分类法,C,t,。为对一个未知的样本,X,分类，每个分类法,C,t,返回它的类预测，算作一票。,装袋的分类法,C,*,统计得票，并将得票最高的类赋予,X,。通过取得票的平均值，装袋也可以用于连续值的预测。,4.1,装袋,/,提升（续）,提升,（,Boosting,）过程如下：每个训练样本赋予一个权，并学习得到一系列分类法。,对于迭代,t,(,t,=1,2,.,T,),，学习得到分类法,C,t,后，更新权，使得随后的分类法,C,t+1,“,更关注,”,C,t,的分类错误。,最终的提升分类法,C,*,组合每个分类法的表决，这里每个分类法的表决是其准确率的函数。,通过取得票的平均值，提升算法也可以扩充到连续值预测。,4.2,共同训练（,Co-Training,）,共同训练算法用两个不同的“,视图,”（即特征集合）来描述文本的特征。,基本思路：每个视图对应一个学习机，而每个学习机都根据自身已学到的规律来标记“最有把握”的无标记样本，然后将这个（或这几个）新标记的样本加入训练样本，并扩展后的训练样本提供给另一个学习机进行学习。如此反复，直到满足一定的条件为止。,该算法中所用到的两个视图需要满足以下两个条件：首先，每个特征集合对文本分类学习来说都是,充分,的；其次，在给定类别标记的条件下，两个特征集合,相互独立,。,4.3,主动学习,/,被动学习,主动学习,在学习过程中可以根据学习进程，选择最有利于分类器性能的样本来进一步训练分类器，它能有效地减少评价样本的数量；,被动学习,只是随机地选择训练样本，被动地接受这些样本的信息进行学习。,主动学习是实现监督学习过程的一个有效的方法。在主动学习过程中，分类器主动地选择对其“最有帮助”的一组子样本进行学习，而不是被动地接受训练集。,“最有帮助”的样本指的是对当前分类器来说，归属最不确定的样本。即当前分类器,最难以区分,的样本。通常情况下，主动学习的计算复杂度比一般的监督学习过程要显著得低。,4.3,主动学习,/,被动学习（续）,初始状态下，候选样本集中所有的样本都未带类别标注，根据先验知识或者随机地从候选样本集中选择少量样本并标注它们的类别，构造初始训练样本集，确保初始训练样本集中至少包含有一个正例样本和一个负例样本。,在上述初始训练样本集上训练一个分类器，并采用某种针对该分类器采样算法，从候选样本集中选择最有利于提高分类器性能的样本，手工标注其类别并加入训练样本集，再重新训练分类器。,重复以上过程，直到候选样本集为空或达到某种要求。主动学习是一个循环反复的过程。,在主动学习的模型中，全部数据被分为两部分，一部分是,带标签的样本集,X,，另一部分是,无标签的样本集,U,。主动学习的模型还包括了一个在带标签的样本集,X,上训练的,学习机,L,和一个,决策模块,q,。决策模块,q,用来决定,U,中的哪一些样本应该被选出标记标签，并加入带标签的样本集,X,。更新后的,X,将在下一个轮次被用于训练学习机,L,。主动学习的框架模型如图。,根据决策模块,q,的不同工作机理，主动学习方法又可以被分为两大类：其一是,不确定取样方法,；另一是,委员会咨询方法,。,4.4,直推式学习,直推式学习的思想来源于前面提到的机器学习的困境：一方面获取已知标签的样本代价高昂；另一方面获取无标签的样本要相对容易得多。,直推式学习的学习过程恰恰可以将大量无标签的测试集样本所携带的分类信息，通过迭代逐步转移到了最终的分类器中去。,由于测试样本易于获得、数量较多，直推式学习机能够更好地描述整体样本空间上的数据分布特性，使测试样本的分类结果更为准确。,4.4,直推式学习（续）,在多数情况下，人们只对测试文本的分类结果感兴趣，这时就没有必要非得寻求具有良好泛化能力的规则，而只要求分类器能对这些特定的文本做出正确分类即可。,它在目前已知标签样本十分紧缺，而未知标签样本易于获得的条件下，有着非常重要的现实意义。,4.5,广义,EM,算法,EM,算法可用于许多问题框架，其中需要估计一组描述基准概率分布的参数,，只给定了由此分布产生的全部数据中能观察到的一部分。,一般地，令,X,=,代表在同样的实例中未观察到的数据，并令,Y,=,X,Z,代表全体数据。,注意到未观察到的,Z,可被看作随机变量，它的概率分布依赖于未知参数,和已知数据,X,。类似地，,Y,是一随机变量，因为它是由随机变量,Z,来定义的。,在,EM,算法的一般形式中，用,h,来代表参数,的假设值，而,h,代表在,EM,的每次迭代中修改的假设。,4.5,广义,EM,算法（续）,EM,算法通过搜寻使,E,ln,P,(,Y,|,h,),最大的,h,来寻找极大似然假设,h,。此期望值是在,Y,所遵循的概率分布上计算，此分布由未知参数,确定。,首先，,P,(,Y,|,h,),是给定假设,h,下全部数据,Y,的似然性。其合理性在于我们要寻找一个,h,使该量的某函数值最大化。,其次，使该量的对数,ln,P,(,Y,|,h,),最大化也使,P,(,Y,|,h,),最大化。,第三，引入期望值,E,ln,P,(,Y,|,h,),是因为全部数据,Y,本身也是一随机变量。已知全部数据,Y,是观察到的,X,和未观察到的,Z,的合并，我们必须在未观察到的,Z,的可能值上取平均，并以相应的概率为权值。,4.5,广义,EM,算法（续）,在,EM,算法的一般形式里，重复以下两个步骤直至收敛。,步骤,1,：估计（,E,）步骤：使用当前假设,h,和观察到的数据,X,来估计,Y,上的概率分布以计算,Q,(,h,|,h,),。,步骤,2,：最大化（,M,）步骤：将假设,h,替换为使,Q,函数最大化的假设,h,：,4.6,强化学习,强化学习的模型如图所示,通过,Agent,与环境的交互进行学习。,Agent,与环境的交互接口包括,行动,（,Action,）、,回报,（,Reward,）和,状态,（,State,）。,交互过程可以表述为如下形式：,每一步，,Agent,根据策略选择一个行动执行，然后感知下一步状态和即时回报，通过经验再修改自己的策略。,Agent,的目标就是,最大化长期回报,。,4.6,强化学习（续）,马尔可夫过程,是四元组,M=,。其中,S,是状态集。,A,是行动集，,A(s,),表示状态,s,下可执行的行动。,T=S,A,S,0,，,1,是状态转换模型，,T,(,s,a,s,),表示状态,s,下执行行动,a,到达状态,s,的概率，且满足,s,T,(,s,a,s,)=1,。,R=S