基于容差计算的非完备信息系统属性约简算法

摘要

对于有缺损值的非完备信息系统约简,多数算法利用容差关系求信息量,但此类算法需消耗大量时间计算容差,导致属性约简质量、消耗的时间及空间复杂度均不理想.为了有效提高求容差类计算效率,引入一个与相容类信息量等价的计算公式.以此为基础,提出一种属性约简算法,使时间复杂度降为O(|C|2|U|),空间降为O(|C||U|).最后,通过实例和实验分析并验证了算法的有效性和可行性.%For incomplete information system reduction with defective values, most algorithms use the tolerance relation to compute the amount of information, but this kind of algorithm consumes a large amount of time computing tolerance, which leads to the quality of attribute reduction and the time and space complexity are not ideal.In order to improve the computation efficiency of the tolerance class effectively, a formula for calculating the equivalent information of the compatible class is introduced.Based on it, an attribute reduction algorithm is proposed, which reduces the time complexity to O(|C|2|U|) and reduces the space to O(|C||U|).Finally, the examples and experimental analysis show that the proposed algorithm is efficient and feasible.