基于灰關(guān)聯(lián)分析的指標(biāo)約簡與權(quán)重分配算法

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

（信息工程大學(xué)，河南 鄭州450001）

0 引 言

由于傳統(tǒng)粗糙集理論要求數(shù)據(jù)對象具有離散性和清晰性，但是在現(xiàn)實應(yīng)用中很多數(shù)據(jù)具有連續(xù)性，因此傳統(tǒng)粗糙集理論的使用受到較大的限制。

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

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

1 灰關(guān)聯(lián)分析簡介

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

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

（1）決策數(shù)據(jù)表建立：決策數(shù)據(jù)表包含條件指標(biāo)和決策指標(biāo)的樣本數(shù)據(jù)，是進行指標(biāo)約減的基礎(chǔ)。

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

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

收益型數(shù)據(jù)的歸一化處理公式

代價型數(shù)據(jù)的歸一化處理公式

式中：xi（j）——歸一化后的指標(biāo)值。

（3）關(guān)聯(lián)系數(shù)和關(guān)聯(lián)度計算

定義2 關(guān)聯(lián)系數(shù)ξid（k）：設(shè)決策表T＝（U，Q，V，f），在樣本uk中條件指標(biāo)ci與決策指標(biāo)d之間的關(guān)聯(lián)系數(shù)ξid（k）可定義為

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

定義3 條件指標(biāo)關(guān)聯(lián)度γ（ci，d）：條件指標(biāo)ci與決策指標(biāo)d的灰關(guān)聯(lián)度簡稱為條件指標(biāo)關(guān)聯(lián)度γ（ci，d）

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

2 條件指標(biāo)重要度與影響度

指標(biāo)重要度是條件指標(biāo)的關(guān)鍵性質(zhì)，而關(guān)聯(lián)度表征條件指標(biāo)與決策指標(biāo)相互影響的程度。一般來說，關(guān)聯(lián)度和重要度具有正相關(guān)性，由此定義條件指標(biāo)的重要度。

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

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

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

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

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

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

圖1 指標(biāo)重疊關(guān)系

我們對條件指標(biāo)是否重疊提出以下3條判定標(biāo)準(zhǔn)：

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

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

（2）兩個條件指標(biāo)完全不重疊的判定標(biāo)準(zhǔn)：指標(biāo)之間影響度為0。

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

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

3 指標(biāo)約簡與權(quán)重分配

3.1 指標(biāo)去重疊化方法

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

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

對圖1中4個指標(biāo)去重疊化后，得到I（c1，d）＝0.45，I（c2，d）＝0.56，I（c3，d）＝0.31，I（c4，d）＝0.8?？梢钥闯觯ブ丿B化后的指標(biāo)絕對重要度有所減小，這是由于對指標(biāo)重要度中的重疊部分進行了重新分配。

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

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

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

定義9 指標(biāo)權(quán)重wi：根據(jù)絕對重要度I（ci，d）確定條件指標(biāo)ci的權(quán)重wi

由 此 可 以 得 到 指 標(biāo) 的 權(quán) 重 向 量W ＝ （w1，…，wi，…wn）。

3.2 指標(biāo)約簡與權(quán)重分配算法IRA－GCA

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

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

輸出：約簡閾值t下的約簡指標(biāo)集B和權(quán)重向量W。

步驟1 對決策表T的數(shù)據(jù)進行標(biāo)準(zhǔn)化處理；

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

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

（2）對條件指標(biāo)集C中任意兩個指標(biāo)ci和cj，當(dāng)κ（ci，cj）＝0時，R（ci，cj）＝0；當(dāng)0＜κ（ci，cj）＜1時，根據(jù)式（10）計算R（ci，cj）；

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

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

步驟6 對約簡指標(biāo)集B的元素，利用指標(biāo)絕對重要度I（ci，d），根據(jù)式 （12）計算指標(biāo)權(quán)重wi；

步驟7 輸出約簡指標(biāo)集B和指標(biāo)權(quán)重向量W。

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

4 仿真實驗與分析

4.1 算法有效性驗證

為驗證IRA－GCA算法的有效性，選取美國加州大學(xué)UCI數(shù)據(jù)庫中的指標(biāo)數(shù)據(jù)集進行實驗。

實驗數(shù)據(jù)集基本信息見表1。

表1 實驗數(shù)據(jù)集基本信息

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

表2 不同算法給出的約簡指標(biāo)集

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

4.2 算法運行效率分析

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

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

圖2 White數(shù)據(jù)集運行結(jié)果

圖3 Ice數(shù)據(jù)集運行結(jié)果

圖4 Atom數(shù)據(jù)集運行結(jié)果

5 結(jié)束語

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

圖5 Stone數(shù)據(jù)集運行結(jié)果

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

（2）算法對條件指標(biāo)集進行去重疊化操作，使指標(biāo)之間相互獨立，有效降低了指標(biāo)之間的關(guān)聯(lián)對約簡結(jié)果產(chǎn)生的影響。

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

（4）算法利用去重疊化后的條件指標(biāo)絕對重要度進行權(quán)重分配，更加準(zhǔn)確合理。

［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］.電子與信息學(xué)報，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］.上海交通大學(xué)學(xué)報，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）.［胡清華，于達仁.基于鄰域粒化和粗糙逼近的數(shù)值屬性約簡［J］.軟件學(xué)報，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）.［宋小威，王加陽.變精度粗糙集區(qū)間約簡模型研究 ［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）.［王磊，王金山.一種基于灰色絕對關(guān)聯(lián)度的變精度粗糙集模型 ［J］.重慶理工大學(xué)學(xué)報，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］.計算機科學(xué)，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］.深圳大學(xué)學(xué)報，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］.計算機研究與發(fā)展，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）.［閏德勤，李克秋.信息系統(tǒng)屬性約簡的柔性差別矩陣 ［J］.通信學(xué)報，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）.［高學(xué)東，丁軍.一種新的信息系統(tǒng)屬性約簡算法 ［J］.系統(tǒng)工程理論與實踐，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）. ［葛浩，李龍澍.基于差別集的啟發(fā)式屬性約簡算法 ［J］.小型微型計算機系統(tǒng)，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）. ［王靖程，諸文智.基于面積的改進灰關(guān)聯(lián)度算法 ［J］.系統(tǒng)工程與電子技術(shù)，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）.［楊文慧，吳建華.一種新的灰關(guān)聯(lián)系數(shù)表達式 ［J］.河海大學(xué)學(xué)報，2008，36 （1）：40－43.］