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

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

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

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

4、分別為O(nm)和O(nm)+O(nkp)，其中n，k，m，p分別為核矩陣的秩、需提取的主成分數(shù)、樣本數(shù)以及迭代次數(shù)。在大規(guī)模數(shù)據(jù)集的情況下，核矩陣的秩和要提取的主成分數(shù)通常遠小于樣本數(shù)，因此空間和時間復雜度都有較大程度的降低。
　　 ●利用核矩陣的對稱性質，基于初始核矩陣創(chuàng)建一個新的Gram-power-矩陣，因為新矩陣和原核矩陣具有相同的特征向量，可以計算Gram-Power矩陣的特征向量來代替核矩陣的特征分解，把核矩陣的每

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