Machine

Learning
Introduction
Machine
Learning

Functionaliti
es

Outline
Introduction
Mining

Associations
Classification
Numeric
Prediction
Cluster Analysis
Interesting
Patterns
References

Rules

Introducti
on

Introduction
Machine

Learning tasks

Descriptive Machine Learning

+

characterize the general properties of the data

in the database.

Predictive Machine Learning

+

perform inference on the current data in order

to make predictions.

Introduction
Different

views lead to different

of
classifications
Machine
Learning
Data view:
Kindsfunctionalities:
of data to be mined
+

e.g. numeric, categorical, mixed, &

Knowledge view: Kinds of knowledge

to be discovered
+

e.g. decision tree, classification rules, &

Method view: Kinds of techniques

utilized

e.g. neural networks, SVM, &

Application view: Kinds of applications

adapted
+

e.g. marketing, medicine, railway, &

Introduction
Knowledge

view
Machine Learning functionalities are used to
kind of patterns
specify
the
to be
found
Main
functionalities
Mining
Association

Rules
Classification
Numeric Prediction
Cluster Analysis

in dat minin tasks

a
g
.

Mining Association
Rules

Frequent Patterns
Frequent

patterns are
occur
patterns that
frequently in data.
The
kinds of frequent
patternsa set of items
Frequent
itemsets patterns:
that frequently
refers
to
appear together in a
transactional data
set, such as milk and bread.
Frequent sequential patterns: such as the
pattern that customers tend to purchase first
a PC, followed by a digital camera, and then
a memory
is a (frequent)
sequential
Mining
frequentcard,
patterns
leads to the
discovery
pattern.
of
interesting associations and correlations
within data.

Association Rules
Suppose,

as a marketing manager of
AllElectronics, you would like to determine
which items are frequently purchased
together within the same transactions.
An example of association rule from the
AllElectronics transactional database, is:

where X is a variable representing a

customer.

Association Rules

A confdence, 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% rule support means that 1% of all
of the transactions under analysis
showed that
computer and software were purchased
together.
This association rule involves a single
attribute
or predicate (i.e., buys) that repeats.

Association Rules
We

may find association rules

like:
The rule indicates that of the AllElectronics customers
to
under
study, 2% are 20 to 29 years of age with an income
of 20,000
29,000 and have purchased a CD player at
AllElectronics.

ThisThere
is an
more
than
is aassociation
60% probabilitybetween
that a customer
in this
one age and income group will purchase a CD player.

attribute (i.e., age, income, and buys).

This is a multidimensional
association rule.

Support and confidence of a rule

Example:

4 cool days with normal

humidity
Support = 4, confidence =
100% minimum support and confidence
Normally:
prespecified,
e.g. support >= 2 and confidence >= 95% for
weather data

Interpreting associationrules
Interpretation

is
is

not the
same
It

no obvious
t :

as

means that the following

holds:
also

Association Rules
Large

number of possible
associations
Output needs to be restricted to show only
the most
predictive associations

Association

rules are interesting if they do

satisfy
both:
A minimum support threshold: number of
instances
predicted correctly
A minimum confdence threshold: number
of correct predictions, as proportion of all
instances that rule applies to

Association Rules

Association

learning is
unsupervised
nonnumeric
Association rules usually involve
only attributes
to uncover
interestinganalysis
statistical
Additional
can correlations
be
between
performed
associated attribute-value pairs.

Association Rules
Examples

of association rule
algorithms:
Apriori Algorithm
FP-growth Algorithm
Tree-Projection algorithm
ECLAT (Equivalence CLASS
Transformation)
algorithm

Classification

Classification

Classifcation
Construct models (functions) that describe
and
distinguish classes or concepts to predict the
class of objects whose class label is unknown

Example:

In weather problem the play or dont play

judgment
In contact lenses problem the lens
Classification learning is
recommendation
supervised
Process is provided with actual
outcome

Training vs. Test Data Set

Training

data

set The derived model is based on the analysis of

a set
of training data (i.e., data objects whose
class label is known).

Test

data

set Using an independent set of test data for

which class
labels are known but not made available
to the machine.
This data set is used to evaluate the
success of classification learning

Classification
Examples

of classification

output:
Decision tree
Classifcation
rules
Neural
networks

Decision trees
Divide

and conquer approach produces

decision tree
Nodes involve testing a particular
attribute
Usually, attribute value is compared to
constant
Comparing values of two attributes
Other
possibilities:
Using
a function of one or more
attributes

Decision trees
Leaf

nodes

give a classification that applies to all

instances that
reach the leaf
set of classifications
probability distribution over all possible

To classifications

classify an unknown instance,

it is routed down the tree according to the
values of the attributes tested in successive
nodes, and
when a leaf is reached the instance is
classified according to the class assigned
to the leaf.

Nominal and numeric attributes

If

the attribute is
nominal:
Number of children usually equal to the
number of
possible values
Usually attribute wont get tested more
If the attribute is
than once
numeric:
Test whether value is
less than
constant
greater or
Attribute may get tested times
several
(or multi-way
+ Integer: less than, equal to, greater
than
Other
possibility: three-waysplit)
split
+ Real: below, within, above

Decision tree for the labor data

Classification rules
Popular

alternative to decision

trees
Rules
include two
parts:
Antecedent
or precondition:
a series of tests just like the tests at of a
decision
the nodes tree
+ Tests are usually logically ANDed
together
+

All the tests must succeed if the rule is to

fire
+ The class or set of classes or probability distribution
Consequent
or conclusion:
assigned
by rule

Example:

A rule from contact lens problem

From trees to rules

Easy:

converting a tree into a set of

rules
One rule for each leaf:
+

Antecedent contains a condition for every node

on the path from the root to the leaf
Consequent is class assigned by the leaf

Produces

rules that are very

clear
Doesnt matter in which order they are
executed

But:

resulting rules are unnecessarily

complex
It needs to remove redundant
tests/rules

From rules to trees

More

difficult: transforming a rule set into

a tree
Tree cannot easily express disjunction
between rules

Example:

attributes

rules which test different

From rules to trees

The exclusive-or
problem

A tree with a replicated subtree

If

it is possible to have a default rule that

covers
cases not specified by the other rules,
rules are much more compact than trees
There are four attributes, x, y, z, and w,
each can be 1, 2, or 3

A tree with a replicated subtree

Replicated

identical
subtrees

subtree problem: tree contains

Executing a rule set

Two

ways of executing a rule

set:
Ordered set of rules (decision list)
+

Order is important for interpretation

Unordered set of rules

+

Rules may overlap and lead to differentfor the

conclusions same instance

Neural Network
A

neural network, when used for classification,

is
typically a collection of neuron-like processing
units with weighted connections between the
units.

Classification Techniques
Examples

of
classifcation
Decision Trees

techniques:

Classification Rules
Neural Network
Nave Bayesian
classification
Support vector machines
k-nearest neighbor
classification

Classification vs. Association Analysis

Difference

association analysis to
classification
learning:
Can predict any attributes value, not just
the class
More than one attributes value at a time
There are more association rules than
classification rules

Numeric
Prediction

Numeric prediction
Numeric

prediction:
predicting a numeric
quantity

Numeric

prediction is a variant of
classification
learning in which the outcome is a
numeric value rather than a category.
Learning
Processisissupervised
being provided with target
value

Measure

data

success on test

Numeric prediction
A

version of the weather data in which what is

to be
predicted is the time (in minutes) to play

Numeric prediction

To

find the important attributes and how

they
relate to the numeric outcome is more
important than predicting value for new
instances.

Numeric prediction
Representing

numeric

prediction:
Linear regression equation: an equation to
predicts
a numeric quantity
Regression tree: a decision tree where
each leaf predicts a numeric quantity
+

Predicted value is average value of training

instances that reach the leaf

Model tree: a regression tree with linear

regression models at the leaf nodes

Linear regression equation

Linear

data

regression equation for CPU

Regression tree
Regression

data

tree for the CPU

Regression tree
We

calculate the average of the absolute

values
of the errors between the predicted
and the actual CPU performance
measures,
It turns out to be significantly less for
the tree than for the regression
equation.

Model tree
Model

data

tree for the CPU

Cluster Analysis

Cluster Analysis

Clustering
grouping similar instances into
clusters

Clustering

is
unsupervised
The class of an example is not
known

Example:

a version of the iris data in which of iris is

the type
omitted
Then it is likely that the 150 instances fall into
natural
clusters corresponding to the three iris types.

Iris data as a clustering problem

Cluster Analysis
A 2-D plot of customer data with respect to customer locations
in a city,
showing three data clusters. Each cluster center is marked
with a +.

Clustering
Clustering

may be followed by a second

step of
classification learning in which rules are
learned that give an intelligible
description of how new instances should
be placed into the clusters.

Representing clusters
The

output takes the form of a diagram that

shows
how the instances fall into clusters.
Different
cases:
2D representation: involves
Simple
associating a cluster number with each
instance

Venn diagram: allow one instance to

belong to more than one cluster

Probabilistic assignment: associate

instances with clusters probabilistically

Dendrogram: produces a hierarchical

structure of clusters (dendron is the Greek
word for tree)

Representing clusters

Representing clusters

Clustering
Examples

of clustering

algorithm:
k-Means algorithm

k-medoids algorithm
AGNES (AGglomerative
NESting)
DIANA (DIvisive ANAlysis)
BIRCH (Balanced Iterative
Reducing
Using Hierarchies)

and Clustering

Interesting
Patterns

Interesting Patterns
Machine

Learning may generate

thousands
Not all of them are interesting
What makes a pattern
interesting?
1. Easily understood by humans,

of
patterns:

2. Valid on new or test data with someof

degree certainty
3. Potentially useful
4. Novel
5. Validates some hypothesis that a user
seeks to
confirm

Interesting Patterns
Objective

vs. subjective interestingness

measures
Objective: based on statistics and of
structures
e.g.,
support,
confidence,
patterns,
Subjective:
based
on users
belief in the
etc.
data, e.g.,
unexpectedness, novelty, actionability, etc.

References

References
Ian

H. Witten and Eibe Frank, Machine

Learning:
Practical Machine Learning Tools
and Techniques, 2nd Edition, Elsevier
Inc., 2005. (Chapter 2 & 3)
J. Han, M. Kamber, Machine Learning:
Concepts and
Techniques, Elsevier Inc. 2006. (Chapter
1)

The
end