# Abnormal Activity Detection Using Pyroelectric Infrared Sensors
## 5 Spectral Clustering
### Self-Tuning Spectral Clustering  
After the similarity matrix \(\mathbf{\hat{S}}=\{s_{ij}\}\) is constructed, we apply spectral clustering methods to partition the training sequences into clusters. For an undirected graph \(G\) with vertices \(v_{i}\) and edges \(s_{ij}\), the matrix \(\mathbf{S}\) could be considered as an adjacent matrix for \(G\), where each element \(s_{ij}\) can be viewed as the similarity between the vector \(v_{i}\) and \(v_{j}\). The target of spectral clustering is to partition the \(G\) into a distinct sub-graph. It is a tricky problem to specify the number of clusters \(C\). One method to discover the number of clusters is to analyze the eigenvalues of the normalized Laplacian matrix \(\mathbf{L}_{a}\), which is based on the similarity matrix \(\hat{\mathbf{S}}\). The analysis given in [33] shows the number of repeated eigenvalues of magnitude 0 with multiplicity equal to the number of clusters \(C\). However, eigenvalues depend on the structure of the individual clusters, and no assumptions can be placed on their values [12]. Once noise is introduced, the eigenvalues deviate from the ideal case, and it is difficult to decide the number of clusters. An alternative approach to discover the number of clusters \(C\) automatically is to analyze the eigenvectors of Laplacian matrix \(\mathbf{L}_{a}\)[12]. Assume the matrix \(\mathbf{X}=[x1,...,x_{C}]\in\mathbb{R}^{N\times C}\) is constructed by stacking the largest eigenvectors of \(\mathbf{L}_{a}\) in columns. In the ideal case where the data points could be separated distinctly, \(\mathbf{X}\) will be strictly block diagonal after sorting the eigenvectors of \(\mathbf{L}_{a}\). Nevertheless, in the general case, the \(\mathbf{X}\)'s off-diagonal blocks are non-zero, and the eigensolver could just pick any other set of the orthogonal vectors; \(\mathbf{X}\) could have been replaced by \(\hat{\mathbf{X}}=\mathbf{X}\mathbf{R}\) for any orthogonal matrix \(\mathbf{R}\in\mathbb{R}^{C\times C}\). Now, we have to recover the rotation which best aligns \(\mathbf{X}\)'s columns with the canonical system with the minimum cost. Let \(\mathbf{Z}\in\mathbb{R}^{N\times C}\) be the matrix obtained after rotating the eigenvector matrix \(\mathbf{X}\); that is, \(\mathbf{Z}=\mathbf{X}\mathbf{R}\). We wish to recover the rotation \(\mathbf{R}\) for which, in every row in \(\mathbf{Z}\), there will be at most one non-zero entry. We thus define the cost function:  
\[J=\sum_{i=1}^{N}\sum_{j=1}^{C}\frac{Z_{ij}^{2}}{M_{i}^{2}} \tag{12}\]  
where \(M_{i}=\max_{j}Z_{ij}\). Minimizing this cost function over all possible rotations will provide the best alignment with the canonical coordinate system. The number of clusters, \(C\), is taken as the one providing the minimal cost. The spectral clustering algorithm that we apply is similar to the one proposed in [12]. The algorithm works as follows:  
1. Define a diagonal degree matrix \(\mathbf{D}=\{d_{ij}\}\) with \(d_{ii}=\sum_{j=1}^{N}\hat{s}_{ij}\), and then construct the normalized Laplacian matrix \(\mathbf{L}_{a}=\mathbf{D}^{-1/2}\hat{\mathbf{S}}\mathbf{D}^{-1/2}\). 2. Find \(C^{\prime}\) principal eigenvectors \(x_{1},x_{2},...,x_{C^{\prime}}\) and form the matrix \(\mathbf{X}=[x1,...,x_{C}^{\prime}]\in\mathbb{R}^{N\times C^{\prime}}\) by stacking the eigenvectors in columns, where \(C^{\prime}\) is the largest possible cluster number. 3. Recover the rotation \(\mathbf{R}\) which best aligns \(\mathbf{X}\)'s columns with the canonical coordinate system using the incremental gradient descent algorithm [12]. 4. According to Equation (12), grade the cost of the alignment for each group number up to \(C^{\prime}\). Set the final group number \(C_{\text{best}}\) to be the largest group number with minimal alignment cost. 5. Take the alignment result \(\mathbf{Z}\) of the \(C_{\text{best}}\) eigenvectors, and assign the original point \(s_{i}\) to cluster c if and only if \(\max_{j}(Z_{ij}^{2})=Z_{ic}^{2}\).