大數(shù)據(jù)存儲(chǔ)與處理

大數(shù)據(jù)存儲(chǔ)與運(yùn)用

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

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