Data Mining: An Overview from a Database Perspective <s> Interestingness of discovered association rules <s> Abstract We introduce the problem of mining generalized association rules. Given a large database of transactions, where each transaction consists of a set of items, and a taxonomy (is-a hierarchy) on the items, we find associations between items at any level of the taxonomy. For example, given a taxonomy that says that jackets is-a outerwear is-a clothes, we may infer a rule that “people who buy outerwear tend to buy shoes”. This rule may hold even if rules that “people who buy jackets tend to buy shoes”, and “people who buy clothes tend to buy shoes” do not hold. An obvious solution to the problem is to add all ancestors of each item in a transaction to the transaction, and then run any of the algorithms for mining association rules on these “extended transactions”. However, this “Basic” algorithm is not very fast; we present two algorithms, Cumulate and EstMerge, which run 2 to 5 times faster than Basic (and more than 100 times faster on one real-life dataset). Finally, we present a new interest-measure for rules which uses the information in the taxonomy. Given a user-specified “minimum-interest-level”, this measure prunes a large number of redundant rules; 40–60% of all the rules were pruned on two real-life datasets. <s> BIB001 </s> Data Mining: An Overview from a Database Perspective <s> Interestingness of discovered association rules <s> One of the central problems in the field of knowledge discovery is the development of good measures of interestingness of discovered patterns. Such measures of interestingness are divided into objective measures - those that depend only on the structure of a pattern and the underlying data used in the discovery process, and the subjective measures - those that also depend on the class of users who examine the pattern. The purpose of this paper is to lay the groundwork for a comprehensive study of subjective measures of interestingness. In the paper, we classify these measures into actionable and unexpected, and examine the relationship between them. The unexpected measure of interestingness is defined in terms of the belief system that the user has. Interestingness of a pattern is expressed in terms of how it affects the belief system. <s> BIB002
Notice that not all the discovered strong association rules (i.e., passing the minimum support and minimum con dence thresholds) are interesting enough to present. For example, consider the following case of mining the survey results in a school of 5,000 students. A retailer of breakfast cereal surveys the students on the activities they engage in the morning. The data show that 60% of students (i.e., 3,000 students) play basketball, 75% of students (i.e., 3,750 students) eat cereal, and 40% of them (i.e., 2,000 students) both play basketball and eat cereal. Suppose that a data mining program for discovering association rules is run on the data with the following settings: the minimal student support is 2,000 and the minimal con dence is 60%. The following association rule will be produced: \(play basketball) =) (eat cereal)," since this rule contains the minimal student support and the corresponding con dence 2000 3000 = 0:66 is larger than the minimal con dence required. However, the above association rule is misleading since the overall percentage of students eating cereal is 75%, even larger than 66%. That is, playing basketball and eating cereals are in fact negatively associated. Being involved in one decreases the likelihood of being involved in the other. Without fully understanding this aspect, one could make wrong business decisions from the rules derived. To lter out such kind of misleading associations, one may de ne that an association rule \A =) B" is interesting if its con dence exceeds a certain measure, or formally, P(A\B) P(A) is greater than d, a suitable constant. However, the simple argument we used in the example above suggests that the right heuristic to measure association should be P(A\B) P(A) ? P(B) > d, or alternatively, P(A \ B) ? P(A) P(B) > k, where k is a suitable constant. The expressions above essentially represent tests of statistical independence. Clearly, the factor of statistical dependence among various user behaviors analyzed has to be taken into consideration for the determination of the usefulness of association rules. There have been some interesting studies on the interestingness or usefulness of discovered rules, such as  BIB001 BIB002 . The notion of interestingness on discovered generalized association rules is introduced in 78]. The subjective measure of interestingness in knowledge discovery is studied in 77].