Data Mining and Knowledge Discovery Handbook, 2 Edition part 33. Knowledge Discovery demonstrates intelligent computing at its best, and is the most desirable and interesting end-product of Information Technology. To be able to discover and to extract knowledge from data is a task that many researchers and practitioners are endeavoring to accomplish. There is a lot of hidden knowledge waiting to be discovered – this is the challenge created by today’s abundance of data. Data Mining and Knowledge Discovery Handbook, 2nd Edition organizes the most current concepts, theories, standards, methodologies, trends, challenges and applications of data mining (DM) and knowledge discovery. | 300 Frank Höppner of an instance with A7 1 A18 1 and Ai 0 for all other attributes is therefore a set-oriented notation A7 A18 . The task of association rule mining is basically to examine relationships between all possible subsets. For instance a rule A9 A37 A214 A189 A165 would indicate that whenever a database record possesses attributes values A9 1 A37 1 and A214 1 also A189 1 and A165 1 will hold. The main difference to classification see Chapter II in this book is that association rules are usually not restricted to the prediction of a single attribute of interest. Even if we consider only n 100 attributes and rules with two items in antecedent and consequent we have already more than 23 500 000 possible rules. Every possible rule has to be verified against a very large database where a single scan takes already considerable time. For this challenging task the technique of association rule mining has been developed Agrawal and Shafer 1996 . Formal Problem Definition Let I a1 . . an be a set of literals properties or items. A record t1 . tn e dom A1 x . x dom An from our transaction database with schema S A1 . An can be reformulated as an itemset T by ai e T ti 1. We want to use the motivation of the introductory example to define an association explicitly. How can we characterize associated products Definition We call a set Z CI an association if the frequency of occurrences of Z deviates from our expectation given the frequencies of individual X e Z. If the probability of having sausages S or mustard M in the shopping carts of our customers is 10 and 4 resp. we expect of the customers to buy both products at the same time. If we instead observe this behaviour for 1 of the customers this deviates from our expectations and thus S M is an association. Do sausages require mustard S M or does mustard require sausages M S If preference or causality induces a kind of direction in the association it can be captured by rules Definition We call X Y an .
