淺析決策樹技術(shù)在計(jì)算機(jī)一級(jí)考試中的應(yīng)用

摘 要：決策樹技術(shù)是數(shù)據(jù)挖掘的一種實(shí)用而方便的分類技術(shù)。通過對(duì)計(jì)算機(jī)一級(jí)考試相關(guān)數(shù)據(jù)進(jìn)行研究，選取影響一級(jí)考試通過率的重要因素，經(jīng)過分析后作為決策屬性。根據(jù)ID3算法，挖掘出三大影響計(jì)算機(jī)一級(jí)考試通過率的重要屬性。本文結(jié)果表明，不僅獲得了具有一定價(jià)值的隱含信息，而且對(duì)計(jì)算機(jī)基礎(chǔ)教學(xué)有一定的指導(dǎo)作用。

關(guān)鍵詞：分類；計(jì)算機(jī)一級(jí)考試；決策樹

1 引言

目前，隨著信息技術(shù)的高速進(jìn)步與發(fā)展，各行各業(yè)對(duì)人才提出新的標(biāo)準(zhǔn)，能夠熟練使用計(jì)算機(jī)已成為人們必須掌握的一種基本工作技能。計(jì)算機(jī)等級(jí)考試通過率與一個(gè)學(xué)校的計(jì)算機(jī)基礎(chǔ)教學(xué)水平成一定的正比關(guān)系，為更好的提高計(jì)算機(jī)教學(xué)的效果，從歷年的計(jì)算機(jī)等級(jí)考試成績數(shù)據(jù)中挖掘出有用信息，采取有針對(duì)性的有效措施提高計(jì)算機(jī)等級(jí)考試的通過率，具有十分重要的實(shí)用價(jià)值。

2分類

2.1 基本概念

分類是一種重要的數(shù)據(jù)分析形式，它提取刻畫重要數(shù)據(jù)類的模型。這種模型稱為分類器，預(yù)測(cè)分類的（離散的、無序的）類標(biāo)號(hào)。例如，我們可以建立個(gè)分類模型，把銀行貸款申請(qǐng)劃分成安全或危險(xiǎn)。這種分析可以幫助我們更好地全面理解數(shù)據(jù)[1]。

2.2 決策樹歸納分類

分類是數(shù)據(jù)挖掘的重要部分，現(xiàn)代商業(yè)支持系統(tǒng)的主要功能大多為分類。在數(shù)據(jù)挖掘技術(shù)中，有很多種分類的技術(shù)，較常見的為如下幾種方法：決策樹算法、關(guān)聯(lián)算法、粗糙集、遺傳算法、貝葉斯分類等[2]。

決策樹分類分兩階段。第一階段是利用訓(xùn)練集建立并精化一棵決策樹，建立決策樹模型。第二階段是利用生成完畢的決策樹對(duì)輸入的數(shù)據(jù)進(jìn)行分類[3]。

2.3 ID3 算法描述

ID3 算法的核心是選擇決策樹各級(jí)結(jié)點(diǎn)的屬性，采用自頂向下的遞歸方式，根據(jù)屬性選擇的標(biāo)準(zhǔn)--最高信息增益，作為決策樹的一個(gè)結(jié)點(diǎn)[4]。該屬性使結(jié)果集對(duì)樣本分類所需要的信息量最小。

2.3.1 分類期望信息

設(shè)數(shù)據(jù)分區(qū)D為訓(xùn)練樣本的訓(xùn)練集，假定類標(biāo)號(hào)屬性具有m個(gè)不同值，定義m個(gè)不同類Ci （i=1，…，m），設(shè)Ci，D是D中Ci類元組的集合，|D|和|Ci，D|分別是D和Ci，D元組的個(gè)數(shù)，則對(duì)D中元組分類所需要期信息由下次給出[5]：

其中，pi是D中任意元組屬于類Ci的非零概率，并用|Ci，D|/|D|估計(jì)。

2.3.2 從決策樹種提出分類規(guī)則

規(guī)則表達(dá)式：IF-THEN。生成規(guī)則的方法為：

1）根節(jié)點(diǎn)到各個(gè)葉節(jié)點(diǎn)屬于一條規(guī)則。

2）根據(jù)每條路徑，以標(biāo)準(zhǔn)選擇恰當(dāng)?shù)膶傩宰鳛橐?guī)則前提（IF）部分，相應(yīng)的每條結(jié)點(diǎn)的葉節(jié)點(diǎn)為結(jié)論（THEN）部分。

3 決策樹分類在計(jì)算機(jī)一級(jí)考試中的應(yīng)用

3.1 數(shù)據(jù)準(zhǔn)備及預(yù)處理

筆者所在學(xué)校每年都會(huì)統(tǒng)計(jì)學(xué)生參與計(jì)算機(jī)考試的情況，本文從數(shù)據(jù)庫中選擇了2005年6月的計(jì)算機(jī)一級(jí)考試的411名學(xué)生作為研究對(duì)象，并進(jìn)行分析處理后得到表1數(shù)據(jù)：：

（1）將“是否完成計(jì)算機(jī)基礎(chǔ)課程學(xué)習(xí)”分為“完成”和“未完成”兩類。

（2）將“年級(jí)”分為“大一”、“大二”和“大三”三類。

（3）將“專業(yè)”分為“理科類”和“文科類”兩類。

（4）將“每周上機(jī)次數(shù)”分為“<3”“、3- 4”和“>4”三類。

（5）將“一級(jí)等級(jí)考試通過否”分為“是”和“否”兩類。

3.2構(gòu)造決策樹

根據(jù)表1構(gòu)建決策樹。根據(jù)ID3算法，按照計(jì)算機(jī)一級(jí)考試通過與否，逐步按照以下步驟構(gòu)建決策樹。

第一步：根據(jù)表1，計(jì)算分類所需要的期望值。

將類標(biāo)識(shí)屬性“是否通過計(jì)算機(jī)一級(jí)考試”分為兩類，D1代表通過計(jì)算機(jī)教試，D2代表沒有通過計(jì)算機(jī)考試。設(shè)D1對(duì)應(yīng)于“是”，D2對(duì)應(yīng)于“否”。對(duì)應(yīng)元組為D1=8，D2=6

根據(jù)ID3算法中屬性選擇度量--信息增益原理，可算出給定樣本分類所需要的期望值：

第二步：計(jì)算每個(gè)屬性的信息增益

首先計(jì)算屬性“是否完成計(jì)算機(jī)基礎(chǔ)課程學(xué)習(xí)”的信息增益

對(duì)于該屬性的類“完成”，有6個(gè)“是”元組，3個(gè)“否”元組。對(duì)于類“未完成”，有2個(gè)“是”元組，3個(gè)“否”元組。

則，對(duì)元組進(jìn)行分類所需要的期望信息為：

因此，這種劃分的信息增益

Gain（是否完成計(jì)算機(jī)基礎(chǔ)課程學(xué)習(xí)）=info（D1，D2）-info是否完成基礎(chǔ)課程=0.396位

同理，可以計(jì)算出Gain（年級(jí)）=-0.028 位，Gain（專業(yè)）= 0.128位，Gain（每周上機(jī)次數(shù)）=0.474位。

第三步：確定屬性結(jié)點(diǎn)

由于屬性“每周上機(jī)次數(shù)”的信息增益最高，因此被選為分裂屬性，作為第一個(gè)結(jié)點(diǎn)，將樣本訓(xùn)練集分為三部分。然后將每個(gè)部分依上述方法計(jì)算，可以得到最終決策樹如圖1所示：

圖1 生成決策樹

3.3 提取分類規(guī)則

IF“每周上機(jī)次數(shù)>4”AND“完成計(jì)算機(jī)基礎(chǔ)課程學(xué)習(xí)” THEN 通過率為：28.6%。

IF“每周上機(jī)次數(shù)>4”AND“未完成計(jì)算機(jī)基礎(chǔ)課程學(xué)習(xí)”AND “專業(yè)為理科類”THEN通過率為：7%。

IF“每周上機(jī)次數(shù)=3-4”AND“專業(yè)為理科類” THEN 通過率為：21.4%。

3.4 結(jié)果分析

根據(jù)上述分類規(guī)則，可以得到結(jié)論，詳見圖2所示：

圖2 通過率分布

在每周上機(jī)次數(shù)>3的學(xué)生中，有80%的學(xué)生通過計(jì)算機(jī)一級(jí)考試。在完成計(jì)算機(jī)基礎(chǔ)課程的學(xué)生中，有66.7%的學(xué)生通過計(jì)算機(jī)一級(jí)考試。在理科類學(xué)生中，有60%的學(xué)生通過計(jì)算機(jī)一級(jí)考試。鑒于以上分析，得出以下結(jié)論：

（1）重視計(jì)算機(jī)基礎(chǔ)課程教學(xué)。首先，計(jì)算機(jī)一級(jí)考試通過率在某種程度上反映了各個(gè)高校的計(jì)算機(jī)基礎(chǔ)教育水平，因此各大高校越來越重視計(jì)算機(jī)基礎(chǔ)的教學(xué)，將計(jì)算機(jī)課程列入大學(xué)公共必修課。其次，計(jì)算機(jī)一級(jí)考試，由于其公平性、規(guī)范性、權(quán)威性，在社會(huì)各行各業(yè)中均有一定的影響力，在當(dāng)今激烈的人才競(jìng)爭(zhēng)中，通過計(jì)算機(jī)一級(jí)考試已經(jīng)成為具有計(jì)算機(jī)基本技術(shù)的能力證明。再次，從本文結(jié)論可知，影響計(jì)算機(jī)一級(jí)考試通過率的最重要因素為：修完計(jì)算機(jī)基礎(chǔ)課程。因此，建議各高校參加一級(jí)計(jì)算機(jī)考試的學(xué)生必須修完計(jì)算機(jī)基礎(chǔ)課程。

（2）加強(qiáng)學(xué)生的上機(jī)操作力度。從結(jié)論中可以看出，學(xué)生所學(xué)的專業(yè)類別并不是決定計(jì)算機(jī)一級(jí)考試通過率的最大因素。學(xué)校應(yīng)根據(jù)自身情況，增加學(xué)生每周上機(jī)的次數(shù)，以學(xué)生上機(jī)操作為主，教師指導(dǎo)為輔，加大學(xué)生自主學(xué)習(xí)能力的培養(yǎng)，使學(xué)生能在課余時(shí)間主動(dòng)學(xué)習(xí)并掌握知識(shí)，學(xué)以致用，為計(jì)算機(jī)一級(jí)考試做好知識(shí)儲(chǔ)備。

參考文獻(xiàn)

[1]Jiawei Han， Micheline Kamber ，Jianpei，范明，孟小峰譯.數(shù)據(jù)挖掘概念與技術(shù)[M].機(jī)械工業(yè)出版社，2012.

[2]遲慶云.基于決策樹的分類算法研究與應(yīng)用[D].2006.

[3] 胡少東.客戶細(xì)分方法探析[J]工業(yè)技術(shù)經(jīng)濟(jì) 2005，24（7）66-69.）

[4] Cygnus GNU Binutils Cygwin Online publication 1999.