基于興趣度度量的多類差異數據關聯規則挖掘

王桌芳 趙會軍 李 聰 趙 煜 劉 震

(常州大學石油工程學院 江蘇 常州 213000)

0 引 言

在數據挖掘領域，關聯規則挖掘是一種非常有效的分析手段，對于挖掘數據中本身存在的項集關聯屬性具有非常好的效果[1～2]。但是，現代社會中數據的容量呈現出爆炸式增長，采用傳統的關聯規則解決思路對大數據的項集規則進行發掘的效果并不理想，數據的執行效率和實用性上存在明顯的弱點。同時，采用置信度方式構建的規則挖掘算法框架對于用戶的關注度考慮得并不周全，這對于諸如微博、Web數據挖掘領域應用效果不佳[3]。

對此，很多學者對于數據興趣發掘提出了很多的解決思路，目的是幫助用戶進行興趣規則的發現，提高數據的挖掘效果。這種算法設計思路主要根據用戶的關注領域，對用戶規則的興趣指標進行計算，并按照計算值進行排序提供給決策者進行決策參考[4]。目前的研究瓶頸主要集中在計算方式的高效性、概念定義的模糊性方面。當前，對于關聯規則領域的研究主要側重于以上方面，主觀興趣模型研究是一種有效的研究策略，其采用的是模版分析策略，目的是通過大數據分析獲得興趣度模型的規則模型[5]。同時，模版是一種有效的知識表達手段，對于興趣度模型的分析具有輔助效果。此外，有學者將Rule Cover分析策略同數據挖掘過程的興趣度模型進行結合，實現了模型效果的提升，獲得了數據挖掘過程的優勢互補，但是缺點是融合算法對于規則過濾的規則過于嚴格，導致規則的保留較少，關聯規則的效果不佳，主要原因如下[6～7]：(1) Rule Cover分析策略主要側重的是規則的普適性，而另一種融合算法則主要側重的是規則的特殊性保持。(2) Rule Cover分析策略所需的規則數量偏少，而另一種融合算法則主要側重的是多規則的數據挖掘，兩者之間存在典型的互斥性。學術界對于Rule Cover分析策略的研究相對比較成熟，而在興趣度模型研究上還不夠全面，可以提升的余地很大，并且從用戶需求角度看，興趣度模型研究的意義主要體現在下列兩個層面[8～9]：(1) 采用排序策略可提高算法的計算效率。因為對于挖掘出的數據特殊規則，如果不加處理地呈現給用戶，會增加用戶分析的計算復雜度，實際應用效果并不理想。(2) 特別是規則數目巨大時，用戶研究目的是能夠實現更加快速的知識信息發現，有助于提升數據發掘的目的性和針對性。因此，對于興趣度模型的研究，獲得更加完善的模型形式，對于提升關聯規則的發掘效果具有非常重要的意義。

本文針對上述問題，提出了一種有效的Web數據挖掘改進策略。針對Web用戶數據挖掘計算不確定性問題，提出了一種具有更佳一致度的興趣度模型；對興趣度模型在單模板情形下進行有效添加，實現了對興趣模型的特殊處理；對于用戶模版能夠提供有效的支持手段，并且能夠更加豐富模型中用戶層面的有效性定義。

1 興趣度模型描述

1.1 問題描述

置信度-支持度模型是關聯規則算法常用的評價準則，這是一種強關聯形式，其主要關注的是信任度和支持度兩項指標的最大化。但是，這種過于苛刻的強關聯規則對于用戶不一定都有意義，應用效果不佳。例如：

選取Web網上超市數據庫作為研究對象，假設數據庫記錄中，存在2 000組事務數據信息，其中1 600組中含有餅干等商品信息，1 200組含有茶葉等商品信息，960個既含有餅干商品信息又含有茶葉等商品信息。這里取支持度參數的最小值supmin為30%，信任度參數的最小值confmin為40%，由此可得規則形式為：

買餅干?買茶葉{Supp=48%,Conf=60%}

(1)

在真實的超市交易過程中，餅干等商品信息和茶葉等商品信息之間可能存在負相關特性。這兩種商品信息的關聯規則的負相關性可表示為：

買餅干?不買茶葉{Supp=32%,Conf=40%}

(2)

分析上述關聯規則模型可知，負相關性關聯規則形式與真實超市交易情形更加貼切。因此，對于給定閾值，獲得的兩條關聯規則之間存在矛盾性。此外，如果給定閾值參數設定過大，會導致規則信息的遺漏，不利于數據挖掘過程算法性能提升。例如，在真實的超市交易過程中，會保存有客人的年齡、性別等個人信息，對于不同人群特征，可進行相關信息的數據發掘，例如，對于女性客戶購買化妝品的相關信息挖掘，設定supmin為50%，confmin為70%，可得如下形式的關聯規則模型：

女性?化妝品{Supp=55%,Conf=79%}

(3)

為獲得更佳準確的用戶興趣度規則模型，有學者提出了基于約束條件設定的數據規則發現方法[10～11]：

(1) 約束模型的維和層次策略，對于數據的維度和層次進行規則約束的設定，實現用戶規則的指定；

(2) 用戶規則約束的數據分析方法，可以對相關數據進行具體指定，而無需對全部數據進行處理。

(3) 用戶數據的規則分析方法，目的是獲得所需要的數據類型。常采用的方法是設定模版概念定義，可對用戶的規則興趣進行設定。如果數據規則與模板之間存在匹配關系，則表明數據是感興趣的。

1.2 興趣模板模型構建

興趣模型的主觀表達中，常采用的是模版表達方式，可對用戶表達含義進行有效的模型表示。參照文獻[5]對于模板模型的定義形式，可給出如下定義形式：

定義1Web服務興趣模型形式為A1,A2,…,AK?Ak+1，模型中Ai是數據模型的類名屬性，比如，對于表達模型C+、C*，C+是多類模型C的實例表達形式，C*是零類模型C的實例表達形式，可表示為模版。

模板模型一般包含前件和后件兩個主要組成部分，模版模型實例規則B1,B2,…,Bh?Bh+1表明上述規則與選取的興趣模版模型是相關聯的。因此，采用興趣模板模型可實現關聯規則的有效發掘，獲得更加有價值的數據信息。

一般而言，興趣模型具有多種不同形式，表達的含義也多種多樣。為實現模版表達含義的統一，這里選取文獻[12]所示形式進行模版形式的改進，具體定義形式為：

定義2如果數據用戶之間關系具有不確定性，這種知識模版稱為印象模板，表示為gi=[S1,S2,…,Sm]，其中參數Sk是用戶數據的屬性名表達形式。

定義3如果數據用戶之間關系具有確定性，這種知識模版稱為知識模板，表示為：

rpc=[S1,S2,…,Sm?V1,V2,…,Vg]

(4)

式中：Sk與Vk也是用戶數據的屬性名表達形式。利用這兩種模板載體形式，可基于計算機處理形式進行數據規則的挖掘。

1.3 差異概率興趣規則發掘模型

定義4興趣度指標常用來對用戶數據的興趣關注度進行量化度量，該指標的主要優勢可對知識點的可用性和新穎性進行綜合考慮，獲得更為理想的模型表示形式。

興趣度模型主要包含兩個方面：客觀層面和主觀層面。前者模型主要是指關注程度的客觀興趣發掘，該指標的取值主要與規則模型形式的前后件之間的依賴性指標有關。當前對于興趣度模型的研究主要集中客觀興趣度模型上，

對于1.1節問題描述中給出的餅干和茶葉超市交易商品信息數據庫中的餅干和茶葉的交易信息關聯情況可知，傳統的客觀興趣度模型有可能會產生與真實情況不相符的規則模型。但是具體分析上述商品交易信息可知，餅干和茶葉的相關性交易信任度為60%。該數據指標表明，如果客人在超市中購買了餅干則該客人同時購買茶葉的可能性比較大，在真實情形下，這兩者之間并不是存在正相關關聯性，對于產生的“買餅干?買茶葉”的規則信息，并未真實反映出客人購買茶葉的變化趨勢。對此，這里提出一種差異化的數據規則興趣定義形式，目的是指導數據規則的挖掘過程，規則X?Y給出的數據之間的關聯規則的準確性取決于兩者之間的置信度指標，這里定義X?Y情況的置信度計算形式：

(5)

(6)

2 差異概率興趣度關聯規則

2.1 算法原理

Web服務模型I={i1,i2,…,im}是m組具有不同形式項目的模型集，參數m是模型集的尺寸參數，如果m=k,則稱其為k-項集，且存在1≤k≤m。符號D是研究對象的事項數據塊，每一事務選項對應的是其標識TID，并且該標識具有唯一性，形式為D={T1,T2,…,Tm}。對于每個事務T，其為項集I內的子集，也就是滿足形式T?I。關聯規則的形式為R：X?Y，其中：參數X?I、Y?I且存在X∩Y=?。參數X是關聯規則算法的條件，參數Y是關聯規則算法的結果輸出。關聯規則算法的規則R所具有的置信度參數形式是Conf(X?Y)，支持度參數形式是Supp(X?Y)。支持度參數反映的是事項集內同時含有X和Y的事項集比例。置信度參數反映的是事項集內存在X，并且在事項處理過程中產生Y的幾率。具體形式為：

(7)

(8)

式中：頻繁項集的定義是高于設定閾值參數Suppmin的支持度項集，若關聯規則算法中滿足Supp(X?Y)≥Suppmin的規則項X?Y，且滿足Conf(X?Y)≥Confmin，則稱為關聯規則算法的關聯規則項是強關聯規則。

采用Web服務興趣度模型建立的Web關聯規則訪問模型主要包含兩個主要步驟：(1) 對于設計的關聯規則算法，利用事務集約簡算法進行頻繁項集的有效約簡；(2) 基于興趣度因子對具有可信度和支持度的參數模型進行優化。具體過程如圖1所示。

圖1 改進算法計算過程

2.2 頻繁項集約簡

Apriori算法進行關聯規則項的處理過程中，需要對D進行多次反復掃描，可構建1-頻繁項集L1，通過對1-項頻繁項集L1的改進可獲得2-頻繁項集L2，經過上述反復迭代過程，可得到算法所有的k-頻繁項集。但是上述多次反復掃描過程會增加算法的I/O計算復雜度，這會導致算法存在過多的頻繁項集，造成算法的計算效率大幅度下降。

(9)

算法1頻繁項集約簡算法偽代碼

(1)L1={large1-itemsets}；

(3) for(k=2；Lk-1≠?；k++)do begin

(4)Ck=apriori-gen(Lk-1)

(7)Ct={c∈Ck|(c-c[k])}；

(8) for allcandidatesc∈Ctdo begin

(9)c.count++；

(11) end；

(12)Lk={c∈Ck|c.count≥minsupp}；

(13) end；

(14)Answer=UkLk；

2.3 興趣度模型融合

根據上述表述可知，頻繁項集約減過程算法得到的頻繁項集是置信度和支持度參數均最小的關聯規則項。但是實際上，如果僅僅選取置信度和支持度兩個參數指標，并不能完全涵蓋用戶需求，甚至會導致用戶做出錯誤的決策。對此，本文的解決思路是設計了一種差異化概率分析模型，首先給出交易集D，則其上的規則X?Y所具有的Web服務興趣參數指標可計算為：

(10)

情形1：如果參數Interest是正值，表明項集A和B之間的相互作用具有積極效應，是一種正相關性關系屬性。如果Interest=1，則存在關系P(AB)=P(A)P(B)，表明在事務集中項集A和B之間的出現具有同步性。

情形2：如果參數Interest是負值，表明項集A和B之間的相互作用具有抑制效應，是一種正相關性關系屬性。如果Interest=-1，則存在關系P(AB)=P(A)，表明在事務集中項集A和B之間的出現具有異步性。

情形3：如果參數Interest是0，表明項集A和B之間的相互作用沒有相關性，此時獲得的關聯規則算法的關聯規則具有冗余性。

情形4：如果參數Interest→1，表明項集A和B之間的相互作用越緊密，此時的規則項X?Y對于數據的挖掘也越有意義。如果參數Interest→0，表明項集A和B之間的相互作用越稀疏，此時的規則項X?Y對于數據的挖掘也越沒有關聯性，相對于真實應用場景意義不大。差異概率興趣度關聯規則挖掘算法偽代碼如算法2所示。

算法2差異概率興趣度關聯規則算法偽代碼

輸入：生成關聯規則算法的頻繁集Lk，算法的置信度最小閾值參數Confmin，算法的興趣度最小閾值參數intmin。

輸出：關聯規則算法的頻繁項集

For 所有k-頻繁項集lk,k≥2 do

H1={lk規則后件}

Callap_genrules(lk,H1);

end

Procedureap_genrules(lk,H1)

//Hm是m項目后件

Ifk>m+1 then

Hm+1=apriori-gen(Hm)；

For allhm+1∈Hm+1do

c=s(lk)/s(lk-hm+1)；

Ifc

If |Int|>Intminthen

outputrule(lk-hm+1)→hm+1；

supp=s(lk)，Conf=c，Interest=Int；

End

Callap_genrules(lk,Hm+1)

End

3 實驗分析

3.1 實驗設置

為驗證所提算法的有效性，選取四種已有的算法進行對比：文獻[12]提出的光譜學習關聯規則算法(SL)、文獻[13]提出的高斯內核均值關聯規則算法(SSKK)、文獻[14]提出的譜正則關聯規則算法(CCSR)和文獻[15]提出的度量約束均值關聯規則算法(MPCK)。選取的測試集是UCI測試集，該測試集共有8組數據集用于實驗測試，該測試集中各含有4組Web數據集和真實數據集，如表1所示。

表1 實驗數據集

表1參數設定中，tissue、parkinsons以及breast三種數據集均為醫學研究領域的Web數據集，ionosphere是物理研究領域的Web數據集，TDT2是文本研究領域的Web數據集，MNIST是數字模式識別領域的Web數據集，Letter是英文字母研究領域的Web數據集，CMU PIE是人臉模式識別領域的Web數據集。

算法測試中，選取的測試準則是Rand準則，具體形式為：

(11)

式中：TN為正確分類不同類對象的個數，TP為正確分類同類對象的個數。實驗過程的硬件參數配置：cpu i7-6400，RAM 8 GB ddr4-2400，實驗平臺的系統為Windows 10旗艦版。

3.2 實驗結果

UCI集測試：4組UCI集上的5種標簽數據挖掘算法實驗對比結果如圖2所示。

(a) tissue集

(b) parkinsons集

(c) breast集

(d) ionosphere集圖2 UCI Web集實驗結果對比

可以看出，在5種選取的對比算法中，本文算法除了在極少數數據集上因為存在的約束較少造成算法性能稍差于SSKK和CCSR兩種對比算法外，在其他情形下均要優于選取的對比算法。具體實驗情況分析如下：(1) tissue集測試結果顯示，在約束數量為100～300參數設定情況下，本文算法與CCSR和SSKK兩種算法相比并無優勢，但是當約束數量大于300情況下，本文算法的Rand指標最高。(2)parkinsons集和breast集測試結果顯示，在約束數量為100～700參數設定情況下，本文算法Rand指標均高于選取的四種對比算法。(3) ionosphere集測試結果顯示，在約束約束數量為100～200參數設定情況下，本文算法與CCSR和SSKK兩種算法相比并無優勢，但是當約束數量大于200情況下，本文算法的Rand指標最高。上述實驗結果顯示，本文算法在正確分類不同類對象的個數以及正確分類同類對象的個數兩種情形的綜合實驗指標要優于選取的對比算法。

4 結 語

本文提出一種基于Web服務興趣度度量函數的多類數據挖掘算法。采取差異概率興趣度量規則對關聯規則算法中的時序事務進行估計和權重的預測；基于用戶興趣度進行約束條件設計，實現數據挖掘關聯規則的精簡；基于支持度函數和期望函數進行事務項集的提取，結合事務項集的置信度對其規則進行導出。結果顯示所提算法可有效提升Web服務數據挖掘算法的性能，對于降低用戶Web訪問復雜性具有非常好的效果。