《数据挖掘基础幻灯片.ppt》由会员分享，可在线阅读，更多相关《数据挖掘基础幻灯片.ppt（87页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据挖掘基础数据挖掘基础第1页，共87页，编辑于2022年，星期六一、概念和术语n n1.1 数据挖掘数据挖掘/知识发现知识发现（1 1）数据挖掘数据挖掘数据挖掘数据挖掘是从存放在数据集中的大量数据挖掘出有趣知识的是从存放在数据集中的大量数据挖掘出有趣知识的过程。过程。（2 2）数据挖掘，又称为）数据挖掘，又称为数据库中知识发现数据库中知识发现数据库中知识发现数据库中知识发现（Knowledge Discovery in Knowledge Discovery in DatabasesDatabases）或）或知识发现知识发现知识发现知识发现，它是一个从大量数据中抽取挖掘出未知的、，它是一个从
2、大量数据中抽取挖掘出未知的、有价值的模式或规律等知识的非平凡过程，它与数据仓库有着密切有价值的模式或规律等知识的非平凡过程，它与数据仓库有着密切的联系。的联系。（3 3）广义的数据挖掘是指知识发现的全过程；狭义的数据挖掘是）广义的数据挖掘是指知识发现的全过程；狭义的数据挖掘是指统计分析、机器学习等发现数据模式的智能方法，即偏重于指统计分析、机器学习等发现数据模式的智能方法，即偏重于模型和算法。模型和算法。（4 4）数据库查询系统和专家系统）数据库查询系统和专家系统不是不是不是不是数据挖掘！在小规模数据上的统数据挖掘！在小规模数据上的统计分析和机器学习过程也不应算作数据挖掘。计分析和机器学习过程
3、也不应算作数据挖掘。第2页，共87页，编辑于2022年，星期六n n1.2 机器学习机器学习（1）对于某类任务T和性能度量P，如果一个计算机程序在T上以P衡量的性能随着经验E而自我完善，那么这个计算机程序被称为在从经验E学习。（2）机器学习是知识发现的一种方法，是指一个系统通过执行某种过程而改进它处理某一问题的能力。第3页，共87页，编辑于2022年，星期六n n1.3 数据挖掘的对象数据挖掘的对象（1 1）关系型数据库、事务型数据库、面向对象的数据库；（2 2）数据仓库/多维数据库；多维数据库；（3）空间数据（如地图信息）空间数据（如地图信息）（4 4）工程数据（如建筑、集成电路的信息）（5
4、 5）文本和多媒体数据（如文本、图象、音频、视频数据）（6）时间相关的数据（如历史数据或股票交换数据）（7）万维网（如半结构化的HTML，结构化的，结构化的XML以及以及其他网络信息）其他网络信息）第4页，共87页，编辑于2022年，星期六n n1.4 数据挖掘的步骤数据挖掘的步骤（1 1）数据清理（消除噪音或不一致数据，补缺）；（2）数据集成（多种数据源可以组合在一起）；（3）数据选择（从数据库中提取相关的数据）；（4 4）数据变换（变换成适合挖掘的形式）；（5 5）数据挖掘（使用智能方法提取数据模式）；（6）模式评估（识别提供知识的真正有趣模式）；）模式评估（识别提供知识的真正有趣模式）；
5、（7）知识表示（可视化和知识表示技术）。）知识表示（可视化和知识表示技术）。第5页，共87页，编辑于2022年，星期六n n1.5 支持数据挖掘的关键技术支持数据挖掘的关键技术（1）数据库/数据仓库/OLAP（2）数学/统计（回归分析：多元回归、自回归；判别分析：Bayes判别、Fisher判别、非参数判别；主成分分析、相关性分析；模糊集；粗糙集）（3）机器学习（聚类分析；关联规则；决策树；范例推理；贝叶斯网络；神经网络；支持向量机；遗传算法）（4）可视化：将数据、知识和规则转化为图形表现的形式。第6页，共87页，编辑于2022年，星期六n n1.6 数据仓库数据仓库（1 1）数据仓库数据仓库
6、是一个面向主题的、集成的、随时间变化的、非易失性数据的集合，用于支持管理人员的决策。（2）数据仓库是一种多个异种数据源在单个站点以统一的模）数据仓库是一种多个异种数据源在单个站点以统一的模式组织的存储，以支持管理决策。数据仓库技术包括数据式组织的存储，以支持管理决策。数据仓库技术包括数据清理、数据集成和清理、数据集成和联机分析处理联机分析处理联机分析处理联机分析处理（OLAP）。）。（3）数据仓库的逻辑结构是多维数据库。数据仓库的实际物理结构可以是关系数据存储或多维数据方多维数据方（Cube）。）。（4）数据方是由）数据方是由维度维度（DimensionDimension）和）和度量度量（Me
7、asure）定义的一种数据集，度量存放在由维度索引的数据方单元中。维度对应于模式中的属性组，度量对应于与主题相关的事实数据。数据方的物化物化是指预计算并存储全是指预计算并存储全部或部分单元中的度量。部或部分单元中的度量。第7页，共87页，编辑于2022年，星期六n n1.7 数据仓库的模型数据仓库的模型（1）星形模式星形模式：最常见模型；其中数据仓库包括一个大的、包含大批数据、不含冗余的中心表（事实表）；一组小的附属表（维表），每维一个。（2）雪花模式雪花模式：雪花模式是星型模式的变种，其中某些维表是规范化的，因而把数据进一步分解到附加的表中。（3）星系模式星系模式：多个事实表共享维表。这种模
8、式可以看作星形模式集，因此称为星系模式，或事实星座。第8页，共87页，编辑于2022年，星期六n n1.8 典型的典型的OLAP操作操作（1 1）OLAPOLAP是一种多维数据分析技术。包括汇总、合并和聚集是一种多维数据分析技术。包括汇总、合并和聚集等功能，以及从不同的角度观察信息的能力。等功能，以及从不同的角度观察信息的能力。（2 2）上卷上卷上卷上卷：从某一维度的更高概念层次观察数据方，获得更概要的：从某一维度的更高概念层次观察数据方，获得更概要的数据。它通过沿维的概念分层向上或维归约来实现。数据。它通过沿维的概念分层向上或维归约来实现。（3 3）下钻下钻下钻下钻：下钻是上卷的逆操作。它从
9、某一维度的更低概念层：下钻是上卷的逆操作。它从某一维度的更低概念层次观察数据方，获得更详细的数据。下钻可以通过沿维的概次观察数据方，获得更详细的数据。下钻可以通过沿维的概念分层向下或引入新的维来实现。念分层向下或引入新的维来实现。（4 4）切片和切块切片和切块切片和切块切片和切块：切片操作在给定的数据方的选择一个维的部分：切片操作在给定的数据方的选择一个维的部分属性，获得一个较小的子数据方。切块操作通过对选择两个或属性，获得一个较小的子数据方。切块操作通过对选择两个或多个维的部分属性，获得一个较小的子数据方。多个维的部分属性，获得一个较小的子数据方。（5 5）转轴转轴转轴转轴：是一种改变数据方
10、二维展现形式的操作。它将数据：是一种改变数据方二维展现形式的操作。它将数据方的二维展现中的某些维度由行改为列，或由列改为行。方的二维展现中的某些维度由行改为列，或由列改为行。第9页，共87页，编辑于2022年，星期六二、数据准备n n现实世界的数据是不完整的不完整的（有些感兴趣的属性缺少属性值，或仅包含聚集数据），含含噪音的噪音的（包含错误，或存在偏离期望的异常值），不一致的不一致的（例如，用于商品分类的部门编码存在差异）。n n需要数据清理数据清理、数据集成数据集成、数据选择数据选择、数据数据变换变换等技术对数据进行处理。第10页，共87页，编辑于2022年，星期六n n2.1 维归约维归约
11、/特征提取特征提取n n2.1-1 决策树归约决策树归约（1）决策树归约构造一个类似于流程图的结构：其每个非叶子结点表示一个属性上的测试，每个分枝对应于测试的一个输出；每个叶子结点表示一个决策类。（2）在每个结点，算法选择“当前对分类最有帮助”的属性，出现在树中的属性形成归约后的属性子集。第11页，共87页，编辑于2022年，星期六n n2.1-2 粗糙集归约粗糙集归约（1）粗糙集理论在数学意义上描述了知识的不确定性，它的特点是把用于分类的知识嵌入集合内，使分类与知识联系在一起。（2）知识的粒度、不可分辨关系、上近似、下近似、边界等概念见下图。第12页，共87页，编辑于2022年，星期六n n
12、2.1-2 粗糙集归约（续）粗糙集归约（续）（3）令Q代表属性的集合。qQ是一个属性，如果IND(Qq)=IND(Q)，则q在S中不是独立的；否则称q在S中是独立的。（4）若集合满足IND(R)=IND(Q)且R中的每一个属性都是独立的，则R被称为Q的一个“约简”，记作R=RED(Q)。（5）约简可以通过删除冗余的（不独立的）属性而获得，约简包含的属性即为“对分类有帮助”的属性。第13页，共87页，编辑于2022年，星期六n n2.2 数据变换数据变换n n2.2-1 归一化与模糊化归一化与模糊化有限区间的归一化：无限区间的归一化：模糊隶属度：第14页，共87页，编辑于2022年，星期六n n
13、2.2-2 核函数核函数（1）核函数的基本思想是将在低维特征向量线性不可分的数据映射到线性可分的高维特征空间中去。（2）映射可以是显式的，也可以是隐式的。显式映射即找到一个映射关系f，使高维空间的特征向量f(x)可以被直接计算出来。（3）隐式映射，即引入一个核函数进行整体处理，就避免了对的直接求f(x)的计算困难。核函数即某高维特征空间中向量的内积，是核矩阵中的一个元素。（4）并不是所有的实值函数f(x)都可以作为空间映射的核函数，只有f(x)是某一特征空间的内积时，即符合Mercer条件，它才能成为核函数。第15页，共87页，编辑于2022年，星期六n n2.2-2 核函数（续）核函数（续）
14、n n多项式函数：n n n n高斯（RBF）函数：n n n n多层感知机函数：n n低维空间向量映射到高维空间向量举例：第16页，共87页，编辑于2022年，星期六n n2.3 数据压缩数据压缩n n2.3-1 离散化离散化n n离散化的用途：（1）适应某些仅接受离散值的算法；（2）减小数据的尺度。n n离散化的方法包括几下几种。n n（1）等距分割；n n（2）聚类分割；n n（3）直方图分割；n n（4）基于熵的分割；n n（5）基于自然属性的分割。第17页，共87页，编辑于2022年，星期六n n2.3-2 回归回归n n回归和对数线性模型可以用来近似给定的数据。n n在线性回归线性
15、回归中，用一条直线来模拟数据的生成规则。n n多元回归多元回归是线性回归的扩展，涉及多个预测变量。n n在多项式回归多项式回归中，通过对变量进行变换，可以将非线性模型转换成线性的，然后用最小平方和法求解。第18页，共87页，编辑于2022年，星期六n n2.3-2 回归（续）回归（续）n n利用线性回归可以为连续取值的函数建模。广义线性模利用线性回归可以为连续取值的函数建模。广义线性模型则可以用于对离散取值变量进行回归建模。型则可以用于对离散取值变量进行回归建模。n n在广义线性模型中，因变量在广义线性模型中，因变量Y 的变化速率是的变化速率是Y 均值的一个函数；这一点与线性回归不同。常见的广
16、义线性模型有：对数回归和泊松回归。n n对数回归模型是利用一些事件发生的概率作为自变量是利用一些事件发生的概率作为自变量所建立的线性回归模型。所建立的线性回归模型。n n泊松回归模型泊松回归模型主要是描述数据出现次数的模型，因为它们主要是描述数据出现次数的模型，因为它们常常表现为泊松分布。常常表现为泊松分布。第19页，共87页，编辑于2022年，星期六n n2.3-3 主成分分析（主成分分析（PCA）n nPCA算法搜索c c个最能代表数据的个最能代表数据的k-k-维正交向量；这里c c k。这样，原来的数据投影到一个较小的空间，导致数。这样，原来的数据投影到一个较小的空间，导致数据压缩。步骤
17、如下：据压缩。步骤如下：（1 1）对输入数据归一化，使得每个属性都落入相同的区间。（2）PCA计算计算c c个规范正交向量，作为归一化输入数据的基。这些是单位向量，每一个都垂直于另一个：称为主成分。输入数据是主要成分的线性组合。（3 3）对主成分按“意义意义”或强度降序排列，选择部分主成分充当数据的一组新坐标轴。第20页，共87页，编辑于2022年，星期六n n2.3-4 离散小波变换（离散小波变换（DWT）n n离散小波变换是一种线性信号处理技术信号处理技术。该技术方法可以将一个数据向量转换为另一个数据向量（为小波相关系数）；且两个向量具有相同长度。n n可以舍弃转换后的数据向量中的一些小波
18、相关系数。保留所有大于用户指定阈值的小波系数，而将其它小波系数置为0，以帮助提高数据处理的运算效率。n n这一技术方法可以在保留数据主要特征情况下除去数据中的噪声，因此该方法可以有效地进行数据清洗。n n给定一组小波相关系数，利用离散小波变换的逆运算还可给定一组小波相关系数，利用离散小波变换的逆运算还可以近似恢复原来的数据。以近似恢复原来的数据。第21页，共87页，编辑于2022年，星期六n n2.3-4 离散小波变换（续）离散小波变换（续）n n常用的小波函数包括Haar系列,Daubechies系列，Moret系列，Sym系列，Meyer系列，Coif系列。第22页，共87页，编辑于202
19、2年，星期六n n2.3-5 潜在语义分析潜在语义分析n n潜在语义分析将样本映射到语义概念空间以发现样本数据潜在语义分析将样本映射到语义概念空间以发现样本数据之间的潜在语义联系。之间的潜在语义联系。n n（1 1）构造）构造“特征特征-样本”矩阵，矩阵，“特征特征-样本”矩阵中的每一列是对应于第i i个样本特征向量；n n（2 2）对该矩阵进行奇异值分解）对该矩阵进行奇异值分解(SVD)；n n（3）用最大的k个奇异值所对应的“特征特征-语义语义”矩阵Uk和“样本样本-语义语义”矩阵矩阵Vk以及最大的以及最大的k个奇异值重构“特征-样本”矩阵。下面两式分别代表在下面两式分别代表在语义空间特征
20、与特征语义空间特征与特征之间的距离和之间的距离和在语义在语义空间空间样本与样本之样本与样本之间的距离间的距离第23页，共87页，编辑于2022年，星期六n n2.3-6 聚类分析聚类分析n n聚类技术将数据元组视为对象。它将对象划分为聚类，使在一个聚类中的对象“类似”，但与其它聚类中的对象“不类似”。n n通常，类似性基于距离，用对象在空间中的“接近”程度定义。聚类的“质量”可以用“直径”表示；而直径是一个聚类中两个任意对象的最大距离。n n质心距离是聚类质量的另一种度量，它定义为由聚类质心（表示“平均对象”，或聚类空间中的平均点）到每个聚类对象的平均距离。第24页，共87页，编辑于2022年
21、，星期六n n2.3-6 聚类分析（续）聚类分析（续）k-meansk-means算法算法k-medoids算法第25页，共87页，编辑于2022年，星期六三、数据挖掘算法n n数据挖掘算法按挖掘目的可分为：数据挖掘算法按挖掘目的可分为：（1）概念描述（总结，对比等）（2）关联规则分析（3）分类与预测 （信息自动分类，信息过滤，图像识别等）（4）聚类分析（5）异常分析（入侵检测，金融安全等）（6）趋势、演化分析（回归，序列模式挖掘）第26页，共87页，编辑于2022年，星期六n n按训练方式，机器学习可分为：按训练方式，机器学习可分为：（1 1）有监督的学习有监督的学习；有训练样本，学习机通过
22、学习获得训练样本包含的知识，并用其作为判断测试样本的类别的依据。（2）无监督的学习：无训练样本，仅根据测试样本的在特：无训练样本，仅根据测试样本的在特征空间分布情况判断其类别。征空间分布情况判断其类别。（3 3）半监督的学习半监督的学习：有少量训练样本，学习机以从训练样本获得的知识为基础，结合测试样本的分布情况逐步修正已有知识，并判断测试样本的类别。（4 4）强化学习强化学习：没有训练样本，但有对学习机每一步是否更：没有训练样本，但有对学习机每一步是否更接近目标的奖惩措施。接近目标的奖惩措施。第27页，共87页，编辑于2022年，星期六n n有监督的学习n n半监督的学习n n无监督的学习第2
23、8页，共87页，编辑于2022年，星期六n n3.1 关联规则挖掘关联规则挖掘n n关联规则挖掘发现大量数据中项集之间有趣的关联或相关关联规则挖掘发现大量数据中项集之间有趣的关联或相关联系。设联系。设I I =i i1 1,i2 2,.,i,.,im 是项的集合。设任务相关的是项的集合。设任务相关的数据数据D是数据库事务的集合，其中每个事务T T是项的集合，使得T I。设。设A A是一个项集，事务是一个项集，事务T包含包含A当且仅当当且仅当A T T。n n关联规则关联规则关联规则关联规则是形如A B B的蕴涵式，其中A A I，B I I，并且并且A A B=。规则A A B B在事务集在事
24、务集D D中成立，具有支中成立，具有支持度持度s s，其中，其中s s是D D中事务包含A B B的百分比。即，的百分比。即，P(A A B)。规则规则A A B在事务集D中具有置信度中具有置信度c，如果D中包含中包含A的事务同时也包含B B的百分比是c c。这是条件。这是条件概率概率P P(B|A)。即n nsupport(A B B)=P(A B)n nconfidence(A B B)=)=P P(B|AB|A)第29页，共87页，编辑于2022年，星期六n n3.1 关联规则挖掘（续）关联规则挖掘（续）n nAprioriApriori性质：频繁项集的所有非空子集都必须也是频繁的。n
25、nAprioriApriori性质基于如下观察：根据定义，如果项集I不不满足最小支持度阈值满足最小支持度阈值s，则，则I I不是频繁的，即P P(I)s s。如果项如果项A A添加到I，则结果项集（即I A A）不可能比I I更频繁出现。因此，I I A A也不是频繁的，即也不是频繁的，即P(I I A A)s s。n n该性质表明如果一个集合不能通过测试，则它的所有超该性质表明如果一个集合不能通过测试，则它的所有超集也都不能通过相同的测试。集也都不能通过相同的测试。n n将将Apriori性质应用于算法：下面算法的两个主要步过程由连接连接和和剪枝组成。第30页，共87页，编辑于2022年，星
26、期六n n3.1 关联规则挖掘（续）关联规则挖掘（续）n n连接步连接步：为找：为找Lk，通过Lk-1k-1与自己连接产生候选k-项集的集合。该候选项集的集合记作Ck k。C Ck k是L Lk的超集。扫描数据库，确定Ck k中每个候选的计数，将令计数值不小于最小支持度计数的（频繁的）所有候选加入L Lk。n n剪枝步剪枝步：但Ck k可能很大，这样所涉及的计算量就很大。可能很大，这样所涉及的计算量就很大。根据根据AprioriApriori性质如果一个候选如果一个候选k-项集的项集的(k-1)-1)-子集不在子集不在L Lk-1中，则该候选也不可能是频繁的，从而可以由Ck中中删除。删除。n
27、nApriori性质性质(逆反描述)：任何非频繁的：任何非频繁的(k k-1)-项集都不项集都不是可能是频繁是可能是频繁k k-项集的子集。项集的子集。第31页，共87页，编辑于2022年，星期六n n3.2 决策树决策树n n决策树学习是归纳推理算法。它是一种逼近离散函数的方决策树学习是归纳推理算法。它是一种逼近离散函数的方法，且对噪声数据有很好的健壮性。在这种方法中学习到法，且对噪声数据有很好的健壮性。在这种方法中学习到的知识被表示为决策树，决策树也能再被表示为多个的知识被表示为决策树，决策树也能再被表示为多个if-then的规则，以提高可读性。的规则，以提高可读性。n n基本决策树算法就
28、是一个基本决策树算法就是一个贪心算法贪心算法。它采用自上而下、分。它采用自上而下、分而制之的递归方式来构造一个决策树而制之的递归方式来构造一个决策树n n通常，决策树是一种自顶向下增长树的贪婪算法，在每通常，决策树是一种自顶向下增长树的贪婪算法，在每个结点选取能最好地分类样例的属性。继续这个过程直个结点选取能最好地分类样例的属性。继续这个过程直到这棵树能完美分类训练样例，或所有的属性都使用过到这棵树能完美分类训练样例，或所有的属性都使用过了。了。“信息增益信息增益”用于衡量属性的价值。熵（用于衡量属性的价值。熵（entropyentropy）是一种度量信息增益的指标，它描述了样本的纯度）是一种
29、度量信息增益的指标，它描述了样本的纯度（purity）。下面是熵的定义：n nEntropy=-Pilog2Pi i第32页，共87页，编辑于2022年，星期六n n3.2 决策树（续）决策树（续）n n注意点：注意点：注意点：注意点：n n（1 1）避免过度拟合，应该适度剪枝；（）避免过度拟合，应该适度剪枝；（2）连续值的离散化；（3 3）处理缺失值的方法：最常见值、按概率分配；（4 4）处理权重不同的属性）处理权重不同的属性n n常用实现算法：常用实现算法：常用实现算法：常用实现算法：n nCART、ID3ID3、ASSISTANTASSISTANT、C4.5第33页，共87页，编辑于20
30、22年，星期六n n3.3 人工神经网络人工神经网络n n人工神经网络（Artificial Neural Networks）提供了一种普遍而且实用的方法，来从样例中学习值为实数、离散或向量的函数。n n反向传播（Back Propagation）这样的算法使用梯度下降来调节网络参数以最佳拟合由输入/输出对组成的训练集合。n nBP网络的学习方法和目标：对网络的连接权值进行调整，使得对任一输入都能得到所期望的输出。第34页，共87页，编辑于2022年，星期六常用的非线性作用函数是常用的非线性作用函数是SigmoidSigmoid函数函数，即f f(x x)=1/(1+e)=1/(1+e-x-x
31、)。在神经网络模型中，。在神经网络模型中，大量神经元节点按一定体系结构连接成大量神经元节点按一定体系结构连接成网状。神经网络一般都具有输入层，隐网状。神经网络一般都具有输入层，隐层和输出层。层和输出层。每个神经元都是一个结构相似每个神经元都是一个结构相似的独立单元，它接受前一层传的独立单元，它接受前一层传来的数据，并将这些数据的加来的数据，并将这些数据的加权和输入非线性作用函数中，权和输入非线性作用函数中，最后将非线性作用函数的输出最后将非线性作用函数的输出结果传递给后一层。结果传递给后一层。第35页，共87页，编辑于2022年，星期六误差反向传播的过程误差反向传播的过程第36页，共87页，编
32、辑于2022年，星期六n n3.3 人工神经网络（续）人工神经网络（续）n n自适应共振理论模型(ART)聚类n n连续/离散Hopfield神经网络求近似最优解，识别与分类n n双向联想记忆模型 (BAM)识别n n玻尔兹曼机(BM)求最优解n n脑中盒模型(BSB)识别与分类n n自组织映射模型(SOM)识别与分类n n对向传播网络模型(CPN)识别与分类n n小脑模型(CMAC)快速识别第37页，共87页，编辑于2022年，星期六n n3.4 朴素贝叶斯（朴素贝叶斯（Naive Bayes）分类器）分类器n n朴素贝叶斯分类器是一种基于贝叶斯理论的分类器。它的特点是朴素贝叶斯分类器是一种
33、基于贝叶斯理论的分类器。它的特点是以概率形式表达所有形式的不确定，学习和推理都由概率规则实以概率形式表达所有形式的不确定，学习和推理都由概率规则实现，学习的结果可以解释为对不同可能的信任程度。现，学习的结果可以解释为对不同可能的信任程度。n nP(H)P(H)是是先验概率先验概率先验概率先验概率，或，或H H的先验概率。的先验概率。P(H|X)P(H|X)是是后验概率后验概率后验概率后验概率，或条件，或条件X X下，下，H H的后验概率。后验概率的后验概率。后验概率P(H|X)P(H|X)比先验概率比先验概率P(H)P(H)基于更多的基于更多的信息。信息。P(H)P(H)是独立于是独立于X X
34、的。的。n n假定数据样本世界由水果组成，用它们的颜色和形状描述。假假定数据样本世界由水果组成，用它们的颜色和形状描述。假定定X X表示红色和圆的，表示红色和圆的，H H表示假定表示假定X X是苹果，则是苹果，则P(H|X)P(H|X)反映当我们反映当我们看到看到X X是红色并是圆的时，我们对是红色并是圆的时，我们对X X是苹果的确信程度。是苹果的确信程度。第38页，共87页，编辑于2022年，星期六朴素贝叶斯分类能够奏效的前提是，P(X|H)相对比较相对比较容易计算。假定容易计算。假定X表示红色和圆的，表示红色和圆的，H H表示假定X X是苹果；是苹果；则则P(X|H)P(X|H)表示已知苹
35、果，它既红又圆的概率。表示已知苹果，它既红又圆的概率。第39页，共87页，编辑于2022年，星期六n n3.5 期望最大化（期望最大化（EM）n n期望最大化（EM）方法和朴素贝叶斯方法有着共同的理论基础。期望最大化是一种基于循环过程的最大似然参数估计方法，用于解决带缺失数据的参数估计问题。n n样本数据分为标记样本和未标记样本，按照统计的观点，对于每一个样本的产生，其背后都有一个模型，即样本生成模型。样本生成模型的参数先由标记样本确定，再通过标记样本和利用当前模型判断标记的未标记样本共同调整。第40页，共87页，编辑于2022年，星期六n n3.5 期望最大化（续）期望最大化（续）n n如果
36、参数适当，如果参数适当，EM EM 算法能得到较好的分类结果，但计算速度相算法能得到较好的分类结果，但计算速度相对较慢。其具体的步骤如下：对较慢。其具体的步骤如下：n n一、初始参数估计，将未标记的样本按朴素贝叶斯分类方法一、初始参数估计，将未标记的样本按朴素贝叶斯分类方法进行类标注。进行类标注。n n二、反复迭代二、反复迭代E E步骤和步骤和MM步骤，直到收敛。步骤，直到收敛。n n三、三、E E步骤：对于每个未标记的样本，按下式计算类标记的期望值。步骤：对于每个未标记的样本，按下式计算类标记的期望值。n n四、四、MM步骤：利用步骤：利用E E步骤计算出的期望值，按下式用已标记样本和未步骤
37、计算出的期望值，按下式用已标记样本和未标记样本重新估计新的分类器参数。标记样本重新估计新的分类器参数。第41页，共87页，编辑于2022年，星期六n n3.6 K-最近邻分类最近邻分类n nK-近邻（K-NN）分类是基于范例基于范例的分类方法，它的基本思想是：给定待分类样本后，考虑在训练样本集中与该待分类样本距离最近（最相似）的K K 个样本，根据这K K 个样本中大多数样本所属的类别判定待分类样个样本中大多数样本所属的类别判定待分类样本的类别。本的类别。n n它的特例是它的特例是1-NN1-NN，即分类时选出待分类样本的最近邻，并以此最近邻的类标记来判断样本的类。n nK-NN算法的优点在于
38、它有较高的精确程度，研究表明，K-NNK-NN的分类效果要明显好于朴素贝叶斯分类、决策树分类。第42页，共87页，编辑于2022年，星期六n n3.6 K-最近邻分类（续）最近邻分类（续）n n最近邻分类的算法步骤如下：n n一、以向量空间模型的形式描述各训练样本。n n二、在全部训练样本集中选出与待分类样本最相似的K个样本。K值的确定目前没有很好的方法，一般采用先定一个100左右的初始值，然后再调整。n n三、将待分类样本标记为其K个邻居中所属最多的那个类别中。第43页，共87页，编辑于2022年，星期六n3.7 遗传算法遗传算法n n遗传算法易于并行处理，其依据是自然界进化和适者生存的原则
39、。遗传学习开始如下：创建若干个由随机产生的个体组成的初始群体群体群体群体。每个个体用一个二进位串表示。n n形成由当前群体中最适合的个体组成新的群体，以及这些形成由当前群体中最适合的个体组成新的群体，以及这些规则的子女。个体的规则的子女。个体的适合度适合度用某一目标函数来评估。n n子女通过使用诸如交叉和变异等遗传操作来创建。在子女通过使用诸如交叉和变异等遗传操作来创建。在交交交交叉叉叉叉操作中，来自个体对的子串交换，形成新的个体对。操作中，来自个体对的子串交换，形成新的个体对。在在变异变异操作中，个体中随机选择的位被反转。第44页，共87页，编辑于2022年，星期六n n3.7 遗传算法（续
40、）遗传算法（续）n nFitnessFitness：适应度评分函数，为给定假设赋予一个评估得分。n nFitness_ _thresholdthreshold：指定终止判据的阈值。：指定终止判据的阈值。n np p：群体中包含的假设数量。：群体中包含的假设数量。r r：每一步中通过交叉取代：每一步中通过交叉取代群体成员的比例。群体成员的比例。m：变异率。：变异率。n n初始化群体：初始化群体：P P随机产生的p p个假设n n评估：评估：对于P中的每一个中的每一个h h，计算FitnessFitness(h)n n当 Fitness(h h)Fitness_ _threshold，做：，做：n
41、 n产生新的一代PS S：第45页，共87页，编辑于2022年，星期六n n3.7 遗传算法（续）遗传算法（续）n n选择：用概率方法选择P的(1-(1-r)p个成员加入个成员加入P PS S。从。从P中选择假设hi的概率的概率P(hi)通过下面公式计算：通过下面公式计算：n n交叉：根据上面给出的P(h hi i)，从P P中按概率选择中按概率选择r p/2对对假设。对于每一对假设假设。对于每一对假设 2应用交叉算子产生两个应用交叉算子产生两个后代。把所有的后代加入后代。把所有的后代加入P PS。n n变异：变异：使用均匀的概率从PS中选择中选择m m百分比的成员。对百分比的成员。对于选出的
42、每个成员，在它的表示中随机选择一个位取反。于选出的每个成员，在它的表示中随机选择一个位取反。n n更新：更新：PP PS S。n n评估：对于对于P P中的每一个中的每一个h计算Fitness(h h)n n从从P P中返回适应度最高的假设。第46页，共87页，编辑于2022年，星期六n n3.8 聚类分析聚类分析n n为达到全局最优，基于划分的聚类会要求穷举所有可能为达到全局最优，基于划分的聚类会要求穷举所有可能的划分。聚类技术将数据元组视为对象。它将对象划分的划分。聚类技术将数据元组视为对象。它将对象划分为群或聚类，使得在一个聚类中的对象为群或聚类，使得在一个聚类中的对象“类似类似”，但与
43、，但与其它聚类中的对象其它聚类中的对象“不类似”。n n绝大多数应用采用了以下两个比较流行的绝大多数应用采用了以下两个比较流行的基于划分的方基于划分的方法法，这些基于划分的聚类方法对在中小规模的数据库中发现球状簇很适用。n n（1）k-meansk-means算法，在该算法中，每个簇用该簇中对象，在该算法中，每个簇用该簇中对象的平均值来表示。的平均值来表示。n n（2）k-medoids算法算法，在该算法中，每个簇用接近聚类，在该算法中，每个簇用接近聚类中心的一个对象来表示。中心的一个对象来表示。第47页，共87页，编辑于2022年，星期六n3.8 聚类分析（续）聚类分析（续）n n常用的相似
44、程度度量 n n余弦夹角：Dice系数：Jaccard系数：第48页，共87页，编辑于2022年，星期六n n3.8 聚类分析（续）聚类分析（续）n n基于层次的方法：基于层次的方法：层次的方法对给定数据集合进行层次层次的方法对给定数据集合进行层次的分解。根据层次的分解如何形成，层次的方法可以被的分解。根据层次的分解如何形成，层次的方法可以被分为凝聚或分裂方法。分为凝聚或分裂方法。（Chameleon，CURECURE，BIRCHBIRCH）n n基于密度的方法：只要临近区域的密度超过某个阈值，就继续聚类。避免仅生成球状聚类。（DBSCAN，OPTICS，DENCLUE）n n基于网格的方法：
45、基于网格的方法把对象空间量化为有限数目的单元，所有的聚类操作都在这个量化的空间上进行。这种方法的主要优点是它的处理速度很快。（STINGSTING，CLIQUE，WaveClusterWaveCluster）n n基于模型的方法：为每个簇假设一个模型，发现数据对模型的最好匹配。（COBWEB，CLASSIT，AutoClassAutoClass）第49页，共87页，编辑于2022年，星期六n n3.9 隐马尔可夫模型隐马尔可夫模型n n对于一个随机事件，有一个观察值序列：对于一个随机事件，有一个观察值序列：O O1 1,.,O,.,OT T。该事件隐。该事件隐含着一个状态序列：含着一个状态序列
46、：X X1 1,.,X,.,XT Tn n假设假设1 1：马尔可夫性，：马尔可夫性，P(XP(Xi i|X|Xi-1i-1X X1 1)=P(X)=P(Xi i|X|Xi-1i-1)n n假设假设2 2：不动性，：不动性，P(XP(Xi+1i+1|X|Xi i)=P(X)=P(Xj+1j+1|X|Xj j)，对任意，对任意i,ji,j成立成立n n假设假设3 3：输出独立性，：输出独立性，P(OP(O1 1,.,O,.,OT T|X|X1 1,.,X,.,XT T)=)=P(OP(Ot t|X|Xt t)n n一个隐马尔可夫模型是一个五元组：一个隐马尔可夫模型是一个五元组：(X X,O O,A
47、,B,),A,B,)n n其中：其中：X X=Q=Q1 1,.,Q,.,QN N：状态的有限集合；：状态的有限集合；n n O O=V=V1 1,.,V,.,VMM：观察值的有限集合；：观察值的有限集合；n nA=aA=aij ij，a aij ij=P(X=P(Xt+1t+1=Q=Qj j|X|Xt t=Q=Qi i)：转移概率；：转移概率；n nB=bB=bikik，b bikik=P(O=P(Ot t=V=Vk k|X|Xt t=Q=Qi i)：输出概率；：输出概率；n n =i i，i i=P(X=P(X1 1=Q=Qi i)：初始状态分布。：初始状态分布。第50页，共87页，编辑于2
48、022年，星期六n n3.9 隐马尔可夫模型（续）隐马尔可夫模型（续）n n令令 =A,B,=A,B,为给定为给定HMMHMM的参数，n n令令 =O=O1 1,.,OT 为观察值序列，为观察值序列，n n隐马尔可夫模型的三个基本问题：n n评估问题：对于给定模型，求某个观察值序列的概率：对于给定模型，求某个观察值序列的概率P(P(|)。向前向前/向后算法向后算法：定义向前：定义向前/向后变量。采用动态规划算法，复杂度O(N2 2T)T)n n解码问题解码问题：对于给定模型和观察值序列，求可能性最大的状态序列。ViterbiViterbi算法算法：采用动态规划算法，复：采用动态规划算法，复杂度
49、杂度O(NO(N2 2T)n n学习问题学习问题：对于给定的一个观察值序列，调整参数，使得观察值出现的概率使得观察值出现的概率P(|)最大。向前最大。向前EM算法的一个特例，带隐变量的最大似然估计。Baum-WelchBaum-Welch算法算法。第51页，共87页，编辑于2022年，星期六n3.9 隐马尔可夫模型（续）隐马尔可夫模型（续）n n向前/向后算法：定义向前/向后变量：n n初始化：n n递归：n n终结：第52页，共87页，编辑于2022年，星期六n3.9 隐马尔可夫模型（续）隐马尔可夫模型（续）n nViterbi算法n n初始化：n n递归：n n终结：n n求S序列：第53
50、页，共87页，编辑于2022年，星期六n3.9 隐马尔可夫模型（续）隐马尔可夫模型（续）n nBaum-Welch算法n n主要步骤：1.初始模型（待训练模型）初始模型（待训练模型）l0,2.基于l l0 0以及观察值序列以及观察值序列s s，训练新模型，训练新模型l l；3.如果如果 logP(X|l)-log(P(X|l l0)Delta，说明训练已经达到预期效果，算法结束。4.否则，令否则，令l l0 l，继续第继续第2 2步工作步工作第54页，共87页，编辑于2022年，星期六n n3.10 支持向量机支持向量机n n支持向量机基本模型是针对线性可分情况下的最优分界面提出的。在这一条件