牛猛

（皖南醫(yī)學院 教務(wù)處，安徽 蕪湖 241002）

關(guān)聯(lián)規(guī)則的基本研究

牛猛

（皖南醫(yī)學院 教務(wù)處，安徽 蕪湖 241002）

關(guān)聯(lián)規(guī)則是數(shù)據(jù)挖掘的一個重要的研究領(lǐng)域。簡要介紹了關(guān)聯(lián)規(guī)則的產(chǎn)生與概述；詳細介紹了關(guān)聯(lián)規(guī)則的相關(guān)定義、性質(zhì)、步驟與分類情況；闡述了關(guān)聯(lián)規(guī)則的多種挖掘方法。

關(guān)聯(lián)規(guī)則，定義，性質(zhì)，步驟，分類，方法

doi：10.3969/j.issn.1673-9477.2016.02.039

一、關(guān)聯(lián)規(guī)則的產(chǎn)生

關(guān)聯(lián)規(guī)則挖掘最早應用于對零售業(yè)中的購物籃數(shù)據(jù)進行分析。零售機構(gòu)記錄了大量的銷售記錄，這些銷售記錄被稱為購物籃數(shù)據(jù)（basket data），而記錄顧客購物信息的購物籃數(shù)據(jù)稱為事務(wù)（transaction）。

在此情況下，1993 年Agrawal 等人首先探索了銷售記錄中項集間的關(guān)聯(lián)問題，并提出了基于頻繁項集的 Apriori 算法。

二、關(guān)聯(lián)規(guī)則的概述

關(guān)聯(lián)規(guī)則挖掘就是從大量數(shù)據(jù)中挖掘出有價值的描述數(shù)據(jù)項之間相互聯(lián)系的相關(guān)知識的數(shù)據(jù)挖掘過程［1］。

關(guān)聯(lián)規(guī)則善于找出數(shù)據(jù)庫中滿足相關(guān)要求的數(shù)據(jù)屬性域之間的相互關(guān)系。

三、關(guān)聯(lián)規(guī)則的相關(guān)定義

（一）項/項目與項集

項/項目是數(shù)據(jù)庫中最小的、不可分割的信息單位，用i表示。

項集是項/項目的集合。

（二）事務(wù)與事務(wù)數(shù)據(jù)庫

（三）項集的頻率

（四）關(guān)聯(lián)規(guī)則

（五）支持度（Support）

支持度描述事務(wù)數(shù)據(jù)庫中同時包含前提（X）和結(jié)果（Y）的事務(wù)數(shù)占所有事務(wù)數(shù)的比值，即包含前提（X）和結(jié)果（Y）的事務(wù)數(shù)在事務(wù)集中出現(xiàn)的頻率，記為即

（六）置信度（Confidence）

置信度描述事務(wù)數(shù)據(jù)庫中包含前提（X）和結(jié)果（Y）的事務(wù)數(shù)占包含前提（X）的事務(wù)數(shù)的比值，即在包含前提（X）的事務(wù)中出現(xiàn)結(jié)果（Y）的概率，記為即

支持度描述了挖掘出的關(guān)聯(lián)規(guī)則在整個事務(wù)數(shù)據(jù)庫中的有用性（即統(tǒng)計重要性）；置信度描述了挖掘出的關(guān)聯(lián)規(guī)則在整個事務(wù)數(shù)據(jù)庫中的確定性（即可靠程度）。通常，只有支持度和置信度都比較高的關(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ī)則的最低有用性（即最低統(tǒng)計重要性）明確了關(guān)聯(lián)規(guī)則的最低確定性（即最低可靠程度）。

（八）頻繁項集

（九）強關(guān)聯(lián)規(guī)則

強關(guān)聯(lián)規(guī)則必須同時滿足min_sup和min_conf這兩個條件的要求。關(guān)聯(lián)規(guī)則挖掘?qū)嵸|(zhì)上就是挖掘出強關(guān)聯(lián)規(guī)則的過程。

四、關(guān)聯(lián)規(guī)則的性質(zhì)

（一）非結(jié)合性

（二）不可分解性

（三）不可傳遞性

（四）可擴展性

五、關(guān)聯(lián)規(guī)則的步驟

（一）找出所有頻繁項集

從資料集合中找出所有頻率大于或等于最小支持度的頻繁項集。找出所有頻繁項集是挖掘的前提，決定了挖掘的整體效率，也是現(xiàn)在研究的重點。

（二）根據(jù)頻繁項集和最小置信度產(chǎn)生強關(guān)聯(lián)規(guī)則

在挖掘出的所有頻繁項集的基礎(chǔ)上，列出所有可能的關(guān)聯(lián)規(guī)則，根據(jù)支持度和置信度同時大于或等于和的原則生成強關(guān)聯(lián)規(guī)則。

（三）關(guān)聯(lián)規(guī)則挖掘需注意的問題

1.明確目標

首先要明確關(guān)聯(lián)規(guī)則挖掘的目標，即用戶需要解決什么問題；然后確定挖掘的數(shù)據(jù)類型和采用的算法；之后制定挖掘的步驟，確定每一步的操作和實現(xiàn)的目標，確保挖掘的有效進行。

2.數(shù)據(jù)準備

數(shù)據(jù)準備非常重要，準備的好壞將直接影響到數(shù)據(jù)挖掘的準確性和效率。關(guān)聯(lián)規(guī)則挖掘通常適用于變量取離散值的情況。若變量取連續(xù)值，則應先進行數(shù)據(jù)離散化（即將區(qū)間內(nèi)不同范圍的連續(xù)值分別對應于不同的具體的離散值）。數(shù)據(jù)離散化是數(shù)據(jù)準備的重要工作，是挖掘的前提，離散化的合理性將直接影響挖掘的準確性和效率。

3.確定最小支持度和最小置信度

要選擇合適的最小支持度和最小置信度閾值，不能太小，也不能太大。太小會獲得過多的規(guī)則，而其中大部分可能都是無用的，這樣會明顯降低挖掘的效率；太大則會獲得極少的規(guī)則甚至是找不到規(guī)則。

4.理解關(guān)聯(lián)規(guī)則

關(guān)聯(lián)規(guī)則挖掘僅僅是一種能夠找出滿足要求的規(guī)則的分析方法，挖掘出的結(jié)果無法判斷是否具有實際意義。需根據(jù)實際情況，確定哪些規(guī)則有意義，哪些規(guī)則沒有意義；有意義的被采用，沒有意義的不能被采用。

六、關(guān)聯(lián)規(guī)則的分類

分類方法有多種，分類標準不同，所屬類型也不同，主要有以下幾種。

（一）根據(jù)涉及到的值的類型，可分為布爾型關(guān)聯(lián)規(guī)則（Boolean Association Rule）和量化型關(guān)聯(lián)規(guī)則（Quantitative Association Rule）［6］

布爾型關(guān)聯(lián)規(guī)則涉及到的值均是離散的、種類化的，它能揭示這些值之間的關(guān)系。

量化型關(guān)聯(lián)規(guī)則涉及到的是量化的值或?qū)傩灾g的關(guān)系，又被稱為數(shù)值型關(guān)聯(lián)規(guī)則。在量化型關(guān)聯(lián)規(guī)則中，將項或?qū)傩缘牧炕祫澐譃椴煌膮^(qū)間。

（二）根據(jù)涉及到的數(shù)據(jù)維數(shù)，可分為單維關(guān)聯(lián)規(guī)則（Single-Dimensional Association Rule）和多維關(guān)聯(lián)規(guī)則（Multi-dimensional Association Rule）［7］

若要處理的數(shù)據(jù)只涉及一個維，稱為單維關(guān)聯(lián)規(guī)則。單維關(guān)聯(lián)規(guī)則忽略了現(xiàn)實中數(shù)據(jù)的多個不同屬性，僅需考慮單個屬性的相互關(guān)系。

若要處理的數(shù)據(jù)涉及超過一個維，稱為多維關(guān)聯(lián)規(guī)則。多維關(guān)聯(lián)規(guī)則必須考慮多個屬性及屬性之間的相互關(guān)系。

（三）根據(jù)規(guī)則中涉及到的抽象層次，可分為單層關(guān)聯(lián)規(guī)則（ Single-level Association Rule）［8］和多層關(guān)聯(lián)規(guī)則（Multi-level Association Rule）［9］

在單層關(guān)聯(lián)規(guī)則中，涉及到的數(shù)據(jù)只有一個抽象層次。不用考慮不同的抽象層次，只需要處理同一抽象層次的項或?qū)傩蚤g的關(guān)聯(lián)。

在多層關(guān)聯(lián)規(guī)則中，涉及到的數(shù)據(jù)有多個不同的抽象層次。必須要考慮來自不同抽象層次的數(shù)據(jù)或?qū)傩蚤g的關(guān)聯(lián)。

七、關(guān)聯(lián)規(guī)則的方法

（一）基于多循環(huán)方式的挖掘方法

是最基本挖掘方法，有AIS算法［10］、Apriori算法、AprioriTid多維關(guān)聯(lián)算法、AprioriHybrid混合算法［11］、Partition分割算法及Sampling抽樣算法等。其中，Apriori算法是使用逐層搜索的迭代方法，找到頻繁項集，挖掘關(guān)聯(lián)規(guī)則的單維、單層的寬度優(yōu)先算法；分割算法 Partition通過對數(shù)據(jù)庫進行分割，從而減少挖掘過程中 I/0操作次數(shù)；抽樣算法Sampling先對數(shù)據(jù)庫進行抽樣，然后對抽樣數(shù)據(jù)進行挖掘，從而提高挖掘的效率。目前國內(nèi)的主要研究方向是對Apriori算法進行改進。

（二）并行挖掘方法

包括計數(shù)分布CD、候選分布CaD、數(shù)據(jù)分布DD［12］、PDM以及DMA等方法［13］。雖然它們通常被用于分布式數(shù)據(jù)庫的挖掘，但也可被認為是并行挖掘方法。

（三）增量式更新方法

主要有兩種情況：一是在給定 min_sup和min_conf的基礎(chǔ)上，當數(shù)據(jù)庫記錄發(fā)生變化時（如添加或者刪除記錄），如何生成關(guān)聯(lián)規(guī)則；二是在給定數(shù)據(jù)庫的基礎(chǔ)上，當min_sup和min_conf發(fā)生變化時，如何生成關(guān) 聯(lián) 規(guī) 則 。 此類算法包括NIUA、FUP、IUA以及PIUA等算法［14］。

（四）基于約束的挖掘方法

為了便于用戶參與、指導以及控制挖掘的過程，增加挖掘的交互性，設(shè)置相應的約束條件。在約束條件下，進行關(guān)聯(lián)規(guī)則挖掘的方法稱為基于約束的挖掘方法。約束類型多樣。此類算法包括CFG算法、Direct算法等算法。

（五）基于多值屬性的挖掘方法

一般通過將多值屬性的每一個類別轉(zhuǎn)化為一個屬性，從而將多值屬性挖掘轉(zhuǎn)化為布爾型挖掘。通常可分為基于數(shù)量的挖掘方法和基于類別的挖掘方法。此類算法包括SA算法和Equi-Depth Partitioning算法等。

［1］朱祥玉，侯德文，陳希.對關(guān)聯(lián)規(guī)則挖掘Apriori算法的進一步改進［J］.信息技術(shù)與信息化，2005（6）：81-83.

［2］鄭濤.基于超市交易信息數(shù)據(jù)挖掘的城市居民消費行為研究［J］.科技情報開發(fā)與經(jīng)濟，2010（19）：136-138.

［3］文拯.關(guān)聯(lián)規(guī)則算法的研究［M］.中南大學，2009.

［4］劉寒冰.數(shù)據(jù)挖掘中的關(guān)聯(lián)規(guī)則算法研究［M］.河北工程大學，2007.

［5］高明.關(guān)聯(lián)規(guī)則挖掘算法的研究及其應用［M］.山東師范大學，2006.

［6］R.Ng.L.V.S. Lakshmanan，J.Han and A.Pang.Exploratory Mining and Pruning OPtimizations of Constrained Associations Rules ［C］. Proc. of 1998 ACM-SIGMOD Conf. on Management of Data，Seattle，Washington，June 1998：13-24.

［7］秦鋒，楊學兵.一種基于APRIORI性質(zhì)的多維關(guān)聯(lián)規(guī)則挖掘算法的研究［J］.安徽工業(yè)大學學報，2003，20（2）：141-144.

［8］王文清，喬雪峰.帶有時態(tài)約束的多層次關(guān)聯(lián)規(guī)則的挖掘［J］.北京理工大學學報，2003（l）：57-90.

［9］程繼華，施鵬飛.多層次關(guān)聯(lián)規(guī)則的有效挖掘算法［J］.計算機學報，1998（11）：1037-1041.

［10］R.Agrawal，T.Imielinski，and A.Swami. Mining association rules between sets of items in large database［C］. Proceedings of the ACM SIGMOD International Conference on Management of Data（SIGMOD'93）， Washington，DC，1993.ACM Press Publisher，1993：207-216.

［11］R.Agrawal，R.Srikant. Fast Algorithms for Mining Association Rules［C］. Proceedings of the 20th International Conference on Very Large Databases（VLDB'94）， Santiago， Chile，1994：487-499.

［12］R.Agrawal，J.C.Shafer.Parallel Mining of Association Rules［J］.IEEE Transactions on knowledge and date engineering，1996，8（6）：962-969.

［13］D.W.Cheung.Efficient Mining of Association Rules in Distributed Databases［J］.IEEE Transactions onKnowledge and Data Engineering，1996（6）：910-921.

［14］馮玉才，馮劍琳.關(guān)聯(lián)規(guī)則的增量式更新算法［J］.軟件學報，1998（4）：301-306.

［責任編輯 王云江］

The basic research of association rules

NIU Meng
（Dean's Office， Wannan Medical College， Wuhu 241002， China）

The association rule is an important area of research for data mining. This paper briefly introduces its generation and overview， and also detailedly introduces its related definitions， property， procedure and classification. Additionally， this paper expounds its different kinds of mining methods.

association rule； definition； property； procedure； classification； method

G43

A

1673-9477（2016）02-114-04

［投稿日期］2016-03-20

安徽省高校人文社會科學研究項目（編號：SK2014A416）

牛猛（1982-），男，安徽淮北人，助教，碩士，研究方向：數(shù)據(jù)挖掘。