關聯規則挖掘算法

胡霽芳+邵明月

摘 要 本文介紹了關聯規則挖掘算法的基本原理，并按照挖掘中涉及到的變量數目、數據的抽象層次和處理變量的類型，依次對關聯規則挖掘算法的研究進行綜述，并對一些典型的算法進行分析和比較，最后展望了關聯規則挖掘算法的研究方向。

關鍵詞 數據挖掘 關聯規則 算法

中圖分類號：TP311 文獻標識碼：A

0引言

數據挖掘是從大型數據庫或數據倉庫中提取隱含的、先前未知的、對決策有潛在價值的知識和規則。它是人工智能和數據庫發展相結合的產物，是國際上數據庫和信息決策系統最前沿的研究方向之一。數據挖掘主要的算法有分類模式、關聯規則、決策樹、序列模式、聚類模式分析、神經網絡算法等等。關聯規則是數據挖掘領域中一個非常重要的研究課題，廣泛用于各個領域，既可以檢驗行業內長期形成的知識模式，也能夠發現隱藏的新規律。有效地發現、理解、運用關聯規則是完成數據挖掘任務的重要手段，因此對關聯規則的研究具有重要的理論價值和現實意義。

1關聯規則基本原理

關聯規則挖掘問題就是在事務數據庫D中找出具有用戶給定的最小支持度minsup和最小置信度minconf的關聯規則。關聯規則挖掘問題可以分解為以下兩個子問題。

（1）找出存在與事務數據庫中所有強相集X的支持度support（X）不小于用戶給定的最小支持度minsup，則X為強項集。

（2）利用強項集生成關聯規則。對于每個強項集A，若B€H袮，B≠，且support（A）/support（B）minconf，則有關聯規則。B€H！（AB）。

2關聯規則算法概述及典型算法分析

R.Agrawal等提出了關聯規則挖掘問題以后，一批有效的挖掘關聯規則的算法在過去幾年中得到了長足的發展。到目前為止，其主要研究方向有：基于規則中涉及到的數據維數的挖掘算法，基于規則中處理變量類別的挖掘算法，其他關聯算法等。

2.1單維關聯規則

基于約束的規則挖掘約束的內容可以是：（1）數據約束：用戶可以指定對哪些數據進行挖掘，而不一定時全部的數據。（2）指定挖掘的維和層次：用戶可以指定對數據哪些維以及這些維上的哪些層次進行挖掘。（3）規則約束：可以指定哪些類型的規則是所需要的，引入一個模板的概念，用戶使用它來確定哪些規則令人感興趣的：如果一條規則匹配一個包含的模板，則是令人感興趣的，然而如果一條規則匹配一個限制的模板，則被認為是缺乏興趣的。

2.2多維關聯規則挖掘

它指關聯規則涉及2個或2個以上變量，根據是否允許同一維重復出現，多維關聯規則又可以分為維間關聯規則和混合維關聯規則。維間關聯規則和混合維關聯規則還要考慮不同的字段種類，即類別數據與數值數據。對于類別資料，一般關聯規則算法都可以處理，而對數值資料，就需要將這些資料轉化成類別資料才可以處理。

3總結

目前，數據庫關聯規則挖掘已經取得了令人矚目的成績，但對下列問題進行研究時具有挑戰性的工作。

3.1開發更有效的挖掘算法

隨著數據庫的尺寸不斷增大，不僅增大了挖掘算法的搜索空間，而且也增加了盲目發現的可能性。因此必須利用領域知識去提取與發現任務有關的數據，刪除無用的數據，有效地降低問題的維數，設計出更加有效地挖掘算法。在這一方面，基于約束的關聯規則挖掘具有廣闊的前途。

3.2可視化挖掘

設計一個靈活方便的用戶界面，允許用戶與挖掘系統進行互換，并對所挖掘的結果進行很好的可視化表示，使非領域專家也能進行挖掘。

3.3各種非結構化數據的挖掘

目前大多數關聯規則挖掘大多是基于關系數據庫或事務數據庫的算法，設計應用于其他類型數據庫（如面向對象數據庫、數據倉庫、文本數據、圖形圖像數據、多媒體數據等）關聯規則挖掘算法也將是十分有意義的工作。

3.4并行關聯規則數據挖掘

隨著數據挖掘中數據量的高速增加以及大規模并行計算在數據挖掘中的應用，由于挖掘系統本身的原因，并行數據挖掘過程更加趨向粗粒度的挖掘，無法實現任意程度的并行。目前在并行數據挖掘中尚有一些問題需要解決：數據量的不斷增加，維數越來越高，數據定位問題，數據的不對稱，動態負載平衡，多表數據庫的數據分布和索引方案，增量的方法，并行的數據庫管理系統和文件系統。

3.5制定更加合理的關聯規則衡量評價標準

目前的關聯規則衡量標準可能會發現一些冗余的、虛假的和非挖掘者關心的關聯規則，因而有必要制定一些新的衡量標準，用來衡量關聯規則挖掘算法的優劣，但這些標準的制定可能要具體問題具體分析。

3.6與其他系統的集成

這里的集成包括與其他挖掘方法的集成和與其他系統的集成。

3.7研究在網絡環境下的關聯規則挖掘技術

特別是在Internet上建立DM服務器，與數據庫服務器配合，實現數據挖掘。

參考文獻

[1] Agrawal R， Srkant R. Mining association rules between sets of items in large databases[A].ProcACM SIGMOD Int1 Conf Management of data [C]. Washington DC，May 1993.207-216.

[2] 尹阿東，高學東，武森等，基于數值屬性的關聯規則挖掘算法[J]. 微機發展，2003，（04）：67-70.

[3] 齊雁，李石君，薛海峰。對演變數據進行關聯規則挖掘的新方法[J].計算機工程，2002（11）：126-128.

[4] 羅可，吳杰.關聯規則衡量標準的研究[J]. 控制與決策，2003（08）：419-424.

[5] 楊建林，鄧三鴻，蘇新寧.關聯規則興趣度的衡量[J]. 情報學報，2003（08）：277-281.endprint