Optimal subspace dimensionality for k-nearest-neighbor queries on clustered and dimensionality reduced datasets with SVD

Abstract

Content based image retrieval represents images as N- dimensional feature vectors. The k images most similar to a target image, i.e., those closest to its feature vector, are determined by applying a k-nearest-neighbor (k-NN) query. A sequential scan of the feature vectors for k-NN queries is costly for a large number of images when N is high. The search space can be reduced by indexing the data, but the effectiveness of multidimensional indices is poor for high dimensional data. Building indices on dimensionality reduced data is one method to improve indexing efficiency. We utilize the Singular Value Decomposition (SVD) method to attain dimensionality reduction (DR) with minimum information loss for static data. Clustered SVD (CSVD) combines clustering with SVD to attain a lower normalized mean square error (NMSE) by taking advantage of the fact that most real-world datasets exhibit local rather than global correlations. The Local Dimensionality Reduction (LDR) method differs from CSVD in that it uses an SVD-friendly clustering method, rather than the k-means clustering method. We propose a hybrid method which combines the clustering method of LDR with the DR method of CSVD, so that the vector of the number of retained dimensions of the clusters is determined by varying the NMSE. We build SR-tree indices based on the vectors in the clusters to determine the number of accessed pages for exact k-NN queries (Thomasian et al., Inf Process Lett - IPL 94(6):247–252, 2005) (see Section A.3 versus the NMSE. Varying the NMSE a minimum cost can be found, because the lower cost of accessing a smaller index is offset with the higher postprocessing cost resulting from lower retrieval accuracy. Experimenting with one synthetic and three real-world datasets leads to the conclusion that the lowest cost is attained at NMSE ≈ 0.03 and between 1/3 and 1/2 of the number of dimensions are retained. In one case doubling the number of dimensions cuts the number of accessed pages by one half. The Appendix provides the requisite background information for reading this paper.

Appendix: preliminaries

We first describe the SVD method in Sectionref:SVD. In Section A.2 we specify the SVD-friendly clustering method developed in conjunction with the LDR method. Exact versus approximate k-NN query processing methods are discussed in Section A.3. Finally, in Section A.3 we specify an efficient method to compute Euclidean distances with dimensionally reduced data.

1.1 A.1 Singular value decomposition

The SVD of an M ×N matrix X for feature vectors is: X = USV ^T, where U is an M×N column-orthonormal matrix, V is an N×N unitary matrix of eigenvectors, and S is a diagonal matrix of singular values: s ₁ ≥ s ₂ ≥ ... ≥ s _N . The mean values have been subtracted from the elements in each column, so that the columns of X have a zero mean. When N′ of the singular values are close to zero, then the rank of X is N − N′ [12]. The cost of computing eigenvalues using SVD is O ( M N ² ).

PCA is based on the decomposition of the covariance matrix C = X ^T X/M = V ΛV ^T , where V is the matrix of eigenvectors and Λ is a diagonal matrix, which holds the eigenvalues of C. C is positive-semidefinite, so that its N eigenvectors are orthonormal and its eigenvalues are nonnegative. The trace (sum of eigenvalues) of C is invariant under rotation. We assume that the eigenvalues, similar to the singular values, are in nonincreasing order. The singular values are related to the eigenvalues by: $\lambda_j = s^2_j /M$ or $s_j = \sqrt{M\lambda_j}$. The eigenvectors constitute the principal components of X, hence the transformation below yields uncorrelated features:

$$\label{equ:transform} Y=XV $$

(5)

Retaining the first n dimensions of Y minimizes the NMSE and maximizes the fraction of preserved variance:

$$ \label{equ:nmse} NMSE = \frac{\sum_{i=1}^M {\sum_{j=n+1}^N{y_{i,j}^2}}}{\sum_{i=1}^M{\sum_{j=1}^N{y_{i,j}^2}}} =\frac{\sum_{j=n+1}^N{\lambda_j}}{\sum_{j=1}^N{\lambda_j}} $$

(6)

Retaining the first n dimensions of Y minimizes the NMSE and maximizes the fraction of preserved variance:

1.2 A.2 Clustering

A large number of clustering algorithms, which are applicable to various domains have been developed over the years [17]. The k-means clustering method used [9, 35] can be specified succinctly [14]: (i) Randomly select H points from the dataset to serve as preliminary centroids for clusters. Improve centroid spacing using the method in [16]. (ii) Assign points to the closest centroid based on the Euclidean distance to form H clusters. (iii) Recompute the centroid for each cluster. (iv) Go back to step (ii), unless there is no new assignment. ${\cal C}^{(h)}$ denotes the h ^th cluster, with centroid C _h with coordinates given by $\vec{\mu}^{(h)}$, and a radius R ^h, which is the distance of the farthest point in the cluster from C _h . Since the quality of the clusters varies significantly from run to run, the clustering experiment is repeated and the experiment yielding the smallest sum of squares (SSQ) distances to the centroids of all clusters is selected:

$$\label{eq:SSQ} SSQ = \sum_{h=1}^H \sum_{i \in {\cal C}^{(h)}} \sum_{j=1}^N \left(x_{i,j} - \mu^{(h)}_j \right) ^2 . $$

(7)

The k-means clustering method does not scale well to large high-dimensional datasets [28]. Subspace clustering methods take advantage of the fact that in high dimensional datasets many dimensions are redundant and hide clusters in noisy data. The curse of dimensionality also makes distance measures meaningless to an extent that data points are equidistant from each other. Subspace clustering methods find clusters in different, lower-dimensional subspaces of a dataset [30]. The weakness of the CLIQUE subspace clustering method [1] is that the subspaces are aligned with the original dimensions. Many others which are reviewed in [30]. The Multi-level Mahalanobis-based Dimensionality Reduction [19] clusters high dimensional datasets using the low-dimensional subspace based on the Mahalanobis [12] rather than the Euclidean distance, since it is argued that locally correlated clusters are elliptical shaped.

The LDR clustering method specified in [11] and utilized in this paper generates SVD-friendly clusters [35], which are amenable to DR at a small NMSE. The following discussion follows the Appendix in [9].

• 1- Initial selection of centroids: H points with pairwise distances of at least threshold are selected.

• 2- Clustering. Each point is associated to the closest centroid whose distance is ≤ ε, and ignored otherwise. Each cluster has now a centroid, the average of the associated points.

• 3- Apply SVD to each cluster. Each cluster has now a reference frame.

• 4- Assign points to clusters: Each point in the dataset is analyzed in the reference frame of each cluster. For each cluster determine the minimum number of retained dimensions so that squared error in representing points does not exceed MaxReconDist ². The cluster requiring the minimum number of dimensions N _min is determined. If N _min  ≤ MaxDim, the point is associated with that cluster, and the required number of dimensions is recorded, otherwise the point becomes an outlier.

• 5- Compute the subspace dimensionality of each cluster. Find the minimum number of dimensions ensuring that at most FracOutliers of the points assigned to the cluster in Step 4 do not satisfy the MaxReconDist ² constraints. Each cluster has now a subspace.

• 6- Recluster points. Each point is associated with the first cluster whose subspace is at a distance less than MaxReconDist from the point. If no such cluster exists, the point becomes an outlier.

• 7- Remove small clusters. Clusters with size smaller than MinSize are removed and the corresponding points reclustered with Step 6.

• 8- Recursively apply Steps 1–7 to the outliers set. Make sure that the centroids selected in Step 1 have a distance at least threshold from the current valid clusters. The procedure terminates when no new cluster is identified.

• 9- Create an outlier list. As in [23] this is searched using a linear scan.

The values for H, threshold, ε, MaxReconDist, MaxDim, FracOutliers, and MinSize need to be provided by the user. This constitutes the main difficulty with applying the LDR method. The invariant parameters are MaxReconDist, MaxDim, and MinSize. The method can produce values of H, threshold, and overall FracOutliers, which are significantly different from the inputs. The fact that the LDR method determines the number of clusters is one of its advantages with respect to the k-means method.

1.3 A.3 Exact versus approximate k-NN queries

k-NN search methods are classifiable into exact and approximate methods. We first define Recall and Precision, which are metrics of retrieval accuracy and efficiency, respectively. Since SVD is a lossy data compression method, in processing k-NN queries we retrieve k ^* ≥ k points. Given that k′ of the retrieved points are among the k desired nearest neighbors, it is easy to see that k′ ≤ k ≤ k ^* . Recall (accuracy) is defined as ${\cal R } = k' / k$ and precision (efficiency) as ${\cal P} = k'/ k^*$. k-NN search on dimensionality reduced data is inherently approximate with a recall ${\cal R} < 1$. Exact k-NN search returns the same k-NNs as would have been obtained without DR, i.e., ${\cal R}=1$.

Post-processing is required to achieve exact k-NN query processing on dimensionally reduced data. Post processing takes advantage of the lower-bounding property (LBP) [12] (or Lemma 1 in [25, 26]): Given that the distance of points in the subspace with reduced dimensions is less than the original distance, a range query guarantees no false dismissals.

False alarms are discarded by referring to the original dataset. Noting the relationship between range and k-NN queries, the latter can be processed as follows [25]: (i) Find the k-NNs of the query point Q in the subspace. (ii) Determine the farthest actual distance to Q among these k points (d _max ). (iii) Issue a range query centered on Q on the subspace with radius ε = d _max . (iv) For all points obtained in this manner find their original distances to Q, by referring to the original dataset and rank the points, i.e., select the k-NNs.

The exact k-NN processing method was extended to multiple clusters in [37], where we compare the CPU cost of the two methods as the NMSE is varied using two of the datasets in Section 3. An offline experiment was used to determine k ^*, which yields a recall R ≈ 1. The CPU time required by the exact method for a sequential scan is lower than the approximate method, even when ${\cal R}=0.8$. This is attributable to the fact that the exact method issues a k-NN query only once and this is followed by less costly range queries.

The LDR method also takes advantage of LBP to attain exact query processing [11]. It produces fewer false alarms by incorporating the reconstruction distance (the squared distance of all dimensions that have been eliminated as an additional dimension with each point.

1.4 A.4 Computing distances with dimensionality reduced data

The DR method in [9, 35] retains n < N columns of the Y matrix, which correspond to the largest eigenvalues, while the method described in [12, 23] retains the n columns of the U matrix corresponding to the largest eigenvalues. In both cases the eigenvalues or singular values are in nonincreasing order, so that columns with the smallest indices need to be preserved. We first show that retaining the n columns of the Y matrix results in the same distance error as retaining the same dimensions of the U matrix. We also show that our method is computationally more efficient than the other method. Retaining the first n dimensions (columns) of the transformed matrix Y = X V we have:

$$ y_{i,j} = \sum_{k=1}^{N} x_{i,k} v_{k,j}, \; 1\leq j \leq n ,\; 1 \leq i \leq M. $$

The rest of the columns of the matrix are set to the column mean, which is zero in our case.² The squared error in representing point $P_i, \ 1 \leq i \leq M$ is then:

$$\label{eq:error} e_i = \sum_{j=n+1}^{N} y_{i,j}^2 = \sum_{j=n+1}^{N} \left( \sum_{k=1}^{N} x_{i,k} v_{k,j} \right)^2 , \; 1 \; \leq i \; \leq M . $$

The elements of X are approximated as X′ ≈ U S V ^T by utilizing the first n dimensions of U [12, 23]:

$$ \label{eq:xprime} {x'}_{i,j} = \sum_{k=1}^{n} s_k u_{i,k} v_{k,j} , \; 1 \leq j \leq N, \; 1 \leq i \leq M . $$

Noting that Y = XV = US, the squared error in representing P _i is:

$$ {e'}_i = \sum_{j=1}^{N} \left( \sum_{k=n+1}^{N} s_k u_{i,k} v_{k,j} \right)^2 = \sum_{j=1}^{N} \left( \sum_{k=n+1}^{N} y_{i,k} v_{k,j} \right)^2 . $$

To show that e _i  = e′ _i , 1 ≤ i ≤ M, we use the definition δ _k,k′ = 1 for k = k′ and δ _k,k′ = 0 for k ≠ k′ .

$$\begin{array}{lll} e'_i &=& \sum_{j=1}^{N} \left(\displaystyle\sum_{k=n+1}^{N} y_{i,k} v_{k,j}\right) \left(\displaystyle\sum_{k'=n+1}^{N} y_{i,k'} v_{k',j}\right) = \displaystyle\sum_{k=n+1}^{N} \displaystyle\sum_{k'=n+1}^{N} y_{i,k} y_{i,k'} \displaystyle\sum_{j=1}^{N} v_{k,j} v_{k',j} \\ &=& \displaystyle\sum_{k=n+1}^{N} \displaystyle\sum_{k'=n+1}^{N} y_{i,k} y_{i,k'} \delta_{k,k'} = \displaystyle\sum_{j=n+1}^{N} y^2_{i,j} = e_i .\end{array} $$

Our method is more efficient from the viewpoint of computational cost for nearest neighbor, range, and window queries. In the case of nearest neighbor queries, once the input or query vector is transformed and the appropriate n dimensions are selected, we need only be concerned with these dimensions. This is less costly than applying the inverse transformation.