留数分析报告模式发现算法改进附应用.docVIP

基于留数分析的模式发现算法的改进及应用 -------------王辰宇 关键词：知识发现：模式发现；离散化；留数分析。 摘要：文中提出了一种改进的知识发现算法．针对基于留数分析和递归切割的模式发现算法的不足，在样本空间分割时，考虑到不同属性对知识发现的不同贡献，采取不同的离散化标准；在模式判别准则方面，改良后的算法随切割后产生的子空间数量动态调整模式判别准则．在人造数据集的应用结果验证了算法改进思路的合理性与有效性．与原算法相比，改良后算法的知识发现效率更高、应用范围更广。 注：本文摘自《华南理工大学学报:自然科学版》2009年 第7期（文章编号：1000-565X(2009)07-0100-06）:本人在文献的学习中也收获了很多，在后面会写出自己的想法及见解。 Ⅰ基于留数分析和递归切割的模式发现算法简介 文献中提出的模式发现算法基于统计学原理，通过比较空间内样本实际分布与虚拟随机分布的差别(即留数)挖掘出蕴涵在样本中的知识．为发现数据中更精细的知识，算法采用递归切割的思想不断对子空间进行切割．算法简要介绍如下． 为定量衡量样本实际分布与虚拟随机分布的偏离程度，记d维空间中封闭的矩形空间为一事件，空间体积为V，落人该事件的训练样本数目为该事件的频率f，则该事件的留数r为： ① 式中：为该事件的虚拟频率(随机分布对应的事件频率)， n为数目． 文献中已证实所有事件的留数分布在满足一定条件下服从标准正态分布，类比统计假设检验，定义在显著性水平下，的事件为重要事件(即模式)，为对应于的标准正态离差，即P[Z≤Zα,Z~N0,1]=α的解。 在样本空间切割过程中，算法采用等频切割技术，递增切割段数的值， ，以最大化下式为目标获得d维属性的最佳切割段数：② 。 式中：为留数满足大于等于z≥Z1-α/2的子空间数之和；Q为递增切割段数．为进一步获得样本在空间分布的更细微的结构信息，算法采用对模式进行递归切割的策略，即令该模式的矩形空间为新的样本空间进行迭代切割，直至满足结束条件． Ⅱ模式发现算法的改进 1 留数分析 原算法在同一个显著性水平下对样本空间中的子空间进行评估．考虑到在样本空间被分割成的子空间数量增加时，事件留数的样本容量增加，其正态分布特性越发明显，从假设检验的角度看，子空间违反正态分布的可能性下降，即子空间成为重要事件的可能性下降．然而，客观上样本空间是包含分布知识的，因而子空间违反正态分布是客观存在的，除非样本中不包含任何知识．因此，随着切割后子空间数量的增加(即事件留数的样本容量增加)而调整判别子空间是否为模式的边界值，将能获得更为可靠的知识．为此，文中按如下准则选择这一显著性水平值： ③ 2 切割策略 知识发现的质量取决于样本空间的划分(切割)方法．样本空间的划分可等效为连续属性的离散化，理论证明最优离散化问题是个NP难(NP—Hard)问题。 在此我们采用等频切割方法、以最大化式②为目标确定最优的切割段数Q，每维属性切割段数等同对待．然而，对于一个维数稍高的数据集，如d=6，考虑到维数越高，样本分布越稀疏的特性，式②中分母的增加速度将远远大于分子的增长，因此，算法将收敛于较小的Q，且并非是实际的最佳值．基于知识发现算法是以获得尽可能多的知识为目标，而计算复杂度在某些离线学习问题中只要在允许范围内都是可接受的这一思想，文中定义以maxN(Q)为最佳Q的判断准则． 研究表明，等频切割对于具有特殊分布的属性维来说(如双峰或多峰分布)，切割效果并不理想．为此，借鉴文献中连续属性离散化方法提出一种基于最小信息损失的各维属性不等切割段数的样本空间划分技术．实现过程描述如下：记为样本落入第i个区间的概率，，为落人第i个区间的样本数，则离散变量x的信息熵为： ④ 文献已证明为一凹函数，且当变量离散化段数最大(两紧邻取值点的中点均作为一个分割点)时，具有最大值；同时证明，若选择两个紧邻区间i和i+1合并，使得min(+)，则合并前后的变化最小，即信息损失量最小．基于此，文中的空间切割过程实现如下： 步骤l 对第k维属性，将样本按属性值从小到大排列，取任意两个连续取值的中点作为一个离散断点，记此时的切割区间为； 步骤2 合并两个相邻区间段i和i+l，使得合并前后的最小，此时切割区间为； 步骤3 重复步骤2，直至切割段数等于，并记录此时的分割点； 步骤4 设k=k+1，返回步骤1，直至k=d结束． 得最佳的Q． 在获得各维属性的初始切割结果Q后，文中提出的各维属性不等切割大小的样本空间划分步骤描述如下：