IEEE ICDM December –, A Fast and Flexible Clustering
Algorithm Using Binary Discretization
Mahito SUGIYAMA†,‡ ，Akihiro YAMAMOTO††

Kyoto University‡
JSPS Research Fellow
/Main Results
. BOOL (Bianry cOding Oriented cLustering)• A clustering algorithm for multivariate data
to detect arbitrarily shaped clusters• Noise tolerant• Robust to changes in input parameters
. BOOL is faster than K-means and the fastest among
the algorithms to detect arbitrarily shaped clusters• It is about two to three orders of magnitude faster thantwo state-of-the-art algorithms [Chaoji et al. SDM ,Chaoji et al. KAIS ] that can detect non-convex
clusters of arbitrary shapes

/Evaluation with Typical Benchmarks• We used four synthetic databases (DS - DS)
– From the CLUTO website∘ http://glaros.dtc.umn.edu/gkhome/views/cluto/• Typical benchmarks for (spatial) clustering– CHAMELEON [Karypis et al., ], SPARCL [Chaoji et al., ],ABACUS [Chaoji et al., ], and so on
DS1DS2300150DS3DS4400

400
2503002003001002001502001005010010050000100200300

400500600

0200400600

8000100200300

400500600

700

0100200300

400

500600700

/Results for Benchmarks• Running time (in seconds)– In table, n denotes the number of data points– Results for ABACUS and SPARCL are from [Chaoji et al., ]∘ Their source codes are not publicly available
Non-convex
DS
DS
DS
DS

ConvexnBOOL

DBSCAN ABACUS SPARCL K-means



.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

/Results (Original Data)
DS1DS2300

150

250

200

100

150

100

50

50

00100

200

300

400

500

600

0DS3200

400

600

800

DS4400

400
300
300
200
200
100
100

00100

200

300

400

500

600

700

0100

200

300

400

500

600

700

/

Results (BOOL)
DS1

DS2300

150

250

200

100

150

100

50

50

00

100

200

300

400

500

600

0DS3200

400

600

800

DS4400

400
300
300
200
200
100
100

00100

200

300

400

500

600

700

0100

200

300

400

500

600

700

/

Results (K-means)
DS1DS2300

150

250

200

100

150

100

50

50

00100

200

300

400

500

600

0DS3200

400

600

800

DS4400400
300
300200200100100001002003004005006007000100200300400500600700/Evaluation with Natural Images• We used four natural images– From the Berkeley segmentation database and benchmark∘ http://www.eecs.berkeley.edu/Research/Projects/
CS/vision/grouping/segbench/•  ×  in size, , pixels in total– The RGB (red-green-blue) values for each pixel were obtainedby pre-precessing, same as [Chaoji et al., ]Horse

Mushroom

PyramidRoad

/Results for Natural Images• Running time (in seconds)– In table, n denotes the number of data points– Results for ABACUS and SPARCL are from [Chaoji et al., ]Horse
Mushroom
PyramidRoadn

BOOL.
.
.
.

Non-convexConvex

ABACUS
.
.
.
.

Kmeans
.
.
.
.

SPARCL.
–––/

Results (Original Data)
Horse

Mushroom

Pyramid

Road

/

Results (BOOL)
Horse

Mushroom

Pyramid

Road

/

Results (K-means)Horse

Mushroom

PyramidRoad

/Results for UCI Data• Running time (in seconds)

ecoli
sonar
shuttlewdbc
winewine quality

ndK

BOOLK-meansDBSCAN







.
.
.
.
.
.

.
.
.
.
.
.

.
.
–
.
.
.

/

Results for UCI Data
• Adjusted Rand index

ecoli
sonar
shuttlewdbc
wine
wine quality

nd

K

BOOL

K-means

DBSCAN














.
.
.
.
.
.

.
.
.
.
.
.

.
.
–.
.
.

/

Motivation• The K-means algorithm is widely used
– Simple and eﬃcient– The main drawback is its limited clustering ability:
Non-spherical clusters cannot be found• Many shape-based algorithms have been proposed– Can ﬁnd clusters of arbitrary shape– Drawbacks:
. Not scalable (time complexity is quadratic or cubic)
. Not robust to input parameters/Key Strategy• Requirements:
. Fast (linear in data size)
. Robust
. Find arbitrary shaped clusters• Key idea: Translate input data onto binary words usingbinary discretization– A hierarchy of clusters is naturally produced byincreasing the accuracy of the discretization• Each cluster is constructed byagglomerating adjacent smaller clusters– performed linearly by sorting binary representations
/Clustering Process

idx

yabc
de

.
.
.
.
.

.
.
.
.
.

/

Discretize Database at Level Discretization level: idx

yabc
de

.
.
.
.
.

.
.
.
.
.

1001/

Discretize Database at Level Discretization level: idx

yabcde01101011101001/

Discretize Database at Level Discretization level: idxyabcde01101011101001/

Discretize Database at Level Discretization level: idx

yabcde01
101011101001/

Discretize Database at Level Discretization level: idx

yabcde01101011101001/

Discretize Database at Level Discretization level: idxyabcde01101011101001/Agglomerate Adjacent Clusters

Discretization level: idxyabcde01101011101001/Go to Next Levelidx

yabcde

.
.
.
.
.

.
.
.
.
.

/

Discretize Database at Level Discretization level: 3idx

yabcde02212123312100

123/

Discretize Database at Level Discretization level: 3idxyabcde02212123312100123/Agglomerate Adjacent Clusters

Discretization level: 3idxyabcde02212123312100123/Construct Clusters with Sorting

Discretization level: 3idxyabcde02212123312100123/

Sort by x-axis → Sort by y-axis

Discretization level: 3idxyaebdc02212112332100123/Compare Each Point to the Next Point

Discretization level: 3idxyaebdc02212112332100123/

Sort by x-axis

Discretization level: 3idxyadebc01222131232100123/Compare Each Point to the Next Point

Discretization level: 3idxyadebc01222131232100123/Finish (... or go to the next level)

Discretization level: 3idxyadebc01222131232100123/Distance Parameter ll=2
l=3
l=1

/

Noise Filtering by BOOL
• Noise ﬁltering is important in clustering• Deﬁne 𝒞⩾N ≔ {C ∈ 𝒞 ∣ #C ⩾ N} for a partition 𝒞– See a cluster C as noises if #C < N• Example: Given 𝒞 = {{0.1}, {0.4, 0.5, 0.6}, {0.9}}– 𝒞⩾2 = {{0.4, 0.5, 0.6}}, and 0.1 and 0.9 are noises• We input the number (noise parameter) N as the lower
bound of the size of cluster in BOOL

/Conclusion• We have developed a clustering algorithm BOOL
– Fastest w.r.t ﬁnding arbitrarily shaped clusters– Robust, highly scalable, and noise tolerant• The key to performance is discretization based on
the binary encoding and sorting of data points• Future work: BOOL is simple and can easily be extended
to other machine learning tasks– e.g., anomaly detection, semi-supervised learning

/Appendix

A-/A-Other Experiments• We evaluate BOOL experimentally to determine its scalability and eﬀectiveness for various types of databases– Randomly generated synthetic databases (d = 2)
– Famous synthetic databases for spatial clustering (d = 2)
– Real databases generated from natural images (d = 3)
– Real databases from the UCI repository (d = 7, 9, 30, 60)• We used Mac OS X version .. ( × .-GHz Quad-CoreIntel Xeon CPUs,  GB of memory)– BOOL was implemented in C, compiled with gcc ..
– All experiments were performed in R version ..
• All databases are pre-processed by min-max normalization in BOOL
A-/A-Speed w.r.t.  Data and  Clusters• Randomly generated synthetic databases– K = 5 (left), n = 10000 (right)
10Running time (s)104102

11

10-1

10-2

10-2

10-4

10-3

102 103 5·103 104 5·104 105 5·105 106
Number of data points n

BOOLK-means
DBSCAN

510 15 20 25 30 35 40
Number of clusters K

A-/A-Quality w.r.t.  Data and  Clusters

Adjusted Rand index• Randomly generated synthetic databases– K = 5 (left), n = 10000 (right)
1.00

1.0

0.98

0.9

0.96

0.8
0.7

0.94

0.6

0.92

0.5

0.9
102 103 5·103 104 5·104 105 5·105 106
Number of data points n0.4510 15 20 25 30 35 40
Number of clusters K

A-/A-Speed w.r.t. Input Parameters

Running time (s)• Randomly generated synthetic databases– K = 5 and n = 10000
0.020

0.020

0.015

0.015

0.010

0.010

0.005

0.005

002

4
68
Distance parameter l

1002
468
Noise parameter N

10A-/A-Quality w.r.t. Input Parameters• Randomly generated synthetic databases– K = 5 and n = 10000
Adjusted Rand index

1.00

1.2
1.0

0.98

0.8

0.96

0.6

0.94

0.4
0.2

0.920.902468
Distance parameter l

10-0.202468
Noise parameter N

10A-/A-Notation• We treat a target database as a relation[Garcia-Molina et al., ]– The columns are called attributes– The domain of each attribute is [0, 1]– Attributes are composed of natural numbers {1, 2, … , d}
∘ Each tuple corresponds to a data point in the d-dimensional
Euclidean space ℝd– xi is the value for attribute i of x
– For M ⊆ {1, 2, … , d}, πM (X) denotes a database that hasonly the columns for attributes M of X
• Clustering is partition of X into K subsets (clusters) C1 , … , CK– Ci ≠ ∅ and Ci ∩ Cj = ∅– We call 𝒞 = {C1 , … , CK } a partition of X– 𝒞(X) = {𝒞 ∣ 𝒞 is a partition of X}
A-/A-

Discretization• For a data point x in a database X, discretization at level k
is an operator Δk for x, where each value xi is mapped toa natural number m such that xi = 0 implies m = 0, andxi ≠ 0 implies
if 0 < xi ⩽ 2−k ,⎧0⎪
−k+1−k+21if2<x⩽2,im=⎨⎪ ...
⎩ 2k − 1 if 2−k+(k−1) < xi ⩽ 1.
– We use the same operator Δk for discretization of a database X;

i.e., each data point x in X is discretized to Δk (x) in the databaseΔk (X).

A-/A-Reachability• Given a distance parameter l ∈ ℕ, a data point x in X isreachable at level k from a data point y if there exists achain of points z1 , z2 , … , zp (p ⩾ 2) such that z1 = x, zp = y,and the distanced0 (Δk (zi ), Δk (zi+1 )) ⩽ 1 and d∞ (Δk (zi ), Δk (zi+1 )) ⩽ lfor all i ∈ {1, 2, … , p − 1}
– The distance between x and y is deﬁned bydd0 (x, y) = ∑ δ(xi , yi ), where δ =i=10 if xi = yi ,1 if xi ≠ yi ,d∞ (x, y) = max |xi − yi |i∈{1,…,d}in the L0 and L∞ metrics, respectively
A-/A-Pseudo-Code (/)Input: Database X,
lower bound on number of clusters K,
noise parameter N, anddistance parameter l
Output: Partition 𝒞function BOOL(X, K, N)
: k ← 1 // k is level of discretization
: repeat
: 𝒞 ← MAKEHIERARCHY(X, k, N)
: k ← k + 1
: until #𝒞 ⩾ K
: output 𝒞A-/A-Pseudo-Code (/)function MAKEHIERARCHY(X, k, N)
: 𝒞 ← {{x} ∣ x ∈ X}
: h ← d // d is number of attributes of X
: XD ← Δk (X) // discretize X at level k
: X ← Sπ1 (XD ) ∘ Sπ2 (XD ) ∘ … ∘ Sπd (XD ) (X): repeat
: X ← Sπh (XD ) (X): 𝒞 ← AGGL(X, 𝒞, h)
: h ← h − 1
: until h = 0
: 𝒞 ← {C ∈ 𝒞 ∣ #C ⩾ N}
: output 𝒞A-/A-Pseudo-Code (/)function AGGL(X, 𝒞, h): for each object x of X
: y ← successive object of x
: if d0 (Δk (x), Δk (y)) ⩽ 1 and d∞ (Δk (x), Δk (y)) ⩽ l then:delete C ∋ x and D ∋ y from 𝒞, and add C ∪ D
: end if
: end for
: output 𝒞A-/A-Level-k partition and Sorting• BOOL construct clusters through level-k partitions(k = 1, 2, 3, … )– A partition of a database X is a level-k partition, denoted by 𝒞k ,if it satisﬁes the following condition:
For all pairs x and y, the pair are in the same cluster iﬀ y is reachable at level k from x• Sorting of a database X is deﬁned as follows:– Let Y be a key database s.t. #X = #Y and Y has only one of X’s
attributes– The expression SY (X) is the database X for which data points
are sorted in the order indicated by Y∘ Ties keep the original order of X
A-/A-Properties of Reachability• If the distance parameter l = 1, the condition is exactly thesame as
d1 (Δk (zi ), Δk (zi+1 )) ⩽ 1– d1 is the Manhattan distance (L1 metric)• The notion of reachability is symmetric– If a data point x is reachable at level k from y, then y isreachable from xA-/A-Hierarchy of Clusters• Level-k partitions have a hierarchical structure• For the level-k and k + 1 partitions 𝒞k and 𝒞k+1 ,the following condition holds:– For every cluster C ∈ 𝒞k , there exists a set of clusters
𝒟 ⊆ 𝒞k+1 such that ⋃ 𝒟 = C.
• This is why, for two objects x and y, if d0 (Δk (x), Δk (y)) ⩽ 1and d∞ (Δk (x), Δk (y)) ⩽ l for some k, then the same holds
for all k , with k ⩽ k.
• BOOL can be viewed as a divisive hierarchical clustering
algorithm
A-/A-Adjusted Rand Index• Let the result be 𝒞 = {C1 , … , CK } and the correct partition
be 𝒟 = {D1 , … , DM }• Suppose nij ≔ ‖{x ∈ X ∣ x ∈ Ci , x ∈ Dj }‖. Then∑i, j nij C2 − (∑i ‖Ci ‖ C2 ∑h ‖Dj ‖ C2 )/n C22−1 (∑i ‖Ci ‖ C2 + ∑h ‖Dj ‖ C2 ) − (∑i ‖Ci ‖ C2 ∑h ‖Dj ‖ C2 )/n C2A-/A-Shape-Based Clustering Algorithms• Many shape-based algorithms have been proposed– See [Berkhin, ; Halkidi et al., ; Jain et al., ]• Partitional algorithms– ABACUS [Chaoji et al., ], SPARCL [Chaoji et al., ]• Mass-based algorithms [Ting and Wells, ]• Density-based algorithms– DBSCAN [Ester et al., ]• Hierarchical clustering algorithms– CURE [Guha et al., ], CHAMELEON [Karypis et al., ]• Grid-based algorithms– STING [Wang et al., ]A-/A-References[Berkhin, ] P. Berkhin. A survey of clustering data mining techniques.
Grouping Multidimensional Data, pages –, .
[Chaoji et al., ] V. Chaoji, G. Li, H. Yildirim, and M. J. Zaki. ABACUS:
Mining arbitrary shaped clusters from large datasets based on backbone identiﬁcation. In Proceedings of  SIAM International Conference on Data Mining, pages –, .
[Chaoji et al., ] V. Chaoji, M. A. Hasan, S. Salem, and M. J. Zaki. SPARCL:
An eﬀective and eﬃcient algorithm for mining arbitrary shape-basedclusters. Knowledge and Information Systems, ():–, .
[Ester et al., ] M. Ester, H. P. Kriegel, J. Sander, and X. Xu. A densitybased algorithm for discovering clusters in large spatial databaseswith noise. In Proceedings of KDD, , –, .
[Garcia-Molina et al., ] H. Garcia-Molina, J. D. Ullman, and J. Widom.
Database systems: The complete book. Prentice Hall Press, .
[Guha et al., ] S. Guha, R. Rastogi, and K. Shim.
CURE: An eﬃ-A-/A-cient clustering algorithm for large databases. Information Systems,
():–, .
[Halkidi et al., ] M. Halkidi, Y. Batistakis, and M. Vazirgiannis. On clustering validation techniques. Journal of Intelligent Information Systems, ():–, .
[Hinneburg and Keim, ] A. Hinneburg and D. A. Keim. An eﬃcient approach to clustering in large multimedia databases with noise. InProceedings of the Fourth International Conference on Knowledge Discovery and Data Mining, pages –, .
[Jain et al., ] A. K. Jain, M. N. Murty, and P. J. Flynn. Data clustering: Areview. ACM Computing Surveys, ():–, .
[Karypis et al., ] G. Karypis, H. Eui-Hong, and V. Kumar. CHAMELEON:
Hierarchical clustering using dynamic modeling.
Computer,():–, .
[Lin et al., ] J. Lin, E. Keogh, S. Lonardi, and B. Chiu. A symbolic representation of time series, with implications for streaming algorithms.
In Proceedings of the th ACM SIGMOD Workshop on Research Issues in
Data Mining and Knowledge Discovery, pages –, .

A-/A-[Qiu and Joe, ] W. Qiu and H. Joe. Generation of random clusters withspeciﬁed degree of separation. Journal of Classiﬁcation, :–,.
[Sheikholeslami et al., ] G. Sheikholeslami, S. Chatterjee, andA. Zhang. WaveCluster: A multi-resolution clustering approach forvery large spatial databases. In Proceedings of the th International
Conference on Very Large Data Bases, pages –, .
[Ting and Wells, ] K. M. Ting and J. R. Wells. Multi-dimensional massestimation and mass-based clustering. In Proceedings of th IEEE International Conference on Data Mining, pages  – , .
[Wang et al., ] W. Wang, J. Yang, and R. Muntz. STING: A statisticalinformation grid approach to spatial data mining. In Proceedingsof the rd International Conference on Very Large Data Bases, pages
–, .

A-/A-