# Two-Step Classification with SVD Preprocessing of Distributed Massive Datasets in Apache Spark
## 3 Proposed Method
### Feature Selection  
Feature selection is a challenging topic in classification since the set of features of minimum cardinality is rarely known in advance; this also accurately describes a given dataset in the sense that adding more features to that set improves a pre-specified classification performance metric. On the other hand, too many attributes may in fact impede the classifier. SVD is a linear algebraic technique which relies on the factorization of the original data matrix \(\mathbf{A}\in\mathbb{R}^{m\times n}\) with \(m\) observations (rows) and \(n\) attributes (columns) in order to achieve dimensionality reduction as in Equation (1):  
\[\mathbf{A}\stackrel{{\triangle}}{{=}}\mathbf{U}\mathbf{\Sigma} \mathbf{V}^{T}\;=\;\sum_{k=1}^{r}\sigma_{k,k}\mathbf{u}_{k}\mathbf{v}_{k}^{T}, \qquad\mathbf{U}\in\mathbb{R}^{m\times r},\mathbf{\mathbf{V}}\in\mathbb{R}^{ n\times r},\mathbf{\mathbf{\Sigma}}\in\mathbb{R}^{r\times r},r\leq\min\left\{m,n\right\} \tag{1}\]  
In Equation (1), \(\mathbf{U}\) and \(\mathbf{V}\) are orthonormal matrices containing the respective bases for two distinct \(r\)-dimensional linear spaces that comprise eigenfeatures. The nature of these spaces depends directly on the underlying domain. For instance, in the document retrieval case, SVD is another name for the latent semantic indexing (\(LSI\)). In the latter, \(\mathbf{U}\) and \(\mathbf{V}\) are the eigendocument and eigenterm spaces respectively, which combined yield the original document-term matrix. \(\mathbf{\Sigma}\) is always a diagonal matrix with strictly positive diagonal entries \(\sigma_{k,k}\), \(1\leq k\leq r\) and dictates how the two features spaces are composed. As it can be seen from the right form of Equation (1), this coupling is straightforward as only the \(k\)-th column \(\mathbf{u}_{k}\) of \(\mathbf{U}\) and the \(k\)-th row \(\mathbf{v}_{k}^{T}\) of \(\mathbf{V}\) are combined in a cross product scaled by \(\sigma_{k,k}\). A key aspect of SVD is that \(r\) is directly discovered from \(\mathbf{A}\) and as a result, it belongs to unsupervised ML methods.  
SVD works best when the attributes are linearly connected. In that case, the resulting attribute set is typically smaller and yet captures most of the essence of the original attribute set. When there are non-linear connections in the feature set, then the SVD yields the orthogonal projection of the best attribute set to the observation data.  
As stated in the dimensionality reduction, RDD based, API documentation of MLlib, _spark.mllib_ provides an efficient SVD implementation for row oriented matrices, provided in the _RowMatrix_ class. According to the same documentation, two strategies can be followed:  
* When \(n\) is smaller than 100 or when \(k\) exceeds \(\left\lceil\frac{n}{2}\right\rceil\), then the Gramian matrix \(\mathbf{A}^{T}\mathbf{A}\) is computed and its top eigenvectors are subsequently computed locally at the Spark driver.
* Otherwise, the Gramian matrix is computed in a distributed way and its top eigenvectors are again locally computed at the driver as in the previous case.