Module 3
Decision Tree & Clustering
Decision trees
• Decision tree learning is a method for approximating discrete valued
target functions, in which the learned function is represented by a
decision tree.
Two types of decision trees
1. Classification trees: Tree models where the target variable can take
a discrete set of values are called classification trees.
2. Regression Trees
Example
Splitting Indices: Feature selection measures
• If a dataset consists of n attributes then deciding which attribute is to
be to placed at the root or at different levels of the tree as internal
nodes is a complicated problem.
• These are called the feature selection measures.
• Two of the popular feature selection measures are information gain
and Gini index.
Entropy
• The degree to which a subset of examples contains only a single class is known
as purity, and any subset composed of only a single class is called a pure class.
• Informally, entropy is a measure of “impurity” in a dataset.
• Sets with high entropy are very diverse
• Entropy is measured in bits.
• If there are only two possible classes, entropy values can range from 0 to 1.
• For n classes, entropy ranges from 0 to log2(n).
• In each case, the minimum value indicates that the sample is completely
homogeneous, while the maximum value indicates that the data are as diverse
as possible.
Definition
• Consider a segment S of a dataset having c number of class labels.
Let pi be the proportion of examples in S having the i class label.
• The entropy of S is defined as
Information gain
• Let S be a set of examples, A be a feature (or, an attribute), Sv be the
subset of S with A = v, and Values (A) be the set of all possible values
of A. Then the information gain of an attribute A relative to the set S,
denoted by Gain (S;A), is defined as
Gini index
• It is a measure of diversity
• Best splitter- Attribute with smallest Gini value
Gini Split Index
The ID3 algorithm
• Developed by Ross Quinlan
• Iterative Dichotomiser 3
• Assumptions
• The algorithm uses information gain to select the
most useful attribute for classification.
• Assume that there are only two class labels,
namely, “+” and “−”. The examples with class
labels “+” are called positive examples and others
negative examples.
Clustering
• Introduction to clustering
• Clustering or cluster analysis is the task of grouping a set of
objects in such a way that objects in the same group (called a
cluster) are more similar (in some sense) to each other than to
those in other groups (clusters).
Measures of dissimilarity
• In order to decide which clusters should be combined, or where a
cluster should be split , a measure of dissimilarity between sets of
observations is required.
• Measures of distance between data points
• Numeric Data
City Block Distance /
• Minkowski distance: It is the generalized form of the Euclidean
and Manhattan Distance Measure. In an N-dimensional space, a
point is represented as,
Non-numeric data
• The Levenshtein distance is a measure of the ”distance” between two
words.
• The Levenshtein distance between two words is the minimum
number of single-character edits (insertions, deletions or
substitutions) required to change one word into the other.
• For example, the Levenshtein distance between “kitten” and “sitting”
is 3, since the following
• three edits change one into the other, and there is no way to do it with fewer
than three edits:
• Kitten : sitten (substitution of “s” for “k”)
• sitten : sittin (substitution of “i” for “e”)
• sittin : sitting (insertion of ‘g” at the end)
Clustering Methods
• Hierarchical vs Partitioning
• Partitioning: K-means, K-medoid, k-mode
• Hierarchical: Agglomerative, Divisive
• Numerical vs Categorical
PAM- Partition Around Medoid
1. Initialize: select k random points out of the n data points as the
medoids.
2. Associate each data point to the closest medoid by using any
common distance metric methods.
3. While the cost decreases: For each medoid ‘m’, for each data
point ‘o’ which is not a medoid:
1. Swap m and o, associate each data point to the closest medoid, and
recompute the cost.
2. If the total cost is more than that in the previous step, undo the swap.
Example
• Step 1: Let the randomly selected 2 medoids, so select k = 2,
and let C1 -(4, 5) and C2 -(8, 5) are the two medoids.
• Step 2: Calculating cost. The dissimilarity of each non-
medoid point with the medoids is calculated and tabulated:
• Here we have used Manhattan distance formula.
• That formula tell that Distance = |X1-X2| + |Y1-Y2|.
• Each point is assigned to the cluster of that medoid whose
dissimilarity is less.
• Points 1, 2, and 5 go to cluster C1 and 0, 3, 6, 7, 8 go to cluster
C2. The Cost = (3 + 4 + 4) + (3 + 1 + 1 + 2 + 2) = 20
• Step 3: randomly select one non-medoid point and
recalculate the cost. Let the randomly selected point be (8, 4).
• The dissimilarity of each non-medoid point with the medoids –
C1 (4, 5) and C2 (8, 4) is calculated and tabulated.
• Each point is assigned to that cluster whose dissimilarity is less.
So, points 1, 2, and 5 go to cluster C1 and 0, 3, 6, 7, 8 go to
cluster C2.
• The New cost = (3 + 4 + 4) + (2 + 2 + 1 + 3 + 3) = 22 Swap
Cost = New Cost – Previous Cost = 22 – 20 and 2 >0
• As the swap cost is not less than zero, we undo the swap.
• Hence (4, 5) and (8, 5) are the final medoids.
Problem
• 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).
A1 3 9
A2 2 5
A3 8 4
A4 5 8
A5 7 5
A6 6 4
A7 1 2
A8 4 9
Data X Y Dist Dist Let C1= (2,5) and C2= (7,5)
fro fro
m m
C1 C2 Groups- G1=(A1, A7, A8)
A1 3 9 5 8 G2=(A3, A4, A6)
A2 2 5 - - Cost(G1)= 5+4+6=15
A3 8 4 7 2 Cost(G2)=2+5+2=9
A4 5 8 6 5 Total Cost= 24
A5 7 5 - -
A6 6 4 5 2 Swap/ Change medoid (2,5) to
A7 1 2 4 9 (3,9)
A8 4 9 6 7
Data X Y Dist Dist Let C1= (3,9) and C2= (7,5)
fro fro
m m
C1 C2 Groups- G1=(A4, A7, A8)
A1 3 9 - - G2=(A2, A3, A6)
A2 2 5 5 5 Cost(G1)= 3+9+8=20
A3 8 4 10 2 Cost(G2)=5+2+2=9
A4 5 8 3 5 New_Total Cost= 29
A5 7 5 - -
A6 6 4 8 2 New_total cost> old total cost
A7 1 2 9 9
A8 4 9 1 7 Swapping cancelled
• Final Medoid Groups are
G1=(A1, A7, A8)
G2=(A3, A4, A6)
DBSCAN
• Density-Based Spatial Clustering of Applications with Noise.
• In density-based clustering, clusters are defined as areas of higher
density than the remainder of the data set.
• Objects in these sparse areas - that are required to separate clusters -
are usually considered to be noise and border points.
• The most popular density based clustering method is DBSCAN
Clusters of points and noise points
Why DBSCAN?
• Partitioning methods are suitable only for compact and well-separated clusters.
• Moreover, they are also severely affected by the presence of noise and outliers in
the data.
• Real life data may contain irregularities, like:
1. Clusters can be of arbitrary shape such as those shown in the figure below.
2. Data may contain noise.
• DBSCAN algorithm requires two parameters:
1. eps (Є ): It defines the neighborhood around a data point i.e. if
the distance between two points is lower or equal to ‘eps’ then
they are considered neighbors.
2. MinPts: Minimum number of neighbors (data points) within
eps radius. Larger the dataset, the larger value of MinPts
must be chosen. 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 Є distance.
• Border Point: A point which has fewer than MinPts within Є but it is
in the neighborhood of a core point.
• Noise or outlier: A point which is not a core point or border point.
Let MinPts = 4 Let MinPts = 4 Let MinPts = 4
P- core point P- border point r- noise point
Algorithmic steps for DBSCAN clustering
• The algorithm proceeds by arbitrarily picking up a point in the
dataset (until all points have been visited).
• If there are at least ‘minPoint’ points within a radius of ‘ε’ to the
point then we consider all these points to be part of the same
cluster.
• The clusters are then expanded by recursively repeating the
neighborhood calculation for each neighboring point
Categorical Clustering-ROCK
• Robust clustering Using Links
• ROCK belongs to the class of Agglomerative
Hierarchical clustering Algorithm
• ROCK works for categorical attributes
• The steps involved in clustering using ROCK are described in Figure. After
drawing a random sample from the database, a hierarchical clustering
algorithm that employs links is applied to the sampled points. Finally, the
clusters involving only the sampled points are used to assign the remaining
data points on disk to the appropriate clusters.
Measures used
• Neighbors : Given a threshold Ɵ between 0 and 1, a pair of points pi
and pj are defined to be neighbors if the following holds:
• Jaccard coefficient, for sim(T1; T2),
•
1) Similarity Table
Example
P1 P2 P3 P4
P1= {A,B,C,D} P1 1
P2={E,B,C} P2 1
P3={D,E,B} P3 1
P4={E,C,F} P4 1
Similarity threshold= 0.3
No of clusters=2
2) Adjacency Table
Example
P1 P2 P3 P4
P1= {A,B,C,D}
P2={E,B,C} P1 1 1 1 0
P3={D,E,B} P2 1 1 1
P4={E,C,F} P3 1 0
Similarity threshold= 0.3
No of clusters=2
P4 1
3) No. of Links/ common
neighbours
Example
P1= {A,B,C,D}
P2={E,B,C}
P3={D,E,B}
P4={E,C,F}
P1 P2 P3 P4
Similarity threshold= 0.3
No of clusters=2 P1 -
P2 -
P3 -
P4 -
4) Goodness Measure
Pair Goodness
Measure
1.35
1.35
0.45
1.35
P1, P2 P3 P4
0.90
P1, P2 -
0.45
P3 -
P4 -
P1 P2 P3 P4
P1 - 3 3 1
P2 - 3 2
P3 - 1
P4 -
New Link Matrix
P1, P2 P3 P4
P1, P2 - 6 3
P3 - 1
P4 -
Goodness of Measure
Pair Goodness
Measure
1.31
0.66
0.22
THANK YOU