《数据挖掘主要算法及流程说明.docx》由会员分享，可在线阅读，更多相关《数据挖掘主要算法及流程说明.docx（9页珍藏版）》请在三一办公上搜索。
1、数据挖掘主要算法及流程说明数据挖掘主要算法及流程说明 1 贝叶斯概率算法 1） 贝叶斯概率算法主要应用于离散分类应用中，其要求属性集保持相对独立性或者具有弱关联关系。 2） 贝叶斯概率算法主要是适用于分类问题，进行所属类型的判定；通过对各种属性及概率的最大似然估计判断，得到最终分类结果。 3） 贝叶斯分类算法的决策依据：1最小误差分类，即P(y1|X)fP(y2|X)，则将X分到类别y1，否则为y2，其相应错误分类概率为P(errot|X)P(y1|X),如果判定为y2=。2最P(y2|X),如果判定为y1小风险分类：通过错误代价矩阵判定应该归属类，其代价矩阵为(i,j0,C=Cij|把一个y
2、j类的样本分到yi中，1)，风险矩阵值通过给定风险函数确定，风险函数为：R(y1|X)=c11P(y1|X)+c12P(y2|X)R(y2|X)=c21P(y1|X)+c22P(y2|X)，若 R(y1|X)pR(y2|X)，则将X分到类y1中，否则分到类别y2中。4） 在判定中，习惯于选择正态密度函数作为数据分布的假设，计算变量X的最终所属分类 为便于描述，X表示属性集，Y表示类变量。贝叶斯概率算法的主要步骤可1创建网络拓扑结构2估计每一个属性的概率表中的概率值。 以分成两大步：其中，网络拓扑结构生成，是简化贝叶斯概率算法复杂度的一个重要步骤。网络拓扑结构可以通过对主观的领域专家知识编码进行
3、获得，其主要流程处理如下： a) 假设T=(X1,X2,L,Xd)表示变量的全序 b) For j=1,2,d do c) 令XT(j)表示T中第j个次序最高的变量 d) 令D(XT(j)=XT(1),XT(2),L,XT(j-1)表示排在XT(j)前面的变量集合 e) 去掉集合D(XT(j)中对变量Xj没有影响的变量，通过先验概率进行判断。 f) 在XT(j)和集合D(XT(j)中剩余的变量之间画弧，即表示彼此之间存在一定的互相影响关系。 g) End for 依据统计数据的概率值进行结果分类判定，其主要执行步骤如下： 1. 假设X=X1,X2,L,Xn表示所有的属性集合，Y=Y1,Y2,L
4、,Ym表示所有的类变量集合。 2. 合计统计数据集的数量，即为N。 3. For i = 1,2,m do 4. For j = 1,2,n do 5. 统计结果为Yi时，恰好相应属性集分别为Xj时的数目Nij。 6. Pij = Nij/N。 7. End for 8. 计算后验概率PX|Yi,X表示当前待判定的属性集合 9. End for 10. 选择最小概率误差结果的Yk，表示最终分类结果 注： 1 在进行贝叶斯网络拓扑结构生成过程中，需要人为适当干预，确定变量中的原因变量与结果变量成分，然后从各原因变量向其对应的结果变量画弧，否则计算量会达到d!之多。 2 在特殊情况下，若训练样例不
5、能保证覆盖所有属性值时，可以针对为覆盖属性指定用户概率值p，尤其适用于训练样集相对比较小的情况。 3 计算后验概率PX|Yi时，依据贝叶斯网络拓扑结构的因果关系图，进行直接乘法操作或者判定无关而直接取先验概率。 4 针对属性集中的相关属性，需要进行打捆处理，否则可能会降低贝叶斯算()()法的分类效果。 2 神经网络算法 1) 神经网络算法是一种由多个输入经计算到单个输出的处理算法，对信息的处理是非线性的。 2) 神经网络算法的输入层与输出层之间可以包含多个中间层，对于不同模型的神经网络算法各神经元节点之间存在不同的连接方式。 3) 神经网络算法可以处理一定的冗余特征，主要体现在权值在训练过程的
6、学习方式。 4) 训练神经网络算法各神经元对应权值是一个非常耗时的过程，尤其是当隐藏节点数量比较大时。但是，其在计算分类过程中速度比较快。 在训练神经网络来学习分类任务之前，需要确定输出层的节点数目，若为2-分类问题，一个输出节点即可；而对于k-类问题，则需要k个输出节点。神经网络算法权值训练学习过程如下所示： 开始 确定输入层与输出层节点数 权值更新 神经网络计算 反馈计算，优化权值 输出结果检验 N Y 得到优化后的权值 结束 图1 神经网络算法权值训练学习流程示意图 以最为常用且比较成熟易操作的单隐藏层神经网络结构为例，其算法伪代码实现如下： a) 令D=Xi,yi|i=1,2,L,N是
7、训练样例集 b) 随机初始化权值向量w c) Do d) For 每一个训练样例Xi,yiD do (0)()()(k)e) 计算预测输出结果yi f) For 每个权值wj do g) 更新权值wjh) End for i) End for j) While 注： 1 在计算过程中l保持01之间，被称作是学习率。其值接近0时，新权值主要受旧权值的影响；当值接近1时，则新权值对当前循环中的调整量更加敏感。 2 为保证新权值变化的合理性与提升运算效率，l开始一般初始化值较大，运算过程中依据计算结果进行梯度调整：l=l*依据误差平方和的平局值进行调整。 (k+1)(k)(k)=wj+lyi-yi
8、()1N(yii=1N)2-yi)。即3 关联分析 1) 关联分析主要用于发现隐藏在大型数据集中的有意义联系，并对所发现的联系用频繁项集或关联规则的形式进行表示。 2) 关联规则是一种形如XY的蕴涵表达式，其中X和Y是不相交的项集，即XY=F。 3) 关联规则的强度由支持度和置信度计量，其中支持度s(XY)=s(XY)s(XY)，置信度c(XY)=。s(X)表示包Ns(X)含项集X的事务数目。 在进行关联分析计算时，最重要且最费时的环节为频繁项集的产生阶段，一般利用Apriori算法进行生成。算法伪代码描述如下： a) K=1 b) Fk=i|iILs(i)Nminsup ,即产生所有的频繁1
9、-项集 c) Do d) K = k + 1 e) Ck=aprior(Fk-1),即产生相对应的候选项集 _igenf) For 事务tT do g) Ct=subset(Ck,t),此步骤用于识别事务t的所有候选 h) For 候选项集cCt do i) s(c)=s(c)+1 j) End for k) End for l) Fk=，即产生所有的频繁k-项c|cCkLs(c)Nminsup集 m) while(Fkf) n) result = UFk 注：！在频繁项集生成与选择过程中，一般是先产生一个包括空集在内的项集格，然后确定包含较少候选项的频繁项集，采用深度优先搜索算法，仅对该项集
10、的超集进行匹配查找，提升运算效率。 针对频繁项集result需要深度分析内部的关联规则，规则生成也使用Apriori算法。 a) for k-频繁项集fk， k 2 do b) H1=i|ifk,即规则的1-项后件 c) Call ap-genrules(fk,H1) d) End for 其中ap-genrules(fk,Hm)的实现伪代码如下： a) k=fk，即频繁项集的大小 b) m=Hm，即规则后件的大小 c) If kfm+1 do d) Hm+1=apriori_gen(Hm) e) For 每个hm+1Hm+1 do f) conf=s(fk)/sC g) If confmin
11、conf do h) 输出：规则(fk-hm+1)hm+1及其置信值 i) Else j) 从Hm+1中删除hm+1 k) End if l) End for m) Call ap-genrules(fk,Hm+1) n) End if 在频繁项集生成与规则发现环节，我们均使用了apriori_gen(Lk)过程，其中apriori_gen(Lk)的实现伪代码基本如下： a) for 每个l1Lkdo b) for每个l2Lk do c) if (l11=l21)(l12=l22)L(l1k-1=l2k-1)(l1kpl2k) do d) c=l1,l2 e) if cLkdo f) delete c g) else h) Ck+1=Ck+1+c i) End if j) End if k) End for l) End for m) Return Ck+1 注： 1 (l11=l21)(l12=l22)L(l1k-1=l2k-1)(l1kpl2k)的作用是为了防止重复产生关联项。 2 频繁项集规则生成过程即在频繁项集中筛选同时满足最小支持度与最小可信度的项集关系。
