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

在審

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

本發(fā)明提供了一種基于J散度的新型決策樹分類方法，包括以下步驟：S1、規(guī)范化輸入樣本數(shù)據(jù)集；S2、設(shè)置樣本數(shù)據(jù)集或數(shù)據(jù)子集的劃分終止條件，也即決策樹根據(jù)當(dāng)前結(jié)點的狀態(tài)，生成葉子結(jié)點不再繼續(xù)劃分的條件；S3、準(zhǔn)備對原始樣本數(shù)據(jù)集進行劃分，創(chuàng)建決策樹的根結(jié)點；S4、按照劃分準(zhǔn)則進行樣本數(shù)據(jù)集的劃分、決策樹結(jié)點的分裂以及決策規(guī)則的產(chǎn)生；S5、采用遞歸的方式，將每次劃分得到的樣本子集繼續(xù)按照步驟S2、S3、S4進行劃分，得到新的結(jié)點；S6、對未知類別標(biāo)簽值的樣本X^*進行類別值的判別預(yù)測。本方法創(chuàng)新地使用了J散度這一信息度量用于劃分準(zhǔn)則的產(chǎn)生，使得決策樹分類算法的預(yù)測準(zhǔn)確度得到了提升。

技術(shù)領(lǐng)域

本發(fā)明涉及信息論和數(shù)據(jù)挖掘交叉技術(shù)領(lǐng)域，具體地，涉及一種基于J散度的新型決策樹分類方法。

背景技術(shù)

隨著無線移動通信、互聯(lián)網(wǎng)以及各種智能終端設(shè)備等技術(shù)的發(fā)展與進步，海量數(shù)據(jù)在呈指數(shù)爆炸式地不斷地產(chǎn)生和收集。如何從海量大數(shù)據(jù)中發(fā)現(xiàn)和提取有用的知識或規(guī)則是一系列值得考慮的問題。這些問題都涉及到大數(shù)據(jù)技術(shù)中的一個關(guān)鍵的技術(shù)，即數(shù)據(jù)挖掘技術(shù)。分類問題是數(shù)據(jù)挖掘所要解決的一個典型問題，廣泛應(yīng)用于垃圾郵件識別、文字和圖像識別、金融風(fēng)險控制和信用卡欺詐、在線廣告投放以及推薦系統(tǒng)等實際的應(yīng)用場景中。目前解決分類問題所采用的方法大多是有監(jiān)督的機器學(xué)習(xí)方法，包括樸素貝葉斯分類、邏輯回歸(Logistic Regression)、支持向量機SVM(Support Vector Machine)、最近鄰分類kNN(k-Nearest Neighbor)、神經(jīng)網(wǎng)絡(luò)(Neural Network)以及決策樹分類算法。其中，決策樹分類算法相較于其他分類算法由于其生成的決策樹清晰、簡潔以及可解釋性強，非常方便決策者做出相應(yīng)決策，廣泛實際的應(yīng)用在生產(chǎn)生活中。

決策樹分類算法的研究最早可追溯到上世紀八十年代，Quinlan于1986年首次在“Induction of decision trees”一文中提出基于信息增益的ID3決策樹分類算法。此后，他于1993年在著作“C4.5:programs for machine learning”提出基于信息增益率的改進版本的C4.5決策樹。而在此期間，幾乎是與此同時，Breiman和Friedman等多名統(tǒng)計學(xué)家在著作“Classification and regression trees”中介紹并提出了二叉結(jié)構(gòu)的CART決策樹分類算法。一時間決策樹學(xué)習(xí)成為當(dāng)時機器學(xué)習(xí)中炙手可熱的研究點。然而，受限于當(dāng)時的計算機技術(shù)，人工智能在不久后迎來了一輪寒冬，一些基本的機器學(xué)習(xí)分類算法的研究也在此后歸于平靜。

近年來，隨著大數(shù)據(jù)技術(shù)以及計算機計算能力的發(fā)展與進步，新一輪的人工智能浪潮來臨。機器學(xué)習(xí)算法也再度成為研究熱點，然而，近年來機器學(xué)習(xí)算法的研究大多集中在深度學(xué)習(xí)，集成學(xué)習(xí)以及遷移學(xué)習(xí)等復(fù)雜算法或模型的方向，對傳統(tǒng)的基本機器學(xué)習(xí)或數(shù)據(jù)挖掘的算法鮮有涉及。

經(jīng)對現(xiàn)有技術(shù)的檢索，申請?zhí)枮?01110100232.0的中國發(fā)明專利公開了一種處理缺失數(shù)據(jù)的新型決策樹分類器方法，包括以下步驟：將待處理的原始樣本數(shù)據(jù)集進行初始化設(shè)置，且將所述數(shù)據(jù)集進行權(quán)重值初始化分配；選擇一將所述數(shù)據(jù)集中的節(jié)點分裂為子節(jié)點的特征屬性；將樣本數(shù)據(jù)根據(jù)節(jié)點的特征屬性分類到各子節(jié)點；通過計算出各子節(jié)點選擇的特征量值將各子節(jié)點分裂出來；根據(jù)分裂出來的各子節(jié)點的樣本屬性確定葉子節(jié)點。該方案沒有采用J散度作為樣本數(shù)據(jù)集劃分以及決策樹結(jié)點分裂準(zhǔn)則，使得決策樹分類算法的預(yù)測準(zhǔn)確度無法得到進一步提升。

發(fā)明內(nèi)容

針對現(xiàn)有技術(shù)中的缺陷，本發(fā)明的目的是提供一種基于J散度的新型決策樹分類方法，應(yīng)用于數(shù)據(jù)樣本集的分類，以解決現(xiàn)有的決策樹分類方法的分類預(yù)測準(zhǔn)確度不佳的技術(shù)問題。

根據(jù)本發(fā)明提供的一種基于J散度的新型決策樹分類方法，包括以下步驟：