多事務(wù)興趣度的度量方法*

閻 婷，吳文華，嚴(yán)麗娜，劉 晶

（國(guó)防科技大學(xué)信息通信學(xué)院試驗(yàn)訓(xùn)練基地，陜西 西安 710106）

0 引 言

常見(jiàn)的衡量關(guān)聯(lián)規(guī)則相關(guān)度的方法有基于最小支持度和最小信任度閾值的支持度-置信度框架、基于Piatetsky-Shapiro提出的PS公式。第二種度量公式能去除大部分不相關(guān)的或負(fù)相關(guān)的關(guān)聯(lián)規(guī)則，且有效簡(jiǎn)單，但在多事務(wù)興趣度度量方面存在一定缺陷[1]。因此，現(xiàn)提出一種可以對(duì)多事務(wù)興趣度進(jìn)行度量的多事務(wù)興趣度的度量方法，通過(guò)驗(yàn)證它是PS公式的擴(kuò)展。

1 問(wèn)題引入

例如，某一商場(chǎng)底層事務(wù)數(shù)據(jù)庫(kù)中購(gòu)買(mǎi)咖啡（事務(wù)C）、牛奶（事務(wù)D）、白糖（事務(wù)E）的統(tǒng)計(jì)況如圖1所示。

圖1 購(gòu)買(mǎi)咖啡、牛奶、白糖的統(tǒng)計(jì)

由 圖1可 得 結(jié) 果：p(C)=50%，p(D)=50%，P(D)P(E)=0，說(shuō)明事務(wù)C、D和E間的關(guān)聯(lián)規(guī)則是無(wú)趣的，但是顯然事務(wù)C和D、C和E、D和E、CD和E、CE和D、DE和C間均正相關(guān)，可見(jiàn)根據(jù)PS興趣度公式推出的結(jié)論是不正確的。由上例可以看出，PS公式具有局限性，尤其是在判斷二維以上關(guān)聯(lián)規(guī)則的情況下。為了解決這樣的問(wèn)題，根據(jù)力學(xué)平衡原理引入多事務(wù)興趣度度量的方法——多事務(wù)間誘導(dǎo)力的數(shù)學(xué)期望法。

2 多事務(wù)興趣度算法描述

2.1 相關(guān)概念

定義1：誘導(dǎo)力。認(rèn)為事務(wù)集S中的事務(wù)C1,C2,…,Cn是否同時(shí)出現(xiàn)是由某種力所決定的，把這種力命名為誘導(dǎo)力[2]，表示為：

定義2：逆項(xiàng)集。對(duì)事務(wù)集S的Cni個(gè)i項(xiàng)子集進(jìn)行任意排序，則第j項(xiàng)子集可表示為X(i,j)。設(shè)S(i,j)是X(i,j)與X(i,j)的所有元素的逆所組成集合的并集，即：

其中k∈(0,Cin)。

設(shè)Si是以S(i,j)為元素的集合，即：

為了方便，稱Si是事務(wù)集S的i項(xiàng)逆項(xiàng)集，把S(i,j)中的第k個(gè)元素表示為S(i,j,k)。

其中K稱為誘導(dǎo)系數(shù)，滿足以下條件[3]：

（1）K是常量，且K＞0；

（2）它的值因數(shù)據(jù)庫(kù)的改變和事務(wù)C1,C2,…,Cn個(gè)數(shù)的改變而改變，在同一數(shù)據(jù)庫(kù)中保持不變。

當(dāng)事務(wù)C1,C2,…,Cn相互獨(dú)立時(shí)，事務(wù)C1,C2,…,以誘導(dǎo)力公式為：

事務(wù)C1,C2,…,Cn所有誘導(dǎo)力的合力是事務(wù)集S中所有逆項(xiàng)集的誘導(dǎo)力數(shù)學(xué)期望之和，其中事務(wù)集S的所有逆項(xiàng)集共有Cn0+Cn1+…+Cin+…+Cnn-1+Cnn=2n個(gè)。

2.2 多事務(wù)興趣度公式推導(dǎo)

當(dāng)誘導(dǎo)力為0時(shí)，設(shè)f是事務(wù)C1,C2,…,Cn同時(shí)發(fā)生的正向誘導(dǎo)力。當(dāng)誘導(dǎo)力小于0時(shí)，f是事務(wù)C1,C2,…,Cn同時(shí)發(fā)生的負(fù)向誘導(dǎo)力。

設(shè)給定誘導(dǎo)力合力的最小誘導(dǎo)力為閾值δ，則當(dāng)誘導(dǎo)力合力小于閾值δ時(shí)，事務(wù)C1,C2,…,Cn正相關(guān)，即規(guī)則是有趣的；若誘導(dǎo)力合力大于閾值δ時(shí)，事務(wù)C1,C2,…,Cn負(fù)相關(guān)，即規(guī)則是無(wú)趣的；誘導(dǎo)力合力等于閾值δ，事務(wù)C1,C2,…,Cn不相關(guān)，即規(guī)則是無(wú)趣的。

將式（6）等號(hào)兩邊同除以K，式（6）轉(zhuǎn)化為：

其中：

多事務(wù)興趣度方法為式（7），有如下結(jié)論：

用戶也可以根據(jù)自己的主觀要求設(shè)定閾值進(jìn)行挖掘或者測(cè)量，令ε=δ/K，ε是最小興趣度的閾值。

3 算法應(yīng)用及實(shí)現(xiàn)

3.1 應(yīng)用

下面以多事務(wù)興趣度公式分析給出購(gòu)買(mǎi)咖啡（事務(wù)C）、牛奶（事務(wù)D）、白糖（事務(wù)E）的興趣度。根據(jù)多事務(wù)興趣度公式，求事務(wù)C、D、E的興趣度如下：

因?yàn)镻(CDE)=0.03＞ε=0.01，所以事務(wù)C、D、E是有興趣的。

3.2 實(shí)現(xiàn)

本算法采用VC++作為開(kāi)發(fā)環(huán)境進(jìn)行測(cè)試，SQL SERVER存放數(shù)據(jù)庫(kù)，且兩個(gè)字段對(duì)數(shù)據(jù)進(jìn)行存放。第一個(gè)字段存放記錄的編號(hào)（相當(dāng)于購(gòu)買(mǎi)商品時(shí)小票的流水號(hào)），第二個(gè)字段存放每一條記錄的所有商品名。采用Apriori算法挖掘頻繁項(xiàng)集（最小支持度為0.3），用多事務(wù)興趣度算法對(duì)挖掘出來(lái)的結(jié)果進(jìn)行度量，結(jié)果如圖2所示。

圖2 多事務(wù)興趣度度量結(jié)果

圖2的結(jié)果顯示，此方法不僅可以對(duì)二維關(guān)聯(lián)規(guī)則進(jìn)行度量，還可以對(duì)二維以上的關(guān)聯(lián)規(guī)則進(jìn)行度量。二維時(shí)，度量結(jié)果是PS公式的計(jì)算結(jié)果。所以，此法的適用性更強(qiáng)。

4 結(jié) 語(yǔ)

本文指出PS公式的缺陷和不足，引入逆項(xiàng)集和誘導(dǎo)力的概念，結(jié)合力學(xué)平衡原理等知識(shí)，提出了多事務(wù)客觀興趣度的度量方法。此方法綜合考慮了規(guī)則準(zhǔn)確度、相關(guān)度對(duì)規(guī)則興趣度的影響，是PS公式的一個(gè)擴(kuò)展。此方法不僅可以進(jìn)行自挖掘，也可以用來(lái)對(duì)挖掘的關(guān)聯(lián)規(guī)則進(jìn)行度量。