朱天宇, 譚文安

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

0 引言

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

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

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

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

1 改進(jìn)的Apriori算法

1.1 算法改進(jìn)方案

1.1.1 問(wèn)題定義

設(shè)J={I1,I2,···,Im}是項(xiàng)的集合,設(shè)數(shù)據(jù)D是數(shù)據(jù)庫(kù)事務(wù)的集合,其中每個(gè)事務(wù)T是一個(gè)非空項(xiàng)集,使得T?J。每個(gè)事務(wù)都有一個(gè)標(biāo)識(shí)符,稱為TID。設(shè)A是一個(gè)項(xiàng)集,事務(wù)T包含A,當(dāng)且僅當(dāng)A?T。關(guān)聯(lián)規(guī)則是形如A?B的蘊(yùn)涵式,其中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ù)同時(shí)也包含B的事務(wù)的百分比。這是條件概率P(B|A),即:

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

1.1.2 數(shù)據(jù)準(zhǔn)備

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

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

表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 算法改進(jìn)

傳統(tǒng)的Apriori算法因?yàn)樾实拖潞苌儆迷诖笠?guī)模數(shù)據(jù)挖掘中。本文放棄其迭代搜索全部的頻繁項(xiàng)集的思路,轉(zhuǎn)而搜索目標(biāo)項(xiàng)目的頻繁2-項(xiàng)集,只挖掘目標(biāo)項(xiàng)目的二項(xiàng)關(guān)聯(lián)規(guī)則,減少連接操作,以此解決頻繁的連接操作造成的性能問(wèn)題。

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

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

1.2 DS Apriori算法偽代碼

改進(jìn)的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]

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

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

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

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

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

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

(4)剪枝步:根據(jù)先驗(yàn)性質(zhì),刪除子集不是頻繁1-項(xiàng)集的候選2-項(xiàng)集,得到剪枝后的C2,需要注意的是,這一步并沒(méi)有候選項(xiàng)從C2中刪除,因?yàn)檫@些候選的每個(gè)子集也都是頻繁的。

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

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

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

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

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

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

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

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

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

2 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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

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

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

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

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ī)則,在精準(zhǔn)度上一致。在業(yè)務(wù)要求下,Apriori、FP-growth算法產(chǎn)生了冗余的關(guān)聯(lián)規(guī)則,DS Apriori算法效率更高、更符合要求。

3 結(jié) 語(yǔ)

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