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

關(guān)鍵詞：數(shù)據(jù)挖掘；數(shù)據(jù)庫；多數(shù)據(jù)庫；模式評(píng)價(jià)

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

2 對(duì)單數(shù)據(jù)庫挖掘模式的評(píng)價(jià)

2.1 客觀評(píng)價(jià)

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

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

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

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

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

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

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

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

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

Magor和Mangano提出了第四個(gè)準(zhǔn)則：

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

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

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

■

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

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

■

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

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

2.2 主觀評(píng)價(jià)

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

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

與主觀評(píng)價(jià)有關(guān)的指標(biāo)有新穎度、用戶感興趣度等，本文認(rèn)為，規(guī)則的新穎度是其中一個(gè)很重要的評(píng)價(jià)指標(biāo)。

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

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

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

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

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

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

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

3 多數(shù)據(jù)庫中的模式的評(píng)價(jià)

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

3.1 模式的支持度

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

■

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

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

3.2 模式的重要度

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

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

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

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

4 小結(jié)

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

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

參考文獻(xiàn)：

[1] 綦艷霞，楊炳儒.KDD中知識(shí)評(píng)價(jià)的研究綜述[J].計(jì)算機(jī)應(yīng)用研究，2001(12):1-4.

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

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

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