Supervised vs.

Unsupervised
Learning

 Supervised learning (classification)

 Supervision: The training data (observations,
measurements, etc.) are accompanied by
labels indicating the class of the observations
 New data is classified based on the training
set
 Unsupervised learning (clustering)
 The class labels of training data is unknown
 Given a set of measurements, observations,
etc. with the aim of establishing the existence
of classes or clusters in the data 1
 Decision Tree
 Flowchart like tree structure
 Internal non leaf node denotes test on an
attribute
 Branch represents outcome of the test
 Leaf node holds a class label
 The topmost node of the tree is the root
node
 Decision Tree Induction: Training
Dataset

age income student credit_rating buys_computer

<=30 high no fair no
This <=30 high no excellent no
31…40 high no fair yes
follows >40 medium no fair yes
an >40 low yes fair yes
example >40 low yes excellent no
31…40 low yes excellent yes
of <=30 medium no fair no
Quinlan’s <=30 low yes fair yes
ID3 >40 medium yes fair yes
<=30 medium yes excellent yes
(Playing 31…40 medium no excellent yes
Tennis) 31…40 high yes fair yes
>40 medium no excellent no

3
 Output: A Decision Tree for
“buys_computer”

age?

<=30 overcast
31..40 >40

student? yes credit rating?

no yes excellent fair

no yes no yes

4
Why Decision Tree Classifier is so popular

 Does not require Domain Knowledge or

parameter settings
 Supports exploratory knowledge discovery
 Decision trees can handle high dimensional
data
 Decision tree knowledge is intuitive and
easily understandable by humans
 Learning and classification steps are simple
and fast
 Decision trees have good accuracy
 Explanation(Algorithm)
 The algorithm is called with three
parameters: D, attribute list, and Attribute selection
method.
 Let D as a data partition. Initially, it is the complete
set of training tuples and their associated class
labels.
 The parameter attribute list is a list of attributes
describing the tuples.
 Attribute selection method specifies a heuristic
procedure for selecting the attribute that “best”
discriminates the given tuples according to class.
7
 Attribute selection measure can be information gain
or the gini index.
 gini index, enforce the resulting tree to be binary.
 information gain, do not, therein allowing multiway
splits (i.e., two or more branches to be grown from a
node).

8
 The tree starts as a single node, N, representing the
training tuples in D (step 1).
 If the tuples in D are all of the same class, then
node N becomes a leaf and is labeled with that class
(steps 2 and 3).
 steps 4 and 5 are terminating conditions.
 All of the tuples in the partition D
belong to the same class(2,3)
 No remaining attributes on which the
tuples can be further partitioned(4,5)
 No tuples for a given branch(12,13)

 Otherwise, the algorithm calls Attribute selection

method to determine the splitting criterion.
9
 The splitting criterion tells us which attribute to test
at node N by determining the “best” way to
separate or partition the tuples in D into individual
classes (step 6).
 The splitting criterion is determined so that, ideally,
the resulting partitions at each branch are as
“pure” as possible.

all of the tuples in it belong to the same class

 The node N is labeled with the splitting criterion,

which serves as a test at the node (step 7).

10
 A branch is grown from node N for each of the outcomes of the splitting
criterion. The tuples in D are partitioned accordingly (steps 10 to 11).

There are three possible scenarios,

 Because all of the tuples in a given partition have
the same value for A, then A need not be considered
in any future partitioning of the tuples. Therefore, it
is removed from attribute list (steps 8 to 9).
 The algorithm uses the same process recursively to
form a decision tree for the tuples at each resulting
partition, Dj , of D (step 14)

12
 Attribute Selection Measure:
Information Gain (ID3/C4.5)
 Select the attribute with the highest information
gain
 Let pi be the probability that an arbitrary tuple in D
belongs to class Ci, estimated by |Ci, D|/|D|
m
 Expected information (entropy)
Info ( D) needed to classify
  pi log 2 ( pi )
a tuple in D: i 1

 Information needed (after using A to | D j | D into v

split
v
Info A ( D)  I ( D j )
partitions) to classify D: j 1 | D |

 Information gained by branching on attribute A

Gain(A) Info(D)  Info A(D)
13
 age income student credit_rating buys_computer
<=30 high no fair no
<=30 high no excellent no
31…40 high no fair yes
>40 medium no fair yes
>40 low yes fair yes
>40 low yes excellent no
31…40 low yes excellent yes
<=30 medium no fair no
<=30 low yes fair yes
>40 medium yes fair yes
<=30 medium yes excellent yes
31…40 medium no excellent yes
31…40 high yes fair yes
>40 medium no excellent no 14
 Attribute Selection: Information Gain
g Class P: buys_computer = 5 4
Info age ( D )  I (2,3)  I (4,0)
“yes” 14 14
g Class N: buys_computer = 5
9 9 5 5
Info ( D)“no”
I (9,5)  log 2 ( )  log 2 ( ) 0.940  I (3,2) 0.694
14 14 14 14 14
age pi ni I(p i, n i) 5
I (2,3) means “age <=30”
<=30 2 3 0.971 14
has 5 out of 14 samples,
31…40 4 0 0
with 2 yes’es and 3 no’s.
>40 3 2 0.971
age income student credit_rating buys_computer GainHence
(age) Info ( D )  Info age ( D ) 0.246
<=30 high no fair no
<=30 high no excellent no
31…40 high no fair yes
>40 medium no fair yes
>40 low yes fair yes Similarly,
>40
31…40
low
low
yes
yes
excellent
excellent
no
yes
Gain(income) 0.029
<=30 medium no fair no
<=30 low yes fair yes Gain( student ) 0.151
>40 medium yes fair yes
<=30
31…40
medium
medium
yes
no
excellent
excellent
yes
yes
Gain(credit _ rating ) 0.048
31…40 high yes fair yes
>40 medium no excellent no 15
 Computing Information-Gain for
Continuous-Value Attributes
 Let attribute A be a continuous-valued attribute
 Must determine the best split point for A
 Sort the value A in increasing order
 Typically, the midpoint between each pair of
adjacent values is considered as a possible split
point
 (ai+ai+1)/2 is the midpoint between the values of ai and
ai+1
 The point with the minimum expected
information requirement for A is selected as the
split-point for A
 Split: 16
 Gain Ratio for Attribute Selection
(C4.5)

 Information gain measure is biased towards

attributes with a large number of values
 C4.5 (a successor of ID3) uses gain ratio to
overcome the problem (normalization to
information gain) v |D | | Dj |
SplitInfo A ( D )  
j
log 2 ( )
j 1 |D| |D|

GainRatio(A) 4 4 6 6 4 4
SplitInfo A ( D ) = Gain(A)/SplitInfo(A)

log 2 ( )  log 2 ( )  log 2 ( ) 0.926
14 14 14 14 14 14
 Ex.
 gain_ratio(income) = 0.029/0.926 = 0.031
 The attribute with the maximum gain ratio is
selected as the splitting attribute
17
 Gini index (CART, IBM
IntelligentMiner)
 If a data set D contains examples from n classes, gini index,
gini(D) is defined as n
gini( D) 1  p 2j
j 1
where pj is the relative frequency of class j in D
 If a data set D is split on A into two subsets D1 and D2, the
gini index gini(D) is defined as| D | |D |
gini A ( D)  1 gini( D1)  2 gini( D 2)
|D| |D|
 Reduction in Impurity:
gini( A) gini( D)  giniA ( D)
 The attribute provides the smallest ginisplit(D) (or the largest
reduction in impurity) is chosen to split the node (need to
enumerate all the possible splitting points for each attribute)
18
 Gini index (CART, IBM
IntelligentMiner)
 Ex. D has 9 tuples in buys_computer = “yes” and 5 in “no”
2 2
9
    5
gini ( D) 1       0.459
 14   14 
 Suppose the attribute income partitions D into 10 in D1: {low,
medium} and 4 in Dgini  10   4
2 income{low, medium} ( D )   Gini ( D1 )    Gini ( D1 )
 14   14 

but gini{medium,high} is 0.30 and thus the best since it is the

lowest
 All attributes are assumed continuous-valued
 May need other tools, e.g., clustering, to get the possible split
values
 Can be modified for categorical attributes 19
DECISION TREES
Which Attribute is the Best Classifier?: Information
Gain

Let’s
investigate
the attribute
Wind

20
DECISION TREES
Which Attribute is the Best Classifier?: Information
Gain

The collection of examples has 9 positive values

and 5 negative ones

Eight (6 positive and 2 negative ones) of these

examples have the attribute value Wind = Weak

Six (3 positive and 3 negative ones) of these

examples have the attribute value Wind = Strong

21
DECISION TREES
Which Attribute is the Best Classifier?: Information
Gain

The information gain obtained by separating the

examples according to the attribute Wind is
calculated as:

22
DECISION TREES
Which Attribute is the Best Classifier?: Information
Gain
We calculate the Info Gain for each attribute and
select the attribute having the highest Info Gain

23
DECISION TREES
Example
Which attribute should be selected as the first test?

“Outlook” provides the most information

24
DECISION TREES

25
DECISION TREES
Example
The process of selecting a new attribute is now
repeated for each (non-terminal) descendant node,
this time using only training examples associated
with that node

Attributes that have been incorporated higher in

the tree are excluded, so that any given attribute
can appear at most once along any path through
the tree

26
DECISION TREES
Example

This process continues for each new leaf node until

either:

1. Every attribute has already been included along

this path through the tree

2. The training examples associated with a leaf

node have zero entropy

27
DECISION TREES
Example

28
DECISION TREES
From Decision Trees to Rules
Next Step: Make rules from the decision tree

After making the identification tree, we trace each

path from the root node to leaf node, recording the
test outcomes as antecedents and the leaf node
classification as the consequent

For our example we have:

If the Outlook is Sunny and the Humidity is High

then No
If the Outlook is Sunny and the Humidity is Normal
then Yes
29
...
 Measuring Error

Consider a Binary Classification Model derived from a two-class

dataset.
Let x be a test instance
Measuring Error

True Positive (TP):

Input Output
Classifie
+ve -> r -> +ve
False Positive(FP):
Classifie
-ve -> r -> +ve
False Negative(FN):
Classifie
+ve -> r -> -ve
True Negative(TN):
Classifie
r
-ve -> -> -ve
 Confusion matrix
 A confusion matrix is used to describe the performance of a
classification model (or “classifier”) on a set of test data for
which the true values are known.
 A confusion matrix is a table that categorizes predictions
according to whether they match the actual value.
 Confusion matrix
 If a classification system has been trained to
distinguish between cats, dogs and rabbits, a
confusion matrix will summarize the results of
testing the algorithm for further inspection.
Assuming a sample of 27animals-8 cats,6
dogs,and13 rabbits
 The resulting confusion matrix could look like the
table below:
 Recall,Precision:
 In machine learning, precision and recall are two measures
used to assess the quality of results produced by a binary
classifier.

 Recall:the ratio of the total number of correctly classified

positive examples divide to the total number of positive
examples.
 Recall tells us how many of the actual positive cases we were able
to predict correctly with our model.
 High Recall indicates the class is correctly recognized
 Precision:
 Precision:total number of correctly classified positive examples
by the total number of predicted positive examples.

 Precision tells us how many of the correctly predicted cases

actually turned out to be positive.
 High recall, low precision: This means that most of the
positive examples are correctly recognized (low FN) but there are
a lot of false positives.
 Low recall, high precision: This shows that we miss a lot of
positive examples (high FN) but those we predict as positive are
indeed positive (low FP)
 Precision & Recall
 Precision is a useful metric in cases where False Positive is a
higher concern than False Negatives.
 Recall is a useful metric in cases where False Negative trumps
False Positive.
 Recall is important in medical cases where it doesn’t matter
whether we raise a false alarm but the actual positive cases
should not go undetected!
 Classification Rate or Accuracy is given by
the relation:
 SLIQ – Supervised learning in Quest

 Scalable classifier
 Improving learning time without loss in
accuracy.
 Tree classifier.
 Handles both numerical and categorical
data
PARTITIONING AROUND MEDOIDS/ K-MEDOID
ALGORITHM

59
60
61
62
63
 (1,21
)

64
65
 K-Medoids algorithm
 Illustrate the working of K medoid algorithm
for the given dataset. A1=(3,9), A2=(2,5),
A3=(8,4), A4=(5,8), A5=(7,5), A6=(6,4),
A7=(1,2), A8=(4,9)
 Let’s solve the problem by setting K=3K =
3K=3 and using the first three
coordinates A1=(3,9)A1 = (3,9)A1=(3,9),
A2=(2,5)A2 = (2,5)A2=(2,5), and
A3=(8,4)A3 = (8,4)A3=(8,4) as the initial
medoids. We'll follow the steps of the K-
Medoids algorithm:
66
 Step 1: Initialize Medoids
 Initial medoids are:
• M1=A1M1 = A1M1=A1 ((3,9)(3,9)(3,9))
• M2=A2M2 = A2M2=A2 ((2,5)(2,5)(2,5))
• M3=A3M3 = A3M3=A3 ((8,4)(8,4)(8,4))
 Step 2: Assign Points to Clusters
 Using Manhattan distance, calculate the distance from
each point to the medoids and assign each point to the
cluster of the nearest medoid.
 Manhattan Distance Formula:
 d((x1,y1),(x2,y2))=∣x1−x2∣+∣y1−y2∣

67
68
69
70
Hierarchical Clustering
•Hierarchical decomposition of DB.
•Iterative splitting of DB until some termination condition is satisfied.
•Disadvantage: termination condition to be specified.
•2 types:
❑ Bottom up (Agglomerative)
❑ Top Down (Divisive)
DBSCAN
• Density-based spatial clustering of applications with noise

Clusters can be of arbitrary shape such as those shown

in the figure below.

Data may contain noise.

• DBSCAN algorithm requires two parameters:

[Link] : It defines the neighborhood around a data point.

• if the distance between two points is lower or equal to ‘eps’
then they are considered neighbors.
•If the eps value is chosen too small then large part of the data
will be considered as outliers. If it is chosen very large then the
clusters will merge and the majority of the data points will be in
the same clusters. One way to find the eps value is based on the k-
distance graph.

2. MinPts: Minimum number of neighbors (data points) within eps

radius.
• Larger the dataset, the larger value of MinPts must be chosen.
• As a general rule, the minimum MinPts can be derived from the
number of dimensions D in the dataset as, MinPts >= D+1. The
minimum value of MinPts must be chosen at least 3.
 In this algorithm, we have 3 types of data
points.

Core Point: A point is a core point if it has more

than MinPts points within eps.

Border Point: A point which has fewer than MinPts

within eps but it is in the neighborhood of a core
point.

Noise or outlier: A point which is not a core point or

border point.

Direct Density Reachable: A point p is DDR from point q

if q is the core point and P is the neighbor of q.

Density Reachable (DR): Two points are DR, if there is a

chain of DDR point that link these two points.
ALGORITHM
1. Find all the neighbor points within eps and identify the core points or visited with
more than MinPts neighbors.
2. For each core point if it is not already assigned to a cluster, create a new cluster.
3. Find recursively all its density connected points and assign them to the same
cluster as the core point.
A point a and b are said to be density connected if there exist a point c which has a
sufficient number of points in its neighbors and both the points a and b are within
the eps distance. This is a chaining process. So, if b is neighbor of c, c is neighbor
of d, d is neighbor of e, which in turn is neighbor of a implies that b is neighbor
of a.
4. Iterate through the remaining unvisited points in the dataset. Those points that do
not belong to any cluster are noise.
Categorical Clustering Algorithm

• ROCK stands for RObust Clustering using linKs.

• It is a hierarchical clustering algorithm that analyze
the concept of links (the number of common
neighbours among two objects) for data with
categorical attributes.
ROCK CLUSTERING
ALGORITHM
ROCK – RObust Hierarchical Clustering with
LinKs
NEIGHBORS AND LINKS
CRITERION FUNCTION
GOODNESS FUNCTION
ROCK CLUSTERING ALGORITHM
LABEL DATA ON DISK