基于灰關聯分析的指標約簡與權重分配算法

張恒巍，韓繼紅，張 健，王晉東，寇 廣

（信息工程大學，河南 鄭州450001）

0 引 言

由于傳統粗糙集理論要求數據對象具有離散性和清晰性，但是在現實應用中很多數據具有連續性，因此傳統粗糙集理論的使用受到較大的限制。

許菲菲等［1］提出模糊粗糙集模型，設計了一種基于數值優化理論的連續值屬性約減方法；王莉等［2］基于模糊決策粗糙集模型，定義高斯核模糊T－等價關系，從模糊隸屬度角度給出條件概率，實現對連續型數據的屬性約簡。上述文獻采用對連續數據離散化處理的方法，使粗糙集適用于連續屬性約減問題，但是離散化處理會帶來屬性值數據的失真，造成一定程度的信息損失。胡清華等［3］提出一種構建在實數空間的粗糙集模型，通過對樣本數據的粒化處理，在模型中用樣本數據的領域關系表示屬性之間的關系；宋小威等［4］基于變精度粗糙集模型，根據下近似分布不變性定義了區間約簡模型，并給出一種基于有序分辨矩陣的區間約簡方法；杜俊慧［5］利用灰色聚類代替粗糙集中的等價關系進行分類，采用F統計量確定灰色聚類的臨界值，能夠實現對連續值屬性的約減；王磊等［6］提出一種基于灰色絕對關聯度的屬性約簡算法，上述方法都未考慮不同屬性間的重疊計算問題和信息損失問題。

針對以上問題，本文在灰關聯分析的基礎上，通過研究不同類型指標之間的關聯性，定義了條件指標的重要性測度和條件指標之間的影響力測度，提出了一種基于灰關聯分析的指標約簡與權重分配算法IRA－GCA （index reduction algorithm based on grey－correlation analysis，IRAGCA）。仿真實驗和對比分析結果表明，本文提出的算法具有能夠同時處理離散型決策表和連續型決策表、權重分配準確、運算效率高的優點。

1 灰關聯分析簡介

在粗糙集研究領域中，屬性約簡是研究的重點和熱點之一。本文關注的指標體系構建中的指標約簡問題，是屬性集約簡問題在指標體系領域的具體表現。張任偉等［7］對現有的屬性約簡算法進行了分析和比較，指出Pawlak約簡算法、基于差別矩陣及其改進的約簡算法［8，11］都存在較為顯著的缺點，在實際使用中限制條件多，實用性較差。啟發式約減算法能夠根據信息熵［1，13］、屬性重要度［12］或差別集［14］等信息進行指標約減，但是存在對啟發信息量依賴程度較高的缺點。

灰關聯分析作為一種多指標分析方法，根據不同指標的樣本數據變化趨勢的相似程度來表征指標間的關聯程度和相似程度。近一段時期，基于面積的灰關聯算法［15］和線性灰關聯算法［16］對傳統灰關聯分析進行了改進和提高，受此啟發，針對現有約減算法的不足，本文提出一種基于灰關聯分析的指標約減算法。首先給出灰關聯分析的過程。

（1）決策數據表建立：決策數據表包含條件指標和決策指標的樣本數據，是進行指標約減的基礎。

定義1 決策表T：用四元組T＝（U，Q，V，f）定義決策表，其中U＝｛x1，x2，…，xm｝是決策對象的非空有限集合，Q是指標集，V為指標的值域集，f是U×Q→V的映射。Q＝C∪D，其中條件指標集合C＝ ｛c1，c2，…，cn｝中有n個指標，決策指標D一般只有一個，用d來表示。

（2）數據標準化：由于不同指標的單位和量級不同，不能直接進行比較。因此，在進行灰關聯分析之前將指標數據按某種效用函數進行歸一化處理。針對收益型數據和代價型數據的歸一化處理公式如下。

收益型數據的歸一化處理公式

代價型數據的歸一化處理公式

式中：xi（j）——歸一化后的指標值。

（3）關聯系數和關聯度計算

定義2 關聯系數ξid（k）：設決策表T＝（U，Q，V，f），在樣本uk中條件指標ci與決策指標d之間的關聯系數ξid（k）可定義為

其中，根據樣本的重要性，可以定義第i個條件指標值在第k個樣本中的權重為ωik。取P＝2，采用歐氏距離。

定義3 條件指標關聯度γ（ci，d）：條件指標ci與決策指標d的灰關聯度簡稱為條件指標關聯度γ（ci，d）

在本文的決策表約簡算法中，令P＝2，ωi為歸一化的等權向量，則式 （5）可以簡化為

2 條件指標重要度與影響度

指標重要度是條件指標的關鍵性質，而關聯度表征條件指標與決策指標相互影響的程度。一般來說，關聯度和重要度具有正相關性，由此定義條件指標的重要度。

定義4 條件指標重要度IMP（ci，d）：條件指標ci相對決策指標d的重要度IMP（ci，d）定義為

每個條件指標代表系統某一方面的屬性。雖然不同指標的描述角度、方式和方法不一樣，但是指標之間不是孤立的，存在或強或弱的聯系，因此不同指標之間存在重疊的情況［13］。兩個條件指標的重疊性越大，則它們對信息系統描述的相似程度就越大。條件指標之間的重疊對指標約簡和權重分配的準確性造成了干擾，為消除這種干擾，本文借鑒灰關聯分析理論，建立了條件指標影響系數和影響度的概念，用以定量描述指標之間的重疊程度。在此基礎上，提出了條件指標的去重疊化方法，設計了指標約簡與權重分配算法IRA－GCA，以實現更加準確的指標約簡和權重分配。

定義5 條件指標影響系數ηij（k）：設決策表T＝（U，Q，V，f），在樣本uk中條件指標ci對cj的影響系數ηij（k）可定義為

定義6 條件指標影響度κ（ci，cj）：定義條件指標ci對cj的影響程度為κ（ci，cj）

式中：κ（ci，cj）代表了條件指標ci對cj的影響程度，說明cj在多大程度上受到ci的影響，0≤κ（ci，cj）≤1。當κ（ci，cj）＝0時，說明ci與cj毫不相關，ci對cj不具有任何影響；當κ（ci，cj）＝1時，說明ci對cj具有完全程度的影響；當0＜κ（ci，cj）＜1時，說明ci對cj具有影響，但又不能完全影響cj。同時，κ（ci，cj）不具有對稱性，即指標ci對cj的影響程度κ（ci，cj）和cj對ci的影響程度κ（cj，ci）通常不相同，所以一般情況下κ（ci，cj）≠κ（cj，ci）。

借助條件指標影響度的定義，可以定量描述指標之間的重疊關系。不失一般性，設4個條件指標之間的關系如圖1所示

圖1 指標重疊關系

我們對條件指標是否重疊提出以下3條判定標準：

（1）兩個條件指標完全重疊的判定標準：①兩個指標的重要性相同IMP（ci，d）＝IMP（cj，d）；②指標之間影響度為1。

兩個條件指標完全重疊表示這兩個指標實際是同一個指標，是對系統同一屬性不同角度或方式的表述。此時，兩個指標可以看作是一個指標。

（2）兩個條件指標完全不重疊的判定標準：指標之間影響度為0。

（3）當兩個指標之間既有重疊又未達到完全重疊時，定義指標之間的重疊部分為

一般來說，條件指標的重要度越大，與其它指標的重疊越小，對決策指標的影響就越大；反之，條件指標對決策指標的影響就越小。

3 指標約簡與權重分配

3.1 指標去重疊化方法

假設圖1中的指標重要度分別為IMP（c1，d）＝0.5，IMP（c2，d）＝0.7，IMP（c3，d）＝0.4，IMP（c4，d）＝0.8。可以看出，c1，c2，c3之間有重疊，但不是完全重疊。設c1和c2之間的 影響度 分別是κ（c1，c2）＝ 0.125和κ（c2，c1）＝0.25，c2和c3之間的影響度分別是κ（c2，c3）＝0.75和κ（c3，c2）＝0.25。指標的重疊部分是指標描述中的冗余信息，去除指標重疊信息的操作稱為指標去重疊化。去重疊化的原則為兩個有重疊的指標對重疊部分重新分配，可以不失一般性地假設每個指標獲得重疊部分的一半。

定義7 條件指標絕對重要度I（ci，d）：若兩個指標ci和cj之間具有重疊關系，則去重疊化后得到指標絕對重要度I（ci，d）和I（cj，d）分別為

對圖1中4個指標去重疊化后，得到I（c1，d）＝0.45，I（c2，d）＝0.56，I（c3，d）＝0.31，I（c4，d）＝0.8。可以看出，去重疊化后的指標絕對重要度有所減小，這是由于對指標重要度中的重疊部分進行了重新分配。

定義8 約簡閾值t：設定 （0，1）上的實數t為約簡閾值，用于判斷條件指標ci能否進入約簡集。

將條件指標的絕對重要度I（ci，d）與t作比較，若I（ci，d）≥t，認為該條件指標重要，可以進入約簡集；若I（ci，d）＜t，則認為該條件指標不夠重要，不能進入約簡集。

根據上述分析可知，對于復雜的指標體系來說，指標之間通常有著某種關聯關系，因此指標的重要度IMP（c，d）之間存在重疊，如果直接利用IMP（c，d）進行指標權重的分配，將會影響權重的準確性和合理性。只有從重要度IMP（c，d）中剔除關聯影響，得到指標的絕對重要度I（c，d），才能準確描述條件指標獨立影響決策指標的程度，依據I（c，d）進行權重分配，更加準確、合理。

定義9 指標權重wi：根據絕對重要度I（ci，d）確定條件指標ci的權重wi

由 此 可 以 得 到 指 標 的 權 重 向 量W ＝ （w1，…，wi，…wn）。

3.2 指標約簡與權重分配算法IRA－GCA

依據上述分析和研究，提出基于灰關聯分析的指標約簡與權重分配算法IRA－GCA。算法以決策表數據為基礎，首先依據本文的定義對指標進行去重疊化操作，然后逐次選擇最重要的條件指標添加到約簡集中，最后對約簡指標集中的指標依據絕對重要度進行權重分配。算法的步驟如下所示。

輸入：決策表T＝（U，Q，V，f）；約簡閾值t。

輸出：約簡閾值t下的約簡指標集B和權重向量W。

步驟1 對決策表T的數據進行標準化處理；

步驟3 計算條件指標集C中元素之間的重疊部分R（ci，cj）；

（1）對條件指標集C中每個指標ci，根據式 （8）和式（9）計算ci對其它條件指標的影響度κ（ci，cj）i，j ＝ 1，2，…，n，i≠j；

（2）對條件指標集C中任意兩個指標ci和cj，當κ（ci，cj）＝0時，R（ci，cj）＝0；當0＜κ（ci，cj）＜1時，根據式（10）計算R（ci，cj）；

步驟4 對條件指標集C中每個指標ci進行去重疊化，根據式 （11）計算指標的絕對重要度I（ci，d）；

步驟5 依據指標絕對重要度I（ci，d）對條件指標集C進行約簡，構建約簡指標集B。若I（ci，d）≥t，則將其選入約簡集B；若I（ci，d）＜t，則將其去除，不作為約簡集B的元素；

步驟6 對約簡指標集B的元素，利用指標絕對重要度I（ci，d），根據式 （12）計算指標權重wi；

步驟7 輸出約簡指標集B和指標權重向量W。

IRA－GCA算法通過完整保留原始數據信息，解得的指標約簡集合理性更強。算法的時間復雜度為O（mn2），存儲原始數據矩陣是本算法的主要空間消耗。

4 仿真實驗與分析

4.1 算法有效性驗證

為驗證IRA－GCA算法的有效性，選取美國加州大學UCI數據庫中的指標數據集進行實驗。

實驗數據集基本信息見表1。

表1 實驗數據集基本信息

同時選擇代數約簡算法ARA、信息熵約簡算法CEBARKCC和基于區分矩陣的約簡算法AM－RASR來進行對比實驗。實驗用計算機配置為Core2處理器，2G內存，操作系統是Windows XP，算法用Matlab2010b實現。設本算法的約簡閾值t＝0.5，分別對4個數據集做指標約簡的結果見表2。

表2 不同算法給出的約簡指標集

可以看出，IRA－GCA算法的約簡結果在其它算法的結果集中，驗證了本算法的有效性。同時，由于約簡閾值t＝0.5，結果更加精簡；在不同的應用中可以通過調整t的取值，靈活適應用戶的約減精度。

4.2 算法運行效率分析

從上述實驗對象數據集中取前N個對象作為實驗樣本，N分別為10，20，…，50。設置本算法的約簡閾值為0.5，分別運行IRA－GCA算法、ARA算法、CEBARKCC算法和AM－RASR算法，記錄算法得到各自約簡結果的運行時間，如圖2～圖5所示。

可以看出，一方面，本文提出的算法IRA－GCA在樣本數量較小時優勢并不突出，當樣本數量增加時IRA－GCA的優勢開始顯著，求解時間明顯較少。另一方面，當條件指標的個數較大時，IRA－GCA的運行時間仍然較少，但與其它算法相比區別不大，圖5表明了這一特點。因此，IRA－GCA算法更適合于樣本數較多且指標數較少情況下的約簡應用。

圖2 White數據集運行結果

圖3 Ice數據集運行結果

圖4 Atom數據集運行結果

5 結束語

本文利用灰關聯分析理論量化定義了指標重要度和指標之間的影響度，提出了條件指標去重疊化方法，設計了指標約簡與權重分配算法IRA－GCA。與其它算法相比，本文提出的算法具有以下特點和優勢：

圖5 Stone數據集運行結果

（1）算法能夠處理離散型決策表和連續型決策表，以及二者同時存在的混合決策表等復雜情況，有效避免了將連續值轉化為離散值時的信息損失。

（2）算法對條件指標集進行去重疊化操作，使指標之間相互獨立，有效降低了指標之間的關聯對約簡結果產生的影響。

（3）算法在保持指標約簡能力的同時，約簡過程更加高效。在樣本數目越大的時候本算法優勢越顯著；而隨著指標數目的增加，本算法的優勢逐步減弱。所以本算法更適合于大樣本空間、小指標空間的情形。

（4）算法利用去重疊化后的條件指標絕對重要度進行權重分配，更加準確合理。

［1］XU Feifei，MIAO Duoqian.Mutual information－based algorithm for fuzzy－rough attribute reduction ［J］.Journal of Electronics ＆Information Technology，2008，30 （6）：1372－1375（in Chinese）.［徐菲菲，苗奪謙.基于互信息的模糊粗糙集屬性約簡 ［J］.電子與信息學報，2008，30 （6）：1372－1375.］

［2］WANG Li，ZHOU Xianzhong，LI Huaxiong.Fuzzy decisiontheoretic rough set model and its attribute reduction ［J］.Journal of Shanghai JiaoTong University，2013，47 （7）：1032－1035（in Chinese）.［王莉，周獻中，李華雄.模糊決策粗糙集模型及其屬性約簡 ［J］.上海交通大學學報，2013，47（7）：1032－1035.］

［3］HU Qinghua，YU Daren.Numerical attribute reduction based on neighborhood granulation and rough approximation ［J］.Journal of Software，2008，19 （3）：640－649 （in Chinese）.［胡清華，于達仁.基于鄰域粒化和粗糙逼近的數值屬性約簡［J］.軟件學報，2008，19 （3）：640－649.］

［4］SONG Xiaowei，WANG Jiayang.Research on interval reduction model in variable precision rough set ［J］.Pattern Recognition and Artificial Intelligence，2013，26 （11）：33－40 （in Chinese）.［宋小威，王加陽.變精度粗糙集區間約簡模型研究 ［J］.模式識別與人工智能，2013，26 （11）：33－40.］

［5］ WANG Lei，WANG Jinshan.Variable precision rough set model based on grey absolute correlation degree ［J］.Journal of Chongqing Institute of Technology，2012，26 （5）：123－126（in Chinese）.［王磊，王金山.一種基于灰色絕對關聯度的變精度粗糙集模型 ［J］.重慶理工大學學報，2012，26（5）：123－126.］

［6］ZHANG Renwei，BAI Xiaoying.Survey of decision table research of attribute reduction ［J］.Computer Science，2011，38 （11）：1－6 （in Chinese）. ［張任偉，白曉穎.決策表的屬性約簡算法綜述 ［J］.計算機科學，2011，38 （11）：1－6.］

［7］FENG Shaorong，ZHANG Dongzhan.Increment algorithm for attribute reduction based on improvement of discernibility matrix ［J］.Journal of Shenzhen University （Science ＆Engineering），2012，29 （5）：405－411 （in Chinese）.［馮少榮，張東站.基于改進差別矩陣的增量式屬性約簡算法 ［J］.深圳大學學報，2012，29 （5）：405－411.］

［8］WANG Xizhao，WANG Tingting.An attribute reduction algorithm based on instance selection ［J］.Journal of Computer Research and Development，2012，49 （11）：2305－2310 （in Chinese）.［王熙照，王婷婷.基于樣例選取的屬性約簡算法［J］.計算機研究與發展，2012，49 （11）：2305－2310.］

［9］Sirzat Kahramanli，Mehmet Hacibeyoglu，Ahmet Arslan.Attribute reduction by partitioning the minimized discernibility function ［J］.International Journal of Innovative Computing，Information and Control，2011，7 （5）：2167－2186.

［10］RUN Deqin，LI Keqiu.Soft discernibility matrix and attribute reduction for information systems ［J］.Journal on Communi－cations，2009，30 （8）：45－50 （in Chinese）.［閏德勤，李克秋.信息系統屬性約簡的柔性差別矩陣 ［J］.通信學報，2009，30 （8）：45－50.］

［11］GAO Xuedong，DING Jun.A new attribute algorithm for reduction of information system ［J］.Systems Engineering Theory and Practice，2007，27 （1）：132－136 （in Chinese）.［高學東，丁軍.一種新的信息系統屬性約簡算法 ［J］.系統工程理論與實踐，2007，27 （1）：132－136.］

［12］Nicol D M，Sanders W H，Tricedi K S.A continuous value attributes reduction algorithm based on gray correlation ［J］.IEEE Transactions on Dependability and Security，2012，3（1）：48－55.

［13］GE Hao，LI Longpeng.Heuristics attribute reduction algorithm based on discernibility set ［J］.Journal of Chinese Computer Systems，2013，34 （2）：380－385 （in Chinese）. ［葛浩，李龍澍.基于差別集的啟發式屬性約簡算法 ［J］.小型微型計算機系統，2013，34 （2）：380－385.］

［14］WANG Jingcheng，ZHU Wenzhi.Improved algorithm of grey incidence degree based on area ［J］.Systems Engineering and Electronics，2010，32 （4）：777－779 （in Chinese）. ［王靖程，諸文智.基于面積的改進灰關聯度算法 ［J］.系統工程與電子技術，2010，32 （4）：777－779.］

［15］YANG Wenhui，WU Jianhua.A new expression of grey relation coefficient ［J］.Journal of Hohai University （Natural Sciences），2008，36 （1）：40－43 （in Chinese）.［楊文慧，吳建華.一種新的灰關聯系數表達式 ［J］.河海大學學報，2008，36 （1）：40－43.］