Data Mining An Overview From A Database Perspective

866 IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGIJEERING, VOL 8, NO 6, DECEMBER 1996
Ming-Syan Chen, Senior Member, IEEE, Jiawei Han, Senidr Member, IEEE,
and Philip S. Yu, Fellow, lEEE
Abstract-Mining information and knowledge from large databases has been recognized by many researchers as a key research
topic in database systems and machine learning, and by many industrial companies as an important area with an opportunity of
major revenues Researchers in many different fields have shown great interest in data mining Several emerging applications in
information providing services, such as data warehousing and on-line services over the Internet, lalso call for various data mining
techniques to better understand user behavior, to improve the service provided, and to increase the business opportunities In
response to such a demand, this article is to provide a survey, from a database researcher's point of view, on the data mining
techniques developed recently A classification of the available data mining techniques is provided, and a comparative study of such
techniques is presented
Index Terms-Data mining, knowledge discovery, association rules, classification, dala clusterir)g, pattern matching algorithms,
data generalization and characterization, data cubes, multiple-dimensional databases
I
-
ECENTLY, our capabilities of both generating and col- data dredging,data analysis, etc. By knowledge discovery in
lecting data have been increasing rapidly. The wide- databases, interesting khowledge, regularities, or high-level
spread use of bar codes for most commercial products, the information can be extjacted from the relevant sets of data
computerization of many business and government trans- in databases and be indestigated from different angles, and
actions, and the advances in data collection tools have pro- large databases therebj serve as rich and reliable sources
vided us with huge amounts of data. Millions of databases for knowledge generation and verification. Mining infor-
have been used in business management, government ad- mation and knowledge^ from large databases has been rec-
ministration, scientific and engineering data management, ognized by many resteakhers as a key research topic in da-
and many other applications. It is noted that the number of tabase systems and machine learning, and by many indus-
such databases keeps growing rapidly because of the avail- trial companies as an important area with an opportunity of
ability of powerful and affordable database systems. This major revenues. The discovered knowledge can be applied
explosive growth in data and databases has generated an to information managFment, query processing, decision
urgent need for new techniques and tools that can intelli- making, process controp, and many other applications. Re-
gently and automatically transform the processed data into searchers in many different fields, including database sys-
useful information and knowledge. Consequently, data tems, knowledge-base ~systems,artificial intelligence, ma-
mining has become a research area with increasing impor- chine learning, knowlbdge acquisition, statistics, spatial
tance [301, [701, [761. databases, and data vi$mlization, have shown great inter-
Data mining, which is also referred to as knozuledge dis- est in data mining. Furthermore, several emerging applica-
covery in databases, means a process of nontrivial extraction tions in information droviding services, such as on-line
I
of implicit, previously unknown and potentially useful in- services and World 'Wide Web, also call for various data
formation (such as knowledge rules, constraints, regulari- mining techniques to p t t e r understand user behavior, to
ties) from data in databases [70].There are also many other meliorate the service pr'ovided, and to increase the business
terms, appearing in some articles and documents, carrying opportunities. ~
a similar or slightly different meaning, such as knowledge 4

In response to suclh demand, this article is to provide a
mining from databases, knowledge extraction, data archaeology, survey on the data miqkng techniques developed in several
research communities,) with an emphasis on database-
oriented techniques imp those implemented in applicative
M.-S. Chen is with the Electrical Engineering Department,
National Taiwan University, Taipei, Taiwan, Republic of China.
4
data mining systems. classification of the available data
E-mail: [email protected]. mining techniques is also provided, based on the kinds of
e J. Hun is with the School of Computing Science, Simon Fraser University, databases to be mined, the kinds of knowledge to be dis-
British Columbia, V5A 1S6, Canada. E-mail: [email protected]. covered, and the kinds of techniques to be adopted. This
e P.S. Yu is with the IBM Thomas J. Watson Research Center, PO Box 704,
Yorktown, Ny 10598. E-mail: [email protected]. survey is organized ac$ording to one classification scheme:
Manuscript accepted Aug. 28,1996.
the kinds of knowledgei to be mined.
For information on obtaining Yeprints of this article, please send e-mail to:
[email protected],and reference IEEECS Log Number K96075.
1041-4347/96$05 00 0 1 9 9 6 IEEE
Authorized licensed use limited to: MULTIMEDIA UNIVERSITY. Downloaded on September 23,2022 at 17:30:27 UTC from IEEE Xplore. Restrictions apply.
CHEN ETAL.: DATA MINING: AN OVERVIEW FROM A DATABASE PERSPECTIVE 867
1.I Requirements and Challenges of Data Mining 5 ) Interactive mining knowledge at multiple abstraction
In order to conduct effective data mining, one needs to first levels.
examine what kind of features an applied knowledge dis- Since it is difficult to predict what exactly could be
covery system is expected to have and what kind of chal- discovered from a database, a high-level data mining
lenges one may face at the development of data mining query should be treated as a probe which may dis-
close some interesting traces for further exploration.
techniques. Inferactive discovery should be encouraged, which al-
Handling of diffzrent types of data. lows a user to interactively refine a data mining re-
Because there are many kinds of data and databases quest, dynamically change data focusing, progres-
used in different applications, one may expect that a sively deepen a data mining process, and flexibly
knowledge discovery system should be able to per- view the data and data mining results at multiple ab-
form effective data mining on different kinds of data. straction levels and from different angles.
Since most available databases are relational, it is cru- 6 ) Mining information from different sources of data.
cial that a data mining system performs efficient and The widely available local and wide-area computer
effective knowledge discovery on relational data. network, including Internet, connect many sources of
Moreover, many applicable databases contain complex data and form huge distributed, heterogeneous data-
data types, such as structured data and complex data bases. Mining knowledge from different sources of
objects, hypertext and multimedia data, spatial and formatted or unformatted data with diverse data se-
temporal data, transaction data, legacy data, etc. A mantics poses new challenges to data mining. On the
powerful system should be able to perform effective other hand, data mining may help disclose the high-
data mining on such complex types of data as well. level data regularities in heterogeneous databases
However, the diversity of data types and different which can hardly be discovered by simple query sys-
goals of data mining make it unrealistic to expect one tems. Moreover, the huge size of the database, the
data mining system to handle all kinds of data. Spe- wide distribution of data, and the computational
cific data mining systems should be constructed for complexity of some data mining methods motivate
knowledge mining on specific kinds of data, such as the development of parallel and distributed data mining
systems dedicated to knowledge mining in relational algorithms.
databases, transaction databases, spatial databases, 7 ) Protection of privacy and data security.
multimedia databases, etc. When data can be viewed from many different angles
Efficiency and scalability of data mining algorithms. and at different abstraction levels, it threatens the goal
To effectively extract information from a huge of protecting data security and guarding against the
amount of data in databases, the knowledge discov- invasion of privacy. It is important to study when
ery algorithms must be efficient and scalable to large knowledge discovery may lead to an invasion of pri-
databases. That is, the running time of a data mining vacy, and what security measures can be developed
algorithm must be predictable and acceptable in for preventing the disclosure of sensitive information.
large databases. Algorithms with exponential or even Notice that some of these requirements may carry con-
medium-order polynomial complexity will not be of flicting goals. For example, the goal of protection of data
practical use.
security may conflict with the requirement of interactive
Usefulness, certainty, and expressiveness of data mining mining of multiple-level knowledge from different angles.
results. Moreover, this survey addresses only some of the above
The discovered knowledge should accurately portray requirements, with an emphasis on the efficiency and scal-
the contents of the database and be useful for certain
applications. The imperfectness should be expressed ability of data mining algorithms. For example, the han-
by measures of uncertainty, in the form of approxi- dling of different types of data are confined to relational
mate rules or quantitative rules. Noise and excep- and transactional data, and the methods for protection of
tional data should be handled elegantly in data min- privacy and data security are not addressed (some discus-
ing systems. This also motivates a systematic study of sions could be found elsewhere, such as 1221, [631). Never-
measuring the quality of the discovered knowledge, theless, we feel that it is still important to present an overall
including interestingness and reliability, by construc- picture regarding to the requirements of data mining.
tion of statistical, analytical, and simulative models
and tools.
Expression of various kinds of data mining requests and 2 AN OVERVIEW OF DATAMININGTECHNIQUES
results. Since data mining poses many challenging research issues,
Different kinds of knowledge can be discovered from direct applications of methods and techniques developed in
a large amount of data. Also, one may like to examine related studies in machine learning, statistics, and database
discovered knowledge from different views and pres- systems cannot solve these problems. It is necessary to per-
ent them in different forms. This requires us to ex- form dedicated studies to invent new data mining methods
press both the data mining requests and the discov- or develop integrated techniques for efficient and effective
ered knowledge in high-level languages or graphical
user interfaces so that the data mining task can be data mining. In this sense, data mining itself has formed an
specified by nonexperts and the discovered knowl- independent new field.
edge can be understandable and directly usable by us-
ers. This also requires the discovery system to adopt
expressive knowledge representation techniques.
868 IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, VOL. 8, NO. 6, DECEMBER 1996
2.1 Classifying Data Minin .2 Mining Different Kinds of Knowledge from

There have been many advances on researches and devel- Databases
opments of data mining, and many data mining techniques Data mining is an application-dependent issue and differ-
and systems have recently been developed. Different classi- ent applications may require different mining techniques to
fication schemes can be used to categorize data mining cope with. In general, the kinds of knowledge which can be
methods and systems based on the kinds of databases to be discovered in a database are categorized as follows.
studied, the kinds of knowledge to bq discovered, and the Mining association rules in transactional or relational
kinds of techniques to be utilized, as shown below. databases has recently attracted a lot of attention in data-
e What kinds of databases to work on.
base communities [4], [7],[39], [57], [66], [73],[78].The task
A data mining system can be classified according to is to derive a set of strong association rules in the form of
the kinds of databases on which the data mining is "Al A ... A A, *El A ... A B,," where A, (for i E (1, ..., m})
performed. For example, a system is a relational data and Bl (for j E (1, ..., n ) ) are sets of attribute-values, from
miner if it discovers knowledge from relational data, the relevant data sets in a database. For example, one may
or an object-oriented one if it mines knowledge from find, from a large set of transaction data, such an associa-
object-oriented databases. In general, a data miner can tion rule as if a customer buys (one brand of) milk, he/she
be classified according to its mining of knowledge usually buys (another brand of) bread in the same transac-
from the following different kinds of databases: relation. Since mining association rules may require to repeat-
tional databases, transaction databases, object- edly scan through a large transaction database to find dif-
oriented databases, deductive databases, spatial data- ferent association patterns, the amount of processing could
bases, temporal databases, multimedia databases, be huge, and performance improvement is an essential con-
heterogeneous databases, active databases, legacy cern. Efficient algorithms for mining association rules and
databases, and the Internet information-base. some methods for further performance enhancements will
0 What kind of knowledge to be mined. be examined in Section 3.
Several typical kinds of knowledge can be discovered The most popularly used data mining and data analysis
by data miners, including association rules, charac- tools associated with database system products are data
teristic rules, classification rules, discriminant rules, generalization and summarization tools, which carry several
clustering, evolution, and deviation analysis, which alternative names, such as on-line analytical processing
will be discussed in detail in the next subsection. (OLAP), multiple-dimensional databases, data cubes, data
Moreover, data miners can also be categorized ac- abstraction, generalization, summarization, characteriza-
cording to the abstraction level of its discovered tion, etc. Data generalization and summarization presents
knowledge which may be classified into generalized the general characteristics or a summarized high-level view
knowledge, primitive-level knowledge, and multiple- over a set of user-specified data in a database. For example,
level knowledge. A flexible data mining system may the general characteristics of the technical staffs in a com-
discover knowledge at multiple abstraction levels. pany can be described as a set of characteristic rules or a set
0 What kind of techniques to be utilized. of generalized summary tables. Moreover, it is often desir-
Data miners can also be categorized according to the able to present generalized views about the data at multiple
underlying data mining techniques. For example, it abstraction levels. An overview on multilevel data gener-
can be categorized according to the driven method alization, summarization, and characterization is presented
into autonomous knowledge miner, data-driven in Section 4.
miner, query-driven miner, and interactive data Another important application of data mining is the
miner. It can also be categorized according to its un- ability to perform classification in a huge amount of data.
derlying data mining approach into generalization- This is referred to as mining classification rules. Data classi-
based mining, pattern-based mining, mining based fication is to classify a set of data based on their values in
on statistics or mathematical theories, and integrated certain attributes. For example, it is desirable for a car
approaches, etc. dealer to classify its customers according to their preference
for cars so that the sales persons will know whom to ap-
Among many different classification schemes, this sur- proach, and catalogs of new models can be mailed directly
vey follows mainly one classification scheme: the kznds of to those customers with identified features so as to maxi-
knowledge to be mined because such a classification presents mize the business opportunity. Some studies in classifica-
a clear picture on different data mining requirements and tion rules will be reviewed in Section 5.
techniques. Methods for mining different kinds of knowl- In Section 6, we discuss the techniques on data clustering.
edge, including association rules, characterization, classifi- Basically, data clustering is to group a set of data (without a
cation, clustering, etc., are examined in depth. For mining a predefined class attribute), based on the conceptual clus-
particular kind of knowledge, different approaches, such as tering principle: maximizing the intraclass simzlarity and
machine learning approach, statistical approach, and large minimizing the znterclass similarity For example, a set of
database-oriented approach, are compared, with an empha- commodity objects can be first clustered into a set of classes
sis on the database issues, such as efficiency and scalability. and then a set of rules can be derived based on such a clas-
sification. Such clustering may facilitate taxonomy formation,
which means the organization of observations into a hierar-
chy of classes that group similar events together.
CHEN ET AL.: DATA MINING: AN OVERVIEW FROM A DATABASE PERSPECTIVE 869
Temporal or spatial-temporal data constitutes a large D that contain X also contain Y. The rule X 3 Y has sup-
portion of data stored in computers [91, [SO]. ExampIes of port s in the transaction set D if s% of transactions in D
this type of database include: financial database for stock contain X v Y.
price index, medical databases, and multimedia databases, Confidence denotes the strength of implication and sup-
to name a few. Searching for similar patterns in a temporal port indicates the frequencies of the occurring patterns in
or spatial-temporal database is essential in many data the rule. It is often desirable to pay attention to only those
mining operations [l], [3], [56] in order to discover and rules which may have reasonably large support. Such rules
predict the risk, causality, and trend associated with a spe- with high confidence and strong support are referred to as
cific pattern. Typical queries for this type of database in- strong rules in 141, 1681. The task of mining association rules
clude identifying companies with similar growth patterns, is essentially to discover strong association rules in large
products with similar selling patterns, stocks with similar databases. In [4], [7], [66], the problem of mining associa-
price movement, images with similar weather patterns, tion rules is decomposed into the following two steps:
geological features, environmental pollutions, or astro- 1) Discover the large itemsets, i.e., the sets of itemsets
physical patterns. These queries invariably require similar- that have transaction support above a predetermined
ity matches as opposed to exact matches. The approach of minimum support s.
pattern-based similarity search is reviewed in Section 7. 2) Use the large itemsets to generate the association
In a distributed information providing environment, rules for the database.
documents or objects are usually linked together to facili-
tate interactive access. Understanding user access patterns It is noted that the overall performance of mining associa-
in such environments will not only help improving the tion rules is determined by the first step. After the large
system design but also be able to lead to better marketing itemsets are identified, the corresponding association rules
decisions. Capturing user access patterns in such environ- can be derived in a straightforward manner. Efficient
ments is referred to as mining path traversal patterns. Notice, counting of large itemsets is thus the focus of most prior
however, that since users are traveling along the informa- work. Here, algorithms Apriori and DHP, developed in 171,
tion providing services to search for the desired informa- L661, respectively, are described to illustrate the nature of
tion, some objects are visited because of their locations this problem.
rather than their content, showing the very difference be- 3.1 Algorithm Apriori and DHP
tween the traversal pattern problem and others which are 1
mainly based on customer transactions. The capability of Consider an example transaction database given in Fig. 1.
mining path traversal patterns is discussed in Section 8. In each iteration (or each pass), Apriori constructs a candi-
In addition to the issues considered above, there are date set of large itemsets, counts the number of occurrences
certainly many other aspects on data mining that are worth of each candidate itemset, and then determines large item-
studying. It is often necessary to use a data mining query sets based on a predetermined minimum support [7]. In the
language or graphical user interface to specify the interest- first iteration, Apriori simply scans all the transactions to
ing subset of data, the relevant set of attributes, and the count the number of occurrences for each item. The set of
kinds of rules to be discovered. Moreover, it is often neces- candidate 1-itemsets, C1, obtained is shown in Fig. 2. As-
sary to perform interactive data mining to examine, trans- suming that the minimum transaction support required is
form, and manipulate intermediate data mining results, two (i.e., s = 40%), the set of large 1-itemsets, L,, composed
focus at different concept levels, or test different kinds of of candidate 1-itemsets with the minimum support re-
thresholds. Visual representation of data and knowledge quired, can then be determined. To discover the set of large
may facilitate interactive knowledge mining in databases.
2-itemsets, in view of the fact that any subset of a large
itemset must also have minimum support, Apriori uses
3 MININGASSOCIATION
RULES L, * L, to generate a candidate set of itemsets Cz where * is
2
Given a database of sales transactions, it is desirable to dis- an operation for concatenation in this case. C2 consists of
cover the important associations among items such that the
presence of some items in a transaction will imply the pres-
ence of other items in the same transaction. A mathematical
model was proposed in [4] to address the problem of min- 2-itemsets. Next, the four transactions in D are scanned and
ing association rules. Let I = {i,, i2, ..., im} be a set of literals,
the support of each candidate itemset in C2 is counted. The
called items. Let D be a set of transactions, where each
transaction T is a set of items such that T E I. Note that the middle table of the second row in Fig. 2 represents the re-
quantities of items bought in a transaction are not consid- sult from such counting in C2. The set of large 2-itemsets, Lz,
ered, meaning that each item is a binary variable repre- is therefore determined based on the support of each can-
senting if an item was bought. Each transaction is associ- didate 2-itemset in C2.
ated with an identifier, called TID. Let X be a set of items. A
transaction T is said to contain X if and only if X c T. An
association rule is an implication of the form X 3 Y, where
X c I, Y c I, and X n Y = 4. The rule X 3 Y holds in the
transaction set D with confidence c if c% of transactions in 1. This example database is extracted from 171.
2.For the general case, L, * L, = (XuY I X,Y E L,, I X n Y I =k -1).
870 IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, VOL. 8, NO 6, DECEMBER 1996
Database L) transaction size but also pruning the number of transac-

tions in the database. We note that both DHP and Apriori
i are iterative algorithms on the large itemset size in the

sense that the large k-itemsets are derived from the large
( k - 1)-itemsets. These large itemset counting techniques are
in fact applicable to dealing with other data mining prob-
lems [81, [191.
Fig. 1. An example transaction database for data mining. Generalized and Multiple-Level
Association Rules
The set of candidate itemsets, C,, is generated from L, as In many applications, interesting associations among data
follows. From L,, two large 2-itemsets with the same first items often occur at a relatively high concept level. For ex-
item, such as {BC) and (BE},are identified first. Then, Apri- ample, the purchase patterns in a transaction database may
ori tests whether the 2-itemset (CEJ, which consists of their not show any substantial regularities at the primitive data
second items, constitutes a large 2-itemset or not. Since {CE] level, such as at the bar-code level, but may show some
is a large itemset by itself, we know that all the subsets interesting regularities at some high concept level(s), such
of (BCE)are large and then {BCEJ becomes a candidate as milk and bread. Therefore, it is important to study min-
3-itemset. There is no other candidate 3-itemset from ing association rules at a generalized abstraction level [78]
L,. Apriori then scans all the transactions and discov- or at multiple levels [39].
ers the large 3-itemsets L, in Fig. 2. Since there is no candi- Information about multiple abstraction levels may exist
date 4-itemset to be constituted from L,, Apriori ends the in database organizations. For example, a class hierarchy
process of discovering large itemsets. [50] may be implied by a combination of database attrib-
Similar to Apriori, DHP in 1661 also generates candidate utes, such as day, month, year. It may also be given explicitly
k-itemsets from Lk-l. However, DHP employs a hash table, by users or experts, such as Alberta c Prairies.
which is built in the previous pass, to test the eligibility of a Consider the class hierarchy in Fig. 3 for example. It
k-itemset. Instead of including all k-itemsets from Lk, * Lk-l could be difficult to find substantial support of the pur-
into Ck, DHP adds a k-itemset into Ck only if that k-itemset chase patterns at the primitive concept level, such as the bar
is hashed into a hash entry whose value is larger than or codes of 1 gallon Dairyland 2% milk and 1 lb Wonder wheat
equal to the minimum transaction support required. As a bread. However, it could be easy to find 80% of customers
result, the size of candidate set Ck can be reduced signifi- that purchase milk may also purchase bread. Moreover, it
cantly. Such a filtering technique is particularly powerful could be informative to also show that 70% of people buy
in reducing the size of C,. DHP also reduces the database wheat bread if they buy 2% milk. The association relation-
size progressively by not only trimming each individual ship in the latter statement is expressed at a lower concept
level but often carries more specific and concrete informa-
Scan
-
.D
Scan
D
*
--f
c3
Scan
Itemset
-D
Itemset Sup.)
Fig. 2. Generation of candidate itemsets and large itemsets.
~
Dairyland Foremost Old Mills Wonder

Fig. 3. An example of concept hierarchiesfor mining multiple-levelassociation rules.
tion than that in the former. Therefore, it is important to To filter out such kind of misleading associations, one
mine association rules at a generalized abstraction level or may define that an association rule "A =+ B is interesting if
at multiple concept levels. its confidence exceeds a certain measure, or formally,
In 1391, the notion of mining multiple-level association P(A n B )
rules are introduced: Low-level associations will be exam-
P(A)
ined only when their high-level parents are large at their
corresponding levels, and different levels may adopt differ- is greater than d, a suitable constant. However, the simple
ent minimum support thresholds. Four algorithms are de- argument we used in the example above suggests that the
veloped for efficient mining of association rules based on right heuristic to measure association should be
different ways of sharing of multiple-level mining processes P(A n B )
and reduction of the encoded transaction tables. In [78], - P(B) > d ,
P(A)
methods for mining associations at generalized abstraction
level are studied by extension of the Apriori algorithm. or alternatively, P(A n B ) - P(A) * P ( B ) > k, where k is a
suitable constant. The expressions above essentially repre-
Besides mining multiple-level and generalized associa-
sent tests of statistical independence. Clearly, the factor of
tion rules, the mining of quantitative association rules [79]
statistical dependence among various user behaviors ana-
and meta-rule guided mining of association rules in rela-
lyzed has to be taken into consideration for the determina-
tional databases [33], [75] are also studied recently, with
efficient algorithms developed. tion of the usefulness of association rules.
There have been some interesting studies on the inter-
3.3 interestingness of Discovered Association Rules estingness or usefulness of discovered rules, such as 1681,
Notice that not all the discovered strong association rules [78], [77]. The notion of interestingness on discovered gen-
(i.e., passing the minimum support and minimum confi- eralized association rules is introduced in [78]. The subjec-
dence thresholds) are interesting enough to present. tive measure of interestingness in knowledge discovery is
For example, consider the following case of mining the studied in [77].
survey results in a school of 5,000 students. A retailer of 3.4 Improving the Efficiency of Mining Association
breakfast cereal surveys the students on the activities they Rules
engage in the morning. The data show that 60% of students
Since the amount of the processed data in mining associa-
(i.e., 3,000 students) play basketball, 75% of students
tion rules tends to be huge, it is important to devise efficient
(i.e., 3,750 students) eat cereal, and 40% of them (i.e., 2,000
algorithms to conduct mining on such data. In this section,
students) both play basketball and eat cereal. Suppose that
some techniques to improve the efficiency of mining asso-
a data mining program for discovering association rules is
ciation rules are presented.
run on the data with the following settings: the minimal
student support is 2,000 and the minimal confidence is 60%. 3.4.1 Database Scan Reduction
The following association rule will be produced: "(play
In both Apriori and DHP, C3 is generated from L2 * L2. In
basketball) 3 (eat cereal)," since this rule contains the
minimal student support and the corresponding confidence fact, a C2 can be used to generate the candidate 3-itemsets.
2000 Clearly, a C; generated from C2 * C2, instead of from
= 0.66
L2 * L,, will have a size greater than I C3 I where C3 is gen-
is larger than the minimal confidence required. However, erated from L2 * L2. However, if IC;[ is not much larger than
the above association rule is misleading since the overall
I C, I , and both C, and C; can be stored in main memory,
percentage of students eating cereal is 75%, even larger
than 66%.That is, playing basketball and eating cereals are we can find L, and L3 together when the next scan of the
in fact negatively associated; i.e., being involved in one de- database is performed, thereby saving one round of data-
creases the likelihood of being involved in the other. With- base scan. It can be seen that using this concept, one can
out fully understanding this aspect, one could make wrong determine all Lks by as few as two scans of the database
business decisions from the rules derived.
(i.e., one initial scan to determine L, and a final scan to de-
termine all other large itemsets), assuming that Ci for k 2 3 ing global decisions can be prohibitively large, thus signifi-
is generated from CL-l and all CL for IC > 2 can be kept in the cantly compromising the benefit achievable from paralleli-
memory. This technique is called scan-reduction. In 1191,the zation. For example, in a shared nothing type parallel envi-
technique of scan-reduction was utilized and shown to re- ronment like SP2 [44], each node can directly collect infor-
sult in prominent performance improvement. Clearly, such mation only from its local database partition, and the proc-
a technique is applicable to both Apriori and DHP. ess to reach a global decision from partial knowledge col-
lected at individual nodes could itself be complicated and
3.4.2 Sampling: Mining with AGustable Accuracy communication intensive. An algorithm for parallel data
Several applications require mining the transaction data to mining, called PDM, was reported in [67]. Under PDM,
capture the customer behavior in a very frequent basis. In with the entire transaction database being partitioned
those applications, the efficiency of data mining could be a across all nodes, each node will employ a hashing method
more important factor than the requirement for a complete to identify candidate k-itemsets (i.e., itemsets consisting of k
accuracy of the results. In addition, in several data mining items) from its local database. To reduce the communica-
applications the problem domain could only be vaguely tion cost incurred, a clue-and-poll technique was devised in
defined. Missing some marginal cases with confidence and E671 to resolve the uncertainty due to the partial knowledge
support levels at the borderline may have little effect on the collected at each node by judiciously selecting a small frac-
quality of the solution to the original problem. Allowing tion of the itemsets for the information exchange among
imprecise results can in fact significantly improve the effi- nodes.
ciency of the mining algorithms. As the database size in-
creases nowadays, sampling appears to be an attractive 4 MULTILEVEL
DATAGENERALIZATION,
approach to data mining. A technique of relaxing the sup-
~ ~ M M A R I Z A T I AND
O~, HARACTERIZATION
port factor based on the sampling size is devised in [65] to
achieve the desired level of accuracy. As shown in [651, the Data and objects in databases often contain detailed infor-
relaxation factor, as well as the sample size, can be properly mation at primitive concept levels. For example, the ”item”
adjusted so as to improve the result accuracy while mini- relation in a ”sales” database may contain attributes about
mizing the corresponding execution time, thereby allowing the primitive level item information such as item number,
us to effectively achieve a design trade-off between accu- item name, date made, price, etc. It is often desirable to
racy and efficiency with two control parameters. As a summarize a large set of data and present it at a high con-
means to improve efficiency, sampling has been used in cept level. For example, one may like to summarize a large
[781 for determining the cut-off level in the class hierarchy set of the items related to some sales to give a general de-
of items to collect occurrence counts in mining generalized scription. This requires an important functionality in data
association rules. Sampling was discussed in [57]as a justi- mining: data generalzzatzon.
fication for devising algorithms and conducting experi- Data generalization is a process which abstracts a large
ments with data sets of small sizes. set of relevant data in a database from a low concept level
to relatively high ones. The methods for efficient and flexi-
3.4.3 Incremental Updating of Discovered Association ble generalization of large data sets can be categorized into
Rules two approaches:
Since it is costly to find the association rules in large data-
1) data cube approach [351,[431, [831,[841, and
bases, incremental updating techniques should be devel-
2) attribute-oriented induction approach [371,[401.
oped for maintenance of the discovered association rules to
avoid redoing data mining on the whole updated database.
4.1 Data Cube Approach
A database may allow frequent or occasional updates
and such updates may not only invalidate some existing The data cube approach has a few alternative names or a
strong association rules but also turn some weak rules into few variants, such as, ”multidimensional databases,”
strong ones. Thus it is nontrivial to maintain such discov- ”materialized views,” and ”OLAP (On-Line Analytical
ered rules in large databases. An incremental updating Processing).” The general idea of the approach is to mate-
technique is developed in 1211 for efficient maintenance of rialize certain expensive computations that are frequently
discovered association rules in transaction databases with inquired, especially those involving aggregate functions,
data insertion. The major idea is to reuse the information of such as count, sum, average, max, etc., and to store such
the old large itemsets and to integrate the support informa- materialized views in a multidimensional database (called
tion of the new large itemsets in order to substantially re- a ”data cube”) for decision support, knowledge discovery,
duce the pool of candidate sets to be re-examined. and many other applications. Aggregate functions can be
precomputed according to the grouping by different sets
3.4.4 Parallel Data Mining or subsets of attributes. Values in each attribute may also
It is noted that data mining in general requires progressive be grouped into a hierarchy or a lattice structure. For ex-
knowledge collection and revision based on a huge trans- ample, ”date” can be grouped into “day,” ”month,”
action database. How to achieve efficient parallel data ”quarter,” ”year,” or “week,” which form a lattice struc-
mining is a very challenging issue, since, with the transac- ture. Generalization and specialization can be performed
tion database being partitioned across all nodes, the on a multiple dimensional data cube by ”roll-up” or
amount of internode data transmission required for reach- ”drill-down” operations, where a roll-up operation re-
duces the number of dimensions in a data cube or gener- 4.2 Attribute-Oriented Induction Approach
alizes attribute values to high-level concepts, whereas a The data warehousing approach which uses materialized
drill-down operation does the reverse. Since many aggre- views are "off-line" database computation which may not
gate functions may often need to be computed repeatedly correspond to the most up-to-date database contents. An
in data analysis, the storage of precomputed results in a alternative, on-line, generalization-based data analysis
multiple dimensional data cube may ensure fast response technique, is called attribute-oriented induction approach [371,
time and flexible views of data from different angles and [40]. The approach takes a data mining query expressed in
at different abstraction levels. an SQL-like data mining query language and collects the set
For example, a relation with the schema "sales(part, of relevant data in a database. Data generalization is then
supplier, customer, sale-price)" can be materialized into a setperformed on the set of relevant data by applying a set of
of eight views as shown in Fig. 4 (extracted from [43]), data generalization techniques [371, 1401, 1601, including at-
where psc indicates a view consisting of aggregate function tribute-removal, concept-tree climbing, attribute-threshold
values (such as total-sales) computed by grouping three control, propagation of counts and other aggregate function
attributes part, supplier, and customer, p indicates a view values, etc. The generalized data is expressed in the form of
consisting of the corresponding aggregate function values a generalized relation on which many other operations or
computed by grouping part alone, etc. transformations can be performed to transform generalized
data into different kinds of knowledge or map them into
different forms [40]. For example, drill-down or roll-up op-
erations can be performed to view data at multiple abstrac-
tion levels [361; 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 differ-
ent classes of data at multiple abstraction levels can be ex-
tracted by grouping the set of comparison data into con-
trasting classes before data generalization; classification
none
rules which classify data at different abstraction levels ac-
Fig. 4. Eight views of data cubes for sales information. cording to one or a set of classification attributes can be
derived by applying a decision tree classifier [72] on the
generalized data 1421; and association rules which associate
There are commonly three choices in the implementation
a set of generalized attribute properties in a logic implica-
of data cubes:
tion rule by integration of attribute-oriented induction and
1) physically materialize the whole data cube, the methods for mining association rules [71, [391,[661, [781.
2) materialize nothing, and Moreover, statistical pattern discovery can also be per-
3) materialize only part of the data cube. formed using attribute-oriented induction [24].
The problem of materialization of a selected subset of a The core of the attribute-oriented induction technique is
very large number of views can be modeled as a lattice of on-line data generalization which is performed by fir$ ex-
views. A recent study [43] has shown that a greedy algo- amining the data distribution for each attribute in the set of
rithm, which, given what views have already been materi- relevant data, calculating the corresponding abstraction
alized, selects for materializing those views that offer the level that data in each attribute should be generalized to,
most improvement in average response time, is able to lead and then replacing each data tuple with its corresponding
to results within 63% of those generated by the optimal al- generalized tuple. The generalization process scans the data
gorithm in all cases. As a matter of fact, in many realistic set only once and collects the aggregate values in the corre-
cases, the difference between the greedy and optimal solu- sponding generalized relation or data cube. It is a highly
tions is essentially negligible. efficient technique since the worst-case time complexity of
Data cube approach is an interesting technique with the process is O(n), if a cube structure is used (desirable
many applications [83]. Techniques for indexing multiple when the data cube is dense), or O(n log(p)), if a general-
dimensional data cubes and for incremental updating of ized relation is used (desirable when the corresponding
data cubes at database updates have also been studied [83], cube is rather sparse), where n is the number of tuples in
[86]. Notice that data cubes could be quite sparse in many the set of relevant data and p is the size (i.e., number of tu-
cases because not every cell in each dimension may have ples) of the generalized relation [401.
corresponding data in the database. Techniques should be To support multiple-level data mining, especially the
developed to handle sparse cubes efficiently. Also, if a drill-down operations, the attribute-oriented induction
query contains constants at even lower levels than those technique should generalize the set of relevant data to a
provided in a data cube (e.g., a query refers time in the unit minimal abstraction level and maintain such a minimally
of "hour" whereas the lowest concept level on time in the generalized relation (if expressed by a relational structure) or
cube is "day"), it is not clear how to make the best use of a minimally generalized cube (if expressed by a cube struc-
the precomputed results stored in the data cube. ture) to facilitate the traversals among multiple abstraction
spaces. The roll-up of a generalized relation may simply
874 IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, VOL 8, NO 6, DECEMBER 1996
start with this relation; however, the drill-down of the rela- cording to the attributes: disc-code (discipline code) and
tion may start with the minimal generalized relation and grant-catego y, the following data mining query can be speci-
perform data generalization to the corresponding abstrac- fied in a data mining query language DMQL I421 as follows:
tion levels [361.
use NSERC95
The essential background knowledge applied in attrib- mine discriminant rule for 'BC-Grants'
ute-oriented induction is concept hierarchy (or lattice) asso- where 0.Province = 'British Columbia'
ciated with each attribute [37]. Most concept hierarchies are in contrast to 'Alberta-Grants'
stored implicitly in databases. For example, a set of attrib- where 0,Province = 'Alberta'
utes in address (number, street, city, province, c o u n t y ) in a from Award A, Organization 0, Grant-type G
database schema represents the concept hierarchies of the where A.grant-code = G.grant-code and
attribute address. A set of attributes in a data relation, A.OrgID = 0.OrgID and A.disc-code =
'Computer'
though seemingly no strong semantic linkages exist, may related to disc-code, grant-category,
also form concept hierarchies (or lattices) among their su- count(*)%
persets or subsets. For example, in the schema item(id, name,
category, producer, date-made, cost, price), "{category, producer, The execution of this data mining query generates
date-made) c {category, date-made}" indicates the former Table 1, which presents the differences between the two
forms a lower level concept than the latter. Moreover, rules provinces in terms of disc-code, grant-category and the
and view definitions can also be used as the definitions of number of the research grants. The column support% rep-
concept hierarchies [24]. Conceptual hierarchies for nu- resents the number of research grants in this category vs.
merical or ordered attributes can be generated automati- the total number of grants in its own province; where the
cally based on the analysis of data distributions in the set of comparison% represents the number of research grants in
relevant data [38].Moreover, a given hierarchy may not be this category in one province vs. that of the other. For ex-
best suited for a particular data mining task. Therefore, ample, the first (composite) row indicates that for Com-
such hierarchies should be adjusted dynamically in many puter Science Infvastructure Grants in the range of 40Ks to
cases based on the analysis of data distributions of the cor- 60Ks, British Columbia takes 2.00% of its total number of
responding set of data 1381. Computer Science Grants, whereas Alberta takes 1.72%;
An an example, one may use data mining facilities to however, in comparison between these two provinces,
study the general characteristics of the Natural Science and British Columbia takes 66.67% of the share (in number)
Engineering Research Council of Canada (NSERC) research whereas Alberta takes only 33.33%. Other rows have
grant database. To compare the research grants between similar interpretations.
'British Columbia' and 'Alberta' (two neighbor provinces in Notice with interactive data mining facilities, such as
Western Canada) in the discipline of 'Computev (Science)' ac- those provided in DBMiner, a user may perform roll-up or
class discipline grant -category amount -category support% comparison%

B.C. 2.00 66.67
Computer Infrastructure Grant 40Ks-6OKs
Albert a 1.72 33.33
B.C. 2.00 66.67
Computer Other 20Ks-40Ks
Albert a 1.72 33.33
B.C. 2.00 50.00
Computer Other 60Ks-
Alberta 3.45 50.00
B.C. 38.00 63.33
Computer Research Grant: Individual 0-2OKs
Albert a 37.93 36.67
B.C. 28.00 56.00
Computer Research Grant: Individual 20Ks-40Ks
Alberta 37.93 44.00
B.C. 6.00 75.00
Computer Research Grant: Individual 40Ks-60Ks
Albert a 3.45 25.00
B.C. 3.00 100.00
Computer Research Grant: Individual 60Ks-
Albert a 0.00 0.00
B.C. 19.00 76.00
Computer Scholarship O-2OKs
Albert a , 10.34 24.00
~
drill-down operations conveniently. For example, one may with a branch corresponding to each possible value of
drill down on 'grant-category' to examine even finer grant that attribute.
categories such as 0-lOKs, 10-15Ks, 15-20Ks, etc., or roll-up A typical decision tree learning system, ID-3 [71], adopts
on disc-code to group together Infrastructure Grant, Research a top-down irrevocable strategy that searches only part of
Grant: Individual, etc., into one category 'Any (Grant)'. the search space. It guarantees that a simple, but not neces-
Overall, attribute-oriented induction is a technique for sarily the simplest, tree is found. ID-3 uses an information-
generalization of any subset of on-line data in a relational theoretic approach aimed at minimizing the expected number
database and extraction of interesting knowledge from the of tests to classify an object. The attribute selection part of
generalized data. The generalized data may also be stored ID-3 is based on the plausible assumption that the com-
in a database, in the form of a generalized relation or a plexity of the decision tree is strongly related to the amount
generalized cube, and be updated incrementally upon of information conveyed by this message. An information-
database updates [37]. The approach has been imple- based heuristic selects the attribute providing the highest
mented in a data mining system, DBMiner, and been ex- information gain, i.e., the attribute which minimizes the
perimented in several large relational databases [401, [421. information needed in the resulting subtrees to classify the
The approach can also be extended to generalization- elements. An extension to ID-3, C4.5 1721, extends the do-
based data mining in object-oriented databases [41], spa- main of classification from categorical attributes to numeri-
tial databases [53], 1561, and other kinds of databases. The cal ones.
approach is designed for generalization-based data min- The ID-3 system [71] uses information gain as the
ing. It is not suitable for mining specific patterns at primi- evaluation functions for classification, with the following
tive concept levels although it may help guiding such data evaluation function,
mining by first finding some traces at high concept levels
and then progressively deepening the data mining proc-
ess to lower abstraction levels [53]. where p , is the probability that an object is in class i. There
are many other evaluation functions, such as Gini index, chi-
5 DATACLASSIFICATION square test, and so forth [14], [52], [68], 821. For example, for
Gini index [14], [59], if a data set T contains examples from
Data classification is the process which finds the common n classes, gini(T) is defined as,
properties among a set of objects in a database and classi-
fies them into different classes, according to a classification gini(T) = 1 - &,2.
model. To construct such a classification model, a sample where p , is the relative frequency of class i in T. Moreover,
database E is treated as the training set, in which each tu- there are also approaches for tranforming decision trees
ple consists of the same set of multiple attributes (or fea- into rules [72] and transforming rules and trees into com-
tures) as the tuples in a large database W, and addition- prehensive knowledge structures [341.
ally, each tuple has a known class identity (label) associ- There have been many other approaches on data classifi-
ated with it. The objective of the classification is to first cation, including statistical approaches [18], [261, 681, rough
analyze the training data and develop an accurate de- sets approach [87], etc. Linear regression and linear dis-
scription or a model for each class using the features criminant analysis techniques are classical statistical models
available in the data. Such class descriptions are then used [26]. Methods have also been studied for scaling machine
to classify future test data in the database W or to develop learning algorithms by combining base classifiers from
a better description (called classification rules) for each partitioned data sets 1181. There have also been some stud-
class in the database. Applications of classification include ies of classification techniques in the context of large data-
medical diagnosis, performance prediction, selective mar- bases [2], [lo]. An interval classifier has been proposed in
keting, to name a few. [2] to reduce the cost of decision tree generation. The neural
Data classification has been studied substantially in sta- network approach for classification and rule extraction in
tistics, machine learning, neural networks, and expert sys- databases has also been studied recently 1551.
tems [82], and is an important theme in data mining 1301.
5.2 Methods for Performance Improvement
5.1 Classification Based on Decision Trees
Most of the techniques developed in machine learning and
A decision-tree-based classification method, such as [71I, statistics may encounter the problem of scaling-up. They
[72], has been influential in machine learning studies. It is a may perform reasonably well in relatively small databases
supervised learning method that constructs decision trees but may suffer the problem of either poor performance or
from a set of examples. The quality (function) of a tree de- the reduction of classification accuracy when the training
pends on both the classification accuracy and the size of the data set grows very large, even though a database system
tree. The method first chooses a subset of the training ex- has been taken as a component in some of the above meth-
amples (a window) to form a decision tree. If the tree does ods. For example, the interval classifier proposed in [2] uses
not give the correct answer for all the objects, a selection of database indices to improve only the efficiency of data re-
the exceptions is added to the window and the process trieval but not the efficiency of classification since the classi-
continues until the correct decision set is found. The fication algorithm itself is essentially an ID-3 algorithm.
eventual outcome is a tree in which each leaf carries a A direct integration of attribute-oriented induction with
class name, and each interior node specifies an attribute the ID-3 algorithm may help discovery of classification
rules at high abstraction levels [40]. It, though efficient, may measurement, in a large, multidimensional data set. Given
reduce the classification accuracy since the classification a large set of multidimensional data points, the data space
interval may have been generalized to a rather high level. A is usually not uniformly occupied by the data points. Data
multiple-level classification technique and a level adjust- clustering identifies the sparse and the crowded places,
ment and merge technique have been developed in and hence discovers the overall distribution patterns of
DBMiner to improve the classification accuracy in large the data set.
databases by the integration of attribute-oriented induction Data clustering has been studied in statistics [18], [47],
and classification methods 1421. machine learning [31], 1321, spatial database [ll], and data
Recently, Mehta et al. 1591 has developed a fast data clas- mining [18], [27], 1621, [85] areas with different emphases.
sifier, called supervised learning in QUEST (SLIQ), for As a branch of statistics, clustering analysis has been
mining classification rules in large databases. SLIQ is a de- studied extensively for many years, mainly focused on
cision tree classifier that can handle both numeric and cate- distance-based clustering analysis. Systems based on statis-
gorical attributes. It uses a novel presorting technique in the tical classification methods, such as AutoClass 1181 which
tree growing phase. This sorting procedure is integrated uses a Bayesian classification method, have been used in
with a breadth-first tree growing strategy to enable classifi- clustering in real world databases with reported success.
cation of disk-resident datasets. SLIQ also uses a new tree- The distance-based approaches assume that all the data
pruning algorithm that is inexpensive, and results in com- points are given in advance and can be scanned frequently.
pact and accurate trees. The combination of these tech- They are global or semiglobal methods at the granularity of
niques enables it to scale for large data sets and classify data points. That is, for each clustering decision, they in-
data sets irrespective of the number of classes, attributes, spect all data points or all currently existing clusters equally
and examples. An approach, called meta-learning, was no matter how close or far away they are, and they use
proposed in 1171. In [17], methods to learn how to combine global measurements, which require scanning all data
several base classifiers, which are learned from subsets of points or all currently existing clusters. Hence, they do not
data, were developed. Efficient scaling-up to larger learning have linear scalability with stable clustering quality.
problems can hence be achieved. In machine learning, clustering analysis often refers to un-
Notice that in most prior work on decision tree generation, supervised learning, since which classes an object belongs to
a single attribute is considered at each level for the branching are not prespecified, or conceptual clustering, because the dis-
decision. However, in some classification tasks, the class tance measurement may not be based on geometric distance,
identity in some cases is not so dependent on the value of a but be based on that a group of objects represents a certain
single attribute, but instead, depends upon the combined conceptual class. One needs to define a measure of similarity
values of a set of attributes. This is particularly true in the between the objects and then apply it to determine classes.
presence of those attributes that have strong inference among Classes are defined as collections of objects whose intraclass
themselves. In view of this, a two-phase method for multiat- similarity is high and interclass similarity is low.
tribute extraction was devised in [20] to improve the effi- The method of clustering analysis in conceptual cluster-
ciency of deriving classification rules in a large training data- ing is mainly based on probability analysis. Such ap-
set. A feature that is useful in inferring the group identity of a proaches, represented by [31], [32],make the assumption
data tuple is said to have a good inference power to that group that probability distributions on separate attributes are sta-
identity. Given a large training set of data tuples, the first tistically independent of each other. This assumption is,
phase, referred to as feature extraction phase, is applied to a however, not always true since correlation between attrib-
subset of the training database with the purpose of identify- utes often exists. Moreover, the probability distribution
ing useful features which have good inference power to representation of clusters makes it very expensive to update
group identities. In the second phase, referred to as feature and store the clusters. This is especially so when the attrib-
combznatzon phase, those features extracted from the first utes have a large number of values since their time and
phase are combinedly evaluated and multiattribute predi- space complexities depend not only on the number of at-
cates with strong inference power are identified. It is noted tributes, but also on the number of values for each attribute.
that the inference power can be improved significantly by Furthermore, the probability-based tree (such as [31]) that is
utilizing multiple attributes in predicates, showing the ad- built to identify clusters is not height-balanced for skewed
vantage of using multiattribute predicates. input data, which may cause the time and space complexity
to degrade dramatically.
Clustering analysis in large databases has been studied
LUSTER~NGANALYSIS
recently in the database community.
The process of grouping physical or abstract objects into
classes of similar objects is called Clustering or unsupervised plications Based on
classification. Clustering analysis helps construct meaningful
partitioning of a large set of objects based on a ”divide and Ng and Han presented a clustering algorithm, CLARANS
conquer” methodology which decomposes a large scale (Clustering Large Applications Based upon Randomized
system into smaller components to simplify design and Search) 1621, based on randomized search and originated
implementation. from two clustering algorithms used in statistics, PAM
As a data mining task, data clustering identifies clusters, (Partitioning Around Medoids) and CLARA (Clustering
or densely populated regions, according to some distance Large Applications) [48].
The CLARANS algorithm I621 integrates PAM and representative objects. The drawback is that some objects,
CLARA by searching only the subset of the data set but not which may be better medoids, are not considered, but the
confining itself to any sample at any given time. While sample is drawn in the way which still enables good quality
CLARA has a fixed sample at every stage of the search, of clustering.
CLARANS draws a sample with some randomness in each The other technique to reduce computation is to restrict
step of the search. The clustering process can be presented the access to certain objects that do not actually contribute
as searching a graph where every node is a potential solu- to the computation, with two different focusing techniques:
tion, i.e., a set of k medoids. The clustering obtained after focus on relevant clusters, and focus on a cluster. Using the
replacing a single medoid is called the neighbor of the cur- R*-tree structure, computation can be performed only on
rent clustering. If a better neighbor is found, CLARANS pairs of objects that can improve the quality of clustering
moves to the neighbor's node and the process is started instead of checking all pairs of objects as in the CLARANS
again, otherwise the current clustering produces a local algorithm.
optimum. If the local optimum is found, CLARANS starts Ester et al. applied the focusing on representative objects
with new randomly selected nodes in search for a new local to a large protein database to find a segmentation of protein
optimum. CLARANS has been experimentally shown to be surfaces so as to facilitate the so-called docking queries. They
more effective than both PAM and CLARA. The computa- reported that when the focusing technique was used the
tional complexity of every iteration in CLARANS is basi- effectiveness (the average distance of the resulting cluster-
cally linearly proportional to the number of objects [27], ing) decreased just from 1.5% to 3.2% whereas the effi-
[62]. It should be mentioned that CLARANS can be used to ciency (CPU time) increased by a factor of 50.
find the most natural number of clusters knat A heuristic is
adopted in 1621 to determine knat,which uses silhouette coeffi- 6.3 Clustering Features and CF Trees
3 R-trees are not always available and their construction may
cients, introduced by Kaufman and Rousseeuw [48].
CLARANS also enables the detection of outliers, e.g., points be time consuming. Zhang et al. 1851 presented another al-
that do not belong to any cluster. gorithm, BIRCH (Balanced Iterative Reducing and Clus-
Based upon CLARANS, two spatial data mining algo- tering), for clustering large sets of points. The method they
rithms were developed in a fashion similar to the attribute- presented is an incremental one with the possibility of ad-
oriented induction algorithms developed for spatial data justment of memory requirements to the size of memory
mining [56], [37]: spatial dominant approach, SD(CLARANS) that is available.
and nonspatial dominant approach, NSD(CLARANS). Both Two concepts, Clustering Feature and CF tree, are introduced.
algorithms assume that the user specifies the type of the A Clustering Feature CF is the triplet summarizing infor-
rule to be mined and relevant data through a learning mation about subclusters of points. Given N d-dimensional
request in a similar way as DBMiner 1401. Experiments points in subcluster: { X I ] CF
, is defined as
show that the method can be used to cluster reasonably
large data sets, such as houses in the Vancouver area, CF = ( N , L i , SS)
and the CLARAN algorithm outperforms PAM and --f
where N is the number of points in the subcluster, LS is the

CLARA.
linear sum on N points, i.e.,
6.2 Focusing Methods
Ester et al. [27] pointed out some drawbacks of the CLARANS
clustering algorithm [62] and proposed new techniques to ,=l
improve its performance. and SS is the square sum of data points,

First, CLARANS assumes that the objects to be clustered
are all stored in main memory. This assumption may not be $2;.
valid for large databases and disk-based methods could be re- 1=1
quired. This drawback is alleviated by integrating CLARANS The Clustering Features are sufficient for computing clusters
with efficient spatial access methods, like R*-tree 1111. and they constitute an efficient storage information method
R'-tree supports the focusing techniques that Ester et al. as they summarize information about the subclusters of
proposed to reduce the cost of implementing CLARANS. points instead of storing all points.
Ester et al. showed that the most computationally expen- A CF tree is a balanced tree with two parameters: branch-
sive step of CLARANS is calculating the total distances ing factor B and threshold T. The branching factor specifies
between the two clusters. Thus, they proposed two ap- the maximum number of children. The threshold parameter
proaches to reduce the cost of this step. specifies the maximum diameter of subclusters stored at the
The first one is to reduce the number of objects consid- leaf nodes. By changing the threshold value we can change
ered. A centroid 9uery returns the most central object of a the size of the tree. The nonleaf nodes are storing sums of
leaf node of the R"-tree where neighboring points are their children's CFs, and thus, they summarize the infor-
stored. Only these objects are used to compute the medoids mation about their children. The CF tree is build dynami-
of the clusters. Thus, the number of objects taken for con- cally as data points are inserted. Thus, the method is an
sideration is reduced. This technique is called focusing on incremental one. A point is inserted to the closest leaf entry
(subcluster). If the diameter of the subcluster stored in the
3. It is a property of an object that specifies how much the object truly leaf node after insertion is larger than the threshold value,
belongs to the cluster.
then, the leaf node and possibly other nodes are split. After quence in the database. Let n be the length of {x,},N be the
the insertion of the new point, the information about it is length of {y,},and assume n 2 N .
passed towards the root of the tree. One can change the size Consider only subsequences of length n of {y,}. The Jth
of the CF tree by changing the threshold. If the size of the
subsequence of length n of {y,) is denoted as {z(}, where J is
memory that is needed for storing the CF tree is larger than
the size of the main memory, then a larger value of thresh- the offset. A metric for measuring the similarity between
old is specified and the CF tree is rebuilt. The rebuild proc- {x,)and {y,} can be defined as
ess is performed by building a new tree from the leaf nodes n
of the old tree. Thus, the process of rebuilding the tree is (7.1)
done without the necessity of reading all the points. There-
fore, for building the tree, data has to be read just once. where Ki be a scaling factor. Assume that the subse-
Some heuristics and methods are also introduced to deal quences are generated dynamically from the original se-
with outliers and improve the quality of CF trees by addi- quence at query time. For each sequence of length N , a total
tional scans of the data. of N - y1 subsequences of length n need to be considered at
Zhang et al. claimed that any clustering algorithm, in- query time.
cluding CLARANS can be used with CF trees. The CPU The Euclidean distance is only meaningful for measuring
and I/O costs of the BIRCH algorithm are of order O(N). A the distance between two vectors with the same dimension.
good number of experiments reported in [85]show linear Another possible similarity measure is the correlation be-
scalability of the algorithm with respect to the number of tween two sequences as considered in [54].This measure not
points, insensibility to the input order, and good quality of only gives the relative similarity as a function of location but
clustering of the data. also eliminates the need to generate all the subsequences
of given length n of each time series in the database.
PATTE The linear correlation between a target sequence {xl}and
a sequence in the database {y,} is defined as
Next, we discuss data mining techniques based on pattern-
based similarity search. When searching for similar patterns
in a temporal or spatial-temporal database, two types of c1 = II (7.2)
queries are usually encountered in various data mining
operations:
for i = 1, . . ., N + n - 1. Such an operation can be expensive,
e Object-relative similarity query (i.e., range query or
similarity query) in which a search is performed on a especially for long target sequences {x,).Yet, when this is
collection of objects to find the ones that are within a the case, the convolution theorem for Fourier transforms
user-defined distance from the queried object. offers an appealing solution to the problem. First, zeros
e All-pair similarity query (i.e., spatial join) where the can be added at the end of the sequences {x,}and {y,},thus
objective is to find all the pairs of elements that are generating new sequences {xl’}and {y:} both with length
within a user-specified distance from each other. 1 = N + n - 1. Then, the Discrete Fourier Transforms (DFT),
Significant progress has recently been made in sequence {X,) and {Y,}of {xl’}and {yL’),can be calculated. Finally, the
matching for temporal databases [11,[51, [281,[291,1541, [571 correlation coefficient can be obtained by multiplying
and for speech recognition techniques such as dynamic pointwise {XI} and {U,} and inverting the result, as
time warping [81].Two types of similarity queries for tem-
poral data have emerged thus far: whole matching [l] in P{x;q
which the target sequence and the sequences in the data-
base have the same length; subsequence matching [29] in
which the target sequence could be shorter than the se-
cl = JmJp (7.3)
quences in the database and the match can occur at any where {X;}denotes the complex conjugate of X I . The de-
arbitrary point. Various approaches proposed in the litera- nominators of (7.2) and (7.3) are equal in virtue of Parse-
ture differ in the following aspects. The first one is the
val’s Theorem 1. If both {x,}and (y,} are properly normal-
similarity measure chosen. The second is whether the com-
parison is performed in time domain vs. transformed do- ized, the value of correlation coefficient c, is a similarity
main. The third is the generality of the approach whether measure of two sequences and ranges from -1 to 1, where 1
subsequence of arbitrary length, scaling and translation are indicates a perfect match. With noisy signals, the correla-
allowed in the matching. Finally, different techniques have tion value is always smaller than one and the peaks of the
been explored to reduce the number of comparisons or sequence {c,} give the locations of possible matches.
search space during mining.
7.2 Alternative Approaches
The straightforward approach for whole matching is to
Different similarity measures have been considered, mainly consider all of the data points of a sequence simultane-
the Euclidean distance [ll, 1291, [281 and the correlation 1541. ously. In [461, the concept of mapping an object to a point in
The Euclidean distance between two sequences is defined the feature space and then applying multidimensional in-
as follows. Let {x,}be the target sequence and {yl}be a se-
dexing method to perform similarity search is explored. A chical scan instead of using a tree structure for indexing.
fast whole matching method generalizing this idea to se- Different transformations were considered in [541.
quence matching is proposed in [l],where the similarity In [51, another approach is introduced to determine all
between a stored sequence in the database and a target se- similar sequences in a set of sequences. It is also applicable
quence is measured by the Euclidean distance between the to find all subsequences similar to a target sequence. The
features extracted from these two sequences in the Fourier similarity measure considered is the Euclidean distance
domain. between the sequences and the matching is performed in
Extending the above concept, an innovative approach is the time domain. An R-tree type index is maintained for all
proposed in [291 to match subsequences by generating the subsequences of a given length (say, U). The matching of all
first few Fourier coefficients of all possible subsequences of similar sequences consists of three steps. In the first step, all
a given length for each stored sequence in the database. The matching pairs of subsequences of length U are identified
idea is to match each sequence into a small set of multidi- using the R-tree type index. In the second step, for each pair
mensional rectangles in the feature space. These rectangles of sequences, the matching pairs in step one are stitched
can then be indexed by spatial access methods like R-tree into long subsequence matches. The third step linearly or-
family of indexes. This approach uses a moving window of ders the long subsequence matches found in the second
a given length to slice each sequence at every possible posi- step to determine the one with the longest match length.
t a n , and extracts features for each subsequence in the win- This approach allows the amplitude of one of the two se-
dow. (The window size determines not only the minimum quences to be scaled and its offset adjusted properly. It also
target sequence length that can be matched, but also the permits nonmatching gaps in the matching subsequences.
effectiveness of the search.) Thus each sequence maps into a
trail in the feature space when sliding the moving window
8 MININGPATHTRAVERSAL
PATTERNS
across the sequence. To reduce bookkeeping, each trail
of feature vectors is divided into subtrails and each of In a distributed information providing environment, docu-
these subtrails is represented with its minimum bounding ments or objects are usually linked together to facilitate
rectangle. interactive access. Examples for such information providing
Fourier transformation is by no means the best method environments include World Wide Web (WWW) [23] and
of feature extraction. It is known that the a priori relative on-line services, such as Prodigy, CompuServe, and Amer-
importance of the features can be optimally determined ica Online, where users, when seeking for information of
from the singular value decomposition (SVD) or the interest, travel from one object to another via the corre-
Karhunen-Loeve transformation on the covariance matrix sponding facilities (i.e., hyperlinks and URL addresses)
of the collection of the time sequences [641. A fast heuristic provided. Clearly, understanding user access patterns in
algorithm which approximates this dimensionality reduc- such environments will not only help improving the system
tion process is proposed in [28]. Even with the significant design (e.g., providing efficient access between highly cor-
dimensionality reduction resulting from the algorithm pro- related objects, better authoring design for pages, etc.) but
posed in [28] and the compression of the representations of also be able to lead to better marketing decisions (e.g., put-
the subsequences in the feature space using the method ting advertisements in proper places, better customer/user
proposed in 1291, generating all subsequences from each classification and behavior analysis, etc.). Capturing user
time series is still a daunting task for a database of long access patterns in such environments is referred to as min-
sequences. ing path traversal patterns. Note that although some efforts
In [54], an enhancement is proposed of the feature ex- have been elaborated upon analyzing the user behavior
traction and matching method discussed in [29]. This [12], 1151, [16], mining path traversal patterns is still in its
new approach on subsequence matching is referred to as infancy. This can be in part explained by the reason that
HierarchyScan. It uses the correlation coefficient as an al- these information providing services, though with great
ternative similarity measure between the target se- potential, are mostly in their infancy and their customer
quence and the stored sequences, and performs an adap- analysis may still remain in a coarser level such as the fre-
tive scan on the extracted features of the stored sequences quency of a page visited and user occupation/age study.
based on the target sequence. Because of the use of correla- Note that, as pointed out in [19], since users are traveling
tion as a similarity measure, the method is insensitive to the along the information providing services to search for the
possible scale and phase differences between the stored desired information, some objects are visited because of
sequences and the target sequence. It also eliminates the their locations rather than their content, showing the very
need of generating all subsequences from each stored se- difference between the traversal pattern problem and oth-
quence for subsequence matching. To improve the search ers which are mainly based on customer transactions. This
efficiency, HierurchyScan first selects the subset of features unique feature of the traversal pattern problem unavoida-
with the greatest discriminating capability (i.e., the features bly increases the difficulty of extracting meaningful infor-
with the largest filtering effect) to perform the matching mation from a sequence of traversal data, and explains the
(correlating). Only a small fraction of the sequences is ex- reason that current web usage analysis products are only
pected to pass the test. Then the next most discriminating able to provide statistical information for traveling points,
set of features is used for matching. This process is iterated but not for traveling paths. However, as these informa-
until all of the features are exhausted. Compared to the tion providing services are becoming increasingly popular
method proposed in [29], HzerarchyScan performs a hierar- nowadays, there is a growing demand for capturing user
traveling behavior and improving the quality of such

services.
In response to this demand, the problem of mining tra-
versal patterns was explored in [19],where the proposed
solution procedure consists of two steps. First, an algorithm
was devised to convert the original sequence of log data
1
into a set of traversal subsequences. Each traversal subse-
quence represents a maximal forward reference from the
starting point of a user access. It is noted that this step of
converting the original log sequence into a set of maximal
forward references will filter out the effect of backward
references which are mainly made for ease of traveling, and
enable us to concentrate on mining meaningful user access 11
sequences. Second, algorithms to determine the frequent
traversal patterns, termed large reference sequences, from the
maximal forward references obtained above were devel-
oped, where a large reference sequence is a reference se-
quence that appeared a sufficient number of times in the
database. For example, suppose the traversal log contains
the following traversal path for a user:
{A, B, C, D, C, B, E, G, H, G, W, A, 0,
U, 0,
VI,
as shown in Fig. 5. Then, the set of maximal forward refer- Fig. 5. An illustrative example for traversal patterns.
ences for this user is
{ABCD,ABEGH, ABEGW, AOU, AOV].
SUMMARY
After maximal forward references for all users are obtained,
Data mining is a fast expanding field with many new re-
the problem of finding frequent traversal patterns is
search results reported and new systems or prototypes de-
mapped into the one of finding frequent occurring con- veloped recently. Researchers and developers in many
secutive subsequences among all maximal forward refer- fields have contributed to the state of the art of data mining
ences. After large reference sequences are determined,
[30], [70]. Therefore, it is a challenging task to provide a
maximal refeyenee sequences can then be obtained in a comprehensive overview of the data mining methods
straightforward manner. A maximal reference sequence is a
within a short article This article is an attempt to provide a
large reference sequence that is not contained in any other
reasonably comprehensive survey, from a database re-
maximal reference sequence. Suppose that {AB, B E , AD,
searcher’s point of view, on the data mining techniques
CG, G H , BG] is the set of large 2-references and {ABE,
developed recently. An overview of data mining and
CGH} is the set of large 3-references. Then, the resulting
knowledge discovery, from some data mining and machine
maximal reference sequences are AD, BG, ABE, and CGH. A
learning researchers, has been performed recently [69].The
maximal reference sequence corresponds to a frequently
major difference of our survey from theirs is the focus of
accessed pattern in an information providing service.
this survey is on the techniques developed by database re-
It is noted that the problem of finding large reference se-
searchers, with an emphasis on efficient methods for data
quences is similar to that of finding large itemsets for asso-
mining in very large databases. A classification of the avail-
ciation rules [4] where a large itemset is a set of items ap-
able data mining techniques is provided and a comparative
pearing in a sufficient number of transactions. However,
study of such techniques has been presented.
they are different from each other in that a reference se-
Based on the diversity of data mining methods and rich
quence in mining traversal patterns has to be consecutive
functionalities of data mining investigated so far, many
references in a maximal forward reference whereas a large
data mining systems or prototypes have been developed
itemset in mining association rules is just a combination of
recently, some of which have been used successfully for
items in a transaction. As a consequence, the very differ-
mining knowledge in large databases. Here we briefly in-
ence between these two problems calls for the use of differ-
troduce some data mining systems reported in recent con-
ent algorithms for mining the knowledge required. As the
ferences and journals. However, this introduction is by no
popularity of internet explodes nowadays, it is expected
means complete. Appendices are welcome, and a compre-
that how to effectively discover knowledge on the web will
hensive overview of such systems is necessary.
be one of the most important data mining issues for years
QUEST is a data mining system developed at the IBM
to come.
Almaden Research Center by Agrawal et al. 161, which
discovers various kinds of knowledge in large databases,
including association rules [7],1781, 1791, sequential pat-
terns 181, classification rules [59], pattern matching and
analysis [5], etc. KEFIR is a knowledge discovery system
developed at the GTE Labs by Piatetsky-Shapiro [68]and
CHEN ET AL DATA MINING AN OVERVIEW FROM A DATABASE PERSPECTIVE 881
Piatetsky-Shapiro et al. [58] for the analysis of health care ACKNOWLEDGMENTS

data. SKICAT is a knowledge discovery system, developed
Jiawei Han was supported, in part, by Research Grant
at Jet Propulsion Laboratory, which automatically detects
NSERC-A3723 from the Natural Sciences and Engineer-
and classifies sky objects from image data resulting from a
ing Research Council of Canada, Research Grant NCE:
major astronomical sky survey. DBMiner is a relational data
IRIS/Precarn-HMI5 from the Networks of Centers of Ex-
mining system developed at Simon Fraser University by
cellence of Canada, and research grants from MPR
Han et al. [37] and Han and Fu [39], [40], for mining multi-
Teltech Ltd. and Hughes Research Laboratories.
ple kinds of rules at multiple abstraction levels, including
characteristic rules, discriminant rules, association rules,
classification rules, etc. KnowledgeMiner is a data mining REFERENCES
system, developed by Shen et al. [75], which integrates data R. Agrawal, C. Faloutsos, and A. Swami, "Efficient Similarity
mining with deductive database techniques and using the Search in Sequence Databases," Proc. Fourth Int'l Conf. Foundations
meta-pattern to guide the data mining process. INLEN is a of Data Organization and Algorithms, Oct. 1993.
R. Agrawal, S.Ghosh, T. Imielinski, B. Iyer, and A. Swami, "An
system, developed by Michalski et al. [61], which integrates Interval Classifier for Database Mining Applications," Proc. 18th
multiple learning paradigms in data mining. Explora is a Int'l Conf. Very Large Data Bases, pp. 560-573, Aug. 1992.
multipattern and multistrategy discovery assistant devel- R. Agrawal, T. Imielinski, and A. Swami, "Database Mining: A
oped by Klosgen [52]. IMACS is a data mining system de- Performance Perspective," IEEE Trans. Knowledge and Data Eng.,
pp. 914-925, Dec. 1993.
veloped at AT&T Laboratory by Brachman and Anand [13], R. Agrawal, T. Imielinski, and A. Swami, "Mining Association
using sophisticated knowledge representation techniques. Rules between Sets of Items in Large Databases," Proc. A C M
DataMine is system exploring interactive ad hoc query-directed SIGMOD, pp. 207-216, May 1993.
R. Agrawal, K.-I. Lin, H.S. Sawhney, and K. Shim, "Fast Similarity
data mining, developed by Imielinski and Virmani [45]. Search in the Presence of Noise, Scaling, and Translation in Time-
IDEA, developed at AT&T Laboratory by Selfridge et al. 1741, Series Databases," Proc. 21th Int'l Couf. Very Large Data Bases,
performs interactive data explorations and analysis. There pp. 490-501, Sept. 1995.
have been many other data mining systems reported by R. Agrawal, M. Mehta, J. Shafer, R. Srikant, A. Arning, and
T. Bollinger, "The QUEST Data Mining System," Proc. Int'l Conf.
machine learning and statistics researchers. Moreover, data Data Mining and Knowledge Discovery (KDD '96), pp. 244-249,
warehousing systems have been seeking data mining tools Portland, Ore., Aug. 1996.
for further enhancement of data analysis capabilities, and it R. Agrawal and R. Srikant, "Fast Algorithms for Mining Associa-
tion Rules in Large Databases," Proc. 20th Int'l Conf. Very Large
is likely to see a trend of integration of the techniques of Data Bases, pp. 478499, Sept. 1994.
data warehousing and data mining in the near future. R. Agrawal and R. Srikant, "Mining Sequential Patterns," Proc.
Besides the work done by database researchers, there 11th Int'l Conf. Data Eng., pp. 3-14, Mar. 1995.
have been fruitful results on data mining and knowledge K.K. Al-Taha, R.T. Snodgrass, and M.D. Soo, "Bibliography on
Spatiotemporal Databases," A C M SIGMOD Record, vol. 22, no. 1,
discovery reported in many others fields. For example, re- pp. 59-67, Mar. 1993.
searchers in statistics have developed many techniques T.M. Anwar, H.W. Beck, and S.B. Navathe, "Knowledge Mining
which may benefit data mining [261. Inductive logic pro- by Imprecise Querying: A Classification-Based Approach," Proc.
gramming [25] is a fast growing subfield in logic program- Eighth Int'l Conf. Data Eng., pp. 622-630, Feb. 1992.
N. Beckmann, H.-P. Kriegel, R. Schneider, and B. Seeger, "The
ming which is closely related to data mining. There have R"-Tree: An Efficient and Robust Access Method for Points and
also been active studies on data mining using data visuali- Rectangles," Proc. A C M SIGMOD Int'l Conf. Management Data, pp.
zation techniques [49] and visualization of data mining re- 322-331, Atlantic City, N.J., June 1990.
M. Bieber and J. Wan, "Backtracking in a Multiple-Window Hy-
sults [51]. For lack of space, the results and issues in these pertext Environment," Proc. A C M European Conf. Hypermedia
related fields cannot be presented in this short article. An Technology, pp. 158-166,1994,
overview of data mining and knowledge discovery in a R. Brachman and T. Anand, "The Process of Knowledge Discov-
broader spectrum is left as a future exercise. ery in Databases: A Human-Centered Approach," U.M. Fayyad,
G. Piatetsky-Shapiro, P. Smyth, and R. Uthurusamy, eds., Ad-
As a young and promising field, data mining still faces vances in Knowledge Discovery and Data Mining, pp. 37-58.
many challenges and unsolved problems which pose new AAAI/MIT Press, 1996.
research issues for further study. For example, further de- L. Breiman, J. Friedman, R. Olshen, and C. Stone, Classification of
Regression Trees. Wadsworth, 1984.
velopment of efficient methods for mining multiple kinds E. Caramel, S. Crawford, and H. Chen, "Browsing in Hypertext A
of knowledge at multiple abstraction levels, a flexible and Cognitive Study," IEEE Trans. Systems, Man, and Cybernetics,
convenient data mining language or interface, the devel- vol. 22, no. 5, pp. 865-883, Sept. 1992.
opment of data mining techniques in advanced database L.D. Catledge and J.E. Pitkow, "Characterizing Browsing Strate-
gies in the World-Wide Web," Proc. Third WWW Conf., Apr. 1995.
systems, such as active databases, object-oriented data- P.K. Chan and S.J. Stolfo, "Learning Arbiter and Combiner Trees
bases, spatial databases, and multimedia databases, data from Partitioned Data for Scaling Machine Learning," PUOC.
mining in Internet information systems, the application of First Int'l Conf. Knowledge Discovery and Data Mining (KDD '98,
pp. 3944, Aug. 1995.
discovered knowledge, the integration of discovered and P. Cheeseman and J. Stutz, "Bayesian Classification (Autoclass):
expert-defined knowledge, and the method to ensure secu- Theory a n d Results," U.M. Fayyad, G . Piatetsky-Shapiro,
rity and protection of privacy in data mining, are important P. Smyth, and R. Uthurusamy, eds., Advances in Knowledge Dis-
issues for further study. covery and Data Mining, pp. 153-180, AAAI/MIT Press, 1996.
M.-S. Chen, J.-S. Park, and P.S. Yu, "Data Mining for Path Tra-
versal Patterns in a Web Environment," Proc. 16th Int'l Conf. Dis-
tributed Computing Systems, pp. 385-392, May 27-30,1996.
M.-S. Chen and P.S. Yu, "Using Multi-Attribute Predicates for
Mining Classification Rules," IBM Research Report, 1995.
882 IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, VOL. 8, NO 6, DECEMBER 1996
[21] D W Cheung, J Han, V Ng, and C Y Wong, ”Maintenance of 1431 V Harinarayan, J D Ullman, and A Ra~araman,”Implementing
Discovered Association Rules in Large Databases An Incremental Data Cubes Efficiently,” P70c 1996 A C M SIGMOD Int 1 Conf
Updating Technique,” Proc Int’l Conf Data Eng , New Or- Management Data, pp 205-216, Montreal, Canada, June 1996
leans, La, Feb 1996 [44] IBM, ”Scalable POWERparallel Systems,” Technical Report GA23-
[22] C Clifton and D Marks, ”Seiurily and Privdcy Implications of 2475-02, Feb 1995
Data Mining,” Proc 1996 SIGMOD ’96 Workshop Research Issues [45] T Imielinski and A Virmani, ”DataMine-Appltcation Pro-
Data Mining and Knowledge Discovery ( D M K D ‘96), pp 15-20, gramming Interface and Query Language for kdd Applications,”
Montreal, Canada, June 1996 Proc Int’l Conf Data Mining and Knowledge Discovery (KDD ‘961,
1231 J December and N Randall, The World Wide Web Unleashed SAMS pp 256-261, Portland, Ore, Aug 1996
Publishing, 1994 1461 H V Jagadish, “A Retnwsl Tpchnique for Similar Shapes,” PYOC
1241 V Dhar and A Tuzhilin, ”Abstract-Driven Pattern Discovery in A C M SIGMOD, pp 208-217,1991
Databases,” IEEE Trans Knowledge and Data E n g , pp 926-938, [47] A K Jain and R C Dubes, Algorithms for Clustering Data Prentice
Dec 1993 Hall, 1988
[25] S Dzeroski, ”Inductive Logic Programming and Knowledge [48] L Kaufman and P J Rousseeuw, Fznding Groups in Data An Intvo-
Discovery,” U M Fayyad, G Piatetsky-Shapiro, P Smyth, and duction to Cluster Analysis John Wiley and Sons, 1990
R Uthurusamy, eds , Advances in Knowledge Discovery and Data [49J D Keim, H Kriegel, and T Seidl, ”Supporting Data Mining of
Mining, pp 117-152 AAAI/MIT Press, 1996 Large Databases by Visual Feedback Queries,” Proc 10th Int’l
[26] J Elder IV and D Pregibon, ”A Statistical Perspective on Knowl- Coizf Data Eng ,pp 302-313, Houston, Feb 1994
edge Discovery in Databases,” U M Fayyad, G Piatetsky- 1501 W Kim, Introduction to Obiected-Onented Databases Cambridge, ”
Shapiro, P Smyth, and R Uthurusamy, eds , Advaizces in Knowl- Mass.: MIT Press, 1990.
edge Discovery and Data M i n i n g , pp 83-115 AAAI/MIT [511 M. Klcmettinen, H. Mannila, P. Ronkainen, H. Toivonen, and
Press, 1996 A.I. Verkamo, ”Finding Interesting Rules from Large Sets of Dis-
[27] M Ester, H I’ Kriegel, and X Xu, ”Knowledge Discovery in covered Association Rules,” Proc. Third Int’l Con$ Information and
Large Spatial Databases Focusing Techniques for Efficient Class Knowledge Management, pp. 401-408, Gaithersburg, Md., Nov. 1994.
Identification,” Proc Fourth Int’l Symp Large Spatial Databases [52] W. Klosgen, ”Explora: A Multipattern and Multistrategy Discov-
( S S D 951, pp 67-82, Portland, Maine, Aug 1995 ery Assistant,” U.M. Fayyad, G. Piatetsky-Shapiro, P. Smyth, and
[28] C Faloutsos and K-I Lin, ”FastMap A Fast Algorithm for In- R. Uthurusamy, eds., Advances in Knowledge Discovery and Data
dexing, Data-Mining and Visualization ol Traditional dnd Multi- Mining, pp. 249-271. AAAI/MIT Press, 1996.
media Datasets,” Proc A C M SIGMOD, pp 163-174, May 1995 1531 K.Koperski and J. Han, “Discovery of Spatial Association Rules
[29] C Faloutsos, M Ranganatlian, and Y Manolopoulos, ”Fast Sub- in Geographic Information Databases,” Proc. Fourth Int’l Symp.
sequence Matching in Time-Series Databases,” Proc A C M Large Spatial Databases ( S S D ‘951, pp. 47-66, Portland, Maine,
S I G M O D , Minneapolis, Minn ,pp 419429, May 1994 Aug. 1995.
[30] U M Fayyad, G Piatetshy-Shapiro, P Smyth, and R Uthu- [54] C-S. Li, P.S. Yu, and V. Castelli, ”HierarchyScan: A Hierarchical
rusamy, Advances in Knowledge Discovevy and Data Mining Similarity Search Algorithm for Databases of Long Sequences,”
AAAI/MIT Press, 1996 Proc. 12th Int’l Conf.Data Eng., Feb. 1996.
[31] D Fisher, ”Improving Inference Through Conceptual Clustering,” [55] H. Lu, R. Setiono, and H. Liu, ”NeuroRule: A Connectionist Ap-
Proc A M I Conf, pp 461465, Seattle, July 1987 proach to Data Mining,” Proc. 21th Int’l Conf, Very Large Data
[32] D Fisher, ”Optimization and Simplification of Hierarchical Clus- Bases, pp. 478489, Sept. 1995.
terings,” Proc First Int 1 Conf Knowledge Discovery and Data Mining [561 W. Lu, J. Han, and B.C. Ooi, “Knowledge Discovery in Large
(KDD ’95), pp 118-123, Montreal, Canada, Aug 1995 Spatial Databases,” Proc. Far East Workshop Geographic Information
[33] Y Fu and J Han, ”Meta-Rule-Guided Mining of Association Systems, pp. 275-289, Singapore, June 1993.
Rules in Relational Databases,” Proc First Int’l Workshop Integra- [57] H. Mannila, H. Toivonen, and A. Inkeri Verkamo, ”Efficient Al-
tion of Knowledge Discovery with Deductive and Object-Oriented Da- gorithms for Discovering Association Rules,” Proc. AAAl Work-
tabases (KDOOD ’951, pp 39-46, Singapore, Dec 1995 shop Knowledge Discovery in Databases, pp. 181-192, July 1994.
[341 B R Gains, ”Tranforming Rules and Trees into Comprehensive 1581 C.J. Matheus, G. Piatetsky-Shapiro, and D. McNeil, “Selecting and
I<nowledge Structures,” U M Fayyad, G Piatetsky-Shapiro, Reporting What is Interesting: The KEFIR Application to Health-
P Srnyth, and R Uthurusamy, eds ,Advances in Knowledge Discov- Care Data,” U.M. Fayyad, G. I’iatetsky-Shapiro, P.Smyth, and
ery and Data Mining, pp 205-228 AAAI/MIT Press, 1996 R. Uthurusamy, eds., Advances in Knowledge Discovery and Data
[35] A Gupta, V Hannarayan, and D Quass, “Aggregate-Query Mining, pp. 495-516. AAAI/MIT Press, 1996.
Processing in Data Warehousing Environment,” Proc 21sf Int’l [591 M. Mehta, R. Agrawal, and J. Rissanen, ”SLIQ: A Fast Scalable
Conf Very Large Data Bases, pp 358-369, Zurich, Sept 1995 Classifier for Data Mining,” Proc. Int’l Conf. Extending Database
[361 J Han, ”Mining Knowledge at Multiple Concept Levels,” Proc Technology (EDBT ’961, Avignon, France, Mar. 1996.
Fourth I n t 1 Conf Information and Knowledge Management, 1601 R.S.Michalski, “A Theory and Methodology of Inductive Learn-
pp 19-24, Baltimore, Md ,Nov 1995 ing,” Michalski et al., eds., Machine Learning: An Artificial Intelli-
[371 J Han, Y Cai, and N Cercone, ”Data Driven Discovery of Quan- gence A p p ~ o a c hvol.
, 1, pp. 83-134. Morgan Kaufmann, 1983.
titative Rules in Relational Databases,” IEEE Trans Knowledge and [611 R.S. Michalski, L. Kerschberg, K.A. Kaufman, and J.S. Ribeiro,
Data Eng ,vol 5, pp 29 40,1993 ”Mining for Knowledge in Databases: The INLEN Architecture,
[381 J Han and Y Fu, ”Dynamic Generation and Refinement of Initial Implementation, and First Results,” J. Int’l Information Sys-
Concept Hierarchies for Knowledge Discovery in Databases,” tems, vol. 1, pp. 85-114,1992.
Proc AAA1 ‘94 Workshop Knowledge Discovery in Databases 1621 R. Ng and J. Han, ”Efficient and Effective Clustering Method for
( K D D ’941, pp 157-168, Seattle, July 1994 Spatial Data Mining,” Proc. Int’l Conf. V e r y Large Data Bases,
[391 J Han and Y Fu, ”Discovery of Multiple-Level Association Rules pp. 144-155, Santiago, Chile, Sept. 1994.
from Large Databases,” Proc 21th Int’l Conf Very Lavge Data Bases, C631 D.E. OLeary, ”Knowledge Discovery as a Threat to Database
pp 420-431 Sept 1995 Security,” G. Piatetsky-Shapiro and W.J. Frawley, eds., Knowledge
1401 J Han and Y Fu, ”Exploration of the Power of Attribute-Oriented Discovery in Databases, pp. 507-516, AAAI/MIT Press, 1991.
Induction in Data Mining,” U M Fayyad, G Piatetsky-Shapiro, [641 A. Papoulis, Probability, Random Variable, and Stochastic Process.
P Smyth, and R Uthurusamy, eds ,Advances in Knowledge Discov- New York McGraw Hill, 1984.
ery and Data Mining, pp 399421, AAAI/MIT Press, 1996 [651 J.-S. Park, M.-S. Chen, and P.S. Yu, ”Mining Association Rules
1411 J Han, S Nishio, and H Kawano, ”Knowledge Discovery in Ob- with Adjustable Accuracy,” IBM Research Report, 1995.
ject-Oriented and Active Databases,” F Fuchi and T Yokoi, eds , [661 J.-S. Park, M.-S. Chen, and P.S. Yu, ”An Effective Hash Based
Knowledge Building and Knowledge Sharing, pp 221-230, Ohmsha, Algorithm for Mining Association Rules,” Proc. A C M SIGMOD,
Ltd and IOS Press, 1994 pp. 175-186, May 1995.
[421 J Han, Y Fu, Mi Wang, J Chmng, W Gong, K Kopersk, D Li, Y Lu, [671 J.6.Park, M.-S. Chen, and P.S. Yu, ”Efficient Parallel Data Mining
A Rajan, N Stefanovic, B Xia, and O R Zaiane, “DBMmer A for Association Rules,” Proc. Fourth Int’l Conf. Information and
System for Mining Knowledge in Large Relational Databases,” Knowledge Management, pp. 31-36, Nov. 29-Dec. 3,1995.
Proc Int’l Coni Data Mining and Knowledge Discovery ( K D D ’961,
pp 250-255, Portland, Ore, Aug 1996
G. Piatetsky-Shapiro, ”Discovery, Analysis, and Presentation of Internet applications. He was a research staff member at the IBM
Strong Rules,” G. Piatetsky-Shapiro and W. J. Frawley, eds., Thomas J. Watson Research Center, Yorktown Heights, New York,
Knowledge Discovery in Databases, pp. 229-238. AAAI/MIT Press, form 1988 to 1996, primarily involved in projects related to parallel
1991. databases, multimedia systems, and digital libraries. He has published
G. Piatetsky-Shapiro, U. Fayyad, and P. Smith, ”From Data Min- more than 70 refereed international journakonference papers in his
ing to Knowledge Discovery: An Overview,” U.M. Fayyad, research areas.
G. Piatetsky-Shapiro, P. Smyth, and R. Uthurusamy, eds., Ad- Dr. Chen is a guest co-editor of this special issue of /€E€ Transac-
vances in Knowledge Discovery and Data Mining, pp. 1-35. tions on Knowledge and Data Engineering dedicated to data mining.
AAAI/MIT Press, 1996. He is the inventor of many international patents in the areas of interac-
G. Piatetsky-Shapiro and W.J. Frawley, Knowledge Discovery in tive video playout, video server design, interconnection networks, and
Databases. AAAI/MIT Press, 1991. concurrency and coherency control protocols. He received the Out-
J.R. Quinlan, ”Induction of Decision Trees,” Machine Learning, standing Innovation Award from IBM in 1994 for his contributions to
vol. 1, pp. 81-106,1986. parallel transaction design of a major database product, and has re-
J.R. Quinlan, C4.5: Programs for Machine Learning. Morgan Kauf- ceived numerous awards for his inventions and patent applications. He
mann, 1993. is a senior member of the IEEE and a member of the IEEE Computer
A. Savasere, E. Omiecinski, and S. Navathe, ”An Efficient Algo- Society and ACM.
rithm for Mining Association Rules in Large Databases,” Proc.
21th Int’l Conf. V e y Large Data Bases, pp. 432444, Sept. 1995.
P.G. Selfridge, D. Srivastava, and L.O. Wilson, “IDEA: Interactive Jiawei Han received his PhD from the Univer-
Data Exploration and Analysis,” Proc. ACM SIGMOD Int’l Conf. sity of Wisconsin, Madison, in 1985. He is now a
Management Data, pp. 24-34, Montreal, Canada, June 1996. professor in the School of Computer Science
W. Shen, K. Ong, B. Mitbander, and C. Zaniolo, “Metaqueries for and director of the Database Systems Research
Data Mining,” U.M. Fayyad, G. Piatetsky-Shapiro, P. Smyth, and Laboratory at Simon Fraser University in British
R. Uthurusamy, eds., Advances in Knowledge Discovery and Data Columbia, Canada.
Mining, pp. 375-398. AAAI/MIT Press, 1996. Dr. Han has conducted research in the areas
A. Silberschatz, M. Stonebraker, and J.D. Ullman, ”Database Re- of knowledge discovery in databases, deductive
search: Achievements and Opportunities into the 21st Century,” and object-oriented databases, spatial data-
Report NSF Workshop Futuve of Database Systems Research, bases, multimedia databases, and logic pro-
May 1995. gramming. He has published more than 100
A. Silberschatz and A. Tuzhilin, ”On Subjective Measure of Inter- journal and conference papers. He is a project leader of the Canada
estingness in Knowledge Discovery,” Proc. First Int’l Conf. Knowl- NCE/IRIS:HMI-5 project (data mining and knowledge discovery in large
edge Discovevy and Data Mining (KDD ’95), pp. 275-281, Montreal, databases) and has served or is currently serving on program com-
Canada, Aug. 1995. mittees of more than 30 international conferences and work-
R. Srikant and R. Agrawal, ”Mining Generalized Association shops-including ICDE ’95 (Program Committee vice chair), DOOD
Rules,” Proc. 21th Int’l Conf. Very Large Data Bases, pp. 407419, ’95, ACM SIGMOD ’96, VLDB ’96, ClKM ’96, KDD ‘96 (Program Com-
Sept. 1995. mittee co-chair), and SSD ’97. He has also served as editor of /€E€
R. Srikant and R. Agrawal, “Mining Quantitative Association Transactions on Knowledge and Data Engineering, the Journal of In-
Rules in Large Relational Tables,” Proc. 1996 ACM SIGMOD Int’l telligent lnformafion Systems, and the Journal of Data Mining and
Conf. Management Data, pp. 1-12, Montreal, Canada, June 1996. Knowledge Discovery. He is a senior member of the IEEE and a mem-
R. Stam and R. Snodgrass, “A Bibliography on Temporal Data- ber of the IEEE Computer Society.
bases,” IEEE Bull. Data Eng., vol. 11, no. 4, Dec. 1988.
Y. Stettiner, D. Malah, and D. Chazan, ”Dynamic Time Warping
with Path Control and Nonlocal Cost,” Proc. 12th IAPR Int’l Conf. Philip S. Yu (S‘76-M’78-SM’87-F‘93) received
Pattern Recognition, pp. 174-177, Oct. 1994. the BS degree in electrical engineering from Na-
S.M. Weiss and C.A. Kulikowski, Computer Systems that Learn: tional Taiwan University, Taipei, Tarwan, Repub-
Classification and Prediction Methods from Statistics, Neural Nets, lic of China, in 1972; the MS and PhD degrees
Machine Learning, and Expert Systems. Morgan Kaufman, 1991. in electrical engineering from Stanford Univer-
J. Widom, “Research Problems in Data Warehousing,” Proc. sity in 1976 and 1978, respectively; and the
Fourth Int’l Conf. Information and Knowledge Management, MBA degree from New York University in 1982.
pp. 25-30, Baltimore, Nov. 1995. Dr Yu has been with the IBM Thomas J.
W.P. Yan and P. Larson, ”Eager Aggregation and Lazy Aggrega- Watson Research Center, Yorktown Heights,
tion,” Proc. 21st Int’l Conf. Very Large Data Bases, pp. 345-357, New York, since 1978, and is currently manager
Zurich, Sept. 1995. of the Software Tools and Techniques group in
T. Zhang, R. Ramakrishnan, and M. Livny, ”BIRCH: An Efficient the Internet Department. His current research interests include data-
Data Clustering Method for Very Large Databases,” Proc. 3996 base systems, data mining, multimedia systems, transaction and query
ACM SIGMOD Int’l Conf. Management Data, Montreal, Canada, processing, parallel and distributed systems, disk arrays, computer
June 1996. architecture, performance modeling, and workload analysis. He has
Y. Zhuge, H. Garcia-Molina, J. Hammer, and J. Widom, ”View published more than 200 papers in refereed journals and conferences,
Maintenance in a Warehousing Environment,” Proc. 1995 ACM plus more than 140 research reports and 90 invention disclosures. He
SIGMOD Int’l Conf. Management Data, pp. 316-327, San Jose, holds, or has applied for, 31 U.S. patents.
Calif., May 1995. Dr. Yu is a fellow of the IEEE and the ACM, and a member of the
W. Ziarko, Rough Sets, Fuzzy Sets and Knowledge Discovery. IEEE Computer Society. He is an editor of /€€E Transactions on
Springer-Verlag, 1994. Knowledge and Data Engineering. In addition to serving as a program
committee member of various conferences, he has served as program
chair of the Second International Workshop on Research Issues on
Data Engineering; Transaction and Query Processing and as program
Ming-Syan Chen received the BS degree in co-chair of the 11th International Conference on Data Engineering, He
electrical engineering from National Taiwan has received several IBM and external honors, including awards for
University in Taipei, Republic of China, in 1982, Best Paper, IBM Outstanding Innovation, Outstanding Technical
and the MS and PhD degrees in COtnpUter, in- Achievement, Research Division, and 15 Invention Achievements.
formation, and control engineering from the
University of Michigan, Ann Arbor, in 1985 and
1988, respectively
Dr. Chen is a faculty member in the Electrical
Engineering Department at National Taiwan
University. HIS research interests include net-
work databases, multimedia technologies, and

Data Mining An Overview From A Database Perspective

Uploaded by

Copyright:

Available Formats

Data Mining An Overview From A Database Perspective

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Data Mining An Overview From A Database Perspective

Uploaded by

Copyright:

Available Formats

866 IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGIJEERING, VOL 8, NO 6, DECEMBER 1996

a similar or slightly different meaning, such as knowledge 4

2.1 Classifying Data Minin .2 Mining Different Kinds of Knowledge from

Database L) transaction size but also pruning the number of transac-

i are iterative algorithms on the large itemset size in the

Fig. 2. Generation of candidate itemsets and large itemsets.

CHEN ET AL.: DATA MINING: AN OVERVIEW FROM A DATABASE PERSPECTIVE 871

Dairyland Foremost Old Mills Wonder

class discipline grant -category amount -category support% comparison%

CHEN ET AL.: DATA MINING: AN OVERVIEW FROM A DATABASE PERSPECTIVE 875

where N is the number of points in the subcluster, LS is the

improve its performance. and SS is the square sum of data points,

traveling behavior and improving the quality of such

Piatetsky-Shapiro et al. [58] for the analysis of health care ACKNOWLEDGMENTS

You might also like