上下文決策樹(shù)學(xué)習(xí)算法及其在機(jī)械波圖像中的應(yīng)用

許 晴， 李凡長(zhǎng)

（蘇州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 蘇州 215006）

上下文決策樹(shù)學(xué)習(xí)算法及其在機(jī)械波圖像中的應(yīng)用

許 晴， 李凡長(zhǎng)

（蘇州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 蘇州 215006）

機(jī)器學(xué)習(xí)技術(shù)在現(xiàn)代各種數(shù)據(jù)分析中是備受關(guān)注的有效方法之一，目前已在眾多領(lǐng)域得到廣泛應(yīng)用。文章以目前較為流行的決策樹(shù)學(xué)習(xí)為重點(diǎn)，介紹了決策樹(shù)學(xué)習(xí)的幾個(gè)較為成熟的算法，并將相應(yīng)算法應(yīng)用到機(jī)械波圖像分析中，提出了5點(diǎn)、7點(diǎn)與11點(diǎn)上下文決策樹(shù)學(xué)習(xí)算法。通過(guò)實(shí)驗(yàn)驗(yàn)證該處理方法是有效的。

決策樹(shù)；信息熵；信息增益；機(jī)械波圖像

決策樹(shù)學(xué)習(xí)是機(jī)器學(xué)習(xí)中重要的學(xué)習(xí)方法之一，也是應(yīng)用最廣的歸納推理算法之一。它是一種逼近離散函數(shù)值的方法，分類(lèi)精度高，操作簡(jiǎn)單，并且對(duì)噪音數(shù)據(jù)有很好的健壯性，在數(shù)據(jù)分析中有著廣泛的應(yīng)用［1－2］。本文在學(xué)習(xí)決策樹(shù)算法的基礎(chǔ)上，引入上下文模型來(lái)改進(jìn)決策樹(shù)學(xué)習(xí)算法，從而實(shí)現(xiàn)對(duì)機(jī)械波圖像的分析［3］。具體處理方法是首先通過(guò)決策樹(shù)學(xué)習(xí)算法從一組數(shù)據(jù)中學(xué)習(xí)機(jī)械波圖像的一般規(guī)律，從而發(fā)現(xiàn)該物理現(xiàn)象的波特征，然后在學(xué)習(xí)到的圖像特征基礎(chǔ)上，形成相應(yīng)的方法，在該方法的基礎(chǔ)上，對(duì)新的數(shù)據(jù)進(jìn)行評(píng)估預(yù)測(cè)［4］。通過(guò)實(shí)驗(yàn)驗(yàn)證該方法是有效的。

1 決策樹(shù)學(xué)習(xí)

1.1 決策樹(shù)學(xué)習(xí)簡(jiǎn)述

決策樹(shù)學(xué)習(xí)是以實(shí)例為基礎(chǔ)的學(xué)習(xí)算法，是目前較為流行的歸納學(xué)習(xí)算法之一。決策樹(shù)學(xué)習(xí)有多種形式，其中心思想是輸入已知數(shù)據(jù)（即訓(xùn)練集），通過(guò)決策樹(shù)算法對(duì)其進(jìn)行訓(xùn)練，產(chǎn)生一棵決策樹(shù)，然后對(duì)其進(jìn)行分析，從而得到研究者想要的預(yù)測(cè)結(jié)果［5］。

1.2 決策樹(shù)學(xué)習(xí)算法

基本決策樹(shù)學(xué)習(xí)算法是一個(gè)貪婪算法，采用自頂向下、分而治之的遞歸方式構(gòu)造一棵決策樹(shù)來(lái)進(jìn)行學(xué)習(xí)。學(xué)習(xí)構(gòu)造決策樹(shù)的一個(gè)基本歸納算法［6］如下：

算法：根據(jù)給定數(shù)據(jù)集產(chǎn)生一個(gè)決策樹(shù)。

輸入：訓(xùn)練樣本，各屬性均取離散數(shù)值，可供歸納的候選屬性集為：attribute－list。

輸出：決策樹(shù)。

處理流程：

（1）創(chuàng)建一個(gè)結(jié)點(diǎn)N。

（2）若該結(jié)點(diǎn)中的所有樣本均為同一類(lèi)別C，則返回N作為葉結(jié)點(diǎn)并標(biāo)志為類(lèi)別C。

（3）若attribute－list為空，則返回N為葉結(jié)點(diǎn)，并標(biāo)記為該結(jié)點(diǎn)所含樣本中類(lèi)別個(gè)數(shù)最多的類(lèi)別。

（4）從attribute－list選擇一個(gè)分類(lèi)訓(xùn)練樣例能力最好的屬性test－attribute，并將結(jié)點(diǎn)N標(biāo)記為test－attribute。

（5）對(duì)于test－attribute中每個(gè)已知取值ai，準(zhǔn)備劃分結(jié)點(diǎn)N所包含的樣本集。

（6）根據(jù)test－attrtibute＝ai條件，從結(jié)點(diǎn)N產(chǎn)生相應(yīng)的一個(gè)分支，以表示該預(yù)測(cè)條件。

（7）設(shè)si為test－attrtibute＝ai條件所獲得的樣本集合。

（8）若si為空，則將相應(yīng)葉結(jié)點(diǎn)標(biāo)記為該結(jié)點(diǎn)所含樣本中類(lèi)別個(gè)數(shù)最多的類(lèi)別。

（9）否則將相應(yīng)葉結(jié)點(diǎn)標(biāo)志generate－decision－tree（si，attribute－list－test－attribute）返回值。

1.3 ID3算法

在各種決策樹(shù)學(xué)習(xí)算法中，最具有影響的是ID3算法。其核心思想是在決策樹(shù)各級(jí)結(jié)點(diǎn)上選擇屬性時(shí)，利用信息熵原理，選用信息增益作為屬性的選擇標(biāo)準(zhǔn)。其具體方法為：檢測(cè)所有的屬性，選擇信息增益最大的屬性產(chǎn)生決策樹(shù)結(jié)點(diǎn)，由該屬性的不同取值建立分支，再對(duì)各分支的子集遞歸調(diào)用該方法，建立決策樹(shù)結(jié)點(diǎn)的分支，直到所有子集僅包含同一類(lèi)別的數(shù)據(jù)為止；最后得到一棵決策樹(shù)，它可以用來(lái)對(duì)新的樣本進(jìn)行分類(lèi)［7］。

（1）用熵度量樣例的均一性。熵是信息論中廣泛使用的度量標(biāo)準(zhǔn)，刻畫(huà)了任意樣例集的純度，具體定義為：給定包含關(guān)于某個(gè)目標(biāo)概念的正反樣例的樣例集S，則S相對(duì)布爾型分類(lèi)的熵為：

其中，p＋為在S中正例的比例；p－為在S中反例的比例。

以上是目標(biāo)分類(lèi)為布爾型情況下的熵，更一般的，如果目標(biāo)屬性具有c個(gè)不同的值，那么S相對(duì)于c個(gè)狀態(tài)的分類(lèi)的熵定義為：

其中，pi為S中屬于類(lèi)別i的比例［8］。

（2）用信息增益度量期望的熵降低。熵是衡量訓(xùn)練樣例集合純度的標(biāo)準(zhǔn)，而信息增益則是屬性分類(lèi)訓(xùn)練數(shù)據(jù)能力的度量標(biāo)準(zhǔn)。一個(gè)屬性A相對(duì)樣例集合S的信息增益Gain（S，A）為：

簡(jiǎn)單記作：Gain（S，A）≡Entropy（S）－E（A）。

（3）式中，Values（A）為屬性A所有可能值的集合；Sv為S中屬性A的值為v的子集，即Sv＝｛s∈S｜A（s）＝v｝；（3）式中第1項(xiàng)為原集合S的熵，第2項(xiàng)為用A分類(lèi)S后熵的期望值。

信息增益是ID3算法增長(zhǎng)樹(shù)的每一步中選取最佳屬性的度量標(biāo)準(zhǔn)，且應(yīng)當(dāng)選取各屬性中Gain（A）最大的，因?yàn)樵贓ntropy固定的情況下，E（A）值最小，即以A為被選屬性所得分類(lèi)的信息熵最小，此時(shí)對(duì)向量空間分類(lèi)的穩(wěn)定性最好。以A為根結(jié)點(diǎn)，對(duì)以后的各結(jié)點(diǎn)不斷調(diào)用上述過(guò)程，從而構(gòu)成一棵決策樹(shù)［9］。ID3算法理論清晰、方法簡(jiǎn)單、學(xué)習(xí)能力較強(qiáng)，但只對(duì)比較小的數(shù)據(jù)集有效，對(duì)噪聲比較敏感，當(dāng)訓(xùn)練數(shù)據(jù)集加大時(shí)，決策樹(shù)可能會(huì)隨之改變［10］。

2 基于上下文模型的決策樹(shù)

2.1 先驗(yàn)?zāi)Ｐ?/h3>

先驗(yàn)?zāi)Ｐ椭械拿總€(gè)對(duì)象類(lèi)別都關(guān)聯(lián)著一個(gè)二進(jìn)制變量，表示是否在圖像中出現(xiàn)，以及一個(gè)高斯變量，表示它的位置［11］。

2.1.1 共現(xiàn)先驗(yàn)

對(duì)象對(duì)的共現(xiàn)是一個(gè)簡(jiǎn)單但有效的背景信息，本文使用二叉樹(shù)模型編碼共現(xiàn)統(tǒng)計(jì)數(shù)［12］。樹(shù)中的每個(gè)結(jié)點(diǎn)bi表示相應(yīng)的對(duì)象i是否在圖像中出現(xiàn)。當(dāng)pa（i）為結(jié)點(diǎn)i的父，所有二進(jìn)制變量聯(lián)合概率根據(jù)樹(shù)結(jié)構(gòu)可分解［13］為：

其中，下標(biāo)i表示與對(duì)象i對(duì)應(yīng)的變量，用一個(gè)沒(méi)有下標(biāo)的符號(hào)表示所有對(duì)應(yīng)變量的集合，b≡｛bi｝。一個(gè)父－子對(duì)可能有正相關(guān)關(guān)系（地板和墻常常共現(xiàn)），也可能有負(fù)相關(guān)關(guān)系（地板很少和天空同時(shí)出現(xiàn)）［14］。

2.1.2 空間先驗(yàn)

（1）空間位置表示。對(duì)象出現(xiàn)在另一個(gè)對(duì)象特定的相對(duì)位置上。例如，電腦屏幕通常出現(xiàn)在鍵盤(pán)和鼠標(biāo)之上。通過(guò)添加位置變量到樹(shù)模型來(lái)捕捉這些空間關(guān)系，用包圍框取代對(duì)象分割，它是所有分割點(diǎn)的最小封閉框，表示對(duì)象實(shí)例的位置。設(shè)lx、ly分別為包圍框中心的水平和垂直坐標(biāo)，lw、lh分別為框的寬和高。假設(shè)圖像高度為1，且lx＝0，ly＝0是圖像的中心。對(duì)象中心間的預(yù)期距離取決于對(duì)象的大小。運(yùn)用以下坐標(biāo)變換來(lái)表示在三維世界坐標(biāo)中的對(duì)象位置，即

其中，Lz為觀(guān)察者與對(duì)象之間的距離；Hi為對(duì)象i的物理高度。每個(gè)對(duì)象類(lèi)的高度可以從算法獲得的注解數(shù)據(jù)推斷，但真實(shí)對(duì)象的大小采用手動(dòng)編碼獲?。ㄈ说母叨葹?.7m，車(chē)的高度為1.5m）。

（2）空間位置先驗(yàn)。從不同的角度來(lái)看，對(duì)象的水平相對(duì)位置會(huì)有很大的不同，并且已經(jīng)顯示水平位置一般有微弱的背景信息。因此忽略lx，只考慮ly、lz來(lái)捕捉豎直信息和規(guī)模關(guān)系。假設(shè)Lys、Lzs是獨(dú)立的，即對(duì)象的豎直位置與到圖像平面的距離是獨(dú)立的。本文建模Lys為聯(lián)合高斯，使用對(duì)數(shù)正態(tài)分布建模Lzs，因?yàn)樗鼈兪冀K是正的，并更多地圍繞小值分布。本文為對(duì)象類(lèi)i定義一個(gè)位置變量Li＝（Ly，lgLz），并且假設(shè)Lis為聯(lián)合高斯。為了簡(jiǎn)單起見(jiàn)，對(duì)對(duì)象類(lèi)的空間關(guān)系進(jìn)行建模，如果在一張圖像上有多個(gè)對(duì)象類(lèi)實(shí)例i，Li代表所有實(shí)例中的中心位置。

假設(shè)以存在變量b為條件時(shí)，Lis的依賴(lài)結(jié)構(gòu)與二叉樹(shù)具有相同的樹(shù)結(jié)構(gòu)，即

其中，以父位置和父與子都出現(xiàn)與否為條件，每邊勢(shì)p（Li｜Lpa（i），bi，bpa（i））編碼一個(gè)子位置的分布。

結(jié)合（4）式和（6）式，所有二進(jìn)制和高斯變量的聯(lián)合分布可以表示為：

2.2 測(cè)量模型

2.2.1 混合全局圖像特征

要旨描述符是圖像的低維表示，用來(lái)捕捉場(chǎng)景的粗結(jié)構(gòu)和空間布局。引入要旨作為每個(gè)存在變量bi的測(cè)量，將全局圖像特征并入本文測(cè)量的模型，使上下文模型能夠完全地推斷出場(chǎng)景類(lèi)別，尤其有助于推測(cè)室內(nèi)對(duì)象還是室外對(duì)象應(yīng)該出現(xiàn)在圖像上。

2.2.2 集成定位檢測(cè)器的輸出

為了檢測(cè)并定位圖像中的對(duì)象實(shí)例，首先運(yùn)用現(xiàn)有的單目標(biāo)檢測(cè)器，為每個(gè)對(duì)象類(lèi)獲得1組候選窗口。用i表示對(duì)象類(lèi)，k索引由基線(xiàn)檢測(cè)器產(chǎn)生的候選窗口。每個(gè)檢測(cè)器輸出提供了1個(gè)評(píng)分sik和1個(gè)包圍框，對(duì)（5）式進(jìn)行坐標(biāo)變換以獲得位置變量Wik＝（Ly，lgLz），分配一個(gè)二進(jìn)制變量cik給每個(gè)窗口，代表它是正確的檢測(cè)（cik＝1）或假陽(yáng)性（cik＝0）。如果一個(gè)候選窗口是對(duì)象i的正確檢測(cè)（cik＝1），則Wik為一個(gè)高斯向量，均值為L(zhǎng)i，位置為對(duì)象i的位置，如果窗口為假陽(yáng)性（cik＝0），Wik與Li獨(dú)立，且均勻分布。

2.3 學(xué)習(xí)

2.3.1 學(xué)習(xí)對(duì)象依賴(lài)結(jié)構(gòu)

本文從一組完全標(biāo)記的圖像中學(xué)習(xí)對(duì)象間的依賴(lài)結(jié)構(gòu)。周劉算法是學(xué)習(xí)樹(shù)模型的一個(gè)簡(jiǎn)單而有效的方法［15］，能最大限度地提高數(shù)據(jù)的似然性，該算法使用示例值計(jì)算所有變量共同信息，再發(fā)現(xiàn)最大權(quán)重生成樹(shù)，它的邊權(quán)重為由邊連接的變量間的共同信息。本文用一組標(biāo)記的圖片的bis示例學(xué)習(xí)樹(shù)結(jié)構(gòu)，即使有100個(gè)對(duì)象，成千上萬(wàn)的訓(xùn)練圖片，Matlab可在幾秒鐘內(nèi)學(xué)習(xí)到樹(shù)模型。

盡管周劉算法的輸出是一個(gè)無(wú)向樹(shù)，本文可以選取某個(gè)對(duì)象作為樹(shù)的根，以獲得有向樹(shù)結(jié)構(gòu)。在學(xué)習(xí)過(guò)程中，本文并沒(méi)有使用任何有關(guān)對(duì)象類(lèi)之間固有層次結(jié)構(gòu)的信息，周劉算法只選擇強(qiáng)依賴(lài)性的對(duì)象類(lèi)。然而，學(xué)習(xí)到的樹(shù)結(jié)構(gòu)用一種自然的層次組織對(duì)象，例如，以建筑為根的子樹(shù)，會(huì)有許多出現(xiàn)在街道場(chǎng)景的對(duì)象，而以水槽為根的子樹(shù)則包含常常出現(xiàn)在廚房的對(duì)象。因此，許多非葉結(jié)點(diǎn)用來(lái)表示粗規(guī)模的元對(duì)象或者場(chǎng)景類(lèi)，即學(xué)習(xí)到的樹(shù)結(jié)構(gòu)捕捉對(duì)象和場(chǎng)景間的固有層次結(jié)構(gòu)能促使更好地進(jìn)行對(duì)象識(shí)別及場(chǎng)景理解表現(xiàn)［16］。

2.3.2 學(xué)習(xí)模型參數(shù)

用訓(xùn)練圖片的地面實(shí)況標(biāo)簽學(xué)習(xí)先驗(yàn)?zāi)Ｐ偷膮?shù)，p（bi｜bpa（i））可以簡(jiǎn)單地通過(guò)數(shù)父 －子對(duì)象共現(xiàn)的對(duì)數(shù)獲得。對(duì)于每個(gè)父－子對(duì)象對(duì)，本文為p（bi｜bpa（i），bi，bpa（i））使用3個(gè)不同的高斯分布：當(dāng)2個(gè)對(duì)象均出現(xiàn)，即bi＝1，bpa（i）＝1，子對(duì)象的位置Li取決于其父位置Lpa（i）。當(dāng)對(duì)象出現(xiàn)而它的父對(duì)象沒(méi)有出現(xiàn)，即bi＝1，bpa（i）＝0，則Li獨(dú)立于Lpa（i）。當(dāng)一個(gè)對(duì)象本身沒(méi)有出現(xiàn)，假設(shè)Li與其他所有對(duì)象位置均獨(dú)立，并且它的均值與所有圖片的平均位置對(duì)象i相等。

在測(cè)量模型的訓(xùn)練中，p（g｜bi）可以使用從每張訓(xùn)練圖片中計(jì)算得到的要旨描述符，因?yàn)樵撘际窍蛄?，為了避免過(guò)度適合，使用邏輯衰退為每個(gè)對(duì)象類(lèi)匹配p（bi｜g），由此可用p（g｜bi）＝p（bi｜g）p（g）／p（bi）來(lái)間接地估計(jì)p（g｜bi）［17］。

為了學(xué)習(xí)剩余參數(shù)，本文為訓(xùn)練圖片的每個(gè)對(duì)象類(lèi)運(yùn)行局部檢測(cè)器。將局部檢測(cè)器的評(píng)分排序，則sik為第k高的評(píng)分的類(lèi)，p（cik｜sik）被訓(xùn)練使用邏輯衰退，從中可以計(jì)算似然性p（sik｜c(diǎn)ik）＝p（cik｜sik）p（sik）／p（cik）。 正 確 檢 測(cè) 的 可 能 性p（cik｜bi）使用訓(xùn)練集中的地面實(shí)況標(biāo)簽和正確檢測(cè)來(lái)進(jìn)行訓(xùn)練。

3 實(shí)驗(yàn)分析

本文主要探索決策樹(shù)學(xué)習(xí)算法在機(jī)械波圖像分析中的應(yīng)用，以決策樹(shù)學(xué)習(xí)算法為基礎(chǔ)，結(jié)合上下文模型加以改進(jìn)，在weka中加以實(shí)現(xiàn)，然后通過(guò)學(xué)習(xí)大量的實(shí)驗(yàn)數(shù)據(jù)，找出機(jī)械波圖像的一般規(guī)律并加以分析［18］。

3.1 實(shí)驗(yàn)準(zhǔn)備

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

機(jī)器學(xué)習(xí)的3個(gè)主要特征為：任務(wù)的種類(lèi)、衡量任務(wù)提高的標(biāo)準(zhǔn)及經(jīng)驗(yàn)的來(lái)源。其中，經(jīng)驗(yàn)來(lái)源為實(shí)驗(yàn)數(shù)據(jù)，由此可見(jiàn)，數(shù)據(jù)采集是機(jī)器學(xué)習(xí)中必不可少的組成部分。本實(shí)驗(yàn)由于客觀(guān)條件的限制，無(wú)法搜集現(xiàn)成的數(shù)據(jù)，本文自行設(shè)計(jì)實(shí)驗(yàn)數(shù)據(jù)，并根據(jù)物理學(xué)知識(shí)，了解到機(jī)械波圖像基本符合正余弦特征分布，因此設(shè)計(jì)實(shí)驗(yàn)數(shù)據(jù)以正余弦公式為基礎(chǔ)。以5點(diǎn)上下文模型決策樹(shù)學(xué)習(xí)為例，其具體構(gòu)造過(guò)程如下：

（1）選定一個(gè)最簡(jiǎn)單的機(jī)械波圖像，其滿(mǎn)足y＝sinx。

（2）關(guān)注該機(jī)械波圖像上的5個(gè)位置的點(diǎn)，分別為0、π／2、π、3π／2、2π，其對(duì)應(yīng)的y值分別為0、1、0、－1、0。

（3）設(shè)定誤差為±0.1。

（4）設(shè)定一個(gè)類(lèi)別屬性，當(dāng)5點(diǎn)的值均在誤差內(nèi)，則認(rèn)為正確，記為1；否則，如果有1個(gè)或多個(gè)點(diǎn)的值溢出誤差，則認(rèn)為錯(cuò)誤，記為0。

（5）設(shè)計(jì)數(shù)據(jù)若干組，其中包含所需的訓(xùn)練集以及測(cè)試集，且包含故意錯(cuò)誤數(shù)據(jù)若干。

按照上述步驟，實(shí)驗(yàn)數(shù)據(jù)即可構(gòu)造完畢，其基本情況見(jiàn)文獻(xiàn) ［19］。

3.1.2 實(shí)驗(yàn)算法

本文通過(guò)對(duì)決策樹(shù)算法的學(xué)習(xí)，結(jié)合上下文模型構(gòu)造決策樹(shù)實(shí)現(xiàn)了分類(lèi)預(yù)測(cè)。以5點(diǎn)上下文模型決策樹(shù)學(xué)習(xí)為例，在機(jī)械波圖像中，根據(jù)y＝sinx取5個(gè)點(diǎn)，分別為0、π／2、π、3π／2、2π，由經(jīng)驗(yàn)可知，該圖像中，如果已知了0點(diǎn)，可根據(jù)0點(diǎn)決定π／2的位置，從而確定π的位置，依此類(lèi)推，5點(diǎn)的位置均可以確定，該過(guò)程用到了上下文信息，根據(jù)一階 Markov隨機(jī)場(chǎng)論（Markov random field，簡(jiǎn)稱(chēng)MRF），在樹(shù)結(jié)構(gòu)中，結(jié)點(diǎn)的父親可建模為其上下文，上下文信息有助于分類(lèi)過(guò)程達(dá)到更高的分類(lèi)精度［20］。具體實(shí)現(xiàn)算法為：

（1）確定0、π／2、π、3π／2、2π5個(gè)點(diǎn)，其中“0”點(diǎn)定為根結(jié)點(diǎn)。

（2）根據(jù)“0”點(diǎn)的不同屬性值計(jì)算信息熵及信息增益，從而確定正確的一類(lèi)。

（3）不考慮“0”點(diǎn)錯(cuò)誤分支，在其正確分支下按照同樣方法確定π／2點(diǎn)的正確分支。

（4）按照以上方法，依次確定π、3π／2、2π點(diǎn)，構(gòu)造一棵基于上下文模型的決策樹(shù)。

（5）按照該決策樹(shù)對(duì)新的數(shù)據(jù)集進(jìn)行分類(lèi)。

以上實(shí)現(xiàn)了5點(diǎn)上下文模型決策樹(shù)學(xué)習(xí)算法，同樣的方法還可以實(shí)現(xiàn)7點(diǎn)以及11點(diǎn)上下文模型決策樹(shù)學(xué)習(xí)算法等。

3.2 實(shí)驗(yàn)結(jié)果

3.2.1 基于上下文模型的決策樹(shù)算法的結(jié)果

5點(diǎn)、7點(diǎn)與11點(diǎn)上下文模型決策樹(shù)算法實(shí)驗(yàn)結(jié)果如圖1所示，由圖1可以看出，基于上下文模 型 的 決 策 樹(shù) 算 法 （Context－Based Decision Tree，簡(jiǎn)稱(chēng)CBDT）的測(cè)試分類(lèi)精度較高，且隨著數(shù)據(jù)集逐漸變大，其精確度也不斷增大，最終趨于穩(wěn)定，且當(dāng)點(diǎn)數(shù)逐漸增多，即上下文信息更加明顯時(shí)，精確度也有所上升。

圖1 上下文模型決策樹(shù)算法結(jié)果比較

3.2.2 幾種算法結(jié)果的比較

為了說(shuō)明基于上下文模型的決策樹(shù)可以很好地學(xué)習(xí)并進(jìn)行分類(lèi)預(yù)測(cè)，本文將其與SimpleCart算法以及KNN算法的測(cè)試分類(lèi)精度加以比較。

本文設(shè)計(jì)了8個(gè)數(shù)據(jù)集，從dataset 1的100組數(shù)據(jù)到dataset 8的800個(gè)數(shù)據(jù)，以100的增長(zhǎng)量遞增，分別用這3個(gè)算法對(duì)8個(gè)數(shù)據(jù)集進(jìn)行學(xué)習(xí)，測(cè)試其分類(lèi)精度，結(jié)果如圖2所示。

圖2 不同算法分類(lèi)精度的比較

由圖2可以看出，KNN的精度最低，Simple－Cart的精度較高，CBDT的精度最高。

4 結(jié)束語(yǔ)

本文主要介紹了決策樹(shù)學(xué)習(xí)的基本知識(shí)與概念和幾種較為成熟的算法，并提出了一種基于上下文模型的決策樹(shù)，這種決策樹(shù)學(xué)習(xí)結(jié)合了上下文信息來(lái)構(gòu)造決策樹(shù)，從而消除了構(gòu)造過(guò)程中一些明顯的錯(cuò)誤組合，提高了分類(lèi)精度。本文利用基于上下文模型的決策樹(shù)分析物理學(xué)中的機(jī)械波圖像，用決策樹(shù)算法從設(shè)計(jì)的實(shí)驗(yàn)數(shù)據(jù)中學(xué)習(xí)圖像的一般規(guī)律，并用于分類(lèi)預(yù)測(cè)。實(shí)驗(yàn)證明，基于上下文模型的決策樹(shù)的精度相對(duì)較好，且隨著數(shù)據(jù)量的增大，趨向于穩(wěn)定。

本文在以下方面可進(jìn)一步改進(jìn)：

（1）本文只運(yùn)用基于上下文模型的決策樹(shù)在簡(jiǎn)單的機(jī)械波圖像上進(jìn)行研究，可增加實(shí)驗(yàn)圖像的復(fù)雜性及實(shí)驗(yàn)數(shù)據(jù)的大量性，以進(jìn)一步驗(yàn)證基于上下文模型的決策樹(shù)的分類(lèi)預(yù)測(cè)精度。

（2）基于上下文模型的決策樹(shù)不僅可以進(jìn)行分類(lèi)預(yù)測(cè)，還可以檢測(cè)脫離上下文的對(duì)象等。本文運(yùn)用了該決策樹(shù)的一部分知識(shí)，可以考慮繼續(xù)對(duì)基于上下文模型的決策樹(shù)的深入研究。

（3）當(dāng)研究的對(duì)象更加復(fù)雜時(shí)，可采用隱Markov樹(shù)模型（HMT）［20］，不僅能以結(jié)點(diǎn)的雙親為其上下文，結(jié)點(diǎn)間為因果關(guān)系，還可以使建模雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)同時(shí)作為結(jié)點(diǎn)的上下文，結(jié)點(diǎn)間為非因果關(guān)系，這樣可以使算法分類(lèi)精度更高。

［1］王 源，王甜甜.改進(jìn)決策樹(shù)算法的應(yīng)用研究［J］.電子科技，2010，23（9）：89－91.

［2］胡學(xué)鋼，方玉成，張玉紅.基于Logistic回歸分析的直推式遷移學(xué)習(xí)［J］.合肥工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，2010，33（12）：1797－1801，1810.

［3］倪海鷗.決策樹(shù)算法研究綜述［J］.寧波廣播電視大學(xué)學(xué)報(bào)，2008，6（3）：113－115.

［4］郭亞寧，馮莎莎.基于決策樹(shù)方法的數(shù)據(jù)挖掘分析［J］.軟件導(dǎo)刊，2010，9（9）：103－104.

［5］Mitchell T M.Machine Learning［M］.曾華軍，張銀奎，譯.北京：機(jī)械工業(yè)出版社，2011：38－44.

［6］邢曉宇，余建坤，陳 磊.決策樹(shù)算法在學(xué)生考試成績(jī)中的應(yīng)用［J］.云南民族大學(xué)學(xué)報(bào)：自然科學(xué)版，2009，18（1）：77－80.

［7］胡蘭蘭.決策樹(shù)算法在淘寶店鋪中的應(yīng)用研究 ［J］.貴州師范學(xué)院學(xué)報(bào)，2010，26（6）：40－43.

［8］牛曉博，趙 虎，張玉冊(cè).基于決策樹(shù)的海戰(zhàn)場(chǎng)艦艇意圖識(shí)別［J］.兵工自動(dòng)化，2010，29（6）：44－45.

［9］林忠會(huì).基于歸納學(xué)習(xí)的數(shù)據(jù)挖掘技術(shù)在高校教學(xué)研究中的應(yīng)用［D］.哈爾濱：哈爾濱工程大學(xué)，2008.

［10］余 藝.基于遺傳算法的分類(lèi)器的研究及其應(yīng)用［D］.武漢：武漢工程大學(xué)，2008.

［11］李秋穎.決策樹(shù)優(yōu)化與關(guān)聯(lián)規(guī)則挖掘算法研究［D］.遼寧大連：大連海事大學(xué)，2010.

［12］牛文穎.改進(jìn)的ID3決策樹(shù)分類(lèi)算法在成績(jī)分析中的應(yīng)用研究［D］.遼寧大連：大連交通大學(xué)，2008.

［13］譚俊璐.基于決策樹(shù)規(guī)則分類(lèi)算法的研究與應(yīng)用［D］.昆明：云南大學(xué)，2010.

［14］Choi M J，Torralba A，Willsky A S.A tree－based context model for object recognition［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2012，34：240－252.

［15］Chow C K，Liu C N.Approximating discrete probability distributions with dependence trees［J］.IEEE Trans Inform Theory，1968，14（3）：462－467.

［16］田永洪，黃鐵軍，高 文.基于多粒度樹(shù)模型的 Web站點(diǎn)描述及挖掘算法［J］.軟件學(xué)報(bào)，2004，15（9）：1393－1403.

［17］王 一，楊俊安，劉 輝.一種基于遺傳算法的SVM決策樹(shù)多分類(lèi)方法［J］.信號(hào)處理，2010，26（10）：1495－1499.

［18］張先武，郭 雷.一種新的支持向量機(jī)決策樹(shù)設(shè)計(jì)算法［J］.火力與指揮控制，2010，35（10）：31－35.

［19］陳 偉.改進(jìn)的ID3算法構(gòu)造決策樹(shù)［J］.淮南師范學(xué)院學(xué)報(bào)，2010，12（3）：33－35.

［20］朱顥東.ID3算法的改進(jìn)和簡(jiǎn)化［J］.上海交通大學(xué)學(xué)報(bào)，2010，44（7）：883－886.

Context－based decision tree learning algorithm and its application in images of mechanical wave

XU Qing， LI Fan－zhang
（School of Computer Science and Technology，Soochow University，Suzhou 215006，China）

Machine learning technique is an effective way of modern data analysis.It has been widely used in many fields and got a lot of attention.Focusing on the most popular decision tree learning，a few of the most sophisticated algorithms are introduced.Then the corresponding algorithm is applied to the image analysis of the mechanical wave，and the five－point，seven－point and eleven－point contextbased decision tree learning algorithms are proposed.The approach is proved to be meaningful by experimental validation.

decision tree；information entropy；information gain；mechanical wave image

TP181

A

1003－5060（2013）02－0160－05

10.3969／j.issn.1003－5060.2013.02.008

2012－07－11；

2012－09－28

國(guó)家自然科學(xué)基金資助項(xiàng)目（61033013；60775045）

許 晴（1990－），女，江蘇東臺(tái)人，蘇州大學(xué)碩士生；

李凡長(zhǎng)（1964－），男，云南宣威人，蘇州大學(xué)教授，博士生導(dǎo)師.

（責(zé)任編輯 閆杏麗）