Cluster Analysis

1. What is Cluster Analysis?

2. Types of Data in Cluster Analysis
3. A Categorization of Major Clustering Methods
4. Partitioning Methods
5. Hierarchical Methods
6. Density-Based Methods
7. Grid-Based Methods
8. Model-Based Methods
9. Clustering High-Dimensional Data
10. Constraint-Based Clustering
11. Outlier Analysis
12. Summary
May 24, 2015

Data Mining: Concepts and

Techniques

What is Cluster Analysis?

Cluster: a collection of data objects

Similar to one another within the same cluster

Dissimilar to the objects in other clusters

Cluster analysis

Finding similarities between data according to the

characteristics found in the data and grouping
similar data objects into clusters

Unsupervised learning: no predefined classes

Typical applications

As a stand-alone tool to get insight into data

distribution

As a preprocessing step for other algorithms

May 24, 2015

Data Mining: Concepts and

Techniques

Clustering: Rich Applications and

Multidisciplinary Efforts

Pattern Recognition

Spatial Data Analysis

Create thematic maps in GIS by clustering feature

spaces

Detect spatial clusters or for other spatial mining

tasks

Image Processing

Economic Science (especially market research)

WWW

Document classification

Cluster Weblog data to discover groups of similar

access patterns

May 24, 2015

Data Mining: Concepts and

Techniques

Examples of Clustering
Applications

Marketing: Help marketers discover distinct groups in their

customer bases, and then use this knowledge to develop
targeted marketing programs

Land use: Identification of areas of similar land use in an

earth observation database

Insurance: Identifying groups of motor insurance policy

holders with a high average claim cost

City-planning: Identifying groups of houses according to their

house type, value, and geographical location

Earth-quake studies: Observed earth quake epicenters

should be clustered along continent faults

May 24, 2015

Data Mining: Concepts and

Techniques

Quality: 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

May 24, 2015

Data Mining: Concepts and

Techniques

Measure the Quality of

Clustering

Dissimilarity/Similarity metric: Similarity is expressed

in terms of a distance function, typically metric: d(i, j)

There is a separate quality function that measures

the goodness of a cluster.

The definitions of distance functions are usually very

different for interval-scaled, boolean, categorical,
ordinal ratio, and vector variables.

Weights should be associated with different variables

based on applications and data semantics.

It is hard to define similar enough or good enough

the answer is typically highly subjective.

May 24, 2015

Data Mining: Concepts and

Techniques

Requirements of Clustering in Data

Mining

Scalability

Ability to deal with different types of attributes

Ability to handle dynamic data

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

May 24, 2015

Data Mining: Concepts and

Techniques

Chapter 7. Cluster Analysis

1. What is Cluster Analysis?
2. Types of Data in Cluster Analysis
3. A Categorization of Major Clustering Methods
4. Partitioning Methods
5. Hierarchical Methods
6. Density-Based Methods
7. Grid-Based Methods
8. Model-Based Methods
9. Clustering High-Dimensional Data
10. Constraint-Based Clustering
11. Outlier Analysis
12. Summary
May 24, 2015

Data Mining: Concepts and

Techniques

Data Structures

Data matrix
(two modes)

x11

...

x
i1
...
x
n1

Dissimilarity matrix
(one mode)

May 24, 2015

...

x1f

...

x1p

...

...

...

...

xif

...

...
xip

...
...
... xnf

...
...

...
xnp

d(2,1)
0

d(3,1) d ( 3,2) 0

:
:
:

d ( n,1) d ( n,2) ...

Data Mining: Concepts and

Techniques

... 0
9

Type of data in clustering analysis

Interval-scaled variables

Binary variables

Nominal, ordinal, and ratio variables

Variables of mixed types

May 24, 2015

Data Mining: Concepts and

Techniques

10

Interval-valued variables

Standardize data

Calculate the mean absolute deviation:

s f 1n (| x1 f m f | | x2 f m f | ... | xnf m f |)

where

...

xnf )

Calculate the standardized measurement (zscore)

m f 1n (x1 f x2 f

xif m f
zif
sf

Using mean absolute deviation is more robust than

using standard deviation

May 24, 2015

Data Mining: Concepts and

Techniques

11

Similarity and Dissimilarity

Between Objects

Distances are normally used to measure the

similarity or dissimilarity between two data
objects

q
q
Some popular
d (i, j) q (| ones
x x |include:
| x x Minkowski
| q ... | x x |distance:
)

i1

j1

i2

j2

ip

jp

where i = (xi1, xi2, , xip) and j = (xj1, xj2, , xjp)

are two p-dimensional data objects, and q is a
positive integer

If q = 1, d isd (iManhattan
, j) | x x | |distance
x x | ... | x x |

May 24, 2015

i1

j1

i2

j2

Data Mining: Concepts and

Techniques

ip

jp

12

Similarity and Dissimilarity

Between Objects (Cont.)

If q = 2, d is Euclidean distance:
d (i, j) (| x x | 2 | x x | 2 ... | x x |2 )
i1
j1
i2
j2
ip
jp

Properties

d(i,j) 0

d(i,i) = 0

d(i,j) = d(j,i)

d(i,j) d(i,k) + d(k,j)

Also, one can use weighted distance, parametric

Pearson product moment correlation, or other
disimilarity measures

May 24, 2015

Data Mining: Concepts and

Techniques

13

Binary Variables

A contingency table for

binary data

Object i

Distance measure for

symmetric binary variables:

1
a

Jaccard coefficient (similarity

0
b

0
c
d
sum a c b d

d (i, j)

Distance measure for

asymmetric binary variables:

Object j

d (i, j)

bc
a bc

May 24, 2015

simJaccard (i, j)
Data Mining: Concepts and
Techniques

cd
p

bc
a bc d

measure for asymmetric

binary variables):

sum
a b

a
a bc
14

Dissimilarity between Binary

Variables

Example
Name
Jack
Mary
Jim

Gender
M
F
M

Fever
Y
Y
Y

Cough
N
N
P

Test-1
P
P
N

Test-2
N
N
N

Test-3
N
P
N

Test-4
N
N
N

gender is a symmetric attribute

the remaining attributes are asymmetric binary
let the values Y and P be set to 1, and the value N be set
to 0 d ( jack , mary ) 0 1 0.33
2 01
11
d ( jack , jim )
0.67
111
1 2
d ( jim , mary )
0.75
11 2

May 24, 2015

Data Mining: Concepts and

Techniques

15

Nominal Variables

A generalization of the binary variable in that it can

take more than 2 states, e.g., red, yellow, blue, green

Method 1: Simple matching

m: # of matches, p: total # of variables

m
d (i, j) p
p

Method 2: use a large number of binary variables

creating a new binary variable for each of the M

nominal states

May 24, 2015

Data Mining: Concepts and

Techniques

16

Ordinal Variables

An ordinal variable can be discrete or continuous

Order is important, e.g., rank

Can be treated like interval-scaled

rif {1,..., M f }
replace x by their rank
if

map the range of each variable onto [0, 1] by

replacing i-th object in the f-th variable by
zif

rif 1

M f 1

compute the dissimilarity using methods for

interval-scaled variables

May 24, 2015

Data Mining: Concepts and

Techniques

17

Ratio-Scaled Variables

Ratio-scaled variable: a positive measurement on a

nonlinear scale, approximately at exponential scale,
such as AeBt or Ae-Bt

Methods:

treat them like interval-scaled variablesnot a

good choice! (why?the scale can be distorted)

apply logarithmic transformation

yif = log(xif)

treat them as continuous ordinal data treat their

rank as interval-scaled

May 24, 2015

Data Mining: Concepts and

Techniques

18

Variables of Mixed Types

A database may contain all the six types of variables

symmetric binary, asymmetric binary, nominal,
ordinal, interval and ratio
One may use a weighted formula to combine their
effects
p ( f )d ( f )

d (i, j )

f 1 ij
p
f 1

ij
(f)
ij

f is binary or nominal:
dij(f) = 0 if xif = xjf , or dij(f) = 1 otherwise
f is interval-based: use the normalized distance
f is ordinal or ratio-scaled
compute ranks r and
if
and treat z as interval-scaled
if
z r 1
if

if

May 24, 2015

Data Mining: Concepts and

Techniques

19

Vector Objects

Vector objects: keywords in documents,

gene features in micro-arrays, etc.

Broad applications: information retrieval,

biologic taxonomy, etc.

Cosine measure

A variant: Tanimoto coefficient

May 24, 2015

Data Mining: Concepts and

Techniques

20

Chapter 7. Cluster Analysis

1. What is Cluster Analysis?
2. Types of Data in Cluster Analysis
3. A Categorization of Major Clustering Methods
4. Partitioning Methods
5. Hierarchical Methods
6. Density-Based Methods
7. Grid-Based Methods
8. Model-Based Methods
9. Clustering High-Dimensional Data
10. Constraint-Based Clustering
11. Outlier Analysis
12. Summary
May 24, 2015

Data Mining: Concepts and

Techniques

21

Major Clustering Approaches

(I)

Partitioning approach:

Construct various partitions and then evaluate them by some

criterion, e.g., minimizing the sum of square errors

Typical methods: k-means, k-medoids, CLARANS

Hierarchical approach:

Create a hierarchical decomposition of the set of data (or objects)

using some criterion

Typical methods: Diana, Agnes, BIRCH, ROCK, CAMELEON

Density-based approach:

Based on connectivity and density functions

Typical methods: DBSACN, OPTICS, DenClue

May 24, 2015

Data Mining: Concepts and

Techniques

22

Major Clustering Approaches

(II)

Grid-based approach:

based on a multiple-level granularity structure

Typical methods: STING, WaveCluster, CLIQUE

Model-based:

A model is hypothesized for each of the clusters and tries to find the
best fit of that model to each other

Typical methods: EM, SOM, COBWEB

Frequent pattern-based:

Based on the analysis of frequent patterns

Typical methods: pCluster

User-guided or constraint-based:

Clustering by considering user-specified or application-specific

constraints

Typical methods: COD (obstacles), constrained clustering

May 24, 2015

Data Mining: Concepts and

Techniques

23

Typical Alternatives to Calculate the

Distance between Clusters

Single link: smallest distance between an element in one

cluster and an element in the other, i.e., dis(K i, Kj) = min(tip, tjq)

Complete link: largest distance between an element in one

cluster and an element in the other, i.e., dis(K i, Kj) = max(tip, tjq)

Average: avg distance between an element in one cluster and

an element in the other, i.e., dis(K i, Kj) = avg(tip, tjq)

Centroid: distance between the centroids of two clusters, i.e.,

dis(Ki, Kj) = dis(Ci, Cj)

Medoid: distance between the medoids of two clusters, i.e.,

dis(Ki, Kj) = dis(Mi, Mj)

Medoid: one chosen, centrally located object in the cluster

May 24, 2015

Data Mining: Concepts and

Techniques

24

Centroid, Radius and Diameter of a

Cluster (for numerical data sets)

Centroid: the middle of a cluster

Cm

iN 1(t

ip

Radius: square root of average distance from any point of

the cluster to its centroid

N (t cm ) 2
Rm i 1 ip
N

Diameter: square root of average mean squared distance

between all pairs of points in the cluster

N N (t t ) 2
Dm i 1 i 1 ip iq
N ( N 1)
May 24, 2015

Data Mining: Concepts and

Techniques

25

Chapter 7. Cluster Analysis

1. What is Cluster Analysis?
2. Types of Data in Cluster Analysis
3. A Categorization of Major Clustering Methods
4. Partitioning Methods
5. Hierarchical Methods
6. Density-Based Methods
7. Grid-Based Methods
8. Model-Based Methods
9. Clustering High-Dimensional Data
10. Constraint-Based Clustering
11. Outlier Analysis
12. Summary
May 24, 2015

Data Mining: Concepts and

Techniques

26

Partitioning Algorithms: Basic

Concept

Partitioning method: Construct a partition of a database D of n

objects into a set of k clusters, s.t., min sum of squared
distance
k
2

m1tmiKm (Cm tmi )

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 (MacQueen67): Each cluster is represented by the

center of the cluster

k-medoids or PAM (Partition around medoids) (Kaufman &

Rousseeuw87): Each cluster is represented by one of the
objects in the cluster

May 24, 2015

Data Mining: Concepts and

Techniques

27

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 partition (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 no more new

assignment

May 24, 2015

Data Mining: Concepts and

Techniques

28

The K-Means Clustering Method

Example

10
9
8
7
6
5

10

10

4
3
2
1
0
0

K=2
Arbitrarily choose
K object as initial
cluster center

10

Assign
each
objects
to
most
similar
center

3
2
1
0
0

10

4
3
2
1
0
0

reassign
10

10

2
1
0
0

10

reassign

May 24, 2015

Update
the
cluster
means

10

Update
the
cluster
means

Data Mining: Concepts and

Techniques

4
3
2
1
0
0

10

29

Comments on the K-Means Method

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

# clusters, and t is # iterations. Normally, k, t << n.

Comparing: PAM: O(k(n-k)2 ), CLARA: O(ks2 + k(n-k))

Comment: Often terminates at a local optimum. The global

optimum may be found using techniques such as:
deterministic annealing and genetic algorithms

Weakness

Applicable only when mean is defined, then what about

categorical data?

Need to specify k, the number of clusters, in advance

Unable to handle noisy data and outliers

Not suitable to discover clusters with non-convex shapes

May 24, 2015

Data Mining: Concepts and

Techniques

30

Variations of the K-Means Method

A few variants of the k-means which differ in

Selection of the initial k means

Dissimilarity calculations

Strategies to calculate cluster means

Handling categorical data: k-modes (Huang98)

Replacing means of clusters with modes

Using new dissimilarity measures to deal with categorical objects

Using a frequency-based method to update modes of clusters

A mixture of categorical and numerical data: k-prototype method

May 24, 2015

Data Mining: Concepts and

Techniques

31

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

0
0

May 24, 2015

10

Data Mining: Concepts and

Techniques

10

32

The K-Medoids Clustering Method

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

CLARA (Kaufmann & Rousseeuw, 1990)

CLARANS (Ng & Han, 1994): Randomized sampling

Focusing + spatial data structure (Ester et al., 1995)

May 24, 2015

Data Mining: Concepts and

Techniques

33

A Typical K-Medoids Algorithm (PAM)

Total Cost = 20
10

10

10

6
5
4
3
2
1
0
0

K=2

10

Arbitrar
y
choose
k object
as
initial
medoid
s

Assign
each
remaini
ng
object
to
nearest
medoid
s

6
5
4
3
2
1
0
0

10

Total Cost = 26
10

Do loop
Until no
change

6
5
4
3
2
1
0
0

10

Compute
total cost
of
swapping

Swapping
O and
Oramdom
If quality is
improved.

7
6
5
4

10

Randomly select a
nonmedoid
object,Oramdom

8
7
6
5
4

0
1
2
3
4
5
6
7
8
9
10
Data
Mining:
Concepts
and
Techniques

May 24, 2015

10

34

PAM (Partitioning Around Medoids)

(1987)

PAM (Kaufman and Rousseeuw, 1987), built in Splus

Use real object to represent the cluster

Select k representative objects arbitrarily

For each pair of non-selected object h and selected

object i, calculate the total swapping cost TCih

For each pair of i and h,

If TCih < 0, i is replaced by h

Then assign each non-selected object to the

most similar representative object

repeat steps 2-3 until there is no change

May 24, 2015

Data Mining: Concepts and

Techniques

35

PAM Clustering: Total swapping cost

TCih=jCjih

10

10

8
7

8
7

6
5

4
3

6
5

h
i

4
3

0
0

10

Cjih = d(j, h) - d(j, i)

Cjih = 0
0

10

10

10

7
6
5

4
3

Cjih and
= d(j, h) - d(j, t)
Cjih = d(j, t) - d(j, i) Data Mining: Concepts
0

May 24, 2015

10

Techniques

10

36

What Is the Problem with PAM?

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)

May 24, 2015

Data Mining: Concepts and

Techniques

37

CLARA (Clustering Large Applications)

(1990)

CLARA (Kaufmann and Rousseeuw in 1990)

Built in statistical analysis packages, such as S+

It draws multiple samples of the data set, applies PAM on

each sample, and gives the best clustering as the output

Strength: deals with larger data sets than PAM

Weakness:

Efficiency depends on the sample size

A good clustering based on samples will not

necessarily represent a good clustering of the whole
data set if the sample is biased

May 24, 2015

Data Mining: Concepts and

Techniques

38

CLARANS (Randomized CLARA)

(1994)

CLARANS (A Clustering Algorithm based on Randomized

Search) (Ng and Han94)

CLARANS draws sample of neighbors dynamically

The clustering process can be presented as searching a

graph where every node is a potential solution, that is, a
set of k medoids

If the local optimum is found, CLARANS starts with new

randomly selected node in search for a new local optimum

It is more efficient and scalable than both PAM and CLARA

Focusing techniques and spatial access structures may

further improve its performance (Ester et al.95)

May 24, 2015

Data Mining: Concepts and

Techniques

39

Chapter 7. Cluster Analysis

1. What is Cluster Analysis?
2. Types of Data in Cluster Analysis
3. A Categorization of Major Clustering Methods
4. Partitioning Methods
5. Hierarchical Methods
6. Density-Based Methods
7. Grid-Based Methods
8. Model-Based Methods
9. Clustering High-Dimensional Data
10. Constraint-Based Clustering
11. Outlier Analysis
12. Summary
May 24, 2015

Data Mining: Concepts and

Techniques

40

Hierarchical Clustering

Use distance matrix as clustering criteria. This

method does not require the number of clusters k
as an input, but needs a termination condition
Step 0

a
b

Step 1

Step 2 Step 3 Step 4

ab
abcde

cde

de

e
Step 4
May 24, 2015

agglomerative
(AGNES)

Step 3

Step 2 Step 1 Step 0

Data Mining: Concepts and

Techniques

divisive
(DIANA)
41

AGNES (Agglomerative Nesting)

Introduced in Kaufmann and Rousseeuw (1990)

Implemented in statistical analysis packages, e.g.,

Splus

Use the Single-Link method and the dissimilarity

matrix.

Merge nodes that have the least dissimilarity

Go on in a non-descending fashion
10

10

10

Eventually all nodes belong to the same cluster

0
0

May 24, 2015

10

0
0

10

Data Mining: Concepts and

Techniques

10

42

Dendrogram: Shows How the Clusters are Merged

Decompose data objects into a several levels of nested

partitioning (tree of clusters), called a dendrogram.
A clustering of the data objects is obtained by cutting the
dendrogram at the desired level, then each connected
component forms a cluster.

May 24, 2015

Data Mining: Concepts and

Techniques

43

DIANA (Divisive Analysis)

Introduced in Kaufmann and Rousseeuw (1990)

Implemented in statistical analysis packages, e.g.,

Splus

Inverse order of AGNES

Eventually each node forms a cluster on its own

10

10

10

0
0

May 24, 2015

10

0
0

10

Data Mining: Concepts and

Techniques

10

44

Recent Hierarchical Clustering

Methods

Major weakness of agglomerative clustering methods

do not scale well: time complexity of at least O(n2),

where n is the number of total objects

can never undo what was done previously

Integration of hierarchical with distance-based

clustering

BIRCH (1996): uses CF-tree and incrementally

adjusts the quality of sub-clusters

ROCK (1999): clustering categorical data by neighbor

and link analysis

CHAMELEON (1999): hierarchical clustering using

dynamic modeling Data Mining: Concepts and

May 24, 2015

Techniques

45

BIRCH (1996)

Birch: Balanced Iterative Reducing and Clustering using

Hierarchies (Zhang, Ramakrishnan & Livny, SIGMOD96)

Incrementally construct a CF (Clustering Feature) tree, a

hierarchical data structure for multiphase clustering

Phase 1: scan DB to build an initial in-memory CF tree

(a multi-level compression of the data that tries to
preserve the inherent clustering structure of the data)

Phase 2: use an arbitrary clustering algorithm to

cluster the leaf nodes of the CF-tree

Scales linearly: finds a good clustering with a single scan

and improves the quality with a few additional scans

Weakness: handles only numeric data, and sensitive to

the order of the data record.

May 24, 2015

Data Mining: Concepts and

Techniques

46

Clustering Feature Vector in

BIRCH
Clustering Feature: CF = (N, LS, SS)
N: Number of data points
LS: Ni=1=Xi
SS: Ni=1=Xi2

CF = (5, (16,30),(54,190))
10
9
8
7
6
5
4
3
2
1
0
0

May 24, 2015

10

Data Mining: Concepts and

Techniques

(3,4)
(2,6)
(4,5)
(4,7)
(3,8)
47

CF-Tree in BIRCH

Clustering feature:

summary of the statistics for a given subcluster: the 0-th, 1st and
2nd moments of the subcluster from the statistical point of view.

registers crucial measurements for computing cluster and utilizes

storage efficiently

A CF tree is a height-balanced tree that stores the clustering

features for a hierarchical clustering

A nonleaf node in a tree has descendants or children

The nonleaf nodes store sums of the CFs of their children

A CF tree has two parameters

Branching factor: specify the maximum number of children.

threshold: max diameter of sub-clusters stored at the leaf nodes

May 24, 2015

Data Mining: Concepts and

Techniques

48

The CF Tree Structure

Root
B=7

CF1

CF2 CF3

CF6

L=6

child1

child2 child3

child6

CF1

Non-leaf node
CF2 CF3

CF5

child1

child2 child3

child5

Leaf node
prev

CF1 CF2

May 24, 2015

Leaf node

CF6 next

prev

CF1 CF2

Data Mining: Concepts and

Techniques

CF4 next

49

Clustering Categorical Data: The ROCK

Algorithm

ROCK: RObust Clustering using linKs

S. Guha, R. Rastogi & K. Shim, ICDE99
Major ideas
Use links to measure similarity/proximity
Not distance-based
2
2
Computational complexity:O( n nm m n log n )
m a
Algorithm: sampling-based clustering
Draw random sample
Cluster with links
Label data in disk
Experiments
Congressional voting, mushroom data

May 24, 2015

Data Mining: Concepts and

Techniques

50

Similarity Measure in ROCK

Traditional measures for categorical data may not work well,

e.g., Jaccard coefficient
Example: Two groups (clusters) of transactions

C1. <a, b, c, d, e>: {a, b, c}, {a, b, d}, {a, b, e}, {a, c,
d}, {a, c, e}, {a, d, e}, {b, c, d}, {b, c, e}, {b, d, e}, {c,
d, e}

C2. <a, b, f, g>: {a, b, f}, {a, b, g}, {a, f, g}, {b, f, g}
Jaccard co-efficient may lead to wrong clustering result

C1: 0.2 ({a, b, c}, {b, d, e}} to 0.5 ({a, b, c}, {a, b, d})
C1 & C2: could be as high as 0.5 ({a, b, c}, {a, b, T
f})
1 T2
Sim( T , T )
Jaccard co-efficient-based similarity function: 1 2
T1 T2

{c{c,
} d, e} 1
Ex. LetSim
T1 (=T {a,
b, c}, T2 =
1, T 2 )

0.2
{a, b, c, d , e}

May 24, 2015

Data Mining: Concepts and

Techniques

51

Link Measure in ROCK

Links: # of common neighbors

C1 <a, b, c, d, e>: {a, b, c}, {a, b, d}, {a, b, e}, {a, c, d}, {a,
c, e}, {a, d, e}, {b, c, d}, {b, c, e}, {b, d, e}, {c, d, e}

C2 <a, b, f, g>: {a, b, f}, {a, b, g}, {a, f, g}, {b, f, g}

Let T1 = {a, b, c}, T2 = {c, d, e}, T3 = {a, b, f}

link(T1, T2) = 4, since they have 4 common neighbors

link(T1, T3) = 3, since they have 3 common neighbors

{a, c, d}, {a, c, e}, {b, c, d}, {b, c, e}

{a, b, d}, {a, b, e}, {a, b, g}

Thus link is a better measure than Jaccard coefficient

May 24, 2015

Data Mining: Concepts and

Techniques

52

CHAMELEON: Hierarchical Clustering

Using Dynamic Modeling (1999)

CHAMELEON: by G. Karypis, E.H. Han, and V. Kumar99

Measures the similarity based on a dynamic model

Two clusters are merged only if the interconnectivity and

closeness (proximity) between two clusters are high relative to
the internal interconnectivity of the clusters and closeness of
items within the clusters

Cure ignores information about interconnectivity of the

objects, Rock ignores information about the closeness of two
clusters

A two-phase algorithm
1.

2.

Use a graph partitioning algorithm: cluster objects into a large

number of relatively small sub-clusters
Use an agglomerative hierarchical clustering algorithm: find the
genuine clusters by repeatedly combining these sub-clusters

May 24, 2015

Data Mining: Concepts and

Techniques

53

Overall Framework of
CHAMELEON
Construct
Partition the Graph

Sparse Graph

Data Set

Merge Partition
Final Clusters

May 24, 2015

Data Mining: Concepts and

Techniques

54

CHAMELEON (Clustering Complex

Objects)

May 24, 2015

Data Mining: Concepts and

Techniques

55

Chapter 7. Cluster Analysis

1. What is Cluster Analysis?
2. Types of Data in Cluster Analysis
3. A Categorization of Major Clustering Methods
4. Partitioning Methods
5. Hierarchical Methods
6. Density-Based Methods
7. Grid-Based Methods
8. Model-Based Methods
9. Clustering High-Dimensional Data
10. Constraint-Based Clustering
11. Outlier Analysis
12. Summary
May 24, 2015

Data Mining: Concepts and

Techniques

56

Density-Based Clustering Methods

Clustering based on density (local cluster criterion),

such as density-connected points
Major features:
Discover clusters of arbitrary shape
Handle noise
One scan
Need density parameters as termination condition
Several interesting studies:
DBSCAN: Ester, et al. (KDD96)
OPTICS: Ankerst, et al (SIGMOD99).
DENCLUE: Hinneburg & D. Keim (KDD98)
CLIQUE: Agrawal, et al. (SIGMOD98) (more gridbased)

May 24, 2015

Data Mining: Concepts and

Techniques

57

Density-Based Clustering: Basic

Concepts

Two parameters:

Eps: Maximum radius of the neighbourhood

MinPts: Minimum number of points in an Epsneighbourhood of that point

NEps(p):

Directly density-reachable: A point p is directly

density-reachable from a point q w.r.t. Eps, MinPts if

{q belongs to D | dist(p,q) <= Eps}

p belongs to NEps(q)

core point condition:

MinPts = 5
Eps = 1 cm

|NEps (q)| >=

MinPts
Data Mining: Concepts and
May 24, 2015

Techniques

58

Density-Reachable and Density-Connected

Density-reachable:

A point p is density-reachable
from a point q w.r.t. Eps, MinPts if
there is a chain of points p1, ,
pn, p1 = q, pn = p such that pi+1 is
directly density-reachable from pi

Density-connected

A point p is density-connected to
a point q w.r.t. Eps, MinPts if there
is a point o such that both, p and
q are density-reachable from o
w.r.t. Eps and MinPts

May 24, 2015

Data Mining: Concepts and

Techniques

p
p1

q
o

59

DBSCAN: Density Based Spatial

Clustering of Applications with Noise

Relies on a density-based notion of cluster: A

cluster is defined as a maximal set of densityconnected points
Discovers clusters of arbitrary shape in spatial
databases with noise
Outlier
Border

Eps = 1cm

Core

May 24, 2015

MinPts = 5

Data Mining: Concepts and

Techniques

60

DBSCAN: The Algorithm

Arbitrary select a point p

Retrieve all points density-reachable from p w.r.t.

Eps and MinPts.

If p is a core point, a cluster is formed.

If p is a border point, no points are densityreachable from p and DBSCAN visits the next point
of the database.

Continue the process until all of the points have

been processed.

May 24, 2015

Data Mining: Concepts and

Techniques

61

DBSCAN: Sensitive to
Parameters

May 24, 2015

Data Mining: Concepts and

Techniques

62

CHAMELEON (Clustering Complex

Objects)

May 24, 2015

Data Mining: Concepts and

Techniques

63

OPTICS: A Cluster-Ordering Method

(1999)

OPTICS: Ordering Points To Identify the Clustering

Structure
Ankerst, Breunig, Kriegel, and Sander (SIGMOD99)
Produces a special order of the database wrt its
density-based clustering structure
This cluster-ordering contains info equiv to the
density-based clusterings corresponding to a
broad range of parameter settings
Good for both automatic and interactive cluster
analysis, including finding intrinsic clustering
structure
Can be represented graphically or using
visualization techniques

May 24, 2015

Data Mining: Concepts and

Techniques

64

OPTICS: Some Extension from

DBSCAN

Index-based:
k = number of dimensions
N = 20
p = 75%
M = N(1-p) = 5

Complexity: O(kN2)

Core Distance

p1

Reachability Distance

o
p2

Max (core-distance (o), d (o, p))

o
MinPts = 5

r(p1, o) = 2.8cm. r(p2,o) =Data

4cm
Mining: Concepts and
= 3 cm
May 24, 2015
Techniques

65

Reachability
-distance

undefined

May 24, 2015

Data Mining: Concepts and

Techniques

Cluster-order
of the objects

66

Density-Based Clustering: OPTICS & Its

Applications

May 24, 2015

Data Mining: Concepts and

Techniques

67

DENCLUE: Using Statistical Density

Functions

DENsity-based CLUstEring by Hinneburg & Keim (KDD98)

Using statistical density functions:

f Gaussian ( x , y ) e

Major features

D
Gaussian

D
Gaussian

d ( x , y )2
2 2

( x ) i 1 e
N

d ( x , xi ) 2
2 2

( x, xi ) i 1 ( xi x) e
N

Solid mathematical foundation

Good for data sets with large amounts of noise

Allows a compact mathematical description of arbitrarily

shaped clusters in high-dimensional data sets

Significant faster than existing algorithm (e.g., DBSCAN)

But needs a large number of parameters

May 24, 2015

Data Mining: Concepts and

Techniques

d ( x , xi ) 2
2 2

68

Denclue: Technical Essence

Uses grid cells but only keeps information about grid

cells that do actually contain data points and
manages these cells in a tree-based access structure

Influence function: describes the impact of a data

point within its neighborhood

Overall density of the data space can be calculated

as the sum of the influence function of all data points

Clusters can be determined mathematically by

identifying density attractors

Density attractors are local maximal of the overall

density function

May 24, 2015

Data Mining: Concepts and

Techniques

69

Density Attractor

May 24, 2015

Data Mining: Concepts and

Techniques

70

Center-Defined and Arbitrary

May 24, 2015

Data Mining: Concepts and

Techniques

71

Chapter 7. Cluster Analysis

1. What is Cluster Analysis?
2. Types of Data in Cluster Analysis
3. A Categorization of Major Clustering Methods
4. Partitioning Methods
5. Hierarchical Methods
6. Density-Based Methods
7. Grid-Based Methods
8. Model-Based Methods
9. Clustering High-Dimensional Data
10. Constraint-Based Clustering
11. Outlier Analysis
12. Summary
May 24, 2015

Data Mining: Concepts and

Techniques

72

Grid-Based Clustering Method

Using multi-resolution grid data structure

Several interesting methods

STING (a STatistical INformation Grid approach) by

Wang, Yang and Muntz (1997)

WaveCluster by Sheikholeslami, Chatterjee, and Zhang

(VLDB98)

A multi-resolution clustering approach using wavelet

method

CLIQUE: Agrawal, et al. (SIGMOD98)

May 24, 2015

On high-dimensional data (thus put in the section of

clustering high-dimensional data
Data Mining: Concepts and
Techniques

73

STING: A Statistical Information Grid

Approach

Wang, Yang and Muntz (VLDB97)

The spatial area area is divided into rectangular
cells
There are several levels of cells corresponding to
different levels of resolution

May 24, 2015

Data Mining: Concepts and

Techniques

74

The STING Clustering Method

Each cell at a high level is partitioned into a number of

smaller cells in the next lower level
Statistical info of each cell is calculated and stored
beforehand and is used to answer queries
Parameters of higher level cells can be easily calculated
from parameters of lower level cell
count, mean, s, min, max
type of distributionnormal, uniform, etc.
Use a top-down approach to answer spatial data queries
Start from a pre-selected layertypically with a small
number of cells
For each cell in the current level compute the confidence
interval

May 24, 2015

Data Mining: Concepts and

Techniques

75

Comments on STING

Remove the irrelevant cells from further consideration

When finish examining the current layer, proceed to

the next lower level

Repeat this process until the bottom layer is reached

Advantages:

Query-independent, easy to parallelize, incremental

update

O(K), where K is the number of grid cells at the

lowest level

Disadvantages:

All the cluster boundaries are either horizontal or

vertical, and no diagonal boundary is detected

May 24, 2015

Data Mining: Concepts and

Techniques

76

WaveCluster: Clustering by Wavelet Analysis

(1998)

Sheikholeslami, Chatterjee, and Zhang (VLDB98)

A multi-resolution clustering approach which applies wavelet

transform to the feature space

How to apply wavelet transform to find clusters

Summarizes the data by imposing a multidimensional

grid structure onto data space

These multidimensional spatial data objects are

represented in a n-dimensional feature space

Apply wavelet transform on feature space to find the

dense regions in the feature space

Apply wavelet transform multiple times which result in

clusters at different scales from fine to coarse

May 24, 2015

Data Mining: Concepts and

Techniques

77

Wavelet Transform

Wavelet transform: A signal processing technique that

decomposes a signal into different frequency sub-band
(can be applied to n-dimensional signals)
Data are transformed to preserve relative distance
between objects at different levels of resolution
Allows natural clusters to become more distinguishable

May 24, 2015

Data Mining: Concepts and

Techniques

78

The WaveCluster Algorithm

Input parameters
# of grid cells for each dimension
the wavelet, and the # of applications of wavelet transform
Why is wavelet transformation useful for clustering?
Use hat-shape filters to emphasize region where points
cluster, but simultaneously suppress weaker information in
their boundary
Effective removal of outliers, multi-resolution, cost effective
Major features:
Complexity O(N)
Detect arbitrary shaped clusters at different scales
Not sensitive to noise, not sensitive to input order
Only applicable to low dimensional data
Both grid-based and density-based

May 24, 2015

Data Mining: Concepts and

Techniques

79

Quantization
& Transformation

First, quantize data into m-D grid

structure, then wavelet transform
a) scale 1: high resolution
b) scale 2: medium resolution
c) scale 3: low resolution

May 24, 2015

Data Mining: Concepts and

Techniques

80

Chapter 7. Cluster Analysis

1. What is Cluster Analysis?
2. Types of Data in Cluster Analysis
3. A Categorization of Major Clustering Methods
4. Partitioning Methods
5. Hierarchical Methods
6. Density-Based Methods
7. Grid-Based Methods
8. Model-Based Methods
9. Clustering High-Dimensional Data
10. Constraint-Based Clustering
11. Outlier Analysis
12. Summary
May 24, 2015

Data Mining: Concepts and

Techniques

81

Model-Based Clustering

What is model-based clustering?

Attempt to optimize the fit between the given
data and some mathematical model
Based on the assumption: Data are generated by
a mixture of underlying probability distribution
Typical methods
Statistical approach

Machine learning approach

EM (Expectation maximization), AutoClass

COBWEB, CLASSIT

Neural network approach

May 24, 2015

SOM (Self-Organizing Feature Map)

Data Mining: Concepts and
Techniques

82

EM Expectation Maximization

EM A popular iterative refinement algorithm

An extension to k-means

Assign each object to a cluster according to a weight (prob.

distribution)

New means are computed based on weighted measures

General idea

Starts with an initial estimate of the parameter vector

Iteratively rescores the patterns against the mixture density

produced by the parameter vector

The rescored patterns are used to update the parameter

updates

Patterns belonging to the same cluster, if they are placed by

their scores in a particular component

Algorithm converges fast but may not be in global optima

May 24, 2015

Data Mining: Concepts and

Techniques

83

The EM (Expectation Maximization)

Algorithm

Initially, randomly assign k cluster centers

Iteratively refine the clusters based on two steps
Expectation step: assign each data point X to
i
cluster Ci with the following probability

Maximization step:
Estimation of model parameters

May 24, 2015

Data Mining: Concepts and

Techniques

84

Conceptual Clustering

Conceptual clustering
A form of clustering in machine learning
Produces a classification scheme for a set of
unlabeled objects
Finds characteristic description for each concept
(class)
COBWEB (Fisher87)
A popular a simple method of incremental
conceptual learning
Creates a hierarchical clustering in the form of a
classification tree
Each node refers to a concept and contains a
probabilistic description of that concept

May 24, 2015

Data Mining: Concepts and

Techniques

85

COBWEB Clustering
Method
A classification tree

May 24, 2015

Data Mining: Concepts and

Techniques

86

More on Conceptual Clustering

Limitations of COBWEB

The assumption that the attributes are independent of each

other is often too strong because correlation may exist

Not suitable for clustering large database data skewed tree

and expensive probability distributions

CLASSIT

an extension of COBWEB for incremental clustering of

continuous data

suffers similar problems as COBWEB

AutoClass (Cheeseman and Stutz, 1996)

Uses Bayesian statistical analysis to estimate the number of

clusters

Popular in industry

May 24, 2015

Data Mining: Concepts and

Techniques

87

Neural Network Approach

Neural network approaches

Represent each cluster as an exemplar, acting
as a prototype of the cluster
New objects are distributed to the cluster whose
exemplar is the most similar according to some
distance measure
Typical methods
SOM (Soft-Organizing feature Map)
Competitive learning

May 24, 2015

Involves a hierarchical architecture of several units

(neurons)
Neurons compete in a winner-takes-all fashion for
the object currently being presented
Data Mining: Concepts and
Techniques

88

Self-Organizing Feature Map (SOM)

SOMs, also called topological ordered maps, or Kohonen SelfOrganizing Feature Map (KSOMs)

It maps all the points in a high-dimensional source space into a 2 to

3-d target space, s.t., the distance and proximity relationship (i.e.,
topology) are preserved as much as possible

Similar to k-means: cluster centers tend to lie in a low-dimensional

manifold in the feature space

Clustering is performed by having several units competing for the

current object

The unit whose weight vector is closest to the current object wins

The winner and its neighbors learn by having their weights

adjusted

SOMs are believed to resemble processing that can occur in the brain

Useful for visualizing high-dimensional data in 2- or 3-D space

May 24, 2015

Data Mining: Concepts and

Techniques

89

Web Document Clustering Using

SOM

The result of
SOM clustering
of 12088 Web
articles

The picture on
the right:
drilling down
on the keyword
mining

Based on
[Link]
Web page
May 24, 2015

Data Mining: Concepts and

Techniques

90

Chapter 6. Cluster Analysis

1. What is Cluster Analysis?
2. Types of Data in Cluster Analysis
3. A Categorization of Major Clustering Methods
4. Partitioning Methods
5. Hierarchical Methods
6. Density-Based Methods
7. Grid-Based Methods
8. Model-Based Methods
9. Clustering High-Dimensional Data
10. Constraint-Based Clustering
11. Outlier Analysis
12. Summary
May 24, 2015

Data Mining: Concepts and

Techniques

91

Clustering High-Dimensional Data

Clustering high-dimensional data

Many applications: text documents, DNA micro-array data

Major challenges:

Many irrelevant dimensions may mask clusters

Distance measure becomes meaninglessdue to equi-distance

Clusters may exist only in some subspaces

Methods

Feature transformation: only effective if most dimensions are relevant

Feature selection: wrapper or filter approaches

PCA & SVD useful only when features are highly

correlated/redundant
useful to find a subspace where the data have nice clusters

Subspace-clustering: find clusters in all the possible subspaces

May 24, 2015

CLIQUE, ProClus, and frequent pattern-based clustering

Data Mining: Concepts and
Techniques

92

The Curse of Dimensionality

(graphs adapted from Parsons et al. KDD Explorations
2004)

Data in only one dimension is

relatively packed

Adding a dimension stretch the

points across that dimension,
making them further apart

Adding more dimensions will make

the points further aparthigh
dimensional data is extremely
sparse

Distance measure becomes

meaninglessdue to equi-distance

May 24, 2015

Data Mining: Concepts and

Techniques

93

Why Subspace Clustering?

(adapted from Parsons et al. SIGKDD Explorations
2004)

May 24, 2015

Clusters may exist only in some subspaces

Subspace-clustering: find clusters in all the subspaces

Data Mining: Concepts and

Techniques

94

CLIQUE (Clustering In QUEst)

Agrawal, Gehrke, Gunopulos, Raghavan (SIGMOD98)

Automatically identifying subspaces of a high dimensional data

space that allow better clustering than original space

CLIQUE can be considered as both density-based and grid-based

It partitions each dimension into the same number of equal

length interval

It partitions an m-dimensional data space into nonoverlapping rectangular units

A unit is dense if the fraction of total data points contained in

the unit exceeds the input model parameter

A cluster is a maximal set of connected dense units within a

subspace

May 24, 2015

Data Mining: Concepts and

Techniques

95

CLIQUE: The Major Steps

Partition the data space and find the number of points

that lie inside each cell of the partition.

Identify the subspaces that contain clusters using the

Apriori principle

Identify clusters

Determine dense units in all subspaces of interests

Determine connected dense units in all subspaces
of interests.

Generate minimal description for the clusters

Determine maximal regions that cover a cluster of
connected dense units for each cluster
Determination of minimal cover for each cluster

May 24, 2015

Data Mining: Concepts and

Techniques

96

40

50

la
a
S

May 24, 2015

20

30

40

50

age
60

Vacation

=3

30

Vacation(
week)
0 1 2 3 4 5 6 7

Salary
(10,000)
0 1 2 3 4 5 6 7
20

age
60

ry

30

50

Data Mining: Concepts and

Techniques

age

97

Strength and Weakness of

CLIQUE

Strength
automatically finds subspaces of the highest
dimensionality such that high density clusters exist
in those subspaces
insensitive to the order of records in input and does
not presume some canonical data distribution
scales linearly with the size of input and has good
scalability as the number of dimensions in the data
increases
Weakness
The accuracy of the clustering result may be
degraded at the expense of simplicity of the method

May 24, 2015

Data Mining: Concepts and

Techniques

98

Frequent Pattern-Based Approach

Clustering high-dimensional space (e.g., clustering text

documents, microarray data)

Projected subspace-clustering: which dimensions to be

projected on?

CLIQUE, ProClus

Feature extraction: costly and may not be effective?

Using frequent patterns as features

Frequent are inherent features

Mining freq. patterns may not be so expensive

Typical methods

Frequent-term-based document clustering

Clustering by pattern similarity in micro-array data

(pClustering)

May 24, 2015

Data Mining: Concepts and

Techniques

99

Clustering by Pattern Similarity (pClustering)

Right: The micro-array raw data

shows 3 genes and their values in a
multi-dimensional space

Difficult to find their patterns

Bottom: Some subsets of dimensions

form nice shift and scaling patterns

May 24, 2015

Data Mining: Concepts and

Techniques

100

Why p-Clustering?

Microarray data analysis may need to

Clustering on thousands of dimensions (attributes)

Discovery of both shift and scaling patterns

Clustering with Euclidean distance measure? cannot find shift patterns

Clustering on derived attribute Aij = ai aj? introduces N(N-1) dimensions

Bi-cluster using transformed mean-squared residue score matrix (I, J)

Where

1
1
1
d
d
d
d

d
IJ | I || J |
ij
Ij | I |
ij
ij | J |
ij
i I, j J
I some > 0
A submatrix is a -cluster
if H(I, J) i
for
jJ

Problems with bi-cluster

No downward closure property,

Due to averaging, it may contain outliers but still within -threshold

May 24, 2015

Data Mining: Concepts and

Techniques

101

p-Clustering:
Clustering by
Pattern Similarity

Given object x, y in O and features a, b in T, pCluster is a 2 by

2 matrix
d xa d xb
) | (d xa d xb ) (d ya d yb ) |

d ya d yb

pScore(

A pair (O, T) is in -pCluster if for any 2 by 2 matrix X in (O, T),

pScore(X) for some > 0

Properties of -pCluster

Downward closure

Clusters are more homogeneous than bi-cluster (thus the

name: pair-wise Cluster)

Pattern-growth algorithm has been developed for efficient

mining
d xa / d ya

d xbon
/ d yb
For scaling patterns, one can observe, taking logarithmic

will lead to the pScore

Dataform
Mining: Concepts and
May 24, 2015

Techniques

102

Chapter 6. Cluster Analysis

1. What is Cluster Analysis?
2. Types of Data in Cluster Analysis
3. A Categorization of Major Clustering Methods
4. Partitioning Methods
5. Hierarchical Methods
6. Density-Based Methods
7. Grid-Based Methods
8. Model-Based Methods
9. Clustering High-Dimensional Data
10. Constraint-Based Clustering
11. Outlier Analysis
12. Summary
May 24, 2015

Data Mining: Concepts and

Techniques

103

Why Constraint-Based Cluster

Analysis?

Need user feedback: Users know their applications the best

Less parameters but more user-desired constraints, e.g., an
ATM allocation problem: obstacle & desired clusters

May 24, 2015

Data Mining: Concepts and

Techniques

104

A Classification of Constraints in Cluster

Analysis

Clustering in applications: desirable to have user-guided

(i.e., constrained) cluster analysis
Different constraints in cluster analysis:
Constraints on individual objects (do selection first)

Constraints on distance or similarity functions

# of clusters, MinPts, etc.

User-specified constraints

Weighted functions, obstacles (e.g., rivers, lakes)

Constraints on the selection of clustering parameters

Cluster on houses worth over $300K

Contain at least 500 valued customers and 5000 ordinary

ones

Semi-supervised: giving small training sets as

constraints or hints

May 24, 2015

Data Mining: Concepts and

Techniques

105

Clustering With Obstacle Objects

K-medoids is more preferable since

k-means may locate the ATM center
in the middle of a lake

Visibility graph and shortest path

Triangulation and micro-clustering

Two kinds of join indices (shortestpaths) worth pre-computation

VV index: indices for any pair of

obstacle vertices

MV index: indices for any pair of

micro-cluster and obstacle indices

May 24, 2015

Data Mining: Concepts and

Techniques

106

An Example: Clustering With Obstacle

Objects

Not Taking obstacles into account

May 24, 2015

Taking obstacles into account

Data Mining: Concepts and

Techniques

107

Clustering with User-Specified Constraints

Example: Locating k delivery centers, each serving at

least m valued customers and n ordinary ones
Proposed approach
Find an initial solution by partitioning the data set
into k groups and satisfying user-constraints
Iteratively refine the solution by micro-clustering
relocation (e.g., moving -clusters from cluster Ci
to Cj) and deadlock handling (break the
microclusters when necessary)
Efficiency is improved by micro-clustering
How to handle more complicated constraints?
E.g., having approximately same number of valued
customers in each cluster?! Can you solve it?

May 24, 2015

Data Mining: Concepts and

Techniques

108

Chapter 7. Cluster Analysis

1. What is Cluster Analysis?
2. Types of Data in Cluster Analysis
3. A Categorization of Major Clustering Methods
4. Partitioning Methods
5. Hierarchical Methods
6. Density-Based Methods
7. Grid-Based Methods
8. Model-Based Methods
9. Clustering High-Dimensional Data
10. Constraint-Based Clustering
11. Outlier Analysis
12. Summary
May 24, 2015

Data Mining: Concepts and

Techniques

109

What Is Outlier Discovery?

What are outliers?

The set of objects are considerably dissimilar
from the remainder of the data
Example: Sports: Michael Jordon, Wayne
Gretzky, ...
Problem: Define and find outliers in large data sets
Applications:
Credit card fraud detection
Telecom fraud detection
Customer segmentation
Medical analysis

May 24, 2015

Data Mining: Concepts and

Techniques

110

Outlier Discovery:
Statistical
Approaches

Assume a model underlying distribution that

generates data set (e.g. normal distribution)
Use discordancy tests depending on
data distribution
distribution parameter (e.g., mean, variance)
number of expected outliers
Drawbacks
most tests are for single attribute
In many cases, data distribution may not be known

May 24, 2015

Data Mining: Concepts and

Techniques

111

Outlier Discovery: Distance-Based

Approach

Introduced to counter the main limitations imposed

by statistical methods
We need multi-dimensional analysis without
knowing data distribution
Distance-based outlier: A DB(p, D)-outlier is an
object O in a dataset T such that at least a fraction
p of the objects in T lies at a distance greater than
D from O
Algorithms for mining distance-based outliers
Index-based algorithm
Nested-loop algorithm
Cell-based algorithm

May 24, 2015

Data Mining: Concepts and

Techniques

112

Density-Based Local
Outlier Detection

Distance-based outlier
detection is based on global
distance distribution
It encounters difficulties to
identify outliers if data is not
uniformly distributed
Ex. C1 contains 400 loosely
distributed points, C2 has 100
tightly condensed points, 2
outlier points o1, o2
Distance-based method
cannot identify o2 as an outlier
Need the concept of local
outlier

May 24, 2015

Local outlier factor

(LOF)
Assume outlier is not
crisp
Each point has a LOF

Data Mining: Concepts and

Techniques

113

Outlier Discovery: Deviation-Based

Approach

Identifies outliers by examining the main

characteristics of objects in a group

Objects that deviate from this description are

considered outliers

Sequential exception technique

simulates the way in which humans can

distinguish unusual objects from among a
series of supposedly like objects

OLAP data cube technique

uses data cubes to identify regions of

anomalies in large multidimensional data

May 24, 2015

Data Mining: Concepts and

Techniques

114

Chapter 7. Cluster Analysis

1. What is Cluster Analysis?
2. Types of Data in Cluster Analysis
3. A Categorization of Major Clustering Methods
4. Partitioning Methods
5. Hierarchical Methods
6. Density-Based Methods
7. Grid-Based Methods
8. Model-Based Methods
9. Clustering High-Dimensional Data
10. Constraint-Based Clustering
11. Outlier Analysis
12. Summary
May 24, 2015

Data Mining: Concepts and

Techniques

115

Summary

Cluster analysis groups objects based on their

similarity and has wide applications

Measure of similarity can be computed for various

types of data

Clustering algorithms can be categorized into

partitioning methods, hierarchical methods, densitybased methods, grid-based methods, and model-based
methods

Outlier detection and analysis are very useful for fraud

detection, etc. and can be performed by statistical,
distance-based or deviation-based approaches

There are still lots of research issues on cluster analysis

May 24, 2015

Data Mining: Concepts and

Techniques

116

Problems and Challenges

Considerable progress has been made in scalable

clustering methods

Partitioning: k-means, k-medoids, CLARANS

Hierarchical: BIRCH, ROCK, CHAMELEON

Density-based: DBSCAN, OPTICS, DenClue

Grid-based: STING, WaveCluster, CLIQUE

Model-based: EM, Cobweb, SOM

Frequent pattern-based: pCluster

Constraint-based: COD, constrained-clustering

Current clustering techniques do not address all the

requirements adequately, still an active area of
research

May 24, 2015

Data Mining: Concepts and

Techniques

117

References (1)

R. Agrawal, J. Gehrke, D. Gunopulos, and P. Raghavan. Automatic subspace clustering of

high dimensional data for data mining applications. SIGMOD'98

M. R. Anderberg. Cluster Analysis for Applications. Academic Press, 1973.

M. Ankerst, M. Breunig, H.-P. Kriegel, and J. Sander. Optics: Ordering points to identify the
clustering structure, SIGMOD99.

P. Arabie, L. J. Hubert, and G. De Soete. Clustering and Classification. World Scientific, 1996

Beil F., Ester M., Xu X.: "Frequent Term-Based Text Clustering", KDD'02

M. M. Breunig, H.-P. Kriegel, R. Ng, J. Sander. LOF: Identifying Density-Based Local Outliers.
SIGMOD 2000.

M. Ester, H.-P. Kriegel, J. Sander, and X. Xu. A density-based algorithm for discovering
clusters in large spatial databases. KDD'96.

M. Ester, H.-P. Kriegel, and X. Xu. Knowledge discovery in large spatial databases: Focusing
techniques for efficient class identification. SSD'95.

D. Fisher. Knowledge acquisition via incremental conceptual clustering. Machine Learning,

2:139-172, 1987.

D. Gibson, J. Kleinberg, and P. Raghavan. Clustering categorical data: An approach based

on dynamic systems. VLDB98.

May 24, 2015

Data Mining: Concepts and

Techniques

118

References (2)

V. Ganti, J. Gehrke, R. Ramakrishan. CACTUS Clustering Categorical Data Using Summaries.

KDD'99.

D. Gibson, J. Kleinberg, and P. Raghavan. Clustering categorical data: An approach based on

dynamic systems. In Proc. VLDB98.

S. Guha, R. Rastogi, and K. Shim. Cure: An efficient clustering algorithm for large databases.
SIGMOD'98.

S. Guha, R. Rastogi, and K. Shim. ROCK: A robust clustering algorithm for categorical
attributes. In ICDE'99, pp. 512-521, Sydney, Australia, March 1999.

A. Hinneburg, D.l A. Keim: An Efficient Approach to Clustering in Large Multimedia Databases

with Noise. KDD98.

A. K. Jain and R. C. Dubes. Algorithms for Clustering Data. Printice Hall, 1988.
G. Karypis, E.-H. Han, and V. Kumar. CHAMELEON: A Hierarchical Clustering Algorithm Using
Dynamic Modeling. COMPUTER, 32(8): 68-75, 1999.

L. Kaufman and P. J. Rousseeuw. Finding Groups in Data: an Introduction to Cluster Analysis.

John Wiley & Sons, 1990.

E. Knorr and R. Ng. Algorithms for mining distance-based outliers in large datasets. VLDB98.

G. J. McLachlan and K.E. Bkasford. Mixture Models: Inference and Applications to Clustering.
John Wiley and Sons, 1988.

P. Michaud. Clustering techniques. Future Generation Computer systems, 13, 1997.

R. Ng and J. Han. Efficient and effective clustering method for spatial data mining. VLDB'94.

May 24, 2015

Data Mining: Concepts and

Techniques

119

References (3)

L. Parsons, E. Haque and H. Liu, Subspace Clustering for High Dimensional Data: A
Review , SIGKDD Explorations, 6(1), June 2004

E. Schikuta. Grid clustering: An efficient hierarchical clustering method for very large
data sets. Proc. 1996 Int. Conf. on Pattern Recognition,.

G. Sheikholeslami, S. Chatterjee, and A. Zhang. WaveCluster: A multi-resolution

clustering approach for very large spatial databases. VLDB98.

A. K. H. Tung, J. Han, L. V. S. Lakshmanan, and R. T. Ng. Constraint-Based Clustering in

Large Databases, ICDT'01.

A. K. H. Tung, J. Hou, and J. Han. Spatial Clustering in the Presence of Obstacles ,

ICDE'01

H. Wang, W. Wang, J. Yang, and P.S. Yu. Clustering by pattern similarity in large data
sets, SIGMOD 02.

W. Wang, Yang, R. Muntz, STING: A Statistical Information grid Approach to Spatial

Data Mining, VLDB97.

T. Zhang, R. Ramakrishnan, and M. Livny. BIRCH : an efficient data clustering method

for very large databases. SIGMOD'96.

May 24, 2015

Data Mining: Concepts and

Techniques

120