基于譜系聚類分析的飼料混合加工的研究

郁智軒 王林渠 韓金諾 楊 洋

（ 成都信息工程大學(xué)光電工程學(xué)院，四川 成都610000）

1 概述

飼料加工廠需要加工一批動物能量飼料，加工廠從不同的產(chǎn)區(qū)收購了原料，原料在收購的過程中由于運輸、保鮮以及產(chǎn)品本身屬性等原因，存在著效能率的問題（如1 噸玉米可加工成0.7 噸左右的玉米面）。這個數(shù)據(jù)在原料進(jìn)廠之后可以通過隨機抽樣進(jìn)行檢測得到。工廠技術(shù)人員對每種加工原料進(jìn)行了基因檢測，得到了10 個關(guān)鍵位點的基因序列，并規(guī)定，兩個加工原料如果有N 個相同位點的基因序列標(biāo)記相同，就認(rèn)為這兩個加工原料的親緣值為N（如果N 大于0，則說明這兩種加工原料之間具有親緣關(guān)系），一個加工包中所有原料兩兩之間親緣值的平均值稱為親緣度。例如品種代碼1、2、5 的加工原料混合成為一個加工包，假設(shè)品種代碼1和品種代碼2 的親緣值為5，品種代碼1和品種代碼5 的親緣值為3，品種代碼2和品種代碼5 的親緣值為5，那么它們的親緣度就是(5+3+5)/3。如果一個加工包中只含有一種加工原料，則該加工包的親緣度為10。本文僅從親緣度角度考慮混合加工飼料的質(zhì)量，親緣度越高，飼料質(zhì)量就越高。

表1 各加工原料的品種代碼、總重量、效能率和基因序列標(biāo)記

2 模型的建立與求解

2.1 譜系聚類分析概述

譜系聚類分析的基本思路是從一批樣品的多個樣本中, 系統(tǒng)聚類首先定義能度量樣品間的親疏關(guān)系的統(tǒng)計值; 然后求出各樣品間的親疏程度度量值; 再接下來按照親疏程度的大小,把樣品挨個歸類, 關(guān)系密切的聚合到一個小的單元, 關(guān)系疏遠(yuǎn)的聚合到一個大的分類單元, 直至所有的樣品都聚合完成;就這樣，將不同的類型挨個劃分, 最后處理繪出相應(yīng)的譜系圖,以更加直觀地表現(xiàn)出分類樣品的相關(guān)聯(lián)系及差異。

譜聚類算法將各項數(shù)據(jù)中的各個對象看作圖的頂點D，將頂點間相似性度量化為相應(yīng)頂點連接邊的權(quán)值Q，我們就能得到一個基于相似度的無向加權(quán)圖G(D, Q)，我們就把聚類問題轉(zhuǎn)化為圖的劃分問題。而基于圖論的最優(yōu)劃分原則就是使劃分成的子圖內(nèi)部相似度最大，子圖之間的相似度最小。建立在譜圖基礎(chǔ)上的譜聚類算法與傳統(tǒng)的聚類算法相比，它具有能在任意形狀的樣本空間上聚類且收斂于全局最優(yōu)解的優(yōu)點。

其基本思想便是利用所得樣本數(shù)據(jù)的相似矩陣，即拉普拉斯矩陣，進(jìn)行特征分解（ Laplacian Eigenmap 方式降維處理），再將得到的特征向量進(jìn)行K-means 聚類。

我們考慮一種最優(yōu)化圖像分割方法，將其為S 和T 兩部分，等價于如下?lián)p失函數(shù)cut(S, T)，如公式（1）所示，即最小(砍掉的邊的加權(quán)和)。

2.2 16 種加工原料參數(shù)

給定所測16 種原料的品種代碼、總重量、效能率和基因序列標(biāo)記值如表1。

圖2 16 個品種的親緣值鄰接矩陣

2.3 分析與求解

圖1 分析流程圖

要求出16 種加工原料兩兩之間的親緣值，并對其進(jìn)行統(tǒng)計性分析，依據(jù)親緣值N 的計算方法得出一個16*16 方陣，列出相似性矩陣，將基因序列a-z 用數(shù)字1-26 代替，將其帶入鄰接矩陣（見圖2）中，得出16 個加工原料兩兩之間的親緣值。建立一種描述性統(tǒng)計分析和譜聚類分析相結(jié)合的統(tǒng)計性分析模型來分析得到的親緣值數(shù)據(jù)（矩陣與圖）。

具體步驟如下：

（1）根據(jù)所得出的親緣值數(shù)據(jù)，構(gòu)造一個Graph，Graph 的中每個節(jié)點對應(yīng)一個數(shù)據(jù)點，將各點連接起來，我們使用邊的權(quán)重來代表數(shù)據(jù)之間的相似度。然后將這個Graph 用鄰接矩陣的形式進(jìn)行表示，記為W。

譜聚類中的矩陣：

鄰接矩陣：

Min cut 和ratiocut 中的Laplacian 矩陣：

Normalizedcut 中的L：

可見不管是L、L'都與W 聯(lián)系特別大。如果將W 看作一個高維向量空間，同樣能夠反映出item 之間的關(guān)系。若把W 直接kmeans 聚類，得到的結(jié)果也能反映V 的聚類特性，而譜聚類的引入L 和L'是使得Graph 的分割頗具物理意義。

（2）把W 上每一列元素加起來共得到16 個數(shù)，把它們放在對角線上（其余均為零），組成一個16x16 的對角矩陣，記為度矩陣M，并把的結(jié)果記為拉普拉斯矩陣。

L=M-W

（4）將k 個特征向量排列在一起組成一個16xk 的矩陣，將其中每一行看成k 維空間中的一個向量，用K-means 算法進(jìn)行聚類處理。得到的結(jié)果中每一行所屬的類別即是原來Graph中的節(jié)點，亦即是最初的16 個數(shù)據(jù)點分別所屬的類別。用matlab 即可快速得出鄰接矩陣W 的拉普拉斯矩陣，及其特征向量，進(jìn)而規(guī)定想要把16 個原料分成幾類，就將k 設(shè)為多少，便可迅速得到一種分類，即是綜合親緣度較高的組合。

圖論是指對某些客觀的事物進(jìn)行抽象處理，利用圖的形式來描述事物的內(nèi)在聯(lián)系。它是研究一類或幾類事物之間相關(guān)關(guān)系的一種理想的數(shù)學(xué)方法，原理是通過把某一類事物抽象成點，使用兩點之間的連線進(jìn)而表示兩個事物之間存在著相關(guān)關(guān)系，進(jìn)而將整個復(fù)雜的分析轉(zhuǎn)化成一個僅由點線構(gòu)成的二維圖,再應(yīng)用數(shù)學(xué)方法展開研究。該方法適用描述各加工原料的親緣值。兩兩加工原料的親緣值與他們相同的基因序列相關(guān)，根據(jù)基因序列的相同個數(shù)得出親緣值，基于鄰接矩陣建立出圖論模型。如圖3（除去孤點共70 種組合）：

圖3 16 個品種親緣值的無向加權(quán)

2.4 計算結(jié)果（見表2）。

3 結(jié)論

由上述結(jié)果可知，在16 個加工原料中，品種5 的綜合親緣關(guān)系最強，品種14 次之。品種10 的親緣關(guān)系最廣，品種5、11、13、16 次之。為加工出更高質(zhì)量的飼料提供了參考。

表2

本方法依據(jù)鄰接矩陣和無向加權(quán)圖準(zhǔn)確的得到了親緣值，并對數(shù)據(jù)進(jìn)行描述統(tǒng)計性分析和譜聚類分析，有著嚴(yán)密的數(shù)學(xué)邏輯思想，具有較高的可信度。