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

陶加云，李英順，趙玉鑫

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

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

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

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

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

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

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

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

1 粗糙集基礎理論

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

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

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

定義4設P和T為定義在論域U上的兩個等價關系簇，T的P正域記為POSP(T)，此時，

定義5設Ω和Θ為定義在論域U上的兩個等價關系簇，設G?Ω,G為Ω的Θ約簡當且僅當G為 Ω的 Θ獨立子簇，并且滿足 POSG(Θ)= POSΩ(Θ)時，就稱Ω的Θ約簡為相對約簡.

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

2.1 屬性集相對分類能力的引入

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

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

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

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

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

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

這與R是條件屬性集C關于決策屬性集D的一個約簡矛盾.因此，得證：對于?r∈R,有：

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

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

2.2 改進最優(yōu)屬性約簡算法描述

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

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

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

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

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

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

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

步驟3：設屬性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：對于屬性集Red,從后往前對每個屬性a進行判斷，看它們是否可省，具體說明如下：

步驟7：輸出最終的Red.

2.3 算法的時間復雜度分析

首先給出并證明如下性質(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.同理，對于任意的Si?Tj,存在使得 Si?Tj=P.綜上可得證

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

O(|C ||U|2).

3 實驗結(jié)果及分析

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

表1 客戶評價數(shù)據(jù)表

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

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

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

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

實驗結(jié)果比較情況如表4所示.

表4 實驗結(jié)果比較情況

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

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

4 結(jié)語

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

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

[2]裴小兵.粗糙集的知識約簡研究[D].武漢：華中科技大學，2006. [3]成新文，陳國超，李琦.關于粗糙集的理論及應用研究[J].煤炭技術，2010（10）:198-200.

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

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

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

[7]夏侯振宇，段隆振，衷爾英，等.一種改進的粗糙集約簡算法及其應用[J].江西科學，2008,26（3）:379-382.

[8]李玉龍，張亞光，畢聰聰.一種基于改進遺傳算法的粗糙集屬性約簡算法[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

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

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

遼寧省自然科學基金項目（2014020115）；遼寧省教育廳科學技術研究項目（L2012031）

陶加云（1991-），男，碩士研究生，研究方向為人工智能與數(shù)據(jù)挖掘

時間：2015-08-2021:37

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