2004 | OriginalPaper | Chapter
Tree-Like Parallelization of Reduct and Construct Computation
Author : Robert Susmaga
Published in: Rough Sets and Current Trends in Computing
Publisher: Springer Berlin Heidelberg
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
The paper addresses the problem of parallel computing in reduct/construct generation. The reducts are subsets of attributes that may be successfully applied in information/decision table analysis. Constructs, defined in a similar way, represent a notion that is a kind of generalization of the reduct. They ensure both discernibility between pairs of objects belonging to different classes (in which they follow the reducts) as well as similarity between pairs of objects belonging to the same class (which is not the case with reducts). Unfortunately, exhaustive sets of minimal constructs, similarly to sets of minimal reducts, are NP-hard to generate. To speed up the computations, decomposing the original task into multiple subtasks and executing these in parallel is employed. The paper presents a so-called constrained tree-like model of parallelization of this task and illustrates practical behaviour of this algorithm in a computational experiment.