cs276atextretrievalandmining.pptVIP

CS276AText Retrieval and Mining Lecture 15 Recap: Clustering 2 Hierarchical clustering Agglomerative clustering techniques Evaluation Term vs. document space clustering Multi-lingual docs Feature selection Labeling Linear Algebra Background Eigenvalues Eigenvectors Eigenvectors (for a square m?m matrix S) How many eigenvalues are there at most? Matrix-vector multiplication Matrix vector multiplication Thus a matrix-vector multiplication such as Sx (S, x as in the previous slide) can be rewritten in terms of the eigenvalues/vectors: Even though x is an arbitrary vector, the action of S on x is determined by the eigenvalues/vectors. Suggestion: the effect of “small” eigenvalues is small. Eigenvalues Eigenvectors Example Let Then The eigenvalues are 1 and 3 (nonnegative, real). The eigenvectors are orthogonal (and real): Eigen/diagonal Decomposition Let be a square matrix with m linearly independent eigenvectors (a “non-defective” matrix) Theorem: Exists an eigen decomposition (cf. matrix diagonalization theorem) Columns of U are eigenvectors of S Diagonal elements of are eigenvalues of Diagonal decomposition: why/how Diagonal decomposition - example Example continued Symmetric Eigen Decomposition If is a symmetric matrix: Theorem: Exists a (unique) eigen decomposition where Q is orthogonal: Q-1= QT Columns of Q are normalized eigenvectors Columns are orthogonal. (everything is real) Exercise Examine the symmetric eigen decomposition, if any, for each of the following matrices: Time out! I came to this class to learn about text retrieval and mining, not have my linear algebra past dredged up again … But if you want to dredge, Strang’s Applied Mathematics is a good place to start. What do these matrices have to do with text? Recall m? n term-document matrices … But everything so far needs square matrices – so … Singular Value Decomposition Singular Value Decomposition Illustration of SVD