決策樹ID3算法的研究與應(yīng)用

摘 要：決策樹算法是數(shù)據(jù)挖掘中常用的重要方法，廣泛應(yīng)用于分類和預(yù)測。本文對決策樹的ID3算法的基本思想進行了介紹，通過應(yīng)用實例說明了構(gòu)造決策樹的實現(xiàn)過程。

關(guān)鍵詞：決策樹；分類；ID3算法

中圖分類號：TP311.13

隨著計算機網(wǎng)絡(luò)技術(shù)和數(shù)據(jù)庫管理系統(tǒng)的不斷普及，在各應(yīng)用領(lǐng)域的信息系統(tǒng)的數(shù)據(jù)庫中積累了大量的數(shù)據(jù)，如何從這些數(shù)據(jù)中提取出潛藏在其中的有用的信息和規(guī)則呢？從數(shù)據(jù)庫中數(shù)據(jù)發(fā)現(xiàn)知識的技術(shù)即數(shù)據(jù)挖掘應(yīng)運而生，數(shù)據(jù)挖掘就是從這些大量的數(shù)據(jù)中提取出有意義的、有應(yīng)用價值的信息或知識的過程。決策樹是數(shù)據(jù)挖掘常用的方法之一。

決策樹方法因其算法易于理解，具有簡單直觀，數(shù)據(jù)分析效率高等特點，被廣泛應(yīng)用和研究，目前決策樹算法中較流行的算法有如ID3、C4.5、CART和SPRINT等，基于信息熵的ID3算法是最有影響的分類算法[1]。

1 決策樹ID3算法

ID3算法是決策樹中的具有代表性的算法，在建立決策樹的過程中，把信息熵作為節(jié)點屬性的選擇標(biāo)準(zhǔn)，即選用具有最大信息增益的屬性，這就使得通過每一個非葉節(jié)點，能獲得最多的關(guān)于數(shù)據(jù)記錄的類別信息。具體方法是：計算數(shù)據(jù)集中所有屬性的信息增益，選擇其中信息增益最大的屬性作為決策樹當(dāng)前節(jié)點，依據(jù)該屬性的不同取值建立不同分支，再對各分支對應(yīng)的數(shù)據(jù)子集遞歸地調(diào)用此方法，由此構(gòu)造的決策樹，其中每一個節(jié)點屬性都是具有最大增益率的屬性，通過決策樹可以實現(xiàn)數(shù)據(jù)記錄的分類。ID3算法涉及的相關(guān)理論知識[2]定義如下：

2 ID3算法實例

以UCI機器學(xué)習(xí)數(shù)據(jù)集中的天氣表中14條數(shù)據(jù)為例，應(yīng)用ID3算法構(gòu)造決策樹。天氣表中主要有天氣、溫度、濕度、是否有風(fēng)、是否適于打球共5種屬性，其中是否打球為類別屬性，根據(jù)天氣情況判斷是否適于打高爾夫球。ID3算法創(chuàng)建決策樹確定各個屬性節(jié)點時以信息增益率作為選擇標(biāo)準(zhǔn)，具體步驟如下：

2.1 計算屬性的信息增益，選取信息增益最大的屬性作為當(dāng)前節(jié)點。

（3）計算屬性的信息增益：

選取各屬性中信息增益最大的屬性作為分支節(jié)點，即選擇“天氣”屬性為根節(jié)點。

2.2 根據(jù)當(dāng)前節(jié)點的屬性不同取值建立節(jié)點的不同分支，不同分支對應(yīng)不同數(shù)據(jù)子集。采用遞歸算法，在各個數(shù)據(jù)子集中計算屬性的信息增益，選擇其中信息增益最大的為當(dāng)前節(jié)點屬性，這樣逐層建立決策樹[3]。對天氣表中的14條數(shù)據(jù)記錄分別以編號1-14代表。本例中按照“天氣”屬性的不同取值得到不同子集。天氣為晴的子集{1，2，8，9，11}，天氣為多云的子集{3，7，12，13}，天氣為雨的子集 {4，5，6，10，14}。天氣為多云的子集的各個實例數(shù)據(jù)都屬于同一個類，因此對應(yīng)分枝的類別標(biāo)記為適合打球，對其余兩個子集將繼續(xù)使用最大信息增益的節(jié)點屬性確定方法，直至各子集中的實例的類別標(biāo)記都屬于同一個類。

對天氣為晴的子集{1，2，8，9，11}，對天氣除外的屬性求信息增益值，選擇信息增益最大的為當(dāng)前節(jié)點。濕度屬性的信息增益最大，選擇濕度為當(dāng)前節(jié)點并向下分枝。濕度為高時所有例子的類別為不適合打球，該節(jié)點標(biāo)記為不適合。濕度為適中時的例子的類別為適合打球，該節(jié)點標(biāo)記適合。

最后建立的決策樹如下：

2.3 根據(jù)建立的決策樹獲取分類規(guī)則。從決策樹的根節(jié)點至各個葉子節(jié)點的各個路徑中節(jié)點屬性的值，可以提取出依據(jù)天氣情況是否適合打高爾夫球的一般分類規(guī)則：

IF“天氣”：=晴 AND“濕度”=高 THEN“是否適于打球”=不適合

IF“天氣”：=晴 AND“濕度”=適中 THEN“是否適于打球”=適合

IF“天氣”：=多云 THEN“是否適于打球”=適合

IF“天氣”：=雨 AND“是否有風(fēng)”=有風(fēng) THEN “是否適于打球”=不適合

IF“天氣”：=雨 AND“是否有風(fēng)”=無風(fēng) THEN “是否適于打球”=不適合

可以將這些規(guī)則應(yīng)用在其他數(shù)據(jù)集上，對是否適于打高爾夫球的情況進行分類和預(yù)測。

3 結(jié)束語

作為一種能夠發(fā)現(xiàn)大量數(shù)據(jù)中潛在信息和規(guī)則的技術(shù)和方法，數(shù)據(jù)挖掘已經(jīng)成為各界所關(guān)注的熱點，其中，決策樹方法以圖形的形式體現(xiàn)挖掘結(jié)果，因其具有形象直觀、分類速度快等特點，在實際中廣泛應(yīng)用于在客戶分類劃分和預(yù)測。ID3算法是決策樹中經(jīng)典的算法，在構(gòu)造的決策樹過程中以信息增益作為選擇節(jié)點屬性的標(biāo)準(zhǔn)[4]。本文著重介紹了決策樹ID3算法的基本思想和特點，結(jié)合實例說明了使用ID3算法構(gòu)造決策樹的過程，通過決策樹獲取的規(guī)則進行判斷和預(yù)測，解決了實際應(yīng)用中的客戶分類等問題。

參考文獻：

[1]孫愛東，朱梅階，涂書琴.基于屬性值的ID3算法改進[J].計算機工程與設(shè)計，2008（12）：3011-3012.

[2]黃文.決策樹的經(jīng)典算法：ID3與C4.5[J].四川文理學(xué)院學(xué)報（自然科學(xué)），2007（05）：16-18.

[3]王永梅，胡學(xué)鋼.決策樹中ID3算法的研究[J].安徽大學(xué)學(xué)報（自然科學(xué)版），2011（03）：71-75.

[4]于淑香.決策樹ID3算法的研究與應(yīng)用[J].沙洲職業(yè)工學(xué)院學(xué)報，2011（02）：27-30.

作者簡介：杜麗英（1969-），女，吉林長春人，講師，碩士，研究方向：計算機。

作者單位：吉林建筑大學(xué) 計算機科學(xué)與工程學(xué)院，長春 130118；長春市137中學(xué)，長春 130051

基金項目：吉林省教育廳“十二五”科學(xué)技術(shù)研究項目（項目編號：吉教科合字[2012]第198號）。