大數據存儲與處理概述課件

大數據存儲與應用

降維課程主頁：http:///?page_id=397陳一帥chenyishuai@大數據存儲與應用

降維1介紹為什么要降維？找出規(guī)律，壓縮數據量幾維？介紹為什么要降維？幾維？2降維看起來2維，其實1維看起來3維，其實2維降維看起來2維，其實1維看起來3維，其實2維3內容特征值與特征向量PCA（主元素分析）Principal-ComponentAnalysisSVD（奇異值分解）Singular-ValueDecompositionCUR分解內容特征值與特征向量4特征值與特征向量特征值與特征向量5特征值與特征向量定義計算方法PowerIteration尋找特征對（Eigenpairs）特征向量矩陣特征值與特征向量定義6定義M矩陣，λ常數，e非零列向量Me=λe唯一確定一個ee為unitvector第一個非零元素為正定義M矩陣，λ常數，e非零列向量7一般計算方法要，的行列式等于0求得λ然后通過Me=λe求e計算復雜度O(n3)一般計算方法要8PowerIteration方法任選一個向量X0遞歸誤差Frobeniusnorm足夠小時，停止這個Xk就是M的主特征向量然后通過Mx=λx求λx是一個單位向量：X-1=XTPowerIteration方法任選一個向量X09PowerIteration方法再找第二個特征對在M中去掉第一個主特征向量的因素然后類似計算PowerIteration方法再找第二個特征對10特征向量矩陣特征向量是單位向量特征向量之間正交特征向量矩陣E的特點特征向量矩陣特征向量是單位向量11PCAPCA12PCA事例使用特征向量進行降維距離矩陣PCA事例13原理將矩陣與一個正交單位向量矩陣相乘，意味著在歐式空間上的旋轉求的特征矩陣E，對高維數據進行旋轉原數據變成在新的坐標上的投影。新的坐標上，第一維是主特征向量指向的那個方向，能量最強以后依次遞減使降維成為可能原理將矩陣與一個正交單位向量矩陣相乘，意味著在歐式空間上的旋14原始數據按虛線旋轉逆時針45度旋轉對稱陣原始數據按虛線旋轉逆時針45度旋轉對稱陣15在新坐標系上的位置第一維的能量>第二維的能量，而且它們正交所以，如果要降到一維，無疑，應該保留第一維，把第二維去掉PCA在新坐標系上的位置第一維的能量>第二維的能量，而且它們正16SVDSVD17SVD定義降維應用計算SVD定義18定義r是A的Rank（秩）U：左奇異向量Leftsingularvectors單位正交矩陣

：奇異值Singularvalues對角陣，V：右奇異向量Rightsingularvectors單位正交矩陣定義r是A的Rank（秩）19例二維M的秩r=2科幻浪漫用戶–概念矩陣概念強度矩陣電影

–概念矩陣科幻浪漫科幻浪漫例二維科幻浪漫用戶–概念矩陣概念強度矩陣電影–概念20SVDSVD21用戶電影觀看矩陣科幻浪漫用戶–概念矩陣概念強度矩陣電影

–概念矩陣科幻浪漫科幻浪漫在實際中，U，V中沒有這么多0概念分得沒有這么清用戶電影觀看矩陣科幻浪漫用戶–概念矩陣概念強度矩陣電影22SVD的理解V是把電影按照用戶進行概念分類后的結果五部電影，投影到“科幻”“浪漫”兩個概念上SVD的理解V是把電影按照用戶進行概念分類后的結果23SVD的理解

是將用戶按照電影進行概念分類后的結果7個用戶，投影到“科幻”“浪漫”兩個概念上SVD的理解是將用戶按照電影24基于SVD的降維降概念強度最低那一維用戶–概念矩陣概念強度矩陣電影

–概念矩陣基于SVD的降維降概念強度最低那一維用戶–概念矩陣概念25降維結果誤差評估降維結果誤差評估26降維降維27證明為什么去掉最小的那一維，誤差最?。啃枰C明兩點如果M=PQR是M的SVD，有qii是Q對角線上的值，也就是證明為什么去掉最小的那一維，誤差最?。?8實踐中保持80～90%的能量計算復雜度看哪個小LINPACK,Matlab,SPlus,Mathematica都有實現實踐中保持80～90%的能量29和特征向量的關系

是的特征值對角陣U是的特征向量矩陣V是的特征向量矩陣就是PCA的那個旋轉矩陣E就可以用PowerIteration的方法解和特征向量的關系就可以用PowerIteration的方法30應用已知：趙老師喜歡Matrix，給它評分為5，問：趙老師喜歡什么類型的片?qV計算，把趙老師投影到概念空間上應用已知：趙老師喜歡Matrix，給它評分為5，31應用給趙老師推薦什么片？把趙老師的概念向量qV，乘視頻的概念向量VT，得到推薦的視頻向量

=[1.641.641.64-0.16-0.16]給他推薦《異形》應用給趙老師推薦什么片？32應用尋找和趙老師興趣相同的人他們雖然看的是不同的片，但發(fā)現了他們的興趣相同通過UI矩陣發(fā)現的應用尋找和趙老師興趣相同的人33SVD的問題結果難以解釋為什么這么多維？U和V很Dense！占空間多SVD的問題結果難以解釋34CURCUR35CUR正確地選擇行/列構造中間矩陣消除冗余的行/列CUR正確地選擇行/列36緣起克服SVD的問題M=CUR隨機找c行，組成C選行j的概率P(j)

=其能量（值的平方和）/A的總能量選出后，除它可能被挑上的次數的開方好處：好理解，C稀疏緣起克服SVD的問題37求UW是C和R的交集對它SVD：

Z+偽反（pseudoinverse）Z中的元素，如果是0，保持不變；如果非0，取倒數求UW是C和R的交集38性能[Drineasetal.]取行，列，就能在O(m*n)時間內，以概率

獲得Drineasetal.,FastMonteCarloAlgorithmsforMatricesIII:ComputingaCompressedApproximateMatrixDecomposition,SIAMJournalonComputing,2006.性能[Drineasetal.]39冗余行/列的處理K列相同扔掉K-1列，保留1列對這一列中的所有值，乘冗余行/列的處理K列相同40比較比較41實驗DBLP作者數據作者–會議矩陣，論文數428K作者（行），3659會議（列）做降維CPU時間準確度存儲空間：輸出矩陣中數值個數/輸入矩陣中數值個數實驗DBLP作者數據42性能比較Sun,Faloutsos:LessisMore:CompactMatrixDecompositionforLargeSparseGraphs,SDM’07.性能比較Sun,Faloutsos:LessisMo43擴展SVD線性投影非線性方法isomap./?AGlobalGeometricFrameworkforNonlinearDimensionalityReduction.J.B.Tenenbaum,V.deSilvaandJ.C.Langford.Science290(5500):2319-2323,給你698張人臉的圖像（64×64灰度），通過isomap降維方法將每張臉當做一個點映到二維平面上，使得橫坐標恰好反映人臉左右看的程度，縱坐標反映人臉上下看的程度。/littlestonelj/article/details/7534382擴展SVD44練習11.3.2練習11.3.245大數據存儲與應用

降維課程主頁：http:///?page_id=397陳一帥chenyishuai@大數據存儲與應用

降維46介紹為什么要降維？找出規(guī)律，壓縮數據量幾維？介紹為什么要降維？幾維？47降維看起來2維，其實1維看起來3維，其實2維降維看起來2維，其實1維看起來3維，其實2維48內容特征值與特征向量PCA（主元素分析）Principal-ComponentAnalysisSVD（奇異值分解）Singular-ValueDecompositionCUR分解內容特征值與特征向量49特征值與特征向量特征值與特征向量50特征值與特征向量定義計算方法PowerIteration尋找特征對（Eigenpairs）特征向量矩陣特征值與特征向量定義51定義M矩陣，λ常數，e非零列向量Me=λe唯一確定一個ee為unitvector第一個非零元素為正定義M矩陣，λ常數，e非零列向量52一般計算方法要，的行列式等于0求得λ然后通過Me=λe求e計算復雜度O(n3)一般計算方法要53PowerIteration方法任選一個向量X0遞歸誤差Frobeniusnorm足夠小時，停止這個Xk就是M的主特征向量然后通過Mx=λx求λx是一個單位向量：X-1=XTPowerIteration方法任選一個向量X054PowerIteration方法再找第二個特征對在M中去掉第一個主特征向量的因素然后類似計算PowerIteration方法再找第二個特征對55特征向量矩陣特征向量是單位向量特征向量之間正交特征向量矩陣E的特點特征向量矩陣特征向量是單位向量56PCAPCA57PCA事例使用特征向量進行降維距離矩陣PCA事例58原理將矩陣與一個正交單位向量矩陣相乘，意味著在歐式空間上的旋轉求的特征矩陣E，對高維數據進行旋轉原數據變成在新的坐標上的投影。新的坐標上，第一維是主特征向量指向的那個方向，能量最強以后依次遞減使降維成為可能原理將矩陣與一個正交單位向量矩陣相乘，意味著在歐式空間上的旋59原始數據按虛線旋轉逆時針45度旋轉對稱陣原始數據按虛線旋轉逆時針45度旋轉對稱陣60在新坐標系上的位置第一維的能量>第二維的能量，而且它們正交所以，如果要降到一維，無疑，應該保留第一維，把第二維去掉PCA在新坐標系上的位置第一維的能量>第二維的能量，而且它們正61SVDSVD62SVD定義降維應用計算SVD定義63定義r是A的Rank（秩）U：左奇異向量Leftsingularvectors單位正交矩陣

：奇異值Singularvalues對角陣，V：右奇異向量Rightsingularvectors單位正交矩陣定義r是A的Rank（秩）64例二維M的秩r=2科幻浪漫用戶–概念矩陣概念強度矩陣電影

–概念矩陣科幻浪漫科幻浪漫例二維科幻浪漫用戶–概念矩陣概念強度矩陣電影–概念65SVDSVD66用戶電影觀看矩陣科幻浪漫用戶–概念矩陣概念強度矩陣電影

–概念矩陣科幻浪漫科幻浪漫在實際中，U，V中沒有這么多0概念分得沒有這么清用戶電影觀看矩陣科幻浪漫用戶–概念矩陣概念強度矩陣電影67SVD的理解V是把電影按照用戶進行概念分類后的結果五部電影，投影到“科幻”“浪漫”兩個概念上SVD的理解V是把電影按照用戶進行概念分類后的結果68SVD的理解

是將用戶按照電影進行概念分類后的結果7個用戶，投影到“科幻”“浪漫”兩個概念上SVD的理解是將用戶按照電影69基于SVD的降維降概念強度最低那一維用戶–概念矩陣概念強度矩陣電影

–概念矩陣基于SVD的降維降概念強度最低那一維用戶–概念矩陣概念70降維結果誤差評估降維結果誤差評估71降維降維72證明為什么去掉最小的那一維，誤差最??？需要證明兩點如果M=PQR是M的SVD，有qii是Q對角線上的值，也就是證明為什么去掉最小的那一維，誤差最小？73實踐中保持80～90%的能量計算復雜度看哪個小LINPACK,Matlab,SPlus,Mathematica都有實現實踐中保持80～90%的能量74和特征向量的關系

是的特征值對角陣U是的特征向量矩陣V是的特征向量矩陣就是PCA的那個旋轉矩陣E就可以用PowerIteration的方法解和特征向量的關系就可以用PowerIteration的方法75應用已知：趙老師喜歡Matrix，給它評分為5，問：趙老師喜歡什么類型的片?qV計算，把趙老師投影到概念空間上應用已知：趙老師喜歡Matrix，給它評分為5，76應用給趙老師推薦什么片？把趙老師的概念向量qV，乘視頻的概念向量VT，得到推薦的視頻向量

=[1.641.641.64-0.16-0.16]給他推薦《異形》應用給趙老師推薦什么片？77應用尋找和趙老師興趣相同的人他們雖然看的是不同的片，但發(fā)現了他們的興趣相同通過UI矩陣發(fā)現的應用尋找和趙老師興趣相同的人78SVD的問題結果難以解釋為什么這么多維？U和V很Dense！占空間多SVD的問題結果難以解釋79CURCUR80CUR正確地選擇行/列構造中間矩陣消除冗余的行/列CUR正確地選擇行/列81緣起克服SVD的問題M=CUR隨機找c行，組成C選行j的概率P(j)

=其能量（值的平方和）/A的總能量選出后，除它可能被挑上的次數的開方好處：好理解，C稀疏緣起克服SVD的問題82求UW是C和R的交集對它SVD：

Z+偽反（pseudoinverse）Z中的元素，如果是0，保持不變；如果非0，取倒數求UW是C和R的交集83性能[Drineasetal.]取行，列，就能在O(m*n)時間內，以概率

獲得Drineasetal.,FastMont