CLUSTER ANALYSIS

ANALYSIS —
Ph.D. Shatovskaya T.
Department of Computer Science

Analysis?
Types of Data in Cluster Analysis
A Categorization of Major Clustering

one another within the same cluster
Dissimilar to the objects in

Data Analysis
create thematic maps in GIS by clustering feature

discover distinct groups in their customer bases, and then use

method will produce high quality clusters with
high intra-class similarity
low inter-class

Scalability
Ability to deal with different types of attributes
Discovery of clusters

Analysis?
Types of Data in Cluster Analysis
A Categorization of Major Clustering

Similarity is expressed in terms of a distance function, which

variables:
Binary variables:
Nominal, ordinal, and ratio variables:
Variables of mixed types:

deviation:

where
Calculate the standardized measurement (z-score)

Using mean absolute deviation is more

data




Simple matching coefficient (invariant, if the binary variable is symmetric):
Jaccard

Object i

Object j

Q(i,j)= ad-bc/ ad+bc


Rassel and Rao coefficient: J(i,j)=

Bravais coefficient: C(i,j)= ad-bc/

Hemming distance: H(i,j)= a+d

symmetric attribute
the remaining attributes are asymmetric binary
let the values Y

variable in that it can take more than 2 states,

discrete or continuous
Order is important, e.g., rank
Can be treated like

on a nonlinear scale, approximately at exponential scale, such as

contain all the six types of variables
symmetric binary, asymmetric binary,

Analysis?
Types of Data in Cluster Analysis
A Categorization of Major Clustering

partitions and then evaluate them by some criterion
Hierarchy algorithms: Create

Analysis?
Types of Data in Cluster Analysis
A Categorization of Major Clustering

a partition of a database D of n objects into

the k-means algorithm is implemented in four steps:
Partition objects into

K object as initial cluster center
Assign each objects to most

Update the cluster means

Update the cluster means

reassign

reassign

efficient: O(tkn), where n is # objects, k is #

variants of the k-means which differ in
Selection of the initial

Method?
The k-means algorithm is sensitive to outliers !
Since an object

20











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



K=2
Arbitrary choose k object as initial medoids
Assign each remaining object

Randomly select a nonmedoid object,Oramdom

Compute total cost of swapping

Total Cost = 26

Swapping O and Oramdom
If quality is improved.

Do loop
Until no change

is more robust than k-means in the presence of noise

and Rousseeuw in 1990)
Built in statistical analysis packages, such as

Algorithm based on Randomized Search) (Ng and Han’94)
CLARANS draws sample

Analysis?
Types of Data in Cluster Analysis
A Categorization of Major Clustering

are Merged Hierarchically
Decompose data objects into a several levels of

To estimate similarity of objects on the basis of binary

0 1 1 1 0

We have 3 objects with 16 attributes . Define the similarity of objects.

1. Define the similarity on the base of Simple matching coefficient

ecoli1
ecoli2

J12=13/16=0.81

J13=12/15=0.8

ecoli1
ecoli3

0.81 0.8

2 1 3

0.8

0.81

number

Example for binary variables

To estimate similarity of objects on the basis of numerical

us consider five points {x1,….,x5} with the attributes
X1=(0,2), x2=(0,0)

a) single-link distance

Cluster 2

Cluster 1

b) complete-link distance

Using Euclidian measure

D(x1,x3)=2.5 D(x1,x4)=5.39 D(x1,x5)=5
D(x2,x3)=1.5 D(x2,x4)=5 D(x2,x5)=5.29
D(x3,x4)=3.5 D(x3,x5)=4.03
D(x4,x5)=2
Dendrogram by single-link method
Dendrogram by

2.2

criteria. This method does not require the number of clusters

Rousseeuw (1990)
Implemented in statistical analysis packages, e.g., Splus
Use the Single-Link

Rousseeuw (1990)
Implemented in statistical analysis packages, e.g., Splus
Inverse order of

of agglomerative clustering methods
do not scale well: time complexity of

Clustering using Hierarchies, by Zhang, Ramakrishnan, Livny (SIGMOD’96)
Incrementally construct a

the statistics for a given subcluster: the 0-th, 1st and

node
Leaf node
Leaf node

by Guha, Rastogi & Shim, 1998
Stops the creation of a

based clustering method
Consider only one point as representative of

sample to p partitions with size s/p
Partially cluster partitions into

= 2
s/p = 25
x
x
s/pq = 5

representative points towards the gravity center by a fraction of

using linKs, by S. Guha, R. Rastogi, K. Shim (ICDE’99).
Use

neighbors for the two points.




Algorithm
Draw random sample
Cluster with links
{1,2,3}, {1,2,4},

{1,2,3} {1,2,4}

3

by G. Karypis, E.H. Han, and V. Kumar’99
Measures the

Graph
Merge Partition
Final Clusters
Data Set

Analysis?
Types of Data in Cluster Analysis
A Categorization of Major Clustering

(local cluster criterion), such as density-connected points
Major features:
Discover clusters of

Analysis?
Types of Data in Cluster Analysis
A Categorization of Major Clustering

data structure
Several interesting methods
STING (a STatistical INformation Grid approach) by

Yang and Muntz (VLDB’97)
The spatial area area is divided into

high level is partitioned into a number of smaller cells

from further consideration
When finish examining the current layer, proceed to

A multi-resolution clustering approach which applies wavelet transform to the

to find clusters
Summaries the data by imposing a multidimensional

frequency subbands. (can be applied to n-dimensional signals)
Data are transformed

for clustering
Unsupervised clustering
It uses hat-shape filters to emphasize

Gunopulos, Raghavan (SIGMOD’98).
Automatically identifying subspaces of a high dimensional

space and find the number of points that lie inside

automatically finds subspaces of the highest dimensionality such that high

Analysis?
Types of Data in Cluster Analysis
A Categorization of Major Clustering

fit between the data and some mathematical model
Statistical and AI

assumption that the attributes are independent of each other is

each cluster as an exemplar, acting as a “prototype” of

performed by having several units competing for the current object
The

Analysis?
Types of Data in Cluster Analysis
A Categorization of Major Clustering

set of objects are considerably dissimilar from the remainder of

underlying distribution that generates data set (e.g. normal distribution)
Use

by statistical methods
We need multi-dimensional analysis without knowing data distribution.
Distance-based

examining the main characteristics of objects in a group
Objects that

Analysis?
Types of Data in Cluster Analysis
A Categorization of Major Clustering

made in scalable clustering methods
Partitioning: k-means, k-medoids, CLARANS
Hierarchical: BIRCH, CURE
Density-based:

but more user-desired constraints, e.g., an ATM allocation problem

account
Not Taking obstacles into account

their similarity and has wide applications
Measure of similarity can be

Gunopulos, and P. Raghavan. Automatic subspace clustering of high dimensional

Rousseeuw. Finding Groups in Data: an Introduction to Cluster Analysis.