數(shù)據(jù)挖掘決策樹ID3算法優(yōu)化

《數(shù)據(jù)挖掘決策樹ID3算法優(yōu)化》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、本科生課程論文…文獻(xiàn)綜述題目：數(shù)據(jù)挖掘決策樹ID3算法優(yōu)化姓名：程健境學(xué)號：221000328學(xué)院：數(shù)計（軟件）學(xué)院專業(yè)：軟件T程年級：2010教師：朱文興2011年6月14日數(shù)據(jù)挖掘決策樹ID3算法優(yōu)化摘要：數(shù)據(jù)挖掘，也可以稱為數(shù)據(jù)庫中的知識發(fā)現(xiàn)(KnowledgeDiscoveryinDatabase,KDD),是從大量數(shù)據(jù)屮提取出可信、新穎、有效并能被人理解的模式的高級處理過程。決策樹算法是數(shù)據(jù)挖掘中的一個比較活躍的研究領(lǐng)域,是對分類問題進(jìn)行深入分析的一種方法，但構(gòu)造最優(yōu)決策樹是一個NP困難問題。文中著垂介紹了ID3算法

2、的基木思想，然后討論了決策樹算法中的難點問題，針對ID3算法中所存在的不足，提出了一種利用優(yōu)化法的思想來改進(jìn)ID3的算法。關(guān)鍵字：數(shù)據(jù)挖掘，決策樹算法，ID3算法。1數(shù)據(jù)挖掘隨著計算機硬件和軟件的飛速發(fā)展，尤其是數(shù)據(jù)庫技術(shù)與應(yīng)用的日益普及,人們血臨著快速擴(kuò)張的數(shù)據(jù)海洋，如何有效利用這一豐富數(shù)據(jù)海洋的寶藏為人類服務(wù)，業(yè)己成為廣人信息科技工作者所重點關(guān)注的焦點之一。為有效解決這一問題，自二十世紀(jì)80年代開始，數(shù)據(jù)挖掘技術(shù)逐步發(fā)展起來。數(shù)據(jù)挖掘[1],簡單地講就是從大量數(shù)據(jù)屮挖掘或抽取出知識，它是一門交叉學(xué)科，它把人們對數(shù)據(jù)的應(yīng)用從

3、低層次的簡單杏詢，提升到從大量數(shù)據(jù)屮提煉有價值的信息，為決策提供支持。數(shù)據(jù)挖掘，乂稱為數(shù)據(jù)庫屮的知識發(fā)現(xiàn)，簡稱KDD,是一個從大量數(shù)據(jù)屮抽取出未知的、有價值的模式或規(guī)律的復(fù)雜過程。典型的KDD過程包括:數(shù)據(jù)準(zhǔn)備、數(shù)據(jù)清洗、數(shù)據(jù)集成、數(shù)據(jù)轉(zhuǎn)換、數(shù)據(jù)挖掘、模式評估和知識表現(xiàn)六個環(huán)節(jié)。盡管數(shù)據(jù)挖掘只是整個知識發(fā)現(xiàn)過程的一個重要步驟，但是已經(jīng)在工業(yè)界、媒體和數(shù)據(jù)庫研究領(lǐng)域中，廣義的表示為整個知識發(fā)掘過程。數(shù)據(jù)挖掘的目標(biāo)是從犬量數(shù)據(jù)屮，發(fā)現(xiàn)隱藏于其后的規(guī)律或數(shù)據(jù)間的關(guān)系，從而服務(wù)于決策。利用數(shù)據(jù)挖掘技術(shù)可以幫助獲得決策所需的多種知識。在

4、許多情況下，用戶并不知道數(shù)據(jù)中存在著哪些有價值的知識，因此對于一個數(shù)據(jù)挖掘系統(tǒng)而言，它應(yīng)該能夠同時搜索發(fā)現(xiàn)多種模式的知識，以滿足用戶的期望和實際需要。而本文主要討論研究其中的決策樹算法-包括ID3算法的優(yōu)化研究，從數(shù)據(jù)挖掘決策樹算法的許多研究資料屮發(fā)現(xiàn)了許多不足Z處，因此乂參考了其他材料對其進(jìn)行深入優(yōu)化研究。2決策樹算法決策樹算法是一種逼近離散函數(shù)值的方法，其分類精度高，成的模式簡單，對噪聲數(shù)據(jù)有很好的健壯性，因而是目前應(yīng)用最為廣泛的歸納推理算法之一，在數(shù)據(jù)挖掘屮受到研究者的廣泛關(guān)注。決策樹方法最早產(chǎn)生于上世紀(jì)60年代，到70

5、年代末。由JRossQuinlan提出了ID3算法，此算法的目的在于減少樹的深度。但是忽略了葉子數(shù)目的研究。C4.5算法在ID3算法的基礎(chǔ)上進(jìn)行了改進(jìn)，對于預(yù)測變量缺值處理、剪枝技術(shù)。派生規(guī)則等方面作了較大改進(jìn)，既適合于分類問題，又適合于回歸問題。說到?jīng)Q策樹的構(gòu)造方法，只是簡單介紹一下。通過分析已有的數(shù)據(jù)訓(xùn)練集形成一系列規(guī)則，并運用規(guī)則對未知的數(shù)據(jù)進(jìn)行預(yù)測的決策，以下為構(gòu)造決策樹的過程［2］：(1)尋找最初的分裂屬性。將整個訓(xùn)練集作為產(chǎn)生決策樹的集合，訓(xùn)練集每個記錄已分類。在決定哪個屬性是目前最好的分類屬性時，一般的做法是窮盡

6、現(xiàn)有的全部屬性，對每個屬性分裂的好壞進(jìn)行量化，計算出最好的一個分裂。(2)重復(fù)步驟(1),直至每個葉節(jié)點內(nèi)的記錄都屬于同一類，并增長到一?棵完整的樹。作為分類器，決策樹是一顆有向、無環(huán)樹。樹中的根節(jié)點沒有父節(jié)點，所有其他節(jié)點都有且只有1個父節(jié)點；1個父節(jié)點可以有1?2個或沒有子節(jié)點。如果節(jié)點沒有子節(jié)點，稱其為葉節(jié)點(LeafNode)；其他的稱為內(nèi)部節(jié)點(InternalNode)。每個葉節(jié)點都對應(yīng)一個類別標(biāo)識C的值；每個內(nèi)部節(jié)點都對應(yīng)一個用于分割數(shù)據(jù)集的屬性Xi,稱為分割屬性(SplittingAttribute)；每個內(nèi)部

7、節(jié)點都有一個分割判斷規(guī)則qj(SplittingPredicate)；如果Xi是連續(xù)屬性,那么①的形式為Xi小于等于Xi，其中Xi屬于dom(Xi),Xi就是節(jié)點n的分割點(SplitPoint)；如果心是離散屬性,那么qj的形式為Xi屬于丫“其中Yi屬于doni(Xi),Y：就成為節(jié)點n的分割子集(SplitSubset)o糕、n的分割屬性和分割判斷規(guī)則組成了節(jié)點n的分割標(biāo)準(zhǔn)(SplittingCriterion)o而本文主要研究決策樹算法中的JLD3算法及其優(yōu)化。3ID3算法決策樹方法的起源是概念學(xué)習(xí)系統(tǒng)(ConceptL

8、earningSystem,CLS)，然后發(fā)展到ID3方法而為高峰。Quinlan提出的TD3算法通過對一個例子集進(jìn)行學(xué)習(xí)生成一棵決策樹，現(xiàn)假設(shè)一個例子僅屬于兩種分類之一:正例，即符合被學(xué)習(xí)的H標(biāo)概念的例子;反例，即不符合目標(biāo)概念的例子。另外，假設(shè)例子的所有屬性都是離散屬性。