## 3 Clustering Methods to Compact the Visual Information
### Spectral Clustering Algorithm  
Spectral clustering algorithms [45] have proven to be suitable to process highly-dimensional data. In this work, a spectral normalized clustering algorithm is used as was introduced by [PERSON] et al. [46]. This algorithm has been already used for mapping along with local features extracted from the scenes [29; 47].  
In our work, the algorithm departs from the set of global appearance descriptors \(D=\{\overrightarrow{d_{1}},\overrightarrow{d_{2}},...\overrightarrow{d_{N}}\}\) obtained from the images collected in the environment, and the parameter \(n_{c}\) is the desired number of clusters. Initially, the similitude between descriptors is calculated. This parameter is calculated for each pair of descriptors; hence, a matrix of similitudes \(S\) is obtained as \(S_{ij}=e^{-\frac{\lvert\overrightarrow{d_{i}}-\overrightarrow{d_{j}}\rvert ^{2}}{2\pi^{2}}}\) where \(\sigma\) is a parameter that controls the rapidity of the reduction of the similitude when the distance between \(\overrightarrow{d_{i}}\) and \(\overrightarrow{d_{j}}\) increases. The steps to carry out the clustering are the following:  
Figure 3: Example of an indoor map and a compression of the information. (**a**) Positions where the images were captured. (**b**) Result of the clustering process. (**c**) Each cluster is reduced to one representative.  
1. Calculation of the normalized Laplacian matrix: \[L=I-D^{-1/2}SD^{1/2}\] (2) where Dis a diagonal matrix \(D_{i}=\sum_{j=1}^{N}S_{ij}\).
2. Calculation of the \(n_{c}\) main eigenvectors of \(L\), \(\{\overrightarrow{u_{1}},\overrightarrow{u_{2}},...,\overrightarrow{u_{n_{c}}}\}\). Arranging these vectors by columns, the matrix \(U\in\mathbb{R}^{N\times n_{c}}\) is obtained.
3. Normalization of the matrix \(U\) to obtain the matrix \(T\in\mathbb{R}^{N\times n_{c}}\).
4. Extraction of vector \(\overrightarrow{y_{i}}\in\mathbb{R}^{n_{c}}\) from the ith row of the matrix \(T\). \(i=1,...,N\).
5. Clustering of the \(\overrightarrow{y_{i}}\) vectors by using a simple clustering algorithm (such as k-means or hierarchical clustering). Through this, the clusters \(A_{1},A_{2},...,A_{n_{c}}\) are obtained.
6. Obtaining the clusters with the original data as \(C_{1},C_{2},...,C_{n_{c}}\) where \(C_{i}=\overrightarrow{d_{j}}\mid\overrightarrow{y_{j}}\in A_{i}\).  
If the number of instances \(N\) or the dimension \(l\) is high, the computation of the \(n_{c}\) eigenvectors (third step) will be computationally expensive. To solve this issue, [PERSON] (1986) proposed cancelling some components of the similitude matrix. This way, in the matrix \(S\), only the components \(S_{ij}\) so that \(j\) is among the \(t\) nearest neighbours of \(i\) are retained. After this, the \(n_{c}\) first eigenvectors of the Laplacian matrix \(L\) are calculated by using the Lanczos/Arnoldi factorization [PERSON] (1986).  
Finally, for each cluster, a representative is obtained as the average visual descriptor of the set of descriptors that compose that cluster.  
Spectral clustering may result in being more efficient than traditional methods such as k-means or hierarchical clustering in large environments due to the fact that spectral clustering considers the mutual similitude between the instances.