Similarity Kernel and Clustering via Random Projection Forests

Donghui Yan; Songxiang Gu; Ying Xu; Zhiwei Qin

REVIEW 4 major objections 5 minor 76 references

Similarity Kernel and Clustering via Random Projection Forests

T0 review · 4 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proposes rpf-kernel, a similarity kernel learned by random projection forests, and claims it assigns high similarity to nearby points and low similarity to far-away points, while the associated rpfCluster algorithm competes with…

desk verdict The rpf-kernel is a tree co-occurrence matrix with a plausible empirical record, but the paper's central theorem that far-away points get low similarity is not proven—two real gaps in Theorem 3.1 and Eq. (2). read the letter →

arxiv 1908.10506 v1 pith:IVX5MVH3 submitted 2019-08-28 cs.LG stat.MEstat.ML

Donghui Yan , Songxiang Gu , Ying Xu , Zhiwei Qin This is my paper · ORCID

classification cs.LGstat.MEstat.ML

keywords similaritykernelrandomprojectionforestsunsupervisedlearningclusteringspectralmethodsco-membershipprobabilitytrees

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Random projection forests are ensembles of trees that split data along randomly chosen directions. This paper proposes using them to learn a similarity kernel without labels: grow the forest, record how often each pair of points falls into the same leaf, and average over trees. The paper's central claim is that the resulting rpf-kernel has the desired ordering property—nearby points receive high similarity, far-away points low similarity—and that each kernel entry is interpretable as the probability that the two points stay together through tree growth. Because the kernel is positive semidefinite, it can feed directly into spectral clustering, yielding the rpfCluster algorithm. On 12 benchmark and real datasets, the paper reports that rpfCluster compares favorably with K-means, spectral clustering, and Cluster Forests, which matters because a label-free kernel that adapts to data geometry could replace hand-chosen kernels in clustering and semi-supervised learning.

What carries the argument

The machinery is a random projection forest (rpForest): an ensemble of trees in which every node is split by projecting its points onto a random direction and cutting uniformly at random within the range of projected values. The rpf-kernel is the normalized co-leaf matrix produced by Algorithm 2, so $S_{ij}$ equals the fraction of trees in which points $i$ and $j$ land in the same leaf. The load-bearing geometric identity behind the theory is that, for two points $A,B$ at distance $d$, a randomly oriented split separates them with probability $|AB|\cos\theta / L$, where $L$ is the projected span of the node and $\theta$ is the angle between the projection direction and $AB$; bounding $L$ by the principal stretch $\rho(\Omega)$—the largest possible spread of the node along any direction—gives the lower bound $2d/(\pi\rho)$. The principal stretch and its counterpart, the neck size, are the quantities that control, respectively, the separation of far-away points and the survival of nearby points, and these two opposing bounds are what the paper uses to establish the kernel's ordering property.

What would settle it

Grow many forests on a fixed dataset with two chosen far-apart points, record every split along their paths, and compare the observed fraction of trees that separate them with the claimed lower bound based on the final enclosing node; an observed fraction below the bound would disprove the proof's key step.

Watch

Extended reading notes

Core claim

On the paper's own terms, the rpf-kernel is the empirical co-membership matrix of an ensemble of random projection trees. The paper argues that this matrix is a valid kernel because each tree contributes a block-diagonal matrix with all-ones diagonal blocks, each block positive semidefinite, and averaging preserves positive semidefiniteness. The key theoretical claim is that far-away points are very likely to be separated during growth—the probability of separation at a split is at least $2d/(\pi\rho)$, with $d$ the distance between points and $\rho$ the principal stretch of the data—while nearby points remain unseparated with high probability, using the neck-size bound from the rpForests analysis. Consequently, with enough trees and enough splits, the averaged kernel concentrates below any small threshold for dissimilar points and above a high value for similar points. The paper then assembles rpfCluster by thresholding the kernel, exponentiating it with a bandwidth, and running spectral clustering, and reports favorable comparisons to K-means, spectral clustering, and Cluster Forests on the 12 datasets tested.

Load-bearing premise

The proof that far-away points end up with low similarity rests on assuming that the chance they are separated at the final node on their path in a tree is a lower bound on the chance they are separated somewhere in that tree, even though they may have been separated in an earlier split.

Editorial extensions

If this is right

Because the rpf-kernel is positive semidefinite, it can be used wherever a kernel matrix is needed: spectral clustering, kernel PCA, kernel k-means, or semi-supervised regularization.
The native probabilistic reading of $S_{ij}$ gives practitioners a principled way to set thresholds: similarity values are co-membership chances, not arbitrary affinities.
The forest construction has log-linear cost, so the kernel remains computable for large datasets, and the ensemble structure parallelizes across trees.
If the theoretical property holds, rpfCluster should inherit resistance to the boundary effect: a close pair separated in one tree is likely reunited in another, while truly distant pairs rarely co-occur.
The paper's stated expectation is that the kernel can act as a regularizer in supervised or weakly supervised settings, since it captures latent structure without labels.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Inference: because the rpf-kernel is nothing more than averaged leaf co-membership, it should be usable as an affinity input for other unsupervised tools such as hierarchical clustering, graph-based visualization, or outlier scoring, without additional training.
Inference: the lower-bound gap in the proof suggests a concrete empirical check: track separation times inside each tree; if pairs are often split before reaching a small final node, the proof's Eq. (2) needs a path-survival conditioning rather than a simple final-node bound.
Inference: the sharp contrast between diagonal and off-diagonal blocks on the Iris example suggests the kernel encodes local geometry rather than global distance; a testable extension is to compare rpf-kernel affinity with a learned Mahalanobis kernel on the same clustering tasks.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

First thing you should know: the rpf-kernel is a tree co-occurrence matrix, and the paper's central theorem—far-away points get low similarity—is not proven. The two gaps the stress-test found are real. Theorem 3.1 assumes the angle between the random projection and AB is uniform on [0, π/2], which is only true in R^2; in R^p, E|cosθ| ~ 1/√p, so the constant 2/(πρ(Ω)) is wrong for p>2 and off by a factor of √p on Madelon. And Eq. (2) applies that bound to a 'final node' N_t^(J_t) without handling the case where A and B are separated before that node; if the node is defined only when they are still together, the bound is conditional and does not give the claimed marginal lower bound. So the high-probability low-similarity claim rests on an invalid argument.

What is genuinely new here is using random projection forests rather than coordinate-aligned trees or random-feature k-means ensembles to define a similarity kernel and then applying spectral clustering. That specific construction is not in the cited Cluster Forests or unsupervised RF literature. The PSD proof is correct, and the kernel's interpretation as a co-occurrence probability is true by construction. The empirical section is substantial—12 real datasets, two metrics, comparisons to K-means, NJW, and Cluster Forests—and rpfCluster is competitive, leading on 7 of 12 datasets for clustering accuracy. The method is simple and plausible.

The soft spots beyond the theorem: no error bars or variance estimates, and the tuning of β1 and β2 is not described as label-free; with labeled datasets, this smells like possible label-based parameter selection, which would inflate the results. The gains over Cluster Forests are modest and mixed across metrics. Also, the 'far-away' vs 'nearby' distinction is left informal; the bounds depend on application-dependent constants without a precise statement of when the separation probability becomes high.

Who is this for? Someone working on unsupervised kernel learning or clustering ensembles might find the empirical recipe useful, but the theoretical promise in the abstract overstates what is actually shown. If you send it to peer review, the referees should focus on Theorem 3.1 and Eq. (2); those need fixing, or the claims need to be downgraded to empirical observations. My recommendation: it deserves a serious referee because the empirical work is real and the construction is plausible, but as it stands the paper should not be accepted without major revision.

Referee Report

4 major / 5 minor

Summary. The paper proposes an unsupervised similarity kernel, rpf-kernel, obtained by averaging, over trees in a random projection forest, the indicator that two points fall in the same leaf. The kernel is claimed to have a desirable property: far-away points receive low similarity and nearby points receive high similarity, with similarity interpretable as the co-occurrence probability in tree leaves. The authors prove that the averaged matrix is positive semidefinite, then define rpfCluster by thresholding and exponentiating the kernel and applying spectral clustering. Experiments on 12 labeled real datasets compare rpfCluster with K-means, NJW spectral clustering, and Cluster Forests on clustering accuracy and co-cluster accuracy.

Significance. If the theoretical claim were established, the paper would contribute a simple, data-adaptive, unsupervised kernel with a clear probabilistic interpretation and a competitive clustering algorithm. The PSD argument in Section 2.2 is elementary and correct, and the co-occurrence interpretation follows immediately from Algorithm 2. However, the central theoretical result — that far-away points have low similarity with high probability — rests on Theorem 3.1 and Eq. (2), which contain load-bearing gaps: the angle distribution in Theorem 3.1 is only valid in two dimensions, and Eq. (2) ignores the conditioning implicit in the existence of a final common node. The empirical comparison, while broad, reports no variance and leaves the hyperparameter selection criterion unspecified. The main contribution is therefore not currently supported.

major comments (4)

[Section 3, Theorem 3.1] The proof uses the density 2/π for the angle θ between the random projection direction and AB, which is correct only when the data lie in R^2. For an isotropic random projection direction in R^p, the acute angle has density proportional to sin^{p-2}(θ), so E|cos θ| is roughly c/√p in high dimensions, not 2/π. Consequently the stated lower bound P(A and B separated by a random projection) ≥ 2d/(πρ(Ω)) does not hold for p > 2. Since Eq. (2) and the subsequent claim that µ is close to 1 for far-away points inherit this constant, the far-away low-similarity theorem is not established for the high-dimensional datasets used in Section 5, e.g., Madelon with p=500 in Table 1.
[Section 3, Eq. (2)] The inequality P(A,B separated in tree t) ≥ P(A,B separated when splitting node N_t^(J_t)) is applied as though N_t^(J_t) always contains both A and B. If the two points are separated at an earlier split, no such common final node exists; if N_t^(J_t) is defined only on the event that they remain together, then Theorem 3.1 bounds a conditional probability, and the unconditional probability of the final-node event is not bounded below by 2d/(πρ(N_t^(J_t))). The proof omits the probability of surviving to the final node, so the lower bound in Eq. (2) is not demonstrated. In fact, for sufficiently large J1 the right-hand side of Eq. (2) can exceed 1, which is impossible for a probability and signals that the marginalization is incorrect.
[Section 3, Eqs. (4)-(5)] The argument establishes, for a fixed pair (A,B), that the similarity is below δ with high probability as T grows. The paper then concludes that the rpf-kernel has the property that far-away points have low similarity. No union bound over the O(n^2) pairs in the data is provided, and the per-pair success probability is not quantified. Without such a bound, the global claim about the kernel matrix is not supported.
[Section 5.2.2 and 5.2.3] Figures 4 and 5 report only point estimates for each method, despite rpForests, K-means, and CF being randomized. No error bars, standard deviations, or repeated-run results are given, so the statement that rpfCluster 'outperforms' CF and NJW is not supported at the reported precision. In addition, the selection of β1 and β2 is described only by search ranges; the paper does not state whether the true labels were used to pick these parameters. If labels are used for tuning, the comparison is not an unsupervised clustering comparison, and if they are not, the selection rule should be specified.

minor comments (5)

[Section 2.1, Algorithm 1] The stopping threshold is written as both n_s and ns; please use one consistent symbol and state the stopping rule as 'stop splitting when the node size is less than ns'.
[Section 3, Eq. (3)] The parameters J1, J2, γ1, γ2 are introduced informally; the assumptions about the number of splits and the uniform shrinkage of the principal stretch of child nodes should be stated as precise conditions under which the bounds hold.
[Section 5.2.2] The description of the β2 search ('step size 0.01 within (0,1], 0.1 over (1,200]') should clarify whether the same grid is applied to every dataset and how a single value is selected from the grid.
[Figure 3] The heatmap comparison would be clearer with colorbars and a statement of how the Gaussian-kernel bandwidth was chosen for the left panel.
[References] There are a number of typos and scanned ligature artifacts, e.g., 'eﬀ' and 'ﬂ' in the text and 'knowlwdge' in reference [64]; the manuscript should be proofread before a revised submission.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the rpf-kernel co-occurrence interpretation is definitional, but the paper's theoretical bounds and empirical comparisons do not reduce to fitted inputs or to an unverified self-citation chain.

full rationale

The rpf-kernel is defined in Algorithm 2 as the average, over trees, of co-leaf indicators, so its 'native interpretation as the probability of points remaining in the same leaf nodes' is true by construction. This is a definitional restatement, not a circular derivation: the paper does not use that interpretation to prove the property it is interpreting. The far-away low-similarity claim is attempted through Theorem 3.1 and Eq. (2), which derive a lower bound on separation probability from random projection geometry; that argument is not an input to itself, and it does not depend on any fitted parameter. The nearby high-similarity claim is imported from the authors' prior work [75], but it is a separate published result about separation probabilities in rpForests, not a restatement of the kernel property, so it functions as external support rather than a self-citation loop. The per-dataset choices of beta_1 and beta_2 are tuning parameters in the clustering pipeline; they are not used to force the reported comparisons, and the paper makes no claim of predicting them from first principles. The reviewer's concerns about Theorem 3.1 -- the use of the uniform angle density 2/pi, which is only exactly correct in dimension two, and the conditioning implicit in applying the theorem to a 'final node' that may not contain both points -- are genuine technical weaknesses that may invalidate the far-away bound, but they are proof errors, not circularity. The central derivation is not equivalent to its inputs by construction, no fitted quantity is renamed as a prediction, and no load-bearing argument reduces to an unverified self-citation. Therefore the circularity score is 0.

Assumptions & free parameters 4 free parameters · 4 assumptions · 0 invented entities

The central theoretical argument depends on several assumptions about the data geometry and the rpTree splitting process, some imported from the authors' prior work. The algorithm also has four tuning parameters whose chosen values are not fully specified per dataset.

free parameters (4)

node size threshold n_s = 30 (or 12 for Soybean, 200 for Madelon)
A node is not split if it has fewer than n_s points; chosen per dataset, affects leaf structure and hence the kernel.
number of trees T = chosen from {200, 400, 600}
The authors report that the difference is small, but T is still chosen by hand for the experiments.
threshold beta_1 = chosen from {0, 0.1, 0.2, 0.3, 0.4}
Parameter in Algorithm 3 that zeros out small kernel entries; selection per dataset is not specified and may use reference labels.
bandwidth beta_2 = searched with step 0.01 in (0,1] and 0.1 in (1,200]
Exponential bandwidth in Algorithm 3; tuned per dataset, potentially using reference labels.

assumptions (4)

domain assumption The split direction in each rpTree is chosen uniformly at random over all angles, and the split point is uniform in the projection range of the current node.
Algorithm 1 specifies this; the theory uses the angle distribution in Theorem 3.1.
domain assumption The principal stretch rho and neck size nu of the full data set and the shrink factors gamma1, gamma2 exist with gamma2 < 1.
Used to derive bounds (2) and (3); if gamma2 = 1 or rho = 0, the argument collapses.
domain assumption The probability of splitting nearby points decays as in Eq. (3), taken from the authors' prior paper [75].
Imported rather than proven here; the current paper relies on it to argue high similarity for nearby points.
standard math The binomial distribution of the number of trees separating a pair of points can be approximated by a normal distribution (Eq. 4).
Used to justify high-probability statements for large T.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Similarity Kernel and Clustering via Random Projection Forests." pith.science (2026). https://pith.science/paper/IVX5MVH3

@misc{pith2026190810506,
  author       = {Pith},
  title        = {Pith review of: Similarity Kernel and Clustering via Random Projection Forests},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IVX5MVH3}},
  note         = {Machine review of arXiv:1908.10506}
}

read the original abstract

Similarity plays a fundamental role in many areas, including data mining, machine learning, statistics and various applied domains. Inspired by the success of ensemble methods and the flexibility of trees, we propose to learn a similarity kernel called rpf-kernel through random projection forests (rpForests). Our theoretical analysis reveals a highly desirable property of rpf-kernel: far-away (dissimilar) points have a low similarity value while nearby (similar) points would have a high similarity}, and the similarities have a native interpretation as the probability of points remaining in the same leaf nodes during the growth of rpForests. The learned rpf-kernel leads to an effective clustering algorithm--rpfCluster. On a wide variety of real and benchmark datasets, rpfCluster compares favorably to K-means clustering, spectral clustering and a state-of-the-art clustering ensemble algorithm--Cluster Forests. Our approach is simple to implement and readily adapt to the geometry of the underlying data. Given its desirable theoretical property and competitive empirical performance when applied to clustering, we expect rpf-kernel to be applicable to many problems of an unsupervised nature or as a regularizer in some supervised or weakly supervised settings.

Figures

Figures reproduced from arXiv: 1908.10506 by the authors.

**Figure 2.** Illustration of the geometry involved in the random projection (image courtesy [75]). A and B are the two points of interest. Line CE indicates the direction of random projection. E and F are the projection of points A and B onto line CE. Line CD is parallel to AB, and G is the projection of D onto line CE. The split point will lie anywhere on line CE within the range of of the projections of all points at a tree no… view at source ↗

**Figure 3.** Heatmap of the similarity matrix generated by the Gaussian kernel (left) and by rpForests (right), respectively [PITH_FULL_IMAGE:figures/full_fig_p012_3.png] view at source ↗

Figures from the paper (2 more)

**Figure 4.** Figure 4: Comparison between K-means clustering, spectral clustering (NJW), CF, and rpfCluster for clustering accuracy ρc. On all but two of the 12 datasets, either rpfCluster or CF is leading with rpfCluster having an edge. Under clustering accuracy ρc, rpfCluster is leading o…

**Figure 5.** Figure 5: Comparison between K-means clustering, spectral clustering (NJW), CF, and rpfCluster for co-clustering accuracy ρr. 7 datasets, and ranks the second on 3 datasets while CF leads on 3 and seconds on 5. For co-cluster accuracy ρr, rpfCluster leads on 5 datasets and secon…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

76 extracted references · 74 canonical work pages

[1]

T. W. Anderson. An Introduction to Multivariate Statistical Analysis . John Wiley & Sons, 1958

work page 1958
[2]

Angiulli and C

F. Angiulli and C. Pizzu. Fast outlier detection in high dimensional spaces. Lecture Notes in Computer Science , 2431:43–78, 2002

work page 2002
[3]

Bach and M

F. Bach and M. I. Jordan. Kernel independent component analysis. Journal of Machine Learning Research, 3:1–48, 2003

work page 2003
[4]

Bar-Hillel, T

A. Bar-Hillel, T. Hertz, N. Shental, and D. Weinshall. Learning a Maha- lanobis metric from equivalence constraints. Journal of Machine Learning Research, 6:937–965, 2005

work page 2005
[5]

Belkin, P

M. Belkin, P. Niyogi, and V. Sindhwani. Manifold regularization: A geomet- ric framework for learning from labeled and unlabeled examples. Journal of Machine Learning Research, 7:2399–2434, 2006

work page 2006
[6]

Bellet, A

A. Bellet, A. Habrard, and M. Sebban. A survey on metric learning for feature vectors and structured data. arXiv:1306.6709.v4, 2014

arXiv 2014
[7]

J. Bentley. Multidimensional binary search trees used for associative search- ing. Communications of the ACM , 18(9):509–517, 1975

work page 1975
[8]

Bertoni and G

A. Bertoni and G. Valentini. Ensembles based on random projections to improve the accuracy of clustering algorithms. In Proceedings of the 16th Italian conference on Neural Nets , pages 31–37, 2005

work page 2005

Show all 76 references

[9]

P. J. Bickel and L. Breiman. Sums of functions of nearest neighbor distances, moment bounds, limit theorems and a goodness of ﬁt test. The Annals of Probability, 11(1):185–214, 1983

1983
[10]

P. J. Bickel, G. Kur, and B. Nadler. Projection pursuit in high dimensions. Proceedings of the National Academy of Sciences, U. S. A. , 115(37):9151– 9156, 2018

2018
[11]

P. J. Bickel and D. Yan. Sparsity and the possibility of inference. Sankhya: The Indian Journal of Statistics, Series A (2008-) , 70(1):1–24, 2008

2008
[12]

Boongoen and N

T. Boongoen and N. Iam-On. Cluster ensembles: A survey of approaches with recent extensions and applications. Computer Science Review, 28:1–25, 2018

2018
[13]

L. Breiman. Bagging predicators. Machine Learning, 24(2):123–140, 1996

1996
[14]

L. Breiman. Random Forests. Machine Learning, 45(1):5–32, 2001

2001
[15]

L. Cayton. Algorithms for manifold learning. Technical Report CS2008- 0923, Department of Computer Science, UC San Diego , 2008

2008
[16]

Chandola, A

V. Chandola, A. Banerjee, and V. Kumar. Anomaly detection: A survey. Technical Report, University of Minnesota , 2007. 18

2007
[17]

Chapelle, J

O. Chapelle, J. Weston, and B. Sch¨ olkopf. Cluster kernels for semi- supervised learning. In Advances in Neural Information Processing Systems 15, pages 601–608, 2003

2003
[18]

Chechik, V

G. Chechik, V. Sharma, U. Shalit, and S. Bengio. Large scale online learn- ing of image similarity through ranking. Journal of Machine Learning Re- search, 11:1109–1135, 2010

2010
[19]

Cortes and V

C. Cortes and V. N. Vapnik. Support-vector networks. Machine Learning, 20(3):273–297, 1995

1995
[20]

Dasgupta and Y

S. Dasgupta and Y. Freund. Random projection trees and low dimensional manifolds. In Fortieth ACM Symposium on Theory of Computing (STOC) , 2008

2008
[21]

Dasgupta and K

S. Dasgupta and K. Sinha. Randomized partition trees for nearest neighbor search. Journal Algorithmica, 72(1):237–263, 2015

2015
[22]

Davis, B

J. Davis, B. Kulis, P. Jain, S. Sra, and I. S. Dhillon. Information-theoretic metric learning. In Proceedings of the 24th International Conference on Machine Learning, pages 209–216, 2007

2007
[23]

Dhillon, Y

I. Dhillon, Y. Guan, and B. Kulis. Kernel k-means: spectral clustering and normalized cuts. In Proceedings of the tenth ACM international conference on Knowledge discovery and data mining (SIGKDD) , 2004

2004
[24]

Z. Ding, M. Shao, and Y. Fu. Robust multi-view representation: A uniﬁed perspective from multi-view learning to domain adaption. In Proceedings of 27th International Joint Conference on Artiﬁcial Intelligence , pages 5434– 5440, 2018

2018
[25]

W. Dong, C. Moses, and K. Li. Eﬃcient k-nearest neighbor graph construc- tion for generic similarity measures. In Proceedings of the 20th International Conference on World Wide Web , 2011

2011
[26]

X. Z. Fern and C. E. Brodley. Random projection for high dimensional data clustering: A cluster ensemble approach. In Proceedings of the 20th International Conference on Machine Learning (ICML) , 2003

2003
[27]

Feuerverger, Y

A. Feuerverger, Y. He, and S. Khatri. Statistical signiﬁcance of the netﬂix challenge. Statistical Science, 27(2):202–231, 2012

2012
[28]

R. A. Fisher. The use of multiple measurements in taxonomic problems. Annals of Eugenics , 7(2):179–188, 1936

1936
[29]

Fowlkes, S

C. Fowlkes, S. Belongie, F. Chung, and J. Malik. Spectral grouping using the Nystr¨ om method.IEEE Transactions on Pattern Analysis and Machine Intelligence, 26(2):214–225, 2004

2004
[30]

Freund and R

Y. Freund and R. Schapire. Experiments with a new boosting algorithm. In International Conference on Machine Learning (ICML) , 1996

1996
[31]

Friedman, J

J. Friedman, J. Bentley, and R. Finkel. An algorithm for ﬁnding the best matches in logarithmic expected time. ACM Transactions on Mathematical Software, 3(3):209–226, 1977. 19

1977
[32]

Fukumizu, F

K. Fukumizu, F. Bach, and A. Gretton. Statistical consistency of kernel canonical correlation analysis. Journal of Machine Learning Research, 8:361– 383, 2007

2007
[33]

Gionis, H

A. Gionis, H. Mannila, and P. Tsaparas. Cluster aggregation. In the 21st International Conference on Data Engineering (ICDE) , 2005

2005
[34]

Goldberger, G

J. Goldberger, G. E. Hinton E, S. Roweis, and R. Salakhutdinov. Neigh- bourhood components analysis. In Advances in Neural Information Process- ing Systems 17 , pages 513–520, 2005

2005
[35]

J. A. Hartigan and M. A. Wong. A K-means clustering algorithm. Applied Statistics, 28(1):100–108, 1979

1979
[36]

M. Hirzer. Large scale metric learning from equivalence constraints. In Proceedings of the 2012 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 2288–2295, 2012

2012
[37]

Hofmann, B

T. Hofmann, B. Sch¨ olkopf, and A. Smola. Kernel methods in machine learning. The Annals of Statistics , 36(3):1171–1220, 2008

2008
[38]

X. Huo, X. Ni, and A. Smith. A survey of manifold-based learning methods. Recent Advances in Data Mining of Enterprise Data , pages 691–745, 2007

2007
[39]

Z. Kang, C. Peng, and Q. Cheng. Kernel-driven similarity learning. Neu- rocomputing, 267(C):210–219, 2017

2017
[40]

Kannan, S

R. Kannan, S. Vempala, and A. Vetta. On clusterings: Good, bad and spectral. Journal of the ACM , 51(3):497–515, 2004

2004
[41]

Karatzoglou, A

A. Karatzoglou, A. Smola, and K. Hornik. kernlab: Kernel-based Machine Learning Lab. http://cran.r-project.org/web/packages/kernlab/index.html, 2013

2013
[42]

Kleinbort, O

M. Kleinbort, O. Salzman, and D. Halperin. Eﬃcient high-quality mo- tion planning by fast all-pairs r-nearest-neighbors. In IEEE International Conference on Robotics and Automation (ICRA) , pages 2985–2990, 2015

2015
[43]

B. Kulis. Metric Learning: A Survey. Foundations and Trends in Machine Learning, 5(4):287–364, 2015

2015
[44]

Levina and P

E. Levina and P. J. Bickel. Maximum likelihood estimation of intrinsic dimension. In Advances in Neural Information Processing Systems 17, 2005

2005
[45]

M. Lichman. UC Irvine Machine Learning Repository. http://archive.ics.uci.edu/ml, 2013

2013
[46]

Lim and G

D. Lim and G. Lanckriet. Eﬃcient learning of mahalanobis metrics for ranking. In Proceedings of the 13rd International Conference on Machine Learning (ICML), 2014

2014
[47]

K. Liu, A. Bellet, and F. Sha. Similarity learning for high-dimensional sparse data. In International Conference on Artiﬁcial Intelligence and Statistics (AISTATS), 2015. 20

2015
[48]

T. Liu, A. Moore, A. Gray, and K. Yang. An investigation of practical approximate nearest neighbor algorithms. In Neural Information Processing Systems (NIPS), volume 19, pages 825–832, 2004

2004
[49]

W. Liu, C. Mu, R. Ji, S. Ma, J. R. Smith, and S.-F. Chang. Low-rank similarity metric learning in high dimensions. In Proceedings of the 29-th AAAI Conference on Artiﬁcial Intelligence , pages 2792–2799, 2015

2015
[50]

S. P. Lloyd. Least squares quantization in PCM. IEEE Transactions on Information Theory, 28(1):128–137, 1982

1982
[51]

Y. P. Mack and M. Rosenblatt. Multivariate k-nearest neighbor density estimates. Journal of Multivariate Analysis , 9:1–15, 1979

1979
[52]

Meila, S

M. Meila, S. Shortreed, and L. Xu. Regularized spectral learning. Technical report, Department of Statistics, University of Washington, 2005

2005
[53]

Moutaﬁs, M

P. Moutaﬁs, M. Leng, and I. A. Kakadiaris. An overview and empirical comparison of distance metric learning methods. IEEE Transactions on Cybernetics, 47(3):612–625, 2017

2017
[54]

A. Y. Ng, M. I. Jordan, and Y. Weiss. On spectral clustering: analysis and an algorithm. In Neural Information Processing Systems (NIPS), volume 14, 2002

2002
[55]

C. Otto, D. Wang, and A. K. Jain. Clustering millions of faces by identity. arXiv:1604.00989, 2016

2016 arXiv
[56]

Penrose and J

M. Penrose and J. Yukich. Laws of large numbers and nearest neighbor distances. Advances in Directional and Linear Statistics , pages 189–199, 2010

2010
[57]

Ramaswamy, R

S. Ramaswamy, R. Rastogi, and K. Shim. Eﬃcient algorithms for mining outliers from large data sets. In Proceedings of the ACM SIGMOD , pages 427–438, 2000

2000
[58]

Sch¨ olkopf

B. Sch¨ olkopf. Nonlinear component analysis as a kernel eigenvalue problem. Neural Computation, 10:1299–1319, 1998

1998
[59]

Sch¨ olkopf and A

B. Sch¨ olkopf and A. Smola. Learning with kernels: Support Vector Ma- chines, Regularization, Optimization, and Beyond . MIT Press, 2001

2001
[60]

Schultz and T

M. Schultz and T. Joachims. Learning a distance metric from relative com- parisons. In Advances in Neural Information Processing Systems (NIPS) , 2003

2003
[61]

Shahabi and D

C. Shahabi and D. Yan. Real-time pattern isolation and recognition over immersive sensor data streams. In Proceedings of the 9th International con- ference on multi-media modeling, pages 93–113, 2003

2003
[62]

Shi and J

J. Shi and J. Malik. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence , 22(8):888–905, 2000. 21

2000
[63]

Shi and S

T. Shi and S. Horvath. Unsupervised learning with random forest pre- dictors. Journal of Computational and Graphical Statistics , 15(1):118–138, 2006

2006
[64]

Strehl and J

A. Strehl and J. Ghosh. Cluster ensembles – a knowlwdge reuse framework for combining multiple partitions. Journal of Machine Learning Research , 3:582–617, 2002

2002
[65]

von Luxburg

U. von Luxburg. A tutorial on spectral clustering. Statistics and Comput- ing, pages 395–416, 2007

2007
[66]

B. Wang, A. Mezlini, F. Demir, M. Fiume, Z. Tu, M. Brudno, B. Haibe- Kains, and A. Goldenberg. Similarity network fusion for aggregating data types on a genomic scale. Nature Methods, 11:333–337, 2014

2014
[67]

K. Q. Weinberger and L. K. Saul. Distance metric learning for large mar- gin nearest neighbor classiﬁcation. Journal of Machine Learning Research , 10:207–244, 2009

2009
[68]

E. Xing, A. Y. Ng, M. I. Jordan, and S. Russell. Distance metric learning, with application to clustering with side-information. InProceedings of Neural Information Processing Systems (NIPS) , pages 521–528, 2002

2002
[69]

C. Xu, D. Tao, and C. Xu. A survey on multi-view learning. arXiv:1304.5634, 2013

2013 arXiv
[70]

D. Yan, A. Chen, and M. I. Jordan. Cluster Forests. Computational Statis- tics and Data Analysis , 66:178–192, 2013

2013
[71]

Yan and G

D. Yan and G. E. Davis. The turtleback diagram for conditional probability. The Open Journal of Statistics , 8(4):684–705, 2018

2018
[72]

D. Yan, L. Huang, and M. I. Jordan. Fast approximate spectral clustering. In Proceedings of the 15th ACM SIGKDD , pages 907–916, 2009

2009
[73]

D. Yan, C. Li, N. Cong, L. Yu, and P. Gong. A structured approach to the analysis of remote sensing images. International Journal of Remote Sensing , 40(20):7874–7897, 2019

2019
[74]

D. Yan, T. W. Randolph, J. Zou, and P. Gong. Incorporating deep features in the analysis of tissue microarray images. Statistics and Its Interface , 12(2):283–293, 2019

2019
[75]

D. Yan, Y. Wang, J. Wang, H. Wang, and Z. Li. K-nearest neighbor search by random projection forests. IEEE Transactions on Big Data , PP:1–12, 2019

2019
[76]

Yang and R

L. Yang and R. Jin. Distance metric learning: A comprehensive survey. Michigan State Universiy , 2, 2006. 22

2006

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

T. W. Anderson. An Introduction to Multivariate Statistical Analysis . John Wiley & Sons, 1958

work page 1958

[2] [2]

Angiulli and C

F. Angiulli and C. Pizzu. Fast outlier detection in high dimensional spaces. Lecture Notes in Computer Science , 2431:43–78, 2002

work page 2002

[3] [3]

Bach and M

F. Bach and M. I. Jordan. Kernel independent component analysis. Journal of Machine Learning Research, 3:1–48, 2003

work page 2003

[4] [4]

Bar-Hillel, T

A. Bar-Hillel, T. Hertz, N. Shental, and D. Weinshall. Learning a Maha- lanobis metric from equivalence constraints. Journal of Machine Learning Research, 6:937–965, 2005

work page 2005

[5] [5]

Belkin, P

M. Belkin, P. Niyogi, and V. Sindhwani. Manifold regularization: A geomet- ric framework for learning from labeled and unlabeled examples. Journal of Machine Learning Research, 7:2399–2434, 2006

work page 2006

[6] [6]

Bellet, A

A. Bellet, A. Habrard, and M. Sebban. A survey on metric learning for feature vectors and structured data. arXiv:1306.6709.v4, 2014

arXiv 2014

[7] [7]

J. Bentley. Multidimensional binary search trees used for associative search- ing. Communications of the ACM , 18(9):509–517, 1975

work page 1975

[8] [8]

Bertoni and G

A. Bertoni and G. Valentini. Ensembles based on random projections to improve the accuracy of clustering algorithms. In Proceedings of the 16th Italian conference on Neural Nets , pages 31–37, 2005

work page 2005