基于效用函數度量的多維效用關聯規則挖掘

王仲君 楊文芳

(武漢理工大學理學院 湖北 武漢 430700)

基于效用函數度量的多維效用關聯規則挖掘

王仲君 楊文芳

(武漢理工大學理學院 湖北 武漢 430700)

傳統的多維關聯規則挖掘過程通常以規則出現的頻率來判定規則的有效性，并以支持度與置信度作為度量標準。這種挖掘方法只考慮規則間的統計相關性，忽略了規則自身的語義重要性，即規則能夠為商家帶來的期望效益。因此在多維關聯規則挖掘過程中，引入效用函數作為統計相關性與語義重要性的綜合度量指標。效用函數主要從潛在機會、購買概率、期望效益三個方面來度量規則的有效性，潛在機會與購買概率表示統計相關性，期望效益表示語義重要性。結果表明，以效用函數作為度量挖掘出的規則既符合客觀上要求的較高頻率，又具有主觀上期望的較高效益。

效用函數度量 語義重要性 統計相關性

0 引 言

關聯規則作為數據挖掘中最重要的一個分支，最早是由Agrawal在分析市場購物籃數據時提出[1]并用于描述商品間的關聯性，現已被應用于網絡日志分析、網絡安全等多個行業。隨著互聯網行業的快速發展，海量數據使得挖掘的難度增大。因此，近年來，人們越來越多地關注從多個維度對關聯規則進行挖掘，即多維關聯規則挖掘。

Kamber等最先提出將數據立方體應用于關聯規則挖掘中，他認為數據立方體可以利用數據倉庫的結構預先計算聚集值，從而提高挖掘速度[2]；Imielinski等提出將聯機分析處理技術與關聯規則挖掘共同應用于模式識別中[3]；Messaoud等提出針對用戶需求將度量一般化，不再局限于計數度量[4]；Bawane等提出在多維關聯規則挖掘中將OLAP技術與Apriori算法相結合[5]。國內相關的研究有胡孔法、陳崚等提出在挖掘過程中數據立方體的存儲與物化問題[6]；王穎等提出通過減少掃描數據庫次數、降低候選項集計算復雜度以及減少預剪枝步驟計算量等途徑改進Apriori算法的執行效率[7]；李海磊等提出一種數據兩方垂直分布條件下，結合數據立方體技術的多維關聯規則挖掘算法[8]；Lee提出基于效用函數對關聯規則進行挖掘[9]。雖然國內外關于多維關聯規則挖掘的相關研究較多，但是，這些研究基本都是基于頻率來判定規則的有效性，考慮規則在統計學意義上的相關性，而忽略了規則能帶來的期望效益。

關聯規則挖掘的目的在于將挖掘出來的規則應用于實際的決策之中，因此本文在對多維關聯規則挖掘的過程中，綜合考慮規則的潛在用戶、購買概率、期望效益三個指標，定義效用函數度量作為判定規則有效性的重要指標。效用函數度量是關于支持度置信度的函數，不僅考慮統計相關性因素來判定規則的客觀有效性，而且引入語義重要性因素來判定規則的主觀適用性，是對傳統度量方法的提升與改進，使得挖掘出的規則能夠從實際意義上為決策者提供決策依據，這種規則稱為效用關聯規則。

1 效用函數度量及多維效用關聯規則挖掘Apriori算法

本文在對不同客戶群體的消費行為進行分析時，首先利用RFM模型對客戶價值進行分類，隨后通過定義效用函數度量作為判定規則有效性的標準，在此基礎上結合Apriori算法對多維數據模型中存在的效用規則進行挖掘。

1.1 RFM模型

表1 RFM模型客戶分類標準

可以看出，通過RFM模型對客戶分類過后，決策者可以針對不同的客戶群體制定不同的營銷策略，一方面提高營銷策略的成功率，另一方面可以節約成本。因此，本文在對客戶價值進行分類之后，對每一類客戶的效用規則進行挖掘。在挖掘過程中，通過構建基于潛在客戶、購買概率、期望效益三個指標的效用函數度量，以效用函數度量作為規則有效性的判定標準。

1.2 效用規則度量與多維效用關聯規則挖掘

在傳統的關聯規則挖掘過程中，置信度與支持度是判定規則有效性的重要度量標準，支持度的大小可以判定模式是否為頻繁模式，再以置信度的大小判定頻繁模式是否能生成有效規則。這種挖掘方式依賴于模式出現的次數，充分考慮規則的統計相關性，能挖掘出頻繁出現的模式并生成規則。然而，這種方式容易忽略出現頻率小但具有高效益的規則。因此，本文引入效用規則的概念，綜合考慮規則的統計相關性與語義重要性的效用函數度量作為規則有效性的判定標準，將效用函數度量值大于最小閾值的規則定義為效用規則。

(1) 支持度與置信度度量

在傳統關聯規則挖掘中，只有支持度與置信度同時大于最小閾值的模式才能作為頻繁模式被挖掘。在統計學意義上，支持度與置信度表示的是兩種概率，關聯規則R：{X,Y?Z}的支持度表示的是模式(X,Y,Z)同時出現的概率[11]，置信度Conf表示的是(X,Y)的客戶群中選擇產品Z概率。其計算公式如下：

(1)

(2)

其中:當X、Y兩個維度都是關于客戶時，|D|表示總的客戶數，C(X,Y)表示X、Y代表的群體的總人數，C(X,Y,Z)表示該群體中購買Z產品的人數。

這種度量值的計算方式只考慮到統計意義上的強相關性，忽略了模式的語義相關性，即將生成的規則應用于商業營銷之后能夠給商家帶來的效益值。因此，本文提出效用函數度量的概念，綜合考慮規則的統計相關性和語義重要性來判定規則的有效性。效用函數度量是關于傳統的支持度和置信度度量的修正函數，在考慮了傳統的支持度和置信度度量的基礎上，又進一步考慮規則可能會給商家帶來的期望效益。

(2) 構建效用函數度量

效用函數大多數時候是用來表示消費者在消費中所獲得的效用與所消費的商品組合之間數量關系的函數，以衡量消費者從消費既定的商品組合中所獲得滿足的程度[12]。本文中，將效用函數表示為商家在銷售活動中獲得的效用，主要從潛在機會、購買概率、期望效益三個方面來定義，多維關聯規則R：{X,Y?Z}的效用函數度量U(R)表示為：

U(R)=Opp(R)×Prob(R)×Eff(R)

(3)

其中:潛在機會OPP、購買概率Prob代表統計相關性。潛在機會是指可以應用營銷的對象數，即規則對應的潛在客戶數量：

Opp(R)=|D|×sup(X,Y)-|D|×sup({X,Y?Z})

(4)

購買概率是指當企業向某客戶群體推銷產品時，該產品會被接受的概率值，可以用現有購物籃數據中的經驗概率代替：

(5)

規則產生的期望效益代表語義重要性，期望效益是指規則對效益值的影響，在零售業中可以表示為交易額的增加量，可以定義為：

Eff(R)=AVG(qty(Z,Ti))×price(Z(Ti))=

AVG(qty(Z,Ti))×price(Z)

(6)

最后得到規則的效用函數為：

U(R)= (sup(X,Y)-sup{R})×conf({R})×

|D|×AVG(qty(Z,Ti))×price(Z)=

AVG(qty(Z,Ti))×price(Z)

(7)

效用函數一方面與傳統的支持度和置信度度量緊密相關，另一方面又充分考慮了規則可能會給商家帶來的期望效益，使得挖掘出的規則不僅能在客觀上保證模式的頻繁性，同時也能在主觀上保證了規則的實用性。因此，這種計算方式比傳統方法中只考慮規則出現的次數更加合理。

1.3 多維效用關聯規則挖掘

多維效用關聯規則挖掘同樣以聯機分析處理技術OLAP為依托，首先在Java中的開源項目Mondrian中構建多維數據模型，然后利用MDX查詢語句計算數據立方體中聚集值C(X,Y,Z)并存儲，最后利用OLAP技術對數據立方體中的聚集值進行查找計算[14]。

在用Apriori算法挖掘時，不再用傳統的支持度計數進行剪枝，而是對購買概率為0或者1的規則進行剪枝，因為當Prob=0或Prob=1時，規則的效用U(R)=0。由于算法過程中不考慮用計數值C進行剪枝，而是根據人群購買產品的概率，因此，本文忽略頻繁一項集的生成過程，直接對以職業或客戶價值類別維度與產品維度組合產生的候選2-項集(Vi,Pk)與(Rj,Pk)進行挖掘。

具體步驟為，第一步：生成候選集C2,將各個維度的屬性值作為2-候選集的子集；將Prob≠0且Prob≠1的項集放入頻繁2-項集F1。第二步：進行循環迭代，根據(k-1)-頻繁項集生成k-候選集，再根據k-候選集生成k-頻繁項集。第三步：將效用值大于最小效用值閾值的頻繁項集生成多維效用關聯規則。具體算法如下。

算法名稱：多維關聯規則挖掘算法

輸入: 數據立方體C,V,M,P,min_sup,min_uti

輸出:L

1. k=1,L=φ

2. C2={(Vi,Pk),(Rj,Pk)}，

3. foreach A∈C2,if prob(A)≠0&prob(A)≠1 then F2=F2∪{A}

4. while F2≠φ

k=k+1

Ck=Fk-1×Fk-1

foreach A∈Ck,

if prob(A)≠0&prob(A)≠1

Fk=Fk∪{A}

foreach B∈Fk,

if uti(B)>min_uti(B)

L=L∪{B/P?P}

end

Vi、Rj、Pk分別表示職業、客戶價值、產品維度的屬性值。其中,在生成Ck的過程中，Fk-1×Fk-1表示將Fk-1中滿足一下兩個條件的項集聯合：① 有k-2個相同項集；② 不相同的兩個項集分別屬于不同的維度。如：{V5,M12},{M12,P28}可以聯合生成{V5,M12,P28}，而{V4,M12},{V5,M12}聯合生成的{V4,V5,M12}不能作為候選集，因為，V4、V5屬于同一個維度。

在效用關聯規則挖掘過程中，利用購買概率對效用函數的影響進行剪枝，通過剪枝策略可以有效地減少數據立方體的掃描次數，從而降低算法復雜度。將效用值作為規則的度量標準，可以使挖掘出的規則更加能滿足決策者的需求。

2 實證分析

本文的實證部分以購物籃數據為例，對不同客戶群體的消費行為模式進行挖掘。對比分析以支持度與置信度為度量的傳統方法和以效用函數度量作為標準的改進方法的計算過程以及挖掘結果。

2.1 數據背景

本文以某商場6年來547名忠實用戶的購買記錄作為數據，共計18萬條，該數據是在”數據堂”網站上購買獲得。在挖掘之前，首先通過RFM模型對大量的客戶進行分群。由于不同職業的人群在購買行為上有較大的差距，并且RFM模型在對客戶分類時只考慮客戶的消費行為，而忽略了其他信息，所以根據數據特征，增加職業維度，將不同價值的客戶群根據職業的不同再進行細分，使得挖掘出的規則更具準確性和針對性。

在購物籃數據挖掘過程中，購買量和銷售額始終是人們關注的重要指標，是用來判定規則有效性的主要標準，該數據中各產品總銷售額與總銷售量占比如表2所示。

表2各產品總銷售額與總銷售量占比

表2對比顯示了數據中28種商品各自的購買量amount和銷售額cost分別在總交易數量和總交易額中所占的比例，氣泡的大小代表比值的大小。不難發現飲料、零食和副食品這些日常的必需品總交易量占比很大，但總交易額占比很??；相反地，化妝品、珠寶首飾、皮具和手表這類非日常用品雖然總交易量很小，總交易額卻比較大。

由于商品在用途上的差異導致了購買量與交易額的量級差異。然而，在用傳統挖掘方法對關聯規則挖掘的過程中，只是以購買概率作為度量值計算基礎，這就導致在挖掘過程中在很大程度上受到交易量的影響，而忽略了交易額這一重要信息與潛在用戶數量。因此，在對關聯規則進行挖掘過程需要引入效用函數度量，使得挖掘到的規則不僅僅只受銷售量這一因素的影響，還能綜合考慮多種因素，具有更高的效用性，使得挖掘出的規則同時具有較高統計相關性與語義重要性。

2.2 傳統方法與改進方法對比分析

傳統方法在對購物籃數據處理的過程中，只考慮模式出現的次數，而忽略了模式本身的效用性，同時也忽略了商品本身存在的量級差。以購物籃數據的特點選取有代表性的部分數據，對傳統的多維關聯規則挖掘以及效用關聯規則挖掘進行對比。為了便于分析，所取的代表性數據只涉及“一般價值客戶”這一類客戶，其部分購買記錄如表3所示。

表3 “一般價值客戶”部分購買數據

表3共涉及到5名“一般價值客戶”。其中，4名屬于第一類職業，1名屬于第二類職業，表4顯示的是涉及到的四類產品的平均價格。

表4 商品價格(元)

分別用傳統方法與改進后的方法對規則進行挖掘，兩種方法的計算過程如表5所示。

表5 傳統方法與改進方法結果對比

表中R1、R2、R3、R4表示如下四種規則:

R1={一般價值客戶∧vocation=1}?藥品保健品；

R2={一般價值客戶∧vocation=1}?手工藝品；

R3={一般價值客戶∧vocation=1}?沖調飲品；

R4={一般價值客戶∧vocation=1}?奢侈品。

表中，方框標出的是大于最小閾值的規則度量值?？梢钥闯觯詡鹘y的支持度、置信度作為度量得到R1、R3為有效規則；以效用作為度量則得到R1、R4為有效規則。

對比分析用傳統多維關聯規則挖掘方法與多維效用關聯規則挖掘方法，將兩種方法挖掘出的前100條規則相關的產品進行計數，結果如表6-表7所示。

表6 改進方法挖掘結果

表7 傳統方法挖掘結果

表中，N表示與該產品相關的有效規則的數量。結果顯示，根據傳統的多維關聯規則挖掘方法得到的規則，大部分集中于交易量很大的日常生活用品，而根據多維效用關聯規則挖掘方法在綜合考慮到多方面的因素后，挖掘出的規則主要集中于奢侈品、珠寶、保健品等。其中，奢侈品交易量不高，但價格比較高；珠寶的交易量與價格在所有商品中都是屬于中等水平；保健品交易量大，且價格不是很低。而飲料零食這類日用產品雖然交易量高，但是價格太低，并且由于購買概率很大、潛在客戶較少，導致相關規則的效用值低于最小閾值。

傳統方法在挖掘過程中很大程度上考慮模式出現的頻率，這使得挖掘出的模式在客觀上具有很強的統計相關性，但是在主觀上并非具有很強的實用性。而改進后的方法的優點在于：

(1) 在計算C(R)的過程中(如模式R1)，將用戶多次購買同一個產品的行為計數為1，保證單個客戶的行為不會過度影響客戶群的行為模式，同時，在計算效益值Eff(R)時將購買數量求和，保證客戶的特殊購買行為不會被忽略。

(2) 同時引進機會、概率兩個概念對統計相關性進行度量，統計相關性不會隨著購買概率的增大不斷增大，因為隨著購買概率的增大，潛在機會降低。如模式R3，購買率為1的同時也導致潛在客戶為0的情況，說明規則適用性不強。

(3) 引進規則效益度量，使得出現頻率很低而效益值很大的模式不會被忽略。如R4，由于商品自身屬性不同，奢侈品的購買量很小，但是效益值很大，導致最終計算的效用度量值增大，從而作為效用模式被挖掘出來。

3 結 語

本文在傳統多維關聯規則挖掘方法的基礎上，提出多維效用關聯規則挖掘方法。在衡量規則有效性時，該方法不再以項目出現的頻率作為單一標準，而是采用同時考慮項目出現頻率、用戶對規則主觀興趣度的綜合標準。多維效用規則挖掘的核心是效用函數，本文在構建效用函數的過程中，以潛在機會、購買概率度量規則的統計相關性，以期望效益度量規則的語義重要性。

實證結果表明，通過定義期望效益對用戶的主觀興趣度進行量化，能夠使得出現頻率不高而效益值很大的規則不被忽略；通過引進機會、概率兩個概念對統計相關性進行度量，使得統計相關性不會隨著購買概率的增大而不斷增大；將效用函數作為規則的度量標準后，挖掘出的規則不再集中于需求量高的日用品，而更偏向于多樣性產品。

多維效用關聯規則的優點在于結合了商家的需求，在挖掘的過程中增加了主觀興趣因素，使得挖掘的規則不僅僅是客觀有效，還能給商家提供更完善的決策依據。這種方法不僅可以應用于購物籃數據分析，還可以應用于文本數據挖掘、電信行業數據挖掘等多個領域。

[1] Agrawal R,Imielinski T,Swami A.Mining Association Rules between Sets of Items in Large Databases[C]//Proceedings of the ACM SIGMOD International Conference on Management of Data,Washington,D.C.,USA:ACM Press,1993:207-216.

[2] Kamber M,Han J,Chiang J.Metarule-Guided Mining of Multi-Dimensional Association Rules Using Data Cubes[C]//Proceedings of the 3rd International Conference on Knowledge Discovery and Data Mining,Newport Beach,CA,USA:The AAAI Press,1997:207-210.

[3] Imielinski T,Khachiyan L,Abdulghani A.Cubegrades:Generalizing Association Rules[J].Data Mining and Knowledge Discovery,2002,6(3):219-258.

[4] Messaoud R B,Rabaséda S L,Boussaid O,et al.Enhanced mining of association rules from data cubes[C]//Proceedings of the 9th ACM international workshop on Data warehousing and OLAP.ACM,2006:11-18.

[5] Bawane G R,Deshkar P.Integration of OLAP and association rule mining[C]//Innovations in Information, Embedded and Communication Systems,2015 International Conference on.IEEE,2015:1-4.

[6] 胡孔法,陳崚,趙茂先,等.DHMC:一種有效的高維Cube并行分布式存儲結構[J].計算機研究與發展,2007,44(12):2098-2105.

[7] 王穎.基于數據倉庫的聯機分析處理探討[J].教育教學論壇,2014(38):239-240.

[8] 李海磊,王晗,孔令富,等.一種基于數據兩方垂直分布的多維關聯規則挖掘算法[J].計算機應用與軟件,2014,31(1):18-21,80.

[9] Lee D,Park S H,Moon S.Utility-based association rule mining:A marketing solution for cross-selling[J].Expert Systems with applications,2013,40(7):2715-2725.

[10] Hughes A M.Strategic database marketing[M].Chicago:Probus Publishing Company,1994.

[11] Tan Pangning,Steinbach M,Kumar V.數據挖掘導論[M].北京:人民郵電出版社,2006.

[12] 張堯庭,陳慧玉.效用函數及優化[M].科學出版社,2000.

[13] 張磊,夏士雄,周勇,等.基于語義相關性的關聯規則挖掘研究[J].東南大學學報(英文版),2008,24(3):358-360.

[14] Rizzi S,Golfarelli M,Graziani S,et al.An OLAM Operator for Multi-Dimensional Shrink[J].International Journal of Data Warehousing and Mining,2015,11(3):68-97.

MININGMULTIDIMENSIONALUTILITYASSOCIATIONRULESBASEDONUTILITYFUNCTIONMEASUREMENT

Wang Zhongjun Yang Wenfang

(CollegeofScience,WuhanUniversityofTechnology,Wuhan430700,Hubei,China)

The traditional multidimensional association rule mining determines the validity of rules by the rule’s frequency. And it takes support and confidence as measurement standards. This mining method only considers the statistical correlation between rules and ignores the semantic importance which is the effectiveness that the rules can bring. In this paper, we introduce the utility function as a comprehensive measure of statistical correlation and semantic significance. The utility function mainly measures the effectiveness of the rule from three aspects: opportunity, probability and effectiveness. Opportunity and probability represents the statistical correlation, effectiveness represents the semantic significance. The results show that the rules mined by the utility function not only meet higher frequency of objective requirements, but also have the subjective expectations of higher effectiveness.

Utility function measurement Semantic significance Statistical correlation

2016-12-31。國家自然科學基金面上項目(71671135)。王仲君，教授，主研領域：復雜系統，數據挖掘。楊文芳，碩士生。

TP3

A

10.3969/j.issn.1000-386x.2017.12.007