大規(guī)模數(shù)據(jù)集下核方法的技術(shù)研究.pdf

1、主成分分析(Principal Component Analysis)是一種用于特征提取和降維的線性方法，它一般使用具有較大方差的維作為主成分而忽略方差小的維，從而將數(shù)據(jù)映射到低維的子空間中提取線性特征。但是當(dāng)數(shù)據(jù)是線性不可分的情況下，該方法不能很好地提取判別特征，通常使用核方法把數(shù)據(jù)映射到高維特征空間進(jìn)行主成分的運(yùn)算，即核主成分分析(Kernel Principal Component Analysis)，該過程不需要顯式地知道映射函

2、數(shù)，而是利用核技巧實(shí)現(xiàn)，提取的非線性特征被成功應(yīng)用于圖像處理等任務(wù)中。在核主成分計(jì)算過程中，需要儲存全部數(shù)據(jù)集生成的核矩陣，該矩陣是通過核函數(shù)計(jì)算數(shù)據(jù)之間的內(nèi)積而得到的，矩陣的大小隨著數(shù)據(jù)集樣本數(shù)目m變化而變化，空間復(fù)雜度為O(m2)，而對核矩陣進(jìn)行特征分解的時(shí)間復(fù)雜度為O(m2)。在大規(guī)模數(shù)據(jù)集的情況下，由于內(nèi)存容量的限制，在一般計(jì)算機(jī)上對核矩陣的存儲和計(jì)算都是困難的，應(yīng)尋找可行的解決方法。
　　 在深入研究模式分析中核方法相

3、關(guān)技術(shù)的基礎(chǔ)上，本文針對大規(guī)模數(shù)據(jù)集問題，探討了已有解決方法的實(shí)質(zhì)以及相互之間的關(guān)系，提出了三種有效的求解核主成分的方法，具體內(nèi)容包括：
　　 ●使用incomplete Cholesky分解將核矩陣轉(zhuǎn)化為兩個(gè)互為轉(zhuǎn)置的三角矩陣，三角矩陣的每一列可以看作為特征空間特殊的“輸入樣本”，將這些樣本輸入到主成分分析的迭代算法中，經(jīng)過若干次迭代后，就可以計(jì)算出核主成分。
　　 該方法不需要對核矩陣進(jìn)行特征分解，其空間和時(shí)間復(fù)雜度

4、分別為O(nm)和O(nm)+O(nkp)，其中n，k，m，p分別為核矩陣的秩、需提取的主成分?jǐn)?shù)、樣本數(shù)以及迭代次數(shù)。在大規(guī)模數(shù)據(jù)集的情況下，核矩陣的秩和要提取的主成分?jǐn)?shù)通常遠(yuǎn)小于樣本數(shù)，因此空間和時(shí)間復(fù)雜度都有較大程度的降低。
　　 ●利用核矩陣的對稱性質(zhì)，基于初始核矩陣創(chuàng)建一個(gè)新的Gram-power-矩陣，因?yàn)樾戮仃嚭驮司仃嚲哂邢嗤奶卣飨蛄?，可以?jì)算Gram-Power矩陣的特征向量來代替核矩陣的特征分解，把核矩陣的每

5、一列看成是迭代主成分分析算法的“輸入樣本”，經(jīng)過若干次迭代后，可以很容易的求出核主成分，并且算法的空間復(fù)雜度從O(m2)減少到O(m)。
　　 ●提出了一個(gè)基于矩陣的核主成分分析(Matrix-based Kernel PrincipalComponent Analysis)方法，該方法首先將大規(guī)模數(shù)據(jù)集等分成許多小的數(shù)據(jù)子集，每個(gè)數(shù)據(jù)子集的自相關(guān)矩陣可以看成是核空間的“特殊樣本”，用一個(gè)基于矩陣的創(chuàng)新核函數(shù)來計(jì)算數(shù)據(jù)子集之間的