决策表属性约简的一种新算法.pdfVIP

计算机科学2006V01．33№．11A 决策表属性约简的一种新算法*) ANewAttributeReduction inDecisionTable Algorithm 魏巍梁吉业 (计算智能与中文信息处理省部共建教育部重点实验室)(山西大学计算机与信息技术学院 太原030006) AbstractInthis theideathattheuniverseiS heuristicattributereduction paper。byutilizing changedgradually，a basedconditionalintormationiS showsthatthis is on algorithmsimple algorithm entropyproposed．Theexample is inuniverse．Theseresults andefficientwhilethenumberofelementiS andthenumberofattributesmaller larger willbe for basedOn set． helpfulknowledgeacquirementrough Decision reduction，Conditionalinformation Keywords table，Attribute entropy ， D，则称决策表是协调的，否则称决策表是不协调 1 引言 ．的。 属性约简是粗糙集理论中重要的研究内容[1】。 协调的决策表产生确定性命题，不协调的决策 目前，已提出了许多属性约简算法。常见的属性约 表产生不确定性命题。 简是利用区别矩阵来计算相对核，得到相对约简。 定义2163给定决策表T=(U，R，y，p，其中 如文[2，3]的算法，这类算法可以得到决策表的所有R=cuD，C是条件属性集，D是决策属性集，U／C 可能的约简，但是逻辑公式化简的过程计算量很大。 文[4，5]提出了启发式属性约简算法，这类算法的计的条件信息熵定义为 算量相对较小，但是只能得到决策表的一个相对约 E(DIC)=搽≮掣等斧， 简，且不一定是最小约简。 I V 上述算法都是在整个论域上进行的，这使得每 次进行划分运算时进行了大量的冗余运算，即在整 个约简过程中仅仅考虑了对属性的增减，而没有考 在论域U中的概率，等*表示K补集在论域U中 虑论域中论域的变化对约简效率的影响。 的概率。 本文提出了一种新的决策表属性约简算法。该 算法通过不断将一定属性集下决策表中协调的部分 R=CUD，C是条件属性集，D是决策属性集，则对 去除，把不协调的部分作为新的论域作进一步处理， 于任意属性a∈C的重要性SGF(口，C，D)定义为 逐步缩小参与属性约简的论域，在一定程度上降低 了求取约简的计算量。 定理1t7】给定决策表T=(【，，R，V，，)，其中 2基本概念 R=CUD，