大數據存儲與處理

大數據存儲與運用

降維課程主頁：/?page_id=397陳一帥chenyishuai@gmail引見為什么要降維？找出規(guī)律，緊縮數據量幾維？降維看起來2維，其實1維看起來3維，其實2維內容特征值與特征向量PCA〔主元素分析〕Principal-ComponentAnalysisSVD〔奇特值分解〕Singular-ValueDecompositionCUR分解特征值與特征向量特征值與特征向量定義計算方法PowerIteration尋覓特征對〔Eigenpairs〕特征向量矩陣定義M矩陣，λ常數，e非零列向量Me=λe獨一確定一個ee為unitvector第一個非零元素為正普通計算方法要，的行列式等于0求得λ然后經過Me=λe求e計算復雜度O(n3)PowerIteration方法任選一個向量X0遞歸誤差Frobeniusnorm足夠小時，停頓這個Xk就是M的主特征向量然后經過Mx=λx求λx是一個單位向量：X-1=XTPowerIteration方法再找第二個特征對在M中去掉第一個主特征向量的要素然后類似計算特征向量矩陣特征向量是單位向量特征向量之間正交特征向量矩陣E的特點PCAPCA事例運用特征向量進展降維間隔矩陣原理將矩陣與一個正交單位向量矩陣相乘，意味著在歐式空間上的旋轉求的特征矩陣E，對高維數據進展旋轉原數據變成在新的坐標上的投影。新的坐標上，第一維是主特征向量指向的那個方向，能量最強以后依次遞減使降維成為能夠原始數據按虛線旋轉逆時針45度旋轉對稱陣在新坐標系上的位置第一維的能量>第二維的能量，而且它們正交所以，假設要降到一維，無疑，應該保管第一維，把第二維去掉PCASVDSVD定義降維運用計算定義r是A的Rank〔秩〕U：左奇特向量Leftsingularvectors單位正交矩陣：奇特值Singularvalues對角陣，V：右奇特向量Rightsingularvectors單位正交矩陣例二維M的秩r=2科幻浪漫用戶–概念矩陣概念強度矩陣電影–概念矩陣科幻浪漫科幻浪漫SVD用戶電影觀看矩陣科幻浪漫用戶–概念矩陣概念強度矩陣電影–概念矩陣科幻浪漫科幻浪漫在實踐中，U，V中沒有這么多0概念分得沒有這么清SVD的了解V是把電影按照用戶進展概念分類后的結果五部電影，投影到“科幻〞“浪漫〞兩個概念上SVD的了解是將用戶按照電影進展概念分類后的結果7個用戶，投影到“科幻〞“浪漫〞兩個概念上基于SVD的降維降概念強度最低那一維用戶–概念矩陣概念強度矩陣電影–概念矩陣降維結果誤差評價降維證明為什么去掉最小的那一維，誤差最小？需求證明兩點假設M=PQR是M的SVD，有qii是Q對角線上的值，也就是實際中堅持80～90%的能量計算復雜度看哪個小LINPACK,Matlab,SPlus,Mathematica都有實現和特征向量的關系是的特征值對角陣U是的特征向量矩陣V是的特征向量矩陣就是PCA的那個旋轉矩陣E就可以用PowerIteration的方法解運用知：趙教師喜歡Matrix，給它評分為5，問：趙教師喜歡什么類型的片?qV計算，把趙教師投影到概念空間上運用給趙教師引薦什么片？把趙教師的概念向量qV，乘視頻的概念向量VT，得到引薦的視頻向量=[1.641.641.64-0.16-0.16]給他引薦<異形>運用尋覓和趙教師興趣一樣的人他們雖然看的是不同的片，但發(fā)現了他們的興趣一樣經過UI矩陣發(fā)現的SVD的問題結果難以解釋為什么這么多維？U和V很Dense！占空間多CURCUR正確地選擇行/列構造中間矩陣消除冗余的行/列緣起抑制SVD的問題M=CUR隨機找c行，組成C選行j的概率P(j)=其能量〔值的平方和〕/A的總能量選出后，除它能夠被挑上的次數的開方益處：好了解，C稀疏求UW是C和R的交集對它SVD：

Z+偽反〔pseudoinverse〕Z中的元素，假設是0，堅持不變；假設非0，取倒數性能[Drineasetal.]取行，列，就能在O(m*n)時間內，以概率獲得Drineasetal.,FastMonteCarloAlgorithmsforMatricesIII:ComputingaCompressedApproximateMatrixDecomposition,SIAMJournalonComputing,2006.冗余行/列的處置K列一樣扔掉K-1列，保管1列對這一列中的一切值，乘比較實驗DBLP作者數據作者–會議矩陣，論文數428K作者〔行〕，3659會議〔列〕做降維CPU時間準確度存儲空間：輸出矩陣中數值個數/輸入矩陣中數值個數性能比較Sun,Faloutsos:LessisMore:CompactMatrixDecompositionforLargeSparseGraphs,SDM’07.擴展SVD線性投影非線性方法/?AGlobalGeometricFrameworkforNonlinearDimensionalityReduction.J.B.Tenenbaum,V.deSilvaandJ.C.Langford.Science290(5500):