Data Mining
PROF. DR. MUHAMMAD SHAHBAZ
DEPARTMENT OF COMPUTER ENGINEERING
UNIVERSITY OF ENGINEERING AND TECHNOLOGY, LAHORE
Clustering
Unsupervised learning
Supervised learning
Predict target value (“y”) given features (“x”)
Unsupervised learning
Understand patterns of data (just “x”)
Useful for many reasons
Data mining (“explain”)
Missing data values (“impute”)
Representation (feature generation or selection)
One example: clustering
What is Clustering ?
Cluster: A collection of data objects
Inter-clusters distance maximization
Intra-clusters distance minimization
Clustering
“Grouping a set of data objects into clusters according to their similarity”
Clustering is unsupervised classification: no predefined classes
Major Types of Clustering Algorithms
Partitioning:
Partition the database into k clusters which are
represented by representative objects of them
Hierarchical:
Decompose the database into several levels of
partitioning which are represented by dendrogram
Euclidean distance
n
d euc (x, y) i i
( x
i 1
y ) 2
Here n is the number of dimensions in the data
vector. For instance:
Clustering - Definition
─ Process of grouping similar items together
─ Clusters should be very similar to each other but…
─ Should be very different from the objects of other
clusters/ other clusters
─ We can say that intra-cluster similarity between
objects is high and inter-cluster similarity is low
─ Important human activity --- used from early
childhood in distinguishing between different items
such as cars and cats, animals and plants etc.
Types of Clustering Algorithms
Classification vs. Clustering
Classification:
Supervised learning:
Learns a method for
predicting the instance
class from pre-labeled
(classified) instances
Clustering
Unsupervised learning:
Finds “natural” grouping of
instances given un-labeled data
Clustering Evaluation
Manual inspection
Benchmarking on existing labels
Cluster quality measures
distance measures
high similarity within a cluster, low across clusters
The Distance Function
Simplest case: one numeric attribute A
Distance(X,Y) = A(X) – A(Y)
Several numeric attributes:
Distance(X,Y) = Euclidean distance between X,Y
Are all attributes equally important?
Weighting the attributes might be necessary
Simple Clustering: K-means
Works with numeric data only
1) Pick a number (K) of cluster centers (at random)
2) Assign every item to its nearest cluster center (e.g. using
Euclidean distance)
3) Move each cluster center to the mean of its assigned
items
4) Repeat steps 2,3 until convergence (change in cluster
assignments less than a threshold)
K-means example, step 1
k1
Y
Pick 3
k2
initial
cluster
centers
(randomly)
k3
X
K-means example, step 2
k1
Y
k2
Assign
each point
to the closest
cluster
center k3
X
K-means example, step 3
k1 k1
Y
Move k2
each cluster
center k3
k2
to the mean
of each cluster k3
X
K-means example, step 4
Reassign k1
points Y
closest to a
different new
cluster center
k3
Q: Which k2
points are
reassigned?
X
K-means example, step 4 …
k1
Y
A: three
points with
animation k3
k2
X
K-means example, step 4b
k1
Y
re-compute
cluster
means k3
k2
X
K-means example, step 5
k1
Y
k2
move cluster
centers to k3
cluster means
X
Squared Error Criterion
Hierarchical clustering
Agglomerative Clustering
Start with single-instance clusters
At each step, join the two closest clusters
Design decision: distance between clusters
Divisive Clustering
Start with one universal cluster
Find two clusters
Proceed recursively on each subset
Can be very fast
Both methods produce a
dendrogram
g a c i e d k b j f h
Define a distance between clusters
Initially, every datum is a cluster (return to this)
Initialize: every example is a cluster
Iterate:
Compute distances between all clusters
(store for efficiency)
Merge two closest clusters
Save both clustering and sequence of
cluster operations
“Dendrogram”
Iteration 1
Iteration 2
Iteration 3
• Builds up a sequence of
clusters (“hierarchical”)
• Algorithm complexity O(N2)
(Why?)
Hierarchical clustering
Hierarchical clustering
Hierarchical clustering
Hierarchical clustering
Hierarchical clustering
• Single Link
• Complete Link
• Average Link
Hierarchical clustering
Hierarchical clustering
Hierarchical clustering
Hierarchical clustering
Questions