Linear Algebra Methods for Data Mining

LSI and related methods Given a set of k basis vectors (x1... xk) = Xk, express the data matrix A in terms of the columns of this basis.. That is, solve the least squares problem: min Y ‖A−XkY‖. The basis vectors xj may be the left singular vectors, or the centroids of some clustering of the data vectors into k clusters. Also express the query in the new basis, and perform query matching in the new subspace spanned by the xj, j = 1...k. Linear Algebra Methods for Data Mining, Spring 2007, University of Helsinki 1 Note: • SVD gives the best approximation of A in terms of minimizing distance between A and XkY (in the euclidean norm). • But: centroids seem to give a better (reduced dimensional) representa-tion of the original documents (at least for well clustered data). • That is, with centroids it seems possible to use even smaller reduced dimension than SVD to get results of similar quality. • Centroids play a very similar role as do singular vectors in LSI. • BUT:Centroids/Concept vectors are sparse. Singular vectors are essentially full. Linear Algebra Methods for Data Mining, Spring 2007, University of Helsinki 2 Query matching Query matching is usually done using cosine similarity: cos(θ(q,aj)) = qTaj ‖q‖‖aj ‖ ≥ tol Varying tolerance you vary the precision and recall: P