[發(fā)明專利]一種針對(duì)分類問題的進(jìn)化集成學(xué)習(xí)方法

在審

• 申請(qǐng)?zhí)枺?/td>: 202110038912.8
• 申請(qǐng)日: 2021-01-12
• 公開（公告）號(hào): CN112734051A
• 公開（公告）日: 2021-04-30
• 發(fā)明（設(shè)計(jì)）人: 陳皓;張國鑫;賈蓉
• 申請(qǐng)（專利權(quán)）人: 西安郵電大學(xué)
• 主分類號(hào): G06N20/20
• 分類號(hào): G06N20/20;G06N3/12;G06N3/00
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種針對(duì)分類問題的雙進(jìn)化架構(gòu)自動(dòng)集成學(xué)習(xí)方法，所述方法包括以下步驟：

步驟1：初始化基學(xué)習(xí)器個(gè)體種群，可表示為N_t是基學(xué)習(xí)器個(gè)體數(shù)量，分類樹初始最小深度為D_min，最大深度為D_max，節(jié)點(diǎn)生成概率為P_node；每個(gè)節(jié)點(diǎn)Node由一個(gè)四元組表示，每個(gè)組件都是一個(gè)數(shù)值，可以在進(jìn)化過程中進(jìn)行修改，四元組中第一個(gè)元素是分裂屬性的整數(shù)索引；第二個(gè)是實(shí)數(shù)，表示閾值的分割值；第三個(gè)是整數(shù)，1表示該節(jié)點(diǎn)是終端節(jié)點(diǎn)，0表示該節(jié)點(diǎn)是非終端節(jié)點(diǎn)；第四個(gè)是預(yù)測(cè)的分類標(biāo)簽值，具體為：

步驟1.1：生成根節(jié)點(diǎn)，從訓(xùn)練樣本中隨機(jī)選擇一個(gè)特征并隨機(jī)選擇該特征的分割閾值作為當(dāng)前節(jié)點(diǎn)的內(nèi)部屬性；

步驟1.2：遞歸的生成樹結(jié)構(gòu)，當(dāng)樹的深度大于D_min且小于D_max時(shí)，則生成隨機(jī)數(shù)Rand與P_node比較，若小于P_node則生成中間節(jié)點(diǎn)，從訓(xùn)練樣本中隨機(jī)選擇一個(gè)特征并隨機(jī)選擇該特征的分割閾值作為節(jié)點(diǎn)的內(nèi)部屬性；若大于P_node則生成葉子節(jié)點(diǎn)，隨機(jī)選擇分類標(biāo)簽作為節(jié)點(diǎn)的內(nèi)部屬性；當(dāng)樹的深度等于D_max時(shí)，執(zhí)行步驟1.3；

步驟1.3：當(dāng)樹的深度等于D_max時(shí)，則生成葉子節(jié)點(diǎn)，隨機(jī)選擇分類標(biāo)簽作為該節(jié)點(diǎn)的內(nèi)部屬性，然后轉(zhuǎn)至步驟2；

步驟2：基學(xué)習(xí)器個(gè)體的搜索過程，在雙進(jìn)化搜索過程中我們依靠針對(duì)樹形編碼設(shè)計(jì)的交叉和變異機(jī)制來產(chǎn)生基學(xué)習(xí)器子代個(gè)體，節(jié)點(diǎn)交叉概率為P_cross，節(jié)點(diǎn)變異概率為P_muate，具體為：

步驟2.1：交叉操作，首先從決策樹群體T中隨機(jī)選擇兩個(gè)個(gè)體t_i和t_j，并分別從根節(jié)點(diǎn)開始向下遍歷，每遍歷一個(gè)節(jié)點(diǎn)生成隨機(jī)數(shù)Rand與P_cross比較，若小于P_cross則當(dāng)前節(jié)點(diǎn)為一個(gè)交叉點(diǎn)，否則繼續(xù)遍歷；當(dāng)兩個(gè)個(gè)體都確定交叉點(diǎn)后，如果兩個(gè)交叉點(diǎn)都是終端節(jié)點(diǎn)則交換交叉點(diǎn)的分類標(biāo)簽，否則將兩個(gè)叉點(diǎn)的子樹進(jìn)行交換；

步驟2.2：變異操作，變異將對(duì)分類樹進(jìn)行局部調(diào)整，具體方式包括：改變節(jié)點(diǎn)上的數(shù)值，以及改變節(jié)點(diǎn)的分支結(jié)構(gòu)；首先對(duì)交叉后生成的子代群體中每個(gè)個(gè)體t_i，從樹的根節(jié)點(diǎn)開始遍歷，每經(jīng)過一個(gè)節(jié)點(diǎn)生成隨機(jī)數(shù)Rand與P_muate比較，若小于P_muate則當(dāng)前節(jié)點(diǎn)為選擇的變異節(jié)點(diǎn)，結(jié)束遍歷，然后按相等的概率隨機(jī)選擇上述的方式對(duì)節(jié)點(diǎn)進(jìn)行變異；

步驟3：集成學(xué)習(xí)器個(gè)體的搜索過程，一個(gè)集成器個(gè)體e可用一個(gè)二進(jìn)制串表示，若e(i)＝1表示決策樹t_i被選中，若e(i)＝0則表示決策樹t_i沒有被選中，故e可表達(dá)決策樹群體的一個(gè)子集，集成器的搜索將基于二進(jìn)制遺傳算法來實(shí)現(xiàn)對(duì)當(dāng)前基學(xué)習(xí)器父代群體中個(gè)體的組合優(yōu)化，具體為：

步驟3.1：交叉操作：參與交叉的父輩個(gè)數(shù)k從2到群體規(guī)模N之間隨機(jī)確定，公式如下：

其中，i＝{1，2，...，N}為個(gè)體的基因編碼位數(shù)，j＝{1，2，...，k}為父輩個(gè)體數(shù)，e_j(i)為第j個(gè)父輩個(gè)體的的第i位基因編碼，e′(i)為交叉操作產(chǎn)生的子代個(gè)體的第i位基因編碼，sign(·)為符號(hào)函數(shù)對(duì)當(dāng)前累加和大于0時(shí)取1，小于或等于0時(shí)取0，W_j為第j個(gè)父輩準(zhǔn)確度值在所有父代個(gè)體準(zhǔn)確度值總和中所占的比重；

步驟3.2：變異操作，對(duì)集成交叉產(chǎn)生的所有個(gè)體e_i，以1/N的概率隨機(jī)翻轉(zhuǎn)的每一位基因，生成變異個(gè)體，N為每個(gè)個(gè)體的基因長度；

步驟4：評(píng)估機(jī)制；

步驟4.1：基學(xué)習(xí)器個(gè)體的評(píng)估，分類樹的多樣性是衡量樹群中子樹之間的差異性，公式如下：

其中f_DF(t_i)表示決策樹t_i在種群中的相似度，DF(t_i，t_j)是t_i和t_j兩個(gè)個(gè)體對(duì)相同樣本都預(yù)測(cè)錯(cuò)誤的數(shù)量，Spl是樣本總數(shù)，當(dāng)f_DF(t_i)＝1時(shí)表示多樣程度最低，f_DF(t_i)目的是減少種群中個(gè)體之間常見錯(cuò)誤的重疊，以使不同個(gè)體的輸出彼此不相關(guān)；因?yàn)榉诸悩涫嵌鏄洌乙呀?jīng)限制了樹的橫向生長，故通過對(duì)最大深度的限制可以降低決策樹的復(fù)雜度，因此決策樹復(fù)雜度可定義如下：

f_depth(t_i)＝max_depth(t_i) (5)

其中max_depth(t_i)是個(gè)體t_i的最大深度；分類樹與其他個(gè)體的協(xié)作程度也就是對(duì)集成器的貢獻(xiàn)程度，這個(gè)指標(biāo)衡量了分類樹參與集成后的平均表現(xiàn)，公式如下：

其中f_coop(t_i)表示t_i與群體中其它個(gè)體的協(xié)作程度，hum是在集成進(jìn)化過程中t_i被選中的次數(shù)；f_acc(t_i∈E)表示集成模型E包含決策樹t_i時(shí)的準(zhǔn)確率，表示集成模型E去除決策樹t_i時(shí)的準(zhǔn)確率，兩個(gè)的差值作為t_i對(duì)集成模型E的貢獻(xiàn)，f_coop(t_i)越小代表t_i與其它成員的協(xié)作程度越好，如果t_i沒有參與任何集成無法評(píng)估其表現(xiàn)，在這種情況下f_coop(t_i)默認(rèn)為0.5；分類樹的準(zhǔn)確度是分類樹對(duì)樣本預(yù)測(cè)正確所占的比例，公式如下：

其中f_acc(t_i)是分類樹t_i的準(zhǔn)確率，Acc(t_i)是對(duì)樣本正確分類的數(shù)量；綜合上述考量，分類樹個(gè)體需要計(jì)算4個(gè)指標(biāo)：

F_t(t_i)＝(f_DF(t_i)，f_depth(t_i)，f_coop(t_i)，f_acc(t_i)) (8)

步驟4.2：集成器個(gè)體評(píng)估，集成器群體優(yōu)化的目標(biāo)是尋找最佳的分類樹組合，適應(yīng)度函數(shù)以準(zhǔn)確率和最小集成規(guī)模為目標(biāo)：

其中，f_acc(e_i)是集成器e_i的分類準(zhǔn)率，len(e_i)是集成器e_i包含的基學(xué)習(xí)器個(gè)數(shù)；

步驟5：群體迭代機(jī)制；

步驟5.1：基學(xué)習(xí)器群體進(jìn)行多目標(biāo)選擇，父代個(gè)體和搜索產(chǎn)生的子代個(gè)體將組成大小為2N的群體，通過多目標(biāo)選擇產(chǎn)生規(guī)模為N的下代群體，具體操作如下：

步驟5.1.1：首先根據(jù)4個(gè)目標(biāo)函數(shù)計(jì)算群體中所有個(gè)體的優(yōu)勢(shì)等級(jí)(即支配關(guān)系)，然后根據(jù)優(yōu)勢(shì)等級(jí)進(jìn)行分層；

步驟5.1.2：針對(duì)同一層的個(gè)體，其他的多目標(biāo)優(yōu)化算法根據(jù)不同的密度估計(jì)方法進(jìn)行排序，目的是維護(hù)群體的多樣性，由于在適應(yīng)度評(píng)估中已經(jīng)計(jì)算了基學(xué)習(xí)器之間的多樣性，這與其他密度估計(jì)方法類似，所以同一層個(gè)體根據(jù)它們的多樣性進(jìn)行排序；

步驟5.1.3：從優(yōu)勢(shì)等級(jí)為0的層開始向后續(xù)層次截?cái)嗲癗個(gè)個(gè)體作為下代群體，為了與集成學(xué)習(xí)器的編碼對(duì)應(yīng)，截?cái)嗪蟮腘個(gè)下代群體中，來自父代的個(gè)體放入原始的編碼位置，來自子代的個(gè)體放入空置的編碼位置；此過程中由于被選擇的子代個(gè)體比被淘汰的父代個(gè)體更優(yōu)秀，所以替換后并不會(huì)降低集成學(xué)習(xí)器的性能；

步驟5.2：集成學(xué)習(xí)器群體選擇操作，父代個(gè)體和子代個(gè)體組成大小為2N的群體，然后依據(jù)集成器個(gè)體的準(zhǔn)確度挑選產(chǎn)生規(guī)模為N的下代群體，具體操作如下：

步驟5.2.1：為了保持集成學(xué)習(xí)器之間的多樣性，將每個(gè)集成器對(duì)驗(yàn)證集的預(yù)測(cè)標(biāo)簽作為集成器的特征，然后通過AP聚類算法對(duì)集成器進(jìn)行聚類，因?yàn)锳P聚類不需要指定最終的聚類族個(gè)數(shù)，并且對(duì)數(shù)據(jù)的初始值不敏感，不需要進(jìn)行隨機(jī)選取初值步驟；

步驟5.2.2：聚類后的每個(gè)簇內(nèi)都是相似度較高的集成學(xué)習(xí)器集合，故首先在每個(gè)簇中按集成學(xué)習(xí)器的準(zhǔn)確度進(jìn)行排名，然后依次從每個(gè)簇中選擇前半部分集成器個(gè)體加入下代群體，最終獲得個(gè)體數(shù)量為N的下代群體；

步驟6：判斷當(dāng)前迭代次數(shù)是否滿足最大迭代次數(shù)，若不滿足則轉(zhuǎn)至步驟2，否則將當(dāng)前基學(xué)習(xí)器群體和最優(yōu)集成器組合作為集成模型，輸出分類結(jié)果。