關于降維的學習主要分為五類:PCA、LDA、LLE、tSNE、ISOMAP
(一)降維的基本知識點總結
1、降維方法分為線性和非線性降維,非線性降維又分為基于核函數和基于特征值的方法。
(1)線性降維:PCA、ICA、LDA、LFA、LPP
(2)非線性降維方法:①基于核函數的方法:KPCA、KICA、KDA
②基于特征值的方法:ISOMAP、LLE、LE、LPP、LTSA、MVU
或者将降維方法如下圖分類:
2、降維的作用:(為什麼會有這些作用?)
(1)降低時間的複雜度和空間複雜度
(2)節省了提取不必要特征的開銷
(3)去掉資料集中夾雜的噪音
(4)較簡單的模型在小資料集上有更強的魯棒性
(5)當資料能有較少的特征進行解釋,我們可以更好地解釋資料,是的我們可以提取知識
(6)實作資料的可視化
3、降維的目的
用來進行特征選擇和特征提取。
①特征選擇:選擇重要的特征子集,删除其餘特征;
②特征提取:由原始特征形成的較少的新特征。
在特征提取中,我們要找到k個新的次元的集合,這些次元是原來k個次元的組合,這個方法可以是監督的,也可以是非監督的,如PCA是非監督的,LDA是監督的。
4、子集選擇
對于n個屬性,有2n個可能的子集。窮舉搜尋找出屬性的最佳子集可能是不現實的,特别是當n和資料類的數目增加時。通常使用壓縮搜尋空間的啟發式算法,通常這些方法是典型的貪心算法,在搜尋屬性空間時,總是做看上去是最佳的選擇。他們的政策是局部最優選擇,期望由此導緻全局最優解。在實踐中,這種貪心方法是有效的,并可以逼近最優解。
子集選擇的缺點:
5、降維的本質:學習一個映射函數f:x到y。(x是原始資料點的表達,目前最多的是用向量來表示,Y是資料點映射後的低維向量表達。)f可能是:顯示的、隐式的、線性的、非線性的。
(二)主成分分析(PCA)
将樣本投影到某一維上,新的坐标的選擇方式:找到第一個坐标,資料集在該坐标的方差最大(方差最大也就是我們在這個資料次元上能更好地區分不同類型的資料),然後找到第二個坐标,該坐标與原來的坐标正交。該過程會一直的重複,直到新坐标的數目和原來的特征個數相同,這時候我們會發現資料的大部分方差都在前面幾個坐标上表示,這些新的次元就是我們所說的主成分。
(1)PCA的基本思想:尋找資料的主軸方向,由主軸構成一個新的坐标系,這裡的維數可以比原維數低,然後資料由原坐标系向新坐标系投影,這個投影的過程就是降維的過程。
(2)PCA算法的過程
①将原始資料中的每一個樣本都用向量表示,把所有樣本組合起來構成樣本矩陣,通常對樣本矩陣進行中心化處理,得到中心化樣本矩陣。
②求中心化後的樣本矩陣的協方差;
③求協方差矩陣的特征值和特征向量;
④将求出的特征值按從大到小的順序排列,并将其對應的特征向量按照此順序組合成一個映射矩陣,根據指定的PCA保留的特征個數取出映射矩陣的前n行或者前n列作為最終的映射矩陣;
⑤用映射矩陣對資料進行映射,達到資料降維的目的。
(3)PCA執行個體中的小插曲:TF-IDF
TF-IDF:term freuency-inverse document frequency,它是一種用于資訊檢索與文本挖掘的常用權重技術,是一種統計方法,用以評估一字詞對于一個文本集或一個語料庫中其中一份檔案的重要程度。包括兩部分,詞頻和逆向檔案頻率。
(4)協方差矩陣的對角上是方差,非對角線上是協方差。協方差是衡量兩個變量同時變化的變化程度。協方差大于0表示x和y中若一個增,另一個也增;小于0表示一個增一個減。
(5)PCA推導—最大方差理論
在信号進行中認為信号具有較大的方差,噪音具有較小的方差,信噪比越大越好。PCA遵循投影後的樣本點間方差最大原則。
(二)LDA(Linear discriminant analysis)
線性判别式分析,也叫fisher線性判别,是模式識别中的經典算法。
是一種監督學習的降維技術,它的資料集的每個樣本是有類别輸出的。
思想:投影後類内距離最小,類間距離最大。
1、線性判别:将高維的模式樣本投影到最佳鑒别矢量空間,以達到抽取分類資訊和壓縮特征空間維數的效果,投影後保證模式樣本在新的子空間有最大的類間距離和最小的類内距離,這是一種有效的特征提取方法,使用這個方法,能使得投影後模式樣本的類間散布矩陣最大,且同時類内散布矩陣最小。
2、與PCA相比較:
(1)共同點:①都屬于線性方法;
②在降維時都采用矩陣分解的方法;
③都假設資料符合高斯分布;
(2)不同點:
①LDA是有監督的;
②不能保證投影到的坐标系是正交的(根據類别的标注,關注分類能力);
③降維直接與類别的個數有關,與資料本身的次元無關(原始資料是n維的,有c個類别,降維後一般是到c-1維)
④可以用于降維,還可用于分類;
⑤選擇分類性能最好的投影方向。
(三)LLE
1、屬于流形學習的一種,和傳統的PCA、LDA相比,不再是關注樣本方差的降維方法,而是一種關注降維時保持樣本局部的線性特征。
LLE是将高維流形分成很多小塊,每一小塊可以用平面代替,然後再在低維中重新拼合起來,且要求保留各點之間的拓撲關系不變。
2、LLE思想:
首先假設資料在較小的局部是線性的,即某一個資料能夠用它鄰域中的幾個樣本來線性表示,可以通過k-近鄰的思想來找到它的近鄰點。在降維之後,希望樣本點對應的投影盡量保持同樣的線性關系。即投影前後線性關系的權重參數不變或者改變很小。
3、LLE算法推導:
(1)首先确定鄰域大小的選擇;
(2)需要找到某個樣本Xi和這k個最近鄰之間的線性關系(找線性關系是一個回歸問題)
(3)由該樣本點的局部重建權值矩陣和其近鄰點計算出該樣本點的輸出值;
(4)
(四)ISOMAP(等距特征映射)
1、以線性流形學習方法MDS為理論基礎,将經典MDS方法中的歐式距離替換為
(五) tSNE
TSNE是由SNE衍生出的一張算法,SNE最早出現在2002年,改變了MDN和ISOMAP中基于距離不變的思想,将高維映射到低維的同時,盡量保證互相之間的分布機率不變,SNE将高維和低維中的樣本分布都看作高斯分布,而TSNE将低維中的坐标當作T分布,這樣的好處是為了讓距離大的簇之間距離拉大,進而解決了擁擠問題。從SNE到TSNE之間,還有一個對稱SNE,其對SNE有部分改進作用。
1、SNE算法
高維資料用X表示,Xi表示第i個樣本,低維資料用Y來表示,則高維中的分布機率矩陣P定義如下:
其中P(i,j)表示第i個樣本分布在樣本j周圍的機率。delta是依據最大熵原理來決定,entropy=sum(pi*log(pi)),以每個樣本點為中心的delta都需要使得最後分布的熵較小,通常以log(k)為上限,k為你所決定的鄰域點的個數。
低維中的分布機率矩陣計算如下:
這裡我們把低維中的分布看作是均衡的,每個delta都是0.5,由此可以判斷最後降維之後生成的分布也是一個相對均勻的分布。
随機給定一個初始化的Y,進行優化,使得Y的分布矩陣逼近X的分布矩陣。給定目标函數,用KL散度來定義兩個不同分布之間的差距:
則可以計算梯度為:
每次梯度下降的步長可設定固定或者自适應、随機等,也可以加上一個動量的梯度,初始值一般設為1e-4的随機正态分布。
2、對稱SNE
就是讓高維和低維中的機率分布矩陣是對稱的,能友善計算,但是對擁擠問題無法改進。
與SNE相比,隻是梯度有一些變化:
3、TSNE
TSNE對高維中的分布采用對稱SNE中的做法,低維中的分布則采用更一般的T分布,也是對稱的,可以發現sum(P)=sum(Q)=1。
TSNE的算法如下所示:
原文:https://blog.csdn.net/tdj8866/article/details/78539024