段巧靈++李芬++張莉

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

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

DOIDOI：10.11907/rjdk.161920

中圖分類號(hào)：TP312

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

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

0引言

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

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

1相關(guān)工作

1.1問(wèn)題描述

間接關(guān)聯(lián)規(guī)則是形如的一個(gè)表達(dá)式，其中A，B，MT，A∩B=Φ，項(xiàng)對(duì)（A，B）依賴中間項(xiàng)集M而存在，稱項(xiàng)對(duì)（A，B）通過(guò)中間集M間接關(guān)聯(lián)。挖掘間接關(guān)聯(lián)規(guī)則即找出滿足條件的中間項(xiàng)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）表示項(xiàng)集之間依賴關(guān)系的強(qiáng)度，ts、tf、td分別稱為項(xiàng)對(duì)支持度閾值、中間集支持度閾值、依賴度閾值。通常設(shè)置tf≥ts。

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

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

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

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

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

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