金玲玲，蘇 莉，王喜鳳

1.海南師范大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院，?？?571158

2.安徽工業(yè)大學(xué) 計算機學(xué)院，安徽 馬鞍山 243002

灰色信息系統(tǒng)基于集中有序關(guān)系下的知識約簡

金玲玲1，蘇 莉1，王喜鳳2

1.海南師范大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院，?？?571158

2.安徽工業(yè)大學(xué) 計算機學(xué)院，安徽 馬鞍山 243002

1引言

粗糙集理論是波蘭數(shù)學(xué)家Pawlak提出的處理不精確、不完備數(shù)據(jù)的有效工具[1]。經(jīng)典的粗糙集以完備信息系統(tǒng)作為研究對象，以等價關(guān)系為基礎(chǔ)，通過等價關(guān)系對論域進(jìn)行分類。但由于噪聲和信息缺損等因素影響，許多信息系統(tǒng)并不是基于等價關(guān)系的，于是人們將等價關(guān)系放寬為相容關(guān)系、相似關(guān)系等。實際應(yīng)用中，由于決策者的偏好等原因，大量的信息又是基于優(yōu)勢關(guān)系的，文獻(xiàn)[2-3]就信息系統(tǒng)中屬性值排序問題提出了基于優(yōu)勢關(guān)系的粗糙集研究方法，促進(jìn)了粗糙集的應(yīng)用和發(fā)展。目前處理偏好信息主要定義了兩種優(yōu)勢關(guān)系，遞增偏好有序和遞減偏好有序，文獻(xiàn)[4-5]討論了在優(yōu)勢關(guān)系下的屬性約簡。然而這種優(yōu)勢關(guān)系不能解決一類屬性偏好既不是遞增有序也不是遞減有序，而是屬性值趨向于標(biāo)準(zhǔn)屬性值的問題，于是文獻(xiàn)[6]建立了一種屬性集中有序關(guān)系來解決集值系統(tǒng)中的分類問題。

灰色系統(tǒng)理論[7]是20世紀(jì)80年代我國學(xué)者鄧聚龍教授提出，用于解決小樣本，貧信息的不確定問題工具，其在分析、建模、預(yù)測等方面的獨到之處，已被證明具有很高的應(yīng)用價值。

鑒于基于優(yōu)勢關(guān)系下的灰色信息系統(tǒng)約簡的研究較少，本文結(jié)合粗糙集理論與灰色理論，在集中有序優(yōu)勢關(guān)系中引入灰數(shù)測度的概念，并以綜合優(yōu)勢度為基礎(chǔ)，給出度量屬性重要度的指標(biāo)，提出了一種新的優(yōu)勢關(guān)系下灰色系統(tǒng)的啟發(fā)式屬性約簡方法。

2 灰色信息系統(tǒng)

定義1[8-9]灰數(shù)指在某一區(qū)間或某個一般的數(shù)集內(nèi)取值的不確定數(shù)，用記號“?”表示。

灰數(shù)有以下幾類：

（4）黑數(shù)與白數(shù)：當(dāng)?∈[-∞，∞]時，即當(dāng)?的上界和下界均為無窮時，稱?為黑數(shù)；當(dāng)?∈且時，稱?為白數(shù)。

（5）離散灰數(shù)與連續(xù)灰數(shù)：在某一區(qū)間內(nèi)取有限個值或可數(shù)個值的灰數(shù)稱為離散灰數(shù)；取值連續(xù)地充滿某一區(qū)間的灰數(shù)稱為連續(xù)灰數(shù)。

定義2[9]灰數(shù)的測度用 μ(?)表示，不同類型的灰數(shù)其測度定義為：

定義3設(shè)灰數(shù)?1∈，?2∈，則?1∩?2運算有五種情形：

（5）其他取Φ。

定義4[9-10]灰色信息系統(tǒng)GS是一個四元組，即GS= {U，A，V，f?}，其中U為對象的非空有限集合，即論域；A為屬性集，V=∪Va且Va是屬性a的灰描述域，f?∶U× A→V為對象的灰描述函數(shù)，對于?a∈A,u∈U，f?(u，a)為對象u在屬性a對應(yīng)的灰數(shù)，記作ua(?)。

3 信息系統(tǒng)中的優(yōu)勢關(guān)系和優(yōu)勢度

3.1 優(yōu)勢關(guān)系

定義5[11-12]設(shè)GS={U，A，V，f?}，對a∈A，xi，xj∈U，若任取vj∈f?(xj，a)，都存在vi∈f?(xi，a)，使vi≥vj，則稱xi關(guān)于a優(yōu)于xj，記為 xi?axj；若任取vj∈f?(xj，a)，都存在vi∈f?(xi，a)，使vi≤vj，則稱 xi關(guān)于a劣于 xj，記為 xi?axj。

對于屬性集B?A，xi?Bxj指xi關(guān)于B優(yōu)于xj，反之，xi?Bxj指xi關(guān)于B劣于xj。

定義6給定信息系統(tǒng)GS={U，A，V，f?}，B?A，優(yōu)勢關(guān)系R≥B定義為：

若記[xi]B={xj∈U|(xi，xj)∈}，U={[xi]B|xi∈U}，則稱[xi]B為對象 xi的優(yōu)勢類，U為信息系統(tǒng)對象集關(guān)于屬性B的一個分類。

3.2 集中有序關(guān)系

限于篇幅，僅介紹合取集值系統(tǒng)中的集中有序關(guān)系。

其中，Ma取Va的某個中間值作為標(biāo)準(zhǔn)值。

定義8給定信息系統(tǒng)S={U，A，V，f}，B?A優(yōu)勢關(guān)系 R∧B≥定義為：

顯然 R∧≥B滿足自反性、傳遞性。

3.3 集中有序關(guān)系擴展

上述的集中有序關(guān)系可應(yīng)用于離散灰數(shù)的信息處理，但不適用于連續(xù)灰數(shù)的處理，因此結(jié)合灰數(shù)測度的概念，對集中有序關(guān)系進(jìn)行擴展。

定義9給定灰色信息系統(tǒng)GS={U，A，V，f?}，Va、Ma分別表示屬性a的值域和標(biāo)準(zhǔn)值，對于 x，y∈U，f?(x，a)=Vax，f?(y，a)=Vay，若滿足Wax=μ(Vax∩Ma)≥μ(Vay∩Ma)=Way，則稱在屬性a∈A下，y優(yōu)于x，記為y?ax。

其中，Ma取Va的某中間段的區(qū)間灰數(shù)作為標(biāo)準(zhǔn)值。

對于x的優(yōu)勢類相應(yīng)地為：

3.4 優(yōu)勢度和屬性重要性度量

定義10[13-14]對于 xi，xj∈U ，對象 xi在屬性集 A下優(yōu)于對象xj的程度為：

顯然有0≤RA(xi，xj)≤1。

對象xi在屬性集A下的綜合優(yōu)勢度為：

其中0≤RA(xi)≤1，且 xi?Axj時，RA(xi)＞RA(xj)。RA(xi)的大小反映了xi在屬性集A下的優(yōu)勢程度。按照RA(xi)的大小排序后其序組成向量，記為rA=(r1，r2，…，rn)。

可見 sigB(a)≥0，若sigB(a)=0時，表明屬性a對 B是不必要的，否則其值越大，屬性a對B的重要性越大。

4 基于優(yōu)勢度的啟發(fā)式屬性約簡

知識約簡是粗糙集理論中的一個重要概念，根據(jù)擴展后的集中有序關(guān)系，以優(yōu)勢度作為屬性重要性的啟發(fā)信息，尋找一個能保持優(yōu)勢關(guān)系 R*≥下的最小屬性子集。因此下面討論灰色系統(tǒng)在優(yōu)勢關(guān)系R*≥下的屬性約簡方法。

定義12設(shè)GS={U，A，V，f?}是一個優(yōu)勢信息系統(tǒng)，?B?A，a∈B，屬性a對B的重要性為sigB(a)，當(dāng)sigB(a)＞0，說明a是B中必要的；當(dāng)sigB(a)=0，說明a是B中不必要的。若?a∈B都為B中必要的，則稱B為獨立的，否則，稱B是依賴的。

性質(zhì)1屬性a∈B在屬性集B中是必要的當(dāng)且僅當(dāng)sigB(a)＞0。

性質(zhì)2Core(B)={a∈B|sigB(a)＞0}。

算法描述：

根據(jù)性質(zhì)2求出信息系統(tǒng)中屬性A的核，其次選擇對核屬性重要性最大屬性依次加入核中，直到序向量各分量差值之和為0為止，得到一個最小約簡。

輸入 一個優(yōu)勢信息系統(tǒng)GS={U，A，V，f?}

輸出 該系統(tǒng)的核Core(A)和約簡Red(A)

步驟1給定一組標(biāo)準(zhǔn)值M，計算?xj∈U，?aj∈A下的。

步驟6輸出Core(A)和Red(A)，算法終止。

5 實例分析

表1[15]所示的是一個完備灰色信息系統(tǒng)，對象集U= {x1，x2，…，x6}，屬性集 A={a1，a2，a3，a4}，屬性集 A中的偏好屬性集中有序。其中，Va1=[0.3，0.9]，可取其中間分段作為 Ma1的標(biāo)準(zhǔn)值，即 Ma1=[0.5，0.7]，同理可令Ma2=[0.25，0.35]，Ma3=[0.4，0.5]，Ma4=[0.6，0.7]。

表1 一個完備灰色信息系統(tǒng)

步驟1根據(jù)定義9，計算各對象在優(yōu)勢關(guān)系R*≥下的Wxj

aj的值，如表2所示。

表2 計算結(jié)果

表2 計算結(jié)果

Wxj aj x1 x2 x3 x4 x5 x6 a1 0.1 0.1 0.1 0.2 0.2 0.1 a2 0.10 0.05 0.10 0.10 0.05 0.05 a3 0.1 0.1 0.1 0.1 0.1 0.1 a4 0.1 0.1 0.1 0 0.1 0.1

刪除屬性a3后，基于優(yōu)勢關(guān)系的集合均未發(fā)生變化，因此sigA(a3)=0。

步驟4將所有重要度大于0的屬性并入Core(A)，可得R=Core(A)={a1，a2，a4}。

例中信息系統(tǒng)的約簡結(jié)果與文獻(xiàn)[15]完全一致，通過計算屬性的重要度來確定核屬性，較文獻(xiàn)[15]通過分辨矩陣求核屬性，節(jié)省了大量的儲存空間。此外，約簡過程中采用迭代方法，利用減小選擇屬性集的大小提高了屬性約簡的效率。

6 結(jié)束語

由于現(xiàn)實應(yīng)用中，信息存在不完全性和復(fù)雜性。本文結(jié)合粗糙集和灰色系統(tǒng)理論兩種不確定信息處理工具的優(yōu)勢，探討了集中有序優(yōu)勢關(guān)系下灰色信息的分類，提出了一種基于優(yōu)勢度的啟發(fā)式屬性約簡算法，該算法能從搜索空間排除不重要的屬性，避免屬性重要性的重復(fù)計算，提高了搜索效率，為灰色信息系統(tǒng)的知識發(fā)現(xiàn)和規(guī)則提取提供了一種新的方法。

[1]Pawlak Z.Rough sets：theoretical aspects reasoning about data[M].Dordrecht，UK：Academic Publishers，1991.

[2]Greco S，Matarazzo B，Slowingski R.Rough sets theory for multicriteria decision analysis[J].European Journal of Operational Research，2001，129（1）：1-47.

[3]Greco S，Matarazzo B，Slowingskir.Rough approximation by dominance relation[J].International Journal of Intelligent Systems，2002，17（2）：153-171.

[4]徐偉華，張文修.基于優(yōu)勢關(guān)系下不協(xié)調(diào)目標(biāo)信息系統(tǒng)的知識約簡[J].計算機科學(xué)，2006，33（2）：182-184.

[5]Shao M W，Zhang W X.Dominance relation and rules in an incomplete ordered information system[J].International Journal of Intelligent Systems，2005，20（1）：13-27.

[6]張騰飛，魏立力.集中有序集值信息系統(tǒng)[J].計算機工程與應(yīng)用，2014，50（16）∶140-145.

[7]鄧聚龍.灰理論基礎(chǔ)[M].武漢：華中科技大學(xué)出版社，2002.

[8]Deng J L.Control problems of grey system[J].System& Control Letter，1982，1（5）：288-294.

[9]吳順祥.灰色粗糙集模型及其應(yīng)用[M].北京：科學(xué)出版社，2009.

[10]吳順祥，林理華，周志文.基于灰色信息系統(tǒng)的優(yōu)勢關(guān)系及其屬性約簡方法[J].廈門大學(xué)學(xué)報：自然科學(xué)版，2009，48（4）：482-488.

[11]陳子春，劉鵬惠，秦克云.集值信息系統(tǒng)基于優(yōu)勢關(guān)系下的知識約簡[J].計算機科學(xué)，2009，36（12）：176-193.

[12]林耀進(jìn)，李進(jìn)金，林夢雷.優(yōu)勢關(guān)系下的集值序值信息系統(tǒng)[J].計算機應(yīng)用，2011，31（12）：3240-3246.

[13]張文修，仇國芳.基于粗糙集的不確定決策[M].北京：清華大學(xué)出版社，2005.

[14]廖啟明，龍鵬飛.基于屬性重要性的粗糙集屬性約簡方法[J].計算機工程與應(yīng)用，2013，49（15）：130-132.

[15]林耀進(jìn)，李進(jìn)金，吳順祥，等.不完備灰色信息系統(tǒng)的粗集模型[J].計算機應(yīng)用，2010，30（2）：3374-3376.

JIN Lingling1,SU Li1,WANG Xifeng2

1.School of Mathematics and Statistics,Hainan Normal University,Haikou 571158,China
2.School of Computer Science,Anhui University of Technology,Ma’anshan,Anhui 243002,China

Attribute reduction is very important to knowledge acquisition in rough set theory.Considering the reality that many attributes values are uncertain in real information system,ordered concentration relation combined with gray system theory is expanded.A kind of preference relation that attribute values tend to the standard values is established in gray information system.The significance of attribute is defined and the degree of dominance is used as heuristic information. On this basis,the algorithm of attributes reduction is proposed to make it suitable for the information system which attributes valued continuous gray number.A practical operation method for computing reduction is given and the feasibility of algorithm is verified via case.

gray system;ordered concentration;dominance relation;knowledge reduction;standard value

屬性約簡是粗糙集理論進(jìn)行知識獲取的核心問題之一。針對現(xiàn)實信息系統(tǒng)中屬性值取值不確定的情況，結(jié)合灰色系統(tǒng)理論對集中有序關(guān)系進(jìn)行擴展，建立了灰色信息系統(tǒng)中趨于某個標(biāo)準(zhǔn)值的一種偏好關(guān)系，并以集中有序關(guān)系下的優(yōu)勢度為啟發(fā)式信息，給出了屬性的重要性度量，在此基礎(chǔ)上提出了適合于屬性值為連續(xù)灰數(shù)的信息系統(tǒng)的屬性約簡算法，給出了約簡的實際操作方法，并通過實例驗證了算法的可行性。

灰色系統(tǒng)；集中有序；優(yōu)勢關(guān)系；知識約簡；標(biāo)準(zhǔn)值

A

TP18

10.3778/j.issn.1002-8331.1302-0013

JIN Lingling,SU Li,WANG Xifeng.Knowledge reduction of gray information systems based on ordered concentration relation.Computer Engineering and Applications,2014,50（24）：139-142.

海南省自然科學(xué)基金（No.610221，No.114005）。

金玲玲（1976—），女，講師，研究領(lǐng)域為粗糙集理論與應(yīng)用；蘇莉（1982—），通訊作者，女，博士，講師，研究領(lǐng)域為粗糙集；王喜鳳（1980—），女，博士，研究領(lǐng)域為粗糙集，Web服務(wù)可靠性。E-mail：hnjll2003@126.com

2013-02-04

2013-04-03

1002-8331（2014）24-0139-04

CNKI網(wǎng)絡(luò)優(yōu)先出版：2013-04-18，http∶//www.cnki.net/kcms/detail/11.2127.TP.20130418.1618.013.html