序Vague 信息系統(tǒng)屬性約簡算法研究

張倩倩　徐天賀

摘要：重點成為常研究對象屬性值為Vague概念的Vague信息系統(tǒng)，通過定義Vague值間的序關(guān)系，建立基于優(yōu)勢關(guān)系的序Vague 信息系統(tǒng)。借助于優(yōu)勢粒度熵來計算每個屬性的重要性，進而提出一種基于優(yōu)勢粒度熵的序Vague信息系統(tǒng)屬性約簡算法，最后的實例驗證了該算法的有效性。

關(guān)鍵詞： 序Vague信息系統(tǒng)，優(yōu)勢粒度熵，屬性約簡

中圖分類號：TP18 文獻標識碼：A 文章編號：1009-3044（2015）13-0261-02

Abstract： It researches vague information system that the object attribute value is vague concept. In this paper， the ordered relationship is defined. The ordered vague information system based on dominance relation has been introduced. The importance of each attribute is computed by defined dominance granularity entropy. Then an algorithm for attribute reduction from ordered vague information system based on dominance granularity entropy. The example proves the validity for the algorithm.

Key words： ordered Vague information system， Dominance granularity entropy， Attribute Reduction

粗糙集理論[1]是一種處理模糊和不確定知識的數(shù)學工具[2]，屬性約簡與規(guī)則提取是粗糙集理論研究的核心內(nèi)容之一，目前已有很多學者對知識約簡做了深入的研究，并取得了大量成果[3-4]。在粗糙集理論中，其所研究的信息系統(tǒng)的屬性值是確定的，然而在實際應(yīng)用中，我們有時候很難去獲得一個屬性的精確值，為此不少學者研究了復(fù)雜信息表的決策規(guī)則獲取與屬性約簡方法[5-8]。目前以Vague集表示的數(shù)據(jù)分析手段還很少，Vague集是在模糊集基礎(chǔ)上發(fā)展起來的一種更加符合人類思維的新型理論，對于數(shù)據(jù)本身未知性、不確定性的描述十分有效。文獻[9]研究了Vague決策表的知識獲取，其主要思想是通過定義Vague值之間的序關(guān)系，將Vague決策表轉(zhuǎn)化為二元決策表，進而利用粗糙集理論對Vague決策表進行屬性約簡與規(guī)則提取。本文重新定義了一種更合理的序關(guān)系，并通過建立優(yōu)勢關(guān)系[11-13]對序Vague信息系統(tǒng)的屬性約簡進行了探討，并給出了優(yōu)勢關(guān)系下序Vague信息系統(tǒng)的屬性約簡算法。

1 Vague集理論

定義1[14] 設(shè)論域U={x1， x2，[…]， xn}，其中元素xi （i=1， 2，[…]， n）是所討論的對象。U上一Vague集A由真隸屬度函數(shù)tA和假隸屬度函數(shù)fA所描述： tA：U→[0，1]， fA：U→[0，1]。其中tA（xi）是由支持xi的證據(jù)所導出的肯定隸屬度的下界，fA（xi） 則是由反對xi的證據(jù)所導出的否定隸屬度的下界，且tA（xi）+fA（xi） ≤ 1。元素xi在Vague集A中的隸屬度被區(qū)間[0，1]的一個子區(qū)間[tA（xi），1- fA（xi）]所界定，稱該區(qū)間為xi在A中的Vague值。

定義2 設(shè)四元組[S′]=（U ， A ，[V′]，[f′]）是一個Vague信息系統(tǒng)，其中，U表示對象的非空有限集合，A表示屬性概念集，[V′]=∪{[V′a] | a∈A}， [V′a]為屬性a的Vague值域；[f′]：U×A→[V′]是一個信息函數(shù)，它將每個對象對應(yīng)屬性的Vague概念映射成Vague隸屬度，即[?]a∈A，x∈U，有[f′]（x ， a）∈[V′a]。

2 序Vague信息系統(tǒng)

下面我們給出一種兩個Vague對象值之間的序關(guān)系。

定義3 對于兩個Vague值x=[tx ， 1-fx]，y=[ty ， 1-fy]，tx、ty∈[0 ， 1]，若tx≥ty 且fx≤fy，則表示針對對象x的評價至少和對象y一樣好，或稱Vague值x優(yōu)于Vague值y，記作：x[?_]y。

如果在Vague信息系統(tǒng)中，對象之間具有滿足定義3的序關(guān)系，此時，可以把Vague信息系統(tǒng)看作有序Vague信息系統(tǒng)。

定義4 在序Vague信息系統(tǒng)[S′]=（U ， A ，[V′]，[f′]）中，對于B[?]A，定義[R≥B]={（xi， xj）：[f′]（xi，a）[?_][f′]（xj，a），[?]a∈B}為屬性集上的優(yōu)勢關(guān)系，則[[xi]≥B]={xj：（xi， xj）∈[R≥B]}為序Vague信息系統(tǒng)屬性集上的優(yōu)勢類。

如果將優(yōu)勢關(guān)系看成是一種信息粒度，則[[xi]≥B]也可以看做是優(yōu)勢關(guān)系上的優(yōu)勢粒。

對于任意X[?]U，定義X關(guān)于優(yōu)勢關(guān)系[R≥B]的下近似和上近似分別定義為：

[R≥B_]（X） = {xi∈U：[[xi]≥B][?]X}，[R≥B]（X） = {xi∈U：[[xi]≥B]∩X≠Φ}。

定義5 設(shè)[S′]=（U ， A ）是一個序Vague信息系統(tǒng)，[R≥A]是U上的優(yōu)勢關(guān)系，U/[R≥A]={[[x1]≥A]， [[x2]≥A]， …， [[xn]≥A]}，知識[R≥A]的優(yōu)勢粒度熵GE（[R≥A]）定義為：

GE（[R≥A]）=[1Ui=1n1[xi]≥A]，其中，|·|表示集合的基數(shù)。

定理1設(shè)[S′]=（U ， A ，[V′]，[f′]）是一個序Vague信息系統(tǒng)，R≥是論域U上的優(yōu)勢關(guān)系，P、Q[?]A且P[?]Q，則有GE（[R≥P]）≤GE（[R≥Q]）。

證明：根據(jù)定義6有GE（[R≥P]）=[1Ui=1n1[xi]≥P]，GE（[R≥Q]）=[1Ui=1n1[xi]≥Q]，GE（[R≥Q]）-GE（[R≥P]） =[1U（i=1n1[xi]≥Q-i=1n1[xi]≥P）] ，由基于優(yōu)勢關(guān)系的序Vague信息系統(tǒng)的性質(zhì)（3）可知，當P[?]Q時，有[[xi]≥Q][?][[xi]≥P]，因此|[[xi]≥Q]| ≤ |[[xi]≥P]|，有[1[xi]≥Q]| ≥ [1[xi]≥P]，則GE（[R≥Q]）≥ GE（[R≥P]），故有GE（[R≥P]） ≤ GE（[R≥Q]）成立。

定義6設(shè)[S′]=（U， A ）是一個序Vague信息系統(tǒng)，屬性a∈A在A中的重要度定義為：

Sig（a， A） = GE（[R≥A]）-GE（[R≥A-{a}]）。

性質(zhì)1 屬性a∈A在A中是必要的當且僅當Sig（a， A） >0。

性質(zhì)2 Core（A）={ a∈A| Sig（a， A） >0}。

定理2 設(shè)[S′]=（U ， A ）是一個序Vague信息系統(tǒng)，B[?]A，則B是A的一個約簡的充分必要條件是：（1） GE（[R≥B]） = GE（[R≥A]），（2）對[?]b∈B都有Sig（b， B） > 0。

3 序Vague信息系統(tǒng)屬性約簡算法

根據(jù)上面的理論設(shè)計一種針對序Vague信息系統(tǒng)進行屬性約簡的算法，在該算法中依次計算各個屬性的重要性，從中去掉對序Vague信息系統(tǒng)不重要的屬性，最后得到屬性集的一個約簡。

算法1 基于優(yōu)勢粒度熵的序Vague信息系統(tǒng)屬性約簡算法

輸入：序Vague信息系統(tǒng)[S′]=（U， A，[V′]，[f′]），U={x1， x2，[…]， xn}，A={a1， a2，…， am}

輸出：屬性A的一個約簡B

Step1：計算U/[R≥A]={[[x1]≥A]，[[x2]≥A]，…，[[xn]≥A]}、 GE（[R≥A]）及U/[R≥（A-{aj}）]= {[[x1]≥（A-{aj}）]， [[x2]≥（A-{aj}）]，…，[[xn]≥（A-{aj}）]} （j=1， 2， …， m）和GE（[R≥A-{aj}]）。

Step2：令B1 = A = {a1， a2， …，an}，Att = ?。

Step3：如果B1 – Att = ?，則B = B1，轉(zhuǎn)Step6；否則任選B1 - Att中的一個屬性ai，計算Sig（ai， A）。

Step4：若Sig（ai， A） = 0，則B1 = B1 –{ai}，轉(zhuǎn)Step4。

Step5：若Sig（ai， A） > 0，則Att = Att ∪{ai}，轉(zhuǎn)Step4。

Step6：Att 為屬性集A的一個約簡B，輸出B，算法結(jié)束。

4 實例分析

表1給出了一個序Vague信息表，其中U={x1，…， x6}為對象集， C={a， b， c， d}為屬性集。

利用算法1對表1進行約簡的步驟如下：

5 結(jié)束語

目前使用粗糙集的方法在Vague信息表上的推廣還處于研究階段，由于實際應(yīng)用中取值的不確定性，本文研究了Vague信息系統(tǒng)的屬性約簡。文中首先探討了Vague集的含義，進而尋求一種更合理的Vague值之間的序關(guān)系，定義了序Vague決策系統(tǒng)的優(yōu)勢關(guān)系，通過定義優(yōu)勢粒度熵來計算每個屬性在該信息系統(tǒng)中的重要性，約簡掉屬性重要性為0的屬性，從而達到簡化信息系統(tǒng)的目的。

參考文獻：

[1] Pawlak Z. Rough Sets. Theoretical Aspects of Reasoning about Data. Dordrecht， Netherlands： Kluwer Academic Publishers， 1991.

[2] Leung Y， Fischer M， Wu weizhi， et al. A Rough Set Approach for the Discovery of Classification Rules in Interval-valued Information Systems[J]. International Jounal of Approximate Reasoning， 2008， 47（2）：233-246.

[3] 孫士保， 秦克云. 基于包含度的決策表屬性約簡算法的研究[J].計算機工程與應(yīng)用， 2006（3）：19-21.

[4] 孫林， 徐久成， 馬媛媛.基于包含度的不一致決策表約簡新方法[J].計算機工程與應(yīng)用， 2007，43（24）：166-168，211.

[5] 陳子春，劉鵬惠，秦克云.區(qū)間值信息系統(tǒng)上決策規(guī)則的獲取與優(yōu)化[J]. 數(shù)學的實踐與認識，2011，41（19）：89-96.

[6] 梁春華，曲開社，張海云. 區(qū)間值信息系統(tǒng)的啟發(fā)式屬性約簡[J]. 計算機工程，2012，38（12）：139-142.

[7] 楊成福， 舒蘭. 基于可辨識矩陣的模糊目標系統(tǒng)決策約簡算法[J].數(shù)學的實踐與認識，2009，39（5）：103-107.

[8] 張楠，苗奪謙，岳曉冬. 區(qū)間值信息系統(tǒng)的知識約簡[J].計算機研究與發(fā)展，2010，47（8）：1362-1371

[9] 江莉， 劉三陽， 王玨， 等.Vague決策表的知識獲取[J].計算機科學， 2004， 31（2）：111-112.

[10] Shao M W， Zhang W X. Dominance Relation and Rules in an Incomplete Ordered Information System. International Journal of Intelligent Systems， 2005（20）：13-17.

[11] 陳娟， 王國胤， 胡軍.優(yōu)勢關(guān)系下不協(xié)調(diào)信息系統(tǒng)的正域約簡[J]， 計算機科學， 2008， 35 （3）：216-218，227.

[12] 徐久成，史進玲，張倩倩.基于粒計算的序決策規(guī)則提取算法[J]，模式識別與人工智能，2009， 22（4）：660-665.

[13] 徐偉華，張文修.基于優(yōu)勢關(guān)系下不協(xié)調(diào)目標信息系統(tǒng)的分布約簡[J].模糊系統(tǒng)與數(shù)學， 2007，21（4）：124-131.

[14] Gau W L， Buehrer D J. Vague sets[J]. IEEE Trans Syst Man Vybern， 1993， 23（2）： 610-614.