1 of 16

Clustering

2 of 16

*Hierarchical clustering

Bottom up

Start with single-instance clusters
At each step, join the two closest clusters
Design decision: distance between clusters

E.g. two closest instances in clusters� vs. distance between means

Top down

Start with one universal cluster
Find two clusters
Proceed recursively on each subset
Can be very fast

Both methods produce a�dendrogram

2

3 of 16

Agglomerative Hierarchical Clustering

… you will find the description and an example here:

https://onlinecourses.science.psu.edu/stat555/node/85/

https://onlinecourses.science.psu.edu/stat555/node/86/

3

4 of 16

*Incremental clustering

Heuristic approach (COBWEB/CLASSIT)
Form a hierarchy of clusters incrementally
Start:

tree consists of empty root node

Then:

add instances one by one
update tree appropriately at each stage
to update, find the right leaf for an instance
May involve restructuring the tree

Base update decisions on category utility

4

5 of 16

*Clustering weather data

1

5

ID	Outlook	Temp.	Humidity	Windy
A	Sunny	Hot	High	False
B	Sunny	Hot	High	True
C	Overcast	Hot	High	False
D	Rainy	Mild	High	False
E	Rainy	Cool	Normal	False
F	Rainy	Cool	Normal	True
G	Overcast	Cool	Normal	True
H	Sunny	Mild	High	False
I	Sunny	Cool	Normal	False
J	Rainy	Mild	Normal	False
K	Sunny	Mild	Normal	True
L	Overcast	Mild	High	True
M	Overcast	Hot	Normal	False
N	Rainy	Mild	High	True

2

3

6 of 16

*Clustering weather data

4

6

ID	Outlook	Temp.	Humidity	Windy
A	Sunny	Hot	High	False
B	Sunny	Hot	High	True
C	Overcast	Hot	High	False
D	Rainy	Mild	High	False
E	Rainy	Cool	Normal	False
F	Rainy	Cool	Normal	True
G	Overcast	Cool	Normal	True
H	Sunny	Mild	High	False
I	Sunny	Cool	Normal	False
J	Rainy	Mild	Normal	False
K	Sunny	Mild	Normal	True
L	Overcast	Mild	High	True
M	Overcast	Hot	Normal	False
N	Rainy	Mild	High	True

3

Merge best host and runner-up

5

Consider splitting the best host if merging doesn’t help

7 of 16

*Final hierarchy

7

ID	Outlook	Temp.	Humidity	Windy
A	Sunny	Hot	High	False
B	Sunny	Hot	High	True
C	Overcast	Hot	High	False
D	Rainy	Mild	High	False

Oops! a and b are actually very similar

8 of 16

*Example: the iris data (subset)�

8

9 of 16

*Clustering with cutoff

9

10 of 16

*Category utility

Category utility: quadratic loss function�defined on conditional probabilities:

Every instance in different category ⇒ �numerator becomes��

10

maximum

number of attributes

11 of 16

*Overfitting-avoidance heuristic

If every instance gets put into a different category the numerator becomes (maximal):

Where n is number of all possible attribute values.

So without k in the denominator of the CU-formula, every cluster would consist of one instance!

11

Maximum value of CU

12 of 16

Other Clustering Approaches

EM – probability based clustering
Bayesian clustering
SOM – self-organizing maps
…

12

13 of 16

Discussion

Can interpret clusters by using supervised learning

learn a classifier based on clusters

Decrease dependence between attributes?

pre-processing step
E.g. use principal component analysis

Can be used to fill in missing values
Key advantage of probabilistic clustering:

Can estimate likelihood of data
Use it to compare different models objectively

13

14 of 16

Examples of Clustering Applications

Marketing: discover customer groups and use them for targeted marketing and re-organization
Astronomy: find groups of similar stars and galaxies
Earth-quake studies: Observed earth quake epicenters should be clustered along continent faults
Genomics: finding groups of gene with similar expressions
…

14

15 of 16

Clustering Summary

Unsupervised
Many approaches

K-means – simple, sometimes useful

K-medoids is less sensitive to outliers

Hierarchical clustering – works for symbolic attributes

Evaluation is a problem

15

16 of 16

Principal Component Analysis (PCA)

… you will find (detailed) description here:

http://setosa.io/ev/principal-component-analysis/

http://www.lauradhamilton.com/introduction-to-principal-component-analysis-pca

http://www.cs.otago.ac.nz/cosc453/student_tutorials/principal_components.pdf

16