Unsupervised

Learning - Clustering
Rahmatin Nur Amalia

Program Studi Sains Data, FSAD, Institut Teknologi Sepuluh Nopember

Today’s Topics

Unsupervised Learning:
▪ Clustering (definition)
▪ K-Means
▪ K-Medoid
▪ K-Prototype
Team Teaching:
• Novri Suhermi (M1-M5)
• Rahmatin Nur A (M6-M10)
• Muhammad Ahsan (M10-M14)
Supervised vs Unsupervised
Supervised Learning

Unsupervised Learning
 Supervised vs Unsupervised
Supervised learning: discover patterns in the data that relate data
attributes with a target (class) attribute.
❑ These patterns are then utilized to predict the values of the
target attribute in future data instances.

Unsupervised learning: The data have no target attribute.

❑ We want to explore the data to find some intrinsic structures in
them.
 Clustering
❑ 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
➢ As a stand-alone tool to get insight into data distribution
➢ As a preprocessing step for other algorithms
 What is good clustering
❑ A good clustering method will produce high quality clusters with
high intra-class similarity
low inter-class similarity
❑ The quality of a clustering result depends on both the similarity measure
used by the method and its implementation.
❑ The quality of a clustering method is also measured by its ability to
discover some or all of the hidden patterns.
 Requirements of Clustering in
Data Mining
❑ Scalability
❑ Ability to deal with different types of attributes
❑ Discovery of clusters with arbitrary shape
❑ Minimal requirements for domain knowledge to determine input
parameters
❑ Able to deal with noise and outliers
❑ Insensitive to order of input records
❑ High dimensionality
❑ Incorporation of user-specified constraints
❑ Interpretability and usability
 Data Structure
• Data matrix
• (two modes)
 x11 ... x1f ... x1p 
 
 ... ... ... ... ... 
x ... xif ... xip 
 i1 
 ... ... ... ... ... 
x ... xnf ... xnp 
 n1 

• Dissimilarity matrix
• (one mode)  0 
 d(2,1) 0 
 
 d(3,1) d ( 3,2) 0 
 
 : : : 
d ( n,1) d ( n,2) ... ... 0
 Methods
❑ Partitioning algorithms: Construct various
partitions and then evaluate them by some
criterion
❑ Hierarchy algorithms: Create a hierarchical
decomposition of the set of data (or objects)
using some criterion
❑ Density-based: based on connectivity and
density functions
❑ Grid-based: based on a multiple-level
granularity structure
❑ Model-based: A model is hypothesized for
each of the clusters and the idea is to find
the best fit of that model to each other
 Partitioning Algorithms
❑ Partitioning method: Construct a partition of a database D of n objects into a
set of k clusters
❑ Given a k, find a partition of k clusters that optimizes the chosen partitioning
criterion
Global optimal: exhaustively enumerate all partitions
Heuristic methods: k-means and k-medoids algorithms
k-means (MacQueen’67): Each cluster is represented by the center of the
cluster
k-medoids or PAM (Partition around medoids) (Kaufman & Rousseeuw’87):
Each cluster is represented by one of the objects in the cluster
K-Means Clustering
K-Means Clustering
 K-Means Clustering
Stopping Criterion
1. no (or minimum) re-assignments of data points to different clusters,
2. no (or minimum) change of centroids, or
3. minimum decrease in the sum of squared error (SSE),
k
SSE = 
j =1
xC j
dist (x, m j ) 2

Ci is the jth cluster, mj is the centroid of cluster Cj (the mean vector of all
the data points in Cj), and dist(x, mj) is the distance between data point x
and centroid mj.
 K-Means Clustering
Similarity Index
❑ Euclidean Distance ❑ Chebychef Distance

❑ Manhattan Distance ❑ Minkowski Distance

❑ Mahalanobis Distance ❑ Canberra Distance

 K-Means Clustering Example
10 10
10
9 9
9
8 8
8
7 7
7
6 6
6
5 5
5
4 4
4

3 Assign 3 Update 3

2
each
2
the 2

cluster
1 1

objects
1
0 0

means
0
0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10

to most
0 1 2 3 4 5 6 7 8 9 10

similar reassign reassign

center 10 10

K=2 9 9

8 8

Arbitrarily choose K 7

6
7

object as initial 5 5

cluster center 4 Update 4

the
3 3

2 2

1 cluster 1

means
0 0
0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10
 K-Means Clustering
Customer Segmentation
Customer Data
Using the customer data, apply k-means
CustID Age Income
clustering to group the customers into two
1 41 19
clusters.
2 47 100
3 33 57
4 29 19
5 47 253
6 40 81
7 38 56
8 42 64
9 26 18
10 47 115
 K-Means Clustering
Customer Segmentation
Customer Data
CustID Age Income
1 41 19 Initial
2 47 100 centroid
3 33 57
4 29 19
5 47 253
6 40 81
7 38 56 C2(47,100)
8 42 64
9 26 18 C1(41,19)
10 47 115
 K-Means Clustering
Compute the distance from x to each centroid
CustID Age Income Distance to C1(41,19) Disatance to C2(47,100) Cluster

3 33 57 (𝟑𝟑 − 𝟒𝟏)𝟐 +(𝟓𝟕 − 𝟏𝟗)𝟐 = 𝟑𝟖, 𝟖𝟑 (33 − 47)2 +(57 − 100)2 = 45,22 1

4 29 19 (𝟐𝟗 − 𝟒𝟏)𝟐 +(𝟏𝟗 − 𝟏𝟗)𝟐 = 𝟏𝟐, 𝟎 (29 − 47)2 +(19 − 100)2 = 82,98 1

5 47 253 (47 − 41)2 +(253 − 19)2 = 234,08 (𝟒𝟕 − 𝟒𝟕)𝟐 +(𝟐𝟓𝟑 − 𝟏𝟎𝟎)𝟐 = 𝟏𝟓𝟑, 𝟎 2

6 40 81 (40 − 41)2 +(81 − 19)2 = 62,01 (𝟒𝟎 − 𝟒𝟕)𝟐 +(𝟖𝟏 − 𝟏𝟎𝟎)𝟐 = 𝟐𝟎, 𝟐𝟓 2

7 38 56 (𝟑𝟖 − 𝟒𝟏)𝟐 +(𝟓𝟔 − 𝟏𝟗)𝟐 = 𝟑𝟕, 𝟏𝟐 (38 − 47)2 +(56 − 100)2 = 44,91 1

8 42 64 (42 − 41)2 +(64 − 19)2 = 45,01 (𝟒𝟐 − 𝟒𝟕)𝟐 +(𝟔𝟒 − 𝟏𝟎𝟎)𝟐 = 𝟑𝟔, 𝟑𝟓 2

9 26 18 (𝟐𝟔 − 𝟒𝟏)𝟐 +(𝟏𝟖 − 𝟏𝟗)𝟐 = 𝟏𝟓, 𝟎𝟑 (26 − 47)2 +(18 − 100)2 = 84,65 1

10 47 115 (47 − 41)2 +(115 − 19)2 = 96,19 (𝟒𝟕 − 𝟒𝟕)𝟐 +(𝟏𝟏𝟓 − 𝟏𝟎𝟎)𝟐 = 𝟏𝟓, 𝟎 2
 K-Means Clustering
Re-compute the centroid using the new membership

CustID Age Income Distance to C1(41,19) Disatance to C2(47,100) Cluster

1 41 19 0 (41 − 47)2 +(19 − 100)2 = 81,22 1

3 33 57 (𝟑𝟑 − 𝟒𝟏)𝟐 +(𝟓𝟕 − 𝟏𝟗)𝟐 = 𝟑𝟖, 𝟖𝟑 (33 − 47)2 +(57 − 100)2 = 45,22 1

4 29 19 (𝟐𝟗 − 𝟒𝟏)𝟐 +(𝟏𝟗 − 𝟏𝟗)𝟐 = 𝟏𝟐, 𝟎 (29 − 47)2 +(19 − 100)2 = 82,98 1

7 38 56 (𝟑𝟖 − 𝟒𝟏)𝟐 +(𝟓𝟔 − 𝟏𝟗)𝟐 = 𝟑𝟕, 𝟏𝟐 (38 − 47)2 +(56 − 100)2 = 44,91 1

9 26 18 (𝟐𝟔 − 𝟒𝟏)𝟐 +(𝟏𝟖 − 𝟏𝟗)𝟐 = 𝟏𝟓, 𝟎𝟑 (26 − 47)2 +(18 − 100)2 = 84,65 1

The new centroid C1 = (mean(41;33;29;38;26), mean(19;57;19;56;18)) = (33,4; 33,8)

 K-Means Clustering
Re-compute the centroid using the new membership
CustID Age Income Distance to C1(41,19) Disatance to C2(47,100) Cluster
2 47 100 (47 − 41)2 +(100 − 19)2 = 81,22 0 2

5 47 253 (47 − 41)2 +(253 − 19)2 = 234,08 (𝟒𝟕 − 𝟒𝟕)𝟐 +(𝟐𝟓𝟑 − 𝟏𝟎𝟎)𝟐 = 𝟏𝟓𝟑, 𝟎 2

6 40 81 (40 − 41)2 +(81 − 19)2 = 62,01 (𝟒𝟎 − 𝟒𝟕)𝟐 +(𝟖𝟏 − 𝟏𝟎𝟎)𝟐 = 𝟐𝟎, 𝟐𝟓 2

8 42 64 (42 − 41)2 +(64 − 19)2 = 45,01 (𝟒𝟐 − 𝟒𝟕)𝟐 +(𝟔𝟒 − 𝟏𝟎𝟎)𝟐 = 𝟑𝟔, 𝟑𝟓 2

10 47 115 (47 − 41)2 +(115 − 19)2 = 96,19 (𝟒𝟕 − 𝟒𝟕)𝟐 +(𝟏𝟏𝟓 − 𝟏𝟎𝟎)𝟐 = 𝟏𝟓, 𝟎 2

The new centroid C2 = (mean(47;47;40;42;47), mean(100;253;81;64;115)) = (44,6; 122,6)

 K-Means Clustering

Re-compute the distance using the new centroid

C2(44,6;122,6) Jarak ke Jarak ke
CustID Age Income Klaster
C1(33,4; 33,8) C2(44,6; 122,6)
1 41 19 16,64 103,66 1
2 47 100 67,58 22,73 2
C1(33,4;33,8) 3 33 57 23,20 66,62 1
4 29 19 15,44 104,77 1
5 47 253 219,62 130,42 2
6 40 81 47,66 41,85 2
Are the clustering results the same as 7 38 56 22,67 66,93 1
before? 8 42 64 31,40 58,66 1
• If yes, stop the clustering process. 9 26 18 17,45 106,24 1
• If not, repeat steps. 10 47 115 82,33 7,97 2
 K-Means Clustering
What is the problem of 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.
 K-Medoids
Find representative objects, called medoids, in clusters
PAM (Partitioning Around Medoids, 1987)
• starts from an initial set of medoids
and iteratively replaces one of the
medoids by one of the non-medoids if
it improves the total distance of the
resulting clustering
• PAM works effectively for small data
sets, but does not scale well for large
data sets
 K-Medoids
Total Cost = 20
10 10 10

9 9 9

8 8 8

Arbitrary Assign
7 7 7

6 6 6

5
choose k 5

4
each 5

object as remaining
4

3 3 3

1
initial 2

1
object to 2

0 medoids 0
0 1 2 3 4 5 6 7 8 9 10
nearest 0
0 1 2 3 4 5 6 7 8 9 10

medoids
0 1 2 3 4 5 6 7 8 9 10

K=2 Randomly select a nonmedoid

Total Cost = 26 object,Oramdom
10 10

Do loop 9

Compute
9

Swapping O
8 8

Until no change total cost of

7 7

and Oramdom
6 6

4
swapping 5

If quality is 3 3

improved.
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
 K-Medoids
❑ Pam is more robust than k-means in the presence of noise and outliers
because a medoid is less influenced by outliers or other extreme values
than a mean
❑ Pam works efficiently for small data sets but does not scale well for large
data sets.
➢ O(k(n-k)2 ) for each iteration, where n is # of data,k is # of clusters

➔Sampling based method,

CLARA(Clustering LARge Applications)
 K-Modes
K-Modes is a clustering algorithm similar to K-Means, but it is specifically designed for
categorical data. Instead of computing distances between numerical values, this algorithm
measures the number of mismatches between categorical values.
Similarity to K-Means:
Like K-Means, it aims to partition the dataset into k clusters. However, it does not use the mean to represent the
cluster centroid.

Mode as Centroid:
In K-Modes, the cluster centroid is represented by the mode (the most frequent value) of each categorical feature
within the cluster, rather than the average.

Dissimilarity Measure:
To determine the similarity between two objects, K-Modes uses a dissimilarity function, which simply counts how
many categorical attributes differ between two data points. The greater the number of mismatches, the less
similar the two objects are.
 K-Modes
Suppose we have two objects of categorical data, X and Y, each with m attributes (features),
defined as:
𝑋 = 𝑥1 , 𝑥2 , … , 𝑥𝑚
𝑌 = 𝑦1 , 𝑦2 , … , 𝑦𝑚

Then, the dissimilarity measure 𝑑 𝑋 𝑌 (the K-Modes distance) between objects X and Y is
defined as:
 K-Modes
Attribute (𝑥𝑗 ) (𝑦𝑗 ) Match? 𝛿 𝑥𝑗 , 𝑦𝑗
Gender Male Female Mismatch 1
Marital Status Married Married Match 0
Favorite Color Blue Green Mismatch 1
Job Type Engineer Engineer Match 0

the
dissimilarity
measure
 K-Prototype
❑ K-Prototypes is a clustering algorithm that combines K-Means and K-
Modes to handle datasets containing both numerical and categorical
data simultaneously.
❑ This algorithm assigns weights to both types of features and computes a
weighted distance metric to determine cluster assignments.
❑ It uses a dissimilarity measure that integrates the distance between
numerical features and the dissimilarity between categorical features.
 K-Prototype
How It Works
➢ It applies K-Means logic to the numerical part (by computing squared distances).
➢ It applies K-Modes logic to the categorical part (by counting mismatches).

Cluster Center (Prototype)

The cluster center in K-Prototypes is called a prototype, which stores:
➢ The mean for all numerical features.
➢ The mode for all categorical features.

Distance Calculation
➢ The distance used to assign a data point to a cluster is the sum of both metrics (numerical
and categorical).
➢ This formula also includes a weighting factor (γ) to ensure that the contributions of
numerical and categorical attributes are balanced and that neither dominates the
clustering process.
K-Prototype
Question?

How to determine the best k?

 THANK
YOU
[Link]/instrumentasi Teknik Instrumentasi ITS

@instrumentasi_its @instrumentasiits

@instrumentasits Rahmatin Nur Amalia

[Link]@[Link]
Program Studi Sains Data, FSAD, Institut Teknologi Sepuluh Nopember