同分布強(qiáng)化學(xué)習(xí)優(yōu)化多決策樹及其在非平衡數(shù)據(jù)集中的應(yīng)用

焦江麗，張雪英，李鳳蓮，牛壯

?

同分布強(qiáng)化學(xué)習(xí)優(yōu)化多決策樹及其在非平衡數(shù)據(jù)集中的應(yīng)用

焦江麗，張雪英，李鳳蓮，牛壯

(太原理工大學(xué) 信息與計(jì)算機(jī)學(xué)院，山西 太原，030024)

針對(duì)傳統(tǒng)決策樹在非平衡數(shù)據(jù)集分類時(shí)少數(shù)類預(yù)測性能出現(xiàn)偏差的問題，提出一種基于強(qiáng)化學(xué)習(xí)累積回報(bào)的屬性優(yōu)化策略即改進(jìn)型同分布多決策樹方法。首先通過同分布隨機(jī)抽樣法對(duì)非平衡數(shù)據(jù)集中的多數(shù)類樣本進(jìn)行隨機(jī)采樣，進(jìn)而對(duì)各子集建立單決策樹形成多個(gè)決策樹，各決策樹采用分類回歸樹算法建樹，并利用強(qiáng)化學(xué)習(xí)累積回報(bào)機(jī)制進(jìn)行屬性選擇策略的優(yōu)化。研究結(jié)果表明：提出的基于強(qiáng)化學(xué)習(xí)累積回報(bào)機(jī)制的屬性優(yōu)化策略可有效提高少數(shù)類被正確分類的概率；同分布多決策樹方法可有效提高非平衡數(shù)據(jù)集整體預(yù)測性能，且正類率和負(fù)類率的幾何平均值都有所提高。

非平衡數(shù)據(jù)集；多決策樹；累積回報(bào)機(jī)制屬性選擇策略；同分布隨機(jī)抽樣；強(qiáng)化學(xué)習(xí)

分類是數(shù)據(jù)挖掘領(lǐng)域的研究熱點(diǎn)之一，目前成熟的算法主要包括樸素貝葉斯、神經(jīng)網(wǎng)絡(luò)和決策樹[1]等。其中，隨機(jī)森林算法因其具有簡單易行、運(yùn)算速度快和準(zhǔn)確度高的特點(diǎn)而在交通、醫(yī)學(xué)、生物學(xué)等眾多領(lǐng)域得到了廣泛應(yīng)用[2?3]。然而，隨著大數(shù)據(jù)時(shí)代的到來，數(shù)據(jù)的非平衡特性也更加突出。決策樹分類算法基本思想是通過一個(gè)樹形結(jié)構(gòu)模型，將數(shù)據(jù)集在不同分裂節(jié)點(diǎn)根據(jù)不同屬性劃分為各類別，其模型構(gòu)建的核心是對(duì)分類節(jié)點(diǎn)的分裂屬性進(jìn)行最佳選擇。其中比較經(jīng)典的算法有ID3，C4.5和分類回歸樹(CART)算法 等[4?5]，這些算法的本質(zhì)區(qū)別是節(jié)點(diǎn)分裂屬性選擇策略不同；而隨機(jī)森林方法是一種將多個(gè)單決策樹分類器集成的多決策樹學(xué)習(xí)方法[6]，在一定程度上可以解決單決策樹過擬合導(dǎo)致的分類準(zhǔn)確性不高的問題。上述單決策樹方法及隨機(jī)森林方法用于平衡數(shù)據(jù)集，一般可得到較好的分類效果，但對(duì)非平衡數(shù)據(jù)集，這些方法則存在少數(shù)類預(yù)測準(zhǔn)確度偏低的缺陷。為此，人們提出多種改進(jìn)算法。ALSHOMRANI等[7]利用特征加權(quán)法優(yōu)化屬性選擇策略以改善非平衡數(shù)據(jù)集分類性能。在對(duì)非平衡數(shù)據(jù)集進(jìn)行分類時(shí)，由于各類別的樣本數(shù)目分布不均勻，少數(shù)類樣本通常得不到充分訓(xùn)練，從而使分類器容易傾向于多數(shù)類而忽略少數(shù)類樣本，但在現(xiàn)實(shí)生活中少數(shù)類樣本通常具有更重要的作 用[8?9]，因此，如何提高少數(shù)類預(yù)測準(zhǔn)確度具有重要意義。目前，國內(nèi)外研究者針對(duì)非平衡數(shù)據(jù)集如何提高分類器性能開展了大量工作：LI等[10]提出了基于屬性混合策略的代價(jià)敏感Top-N多決策樹算法，并將其用于非平衡數(shù)據(jù)集分類預(yù)測；KOZIARSKI等[11]提出了一種用于改變非平衡數(shù)據(jù)集數(shù)據(jù)不平衡率的預(yù)處理方法；付忠良[12]提出了一種多標(biāo)簽代價(jià)敏感分類集成學(xué)習(xí)算法。但針對(duì)非平衡數(shù)據(jù)分類問題，雖然引入代價(jià)敏感因子和采用抽樣的方法可提高分類的性能，但在實(shí)施中往往難以確定代價(jià)，且抽樣的方法容易造成樣本信息丟失或者過擬合等問題。強(qiáng)化學(xué)習(xí)方法是從自適應(yīng)控制理論中發(fā)展出來的一種機(jī)器學(xué)習(xí)方法，其通過判斷當(dāng)前學(xué)習(xí)環(huán)境對(duì)分類器的影響，綜合分析各種影響所造成的結(jié)果可對(duì)學(xué)習(xí)方法進(jìn)行調(diào)整，從而使最終的分類預(yù)測偏向更加準(zhǔn)確的結(jié)果[13?14]。周浦城等[15]將Q-Learning強(qiáng)化學(xué)習(xí)算法與決策樹模型相結(jié)合，根據(jù)決策樹當(dāng)前節(jié)點(diǎn)輸入的數(shù)據(jù)不斷更新Q?表生成新的決策節(jié)點(diǎn)。人們對(duì)利用強(qiáng)化學(xué)習(xí)方法進(jìn)行屬性選擇策略優(yōu)化的研究較少，而屬性選擇直接影響決策樹性能，為此，本文作者首先基于強(qiáng)化學(xué)習(xí)累積回報(bào)機(jī)制提出一種屬性選擇優(yōu)化策略，進(jìn)而將該策略與集成學(xué)習(xí)算法結(jié)合，提出一種基于同分布隨機(jī)抽樣的多決策樹集成學(xué)習(xí)算法。

1 基于強(qiáng)化學(xué)習(xí)累積回報(bào)機(jī)制的優(yōu)化策略

強(qiáng)化學(xué)習(xí)是研究一個(gè)能夠感知環(huán)境的智能體，在沒有先驗(yàn)知識(shí)的情況下，從延遲回報(bào)中學(xué)習(xí)優(yōu)化的控制策略，進(jìn)而使智能體的累積回報(bào)最大[16]。傳統(tǒng)決策樹采用特征選擇策略建樹以實(shí)現(xiàn)分類，其中CART算法采用基尼(Gini)指數(shù)作為特征選擇策略，對(duì)非平衡數(shù)據(jù)集分類時(shí)會(huì)使多數(shù)類數(shù)據(jù)分類性能更優(yōu)[17]。由于強(qiáng)化學(xué)習(xí)會(huì)根據(jù)智能體做出動(dòng)作后的執(zhí)行結(jié)果進(jìn)行獎(jiǎng)勵(lì)或者懲罰，并通過延遲回報(bào)獲得各個(gè)狀態(tài)下的最優(yōu)動(dòng)作。若能借鑒這種獎(jiǎng)懲策略，使少數(shù)類分類正確時(shí)獲得更大的獎(jiǎng)勵(lì)，并將這種策略融合于決策樹屬性選擇階段，則有利于提高決策樹中少數(shù)類分類性能。借鑒這種優(yōu)化思路，本文作者提出基于累積回報(bào)機(jī)制的屬性選擇優(yōu)化策略，通過決策樹每一層的回報(bào)系數(shù)計(jì)算決策樹屬性選擇的累積回報(bào)值以使決策樹屬性選擇策略得到優(yōu)化。

1.1 累積回報(bào)求解

依據(jù)強(qiáng)化學(xué)習(xí)的累積回報(bào)思想，結(jié)合CART算法，通過每一層的回報(bào)系數(shù)優(yōu)化決策樹的屬性選擇策略，本文將第1~層的層累積回報(bào)系數(shù)相乘定義為累積回報(bào)，其具體表達(dá)式如下：

=1?2…R(1)

式中：R為該節(jié)點(diǎn)在決策樹的第層的累積回報(bào)系數(shù)，R越大，說明分類性能越優(yōu)?？紤]預(yù)測效果的幾何平均值系數(shù)、真實(shí)正類率以及模型的準(zhǔn)確率，本文將R定義為

R=+i?A?mi(2)

式中：P為分類模型第層的真實(shí)正類率即正確預(yù)測的正類與實(shí)際為正類的樣本數(shù)量的比值，+i越大，說明正類預(yù)測越準(zhǔn)確，性能越好；A為模型第層分類準(zhǔn)確率即正確預(yù)測的樣本數(shù)與總樣本數(shù)的比值，其值越大，說明總體預(yù)測越準(zhǔn)確，性能越好；mi為模型中第層幾何平均值系數(shù)即真實(shí)正類率與真實(shí)負(fù)類率乘積的開方，其值越大，說明總體預(yù)測性能越好。

式中：?i為分類模型中第層的真實(shí)負(fù)類率即正確預(yù)測的負(fù)類與實(shí)際為負(fù)類的樣本數(shù)量的比值，其值越大，說明負(fù)類預(yù)測越準(zhǔn)確，性能越好；TPi為所有樣本在當(dāng)前節(jié)點(diǎn)第層被正確的分為正類的數(shù)量；TNi為所有樣本在當(dāng)前節(jié)點(diǎn)第層正確分為負(fù)類的數(shù)量；FPi為第層錯(cuò)誤分為正類的樣本數(shù)量，F(xiàn)Ni為第層錯(cuò)誤分為負(fù)類的樣本數(shù)量。

1.2 基于累積回報(bào)機(jī)制的屬性選擇策略

傳統(tǒng)的屬性選擇策略在非平衡數(shù)據(jù)集預(yù)測中表現(xiàn)并不佳[18?19]，為此，本文作者結(jié)合上述強(qiáng)化學(xué)習(xí)累積回報(bào)機(jī)制的思想，提出基于強(qiáng)化學(xué)習(xí)的累積回報(bào)機(jī)制的屬性選擇策略(cumulative reward mechanism attributes selection strategy, CRS)，利用每個(gè)屬性被選擇后當(dāng)前節(jié)點(diǎn)的分類結(jié)果作為影響因子反饋到當(dāng)前節(jié)點(diǎn)屬性選擇的過程中，即在傳統(tǒng)屬性選擇方法的基礎(chǔ)上加入累積回報(bào)系數(shù)進(jìn)行當(dāng)前節(jié)點(diǎn)最佳分裂屬性選擇的優(yōu)化。屬性選擇策略AS定義為

式中：Gini為所有屬性的Gini系數(shù)。在傳統(tǒng)決策樹屬性選擇中，Gini系數(shù)越小，最終分類效果越好，而累積回報(bào)系數(shù)R越大，說明對(duì)屬性選擇的優(yōu)化效果越好，因此，選擇AS最小值對(duì)應(yīng)的屬性作為當(dāng)前節(jié)點(diǎn)分裂的屬性最好。

1.3 基于累積回報(bào)機(jī)制的決策樹模型構(gòu)建

本文采用自上向下遞歸二分技術(shù)，利用強(qiáng)化學(xué)習(xí)累積回報(bào)機(jī)制得到各節(jié)點(diǎn)的最佳分裂屬性?；诶鄯e回報(bào)機(jī)制的決策樹(cumulative reward mechanism attributes selection strategy decision tree, CRDT)原理圖如圖1所示。

圖1中CART決策樹根節(jié)點(diǎn)采用傳統(tǒng)的屬性選擇策略構(gòu)建，各子節(jié)點(diǎn)的構(gòu)建采用本文提出的累積回報(bào)機(jī)制，即根據(jù)式(4)計(jì)算各子節(jié)點(diǎn)的AS，最小AS對(duì)應(yīng)的屬性為子節(jié)點(diǎn)最佳屬性，直至達(dá)到葉節(jié)點(diǎn)。

圖1 CRDT原理圖

2 同分布隨機(jī)抽樣的CRS多決策樹集成學(xué)習(xí)算法

在數(shù)據(jù)集不平衡的情況下，少數(shù)類被抽取的概率很小，而經(jīng)典隨機(jī)森林中單決策樹的訓(xùn)練樣本是隨機(jī)抽取的，因此，少數(shù)類在最后決策樹形成過程中不會(huì)被充分訓(xùn)練[20]。已有方法是將非平衡數(shù)據(jù)集中的多數(shù)類樣本隨機(jī)分為個(gè)子集，然后，分別將這些子集中的樣本與少數(shù)類樣本合成新的訓(xùn)練樣本子集，通過個(gè)決策樹對(duì)各個(gè)新的樣本子集分別進(jìn)行訓(xùn)練，最后采用投票法將這些決策樹結(jié)果集成。但此種方法使個(gè)數(shù)據(jù)集之間的多數(shù)類樣本完全不同，雖然少數(shù)類樣本得到了充分訓(xùn)練，但多數(shù)類樣本訓(xùn)練不足，因此，這種方法的分類效果并不理想。

為此，本文作者提出一種同分布隨機(jī)抽樣的CRS多決策樹集成學(xué)習(xí)(identically distributed random sampling cumulative reward attributes selection strategy multi-decision tree, IDCRMDT)算法。該方法首先對(duì)輸入數(shù)據(jù)集采用同分布隨機(jī)抽樣法進(jìn)行預(yù)處理，得到個(gè)樣本子集，以使非平衡數(shù)據(jù)集中的多數(shù)類樣本均勻分布至各子集，進(jìn)而使用本文提出的累積回報(bào)屬性選擇策略建立各個(gè)單決策樹。IDCRMDT算法原理圖如圖2所示。

圖2中同分布隨機(jī)抽樣法使用-means聚類算法對(duì)輸入數(shù)據(jù)集中的多數(shù)類進(jìn)行聚類，得到各決策樹訓(xùn)練時(shí)使用的樣本子集，這樣既可以保證抽取的多數(shù)類樣本服從同分布，又可以使少數(shù)類樣本也被均勻抽樣，克服了非平衡數(shù)據(jù)集的非平衡率過大時(shí)少數(shù)類樣本得不到充分訓(xùn)練的弊端。

2.1 同分布隨機(jī)抽樣法

本文提出的IDCRMDT算法首先采用同分布隨機(jī)抽樣法對(duì)多數(shù)類樣本進(jìn)行聚類，形成(選取和少數(shù)類樣本一致的個(gè)數(shù))個(gè)樣本子集ma，以使分布相近的多數(shù)類樣本劃分為1個(gè)集合，然后將各個(gè)子集分別與少數(shù)類樣本進(jìn)行組合形成新的同分布樣本子集。同分布隨機(jī)抽樣法流程圖如圖3所示。

2.2 IDCRMDT算法

數(shù)據(jù)樣本集合分為多數(shù)類樣本集合ma和少數(shù)類樣本集合mi，記多數(shù)類樣本的數(shù)量為，少數(shù)類樣本的數(shù)量為。IDCRMDT算法流程如下。

輸入：數(shù)據(jù)集。

圖2 IDCRMDT算法原理圖

圖3 同分布隨機(jī)抽樣法流程圖

輸出：分類預(yù)測結(jié)果。

3) 使用投票法得到多決策樹分類預(yù)測結(jié)果。

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

本文設(shè)計(jì)實(shí)驗(yàn)分別驗(yàn)證基于強(qiáng)化學(xué)習(xí)累積回報(bào)的屬性選擇策略的優(yōu)勢以及提出的IDCRMDT算法性能優(yōu)劣。

3.1 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)數(shù)據(jù)集采用KEEL-Imbalanced Data Sets中的10個(gè)不同平衡率的非平衡數(shù)據(jù)集，各數(shù)據(jù)集詳情如表1所示。

3.2 實(shí)驗(yàn)設(shè)計(jì)

本文設(shè)計(jì)實(shí)驗(yàn)方案，并采用10折交叉驗(yàn)證的方法得到實(shí)驗(yàn)結(jié)果。

1) 方案1。

對(duì)比方法：CART(單決策樹)；

表1 實(shí)驗(yàn)數(shù)據(jù)集

本文方法：CRDT(基于累積回報(bào)機(jī)制的單決策樹)。

2) 方案2。

對(duì)比方法1：RF(傳統(tǒng)隨機(jī)森林算法)；

對(duì)比方法2：CRRF(基于單決策樹CRS屬性選擇策略的隨機(jī)森林，cumulative reward mechanism attributes selection strategy random forest)；

本文方法：IDCRMDT(同分布隨機(jī)抽樣的CRS多決策樹)。

3.3 評(píng)價(jià)指標(biāo)

本論文采用真實(shí)正類率+、準(zhǔn)確率和幾何平均值m評(píng)估算法的性能。其中，真實(shí)正類率P和準(zhǔn)確率越大，說明決策樹的分類效果更好，而幾何平均值m是真實(shí)正類率和真實(shí)負(fù)類率乘積的開方，對(duì)于非平衡數(shù)據(jù)集而言更能反映總體預(yù)測分類性能的 優(yōu)劣。

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

本文提出的方法CRDT與CART單決策樹性能對(duì)比見圖4。由圖4(a)可知：相較CART，采用本文提出的CRDT算法各數(shù)據(jù)集的真實(shí)正類率+均有所提高；對(duì)于數(shù)據(jù)集3，4，7，9和10，真實(shí)正類率分別提高16.7%，9.9%，22.0%，27.7%和60.2%。由圖4(b)可以看出：除數(shù)據(jù)集1外，采用CRDT各數(shù)據(jù)集的準(zhǔn)確率均有所提高。由圖4(c)可以看出：除了數(shù)據(jù)集1之外，采用CRDT時(shí)其余數(shù)據(jù)集幾何平均值m都有所提高。綜合來看，CRDT應(yīng)用于非平衡數(shù)據(jù)集整體性能比已有的CART算法的分類性能更優(yōu)。

將傳統(tǒng)的隨機(jī)森林算法(RF)與本文提出的IDCRMDT和CRRF的真實(shí)正類率、準(zhǔn)確率以及幾何平均值進(jìn)行對(duì)比，結(jié)果如圖5所示。從圖5(a)和圖5(b)可知：采用本文的IDCRMDT算法時(shí)，除數(shù)據(jù)集10的真實(shí)正類率下降較多外，其余數(shù)據(jù)集的真實(shí)正類率都比采用RF和CRRF時(shí)的真實(shí)正類率高，但準(zhǔn)確率提高幅度不是很明顯。由圖5(c)可知：采用本文的IDCRMDT算法時(shí)，數(shù)據(jù)集1，2，3，5和8的m與采用傳統(tǒng)隨機(jī)森林算法(RF)得到的m相比均有所提高，而較CRRF得到的m則分別提高3.9%，16.9%，6.3%，7.8%和32.2%。

圖4 CRDT與CART性能對(duì)比

圖5 IDCRMDT與CRRF和RF的性能對(duì)比

從實(shí)驗(yàn)方案1可以看出：利用強(qiáng)化學(xué)習(xí)累積回報(bào)機(jī)制思路改進(jìn)決策樹屬性選擇策略的性能都有所提高。隨機(jī)森林算法在很大程度上解決了單決策樹的過擬合問題，傳統(tǒng)的隨機(jī)森林在建樹過程中采用可放回隨機(jī)抽樣方法產(chǎn)生不同的數(shù)據(jù)集，但往往非平衡數(shù)據(jù)集的少數(shù)類被抽取的概率會(huì)很小。從實(shí)驗(yàn)方案2可以看出：采用同分布隨機(jī)抽樣的方法可使少數(shù)類得到充分訓(xùn)練，與傳統(tǒng)的RF以及改進(jìn)的屬性選擇策略的CRRF算法相比，本文提出的IDCRMDT算法的真實(shí)正類率和準(zhǔn)確率均有所提高，同時(shí)，模型整體性能有所提高。

4 結(jié)論

1) 本文提出一種同分布類隨機(jī)抽樣的CRS多決策樹集成學(xué)習(xí)(IDCRMDT)算法，利用累積回報(bào)機(jī)制進(jìn)行決策樹屬性選擇優(yōu)化，并對(duì)非平衡數(shù)據(jù)集中的多數(shù)類采用同分布隨機(jī)抽樣法進(jìn)行預(yù)處理，以使多數(shù)類樣本均勻分布于各子集并使少數(shù)類樣本得到充分訓(xùn)練。

2) 本文提出的方法對(duì)多數(shù)非平衡數(shù)據(jù)集的分類效果均有提升；而對(duì)于個(gè)別數(shù)據(jù)集，雖然少數(shù)類分類性能得到了提高，但數(shù)據(jù)集整體預(yù)測性能稍有下降。

[1] HAN Jiawei, KAMBER M, PEI Jian. Data mining: concepts and techniques[M]. 3rd ed. San Francisco, USA: Elsevier, 2011: 15?23.

[2] 楊宏宇, 徐晉. 基于改進(jìn)隨機(jī)森林算法的Android惡意軟件檢測[J]. 通信學(xué)報(bào), 2017, 38(4): 8?16. YANG Hongyu, XU Jin. Android malware detection based on improved random forest[J]. Journal on Communications, 2017, 38(4): 8?16.

[3] 杜春蕾, 張雪英, 李鳳蓮. 改進(jìn)的CART算法在煤層底板突水預(yù)測中的應(yīng)用[J]. 工礦自動(dòng)化, 2014, 40(12): 52?56. DU Chunlei, ZHANG Xueying, LI Fenglian. Application of improved CART algorithm in prediction of water inrush from coal seam floor[J]. Industry and Mine Automation, 2014, 40(12): 52?56.

[4] STROBL C. Fifty years of classification and regression trees discussion[J]. International Statistical Review, 2014, 82(3): 349?352.

[5] 姚亞夫, 邢留濤. 決策樹C4.5連續(xù)屬性分割閾值算法改進(jìn)及其應(yīng)用[J]. 中南大學(xué)學(xué)報(bào)(自然科學(xué)版), 2011, 42(12): 3772? 3776. YAO Yafu, Xing Liutao. Improvement of C4.5 decision tree continuous attributes segmentation threshold algorithm and its application[J]. Journal of Central South University (Science and Technology), 2011, 42(12): 3772?3776.

[6] 鄧生雄, 雒江濤, 劉勇, 等. 集成隨機(jī)森林的分類模型[J]. 計(jì)算機(jī)應(yīng)用研究, 2015, 32(6): 1621?1624. DENG Shengxiong, LUO Jiangtao, LIU Yong, et al. Classification model based on ensemble random forests[J]. Application Research of Computers, 2015, 32(6): 1621?1624.

[7] ALSHOMRANI S, BAWAKID A, SHIM S O, et al. A proposal for evolutionary fuzzy systems using feature weighting: dealing with overlapping in imbalanced datasets[J]. Knowledge-Based Systems, 2015, 73(1): 1?17.

[8] BEYAN C, FISHER R. Classifying imbalanced data sets using similarity based hierarchical decomposition[J]. Pattern Recognition, 2015, 48(5): 1653?1672.

[9] 陳橙, 顏艷, 何瓊, 等. 決策樹與logistic回歸模型用于開奶時(shí)間延遲影響因素分析[J]. 中南大學(xué)學(xué)報(bào)(醫(yī)學(xué)版), 2018, 43(3): 306?312. CHEN Cheng, YAN Yan, HE Qiong, et al. Risk factors for delayed breastfeeding initiation based on decision tree model and logistic regression model[J]. Journal of Central South University (Medical Sciences), 2018, 43(3): 306?312.

[10] LI Fenglian, ZHANG Xueying, ZHANG Xiqian, et al. Cost-sensitive and hybrid-attribute measure multi-decision tree over imbalanced data sets[J]. Information Sciences, 2018, 422: 242?256.

[11] KOZIARSKI M, WO?NIAK M. CCR: A combined cleaning and resampling algorithm for imbalanced data classification[J]. International Journal of Applied Mathematics & Computer Science, 2017, 27(4): 727?736.

[12] 付忠良. 多標(biāo)簽代價(jià)敏感分類集成學(xué)習(xí)算法[J]. 自動(dòng)化學(xué)報(bào), 2014, 40(6): 1075?1085. FU Zhongliang. Cost-sensitive ensemble learning algorithm for multi-label classification problems[J]. Acta Automatica Sinica, 2014, 40(6): 1075?1085.

[13] LI Hongjia, CAI Ruizhe, LIU Ning et al. Deep reinforcement learning: Algorithm, applications, and ultra-low-power implementation[J]. Nano Communication Networks, 2018, 16: 81?90.

[14] WU Jingda, HE Hongwei, PENG Jiankun, et al. Continuous reinforcement learning of energy management with deep Q network for a power split hybrid electric bus[J]. Applied Energy, 2018, 222: 799?811.

[15] 周浦城, 洪炳镕. 基于決策樹的強(qiáng)化學(xué)習(xí)算法[J]. 計(jì)算研究與發(fā)展, 2005, 42(S): 233?237. ZHOU Pucheng, HONG Bingrong. Decision tree based reinforcement learning algorithm[J]. Journal of Computer Research and Development, 2005, 42(S): 233?237.

[16] SUTTON R S, BARTO A G. Reinforcement learning: an introduction[M]. 2nd ed. London, UK: MIT Press, 2018: 1?68

[17] SUN Shasha, FAN Wenlai, XU Yan, et al. Comparative analysis of the aroma components of Cabernet Sauvignon in four regions [J]. Science & Technology of Food Industry, 2013, 34(24): 70?69.

[18] ALSHOMRANI S, BAWAKID A, SHIM S O, et al. A proposal for evolutionary fuzzy systems using feature weighting: Dealing with overlapping in imbalanced datasets[J]. Knowledge-Based Systems, 2015, 73(1): 1?17.

[19] ANTONELLI M, DUCANGE P, MARCELLONI F. An experimental study on evolutionary fuzzy classifiers designed for managing imbalanced datasets[J]. Neurocomputing, 2014, 146: 125?136.

[20] ARCHER K J, KIMES R V. Empirical characterization of random forest variable importance measures[J]. Computational Statistics and Data Analysis, 2008, 52(4): 2249?2260.

Identically distributed multi-decision tree based on reinforcement learning and its application in imbalanced data sets

JIAO Jiangli, ZHANG Xueying, LI Fenglian, NIU Zhuang

(College of Information and Computer, Taiyuan University of Technology, Taiyuan 030024, China)

As the general decision tree can not classify the minority class of the imbalanced data sets well, an improved identically distributed multi-decision tree approach based on reinforcement learning cumulative reward was proposed to optimize the attribute selection strategy. Firstly, the majority class samples of the imbalanced data sets were randomly sampled by the identically distributed random sampling approach, and then each single decision tree was established over each subset and eventually a multi-decision tree was formed. Each single decision tree was constructed by classification and regression tree(CART) algorithm firstly and then reinforcement learning cumulative reward mechanism was utilized to optimize the attribute selection strategy. The results show that the proposed attribute optimization strategy based on the reinforcement learning cumulative reward mechanism effectively improves the probability that the minority class can be correctly classified. The identically distributed multi-decision tree method effectively improves the overall prediction performance over imbalanced data sets. Moreover, the positive rate and geometric mean value of positive and negative rates are improved at the same time.

imbalanced data sets; multi-decision tree; cumulative reward mechanism attributes selection strategy; identically distributed random sampling; reinforcement learning

TP301

A

1672?7207(2019)05?1112?07

10.11817/j.issn.1672?7207.2019.05.014

2018?06?11；

2018?08?11

國家自然科學(xué)基金資助項(xiàng)目(61376693)；山西省重點(diǎn)研發(fā)計(jì)劃(社會(huì)發(fā)展領(lǐng)域)項(xiàng)目(201803D31045)；山西省自然科學(xué)基金資助項(xiàng)目(201801D121138)；山西省重大專項(xiàng)(20181102008)；山西省優(yōu)秀人才科技創(chuàng)新項(xiàng)目(201605D211021) (Project(61376693) supported by the National Natural Science Foundation of China; Project(201803D31045) supported by Key R&D (Social Development) Program of Shanxi Province;Project(201801D121138) supported by the Natural Science Foundation of Shanxi Province; Project(20181102008) supported by the Major Program of Shanxi Province; Project(201605D211021) supported by the Science and Technology Innovation Program for Excellent Talents in Shanxi Province)

張雪英，博士，教授，博士生導(dǎo)師，從事語音信號(hào)處理以及人工智能等研究；E-mail: tyzhangxy@163.com

(編輯 伍錦花)