陶加云，李英順，趙玉鑫

（1.沈陽(yáng)工業(yè)大學(xué)信息科學(xué)與工程學(xué)院，遼寧沈陽(yáng)110870；2.沈陽(yáng)工業(yè)大學(xué)化工過程自動(dòng)化學(xué)院，遼寧遼陽(yáng)111003）

一種改進(jìn)的啟發(fā)式最優(yōu)相對(duì)屬性約簡(jiǎn)算法

陶加云1，李英順2，趙玉鑫2

（1.沈陽(yáng)工業(yè)大學(xué)信息科學(xué)與工程學(xué)院，遼寧沈陽(yáng)110870；2.沈陽(yáng)工業(yè)大學(xué)化工過程自動(dòng)化學(xué)院，遼寧遼陽(yáng)111003）

針對(duì)在傳統(tǒng)的粗糙集理論相對(duì)屬性約簡(jiǎn)算法中因需計(jì)算可區(qū)別矩陣和正區(qū)域而導(dǎo)致的約簡(jiǎn)效率低下這一問題，提出一種改進(jìn)的啟發(fā)式最優(yōu)相對(duì)屬性約簡(jiǎn)算法加以解決.通過引入屬性集的相對(duì)分類能力的定義給出相對(duì)屬性約簡(jiǎn)的判定條件，在此基礎(chǔ)上導(dǎo)出的改進(jìn)相對(duì)屬性約簡(jiǎn)算法既能保證約簡(jiǎn)過后的條件屬性是最優(yōu)的，又能提高約簡(jiǎn)效率.實(shí)際算例結(jié)果以及對(duì)比實(shí)驗(yàn)體現(xiàn)了該算法的高效性.

粗糙集理論；改進(jìn)最優(yōu)相對(duì)屬性約簡(jiǎn)；判定條件

粗糙集理論誕生于20世紀(jì)80年代初期，是一種能有效分析和處理不精確、不完整信息的數(shù)據(jù)分析工具[1].該理論在近十多年來日益受到國(guó)內(nèi)外專家學(xué)者的重視，對(duì)其研究也在不斷加深，并且已經(jīng)成功運(yùn)用在機(jī)器學(xué)習(xí)、人工智能與知識(shí)工程、故障診斷、信息系統(tǒng)決策支持等領(lǐng)域[2-4].約簡(jiǎn)是粗糙集理論的核心內(nèi)容之一，是粗糙集理論能否成功運(yùn)用到工程實(shí)踐中的關(guān)鍵，其主要內(nèi)容是在保持知識(shí)庫(kù)分類能力不變的前提下導(dǎo)出決策規(guī)則.對(duì)決策系統(tǒng)屬性集的約簡(jiǎn)稱為屬性約簡(jiǎn)，而尋求到所有約簡(jiǎn)后的屬性已被證明是一個(gè)NP-hard問題[5].

高效的屬性約簡(jiǎn)算法是粗糙集理論完成數(shù)據(jù)約簡(jiǎn)的基礎(chǔ)和保障.文獻(xiàn)[6]利用傳統(tǒng)的基于可區(qū)別矩陣的相對(duì)屬性約簡(jiǎn)算法對(duì)綜合傳動(dòng)裝置的故障數(shù)據(jù)進(jìn)行約簡(jiǎn)，算例的結(jié)果中出現(xiàn)了兩個(gè)約簡(jiǎn)值，雖然都能導(dǎo)出決策規(guī)則，但是可信度卻受到影響，并且計(jì)算量大.文獻(xiàn)[7]提出了一種改進(jìn)的基于屬性頻率度的約簡(jiǎn)算法，該算法使得約簡(jiǎn)的計(jì)算量有所減少，但是不能保證求得的約簡(jiǎn)后的屬性個(gè)數(shù)是最少的.在實(shí)際運(yùn)用中所需要屬性個(gè)數(shù)往往是越少越好，且計(jì)算量越小越好，這樣便于得到精簡(jiǎn)的規(guī)則集，從而提高解決問題的效率.因此，文章通過引入屬性集的相對(duì)分類能力的定義來給出相對(duì)屬性約簡(jiǎn)的判定條件，在此基礎(chǔ)上定義屬性重要度，并將它作為改進(jìn)的最優(yōu)相對(duì)屬性約簡(jiǎn)算法的啟發(fā)式信息，以便于減小搜索空間，提高相對(duì)屬性約簡(jiǎn)效率.實(shí)際算例結(jié)果證實(shí)了該算法不僅高效，而且能夠保證約簡(jiǎn)后的屬性個(gè)數(shù)是最少、最優(yōu)的.

1 粗糙集基礎(chǔ)理論

定義1 設(shè)四元組信息表達(dá)系統(tǒng)其中U代表包含所有對(duì)象的非空有限集，被稱為論域；R代表屬性集，R=( ) r1,r2,r3,…,rm= C?D,C?D≠?,C代表?xiàng)l件屬性集，U代表決策屬性集；V=?r∈RVr，Vr代表屬性r的值域；f∶U×R→V為一全函數(shù)，它賦予每一對(duì)象對(duì)應(yīng)的每一屬性一個(gè)信息值.此時(shí)，稱上述信息表達(dá)系統(tǒng)S為決策表.

定義2設(shè)信息表達(dá)系統(tǒng)A為屬性集R的一個(gè)子集，亦即A?R,定義一不可分辨關(guān)系ind(A),且：

定義3設(shè)S中的集合U上任意一個(gè)不可分辨關(guān)系和任意一個(gè)子集X,定義X關(guān)于Q的下、上近似集分別為：

定義4設(shè)P和T為定義在論域U上的兩個(gè)等價(jià)關(guān)系簇，T的P正域記為POSP(T)，此時(shí)，

定義5設(shè)Ω和Θ為定義在論域U上的兩個(gè)等價(jià)關(guān)系簇，設(shè)G?Ω,G為Ω的Θ約簡(jiǎn)當(dāng)且僅當(dāng)G為 Ω的 Θ獨(dú)立子簇，并且滿足 POSG(Θ)= POSΩ(Θ)時(shí)，就稱Ω的Θ約簡(jiǎn)為相對(duì)約簡(jiǎn).

2 基于粗糙集理論的改進(jìn)最優(yōu)相對(duì)屬性約簡(jiǎn)算法

2.1 屬性集相對(duì)分類能力的引入

粗糙集理論是在等價(jià)關(guān)系的基礎(chǔ)上建立的，這些等價(jià)關(guān)系[8]對(duì)特定的數(shù)據(jù)空間進(jìn)行劃分.劃分準(zhǔn)則可以看作一種粗糙的知識(shí)，知識(shí)的粒度越大越粗糙，可用度相對(duì)而言也就越小，反之就越大.以下就等價(jià)關(guān)系分類能力這一觀點(diǎn)，給出定義等價(jià)關(guān)系相對(duì)分類能力的表達(dá)方式.

定義6給定一相容決策系統(tǒng)，則條件屬性集C相對(duì)于決策屬性集D的分類能力記為M(U,C/D),且

性質(zhì)1：給定相容決策系統(tǒng)?R?C,則POSC(U,D)=POSR(U,D)成立的充要條件為

設(shè)R?C,r∈R,結(jié)合上述定義6及其性質(zhì)可推導(dǎo)出屬性集R是條件屬性集C關(guān)于決策屬性集D的一個(gè)相對(duì)約簡(jiǎn)的充要條件是：

由上述性質(zhì)可得：

POSC(U,D)=POSR-{r}(U,D)

這與R是條件屬性集C關(guān)于決策屬性集D的一個(gè)約簡(jiǎn)矛盾.因此，得證：對(duì)于?r∈R,有：

POSC(U,D)=POSR(U,D)

上述證明的充要條件即為相對(duì)屬性約簡(jiǎn)的判定條件，是最優(yōu)屬性約簡(jiǎn)算法的基礎(chǔ).

2.2 改進(jìn)最優(yōu)屬性約簡(jiǎn)算法描述

在傳統(tǒng)的啟發(fā)式相對(duì)屬性約簡(jiǎn)算法的基礎(chǔ)上引入了相對(duì)分類能力和屬性重要度的定義，既可在一定的程度上減小計(jì)算量，又能保證約簡(jiǎn)過后的屬性集是最精簡(jiǎn)的.算法的主要內(nèi)容如下：

輸出：相容決策系統(tǒng)DS的一個(gè)最優(yōu)相對(duì)屬性約簡(jiǎn)集.

對(duì)算法中出現(xiàn)的部分符號(hào)的說明：

（Ⅰ）Red：算法的輸出結(jié)果；

（Ⅱ） Div||Red：論域U的劃分，亦即

（Ⅲ）Div：論域U的劃分；

（Ⅳ）SGF(a,S,D)：屬性重要度.

步驟3：設(shè)屬性a∈S,S為C中的某一屬性集，S?C, U1=U，將a按SGF(a,S,D)升序排列，并將排列結(jié)果記為

步驟4：Fork=1;k＜|c|+1;k++；

步驟5：令Div={U1}，其中U1=U；

步驟6：對(duì)于屬性集Red,從后往前對(duì)每個(gè)屬性a進(jìn)行判斷，看它們是否可省，具體說明如下：

步驟7：輸出最終的Red.

2.3 算法的時(shí)間復(fù)雜度分析

首先給出并證明如下性質(zhì)：

證明：任意的且?x,y∈P,有f(x ,S?T)=f(y ,S?T),因此又有 f(x,S)= f(y,S)和 f(x,T)=f(y,T),即存在 Si?Tj使得P?Si?Tj.又知，有 f(x,Si?Tj)=f(y,Si?Tj),因此可得出P=Si?Tj.同理，對(duì)于任意的Si?Tj,存在使得 Si?Tj=P.綜上可得證

由上述改進(jìn)最優(yōu)屬性約簡(jiǎn)算法可知，其步驟1-5的時(shí)間復(fù)雜度為O(|C ||U|2)，又由如上性質(zhì)可以求得步驟6的時(shí)間復(fù)雜度為O(|C ||U|2)，因此，改進(jìn)最優(yōu)相對(duì)屬性約簡(jiǎn)算法的總的時(shí)間復(fù)雜度為：

O(|C ||U|2).

3 實(shí)驗(yàn)結(jié)果及分析

本文以客戶關(guān)系管理情況評(píng)價(jià)表的相關(guān)數(shù)據(jù)為例來對(duì)算法進(jìn)行分析.選擇30個(gè)比較典型的評(píng)價(jià)數(shù)據(jù)來作為樣本數(shù)據(jù)，建立如表1所示的客戶評(píng)價(jià)數(shù)據(jù)表.其中，條件屬性C={c1,c2,c3,c4,c5}={產(chǎn)品能力認(rèn)知，管理水平評(píng)價(jià)，服務(wù)質(zhì)量，客戶情感，責(zé)任感表現(xiàn)} ，決策屬性D為客戶滿意度.條件屬性值1-5分別代表“差”“一般”“好”“很好”“最好”，決策屬性值A(chǔ)-C分別代表“高”“較高”和“一般”.

表1 客戶評(píng)價(jià)數(shù)據(jù)表

選用機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)中的客戶評(píng)價(jià)數(shù)據(jù)集，分別利用改進(jìn)最優(yōu)相對(duì)屬性約簡(jiǎn)算法和傳統(tǒng)的啟發(fā)式相對(duì)屬性約簡(jiǎn)算法對(duì)表1中的數(shù)據(jù)進(jìn)行了25次實(shí)驗(yàn)，本文所提算法的約簡(jiǎn)結(jié)果如表2所示.

表2 文章所提算法的約簡(jiǎn)結(jié)果

傳統(tǒng)的啟發(fā)式相對(duì)屬性約簡(jiǎn)結(jié)果如表3所示.

表3 傳統(tǒng)的啟發(fā)式相對(duì)屬性約簡(jiǎn)結(jié)果

實(shí)驗(yàn)結(jié)果比較情況如表4所示.

表4 實(shí)驗(yàn)結(jié)果比較情況

從表4中的數(shù)據(jù)可以明顯看出，采用改進(jìn)最優(yōu)相對(duì)屬性約簡(jiǎn)算法比統(tǒng)的啟發(fā)式相對(duì)屬性約簡(jiǎn)算法在快4.7s的同時(shí)，約簡(jiǎn)集較之也減少了一個(gè).

結(jié)果分析：由表2可以更直觀地看出“服務(wù)質(zhì)量”和“客服情感”都對(duì)“客戶滿意度”有重大影響，兩者不可或缺，因此，這已是最精簡(jiǎn)的最優(yōu)屬性集.通過表2能夠更快地完成數(shù)據(jù)分析，表明企業(yè)需要把“服務(wù)質(zhì)量”和“客服情感”放在重要地位，體現(xiàn)了該算法在決策信息系統(tǒng)上的優(yōu)點(diǎn)和適用性.由表3可以看出，傳統(tǒng)的啟發(fā)式相對(duì)屬性約簡(jiǎn)算法得到的約簡(jiǎn)集中含有“產(chǎn)品認(rèn)知能力”這一屬性，然而從數(shù)據(jù)可以看出，該屬性并不對(duì)客戶滿意度產(chǎn)生多少影響，換句話說，得到的相對(duì)屬性約簡(jiǎn)集不是最優(yōu)的.由表4可以看出，本文所提算法能夠保證約簡(jiǎn)效率高于傳統(tǒng)算法，體現(xiàn)了該算法約簡(jiǎn)效率高的優(yōu)點(diǎn).

4 結(jié)語

為保證相對(duì)屬性約簡(jiǎn)的最優(yōu)性和高效性，在導(dǎo)出相對(duì)屬性約簡(jiǎn)判定條件的基礎(chǔ)上定義了屬性重要度，提出了一種啟發(fā)式最優(yōu)相對(duì)屬性約簡(jiǎn)算法.該算法克服了傳統(tǒng)的相對(duì)屬性約簡(jiǎn)算法需要計(jì)算可區(qū)別矩陣、正區(qū)域以及析取合取計(jì)算量大的問題.實(shí)驗(yàn)證明，算法能夠在相對(duì)較小的時(shí)間內(nèi)完成相對(duì)屬性約簡(jiǎn)，挖掘出有效信息，從而更好地反映知識(shí)表達(dá)系統(tǒng)的特性.

[1]PAWLAKZ.Roughsets[J].InternationalJournalofComputerand InformationSciences,1982,11（11）:341-356.

[2]裴小兵.粗糙集的知識(shí)約簡(jiǎn)研究[D].武漢：華中科技大學(xué)，2006. [3]成新文，陳國(guó)超，李琦.關(guān)于粗糙集的理論及應(yīng)用研究[J].煤炭技術(shù)，2010（10）:198-200.

[4]WONGSKM,ZIARKOW.Onoptimaldecisionrulesindecision table[J].BulletinofPolishAcademyofSciences,1985,33（11-12）: 693-696.

[5]柳熾偉，景玉軍，郭美華.基于故障樹的DCT故障診斷專家系統(tǒng)的研究[J].機(jī)床與液壓，2014,42（1）:169-172.

[6]李英順，姜雙雙，佟維妍，等.基于RST及FTA的綜合傳動(dòng)裝置故障診斷專家系統(tǒng)的應(yīng)用研究[J].組合機(jī)床與自動(dòng)化加工技術(shù)，2014（4）:60-63.

[7]夏侯振宇，段隆振，衷爾英，等.一種改進(jìn)的粗糙集約簡(jiǎn)算法及其應(yīng)用[J].江西科學(xué)，2008,26（3）:379-382.

[8]李玉龍，張亞光，畢聰聰.一種基于改進(jìn)遺傳算法的粗糙集屬性約簡(jiǎn)算法[J].計(jì)算機(jī)與數(shù)字工程，2014（10）:1831-1834.

【編校：王露】

AnImprovedHeuristicOptimalRelativeAttributeReductionAlgorithm

TAOJiayun1,LIYingshun2,ZHAOYuxin2
（1.SchoolofInformationScienceandEngineering,ShenyangUniversityofTechnology,Shenyang,Liaoning110870,China;2.School ofChemicalProcessandAutomation,ShenyangUniversityofTechnology,Liaoyang,Liaoning111003,China）

Animprovedheuristicoptimalrelativeattributereductionalgorithmwasputforwardtosolvetheproblem whichhadlowreductionefficiencycausedbytheneedofcalculatedistinguishablematrixandpositiveregionintherela?tiveattributereductionalgorithmbasedonroughsettheory.Thedecisiveconditionofrelativeattributereductionwasgiv?enbyintroducingthedefinitionofrelativeclassificationabilityinattributeset.Theimprovedrelativeattributereduction algorithmofwhichwasexportedbythemethodasabovenotonlycanguaranteetheconditionalattributesarebest,butal?socanimprovethereductionefficiency.Theresultsofthepracticalexamplesandthecomparisonexperimentsshowhigh efficiencyofthisalgorithm.

roughsettheory;improvedoptimalrelativeattributereduction;decisivecondition

TP18

A

1671-5365(2015)12-0032-04

陶加云，李英順，趙玉鑫.一種改進(jìn)的啟發(fā)式最優(yōu)相對(duì)屬性約簡(jiǎn)算法[J].宜賓學(xué)院學(xué)報(bào),2015,15(12):32-35. TAOJY,LIYS,ZHAOYX.AnImprovedHeuristicOptimalRelativeAttributeReductionAlgorithm[J].JournalofYibinUniver?sity,2015,15(12):32-35.

2015-07-15修回：2015-08-19

遼寧省自然科學(xué)基金項(xiàng)目（2014020115）；遼寧省教育廳科學(xué)技術(shù)研究項(xiàng)目（L2012031）

陶加云（1991-），男，碩士研究生，研究方向?yàn)槿斯ぶ悄芘c數(shù)據(jù)挖掘

時(shí)間：2015-08-2021:37

http://www.cnki.net/kcms/detail/51.1630.z.20150820.2137.001.html