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

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

1. 青島科技大學(xué)信息科學(xué)技術(shù)學(xué)院， 山東 青島 266061 2. 青島藍(lán)智現(xiàn)代服務(wù)業(yè)數(shù)字工程技術(shù)研究中心， 山東 青島 266071 3. 云南中煙工業(yè)有限責(zé)任公司技術(shù)中心， 云南 昆明 650024

引 言

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

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

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

1 算法與原理

1.1 經(jīng)典局部保持投影算法

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

LPP算法的基本步驟如下：

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

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

(1)

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

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

(2)

為了得到最佳變換矩陣U， 變換目標(biāo)函數(shù)并將其最小化。

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

XLXTu=λXDXTu

(3)

1.2 rank-order距離

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

Step1: 計算每個樣本點xi和其他樣本點的歐氏距離， 并根據(jù)距離的遠(yuǎn)近排序得到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)的值越小， 空間中的樣本點的局部鄰域信息越準(zhǔn)確。

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

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

(5)

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

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

(6)

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

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

KRLPP算法步驟如下：

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

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

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

(7)

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

KLKu=λKDKu

(8)

核矩陣K為半正定矩陣。

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

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

(9)

2 實驗部分

2.1 樣品制備

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

2.2 光譜采集和預(yù)處理

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

為消除高頻噪聲和基線漂移等對光譜造成的影響， 選取二階導(dǎo)數(shù)加Savitzky Golay平滑對光譜進(jìn)行預(yù)處理。

2.3 評價方法

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

表1 總體質(zhì)量評價標(biāo)準(zhǔn)

3 結(jié)果與討論

3.1 參數(shù)的選擇

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

R=1-ρ(DX,DY)

(10)

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

圖2 不同參數(shù)取值殘差圖

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

3.2 投影結(jié)果對比分析

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

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

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

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

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

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

3.3 相似性度量結(jié)果對比分析

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

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

3.3.1 單料煙替換前后評價結(jié)果對比

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

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

3.3.2 葉組配方替換前后評價結(jié)果對比

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

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

表3 替換煙葉與目標(biāo)煙葉評價結(jié)果對比

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

表4 替換配方與原配方評價結(jié)果對比

4 結(jié) 論

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