朱天宇, 譚文安

(上海第二工業(yè)大學(xué) 計算機與信息工程學(xué)院,上海 201209)

0 引言

清華大學(xué)國家金融研究院中國保險與養(yǎng)老金研究中心發(fā)布的《2021中國互聯(lián)網(wǎng)保險消費者洞察報告》顯示,傳統(tǒng)線下網(wǎng)點、保險代理人仍然是主要代理渠道,調(diào)查人群中88%的人通過線下渠道購買保險。然而,目前保險公司線下推薦保險產(chǎn)品時,主要依靠保險經(jīng)理人的經(jīng)驗,對于新員工而言,經(jīng)驗的缺乏和普遍的能力不足導(dǎo)致了推薦的產(chǎn)品不滿足客戶需求的問題,因而銷售成功率低、客戶滿意度低。近年來,數(shù)據(jù)規(guī)模呈幾何級數(shù)高速成長。海量數(shù)據(jù)已經(jīng)成為企業(yè)資產(chǎn)的一部分[1],數(shù)據(jù)分析技術(shù)也日漸成熟[2]。在這種情況下,商務(wù)智能技術(shù)的應(yīng)用給問題的解決提供了可行方案。數(shù)據(jù)分析表明,多家公司采用商務(wù)智能優(yōu)化業(yè)務(wù)方法之后,在規(guī)避風(fēng)險和保留客戶方面取得了更好的效果[3]。

Apriori算法是由Agrawal和Skrikant于1994年提出的關(guān)聯(lián)規(guī)則算法,用于挖掘頻繁項集間的關(guān)聯(lián)規(guī)則。但是在大規(guī)模數(shù)據(jù)庫中應(yīng)用Apriori算法的效率非常低,因為Apriori算法使用逐層搜索的迭代方法尋找頻繁項集。自Apriori算法出現(xiàn)至今,不少學(xué)者從不同角度對該算法提出了優(yōu)化和改進的方法。周發(fā)超等[4]提出了一種Apriori的改進方案I Apriori,通過減少掃描數(shù)據(jù)庫次數(shù),降低候選項集計算復(fù)雜度以及減少預(yù)剪枝步驟計算量等途徑提高了算法的執(zhí)行效率。張繼榮等[5]基于新的數(shù)據(jù)結(jié)構(gòu),利用Hash表的存儲技術(shù)以及對Apriori算法的優(yōu)化提高了查找頻繁項集的效率。胡世昌等[6]提出以二進制編碼的項集作為載體載入內(nèi)存,并在二進制編碼的基礎(chǔ)上有效地進行等效的集合之間的運算,有效提高了Apriori算法的執(zhí)行效率和空間利用率。陳晨等[7]提出的Gra-Apriori算法,解決了經(jīng)典的Apriori無法考慮屬性類別關(guān)系的問題。郭凱等[8]改進后的Apriori算法大大減少了無效規(guī)則的產(chǎn)生,通過關(guān)聯(lián)分析可得到對斷面進行調(diào)整的有效強關(guān)聯(lián)規(guī)則。高海洋等[9]通過數(shù)據(jù)壓縮的方法減少了數(shù)據(jù)庫掃描次數(shù)的同時,對生成的候選集進行了多次驗證,大大減少了無效候選集的數(shù)量。趙學(xué)健等[10]對Apriori算法復(fù)雜的自連接和剪枝過程進行了優(yōu)化,簡化了頻繁項目集的生成過程,提高了Apriori算法的時間效率。Supriyono等[11]將Apriori算法應(yīng)用到農(nóng)業(yè)領(lǐng)域,提高了農(nóng)產(chǎn)品銷售額。

以上介紹的相關(guān)算法實施比較復(fù)雜,或者雖有改進但不能較好適用于應(yīng)用場景問題,本文通過采取Python字典列表[12]以鍵值方式重新組織數(shù)據(jù)、根據(jù)時序劃分數(shù)據(jù)集、僅僅計算頻繁2-項集的差集[13]等方式來提高算法執(zhí)行效率,通過以客戶為主鍵聚合事務(wù)數(shù)據(jù)來挖掘潛在關(guān)聯(lián)規(guī)則,從而達到算法優(yōu)化的目的,改進了Apriori算法,提出了一種改進的DS Apriori算法,計算出關(guān)聯(lián)規(guī)則,以得出已經(jīng)停售的保險產(chǎn)品的最佳替代產(chǎn)品,來指導(dǎo)保險經(jīng)理人線下展業(yè),在最大程度上保留客戶。

本文將詳細闡釋改進的DS Apriori算法和具體實現(xiàn),并對DS Apriori算法與Apriori等算法進行實驗和對比分析,最后得出總結(jié)及工作展望。

1 改進的Apriori算法

1.1 算法改進方案

1.1.1 問題定義

設(shè)J={I1,I2,···,Im}是項的集合,設(shè)數(shù)據(jù)D是數(shù)據(jù)庫事務(wù)的集合,其中每個事務(wù)T是一個非空項集,使得T?J。每個事務(wù)都有一個標識符,稱為TID。設(shè)A是一個項集,事務(wù)T包含A,當且僅當A?T。關(guān)聯(lián)規(guī)則是形如A?B的蘊涵式,其中A?J,B?J,A/=?,B/=?,并且A∩B=?。規(guī)則A?B在事務(wù)集D中成立。具有支持度s,其中s是D中事務(wù)包含A∪B的百分比。它是概率P(A∪B)。規(guī)則A?B在事務(wù)集D中具有置信度c,其中c是D中包含A的事務(wù)同時也包含B的事務(wù)的百分比。這是條件概率P(B|A),即:

同時滿足最小支持度閾值(min sup)和最小置信度閾值(min conf)的規(guī)則為強規(guī)則,項的集合稱為項集,包含k個項的項集稱為k項集,如集合X={I1,I2}是一個2項集。

1.1.2 數(shù)據(jù)準備

保險產(chǎn)品通常具有時效性,保險產(chǎn)品的推陳出新已是司空見慣[14]。傳統(tǒng)的Apriori算法沒有對數(shù)據(jù)進行針對性的劃分,由于數(shù)據(jù)中包含已經(jīng)停售的產(chǎn)品,在產(chǎn)生關(guān)聯(lián)規(guī)則時,會產(chǎn)生停售產(chǎn)品之間的關(guān)聯(lián)規(guī)則,既浪費了寶貴的計算性能,又沒有意義。這里按照保險產(chǎn)品A的停售時間,將完整數(shù)據(jù)集CompleteSale集中停售之前的數(shù)據(jù)劃分出來,稱為BeforeStopSale集。通過重新劃分數(shù)據(jù)集,為差集的計算提供數(shù)據(jù)準備,以此來挖掘新舊產(chǎn)品之間的關(guān)聯(lián)規(guī)則。

傳統(tǒng)的算法是以單次保險銷售記錄為一個事務(wù),一條銷售記錄往往只包含一份保單的內(nèi)容;如果直接在此基礎(chǔ)上采用Apriori算法,單次銷售記錄的不連續(xù)忽略了用戶所購買產(chǎn)品在時序上的相關(guān)性;不能夠很好地將同一用戶的多次購買記錄關(guān)聯(lián)起來,導(dǎo)致了潛在關(guān)聯(lián)規(guī)則的丟失,關(guān)聯(lián)規(guī)則挖掘效果受到影響。因此,本文重新組織了數(shù)據(jù),將同一用戶的所有購買記錄整合為一條事務(wù)記錄加入運算,建立起用戶所購買產(chǎn)品之間的時序聯(lián)系;使用Python的字典列表數(shù)據(jù)結(jié)構(gòu),通過鍵值對保存用戶購買的產(chǎn)品以及該產(chǎn)品的購買次數(shù),以此保留了原始數(shù)據(jù)作為多重集合的數(shù)據(jù)特征如表1所示;同時將購買次數(shù)也加入支持度計數(shù)的計算,用戶重復(fù)購買這一行為在數(shù)據(jù)中得到了體現(xiàn)(見表2),更能體現(xiàn)用戶的購買偏重。采用內(nèi)存數(shù)據(jù)庫Redis保存鍵值對數(shù)據(jù),以此優(yōu)化數(shù)據(jù)加載速度,進一步提高算法性能。

表1 Apriori算法輸入數(shù)據(jù)格式Tab.1 The input data form for Apriori algorithm

表2 DSApriori輸入數(shù)據(jù)格式Tab.2 The input data form for DSApriori algorithm

1.1.3 算法改進

傳統(tǒng)的Apriori算法因為效率低下很少用在大規(guī)模數(shù)據(jù)挖掘中。本文放棄其迭代搜索全部的頻繁項集的思路,轉(zhuǎn)而搜索目標項目的頻繁2-項集,只挖掘目標項目的二項關(guān)聯(lián)規(guī)則,減少連接操作,以此解決頻繁的連接操作造成的性能問題。

式中,X為頻繁2-項集;ResultSet為頻繁2-項集的集合。由先驗性質(zhì)的數(shù)學(xué)原理可得,產(chǎn)生頻繁2-項集并不需要剪枝,再次提高了算法的效率。在BeforeStopSale數(shù)據(jù)集和CompleteSale數(shù)據(jù)集產(chǎn)生頻繁2-項集得到結(jié)果ResultSetBeforeStopSale和ResultSetCompleteSale之后,分別計算出各自的關(guān)聯(lián)規(guī)則集合RuleSetCS和RuleSetBSS

最終得到的關(guān)聯(lián)規(guī)則集合RuleSettarget,即可推出保險產(chǎn)品A的替代產(chǎn)品。

1.2 DS Apriori算法偽代碼

改進的Apriori算法偽代碼描述如下:

Algorithm 1 DS Apriori Input:D,min sup Output:L,frequent 2-itemset in D.1. L1=find frequent 1 itemsets(D);2. C2=apriori gen(L1);3. for each transaction t∈D{4. C t=subset(C2,t);5. c.count++;6.}7.for each candidate c∈C t;8. L2={c∈C2|c.count>=min sup}9.Return L2;10.Procedure apriori gen(L1:frequent 1 itemset)11. for each itemset l1∈l1 12. for each itemset l2∈l1 13. if(l1[1]=l2[1])∧···∧(l1[0]=l2[0])∧(l1[1]

改進的DSApriori算法創(chuàng)新工作主要包括如何構(gòu)造頻繁2-項集和關(guān)聯(lián)規(guī)則兩部分。

1.2.1 頻繁2-項集構(gòu)造

構(gòu)造頻繁2-項集目的是找出所有可能存在的二元關(guān)聯(lián)項集,其構(gòu)造步驟如下:

(1)從生產(chǎn)數(shù)據(jù)庫中獲取原始數(shù)據(jù),利用SQL語句重新組織數(shù)據(jù),以字典列表的數(shù)據(jù)結(jié)構(gòu)存儲以用戶ID為TID的事務(wù)數(shù)據(jù)集合BeforeStopSale集和CompleteSale集;BeforeStopSale是保險產(chǎn)品A停售之前的所有保險銷售數(shù)據(jù);CompleteSale是所有的保險銷售數(shù)據(jù)。

(2)輸入預(yù)定的最小支持度計數(shù)min sup,掃描事務(wù)數(shù)據(jù)集合,計算每個1-項集的支持度計數(shù)(即每個產(chǎn)品的購買次數(shù));刪除小于最小支持度計數(shù)的集合,得到頻繁1-項集的集合L1。

(3)連接步:使用L1自連接[15]產(chǎn)生候選2-項集的集合C2。

(4)剪枝步:根據(jù)先驗性質(zhì),刪除子集不是頻繁1-項集的候選2-項集,得到剪枝后的C2,需要注意的是,這一步并沒有候選項從C2中刪除,因為這些候選的每個子集也都是頻繁的。

(5)計算每個候選2-項集的支持度計數(shù),刪除小于最小支持度計數(shù)的候選2-項集,得到頻繁2-項集的集合L2。

(6)對BeforeStopSale和CompleteSale分別執(zhí)行步驟(2)～(5),得到頻繁2-項集ResultSetBeforeStopSale和ResultSetCompleteSale。

1.2.2 關(guān)聯(lián)規(guī)則構(gòu)造

關(guān)聯(lián)規(guī)則的作用是確定關(guān)聯(lián)項之間的關(guān)聯(lián)關(guān)系,其構(gòu)造步驟如下:

(1)設(shè)置置信度閾值min conf;

(2)構(gòu)造L2中頻繁2-項集的項之間的關(guān)聯(lián)規(guī)則A?X,此處僅構(gòu)造目標產(chǎn)品A與其蘊含的項集之間的關(guān)聯(lián)規(guī)則,并計算置信度;

(3)刪除小于置信度閾值的關(guān)聯(lián)規(guī)則,最終得到滿足條件的強關(guān)聯(lián)規(guī)則;

(4)分別對頻繁2-項集ResultSetBeforeStopSale和ResultSetCompleteSale執(zhí)行(1)～(3)步驟,得到強關(guān)聯(lián)規(guī)則集合RuleSetBSS和RuleSetCS;

(5)依據(jù)RuleSettarget=RuleSetCS-RuleSetBSS,求得RuleSettarget集合中關(guān)聯(lián)規(guī)則右端即為保險產(chǎn)品A的最可能替代產(chǎn)品。

2 實驗結(jié)果與分析

為了驗證所提出算法的有效性和高效性,將所提出的DS Apriori算法與經(jīng)典的Apriori和Han等[16]提出的不產(chǎn)生中間項集的FP-growth進行了對比試驗。實驗環(huán)境參數(shù)如表3所示,算法使用Python語言實現(xiàn)。測試數(shù)據(jù)集mushroom.dat來自UCI公共數(shù)據(jù)集[17]。

表3 實驗環(huán)境參數(shù)Tab.3 Experiment environment parameters

Mushroom數(shù)據(jù)集包括對姬松茸和Lepiota家族中23種鰓蘑菇的假設(shè)樣本的描述,包含8 124條數(shù)據(jù),存在缺失值,用1代替;共23個屬性。

為了消除單次實驗帶來誤差的影響,本文采用了多次取平均的方式,統(tǒng)計在不同最小支持度的情況下算法的執(zhí)行時間。對Mushroom數(shù)據(jù)集應(yīng)用Apriori等算法和本文算法的執(zhí)行時間如表4所示。

表4 Mushroom數(shù)據(jù)集的實驗結(jié)果對比Tab.4 Experiment results of Mushroom data set

為了更加直觀地展現(xiàn)3種算法執(zhí)行時間的對比情況,表4中執(zhí)行時間的可視化如圖1所示。

圖1 Mushroom數(shù)據(jù)集的實驗結(jié)果對比Fig.1 Experiment results of Mushroom data set

圖1所示為各算法計算得出635個2項關(guān)聯(lián)關(guān)系的運行時間對比。從表4可以看出,DS Apriori算法在效率上明顯優(yōu)于Apriori算法,略優(yōu)于FPgrowth算法,在最小支持度較小時尤為明顯。隨著最小支持度增加,Apriori算法與FP-growth算法的執(zhí)行時間呈下降趨勢,但是DS Apriori算法的執(zhí)行時間卻基本持平。從圖1可以直觀地看出,DS Apriori算法隨最小支持度的增大,其執(zhí)行時間曲線幾乎趨于水平,而Apriori算法的下降幅度卻很大,尤其在最小支持度為0.20和0.22時表現(xiàn)得尤為明顯。但是當最小支持度為0.28時,兩種算法的執(zhí)行時間基本一致。這主要是因為最小支持度越大,過濾掉的頻繁k-項集(k＞2)越多,運算量也越相近。

在以上實驗中,以Mushroom數(shù)據(jù)集為對象,對Apriori、DS Apriori算法與FP-growth算法進行了比較,改進算法在效率上優(yōu)于后兩者。同時,從上述實驗結(jié)果可以看出,在不同的最小支持度取值下,Apriori算法在執(zhí)行時間上的波動幅度明顯大于改進算法。FP-growth算法的執(zhí)行時間隨著最小支持度的增加較為平穩(wěn)的下降,不斷逼近DS Apriori算法。綜上所述,本文改進算法DS Apriori的執(zhí)行效率大幅高于Apriori算法與FP-growth算法,是一種行之有效的頻繁2-項集生成算法。

DS Apriori算法與Apriori、FP-growth算法得出關(guān)聯(lián)規(guī)則的原理相同。Apriori、FP-growth算法得到的是二元及以上的關(guān)聯(lián)規(guī)則,DS Apriori算法得到的是二元關(guān)聯(lián)規(guī)則,在精準度上一致。在業(yè)務(wù)要求下,Apriori、FP-growth算法產(chǎn)生了冗余的關(guān)聯(lián)規(guī)則,DS Apriori算法效率更高、更符合要求。

3 結(jié) 語

本文提出了一種改進的DSApriori算法,創(chuàng)新工作表現(xiàn)在:①通過數(shù)據(jù)重組以挖掘出更多潛在的關(guān)聯(lián)規(guī)則;②通過計算頻繁2-項集的差集代替迭代搜索,減少搜索次數(shù),降低了算法的時間復(fù)雜度,為大規(guī)模數(shù)據(jù)實時處理提供了可行方案。依據(jù)此關(guān)聯(lián)規(guī)則得到某款已停售保險產(chǎn)品的最佳替代產(chǎn)品,為保險業(yè)務(wù)員線下展業(yè)提供指導(dǎo)。由于算法對數(shù)據(jù)要求較為嚴格,數(shù)據(jù)預(yù)處理花費較多時間。今后工作可考慮實現(xiàn)DSApriori算法與大數(shù)據(jù)存儲技術(shù)以及并行計算相結(jié)合,整體上提高算法的效率。