《海量数据挖掘-王永利》ch11-dimred.pptVIP

Sampling columns (similarly for rows): J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, * Note this is a randomized algorithm, same column can be sampled more than once Let W be the “intersection” of sampled columns C and rows R Let SVD of W = X Z?YT Then: U = W+ =?Y Z+?XT Z+: reciprocals of non-zero singular values: Z+ii =1/ Zii W+ is the “pseudoinverse” J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, * A C R U = W+ W ? Why pseudoinverse works? W = X Z Y then W-1 = X-1 Z-1 Y-1 Due to orthonomality X-1=XT and Y-1=YT Since Z is diagonal Z-1 = 1/Zii Thus, if W is nonsingular, pseudoinverse is the true inverse J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, * In practice: Pick 4k cols/rowsfor a “rank-k” approximation SVD error CUR error Easy interpretation Since the basis vectors are actual columns and rows Sparse basis Since the basis vectors are actual columns and rows Duplicate columns and rows Columns of large norms will be sampled many times J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, * Singular vector Actual column If we want to get rid of the duplicates: Throw them away Scale (multiply) the columns/rows by the square root of the number of duplicates J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, * A Cd Rd Cs Rs Construct a small U J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, * SVD: A = U ? VT Huge but sparse Big and dense CUR: A = C U R Huge but sparse Big but sparse dense but small sparse and small DBLP bibliographic data Author-to-conference big sparse matrix Aij: Number of papers published by author i at conference j 428K authors (rows), 3659 conferences (columns) Very sparse Want to reduce dimensionality How much time does it take? What is the reconstruction error? How much space do we need? J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, * Accuracy: 1 – relative sum squared err