Data Mining
Concepts and Techniques
Dr. Mohamad Shady Ahmad Alrahhal
1 1
Data Mining:
Concepts and
Techniques
(3rd ed.)
— Chapter 10 —
Jiawei Han, Micheline Kamber, and Jian Pei
University of Illinois at Urbana-Champaign &
Simon Fraser University
©2013 Han, Kamber & Pei. All rights reserved.
Dr. Mohamad Shady Ahmad Alrahhal
2
What is Cluster Analysis?
■ Cluster: A collection of data objects
■ similar (or related) to one another within the same
group
■ dissimilar (or unrelated) to the objects in other
groups
■ Cluster analysis (or clustering, data segmentation,
…)
■ Finding similarities between data according to the
characteristics found in the data and grouping
similar data objects into clusters
■ Unsupervised learning: no predefined classes (i.e.,
learning by observations vs. learning by examples:
supervised)
■ Typical applications 3
Applications of Cluster Analysis
■ Data reduction
■ Summarization: Preprocessing for regression,
PCA, classification, and association analysis
■ Compression: Image processing: vector
quantization
■ Hypothesis generation and testing
■ Prediction based on groups
■ Cluster & find characteristics/patterns for each
group
■ Finding K-nearest Neighbors
■ Localizing search to one or a small number of
clusters
■ 4
Basic Steps to Develop a Clustering
Task
■ Feature selection
■ Select info concerning the task of interest
■ Minimal information redundancy
■ Proximity measure
■ Similarity of two feature vectors
■ Clustering criterion
■ Expressed via a cost function or some rules
■ Clustering algorithms
■ Choice of algorithms
■ Validation of the results
■ Validation test (also, clustering tendency test)
■ Interpretation of the results
■ Integration with applications
5
Quality: What Is Good Clustering?
■ A good clustering method will produce high quality
clusters
■ high intra-class similarity: cohesive within
clusters
■ low inter-class similarity: distinctive between
clusters
■ The quality of a clustering method depends on
■ the similarity measure used by the method
■ its implementation, and
■ Its ability to discover some or all of the hidden
6
The K-Means Clustering
Method
■ Given k, the k-means algorithm is implemented
in four steps:
■ Partition objects into k nonempty subsets
■ Compute seed points as the centroids of the
clusters of the current partitioning (the
centroid is the center, i.e., mean point, of
the cluster)
■ Assign each object to the cluster with the
nearest seed point
■ Go back to Step 2, stop when the
assignment does not change
7
An Example of K-Means Clustering
K=2
Arbitrarily Update
partition the
objects cluster
into k centroids
groups
The initial data Loop if
set Reassign objects
needed
■ Partition objects into k nonempty
subsets
■ Repeat
■ Compute centroid (i.e., mean Update
the
point) for each partition cluster
■ Assign each object to the centroids
cluster of its nearest centroid
■ Until no change
8
What Is the Problem of the K-Means Method?
■ The k-means algorithm is sensitive to outliers !
■ Since an object with an extremely large value may
substantially distort the distribution of the data
■ K-Medoids: Instead of taking the mean value of the object in
a cluster as a reference point, medoids can be used, which is
the most centrally located object in a cluster
10 10
9 9
8 8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
0 0
0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10
9
PAM: A Typical K-Medoids Algorithm
Total Cost =
20
1
0
9
6
Arbitrar Assign
5
y each
4 choose remaini
3
k object ng
2
as object
initial to
1
0
0 1 2 3 4 5 6 7 8 9 1
0
medoid nearest
K=2 s medoid
s Randomly select a
Total Cost = nonmedoid
26 object,Oramdom
1 1
Do loop
0 0
9 9
8
Compute 8
Swapping total cost
Until no
7 7
O and 6
of 6
change Oramdom 5
swapping
5
4 4
If quality is 3 3
2 2
improved. 1 1
0 0
0 1 2 3 4 5 6 7 8 9 1 0 1 2 3 4 5 6 7 8 9 1
0 0
10
Measuring Clustering Quality
■ 3 kinds of measures: External, internal and relative
■ External: supervised, employ criteria not inherent to the
dataset
■ Compare a clustering against prior or expert-specified
knowledge (i.e., the ground truth) using certain
clustering quality measure
■ Internal: unsupervised, criteria derived from data itself
■ Evaluate the goodness of a clustering by considering
how well the clusters are separated, and how
compact the clusters are, e.g., Silhouette coefficient
■ Relative: directly compare different clusterings, usually
those obtained via different parameter settings for the
same algorithm 11
Some Commonly Used External Measures
■ Matching-based measures
■ Purity, maximum matching, F-measure
■ Entropy-Based Measures
Ground truth partitioning T2
■ Conditional entropy, normalized mutual T 1
Cluster Cluster
information (NMI), variation of information C 1
C 2
■ Pair-wise measures
■ Four possibilities: True positive (TP), FN,
FP, TN
■ Jaccard coefficient, Rand statistic,
Fowlkes-Mallow measure
■ Correlation measures
■ Discretized Huber static, normalized
discretized Huber static
12