Effective tests for minimality in reduct generation

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

Abstrakty

EN

The paper addresses the problem of checking for inclusion minimality in attribute reduction. Reduction of attributes information/decision tables is an important aspect of table analysis where so called reducts of attributes may successfully be applied. The reducts, however, are hard to generate because of high theoretical complexity of the problem. Especially difficult is the generation of all exact reducts for a given data set. This paper reports on a series of experiments with some advariced algorithms that allow to generate all reducts. Particular attention is paid to a family of algorithms based on the notion of discernibility matrix. The heaviest computing load of these algorithms lies in testing for minimality with regard to inclusion. The paper introduces a new minimality test that makes the algorithms even more effective. All the presented tests are evaluated in experiments with real-life data sets.

Słowa kluczowe

EN

reduct; minimality

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 1998
• Tom: Vol. 23, No. 4
• Strony: 219--240
• Opis fizyczny: Bibliogr. 35 poz.

Twórcy

autor

Susmaga R.

• Institute of Computing Science, Poznan University of Technology, Piotrowo 3a, 60-965 Poznan, Poland [Politechnika Poznańska, Instytut Informatyki],