【cs229-Lecture2】Linear Regression with One Variable (Week 1)(含测试数据和源码)
從Ⅱ到Ⅳ都在講的是線性回歸，其中第Ⅱ章講得是簡單線性回歸（simple linear regression, SLR）（單變量），第Ⅲ章講的是線代基礎，第Ⅳ章講的是多元回歸（大于一個自變量）。
本文的目的主要是對Ⅱ章中出現的一些算法進行實現，適合的人群為已經看完本章節Stanford課程的學者。本人只是一名初學者，盡可能以白話的方式來說明問題。不足之處，還請指正。
在開始討論具體步驟之前，首先給出簡要的思維路線：
1.擁有一個點集，為了得到一條最佳擬合的直線；
2.通過“最小二乘法”來衡量擬合程度，得到代價方程；
3.利用“梯度下降算法”使得代價方程取得極小值點；
首先，介紹幾個概念：
回歸在數學上來說是給定一個點集，能夠用一條曲線去擬合之。如果這個曲線是一條直線，那就被稱為線性回歸；如果曲線是一條二次曲線，就被稱為二次回歸，回歸還有很多的變種，如locally weighted回歸，logistic回歸等等。
課程中得到的h就是線性回歸方程：
下面，首先來介紹一下單變量的線性回歸：
問題是這樣的：給定一個點集，找出一條直線去擬合，要求擬合的效果達到最佳（最佳擬合）。
既然是直線，我們先假設直線的方程為：
???? 如圖：
??? 點集有了，直線方程有了，接下來，我們要做的就是計算出和，使得擬合效果達到最佳（最佳擬合）。
??? 那么，擬合效果的評判標準是什么呢？換句話說，我們需要知道一種對擬合效果的度量。
?? 在這里，我們提出“最小二乘法”：（以下摘自wiki）
最小二乘法（又稱最小平方法）是一種數學優化技術。它通過最小化誤差的平方和尋找數據的最佳函數匹配。
利用最小二乘法可以簡便地求得未知的數據，并使得這些求得的數據與實際數據之間誤差的平方和為最小。
對于“最小二乘法”就不再展開討論，只要知道他是一個度量標準，我們可以用它來評判計算出的直線方程是否達到了最佳擬合就夠了。
那么，回到問題上來，在單變量的線性回歸中，這個擬合效果的表達式是利用最小二乘法將未知量殘差平方和最小化：
結合課程，定義了一個成本函數：
其實，到這里，要是把點集的具體數值代入到成本函數中，就已經完全抽象出了一個高等數學問題（解一個二元函數的最小值問題）。
其中，a,b,c,d,e,f均為已知。
課程中介紹了一種叫“Gradient descent”的方法——梯度下降算法
兩張圖說明算法的基本思想：
所謂梯度下降算法（一種求局部最優解的方法），舉個例子就好比你現在在一座山上，你想要盡快地到達山底（極小值點），這是一個下降的過程，這里就涉及到了兩個問題：1）你下山的時候，跨多大的步子（當然，肯定不是越大越好，因為有一種可能就是你一步跨地太大，正好錯過了極小的位置）；2）你朝哪個方向跨步（注意，這個方向是不斷變化的，你每到一個新的位置，要判斷一下下一步朝那個方向走才是最好的，但是有一點可以肯定的是，要想盡快到達最低點，應從最陡的地方下山）。
那么，什么時候算是你到了一個極小點呢，顯然，當你所處的位置發生的變化不斷減小，直至收斂于某一位置，就說明那個位置就是一個極小值點。
?
so，我們來看的變化，則我們需要讓對求偏導，倒數代表變化率。也就是要朝著對陡的地方下山（因為沿著最陡顯然比較快），就得到了的變化情況：
簡化之后：
?
步長不宜過大或過小
梯度下降法是按下面的流程進行的：（轉自：http://blog.sina.com.cn/s/blog_62339a2401015jyq.html）
1）首先對θ賦值，這個值可以是隨機的，也可以讓θ是一個全零的向量。
2）改變θ的值，使得J(θ)按梯度下降的方向進行減少。
｛
??????? 為了方便大家的理解，首先給出單變量的例子：
?????? eg：求的最小值。（注：）
?????? java代碼如下：
·
package OneVariable;public class OneVariable{public static void main(String[] args){double e=0.00001;//定義迭代精度double alpha=0.5;//定義迭代步長double x=0; //初始化xdouble y0=2*x*x+3*x+1;//與初始化x對應的y值double y1=0;//定義變量，用于保存當前值while (true){x=x-alpha*(4.0*x+3.0);y1=2*x*x+3*x+1;if (Math.abs(y1-y0)<e)//如果2次迭代的結果變化很小，結束迭代 {break;}y0=y1;//更新迭代的結果 }System.out.println("Min(f(x))="+y0);System.out.println("minx="+x);} }//輸出 Min(f(x))=1.0 minx=-1.5｝
兩個變量的時候，為了更清楚，給出下面的圖：
這是一個表示參數θ與誤差函數J(θ)的關系圖，紅色的部分是表示J(θ)有著比較高的取值，我們需要的是，能夠讓J(θ)的值盡量的低。也就是深藍色的部分。θ0，θ1表示θ向量的兩個維度。
在上面提到梯度下降法的第一步是給θ給一個初值，假設隨機給的初值是在圖上的十字點。
然后我們將θ按照梯度下降的方向進行調整，就會使得J(θ)往更低的方向進行變化，如圖所示，算法的結束將是在θ下降到無法繼續下降為止。
當然，可能梯度下降的最終點并非是全局最小點，可能是一個局部最小點，可能是下面的情況：
上面這張圖就是描述的一個局部最小點，這是我們重新選擇了一個初始點得到的，看來我們這個算法將會在很大的程度上被初始點的選擇影響而陷入局部最小點?
一個很重要的地方值得注意的是，梯度是有方向的，對于一個向量θ，每一維分量θi都可以求出一個梯度的方向，我們就可以找到一個整體的方向，在變化的時候，我們就朝著下降最多的方向進行變化就可以達到一個最小點，不管它是局部的還是全局的。
?
理論的知識就講到這，下面，我們就用java去實現這個算法：
梯度下降有兩種：批量梯度下降和隨機梯度下降。詳見：http://blog.csdn.net/lilyth_lilyth/article/details/8973972
測試數據就用課后題中的數據（ex1data1.txt），用matlab打開作圖得到：
?
首先說明：以下源碼是不正確的，具體為什么不正確我還沒搞清楚！非常希望各位高手能夠指正！
測試數據及源碼下載：http://pan.baidu.com/s/1mgiIVm4
?
OneVariable.java1 package OneVariableVersion; 2 3 import java.io.IOException; 4 import java.util.List; 5 6 7 /** 8 * Linear Regression with One Variable 9 * @author XBW 10 * @date 2014年8月17日 11 */ 12 13 public class OneVariable{ 14 public static final Double e=0.00001; 15 public static List<Data> DS; 16 public static Double step; 17 public static Double m; 18 19 /** 20 * 計算當前參數是否符合 21 * @param ans 22 * @param datalist 23 * @return 24 */ 25 public static Ans calc(Ans ans){ 26 Double costfun; 27 do{ 28 costfun=calcAccuracy(ans); 29 ans=update(ans); 30 step*=0.3; 31 }while(Math.abs(costfun-calcAccuracy(ans))>e); 32 ans.ifConvergence=true; 33 return ans; 34 } 35 36 /** 37 * 判斷當前ans是否滿足精度,y=t0+t1*x 38 * @param ans 39 * @return 40 */ 41 public static Double calcAccuracy(Ans ans){ 42 Double cost=0.0; 43 Double tmp; 44 for(int i=0;i<m;i++){ 45 tmp=DS.get(i).y-(ans.theta[0]*DS.get(i).x[0]+ans.theta[1]*DS.get(i).x[1]); 46 cost+=tmp*tmp; 47 } 48 cost/=(2*m); 49 return cost; 50 } 51 52 /** 53 * 更新ans 54 * @param ans，學習速率為step，m為數據量 55 * @return 56 */ 57 public static Ans update(Ans ans){ 58 Double[] tmp=new Double[100] ; 59 for(int i=0;i<2;i++){ 60 tmp[i]=ans.theta[i]-step*fun(ans,i); 61 } 62 for(int i=0;i<2;i++){ 63 ans.theta[i]=tmp[i]; 64 } 65 return ans; 66 } 67 68 /** 69 * 計算偏導 70 * @return 71 */ 72 public static Double fun(Ans ans,int xi){ 73 Double ret = 0.0; 74 for(int i=0;i<m;i++){ 75 ret+=(ans.theta[0]*DS.get(i).x[0]+ans.theta[1]*DS.get(i).x[1]-DS.get(i).y)*DS.get(i).x[xi]; 76 } 77 ret/=m; 78 return ret; 79 } 80 81 public static void main(String[] args) throws IOException{ 82 DS=new DataSet().ds; 83 step=1.0; 84 m=(double)DS.size(); 85 86 87 Double[] theta={0.0,0.0}; //初始設定theta0=0,theta1=0 88 Ans ans=new Ans(theta,false); 89 Ans answer; 90 answer=calc(ans); 91 System.out.println("theta1= "+answer.theta[0]+" theta2="+answer.theta[1]); 92 } 93 }?
DataSet.java
?
1 package OneVariableVersion; 2 3 import java.io.BufferedReader; 4 import java.io.File; 5 import java.io.FileReader; 6 import java.io.IOException; 7 import java.util.ArrayList; 8 import java.util.List; 9 10 11 /** 12 * 數據處理 13 * @author XBW 14 * @date 2014年8月17日 15 */ 16 17 public class DataSet{ 18 String defaultpath="D:\\MachineLearning\\StanfordbyAndrewNg\\II.LinearRegressionwithOneVariable(Week1)\\homework\\ex1data1.txt"; 19 20 List<Data> ds=new ArrayList<Data>(); 21 22 public DataSet() throws IOException{ 23 File dataset=new File(defaultpath); 24 BufferedReader br = new BufferedReader(new FileReader(dataset)); 25 String tsing; 26 while((tsing=br.readLine())!=null){ 27 String[] dlist=tsing.split(","); 28 Data dtmp=new Data(Double.parseDouble(dlist[0]),Double.parseDouble(dlist[1])); 29 this.ds.add(dtmp); 30 } 31 br.close(); 32 } 33 }?
?
?
Ans.java
?
1 package OneVariableVersion; 2 3 /** 4 * 保存結果,y=t0+t1*x 5 * @author XBW 6 * @date 2014年8月17日 7 */ 8 9 public class Ans { 10 Double[] theta; 11 boolean ifConvergence; 12 13 public Ans(Double[] tmp,boolean ifCon){ 14 this.theta=tmp; 15 this.ifConvergence=ifCon; 16 } 17 }?
?
?
?
Data.java
?
1 package OneVariableVersion; 2 3 4 /** 5 * 一條數據 6 * @author XBW 7 * @date 2014年8月17日 8 */ 9 public class Data { 10 Double[] x=new Double[2]; 11 Double y; 12 13 public Data(Double xtmp,Double ytmp){ 14 this.x[0]=1.0; 15 this.x[1]=xtmp; 16 this.y=ytmp; 17 } 18 }?
?
?
?
?
?
總結：寫代碼的時候有幾個講究：
- 步長是否需要動態變化，按照coursera公開課上講的是不必要動態改變的，因為偏導數會越來越小，但在實際情況下，按照一定的比值縮小或者自己定義一種縮小的方式可能是有必要的，所以具體情況具體分析；
- 初始步長的設定也是很重要的，大了就不會得到結果，因為發散了；步長越大，下降速率越快，但是也會導致震蕩，所以，還是哪句話：具體問題具體分析；
轉載于:https://www.cnblogs.com/XBWer/p/3912792.html
總結
以上是生活随笔為你收集整理的【cs229-Lecture2】Linear Regression with One Variable (Week 1)(含测试数据和源码)的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 黄山风景区离机场多远
- 下一篇： 想找个人来陪是什么歌？