多數據庫中的間接關聯規(guī)則挖掘算法

段巧靈++李芬++張莉

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

關鍵詞：間接關聯規(guī)則；數據挖掘；多數據庫；投票率

DOIDOI：10.11907/rjdk.161920

中圖分類號：TP312

文獻標識碼：A文章編號文章編號：16727800（2016）009004902

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

0引言

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

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

1相關工作

1.1問題描述

間接關聯規(guī)則是形如的一個表達式，其中A，B，MT，A∩B=Φ，項對（A，B）依賴中間項集M而存在，稱項對（A，B）通過中間集M間接關聯。挖掘間接關聯規(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）表示項集之間依賴關系的強度，ts、tf、td分別稱為項對支持度閾值、中間集支持度閾值、依賴度閾值。通常設置tf≥ts。

1.2間接關聯規(guī)則挖掘技術

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

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

2多數據庫中的間接關聯規(guī)則挖掘

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

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