基于二進制的關聯規則挖掘算法

摘要：將二進制引入關聯規則求解中，充分利用二進制操作方便、運算速度快、節省空間的優勢。在求解事務項集真子集和支持度時，對事務數據庫中相同事務只求解一次，并給出了真子集的具體求解算法。本算法一次掃描數據庫可以挖掘出所有頻繁集，而且可以根據需求對最小支持度和最小置信度進行修改，修改后不需要再次掃描數據庫即可求出頻繁項集，大大提高了挖掘效率。

關鍵詞：二進制； 關聯規則； 頻繁集； 真子集

中圖分類號：TP301．6文獻標志碼：A

文章編號：1001－3695(2007)08－0079－02

0引言

數據挖掘是從已有的海量數據中發現未知的、具有潛在應用價值的信息或模式。此概念一提出就立即引起了科技界的廣泛關注。關聯規則算法則是數據挖掘的一個重要研究方向。其側重于確定數據庫中不同領域間的聯系，找出滿足給定支持度和可信度的多個域之間的相互關系。它由R.Agrawal等人首先提出。國內外很多學者對這一課題做了大量的研究工作[1~4]，為數據挖掘的發展作出了很大的貢獻。傳統的關聯規則挖掘方法大多是在R.Agrawal提出的Apriori算法的基礎上進行研究和改進的。 Apriori算法最大的缺陷就是需要多次掃描數據庫，影響了運行效率。雖然后來很多人對其進行了改進，但效率仍然不是很高。文獻[1，2]提出的關聯規則挖掘方法可以在一次掃描事務數據庫的情況下發現所有頻繁集，但是需要對每一個事務都求出其所有真子集。求集合的所有真子集是很麻煩、費時的，因此應該盡量減少子集的求解次數。本文提出的基于二進制的關聯規則挖掘算法，在文獻[2]的基礎上進行了改進，對事務數據庫中相同事務只需求解一次真子集，并且給出了真子集求解的二進制實現算法。

1關聯規則挖掘基本知識

3基于二進制的關聯規則挖掘算法

3．1算法結構體設計

本算法需要如下數據結構：

typedef struct pset

{int location[];

int value;

}Pset;

用每個Pset節點代表一個事務；location屬性記錄事務項集中元素在對應二進制數中的位置；location[0]為事務項集中的元素數；value記錄事務數據庫中與此事務相同的事務數目。

3．2事務項集真子集求解

本算法首先掃描數據庫，獲得每個事務的項集下標，并對相同事務進行計數，也就是求出事務項集的支持量；最后，根據掃描得到的事務項集支持量以及事務中項目元素與事務項集下標的對應關系，求解每種事務項集的真子集支持量。

要求解某個事務項集的真子集支持量，首先要求出每個真子集對應的事務項集的下標。為此在掃描數據庫時，需要記錄每個事務中各個項目元素在對應事務項集下標中的位置（存放在location數組中）；然后，對每個事務項集求出本項集自身的局部真子集二進制表示；最后，根據此局部真子集二進制表示以及每個元素在對應事務項集下標中的位置，得到事務項目集的所有真子集下標。

從以上描述可以看出，Armab算法能夠方便地求出頻繁項集。在最小支持度改變時不用再掃描事務數據庫，只需重新掃描PC數組即可，而且對事務項集的真子集求解方法也很簡單。沒有使用傳統的遞歸操作，使用了運算速度最快的位運算，可以節省空間和運算時間，提高挖掘效率。

4結束語

本文將二進制引入到關聯規則挖掘中，通過預先掃描數據庫，將事務分類并計數，得到事務項集的支持量；然后再求解每種事務項集的真子集。這樣既實現了一次掃描數據庫得到所有頻繁集，又避免了對同一種事務多次求解其真子集的弊端。真子集的求解不是采用傳統的遞歸分算法，而是利用位運算，大大提高了運算速度。

參考文獻：

［1］周海巖．適合于高效更新的關聯規則挖掘算法[J].小型微型計算機系統，2004，25(4):4634－4637.

[2］閆煒，崔杜武，付長龍．基于冪集的關聯規則挖掘算法研究[J]. 計算機工程與應用，2004，40(1):192－193.

[3]TSAY Y J， CHIANG J Y.CBAR: an efficient method for mining association rules[J].KnowledgeBased Systems，2005，18(2－3):99－105.

[4]AGRAWAL R， IMIELINSKI T， SWAMI A， Mining association rules between sets of items in large databases[C]//Proc of the ACM SIGMOD Int’l Conference on Management of Data. Washington D C:[s.n.]， 1993:207－216.

[5］李天志， 梁家榮， 范平. 基于二進制的集合運算研究[J].計算機工程與應用，2005，41(33):100102.

[6］李天志， 梁家榮， 范平，等.基于二進制的粗糙集基本運算研究[J].廣西科學，2006，13(2):109112.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”