[發(fā)明專利]基于J散度的新型決策樹分類方法

在審

• 申請?zhí)枺?/td>: 201910082556.2
• 申請日: 2019-01-28
• 公開（公告）號: CN109754023A
• 公開（公告）日: 2019-05-14
• 發(fā)明（設(shè)計(jì)）人: 楊云帆;陳文
• 申請（專利權(quán)）人: 上海交通大學(xué)
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 上海漢聲知識產(chǎn)權(quán)代理有限公司 31236
• 代理人: 莊文莉

1.一種基于J散度的新型決策樹分類方法，其特征在于，包括以下步驟：

S1、規(guī)范化輸入樣本數(shù)據(jù)集D＝{X_j⁽ⁱ⁾；C⁽ⁱ⁾},i＝1,2,...,M,j＝1,2,...,N，其中，X_j⁽ⁱ⁾表示樣本X⁽ⁱ⁾在特征A_j上的特征值，C⁽ⁱ⁾∈{c₁,c₂,...,c_K}表示樣本X⁽ⁱ⁾對應(yīng)的類別標(biāo)簽值；

S2、設(shè)置樣本數(shù)據(jù)集或數(shù)據(jù)子集的劃分終止條件，也即決策樹根據(jù)當(dāng)前結(jié)點(diǎn)的狀態(tài)，生成葉子結(jié)點(diǎn)不再繼續(xù)劃分的條件；

S3、準(zhǔn)備對原始樣本數(shù)據(jù)集進(jìn)行劃分，創(chuàng)建決策樹的根結(jié)點(diǎn)；

S4、按照劃分準(zhǔn)則進(jìn)行樣本數(shù)據(jù)集的劃分、決策樹結(jié)點(diǎn)的分裂以及決策規(guī)則的產(chǎn)生；

S5、采用遞歸的方式，將每次劃分得到的樣本子集繼續(xù)按照步驟S2、S3、S4進(jìn)行劃分，得到新的結(jié)點(diǎn)；

S6、對未知類別標(biāo)簽值的樣本X^*進(jìn)行類別值的判別預(yù)測。

2.根據(jù)權(quán)利要求1所述的基于J散度的新型決策樹分類方法，其特征在于，所述步驟S1中，原始樣本數(shù)據(jù)集D中有M個樣本，每個樣本用X⁽ⁱ⁾,i＝1,2,...,M表示，樣本數(shù)據(jù)集D中同樣包含了N個特征A_j,j＝1,2,...,N，每個特征A_j是類別型特征或者數(shù)值型特征，此外，數(shù)據(jù)集中共有K個類別標(biāo)簽值構(gòu)成集合C＝{c₁,c₂,...,c_K}，每個樣本都由這N個特征所對應(yīng)的N個特征值和一個類別標(biāo)簽值所描述，其中，對應(yīng)的特征值描述為X_j⁽ⁱ⁾，i＝1,2,...,M,j＝1,2,...,N，對應(yīng)的類別標(biāo)簽值描述為C⁽ⁱ⁾,i＝1,2,...,M。

3.根據(jù)權(quán)利要求1所述的基于J散度的新型決策樹分類方法，其特征在于，所述步驟S2中，劃分終止條件有3個，分別為：

a.設(shè)置參數(shù)決策樹最大高度MaxHeight，如果當(dāng)前結(jié)點(diǎn)在樹中的高度大于MaxHeight，則直接生成葉子結(jié)點(diǎn)，不再繼續(xù)往下劃分；

b.設(shè)置葉子結(jié)點(diǎn)最小樣本個數(shù)MinSamples，如果與當(dāng)前結(jié)點(diǎn)相關(guān)的樣本集或樣本子集中的樣本個數(shù)小于等于MinSamples，則直接生成葉子節(jié)點(diǎn)，不再繼續(xù)往下劃分；

c.設(shè)置當(dāng)前結(jié)點(diǎn)類別最小不確定度MinUncertainty，其取值范圍在[0,1]之間，如果當(dāng)前結(jié)點(diǎn)的不確定度U_c(p)小于MinUncertainty，則直接生成葉子節(jié)點(diǎn)，不再繼續(xù)往下劃分。

4.根據(jù)權(quán)利要求3所述的基于J散度的新型決策樹分類方法，其特征在于，所述當(dāng)前結(jié)點(diǎn)的不確定度U_c(p)的計(jì)算方法如下：假設(shè)與當(dāng)前結(jié)點(diǎn)相關(guān)聯(lián)的樣本集或樣本子集為D_c＝{X_j⁽ⁱ⁾；C⁽ⁱ⁾},i＝1,2,...,M_c,j＝1,2,...,N，則計(jì)算當(dāng)前結(jié)點(diǎn)的不確定度為：

其中，K表示類別標(biāo)簽值的個數(shù)，即數(shù)據(jù)集樣本分為K個不同的類別，p＝(p₁,p₂,...,p_K)是當(dāng)前樣本集中樣本類別標(biāo)簽值的概率分布向量，每個概率值由p_k＝|∑(C⁽ⁱ⁾＝c_k)|/|D_c|計(jì)算，其中|∑(C⁽ⁱ⁾＝c_k)|表示與當(dāng)前結(jié)點(diǎn)相關(guān)聯(lián)的樣本集或樣本子集D_c中類別標(biāo)簽值為c_k的樣本個數(shù)，|D_c|表示樣本集或樣本子集大小，即D_c中樣本總數(shù)。