Lower Bounds on Cardinality of Reducts for Decision Tables from Closed Classes

In this research paper, we examine classes of decision tables that are closed under attribute (column) removal and changing of decisions associated with rows. For decision tables belonging to these closed classes, we investigate lower bounds on the minimum cardinality of reducts. Reducts are minimal sets of attributes that allow us to determine the decision attached to a given row. We assume that the number of rows in the decision tables from the closed class is not limited by a constant. We divide the set of these closed classes into two families. In one family, the minimum cardinality of reducts for decision tables is bounded by standard lower bounds of the form Ω(logcl(T)), where cl(T) represents the number of decision classes in the table T. In the other family, these lower bounds can be significantly tightened to the form Ω(cl(T)^1/q) for some natural number q.

I. Introduction

DECISION tables are a widely recognized method for organizing and presenting information that is crucial for decision-making. These tables have various applications in data analysis, such as classification problems, studying combinatorial optimization, fault diagnosis, and computational geometry, among others. They have been extensively studied and utilized in different fields, as evidenced by the works [1], [2], [3], [4], [5], [6], [7], [8], [9]. It is worth noting that finite information systems with a designated decision attribute, datasets with a selected class attribute, and partially defined Boolean functions, which are commonly used in various data analysis domains to represent decision problems, can all be naturally interpreted as decision tables.