王桌芳 趙會(huì)軍 李 聰 趙 煜 劉 震

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

0 引 言

在數(shù)據(jù)挖掘領(lǐng)域，關(guān)聯(lián)規(guī)則挖掘是一種非常有效的分析手段，對(duì)于挖掘數(shù)據(jù)中本身存在的項(xiàng)集關(guān)聯(lián)屬性具有非常好的效果[1～2]。但是，現(xiàn)代社會(huì)中數(shù)據(jù)的容量呈現(xiàn)出爆炸式增長(zhǎng)，采用傳統(tǒng)的關(guān)聯(lián)規(guī)則解決思路對(duì)大數(shù)據(jù)的項(xiàng)集規(guī)則進(jìn)行發(fā)掘的效果并不理想，數(shù)據(jù)的執(zhí)行效率和實(shí)用性上存在明顯的弱點(diǎn)。同時(shí)，采用置信度方式構(gòu)建的規(guī)則挖掘算法框架對(duì)于用戶的關(guān)注度考慮得并不周全，這對(duì)于諸如微博、Web數(shù)據(jù)挖掘領(lǐng)域應(yīng)用效果不佳[3]。

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

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

1 興趣度模型描述

1.1 問題描述

置信度-支持度模型是關(guān)聯(lián)規(guī)則算法常用的評(píng)價(jià)準(zhǔn)則，這是一種強(qiáng)關(guān)聯(lián)形式，其主要關(guān)注的是信任度和支持度兩項(xiàng)指標(biāo)的最大化。但是，這種過于苛刻的強(qiáng)關(guān)聯(lián)規(guī)則對(duì)于用戶不一定都有意義，應(yīng)用效果不佳。例如：

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

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

(1)

在真實(shí)的超市交易過程中，餅干等商品信息和茶葉等商品信息之間可能存在負(fù)相關(guān)特性。這兩種商品信息的關(guān)聯(lián)規(guī)則的負(fù)相關(guān)性可表示為：

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

(2)

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

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

(3)

為獲得更佳準(zhǔn)確的用戶興趣度規(guī)則模型，有學(xué)者提出了基于約束條件設(shè)定的數(shù)據(jù)規(guī)則發(fā)現(xiàn)方法[10～11]：

(1) 約束模型的維和層次策略，對(duì)于數(shù)據(jù)的維度和層次進(jìn)行規(guī)則約束的設(shè)定，實(shí)現(xiàn)用戶規(guī)則的指定；

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

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

1.2 興趣模板模型構(gòu)建

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

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

模板模型一般包含前件和后件兩個(gè)主要組成部分，模版模型實(shí)例規(guī)則B1,B2,…,Bh?Bh+1表明上述規(guī)則與選取的興趣模版模型是相關(guān)聯(lián)的。因此，采用興趣模板模型可實(shí)現(xiàn)關(guān)聯(lián)規(guī)則的有效發(fā)掘，獲得更加有價(jià)值的數(shù)據(jù)信息。

一般而言，興趣模型具有多種不同形式，表達(dá)的含義也多種多樣。為實(shí)現(xiàn)模版表達(dá)含義的統(tǒng)一，這里選取文獻(xiàn)[12]所示形式進(jìn)行模版形式的改進(jìn)，具體定義形式為：

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

定義3如果數(shù)據(jù)用戶之間關(guān)系具有確定性，這種知識(shí)模版稱為知識(shí)模板，表示為：

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

(4)

式中：Sk與Vk也是用戶數(shù)據(jù)的屬性名表達(dá)形式。利用這兩種模板載體形式，可基于計(jì)算機(jī)處理形式進(jìn)行數(shù)據(jù)規(guī)則的挖掘。

1.3 差異概率興趣規(guī)則發(fā)掘模型

定義4興趣度指標(biāo)常用來對(duì)用戶數(shù)據(jù)的興趣關(guān)注度進(jìn)行量化度量，該指標(biāo)的主要優(yōu)勢(shì)可對(duì)知識(shí)點(diǎn)的可用性和新穎性進(jìn)行綜合考慮，獲得更為理想的模型表示形式。

興趣度模型主要包含兩個(gè)方面：客觀層面和主觀層面。前者模型主要是指關(guān)注程度的客觀興趣發(fā)掘，該指標(biāo)的取值主要與規(guī)則模型形式的前后件之間的依賴性指標(biāo)有關(guān)。當(dāng)前對(duì)于興趣度模型的研究主要集中客觀興趣度模型上，

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

(5)

(6)

2 差異概率興趣度關(guān)聯(lián)規(guī)則

2.1 算法原理

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

(7)

(8)

式中：頻繁項(xiàng)集的定義是高于設(shè)定閾值參數(shù)Suppmin的支持度項(xiàng)集，若關(guān)聯(lián)規(guī)則算法中滿足Supp(X?Y)≥Suppmin的規(guī)則項(xiàng)X?Y，且滿足Conf(X?Y)≥Confmin，則稱為關(guān)聯(lián)規(guī)則算法的關(guān)聯(lián)規(guī)則項(xiàng)是強(qiáng)關(guān)聯(lián)規(guī)則。

采用Web服務(wù)興趣度模型建立的Web關(guān)聯(lián)規(guī)則訪問模型主要包含兩個(gè)主要步驟：(1) 對(duì)于設(shè)計(jì)的關(guān)聯(lián)規(guī)則算法，利用事務(wù)集約簡(jiǎn)算法進(jìn)行頻繁項(xiàng)集的有效約簡(jiǎn)；(2) 基于興趣度因子對(duì)具有可信度和支持度的參數(shù)模型進(jìn)行優(yōu)化。具體過程如圖1所示。

圖1 改進(jìn)算法計(jì)算過程

2.2 頻繁項(xiàng)集約簡(jiǎn)

Apriori算法進(jìn)行關(guān)聯(lián)規(guī)則項(xiàng)的處理過程中，需要對(duì)D進(jìn)行多次反復(fù)掃描，可構(gòu)建1-頻繁項(xiàng)集L1，通過對(duì)1-項(xiàng)頻繁項(xiàng)集L1的改進(jìn)可獲得2-頻繁項(xiàng)集L2，經(jīng)過上述反復(fù)迭代過程，可得到算法所有的k-頻繁項(xiàng)集。但是上述多次反復(fù)掃描過程會(huì)增加算法的I/O計(jì)算復(fù)雜度，這會(huì)導(dǎo)致算法存在過多的頻繁項(xiàng)集，造成算法的計(jì)算效率大幅度下降。

(9)

算法1頻繁項(xiàng)集約簡(jiǎn)算法偽代碼

(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 興趣度模型融合

根據(jù)上述表述可知，頻繁項(xiàng)集約減過程算法得到的頻繁項(xiàng)集是置信度和支持度參數(shù)均最小的關(guān)聯(lián)規(guī)則項(xiàng)。但是實(shí)際上，如果僅僅選取置信度和支持度兩個(gè)參數(shù)指標(biāo)，并不能完全涵蓋用戶需求，甚至?xí)?dǎo)致用戶做出錯(cuò)誤的決策。對(duì)此，本文的解決思路是設(shè)計(jì)了一種差異化概率分析模型，首先給出交易集D，則其上的規(guī)則X?Y所具有的Web服務(wù)興趣參數(shù)指標(biāo)可計(jì)算為：

(10)

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

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

情形3：如果參數(shù)Interest是0，表明項(xiàng)集A和B之間的相互作用沒有相關(guān)性，此時(shí)獲得的關(guān)聯(lián)規(guī)則算法的關(guān)聯(lián)規(guī)則具有冗余性。

情形4：如果參數(shù)Interest→1，表明項(xiàng)集A和B之間的相互作用越緊密，此時(shí)的規(guī)則項(xiàng)X?Y對(duì)于數(shù)據(jù)的挖掘也越有意義。如果參數(shù)Interest→0，表明項(xiàng)集A和B之間的相互作用越稀疏，此時(shí)的規(guī)則項(xiàng)X?Y對(duì)于數(shù)據(jù)的挖掘也越?jīng)]有關(guān)聯(lián)性，相對(duì)于真實(shí)應(yīng)用場(chǎng)景意義不大。差異概率興趣度關(guān)聯(lián)規(guī)則挖掘算法偽代碼如算法2所示。

算法2差異概率興趣度關(guān)聯(lián)規(guī)則算法偽代碼

輸入：生成關(guān)聯(lián)規(guī)則算法的頻繁集Lk，算法的置信度最小閾值參數(shù)Confmin，算法的興趣度最小閾值參數(shù)intmin。

輸出：關(guān)聯(lián)規(guī)則算法的頻繁項(xiàng)集

For 所有k-頻繁項(xiàng)集lk,k≥2 do

H1={lk規(guī)則后件}

Callap_genrules(lk,H1);

end

Procedureap_genrules(lk,H1)

//Hm是m項(xiàng)目后件

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 實(shí)驗(yàn)分析

3.1 實(shí)驗(yàn)設(shè)置

為驗(yàn)證所提算法的有效性，選取四種已有的算法進(jìn)行對(duì)比：文獻(xiàn)[12]提出的光譜學(xué)習(xí)關(guān)聯(lián)規(guī)則算法(SL)、文獻(xiàn)[13]提出的高斯內(nèi)核均值關(guān)聯(lián)規(guī)則算法(SSKK)、文獻(xiàn)[14]提出的譜正則關(guān)聯(lián)規(guī)則算法(CCSR)和文獻(xiàn)[15]提出的度量約束均值關(guān)聯(lián)規(guī)則算法(MPCK)。選取的測(cè)試集是UCI測(cè)試集，該測(cè)試集共有8組數(shù)據(jù)集用于實(shí)驗(yàn)測(cè)試，該測(cè)試集中各含有4組Web數(shù)據(jù)集和真實(shí)數(shù)據(jù)集，如表1所示。

表1 實(shí)驗(yàn)數(shù)據(jù)集

表1參數(shù)設(shè)定中，tissue、parkinsons以及breast三種數(shù)據(jù)集均為醫(yī)學(xué)研究領(lǐng)域的Web數(shù)據(jù)集，ionosphere是物理研究領(lǐng)域的Web數(shù)據(jù)集，TDT2是文本研究領(lǐng)域的Web數(shù)據(jù)集，MNIST是數(shù)字模式識(shí)別領(lǐng)域的Web數(shù)據(jù)集，Letter是英文字母研究領(lǐng)域的Web數(shù)據(jù)集，CMU PIE是人臉模式識(shí)別領(lǐng)域的Web數(shù)據(jù)集。

算法測(cè)試中，選取的測(cè)試準(zhǔn)則是Rand準(zhǔn)則，具體形式為：

(11)

式中：TN為正確分類不同類對(duì)象的個(gè)數(shù)，TP為正確分類同類對(duì)象的個(gè)數(shù)。實(shí)驗(yàn)過程的硬件參數(shù)配置：cpu i7-6400，RAM 8 GB ddr4-2400，實(shí)驗(yàn)平臺(tái)的系統(tǒng)為Windows 10旗艦版。

3.2 實(shí)驗(yàn)結(jié)果

UCI集測(cè)試：4組UCI集上的5種標(biāo)簽數(shù)據(jù)挖掘算法實(shí)驗(yàn)對(duì)比結(jié)果如圖2所示。

(a) tissue集

(b) parkinsons集

(c) breast集

(d) ionosphere集圖2 UCI Web集實(shí)驗(yàn)結(jié)果對(duì)比

可以看出，在5種選取的對(duì)比算法中，本文算法除了在極少數(shù)數(shù)據(jù)集上因?yàn)榇嬖诘募s束較少造成算法性能稍差于SSKK和CCSR兩種對(duì)比算法外，在其他情形下均要優(yōu)于選取的對(duì)比算法。具體實(shí)驗(yàn)情況分析如下：(1) tissue集測(cè)試結(jié)果顯示，在約束數(shù)量為100～300參數(shù)設(shè)定情況下，本文算法與CCSR和SSKK兩種算法相比并無優(yōu)勢(shì)，但是當(dāng)約束數(shù)量大于300情況下，本文算法的Rand指標(biāo)最高。(2)parkinsons集和breast集測(cè)試結(jié)果顯示，在約束數(shù)量為100～700參數(shù)設(shè)定情況下，本文算法Rand指標(biāo)均高于選取的四種對(duì)比算法。(3) ionosphere集測(cè)試結(jié)果顯示，在約束約束數(shù)量為100～200參數(shù)設(shè)定情況下，本文算法與CCSR和SSKK兩種算法相比并無優(yōu)勢(shì)，但是當(dāng)約束數(shù)量大于200情況下，本文算法的Rand指標(biāo)最高。上述實(shí)驗(yàn)結(jié)果顯示，本文算法在正確分類不同類對(duì)象的個(gè)數(shù)以及正確分類同類對(duì)象的個(gè)數(shù)兩種情形的綜合實(shí)驗(yàn)指標(biāo)要優(yōu)于選取的對(duì)比算法。

4 結(jié) 語

本文提出一種基于Web服務(wù)興趣度度量函數(shù)的多類數(shù)據(jù)挖掘算法。采取差異概率興趣度量規(guī)則對(duì)關(guān)聯(lián)規(guī)則算法中的時(shí)序事務(wù)進(jìn)行估計(jì)和權(quán)重的預(yù)測(cè)；基于用戶興趣度進(jìn)行約束條件設(shè)計(jì)，實(shí)現(xiàn)數(shù)據(jù)挖掘關(guān)聯(lián)規(guī)則的精簡(jiǎn)；基于支持度函數(shù)和期望函數(shù)進(jìn)行事務(wù)項(xiàng)集的提取，結(jié)合事務(wù)項(xiàng)集的置信度對(duì)其規(guī)則進(jìn)行導(dǎo)出。結(jié)果顯示所提算法可有效提升Web服務(wù)數(shù)據(jù)挖掘算法的性能，對(duì)于降低用戶Web訪問復(fù)雜性具有非常好的效果。