大數據存儲與應用

降維課程主頁：httppage_id=397陳一帥介紹為什么要降維？找出規律，壓縮數據量幾維？降維看起來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]給他推薦《異形》應用尋找和趙老老師興趣相相同的人他們雖然看看的是不同同的片，但但發現了他他們的興趣趣相同通過UI矩陣發現的的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線性投影非線性方法法isomap./?AGlobalGeometricFrameworkforNonlinearDimensionalityReduction.J.B.Tenenbaum,V.deSilvaandJ.C.Langford.Science290(5500)