Dimensionality’s Blessing: Clustering Images by Underlying Distribution
Wen-Yan Lin
Advanced Digital Sciences Center

Siying Liu
Institute of Infocomm Research

linwenyan.daniel@gmail.com

szewinglau@gmail.com

Jian-Huang Lai
Sun Yat-Sen University

Yasuyuki Matsushita
Osaka University

stsljh@mail.sysu.edu.cn

yasumat@ist.osaka-u.ac.jp

Abstract
Many high dimensional vector distances tend to a constant. This is typically considered a negative “contrastloss” phenomenon that hinders clustering and other machine learning techniques. We reinterpret “contrast-loss”
as a blessing. Re-deriving “contrast-loss” using the lawof large numbers, we show it results in a distribution’s instances concentrating on a thin “hyper-shell”. The hollow center means apparently chaotically overlapping distributions are actually intrinsically separable. We use thisto develop distribution-clustering, an elegant algorithm forgrouping of data points by their (unknown) underlying distribution. Distribution-clustering, creates notably clean
clusters from raw unlabeled data, estimates the numberof clusters for itself and is inherently robust to “outliers”
which form their own clusters. This enables trawling forpatterns in unorganized data and may be the key to enablingmachine intelligence.

Distribution-clusters from a subset of Flickr11k [43]1. Introduction
Who is thy neighbor? The question is universal and old
as the Bible. In computer vision, images are typically converted into a high-dimensional vector known as image descriptors. Neigborness of images is defined as distances
between their respective descriptors. This approach has
had mixed success. Descriptors excel at nearest-neighbors
retrieval applications. However, descriptor distances are
rarely effective in other neighbor based machine learning
tasks like clustering.
Conventional wisdom suggests poor clustering performance is due to two intrinsic factors. a) Images are theproduct of a complex interplay of geometric, illuminationand occlusion factors. These are seldom constant, causing even images of the same location to vary significantly
from each other. The extreme variability makes clustering

Affinity matrix before and after clustering
Figure 1: Distribution-clustering on a set of random images.
Our technique captures even highly variable distributions
like flowers and scenery. The post-clustering affinity matrix
displays distinctive blocky patterns predicted by our theory.

difficult. This can be understood mathematically as each
image being an instance of some distribution. The variability causes image data-sets to be chaotic. Here, chaotic isdefined as having distributions whose mean separation is15784

significantly smaller than their standard deviation. Clustering chaotic data is ill-posed because data points of different distributions mingle. This can be alleviated by enhancing invariance with higher dimensional image descriptors.
However, it leads to a second problem. b) As dimensions
increase, “contrast-loss” [3, 10, 17] occurs. Distances between points tend to a constant, with traditional clustering
metrics becoming ill-defined [3, 5]. This is considered partof the curse of dimensionality [17, 1].
We offer a different perspective in which “contrast-loss”
is not a problem but the solution to clustering chaotic data.
The core idea is simple. What was previously interpreted as“contrast-loss” is actually the law of large numbers causing
instances of a distribution to concentrate on a thin “hypershell”. The hollow shells mean data points from apparently
overlapping distributions do not actually mingle, making
choatic data intrinsically separable. We encapsulate thisconstraint into a second order cost that treats the rows of
an affinity matrix as identifiers for instances of the same
distribution. We term this distribution-clustering.
Distribution-clustering is fundamentally different fromtraditional clustering as it can disambiguate chaotic data,
self-determine the number of clusters and is intrinsically robust to “outliers” that form their own clusters. This mindbending result provides an elegant solution to a problem
previously deemed intractable. Thus, we feel it fair to conclude that “contrast-loss” is a blessing rather than a curse.

1.1. Related Works
To date, there are a wide variety of clustering algorithms [32, 26, 19, 15, 21, 38] customized to various tasks.
A comprehensive survey is provided in [9, 42]. Despite thevariety, we believe distribution-clustering is the first to utilize the peculiarities of high dimensional space. The resultin a fundamentally different clustering algorithm.
This work is also part of on-going research in the properties of high dimensional space. Pioneering research beganwith Beyer et al.’s [10] discovery of “contrast-loss”. Thiswas interpreted as an intrinsic hindrance to clustering andmachine learning [3, 10, 17], motivating the development of
sub-space clustering [35, 18], projective-clustering [2, 27],and other techniques [44, 28, 20] for alleviating “contrastloss”. This simplistic view has begun to change, with recent
papers observing that “contrast-loss” can be beneficial in
detecting outliers [37, 47], cluster centroids [40] and scoring clusters [40]. These results indicate a gap in our knowledge but a high-level synthesis is still lacking.
While we do not agree with Aggarwal et al.’s [3] interpretation of “contrast-loss”, we are inspired by their attempts to develop a general intuition about the behavior ofalgorithms in high-dimensional space. This motivates us toanalyze the problem from both intuitive and mathematicalperspectives. We hope it contributes to the general under-

standing of high dimensional space.
Within the larger context of artificial intelligence research, our work can be considered research on similarity
functions surveyed by Cha [13]. Unlike most other similarity functions, ours is statistical in nature, relying on extreme
improbability of events to achieve separability. Such statistical similarity has been used both explicitly [11] and implicitly [30, 14, 36, 46, 39] in matching and retrieval. Manyof these problems may be reformulatable in terms of the lawof large numbers, “contrast-loss” and high-dimensional features. This is a fascinating and as yet unaddressed question.
Finally, distribution-clustering builds on decades of research on image descriptors [33, 25, 6] and normalization [24, 7]. These works reduce variation, making the lawof large numbers more impactful at lower dimensions. As
distribution-clustering is based on the law of large numbers,
its performance is correspondingly enhanced.

2. Visualizing High Dimensions
Our intuition about space was formed in two and three
dimensions and is often misleading in high dimensions. In
fact, it can be argued that the “contrast-loss” curse ultimately derives from misleading visualization. This section
aims to correct that.
At low dimensions, our intuition is that solids with similar parameters have significant volumetric overlap. This is
not true in high dimensions.
Consider two high dimensional hyper-spheres which are
identical except for a small difference in radius. Their volume ratio is

r − ∆r
r

k

=



∆r
1−
r

k

→ 0,

k→∞

(1)

which tends to zero as the number of dimensions, k → ∞.
This implies almost all of a sphere’s volume is concentrated
at its surface. Thus, small changes in either radius or centroid cause apparently overlapping spheres to have near zerointersecting volume as illustrated in Fig. 2, i.e., they become volumetrically separable! A more rigorous proof canbe found in [23].
Intriguingly, instances of a distribution behave similarly
to a hyper-sphere’s volume. Section 3.3 shows that when
distributions have many independent dimensions, their instances concentrate on thin “hyper-shells”. Thus, instancesof apparently overlapping distributions almost never mingle. This makes clustering chaotic data by distribution awell-posed problem, as illustrated in Fig. 3.

3. Distribution-Clustering (theory)
Images are often represented as high dimensional feature vectors, such as the 4096-dimensional NetVLAD [6]5785

Geometric overlap�
TE(Z1 ), E(Z2 ), . . . , E(Zk )• E(Z) =is avector of each dimension’s expectation;

Volumetric overlap• With a slight abuse of notation, we define Var(Z) =Pk var(Zi ), as the average variance over all dimeni=1
ksions.

� − ∆�

(a) Small change in radius

3.1. Passive Sensing Model(b) Small change in centroid

Many data sources (like cameras) can be modeled as passive sensors. Data points (like image descriptors) {x(i) : i ∈Sn }, are instances of random vectors {X(i) : i ∈ Sn } representing environmental factors that influence sensory outcome, e.g., camera position, time of day, weather conditions. As sensing does not influence the environment, allrandom vectors are mutually independent. Our goal is tocluster x(i) instances by their underlying X(i) distributions.

Majority ofoverlap
volumeFigure 2: Almost all of a high dimensional sphere’s volume
is near its surface. Thus, small changes of radius or centroid result in almost no volumetric overlap. The apparently
overlapping spheres are volumetrically separable!

Figure 3: Left: Traditional view of chaotic data as overlapping spheres. Clustering such data is deemed an ill-posed
problem. Right: Our visualization. Each distribution’s instances form hollow rings. Thus, clustering data by fitting“hyper-shells” becomes a well-posed problem.
descriptor. This section shows how we can create indicators
to group images based on their generative distributions.
Definition 1.
• D(m, σ 2 ) denotes a probability distribution with meanm and variance σ 2 ;• Sn = { 1, 2, . . . , n } denotes a set of consecutive
positive integers from 1 to n;• d(.) denotes a normalized squared ℓ2 norm operator,
2i.e., for x ∈ Rk , d(x) = kxkk .
TLet Z = Z1 , Z2 , . . . , Zk
denote a k dimensional random vector where Zi is a random variable,• d(.) operator can also be applied on a random vec2
tors Z. d(Z) = kZk
is a random variable formed bykaveraging Z’s squared elements.

3.2. Quasi-ideal Features
An ideal feature descriptor has statistically independent
dimensions. However, this is hard to ensure in practice.
A more practical assumption is the quasi-independence incondition 1.
Condition 1. Quasi-independent: A set of k random variables {X (i) : i ∈ Sk } are quasi-independent, if and only if,
as k → ∞, each random variable has finite number of pairwise dependencies. That is, let A be the set of all pairwise
dependent variables and 1 be an indicator function, there
exists t ∈ Z+ such thatkX

1A ({X (i) , X (j) }) ≤ t,∀i ∈ Sk .

j=1

Quasi-independence is approximately equivalent to requiring information increases proportionally with number ofrandom variables. When the random variables are concatenated into a feature, we term it quasi-ideal.
Condition 2. Quasi-ideal: A k-dimensional random vector
X is quasi-ideal, if and only if, as k → ∞, the varianceof all its elements are finite and the set of all its elements,{Xi : i ∈ Sk }, is quasi-independent.
Treating the links of an infinitely long Markov chain asfeature dimensions would create a quasi-ideal feature. Thisis useful in computer vision, as pixel values have Markov
like properties of some statistical dependence on neighbors
but long range statistical independence. Hence, many image
based descriptors can be modeled as quasi-ideal.
Practicality aside, quasi-ideal features have useful mathematical properties, as they permit the law of large numbers
to apply to distance metrics. This leads to interesting resultssummarized in Lemmas 1 and 2.
5786

Lemma 1. Let X be a quasi-ideal random vector with dimension k → ∞. The normalized squared ℓ2 norm of any
instance is almost surely a constant:
Pk

X2
kXk2
d(X) == i=1 i ∼ D m, σ 2 , σ → 0, (2)kkProof. As X is quasi-ideal, the set of squared elements{X12 , X22 , . . . , Xk2 } form a covariance matrix where the sumof elements in any row is bounded by some positive real
number t, i.e.,kX

cov(Xi2 , Xj2 ) ≤ t,∀i ∈ Sk .

(3)

j=1

3.3. Distribution-clusters
Identifying data points from “similar” distributions requires a definition of “similarity”. Ideally, we would follow
Lemma 2’s intuition and define “similarity” as having thesame mean and average variance. However, the definitionneeds to accommodate dimensions tending to infinity. This
leads to a distribution-cluster based “similarity” definition.
Let ΩX = {X(i) : i ∈ Sn } be a set of independent kdimensional random vectors. k → ∞ such that the random
vectors satisfy quasi-ideal conditions.

This implies
Var(d(X)) =

Pk

i=1

Pk

2
2
j=1 cov(Xi , Xj )

k2

<

kt
t
< .
k2
k

(4)

Lemma 2. Let X and Y be statistically independent, quasiideal random vectors. As the dimensions k → ∞.
kX − Yk2∼ D m, σ 2 , σ → 0,
(5)d(X − Y) =kwhere m = Var(X) + Var(Y) + d(E(X) − E(Y)).
Proof. As X and Y are quasi-ideal, random vector X − Y
is also quasi-ideal. Using Lemma 1, we know d(X − Y)’s
variance tends to zero. The expression for its mean is:kX − Yk2kk
X E Xi2E Yi2
2E (Xi Yi )
=
+
−
k
k
k
i=1
=



k
X
var (Xi ) + var (Yi )
i=1

+

k

k
X
E (Xi )2 − 2E (Xi ) E (Yi ) + E (Yi )2
i=1=Var(X) + Var(Y) +kkX(E (Xi ) − E (Yi ))2
i=1

forms

a

• The normalized squared ℓ2 norm distance between any
two distribution mean is zero, i.e.,d(E(X(i) ) − E(X(j) )) = 0,

Thus, as k → ∞, variance tends to zero.

m =E

ΩX

Condition 3. Distribution-cluster:
distribution-cluster if and only if:∀i, j ∈ Sn ;(6)

• All distributions have the same average variance, i.e.,
Var(X(i) ) = Var(X(j) ),∀i, j ∈ Sn .

(7)

As dimensions tend to infinity, instances of a
distribution-cluster concentrate on a “thin-shell”. This isproved in theorem 1 and validates Fig. 3’s intuition. The“hollow-center” means data points from apparently overlapping distributions almost never mingle, creating the potential for clustering chaotic data.
Theorem 1. If ΩX is a distribution-cluster with averagevariance v, the normalized squared distance of its instancesfrom the cluster centroid will almost surely be v, i.e., ΩX ’s
instances form a thin annulus about it’s centroid.
Proof. Without loss of generality, let m = E(X(1) ). Let
X in Lemma 2 be X(i) and Y in Lemma 2 be a distribution
with mean m and variance 0. This gives an expression:
p d(X(i) − m) = v → 1 ∀i ∈ Sn
(8)k=Var(X) + Var(Y) + d(E(X) − E(Y)).

Lemma 2 is similar in spirit to Beyer et al.’s [10]“contrast-loss” proof. However, it accommodates realizations from different distributions, introduces a more practical quasi-independence assumption and is simpler to derive.
Unlike [3], we consider “contrast-loss” an opportunity
not a liability. Lemma 2 proves that distance between instances almost always depend only on the mean and variances of the underlying distributions and not on instances’values. This makes distance between instances a potential
proxy for identifying their underlying distributions.

3.4. Grouping Data by Distribution
We seek to group a set of data points by their underlying
distribution-clusters. This is achieved by proving that data
points of a distribution-cluster share unique identifiers that
we term cluster-indicators.
Theorem 2. Cluster-indicator: Let Y be a quasi-ideal random vector that is independent of all ΩX ’s random vectors.
ΩX forms a distribution-cluster (c.f condition 3), if andonly if, for any valid random vector Y, there exists a real
number bY such thatp(d(Y − X(i) ) = bY ) → 1,5787

∀i ∈ Sn .

(9)• A solution is unique. This follows from Theorem 2’s
only if condition which means cluster-indicators almost never confuse data points of different distributions. This can also be understood as proving intrinsic separability of instances from different distributionclusters;

Proof. First, the if part is proved. Given ΩX is a
distribution-cluster, Eq. (9) is a direct result of Lemma 2,
where the distance between instances of quasi-ideal distributions are almost surely determined by the distributions’mean and average variances.
Moving on to the only if proof, where it is given that
ΩX satisfies Eq. (9)’s cluster-indicator. W.l.o.g, we consider
only elements X(1) , X(2) . Let Y be independent but identically distributed with X(1) .
From Lemma 2, we know that

• The solution’s behavior changes continuously with theinitial conditions. The bY cluster-indicator in Eq. (9)vary continuously with the mean and average varianceof the underlying distribution-cluster. This follows
from Lemma 2’s expression for bY .

• p(d(Y − X(1) ) = m1 ) → 1, wherem1 = 2Var(X(1) );4. Distribution-Clustering (practical)• p(d(Y − X(2) ) = m2 ) → 1, wherem2 = Var(X(1) )+Var(X(2) )+d(E(X(1) )−E(X(2) )).
Equation (9) means bY = m1 = m2 , implying:
2Var(X(1) )=Var(X(1) ) + Var(X(2) ) + d(E(X(1) ) − E(X(2) )).

(10)

Similarly, treating Y as independent but identically distributed with X(2) implies
2Var(X=Var(X

(2)

(1)

)

) + Var(X(2) ) + d(E(X(1) ) − E(X(2) )).

(11)

Solving (10) and (11) yields
Var(X

(1)

) = Var(X

(2)

),

d(E(X

(1)

) − E(X(2))) = 0.

This proves that X(1) , X(2) are members of a distributioncluster, (c.f condition 3). Repeating the process with all element pairs of ΩX will show they belong to one distributioncluster. This completes the only if proof.
As argued in Sec. 3.1, image descriptors can be modeled
as instances of independent, quasi-ideal random vectors,i.e., a set of image descriptors Ωx = {x(i) : i ∈ Sn } canbe considered instances of the respective random vectors
in ΩX . Theorem 2 implies that descriptors from the same
distribution-cluster will (almost surely) be equi-distance toany other descriptor. Further, it is a unique property of descriptors from the same distribution-cluster. This allows
descriptors to be unambiguously assigned to distributionclusters. In summary, distribution-clustering of images (andother passive sensing data) is a well-posed problem, per thedefinition in McGraw-Hill dictionary of scientific and technical terms [34]:• A solution exist. This follows from Theorem 2’s if
condition where cluster-indicators almost surely (inpractice it can be understood as surely) identify all data
points of a distribution-cluster;Our goal is to use theorem 2’s cluster-indicators to groupdata points by their underlying distributions. From theorem 2, we know that if x(i) , x(j) are instances of the same
distribution-cluster, the affinity matrix’s i, j rows/ columns
will be near identical. To exploit this, we define second order features as columns of the affinity matrix. Clustering isachieved by grouping second-order features.

4.1. Second-order Affinity
Let Ωx = {x(i) : i ∈ Sn } be a set of realizations, withan associated affinity matrix An×n :A(i, j) = d(x(i) − x(j) ).

(12)

The columns of A are denoted as a(i) = A(:, i). Treating columns as features yields a set of second-order features{a(i) : i ∈ Sn }. The elements of a(i) encodes the distance
between vector x(i) and all others in Ωx .
From theorem 2, we know that if and only if the distributions underlying a(i) , a(j) come from the same distributioncluster, all their elements, except the ith and j th entries, arealmost surely identical. This is encapsulated as a secondorder distance:
2
X  (i)(j)d′ (a(i) , a(j) ) =.
(13)
ak − akk∈Sn \{i,j}which should be zero if i, j belong to the same distributioncluster. The presence of clusters of identical rows causes thepost-clustering affinity matrix to display a distinctive blocky
pattern shown in Fig. 1.
Second order distance can be embedded in existing clustering algorithms. For techniques like spectralclustering [45] which require an affinity matrix, a secondorder affinity matrix is defined as A′n×n :A′ (i, j) = d′ a(i) , a(j) .

If n is large, d′ a(i) , a(j) ≈ ka(i) − a(j) k2 . This allows
second order {a(i) } features to be used directly in clustering
algorithms like k-means, which require feature inputs.
5788

Input: Affinity matrix An×n
Output: Vector of cluster labels L
Initialization: 1) Set of un-assigned image indices:
Sn = {1, 2, . . . , n}; 2) Set of non-diagonal elementsof A: E = {A(i, j)}, i 6= j; 3) Initialize L = 0n×1 ;4) Set label counter c = 1;
while Sn 6= ∅ do
Find i and j corresponding to min(E);Create candidate cluster H = {i, j};for s ∈ SnPdo
1′ (s)if |H|, a(h) ) < τ , thenh∈H d (ainsert s into H
end
end
if |H| < m thendelete A(i, j) from E ;else
accept cluster H and assign its elements a
unique label;
L(h) = c, ∀h ∈ H;
c := c + 1;
for h ∈ H dodelete A(:, h) and A(h, :) from set E;
delete h from set Sn .
end
end
end
Algorithm 1: Distribution-clustering

Incorporating second-order constraints into a prior clustering algorithm does not fully utilize theorem 2. This isbecause realizations of the same distribution-cluster havezero second-order-distance, while most clustering algorithms only apply a distance penalty. This motivates an alternative solution we term distribution-clustering

4.2. Implementing Distribution-clustering
Distribution-clustering can be understood as identifying
indices whose mutual second-order distance is near zero.
These are grouped into one cluster and the process repeatedto identify more clusters.
An algorithmic overview is as follows. Let i, j be the indices of its smallest off-diagonal entry of affinity matrix A.
If {x(i) , x(j) } are instances of a distribution-cluster, Lemma
2 states the average cluster variance is A(i, j)/2. Thus
they are the data-set’s lowest average variance distributioncluster. Initialize {x(i) , x(j) } as a candidate distributioncluster. New members are recruited by finding vectors
whose average second-order distance from all distributioncluster candidates is less than threshold τ . If a candidate
distribution-cluster grows to have no less than m members,
accept it. Irrespective of the outcome, remove {x(i) , x(j) }from consideration as candidate clusters. Repeat on unclustered data till all data points are clustered or it is impossible to form a candidate cluster. Some data may not
be accepted in any cluster and remain outliers. Details arein Algorithm 1. For whitened descriptors [24, 7], typicalparameters are τ = 0.07, m = 5.
Relative to other clustering techniques, distributionclustering has many theoretical and practical advantages:• Clustering chaotic data is a well-posed problem (c.f .
Sec. 3.4);• No pre-definition of cluster numbers is required;• Innate robustness to “outliers” which form their own
clusters.

5. Clustering
Simulation Results use quasi-ideal features created froma mixture of uniform and Gaussian distributions. To evaluate the effect of increasing dimensionality, the number ofdimensions is increased from 1 to 4000. Two sets are evaluated. The “Easy” set has wide separation of underlying
distributions while the “Difficult” set has little separation.
Results are presented in Fig. 4. We compare three different distance measures on k-means clustering [31, 8]: ℓ2
norm, ℓ1 norm and our proposed second-order distance in
Eq. (13). We also compare spectral clustering [45] with ℓ2and second-order distance. Finally, we provide a system
to system comparison between our distribution-clustering,k-means and spectral-clustering. At low dimensions, thesecond-order distance gives results comparable to other algorithms. However, performance steadily improves withnumber of dimensions. Notably, only algorithms which employ second-order distance are effective on the “Difficult”
set. This validates the theoretical prediction that (the previously ill-posed problem of) clustering chaotic data is madewell-posed by the second-order distance.
To study the effect of mean separation on clustering performance, we repeat the previous experiment under similar
conditions, except the number of dimensions are kept constant and the mean separation progressively reduced to zero.
Results are presented in Fig. 5. Note that second-order distance ensures clustering performance is relatively invariant
to mean separation.
Real Images with NetVLAD [6] as image descriptors areused to evaluate clustering on 5 data-sets: Handwritten
numbers in Mnist [29]; A mixture of images from Google
searches for “Osaka castle”’ and “Christ the redeemer
statue”; 2 sets of 10 object types from CalTech 101 [22];And a mixture of ImageNet [16] images from the Lion,
Cat, Tiger classes. Distribution-clustering is evaluatedagainst five baseline techniques: K-means [31, 8], spectral5789

40
20

20
0
0

1000

0
0

2000 3000 4000

60

1000

Spectral ClusteringOurs
k-means

40

Spectral Clustering
Spectral (given # clus.)
Our Spectral Clustering

202000 3000 4000

0
0

60

80

Spectral Clustering
Spectral (given # clus.)
Our Spectral Clustering

40

40

20

20

0
0

1000

2000 3000 4000

0
0

200

1000

2000 3000 4000

Easy
Figure 4: Simulation with increasing number of dimensions. Left: k-means with ℓ2 norm, k-means with ℓ1
norm and our second-order distance. Center: Spectral clustering with automatic detection of cluster numbers [45], given number of clusters [45] and second-orderdistance (Eq. (13)). Right: System to system comparisonof distribution-clustering, k-means and spectral clustering.
Only high dimensional, second-order distance algorithms
are effective on “Difficult” data.
k-means80
L1 k-means
Our k-means 60

40

40

40

20

20

20

0
0

0
0

0
0

5

10

400

600

800

0

1000

0

100

200

300

400

Internet Images

0.8
0.6
0.4
0.2
0
0

50

100

150

200

0.8
0.6
0.4
0.2
0
0

200

400

600

Num. images processed (ranked output)

CalTech101 (Set1)

CalTech101 (Set2)

Percentage Error

Num. images processed (ranked output)

0.8

K-means
Ours
Spectral
PROCLUSGMM
Quick Shift

0.6
0.4
0.2
500

1000

Num. images processed (ranked output)

Spectral ClusteringOurs
k-means

Spectral Clustering
Spectral (given # clus.) 80
Our Spectral Clustering

60

0.05

Minst

0
0
80

0.1

Num. images processed (ranked output)

Spectral ClusteringOurs
k-means

60

201000 2000 3000 4000

0.2
0
0

40

0
0

0.4

0.2
0.15

Num. images processed (ranked output)

Percentage Error

80

k-means
L1 k-means
Our k-means

60

0.6

1000 2000 3000 4000

Difficult80

Percentage Error

60

k-means
L1 k-means
Our k-means

40

80

Percentage Error

60

Percentage Error

0.8

80

80

Cats

60

5

10

5

10

% Mis-classified vs. Separation of distribution centers
Figure 5: Simulation with increasing separation of distribution centers. Algorithms are the same as in Fig. 4. Only
second-order distance algorithms are performance invariant
with separation of distribution centers.

clustering [45], projective-clustering [4], GMM [12] andquick-shift [41]. For k-means and GMM, the number ofclusters is derived from distribution-clustering. This is typically 20 − 200. Spectral and projective-clustering are prohibitively slow with many clusters. Thus, their cluster numbers are fixed at 20.
Cluster statistics are reported in Tab. 1. On standard silhouette and purity scores, distribution-clustering’s performance is comparable to benchmark techniques. The performance is decent for a new approach and validates Theorem
2’s “contrast-loss” constraint in the real-world. However,an interesting trend hides in the average statistics.
Breaking down the purity score to find the percentage
of images deriving from pure clusters, i.e., clusters with nowrong elements, we find that distribution-clustering assigns
a remarkable fraction of images to pure clusters. On average, it is 1.5 times better than the next best algorithm andFigure 6: Clustering real images. Clusters are ranked byvariance. Unlike prior methods where “outliers” are randomly scattered in clusters, distribution-clustering concentrates “outliers” in high variance clusters, making identification of pure clusters easy.

in some cases can nearly double the performance. This isimportant to data-abstraction where pure clusters allow asingle average-feature to represent a set of features. In addition, distribution-clustering ensures pure clusters are readily identifiable. Figure 6 plots percentage error as clusters
are processed in order of variance. Distribution-clustering
keeps “outliers” packed into high-variance clusters, leaving low-variance clusters especially pure. This enables concepts like image “over-segmentation” to be transferred tounorganized image sets.
K-means and GMM are the closest alternative to
distribution-clustering. However, their clusters are less pureand they are dependent on distribution-clustering to initialize the number of clusters. This makes distributionclustering one of the few (only?) methods effective onhighly chaotic image data like Flickr11k [43] demonstrated
in Fig. 1.
Timing excludes feature extraction cost which is common to all algorithms. Experiments are on an i7 machine,
5790

Dataset
MNISTInternet
CalTech1
CalTech2
Cats
Average
DatasetMNISTInternet
CalTech1
CalTech2
Cats
Average
DatasetMNISTInternet
CalTech1
CalTech2
Cats
Average
DatasetMNISTInternet
CalTech1
CalTech2
Cats
Average

Silhouette Score
PROCLUS
GMM
QS
Ours
[4]
[12]
[41]
-0.0349
0.0076
0.07300.038-0.0380.09630.04880.003-0.00450.03730.09990.074-0.0186
0.02480.03500.042-0.0020.02360.07520.0239-0.0200.03790.0532
0.036
Purity Score
K-Means Spectral PROCLUS
GMM
QS
Ours
0.77
0.45
0.41
0.81
0.55
0.79
0.96
0.90
0.86
0.97
0.82
0.97
0.71
0.44
0.36
0.80
0.31
0.82
0.84
0.83
0.41
0.88
0.29
0.87
0.88
0.63
0.50
0.90
0.35
0.93
0.83
0.65
0.51
0.87
0.46
0.88
% of images in pure clusters (excluding singletons)
K-Means Spectral PROCLUS
GMM
QS
Ours
0.28
0
0
0.32
0.059
0.49
0.83
0.82
0.40
0.83
0.031
0.92
0.08
0.02
0.01
0.30
0.081
0.52
0.47
0.24
0
0.52
0.16
0.65
0.34
0
0
0.40
0.017
0.72
0.40
0.22
0.082
0.47
0.070
0.66
% of pure clusters (excluding singletons)
K-Means Spectral PROCLUS
GMM
QS
Ours
0.43
0
0
0.44
0.62
0.49
0.80
0.90
0.8
0.83
0.40
0.93
0.30
0.20
0.09
0.46
0.75
0.52
0.54
0.20
0
0.57
0.67
0.67
0.57
0
0
0.55
0.50
0.74
0.53
0.32
0.178
0.57
0.59
0.67
K-Means[31, 8]0.0082
0.084
0.027
0.028
0.007
0.0308Spectral[45]
0.0267
0.041
0.02
0.084
0
0.034

Table 1: Cluster Statistics. Distribution-clustering ensuresa large percentage of images belong to pure clusters.

Distribution-clustering

K-means clustering

Figure 7: Distribution-clustering provides fine intra-cluster
consistency, with images of a cluster sharing a clear, generative distribution. This qualitative improvement is not captured in evaluation statistics.

6. Conclusion
with 4096 dimension NetVlad [6] features computed overthe 400 images of Internet data-set. Our single core, Matlab implementation of distribution-clustering takes 23 seconds, of which 4.5 seconds was spent computing the affinity matrix. Timing for other algorithms are as follows. Kmeans [31, 8]: 0.73 seconds, Quick Shift [41] (Python): 1.5
seconds, spectral clustering [45] (20 clusters): 2 seconds,
GMM1 [12]: 4 minutes and PROCLUS [4] (20 clusters on
OpenSubspace V3.31): 9 minutes.

We have shown that chaotically overlapping distributions
become intrinsically separable in high dimensional spaceand proposed a distribution-clustering algorithm to achieve
it. By turning a former curse of dimensionality into a blessing, distribution-clustering is a powerful technique for discovering patterns and trends in raw data. This can impact
a wide range of disciplines ranging from semi-supervised
learning to bio-informatics.

Acknowledgment
Qualitative inspection of distribution-clusters show they
have a purity not captured by quantitative evaluation. Figure 7 illustrates this on Colosseum images crawled fromthe web. Quantitatively, both distribution-clustering and kmeans are nearly equal, with few clusters mixing Colosseum and “outlier” images. However, distribution-clusters
are qualitatively better, with images in a cluster sharing aclear, generative distribution.
Other things readers may want to note. More qualitativeevaluation of clustering is available in the supplementary.
Code is available at http://www.kind-of-works.com/.
1 GMM’s timing is with covariance estimation. Fixed covariance matrix
permits convergence in seconds but is inappropriate on some data.

This paper is dedicated to Professor Douglas L. Jones,
Professor Minh N. Do and Hong-Wei Ng.
Y. Matsushita is supported by JST CREST Grant Number JP17942373, Japan.

References[1] https://en.wikipedia.org/wiki/Curse_of_
dimensionality. Accessed: 2017-11-10. 2[2] P. K. Agarwal and N. H. Mustafa. K-means projective clustering. In Proceedings of ACM SIGMOD-SIGACT-SIGART
symposium on Principles of Database Systems, pages 155–
165, 2004. 2[3] C. C. Aggarwal, A. Hinneburg, and D. A. Keim. On thesurprising behavior of distance metrics in high dimensional
spaces. In Proceedings of International Conference on

5791

Database Theory (ICDT), volume 1, pages 420–434, 2001.
2, 4[4] C. C. Aggarwal, J. L. Wolf, P. S. Yu, C. Procopiuc, and J. S.
Park. Fast algorithms for projected clustering. In Proceedings of the ACM SIGMOD International Conference on Management of Data, number 2, pages 61–72, 1999. 7, 8
[5] C. C. Aggarwal and P. S. Yu. Outlier detection for high dimensional data. In Proceedings of the ACM SIGMOD International Conference on Management of Data, number 2,
pages 37–46, 2001. 2[6] R. Arandjelovic, P. Gronat, A. Torii, T. Pajdla, and J. Sivic.
Netvlad: CNN architecture for weakly supervised place
recognition. In Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 5297–
5307, 2016. 2, 6, 8
[7] R. Arandjelović and A. Zisserman. Three things everyone
should know to improve object retrieval. In Proceedings ofIEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 2911–2918, 2012. 2, 6
[8] D. Arthur and S. Vassilvitskii. k-means++: The advantagesof careful seeding. In Proceedings of the eighteenth annual
ACM-SIAM symposium on Discrete algorithms, pages 1027–
1035, 2007. 6, 8
[9] P. Berkhin et al. A survey of clustering data mining techniques. Grouping Multidimensional Data, 25:71, 2006. 2[10] K. Beyer, J. Goldstein, R. Ramakrishnan, and U. Shaft.
When is nearest neighbor meaningful? In Proceedings of International Conference on Database Theory (ICDT), pages
217–235, 1999. 2, 4
[11] J. Bian, W.-Y. Lin, Y. Matsushita, S.-K. Yeung, T.-D.
Nguyen, and M.-M. Cheng. Gms: Grid-based motion statistics for fast, ultra-robust feature correspondence. In Proceedings of IEEE Conference on Computer Vision and Pattern
Recognition (CVPR), pages 2828–2837, 2017. 2[12] C. Bishop. Pattern recognition and machine learning.
Springer, 2007. 7, 8
[13] S.-H. Cha. Comprehensive survey on distance/similarity
measures between probability density functions. International Journal of Mathematical Models and Methods in Applied Sciences, 1(300–307):1, 2007. 2[14] A. Delvinioti, H. Jégou, L. Amsaleg, and M. E. Houle. Image retrieval with reciprocal and shared nearest neighbors.
In Proceedings of International Conference on Computer Vision Theory and Applications (VISAPP), volume 2, pages
321–328, 2014. 2[15] A. P. Dempster, N. M. Laird, and D. B. Rubin. Maximum
likelihood from incomplete data via the em algorithm. Journal of the royal statistical society. Series B (methodological),pages 1–38, 1977. 2[16] J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. FeiFei. Imagenet: A large-scale hierarchical image database.
In Proceedings of IEEE Conference on Computer Vision and
Pattern Recognition (CVPR), pages 248–255, 2009. 6[17] P. Domingos. A few useful things to know about machinelearning. Communications of the ACM, 55(10):78–87, 2012.
2[18] E. Elhamifar and R. Vidal. Sparse subspace clustering: Algorithm, theory, and applications. IEEE Transactions on Pattern Analysis and Machine Intelligence, 35(11):2765–2781,
2013. 2[19] M. Ester, H.-P. Kriegel, J. Sander, X. Xu, et al. A densitybased algorithm for discovering clusters in large spatial
databases with noise. In Proceedings of ACM SIGKDD
Conference on Knowledge Discovery and Data Mining, volume 96, pages 226–231, 1996. 2[20] D. Francois, V. Wertz, and M. Verleysen. The concentrationof fractional distances. IEEE Transactions on Knowledge
and Data Engineering, 19(7):873–886, 2007. 2[21] M. X. Goemans and D. P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM(JACM), 42(6):1115–1145, 1995. 2[22] G. Griffin, A. Holub, and P. Perona. Caltech-256 object category dataset. 2007. 6[23] J. Hopcroft and R. Kannan. Foundations of data science.
2014. 2[24] H. Jégou and O. Chum. Negative evidences and cooccurences in image retrieval: The benefit of pca and whitening. Proceedings of European Conference on Computer Vision (ECCV), pages 774–787, 2012. 2, 6
[25] H. Jégou, M. Douze, C. Schmid, and P. Pérez. Aggregating
local descriptors into a compact image representation. In
Proceedings of IEEE Conference on Computer Vision and
Pattern Recognition (CVPR), pages 3304–3311, 2010. 2[26] T. Kanungo, D. M. Mount, N. S. Netanyahu, C. D. Piatko,
R. Silverman, and A. Y. Wu. An efficient k-means clustering
algorithm: Analysis and implementation. IEEE Transactions
on Pattern Analysis and Machine Intelligence, 24(7):881–
892, 2002. 2[27] H.-P. Kriegel, P. Kröger, and A. Zimek. Clustering highdimensional data: A survey on subspace clustering, patternbased clustering, and correlation clustering. ACM Transactions on Knowledge Discovery from Data (TKDD), 3(1):1,
2009. 2[28] H.-P. Kriegel, A. Zimek, et al. Angle-based outlier detection in high-dimensional data. In Proceedings of ACM
SIGKDD Conference on Knowledge Discovery and Data
Mining, pages 444–452, 2008. 2[29] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner. Gradientbased learning applied to document recognition. Proceedings of the IEEE, 86(11):2278–2324, 1998. 6[30] W.-Y. Lin, S. Liu, N. Jiang, M. N. Do, P. Tan, and J. Lu. Repmatch: Robust feature matching and pose for reconstructing
modern cities. In Proceedings of European Conference on
Computer Vision (ECCV), pages 562–579, 2016. 2[31] S. P. Lloyd. Least squares quantization in pcm. IEEE Transactions on Information Theory, 28:129–137, 1982. 6, 8
[32] A. Y. Ng, M. I. Jordan, and Y. Weiss. On spectral clustering:
Analysis and an algorithm. In Proceedings of Advances in
Neural Information Processing Systems (NIPS), pages 849–
856, 2002. 2[33] A. Oliva and A. Torralba. Modeling the shape of the scene: A
holistic representation of the spatial envelope. International
Journal of Computer Vision, 42(3):145–175, 2001. 2

5792

[34] S. P. Parker. McGraw-Hill dictionary of scientific and technical terms. McGraw-Hill, 1984. 5[35] L. Parsons, E. Haque, and H. Liu. Subspace clustering forhigh dimensional data: a review. ACM SIGKDD Explorations Newsletter, 6(1):90–105, 2004. 2[36] D. Qin, S. Gammeter, L. Bossard, T. Quack, andL. Van Gool. Hello neighbor: Accurate object retrieval
with k-reciprocal nearest neighbors. In Proceedings of IEEE
Conference on Computer Vision and Pattern Recognition(CVPR), pages 777–784, 2011. 2[37] M. Radovanović, A. Nanopoulos, and M. Ivanović. Reverse
nearest neighbors in unsupervised distance-based outlier detection. IEEE transactions on Knowledge and Data Engineering, 27(5):1369–1382, 2015. 2[38] J. Shi and J. Malik. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and MachineIntelligence, 22(8):888–905, 2000. 2[39] M. Shi, Y. Avrithis, and H. Jégou. Early burst detection formemory-efficient image retrieval. In Proceedings of IEEE
Conference on Computer Vision and Pattern Recognition(CVPR), pages 605–613, 2015. 2[40] N. Tomasev, M. Radovanovic, D. Mladenic, andM. Ivanovic. The role of hubness in clustering highdimensional data. IEEE Transactions on Knowledge andData Engineering, 26(3):739–751, 2014. 2[41] A. Vedaldi and S. Soatto. Quick shift and kernel methods
for mode seeking. Proceedings of European Conference on
Computer Vision (ECCV), 2008. 7, 8[42] D. Xu and Y. Tian. A comprehensive survey of clustering
algorithms. Annals of Data Science, 2(2):165–193, 2015. 2[43] Y. H. Yang, P. T. Wu, C. W. Lee, K. H. Lin, W. H. Hsu, and
H. H. Chen. Contextseer: context search and recommendation at query time for shared consumer photos. In Proceedings of ACM international conference on Multimedia, pages
199–208, 2008. 1, 7
[44] D. Yu, X. Yu, and A. Wu. Making the nearest neighbor meaningful for time series classification. In Proceedings of International Congress on Image and Signal Processing, pages
2481–2485, 2011. 2[45] L. Zelnik-Manor and P. Perona. Self-tuning spectral clustering. In Proceedings of Advances in Neural Information
Processing Systems (NIPS), pages 1601–1608, 2005. 5, 6, 7,
8[46] S. Zhang, M. Yang, T. Cour, K. Yu, and D. N. Metaxas.
Query specific fusion for image retrieval. In Proceedingsof European Conference on Computer Vision (ECCV), pages
660–673. 2012. 2[47] A. Zimek, E. Schubert, and H.-P. Kriegel. A survey on unsupervised outlier detection in high-dimensional numerical
data. Statistical Analysis and Data Mining: The ASA Data
Science Journal, 5(5):363–387, 2012. 2

5793