New test for inclusion minimality in reduct generation

• Autorzy: Susmaga R.
• Języki publikacji: EN

Abstrakty

EN

The paper addresses the problem of generating reducts, i.e. minimal subsets of attributes that satisfy pre-defmed consistency and minimality conditions. The main problem with the reduct generating process is its high computational complexity. This paper describes a breadth-first search algorithm to reduct generation that is based on the notion of discernibility matrix. The most time consuming part of the algorithm is a test for inclusion minimality that has to be applied to every potential reduct. As it has been shown, implementation of this minimality test determines strongly the behaviour of the whole algorithm. A number of different minimality tests has been presented and computationally evaluated in [33]. This paper is in a sense its continuation in that it introduces further improvements to the minimality tests. It also presents results of a set of experiments with non-trivial real-life data sets in which the new tests have been compared with their earlier implementations.

Słowa kluczowe

EN

reduct generation

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2000
• Tom: Vol. 25, No. 2
• Strony: 121--146
• Opis fizyczny: Bibliogr. 40 poz.

Twórcy

autor

Susmaga R.

• Institute of Computing Science, Poznan University of Technology, Piotrowo 3a, 60-965 Poznań, Poland,