基于超圖的多尺度決策信息系統最優尺度選擇

馬周明, 黃 閩, 林國平, 施虹藝

（1.閩南師范大學數學與統計學院,福建 漳州 363000；2.閩南師范大學福建省粒計算及其應用重點實驗室,福建 漳州 363000）

Pawlak[1]于1982年提出了經典粗糙集理論，隨著數據挖掘等信息技術的迅速發展，經典粗糙集理論現已被廣泛用于處理不確定數據及特征選擇問題，成為分析處理不精確、不一致、不完整等不完備信息的有效工具.基于經典粗糙集理論，眾多學者提出了優勢粗糙集[2]、鄰域粗糙集[3-6]等廣義粗糙集模型.

Lin[7]在1998年首次提出“粒計算”概念.粒計算作為一種處理多尺度數據的方法，注重在各種粒度層面上進行數據處理.采用這種多粒度視角，粗糙集理論在處理多尺度或分層信息時的效率得以顯著提升，尤其是在特征選擇和數據分類等方面.這種多層次的數據處理方法在醫療診斷、圖像識別、決策支持系統等多個領域中得到應用，并展示了其在處理模糊、不確定或不完整信息方面的強大能力.將粒計算理念融入到粗糙集理論中，諸如多粒度粗糙集[8-10]這樣的模型便得以誕生.這類模型通過考慮不同粒度層次上的知識，為分析復雜信息系統提供了新的視角.而現實世界的應用場景復雜多變，一個樣本在某特定特征上可能存在多個不同等級的評價尺度.針對這一問題，Wu 等[11]提出了Wu-leung 多尺度信息系統模型.對于尋找多尺度決策信息系統中尺度的變化規律與最優尺度選擇，Chen 等[12-13]利用三支決策研究目標動態增長條件下局部最優尺度的更新規律.在保持系統的不確定域不變的情況下，首先探討了對象增量情況下決策信息系統中決策類的不確定性更新規律.其次，利用序列三向決策理論給出了保持決策類不確定性的局部最優尺度的定義，并利用決策類不確定性的更新機制給出了最優尺度的更新規律.Li 等[14]利用三支決策中的不確定域，探討了最優尺度變大或者不變的充要條件.Yang 等[15]提出了一種新的成本敏感多粒度S3WD 模型，對于S3WDRFS 及其三個區域，以層次顆粒結構揭示了其決策代價的變化規律，通過考慮用戶的需求，討論如何實現目標優化機制與總成本最低的最優粒度.Hao等[16]應用序貫三支決策理論研究了該系統中決策類別的不確定性與尺度變化之間的關系，提出了不確定性的最優尺度選擇，并給出了添加新對象時的更新規律.目前大部分研究集中在如何選取多尺度決策信息系統的最優尺度組合[17-21].

圖論中求解極小頂點覆蓋問題為一個NP-hard問題，長期以來，許多學者對該課題從不同層面或不同角度的進行了探索和研究.Chavatal[22]在1979 年提出了經典的頂點覆蓋算法.Chen 等[23]研究了特征子集選擇與極小頂點覆蓋之間的關系，發現求圖的極小頂點覆蓋等價于求信息系統的特征子集選擇.同時，特征子集選擇亦可轉化為圖的極小頂點覆蓋的計算.Mi等[24]利用圖論的相關理論方法，對基于區分矩陣的粗糙集特征選擇方法給出了直觀和等價的刻畫.Zhang 等[25]利用圖的思想研究了覆蓋決策信息系統特征子集選擇算法，首先計算覆蓋決策信息系統的辨識集，進而得到一個超圖的關聯矩陣.然后，基于貪心法求該超圖的極小頂點覆蓋，該方法可以看作是一種局部逼近最優的特征子集選擇策略.Jin 等[26]通過構造多尺度辨識矩陣，將辨識矩陣與多尺度信息系統結合，探究其特征選擇與最優尺度選擇.

目前已有研究中的多尺度決策信息系統的特征選擇與最優尺度選擇算法，在面對高維尺度以及海量樣本時具有較高的時間復雜度以及時常陷入局部最優解.利用圖論解決該問題的傳統方法中，邊的數目繁多且不直觀，不利于獲取極小頂點覆蓋.將超圖與多尺度信息系統結合，控制特征鄰接關系數目，利用超圖對多尺度信息系統中特征的鄰接關系可視化，提出了基于超圖的多尺度信息系統最優尺度特征求解算法，在處理高維度數據時具有顯著的優勢.

1 預備知識

本節介紹關于多尺度決策信息系統中的基本知識.

定義1[27]設S=(U，C)為一個信息系統，U是非空有限論域，C為特征集.對于任意特征a∈C，稱a:U→Va是信息函數，Va稱為特征a的值域．

定義2[20]設S=(U，C) 為一個信息系統，C為特征集 對B?C且B≠?，有不可辨識關系RB={(xi，xj)∈U|?b∈B(b(xi)=b(xj))}.顯然RB為U上的等價關系.論域U被RB劃分為兩兩不相交的等價類U/RB={[xi]B|x∈U}，其中

設X為U的任意非空子集，定義X關于特征子集B的上近似和下近似為

定義3[20]設S=(U，C∪D)為一個決策信息系統，D為決策特征類，由?d∈D誘導的不可辨識關系Rd，若RC?RD，則稱該決策信息系統S是協調的，否則稱決策信息系統S是不協調的.

定義4[20]設S=(U，C∪D)為一個協調決策信息系統，設B?C，稱B為協調決策信息系統S的一個特征選擇子集，若B滿足

1） [xi]B?[xi]D，?xi∈U；

2）?a∈B，?x∈U，[xi]B-{a}≠[xi]B.

定義5[10]設S=(U，C∪D)為一個協調決策信息系統，假設C中的每個特征都具有I個等級的尺度，決策類D為單一等級的尺度，則多尺度決策信息系統可以表示為

對于1≤t≤l，存在映射，即，其中為粒度信息轉換函數.

性質1[17]設S=(U，C∪D)為一個協調多尺度決策信息系統，其中B為C的一個特征子集，xi，xj∈U，對?at∈B,t∈[1，2，···，I]，滿足

1）RBt={(xi，xj)∈U×U|at(xi)=at(xj)}；

2）[xi]Bt={xj∈U|(xi，xj)∈RBt}={xj∈U|at(xi)=at(xj)}；

3）U/RBt={[xi]Bt}.

則有RB1?RB2?…?RBI，[xi]B1?[xi]B2?…?[xi]BI.

定義6[21]設S=(U，C∪D)為一個廣義多尺度決策信息系統，對于特征am∈C，取第lm等級的尺度，m=1，2，…，n.定義指標序列K=(l1，l2，…，ln)，有，SK=(U，CK∪D)，則稱K為SK在S中的一個尺度組合，記所有的尺度組合為κ.

定義7[21]設S=(U，C∪D) 為一個協調多尺度決策信息系統，κ是S的所有尺度組合，對K1=(l11，l12，…，l1n)，K2=(l21，l22，…，l2n)∈κ，若對于m=1，2，…，n均有l1m≤l2m，則稱尺度組合K1細于K2，記作K1-?K2.

進一步地，若K1?-K2且?p∈{1，2，…，n}，使得lp1＜lp2，則稱尺度組合K1嚴格細于K2，記作K1?K2.

性質2[21]設S=(U，C∪D)為一個協調多尺度決策信息系統，尺度組合K1=(l11，l12，…，l1n)，K2=(l21，l22，…，l2n)∈κ，有

其中：lj=min{l1j，l2j}，Lj=max{l1j，l2j}，j=1，2，…，n.

定義8[28,30]給定一個協調多尺度決策信息系統S=(U，C∪D)，對?xi，xj∈U，定義|U| ×|U|的矩陣M為S的辨識矩陣，其中

對于協調多尺度決策信息系統S=(U，C∪D)的其辨識矩陣M，其辨識函數定義為

其中：∨M(xi，xj)表示辨識矩陣M中所有辨識集的析取；∧M(xi，xj)表示辨識矩陣M中所有辨識集的合取．

性質3[29-30]設S=(U，C∪D)為一個協調多尺度決策信息系統，B?C是S的一個特征子集當且僅當是fM的主蘊含項.

2 多尺度決策信息系統特征鄰接關系及其誘導的超圖

本節定義了β鄰域，用樣本間的距離構造了極小相似對，生成特征間的鄰接關系，利用超圖將其可視化.探究求解信息系統中的特征子集選擇與對應超圖的極小頂點覆蓋問題間的關系．

受到文獻[31]的啟發，類似地定義樣本關于特征的鄰域.

定義9設S=(U，C∪D)為一個協調多尺度決策信息系統，對am∈C，xi∈U，給定閾值β∈[0，1]，若有xj∈U，使得d(xi)=d(xj)或|atm(xi)-atm(xj)| ＜β，t=1，2，…，I，稱xj在xi關于特征am的β鄰域中.記(xi)為xi關于特征am的β鄰域，其中

定義10設S=(U，C∪D)為一個協調多尺度決策信息系統，am∈C，xi∈U，給定閾值β∈[0，1]，若有xj∈U，使得d(xi)≠d(xj)且，則xj在xi關于特征am的β鄰域的補集之中.記為xi關于特征am的β鄰域補集，其中

其中t=1，2，…，I，β為給定的閾值.因，故(xi)為xi的一個去心領域.

性質4設S=(U，C∪D)為一個協調多尺度決策信息系統，其中Nβam(xi)為xi關于特征am的β鄰域，(xi)為xi關于特征am的β鄰域補集，有

定義11設S=(U，C∪D)為一個協調多尺度決策信息系統，(xi)為xi關于特征atm的β鄰域補集，對?xj∈(xi)，定義(xi，xj)為xi關于特征am的相似對，記特征am的所有相似對為δ(am).

對于(xi，xq)∈δ(am)，若不存在(xi，xp)∈δ(am)，使d(xi，xp)＜d(xi，xq)，那么稱(xi，xp)為特征am下的極小相似對，記為δmin(am).其中

定義12[22]設G=(V，E)為超圖，V代表包含對象的集合，E為基于V構建的超邊ei的集合.在傳統圖結構中，它的一個邊只能和兩個頂點連接，若邊的端點重合為一個頂點，則稱為環.超圖是在傳統圖上的泛化.在超圖中，每條邊可以連接任意數量的頂點，記邊ei中的頂點集為N(ei)．

定義13[32]給定圖G=(V，E)，對于V'?V，若V'中的頂點能覆蓋圖G所有邊，那么稱V'為圖G的一個支配集.若V'為圖G的一個支配集，對?v∈B，若V'-{v}不能覆蓋圖G的所有邊，那么稱支配集V'為圖G的一個極小頂點覆蓋．

性質5[23,32]給定圖G=(V，E)，v∈V'?V，若V'是圖G的極小頂點覆蓋當且僅當是fG的一個主蘊含項，其中

定義14設S=(U，C∪D)為一個協調多尺度決策信息系統，記R(C)={R(a1)，R(a2)，…，R(an)}為C的特征組合集，其中am∈C，δmin(am)=(xi，xj)，有R(am)={atk||atk(xi)-atk(xj) |≥β}.

受到文獻[23]的啟發，根據定義14 得到的特征間鄰接關系R(C)，類似地定義多尺度決策信息系統誘導的鄰接矩陣.

定義15設S=(U，C∪D)為一個協調多尺度決策信息系統，對于atk∈C，k∈{1，2，…，m}，t∈{1，2，…，I}，定義|m| ×|m×I|的矩陣Is為多尺度決策信息系統誘導的鄰接矩陣，即

Is(am，atk)代表的位置為矩陣Is的第m行，第((k-1)×I+t)列.

令e∈R(C)，表示e為R(C)中的元素，記V=C，E={e∈R(C)}.稱GS=(V，E)為協調多尺度決策信息系統S的所生成的超圖.

由定義15 可知，超圖GS實際上是協調多尺度決策信息系統S的特征作為頂點集，以鄰接關系作為邊集，是特征間的鄰接關系的直接刻畫.根據性質3 和性質5，可知通過鄰接矩陣生成的超圖的極小頂點覆蓋與該決策信息系統S的特征選擇子集是相同的[23-24,33].故求決策信息系統的特征選擇問題亦可轉化為求相應圖的極小頂點覆蓋問題.

例1設S=(U，C∪D)為給定的協調多尺度決策信息系統，U={x1，x2，…，x6}，D={0，1}，特征類C={al1，al2，al3}，其中l=1，2，3，β=0.5，詳見表1.

表1 協調多尺度決策信息系統Tab.1 Generalized coordination multi-scale decision information systems

對于協調多尺度決策信息系統S，計算可得所有相似對為

根據式（9），計算得到特征下的極小相似對δmin(a1)=(x2，x5)，δmin(a2)=(x2，x5)，δmin(a4)=(x2，x3).計算極小相似對中的特征間鄰接關系，可得R(a1)={a21，a32}，R(a2)={a21，a32}，R(a3)={a12，a32，a13，a23}.令V=C，E=R(C)，得到表2 所示的鄰接矩陣，用超圖將其可視化，如圖1 中的超圖G所示.由于v11，v31，v22，v33并未出現在任一邊中，與其他頂點均未連接，不另外表出.根據式（10）可得

圖1 鄰接矩陣誘導的超圖Fig.1 Hypergraph induced by adjacency matrix

表2 多尺度決策信息系統誘導的鄰接矩陣Tab.2 Adjacency matrix induced by multi-scale decision information systems

由此可得圖超圖G的極小頂點覆蓋有{v32}，{v21，v12}，{v21，v13}，{v21，v23}.令V=C，可得{a32}，{a21，a12}，{a21，a13}，{a21，a23}為協調多尺度決策信息系統S的尺度特征選擇子集.

根據布爾函數求解超圖的極小頂點覆蓋，在頂點數相同或是極小頂點覆蓋中尺度相近，往往無法明確得到一個最優解，接下去探究對超圖中頂點的提取規則，以得到極小頂點覆蓋的最優解.

3 基于超圖的多尺度決策信息系統最優尺度特征選擇

目前關于多尺度決策信息系統的最優尺度組合算法，在處理高維度樣本時效率不高且易陷入局部最優，而利用圖論解決該問題的傳統方法中，邊數目繁多復雜，兩者都影響了數據挖掘效率.針對這些問題提出基于超圖的多尺度決策信息系統最優尺度特征求解算法.

定義16設S=(U，C∪D)為一個協調多尺度決策信息系統，對?R(am)≠φ，?atm∈R(am)使得Ram-{}=φ，則稱R(am)為核心子集.定義core(C)為核心特征集.若atm∈core(C)，稱為核心特征.

定義17設S=(U，C∪D)為一個協調多尺度決策信息系統，R(C)為特征間的鄰接關系，對?atm∈R(am)，R(am)≠{}，有

1）當core(C)∩R(am)≠?，稱R(am)為不必要子集，記Run(C)為全體不必要子集；

2）當core(C)∩R(am)=?，稱R(am)為必要子集，記Rne(C)為全體必要子集，∩Rne(C)為所有必要子集的交．

定義18設S=(U，C∪D)為一個協調多尺度決策信息系統，對第k個特征，有atk?core(C)，且∩Rne(C)={apk}，那么apk為特征選擇子集中的必要特征.對apk，aqk∈∩Rne(C)，若q＜p，那么apk為特征選擇子集中的必要特征，為特征選擇子集中的不必要特征.

性質6設S=(U，C∪D)為一個協調多尺度決策信息系統，對第k個特征，有atk?core(C)，且∈∩Rne(C).apk為特征選擇子集中的不必要特征當且僅當?aqk∈∩Rne(C)，且p＜q.

證明首先證明其必要性.因apk為特征選擇子集中的不必要特征，則有apk∈∩Rne(C).若不存在∈∩Rne(C)，其中aqk∈C且p＜q，那么apk為特征選擇子集中的必要特征.這與apk為特征選擇子集中的不必要特征所矛盾，可得?apk∈∩Rne(C).

其次證明充分性，當apk，aqk∈∩Rne(C)，且p＜q，由定義18可得apk為不必要特征.

定義19設S=(U，C∪D)為一個協調多尺度決策信息系統，?ak∈C∧ak?core(C)，記當前必要子集數目|Rne(C)| =γC.定義?(alk)為alk的特征權重，其中

令E=R(C)，V=C.對?vi，vj∈V，若?(vi)＞?(vj)，有vi?vj，定義“?”為頂點優先序.當?(vpi)=?(vqi)，若p＜q，則vqi?vpi.進一步地，為了減少極小頂點覆蓋的搜索成本，若vqi為必要特征，則令vri=0，其中r＜q.

當記max ?(v)為當前頂點優先序下的首位頂點.核心頂點集不能覆蓋所有的邊時，依照優先序，添加max ?(v)至極小頂點覆蓋中.若max ?(v)不唯一，則同時選取.

例2設S=(U，C∪D)為給定一個協調多尺度決策信息系統，其中U={x1，x2，…，x8}，決策類D={0，1}，特征類，l=1，2，3，給定β=0.5，詳見表3.

表3 協調多尺度決策信息系統Tab.3 Generalized coordinated multi-scale decision information systems

根據定義11可得每個特征的相似對為

由此可得到每個特征下的極小相似對

計算極小相似對中的特征間鄰接關系，可得

令E=V，得到如表4所示的多尺度決策信息系統誘導的鄰接矩陣.用超圖將其可視化，如圖2所示.

圖2 鄰接矩陣誘導的超圖Fig.2 Hypergraph induced by adjacency matrix

表4 多尺度決策信息系統誘導的鄰接矩陣Tab.4 Adjacency matrix induced by multi-scale decision information systems

由于v21、v31、v23、v33并未出現在任一鄰接關系中，故與其他頂點均無超邊連接，不額外表出.N(e1)中只有一個頂點，core(V)={v11}，去除v11所覆蓋的邊剩下的邊為e2，e3，計算N(e2)，N(e3)中頂點的權重，同時，對?vt1，t∈l，令?()=0.

計算可得?(v12)=0.5，?(v22)=0.5，?(v32)=1，?(v13)=0.5.計算頂點優先序，可得v32?v13=v22=v12，此時max ?(v)=v32，將v32添加到極小頂點覆蓋集當中，刪除被v32所覆蓋的邊，此時已無剩余邊，令C=V，故{a11，a32}為協調多尺度決策信息系統S的一個特征選擇子集.

根據例3的求解步驟，給出基于超圖的多尺度決策信息系統最優尺度特征求解算法.

算法1 基于超圖的最優尺度特征求解算法(MGED算法)輸入:協調多尺度決策信息系統S=(U，C ∪D),alk:k ∈[1，n]， l ∈[1，I],閾值β輸出:最優尺度特征選擇子集Cη 1:根據定義11得到δmin(a)2:生成R(ak),令V=C,E=R(C),Ene=Rne(C),將其刻畫成超圖Gs 3:for k=1:n 4: while |N(ek)|=1 5: core(V)←core(V)∪{vlk}6: while N(ek)∩core(V)=?7: Ene ←Ene ∪ek 8:Cη←Cη∪core(V)9:while E ≠?10: 計算?(v),對?vt m ∈Cη,令?(vpm)=0,其中p=1，2，…，l.對?(v)排序11: if max ?(v)=vtm∧?vpm ∩core(V)=?12: Cη←Cη∪vt m 13: if vt m ∩N(ek)≠?14: Ene ←Ene-ek 15: else 16: ?(vpm)←0 17: end if 18: else 19: ?(vpm)←0 20: end if 21:令C=V,輸出Cη

MGED 算法在步驟1～2 中的時間復雜度為O(|U|*n*I)，在步驟3～8 中時間復雜度僅為O(n).在步驟9～20中，僅有一層循環結構，該部分時間復雜度最為O(n!).因此，對于高維度數據集，MGED 算法能夠有效提高特征選擇的效率.

4 實驗設計與分析

為了驗證算法的有效性，對算法進行數值實驗分析與對比.CDG 算法[34]、GBFS 算法[26]都是采用圖論方法來對多尺度信息系統求解最優尺度組合.CDG 算法是在單尺度信息系統進行特征選擇，采用辨識矩陣來刻畫圖的每一個邊集；而GBFS 算法則是將其推廣到協調多尺度決策信息系統.兩種算法與MGED算法均具有一定的對比性.

實驗選取了10個UCI上的公開數據集，數據集基本信息如表5所示.有高維數據集也有低維數據集.β取值均為0.5，每個數據集運行10次，取10次的平均成績來對比分析各個算法的性能水平.

表5 數據集基本信息Tab.5 Basic information about the datasets

值得注意的是，UCI中的數據集均為單尺度數據集，因此先對這些數據集進行預處理.

1）刪除具有缺失特征的樣本.

2）將特征中的語義型數據轉化為數值型數據.

3）利用類似合并相鄰方法將單一尺度擴充成為多尺度.定義?σk(at)為特征a第t等級下的第k個特征相似域，其中σ為特征相似域的容量.

將原始尺度記為第1等級尺度，則有?σ1(a1m)為特征am在第1等級下的特征相似域，且特征相似域容量為σ1=1.將樣本按am的特征值升序排列，設?σ2(a2m)為第2等級的特征相似域，其容量為σ2，且σ2＞σ1.

將第1 等級尺度am下的每個特征值，按照順序分配至對應的特征相似域中，并取每個特征相似域中平均值生成第2 尺度.即第1 至第σ2個特征值分配到第1 個特征相似域并取均值，第σ2+1 至第2σ2個特征值分配到

第2個特征相似域并取均值，以此類推，結果均保留兩位小數.若最后一個特征相似域中特征值數目不足σ2，則在取均值時從前一個特征相似域中隨機挑選對應數量的特征值加入計算.直至遍歷完所有尺度特征.

設第3尺度等級的特征相似域為φσ3(a3)，其中σ3＞σ2，依照生成第2尺度方法，將第2尺度下的特征值分配至?σ3(a3)，生成第3尺度.直到生成最后一個尺度.本次實驗對所有數據集統一選取10個等級尺度，且σn=n.

文中的算法均在基于Python3.9的Spyder軟件中實現，并在裝有Windows 10的個人電腦上運行，電腦核心處理器為i5-10300H，四核心八線程，主頻2.5 GHz，最大睿頻4.5 GHz，運行內存為8 GB．

將每個數據集U平均分成10 個子集{U1，U2，…，U10}.將U1作為第一個臨時數據集，即10%的樣本，U1∪U2作為第二個臨時數據集，樣本比例為20%，以此類推.對于每個特征，均取十個等級的尺度.

MGED 算法與GBFS 算法對于各比例樣本的時間差異，如圖3 所示.可以看出，MGED 算法在大部分數據集上都具有一定的時間優勢.在數據集維度較小時，MGED算法與GBFS算法差距并不十分明顯.但從圖的整體趨勢來看，樣本比例越大，兩個算法的時間差異越明顯.在100%的Ionosphere數據集與Cervical數據集中，MGED算法用時均不超過GBFS算法用時的4%.說明MGED算法在處理高維數據更具有優勢.采用十折交叉法將兩個算法在100%樣本比例下所得的特征子集結果，在CART、LDA、SVM、KNN、SDA 與3N 分類器上進行其分類性能評估.其中原始尺度記為RAW，最粗的尺度記為COAST，添加文獻[23]中的CED算法作為對比，對比結果如表6～11所示.

圖3 不同樣本比例下的時間變化Fig.3 Time variation at different parameter levels

表6 CART分類器上的精度比較Tab.6 Accuracy comparison on classifier CART （單位： %）

表7 LDA分類器上的精度比較Tab.7 Accuracy comparison on classifier LDA （單位： %）

表8 SVM分類器上的精度比較Tab.8 Accuracy comparison on classifier SVM （單位： %）

表9 KNN分類器（k=2）上的精度比較Tab.9 Accuracy comparison on classifier （k=2） KNN （單位： %）

表10 SDA分類器上的精度比較Tab.10 Accuracy comparison on SDA classifier （單位： %）

表11 3N分類器上的精度比較Tab.11 Accuracy comparison on classifier 3N （單位： %）

由表6～11可得，MGED算法的分類精度較于GBFS算法與最粗尺度，具有一定優勢.對于Chemical數據集，僅有MGED 算法在各個分類器上將分類精度保持在100%.MGED 算法在CART、LDA、SVM 與3N分類器上都有較好的表現.在KNN 與SDA 分類器上，分類精度接近原始數據的分類精度，對于GBFS 算法與CDG算法，MGED算法對多尺度信息系統進行特征選擇時能保持相對較好的分類訓練精度．

為了探究MGED 算法、GBFS 算法與CED 算法是否具有統計學上的差異，對三個算法進行Friedman檢驗.首先，假設三個算法的性能相同，當α=0.05 時，qα=0.05=2.344，F(2，18)的臨界值為3.555.在CART 分類器上的ΤF=2.650 5，在LDA 與3N 分類器上的ΤF值均為4.483 1，在SVM 分類器上的ΤF=4.793，在KNN分類器上的ΤF=3.720，同時在SDA分類器上的ΤF=1.714.

可知在α=0.05 時，原假設在LDA、SVM、KNN 與3N 分類器上被拒絕.為了進一步驗證結論，對其進行Nemenyi 后續檢驗，CD 值為1.048.結果如圖4 所示，可以看出三個算法在CART 與SDA 分類器上并沒有顯著性差異，而在LDA、SVM、KNN與3N分類器上都有顯著性差異，這與假設性檢驗結果一致.

圖4 分類學習精度的Nemenyi檢驗Fig.4 Nemenyi test for categorical learning accuracy

為了進一步驗證MGED模型的有效性，對每個模型得到的特征子集在分類器上的訓練時間進行對比，結果如圖5所示.可以看出，MGED 算法在大部分數據集中，訓練時間優于原始數據集及GBFS與CED 算法.在SVM分類器上，因為所有模型的訓練時間較為接近，但是MGED算法在10個數據集中，有8個數據集的訓練時間小于其他模型的訓練時間.相較于最粗尺度，MGED算法在訓練時間上依舊具有一定優勢.

圖5 模型在分類器上的訓練時間對比Fig.5 Comparison of the training time of the model on the classifier

當尺度較粗時可能出現信息系統不協調的情況，故對分類訓練時間有些許影響.在KNN分類器上的訓練時間相較于其他模型具有較為明顯的優勢.整體上看MGED 算法能更好的去除冗余特征，更利于數據的分類與預測.

5 總結與展望

針對多尺度決策信息系統的最優尺度組合與特征選擇問題，將圖論思想與協調多尺度信息系統相結合，提出了基于超圖的多尺度信息系統最優尺度特征求解算法.通過特征間的鄰接關系構造多尺度決策信息系統誘導的鄰接矩陣，利用超圖將其可視化，將求解信息系統的特征選擇子集與求解對應超圖的極小頂點覆蓋相聯.從減少必要子集的數量入手，減少超圖中不重要的超邊數量，以此大幅減少特征選擇的時間.因此，隨著數據規模的增加，算法始終能保持相對較低的運行時間.數值實驗結果表明，算法在分類訓練精度上具有一定優勢.在處理小數據集樣本，運行穩定的同時大幅度減少陷入局部最優的情況發生.對于具有海量樣本和高維特征的數據時，算法具有顯著的時間優勢以及相對較高的分類精度.今后將進一步研究如何優化極小相似對的生成算法，以及在多決策信息系統中的知識獲取問題.