關(guān)鍵字
樣本的特征數(shù)稱為維數(shù)（dimensionality），當(dāng)維數(shù)非常大時(shí)，也就是現(xiàn)在所說的“維數(shù)災(zāi)難”，具體表現(xiàn)在：在高維情形下，數(shù)據(jù)樣本將變得十分稀疏，因?yàn)榇藭r(shí)要滿足訓(xùn)練樣本為“密采樣”的總體樣本數(shù)目是一個(gè)觸不可及的天文數(shù)字，訓(xùn)練樣本的稀疏使得其代表總體分布的能力大大減弱，從而消減了學(xué)習(xí)器的泛化能力；同時(shí)當(dāng)維數(shù)很高時(shí)，計(jì)算距離也變得十分復(fù)雜，甚至連計(jì)算內(nèi)積都不再容易，這也是為什么支持向量機(jī)（SVM）使用核函數(shù)“低維計(jì)算，高維表現(xiàn)”的原因。
1、k近鄰學(xué)習(xí)（KNN算法）
k近鄰學(xué)習(xí)是一種常用的監(jiān)督學(xué)習(xí)方法，無需訓(xùn)練訓(xùn)練集，是較為簡(jiǎn)單的經(jīng)典機(jī)器學(xué)習(xí)算法之一，可以處理回歸問題和分類問題。
其工作機(jī)制很簡(jiǎn)單：給定測(cè)試樣本，基于某種距離度量找出訓(xùn)練集中與其最靠近的k個(gè)訓(xùn)練樣本，然后基于這k個(gè)“鄰居”的信息來進(jìn)行預(yù)測(cè)。一般來說，我們只選擇樣本數(shù)據(jù)集中前k個(gè)最相似的數(shù)據(jù)，這就是k近鄰算法中k的出處，通常k是不大于20的整數(shù)。
通常在分類任務(wù)中可使用“投票法”，即選擇這k個(gè)樣本中出現(xiàn)最多的類別標(biāo)記作為預(yù)測(cè)結(jié)果；在回歸任務(wù)中可使用“平均法”，即將這k個(gè)樣本的實(shí)值輸出標(biāo)記的平均值作為預(yù)測(cè)結(jié)果，還可以基于距離遠(yuǎn)近進(jìn)行加權(quán)平均或加權(quán)投票，距離越近的樣本權(quán)重越大。
投票法：通常在分類任務(wù)中使用，判別方法是選擇這k個(gè)樣本中出現(xiàn)最多的雷冰標(biāo)記作為預(yù)測(cè)結(jié)果。
平均法：通常在回歸任務(wù)中使用，判別方法是將這k個(gè)樣本的實(shí)值輸出標(biāo)記的平均值最為預(yù)測(cè)結(jié)果。
加權(quán)平均或加權(quán)投票：根據(jù)距離遠(yuǎn)近來決定權(quán)重，距離越近，權(quán)重越大。
2、SVM和KNN算法區(qū)別
SVM算法樣本需要固定，屬于急切性學(xué)習(xí)，即在存在訓(xùn)練階段，在學(xué)習(xí)模型中訓(xùn)練好后，與驗(yàn)證集比較，將低維度問題上升到高緯度
KNN算法不需要固定樣本數(shù)量，屬于懶惰學(xué)習(xí)，沒有顯示的訓(xùn)練過程，它在訓(xùn)練階段只是把數(shù)據(jù)保存下來，訓(xùn)練時(shí)間開銷為0，等收到測(cè)試樣本后進(jìn)行處理
3、KNN優(yōu)缺點(diǎn)：
優(yōu)點(diǎn)：
（1）簡(jiǎn)單，易于理解，易于實(shí)現(xiàn)，無需參數(shù)估計(jì)，無需訓(xùn)練，用法靈活;（2） 精度高，對(duì)異常值不敏感，無數(shù)據(jù)輸入假定
（3）適合對(duì)稀有事件進(jìn)行分類;
（4） 適合于多分類問題(multi-modal,對(duì)象具有多個(gè)類別標(biāo)簽)，KNN要比SVM表現(xiàn)要好
（5）對(duì)于小樣本預(yù)測(cè)方便
缺點(diǎn)：
（1）計(jì)算復(fù)雜度高、空間復(fù)雜度高，對(duì)大量測(cè)試樣本計(jì)算量大，資源開銷大。
（2）K值的選擇：最大的缺點(diǎn)是當(dāng)樣本不平衡時(shí)，如一個(gè)類的樣本容量很大，而其他類樣本容量很小時(shí)，有可能導(dǎo)致當(dāng)輸入一個(gè)新樣本時(shí)，該樣本的K個(gè)鄰居中大容量類的樣本占多數(shù)。
（3） KNN是一種消極學(xué)習(xí)方法、懶惰算法。 缺少訓(xùn)練階段，無法應(yīng)對(duì)多樣本。
4、KNN實(shí)現(xiàn)步驟：
1）計(jì)算距離
歐氏距離（Euclidean distance），即
2）按照距離的遞增關(guān)系進(jìn)行排序；
3）選取距離最小的K個(gè)點(diǎn)（一般不大于20個(gè)）；
4）確定前K個(gè)點(diǎn)所在類別的出現(xiàn)頻率:
出現(xiàn)頻率 =某個(gè)類別 / k
5）返回前K個(gè)點(diǎn)中出現(xiàn)頻率最高的類別作為測(cè)試數(shù)據(jù)的預(yù)測(cè)分類。
舉個(gè)例子，根據(jù)下圖，測(cè)試樣本m在圖中央，若k=1時(shí)，樣本m的近鄰點(diǎn)為“+”，則判斷樣本m為“+”。當(dāng)k=3時(shí)，近鄰點(diǎn)有1個(gè)+、2個(gè)-，則判斷為“-”。當(dāng)k=5時(shí)，近鄰點(diǎn)有3個(gè)+、2個(gè)-，則判斷為“+”。
4.1、歐幾里得距離、巴氏距離、馬氏距離的區(qū)別：
歐幾里得距離
歐幾里得距離也叫做（歐氏距離）是歐幾里得空間中兩點(diǎn)的“普遍”（直線距離）。
缺點(diǎn)主要有兩個(gè)：(1)將各個(gè)分量的量綱(scale)，也就是“單位”當(dāng)作相同的看待了。(2)沒有考慮各個(gè)分量的分布（期望，方差等)可能是不同的。
舉個(gè)例子：二維樣本(身高,體重)，其中身高范圍是150-190，體重范圍是50-60，有三個(gè)樣本：a(180,50)，b(190,50)，c(180,60)。那么a與b之間的閔氏距離（無論是曼哈頓距離、歐氏距離或切比雪夫距離）等于a與c之間的閔氏距離，但是身高的10cm不等價(jià)于體重的10kg。
代碼實(shí)現(xiàn)
import numpy as np
np.linalg(vector1-vector2, ord=2)
巴氏距離
在統(tǒng)計(jì)中，Bhattacharyya距離測(cè)量?jī)蓚€(gè)離散或連續(xù)概率分布的相似性。它與衡量?jī)蓚€(gè)統(tǒng)計(jì)樣品或種群之間的重疊量的Bhattacharyya系數(shù)密切相關(guān)。Bhattacharyya距離和Bhattacharyya系數(shù)以20世紀(jì)30年代曾在印度統(tǒng)計(jì)研究所工作的一個(gè)統(tǒng)計(jì)學(xué)家A. Bhattacharya命名。同時(shí)，Bhattacharyya系數(shù)可以被用來確定兩個(gè)樣本被認(rèn)為相對(duì)接近的，它是用來測(cè)量中的類分類的可分離性。
巴氏距離的定義
對(duì)于離散概率分布 p和q在同一域 X，它被定義為：
其中
它是Bhattacharyya系數(shù)。
馬氏距離
由印度科學(xué)家馬哈拉諾比斯提出，表示數(shù)據(jù)的協(xié)方差距離。是一種有效的計(jì)算兩個(gè)位置樣本集相似度的方法。與歐氏距離不同的是他考慮到各種特性之間的聯(lián)系并且是尺度無關(guān)的，即獨(dú)立于測(cè)量尺度。如果協(xié)方差矩陣為單位矩陣，馬氏距離就簡(jiǎn)化為歐式距離，如果協(xié)方差矩陣為對(duì)角陣，其也可稱為正規(guī)化的馬氏距離。
優(yōu)點(diǎn)：（1）它不受量綱的影響，兩點(diǎn)之間的馬氏距離與原始數(shù)據(jù)的測(cè)量單位無關(guān)。（它考慮到各種特性之間的聯(lián)系（例如：一條關(guān)于身高的信息會(huì)帶來一條關(guān)于體重的信息，因?yàn)閮烧呤怯嘘P(guān)聯(lián)的）并且是尺度無關(guān)的(scale-invariant)，即獨(dú)立于測(cè)量尺度）；（2）馬氏距離還可以排除變量之間的相關(guān)性的干擾。
缺點(diǎn)：（1）夸大了變化微小的變量的作用。（2）受協(xié)方差矩陣不穩(wěn)定的影響，馬氏距離并不總是能順利計(jì)算出。即計(jì)算馬氏距離過程中，要求總體樣本數(shù)大于樣本的維數(shù)，否則得到的總體樣本協(xié)方差矩陣逆矩陣不存在。（3）如果樣本的維數(shù)非常大，那么計(jì)算它的協(xié)方差矩陣是十分耗時(shí)的
代碼實(shí)現(xiàn)：
import numpy as np
x=np.random.random(10)
y=np.random.random(10)
#馬氏距離要求樣本數(shù)要大于維數(shù)，否則無法求協(xié)方差矩陣
#此處進(jìn)行轉(zhuǎn)置，表示10個(gè)樣本，每個(gè)樣本2維
X=np.vstack([x,y])
XT=X.T
#根據(jù)公式求解
S=np.cov(X) #兩個(gè)維度之間協(xié)方差矩陣
SI = np.linalg.inv(S) #協(xié)方差矩陣的逆矩陣
#馬氏距離計(jì)算兩個(gè)樣本之間的距離，此處共有10個(gè)樣本，兩兩組合，共有45個(gè)距離。
n=XT.shape[0]
d1=[]
for i in range(0,n):
for j in range(i+1,n):
delta=XT[i]-XT[j]
d=np.sqrt(np.dot(np.dot(delta,SI),delta.T))
d1.append(d)
表格統(tǒng)計(jì)
| 歐氏距離 | 巴氏距離 | 馬氏距離 | |
|---|---|---|---|
| 優(yōu)點(diǎn) | 易于理解、適用于大多數(shù)場(chǎng)景 | 可以測(cè)量?jī)蓚€(gè)離散或連續(xù)概率分布的相似性。 | （1）它不受量綱的影響，兩點(diǎn)之間的馬氏距離與原始數(shù)據(jù)的測(cè)量單位無關(guān)。 （2）馬氏距離還可以排除變量之間的相關(guān)性的干擾。 |
| 缺點(diǎn) | (1)將各個(gè)分量的量綱(scale)，也就是“單位”當(dāng)作相同的看待了。(2)沒有考慮各個(gè)分量的分布（期望，方差等)可能是不同的。 | 使用場(chǎng)景較少 | （1）夸大了變化微小的變量的作用。 （2）受協(xié)方差矩陣不穩(wěn)定的影響，馬氏距離并不總是能順利計(jì)算出。 （3）如果樣本的維數(shù)非常大，那么計(jì)算它的協(xié)方差矩陣是十分耗時(shí)的！ |
| 相同點(diǎn) | （1）如果馬氏距離的協(xié)方差矩陣為單位矩陣，馬氏距離就簡(jiǎn)化為歐氏距離 | （2）歐氏和馬氏都是計(jì)算兩個(gè)未知樣本集的相似度的方法。 | （3）歐氏和馬氏距離都可以計(jì)算多維度數(shù)據(jù) |
| 不同點(diǎn) | （1）馬氏距離它不受量綱的影響，兩點(diǎn)之間的馬氏距離與原始數(shù)據(jù)的測(cè)量單位無關(guān)而歐氏當(dāng)各個(gè)分量為不同性質(zhì)的量時(shí)，“距離”的大小與指標(biāo)的單位有關(guān)。它將樣品的不同屬性之間的差別等同看待 | （2）馬氏距離的計(jì)算是不穩(wěn)定的而歐氏和巴氏是穩(wěn)定的 | （3）巴氏距離測(cè)量?jī)蓚€(gè)離散或連續(xù)概率分布的相似性 |
| 公式 |  |
 |
 |
參考博客：
https://blog.csdn.net/jideljd_2010/article/details/39938555
https://blog.csdn.net/shenbo2030/article/details/44226919
https://blog.csdn.net/mousever/article/details/45967643
5、MDS多維標(biāo)度法
k近鄰學(xué)習(xí)方法基于一個(gè)重要的假設(shè)：任意測(cè)試樣本x附近任意小的 距離范圍內(nèi)總能找到一個(gè)訓(xùn)練樣本，即訓(xùn)練樣本的采樣密度足夠大，或稱為密采樣（dense sample）。不過這在現(xiàn)實(shí)任務(wù)中一般很難滿足，假設(shè) ，在單個(gè)屬性情況下，僅需1000個(gè)樣本點(diǎn)平均分布在歸一化后的屬性取值范圍內(nèi)[0,1]，即可使得任務(wù)測(cè)試樣本在其附近0.001距離范圍內(nèi)總能找到一個(gè)訓(xùn)練樣本，此時(shí)最近鄰分類器的錯(cuò)誤率不超過貝葉斯最優(yōu)分類器的錯(cuò)誤率的兩倍；但若在多個(gè)屬性情況下，如假定屬性維數(shù)是20，按照密采樣條件要求，至少需要 (〖10〗^3 )20=〖10〗60個(gè)樣本。現(xiàn)實(shí)應(yīng)用中屬性維數(shù)眾多，要滿足密采樣條件，所需的樣本數(shù)目將是天文數(shù)字。而且還要考慮距離度量計(jì)算，高維空間對(duì)距離計(jì)算來說不是簡(jiǎn)單的開銷，當(dāng)維數(shù)很高時(shí)，連計(jì)算內(nèi)積都不容易。
上文的分析暴露一個(gè)很嚴(yán)重的問題，就是高維情形下，樣本數(shù)的采樣以及距離計(jì)算問題。在高維情形下出現(xiàn)的數(shù)據(jù)樣本稀疏、距離計(jì)算困難等問題，是所有機(jī)器學(xué)習(xí)方法共同面臨的嚴(yán)重障礙，被稱為維數(shù)災(zāi)難（curse of dimensionality）。
緩解維數(shù)災(zāi)難的兩個(gè)途徑：一是特征選擇；二是本文要重點(diǎn)介紹的降維（dimension reduction）。思路上，這兩種途徑都是減少維數(shù)，不過一個(gè)是在事前，一個(gè)是在事中。降維，也稱維數(shù)約簡(jiǎn)，通過某種數(shù)學(xué)變換將原始高維屬性空間轉(zhuǎn)變?yōu)橐粋€(gè)低維子空間（subspace），在子空間中，樣本密度可以大幅提高，距離計(jì)算也相對(duì)容易。事實(shí)上，觀測(cè)或收集到的數(shù)據(jù)樣本雖然是高維的，但與學(xué)習(xí)任務(wù)相關(guān)的或許只是某個(gè)低維分布，這也是特征選擇可以事前根據(jù)業(yè)務(wù)來定義的。
在很多時(shí)候，人們觀測(cè)或收集到的數(shù)據(jù)樣本雖然是高維的，但與學(xué)習(xí)任務(wù)密切相關(guān)的也許僅是某個(gè)低維分布，即高維空間中的一個(gè)低維嵌入，如圖10.2，原始高維空間中的樣本點(diǎn)，在這個(gè)低維嵌入空間中更容易進(jìn)行學(xué)習(xí)。
線性降維方法：基于線性變換來進(jìn)行降維的方法。
5.1 不管是使用核函數(shù)升維還是對(duì)數(shù)據(jù)降維，我們都希望原始空間樣本點(diǎn)之間的距離在新空間中基本保持不變，這樣才不會(huì)使得原始空間樣本之間的關(guān)系及總體分布發(fā)生較大的改變。“多維縮放”（MDS）正是基于這樣的思想，MDS要求原始空間樣本之間的距離在降維后的低維空間中得以保持，如圖10.2
算法實(shí)現(xiàn)：
import numpy as np
import operator
def createDataset():
#四組二維特征
group = np.array([[5,115],[7,106],[56,11],[66,9]])
#四組對(duì)應(yīng)標(biāo)簽
labels = ('動(dòng)作片','動(dòng)作片','愛情片','愛情片')
return group,labels
def classify(intX,dataSet,labels,k):
'''
KNN算法
'''
#numpy中shape[0]返回?cái)?shù)組的行數(shù)，shape[1]返回列數(shù)
#MDS降維操作
dataSetSize = dataSet.shape[0]
#去逆矩陣
diffMat = np.tile(intX,(dataSetSize,1))-dataSet
#二維特征相減后乘方
sqdifMax = diffMat**2
#計(jì)算距離
seqDistances = sqdifMax.sum(axis=1)
distances = seqDistances**0.5
print ("distances:",distances)
#返回distance中元素從小到大排序后的索引
sortDistance = distances.argsort()
print ("sortDistance:",sortDistance)
classCount = {}
for i in range(k):
#取出前k個(gè)元素的類別
voteLabel = labels[sortDistance[i]]
print ("第%d個(gè)voteLabel=%s",i,voteLabel)
classCount[voteLabel] = classCount.get(voteLabel,0)+1
#dict.get(key,default=None),字典的get()方法,返回指定鍵的值,如果值不在字典中返回默認(rèn)值。
#計(jì)算類別次數(shù)
#key=operator.itemgetter(1)根據(jù)字典的值進(jìn)行排序
#key=operator.itemgetter(0)根據(jù)字典的鍵進(jìn)行排序
#reverse降序排序字典
sortedClassCount = sorted(classCount.items(),key = operator.itemgetter(1),reverse = True)
#結(jié)果sortedClassCount = [('動(dòng)作片', 2), ('愛情片', 1)]
print ("sortedClassCount:",sortedClassCount)
return sortedClassCount[0][0]
if __name__ == '__main__':
group,labels = createDataset()
test = [20,101]
test_class = classify(test,group,labels,3)
print (test_class)
完整代碼查看碼云
5.2 主成分分析（PCA）
參閱：http://blog.csdn.net/hellotruth/article/details/30750823
簡(jiǎn)單說：以二維特征為例，如下圖。特征之間可能不存在完全的線性關(guān)系，可能只是強(qiáng)的正相關(guān)。如果把x-y坐標(biāo)分解成u1-u2坐標(biāo)，而u1軸線上反應(yīng)了特征的主要變化（intrinsic），而u2的特征變化較小，其實(shí)可以完全理解為一些噪聲的擾動(dòng)而不去考慮它。PCA的任務(wù)就是找到u1和u2。
PCA其實(shí)是最簡(jiǎn)單的降維方法之一了，很明顯的劣勢(shì)是它僅去除數(shù)據(jù)之間的線性相關(guān)性。對(duì)線性的改善往往通過kernel技術(shù)拓展到非線性的應(yīng)用上。另外，PCA的這種降維不一定有助于分類，用于分類的降維方法之一就是LDA。從另一方面說，PCA是一種線性投影，保留了數(shù)據(jù)與數(shù)據(jù)之間的歐式距離，即原來歐式距離大的兩點(diǎn)在降維后的空間中距離也應(yīng)大（這樣才好保證方差大）。而事實(shí)上數(shù)據(jù)有可能呈現(xiàn)某種流型結(jié)構(gòu)，用PCA降維后數(shù)據(jù)將不能保持原有的流型結(jié)構(gòu)。
原理：PCA采用一組新的基來表示樣本點(diǎn)，其中每一個(gè)基向量都是原來基向量的線性組合，通過使用盡可能少的新基向量來表出樣本，從而達(dá)到降維的目的。
假設(shè)使用d’個(gè)新基向量來表示原來樣本，實(shí)質(zhì)上是將樣本投影到一個(gè)由d’個(gè)基向量確定的一個(gè)超平面上（即舍棄了一些維度），要用一個(gè)超平面對(duì)空間中所有高維樣本進(jìn)行恰當(dāng)?shù)谋磉_(dá)，最理想的情形是：若這些樣本點(diǎn)都能在超平面上表出且這些表出在超平面上都能夠很好地分散開來。但是一般使用較原空間低一些維度的超平面來做到這兩點(diǎn)十分不容易，因此我們退一步海闊天空，要求這個(gè)超平面應(yīng)具有如下兩個(gè)性質(zhì)：
最近重構(gòu)性：樣本點(diǎn)到超平面的距離足夠近，即盡可能在超平面附近；
最大可分性：樣本點(diǎn)在超平面上的投影盡可能地分散開來，即投影后的坐標(biāo)具有區(qū)分性。
這里十分神奇的是：最近重構(gòu)性與最大可分性雖然從不同的出發(fā)點(diǎn)來定義優(yōu)化問題中的目標(biāo)函數(shù)，但最終這兩種特性得到了完全相同的優(yōu)化問題：
接著使用拉格朗日乘子法求解上面的優(yōu)化問題，得到：
因此只需對(duì)協(xié)方差矩陣進(jìn)行特征值分解即可求解出W，PCA算法的整個(gè)流程如下圖所示：
總結(jié)
PCA優(yōu)缺點(diǎn)：
優(yōu)點(diǎn)：1）最小誤差。2）提取了主要信息
缺點(diǎn)：1）計(jì)算協(xié)方差矩陣，計(jì)算量大
LDA方法簡(jiǎn)介
（1）LDA核心思想：往線性判別超平面的法向量上投影，使得區(qū)分度最大（高內(nèi)聚，低耦合）。
（2）LDA優(yōu)缺點(diǎn)：
優(yōu)點(diǎn)：1）簡(jiǎn)單易于理解
缺點(diǎn)：2）計(jì)算較為復(fù)雜
在很多問題上，可能需要非線性映射才能找到恰當(dāng)?shù)牡途S嵌入。那么非線性降維常用的一種方法，就是基于核技巧對(duì)線性降維方法進(jìn)行“核化”（使用一個(gè)超平面去近似表出）。例如核主成分分析（KPCA）
下面主要介紹核化主成分分析（KPCA）的思想。
若核函數(shù)的形式已知，即我們知道如何將低維的坐標(biāo)變換為高維坐標(biāo)，這時(shí)我們只需先將數(shù)據(jù)映射到高維特征空間，再在高維空間中運(yùn)用PCA即可。但是一般情況下，我們并不知道核函數(shù)具體的映射規(guī)則，例如：Sigmoid、高斯核等，我們只知道如何計(jì)算高維空間中的樣本內(nèi)積，這時(shí)就引出了KPCA的一個(gè)重要?jiǎng)?chuàng)新之處：即空間中的任一向量，都可以由該空間中的所有樣本線性表示。證明過程也十分簡(jiǎn)單：
這樣我們便可以將高維特征空間中的投影向量wi使用所有高維樣本點(diǎn)線性表出，接著代入PCA的求解問題，得到：
化簡(jiǎn)到最后一步，發(fā)現(xiàn)結(jié)果十分的美妙，只需對(duì)核矩陣K進(jìn)行特征分解，便可以得出投影向量wi對(duì)應(yīng)的系數(shù)向量α，因此選取特征值前d’大對(duì)應(yīng)的特征向量便是d’個(gè)系數(shù)向量。這時(shí)對(duì)于需要降維的樣本點(diǎn)，只需按照以下步驟便可以求出其降維后的坐標(biāo)?？梢钥闯觯篕PCA在計(jì)算降維后的坐標(biāo)表示時(shí)，需要與所有樣本點(diǎn)計(jì)算核函數(shù)值并求和，因此該算法的計(jì)算開銷十分大。
流行學(xué)習(xí)是一類借鑒了拓?fù)淞餍胃拍畹慕稻S方法。常用的流行學(xué)習(xí)方法有等度量映射和局部線性嵌入。
1 等度量映射（Isomap）
等度量映射的基本出發(fā)點(diǎn)是：高維空間中的直線距離具有誤導(dǎo)性，因?yàn)橛袝r(shí)高維空間中的直線距離在低維空間中是不可達(dá)的。因此利用流形在局部上與歐式空間同胚的性質(zhì)，可以使用近鄰距離來逼近測(cè)地線距離，即對(duì)于一個(gè)樣本點(diǎn)，它與近鄰內(nèi)的樣本點(diǎn)之間是可達(dá)的，且距離使用歐式距離計(jì)算，這樣整個(gè)樣本空間就形成了一張近鄰圖，高維空間中兩個(gè)樣本之間的距離就轉(zhuǎn)為最短路徑問題?？刹捎弥?strong>Dijkstra算法或Floyd算法計(jì)算最短距離，得到高維空間中任意兩點(diǎn)之間的距離后便可以使用MDS算法來其計(jì)算低維空間中的坐標(biāo)。
從MDS算法的描述中我們可以知道：MDS先求出了低維空間的內(nèi)積矩陣B，接著使用特征值分解計(jì)算出了樣本在低維空間中的坐標(biāo)，但是并沒有給出通用的投影向量w，因此對(duì)于需要降維的新樣本無從下手，書中給出的權(quán)宜之計(jì)是利用已知高/低維坐標(biāo)的樣本作為訓(xùn)練集學(xué)習(xí)出一個(gè)“投影器”，便可以用高維坐標(biāo)預(yù)測(cè)出低維坐標(biāo)。Isomap算法流程如下圖：
對(duì)于近鄰圖的構(gòu)建，常用的有兩種方法：一種是指定近鄰點(diǎn)個(gè)數(shù)，像kNN一樣選取k個(gè)最近的鄰居；另一種是指定鄰域半徑，距離小于該閾值的被認(rèn)為是它的近鄰點(diǎn)。但兩種方法均會(huì)出現(xiàn)下面的問題：
若鄰域范圍指定過大，則會(huì)造成“短路問題”，即本身距離很遠(yuǎn)卻成了近鄰，將距離近的那些樣本扼殺在搖籃。
若鄰域范圍指定過小，則會(huì)造成“斷路問題”，即有些樣本點(diǎn)無法可達(dá)了，整個(gè)世界村被劃分為互不可達(dá)的小部落。
2 局部線性嵌入(LLE)
不同于Isomap算法去保持鄰域距離，LLE算法試圖去保持鄰域內(nèi)的線性關(guān)系，假定樣本xi的坐標(biāo)可以通過它的鄰域樣本線性表出：
LLE算法分為兩步走，首先第一步根據(jù)近鄰關(guān)系計(jì)算出所有樣本的鄰域重構(gòu)系數(shù)w：
接著根據(jù)鄰域重構(gòu)系數(shù)不變，去求解低維坐標(biāo)：
這樣利用矩陣M，優(yōu)化問題可以重寫為：
M特征值分解后最小的d’個(gè)特征值對(duì)應(yīng)的特征向量組成Z，LLE算法的具體流程如下圖所示：
首先要學(xué)習(xí)出距離度量必須先定義一個(gè)合適的距離度量形式。對(duì)兩個(gè)樣本xi與xj，它們之間的平方歐式距離為：
若各個(gè)屬性重要程度不一樣即都有一個(gè)權(quán)重，則得到加權(quán)的平方歐式距離：
此時(shí)各個(gè)屬性之間都是相互獨(dú)立無關(guān)的，但現(xiàn)實(shí)中往往會(huì)存在屬性之間有關(guān)聯(lián)的情形，例如：身高和體重，一般人越高，體重也會(huì)重一些，他們之間存在較大的相關(guān)性。這樣計(jì)算距離就不能分屬性單獨(dú)計(jì)算，于是就引入經(jīng)典的馬氏距離(Mahalanobis distance):
標(biāo)準(zhǔn)的馬氏距離中M是協(xié)方差矩陣的逆，馬氏距離是一種考慮屬性之間相關(guān)性且尺度無關(guān)（即無須去量綱）的距離度量。
矩陣M也稱為“度量矩陣”，為保證距離度量的非負(fù)性與對(duì)稱性，M必須為(半)正定對(duì)稱矩陣，這樣就為度量學(xué)習(xí)定義好了距離度量的形式，換句話說：度量學(xué)習(xí)便是對(duì)度量矩陣進(jìn)行學(xué)習(xí)?，F(xiàn)在來回想一下前面我們接觸的機(jī)器學(xué)習(xí)不難發(fā)現(xiàn)：機(jī)器學(xué)習(xí)算法幾乎都是在優(yōu)化目標(biāo)函數(shù)，從而求解目標(biāo)函數(shù)中的參數(shù)。同樣對(duì)于度量學(xué)習(xí)，也需要設(shè)置一個(gè)優(yōu)化目標(biāo)，書中簡(jiǎn)要介紹了錯(cuò)誤率和相似性兩種優(yōu)化目標(biāo)，此處限于篇幅不進(jìn)行展開。
總結(jié)：
數(shù)據(jù)降維的目的:數(shù)據(jù)降維，直觀地好處是維度降低了，便于計(jì)算和可視化，其更深層次的意義在于有效信息的提取綜合及無用信息的擯棄。
數(shù)據(jù)降維的好處：降維可以方便數(shù)據(jù)可視化+數(shù)據(jù)分析+數(shù)據(jù)壓縮+數(shù)據(jù)提取等。
-········
【問題】knn似乎和降維沒有關(guān)系？
降維是將原高維空間嵌入到一個(gè)合適的低維子空間中，接著在低維空間中進(jìn)行學(xué)習(xí)任務(wù)；度量學(xué)習(xí)則是試圖去學(xué)習(xí)出一個(gè)距離度量來等效降維的效果，兩者都是為了解決維數(shù)災(zāi)難帶來的諸多問題。
那kNN呢，為什么一開頭就說了kNN算法，但是好像和后面沒有半毛錢關(guān)系？
正是因?yàn)樵诮稻S算法中，低維子空間的維數(shù)d’通常都由人為指定，因此我們需要使用一些低開銷的學(xué)習(xí)器來選取合適的d’，kNN這家伙懶到家了根本無心學(xué)習(xí)，在訓(xùn)練階段開銷為零，測(cè)試階段也只是遍歷計(jì)算了距離，因此拿kNN來進(jìn)行交叉驗(yàn)證就十分有優(yōu)勢(shì)了~同時(shí)降維后樣本密度增大同時(shí)距離計(jì)算變易，更為kNN來展示它獨(dú)特的十八般手藝提供了用武之地。
參考文獻(xiàn)：
https://www.cnblogs.com/nolonely/p/6435159.html
