Data Mining:

Concepts and
Techniques
(3rd ed.)

— Chapter 1 —

Jiawei Han, Micheline Kamber, and Jian Pei

University of Illinois at Urbana-Champaign &
Simon Fraser University
©2011 Han, Kamber & Pei. All rights reserved.
1
 Chapter 1. Introduction
 Why Data Mining?
 What Is Data Mining?
 A Multi-Dimensional View of Data Mining
 What Kind of Data Can Be Mined?
 What Kinds of Patterns Can Be Mined?
 What Technology Are Used?
 What Kind of Applications Are Targeted?
 Major Issues in Data Mining
 A Brief History of Data Mining and Data Mining Society
 Summary
2
 Why Data Mining?
 The Explosive Growth of Data: from terabytes to petabytes

Data collection and data availability

Automated data collection tools, database systems, Web,
computerized society

Major sources of abundant data

Business: Web, e-commerce, transactions, stocks, …

Science: Remote sensing, bioinformatics, scientific
simulation, …

Society and everyone: news, digital cameras, YouTube
 We are drowning in data, but starving for knowledge!
 “Necessity is the mother of invention”—Data mining—
Automated analysis of massive data sets
3
 Evolution of Sciences
 Before 1600, empirical science
 1600-1950s, theoretical science
 Each discipline has grown a theoretical component. Theoretical models often
motivate experiments and generalize our understanding.
 1950s-1990s, computational science
 Over the last 50 years, most disciplines have grown a third, computational
branch (e.g. empirical, theoretical, and computational ecology, or physics, or
linguistics.)
 Computational Science traditionally meant simulation. It grew out of our
inability to find closed-form solutions for complex mathematical models.
 1990-now, data science
 The flood of data from new scientific instruments and simulations
 The ability to economically store and manage petabytes of data online
 The Internet and computing Grid that makes all these archives universally
accessible
 Scientific info. management, acquisition, organization, query, and visualization
tasks scale almost linearly with data volumes. Data mining is a major new
challenge!
 Jim Gray and Alex Szalay, The World Wide Telescope: An Archetype for Online
Science, Comm. ACM, 45(11): 50-54, Nov. 2002 4
 Evolution of Database
Technology
 1960s:
 Data collection, database creation, IMS and network DBMS
 1970s:
 Relational data model, relational DBMS implementation
 1980s:
 RDBMS, advanced data models (extended-relational, OO, deductive,
etc.)
 Application-oriented DBMS (spatial, scientific, engineering, etc.)
 1990s:
 Data mining, data warehousing, multimedia databases, and Web
databases
 2000s
 Stream data management and mining
 Data mining and its applications
 Web technology (XML, data integration) and global information
systems
5
 Chapter 1. Introduction
 Why Data Mining?
 What Is Data Mining?
 A Multi-Dimensional View of Data Mining
 What Kind of Data Can Be Mined?
 What Kinds of Patterns Can Be Mined?
 What Technology Are Used?
 What Kind of Applications Are Targeted?
 Major Issues in Data Mining
 A Brief History of Data Mining and Data Mining Society
 Summary
6
 What Is Data Mining?

 Data mining (knowledge discovery from data)

 Extraction of interesting (non-trivial, implicit, previously
unknown and potentially useful) patterns or knowledge
from huge amount of data
 Data mining: a misnomer?
 Alternative names
 Knowledge discovery (mining) in databases (KDD),
knowledge extraction, data/pattern analysis, data
archeology, data dredging, information harvesting,
business intelligence, etc.
 Watch out: Is everything “data mining”?
 Simple search and query processing
 (Deductive) expert systems
7
 Knowledge Discovery (KDD) Process
 This is a view from typical
database systems and data
Pattern Evaluation
warehousing communities
 Data mining plays an
essential role in the
knowledge discovery process Data Mining

Task-relevant Data

Data Selection
Warehouse
Data Cleaning

Data Integration

Databases
8
 Example: A Web Mining
Framework

 Web mining usually involves

 Data cleaning
 Data integration from multiple sources
 Warehousing the data
 Data cube construction
 Data selection for data mining
 Data mining
 Presentation of the mining results
 Patterns and knowledge to be used or stored
into knowledge-base

9
Data Mining in Business Intelligence

Increasing potential
to support
business decisions End User
Decisio
n
Making
Data Presentation Business
Analyst
Visualization Techniques
Data Mining Data
Information Discovery Analyst

Data Exploration
Statistical Summary, Querying, and Reporting

Data Preprocessing/Integration, Data Warehouses

DBA
Data Sources
Paper, Files, Web documents, Scientific experiments, Database Systems
10
 Example: Mining vs. Data
Exploration
 Business intelligence view
 Warehouse, data cube, reporting but not much
mining
 Business objects vs. data mining tools
 Supply chain example: tools
 Data presentation
 Exploration

11
 KDD Process: A Typical View from ML
and Statistics

Input Data Data Pre- Data Post-

Processing Mining Processin
g

Data integration Pattern discovery Pattern evaluation

Normalization Association & Pattern selection
correlation
Feature selection Classification Pattern
interpretation
Dimension reduction Clustering
Pattern visualization
Outlier analysis
…………

 This is a view from typical machine learning and statistics communities

12
 Example: Medical Data
Mining

 Health care & medical data mining – often

adopted such a view in statistics and
machine learning
 Preprocessing of the data (including feature
extraction and dimension reduction)
 Classification or/and clustering processes
 Post-processing for presentation

13
 Chapter 1. Introduction
 Why Data Mining?
 What Is Data Mining?
 A Multi-Dimensional View of Data Mining
 What Kind of Data Can Be Mined?
 What Kinds of Patterns Can Be Mined?
 What Technology Are Used?
 What Kind of Applications Are Targeted?
 Major Issues in Data Mining
 A Brief History of Data Mining and Data Mining Society
 Summary
14
 Multi-Dimensional View of Data
Mining
 Data to be mined

Database data (extended-relational, object-oriented,
heterogeneous, legacy), data warehouse, transactional data,
stream, spatiotemporal, time-series, sequence, text and web,
multi-media, graphs & social and information networks
 Knowledge to be mined (or: Data mining functions)

Characterization, discrimination, association, classification,
clustering, trend/deviation, outlier analysis, etc.

Descriptive vs. predictive data mining

Multiple/integrated functions and mining at multiple levels
 Techniques utilized

Data-intensive, data warehouse (OLAP), machine learning,
statistics, pattern recognition, visualization, high-performance,
etc.
 Applications adapted

Retail, telecommunication, banking, fraud analysis, bio-data
mining, stock market analysis, text mining, Web mining, etc.
15
 Data Mining: Concepts and
December 7, 2025 Techniques 16
 Chapter 1. Introduction
 Why Data Mining?
 What Is Data Mining?
 A Multi-Dimensional View of Data Mining
 What Kind of Data Can Be Mined?
 What Kinds of Patterns Can Be Mined?
 What Technology Are Used?
 What Kind of Applications Are Targeted?
 Major Issues in Data Mining
 A Brief History of Data Mining and Data Mining Society
 Summary
17
 Data Mining: On What Kinds of
Data?
 Database-oriented data sets and applications
 Relational database, data warehouse, transactional database
 Advanced data sets and advanced applications
 Data streams and sensor data
 Time-series data, temporal data, sequence data (incl. bio-
sequences)
 Structure data, graphs, social networks and multi-linked data
 Object-relational databases
 Heterogeneous databases and legacy databases
 Spatial data and spatiotemporal data
 Multimedia database
 Text databases
 The World-Wide Web
18
 Chapter 1. Introduction
 Why Data Mining?
 What Is Data Mining?
 A Multi-Dimensional View of Data Mining
 What Kind of Data Can Be Mined?
 What Kinds of Patterns Can Be Mined?
 What Technology Are Used?
 What Kind of Applications Are Targeted?
 Major Issues in Data Mining
 A Brief History of Data Mining and Data Mining Society
 Summary
19
 What Kinds of Patterns Can Be Mined?

 Data mining functionalities.

1. Class/Concept Description: Characterization and
Discrimination
2. Mining Frequent Patterns, Associations, and
Correlations
3. Classification and Regression for Predictive Analysis
4. Cluster Analysis
5. Outlier Analysis
 Data mining functionalities are used to specify the

kinds of patterns to be found in data mining tasks.

 In general, such tasks can be classified into two
categories:
a) descriptive : characterize properties of the data in a
target data set
b) predictive:perform induction on the current data in
order to make predictions.
Data Mining: Concepts and
December 7, 2025 Techniques 20
 Class/Concept Description:
Characterization and Discrimination

 Data entries can be associated with classes or

concepts
 For example, in the AllElectronics store, classes of

items for sale include computers and printers, and

concepts of customers include bigSpenders and
budgetSpenders
 It can be useful to describe individual classes and

concepts in [Link] descriptions of a class

or a concept are called class/concept descriptions
These descriptions can be derived
1. data characterization by summarizing the data of the
class under study (often called the target class) in
general terms.
(2) data discrimination, by comparison of the target
class with one or a set of comparative classes (often
called the contrasting classes),
(3) both data characterization and discrimination.
 data characterization can be presented in various forms.
Examples include pie charts, bar charts, curves,
multidimensional data cubes, and multidimensional tables,
including crosstabs. The resulting descriptions can also be
presented as generalized relations or in rule form (called
characteristic rules).

 Example 1.5 Data characterization. A customer

relationship manager at AllElectronics may order the
following data mining task: Summarize the characteristics
of customers who spend more than $5000 a year at
AllElectronics.

ANS: The result is a general profile of these

customers, such as that they are 40 to 50 years old,
employed, and have excellent credit ratings.
 Data discrimination

Data discrimination is a comparison of the general

features of the target class data objects against the
general features of objects from one or multiple
contrasting classes.
Example 1.6 Data discrimination. A customer
relationship manager at AllElectronics may want to
compare two groups of customers—those who shop for
computer products regularly (e.g., more than twice a
month) and those who rarely shop for such products
(e.g., less than three times a year).
ANS: The resulting description provides a general
comparative profile of these customers, such as that
80% of the customers who frequently purchase
computer products are between 20 and 40 years old
and have a university education, whereas 60% of the
customers who infrequently buy such products are
either seniors or youths, and have no university
degree.
December 7, 2025
Data Mining: Concepts and
Techniques 23
Mining Frequent Patterns, Associations, and
Correlations

 Frequent patterns, as the name suggests, are

patterns that occur frequently in data.
 There are many kinds of frequent patterns

1. frequent itemsets: A frequent itemset typically

refers to a set of items that often appear together in
a transactional data set—for example, milk and
bread

2. frequent subsequences (also known as sequential

patterns):A frequently occurring subsequence, such
as the pattern that customers, tend to purchase first
a laptop, followed by a digital camera, and then a
memory card, is a (frequent) sequential pattern

3. frequent substructures: A substructure can refer

to different structural forms (e.g., graphs, trees, or
lattices) that may be combined with itemsets or
subsequences.
 Example 1.7 Association analysis. Suppose that, as a
marketing manager at AllElectronics, you want to
know which items are frequently purchased together
(i.e., within the same transaction). An example of
such a rule, mined from the AllElectronics
transactional database, is

buys(X, “computer”) ⇒ buys(X, “software”) [support =

1%,confidence = 50%],

where X is a variable representing a customer. A

confidence, or certainty, of 50% means that if a
customer buys a computer, there is a 50% chance
that she will buy software as well. A 1% support
means that 1% of all the transactions under analysis
show that computer and software are purchased
together
  Association rules that contain a single predicate are
referred to as single-dimensional association rules
 Suppose, instead, that we are given the

AllElectronics relational database related to

purchases. A data mining system may find
association rules like
age(X, “20..29”) ∧ income(X, “40K..49K”) ⇒ buys(X,
“laptop”) [support = 2%, confidence = 60%].
 The rule indicates that of the AllElectronics

customers under study, 2% are 20 to 29 years old

with an income of $40,000 to $49,000 and have
purchased a laptop (computer) at AllElectronics
 Note that this is an association involving more than

one attribute or predicate (i.e., age, income, and

buys). There fore it is a multidimensional
association rule.
Data Mining: Concepts and
December 7, 2025 Techniques 26
Classification and Regression for
Predictive Analysis
 Classification is the process of finding a model (or
function) that describes and distinguishes data
classes or concepts.

 The model is used to predict the class label of

objects for which the the class label is unknown

 “How is the derived model presented?” The derived

model may be represented in various forms, such as
classification rules (i.e., IF-THEN rules)

 A decision tree is a flowchart-like tree structure,

where each node denotes a test on an attribute
value, each branch represents an outcome of the
test, and tree leaves represent classes or class
distributions.
A classification model can be
represented in various forms
 classification predicts categorical (discrete,
unordered) labels.
 regression models continuous-valued functions.
That is, regression is used to predict missing or
unavailable numerical data values rather than
(discrete) class labels.
 Cluster Analysis

clustering analyzes data objects without consulting
class labels. In many cases, classlabeled data may
simply not exist at the beginning. Clustering can be
used to generate class labels for a group of data.


The objects are clustered or grouped based on the
principle of maximizing the intraclass similarity and
minimizing the interclass similarity
 Outlier Analysis
 A data set may contain objects that do not comply
with the general behavior or model of the data.
These data objects are outliers.

 Many data mining methods discard outliers as

noise or exceptions.

 However, in some applications (e.g., fraud

detection) the rare events can be more interesting
than the more regularly occurring ones.

 The analysis of outlier data is referred to as outlier

analysis or anomaly mining.
 Major Issues in Data Mining
(1)
 Mining Methodology

Mining various and new kinds of knowledge

Mining knowledge in multi-dimensional space

Data mining: An interdisciplinary effort

Boosting the power of discovery in a networked environment

Handling noise, uncertainty, and incompleteness of data

Pattern evaluation and pattern- or constraint-guided mining
 User Interaction

Interactive mining

Incorporation of background knowledge

Presentation and visualization of data mining results

32
 Major Issues in Data Mining
(2)

 Efficiency and Scalability

 Efficiency and scalability of data mining algorithms
 Parallel, distributed, stream, and incremental mining
methods
 Diversity of data types
 Handling complex types of data
 Mining dynamic, networked, and global data repositories
 Data mining and society
 Social impacts of data mining
 Privacy-preserving data mining
 Invisible data mining

33