Search

The paper presents the proposed research methodology, dedicated to the application of greedy heuristics as a way of gathering information about available features. Discovered knowledge, represented in the form of generated decision rules, was employed to support feature selection and reduction process for induction of decision rules with classical rough set approach. Observations were executed over input data sets discretised by several methods. Experimental results show that elimination of less relevant attributes through the proposed methodology led to inferring rule sets with reduced cardinalities, while maintaining rule quality necessary for satisfactory classification.

23rd International Conference on Knowledge-Based and Intelligent Information & Engineering Systems - early article, The paper presents research on unsupervised and supervised discretisation of input data used in execution of stylometric tasks of authorship attribution. Basing on numeric characterisation of writing styles, recognition of authorship is performed by decision rules, as their transparent structure enhances understanding of discovered knowledge. The performance of rule classifiers, constructed in rough set approach, is studied in the context of a strategy employed for resolving conflicts. It is also contrasted with that of other selected inducers.

Typically discretisation procedures are implemented as a part of initial pre-processing of data, before knowledge mining is employed. It means that conclusions and observations are based on reduced data, as usually by discretisation some information is discarded. The paper presents a different approach, with taking advantage of discretisation executed after data mining. In the described study firstly decision rules were induced from real-valued features. Secondly, data sets were discretised. Using categories found for attributes, in the third step conditions included in inferred rules were translated into discrete domain. The properties and performance of rule classifiers were tested in the domain of stylometric analysis of texts, where writing styles were defined through quantitative attributes of continuous nature. The performed experiments show that the proposed processing leads to sets of rules with significantly reduced sizes while maintaining quality of predictions, and allows to test many data discretisation methods at the acceptable computational costs.

In the paper, an application of dynamic programming approach for optimization of association rules from the point of view of knowledge representation is considered. 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.

Technological progress of the ever evolving world is connected with the need of developing methods for extracting knowledge from available data, distinguishing variables that are relevant from irrelevant, and reduction of dimensionality by selection of the most informative and important descriptors. As a result, the field of feature selection for data and pattern recognition is studied with such unceasing intensity by researchers, that it is not possible to present all facets of their investigations. The aim of this chapter is to provide a brief overview of some recent advances in the domain, presented as chapters included in this monograph.

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.

This paper is devoted to the consideration of software system Dagger created 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 of Dagger and consider examples of this system’s work on decision tables from UCI Machine Learning Repository. We also use Dagger to compare 16 different greedy algorithms for decision tree construction.

The paper describes research on filtering decision rules with continuous and discretised condition attributes while combining characteristics of these attributes returned from supervised discretisation with their ranking. Numbers of intervals required for partitioning of attributes values imposed their grouping into corresponding categories, and for each group separately ranking procedures with Relief algorithm were executed. Information about numbers of bins combined with ranking positions were next exploited for selection of rules induced within rough set approaches. Filtering rules was performed directly by their conditions, or by calculating defined measures based on attribute weights, returning shortened decision algorithms with at least the same or improved classification accuracy.

This paper is devoted to the study of an extension of dynamic programming approach which allows sequential optimization of approximate decision rules relative to the length and coverage. We introduce an uncertainty measure R(T) which is the number of unordered pairs of rows with different decisions in the decision table T. For a nonnegative real number @b, we consider @b-decision rules that localize rows in subtables of T with uncertainty at most @b. Our algorithm constructs a directed acyclic graph @D"@b(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 @b. The graph @D"@b(T) allows us to describe the whole set of so-called irredundant @b-decision rules. We can describe all irredundant @b-decision rules with minimum length, and after that among these rules describe all rules with maximum coverage. We can also change the order of optimization. The consideration of irredundant rules only does not change the results of optimization. This paper contains also results of experiments with decision tables from UCI Machine Learning Repository.

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.

The paper is devoted to the study of a greedy algorithm for construction of approximate decision rules. 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 length of rules. To illustrate proposed approach we study a problem of recognition of labels of points in the plain. This paper contains also results of experiments with modified decision tables from UCI Machine Learning Repository.

Test Theory (TT) was created by Yablonskii and Chegis in the middle of fifties of the last century as a tool for analysis of problems connected with control and diagnosis of faults in circuits. The first short paper [75] was published in 1955, and the principal paper [10] - in 1958. In 1966 Dmitriev, Zhuravlev and Krendelev [16] adapted test approach to the study of pattern recognition (prediction) problems. Later TT was developed in the two directions related to tools and applications.

In the paper, we present an algorithm for optimization of approximate decision rules relative to the number of misclassifications. The considered algorithm is based on extensions of dynamic programming and constructs a directed acyclic graph Δβ(T). Based on this graph we can describe the whole set of so-called irredundant β-decision rules. We can optimize rules from this set according to the number of misclassifications. Results of experiments with decision tables from the UCI Machine Learning Repository are presented.

In this chapter, we consider two approaches to the study of decision trees and decision rule systems for problems over finite and infinite information systems. Local approach is based on the assumption that only attributes contained in a problem description are used in decision trees and decision rules systems solving this problem. Global approach is based on the assumption that any attributes from the considered information system can be used in decision trees and decision rule systems solving the problem.

We describe an online learning algorithm that builds a system of decision rules for a classification problem. Rules are constructed according to the minimum description length principle by a greedy algorithm or using the dynamic programming approach.

In the paper, the accuracy of greedy algorithms for construction of partial covers, reducts and decision rules is considered. Bounds on the minimal complexity of partial covers, reducts and decision rules based on an information about greedy algorithm work are studied. The results of experiments with greedy algorithms are described.

In the paper the accuracy of greedy algorithms with weights for construction of partial covers, reducts and decision rules is considered. Bounds on minimal weight of partial covers, reducts and decision rules based on an information on greedy algorithm work are studied. Results of experiments with software implementation of greedy algorithms are described.