Data mining Assignment
Shravan
ITS_632_Week6_ClusteringPartI.pptxDr. Oner Celepcikay
ITS 632
Data Mining
Algorithms: Clustering
Part I
Header – dark yellow 24 points Arial Bold
Body text – white 20 points Arial Bold, dark yellow highlights
Bullets – dark yellow
Copyright – white 12 points Arial
Size:
Height: 7.52"
Width: 10.02"
Scale: 70%
Position on slide:
Horizontal - 0"
Vertical - 0"
Finding groups of objects such that the objects in a group will be similar (or related) to one another and different from (or unrelated to) the objects in other groups
Clustering Analysis
ITS 632
Inter-cluster distances are maximized
Intra-cluster distances are minimized
Header – dark yellow 24 points Arial Bold
Body text – white 20 points Arial Bold, dark yellow highlights
Bullets – dark yellow
Copyright – white 12 points Arial
Size:
Height: 7.52"
Width: 10.02"
Scale: 70%
Position on slide:
Horizontal - 0"
Vertical - 0"
Supervised Learning
Unsupervised Learning
ITS 632
Clustering Analysis
Header – dark yellow 24 points Arial Bold
Body text – white 20 points Arial Bold, dark yellow highlights
Bullets – dark yellow
Copyright – white 12 points Arial
Size:
Height: 7.52"
Width: 10.02"
Scale: 70%
Position on slide:
Horizontal - 0"
Vertical - 0"
ITS 632
Notion of a Cluster can be Ambiguous
How many clusters?
Four Clusters
Two Clusters
Six Clusters
Header – dark yellow 24 points Arial Bold
Body text – white 20 points Arial Bold, dark yellow highlights
Bullets – dark yellow
Copyright – white 12 points Arial
Size:
Height: 7.52"
Width: 10.02"
Scale: 70%
Position on slide:
Horizontal - 0"
Vertical - 0"
Partitional Clustering
A division data objects into non-overlapping subsets (clusters) such that each data object is in exactly one subset
Hierarchical Clustering
A set of nested clusters organized as a hierarchical tree
ITS 632
Types of Clustering
Header – dark yellow 24 points Arial Bold
Body text – white 20 points Arial Bold, dark yellow highlights
Bullets – dark yellow
Copyright – white 12 points Arial
Size:
Height: 7.52"
Width: 10.02"
Scale: 70%
Position on slide:
Horizontal - 0"
Vertical - 0"
ITS 632
Partitional Clustering
Original Points
A Partitional Clustering
Header – dark yellow 24 points Arial Bold
Body text – white 20 points Arial Bold, dark yellow highlights
Bullets – dark yellow
Copyright – white 12 points Arial
Size:
Height: 7.52"
Width: 10.02"
Scale: 70%
Position on slide:
Horizontal - 0"
Vertical - 0"
ITS 632
Hierarchical Clustering
Header – dark yellow 24 points Arial Bold
Body text – white 20 points Arial Bold, dark yellow highlights
Bullets – dark yellow
Copyright – white 12 points Arial
Size:
Height: 7.52"
Width: 10.02"
Scale: 70%
Position on slide:
Horizontal - 0"
Vertical - 0"
Clusters Defined by an Objective Function
Finds clusters that minimize or maximize an objective function.
Enumerate all possible ways of dividing the points into clusters and evaluate the `goodness' of each potential set of clusters by using the given objective function.
Parameters for the model are determined from the data.
ITS 632
Types of Clustering: Objective Function
Header – dark yellow 24 points Arial Bold
Body text – white 20 points Arial Bold, dark yellow highlights
Bullets – dark yellow
Copyright – white 12 points Arial
Size:
Height: 7.52"
Width: 10.02"
Scale: 70%
Position on slide:
Horizontal - 0"
Vertical - 0"
Map the clustering problem to a different domain
Proximity matrix defines a weighted graph, where the nodes are the points being clustered, and the weighted edges represent the proximities between points
Clustering is equivalent to breaking the graph into connected components, one for each cluster.
Want to minimize the edge weight between clusters and maximize the edge weight within clusters
ITS 632
Types of Clustering: Objective Function
Header – dark yellow 24 points Arial Bold
Body text – white 20 points Arial Bold, dark yellow highlights
Bullets – dark yellow
Copyright – white 12 points Arial
Size:
Height: 7.52"
Width: 10.02"
Scale: 70%
Position on slide:
Horizontal - 0"
Vertical - 0"
K-means and its variants
Hierarchical clustering
Density-based clustering
ITS 632
Clustering Algorithms
Header – dark yellow 24 points Arial Bold
Body text – white 20 points Arial Bold, dark yellow highlights
Bullets – dark yellow
Copyright – white 12 points Arial
Size:
Height: 7.52"
Width: 10.02"
Scale: 70%
Position on slide:
Horizontal - 0"
Vertical - 0"
Partitional clustering approach
Each cluster is associated with a centroid (center point)
Each point is assigned to the cluster (closest centroid)
Number of clusters, K, must be specified
The basic algorithm is very simple
K-means Clustering
ITS 632
Header – dark yellow 24 points Arial Bold
Body text – white 20 points Arial Bold, dark yellow highlights
Bullets – dark yellow
Copyright – white 12 points Arial
Size:
Height: 7.52"
Width: 10.02"
Scale: 70%
Position on slide:
Horizontal - 0"
Vertical - 0"
Initial centroids are often chosen randomly.
Clusters produced vary from one run to another.
The centroid is the mean of the points in the cluster.
‘Closeness’ is measured by Euclidean distance, cosine similarity, correlation, etc.
K-means will converge for common similarity measures mentioned above.
Most of the convergence happens in first few iterations.
K-means Clustering
ITS 632
Header – dark yellow 24 points Arial Bold
Body text – white 20 points Arial Bold, dark yellow highlights
Bullets – dark yellow
Copyright – white 12 points Arial
Size:
Height: 7.52"
Width: 10.02"
Scale: 70%
Position on slide:
Horizontal - 0"
Vertical - 0"
ITS 632
K-means Clustering in Action
Header – dark yellow 24 points Arial Bold
Body text – white 20 points Arial Bold, dark yellow highlights
Bullets – dark yellow
Copyright – white 12 points Arial
Size:
Height: 7.52"
Width: 10.02"
Scale: 70%
Position on slide:
Horizontal - 0"
Vertical - 0"
ITS 632
K-means Clustering in Action
Header – dark yellow 24 points Arial Bold
Body text – white 20 points Arial Bold, dark yellow highlights
Bullets – dark yellow
Copyright – white 12 points Arial
Size:
Height: 7.52"
Width: 10.02"
Scale: 70%
Position on slide:
Horizontal - 0"
Vertical - 0"
ITS 632
K-means Clustering in Action
K-Means Animation
Header – dark yellow 24 points Arial Bold
Body text – white 20 points Arial Bold, dark yellow highlights
Bullets – dark yellow
Copyright – white 12 points Arial
Size:
Height: 7.52"
Width: 10.02"
Scale: 70%
Position on slide:
Horizontal - 0"
Vertical - 0"
ITS 632
Importance of Choosing Initial Centroids
Header – dark yellow 24 points Arial Bold
Body text – white 20 points Arial Bold, dark yellow highlights
Bullets – dark yellow
Copyright – white 12 points Arial
Size:
Height: 7.52"
Width: 10.02"
Scale: 70%
Position on slide:
Horizontal - 0"
Vertical - 0"
ITS 632
Importance of Choosing Initial Centroids
Header – dark yellow 24 points Arial Bold
Body text – white 20 points Arial Bold, dark yellow highlights
Bullets – dark yellow
Copyright – white 12 points Arial
Size:
Height: 7.52"
Width: 10.02"
Scale: 70%
Position on slide:
Horizontal - 0"
Vertical - 0"
Multiple runs
Helps, but probability is not on your side
Sample & use hierarchical clustering to find K centroids
Select more than K initial centroids and then select among these initial centroids
Select most widely separated
Postprocessing
Solutions to Initial Centroids Problem
ITS 632
Header – dark yellow 24 points Arial Bold
Body text – white 20 points Arial Bold, dark yellow highlights
Bullets – dark yellow
Copyright – white 12 points Arial
Size:
Height: 7.52"
Width: 10.02"
Scale: 70%
Position on slide:
Horizontal - 0"
Vertical - 0"
Most common measure is Sum of Squared Error (SSE)
For each point, error is the distance to the nearest cluster
To get SSE, we square these errors and sum them.
Given two clusters, choose the one with the smallest error
One easy way to reduce SSE is to increase K,
A good clustering with smaller K can have a lower SSE than a poor clustering with higher K.
Evaluating K-means Clusters
ITS 632
Header – dark yellow 24 points Arial Bold
Body text – white 20 points Arial Bold, dark yellow highlights
Bullets – dark yellow
Copyright – white 12 points Arial
Size:
Height: 7.52"
Width: 10.02"
Scale: 70%
Position on slide:
Horizontal - 0"
Vertical - 0"
Hierarchical Clustering
Evaluating Clustering
Clustering Python Lab
Introduction to Pandas
Visualization using Seaborn
Clustering using K-Means
Classification using Decision Trees
Next Week(s)
ITS 632
Header – dark yellow 24 points Arial Bold
Body text – white 20 points Arial Bold, dark yellow highlights
Bullets – dark yellow
Copyright – white 12 points Arial
Size:
Height: 7.52"
Width: 10.02"
Scale: 70%
Position on slide:
Horizontal - 0"
Vertical - 0"
-2
-1.5
-1
-0.5
0
0.5
1
1.5
2
0
0.5
1
1.5
2
2.5
3
x
y
Iteration 1
-2
-1.5
-1
-0.5
0
0.5
1
1.5
2
0
0.5
1
1.5
2
2.5
3
x
y
Iteration 2
-2
-1.5
-1
-0.5
0
0.5
1
1.5
2
0
0.5
1
1.5
2
2.5
3
x
y
Iteration 3
-2
-1.5
-1
-0.5
0
0.5
1
1.5
2
0
0.5
1
1.5
2
2.5
3
x
y
Iteration 4
-2
-1.5
-1
-0.5
0
0.5
1
1.5
2
0
0.5
1
1.5
2
2.5
3
x
y
Iteration 5
-2
-1.5
-1
-0.5
0
0.5
1
1.5
2
0
0.5
1
1.5
2
2.5
3
x
y
Iteration 6
-2
-1.5
-1
-0.5
0
0.5
1
1.5
2
0
0.5
1
1.5
2
2.5
3
x
y
Iteration 1
-2
-1.5
-1
-0.5
0
0.5
1
1.5
2
0
0.5
1
1.5
2
2.5
3
x
y
Iteration 2
-2
-1.5
-1
-0.5
0
0.5
1
1.5
2
0
0.5
1
1.5
2
2.5
3
x
y
Iteration 3
-2
-1.5
-1
-0.5
0
0.5
1
1.5
2
0
0.5
1
1.5
2
2.5
3
x
y
Iteration 4
-2
-1.5
-1
-0.5
0
0.5
1
1.5
2
0
0.5
1
1.5
2
2.5
3
x
y
Iteration 5
å
å
=
Î
=
K
i
C
x
i
i
x
m
dist
SSE
1
2
)
,
(
