金玲玲，蘇 莉，王喜鳳

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

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

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

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

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

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

1引言

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

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

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

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

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

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

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

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

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

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

（5）其他取Φ。

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

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

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

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

對(duì)于屬性集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)勢(shì)關(guān)系R≥B定義為：

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

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

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

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

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

顯然 R∧≥B滿(mǎn)足自反性、傳遞性。

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

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

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

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

對(duì)于x的優(yōu)勢(shì)類(lèi)相應(yīng)地為：

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

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

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

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

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

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

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

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

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

性質(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的核，其次選擇對(duì)核屬性重要性最大屬性依次加入核中，直到序向量各分量差值之和為0為止，得到一個(gè)最小約簡(jiǎn)。

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

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

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

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

5 實(shí)例分析

表1[15]所示的是一個(gè)完備灰色信息系統(tǒng)，對(duì)象集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 一個(gè)完備灰色信息系統(tǒng)

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

aj的值，如表2所示。

表2 計(jì)算結(jié)果

表2 計(jì)算結(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)勢(shì)關(guān)系的集合均未發(fā)生變化，因此sigA(a3)=0。

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

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

6 結(jié)束語(yǔ)

由于現(xiàn)實(shí)應(yīng)用中，信息存在不完全性和復(fù)雜性。本文結(jié)合粗糙集和灰色系統(tǒng)理論兩種不確定信息處理工具的優(yōu)勢(shì)，探討了集中有序優(yōu)勢(shì)關(guān)系下灰色信息的分類(lèi)，提出了一種基于優(yōu)勢(shì)度的啟發(fā)式屬性約簡(jiǎn)算法，該算法能從搜索空間排除不重要的屬性，避免屬性重要性的重復(fù)計(jì)算，提高了搜索效率，為灰色信息系統(tǒng)的知識(shí)發(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)勢(shì)關(guān)系下不協(xié)調(diào)目標(biāo)信息系統(tǒng)的知識(shí)約簡(jiǎn)[J].計(jì)算機(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].計(jì)算機(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)勢(shì)關(guān)系及其屬性約簡(jiǎn)方法[J].廈門(mén)大學(xué)學(xué)報(bào)：自然科學(xué)版，2009，48（4）：482-488.

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

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

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

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

[15]林耀進(jìn)，李進(jìn)金，吳順祥，等.不完備灰色信息系統(tǒng)的粗集模型[J].計(jì)算機(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

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

灰色系統(tǒng)；集中有序；優(yōu)勢(shì)關(guān)系；知識(shí)約簡(jiǎ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àn)榇植诩碚撆c應(yīng)用；蘇莉（1982—），通訊作者，女，博士，講師，研究領(lǐng)域?yàn)榇植诩?；王喜鳳（1980—），女，博士，研究領(lǐng)域?yàn)榇植诩?，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