《数据挖掘算法wangy课件》由会员分享，可在线阅读，更多相关《数据挖掘算法wangy课件（87页珍藏版）》请在金锄头文库上搜索。
1、数据挖掘算法数据挖掘算法 WangYe2006.8数据挖掘算法数据挖掘算法wangywangy一、概念和术语n n1.1 数据挖掘数据挖掘 / 知识发现知识发现（1 1）数据挖掘数据挖掘数据挖掘数据挖掘是从存放在数据集中的大量数据挖掘出有趣是从存放在数据集中的大量数据挖掘出有趣知识的过程。知识的过程。（2 2）数据挖掘，又称为）数据挖掘，又称为数据库中知识发现数据库中知识发现数据库中知识发现数据库中知识发现（KnowledgeKnowledgeDiscoveryinDatabasesDiscoveryinDatabases）或）或知识发现知识发现知识发现知识发现，它是一个从大量数，它是一个从大
2、量数据中抽取挖掘出未知的、有价值的模式或规律等知识的非据中抽取挖掘出未知的、有价值的模式或规律等知识的非平凡过程，它与数据仓库有着密切的联系。平凡过程，它与数据仓库有着密切的联系。（3 3）广义的数据挖掘是指知识发现的全过程；狭义的数据）广义的数据挖掘是指知识发现的全过程；狭义的数据挖掘是指统计分析、机器学习等发现数据模式的智能方法，挖掘是指统计分析、机器学习等发现数据模式的智能方法，即偏重于模型和算法。即偏重于模型和算法。（4 4）数据库查询系统和专家系统）数据库查询系统和专家系统不是不是不是不是数据挖掘！在小规模数据挖掘！在小规模数据上的统计分析和机器学习过程也不应算作数据挖掘。数据上的统
3、计分析和机器学习过程也不应算作数据挖掘。 数据挖掘算法数据挖掘算法wangywangyn n1.2 机器学习机器学习（1）对于某类任务T和性能度量P，如果一个计算机程序在T上以P衡量的性能随着经验E而自我完善，那么这个计算机程序被称为在从经验E学习。（2）机器学习是知识发现的一种方法，是指一个系统通过执行某种过程而改进它处理某一问题的能力。数据挖掘算法数据挖掘算法wangywangyn n1.3 数据挖掘的对象数据挖掘的对象（1 1）关系型数据库、事务型数据库、面向对象的数）关系型数据库、事务型数据库、面向对象的数据库；据库；（2 2）数据仓库）数据仓库/多维数据库；多维数据库；（3 3）空间
4、数据（如地图信息）空间数据（如地图信息）（4 4）工程数据（如建筑、集成电路的信息）工程数据（如建筑、集成电路的信息）（5 5）文本和多媒体数据（如文本、图象、音频、视）文本和多媒体数据（如文本、图象、音频、视频数据）频数据）（6 6）时间相关的数据（如历史数据或股票交换数据）时间相关的数据（如历史数据或股票交换数据）（7 7）万维网（如半结构化的）万维网（如半结构化的HTMLHTML，结构化的，结构化的XMLXML以及其他网络信息）以及其他网络信息）数据挖掘算法数据挖掘算法wangywangyn n1.4 数据挖掘的步骤数据挖掘的步骤（1 1）数据清理（消除噪音或不一致数据，补缺）；）数据清
5、理（消除噪音或不一致数据，补缺）；（2 2）数据集成（多种数据源可以组合在一起）；）数据集成（多种数据源可以组合在一起）；（3 3）数据选择（从数据库中提取相关的数据）；）数据选择（从数据库中提取相关的数据）；（4 4）数据变换（变换成适合挖掘的形式）；）数据变换（变换成适合挖掘的形式）；（5 5）数据挖掘（使用智能方法提取数据模式）；）数据挖掘（使用智能方法提取数据模式）；（6 6）模式评估（识别提供知识的真正有趣模式）；）模式评估（识别提供知识的真正有趣模式）；（7 7）知识表示（可视化和知识表示技术）。）知识表示（可视化和知识表示技术）。数据挖掘算法数据挖掘算法wangywangyn n
6、1.5 支持数据挖掘的关键技术支持数据挖掘的关键技术（1）数据库/数据仓库/OLAP（2）数学/统计（回归分析：多元回归、自回归；判别分析：Bayes判别、Fisher判别、非参数判别；主成分分析、相关性分析；模糊集；粗糙集）（3）机器学习（聚类分析；关联规则；决策树；范例推理；贝叶斯网络；神经网络；支持向量机；遗传算法）（4）可视化：将数据、知识和规则转化为图形表现的形式。数据挖掘算法数据挖掘算法wangywangyn n1.6 数据仓库数据仓库（1 1）数据仓库数据仓库数据仓库数据仓库是一个面向主题的、集成的、随时间变是一个面向主题的、集成的、随时间变化的、非易失性数据的集合，用于支持管理
7、人员的化的、非易失性数据的集合，用于支持管理人员的决策。决策。（2 2）数据仓库是一种多个异种数据源在单个站点以统）数据仓库是一种多个异种数据源在单个站点以统一的模式组织的存储，以支持管理决策。数据仓库一的模式组织的存储，以支持管理决策。数据仓库技术包括数据清理、数据集成和技术包括数据清理、数据集成和联机分析处理联机分析处理联机分析处理联机分析处理（OLAPOLAP）。）。（3 3）数据仓库的逻辑结构是多维数据库。数据仓库的）数据仓库的逻辑结构是多维数据库。数据仓库的实际物理结构可以是关系数据存储或实际物理结构可以是关系数据存储或多维数据方多维数据方多维数据方多维数据方（CubeCube）。）
8、。（4 4）数据方是由）数据方是由维度维度维度维度（DimensionDimension）和）和度量度量度量度量（MeasureMeasure）定义的一种数据集，度量存放在由维度）定义的一种数据集，度量存放在由维度索引的数据方单元中。维度对应于模式中的属性组，索引的数据方单元中。维度对应于模式中的属性组，度量对应于与主题相关的事实数据。数据方的度量对应于与主题相关的事实数据。数据方的物化物化物化物化是指预计算并存储全部或部分单元中的度量。是指预计算并存储全部或部分单元中的度量。数据挖掘算法数据挖掘算法wangywangyn n1.7 数据仓库的模型数据仓库的模型（1）星形模式星形模式：最常见模
9、型；其中数据仓库包括一个大的、包含大批数据、不含冗余的中心表（事实表）；一组小的附属表（维表），每维一个。（2）雪花模式雪花模式：雪花模式是星型模式的变种，其中某些维表是规范化的，因而把数据进一步分解到附加的表中。（3）星系模式星系模式：多个事实表共享维表。这种模式可以看作星形模式集，因此称为星系模式，或事实星座。数据挖掘算法数据挖掘算法wangywangyn n1.8 典型的典型的OLAP操作操作（1 1）OLAPOLAP是一种多维数据分析技术。包括汇总、合并和聚是一种多维数据分析技术。包括汇总、合并和聚集等功能，以及从不同的角度观察信息的能力。集等功能，以及从不同的角度观察信息的能力。（2
10、 2）上卷上卷上卷上卷：从某一维度的更高概念层次观察数据方，获得：从某一维度的更高概念层次观察数据方，获得更概要的数据。它通过沿维的概念分层向上或维归约来实更概要的数据。它通过沿维的概念分层向上或维归约来实现。现。（3 3）下钻下钻下钻下钻：下钻是上卷的逆操作。它从某一维度的更低概：下钻是上卷的逆操作。它从某一维度的更低概念层次观察数据方，获得更详细的数据。下钻可以通过沿念层次观察数据方，获得更详细的数据。下钻可以通过沿维的概念分层向下或引入新的维来实现。维的概念分层向下或引入新的维来实现。（4 4）切片和切块切片和切块切片和切块切片和切块：切片操作在给定的数据方的选择一个维：切片操作在给定的
11、数据方的选择一个维的部分属性，获得一个较小的子数据方。切块操作通过对的部分属性，获得一个较小的子数据方。切块操作通过对选择两个或多个维的部分属性，获得一个较小的子数据方。选择两个或多个维的部分属性，获得一个较小的子数据方。（5 5）转轴转轴转轴转轴：是一种改变数据方二维展现形式的操作。它将：是一种改变数据方二维展现形式的操作。它将数据方的二维展现中的某些维度由行改为列，或由列改为数据方的二维展现中的某些维度由行改为列，或由列改为行。行。数据挖掘算法数据挖掘算法wangywangy二、数据准备n n现实世界的数据是不完整的不完整的（有些感兴趣的属性缺少属性值，或仅包含聚集数据），含噪音的含噪音的
12、（包含错误，或存在偏离期望的异常值），不一致的不一致的（例如，用于商品分类的部门编码存在差异）。n n需要数据清理数据清理、数据集成数据集成、数据选择数据选择、数数据变换据变换等技术对数据进行处理。数据挖掘算法数据挖掘算法wangywangyn n2.1 维归约维归约 / 特征提取特征提取n n2.1-1 决策树归约决策树归约（1）决策树归约构造一个类似于流程图的结构：其每个非叶子结点表示一个属性上的测试，每个分枝对应于测试的一个输出；每个叶子结点表示一个决策类。（2）在每个结点，算法选择“当前对分类最有帮助”的属性，出现在树中的属性形成归约后的属性子集。数据挖掘算法数据挖掘算法wangywa
13、ngyn n2.1-2 粗糙集归约粗糙集归约（1）粗糙集理论在数学意义上描述了知识的不确定性，它的特点是把用于分类的知识嵌入集合内，使分类与知识联系在一起。（2）知识的粒度、不可分辨关系、上近似、下近似、边界等概念见下图。数据挖掘算法数据挖掘算法wangywangyn n2.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）约简可以通过删除冗余的（不独立的
14、）属性而获得，约简包含的属性即为“对分类有帮助”的属性。数据挖掘算法数据挖掘算法wangywangyn n2.2 数据变换数据变换n n2.2-1 归一化与模糊化归一化与模糊化有限区间的归一化：有限区间的归一化：无限区间的归一化：无限区间的归一化：模糊隶属度：模糊隶属度：数据挖掘算法数据挖掘算法wangywangyn n2.2-2 核函数核函数（1 1）核函数的基本思想是将在）核函数的基本思想是将在低维特征向量线性不可低维特征向量线性不可分分的数据映射到线性可分的的数据映射到线性可分的高维特征空间高维特征空间中去。中去。（2 2）映射可以是显式的，也可以是隐式的。显式映射）映射可以是显式的，也
15、可以是隐式的。显式映射即找到一个映射关系即找到一个映射关系f f，使高维空间的特征向量，使高维空间的特征向量f f ( (x x) )可以被直接计算出来。可以被直接计算出来。（3 3）隐式映射，即引入一个核函数进行整体处理，就）隐式映射，即引入一个核函数进行整体处理，就避免了对的直接求避免了对的直接求f f ( (x x) )的计算困难。的计算困难。核函数核函数即某高即某高维特征空间中向量的内积，是核矩阵中的一个元素。维特征空间中向量的内积，是核矩阵中的一个元素。（4 4）并不是所有的实值函数）并不是所有的实值函数f f ( (x x) )都可以作为空间映射都可以作为空间映射的核函数，只有的核
16、函数，只有f f ( (x x) )是某一特征空间的内积时，即是某一特征空间的内积时，即符合符合MercerMercer条件条件，它才能成为核函数。，它才能成为核函数。 数据挖掘算法数据挖掘算法wangywangyn n2.2-2 核函数（续）核函数（续）n n多项式函数：n nn n高斯（RBF）函数：n nn n多层感知机函数：n n低维空间向量映射到高维空间向量举例：数据挖掘算法数据挖掘算法wangywangyn n2.3 数据压缩数据压缩n n2.3-1 离散化离散化n n离散化的用途：（1）适应某些仅接受离散值的算法；（2）减小数据的尺度。n n离散化的方法包括几下几种。n n（1）
17、等距分割；n n（2）聚类分割；n n（3）直方图分割；n n（4）基于熵的分割；n n（5）基于自然属性的分割。数据挖掘算法数据挖掘算法wangywangyn n2.3-2 回归回归n n回归和对数线性模型可以用来近似给定的数据。n n在线性回归线性回归中，用一条直线来模拟数据的生成规则。n n多元回归多元回归是线性回归的扩展，涉及多个预测变量。n n在多项式回归多项式回归中，通过对变量进行变换，可以将非线性模型转换成线性的，然后用最小平方和法求解。数据挖掘算法数据挖掘算法wangywangyn n2.3-2 回归（续）回归（续）n n利用线性回归可以为连续取值的函数建模。广义利用线性回归可
18、以为连续取值的函数建模。广义线性模型则可以用于对离散取值变量进行回归建线性模型则可以用于对离散取值变量进行回归建模。模。n n在广义线性模型中，因变量在广义线性模型中，因变量YY的变化速率是的变化速率是YY均均值的一个函数；这一点与线性回归不同。常见的值的一个函数；这一点与线性回归不同。常见的广义线性模型有：对数回归和泊松回归。广义线性模型有：对数回归和泊松回归。n n对数回归模型对数回归模型是利用一些事件发生的概率作为自是利用一些事件发生的概率作为自变量所建立的线性回归模型。变量所建立的线性回归模型。n n泊松回归模型泊松回归模型主要是描述数据出现次数的模型，主要是描述数据出现次数的模型，因
19、为它们常常表现为泊松分布。因为它们常常表现为泊松分布。数据挖掘算法数据挖掘算法wangywangyn n2.3-3 主成分分析（主成分分析（PCA）n nPCAPCA算法搜索算法搜索c c个最能代表数据的个最能代表数据的k-k-维正交向量；维正交向量；这里这里c c k k。这样，原来的数据投影到一个较小的。这样，原来的数据投影到一个较小的空间，导致数据压缩。步骤如下：空间，导致数据压缩。步骤如下： （1 1）对输入数据归一化，使得每个属性都落入相同）对输入数据归一化，使得每个属性都落入相同的区间。的区间。（2 2）PCAPCA计算计算c c个规范正交向量，作为归一化输入个规范正交向量，作为归
20、一化输入数据的基。这些是单位向量，每一个都垂直于另数据的基。这些是单位向量，每一个都垂直于另一个：称为主成分。输入数据是主要成分的线性一个：称为主成分。输入数据是主要成分的线性组合。组合。（3 3）对主成分按）对主成分按“ “意义意义” ”或强度降序排列，选择部或强度降序排列，选择部分主成分充当数据的一组新坐标轴分主成分充当数据的一组新坐标轴 。 数据挖掘算法数据挖掘算法wangywangyn n2.3-4 离散小波变换（离散小波变换（DWT）n n离散小波变换是一种线性离散小波变换是一种线性信号处理技术信号处理技术。该技术。该技术方法可以将一个数据向量转换为另一个数据向量方法可以将一个数据向
21、量转换为另一个数据向量（为小波相关系数）；且两个向量具有相同长度。（为小波相关系数）；且两个向量具有相同长度。n n可以舍弃转换后的数据向量中的一些小波相关系可以舍弃转换后的数据向量中的一些小波相关系数。保留所有大于用户指定阈值的小波系数，而数。保留所有大于用户指定阈值的小波系数，而将其它小波系数置为将其它小波系数置为0 0，以帮助提高数据处理的运，以帮助提高数据处理的运算效率。算效率。n n这一技术方法可以在保留数据主要特征情况下除这一技术方法可以在保留数据主要特征情况下除去数据中的噪声，因此该方法可以有效地进行数去数据中的噪声，因此该方法可以有效地进行数据清洗。据清洗。n n给定一组小波相
22、关系数，利用离散小波变换的逆给定一组小波相关系数，利用离散小波变换的逆运算还可以近似恢复原来的数据。运算还可以近似恢复原来的数据。数据挖掘算法数据挖掘算法wangywangyn n2.3-4 离散小波变换（续）离散小波变换（续）n n常用的小波函数包括Haar系列,Daubechies系列，Moret系列，Sym系列，Meyer系列，Coif系列。数据挖掘算法数据挖掘算法wangywangyn n2.3-5 潜在语义分析潜在语义分析n n潜在语义分析将样本映射到语义概念空间以发现潜在语义分析将样本映射到语义概念空间以发现样本数据之间的潜在语义联系。样本数据之间的潜在语义联系。 n n（1 1）
23、构造）构造“ “特征特征- -样本样本” ”矩阵，矩阵，“ “特征特征- -样本样本” ”矩矩阵中的每一列是对应于第阵中的每一列是对应于第i i个样本特征向量；个样本特征向量； n n（2 2）对该矩阵进行奇异值分解）对该矩阵进行奇异值分解(SVD)(SVD)；n n（3 3）用最大的）用最大的k k个奇异值所对应的个奇异值所对应的“ “特征特征- -语义语义” ”矩阵矩阵U Uk k和和“ “样本样本- -语义语义” ”矩阵矩阵VkVk以及最大的以及最大的k k个奇个奇异值重构异值重构“ “特征特征- -样本样本” ”矩阵。矩阵。下面两式分别代下面两式分别代表在语义空间特表在语义空间特征与特
24、征之间的征与特征之间的距离和距离和在语义空间在语义空间样本与样本之间样本与样本之间的距离的距离数据挖掘算法数据挖掘算法wangywangyn n2.3-6 聚类分析聚类分析n n聚类技术将数据元组视为对象。它将对象划分为聚类，使在一个聚类中的对象“类似”，但与其它聚类中的对象“不类似”。n n通常，类似性基于距离，用对象在空间中的“接近”程度定义。聚类的“质量”可以用“直径”表示；而直径是一个聚类中两个任意对象的最大距离。n n质心距离是聚类质量的另一种度量，它定义为由聚类质心（表示“平均对象”，或聚类空间中的平均点）到每个聚类对象的平均距离。数据挖掘算法数据挖掘算法wangywangyn n
25、2.3-6 聚类分析（续）聚类分析（续）k-meansk-means算法算法k-medoidsk-medoids算法算法数据挖掘算法数据挖掘算法wangywangy三、数据挖掘算法n n数据挖掘算法按挖掘目的可分为：数据挖掘算法按挖掘目的可分为：（1）概念描述（总结，对比等）（2）关联规则分析（3）分类与预测（信息自动分类，信息过滤，图像识别等）（4）聚类分析（5）异常分析（入侵检测，金融安全等）（6）趋势、演化分析（回归，序列模式挖掘）数据挖掘算法数据挖掘算法wangywangyn n按训练方式，机器学习可分为：按训练方式，机器学习可分为：按训练方式，机器学习可分为：按训练方式，机器学习可分
26、为： （1 1）有监督的学习有监督的学习；有训练样本，学习机通过学习获；有训练样本，学习机通过学习获得训练样本包含的知识，并用其作为判断测试样本得训练样本包含的知识，并用其作为判断测试样本的类别的依据。的类别的依据。（2 2）无监督的学习无监督的学习：无训练样本，仅根据测试样本的：无训练样本，仅根据测试样本的在特征空间分布情况判断其类别。在特征空间分布情况判断其类别。（3 3）半监督的学习半监督的学习：有少量训练样本，学习机以从训：有少量训练样本，学习机以从训练样本获得的知识为基础，结合测试样本的分布情练样本获得的知识为基础，结合测试样本的分布情况逐步修正已有知识，并判断测试样本的类别。况逐步
27、修正已有知识，并判断测试样本的类别。（4 4）强化学习强化学习：没有训练样本，但有对学习机每一步：没有训练样本，但有对学习机每一步是否更接近目标的奖惩措施。是否更接近目标的奖惩措施。数据挖掘算法数据挖掘算法wangywangyn n有监督的学习n n半监督的学习n n无监督的学习数据挖掘算法数据挖掘算法wangywangyn n3.1 关联规则挖掘关联规则挖掘n n关联规则挖掘发现大量数据中项集之间有趣的关关联规则挖掘发现大量数据中项集之间有趣的关联或相关联系。设联或相关联系。设I I =i i1 1 , i , i2 2 ,., i ,., im m 是项的集是项的集合。设任务相关的数据合。
28、设任务相关的数据D D是数据库事务的集合，是数据库事务的集合，其中每个事务其中每个事务T T是项的集合，使得是项的集合，使得T T I I。设。设A A是一是一个项集，事务个项集，事务T T包含包含A A当且仅当当且仅当A A T T。n n关联规则关联规则关联规则关联规则是形如是形如A A B B的蕴涵式，其中的蕴涵式，其中A A I I，B B I I，并且，并且A A B B=。规则。规则A A B B在事务集在事务集D D中成立，中成立，具有支持度具有支持度s s，其中，其中s s是是D D中事务包含中事务包含A A B B的百分的百分比。即，比。即，P P( (A A B) B)。规
29、则规则A A B B在事务集在事务集D D中具有中具有置信度置信度c c，如果，如果D D中包含中包含A A的事务同时也包含的事务同时也包含B B的百的百分比是分比是c c。这是条件概率。这是条件概率P P( (B|AB|A) )。即。即n nsupport support ( (A A B B)=)=P P( (A A B) B) n nconfidence confidence ( (A A B B)=)=P P( (B|AB|A) )数据挖掘算法数据挖掘算法wangywangyn n3.1 关联规则挖掘（续）关联规则挖掘（续）n nAprioriApriori性质性质：频繁项集的所有非空
30、子集都必须也：频繁项集的所有非空子集都必须也是频繁的。是频繁的。n nAprioriApriori性质基于如下观察：根据定义，如果项集性质基于如下观察：根据定义，如果项集I I不满足最小支持度阈值不满足最小支持度阈值s s，则，则I I不是频繁的，即不是频繁的，即P P( (I I) )s s。如果项。如果项A A添加到添加到I I，则结果项集（即，则结果项集（即I I A A）不）不可能比可能比I I更频繁出现。因此，更频繁出现。因此，I I A A也不是频繁的，也不是频繁的，即即P P( (I I A A)s s。n n该性质表明如果一个集合不能通过测试，则它的该性质表明如果一个集合不能通
31、过测试，则它的所有超集也都不能通过相同的测试。所有超集也都不能通过相同的测试。n n将将AprioriApriori性质应用于算法：下面算法的两个主要性质应用于算法：下面算法的两个主要步过程由步过程由连接连接和和剪枝剪枝组成。组成。数据挖掘算法数据挖掘算法wangywangyn n3.1 关联规则挖掘（续）关联规则挖掘（续）n n连接步连接步连接步连接步：为找：为找L Lk k，通过，通过L Lk - 1k - 1与自己连接产生候选与自己连接产生候选k k- -项集的集合。该候选项集的集合记作项集的集合。该候选项集的集合记作C Ck k。 C Ck k是是L Lk k的超集。扫描数据库，确定的
32、超集。扫描数据库，确定C Ck k中每个候选的计数，中每个候选的计数，将令计数值不小于最小支持度计数的（频繁的）将令计数值不小于最小支持度计数的（频繁的）所有候选加入所有候选加入L Lk k。n n剪枝步剪枝步剪枝步剪枝步：但但C Ck k可能很大，这样所涉及的计算量就可能很大，这样所涉及的计算量就很大。根据很大。根据AprioriApriori性质性质如果一个候选如果一个候选k k- -项集的项集的( (k k- -1)-1)-子集不在子集不在L Lk-1k-1中，则该候选也不可能是频繁的，中，则该候选也不可能是频繁的，从而可以由从而可以由C Ck k中删除。中删除。n nAprioriAp
33、riori性质性质( (逆反描述逆反描述) )：任何非频繁的：任何非频繁的( (k k-1)-1)-项集项集都不是可能是频繁都不是可能是频繁k k- -项集的子集。项集的子集。数据挖掘算法数据挖掘算法wangywangyn n3.2 决策树决策树n n决策树学习是归纳推理算法。它是一种逼近离散决策树学习是归纳推理算法。它是一种逼近离散函数的方法，且对噪声数据有很好的健壮性。在函数的方法，且对噪声数据有很好的健壮性。在这种方法中学习到的知识被表示为决策树，决策这种方法中学习到的知识被表示为决策树，决策树也能再被表示为多个树也能再被表示为多个if-thenif-then的规则，以提高可读的规则，以
34、提高可读性。性。n n基本决策树算法就是一个基本决策树算法就是一个贪心算法贪心算法。它采用自上。它采用自上而下、分而制之的递归方式来构造一个决策树而下、分而制之的递归方式来构造一个决策树n n通常，决策树是一种自顶向下增长树的贪婪算法，通常，决策树是一种自顶向下增长树的贪婪算法，在每个结点选取能最好地分类样例的属性。继续在每个结点选取能最好地分类样例的属性。继续这个过程直到这棵树能完美分类训练样例，或所这个过程直到这棵树能完美分类训练样例，或所有的属性都使用过了。有的属性都使用过了。“ “信息增益信息增益” ”用于衡量属用于衡量属性的价值。熵（性的价值。熵（entropyentropy）是一种
35、度量信息增益的）是一种度量信息增益的指标，它描述了样本的纯度（指标，它描述了样本的纯度（puritypurity）。下面是熵）。下面是熵的定义：的定义：n nEntropy=-PEntropy=-Pi ilog2Plog2Pi i数据挖掘算法数据挖掘算法wangywangyn n3.2 决策树（续）决策树（续）n n注意点：注意点：注意点：注意点：n n（1 1）避免过度拟合，应该适度剪枝；（）避免过度拟合，应该适度剪枝；（2 2）连续）连续值的离散化；（值的离散化；（3 3）处理缺失值的方法：最常见值、）处理缺失值的方法：最常见值、按概率分配；（按概率分配；（4 4）处理权重不同的属性）处理
36、权重不同的属性n n常用实现算法：常用实现算法：常用实现算法：常用实现算法：n nCARTCART、ID3ID3、ASSISTANTASSISTANT、C4.5C4.5数据挖掘算法数据挖掘算法wangywangyn n3.3 人工神经网络人工神经网络n n人工神经网络（ArtificialNeuralNetworks）提供了一种普遍而且实用的方法，来从样例中学习值为实数、离散或向量的函数。n n反向传播（BackPropagation）这样的算法使用梯度下降来调节网络参数以最佳拟合由输入/输出对组成的训练集合。n nBP网络的学习方法和目标：对网络的连接权值进行调整，使得对任一输入都能得到所期
37、望的输出。数据挖掘算法数据挖掘算法wangywangy常用的非线性作用函数是常用的非线性作用函数是SigmoidSigmoid函数函数，即，即f f ( (x x)=1/(1+e)=1/(1+e-x-x) )。在神经。在神经网络模型中，大量神经元节点按网络模型中，大量神经元节点按一定体系结构连接成网状。神经一定体系结构连接成网状。神经网络一般都具有输入层，隐层和网络一般都具有输入层，隐层和输出层。输出层。每个神经元都是一个结构相每个神经元都是一个结构相似的独立单元，它接受前一似的独立单元，它接受前一层传来的数据，并将这些数层传来的数据，并将这些数据的加权和输入非线性作用据的加权和输入非线性作用
38、函数中，最后将非线性作用函数中，最后将非线性作用函数的输出结果传递给后一函数的输出结果传递给后一层。层。数据挖掘算法数据挖掘算法wangywangy误差反向传播的过程误差反向传播的过程数据挖掘算法数据挖掘算法wangywangyn 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)快速识
39、别数据挖掘算法数据挖掘算法wangywangyn n3.4 朴素贝叶斯（朴素贝叶斯（Naive Bayes）分类器）分类器n n朴素贝叶斯分类器是一种基于贝叶斯理论的分类器。它的朴素贝叶斯分类器是一种基于贝叶斯理论的分类器。它的特点是以概率形式表达所有形式的不确定，学习和推理都特点是以概率形式表达所有形式的不确定，学习和推理都由概率规则实现，学习的结果可以解释为对不同可能的信由概率规则实现，学习的结果可以解释为对不同可能的信任程度。任程度。 n nP(H)P(H)是是先验概率先验概率先验概率先验概率，或，或H H的先验概率。的先验概率。P(H|X)P(H|X)是是后验概率后验概率后验概率后验概
40、率，或条件或条件X X下，下，H H的后验概率。后验概率的后验概率。后验概率P(H|X)P(H|X)比先验概率比先验概率P(H)P(H)基于更多的信息。基于更多的信息。P(H)P(H)是独立于是独立于X X的。的。n n假定数据样本世界由水果组成，用它们的颜色和形状描述。假定数据样本世界由水果组成，用它们的颜色和形状描述。假定假定X X表示红色和圆的，表示红色和圆的，H H表示假定表示假定X X是苹果，则是苹果，则P(H|X)P(H|X)反反映当我们看到映当我们看到X X是红色并是圆的时，我们对是红色并是圆的时，我们对X X是苹果的确信是苹果的确信程度。程度。数据挖掘算法数据挖掘算法wangy
41、wangy朴素贝叶斯分类能够奏效的前提是，朴素贝叶斯分类能够奏效的前提是，P(X|H)P(X|H) 相对比相对比较容易计算。假定较容易计算。假定X X表示红色和圆的，表示红色和圆的，H H表示假定表示假定X X是苹果；则是苹果；则P(X|H)P(X|H)表示已知苹果，它既红又圆的概表示已知苹果，它既红又圆的概率。率。数据挖掘算法数据挖掘算法wangywangyn n3.5 期望最大化（期望最大化（EM）n n期望最大化（EM）方法和朴素贝叶斯方法有着共同的理论基础。期望最大化是一种基于循环过程的最大似然参数估计方法，用于解决带缺失数据的参数估计问题。n n样本数据分为标记样本和未标记样本，按照
42、统计的观点，对于每一个样本的产生，其背后都有一个模型，即样本生成模型。样本生成模型的参数先由标记样本确定，再通过标记样本和利用当前模型判断标记的未标记样本共同调整。数据挖掘算法数据挖掘算法wangywangyn n3.5 期望最大化（续）期望最大化（续）n n如果参数适当，如果参数适当，EMEM算法能得到较好的分类结果，但计算算法能得到较好的分类结果，但计算速度相对较慢。其具体的步骤如下：速度相对较慢。其具体的步骤如下：n n一、初始参数估计，将未标记的样本按朴素贝叶斯分类方一、初始参数估计，将未标记的样本按朴素贝叶斯分类方法进行类标注。法进行类标注。n n二、反复迭代二、反复迭代E E步骤和
43、步骤和MM步骤，直到收敛。步骤，直到收敛。n n三、三、E E步骤：对于每个未标记的样本，按下式计算类标记步骤：对于每个未标记的样本，按下式计算类标记的期望值。的期望值。n n四、四、MM步骤：利用步骤：利用E E步骤计算出的期望值，按下式用已标记步骤计算出的期望值，按下式用已标记样本和未标记样本重新估计新的分类器参数。样本和未标记样本重新估计新的分类器参数。数据挖掘算法数据挖掘算法wangywangyn n3.6 K-最近邻分类最近邻分类n nK-K-近邻（近邻（K-NNK-NN）分类是）分类是基于范例基于范例的分类方法，它的分类方法，它的基本思想是：给定待分类样本后，考虑在训练的基本思想是
44、：给定待分类样本后，考虑在训练样本集中与该待分类样本距离最近（最相似）的样本集中与该待分类样本距离最近（最相似）的KK个样本，根据这个样本，根据这KK个样本中大多数样本所属的个样本中大多数样本所属的类别判定待分类样本的类别。类别判定待分类样本的类别。n n它的特例是它的特例是1-NN1-NN，即分类时选出待分类样本的最，即分类时选出待分类样本的最近邻，并以此最近邻的类标记来判断样本的类。近邻，并以此最近邻的类标记来判断样本的类。n nK-NNK-NN算法的优点在于它有较高的精确程度，研究算法的优点在于它有较高的精确程度，研究表明，表明，K-NNK-NN的分类效果要明显好于朴素贝叶斯分的分类效果
45、要明显好于朴素贝叶斯分类、决策树分类。类、决策树分类。数据挖掘算法数据挖掘算法wangywangyn n3.6 K-最近邻分类（续）最近邻分类（续）n n最近邻分类的算法步骤如下：n n一、以向量空间模型的形式描述各训练样本。n n二、在全部训练样本集中选出与待分类样本最相似的K个样本。K值的确定目前没有很好的方法，一般采用先定一个100左右的初始值，然后再调整。n n三、将待分类样本标记为其K个邻居中所属最多的那个类别中。数据挖掘算法数据挖掘算法wangywangyn n3.7 遗传算法遗传算法n n遗传算法易于并行处理，其依据是自然界进化和遗传算法易于并行处理，其依据是自然界进化和适者生存
46、的原则。遗传学习开始如下：创建若干适者生存的原则。遗传学习开始如下：创建若干个由随机产生的个体组成的初始个由随机产生的个体组成的初始群体群体群体群体。每个个体。每个个体用一个二进位串表示。用一个二进位串表示。n n形成由当前群体中最适合的个体组成新的群体，形成由当前群体中最适合的个体组成新的群体，以及这些规则的子女。个体的以及这些规则的子女。个体的适合度适合度适合度适合度用某一目标用某一目标函数来评估。函数来评估。n n子女通过使用诸如交叉和变异等遗传操作来创建。子女通过使用诸如交叉和变异等遗传操作来创建。在在交叉交叉交叉交叉操作中，来自个体对的子串交换，形成新操作中，来自个体对的子串交换，形
47、成新的个体对。在的个体对。在变异变异变异变异操作中，个体中随机选择的位操作中，个体中随机选择的位被反转。被反转。数据挖掘算法数据挖掘算法wangywangyn n3.7 遗传算法（续）遗传算法（续）n nFitnessFitness：适应度评分函数，为给定假设赋予一个：适应度评分函数，为给定假设赋予一个评估得分。评估得分。n nFitnessFitness_ _thresholdthreshold：指定终止判据的阈值。：指定终止判据的阈值。n np p：群体中包含的假设数量。：群体中包含的假设数量。r r：每一步中通过交：每一步中通过交叉取代群体成员的比例。叉取代群体成员的比例。m m：变异率
48、。：变异率。n n初始化群体：初始化群体：P P随机产生的随机产生的p p个假设个假设n n评估：评估：对于对于P P中的每一个中的每一个h h，计算，计算FitnessFitness( (h h) )n n当当 FitnessFitness( (h h)FitnessFitness_ _thresholdthreshold，做：，做：n n产生新的一代产生新的一代P PS S：数据挖掘算法数据挖掘算法wangywangyn n3.7 遗传算法（续）遗传算法（续）n n选择：选择：用概率方法选择用概率方法选择P P的的(1-(1-r r) )p p个成员加入个成员加入P PS S。从从P P中
49、选择假设中选择假设hihi的概率的概率P(P(hihi) )通过下面公式计算：通过下面公式计算：n n交叉：交叉：根据上面给出的根据上面给出的P(P(h hi i) )，从，从P P中按概率选择中按概率选择r r p p/2/2对假设。对于每一对假设对假设。对于每一对假设 2应用交叉应用交叉算子产生两个后代。把所有的后代加入算子产生两个后代。把所有的后代加入P PS S。n n变异：变异：使用均匀的概率从使用均匀的概率从P PS S中选择中选择m m百分比的成百分比的成员。对于选出的每个成员，在它的表示中随机选员。对于选出的每个成员，在它的表示中随机选择一个位取反。择一个位取反。n n更新：更
50、新：P PP PS S。n n评估：评估：对于对于P P中的每一个中的每一个h h计算计算FitnessFitness( (h h) )n n从从P P中返回适应度最高的假设。中返回适应度最高的假设。数据挖掘算法数据挖掘算法wangywangyn n3.8 聚类分析聚类分析n n为达到全局最优，基于划分的聚类会要求穷举所为达到全局最优，基于划分的聚类会要求穷举所有可能的划分。聚类技术将数据元组视为对象。有可能的划分。聚类技术将数据元组视为对象。它将对象划分为群或聚类，使得在一个聚类中的它将对象划分为群或聚类，使得在一个聚类中的对象对象“ “类似类似” ”，但与其它聚类中的对象，但与其它聚类中的
51、对象“ “不类似不类似” ”。n n绝大多数应用采用了以下两个比较流行的绝大多数应用采用了以下两个比较流行的基于划基于划分的方法分的方法，这些基于划分的聚类方法对在中小规，这些基于划分的聚类方法对在中小规模的数据库中发现球状簇很适用。模的数据库中发现球状簇很适用。n n（1 1）k-meansk-means算法算法，在该算法中，每个簇用该簇，在该算法中，每个簇用该簇中对象的平均值来表示。中对象的平均值来表示。n n（2 2）k-medoidsk-medoids算法算法，在该算法中，每个簇用接，在该算法中，每个簇用接近聚类中心的一个对象来表示。近聚类中心的一个对象来表示。数据挖掘算法数据挖掘算法
52、wangywangyn3.8 聚类分析（续）聚类分析（续）n n常用的相似程度度量n n余弦夹角：Dice系数：Jaccard系数：数据挖掘算法数据挖掘算法wangywangyn n3.8 聚类分析（续）聚类分析（续）n n基于层次的方法：基于层次的方法：层次的方法对给定数据集合进层次的方法对给定数据集合进行层次的分解。根据层次的分解如何形成，层次行层次的分解。根据层次的分解如何形成，层次的方法可以被分为凝聚或分裂方法。的方法可以被分为凝聚或分裂方法。 （ChameleonChameleon，CURECURE，BIRCHBIRCH） n n基于密度的方法：基于密度的方法：只要临近区域的密度超过
53、某个只要临近区域的密度超过某个阈值，就继续聚类。避免仅生成球状聚类。阈值，就继续聚类。避免仅生成球状聚类。（DBSCANDBSCAN，OPTICSOPTICS，DENCLUEDENCLUE）n n基于网格的方法：基于网格的方法：基于网格的方法把对象空间量基于网格的方法把对象空间量化为有限数目的单元，所有的聚类操作都在这个化为有限数目的单元，所有的聚类操作都在这个量化的空间上进行。这种方法的主要优点是它的量化的空间上进行。这种方法的主要优点是它的处理速度很快。（处理速度很快。（STINGSTING，CLIQUECLIQUE，WaveClusterWaveCluster）n n基于模型的方法：基于
54、模型的方法：为每个簇假设一个模型，发现为每个簇假设一个模型，发现数据对模型的最好匹配。（数据对模型的最好匹配。（COBWEBCOBWEB，CLASSITCLASSIT，AutoClassAutoClass） 数据挖掘算法数据挖掘算法wangywangyn n3.9 隐马尔可夫模型隐马尔可夫模型n n对于一个随机事件，有一个观察值序列：对于一个随机事件，有一个观察值序列：O O1 1,.,O,.,OT T。该。该事件隐含着一个状态序列：事件隐含着一个状态序列：X X1 1,.,X,.,XT Tn n假设假设1 1：马尔可夫性，：马尔可夫性，P(XP(Xi i|X|Xi-1i-1XX1 1)=P(
55、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,B,),A,B,)n n其中：其中： X X=Q=Q1 1,.,Q,.,QN N ：状态的有限集合；：状态的有限集合；n n
56、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) )：初始状态分布。：初始状态分布。数据挖掘算法数据挖掘算法wangywangyn n3.9 隐马尔可夫模型（续）隐马尔可夫模型（续）n n令令 =A,B,=A,B,
57、 为给定为给定HMMHMM的参数，的参数，n n令令 =O=O1 1,.,O,.,OT T 为观察值序列，为观察值序列，n n隐马尔可夫模型的三个基本问题：隐马尔可夫模型的三个基本问题： n n评估问题评估问题：对于给定模型，求某个观察值序列的：对于给定模型，求某个观察值序列的概率概率P(P( | | ) )。向前向前/ /向后算法向后算法：定义向前：定义向前/ /向后变向后变量。采用动态规划算法，复杂度量。采用动态规划算法，复杂度O(NO(N2 2T)T)n n解码问题解码问题：对于给定模型和观察值序列，求可能：对于给定模型和观察值序列，求可能性最大的状态序列。性最大的状态序列。Viterb
58、iViterbi算法算法：采用动态规划：采用动态规划算法，复杂度算法，复杂度O(NO(N2 2T)T)n n学习问题学习问题：对于给定的一个观察值序列，调整参：对于给定的一个观察值序列，调整参数数 ，使得观察值出现的概率，使得观察值出现的概率P(P( | | ) )最大。向前最大。向前EMEM算法的一个特例，带隐变量的最大似然估计。算法的一个特例，带隐变量的最大似然估计。Baum-WelchBaum-Welch算法算法。数据挖掘算法数据挖掘算法wangywangyn3.9 隐马尔可夫模型（续）隐马尔可夫模型（续）n n向前/向后算法：定义向前/向后变量：n n初始化：n n递归：n n终结：数
59、据挖掘算法数据挖掘算法wangywangyn3.9 隐马尔可夫模型（续）隐马尔可夫模型（续）n nViterbiViterbi算法算法n n初始化：n n递归：n n终结：n n求S序列：数据挖掘算法数据挖掘算法wangywangyn3.9 隐马尔可夫模型（续）隐马尔可夫模型（续）n nBaum-Welch算法n n主要步骤：1.1.初始模型（待训练模型）初始模型（待训练模型） l l0 0, ,2.2.基于基于l l0 0 以及观察值序列以及观察值序列s s，训练新模型，训练新模型 l l；3.3.如果如果 logP(X|logP(X|l l)-log(P(X|)-log(P(X|l l0
60、0)Delta)Delta，说明训练说明训练已经达到预期效果，已经达到预期效果， 算法结束。算法结束。4.4.否则，令否则，令l l00 l l ，继续第继续第2 2步工作步工作 数据挖掘算法数据挖掘算法wangywangyn n3.10 支持向量机支持向量机n n支持向量机基本模型是针对线性可分情况下的最支持向量机基本模型是针对线性可分情况下的最优分界面提出的。在这一条件下，正类和反类训优分界面提出的。在这一条件下，正类和反类训练样本可用练样本可用超平面超平面完全正确地分开。完全正确地分开。n n设线性可分样本集合为设线性可分样本集合为( (x xi i, ,y yi i) )，i i=1,
61、=1,n n；x xR Rd d，y y+1,-1+1,-1是类别标记。支持向量机工作是类别标记。支持向量机工作的机理可描述为：寻找一个超平面的机理可描述为：寻找一个超平面w w x x+b b=0=0，该，该平面把两类训练样本点完全正确地分开，即满足平面把两类训练样本点完全正确地分开，即满足且且；同时满足两；同时满足两类训练点到此超平面的最近距离之和，即类训练点到此超平面的最近距离之和，即“ “间隔间隔”(Margin)”(Margin)，达到最大。，达到最大。n n满足上述条件的分界面就是满足上述条件的分界面就是最优分界面最优分界面，经过两，经过两类样本中距离最优分类面最近的点，且平行于最
62、类样本中距离最优分类面最近的点，且平行于最优分界面的超平面优分界面的超平面H H1 1、H H2 2（边界超平面）上的训（边界超平面）上的训练样本称为练样本称为支持向量支持向量，即图中带圈的点。，即图中带圈的点。数据挖掘算法数据挖掘算法wangywangyn n3.10 支持向量机（续）支持向量机（续）n n根据最近距离之和最大以及正确分离两类样本这两个条件，根据最近距离之和最大以及正确分离两类样本这两个条件，可以构造约束极值问题：见（可以构造约束极值问题：见（1 1）式。）式。n n通过拉格朗日乘数法并引入拉格朗日乘数，该约束极值问通过拉格朗日乘数法并引入拉格朗日乘数，该约束极值问题就可以转
63、化成一个求解较为简单的对偶问题，通过寻求题就可以转化成一个求解较为简单的对偶问题，通过寻求该对偶问题的最优解，就可以得到原问题的最优解。构造该对偶问题的最优解，就可以得到原问题的最优解。构造分类器判决函数：见（分类器判决函数：见（2 2）式。）式。n n（2 2）式中，）式中，sgnsgn(.)(.)是取符号函数，产生是取符号函数，产生+1+1或或-1-1两种结果。两种结果。当测试无标记的测试数据时，根据上式的计算结果就可判当测试无标记的测试数据时，根据上式的计算结果就可判断无标记测试数据属于正类还是反类。断无标记测试数据属于正类还是反类。（1）（2）数据挖掘算法数据挖掘算法wangywang
64、yn n3.10 支持向量机（续）支持向量机（续）n n由于噪声或其他因素的影响，两类数据可能有少数的融合由于噪声或其他因素的影响，两类数据可能有少数的融合或交叉。引入松弛变量或交叉。引入松弛变量x x使得分类器在训练后仍可以存在使得分类器在训练后仍可以存在一些错分样本，不但要使两类样本之间的间隔尽量大，同一些错分样本，不但要使两类样本之间的间隔尽量大，同时还要使错分的样本的松弛变量之和尽可能的小，即时还要使错分的样本的松弛变量之和尽可能的小，即其中，其中，x x为松弛变量，满足为松弛变量，满足x xi i00；C C为大于零的折衷因为大于零的折衷因子，它调和了间隔距离和错子，它调和了间隔距离
65、和错分样本数之间的关系，分样本数之间的关系，C C趋趋近于无穷大时即为线性可分近于无穷大时即为线性可分的形式。为了提高支持向量的形式。为了提高支持向量机的推广能力，机的推广能力，C C通常取为通常取为较大的数。较大的数。 数据挖掘算法数据挖掘算法wangywangyn n3.10 支持向量机（续）支持向量机（续）n n解决线性不可分数据问题的方法是将低维空间的线性不可解决线性不可分数据问题的方法是将低维空间的线性不可分数据映射到高维的线性可分空间中。分数据映射到高维的线性可分空间中。n n支持向量机通过非线性映射支持向量机通过非线性映射f f ( (x x) )把数据由低维空间向高维把数据由低
66、维空间向高维空间映射，在高维空间为低维数据构造线性分离超平面。空间映射，在高维空间为低维数据构造线性分离超平面。该分离超平面对应着原特征空间上的一个分割超曲面。该分离超平面对应着原特征空间上的一个分割超曲面。n n在高维特征空间上所有涉及在高维特征空间上所有涉及f f ( (x x) )的计算及判决函数都以的计算及判决函数都以f f ( (x x) )的内积形式出现，因而可以引入一个核函数进行整体的内积形式出现，因而可以引入一个核函数进行整体处理从而避免了对处理从而避免了对f f ( (x x) )的直接计算，使所有的计算仍在原的直接计算，使所有的计算仍在原空间进行。空间进行。 数据挖掘算法数
67、据挖掘算法wangywangyn n3.10 支持向量机（续）支持向量机（续）n n统计学习理论认为：学习机误判未知数据类别的实际风险统计学习理论认为：学习机误判未知数据类别的实际风险与学习机的训练误差并不完全一致，对于两类分类问题，与学习机的训练误差并不完全一致，对于两类分类问题，实际风险与学习机的训练误差之间至少以实际风险与学习机的训练误差之间至少以1-1-h h 的概率（的概率（00h h 11）满足下式：）满足下式： n n根据统计学习的理论，对于两类分类的支持向量机，在线根据统计学习的理论，对于两类分类的支持向量机，在线性可分的情况下，它的推广误差的上界（以性可分的情况下，它的推广误
68、差的上界（以1-1-d d 的概率的概率（00d d 11）保证）为：）保证）为：n n其中，其中，mm是连续分类正确的样本数；是连续分类正确的样本数；g g=1/|=1/|w w| |，是间隔距，是间隔距离的一半；离的一半；R R是一个特征空间球的半径，它将全部样本包是一个特征空间球的半径，它将全部样本包含在其中。含在其中。 数据挖掘算法数据挖掘算法wangywangyn n3.11 关系学习关系学习n n关系学习所涉及的问题比传统机器学习中涉及到的关系学习所涉及的问题比传统机器学习中涉及到的问题高一个层次。该类问题的假设空间庞大，结构问题高一个层次。该类问题的假设空间庞大，结构复杂；需要加
69、入领域知识反映问题的内在结构。复杂；需要加入领域知识反映问题的内在结构。n n关系学习中知识的表示：原子；析取、合取、蕴含、关系学习中知识的表示：原子；析取、合取、蕴含、非；验证、等价、涵蕴等。句子由上述元素组成。非；验证、等价、涵蕴等。句子由上述元素组成。n n一阶一阶HornHorn子句子句：仅包含一个肯定文字的子句。：仅包含一个肯定文字的子句。n n有三种类型的有三种类型的HornHorn子句：单一原子（事实）；一个子句：单一原子（事实）；一个蕴涵（规则）；一个否定文字的集合（目标）。蕴涵（规则）；一个否定文字的集合（目标）。数据挖掘算法数据挖掘算法wangywangyn n3.11 关
70、系学习（续）关系学习（续）n n归纳逻辑编程归纳逻辑编程(InductiveLogicProgramming,(InductiveLogicProgramming,ILP)ILP)是处理关系学习领域问题的重要方法。它是是处理关系学习领域问题的重要方法。它是归纳学习和逻辑程序结合的产物。归纳学习和逻辑程序结合的产物。n nILPILP用于一阶逻辑的概念学习和逻辑程序的合成。用于一阶逻辑的概念学习和逻辑程序的合成。ILPILP系统处理分类任务时主要采用两种方式：覆系统处理分类任务时主要采用两种方式：覆盖方法和分治方法。盖方法和分治方法。n n子句空间子句空间由形如：由形如：H HL L1 1,L,
71、L2 2,L,Lm m 的一阶子句构成。的一阶子句构成。n n-包容关系包容关系：假设：假设c c和和cc是两个程序子句，子句是两个程序子句，子句c-c-包容子句包容子句c,c,如果存在一个替换如果存在一个替换 使得使得ccccn n基于基于ILPILP的常用方法有：的常用方法有：ProgolProgol、FOILFOIL、TLIDETLIDE、ICLICL数据挖掘算法数据挖掘算法wangywangy四、模型上的模型n n4.1 装袋装袋 / 提升提升n n给定给定s s个样本的集合个样本的集合S S。装袋装袋（BaggingBagging）过程如下。）过程如下。对于迭代对于迭代t t(t t
72、 =1,2,.,=1,2,.,T T ) )，训练集，训练集S St t采用放回选样，采用放回选样，由原始样本集由原始样本集S S选取。选取。n n由于使用放回选样，由于使用放回选样，S S的某些样本可能不在的某些样本可能不在S St t中，中，而其它的可能出现多次。而其它的可能出现多次。n n由每个训练集由每个训练集S St t学习，得到一个分类法学习，得到一个分类法C Ct t。为对一。为对一个未知的样本个未知的样本X X分类，每个分类法分类，每个分类法C Ct t返回它的类预返回它的类预测，算作一票。测，算作一票。n n装袋的分类法装袋的分类法C C* *统计得票，并将得票最高的类赋统计
73、得票，并将得票最高的类赋予予X X。通过取得票的平均值，装袋也可以用于连续。通过取得票的平均值，装袋也可以用于连续值的预测。值的预测。数据挖掘算法数据挖掘算法wangywangyn n4.1 装袋装袋 / 提升（续）提升（续）n n提升提升（BoostingBoosting）过程如下：每个训练样本赋予）过程如下：每个训练样本赋予一个权，并学习得到一系列分类法。一个权，并学习得到一系列分类法。n n对于迭代对于迭代t t(t t =1,2,.,=1,2,.,T T ) )，学习得到分类法，学习得到分类法C Ct t后，后，更新权，使得随后的分类法更新权，使得随后的分类法C Ct+1t+1“ “更
74、关注更关注” ”C Ct t的分的分类错误。类错误。n n最终的提升分类法最终的提升分类法C C* *组合每个分类法的表决，这组合每个分类法的表决，这里每个分类法的表决是其准确率的函数。里每个分类法的表决是其准确率的函数。n n通过取得票的平均值，提升算法也可以扩充到连通过取得票的平均值，提升算法也可以扩充到连续值预测。续值预测。数据挖掘算法数据挖掘算法wangywangyn n4.2 共同训练（共同训练（Co-Training）n n共同训练算法用两个不同的共同训练算法用两个不同的“ “视图视图” ”（即特征集（即特征集合）来描述文本的特征。合）来描述文本的特征。n n基本思路：每个视图对应
75、一个学习机，而每个学基本思路：每个视图对应一个学习机，而每个学习机都根据自身已学到的规律来标记习机都根据自身已学到的规律来标记“ “最有把握最有把握” ”的无标记样本，然后将这个（或这几个）新标的无标记样本，然后将这个（或这几个）新标记的样本加入训练样本，并扩展后的训练样本提记的样本加入训练样本，并扩展后的训练样本提供给另一个学习机进行学习。如此反复，直到满供给另一个学习机进行学习。如此反复，直到满足一定的条件为止。足一定的条件为止。n n该算法中所用到的两个视图需要满足以下两个条该算法中所用到的两个视图需要满足以下两个条件：首先，每个特征集合对文本分类学习来说都件：首先，每个特征集合对文本分
76、类学习来说都是是充分充分的；其次，在给定类别标记的条件下，两的；其次，在给定类别标记的条件下，两个特征集合个特征集合相互独立相互独立。数据挖掘算法数据挖掘算法wangywangyn n4.3 主动学习主动学习 / 被动学习被动学习n n主动学习主动学习在学习过程中可以根据学习进程，选择在学习过程中可以根据学习进程，选择最有利于分类器性能的样本来进一步训练分类器，最有利于分类器性能的样本来进一步训练分类器，它能有效地减少评价样本的数量；它能有效地减少评价样本的数量；n n被动学习被动学习只是随机地选择训练样本，被动地接受只是随机地选择训练样本，被动地接受这些样本的信息进行学习。这些样本的信息进行
77、学习。n n主动学习是实现监督学习过程的一个有效的方法。主动学习是实现监督学习过程的一个有效的方法。在主动学习过程中，分类器主动地选择对其在主动学习过程中，分类器主动地选择对其“ “最最有帮助有帮助” ”的一组子样本进行学习，而不是被动地的一组子样本进行学习，而不是被动地接受训练集。接受训练集。n n“ “最有帮助最有帮助” ”的样本指的是对当前分类器来说，的样本指的是对当前分类器来说，归属最不确定的样本。即当前分类器归属最不确定的样本。即当前分类器最难以区分最难以区分的样本。通常情况下，主动学习的计算复杂度比的样本。通常情况下，主动学习的计算复杂度比一般的监督学习过程要显著得低。一般的监督学
78、习过程要显著得低。数据挖掘算法数据挖掘算法wangywangyn n4.3 主动学习主动学习 / 被动学习（续）被动学习（续）n n初始状态下，候选样本集中所有的样本都未带类初始状态下，候选样本集中所有的样本都未带类别标注，根据先验知识或者随机地从候选样本集别标注，根据先验知识或者随机地从候选样本集中选择少量样本并标注它们的类别，构造初始训中选择少量样本并标注它们的类别，构造初始训练样本集，确保初始训练样本集中至少包含有一练样本集，确保初始训练样本集中至少包含有一个正例样本和一个负例样本。个正例样本和一个负例样本。n n在上述初始训练样本集上训练一个分类器，并采在上述初始训练样本集上训练一个分
79、类器，并采用某种针对该分类器采样算法，从候选样本集中用某种针对该分类器采样算法，从候选样本集中选择最有利于提高分类器性能的样本，手工标注选择最有利于提高分类器性能的样本，手工标注其类别并加入训练样本集，再重新训练分类器。其类别并加入训练样本集，再重新训练分类器。n n重复以上过程，直到候选样本集为空或达到某种重复以上过程，直到候选样本集为空或达到某种要求。主动学习是一个循环反复的过程。要求。主动学习是一个循环反复的过程。数据挖掘算法数据挖掘算法wangywangyn n在主动学习的模型中，全部数据被分为两部分，在主动学习的模型中，全部数据被分为两部分，一部分是一部分是带标签的样本集带标签的样本
80、集X X，另一部分是，另一部分是无标签的无标签的样本集样本集U U。主动学习的模型还包括了一个在带标。主动学习的模型还包括了一个在带标签的样本集签的样本集X X上训练的上训练的学习机学习机L L和一个和一个决策模块决策模块q q。决策模块决策模块q q用来决定用来决定U U中的哪一些样本应该被选出中的哪一些样本应该被选出标记标签，并加入带标签的样本集标记标签，并加入带标签的样本集X X。更新后的。更新后的X X将在下一个轮次被用于训练学习机将在下一个轮次被用于训练学习机L L。主动学习的。主动学习的框架模型如图。框架模型如图。根据决策模块根据决策模块q q的不同的不同工作机理，主动学习方工作机
81、理，主动学习方法又可以被分为两大类：法又可以被分为两大类：其一是其一是不确定取样方法不确定取样方法；另一是另一是委员会咨询方法委员会咨询方法。数据挖掘算法数据挖掘算法wangywangyn n4.4 直推式学习直推式学习n n直推式学习的思想来源于前面提到的机器学习的直推式学习的思想来源于前面提到的机器学习的困境：一方面获取已知标签的样本代价高昂；另困境：一方面获取已知标签的样本代价高昂；另一方面获取无标签的样本要相对容易得多。一方面获取无标签的样本要相对容易得多。n n直推式学习的学习过程恰恰可以将大量无标签的直推式学习的学习过程恰恰可以将大量无标签的测试集样本所携带的分类信息，通过迭代逐步
82、转测试集样本所携带的分类信息，通过迭代逐步转移到了最终的分类器中去。移到了最终的分类器中去。n n由于测试样本易于获得、数量较多，直推式学习由于测试样本易于获得、数量较多，直推式学习机能够更好地描述整体样本空间上的数据分布特机能够更好地描述整体样本空间上的数据分布特性，使测试样本的分类结果更为准确。性，使测试样本的分类结果更为准确。数据挖掘算法数据挖掘算法wangywangyn n4.4 直推式学习（续）直推式学习（续）n n在多数情况下，人们只对测试文本的分类结果感在多数情况下，人们只对测试文本的分类结果感兴趣，这时就没有必要非得寻求具有良好泛化能兴趣，这时就没有必要非得寻求具有良好泛化能力
83、的规则，而只要求分类器能对这些特定的文本力的规则，而只要求分类器能对这些特定的文本做出正确分类即可。做出正确分类即可。n n它在目前已知标签样本十分紧缺，而未知标签样它在目前已知标签样本十分紧缺，而未知标签样本易于获得的条件下，有着非常重要的现实意义。本易于获得的条件下，有着非常重要的现实意义。数据挖掘算法数据挖掘算法wangywangyn n4.5 广义广义EM算法算法n nEMEM算法可用于许多问题框架，其中需要估计一组算法可用于许多问题框架，其中需要估计一组描述基准概率分布的参数描述基准概率分布的参数 ，只给定了由此分布产，只给定了由此分布产生的全部数据中能观察到的一部分。生的全部数据中
84、能观察到的一部分。n n一般地，令一般地，令X X= 代表在同样的实例中代表在同样的实例中未观察到的数据，并令未观察到的数据，并令Y Y= =X XZ Z代表全体数据。代表全体数据。n n注意到未观察到的注意到未观察到的Z Z可被看作随机变量，它的概率可被看作随机变量，它的概率分布依赖于未知参数分布依赖于未知参数 和已知数据和已知数据X X。类似地，。类似地，Y Y是是一随机变量，因为它是由随机变量一随机变量，因为它是由随机变量Z Z来定义的。来定义的。n n在在EMEM算法的一般形式中，用算法的一般形式中，用h h来代表参数来代表参数 的假设的假设值，而值，而h h 代表在代表在EMEM的每
85、次迭代中修改的假设。的每次迭代中修改的假设。数据挖掘算法数据挖掘算法wangywangyn n4.5 广义广义EM算法（续）算法（续）n nEMEM算法通过搜寻使算法通过搜寻使E ElnlnP P( (Y Y| |h h)最大的最大的h h 来寻找极来寻找极大似然假设大似然假设h h 。此期望值是在。此期望值是在Y Y所遵循的概率分布所遵循的概率分布上计算，此分布由未知参数上计算，此分布由未知参数 确定。确定。n n首先，首先，P P( (Y Y| |h h) )是给定假设是给定假设h h 下全部数据下全部数据Y Y的似然性。的似然性。其合理性在于我们要寻找一个其合理性在于我们要寻找一个h h
86、 使该量的某函数使该量的某函数值最大化。值最大化。n n其次，使该量的对数其次，使该量的对数lnlnP P( (Y Y| |h h) )最大化也使最大化也使P P( (Y Y| |h h) )最大化。最大化。n n第三，引入期望值第三，引入期望值E ElnlnP P( (Y Y| |h h)是因为全部数据是因为全部数据Y Y本本身也是一随机变量。已知全部数据身也是一随机变量。已知全部数据Y Y是观察到的是观察到的X X和未观察到的和未观察到的Z Z的合并，我们必须在未观察到的的合并，我们必须在未观察到的Z Z的可能值上取平均，并以相应的概率为权值。的可能值上取平均，并以相应的概率为权值。数据挖
87、掘算法数据挖掘算法wangywangyn n4.5 广义广义EM算法（续）算法（续）n n在EM算法的一般形式里，重复以下两个步骤直至收敛。n n步骤1：估计（E）步骤：使用当前假设h和观察到的数据X来估计Y上的概率分布以计算Q(h|h)。n n步骤2：最大化（M）步骤：将假设h替换为使Q函数最大化的假设h：数据挖掘算法数据挖掘算法wangywangyn4.6 强化学习强化学习n n强化学习的模型如图所示n n通过Agent与环境的交互进行学习。Agent与环境的交互接口包括行动（Action）、回报（Reward）和状态（State）。n n交互过程可以表述为如下形式：n n每一步，Agen
88、t根据策略选择一个行动执行，然后感知下一步状态和即时回报，通过经验再修改自己的策略。Agent的目标就是最大化长期回报。数据挖掘算法数据挖掘算法wangywangyn n4.6 强化学习（续）强化学习（续）n n马尔可夫过程是四元组M=。其中S是状态集。A是行动集，A(s)表示状态s下可执行的行动。n nT=SAS0，1是状态转换模型，T(s,a,s)表示状态s下执行行动a到达状态s 的概率，且满足s T(s,a,s)=1。n nR=SASR是即时回报函数，R(s,a,s)表示状态s下执行行动a到达状态s后可以得到的即时回报。数据挖掘算法数据挖掘算法wangywangyn n4.6 强化学习（
89、续）强化学习（续）n n转换模型和回报函数是环境的一部分，描述了环境模型，且只与当前状态和行动有关，与以前的状态和行动都没有关系，体现了马尔可夫特性。n nAgent为了完成任务，必须知道每个行动的长远回报，而不仅仅是即时回报。而长远回报必须经过一定时间的延迟之后才可以获得。n n有终任务和持续任务可以统一起来，他们的长期回报是或数据挖掘算法数据挖掘算法wangywangyn n4.6 强化学习（续）强化学习（续）n nAgent与环境交互的学习中选择行动的方法称为策略:SA0,1，(s,a)表示在状态s下选择行动a的概率。n n策略的一个退化形式为:SA，称为确定性策略，表示在状态s下行动a
90、的执行概率为1，其它行动均为0。Q学习是最常用的强化学习技术。值函数Q函数数据挖掘算法数据挖掘算法wangywangyn n4.6 强化学习（续）强化学习（续）n n学习的目的是找到一个最优策略。设有策略和，若对所有状态sS都有V(s)V(s)，则称策略比策略好。n n这样就总存在一个策略，它比其它所有策略都好，称为最优策略*。n n若最优策略对应的状态评价函数记为V*，则对所有状态sS，有V*(s)=maxV(s)。n n对所有状态sS，所有行动aA(s)，有Q*(s)=maxQ(s)。数据挖掘算法数据挖掘算法wangywangyn n4.6 强化学习（续）强化学习（续）n n三种计算“值函
91、数”V(s)方法：n n动态规划法：已知环境模型T和R，每步进行迭代。n nMonteCarlo法：没有环境模型，根据经验学习。只考虑有终任务，任务结束后对所有的回报进行平均。n n时序差分法：没有环境模型，根据经验学习。每步进行迭代，不需要等任务完成。数据挖掘算法数据挖掘算法wangywangyn n4.6 强化学习（续）强化学习（续）n n在在多多AgentAgent系统系统中，环境在多个中，环境在多个AgentAgent的联合动作的联合动作下进行状态的迁移。对于单个下进行状态的迁移。对于单个AgentAgent来讲，由于其来讲，由于其只能确定自身只能确定自身AgentAgent的行为动作
92、，因此体现出一种的行为动作，因此体现出一种行为动作上的行为动作上的“ “部分感知部分感知” ”，从而产生出另一种，从而产生出另一种形式的非标准马尔可夫环境。形式的非标准马尔可夫环境。n n多多AgentAgent强化学习的技术包括：强化学习的技术包括：合作多合作多AgentAgent强化强化学习（适用于分布、同构、合作环境）；基于平学习（适用于分布、同构、合作环境）；基于平衡解多衡解多AgentAgent强化学习（适用于同构或异构、合作强化学习（适用于同构或异构、合作或竞争环境）；最佳响应多或竞争环境）；最佳响应多AgentAgent强化学习（适用强化学习（适用于异构、竞争环境）。于异构、竞争
93、环境）。n n多多AgentAgent强化学习机制被广泛应用到各个领域，例强化学习机制被广泛应用到各个领域，例如游戏、邮件路由选择、电梯群控系统以及机器如游戏、邮件路由选择、电梯群控系统以及机器人设计等等。人设计等等。数据挖掘算法数据挖掘算法wangywangyn n4.6 强化学习（续）强化学习（续）n n在对策模型中，每个在对策模型中，每个AgentAgent获得的瞬时奖惩不仅仅取决于获得的瞬时奖惩不仅仅取决于自身的动作，同时还依赖于其他自身的动作，同时还依赖于其他AgentAgent的动作。的动作。n n马尔可夫对策马尔可夫对策 在在n n个个AgentAgent的系统中，定义离散的状态
94、集的系统中，定义离散的状态集S S，AgentAgent动作集动作集A Ai i的集合的集合A A。n n联合奖赏函数联合奖赏函数R Ri i：S S A A1 1A An n S S R R；n n状态转移函数状态转移函数T T：S S A A1 1A An nS S00，11。n n每个每个AgentAgent目标都是最大化期望折扣奖赏和。目标都是最大化期望折扣奖赏和。 数据挖掘算法数据挖掘算法wangywangyn n5.1 分类精度评价指标分类精度评价指标n n理想的分类器应该将所有属于某一类的样本标记理想的分类器应该将所有属于某一类的样本标记为该类；且不将任何一个不属于该类的样本标记
95、为该类；且不将任何一个不属于该类的样本标记为该类。可以采有两个指标用来评价分类器的性为该类。可以采有两个指标用来评价分类器的性能：准确率（查准率）和召回率能：准确率（查准率）和召回率( (查全率查全率) )。对于。对于某一特定类别某一特定类别C Ci i ，n n准确率准确率(P)=(P)=n n召回率召回率(R)=(R)=五、性能评估数据挖掘算法数据挖掘算法wangywangyn n5.1 分类精度评价指标（续）分类精度评价指标（续）n n对于同一分类器，这准确率和查全率的变化趋势对于同一分类器，这准确率和查全率的变化趋势通常是相反的，片面追求其中一个指标而完全不通常是相反的，片面追求其中一
96、个指标而完全不顾及另一个是没有意义的。顾及另一个是没有意义的。n n为综合考虑准确率和查全率，可以使用一种能够为综合考虑准确率和查全率，可以使用一种能够全面评价分类器性能的指标：全面评价分类器性能的指标：F-1F-1。n nF-1=F-1=n nF-1F-1综合考虑了上述两指标，且偏向于准确率和查综合考虑了上述两指标，且偏向于准确率和查全率中较小的一个，只有当准确率和查全率都较全率中较小的一个，只有当准确率和查全率都较大时，大时，F-1F-1指标才会比较大。指标才会比较大。数据挖掘算法数据挖掘算法wangywangyn n5.1 分类精度评价指标（续）分类精度评价指标（续）n n多数分类器可以
97、通过调整参数获得不同的准确率多数分类器可以通过调整参数获得不同的准确率和查全率，当分类器的参数调节到正好使准确率和查全率，当分类器的参数调节到正好使准确率和查全率相等时，该值称为和查全率相等时，该值称为P/RP/R无损耗无损耗( (平衡平衡) )点。点。它也是一种综合考虑准确率和查全率的指标。它也是一种综合考虑准确率和查全率的指标。 n n在综合考虑全部类别的条件下，精确度在综合考虑全部类别的条件下，精确度(Accuracy)(Accuracy)也是一个常用的指标，它是指所有分也是一个常用的指标，它是指所有分类正确的样本数在所有样本中所占的比例。类正确的样本数在所有样本中所占的比例。n n精确
98、度精确度(A)=(A)=数据挖掘算法数据挖掘算法wangywangyn n5.2 分类器泛化性能分类器泛化性能n n分类器的泛化性能，是指在某一训练集上训练过以分类器的泛化性能，是指在某一训练集上训练过以后的分类器适应该训练集以外的数据的性能，也称后的分类器适应该训练集以外的数据的性能，也称为可扩展性。泛化性能好的分类器不但对训练集中为可扩展性。泛化性能好的分类器不但对训练集中的数据准确分类，也能对其他数据准确分类。的数据准确分类，也能对其他数据准确分类。n n在在k k- -折交叉验证折交叉验证中，初试数据被划分成中，初试数据被划分成k k个互不相个互不相交的子集或交的子集或“ “折折” ”
99、S S 1 1, ,S S 2 2,.,.,S S k k，每个折的大小，每个折的大小大致相等。训练和测试进行大致相等。训练和测试进行k k次。在第次。在第i i次迭代，次迭代，S S i i用作测试集，其余的子集都用于训练分类法。用作测试集，其余的子集都用于训练分类法。n n扣留测试扣留测试（Hold-outHold-out）是将训练集随机地分成两部）是将训练集随机地分成两部分，一部分用于训练学习机，记作分，一部分用于训练学习机，记作S Straintrain，另一部分，另一部分用于测试，记作用于测试，记作S Svalval。Hold-outHold-out测试的误差按下式计测试的误差按下式
100、计算：算：数据挖掘算法数据挖掘算法wangywangyn n5.2 分类器泛化性能（续）分类器泛化性能（续）n n解鞋带法解鞋带法（BootstrapBootstrap）测试是一种估计训练误差）测试是一种估计训练误差偏差的方法，它以偏差的方法，它以BootstrapBootstrap样本进行多次训练，样本进行多次训练，并评价它们的总偏差。并评价它们的总偏差。n nBootstrapBootstrap样本是通过替换法从训练样本中独立提样本是通过替换法从训练样本中独立提取出来的。取出来的。BootstrapBootstrap测试是一种计算代价非常高测试是一种计算代价非常高的评估方法。的评估方法。n
101、 n留一法留一法（LeaveOneOutLeaveOneOut）是一种特殊的交叉验证，）是一种特殊的交叉验证，它令它令n n等于训练集个数，即每次只抽取一个作为测等于训练集个数，即每次只抽取一个作为测试样本。试样本。n n留一法错误的计算留一法错误是推广误差的几乎留一法错误的计算留一法错误是推广误差的几乎无偏估计。无偏估计。数据挖掘算法数据挖掘算法wangywangyn n5.2 分类器泛化性能（续）分类器泛化性能（续）n n发生发生留一法错误留一法错误最少的模型的泛化能力最好，这最少的模型的泛化能力最好，这时模型的参数是学习机最佳的参数。时模型的参数是学习机最佳的参数。n n直接进行留一法验
102、证的代价是高昂的。它必须进直接进行留一法验证的代价是高昂的。它必须进行行N N次（次（N N为训练集样本数）训练才能统计出留一为训练集样本数）训练才能统计出留一法错误发生的次数。法错误发生的次数。n n为避免大量的学习机训练次数，一些学者提出了为避免大量的学习机训练次数，一些学者提出了只需进行一次训练即可估计出留一法错误发生次只需进行一次训练即可估计出留一法错误发生次数的留一法错误估计方法。数的留一法错误估计方法。n n估计方法包括的估计方法包括的R-MR-M估计估计、xaxa估计估计、SpanSpan估计估计以以及及GCKLGCKL和和GACVGACV等。等。 数据挖掘算法数据挖掘算法wan
103、gywangyn n5.3 分类器的其他性能分类器的其他性能n n除了准确性、可扩展性之外，还有除了准确性、可扩展性之外，还有速度速度和和可理解可理解性性也可以作为分类器的比较指标。也可以作为分类器的比较指标。n n基于有监督学习的分类器速度包括训练速度和决基于有监督学习的分类器速度包括训练速度和决策速度，通常，其决策速度远快于训练速度。策速度，通常，其决策速度远快于训练速度。n n基于无监督学习的分类器仅有一个决策的过程，基于无监督学习的分类器仅有一个决策的过程，通常比较慢；基于半监督学习的分类器一般需要通常比较慢；基于半监督学习的分类器一般需要通过反复训练获得决策结果，其速度也很慢。通过反复训练获得决策结果，其速度也很慢。n n可理解性是指规则是否易于被人类理解。例如，可理解性是指规则是否易于被人类理解。例如，决策树的发现的规则就远比神经网络所获得的权决策树的发现的规则就远比神经网络所获得的权值易于理解。值易于理解。数据挖掘算法数据挖掘算法wangywangy
