什么是線性回歸？
線性回歸（Linear regression）是一種利用線性函數(shù)對(duì)自變量（特征）和因變量之間的關(guān)系進(jìn)行建模的方法。線性回歸是機(jī)器學(xué)習(xí)中一種廣泛使用的基本回歸算法。含有有多個(gè)特征的線性回歸稱為多元線性回歸。
假設(shè)有 nn 個(gè)特征（自變量）x1x1,x2x2,...,xnxn，一個(gè)輸出變量 yy，線性回歸的一般形式表示如下：
y=f(x)=w1x1+w2x2+...+wnxn+b .(1)(1)y=f(x)=w1x1+w2x2+...+wnxn+b .
其中，系數(shù) w1w1,w2w2,...,wnwn 為特征的權(quán)重，bb 為偏置。
上式也可以寫成向量的形式：y=f(x)=wTx+b .(2)(2)y=f(x)=wTx+b .
其中，x=[x1,x2,...,xn]x=[x1,x2,...,xn],w=[w1,w2,...,wn]w=[w1,w2,...,wn].
看不懂吧，我也看不懂，直接上圖，有圖有真相。
藍(lán)色表示數(shù)據(jù)點(diǎn)，紅色直線表示最終求得的線性回歸結(jié)果。
幾種線性回歸算法：
最小二乘法：
• 它通過 最小化誤差的平方和 ，尋找數(shù)據(jù)的最佳函數(shù)匹配。
• 利用最小二乘法可以簡(jiǎn)便地求得未知的數(shù)據(jù)，并使得這些求得的數(shù)據(jù)與實(shí)際數(shù)據(jù)之間 誤差的平方 和 為最小。
• 假設(shè)我們現(xiàn)在有一系列的數(shù)據(jù)點(diǎn)(xi,yi) (i=1,…,m)，那么由我們給出的擬合函數(shù)h(x)得到的估計(jì)量就是h(xi)
• 殘差：ri = h(xi) – yi
• 三種范數(shù)：
1. ∞-范數(shù)：殘差絕對(duì)值的最大值，即所有數(shù)據(jù)點(diǎn)中殘差距離的最大值：
2. 1-范數(shù)：絕對(duì)殘差和，即所有數(shù)據(jù)點(diǎn)殘差距離之和：
3. 2-范數(shù)：殘差平方和：
• 擬合程度，用通俗的話來講，就是我們的擬合函數(shù)h(x)與待求解的函數(shù)y之間的相似性。那么
2-范數(shù)越小，自然相似性就比較高了。
所以式子就可以寫為：
分別對(duì)k和b求偏導(dǎo)，然后令偏導(dǎo)數(shù)為0，即可獲得極值點(diǎn)。
RANSAC：
• 隨機(jī)采樣一致性（random sample consensus）。
• RANSAC是一種思想 ，一個(gè)求解已知模型的參數(shù)的框架。 它不限定某一特定的問題，可以是計(jì) 算機(jī)視覺的問題，同樣也可以是統(tǒng)計(jì)數(shù)學(xué)，甚至可以是經(jīng)濟(jì)學(xué)領(lǐng)域的模型參數(shù)估計(jì)問題。
• 它是一種迭代的方法，用來在一組包含離群的被觀測(cè)數(shù)據(jù)中估算出數(shù)學(xué)模型的參數(shù)。 RANSAC是一個(gè)非確定性算法，在某種意義上說，它會(huì)產(chǎn)生一個(gè)在一定概率下合理的結(jié)果，其允許使用更多次的迭代來使其概率增加。
• RANSAC的基本假設(shè)是 “內(nèi)群”數(shù)據(jù)可以通過幾組模型參數(shù)來敘述其數(shù)據(jù)分布，而“離群”數(shù)據(jù)則是不適合模型化的數(shù)據(jù)。 數(shù)據(jù)會(huì)受噪聲影響,噪聲指的是離群，例如從極端的噪聲或錯(cuò)誤解釋有關(guān)數(shù)據(jù)的測(cè)量或不正確的假設(shè)。 RANSAC假定，給定一組（通常很小的）內(nèi)群，存在一個(gè) 程序，這個(gè)程序可以估算最佳解釋或最適用于這一數(shù)據(jù)模型的參數(shù)。
RANSAC算法的輸入:
1. 一組觀測(cè)數(shù)據(jù)（往往含有較大的噪聲或無效點(diǎn)），
2. 一個(gè)用于解釋觀測(cè)數(shù)據(jù)的參數(shù)化模型， 比如 y=ax+b
3. 一些可信的參數(shù)。
RANSAC 的步驟：
1. 在數(shù)據(jù)中隨機(jī)選擇幾個(gè)點(diǎn)設(shè)定為內(nèi)群
2. 計(jì)算適合內(nèi)群的模型 e.g. y=ax+b ->y=2x+3 y=4x+5
3. 把其它剛才沒選到的點(diǎn)帶入剛才建立的模型中，計(jì)算是否為內(nèi)群 e.g. hi=2xi+3->ri
4. 記下內(nèi)群數(shù)量
5. 重復(fù)以上步驟
6. 比較哪次計(jì)算中內(nèi)群數(shù)量最多,內(nèi)群最多的那次所建的模型就是我們所要求的解
注意 ： 不同問題對(duì)應(yīng)的數(shù)學(xué)模型不同，因此在計(jì)算模型參數(shù)時(shí)方法必定不同，RANSAC的作用不在于
計(jì)算模型參數(shù)。（這導(dǎo)致ransac的缺點(diǎn)在于要求數(shù)學(xué)模型已知）
這里有幾個(gè)問題：
1. 一開始的時(shí)候我們要隨機(jī)選擇多少點(diǎn)(n)
2. 以及要重復(fù)做多少次(k)
• 假設(shè)每個(gè)點(diǎn)是真正內(nèi)群的概率為 w：
w = 內(nèi)群的數(shù)目/（內(nèi)群數(shù)目+外群數(shù)目）
• 通常我們不知道 w 是多少, w^n是所選擇的n個(gè)點(diǎn)都是內(nèi)群的機(jī)率, 1-w^n 是所選擇的n個(gè)點(diǎn)至少有一個(gè)不是內(nèi)群的機(jī)率, (1 − w^n)^k 是表示重復(fù) k 次都沒有全部的n個(gè)點(diǎn)都是內(nèi)群的機(jī)率, 假設(shè)算法跑 k 次以后成功的機(jī)率是p，那么,
1 − p = (1 − w^n)^k
p = 1 − (1 − w^n)^k
• 我們可以通過P反算得到抽取次數(shù)K，K=log(1-P)/log(1-w^n)。
• 所以如果希望成功機(jī)率高：
• 當(dāng)n不變時(shí)，k越大，則p越大； 當(dāng)w不變時(shí)，n越大，所需的k就越大。
• 通常w未知，所以n 選小一點(diǎn)比較好。
RANSAC 的優(yōu)缺點(diǎn)：
優(yōu)點(diǎn)：
1. 它能魯棒的估計(jì)模型參數(shù)。例如，它能從包含大量局外點(diǎn)的數(shù)據(jù)集中估計(jì)出高精度的參數(shù)。
缺點(diǎn)：
1. 它計(jì)算參數(shù)的迭代次數(shù)沒有上限；如果設(shè)置迭代次數(shù)的上限，得到的結(jié)果可能不是最優(yōu)的結(jié)果，甚至可能得到錯(cuò)誤的結(jié)果。
2. RANSAC只有一定的概率得到可信的模型，概率與迭代次數(shù)成正比。
3. 它要求設(shè)置跟問題相關(guān)的閥值。
4. RANSAC只能從特定的數(shù)據(jù)集中估計(jì)出一個(gè)模型，如果存在兩個(gè)（或多個(gè)）模型，RANSAC不能找到別的模型。
5. 要求數(shù)學(xué)模型已知
RANSAC 與最小二乘法
• 生產(chǎn)實(shí)踐中的數(shù)據(jù)往往會(huì)有一定的偏差。
• 例如我們知道兩個(gè)變量X與Y之間呈線性關(guān)系，Y=aX+b，我們想確定參數(shù)a與b的具體值。通過實(shí)驗(yàn)，可以得到一組X與Y的測(cè)試值。雖然理論上兩個(gè)未知數(shù)的方程只需要兩組值即可確認(rèn)，但由于系統(tǒng)誤差的原因，任意取兩點(diǎn)算出的a與b的值都不盡相同。我們希望的是，最后計(jì)算得出的理論模型與測(cè)試值的誤差最小。
• 最小二乘法：通過計(jì)算最小均方差關(guān)于參數(shù)a、b的偏導(dǎo)數(shù)為零時(shí)的值。事實(shí)上，很多情況下，最小二乘法都是線性回歸的代名詞。
• 遺憾的是，最小二乘法只適合于誤差較小的情況。
• 在模型確定以及最大迭代次數(shù)允許的情況下，RANSAC總是能找到最優(yōu)解。（對(duì)于包含80%誤差的數(shù)據(jù)集，RANSAC的效果遠(yuǎn)優(yōu)于直接的最小二乘法。）
• 由于一張圖片中像素點(diǎn)數(shù)量大，采用最小二乘法運(yùn)算量大，計(jì)算速度慢。
哈希算法：
1. 均值哈希算法aHash
步驟
1. 縮放：圖片縮放為8*8，保留結(jié)構(gòu)，除去細(xì)節(jié)。
2. 灰度化：轉(zhuǎn)換為灰度圖。
3. 求平均值：計(jì)算灰度圖所有像素的平均值。
4. 比較：像素值大于平均值記作1，相反記作0，總共64位。
5. 生成hash：將上述步驟生成的1和0按順序組合起來既是圖片的指紋（hash）。
6. 對(duì)比指紋：將兩幅圖的指紋對(duì)比，計(jì)算漢明距離，即兩個(gè)64位的hash值有多少位是不一樣的，不相同位數(shù)越少，圖片越相似。
漢明距離
兩個(gè)整數(shù)之間的漢明距離指的是這兩個(gè)數(shù)字對(duì)應(yīng)二進(jìn)制位不同的位置的數(shù)目。
2. 差值哈希算法dHash
差值哈希算法相較于均值哈希算法，前期和后期基本相同，只有中間比較hash有變化。
步驟
1. 縮放：圖片縮放為 8*9 ，保留結(jié)構(gòu)，除去細(xì)節(jié)。
2. 灰度化：轉(zhuǎn)換為灰度圖。
3. 求平均值：計(jì)算灰度圖所有像素的平均值。 ---這步?jīng)]有，只是為了與均值哈希做對(duì)比
4. 比較：像素值大于后一個(gè)像素值記作1，相反記作0。本行不與下一行對(duì)比，每行9個(gè)像素，
八個(gè)差值，有8行，總共64位
5. 生成hash：將上述步驟生成的1和0按順序組合起來既是圖片的指紋（hash）。
6. 對(duì)比指紋：將兩幅圖的指紋對(duì)比，計(jì)算漢明距離，即兩個(gè)64位的hash值有多少位是不一樣的，不相同位數(shù)越少，圖片越相似。
3. 感知哈希算法pHash
均值哈希算法過于嚴(yán)格，不夠精確，更適合搜索縮略圖，為了獲得更精確的結(jié)果可以選擇感知哈希
算法，它采用的是DCT（離散余弦變換）來降低頻率的方法。
步驟：
1. 縮小圖片：32 * 32是一個(gè)較好的大小，這樣方便DCT計(jì)算
2. 轉(zhuǎn)化為灰度圖：把縮放后的圖片轉(zhuǎn)化為灰度圖。
3. 計(jì)算DCT:DCT把圖片分離成分率的集合
4. 縮小DCT：DCT計(jì)算后的矩陣是32 * 32，保留左上角的8 * 8，這些代表圖片的最低頻率。
5. 計(jì)算平均值：計(jì)算縮小DCT后的所有像素點(diǎn)的平均值。
6. 進(jìn)一步減小DCT：大于平均值記錄為1，反之記錄為0.
7. 得到信息指紋：組合64個(gè)信息位，順序隨意保持一致性。
8. 最后比對(duì)兩張圖片的指紋，獲得漢明距離即可。
離散余弦變換 DCT
| 
