《数据挖掘算法》PPT课件.ppt

《《数据挖掘算法》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《数据挖掘算法》PPT课件.ppt（87页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据挖掘算法数据挖掘算法 WangYe2006.8一、概念和术语n n1.1 数据挖掘数据挖掘/知识发现知识发现（1 1）数据挖掘数据挖掘数据挖掘数据挖掘是从存放在数据集中的大量数据挖掘出有趣是从存放在数据集中的大量数据挖掘出有趣知识的过程。知识的过程。（2 2）数据挖掘，又称为）数据挖掘，又称为数据库中知识发现数据库中知识发现数据库中知识发现数据库中知识发现（KnowledgeKnowledgeDiscoveryinDatabasesDiscoveryinDatabases）或）或知识发现知识发现知识发现知识发现，它是一个从大量数，它是一个从大量数据中抽取挖掘出未知的、有价值的模式或规律等知

2、识的非据中抽取挖掘出未知的、有价值的模式或规律等知识的非平凡过程，它与数据仓库有着密切的联系。平凡过程，它与数据仓库有着密切的联系。（3 3）广义的数据挖掘是指知识发现的全过程；狭义的数据）广义的数据挖掘是指知识发现的全过程；狭义的数据挖掘是指统计分析、机器学习等发现数据模式的智能方法，挖掘是指统计分析、机器学习等发现数据模式的智能方法，即偏重于模型和算法。即偏重于模型和算法。（4 4）数据库查询系统和专家系统）数据库查询系统和专家系统不是不是不是不是数据挖掘！在小规模数据挖掘！在小规模数据上的统计分析和机器学习过程也不应算作数据挖掘。数据上的统计分析和机器学习过程也不应算作数据挖掘。n n1

3、.2 机器学习机器学习（1）对于某类任务T和性能度量P，如果一个计算机程序在T上以P衡量的性能随着经验E而自我完善，那么这个计算机程序被称为在从经验E学习。（2）机器学习是知识发现的一种方法，是指一个系统通过执行某种过程而改进它处理某一问题的能力。n n1.3 数据挖掘的对象数据挖掘的对象（1 1）关系型数据库、事务型数据库、面向对象的数）关系型数据库、事务型数据库、面向对象的数据库；据库；（2 2）数据仓库）数据仓库/多维数据库；多维数据库；（3 3）空间数据（如地图信息）空间数据（如地图信息）（4 4）工程数据（如建筑、集成电路的信息）工程数据（如建筑、集成电路的信息）（5 5）文本和多媒

4、体数据（如文本、图象、音频、视）文本和多媒体数据（如文本、图象、音频、视频数据）频数据）（6 6）时间相关的数据（如历史数据或股票交换数据）时间相关的数据（如历史数据或股票交换数据）（7 7）万维网（如半结构化的）万维网（如半结构化的HTMLHTML，结构化的，结构化的XMLXML以及其他网络信息）以及其他网络信息）n n1.4 数据挖掘的步骤数据挖掘的步骤（1 1）数据清理（消除噪音或不一致数据，补缺）；）数据清理（消除噪音或不一致数据，补缺）；（2 2）数据集成（多种数据源可以组合在一起）；）数据集成（多种数据源可以组合在一起）；（3 3）数据选择（从数据库中提取相关的数据）；）数据选择（

5、从数据库中提取相关的数据）；（4 4）数据变换（变换成适合挖掘的形式）；）数据变换（变换成适合挖掘的形式）；（5 5）数据挖掘（使用智能方法提取数据模式）；）数据挖掘（使用智能方法提取数据模式）；（6 6）模式评估（识别提供知识的真正有趣模式）；）模式评估（识别提供知识的真正有趣模式）；（7 7）知识表示（可视化和知识表示技术）。）知识表示（可视化和知识表示技术）。n n1.5 支持数据挖掘的关键技术支持数据挖掘的关键技术（1）数据库/数据仓库/OLAP（2）数学/统计（回归分析：多元回归、自回归；判别分析：Bayes判别、Fisher判别、非参数判别；主成分分析、相关性分析；模糊集；粗糙集）

6、（3）机器学习（聚类分析；关联规则；决策树；范例推理；贝叶斯网络；神经网络；支持向量机；遗传算法）（4）可视化：将数据、知识和规则转化为图形表现的形式。n n1.6 数据仓库数据仓库（1 1）数据仓库数据仓库数据仓库数据仓库是一个面向主题的、集成的、随时间变是一个面向主题的、集成的、随时间变化的、非易失性数据的集合，用于支持管理人员的化的、非易失性数据的集合，用于支持管理人员的决策。决策。（2 2）数据仓库是一种多个异种数据源在单个站点以统）数据仓库是一种多个异种数据源在单个站点以统一的模式组织的存储，以支持管理决策。数据仓库一的模式组织的存储，以支持管理决策。数据仓库技术包括数据清理、数据集

7、成和技术包括数据清理、数据集成和联机分析处理联机分析处理联机分析处理联机分析处理（OLAPOLAP）。）。（3 3）数据仓库的逻辑结构是多维数据库。数据仓库的）数据仓库的逻辑结构是多维数据库。数据仓库的实际物理结构可以是关系数据存储或实际物理结构可以是关系数据存储或多维数据方多维数据方多维数据方多维数据方（CubeCube）。）。（4 4）数据方是由）数据方是由维度维度维度维度（DimensionDimension）和）和度量度量度量度量（MeasureMeasure）定义的一种数据集，度量存放在由维度）定义的一种数据集，度量存放在由维度索引的数据方单元中。维度对应于模式中的属性组，索引的数据

8、方单元中。维度对应于模式中的属性组，度量对应于与主题相关的事实数据。数据方的度量对应于与主题相关的事实数据。数据方的物化物化物化物化是指预计算并存储全部或部分单元中的度量。是指预计算并存储全部或部分单元中的度量。n n1.7 数据仓库的模型数据仓库的模型（1）星形模式星形模式：最常见模型；其中数据仓库包括一个大的、包含大批数据、不含冗余的中心表（事实表）；一组小的附属表（维表），每维一个。（2）雪花模式雪花模式：雪花模式是星型模式的变种，其中某些维表是规范化的，因而把数据进一步分解到附加的表中。（3）星系模式星系模式：多个事实表共享维表。这种模式可以看作星形模式集，因此称为星系模式，或事实星座

9、。n n1.8 典型的典型的OLAP操作操作（1 1）OLAPOLAP是一种多维数据分析技术。包括汇总、合并和聚是一种多维数据分析技术。包括汇总、合并和聚集等功能，以及从不同的角度观察信息的能力。集等功能，以及从不同的角度观察信息的能力。（2 2）上卷上卷上卷上卷：从某一维度的更高概念层次观察数据方，获得：从某一维度的更高概念层次观察数据方，获得更概要的数据。它通过沿维的概念分层向上或维归约来实更概要的数据。它通过沿维的概念分层向上或维归约来实现。现。（3 3）下钻下钻下钻下钻：下钻是上卷的逆操作。它从某一维度的更低概：下钻是上卷的逆操作。它从某一维度的更低概念层次观察数据方，获得更详细的数据

10、。下钻可以通过沿念层次观察数据方，获得更详细的数据。下钻可以通过沿维的概念分层向下或引入新的维来实现。维的概念分层向下或引入新的维来实现。（4 4）切片和切块切片和切块切片和切块切片和切块：切片操作在给定的数据方的选择一个维：切片操作在给定的数据方的选择一个维的部分属性，获得一个较小的子数据方。切块操作通过对的部分属性，获得一个较小的子数据方。切块操作通过对选择两个或多个维的部分属性，获得一个较小的子数据方。选择两个或多个维的部分属性，获得一个较小的子数据方。（5 5）转轴转轴转轴转轴：是一种改变数据方二维展现形式的操作。它将：是一种改变数据方二维展现形式的操作。它将数据方的二维展现中的某些维

11、度由行改为列，或由列改为数据方的二维展现中的某些维度由行改为列，或由列改为行。行。二、数据准备n n现实世界的数据是不完整的不完整的（有些感兴趣的属性缺少属性值，或仅包含聚集数据），含噪音的含噪音的（包含错误，或存在偏离期望的异常值），不一致的不一致的（例如，用于商品分类的部门编码存在差异）。n n需要数据清理数据清理、数据集成数据集成、数据选择数据选择、数数据变换据变换等技术对数据进行处理。n n2.1 维归约维归约/特征提取特征提取n n2.1-1 决策树归约决策树归约（1）决策树归约构造一个类似于流程图的结构：其每个非叶子结点表示一个属性上的测试，每个分枝对应于测试的一个输出；每个叶子结

12、点表示一个决策类。（2）在每个结点，算法选择“当前对分类最有帮助”的属性，出现在树中的属性形成归约后的属性子集。n n2.1-2 粗糙集归约粗糙集归约（1）粗糙集理论在数学意义上描述了知识的不确定性，它的特点是把用于分类的知识嵌入集合内，使分类与知识联系在一起。（2）知识的粒度、不可分辨关系、上近似、下近似、边界等概念见下图。n n2.1-2 粗糙集归约（续）粗糙集归约（续）（3）令Q代表属性的集合。qQ是一个属性，如果IND(Qq)=IND(Q)，则q在S中不是独立的；否则称q在S中是独立的。（4）若集合满足IND(R)=IND(Q)且R中的每一个属性都是独立的，则R被称为Q的一个“约简”，

13、记作R=RED(Q)。（5）约简可以通过删除冗余的（不独立的）属性而获得，约简包含的属性即为“对分类有帮助”的属性。n n2.2 数据变换数据变换n n2.2-1 归一化与模糊化归一化与模糊化有限区间的归一化：有限区间的归一化：无限区间的归一化：无限区间的归一化：模糊隶属度：模糊隶属度：n n2.2-2 核函数核函数（1 1）核函数的基本思想是将在）核函数的基本思想是将在低维特征向量线性不可低维特征向量线性不可分分的数据映射到线性可分的的数据映射到线性可分的高维特征空间高维特征空间中去。中去。（2 2）映射可以是显式的，也可以是隐式的。显式映射）映射可以是显式的，也可以是隐式的。显式映射即找到

14、一个映射关系即找到一个映射关系f f，使高维空间的特征向量，使高维空间的特征向量f f(x x)可以被直接计算出来。可以被直接计算出来。（3 3）隐式映射，即引入一个核函数进行整体处理，就）隐式映射，即引入一个核函数进行整体处理，就避免了对的直接求避免了对的直接求f f(x x)的计算困难。的计算困难。核函数核函数即某高即某高维特征空间中向量的内积，是核矩阵中的一个元素。维特征空间中向量的内积，是核矩阵中的一个元素。（4 4）并不是所有的实值函数）并不是所有的实值函数f f(x x)都可以作为空间映射都可以作为空间映射的核函数，只有的核函数，只有f f(x x)是某一特征空间的内积时，即是某一

15、特征空间的内积时，即符合符合MercerMercer条件条件，它才能成为核函数。，它才能成为核函数。n n2.2-2 核函数（续）核函数（续）n n多项式函数：n nn n高斯（RBF）函数：n nn n多层感知机函数：n n低维空间向量映射到高维空间向量举例：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）基于自然属性的分割。n n2.3-2 回归回归n n回归和对数线

16、性模型可以用来近似给定的数据。n n在线性回归线性回归中，用一条直线来模拟数据的生成规则。n n多元回归多元回归是线性回归的扩展，涉及多个预测变量。n n在多项式回归多项式回归中，通过对变量进行变换，可以将非线性模型转换成线性的，然后用最小平方和法求解。n n2.3-2 回归（续）回归（续）n n利用线性回归可以为连续取值的函数建模。广义利用线性回归可以为连续取值的函数建模。广义线性模型则可以用于对离散取值变量进行回归建线性模型则可以用于对离散取值变量进行回归建模。模。n n在广义线性模型中，因变量在广义线性模型中，因变量YY的变化速率是的变化速率是YY均均值的一个函数；这一点与线性回归不同。

17、常见的值的一个函数；这一点与线性回归不同。常见的广义线性模型有：对数回归和泊松回归。广义线性模型有：对数回归和泊松回归。n n对数回归模型对数回归模型是利用一些事件发生的概率作为自是利用一些事件发生的概率作为自变量所建立的线性回归模型。变量所建立的线性回归模型。n n泊松回归模型泊松回归模型主要是描述数据出现次数的模型，主要是描述数据出现次数的模型，因为它们常常表现为泊松分布。因为它们常常表现为泊松分布。n n2.3-3 主成分分析（主成分分析（PCA）n nPCAPCA算法搜索算法搜索c c个最能代表数据的个最能代表数据的k-k-维正交向量；维正交向量；这里这里c c k k。这样，原来的数

18、据投影到一个较小的。这样，原来的数据投影到一个较小的空间，导致数据压缩。步骤如下：空间，导致数据压缩。步骤如下：（1 1）对输入数据归一化，使得每个属性都落入相同）对输入数据归一化，使得每个属性都落入相同的区间。的区间。（2 2）PCAPCA计算计算c c个规范正交向量，作为归一化输入个规范正交向量，作为归一化输入数据的基。这些是单位向量，每一个都垂直于另数据的基。这些是单位向量，每一个都垂直于另一个：称为主成分。输入数据是主要成分的线性一个：称为主成分。输入数据是主要成分的线性组合。组合。（3 3）对主成分按）对主成分按“意义意义”或强度降序排列，选择部或强度降序排列，选择部分主成分充当数据

19、的一组新坐标轴分主成分充当数据的一组新坐标轴。n n2.3-4 离散小波变换（离散小波变换（DWT）n n离散小波变换是一种线性离散小波变换是一种线性信号处理技术信号处理技术。该技术。该技术方法可以将一个数据向量转换为另一个数据向量方法可以将一个数据向量转换为另一个数据向量（为小波相关系数）；且两个向量具有相同长度。（为小波相关系数）；且两个向量具有相同长度。n n可以舍弃转换后的数据向量中的一些小波相关系可以舍弃转换后的数据向量中的一些小波相关系数。保留所有大于用户指定阈值的小波系数，而数。保留所有大于用户指定阈值的小波系数，而将其它小波系数置为将其它小波系数置为0 0，以帮助提高数据处理的

20、运，以帮助提高数据处理的运算效率。算效率。n n这一技术方法可以在保留数据主要特征情况下除这一技术方法可以在保留数据主要特征情况下除去数据中的噪声，因此该方法可以有效地进行数去数据中的噪声，因此该方法可以有效地进行数据清洗。据清洗。n n给定一组小波相关系数，利用离散小波变换的逆给定一组小波相关系数，利用离散小波变换的逆运算还可以近似恢复原来的数据。运算还可以近似恢复原来的数据。n n2.3-4 离散小波变换（续）离散小波变换（续）n n常用的小波函数包括Haar系列,Daubechies系列，Moret系列，Sym系列，Meyer系列，Coif系列。n n2.3-5 潜在语义分析潜在语义分析

21、n n潜在语义分析将样本映射到语义概念空间以发现潜在语义分析将样本映射到语义概念空间以发现样本数据之间的潜在语义联系。样本数据之间的潜在语义联系。n n（1 1）构造）构造“特征特征-样本样本”矩阵，矩阵，“特征特征-样本样本”矩矩阵中的每一列是对应于第阵中的每一列是对应于第i i个样本特征向量；个样本特征向量；n n（2 2）对该矩阵进行奇异值分解）对该矩阵进行奇异值分解(SVD)(SVD)；n n（3 3）用最大的）用最大的k k个奇异值所对应的个奇异值所对应的“特征特征-语义语义”矩阵矩阵U Uk k和和“样本样本-语义语义”矩阵矩阵VkVk以及最大的以及最大的k k个奇个奇异值重构异值

22、重构“特征特征-样本样本”矩阵。矩阵。下面两式分别代下面两式分别代表在语义空间特表在语义空间特征与特征之间的征与特征之间的距离和距离和在语义空间在语义空间样本与样本之间样本与样本之间的距离的距离n n2.3-6 聚类分析聚类分析n n聚类技术将数据元组视为对象。它将对象划分为聚类，使在一个聚类中的对象“类似”，但与其它聚类中的对象“不类似”。n n通常，类似性基于距离，用对象在空间中的“接近”程度定义。聚类的“质量”可以用“直径”表示；而直径是一个聚类中两个任意对象的最大距离。n n质心距离是聚类质量的另一种度量，它定义为由聚类质心（表示“平均对象”，或聚类空间中的平均点）到每个聚类对象的平均

23、距离。n n2.3-6 聚类分析（续）聚类分析（续）k-meansk-means算法算法k-medoidsk-medoids算法算法三、数据挖掘算法n n数据挖掘算法按挖掘目的可分为：数据挖掘算法按挖掘目的可分为：（1）概念描述（总结，对比等）（2）关联规则分析（3）分类与预测（信息自动分类，信息过滤，图像识别等）（4）聚类分析（5）异常分析（入侵检测，金融安全等）（6）趋势、演化分析（回归，序列模式挖掘）n n按训练方式，机器学习可分为：按训练方式，机器学习可分为：按训练方式，机器学习可分为：按训练方式，机器学习可分为：（1 1）有监督的学习有监督的学习；有训练样本，学习机通过学习获；有训练

24、样本，学习机通过学习获得训练样本包含的知识，并用其作为判断测试样本得训练样本包含的知识，并用其作为判断测试样本的类别的依据。的类别的依据。（2 2）无监督的学习无监督的学习：无训练样本，仅根据测试样本的：无训练样本，仅根据测试样本的在特征空间分布情况判断其类别。在特征空间分布情况判断其类别。（3 3）半监督的学习半监督的学习：有少量训练样本，学习机以从训：有少量训练样本，学习机以从训练样本获得的知识为基础，结合测试样本的分布情练样本获得的知识为基础，结合测试样本的分布情况逐步修正已有知识，并判断测试样本的类别。况逐步修正已有知识，并判断测试样本的类别。（4 4）强化学习强化学习：没有训练样本，

25、但有对学习机每一步：没有训练样本，但有对学习机每一步是否更接近目标的奖惩措施。是否更接近目标的奖惩措施。n n有监督的学习n n半监督的学习n n无监督的学习n n3.1 关联规则挖掘关联规则挖掘n n关联规则挖掘发现大量数据中项集之间有趣的关关联规则挖掘发现大量数据中项集之间有趣的关联或相关联系。设联或相关联系。设I I =i i1 1,i,i2 2,.,i,.,im m 是项的集是项的集合。设任务相关的数据合。设任务相关的数据D D是数据库事务的集合，是数据库事务的集合，其中每个事务其中每个事务T T是项的集合，使得是项的集合，使得T T I I。设。设A A是一是一个项集，事务个项集，事

26、务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)。规则规则A A B B在事务集在事务集D D中具有中具有置信度置信度c c，如果，如果D D中包含中包含A A的事务同时也包含的事务同时也包含B B的百的百分比是分比是c c。这是条件概率。

27、这是条件概率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)n n3.1 关联规则挖掘（续）关联规则挖掘（续）n nAprioriApriori性质性质：频繁项集的所有非空子集都必须也：频繁项集的所有非空子集都必须也是频繁的。是频繁的。n nAprioriApriori性质基于如下观察：根据定义，如果项集性质基于如下观察：根据定义，如果项集I I不满足最小支持度阈值不满足最小支持度阈值s s，则，则I I不是频繁的，即不是频繁的，即P

28、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该性质表明如果一个集合不能通过测试，则它的该性质表明如果一个集合不能通过测试，则它的所有超集也都不能通过相同的测试。所有超集也都不能通过相同的测试。n n将将AprioriApriori性质应用于算法：下面算法的两个主要性质应用于算法：下面算法的两个主要步过程由步过程由连接连接和和剪枝剪枝组成。组成。n n3.1 关联规则挖掘（续）关联规则挖掘（续

29、）n n连接步连接步连接步连接步：为找：为找L Lk k，通过，通过L Lk-1k-1与自己连接产生候选与自己连接产生候选k k-项集的集合。该候选项集的集合记作项集的集合。该候选项集的集合记作C Ck k。C Ck k是是L Lk k的超集。扫描数据库，确定的超集。扫描数据库，确定C Ck k中每个候选的计数，中每个候选的计数，将令计数值不小于最小支持度计数的（频繁的）将令计数值不小于最小支持度计数的（频繁的）所有候选加入所有候选加入L Lk k。n n剪枝步剪枝步剪枝步剪枝步：但但C Ck k可能很大，这样所涉及的计算量就可能很大，这样所涉及的计算量就很大。根据很大。根据AprioriAp

30、riori性质性质如果一个候选如果一个候选k k-项集的项集的(k k-1)-1)-子集不在子集不在L Lk-1k-1中，则该候选也不可能是频繁的，中，则该候选也不可能是频繁的，从而可以由从而可以由C Ck k中删除。中删除。n nAprioriApriori性质性质(逆反描述逆反描述)：任何非频繁的：任何非频繁的(k k-1)-1)-项集项集都不是可能是频繁都不是可能是频繁k k-项集的子集。项集的子集。n n3.2 决策树决策树n n决策树学习是归纳推理算法。它是一种逼近离散决策树学习是归纳推理算法。它是一种逼近离散函数的方法，且对噪声数据有很好的健壮性。在函数的方法，且对噪声数据有很好的

31、健壮性。在这种方法中学习到的知识被表示为决策树，决策这种方法中学习到的知识被表示为决策树，决策树也能再被表示为多个树也能再被表示为多个if-thenif-then的规则，以提高可读的规则，以提高可读性。性。n n基本决策树算法就是一个基本决策树算法就是一个贪心算法贪心算法。它采用自上。它采用自上而下、分而制之的递归方式来构造一个决策树而下、分而制之的递归方式来构造一个决策树n n通常，决策树是一种自顶向下增长树的贪婪算法，通常，决策树是一种自顶向下增长树的贪婪算法，在每个结点选取能最好地分类样例的属性。继续在每个结点选取能最好地分类样例的属性。继续这个过程直到这棵树能完美分类训练样例，或所这个

32、过程直到这棵树能完美分类训练样例，或所有的属性都使用过了。有的属性都使用过了。“信息增益信息增益”用于衡量属用于衡量属性的价值。熵（性的价值。熵（entropyentropy）是一种度量信息增益的）是一种度量信息增益的指标，它描述了样本的纯度（指标，它描述了样本的纯度（puritypurity）。下面是熵）。下面是熵的定义：的定义：n nEntropy=-PEntropy=-Pi ilog2Plog2Pi in n3.2 决策树（续）决策树（续）n n注意点：注意点：注意点：注意点：n n（1 1）避免过度拟合，应该适度剪枝；（）避免过度拟合，应该适度剪枝；（2 2）连续）连续值的离散化；（值

33、的离散化；（3 3）处理缺失值的方法：最常见值、）处理缺失值的方法：最常见值、按概率分配；（按概率分配；（4 4）处理权重不同的属性）处理权重不同的属性n n常用实现算法：常用实现算法：常用实现算法：常用实现算法：n nCARTCART、ID3ID3、ASSISTANTASSISTANT、C4.5C4.5n n3.3 人工神经网络人工神经网络n n人工神经网络（ArtificialNeuralNetworks）提供了一种普遍而且实用的方法，来从样例中学习值为实数、离散或向量的函数。n n反向传播（BackPropagation）这样的算法使用梯度下降来调节网络参数以最佳拟合由输入/输出对组成的

34、训练集合。n nBP网络的学习方法和目标：对网络的连接权值进行调整，使得对任一输入都能得到所期望的输出。常用的非线性作用函数是常用的非线性作用函数是SigmoidSigmoid函数函数，即，即f f(x x)=1/(1+e)=1/(1+e-x-x)。在神经。在神经网络模型中，大量神经元节点按网络模型中，大量神经元节点按一定体系结构连接成网状。神经一定体系结构连接成网状。神经网络一般都具有输入层，隐层和网络一般都具有输入层，隐层和输出层。输出层。每个神经元都是一个结构相每个神经元都是一个结构相似的独立单元，它接受前一似的独立单元，它接受前一层传来的数据，并将这些数层传来的数据，并将这些数据的加权

35、和输入非线性作用据的加权和输入非线性作用函数中，最后将非线性作用函数中，最后将非线性作用函数的输出结果传递给后一函数的输出结果传递给后一层。层。误差反向传播的过程误差反向传播的过程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)快速识别n n3.4 朴素贝叶斯（朴素贝叶斯（Naive

36、 Bayes）分类器）分类器n n朴素贝叶斯分类器是一种基于贝叶斯理论的分类器。它的朴素贝叶斯分类器是一种基于贝叶斯理论的分类器。它的特点是以概率形式表达所有形式的不确定，学习和推理都特点是以概率形式表达所有形式的不确定，学习和推理都由概率规则实现，学习的结果可以解释为对不同可能的信由概率规则实现，学习的结果可以解释为对不同可能的信任程度。任程度。n nP(H)P(H)是是先验概率先验概率先验概率先验概率，或，或H H的先验概率。的先验概率。P(H|X)P(H|X)是是后验概率后验概率后验概率后验概率，或条件或条件X X下，下，H H的后验概率。后验概率的后验概率。后验概率P(H|X)P(H|

37、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是苹果的确信是苹果的确信程度。程度。朴素贝叶斯分类能够奏效的前提是，朴素贝叶斯分类能够奏效的前提是，P(X|H)P(X|H)相对比相对比较容易计算。假定较容易计算。假

38、定X X表示红色和圆的，表示红色和圆的，H H表示假定表示假定X X是苹果；则是苹果；则P(X|H)P(X|H)表示已知苹果，它既红又圆的概表示已知苹果，它既红又圆的概率。率。n n3.5 期望最大化（期望最大化（EM）n n期望最大化（EM）方法和朴素贝叶斯方法有着共同的理论基础。期望最大化是一种基于循环过程的最大似然参数估计方法，用于解决带缺失数据的参数估计问题。n n样本数据分为标记样本和未标记样本，按照统计的观点，对于每一个样本的产生，其背后都有一个模型，即样本生成模型。样本生成模型的参数先由标记样本确定，再通过标记样本和利用当前模型判断标记的未标记样本共同调整。n n3.5 期望最大

39、化（续）期望最大化（续）n n如果参数适当，如果参数适当，EMEM算法能得到较好的分类结果，但计算算法能得到较好的分类结果，但计算速度相对较慢。其具体的步骤如下：速度相对较慢。其具体的步骤如下：n n一、初始参数估计，将未标记的样本按朴素贝叶斯分类方一、初始参数估计，将未标记的样本按朴素贝叶斯分类方法进行类标注。法进行类标注。n n二、反复迭代二、反复迭代E E步骤和步骤和MM步骤，直到收敛。步骤，直到收敛。n n三、三、E E步骤：对于每个未标记的样本，按下式计算类标记步骤：对于每个未标记的样本，按下式计算类标记的期望值。的期望值。n n四、四、MM步骤：利用步骤：利用E E步骤计算出的期望

40、值，按下式用已标记步骤计算出的期望值，按下式用已标记样本和未标记样本重新估计新的分类器参数。样本和未标记样本重新估计新的分类器参数。n n3.6 K-最近邻分类最近邻分类n nK-K-近邻（近邻（K-NNK-NN）分类是）分类是基于范例基于范例的分类方法，它的分类方法，它的基本思想是：给定待分类样本后，考虑在训练的基本思想是：给定待分类样本后，考虑在训练样本集中与该待分类样本距离最近（最相似）的样本集中与该待分类样本距离最近（最相似）的KK个样本，根据这个样本，根据这KK个样本中大多数样本所属的个样本中大多数样本所属的类别判定待分类样本的类别。类别判定待分类样本的类别。n n它的特例是它的特例

41、是1-NN1-NN，即分类时选出待分类样本的最，即分类时选出待分类样本的最近邻，并以此最近邻的类标记来判断样本的类。近邻，并以此最近邻的类标记来判断样本的类。n nK-NNK-NN算法的优点在于它有较高的精确程度，研究算法的优点在于它有较高的精确程度，研究表明，表明，K-NNK-NN的分类效果要明显好于朴素贝叶斯分的分类效果要明显好于朴素贝叶斯分类、决策树分类。类、决策树分类。n n3.6 K-最近邻分类（续）最近邻分类（续）n n最近邻分类的算法步骤如下：n n一、以向量空间模型的形式描述各训练样本。n n二、在全部训练样本集中选出与待分类样本最相似的K个样本。K值的确定目前没有很好的方法，

42、一般采用先定一个100左右的初始值，然后再调整。n n三、将待分类样本标记为其K个邻居中所属最多的那个类别中。n n3.7 遗传算法遗传算法n n遗传算法易于并行处理，其依据是自然界进化和遗传算法易于并行处理，其依据是自然界进化和适者生存的原则。遗传学习开始如下：创建若干适者生存的原则。遗传学习开始如下：创建若干个由随机产生的个体组成的初始个由随机产生的个体组成的初始群体群体群体群体。每个个体。每个个体用一个二进位串表示。用一个二进位串表示。n n形成由当前群体中最适合的个体组成新的群体，形成由当前群体中最适合的个体组成新的群体，以及这些规则的子女。个体的以及这些规则的子女。个体的适合度适合度

43、适合度适合度用某一目标用某一目标函数来评估。函数来评估。n n子女通过使用诸如交叉和变异等遗传操作来创建。子女通过使用诸如交叉和变异等遗传操作来创建。在在交叉交叉交叉交叉操作中，来自个体对的子串交换，形成新操作中，来自个体对的子串交换，形成新的个体对。在的个体对。在变异变异变异变异操作中，个体中随机选择的位操作中，个体中随机选择的位被反转。被反转。n n3.7 遗传算法（续）遗传算法（续）n nFitnessFitness：适应度评分函数，为给定假设赋予一个：适应度评分函数，为给定假设赋予一个评估得分。评估得分。n nFitnessFitness_ _thresholdthreshold：指定

44、终止判据的阈值。：指定终止判据的阈值。n np p：群体中包含的假设数量。：群体中包含的假设数量。r r：每一步中通过交：每一步中通过交叉取代群体成员的比例。叉取代群体成员的比例。m m：变异率。：变异率。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：n n3.7 遗传算法（续）遗传算法

45、（续）n n选择：选择：用概率方法选择用概率方法选择P P的的(1-(1-r r)p p个成员加入个成员加入P PS S。从从P P中选择假设中选择假设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百分比的成百分比的成

46、员。对于选出的每个成员，在它的表示中随机选员。对于选出的每个成员，在它的表示中随机选择一个位取反。择一个位取反。n n更新：更新：P PP PS S。n n评估：评估：对于对于P P中的每一个中的每一个h h计算计算FitnessFitness(h h)n n从从P P中返回适应度最高的假设。中返回适应度最高的假设。n n3.8 聚类分析聚类分析n n为达到全局最优，基于划分的聚类会要求穷举所为达到全局最优，基于划分的聚类会要求穷举所有可能的划分。聚类技术将数据元组视为对象。有可能的划分。聚类技术将数据元组视为对象。它将对象划分为群或聚类，使得在一个聚类中的它将对象划分为群或聚类，使得在一个聚

47、类中的对象对象“类似类似”，但与其它聚类中的对象，但与其它聚类中的对象“不类似不类似”。n n绝大多数应用采用了以下两个比较流行的绝大多数应用采用了以下两个比较流行的基于划基于划分的方法分的方法，这些基于划分的聚类方法对在中小规，这些基于划分的聚类方法对在中小规模的数据库中发现球状簇很适用。模的数据库中发现球状簇很适用。n n（1 1）k-meansk-means算法算法，在该算法中，每个簇用该簇，在该算法中，每个簇用该簇中对象的平均值来表示。中对象的平均值来表示。n n（2 2）k-medoidsk-medoids算法算法，在该算法中，每个簇用接，在该算法中，每个簇用接近聚类中心的一个对象来

48、表示。近聚类中心的一个对象来表示。n3.8 聚类分析（续）聚类分析（续）n n常用的相似程度度量n n余弦夹角：Dice系数：Jaccard系数：n n3.8 聚类分析（续）聚类分析（续）n n基于层次的方法：基于层次的方法：层次的方法对给定数据集合进层次的方法对给定数据集合进行层次的分解。根据层次的分解如何形成，层次行层次的分解。根据层次的分解如何形成，层次的方法可以被分为凝聚或分裂方法。的方法可以被分为凝聚或分裂方法。（ChameleonChameleon，CURECURE，BIRCHBIRCH）n n基于密度的方法：基于密度的方法：只要临近区域的密度超过某个只要临近区域的密度超过某个阈值

49、，就继续聚类。避免仅生成球状聚类。阈值，就继续聚类。避免仅生成球状聚类。（DBSCANDBSCAN，OPTICSOPTICS，DENCLUEDENCLUE）n n基于网格的方法：基于网格的方法：基于网格的方法把对象空间量基于网格的方法把对象空间量化为有限数目的单元，所有的聚类操作都在这个化为有限数目的单元，所有的聚类操作都在这个量化的空间上进行。这种方法的主要优点是它的量化的空间上进行。这种方法的主要优点是它的处理速度很快。（处理速度很快。（STINGSTING，CLIQUECLIQUE，WaveClusterWaveCluster）n n基于模型的方法：基于模型的方法：为每个簇假设一个模型，

50、发现为每个簇假设一个模型，发现数据对模型的最好匹配。（数据对模型的最好匹配。（COBWEBCOBWEB，CLASSITCLASSIT，AutoClassAutoClass）n 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(X)=P(Xi i|X|Xi-1i-1)n n假设假设2 2：不动性，：不动性，