صفحه 1:
Data Mining:
oncepts and Techniques
— Slides for Textbook —
— Chapter 1 —
©Jiawei Han and Micheline Kamber
Intelligent Database Systems Research Lab
School of Computing Science
Simon Fraser University, Canada
http://www.cs.sfu.ca
December 24, 2024 Peete see nett
صفحه 2:
Acknowledgements
= This work on this set of slides started with my (Han’s)
tutorial for UCLA Extension course in February 1998
Dr. Hongjun Lu from Hong Kong Univ. of Science and
Technology taught jointly with me a Data Mining
Summer Course in Shanghai, China in July 1998. He
has contributed many excellent slides to it
Some graduate students have contributed many new
slides in the following years. Notable contributors
include Eugene Belchev, Jian Pei, and Osmar R.
Zaiane (now teaching in Univ. of Alberta).
December 24, 2024 Peete see nett
صفحه 3:
CMPT-459-00.3 Course
Schedule
ع يي eats ace رت
ا ا eur ee eerie ia Ree nage 0
eee ence eee Ae ea) 00
۱
الاك عع ee Oe a ee oe ara ع ۰
u
Peon e se tM eee eT
Ree es eR اي ee Mec: ee 0
eeeg ل
ا ee Sere Sen Reco 0
ييف رت ۱
۱
۱
عذال #2 6ارونيعممون! 13 ۳۹
ل ل ل 0
aa ا 00
ess ۱
۷24 ل 02
3, WS:
December 24, 2024 Peete see nett
صفحه 4:
Where to Find the Set of
1 Slides?
= Tutorial sections (MS PowerPoint files):
= http://www.cs.sfu.ca/~han/dmbook
= Other conference presentation slides (.ppt):
"= http://db.cs.sfu.ca/ or http://www.cs.sfu.ca/~han
= Research papers, DBMiner system, and other
related information:
= http://db.cs.sfu.ca/ or http://www.cs.sfu.ca/~han
December 24, 2024 Peete see nett
صفحه 5:
Chapter 1. Introduction
د
= Motivation: Why data mining?
= What is data mining?
= Data Mining: On what kind of data?
= Data mining functionality
= Are all the patterns interesting?
= Classification of data mining systems
= Major issues in data mining
December 24, 2024 Peete see nett
صفحه 6:
Motivation: “Necessity is the
Mother of Invention”
= Data explosion problem
= Automated data collection tools and mature database
technology lead to tremendous amounts of data stored in
databases, data warehouses and other information
repositories
= We are drowning in data, but starving for knowledge!
= Solution: Data warehousing and data mining
* Data warehousing and on-line analytical processing
= Extraction of interesting knowledge (rules, regularities,
patterns, constraints) from data in large databases
December 24, 2024 Peete see nett
صفحه 7:
Evolution of Database
Technology
(See Fig. 1.1)
= 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.) and application-oriented DBMS (spatial,
scientific, engineering, etc.)
= 1990s—2000s:
= Data mining and data warehousing, multimedia databases,
and Web databases
December 24, 2024 Peete see nett
صفحه 8:
What Is Data Mining?
= Data mining (knowledge discovery in databases):
= Extraction of interesting (non-trivial, implicit, previously
unknown and potentially useful) information or patterns
from data in large databases
» رورت رو را ریات عبالأهممعغام
= Data mining: a misnomer?
= Knowledge discovery(mining) in databases (KDD),
knowledge extraction, data/pattern analysis, data
archeology, data dredging, information harvesting,
business intelligence, etc.
= What is not data mining?
= (Deductive) query processing.
= Expert systems or small ML/statistical programs
December 24, 2024 Peete see nett 8
صفحه 9:
Why Data Mining? — Potential
Applications
= Database analysis and decision support
1۱ Rene naa
= target marketing, customer relation management,
market basket analysis, cross selling, market
segmentation
۱ 8
= Forecasting, customer retention, improved
underwriting, quality control, competitive analysis
0 ce eRe etait Rue eye aia
= Other Applications
* Text mining (news group, email, documents) and Web analysis.
Saale uae sae nt)
December 24, 2024 Peete see nett
صفحه 10:
Market Analysis and
Management (1)
57أكلااة36 106 5عع]ناه5 03638 عط مخ عمعطلالا "
= Credit card transactions, loyalty cards, discount coupons,
customer complaint calls, plus (public) lifestyle studies
= Target marketing
= Find clusters of “model” customers who share the same
characteristics: interest, income level, spending habits, etc.
= Determine customer purchasing patterns over time
= Conversion of single to a joint bank account: marriage, etc.
= Cross-market analysis
= Associations/co-relations between product sales
= Prediction based on the association information
December 24, 2024 Peete see nett 10
صفحه 11:
11
Market Analysis and
Management (2)
= Customer profiling
= data mining can tell you what types of customers buy what
products (clustering or classification)
= Identifying customer requirements
= identifying the best products for different customers
= use prediction to find what factors will attract new customers
ات ریات ات مرها
= various multidimensional summary reports
= statistical summary information (data central tendency and
تیان
December 24, 2024 Peete see nett
صفحه 12:
Corporate Analysis and Risk
Management
= Finance planning and asset evaluation
= cash flow analysis and prediction
= contingent claim analysis to evaluate assets
= cross-sectional and time series analysis (financial-ratio,
trend analysis, etc.)
= Resource planning:
= summarize and compare the resources and spending
= Competition:
= monitor competitors and market directions
= group customers into classes and a class-based pricing
procedure
= set pricing strategy in a highly competitive market
December 24, 2024 Peete see nett 12
صفحه 13:
Fraud Detection and
Management (1)
pplications
= widely used in health care, retail, credit card services,
telecommunications (phone card fraud), etc.
= Approach
= use historical data to build models of fraudulent behavior
and use data mining to help identify similar instances
= Examples
= auto insurance: detect a group of people who stage
accidents to collect on insurance
= money laundering: detect suspicious money transactions
(US Treasury's Financial Crimes Enforcement Network)
= medical insurance: detect professional patients and ring
of doctors and ring of references
December 24, 2024 Peete see nett 13
صفحه 14:
Fraud Detection and
Management (2)
etecting inappropriate medical treatment
قط روت رن یتیگ ریا تا و۱۱
in many cases blanket screening tests were requested
(save Australian $1m/yr).
= Detecting telephone fraud
= Telephone call model: destination of the call, duration,
time of day or week. Analyze patterns that deviate from
an expected norm.
= British Telecom identified discrete groups of callers with
frequent intra-group calls, especially mobile phones, and
broke a multimillion dollar fraud.
الت بن
= Analysts estimate that 38% of retail shrink is due to
dishonest employees.
December 24, 2024 Peete see nett 14
صفحه 15:
Other Applications
ports
= IBM Advanced Scout analyzed NBA game statistics (shots
blocked, assists, and fouls) to gain competitive advantage
for New York Knicks and Miami Heat
= Astronomy
= JPL and the Palomar Observatory discovered 22 quasars
with the help of data mining
وت روت زو
= IBM Surf-Aid applies data mining algorithms to Web
access logs for market-related pages to discover
customer preference and behavior pages, analyzing
effectiveness of Web marketing, improving Web site
organization, etc.
December 24, 2024 Peete see nett 15
صفحه 16:
Data Mining: A KDD Process
نی ۱
16
PVCu UT sl
= Data mining: the core
or (۵ 58
iscovery process. Data ين
BE نت تا
۳
22 an
ات نا
الي ا للا
دونو م قل
preter ty
December 24, 2924 Peete see nett
صفحه 17:
Steps of a KDD Process
= Learning the application domain:
«relevant prior knowledge and goals of application
= Creating a target data set: data selection
= Data cleaning and preprocessing: (may take 60% of effort!)
= Data reduction and transformation:
Se Ree tM a sae ی CS
لورت
= Choosing functions of data mining
Se eye ا ا ا elec len
= Choosing the mining algorithm(s)
= Data mining: search for patterns of interest
= Pattern evaluation and knowledge presentation
Se EE ester UC le Res Ue ec a
= Use of discovered knowledge
December 24, 2024 Peete see nett 17
صفحه 18:
Data Mining and Business
و :۱
etc ان
aking
000
Data Presentatio تا
72 2 = PUT
] Te AU
هد نا
عونمم |
ماد
Bee UME CRED اکتا
w meee Cla ا
OLAP, MDA 9
Data Sources
PAper, Files, Information Providers, Database Systems, OLTP
Peete nett
December 24, 2024
صفحه 19:
Architecture of a Typical
Data Mining System
Seen user interface
1 1
۵ ۲6۲۱ا۵ظ
! +
Data mining engine-———
1
Database or
data warehouse
Data clea: es ۵ Filteri
peters
۱ Knowledge-
0
December 24, 2024 Peete hee tt 19
صفحه 20:
Data Mining: On What Kind
of Data?
= Relational databases
= Data warehouses
= Transactional databases
= Advanced DB and information repositories
= Object-oriented and object-relational databases
= Spatial databases
= Time-series data and temporal data
= Text databases and multimedia databases
= Heterogeneous and legacy databases
= WWW
December 24, 2024 Peete see nett 20
صفحه 21:
Data Mining Functionalities
(1)
= Concept description: Characterization and
discrimination
= Generalize, summarize, and contrast data
characteristics, e.g., dry vs. wet regions
= Association (correlation and causality)
= Multi-dimensional vs. single-dimensional association
= age(X, “20..29”) * income(X, “20..29K”) > buys(X,
“PC”) [support = 2%, confidence = 60%]
= contains(T, “computer”) > contains(x, “software”)
]196, 75961
December 24, 2024 Peete see nett 21
صفحه 22:
22
Data Mining Functionalities
(2)
lassification and Prediction
= Finding models (functions) that describe and distinguish
classes or concepts for future prediction
= E.g., classify countries based on climate, or classify cars
based on gas mileage
= Presentation: decision-tree, classification rule, neural network
= Prediction: Predict some unknown or missing numerical
Nelle}
= Cluster analysis
= Class label is unknown: Group data to form new classes, e.g.,
cluster houses to find distribution patterns
= Clustering based on the principle: maximizing the intra-class
similarity and minimizing the interclass similarity
December 24, 2024 Peete see nett
صفحه 23:
Data Mining Functionalities
(3)
= Outlier analysis
= Outlier: a data object that does not comply with the general
عط كه ءمأناق عط 33
It can be considered as noise or exception but is quite useful
in fraud detection, rare events analysis
= Trend and evolution analysis
= Trend and deviation: regression analysis
= Sequential pattern mining, periodicity analysis
= Similarity-based analysis
= Other pattern-directed or statistical analyses
December 24, 2024 Peete ee ert 23
صفحه 24:
Are All the “Discovered”
Patterns Interesting?
data mining system/query may generate thousands of
patterns, not all of them are interesting.
Beech tee aimee cement NAS Ete M ا
= Interestingness measures: A pattern is interesting if it is
easily understood by humans, valid on new or test data with
some degree of certainty, potentially useful, novel, or validates
some hypothesis that a user seeks to confirm
= Objective vs. subjective interestingness measures:
Same Tsetse eC Rett: Ree Coe ese ect aa
010100 ee ee
See tetera ee Renee aR Coa teeta
00000
December 24, 2024 Peete see nett 24
صفحه 25:
Can We Find All and Only
Interesting Patterns?
* Find all the interesting patterns: Completeness
= Can a data mining system find all the interesting patterns?
= Association vs. classification vs. clustering
= Search for only interesting patterns: Optimization
= Can a data mining system find only the interesting
۱01۶ فتووت
= Approaches
* First general all the patterns and then filter out the
۱1 ی رات توت زوا زر
= Generate only the interesting patterns—mining query
optimization
ee ey eles) eee entry 25
صفحه 26:
Data Mining: Confluence of
۳ Multiple Disciplines
9
December 24, 2024 Peete see nett
صفحه 27:
27
Data Mining: Classification
۳ Schemes
= General functionality
= Descriptive data mining
= Predictive data mining
= Different views, different classifications
= Kinds of databases to be mined
= Kinds of knowledge to be discovered
= Kinds of techniques utilized
= Kinds of applications adapted
December 24, 2024 Peete see nett
صفحه 28:
۱۰۹ ۱0۱۱۹۵ و0۱ ۱
Data Mining Classification
۲۳۱۰۰۱۰۰۰ ایا
= Relational, transactional, object-oriented, object-relational,
active, spatial, time-series, text, multi-media,
heterogeneous, legacy, WWW, etc.
= Knowledge to be mined
= Characterization, discrimination, association, classification,
clustering, trend, deviation and outlier analysis, etc.
= Multiple/integrated functions and mining at multiple levels
=" Techniques utilized
= Database-oriented, data warehouse (OLAP), machine
learning, statistics, visualization, neural network, etc.
= Applications adapted
* Retail, telecommunication, banking, fraud analysis, DNA mining,
.ععة ,وتنزاهمة وهامع للا ,ومتمتد طعلالا ,كتدزاهم3 غع6/مهمم عاء0غد
December 24, 2024 Peete see nett 28
صفحه 29:
OLAP Mining: An Integration of
Data Mining and Data
Warehousing
=" Data mining systems, DBMS, Data warehouse
systems coupling
= No coupling, loose-coupling, semi-tight-coupling, tight-coupling
= On-line analytical mining data
= integration of mining and OLAP technologies
= Interactive mining multi-level knowledge
= Necessity of mining knowledge and patterns at different levels
of abstraction by drilling/rolling, pivoting, slicing/dicing, etc.
= Integration of multiple mining functions
= Characterized classification, first clustering and then
association
December 24, 2024 Peete see nett 29
صفحه 30:
Data
Repository,
An OLAM Architecture
lining
qu
OLAM
Engine
Wareho
use
صفحه 31:
Major Issues in Data Mining
(1)
= Mining methodology and user interaction
Mining different kinds of knowledge in databases
Interactive mining of knowledge at multiple levels of
abstraction
Incorporation of background knowledge
Data mining query languages and ad-hoc data mining
Expression and visualization of data mining results
Handling noise and incomplete data
Pattern evaluation: the interestingness problem
= Performance and scalability
Efficiency and scalability of data mining algorithms
Parallel, distributed and incremental mining methods
December 24, 2024 Peete ا 31
صفحه 32:
32
Major Issues in Data Mining (2)
= Issues relating to the diversity of data types
= Handling relational and complex types of data
= Mining information from heterogeneous databases and
global information systems (WWW)
= Issues related to applications and social impacts
= Application of discovered knowledge
" Domain-specific data mining tools
= Intelligent query answering
= Process control and decision making
= Integration of the discovered knowledge with existing
۱ وتات
= Protection of data security, integrity, and privacy
December 24, 2024 Peete see nett
صفحه 33:
Summary
= Data mining: discovering interesting patterns from large amounts
06
= Anatural evolution of database technology, in great demand, with
wide applications
» AKDD process includes data cleaning, data integration, data
selection, transformation, data mining, pattern evaluation, and
knowledge presentation
= Mining can be performed in a variety of information repositories
= Data mining functionalities: characterization, discrimination,
association, classification, clustering, outlier and trend analysis,
etc.
™ Classification of data mining systems
= Major issues in data mining
December 24, 2024 Peete see nett 33
صفحه 34:
A Brief History of Data Mining
Society
= 1989 IJCAI Workshop on Knowledge Discovery in Databases
Piatetsky-Shapiro
* Knowledge Discovery in Databases (G. Piatetsky-Shapiro and W. Frawley,
1991(
= 1991-1994 Workshops on Knowledge Discovery in Databases
* Advances in Knowledge Discovery and Data Mining (U. Fayyad, G. Piatetsky-
Seu meu Miata)
= 1995-1998 International Conferences on Knowledge Discovery
in Databases and Data Mining (KDD'95-98
۱
= 1998 ACM SIGKDD, SIGKDD'1999-2001 conferences, and
SIGKDD Explorations
= More conferences on data mining
SOP MU a ل
December 24, 2024 Data Mining: Concepts and Techniques 34
صفحه 35:
Where to Find References?
= Data mining and KDD (SIGKDD member CDROM):
= Conference proceedings: KDD, and others, such as PKDD, PAKDD, etc.
Sas Pe MarR R title apere niin
= Database field (SIGMOD member CD ROM):
= Conference proceedings: ACM-SIGMOD, ACM-PODS, VLDB, ICDE,
EDBT, DASFAA
= Journals: ACM-TODS, J. ACM, IEEE-TKDE, JIS, etc.
= Aland Machine Learning:
= Conference proceedings: Machine learning, AAAI, IJCAI, etc.
۱
۰۱۱
= Conference proceedings: Joint Stat. Meeting, etc.
Se Or eee Gut ا
= Visualization:
* Conference proceedings: CHI, etc.
۱ یر Rectal ieciae cc] al ecmecic
December 24, 2024 Peete see nett 35
صفحه 36:
References
SOM ا Cee
FONE ee GC ea RR CCU er eC
See CCU eC ec CR eee Se Ra ome
۱
Se CeCe eee cat Rn tele
۱ EL Tne
SECM Ac Sec RNC RU en RC RR
Pere ee eae cn URN ROR NC cree ree
ee تا
SRM AEC eo RNs a ا Soe
EN ago
December 24, 2024 Peete see nett 36
صفحه 37:
http://www.cs.sfu.ca/
93 ~han
صفحه 38:
CMPT-843 Course
Arrangement
Para ee Be ercetece Catia
SP BCR ا
۱۳۳ ear ets alee cee ce Cem og Ue Tela
ا 0
00 runt Smee cece Re ee cc Ya
See ene ELLs
Seno gee et eee ee ES
00 Hetil
Deadline for the selection of your work in the semester:
۱ ect ea Ree aes
Sees ا est aca ce Reco
Sees et eee oe Rema gto
0
0 ل
۱
0 Rem aaah
December 24, 2024 Peete see nett 38