Advanced Patterns - Data Mining

1 Pattern Mining: A Road Map

Based on pattern diversity, pattern mining can be classified using the following
criteria:
Basic patterns: As discussed in Chapter 6, a frequent pattern may have several alternative
forms, including a simple frequent pattern, a closed pattern, or a max-pattern.
To review, a frequent pattern is a pattern (or itemset) that satisfies a minimum support
threshold. A pattern p is a closed pattern if there is no superpattern p
0 with the
same support as p. Pattern p is a max-pattern if there exists no frequent superpattern
of p. Frequent patterns can also be mapped into association rules, or other kinds
of rules based on interestingness measures. Sometimes we may also be interested in
infrequent or rare patterns (i.e., patterns that occur rarely but are of critical importance,
or negative patterns (i.e., patterns that reveal a negative correlation between
items).

We refer to the rule set mined as
consisting of multilevel association rules. If, instead, the rules within a given set do
not reference items or attributes at different abstraction levels, then the set contains
single-level association rules.
Based on the number of dimensions involved in the rule or pattern: If the items
or attributes in an association rule or pattern reference only one dimension, it is a
single-dimensional association rule/pattern.
If a rule/pattern references two or more dimensions, such as age, income, and buys,
then it is a multidimensional association rule/pattern.
Based on the types of values handled in the rule or pattern: If a rule involves associations
between the presence or absence of items, it is a Boolean association rule
If a rule describes associations between quantitative items or attributes, then it
is a quantitative association rule. In these rules, quantitative values for items or
attributes are partitioned into intervals.
Based on the constraints or criteria used to mine selective patterns: The patterns
or rules to be discovered can be constraint-based (i.e., satisfying a set of userdefined
constraints), approximate, compressed, near-match (i.e., those that tally
the support count of the near or almost matching itemsets), top-k (i.e., the k most
frequent itemsets for a user-specified value, k), redundancy-aware top-k (i.e., the
top-k patterns with similar or redundant patterns excluded), and so on.

Alternatively, pattern mining can be classified with respect to the kinds of data and
applications involved, using the following criteria:
Based on kinds of data and features to be mined: Given relational and data warehouse
data, most people are interested in itemsets. Thus, frequent pattern mining
in this context is essentially frequent itemset mining,

In sequential patterns, that is, frequent subsequences (which are often separated by some other events) in a sequence
of ordered events.
We may also mine structural patterns, that is, frequent substructures, in a structured
data set. Note that structure is a general concept that covers many different
kinds of structural forms such as directed graphs, undirected graphs, lattices, trees,
sequences, sets, single items, or combinations of such structures. Single items are the
simplest form of structure. Each element of a general pattern may contain a subsequence,
a subtree, a subgraph, and so on, and such containment relationships can
be defined recursively. Therefore, structural pattern mining can be considered as the
most general form of frequent pattern mining.
Based on application domain-specific semantics: Both data and applications can be
very diverse, and therefore the patterns to be mined can differ largely based on their
domain-specific semantics. Various kinds of application data include spatial data,
temporal data, spatiotemporal data, multimedia data (e.g., image, audio, and video
data), text data, time-series data, DNA and biological sequences, software programs,
chemical compound structures, web structures, sensor networks, social and information
networks, biological networks, data streams, and so on. This diversity can lead
to dramatically different pattern mining methodologies.

Based on data analysis usages: Frequent pattern mining often serves as an intermediate
step for improved data understanding and more powerful data analysis. For
example, it can be used as a feature extraction step for classification, which is often
referred to as pattern-based classification. Similarly, pattern-based clustering has
shown its strength at clustering high-dimensional data. For improved data understanding,
patterns can be used for semantic annotation or contextual analysis. Pattern
analysis can also be used in recommender systems, which recommend information
items (e.g., books, movies, web pages) that are likely to be of interest to the user
based on similar users’ patterns. Different analysis tasks may require mining rather
different kinds of patterns as well.

2 Pattern Mining in Multilevel, Multidimensional Space

Mining Multilevel Associations

It is interesting to examine how
to develop effective (useful and not trivial) methods for mining patterns at multiple abstraction levels, with
sufficient flexibility for easy traversal among different abstraction spaces.

Association rules generated from mining data at multiple abstraction levels are
called multiple-level or multilevel association rules. Multilevel association rules can be
mined efficiently using concept hierarchies under a support-confidence framework. In
general, a top-down strategy is employed, where counts are accumulated for the calculation
of frequent itemsets at each concept level, starting at concept level 1 and working
downward in the hierarchy toward the more specific concept levels, until no more frequent
itemsets can be found. For each level, any algorithm for discovering frequent
itemsets may be used, such as Apriori or its variations.

Using uniform minimum support for all levels (referred to as uniform support):
The same minimum support threshold is used when mining at each abstraction level.

Using reduced minimum support at lower levels (referred to as reduced support):
Each abstraction level has its own minimum support threshold. The deeper the
abstraction level, the smaller the corresponding threshold.

Using item or group-based minimum support (referred to as group-based support):
Because users or experts often have insight as to which groups are more
important than others, it is sometimes more desirable to set up user-specific, item, or
group-based minimal support thresholds when mining multilevel rules.

Mining Multidimensional Associations

Following the terminology used in multidimensional databases, we refer to each distinct
predicate in a rule as a dimension.

Instead of considering transactional data only, sales and related information are often
linked with relational data or integrated into a data warehouse. Such data stores are
multidimensional in nature. For instance, in addition to keeping track of the items purchased
in sales transactions, a relational database may record other attributes associated
with the items and/or transactions such as the item description or the branch location
of the sale. Additional relational information regarding the customers who purchased
the items (e.g., customer age, occupation, credit rating, income, and address) may also
be stored. Considering each database attribute or warehouse dimension as a predicate,
we can therefore mine association rules containing multiple predicates such as
age(X, “20...29”) ∧ occupation(X, “student”)⇒buys(X, “laptop”). (7.7)
Association rules that involve two or more dimensions or predicates can be referred
to as multidimensional association rules.

Mining Quantitative Association Rules

 (1) a data cube method, (2)
a clustering-based method, and (3) a statistical analysis method to uncover exceptional
behaviors

Data Cube–Based Mining of Quantitative Associations

The transformed multidimensional data may be used to construct a
data cube. Data cubes are well suited for the mining of multidimensional association
rules: They store aggregates (e.g., counts) in multidimensional space, which is essential
for computing the support and confidence of multidimensional association rules.

Mining Clustering-Based Quantitative Associations

Besides using discretization-based or data cube–based data sets to generate quantitative
association rules, we can also generate quantitative association rules by clustering
data in the quantitative dimensions.

A typical top-down approach for finding clustering-based quantitative frequent patterns
is as follows. For each quantitative dimension, a standard clustering algorithm
(e.g., k-means or a density-based clustering algorithm, as described in Chapter 10) can
be applied to find clusters in this dimension that satisfy the minimum support threshold.
For each cluster, we then examine the 2-D spaces generated by combining the cluster
with a cluster or nominal value of another dimension to see if such a combination passes
the minimum support threshold. If it does, we continue to search for clusters in this
2-D region and progress to even higher-dimensional combinations. The Apriori pruning
still applies in this process: If, at any point, the support of a combination does not
have minimum support, its further partitioning or combination with other dimensions
cannot have minimum support either.

Using Statistical Theory to Disclose Exceptional Behavior

An association rule under the new definition is a rule of the form:
population subset ⇒ mean of values for the subset,
where the mean of the subset is significantly different from the mean of its complement
in the database (and this is validated by an appropriate statistical test).



Mining Rare Patterns and Negative Patterns

3 Constraint-Based Frequent Pattern Mining

users have a good sense of
which “direction” of mining may lead to interesting patterns and the “form” of the patterns
or rules they want to find. They may also have a sense of “conditions” for the rules,
which would eliminate the discovery of certain rules that they know would not be of
interest. Thus, a good heuristic is to have the users specify such intuition or expectations
as constraints to confine the search space. This strategy is known as constraint-based
mining. The constraints can include the following:
Knowledge type constraints: These specify the type of knowledge to be mined, such
as association, correlation, classification, or clustering.
Data constraints: These specify the set of task-relevant data.
Dimension/level constraints: These specify the desired dimensions (or attributes)
of the data, the abstraction levels, or the level of the concept hierarchies to be used in
mining.
Interestingness constraints: These specify thresholds on statistical measures of rule
interestingness such as support, confidence, and correlation.
Rule constraints: These specify the form of, or conditions on, the rules to be mined.
Such constraints may be expressed as metarules (rule templates), as the maximum or
minimum number of predicates that can occur in the rule antecedent or consequent,
or as relationships among attributes, attribute values, and/or aggregates.
These constraints can be specified using a high-level declarative data mining query
language and user interface.



Metarule-Guided Mining of Association Rules

“How are metarules useful?” Metarules allow users to specify the syntactic form of rules
that they are interested in mining. The rule forms can be used as constraints to help
improve the efficiency of the mining process. Metarules may be based on the analyst’s
experience, expectations, or intuition regarding the data or may be automatically
generated based on the database schema.

Constraint-Based Pattern Generation: Pruning Pattern Space and Pruning Data Space

Rule constraints specify expected set/subset relationships of the variables in the mined
rules, constant initiation of variables, and constraints on aggregate functions and other
forms of constraints. Users typically employ their knowledge of the application or
data to specify rule constraints for the mining task. These rule constraints may be
used together with, or as an alternative to, metarule-guided mining. In this section,
we examine rule constraints as to how they can be used to make the mining process
more efficient.

Pruning Pattern Space with Pattern Pruning Constraints

Based on how a constraint may interact with the pattern mining process, there are five
categories of pattern mining constraints: (1) antimonotonic, (2) monotonic, (3) succinct,
(4) convertible, and (5) inconvertible.

Pruning Data Space with Data Pruning Constraints
The second way of search space pruning in constraint-based frequent pattern mining
is pruning data space. This strategy prunes pieces of data if they will not contribute to
the subsequent generation of satisfiable patterns in the mining process. We consider two
properties: data succinctness and data antimonotonicity.
Constraints are data-succinct if they can be used at the beginning of a pattern mining
process to prune the data subsets that cannot satisfy the constraints.
Interestingly, many constraints are data-antimonotonic in the sense that during the
mining process, if a data entry cannot satisfy a data-antimonotonic constraint based on
the current pattern, then it can be pruned.

4. Mining High-Dimensional Data and Colossal Patterns

The frequent pattern mining methods presented so far handle large data sets having
a small number of dimensions. However, some applications may need to mine highdimensional
data (i.e., data with hundreds or thousands of dimensions).

Researchers have overcome this difficulty in two directions. One direction extends a
pattern growth approach by further exploring the vertical data format to handle data
sets with a large number of dimensions (also called features or items, e.g., genes) but
a small number of rows (also called transactions or tuples, e.g., samples). This is useful
in applications like the analysis of gene expressions in bioinformatics, for example,
where we often need to analyze microarray data that contain a large number of genes
(e.g., 10,000 to 100,000) but only a small number of samples (e.g., 100 to 1000). The
other direction develops a new mining methodology, called Pattern-Fusion, which mines
colossal patterns, that is, patterns of very long length.

Mining Colossal Patterns by Pattern-Fusion

Researchers are more interested in finding large patterns
(e.g., long sequences) than finding small ones since larger patterns usually carry more
significant meaning. We call these large patterns colossal patterns, as distinguished from
patterns with large support sets. Finding colossal patterns is challenging because incremental
mining tends to get “trapped” by an explosive number of midsize patterns before
it can even reach candidate patterns of large size

A new mining strategy called Pattern-Fusion was developed, which fuses a small
number of shorter frequent patterns into colossal pattern candidates. It thereby takes
leaps in the pattern search space and avoids the pitfalls of both breadth-first and depth-
first searches. This method finds a good approximation to the complete set of colossal
frequent patterns.
The Pattern-Fusion method has the following major characteristics. First, it traverses
the tree in a bounded-breadth way. Only a fixed number of patterns in a bounded-size
candidate pool are used as starting nodes to search downward in the pattern tree. As
such, it avoids the problem of exponential search space.
Second, Pattern-Fusion has the capability to identify “shortcuts” whenever possible.
Each pattern’s growth is not performed with one-item addition, but with an agglomeration
of multiple patterns in the pool. These shortcuts direct Pattern-Fusion much more
rapidly down the search tree toward the colossal patterns.

e Pattern-Fusion method is outlined in the following two
phases:
1. Initial Pool: Pattern-Fusion assumes an initial pool of small frequent patterns is
available. This is the complete set of frequent patterns up to a small size (e.g., 3).
This initial pool can be mined with any existing efficient mining algorithm.
2. Iterative Pattern-Fusion: Pattern-Fusion takes as input a user-specified parameter,
K, which is the maximum number of patterns to be mined. The mining process is
iterative. At each iteration, K seed patterns are randomly picked from the current
pool. For each of these K seeds, we find all the patterns within a ball of a size specified
by τ . All the patterns in each “ball” are then fused together to generate a set of
superpatterns. These superpatterns form a new pool. If the pool contains more than
K patterns, the next iteration begins with this pool for the new round of random
drawing. As the support set of every superpattern shrinks with each new iteration,
the iteration process terminates.
Note that Pattern-Fusion merges small subpatterns of a large pattern instead of
incrementally-expanding patterns with single items.

5 Mining Compressed or Approximate Patterns

To reduce the huge set of frequent patterns generated in mining while maintaining
high-quality patterns, we can instead mine a compressed or approximate set of frequent
patterns. Top-k most frequent closed patterns were proposed to make the mining process
concentrate on only the set of k most frequent patterns. Although interesting, they usually
do not epitomize the k most representative patterns because of the uneven frequency
distribution among itemsets. Constraint-based mining of frequent patterns
incorporates user-specified constraints to filter out uninteresting patterns. Measures of
pattern/rule interestingness and correlation  can also be used to help confine
the search to patterns/rules of interest.

Mining Compressed Patterns by Pattern Clustering


. Clustering is the automatic process of grouping
like objects together, so that objects within a cluster are similar to one another and dissimilar
to objects in other clusters. In this case, the objects are frequent patterns. The
frequent patterns are clustered using a tightness measure called δ-cluster. A representative
pattern is selected for each cluster, thereby offering a compressed version of the set
of frequent patterns.
Before we begin, let’s review some definitions. An itemset X is a closed frequent
itemset in a data set D if X is frequent and there exists no proper super-itemset Y of X
such that Y has the same support count as X in D. An itemset X is a maximal frequent
itemset in data set D if X is frequent and there exists no super-itemset Y such that
X ⊂ Y and Y is frequent in D.

We can use the following distance measure between closed patterns. Let P1 and P2 be
two closed patterns. Their supporting transaction sets are T(P1) and T(P2), respectively.
The pattern distance of P1 and P2, Pat Dist(P1,P2), is defined as
Pat Dist(P1,P2) = 1 − [|T(P1)∩T(P2)|]/[|T(P1)∪T(P2)|]

Pattern distance is a valid distance metric defined on the set of transactions. Note that it
incorporates the support information of patterns.

The pattern compression problem can be defined as follows: Given a transaction database, a minimum support min sup, and the cluster
quality measure δ, the pattern compression problem is to find a set of representative patterns
R such that for each frequent pattern P (with respect to min sup), there is a representative
pattern Pr ∈ R (with respect to min supr), which covers P, and the value of |R| is
minimized.

Finding a minimum set of representative patterns is an NP-Hard problem. However,
efficient methods have been developed that reduce the number of closed frequent
patterns generated by orders of magnitude with respect to the original collection of
closed patterns. The methods succeed in finding a high-quality compression of the
pattern set.

Extracting Redundancy-Aware Top-k Patterns

A small set of k representative patterns that have not only high significance but also low redundancy
are called redundancy-aware top-k patterns.

A significance measure S is a function mapping a pattern p ∈ P to a real value such
that S(p) is the degree of interestingness (or usefulness) of the pattern p.

Given the significance measure S, the redundancy R between two patterns p and
q is defined as R(p,q) = S(p) + S(q) − S(p,q). Subsequently, we have S(p|q) = S(p) −
R(p,q).

6 Pattern Exploration and Application

Semantic Annotation of Frequent Patterns


“What is an appropriate semantic annotation for a frequent pattern?”

we can define the basic task of semantic pattern annotation
as follows:
1. Select context units and design a strength weight for each unit to model the contexts
of frequent patterns.
2. Design similarity measures for the contexts of two patterns, and for a transaction and
a pattern context.
3. For a given frequent pattern, extract the most significant context indicators, representative
transactions, and semantically similar patterns to construct a structured
annotation.



Applications of Pattern Mining


Pattern mining is widely used for noise filtering and data cleaning as preprocessing
in many data-intensive applications.

Pattern mining often helps in the discovery of inherent structures and clusters
hidden in the data.

Frequent patterns can also be used effectively for subspace clustering in highdimensional
space.

Pattern analysis is useful in the analysis of spatiotemporal data, time-series data,
image data, video data, and multimedia data

Pattern mining has also been used for the analysis of sequence or structural data
such as trees, graphs, subsequences, and networks


Next Chapter: Data Mining - Classification: Basic Concepts
Data Mining - Classification: Advanced Methods

Data Mining Recent Trends and Research Frontiers

Excerpts from the Book

Data Mining Concepts and Techniques
Third Edition
Jiawei Han
University of Illinois at Urbana–Champaign
Micheline Kamber, Jian Pei
Simon Fraser University

Mining Frequent Patterns, Associations, and Correlations: Basic Concepts and Methods

1 Basic Concepts

Frequent pattern mining searches for recurring relationships in a given data set.

Market Basket Analysis:

This process
analyzes customer buying habits by finding associations between the different items that
customers place in their “shopping baskets” (Figure 6.1). The discovery of these associations
can help retailers develop marketing strategies by gaining insight into which items
are frequently purchased together by customers.

Rule support and confidence are two measures of rule interestingness. They respectively
reflect the usefulness and certainty of discovered rules. A support of 2% for
Rule (6.1) means that 2% of all the transactions under analysis show that computer
and antivirus software are purchased together. A confidence of 60% means that 60% of
the customers who purchased a computer also bought the software. Typically, association
rules are considered interesting if they satisfy both a minimum support threshold
and a minimum confidence threshold. These thresholds can be a set by users or
domain experts. Additional analysis can be performed to discover interesting statistical
correlations between associated items.

Frequent Itemsets, Closed Itemsets,
and Association Rules


A set of items is referred to as an itemset.
2 An itemset that contains k items is a
k-itemset.
In general, association rule mining can be viewed as a two-step process:
1. Find all frequent itemsets: By definition, each of these itemsets will occur at least as
frequently as a predetermined minimum support count, min sup.
2. Generate strong association rules from the frequent itemsets: By definition, these
rules must satisfy minimum support and minimum confidence.

2 Frequent Itemset Mining Methods

Apriori Algorithm: Finding Frequent Itemsets
by Confined Candidate Generation
Apriori is a seminal algorithm proposed by R. Agrawal and R. Srikant in 1994 for mining
frequent itemsets for Boolean association rules [AS94b]. The name of the algorithm
is based on the fact that the algorithm uses prior knowledge of frequent itemset properties,
as we shall see later. Apriori employs an iterative approach known as a level-wise
search, where k-itemsets are used to explore (k + 1)-itemsets. First, the set of frequent
1-itemsets is found by scanning the database to accumulate the count for each item, and
collecting those items that satisfy minimum support. The resulting set is denoted by L1.
Next, L1 is used to find L2, the set of frequent 2-itemsets, which is used to find L3, and
so on, until no more frequent k-itemsets can be found. The finding of each Lk requires
one full scan of the database.
To improve the efficiency of the level-wise generation of frequent itemsets, an
important property called the Apriori property is used to reduce the search space.

“How is the Apriori property used in the algorithm?” To understand this, let us look at
how Lk−1 is used to find Lk
for k ≥ 2. A two-step process is followed, consisting of join
and prune actions.
1. The join step: To find Lk
, a set of candidate k-itemsets is generated by joining
Lk−1 with itself.
2. The prune step: Ck
is a superset of Lk
, that is, its members may or may not be
frequent, but all of the frequent k-itemsets are included in Ck.
To reduce the size of Ck
, the Apriori property
is used as follows. Any (k − 1)-itemset that is not frequent cannot be a subset of a
frequent k-itemset. Hence, if any (k − 1)-subset of a candidate k-itemset is not in
Lk−1, then the candidate cannot be frequent either and so can be removed from Ck
.
This subset testing can be done quickly by maintaining a hash tree of all frequent
itemsets.


Generating Association Rules from Frequent Itemsets
Once the frequent itemsets from transactions in a database D have been found, it is
straightforward to generate strong association rules from them (where strong association
rules satisfy both minimum support and minimum confidence). This can be done
using Eq. (6.4) for confidence, which we show again here for completeness:
confidence(A ⇒ B) = P(B|A) =
support count(A ∪B)
support count(A)
.
The conditional probability is expressed in terms of itemset support count, where
support count(A ∪B) is the number of transactions containing the itemsets A ∪B, and
support count(A) is the number of transactions containing the itemset A. Based on this
equation, association rules can be generated as follows:
For each frequent itemset l, generate all nonempty subsets of l.
For every nonempty subset s of l, output the rule “s ⇒ (l − s)” if support count(l)
support count(s) ≥
min conf, where min conf is the minimum confidence threshold.
Because the rules are generated from frequent itemsets, each one automatically satis-
fies the minimum support. Frequent itemsets can be stored ahead of time in hash tables
along with their counts so that they can be accessed quickly

Improving the Efficiency of Apriori

Hash-based technique (hashing itemsets into corresponding buckets): A hash-based
technique can be used to reduce the size of the candidate k-itemsets, Ck
, for k > 1.
For example, when scanning each transaction in the database to generate the frequent
1-itemsets, L1, we can generate all the 2-itemsets for each transaction, hash (i.e., map)
them into the different buckets of a hash table structure, and increase the corresponding
bucket counts (Figure 6.5). A 2-itemset with a corresponding bucket count in the
hash table that is below the support threshold cannot be frequent and thus should
be removed from the candidate set. Such a hash-based technique may substantially
reduce the number of candidate k-itemsets examined (especially when k = 2).
Transaction reduction (reducing the number of transactions scanned in future iterations):
A transaction that does not contain any frequent k-itemsets cannot contain any
frequent (k + 1)-itemsets. Therefore, such a transaction can be marked or removed
from further consideration because subsequent database scans for j-itemsets, where
j > k, will not need to consider such a transaction.
Partitioning (partitioning the data to find candidate itemsets): A partitioning technique
can be used that requires just two database scans to mine the frequent itemsets
(Figure 6.6). It consists of two phases. In phase I, the algorithm divides the transactions
of D into n nonoverlapping partitions. If the minimum relative support
threshold for transactions in D is min sup, then the minimum support count for a
partition is min sup × the number of transactions in that partition. For each partition,

Sampling (mining on a subset of the given data): The basic idea of the sampling
approach is to pick a random sample S of the given data D, and then search for
frequent itemsets in S instead of D.

Dynamic itemset counting (adding candidate itemsets at different points during a
scan): A dynamic itemset counting technique was proposed in which the database
is partitioned into blocks marked by start points. In this variation, new candidate
itemsets can be added at any start point, unlike in Apriori, which determines new
candidate itemsets only immediately before each complete database scan


A Pattern-Growth Approach for Mining Frequent Itemsets

frequent pattern growth, or simply FP-growth, which adopts a divide-and-conquer
strategy as follows. First, it compresses the database representing frequent items into a
frequent pattern tree, or FP-tree, which retains the itemset association information. It
then divides the compressed database into a set of conditional databases (a special kind of
projected database), each associated with one frequent item or “pattern fragment,” and
mines each database separately. For each “pattern fragment,” only its associated data sets
need to be examined. Therefore, this approach may substantially reduce the size of the
data sets to be searched, along with the “growth” of patterns being examined.

Mining Frequent Itemsets Using the Vertical Data Format

Mining Closed and Max Patterns

A recommended methodology is to search for closed frequent itemsets directly during
the mining process. This requires us to prune the search space as soon as we

can identify the case of closed itemsets during mining. Pruning strategies include the
following:
Item merging: If every transaction containing a frequent itemset X also contains an itemset
Y but not any proper superset of Y , then X ∪Y forms a frequent closed itemset and there
is no need to search for any itemset containing X but no Y .

Sub-itemset pruning: If a frequent itemset X is a proper subset of an already found frequent
closed itemset Y and support count(X)=support count(Y), then X and all of X’s
descendants in the set enumeration tree cannot be frequent closed itemsets and thus can
be pruned.

Item skipping: In the depth-first mining of closed itemsets, at each level, there will be
a prefix itemset X associated with a header table and a projected database. If a local
frequent item p has the same support in several header tables at different levels, we can
safely prune p from the header tables at higher levels.

3 Which Patterns Are Interesting?—Pattern Evaluation Methods

From Association Analysis to Correlation Analysis

 a correlation measure can
be used to augment the support–confidence framework for association rules. This leads
to correlation rules of the form
A ⇒ B [support, confidence, correlation]. (6.7)
That is, a correlation rule is measured not only by its support and confidence but also
by the correlation between itemsets A and B

Lift is a simple correlation measure that is given as follows. The occurrence of itemset
A is independent of the occurrence of itemset B if P(A ∪B) = P(A)P(B); otherwise,
itemsets A and B are dependent and correlated as events. This definition can easily be
extended to more than two itemsets. The lift between the occurrence of A and B can be
measured by computing
lift(A, B) =
P(A ∪B)
P(A)P(B)
. (6.8)
If the resulting value of Eq. (6.8) is less than 1, then the occurrence of A is negatively
correlated with the occurrence of B, meaning that the occurrence of one likely leads to
the absence of the other one. If the resulting value is greater than 1, then A and B are
positively correlated, meaning that the occurrence of one implies the occurrence of the
other. If the resulting value is equal to 1, then A and B are independent and there is no
correlation between them.

The second correlation measure is the χ2 measure.  To compute the χ2 value, we take the squared difference
between the observed and expected value for a slot (A and B pair) in the contingency
table, divided by the expected value. This amount is summed for all slots of the
contingency table.

A Comparison of Pattern Evaluation Measures
The above discussion shows that instead of using the simple support–confidence framework
to evaluate frequent patterns, other measures, such as lift and χ
2
, often disclose
more intrinsic pattern relationships. How effective are these measures? Should we also
consider other alternatives?

Four more measures: all confidence, max confidence, Kulczynski, and cosine.


Given two itemsets, A and B, the all confidence measure of A and B is defined as
all conf(A,B) =
sup(A ∪B)
max{sup(A),sup(B)}
= min{P(A|B),P(B|A)}, (6.9)
where max{sup(A), sup(B)} is the maximum support of the itemsets A and B. Thus,
all conf(A,B) is also the minimum confidence of the two association rules related to
A and B, namely, “A ⇒ B” and “B ⇒ A.”
Given two itemsets, A and B, the max confidence measure of A and B is defined as
max conf(A, B) = max{P(A|B),P(B|A)}. (6.10)
The max conf measure is the maximum confidence of the two association rules,
“A ⇒ B” and “B ⇒ A.”
Given two itemsets, A and B, the Kulczynski measure of A and B (abbreviated as
Kulc) is defined as
Kulc(A, B) =
1
2
(P(A|B) + P(B|A)). (6.11)
It was proposed in 1927 by Polish mathematician S. Kulczynski. It can be viewed as an
average of two confidence measures. That is, it is the average of two conditional probabilities:
the probability of itemset B given itemset A, and the probability of itemset A
given itemset B.
Finally, given two itemsets, A and B, the cosine measure of A and B is defined as
cosine(A, B) =
P(A ∪B)
√
P(A) × P(B)
=
sup(A ∪B)
p
sup(A) × sup(B)
=
p
P(A|B) × P(B|A). (6.12)
The cosine measure can be viewed as a harmonized lift measure: The two formulae are
similar except that for cosine, the square root is taken on the product of the probabilities
of A and B. This is an important difference, however, because by taking the square root,
the cosine value is only influenced by the supports of A, B, and A ∪B, and not by the
total number of transactions.
Each of these four measures defined has the following property: Its value is only
influenced by the supports of A, B, and A ∪B, or more exactly, by the conditional probabilities
of P(A|B) and P(B|A), but not by the total number of transactions. Another
common property is that each measure ranges from 0 to 1, and the higher the value, the
closer the relationship between A and B.
Now, together with lift and χ
2
Thus total six pattern evaluation measures were given so far.

In summary, the use of only support and confidence measures to mine associations
may generate a large number of rules, many of which can be uninteresting to
users. Instead,  the support–confidence framework augmented with a pattern interestingness
measure,  helps focus the mining toward rules with strong pattern
relationships. The added measure substantially reduces the number of rules generated
and leads to the discovery of more meaningful rules.   Among the four null-invariant measures described,  all confidence,
max confidence, Kulc, and cosine, the authors recommend using Kulc in conjunction with the
imbalance ratio.


Next Chapter: Advanced Patterns - Data Mining
Data Mining - Classification: Basic Concepts
Data Mining - Classification: Advanced Methods





.

Data Cube Technology for Data Mining

1 Data Cube Computation: Preliminary Concepts

Data cubes facilitate the online analytical processing of multidimensional data. “But how
can we compute data cubes in advance, so that they are handy and readily available for
query processing?” This section contrasts full cube materialization (i.e., precomputation)
versus various strategies for partial cube materialization.


In general, there are two basic data structures used for storing cuboids. The implementation of relational OLAP (ROLAP) uses relational tables, whereas multidimensional arrays are used in multidimensional OLAP (MOLAP). Although ROLAP and MOLAP may each explore different cube
computation techniques, some optimization “tricks” can be shared among the different
data representations. The following are general optimization techniques for efficient
computation of data cubes.
Optimization Technique 1: Sorting, hashing, and grouping. Sorting, hashing, and
grouping operations should be applied to the dimension attributes to reorder and
cluster related tuples.


Optimization Technique 2: Simultaneous aggregation and caching of intermediate
results. In cube computation, it is efficient to compute higher-level aggregates from
previously computed lower-level aggregates, rather than from the base fact table

Optimization Technique 3: Aggregation from the smallest child when there exist multiple
child cuboids. When there exist multiple child cuboids, it is usually more
efficient to compute the desired parent (i.e., more generalized) cuboid from the
smallest, previously computed child cuboid

Optimization Technique 4: The Apriori pruning method can be explored to
compute iceberg cubes efficiently. The Apriori property, in the context of data
cubes, states as follows: If a given cell does not satisfy minimum support, then no descendant
of the cell (i.e., more specialized cell) will satisfy minimum support either.

2 Data Cube Computation Methods

Data cube computation is an essential task in data warehouse implementation. The precomputation
of all or part of a data cube can greatly reduce the response time and enhance the performance of online analytical processing. However, such computation is challenging because it may require substantial computational time and storage space.

Multiway Array Aggregation for Full Cube Computation

The multiway array aggregation (or simply MultiWay) method computes a full data
cube by using a multidimensional array as its basic data structure. It is a typical MOLAP
approach that uses direct array addressing, where dimension values are accessed via the
position or index of their corresponding array locations.

BUC: Computing Iceberg Cubes from the Apex Cuboid Downward

BUC is an algorithm for the computation of sparse and iceberg cubes. Unlike MultiWay,
BUC constructs the cube from the apex cuboid toward the base cuboid. This allows BUC
to share data partitioning costs. This processing order also allows BUC to prune during
construction, using the Apriori property.


Star-Cubing: Computing Iceberg Cubes Using a Dynamic Star-Tree Structure

Star-Cubing algorithm for computing iceberg cubes.
Star-Cubing combines the strengths of the other methods we have studied up to this
point. It integrates top-down and bottom-up cube computation and explores both
multidimensional aggregation (similar to MultiWay) and Apriori-like pruning (similar
to BUC). It operates from a data structure called a star-tree, which performs lossless
data compression, thereby reducing the computation time and memory requirements

Precomputing Shell Fragments for Fast High-Dimensional OLAP

Recall the reason that we are interested in precomputing data cubes: Data cubes facilitate
fast OLAP in a multidimensional data space. However, a full data cube of high
dimensionality needs massive storage space and unrealistic computation time. Iceberg
cubes provide a more feasible alternative, as we have seen, wherein the iceberg condition
is used to specify the computation of only a subset of the full cube’s cells.
However, although an iceberg cube is smaller and requires less computation time than
its corresponding full cube, it is not an ultimate solution.

3 Processing Advanced Kinds of Queries by Exploring Cube Technology

Methods for effective processing of advanced kinds of queries.

Sampling Cubes: OLAP-Based Mining
on Sampling Data
When collecting data, we often collect only a subset of the data we would ideally like
to gather. In statistics, this is known as collecting a sample of the data population.

Sampling Cube Framework
The sampling cube is a data cube structure that stores the sample data and their multidimensional
aggregates. It supports OLAP on sample data. It calculates confidence intervals
as a quality measure for any multidimensional query. Given a sample data relation
(i.e., base cuboid) R, the sampling cube CR typically co


The best way to solve the small sample size problem is to get more data. Fortunately,
there is usually an abundance of additional data available in the cube. The data do not
match the query cell exactly; however, we can consider data from cells that are “close
by.” There are two ways to incorporate such data to enhance the reliability of the query
answer: (1) intracuboid query expansion, where we consider nearby cells within the same
cuboid, and (2) intercuboid query expansion, where we consider more general versions
(from parent cuboids) of the query cell.

Ranking Cubes: Efficient Computation of Top-k Queries

Ranking Cube contributes to the efficient processing of top-k queries. Instead of returning a large set of indiscriminative answers to a query, a top-k
query (or ranking query) returns only the best k results according to a user-specified
preference.
The results are returned in ranked order so that the best is at the top. The userspecified
preference generally consists of two components: a selection condition and
a ranking function. Top-k queries are common in many applications like searching
web databases, k-nearest-neighbor searches with approximate matches, and similarity
queries in multimedia databases.

4 Multidimensional Data Analysis in Cube Space

Prediction Cubes: Prediction Mining in Cube Space

Recently, researchers have turned their attention toward multidimensional data mining to uncover knowledge at varying dimensional combinations and granularities. Such mining is also known as exploratory multidimensional data mining and online analytical data mining (OLAM).

There are at least four ways in which OLAP-style analysis can be fused with data
mining techniques:
1. Use cube space to define the data space for mining. Each region in cube space represents
a subset of data over which we wish to find interesting patterns. Cube space
is defined by a set of expert-designed, informative dimension hierarchies, not just
arbitrary subsets of data. Therefore, the use of cube space makes the data space both
meaningful and tractable.
2. Use OLAP queries to generate features and targets for mining. The features and even
the targets (that we wish to learn to predict) can sometimes be naturally defined as
OLAP aggregate queries over regions in cube space.
3. Use data mining models as building blocks in a multistep mining process. Multidimensional
data mining in cube space may consist of multiple steps, where data mining
models can be viewed as building blocks that are used to describe the behavior of
interesting data sets, rather than the end results.
4. Use data cube computation techniques to speed up repeated model construction. Multidimensional
data mining in cube space may require building a model for each
candidate data space, which is usually too expensive to be feasible. However, by carefully
sharing computation across model construction for different candidates based
on data cube computation techniques, efficient mining is achievable.

Multifeature cubes
enable more in-depth analysis. They can compute more complex queries of which the
measures depend on groupings of multiple aggregates at varying granularity levels. The
queries posed can be much more elaborate and task-specific than traditional queries,
as we shall illustrate in the next examples. Many complex data mining queries can be
answered by multifeature cubes without significant increase in computational cost, in
comparison to cube computation for simple queries with traditional data cubes.


Exception-Based, Discovery-Driven Cube Space Exploration

A discovery-driven approach to exploring cube space.

Precomputed measures indicating data exceptions are used to guide the user in the data
analysis process, at all aggregation levels. We hereafter refer to these measures as exception
indicators. Intuitively, an exception is a data cube cell value that is significantly
different from the value anticipated, based on a statistical model. The model considers
variations and patterns in the measure value across all the dimensions to which a cell
belongs. For example, if the analysis of item-sales data reveals an increase in sales in
December in comparison to all other months, this may seem like an exception in the
time dimension. However, it is not an exception if the item dimension is considered,
since there is a similar increase in sales for other items during December.
The model considers exceptions hidden at all aggregated group-by’s of a data cube.
Visual cues, such as background color, are used to reflect each cell’s degree of exception,
based on the precomputed exception indicators. Efficient algorithms have been proposed
for cube construction


Next Chapter: Mining Frequent Patterns, Associations, and Correlations: Basic Concepts and Methods
Advanced Patterns - Data Mining
Data Mining - Classification: Basic Concepts
Data Mining - Classification: Advanced Methods


Excerpts from the Book

Data Mining Concepts and Techniques

Third Edition
Jiawei Han
University of Illinois at Urbana–Champaign
Micheline Kamber, Jian Pei
Simon Fraser University

Data Warehousing and Online Analytical Processing - Chapter of Data Mining

1 Data Warehouse: Basic Concepts

What Is a Data Warehouse?
Data warehousing provides architectures and tools for business executives to systematically
organize, understand, and use their data to make strategic decisions.

According to William H. Inmon, a leading architect in the construction of data
warehouse systems, “A data warehouse is a subject-oriented, integrated, time-variant,
and nonvolatile collection of data in support of management’s decision making process”
. This short but comprehensive definition presents the major features of
a data warehouse. The four keywords—subject-oriented, integrated, time-variant, and
nonvolatile—distinguish data warehouses from other data repository systems, such as
relational database systems, transaction processing systems, and file systems.

Differences between Operational Database Systems
and Data Warehouses


The major distinguishing features of OLTP and OLAP:
Users and system orientation: An OLTP system is customer-oriented and is used
for transaction and query processing by clerks, clients, and information technology
professionals. An OLAP system is market-oriented and is used for data analysis by
knowledge workers, including managers, executives, and analysts.
Data contents: An OLTP system manages current data that, typically, are too detailed
to be easily used for decision making. An OLAP system manages large amounts of
historic data, provides facilities for summarization and aggregation, and stores and
manages information at different levels of granularity. These features make the data
easier to use for informed decision making.

Database design: An OLTP system usually adopts an entity-relationship (ER) data
model and an application-oriented database design. An OLAP system typically
adopts either a star or a snowflake model  and a subject-oriented
database design.
View: An OLTP system focuses mainly on the current data within an enterprise or
department, without referring to historic data or data in different organizations. In
contrast, an OLAP system often spans multiple versions of a database schema, due to
the evolutionary process of an organization. OLAP systems also deal with information
that originates from different organizations, integrating information from many
data stores. Because of their huge volume, OLAP data are stored on multiple storage
media.
Access patterns: The access patterns of an OLTP system consist mainly of short,
atomic transactions. Such a system requires concurrency control and recovery mechanisms.
However, accesses to OLAP systems are mostly read-only operations (because
most data warehouses store historic rather than up-to-date information), although
many could be complex queries.

Data Warehousing: A Multitiered Architecture
Data warehouses often adopt a three-tier architecture,

1. The bottom tier is a warehouse database server that is almost always a relational
database system.
2. The middle tier is an OLAP server that is typically implemented using either (1) a
relational OLAP (ROLAP) model (i.e., an extended relational DBMS that maps operations
on multidimensional data to standard relational operations); or (2) a multidimensional
OLAP (MOLAP) model (i.e., a special-purpose server that directly
implements multidimensional data and operations).
3. The top tier is a front-end client layer, which contains query and reporting tools,
analysis tools, and/or data mining tools (e.g., trend analysis, prediction, and so on).


Data Warehouse Models: Enterprise Warehouse,
Data Mart, and Virtual Warehouse
From the architecture point of view, there are three data warehouse models: the
enterprise warehouse, the data mart, and the virtual warehouse.
Enterprise warehouse: An enterprise warehouse collects all of the information about
subjects spanning the entire organization. It provides corporate-wide data integration,
usually from one or more operational systems or external information
providers, and is cross-functional in scope. It typically contains detailed data as
well as summarized data, and can range in size from a few gigabytes to hundreds
of gigabytes, terabytes, or beyond. An enterprise data warehouse may be implemented
on traditional mainframes, computer superservers, or parallel architecture
platforms. It requires extensive business modeling and may take years to design
and build.
Data mart: A data mart contains a subset of corporate-wide data that is of value to a
specific group of users. The scope is confined to specific selected subjects. For example,
a marketing data mart may confine its subjects to customer, item, and sales. The
data contained in data marts tend to be summarized.
Data marts are usually implemented on low-cost departmental servers that are
Unix/Linux or Windows based. The implementation cycle of a data mart is more
likely to be measured in weeks rather than months or years. However, it may
involve complex integration in the long run if its design and planning were not
enterprise-wide.
Depending on the source of data, data marts can be categorized as independent
or dependent. Independent data marts are sourced from data captured from one or
more operational systems or external information providers, or from data generated
locally within a particular department or geographic area. Dependent data marts are
sourced directly from enterprise data warehouses.
Virtual warehouse: A virtual warehouse is a set of views over operational databases.
For efficient query processing, only some of the possible summary views may be
materialized.

Extraction, Transformation, and Loading
Data warehouse systems use back-end tools and utilities to populate and refresh their
data. These tools and utilities include the following functions:
Data extraction, which typically gathers data from multiple, heterogeneous, and
external sources.
Data cleaning, which detects errors in the data and rectifies them when possible.
Data transformation, which converts data from legacy or host format to warehouse
format.
Load, which sorts, summarizes, consolidates, computes views, checks integrity, and
builds indices and partitions.
Refresh, which propagates the updates from the data sources to the warehouse.
Besides cleaning, loading, refreshing, and metadata definition tools, data warehouse
systems usually provide a good set of data warehouse management tools.

Metadata Repository
Metadata are data about data. When used in a data warehouse, metadata are the data
that define warehouse objects.

2 Data Warehouse Modeling: Data Cube and OLAP

Data warehouses and OLAP tools are based on a multidimensional data model. This
model views data in the form of a data cube.

Data Cube: A Multidimensional Data Model
“What is a data cube?” A data cube allows data to be modeled and viewed in multiple
dimensions. It is defined by dimensions and facts.
In general terms, dimensions are the perspectives or entities with respect to which
an organization wants to keep records. . Each dimension may have a table associated with it, called a dimension
table, which further describes the dimension.

A multidimensional data model is typically organized around a central theme, such
as sales. This theme is represented by a fact table. Facts are numeric measures. Think of
them as the quantities by which we want to analyze relationships between dimensions

Although we usually think of cubes as 3-D geometric structures, in data warehousing
the data cube is n-dimensional.

In the data
warehousing research literature, a data cuboid can be generated for
each of the possible subsets of the given dimensions. From the all possible cuboids, a lattice of
cuboids, each showing the data at a different level of summarization can be visualized. The
lattice of cuboids is then referred to as a data cube.

The cuboid that holds the lowest level of summarization is called the base cuboid.
. The 0-D cuboid, which holds the highest level
of summarization, is called the apex cuboid. The apex cuboid is typically denoted
by all.

Stars, Snowflakes, and Fact Constellations: Schemas for
Multidimensional Data Models
The entity-relationship data model is commonly used in the design of relational
databases, where a database schema consists of a set of entities and the relationships
between them.

A data warehouse, however, requires a concise, subject-oriented schema that facilitates
online data analysis.
The most popular data model for a data warehouse is a multidimensional model,
which can exist in the form of a star schema, a snowflake schema, or a fact constellation
schema

Dimensions: The Role of Concept Hierarchies
A concept hierarchy defines a sequence of mappings from a set of low-level concepts
to higher-level, more general concepts.

 Measures: Their Categorization and Computation

 A data cube measure is a numeric function that can be evaluated
at each point in the data cube space. A measure value is computed for a given point by
aggregating the data corresponding to the respective dimension–value pairs defining the
given point. Measures can be organized into three categories—distributive, algebraic, and holistic—based
on the kind of aggregate functions used.

Distributive: An aggregate function is distributive if it can be computed in a distributed
manner as follows. Suppose the data are partitioned into n sets. We apply the function
to each partition, resulting in n aggregate values. If the result derived by applying
the function to the n aggregate values is the same as that derived by applying the function
to the entire data set (without partitioning), the function can be computed in a
distributed manner

Algebraic: An aggregate function is algebraic if it can be computed by an algebraic function
with M arguments (where M is a bounded positive integer), each of which
is obtained by applying a distributive aggregate function.

Holistic: An aggregate function is holistic if there is no constant bound on the storage
size needed to describe a subaggregate

Most large data cube applications require efficient computation of distributive and
algebraic measures. Many efficient techniques for this exist.

Typical OLAP Operations

Roll-up
Drill-down
Slice and dice
Pivot

 A Starnet Query Model for Querying
Multidimensional Databases
The querying of multidimensional databases can be based on a starnet model, which
consists of radial lines emanating from a central point, where each line represents a
concept hierarchy for a dimension. Each abstraction level in the hierarchy is called a
footprint. These represent the granularities available for use by OLAP operations such
as drill-down and roll-up.

.3 Data Warehouse Design and Usage


 A Business Analysis Framework for Data
Warehouse Design


To design an effective data warehouse we need to understand and analyze business
needs and construct a business analysis framework. The construction of a large
and complex information system can be viewed as the construction of a large and
complex building, for which the owner, architect, and builder have different views.
These views are combined to form a complex framework that represents the top-down,
business-driven, or owner’s perspective, as well as the bottom-up, builder-driven, or
implementor’s view of the information system.
Four different views regarding a data warehouse design must be considered: the topdown
view, the data source view, the data warehouse view, and the business query view.

Data Warehouse Design Process
Let’s look at various approaches to the data warehouse design process and the steps
involved.
A data warehouse can be built using a top-down approach, a bottom-up approach,
or a combination of both. The top-down approach starts with overall design and planning.
It is useful in cases where the technology is mature and well known, and where
the business problems that must be solved are clear and well understood. The bottomup
approach starts with experiments and prototypes. This is useful in the early stage
of business modeling and technology development.

In general, the warehouse design process consists of the following steps:

1. Choose a business process to model (e.g., orders, invoices, shipments, inventory,
account administration, sales, or the general ledger). If the business process is organizational
and involves multiple complex object collections, a data warehouse model
should be followed. However, if the process is departmental and focuses on the
analysis of one kind of business process, a data mart model should be chosen.
2. Choose the business process grain, which is the fundamental, atomic level of data
to be represented in the fact table for this process (e.g., individual transactions,
individual daily snapshots, and so on).
3. Choose the dimensions that will apply to each fact table record. Typical dimensions
are time, item, customer, supplier, warehouse, transaction type, and status.
4. Choose the measures that will populate each fact table record. Typical measures are
numeric additive quantities like dollars sold and units sold.


Data Warehouse Usage for Information Processing
Data warehouses and data marts are used in a wide range of applications. Business
executives use the data in data warehouses and data marts to perform data analysis
and make strategic decisions. In many firms, data warehouses are used as an integral
part of a plan-execute-assess “closed-loop” feedback system for enterprise management.
Data warehouses are used extensively in banking and financial services, consumer goods
and retail distribution sectors, and controlled manufacturing such as demand-based
production.

There are three kinds of data warehouse applications: information processing, analytical
processing, and data mining.
Information processing supports querying, basic statistical analysis, and reporting
using crosstabs, tables, charts, or graphs. A current trend in data warehouse information
processing is to construct low-cost web-based accessing tools that are then
integrated with web browsers.
Analytical processing supports basic OLAP operations, including slice-and-dice,
drill-down, roll-up, and pivoting. It generally operates on historic data in both summarized
and detailed forms. The major strength of online analytical processing over
information processing is the multidimensional data analysis of data warehouse data.
Data mining supports knowledge discovery by finding hidden patterns and associations,
constructing analytical models, performing classific

Data mining is not confined to the analysis of data stored in data warehouses. It may
analyze data existing at more detailed granularities than the summarized data provided
in a data warehouse. It may also analyze transactional, spatial, textual, and multimedia
data that are difficult to model with current multidimensional database technology. In
this context, data mining covers a broader spectrum than OLAP with respect to data
mining functionality and the complexity of the data handled.

From Online Analytical Processing
to Multidimensional Data Mining
The data mining field has conducted substantial research regarding mining on various
data types, including relational data, data from data warehouses, transaction data,
time-series data, spatial data, text data, and flat files. Multidimensional data mining
(also known as exploratory multidimensional data mining, online analytical mining,
or OLAM) integrates OLAP with data mining to uncover knowledge in multidimensional
databases. Among the many different paradigms and architectures of data mining
systems, multidimensional data mining is particularly important for the following
reasons:

4 Data Warehouse Implementation

Data warehouses contain huge volumes of data. OLAP servers demand that decision
support queries be answered in the order of seconds. Therefore, it is crucial for data
warehouse systems to support highly efficient cube computation techniques, access
methods, and query processing techniques.

Efficient Data Cube Computation: An Overview
At the core of multidimensional data analysis is the efficient computation of aggregations
across many sets of dimensions. In SQL terms, these aggregations are referred to
as group-by’s. Each group-by can be represented by a cuboid, where the set of group-by’s
forms a lattice of cuboids defining a data cube.

The compute cube Operator and the Curse of Dimensionality
One approach to cube computation extends SQL so as to include a compute cube operator.
The compute cube operator computes aggregates over all subsets of the dimensions
specified in the operation. This can require excessive storage space, especially for large
numbers of dimensions.

Partial Materialization: Selected Computation of Cuboids
There are three choices for data cube materialization given a base cuboid:
1. No materialization: Do not precompute any of the “nonbase” cuboids. This leads
to computing expensive multidimensional aggregates on-the-fly, which can be extremely
slow.
2. Full materialization: Precompute all of the cuboids. The resulting lattice of computed
cuboids is referred to as the full cube. This choice typically requires huge
amounts of memory space in order to store all of the precomputed cuboids.
3. Partial materialization: Selectively compute a proper subset of the whole set of possible
cuboids. Alternatively, we may compute a subset of the cube, which contains
only those cells that satisfy some user-specified criterion, such as where the tuple
count of each cell is above some threshold. We will use the term subcube to refer to
the latter case, where only some of the cells may be precomputed for various cuboids.
Partial materialization represents an interesting trade-off between storage space and
response time.

Indexing OLAP Data: Bitmap Index and Join Index

To facilitate efficient data accessing, most data warehouse systems support index structures
and materialized views (using cuboids).

The bitmap indexing method is popular in OLAP products because it allows quick searching in data cubes.

The join indexing method gained popularity from its use in relational database query processing.The star schema model of data warehouses makes join indexing attractive for crosstable
search, because the linkage between a fact table and its corresponding dimension
tables comprises the fact table’s foreign key and the dimension table’s primary key. Join
indexing maintains relationships between attribute values of a dimension (e.g., within
a dimension table) and the corresponding rows in the fact table. Join indices may span
multiple dimensions to form composite join indices. We can use join indices to identify
subcubes that are of interest.

Efficient Processing of OLAP Queries

The purpose of materializing cuboids and constructing OLAP index structures is to speed up query processing in data cubes. Given materialized views, query processing should proceed as follows:

1. Determine which operations should be performed on the available cuboids: This
involves transforming any selection, projection, roll-up (group-by), and drill-down
operations specified in the query into corresponding SQL and/or OLAP operations.
For example, slicing and dicing a data cube may correspond to selection and/or
projection operations on a materialized cuboid.

2. Determine to which materialized cuboid(s) the relevant operations should be
applied: This involves identifying all of the materialized cuboids that may potentially
be used to answer the query, pruning the set using knowledge of “dominance”
relationships among the cuboids, estimating the costs of using the remaining
materialized cuboids, and selecting the cuboid with the least cost.



OLAP Server Architectures: ROLAP versus MOLAP versus HOLAP
Logically, OLAP servers present business users with multidimensional data from data
warehouses or data marts, without concerns regarding how or where the data are stored.
However, the physical architecture and implementation of OLAP servers must consider
data storage issues. Implementations of a warehouse server for OLAP processing include
the following:

Relational OLAP (ROLAP) servers: These are the intermediate servers that stand in
between a relational back-end server and client front-end tools. They use a relational
or extended-relational DBMS to store and manage warehouse data, and OLAP
middleware to support missing pieces. ROLAP servers include optimization for
each DBMS back end, implementation of aggregation navigation logic, and additional
tools and services. ROLAP technology tends to have greater scalability than
MOLAP technology. The DSS server of Microstrategy, for example, adopts the
ROLAP approach.

Multidimensional OLAP (MOLAP) servers: These servers support multidimensional
data views through array-based multidimensional storage engines. They map multidimensional
views directly to data cube array structures. The advantage of using a
data cube is that it allows fast indexing to precomputed summarized data. Notice
that with multidimensional data stores, the storage utilization may be low if the data
set is sparse. In such cases, sparse matrix compression techniques should be explored

Many MOLAP servers adopt a two-level storage representation to handle dense
and sparse data sets: Denser subcubes are identified and stored as array structures,
whereas sparse subcubes employ compression technology for efficient storage
utilization.

Hybrid OLAP (HOLAP) servers: The hybrid OLAP approach combines ROLAP and
MOLAP technology, benefiting from the greater scalability of ROLAP and the faster
computation of MOLAP. For example, a HOLAP server may allow large volumes
of detailed data to be stored in a relational database, while aggregations are kept in
a separate MOLAP store. The Microsoft SQL Server 2000 supports a hybrid OLAP
server.

Specialized SQL servers: To meet the growing demand of OLAP processing in relational
databases, some database system vendors implement specialized SQL servers
that provide advanced query language and query processing support SQL queries over star and snowflake schemas in read only environment

5. Data Generalization by Attribute-Oriented Induction

 In general, data generalization summarizes data by replacing relatively low-level
values (e.g., numeric values for an attribute age) with higher-level concepts (e.g., young,
middle-aged, and senior), or by reducing the number of dimensions to summarize data
in concept space involving fewer dimensions (e.g., removing birth date and telephone
number when summarizing the behavior of a group of students). Given the large amount
of data stored in databases, it is useful to be able to describe concepts in concise and succinct
terms at generalized (rather than low) levels of abstraction. Allowing data sets to
be generalized at multiple levels of abstraction facilitates users in examining the general
behavior of the data

concept description, which is a form of data generalization.
A concept typically refers to a data collection such as frequent buyers, graduate
students, and so on. As a data mining task, concept description is not a simple
enumeration of the data. Instead, concept description generates descriptions for data
characterization and comparison. It is sometimes called class description when the concept
to be described refers to a class of objects. Characterization provides a concise and
succinct summarization of the given data collection, while concept or class comparison
(also known as discrimination) provides descriptions comparing two or more data
collections

Attribute-Oriented Induction for Data Characterization
The attribute-oriented induction (AOI) approach to concept description was first proposed
in 1989, a few years before the introduction of the data cube approach. The data
cube approach is essentially based on materialized views of the data, which typically
have been precomputed in a data warehouse.

The general idea of attribute-oriented induction is to first collect the task-relevant
data using a database query and then perform generalization based on the examination
of the number of each attribute’s distinct values in the relevant data set. The generalization
is performed by either attribute removal or attribute generalization

Efficient Implementation of Attribute-Oriented Induction


 Attribute-Oriented Induction for Class Comparisons

“How is class comparison performed?” In general, the procedure is as follows:
1. Data collection: The set of relevant data in the database is collected by query processing
and is partitioned respectively into a target class and one or a set of contrasting
classes.
2. Dimension relevance analysis: If there are many dimensions, then dimension relevance
analysis should be performed on these classes to select only the highly relevant
dimensions for further analysis. Correlation or entropy-based measures can be used
for this step (Chapter 3).
3. Synchronous generalization: Generalization is performed on the target class to the
level controlled by a user- or expert-specified dimension threshold, which results in
a prime target class relation. The concepts in the contrasting class(es) are generalized
to the same level as those in the prime target class relation, forming the prime
contrasting class(es) relation.
4. Presentation of the derived comparison: The resulting class comparison description
can be visualized in the form of tables, graphs, and rules. This presentation usually
includes a “contrasting” measure such as count% (percentage count) that reflects the
comparison between the target and contrasting classes. The user can adjust the comparison
description by applying drill-down, roll-up, and other OLAP operations to
the target and contrasting classes, as desired.


Next Chapter: Data Cube Technologies for Data Mining
Mining Frequent Patterns, Associations, and Correlations: Basic Concepts and Methods
Advanced Patterns - Data Mining
Data Mining - Classification: Basic Concepts
Data Mining - Classification: Advanced Methods


Data Mining Recent Trends and Research Frontiers

Excerpts from the Book

Data Mining Concepts and Techniques

Third Edition
Jiawei Han
University of Illinois at Urbana–Champaign
Micheline Kamber, Jian Pei
Simon Fraser University

Data Preprocessing for Data Mining

Data Preprocessing

1 Data Preprocessing: An Overview

Data Quality: Why Preprocess the Data?
Data have quality if they satisfy the requirements of the intended use. There are many
factors comprising data quality, including accuracy, completeness, consistency, timeliness,
believability, and interpretability

Major Tasks in Data Preprocessing
In this section, we look at the major steps involved in data preprocessing, namely, data
cleaning, data integration, data reduction, and data transformation.

Data cleaning routines work to “clean” the data by filling in missing values, smoothing
noisy data, identifying or removing outliers, and resolving inconsistencies.

Suppose that you would like to include
data from multiple sources in your analysis. This would involve integrating multiple
databases, data cubes, or files (i.e., data integration).

Data reduction obtains a reduced representation of the data set that is much smaller in
volume, yet produces the same (or almost the same) analytical results. Data reduction
strategies include dimensionality reduction and numerosity reduction.

In dimensionality reduction, data encoding schemes are applied so as to obtain a
reduced or “compressed” representation of the original data. Examples include data
compression techniques (e.g., wavelet transforms and principal components analysis),
attribute subset selection (e.g., removing irrelevant attributes), and attribute construction
(e.g., where a small set of more useful attributes is derived from the original set).
In numerosity reduction, the data are replaced by alternative, smaller representations
using parametric models (e.g., regression or log-linear models) or nonparametric
models (e.g., histograms, clusters, sampling, or data aggregation).

Discretization and concept hierarchy generation are powerful tools for data mining
in that they allow data mining at multiple abstraction levels. Normalization, data
discretization, and concept hierarchy generation are forms of data transformation.
Data transformation operations are additional data preprocessing
procedures that would contribute toward the success of the mining process.

2 Data Cleaning

Missing Values

Alternatives

1. Ignore the tuple: This is usually done when the class label is missing (assuming the
mining task involves classification). This method is not very effective, unless the tuple
contains several attributes with missing values. It is especially poor when the percentage
of missing values per attribute varies considerably. By ignoring the tuple, we do
not make use of the remaining attributes’ values in the tuple. Such data could have
been useful to the task at hand.
2. Fill in the missing value manually: In general, this approach is time consuming and
may not be feasible given a large data set with many missing values.
3. Use a global constant to fill in the missing value: Replace all missing attribute values
by the same constant such as a label like “Unknown” or −∞. If missing values are
replaced by, say, “Unknown,” then the mining program may mistakenly think that
they form an interesting concept, since they all have a value in common—that of
“Unknown.” Hence, although this method is simple, it is not foolproof.
4. Use a measure of central tendency for the attribute (e.g., the mean or median) to
fill in the missing value: For normal (symmetric) data distributions,
the mean can be used, while skewed data distribution should employ
the median.
5. Use the attribute mean or median for all samples belonging to the same class as
the given tuple: For example, if classifying customers according to credit risk, we
may replace the missing value with the mean income value for customers in the same
credit risk category as that of the given tuple. If the data distribution for a given class
is skewed, the median value is a better choice.
6. Use the most probable value to fill in the missing value: This may be determined
with regression, inference-based tools using a Bayesian formalism, or decision
induction. For example, using the other customer attributes in your data set, you
may construct a decision tree to predict the missing values for income.

Noisy Data
“What is noise?” Noise is a random error or variance in a measured variable

Data smoothing techniques.
Binning: Binning methods smooth a sorted data value by consulting its “neighborhood,”
that is, the values around it. The sorted values are distributed into a number
of “buckets,” or bins.

Similarly, smoothing by bin medians can be employed, in which each bin value
is replaced by the bin median. In smoothing by bin boundaries, the minimum and
maximum values in a given bin are identified as the bin boundaries

Regression: Data smoothing can also be done by regression, a technique that conforms
data values to a function. Linear regression involves finding the “best” line to
fit two attributes (or variables) so that one attribute can be used to predict the other.


Outlier analysis: Outliers may be detected by clustering, for example, where similar
values are organized into groups, or “clusters.” Intuitively, values that fall outside of
the set of clusters may be considered outliers.



Data Cleaning as a Process

The first step in data cleaning as a process is discrepancy detection. Discrepancies can
be caused by several factors, including poorly designed data entry forms that have many
optional fields, human error in data entry, deliberate errors (e.g., respondents not wanting
to divulge information about themselves), and data decay (e.g., outdated addresses).

There are a number of different commercial tools that can aid in the discrepancy
detection step. Data scrubbing tools use simple domain knowledge (e.g., knowledge
of postal addresses and spell-checking) to detect errors and make corrections in the
data. These tools rely on parsing and fuzzy matching techniques when cleaning data
from multiple sources. Data auditing tools find discrepancies by analyzing the data to
discover rules and relationships, and detecting data that violate such conditions. They
are variants of data mining tools.

3 Data Integration

Data mining often requires data integration—the merging of data from multiple data
stores.

Entity Identification Problem
How can equivalent real-world entities from multiple
data sources be matched up? This is referred to as the entity identification problem.
When matching attributes from one database to another during integration, special
attention must be paid to the structure of the data. This is to ensure that any attribute
functional dependencies and referential constraints in the source system match those in
the target system.

Redundancy and Correlation Analysis
Redundancy is another important issue in data integration. An attribute (such as annual
revenue, for instance) may be redundant if it can be “derived” from another attribute
or set of attributes. Inconsistencies in attribute or dimension naming can also cause
redundancies in the resulting data set.
Some redundancies can be detected by correlation analysis.

Tuple Duplication
In addition to detecting redundancies between attributes, duplication should also be
detected at the tuple level (e.g., where there are two or more identical tuples for a given
unique data entry case).

Data Value Conflict Detection and Resolution
Data integration also involves the detection and resolution of data value conflicts. For
example, for the same real-world entity, attribute values from different sources may differ.

4 Data Reduction

Dimensionality reduction is the process of reducing the number of random variables
or attributes under consideration.

Numerosity reduction techniques replace the original data volume by alternative,
smaller forms of data representation. These techniques may be parametric or nonparametric

In data compression, transformations are applied so as to obtain a reduced or “compressed”
representation of the original data.

Wavelet Transforms
The discrete wavelet transform (DWT) is a linear signal processing technique that,
when applied to a data vector X, transforms it to a numerically different vector, X
0, of wavelet coefficients. The two vectors are of the same length.

Principal Components Analysis
PCA “combines” the essence of all attributes by creating an alternative,
smaller set of variables. The initial data can then be converted into this smaller
set through projection process. PCA often reveals relationships that were not previously suspected and thereby
allows interpretations that would not ordinarily result.

The components are sorted in decreasing order of “significance,” the data size
can be reduced by eliminating the weaker components, that is, those with low variance.
Using the strongest principal components, it should be possible to reconstruct
a good approximation of the original data.

Attribute Subset Selection

Attribute subset selection reduces the data set size by removing irrelevant or
redundant attributes (or dimensions). The goal of attribute subset selection is to find
a minimum set of attributes such that the resulting probability distribution of the data
classes is as close as possible to the original distribution obtained using all attributes.

Regression and Log-Linear Models: Parametric Data Reduction
Regression and log-linear models can be used to approximate the given data.

Histograms
Histograms use binning to approximate data distributions and are a popular form
of data reduction

Clustering

In data reduction, the cluster representations of the data are used to replace the actual
data

Sampling
Sampling can be used as a data reduction technique because it allows a large data set to
be represented by a much smaller random data sample (or subset).

Data Cube Aggregation

Example description: Data cubes store  for multidimensional analysis of sales data with respect to annual sales per item type
for each branch of a company. Each cell holds an aggregate data value, corresponding
to the data point in multidimensional space. (For readability, only some cell values are
shown.) Concept hierarchies may exist for each attribute, allowing the analysis of data
at multiple abstraction levels. For example, a hierarchy for branch could allow branches
to be grouped into regions, based on their address. Data cubes provide fast access to
precomputed, summarized data, thereby benefiting online analytical processing as well
as data mining.
The cube created at the lowest abstraction level is referred to as the base cuboid. The
base cuboid should correspond to an individual entity of interest such as sales or customer.
In other words, the lowest level should be usable, or useful for the analysis. A cube
at the highest level of abstraction is the apex cuboid.

5 Data Transformation and Data Discretization

Data Transformation Strategies Overview
In data transformation, the data are transformed or consolidated into forms appropriate
for mining. Strategies for data transformation include the following:
1. Smoothing, which works to remove noise from the data. Techniques include binning,
regression, and clustering.
2. Attribute construction (or feature construction), where new attributes are constructed
and added from the given set of attributes to help the mining process.
3. Aggregation, where summary or aggregation operations are applied to the data. For
example, the daily sales data may be aggregated so as to compute monthly and annual
total amounts. This step is typically used in constructing a data cube for data analysis
at multiple abstraction levels.
4. Normalization, where the attribute data are scaled so as to fall within a smaller range,
such as −1.0 to 1.0, or 0.0 to 1.0.
5. Discretization, where the raw values of a numeric attribute (e.g., age) are replaced by
interval labels (e.g., 0–10, 11–20, etc.) or conceptual labels (e.g., youth, adult, senior).
The labels, in turn, can be recursively organized into higher-level concepts, resulting
in a concept hierarchy for the numeric attribute. More than one concept hierarchy can be defined for the same
attribute to accommodate the needs of various users.
6. Concept hierarchy generation for nominal data, where attributes such as street can
be generalized to higher-level concepts, like city or country. Many hierarchies for
nominal attributes are implicit within the database schema and can be automatically
defined at the schema definition level.

Data Transformation by Normalization
To help avoid dependence on the choice of measurement units, the
data should be normalized or standardized. This involves transforming the data to fall
within a smaller or common range such as [−1,1] or [0.0, 1.0]. (The terms standardize
and normalize are used interchangeably in d. Normalizing the data attempts to give all attributes an equal weight

Data normalization methods described in the book  min-max normalization,
z-score normalization, and normalization by decimal scaling.

Discretization by Binning
Binning is a top-down splitting technique based on a specified number of bins.
Binning methods for data smoothing are also
used as discretization methods for data reduction and concept hierarchy generation.

Discretization by Histogram Analysis
Like binning, histogram analysis is an unsupervised discretization technique because it
does not use class information.

Discretization by Cluster, Decision Tree,
and Correlation Analyses
Clustering, decision tree analysis, and correlation analysis can be used for data discretization.

Concept Hierarchy Generation for Nominal Data
 Nominal attributes have a finite (but possibly
large) number of distinct values, with no ordering

Four methods for the generation of concept hierarchies for nominal data,

1. Specification of a partial ordering of attributes explicitly at the schema level by
users or experts: Concept hierarchies for nominal attributes or dimensions typically
involve a group of attributes. A user or expert can easily define a concept hierarchy by
specifying a partial or total ordering of the attributes at the schema level.

2. Specification of a portion of a hierarchy by explicit data grouping: This is essentially
the manual definition of a portion of a concept hierarchy.
On the contrary, we can easily specify explicit groupings for a small portion
of intermediate-level data. For example, after specifying that province and country
form a hierarchy at the schema level, a user could define some intermediate levels
manually, such as “{Alberta, Saskatchewan, Manitoba} ⊂ prairies Canada” and
“{British Columbia, prairies Canada} ⊂ Western Canada.”

3. Specification of a set of attributes, but not of their partial ordering: A user may
specify a set of attributes forming a concept hierarchy, but omit to explicitly state
their partial ordering. The system can then try to automatically generate the attribute
ordering so as to construct a meaningful concept hierarchy.

4. Specification of only a partial set of attributes: The user may have included only a small subset of the

relevant attributes in the hierarchy specification. For example,  the user may specify
only street and city for a location. If data semantics are embedded in the database schema, attributes with tight semantic
connections can be pinned together. In this way, the specification of one attribute
may trigger a whole group of semantically tightly linked attributes to be “dragged in”
to form a complete hierarchy.

Next Chapter
Data Warehousing and Online Analytical Processing - Chapter of Data Mining
Data Cube Technologies for Data Mining
Mining Frequent Patterns, Associations, and Correlations: Basic Concepts and Methods
Advanced Patterns - Data Mining
Data Mining - Classification: Basic Concepts
Data Mining - Classification: Advanced Methods


Data Mining Recent Trends and Research Frontiers

Excerpts from
Data Mining Concepts and Techniques
Third Edition
Jiawei Han
University of Illinois at Urbana–Champaign
Micheline Kamber
Jian Pei
Simon Fraser University

Knowing and Understanding the Dataset for Data Mining

1. Data Objects and Attributes

Data objects are typically described by attributes. Data objects can also be
referred to as samples, examples, instances, data points, or objects. If the data objects are
stored in a database, they are data tuples. That is, the rows of a database correspond to
the data objects, and the columns correspond to the attributes. In this section, we define
attributes and look at the various attribute types.

What Is an Attribute?
An attribute is a data field, representing a characteristic or feature of a data object. The
nouns attribute, dimension, feature, and variable are often used interchangeably in the
literature. The term dimension is commonly used in data warehousing. Machine learning
literature tends to use the term feature, while statisticians prefer the term variable. Data
mining and database professionals commonly use the term attribute

Nominal Attributes
Nominal means “relating to names.” The values of a nominal attribute are symbols or
names of things.

Binary Attributes
A binary attribute is a nominal attribute with only two categories or states: 0 or 1, where
0 typically means that the attribute is absent, and 1 means that it is present. Binary
attributes are referred to as Boolean if the two states correspond to true and false.


Ordinal Attributes
An ordinal attribute is an attribute with possible values that have a meaningful order or
ranking among them, but the magnitude between successive values is not known.

Numeric Attributes
A numeric attribute is quantitative; that is, it is a measurable quantity, represented in
integer or real values. Numeric attributes can be interval-scaled or ratio-scaled.
Interval-Scaled Attributes
Interval-scaled attributes are measured on a scale of equal-size units. The values of
interval-scaled attributes have order and can be positive, 0, or negative. Thus, in addition
to providing a ranking of values, such attributes allow us to compare and quantify the
difference between values.


Ratio-Scaled Attributes
A ratio-scaled attribute is a numeric attribute with an inherent zero-point. That is, if
a measurement is ratio-scaled, we can speak of a value as being a multiple (or ratio)
of another value. In addition, the values are ordered, and we can also compute the
difference between values, as well as the mean, median, and mode.

Classification algorithms developed from the field of machine learning often talk of
attributes as being either discrete or continuous. Each type may be processed differently.
A discrete attribute has a finite or countably infinite set of values, which may or may not
be represented as integers.

If an attribute is not discrete, it is continuous.

2. Basic Statistical Descriptions of Data

 (You learnt these things in basic statistics course long back)

Measuring the Central Tendency: Mean, Median, and Mode
Measuring the Dispersion of Data: Range, Quartiles, Variance,
Standard Deviation, and Interquartile Range


Graphic Displays of Basic Statistical Descriptions of Data
Histograms
Scatter Plots and Data Correlation

3. Data Visualization

How can we convey data to users effectively? Data visualization aims to communicate
data clearly and effectively through graphical representation. Data visualization has been
used extensively in many applications—for example, at work for reporting, managing
business operations, and tracking progress of tasks. More popularly, we can take advantage
of visualization techniques to discover data relationships that are otherwise not
easily observable by looking at the raw data.

Pixel-Oriented Visualization Techniques

Geometric Projection Visualization Techniques

 Icon-Based Visualization Techniques
Hierarchical Visualization Techniques

Visualizing Complex Data and Relations

4. Measuring Data Similarity and Dissimilarity

Data Matrix versus Dissimilarity Matrix
Data matrix (or object-by-attribute structure): This structure stores the n data objects
in the form of a relational table, or n-by-p matrix (n objects ×p attributes):


Dissimilarity matrix (or object-by-object structure): This structure stores a collection
of proximities that are available for all pairs of n objects. It is often represented by an
n-by-n table of d(i, j):


where d(i, j) is the measured dissimilarity or “difference” between objects i and j. In
general, d(i, j) is a non-negative number that is close to 0 when objects i and j are
highly similar or “near” each other, and becomes larger the more they differ.

Proximity Measures for Nominal Attributes
Proximity Measures for Binary Attributes
Dissimilarity of Numeric Data: Minkowski Distance


Distance measures are commonly used for computing
the dissimilarity of objects described by numeric attributes. These measures include the
Euclidean, Manhattan, and Minkowski distances.

Proximity Measures for Ordinal Attributes
The values of an ordinal attribute have a meaningful order or ranking about them,
yet the magnitude between successive values is unknown (Section 2.1.4). An example
includes the sequence small, medium, large for a size attribute.

Dissimilarity for Attributes of Mixed Types


Cosine Similarity
A document can be represented by thousands of attributes, each recording the frequency
of a particular word (such as a keyword) or phrase in the document. Thus, each document
is an object represented by what is called a term-frequency vector. For example, in
Table 2.5, we see that Document1 contains five instances of the word team, while hockey
occurs three times. The word coach is absent from the entire document, as indicated by
a count value of 0. Such data can be highly asymmetric.
Term-frequency vectors are typically very long and sparse (i.e., they have many 0 values).


Cosine similarity is a measure of similarity that can be used to compare documents
or, say, give a ranking of documents with respect to a given vector of query
words. Let x and y be two vectors for comparison.


Next Topic:  Data Preprocessing for Data Mining
Data Warehousing and Online Analytical Processing - Chapter of Data Mining
Data Cube Technologies for Data Mining
Mining Frequent Patterns, Associations, and Correlations: Basic Concepts and Methods

Data Cube Technologies for Data Mining
Mining Frequent Patterns, Associations, and Correlations: Basic Concepts and Methods
Advanced Patterns - Data Mining
Data Mining - Classification: Basic Concepts
Data Mining - Classification: Advanced Methods

Data Mining Recent Trends and Research Frontiers

Excerpts from

Data Mining
Concepts and Techniques
Third Edition
Jiawei Han
University of Illinois at Urbana–Champaign
Micheline Kamber
Jian Pei
Simon Fraser University