数据挖掘主要算法及流程说明(共7页).doc

精选优质文档-倾情为你奉上数据挖掘主要算法及流程说明1 贝叶斯概率算法1） 贝叶斯概率算法主要应用于离散分类应用中，其要求属性集保持相对独立性或者具有弱关联关系。2） 贝叶斯概率算法主要是适用于分类问题，进行所属类型的判定；通过对各种属性及概率的最大似然估计判断，得到最终分类结果。3） 贝叶斯分类算法的决策依据（以二分类为例）：最小误差分类，即，则将X分到类别y1，否则为y2，其相应错误分类概率为。最小风险分类：通过错误代价矩阵判定应该归属类，其代价矩阵为，风险矩阵值通过给定风险函数确定，风险函数为：，若，则将X分到类y1中，否则分到类别y2中。4） 在判定中，习惯于选择正态密度函数作为数据分布的假设，计算变量X的最终所属分类为便于描述，X表示属性集，Y表示类变量。贝叶斯概率算法的主要步骤可以分成两大步：创建网络拓扑结构估计每一个属性的概率表中的概率值。其中，网络拓扑结构（有向无环图）生成，是简化贝叶斯概率算法复杂度的一个重要步骤。网络拓扑结构可以通过对主观的领域专家知识编码进行获得，其主要流程处理如下：a) 假设表示变量的全序b) For j=1,2,d doc) 令表示T中第j个次序最高的变量d) 令表示排在前面的变量集合e) 去掉集合中对变量没有影响的变量，通过先验概率进行判断。f) 在和集合中剩余的变量之间画弧，即表示彼此之间存在一定的互相影响关系。g) End for依据统计数据的概率值进行结果分类判定，其主要执行步骤如下：1. 假设表示所有的属性集合，表示所有的类变量集合。2. 合计统计数据集的数量，即为N。3. For i = 1,2,m do4. For j = 1,2,n do5. 统计结果为Yi时，恰好相应属性集分别为Xj时的数目Nij。6. Pij = Nij/N（即计算的统计概率）。7. End for8. 计算后验概率,表示当前待判定的属性集合9. End for10. 选择最小概率误差结果的Yk，（k=1,2,m）表示最终分类结果注：1 在进行贝叶斯网络拓扑结构生成过程中，需要人为适当干预，确定变量中的原因变量与结果变量成分，然后从各原因变量向其对应的结果变量画弧，否则计算量会达到d!之多。2 在特殊情况下，若训练样例不能保证覆盖所有属性值时，可以针对为覆盖属性指定用户概率值p，尤其适用于训练样集相对比较小的情况。3 计算后验概率时，依据贝叶斯网络拓扑结构的因果关系图，进行直接乘法操作或者判定无关而直接取先验概率。4 针对属性集中的相关属性，需要进行打捆处理，否则可能会降低贝叶斯算法的分类效果。2 神经网络算法1) 神经网络算法是一种由多个输入经计算到单个输出的处理算法，对信息的处理是非线性的。2) 神经网络算法的输入层与输出层之间可以包含多个中间层，对于不同模型的神经网络算法各神经元节点之间存在不同的连接方式。3) 神经网络算法可以处理一定的冗余特征，主要体现在权值在训练过程的学习方式。4) 训练神经网络算法各神经元对应权值是一个非常耗时的过程，尤其是当隐藏节点数量比较大时。但是，其在计算分类过程中速度比较快。在训练神经网络来学习分类任务之前，需要确定输出层的节点数目，若为2-分类问题，一个输出节点即可；而对于k-类问题，则需要k个输出节点。神经网络算法权值训练学习过程如下所示：开始确定输入层与输出层节点数神经网络计算输出结果检验得到优化后的权值Y反馈计算，优化权值权值更新N结束图1 神经网络算法权值训练学习流程示意图以最为常用且比较成熟易操作的单隐藏层神经网络结构为例，其算法伪代码实现如下：a) 令是训练样例集b) 随机初始化权值向量c) Dod) For 每一个训练样例 doe) 计算预测输出结果f) For 每个权值 dog) 更新权值h) End fori) End forj) While（不满足终止条件）注：1 在计算过程中保持01之间，被称作是学习率。其值接近0时，新权值主要受旧权值的影响；当值接近1时，则新权值对当前循环中的调整量更加敏感。2 为保证新权值变化的合理性与提升运算效率，开始一般初始化值较大，运算过程中依据计算结果进行梯度调整：。即依据误差平方和的平局值进行调整。3 关联分析1) 关联分析主要用于发现隐藏在大型数据集中的有意义联系，并对所发现的联系用频繁项集或关联规则的形式进行表示。2) 关联规则是一种形如的蕴涵表达式，其中X和Y是不相交的项集，即。3) 关联规则的强度由支持度和置信度计量，其中支持度，置信度。表示包含项集X的事务数目。在进行关联分析计算时，最重要且最费时的环节为频繁项集的产生阶段，一般利用Apriori算法进行生成。算法伪代码描述如下：a) K=1b) ,即产生所有的频繁1-项集c) Dod) K = k + 1e) ,即产生相对应的候选项集f) For 事务 dog) ,此步骤用于识别事务t的所有候选h) For 候选项集 doi) j) End fork) End forl) ，即产生所有的频繁k-项集m) whilen) result = 注：！在频繁项集生成与选择过程中，一般是先产生一个包括空集在内的项集格，然后确定包含较少候选项的频繁项集，采用深度优先搜索算法，仅对该项集的超集进行匹配查找，提升运算效率。针对频繁项集result需要深度分析内部的关联规则，规则生成也使用Apriori算法。a) for k-频繁项集， k 2 dob) ,即规则的1-项后件c) Call ap-genrulesd) End for其中ap-genrules的实现伪代码如下：a) ，即频繁项集的大小b) ，即规则后件的大小c) If dod) e) For 每个 dof) g) If doh) 输出：规则及其置信值i) Elsej) 从中删除k) End ifl) End form) Call ap-genrulesn) End if在频繁项集生成与规则发现环节，我们均使用了过程，其中的实现伪代码基本如下：a) for 每个dob) for每个 doc) if dod) e) if dof) delete cg) else h) i) End ifj) End ifk) End forl) End form) Return 注：1 的作用是为了防止重复产生关联项。2 频繁项集规则生成过程即在频繁项集中筛选同时满足最小支持度与最小可信度的项集关系。专心-专注-专业