范兵兵，李 進(jìn)，陳玉金

（空軍工程大學(xué)防空反導(dǎo)學(xué)院，西安 710051）

0 引言

決策粗糙集［1］是Yao等人提出的，在經(jīng)典Pawlak粗糙集［2-3］的基礎(chǔ)上引入了貝葉斯風(fēng)險(xiǎn)分析，通過單個(gè)代價(jià)矩陣來求得構(gòu)建概率粗糙近似所需的一對(duì)閾值［4］。然而，單個(gè)代價(jià)矩陣的確定需要合理的先驗(yàn)知識(shí)，不合理的先驗(yàn)知識(shí)將直接導(dǎo)致模型無(wú)法獲得具有普遍決策意義的近似集和決策規(guī)則。為了消除或者抑制這種由不合理先驗(yàn)知識(shí)帶來的模型噪聲，許多學(xué)者給出了自己的解決方法。文獻(xiàn)［5-7］通過構(gòu)建多重代價(jià)決策粗糙集模型來解決單一矩陣決策的不足；文獻(xiàn)［8-11］通過構(gòu)建包含模糊概念的代價(jià)函數(shù)，建立基于模糊概念的決策粗糙集模型，進(jìn)而抑制不合理的先驗(yàn)知識(shí)帶來的分類不精確性；文獻(xiàn)［12］通過引入博弈論尋求最優(yōu)策略確定閾值；文獻(xiàn)［13］從最小代價(jià)角度考慮自適應(yīng)確定閾值。以上的研究從不同側(cè)面推動(dòng)了決策粗糙集模型的發(fā)展。

回顧決策粗糙集模型和相關(guān)的約簡(jiǎn)算法，決策規(guī)則的簡(jiǎn)潔程度和可信度是模型分類效果好壞的直接體現(xiàn)。因此，在考慮如何抑制由不合理先驗(yàn)知識(shí)帶來的模型噪聲時(shí)，需要兼顧考慮模型分類效果好壞：1）在屬性約簡(jiǎn)及后續(xù)決策中，可信度高的規(guī)則更具有指導(dǎo)性作用。2）獲取的決策規(guī)則越簡(jiǎn)潔，即屬性的個(gè)數(shù)越少，信息系統(tǒng)決策速率越快。

1 基本知識(shí)

1.1 經(jīng)典決策粗糙集模型

在此基礎(chǔ)上，定義決策粗糙集的下、上近似分別為：

1.2 決策規(guī)則的獲取

2 基于決策規(guī)則的求閾值方法

在決策粗糙集及屬性約簡(jiǎn)中，如何通過合理的先驗(yàn)知識(shí)給出合理的風(fēng)險(xiǎn)代價(jià)矩陣是一個(gè)需要解決的關(guān)鍵問題?；诖?，本節(jié)介紹一種自適應(yīng)求代價(jià)矩陣的算法，以減少新引入?yún)?shù)對(duì)模型的影響。

回顧決策粗糙集模型和相關(guān)的約簡(jiǎn)算法，決策規(guī)則的簡(jiǎn)潔程度和可信度是模型分類效果好壞的直接體現(xiàn)。因此，在考慮自適應(yīng)求代價(jià)矩陣的算法中必須考慮以下兩點(diǎn)：

1）在屬性約簡(jiǎn)及后續(xù)決策中，可信度高的規(guī)則更具有指導(dǎo)性作用。

2）獲取的決策規(guī)則越簡(jiǎn)潔，即屬性的個(gè)數(shù)越少，信息系統(tǒng)決策速率越快。

下面我們將基于決策規(guī)則的自適應(yīng)求代價(jià)矩陣方法轉(zhuǎn)化為單目標(biāo)優(yōu)化問題進(jìn)行解決。令為一信息系統(tǒng)，其中，那么，求代價(jià)矩陣的問題可以轉(zhuǎn)化為

同時(shí)，為了保留一個(gè)明確的邊界域，假設(shè)α≥β。綜合以上條件，對(duì)約束條件進(jìn)行簡(jiǎn)化

3 基于引力搜索算法的自適應(yīng)求閾值算法

3.1 引力搜索算法的基本描述

假設(shè)存在一個(gè)包含N個(gè)個(gè)體的系統(tǒng)。其中，第i個(gè)個(gè)體的位置定義為n維空間。那么，t時(shí)刻第 d維上，個(gè)體 Xj，Xi之間的作用力分量定義為

其中，Maj（t）和Mpi（t）分別為個(gè)體Xj和粒子Xi的主動(dòng)引力質(zhì)量和被動(dòng)引力質(zhì)量。ε是一個(gè)很小的常量，防止分母為零；Rij（t）是粒子Xj和粒子Xi的歐式距離；G（t）是在 t時(shí)刻的引力常數(shù)

其中，G0、α為常數(shù)，T是最大迭代次數(shù)。文獻(xiàn)［15］建議取值為 G0=100，α=20。

這里假設(shè)引力質(zhì)量和慣性質(zhì)量相等，即Mai=Mpi=Mii=Mi，i=1，2，…，n。那么，式（3）中的相關(guān)質(zhì)量值可以計(jì)算如下

其中，fiti（t）表示t時(shí)刻個(gè)體Xi的適應(yīng)度；best（t），worst（t）表示t時(shí)刻所有個(gè)體最好和最差的適應(yīng)度值。

Rij（t）通過矩陣范數(shù)表示

那么，個(gè)體Xi在t時(shí)刻第d維上受到的合力為：

其中，randj是［0，1］的隨機(jī)數(shù)，kbest表示當(dāng)前質(zhì)量排名前k位的個(gè)體。

根據(jù)牛頓第二定律，個(gè)體Xi在t時(shí)刻第d維的加速度aid（t）為

最后，個(gè)體的速度和位置更新如下

其中，randi是［0，1］的隨機(jī)數(shù)。分別表示個(gè)體Xi在t時(shí)刻第d維上的速度分量和位移分量。

3.2 自適應(yīng)求閾值的算法描述

3.2.1 個(gè)體位置的表示

第i個(gè)個(gè)體Xi的位置由一組四維的正實(shí)數(shù)向量，其中，表示當(dāng)一個(gè)對(duì)象x屬于集合X時(shí)，采取aB，aN決策時(shí)所需的代價(jià)表示當(dāng)一個(gè)對(duì)象x不屬于集合X時(shí)，采取aP，aB決策時(shí)所需的代價(jià)。同時(shí)根據(jù)最優(yōu)化問題描述可得，滿足如下關(guān)系

3.2.2 適應(yīng)度函數(shù)

代價(jià)矩陣的適應(yīng)度函數(shù)需要滿足兩個(gè)條件：一是要保證通過代價(jià)矩陣得出的閾值可以給出簡(jiǎn)潔且有效的決策規(guī)則；二是要保證所有個(gè)體都能夠受到力的作用（慣性質(zhì)量大于等于0），進(jìn)而發(fā)生位移，以產(chǎn)生新的個(gè)體供全局搜索。因此，適應(yīng)度函數(shù)定義為

由于約簡(jiǎn)問題中需要求解目標(biāo)函數(shù)的最大值，因此定義

3.2.3 位置修正

由適應(yīng)度函數(shù)可得，引力搜索算法中對(duì)于加速度和位移分量的計(jì)算結(jié)果可能導(dǎo)致個(gè)體位置不滿足式（14）的約束，故需要對(duì)數(shù)據(jù)結(jié)果進(jìn)行修正。

閾值α，β的取值事實(shí)上可以為一系列離散值代替以往區(qū)間內(nèi)的連續(xù)值，而使等價(jià)類進(jìn)行正域、負(fù)域、邊界域劃分效果不變。例：已知，等價(jià)類為，當(dāng)閾值或者時(shí)，均可達(dá)到使等價(jià)類劃分到正域的效果，同理，對(duì)于等價(jià)類，當(dāng)閾值或者時(shí)，均可達(dá)到使等價(jià)類劃分到負(fù)域的效果。因此，可以推斷，對(duì)于任一等價(jià)類，假設(shè)其含有n個(gè)元素，則當(dāng)時(shí)，可以達(dá)到相同的劃分效果。將α，β的取值離散化后，相對(duì)于區(qū)間內(nèi)的連續(xù)值更加適合智能算法的搜索，使搜索時(shí)間減少也避免發(fā)生組合爆炸。

本算法引入上述位置修正以及閾值α，β的離散化限定，保證個(gè)體位置滿足問題約束，具體如算法1所示。

算法1：代價(jià)矩陣位置修正

綜合以上分析，下面給出基于引力搜索算法的自適應(yīng)求代價(jià)矩陣算法，如下頁(yè)算法2所示。

4 仿真實(shí)驗(yàn)

為了檢驗(yàn)上述基于引力搜索的自適應(yīng)求閾值算法的應(yīng)用過程和效果，將引力搜索求三支決策最優(yōu)閾值算法分別和自適應(yīng)算法Alcofa、模擬退火算法求解三支決策閾值從運(yùn)行時(shí)間隨著屬性個(gè)數(shù)以及樣本數(shù)增加，對(duì)其運(yùn)行時(shí)間影響兩方面進(jìn)行比較。此外，為了檢驗(yàn)利用基于引力搜索的自適應(yīng)算法學(xué)習(xí)到的閾值的有效性，利用3種算法學(xué)習(xí)到的閾值構(gòu)建了分類器，并計(jì)算其準(zhǔn)確率Precision（P）、召回率Recall（R）和F1值，計(jì)算方法［14］如下：Preciosn=系統(tǒng)檢索到的相關(guān)文件數(shù)/相關(guān)文件總數(shù)Recall=系統(tǒng)檢索到的相關(guān)文件數(shù)/系統(tǒng)返回的文件總數(shù)

算法2：基于引力搜索算法的自適應(yīng)求代價(jià)矩陣算法

Step1：系統(tǒng)初始化

1）給定系統(tǒng)中個(gè)體規(guī)模N，最大迭代次數(shù)T，初始化每個(gè)個(gè)體的位置

2）根據(jù)式（14）、相應(yīng)的屬性約簡(jiǎn)算法和決策規(guī)則提取方法計(jì)算每個(gè)個(gè)體的適應(yīng)度值fiti（t），記錄最優(yōu)適應(yīng)度值及對(duì)應(yīng)的個(gè)體位置信息作為歷史最優(yōu)信息

Step2：系統(tǒng)位置更新

1）根據(jù)式（8）計(jì)算每個(gè)個(gè)體的慣性質(zhì)量Mi（t）

2）根據(jù)式（10）計(jì)算每個(gè)個(gè)體當(dāng)前時(shí)刻受其他個(gè)體影響的合力Fid（t）

3）根據(jù)式（11）計(jì)算每個(gè)個(gè)體當(dāng)前時(shí)刻的加速度aid（t）

4）根據(jù)式（12）更新每個(gè)個(gè)體的速度和位置

5）根據(jù)算法1對(duì)新系統(tǒng)中的個(gè)體位置進(jìn)行修正

6）根據(jù)式（14）更新每個(gè)個(gè)體的適應(yīng)度值fiti（t）

7）記錄當(dāng)前時(shí)刻最優(yōu)適應(yīng)度值及對(duì)應(yīng)的個(gè)體位置信息。若當(dāng)前時(shí)刻最優(yōu)適應(yīng)度值優(yōu)于歷史最優(yōu)適應(yīng)度值，則更新歷史最優(yōu)信息

Step3：如果連續(xù)M代最優(yōu)適應(yīng)度值沒有發(fā)生變化或者迭代次數(shù)達(dá)到最大迭代次數(shù)T，轉(zhuǎn)到Step4，否則轉(zhuǎn)到Step2

F1=2Precision x Recall/（ Precision+Recall）

實(shí)驗(yàn)環(huán)境如下：CPU是Intel的I7-4790，主頻3.60 GHz，8G 的內(nèi)存，64位的 Windows7系統(tǒng)，Matlab R2012a上實(shí)現(xiàn)。

表1 數(shù)據(jù)集描述

實(shí)驗(yàn)的數(shù)據(jù)集為UCI數(shù)據(jù)庫(kù)中的10個(gè)數(shù)據(jù)集，首先，需要對(duì)數(shù)據(jù)集進(jìn)行預(yù)處理，將數(shù)據(jù)集中的missing值直接刪除。又因?yàn)槟M退火算法是一種隨機(jī)算法，每次運(yùn)行狀態(tài)和結(jié)果可能不一樣，因此，對(duì)每個(gè)數(shù)據(jù)集都運(yùn)行50次取平均值作為算法的運(yùn)行結(jié)果。

從表2中的運(yùn)行時(shí)間結(jié)果來看，由于對(duì)引力搜索空間進(jìn)行了離散化的搜索限定，使得引力搜索自適應(yīng)算法明顯快于自適應(yīng)算法和模擬退火算法，并且隨著數(shù)據(jù)集樣本以及屬性的增加，運(yùn)行時(shí)間無(wú)明顯增加。而自適應(yīng)算法Alcofa的運(yùn)行時(shí)間隨著樣本個(gè)數(shù)以及屬性個(gè)數(shù)的增加明顯提高。

表2 3種算法的運(yùn)行時(shí)間結(jié)果

為了研究隨著屬性個(gè)數(shù)以及樣本數(shù)增加對(duì)其運(yùn)行時(shí)間影響，分別限定數(shù)據(jù)集樣本個(gè)數(shù)固定為432、屬性個(gè)數(shù)9到34不等，以及數(shù)據(jù)集樣本個(gè)數(shù)為192～45 212不等、屬性個(gè)數(shù)固定為11，對(duì)這兩種情況進(jìn)行實(shí)驗(yàn)，并統(tǒng)計(jì)運(yùn)行時(shí)間，如下頁(yè)表3所示。

從表3所求的標(biāo)準(zhǔn)差來看，無(wú)論是隨著屬性個(gè)數(shù)增加還是隨著樣本個(gè)數(shù)增加，引力搜索自適應(yīng)算法較Alcofa算法以及模擬退火算法均具有更好的穩(wěn)定性。

表3 兩種情況的運(yùn)行時(shí)間結(jié)果

表4 3種算法所求閾值構(gòu)建的分類器的性能比較

從表4的結(jié)果來看，對(duì)比10組數(shù)據(jù)庫(kù)的分類效果，在07、08號(hào)數(shù)據(jù)庫(kù)中引力搜索自適應(yīng)算法略高于Alcofa自適應(yīng)算法構(gòu)建的分類器的分類能力，在04號(hào)數(shù)據(jù)庫(kù)，顯示兩者分類能力相同，其余7個(gè)數(shù)據(jù)庫(kù)顯示，Alcofa自適應(yīng)算法構(gòu)建的分類器的分類能力略高于引力搜索自適應(yīng)算法所構(gòu)建的分類器。對(duì)比上述十組數(shù)據(jù)顯示，模擬退火算法所構(gòu)建的分類器的分類能力強(qiáng)于Alcofa自適應(yīng)算法和引力搜索自適應(yīng)算法。

出現(xiàn)引力搜索自適應(yīng)算法的分類能力下降主要原因是，為了加快運(yùn)行時(shí)間，對(duì)引力搜索空間進(jìn)行了離散化的搜索限定，因此，在精度上有所下降，下面分別就引力搜索自適應(yīng)算法對(duì)Alcofa自適應(yīng)算法以及模擬退火算法的準(zhǔn)確率（P）的平均誤差率μ1、μ2進(jìn)行計(jì)算，來說明這種誤差是可接受的，以此說明該算法所得出的閾值有效。

由于平均誤差率μ1、μ2的值均小于千分之五，屬于可接受范圍之內(nèi)，說明該算法所得出的閾值有效。

5 結(jié)論

為了消除或者抑制由不合理先驗(yàn)知識(shí)帶來的模型噪聲，本文提出了一種基于規(guī)則提取的閾值自適應(yīng)方法。本文以約簡(jiǎn)結(jié)果中屬性的數(shù)量最小和相應(yīng)決策規(guī)則的可信度最大為目標(biāo)，結(jié)合引力搜索算法，并利用決策粗糙集中的閾值α，β為一特定離散取值時(shí)，不會(huì)改變等價(jià)類的劃分這一性質(zhì)，對(duì)搜索空間離散化處理，然后給出基于智能算法的自適應(yīng)求閾值算法。通過實(shí)例證明，本文提出的決策粗糙集閾值自適應(yīng)方法是可行的。下一步需要努力在本文工作的基礎(chǔ)上考慮特定語(yǔ)義下的根據(jù)權(quán)重，構(gòu)建新的目標(biāo)函數(shù)將這一方法運(yùn)用到更多方面。

參考文獻(xiàn)：

［1］YAO Y Y，WONG S K M，LINGRAS P.A decision-theoretic rough set model［C］//Raszw，Zemankovam，Proceedings of the 5th International Symposium on Methodologies for Intelligent Systems.North-Holland，1990：17-25.

［2］PAWLAK Z.Rough sets ［J］.International Journal of Computer and Information Sciences，1982，11（5）：341-356.

［3］PAWLAK Z.Rudiments of rough sets ［J］.Information Science，2007，177（1）：3-27.

［4］于洪，王國(guó)胤，姚一豫.決策粗糙集理論研究現(xiàn)狀與展望［J］.計(jì)算機(jī)學(xué)報(bào)，2015，38（8）：1628-1639.

［5］陳玉金，李續(xù)武，賈英杰，等.可變多重代價(jià)決策粗糙集模型［J］.計(jì)算機(jī)科學(xué)，2017，44（6）：245-249.

［6］MA X B，YANG X B，QI Y，et al.Multicost decision-theoretic rough sets based on maximal consistent blocks［C］//Miao Duoqian，Witold pedrycz.Rough sets and knowledge technology：9th International Conference.Shanghai：Springer，2014：824-833.

［7］DOU H L，YANG X B，SONG X N，et al.Decision-theoretic rough set：a multicost strategy ［J］.Knowledge-Based Systems，2016，91：71-83.

［8］LIANG D C，LIU D，WITOLD PEDRYCZ，et al.Triangular fuzzy decision-theoretic rough sets［J］.International Journal of Approximate Reasoning，2013，54：1087-1106.

［9］LIANG D C，LIU D.Systematic studies on three-way decisions with interval-valued decision-theoretic rough sets［J］.Information Sciences，2014，276：186-203.

［10］LIANG D C，LIU D.Deriving three-way decisions from intuitionistic fuzzy decision-theoretic rough sets［J］.Information Science，2015，300：28-48.

［11］LIANG D C，XU Z S，LIU D.Three-way decisions with intuitionistic fuzzy decision-theoretic rough sets based on pointoperators ［J］.Information Science，2017，375：183-201.

［12］HERBERT J P，YAO J T.Game-theoretical rough sets［J］.Fudanmenta Informaticae，2011，108（3）：267-286.

［13］JIA X Y，TANG Z M，LIAO W H，et al.On an optimization representation of decision-theoretic rough set model［J］.International Journal of Approximate Reasoning，2014，55：155-166.

［14］胡盼，秦亮曦，姚洪曼.用人工魚群算法自動(dòng)確定三支決策閡值［J］.計(jì)算機(jī)與現(xiàn)代化，2016，32（6）：97-101.

［15］JIA X Y，ZHENG K，LI W W，et al.Three-way decisions solution to filter spam email：An empirical study［C］//Proceedings of the 8th International Conference on Rough Sets and Current Trends in Computing.Chengdu，China，2012：287-296.

［16］RASHEDI E，NEZAMABADI-POUR H，SARYAZDI S.GSA：A gravitational search algorithm［J］.Information Sciences，2009，179（13）：2232-2248.

［17］YAO Y Y，ZHAO Y.Attribute reduction in decision-theoretic rough set models［J］.Information Sciences，2008，178（17）：3356-3373.