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

郁智軒 王林渠 韓金諾 楊 洋

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

1 概述

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

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

2 模型的建立與求解

2.1 譜系聚類分析概述

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

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

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

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

2.2 16 種加工原料參數

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

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

2.3 分析與求解

圖1 分析流程圖

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

具體步驟如下：

（1）根據所得出的親緣值數據，構造一個Graph，Graph 的中每個節點對應一個數據點，將各點連接起來，我們使用邊的權重來代表數據之間的相似度。然后將這個Graph 用鄰接矩陣的形式進行表示，記為W。

譜聚類中的矩陣：

鄰接矩陣：

Min cut 和ratiocut 中的Laplacian 矩陣：

Normalizedcut 中的L：

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

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

L=M-W

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

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

圖3 16 個品種親緣值的無向加權

2.4 計算結果（見表2）。

3 結論

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

表2

本方法依據鄰接矩陣和無向加權圖準確的得到了親緣值，并對數據進行描述統計性分析和譜聚類分析，有著嚴密的數學邏輯思想，具有較高的可信度。