本文關(guān)鍵詞：優(yōu)化的ID3算法在酒店客房續(xù)費問題中的應(yīng)用

  更多相關(guān)文章： 數(shù)據(jù)挖掘 決策樹算法 ID3算法 多值偏向 算法優(yōu)化

【摘要】：隨著數(shù)據(jù)庫技術(shù)的逐步成熟,分類預(yù)測之類的數(shù)據(jù)挖掘技術(shù)也得到了高速的發(fā)展,分類預(yù)測技術(shù)中的決策樹方法也常常被應(yīng)用于多個行業(yè)領(lǐng)域。ID3算法作為影響力最大的決策樹算法之一而且得到了大范圍的應(yīng)用,然而ID3算法也有一些不足之處。本文主要針對ID3算法多值偏向、算法公式計算量大兩方面的的缺陷,通過對ID3算法進行算法改進和公式簡化,從而實現(xiàn)對ID3算法的優(yōu)化,主要進行的工作為:(1)提出基于矯正函數(shù)的ID3優(yōu)化方案。在基于矯正函數(shù)的ID3優(yōu)化方案中,克服多值偏向問題的方法為:通過引入矯正函數(shù)的定義,對子元組所需的期望信息量進行矯正,多值偏向分析證明改進后的ID3算法可克服多值偏向問題;克服ID3信息增益公式運算較為耗時的方法為:通過利用等價無窮小簡化信息增益公式,使得簡化后的信息增益公式中已消除了較為耗時的對數(shù)運算。最后,將算法改進和信息增益公式簡化兩部分的工作相結(jié)合,并提出了基于矯正函數(shù)的決策樹優(yōu)化算法。實驗結(jié)果分析表明:與ID3算法相比,在分類精度和計算時間兩個方面,基于矯正函數(shù)的決策樹優(yōu)化算法具有更好的優(yōu)化效果。(2)提出基于相關(guān)系數(shù)的ID3優(yōu)化方案。在基于相關(guān)系數(shù)的ID3優(yōu)化方案中,克服多值偏向問題的方法為:將相關(guān)系數(shù)修改成適用于決策樹領(lǐng)域的新型相關(guān)系數(shù),通過引入新型相關(guān)系數(shù)子元組所需的期望信息量進行重新矯正,實驗中的多值偏向相關(guān)理論的分析證明了改進后的ID3算法能夠解決克服多值偏向的缺陷;克服ID3信息增益公式運算較為耗時的方法為:通過利用麥克勞林公式簡化信息增益公式,使得簡化后的信息增益公式中已消除了較為耗時的對數(shù)運算。最后,將算法改進和信息增益公式簡化兩部分之間工作進行結(jié)合,得到了基于相關(guān)系數(shù)的決策樹優(yōu)化算法。實驗結(jié)果表明,相比于ID3算法,基于相關(guān)系數(shù)的決策樹優(yōu)化算法既能克服多值偏向問題,又具有更高的分類精度,同時也降低了決策樹的生成時間;相比于基于矯正函數(shù)的決策樹優(yōu)化算法,除了在決策樹生成時間方面,基于相關(guān)系數(shù)的決策樹優(yōu)化算法的時間較長;但在分類精度方面,基于相關(guān)系數(shù)的決策樹優(yōu)化算法則更顯優(yōu)勢。最后將提出的兩種ID3優(yōu)化算法應(yīng)用于酒店客房續(xù)費問題中,并在Visual Studio 2013上用C++語言分別將其實現(xiàn)。將酒店客戶基本信息和客戶入住后的居住意見整理成樣本集合,分別用ID3算法及提出的兩種優(yōu)化算法建立決策樹并提取出規(guī)則,通過對算法生成結(jié)果進行對比分析,表明兩種優(yōu)化后的ID3決策樹算法在生成規(guī)則上具有更好的實驗效果。
【關(guān)鍵詞】：數(shù)據(jù)挖掘 決策樹算法 ID3算法 多值偏向 算法優(yōu)化
【學位授予單位】：江西理工大學
【學位級別】：碩士
【學位授予年份】：2016
【分類號】：F719.2;TP311.13
【目錄】：

• 摘要4-5
• Abstract5-10
• 第一章 緒論10-15
• 1.1 課題研究背景與意義10
• 1.2 國內(nèi)外研究現(xiàn)狀10-12
• 1.2.1 國外決策樹算法研究進程10-11
• 1.2.2 國內(nèi)決策樹算法研究進程11-12
• 1.3 課題研究內(nèi)容12-13
• 1.4 課題組織結(jié)構(gòu)13-15
• 第二章 數(shù)據(jù)挖掘技術(shù)簡介和決策樹算法15-22
• 2.1 數(shù)據(jù)挖掘概述15-17
• 2.1.1 數(shù)據(jù)挖掘的定義15
• 2.1.2 數(shù)據(jù)挖掘的方法15-16
• 2.1.3 數(shù)據(jù)挖掘的步驟16-17
• 2.2 決策樹概述17-18
• 2.2.1 決策樹的相關(guān)介紹及其生成17
• 2.2.2 決策樹的規(guī)則提取及預(yù)測17-18
• 2.3 ID3算法概述18-21
• 2.3.1 ID3算法的基本思想18
• 2.3.2 ID3算法的算法描述18-19
• 2.3.3 ID3算法的實例分析19-21
• 2.3.4 ID3算法的優(yōu)缺點21
• 2.4 本章小結(jié)21-22
• 第三章 基于矯正函數(shù)的決策樹優(yōu)化算法22-36
• 3.1 引言22
• 3.2 相關(guān)基本理論22-25
• 3.2.1 ID3算法改進的理論基礎(chǔ)22-23
• 3.2.2 等價無窮小相關(guān)簡化理論基礎(chǔ)23-24
• 3.2.3 基于矯正函數(shù)的ID3決策樹優(yōu)化算法的實現(xiàn)方案24-25
• 3.3 結(jié)合矯正函數(shù)的ID3算法改進25-28
• 3.3.1 矯正函數(shù)的提出25
• 3.3.2 矯正函數(shù)的選取25-26
• 3.3.3 矯正函數(shù)的相關(guān)證明26-27
• 3.3.4 基于矯正函數(shù)的ID3改進算法27
• 3.3.5 改進后ID3算法的多值偏向分析27-28
• 3.4 信息增益公式的簡化28-29
• 3.5 基于矯正函數(shù)的ID3決策樹優(yōu)化算法的提出29-30
• 3.6 實驗研究30-35
• 3.6.1 實驗說明及評價標準30
• 3.6.2 DTCF算法的實例驗證與分析30-32
• 3.6.3 實驗驗證及分析32-35
• 3.6.4 實驗結(jié)論35
• 3.7 本章小結(jié)35-36
• 第四章 基于相關(guān)系數(shù)的決策樹優(yōu)化算法36-52
• 4.1 引言36-37
• 4.2 相關(guān)基本理論37-39
• 4.2.1 麥克勞林公式相關(guān)簡化理論37-38
• 4.2.2 相關(guān)系數(shù)的定義及含義38-39
• 4.2.3 基于相關(guān)系數(shù)的決策樹優(yōu)化算法的實現(xiàn)方案39
• 4.3 結(jié)合相關(guān)系數(shù)的ID3算法改進39-42
• 4.3.1 屬性之間相關(guān)系數(shù)的引入39-41
• 4.3.2 基于相關(guān)系數(shù)的ID3改進算法41
• 4.3.3 改進后ID3算法的多值偏向分析41-42
• 4.4 信息增益公式的簡化42-43
• 4.5 基于相關(guān)系數(shù)的決策樹優(yōu)化算法的提出43
• 4.6 實驗研究43-51
• 4.6.1 實驗說明及評價標準43-44
• 4.6.2 DTCC算法的實例驗證與分析44-49
• 4.6.3 實驗驗證及分析49-50
• 4.6.4 實驗結(jié)論50-51
• 4.7 本章小結(jié)51-52
• 第五章 優(yōu)化的ID3算法在酒店客房續(xù)費問題中的應(yīng)用52-61
• 5.1 引言52
• 5.2 問題確立52-53
• 5.3 數(shù)據(jù)準備53-54
• 5.4 數(shù)據(jù)挖掘算法的執(zhí)行54-58
• 5.4.1 ID3算法的實現(xiàn)55
• 5.4.2 DTCF算法的實現(xiàn)55-56
• 5.4.3 DTCC算法的實現(xiàn)56-57
• 5.4.4 三種算法運行結(jié)果的比較分析57-58
• 5.5 提取規(guī)則及預(yù)測58-60
• 5.6 本章小結(jié)60-61
• 第六章 總結(jié)和展望61-63
• 6.1 本文工作總結(jié)61-62
• 6.2 課題展望62-63
• 參考文獻63-66
• 致謝66-67
• 攻讀學位期間的研究成果67-68

【相似文獻】

中國期刊全文數(shù)據(jù)庫 前10條

1 葛磊;武芳;王鵬波;張冬林;;3維建筑綜合中基于最小特征的面平移算法[J];測繪科學技術(shù)學報;2009年02期

2 駱雯,孫延明,陳振威,陳錦昌;判斷點與封閉多邊形相對關(guān)系的改進算法[J];機械;1999年03期

3 李林;盧顯良;;一種基于切割映射的規(guī)則沖突消除算法[J];電子學報;2008年02期

4 劉巧玲;張紅英;林茂松;;一種簡單快速的圖像去霧算法[J];計算機應(yīng)用與軟件;2013年07期

5 林亞平,楊小林;快速概率分析進化算法及其性能研究[J];電子學報;2001年02期

6 章郡鋒;吳曉紅;黃曉強;何小海;;基于暗原色先驗去霧的改進算法[J];電視技術(shù);2013年23期

7 楊鐵軍;靳婷;;一種動態(tài)整周模糊值求解算法及其仿真分析[J];系統(tǒng)工程與電子技術(shù);2007年01期

8 周秀玲;郭平;陳寶維;王靜;;幾種計算超體積算法的比較研究[J];計算機工程;2011年03期

9 吳一戎,胡東輝,彭海良;Chirp Scaling SAR成象算法及其實現(xiàn)[J];電子科學學刊;1995年03期

10 王貴竹;一種產(chǎn)生單向分解值的算法[J];安徽大學學報(自然科學版);2001年03期

中國重要會議論文全文數(shù)據(jù)庫 前10條

1 尹冀鋒;;一種新的圖象自適應(yīng)增強算法[A];四川省通信學會一九九二年學術(shù)年會論文集[C];1992年

2 寧春平;田家瑋;郭延輝;王影;張英濤;鄭桂霞;劉研;;計算機輔助增強、分割算法在鑒別乳腺良、惡性腫塊中的應(yīng)用價值[A];中華醫(yī)學會第十次全國超聲醫(yī)學學術(shù)會議論文匯編[C];2009年

3 謝麗聰;;SVB查詢改寫算法的改進[A];第二十一屆中國數(shù)據(jù)庫學術(shù)會議論文集（研究報告篇）[C];2004年

4 鄭存紅;;復(fù)雜背景下相關(guān)跟蹤算法研究及DSP實現(xiàn)[A];中國光學學會2010年光學大會論文集[C];2010年

5 楊文杰;吳軍;;RFID抗沖突算法研究[A];2008通信理論與技術(shù)新進展——第十三屆全國青年通信學術(shù)會議論文集（上）[C];2008年

6 高山;畢篤彥;魏娜;;一種基于UPF的小目標TBD算法[A];第十四屆全國圖象圖形學學術(shù)會議論文集[C];2008年

7 周磊;張衛(wèi)華;王曉奇;張軍;;基于流水算法的智能路障機器人設(shè)計[A];2011年全國電子信息技術(shù)與應(yīng)用學術(shù)會議論文集[C];2011年

8 潘巍;李戰(zhàn)懷;陳群;索博;李衛(wèi)榜;;面向MapReduce的非對稱分片復(fù)制連接算法優(yōu)化技術(shù)研究[A];第29屆中國數(shù)據(jù)庫學術(shù)會議論文集（B輯）（NDBC2012）[C];2012年

9 李偉偉;蔡康穎;鄭新;王文成;;3D模型中重復(fù)結(jié)構(gòu)的多尺度快速檢測算法[A];第六屆和諧人機環(huán)境聯(lián)合學術(shù)會議（HHME2010)、第19屆全國多媒體學術(shù)會議（NCMT2010）、第6屆全國人機交互學術(shù)會議（CHCI2010）、第5屆全國普適計算學術(shù)會議（PCC2010）論文集[C];2010年

10 楊任爾;陳懇;勵金祥;;基于棱邊方向檢測的運動自適應(yīng)去隔行算法[A];Proceedings of 2010 Chinese Control and Decision Conference[C];2010年

中國重要報紙全文數(shù)據(jù)庫 前1條

1 國泰君安資產(chǎn)管理部;“算法交易”是道指暴跌罪魁禍首?[N];上海證券報;2010年

中國博士學位論文全文數(shù)據(jù)庫 前10條

1 馮輝;網(wǎng)絡(luò)化的并行與分布式優(yōu)化算法研究及應(yīng)用[D];復(fù)旦大學;2013年

2 許玉杰;云計算環(huán)境下海量數(shù)據(jù)的并行聚類算法研究[D];大連海事大學;2014年

3 李琰;基于貓群算法的高光譜遙感森林類型識別研究[D];東北林業(yè)大學;2015年

4 陳加順;海洋環(huán)境下聚類算法的研究[D];南京航空航天大學;2014年

5 王洋;基于群體智能的通信網(wǎng)絡(luò)告警關(guān)聯(lián)規(guī)則挖掘算法研究[D];太原理工大學;2015年

6 雷雨;面向考試時間表問題的啟發(fā)式進化算法研究[D];西安電子科技大學;2015年

7 熊霖;大數(shù)據(jù)下的數(shù)據(jù)選擇與學習算法研究[D];西安電子科技大學;2015年

8 周雷;基于圖結(jié)構(gòu)的目標檢測與分割算法研究[D];上海交通大學;2014年

9 王冰;人工蜂群算法的改進及相關(guān)應(yīng)用的研究[D];北京理工大學;2015年

10 蔣亦樟;多視角和遷移學習識別方法和智能建模研究[D];江南大學;2015年

中國碩士學位論文全文數(shù)據(jù)庫 前10條

1 姚鑫宇;EMD去噪與MUSIC算法在DOA估計中的聯(lián)合應(yīng)用[D];昆明理工大學;2015年

2 陸進;面向含噪數(shù)據(jù)聚類相關(guān)算法的研究[D];復(fù)旦大學;2014年

3 葉一舟;紅外弱小目標檢測算法研究[D];上海交通大學;2015年

4 王繼重;基于Hadoop和Mahout的K-Means算法設(shè)計與實現(xiàn)[D];大連海事大學;2016年

5 何靜;遙感圖像的快速壓縮算法研究[D];北京交通大學;2016年

6 章華燕;鋼軌擦傷檢測算法研究[D];北京交通大學;2016年

7 王一博;MODIS地震熱異常的數(shù)據(jù)處理與算法研究[D];中國石油大學(華東);2014年

8 成鑫;基于組合優(yōu)化問題的多目標模因算法的研究[D];南京航空航天大學;2015年

9 傅致暉;基于協(xié)同分割的視頻目標分割算法研究[D];上海交通大學;2015年

10 張媛;運動車輛檢測與跟蹤算法的研究與實現(xiàn)[D];大連海事大學;2016年

，

本文編號：880202