翟俊海， 邵慶言， 苗 青

（河北大學(xué) 數(shù) 學(xué)與計(jì)算機(jī)學(xué)院，河北 保 定 071002）

0 引 言

粗糙集理論［1］是波蘭數(shù)學(xué)家Pawlak教授于1982年提出的一種數(shù)據(jù)挖掘方法，已成功應(yīng)用于數(shù)據(jù)挖掘、模式識別、機(jī)器學(xué)習(xí)及決策分析等領(lǐng)域。粗糙集理論是一種不確定性數(shù)據(jù)分析工具，與經(jīng)典集合論、模糊集理論并稱三大集合理論［2］。

Pawlak建立的粗糙集模型是架構(gòu)在等價(jià)關(guān)系基礎(chǔ)上的，用一對逼近算子（上近似算子和下近似算子）逼近目標(biāo)概念。在逼近目標(biāo)概念時(shí)，不需要任何先驗(yàn)知識，所以經(jīng)典粗糙集模型是一種完全數(shù)據(jù)驅(qū)動的方法。但經(jīng)典粗糙集模型只能處理離散值數(shù)據(jù)，使其應(yīng)用有一定的困難。許多研究人員從不同的角度對經(jīng)典粗糙集模型進(jìn)行了擴(kuò)展［3－12］。在允許有一定錯(cuò)分率的情況下，文獻(xiàn)［3］提出了變精度粗糙集模型。文獻(xiàn)［4－5］通過在經(jīng)典粗糙集模型中引入概率方法，提出了概率粗糙集模型。文獻(xiàn)［6］通過將決策理論引入到經(jīng)典粗糙集，提出了決策粗糙集模型。這3種擴(kuò)展模型是在等價(jià)關(guān)系的框架下，只對上近似算子和下近似算子的定義進(jìn)行了改進(jìn)。文獻(xiàn)［7］將等價(jià)關(guān)系擴(kuò)展為一般二元關(guān)系，提出了廣義粗糙集模型。文獻(xiàn)［8］將等價(jià)關(guān)系擴(kuò)展為優(yōu)勢關(guān)系，提出了基于優(yōu)勢關(guān)系的粗糙集模型。文獻(xiàn)［9］將等價(jià)關(guān)系擴(kuò)展為相容關(guān)系，提出了相容粗糙集模型。在這3種擴(kuò)展模型中，被逼近的目標(biāo)概念和經(jīng)典粗糙集是一樣的，但將等價(jià)關(guān)系進(jìn)行了擴(kuò)展。文獻(xiàn)［10］將被逼近的目標(biāo)概念擴(kuò)展為模糊集，等價(jià)關(guān)系擴(kuò)展為模糊相似關(guān)系，提出了模糊粗糙集模型。相容粗糙集模型和模糊粗糙集模型均可以處理實(shí)值數(shù)據(jù)庫。文獻(xiàn)［11］對近年來國內(nèi)外粗糙集理論研究的現(xiàn)狀進(jìn)行了綜述，并討論了當(dāng)前粗糙集理論的熱點(diǎn)研究領(lǐng)域以及將來需要重點(diǎn)研究的主要問題。

ELM（Extreme Learning Machine）是用于訓(xùn)練單隱含層前饋神經(jīng)網(wǎng)絡(luò)（Single－h(huán)idden Layer Feed－forward Network，簡稱 SLFN）的學(xué)習(xí)算法［12－13］。不同于反向傳播算法（如 BP算法），ELM算法不需要反復(fù)迭代，它隨機(jī)生成輸入層到隱含層的權(quán)值和偏置，然后用分析的方法確定隱含層到輸出層的權(quán)值。近年來，ELM已成為神經(jīng)網(wǎng)絡(luò)領(lǐng)域的一個(gè)研究熱點(diǎn)，引起了眾多研究人員的興趣，并成功應(yīng)用于人臉識別［14］、手寫數(shù)字識別［15］、時(shí)間序列預(yù)測［16］及嶺回歸［17］等領(lǐng)域。

ELM算法存在結(jié)構(gòu)選擇的問題，即有效地確定網(wǎng)絡(luò)隱含層結(jié)點(diǎn)的個(gè)數(shù)。確定ELM網(wǎng)絡(luò)結(jié)構(gòu)的算法可分為增量算法和剪枝算法2類。文獻(xiàn)［18］提出了一種增量學(xué)習(xí)算法，該算法在初始化的單隱含層前饋神經(jīng)網(wǎng)絡(luò)基礎(chǔ)上逐個(gè)或者逐組增加隱含層結(jié)點(diǎn)，直到算法的精度達(dá)到預(yù)定的目標(biāo)。文獻(xiàn)［19］提出了一種基于統(tǒng)計(jì)方法的剪枝算法，算法的基本思想是先初始化大量的隱含層結(jié)點(diǎn)，然后使用統(tǒng)計(jì)的方法對隱含層結(jié)點(diǎn)按重要程度進(jìn)行排序，并剪掉重要程度低的隱含層結(jié)點(diǎn)。但該方法需要離散化預(yù)處理，容易產(chǎn)生信息丟失，且計(jì)算復(fù)雜度高。針對這一問題，本文提出了一種基于相容粗糙集技術(shù)的剪枝算法，用于確定ELM網(wǎng)絡(luò)的結(jié)構(gòu)。

1 基本概念

1.1 相容粗糙集

相容粗糙集理論［9］是經(jīng)典粗糙集理論的推廣，它用相容關(guān)系（或相似關(guān)系）代替不可分辨關(guān)系（或等價(jià)關(guān)系），不僅可以發(fā)現(xiàn)屬性值之間的相似性，還可以消除屬性值之間的微小偏差，從而提高系統(tǒng)決策的魯棒性，也可有效提高決策的效率。在相容粗糙集理論中，按相容關(guān)系劃分得到的相容類一般不構(gòu)成對論域的劃分，而是構(gòu)成對論域的覆蓋，即把知識看作是關(guān)于論域的覆蓋。

定義1 信息系統(tǒng)是一個(gè)四元組IS＝（U，A，V，F(xiàn)）。其中，U＝｛x1，x2，…，xn｝為有限對象的非空集合，稱為論域；A為用于描述對象的屬性的集合為屬性a∈A的取值范圍；F∶U×A→V稱為信息函數(shù)，滿足?a∈A，?x∈U，F(xiàn)（x，a）∈Va。若A＝C∪D，C為條件屬性集合，D為單決策屬性，則稱IS為決策系統(tǒng)或決策表，記為DT＝ （U，C∪D，V，F(xiàn)）。

定義2 給定決策系統(tǒng)DT＝（U，C∪D，V，F(xiàn)），R為定義在論域U上的二元關(guān)系，R為相容關(guān)系（或相似關(guān)系），當(dāng)且僅當(dāng)R滿足：

（1）自反性。?x∈U，有xRx。

（2）對稱性。?x，y∈U，若xRy，則yRx。

對 于 給 定 的 決 策 系 統(tǒng)DT＝（U，C∪D，V，F(xiàn)） ，可以在論域U上定義多種相似關(guān)系R［14］，即

其中，a∈C；σa為屬性a的方差；a（x）和a（y）分別為樣例x和y在屬性a上的取值；amax∈Va和amin∈Va分別為屬性a的最大值和最小值，稱Ra為由屬性a誘導(dǎo)出的相似關(guān)系。對于?P?C，定義屬性子集P誘導(dǎo)出的相似關(guān)系RP［15－16］為：

或

其中，τ∈［0，1］為相似性閾值。

定義3 給定決策系統(tǒng)DT＝（U，C∪D，V，F(xiàn)），P?C，RP為由屬性子集P誘導(dǎo)出的相似關(guān)系。對于?x∈U，定義x的RPτ相似類（或相容類為：

定義4 給定決策系統(tǒng)DT＝（U，C∪D，V，F(xiàn)），P?C，RP為由屬性子集P誘導(dǎo)出的相似關(guān)系。U／D＝｛U1，U2，…，Uk｝是決策屬性D對論域U的劃分。定義Ui關(guān)于RP的τ上近似和τ下近似分別為：

定義5 給定決策系統(tǒng)DT＝（U，C∪D，V，F(xiàn)），P?C，RP為由屬性子集P誘 導(dǎo)出的相似關(guān)系，則稱（9）式為P相對于D的τ正域，即

定義6 給定決策系統(tǒng)DT＝（U，C∪D，V，F(xiàn)），P?C，RP為由屬性子集P誘 導(dǎo)出的相似關(guān)系，稱（10）式為D相對于P的τ依賴度，即

1.2 ELM 算 法

給定訓(xùn)練集D＝｛（xj，yj）｜xj∈Rn，yj∈RK｝，j＝1，2，…，M。ELM是用于訓(xùn)練如圖1所示的單隱含層前饋神經(jīng)網(wǎng)絡(luò)的算法，網(wǎng)絡(luò)的輸入層結(jié)點(diǎn)個(gè)數(shù)為n，隱含層結(jié)點(diǎn)個(gè)數(shù)為N，輸出層結(jié)點(diǎn)個(gè)數(shù)為m。輸入層結(jié)點(diǎn)和輸出層結(jié)點(diǎn)的激活函數(shù)均為線性函數(shù)，隱含層結(jié)點(diǎn)的激活函數(shù)為Sigmoid函數(shù)。wi＝（w1i，w2i，…，wni）是輸入層的n個(gè)結(jié)點(diǎn)連接到隱含層第i個(gè)結(jié)點(diǎn)的連接權(quán)，i＝1，2，…，N。βi＝（βi1，βi2，…，βiK）是隱含層的第i個(gè)結(jié)點(diǎn)連接到輸出層K個(gè) 結(jié)點(diǎn)的連接權(quán)，i＝1，2，…，N。該神經(jīng)網(wǎng)絡(luò)的模型為：

（11）式的矩陣表示為：

其中，

H稱為隱含層輸出矩陣，H的第i列是第i個(gè)隱含層結(jié)點(diǎn)關(guān)于輸入樣例x1，x2，…，xM的輸出。H可逆時(shí)，權(quán)值β可以通過β＝H－1y求得，然而在大多情況下，訓(xùn)練樣例個(gè)數(shù)遠(yuǎn)遠(yuǎn)大于隱含層結(jié)點(diǎn)數(shù)量；矩陣H不可逆，上述方法便行不通。ELM算法使用Moore－Penrose廣義逆來近似求解權(quán)值β，即＝H＋y，其中H＋為隱層輸出矩陣H的 Moore－Penrose廣義逆矩陣。ELM 算法描述為：

（1）隨機(jī)初始化輸入層到隱含層的權(quán)值wi和偏置bi，i＝1，2，…，N。

（2）計(jì)算隱含層輸出矩陣H。

（3）計(jì)算隱含層到輸出層的權(quán)值＾β＝H＋y。

圖1 單隱含層前饋神經(jīng)網(wǎng)絡(luò)

2 基于相容粗糙集的ELM網(wǎng)絡(luò)結(jié)構(gòu)選擇

在ELM算法中，輸入層到隱含層實(shí)際上是一個(gè)隨機(jī)映射，它把n維樣例空間映射到了一個(gè)N維特征空間。隱含層輸出矩陣H的行對應(yīng)映射后的樣例點(diǎn)，列對應(yīng)特征空間的維數(shù)（屬性）。實(shí)際上，H為原樣例集合經(jīng)隨機(jī)映射后，在N維特征空間中對應(yīng)的樣例集合。為描述方便，設(shè)H的第i列用ai表示（i＝1，2，…，N）。因?yàn)椴煌袑?yīng)不同的隱含層結(jié)點(diǎn)，所以決策屬性D對ai的依賴度可用來表示隱含層結(jié)點(diǎn)i的重要度（i＝1，2，…，N），即對分類的貢獻(xiàn)。本文可以將對分類沒有貢獻(xiàn)或貢獻(xiàn)非常小的隱含層結(jié)點(diǎn)剪掉，算法首先將數(shù)據(jù)集分為訓(xùn)練集Tr和驗(yàn)證集Tv，然后從一個(gè)初始化的具有較多隱含層結(jié)點(diǎn)的SLFN開始，每次剪掉一個(gè)隱含層結(jié)點(diǎn)，直到滿足預(yù)定義的終止條件為止。算法的終止條件是使C（p）達(dá)到其最小值，C（p）定義為：

其中，RSS（p）＝－yi）2；ti為 SLFN 的實(shí)際輸出；Nv為驗(yàn)證集Tv中所含樣例的個(gè)數(shù)；σ2為SLFN在訓(xùn)練集Tr上的均方誤差的標(biāo)準(zhǔn)差；p為當(dāng)前網(wǎng)絡(luò)隱含層結(jié)點(diǎn)的個(gè)數(shù)。算法描述為：

（1）令τ＝τ0，將數(shù)據(jù)集劃分為交集為空集的2個(gè)子集Tr和Tv。

（2）初始化SLFN為含有M個(gè)隱含層結(jié)點(diǎn)的網(wǎng)絡(luò)，并用ELM在Tr上訓(xùn)練該網(wǎng)絡(luò)。

（3）對隱含層權(quán)矩陣H的每一列ai，即對隱含層每一個(gè)結(jié)點(diǎn)i，用 （ 10）式計(jì)算γai，τ（D）。

（4）令ak＝

（5）剪掉ak所對應(yīng)的隱含層結(jié)點(diǎn)k，得到新的網(wǎng)絡(luò)SLFN，并在Tr上重新訓(xùn)練新的網(wǎng)絡(luò)SLFN。

3 實(shí)驗(yàn)結(jié)果

為了進(jìn)一步驗(yàn)證本文算法的有效性，本文在8個(gè)UCI數(shù)據(jù)庫［20］上進(jìn)行了實(shí)驗(yàn)，實(shí)驗(yàn)所用數(shù)據(jù)庫的基本信息見表1所列。實(shí)驗(yàn)環(huán)境是PC機(jī)，雙核1.86GCPU，2G內(nèi)存，Windows XP操作系統(tǒng)，Matlab 7.1實(shí)驗(yàn)平臺。實(shí)驗(yàn)采用十折交叉驗(yàn) 證 的 方 法，與 原 始 ELM 算 法［12］、BP 算法［21］、文獻(xiàn)［18］和文獻(xiàn)［19］中的方法進(jìn)行了比較。實(shí)驗(yàn)中相容依賴度參數(shù)τ取為0.90，實(shí)驗(yàn)結(jié)果見表2所列。從表2可以看出，本文提出的方法在訓(xùn)練時(shí)間和測試精度上均優(yōu)于其他方法。

表1 實(shí)驗(yàn)所用數(shù)據(jù)庫的基本信息

表2 與相關(guān)方法進(jìn)行比較的實(shí)驗(yàn)結(jié)果

4 結(jié)束語

針對文獻(xiàn)［18］中提出的剪枝算法需要離散化預(yù)處理，有信息丟失、計(jì)算復(fù)雜度高等問題，本文提出了基于相容粗糙集技術(shù)的ELM網(wǎng)絡(luò)結(jié)構(gòu)選擇算法，該算法用相容依賴度來度量ELM網(wǎng)絡(luò)中隱含層結(jié)點(diǎn)的重要性，遞歸地剪掉對分類沒有貢獻(xiàn)或貢獻(xiàn)不大的隱含層結(jié)點(diǎn)，直到滿足預(yù)定義的終止條件。實(shí)驗(yàn)結(jié)果表明，本文算法是行之有效的。

［1］ Pawlak Z.Rough sets［J］.International Journal of Information and Computer Sciences，1982，11：341－356.

［2］ 苗奪謙，李道國.粗糙集理論、算法與應(yīng)用［M］.北京：清華大學(xué)出版社，2008：34－66.

［3］ Ziarko W.Variable precision rough set model［J］.Journal of Computer and System Sciences，1993，46（1）：39－59.

［4］ Yao Y Y.Probabilistic rough set approximations［J］.International Journal of Approximate Reasoning，2008，49（2）：255－271.

［5］ Yao Y Y.Probabilistic approachs to rough sets［J］.Expert Systems，2003，20（5）：287－297.

［6］ Yao Y Y，Wong S K M.A decision theoretic framework for approximating concepts［J］.International Journal of Manmachine Studies，1992，37（6）：793－809.

［7］ Yao Y Y.Generalized rough set models［C］／／Polkowski L，Skowron A.Rough Sets in Knowledge Discovery.Physica－Verlag Heidelberg，1998：286－318.

［8］ Greco S，Matarazzo B，Slowinski R.Rough Approximation of a preference relation by dominance relations［J］.European Journal of Operational Research，1999，117（1）：63－83.

［9］ Skowron A.Tolerance approximation spaces［J］.Fundamenta Informaticae，1996，27（2／3）：245－253.

［10］ Dubois D，Prade H.Rough fuzzy sets and fuzzy rough sets［J］.International Journal of General Systems，1990，17（1）：191－208.

［11］ 王國胤，姚一豫，于 洪.粗糙集理論與應(yīng)用研究綜述［J］.計(jì)算機(jī)學(xué)報(bào)，2009，32（7）：1229－1246.

［12］ Huang G B，Zhu Q Y，Siew C H.Extreme learning machine：theory and applications［J］.Neurocomputing，2006，70（1／2／3）：489－501.

［13］ Huang G B，Wang D H，Lan Y.Extreme learning machines：a survey［J］.International Journal of Machine Learning and Cybernetics，2011，2（2）：107－122.

［14］ Mohammed A A，Minhas R，Jonathan Q M，et al.Human face recognition based on multidimensional PCA and extreme learning machine［J］.Pattern Recognition，2011，44（10／11）：2588－2597.

［15］ Chacko B P，Krishnan V R V，Raju G，et al.Handwritten character recognition using wavelet energy and extreme learning machine ［J］.International Journal of Machine Learning and Cybernetics，2012，3（2）：149－161.

［16］ Dusan Sovilj，Antti Sorjamaa，Qi Yu，et al.OPELM and OPKNN in long－term prediction of time series using projected input data ［J］.Neurocomputing，2010，73（10／11／12）：1976－1986.

［17］ 王改堂，李 平，蘇成利.ELM嶺回歸軟測量建模方法［J］.合 肥 工 業(yè) 大 學(xué) 學(xué) 報(bào)：自 然 科 學(xué) 版，2011，34（8）：1150－1154.

［18］ Feng G R，Huang G B，Lin Q P，et al.Error minimized extreme learning machine with growth of hidden nodes and incremental learning ［J］.IEEE Transactions on Neural Networks，2009，20（8）：1352－1357.

［19］ Rong H J，Ong Y S，Tan A H，et al.A fast pruned－extreme learning machine for classification problem［J］.Neurocomputing，2008，72（2）：359－366.

［20］ Blake C L，Merz C J.UCI Repository of machine learning databases［EB／OL］.［2011－03－01］.http：／／www.ics.uci.edu／～mlearn／MLRepository.html.

［21］ Kumar S.Neural networks［M］.Beijing：Tsinghua Univesity Press，2006：167－176.