ch11-dimred的文档的文档.pptx

Dimensionality Reduction:SVD & CURMining of Massive DatasetsJure Leskovec, Anand Rajaraman, Jeff Ullman Stanford University Note to other teachers and users of these slides: We would be delighted if you found this our material useful in giving your own lectures. Feel free to use these slides verbatim, or to modify them to fit your own needs. If you make use of a significant portion of these slides in your own lecture, please include this message, or a link to our web site: Dimensionality ReductionAssumption: Data lies on or near a low d-dimensional subspaceAxes of this subspace are effective representation of the dataJ. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, 2 Dimensionality ReductionCompress / reduce dimensionality:106 rows; 103 columns; no updatesRandom access to any cell(s); small error: OKJ. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, 3The above matrix is really “2-dimensional.” All rows can be reconstructed by scaling [1 1 1 0 0] or [0 0 0 1 1] Rank of a MatrixQ: What is rank of a matrix A?A: Number of linearly independent columns of AFor example:Matrix A = has rank r=2Why? The first two rows are linearly independent, so the rank is at least 2, but all three rows are linearly dependent (the first is equal to the sum of the second and third) so the rank must be less than 3.Why do we care about low rank?We can write A as two “basis” vectors: [1 2 1] [-2 -3 1]And new coordinates of : [1 0] [0 1] [1 1]J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, 4 Rank is “Dimensionality”Cloud of points 3D space:Think of point positionsas a matrix:We can rewrite coordinates more efficiently!Old basis vectors: [1 0 0] [0 1 0] [0 0 1]New basis vectors: [1 2 1] [-2 -3 1]Then A has new coordinates: [1 0]. B: [0 1], C: [1 1]Notice: We reduced the number of coordinates!1 row per point:ABC AJ. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, 5 Dimensionality ReductionGoal of dimensionali