機器學(xué)習(xí)實驗報告

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