機(jī)器學(xué)習(xí)及應(yīng)用第9章-降維課件

1、第09章 降維k-近鄰學(xué)習(xí)主成分分析低維嵌入SVD分解9.1 引言降維（Dimensionality Reduction，DR）是指采用線性或者非線性的映射方法將高維空間的樣本映射到低維空間中。降維獲得低維空間下的數(shù)據(jù)等價(jià)表示，實(shí)現(xiàn)高維數(shù)據(jù)的可視化呈現(xiàn)。等價(jià)的低維數(shù)據(jù)更方便存儲(chǔ)、處理、計(jì)算和使用。降維能夠去除數(shù)據(jù)噪聲、降低算法開銷。降維還可應(yīng)用于文本分類和數(shù)據(jù)壓縮等領(lǐng)域。降維可以得到原始數(shù)據(jù)的簡(jiǎn)化表示以加速后續(xù)處理或者改進(jìn)輸出結(jié)果，因此它已經(jīng)成為很多算法數(shù)據(jù)進(jìn)行預(yù)處理的重要手段。9.1.1 降維的概念9.1 引言9.1 引言降維方法可分為線性降維和非線性降維兩大類。線性降維假設(shè)構(gòu)成數(shù)據(jù)集的各變

2、量間獨(dú)立無關(guān)。 主成分分析（Principal Component Analysis，PCA） 獨(dú)立成分分析（Independent Component Analysis，ICA） 線性判別分析（Linear Discriminant Analysis，LDA）非線性降維方法，也稱之為流形學(xué)習(xí)方法（Manifold Learning），其目標(biāo)是從高維采樣數(shù)據(jù)中恢復(fù)低維流形結(jié)構(gòu)，不改變數(shù)據(jù)本身的拓?fù)涮匦浴?基于保持全局結(jié)構(gòu)信息，如等距離映射算法ISOMAP 關(guān)注局部結(jié)構(gòu)信息，如LLE、LE、HLLE9.1.2 常見算法分類9.2 k-近鄰學(xué)習(xí)k-近鄰(k-Nearest Neighbor，kNN

3、)：給定一個(gè)訓(xùn)練數(shù)據(jù)集，對(duì)新的輸入實(shí)例，在訓(xùn)練數(shù)據(jù)集中找到與該實(shí)例最鄰近的k個(gè)實(shí)例，即k個(gè)鄰居。如果這k個(gè)實(shí)例的多數(shù)屬于某個(gè)類，就把該輸入實(shí)例分類到這個(gè)類中。9.2.1 算法實(shí)現(xiàn)kNN算法計(jì)算流程如下: 計(jì)算每個(gè)樣本點(diǎn)與測(cè)試點(diǎn)的距離； 排序后取距離值最小的k個(gè)樣本點(diǎn)作為k-近鄰； 獲取k-近鄰的分類標(biāo)簽并計(jì)算各分類出現(xiàn)的次數(shù)； 找出出現(xiàn)次數(shù)最多的分類，返回該值作為測(cè)試點(diǎn)的分類結(jié)果。9.2 k-近鄰學(xué)習(xí)實(shí)例代碼 9.2 k-近鄰學(xué)習(xí)運(yùn)行效果：左下角兩個(gè)點(diǎn)屬于B類用藍(lán)色點(diǎn)標(biāo)識(shí)，右上角兩個(gè)點(diǎn)屬于A類用紅色標(biāo)識(shí)。取k值為3時(shí)通過kNN算法計(jì)算，距離測(cè)試點(diǎn)（0.2, 0.1）最近的三個(gè)點(diǎn)中的兩個(gè)點(diǎn)都是藍(lán)

4、色，因此測(cè)試點(diǎn)也是藍(lán)色，屬于B類。這樣的實(shí)現(xiàn)方式適合樣本數(shù)量和特征數(shù)量比較少的情況。假設(shè)樣本數(shù)量為N、特征數(shù)量為M，該算法時(shí)間復(fù)雜度是 。面對(duì)大樣本和特征數(shù)較多的情況，使用KD樹、球樹訓(xùn)練數(shù)據(jù)。以KD樹為例，搜索時(shí)間復(fù)雜度為 ，適合于樣本數(shù)量遠(yuǎn)大于特征數(shù)量的kNN搜索。9.2 k-近鄰學(xué)習(xí)sklearn.neighbors模塊集成了k-近鄰相關(guān)的類，KNeighborsClassifier用做kNN分類樹，KNeighborsRegressor用做kNN回歸樹。KNeighborsClassifier類的實(shí)現(xiàn)原型如下：9.2.2 算法實(shí)例class sklearn.neighbors.KNei

5、ghborsClassifier(n_neighbors=5, weights=uniform, algorithm=auto, leaf_size=30, p=2, metric=minkowski, metric_params=None, n_jobs=1, *kwargs)：主要參數(shù)如下：n_neighbors：整型，默認(rèn)參數(shù)值為5。鄰居數(shù)k值。weights：字符串或回調(diào)函數(shù)，默認(rèn)參數(shù)值為uniform。預(yù)測(cè)時(shí)的權(quán)重有：9.2 k-近鄰學(xué)習(xí)uniform：所有近鄰樣本權(quán)重都一樣；distance：權(quán)重和距離成反比；callable，即回調(diào)函數(shù)：該函數(shù)的輸入是距離數(shù)組，輸出是同樣大小的權(quán)

6、重?cái)?shù)組。algorithm：計(jì)算近鄰的算法，包括如下四種：auto，根據(jù)傳遞給fit方法的參數(shù)值，嘗試選擇最優(yōu)算法；ball_tree，球樹實(shí)現(xiàn)（BallTree）；kd-tree，KD樹實(shí)現(xiàn)（KDTree）；brute，暴力實(shí)現(xiàn)。leaf size：整型，默認(rèn)參數(shù)值為30。定義構(gòu)建KD樹或球樹時(shí)葉子結(jié)點(diǎn)數(shù)量的閾值。這個(gè)值會(huì)影響構(gòu)建和查詢的速度，以及樹的存儲(chǔ)空間。 metric：字符串或回調(diào)函數(shù)，默認(rèn)參數(shù)值為minkowski。給定樹的距離度量方法。p：整型，默認(rèn)參數(shù)值為2。定義閔可夫斯基距離中的p值。9.2 k-近鄰學(xué)習(xí)實(shí)例代碼 9.2 k-近鄰學(xué)習(xí)在這個(gè)例子中，使用鳶尾花iris數(shù)據(jù)集作為

7、訓(xùn)練數(shù)據(jù)集，提取該數(shù)據(jù)集的前兩個(gè)特征值以簡(jiǎn)化樣本。首先創(chuàng)建近鄰分類的實(shí)例并對(duì)數(shù)據(jù)進(jìn)行擬合，同時(shí)繪制了分類的邊界，將不同分類點(diǎn)以不同的顏色顯示出來。最后將訓(xùn)練數(shù)據(jù)集中的數(shù)據(jù)用不同顏色的散點(diǎn)顯示出來。9.2 k-近鄰學(xué)習(xí)kNN算法本身簡(jiǎn)單有效，能處理大規(guī)模的數(shù)據(jù)分類，尤其適用于樣本分類邊界不明顯的情況。計(jì)算量較大且運(yùn)行時(shí)需要大量?jī)?nèi)存：對(duì)每一個(gè)待分類數(shù)據(jù)都要計(jì)算它到全體已知樣本的距離，才能求得它的k個(gè)最近鄰點(diǎn)。kNN算法的三個(gè)基本要素：（1）k值的選擇：通過交叉驗(yàn)證的方式求出最合適的k值，默認(rèn)取值為5。（2）分類決策規(guī)則：通常采用多數(shù)表決決定。在類域間分布不平衡的情況下，采用為k個(gè)鄰居分配不同權(quán)值的

8、方法來改進(jìn)。（3）距離度量方法。9.2.3 算法關(guān)鍵9.3 主成分分析通過某種線性投影，將高維的數(shù)據(jù)映射到低維的空間中表示，并期望在所投影的維度上數(shù)據(jù)的方差最大，以此使用較少的數(shù)據(jù)維度，同時(shí)保留住較多的原數(shù)據(jù)點(diǎn)的特性。PCA是丟失原始數(shù)據(jù)信息最少的一種線性降維方式，可以將PCA應(yīng)用在數(shù)據(jù)壓縮、數(shù)據(jù)可視化、提升機(jī)器學(xué)習(xí)速度等場(chǎng)景中。9.3.1 算法思想 PCA是將n維特征向量映射到r維上（ ），映射的過程要求每個(gè)維度的樣本方差最大化，達(dá)到盡量使新的r維特征向量之間互不相關(guān)的目的。這些數(shù)據(jù)中擁有方差最大的r個(gè)維度被稱為主成分。假設(shè)有樣本數(shù)據(jù)集 ，每個(gè)樣本有n個(gè)特征： 。處理過程如下：9.3 主成分

9、分析計(jì)算樣本均值生成去中心化的樣本，得到中心化矩陣： , 其中 ， ，計(jì)算S的協(xié)方差矩陣： ，即 使用SVD奇異值分解方法計(jì)算協(xié)方差矩陣的特征值和特征向量。 調(diào)用方法：linalg.svd()， 矩陣 中的特征值排序，選擇其中最大的r個(gè)，將其對(duì)應(yīng)特征向量作為 列向量組成降維矩陣 。將樣本點(diǎn)投影到選取的特征向量 上，降維后的數(shù)據(jù)為： 9.3 主成分分析我們使用貢獻(xiàn)率來判斷選擇主成分的個(gè)數(shù)。貢獻(xiàn)率是指選取的r個(gè)特征值總和占全部特征值總和的比重，一般應(yīng)取85%以上。公式如下：9.3.2 算法實(shí)例scikit-learn提供了主成分分析相關(guān)的類sklearn.decomposition，其函數(shù)原型如下

10、：class sklearn.decomposition.PCA(n_components=None, copy=True, whiten=False, svd_solver=auto, tol=0.0, iterated_power=auto, random_state=None)9.3 主成分分析主要參數(shù)如下：n_components：整型，浮點(diǎn)型，None或者字符串。保留的主成分個(gè)數(shù)，亦即保留下來的特征個(gè)數(shù)n。copy：布爾值類型，默認(rèn)參數(shù)值為False。若為True，將原始訓(xùn)練數(shù)據(jù)復(fù)制一份，算法運(yùn)行后原始訓(xùn)練數(shù)據(jù)的值不會(huì)有任何改變；若為False，則在原始數(shù)據(jù)上進(jìn)行降維計(jì)算，運(yùn)行PCA

11、算法后原始訓(xùn)練數(shù)據(jù)的值會(huì)改變。whiten：布爾值類型，默認(rèn)參數(shù)值為False。白化，使得每個(gè)特征具有相同的方差。從轉(zhuǎn)換后的信號(hào)中刪除一些信息，提高下游估計(jì)值的預(yù)測(cè)精度。svd_solver：字符串。可以取值auto，full，arpark，或randomized。以三維的球型數(shù)據(jù)集為原始數(shù)據(jù)對(duì)象，通過降維方法把它降成二維數(shù)據(jù)：9.3 主成分分析實(shí)例代碼 9.3 主成分分析運(yùn)行結(jié)果如下： n_components=2.000000主成分方差比例： 0.98318212 0.00850037主成分方差： 3.78483785 0.03272285n_components=0.950000主成分方

12、差比例： 0.98318212主成分方差： 3.78483785n_components=0.990000主成分方差比例： 0.98318212 0.00850037主成分方差： 3.78483785 0.03272285n_components=mle主成分方差比例： 0.98318212主成分方差： 3.78483785首先使用scikit提供的make_blobs方法，在指定樣本點(diǎn)數(shù)量、特征數(shù)量、中心點(diǎn)、范圍等基礎(chǔ)上生成三維球型數(shù)據(jù)；當(dāng)n_components=2時(shí)，將數(shù)據(jù)降維到二維，即保留2個(gè)主成分；當(dāng)n_components=0.95時(shí)，表示不直接指定降維的維度，而指定降維后的主成分

13、方差占總方差值的比例為95%以上。此時(shí)只保留了1個(gè)主成分，其方差為3.78483785、方差占比98.3%。當(dāng)n_components=mle，與保留2個(gè)主成分的效果一致。9.3 主成分分析當(dāng)n_components=0.99時(shí)，表示指定降維后的主成分方差占總方差值的比例為99%以上。此時(shí)保留了2個(gè)主成分，其方差分別為3.78483785和0.3272285，方差占比為98.3%和0.85%，方差占比之和為99.2%。使用mplot3d實(shí)現(xiàn)三維數(shù)據(jù)可視化，并利用mplotlib將降維后的數(shù)據(jù)顯示出來。對(duì)比兩幅圖可以很清楚地看到，PCA降維的過程保留了原始三維圖中的4個(gè)聚類。9.4 低維嵌入傳統(tǒng)

14、的線性降維方法，如主成分分析PCA，在把高維數(shù)據(jù)映射到低維空間時(shí)通常不能保留原高維數(shù)據(jù)的內(nèi)在非線性結(jié)構(gòu)和特征。非線性的方法如LLE、hessian局部線性嵌入算法HLLE等應(yīng)運(yùn)而生。它們的優(yōu)點(diǎn)是具有較少的參數(shù)需要設(shè)置，而且使用非迭代方法求解從而可以避免陷入局部極小。9.4.1 算法原理 LLE算法基本思想是把整個(gè)非線性流形分為許多個(gè)小塊，這些小塊由各數(shù)據(jù)點(diǎn)與它的k個(gè)鄰居點(diǎn)構(gòu)成，每個(gè)小塊可以看作是擁有局部線性結(jié)構(gòu)的。每個(gè)數(shù)據(jù)點(diǎn)和它的k個(gè)鄰居點(diǎn)的線性組合系數(shù)稱為重構(gòu)權(quán)重。LLE認(rèn)為所有數(shù)據(jù)點(diǎn)降到低維后鄰居關(guān)系不變，包括重構(gòu)權(quán)重也不變。因此將小塊數(shù)據(jù)線性降維后，再把它們拼接起來，即可構(gòu)成高維數(shù)據(jù)的低

15、維表示。9.4 低維嵌入9.4 低維嵌入9.4.2 算法實(shí)例流形學(xué)習(xí)庫在sklearn.manifold包中。里面實(shí)現(xiàn)的流形學(xué)習(xí)算法包括：多維尺度變換（MDS）算法、等距映射（ISOMAP）算法、拉普拉斯特征映射（LE）算法以及局部線性嵌入（LLE）算法。LLE算法對(duì)應(yīng)的類是LocallyLinearEmbedding，其函數(shù)原型如下： class sklearn.manifold.LocallyLinearEmbedding(n_neighbors=5, n_components=2, reg=0.001, eigen_solver=auto, tol=1e-06, max_iter=100

16、, method=standard, hessian_tol=0.0001, modified_tol=1e-12, neighbors_algorithm=auto, random_state=None, n_jobs=1主要參數(shù)如下： 9.4 低維嵌入n_neighbors：整型。搜索樣本的近鄰的個(gè)數(shù)，默認(rèn)是5。n_components：整型。流形學(xué)習(xí)降維到的維數(shù)，維度降到2-3維可用于可視化呈現(xiàn)。reg：浮點(diǎn)型。正則化常量，乘以距離矩陣的局部協(xié)方差矩陣的跡。eigen_solver：字符串，可以取值arpack，dense和auto。其含義如下：auto：算法會(huì)為輸入數(shù)據(jù)嘗試選擇最好的特

17、征分解的方法；dense：使用標(biāo)準(zhǔn)非稀疏矩陣特征分解方法；arpack：用于稀疏和非稀疏的矩陣分解，但在稀疏矩陣分解時(shí)速度更快。method：字符串，可以取值 standard， hessian， modified和ltsa。 standard：使用標(biāo)準(zhǔn)的局部線性嵌入算法； hessian： 使用Hessian eigenmap算法； modified：使用改進(jìn)的局部線性嵌入算法；ltsa：使用局部切線空間對(duì)齊算法。neighbors_algorithm：字符串，可以取值 auto， brute，kd-tree和ball-tree。9.4 低維嵌入實(shí)例代碼 9.4 低維嵌入使用sklearn生

18、成的生成瑞士卷曲線數(shù)據(jù)集，樣本點(diǎn)數(shù)量為1500。接下來調(diào)用manifold包中的locally_linear_embedding類實(shí)現(xiàn)LLE算法。最后對(duì)原始數(shù)據(jù)、降維結(jié)果分別做可視化呈現(xiàn)。LLE算法對(duì)k值選取非常敏感，只有選取了合適的k值參數(shù)才能獲得較好效果。 (a) 原始瑞士卷數(shù)據(jù)(b) K=10時(shí)LLE降維效果(c) K=20時(shí)LLE降維效果(c) K=80時(shí)LLE降維效果9.4 低維嵌入9.4.3 算法評(píng)價(jià)9.5 SVD分解矩陣分解技術(shù)能從復(fù)雜數(shù)據(jù)中提取重要的特征信息。它將原始矩陣表示成兩個(gè)或多個(gè)矩陣的乘積，能夠用相對(duì)較小的數(shù)據(jù)集來表示原始數(shù)據(jù)集，其他數(shù)據(jù)則被視作噪聲或冗余信息，從而提高

19、運(yùn)算效率和推薦精度。奇異值分解（Singular Value Decomposition，SVD）作為常見的矩陣分解技術(shù)，也常應(yīng)用于降維。9.5.1 SVD算法原理9.5 SVD分解9.5 SVD分解9.5 SVD分解9.5.2 算法實(shí)例例1 SVD算法實(shí)現(xiàn)。利用線性代數(shù)工具箱 numpy.linalg的svd函數(shù)，實(shí)現(xiàn)代碼如下：二維數(shù)組輸入數(shù)據(jù)data，SVD函數(shù)輸出3個(gè)矩陣U、S和V，其中U和V是正交矩陣，S由輸入矩陣data的奇異值組成。使用np.diag(S)函數(shù)生成完整的奇異值矩陣，將U、S、V三個(gè)矩陣相乘還原出來的結(jié)果數(shù)據(jù)，可以看到它和原始矩陣data是十分接近的。9.5 SVD分

20、解U: -0.44721867 0.53728743 0.00643789 -0.50369332 -0.35861531 -0.24605053 -0.86223083 -0.14584826 -0.29246336 0.40329582 0.22754042 -0.10376096 -0.20779151 -0.67004393 0.3950621 -0.58878098 -0.50993331 -0.05969518 0.10968053 0.28687443 -0.53164501 -0.18870999 0.19141061 0.53413013S: 17.71392084 0. 0

21、. 0. 0. 6.39167145 0. 0. 0. 0. 3.09796097 0. 0. 0. 0. 1.32897797V: -0.57098887 -0.4274751 -0.38459931 -0.58593526 0.22279713 0.51723555 -0.82462029 -0.05319973 -0.67492385 0.69294472 0.2531966 -0.01403201 0.41086611 0.26374238 0.32859738 -0.80848795U*S*V: 5.00000000e+00 5.00000000e+00 1.38777878e-15

22、 5.00000000e+00 5.00000000e+00 2.39391840e-15 3.00000000e+00 4.00000000e+00 3.00000000e+00 4.00000000e+00 1.09634524e-15 3.00000000e+00 -5.55111512e-16 1.94289029e-16 5.00000000e+00 3.00000000e+00 5.00000000e+00 4.00000000e+00 4.00000000e+00 5.00000000e+00 5.00000000e+00 4.00000000e+00 5.00000000e+0

23、0 5.00000000e+00運(yùn)行結(jié)果9.5 SVD分解9.5 SVD分解降序索引： 0 2 1降序的距離數(shù)組： 0.93401972 0.4508519 0.25244701運(yùn)行結(jié)果如下經(jīng)過SVD分解降維處理以后，與測(cè)試用戶最相似的用戶是第一行用戶，可以將他評(píng)價(jià)過的物品推薦給測(cè)試用戶。9.5 SVD分解9.5 SVD分解實(shí)例代碼 9.5 SVD分解(9, 4.1039196647197578), (6, 4.077571965028409), (4, 4.0607093807694685)運(yùn)行結(jié)果如下，表示按照影片相似度，優(yōu)先推薦第9個(gè)、第6個(gè)、第4個(gè)影片。9.5 綜合實(shí)例作為無監(jiān)督學(xué)習(xí)的

24、一種應(yīng)用，如果碰到特征維度較高的訓(xùn)練樣本，可以考慮使用PCA特征降維方法獲取低維度的樣本特征，從而實(shí)現(xiàn)數(shù)據(jù)降維和壓縮的目的。接下來以手寫體數(shù)字圖像識(shí)別為例來說明PCA算法的使用。9.6.1 PCA主成分分析9.6 綜合實(shí)例實(shí)現(xiàn)代碼 9.6 綜合實(shí)例實(shí)現(xiàn)代碼（續(xù)上） 9.6 綜合實(shí)例手寫體數(shù)字圖像識(shí)別實(shí)現(xiàn)過程首先，使用sklearn中自帶的手寫數(shù)字?jǐn)?shù)據(jù)集load_digits獲得手寫數(shù)字圖像數(shù)據(jù)并存于digits變量中。利用train_test_split方法分割數(shù)據(jù)，并隨機(jī)選取80%數(shù)據(jù)作為訓(xùn)練樣本x_train，20%作為測(cè)試樣本y_train；從sklearn.preprocessing里

25、導(dǎo)入數(shù)據(jù)標(biāo)準(zhǔn)化模塊StandardScaler，對(duì)訓(xùn)練和測(cè)試的特征數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化。然后，分別訓(xùn)練兩個(gè)以支持向量機(jī)分類器SVC為基礎(chǔ)的手寫數(shù)字圖像識(shí)別模型，其中一個(gè)模型使用原始維度即64維的像素特征識(shí)別，另一個(gè)采用PCA降維重構(gòu)之后的低維特征來識(shí)別圖像特征，其中n_components設(shè)置為10，也就是將64維降到10維。預(yù)測(cè)出分類結(jié)果后，分別比較兩個(gè)模型的準(zhǔn)確率評(píng)分以及分類報(bào)告。最后，展示前100個(gè)測(cè)試樣本數(shù)據(jù)以及PCA降維后的SVC分類結(jié)果9.6 綜合實(shí)例The Accuracy of SVC is 0.988888888889classification report of SVC pre

26、cision recall f1-score support 0 1.00 1.00 1.00 29 1 0.98 1.00 0.99 46 2 1.00 0.97 0.99 37 3 1.00 1.00 1.00 39 4 0.96 1.00 0.98 25 5 0.97 0.97 0.97 37 6 0.98 1.00 0.99 41 7 1.00 1.00 1.00 29 8 1.00 0.98 0.99 44 9 1.00 0.97 0.98 33avg / total 0.99 0.99 0.99 360運(yùn)行結(jié)果如下The Accuracy of PCA_SVC is 0.95classification report of PCA_SVC precision recall f1-score support 0 1.00 1.00 1.00 29 1 0.98 0.98 0.98 46 2 1.00 1.00 1.00 37 3 0.91 0.82 0.86 39 4 1.00 0.96 0.98 25 5 0.92 0.95 0.93 37