基于GA-DBN 模型的分類方法研究

師 展，安艾芝，樊重俊，秦小暉

（上海理工大學(xué) 管理學(xué)院，上海 200093）

0 引言

分類問題屬于數(shù)據(jù)挖掘的重要任務(wù)之一，即通過對數(shù)據(jù)進(jìn)行學(xué)習(xí)，建立合理的分類預(yù)測模型，得到目標(biāo)函數(shù)，實(shí)現(xiàn)將新的樣本數(shù)據(jù)屬性集對應(yīng)到目標(biāo)屬性分類。分類是一個(gè)監(jiān)督學(xué)習(xí)的過程，其處理“帶標(biāo)簽”的數(shù)據(jù)，即分類結(jié)果的類別標(biāo)簽均為已知的［1］。已知數(shù)據(jù)集的特征以及這些特征對應(yīng)的標(biāo)簽，算法會(huì)遍歷每一筆數(shù)據(jù)，盡可能正確地劃分?jǐn)?shù)據(jù)的類別。

分類問題可分為二分類問題與多分類問題。二分類問題處理包含兩種類別標(biāo)簽的數(shù)據(jù)，將每一個(gè)樣本盡可能正確地劃分到這兩個(gè)類別之一中，給定一個(gè)樣本作為輸入，輸出的答案只能有兩個(gè)，諸如：“是否”、“有無”問題即為二分類問題。多分類問題又可以區(qū)分為多類別問題和多標(biāo)簽問題，前者對含有多個(gè)類別的數(shù)據(jù)進(jìn)行處理，把每個(gè)樣本歸入一個(gè)類別，這樣每個(gè)樣本所歸屬的類別就是唯一的，不能同時(shí)歸入多個(gè)類別；后者是指一個(gè)樣本可以分到多個(gè)類別中，每個(gè)樣本所劃分的類別不是單一的，一個(gè)樣本可能同時(shí)有多個(gè)標(biāo)簽來描述，是一個(gè)樣本可以屬于多個(gè)類別的問題［2-3］。本文只對分類問題中的二分類問題進(jìn)行研究。

如何對所接觸的事物進(jìn)行合理分類是人類認(rèn)識(shí)世界、了解世界的重要途徑，同時(shí)也是機(jī)器學(xué)習(xí)領(lǐng)域的重點(diǎn)內(nèi)容［4］。獲得最佳的分類精度是各種分類器的最終目標(biāo)，主要通過以下步驟來實(shí)現(xiàn)：首先，通過對訓(xùn)練集數(shù)據(jù)進(jìn)行學(xué)習(xí)，構(gòu)建分類模型，明確分類的特定規(guī)則；其次，用已知的分類規(guī)則和分類模型在測試集上進(jìn)行檢測，達(dá)到一定的準(zhǔn)確度后，對新數(shù)據(jù)集進(jìn)行分類預(yù)測。為解決分類問題，學(xué)者們陸續(xù)提出了眾多分類算法，常用的分類算法包括K-近鄰、樸素貝葉斯分類算法、決策樹算法、支持向量機(jī)算法、人工神經(jīng)網(wǎng)絡(luò)算法等。

數(shù)據(jù)挖掘的主要工作包括數(shù)據(jù)描述和數(shù)據(jù)預(yù)測。數(shù)據(jù)描述是對數(shù)據(jù)之間存在的相關(guān)性、發(fā)展的趨勢、是否異常等潛在的聯(lián)系進(jìn)行歸納，預(yù)測是基于一部分?jǐn)?shù)據(jù)的屬性值，對另一部分?jǐn)?shù)據(jù)特定屬性的值做出判斷。當(dāng)對象為離散數(shù)據(jù)，預(yù)測的屬性值是離散且無序時(shí)，該任務(wù)即為分類任務(wù)。在分類任務(wù)方面，本文提出了遺傳算法優(yōu)化的DBN 模型，構(gòu)建基于遺傳算法改進(jìn)的GA-DBN 模型，并利用多個(gè)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，驗(yàn)證GA-DBN 模型在準(zhǔn)確率、F1值等方面優(yōu)于其他分類器。

1 模型構(gòu)建

1.1 遺傳算法

遺傳算法（Genetic Algorithms，GA）是經(jīng)典的群智能優(yōu)化算法之一。20 世紀(jì)60 年代遺傳算法這一名詞便開始初露頭角，但缺乏實(shí)踐研究；1975 年，遺傳算法在J.Holland 等學(xué)者出版的《自然系統(tǒng)和人工系統(tǒng)的適配》中有了系統(tǒng)的論述［5］；20 世紀(jì)80 年代后，GA 算法理論研究和應(yīng)用研究都成為專家學(xué)者們關(guān)注的重點(diǎn)，在組合優(yōu)化、機(jī)器學(xué)習(xí)等方面均占有一席之地。

群智能優(yōu)化算法受自然界和生物界規(guī)律的啟發(fā)，根據(jù)其原理模仿設(shè)計(jì)出計(jì)算機(jī)求解問題的算法。達(dá)爾文的生物進(jìn)化論與孟德爾的基因理論是遺傳算法的兩個(gè)重要理論基礎(chǔ)。生物進(jìn)化的基本過程如圖1 所示，種群中生物的生存與淘汰遵循“物競天擇，適者生存”的規(guī)律，群體中的個(gè)體經(jīng)過婚配產(chǎn)生子群體，進(jìn)化過程中生物機(jī)體的某些特性也會(huì)傳遞到后代身上，但也會(huì)產(chǎn)生新的個(gè)體特性。后代逐漸成長為新的群體淘汰舊群體。但為了保證多樣性，淘汰的可能性并不是由適應(yīng)度唯一決定，只是適應(yīng)度高的個(gè)體被淘汰的可能性低，適應(yīng)度低的個(gè)體也同樣可能進(jìn)入群體，只是進(jìn)入群體的可能低于適應(yīng)度高的個(gè)體。

圖1 生物進(jìn)化的基本過程Fig.1 The basic process of biological evolution

遺傳算法中通過遺傳操作尋找問題最優(yōu)解，基本流程如圖2 所示。算法涉及到參數(shù)編碼、初始群體設(shè)定、適應(yīng)度函數(shù)計(jì)算、遺傳操作和終止條件等基本要素。

圖2 遺傳算法的基本流程Fig.2 The basic process of genetic algorithm

遺傳操作包括選擇、交叉、變異，是算法的關(guān)鍵步驟。選擇就是從群體中淘汰部分個(gè)體，選擇出一部分優(yōu)良個(gè)體去繁殖子代。選擇需要遵循一個(gè)既能實(shí)現(xiàn)較快收斂又要維持種群多樣性方法，因此不能總挑選最好的個(gè)體也不能隨機(jī)選擇。常用的選擇方法有適應(yīng)度比例法、錦標(biāo)賽選擇策略及最佳個(gè)體保存方法。

交叉就是兩個(gè)生物機(jī)體彼此的染色體相互混合后產(chǎn)生新的染色體，即基因重組。父代的優(yōu)良基因和不良基因都有可能被后代繼承，但隨著種群進(jìn)化，后代總會(huì)比上一代生存和復(fù)制得更好。常用的交叉方法有實(shí)數(shù)重組法和二進(jìn)制交叉法。

變異就是個(gè)體基因在傳遞給后代的過程中發(fā)生改變，使其成為新的個(gè)體。變異可以對選擇及交叉過程進(jìn)行修復(fù)，避免算法出現(xiàn)早熟現(xiàn)象。常用的變異方法有實(shí)數(shù)變異法和二進(jìn)制變異法。

遺傳算法步驟如下：

（1）初始化種群。隨機(jī)生成一個(gè)有N個(gè)個(gè)體的初始群體pop（t），并對個(gè)體popi（t）進(jìn)行編碼，設(shè)定群體規(guī)模、迭代次數(shù)、終止條件等參數(shù)；

（2）計(jì)算適應(yīng)度。明確目標(biāo)函數(shù)，計(jì)算群體中各個(gè)個(gè)體的適應(yīng)度函數(shù)值，如式（1）：

（3）判斷是否滿足終止條件：滿足，算法終止；反之執(zhí)行下一步；

（4）選擇操作。在群體中，根據(jù)一定的概率，從中隨機(jī)選出一批個(gè)體形成一個(gè)新的群體；

（5）交叉操作。隨機(jī)指定兩個(gè)個(gè)體中染色體的一點(diǎn)進(jìn)行交換；

（6）變異操作。對某個(gè)個(gè)體染色體的部分基因進(jìn)行變異，得到新的個(gè)體；

（7）返回第（2）步，重復(fù)執(zhí)行直到找到最優(yōu)解。

1.2 深度置信網(wǎng)絡(luò)

深度置信網(wǎng)絡(luò)模型（Deep Belief Networks，DBN）將BP 算法（Back Propagation，BP）與多層受限玻爾茲曼機(jī)RBM（Restricted Boltzmann Machine，RBM）進(jìn)行組合，RBM 模型完成DBN 模型中無監(jiān)督的學(xué)習(xí)過程，有監(jiān)督學(xué)習(xí)則是由BP 算法來完成［6］。DBN 模型的組成結(jié)構(gòu)如圖3 所示。

圖3 DBN 模型的組成結(jié)構(gòu)Fig.3 Composition structure of DBN model

BP 算法在DBN 模型頂層逐層微調(diào)RBM 模型相關(guān)參數(shù)，盡量使模型的輸出與實(shí)際標(biāo)簽一致，以提高模型分類的準(zhǔn)確率，同時(shí)使DBM 模型達(dá)到整體最優(yōu)。在DBN 模型中，除了頂層的受限玻爾茲曼機(jī)，其它層之間的權(quán)重可以被分為向上的認(rèn)知權(quán)重和向下的生成權(quán)重。認(rèn)知權(quán)重向上逐層傳遞，與當(dāng)前層的輸入數(shù)據(jù)結(jié)合生成高一層的神經(jīng)元狀態(tài)，傳遞過程中采用梯度下降法尋找最優(yōu)狀態(tài)，生成權(quán)重向下與BP 神經(jīng)網(wǎng)絡(luò)結(jié)合生成低一層次的神經(jīng)元狀態(tài)，與實(shí)際神經(jīng)元狀態(tài)作對比求誤差。

DBN 訓(xùn)練過程如圖4 所示，主要分為兩步：

圖4 DBN 模型的訓(xùn)練過程Fig.4 Training process of DBN model

（1）分別單獨(dú)無監(jiān)督訓(xùn)練每一層RBM 網(wǎng)絡(luò)，確保特征向量映射到不同特征空間時(shí)都盡可能多的保留特征信息；

1.3 GA-DBN 模型的構(gòu)建

本文采用遺傳算法對深度置信網(wǎng)絡(luò)中的受限玻爾茲曼機(jī)的參數(shù)進(jìn)行逐層尋優(yōu)，從而構(gòu)建了GADBN 分類模型。遺傳算法從DBN 模型中最底層的RBM 模型開始權(quán)重尋優(yōu)，低層RBM 模型將遺傳算法訓(xùn)練后的權(quán)重矩陣進(jìn)行正向計(jì)算和反向傳播后得到隱含層，作為上層的RBM 模型的輸入層，上層RBM重復(fù)這一過程，最終輸入到BP 神經(jīng)網(wǎng)絡(luò)中。

GA-DBN 模型的訓(xùn)練流程如圖5 所示。訓(xùn)練關(guān)鍵步驟如下：

圖5 GA-DBN 模型訓(xùn)練流程Fig.5 GA-DBN model training proces

（1）數(shù)據(jù)預(yù)處理，劃分?jǐn)?shù)據(jù)集并輸入訓(xùn)練集和測試集；

（2）各層RBM 模型中連接可見單元和隱藏單元之間的權(quán)重作為遺傳算法種群，對各個(gè)權(quán)值進(jìn)行實(shí)數(shù)編碼；

（3）構(gòu)造適應(yīng)度函數(shù)。本文以重構(gòu)誤差作為適應(yīng)度函數(shù)，重構(gòu)誤差即經(jīng)吉布斯采樣重構(gòu)后的數(shù)據(jù)與原始數(shù)據(jù)之間的平方差，如式（2）：

（4）根據(jù)適應(yīng)度值選擇出優(yōu)良個(gè)體遺傳到子代，如式（3）：

（5）兩個(gè)個(gè)體交叉匹配后產(chǎn)生新個(gè)體并遺傳給子代，如式（4）：

計(jì)量資料數(shù)據(jù)分析結(jié)果以（±s）表示，兩組間均數(shù)比較采用檢驗(yàn)和秩和檢驗(yàn)，計(jì)數(shù)資料采用檢驗(yàn)，以P＜0.05為差異有統(tǒng)計(jì)學(xué)意義。所有數(shù)據(jù)均采用SPSS23.0軟件進(jìn)行統(tǒng)計(jì)學(xué)處理。

（6）個(gè)體部分基因變異成為新個(gè)體，如式（5）：

其中，gij表示個(gè)體的基因，基因的上界為gmax，下界為gmin，r1、r2為隨機(jī)數(shù)，當(dāng)前遺傳算法進(jìn)化次數(shù)為s，最大為smax。

（7）計(jì)算適應(yīng)度函數(shù)，滿足算法結(jié)束條件則更新RBM 模型的權(quán)重和偏置量，反之執(zhí)行（3）；

（8）對DBN 模型中的RBM 模型逐層訓(xùn)練。

遺傳算法結(jié)束條件為：算法到達(dá)最大進(jìn)化次數(shù)或算法得到的重構(gòu)誤差逼近程度在某個(gè)范圍內(nèi)，且遺傳算法多次進(jìn)化后發(fā)現(xiàn)優(yōu)化結(jié)果幾乎不變。

在預(yù)訓(xùn)練階段完成后，RBM 達(dá)到了局部最優(yōu)。為了實(shí)現(xiàn)整體最優(yōu)，RBM 模型訓(xùn)練好后正向輸入到BP 神經(jīng)網(wǎng)絡(luò)進(jìn)行反向計(jì)算，BP 神經(jīng)網(wǎng)絡(luò)自上而下對整個(gè)DBN 模型參數(shù)進(jìn)行微調(diào)，并且結(jié)合預(yù)訓(xùn)練得到的權(quán)重和DBN 參數(shù)，soft-max 模型對訓(xùn)練數(shù)據(jù)進(jìn)行分類。

2 模型評估方法

本文選用Acc（Accuracy，Acc）、F1度量、受試者工作特征曲線（Receiver Operating Characteristic Curve，ROC）對分類模型性能進(jìn)行綜合評價(jià)。

Acc為準(zhǔn)確率指標(biāo)，表示在分類中模型對測試集進(jìn)行分類，分類正確的個(gè)數(shù)占測試集總個(gè)數(shù)的比例，如式（6）：

F1度量的一般形式是Fβ，是查準(zhǔn)率（precision）和查全率（recall）的加權(quán)調(diào)和平均數(shù)，查準(zhǔn)率代表分類器分類正確的正類數(shù)據(jù)占分類器中分類為正的全部數(shù)據(jù)的比例，查全率表示分類器分類正確的正類數(shù)據(jù)占整個(gè)數(shù)據(jù)集正類數(shù)據(jù)的比例，如式（7）～式（9）：

其中，TP表示預(yù)測值和真實(shí)值均為正類；FN表示預(yù)測值為負(fù)類，真實(shí)值為正類；FP表示預(yù)測值為正類，真實(shí)值為負(fù)類；TN表示預(yù)測值和真實(shí)值均為負(fù)類；β表示對精準(zhǔn)率與召回率賦予的權(quán)重，本文中β取值為1。

受試者工作特征曲線（Receiver Operating Characteristic Curve，ROC）是評價(jià)模型的常用圖示方法，ROC曲線示意圖如圖6 所示，橫坐標(biāo)為FPR，縱坐標(biāo)為TPR，（Area Under Curve，AUC）為ROC曲線下的面積，其值越大代表分類器的性能越好。

圖6 ROC 曲線示意圖Fig.6 ROC curve diagram

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

3.1 數(shù)據(jù)集選取與描述

UCI 數(shù)據(jù)庫是由美國加州大學(xué)Owen 分校提供的開放數(shù)據(jù)庫，其中包含了許多可供機(jī)器學(xué)習(xí)使用的標(biāo)準(zhǔn)數(shù)據(jù)集，可用于驗(yàn)證本文分類模型的性能。本文實(shí)驗(yàn)選取UCI 數(shù)據(jù)庫中樣本數(shù)不一、屬性不一的7 組數(shù)據(jù)用于分類器性能對比。

選取的7 組數(shù)據(jù)集的名稱、樣本數(shù)、屬性數(shù)等信息，見表1。

表1 實(shí)驗(yàn)數(shù)據(jù)集Tab.1 Experimental data sets

3.2 不同分類算法實(shí)驗(yàn)結(jié)果與分析

按照4：1 的比例對Breast Cancer、Wholesale customers、Transfusion、Shill Bidding、Mushroom、Bank Marketing、Adult 數(shù)據(jù)集進(jìn)行劃分，并選取隨機(jī)森林（Random Forests，RF）、人工神經(jīng)網(wǎng)絡(luò)（Artificial Neural Network，ANN）、支持向量機(jī)（Support Vector Machine，SVM ）和 XGBoost（eXtreme Gradient Boosting）分類模型這4 個(gè)分類器在訓(xùn)練集上對數(shù)據(jù)進(jìn)行訓(xùn)練，并與本文所提出的GA-DBN 分類模型進(jìn)行比較。

本實(shí)驗(yàn)中，DBN 模型中的RBM 層數(shù)均為3 層，迭代次數(shù)為100 為止，其中學(xué)習(xí)速率為0.10，動(dòng)量學(xué)習(xí)率為0.5，迭代過程中模型的重構(gòu)誤差逐漸降低，當(dāng)趨于某個(gè)固定值時(shí)，動(dòng)量學(xué)習(xí)率變?yōu)?.9。依據(jù)不同數(shù)據(jù)集劃分的DBN 結(jié)構(gòu)見表2。

表2 DBM 結(jié)構(gòu)Tab.2 DBM structure

GA-DBN 模型將重構(gòu)誤差作為適應(yīng)度函數(shù)，通過GA 算法找到誤差最小時(shí)對應(yīng)的參數(shù)，最終可以得到權(quán)重的學(xué)習(xí)速率以及可見層和隱藏層的偏置量學(xué)習(xí)速率。本文實(shí)驗(yàn)針對不同數(shù)據(jù)集建立了相對應(yīng)的DBN 模型，對DBN 模型中的每層RBM 模型進(jìn)行GA 算法優(yōu)化迭代可得到該層的重構(gòu)誤差，多次迭代后每層RBM 的重構(gòu)誤差都在0.03 左右，數(shù)據(jù)集7中的底層RBM 重構(gòu)誤差的實(shí)驗(yàn)結(jié)果如圖7 所示。

圖7 重構(gòu)誤差Fig.7 Reconstruction errors

各個(gè)數(shù)據(jù)集被正確分類樣本數(shù)的實(shí)驗(yàn)結(jié)果如圖8 所示，表明基于GA-DBN 分類模型對多分類問題表現(xiàn)出較好的分類效果，正確分類的樣本數(shù)最高。不同分類器的實(shí)驗(yàn)結(jié)果見表3，與其他分類模型相比，GA-DBN 模型在分類效果上有不同程度的提升，誤判率較低。與人工神經(jīng)網(wǎng)絡(luò)（ANN）模型相比，GA-DBN 模型準(zhǔn)確率提升了2.33%～14.91%，F(xiàn)1度量提升2.75%～145.92%；與SVM 模型相比，GA-DBN 模型準(zhǔn)確率提升了1.23%～4.93%，F(xiàn)1度量提升0.14%～44.99%；與XGBoost 模型相比，GADBN 模型準(zhǔn)確率提升了0.14%～4.03%，F(xiàn)1度量提升0.77%～8.69%。

圖8 正確分類樣本數(shù)Fig.8 Number of correctly classified samples

表3 不同分類器的實(shí)驗(yàn)結(jié)果Tab.3 Experimental results of different classifiers

根據(jù)表3，在數(shù)據(jù)集1 上，GA-DBN 的準(zhǔn)確率略低于隨機(jī)森林，但GA-DBN 模型在運(yùn)行時(shí)間上更短，效率明顯提升；在數(shù)據(jù)集2 上，GA-DBN 在準(zhǔn)確率和運(yùn)行時(shí)間上不及隨機(jī)森林，但F1值高于隨機(jī)森林；在數(shù)據(jù)集5 上，GA-DBN 模型表現(xiàn)一般，結(jié)合數(shù)據(jù)集中數(shù)據(jù)的分布特點(diǎn)發(fā)現(xiàn)該數(shù)據(jù)集為不平衡數(shù)據(jù)集，因而分類效果較差；在數(shù)據(jù)集7 上，GA-DBN 模型的F1 值略低于XGBoost，但準(zhǔn)確率高于XGBoost；在其余數(shù)據(jù)集上，GA-DBN 模型的準(zhǔn)確率Acc與F1值均較為理想。同分類器在7 個(gè)數(shù)據(jù)集上的ROC曲線如圖9 所示。

圖9 ROC 圖Fig.9 ROC diagram

3.3 不同優(yōu)化算法實(shí)驗(yàn)結(jié)果與分析

采用人工蜂群算法（Artificial Bee Colony，ABC）對DBN 模型中的權(quán)重尋優(yōu)，以驗(yàn)證遺傳算法對DBN模型的優(yōu)化效果。在實(shí)驗(yàn)中，ABC 算法的各種參數(shù)設(shè)定與GA-DBN 模型一致，選取準(zhǔn)確率、F1度量和運(yùn)行時(shí)間對ABC-DBN 模型和GA-DBN 模型進(jìn)行評價(jià)，實(shí)驗(yàn)結(jié)果見表4。

表4 不同優(yōu)化算法的實(shí)驗(yàn)結(jié)果Tab.4 Experimental results of different optimization algorithms

通過表4 實(shí)驗(yàn)結(jié)果可知，與ABC-DBN 模型相比，GA-DBN 模型在準(zhǔn)確率和F1度量上表現(xiàn)良好，但ABC-DBN 模型運(yùn)行時(shí)間較短；在數(shù)據(jù)集1、2、3上，ABC-DBN 模型與GA-DBN 模型的表現(xiàn)相差無幾，但是隨著數(shù)據(jù)量增大，樣本特征變多，遺傳算法的優(yōu)化效果更加突出，ABC-DBN 模型與GA-DBN模型的差距拉大，遺傳算法中的交叉和變異操作有助于尋找DBN 模型實(shí)現(xiàn)全局最優(yōu)。

4 結(jié)束語

在訓(xùn)練過程中，DBN 模型參數(shù)具有不穩(wěn)定性，從而影響模型性能。本文選用遺傳算法（GA）對DBN 模型的權(quán)重參數(shù)進(jìn)行尋優(yōu)，構(gòu)建了GA-DBN 模型；從UCI 數(shù)據(jù)庫選取了7 個(gè)樣本數(shù)和屬性不同的二分類數(shù)據(jù)集作為實(shí)驗(yàn)數(shù)據(jù)，驗(yàn)證GA-DBM 模型的分類效果；同時(shí)選擇隨機(jī)森林、人工神經(jīng)網(wǎng)絡(luò)、支持向量機(jī)和XGBoost 4 個(gè)常用的分類模型作為對比模型，實(shí)驗(yàn)結(jié)果表明GA-DBN 模型在不同數(shù)據(jù)集上的表現(xiàn)至少有一個(gè)指標(biāo)是最優(yōu)的，整體來講其在準(zhǔn)確率Acc、F1值及運(yùn)行效率上均較為理想。為了驗(yàn)證GA-DBN 模型的優(yōu)化效果，選擇人工蜂群算法（ABC）優(yōu)化后的DBN 模型即ABC-DBN 模型與GA-DBN模型進(jìn)行對比實(shí)驗(yàn)，結(jié)果表明遺傳算法對DBN 模型的優(yōu)化更穩(wěn)定。