[發明專利]一種適用于高維大數據集的數據分類方法

在審

• 申請號: 201710983277.4
• 申請日: 2017-10-20
• 公開（公告）號: CN107943830A
• 公開（公告）日: 2018-04-20
• 發明（設計）人: 宋彬;張穎;張悅;郭潔
• 申請（專利權）人: 西安電子科技大學
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06N99/00
• 代理公司: 陜西電子工業專利中心61205
• 代理人: 田文英,王品華

技術領域

本發明屬于計算機技術領域，更進一步涉及數據分類技術領域中一種適用于高維大數據集的數據分類方法。本發明可用于高維大數據的分類，以提高數據分類的準確率。

背景技術

在過去的二十年里，人類收集、存儲、傳輸、處理數據的能力取得了飛速提升，人們積累了越來越龐大和復雜的數據，因此，能有效對數據進行分析和利用的計算機算法是現今迫切需要的。同時，高維大數據量和稀疏冗余的特征使得數據挖掘的難度不斷增大，一些傳統的機器學習算法已經不能取得較好的效果或難以適用于當前的場景，這導致了高維大數據的挖掘具有很大的挑戰性，也具有很大的提升空間。

浪潮電子信息產業股份有限公司在其申請的專利文獻“一種基于隨機森林加權距離的大規模高維數據分類方法”(申請號：201510272419.7，公開號：CN 104915679 A)中公開了一種大規模高維數據的分類方法。該方法首先對訓練樣本利用隨機森林算法計算各維度特征的重要性，用維度特征重要性數值來加權標準化距離，在此基礎上利用k近鄰算法進行分類。該方法存在的不足之處是：k近鄰算法用于大規模高維數據集時計算量過大，算法復雜度高，另外，對于現實場景下的高維稀疏數據集，傳統隨機森林算法收斂速度和分類精度表現不佳，導致該算法的準確率下降。

毛林、陸全華和程濤在其發表的論文“基于高維數據的集成邏輯回歸分類算法的研究與應用”(科技通報,2013年12期)中提出一種大規模高維數據的分類方法。該方法首先對全部特征隨機抽取多個特征集，并針對各個特征集構建多個邏輯回歸模型。最后針對多個邏輯回歸模型結果，利用集成學習方法進行最終預測。該方法存在的不足之處是：由于高維大數據集特征的冗余性和稀疏性，隨機的特征抽取很難選到有用的特征的問題，導致多數基分類器性能不佳，算法準確率不理想，且直接進行集成學習使得基學習器相似性高，容易過擬合。

發明內容

本發明的目的在于克服上述已有技術的不足，提出一種適用于高維大數據集的數據分類方法，在保證高維大數據下算法收斂速度的同時盡可能的提高分類精度。

實現本發明目的的具體思路是：依據高維稀疏數據集的特點，優化傳統隨機森林算法的特征選擇方式，提高基決策樹的分類能力及整體算法的性能。

實現本發明目的的具體步驟如下：

(1)輸入訓練樣本數據集和測試樣本數據集：

(1a)輸入一個包含兩種及以上類別的高維大數據集，作為訓練樣本數據集；

(1b)輸入一個包含兩種及以上類別的，與訓練樣本數據集特征相同的待分類的高維大數據集，作為測試樣本數據集；

(2)對訓練樣本集進行采樣：

(2a)采用自助采樣法，從訓練樣本數據集中抽取與訓練集樣本數量相等的樣本，作為抽樣樣本，放入一個采樣集中；

(2b)執行30次上述采樣，得到30個采樣集；

(3)計算特征權重：

(3a)利用基尼指數計算公式，分別計算每個采樣集對應的特征集中所有特征的基尼指數；

(3b)計算每個特征的基尼指數的倒數：

(3c)對每個特征的基尼指數的倒數進行歸一化處理，得到各特征的權重值；

(4)用輪盤賭法選擇特征：

(4a)按照下式，計算所有采樣集中每一個特征的累積權重值：

其中，q(i)表示第D個采樣集中第i個特征的累積權重值，Σ表示求和操作，W(D,j)表示第D個采樣集中第j個特征的權重值；

(4b)在[0,1]區間內隨機選擇一個均勻分布的偽隨機數；

(4c)判斷所選偽隨機數是否小于當前采樣集中第一個特征的累積權重值，若是，則執行步驟(4d)，否則，執行步驟(4e)；

(4d)將當前采樣集中的第一個特征放入當前采樣集的特征子集中；

(4e)判斷所選偽隨機數是否處于當前特征的累積權重值與當前特征的前一個特征的累積權重值之間，若是，則執行步驟(4g)，否則，執行步驟(4f)；

(4f)用當前特征的下一個特征作為當前特征，執行步驟(4e)；

(4g)將當前特征放入當前采樣集的特征子集中；

(4h)按照下式，計算當前采樣集的特征子集的容量：

k＝log₂n

其中，k表示當前采樣集的特征子集的容量，log₂·表示以2為底的對數操作，n表示采樣集的特征總數；

(4i)判斷當前特征子集中的特征總數是否等于特征子集的容量，若是，執行步驟(5)，否則，執行步驟(4b)；