設計課題：id3演算法與c4.5演算法的比較分析
專業班級：086081-01
學生姓名：李小龍
學生學號：20071003550
指導教師：蔣良孝
成績二○一○年十月二十日
1． 背景知識：
決策樹是對資料進行分類，以此達到**的目的。該決策樹方法先根據訓練集資料形成決策樹，如果該樹不能對所有物件給出正確的分類，那麼選擇一些例外加入到訓練集資料中，重複該過程一直到形成正確的決策集。決策樹代表著決策集的樹形結構。
決策樹由決策結點、分支和葉子組成。決策樹中最上面的結點為根結點，每個分支是乙個新的決策結點，或者是樹的葉子。每個決策結點代表乙個問題或決策，通常對應於待分類物件的屬性。
每乙個葉子結點代表一種可能的分類結果。沿決策樹從上到下遍歷的過程中，在每個結點都會遇到乙個測試，對每個結點上問題的不同的測試輸出導致不同的分支，最後會到達乙個葉子結點，這個過程就是利用決策樹進行分類的過程，利用若干個變數來判斷所屬的類別。
2. id3演算法與c4.5演算法介紹
2.1 id3演算法：
id3演算法是由quinlan首先提出的。該演算法是以資訊理論為基礎，以資訊熵和資訊增益度為衡量標準，從而實現對資料的歸納分類。
id3演算法計算每個屬性的資訊增益，並選取具有最高增益的屬性作為給定集合的測試屬性。對被選取的測試屬性建立乙個節點，並以該節點的屬性標記，對該屬性的每個值建立乙個分支據此劃分樣本.id3演算法具體步驟如下：
1. 從訓練集中隨機選擇乙個既含正例又含反例的子集；
2. 用「建樹演算法」對當前視窗形成一顆決策樹；
3. 用對訓練集（視窗除外）中例子所得決策樹進行類別判定，找出錯判的例子；
4. 若存在錯判的例子，把它們插入視窗，轉步驟2，否則結束。
2.2 c4.5演算法：
由於id3演算法在實際應用中存在一些問題，於是quilan提出了c4.5演算法，嚴格上說c4.5只能是id3的乙個改進演算法。具體演算法步驟如下；
1.建立節點n
2.如果訓練集為空，在返回節點n標記為failure
3.如果訓練集中的所有記錄都屬於同乙個類別，則以該類別標記節點n
4.如果候選屬性為空，則返回n作為葉節點，標記為訓練集中最普通的類；
each 候選屬性 attribute_list
候選屬性是聯絡的then
7.對該屬性進行離散化
8.選擇候選屬性attribute_list中具有最高資訊增益的屬性d
9.標記節點n為屬性d
each 屬性d的一致值d
11.由節點n長出乙個條件為d=d的分支
12.設s是訓練集中d=d的訓練樣本的集合
s為空14.加上乙個樹葉，標記為訓練集中最普通的類
加上乙個有c4.5（r-,c，s）返回的點
3. 實驗分析比較
以下是用wake資料探勘工具做的實驗得到的資料（以表為例），
分別用了id3, c4.5 ，nbtree演算法對同一表做的實驗，其中nbtree演算法主要是作為id3, c4.5演算法結果的乙個參考。
3.1 id3演算法得到的實驗結果：
3.2 c4.5演算法得到的實驗結果：
3.3 nbtree演算法得到的實驗結果：
4．總結：
通過對id3,c4.5演算法的學習與研究，我有以下收穫：
嚴格上說c4.5演算法只能是id3的乙個改進演算法，並在以下幾方面對id3演算法進行了改進：
1) 用資訊增益率來選擇屬性，克服了用資訊增益選擇屬性時偏向選擇取值多的屬性的不足；
2) 在樹構造過程中進行剪枝；
3) 能夠完成對連續屬性的離散化處理；
4) 能夠對不完整資料進行處理。
c4.5演算法繼承了id3演算法的優點。同時，與id3演算法相比較，c4.5演算法有如下優點：產生的分類規則易於理解，準確率較高。
資料倉儲與資料探勘
頻繁專案集.給定全域性專案集i和資料庫d，d中所有滿足使用者指定的最小支援度 minsupport 的專案集，即大於或等於minsupport的i的非空子集，稱為頻繁專案集 frequent itemsets 或者大專案集 large itemsets 在頻繁專案集中挑選出所有不被其他元素包含的頻繁...
資料倉儲和資料探勘
編號 data warehouse data mining 一 課內學時 32 學分 2 二 適用專業 計算機軟體與理論 計算機應用等。三 預修課程 資料庫 四 教學目的 通過資料倉儲和資料探勘的有關基礎知識介紹，使學生對其含義 作用及發展有所了解，為進一步做有關的研究打下基礎。五 大綱內容 第一章...
資料倉儲與資料探勘考試題
選擇題1.某超市研究銷售紀錄資料後發現，買啤酒的人很大概率也會購買尿布，這種屬於資料探勘的哪類問題 a.關聯規則發現 b.聚類 c.分類d.自然語言處理 2.將原始資料進行整合 變換 維度規約 數值規約是在以下哪個步驟的任務 a.頻繁模式挖掘 b.分類和 c.資料預處理 d.資料流挖掘 3.當不知道...