An Efficient Method for Computing All Reducts
An Efficient Method for Computing All Reducts
复制标题
计算全归约的有效方法
DOI：
10.1527/tjsai.19.166
复制
发表时间：
2004
影响因子：
--
通讯作者：
N. Ishii
中科院分区：
文献类型：
--
作者：
Y. Bao;Xiaoyong Du;Mingrong Deng;N. Ishii
在使用粗糙集方法的决策表进行挖掘的过程中，主要的计算工作与确定还原有关。计算所有还原是一个组合NP硬化计算问题。因此，实现其更快执行的唯一方法是提供一种算法，具有更好的恒定因素，这可以在现实生活数据集的合理时间内解决此问题。本演讲的目的是提出两种新的有效算法来计算信息系统中的减少。所提出的算法基于还原的命题以及还原和识别性矩阵之间的关系。在执行时间内，已经对一些现实世界领域进行了实验。结果表明，与其他方法相比，它可以改善执行时间。在实际应用中，我们可以组合两个提出的算法。
In the process of data mining of decision table using Rough Sets methodology, the main computational effort is associated with the determination of the reducts. Computing all reducts is a combinatorial NP-hard computational problem. Therefore the only way to achieve its faster execution is by providing an algorithm, with a better constant factor, which may solve this problem in reasonable time for real-life data sets. The purpose of this presentation is to propose two new efficient algorithms to compute reducts in information systems. The proposed algorithms are based on the proposition of reduct and the relation between the reduct and discernibility matrix. Experiments have been conducted on some real world domains in execution time. The results show it improves the execution time when compared with the other methods. In real application, we can combine the two proposed algorithms.