[發明專利]一種基于二叉樹結構的不平衡數據處理方法

在審

• 申請號: 201810320811.8
• 申請日: 2018-04-11
• 公開（公告）號: CN108920477A
• 公開（公告）日: 2018-11-30
• 發明（設計）人: 胡勤生;梁亞玲;杜明輝
• 申請（專利權）人: 華南理工大學
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06K9/62
• 代理公司: 廣州市華學知識產權代理有限公司 44245
• 代理人: 劉巧霞

本發明公開了一種基于二叉樹結構的不平衡數據處理方法，具體包括：(1)將原始數據集Ω劃分為正樣本空間集合Ω_P和負樣本空間集合Ω_N，創建Ω_N的副本C_N；(2)選擇正負樣本比r、樹的深度D、葉子節點的最少樣本數量LeafMin以及基聚類算法；(3)將C_N劃分為2個不相交的簇；(4)根據分裂準則，判斷Ω_N是否繼續分裂，形成二叉樹；(5)進行歸一化處理，求取特征差異度方差和特征極差程度；重復上述步驟，挑選出最佳的負樣本集合；(6)對最佳負樣本集合進行抽樣；(7)原始空間中的正樣本集合與最佳負樣本集合構成一個平衡樣本集合。本發明解決了正負樣本不平衡的問題，降低了數據集的噪聲，提高訓練速度，而且能夠提高每個基分類器的泛化能力。

技術領域

本發明屬于數據挖掘領域，特別涉及一種基于二叉樹結構的不平衡數據處理方法。

背景技術

在數據挖掘領域中，大量的場景中會出現數據集不平衡的問題，如搜索引擎的點擊預測(點擊的網頁往往占據很小的比例)、電子商務領域的商品推薦(推薦的商品被購買的比例很低)、信用卡欺詐檢測、網絡攻擊識別等等。在二分類問題中具體表現為正樣本數量相對負樣本數量要少很多。即正樣本少，負樣本多。這樣在分類問題上往往會導致分類結果偏向于負樣本。現有的數據集不平衡處理方法主要有：收集更多的正樣本數據、欠采樣過采樣、樣本權重賦值。收集更多的正樣本數據可以很好地解決數據不平衡問題，但是往往很多數據的獲得都是非常困難的，單純依靠增加數據量來解決不平衡數據集的方法是不現實的。在欠采樣中，通過隨機抽取部分負樣本，從而減少負樣本的數量，使得正負樣本比得到改善。但是欠采樣會導致部分重要的負樣本的信息丟失，使得數據不能得到充分的使用。在過采樣中，例如著名的SMOTE算法，就是通過人為的按照某種準則添加正樣本數量，但如果對正樣本擬合得不好，這個過程實際上是人為引入噪聲。在樣本權重賦值中，需要人為設定每個正、負樣本的權重，由于實際中，很難衡量某個正、負樣本的質量。因此若賦予的權重不適合，同樣也會加大數據集的噪聲。

發明內容

本發明的主要目的在于克服現有技術的缺點與不足，提供一種基于二叉樹結構的不平衡數據處理方法。本發明一方面能夠利用多次聚類算法來分裂出同類數據，使得相近的數據無需多次學習，僅學習一定量具有代表性的數據，從而減少負樣本數量，實現數據的充分利用。另一方面，本發明通過調整樹的深度以及葉子節點最少樣本數量來調整平衡樣本集合的質量，提高學習器的泛化能力。利用特征差異程度方差、特征極差程度兩個指標來準確、客觀地挑選出合適的樣本平衡比、樹的深度以及葉子節點最少樣本數量，大大提高訓練樣本的質量，從而提高不平衡數據處理方法的有效性。

本發明的目的能夠通過以下技術方案實現：

一種基于二叉樹結構的不平衡數據處理方法，具體包括以下步驟：

(1)將原始數據集Ω按標簽劃分為正樣本空間集合Ω_P和負樣本空間集合Ω_N，同時創建負樣本空間集合的副本C_N；

(2)選擇每個平衡樣本集合的樣本平衡比r、選擇樹的深度D、葉子節點的最少樣本數量LeafMin以及基于原型聚類的基聚類算法Γ；

(3)采用步驟(2)中所選擇的基聚類算法Γ將負樣本集合C_N劃分為2個不相交的簇C_i,i＝1,2；

(4)根據分裂準則，判斷步驟(3)中所劃分的簇，即C_N←C_i,i＝1,2是否滿足分裂準則；若滿足分裂準則，則對負樣本集合C_N重復步驟(3)和步驟(4)直至當前負樣本集合C_N不再滿足分裂準則；遞歸完畢后，形成二叉樹Τ；