数据挖掘主要算法及流程说明

数据挖掘主要算法及流程说明数据挖掘主要算法及流程说明 1贝叶斯概率算法 1 贝叶斯概率算法主要应用于离散分类应用中 其要求属性集保持相 对独立性或者具有弱关联关系 2 贝叶斯概率算法主要是适用于分类问题 进行所属类型的判定 通 过对各种属性及概率的最大似然估计判断 得到最终分类结果 3 贝叶斯分类算法的决策依据 以二分类为例 最小误差分类 1 即 则将 X 分到类别 y1 否则为 y2 其相 XyPXyP 21 应错误分类概率为 12 21 如果判定为 如果判定为 yXyP yXyP XerrotP 最小风险分类 通过错误代价矩阵判定应该归属类 其代价矩 2 阵为 风险矩 1 0 中类的样本分到把一个 jiyyCC ijij 阵值通过给定风险函数确定 风险函数为 若 XyPcXyPcXyR XyPcXyPcXyR 2221212 2121111 则将 X 分到类 y1中 否则分到类别 y2中 XyRXyR 21 4 在判定中 习惯于选择正态密度函数作为数据分布的假设 计算变 量 X 的最终所属分类 为便于描述 X 表示属性集 Y 表示类变量 贝叶斯概率算法的主要步骤 可以分成两大步 创建网络拓扑结构估计每一个属性的概率表中的概率值 1 2 其中 网络拓扑结构 有向无环图 生成 是简化贝叶斯概率算法复杂度 的一个重要步骤 网络拓扑结构可以通过对主观的领域专家知识编码进行获得 其主要流程处理如下 a 假设表示变量的全序 21d XXXT b For j 1 2 d do c 令表示 T 中第 j 个次序最高的变量 jT X d 令表示排在前面的变量集合 1 21 jTTTjT XXXX jT X e 去掉集合中对变量没有影响的变量 通过先验概率进行 jT X j X 判断 f 在和集合中剩余的变量之间画弧 即表示彼此之间存 jT X jT X 在一定的互相影响关系 g End for 依据统计数据的概率值进行结果分类判定 其主要执行步骤如下 1 假设表示所有的属性集合 表示 n XXXX 21 m YYYY 21 所有的类变量集合 2 合计统计数据集的数量 即为 N 3 For i 1 2 m do 4 For j 1 2 n do 5 统计结果为 Yi时 恰好相应属性集分别为 Xj时的数目 Nij 6 Pij Nij N 即计算的统计概率 ij YXP 7 End for 8 计算后验概率 表示当前待判定的属性集合 i YXP X 9 End for 10 选择最小概率误差结果的 Yk k 1 2 m 表示最终分类结果 注 1 在进行贝叶斯网络拓扑结构生成过程中 需要人为适当干预 确定变量中 的原因变量与结果变量成分 然后从各原因变量向其对应的结果变量画弧 否则计算量会达到 d 之多 2 在特殊情况下 若训练样例不能保证覆盖所有属性值时 可以针对为覆盖 属性指定用户概率值 p 尤其适用于训练样集相对比较小的情况 3 计算后验概率时 依据贝叶斯网络拓扑结构的因果关系图 进 i YXP 行直接乘法操作或者判定无关而直接取先验概率 4 针对属性集中的相关属性 需要进行打捆处理 否则可能会降低贝叶斯算 法的分类效果 2神经网络算法 1 神经网络算法是一种由多个输入经计算到单个输出的处理算法 对信息的 处理是非线性的 2 神经网络算法的输入层与输出层之间可以包含多个中间层 对于不同模型 的神经网络算法各神经元节点之间存在不同的连接方式 3 神经网络算法可以处理一定的冗余特征 主要体现在权值在训练过程的学 习方式 4 训练神经网络算法各神经元对应权值是一个非常耗时的过程 尤其是当隐 藏节点数量比较大时 但是 其在计算分类过程中速度比较快 在训练神经网络来学习分类任务之前 需要确定输出层的节点数目 若为 2 分类问题 一个输出节点即可 而对于 k 类问题 则需要 k 个输出节点 神 经网络算法权值训练学习过程如下所示 开始 确定输入层与输出层节点数 神经网络计算 输出结果检验 得到优化后的权值 Y 反馈计算 优化权值 权值更新 N 结束 图 1 神经网络算法权值训练学习流程示意图 以最为常用且比较成熟易操作的单隐藏层神经网络结构为例 其算法伪代 码实现如下 a 令是训练样例集 NiyXD ii 2 1 b 随机初始化权值向量 0 c Do d For 每一个训练样例 do DyX ii e 计算预测输出结果 k i y f For 每个权值 do j g 更新权值 k ii k j k j yy 1 h End for i End for j While 不满足终止条件 注 1 在计算过程中保持 0 1 之间 被称作是学习率 其值接近 0 时 新权 值主要受旧权值的影响 当值接近 1 时 则新权值对当前循环中的调 整量更加敏感 2 为保证新权值变化的合理性与提升运算效率 开始一般初始化值较大 运算过程中依据计算结果进行梯度调整 N i ii yy N 1 21 即依据误差平方和的平局值进行调整 3关联分析 1 关联分析主要用于发现隐藏在大型数据集中的有意义联系 并对所发现 的联系用频繁项集或关联规则的形式进行表示 2 关联规则是一种形如的蕴涵表达式 其中 X 和 Y 是不相交的项YX 集 即 YX 3 关联规则的强度由支持度和置信度计量 其中支持度 置信度 表示 N YX YXs X YX YXc X 包含项集 X 的事务数目 在进行关联分析计算时 最重要且最费时的环节为频繁项集的产生阶段 一般利用 Apriori 算法进行生成 算法伪代码描述如下 a K 1 b 即产生所有的频繁 1 项集 supmin NiIiiFk c Do d K k 1 e 即产生相对应的候选项集 1 kk FgenaprioriC f For 事务 doTt g 此步骤用于识别事务 t 的所有候选 tCsubsetC kt h For 候选项集 do t Cc i 1 cc j End for k End for l 即产生所有的频繁 k 项 supmin NcCccF kk 集 m while k F n result k F 注 在频繁项集生成与选择过程中 一般是先产生一个包括空集在内的 项集格 然后确定包含较少候选项的频繁项集 采用深度优先搜索算法 仅对 该项集的超集进行匹配查找 提升运算效率 针对频繁项集 result 需要深度分析内部的关联规则 规则生成也使用 Apriori 算法 a for k 频繁项集 k 2 do k f b 即 规则的 1 项后件 k fiiH 1 c Call ap genrules 1 Hfk d End for 其中 ap genrules的实现伪代码如下 mk Hf a 即频繁项集的大小 k fk b 即规则后件的大小 m Hm c If do1 mk d mm HgenaprioriH 1 e For 每个 do 11 mm Hh f Cfconf k g If doconfconfmin h 输出 规则及其置信值 11 mmk hhf i Else j 从中删除 1 m H 1 m h k End if l End for m Call ap genrules 1 mk Hf n End if 在频繁项集生成与规则发现环节 我们均使用了过程 k Lgenapriori 其中的实现伪代码基本如下 k Lgenapriori a for 每个do k Ll 1 b for 每个 do k Ll 2 c if do klklklklllll 21212121 112211 d 21 l lc e if do k Lc f delete