基于聚類與?；攘康母咝Q策表約簡(jiǎn)

李敏 楊亞鋒 李麗紅

摘要：屬性約簡(jiǎn)是粗糙集理論的核心內(nèi)容之一，傳統(tǒng)的屬性約簡(jiǎn)每次只考慮去掉一個(gè)屬性后對(duì)原來(lái)知識(shí)系統(tǒng)的影響，或者利用區(qū)分函數(shù)進(jìn)行約簡(jiǎn)，但是當(dāng)數(shù)據(jù)集較大時(shí)，區(qū)分函數(shù)范式轉(zhuǎn)換獲得解集具有一定的困難性，降低約簡(jiǎn)效率。針對(duì)決策系統(tǒng)的屬性約簡(jiǎn)與高效決策的粒度選擇問(wèn)題，將粒化度量和聚類相結(jié)合，由聚類結(jié)果選擇粒結(jié)構(gòu)，再由?；攘康玫礁髁＝Y(jié)構(gòu)的重要度，從而進(jìn)行屬性約簡(jiǎn)。考慮同時(shí)去掉多個(gè)屬性，提高了效率;最后結(jié)合實(shí)例驗(yàn)證此方法約簡(jiǎn)與利用區(qū)分矩陣的方法約簡(jiǎn)結(jié)果一致。

關(guān)鍵詞：屬性約簡(jiǎn);?；??；匾?區(qū)分矩陣

中圖分類號(hào)：TP18? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2019）26-0246-03

開放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

隨著現(xiàn)實(shí)世界中不確定信息的不斷增加，粗糙集[1]、模糊集等這些處理不精確、不一致，不完整信息的數(shù)學(xué)工具受到越來(lái)越多人的關(guān)注，粗糙集理論是利用屬性約簡(jiǎn)、信息熵[2]等概念來(lái)確定信息表達(dá)系統(tǒng)中差別屬性的重要性 ，簡(jiǎn)化知識(shí)表達(dá)空間，并從數(shù)據(jù)中挖掘特征規(guī)則，通常是通過(guò)刪除冗余屬性來(lái)實(shí)現(xiàn)的。粒計(jì)算方法是以粒為求解問(wèn)題的基本單位，人類在處理大量復(fù)雜信息時(shí)，由于人類認(rèn)知能力有限，往往會(huì)把大量復(fù)雜信息按其各自特征和性能將其劃分為若干較為簡(jiǎn)單的塊，每個(gè)被分出來(lái)的塊就被看成是一個(gè)粒，這樣處理信息的過(guò)程就稱為信息?；?979年Zadeh提出信息粒度之后，研究人員便對(duì)信息粒度化的思想產(chǎn)生了濃厚的興趣，其中將粒化問(wèn)題與屬性約簡(jiǎn)相結(jié)合，從相關(guān)實(shí)際問(wèn)題的研究背景出發(fā)，提出了多種信息系統(tǒng)屬性約簡(jiǎn)的方法。史進(jìn)玲，張倩倩，徐久成提出了多粒度決策系統(tǒng)屬性約簡(jiǎn)的最優(yōu)粒度選擇[3];朱紅，丁世飛在基于屬性區(qū)分能力和AP聚類的基礎(chǔ)上，給出了屬性?；姆椒╗4];將二進(jìn)制粒與粒計(jì)算結(jié)合，陳玉明等人提出了基于二進(jìn)制粒與粒計(jì)算的屬性約簡(jiǎn)[5];文獻(xiàn)[6-10]給出了基于粒計(jì)算，多粒度和鄰域熵下的屬性約簡(jiǎn)。近年來(lái)，知識(shí)粒度作為一種新的屬性約簡(jiǎn)方式受到研究人員們的關(guān)注，因此本文采用二進(jìn)制粒對(duì)決策表進(jìn)行?；?，計(jì)算屬性之間的相對(duì)依賴度及距離進(jìn)行聚類;然后根據(jù)聚類結(jié)果選擇粒結(jié)構(gòu)，計(jì)算不同粒結(jié)構(gòu)下的粒集，再由?；攘康玫礁髁＝Y(jié)構(gòu)的重要度，進(jìn)行屬性約簡(jiǎn)，最后結(jié)合實(shí)例驗(yàn)證方法的合理性。

1 基本知識(shí)

1.1屬性約簡(jiǎn)相關(guān)概念

粗糙集中由于知識(shí)庫(kù)里的屬性并不是同等重要的，甚至其中某些屬性是冗余的，不利于分析問(wèn)題，因此使得屬性約簡(jiǎn)成為粗糙集理論比較重要的內(nèi)容，有著廣泛的應(yīng)用價(jià)值，屬性約簡(jiǎn)即在保持知識(shí)庫(kù)分類能力不變的條件下，刪除其中不相關(guān)或不重要的屬性。

1.2 屬性粒化相關(guān)概念

為了更好地剖析和解決復(fù)雜的問(wèn)題，粒計(jì)算將其抽象化為簡(jiǎn)單的問(wèn)題，信息粒在我們實(shí)際生活中普遍存在，抽象概括了現(xiàn)實(shí)問(wèn)題。粒化是將總體分解為部分，信息粒化反映了人類如何處理和存儲(chǔ)信息。

3 實(shí)例分析

例：給定一個(gè)決策表[S=（U，A，V，f）]：其中對(duì)象集合[U={1，2，3，4，5}]，條件屬性集[A={a，b，c，d}]，決策屬性為[D]，如表1所示。試化簡(jiǎn)該決策表，并求出約簡(jiǎn)。

第三步：根據(jù)屬性之間的相對(duì)依賴度，計(jì)算屬性之間的距離，并根據(jù)距離關(guān)系進(jìn)行聚類。

計(jì)算屬性[a]與其他屬性之間的距離之和為[ab+ac+ad≈3.0115]，同理屬性[b]與其它屬性距離之和為3.5804，屬性[c]與其它屬性距離之和為4.0048，屬性[d]與其它屬性距離之和為2.7268。根據(jù)距離關(guān)系，將屬性聚類為兩類：[{a，d}]、[{c，b}]。

第六步：通過(guò)區(qū)分矩陣的方法驗(yàn)證合理性

依據(jù)決策表可以得到對(duì)應(yīng)的區(qū)分矩陣，如表所示：

得到該決策系統(tǒng)的屬性約簡(jiǎn)集合也為[{a，b}]或[{b，d}]，從而驗(yàn)證了此方法的合理性。

4 結(jié)論

以往的決策表屬性約簡(jiǎn)的研究有基于信息熵、博弈論、區(qū)分矩陣等進(jìn)行的，但是大多都基于等價(jià)關(guān)系給出，這種單一的方法不符合大數(shù)據(jù)時(shí)代所要求的效率問(wèn)題。因此針對(duì)以上不足，本文基于?；攘颗c屬性重要度考慮同時(shí)去掉多個(gè)屬性，為屬性約簡(jiǎn)開辟了新的途徑，使得約簡(jiǎn)更加高效;本文所提出的算法中如果決策表里有新增加的屬性，只需計(jì)算該屬性與其他屬性的依賴程度和距離，重新考慮聚類，再計(jì)算?；攘亢土；匾冗M(jìn)行約簡(jiǎn)即可，同時(shí)也適用于動(dòng)態(tài)約簡(jiǎn)，比傳統(tǒng)的約簡(jiǎn)算法節(jié)省了時(shí)間。

本文只是以一個(gè)簡(jiǎn)單實(shí)例給出了可以多個(gè)屬性同時(shí)約簡(jiǎn)的新方法，依然還有很多值得提高的地方，比如是否可以找到更合適的屬性聚類的方法與?；攘拷Y(jié)合，或者大數(shù)據(jù)時(shí)代何時(shí)選用這種方法等問(wèn)題，這需要我們以后繼續(xù)深入研究，給出更加合理有效的約簡(jiǎn)算法。

參考文獻(xiàn)：

[1] 劉保相.粗糙集對(duì)分析理論與決策模型[M].北京：科學(xué)出版社，2010：11-55.

[2] 于迎春.覆蓋粗糙集中基于信息熵的幾個(gè)定義[J].商業(yè)文化，2012（2）：344.

[3] 史進(jìn)玲，張倩倩，徐久成.多粒度決策系統(tǒng)屬性約簡(jiǎn)的最優(yōu)粒度選擇[J].計(jì)算機(jī)科學(xué)，2018，45（2）：153-156.

[4] 朱紅，丁世飛.基于屬性區(qū)分能力和AP聚類的屬性?；椒╗J].計(jì)算機(jī)科學(xué)，2016，43（2）：95-97.

[5] 陳玉明，苗奪謙，焦娜.基于二進(jìn)制粒與粒計(jì)算的屬性約簡(jiǎn).廣西師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2008，26（2）：81-84.

[6] 胡清華，于達(dá)仁，謝宗霞.基于鄰域粒化和粗糙逼近的數(shù)值屬性約簡(jiǎn)[J].軟件學(xué)報(bào)，2008，19（3）：640-649.

[7] 楊田，伍秀華，王玉芳.覆蓋粗糙集屬性約簡(jiǎn)的新算法[J].模糊系統(tǒng)與數(shù)學(xué)，2013，27（2）：183-190.

[8] 許晴媛，李進(jìn)金，張燕蘭.覆蓋決策信息系統(tǒng)的約簡(jiǎn)[J].山東大學(xué)學(xué)報(bào) （理學(xué)版），2010，45（1）：89-93.

[9] 譚安輝，李進(jìn)金，吳偉志. 多粒度粗糙集和覆蓋粗糙集間的近似與約簡(jiǎn)關(guān)系[J].模式識(shí)別與人工智能2016，29（8）：691-697.

[10] 張小紅，裴道武，代建華.模糊數(shù)學(xué)與rough集理論[M].北京：清華大學(xué)出版社，2013：264-265.

[11] 秦克云，敬思惠.決策系統(tǒng)基于不可區(qū)分關(guān)系及區(qū)分關(guān)系的約簡(jiǎn)[J].計(jì)算機(jī)科學(xué)，2018，45（6）：247-250.

[12] 顧沈明，萬(wàn)雅虹，吳偉志，等.多粒度決策系統(tǒng)的局部最優(yōu)粒度選擇[J].南京大學(xué)學(xué)報(bào)（自然科學(xué)），2016，52（2）：280-288.

【通聯(lián)編輯：唐一東】