Cluster Analysis

1. What is Cluster Analysis?

2. Types of Data in Cluster Analysis
3. A Categorization of Major Clustering Methods
4. Density-Based Methods
5. Clustering High-Dimensional Data
6. Constraint-Based Clustering
7. Outlier Analysis
8. Summary

7/10/22 Data Mining: Concepts and Techniques 1

 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
7/10/22
 As a preprocessing step for other algorithms
Data Mining: Concepts and Techniques 2
 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
7/10/22 Data Mining: Concepts and Techniques 3
 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

7/10/22 Data Mining: Concepts and Techniques 4

 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

7/10/22 Data Mining: Concepts and Techniques 5

 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.

7/10/22 Data Mining: Concepts and Techniques 6

 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
7/10/22 Data Mining: Concepts and Techniques 7
 Cluster Analysis
1. What is Cluster Analysis?
2. Types of Data in Cluster Analysis
3. A Categorization of Major Clustering Methods
4. Density-Based Methods
5. Clustering High-Dimensional Data
6. Constraint-Based Clustering
7. Outlier Analysis
8. Summary

7/10/22 Data Mining: Concepts and Techniques 8

 Data Structures
 Data matrix
 x11 ... x1f ... x1p 
 (two modes)  
 ... ... ... ... ... 
x ... xif ... xip 
 i1 
 ... ... ... ... ... 
x ... xnf ... xnp 
 n1 
 Dissimilarity matrix
 0 
 (one mode)  d(2,1) 
 0 
 d(3,1) d ( 3,2) 0 
 
 : : : 
d ( n,1) d ( n,2) ... ... 0

7/10/22 Data Mining: Concepts and Techniques 9

 Type of data in clustering analysis

 Interval-scaled variables
 Binary variables
 Nominal, ordinal, and ratio variables

7/10/22 Data Mining: Concepts and Techniques 10

 Interval-valued variables

 Standardize data
 Calculate the mean absolute deviation:
sf  1
n (| x1 f  m f |  | x2 f  m f | ... | xnf  m f |)

where mf  1
n (x1 f  x2 f  ...  xnf )
.

 Calculate the standardized measurement (z-score)

xif  m f
zif  sf
 Using mean absolute deviation is more robust than using
standard deviation

7/10/22 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
 Some popular ones include: Minkowski distance:
d (i, j)  q (| x  x |q  | x  x |q ... | x  x |q )
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 is Manhattan distance
d (i, j) | x  x |  | x  x | ... | x  x |
i1 j1 i2 j 2 ip j p

7/10/22 Data Mining: Concepts and Techniques 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

7/10/22 Data Mining: Concepts and Techniques 13

 Binary Variables
Object j
1 0 sum
 A contingency table for 1 a b a b
Object i
binary data 0 c d cd
sum a  c b  d p
 Distance measure for bc
d (i, j) 
symmetric binary variables: a bc  d
 Distance measure for bc
d (i, j ) 
asymmetric binary variables: a bc
 Jaccard coefficient (similarity
measure for asymmetric simJaccard (i, j)  a
a bc
binary variables):
7/10/22 Data Mining: Concepts and Techniques 14
 Dissimilarity between Binary Variables

 Example
Name Gender Fever Cough Test-1 Test-2 Test-3 Test-4
Jack M Y N P N N N
Mary F Y N P N P N
Jim M Y P N 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

Jack
d (i, j )  bc 1 0 sum
a bc 1 2 1 3
Mary
0 0 3 3
sum 2 4 6
7/10/22 Data Mining: Concepts and Techniques 15
 Dissimilarity between Binary Variables

0 1 1
d (Mary, jack )    0.33
2 1 0 3
Jack
1 0 sum
1 2 1 3
Mary
0 0 3 3
sum 2 4 6
01
d ( jack , mary )   0.33
2 01
11
d ( jack , jim )   0.67
111
1 2
d ( jim , mary )   0.75
11 2

7/10/22 Data Mining: Concepts and Techniques 16

 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
d (i, j)  p 
p
m

 Method 2: use a large number of binary variables

 creating a new binary variable for each of the M
nominal states

7/10/22 Data Mining: Concepts and Techniques 17

 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 xif by their rank
 map the range of each variable onto [0, 1] by replacing
i-th object in the f-th variable by
rif 1
zif 
M f 1

 compute the dissimilarity using methods for interval-

scaled variables
7/10/22 Data Mining: Concepts and Techniques 18
 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 variables—not 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
7/10/22 Data Mining: Concepts and Techniques 19
 Cluster Analysis
1. What is Cluster Analysis?
2. Types of Data in Cluster Analysis
3. A Categorization of Major Clustering Methods
4. Density-Based Methods
5. Clustering High-Dimensional Data
6. Constraint-Based Clustering
7. Outlier Analysis
8. Summary

7/10/22 Data Mining: Concepts and Techniques 20

 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

7/10/22 Data Mining: Concepts and Techniques 21

 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
7/10/22 Data Mining: Concepts and Techniques 22
 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(Ki, Kj) = min(tip, tjq)
 Complete link: largest distance between an element in one cluster
and an element in the other, i.e., dis(Ki, Kj) = max(tip, tjq)
 Average: avg distance between an element in one cluster and an
element in the other, i.e., dis(Ki, 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
7/10/22 Data Mining: Concepts and Techniques 23
 Centroid, Radius and Diameter of a
Cluster (for numerical data sets)
 Centroid: the “middle” of a cluster iN 1(t )
Cm  N
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)

7/10/22 Data Mining: Concepts and Techniques 24

 Cluster Analysis
1. What is Cluster Analysis?
2. Types of Data in Cluster Analysis
3. A Categorization of Major Clustering Methods
4. Density-Based Methods
5. Clustering High-Dimensional Data
6. Constraint-Based Clustering
7. Outlier Analysis
8. Summary

7/10/22 Data Mining: Concepts and Techniques 25

 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. (KDD’96)

 OPTICS: Ankerst, et al (SIGMOD’99).

 DENCLUE: Hinneburg & D. Keim (KDD’98)

 CLIQUE: Agrawal, et al. (SIGMOD’98) (more grid-

based)
7/10/22 Data Mining: Concepts and Techniques 26
 Density-Based Clustering: Basic Concepts
 Two parameters:
 Eps: Maximum radius of the neighbourhood
 MinPts: Minimum number of points in an Eps-
neighbourhood of that point
 NEps(p): {q belongs to D | dist(p,q) <= Eps}
 Directly density-reachable: A point p is directly density-
reachable from a point q w.r.t. Eps, MinPts if
 p belongs to NEps(q)
 core point condition: p MinPts = 5
q Eps = 1 cm
|NEps (q)| >= MinPts

7/10/22 Data Mining: Concepts and Techniques 27

 Density-Reachable and Density-Connected
 Density-reachable:
 A point p is density-reachable p
from a point q w.r.t. Eps, MinPts if
p1
there is a chain of points p1, …, q
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 p q
point q w.r.t. Eps, MinPts if there
is a point o such that both, p and o
q are density-reachable from o
w.r.t. Eps and MinPts
7/10/22 Data Mining: Concepts and Techniques 28
 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 density-connected points
 Discovers clusters of arbitrary shape in spatial databases
with noise

Outlier

Border
Eps = 1cm
Core MinPts = 5

7/10/22 Data Mining: Concepts and Techniques 29

 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 density-reachable
from p and DBSCAN visits the next point of the database.
 Continue the process until all of the points have been
processed.

7/10/22 Data Mining: Concepts and Techniques 30

 DBSCAN: Sensitive to Parameters

7/10/22 Data Mining: Concepts and Techniques 31

 Cluster Analysis
1. What is Cluster Analysis?
2. Types of Data in Cluster Analysis
3. A Categorization of Major Clustering Methods
4. Density-Based Methods
5. Clustering High-Dimensional Data
6. Constraint-Based Clustering
7. Outlier Analysis
8. Summary

7/10/22 Data Mining: Concepts and Techniques 32

 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 meaningless—due to equi-distance
 Clusters may exist only in some subspaces
 Methods
 Feature transformation: only effective if most dimensions are relevant
 PCA & SVD useful only when features are highly correlated/redundant
 Feature selection: wrapper or filter approaches
 useful to find a subspace where the data have nice clusters
 Subspace-clustering: find clusters in all the possible subspaces
 CLIQUE, ProClus, and frequent pattern-based clustering

7/10/22 Data Mining: Concepts and Techniques 33

 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 apart—high dimensional
data is extremely sparse
 Distance measure becomes
meaningless—due to equi-distance

7/10/22 Data Mining: Concepts and Techniques 34

 CLIQUE (Clustering In QUEst)

 Agrawal, Gehrke, Gunopulos, Raghavan (SIGMOD’98)

 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 non-overlapping
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

7/10/22 Data Mining: Concepts and Techniques 35

 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

7/10/22 Data Mining: Concepts and Techniques 36

 Vacation
(10,000)

(week)
Salary

0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7

age age
20 30 40 50 60 20 30 40 50 60

=3
Vacation

r y 30 50
l a
Sa age

7/10/22 Data Mining: Concepts and Techniques 37

 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

7/10/22 Data Mining: Concepts and Techniques 38

 Cluster Analysis
1. What is Cluster Analysis?
2. Types of Data in Cluster Analysis
3. A Categorization of Major Clustering Methods
4. Density-Based Methods
5. Clustering High-Dimensional Data
6. Constraint-Based Clustering
7. Outlier Analysis
8. Summary

7/10/22 Data Mining: Concepts and Techniques 39

 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

7/10/22 Data Mining: Concepts and Techniques 40

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)

 Cluster on houses worth over $300K

 Constraints on distance or similarity functions
 Weighted functions, obstacles (e.g., rivers, lakes)
 Constraints on the selection of clustering parameters
 # of clusters, MinPts, etc.
 User-specified constraints
 Contain at least 500 valued customers and 5000 ordinary ones
 Semi-supervised: giving small training sets as
“constraints” or hints
7/10/22 Data Mining: Concepts and Techniques 41
 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 (shortest-
paths) worth pre-computation
 VV index: indices for any pair of
obstacle vertices
 MV index: indices for any pair of
micro-cluster and obstacle
indices
7/10/22 Data Mining: Concepts and Techniques 42
 An Example: Clustering With Obstacle Objects

Not Taking obstacles into account Taking obstacles into account

7/10/22 Data Mining: Concepts and Techniques 43
 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?

7/10/22 Data Mining: Concepts and Techniques 44
 Cluster Analysis
1. What is Cluster Analysis?
2. Types of Data in Cluster Analysis
3. A Categorization of Major Clustering Methods
4. Density-Based Methods
5. Clustering High-Dimensional Data
6. Constraint-Based Clustering
7. Outlier Analysis
8. Summary

7/10/22 Data Mining: Concepts and Techniques 45

 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

7/10/22 Data Mining: Concepts and Techniques 46

 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

7/10/22 Data Mining: Concepts and Techniques 47

 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

7/10/22 Data Mining: Concepts and Techniques 48

 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  Local outlier factor (LOF)
 Assume outlier is not
 Ex. C1 contains 400 loosely
crisp
distributed points, C2 has 100  Each point has a LOF
tightly condensed points, 2
outlier points o1, o2
 Distance-based method cannot
identify o2 as an outlier
 Need the concept of local outlier

7/10/22 Data Mining: Concepts and Techniques 49

 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

7/10/22 Data Mining: Concepts and Techniques 50

 Cluster Analysis
1. What is Cluster Analysis?
2. Types of Data in Cluster Analysis
3. A Categorization of Major Clustering Methods
4. Density-Based Methods
5. Clustering High-Dimensional Data
6. Constraint-Based Clustering
7. Outlier Analysis
8. Summary

7/10/22 Data Mining: Concepts and Techniques 51

 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, density-based 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

7/10/22 Data Mining: Concepts and Techniques 52

 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
7/10/22 Data Mining: Concepts and Techniques 53
 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, SIGMOD’99.
 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. VLDB’98.

7/10/22 Data Mining: Concepts and Techniques 54

 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. VLDB’98.
 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. KDD’98.
 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. VLDB’98.
 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.

7/10/22 Data Mining: Concepts and Techniques 55

 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. VLDB’98.
 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,
VLDB’97.
 T. Zhang, R. Ramakrishnan, and M. Livny. BIRCH : an efficient data clustering method for very
large databases. SIGMOD'96.

7/10/22 Data Mining: Concepts and Techniques 56