特徵降維&特徵選擇

在實際應用中，當特徵個數增加到某一個臨界點後，繼續增加反而會導致分類器的性能變差——「維度災難」（curse of dimensionality）。

其可能的原因有：

假設的概率模型與真實模型不匹配
訓練樣本個數有限，導致概率分布的估計不準
……

對於高維數據，「維度災難」使解決模式識別問題非常困難，此時，往往要求首先降低特徵向量的維度。

降低特徵向量維度的可行性分析：

特徵向量往往是包含冗餘信息的！
有些特徵可能與分類問題無關
特徵之間存在著很強的相關性

降低維度的方法

?特徵組合：把幾個特徵組合在一起，形成新的特徵

?特徵選擇：選擇現有特徵集的一個子集

針對不同的訓練目標有不同的訓練演算法：

?最小化重構誤差（主成分分析，PCA）

?最大化類別可分性（線性判別分析，LDA）

?最小化分類誤差（判別訓練，discriminative training）

?保留最多細節的投影（投影尋蹤，projection pursuit）

?最大限度的使各特徵之間獨立（獨立成分分析，ICA）

在特徵組合的方法中，本文將主要介紹PCA演算法和LDA演算法。

首先是，主成分分析（PCA）。

考慮用一維向量表示ｄ維樣本：用通過樣本均值m的直線（單位向量為e）上的點表示樣本

這裡，唯一決定了。

最小化平方重構誤差：

表示( )在e上的投影，如圖所示：

尋找e的最優方向：

其中，S表示散布矩陣：

$S=sum_{k=1}^n(x_k-m)(x_k-m)^t$

尋找使最大化得，可以使用拉格朗日乘子法（約束條件是）：

$frac{partial u}{partial e}=2Se-2lambda e=0$

, 其中λ是S的特徵值，e是S的特徵向量。

，最大特徵值λ對應的的最大值。

得到結論：e為散布矩陣最大的本徵值對應的本徵向量。

將一維的 擴展到d(d≤d)維空間

用 $y=egin{pmatrix} a_{k1} \ a_{k2} \ ...\ a_{kd} end{pmatrix}$ 表示， $x_k=m+sum_{i=1}^{d}a_{ki}e_i$ 。

最小化平方誤差

$J_d(e)=sum_{k=1}^{n}||(m+sum_{i=1}^{d}a_{ki}e_i)-x_k||^2$

結論：

使得平方誤差最小的向量 $e_1,e_2,...,e_{d}$ 分別為散布矩陣S的d個最大本徵值對應的本徵向量。
S為實對稱矩陣，所以 $e_1,e_2,...,e_{d}$ 相互正交。
$e_1,e_2,...,e_{d}$ 可被視為特徵空間的一個子空間的單位向量基
$a_{ki}$ 為對應於基的係數，或在的投影。
$a_{ki}$ 稱為主成分（principal component）。
幾何意義： $e_1,e_2,...,e_{d}$ 為沿數據云團方差最大的方向的直線。

利用PCA，可以將d維數據降維到d(d≤d)維，同時使得降維後的數據與源數據的平方誤差最小。

主成分分析的步驟：

計算散布矩陣S： $S=sum_{k=1}^n(x_k-m)(x_k-m)^t$
計算S的特徵值和特徵向量：
將本徵向量按相應的本徵值從大到小排序。
選擇最大的d』個本徵向量作為投影向量 $e_1,e_2,...,e_{d}$ ，構成投影d*d的矩陣W，其中第i列為。
對任意d維樣本x，其用PCA降維後的d』維向量為。

使用python實現PCA演算法：

def pca(dataMat, topNfeat=9999999): meanVals = mean(dataMat, axis=0) meanRemoved = dataMat - meanVals #remove mean covMat = cov(meanRemoved, rowvar=0) eigVals,eigVects = linalg.eig(mat(covMat)) eigValInd = argsort(eigVals) #sort, sort goes smallest to largest eigValInd = eigValInd[:-(topNfeat+1):-1] #cut off unwanted dimensions redEigVects = eigVects[:,eigValInd] #reorganize eig vects largest to smallest lowDDataMat = meanRemoved * redEigVects#transform data into new dimensions reconMat = (lowDDataMat * redEigVects.T) + meanVals return lowDDataMat, reconMat

通常，最大的幾個本徵值佔據了所有本徵值之和的絕大部分，少數幾個最大本徵值對應的本徵向量即可表示原數據中的絕大部分信息，而剩下的小部分（即對應較小的本徵值的本徵向量所表示的信息），通常可以認為是數據雜訊而丟掉。

PCA中對散布矩陣S的本徵值分解計算量較大，如特徵向量維度較高，直接對S進行本徵值分解十分困難。以圖像為例，100*100像素的圖像的散布矩陣的維度為10000*10000。對10000*10000的矩陣進行分解的空間複雜度和時間複雜度都是無法接受的。

一個解決方案是：不直接對S進行本徵值分解，而利用SVD對一個較小的矩陣進行本徵值分解。

利用SVD簡化S的本徵值分解

散布矩陣 $S=sum_{k=1}^n(x_k-m_)(x_k-m)^t=AA^Tin R^{d imes d}$

其中， $A=[x_1-m,x_2-m,...,x_n-m]in R^{d imes n}$

令 $R=A^TAin d^{n imes n}$ ,若d>n，則對R進行本徵值分解要比直接對S進行本徵值分解快。

例如，對絕大多數圖像訓練集來講，圖像的像素數要遠遠大於訓練集中的樣本個數，即。

為了方便計算特徵值分解，這裡給出SVD定理。

設A是一個秩為n的矩陣，則存在兩個正交矩陣：

$U=[u_1,u_2,...,u_n]in R^{d imes n}$ ,

$V=[v_1,v_2,...,v_n]in R^{n imes n}$ ,

以及對角矩陣 $Lambda=diag[lambda_1,lambda_2,...,lambda_n]in R^{n imes n}$ , ,滿足： $A=ULambda^{frac{1}{2}}V^T$ 。其中為矩陣和的非零本徵值，和分別是矩陣和對應於的本徵向量。該分解稱為奇異值分解（Singular Value Decomposition，SVD）， $sqrt{lambda_i}$ 是A的奇異值。

對R進行特徵值分解：

本徵值：

本徵向量：

由 $A=ULambda^{frac{1}{2}}V^T$ 得 $U=AVLambda^{-frac{1}{2}}$

得出的本徵向量為： $u_i=frac{1}{sqrt{lambda_i}}Av_i$ 。

上式表示， d*d 矩陣的本徵值可以分解轉換成 n*n 矩陣的本徵值分解。

除此之外，我們還可以利用SVD方法做隱形語義索引（latent Semantic Indexing,LSI)和推薦系統。在推薦系統中，可以將奇異值想像成一個新空間，該新空間的維度與主題的個數有關，可以將矩陣U和矩陣V映射到奇異值空間中。另外，在科學和工程中，一直存在這樣一個普遍事實：在某個奇異值的個數之後，其他的奇異值均置為0。這意味著數據集中僅有r個重要特徵，而其餘的特徵都是雜訊或冗餘特徵。

這裡，以餐館菜肴推薦引擎為例，給出SVD演算法：

def standEst(dataMat, user, simMeas, item): n = shape(dataMat)[1] simTotal = 0.0; ratSimTotal = 0.0 for j in range(n): userRating = dataMat[user,j] if userRating == 0: continue overLap = nonzero(logical_and(dataMat[:,item].A>0, dataMat[:,j].A>0))[0] if len(overLap) == 0: similarity = 0 else: similarity = simMeas(dataMat[overLap,item], dataMat[overLap,j]) print the %d and %d similarity is: %f % (item, j, similarity) simTotal += similarity ratSimTotal += similarity * userRating if simTotal == 0: return 0 else: return ratSimTotal/simTotal

def svdEst(dataMat, user, simMeas, item):
n = shape(dataMat)[1]
simTotal = 0.0; ratSimTotal = 0.0
U,Sigma,VT = la.svd(dataMat)
Sig4 = mat(eye(4)*Sigma[:4]) #arrange Sig4 into a diagonal matrix
xformedItems = dataMat.T * U[:,:4] * Sig4.I #create transformed items
for j in range(n):
userRating = dataMat[user,j]
if userRating == 0 or j==item: continue
similarity = simMeas(xformedItems[item,:].T,
xformedItems[j,:].T)
print the %d and %d similarity is: %f % (item, j, similarity)
simTotal += similarity
ratSimTotal += similarity * userRating
if simTotal == 0: return 0
else: return ratSimTotal/simTotal

def recommend(dataMat, user, N=3, simMeas=cosSim, estMethod=standEst):
unratedItems = nonzero(dataMat[user,:].A==0)[1]#find unrated items
if len(unratedItems) == 0: return you rated everything
itemScores = []
for item in unratedItems:
estimatedScore = estMethod(dataMat, user, simMeas, item)
itemScores.append((item, estimatedScore))
return sorted(itemScores, key=lambda jj: jj[1], reverse=True)[:N]

下一個主題是Fisher線性判別分析。

PCA方法尋找用來有效表示數據（從最小平方誤差的意義上講）的主軸方向，而線性判別分析（linear discriminant analysis, LDA）尋找的是用來有效分類的方向。

假設：

n個d維樣本，他們分屬兩個類別和。其中，個屬於類別的樣本組成樣本子集，個屬於類別的樣本組成樣本子集。單位向量w方向上的投影為，投影點根據源數據的類別也分成兩個子集和。

?目標：

投影到w上後，投影點更易分類，這要求不同類的投影點盡量分開，並且同一類的投影點盡量靠近。

從不同類的投影點盡量分開角度來看：

設為第i類的樣本均值，則 $m_i=frac{1}{n_i}sum_{xin D_i}x$

則投影后的兩類樣本均值之間的距離為： $m_i =frac{1}{n_i}sum_{yin Y_i}y=frac{1}{n_i}sum_{xin D_i}w^tx=w^tm_i$

投影后的兩類樣本均值之間的距離為： ,此距離越大，說明兩類投影點分的越開。

從同一類的投影點盡量靠近角度來看：

投影內的散布： $s_i=sum_{yin Y_i}(y-m_i)^2$ ，各類的投影內散布之和為：。此總類內散布體現了投影后類內的「緊緻」程度，其越小，說明同一類內的投影點越靠近。

根據上面兩個角度，引出Fisher準則函數：

$J(w)=frac{|m_1-m_2|^2}{s_1^2+s_2^2}$

最大化J(w)即使得類間差距（分子）最大化同時類內差距（分母）最小化。

將J(w)表示為w的函數：

原始數據空間內的散布函數矩陣為： $S_i=sum_{xin D_i}(x-m_i)(x-m_i)^t$ ,總類內散布矩陣為。

則： $s_i^2=sum_{xin D_i}(w^tx-w^tm_i)^2=sum_{xin D_i}w^t(x-m_i)(x-m_i)^tw=w^tS_iw$

原始數據空間空間總類間散布矩陣為：

則：

故：

$J(w)=frac{w^tS_Bw}{w^tS_Ww}$

Fisher準則函數最大化，w需滿足： (廣義本徵值問題)

若非奇異，有 $S_W^{-1}S_Bw=lambda w$ (普通本徵值問題)

將二元分類問題推廣到多元問題：

總類內散布矩陣：

$m_i=frac{1}{n_i}sum_{xin D_i}x$

$S_i=sum_{xin D_i}(x-m_i)(x-m_i)^t$

$S_W=sum_{i=1}^{c}S_i$

總體均值向量：

$m=frac{1}{n}sum_{x}x=frac{1}{n}sum_{i=1}^{c}n_im_i$

總體散布矩陣：

$S_T=sum_{x}(x-m)(x-m)^t$

代入得：

$S_T=sum_{i=1}^csum_{xin D_i}(x-m_i+m_i-m)(x-m_i+m_i-m)^t$

$=sum_{i=1}^csum_{xin D_i}(x-m_i)(x-m_i)^t+sum_{i=1}^csum_{xin D_i}(m_i-m)(m_i-m)^t$

$=S_W+sum_{i=1}^cn_i(m_i-m)(m_i-m)^t$

這裡，在化簡的過程中有 $sum_{xin D_i}(x-m_i)(m_i-m)^t$ 。另外 $sum_{i=1}^cn_i(m_i-m)(m_i-m)^t$ 表示類間散布矩陣。

所以，有。

記投影為：。

由W張成的投影子空間中有：

$m_i==frac{1}{n_i}sum_{yin Y_i}y$

$m=frac{1}{n}sum_{i=1}^nn_im_i$

$S_W=sum_{i=1}^csum_{yin Y_i}(y-m_i)(y-m_i)^t$

$S_B=sum_{i=1}^cn_i(m_i-m)(m_i-m)^t$

將代入得到：

求能夠最有效分類的W：使得類間離散度和類內離散度的比值最大。

準則函數為：

$J(W)=frac{|S_B|}{|S_W|}=frac{|W^tS_BW|}{|W^tS_WW|}$

使J(W)最大化的W的列向量由如下廣義本徵值問題中最大本徵值對應的本徵向量組成:

這裡，為c個秩為1或0的矩陣之和，其中只有c-1個矩陣相互獨立，所以的秩不大於c-1。原因：。

所以如上廣義本徵值問題最多有c-1個非零本徵值，對應c-1個本徵向量，所以W最多有c-1列。

接下來討論特徵選擇的問題。

特徵選擇中將選擇特徵集的一個子集。

特徵選擇方法包含兩個主要組成部分：其一是搜索過程，其二是選擇準則。

搜索過程是在所有候選特徵子集中進行系統搜索的過程，原則上，窮盡搜索（exhaustive search）即能夠找到最優子集。實踐中，往往採用更高效的非窮盡搜索演算法，找到次優解。

選擇準則用於判斷某個特徵子集是否優於另一個特徵子集的標準，原則上，選擇準則即為系統性能的評價準則，如分類錯誤率等。實踐中，往往採用簡化的選擇準則。

首先討論搜索過程，在本文中主要涉及循序向前選擇法（Sequential Forward Selection，SFS）和循序向後選擇法（Sequential Backward Selection，SBS）。

在SFS中，首先，最好的單個特徵被選出；然後，用所有其他特徵與第一個選出的特徵組合成候選特徵對，找出最好的一對；再用剩下的特徵分別與上一步選出的最好特徵對組成候選特徵三元組，找出最好的三元組；該過程直到選出足夠多的特徵停止。

很顯然，當單個特徵區分力很差，但兩個特徵結合區分力強時，SFS失效。一部分原因是最優子集中的每個特徵分別單獨考慮時，並不一定都為最優。

在SBS中，首先，選擇所有d個特徵；然後，從所有特徵中任意去掉一個形成d個候選的d-1特徵集，從中選出最好的一個；再從上一步得到的d-1特徵集中任意去掉一個特徵形成d-1個d-2特徵集，從中選出最好的一個；該過程直到特徵集中的特徵個數到達預先設定的值時停止。

因為SBS考慮的特徵數目大於等於期望的特徵數目，所以SBS通常比SFS需要更多的選擇準則計算。

當然還有其他的搜索過程，比如說單個最佳特徵子集。該搜索過程直接搜索最佳的單個特徵（每次僅用一個特徵，計算選擇準則），用它們構成的集合作為特徵選擇結果。顯然，雖然簡單，但是往往不可靠，只有當各特徵之間完全獨立的情況下能找到最優特徵子集。

接著討論選擇準則。

理想的方法是：用選定的特徵子集表示訓練樣本，訓練分類器，然後測試該分類器的泛化誤差（如採用交叉驗證等方法）。因為該方法對每個特徵子集都需要訓練一個分類器，因此計算量很大。我們可以採用簡化的方法：定義某種類內距離度量來描述採用某個特徵子集時的類可分度。該方法不需要為每個特徵子集訓練一個分類器，因此計算量較小。

關於類內距離度量，可以使用類內散布度以及均方距離的方法。