基于變精度優(yōu)粗集模型的一致性規(guī)則挖掘算法

陶 志，胡 柳，王 丹

（中國民航大學(xué)理學(xué)院，天津 300300）

粗糙集理論是由波蘭數(shù)學(xué)家Pawlak[1]提出的一種處理不確定性數(shù)據(jù)知識的新理論，學(xué)界普遍稱之為“數(shù)據(jù)驅(qū)動的數(shù)學(xué)”，自20 世紀(jì)80年代初提出以來，已獲得越來越廣泛的關(guān)注。基于粗糙集理論的數(shù)據(jù)挖掘方法目前已成為數(shù)據(jù)挖掘的主要方法之一，并被廣泛應(yīng)用于故障診斷、圖像處理、聲音識別、市場分析與預(yù)測等領(lǐng)域[2-6]。

粗糙集理論將知識理解為對已知數(shù)據(jù)集的分類能力，根據(jù)已知數(shù)據(jù)集自身的不可分辨關(guān)系，形成一對近似集合，對論域上的某個給定概念進(jìn)行近似表達(dá)。該方法采用數(shù)據(jù)驅(qū)動的方式，本質(zhì)上不需要任何輔助信息，僅依據(jù)數(shù)據(jù)本身提供的信息，就能夠在保留關(guān)鍵信息的前提下對數(shù)據(jù)集合進(jìn)行化簡并求得知識的最小表達(dá)，從而建立決策規(guī)則，發(fā)現(xiàn)潛在和隱含的知識（規(guī)則），特別適合應(yīng)用于知識發(fā)現(xiàn)與數(shù)據(jù)挖掘等領(lǐng)域[7]。在粗糙集數(shù)據(jù)分析中，屬性之間的依賴關(guān)系通常表現(xiàn)為一組粗糙決策規(guī)則，而粗糙規(guī)則既有確定性（一致性）的，也有不確定性（不一致性）的?；谧兙葍?yōu)粗集模型的規(guī)則挖掘算法可在含有偏好信息的數(shù)據(jù)系統(tǒng)中進(jìn)行數(shù)據(jù)挖掘，并通過預(yù)置近似精度因子，放寬標(biāo)準(zhǔn)優(yōu)粗集的嚴(yán)格邊界定義，從而克服了標(biāo)準(zhǔn)優(yōu)勢關(guān)系粗糙規(guī)則集對數(shù)據(jù)噪聲過于敏感的缺點，具有一定的容錯和抗噪聲能力[8-9]。

1 基本概念

粗糙集理論核心是分類分析，根據(jù)已有給定問題的知識將問題論域進(jìn)行劃分，然后對劃分后的每個組成部分確定其對某一概念的支持程度[10]。但在一些實際應(yīng)用系統(tǒng)中，屬性值域往往具有某種偏序關(guān)系，以此來表示優(yōu)先等級，對于這類問題就不能再依據(jù)標(biāo)準(zhǔn)粗糙集中的等價關(guān)系來劃分論域，而需要建立基于優(yōu)勢關(guān)系的粗糙集模型，以便針對相應(yīng)問題進(jìn)行分析和決策。

1.1 優(yōu)勢關(guān)系粗糙集

首先，引入優(yōu)勢關(guān)系粗糙集理論中的幾個相關(guān)概念[11]。設(shè)形式化的偏好決策系統(tǒng)表示為

式中：U 為非空有限論域；AT=C∪D 為非空有限屬性集，分為條件屬性集C 和決策屬性集D，C∩D=；V為屬性值集，V=VC∪VD，VC為條件屬性值集，VD為決策屬性值集，且屬性值具有偏好次序；f ∶U×AT→V 是一個信息函數(shù)（映射），表示對每個x∈U，q∈AT，有（fx，q）∈V。

在偏好決策系統(tǒng)中，依據(jù)決策屬性集D 可將U 劃分為有限個決策類集合：cl={clt，t∈T}，T={1，2，…，n}，通常認(rèn)為決策屬性劃分的決策類集合是有序的，即?r，s∈T，若r ＞s，則clr集合中對象從決策角度考慮優(yōu)于cls的對象。

定義1設(shè)S=〈U，AT，V，f〉為偏好決策系統(tǒng)，C為條件屬性集，若對于A?C 和?q∈A，x，y∈U，總有q（x）≥q（y），則稱x 在條件屬性集A 上優(yōu)于y，記為xDAy。

定義2設(shè)S=〈U，AT，V，f〉為偏好決策系統(tǒng)，C為條件屬性集，對于給定的A?C 和?x，y∈U，稱集合DA+（x）={y∈U|yDAx}為屬性集A 關(guān)于對象x 的優(yōu)勢集，稱集合DA-（x）={y∈U|xDAy}為屬性集A 關(guān)于對象x 的劣勢集。

定義3在偏好決策系統(tǒng)S=〈U，AT，V，f〉中，clt為決策屬性集D 下的一個決策類，clt的向上累積集（簡稱clt的優(yōu)勢類）為的向下累積集（簡稱clt的劣勢類）為

關(guān)于優(yōu)勢關(guān)系粗糙集模型的下近似和上近似定義如下。

定義4設(shè)S=〈U，AT，V，f〉為偏好決策系統(tǒng)，屬性集A?C，則向上累積集clt≥關(guān)于屬性集A 的下、上近似集及其邊界域分別為

向下累積集clt≤關(guān)于屬性集A 的下、上近似集及其邊界域分別為

1.2 變精度優(yōu)粗集

優(yōu)勢關(guān)系粗糙集嚴(yán)格按照優(yōu)勢集合DA+（x）（或劣勢集DA-（x））來進(jìn)行分類，存在由其“剛性”特質(zhì)所決定的局限性，如對擾動（噪聲）數(shù)據(jù)過于敏感。本節(jié)所提出的變精度優(yōu)粗集模型具有某種“柔性”特征，克服了優(yōu)粗集模型對數(shù)據(jù)噪聲過于敏感的缺點，適用范圍更加廣泛。

下面是變精度優(yōu)粗集的下近似和上近似的定義。

定義5設(shè)S=〈U，AT，V，f〉是一個偏好決策系統(tǒng)，屬性集A?C，clt≥是clt的一個優(yōu)勢類，則向上累積集clt≥依參數(shù)α 的下、上近似集定義為

式中：|·|表示集合的勢；參數(shù)α 取0.5 ＜α≤1，可看出，當(dāng)α=1時，變精度優(yōu)粗集即變?yōu)閮?yōu)勢關(guān)系粗糙集。相應(yīng)地，集合clt≥依參數(shù)α 的粗糙近似邊界為

對向下累積集clt≤依參數(shù)α 的下、上近似集及其邊界域分別定義為

2 基于變精度優(yōu)粗集模型的粗糙規(guī)則集

2.1 粗糙規(guī)則集

在變精度優(yōu)粗集模型中，通過對優(yōu)勢類的粗糙近似可形成一組粗糙決策規(guī)則，從數(shù)據(jù)中發(fā)現(xiàn)這些規(guī)則是粗糙集數(shù)據(jù)分析的主要目標(biāo)。

假設(shè)0.5 ＜α≤1，A?C，某優(yōu)勢類clt≥的下近似集為，則與下近似集對應(yīng)的是“至少”一致性決策規(guī)則，即對每個對象均對應(yīng)如下一條“至少”一致性決策規(guī)則x∈DA+（x）→x∈clt≥，簡記為DA+（x）→clt≥。同樣，與下近似集對應(yīng)的是“至多”一致性決策規(guī)則，簡記為DA-（x）→clt≤。以上規(guī)則：當(dāng)α=1 時，為完全一致性規(guī)則，即在優(yōu)勢關(guān)系意義下的一致性規(guī)則；否則，稱為“幾乎一致性”規(guī)則，即準(zhǔn)確度不低于閾值α 且小于1 的規(guī)則。將“幾乎一致性”規(guī)則在閾值α 水平上與完全一致性規(guī)則等同看待，可有效處理噪聲對數(shù)據(jù)一致性的影響。將“完全一致性”規(guī)則與“幾乎一致性”規(guī)則統(tǒng)稱為α 一致性規(guī)則，而將準(zhǔn)確度低于閾值α 的規(guī)則稱作不一致性規(guī)則。

定義6設(shè)Mi={cl1≥，cl2≥，…，clt≥}，1≤t≤n，則稱如下決策規(guī)則為依參數(shù)α 的“至少”不一致規(guī)則。

2.2 規(guī)則評價

對于一個決策規(guī)則DA+（x）→clt≥，一般可用準(zhǔn)確度和覆蓋度來評價其優(yōu)劣。

定義7規(guī)則DA+（x）→clt≥的準(zhǔn)確度為

定義8規(guī)則DA+（x）→clt≥的覆蓋度為

準(zhǔn)確度反映規(guī)則的準(zhǔn)確程度，覆蓋度在一定程度上表達(dá)了規(guī)則隨機(jī)性大小，期望得到既有高準(zhǔn)確度又有高覆蓋度的規(guī)則，即得到的規(guī)則要在不一致性和隨機(jī)性兩方面均得到一定程度的消除。

2.3 不確定性量度

粗糙規(guī)則集的不確定性主要有兩個原因[12-13]：一個來自于邊界域，另一個體現(xiàn)在論域中對象的不可分辨性，這兩種不確定性反映了不確定性的不同方面，不能互相代替[14-15]。

以下修正知識粒度的概念可用于從不確定性的兩個方面精確地測量粗糙規(guī)則集的不確定性。

定義9設(shè)S=〈U，AT，V，f〉是一個偏好決策系統(tǒng)，0.5 ＜α≤1，D 將U 劃分為有限個決策類，cl={cl1，cl2，…，cln}，則?A?C，修正知識粒度為

式中：ρ（AD）表示由邊界域引起的不確定性，即

GK（AD）表示由分類不精細(xì)引起的不確定性，即

修正知識粒度滿足以下性質(zhì)。

性質(zhì)10≤IGK（AD）≤1。

性質(zhì)2設(shè)S=〈U，AT，V，f〉是一個偏好決策系統(tǒng)，若A′?A，則有IGK（AD）≤IGK（AD′）。

證明由于A′?A，則對?x∈U，必滿足DA+（x）?DA′+（x），從而有|DA+（xi）|≤|DA′+（xi）|，所以GK（AD）≤GK（AD′）。

另一方面，由于A′?A，則對?x∈U，必滿足DA+（x）?DA′+（x），則有，因此，有|BndA（clt≥，α）|≤|BndA′（clt≥，α）|。

同理，可證|BndA（clt≤，α）|≤|BndA′（clt≤，α）|，從而有ρ（AD）≤ρ（AD′）。

綜上，則有ρ（AD）GK（AD）≤ρ（AD′）GK（AD′），即IGK（AD）≤IGK（AD′）。

證畢。

性質(zhì)2 說明，修正知識粒度對屬性集合具有單調(diào)性，當(dāng)屬性增加、分類能力增強(qiáng)時，修正知識粒度會隨之減小，反之，則會增大。該性質(zhì)為后續(xù)啟發(fā)式屬性約簡算法提供了理論基礎(chǔ)。

3 基于修正知識粒度的屬性相對約簡方法

一般來說，根據(jù)對決策結(jié)果影響程度的不同，屬性的重要性程度也不同。按照屬性對決策結(jié)果的影響，屬性可分為核心屬性、相對必要屬性和不必要屬性3 類，去除不必要屬性是屬性約簡問題的核心。因此，首先引入條件屬性對決策重要性的定義如下。

定義10設(shè)S=〈U，AT，V，f〉是一個偏好決策系統(tǒng)，?B?C，若a∈B，則a 對屬性集B 的重要性定義為

SigB（a）=IGK（（B-{a}）D）-IGK（BD）。

上述定義表明屬性a∈B 對B 的重要性可由B 中去掉a 后所引起的修正知識粒度變化的大小來度量。

由以上定義可推出如下性質(zhì)。

性質(zhì)30≤SigB（a）≤1。

性質(zhì)4屬性a 在屬性集B 中是必要的當(dāng)且僅當(dāng)SigB（a）＞0。

性質(zhì)5核心屬性集Core（B）={a∈B|SigB（a）＞0}。

性質(zhì)4 表明：當(dāng)SigB（a）＞0 時，說明a 是B 中必要的；當(dāng)SigB（a）=0 時，說明a 是B 中不必要的。性質(zhì)5給出求取核心屬性集的方法，核心屬性集是求取所有屬性約簡的起點。

定義11設(shè)S=〈U，AT，V，f〉是一個偏好決策系統(tǒng)，?B?C，若B 是一個相對屬性約簡，當(dāng)且僅當(dāng)B 滿足：①IGK（BD）=IGK（CD）；②?a∈B?SigB（a）＞0。

定義11 從修正知識粒度的角度提供了屬性相對約簡的定義，為后面求取屬性相對約簡算法奠定了理論基礎(chǔ)。

4 閾值α 對粗糙規(guī)則集影響分析

對于變精度粗糙規(guī)則集而言，如果條件屬性子集和決策屬性均已確定，則閾值α 取值不同就會得到不同的粗糙規(guī)則集，研究α 的變化對規(guī)則集的影響很重要，其意義是幫助決策者找出實際問題中的關(guān)鍵環(huán)節(jié)，從而起到輔助決策的作用。

4.1 相對粗糙規(guī)則集與絕對粗糙規(guī)則集

某一優(yōu)勢類clt≥的邊界域可表示為Bnd（clt≥，α）=如果或，此時，稱集合clt≥為α 可辨別的，否則稱clt≥為α 不可辨別的。

集合的可辨別性依賴于α 的取值，易證明下列定理。

定理1若clt≥在閾值0.5 ＜α≤1 水平上是可辨別的，則clt≥在任何α1＜α 水平上也是可辨別的。

對于粗糙規(guī)則集，A→αD 若存在充分小的閾值α使得W=U，即在優(yōu)勢關(guān)系粗糙集意義下，所有不一致性規(guī)則在α 水平上均可變成一致性規(guī)則，此時稱此粗糙規(guī)則集為相對粗糙規(guī)則集。相對粗糙規(guī)則集在某一α 水平上不再包含不一致性規(guī)則，完全由α 一致性規(guī)則組成，此時亦稱其達(dá)到弱完全一致。反過來，無論α取值多小，粗糙規(guī)則集中均含有不一致性規(guī)則，此時，稱此粗糙規(guī)則集為絕對粗糙規(guī)則集。

定理2設(shè)S=〈U，AT，V，f〉是一個偏好決策系統(tǒng)，D 將U 劃分為有限個決策類，cl={cl1，cl2，…，cln}，則粗糙規(guī)則集是相對粗糙規(guī)則集的充要條件是：

4.2 閾值α 靈敏度分析

設(shè)A 是條件屬性子集，D 是決策屬性集，D 將U劃分為有限個決策類，cl={cl1，cl2，…，cln}，對確定的A、D 和α 可產(chǎn)生確定的粗糙規(guī)則集A→αD。靈敏度分析是指在A、D 已確定的情況下，參數(shù)α 在何種范圍內(nèi)變化時，不會對已生成的規(guī)則集產(chǎn)生影響，參數(shù)α 的這一變化范圍即α 的閾值平穩(wěn)區(qū)間。

對每個決策類clt（1≤t≤n），clt≥為向上累積集，令

同理，對于向下累積集clt≤，令

5 一致性規(guī)則挖掘算法

變精度優(yōu)粗集模型中一致性規(guī)則集的形成可由以下3 個算法來實現(xiàn)。

5.1 求取相對屬性約簡算法

輸入偏好決策系統(tǒng)S=〈U，AT，V，f〉；閾值0.5 ＜α≤1。

輸出屬性相對約簡集C*?C。

步驟1由式（3）計算系統(tǒng)的修正知識粒度。

步驟2賦值計算出Core（C）={a∈C|SigC（a）＞0}。若IGK（Core（C）D）=IGK（CD），則C*=Core（C），輸出C*，終止計算（此時Core（C）為最小相對約簡）；否則C*=Core（C），繼續(xù)執(zhí)行步驟3。

步驟3

1）對?a∈C-C*，計算出SigC*∪{a}（a）；

3）若IGK（C*D）= IGK（CD），則輸出C*終止計算（此時C*即為一個相對約簡）；否則轉(zhuǎn)步驟1）。

5.2 一致性規(guī)則提取算法

輸入一個得到化簡的偏好決策系統(tǒng)S*=〈U，C*∪D，V，f〉；閾值0.5 ＜α≤1。

輸出α 一致性規(guī)則集

步驟1輸入一條新對象的條件屬性值C1。

步驟2對于決策表S*：

1）計算屬性值優(yōu)于C1中屬性值的元素個數(shù)N；

2）對每個不同的決策屬性值dj（j=1，2，…，n），求出條件屬性值優(yōu)于C1而決策屬性值滿足dj≥j 的元素個數(shù)Mj，并求出αj=Mj/N；

3）判斷是否存在αj≥α，如果是，則取j = min{ j |αj≥α}，轉(zhuǎn)步驟4）；否則，轉(zhuǎn)步驟3；

5）判斷αj是否為1，如果是，則輸出“完全一致性規(guī)則”至規(guī)則表，同時令μ=1 并由式（2）計算出該條規(guī)則的覆蓋度λ 并轉(zhuǎn)步驟3；否則，輸出“幾乎一致性規(guī)則”至規(guī)則表，同時由式（1）、式（2）計算出該條規(guī)則的準(zhǔn)確度μ（此時μ≥α）和覆蓋度λ 并轉(zhuǎn)步驟3。

步驟3判斷是否輸完所有對象條件屬性值，如果不是，則轉(zhuǎn)步驟1；否則，終止計算。

5.3 閾值α 影響性分析算法

輸入偏好決策系統(tǒng)S*=〈U，C*∪D，V，f〉，α 一致性規(guī)則集，閾值0.5 ＜α≤1。

輸出輸出是相對（或絕對）粗糙規(guī)則集及參數(shù)α 的閾值平穩(wěn)區(qū)間。

步驟1將S*劃分為有限個決策類，cl={cl1，cl2，…，cln}。

步驟2判定是否對每個優(yōu)勢類clt≥（t=1，2，…，n）都有且對每個優(yōu)勢類clt≤（t =1，2，…，n）都有；如果是，則令ξ =1，否則，令ξ=0。

步驟3由式（4）、式（5）計算出δ1，t和δ2，t，并取δ1=

步驟4由式（6）、式（7）計算出γ1，t和γ2，t，并取γ1=

步驟5計算出α 閾值平穩(wěn)區(qū)間（a，b] =（δ，α+δ2]∩（γ，α+γ2]。

步驟6判定是否ξ=1，如果是，則輸出是相對粗糙規(guī)則集，且輸出α 的閾值平穩(wěn)區(qū)間（a，b]；否則，輸出是絕對粗糙規(guī)則集，并輸出α 的閾值平穩(wěn)區(qū)間（a，b]。

6 算例

偏好決策系統(tǒng)S=〈U，AT，V，f〉，如表1所示，條件屬性集C = {a，b，c，d}，決策屬性集D = {e}，fr為頻數(shù)（總體樣本數(shù)為50）。

表1 偏好決策表Tab.1 Preference decision table

首先，針對表1利用5.1 節(jié)算法求出相對屬性約簡C*={a，b，d}，再針對向上累積集cl1≥、cl2≥、cl3≥，利用5.2 節(jié)算法求得α“至少”一致性規(guī)則集，如表2所示，其中取α=0.7。

由于clt≥=U，所以無需保留表2中對應(yīng)e =0 的“至少”一致性規(guī)則，則保留的規(guī)則剩下2、4、6、9、11、13、14、16。

表2 “至少”一致性規(guī)則表Tab.2 “At least”consistency rule table

對上述保留的α 一致性規(guī)則還需進(jìn)行綜合評判，采用設(shè)置覆蓋度閾值的方法，將一些過于瑣碎的規(guī)則屏蔽掉，而只保留覆蓋度超過閾值的較強(qiáng)壯規(guī)則。如若取λ=0.2，則最后保留的規(guī)則只剩2、4、6、14。

最后，用于決策的“至少”一致性規(guī)則如下：

規(guī)則1if a≥0∧b≥0∧d≥1 then e≥1（x∈cl2≥）（準(zhǔn)確度為0.83，覆蓋度為0.85）；

規(guī)則2if a≥0∧b≥1∧d≥2 then e≥1（x∈cl2≥）（準(zhǔn)確度為0.96，覆蓋度為0.59）；

規(guī)則3if a≥0∧b≥2∧d≥2 then e≥1（x∈cl2≥）（準(zhǔn)確度為0.92，覆蓋度為0.29）；

規(guī)則4if a≥2∧b≥0∧d≥1 then e≥2（x∈cl3≥）（準(zhǔn)確度為0.80，覆蓋度為0.50）。

同樣，對于向下累積集cl1≤、cl2≤、cl3≤，利用類似方法亦可求出α“至多”一致性規(guī)則集（此處不再贅述）。

此外，通過執(zhí)行5.3 節(jié)算法亦可求得此粗糙規(guī)則集是絕對粗糙規(guī)則集，且求出的閾值平穩(wěn)區(qū)間為（0.67，0.75]。

7 結(jié)語

文中提出一個完整的基于變精度優(yōu)粗集理論的規(guī)則挖掘過程，并通過實例演示證明對于含有擾動數(shù)據(jù)的優(yōu)勢關(guān)系數(shù)據(jù)集通過變精度優(yōu)粗集模型進(jìn)行規(guī)則挖掘和知識發(fā)現(xiàn)是非常有效的。該方法具有一定的容錯能力，能夠確保所得到的規(guī)則既簡潔又具有較高準(zhǔn)確度和覆蓋度，同時求出了參數(shù)對數(shù)據(jù)集的敏感性區(qū)間，便于對實際應(yīng)用系統(tǒng)進(jìn)行更加精細(xì)地分析。