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

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

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

1 研究的背景

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

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

2 特征向量法建模

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

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

用層次分析法來(lái)解決這個(gè)問(wèn)題的具體步驟如下:

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

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

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

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

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

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

就糖果形狀檢測(cè)這一目標(biāo)，因素Bi與因素Bj比較，分別得到5個(gè)相對(duì)分值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稱為判斷矩陣。由這個(gè)矩陣的元素可以確定因素B i對(duì)于目標(biāo)的綜合分值， 這個(gè)值記為yi( i= 1， ...， 5)。

其次建立數(shù)學(xué)模型。下面來(lái)說(shuō)明由相對(duì)分值aij( j= 1， ...， 5)如何得到分值yi(i= 1， ...，5)的。從判斷矩陣的建立過(guò)程可以看出，對(duì)于目標(biāo)，因素Bi的重要性由Bj( j = 1， ...， 5)綜合體現(xiàn)。由于Bj對(duì)于目標(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對(duì)于目標(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個(gè)因素的分值向量。

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

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

A ω = λω (4)

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

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

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

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

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

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

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

4 k-最近鄰算法

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

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

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

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

5 結(jié)論

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

表2 決策樹(shù)和k-nn算法比較

參考文獻(xiàn)

[1]徐冰，郭紹忠，黃永忠.基于樸素貝葉斯分類(lèi)算法的活躍網(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.