數(shù)據(jù)挖掘-線性回歸

1、數(shù)據(jù)挖掘數(shù)據(jù)挖掘: :線性回歸線性回歸王成（副教授）王成（副教授）計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院主要內(nèi)容主要內(nèi)容線性回歸梯度下降算法線性最小二乘問題的矩陣解法最小二乘的概率解釋局部加權(quán)線性回歸有監(jiān)督的機(jī)器學(xué)習(xí)過程有監(jiān)督的機(jī)器學(xué)習(xí)過程輸出 y:fxy(貸款申請人信息)(是否可以批準(zhǔn)?)歷史數(shù)據(jù)學(xué)習(xí)算法:g xy輸出 y:g xy(是否可以批準(zhǔn)?)學(xué)習(xí)算法(貸款申請人信息)不可知假設(shè)(Hypothesis)，由學(xué)習(xí)得到，是f的近似機(jī)器學(xué)習(xí)的關(guān)鍵因素機(jī)器學(xué)習(xí)的關(guān)鍵因素1. 模式存在2. 但無法用數(shù)學(xué)方式確定下來3. 有數(shù)據(jù)可供學(xué)習(xí)有監(jiān)督的機(jī)器學(xué)習(xí)過程有監(jiān)督的機(jī)器學(xué)習(xí)過程:fxy:g xy擬

2、合數(shù)據(jù)點(diǎn)擬合擬合擬合: 指已知某函數(shù)的若干離散函數(shù)值，通過調(diào)整該函數(shù)中若干待定系數(shù)，使得該函數(shù)與已知點(diǎn)集的差別最小如果待定函數(shù)是線性，就叫線性擬合或者線性回歸分類與回歸分類與回歸分類問題: 目標(biāo)變量是離散值回歸問題: 目標(biāo)變量是連續(xù)值(數(shù)值預(yù)測)“回歸”是由達(dá)爾文的表兄弟弗朗西斯高爾頓爵士(Sir Francis Galton,1822-1911)發(fā)明的。高爾頓于1877年完成了第一次回歸預(yù)測，目的是根據(jù)上一代豌豆種子(雙親)的尺寸預(yù)測下一代豌豆種子的尺寸。高爾頓在大量對象上應(yīng)用了回歸分析，包括人的身高。他注意到，如果雙親的高度比平均高度高，他們的子女也傾向于比平均高度高，但尚不及雙親，孩子的

3、高度向著平均高度回退(回歸)。盡管這個(gè)單詞和數(shù)值預(yù)測沒有任何關(guān)系，但這種研究方法仍被稱為回歸。給定一套房屋的信息，如何預(yù)測其價(jià)格？房屋信息: (面積=100平, 三室, 兩衛(wèi))預(yù)測價(jià)格 = 0.8500 * 面積 + 0.0500 * 臥室數(shù)量 + 0.0015 * 衛(wèi)生間數(shù)量線性回歸線性回歸01 122( )h xxx1 (1)(1) 11 (1)(1) 10( )nTTiinnnnih xxxx 設(shè)x0=1x1yx2這個(gè)方程稱為回歸方程，i稱為回歸系數(shù)或權(quán)重房屋價(jià)格與其面積及臥室數(shù)量的統(tǒng)計(jì)數(shù)據(jù)線性回歸線性回歸( )( )211( )()2miiiJhxyy(i)表示第i個(gè)訓(xùn)練實(shí)例對應(yīng)的目標(biāo)

4、變量值，m為實(shí)例數(shù)量；常數(shù)1/2是為了方便后續(xù)計(jì)算；最小二乘(least squares)損失函數(shù)線性回歸線性回歸兩條不同的擬合直線線性回歸線性回歸( )( )211( )()2miiiJhxy計(jì)算回歸系數(shù)計(jì)算回歸系數(shù)主要內(nèi)容主要內(nèi)容線性回歸梯度下降算法線性最小二乘問題的矩陣解法最小二乘的概率解釋局部加權(quán)線性回歸梯度下降算法梯度下降算法梯度下降法梯度下降法(Gradient descent)是一個(gè)最優(yōu)化算法最優(yōu)化算法，通常也稱為最速下降法最速下降法。1847年由著名的數(shù)學(xué)家柯西給出假設(shè)我們爬山，如果想最快上到山頂，那么我們應(yīng)該從山勢最陡的地方上山。也就是山勢變化最快的地方上山同樣，如果從任意一

5、點(diǎn)出發(fā)，需要最快搜索到函數(shù)最大值最快搜索到函數(shù)最大值，那么我們也應(yīng)該從函數(shù)變化最快的方向搜索函數(shù)變化最快函數(shù)變化最快的方向是函數(shù)的梯度方向函數(shù)的梯度方向梯度下降算法梯度下降算法如果函數(shù)為一元函數(shù)，梯度就是該函數(shù)的導(dǎo)數(shù))()(xfxf如果為二元函數(shù)，梯度定義為12121212(,)(,)(,)y xxy xxfxxijxx梯度下降算法梯度下降算法要搜索極小值C點(diǎn):在A點(diǎn)必須向x增加方向搜索，此時(shí)與A點(diǎn)梯度方向相反；在B點(diǎn)必須向x減小方向搜索，此時(shí)與B點(diǎn)梯度方向相反。總之，搜索極小值，必須向負(fù)梯度方向搜索。梯度下降算法梯度下降算法- -步驟步驟假設(shè)函數(shù) 只有一個(gè)極小點(diǎn)。初始給定參數(shù)為 。從這個(gè)點(diǎn)如

6、何搜索才能找到原函數(shù)的極小值點(diǎn)？方法：12(,)nyfxxx(1) 101(,)Tnn1. 首先設(shè)定一個(gè)較小的正數(shù)，以及迭代次數(shù)k;2. 求當(dāng)前位置處的各個(gè)偏導(dǎo)數(shù)：( ),1 jfxjn3. 修改當(dāng)前函數(shù)的參數(shù)值，公式如下：( ),1 jjjfxjn4. 若參數(shù)變化量小于或已達(dá)迭代次數(shù)，退出；否則返回2梯度下降算法梯度下降算法- -舉例舉例例: 利用梯度下降法求函數(shù) 的極小值(1) 設(shè) (2) 計(jì)算導(dǎo)數(shù)：(3) 計(jì)算當(dāng)前導(dǎo)數(shù)值：(4) 修改當(dāng)前參數(shù)：4,01.0,9.002ddy6yddy4 .1)6(9 .044 .5)6(9 .0(5) 計(jì)算當(dāng)前導(dǎo)數(shù)值：6.0y(6) 修改當(dāng)前參數(shù)：ddy

7、94.1)6 .0(9 .04 .154.0)6 .0(9 .02212y梯度下降算法梯度下降算法- -舉例舉例(7) 計(jì)算當(dāng)前導(dǎo)數(shù)值：(8) 修改當(dāng)前參數(shù)：06.0yddy994.1)06.0(9 .094.1(9) 計(jì)算當(dāng)前導(dǎo)數(shù)值：(10) 修改當(dāng)前參數(shù)：006.0yddy9994.1)006.0(9 .0994.1(11)此時(shí)變化量滿足終止條件，終止054.0)06.0(9 .00054.0)006.0(9 .0梯度下降算法梯度下降算法( ):jjjJ其中稱為學(xué)習(xí)速率，即每次“前進(jìn)”的步長梯度下降算法梯度下降算法簡單起見，暫假設(shè)只有一個(gè)訓(xùn)練實(shí)例，則對j求偏導(dǎo)時(shí)，僅jxj一項(xiàng)不為常數(shù)，因此

8、求偏導(dǎo)的結(jié)果為xj0011jj x + x +.+ x +.+ x -ynnj( )( )( ):()iiijjjhxyx( ):jjjJ梯度下降算法梯度下降算法( )( )( ):()iiijjjyhxx梯度下降算法梯度下降算法應(yīng)用到不只一個(gè)訓(xùn)練實(shí)例的情況( )( )( )1:()miiijjjihxyx梯度下降算法舉例梯度下降算法舉例01 122( )h xxx0=0, 1=0, 2=0, h(x(i)=0, x0=1y(1)=400, y(2)=330, y(3)=369, y(4)=232, y(5)=540 x1(1)=2104, x1(2)=1600, x1(3)=2400, x1

9、(4)=1416, x1(5)=3000 x2(1)=3, x2(2)=3, x2(3)=3, x2(4)=2, x2(5)=40=0+0.01(y(1)-h(x(1)x0(1)+.+(y(5)-h(x(5)x0(5)1=0+0.01(y(1)-h(x(1)x1(1)+.+(y(5)-h(x(5)x1(5)2=0+0.01(y(1)-h(x(1)x2(1)+.+(y(5)-h(x(5)x2(5)x1yx2( )( )( )1:()miiijjjiyhxx隨機(jī)梯度下降算法隨機(jī)梯度下降算法批量梯度下降算法每一步都要考慮整個(gè)數(shù)據(jù)集以計(jì)算梯度，這在數(shù)據(jù)集較大時(shí)計(jì)算成本很高另一種可選的方案是一次僅用一個(gè)

10、樣本來更新回歸系數(shù)，該方法稱為隨機(jī)梯度下降算法隨機(jī)梯度下降算法(Stochastic gradient descent) 值的選擇值的選擇過大容易“越過”極值點(diǎn)，導(dǎo)致不收斂，過小則收斂速度慢隨著迭代次數(shù)的增加，一般要慢慢減小 (直觀上，一開始前進(jìn)快點(diǎn)，然后放慢速度)梯度下降算法梯度下降算法主要內(nèi)容主要內(nèi)容線性回歸梯度下降算法線性最小二乘問題的矩陣解法最小二乘的概率解釋局部加權(quán)線性回歸矩陣解法矩陣解法對于m*n矩陣A，定義關(guān)于A的函數(shù) f 的梯度:例如，其中第(i, j)個(gè)元素為 ijAAf)(23523)(2221212111111AAAAAAAf121210)(AAAf2221)(AAAf2

11、122)(AAAf矩陣解法矩陣解法n*n矩陣A的跡(trace)定義為A的主對角上元素之和，記為 tr AniiiAtrA1若a是一實(shí)數(shù)，即一個(gè)1x1矩陣，則 tr a = a性質(zhì)性質(zhì):trBAtrAB trBCDAtrCDABtrDABCtrABCDTtrAtrA trBtrABAtr)(atrAtraA TABtrAB 跡可理解為一個(gè)應(yīng)用在A上的函數(shù) f(A) = tr(A)TAAAfAfT)()(TTTAABCCABCtrABA矩陣解法矩陣解法(1)(1)(1)(1)12(2)(2)(2)(2)12()()()()121.()1.().1.()TnTnmmmmTnxxxxxxxxXxxx

12、x輸入矩陣(m * (n+1)維):目標(biāo)變量值向量(m維):)()2()1(.myyyy在房屋價(jià)格預(yù)測例子中，x1為“面積”屬性，x2為“臥室數(shù)量”屬性，x1(1)為第1個(gè)樣本的面積，x2(1)為第1個(gè)樣本的臥室數(shù)量，x1(2)為第2個(gè)樣本的面積，x2(2)為第2個(gè)樣本的臥室數(shù)量，共m個(gè)樣本，每個(gè)屬性有n個(gè)屬性在房屋價(jià)格預(yù)測例子中，y(1)為第1個(gè)樣本的報(bào)價(jià)，y(2)為第2個(gè)樣本的報(bào)價(jià)，共m個(gè)樣本假設(shè)共有m個(gè)訓(xùn)練樣本，每個(gè)樣本有n個(gè)屬性矩陣解法矩陣解法( )( )( )( )01 1().iiii Tnnhxxxx(1)(1)(1)(1)(2)(2)(2)(2)()()()()()()()()

13、.()()TTmmmmTxhxyyhxyyxyhxyyxX( )( )211() ()21()2( )TmiiiyyhxyJXX21nTiiz zz 矩陣解法矩陣解法為最小化 J，計(jì)算 J 的梯度() ()()()()()TTTTTTTTTTTTyyyyyyyyy yXXXXXXX XXX X是m(n+1)維= 一個(gè)數(shù)矩陣解法矩陣解法若a為一實(shí)數(shù)，則 tr a = a矩陣解法矩陣解法TTTTTTTTyyyXXXTtrtrAA()trtrtrABABTTTTTTtrytrytryXXXyyT矩陣解法矩陣解法TAAAfAfT)()(TTTAABCCABCtrABACBACABABCCtrABACt

14、rABATTTTTTTTTATATCABTATTBXXBEC TTTTtrX XX XX XTByXTABtrAB 22222TTTTTTtrytrytr yyy XXXXXtrBAtrAB 矩陣解法矩陣解法J( )0TTyX XXTTyX XX11()()TTTTyX XX XX XX1()TTy X XX1A AI主要內(nèi)容主要內(nèi)容線性回歸梯度下降算法線性最小二乘問題的矩陣解法最小二乘的概率解釋局部加權(quán)線性回歸最小二乘的概率解釋最小二乘的概率解釋為什么最小二乘代價(jià)函數(shù)J是一個(gè)合理的選擇？( )( )211( )()2miiiJhxy最小二乘的概率解釋最小二乘的概率解釋假設(shè)目標(biāo)變量和輸入的關(guān)系

15、可表示為：( )( )( )iTiiyx其中(i)表示線性模型與目標(biāo)值的誤差。例如樣本的某屬性和房價(jià)預(yù)測相關(guān)，但卻沒有被考慮進(jìn)來；或隨機(jī)噪音。最小二乘的概率解釋最小二乘的概率解釋假設(shè)誤差(i)獨(dú)立同分布(IID, Independent and Identical Distribution)，并服從正態(tài)分布：), 0(2)(Ni中心極限定理: 若一隨機(jī)變量受大量微小獨(dú)立的隨機(jī)因素影響，其中每個(gè)個(gè)別隨機(jī)變量對于總和的作用都是微小的，那么作為總和的隨機(jī)變量的分布就會逼近于正態(tài)分布。22)(2)()(21)(iepi因此，(i)的概率密度：( )( ) 22()( )( )21(|; )2iTiyx

16、iip yxe( )( )( )iiTiyx最小二乘的概率解釋最小二乘的概率解釋給定輸入矩陣X (每i行為第i個(gè)樣本的特征向量)和參數(shù)，可得到似然(likelihood)函數(shù):( )( ) 22( )( )1()21( )( ;, )( |; )(|; )12iTimiiiyxmiLLyp yp yxeXXm為樣本總數(shù)，(i)上標(biāo)表示第(i)個(gè)樣本最大似然法，也叫極大似然估計(jì)最小二乘的概率解釋最小二乘的概率解釋( )( ) 22( )( ) 22( )( ) 22()21()21()21( )( )221( )ln ( )1ln21ln21lnln2111ln()22iTiiTiiTiyxmi

17、yxmiyxmimiTiilLeememyx最小化( )( )211()2miTiiyx( )J最小二乘的概率解釋最小二乘的概率解釋基于前面的概率假設(shè)(IID，正態(tài)分布)，最小二乘回歸相當(dāng)于尋找最大化似然函數(shù)的。因此，最小二乘回歸可被證明是一種非常自然的選擇。主要內(nèi)容主要內(nèi)容線性回歸梯度下降算法線性最小二乘問題的矩陣解法最小二乘的概率解釋局部加權(quán)線性回歸局部加權(quán)線性回歸局部加權(quán)線性回歸使用更多合適的特征，例如y=0+1x+2x2可能可以擬合得更好考慮對數(shù)據(jù)集進(jìn)行線性擬合得到線性模型 y=0+1x數(shù)據(jù)點(diǎn)不在一條直線上，用線性模型擬合的并不好局部加權(quán)線性回歸局部加權(quán)線性回歸但也可能導(dǎo)致過擬合，例如

18、上圖為y=0+1x+.+5x5的擬合結(jié)果考慮對數(shù)據(jù)集進(jìn)行線性擬合得到線性模型 y=0+1x數(shù)據(jù)點(diǎn)不在一條直線上，用線性模型擬合的并不好局部加權(quán)線性回歸局部加權(quán)線性回歸局部加權(quán)線性回歸 (LWLR, Locally weighted linear regression):越靠近待預(yù)測點(diǎn)的訓(xùn)練樣本，對預(yù)測結(jié)果的影響越大，越遠(yuǎn)離待預(yù)測點(diǎn)的訓(xùn)練樣本，對預(yù)測結(jié)果的影響越小。只關(guān)注位于待預(yù)測點(diǎn)附近的樣本點(diǎn)(即“局部”的含義)給每個(gè)訓(xùn)練樣本賦予一個(gè)權(quán)重w(i)，訓(xùn)練樣本點(diǎn)離待預(yù)測點(diǎn)越近，w(i)越趨于1訓(xùn)練樣本點(diǎn)離待預(yù)測點(diǎn)越遠(yuǎn)，w(i)越趨于0局部加權(quán)線性回歸局部加權(quán)線性回歸直觀的理解，局部加權(quán)線性回歸在給定待預(yù)測點(diǎn)時(shí)，對其附近的點(diǎn)進(jìn)行訓(xùn)練得到局部線性模型，并用于預(yù)測局部加權(quán)線性回歸局部加權(quán)線性回歸直觀的理解，局部加權(quán)線性回歸在給定待預(yù)測點(diǎn)時(shí)，對其附近的點(diǎn)進(jìn)行訓(xùn)練得到局部線性模型，并用于預(yù)測局部加權(quán)線性回歸局部加權(quán)線性回歸直觀的理解，局部加權(quán)線性回歸在給定待預(yù)測點(diǎn)時(shí)，對其附近的點(diǎn)進(jìn)行訓(xùn)練得到局部線性模型，并用于預(yù)測局部加權(quán)線性回歸局部加權(quán)線性回歸線性回歸局部加權(quán)線性回歸1. 求擬合參數(shù)以最小化2. 輸出 Tx1. 求擬合參數(shù)以最小化2. 輸出 Tx 21miii