段巧靈++李芬++張莉

摘要：隨著多數(shù)據(jù)庫技術(shù)的快速發(fā)展，在多個數(shù)據(jù)庫中獲取有效信息顯得尤為重要?，F(xiàn)有技術(shù)都是在一個數(shù)據(jù)庫中挖掘間接關(guān)聯(lián)規(guī)則。采用投票率作為規(guī)則興趣度量來提取全局間接關(guān)聯(lián)規(guī)則，并在此基礎(chǔ)上定義了相對支持度和方差來衡量間接規(guī)則的強(qiáng)度，以從多個數(shù)據(jù)庫中挖掘有效的間接關(guān)聯(lián)規(guī)則。最后通過實驗驗證了該方法的有效性。

關(guān)鍵詞：間接關(guān)聯(lián)規(guī)則；數(shù)據(jù)挖掘；多數(shù)據(jù)庫；投票率

DOIDOI：10.11907/rjdk.161920

中圖分類號：TP312

文獻(xiàn)標(biāo)識碼：A文章編號文章編號：16727800（2016）009004902

作者簡介作者簡介：段巧靈（1986-），女，湖南衡陽人，碩士，武漢晴川學(xué)院計算機(jī)學(xué)院助教，研究方向為數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)。

0引言

關(guān)聯(lián)規(guī)則作為數(shù)據(jù)挖掘的重要領(lǐng)域之一，由R Agrawal[1]在1993年首次提出。關(guān)聯(lián)規(guī)則是通過頻繁項集的挖掘來獲取的，卻忽略了其中的非頻繁項集。例如，在超市的商品交易中，如果數(shù)據(jù)項對（A，B）頻率非常低，但是（A，C）和（B，C）出現(xiàn)的頻率卻非常高，可稱為間接關(guān)聯(lián)規(guī)則[2]，即（A，B）通過中間集C間接關(guān)聯(lián)。間接關(guān)聯(lián)規(guī)則提供了非常有價值的信息，可以應(yīng)用在很多方面，如對文本的查詢進(jìn)行分類、市場營銷、Web日志挖掘和股票分析等。

目前，現(xiàn)有技術(shù)都是在單個數(shù)據(jù)庫中挖掘間接關(guān)聯(lián)規(guī)則。隨著多數(shù)據(jù)庫技術(shù)的快速發(fā)展，在多個數(shù)據(jù)庫中挖掘間接關(guān)聯(lián)規(guī)則顯得尤為重要[3]。本文致力于挖掘多數(shù)據(jù)庫中的間接關(guān)聯(lián)規(guī)則，即挖掘全局的間接關(guān)聯(lián)規(guī)則。使用投票率作為標(biāo)準(zhǔn)選取有效的全局間接關(guān)聯(lián)規(guī)則，并通過計算各個有效的間接規(guī)則的支持度方差對其進(jìn)行排序，以供決策者使用。最后設(shè)計了相關(guān)算法，實驗結(jié)果證明了該算法的有效性。

1相關(guān)工作

1.1問題描述

間接關(guān)聯(lián)規(guī)則是形如的一個表達(dá)式，其中A，B，MT，A∩B=Φ，項對（A，B）依賴中間項集M而存在，稱項對（A，B）通過中間集M間接關(guān)聯(lián)。挖掘間接關(guān)聯(lián)規(guī)則即找出滿足條件的中間項M：

（1） sup（A，B）≤ts

（2） sup（A，M）≥tf，sup（B，M）≥tf，dep（A，M）≥td，dep（B，M）≥td

其中，dep（A，B）=P（A∩B）[]P（A）*P（B）表示項集之間依賴關(guān)系的強(qiáng)度，ts、tf、td分別稱為項對支持度閾值、中間集支持度閾值、依賴度閾值。通常設(shè)置tf≥ts。

1.2間接關(guān)聯(lián)規(guī)則挖掘技術(shù)

現(xiàn)行的間接關(guān)聯(lián)規(guī)則挖掘研究主要針對提高開發(fā)效率和擴(kuò)展定義兩方面[46]。間接關(guān)聯(lián)規(guī)則是由P N Tan等在文獻(xiàn)[2]中首次提出。通過頻繁項集挖掘間接關(guān)聯(lián)規(guī)則，主要分為以下兩步：①用標(biāo)準(zhǔn)的頻繁項集挖掘算法獲取所有頻繁項集，如Apriori算法；②通過檢查由頻繁項集產(chǎn)生的候選關(guān)聯(lián)規(guī)則來發(fā)現(xiàn)有效的間接關(guān)聯(lián)規(guī)則。

顯然，通過挖掘所有頻繁項集來獲取間接關(guān)聯(lián)規(guī)則非常費時。Wan在文獻(xiàn)[4]中提出了一種基于HIstruct的數(shù)據(jù)模型，通過HI-mine算法來提高間接關(guān)聯(lián)規(guī)則挖掘效率；Chen等在文獻(xiàn)[5]中考慮到數(shù)據(jù)項的生命周期，探索出一種新模式并用MGGrowth算法來挖掘間接關(guān)聯(lián)規(guī)則；Ouyang等在文獻(xiàn)[6]中考慮到不同角色在現(xiàn)實世界中的應(yīng)用，提出一個間接的加權(quán)關(guān)聯(lián)規(guī)則模型來擴(kuò)展間接關(guān)聯(lián)規(guī)則挖掘模型。

2多數(shù)據(jù)庫中的間接關(guān)聯(lián)規(guī)則挖掘

在多數(shù)據(jù)庫中挖掘有效的間接關(guān)聯(lián)規(guī)則主要包括以下3個步驟：①對多個數(shù)據(jù)庫使用聚類算法進(jìn)行分類；②對每個數(shù)據(jù)庫進(jìn)行間接關(guān)聯(lián)規(guī)則挖掘；③挖掘多個數(shù)據(jù)中的全局間接關(guān)聯(lián)規(guī)則。

下文詳細(xì)闡述了多數(shù)據(jù)庫挖掘的第3個步驟。在科學(xué)研究及應(yīng)用中，對于規(guī)則的選取可以采用投票來決定。一個規(guī)則投票數(shù)越多，則表示該規(guī)則可靠性越高。因此，多數(shù)據(jù)庫中的全局間接關(guān)聯(lián)規(guī)則是以投票率作為標(biāo)準(zhǔn)來挖掘的。