DATA MINING AND BUSINESS

INTELLIGENCE
Course Information
• Credits: 4 Units
• Course Code: IT402
Course Objectives
• The purpose of this course is to introduce the basic data mining
technologies and their use for business intelligence. The objective of
this course is to teach the students how to analyze the business needs
for knowledge discovery in order to create competitive advantages and
to apply data mining technologies appropriately in order to realize
their real business value
Syllabus
Syllabus Contd.
Assessment/Examination Scheme
Books
 Recommended Books
Jiawei Han, Micheline Kamber and Jian Pei, “Data
mining Concepts and Techniques”, Elsevier. Soft copy
available at:
http://ccs1.hnue.edu.vn/hungtd/DM2012/DataMining_BO
OK.pdf
ASET

8/55
 INTRODUCTION: DM AND KDD PROCESS

Loads of Data

ASET

9/55
 INTRODUCTION: DM AND KDD PROCESS

Loads of Data

ASET

10/
 INTRODUCTION: DM AND KDD PROCESS

I have data: Now...???

ASET

What form of analysis??

11/
 INTRODUCTION: DM AND KDD PROCESS

ASET

We are drowning in data, but starving for Knowledge !!!

Need of the hour

Data Mining- Automated analysis of massive data sets.

12/
What is data mining?
• After years of data mining there is still no unique answer to this
question.

• A tentative definition:
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.
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 possible to maintain this data
• Need to 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
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: genomic sequences
• http://www.1000genomes.org/page.php

• Full sequence of 1000 individuals

• 3*109 nucleotides per person  3*1012 nucleotides

• Lots more data in fact: medical history of the persons, gene

expression data
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 their Status Income Cheat
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
feature 8 No Single 85K Yes
9 No Married 75K No
• A collection of attributes describe
an object 10
10 No Single 90K Yes

• 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
• There are different types of attributes
• Categorical
• 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)
• Numeric
• Examples: dates, temperature, time, length, value, count.
• Discrete (counts) vs Continuous (temperature)
• 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
Document 1 3 0 y
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 document can also be represented as a set of words (no counts)

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

2 <a href="papers/papers.html#bbbb">
Data Mining </a>
<li>
5 1 <a href="papers/papers.html#aaaa">
Graph Partitioning </a>
2 <li>
<a href="papers/papers.html#aaaa">
Parallel Solution of Sparse Linear System of Equations </a>
5 <li>
<a href="papers/papers.html#ffff">
N-Body Computation and Dense Linear System Solvers
Types of data
• Numeric data: Each object is a point in a multidimensional space
• Categorical data: Each object is a vector of categorical values
• Set data: Each object is a set of values (with or without counts)
• Sets can also be represented as binary vectors, or vectors of counts
• Ordered sequences: Each object is an ordered sequence of values.
• Graph data
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 out of the data?
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 our
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 the extract the most prominent features of the data.
 Data Mining: A KDD Process

Pattern Evaluation
Data mining: the core of
knowledge discovery
Data Mining
process.
Task-relevant Data

Data Warehouse Selection & transformation

Data Cleaning

Data Integration

Databases
KDD Process
Data cleaning (to remove noise and inconsistent data)

Data integration (where multiple data sources may be combined)

Data selection (where data relevant to the analysis task are retrieved fromthe database)

Data transformation (where data are transformed or consolidated into forms appropriate for mining
by performing summary or aggregation operations, for instance)
Data mining (an essential process where intelligent methods are applied in order to extract data
patterns)
Pattern evaluation (to identify the truly interesting patterns representing knowledge based on some
interestingness measures)
Knowledge presentation (where visualization and knowledge representation techniques are used to
present the mined knowledge to the user)
Architecture of Data Mining
Contd.

Data Sources: Database, World Wide Web(WWW), and data warehouse are parts of data
sources. The data in these sources may be in the form of plain text, spreadsheets, or
other forms of media like photos or videos. WWW is one of the biggest sources of data.

Database Server: The database server contains the actual data ready to be processed. It
performs the task of handling data retrieval as per the request of the user.

Data Mining Engine: It is one of the core components of the data mining architecture that
performs all kinds of data mining techniques like association, classification,
characterization, clustering, prediction, etc.
Contd…

Pattern Evaluation Modules: They are responsible for finding interesting patterns in the data and
sometimes they also interact with the database servers for producing the result of the user
requests.

Graphic User Interface: Since the user cannot fully understand the complexity of the data mining
process so graphical user interface helps the user to communicate effectively with the data mining
system.

Knowledge Base: Knowledge Base is an important part of the data mining engine that is quite
beneficial in guiding the search for the result patterns. Data mining engines may also sometimes
get inputs from the knowledge base. This knowledge base may contain data from user
experiences. The objective of the knowledge base is to make the result more accurate and reliable.
What can we do with data mining?
• Some examples:
• Frequent itemsets and Association Rules extraction
• Coverage
• Clustering
• Classification
• Ranking
• Exploratory analysis
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!
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.
Illustrating Clustering
Euclidean Distance Based Clustering in 3-D space.

Intracluster
Intraclusterdistances
distances Intercluster
Interclusterdistances
distances
are
areminimized
minimized are
aremaximized
maximized
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.
Clustering of S&P 500 Stock Data

• Observe Stock Movements every day.

• Cluster stocks if they change similarly over time.

Discovered Clusters Industry Group

1
Applied-Matl-DOW N,Bay-Net work-Down,3-COM-DOWN,
Cabletron-Sys-DOWN,CISCO-DOWN,HP-DOWN,
DSC-Co mm-DOW N,INTEL-DOWN,LSI-Logic-DOWN,
Micron-Tech-DOWN,Texas-Inst-Down,Tellabs-Inc-Down,
Technology1-DOWN
Natl-Semiconduct-DOWN,Oracl-DOWN,SGI-DOW N,
Sun-DOW N

2
Apple-Co mp-DOW N,Autodesk-DOWN,DEC-DOWN,
ADV-M icro-Device-DOWN,Andrew-Corp-DOWN,
Co mputer-Assoc-DOWN,Circuit-City-DOWN,
Technology2-DOWN
Co mpaq-DOWN, EM C-Corp-DOWN, Gen-Inst-DOWN,
Motorola-DOW N,Microsoft-DOWN,Scientific-Atl-DOWN

3
Fannie-Mae-DOWN,Fed-Ho me-Loan-DOW N,
MBNA-Corp -DOWN,Morgan-Stanley-DOWN Financial-DOWN

4
Baker-Hughes-UP,Dresser-Inds-UP,Halliburton-HLD-UP,
Louisiana-Land-UP,Phillips-Petro-UP,Unocal-UP, Oil-UP
Schlu mberger-UP
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
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.
 Outlier Analysis

A database may contain data objects

Most data mining methods discard
that do not comply with the general These data objects are outliers.
outliers as noise or exceptions.
behavior or model of the data.

Outliers may be detected using

However, in some applications such
statistical tests that assume a Rather than using statistical or
as fraud detection, the rare events
distribution or probability model for distance measures, deviation-based
can be more interesting than the
the data, or using distance measures methods identify outliers by
more regularly occurring ones. The
where objects that are a substantial examining differences in the main
analysis of outlier data is referred to
distance from any other cluster are characteristics of objects in a group.
as outlier mining.
considered outliers.
Example

Outlier analysis may uncover fraudulent usage of credit cards by

detecting purchases of extremely large amounts for a given account
number in comparison to regular charges incurred by the same account.

Outlier values may also be detected with respect to the location and
type of purchase, or the purchase frequency
Evolution Analysis

• Data evolution analysis describes and models

regularities or trends for objects whose behavior
changes over time.
• This may include characterization,
discrimination, association and correlation
analysis, classification, prediction, or clustering
of time related data
• distinct features of such an analysis include time-
series data analysis, sequence or periodicity
pattern matching, and similarity-based data
analysis.
Example
• Suppose that you have the major stock market (time-series) data of the
last several years available from the New York Stock Exchange and
you would like to invest in shares of high-tech industrial companies.
• A data mining study of stock exchange data may identify stock
evolution regularities for overall stocks and for the stocks of particular
companies.
• Such regularities may help predict future trends in stock market prices,
contributing to your decision making regarding stock investments.
Link Analysis Ranking
• Given a collection of web pages that are linked to each other, rank the
pages according to importance (authoritativeness) in the graph
• Intuition: A page gains authority if it is linked to by another page.

• Application: When retrieving pages, the authoritativeness is factored

in the ranking.
Exploratory Analysis
• Trying to understand the data as a physical phenomenon, and describe
them with simple metrics
• What does the web graph look like?
• How often do people repeat the same query?
• Are friends in facebook also friends in twitter?

• The important thing is to find the right metrics and ask the right questions

• It helps our understanding of the world, and can lead to models of the
phenomena we observe.
Exploratory Analysis: The Web
• What is the structure and the properties of the web?
Exploratory Analysis: The Web
• What is the distribution of the incoming links?
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/
• High dimensionality AI Pattern
of data Recognition

• Heterogeneous, Data Mining

distributed nature
of data
• Emphasis on the use of data Database
systems
Data Mining: Research Trends
Exercise: generate frequent itemsets and
association rules
• minimum support count is 2
minimum confidence is 60%
minimum support count is 2
minimum confidence is 60%