基于ID3決策樹算法的非規(guī)則數(shù)據(jù)的規(guī)律

文/孫亞非 郭盛 李悅

基于ID3決策樹算法的非規(guī)則數(shù)據(jù)的規(guī)律

文/孫亞非 郭盛 李悅

海量信息的處理，關(guān)鍵在于找出有價值或者有潛在價值的數(shù)據(jù)。這些數(shù)據(jù)為非規(guī)則數(shù)據(jù)，從這些數(shù)據(jù)中找到規(guī)律是數(shù)據(jù)處理中的重點和難點。ID3算法可以較為有效地解決這些問題，能夠準確的把握數(shù)據(jù)的走勢和是否能夠成為熱點的可能。

ID3算法 樣本集 決策樹

1 引言

隨著社會各個領(lǐng)域的快速發(fā)展，各種數(shù)據(jù)量成爆炸式增長，網(wǎng)絡(luò)數(shù)據(jù)尤為體現(xiàn)。這些數(shù)據(jù)的增長呈現(xiàn)出的特點為非規(guī)則性、突發(fā)性，研究它們的關(guān)鍵點就在于時間特性和數(shù)據(jù)量特性。如何在這些不規(guī)則的數(shù)據(jù)中找到某些數(shù)據(jù)的變化規(guī)律以及走勢，已經(jīng)成為現(xiàn)在數(shù)據(jù)研究中的重點和熱點。本文采用ID3算法[1]建立決策樹，可以較為有效的解決這些問題。

2 ID3決策樹算法的基本原理

決策樹又可稱之為判定樹。在決策樹中，某一屬性的一次測試由內(nèi)部的某個節(jié)點代表，每個測試結(jié)果由每條邊代表，某個類或類的分布由葉節(jié)點代表。在ID3決策樹算法中信息熵和信息增量的計算是最主要的兩個部分。

ID3決策樹算法的描述[2]如下：

ID3（A：條件屬性集合，d：決策屬性，U：訓練集）返回一棵決策樹

{

if U為空，返回一個值為Failure的單結(jié)點；//為了程序的健壯性這種情況一般不會出現(xiàn)

if U由其值均為相同決策屬性值的記錄構(gòu)成，返回帶有該值的單結(jié)點；//此分支到此結(jié)束

if A為空，則返回一個單結(jié)點，其值為在U的記錄中找到頻率最高的決策屬性值；//這時記錄出現(xiàn)誤分類

將A中屬性之間具有最大I(d;a)的屬性賦給a；

將屬性a的值賦給{aj|j=1,2,...,m}；

將分別由對應(yīng)于a的值aj的記錄組成的U的子集賦給{uj|j=1,2,...,m}；

返回一棵樹，其根標記為a，樹枝標記為a1,a2,...am；

再構(gòu)造樹：ID3(A-{a},d,u1)，ID3(A-{a},d,u2)，...，ID3(A-{a},d,um)；//遞歸算法}

3 利用ID3算法建立決策樹的過程

3.1 數(shù)據(jù)量定義

假設(shè)數(shù)據(jù)的訓練樣本集[3]為S，且對其在兩個方向進行定義，一個為時間方向，一個為數(shù)據(jù)量大小方向，分別定義為ht、hd。

即數(shù)據(jù)樣本的集合為

根據(jù)上述數(shù)據(jù)集，利用ID3算法，即可得出在不同時間域數(shù)據(jù)的分布以及變化情況，即滿足某些趨勢條件下信息熵的情況。

3.2 信息熵的獲取

假設(shè)從上述數(shù)據(jù)集中取出某種具有同種屬性的數(shù)據(jù)s。

在s中假設(shè)取三個相鄰的數(shù)值，分別為an-1bn-1、anbn、an+1bn+1。當同時滿足

條件時（約定該條件為θn），該屬性數(shù)據(jù)開始出現(xiàn)上升趨勢，即該數(shù)據(jù)有可能成為熱點數(shù)據(jù)。當θn-1、θn、θn+1均出現(xiàn)時，該數(shù)據(jù)必然成為熱點數(shù)據(jù)，且較長時間處于上升趨勢。在相反條件下，當滿足

圖1：根據(jù)ID3算法生成的決策樹

3.3 決策樹的生成

根據(jù)以上條件，可生成的決策樹如圖1所示。

4 結(jié)束語

從以上ID3算法的應(yīng)用研究[4]中，可以看出此算法在數(shù)據(jù)規(guī)律以及數(shù)據(jù)趨勢的應(yīng)用中效果明顯，提高了數(shù)據(jù)判定的真實性。同時，此算法也顯露出不足之處，如在數(shù)據(jù)建樹的過程較為復(fù)雜，即時性需要提高。此種應(yīng)用研究適合于網(wǎng)絡(luò)數(shù)據(jù)的跟蹤與處理，對突發(fā)熱點事件有較強反饋處理能力。

[1]王永梅,胡學鋼.決策樹中ID3算法的研究[J].安徽大學學報(自然科學版),2011(03)：121.

[2]孫怡哲.一種改進的決策樹算法研究與應(yīng)用[D].遼寧：遼寧工程技術(shù)大學,2010.

[3]朱顥東.ID3算法的改進和簡化[J].上海交通大學學報,2010(07)：242-243.

[4]周愛華.決策樹技術(shù)在實驗室評估中的應(yīng)用研究[D].北京：中國石油大學,2011．

作者單位 滄州職業(yè)技術(shù)學院 河北省滄州市 061001

孫亞非（1981-），女，河北省唐山市人。碩士學位?，F(xiàn)為滄州職業(yè)技術(shù)學院信息工程系講師。研究方向為計算機應(yīng)用技術(shù)。

●本論文為：2017年度滄州市社會科學發(fā)展研究課題。課題名稱為：《基于大數(shù)據(jù)的高職院校畢業(yè)生就業(yè)情況的研究》，課題批準號為：2017213，一般課題。