On efficient methods of computing attribute-value blocks in incomplete decision systems

摘要

In rough set models, almost all computations, such as attribute reduction, rule reduction, etc., are based on attribute-value blocks. Computing attribute-value blocks is most frequently used and time-consuming basic operation for these computations. However, special studies were relatively little reported on the construction of efficient methods of computing attribute-value blocks for incomplete decision systems. In this paper, we considered two representative interpretations of missing values: “do not care” conditions and “lost values”, and divided incomplete decision systems into two categories: ones containing only “do not care” conditions and the other ones containing both “do not care” conditions and “lost values”, which lead to two kinds of rough set models, tolerance relation-based rough set models (TRRSMs) and characteristic relation-based rough set models (CRRSMs), respectively. Then, two algorithms, division algorithm and index algorithm, for computing attribute-value blocks were proposed, with the division algorithm for TRRSMs and the index algorithm for both CRRSMs and TRRSMs. The two proposed algorithms are far more efficient than usual algorithms when dealing with “do not care” conditions; the division algorithm is a little more efficient than the index algorithm when missing value degrees are small, but it can not deal with “lost values”, whereas the index algorithm is evidently more efficient than the division algorithm when missing value degrees are relatively large, and it is relatively insensitive to missing value degrees. Experimental results also show that the proposed algorithms are effective and efficient. Thus, the two proposed methods constitute an effective solution to the problem of efficiently computing attribute-value blocks for incomplete decision systems.