機(jī)器學(xué)習(xí)在糖果形狀檢測中的應(yīng)用

摘要:機(jī)器學(xué)習(xí)解決工業(yè)檢查的問題，例如巧克力形狀的分類，主要是通過將實(shí)例編碼成特征向量和學(xué)習(xí)獲得決策樹。本文討論將機(jī)器學(xué)習(xí)理論應(yīng)用于糖果形狀的檢測，對糖果形狀的建模采用特征向量法，通過決策樹和k最近鄰算法實(shí)現(xiàn)糖果形狀的判定。

關(guān)鍵詞:特征向量法;決策樹;k最近鄰算法

1 研究的背景

全自動制糖生產(chǎn)線上各種糖果由傳送裝置送入分裝車間，在進(jìn)行包裝之前需要做的一項(xiàng)重要工作就是撿出糖體有缺損的糖果，即找出其中形狀不規(guī)則和破碎的糖果。在電腦控制的感應(yīng)定位系統(tǒng)和機(jī)械手的配合下迅速撿出不合格的糖果，既能提高工作效率又避免了人工接觸造成的食品安全問題。由于破損的糖果呈不規(guī)則形狀，對其判定帶來相當(dāng)難度，這就需要實(shí)現(xiàn)計(jì)算機(jī)視覺智能化。

計(jì)算機(jī)視覺中機(jī)器學(xué)習(xí)的研究為此類應(yīng)用提供了理論和實(shí)踐的依據(jù)。我們用特征向量法將糖果的形狀描述為知識(特征向量法適用于復(fù)雜形狀的描述)，特征向量和對應(yīng)的響應(yīng)作為決策樹的訓(xùn)練數(shù)據(jù)，通過訓(xùn)練使計(jì)算機(jī)“學(xué)習(xí)”合格糖果的形狀，最終將合格的糖果劃分到正確的分類，并與不合格的糖果區(qū)分開。

2 特征向量法建模

對糖果形狀的建模采用特征向量法，即把問題歸結(jié)為求某個非負(fù)矩陣最大特征根對應(yīng)的特征向量作為模型的解，用層次分析法中特征根法確定權(quán)重向量的問題。

設(shè)有三個糖果種類:一是圓形的薄荷糖(P1)，二是圓柱形的奶糖(P2)，三是橢圓形的水果糖(P3)。根據(jù)輪廓大小(B1)、陰影度(B2)、周長(B3)、直徑(B4)和對邊距(B5)這5個準(zhǔn)則去反復(fù)比較這三個歸類方案。

用層次分析法來解決這個問題的具體步驟如下:

首先將決策問題分解為三個層次，最上層為目標(biāo)層，即糖果形狀分類，最下層為方案層，有候選種類P1、P2、P3，中間層為準(zhǔn)則層，有輪廓大小(B1)、陰影度(B2)、周長(B3)、直徑(B 4)和對邊距(B 5)這5個準(zhǔn)則，層次結(jié)構(gòu)圖如圖1。其次確定各準(zhǔn)則對于目標(biāo)的權(quán)重及各方案對于每一準(zhǔn)則的權(quán)重。最后組合各層權(quán)重，得到方案層因素對于目標(biāo)的權(quán)重。

下面對準(zhǔn)則層各因素對于目標(biāo)的權(quán)重建立數(shù)學(xué)模型，可合理確定各方案對于每一個準(zhǔn)則的權(quán)重。至于權(quán)重的組合根據(jù)實(shí)際情況確定。

設(shè)準(zhǔn)則層中因素Bi對于目標(biāo)的權(quán)重為ωi，ωi反映了因素Bi(i= 1， ...， 5)相對于目標(biāo)的重要程度。即:

ω = (ω1， ω2， ω3， ω4， ω5)T{其中， ωi > 0，且1}

則ω就是各因素的權(quán)重向量，下面討論如何確定這個量。

第一步是采用兩兩比較的方法構(gòu)造判斷矩陣A。具體做法如下:

就糖果形狀檢測這一目標(biāo)，因素Bi與因素Bj比較，分別得到5個相對分值aij (j = 1，...，5)，若aij>1，則表示Bi比Bj重要，且重要程度是Bj的aij倍;aij1，則表示Bj比B i重要，且重要程度是B i的1/a ij(j= 1，...， 5)倍。

令A(yù) = (aij )5×5(其中，aii= 1， aij=1/aji， i， j = 1， 2， 3， 4， 5)，A稱為判斷矩陣。由這個矩陣的元素可以確定因素B i對于目標(biāo)的綜合分值， 這個值記為yi( i= 1， ...， 5)。

其次建立數(shù)學(xué)模型。下面來說明由相對分值aij( j= 1， ...， 5)如何得到分值yi(i= 1， ...，5)的。從判斷矩陣的建立過程可以看出，對于目標(biāo)，因素Bi的重要性由Bj( j = 1， ...， 5)綜合體現(xiàn)。由于Bj對于目標(biāo)的權(quán)重為ωj(j = 1， 2， 3， 4， 5)，所以用數(shù)量ai1， ...， ai5的加權(quán)平均值ai1ω1+ ai2ω2+ ai3ω3+ ai4ω4+ ai5ω5 作為因素Bi對于目標(biāo)的綜合分值(這樣可以減少由于Bj重要性的不同，而給Bi的權(quán)重造成的誤差)，即:

yi = ai1ω1+ ai2ω2+ ai3ω3+ ai4ω4+ ai5ω5(1)

令Y = (y1， y2， y3， y4， y5)T(2)

稱Y為5個因素的分值向量。

顯然，分值y i的大小反映因素Bi ( i= 1， ...， 5)對于目標(biāo)的重要程度，所以Y也是反映各因素重要程度的向量，亦即相對目標(biāo)而言，Y也是各因素的一個排序向量。既然向量ω與Y都是各因素對于目標(biāo)的排序向量，所以二者應(yīng)該成正比例關(guān)系，即存在正常數(shù)λ，使Y = λω(3)

由式(1)、(2)、(3) 得

A ω = λω (4)

λ是判斷矩陣A的正特征值，ω是λ對應(yīng)的特征向量。對該線性方程求解，得到糖果形狀樣本描述的模型。

3 學(xué)習(xí)獲得決策樹

接下來利用輸入的特征向量和對應(yīng)的響應(yīng)值(responses)來訓(xùn)練統(tǒng)計(jì)模型——決策樹。決策樹是從根結(jié)點(diǎn)遞歸構(gòu)造的。用所有的訓(xùn)練數(shù)據(jù)來在根結(jié)點(diǎn)處進(jìn)行分裂。所有的數(shù)據(jù)根據(jù)初始和替代分裂點(diǎn)來劃分給左、右孩子結(jié)點(diǎn)(就像在預(yù)測算法里做的一樣)。然后算法回歸的繼續(xù)分裂左右孩子結(jié)點(diǎn)。在以下情況下算法可能會在某個結(jié)點(diǎn)停止:

●樹的深度達(dá)到了指定的最大值。

●在該結(jié)點(diǎn)訓(xùn)練樣本的數(shù)目少于指定值，比如，沒有統(tǒng)計(jì)意義上的集合來進(jìn)一步進(jìn)行結(jié)點(diǎn)分裂了。

●在該結(jié)點(diǎn)所有的樣本屬于同一類(或者，如果是回歸的話，變化已經(jīng)非常小了)。

●跟隨機(jī)選擇相比，能選擇到的最好的分裂已經(jīng)基本沒有什么有意義的改進(jìn)了。

4 k-最近鄰算法

k-最近鄰(k-nn)算法的思想是建立一種對函數(shù)形式?jīng)]有假設(shè)的分類方法——方程，把因變量(或回應(yīng))和自變量聯(lián)系起來。我們所做的唯一的假設(shè)是，認(rèn)為它是一個光滑的函數(shù)。我們的訓(xùn)練數(shù)據(jù)中，每個觀測點(diǎn)都含有y值，這個值剛好是該觀測點(diǎn)的類別。對每個輸入向量(表示為樣本矩陣的每一行)，該方法找到k個最近鄰。在回歸中，預(yù)測結(jié)果將是指定向量的近鄰的響應(yīng)的均值。在分類中，類別將由投票決定。

當(dāng)我們計(jì)算觀測點(diǎn)間的距離時，采用歐幾里德距離。點(diǎn)(x1，x2，…，xp)和(u1，u2，...，up)之間的歐式距離為:

對不同的k值，我們用訓(xùn)練數(shù)據(jù)去分類事例，用驗(yàn)證數(shù)據(jù)去計(jì)算分類錯誤率。在這個過程中，我們隨機(jī)地選取含有20個事例的訓(xùn)練集和含有18個事例的測試集。當(dāng)然，在實(shí)際的情況下，會有更大規(guī)模的例子。圖2展示了在測試集中的事例。

測試中我們選擇k=14(或16)。這個選擇最佳的消除了在低k值時的變動性和高k值時的過平滑現(xiàn)象。

5 結(jié)論

我們利用樣本數(shù)據(jù)對決策樹和k-最近鄰(k-nn)算法之間分類的準(zhǔn)確率進(jìn)行了比較，這兩種分類方法得到的結(jié)果類似，其中決策樹的分類結(jié)果略優(yōu)于k-最近鄰算法。

表2 決策樹和k-nn算法比較

參考文獻(xiàn)

[1]徐冰，郭紹忠，黃永忠.基于樸素貝葉斯分類算法的活躍網(wǎng)絡(luò)結(jié)構(gòu)挖掘[J].計(jì)算機(jī)應(yīng)用.2007(6).

[2]Guha S，Rastugi Shim K.CURE:An efficient clustering algorithm for large databases.In Proc.1998 ACM -SIGMOD Int.Conf Management of Data(SIGMOD’98)，Seattle，WA，June 1998:73-84.

[3]Pemg C，Wang H，Zhang S，parker D.Landmarks:A new model for similarity-based pattern querying in time series databases.IEEE Conf. Data Engineering，2000:33-44.

[4]Quinlan J R.C4.5:Programs for Machine Learning.San Mateo，CA:Morgan Kaufman n，1993，Chapter 3.