大連理工大學(xué)人工智能課程小論文

大連底N大孕人工智能（小論文）專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)班級(jí)：電計(jì)1203學(xué)號(hào)：201281303姓名：劉陽(yáng)知識(shí)發(fā)現(xiàn)及數(shù)據(jù)挖掘中的決策樹(shù)方法及其應(yīng)用概述摘要：決策樹(shù)是一種用于分類、聚類和預(yù)測(cè)的預(yù)測(cè)型建模方法，對(duì)數(shù)據(jù)探查、分類等具有廣泛的適應(yīng)性。決策樹(shù)以樹(shù)形結(jié)構(gòu)來(lái)表示決策集合，由葉節(jié)點(diǎn)代表類或者類分布。由預(yù)分類組成的訓(xùn)練集經(jīng)過(guò)每一步最佳拆分生成決策樹(shù)。拆分的純度可以由基尼系數(shù)等方式衡量。為了獲得穩(wěn)定的決策樹(shù)需要進(jìn)行剪枝。引言：數(shù)據(jù)挖掘（DataMining，DM）是目前人工智能和數(shù)據(jù)庫(kù)領(lǐng)域研究的熱點(diǎn)問(wèn)題，所謂數(shù)據(jù)挖掘是指從數(shù)據(jù)庫(kù)的大量數(shù)據(jù)中揭示出隱含的、先前未知的并有潛在價(jià)值的信息的非平凡過(guò)程。數(shù)據(jù)挖掘是一種決策支持過(guò)程，它主要基于人工智能、機(jī)器學(xué)習(xí)、模式識(shí)別、統(tǒng)計(jì)學(xué)、數(shù)據(jù)庫(kù)、可視化技術(shù)等，高度自動(dòng)化地分析企業(yè)的數(shù)據(jù)，做出歸納性的推理，從中挖掘出潛在的模式，幫助決策者調(diào)整市場(chǎng)策略，減少風(fēng)險(xiǎn)，做出正確的決策。而決策樹(shù)是數(shù)據(jù)挖掘分類算法的一個(gè)重要方法。在各種分類算法中，決策樹(shù)是最直觀的一種正文：什么是數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn)數(shù)據(jù)是我們收集和存儲(chǔ)的，知識(shí)是幫助我們做決策的。從數(shù)據(jù)中提取知識(shí)稱為數(shù)據(jù)挖掘。數(shù)據(jù)挖掘也可以定義為在大量數(shù)據(jù)中進(jìn)行探索和分析，提取出有意義的模式和規(guī)則的過(guò)程。數(shù)據(jù)庫(kù)中的知識(shí)發(fā)現(xiàn)是指從大量數(shù)據(jù)中辨識(shí)出有效的、新穎的、潛在有用的并可理解的模式的高級(jí)處理過(guò)程?？梢钥闯觯瑪?shù)據(jù)發(fā)現(xiàn)的最終目標(biāo)是發(fā)現(xiàn)知識(shí)，而數(shù)據(jù)挖掘只是知識(shí)發(fā)現(xiàn)中的一個(gè)步驟。什么是決策樹(shù)2.1決策樹(shù)的定義決策樹(shù)是一種用于分類、聚類和預(yù)測(cè)的預(yù)測(cè)型建模方法。決策樹(shù)可以定義為推理過(guò)程的圖，它是一個(gè)預(yù)測(cè)模型，代表的是對(duì)象屬性與對(duì)象值之間的一種映射關(guān)系。決策樹(shù)方法著眼于從一組無(wú)次序、無(wú)規(guī)則的實(shí)例中推理出分類規(guī)則，是一種直觀的分類表示方法，同時(shí)也是高效的分類器，可以非常高效的產(chǎn)生分類規(guī)則。2.2.決策樹(shù)的結(jié)構(gòu)決策樹(shù)以樹(shù)形結(jié)構(gòu)來(lái)表示決策集合，其中包括內(nèi)部節(jié)點(diǎn)、分支和葉節(jié)點(diǎn)。決策樹(shù)的每一個(gè)非終葉節(jié)點(diǎn)表示所考慮的數(shù)據(jù)項(xiàng)的測(cè)試或決策。一個(gè)確定分支的選擇取決于測(cè)試的結(jié)果，代表一個(gè)測(cè)試輸出，而每個(gè)葉節(jié)點(diǎn)代表類或者類分布。為了對(duì)數(shù)據(jù)集分類，從根節(jié)點(diǎn)開(kāi)始，根據(jù)判定自頂向下，趨向終葉節(jié)點(diǎn)或葉節(jié)點(diǎn)。決策樹(shù)的生成3.1發(fā)現(xiàn)拆分首先，有一個(gè)預(yù)分類記錄組成的訓(xùn)練集，其中所有的目標(biāo)變量值都是已知的。我們的任務(wù)是生成一棵樹(shù)，基于輸入變量的數(shù)值給新紀(jì)錄的目標(biāo)字段指派一個(gè)類。遞歸執(zhí)行，我們?cè)诿恳粋€(gè)節(jié)點(diǎn)按照單一輸入字段的功能拆分紀(jì)錄可以建立樹(shù)，因而，在這里需要判斷哪一個(gè)輸入字段會(huì)產(chǎn)生最佳拆分。所謂最佳拆分，是指能夠把記錄很好的分割為不同的群組，是每個(gè)群組里的單個(gè)類成為主導(dǎo)。3.2生成完全樹(shù)決策樹(shù)建立算法通常始于在期望類別中試圖發(fā)現(xiàn)能夠最好的拆分?jǐn)?shù)據(jù)的輸入變量，即首次拆分產(chǎn)生兩個(gè)或更多的子節(jié)點(diǎn)，然后以與根節(jié)點(diǎn)相同的方式繼續(xù)拆分每一個(gè)子節(jié)點(diǎn)，在樹(shù)的每一后繼層，前一次拆分創(chuàng)建的子集本身按照最利于其工作的規(guī)則拆分，書繼續(xù)生長(zhǎng)，直到不可能發(fā)現(xiàn)更好的方法拆分新的記錄。3.3決策樹(shù)歸納這里列舉一種決策樹(shù)歸納的基本算法，是一種貪心算法。樹(shù)以代表訓(xùn)練樣本的單個(gè)節(jié)點(diǎn)開(kāi)始如果樣本都在同一個(gè)類，則該節(jié)點(diǎn)成為葉節(jié)點(diǎn)，并用該類標(biāo)記否則，算法使用信息增益（一種基于熵的度量）或者基尼（也稱整體發(fā)散性），選擇能夠最好的將樣本分類的屬性。將屬性作為該節(jié)點(diǎn)的“測(cè)試”或“判定”屬性。對(duì)測(cè)試屬性的每個(gè)已知的值，創(chuàng)建一個(gè)分枝，并據(jù)此劃分樣本。使用同樣的過(guò)程，遞歸的對(duì)每個(gè)劃分上的樣本生成樣本決策樹(shù)。當(dāng)遞歸到以下條件之一成立時(shí)停止1）給定節(jié)點(diǎn)的所有樣本屬于同一類2）沒(méi)有剩余的屬性可以用于進(jìn)一步的劃分樣本3）分枝沒(méi)有樣本3.4選擇最佳拆分的測(cè)試如3.1中所說(shuō)，最佳拆分是指能夠把記錄很好的分割為不同的群組，是每個(gè)群組里的單個(gè)類成為主導(dǎo)。那么，我們需要引入一個(gè)評(píng)價(jià)可能拆分的度量一一純度。低純度意味著該集合包含了各個(gè)類的典型分布，而高純度意味著但各類別的成員占主流。用于評(píng)價(jià)拆分分類目標(biāo)變量的純度度量包括：?基尼（也稱總體發(fā)散性）熵（也稱信息增益）?信息增益比率卡方檢驗(yàn)這些方法的具體使用超出了本文的范圍，也超出了筆者的知識(shí)水平，有意者可以翻閱相關(guān)書籍，如參考文獻(xiàn)［5］；另外還有一些拆分方法，如參考文獻(xiàn)［3］中基于粗糙集的方法。4決策樹(shù)的剪枝4.1為什么要進(jìn)行剪枝如前所述，只要能找到新的拆分，能夠改善把訓(xùn)練集中的記錄分割為更純的子集的能力，決策樹(shù)就會(huì)繼續(xù)長(zhǎng)高。這樣的決策樹(shù)已針對(duì)訓(xùn)練集進(jìn)行優(yōu)化，因而去掉任何葉節(jié)點(diǎn)都會(huì)增加該樹(shù)在訓(xùn)練集上的誤差率。但是事實(shí)上，并非完整的樹(shù)一定是最好的分類工具。決策樹(shù)算法首先在有大量記錄的根節(jié)點(diǎn)處做出最好的拆分，隨著節(jié)點(diǎn)變得越來(lái)越小，一個(gè)節(jié)點(diǎn)上特定訓(xùn)練記錄的特性開(kāi)始支配該過(guò)程?？梢赃@么理解，一棵樹(shù)在大節(jié)點(diǎn)處發(fā)現(xiàn)通用模式，而在小節(jié)點(diǎn)發(fā)現(xiàn)訓(xùn)練集的具體模式，導(dǎo)致該樹(shù)過(guò)度適應(yīng)于該訓(xùn)練集，結(jié)果將是一個(gè)不會(huì)做出好的預(yù)測(cè)的不穩(wěn)定的樹(shù)。解決這個(gè)問(wèn)題需要一個(gè)成為剪枝的過(guò)程。4.2剪枝的簡(jiǎn)單分類剪枝分預(yù)先剪枝和后剪枝兩種。預(yù)先剪枝是在樹(shù)的生長(zhǎng)過(guò)程中設(shè)定一個(gè)指標(biāo)，當(dāng)達(dá)到該指標(biāo)時(shí)就停止生長(zhǎng)，這樣做容易產(chǎn)生“視界局限”，就是一旦停止分支，使得節(jié)點(diǎn)N成為葉節(jié)點(diǎn)，就斷絕了其后繼節(jié)點(diǎn)進(jìn)行“好”的分支操作的任何可能性。不嚴(yán)格的說(shuō)這些已停止的分支會(huì)誤導(dǎo)學(xué)習(xí)算法，導(dǎo)致產(chǎn)生的樹(shù)不純度降差最大的地方過(guò)分靠近根節(jié)點(diǎn)。后剪枝中樹(shù)首先要充分生長(zhǎng)，直到葉節(jié)點(diǎn)都有最小的不純度值為止，因而可以克服“視界局限”。然后對(duì)所有相鄰的成對(duì)葉節(jié)點(diǎn)考慮是否消去它們，如果消去能引起令人滿意的不純度增長(zhǎng)，那么執(zhí)行消去，并令它們的公共父節(jié)點(diǎn)成為新的葉節(jié)點(diǎn)。這種合并小的葉節(jié)點(diǎn)以排除不穩(wěn)定的拆分的做法和節(jié)點(diǎn)分支的過(guò)程恰好相反，經(jīng)過(guò)剪枝后葉節(jié)點(diǎn)常常會(huì)分布在很寬的層次上，樹(shù)也變得非平衡。后剪枝技術(shù)的優(yōu)點(diǎn)是克服了“視界局限”效應(yīng)，而且無(wú)需保留部分樣本用于交叉驗(yàn)證，所以可以充分利用全部訓(xùn)練集的信息。通用的剪枝算法有：CART修剪算法、C5修剪算法等，這里不作展開(kāi)討論。從決策樹(shù)中提煉規(guī)則決策樹(shù)應(yīng)用簡(jiǎn)單舉例參考文獻(xiàn)：蔡自興，徐光祐《人工智能及其應(yīng)用》清華大學(xué)出版社MichaelNegnevitsky著顧力栩、沈晉惠等譯《人工智能智能系統(tǒng)指南》機(jī)械工業(yè)出版社鄒瑞芝，羅可，曾正亮《基于粗糙集理論的決策樹(shù)分類方法》計(jì)算機(jī)工程與科學(xué)2009年第31卷第10期1007-130X（2009）10-0112-03JiaweiHan,MichelineKa