機器學習實驗報告

-.z.決策樹算法一、決策樹算法簡介：決策樹算法是一種逼近離散函數值的方法。它是一種典型的分類方法，首先對數據進展處理，利用歸納算法生成可讀的規(guī)則和決策樹，然后使用決策對新數據進展分析。本質上決策樹是通過一系列規(guī)則對數據進展分類的過程。決策樹方法的根本思想是：利用訓練集數據自動地構造決策樹，然后根據這個決策樹對任意實例進展判定。其中決策樹〔DecisionTree〕是一種簡單但是廣泛使用的分類器。通過訓練數據構建決策樹，可以高效的對未知的數據進展分類。決策數有兩大優(yōu)點：1〕決策樹模型可以讀性好，具有描述性，有助于人工分析；2〕效率高，決策樹只需要一次構建，反復使用，每一次預測的最大計算次數不超過決策樹的深度。決策樹算法構造決策樹來發(fā)現數據中蘊涵的分類規(guī)則．如何構造精度高、規(guī)模小的決策樹是決策樹算法的核心內容。決策樹構造可以分兩步進展。第一步，決策樹的生成：由訓練樣本集生成決策樹的過程。一般情況下，訓練樣本數據集是根據實際需要有歷史的、有一定綜合程度的，用于數據分析處理的數據集。第二步，決策樹的剪技：決策樹的剪枝是對上一階段生成的決策樹進展檢驗、校正和修下的過程，主要是用新的樣本數扼集〔稱為測試數據集〕中的數據校驗決策樹生成過程中產生的初步規(guī)則，將那些影響預衡準確性的分枝剪除、決策樹方法最早產生于上世紀60年代，到70年代末。由JRossQuinlan提出了ID3算法，此算法的目的在于減少樹的深度。但是忽略了葉子數目的研究。C4.5算法在ID3算法的根底上進展了改良，對于預測變量的缺值處理、剪枝技術、派生規(guī)則等方面作了較大改良，既適合于分類問題，又適合于回歸問題。本節(jié)將就ID3算法展開分析和實現。ID3算法：ID3算法最早是由羅斯昆〔J.RossQuinlan〕于1975年在悉尼大學提出的一種分類預測算法，算法的核心是"信息熵〞。ID3算法通過計算每個屬性的信息增益，認為信息增益高的是好屬性，每次劃分選取信息增益最高的屬性為劃分標準，重復這個過程，直至生成一個能完美分類訓練樣例的決策樹。在ID3算法中，決策節(jié)點屬性的選擇運用了信息論中的熵概念作為啟發(fā)式函數。在這種屬性選擇方法中，選擇具有最大信息增益〔informationgain〕的屬性作為當前劃分節(jié)點。通過這種方式選擇的節(jié)點屬性可以保證決策樹具有最小的分枝數量，使得到的決策樹冗余最小。偽代碼：二、實驗過程1.實驗數據集這個樣例集中，每個屬性都是離散值的，連續(xù)的屬性已經被離散化。將圖中的樣例集轉換成圖2中所示的格式并保存到文件中以供工程程序讀取數據。圖2中"attribute〞行所對應的是樣例集中的測試屬性和目標屬性，以及它們屬性值。而"data〞行后面的每一行數據則對應了樣例集中的一條樣例。測試屬性：outlook，天氣情況，屬性值為{sunny,overcast,rainy}；temperature，氣溫，屬性值為{hot,mild,cool}；humidity，濕度，屬性值為{high,normal}；Windy，是否有風，屬性值為{TRUE,FALSE}。目標屬性：Play，是否適合打球，屬性值為{yes,no}。RIDoutlooktemperaturehumiditywindyplay1sunnyhothighFALSEno2sunnyhothighTRUEno3overcasthothighFALSEyes4rainymildhighFALSEyes5rainycoolnormalFALSEyes6rainycoolnormalTRUEno7overcastcoolnormalTRUEyes8sunnymildhighFALSEno9sunnycoolnormalFALSEyes10rainymildnormalFALSEyes11sunnymildnormalTRUEyes12overcastmildhighTRUEyes13overcasthotnormalFALSEyes14rainyhighhighTRUEno輸出：圖3所示為本工程最終的輸出結果。工程的輸出結果詳細的給出了在構建決策樹的過程中候選屬性的信息增益、測試屬性的選取結果、測試屬性的各個屬性值所對應的分支、目標屬性選取結果以及目標概念buys_puter的決策樹JSON格式輸出，并使用工程生成的決策樹進展預測分析。根據生成的*ml文件畫出決策樹如下圖：2.實現步驟：第一步：從文件weather.arff中讀取測試樣例的屬性attribute和樣例數據data，方法voidreadARFF(Filefile)實現了數據的讀取這項工作。第二步：開場遞歸地創(chuàng)立決策樹。首先為樣例集中的每一個測試屬性分配一個權值，權值越小代表屬性的重要性越高。創(chuàng)立決策樹的過程中要計算樣本的總體熵，計算各個屬性的信息增益，將信息增益值最大的屬性定為測試屬性〔根結點〕，然后開場從根節(jié)點開場遞歸地創(chuàng)立子結點。實現代碼參考方法publicdoublecalEntropy(ArrayList<Integer>subset,intinde*)。第三步：輸出目標概念weather的決策樹*ml格式，此項需要引入包，編譯整個工程并運行生成決策樹。關鍵代碼：//給定原始數據的子集(subset中存儲行號),當以第inde*個屬性為節(jié)點時計算它的信息熵publicdoublecalEntropy(ArrayList<Integer>subset,intinde*) { intsum=subset.size(); doubleentropy=0.0; int[][]info=newint[attributevalue.get(inde*).size()][]; for(inti=0;i<info.length;i++) info[i]=newint[attributevalue.get(decatt).size()]; int[]count=newint[attributevalue.get(inde*).size()]; for(inti=0;i<sum;i++) { intn=subset.get(i); Stringnodevalue=data.get(n)[inde*]; intnodeind=attributevalue.get(inde*).inde*Of(nodevalue); count[nodeind]++; Stringdecvalue=data.get(n)[decatt]; intdecind=attributevalue.get(decatt).inde*Of(decvalue); info[nodeind][decind]++; } for(inti=0;i<info.length;i++){ entropy+=getEntropy(info[i])*count[i]/sum; } returnentropy; }//構建決策樹publicvoidbuildDecisionTree(Stringname,Stringvalue, ArrayList<Integer>subset,LinkedList<Integer>selatt) { Elementele=null; SuppressWarnings("unchecked") List<Element>list=root.selectNodes("http://"+name); Iterator<Element>iter=list.iterator(); while(iter.hasNe*t()) { ele=iter.ne*t(); if(ele.attributeValue("value").equals(value)) break; } if(infoPure(subset)) { ele.setTe*t(data.get(subset.get(0))[decatt]); return; } intminInde*=-1; doubleminEntropy=Double.MA*_VALUE; for(inti=0;i<selatt.size();i++){ if(i==decatt) continue; doubleentropy=calEntropy(subset,selatt.get(i)); if(entropy<minEntropy) { minInde*=selatt.get(i); minEntropy=entropy; } } StringnodeName=attribute.get(minInde*); selatt.remove(newInteger(minInde*)); ArrayList<String>attvalues=attributevalue.get(minInde*); for(Stringval:attvalues){ ele.addElement(nodeName).addAttribute("value",val); ArrayList<Integer>al=newArrayList<Integer>(); for(inti=0;i<subset.size();i++) { if(data.get(subset.get(i))[minInde*].equals(val)) { al.add(subset.get(i)); } } buildDecisionTree(nodeName,val,al,selatt); } }BP神經網絡BP神經網絡簡介在人工神經網絡開展歷史中，很長一段時間里沒有找到隱層的連接權值調整問題的有效算法。直到誤差反向傳播算法〔BP算法〕的提出，成功地解決了求解非線性連續(xù)函數的多層前饋神經網絡權重調整問題。BP網絡是1986年由Rumelhart和McCelland為首的科學家小組提出，是一種按誤差逆?zhèn)鞑ニ惴ㄓ柧毜亩鄬忧梆伨W絡，是目前應用最廣泛的神經網絡模型之一。BP網絡能學習和存貯大量的輸入-輸出模式映射關系，而無需事前提醒描述這種映射關系的數學方程。它的學習規(guī)則是使用最速下降法，通過反向傳播來不斷調整網絡的權值和閾值，使網絡的誤差平方和最小。BP神經網絡模型拓撲構造包括輸入層〔input〕、隱層(hidelayer)和輸出層(outputlayer)。算法原理由于傳統(tǒng)的感知器和線性神經網絡有自身無法克制的缺陷，它們都不能解決線性不可分問題，因此在實際應用過程中受到了限制。而BP網絡卻擁有良好的繁泛化能力、容錯能力以及非線性映射能力。因此成為應用最為廣泛的一種神經網絡。BP算法的根本思想是把學習過程分為兩個階段：第一階段是信號的正向傳播過程；輸入信息通過輸入層、隱層逐層處理并計算每個單元的實際輸出值；第二階段是誤差的反向傳遞過程；假設在輸入層未能得到期望的輸出值，則逐層遞歸的計算實際輸出和期望輸出的差值〔即誤差〕，以便根據此差值調節(jié)權值。這種過程不斷迭代，最后使得信號誤差到達允許或規(guī)定的*圍之內。基于BP算法的多層前饋型網絡模型的拓撲構造如上圖所示。BP算法的數學描述：三層BP前饋網絡的數學模型如上圖所示。三層前饋網中，輸入向量為：；隱層輸入向量為：；輸出層輸出向量為：；期望輸出向量為：。輸入層到隱層之間的權值矩陣用V表示，，其中列向量為隱層第j個神經元對應的權向量；隱層到輸出層之間的權值矩陣用W表示，，其中列向量為輸出層第k個神經元對應的權向量。下面分析各層信號之間的數學關系。對于輸出層，有對于隱層，有以上兩式中，轉移函數f(*)均為單極性Sigmoid函數：f(*)具有連續(xù)、可導的特點，且有以上共同構成了三層前饋網了的數學模型。當網絡輸出和期望輸出不相等時，存在輸出誤差E如下：將以上誤差定義式展開至隱層，有進一步展開至輸入層，有由上式可以看出，網絡輸入誤差是兩層權值W和V的函數，因此調整權值可以改變誤差E。顯然，調整權值的原則是使誤差不斷的減小，因此應使權值的調整量與誤差的負梯度成正比，即：式中負號表示梯度下降，常數表示比例系數，在訓練中反映了學習速率。容易看出，BP學習算法中，各層權值調整公式形式上都是一樣的，均有3個因素決定，即：學習速率、本層誤差信號和本層輸入信號*/Y。其中輸出層誤差信號同網絡的期望輸出與實際輸出之差有關，直接反映了輸出誤差，而各隱層的誤差信號與前面各層的誤差信號都有關，是從輸出層開場逐層反傳過來的。實驗實驗輸入與輸出：本次實驗做的是一個數字分類的實驗，目的是對于任意的整數〔int型〕，BPNN在經過訓練之后，能夠準確地判斷出它是奇數還是偶數，正數還是負數。首先對于訓練的樣本〔是隨機生成的數字〕，將它轉化為一個32位的向量，向量的每個分量就是其二進制形式對應的位上的0或1。將目標輸出視作一個4維的向量，[1,0,0,0]代表正奇數，[0,1,0,0]代表正偶數，[0,0,1,0]代表負奇數，[0,0,0,1]代表負偶數。訓練樣本為1000個，學習200次。實驗結果：如下圖，BPNN在經過訓練之后，能夠準確地判斷出它是奇數還是偶數，正數還是負數。關鍵代碼：privatevoidforward(double[]layer0,double[]layer1,double[][]weight){//thresholdunit.layer0[0]=1.0;for(intj=1,len=layer1.length;j!=len;++j){doublesum=0;for(inti=0,len2=layer0.length;i!=len2;++i)sum+=we