Data Mining: An Overview from a Database Perspective <s> Attribute-oriented induction approach <s> A quantitative rule is a rule associated with quantitative information which assesses the representativeness of the rule in the database. An efficient induction method is developed for learning quantitative rules in relational databases. With the assistance of knowledge about concept hierarchies, data relevance, and expected rule forms, attribute-oriented induction can be performed on the database, which integrates database operations with the learning process and provides a simple, efficient way of learning quantitative rules from large databases. The method involves the learning of both characteristic rules and classification rules. Quantitative information facilitates quantitative reasoning, incremental learning, and learning in the presence of noise. Moreover, learning qualitative rules can be treated as a special case of learning quantitative rules. It is shown that attribute-oriented induction provides an efficient and effective mechanism for learning various kinds of knowledge rules from relational databases. > <s> BIB001 </s> Data Mining: An Overview from a Database Perspective <s> Attribute-oriented induction approach <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> BIB002 </s> Data Mining: An Overview from a Database Perspective <s> Attribute-oriented induction approach <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> BIB003 </s> Data Mining: An Overview from a Database Perspective <s> Attribute-oriented induction approach <s> Spatial data mining, i.e., discovery of interesting, implicit knowledge in spatial databases, is an important task for understanding and use of spatial data- and knowledge-bases. In this paper, an efficient method for mining strong spatial association rules in geographic information databases is proposed and studied. A spatial association rule is a rule indicating certain association relationship among a set of spatial and possibly some nonspatial predicates. A strong rule indicates that the patterns in the rule have relatively frequent occurrences in the database and strong implication relationships. Several optimization techniques are explored, including a two-step spatial computation technique (approximate computation on large sets, and refined computations on small promising patterns), shared processing in the derivation of large predicates at multiple concept levels, etc. Our analysis shows that interesting association rules can be discovered efficiently in large spatial databases. <s> BIB004 </s> Data Mining: An Overview from a Database Perspective <s> Attribute-oriented induction approach <s> A data mining system, DBMiner, has been developed for interactive mining of multiple-level knowledge in large relational databases. The system implements a wide spectrum of data mining functions, including generalization, characterization, association, classification, and prediction. By incorporating several interesting data mining techniques, including attribute-oriented induction, statistical analysis, progressive deepening for mining multiple-level knowledge, and meta-rule guided mining, the system provides a user-friendly, interactive data mining environment with good performance. <s> BIB005
The data warehousing approach which uses materialized views are \o -line" database computation which may not correspond to the most up-to-date database contents. An alternative, online, generalization-based data analysis technique, is called attribute-oriented induction approach BIB001  . The approach takes a data mining query expressed in an SQL-like data mining query language and collects the set of relevant data in a database. Data generalization is then performed on the set of relevant data by applying a set of data generalization techniques 37, 40, 60], including attribute-removal, concept-tree climbing, attribute-threshold control, propagation of counts and other aggregate function values, etc. The generalized data is expressed in the form of a generalized relation on which many other operations or transformations can be performed to transform generalized data into di erent kinds of knowledge or map them into di erent forms 40]. For example, drill-down or roll-up operations can be performed to view data at multiple abstraction levels 36]; the generalized relation can be mapped into summarization tables, charts, curves, etc., for presentation and visualization; characteristic rules which summarize the generalized data characteristics in quantitative rule forms can be extracted; discriminant rules which contrast di erent classes of data at multiple abstraction levels can be extracted by grouping the set of comparison data into contrasting classes before data generalization; classi cation rules which classify data at di erent abstraction levels according to one or a set of classi cation attributes can be derived by applying a decision tree classi er 72] on the generalized data 42]; and association rules which associate a set of generalized attribute properties in a logic implication rule by integration of attribute-oriented induction and the methods for mining association rules  BIB002  BIB003 . Moreover, statistical pattern discovery can also be performed using attribute-oriented induction 24]. The core of the attribute-oriented induction technique is on-line data generalization which is performed by rst examining the data distribution for each attribute in the set of relevant data, calculating the corresponding abstraction level that data in each attribute should be generalized to, and then replacing each data tuple with its corresponding generalized tuple. The generaliza-tion process scans the data set only once and collects the aggregate values in the corresponding generalized relation or data cube. It is a highly e cient technique since the worst-case time complexity of the process is O(n), if a cube structure is used (desirable when the data cube is dense), or O(n log(p)), if a generalized relation is used (desirable when the corresponding cube is rather sparse), where n is the number of tuples in the set of relevant data and p is the size (i.e., number of tuples) of the generalized relation 40]. To support multiple-level data mining, especially the drill-down operations, the attributeoriented induction technique should generalize the set of relevant data to a minimal abstraction level and maintain such a minimally generalized relation (if expressed by a relational structure) or a minimally generalized cube (if expressed by a cube structure) to facilitate the traversals among multiple abstraction spaces. The roll-up of a generalized relation may simply start with this relation; however, the drill-down of the relation may start with the minimal generalized relation and perform data generalization to the corresponding abstraction levels 36]. The essential background knowledge applied in attribute-oriented induction is concept hierarchy (or lattice) associated with each attribute 37]. Most concept hierarchies are stored implicitly in databases. For example, a set of attributes in address(number; street; city; province; country) in a database schema represents the concept hierarchies of the attribute address. A set of attributes in a data relation, though seemingly no strong semantic linkages exist, may also form concept hierarchies (or lattices) among their supersets or subsets. For example, in the schema item(id; name; category; producer; date made; cost; price), \fcategory, producer, date madeg fcategory, date madeg" indicates the former forms a lower level concept than the latter. Moreover, rules and view de nitions can also be used as the de nitions of concept hierarchies 24]. Conceptual hierarchies for numerical or ordered attributes can be generated automatically based on the analysis of data distributions in the set of relevant data 38]. Moreover, a given hierarchy may not be best suited for a particular data mining task. Therefore, such hierarchies should be adjusted dynamically in many cases based on the analysis of data distributions of the corresponding set of data 38]. An an example, one may use data mining facilities to study the general characteristics of NSERC (Natural Science and Engineering Research Council of Canada) research grant database. To compare the research grants between`British Columbia' and`Alberta' (two neighbor provinces in Western Canada) in the discipline of`Computer (Science)' according to the attributes: disc code (discipline code) and grant category, the following data mining query can be speci ed in a data mining query language DMQL 42] The execution of this data mining query generates Table 1 which presents the di erences between the two provinces in terms of disc code, grant category and the number of the research grants. The column support% represents the number of research grants in this category vs. the total number of grants in its own province; where the comparison% represents the number of research grants in this category in one province vs. that of the other. For example, the rst (composite) row indicates that for Computer Science Infrastructure Grants in the range of 40Ks to 60Ks, British Columbia takes 2.00% of its total number of Computer Science Grants, whereas Alberta takes 1.72%; however, in comparison between these two provinces, British Columbia takes 66.67% of the share (in number) whereas Alberta takes only 33.33%. Other rows have similar interpretations. Notice with interactive data mining facilities, such as those provided in DBMiner, a user may perform roll-up or drill-down operations conveniently. For example, one may drill down oǹ grant category' to examine even ner grant categories such as 0-10Ks, 10-15Ks, 15-20Ks, etc., or roll-up on disc code to group together Infrastructure Grant, Research Grant: Individual, etc. into one category`Any (Grant)'. Overall, attribute-oriented induction is a technique for generalization of any subset of on-line data in a relational database and extraction of interesting knowledge from the generalized data. The generalized data may also be stored in a database, in the form of a generalized relation or a generalized cube, and be updated incrementally upon database updates 37]. The approach has been implemented in a data mining system, DBMiner, and been experimented in several large relational databases  BIB005 . The approach can also be extended to generalization-based data mining in object-oriented databases 41], spatial databases BIB004  , and other kinds of databases. The approach is designed for generalization-based data mining. It is not suitable for mining speci c patterns at primitive concept levels although it may help guiding such data mining by rst nding some traces at high concept levels and then progressively deepening the data mining process to lower abstraction levels 53]. for each class in the database. Applications of classi cation include medical diagnosis, performance prediction, selective marketing, to name a few. Data classi cation has been studied substantially in statistics, machine learning, neural networks, and expert systems 82] and is an important theme in data mining 30].