启发式属性约简算法完备性和规则发现算法的研究

摘要

寻找最小属性集已经被证明是NP难的问题,一般采用启发式的算法来寻找近似最优解.而一般文献中对启发式算法的完备性都没做深入的讨论,论文从冗余性存在的两种情况和找到的属性集可能不是最小属性约简集两方面对算法完备性问题作了研究,对几个算法的各种情况都相应地用构造性的方法给出了例子,特别定理1、2对构造例子有重要的指导作用.论文同时考虑了如何根据应用的要求求得一定程度的属性约简集.论文最后改进了规则提取的算法并详细分析了算法的优缺点.