Data Mining: An Overview from a Database Perspective <s> Mining di erent kinds of knowledge from databases <s> Abstract : The entries in this bibliography are classified according to a taxonomy of time in databases developed by Snodgrass and Ahn (Temporal Databases, IEEE Computer, 19, No. 9, September, 1986, pp. 35-42.) Papers that propose augmenting conventional database management systems to represent transaction time (that is, the time when information is entered into a database) are listed in Section 2. Papers that propose augmenting conventional database management systems to represent valid time (that is, the time that information models in the real world) are listed in Section 3. Finally, papers that propose augmenting conventional databases with both aspects of time are listed in Section 4. <s> BIB001 </s> Data Mining: An Overview from a Database Perspective <s> Mining di erent kinds of knowledge from databases <s> We are given a large database of customer transactions. Each transaction consists of items purchased by a customer in a visit. We present an efficient algorithm that generates all significant association rules between items in the database. The algorithm incorporates buffer management and novel estimation and pruning techniques. We also present results of applying this algorithm to sales data obtained from a large retailing company, which shows the effectiveness of the algorithm. <s> BIB002 </s> Data Mining: An Overview from a Database Perspective <s> Mining di erent kinds of knowledge from databases <s> Spatial and temporal databases are important and well-established sub-disciplines of database research. Some 350 papers in temporal databases have appeared, authored by almost 300 researchers. The literature on spatial databases is also substantial; the bibliography of Samet's landmark book on spatial data structures lists 823 references. <s> BIB003 </s> Data Mining: An Overview from a Database Perspective <s> Mining di erent kinds of knowledge from databases <s> The authors' perspective of database mining as the confluence of machine learning techniques and the performance emphasis of database technology is presented. Three classes of database mining problems involving classification, associations, and sequences are described. It is argued that these problems can be uniformly viewed as requiring discovery of rules embedded in massive amounts of data. A model and some basic operations for the process of rule discovery are described. It is shown how the database mining problems considered map to this model, and how they can be solved by using the basic operations proposed. An example is given of an algorithm for classification obtained by combining the basic rule discovery operations. This algorithm is efficient in discovering classification rules and has accuracy comparable to ID3, one of the best current classifiers. > <s> BIB004 </s> Data Mining: An Overview from a Database Perspective <s> Mining di erent kinds of knowledge from databases <s> Previous studies on mining association rules find rules at single concept level, however, mining association rules at multiple concept levels may lead to the discovery of more specific and concrete knowledge from data. In this study, a top-down progressive deepening method is developed for mining multiplelevel association rules from large transaction databases by extension of some existing association rule mining techniques. A group of variant algorithms are proposed based on the ways of sharing intermediate results, with the relative performance tested on different kinds of data. Relaxation of the rule conditions for finding “level-crossing” association rules is also discussed in the paper. <s> BIB005 </s> Data Mining: An Overview from a Database Perspective <s> Mining di erent kinds of knowledge from databases <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> BIB006
Data mining is an application-dependent issue and di erent applications may require di erent mining techniques to cope with. In general, the kinds of knowledge which can be discovered in a database are categorized as follows. Mining association rules in transactional or relational databases has recently attracted a lot of attention in database communities BIB002  BIB005    BIB006 . The task is to derive a set of strong association rules in the form of \A 1^ ^A m =) B 1^ ^B n ," where A i (for i 2 f1; : : :; mg) and B j (for j 2 f1; : : :; ng) are sets of attribute-values, from the relevant data sets in a database. For example, one may nd, from a large set of transaction data, such an association rule as if a customer buys (one brand of) milk, he/she usually buys (another brand of) bread in the same transaction. Since mining association rules may require to repeatedly scan through a large transaction database to nd di erent association patterns, the amount of processing could be huge, and performance improvement is an essential concern at mining such rules. E cient algorithms for mining association rules and some methods for further performance enhancements will be examined in Section 3. The most popularly used data mining and data analysis tools associated with database system products are data generalization and summarization tools, which carry several alternative names, such as on-line analytical processing (OLAP), multiple-dimensional databases, data cubes, data abstraction, generalization, summarization, characterization, etc. Data generalization and summarization presents the general characteristics or a summarized high-level view over a set of user-speci ed data in a database. For example, the general characteristics of the technical sta s in a company can be described as a set of characteristic rules or a set of generalized summary tables. Moreover, it is often desirable to present generalized views about the data at multiple abstraction levels. An overview on multi-level data generalization, summarization, and characterization is presented in Section 4. Another important application of data mining is the ability to perform classi cation in a huge amount of data. This is referred to as mining classi cation rules. Data classi cation is to classify a set of data based on their values in certain attributes. For example, it is desirable for a car dealer to classify its customers according to their preference for cars so that the sales persons will know whom to approach, and catalogs of new models can be mailed directly to those customers with identi ed features so as to maximize the business opportunity. Some studies in classi cation rules will be reviewed in Section 5. In Section 6, we discuss the techniques on data clustering. Basically, data clustering is to group a set of data (without a prede ned class attribute), based on the conceptual clustering principle: maximizing the intraclass similarity and minimizing the interclass similarity. For example, a set of commodity objects can be rst clustered into a set of classes and then a set of rules can be derived based on such a classi cation. Such clustering may facilitate taxonomy formation, which means the organization of observations into a hierarchy of classes that group similar events together. Temporal or spatial-temporal data constitutes a large portion of data stored in computers BIB003 BIB001 . Examples of this type of database include: nancial database for stock price index, medical databases, and multimedia databases, to name a few. Searching for similar patterns in a temporal or spatial-temporal database is essential in many data mining operations  BIB004  in order to discover and predict the risk, causality, and trend associated with a speci c pattern. Typical queries for this type of database include identifying companies with similar growth patterns, products with similar selling patterns, stocks with similar price movement, images with similar weather patterns, geological features, environmental pollutions, or astrophysical patterns. These queries invariably require similarity matches as opposed to exact matches. The approach of pattern-based similarity search is reviewed in Section 7. In a distributed information providing environment, documents or objects are usually linked together to facilitate interactive access. Understanding user access patterns in such environments will not only help improving the system design but also be able to lead to better marketing decisions. Capturing user access patterns in such environments is referred to as mining path traversal patterns. Notice, however, that since users are traveling along the information providing services to search for the desired information, some objects are visited because of their locations rather than their content, showing the very di erence between the traversal pattern problem and others which are mainly based on customer transactions. The capability of mining path traversal patterns is discussed in Section 8. In addition to the issues considered above, there are certainly many other aspects on data mining that are worthy of studying. It is often necessary to use a data mining query language or graphical user interface to specify the interesting subset of data, the relevant set of attributes, and the kinds of rules to be discovered. Moreover, it is often necessary to perform interactive data mining to examine, transform, and manipulate intermediate data mining results, focus at di erent concept levels, or test di erent kinds of thresholds. Visual representation of data and knowledge may facilitate interactive knowledge mining in databases.