连续属性空间上的规则学习算法.pdfVIP

清华大学学报(自然科学版) 28／57 1998年第38卷 JournM University(Sci＆Tech)第s2期第95～96页 o{Tsinghua 连续属性空间上的规则学习算法。 权光日，陈弗，卢彬 哈尔滨工业大学计算机科学与工程系．哈尔摈150001 摘 要 本文研究连续属性空间上的规则学习算法。首先简述了研究连续属性宅间上的规 则学习算法的目的和意义。在此基础上，研究了连续属性空问离散化问题．将信息墒函数 与无穷范数的概念应用到连续属性离散化问题，提出了基于信息墒的属性空间极小化算法。 在此基础上，提出了连续属性空问上的规则学习算法。 关键词 规则学习算法：连续属性空间：信息墒：无穷范数 引言 样本空间化简问题是人工智能领域中的重要的研究谍题。示例学习算法通过样本例子的 训练产生识别函数。示例学习系统的学习速度与精度以及识速度不仪依赖于采用的学习算法 本身，而且与训练样本集合的规模与样本空间的描述密切相关。对实际采样的数据进行筛选 和改用适当的描述是提高学习学习速度与识别精度以及节省存储空间的重要手段。另外，样 本例子的筛选与属性空间的优化描述还可以提高识别系统对输入例子噪音的鲁棒性。 本文在前人工作的基础上，将信息熵函数与无穷范数的概念应用到连续属性离散化问题，提 出了基于信息熵的属性空间极小化算法。其目的在于区间分割过程中防止过分细化，以便提 高学习系统的聚类能力以及识别系统对输入例子噪音的鲁棒性。在此基础上．提出了连续属 性空间上的规则学习算法。 l基本概念 设PE和NE是E的两个子集，为区别起见，分别叫正例集和反例集。 定义lPE、ICE分别表示正例集与反例集， d(PE，旧：Min{Max{l哆一vm}。 。+e,o，e-“1卸自 称d(PE,NE)为正例集与反例集在无穷范数下的距离，简称正例集与反例集的距离。其中 P+=(Vj，V；，…，V：)∈PE、e。(Vi，Vj，…，V：)∈ⅣE为任意反例子与正例子。 +国家自然科学基金、煤炭科学基金资助项目 96 清华大学学报(自然科学版) 1998，38(S2) 中白=f鼢f／胡+j(j=l，2，…，Ⅳ)。 证明略。 2基于信息熵的属性空问分割算法 属性区问分割算法的启发式策略准则： f”选择信息增益最大的划分点进行分割，加快分割过程，减少分割点的数目。 (2)如果一个子区间的长度小于正例集与反例集之间的距离d(PE，旧，则不再进行该区 间分割。这一准则能够防止区间分割过分细微，使学习后的识别系统对于输入例子具有蟊好 的鲁棒性。 定理2如果区间分割程序停机，则每一个属性子区间被分害0成互不相交的子区间。 证明略。 3连续属性空间上的规则学习算法C黝 下面给出连续属性空间上的规则学习算法(简称连续规则学习算法，记作(jRd)。 区闸分割算法进行属性区间划分。 分别表示正例集和反例集的分布函数，，：表示区间分割算法得到的第，个属性的第，个子区 问，瞄I，：l表示属于x的例了中，第／个属性值属0：，：的例子数目。 第二步，建立正例集和反例集的分布函数F(t，PE)和F(t，NE)； 第三步，所有，：中选择使(IPE‘|_F(t．PE))只，．NE‘)最大的，和，(其中f∈1：)； 第四步．在尸E4和AtE’中删除第，个特征值属于，：的例子，删除子区间，：．调整正例 集和反例集的分布函数F(t，PE‘)和一f，NE‘)： 第五步，如果NE‘不空，则返回第三步：舌则，调用生成公式算法； 步。 4学习算法的时间复杂性 (托4算法的计算时间复杂度为戏(咒4)；。(∽+即(P+．Ⅳ)(主f2掣}+盯)) 1-IL “J 参考文献 1 Trees RQuinianInductive o