機器學習在糖果形狀檢測中的應用

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

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

1 研究的背景

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

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

2 特征向量法建模

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

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

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

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

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

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

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

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

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

就糖果形狀檢測這一目標，因素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 = (aij )5×5(其中，aii= 1， aij=1/aji， i， j = 1， 2， 3， 4， 5)，A稱為判斷矩陣。由這個矩陣的元素可以確定因素B i對于目標的綜合分值， 這個值記為yi( i= 1， ...， 5)。

其次建立數(shù)學模型。下面來說明由相對分值aij( j= 1， ...， 5)如何得到分值yi(i= 1， ...，5)的。從判斷矩陣的建立過程可以看出，對于目標，因素Bi的重要性由Bj( j = 1， ...， 5)綜合體現(xiàn)。由于Bj對于目標的權(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對于目標的綜合分值(這樣可以減少由于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)對于目標的重要程度，所以Y也是反映各因素重要程度的向量，亦即相對目標而言，Y也是各因素的一個排序向量。既然向量ω與Y都是各因素對于目標的排序向量，所以二者應該成正比例關(guān)系，即存在正常數(shù)λ，使Y = λω(3)

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

A ω = λω (4)

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

3 學習獲得決策樹

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

●樹的深度達到了指定的最大值。

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

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

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

4 k-最近鄰算法

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

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

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

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

5 結(jié)論

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

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

參考文獻

[1]徐冰，郭紹忠，黃永忠.基于樸素貝葉斯分類算法的活躍網(wǎng)絡結(jié)構(gòu)挖掘[J].計算機應用.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.