機(jī)器學(xué)習(xí)-05-下-.ppt

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