文章目錄
- 一、凸優化
- 1.1 仿射集:（直線）
- 1.2 凸集:（線段）
- 1.3 錐定義（射線）
- 1.4 凸優化
- 1.5 示例
- 二、SVD分解
- 2.1 奇異值分解
- 2.2 SVD概念及了解
- 三、PCA—主成分分析
- 3.1 PCA的概念
- 3.2 協方差和散度矩陣
- 3.3 基于特征值分解協方差矩陣實作PCA算法
- 3.4 基于SVD分解協方差矩陣實作PCA算法
一、凸優化
兩個正數的算術平均數大于等于幾何平均數：
給定可逆對稱陣Q，對于任意的向量x，y，有：
1.1 仿射集:（直線）
通過集合C中任意兩個不同點的直線仍然在集合C内，則稱集合C為仿射集。
1.2 凸集:（線段）
如果通過集合C中任意兩個不同點之間的線段(上的任何點)仍在集合C中，那麼稱集合C是凸的。
1.3 錐定義（射線）
給定 稱之為錐。
凸錐（convex cone）：
都成立，那麼稱集合C 為凸錐。顯然凸錐是錐的一種。
1.4 凸優化
若函數f的定義域domf 為凸集，且滿足：
拉格朗日乘子法就是求函數 在限制條件 下的極值的方法：
1.5 示例
求橢球的内接最大體積 :
由拉格朗日函數F(x):(λk是各個限制的待定系數)
二、SVD分解
奇異值分解能夠簡約資料，去除噪聲和備援資料。其實也是一種降維方法，将資料映射到低維空間。
奇異值分解（singular value decomposition，SVD）是線性代數中一種重要的矩陣分解，在信号處理、統計學等領域有重要應用。
假設 是一個 階矩陣，其中的元素全部屬于域 ，也就是實數域或複數域。如此則存在一個分解使得
其中 是 階矩陣； 是 階非負實數對角矩陣；而 為矩陣 的共轭轉置矩陣，是 階矩陣。這樣的分解就稱為矩陣 奇異值分解。
2.1 奇異值分解
- 分别了解計算 和
-
的特征向量組成
的特征向量組成
-
對和的非零特征值求平方根，對應上述的特征向量的位置，填入的非零對角元素（即 M 的奇異值）。
求特征值 與特征向量。由定義；是以 。
即：
求行列式det得：
特征值λ：。
将特征值帶入原方程 M ，可解的特征向量。
當
當 = 29.866
當 = 0.134
2.2 SVD概念及了解
在實數内，我們實質上是将一個複雜的變換 分解成了三個變換：
旋轉/鏡像 ；
縮放 ；
旋轉/鏡像 。
我們假設 以及 和
- 首先将（可能是退化的）機關球旋轉（旋轉标準正交基），
- 而後經由将機關圓縮放拉伸成橢圓（超空間中的超橢球），
-
再經由将超橢球在空間中旋轉。
這個超橢球的各個半軸的長度， 就是矩陣的奇異值，也就是矩陣
SVD 分解至少有兩方面作用：
分析了解
原矩陣的主要特征和攜帶的資訊（取若幹最大的奇異值），這引出了主成分分析（PCA）；
丢棄忽略原矩陣的次要特征和攜帶的次要資訊（丢棄若幹較小的奇異值），這引出了資訊有損壓縮、矩陣低秩近似等話題。
三、PCA—主成分分析
關于PCA粗略認識請檢視：特征工程——資料降維 降維就是一種對高次元特征資料預處理方法。降維是将高次元的資料保留下最重要的一些特征，去除噪聲和不重要的特征，進而實作提升資料處理速度的目的。
在實際的生産和應用中，降維在一定的資訊損失範圍内，可以為我們節省大量的時間和成本。降維也成為應用非常廣泛的資料預處理方法。
降維具有如下一些優點：
- 使得資料集更易使用。
- 降低算法的計算開銷。
- 去除噪聲。
- 使得結果容易了解。
降維的算法有很多，比如奇異值分解(SVD)、主成分分析(PCA)、因子分析(FA)、獨立成分分析(ICA)。
3.1 PCA的概念
PCA(Principal Component Analysis)，即主成分分析方法，是一種使用最廣泛的資料降維算法。
PCA的主要思想是将n維特征映射到k維上，這k維是全新的正交特征也被稱為主成分，是在原有n維特征的基礎上重新構造出來的k維特征。PCA的工作就是從原始的空間中順序地找一組互相正交的坐标軸，新的坐标軸的選擇與資料本身是密切相關的。其中，第一個新坐标軸選擇是原始資料中方差最大的方向，第二個新坐标軸選取是與第一個坐标軸正交的平面中使得方差最大的，第三個軸是與第1,2個軸正交的平面中方差最大的。依次類推，可以得到n個這樣的坐标軸。通過這種方式獲得的新的坐标軸，我們發現，大部分方差都包含在前面k個坐标軸中，後面的坐标軸所含的方差幾乎為0。于是，我們可以忽略餘下的坐标軸，隻保留前面k個含有絕大部分方差的坐标軸。事實上，這相當于隻保留包含絕大部分方差的次元特征，而忽略包含方差幾乎為0的特征次元，實作對資料特征的降維處理。
簡而言之：通過計算資料矩陣的協方差矩陣，然後得到協方差矩陣的特征值特征向量，選擇特征值最大(即方差最大)的k個特征所對應的特征向量組成的矩陣。這樣就可以将資料矩陣轉換到新的空間當中，實作資料特征的降維。
基于 特征值分解協方差矩陣實作PCA算法
基于 SVD分解協方差矩陣實作PCA算法。
3.2 協方差和散度矩陣
樣本均值：
樣本方差：
樣本 和樣本 的協方差：
- 協方差要求樣本必須至少滿足二維特征；方差隻是協方差的特殊情況。
- 方差和協方差的除數是n-1,這是為了得到方差和協方差的無偏估計。
- 協方差為正時，說明X和Y是正相關關系；
- 協方差為負時，說明X和Y是負相關關系；
- 協方差為0時，說明X和Y無相關關系。Cov(X,X)就是X的方差。當樣本是n維資料時，它們的協方差實際上是協方差矩陣(對稱方陣)。
同理，對于3維資料(x,y,z)，計算它的協方差就是：
散度矩陣定義為：
對于資料X的散度矩陣為。其實協方差矩陣和散度矩陣關系密切，散度矩陣就是協方差矩陣乘以（總資料量-1）。是以它們的特征值和特征向量是一樣的。這裡值得注意的是，散度矩陣是SVD奇異值分解的一步，是以PCA和SVD是有很大聯系。
3.3 基于特征值分解協方差矩陣實作PCA算法
資料集，需要降到 k 維。
- 去中心化，即每一位特征減去各自的平均值。、
- 計算協方差矩陣, 注：這裡除或不除樣本數量n或n-1,其實對求出的特征向量沒有影響。
- 用特征值分解方法求協方差矩陣
- 對特征值從大到小排序，選擇其中最大的個。然後将其對應的個特征向量分别作為行向量組成特征向量矩陣。
- 将資料轉換到個特征向量建構的新空間中，即。
關于PCA數學原理：http://blog.codinglabs.org/articles/pca-tutorial.html
為什麼用特征值分解矩陣，是因為
舉例：
我們用PCA方法将這兩行資料降到一行：
- 顯然：X矩陣的每行已經是零均值，是以不需要去平均值。
- 求協方差矩陣：
-
求協方差矩陣的特征值與特征向量。
特征值為： 特征向量為：
其中對應的特征向量分别是一個通解，和可以取任意實數。
那麼标準化後的特征向量為：
- 矩陣為：
-
最後我們用P的第一行乘以資料矩陣X，就得到了降維後的表示：
結果如圖所示：
- 注意：如果我們通過特征值分解協方差矩陣，那麼我們隻能得到一個方向的PCA降維。這個方向就是對資料矩陣X從行(或列)方向上壓縮降維。
3.4 基于SVD分解協方差矩陣實作PCA算法
在PCA降維中，我們需要找到樣本協方差矩陣 的最大k個特征向量，然後用這最大的k個特征向量組成的矩陣來做低維投影降維。可以看出，在這個過程中需要先求出協方差矩陣
- 有一些SVD的實作算法可以先不求出協方差矩陣
- 注意到PCA僅僅使用了我們SVD的左奇異矩陣，沒有使用到右奇異值矩陣，那麼右奇異值矩陣有什麼用呢？