畢業(yè)論文《數(shù)據(jù)挖掘決策樹算法的研究與改進(jìn)(終稿)》

1、海南師范大學(xué)本科生畢業(yè)論文（設(shè)計(jì)）題目:決策樹算法的研究與改進(jìn)1=.si姓 名：學(xué) 號：專 業(yè)： 計(jì)算機(jī)科學(xué)與技術(shù)年 級：系 別：計(jì)算機(jī)科學(xué)與教育技術(shù)完成日期：指導(dǎo)教師：講師目錄2. 決策樹算法的研究22.1基本定義22. 1. 1.歸納學(xué)習(xí)的基本概念22. 1.2.信息論的基木概念22. 1.3.決策樹的基本概念32. 2.幾種常見的決策樹算法的簡單介紹42. 2. 1. id3 算法42.2. 2. c4. 5 算法簡介112. 2. 3.遺傳算法 ga (genet i c ai gor i thm)122.3. 決策樹的評價標(biāo)準(zhǔn)1132.4. 決策樹的進(jìn)展與發(fā)展方向152.4.1. 數(shù)

2、據(jù)挖掘中決策樹算法的主要進(jìn)展152.4. 2.決策樹技術(shù)面臨的挑戰(zhàn)及目前研究方向153關(guān)于決策樹算法的改進(jìn)153.1 基于樣本離散度6的特征選擇方法163. 1. 1.基本概念163.1.2. 基于離散度的改進(jìn)算法173.1.3. 分析與比較183. 1.4.小結(jié)183. 2.利用條件概率的思想來改進(jìn)決策樹算法183. 2. 1.算法的理論基礎(chǔ)與基本思想193.2. 2.舉例分析193.2. 3.分析與比較273. 2. 4.小結(jié)274總結(jié)285. 結(jié)朿語286. 致謝28參考文獻(xiàn)29挖掘決策樹算法的研究與改進(jìn)作者：張亞磊 指導(dǎo)老師：徐冬講師(海南師范大學(xué),?？?，571158)摘 要：在大量信

3、息展現(xiàn)給人們的時候，“知識爆炸”給人們帶來了極大的困擾，如何有效的利用數(shù)據(jù)成為人們事 業(yè)成敗的關(guān)鍵。本論文主要對決策樹的常見算法做初步的研究與探討，并給出決策樹的評價標(biāo)準(zhǔn)。并在此基礎(chǔ)上利 用最新的決策樹算法思想由本人設(shè)計(jì)實(shí)例集驗(yàn)證相關(guān)文獻(xiàn)中筆者的思想，最后提出自己一點(diǎn)意見和看法。關(guān)鍵詞：數(shù)據(jù)挖掘；決策樹；研究；改進(jìn)the research and improvement of data mining decision-makingtree algorithmauthor:yalei zhang tutor: dong xu lecturer(hainan normal university,h

4、aikou,571158)abstract： nowadays there arc so much information tounfbld in the people at present, which causes our eyes taking out all in, nthe knowledge explosion11 has brought the enormous puzzle to the people, how does the effective use data become the people enteiprise success or failure the key.

5、 this paper mainly discussed the preliminary research and the discussion to the policy-making tree's common algorithm, and produces the policy-making trcc*s evaluation criteria, as well as to policy-making tree future discussion. using the newest policymaking algorithm thought in this foundation

6、 to design in the example collection confirmation coitelation literature after myself authors thought, finally proposes a propose his viewpoint and the viewkey words： data mining; decision-making tree; research; improvement1. 引言隨著現(xiàn)代信息技術(shù)的飛速發(fā)展，在全球范圍內(nèi)掀起了信息化(infonnalion)浪潮。信息產(chǎn)牛的 渠道多而且寬廣，更新的頻率日益加快，各行業(yè)均產(chǎn)牛

7、了大量的信息?；貙Υ罅慷嗟臄?shù)據(jù)，人們往 往無法找到口己所需要的知識或信息，這就是所謂“信息爆炸” (information detonation)以及 它給人們帶來的困惑。如何有效地利用和處理大量的信息成為當(dāng)今世界共同關(guān)心的問題。隨著數(shù)據(jù) 庫技術(shù)(database technology) 人酣吉(artificial intelligence)、獨(dú)用鄉(xiāng)計(jì)(mathematical statistic) 和并行計(jì)算(parallel computation)等技術(shù)的發(fā)展與融合,數(shù)據(jù)挖掘(datamining, dm)技術(shù)應(yīng)運(yùn) 而生。自數(shù)據(jù)挖掘技術(shù)誕生以來，關(guān)于數(shù)據(jù)挖掘技術(shù)的研究也就開始了。數(shù)據(jù)挖

8、掘是一門新興的交叉 學(xué)科，白提出以來，引起了眾多專家學(xué)者的廣泛關(guān)注，數(shù)據(jù)開采(data mining)、數(shù)據(jù)采掘(data excavation)> 知識發(fā)現(xiàn)(knowledge discovery)和信息抽取(information extracts)等許多同義詞相 繼出現(xiàn)。目前，普遍采用的主要有數(shù)據(jù)挖掘(dm)和數(shù)據(jù)庫中的知識發(fā)現(xiàn)(knowledge discovery in database,簡稱kdd）。數(shù)據(jù)挖掘有廣義和狹義z分，廣義的數(shù)據(jù)挖掘，指從大量的數(shù)據(jù)中發(fā)現(xiàn) 隱藏的、內(nèi)在的和有用的知識或信息的過程。狹義的數(shù)據(jù)挖掘是指知識發(fā)現(xiàn)中的一個關(guān)鍵步驟，是 一個抽取有用模式或建立模型

9、的重要環(huán)節(jié)。數(shù)據(jù)挖掘是在對數(shù)據(jù)實(shí)例集全而而深刻認(rèn)識的基礎(chǔ)上, 對數(shù)據(jù)內(nèi)在利本質(zhì)的高度抽象與概括，也是對數(shù)據(jù)從感性認(rèn)識到理性認(rèn)識的升華2。如今有多種數(shù)據(jù)挖掘技術(shù)方法，可以分為兩大類。決策樹就是其中的-種，決策樹主要是基于 數(shù)據(jù)的屬性值進(jìn)行歸納分類，常用于分類的層次方法有“ifthenl”規(guī)則。決策樹方法的最大優(yōu) 點(diǎn)就是可理解性，比較直觀。它與神經(jīng)網(wǎng)絡(luò)（另外一種數(shù)據(jù)挖掘技術(shù)方法）最大的區(qū)別是，決策樹 可以解釋如何得出結(jié)果的決策過程。其缺點(diǎn)是處理復(fù)雜性的數(shù)據(jù)吋，分支數(shù)目非常多，管理難度大。 同時，還存在數(shù)據(jù)的“缺值”處理問題。其經(jīng)典算法有id3、c4.5、cart、chaid、sliq和sprint

10、 等。本論文主要對決策樹的常見算法（id3算法、c4.5算法）做初步的研究與探討，（由于遺傳算 法與決策樹的構(gòu)造類型相似，這里也有涉及。）并給出決策樹的評價標(biāo)準(zhǔn)以及決策樹的發(fā)展現(xiàn)狀和 以后的發(fā)展方向。并在此基礎(chǔ)上利用最新的決策樹算法思想山本人設(shè)計(jì)實(shí)例集驗(yàn)證相關(guān)文獻(xiàn)中筆者 的思想，最后提出自己一點(diǎn)意見和看法。2. 決策樹算法的研究2. 1.基本定義2. 1. 1.歸納學(xué)習(xí)的基本概念歸納學(xué)習(xí)（induction learning）是符號學(xué)習(xí)屮研究最為廣泛的一種方法。給定關(guān)于某個概念的 一系列已知的正例和反例，從屮歸納出一個通用的概念描述。歸納學(xué)習(xí)能夠獲得新的概念，創(chuàng)立新 的規(guī)則，發(fā)現(xiàn)新的理論。它的

11、一般操作是泛化（generalization）和特化（specialization）。泛化用 來擴(kuò)展一假設(shè)的語義信息，以使其能夠包含更多的正例，應(yīng)川于更多的情況。特化是泛化的相反操 作，用丁限制概念描述的應(yīng)用范圍。2. 1.2.信息論的基本概念信息論在決策樹學(xué)習(xí)中有著重要的意義，1948年sharmonl提出并發(fā)展了信息論，研究以數(shù)學(xué) 的方法度量并研究信息。通過通信后對信源中各種符號岀現(xiàn)的不確定程度的消除來度量信息量的大 小。他提出了一系列概念：（1）口信息量。在收到z前，收信者對信源發(fā)出的不確定性定義為信息符號的口信息量。即, 其中為信源發(fā)出的概率。（2）信息炳。自信息量只能反映符號的不確定

12、性，i何信息嫡可以用來度量信源x整體的不確定 性，定義如下：h （x） =p（a.） i （ai） +p （色）i（偽）+ +p（%）i（坷）r二-工/?（q）lo g（aj/=!其屮t為信源x所有可能的符號數(shù)，即川信源每發(fā)一個符號所提供的平均自信息童來定義信息 爛。（3）條件嫡。如果信源x與隨機(jī)變量y不是相互獨(dú)立的，收信者收到信息y。那么，用條件爛h （x/y）來度量收信者在收到隨機(jī)變彊y之后，対隨機(jī)變量x仍然存在的不確定性。設(shè)x対應(yīng)信源符號,y對應(yīng)信源符號，為當(dāng)y為時x為的概率，則有：h （x/y）二心小0*生 /bj/=! j=l（4）平均互信息量。川它來表示信號y所能提供的關(guān)于x的信息

13、良的人小，川i （x, y）表示:h （x, y） = h （x） -h （x/y）信息論的這些基本概念，對決策樹來說是非常蟲要的，是決策樹算法的設(shè)計(jì)與實(shí)現(xiàn)基礎(chǔ)。2. 1.3.決策樹的基本概念決策樹是定義布爾函數(shù)的一種方法，其輸入是一組屬性描述的對彖,輸出為yes/ no決策。它代 表一個假設(shè)，可以寫成邏輯公式。其表達(dá)能力限丁命題邏輯，該對象的任一個屬性的任一次測試均是 一個命題。在命題邏輯范圍內(nèi)，決策樹的表達(dá)能力是完全的。一棵決策樹可以代表一個決定訓(xùn)練實(shí) 例集分類的決策過程，樹的每個結(jié)點(diǎn)對應(yīng)于一個屬性名或一個特定的測試，該測試在此結(jié)點(diǎn)根據(jù)測 試的可能結(jié)果對訓(xùn)練實(shí)例集進(jìn)行劃分。劃分出的每個部分

14、都對應(yīng)于相應(yīng)訓(xùn)練實(shí)例集子空間的一個分 類子問題，該分類子問題可以由一棵決策樹來解決。因此，一棵決策樹可以看作是一個對目標(biāo)分類的 劃分和獲取策略。-棵決策樹的內(nèi)部結(jié)點(diǎn)是屬性或?qū)傩缘募希▉V稱測試屬性），葉結(jié)點(diǎn)是所要學(xué)習(xí)劃分的類。 根據(jù)決策樹各種不同的屬性，可分為以下兒種：（1）決策樹的內(nèi)結(jié)點(diǎn)的測試屬性可能是單變量的，即每個內(nèi)結(jié)點(diǎn)只包含一個屬性。也可能是 多變量的。（2）根據(jù)測試屬性的不同屬性值的個數(shù)，可能使得每個內(nèi)結(jié)點(diǎn)有兩個或多個分支。如果每個lw內(nèi)結(jié)點(diǎn)只有兩個分支則稱z為二叉決策樹。（3）每個屬性可能是值類型，也可能是枚舉類型。（4）分類結(jié)果既可能是兩類有可能是多類，如果只有兩類則稱為布爾決策

15、樹。因?yàn)闆Q策樹有不同的等價農(nóng)示形式，所以會有不同的算法來實(shí)現(xiàn)與決策樹學(xué)習(xí)相同的功能。例 如:id3、c4.5、cart、ch aid > sliq 和 sprint 等等。2. 2.幾種常見的決策樹算法的簡單介紹2.2.1. id3 算法2.2.1.1. id3算法簡介上面講到?jīng)Q策樹學(xué)習(xí)是一種歸納學(xué)習(xí)方法，這電介紹決策樹學(xué)習(xí)的核心算法一1d3算法，1d3 算法是在所有可能的決策樹空間中一種自頂向下、貪婪的搜索方法。id3算法的關(guān)鍵是確定屈性表 as中可對訓(xùn)練實(shí)例集es進(jìn)行的最佳分類的屬性a ,即在樹的每一個節(jié)點(diǎn)上確定一個候選屬性，它的 測試對訓(xùn)練例的分類最有利。id3搜索的假設(shè)空間是對能

16、的決策樹的集合，而id3搜索目的是構(gòu)造為 訓(xùn)練數(shù)據(jù)一致的一棵決策樹。id3的搜索策略是爬山法，在構(gòu)造決策樹時從簡單到復(fù)雜，用信息贏取 作為指導(dǎo)爬山法的評價函數(shù)。td3是基于信息爛的決策樹分類算法。自從quinlan描述和分析了td3算法以來，有大量的學(xué)者 圍繞該算法作了丁分廣泛的研究。該算法是根據(jù)屬性集的取值選擇實(shí)例的類別。它的核心是在決策 樹中各級結(jié)點(diǎn)上選擇屬性,川信息增益率作為屬性選擇標(biāo)準(zhǔn)，使得在每一非葉結(jié)點(diǎn)進(jìn)行測試時，能獲 得關(guān)于被測試?yán)幼钊说念悇e信息。使丿u該屬性將例子集分成了集后，系統(tǒng)的爛值最小，期槊該非葉 結(jié)點(diǎn)到達(dá)各后代葉節(jié)點(diǎn)的平均路徑最短，使生成的決策樹平均深度較小，提高分類速

17、度和準(zhǔn)確率。td3的基木原理如下：設(shè)e = f1 xf2 x-xfn是n維有窮向量空間，其中巧是有窮離散符號 集，e中的元素e = <vh v2,-, v>叫做例子，其中片丘耳,j二1,2,，n。設(shè)pe和ne是e的 f兩個例了集，分別叫正例集和反例集。假設(shè)向屋空間e中的正例集pe和反例集ne的人小分別為p和n , jld3基于下列兩個假設(shè)：（1）在向 量空間e上的一棵正確決策樹，對任意例子的分類概率同e屮的正、反例的概率一致;（2）-棵決策 樹能対一-例子做出正確類別判斷所需的信息量為：i （p, n） = log2 log2-p+np+斤p+n如果以屬性a作為決策樹的根，a具有v

18、個值（%,匕，匕），它將e分為v個子集（ee?,ev)，假設(shè)e；中含有pi個正例和耳個反例，子集&的信息爛為i(pi, 72,.),以屬性a為根分類后的信 息爛為:/=! p + n因此，以a為根的信息增益是gain (a) = t (p, n) - e(a)。id3選擇使gain (a)最大(即e(a) 最小)的屬性力作為根結(jié)點(diǎn)。對月的不同的取值對應(yīng)的e的v個子集耳遞歸調(diào)用上述過程，生成 /的子結(jié)點(diǎn),b, b?,by 0id3的基本原理是基于兩類分類問題，但很容易擴(kuò)展到多類。設(shè)樣本集s共有c類樣本，每類樣 本數(shù)為pi , ( i = 1 ,2 ,3 ,c) o若以屬性a作為決策樹的根

19、，a具有v個值, v2,-匕， 它將e分成v個子集厶，疋2,，& ，假設(shè)&中含有j類樣本的個數(shù)為心，j二1,2,c那么， 子集ej的信息量是i(£,.)o/(£,)=y-*iog-'臺i&i 1毘1以a為根分類的信息爛為：e(a)£*(eji=l i 匕 i選擇屬性必使e(a)最小,信息增益也將增大。理想的決策樹分成3種：(1)葉節(jié)點(diǎn)數(shù)最小，(2)葉節(jié)點(diǎn)深度最小；(3)葉節(jié)點(diǎn)數(shù)量最少且葉子結(jié) 點(diǎn)深度最小。決策樹的好壞，不僅影響分類的效率,而冃還影響分類的準(zhǔn)確率。因而許多學(xué)者致力于 尋找更優(yōu)的啟發(fā)式函數(shù)和評價函數(shù)，洪家榮、pei -

20、lei tu等人分別證明了要找到這種最優(yōu)的決策 樹是np難題。因此人們?yōu)榱藢で筝^優(yōu)的解，不得不尋求各種啟發(fā)式的方法。有的采用基于屬性相關(guān) 性的啟發(fā)式函數(shù);有的對生成的決策樹進(jìn)行剪枝處理;有的則擴(kuò)充決策樹,形成決策圖。如今普遍采用的是優(yōu)化算法，基本思想:首先用id3選擇屬性f1,建立樹t1,左、右子樹的屬性分 別為f2, f3,再以f2, f3為根,重建樹t2, t3;較tl, t2, t3的結(jié)點(diǎn)個數(shù)，選擇結(jié)點(diǎn)最少的樹。對于選擇定 樹的兒子結(jié)點(diǎn)采用同樣的方法遞歸建樹。盡管作者用一個實(shí)驗(yàn)證明能建立理想的決策樹，但算法有 較大的弱點(diǎn)：時間開銷太尢因?yàn)槊窟x擇一個新的屬性，算法都需要建立3棵決策樹，從中

21、選優(yōu)。2. 2. 1.2. id3算法實(shí)例例子一：這里我們通過考察不同的人群購買手機(jī)的狀況為例,來展示id3算法的實(shí)際流程。此例假定耍 按是否買手機(jī)對一個集合進(jìn)行分類，該集合中用來描述人郡的屬性有age. income, student和 credit-ratingo age 的取值為 youth、middle-aged, old； income 的取值為 high medium 和 low；student的取值為no和yes； credit-rating的取值為fair和excel 1 ento例子集中共有14個人， 如表1所示。在類別一欄，將正例即“買手機(jī)”的人用“y”標(biāo)出，反例即“不買手

22、機(jī)”的人用“n” 標(biāo)出。表1idageincomestudentcredit-ratingclass1vouthhighnofairn2youthhighnoexcellentn3middle-agedhighnofairy4oldmediumnofairy5oldlowyesfairy6old1 owyesexcellentn7middle-agedlowyesexcellenty8youthmediumnofairn9youthlowyesfairy10oldmediumyesfairy11youthmediumyesexcel lenty12middle-agedmediumnoexce

23、llenty13middle-agedhighyesfairy14oldmediumnoexcellentn首先利用公式i（p,n）二-一匕-log2-log2-計(jì)算樣本分類所需要的期望信息：p+np+np+n99551（ kp ） = t （9, 5）二-一log2log.=0. 940,然后計(jì)算每個屬性的炳。從且ge屬性1214“14 14 t4開始。需要觀察age的每個樣木值的y和n的分布。對每個分布計(jì)算期槊信息。對于age= "middleaged”對于age二"old”杳 3 分 25, 丫23)=0-971如果樣木按age劃分，對一個給定的樣木分類所需的期望信息

24、為：545e (age) t (乙,) + t () + t (,乙q)=。 694141112142122141323計(jì)算其信息增益為：gaincr, §)二1(匕，y2)- v. (age) =0.246類似地，計(jì)算gain (income) =0. 029, gain (student) =0. 151 和gain (credit-rating) =0. 048o（1此可知age在屈性中的信息增益最高，故選它做為測試屈性。創(chuàng)建根結(jié)點(diǎn)，用age標(biāo)記，并對每個屬值得引出一個分支。依次類推可得出決策樹如下圖:這些例了一開始全部包含在根結(jié)點(diǎn)屮，為了找出當(dāng)前的最佳劃分屬性，先須根據(jù)前述公

25、式計(jì)算studentstudent生成如卜決策樹分類規(guī)則:if age= “youth” and student = “no”then cl ass二 “n”if age= "middleaged”then class= “y”if age= “youth” and student = "yes”then class= “y”then class= “y”then class= “n”if age= "old" and credit-rating二 “fair”if age= "old" and credit-ratings &quo

26、t;excellent”例子二:這里我們通過考察?？谀承W(xué)牛的學(xué)習(xí)狀況為例，來展示id3算法的實(shí)際流程。此例假定要按 某校學(xué)生學(xué)習(xí)成績好壞這個概念對一個集合進(jìn)行分類,該集合小用來描述學(xué)生的屈性有性格、父母 教育程度和性別。性格的取值為外向、內(nèi)向。父母教育程度取值為良好、中等和差。性別的取值為 男牛、女牛。例子集中共有12名學(xué)牛，如表2所示。在類別一欄，將正例即“學(xué)習(xí)成績好”的學(xué)生用 “好”標(biāo)出，反例即“學(xué)牛成績差”的學(xué)牛用“差”標(biāo)出。表2 某學(xué)校學(xué)牛的例子集性格父母教育程度性別類別內(nèi)向良女生好外向良男生好外向中女生差內(nèi)向差女生差外向中男生好內(nèi)向良男生好外向差女生好外向差男生差外向良女生好內(nèi)向中

27、女生差內(nèi)向中男生差內(nèi)向差男生差這些例子一開始全部包含在根結(jié)點(diǎn)中，為了找出當(dāng)前的最佳劃分屬性，先須根據(jù)信息論中的公 式計(jì)算訓(xùn)練實(shí)例集es的炳值。則根節(jié)點(diǎn)的炳值為：曲"2)"善log 2卷一善log 2議下而分別計(jì)算例子集中各個屬性的信息贏取值。對屬性“性格”來說，分外向和內(nèi)向兩個分支。 當(dāng)v二“外向”時，有4名“外向”小學(xué)生是“學(xué)習(xí)成績好”的，有2名“外向”小學(xué)生是“學(xué)習(xí)成績差”的。因此,4422entropy（es 性格外向）=一 $ log 2 帀-log 2 幣= 0.9183當(dāng)v二“內(nèi)向”時，有2名“內(nèi)向”小學(xué)生是“學(xué)習(xí)成績好”的，有4名“內(nèi)向”小學(xué)生是“學(xué)習(xí)成績差”

28、的。因此,4422entropye 內(nèi)向）二石log 2帀-log 2 = 0.9183所以根據(jù)“性格”屬性來進(jìn)行例子集分類的信息贏取值為：gain （es,性格）=entropy （es）-entropy （esv,格）=1 -（*0.9183+丄*0.9183）=0.08172 2同理，對“父母教育程度”來說:gain（es,父母教育程度）=0. 4591 ;對"性別”來說:gain（ es,性別）=0。因?yàn)間ain （ es ,性別） gain （ es ,性格）gain （ es ,父母教育程度）可以看出以“父 母教冇程度”這個屬性進(jìn)行例子集分類的信息贏取值最大，于是“父母教

29、冇程度”就被選為用于劃 分的屬性，得到如卜圖所示的決策樹。r好好妹 4:1:也生 女男男女 , , , , 良良良、li , , , , 向向向向 帀外內(nèi)廠丙向, 外向, 內(nèi)向,中，女生：粵 中，男生：好i中，男生:差 中,女生:差丿f向, 外向, 內(nèi)向, 外向,差, 差, 差, 差,按“父母教育程度”劃分后的決策樹現(xiàn)在必須根據(jù)所提供的信息進(jìn)一步分析“父母教育程度”為“中”或“差”的小學(xué)牛的“學(xué)習(xí) 成績好壞”，因此必須對“中”和“差”兩個分支的實(shí)例組成的例子集（共8個例子）重復(fù)上述計(jì)算 過程。這里簡化計(jì)算過程，算出：gain（es,性格）=0.3113和gain（es,性別）二0.2045。因

30、為gain （ es，性別） gain （ es ,性格），所以用屬性“性格”作第二步劃分，于是得到如 下圖所示的決策樹。向向向向向向男生:女生:父母教育程度4:4:生蟲 女男男女 , , , 良良良良生生 女男 f f性格外向內(nèi)向'石向，'差，女生：斥:”向，差，男生：差外向，差，女生：好 外向，差，男生：差按“性格”作第二次劃分后的決策樹現(xiàn)在只有“父母教育程度”為“屮”和“差”的“外向”小學(xué)生還沒有明確類別，它們要川屬 性“性別”來進(jìn)一步劃分。最終得到的決策樹如下圖所示。r良良良 , , , , 向向向向內(nèi)向，中，女生: 內(nèi)向，中，男牛:性別性格父母教育程度電也生牝 女男男

31、女性格性別男生"女生外向，中，男牛：好外向，中，女生一男生女生:差外向,差,男生:差外向,差，女生:好then學(xué)習(xí)成績二“好”then學(xué)習(xí)成績二“差”then學(xué)習(xí)成績二“差”then學(xué)習(xí)成績二“差”then學(xué)習(xí)成績二“好”then學(xué)習(xí)成績二“好”then學(xué)習(xí)成績二“差”最終得到的決策樹if父母教育程度二“良”if父母教育程度二“中” and性格二“內(nèi)向”if父母教育程度二“差” and性格二“內(nèi)向”if父母教育程度二“中” and性格二“外向” and性別二“女生”if父母教育程度二“中” and性格二“外向” and性別二“男生”if父母教育程度二“差” and性格二“外向” an

32、d性別二“女生”if父母教育程度二“差” and性格=“外向” and性別二“男生”但是不能保證1d3算法對任何問題總能做出最佳選擇，只能說它在一般情況下能夠找出最優(yōu)決 策樹。這是1d3算法的最人缺點(diǎn)。2. 2. 1.3. id3算法的優(yōu)缺點(diǎn)這里対id3算法作一些總結(jié)：id3通過不斷的循環(huán)處理，逐步求精決策樹，直到找到一個完全止確 的決策樹。id3算法構(gòu)造的決策樹是從頂向下歸納形成了一組類似if -then的規(guī)則。其最原始的程 序只是用來區(qū)分象棋中的走步，所以區(qū)分的類別只有兩種t或f ,其屬性值也是一些離散有限的值， 而今1d3算法已發(fā)展到允許多于兩個類別，而其屬性值可以是整數(shù)或?qū)崝?shù)。下面歸納

33、總結(jié)出1d3算法 的優(yōu)缺點(diǎn)如卞：優(yōu)點(diǎn):搜索空間是完全的假設(shè)空間，忖標(biāo)函數(shù)必在搜索空間中，不存在無解的危險;全盤使用訓(xùn) 練數(shù)據(jù)，而不是像候選剪除算法一個一個地考慮訓(xùn)練例。這樣做的優(yōu)點(diǎn)是可以利用全部訓(xùn)練例的統(tǒng) 計(jì)性質(zhì)進(jìn)行決策，從而抵抗噪音。缺點(diǎn):搜索中只維持一個解，不能像候選剪除算法那樣返冋所有口 j能的與練例集一致的假設(shè)，并 優(yōu)化地杏詢新例以獲得收斂于目標(biāo)函數(shù)的解;其搜索無冋溯它可能收斂于局部最優(yōu)解而丟失全局最 優(yōu)解，因?yàn)橐粋€一個地考慮訓(xùn)練例,不容易象剪除算法那樣使用新例步進(jìn)式地改進(jìn)決策樹。2.2. 1.4. id3算法的發(fā)展11)3算法在實(shí)際應(yīng)用中解決了許多問題，對于非增量式學(xué)習(xí)任務(wù)，id3算

34、法常常是建立決策樹的 很好的選擇。但對于增暈式學(xué)習(xí)任務(wù)來說，h于id3不能增量地接受訓(xùn)練例，這就使得每增加一次實(shí) 例都必須拋棄原有決策樹，匝新構(gòu)造新的決策樹,造成了極大的開銷。于是id3算法被quinlanel 自己擴(kuò)充為c4. 5法,c4. 5算法每接受一個新的訓(xùn)練例就更新一次決策樹。在c4. 5的決策樹屮，每個結(jié) 點(diǎn)都保存了可用于計(jì)算e值的屈性的信息，這些信息由屬性的每個取值所對應(yīng)的正例、反例計(jì)數(shù)組 成。根據(jù)放在結(jié)點(diǎn)的信息,就可以判斷出哪個屬性的訓(xùn)練例集es值最小，從而確定當(dāng)前用哪一個屬性 來進(jìn)行劃分。c4. 5算法使用了一個適合小數(shù)據(jù)量的方法:基于訓(xùn)練例口身的性能估計(jì)。當(dāng)然訓(xùn)練例進(jìn)行估計(jì)

35、 很可能產(chǎn)牛偏向于規(guī)則的結(jié)果，為了克服這一點(diǎn),c4. 5算法采用了保守佔(zhàn)計(jì)。它采用的具體方法是： 計(jì)算規(guī)則對其使用的各個訓(xùn)練例分類的精度a ,然后計(jì)算這個秸度的二項(xiàng)分布的標(biāo)準(zhǔn)差s ,最后對給 定信任度(95 %),取下界(a-1.96)為該規(guī)則的性能度量pa；在有大量數(shù)據(jù)的情況下,s接近于0, pa 接近于a ;隨著數(shù)據(jù)量的減少,pams的差別將會增大。c4. 5算法使用更復(fù)雜的方法是為屬性a的各 種取值賦以概率,具有未知屈性a值的實(shí)例x按概率值分為大小不等的碎片，沿相應(yīng)屬性a值的分 支向樹的下方分布，實(shí)例的碎片將用于計(jì)算信息贏取。這個實(shí)例處片在學(xué)習(xí)后,還可以用來對屬性值 不全的新實(shí)例進(jìn)行分類

36、。下而就c4. 5算法的基木思想做簡要的概述。2.2.2. c4. 5算法簡介c4.5算法是在1d3的基礎(chǔ)上改進(jìn)而成的，它繼承了jld3的全部優(yōu)點(diǎn)，更好地修正了 1d3的剪枝算 法并對高分支屬性、數(shù)值型屬性和含空值屬性地整理有了系統(tǒng)地描述。例如cn4. 5屮也采川“窗口” (windows )的概念，先從所有的雷例屮選取一部分川做構(gòu)造決策樹，再利川剩余的事例測試決策樹 并對它進(jìn)行調(diào)整。cn4. 5算法能處理連續(xù)值類型的屈性，它還能對屬性的取值集合進(jìn)行等價類劃分， 劃分在同一類的屬性值在屬性值判斷時將走到同一分支上。再加上cn4. 5算法的思想簡單，實(shí)現(xiàn)高效, 結(jié)杲可靠，使cn4. 5在歸納學(xué)習(xí)

37、中的地位更加顯著。但是cn 4. 5算法也有如卞不足之處：笫一，cn4. 5采用的是分而治z的策略，在構(gòu)造樹的內(nèi)部結(jié)點(diǎn)的時候是局部最優(yōu)的搜索方式。所 以它所得到的最終結(jié)杲盡管有很高的準(zhǔn)確性，仍然得不到全局最優(yōu)的結(jié)果。第二，在cn4. 5評價決策最主要的依據(jù)是決策樹的錯誤率，而対樹的深度,結(jié)點(diǎn)的個數(shù)等不進(jìn)行 考慮，而樹平均深度直接對應(yīng)著決策樹的預(yù)測速度，樹的結(jié)點(diǎn)個數(shù)則代表樹的規(guī)模。第三，一邊構(gòu)造決策樹,一邊迓行評價，決策樹構(gòu)造出來之后,很難再調(diào)整樹的結(jié)構(gòu)和內(nèi)容，決策 樹性能的改善十分困難。笫四，cn4. 5在進(jìn)行屈性值分組時逐個試探，沒有一種使川啟發(fā)搜索的機(jī)制，分組時的效率較 低。2. 2. 3

38、.遺傳算法 ga (genet ic al gor i thm)遺傳算法是一種通用搜索算法。它通過模擬自然界進(jìn)化的過程來演化出解決問題的較優(yōu)方法。 它把一些解決方案用一定的方式來表示，放在一起稱為群體(population)。每-個方案的優(yōu)劣程度 即為適應(yīng)性(fit2ness),根據(jù)自然界進(jìn)化的“優(yōu)勝劣汰”的原則，逐步產(chǎn)生出它們的后代，使后代具 有更強(qiáng)的適應(yīng)性。這樣不斷演化下去,就能得到更優(yōu)的解決方案。它具有思想簡明、健壯性好等特 點(diǎn)。在工農(nóng)業(yè)、經(jīng)濟(jì)政治、科研方而應(yīng)用極為廣泛。在計(jì)算機(jī)科學(xué)領(lǐng)域中的機(jī)器學(xué)習(xí)領(lǐng)域更是人有 用武z地。群體搜索策略和個體z間的信息交換是遺傳算法的兩大特點(diǎn)，主要表現(xiàn)在全

39、局最優(yōu)性和潛在的 并行性。cn4. 5在構(gòu)造決策樹時并不一定得到最優(yōu)的決策樹，那么是不是能用遺傳算法的思想能夠得 到解決呢，回答是肯定的。雖然遺傳算法的進(jìn)發(fā)結(jié)果并不能保證得到理論意義上的最佳的決策樹， 但是它提供了一種試探的過程。由丁適者牛存的特點(diǎn)，使得適應(yīng)性較優(yōu)的決策樹能盡量保留，乂由于 它捉供了對決策樹的調(diào)整和車新組合的機(jī)制,使得有更優(yōu)適應(yīng)性的決策樹在進(jìn)發(fā)過程中岀現(xiàn)。那么 如何應(yīng)用遺傳算法,如何基于決策樹的結(jié)構(gòu)和性質(zhì)定義遺傳算子呢？遺傳算子主要有三種：復(fù)制(reproduction)、重組(crossover)、算子和變異(mutation)算 子。一般的算子都是對特征串進(jìn)行操作的。針對決

40、策樹的結(jié)構(gòu)和特性，我們定義遺傳算子:首先定義 適應(yīng)函數(shù)(fitness function)。遺傳算法是一個探索過程,它對樹的評價是在樹完全作成以后進(jìn)行 的，可以將樹的深度、結(jié)點(diǎn)數(shù)等因素都考慮在內(nèi)。復(fù)制算子的定義與常用的復(fù)制算子的定義一致。重組算子的定義就要用到?jīng)Q策樹結(jié)構(gòu)特點(diǎn)。我 們有以下兒種重組方式：(1)用后代結(jié)點(diǎn)代替祖先結(jié)點(diǎn)，類似于書的剪枝操作。(2)同一棵樹的兩 個結(jié)點(diǎn)互相交換。(3)兩個樹z間結(jié)點(diǎn)交換,這里所說的結(jié)點(diǎn)交換就是交換以這些結(jié)點(diǎn)為根的子樹。變異是產(chǎn)生全局最優(yōu)的重要原因，盡管大多數(shù)的變異不能產(chǎn)生良好的效果，對于決策樹，我們定 義的變異算子是改變樹的結(jié)構(gòu)或者改變樹中結(jié)點(diǎn)內(nèi)的信息。

41、針對內(nèi)部結(jié)點(diǎn)和葉節(jié)點(diǎn),屬性值的分組 與否這些不同情況，變異的處理是不一樣的。對于內(nèi)部結(jié)點(diǎn)內(nèi)，變異操作可能產(chǎn)牛下血的結(jié)果：(1) 改變結(jié)點(diǎn)上判斷的屬性。(2) 改變屬性值的分組情況。(3) 改變該結(jié)點(diǎn)下的子樹的分支情況，改變屬性值與分支子樹的對應(yīng)。(4) 改變該結(jié)點(diǎn)的分支數(shù)。這樣經(jīng)過重組、變異算子運(yùn)算得到的新的決策樹需要迓行結(jié)構(gòu)上的完整性和一致性處理。調(diào)整 變異結(jié)點(diǎn)及其子結(jié)點(diǎn)的樹結(jié)構(gòu)使z為一-棵完整的正確的決策樹;去除從樹根到葉節(jié)點(diǎn)路徑上重復(fù)的 屈性判斷等。決策樹的構(gòu)造分為以下兒步：(1) 第一-代群體的產(chǎn)生；(2) 產(chǎn)生下一代；(3) 產(chǎn)牛最優(yōu)決策樹。2. 3.決策樹的評價標(biāo)準(zhǔn)1以上討論了一些

42、決策樹構(gòu)造算法，并且對這些算法的優(yōu)缺點(diǎn)進(jìn)行了分析。下而，給出評價決策 樹的一些標(biāo)準(zhǔn)。1. 過學(xué)習(xí)在由決策樹學(xué)習(xí)的過程屮，我們必須在一組假設(shè)屮選擇一個，使得它與訓(xùn)練實(shí)例集相匹配。我 們已經(jīng)看到不可能在沒有任何偏置(bias)的情況下學(xué)習(xí)。如果預(yù)先字段所要學(xué)習(xí)的函數(shù)屬于整個 假設(shè)空間中一個很小子集，那么即使在訓(xùn)練實(shí)例不完整的情況下，我們也有可能從訓(xùn)練實(shí)例集喪鐘 學(xué)習(xí)有用的假設(shè)，來使得它能夠?qū)ξ粗膶?shí)例進(jìn)行止確分類。即使如此，我們還是希望有一個大的訓(xùn)練實(shí)例集。因?yàn)橛?xùn)練實(shí)例集越大，關(guān)于分類的信息越多。 在這種情況下，即使我們隨機(jī)地從與訓(xùn)練實(shí)例集相一致的假設(shè)集中選擇一個，它也能對未知實(shí)例的 分類進(jìn)行預(yù)測

43、。和反，即使在有偏置的情況下，如果訓(xùn)練實(shí)例集與整個假設(shè)空間相比過小，仍有過 多的與訓(xùn)練實(shí)例相一致的假設(shè)供我們選擇，我們做出假設(shè)的泛化能力將很差。當(dāng)有過多的假設(shè)與訓(xùn) 練實(shí)例集相一致的時候，則成為過學(xué)習(xí)。過學(xué)習(xí)是所冇機(jī)器學(xué)習(xí)都要考慮的問題。過學(xué)習(xí)將導(dǎo)致我們所做出的假設(shè)泛化能力過差。所以，也可以如下定義過學(xué)習(xí)。假設(shè)h對所有 的訓(xùn)練實(shí)例分類的錯誤率為errorliainh,對整個實(shí)例空間d分類的錯誤率為errord(h)。如果存在 另一個假設(shè)力使得：并且errord (/z) < errord (/?)一般將errortrain(/?)成為重替換(resubstitution)錯誤率，在木書屮將

44、其簡記為r錯誤率。而在 此一般將在測試集屮的錯誤率errors 成為錯誤。cohen和jensen捉出了一個有用的理論來解禪為何會出現(xiàn)過學(xué)習(xí)的情況。他們捉出，當(dāng)一個算 法過高估計(jì)增加樹的復(fù)雜性對于分類的正確性的貢獻(xiàn)，那么就會出現(xiàn)過學(xué)習(xí)現(xiàn)象。主要有三種原因 使得算法過高估計(jì)這些貢獻(xiàn)：（1）檢測模型的數(shù)目：算法檢測模型數(shù)目與出現(xiàn)過學(xué)習(xí)的可能性是正相關(guān)的。（2）不同的正確性估計(jì)：小的訓(xùn)練實(shí)例集更不可能代表數(shù)據(jù)的內(nèi)衣分布，更有可能產(chǎn)生過學(xué) 習(xí)的現(xiàn)彖。而大一些的訓(xùn)練實(shí)例集產(chǎn)生過學(xué)習(xí)問題的可能性更小。（3）選擇最優(yōu)樹：通過極大化某個特定評價函數(shù)來選擇最優(yōu)決策樹增加了過學(xué)習(xí)的可能性。 cohen和jense

45、n利用事后剪枝的方法驗(yàn)證了他們的理論。2. 有效性最為直接的估計(jì)一棵決策樹在測試實(shí)例集合上的性能的方法是，將它在測試實(shí)例集合上進(jìn)行實(shí) 際測試，這樣就可以選中在測試集合中表現(xiàn)最好的-棵決第樹。但是這種方法等價于在測試實(shí)例集 屮訓(xùn)練決策樹，這在人多數(shù)情況下是不現(xiàn)實(shí)的。所以一般并不采川這種方法，而是采取川訓(xùn)練實(shí)例 集本身來估計(jì)訓(xùn)練算法的有效性。一種最簡便的方法是川訓(xùn)練實(shí)例集的一部分（例如3/4的訓(xùn)練實(shí) 例）對決策樹進(jìn)行訓(xùn)練，而川另外一部分（例如1/4的訓(xùn)練實(shí)例）對決策樹檢測其有效性。但是， 這樣做將會減小訓(xùn)練實(shí)例空間，而增人過學(xué)習(xí)的可能性，所以這種方法也不可取。3. 交叉有效性在此方法中，我們將訓(xùn)練

46、實(shí)例集t分為互不相交且大小相等的k個子集7；, t2.tk.對于任 意子集7；,用t-7；訓(xùn)練決策樹，z后用7；對牛成的決策樹進(jìn)行測試，得到錯誤率耳，然后估計(jì)整 個算法的錯誤率:可以看出隨著k的增加，所生成的樹的數(shù)【也隨之增加，算法的復(fù)朵度也會變?nèi)恕?. 余一-有效性（leave-one-out validation）這種有效性的度量與交叉有效性類似，不同z處在于將每個的人小定為1。假設(shè)|t|=n,則 錯誤率為:顯然，這種有效性測量算法的復(fù)雜度過高，但是它的準(zhǔn)確程度也是故高的。5. 決策樹的復(fù)雜程度決策樹的復(fù)雜程度也是度量決策樹學(xué)習(xí)效果的一個重要標(biāo)準(zhǔn)。対于給定的描述語言，如果決策 樹是旳變量（

47、univariate）的，那么決策樹的復(fù)雜程度主要山樹的結(jié)點(diǎn)個數(shù)決定；如果是多變量(multivariare)的，則主要是由結(jié)點(diǎn)中屬性的總個數(shù)決定。2. 4.決策樹的進(jìn)展與發(fā)展方向2. 4. 1 數(shù)據(jù)挖掘中決策樹算法的主要進(jìn)展傳統(tǒng)的決策樹算法主要是針對小數(shù)據(jù)集的，大都要求訓(xùn)練集常駐內(nèi)存，這使得在處理數(shù)據(jù)挖掘 任務(wù)吋，傳統(tǒng)決策樹算法在可伸縮性、精度和效率方而受到了很大的限制。而在實(shí)際的數(shù)據(jù)挖掘應(yīng) 用中我們面臨的數(shù)據(jù)集往往是容量匕大的數(shù)據(jù)庫或者數(shù)據(jù)倉庫,在構(gòu)造決策樹時需要將龐大的數(shù)據(jù) 在主存和緩存中不停的導(dǎo)入導(dǎo)出，使得運(yùn)算效率大大降低。針對以上問題，許多學(xué)者提出了處理大型 數(shù)據(jù)集的決策樹算法。其中

48、主要在以下四個方面的應(yīng)用：1、數(shù)據(jù)預(yù)處理；2、抽樣方法；3、數(shù)據(jù)的重構(gòu)；4、結(jié)合上述的遺傳算法等其他算法。2. 4. 2.決策樹技術(shù)面臨的挑戰(zhàn)及目前研究方向目前決策樹技術(shù)的主要研究方向8有以下兒點(diǎn)：1決策樹算法的并行性研究2尋找新的構(gòu)造決策樹的方法3尋找更好的簡化決策樹的方法4研究產(chǎn)生決策樹的訓(xùn)練和檢驗(yàn)數(shù)據(jù)的人小及特性與決策樹特性之間的關(guān)系5不確定環(huán)境下決策樹研究6將決策樹用于多智能體控制并不多見7決策樹時間復(fù)雜度與準(zhǔn)確性z間的矛盾8決策樹技術(shù)的軟件實(shí)現(xiàn)3. 關(guān)于決策樹算法的改進(jìn)由以上討論可知：1d3算法存在種種缺陷，女口：算法的計(jì)算時間是例子個數(shù)、特征個數(shù)、節(jié)點(diǎn) 個數(shù)z積的線性函數(shù)。另外大量

49、實(shí)驗(yàn)證明，id3算法在預(yù)測止確率和效果上是令人滿意的。用互信息作為特征選擇量,要求訓(xùn)練例子集中的正、反例比例應(yīng)與實(shí)際領(lǐng)域里正、反例比例相同。但在一般情況下不能保證相 同，因而計(jì)算訓(xùn)練集的互信息就有偏差?；バ畔⒌挠?jì)算依賴于特征值數(shù)h較多的特征，這樣不太合 理。另外id3在建樹時，每個節(jié)點(diǎn)僅含一個特征，特征間的相關(guān)性強(qiáng)調(diào)不夠。下血針xjid3算法的第 二個不足之處，捉出-些決策樹改進(jìn)意見。3. 1 基于樣本離散度的特征選擇方法3. 1. 1.基本概念1 樣本均值(1)表示第i類在第j維特征處的樣本均值。其中，si表示第i類總的樣本數(shù)，x/表示第i類第k個 樣木在第j維特征處的取值。2.樣本歸一化樣

50、本歸一化就是將屬性取值范圍投影到一個特定的范圍z內(nèi)，以消除數(shù)值型屬性因大小不一而 造成挖掘結(jié)果的偏差。對丁基丁距離計(jì)算的挖掘,數(shù)值歸一化可以幫助消除因?qū)傩匀≈捣秶煌?影響挖掘結(jié)果的公正性。我們按照下式刈離散的數(shù)據(jù)進(jìn)行歸一化處理，歸一化后的結(jié)果將限制在0 ,1 范圍之內(nèi)。v. = (2)vmax -其中©為第j維某個數(shù)據(jù)的歸一化值；怙沏為第j維該數(shù)據(jù)的實(shí)際值；為第j維數(shù)據(jù)的最 小值；叫喚為第j維數(shù)據(jù)的最大值。連續(xù)數(shù)據(jù)的歸一化處理,首先應(yīng)該對數(shù)據(jù)進(jìn)行離散化,(有關(guān)連續(xù)數(shù)據(jù)離散化處理方法這里暫吋 不做介紹，請讀者參考上述決策樹算法的研究中的相關(guān)內(nèi)容)，然后再述行數(shù)據(jù)的歸一化。3. 樣本

51、總類內(nèi)離散度離散度的定義:一個在d維空間山n個點(diǎn)組成的聚類，其散布的程度口j以用離散度來衡量。離散度 的計(jì)算和我們規(guī)定的中心點(diǎn)有關(guān)。設(shè)方是d維空間中所選的中心點(diǎn)，從聚類的n個點(diǎn)中取出d個點(diǎn)，以 a為引點(diǎn)，作一個超平行四邊形。對所有n中的d個點(diǎn)求出相應(yīng)的u個超平行四邊形的體積平方和 対n個點(diǎn)的均值，就是該聚類刈于中心點(diǎn)方的離散度。假使取聚類的均值點(diǎn)作為引點(diǎn)，則離散度為：s = |c|（3）式中c是聚類的協(xié)方差矩陣，即離散度矩陣s?？傠x散度st定義為：石=萬工（x廠"）（疋-兀）2n /=i根據(jù)離散度的概念，推導(dǎo)出樣本類內(nèi)離散度定義:樣木與樣木均值的方差，若考慮先驗(yàn)概率，可 以定義如下：

52、/=1k=門表示第i類的先驗(yàn)概率，即p.s表示訓(xùn)練集的總的樣本數(shù)。$4. 歸一化后的樣本分布設(shè)樣木各維數(shù)據(jù)已經(jīng)歸一化到0 ,1 區(qū)間，貝將所有類在第j維的均值按從小到 大的升序排列，記為：“丿二 “ j 9 “2 丿，“v (6)理想情況下的特征分布應(yīng)當(dāng)為從= 1,并口任意兩個相鄰的均值間的距離為:嘰一如172 1d“ j =工心£+1 -“)一1=1市于所提取的特征的均值并非完全理想分布，因此，我們定義一個函數(shù)來度量實(shí)際分布與理想 分布之間的距離。(8)7°越小，a+1/-a:/越接近于占，即各均值點(diǎn)在°，1區(qū)間越接近理想分布。5. 距離函數(shù)定義一個距離函數(shù)，希

53、望投影后，各類樣本盡可能分得開些，即希望dui越小越好；同時希望 各類樣本內(nèi)部盡量密集，即希望類內(nèi)離散度st越小越好.山式（5）和（8）定義距離函數(shù)。dj = s + 出口 j總之，希望dj越小越好,這樣特征越理想.因此，在式（6）中選擇一個較小的dj值所對應(yīng)的 一個特征作為形成決策樹的分類特征。3. 1.2.基于離散度的改進(jìn)算法根據(jù)上述特征選擇方法，在id3算法的基礎(chǔ)上，捉出一種改進(jìn)的決策樹建樹算法，算法步驟如下:1）將訓(xùn)練集窗口中的全部數(shù)據(jù)，選擇一種歸一化方法，歸一化到0 ,1 區(qū)間，形成訓(xùn)練集d。2）對訓(xùn)練集d ,利用上述特征選擇方法，利川式、（9）求出£，d廠。3）選擇較小的

54、值所對應(yīng)的那一個特征4作為分類特征，對數(shù)據(jù)集d進(jìn)行分割，a,取兒個值就 得兒個子集。4）對不含同一類樣木的子集,遞歸調(diào)用建樹算法。5）若各子集中的樣本為同一類樣本，則對應(yīng)分枝為葉子節(jié)點(diǎn)，作相應(yīng)的類標(biāo)記,返回調(diào)用處。3. 1.3.分析與比較此算法是根據(jù)離散數(shù)學(xué)的基礎(chǔ)知識來討論實(shí)現(xiàn)的，與id3的利用的信息論知識一樣含概了大量 的數(shù)學(xué)公式，在第3.2節(jié)中即將討論的基于概率論的算法也用是一樣。利用數(shù)學(xué)公式計(jì)算并構(gòu)建決 策樹是眾多決策樹算法中的優(yōu)先選擇。淌澤學(xué)院計(jì)算機(jī)與信息工程學(xué)系的郭玉濱講師6已經(jīng)證明 基于離散度的改進(jìn)算法有以下幾點(diǎn)好處：（1）基于離散度的改進(jìn)算法cpu的耗時遠(yuǎn)小于td3的cpu耗吋。

55、（2）分類的錯誤率:這種基于離散度的改迓算法分類的錯謀率要低于td3算法分類的錯誤率。3. 1.4.小結(jié)基于離散度的改進(jìn)算法的兒個問題：（1）建樹步驟1中：如何將訓(xùn)練集窗口中的全部數(shù)據(jù)通過選擇-種歸一化方法，歸一化到0,1 區(qū)間，形成訓(xùn)練集do在眾多的歸一化方法中找到一種合適的方式是很耗費(fèi)的事，如果事先為計(jì)算 機(jī)選擇好歸一化方法可以減輕計(jì)算機(jī)的負(fù)擔(dān)，但這卻給設(shè)計(jì)者帶來了負(fù)擔(dān)。（2）建樹步驟1中：要將歸-化后的數(shù)據(jù)進(jìn)行從小到大的升序排序，這乂要選樣一種排序方 法。在排序算法中最好情況卜-就是快速排序算法，其時間復(fù)雜度為：0 （nlogn） o在不知情的情況 下設(shè)計(jì)者要對眾多的排序算法進(jìn)行研究以求最快。（3）建樹步驟2中：對訓(xùn)練集d,要利用式、（8）、（9）等三個公式來求岀每一個訓(xùn)練實(shí)例 的距離函數(shù)。這乂是一項(xiàng)復(fù)雜的計(jì)算。（4）建樹步驟3中：若要選擇距離函數(shù)最小的訓(xùn)練實(shí)例就要進(jìn)行排序。這個雖然可以用上面 問題（2）中的排序算法解決。但也盂要花費(fèi)計(jì)算機(jī)的時間來做。（5）循壞遞歸調(diào)川也