胡霽芳+邵明月

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

關(guān)鍵詞 數(shù)據(jù)挖掘 關(guān)聯(lián)規(guī)則 算法

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A

0引言

數(shù)據(jù)挖掘是從大型數(shù)據(jù)庫或數(shù)據(jù)倉庫中提取隱含的、先前未知的、對(duì)決策有潛在價(jià)值的知識(shí)和規(guī)則。它是人工智能和數(shù)據(jù)庫發(fā)展相結(jié)合的產(chǎn)物，是國際上數(shù)據(jù)庫和信息決策系統(tǒng)最前沿的研究方向之一。數(shù)據(jù)挖掘主要的算法有分類模式、關(guān)聯(lián)規(guī)則、決策樹、序列模式、聚類模式分析、神經(jīng)網(wǎng)絡(luò)算法等等。關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘領(lǐng)域中一個(gè)非常重要的研究課題，廣泛用于各個(gè)領(lǐng)域，既可以檢驗(yàn)行業(yè)內(nèi)長期形成的知識(shí)模式，也能夠發(fā)現(xiàn)隱藏的新規(guī)律。有效地發(fā)現(xiàn)、理解、運(yùn)用關(guān)聯(lián)規(guī)則是完成數(shù)據(jù)挖掘任務(wù)的重要手段，因此對(duì)關(guān)聯(lián)規(guī)則的研究具有重要的理論價(jià)值和現(xiàn)實(shí)意義。

1關(guān)聯(lián)規(guī)則基本原理

關(guān)聯(lián)規(guī)則挖掘問題就是在事務(wù)數(shù)據(jù)庫D中找出具有用戶給定的最小支持度minsup和最小置信度minconf的關(guān)聯(lián)規(guī)則。關(guān)聯(lián)規(guī)則挖掘問題可以分解為以下兩個(gè)子問題。

（1）找出存在與事務(wù)數(shù)據(jù)庫中所有強(qiáng)相集X的支持度support（X）不小于用戶給定的最小支持度minsup，則X為強(qiáng)項(xiàng)集。

（2）利用強(qiáng)項(xiàng)集生成關(guān)聯(lián)規(guī)則。對(duì)于每個(gè)強(qiáng)項(xiàng)集A，若B€H袮，B≠，且support（A）/support（B）minconf，則有關(guān)聯(lián)規(guī)則。B€H！（AB）。

2關(guān)聯(lián)規(guī)則算法概述及典型算法分析

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

2.1單維關(guān)聯(lián)規(guī)則

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

2.2多維關(guān)聯(lián)規(guī)則挖掘

它指關(guān)聯(lián)規(guī)則涉及2個(gè)或2個(gè)以上變量，根據(jù)是否允許同一維重復(fù)出現(xiàn)，多維關(guān)聯(lián)規(guī)則又可以分為維間關(guān)聯(lián)規(guī)則和混合維關(guān)聯(lián)規(guī)則。維間關(guān)聯(lián)規(guī)則和混合維關(guān)聯(lián)規(guī)則還要考慮不同的字段種類，即類別數(shù)據(jù)與數(shù)值數(shù)據(jù)。對(duì)于類別資料，一般關(guān)聯(lián)規(guī)則算法都可以處理，而對(duì)數(shù)值資料，就需要將這些資料轉(zhuǎn)化成類別資料才可以處理。

3總結(jié)

目前，數(shù)據(jù)庫關(guān)聯(lián)規(guī)則挖掘已經(jīng)取得了令人矚目的成績，但對(duì)下列問題進(jìn)行研究時(shí)具有挑戰(zhàn)性的工作。

3.1開發(fā)更有效的挖掘算法

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

3.2可視化挖掘

設(shè)計(jì)一個(gè)靈活方便的用戶界面，允許用戶與挖掘系統(tǒng)進(jìn)行互換，并對(duì)所挖掘的結(jié)果進(jìn)行很好的可視化表示，使非領(lǐng)域?qū)＜乙材苓M(jìn)行挖掘。

3.3各種非結(jié)構(gòu)化數(shù)據(jù)的挖掘

目前大多數(shù)關(guān)聯(lián)規(guī)則挖掘大多是基于關(guān)系數(shù)據(jù)庫或事務(wù)數(shù)據(jù)庫的算法，設(shè)計(jì)應(yīng)用于其他類型數(shù)據(jù)庫（如面向?qū)ο髷?shù)據(jù)庫、數(shù)據(jù)倉庫、文本數(shù)據(jù)、圖形圖像數(shù)據(jù)、多媒體數(shù)據(jù)等）關(guān)聯(lián)規(guī)則挖掘算法也將是十分有意義的工作。

3.4并行關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘

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

3.5制定更加合理的關(guān)聯(lián)規(guī)則衡量評(píng)價(jià)標(biāo)準(zhǔn)

目前的關(guān)聯(lián)規(guī)則衡量標(biāo)準(zhǔn)可能會(huì)發(fā)現(xiàn)一些冗余的、虛假的和非挖掘者關(guān)心的關(guān)聯(lián)規(guī)則，因而有必要制定一些新的衡量標(biāo)準(zhǔn)，用來衡量關(guān)聯(lián)規(guī)則挖掘算法的優(yōu)劣，但這些標(biāo)準(zhǔn)的制定可能要具體問題具體分析。

3.6與其他系統(tǒng)的集成

這里的集成包括與其他挖掘方法的集成和與其他系統(tǒng)的集成。

3.7研究在網(wǎng)絡(luò)環(huán)境下的關(guān)聯(lián)規(guī)則挖掘技術(shù)

特別是在Internet上建立DM服務(wù)器，與數(shù)據(jù)庫服務(wù)器配合，實(shí)現(xiàn)數(shù)據(jù)挖掘。

參考文獻(xiàn)

[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] 尹阿東，高學(xué)東，武森等，基于數(shù)值屬性的關(guān)聯(lián)規(guī)則挖掘算法[J]. 微機(jī)發(fā)展，2003，（04）：67-70.

[3] 齊雁，李石君，薛海峰。對(duì)演變數(shù)據(jù)進(jìn)行關(guān)聯(lián)規(guī)則挖掘的新方法[J].計(jì)算機(jī)工程，2002（11）：126-128.

[4] 羅可，吳杰.關(guān)聯(lián)規(guī)則衡量標(biāo)準(zhǔn)的研究[J]. 控制與決策，2003（08）：419-424.

[5] 楊建林，鄧三鴻，蘇新寧.關(guān)聯(lián)規(guī)則興趣度的衡量[J]. 情報(bào)學(xué)報(bào)，2003（08）：277-281.endprint