A Survey of Evolutionary Algorithms for Data Mining and Knowledge Discovery <s> Discovered-Knowledge Postprocessing. <s> In a learning situation with noisy data, a generalization procedure may find a sizeable collection of partial generalizations each of them covering a part of the positive examples and, in general, a few negative examples. The task is to choose a moderately sized sub-collection of partial generalizations that are sufficiently different from one another. The idea is that the user is less interested in all the “best” partial generalizations (according to a given criterion) if they are quite similar rather than in some diverse ones, even if they are, taken individually, less satisfactory. This vague goal concept is made more precise and a procedure is developed and examined that employs two notions: a measure for the quality of a single generalization (called evidence) and an asymmetric measure for the similarity of two generalizations (called affinity). These two co-operate in suppressing generalizations that are worse than, but not too different from, another generalization. The selection procedure works satisfactorily in different environments. <s> BIB001 </s> A Survey of Evolutionary Algorithms for Data Mining and Knowledge Discovery <s> Discovered-Knowledge Postprocessing. <s> Association rules, introduced by Agrawal, Imielinski, and Swami, are rules of the form “for 90% of the rows of the relation, if the row has value 1 in the columns in set W , then it has 1 also in column B”. Efficient methods exist for discovering association rules from large collections of data. The number of discovered rules can, however, be so large that browsing the rule set and finding interesting rules from it can be quite difficult for the user. We show how a simple formalism of rule templates makes it possible to easily describe the structure of interesting rules. We also give examples of visualization of rules, and show how a visualization tool interfaces with rule templates. <s> BIB002 </s> A Survey of Evolutionary Algorithms for Data Mining and Knowledge Discovery <s> Discovered-Knowledge Postprocessing. <s> One of the important problems in data mining is the evaluation of subjective interestingness of the discovered rules. Past research has found that in many real-life applications it is easy to generate a large number of rules from the database, but most of the rules are not useful or interesting to the user. Due to the large number of rules, it is difficult for the user to analyze them manually in order to identify those interesting ones. Whether a rule is of interest to a user depends on his/her existing knowledge of the domain, and his/her interests. In this paper, we propose a technique that analyzes the discovered rules against a specific type of existing knowledge, which we call general impressions, to help the user identify interesting rules. We first propose a representation language to allow general impressions to be specified. We then present some algorithms to analyze the discovered classification rules against a set of general impressions. The results of the analysis tell us which rules conform to the general impressions and which rules are unexpected. Unexpected rules are by definition interesting. <s> BIB003 </s> A Survey of Evolutionary Algorithms for Data Mining and Knowledge Discovery <s> Discovered-Knowledge Postprocessing. <s> Most of the literature argues that surprisingness is an inherently subjective aspect of the discovered knowledge, which cannot be measured in objective terms. This paper departs from this view, and it has a twofold goal: (1) showing that it is indeed possible to define objective (rather than subjective) measures of discovered rule surprisingness; (2) proposing new ideas and methods for defining objective rule surprisingness measures. <s> BIB004
It is often the case that the knowledge discovered by a data mining algorithm needs to undergo some kind of postprocessing. Since in this chapter we focus on discovered knowledge expressed as IF-THEN prediction rules, we are mainly interested in the postprocessing of a discovered rule set. There are two main motivations for such postprocessing. First, when the discovered rule set is large, we often want to simplify it -i.e., to remove some rules and/or rule conditions -in order to improve knowledge comprehensibility for the user. Second, we often want to extract a subset of interesting rules, among all discovered ones. The reason is that although many data mining algorithms were designed to discover accurate, comprehensible rules, most of these algorithms were not designed to discover interesting rules, which is a rather more difficult and ambitious goal, as mentioned in section 2.1. Methods for selection of interesting rules can be roughly divided into subjective and objective methods. Subjective methods are user-driven and domain-dependent. For instance, the user may specify rule templates, indicating which combination of attributes must occur in the rule for it to be considered interesting -this approach has been used mainly in the context of association rules BIB002 . As another example of a subjective method, the user can give the system a general, high-level description of his/her previous knowledge about the domain, so that the system can select only the discovered rules which represent previously-unknown knowledge for the user BIB003 . By contrast, objective methods are data-driven and domain-independent. Some of these methods are based on the idea of comparing a discovered rule against other rules, rather than against the user's beliefs. In this case the basic idea is that the interestingness of a rule depends not only on the quality of the rule itself, but also on its similarity to other rules. Some objective measures of rule interestingness are discussed in BIB001 , BIB004 , [23] . We believe that ideally a combination of subjective and objective approaches should be used to try to solve the very hard problem of returning interesting knowledge to the user.