Multi-Objective Genetic and Fuzzy Approaches in Rule Mining Problem of Knowledge Discovery in Databases

Introduction

Knowledge Discovery in Databases (KDD) (Fayyad, Piatetsky-Shapiro, & Smyth, 1996) refers to the non-trivial, iterative, and interactive process of discovering high-level/abstract knowledge from low level/raw datasets in the form of patterns, models, rules, etc., which are convincing, narrative, potentially useful, and comprehensible.

Data mining (Cios, Pedrycz, Swiniarski, & Kurgan, 2012) is used as a central step of KDD process, performed either through semi-automatic, or automatic methods. In particular, it involves inferring algorithms for tasks like classification, association rule mining, associative classification, clustering, data visualization, and sequential pattern analysis (Han & Kamber, 2006) for exploring the data and discovering previously unknown patterns.

Fuzzy logic/fuzzy sets (Zadeh, 1988) used in knowledge discovery process, make them more flexible in comparison to classical hard computing techniques and make the system tolerant to vagueness, uncertainty, biased, and approximation. Furthermore, it makes use of this tolerance in achieving tractability, robustness and low cost solution to real-world problems. Use of linguistic variables and linguistic terms used in knowledge mining/rule mining process enhance the knowledge representation and facilitates the interpretation of knowledge/rules in linguistic terms as well as successfully evades unnatural boundaries arise in the partitioning of the attribute domains.

Rule mining (Fayyad, Piatetsky-Shapiro, & Smyth, 1996) is an emerging approach in data mining employed to handle and analyze the huge amount of data in order to extract the wealth of knowledge. It is a process of discovering knowledge in the form of IF-THEN rules from large datasets. These knowledge representation schemes in IF-THEN rule format are popular as the discovered knowledge is represented at a high level of abstraction using few logical conditions, which make knowledge representation more comprehensible.

The IF-THEN rule is an expression of the form:

The “IF” part of the rule is called antecedent or precondition, which consists of one or more attribute tests that are logically connected and “THEN” part is called consequent.

Basing on the types of set utilized in attribute representation the IF-THEN are classified as: crisp rules which uses crisp set and fuzzy rules which uses fuzzy sets.

Crisp rules are best suited for categorical/Boolean data. In case of quantitative/continuous data, these rules use a sharp cutoff in selecting attributes, which is a major drawback.

As an example, let us consider a rule used for a job selection;

In this rule, the candidate either with one day less than age 18 or having height 164.9cm or having weight 54.95kg is not selected, which is very unsympathetic.

On the contrary fuzzy rules uses linguistic variables and linguistic values that are defined by context-dependent fuzzy sets whose meanings are spell out by membership functions. In particular very-young, young, middle-aged, old and very-old for age attribute, short, medium and tall for height attribute and low-weight, medium-weight and high-weight for weight attribute and determine the membership degree in [0,1] of the attribute using fuzzy set. Hence the height of 164 is regarded as tall with membership degree less than 165 as tall.

Hence using fuzzy set the above crisp rule towards job selection may look like;

In this rule the candidate with one day less than age 18 or having height 164.9cm or having weight 54.95kg may be selected.

Hence fuzzy rules are popular over comparison to crisp rules. Moreover, the features like: capability to handle data with non-linearity, vagueness, and impreciseness enhance the popularity of fuzzy rules.