基于超圖的多尺度決策信息系統(tǒng)最優(yōu)尺度選擇

馬周明, 黃 閩, 林國(guó)平, 施虹藝

（1.閩南師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,福建 漳州 363000；2.閩南師范大學(xué)福建省粒計(jì)算及其應(yīng)用重點(diǎn)實(shí)驗(yàn)室,福建 漳州 363000）

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

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

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

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

1 預(yù)備知識(shí)

本節(jié)介紹關(guān)于多尺度決策信息系統(tǒng)中的基本知識(shí).

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

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

設(shè)X為U的任意非空子集，定義X關(guān)于特征子集B的上近似和下近似為

定義3[20]設(shè)S=(U，C∪D)為一個(gè)決策信息系統(tǒng)，D為決策特征類，由?d∈D誘導(dǎo)的不可辨識(shí)關(guān)系Rd，若RC?RD，則稱該決策信息系統(tǒng)S是協(xié)調(diào)的，否則稱決策信息系統(tǒng)S是不協(xié)調(diào)的.

定義4[20]設(shè)S=(U，C∪D)為一個(gè)協(xié)調(diào)決策信息系統(tǒng)，設(shè)B?C，稱B為協(xié)調(diào)決策信息系統(tǒng)S的一個(gè)特征選擇子集，若B滿足

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

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

定義5[10]設(shè)S=(U，C∪D)為一個(gè)協(xié)調(diào)決策信息系統(tǒng)，假設(shè)C中的每個(gè)特征都具有I個(gè)等級(jí)的尺度，決策類D為單一等級(jí)的尺度，則多尺度決策信息系統(tǒng)可以表示為

對(duì)于1≤t≤l，存在映射，即，其中為粒度信息轉(zhuǎn)換函數(shù).

性質(zhì)1[17]設(shè)S=(U，C∪D)為一個(gè)協(xié)調(diào)多尺度決策信息系統(tǒng)，其中B為C的一個(gè)特征子集，xi，xj∈U，對(duì)?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]設(shè)S=(U，C∪D)為一個(gè)廣義多尺度決策信息系統(tǒng)，對(duì)于特征am∈C，取第lm等級(jí)的尺度，m=1，2，…，n.定義指標(biāo)序列K=(l1，l2，…，ln)，有，SK=(U，CK∪D)，則稱K為SK在S中的一個(gè)尺度組合，記所有的尺度組合為κ.

定義7[21]設(shè)S=(U，C∪D) 為一個(gè)協(xié)調(diào)多尺度決策信息系統(tǒng)，κ是S的所有尺度組合，對(duì)K1=(l11，l12，…，l1n)，K2=(l21，l22，…，l2n)∈κ，若對(duì)于m=1，2，…，n均有l(wèi)1m≤l2m，則稱尺度組合K1細(xì)于K2，記作K1-?K2.

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

性質(zhì)2[21]設(shè)S=(U，C∪D)為一個(gè)協(xié)調(diào)多尺度決策信息系統(tǒng)，尺度組合K1=(l11，l12，…，l1n)，K2=(l21，l22，…，l2n)∈κ，有

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

定義8[28,30]給定一個(gè)協(xié)調(diào)多尺度決策信息系統(tǒng)S=(U，C∪D)，對(duì)?xi，xj∈U，定義|U| ×|U|的矩陣M為S的辨識(shí)矩陣，其中

對(duì)于協(xié)調(diào)多尺度決策信息系統(tǒng)S=(U，C∪D)的其辨識(shí)矩陣M，其辨識(shí)函數(shù)定義為

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

性質(zhì)3[29-30]設(shè)S=(U，C∪D)為一個(gè)協(xié)調(diào)多尺度決策信息系統(tǒng)，B?C是S的一個(gè)特征子集當(dāng)且僅當(dāng)是fM的主蘊(yùn)含項(xiàng).

2 多尺度決策信息系統(tǒng)特征鄰接關(guān)系及其誘導(dǎo)的超圖

本節(jié)定義了β鄰域，用樣本間的距離構(gòu)造了極小相似對(duì)，生成特征間的鄰接關(guān)系，利用超圖將其可視化.探究求解信息系統(tǒng)中的特征子集選擇與對(duì)應(yīng)超圖的極小頂點(diǎn)覆蓋問題間的關(guān)系．

受到文獻(xiàn)[31]的啟發(fā)，類似地定義樣本關(guān)于特征的鄰域.

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

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

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

性質(zhì)4設(shè)S=(U，C∪D)為一個(gè)協(xié)調(diào)多尺度決策信息系統(tǒng)，其中Nβam(xi)為xi關(guān)于特征am的β鄰域，(xi)為xi關(guān)于特征am的β鄰域補(bǔ)集，有

定義11設(shè)S=(U，C∪D)為一個(gè)協(xié)調(diào)多尺度決策信息系統(tǒng)，(xi)為xi關(guān)于特征atm的β鄰域補(bǔ)集，對(duì)?xj∈(xi)，定義(xi，xj)為xi關(guān)于特征am的相似對(duì)，記特征am的所有相似對(duì)為δ(am).

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

定義12[22]設(shè)G=(V，E)為超圖，V代表包含對(duì)象的集合，E為基于V構(gòu)建的超邊ei的集合.在傳統(tǒng)圖結(jié)構(gòu)中，它的一個(gè)邊只能和兩個(gè)頂點(diǎn)連接，若邊的端點(diǎn)重合為一個(gè)頂點(diǎn)，則稱為環(huán).超圖是在傳統(tǒng)圖上的泛化.在超圖中，每條邊可以連接任意數(shù)量的頂點(diǎn)，記邊ei中的頂點(diǎn)集為N(ei)．

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

性質(zhì)5[23,32]給定圖G=(V，E)，v∈V'?V，若V'是圖G的極小頂點(diǎn)覆蓋當(dāng)且僅當(dāng)是fG的一個(gè)主蘊(yùn)含項(xiàng)，其中

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

受到文獻(xiàn)[23]的啟發(fā)，根據(jù)定義14 得到的特征間鄰接關(guān)系R(C)，類似地定義多尺度決策信息系統(tǒng)誘導(dǎo)的鄰接矩陣.

定義15設(shè)S=(U，C∪D)為一個(gè)協(xié)調(diào)多尺度決策信息系統(tǒng)，對(duì)于atk∈C，k∈{1，2，…，m}，t∈{1，2，…，I}，定義|m| ×|m×I|的矩陣Is為多尺度決策信息系統(tǒng)誘導(dǎo)的鄰接矩陣，即

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

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

由定義15 可知，超圖GS實(shí)際上是協(xié)調(diào)多尺度決策信息系統(tǒng)S的特征作為頂點(diǎn)集，以鄰接關(guān)系作為邊集，是特征間的鄰接關(guān)系的直接刻畫.根據(jù)性質(zhì)3 和性質(zhì)5，可知通過鄰接矩陣生成的超圖的極小頂點(diǎn)覆蓋與該決策信息系統(tǒng)S的特征選擇子集是相同的[23-24,33].故求決策信息系統(tǒng)的特征選擇問題亦可轉(zhuǎn)化為求相應(yīng)圖的極小頂點(diǎn)覆蓋問題.

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

表1 協(xié)調(diào)多尺度決策信息系統(tǒng)Tab.1 Generalized coordination multi-scale decision information systems

對(duì)于協(xié)調(diào)多尺度決策信息系統(tǒng)S，計(jì)算可得所有相似對(duì)為

根據(jù)式（9），計(jì)算得到特征下的極小相似對(duì)δmin(a1)=(x2，x5)，δmin(a2)=(x2，x5)，δmin(a4)=(x2，x3).計(jì)算極小相似對(duì)中的特征間鄰接關(guān)系，可得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并未出現(xiàn)在任一邊中，與其他頂點(diǎn)均未連接，不另外表出.根據(jù)式（10）可得

圖1 鄰接矩陣誘導(dǎo)的超圖Fig.1 Hypergraph induced by adjacency matrix

表2 多尺度決策信息系統(tǒng)誘導(dǎo)的鄰接矩陣Tab.2 Adjacency matrix induced by multi-scale decision information systems

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

根據(jù)布爾函數(shù)求解超圖的極小頂點(diǎn)覆蓋，在頂點(diǎn)數(shù)相同或是極小頂點(diǎn)覆蓋中尺度相近，往往無(wú)法明確得到一個(gè)最優(yōu)解，接下去探究對(duì)超圖中頂點(diǎn)的提取規(guī)則，以得到極小頂點(diǎn)覆蓋的最優(yōu)解.

3 基于超圖的多尺度決策信息系統(tǒng)最優(yōu)尺度特征選擇

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

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

定義17設(shè)S=(U，C∪D)為一個(gè)協(xié)調(diào)多尺度決策信息系統(tǒng)，R(C)為特征間的鄰接關(guān)系，對(duì)?atm∈R(am)，R(am)≠{}，有

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

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

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

性質(zhì)6設(shè)S=(U，C∪D)為一個(gè)協(xié)調(diào)多尺度決策信息系統(tǒng)，對(duì)第k個(gè)特征，有atk?core(C)，且∈∩Rne(C).apk為特征選擇子集中的不必要特征當(dāng)且僅當(dāng)?aqk∈∩Rne(C)，且p＜q.

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

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

定義19設(shè)S=(U，C∪D)為一個(gè)協(xié)調(diào)多尺度決策信息系統(tǒng)，?ak∈C∧ak?core(C)，記當(dāng)前必要子集數(shù)目|Rne(C)| =γC.定義?(alk)為alk的特征權(quán)重，其中

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

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

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

表3 協(xié)調(diào)多尺度決策信息系統(tǒng)Tab.3 Generalized coordinated multi-scale decision information systems

根據(jù)定義11可得每個(gè)特征的相似對(duì)為

由此可得到每個(gè)特征下的極小相似對(duì)

計(jì)算極小相似對(duì)中的特征間鄰接關(guān)系，可得

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

圖2 鄰接矩陣誘導(dǎo)的超圖Fig.2 Hypergraph induced by adjacency matrix

表4 多尺度決策信息系統(tǒng)誘導(dǎo)的鄰接矩陣Tab.4 Adjacency matrix induced by multi-scale decision information systems

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

計(jì)算可得?(v12)=0.5，?(v22)=0.5，?(v32)=1，?(v13)=0.5.計(jì)算頂點(diǎn)優(yōu)先序，可得v32?v13=v22=v12，此時(shí)max ?(v)=v32，將v32添加到極小頂點(diǎn)覆蓋集當(dāng)中，刪除被v32所覆蓋的邊，此時(shí)已無(wú)剩余邊，令C=V，故{a11，a32}為協(xié)調(diào)多尺度決策信息系統(tǒng)S的一個(gè)特征選擇子集.

根據(jù)例3的求解步驟，給出基于超圖的多尺度決策信息系統(tǒng)最優(yōu)尺度特征求解算法.

算法1 基于超圖的最優(yōu)尺度特征求解算法(MGED算法)輸入:協(xié)調(diào)多尺度決策信息系統(tǒng)S=(U，C ∪D),alk:k ∈[1，n]， l ∈[1，I],閾值β輸出:最優(yōu)尺度特征選擇子集Cη 1:根據(jù)定義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: 計(jì)算?(v),對(duì)?vt m ∈Cη,令?(vpm)=0,其中p=1，2，…，l.對(duì)?(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 中的時(shí)間復(fù)雜度為O(|U|*n*I)，在步驟3～8 中時(shí)間復(fù)雜度僅為O(n).在步驟9～20中，僅有一層循環(huán)結(jié)構(gòu)，該部分時(shí)間復(fù)雜度最為O(n!).因此，對(duì)于高維度數(shù)據(jù)集，MGED 算法能夠有效提高特征選擇的效率.

4 實(shí)驗(yàn)設(shè)計(jì)與分析

為了驗(yàn)證算法的有效性，對(duì)算法進(jìn)行數(shù)值實(shí)驗(yàn)分析與對(duì)比.CDG 算法[34]、GBFS 算法[26]都是采用圖論方法來(lái)對(duì)多尺度信息系統(tǒng)求解最優(yōu)尺度組合.CDG 算法是在單尺度信息系統(tǒng)進(jìn)行特征選擇，采用辨識(shí)矩陣來(lái)刻畫圖的每一個(gè)邊集；而GBFS 算法則是將其推廣到協(xié)調(diào)多尺度決策信息系統(tǒng).兩種算法與MGED算法均具有一定的對(duì)比性.

實(shí)驗(yàn)選取了10個(gè)UCI上的公開數(shù)據(jù)集，數(shù)據(jù)集基本信息如表5所示.有高維數(shù)據(jù)集也有低維數(shù)據(jù)集.β取值均為0.5，每個(gè)數(shù)據(jù)集運(yùn)行10次，取10次的平均成績(jī)來(lái)對(duì)比分析各個(gè)算法的性能水平.

表5 數(shù)據(jù)集基本信息Tab.5 Basic information about the datasets

值得注意的是，UCI中的數(shù)據(jù)集均為單尺度數(shù)據(jù)集，因此先對(duì)這些數(shù)據(jù)集進(jìn)行預(yù)處理.

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

2）將特征中的語(yǔ)義型數(shù)據(jù)轉(zhuǎn)化為數(shù)值型數(shù)據(jù).

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

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

將第1 等級(jí)尺度am下的每個(gè)特征值，按照順序分配至對(duì)應(yīng)的特征相似域中，并取每個(gè)特征相似域中平均值生成第2 尺度.即第1 至第σ2個(gè)特征值分配到第1 個(gè)特征相似域并取均值，第σ2+1 至第2σ2個(gè)特征值分配到

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

設(shè)第3尺度等級(jí)的特征相似域?yàn)棣咋?(a3)，其中σ3＞σ2，依照生成第2尺度方法，將第2尺度下的特征值分配至?σ3(a3)，生成第3尺度.直到生成最后一個(gè)尺度.本次實(shí)驗(yàn)對(duì)所有數(shù)據(jù)集統(tǒng)一選取10個(gè)等級(jí)尺度，且σn=n.

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

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

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

圖3 不同樣本比例下的時(shí)間變化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算法與最粗尺度，具有一定優(yōu)勢(shì).對(duì)于Chemical數(shù)據(jù)集，僅有MGED 算法在各個(gè)分類器上將分類精度保持在100%.MGED 算法在CART、LDA、SVM 與3N分類器上都有較好的表現(xiàn).在KNN 與SDA 分類器上，分類精度接近原始數(shù)據(jù)的分類精度，對(duì)于GBFS 算法與CDG算法，MGED算法對(duì)多尺度信息系統(tǒng)進(jìn)行特征選擇時(shí)能保持相對(duì)較好的分類訓(xùn)練精度．

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

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

圖4 分類學(xué)習(xí)精度的Nemenyi檢驗(yàn)Fig.4 Nemenyi test for categorical learning accuracy

為了進(jìn)一步驗(yàn)證MGED模型的有效性，對(duì)每個(gè)模型得到的特征子集在分類器上的訓(xùn)練時(shí)間進(jìn)行對(duì)比，結(jié)果如圖5所示.可以看出，MGED 算法在大部分?jǐn)?shù)據(jù)集中，訓(xùn)練時(shí)間優(yōu)于原始數(shù)據(jù)集及GBFS與CED 算法.在SVM分類器上，因?yàn)樗心Ｐ偷挠?xùn)練時(shí)間較為接近，但是MGED算法在10個(gè)數(shù)據(jù)集中，有8個(gè)數(shù)據(jù)集的訓(xùn)練時(shí)間小于其他模型的訓(xùn)練時(shí)間.相較于最粗尺度，MGED算法在訓(xùn)練時(shí)間上依舊具有一定優(yōu)勢(shì).

圖5 模型在分類器上的訓(xùn)練時(shí)間對(duì)比Fig.5 Comparison of the training time of the model on the classifier

當(dāng)尺度較粗時(shí)可能出現(xiàn)信息系統(tǒng)不協(xié)調(diào)的情況，故對(duì)分類訓(xùn)練時(shí)間有些許影響.在KNN分類器上的訓(xùn)練時(shí)間相較于其他模型具有較為明顯的優(yōu)勢(shì).整體上看MGED 算法能更好的去除冗余特征，更利于數(shù)據(jù)的分類與預(yù)測(cè).

5 總結(jié)與展望

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