數據降維及聚類算法在煙葉相似性分析中的應用

翟擎辰，周園春，宋秋成，王建偉，孟珍＊，張艷玲＊

1.中國科學院計算機網絡信息中心，北京 100190

2.中國煙草總公司鄭州煙草研究院，河南 鄭州 450001

3.中國科學院大學，北京 100049

引 言

數據與計算技術飛速發展，不僅在科學研究中起到輔助與支撐的作用，而且可以依靠其自身的邏輯方法，驅動甚至引領科學研究活動[1]。煙草行業內的工業需求的快速擴張，對傳統的煙葉質量的認知模式也帶來了很大的挑戰。僅依靠經驗主觀判斷的方法如人工抽吸法與化學分析法，來完成對煙葉質量的判別與評價已經無法滿足產品質量穩定性的需求。機器學習時代的來臨實現了很多技術上的應用[2]。通過對以往歷史數據的挖掘模擬，建立智能替代模型和交互分析應用，采用客觀數據作為輔助來配方評價和煙葉替代，對提高卷煙質量穩定性有重要意義。因此機器學習方法成為挖掘煙葉原料內在特征、發現煙葉產地外在關聯、尋找煙葉分類特點的一種重要的科學手段。這也是目前輔助技術人員快速尋找缺失原料替代產地的一種重要方法[3]。

標準化的數據集是人工智能算法開展大規模訓練和提升準確率的重要要素[4]。煙葉質量數據中包括物理屬性、化學屬性、感官質量、葉身外觀等多種指標[5]，有的數據源可以到達幾十維甚至上百維。這種情況下，屬性指標的選擇和降維以及距離度量的構建就成了影響相似性度量和煙葉分類結果的關鍵[6]。僅僅依靠人工經驗篩選輸入指標，結果會喪失客觀性且不能體現數據之間的關聯性；而在使用數據降維算法時，所降維的數據在高維空間中的分布狀態將對降維算法的準確性產生影響。數據分布狀態未知時，采用主成分分析法進行降維可能出現原始樣本間距離結構、拓撲結構發生改變等諸多問題，導致相似性度量結果不準確[7]。

面對上述問題，文章在數據降維時采用方差權重法、主成分分析法及局部線性嵌入法三種方法進行特征篩選與降維。方差權重法可以對相似性度量及聚類指導性較高的屬性進行篩選。主成分分析法與局部線性嵌入法進行降維針對數據在高維空間的分布結構，以線性與非線性兩種方式進行降維。通過比較三種方法的篩選和降維后的數據的聚類效果，文章對特征篩選與降維方法進行分析，將優勝的篩選或降維后的數據通過加權歐氏距離進行相似性度量，以克服工業數據中不同屬性的指導性不同的問題，并通過K-means 算法對煙葉進行聚類及分析。

文章以數據挖掘技術為基礎，為完善煙葉質量評價體系、提升煙葉感官品質提供理論基礎，為研究煙葉質量智能評吸算法逐步替代人工抽吸評價提供算法基礎，在煙草工業應用中有較高的參考價值。

1 煙葉感官質量數據

文章數據源采用中國煙草總公司鄭州煙草研究院的2004年至2017年湖南、云南、湖北、安徽、福建等22 個省208 個縣區5 314 個烤煙煙葉樣品數據，其品質屬性指標包括：物理化學屬性如總植物堿、還原糖、總糖、總氮、鉀、揮發酸、淀粉等28 項，感官指標包括香氣質、香氣量、雜氣、刺激、勁頭、濃度、余味等7 項指標，以及葉身外觀的長度、厚度、顏色、重量等7 項指標。

2 面向煙葉產地的數據挖掘算法

2.1 數據預處理

文章對源數據進行歸一化預處理：

其中xmax為樣本數據的最大值，xmin為樣本數據的最小值，x*為原數據在[0,1]之間的線性映射。

2.2 特征篩選及降維

原始數據在高維空間中的結構特征尚未明確，采用單一的降維方法不利于特征的選擇。文章采用方差權重法、主成分分析法、局部線性嵌入法三種核心思想不同的算法對煙葉原始數據進行降維。使線性與非線性結構分布的數據在實驗中都盡可能保持在高維空間下的原有拓撲結構映射[8]，并且方差權重法可以對煙葉質量具有指導性強的屬性進行篩選。文章通過降維后數據的Kmeans 聚類效果對三種特征選擇與降維方法在煙葉數據集上的適用性進行比較。

本文的方法有效避免了數據在高維空間中分布未知的情況下造成的“距離度量失效”的問題，并且保證了輸入指標選擇的客觀性。

2.2.1 方差權重法

方差權重法是通過特征本身的方差來篩選特征的算法。當一個特征本身的方差很小，表明樣本在此特征上基本沒有差異。這種情況下該特征對于樣本區分作用較小。當一個特征分布發散，則代表特征的方差大，能夠根據取值的差異化度量目標信息[9]。故文章通過對于每個特征進行方差計算，設定閾值或者待選擇閾值的個數選擇特征，優先選取與目標高度相關性的指標。

在煙葉的特征對其聚類與相似性度量未知的情況下，文章通過方差權重法對特征進行篩選會有更強的可解釋性。

2.2.2 主成分分析法

主成分分析法（PCA）將輸入數據構成協方差矩陣，并以特征分解的方式對數據進行優化，得到數據的特征向量與特征值。其中特征向量為數據的主成分，特征值為這些數據的權重值[10]。

2.2.3 局部線性嵌入法

局部線性嵌入算法（LLE）基于數據在高維空間滿足流形分布為假設，將其映射至低維空間時也將保持其流形結構不變化[11]。其步驟主要分為三步：（1）得到樣本的k鄰近點；（2）通過樣本點的鄰近點計算出該樣本點的局部重建權值矩陣；（3）由樣本點的局部重建權值矩陣與其相應的鄰近點可計算出輸出值[12]。

上述三種方法得到的輸入值分別是特征選擇后的四種屬性、PCA 降維后的屬性因子及LLE 降維后的屬性因子。將這三種方法得到的因子與屬性分別作為輸入對樣本進行K-means 聚類，通過比較聚類輪廓系數，對三種方法在文章數據集上的適用性進行判斷，從而確定分類輸入指標或屬性。

2.3 產地相似性構建

文章煙葉產地以縣區為基本單位對煙葉質量的相似性進行分析。基于加權的歐式距離公式對產地間的相似性進行度量。

定義樣本矩陣X：

其中xik表示第i個樣本的第k個指標數據，原料樣本質量數據可包括理化屬性、感官質量及外觀指標等。

定義Dij為兩個樣本間的相似度：

其中n為所輸入特征的維度，w為權重。

定義距離矩陣M，其中m為縣區總數量，該矩陣中每一個D值由上文中距離公式所求得：

該矩陣即含括了所有縣區之間的距離，且該矩陣每一行最小的距離即為該行所對應的縣區與其最相近的產地。當樣本集中某個樣本xi需要用另一個樣本作為替代時，可以從距離矩陣M中尋找與樣本xi最短距離的點即最鄰近樣本點集合B。

2.4 煙葉產地聚類及指標

文章采用K-Means 聚類對煙葉質量進行聚類并對聚類結果進行分析。

對于聚類簇數即k值的選取，將通過輪廓系數作為評價指標。輪廓系數表達式如下：

其中b(i)與a(i)分別是簇間與簇內樣本點間距離。當輪廓系數S越接近1 時，則聚類輪廓的表達越優異。

3 面向應用的煙葉數據挖掘

3.1 煙葉特征篩選及降維

3.1.1 方差權重特征選擇

煙葉作為一種農產品，其質量特征可以看作內在理化屬性的外在表現。故本文采用理化屬性作為衡量煙葉分類與相似性的輸入指標。輸入指標通過方差權重法進行篩選得到本次實驗中相近煙葉查找的關鍵指標為：總植物堿、還原糖、含梗率、鉀。其歸一化后權重系數取值分別近似取值 1.0、0.5、1.0、0.8。

3.1.2 PCA 及LLE 降維

使用主成分分析法將總植物堿、還原糖、總糖、總氮、鉀、淀粉、含梗率、單葉重、葉面密度多個屬性降至四維。其降維篩選過程如下表。

表1 PCA 篩選過程Table 1 PCA screening process

由上表可以發現，主成分分析法分解所得到的前6 個特征根所代表的主成分累計方差貢獻率達到79.989 %，可以涵蓋數據源中大部分的信息。若要保留更多信息，則會保留9 維以上的維度，喪失了降維的初衷，故文章采用PCA 將數據降至6 維。

由于LLE 降維的維數選取基于高維空間的本征維數，維數過高會導致數據中含有過多噪聲，維數過低會導致數據集在低維空間映射會彼此交疊。文章基于已有的特征篩選結果對維度數做出判斷，通過LLE 算法將原數據集降至與特征篩選相同的維度數目（4 維）。

3.1.3 特征篩選及降維方法比較

為對比降維的效果，文章對未降維的數據進行K-means 聚類的輪廓系數如圖1所示。

圖1 輪廓系數（未降維）Fig.1 Silhouette coeff cient(unreduced)

圖1表明數據未降維時聚類在簇數為2 時輪廓系數最佳，但數值仍未超過0.5，故文章存在對數據進行特征選擇和降維的必要。

文章將方差權重數據集（4 維）、PCA 變換數據集（6 維）及LLE 變換數據集（4 維）在K-means聚類后計算其輪廓系數。結果如圖2所示。

由圖2可知，PCA 及LLE 兩種方法所得到的數據在簇數目分別為3 和4 時有最高的輪廓系數值0.544 和0.548。方差權重法篩選所得的數據在簇數目為4 時有最高的輪廓系數值0.632。

圖2 輪廓系數（降維后）Fig.2 Silhouette coeff cient (reduced)

雖然方差權重計算性上相對簡單，但PCA 與LLE 也存在一定的不足，可能是導致降維效果較差的原因之一。PCA 可能會將特征向量集合作為整體進行處理，以尋找均方誤差最小意義下的最優線性映射投影，但這種情況下忽視所投影方向可能剛好包含重要可分性信息。而LLE 降維對數據分布要求較高，對非流行分布的數據可能效果相對較差，可能對文章所用數據集也不夠契合，并且文章所使用的數據集維度及樣本量相對較小。這種情況下，采用特征的方差對重要特征進行篩選，反而存在所得到的特征更有代表性且特征間的分離度會更好的可能性。

綜上多種原因，方差權重法在此煙葉數據集上降維的效果更為優異，且篩選所得的總植物堿、還原糖、含梗率、鉀四個指標對于煙葉聚類有一定的指導作用。

而對比PCA 及LLE 兩種降維方法所得到的結果可以發現，LLE 降維所得到的結果相較于PCA 降維所得到的結果隨著簇數目增加，普遍有更好的表現。一定程度上可以反應，對于煙葉數據集，非線性降維相較于線性降維可能更能保持煙葉數據在高維空間的原始拓撲結構。局部線性嵌入法對煙葉領域數據適應性更強。

3.2 煙葉產地聚類分析

圖2表明，以特征選擇所篩選的四個屬性作為輸入的情況下，簇數目為4 聚類效果最好。

在簇數目為4 時K-means 聚類結果如表2所示。類別1 含123 個縣區，煙葉質量主要特征是還原糖、含梗率、鉀均相對較高，代表性產區有安龍縣、賓川縣等；類別3 含51 個縣區，煙葉質量主要特征是含梗率、總植物堿和鉀含量均明顯較高，代表性產區有保康縣、昌寧縣、楚雄市等；類別4 煙葉質量主要特征為含梗率和鉀含量相對較低，代表性產區有寶豐、郟縣等；類別2 煙葉總植物堿、鉀含量和含梗率均明顯較低，還原糖含量明顯較高，代表性產區有賓縣、大安市、富錦等。

表2 四類煙葉的代表指標的平均值Table 2 Average value of representative indicators of four types of tobacco leaves

3.3 煙葉相似產地可視化

選取總植物堿、還原糖、含梗率、鉀作為加權歐氏距離的輸入指標，得到最鄰近距離矩陣并將其以網絡圖的形式進行可視化結果如圖3。

圖3 縣區相似性關聯圖Fig.3 County similarity association graph

文章以濃香型典型產區襄城縣為例對相似性度量結果的準確性進行驗證。文章將與襄城縣最相似的五個煙葉產地（譙城區、郟縣、徽縣、臨朐縣、泌陽縣）分別從香氣質、香氣量、濃度、總植物堿、還原糖、鉀六個維度進行比較。各產地屬性的雷達圖見圖4所示。通過比較六個產地的雷達圖發現，文章所得結果的產地間屬性輪廓較為相似。

圖4 襄城縣與最相近的五個縣區雷達圖Fig.4 Radar map of Xiangcheng County and the f ve closest counties

為從煙草業內角度對結果進行驗證，文章采用指紋圖譜技術取得的研究成果與本文進行比對（唐徐紅等應用煙葉指紋圖譜聚類對云南省的十五個不同的煙葉產區進行的研究[13]）。

文章與唐徐紅等研究結果中所共同涉及的產地為麒麟區、宣威縣、羅平縣。唐徐紅等的研究結果表明，基于煙葉指紋圖譜聚類時，宣威市與羅平縣處于同一簇；基于產區特點分類時，羅平縣與麒麟區處在同一產區類別；結合上述兩點，宣威市、羅平縣、麒麟區在指紋圖譜技術下表現為質量相近的煙葉產地。與本文表3中的結果趨于一致。

表3 最鄰近產地Table 3 Nearest origin

故實驗結果表明，文章的相似性度量結果與行業內專家對特定產區相似性分析的判定相互驗證。文章相似性度量的結論及算法對煙草企業進行產地替代、配方維護、煙葉種植區規劃有一定的指導作用。

4 結論與展望

針對實驗結果及分析，文章從三個方面進行總結。

對降維算法研究而言。在煙葉數據集上，局部線性嵌入法降維后的結果相較于主成分分析法更能體現煙葉數據集在高維空間中的非線性特征，使其在低維空間映射后能更大程度地保持其分布的拓撲結構，故局部線性嵌入法更為適合于應用在煙葉數據集上。而文章采用方差權重法所篩選出的四個特征相較于兩種降維算法也更為優異。基于實驗分析可以發現總植物堿、還原糖、鉀、含梗率四個指標對于煙葉聚類與相似度分析有一定指導作用。

對煙葉聚類而言。文章基于K-means 聚類算法，使用總植物堿、還原糖、鉀、含梗率作為輸入特征進行聚類。通過聚類結果分析發現，煙葉產地分為四類時是最理想的結果并得到四類煙葉產地所產煙葉的理化指標特點及代表性縣區。

對樣本集相似性度量而言。本文以總植物堿、還原糖、鉀、含梗率作為輸入指標，通過加權歐氏距離進行相似性度量，所得結果與業內專家通過指紋圖譜技術所得結果間相互驗證。表明文章所構建的煙葉相似度計算算法對卷煙配方替代工作有重要意義。

總體而言，本文構建針對煙葉分類與相似度計算的組合算法庫能夠通過對以往歷史數據的挖掘模擬，建立智能替代模型來作為輔助煙葉配方評價和煙葉替代的方法，對提高卷煙質量穩定性有重要意義。

當然，數據挖掘技術在煙葉聚類與相似性度量領域的應用尚處于起步階段，對煙葉質量的評價指標還缺乏統一和規范的計算方法，這對于數據挖掘技術在煙草業內的實際應用構成了一定的障礙。保留原始特征信息、過濾無用信息、構建距離度量都是數據挖掘在煙葉應用領域的難點。目前在未對煙葉按風格及年份進行標簽的情況下所得到的結果精確度依然有待提高，通過基于區分典型區域或典型風格的條件下，將樣本數據集帶上年份標簽進行研究可能使精確度有一定程度上的提高，這也為后續卷煙配方替代的研究工作提供了一個新的研究方向及目標。

利益沖突聲明

所有作者聲明不存在利益沖突關系。