機器學習-05-下-.ppt

機器學習第五講(下),多維數(shù)據處理與維度約簡,盧志茂,維度約簡,維度約簡,維度約簡概述（1） 多種稱謂 維度規(guī)約 dimensionality reduction 特征選擇 feature selection 特征提取 feature extraction,統(tǒng)稱 降維 降低維數(shù)，減少類別描述的特征數(shù)量,維度約簡,維度約簡概述（2） 輸入的空間 輸入輸出均為二元的情況,需要降維嗎？,維度約簡,維度約簡概述（3） 輸入的空間 神經網絡的輸入層,維度約簡,維度約簡概述（4） 降維的好處 理想情況下，降維不該是一個獨立過程 常被看做預處理過程加以考慮 降低算法計算復雜度 簡單模型，方差小，更魯棒 特征少，易解釋和學習 容易實現(xiàn)可視化,聽說過維數(shù)災難嗎？,嘭、嘭,維度約簡,維度約簡概述（5） 降維的可能性 特征描述存在冗余 特征變量相互依賴 對類別沒有表征能力 無關的、錯誤的、表現(xiàn)力弱的 高維空間向低維空間映射 多維信息的融合、混合、揉合,還記得數(shù)據表的主鍵嗎,單鍵、 組合鍵、 全鍵,維度約簡,維度約簡概述（6） 常用降維方法 特征選擇 從 d 維中找出能提供更多信息的 k 個維 子集選擇 subset selection 特征提取 通過變換，找出 k 個維的新組合 主成分分析 線性判別分析,維度約簡,子集選擇（1） 尋找最佳子集 最佳子集包括那些對正確率貢獻最大的屬性（特征） d 個變量有 2d 的個可能子集 只能在合理的時間找到一個合理的解 主要方法 向前選擇 forward selection 從空集開始添加使誤差降低最多的特征 向后選擇 backward selection 逐步刪除掉使誤差提高很小的特征,維度約簡,子集選擇（2） 順序向前選擇 sequential forward selection 處理思想 F, a feature set of input dimensions, xi, i = 1, . . . , d. E(F) denotes the error incurred on the validation sample when only the inputs in F are used. start with no features: F = . At each step, for all possible xi , we train our model on the training set and calculate E(Fxi) on the validation set,驗證集,維度約簡,子集選擇（3） 順序向前選擇 sequential forward selection 處理思想 Then, we choose that input xj that causes the least error E 不在減小，則停止 E 如果變化太小，也可以考慮提前停止,維度約簡,子集選擇（4） 順序向前選擇 sequential forward selection 該方法的復雜度分析 從 d 到 k train and test the system d+ (d 1) + (d 2) + + (d k) times, which is O(d2). 貪心策略，局部最優(yōu) 不能發(fā)現(xiàn)組合特征 一次可增加多個，但需更多計算量 也可回溯，考察是否要刪除某些已添加特征,維度約簡,子集選擇（5） 順序向后選擇 sequential backward selection 與添加特征向反，逐個刪除特征 改進策略與向前方法一樣 如果預料無效特征多，則向前方法更可取,考慮變化最小的特征,維度約簡,主成份分析Principal Components Analysis （1） 投影方法 project ion methods 從 d 維投影到 k (k d) 維輸入空間，并且信息損失最小 首先考慮，向 d 維向量 w 投影,高維空間的一條直線,注意： 都是標量,維度約簡,主成份分析（2） 投影方法 projection methods 向 d 向量 w 投影 每個樣本點的投影是一個 一維 點 d 維 正態(tài)分布在上的投影仍然是 一維 正態(tài)分布 推廣 W is a d k matrix with rank k d, then the k-dimensional WTx is k-variate normal（k 維正態(tài)分布） 投影到 k 個d 維向量，構成新的 k 維向量空間,維度約簡,主成份principal component分析（3） 是一種特征提取方法 無監(jiān)督方法 不依賴輸出（不用標記類別） 但需要最大化方差 選擇可以造成最大方差的特征 The principal component is w1 such that the sample, after projection on to w1, is most spread out so that the difference between the sample points becomes most apparent.（放大樣本之間的差別） 要求| w1| = 1 （單位向量） z1 = wT1 x 且 Cov(x) = ,維度約簡,主成份分析（4） 計算過程 用拉格朗日方法求極值 限制條件 對w1求導并令其為0，可以求解w1 w1 是矩陣 的特征向量， 是特征值（本征值） 為了使方差最大，選擇具有最大特征值的特征向量,特征向量形式 特征值分解,維度約簡,主成份分析（5） 計算過程 用拉格朗日方法求極值 依次計算第二個主成份 并要求與第一個主成分正交（不相關） w2求導并令其為0：,組成新的 坐標系,維度約簡,主成份分析（6） 計算過程 用拉格朗日方法求極值 依次計算第二個主成份 并要求與第一個主成分正交（不相關）,第一大的 特征值,維度約簡,主成份分析（7） 計算過程 w2 should be the eigenvector of with the second largest eigenvalue, 2 = . 其它主成份依次可求解,各維上的變量存在線性相關,降到了 k 維,維度約簡,主成份分析（8） 原點中心化 k columns of W are the k leading eigenvectors of S（the estimator to ）,坐標系旋轉,維度約簡,主成份分析（9） 討論 如何控制主成份的數(shù)量 S 是對角陣， 如果特征值都大于0，但如果 |S| 很小，對方差影響小，也可以舍棄 如果考慮貢獻在 90% 以上的方差的前 k 個主要成分 方差比例 proportion of variance 如果特征變量間高度相關，則看 kd, 維度壓縮比會很大 不相關，則 k = d,空間變換后，各維的特征變量是相互獨立的,d 是變量 可控制,維度約簡,斜坡圖（Scree graph）,(a) Scree graph. (b) Proportion of variance explained is given for the Optdigits dataset from the UCI Repository.,This is a handwritten digit dataset with ten classes and sixty-four dimensional inputs. The first twenty eigenvectors explain 90 percent of the variance.,維度約簡,如果前兩個主成份貢獻最大，可視化的情況,search visually for structure, groups, outliers, normality, and so forth,維度約簡,主成份分析（10） 來自譜分解的解釋 如何控制主成份的數(shù)量 S 是對角陣， 如果特征值都大于0，但如果 |S|,協(xié)方差矩陣,矩陣正交可逆,S 就是 對角陣,維度約簡,主成份分析（11） 來自譜分解 spectral decomposition 的解釋 如何控制主成份的數(shù)量,維度約簡,主成份分析（12） 實例分析 有一個班學生的五門課成績，要求對學生排序 如何解決 記總分？ 計算平均分？ 問題是如何突出五門成績之間的差別 引入PCA 計算最大特征值的特征向量 投影到具有最大的方差的特征向量上,空間變換 投影,維度約簡,線性判別式分析Linear discriminant analysis （1） 概述 用于分類的有指導降維方法 有別于 PCA 有監(jiān)督方法，需要 訓練樣本對應的輸出，而PCA是無監(jiān)督方法 PCA突出特征對樣本的有效表示 LDA側重類別之間的差別，效果通?；乇躊CA更好 應用十分廣泛的特征提取方法 與 PCA 一樣受重視 屬于降維的基本方法,維度約簡,線性判別式分析 (LDA)（2） 兩個類的問題 Given samples from two classes C1 and C2, we want to find the direction, as defined by a vector w, such that when the data are projected onto w, the examples from the two classes are as well separated as possible. As we saw before： z = wTx 從 d 維 到 一維 投影 如何尋找或確定向量 w 的方向 使誤差最小或者方差最小,在兩條不同的直線上投影差別,維度約簡,線性判別式分析 (LDA)（3） 兩個類的問題 確定 w m1 and m1 are the means of samples from C1 before and after projection, respectively. Note that m1 Rd and m1 R . We are given a sample X = xt, rt such that rt = 1 if xt C1 and rt = 0 if xt C2.,投到一維 變標量,標量,維度約簡,線性判別式分析 (LDA)（4） 兩個類的問題 確定 w The scatter（散布） of samples from C1 and C2 after projection are: 希望 |m1 m2| 大，s12 + s22 小,分散程度,維度約簡,線性判別式分析 (LDA)（5） 兩個類的問題 確定 w Fishers linear discriminant 最大化下式,投影到向量上，尋找理想的分界,維度約簡,線性判別式分析 (LDA)（6） 兩個類的問題 確定 w Fishers linear discriminant 重寫分子 定義SB 為類間散布矩陣（between-class scatter matrix.）,維度約簡,線性判別式分析 (LDA)（7） 兩個類的問題 確定 w Fishers linear discriminant 重寫分母,維度約簡,線性判別式分析 (LDA)（8） 兩個類的問題 確定 w Fishers linear discriminant 重寫分母,維度約簡,線性判別式分析 (LDA)（9） 兩個類的問題 確定 w Fishers linear discriminant 判別式改寫 對 w 微分，并令其為0,維度約簡,線性判別式分析 (LDA)（10） 兩個類的問題 確定 w Fishers linear discriminant 方程的解 當 ， 有判別式：,已被證明,維度約簡,線性判別式分析 (LDA)（11） 推廣到多類問題 對于 K 個類的情況 需要K-1個判別式 二類問題需要一個判別式 需要向 K-1 個 d 維矢量投影（需要 K-1條直線，K-1個分界） 由這些向量作為列向量組成矩陣 W X 向 W 投影 z 是 k 維，W 是 d k.,維度約簡,線性判別式分析 (LDA)（12） 推廣到多類問題 對于 K 個類的情況 Ci 的類內散布矩陣,維度約簡,線性判別式分析 (LDA)（13） 推廣