基于LDABPSO算法的煙葉復烤配方關聯特征挖掘

杜清清，侯開虎，陳興侯，劉雅琴，馬顯滔，范振宇，孫浩巍

（1.昆明理工大學機電工程學院，云南昆明 650500；2.云南煙葉復烤有限責任公司麒麟復烤廠，云南曲靖 655000；3.云南省煙草質量監督檢測站，云南 昆明 650500）

0 引言

卷煙作為一種特殊的農業副食品，通常要求吸食口感長期保持穩定［1］。復烤企業作為煙草生產鏈的關鍵環節，實現對煙葉的初步加工及模塊化配方打葉，對不同質量的煙葉進行協調搭配，為卷煙企業提供穩定的原材料。但在實際生產中，煙葉質量受氣候、土質等因素的影響，導致復烤配方每年的波動性較大，如何維護復烤配方模塊是目前亟待解決的問題。

近年來，已經有學者針對煙葉復烤配方維護展開研究。雒興剛等［2］基于歷史配方數據，運用關聯規則Apriori算法挖掘配方中隱含的規則，得到單料煙的替換規則，對于卷煙配方維護具有積極意義。王蘿萍等［3］在文獻［2］的基礎上對Apriori 算法進行改進，提出一種基于矩陣的多維關聯規則算法并在煙葉復烤配方中成功實踐。上述文獻通過Apriori 算法可得到配方中隱藏的大量煙葉搭配協同信息進而提煉為規則，能在一定程度上實現配方維護。但采用Apriori 算法進行關聯分析，需要人工設定規則提取閾值，挖掘結果受主觀性影響大，造成海量冗余規則的出現且規則質量較低，如何解決上述問題是現階段研究的方向。

關聯分析屬于離散域問題，而二進制粒子群算法（Binary Particle Swarm Optimization，BPSO）在離散優化方面具有較好的性能［4］，近年來備受研究者關注。宋剛等［5］利用二進制粒子群算法優化LSTM 模型，并將其應用于股票預測研究，該模型提高了預測準確度，且具有普遍適用性；閆坤等［6］針對復雜網絡問題，提出基于二進制粒子群算法的攻擊策略，研究表明該策略具有高效性等優勢；古良云等［7］提出一種改進二進制粒子群算法，并且在6 個高維數據集上進行關聯規則挖掘驗以證算法性能，通過與Apriori 算法作對比，表明該方法具有一定可行性；鐘倩漪等［8］將一種多策略二進制粒子群算法用于關聯規則挖掘，如此可得到更有效的規則。上述文獻表明，二進制粒子群算法在離散域問題及關聯規則挖掘中的有效性，但現有文獻并未將該算法應用于復烤配方維護領域。

綜上，提出一種改進二進制粒子群算法（Latin Hypercube Arcshaped Binary Particle Swarm Optimization，LDABPSO）用于煙葉復烤配方關聯規則挖掘。首先對二進制粒子群算法從種群初始化、可行解的停滯、擾動機制等3 個方面提出改進策略；其次，將LDABPSO 算法在標準測試函數上與BPSO算法［9］、李浩君等［10］提出的ABPSO算法（Arcshaped Binary Particle Swarm Optimization，ABPSO）作對比。最后，以云南省麒麟復烤廠近年配方數據作為數據源，運用LDABPSO 算法進行配方關聯規則挖掘。實驗表明，當Apriori 算法最小支持度和最小置信度分別設置為0.18 和0.5 時，LDABPSO 算法挖掘到的煙葉規則數量相比Apriori算法減少90.23%，極大減少了冗余規則的產生，挖掘到的煙葉搭配規則質量更好，且算法運行時間減少8.4%。

1 改進二進制粒子群算法

基本粒子群算法（Particle Swarm Optimization，PSO）只能解決連續問題，為了解決離散空間問題，Kennedy 等［9］于1997 年在PSO 算法的基礎上提出BPSO 算法。針對BPSO算法容易陷入局部最優且產生大量無用計算的缺陷，本文從全局及局部搜索方面進行算法改進，進而提出LDABPSO算法。

1.1 全局搜索

本文全局改進策略主要從種群初始化方面進行設計，BPSO 算法一般采用隨機初始化策略，但種群的好壞同樣影響算法的收斂速度和精度［11］。鑒于此，本文提出采用拉丁超立方抽樣初始化種群，均勻劃分搜索空間，保持初始種群的多樣性［12］，與隨機初始化不同的是，拉丁超立方抽樣可以保證變量覆蓋整個分布空間。圖1 和圖2 分別為隨機抽樣分布圖和拉丁超立方抽樣圖，在區間［0，1］隨機抽取10 個點，可以看到拉丁超立方抽樣基本可以分布到整個空間。

Fig.1 Comparison of the two sampling methods圖1 兩種抽樣方式比較

1.2 局部搜索

1.2.1 limit 閾值

受文獻［13］啟發，本文引入蜂群算法在迭代過程中可行解的停滯次數limit 閾值。在BPSO 算法迭代過程中，算法后期全局搜索過強、局部搜索不足，容易陷入局部最優［14］。limit 閾值的引入在很大程度上能促使算法跳出局部最優，是對算法迭代過程的一種監控。在算法初始階段，提前設置閾值的極大值limitmax。算法迭代時，觀察每個粒子在閾值內的位置是否發生變化，若沒有發生變化，則說明算法可能陷入了局部最優，此時需要調整陷入局部最優的粒子位置。本文采取的策略是：若某個粒子位置在limitmax 內的位置沒有發生改變，則直接舍棄，生成新的粒子作為補充。文獻［15］提到，閾值大小對算法尋優能力的影響較大，經過多次試驗，本文將limitmax 閾值設置為80。

1.2.2 隨機擾動

其中，是第k次迭代時第i個粒子的速度，w為慣性權重，C1、C2為學習因子，r1、r2來自于均勻分布(0,1)，pi為粒子最佳適應值，g為全局最優適應值，xi是粒子當前位置，x′為粒子隨機位置，類似地，r3來自于均勻分布(0,1)。由于BPSO 算法中粒子位置只能為0、1，因而粒子位置通過映射函數決定，rand（）為[0,1] 區間的隨機數，如式（3）所示。

1.3 算法框架

Fig.2 LDABPSO algorithm flow圖2 LDABPSO 算法流程

2 LDABPSO 算法測試

2.1 測試函數

為了測試LDABPSO 算法的性能，選擇6 種基準函數進行測試，表1 為標準測試函數及參數說明，其中F1、F2、F3為單峰函數，適合測試算法收斂性，F4、F5、F6為多峰函數，用來測試函數跳出局部最優的能力，所有粒子的取值只有0和1。

Table 1 Standard test functions and parameters表1 標準測試函數及參數

2.2 比較算法

為了驗證LDABPSO 算法的性能，選用以下算法進行仿真實驗：①基本BPSO 算法［9］；②文獻［10］提出的ABPSO 算法；③本文提出的LDABPSO 算法。

2.3 關鍵參數確定

（1）學習因子。學習因子C1、C2的大小分別控制粒子向局部最優粒子和全局最優粒子靠近的步長，通常令C1=C2=1.449。

（2）慣性權重。BPSO 算法的慣性權值w 和文獻［9］保持一致，采用固定慣性權重。ABPSO、LDABPSO 算法均采用文獻［17］的線性遞減式慣性權重，相應的最大和最小慣性權重值分別為0.9 和0.4。

（3）其他參數。在本次實驗中，BPSO 算法、ABPSO 算法、LDABPSO 算法種群數量均設置為15，迭代次數設置為500 次。參考文獻［10］，BPSO、ABPSO 算法的最大速度值設為9，LDABPSO 算法的最大速度值設為4。

2.4 仿真結果

仿真實驗數據通過10 次獨立實驗獲取，圖3 為3 種算法在F1-F6函數上的收斂曲線比較圖（以種群數15、迭代次數500 次為例）。

為了更好地體現LDABPSO 算法的性能，表2 計算了BPSO 算法、ABPSO 算法、LDABPSO 算法在F1-F6函數上的均值及方差。

Fig.3 Function convergence curve圖3 函數收斂曲線

由于單峰函數F1、F2、F3沒有局部最小點，因此算法設置的維度較低，F4、F5、F6為多峰函數，函數隨著維度的增加會出現更多局部最小解，所以將其維度設置為30。從表2可知，種群數為15、20、25，對應迭代次數分別為500、600、700。不同的參數設定下，LDABPSO 算法在6 個標準測試函數中具有最好的均值，除多峰函數F5 外，算法同樣有最好的方差，說明算法具有較好的穩定性。通過對初始化種群、加入擾動、局部停滯解次數等多方面的改進后，LDABPSO的性能優于文獻［10］提出的ABPSO 算法和基本BPSO算法，且LDABPSO 算法在單峰函數上的收斂速度和精度高于ABPSO 算法、BPSO 算法。

圖3（d）—圖3（f）為多峰函數收斂曲線圖，曲線呈直線狀態時，說明此時算法已經陷入局部最優，不可避免的是3條曲線都出現了這種情況。曲線狀態由直線轉為折線時，說明算法跳出了局部最優，從多峰函數收斂曲線圖可以看出，相較于BPSO 算法、ABPSO 算法，LDABPSO 算法在多峰函數上的收斂曲線呈折線狀態較多，這說明算法具有很好的跳出局部最優的能力。如圖3（f）所示，在迭代300 次左右時，BPSO 算法、ABPSO 算法在局部已呈現直線狀態，而LDABPSO 算法依然呈折線狀態，說明算法在不斷跳出局部最優，向質量更好的解迭代，因此本文所提的LDABPSO 算法在單峰、多峰測試函數上均表現良好。

Table 2 Experimental simulation results表2 實驗仿真結果

3 LDABPSO 算法關聯規則挖掘

本文將一種改進二進制粒子群算法（LDABPSO）用于歷史復烤配方（2018-2020 年）的關聯規則挖掘，課題及數據均來源于云南省麒麟復烤廠。

3.1 復烤配方關聯特征挖掘設計

3.1.1 編碼

關聯規則就是從數據集中發現事務之間的關系，用形如{A}→{B}這樣的規則表示［18］。首先發現頻繁項集，頻繁項集指滿足最小支持度的集合，最終關聯規則由頻繁項集生成，用于描述兩種事物間存在很強的關系，生成的關聯規則必須同時滿足最小支持度和置信度。

定義1支持度表示事務A 和B 在整個數據庫中的占比，σ(D)代表整個事務數據庫，數學表達如式（4）所示。

定義2置信度表示所有包含A的事務中又包含事務B的占比，數學表達如式（5）所示。

由上述可知，關聯規則挖掘屬于離散域問題，因此本文采用二進制編碼，將原始數據轉換為二進制數據，每條記錄的屬性為0 或1［19］，在實際計算時便可很容易計算出相應的支持度和置信度，編碼表示如圖4 所示。

Fig.4 Coding圖4 編碼

3.1.2 解碼

傳統關聯規則挖掘Apriori 算法通過逐層搜索進行迭代的方法發現頻繁項集，進而直接得到關聯規則。二進制粒子群算法用于關聯規則挖掘則不同，在滿足既定最大迭代次數M的前提下，最后得到的M 個全局最佳位置需以一定方式解碼得到關聯規則。如Gbest=（000110111000），采用Holland的密歇根方法［20］，其按順序兩兩組合得到S1=（0，0），S2=（0，1），S3=（1，0），S4=（1，1），S5=（1，0），S6=（0，0），Gbest=（S1，S2，S3，S4，S5，S6），S1…S6分別由兩部分組成，第一部分若為1，則表示該事務出現在規則中，反之，規則中不存在該事務；第二部分表示該事務是規則的前項或后項，1為前項，0 為后項。綜上，Gbest 所代表的規則表示為{ 3,5} →{ 4}。

3.1.3 適應度函數

在Apriori 算法中，適應度函數多以支持度或置信度為主。單獨使用支持度為適應度函數，數據集中很少出現的項會被刪減，盡管它們仍然會產生潛在有價值的規則；若單獨使用置信度，根據置信度的定義，具有更高支持度的結果將自動產生更高的置信值，即使項目之間不存在關聯。因此，本文采用文獻［21］所提的使用支持度和置信度的乘積作為關聯規則挖掘研究的適應度函數，如式（6）所示。

3.2 復烤配方關聯規則挖掘實現

用拉丁超立方抽樣初始化每個粒子，重復以下步驟，直到達到預先指定的迭代次數M。

Step1：使用式（6）計算所有粒子的適應度函數；

Step2：更新局部最佳值和全局最佳值；

Step3：使用式（2）更新粒子位置；

Step4：判斷粒子的位置在limit 閾值內是否發生變化；

Step5：粒子的位置若沒有發生變化，重新生成新的粒子保持種群不變，返回Step1；

Step6：若粒子位置發生變化，滿足結束條件，挖掘停止。

這個過程將生成一個單一的規則，算法需運行M 次，以便從數據中獲取前M 個規則，基于LDABPSO 算法的煙葉復烤配方關聯規則挖掘過程如圖5 所示。

Fig.5 LDABPSO algorithm-based association rule mining flow for redrying formula圖5 基于LDABPSO 算法的復烤配方關聯規則挖掘流程

3.3 數據預處理

現有歷史復烤配方共計82 個，分為不同的配方模塊，但是由于有些配方模塊數較少，不適合關聯規則挖掘，因此本文結合企業實際生產，對主要生產加工配方模塊進行關聯規則挖掘。通過對配方數據的篩選及整理，得到實驗所用復烤配方數據，共計12 行、72 列。若對應行的配方中包含對應列的煙葉，則為1，反之為0，A 模塊配方數據如表3 所示。

Table 3 Module A formula data表3 A模塊配方數據

3.4 關聯規則挖掘結果比較分析

從規則提取時間、提取數量、規則質量3 個方面分別對Apriori 算法、基于LDABPSO 算法的關聯規則挖掘結果進行實驗比較。

3.4.1 規則提取時間比較

使用Apriori 算法進行復烤配方挖掘時，將支持度設置為0.18，置信度設置為0.5。LDABPSO 算法中，算法總體規模保持在20 次，迭代次數保持在50 次，取20 次實驗結果的平均值，兩種算法的運行時間對比如表4 所示。

Table 4 Time comparison表4 時間比較 （s）

根據表4 可知，LDABPSO 算法相比于Apriori 算法運行時間減少8.4%。這主要是因為Apriori 算法在運行時，采用逐層搜索迭代策略，在實際計算時，需要多次掃描輸入數據，而LDABPSO 算法不需要多次掃描數據，只需要將處理過后的數據按照既定的條件迭代，最后得到的全局最好值即為提取到的較佳規則，且隨著數據集的增大，本文所提出的方法在運行時間方面將會有更突出的優勢。

3.4.2 規則提取質量

因得到的規則數量較多，表5 所展示的只是部分規則。表5 中［0.21，0.52］代表支持度為0.21，置信度為0.52。以改進算法提取的規則5 為例，規則表示為{53,62} →{55,57}，可以看出模塊配方同時包含煙葉編號為53、62、55、57的概率為10%，置信度為1，表明在實際模塊配方中，在含有煙葉編號53、62的前提下，有100%的概率包含編號為55 和57的煙葉，規則提取質量比較如表5 所示。

通過表5 可知，Apriori 算法提取出的規則{ 6} →{ 23}和{ 23} →{ 6} 為冗余規則，而LDABPSO 算法提取到的規則只有{ 6} →{ 23}。同樣地，規則{17,18,23} →{6,13,16} 和規則{17,6} →{13,17,18,23} 也為冗余規則，可見在Apriori算法中，會出現大量的冗余規則，這造成兩種不同算法提取到的規則數量出現很大差距。

Table 5 Comparison of rule extraction quality（partial）表5 規則提取質量比較（部分）

綜上，Apriori 算法提取到的規則多為無效規則。此外，LDABPSO 算法還能挖掘出被忽略的低支持度而高置信度的關聯規則，而往往這類規則具有重要價值，例如規則{6,20,35,37} →{17,32}，這是Apriori 算法無法實現的。

3.4.3 規則提取數量

對于Apriori 算法，需要提前設定好最小支持度和最小置信度，最后得到的煙葉搭配規則數受上述兩個參數的影響較大。將其最小支持度和最小置信度分別設置為0.18和0.5，提取規則共計4 073 條，將其分別設置為其他數值，如0.2 和0.5，得到的結果僅1 532 條，又如設定為0.1 和0.3，得到結果共8 956 條，由此可見，Apriori 算法受主觀性影響很大。若最小支持度和最小置信度設定過小，結果集會出現海量規則；如果設定過大，又會丟失很多重要規則，LDABPSO 算法解決了從海量雜亂規則中人工盲目篩選規則的問題，兩種算法得到的規則數量比較如表6 所示。

Table 6 Comparison of number of rules表6 規則數量比較

綜上可知，運用LDABPSO 算法挖掘A 配方模塊中煙葉之間的協同、搭配信息規則，經過比對真實配方數據，挖掘到的結果和真實配方數據保持一致，因而采用LDABPSO 算法挖掘到的煙葉搭配規則有效。

4 結語

本文將一種改進二進制粒子群算法（LDABPSO）用于復烤配方的關聯規則挖掘，對BPSO 算法提出改進策略，將其應用于關聯規則復烤配方挖掘，并通過實驗對比驗證所提算法的有效性。LDABPSO 算法避免了Apriori 算法預設最小支持度和最小置信度的缺陷及大量冗余規則的出現，且規則質量進一步提升。在實際生產中，使用LDABPSO 算法挖掘到的復烤配方中煙葉協同搭配信息可在一定程度上實現復烤配方維護。此外，各配方模塊所使用的主要煙葉每年變動不大，對于復烤企業而言，可以根據挖掘到的煙葉協同規則為卷煙企業提前準備煙葉原料，縮短生產提前期。隨著配方數的不斷增多，未來可考慮從算法運行時間、規則質量提升方面作進一步優化。