TY - GEN

T1 - Partial covers and inhibitory decision rules

AU - Delimata, Pawel

AU - Moshkov, Mikhail Ju

AU - Skowron, Andrzej

AU - Suraj, Zbigniew

PY - 2009

Y1 - 2009

N2 - In this chapter, we consider algorithms for construction of partial inhibitory decision rules and some bounds on the length such rules. These investigations are based on the use of known results for partial covers. We show that: • Under some natural assumptions on the class NP, the greedy algorithm is close to the best polynomial approximate algorithms for the minimization of the length of partial inhibitory decision rules. • Based on an information received during the greedy algorithm work, it is possible to obtain nontrivial lower and upper bounds on the minimal length of partial inhibitory decision rules. • For the most part of randomly generated binary decision tables, greedy algorithm constructs simple partial inhibitory decision rules with relatively high accuracy. In particular, some theoretical results confirm the following 0.5-hypothesis for inhibitory decision rules: for the most part of decision tables for each row during each step the greedy algorithm chooses an attribute that separates from the considered row at least one-half of rows that should be separated. Similar results can be obtained for partial inhibitory association rules over information systems. To this end, it is enough to fix an arbitrary attribute a i of the information system as the decision attribute and study inhibitory association rules with the right-hand side of the kind ai ≠ c as inhibitory decision rules over the obtained decision system (decision table).

AB - In this chapter, we consider algorithms for construction of partial inhibitory decision rules and some bounds on the length such rules. These investigations are based on the use of known results for partial covers. We show that: • Under some natural assumptions on the class NP, the greedy algorithm is close to the best polynomial approximate algorithms for the minimization of the length of partial inhibitory decision rules. • Based on an information received during the greedy algorithm work, it is possible to obtain nontrivial lower and upper bounds on the minimal length of partial inhibitory decision rules. • For the most part of randomly generated binary decision tables, greedy algorithm constructs simple partial inhibitory decision rules with relatively high accuracy. In particular, some theoretical results confirm the following 0.5-hypothesis for inhibitory decision rules: for the most part of decision tables for each row during each step the greedy algorithm chooses an attribute that separates from the considered row at least one-half of rows that should be separated. Similar results can be obtained for partial inhibitory association rules over information systems. To this end, it is enough to fix an arbitrary attribute a i of the information system as the decision attribute and study inhibitory association rules with the right-hand side of the kind ai ≠ c as inhibitory decision rules over the obtained decision system (decision table).

UR - http://www.scopus.com/inward/record.url?scp=51849154685&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-85638-2_4

DO - 10.1007/978-3-540-85638-2_4

M3 - Conference contribution

AN - SCOPUS:51849154685

SN - 9783540856375

VL - 163

T3 - Studies in Computational Intelligence

SP - 43

EP - 62

BT - Inhibitory Rules in Data Analysis

ER -