Title: X-Forest: Approximate Random Projection Trees for Similarity Measurement

Abstract: Similarity measurement plays a central role in various data mining and machine learning tasks. Generally, a similarity measurement solution should, in an ideal state, possess the following three properties: high accuracy, high efficiency in terms of speed and independence from prior knowledge. Yet unfortunately, vital as similarity measurements are, no previous works have addressed all of them. In this paper, we propose X-Forest, consisting of a group of approximate Random Projection Trees, such that all three targets mentioned above are tackled simultaneously. Our key techniques are as follows. First, we introduced RP Trees into similarity measurement such that accuracy is improved. In addition, we enforce certain layers in each tree to share identical projection vectors, such that exalted speed is achieved. Last but not least, we introduce randomness into partition to eliminate its reliance on prior knowledge. We conduct experiments on three real-world datasets, whose results demonstrate that our model, X-Forest, reaches an efficiency of up to 3.5 times higher than RP Trees with negligible compromise on its accuracy, while also being able to outperform traditional Euclidean distance-based similarity metrics by as much as 20% with respect to clustering tasks.

1. Introduction:



1.1. Background and motivation:

Similarity measurement is to measure the similarity between every pair of items in a given dataset. Generally, an item can be represented by a data point in the space (e.g., Euclidean space). The target of similarity measurement is to generate a similarity matrix M whose element M ij represents the similarity value between two data points: i and j.

Similarity measurement plays a central role in data mining and machine learning, and also has practical applications in other fields such as biochemistry, biology, botany, etc. In data mining, similarity is a vital criterion in unsupervised clustering which is to classify objects into groups and eliminate inappropriate data Santos et al. (2013) ; Kushawah & Yadav (2016) ; Jarvis & Patrick (1973) . The result of clustering can be applied in various specific fields, e.g., the accurate segmentation of liver lesions Jha et al. (2010) , the characterization of chemical structures and biological activity spectra Fliri et al. (2005) , or for ligand identification Koch et al. (2004) . In machine learning, similarity can be used in social filtering algorithms to make predictions for recommendation systems Billsus & Pazzani (1998) .

Therefore, these extensive applications require the similarity measurement solution to maintain high accuracy in different datasets Ma & Manjunath (1996) , and this is the first design goal of this paper. The second design goal is to achieve efficient similarity measurement.

1.2. Prior art and their limitations:

For similarity measurement, existing works can be divided into two kinds: mathematical distance-based similarity and multi-partition based similarity. Currently the prevailing approaches belong to the first kind of solutions, such as Minkowski distance family, Fidelity or Squared-chord family, Shannon's entropy Cha (2007) , Cosine similarity Irani et al. (2016) , etc. These similarity measurement solutions only depend on the pairwise information (i.e., partial information), but neglect the overall information, such as the dimensions, features, distribution of the dataset. Consequently, they have low versatility, i.e., lacking the flexibility to adapt to different datasets. Furthermore, they are not accurate enough, because they may not preserve the perceptual similarity (intuitive similarity) of the dataset, especially when encountered with high dimension datasets Ma & Manjunath (1996) ; Dasgupta & Freund (2008) .

The second kind of solutions such as Multiple RP+EM Fern & Brodley (2003) and RF similarity Gray et al. (2013) overcome the shortcomings of the first kind by projecting and partitioning the data. Unfortunately, this kind of solutions often depends on priori knowledge about data distribution or data labels, which can hardly be acquired in common circumstances. Consequently, The third design goal of this paper is to eliminate the dependence on priori knowledge. No existing works can achieve all the design goals at the same time.

1.3. Our contributions:

This paper aims to achieve the above three design goals at the same time. Towards the first and third goal, we introduce the Random Projection Tree (RP Tree) to similarity measurement. RP Tree is used to randomly partition a set of data points in a space into several disjoint subsets. It is well known that in an RP Tree, data points that are closely distributed, indicating their high level of similarity in space, are always partitioned into the same subset Dasgupta & Freund (2008) . This means that RP Tree can achieve the first goalhigh accuracy. As RP Tree uses random partitions, thus achieves the third goal -eliminating priori knowledge dependence.

Unfortunately, directly using RP Tree cannot achieve the second goal -high efficiency, because during each partition, we need to project all data points into a random vector which is time consuming (see details in Section 2). To address this problem, we propose the X-Forest.

The key idea is to allow nodes at i, i + X, i + 2X... (i=0,1,2...) layers of the tree to share the same projection vector for partitioning. For example, let us assume that we are given a complete binary RP Tree with 4 layers. The root node denotes the entire dataset and each node denotes a subset of the entire dataset. For each inner node, the standard RP Tree needs to project all data points into one random vector. In this way, it projects each data point four times. Our solution is to let the nodes at the first and third layers share the same projection vector, and do so for the second and fourth layers. For the nodes at the third layer, we reuse the projection results of the first layer, and do so for the four layer. In this way, we project each data point twice instead of four times.

Obviously, sharing vectors sacrifices the randomness of projection vectors, further degrading the accuracy. Fortunately, the accuracy loss can be almost eliminated by using a great many Trees and carefully choosing the sharing parameter -X (see details in Section 3.2).

We propose β-Similarity to record the results in X-Forest into a similarity matrix. It features better representing the similarity relationship between data points, which is proved by the higher accuracy in our clustering experiments.

Our key contributions are as follows:

• We introduce RP Trees into similarity measurement and proposed a new similarity matrix β-Similarity, which better reveals the similarity relationships between data points than traditional distance based similarity measurement. • We propose X-Forest which significantly reduces the time of building procedure of RP Trees by sharing projection vectors. • We conduct extensive experiments on three real datasets, and our experimental results

show that RP Trees achieves two design goals, while X-Forest achieves all three desigan goals at the same time.

We have released codes in github anonymously so as to meet the demand of reproducibility sou.

The mathematical proofs of our algorithm is detailed in supplementary materials.

2 Background and Related Work

2.1. Similarity Measurement:

Existing solutions for similarity measurement can be classified into two categories: 1) mathematical distance based similarity and 2) multi-partition based similarity. The first kind is Mathematical distance based similarity which is widely used. It includes Minkowski distance family, Fidelity or Squared-chord and Shannon's entropy Cha (2007) , Cosine similarity Irani et al. (2016) , the correlation coefficient Billsus & Pazzani (1998) , travel time, and edit distance Chen et al. (2009) , etc. According to the applying method of distance, it can be divided into two cases: 1) distance is directly applied as similarity; 2) distance is first computed as a criterion for further similarity evaluation. An example of the second case is shared neighbours based clustering Jarvis & Patrick (1973) . The k nearest neighbours of each data point are found using Euclidean distance. The similarity between data point i and j is defined as the number of common neighbours.

Existing works of the second kind, multi-partition based similarity, is rare, and an example is Multiple RP+EM Fern & Brodley (2003) . In each operation of RP+EM, the dimension of the original dataset is degraded through a linear transformation. Then, it applies EM clustering to generate a probabilistic model θ of a mixture of k Gaussians. The similarity between data points i and j is defined as the average value of

P θ ij = k l=1 P (l | i, θ)×P (l | j, θ) of each RP+EM.

The first kind of solutions falls short in terms of leading to unsatisfied results, especially in high-dimensional spaces. And the second kind depends on prior knowledge about data labels or data distribution.

2.2. Random Projection Tree:

Sanjoy Dasgupta and Yoav Freund first propose the idea of RP Tree Dasgupta & Freund (2008) . An RP Tree is a variant of k -d tree Bentley (1975) . The most popular application of RP Tree is in nearest neighbours finding, where it compensates k -d tree's diminishing efficacy in high-dimensional spaces Dasgupta & Sinha (2015) . Other applications of RP Tree cover clustering Yan et al. (2009) , pattern discovering Minnen et al. (2007) and nearest neighbours finding, vector quantization Dasgupta & Freund (2009) , local symmetry detection in natural images Shen et al. (2016) , etc.

The details of building an RP Tree are as follows. In an RP Tree, the root node includes all items in a given set S. Through RP operation, RP Tree partitions S into two disjoint sets, each of which is a child node of the root node. The child node will be recursively partitioned until its size is smaller than a predefined threshold τ . In the end, each leaf node of an RP Tree forms a set of size less than τ . Figure 2 shows the structure of an RP Tree. The main operation of RP Tree, the RP operation, generates a random unit direction vector e for each partition. After all data points have been projected into the random direction, we uniformly choose a partition point at random within the projection range, where the projection range refers to the interval between the smallest and the largest projection value.

The formal description of an RP operation is as follows. RP Tree computes the projection value of each point in the set S into the unit directional vector e. Let P be the set of projection values, i.e., P = {x • e | x ∈ S}. Let P max be the maximum value in P and P min be the minimum value in P. The partition point P τ is uniformly and randomly selected from 0 5 0 1 0 0 1 5 0 0 . 0 0 . 4 0 . 8 S i m i l a r i t y (a) Basic Similarity. 0 5 0 1 0 0 1 5 0 0 . 0 0 . 4 0 . 8 S i m i l a r i t y (b) β-Similarity (β = 0.9) number 1-50) and the entire  dataset (number 1-50, number 51-100, number 101-150). (P min , P max ). P τ partitions the set S into two disjoint subsets S L = {x • e P τ | x ∈ S} and S R = {x • e > P τ | x ∈ S}. This is equivalent to partitioning the space into two parts with a (d -1)-dimensional hyperplane x T • e = P τ . When d = 2, as shown in Figure 1 , the (d -1)-dimensional hyperplane degrades to a line. Building an RP Tree suffers from high computation complexity since, a large number of RP operations are involved whenever an RP Tree is built, worsened by the fact that, it requires another large number of inner products to complete a single RP operation.

3. The X-Forest Algorithm:

As detailed in Section 2.2, RP Tree cluster similarly data points into the same node. In this section, we first show how to use a number of RP Trees to generate the similarity matrix. Then we introduce X-Forest, which significantly accelerate the building procedure of these trees.

3.1. Similarity Matrix Generation:

In an RP Tree, two data points are regarded as similar if they are in the same leaf node. Therefore, given a number of trees that are built independently, we can consider the probability that two data points fall into the same leaf node as their similarity. Based on this idea, the well known similarity matrix is defined as follows.

Definition 1 Given m RP Trees T 1 , ..., T m , for RP Tree T i , suppose a data point x j belongs to the leaf node L i (x j ) . The basic similarity matrix M basic is defined as

EQUATION

, where I is the indicator function.

The basic similarity matrix is the average of some 01 matrix, and each 01 matrix is a similarity matrix generated by one RP Tree. In a 01 matrix, the similarity between data points falling into the same leaf node is 1 and the similarity between data points falling into different leaf nodes is 0.

This definition does not consider the information of the structure of the RP Tree. This leads to the 01 matrix is too sparse, i.e., has a large number of 0s. To show that, consider the following example. Given n data points to build an RP Tree with each leaf nodes containing r data points, this RP Tree has n r leaf nodes and each leaf node fills the similarity matrix with r 2 1s. Therefore, the size of this 01 matrix generated by this RP Tree is n 2 , but only nr elements are 1, accounting for r n of all elements (e.g. n = 150, r = 3, 1 accounted for only 0.02). The issue is that the similarity of data points in different leaf nodes should be a number between 0 and 1 rather than 0. Thus we can get a matrix better representing the similarity between data points, by reasonably eliminating some 0s. To achieve this, we need to consider information about the whole structure of an RP Tree. If the distance between two data points in an RP Tree is short (i.e., they are divided later), we should define their similarity as a value closer to 1. If the distance between two data points in an RP Tree is long (i.e., they are divided earlier), we should define their similarity as a value closer to 0. Based on this observation, we propose the β-Similarity matrix. A tree uses only two random directions. One (red) for odd layers and the other (yellow) for even layers.

Definition 2 Given an RP Tree T i , let DIS i (X, Y) be the distance between nodes X and Y in T i . The β-Similarity matrix M β is defined as

M β jk = 1 m m i=1 β DISi(Li(xj ),Li(x k )) (2)

Here β is a parameter controlling the speed at which the similarity decays with increasing distance. When β → 0, the β-Similarity matrix degenerates into the basic similarity matrix. We use the most popular Iris flower dataset Dua & Graff (2017) to compare the basic similarity and β-Similarity and the result is shown in Figure 3 . For basic similarity, most data points in the same class (number 1-50) have rather low similarity. For β-Similarity, the similarity between data points in the same class is significantly greater than that of the data points in different classes. In our experiments, we find that the accuracy of clustering can be significantly improved by properly choosing β (Figure 8 ).

3.2. X-Projection Tree and X-Forest:

Generating a similarity matrix requires a large number of different RP Trees. However, the process of building such a large number of RP Trees is rather slow. To address this issue, we propose X-Forest. The key idea is to allow nodes at i, i + X, i + 2X, ...(i = 1, 2, ...) layers of the tree to share the same direction vector.

In order to introduce the X-Forest, we first introduce an equivalent RP Tree called Layer-by-Layer RP Tree. Compared to the standard RP Tree, Layer-by-Layer RP Tree allows nodes in each layer share the same projection direction. An example of a Layer-by-Layer RP Tree is shown in Figure 4 . Theoretically, the Layer-by-Layer RP Tree is equivalent to the standard RP tree. Here we give a brief explanation: For a standard RP Tree, the partition of each node on the tree relies on a series of independent projection directions. Intuitively, a random partition of the dataset demands each data point to go through a series of mutually independent partitions. Thus, in an RP Tree, the nodes which are ancestor-descendant related (ADR) need mutually independent projection directions, and the nodes which are not ADR can share the same projection directions. Specifically, it is sufficient that the projection directions used by different layers are mutually independent. This shows the equivalence between the standard RP Tree and Layer-by-Layer RP Tree.

To further explore other avenues to economize computation time, X-Forest allows different layers share the same projection directions. Sharing projection directions sacrifices the randomness of partition, further affecting the similarity generated. To implement the tradeoff between speed and accuracy, we give a method by adjusting the sharing parameter X.

Here we describe the details about building an X-Forest, which is a group of X-Projection Trees. Given a dataset S, for each X-Projection Tree, we select X independent random projection directions e 0 , e 1 , • • • , e X-1 , and compute the projection value of all data points into the X projection directions, i.e. P i = {x • e i | x ∈ S}. When building an X-Projection

Tree, we rely on the following idea to allow data sharing of the projection directions: the root node uses the first projection direction e 0 for partitioning. The node in the i-th layer uses the (i mod X)-th projection direction e (i mod X) , and uses the pre-calculated projection value in P (i mod X) to partition the set. The rest of the recursive tree construction is identical to standard RP Tree. Figure 5 shows an example of using X = 2 version of X-Projection Tree to partition data points.

The X-Projection Tree is equivalent to a Layer-by-Layer RP Tree when its depth is no greater than X. When X = 1, it is equivalent to using a series of parallel (d -1)-dimension hyperplanes to partition the space. This is the most efficient case because only one RP operation is required. According to our experimental analysis, we find out that: 1) the X = 2 version of X-Forest achieves the best trade-off between improvement in computational efficiency and loss in partition precision. 2) the X = 4 version of X-Forest almost achieves the accuracy of Layer-by-Layer RP Trees, while requiring little additional time compared to the X = 2 version. Further experimental details are discussed in Section 5.

Here we provide an analysis of the computational complexity of X-Forest. 

(m • n • (n + X • d))

. Therefore, X-Forest is especially suitable for datasets satisfying d n/ log n.

In term of implementation, X-Forest can calculate P i in parallel for all projection directions. For the standard RP Tree, parallel acceleration cannot be used because information about which set of data points is to be projected into each direction remains uncertain.

4. Applications of X-Forest:

In this section, we demonstrate how to apply the similarity matrix to some classical clustering algorithms, including Kernel K-means, density clustering, and spectral clustering.

Kernel K-means: K-means Hartigan & Wong (1979) is the most popular unsupervised clustering algorithm. It partitions all data points into K clusters by finding K optimal cluster centers. The optimization goal is to minimize the sum of the distances of each data point to its nearest cluster center. The Kernel K-means is an optimization of K-means clustering. The input data points are mapped into a feature space using a nonlinear mapping φ. A kernel function F jk = φ(x j ), φ(x k ) is used to calculate the distance in feature space.

For this application, X-Forest maps data points to unit vectors in the feature space, and the kernel function is given by the similarity matrix M.

F jk = φ(x j ), φ(x k ) = M jk (3)

Density clustering: DBSCAN Ester et al. (1996) is the most popular density-based clustering method. In DBSCAN, a point is considered as a dense part if its -neighborhood has enough points. In the process of clustering, DBSCAN arbitrarily selects an unvisited dense part and its -neighborhood as a cluster, and recursively adds the -neighborhoods of the dense parts already added into this cluster, until no more points can be added. This process is repeated until all dense parts are visited.

In this application, the similarity matrix M can be used to express the inner product of two data points in the feature space φ. The distance of any two data points in the feature space can be obtained by the following formula.

φ(x j ) -φ(x k ) 2 = ( φ(x j ) -φ(x k ), φ(x j ) -φ(x k ) ) 1 2 = (2 -2 • M jk ) (4)

Spectral clustering: Spectral clustering Ng et al. ( 2002); Shi & Malik (2000) is an algorithm derived from graph theory and has been widely used in clustering. By defining the weight (similarity) between two data points, spectral clustering embeds data points into an undirected weighted complete graph. The complete graph is divided into K sub-graphs by cutting off the edge set with minimum weight to achieve the purpose of clustering.

Classic spectral clustering uses exp -x j -x k 2 /2σ 2 as the weight of the edge, where σ is the bandwidth of the graph. In this application, we directly use M jk of the similarity matrix M as the edge weight.

5. Experimental Results:

We first show the accuracy improvement of some classical clustering methods after using the β-Similarity generated by X-Forest. Then, we compare the performance in terms of computation time of X-Forest under different parameter settings.

5.1. Experimental Setup:

Choice of Datasets: As is shown in Table 1 , we conduct experiments on three real datasets from the UC Irvine machine learning library Dua & Graff (2017) , including Wine, Soybean and WDBC. All three datasets are labeled, allowing us to evaluate the actual performance of the clustering. Table 1 : A summary of datasets.

Dataset dimension # categories # data points:

Choice of Clustering Algorithms: In the first part of this section, we compare the accuracy of Kernel K-means, Density Clustering and Spectral Clustering using β-Similarity generated by X-Forest and distance similarity. In the second part, we use Kernel K-means as clustering algorithm to compare the performance of X-Forest under different parameter settings.

Evaluation Metrics: We use Accuracy as an evaluation metric of the performance of clustering. The definition of Accuracy is given by the formula below. It measures the fraction of matching labels given by the clustering algorithm divided by the real label.

Definition 3 Let S = {x 1 : y 1 , x 2 : y 2 , • • • , x n : y n } be the dataset, ŷ(.) be the label obtained by the clustering algorithm, and σ(.) be the permutation of n elements.

EQUATION

Default Configuration: Table 2 shows the default parameter configuration of X-Forest on 3 data sets, and lists the average depth of the X-Projection trees on these datasets. Since all the average depths are between 8 and 16, we regard the X = 16 X-Forest as standard RP Trees and layer-by-layer RP Trees. In the experiment, we generate 1000 similarity matrices for each parameter configuration and show the average value of Accuracy and Time. All experiments are conducted on laptop with 2.6 GHZ Intel Core i7 CPU. D i s t a n c eX -s i m i l a r i t yD i s t a n c eX -s i m i l a r i t yD i s t a n c e X -s i m i l a r i t y 0 . 4 0 . 6 0 . 8 1 . 0 

Dataset # Trees:



5.1.1. Experiments on Accuracy:

Accuracy vs. Different Similarity (Figure 6 ): In this experiment, we use different clustering algorithms (Kernel K-means, DBSCAN, Spectral Clustring) and different similarity measurements (β-Similarity, distance similarity). Figure 6 shows that the Accuracy of Kernel K-means using β-Similarity are respectively about 11.1%, 9%, 24% higher than the of that of using distance similarity on the three datasets. The Accuracy of DBSCAN using β-Similarity are respectively about 27.6%, 5.5%, 33.7% higher than that of using distance similarity on the three datasets. The Accuracy of Spectral Clustering using β-Similarity are respectively about 21.3%, 28.6%, 34.8% higher than that of using distance similarity on the three datasets.

Accuracy vs. X (Figure 7 ): In this experiment, we change the value of X (1, 2, 4, 8, 16) and the number of X-Projection trees (20, 40, 80, 160, 320, 640, 1280) in an X-Forest and use Kernel K-means for clustering. When tree number is 1280, for the soybean dataset (Figure 7 (a)), we see that the accuracy of the X = 2 and X = 4 version of X-Forest are respectively about 96.4% and 99.1% of that of standard RP Trees. For the WDBC dataset (Figure 7 (b)), we see that the accuracy of the X = 2 and X = 4 version of X-Forest are almost the same as that of standard RP Trees. For the wine dataset (Figure 7 (c)), we see that the accuracy of the X = 2 and X = 4 version of X-Forest are respectively about 99.4% and 99.8% of that of standard RP Trees.

6 42 5 61 0 2 4 0 . 6 4 0 . 6 8 0 . 7 2 0 . 7 6 A c c u r a c y # T r e e s X = 1 X = 2 X = 4 X = 8 X = 1 6 (a) Soybean.

6 42 5 61 0 2 4 0 . 9 0 0 . 9 2 0 . 9 4 A c c u r a c y # T r e e s X = 1 X = 2 X = 4 X = 8 X = 1 6 (b) WDBC.

6 42 5 61 0 2 4 0 . 8 4 0 . 8 7 0 . 9 0 0 . 9 3 0 . 00 . 30 . 60 . 9 0 . 9 3 0 . 9 4 0 . 9 5 0 . 00 . 30 . 60 . 9 0 . 9 0 0 . 9 2 0 . 9 4 ), the accuracy of the β = 0.7 version of β-Similarity is about 0.9% higher than that of the β = 0 version of β-Similarity, while the variance is 5.28 times smaller. For the wine dataset (Figure 8(c )), the accuracy of the β = 0.9 version of β-Similarity is about 3.8% higher than that of the β = 0 version of β-Similarity , while the variance is 2.16 times smaller.

5.1.2. Experiments on Speed:

Building Speed X-Forest vs. X (Figure 9 ): In this experiment, we vary X (1, 2, 4, 8, 16) and the number of X-Projection trees (160, 320, 640, 1280) in X-Forest and use Kernel K-means for clustering. When the number of X-Projection trees is 1280, for the soybean dataset (Figure 9 (a)), the speed of the X = 2 and X = 4 versions of X-Forest are respectively about 2.98 and 1.74 times faster than standard RP Trees. For the WDBC dataset (Figure 9 (b)), the speed of the X = 2 and X = 4 versions of X-Forest are respectively about 3.61 and 2.57 times faster than standard RP Trees. For the wine dataset (Figure 9 (c)), the speed of the X = 2 and X = 4 versions of X-Forest are respectively about 1.34 and 1.03 times faster than standard RP Trees.

6. Conclusion:

The design goals of an ideal similarity measurement solution are respectively high accuracy, high efficiency in terms of speed and independence from priori knowledge of the dataset. We propose X-Forestto achieve all the above goals: 1) We introduce RP Tree into similarity measurement because it better represents the similarity value between item pairs; 2) We manage to reduce computational time through sharing projection values in the partition process of some layers; 3) We rely on randomness in partition to get rid of the need of priori knowledge of the dataset, such as data distribution characteristics.

where V a and V b are random variables representing whether point A and B are partitioned on direction a and b respectively, similar to V . It is obvious that Pr(V a = 0 | Y 1 = θ 1 ) has the same form as Pr(V b = 0 | Y 2 = θ 2 ), therefore we just need to focus on the direction a.

Recall that when the depth of a tree node is even, direction a will be used. Therefore, n partition thresholds will be chosen on direction a. We can simplify the procedure of choosing n partition thresholds as shrinking the total length L(S, a) by n times. The probability of the final total length being bigger than l cos(θ 1 ) is the probability of the two points A and B not being partitioned in direction a. In our algorithm, the partition threshold is uniformly chosen at random in the current range recursively, which means that the shrink factor satisfies U [0,1] . Therefore, we have

EQUATION

where Z 1 , Z 2 , . . . , Z n are i.i.d random variables such that Z i ∼ U [0,1] , and Z(n) is the product of Z 1 , Z 2 , . . . , Z n .

We now derive the upper bound of the probability as the following

Pr(V = 0) = Pr V ≤ 0, Y 1 ≤ π 2 , Y 2 ≤ π 2 = π 2 0 dθ 1 π 2 0 dθ 2 • Pr(V = 0 | Y 1 = θ 1 , Y 2 = θ 2 ) • f Y1 (θ 1 ) • f Y2 (θ 2 )

where f Y1 and f Y2 is the probability density function (PDF) of Y 1 and Y 2 . Combining ( 6), ( 7) and the result from Lemma 2, we find Pr(V = 0) ≤ The inequality of Theorem 1 shows that the probability of the two point not being partitioned has an upper bound F 2 n (l/ρ(S)). However, the reader may want to know whether F n gives a reasonable bound for the probability. Therefore, we give a lemma to further illustrate the feature of F n .

Lemma 1 F n (x) is a strictly monotonically decreasing function with respect to x in (0, 1), and satisfies F n (0) = 1 , F n (1) = 0

Proof. First we prove that F n is strictly monotonically decreasing. It is obvious that (-log z) n-1 > 0 for any z ∈ (0, 1). Therefore, given x 1 , x 2 ∈ (0, 1) such that x 1 < x 2 , we have 

:



Figures and Tables:

Figure 1: Relationship between projection and space partitioning. The red arrow is the projection direction. P τ the a partition point. The vertical line is the spatial partition hyperplane.

Figure 2: Example of a standard RP Tree. Each node uses an independent unit random projection direction.

Figure 3: Similarity between data points of the first class (number 1-50) and the entire dataset (number 1-50, number 51-100, number 101-150).

Figure 4: Example of a layer-by-layer RP tree. Different nodes of each layer use the same projection direction. The projection directions on each path from the root to the leaf are still independent.

Figure 5: Example of a X-Projection Tree.A tree uses only two random directions. One (red) for odd layers and the other (yellow) for even layers.

A c c u r a c y S o y b e a n W D B C W i n e K e r n e l K -m e a n s D B S C A N S p e c t u a l C l u s t e r i n g

Figure 6: Accuracy of different clustering algorithms on several datasets with distance similarity and X-Similarity.

Figure 7: Accuracy of X-Forest with different numbers of trees and Xs.0 . 00 . 30 . 60 . 9 0 . 5 0 0 . 6 0 0 . 7 0 0 . 8 0 A c c u r a c y

Figure 8: Accuracy and variance of β-Similarity with different βs. Accuracy vs. β (Figure 8): In this experiment, we change β ([0, 1)) and use Kernel K-means for clustering. For the soybean dataset (Figure 8(a)), the accuracy of the β = 0.9 version of β-Similarity is about 25.9% higher than that of the β = 0 version of

Figure 9: Time to build X-Forest for different numbers of trees and Xs. β-Similarity. For the WDBC dataset (Figure 8(b)), the accuracy of the β = 0.7 version of β-Similarity is about 0.9% higher than that of the β = 0 version of β-Similarity, while the variance is 5.28 times smaller. For the wine dataset (Figure8(c)), the accuracy of the β = 0.9 version of β-Similarity is about 3.8% higher than that of the β = 0 version of β-Similarity , while the variance is 2.16 times smaller.

dz 2 • (log z 1 log z 2 ) n-1

x1cos(θ) (-log z) n-1 dz > 1 x2cos(θ) (-log z) n-1 dz

Default Configuraion.

Table content: <table><tr><td/><td/><td>X</td><td>τ</td><td>β</td><td>Average Depth</td></tr><tr><td>Wine</td><td>1000</td><td colspan="3">2 10 0.9</td><td>9.6</td></tr><tr><td>Soybean</td><td>1000</td><td>2</td><td colspan="2">3 0.9</td><td>12.4</td></tr><tr><td>WDBC</td><td>1000</td><td colspan="3">2 30 0.9</td><td>15.1</td></tr></table>

Peer review (iclr2020):
This paper proposes the similarity measure called *beta-similarity* generated by an ensemble of Random projection trees (RP trees) by Dasgupta & Freund (2008). To reduce the computational costs for building many RP trees, the paper develops an efficient approximate version called X-Projection trees by first generating X independent random projection directions, and then by sharing them at layers in turns. X-Forest is a set of X-Projection trees with X different random projections, and the proposed *beta similarity* between x and y is defined by distances between a leaf region having x and one having y in PR trees. Experimental evaluations demonstrated that the use of beta similarity improves the clustering accuracy using it within three types of methods (kernel k-means, DBSCAN, Spectral clustering). The paper*s idea of defining a similarity using many RP Trees with different randomization is quite interesting and sounds promising given that the recently reported performance of tree ensembles such as XGBoost and LightGBM is very good. Partition-based trees plus randomizations are known to have very nice properties particularly in high dimensions, theoretically speaking. However, this paper also has several problems 1) novelty and 2) confusing and imprecise statements. 1) novelty The novelty of the paper is basically (a) a simple computation savings of X-forest and (b) a definition of beta similarity. For (a), the novelty is rather small, and how much this computation savings have a practical impact is questionable since reported computation timings in Figure.9 are in ms. Furthermore, trivial parallelization would be possible because individual computations of RP trees in the ensemble are independent. Also, there exists a highly cited paper by Yan et al KDD*09 proposed a fast clustering method based on RP trees as *fast approximate spectral clustering* in their title. On the other hand, (b) would be novel but any consideration about alternatives is not given, and the definition sounds quite heuristic and less convincing. RP trees are existing spatial structures (proposed by Dasgupta & Freund) extending widely used k-d trees. It naturally defines the spatial closeness of data points, and thus the use of RP trees to define the similarity, and applying them to clustering (kernel k-means, DBSCAN, spectral) is not new. RP trees were proposed as an alternative of k-d trees, and the primary applications would be for nearest neighbor search or data compression like vector quantization. 2) confusing and imprecise statements Many confusing and imprecise statements exist. 2a) The proposed *beta similarity* eq (2) seems to lack the definition of DIS_i(X, Y). It would be something like the path length between node X and Y, or steps to the LCA (the lowest common ancestor). Also, the number m (the number of trees?) is also undefined. 2b) The three goals are set: accuracy, efficiency, and independence from prior knowledge. But when we use RP trees, 1st and 3rd are considered as resolved and sounds like the only remaining problem is *efficiency* for their computations. Also, the third goal *independence from prior knowledge* is quite vaguely explained, and hard to understand. For example, the affinity matrix in spectral clustering or kernel matrix with an RBF kernel is the case? It would be a kind of hyperparameters but not like *dependence on prior knowledge*. 2c) Also, *accuracy* of *similarity measurements* is quite ambiguous. The use of kernel distance with RBF kernel is less accurate than the use of RP trees?? The *similarity measurement* sounds like the problem of definition, and it cannot be accurate or inaccurate. The distance-based similarities themselves have no problems, and even when RP trees are used, we need some distance metric (i.e. Euclidean distance) in a space.