核映射和Rank-Order距離的局部保持投影相似性度量方法

秦玉華， 張 萌*， 楊 寧， 單秋甫

1. 青島科技大學信息科學技術學院， 山東 青島 266061 2. 青島藍智現代服務業數字工程技術研究中心， 山東 青島 266071 3. 云南中煙工業有限責任公司技術中心， 云南 昆明 650024

引 言

近年來， 近紅外光譜分析技術(NIR)因其簡便、 環保、 速度快、 不損壞樣品等優點， 已經在農業、 石化、 食品、 煙草等眾多領域占有重要地位[1]。 產品的近紅外光譜中含有超90%的結構信息， 能夠較全面的表征產品的質量信息。 而相似性度量作為一種衡量數據間差異的重要方法， 廣泛應用于機器學習和數據挖掘領域[2]。 對近紅外光譜進行相似性度量， 可實現產品之間質量相似性的評價； 該方法也可用于食品、 卷煙等各類配方產品相近原料的查找和替換。 但近紅外光譜數據具有高維、 非線性、 高噪聲、 高冗余的特點， 同時存在數據分布稀疏和空空間現象[3]， 導致相似性度量在低維空間常用的距離度量方式失效， 因此需要研究一種高效的適用于高維數據的相似性度量方法， 解決高維空間存在的“維度災難”問題。

賀玲等[4]對高維空間進行基于網格劃分的子空間相似性度量， 但只能避免噪聲對高維數據的影響。 謝明霞等[5]提出了一種高維數據的相似性度量函數， 可以有效緩解高維的影響， 但此函數的提出基于聚類算法， 并不具有普遍性。 曹鵬云等[6]提出一種基于核方法和測地線距離的高維空間相似性度量方法， 解決了傳統度量中低維保距映射的問題， 但不適用于稀疏的光譜樣本。 徐寶鼎等[7]改進局部線性嵌入算法中的距離度量公式并在子空間進行降維， 但此方法需要通過特征篩選實現對子空間的劃分， 算法復雜且計算量較大。 由此可見， 由于直接對高維數據進行相似性度量較為困難， 因此往往先采用降維的方法進行特征提取， 消除高維數據中的噪聲和冗余， 在低維空間中進行數據的度量。 但是目前存在的相似性度量方法都選擇以測地線距離作為距離的度量方式， 并沒有真正映射到準確的鄰域信息， 因此得到的度量結果會出現不同程度的偏差。

針對上述問題， 提出一種基于核變換和rank-order距離局部保持投影相似性度量方法， 首先， 將光譜數據映射到更高維的數據空間， 采用改進的局部保持投影算法對數據進行降維， 引入rank-order距離替代歐氏距離， 可以更有效地保證映射到低維空間局部鄰域信息的準確性， 同時使得在降維之后的低維空間得到的相似光譜更加準確。 將該方法應用于卷煙配方替換煙葉的尋找并取得了較好的效果， 實現了卷煙配方的輔助維護。

1 算法與原理

1.1 經典局部保持投影算法

局部保持投影(LPP)算法作為一種經典的無監督的特征提取算法， 由He[8]等首次提出。 LPP算法綜合了PCA算法和LE算法的優點， 有較強的泛化能力， 在模式識別、 數據挖掘等領域取得了顯著成效[9]。 假設在高維歐氏空間RD中有n個D維數據集X={x1,x2,x3, …,xn},xi∈RD， (i=1, 2, 3, …，n)， LPP算法的核心思想是選取一個最佳的變換矩陣U將高維數據集X映射到低維空間Rd(d?D)[10]， 在低維空間重構局部鄰域信息， 獲得低維特征矩陣Y={y1,y2,y3, …,yn}， 使得降維之后的特征空間仍保持高維空間局部鄰域信息不變。

LPP算法的基本步驟如下：

Step1: 通過歐氏距離的計算為樣本點xi(i=1, 2, 3…,n)選出k個距離最近的點作為近鄰點并構建鄰接圖G=(V,E)。

Step2： 利用熱核函數Sij[11]度量樣本點xi和鄰近點xj的相似性， 即兩點之間邊的權重值。 計算公式為

(1)

式(1)中，t為無關參數，Nk(xj)可表示xi所有的鄰近點。

Step3: 利用yi=UTxi獲得由高維數據X映射到低維空間的矩陣Y。 定義目標函數O(u)為

(2)

為了得到最佳變換矩陣U， 變換目標函數并將其最小化。

然后根據矩陣論通過式(3)計算廣義特征方程的特征值。

XLXTu=λXDXTu

(3)

1.2 rank-order距離

rank-order距離作為一種新的距離度量方式， 由Zhu[12]在2011年提出。 rank-order距離是利用數據點間共同的鄰近點信息來計算樣本間的距離， 在高維空間中兩點之間的直線距離不一定準確， 但是加上鄰近點的共享信息會極大的提高距離度量的準確性[13]。 rank-order距離計算步驟如下：

Step1: 計算每個樣本點xi和其他樣本點的歐氏距離， 并根據距離的遠近排序得到xi鄰近點的順序表。

Step2: 計算每兩個樣本點xi和xj間的不對稱rank-order距離d(xi,xj)。 分別定義fxi(m)為樣本點xi在順序表中第m個鄰近點，Rxi(xj)表示xj是xi在鄰近順序表中第幾個鄰近點， 即樣本點xj在xi鄰近順序表中的序號。 則Rxj(fxi(m))表示的是樣本點fxi(m)在xj鄰近點順序表中的序號。 因此樣本點xj和xi的非對稱rank-order距離公式如式(4)

(4)

由式(4)可知，d(xi,xj)表示的是樣本點xi的幾個最近鄰點在xj的鄰近點順序表中所在位置序號的總和， 并且d(xi,xj)的值越小， 空間中的樣本點的局部鄰域信息越準確。

如圖1所示， 樣本點xi和xj之間的非對稱rank-order距離為

=6+2+0+3+5=16

(5)

圖1 樣本點xi和xj共享鄰近點信息

Step3: 將Step2中計算得出的不對稱rank-order距離進行歸一化， 可得對稱的rank-order距離為

(6)

1.3 基于核映射rank-order距離的局部保持投影算法(KRLPP)

為了能準確地找出樣本的鄰近點， 提出了基于核映射和rank-order距離的局部投影(KRLPP)算法， 先通過核變換將數據集映射到更高維的空間， 同時引入rank-order距離替換歐氏距離， 通過共享局部鄰近點的信息來重新度量樣本點的相似關系， 以此提高低維空間中相似性度量結果的精度。

KRLPP算法步驟如下：

Step2： 根據1.2中算法的描述計算得出矩陣中任意兩點間的rank-order距離dR〈Φ(xi),Φ(xj)〉， 并以dR〈Φ(xi),Φ(xj)〉尋找樣本點的鄰近點。

Step3： 在H空間中， 最小化目標函數， 則式(3)可寫為

Φ(X)LΦ(X)Tu=λΦ(X)DΦ(X)Tu

(7)

用核變換后的核矩陣K=(Kij)表示式(8)為

KLKu=λKDKu

(8)

核矩陣K為半正定矩陣。

求式(8)的前d個廣義特征值及特征向量得到最佳變換矩陣， 并求出低維映射矩陣Y。

Step4： 對于降維得到低維特征矩陣Y， 通過歐氏距離進行相似樣本點的尋找， 樣本個數自行設定。 相似點的距離度量公式作為相似度的度量標準定義如式(9)

(9)

2 實驗部分

2.1 樣品制備

選取2017年—2019年300個用于調配卷煙配方的單料煙和1個需要維護的某品牌卷煙葉組配方(葉組配方是專家根據各種煙葉的主要化學成分、 物理特征及感官等品質因素， 將不同的單料煙按照一定原則和比例配制而成具有特定吸味風格和品質要求的卷煙產品)。 將煙葉樣品放置于60 ℃的烘箱中干燥4 h， 用旋風磨磨碎過40目篩， 密封平衡后進行光譜數據的采集。

2.2 光譜采集和預處理

選用尼高力公司的Antaris Ⅱ 近紅外光譜儀， 掃描范圍為4 000～10 000 cm-1， 分辨率為8 cm-1。 每個實驗樣品稱重15 g， 放于在樣品杯中用壓樣器壓實進行光譜采集， 室溫保持在18～25 ℃， 為減少不確定性， 每個樣品掃描3次， 取平均值作為該樣品的最終光譜。

為消除高頻噪聲和基線漂移等對光譜造成的影響， 選取二階導數加Savitzky Golay平滑對光譜進行預處理。

2.3 評價方法

煙葉中總煙堿、 總糖、 還原糖、 總氮等化學成分[15]及感官質量對煙葉的品質有重要影響， 本研究主要以化學成分及感官評吸打分兩種方式對替換前后的煙葉和葉組配方進行了對比。 其中化學成分通過近紅外方法檢測三次取平均值得出， 感官評吸由10位配方專家組成感官質量評價小組， 依據YC/T 497—2014《卷煙中式卷煙感官評價方法》， 對煙葉的香氣、 煙氣、 口感特性(各占比40%， 40%和20%)分別打分， 總分為百分制。 同時為了更直觀的展示替換前后煙葉及葉組配方的總體質量差異， 以0.5為梯度進行質量特征差異評價打分， 評價標準如表1所示。

表1 總體質量評價標準

3 結果與討論

3.1 參數的選擇

近鄰點個數k和降維后的維數d為LPP算法中兩個重要的參數。k取值過大會使部分重要的鄰域結構信息被忽略， 取值過小得到的鄰域信息會比較局限；d選取過大則可能會包含較多的噪聲信息， 在以往的算法中， 往往都是根據經驗選擇， 因此不同參數的選取對降維結果的影響頗大。 本工作根據降維前后數據集信息殘差的變化來確定參數。 殘差的計算公式如式(10)

R=1-ρ(DX,DY)

(10)

式(10)中，DX和DY分別為降維前后數據的距離矩陣，ρ為兩者的線性相關系數，ρ越大， 代表高維數據降維之后得到的DY的信息量越大。 圖2為選取不同k值和d值的殘差圖。

圖2 不同參數取值殘差圖

可以看出， 當k值為6，d為3時， 殘差最小， 表示此時映射到低維空間的特征矩陣獲得最大的信息量。

3.2 投影結果對比分析

針對煙葉光譜數據的內在規律提取和相似性度量， 有學者提出了改進鄰域的局部保持投影方法INLPP， 將類別信息參數加入到距離計算中， 對于不同香型風格的煙葉有較好的區分效果。 圖3為分別采用PCA， LPP， INLPP和KRLPP對煙葉光譜數據進行降維的投影效果對比。

圖3 PCA， LPP， INLPP和KRLPP算法降維投影圖

不同部位的煙葉在化學成分、 質量方面存在較多的差異， 煙葉能提供的香味與部位間存在直接的相關性， 因此配方設計和維護中配方人員要充分考慮煙葉部位的差異。 由圖3投影圖可以看出， PCA算法無法有效區分上、 中、 下不同部位的煙葉， LPP算法對于區分不同部位煙葉邊界仍明顯存在交叉現象， INLPP算法對于部位的區分效果明顯優于PCA和LPP算法， 但是中部和下部還是有少部分重疊的區域， 而KRLPP算法對于煙葉上部、 中部、 下部三部分區分邊界較為明顯， 降維效果優于INLPP方法。

為進一步驗證投影結果的有效性， 表2為分別采用PCA， LPP， INLPP和KRLPP四種算法進行特征提取， 使用SVM分類器建立不同部位煙葉的分類模型正確識別率的對比。

由表2可以得出， 由KRLPP算法進行降維操作后的煙葉光譜不同部位的識別率為91.2%， 明顯高于其他算法， 說明該方法對于煙葉部位分類信息特征提取更為有效。

表2 不同降維算法煙葉部位分類結果對比

3.3 相似性度量結果對比分析

從卷煙葉組配方中選取5個代表性煙葉作為目標替換煙葉， 然后分別采用PCA， LPP和KRLPP方法從300個用于配方維護的煙葉樣品中為每個目標煙葉尋找相似煙葉， 用于葉組配方中原料的替換。 其中LPP和KRLPP用于降維的參數選擇保持一致， PCA選擇前6個主成分。

為了驗證實驗結果的準確性， 本文采用化學成分和感官評吸打分兩種評價方式， 分別從替換前后的單料煙和葉組配方兩個角度進行了評價， 從而保證了配方維護結果的可靠性。

3.3.1 單料煙替換前后評價結果對比

表3列出了1個目標煙葉分別采用PCA， LPP和KRLPP三種方法， 根據相似度計算標準， 從單料煙度量角度選出的3個替換煙葉與目標煙葉的化學成分和感官評吸結果對比。 其他4個目標煙葉的替換推薦結果與該表所列的結果類似， 不再詳細列出。

由表3可得， 三種方法所選出的替換煙葉與目標煙葉從化學成分和感官特征兩方面皆有較小的偏差。 其中由PCA算法選出的替換煙葉較目標煙葉偏差相對略大， LPP次之， KRLPP偏差最小。 特別是KRLPP算法選出的3個替換煙葉， 在總糖、 還原糖、 總煙堿、 總氮等化學成分指標以及香氣、 煙氣、 口感等感官特征上與目標煙葉非常接近。 說明該方法在卷煙配方維護中尋找相似煙葉的效果最好。

3.3.2 葉組配方替換前后評價結果對比

煙葉有效替換是配方維護的重要環節， 但由于煙葉的種植受氣候、 土壤、 栽培甚至是年份的影響， 為保證產品質量的穩定性， 通常要根據原料庫存等實際需要對配方進行調整， 尋找相似度高的替換煙葉決定了最終配方維護的穩定性和一致性， 因此從葉組配方整體角度對比替換前后的配方產品評價更能體現配方的維護效果。

表4為采用PCA， LPP和KRLPP方法選出的3個替換煙葉(表3結果)， 從葉組配方整體角度使用上述替換煙葉對目標煙葉進行替換， 從而調配生成3個不同的替換配方與原配方的化學成分和感官評吸結果對比。

表3 替換煙葉與目標煙葉評價結果對比

由表4可得， KRLPP算法所得的替換配方在化學成分和感官指標上較PCA和LPP最接近于原配方， 尤其是替換配方1， 各種指標幾乎相同， 配方質量差異最小， 說明該方法得到的度量結果準確度最高。 主要原因是該方法經過核變換和rank-order距離改進， 使得高維數據在降維之后更能有效的保持局部鄰域信息， 因此相似性度量結果的穩定性和準確性更好， 該方法能更有效地指導煙葉的配方設計與維護工作。

表4 替換配方與原配方評價結果對比

4 結 論

基于核變換和rank-order距離的相似性度量方法KRLPP有效的提高了相似性度量的準確性， 將光譜數據經過核變換之后， 更能保持數據的空間結構， 改進距離度量公式， 則保證映射后的局部鄰域信息更準確， 使得高維空間中存在“距離失效”導致的維度災難問題得到有效的解決。 通過對替換前后煙葉和葉組配方兩個角度進行化學成分和感官質量評吸打分可得， 本文提出的相似性度量方法更有效的尋找替換煙葉和葉組配方的維護， 該方法可有效推進配方產品輔助設計與維護工作， 保持產品質量的穩定性。