[發明專利]非均勻大數據分類方法

有效

• 申請號: 201310452365.3
• 申請日: 2013-09-29
• 公開（公告）號: CN103500205B
• 公開（公告）日: 2017-04-12
• 發明（設計）人: 朱曉峰;張師超
• 申請（專利權）人: 廣西師范大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 桂林市華杰專利商標事務所有限責任公司45112
• 代理人: 巢雄輝

技術領域

本發明涉及計算機科學與技術領域和信息技術領域，具體涉及大數據，特別是一種非均勻大數據分類的處理方法。

背景技術

大數據是指沒有辦法在現有物理條件和允許的時間里用常規的軟件工具對內容進行抓取、管理和處理的數據集合。大數據有如下特點：Volume（數據量大）、Variety（數據類型繁多）、Value（價值密度低）、Velocity（處理速度快），被簡稱為4V。

目前大數據研究通常包括兩大類。第一，大數據對架構的挑戰。目前很多著名網站的HADOOP集群中裸數據容量達到幾十PB，而且存在冗余，每天需要掃描更新。然后HADOOP為了確保單節點失效或單機架失效不影響運行通常采用3副本策略。這樣數據在時間維和空間維方面都需要考慮到成本問題。因此，如果構造高效率的大規模小文件管理和大文件管理機制并存，同時支持結構化數據、非結構化數據和無結構數據的存儲、管理與訪問等都是必須要考慮的問題。第二，大數據知識發現和大數據對挖掘算法的挑戰。首先需要面多的是算法的可擴展性。一些數據挖掘和機器學習經典算法，例如KNN密度估計，非參BAYES，支持向量機，高斯過程回歸和層次聚類等算法，由于它們的復雜度至少是二次以上，都不能在大數據挖掘中得以較好的應用。所以，這就需要設計出更高效率的算法，即O(nlogn)或者O(n)。

從現有的大量大數據挖掘方面的文獻來看，大數據學習的研究主要集中在劃分、聚類、檢索、增量（批量、在線或平行）學習這4個方面的傳統方法的升級改良。目前對非均勻大數據問題處理的研究比較少。通常類似大數據知識發現的其他研究，大數據分類問題首先需要考慮的是算法的復雜度問題。其次現有分類算法（假設數據的不同類別分布是均勻的）直接應用到非均勻大數據上容易導致偏置（bias），即分類結果偏向于大類別（即此類別含有實例數目比例很大，例如在二類問題中超過90%）。最后，常見算法用于非均勻（不平衡）數據分類問題通常追求分類錯誤最小問題，但是忽略了非均勻類誤分類代價問題。

然而，非均勻大數據分類是一個極為挑戰性的問題，從何入手、怎么利用大數據進行智能活動，等等一系列亟待解決的基本問題。

發明內容

本發明研究非均勻大數據分類問題。

本發明的目的在于提供簡單而有效的非均勻大數據分類方法。該方法可解決大數據分類易出現的偏置問題以及大數據算法高復雜度問題。即本方法通過降抽樣(Downsampling)和二類分類(one-vs-all)大數據，達到線性復雜度非均勻大數據分類，通過集成多個分類器(ensemble)結果的方法解決偏置問題和提高分類準確率，并具有穩健性(robust)即抗噪性。

本方法的具體步驟如下：

(1)獲得大數據各類實例的數目m_i,i=1,2,…,M；

(2)采用Downsampling方法為每個類m_i抽樣出D_i數據集。其中每個數據集中數據量大小n_i由決定，其中t_a/2表示置信度的值，可以通過t分布臨界值獲得，ε表示最大的允許誤差。通過這樣方法對每個類m_i抽樣出D_i。

(3)對每個類m_i的D_i個數據集用one-vs-all方法（即當前類所有實例為正類，其他類的所有實例為負類）建立D_i個分類器，即對每個數據集構建一個分類器。

(4)對每個類m_i的D_i個分類器進行集成學習。根據集成學習理論，集成分類器可以由多個元分類器根據集成原理集合而成。所有的元分類器分類速度應該快，而且相互間是獨立的，每個分類器的錯誤率不高于50%。常見的此類分類器，如最近鄰算法，決策樹法，神經網絡法或者森林樹法(Forest?tree)等都能滿足上述要求。集成原理一般有bagging,adaboost,selective?ensemble等。本發明每個類m_i得到的D_i個分類器采用向前貪婪集成分類結果方法（forward?greedy?ensemble）對分類器進行集成學習。

(5)測試：對每個實例在每個類中進行分類，得到M個結果中的準確率最高的類為測試實例的類別。