Outline of Introduction

Data Mining
Why data mining?
(EECS 6412)
What is data mining?
Process of data mining or KDD
Introduction to Data Mining
Course information
Instructor: Aijun An
Overview of data mining
EECS, York University
What kind of data to mine from?
What kind of patterns to mine? (Data Mining
Tasks)
Data mining R&D issues
2

Why Data Mining?

Why Data Mining Became Popular?
Data mining started around 1990
People were from Data flood
Database systems, machine learning (ML), and Vast amounts of data are produced every day
statistics Data are generated by:
ML at that time Bank, telecom, stores, other business transactions ...
Worked only on small datasets Scientific fields: astronomy, biology, etc
Focused on classification, regression and Web and social media (text, images, audio, video,
clustering tasks etc.)
There was need to Internet of Things (IoT)
Handle large amounts of data In 2020, 31 billion IoT devices exist (source: Statista).
Learn other types of useful patterns 3
Big Data Era 4

Big Data Examples Characteristics of Big Data

5Vs in Big Data:
Volume
2.4 Billion 34 GIGABYTES 183 HOURS 24 PETABYTES
NUMBER OF MAILS SENT DATA CONSUMED BY VIDEO UPLOADED TO DATA PER DAY PROCESSED
Velocity
EVERY SECOND HOUSEHOLDS EACH DAY YOUTUBE EVERY MINUTE BY GOOGLE (2017)
Variety
Veracity
Value

500 MILLION 700 BILLION 13 EXABYTES 398 ITEMS

TWEETS PER DAY TOTAL MINUTES SPENT ON DATA SENT AND RECEIVED PRODUCTS ORDERED ON
FACEBOOK EACH MONTH (2017) BY MOBILE INTERNET AMAZON PER SECOND (2017)
USERS (2017)

5 6

1
 Value Purpose of Data Mining
Data mining is a tool to get the value out of
Valuable information hidden in data data.
For example:
What types of credit card transactions are fraud?
What items are often bought together? Value
Veracity
What types of customers like a particular product?
What news or ads should be recommended to an online
news reader? Variety Volume
Who are the most influential people in a social network?
Velocity
What topics are people discussing in social media?
What types of patients react positively to a new drug?
7 8

What is Data Mining? What Is Data Mining?

Mining knowledge from data Data mining [Han, 2001]
Data = raw information process of extracting interesting (non-trivial,
Knowledge = patterns or models ‘behind’ the implicit, previously unknown and potentially
data useful) knowledge or patterns from data in
large databases.
Objectives of data mining:
Data
Data Knowledge Decision Plans for
future activities
Discover knowledge that characterizes general
Mining Making
properties of data
Discover patterns on the previous data in order
to make predictions on future data

9 10

Example 1 Example 2
Hypothetical Training Data for Disease Diagnosis
Data about investors
Patient Sore Swollen
ID# Throat Fever Glands Congestion Headache Diagnosis
Customer Account Margin Transaction Trades/ Favorite Annual
ID Type Account Method Month Sex Age Recreation Income 1 Yes Yes Yes Yes Yes Strep throat
2 No No No Yes Yes Allergy
3 Yes Yes No Yes No Cold
1005 Joint No Online 12.5 F 30–39 Tennis 40–59K 4 Yes No Yes No No Strep throat
1013 Custodial No Broker 0.5 F 50–59 Skiing 80–99K 5 No Yes No Yes No Cold
1245 Joint No Online 3.6 M 20–29 Golf 20–39K 6 No No No Yes No Allergy
2110 Individual Yes Broker 22.3 M 40–49 Fishing 40–59K 7 No No Yes No No Strep throat
1001 Individual Yes Online 5.0 M 30–39 Golf 60–79K 8 Yes No No Yes Yes Allergy
9 No Yes No Yes Yes Cold
10 Yes Yes No Yes Yes Cold
Possible business questions
• In this example dataset, attributes correspond to Symptoms,
Can we develop a general characterization/profile of and Diagnosis.
different investor types? (characterization/frequent patterns)
What characteristics distinguish between Online and Broker • The natural question is to predict the Diagnosis (class) [the
investors? (classification) Output variable] from the symptoms [the input variables].
Can we develop a model which will predict the average
trades/month for a new investor? (regression) 11 12

2
 Example 2 (Cont’d)
Swollen

Example 2 (Cont’d) No
Glands

Yes

Fever Strep throat

Pattern discovered: No Yes

a decision tree Swollen

Allergy Cold
Using Decision Tree for Prediction
Glands
No Yes Data Instances with an Unknown Classification
Patient Sore Swollen
ID# Throat Fever Glands Congestion Headache Diagnosis
Fever Diagnosis= Strep throat
11 No No Yes Yes Yes ?
12 Yes Yes No No Yes ?
No Yes 13 No No No No Yes ?

Diagnosis= Allergy Diagnosis= Cold

What are the predicted diagnoses?

13 14

Generated Rules for Iris Plants Classification

Example 3 Rules for Class = Iris Setosa (1 rule)
Rule 1: (petal_length<=1.9)  (class = Iris Setosa)
Part of training data for Iris plants
Rules for Class= Iris Versicolour (3 rules)
classification Rule 1: (1.9<petal_length<=4.9)  (petal_width<=1.6)  (class = Iris Versicolour)
Sepal Length Sepal W idth Petal Length Petal W idth Class Rule 2: (sepal_length>5.8)  (petal_length<=5.1)  (petal_width<=1.7)
5.1 3.5 1.4 0.2 Iris Setosa  (class = Iris Versicolour)
4.9 3 1.4 0.2 Iris Setosa
Rule 3: (sepal_length>5.8)  (sepal_width>3.0)  (petal_length<=4.8)
4.7 3.2 1.3 0.2 Iris Setosa
5.4 3.9 1.7 0.4 Iris Setosa  (class = Iris Versicolour)
4.8 3 1.4 0.1 Iris Setosa
7 3.2 4.7 1.4 Iris Versicolour
Rules for Class = Iris Virginica (4 rules)
6.4 3.2 4.5 1.5 Iris Versicolour
5.5 2.3 4 1.3 Iris Versicolour Rule 1: (petal_length>4.8)  (petal_width>1.7) (class = Iris Virginica)
5 2 3.5 1 Iris Versicolour
Rule 1: (sepal_length>6.2) (petal_length>5.0) (class = Iris Virginica)
5.4 3 4.5 1.5 Iris Versicolour
6 3 4.8 1.8 Iris Virginica :
6.9 3.1 5.4 2.1 Iris Virginica Summary: Total number of rules = 8
6.5 3 5.2 2 Iris Virginica
6.2 3.4 5.4 2.3 Iris Virginica Average length of rules = 2.75
5.9 3 5.1 1.8 Iris Virginica Training accuracy = 99.33%
15 16

Data Mining: Confluence of Multiple Disciplines

Example 4: Recommendation
A person buys a book (product) at [Link]. Machine Pattern Statistics
Learning Recognition
Task:
Recommend other books (products) this person is
likely to buy Visualization
Applications Data Mining
One method:
Use frequent pattern mining on transaction histories
and may find: Algorithm Database High-Performance
Customers who bought “Advances in Knowledge Discovery and Technology Computing
Data Mining”, also bought “Data Mining: Concepts and
Techniques”

Recommendation program is quite successful 17 18

3
 Some Related Fields
Alternative Name: KDD
Machine Learning
Subfield of AI Knowledge discovery in databases (KDD)
Used by AI, Machine Learning Community since
Exploratory data analysis 1989
Subfield of Statistics
Data warehousing and OLAP (Database) Data mining
Data summarization and aggregation Used by DB, business people since 1990
Data mining (in comparison to ML)
inherits techniques from ML and statistics Two names are now used interchangeably
emphasizes processing very large data sets
finds more types of patterns 19 20

Process of Data Mining and KDD Course Objectives

To provide an introduction to data mining
To understand the fundamental concepts, principles,
Pattern Evaluation and Presentation algorithms, and applications of data mining.
patterns
Pattern Extraction
To gain hands-on experience by
training data
Feedback
implementing some data mining algorithms.
Data Reduction and Transformation using data mining software to mine patterns from real
world data
Data Data Cleaning
Preprocessing
target data To study advanced topics in data mining
Data Selection and Integration
To prepare yourself for
Goals of Prior
pursuing research in data mining,
Data
Application Knowledge using data mining in your research or pursuing data
21 analytics jobs 22

Course Content Reference Books and Materials

Basics of data mining
Pattern mining Reference books
Frequent pattern and association rule mining Jiawei Han, Jian Pei and Hanghang Tong, Data Mining:
Sequential pattern mining Concepts and Techniques, Morgan Kaufmann, 4th
Mining classification models Edition, 2023.
Data preprocessing (feature selection, normalization, missing value
handling, etc.) Pang-Ning Tan, Michael Steinbach, Anuj Karpatne,
Decision tree learning Vipin Kumar, Introduction to Data Mining, Second
Bayesian classification (naïve Bayes and Bayesian networks) Edition, Pearson, 2019.
Neural networks and introduction to deep learning Charu C. Aggarwal, Data Mining, The Textbook,
K-nearest neighbor method Springer, 2015.
Learning from imbalanced data
Ian H. Witten and Eibe Frank, Data Mining: Practical
Clustering analysis Machine Learning Tools and Techniques (Second
Text classification Edition), Morgan Kaufmann, 2005.
Graph mining
Advanced topics (e.g., recommendation systems, multi- Some conference/journal papers
modal sentiment analysis, knowledge graphs, causality (To be) posted on the course web site
discovery, etc.)
23 24

4
 Project
Evaluation and Grading
Should be done in a group of 2 students.
Pick a recent advanced topic in data mining
Topic list will be released in the second week
Assignments (20%) Conduct a survey on the topic
2 assignments Present the survey to the class in November (10%)

Project (45%) Implement and evaluate a (SOTA) method as a baseline

Submit code and a short report (10%)
Final exam (25%) Design your solution to the problem
Participation (10%) E.g., a reasonable improvement to the baseline
Implement your solution
Evaluate your solution by comparing it to baseline(s)
Write a final project report (in a research paper format) (20%)
Present the project to the class (7-10 minutes) (5%)
25 26

Survey Presentation
Make a 30-minute presentation to the class
Instructor Information
What is the topic area about?
Motivation, objectives, and problem definition Office hours
What are the categories of existing techniques?
Thursdays: 1:00pm-2:00pm
Briefly present a representative method in at least two
categories. Location: LAS 2048
What are the advantages of each category or technique?
What are the limitations of each category or technique?
What are the open (unresolved) issues in the research? Email: aan@[Link]

Purpose:
Course eClass site:
Make the class understand the topic areas and techniques
for solving the problem [Link]
Develop presentation skills 27 28

Outline of Introduction What Kind of Data?

Why data mining? Tabular data
What is data mining? Transactional data
Process of data mining or KDD Text data
Time-series data
Course information
Sequence data
Overview of data mining
Data streams
What kind of data to mine from?
Graphs
What kind of patterns to mine? (Data Mining
Multimedia databases
Tasks)
…
Data mining R&D issues
29 30

5
 Tabular Data
Transactional Data
Attributes/Features/Variables

Structured data
Transaction-id Itemset
Table
T100 Milk, bread, beer, diaper
Examples Examples/ T200 Beer, cook, fish, potato, orange, diaper
Instances/
Attributes Cases/ … …
Observations
Can be stored in Some transactional databases also contain time stamp and
plain text files, or the customer id for each transaction

relational databases.
An attribute can be:
Patterns
Most common form of • Symbolic (discrete, categorical) What kind of product combinations that customers
• Numeric (continuous, integer)
data for classification, • Ordinal (categorical with a value
like to buy together?
clustering and regression order, e.g., temperature with values
of low, medium, high)
tasks 31 32

Text Data
<breakfast_menu>
<food>
<name>Belgian Waffles</name>
Example of XML Data
<price>$5.95</price>
<description>Two of our famous Belgian Waffles with plenty of real maple syrup</description>

Documents <calories>650</calories>
</food>
<food>
articles, Web pages, blogs, tweets, emails, product <name>Strawberry Belgian Waffles</name>
<price>$7.95</price>
specifications, reports, notes, reviews, etc. <description>Light Belgian waffles covered with strawberries and whipped cream</description>
<calories>900</calories>
</food>
Structure <food>
<name>Berry-Berry Belgian Waffles</name>

highly unstructured (news, stories, etc.), or <price>$8.95</price>

<description>Light Belgian waffles covered with an assortment of fresh berries and whipped cream</description>
<calories>900</calories>

semistructured (HTML/XML documents, etc.) </food>

<food>
<name>French Toast</name>

What can be discovered from a text database? <price>$4.50</price>

<description>Thick slices made from our homemade sourdough bread</description>
<calories>600</calories>
text classification models </food>
<food>
keyword or content associations <name>Homestyle Breakfast</name>
<price>$6.95</price>

summaries, topics, sentiments, emotions <description>Two eggs, bacon or sausage, toast, and our ever-popular hash browns</description>
<calories>950</calories>

... 33
</food>
</breakfast_menu> 34

Time Series Data Sequence Data

A sequence of values that change with time Sequences of ordered objects or events
Daily water consumption data in a city (with or without concrete notation of time)
Data collected regarding the stock exchange Bio-sequences
Types of analysis DNA, protein
An example DNA sequence and its paired strand
Trend analysis Web log data (Credit: Gerardo M Nava)

To predict future values Click stream (web page traversal sequences)

Similarity search
Sequences of items bought by a customer
Find similarities in sub-sequences, such as periodic
patterns, recurring patterns Patterns
Frequent sequences, alignments of two bio-
35
sequences, etc. 36

6
 Graph Data Example 1 of Graph Dataset
Data entities are connected, forming graphs
Aspirin Biological Networks Graph data set: containing one or more graphs (3 in this example)

Credits: Chinese Academy of Agricultural Sciences

Social Networks
Financial Networks
1

2 2

Patterns can be found:

• Frequent subgraphs
3 3

4 4

5 5

(1) (2)
37 38

Example 2 of Graph Dataset Other Graph Mining Tasks

Social networks
Find communities in social networks
Find the most influential people in communities
Anomaly detection
Etc.

Two graph mining tasks:

• Link prediction
• Node classification
39 40

Outline of Introduction Basic Data Mining Tasks

Predictive: Discover patterns on previous & current
data in order to make predictions on future data
Why data mining? Classification
Regression
What is data mining?
Structured prediction
Process of data mining or KDD Descriptive: Discover knowledge that characterizes
Course information general properties of data
Clustering
Overview of data mining Concept characterization / Summarization
What kind of data to mine from? Association analysis (frequent itemsets, association rules)
Sequential pattern mining
What kind of patterns to mine? (Data Mining
Predictive or descriptive
Tasks) Time series analysis
Data mining R&D issues Outlier detection
41 …… 42

7
 Predictive Tasks Types of Predictive Tasks / Supervised Learning
A form of Supervised Learning
− Training examples are labeled with target outputs
Input/independent/Condition
Classification
Target/Output/Decision
attributes/features/variables
attribute/variable Regression
Structured prediction
Examples/
Instances/
Cases/
Observations

− Learn a model from labelled data to make predictions on the future data

Input of a new example Learned Model Predicted output

43 44

Class attribute

Classification Classification (Cont’d)

Examples

Target variable is discrete Models can be in different types

Its values are considered as classes (labels) − Decision tree
− The target attribute is also called class attribute − A set of rules
− Examples: − Bayesian network
 Diagnosis: {strep throat, allergy, cold} − Support vector machine
 Image type: {cat, dog, car, truck, ……} − Neural network
− ……
Goal:
− Learn a model from the labeled training data
− Learned model is used to classify new examples
For different types of models, different types of learning
algorithms were designed

45 46

Example of Classification Models Types of Predictive Tasks / Supervised Learning

A decision tree for PlayTennis Classification

Day Outlook Temp Humid Wind PlayTennis
D1 Sunny Hot High Weak No Regression
D2 Sunny Hot High Strong No Outlook
D3 Overcast Hot High Weak Yes Structured prediction
D4 Rain Mild High Weak Yes
Sunny Overcast Rain
D5 Rain Cool Normal Weak Yes
D6 Rain Cool Normal Strong No
Humidity Yes
D7 Overcast Cool Normal Strong Yes Wind
D8 Sunny Mild High Weak No
D9 Sunny Cool Normal Weak Yes High Normal Strong Weak
D10 Rain Mild Normal Weak Yes
D11 Sunny Mild Normal Strong Yes
D12 Overcast Mild High Strong Yes No Yes No Yes
D13 Overcast Hot Normal Weak Yes
D14 Rain Mild High Strong No

47 48

8
 Input/independent variables/predictors
Target attribute/variable
Regression
Regression Hours
1
Prep
exams
1
Exam
score
76
(Dependent
variable)
2 3 78
2 3 85

Target variable is numeric, e.g.,

4
2
1
5
2
2
88
72
69
Linear vs. non-linear regression
− House price 5
4
1
1
94
94 − Relationship between independent and dependent variables are
2 0 88
− Daily water consumption in a city 4
4
3
4
92
90
linear or non-linear
3 3 75
− Exam score 6 2 96
5 4 90
3 4 82
4
6
4
5
85
99 Simple vs. multiple regression
Goal: 2
1
1
0
83
62
− Simple regression
2 1 76
− Learn a model from the labeled training data to model the relationship
 only one independent variable
between the input and target variables
− Learned model is used to predict a numeric value for a new example
− Multiple regression
 multiple independent variables

49 50

Simple Linear Regression - Example Simple Linear Regression - Example

SBP (mm Hg)
Data: Age and systolic blood pressure (SBP) among 33 adult women

Age SBP Age SBP Age SBP

22 131 41 139 52 128
23 128 41 171 54 105
24 116 46 137 56 145
27 106 47 111 57 141
28 114 48 115 58 153
29 123 49 133 59 157
30 117 49 128 63 155
32 122 50 183 67 176
33 99 51 130 71 172
35 121 51 133 77 178
40 147 51 144 81 217
Age (years)

adapted from Colton T. Statistics in Medicine. Boston: Little Brown, 1974

51 52

Multiple Linear Regression Example Types of Predictive Tasks / Supervised Learning

Target attribute/variable

Hours
Prep
exams
Exam
score Linear regression model learned: Classification
1 1 76
2
2
3
3
78
85
Exam score = 67.67 + 5.56*(Hours) – 0.60*(Prep exams)
Regression
4 5 88
2
1
2
2
72
69 Structured prediction
5
4
1
1
94
94 Prediction:
2 0 88
4 3 92 − A new student with Hours=4 and Prep exams = 2
4 4 90
3 3 75
− Predicted exam score:
6 2 96
5 4 90 Exam score = 67.67 + 5.56*4– 0.60*2 = 88.71
3 4 82
4 4 85
6 5 99
2 1 83
1 0 62
2 1 76

53 54

9
 Structured Prediction Structured Prediction
• Another example: Named entity recognition
Outputs are structured objects, e.g.,
Labeled Training data: Prediction on new data:
− Sequences, trees, graphs, or other interrelated
components
− There are often relationships among output components
Example:
− Sequence-to-sequence problems
 Both input and output are a sequence
 E.g., machine translation (English  French)

56
55

Basic Data Mining Tasks

Descriptive Data Mining Tasks
Predictive:
Classification
Training data do not have output or target variables
Regression
Structured prediction Goal is to
− Extract hidden patterns or relationships in data
Descriptive:
− Discover knowledge that characterizes general properties of data
Clustering
Concept characterization / Summarization A form of unsupervised learning
Association analysis (frequent itemsets, association rules) Typical descriptive tasks
Sequential pattern mining − Clustering
Predictive or descriptive − Concept characterization / Summarization
Time series analysis − Association analysis (frequent itemsets, association rules)
Outlier detection − Sequential pattern mining
…… 57 58

Clustering Concept Characterization

Class label is unknown in the training data.
Group data to form classes (clusters)
Summarization of general properties of
Unsupervised learning.
objects in a target group
Principle:
maximizing the intra-class
Example:
similarity Characterize customers who spend more than
minimizing the inter-class $1000 a year in the AllElectronic store and
similarity have excellent credit ratings.
Applications
Market/customer segmentation Result: 40-50 years old, employed,
Image segmentation
…. 59 60

10
 Association Analysis Mining Sequential Patterns
Examples of association rules: Find frequently occurring patterns in a
age(X, “20..29”) ^ income(X, “20..29K”)  buys(X, “PC”) sequence database.
[support = 2%, confidence = 60%]
Within 3 months, buy computer  buy USB
contains(T, “computer”)  contains(T, “software”)
drive  buy digital camera
[support=1%, confidence=75%] (T stands for a transaction)
Applications
Sale campaign analysis
Widely used for market basket or transactional
What are the subsequent purchases after buying a
data analysis. PC?
What products were often purchased together? Web log analysis
DNA or protein analysis
61 62

Basic Data Mining Tasks Time Series Analysis

Predictive: Mine from time-series data to
Classification Predict future values (Predictive)
Regression Determine similar patterns over time (Descriptive)
Descriptive: Example: Stock Market
Clustering
Concept characterization / Summarization
Association analysis (frequent itemsets, association rules)
Sequential pattern mining
Predictive or descriptive
Time series analysis
Outlier detection

63 64

Outlier/Anomaly Detection What will be covered in lectures

Outlier
A data object that does not comply with the general behavior
Predictive:
of the data Classification 
Regression (will cover regression trees )
Noise or exception? Structured prediction
One person’s garbage could be another person’s treasure Descriptive:
Methods: Clustering 
Clustering Concept characterization / Summarization
Association analysis (frequent itemsets, association rules) 
Classification
Sequential pattern mining 
Regression analysis
Predictive or descriptive
… Time series analysis
Useful in fraud detection, rare events analysis 65
Outlier detection 66

11
 Outline of Introduction
Questions
Why data mining?
What is the difference between classification What is data mining?
and clustering?
Process of data mining or KDD
Course information
What is the difference between classification
Overview of data mining
and regression?
What kind of data to mine from?
What kind of patterns to mine? (Data Mining
Tasks)
Data mining R&D issues
67 68

Major Issues in Data Mining Efficiency

Develop fast and scalable data mining
Efficiency algorithms (time-efficient)
Effective data structure
Effectiveness
Parallel, distributed, and incremental mining
User interaction
Heuristic and Approximation algorithms
Privacy preserving
Memory-efficient
Fairness and biases Develop algorithms that can handle huge amounts
Interpretability of data that cannot be held in RAM.

69 70

Effectiveness User Interaction

Accuracy Interactive mining

How to develop models from data to make Incorporate background knowledge
accurate predictions on future data Combine objective and subjective measures
Interestingness and actionability of Visualization helps such an integration
discovered patterns Visualization of data
How to identify interesting patterns from a Presentation of mining results
large number of patterns discovered
Visualization of the mining process
How to use the discovered patterns

71 72

12
 Data Mining with Privacy
Fairness and Bias in AI
Data may contain private information
Data mining can invade privacy A model is considered fair if errors are
Technical solutions can limit privacy invasion distributed similarly across different groups
Replacing sensitive personal data with anon. ID of data
Alter the data so that real values are obscured Unfairness is usually caused by bias in
Multi-party computation – distributed data data, or/and
… learning algorithm
Bayardo & Srikant, Technological Solutions
for Protecting Privacy, IEEE Computer, Sep
2003 73 74

Interpretability Next Class

How easy to interpret a learned model/pattern Frequent pattern and association rule
How easy for a human to understand the cause of mining
a decision made by a model

Reading: Chapter 4 of Han’s book (Pattern

mining: basic concepts and methods)

75 76

13