DATA MINING BEC 414

LECTURE 1
Introduction
What is data mining?

Data mining is the use of efficient

techniques for the analysis of very
large collections of data and the
extraction of useful and possibly
unexpected patterns in data.
 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

• Alternative names
• Knowledge discovery (mining) in databases (KDD), knowledge
extraction, data/pattern analysis
Knowledge Discovery (KDD) Process
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
Dimension reduction interpretation
Clustering
Outlier analysis Pattern visualization
…………

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

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
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
Why Data Preprocessing?
• Data in the real world is dirty
• incomplete: lacking attribute values, lacking certain attributes of
interest, or containing only aggregate data
• noisy: containing errors or outliers
• inconsistent: containing discrepancies in codes or names
• No quality data, no quality mining results!
• Quality decisions must be based on quality data
• Data warehouse needs consistent integration of quality data
• Required for both OLAP and Data Mining!
 Why can Data be Incomplete?

• Attributes of interest are not available (e.g., customer

information for sales transaction data)
• Data were not considered important at the time of
transactions, so they were not recorded!
• Data not recorded because of misunderstanding or
malfunctions
• Data may have been recorded and later deleted!
• Missing/unknown values for some data
 Data Cleaning

• Data cleaning tasks

• Fill in missing values

• Identify outliers and smooth out noisy data

• Correct inconsistent data

Why do we need data mining?
• Really, really huge amounts of raw data!!
• In the digital age, TB of data is generated by the second
• Mobile devices, digital photographs, web documents.
• Facebook updates, Tweets, Blogs, User-generated content
• Transactions, sensor data, surveillance data
• Queries, clicks, browsing
• Cheap storage has made it possible to maintain this data
• Needto analyze the raw data to extract
knowledge
Why do we need data mining?
• “The data is the computer”
• Large amounts of data can be more powerful than
complex algorithms and models
• Google has solved many Natural Language Processing problems,
simply by looking at the data
• Example: misspellings, synonyms
• Data is power!
• Today, the collected data is one of the biggest assets of an online
company
• Query logs of Google
• The friendship and updates of Facebook
• Tweets and follows of Twitter
• Amazon transactions
• We need a way to harness the collective intelligence
The data is also very complex
• Multiple types of data: tables, time series,
images, graphs, etc

• Spatial and temporal aspects

• Interconnected data of different types:

• From the mobile phone we can collect, location of the
user, friendship information, check-ins to venues,
opinions through twitter, images though cameras,
queries to search engines
 Examples of Data mining Applications
1. Fraud detection: credit cards, phone cards
2. Marketing: customer targeting
3. Data Warehousing: Walmart
4. Astronomy
5. Molecular biology
Example: transaction data
• Billions of real-life customers:
• WALMART: 20M transactions per day
• AT&T 300 M calls per day
• Credit card companies: billions of transactions per day.

• The point cards allow companies to collect

information about specific users
Example: document data
• Web as a document repository: estimated 50
billions of web pages

• Wikipedia: 4 million articles (and counting)

• Online news portals: steady stream of 100’s of

new articles every day

• Twitter: ~300 million tweets every day

Example: network data
• Web: 50 billion pages linked via hyperlinks

• Facebook: 500 million users

• Twitter: 300 million users

• Instant messenger: ~1billion users

• Blogs: 250 million blogs worldwide, presidential

candidates run blogs
Example: environmental data
• Climate data (just an example)
http://www.ncdc.gov/oa/climate/ghcn-monthly/index.php

• “a database of temperature, precipitation and

pressure records managed by the National Climatic
Data Center, Arizona State University and the
Carbon Dioxide Information Analysis Center”

• “6000 temperature stations, 7500 precipitation

stations, 2000 pressure stations”
• Spatiotemporal data
Behavioral data
• Mobile phones today record a large amount of information about the user
behavior
• GPS records position
• Camera produces images
• Communication via phone and SMS
• Text via facebook updates
• Association with entities via check-ins

• Amazon collects all the items that you browsed, placed into your basket,
read reviews about, purchased.

• Google and Bing record all your browsing activity via toolbar plugins.
They also record the queries you asked, the pages you saw and the
clicks you did.

• Data collected for millions of users on a daily basis

 Attributes
So, what is Data?
Tid Refund Marital Taxable
• Collection of data objects and Status Income Cheat

their attributes 1 Yes Single 125K No

2 No Married 100K No
• An attribute is a property or 3 No Single 70K No
characteristic of an object 4 Yes Married 120K No
• Examples: eye color of a person, 5 No Divorced 95K Yes
temperature, etc. Objects
6 No Married 60K No
• Attribute is also known as 7 Yes Divorced 220K No
variable, field, characteristic, or 8 No Single 85K Yes
feature
9 No Married 75K No
• A collection of attributes 10 No Single 90K Yes
describe an object 10

• Object is also known as record,

point, case, sample, entity, or Size: Number of objects
instance Dimensionality: Number of attributes
Sparsity: Number of populated
object-attribute pairs
Types of Attributes
• Categorical attributes
• Examples: eye color, zip codes, words, rankings (e.g, good,
fair, bad), height in {tall, medium, short}
• Nominal (no order or comparison) vs Ordinal (order but not
comparable)
• A nominal variable has no intrinsic ordering to its categories.
For example, gender is a categorical variable having two
categories (male and female) with no intrinsic ordering to
the categories.
• An ordinal variable has a clear ordering. For example,
temperature as a variable with three orderly categories (low,
medium and high).
Cont…
• Numeric
• Examples: dates, temperature, time, length, value, count.
• Discrete finite (counts) eg zip code vs Continuous infinite
(temperature) or weight
• Special case: Binary attributes (yes/no, exists/not exists)
Numeric Record Data
• If data objects have the same fixed set of numeric
attributes, then the data objects can be thought of as
points in a multi-dimensional space, where each
dimension represents a distinct attribute

• Such data set can be represented by an n-by-d data

matrix, where there are n rows, one for each object, and d
columns, one for each attribute

Projection Projection Distance Load Thickness

of x Load of y load

10.23 5.27 15.22 2.7 1.2

12.65 6.25 16.22 2.2 1.1
Categorical Data
• Data that consists of a collection of records, each
of which consists of a fixed set of categorical
attributes
Tid Refund Marital Taxable
Status Income Cheat

1 Yes Single High No

2 No Married Medium No
3 No Single Low No
4 Yes Married High No
5 No Divorced Medium Yes
6 No Married Low No
7 Yes Divorced High No
8 No Single Medium Yes
9 No Married Medium No
10 No Single Medium Yes
10
Document Data
• Each document becomes a `term' vector,
• each term is a component (attribute) of the vector,
• the value of each component is the number of times the
corresponding term occurs in the document.
• Bag-of-words representation – no ordering

timeout

season
coach

game
score
team

ball

lost
pla

wi
n
y

Document 1 3 0 5 0 2 6 0 2 0 2

Document 2 0 7 0 2 1 0 0 3 0 0

Document 3 0 1 0 0 1 2 2 0 3 0
Transaction Data
• Each record (transaction) is a set of items.
TID Items
1 Bread, Coke, Milk
2 Beer, Bread
3 Beer, Coke, Diaper, Milk
4 Beer, Bread, Diaper, Milk
5 Coke, Diaper, Milk

• A set of items can also be represented as a

binary vector, where each attribute is an item.
Sparsity: average number of products bought by a customer
Ordered Data
• Genomic sequence data

GGTTCCGCCTTCAGCCCCGCGCC
CGCAGGGCCCGCCCCGCGCCGTC
GAGAAGGGCCCGCCTGGCGGGCG
GGGGGAGGCGGGGCCGCCCGAGC
CCAACCGAGTCCGACCAGGTGCC
CCCTCTGCTCGGCCTAGACCTGA
GCTCATTAGGCGGCAGCGGACAG
GCCAAGTAGAACACGCGAAGCGC
TGGGCTGCCTGCTGCGACCAGGG

• Data is a long ordered string

Ordered Data
• Time series
• Sequence of ordered (over “time”) numeric values.
Graph Data
• Examples: Web graph and HTML Links
<a href="papers/papers.html#bbbb">
Data Mining </a>
<li>
2 <a href="papers/papers.html#aaaa">
Graph Partitioning </a>
<li>
5 1 <a href="papers/papers.html#aaaa">
Parallel Solution of Sparse Linear System of Equations </a>
<li>
2 <a href="papers/papers.html#ffff">
N-Body Computation and Dense Linear System Solvers
5
What can you do with the data?
• Suppose that you are the owner of a supermarket
and you have collected billions of market basket
data. What information would you extract from it
and how would you use it?
TID Items
Product placement
1 Bread, Coke, Milk
2 Beer, Bread
3 Beer, Coke, Diaper, Milk Catalog creation
4 Beer, Bread, Diaper, Milk
5 Coke, Diaper, Milk Recommendations

• What if this was an online store?

What can you do with the data?
• Suppose you are a search engine and you have
a toolbar log consisting of
• pages browsed,
• queries,
Ad click prediction
• pages clicked,
• ads clicked Query reformulations

each with a user id and a timestamp. What

information would you like to get our of the data?
What can you do with the data?
• Suppose you are biologist who has microarray
expression data: thousands of genes, and their
expression values over thousands of different settings
(e.g. tissues). What information would you like to get
out of your data?

Groups of genes and tissues

What can you do with the data?
• Suppose you are a stock broker and you observe
the fluctuations of multiple stocks over time. What
information would you like to get out of your data?

Clustering of stocks

Correlation of stocks

Stock Value prediction

What can you do with the data?
• You are the owner of a social network, and you
have full access to the social graph, what kind of
information do you want to get out of your graph?

• Who is the most important node in the graph?

• What is the shortest path between two nodes?
• How many friends two nodes have in common?
• How does information spread on the network?
Why data mining?
• Commercial point of view
• Data has become the key competitive advantage of companies
• Examples: Facebook, Google, Amazon
• Being able to extract useful information out of the data is key for exploiting
them commercially.
• Scientific point of view
• Scientists are at an unprecedented position where they can collect TB of
information
• Examples: Sensor data, astronomy data, social network data, gene data
• We need the tools to analyze such data to get a better understanding of the
world and advance science
• Scale (in data size and feature dimension)
• Why not use traditional analytic methods?
• Enormity of data, curse of dimensionality
• The amount and the complexity of data does not allow for manual
processing of the data. We need automated techniques.
What is Data Mining again?
• “Data mining is the analysis of (often large)
observational data sets to find unsuspected
relationships and to summarize the data in novel ways
that are both understandable and useful to the data
analyst” (Hand, Mannila, Smyth)

• “Data mining is the discovery of models for data”

(Rajaraman, Ullman)
• We can have the following types of models
• Models that explain the data (e.g., a single function)
• Models that predict the future data instances.
• Models that summarize the data
• Models that extract the most prominent features of the data.
What can we do with data mining?
• Some examples:
• Frequent itemsets and Association Rules extraction
• Clustering
• Classification
• Ranking
• Exploratory analysis
Same as saying..DM functions
• Association and Correlation Analysis
• Generalization
• Classification
• Cluster analysis
• Outlier analysis
• Trend analysis
 Data Mining Methods
1. Decision Tree Classifiers:
Used for modeling, classification
2. Association Rules:
Used to find associations between sets of attributes
3. Sequential patterns:
Used to find temporal associations in time series
4. Hierarchical clustering:
used to group customers, web users, etc
Frequent Itemsets and Association Rules
• Given a set of records each of which contain some
number of items from a given collection;
• Identify sets of items (itemsets) occurring frequently
together
• Produce dependency rules which will predict occurrence
of an item based on occurrences of other items.
Itemsets
ItemsetsDiscovered:
Discovered:
TID Items {Milk,Coke}
{Milk,Coke}
1 Bread, Coke, Milk {Diaper,
{Diaper,Milk}
Milk}
2 Beer, Bread
3 Beer, Coke, Diaper, Milk Rules
RulesDiscovered:
Discovered:
4 Beer, Bread, Diaper, Milk {Milk}
{Milk}-->
-->{Coke}
{Coke}
5 Coke, Diaper, Milk {Diaper,
{Diaper,Milk}
Milk}-->
-->{Beer}
{Beer}
Tan, M. Steinbach and V. Kumar, Introduction to Data Mining
Frequent Itemsets: Applications
• Text mining: finding associated phrases in text
• There are lots of documents that contain the phrases
“association rules”, “data mining” and “efficient
algorithm”

• Recommendations:
• Users who buy this item often buy this item as well
• Users who watched James Bond movies, also watched
Jason Bourne movies.

• Recommendations make use of item and user similarity

Association Rule Discovery: Application
• Supermarket shelf management.
• Goal: To identify items that are bought together by
sufficiently many customers.
• Approach: Process the point-of-sale data collected
with barcode scanners to find dependencies among
items.
• A classic rule --
• If a customer buys diaper and milk, then he is very likely to
buy beer.
• So, don’t be surprised if you find six-packs stacked next to
diapers!

Tan, M. Steinbach and V. Kumar, Introduction to Data Mining

Clustering Definition
• Given a set of data points, each having a set of
attributes, and a similarity measure among them,
find clusters such that
• Data points in one cluster are more similar to one
another.
• Data points in separate clusters are less similar to
one another.
• Similarity Measures?
• Euclidean Distance if attributes are continuous.
• Other Problem-specific Measures.

Tan, M. Steinbach and V. Kumar, Introduction to Data Mining

 Illustrating Clustering
Euclidean Distance Based Clustering in 3-D space.

Intracluster
Intraclusterdistances
distances Intercluster
Interclusterdistances
distances
are
areminimized
minimized are
aremaximized
maximized

Tan, M. Steinbach and V. Kumar, Introduction to Data Mining

Clustering: Application 1
• Bioinformatics applications:
• Goal: Group genes and tissues together such that genes are
coexpressed on the same tissues
Clustering: Application 2
• Document Clustering:
• Goal: To find groups of documents that are similar to
each other based on the important terms appearing in
them.
• Approach: To identify frequently occurring terms in
each document. Form a similarity measure based on
the frequencies of different terms. Use it to cluster.
• Gain: Information Retrieval can utilize the clusters to
relate a new document or search term to clustered
documents.

Tan, M. Steinbach and V. Kumar, Introduction to Data Mining

 47

Data Mining Function: Outlier Analysis

• Outlier analysis
• Outlier: A data object that does not comply with the general behavior
of the data
• Noise or exception? ― One person’s garbage could be another
person’s treasure
• Methods: by product of clustering or regression analysis, …
• Useful in fraud detection, rare events analysis
Classification: Definition
• Given a collection of records (training set )
• Each record contains a set of attributes, one of the
attributes is the class.
• Find a model for class attribute as a function of
the values of other attributes.

• Goal: previously unseen records should be

assigned a class as accurately as possible.
• A test set is used to determine the accuracy of the
model. Usually, the given data set is divided into
training and test sets, with training set used to build
the model and test set used to validate it.
 Classification Example
l l
us
ir ca ir ca uo
ego ego t in
t t n ss
ca ca co c l a
Tid Refund Marital Taxable Refund Marital Taxable
Status Income Cheat Status Income Cheat

1 Yes Single 125K No No Single 75K ?

2 No Married 100K No Yes Married 50K ?
3 No Single 70K No No Married 150K ?
4 Yes Married 120K No Yes Divorced 90K ?
5 No Divorced 95K Yes No Single 40K ?
6 No Married 60K No No Married 80K ? Test
10

Set
7 Yes Divorced 220K No
8 No Single 85K Yes
9 No Married 75K No
Training
Learn
10
10 No Single 90K Yes
Set Classifier Model

Tan, M. Steinbach and V. Kumar, Introduction to Data Mining

Classification: Application 1
• Ad Click Prediction
• Goal: Predict if a user that visits a web page will click
on a displayed ad. Use it to target users with high
click probability.
• Approach:
• Collect data for users over a period of time and record who
clicks and who does not. The {click, no click} information
forms the class attribute.
• Use the history of the user (web pages browsed, queries
issued) as the features.
• Learn a classifier model and test on new users.
Classification: Application 2
• Fraud Detection
• Goal: Predict fraudulent cases in credit card
transactions.
• Approach:
• Use credit card transactions and the information on its
account-holder as attributes.
• When does a customer buy, what does he buy, how often he pays on
time, etc
• Label past transactions as fraud or fair transactions. This
forms the class attribute.
• Learn a model for the class of the transactions.
• Use this model to detect fraud by observing credit card
transactions on an account.

Tan, M. Steinbach and V. Kumar, Introduction to Data Mining

Connections of Data Mining with other areas
• Draws ideas from machine learning/AI, pattern
recognition, statistics, and database systems
• Traditional Techniques
may be unsuitable due to
• Enormity of data Statistics/ Machine Learning/
AI Pattern
• High dimensionality Recognition
of data
• Heterogeneous, Data Mining

distributed nature
of data Database
• Emphasis on the use of data systems

Tan, M. Steinbach and V. Kumar, Introduction to Data Mining

Data Mining: Confluence of Multiple Disciplines

Database
Technology Statistics

Machine Visualization
Data Mining
Learning

Pattern
Recognition Distributed
Algorithm Computing
The data analysis pipeline
• Mining is not the only step in the analysis process

Data Result
Data Mining
Preprocessing Post-processing

• Preprocessing: real data is noisy, incomplete and inconsistent.

Data cleaning is required to make sense of the data
• Techniques: Sampling, Dimensionality Reduction, Feature selection.
• A dirty work, but it is often the most important step for the analysis.
• Post-Processing: Make the data actionable and useful to the user
• Statistical analysis of importance
• Visualization.

• Pre- and Post-processing are often data mining tasks as

well
Data Quality
• Examples of data quality problems:
• Noise and outliers
• missing values
• duplicate data
Sampling
• Sampling is the main technique employed for data
selection.
• It is often used for both the preliminary investigation of the
data and the final data analysis.

• Statisticians sample because obtaining the entire

set of data of interest is too expensive or time
consuming.

• Sampling is used in data mining because

processing the entire set of data of interest is too
expensive or time consuming.
Sampling …
• The key principle for effective sampling is the
following:
• using a sample will work almost as well as using the
entire data sets, if the sample is representative

• A sample is representative if it has approximately the

same property (of interest) as the original set of data
Types of Sampling
• Simple Random Sampling
• There is an equal probability of selecting any particular item

• Sampling without replacement

• As each item is selected, it is removed from the population

• Sampling with replacement

• Objects are not removed from the population as they are selected
for the sample.
• In sampling with replacement, the same object can be picked up more
than once

• Stratified sampling
• Split the data into several partitions; then draw random samples
from each partition