最小二乘法的弊端

之前文章里的關(guān)于線性回歸的模型，都是基于最小二乘法來(lái)實(shí)現(xiàn)的。但是，當(dāng)數(shù)據(jù)樣本點(diǎn)出現(xiàn)很多的異常點(diǎn)（outliers），這些異常點(diǎn)對(duì)回歸模型的影響會(huì)非常的大，傳統(tǒng)的基于最小二乘的回歸方法將不適用。

當(dāng)然，可以考慮在做回歸分析之前，對(duì)數(shù)據(jù)做預(yù)處理，剔除掉那些異常點(diǎn)。但是，在實(shí)際的數(shù)據(jù)中，存在兩個(gè)問(wèn)題：

1. 異常點(diǎn)并不能很好的確定，并沒(méi)有一個(gè)很好的標(biāo)準(zhǔn)用于確定哪些點(diǎn)是異常點(diǎn)

2. 即便確定了異常點(diǎn)，但這些被確定為異常的點(diǎn)，真的是錯(cuò)誤的數(shù)據(jù)嗎？很有可能這看似異常的點(diǎn)，就是原始模型的數(shù)據(jù)，如果是這樣的話，那么這些異常的點(diǎn)就會(huì)帶有大量的原始模型的信息，剔除之后就會(huì)丟失大量的信息。

   
   

穩(wěn)健回歸

穩(wěn)健回歸（Robust regression），就是當(dāng)最小二乘法遇到上述的，數(shù)據(jù)樣本點(diǎn)存在異常點(diǎn)的時(shí)候，用于代替最小二乘法的一個(gè)算法。當(dāng)然，穩(wěn)健回歸還可以用于異常點(diǎn)檢測(cè)，或者是找出那些對(duì)模型影響最大的樣本點(diǎn)。

Breakdown point

關(guān)于穩(wěn)健回歸，有一個(gè)名詞需要做解釋?zhuān)築reakdown point，這個(gè)名詞我并不想翻譯，我也沒(méi)找到一個(gè)很好的中文翻譯。對(duì)于一個(gè)估計(jì)器而言，原始數(shù)據(jù)中混入了臟數(shù)據(jù)，那么，Breakdown point 指的就是在這個(gè)估計(jì)器給出錯(cuò)誤的模型估計(jì)之前，臟數(shù)據(jù)最大的比例 α，Breakdown point 代表的是一個(gè)估計(jì)器對(duì)臟數(shù)據(jù)的最大容忍度。

舉個(gè)簡(jiǎn)單的例子：有 n 個(gè)隨機(jī)變量，(X1,X2,…,Xn)， 其對(duì)應(yīng)的數(shù)據(jù)為(x1,x2,…,xn)，那么，我么可以求出這 n 個(gè)隨機(jī)變量的均值：

這個(gè)均值估計(jì)器的Breakdown point 為0，因?yàn)槭谷我庖粋€(gè)xi變成足夠大的臟數(shù)據(jù)之后，上面估計(jì)出來(lái)的均值，就不再正確了。

毫無(wú)疑問(wèn)，Breakdown point越大，估計(jì)器就越穩(wěn)健。

Breakdown point 是不可能達(dá)到 50% 的，因?yàn)槿绻傮w樣本中超過(guò)一半的數(shù)據(jù)是臟數(shù)據(jù)了，那么從統(tǒng)計(jì)上來(lái)說(shuō)，就無(wú)法將樣本中的隱藏分布和臟數(shù)據(jù)的分布給區(qū)分開(kāi)來(lái)。

本文主要介紹兩種穩(wěn)健回歸模型：RANSAC（RANdom SAmple Consensus 隨機(jī)采樣一致性）和Theil-Sen estimator。

RANSAC隨機(jī)采樣一致性算法

RANSAC算法的輸入是一組觀測(cè)數(shù)據(jù)（往往含有較大的噪聲或無(wú)效點(diǎn)），它是一種重采樣技術(shù)（resampling technique），通過(guò)估計(jì)模型參數(shù)所需的最小的樣本點(diǎn)數(shù)，來(lái)得到備選模型集合，然后在不斷的對(duì)集合進(jìn)行擴(kuò)充，其算法步驟為：

1. 隨機(jī)的選擇估計(jì)模型參數(shù)所需的最少的樣本點(diǎn)。

2. 估計(jì)出模型的參數(shù)。

3. 找出在誤差 ? 內(nèi)，有多少點(diǎn)適合當(dāng)前這個(gè)模型，并將這些點(diǎn)標(biāo)記為模型內(nèi)點(diǎn)

4. 如果內(nèi)點(diǎn)的數(shù)目占總樣本點(diǎn)的比例達(dá)到了事先設(shè)定的閾值 τ，那么基于這些內(nèi)點(diǎn)重新估計(jì)模型的參數(shù)，并以此為最終模型， 終止程序。

5. 否則重復(fù)執(zhí)行1到4步。

RANSAC算法是從輸入樣本集合的內(nèi)點(diǎn)的隨機(jī)子集中學(xué)習(xí)模型。

RANSAC算法是一個(gè)非確定性算法（non-deterministic algorithm），這個(gè)算法只能得以一定的概率得到一個(gè)還不錯(cuò)的結(jié)果，在基本模型已定的情況下，結(jié)果的好壞程度主要取決于算法最大的迭代次數(shù)。

RANSAC算法在線性和非線性回歸中都得到了廣泛的應(yīng)用，而其最典型也是最成功的應(yīng)用，莫過(guò)于在圖像處理中處理圖像拼接問(wèn)題，這部分在Opencv中有相關(guān)的實(shí)現(xiàn)。

從總體上來(lái)講，RANSAC算法將輸入樣本分成了兩個(gè)大的子集：內(nèi)點(diǎn)（inliers）和外點(diǎn)（outliers）。其中內(nèi)點(diǎn)的數(shù)據(jù)分布會(huì)受到噪聲的影響；而外點(diǎn)主要來(lái)自于錯(cuò)誤的測(cè)量手段或者是對(duì)數(shù)據(jù)錯(cuò)誤的假設(shè)。而RANSAC算法最終的結(jié)果是基于算法所確定的內(nèi)點(diǎn)集合得到的。

下面這份代碼是RANSAC的適用實(shí)例：

運(yùn)行結(jié)果為：

Theil-Sen Regression 泰爾森回歸

Theil-Sen回歸是一個(gè)參數(shù)中值估計(jì)器，它適用泛化中值，對(duì)多維數(shù)據(jù)進(jìn)行估計(jì)，因此其對(duì)多維的異常點(diǎn)（outliers 外點(diǎn)）有很強(qiáng)的穩(wěn)健性。

一般的回歸模型為：y=α+βx+?

其中，α,β 模型的參數(shù)，而 ? 為模型的隨機(jī)誤差。

Theil-Sen回歸則是這么處理的：

在實(shí)踐中發(fā)現(xiàn)，隨著數(shù)據(jù)特征維度的提升，Theil-Sen回歸的效果不斷的下降，在高維數(shù)據(jù)中，Theil-Sen回歸的效果有時(shí)甚至還不如OLS（最小二乘）。

在之間的文章《線性回歸》中討論過(guò)，OLS方法是漸進(jìn)無(wú)偏的，Theil-Sen方法在漸進(jìn)無(wú)偏方面和OLS性能相似。和OLS方法不同的是，Theil-Sen方法是一種非參數(shù)方法，其對(duì)數(shù)據(jù)的潛在分布不做任何的假設(shè)。Theil-Sen方法是一種基于中值的估計(jì)其，所以其對(duì)異常點(diǎn)有更強(qiáng)的穩(wěn)健性。

在單變量回歸問(wèn)題中，Theil-Sen方法的Breakdown point為29.3%，也就是說(shuō)，Theil-Sen方法可以容忍29.3%的數(shù)據(jù)是outliers。