【作者】 曾凡智；

【导师】 卢炎生；

【作者基本信息】 华中科技大学 ， 计算机软件与理论， 2009， 博士

【摘要】 在知识发现过程中,为了解决数据带有噪声或不完整的问题,迫切需要能处理不精确、不确定数据的理论和方法。粗糙集理论是满足这种要求的重要新型数学工具之一。通过把粗糙集理论与方法应用在知识发现过程中,就能从相关数据中挖掘出有价值的、非平凡的模式。知识约简是粗糙集理论研究的核心问题,虽然目前关于知识约简的研究目前已经取得很多研究成果,但其中很多成果是针对没有决策属性的信息系统或一致决策表提出来的,它们并不适用于不一致决策表情形。对于一致决策表,基于D-S证据理论的知识约简与代数约简所得的结果是一致的。对于不一致决策表,具体算例能说明基于D-S证据理论的广义决策约简与代数约简在不一致决策表下的差异性,理论上证明广义决策约简仅与分配约简是等价的。在分析了广义决策约简与代数约简不同原因的基础上,给出一种将不一致决策表转化成一致决策表,再基于D-S证据理论求原始决策表代数约简的方法。通过建立信任函数与正区域基数之间的联系,给出了不需要转换过程,基于D-S证据理论直接求不一致决策表代数约简的新方法,数值算例验证了其正确性。在基于决策强度知识约简中,决策强度知识约简与条件信息熵约简本质上被证明是等价的。从条件概率的角度,将基于近似分类质量的代数约简与基于决策强度的条件信息熵约简的数学模型在形式上给出统一表示,从而分析它们在一致决策表下是一致的以及在不一致决策表下是不一致的原因。通过定义一种与正区域相一致的新决策强度,证明新决策强度约简与代数约简是等价的,提出了基于该新决策强度的启发式约简算法,数值算例验证了其正确性。将属性区分能力与差别矩阵结合起来研究,可建立差别矩阵中某属性集的可辩识属性集项数与其属性区分能力之间的关系。基于等价差别矩阵具有相同核属性和约简结果的思想,对现有差别矩阵进行改写,将基于知识量计算的方法推广到决策表情形,得到基于Hu差别矩阵知识约简和代数约简下的属性区分能力计算公式,提出一类以属性区分能力大小为启发式信息的决策表属性约简算法。该类方法的最大优点是以差别矩阵为参考但又不必通过构造差别矩阵来计算知识约简,从而巧妙避开基于差别矩阵方法的低效性问题,算法既有明显意义解释,又有坚实的理论基础。数值算例和仿真实验验证了该算法更易搜索到最优约简。同时,给出两类构造启发式算法的一般框架,为设计高效的启发式算法提供思路。更多还原

【Abstract】 During the process of knowledge discovery, in order to solve the problem of information noise or information incompleteness, it is necessary to develop the theories and methods which can deal with imprecise and uncertain information. Rough set theory is one of important novel mathematical tool to meet those demands. The valuable and non-trivial patterns are mined by application of rough set theory and method in knowledge discovery.Knowledge reduction is one of the fundamental contents in rough set theory. At present, many research results have been achieved, but most of them are just effective for information system without decision attributes or consistent decision table and invalid for inconsistent decision table.For consistent decision table, the approach to knowledge reduction based on D-S evidence theory is consistent with algebraic reduction. For inconsistent decision table,the difference between generalized decision reduction based on D-S evidence theory and algebraic reduction has been illustrated by an example firstly. It is proved that generalized decision reduction is just equivalent to assignment reduction. The essential causes that algebraic reduction and generalized decision reduction obtain a different result for inconsistent decision table are analyzed. A new approach to algebraic reduction based on evidence theory is proposed by transferring the inconsistent decision table into consistent one. By establishing the relationship between positive region bases and belief function, a new approach which can obtain algebraic reduction based on D-S evidence theory is proposed and its correctness is illustrated by a numerical example.It is proved that knowledge reduction based on decision power is equivalent to that based on conditional information entropy after knowledge reduction based on decision power discussion. From the view of conditional probability, because the mathematical models for algebraic and conditional information entropy reductions are unified formally, the reason of Consistency of their application in consistent decision table and inconsistency of their application in inconsistent decision table can be discussed. A new decision power which coincides with positive region is presented and a heuristic algorithm is proposed, which ensures to obtain an algebraic reduction, its correctness is illustrated by a numerical example.Attribute discernibility and discernible matrix are studied to establish the relationship between attribute discernibility and the number of times in discernible matrix. Based on the thought that equivalent discernible matrix has the same attribute reduction and core, the existing discernible matrices are rewritten, and then, the method based on knowledge measurement computation is generalized to decision table. The calculation formulas of attribute discernibility for Hu’s discernible matrix reduction and algebraic reduction are obtained. Accordingly, the heuristic reduction algorithms based on attribute discernibility are presented. The biggest advantage of these two algorithms is to calculate knowledge reduction without discernible matrices construction. Thus, they can avoid the low efficiency of discernible matrices. These methods have not only clear explanation but also solid theoretical foundation. Numerical examples and results of simulation experiment show that the proposed method can explore the optimal reduction more easily. At the same time, the new way to construct the high efficient heuristic reduction algorithm is given, by application of two general frameworks used to design heuristic reduction algorithm.更多还原