Search

Decision rules belong to known forms of knowledge representation. Among popular measures of their quality length and support can be distinguished. Shorter rules are easier to understand and interpret. Support allows to present patterns hidden in the data. Nowadays, data mining tasks are oriented toward extracting knowledge from data in both distributed and centralized forms. Learning decision rules from a decision tree is a relatively simple task. However, the challenge arises when decision rules are induced from a set of decision trees. Moreover, in the case of distributed data, the decision trees may be constructed independently on different sources, and merging them into a unified set requires resolving conflicts and inconsistencies. In this paper, decision rules are constructed from distributed data based on decision trees induced using the randomly chosen attributes as the splitting criterion. The aim of the study is to compare the quality of two algorithms for constructing rules which are true for a maximum number of trees. The comparison was made based on three factors: the number of trees for which the rule is true, their length and support. Based on performed experiments it was possible to see that the number of true rules for the maximum number of decision trees from the set is greater for algorithm A than for heuristics H. This algorithm allows the induction of shorter rules with greater support compared to heuristic H. However, it should be also noted that the rules induced by heuristic H are often true for a larger number of trees than the rules constructed by algorithm A. Thus, both algorithms can be applied to distributed data. [ABSTRACT FROM AUTHOR]

In this article, we present a modification of the algorithm based on EAV (entity–attribute–value) model, for induction of decision rules, utilizing novel approach for attribute ranking. The selection of attributes used as premises of decision rules, is an important stage of the process of rules induction. In the presented approach, this task is realized using ranking of attributes based on standard deviation of attributes' values per decision classes, which is considered as a distinguishability level. The presented approach allows to work not only with numerical values of attributes but also with categorical ones. For this purpose, an additional step of data transformation into a matrix format has been proposed. It allows to transform data table into a binary one with proper equivalents of categorical values of attributes and ensures independence of the influence of the attribute selection function from the data type of variables. The motivation for the proposed method is the development of an algorithm which allows to construct rules close to optimal ones in terms of length, while maintaining enough good classification quality. The experiments presented in the paper have been performed on data sets from UCI ML Repository, comparing results of the proposed approach with three selected greedy heuristics for induction of decision rules, taking into consideration classification accuracy and length and support of constructed rules. The obtained results show that for the most part of datasests, the average length of rules obtained for 80% of best attributes from the ranking is very close to values obtained for the whole set of attributes. In case of classification accuracy, for 50% of considered datasets, results obtained for 80% of best attributes from the ranking are higher or the same as results obtained for the whole set of attributes. [ABSTRACT FROM AUTHOR]

In this paper, we deal with distributed data represented either as a finite set T of decision tables with equal sets of attributes or a finite set I of information systems with equal sets of attributes. In the former case, we discuss a way to the study decision trees common to all tables from the set T : building a decision table in which the set of decision trees coincides with the set of decision trees common to all tables from T. We show when we can build such a decision table and how to build it in a polynomial time. If we have such a table, we can apply various decision tree learning algorithms to it. We extend the considered approach to the study of test (reducts) and decision rules common to all tables from T. In the latter case, we discuss a way to study the association rules common to all information systems from the set I : building a joint information system for which the set of true association rules that are realizable for a given row ρ and have a given attribute a on the right-hand side coincides with the set of association rules that are true for all information systems from I , have the attribute a on the right-hand side, and are realizable for the row ρ. We then show how to build a joint information system in a polynomial time. When we build such an information system, we can apply various association rule learning algorithms to it. [ABSTRACT FROM AUTHOR]

Decision and association rules are known and popular forms of knowledge representation. They are used in many areas of data mining and have different applications. One of them is associative classification which finds association rules that have only class label in the consequent part and satisfies the minimum support and confidence thresholds. The aim of this paper is to merge set of association rules induced by Apriori algorithm with the set of decision rules induced by selected heuristics, forming a combined classifier. Experimental results concern parameters of induced sets of rules as number of unique rules, their length and support, and classification accuracy involving two voting strategies as decision list and standard voting. It was shown, that for considered parameters of Apriori algorithm, the combined classifier allows to obtain improved classification accuracy compared to the classifier based only on association rules. Therefore selected heuristic for induction of decision rules can be applied in associative classification tasks. [ABSTRACT FROM AUTHOR]

The area of feature selection methods constantly expands along with the development of artificial intelligence domain, and has great impact on almost every field, whenever data is processed and explored. The paper presents research where a ranking method was proposed, inspired by an approach which comes from an algorithm for induction of decision rules. The ranking procedure was based on calculation of standard deviation for attributes, taking into account assigned class labels. This method was compared with another ranking mechanism, a modified version of popular Relief algorithm, with incorporating characteristics of variables by supervised discretisation. Comparison of obtained results included the aspect of knowledge representation as well as the perspective of the accuracy for constructed rule-based classifiers. The experiments were performed on datasets from stylometry domain, where authorship attribution was considered as a classification task, and stylometric descriptors as characteristic features defining writing styles of authors. [ABSTRACT FROM AUTHOR]

Decision rules are popular form of knowledge representation. From this point of view, length of such rules is an important factor since it influences on data understanding by experts. Unfortunately, the problem of construction of short rules is NP-hard, so different heuristics are discussed in the literature. The paper presents comparison of two selected methods for decision rules construction. The first one is connected with a new algorithm based on EAV model, the second one - with construction of rules based on reduct. Decision rules were induced for data sets from UCI ML Repository and compared from the point of view of length and support, and from the point of view of classification accuracy. Results of Wilcoxon test are also included. [ABSTRACT FROM AUTHOR]

The paper is dedicated to the area of feature selection, in particular a notion of attribute rankings that allow to estimate importance of variables. In the research presented for ranking construction a new weighting factor was defined, based on relative reducts. A reduct constitutes an embedded mechanism of feature selection, specific to rough set theory. The proposed factor takes into account the number of reducts in which a given attribute exists, as well as lengths of reducts. Two approaches for reduct generation were employed and compared, with search executed by a genetic algorithm. To validate the usefulness of the reduct-based rankings in the process of feature reduction, for gradually decreasing subsets of attributes, selected through rankings, sets of decision rules were induced in classical rough set approach. The performance of all rule classifiers was evaluated, and experimental results showed that the proposed rankings led to at least the same, or even increased classification accuracy for reduced sets of features than in the case of operating on the entire set of condition attributes. The experiments were performed on datasets from stylometry domain, with treating authorship attribution as a classification task, and stylometric descriptors as characteristic features defining writing styles. [ABSTRACT FROM AUTHOR]

The paper presents research focused on decision reducts, a feature reduction mechanism inherent to rough sets theory. As a reduct enables to protect the discriminative properties of attributes with respect to described concepts, from the point of data representation, a reduct length is considered to be the most important measure of its quality. However, such approach is insufficient while taking into account the performance of a reduct-based rule classifier applied to test samples. When many reducts of the same length are available, they can lead to vastly different predictions. The paper provides a description for the proposed procedure for iterative reduct generation, which results in decrease of diversity in the observed levels of accuracy, supporting reduct selection. The procedure was applied for binary classification with balanced classes, for the stylometric task of authorship attribution. [ABSTRACT FROM AUTHOR]

In this paper, seven greedy heuristics for construction of association rules are compared from the point of view of the length and coverage of constructed rules. The obtained rules are compared also with optimal ones constructed by dynamic programming algorithms. The average relative difference between length of rules constructed by the best heuristic and minimum length of rules is at most 4%. The same situation is with coverage. [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]

In the paper, an application of dynamic programming approach for optimization of association rules from the point of view of knowledge representation is considered. The association rule set is optimized in two stages, first for minimum cardinality and then for minimum length of rules. Experimental results present cardinality of the set of association rules constructed for information system and lower bound on minimum possible cardinality of rule set based on the information obtained during algorithm work as well as obtained results for length. [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]

This paper is devoted to the consideration of software systemDaggercreated in KAUST. This system is based on extensions of dynamic programming. It allows sequential optimization of decision trees and rules relative to different cost functions, derivation of relationships between two cost functions (in particular, between number of misclassifications and depth of decision trees), and between cost and uncertainty of decision trees. We describe features ofDaggerand consider examples of this system’s work on decision tables from UCI Machine Learning Repository. We also useDaggerto compare 16 different greedy algorithms for decision tree construction. [ABSTRACT FROM AUTHOR]

Based on dynamic programming approach we design algorithms for sequential optimization of exact and approximate decision rules relative to the length and coverage [3, 4]. In this paper, we use optimal rules to construct classifiers, and study two questions: (i) which rules are better from the point of view of classification - exact or approximate; and (ii) which order of optimization gives better results of classifier work: length, length+coverage, coverage, or coverage+length. Experimental results show that, on average, classifiers based on exact rules are better than classifiers based on approximate rules, and sequential optimization (length+coverage or coverage+length) is better than the ordinary optimization (length or coverage). [ABSTRACT FROM AUTHOR]

In the paper, an approach for decision rules construction is proposed. It is studied from the point of view of the supervised machine learning task, i.e., classification, and from the point of view of knowledge representation. Generated rules provide comparable classification results to the dynamic programming approach for optimization of decision rules relative to length or support. However, the proposed algorithm is based on transformation of decision table into entity–attribute–value (EAV) format. Additionally, standard deviation function for computation of averages' values of attributes in particular decision classes was introduced. It allows to select from the whole set of attributes only these which provide the highest degree of information about the decision. Construction of decision rules is performed based on idea of partitioning of a decision table into corresponding subtables. In opposite to dynamic programming approach, not all attributes need to be taken into account but only these with the highest values of standard deviation per decision classes. Consequently, the proposed solution is more time efficient because of lower computational complexity. In the framework of experimental results, support and length of decision rules were computed and compared with the values of optimal rules. The classification error for data sets from UCI Machine Learning Repository was also obtained and compared with the ones for dynamic programming approach. Performed experiments show that constructed rules are not far from the optimal ones and classification results are comparable to these obtained in the framework of the dynamic programming extension. [ABSTRACT FROM AUTHOR]