機(jī)器學(xué)習(xí)實(shí)驗(yàn)報(bào)告

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