贝叶斯与频繁模式

1DataMining:

ConceptsandTechniques

—Chapter9—

Classification:AdvancedMethods

姓名：周芳学号：20152161409.1贝叶斯信念网络朴素贝叶斯分类假定类条件独立（实际上在现实应用中几乎不可能做到完全独立），在实践中，变量之间的依赖可能存在。各个特征属性间往往并不条件独立，而是具有较强的相关性，这样就限制了朴素贝叶斯分类的能力。贝叶斯信念网络说明联合条件概率分布。它允许在变量的子集间定义类条件独立性。它提供一种因果关系的图形，可以在其上进行学习训练后的贝叶斯网络可以用于分类February6,2023DataMining:ConceptsandTechniques2两个成分定义第一部分是有向无环图，其每个节点代表一个随机变量，而每条弧代表一个概率依赖。（变量可以是离散的或连续值的）第二部分是条件概率表。February6,2023DataMining:ConceptsandTechniques39.1贝叶斯网络February6,2023DataMining:ConceptsandTechniques4在贝叶斯信念网络中对应于属性或变量Z1....Zn的任意元组(Z1....Zn)的联合概率由下式计算：如上图，对于FamilyHistory，Smoker，LungCancer这三个属性，用朴素贝叶斯计算，得到的联合概率是贝叶斯网络求得联合概率为：由条件概率表（CPT）求联合分布变量Z的CPT说明条件分布P(Z|Parents(Z))，其中Parents(Z)是Z的双亲。对于其双亲值的每个可能组合，表中给出了LangCancer的每个值的条件概率。例如，由左上角和右下角，P(LangCancer=”yes”

|

FamilyHistory=”yes”,

Smoker=”yes”)=0.8

P(LangCancer=”no”

|

FamilyHistory=”no”,

Smoker=”no”)=0.9

对应于属性或变量Z1,Z2,…Zn的任意元组（z1,z2,…zn）的联合概率由下式计算February6,2023DataMining:ConceptsandTechniques5February6,2023DataMining:ConceptsandTechniques6例子：i、真实账号比非真实账号平均具有更大的日志密度、更大的好友密度以及更多的使用真实头像。ii、日志密度与好友密度、日志密度与是否使用真实头像在账号真实性给定的条件下是独立的。iii、使用真实头像的用户比使用非真实头像的用户平均有更大的好友密度。February6,2023DataMining:ConceptsandTechniques7通过对训练数据集的统计，得到下表（R表示账号真实性，H表示头像真实性）：例如，现随机抽取一个账户，已知其头像为假，求其账号也为假的概率：February6,2023DataMining:ConceptsandTechniques8我们的模型中存在四个随机变量：账号真实性R，头像真实性H，日志密度L，好友密度F训练贝叶斯信念网络---构建：1、主观网络拓扑可以由专家构造或数据导出。专家通常对所分析领域成了的直接条件依赖有很好的把握，但是必须说明参与直接依赖接单的条件概率。马尔科夫假设：在直接原因已知前提下，一个变量独立于与其没有影响的变量。E.g.,S‹—F—›A‹—T,在已知F—›A的前提下，pathS—›A不通隐马尔科夫模型：常用于动态系统模型的状态是不明显的,但是他们的输出明显。February6,2023DataMining:ConceptsandTechniques9训练贝叶斯信念网络设S是s个训练样本X1,X2,…Xs的集合，Wijk是具有是双亲Ui=uik的变量Y=yij的CPT项。Wijk可以看作权，类似于神经网络中隐藏单元的权。权的集合总称为w。这些权被初始化为随机概率值。梯度下降策略采用贪心爬山法。在每次迭代中，修改这些权，并最终收敛到一个局部最优解。

基于w的每个可能设置都等可能地假定，该方法搜索能最好地对数据建模的Wijk值。目标是最大化

。这通过按梯度来做，使得问题更简单。给定网络结构和Wijk的初值，该算法按以下步骤处理：February6,2023DataMining:ConceptsandTechniques10梯度下降1.计算梯度2.沿梯度方向前进一小步，下式更新权重3.更新规格化权值保证权重在0—1之间，进行归格化操作。February6,2023DataMining:ConceptsandTechniques11梯度下降February6,2023DataMining:ConceptsandTechniques12梯度训练是用于解决信念网络中隐藏数据问题的，例如，已知上图（a），不知道上图（b）。9.4使用频繁模式分类February6,2023DataMining:ConceptsandTechniques13

频繁模式显示了频繁地出现在给定数据集上的属性——值对之间的有趣联系。例如，我们可能发现属性——值对age=youth和credit=OK出现在20%的购买计算机的AllRlectronics顾客元组中。我们可以把每个属性——值对看作一个项，因此搜索这种频繁模式称作频繁模式挖掘或频繁项集挖掘。频繁模式February6,2023DataMining:ConceptsandTechniques14下面是从数据集D中挖掘的一个关联规则，显示了它的置信度和支持度：其中，“^”表示逻辑“AND“。意味着，D中20%的顾客是青年、信誉为Ok，并且属于类buys_computer=yes；D中身为青年人并且信誉度为OK的顾客中，93%属于类buys_computer=yes。设D是元组的数据集合。D中每个元组用n个属性A1，A2，…，An和一个类标号属性Aclass描述。所有的连续属性都被离散化并按分类（或标称）属性处理。项p是一个形如（Ai，v）的属性——值对，其中Ai是属性，取值v。数据元组X=（x1，x2，…,xn）满足项p=（Ai，v），当且仅当xi=v，其中xi是X的第i个属性（Ai）的值。在挖掘用于分类的关联规则时，我们只对形如p1^p2^…pl=>Aclass=C的关联规则感兴趣，其中规则的前件是项的合取，与一个类标号C相关联。

置信度：对于一个给定的规则R，D中满足该规则前件也具有类标号C的元组所占的百分比称作R的置信度。从分类角度看，这类似于规则的准确率。

支持度：D中满足规则前件并具有类标号C的元组所占的百分比称作规则R的支持度。关联规则分类的步骤February6,2023DataMining:ConceptsandTechniques15一般而言，关联规则分类包括以下步骤：（1）挖掘数据，得到频繁项集，即找出数据中经常出现的属性——值对。（2）分析频繁项集，产生每个类的关联规则，它们满足置信度和支持度标准。（3）组织规则，形成基于规则的分类器。关联规则分类方法的不同在于挖掘频繁项集所用的方法、如何将被分析的规则导出并用于分类。典型的关联分类方法February6,2023DataMining:ConceptsandTechniques16CBA（基于关联分类）主要可能的关联规则的形式项（一组属性-值对）类标签在优先级递减的基础上的信任和支持，然后组织规则，建立分类CMAR（基于多关联规则分类）分类：对多个规则统计分析CPAR（基于预测关联规则分类）产生预测规则（FOIL分析），但允许覆盖规则具有减小权重高效率，高精度类似于CMARCBA算法February6,2023DataMining:ConceptsandTechniques17最早最简单的关联分类算法时基于分类的关联（ClassificationBasedonAssociation，CBA）。CBA使用迭代方法挖掘频繁项集，类似于Apriori算法。找出满足最小置信度和支持度阈值的规则的完全集后，然后分析，找出包含在分类器中的规则。CBA使用一种启发式方法构造分类器，其中规则按照它们的置信度和支持度递减优先级排序。（1）如果一组规则具有相同的前件，则选取具有最高置信度的规则代表该集合。（2）在对新元组分类时，使用满足该元组的第一个规则对它进行分类。（3）分类器还包含一个默认规则，具有最低优先级，用来为不能被分类器中其他规则满足的新元组指定默认类。这样，构成分类器的规则的集合形成一个决策表。一般而言，实验表明CBA在大量数据集上比C4.5更准确。CMAR算法February6,2023DataMining:ConceptsandTechniques18

基于多关联规则的分类（ClassificationbasedonMultipleAssociationRules，CMAR）在频繁项集挖掘和分类器构造方面都不同于CBA。CMAR采用FP—Growth算法的变形来发现满足最小支持度和最小置信度阈值的规则的完全集。CMAR使用一种加强的FP-树，记录满足每个频繁项集的元组的类标号分布。这样，它可以把规则产生与频繁项集挖掘合并成一步。CMAR还使用另一种树结构来有效地存储和提取规则，并根据置信度、相关度和数据库覆盖率对规则剪枝。当规则插入该树时就触发规则剪枝策略。例如，给定两个规则R1和R2，如果R1的前件比R2更一般，并且conf（R1）>=conf（R2），则剪去R2。其基本原理是：如果规则存在具有更高置信度的更泛化的版本，则可以剪去具有低置信度的更特殊化的规则。

CMAR算法February6,2023DataMining:ConceptsandTechniques19“如果多个规则可用，我们使用哪一个？”作为分类法，假设多个规则满足或匹配X，这些规则形成一个集合S。使用哪个规则确定X的类标号？CMAR在做出它的类预测时考虑多个规则。它根据类标号将规则分组。在一个组中的所有规则都具有相同的类标号，而在不同组中的规则具有不同的类标号。CMAR使用加权的X2度量，根据组中规则的统计相关性找出“最强的”规则组。然后把X的类标号指派为最强的组的类标号。这样，在预测新元组的类标号时，它考虑多个规则，而不只是一个具有最高置信度的规则。实验表明，CMAR比CBA的平均准确率稍高。它的运行时间、可伸缩性和内存使用都更有效。CPAR算法February6,2023DataMining:ConceptsandTechniques20CPAR（ClassificationbasedonPredictiveAssociationRules，基于预测关联规则的分类）采用了不同方法产生规则，基于一种称作FOIL的分类规则产生算法。FOIL构造规则来区别正元组（如类buys_computer=yes的元组）和负元组（如类buys_computer=no的元组）。对于多类问题，将FOIL用于每一个类。也就是说，对于类C，类C的所有元组都看做正元组，而其余的都看做负元组。产生规则以区分C类和其他类的元组。每当产生一个规则时，就删除它满足（或覆盖）的正样本，直到数据集合中所有的正元组都被覆盖。这样，产生的规则更少，CPAR放宽了这一步，允许被覆盖的元组留下并被考虑，但是降低它们的权重。对每个类重复该过程。结果规则被合并在一起，形成分类器的规则集。在分类时，CPAR采用多少有些不同于CMAR的多规则策略。如果多个规则满足新元组X，则类似于CMAR，这些规则将按类分组。然而，CPAR根据期望准确率，使用每组中的最好的k个规则预测X的类标号。通过考虑组中最好的k个规则而不是所有的规则，这避免了较低秩规则的影响。在大量数据集上，CPAR的准确率与CMAR接近。然而，由于CPAR产生的规则比CMAR少得多，对于大型训练数据集，CMAR有效得多。频繁模式分类February6,2023DataMining:ConceptsandTechniques21精度问题提高辨别力增加特征空间的表现力可伸缩性问题它是计算上不可行生成所有的特征组合，并用信息增益阈值进行筛选有效的方法（DDPMine：FPtree修剪）：H.Cheng,X.Yan,J.Han,andP.S.Yu“直接识别图案为挖掘有效的分类”，ICDE'08频繁模式VS单个特征February6,2023DataMining:ConceptsandTechniques22一些频繁模式的辨别力比的单个特征更高，如图绘制了长度等于1的信息增益(a)Austral(c)Sonar(b)Cleve图1.信息增益vs.模式长度实验结果February6,2023DataMining:ConceptsandTechniques23(a)Austral(c)Sonar(b)Breast图2.信息增益vs.模式频率如图绘制了UCI数据集的模式频度（支持度）与信息增益，及理论上界。低频度的模式的区别能力受限于一个小上界，信息增益的上界随着模式频度单调增加特征选择February6,2023DataMining:ConceptsandTechniques24给定一组频繁模式，无判别和冗余型态都存在，可能会导致过度拟合我们要挑出判别模式，并删除冗余的模式借用最大边际关联的概念（MMR