基于遺傳模擬退火算法的藥品零售大數(shù)據(jù)關聯(lián)規(guī)則挖掘

盛 魁，馬 健，曹 巖，卞顯福

(1.亳州職業(yè)技術學院 信息工程系，安徽 亳州 236800；2.安徽中醫(yī)藥科學院 亳州中醫(yī)藥研究所，安徽 亳州 236800；3.中國科學技術大學 軟件學院，安徽 合肥 230051)

隨著大數(shù)據(jù)、云計算、物聯(lián)網(wǎng)、移動互聯(lián)網(wǎng)等信息技術爆發(fā)式發(fā)展，藥品零售企業(yè)積累大量的數(shù)據(jù)。目前，這些數(shù)據(jù)只用在銷售統(tǒng)計和藥品庫存管理上，對數(shù)據(jù)相關性分析和預測分析等深層次運用較少，使得這些有價值的資源卻成為企業(yè)信息存儲的負擔。如何從這些海量數(shù)據(jù)中挖掘出有價值的藥品關聯(lián)知識，實現(xiàn)藥品的精準銷售和個性推薦成為當前人們研究的熱點。關聯(lián)規(guī)則挖掘是一種有效的數(shù)據(jù)挖掘方法，它可以從大量的數(shù)據(jù)信息中發(fā)現(xiàn)隱藏的、有價值的關聯(lián)和規(guī)律[1]。大數(shù)據(jù)的關聯(lián)規(guī)則挖掘流程包括源數(shù)據(jù)的獲取、頻繁項集提取、強關聯(lián)規(guī)則提取和有價值關聯(lián)規(guī)則提取，已應用于電力、金融、交通、醫(yī)療、零售等領域[2-3]。

本文從藥品零售大數(shù)據(jù)本身出發(fā)完成知識發(fā)現(xiàn)，在遺傳算法選擇操作、交叉運算和變異運算中融入模擬退火算法，提出一種基于遺傳模擬退火算法的關聯(lián)規(guī)則挖掘改進算法，用以挖掘藥品零售大數(shù)據(jù)之間關聯(lián)和規(guī)律，有效地量化了藥品之間的相關程度，為藥品零售企業(yè)的經(jīng)營決策提供支持，能夠為企業(yè)帶來更多潛在商業(yè)機會。

1 關聯(lián)規(guī)則技術研究

1.1 關聯(lián)規(guī)則挖掘

關聯(lián)規(guī)則挖掘是從海量數(shù)據(jù)中發(fā)現(xiàn)事物之間可能存在的關聯(lián)和相互關系，以揭示事物間內在的本質聯(lián)系。設I={i1,i2,…,im}是所有數(shù)據(jù)項的集合，給定一個事務集合D，T={t1,t2,…tm}為D中的一個事務，即T?I。若項集A?I且A?T，則事務T包含項集A，關聯(lián)規(guī)則是形如A?B的蘊含式，其中A?I，B?I，且A∩B=φ。一般用支持度(support)和置信度(confidence)來衡量一個關聯(lián)規(guī)則，支持度表示關聯(lián)規(guī)則出現(xiàn)的頻度，表達式為：support(A?B)=P(A∪B)，置信度則表示關聯(lián)規(guī)則的強度，表達式為：confidence(A?B)=P(A|B)。如果規(guī)則不但滿足support(A?B)>supportmin，而且滿足confidence(A?B)>confidencemin，則稱規(guī)則A?B為強關聯(lián)規(guī)則。關聯(lián)規(guī)則挖掘是要在事務集合中找出全部強規(guī)則。

1.2 關聯(lián)規(guī)則挖掘方法

常用的關聯(lián)規(guī)則挖掘算法有Apriori算法、FP-growth算法、Eclat算法、神經(jīng)網(wǎng)絡法、決策樹法、粗糙集和遺傳算法等，但在具體應用時會根據(jù)實際問題需求對現(xiàn)有挖掘算法進行融合或改進，有針對性的進行數(shù)據(jù)分析和挖掘[4]。

(1)Apriori算法

Apriori算法是一種寬度優(yōu)先算法，算法簡單、易實現(xiàn)，不需要構建新的數(shù)據(jù)結構。當數(shù)據(jù)庫中的數(shù)據(jù)量較大時，需要對數(shù)據(jù)庫多次掃描數(shù)而產(chǎn)生大量頻繁項集，導致算法效率不高[5]。

(2)FP-growth算法

FP-growth算法采用分而治之的策略，算法對數(shù)據(jù)庫僅需掃描兩次且不需要產(chǎn)生候選集，在效率上優(yōu)于Apriori算法。但算法構建項頭表、FP-tree和條件FP-tree等數(shù)據(jù)結構需要消耗大量存儲空間，影響挖掘效率[6]。

(3)Eclat算法

Eclat算法是一種深度優(yōu)先搜索的算法，算法對數(shù)據(jù)庫不需要重復多次遍掃描，通過交集操作求頻繁項集。但算法無法對產(chǎn)生的候選集做剪枝操作，生成大量的候選項集，并且算法在運行的過程中，會消耗大量存儲空間[7]。

(4)遺傳算法

遺傳算法(Genetic Algorithm, GA)是基于達爾文進化論的自適應全局優(yōu)化概率搜索算法，通過選擇、交叉、變異等遺傳運算達到優(yōu)化的目的。GA算法具有良好的全局搜索特性，但算法在進化過程中容易出現(xiàn)早熟現(xiàn)象。遺傳算法已在機器學習、人工智能、信號處理、組合優(yōu)化和自適應控制和等領域得到廣泛的應用。

(5)模擬退火算法

模擬退火算法(Simulated Annealing Algorithm, SA)是基于蒙特卡洛思想設計的隨機尋優(yōu)迭代求解算法，在問題求解中引入熱力學的退火平衡模型，能夠實現(xiàn)搜索全局最優(yōu)解。SA算法在較小的范圍內具有尋優(yōu)速度快、收斂精度高等特點，但是尋優(yōu)的結果受初始值的影響較大。模擬退火算法已在生產(chǎn)調度、機器學習、控制工程、信號處理、神經(jīng)網(wǎng)絡等領域得到了廣泛應用。

2 基于GA-SA算法的關聯(lián)規(guī)則挖掘設計

2.1 挖掘算法設計思想

為了克服GA算法局部搜索能力差、早熟收斂，且易陷入局部最優(yōu)解的缺點，將SA算法融入GA算法中，形成一種高效的GA-SA算法，實現(xiàn)對藥品零售大數(shù)據(jù)關聯(lián)規(guī)則挖掘。GA-SA算法以GA算法為主體，SA算法為其輔助，在SA算法選擇操作、交叉運算和變異運算中融入SA算法，從而提高算法的效率。通過GA算法尋找一批優(yōu)良的群體，利用SA算法抑制群體陷入局部最優(yōu)，進一步調整優(yōu)化種群，減少消耗進而篩選得到有用規(guī)則。挖掘流程如圖1所示。

圖1 GA-SA算法的關聯(lián)規(guī)則挖掘流程圖

2.2 GA-SA算法的設計

(1)編碼方法的設計

關聯(lián)規(guī)則編碼是設計GA-SA算法時的一個關鍵步驟。為了便于交叉、變異和選擇算子的操作，采用實數(shù)編碼方法對個體進行編碼。假設個體的長度為N,定義實數(shù)數(shù)組A[N]與其對應，字段的屬性值與數(shù)組A[i](i∈[1，N])的元素值一一對應，如果此屬性與其他的屬性無關聯(lián)則A[i]的值為0。

(2)適應度函數(shù)設計

適應度函數(shù)是GA-SA算法進化過程的驅動力，也是群體進化過程中用到的唯一信息。采用可信度和支持度表示適應度函數(shù)，適應度函數(shù)表達式為：

(1)

其中，ws+wc=1，ws≥0，wc≥0，supportmin表示支持度的閾值，confidencemin表示可信度的閾值。

(3)選擇操作

選擇操作是為了提高全局收斂性和計算效率，避免基因缺失。采用最佳個體保存法進行選擇操作，保證交叉和變異操作不能破壞進化過程中某一代的最優(yōu)解。在當前種群P={x1,x2,…,xn}中，個體xi被選中進入下一代的概率為：

(2)

其中，f(xi)是個體xi的適應度函數(shù)。Tk為進化到第k代時的退火溫度。

(4)交叉退火和變異退火操作

變異退火操作GA-SA算法中生成新個體的主要手段。為了不會影響算法的效率，本文采用單點交的方法。p1、p2按照預定交叉概率，交叉生成新子代c1、c2，計算f(ci)、f(pi)(i=1,2)的值，同時實施模擬退火操作[8]，如果f(ci)>f(pi)，則用ci代替pi；如果f(ci)

(5)降溫操作

采用有限的非齊次馬爾可夫鏈序列[9]實現(xiàn)降溫操作，溫度變化表達：

(3)

3 基于GA-SA算法的關聯(lián)規(guī)則挖掘

本文開發(fā)環(huán)境為Python，版本為Python3.6，IED為Pycharm和Anaconda，運行平臺為windows 10，算法用Python語言實現(xiàn)。

3.1 數(shù)據(jù)采集

實驗數(shù)據(jù)來自亳州某連鎖零售藥店21家門店2018年5月1日到2018年10月1日6個月的數(shù)據(jù)，數(shù)據(jù)庫包括藥品信息表、藥品類別和門店的銷售表三類原始數(shù)據(jù)表格682000條記錄。

(1)藥品信息表。包括藥品編碼、藥品名稱、規(guī)格、類別、藥品屬性、產(chǎn)地、原價、單價、條形碼等。

(2)藥品類別表。包括商品的藥品編號、藥品名稱、類別碼和類別名稱(如心腦血管類，胃腸類等)、藥品屬性(中成藥、西藥、中藥飲片)等。

(3)門店的銷售表，包括流水號、門店號、購買藥品序號、日期、藥品編碼、購買數(shù)量、銷售價格等。

3.2 數(shù)據(jù)預處理

獲取的原始數(shù)據(jù)含有一些“臟數(shù)據(jù)”，低質量的“臟數(shù)據(jù)”將會導致低質量的挖掘結果。數(shù)據(jù)處理主要包括“臟數(shù)據(jù)”(不完整的數(shù)據(jù)、有明顯錯誤的數(shù)據(jù)以及重復數(shù)據(jù))的剔除和處理。數(shù)據(jù)預處理的過程主要有：

(1)數(shù)據(jù)清洗

根據(jù)數(shù)據(jù)分析的任務選擇任務所需的數(shù)據(jù)對象和屬性，對缺失數(shù)據(jù)、重復數(shù)據(jù)和異常數(shù)據(jù)等不規(guī)整的數(shù)據(jù)進行清洗。針對臟數(shù)據(jù)，應用Python編寫程序對原始數(shù)據(jù)進行處理，清除挖掘中不需要的數(shù)據(jù)信息，保存藥品數(shù)據(jù)的原始特征。

(2)數(shù)據(jù)集成

數(shù)據(jù)挖掘只需要導入需要的數(shù)據(jù)，這就需要針對終端零售數(shù)據(jù)存儲在關系數(shù)據(jù)庫中的不同表結構中，提取藥品信息表、藥品類別和門店的銷售表所需的數(shù)據(jù)列數(shù)據(jù)，如藥品名稱、類別名稱、銷售時間、銷售數(shù)量等數(shù)據(jù)進行處理，提取所需的數(shù)據(jù)列數(shù)據(jù)。對原始數(shù)據(jù)682000條記錄，經(jīng)過數(shù)據(jù)清洗和去重等處理后有561357條記錄為有效記錄。

3.3 算法步驟

Step1.初始化控制參數(shù)。群體規(guī)模M，最大遺傳代數(shù)MAX，初始種群P，交叉概率Pc，變異概率Pm，初始退火溫度T0，終止溫度Tend，最小支持度supportmin和最小置信度confidencemin。

Step2.適應度函數(shù)計算。根據(jù)公式(1)計算當前種群P中的每個體適應度值。

Step3.選擇操作。根據(jù)公式(2)對全部個體都進行了選擇操作。

Step4.交叉退火操作。按照本文GA-SA算法設計進行交叉退火操作。

Step5.變異退火操作。方法同Step4。

Step6.降溫操作。根據(jù)公式(3)進行降溫操作。

Step7.算法終止。判斷遺傳代數(shù)是否達到給定到最大遺傳代數(shù)或降溫溫度是否達到終止溫度，如果達不到轉Step2；否則結束算法。

Step8.關聯(lián)規(guī)則挖掘與提取。

4 挖掘結果與算法性能分析

4.1 關聯(lián)規(guī)則挖掘

初始種群規(guī)模為40，最大的迭代次數(shù)MAX=30，交叉概率為0.9，變異概率為0.05；最小置信度為0.6，最小支持度設定為0.01，初始溫度為50000，退火終止溫度為15；溫度可以下降的最大次數(shù)M=1000。

采用GA-SA算法的關聯(lián)規(guī)則挖掘算法對預處理后的數(shù)據(jù)進行分析，最終得到關聯(lián)規(guī)則7715條，發(fā)現(xiàn)部分關聯(lián)規(guī)則如圖2所示。

圖2 藥品和藥品關聯(lián)規(guī)則結果

從圖2中可以看出，以“抗感冒藥?抗病毒藥”規(guī)則為例，在購買不同種類的消費者中，購買抗感冒藥類藥品同時購買了抗病毒藥，感冒大部分是由病毒引起的，毒性感染導致的鼻塞、流涕、打噴嚏等癥狀，從醫(yī)學角度看，需要理抗病毒藥如雙黃連口服液或者抗病毒片等藥品進行聯(lián)合治療，規(guī)則與實際用藥情況基本相符。

規(guī)則“腸胃疾病類?營養(yǎng)保健類”表明，消費者在購買腸胃疾病類藥品的時候購買營養(yǎng)保健類藥品的機率比較大。在購買奧美拉唑腸溶膠囊、硫糖鋁片、正露丸等腸胃道用藥的同時還會買類似復方阿膠、六味地黃丸、維生素類的藥品。從醫(yī)學角度看，由于腸胃消化不好的顧客通常體質比較弱，在治療腸胃需要服用營養(yǎng)保健增加腸胃道消化，符合一定用藥的規(guī)律。

規(guī)則“高血壓類?心腦血管用藥”表明，購買高血壓類藥品的消費者，同時也可能購買心腦血管用藥的藥品?；颊唛L時間服用硝苯地平緩釋片、卡托普利片和替米沙坦降壓藥會導致擴張血管，配合服用阿司匹林腸溶片、復方丹參片和腦洛通膠囊，增加血管彈性，預防腦溢血，調解血脂，改善血液粘稠度，規(guī)則與實際用藥情況基本一致。

4.2 算法性能分析

為了驗證GA-SA算法的性能，從事務數(shù)目和支持度兩方面分別與Apriori算法和GA算法進行比較，算法采用Python實現(xiàn)。不同事務數(shù)目下算法性能比較結果如圖3和圖4圖所示；不同支持度下算法性能比較結果如圖5和圖6圖所示。

圖6 不同支持度下算法挖掘規(guī)則數(shù)目比較

圖5 不同支持度下算法運行時間比較

圖3 不同事務數(shù)目下算法運行時間比較

圖4 不同事務數(shù)目下算法挖掘規(guī)則數(shù)目比較

通過圖3和圖4可以看出，在事務數(shù)據(jù)量不斷增加的情況下，運行時間都在增加，但GA-SA算法相比Apriori算法和GA算法挖掘速率略微快些，說明GA-SA算法在處理大規(guī)模數(shù)據(jù)集時，運行較快，性能較好。相同的事務數(shù)據(jù)量下，GA-SA算法挖掘出的規(guī)則數(shù)更多。

通過圖5和圖6可以看出，三種算法的性能都受支持度的影響，同一支持度下GA-SA算法挖掘關聯(lián)規(guī)則運行時間最短，但挖掘的關聯(lián)規(guī)則數(shù)目最多。

通過上面兩種情況下的比較，證明了GA-SA算法不論在運行時間還是在挖掘規(guī)則數(shù)目上都要優(yōu)于Apriori算法和GA算法，說明了GA-SA算法在挖掘關聯(lián)規(guī)則方面具有較高的運行效率和較全面的關聯(lián)規(guī)則。

結語

本文以遺傳算法為主導，模擬退火算法作為其輔助，提出了一種新穎的GA-SA算法挖掘關聯(lián)規(guī)則算法，對藥品零售大數(shù)據(jù)進行分析，能夠挖掘出隱藏在藥品零售大數(shù)據(jù)之中有價值的知識與信息，并自動計算出藥品之間的支持度與置信度，有效地度量了藥品之間的影響程度，為藥品零售企業(yè)決策提供了參考依據(jù)，并通過與Apriori算法和GA算法進行對比，證明了GA-SA算法的有效性。藥品零售大數(shù)據(jù)的挖掘研究仍具有很大的空間，如何設計更準確的算法實現(xiàn)藥品銷售預測和智能采購，將是我們下一步研究的內容。