關聯規則興趣度研究

摘要：關聯規則是一種常見的知識表達形式。本文介紹了關聯規則的提取模式和基于PS架構提取模式的不足；介紹了關聯規則興趣度的定義，包括客觀興趣度和主觀興趣度以及綜合興趣度。

關鍵詞：關聯規則；客觀興趣度；主觀興趣度；綜合興趣度

中圖分類號：TP18文獻標識碼：A文章編號：1009-3044(2008)24-1133-04

A study of association rule interestingness

SI Kang

(Guangzhou Architechture Engineering Vocational School， Guangzhou 510403，China)

Abstract:Association rule is a ordinary expression method of knowledge. In this article， it’s mining mode of association rule and defection of mining mode based on PS framework which wereilluminated. Also definitions were illuminated in this article， which of association rule interestingness， including objective interestingness， subjective interestingness and compositive interestingness.

Key words: association rule;objective interestingness;subjective interestingness;compositive interestingness

KDD （Knowledge Discovery in Database），即數據庫中的知識發現，是一系列操作的集成，獲取的知識是一組規則的集合。產生式規則（Production Rules）是知識表示的一種常見形式，日常活動中廣泛使用的各種“條件 結論”結構；“原因 結果”結構都是屬于產生式規則的表示形式。關聯規則是產生式規則的一種重要形式，是KDD中通過數據挖掘獲取的知識的一種主要表達形式。在商業智能（BI）系統中，關聯規則挖掘的典型例子是購物籃分析。通過購物籃分析，可以發現顧客放入其購物籃中不同商品之間的聯系，可以分析顧客的購買習慣。通過了解哪些商品頻繁地被顧客同時購買，發現商品之間的關聯，可以幫助企業管理者制定營銷策略，如分類設計、交叉購物和賤賣分析等。

對大型數據庫的挖掘會產生很多關聯規則，其中對用戶有價值的規則稱之為“有趣的”。有趣的規則必須通過提取。在過去的研究中，一般把提取的過程作為提取關聯規則算法的一部分，主要是算法研究。很少考慮用戶的“興趣”。很多規則是正確的，但用戶來說是“無趣的”。為了將用戶的“興趣”參與到整個提取過程，引入了“興趣度”的概念，大大提高了規則提取的有效性和“有趣性”。

興趣度的定義很多，主要有客觀興趣度和主觀興趣度。本文討論一些較有代表性的定義以及興趣度的產生背景和研究動態，并著重介紹客觀興趣度的度量。對主觀興趣度的度量主要做了定性介紹，因為主觀興趣度的定量定義是一個非常復雜的問題，與行業的背景知識有很大的關系。目前，沒有一種對各行業都適應的定義方法，按照行業背景的不同，可以選擇不同的主觀興趣度定義。

1 關聯規則獲取的常見模式

發現關聯規則挖掘過程的模式多種多樣，常見的主要有以下四種。如圖1所示。

圖1中，圖a是目前典型的知識發現模式，這種模式沒有知識評價過程，數據挖掘的結果就是最終輸出的知識。用戶面對輸出的眾多知識，要從中優選出感興趣的知識非常困難，甚至是不可能的。

圖b 所示的知識發現模式相對圖a 的模式要實用些，它在數據挖掘后面增加了一個過濾器，用來篩除掉那些不符合給定評價標準的知識。但它缺少背景知識和與用戶的交互過程，而這些恰恰是很關鍵的，因為知識發現是面向具體的應用的，并且知識的最終使用者是用戶，缺少了背景知識的過濾和用戶的參與，使得知識發現的過程缺少了用戶的確認。另外，它僅有一個過濾器，只能刪除掉某一類型的知識，而這在實際應用中是遠遠不夠的。

圖c所示的模式從理論上講是最具吸引力的，因為數據挖掘是在感興趣產生器的指導下進行的，只挖掘那些用戶感興趣的知識，從而使搜索空間減小，挖掘速度加快。它不會產生用戶不感興趣的知識，提高了系統的效率。感興趣產生器中最重要的組成部分是背景知識和用戶興趣方面的知識。其不足在于：由于用戶的興趣在不斷變化，不同時刻感興趣的方面和對同一問題的感興趣程度不同，要確定在特定時刻用戶的感興趣度幾乎不可能。同時，當不同的用戶使用同一個知識發現系統時，感興趣產生器要隨著改變。每改變一次，就需要重新挖掘一次。運算量很大。降低了系統的使用效率。

圖d是圖b的一種擴展，其中感興趣分析器由一系列感興趣的度量單元組成，它們是并行操作的，分別對不同類型的知識、同一類型知識的不同形式進行評價。通過不斷的人機交互，一方面用戶可以輸入有關的背景知識，另一方面通過這一階段知識評價的結果可以激發用戶新的興趣或對原有的興趣進行實時修改。再者，對于不同的用戶，他們使用的是同一個數據挖掘的結果，不同的是各個度量單元，改變時不需要直接對數據庫操作。與圖c模式相比，系統的運算量大大減少。這種方式的不足是不容易保證不同度量單元的相互獨立，因為最后輸出的不僅是知識的表示形式，還有感興趣度。因此各個度量結果的相互影響成為要考慮的問題。從這里可以看出，盡管多數的知識發現系統還沒有考慮評價過程，但它作為知識發現的一項重要內容應越來越受到重視。圖b ，c，d中的系統都加入了評價這一環節，方式各不一樣，各有其優缺點。當獲取的背景知識很少時應該使用圖b的模式。使用圖d 中的知識發現方法，既可以避免丟失知識，又有利于背景知識的進一步獲取。當領域知識比較完全，同時用戶的興趣相對穩定時，可考慮使用圖c 中的知識發現模式。

2 支持度——置信度（support-confidence）架構的不足

支持度（support）與置信度(confidence)是挖掘關聯規則中衡量規則價值的最常用評價框架。長期以來，對關聯規則的評價都采取這種評價體系，即滿足支持度和置信度閾值的規則是強關聯規則，是“有趣的”。這種評價體系對大多數規則是有效的。但存在一些缺點：首先，有些強關聯規則不是有趣的，會對用戶產生誤導；其次，滿足閾值要求的規則數量很多，其中很多不是用戶感興趣的。產生這種情況的原因主要是這種評價體系沒有考慮到背景知識，沒有考慮用戶的關注點以及一些常識。

規則歸納系統的一般思想是產生規則，用以發現數據庫中“有趣的”模式，有時也用來做預測。規則歸納系統的優點是它能得到數據庫中所有可能的有趣模式，但經常也被看作是它的缺點，因為它雖然不會漏掉任何一種情況，但用戶可能被淹沒在數量眾多的規則中。在實際應用中，挖掘的關聯規則可能因為以下原因失去有趣性。

1) 挖掘的規則符合先驗知識或期望值。

2) 挖掘的規則可能涉及非有趣屬性或屬性組合。

3) 規則冗余。

規則的置信度和支持度對理解一條規則很重要，置信度是規則后件對前件有影響的可能性；支持度是規則前件與后件同時出現的先驗可能性。由于規則過多，有些規則可能相互矛盾，有些沒有實用價值或人們不感興趣，這時就需要尋找衡量規則的有用度和興趣度的尺度。

3 關聯規則的興趣度

興趣度可以有多種定義方法，但任何衡量興趣度的尺度都與置信度和支持度有關， 它至少應滿足Piatetsky -Shapiro提出的三個基本要求:

1) 當規則的置信度等于背景知識的正確率時，興趣度為零；

2) 當支持度(置信度)一定時，興趣度隨著置信度(支持度)單調遞增；

3) 當記錄的正確響應數量一定時，興趣度隨著支持度單調遞減。

關聯規則的興趣度評測包括客觀(objective)和主觀(subjective)兩個方面。有趣性的客觀評測由規則的具體結構和所依賴的數據決定， 它與規則的支持度和置信度有關。 有趣性的主觀評測與用戶的領域知識有關， 有些規則盡管支持度和置信度很高， 但用戶未必對規則的內容感興趣。 規則有趣性的客觀度量稱為客觀興趣度， 規則有趣性的主觀度量稱為主觀興趣度。上面提到的三個基本要求中，要求2）和3）是對客觀興趣度而言的，要求1）是對主觀興趣度而言的。

3.1 關聯規則的客觀興趣度

對關聯規則評價體系的改進，利用了現有的支持度—置信度（support-confidence）框架。從改進算法和對挖掘結果加以過濾的角度增加了對規則產生的約束，使產生的關聯規則更加有趣。

使用支持度—置信度框架的關聯規則挖掘對許多應用是有用的。然而，支持度—置信度框架也可能誤導。我們考慮一種替代框架，根據相關性挖掘數據項之間有趣的聯系。如果p(A∪B)=p(A)p(B)，項集A的出現獨立于項集B的出現；否則，項集A和B作為事件是依賴的(dependent)和相關的(correlated)。這個定義容易推廣到多于兩個項集。A和B的出現之間的相關性通過下面的計算度量：

如果（1）的值小于1，則A的出現和B的出現是負相關的。如果結果值大于l，則A和B是正相關的，意味每一個的出現都蘊涵另一個的出現。如果結果值等于1，則A和B是獨立的，它們之間沒有相關性。

等式（2)等價于p(B|A)/p(B) ，這也稱為關聯規則A=>的“提升”。

3.2 關聯規則的主觀興趣度

利用規則興趣度的客觀度量可以發現符合客觀興趣條件的規則，但這是不夠的，因為產生的很多強規則雖然是客觀有趣的，但對用戶仍然無用。因此還需要用有趣度的主觀度量來定義模式的有趣度。主觀度量不但依賴于規則結構還依賴于檢查規則的用戶，一條規則對此用戶有趣對彼用戶不一定有趣。例如，有一條顯示不規范證券交易（比如說內部交易)的模式對證券交易委員會(SEC)的官員是有趣的，但對紐約無家可歸的人來說就毫無用處。

3.3 主觀興趣度度量

Klemetinenetal最早在[1]中提出了一個模板系統，模板中的規則不是用數據屬性表示的，而是先用數據屬性表示詞表(vocabulary)，再用詞表表示規則。當規則在模板中可以找到匹配時，就說規則是有趣的。不過文中沒有給出主觀有趣度是什么、怎么用，且模板是用戶自己具體明確的，所以比較適合于有自己的信念系統的用戶，但對發現那些未預料的(unexpected)規則卻是無能為力的。

[2，3，4，5]中提出了一系列發現未預料（unexpected）規則的方法，它不是通過詢問用戶想看到什么樣的規則來減少產生規則的數目，而是讓用戶明確他現有的領域知識，然后系統通過把用戶的知識和發現的規則對比，找出需要的規則。

Avisilberschatz[4]在領域獨立的背景下，把主觀有趣的規則分為兩種:未預料（unxepected）和可操作（actionable）。Unexpected規則就是與期望發生了沖突的規則，actionable規則就是可以為用戶做有益于自己的事情提供參考的規則。

4 關聯規則的綜合興趣度

綜合興趣度同時考慮了客觀興趣度和主觀興趣度兩個部分。將兩個部分加以綜合，得到一個綜合興趣度的度量。當一個規則的綜合興趣度大于綜合興趣度閾值時，就可以判斷這個模式是用戶感興趣的。主觀興趣度的確定主要由用戶給定，他考慮了可用性和新穎性等多方面的因素。

綜合興趣度的定義很多，下面介紹其中一種。

4.1 基于改進的PS架構的綜合興趣度度量

對基于相關性定義的客觀興趣度的定義進行研究發現，基于相關性定義的客觀興趣度的兩種度量方式中，式（2）給出的度量方式（ps興趣度）[5]：

在(2)中，一般說來p(A∪B)、P(A)、P(B)的值分別由式|A∪B|/|D|、|A|/|D|和|B|/|D|計算得到。其中，|A∪B| 、|A、|B|分別表示A、B在數據集D中出現的次數，|D表示數據集D中元組的個數。分別用x1、x2、x3表示 、A、B在數據集D中出現的次數，用常量n表示數據集D中元組的個數，可以將規則的相關性表示轉化為一個數學表達式：

研究關聯規則的相關性的問題就轉化為研究（3）的數學特性。

利用集合論、非線形規劃等對（3）公式進行研究發現，以下三個命題成立：

命題一：以下不等式

由以上命題可知，PS公式具有下列特性：

1) 在數據集D中，當A、B的支持度為0.5，A∪B的支持度為0時，A、B的負相關度最大，為－0.25；

2) 當A、B、AUB的支持度都為0.5時，A、B的相關度最大，為0.25；

3) A或B的支持度過大或過小時，A和B相關度都很小；

4) A、B正相關的充要條件是A、B負相關；

5) A、B的相關度與A、B的相關度是一對相反數。

將式(2)加以變形，可得到：

由（7）分析可知，當一個數據庫中的元組數一定時，且P（A）、P（B）不變時，規則的置信度p(A∪B/p(A)隨規則的興趣度增加而增加。當規則的興趣度比較大時，其置信度也比較大。客觀性的度量實際上已經綜合考慮了置信度和支持度的因素。當一個規則滿足興趣度閾值時，它同時滿足了置信度和支持度的閾值。

PS興趣度的度量有不少優點，但也存在以下的不足：

1) PS方法把A=>B和B=>A的興趣度等同看待。根據PS公式的定義可知，A=>B和B=>A的興趣度是相同的，如果接受規則A=>B，那么，也應該接受規則B=>A。換句話說，挖掘出來的規則都可以描述成“A成立當且僅當B成立”的形式。這顯然是不合適的。

2) PS方法默認0.5是最令人感興趣的支持度。PS公式使用相關度來定義興趣度，當支持度為0.5時，規則的興趣度才有可能取得最大值0.25。這種默認忽略了用戶的主觀感覺。事實上，不同的用戶可能對不同類型的規則感興趣。有的用戶對例外規則感興趣，這類規則的支持度小于0.5。因此，定義規則的興趣度應該考慮用戶的主觀感覺。由用戶指定最令人感興趣的支持度就是一種解決方案。

為了彌補PS公式的不足，我們引入了準確度等其他參數，修正興趣度的計算。

定義4.5:準確度規則A=>B準確度定義為：

公式（10）綜合考慮了用戶主觀偏好、規則準確度、規則相關度對規則興趣度的影響。

關聯規則興趣度的定義很多，本文只討論了一些較有代表性的定義。著重介紹了客觀興趣度的定量度量，對主觀興趣度的度量主要做了定性介紹，因為主觀興趣度的定量定義是一個非常復雜的問題，與行業的背景知識有很大的關系。目前，沒有一種對各行業都適應的定義方法，按照行業背景的不同，可以選擇不同的主觀興趣度定義。給出了兩種綜合興趣度的定義，在定量度量關聯規則的興趣度中具有實用價值。

參考文獻：

[1] 綦艷霞， 楊炳儒. KDD中知識評價的研究綜述[J].計算機應用研究，2001，(12):1-20.

[2] Han W， Kambr M. 范明，孟小峰譯.數據挖掘-概念與技術（影印版）[M].北京:高等教育出版社，2005.

[3] Silberschatz A， Tuzhilin A， What Makes Paterns Interesting in Knowledge Discovery Systems[J].In:IEEE Transactions on Knowledge and Data Engineering，Speciali ssue on data mining，1996，vol.5，No.6：970-974.

[4] 楊建林，鄧三鴻，蘇新寧.關聯規則興趣度的度量[J].情報學報，2003，(8):419-424.

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