Kernelized Locality-Sensitive Hashing for Semi-Supervised Agglomerative Clustering
Authors: Boyi Xie, Shuheng Zheng
ICLR 2013

Abstract: Large scale agglomerative clustering is hindered by computational burdens. We propose a novel scheme where exact inter-instance distance calculation is replaced by the Hamming distance between Kernelized Locality-Sensitive Hashing (KLSH) hashed values. This results in a method that drastically decreases computation time. Additionally, we take advantage of certain labeled data points via distance metric learning to achieve a competitive precision and recall comparing to K-Means but in much less computation time.

arXiv:1301.3575v1  [cs.LG]  16 Jan 2013
Kernelized Locality-Sensitive Hashing for
Semi-Supervised Agglomerative Clustering
Boyi Xie
Department of Computer Science
Columbia University
New York, NY 10027
xie@cs.columbia.edu
Shuheng Zheng
Department of Industrial Engineering & Operations Research
Columbia University
New York, NY 10027
sz2228@columbia.edu
Abstract
Large scale agglomerative clustering is hindered by comput ational burdens. We
propose a novel scheme where exact inter-instance distance calculation is re-
placed by the Hamming distance between Kernelized Locality-Sensitive Hashing
(KLSH) hashed values. This results in a method that drastica lly decreases com-
putation time. Additionally, we take advantage of certain l abeled data points via
distance metric learning to achieve a competitive precisio n and recall comparing
to K-Means but in much less computation time.
1 Introduction
Our proposed research topic is to do clustering on a scalable dataset from a semi-supervised ap-
proach based on hashing methods. In particular, our goal is t o explore the underlying data distribu-
tion by clustering the data points and differentiating the c lasses. When a small set of labeled data
that come from only a subset of the classes is given, we want to ﬁnd out the whole data distribution
for a complete set of classes. For example, we are given a set o f labels of two classes, can we sep-
arate these two classes well and at the same time discover the existence of a third class. It requires
using the information from the labeled data to ﬁnd a transfor mation metric that can split the two
classes well; and after this data transformation, we can dis cover that there is a third class exists.
Suppose there is a handwritten digit recognition task and the dataset contains digits ‘2’, ‘7’ and ‘4’.
If a general agglomerative clustering is run, it might end up with 2 clusters that ‘2’ and ‘7’ in one
cluster and ‘4’ in the other, due to the similarity of their sh apes. However, when a small labeled
set of classes ‘2’ and ‘7’ is given, we can learned a degree of granularity for similarity comparison.
By using a data transformation that maximally can split ‘2’ and ‘7’ into two clusters, we are able to
identify the existence of another cluster, digit ‘4’. Because agglomerative clustering suffers from its
computation inefﬁciency, a major contribution of this paper is to introduce a machine learned hash-
ing method - kernelized locality-sensitive hashing (KLSH) - into agglomerative clustering. This
results in an efﬁcient computation in clustering for large-scale dataset.
Our paper is structured as follows. We provide background st udy and related work in section 2.
Section 3 presents our algorithms for distance metric learn ing and KLSH clustering. Section 4
describes the experiments with a discussion of the results, followed by conclusions in section 5.
1
2 Related Work
There has been much previous work on cluster seeding to addre ss the limitation that iterative clus-
tering techniques (e.g. K-Means and Expectation Maximizat ion (EM)) are sensitive to the choice
of initial starting points (seeds). The problem addressed i s how to select seed points in the absence
of prior knowledge. Kaufman and Rousseeuw [1] propose an elaborate mechanism: the ﬁrst seed is
the instance that is most central in the data; the rest of the r epresentatives are selected by choosing
instances that promise to be closer to more of the remaining i nstances. Pena et al. [2] empirically
compare the four initialization methods for the K-Means alg orithm and illustrate that the random
and Kaufman initializations outperform the other two, since they make K-Means less dependent on
the initial choice of seeds. In K-Means++ [3], the random sta rting points are chosen with speciﬁc
probabilities: that is, a point p is chosen as a seed with probability proportional to p’s contribution
to the overall potential (deﬁned by the sum of squared distances between each point and the closest
center). By augmenting K-Means using this simple, randomiz ed seeding technique, K-Means++ is
θ(log K) competitive with the optimal clustering. Bradley and Fayyad [4] propose reﬁning the initial
seeds by taking into account the modes of the underlying dist ribution. This reﬁned initial seed en-
ables the iterative algorithm to converge to a better local minimum. Semi-supervised learning is also
seen as unsupervised learning guided by constraints. Notic ed that clustering is heavily dependent
on distance metrics and a particular algorithm is an executor to follow the rules, [5] pointed out the
desire to use a systematic way to learn distance metric for cl ustering from labeled data. It is based
on posing metric learning as a convex optimization problem.
When the data size is growing exponentially, hashing is a tec hnique especially good at solving
large scale problems. [6] described Locality-Sensitive Hashing (LSH) method, which is an efﬁcient
algorithm for the approximate and exact nearest neighbor pr oblem. Their goal is to preprocess a
dataset of objects (e.g. images) so that later, given a new qu ery object, one can quickly return the
dataset object that is most similar to the query. The techniq ue is of signiﬁcant interest in a wide
variety of areas of unsupervised learning. Hierarchical cl ustering tries to solve a similar problem,
from another perspective. By iteratively ﬁnding nearest ne ighbors, it groups data into clusters.
Kernelized LSH is later proposed by [7] for fast image search. It generalizes LSH to accommodate
arbitrary kernel functions, making it possible to preserve the algorithm’s sub-linear time similarity
search guarantees for a wide class of useful similarity functions.
3 Methods
In this section, we describe our methods to solve a large scale semi-supervised learning problem by
ﬁrst introducing the distance learning metrics, and then ou r fast agglomerative clustering method
based on kernelized locality-sensitive hashing (KLSH).
3.1 Distance Metric Learning
Under the circumstances that the data given to us has a few lab eled points, and we know which
points for sure belongs to the same or different classes. We h ave a similarity and a dissimilarity
matrix S and D respectively. For entry si,j in similarity matrix S, si,j = 1 if data xi and xj are in
the same class and 0 otherwise. Similarly for dissimilarity matrix D. Based on [5], we try to learn a
distance metric ||x − y||A =
√
(x − y)T A(x − y), where x, y are two data points, A is a positive
semi-deﬁnite matrix of distance parameters among data points. The idea is to minimize the distance
between similar points while keeping dissimilar points apart.
min
∑
(xi,xj )∈S
||xi − xj ||2
A
∑
(xi,xj )∈D
||xi − xj ||A ≥ 1
A ⪰ 0
It can be solved efﬁciently using constrained Newton’s descent on the objective function
2
Algorithm 1 Semi-Supervised Clustering with Hashing
Input: DataLabeled(limited), Data x1, ..., x N .
Step1: Learn distance metric A from labeled (limited) data
Step2: Build A-Distance KLSH table (Algorithm 2).
Step3:
Initialization:
• Let cluster distribution R0 = {{xi}, i = 1 , ..., N }, i.e. each data point is an individual cluster
Ci.
• Let proximity matrix P0 = P (X) of hash keys.
• Set t = 1 .
repeat
• t = t + 1
• Find Ci, Cj such that d(Ci, C j ) = minr,s=1,...,N,r̸=sd(Cr, C s).
• Merge Ci, Cj into a single cluster Cq and form Rt = ( Rt−1 − Ci, C j ) ∪ Cq.
• Deﬁne the proximity matrix Pt from Pt−1 by (a) deleting the two rows and columns that
corresponding to the merged clusters and (b) adding a row and a column of the new cluster.
until (The remaining number of clusters is equal to a speciﬁed k; or the inconsistency coefﬁcient
exceeds a threshold.)
Step4: Retrieve actual data instances from KLSH hash table for the corresponding clusters
Algorithm 2 Build A-Distance KLSH Table
Input: Data xi, ..., x N , distance parameter A.
Step1: Randomly select p points from data, denoted as x1, ..., x i, ..., x p.
Build kernel K(i, j ) = exp(−(d(xi, x j )2/σ 2), for i, j = 1 , ..., p , where d(x, y ) =√
(x − y)′A(x − y).
Step2: Apply SVD to K, suppose K = UΣ UT . K−1/2 = UΣ −1/2UT .
Step3: Form a p-dim vector es, where t dimensions are 1 while others are 0. These t dimensions
are chosen randomly.
Step4: w = K−1/2es. For any x, the bit is created as h(x) = sign(Σ p
i=1wik(x, x i)).
∑
(xi,xj )∈S
||xi − xj ||2
A − log(
∑
(xi,xj )∈D
||xi − xj ||A).
This semi-supervised part is to learn a distance metric for d ata transformation before the main ag-
glomerative clustering.
3.2 Clustering with KLSH
Curse of dimensionality is a well-known problem for learnin g on large scale datasets. It is related
to the fact that the cost of computation grows exponentiallywith the increase of data dimensions, or
the number of data instances. This is a problem directly affe cts clustering approaches that based on
density estimation in input space.
For instance, in K-Means or general agglomerative clustering, the cost in iteratively estimating new
centroid locations and re-arranging data instances to clus ters exerts a signiﬁcant burden on the per-
formance. This happens especially to dataset in high dimens ion, where frequently computing inter-
instance distances are highly expensive.
Our proposed semi-supervised clustering algorithm using k ernelized locality-sensitive hashing
(KLSH) in Algorithm 1 aims to solve the large scale agglomera tive clustering problem. It ﬁrst
learn a distance metric A from a small set of labeled data (step 1 in Algorithm 1). The second step is
to build KLSH table that map the data in to hashed bits. In the r est of the procedure, an agglomera-
tive clustering is performed. Instead of explicitly comput ing inter-instance distances, the clustering
is done based on the KLSH-hashed data points by measuring their Hamming distance. Such kernel-
ized locality-sensitive hashing method has a high probabil ity of preserving neighborhoods so it’s a
reasonable substitute for the exact inter-instance distances.
3
Table 1: Experiment results that compare four methods: (1) K -Means, (2) K-Means with Distance-
metric Learning, (3) Agglomerative clustering using KLSH and (4) Agglomerative clustering using
KLSH with Distance-metric Learning. Precision, recall and computation time is reported. They all
run on data underlying 10 classes and the hash code is 32-bit.
# INST. K-M EANS K-M EANS W / DL AGGL . KLSH AGGL . KLSH W/ DL
PRE REC TIME PRE REC TIME PRE REC TIME PRE REC TIME
5000 .590 .564 13.246 .537 .496 15.647 .573 .305 2.155 .631 .272 2.466
10000 .568 .540 46.398 .580 .556 33.736 .520 .336 7.255 .613 .250 5.246
15000 .574 .530 69.252 .556 .539 186.469 .584 .180 13.843 .610 .156 8.077
20000 .589 .563 79.499 .455 .448 112.178 .609 .355 3.052 .617 .292 18.070
30000 .523 .503 164.853 .552 .541 139.773 .624 .235 58.646 .548 .306 23.136
50000 .560 .531 339.599 .565 .530 333.313 .579 .230 126.280 .590 .252 122.558
4 Experiments
Our experiment is based on the MNIST dataset of handwritten d igits. We evaluate our KLSH ag-
glomerative clustering algorithm via a comparison to K-Means.
4.1 Datasets
We obtained handwritten digits from the MNIST data repository. There are 10 classes of rasterized
images (corresponding to digits from ‘0’ to ‘9’). We used up to 50,000 data points for experiments.
4.2 Experiment Setup
We ran experiments using both K-Means and KLSH agglomerativ e clustering with and without
distance metric learning. Hash string length, the number of classes, and the number of data points
are varied one at a time. We report precision, recall and the c omputation time. All the experiments
were done on a machine with 8-core Intel processors of 2.8 GHz and 8 GB of RAM.
4.3 Results and Analysis
Tables 1-3 summarize our results, and the followings are several trends to notice.
First in Table 1, we observed that KLSH agglomerative cluste ring can achieve the same level of
precision for a fraction of the computational cost. The down side is that recall is caused by the
factor of 2. The decrease in recall is caused by the fact that K LSH cannot recover all of the points
in the nearest neighborhood. The addition of distance metri c learning has noticeable beneﬁts on
performance for KLSH Agglomerative Clustering.
In Table 2, we analyzed the effect of an increase in the number of classes (while ﬁxing the number
of data points) on precision, recall, and computation time. Precision remains constant while recall
decreases. The computational costs remains relatively independent of the number of clusters.
In Table 3, we analyzed the effect of hash string length on clustering validity. Increasing the length
of hash string increases both the precision and recall.
It is also able to adjust the tradeoff between efﬁciency and effectiveness. Notice that even if we use
m = 32 bit binary hash code, there are still232 possible outcomes. If the hashing split data well, the
number of entries of the table will still be very large. It inc reases the accuracy of clustering results
but meanwhile leads to a higher computation cost during agglomerative clustering.
According to the results, clustering with KLSH has superior performance when the dataset is large
and the number of real clusters is small. Comparing to K-Mean s, it has large promising improve-
ment on speed. When true cluster number is not large, it achie ves high performance on both speed
and accuracy. Especially in a lower level of the linkage tree , clustering with bias (distance metric
learning) can immediately correctly cluster similar data instances.
4
Table 2: Compare the performance of various number of underlying classes for agglomerative clus-
tering using KLSH with distance metric learning. In this case, data size is 20,000 and the hash code
is 32-bit. With an increase in the number of classes, the prec ision remains constant while recall
decreases
# CLASSES PRE REC TIME
4 .714 .465 16.527
5 .629 .355 19.226
6 .702 .507 18.747
7 .611 .317 21.675
8 .654 .354 21.540
9 .603 .284 24.024
10 .617 .292 18.070
Table 3: Compare the performance of various number of hash code bits for agglomerative clustering
using KLSH with distance metric learning. In this case, data size is 20,000 with underlying 10
classes. Increasing the length of hash string increases both the precision and recall.
# BITS PRE REC TIME
8 .402 .245 0.043
16 .599 .111 1.000
32 .617 .292 18.070
64 .635 .380 92.452
5 Conclusions
General hierarchical clustering methods cannot scale well on large dataset due to the exponentially
growing number of calculations on inter-instance distance s. Kernelized locality-sensitive hashing
(KLSH) provides a high probability of preserving neighborhoods and it’s a reasonable substitute for
the exact inter-instance distances. Our proposed KLSH agglomerative clustering alleviates the prob-
lem by calculating a reduced-sized Hamming distance and achieves efﬁcient clustering computation.
The incorporation of distance metric learning marginally improves the precision and recall.
References
[1] L. Kaufman and P. J. Rousseeuw. Finding Groups in Data: An Introduction to Cluster Analysis.
John Wiley, 1990.
[2] Jos´ e Manuel Pe˜ na, Jos´ e Antonio Lozano, and Pedro Larra˜ naga. An empirical comparison of four
initialization methods for the k-means algorithm. Pattern Recognition Letters, 20(10):1027–
1040, 1999.
[3] David Arthur and Sergei Vassilvitskii. k-means++: the a dvantages of careful seeding. In Pro-
ceedings of the eighteenth annual ACM-SIAM symposium on Dis crete algorithms, SODA ’07,
pages 1027–1035, Philadelphia, PA, USA, 2007.
[4] Jude W. Shavlik, editor. Reﬁning Initial Points for K-Means Clustering . Morgan Kaufmann,
1998.
[5] Eric P. Xing, Andrew Y . Ng, Michael I. Jordan, and Stuart R ussell. Distance metric learning,
with application to clustering with side-information. In Advances in Neural Information Pro-
cessing Systems 15, pages 505–512. MIT Press, 2002.
[6] Alexandr Andoni and Piotr Indyk. Near-optimal hashing a lgorithms for approximate nearest
neighbor in high dimensions. Commun. ACM, 51(1):117–122, January 2008.
[7] Brian Kulis and Kristen Grauman. Kernelized locality-s ensitive hashing for scalable image
search. In IEEE International Conference on Computer Vision (ICCV), 2009.
5


Peer review:
[Review]:
This paper proposes to use kernelized locality-sensitive hashing (KLSH), based on a similarity metric learned from labeled data, to accelerate agglomerative (hierarchical) clustering. Agglomerative clustering requires, at each iteration, to find the pair of closest clusters. The idea behind this paper is that KLSH can be used to accelerate the search for these pairs of clusters. Also, the use of a learned, supervised metric should encourage the extraction of a clustering that reflects the class structure of the data distribution, even if computed from a relatively small subset of labeled data. Comparisons with k-means, k-means with distance learning, agglomerative clustering with KLSH and agglomerative clustering with KLSH and distance learning are reported.

Unfortunately, I find this paper to be quite incremental. It essentially corresponds to a straightforward combination of 3 ideas 1) agglomerative clustering, 2) kernelized LSH [7] and 3) supervised metric learning [5].

I find that details about the approach are also missing, about how to combine KLSH with agglomerative clustering. First, the authors do not explain how KLSH is leveraged to find the pair of closest clusters C_i and C_j. Are they iterating over each cluster C_i, finding its closest neighbour C_j using KLSH? This would correspond to a complexity linear in the number of clusters, and thus initially linear in the number of data points N. In a large scale setting, isn't this still too expensive? Are the authors doing something more clever? Algorithm 1 also mentions a proximity matrix P. Isn't its size N^2 initially? Again, in a large scale setting, it would be impossible to store such a matrix. The authors also do not specify how to compute distances between two clusters consisting in more than a single data point. I believe this is sometimes referred to as the linkage distance or criteria between clusters, which can be the min distance over all pairs or max distance over all pairs. What did the authors use, and how does KLSH allow for an efficient computation?

Moreover, I'm not convinced of the benefit of the algorithm, based on the experiments reported in table 1. Indeed, agglomerative clustering with KLSH and distance learning does not dominate all other algorithm for both the precision and recall. In fact, it's doing terribly in terms of recall, compared to k-means. Also, it is not exactly clear to me what precision and recall correspond to in the context of this clustering experiment. I would suggest the author explicitly define what they mean here. I'm more familiar with adjusted rand index, as an evaluation metric for clustering...

Finally, the writing of the paper is quite poor. I already mentioned that many details are lacking. Moreover, the paper is filled with typos and oddly phrased sentences.