Search

Association rules are popular form for knowledge discovery domain. They are used for finding interesting relationships and patterns hidden in large data sets and in the area of associative classification, where usually rules with one item in the right-hand side are considered. There are many different approaches and algorithms for mining association rules. One of the most popular group are methods which are based on mining frequent itemsets, usually applied for data in transaction format. Such data can be transformed to binary information system which corresponds to matrix data format. Technological development means that we are dealing with an increasing amount of data that can be heterogeneous, taking into account their format and location. In this paper, we assume that dispersed data is represented by a finite set S of information systems with equal sets of attributes. We discuss one of the possible ways to the study association rules common to all information systems from the set S : building a joint information system for which the set of true association rules that are realizable for a given row r and have given attribute f on the right-hand side coincides with the set of association rules that are true for all information systems from S , are realizable for the row r , and have the attribute f on the right-hand side. We show how to build a joint information system in a polynomial time. When we build such an information system, we can apply to it various association rule learning algorithms. [ABSTRACT FROM AUTHOR]

In the paper, an application of dynamic programming approach to global optimization of approximate association rules relative to coverage and length is presented. It is an extension of the dynamic programming approach to optimization of decision rules to inconsistent tables. Experimental results with data sets from UCI Machine Learning Repository are included. [ABSTRACT FROM AUTHOR]

The paper describes a new tool for study relationships between length and coverage of exact decision rules. This tool is based on dynamic programming approach. We also present results of experiments with decision tables from UCI Machine Learning Repository. [ABSTRACT FROM AUTHOR]

Abstract: In this work, we consider so-called nonredundant inhibitory rules, containing an expression “attribute:F value” on the right- hand side, for which the number of misclassifications is at most a threshold γ. We study a dynamic programming approach for description of the considered set of rules. This approach allows also the optimization of nonredundant inhibitory rules relative to the length and coverage. The aim of this paper is to investigate an additional possibility of optimization relative to the number of misclassifications. The results of experiments with decision tables from the UCI Machine Learning Repository show this additional optimization achieves a fewer misclassifications. Thus, the proposed optimization procedure is promising. [Copyright &y& Elsevier]

Abstract: In this paper, we present three approaches for construction of decision rules for decision tables with many-valued decisions. We construct decision rules directly for rows of decision table, based on paths in decision tree, and based on attributes contained in a test (super-reduct). Experimental results for the data sets taken from UCI Machine Learning Repository, contain comparison of the maximum and the average length of rules for the mentioned approaches. [Copyright &y& Elsevier]

Conventional decision trees use queries each of which is based on one attribute. In this study, we also examine decision trees that handle additional queries based on hypotheses. This kind of query is similar to the equivalence queries considered in exact learning. Earlier, we designed dynamic programming algorithms for the computation of the minimum depth and the minimum number of internal nodes in decision trees that have hypotheses. Modification of these algorithms considered in the present paper permits us to build decision trees with hypotheses that are optimal relative to the depth or relative to the number of the internal nodes. We compare the length and coverage of decision rules extracted from optimal decision trees with hypotheses and decision rules extracted from optimal conventional decision trees to choose the ones that are preferable as a tool for the representation of information. To this end, we conduct computer experiments on various decision tables from the UCI Machine Learning Repository. In addition, we also consider decision tables for randomly generated Boolean functions. The collected results show that the decision rules derived from decision trees with hypotheses in many cases are better than the rules extracted from conventional decision trees. [ABSTRACT FROM AUTHOR]

In the paper, we study a greedy algorithm for construction of decision trees. This algorithm is applicable to decision tables with many-valued decisions where each row is labeled with a set of decisions. For a given row, we should find a decision from the set attached to this row. Experimental results for data sets from UCI Machine Learning Repository and randomly generated tables are presented. We make a comparative study of the depth and average depth of the constructed decision trees for proposed approach and approach based on generalized decision. The obtained results show that the proposed approach can be useful from the point of view of knowledge representation and algorithm construction. [ABSTRACT FROM AUTHOR]

The paper is devoted to the study of a greedy algorithm for construction of approximate tests (super-reducts). This algorithm is applicable to decision tables with many-valued decisions where each row is labeled with a set of decisions. For a given row, we should find a decision from the set attached to this row. We consider bounds on the precision of this algorithm relative to the cardinality of tests. [ABSTRACT FROM AUTHOR]

This paper is devoted to the study of an extension of dynamic programming approach which allows optimization of partial decision rules relative to the length or coverage. We introduce an uncertainty measure J(T) which is the difference between number of rows in a decision table T and number of rows with the most common decision for T. For a nonnegative real number γ, we consider γ-decision rules (partial decision rules) that localize rows in subtables of T with uncertainty at most γ. Presented algorithm constructs a directed acyclic graph Δγ(T) which nodes are subtables of the decision table T given by systems of equations of the kind 'attribute = value'. This algorithm finishes the partitioning of a subtable when its uncertainty is at most γ. The graph Δγ(T) allows us to describe the whole set of so-called irredundant γ-decision rules. We can optimize such set of rules according to length or coverage. This paper contains also results of experiments with decision tables from UCI Machine Learning Repository. [ABSTRACT FROM AUTHOR]