對單數(shù)據(jù)庫和多數(shù)據(jù)庫中挖掘模式的評價

摘要：文章從客觀和主觀兩方面分別分析了現(xiàn)有的一些對數(shù)據(jù)挖掘模式的評價方法，并提出對多數(shù)據(jù)庫中模式評價的兩種客觀性度量。

關鍵詞：數(shù)據(jù)挖掘；數(shù)據(jù)庫；多數(shù)據(jù)庫；模式評價

中圖分類號：TP311文獻標識碼：A文章編號：1009-3044(2008)19-30021-02

Data Mining Pattern Valuation in Multi-database and Single-database

MI Jie， LI Ke

(Henan Institute of Engineering， Zhengzhou 450007， China)

Abstract: Some measures of pattern evaluation are analyzed from both the objective and subjective point of view respectively. Also two objective measures to evaluate patterns in multi-database are proposed.

Key words: data mining; database; multi-database; pattern evaluation

1 引言

數(shù)據(jù)挖掘(DM)，又稱為數(shù)據(jù)庫中的知識發(fā)現(xiàn)(KDD)。根據(jù)目前比較公認、完整、深刻和全面的數(shù)據(jù)挖掘定義——德國Fayyadz等人在1996年發(fā)表的論文《From Data Mining to Knowledge Discovery》中提出：數(shù)據(jù)挖掘是從大量的數(shù)據(jù)中提取出有效的、新穎的、有潛在價值的、可信的、并能最終被人理解的模式的非平凡的處理過程。從該定義可以看出，數(shù)據(jù)挖掘得到的模式，評價其度量標準主要包括有效性、新穎性、潛在有用性和最終可理解性[1]。對它們進行綜合度量的標準稱為模式或規(guī)則的感興趣度，它分為客觀感興趣度和主觀感興趣度。前者的主要根據(jù)是模式或規(guī)則的形式和數(shù)據(jù)庫中的數(shù)據(jù)，屬于數(shù)據(jù)驅(qū)動；而后者還要考慮用戶的參與等人為因素的影響，屬于用戶驅(qū)動。在評價過程中應該綜合使用這兩種度量標準，比較合理的方法是首先用客觀感興趣度作為第一級過濾器，選出潛在感興趣的模式，然后再用主觀感興趣度來對它們進行第二級篩選，得到用戶真正感興趣的知識。

2 對單數(shù)據(jù)庫挖掘模式的評價

2.1 客觀評價

目前，感興趣度的研究主要針對規(guī)則的客觀感興趣度[2]，客觀度量是對用戶興趣的估計。有趣性的客觀評價是指規(guī)則的有趣性是由規(guī)則的具體結(jié)構(gòu)和在數(shù)據(jù)挖掘過程中所依賴的數(shù)據(jù)決定的，這種方法主要是在這些規(guī)則上應用統(tǒng)計學方法，用定量的數(shù)值來判定規(guī)則的有趣性，從而避免了人為的主觀意見，因此從這個意義上講，規(guī)則有趣性的客觀評價是可靠的、有說服力的。

一般的，影響規(guī)則感興趣度的數(shù)據(jù)方面的因素共有三個（假設規(guī)則為A=>B）：

(1)覆蓋度(Coverage)：指前件A出現(xiàn)的概率P(A)；

(2)完全性（Completeness）：指兩者（A與B）同時出現(xiàn)的概率與B出現(xiàn)的概率之比，即P P(A∧B)/P(B)；

(3)可信度（Confidence Factor）：指兩者（A與B）同時出現(xiàn)的概率與A出現(xiàn)的概率之比，即P(A∧B)/P(A)。

Piatetsky-Shapiro提出的規(guī)則感興趣性RI(Rule Interestingness)度量的三個準則為：

(1)如果P(A∧B)=P(A)P(B)，那么RI=0；

(2)當其它參數(shù)固定時，RI隨著P(A∧B)的增加單調(diào)遞增；

(3)當其它參數(shù)固定時，RI隨著P(A)或P(B)的增加單調(diào)遞減。

Magor和Mangano提出了第四個準則：

(4)當給定的可信度大于允許的可信度時，RI隨著P(A)的增加單調(diào)遞增。

另一個通用的評價規(guī)則質(zhì)量的是規(guī)則簡潔度。它是用來衡量規(guī)則的最終可理解程度的指標。它表現(xiàn)在兩個方面：一方面是在規(guī)則項的個數(shù)上，如果規(guī)則項數(shù)很多將不利于對這條規(guī)則的理解。因此，規(guī)則的項數(shù)是一個衡量規(guī)則簡潔性的逆向指標，即規(guī)則的項數(shù)越多，規(guī)則的簡潔性越差；另一方面是在規(guī)則所包含的抽象層次上，層次越高，它對數(shù)據(jù)的解釋能力越強，也越容易理解；相反則它對數(shù)據(jù)的解釋能力越差，因此也越不容易理解。

Symth利用如下函數(shù)對規(guī)則A=>B的簡潔性和包含的信息量進行綜合度量，考慮了規(guī)則的前件A和后件B的概率分布的相似程度，以及用A的出現(xiàn)概率作為前件的簡潔性的度量，但是，忽略了P(B)的作用。

■

以關聯(lián)規(guī)則為例，支持度和可信度度量是評價關聯(lián)規(guī)則的兩個常用客觀性指標，支持度度量反映了規(guī)則的實用性，而可信度度量反映了規(guī)則的有效性。很多傳統(tǒng)的關聯(lián)規(guī)則挖掘算法就是基于這種模型來進行關聯(lián)規(guī)則挖掘的，也就是找出所有的強關聯(lián)規(guī)則。但是強關聯(lián)規(guī)則并不一定是有趣的，有時甚至是有錯誤的。

因此，有人提出了各種新的規(guī)則評價標準，并將其加入到挖掘算法中，對關聯(lián)規(guī)則的產(chǎn)生加以限制和約束，以得到更加新穎、更加有效的關聯(lián)規(guī)則。有人提出了興趣度（lift）度量方法。對于一條規(guī)則A=>B，興趣度定義為：

■

興趣度反映了交易A和交易B之間的關系，當興趣度等于1時，表明兩項交易同時出現(xiàn)屬于概率事件，不具有特別意義，即A和B是獨立的，稱該規(guī)則為不相關規(guī)則；興趣度小于1時表明其中一個項集的出現(xiàn)降低了另一個項集出現(xiàn)的可能性，稱為負相關規(guī)則；興趣度大于1時表明一個項集的出現(xiàn)會增加另一個項集出現(xiàn)的可能性，稱為正相關規(guī)則。一般情況下，挖掘出正相關的關聯(lián)規(guī)則更具現(xiàn)實意義，但有時負相關規(guī)則的出現(xiàn)也會為用戶帶來新的知識。

我們可以將興趣度同支持度和可信度一起作為規(guī)則的客觀度量標準，以提高所挖掘規(guī)則的有效性。

2.2 主觀評價

規(guī)則有趣性的客觀評價只是基于數(shù)據(jù)本身的結(jié)構(gòu)來展開的[3]，規(guī)則的產(chǎn)生完全基于事實數(shù)據(jù)，并沒有考慮規(guī)則之間的聯(lián)系和用戶對規(guī)則的認同程度。但是一個規(guī)則是否有趣最終要取決于用戶的感覺。只有用戶可以決定規(guī)則的有效性和可行性。我們應該將用戶的需求和挖掘系統(tǒng)結(jié)合起來才能挖掘出更加有效的規(guī)則。因此，判斷規(guī)則的有趣性必須考慮到主觀層面上的意義。僅根據(jù)客觀感興趣度選取用戶所關注的模式，難以獲得用戶真正感興趣的模式，還需要人為的參與。從主觀的角度講，能使用戶對發(fā)現(xiàn)的模式產(chǎn)生興趣的原因主要有兩個：意外性和實用性。

這兩者是緊密相關的。以關聯(lián)規(guī)則為例，有趣性的主觀評價是指關聯(lián)規(guī)則的有趣性不僅由規(guī)則的具體結(jié)構(gòu)和在數(shù)據(jù)挖掘過程所依賴的數(shù)據(jù)決定，而還應與使用規(guī)則的用戶感覺有關。而高支持度和高可信度的規(guī)則對用戶來講并不一定有意義，從用戶的主觀角度看，規(guī)則的非預期性(指所挖掘的規(guī)則對用戶來講是超乎想象的、沒曾見過的)和可行性（指依據(jù)所挖掘出來的規(guī)則進行決策）應該是用戶更感興趣的。

與主觀評價有關的指標有新穎度、用戶感興趣度等，本文認為，規(guī)則的新穎度是其中一個很重要的評價指標。

模式的新穎性主要表現(xiàn)在發(fā)現(xiàn)模式與知識庫中模式的差異程度上。對模式的新穎性評價是針對于原有的模式而言的，這可能會包括兩個部分的內(nèi)容：

首先，所挖掘出來的模式與已有的模式有差異，產(chǎn)生這種情況的原因可能是：

(1)所挖掘的數(shù)據(jù)對象有問題，則該模式是錯誤的；

(2)新挖掘出來的模式是對原有模式的一個補充或具有更高的抽象層次；

(3)新挖掘出來的模式推翻了原有的模式。這說明原有的模式可能失效，應刪除原有的模式。

其次，所挖掘出來的模式與用戶的期望模式有差異，用戶在進行模式挖掘的過程中，往往期望得到一些自己感興趣的模式。然而，實際的挖掘過程中可能會出現(xiàn)用戶意想不到的新模式。這些可能有助于用戶修正原有的期望模式，同時可以通過對新模式的進一步分析，從而得到更具新穎性的。

用戶對規(guī)則是否感興趣的重要指標是新穎性，它是針對于原有知識而言的，這些知識包括兩個部分：一是以往得到的準確性很高的規(guī)則，與當前所得到的規(guī)則相悖；二是與用戶所期望的知識相悖。因此，衡量新穎性主要是從形式上進行的，即分別用與規(guī)則的前件和后件的相悖程度來衡量，也可以用與原有知識的相悖的項數(shù)來衡量。我們可以通過模板匹配的方法來評價模式的新穎度，首先由用戶給出他所期望的模式作為模板，然后我們將挖掘得到的模式與模板對前件和后件分別進行匹配。匹配的結(jié)果可以將挖掘得到的模式分成四類：前件后件都匹配、前件匹配后件不匹配、后件匹配前件不匹配及前件后件都不匹配。前件后件都匹配的模式與用戶的期望一致，達到了用戶預想的目的，但是它對用戶的期望不具有新穎性。其他三類模式均與用戶的期望有差異，也即具有新穎性，這時用戶便可以對這些模式進行更深層次的分析，從而發(fā)現(xiàn)問題或作出更加有利的決策。

3 多數(shù)據(jù)庫中的模式的評價

目前，專門針對多數(shù)據(jù)庫中的模式的評價尚不多見。本文認為從主觀方面，對多數(shù)據(jù)庫中的模式的評價與單數(shù)據(jù)庫中的模式評價方法類似，但從客觀方面應有不同，因為多數(shù)據(jù)庫在數(shù)據(jù)方面與單數(shù)據(jù)庫有著很大差別，需要考慮許多單數(shù)據(jù)庫不需要考慮的因素，比如說應考慮多數(shù)據(jù)庫中每個數(shù)據(jù)庫的權重等。對于多數(shù)據(jù)庫中模式的客觀度量主要考慮以下兩方面：

3.1 模式的支持度

假設模式為A，我們定義模式A的支持度為多數(shù)據(jù)庫中模式A的支持程度，記為support(A)，計算方法如下：

■

其中，num(A)表示多數(shù)據(jù)庫中支持模式A的數(shù)據(jù)庫個數(shù)，n為總的數(shù)據(jù)庫個數(shù)。

模式的支持度反映了模式在多數(shù)據(jù)庫中的實用性或普遍性。支持模式的數(shù)據(jù)庫個數(shù)越多，則模式的支持度也越高，該模式在多數(shù)據(jù)庫中就越普遍，也即實用性也越高。

3.2 模式的重要度

我們定義多數(shù)據(jù)庫中模式的重要度為模式對整個多數(shù)據(jù)庫系統(tǒng)的重要程度，記為importance(A)。 計算方法如下：

其中，k為支持模式A的數(shù)據(jù)庫個數(shù)，即num(A)；Wi為支持模式A的第i個數(shù)據(jù)庫的權重，這里我們對如何為數(shù)據(jù)庫賦權值不作討論，只在我們假設多數(shù)據(jù)庫中各個數(shù)據(jù)庫具有相同地位時將其權重默認為1；sup(Ai)為模式A在支持它的第i個數(shù)據(jù)庫中的支持度；min supi為支持模式A的第i個數(shù)據(jù)庫中用戶給定的最小支持度閾值；max supi為支持模式A的第i個數(shù)據(jù)庫中所有模式的最大支持度。

重要度的計算中我們主要考慮到三個因素：模式的支持度、支持模式的數(shù)據(jù)庫的權重及模式在支持它的數(shù)據(jù)庫中的相對支持度。模式的支持度反映了模式的實用性或普遍性；每個數(shù)據(jù)庫所在的分支對總公司的貢獻是不同的，因此對不同的數(shù)據(jù)庫應賦予不同的權重；每個數(shù)據(jù)庫有不同的數(shù)據(jù)信息，模式在支持它的不同數(shù)據(jù)庫中的支持度有著不同的標準，因此要計算模式在支持它的各個數(shù)據(jù)庫中的相對支持度，即公式中的■。

模式的重要度越大，我們認為模式對整個多數(shù)據(jù)庫系統(tǒng)越重要。

4 小結(jié)

在知識發(fā)現(xiàn)過程中，通過挖掘算法產(chǎn)生大量的模式，但是大多數(shù)用戶對此并不感興趣。如何對它們進行評價，選取出用戶感興趣的和有用的知識是至關重要的，故對知識評價的研究具有重要的意義。

現(xiàn)有的各種評價方法都存在一定的缺陷，目前還沒有一種非常有效的評價方法能適應所有的數(shù)據(jù)或不同的用戶需求。這方面的研究工作還有待我們繼續(xù)進行。

參考文獻：

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

[2] 婁蘭芳，蔣志芳，田世壯.影響關聯(lián)規(guī)則挖掘的有趣性因素[J].計算機工程與應用，2003(6):190-191.

[3] 蘇占東，游福成，楊炳儒.關聯(lián)規(guī)則的綜合評價方法研究與實例驗證[J].計算機應用，2004，24(10):17-20.

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文