基于貼近度的協(xié)調(diào)序決策系統(tǒng)屬性約簡(jiǎn)算法

孟慧麗,　張倩倩,　徐久成

(1.河南師范大學(xué) 計(jì)算機(jī)與信息工程學(xué)院　河南 新鄉(xiāng) 453007;2.河南省高校計(jì)算智能與數(shù)據(jù)挖掘工程技術(shù)研究中心　河南 新鄉(xiāng) 453007)

?

基于貼近度的協(xié)調(diào)序決策系統(tǒng)屬性約簡(jiǎn)算法

孟慧麗1,2,張倩倩1,2,徐久成1,2

(1.河南師范大學(xué) 計(jì)算機(jī)與信息工程學(xué)院河南 新鄉(xiāng) 453007;2.河南省高校計(jì)算智能與數(shù)據(jù)挖掘工程技術(shù)研究中心河南 新鄉(xiāng) 453007)

針對(duì)基于優(yōu)勢(shì)關(guān)系的協(xié)調(diào)序決策系統(tǒng)，定義了條件屬性集相對(duì)于決策屬性集的貼近度，并定義了協(xié)調(diào)序決策系統(tǒng)中屬性的重要度.提出了基于貼近度的啟發(fā)式屬性約簡(jiǎn)算法，通過(guò)實(shí)例分析證實(shí)了該算法的有效性.

協(xié)調(diào)序決策系統(tǒng)； 貼近度； 屬性約簡(jiǎn)

0　引言

粗糙集理論是一種能有效處理不精確、不確定信息的分析方法[1].屬性約簡(jiǎn)是粗糙集理論研究的重要內(nèi)容，通過(guò)刪除信息系統(tǒng)中不必要的屬性，可以從信息系統(tǒng)中獲取更加簡(jiǎn)潔的規(guī)則.經(jīng)典粗糙集理論主要基于等價(jià)關(guān)系對(duì)論域進(jìn)行劃分，在保持分類(lèi)能力不變的情況下對(duì)屬性集進(jìn)行約簡(jiǎn).但實(shí)際的生產(chǎn)生活中所產(chǎn)生的信息系統(tǒng)并不都是基于等價(jià)關(guān)系的，一些信息系統(tǒng)由于各種原因是基于優(yōu)勢(shì)關(guān)系的，優(yōu)勢(shì)關(guān)系放松了對(duì)命題的條件和結(jié)論的要求，有著更廣泛的應(yīng)用范圍.

針對(duì)基于優(yōu)勢(shì)關(guān)系的序信息系統(tǒng)、序決策系統(tǒng)已經(jīng)有較多研究，提出了多種不同的屬性約簡(jiǎn)算法，但這些算法主要針對(duì)序信息系統(tǒng)[2-7]及不協(xié)調(diào)序決策系統(tǒng)[8-13].協(xié)調(diào)序決策系統(tǒng)的屬性約簡(jiǎn)既不同于序信息系統(tǒng)的屬性約簡(jiǎn)，也不同于不協(xié)調(diào)序決策系統(tǒng)的屬性約簡(jiǎn).目前針對(duì)協(xié)調(diào)序決策系統(tǒng)的屬性約簡(jiǎn)的研究較少.文獻(xiàn)[14]定義了完備信息系統(tǒng)的劃分貼近度，并設(shè)計(jì)了基于劃分貼近度的屬性約簡(jiǎn)算法，但劃分貼近度并不直接適用于基于優(yōu)勢(shì)關(guān)系的序決策系統(tǒng).本文將文獻(xiàn)[14]中的貼近度思想引入基于優(yōu)勢(shì)關(guān)系的協(xié)調(diào)序決策系統(tǒng)，定義了協(xié)調(diào)序決策系統(tǒng)中條件屬性集相對(duì)于決策屬性集的貼近度，設(shè)計(jì)了基于貼近度的協(xié)調(diào)序決策系統(tǒng)的啟發(fā)式屬性約簡(jiǎn)算法,并通過(guò)實(shí)例分析證實(shí)了該屬性約簡(jiǎn)算法的有效性.

1　基于優(yōu)勢(shì)關(guān)系的協(xié)調(diào)序決策系統(tǒng)

定義2[1]設(shè)S=(U,C∪D,V,f)為決策系統(tǒng)，C為條件屬性集，D為決策屬性集.對(duì)于B?C，令

RB={(xi,xj)∈U×U：fa(xi)≤fa(xj), ?a∈B},

(1)

RD={(xi,xj)∈U×U：fd(xi)≤fd(xj),?d∈D},

(2)

稱(chēng)RB為決策系統(tǒng)S=(U,C∪D,V,f)條件屬性集上的優(yōu)勢(shì)關(guān)系，RD為決策屬性集上的優(yōu)勢(shì)關(guān)系，此時(shí)該信息系統(tǒng)稱(chēng)為基于優(yōu)勢(shì)關(guān)系的序決策系統(tǒng).

記：

(3)

(4)

(5)

(6)

定義3[1]設(shè)S=(U,C∪D,V,f)為序決策系統(tǒng)，C為條件屬性集，D為決策屬性集.若優(yōu)勢(shì)關(guān)系RC?RD成立，則稱(chēng)S=(U,C∪D,V,f)為協(xié)調(diào)的，否則，稱(chēng)S=(U,C∪D,V,f)為不協(xié)調(diào)的.

定義4[1]設(shè)S=(U,C∪D,V,f)為協(xié)調(diào)序決策系統(tǒng)，C為條件屬性集，D為決策屬性集.B?C，若有RB?RD，且對(duì)于?b∈B，優(yōu)勢(shì)關(guān)系RB-?RD不成立，則稱(chēng)B是協(xié)調(diào)序決策系統(tǒng)S=(U,C∪D,V,f)在優(yōu)勢(shì)關(guān)系下的一個(gè)約簡(jiǎn).

2　基于貼近度的協(xié)調(diào)序決策系統(tǒng)屬性約簡(jiǎn)

定義5設(shè)S=(U,C∪D,V,f)為協(xié)調(diào)序決策系統(tǒng)，C為條件屬性集，D為決策屬性集，B?C，對(duì)?x∈U，定義

(7)

為對(duì)象x在條件屬性集B下的優(yōu)勢(shì)等價(jià)類(lèi)相對(duì)x在決策屬性集D下的優(yōu)勢(shì)決策類(lèi)中的貼近度.

定義6設(shè)S=(U,C∪D,V,f)為協(xié)調(diào)序決策系統(tǒng)，C為條件屬性集，D為決策屬性集，B?C，定義

(8)

為條件屬性集B相對(duì)于決策屬性集D的貼近度.

3　基于貼近度的協(xié)調(diào)序決策系統(tǒng)屬性約簡(jiǎn)算法

基于協(xié)調(diào)序決策系統(tǒng)中條件屬性集相對(duì)于決策屬性集的貼近度，設(shè)計(jì)了協(xié)調(diào)序決策系統(tǒng)的屬性約簡(jiǎn)算法，算法從條件屬性集中依次選擇一個(gè)屬性，計(jì)算從條件屬性集中去掉該屬性后，條件屬性集相對(duì)于決策屬性集的貼近度，如果貼近度不變，則從條件屬性集中去掉該屬性.基于貼近度的協(xié)調(diào)序決策系統(tǒng)屬性約簡(jiǎn)算法步驟如下：

輸入： 協(xié)調(diào)序決策系統(tǒng)S=(U,C∪D,V,f)，U={x1,x2,…,xn}，C={c1,c2,…,cm}.

輸出： 協(xié)調(diào)序決策系統(tǒng)條件屬性集C的一個(gè)約簡(jiǎn)B.

Step 5輸出約簡(jiǎn)B，算法結(jié)束.

4　實(shí)例分析

表1是文獻(xiàn)[1]中的一個(gè)協(xié)調(diào)序決策系統(tǒng)，U={x1,x2,x3,x4,x5,x6},C={c1,c2,c3},D=j5i0abt0b,根據(jù)文獻(xiàn)[1]中的區(qū)分矩陣，可以得到該協(xié)調(diào)序決策系統(tǒng)的約簡(jiǎn)為{c1}或{c2,c3}，根據(jù)本文算法同樣可以計(jì)算得到該系統(tǒng)的一個(gè)約簡(jiǎn).

表1　協(xié)調(diào)序決策系統(tǒng)Tab.1　Consistent ordered decision system

5　小結(jié)

將貼近度引入到基于優(yōu)勢(shì)關(guān)系的協(xié)調(diào)序決策系統(tǒng)，針對(duì)基于優(yōu)勢(shì)關(guān)系的協(xié)調(diào)序決策系統(tǒng)的屬性約簡(jiǎn)進(jìn)行研究，提出基于貼近度的協(xié)調(diào)序決策系統(tǒng)的啟發(fā)式屬性約簡(jiǎn)算法，豐富了基于優(yōu)勢(shì)關(guān)系的粗糙集理論，為基于優(yōu)勢(shì)關(guān)系的協(xié)調(diào)序決策系統(tǒng)的知識(shí)發(fā)現(xiàn)與獲取提供了理論基礎(chǔ).

[1]張文修，梁怡，吳偉志.信息系統(tǒng)與知識(shí)發(fā)現(xiàn)[M].北京：科學(xué)出版社， 2003.

[2]王鋒,錢(qián)宇華,梁吉業(yè).序信息系統(tǒng)的啟發(fā)式屬性約簡(jiǎn)算法[J].計(jì)算機(jī)科學(xué),2010,37(1): 258-260.

[3]韋碧鵬,呂躍進(jìn),李金海.基于α優(yōu)勢(shì)關(guān)系粗糙集模型的屬性約簡(jiǎn)[J].智能系統(tǒng)學(xué)報(bào),2014,9(1):1-9.

[4]廖帆,滕書(shū)華,邵世雷.基于優(yōu)勢(shì)關(guān)系的啟發(fā)式屬性約簡(jiǎn)算法[J].計(jì)算機(jī)工程,2011,37(24):52-54.

[5]呂躍進(jìn),韋碧鵬,胡明明.基于相對(duì)優(yōu)勢(shì)類(lèi)差量的序信息系統(tǒng)屬性約簡(jiǎn)算法[J].模糊系統(tǒng)與數(shù)學(xué),2013,27(1): 142-148.

[6]孟慧麗，趙曉焱，徐久成.序信息系統(tǒng)的貼近度及屬性約簡(jiǎn)算法[J].計(jì)算機(jī)科學(xué)，2014，41(12):189-191.

[7]鮑忠奎,楊善林.基于新特征優(yōu)勢(shì)關(guān)系的知識(shí)約簡(jiǎn)模型[J].小型微型計(jì)算機(jī)系統(tǒng),2013,34(8):1858-1861.

[8]GOU G L,WANG G Y.Inconsistent dominance principle based attribute reduction in ordered information systems[C]// 10th International Conference on Rough Sets and Knowledge Technology.Tianjin,2015: 110-118.

[9]翁世洲,呂躍進(jìn).不協(xié)調(diào)序決策系統(tǒng)的協(xié)調(diào)修正算法[J].模式識(shí)別與人工智能，2015,28(2)：116-122.

[10]陳娟,王國(guó)胤,胡軍.優(yōu)勢(shì)關(guān)系下不協(xié)調(diào)信息系統(tǒng)的正域約簡(jiǎn)[J].計(jì)算機(jī)科學(xué),2008,35(3):216-218.

[11]徐偉華,張曉燕,張文修.優(yōu)勢(shì)關(guān)系下不協(xié)調(diào)目標(biāo)信息系統(tǒng)的部分一致約簡(jiǎn)[J].模糊系統(tǒng)與數(shù)學(xué),2009,23(6):155-161.

[12]莫京蘭,朱廣生,呂躍進(jìn).不協(xié)調(diào)優(yōu)勢(shì)目標(biāo)信息系統(tǒng)的啟發(fā)式下近似約簡(jiǎn)[J].計(jì)算機(jī)工程,2012,38(17): 52-55.

[13]XU W H,LI Y,LIAO X W.Approaches to attribute reductions based on rough set and matrix computation in inconsistent ordered information systems[J].Knowledge-based systems,2012,27(3):78-91.

[14]徐久成,孟慧麗,郭林鵬,等.粗糙集的劃分貼近度及基于劃分貼近度的屬性約簡(jiǎn)算法[J].計(jì)算機(jī)科學(xué),2008,35(3):213-215.

(責(zé)任編輯：孔薇)

Attribute Reduction Algorithm of Consistent Ordered Decision System Based on the Close-degree

MENG Huili1,2,ZHANG Qianqian1,2,XU Jiucheng1,2

(1.CollegeofComputerandInformationEngineering,HenanNormalUniversity,Xinxiang453007,China； 2.EngineeringTechnologyResearchCenterforComputingIntelligenceandDataMiningofHenanProvince,Xinxiang453007,China)

The close-degree was introduced into the consistent ordered decision system which was based on the dominance relation.The close-degree of condition attributes relative to decision attributes in the consistent ordered decision system was defined.The significance of attribute was also defined,and a heuristic attribute reduction algorithm based on the close-degree was proposed.The validity of the algorithm was tested by an example,and the results showed that the algorithm was efficient for the attribute reduction of consistent ordered decision system.

consistent ordered decision system； close-degree； attribute reduction

2016-04-01

國(guó)家自然科學(xué)基金資助項(xiàng)目(60873104,61370169)；河南省科技攻關(guān)重點(diǎn)項(xiàng)目(112102210194).

孟慧麗(1978—)，女，河南新鄉(xiāng)人，講師，主要從事粗糙集理論及數(shù)據(jù)挖掘研究，E-mail:menghuili93@163.com；通訊作者：徐久成(1963—)，男，河南洛陽(yáng)人，教授，主要從事數(shù)據(jù)挖掘及生物信息學(xué)研究.

TP18

A

1671-6841(2016)03-0090-04

10.13705/j.issn.1671-6841.2016068

引用本文：孟慧麗，張倩倩，徐久成.基于貼近度的協(xié)調(diào)序決策系統(tǒng)屬性約簡(jiǎn)算法[J].鄭州大學(xué)學(xué)報(bào)(理學(xué)版)，2016，48(3)：90-93.