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

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

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

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

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

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

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

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

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

(1)Apriori算法

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

(2)FP-growth算法

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

(3)Eclat算法

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

(4)遺傳算法

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

(5)模擬退火算法

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

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

2.1 挖掘算法設(shè)計(jì)思想

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

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

2.2 GA-SA算法的設(shè)計(jì)

(1)編碼方法的設(shè)計(jì)

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

(2)適應(yīng)度函數(shù)設(shè)計(jì)

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

(1)

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

(3)選擇操作

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

(2)

其中，f(xi)是個(gè)體xi的適應(yīng)度函數(shù)。Tk為進(jìn)化到第k代時(shí)的退火溫度。

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

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

(5)降溫操作

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

(3)

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

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

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

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

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

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

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

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

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

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

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

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

數(shù)據(jù)挖掘只需要導(dǎo)入需要的數(shù)據(jù)，這就需要針對終端零售數(shù)據(jù)存儲(chǔ)在關(guān)系數(shù)據(jù)庫中的不同表結(jié)構(gòu)中，提取藥品信息表、藥品類別和門店的銷售表所需的數(shù)據(jù)列數(shù)據(jù)，如藥品名稱、類別名稱、銷售時(shí)間、銷售數(shù)量等數(shù)據(jù)進(jìn)行處理，提取所需的數(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.適應(yīng)度函數(shù)計(jì)算。根據(jù)公式(1)計(jì)算當(dāng)前種群P中的每個(gè)體適應(yīng)度值。

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

Step4.交叉退火操作。按照本文GA-SA算法設(shè)計(jì)進(jìn)行交叉退火操作。

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

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

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

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

4 挖掘結(jié)果與算法性能分析

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

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

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

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

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

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

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

4.2 算法性能分析

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

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

圖5 不同支持度下算法運(yùn)行時(shí)間比較

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

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

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

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

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

結(jié)語

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