一斩祭、介紹
本篇文章纽绍，我們將討論所謂的“維度災(zāi)難”要尔，并解釋在設(shè)計(jì)一個(gè)分類器時(shí)它為何如此重要铁瞒。在下面幾節(jié)中我將對(duì)這個(gè)概念進(jìn)行直觀的解釋妙色，并通過(guò)一個(gè)由于維度災(zāi)難導(dǎo)致的過(guò)擬合的例子來(lái)講解。
考慮這樣一個(gè)例子慧耍，我們有一些圖片身辨，每張圖片描繪的是小貓或者小狗丐谋。我們?cè)噲D構(gòu)建一個(gè)分類器來(lái)自動(dòng)識(shí)別圖片中是貓還是狗。要做到這一點(diǎn)煌珊，我們首先需要考慮貓号俐、狗的量化特征，這樣分類器算法才能利用這些特征對(duì)圖片進(jìn)行分類定庵。例如我們可以通過(guò)毛皮顏色特征對(duì)貓狗進(jìn)行識(shí)別吏饿，即通過(guò)圖片的紅色程度、綠色程度蔬浙、藍(lán)色程度不同猪落，設(shè)計(jì)一個(gè)簡(jiǎn)單的線性分類器：
If 0.5*red+0.3*green+0.2*blue>0.6:
return cat;
else:
return dog;
紅、綠畴博、藍(lán)三種顏色我們稱之為特征Features笨忌，但僅僅利用這三個(gè)特征，還不能得到一個(gè)完美的分類器俱病。因此官疲，我們可以增加更多的特征來(lái)描述圖片。例如計(jì)算圖片X和Y方向的平均邊緣或者梯度密度×料叮現(xiàn)在總共有5個(gè)特征來(lái)構(gòu)建我們的分類器了袁余。
為了得到更好的分類效果，我們可以增加更多特征咱揍，例如顏色颖榜、紋理分布和統(tǒng)計(jì)信息等。也許我們能得到上百個(gè)特征煤裙，但是分類器的效果會(huì)變得更好嗎掩完？答案有些令人沮喪：并不能！事實(shí)上硼砰，特征數(shù)量超過(guò)一定值的時(shí)候且蓬，分類器的效果反而下降。圖1顯示了這種變化趨勢(shì)题翰，這就是“維度災(zāi)難”恶阴。
下一節(jié)我們將解釋為什么產(chǎn)生這條曲線并討論如何避免這種情況發(fā)生。
二血公、維度災(zāi)難與過(guò)擬合
在之前引入的貓和狗的例子中昵仅，我們假設(shè)有無(wú)窮多的貓和狗的圖片，然而，由于時(shí)間和處理能力限制摔笤，我們只得到10張圖片（貓的圖片或者狗的圖片）够滑。我們的最終目標(biāo)是基于這10張圖片構(gòu)建一個(gè)分類器，能夠正確對(duì)10個(gè)樣本之外的無(wú)限多的圖片進(jìn)行正確分類吕世。
現(xiàn)在彰触，讓我們使用一個(gè)簡(jiǎn)單的線性分類器來(lái)嘗試得到一個(gè)好的分類器。如果只使用一個(gè)特征命辖，例如使用圖片的平均紅色程度red渴析。
圖2展示了只使用一個(gè)特征并不能得到一個(gè)最佳的分類結(jié)果。因此吮龄，我們覺(jué)得增加第二個(gè)特征：圖片的平均綠色程度green俭茧。
最后母债，我們決定再增加第三個(gè)特征：圖片的平均藍(lán)色程度，得到了三維特征空間：
在三維特征空間，我們可以找到一個(gè)平面將貓和狗完全分開(kāi)昧辽。這意味著三個(gè)特征的線性組合可以對(duì)10個(gè)訓(xùn)練樣本進(jìn)行最佳的分類衙熔。
以上的例子似乎證明了不斷增加特征數(shù)量搅荞，直到獲得最佳分類效果红氯，是構(gòu)建一個(gè)分類器的最好方法。但是咕痛，之前圖1中痢甘，我們認(rèn)為情況并非如此。我們需要注意一個(gè)問(wèn)題：隨著特征維度的增加茉贡，訓(xùn)練樣本的在特征空間的密度是如何呈指數(shù)型下降的塞栅？
在1D空間中（圖2所示），10個(gè)訓(xùn)練樣本完全覆蓋了1D特征空間腔丧，特征空間寬度為5放椰。因此，1D下的樣本密度是10/2=5愉粤。而在2D空間中（圖3所示）砾医，同樣是10個(gè)訓(xùn)練樣本，它構(gòu)成的2D特征空間面積為5x5=25.因此科汗，2D下的樣本密度是10/25=0.4藻烤。最后在3D空間中，10個(gè)訓(xùn)練樣本構(gòu)成的特征空間大小為5x5x5=125头滔，因此怖亭，3D下的樣本密度為10/125=0.08。
如果我們繼續(xù)增加特征坤检，整個(gè)特征空間維度增加兴猩，并變得越來(lái)越稀疏。由于稀疏性早歇，我們更加容易找到一個(gè)超平面來(lái)實(shí)現(xiàn)分類。這是因?yàn)殡S著特征數(shù)量變得無(wú)限大，訓(xùn)練樣本在最佳超平面的錯(cuò)誤側(cè)的可能性將會(huì)變得無(wú)限小链嘀。然而兜叨，如果我們將高維的分類結(jié)果投影到低維空間中，將會(huì)出現(xiàn)一個(gè)嚴(yán)重的問(wèn)題：
圖6展示了3D的分類結(jié)果投影到2D特征空間的樣子屉来。樣本數(shù)據(jù)在3D是線性可分的路翻，但是在2D卻并非如此。事實(shí)上茄靠，增加第三個(gè)維度來(lái)獲得最佳的線性分類效果茂契，等同于在低維特征空間中使用非線性分類器。其結(jié)果是慨绳，分類器學(xué)習(xí)了訓(xùn)練數(shù)據(jù)的噪聲和異常掉冶，而對(duì)樣本外的數(shù)據(jù)擬合效果并不理想，甚至很差脐雪。
這個(gè)概念稱為過(guò)擬合郭蕉，是維度災(zāi)難的一個(gè)直接后果。圖7展示了一個(gè)只用2個(gè)特征進(jìn)行分類的線性分類器的二維平面圖喂江。
盡管圖7中的簡(jiǎn)單的線性分類器比圖5中的非線性分類器的效果差获询，但是圖7的分類器的泛化能力強(qiáng)涨岁。這是因?yàn)榉诸惼鳑](méi)有把樣本數(shù)據(jù)的噪聲和異常也進(jìn)行學(xué)習(xí)。另一方面說(shuō)吉嚣，使用更少的特征梢薪，維度災(zāi)難就能避免，就不會(huì)出現(xiàn)對(duì)訓(xùn)練樣本過(guò)擬合的現(xiàn)象尝哆。
圖8用不同的方式解釋上面的內(nèi)容秉撇。假設(shè)我們只使用一個(gè)特征來(lái)訓(xùn)練分類器，1D特征值的范圍限定在0到1之間，且每只貓和狗對(duì)應(yīng)的特征值是唯一的琐馆。如果我們希望訓(xùn)練樣本的特征值占特征值范圍的20%规阀，那么訓(xùn)練樣本的數(shù)量就要達(dá)到總體樣本數(shù)的20%。現(xiàn)在瘦麸，如果增加第二個(gè)特征谁撼，也就是從直線變?yōu)槠矫?D特征空間，這種情況下滋饲，如果要覆蓋特征值范圍的20%厉碟，那么訓(xùn)練樣本數(shù)量就要達(dá)到總體樣本數(shù)的45%（0.450.45=0.2）。而在3D空間中屠缭，如果要覆蓋特征值范圍的20%箍鼓，就需要訓(xùn)練樣本數(shù)量達(dá)到總體樣本數(shù)的58%（0.580.58*0.58=0.2）。
換句話說(shuō)呵曹，如果可用的訓(xùn)練樣本數(shù)量是固定的款咖，那么如果增加特征維度的話，過(guò)擬合就會(huì)發(fā)生逢并。另一方面之剧，如果增加特征維度，為了覆蓋同樣的特征值范圍砍聊、防止過(guò)擬合背稼，那么所需的訓(xùn)練樣本數(shù)量就會(huì)成指數(shù)型增長(zhǎng)。
在上面的例子中玻蝌，我們展示了維度災(zāi)難會(huì)引起訓(xùn)練數(shù)據(jù)的稀疏化蟹肘。使用的特征越多，數(shù)據(jù)就會(huì)變得越稀疏俯树，從而導(dǎo)致分類器的分類效果就會(huì)越差帘腹。維度災(zāi)難還會(huì)造成搜索空間的數(shù)據(jù)稀疏程度分布不均。事實(shí)上许饿，圍繞原點(diǎn)的數(shù)據(jù)（在超立方體的中心）比在搜索空間的角落處的數(shù)據(jù)要稀疏得多阳欲。這可以用下面這個(gè)例子來(lái)解釋：
想象一個(gè)單位正方形代表了2D的特征空間，特征空間的平均值位于這個(gè)單位正方形的中心處陋率，距中心處單位距離的所有點(diǎn)構(gòu)成了正方形的內(nèi)接圓球化。沒(méi)有落在單位圓的訓(xùn)練樣本距離搜索空間的角落處更距離中心處更近，而這些樣本由于特征值差異很大（樣本分布在正方形角落處）瓦糟，所有難以分類筒愚。因此，如果大部分樣本落在單位內(nèi)接圓里菩浙，就會(huì)更容易分類巢掺。如圖9所示：
一個(gè)有趣的問(wèn)題是當(dāng)我們?cè)黾犹卣骺臻g的維度時(shí)陆淀，隨著正方形（超立方體）的體積變化考余，圓形（超球體）的體積是如何變化的？無(wú)論維度如何變化倔约，超立方體的體積都是1秃殉，而半徑為0.5的超球體的體積隨著維度d的變化為：
$$V(d)=\frac{\pi^{d/2}}{\Gamma(\frac d2+1)}0.5^d$$
圖10展示了隨著維度d的增加坝初，超球面的體積是如何變化的：
這表明了隨著維度變得越來(lái)越大，超球體的體積趨于零鳄袍，而超立方體的體積是不變的绢要。這種令人驚訝的反直覺(jué)發(fā)現(xiàn)部分解釋了在分類中維度災(zāi)難的問(wèn)題：在高維空間中，大部分的訓(xùn)練數(shù)據(jù)分布在定義為特征空間的超立方體的角落處拗小。就像之前提到的重罪，特征空間角落處的樣本比超球體內(nèi)的樣本更加難以進(jìn)行正確分類。圖11分別從2D哀九、3D和可視化的8D超立方體（$2^8=256$個(gè)角落）的例子論證了這個(gè)結(jié)論剿配。
對(duì)于8維的超球體阅束，大約98%的數(shù)據(jù)集中在它256個(gè)角落處呼胚。其結(jié)果是，當(dāng)特征空間的維度變得無(wú)限大時(shí)息裸，從樣本點(diǎn)到質(zhì)心的最大蝇更、最小歐氏距離的差值與其最小歐式距離的比值趨于零：
$$\lim_{d\rightarrow \infty}\frac{dist_{max}-dist_{min}}{dist_{min}}\rightarrow0$$
因此，距離測(cè)量在高維空間中逐漸變得無(wú)效呼盆。因?yàn)榉诸惼魇腔谶@些距離測(cè)量的（例如Euclidean距離年扩、Mahalanobis距離、Manhattan距離）访圃，所以低維空間特征更少厨幻，分類更加容易。同樣地腿时，在高維空間的高斯分布會(huì)變平坦且尾巴更長(zhǎng)况脆。
三、如何避免維度災(zāi)難
圖1展示了隨著維度變得很大圈匆，分類器的性能是下降的漠另。那么問(wèn)題是“很大”意味著什么？過(guò)擬合如何避免跃赚？很遺憾笆搓，在分類問(wèn)題中性湿，沒(méi)有固定的規(guī)則來(lái)指定應(yīng)該使用多少特征。事實(shí)上满败，這依賴于訓(xùn)練樣本的數(shù)量肤频、決策邊界的復(fù)雜性和使用的是哪個(gè)分類器。
如果理論上訓(xùn)練樣本時(shí)無(wú)限多的算墨，那么維度災(zāi)難不會(huì)發(fā)生宵荒，我們可以使用無(wú)限多的特征來(lái)獲得一個(gè)完美的分類器。訓(xùn)練數(shù)據(jù)越少净嘀，使用的特征就要越少报咳。如果N個(gè)訓(xùn)練樣本覆蓋了1D特征空間的范圍，那么在2D中挖藏，覆蓋同樣密度就需要NN個(gè)數(shù)據(jù)暑刃，同樣在3D中，就需要NN*N個(gè)數(shù)據(jù)膜眠。也就是說(shuō)岩臣，隨著維度增加，訓(xùn)練樣本的數(shù)量要求隨指數(shù)增加宵膨。
此外架谎，那些非線性決策邊界的分類器（例如神經(jīng)網(wǎng)絡(luò)、KNN分類器辟躏、決策樹(shù)等）分類效果好但是泛化能力差且容易發(fā)生過(guò)擬合谷扣。因此，當(dāng)使用這些分類器的時(shí)候鸿脓，維度不能太高抑钟。如果使用泛化能力好的分類器（例如貝葉斯分類器、線性分類器）野哭，可以使用更多的特征在塔，因?yàn)榉诸惼髂Ｐ筒⒉粡?fù)雜。圖6展示了高維中的簡(jiǎn)單分類器對(duì)應(yīng)于地位空間的復(fù)雜分類器拨黔。
因此蛔溃，過(guò)擬合只在高維空間中預(yù)測(cè)相對(duì)少的參數(shù)和低維空間中預(yù)測(cè)多參數(shù)這兩種情況下發(fā)生。舉個(gè)例子篱蝇，高斯密度函數(shù)有兩類參數(shù)：均值和協(xié)方差矩陣贺待。在3D空間中，協(xié)方差矩陣是3x3的對(duì)稱陣零截，總共有6個(gè)值（3個(gè)主對(duì)角線值和3個(gè)非對(duì)角線值）麸塞，還有3個(gè)均值，加在一起涧衙，一共要求9個(gè)參數(shù)哪工；而在1D奥此，高斯密度函數(shù)只要求2個(gè)參數(shù)（1個(gè)均值，1個(gè)方差）雁比；在2D中稚虎，高斯密度函數(shù)要求5個(gè)參數(shù)（2個(gè)均值，3個(gè)協(xié)方差參數(shù)）偎捎。我們可以發(fā)現(xiàn)蠢终，隨著維度增加，參數(shù)數(shù)量呈平方式增長(zhǎng)茴她。
在之前的文章里我們發(fā)現(xiàn)寻拂，如果參數(shù)數(shù)量增加，那么參數(shù)的方差就會(huì)增大（前提是估計(jì)偏差和訓(xùn)練樣本數(shù)量保持不變）败京。這就意味著兜喻，如果圍度增加梦染，估計(jì)的參數(shù)方差增大赡麦，導(dǎo)致參數(shù)估計(jì)的質(zhì)量下降。分類器的方差增大意味著出現(xiàn)過(guò)擬合帕识。
另一個(gè)有趣的問(wèn)題是：應(yīng)該選擇哪些特征泛粹。如果有N個(gè)特征，我們應(yīng)該如何選取M個(gè)特征肮疗？一種方法是在圖1曲線中找到性能最佳的位置晶姊。但是，由于很難對(duì)所有的特征組合進(jìn)行訓(xùn)練和測(cè)試伪货，所以有一些其他辦法來(lái)找到最佳選擇们衙。這些方法稱之為特征選擇算法，經(jīng)常用啟發(fā)式方法（例如貪心算法碱呼、best-first方法等）來(lái)定位最佳的特征組合和數(shù)量蒙挑。
還有一種方法是用M個(gè)特征替換N個(gè)特征，M個(gè)特征由原始特征組合而成愚臀。這種通過(guò)對(duì)原始特征進(jìn)行優(yōu)化的線性或非線性組合來(lái)減少問(wèn)題維度的算法稱為特征提取忆蚀。一個(gè)著名的維度降低技術(shù)是主成分分析法（PCA），它去除不相關(guān)維度姑裂，對(duì)N個(gè)原始特征進(jìn)行線性組合馋袜。PCA算法試著找到低維的線性子空間，保持原始數(shù)據(jù)的最大方差舶斧。然而欣鳖，數(shù)據(jù)方差最大不一定代表數(shù)據(jù)最顯著的分類信息。
最后茴厉，一項(xiàng)非常有用的被用來(lái)測(cè)試和避免過(guò)擬合的技術(shù)是交叉驗(yàn)證泽台。交叉驗(yàn)證將原始訓(xùn)練數(shù)據(jù)分成多個(gè)訓(xùn)練樣本子集让网。在分類器進(jìn)行訓(xùn)練過(guò)程中，一個(gè)樣本子集被用來(lái)測(cè)試分類器的準(zhǔn)確性师痕，其他樣本用來(lái)進(jìn)行參數(shù)估計(jì)溃睹。如果交叉驗(yàn)證的結(jié)果與訓(xùn)練樣本子集得到的結(jié)果不一致，那么就表示發(fā)生了過(guò)擬合胰坟。如果訓(xùn)練樣本有限因篇，那么可以使用k折法或者留一發(fā)進(jìn)行交叉驗(yàn)證。
四笔横、結(jié)論
這篇文章我們討論了特征選擇竞滓、特征提取、交叉驗(yàn)證的重要性吹缔，以及避免由維度災(zāi)難導(dǎo)致的過(guò)擬合商佑。通過(guò)一個(gè)過(guò)擬合的簡(jiǎn)單例子，我們復(fù)習(xí)了維度災(zāi)難的重要影響厢塘。
我的CSDN博客地址：
http://blog.csdn.net/red_stone1/article/details/71692444
原文出處：
http://www.visiondummy.com/2014/04/curse-dimensionality-affect-classification/
