常用的決策樹生成算法分析

1、天津市財貿(mào)管理干部學院學報 j o u r n a l0 f ，r i a n j i nl n s t l t u t e0 f 兀n a n c i a la n dc o m m e r c i a lm a n a g e m e n t第十卷2 8 年第2 期 常用的決策樹生成算法分析 于莉 天津財貿(mào)管理干部學院，天津3 0 0 1 7 0 【摘要1 數(shù)據(jù)分類是數(shù)據(jù)挖掘中的一個重要課題，被有效地應用于科學實驗、醫(yī)療診斷、氣象預報、商業(yè)預測等領(lǐng) 域。常用的分類方法包括決策樹、神經(jīng)網(wǎng)絡(luò)、遺傳算法等。其中決策樹是分類方法中的一個重要研究方向，由于其結(jié) 構(gòu)簡單、可以清晰的生成便于人們理解的規(guī)

2、則效率高、以及適用大數(shù)據(jù)量等優(yōu)點而被廣泛使用本文就幾種常用的 決策樹生成算法進行較深入地分析和比較。 【關(guān)鍵詞】數(shù)據(jù)挖掘；決策樹；決策樹算法 【中圖分類號】t p 3 0 1 6 【文獻標識碼】b 【文章編號】1 0 0 8 9 0 5 5 ( 2 0 0 8 ) 0 2 0 0 1 9 一0 2 a n a l y s e so ne s t a b l i s h i n gc a l c u l a t ew a y so f 1 m ，1tt j 一，e c l s l o n 。lr e e sl nl 0 m m o nus e y ul i ( t i a 巧i nc o m m

3、 e r c i a l 徹df i n a n c i a lm a n a g e r l l e n ti n s t i t u t e ，t i a n j i n3 0 0 1 7 0 ) 【a b s t r a c t 】d a t ac l a s s i f i c a t i o ni sa ni m p o r t a mt o p i ci nd i g i t a le x c a v a t i o n ，a n db e i n gu s e df o rs c i e n c et e s t s ，m e d i c a lt r e a t m e n t

4、 s ，w e a t h e rf o r e c a s t s ，a n db u s i n e s sp r e d i c t i o n s t h ec l a s s i 6 c a t i o nm e t h o di n c o m m o nu s ei n c l u d e sd e c i s i o nt r e e ，n e u r a ln e t ，t h eg e n e t i cc a l c u l a t i o ne t c a m o n gt h e md e c i s i o nt r e ei s am e t h o do fm

5、u c hm o r ei m p o r t a n c ei nt h er e s e a r c hd i r e c t i o n hi si nas i m p l es t m c t u r e ，e a s vt ob ee s t a b l i s h e da n du n d e r s t o o d ，w i t hh i g he f n c i e n c y ，a n ds u i t a b l et oa 卿a td e a lo fd a t ae t c i ti su s e de x t e n s i v e l yd u et oa l l

6、t h e s ea d v a n t a g e s t h i sa r t i c l ec a r r i e so na n a l y z i n ga n dc o m p a r i n gm o r ea n dt h o r o u g 王l l y f o raf e wd e c i s i o nt r e e s e s t a b l i s h i n gc a l c u l a t ew a 丫si nc o m m o nu s e 【k e yw o r d s 】d i 舀t a le x c a v a t i o n ；d e c i s i o

7、 nt r e e ；c a l c u l a t ew a y so f d e c i s i o nt r e e s 一、數(shù)據(jù)挖掘及分類 數(shù)據(jù)挖掘是從大量的、不完全的、有噪聲的、模糊的、隨 機的實際應用數(shù)據(jù)中，提取隱含在其中的、人們事先不知道 的、但又是潛在有用的信息和知識的過程其任務(wù)是從大量 的數(shù)據(jù)中發(fā)現(xiàn)有價值的模式 分類是數(shù)據(jù)挖掘中應用極其廣泛的重要技術(shù)之一其目 的是分析輸入數(shù)據(jù)通過數(shù)據(jù)表現(xiàn)的特性構(gòu)造一個分類模 型用該模型對類別未知的數(shù)據(jù)進行分類。分類過程分為訓 練和測試兩個步驟：在訓練階段，分析訓練數(shù)據(jù)，為每個類別 產(chǎn)生一個對應的數(shù)據(jù)集的描述規(guī)則：在測試階段用上述產(chǎn) 生的規(guī)則對

8、測試數(shù)據(jù)進行分類，以此來測試分類的準確性。 訓練階段用于產(chǎn)生分類模型，是關(guān)鍵步驟。分類模型的構(gòu)造 方法有多種，其中最為典型的是基于決策樹的分類方法。 二、決策樹分類方法 決策樹方法廣泛用于解決與分類相關(guān)的各種問題屬于 有指導的歸納學習算法。該方法著眼于從一組無次序、無規(guī) 則的數(shù)據(jù)中歸納出一個分類描述從中發(fā)現(xiàn)潛在的、具有商 業(yè)價值的信息。 決策樹( d e c j s i o nt r e e ) 是一個類似樹結(jié)構(gòu)的表示法每 個內(nèi)部節(jié)點表示一個屬性的測試分支表示一個測試的輸 出，而葉節(jié)點就表示類或類的分布。使用訓練樣本構(gòu)建決策 樹時通常采用自頂向下的遞歸方式即從代表全部訓練樣 本的根節(jié)點開始為每

9、個內(nèi)部節(jié)點選擇一個測試屬性并根 據(jù)該屬性的取值將樣本劃分為若干分支直到葉節(jié)點將樣本 劃分為某一類。在決策樹的構(gòu)建過程中，關(guān)鍵問題是測試屬 性的選擇以及分割點的確定。不同的決策樹算法采用的屬性 分割方法不同，常用的決策樹算法主要有i d 3 、c 4 5 、c a r t 、 s u q 、s p r i n t 等。 三、常用的決策樹算法分析比較 ( 一) i d 3 算法 最早出現(xiàn)的決策樹算法是1 9 6 6 年由h u n t 等人提出的 c l s 算法其主要思想是從一棵空的決策樹開始通過添加 結(jié)點逐步求精直到產(chǎn)生一棵能正確分類訓練實例的決策樹 為止。c 1 5 算法在構(gòu)造決策樹的過程中

10、沒有給出選擇測試屬 性的具體標準。因此，在該算法的基礎(chǔ)上，o u i n l a n 在1 9 7 9 年 提出了在國際上最有影響力的以信息熵的下降速度作為選 擇測試屬性標準的i d 3 算法。 該算法的基本思想是：從代表訓練樣本的單個節(jié)點開始 樹的構(gòu)造。如果樣本屬于同一類，則該節(jié)點成為葉節(jié)點，并用 該類標記：否則采用窗口的采樣方法，隨機地從訓練數(shù)據(jù)集 中選擇一個子集通過計算每個屬性的信息增益。選擇增益 最大且從根節(jié)點到當前節(jié)點尚未被選擇的屬性作為節(jié)點并 【收稿日期】2 0 0 7 1 2 一0 8 i 作者簡介】于莉( 1 9 7 7 一) ，女，漢族，天津市人，天津市財貿(mào)管理干部學院會統(tǒng)系

11、講師。研究方向：計算機教學。 1 9 萬方數(shù)據(jù) 天津市財貿(mào)管理干部學院學報 j o u l 型皇l 旦ft i a n jj ni n s t i t u t e ( ) f i n a n c i a la n dc o m m e r c i a lm a n a g e m e n t第十卷2 8 年第2 期 根據(jù)該屬性的不同取值創(chuàng)建不同的分支。直至節(jié)點中的所有 記錄屬于同一類或節(jié)點中的記錄數(shù)小于規(guī)定的最小記錄數(shù)。 從i d 3 算法構(gòu)造決策樹的過程可以看出i d 3 算法屬于 一種自頂向下、分而治之的遞歸構(gòu)造決策樹的貪心算法。它 采用不可返回的策略每次搜索全部樣本空間的一個子集生 成決

12、策樹以確保決策樹建立最簡單每次分析的訓練數(shù)據(jù) 最少。其優(yōu)點是在測試屬性的選擇上利用了信息增益的概 念，描述簡單，構(gòu)造的決策樹平均深度較小，分類速度快學 習能力強。但其也存在許多缺陷，如不能處理連續(xù)屬性、可伸 縮性差、容易產(chǎn)生過度擬和等。 ( 二) c 4 5 算法 c 4 5 算法是針對i d 3 算法存在的不足，由0 u i n l a n 于 1 9 9 3 年提出的決策樹主流算法之一。該算法與i d 3 算法相輔 相成，都屬于啟發(fā)式的探索屬性空間的貪心算法。在i d 3 的 基礎(chǔ)上，c 4 5 算法對其缺點進行了改進： 1 當每條記錄的屬性值都不同時為避免i d 3 算法傾向 于優(yōu)先選擇

13、多值的屬性c 4 5 用增益比例取代信息增益作為 選擇分割屬性的標準避免過度擬和的產(chǎn)生。 2 既可以處理離散屬性也可以處理連續(xù)屬性。對于連續(xù) 屬性值通過自動離散化的方式進行處理即先對連續(xù)屬性a 的值進行遞增排序排序后如果相鄰的兩個值不屬于同一 類則用這兩個值的中點m 將數(shù)據(jù)劃分為兩部分一部分落 人該值范圍內(nèi)即a m 。將所有 的中點值m 作為可能的分割點計算信息增益比選擇最大信 息增益比對應的中點值作為分割點劃分樣本空間。由于c 4 5 采用深度優(yōu)先建樹所以為找到對于連續(xù)屬性而言最佳的分 割點，在每一節(jié)點處需對數(shù)據(jù)進行反復的劃分。 雖然c 4 5 算法繼承了i d 3 算法的全部優(yōu)點而且由于

14、其思想簡單，結(jié)果可靠等優(yōu)點更加鞏固了其主流算法的地 位。但其本身也存在決策樹性能改善困難、達不到全局最優(yōu) 的結(jié)果、評價決策樹主要依據(jù)錯誤率以及沒有考慮樹的深度 和結(jié)點的個數(shù)等不足 ( 三) c a r t 算法 c a r t ( c l a s s i f i c a l i o na i l dr e g r e s s i o n7 i b e s ) 算法即分類 與回歸樹算法是由l b r e m a n 等人于1 9 8 4 年提出的生成二 叉決策樹的算法。它依據(jù)g i n i 系數(shù)作為測試屬性的選擇標 準每次將能夠降低數(shù)據(jù)無序度的預測屬性選擇出來按照 深度優(yōu)先的策略構(gòu)造決策樹，屬于

15、有指導的學習算法。 該算法可對連續(xù)型和離散型屬性進行處理。對于離散屬 性將其所有的屬性值看作可能的分割點，求出對應的彝n i 參 數(shù)，最后選擇所有分割點中基尼指數(shù)最小者對應的屬性作為 節(jié)點的分割屬性。對于連續(xù)屬性首先將屬性值進行排序可 能的分割點為相鄰屬性值的中點。從所有可能分割點中找出 西n i 指數(shù)最小的分割點對應的屬性作為分割屬性。由于 c a r t 算法采用深度優(yōu)先建樹所以對于連續(xù)屬性為了找到 最佳分割點，需要在節(jié)點上對數(shù)據(jù)反復進行劃分。 ( 四) c h a i d 算法 c h a i d ( c h is q u a r ea u t o m a t i ci n t e r

16、a c t i o nd e t e c t o r ) 算 法，即卡方自動交互檢測算法是由g o r d o nb 凡s 博士在 1 9 7 6 年提出的快速生成多層決策樹的算法。該算法主要對離 散型變量進行處理，有時也可以對連續(xù)型變量進行處理。但 由于選擇分割屬性的算法不是針對連續(xù)型變量設(shè)計的所以 對于該類型的輸入變量需要先進行離散化的操作。 應用c h a i d 算法建立決策樹時首先為分類變量的每 個取值建立一個分支如果測試屬性存在缺失值，則將缺失 值單獨分支。然后依據(jù)卡方分布的p 值來決定是否進行節(jié) 點的分裂操作。如果節(jié)點中類別的p 值小于預先指定的閾 值，則節(jié)點被分割，直到所有節(jié)點

17、的p 值均大于閾值，則樹的 構(gòu)造結(jié)束。 上述四種算法存在的一個共同弱點就是在決策樹生成 的過程中要求訓練集全部或部分一直駐留在內(nèi)存。所以在數(shù) 據(jù)量急劇增長的情況下由于數(shù)據(jù)集不能擴展，致使這些算 法不能處理大容量的數(shù)據(jù)。因此迫切需要具有可伸縮性的算 法來解決這一問題 ( 五) s l i q 算法 s u q ( s u p e r v i s e dk a m i n gi no u e s t ) 即o u e s t 上的有監(jiān) 督學習是由i b ma l m a d e n 研究中心的m e h t a 等人在1 9 9 6 年提出的一種快速可擴展的分類算法。該算法在樹的構(gòu)建階 段針對數(shù)據(jù)

18、量遠大于內(nèi)存容量的情況利用駐留在磁盤上的 屬性列表和駐留在內(nèi)存的類列表兩種數(shù)據(jù)結(jié)構(gòu)通過采用預 排序技術(shù)和寬度優(yōu)先的決策樹生長方法，使s l i q 算法能夠 對駐留在磁盤上的大數(shù)據(jù)集進行分類而且在改進學習的時 間的同時沒有降低精確度。雖然s u o 算法能以更快的速度 生成較小的樹而且不限制訓練數(shù)據(jù)的數(shù)量及屬性的數(shù)量 但由于類表需要一直駐留在內(nèi)存當類表不能一次裝入內(nèi)存 時，s l i q 算法需要額外進行內(nèi)外存數(shù)據(jù)交換。所以處理的數(shù) 據(jù)量仍有限。 ( 六) s p r i n t 算法 s p r i n7 r ( s c a l a b l ep a r a l l e l i z a b

19、l ei n d u c t i o no fc i a s s i 6 c a t i o n t r e e ) 算法即可擴展的、可并行的歸納決策樹算法是由i b m 的j s h 如r 于1 9 9 6 年提出的。它完全不受內(nèi)存的限制而且 處理速度很快且可擴展。該算法在設(shè)計上兼顧了并行處理 允許多個處理器相互合作生成一致的模型。s p r i n t 算法使 用屬性列表和類統(tǒng)計矩形表通過一次排序?qū)ふ易罴逊指?點。由于在s p r i n t 中將屬性列表平均分配到多個處理器上。 使得它可以處理大規(guī)模的數(shù)據(jù)集。但隨著訓練集的增長它 所使用的h a s h 表也成正比例增長從而使其運行性能受

20、到 較大影響。 通過分析。每種算法各有優(yōu)勢和適用范圍。沒有一種算 法對于所有的數(shù)據(jù)都適用也沒有一種算法完全優(yōu)于其他方 法。因此需要根據(jù)特定問題和特定的數(shù)據(jù)選擇適合的算法。 參考文獻： 1 】1 h u n teb 。jm a r i n ，pts 惦n e e x p e d m e 耵瞳si ni n d u c t i o n a c a - d e i cp r e s s 1 9 6 6 【2 】q i l i n l a l ljr i n d u c t i 徹0 fd e c i 8 i o nt r e e s m a c h i n el e 枷i n g ，1 9 8 6

21、， 1 3 】q u i t l l a njr d i s c o v e r i n gm l e 8f 而m1 a r g ec o l l e c t i o n so fe x 棚p l e s ： ac a s es t u d y i n ：m i c h i ed ，e d e x p e r ts y s t e m si nt h em i c r 0e l e c t r o n i c a g e ，e d i n b u r g hu n i v e r s i t yp r e s s ，1 9 7 9 【4 】j i a w e ih a n ，m i c h e

22、 l i n ek a r r 】【b e r ，范明盂小峰譯數(shù)據(jù)挖掘概念 與技術(shù) m 】北京：機械工業(yè)出版社，2 0 0 1 5 】數(shù)據(jù)挖掘資料匯編h t t p ：，w w w d m g m u p o 唱c n 【6 】陳文偉，黃金才，趙新昱數(shù)據(jù)挖掘技術(shù)【m 】北京：北京工業(yè)大 學出版社2 0 0 2 【7 】邵峰晶，于忠清數(shù)據(jù)挖掘原理與算法【m 】北京：中國水利水電 出版社2 0 0 1 責任編輯：周曉豐 萬方數(shù)據(jù) 常用的決策樹生成算法分析常用的決策樹生成算法分析 作者：于莉 作者單位：天津市財貿(mào)管理干部學院,天津,300170 刊名： 天津市財貿(mào)管理干部學院學報 英文刊名：jour

23、nal of tianjin institute of financial and commercial management 年，卷(期)：2008，10(2) 引用次數(shù)：1次 參考文獻(7條)參考文獻(7條) 1.1.hunt e b,j matin,p t stone.experiments in induction.academic press.1966. 2.quinlan j r.induction of decision trees.machine learning.1986.1. 3.quinlan j r.discovering rules from large collec

24、tions of examples:a case study.in:michie d,ed.expert systems in the micro electronic age,edinburgh university press,1979. 4.jiawei han,micheline kamber.,范明孟小峰譯.數(shù)據(jù)挖掘概念與技術(shù)m.北京:機械工業(yè)出版社,2001. 5.數(shù)據(jù)挖掘資料匯編. 6.陳文偉,黃金才,趙新昱.數(shù)據(jù)挖掘技術(shù)m.北京:北京工業(yè)大學出版社.2002. 7.邵峰晶,于忠清.數(shù)據(jù)挖掘原理與算法m.北京:中國水利水電出版社.2001. 相似文獻(10條)相似文獻(10條)

25、1.學位論文 趙翔 數(shù)據(jù)挖掘中決策樹分類算法的研究 2005 決策樹方法是數(shù)據(jù)挖掘中一種重要的分類方法。本課題從新的建樹準則、決策樹修剪、多變量決策樹、多決策樹組合、不完備信息系統(tǒng)下的模型建 立等幾個方面對決策樹方法進行了研究和探討。 本課題的主要研究工作和成果有： 1、針對傳統(tǒng)決策樹算法的不足（如id3、c4.5），提出 了基于協(xié)方差及高階相關(guān)系數(shù)的決策樹生成算法，避免了經(jīng)典的以信息熵作為建樹準則的決策樹生成算法盲目地偏向于屬性值較多的屬性的缺點。 2、針對決策樹的構(gòu)造和修剪通常不能同時進行所產(chǎn)生的效率低下的問題，提出了基于粗糙集的決策樹構(gòu)造方法。利用優(yōu)先策略，將知識相依性同時作為 屬性約簡

26、和建樹的準則，在決策樹預修剪的同時進行節(jié)點生成，大大提高了決策樹構(gòu)造的效率。 3、針對單變量決策樹忽視信息系統(tǒng)中廣泛存在的 屬性間的關(guān)聯(lián)作用，而且修剪時往往代價很大的缺陷，提出了一種基于主成分分析的多變量決策樹構(gòu)造方法，提取信息系統(tǒng)中的若干主成分來構(gòu)造決策 樹。 4、探討了用boosting方法組合多決策樹，構(gòu)造決策森林的方法。 5、在不完備信息系統(tǒng)中的模型拓展。提出了一種加權(quán)聯(lián)系度容差關(guān) 系，在各屬性重要性排序的前提下對不完備信息系統(tǒng)進行進一步的粗糙集模型拓展，使其更加符合人的主觀要求和客觀現(xiàn)實。從而為進一步探討在不完 備信息系統(tǒng)中構(gòu)造分類器模型打下基礎(chǔ)。 2.學位論文 程向前 基于決策樹的

27、數(shù)據(jù)挖掘算法和可視化研究 2007 數(shù)據(jù)挖掘是一種可以從海量數(shù)據(jù)中智能地和自動地抽取一些有用的、可信的、有效的、可以理解的模式的過程，也被稱之為數(shù)據(jù)庫中的知識發(fā)現(xiàn)。 分類是數(shù)據(jù)挖掘的一種非常重要的方法。分類的概念是在已有數(shù)據(jù)的基礎(chǔ)上學習一個分類函數(shù)或構(gòu)造出一個分類模型（即分類器）進行類型的劃分。該 函數(shù)或模型能夠把數(shù)據(jù)庫中的數(shù)據(jù)記錄映像到給定類別中的某一個。分類方法應用領(lǐng)域廣泛，如金融市場走向分析、顧客信用度分析、醫(yī)療診斷等。 決策樹是數(shù)據(jù)挖掘中一種應用最為廣泛的分類器。其原因主要有:（1）決策樹分類的直觀表示方法較容易轉(zhuǎn)化為標準的數(shù)據(jù)庫查詢；（2）決策樹分類 歸納的方法行之有效、尤其適合于大

28、型數(shù)據(jù)集；（3）決策樹在分類過程中，除了數(shù)據(jù)集中己經(jīng)包括的信息外，不再需要其他額外的信息；（4）決策樹 分類模型的預測準確度較高。由于決策樹本身具有建樹思想簡單、易于提取規(guī)則、貼近人類思維、便于理解等優(yōu)點，使其在分類數(shù)據(jù)挖掘中得到了廣泛 應用。決策樹算法的研究可以擴大算法的應用范圍，提高算法的運行效率以及分類的準確率。本文從屬性離散化、降維、屬性選擇標準、剪枝、與其它 數(shù)據(jù)挖掘方法的結(jié)合等幾個方面對目前決策樹在分類數(shù)據(jù)挖掘中的研究狀況進行了闡述。 本文在介紹了一些典型的決策樹分類算法的基礎(chǔ)上，重 點描述了一種基于決策樹的數(shù)據(jù)挖掘新算法，即基于屬性相似度的決策樹分類器的研究成果。不同測試屬性在決

29、策中的地位也不相同，部分測試屬性甚 至對決策不起任何作用，完全可進行約簡。實驗也證明數(shù)據(jù)集中無關(guān)的、干擾的屬性會影響分類器的性能，導致性能變差。因而本文首先進行了屬性選 擇，只保留與決策最為相關(guān)的屬性，而將其他屬性都去除。然后通過計算測試屬性與決策屬性的相似度作為啟發(fā)規(guī)則來構(gòu)造決策樹。算法還使用了分類 閾值設(shè)定方法簡化決策樹的生成過程。新算法在對uci實驗數(shù)據(jù)庫中的四個數(shù)據(jù)集的實驗中，運行效率明顯高于id3算法，預測精度在某些數(shù)據(jù)集中也優(yōu) 于id3。 weka數(shù)據(jù)挖掘平臺是新西蘭懷卡托大學開發(fā)的基于java語言的開源的數(shù)據(jù)挖掘平臺。它提供了一個java類庫形式的框架，這個框架支持嵌 入式及其學

30、習的應用，以及新的學習方案的實現(xiàn)。本文在熟悉其api的基礎(chǔ)上，成功地在此平臺上實現(xiàn)了自己的新的算法。數(shù)據(jù)挖掘結(jié)果的可視化可以使 用戶和決策者非常形象和直觀地分析得到的知識，本文在weka平臺上將新算法模型得到的決策樹成功地以圖形的方式展示。 3.學位論文 劉振宇 數(shù)據(jù)挖掘算法研究及其在鐵路員工培訓系統(tǒng)中的應用 2006 數(shù)據(jù)庫知識發(fā)現(xiàn)(knowledgediscoveryindatabase，kdd)是從大量數(shù)據(jù)中發(fā)現(xiàn)潛在規(guī)律、提取有用知識的方法和技術(shù)。近年來，kdd受到了國內(nèi)外普 遍關(guān)注，已經(jīng)成為信息系統(tǒng)和計算機科學領(lǐng)域研究中最活躍的部分。kdd被認為是從數(shù)據(jù)中發(fā)現(xiàn)有用知識的整個過程，而數(shù)據(jù)

31、挖掘(datamining，dm)被認 為是kdd過程中的一個特定步驟，它用專門算法從數(shù)據(jù)中抽取模式。 數(shù)據(jù)挖掘作為一種高效、深層次的數(shù)據(jù)分析處理技術(shù)，其目的在于從大量的數(shù) 據(jù)中提取出隱含在其中的潛在信息，這些信息將為人們進行各種決策分析提供有力依據(jù)。如何利用數(shù)據(jù)挖掘技術(shù)對現(xiàn)有的大量數(shù)據(jù)進行分析處理，具有 重要的實際應用價值。目前數(shù)據(jù)挖掘的研究主要集中在如何完成各種知識發(fā)現(xiàn)任務(wù)，如分類知識發(fā)現(xiàn)、聚類知識發(fā)現(xiàn)、關(guān)聯(lián)規(guī)則發(fā)現(xiàn)等。研究的重點在 具體的數(shù)據(jù)挖掘算法，算法研究的目的在于提高挖掘的效率及挖掘結(jié)果的實用性。 本文以實現(xiàn)鐵路員工培訓系統(tǒng)中培訓資源和培訓模式選擇的優(yōu) 化為目標。首先在初步調(diào)研與分

32、析知識發(fā)現(xiàn)與數(shù)據(jù)挖掘相關(guān)理論與應用的基礎(chǔ)上，歸納了該領(lǐng)域的主要研究內(nèi)容和關(guān)鍵技術(shù)。進而結(jié)合數(shù)據(jù)挖掘的應用 現(xiàn)狀和理論基礎(chǔ)，重點分析了分類、聚類算法的理論、方法和實現(xiàn)技術(shù)。研究的主要內(nèi)容有數(shù)據(jù)挖掘的過程模型、數(shù)據(jù)預處理、決策樹分類和聚類的常 用算法等。然后介紹了目前鐵路員工培訓資源與培訓模式的現(xiàn)狀及現(xiàn)有鐵路員工培訓系統(tǒng)的作用和意義。并著重分析了系統(tǒng)中存在的問題，在培訓資源 與培訓模式方面提出了改進方案。最后利用聚類與分類算法對培訓資源與培訓模式進行優(yōu)化，并對所搜集的現(xiàn)有培訓資源與培訓模式進行了聚類和分類 挖掘，分析了已有數(shù)據(jù)的規(guī)律，期望對未知類別的數(shù)據(jù)進行預測。本文所提出的培訓資源與培訓模式優(yōu)化

33、選擇方案對鐵路員工培訓具有一定的指導及幫 助作用。 本文主要研究工作如下：1、介紹數(shù)據(jù)挖掘算法中基本分類算法決策樹分類算法，進行了系統(tǒng)的總結(jié)，給出了決策樹算法的處理流程以 及決策樹生成過程，對經(jīng)典的決策樹算法進行了比較，分析了各自的優(yōu)缺點。 2、針對經(jīng)典決策樹與人的思維及感知認識上的不相符，對連續(xù)屬性 處理的缺陷，引入模糊決策樹算法，深入研究了模糊決策樹算法的實現(xiàn)策略，在此基礎(chǔ)上提出了一種新的模糊決策樹算法模糊基尼系數(shù)法。 3、 對聚類算法中的經(jīng)典k均值法進行描述，指出該算法的不足之處，提出了一種改進的k均值算法，并對二者的性能進行了比較，證明了改進后的k均值算法 優(yōu)于經(jīng)典k均值算法。 4、基

34、于本文所闡述的決策樹算法和聚類算法，設(shè)計了一個關(guān)于鐵路員工培訓資源與培訓模式的優(yōu)化選擇方案，對培訓資源 與培訓模式進行分析與預測，可以提高員工培訓質(zhì)量。 本文針對上述研究內(nèi)容，進行了大量的實驗研究和論證。結(jié)果表明，本文的理論、方法與 技術(shù)基本正確有效，所涉及的鐵路員工培訓系統(tǒng)培訓資源與培訓模式優(yōu)化方案對實際員工培訓可提供一定的指導作用，具有良好的實際應用前景。 4.學位論文 胡小剛 數(shù)據(jù)挖掘中決策樹分類算法的研究 2002 數(shù)據(jù)挖掘,也稱之為數(shù)據(jù)庫中知識發(fā)現(xiàn)是一個可以從海量數(shù)據(jù)中智能地和自動地抽取一些有用的、可信的、有效的和可以理解的模式的過程.分類是 數(shù)據(jù)挖掘的重要內(nèi)容之一.目前,分類已廣泛

35、應用于許多領(lǐng)域,如醫(yī)療診斷、天氣預測、信用證實、顧客區(qū)分、欺詐甄別. 現(xiàn)己有多種分類的方法,其中決 策樹分類法在海量數(shù)據(jù)環(huán)境中應用最為廣泛.其原因如下;1、決策樹分類的直觀的表示方法較容易轉(zhuǎn)化為標準的數(shù)據(jù)庫查詢.2、決策樹分類歸納的方法行 之有效,尤其適合大型數(shù)據(jù)集.3、決策樹在分類過程中,除了數(shù)據(jù)集中已包括的信息外,不再需要額外的信息.4、決策樹分類模型的精確度較高. 該文首先 研究了評估分類模型的方法.在此基礎(chǔ)上著重研究了決策樹分類方法,并對決策樹算法的可伸縮性問題進行了具體分析,最后給出了基于ole db for dm開 發(fā)決策樹分類預測應用程序. 5.學位論文 但小容 數(shù)據(jù)挖掘中決策樹

36、分類算法的研究與改進 2008 數(shù)據(jù)庫技術(shù)的迅速發(fā)展以及數(shù)據(jù)庫管理系統(tǒng)的廣泛應用，導致人們積累了越來越多的數(shù)據(jù)。巨增的數(shù)據(jù)背后蘊藏著豐富的知識，而目前的數(shù)據(jù)庫技 術(shù)雖可以高效的實現(xiàn)數(shù)據(jù)的查詢、統(tǒng)計等功能，卻無法發(fā)現(xiàn)數(shù)據(jù)中存在的關(guān)系和規(guī)則，無法根據(jù)現(xiàn)有的數(shù)據(jù)預測未來的發(fā)展趨勢。數(shù)據(jù)庫中存在著大量 的數(shù)據(jù)，卻缺乏挖掘數(shù)據(jù)背后隱藏的知識的手段，出現(xiàn)了“數(shù)據(jù)爆炸而知識貧乏”的現(xiàn)象。 在此背景下，數(shù)據(jù)庫知識發(fā)現(xiàn)(kdd)及其核心技術(shù) 數(shù)據(jù)挖掘(dm)便應運而生了。數(shù)據(jù)挖掘(data mining)是信息處理技術(shù)研究領(lǐng)域的一項重要課題。數(shù)據(jù)挖掘是利用分析工具從大量的、不完全的、有 噪聲的、模糊的、隨機的數(shù)

37、據(jù)中，提取出隱含在其中、事先未知、潛在有用的信息和知識的過程，建立數(shù)據(jù)間關(guān)系模型，用其做出預測，從而為決策者 提供輔助。它是一種新型的數(shù)據(jù)分析技術(shù)，已被廣泛應用于金融、保險、政府、教育、運輸以及國防等領(lǐng)域。 數(shù)據(jù)分類是數(shù)據(jù)挖掘中一個重要的 內(nèi)容。常用的分類模型有決策樹、神經(jīng)網(wǎng)絡(luò)、遺傳算法、粗糙集、統(tǒng)計模型等。決策樹是分類應用中采用最廣泛的模型之一。與神經(jīng)網(wǎng)絡(luò)和貝葉斯方法 相比，決策樹無須花費大量的時間和進行上千次的迭代來訓練模型，適用于大規(guī)模數(shù)據(jù)集，除了訓練數(shù)據(jù)中的信息外不再需要其他額外信息，表現(xiàn)了很 好的分類精確度。并且決策樹算法是以實例為基礎(chǔ)的歸納學習算法，以其易于提取顯式規(guī)則、計算量相對

38、較小、可以顯示重要的決策屬性和較高的分類 準確率等優(yōu)點而得到廣泛的應用。據(jù)統(tǒng)計，目前決策樹算法是利用最廣泛的數(shù)據(jù)挖掘算法之一。然而在實際應用過程中，現(xiàn)存的決策樹算法也存在著很 多不足之處，如計算效率低下、多值偏向等。因此，進一步改進決策樹，提高決策樹的性能，使其更加適合數(shù)據(jù)挖掘技術(shù)的應用要求具有重要的理論和 實際意義。 本文主要介紹如何利用決策樹方法對數(shù)據(jù)進行分類挖掘。文中詳細的闡述了決策樹的基本知識和相關(guān)算法，并對幾種典型的決策樹算 法進行了分析比較，如：核心經(jīng)典算法-id3算法；能夠處理不完整的數(shù)據(jù)、對連續(xù)屬性的數(shù)據(jù)離散化的c4.5算法：利用gini系數(shù)判別數(shù)據(jù)集中的分裂屬 性并形成二叉樹

39、的cart算法；使數(shù)據(jù)的分類不受機器主存的限制，有著良好的伸縮和并行性的sliq和sprint算法。文中分析并比較了它們各自的優(yōu)缺點 。在決策樹算法中屬quinlan于1986年提出的id3算法最有名，它是非遞增算法，并且采用信息熵作為屬性選擇的標準，可是這個標準易偏向于屬性值數(shù) 較多的屬性，而屬性值較多的屬性卻不總是最優(yōu)的屬性。為了解決取值偏向的問題，本文提出了一種基于id3算法的加權(quán)簡化信息熵算法，該算法的思想 是首先將泰勒公式的原理與id3算法的屬性選擇標準信息熵的求解相結(jié)合，對id3算法信息熵的求解進行簡化，改變了決策樹算法中屬性選擇的標準 ，減小了算法的計算復雜度，提高了算法的運行效

40、率；然后再賦予每個屬性的信息簡化熵一個權(quán)值n，n的取值取決于每個屬性的取值個數(shù)，用以平衡每 個屬性對數(shù)據(jù)集的不確定程度，使得屬性的選擇更加合理化，避免選擇的屬性與實際不相符。最后在visual studio6.0平臺上利用c+語言分別實現(xiàn)改進 前后的id3算法。實驗結(jié)果表明，改進后的加權(quán)簡化信息熵算法提高了決策樹的構(gòu)建速度，減少了算法的計算運行時間，同時也克服了id3算法往往偏向 于選擇取值較多的屬性作為測試屬性的缺陷。并且隨著數(shù)據(jù)規(guī)模的增大，決策樹的分類性能表現(xiàn)得越好。理論分析和實驗結(jié)果表明，本文提出的改進算 法改善了決策樹的id3算法的性能，表現(xiàn)出了良好的分類效果。 6.學位論文 周剛 數(shù)

41、據(jù)挖掘中決策樹算法在客戶流失中的應用研究 2006 數(shù)據(jù)挖掘是從大量的數(shù)據(jù)中抽取出潛在的、不為人知的有用信息、模式和趨勢。其目的是提高市場決策能力、檢測異常模式、在過去的經(jīng)驗基礎(chǔ)上 預言未來趨勢等等。它致力于數(shù)據(jù)分析和理解、揭示數(shù)據(jù)內(nèi)部蘊藏知識的技術(shù)，已成為未來信息技術(shù)應用的重要目標之一。經(jīng)過20多年的發(fā)展，數(shù)據(jù)挖 掘產(chǎn)生了許多新概念和方法。特別是最近幾年，一些基本概念和方法趨于清晰，它的研究正向著更深入的方向發(fā)展。 分類模式挖掘是數(shù)據(jù)挖掘中 的一種非常重要的方法，可以應用于數(shù)據(jù)預測，可劃為決策樹學習、貝葉斯分類、遺傳算法和粗糙集等等。決策樹學習是以實例為基礎(chǔ)的歸納學習算法 。它著眼于從一組無

42、次序、無規(guī)則的事例中推理出決策樹表示形式的分類規(guī)則。它采用自頂向下的遞歸方式，在決策樹的內(nèi)部結(jié)點進行屬性值的比較并 根據(jù)不同的屬性值判斷從該結(jié)點向下的分支，在決策樹的葉結(jié)點得到結(jié)論。 本文主要是研究數(shù)據(jù)挖掘中的決策樹算法以及決策樹算法在具體的小 靈通流失分析中的研究與分析。首先對數(shù)據(jù)挖掘技術(shù)的產(chǎn)生和發(fā)展現(xiàn)狀做了概括性的闡述，介紹了數(shù)據(jù)挖掘的概念、主要內(nèi)容、模式和主要問題，以及 數(shù)據(jù)挖掘的應用和發(fā)展；接著對數(shù)據(jù)挖掘中的決策樹技術(shù)做了詳細的描述，介紹了決策樹中的經(jīng)典挖掘算法id3算法，在分析和總結(jié)了id3，c4.5算法的 基本性質(zhì)、性能和特點的基礎(chǔ)上，本文作者對經(jīng)典的c4.5算法進行了一些改進，并

43、分析了改進后的特點和效果。最后，針對電信業(yè)小靈通客戶流失的問 題，通過數(shù)據(jù)挖掘技術(shù)在大量的歷史數(shù)據(jù)中進行挖掘分析，使用sas等工具，結(jié)合id3、c4.5以及改進后的c4.5算法對樣本集進行分析和比對，進行客戶 細分，挖掘出不同客戶群的業(yè)務(wù)特征，向公司建議，針對流失傾向較高的群體，并結(jié)合這些客戶對應的客戶群特征，采取有針對性的客戶挽留策略。在 理論知識商業(yè)化應用方面，本論文進行了一次有意義的探索和嘗試。 7.學位論文 王惠坡 基于決策樹的貨票數(shù)據(jù)挖掘系統(tǒng)的研究 2003 隨著鐵路信息化技術(shù)的發(fā)展,作為鐵路信息系統(tǒng)子系統(tǒng)的貨票系統(tǒng)已經(jīng)積累了豐富的數(shù)據(jù).如何以較少的人力和技術(shù)成本,合理利用現(xiàn)有的貨票

44、信息資 源獲取有價值的決策信息,成為貨運營銷和信息技術(shù)部門的一個工作重點.數(shù)據(jù)挖掘技術(shù)的迅速發(fā)展,為鐵路貨運營銷工作的深入分析奠定了良好的基礎(chǔ) ,但現(xiàn)有的數(shù)據(jù)挖掘工具大都基于數(shù)據(jù)倉庫、olap server或數(shù)據(jù)文件等,無法直接應用于現(xiàn)有的貨票系統(tǒng)中.該課題針對目前鐵路信息系統(tǒng)不具有數(shù)據(jù)倉 庫的現(xiàn)狀和應用人員數(shù)據(jù)庫技術(shù)有限的特點,緊密結(jié)合鐵路貨運營銷分析問題,采用數(shù)據(jù)挖掘技術(shù)的決策樹歸納方法,研究、設(shè)計了一個基于決策樹的以 oltp數(shù)據(jù)庫為數(shù)據(jù)源的數(shù)據(jù)挖掘系統(tǒng)hpminer.基本系統(tǒng)的研究和設(shè)計力圖集預處理、決策樹生成、分類規(guī)則提取、統(tǒng)計分析與預測為一體,能直接進 行連續(xù)屬性的動態(tài)離散化,該離

45、散化過程基于oltp數(shù)據(jù)庫,是面向具體的挖掘問題,從而降低了對源數(shù)據(jù)的要求;另一方面,離散化可直接面向應用領(lǐng)域人員 ,可由用戶指定離散區(qū)間個數(shù)和設(shè)定閾值,從而極大地方便了用戶的使用,較好地適應了貨票信息系統(tǒng)中數(shù)據(jù)的復雜性.hpminer系統(tǒng)基于決策樹分類算法 id3和c4.5的基本思想,系統(tǒng)的基本平臺是client/server結(jié)構(gòu),前臺使用vb.net語言開發(fā),后臺通過ado.net連接oracle或sql server數(shù)據(jù)庫,基本系統(tǒng)的設(shè) 計便于和貨票信息系統(tǒng)的集成,界面友好.該系統(tǒng)應用于鐵路貨運營銷分析,解決了保價運輸收入分析和貨流去向分析等多個具體問題.hpminer系統(tǒng)的研究 將決策

46、樹分類技術(shù)與現(xiàn)有貨票信息系統(tǒng)有機地結(jié)合起來,使得應用領(lǐng)域分析人員可以方便地挖掘出所希望的知識,用于指導生產(chǎn);另一方面也為決策樹分類 技術(shù)的應用研究開辟了新的領(lǐng)域. 8.學位論文 周燕 基于id3決策樹算法的醫(yī)療數(shù)據(jù)挖掘研究 2004 醫(yī)學領(lǐng)域已成為數(shù)據(jù)挖掘的一個重要領(lǐng)域.在當前醫(yī)學中,存在大量的可以使用的歷史成功案例數(shù)據(jù),這些數(shù)據(jù)中蘊含著很有實用價值的規(guī)則,醫(yī)生可 以利用這些規(guī)則對新的病人進行輔助診斷,以提供其工作速度、準確度與可靠性,并增強對問題的理解,或者用來訓練沒有經(jīng)驗的學生或相關(guān)人員.因此,研 究適用于醫(yī)學領(lǐng)域的數(shù)據(jù)挖掘具有重要的意義.決策樹(decision tree),就是一棵規(guī)則

47、樹.它利用樹的結(jié)構(gòu)將數(shù)據(jù)記錄進行分類,樹的一個葉結(jié)點就代表某 個條件下的一個記錄集,根據(jù)記錄字段的不同取值建立樹的分支,在每個分支子集中重復建立下層結(jié)點和分支,便可生成一棵決策樹.決策樹的學習是以實 例為基礎(chǔ)的歸納學習算法.它著眼于從一組無次序、無規(guī)則的事例中推理出決策樹表示形式的分類規(guī)則.基于決策樹的學習算法的一個最大優(yōu)點就是它在 學習過程中不需要使用者了解太多的背景知識,只要訓練例子能夠用屬性一結(jié)論式的方式表達出來,就能使用該算法來學習.在決策樹學習算法的各種算法 中,最為有影響的是ouinlan于1979年提出的以信息熵(entropy)取測試屬性的標準的id3算法.id3算法采取信息熵

48、原理選擇測試屬性分割樣本集,處理具有 離散型屬性和屬性值齊全的樣本,常常能生成結(jié)構(gòu)比較好,效率比較高的決策樹.本文主要分析設(shè)計了基于決策樹id3算法的醫(yī)療數(shù)據(jù)挖掘的方法,重點研究 了決策樹id3算法,并建立了一個基于決策樹id3算法的醫(yī)療數(shù)據(jù)挖掘系統(tǒng)原型,將本系統(tǒng)應用于醫(yī)學數(shù)據(jù)集上可以獲得較好的效果,證實本文所探討的方法 具有一定的應用價值.數(shù)據(jù)挖掘是一個處于不斷發(fā)展和完善的多學科研究領(lǐng)域,其理論本身及其在醫(yī)學領(lǐng)域中的應用還存在很多問題值得探討.本文的研究 工作主要是針對是已經(jīng)轉(zhuǎn)化好的關(guān)系數(shù)據(jù)庫數(shù)據(jù),避開了復雜類型數(shù)據(jù)到關(guān)系數(shù)據(jù)庫數(shù)據(jù)這一轉(zhuǎn)化過程.因此,相關(guān)研究工作還需要進一步深入. 9.學位

49、論文 林海 基于基因表達式編程的決策樹研究 2006 隨著數(shù)據(jù)庫技術(shù)的不斷發(fā)展及數(shù)據(jù)庫管理系統(tǒng)的廣泛應用，數(shù)據(jù)庫中存儲的數(shù)據(jù)量急劇增大，在大量的數(shù)據(jù)背后隱藏著許多重要的信息。數(shù)據(jù)挖掘 就是利用分析工具從大量的、不完全的、有噪聲的、模糊的、隨機的數(shù)據(jù)中，提取出隱含在其中、事先未知、但又潛在有用的信息和知識的過程，建立 數(shù)據(jù)間關(guān)系模型，并用其做出預測。近年來，數(shù)據(jù)挖掘受到了國內(nèi)外的普遍關(guān)注，己經(jīng)成為信息系統(tǒng)和計算機科學領(lǐng)域研究中最活躍的前沿領(lǐng)域。數(shù)據(jù) 挖掘已廣泛應用于生物醫(yī)學、金融、零售業(yè)、電信業(yè)等領(lǐng)域，并產(chǎn)生了巨大的效益。 分類是數(shù)據(jù)挖掘中的一種非常重要的方法。它是在已有數(shù)據(jù) 的基礎(chǔ)上學會一個分

50、類函數(shù)或構(gòu)造出一個分類模型(即通常說的分類器)。該函數(shù)或模型能夠把數(shù)據(jù)庫中的數(shù)據(jù)項映射到給定類別中的某一個，從而可以 應用于數(shù)據(jù)預測。目前，分類已廣泛應用于許多領(lǐng)域，如醫(yī)療診斷、天氣預測、信用證實、顧客區(qū)分、欺詐甄別。 現(xiàn)已有多種分類的方法，其中 決策樹分類法在海量數(shù)據(jù)環(huán)境中應用最為廣泛。其原因如下：1、決策樹分類的直觀的表示方法較容易轉(zhuǎn)化為標準的數(shù)據(jù)庫查詢。2、決策樹分類歸納的 方法行之有效，尤其適合大型數(shù)據(jù)集。3、決策樹在分類過程中，除了數(shù)據(jù)集中己包括的信息外，不再需要額外的信息。4、決策樹分類模型的精確度較 高。 決策樹分類器是一個類似流程圖的樹型結(jié)構(gòu)，其中樹的每個內(nèi)部結(jié)點代表對一個屬性(取值)的測試，其分支就代表測試的每個結(jié)果，而樹的 每個葉結(jié)點就代表一個類別。決策樹很容易用if-then規(guī)則進行表達。決策樹模型是數(shù)據(jù)挖掘中最常用的一種方法。它能夠直接體現(xiàn)數(shù)據(jù)的特點，便于理 解，具有較好的分類預測能力，并能方便提取決策規(guī)則。決策樹的生成過程也就是知識發(fā)現(xiàn)的過程，決策樹模型的復雜度和預測精度決定了決策樹的好 壞。決策樹是根據(jù)啟發(fā)規(guī)則生成的，常見的決策樹生成算法有基于信息論的id3