ID3算法改進(jìn)及其在分析商品價(jià)格波動(dòng)因素中的應(yīng)用

蔡照鵬 ，王永皎，韓正亮

(河南城建學(xué)院 計(jì)算機(jī)與數(shù)據(jù)科學(xué)學(xué)院，河南 平頂山 467036)

ID3算法改進(jìn)及其在分析商品價(jià)格波動(dòng)因素中的應(yīng)用

蔡照鵬 ，王永皎，韓正亮

(河南城建學(xué)院 計(jì)算機(jī)與數(shù)據(jù)科學(xué)學(xué)院，河南 平頂山 467036)

對決策樹以及ID3算法進(jìn)行介紹，運(yùn)用決策樹ID3算法對1978-2005年全國農(nóng)業(yè)商品價(jià)格總指數(shù)、種植業(yè)指數(shù)、林業(yè)產(chǎn)品指數(shù)、畜牧業(yè)產(chǎn)品指數(shù)、漁業(yè)產(chǎn)品指數(shù)進(jìn)行分析，在數(shù)據(jù)分類過程中對連續(xù)數(shù)據(jù)采用聚類分析方法進(jìn)行離散化及概念泛化，最后，生成我國農(nóng)業(yè)商品價(jià)格指數(shù)變化情況的決策樹。結(jié)果表明，決策樹分類方法適用于分析我國農(nóng)業(yè)商品價(jià)格的波動(dòng)狀況。

決策樹；ID3算法；商品價(jià)格

1 決策樹方法概述

決策樹方法是數(shù)據(jù)挖掘中一種重要的分類方法，它采用一種貪心算法，即自頂向下的遞歸方式，從根節(jié)點(diǎn)開始在每個(gè)節(jié)點(diǎn)上按照給定標(biāo)準(zhǔn)選擇測試屬性，然后根據(jù)相應(yīng)屬性的所有可能取值向下建立分枝、劃分訓(xùn)練樣本，直到一個(gè)節(jié)點(diǎn)上的所有樣本都被劃分到同一個(gè)類，這一階段最關(guān)鍵的操作是在樹的節(jié)點(diǎn)上選擇最佳測試屬性，該屬性可以將訓(xùn)練樣本進(jìn)行最好劃分。另外，測試屬性的取值可以是連續(xù)的，也可以是離散的[1]。

決策樹是一種逼近離散函數(shù)值的方法。本質(zhì)上決策樹是通過一系列規(guī)則對數(shù)據(jù)進(jìn)行分類的過程[2-4]，其另一特點(diǎn)是在學(xué)習(xí)過程中只要訓(xùn)練實(shí)例能夠用屬性的方式表現(xiàn)，就可以使用該方法而并不需要很多專業(yè)背景知識。

2 決策樹ID3算法

決策樹方法中ID3算法是Quilan在1986年提出來的，是決策樹構(gòu)造中的經(jīng)典算法，基本思想為：

(1)決策樹中每一個(gè)非葉結(jié)點(diǎn)對應(yīng)著一個(gè)非類別屬性，樹枝代表這個(gè)屬性的值。一個(gè)葉節(jié)點(diǎn)代表從樹根到葉節(jié)點(diǎn)之間的路徑對應(yīng)記錄所屬的類別屬性值。

(2)每個(gè)非葉結(jié)點(diǎn)都將與屬性中具有最大信息量的非類別屬性相關(guān)聯(lián)。

(3)采用信息增益來選擇樣本分類屬性。

2.1 基本定義

設(shè)S是s個(gè)數(shù)據(jù)樣本的集合,類標(biāo)號屬性具有m個(gè)不同的值，定義m個(gè)不同的類Ci，其中i[1,m]，設(shè)Si是類Ci中的樣本數(shù)。

定義1：對于一個(gè)給定的樣本分類需要的信息熵為：

(1)

Pi是任意樣本屬于Ci的概率，可用Si/S進(jìn)行估算。

定義2：假如A選為測試屬性，設(shè)Sij子集為Sj中屬于Ci類別的樣本數(shù)。利用屬性A劃分當(dāng)前樣本集合所需要的公式為：

(2)

E(A)計(jì)算結(jié)果越小，就越表示其子集劃分越好。而對于一個(gè)給定子集Sj，它的信息為：

其中，Pij=Sij/|Sij|表示Sj中任一個(gè)數(shù)據(jù)樣本類別的概率。

定義3：若利用A對當(dāng)前節(jié)點(diǎn)分支進(jìn)行樣本集合劃分所獲得的信息增益為：

Gain(A)=I(S1…..Sm)-E(A)

(3)

根據(jù)屬性A取值進(jìn)行樣本集合劃分所獲得的熵的減少量就是Gain(A)。Gain(A)越大說明測試屬性A對結(jié)果劃分分類所需信息量越小。所以應(yīng)作為分類屬性。

2.2 決策樹ID3算法描述

輸入：訓(xùn)練數(shù)據(jù)集samples，用離散值屬性表示；候選屬性的集合attribute_list。

輸出：一棵決策樹。

基本步驟為：

(1)創(chuàng)建結(jié)點(diǎn)N；

(2)ifsamples都在同一個(gè)類Cthen；

(3)返回N作為葉結(jié)點(diǎn)，用類C標(biāo)記；

(4)ifattribute_list為空then；

(5)返回N作為葉結(jié)點(diǎn)，標(biāo)記samples中最普通的類； //多數(shù)表決；

(6)選擇attribute_list中具有最高信息增益的屬性test_attribute； //用信息增益作為屬性選擇度量。

(7)標(biāo)記結(jié)點(diǎn)N為test_attribute；

(8)foreachtest_attribute中的已知值ai//劃分samples

(9)由結(jié)點(diǎn)N生長出一個(gè)條件為test_attribute=ai的分枝；

(10)設(shè)si為samples中test_attribute=ai的樣本集合；//一個(gè)劃分

(11)ifsi為空then；

(12)加上一個(gè)葉結(jié)點(diǎn)，標(biāo)記為標(biāo)記samples中最普通的類；//多數(shù)表決

(13)else加上一個(gè)由Generate_decision_tree(si,attribute_list-test_attribute)返回的結(jié)點(diǎn)。

3 決策樹ID3算法改進(jìn)

在ID3算法中對于每個(gè)節(jié)點(diǎn)在選擇測試屬性時(shí)需要計(jì)算E(A)，在數(shù)據(jù)量比較大時(shí)會(huì)影響決策樹的生成效率。假設(shè)決策樹只有兩種分類即正例和反例。設(shè)樣本集S中正例個(gè)數(shù)為p,反例個(gè)數(shù)為n，由式(3)可知，I(S1…Sm)為定值，所以可以以E(A)作為劃分節(jié)點(diǎn)的比較標(biāo)準(zhǔn)[5-7]。

其中

(4)

由麥克勞林公式：

(5)

當(dāng)x→0時(shí)ln(x+1)≈x

由公式(5)對公式(4)做變換可得：

(6)

E(A)為簡化后的信息增益即Gain’(A),只有加、乘、除運(yùn)算，在處理大量數(shù)據(jù)時(shí)可縮減運(yùn)算時(shí)間，提高計(jì)算效率。

4 我國農(nóng)業(yè)商品生產(chǎn)價(jià)格總指數(shù)挖掘分析

4.1 數(shù)據(jù)準(zhǔn)備

分析1987-2005年農(nóng)業(yè)商品價(jià)格指數(shù)變化情況，由于數(shù)據(jù)的變化過程是連續(xù)的，所以在實(shí)際中根據(jù)人們的經(jīng)驗(yàn)以及長期的實(shí)驗(yàn)判斷尋求最佳值確定，上升到知識層次對此類問題進(jìn)行求解的模型很少。因此，需先對連續(xù)的數(shù)據(jù)進(jìn)行離散處理，選用SPSS統(tǒng)計(jì)軟件對數(shù)據(jù)進(jìn)行聚類分析，實(shí)現(xiàn)分類分層目的，然后對數(shù)據(jù)進(jìn)行分類后的概念泛化處理。具體數(shù)據(jù)見表1，運(yùn)用SPSS聚類之后的結(jié)果見表2。

表1 全國農(nóng)業(yè)商品生產(chǎn)價(jià)格總指數(shù)

年份總指數(shù)種植業(yè)指數(shù)林業(yè)產(chǎn)品畜牧業(yè)產(chǎn)品漁業(yè)產(chǎn)品1978103．90104．69101．00100．50102．501979122．10122．39115．00122．60118．201980107．10107．78115．80103．40101．801981105．90106．09127．00101．10100．601982102．20102．48105．90100．30101．001983104．40105．74100．20100．50103．201984104．00103．82103．30104．10109．801985108．60101．66155．50124．10151．301986106．40106．62114．90103．00110．401987112．00108．83120．30117．90122．801988123．00113．46136．70140．20134．301989115．00118．90105．20110．2099．80199097．40100．7384．5092．3098．80199198．0097．31102．4097．40104．701992103．40101．14107．30106．30108．101993113．40112．05111．10114．20122．101994139．90141．91111．80144．60122．001995119．90123．95105．10115．80112．401996104．20104．71104．40103．30103．40199795．5092．8198．90101．8091．70199892．0093．64101．1086．9093．90199987．8085．75101．4088．5092．50200096．4094．6690．0099．00100．502001103．10105．6594．15103．0798．57

注：2000年以前農(nóng)業(yè)商品生產(chǎn)價(jià)格總指數(shù)為農(nóng)業(yè)商品收購價(jià)格指數(shù)。數(shù)據(jù)來源：中華人民共和國統(tǒng)計(jì)局。

為方便算法運(yùn)行，特對表1數(shù)據(jù)做聚類分析處理，見表2。

表2 聚類分析結(jié)果

年份總指數(shù)種植業(yè)指數(shù)林業(yè)產(chǎn)品指數(shù)畜牧業(yè)產(chǎn)品指數(shù)漁業(yè)產(chǎn)品指數(shù)197811111197912222198001211198101211198201111198301111198401111198511222198601212198711222198812222198902120199001000199110101199211111199312222199412222199502122199601111199700010199800100199900100200010001200111010200201010200311111200412121200501111

注：表中各個(gè)指數(shù)數(shù)字說明：總指數(shù)：0降，1升；種植業(yè)指數(shù)：0低，1中，2高； 林業(yè)產(chǎn)品指數(shù)：0低，1中，2高；畜牧業(yè)產(chǎn)品指數(shù)：0低，1中，2高；漁業(yè)產(chǎn)品指數(shù)：0低，1中，2高。

4.2 傳統(tǒng)ID3算法的信息增益

(1)計(jì)算對D(總指數(shù))中元祖分類所需的期望信息,根據(jù)式(1)得，

Info(D)=0.996

(2)計(jì)算每個(gè)屬性是期望信息需求，由式(2)得Info種植業(yè)指數(shù)(D)=0.934

同理得

Info林業(yè)產(chǎn)品指數(shù)(D)=0.938

Info畜牧業(yè)產(chǎn)品指數(shù)(D)=0.850
Info漁業(yè)產(chǎn)品指數(shù)(D)=0.842

計(jì)算該劃分的信息增益，由式(3)得

Gain(種植業(yè)指數(shù))= Info(D)- Info種植業(yè)指數(shù)(D)= 0.996-0.934=0.062

Gain(林業(yè)產(chǎn)品指數(shù))= Info(D)- Info林業(yè)產(chǎn)品指數(shù)(D)= 0.996-0.938=0.058

Gain(畜牧業(yè)產(chǎn)品指數(shù))= Info(D)- Info畜牧業(yè)產(chǎn)品指數(shù)(D)=0.996-0.850=0.146

Gain(漁業(yè)產(chǎn)品指數(shù))= Info(D)- Info漁業(yè)產(chǎn)品指數(shù)(D)= 0.996-0.842=0.154

由于漁業(yè)產(chǎn)品指數(shù)在屬性中具有最高信息增益，它被選作測試屬性。決策樹創(chuàng)建過程為：創(chuàng)建一個(gè)節(jié)點(diǎn)，用漁業(yè)產(chǎn)品指數(shù)標(biāo)記，并對每個(gè)屬性值引出一個(gè)分枝，對各個(gè)分枝進(jìn)行如上所述遞歸運(yùn)算，決策樹如圖1所示。

圖 1 最終決策樹

4.3 改進(jìn)ID3算法后的信息增益

使用改進(jìn)的決策樹ID3算法，由式(6)可得計(jì)算結(jié)果如下：

Gain’(D)種植業(yè)指數(shù)=6.37
Gain’(D)林業(yè)產(chǎn)品指數(shù)=6.41
Gain’(D)畜牧業(yè)產(chǎn)品指數(shù)=5.6
Gain’(D)漁業(yè)產(chǎn)品指數(shù)=5.58

Gain’(D)漁業(yè)產(chǎn)品指數(shù)最小即應(yīng)把漁業(yè)產(chǎn)品指數(shù)作為測試屬性創(chuàng)建決策樹，然后對各個(gè)分枝進(jìn)行遞歸運(yùn)算，構(gòu)造決策樹與圖1相同。圖2為決策樹ID3算法改進(jìn)前后處理相同數(shù)據(jù)所需的耗時(shí)對比圖。

圖2 耗時(shí)對比圖

5 結(jié)論

(1)從決策樹中可以看出：漁業(yè)產(chǎn)品指數(shù)對總指數(shù)變化影響最大，其次是種植業(yè)指數(shù)和林業(yè)產(chǎn)品指數(shù)，在對決策樹準(zhǔn)確率驗(yàn)證的前提下可以以此制定、調(diào)整和檢查各項(xiàng)經(jīng)濟(jì)政策，對農(nóng)業(yè)商品價(jià)格指數(shù)的變化進(jìn)行調(diào)節(jié)。

(2)從規(guī)則中提取相關(guān)的知識可以對新的數(shù)據(jù)進(jìn)行預(yù)測。在連續(xù)數(shù)據(jù)離散化過程中，聚類分析并行概念泛化使數(shù)據(jù)更加客觀反映實(shí)際情況。

(3)ID3算法在屬性選擇標(biāo)準(zhǔn)的改進(jìn)上，雖然計(jì)算E(A)時(shí)采用了近似計(jì)算，由于在計(jì)算熵中考慮了屬性的取值個(gè)數(shù)，所以對分類的準(zhǔn)確率影響不大，改進(jìn)的算法在分類效率上有很大的提高。

(4)ID3算法是決策樹方法中的經(jīng)典算法之一，在實(shí)際工作中，需要根據(jù)數(shù)據(jù)類型的特點(diǎn)以及數(shù)據(jù)集的大小選取合適的算法。

[1] 田苗苗.數(shù)據(jù)挖掘之決策樹方法概述[J].長春大學(xué)學(xué)報(bào).2004，14(6)：48-51.

[2] 唐華松，姚耀文.數(shù)據(jù)挖掘中決策樹算法的探討[J].計(jì)算機(jī)應(yīng)用研究，2001，18(18)：18-19.

[3] 張琳,陳燕,李桃迎,等.決策樹分類算法研究[J].計(jì)算機(jī)工程，2011，37(13)：66-67.

[4] 楊學(xué)兵，張俊.決策樹算法及其核心技術(shù)[J].計(jì)算機(jī)研究與發(fā)展，2007,17(1)：43-45.

[5] 王勝.基于決策樹ID3算法研究與實(shí)現(xiàn)[J].齊齊哈爾大學(xué)學(xué)報(bào)，2012(3)：64-68.

[6] 黃愛輝，陳湘濤.決策樹ID3算法的改進(jìn)[J].計(jì)算機(jī)工程與科學(xué)，2009，31(6)：109-11.

[7] 高懿洋.基于決策樹的我國農(nóng)業(yè)數(shù)據(jù)挖掘分析[J].測繪科學(xué)技術(shù)學(xué)報(bào)，2008，25(5)：352-354.

Improved ID3 algorithm and its application in commodity price fluctuations analysis

CAI Zhao-peng, WANG Yong-jiao, HAN Zheng-liang

(DepartmentofComputerandDataScience,HenanUniversityofUrbanConstruction,Pingdingshan467036,China)

Firstly, a brief introduction of the decision tree and ID3 algorithm is made, then decision tree ID3 algorithm was used to analyze the 1978-2005 national agricultural commodity price index, index of planting and forestry products index, animal husbandry and fishery products product index index. In the data classification process, continuous data is made discretization and generalization of the concept by using the above data cluster analysis method,and finally using decision tree classification method to generate decision tree for the change of Chinese agricultural commodity price index. The results show that the decision tree classification method is applicable to the analysis of the fluctuation of agricultural commodity prices in China.

decision tree; ID3 algorithm; price of agricultural commodity products

2016-06-22

河南省高等學(xué)校重點(diǎn)科研項(xiàng)目(15A520048)

蔡照鵬(1980—)，男，河南濮陽人，碩士，講師。

1674-7046(2016)06-0086-07

10.14140/j.cnki.hncjxb.2016.06.016

TP393

A