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

金玲玲，蘇 莉，王喜鳳

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

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

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

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

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

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

1引言

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

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

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

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

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

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

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

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

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

定義3設灰數(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對應的灰數(shù)，記作ua(?)。

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

3.1 優(yōu)勢關系

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

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

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

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

3.2 集中有序關系

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

其中，Ma取Va的某個中間值作為標準值。

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

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

3.3 集中有序關系擴展

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

定義9給定灰色信息系統(tǒng)GS={U，A，V，f?}，Va、Ma分別表示屬性a的值域和標準值，對于 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ù)作為標準值。

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

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ù)擴展后的集中有序關系，以優(yōu)勢度作為屬性重要性的啟發(fā)信息，尋找一個能保持優(yōu)勢關系 R*≥下的最小屬性子集。因此下面討論灰色系統(tǒng)在優(yōu)勢關系R*≥下的屬性約簡方法。

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

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

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

算法描述：

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

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

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

步驟1給定一組標準值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的標準值，即 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)勢關系R*≥下的Wxj

aj的值，如表2所示。

表2 計算結果

表2 計算結果

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)勢關系的集合均未發(fā)生變化，因此sigA(a3)=0。

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

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

6 結束語

由于現(xiàn)實應用中，信息存在不完全性和復雜性。本文結合粗糙集和灰色系統(tǒng)理論兩種不確定信息處理工具的優(yōu)勢，探討了集中有序優(yōu)勢關系下灰色信息的分類，提出了一種基于優(yōu)勢度的啟發(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)勢關系下不協(xié)調目標信息系統(tǒng)的知識約簡[J].計算機科學，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].計算機工程與應用，2014，50（16）∶140-145.

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

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

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

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

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

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

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

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

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

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

灰色系統(tǒng)；集中有序；優(yōu)勢關系；知識約簡；標準值

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.

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

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

2013-02-04

2013-04-03

1002-8331（2014）24-0139-04

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