[發明專利]基于信息熵特征權重量化的海量短文本分布式KNN分類算法及系統

有效

• 申請號: 201410150855.2
• 申請日: 2014-04-15
• 公開（公告）號: CN103955489B
• 公開（公告）日: 2017-09-22
• 發明（設計）人: 蔡毅;蔡志威;王濤
• 申請（專利權）人: 華南理工大學
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06F17/27
• 代理公司: 廣州市華學知識產權代理有限公司44245
• 代理人: 蔡茂略

技術領域

本發明屬于文本分類技術領域，涉及一種基于信息熵特征權重量化的海量短文本分布式KNN分類算法及系統。

背景技術

隨著互聯網的高速發展，用戶生成的電子文檔及資源數目日益增長。文本分類技術成為處理和組織海量文檔數據的關鍵技術。特別是隨著微型博客和各類用戶評論等短文本數據在互聯網范圍內的大量出現，有關短文本的相關研究逐步受到人們的關注。分本分類算法一般包括：文本預處理、文檔的表示以及分類器的選擇和訓練。具體來說，文本預處理主要是將文本進行分詞切割，并將其中對于語義表達無用的停詞去除。文檔表示是為了降低文檔的復雜性，使其便于后續步驟的處理，將文檔的文本格式轉成向量格式。向量中的每個特征將被賦予一個權重用來表示其在分類貢獻度，對特征進行恰當的權重量化處理能夠有效地提高分類算法的分類精度。最后，采用相應的分類算法對重新表示后的文檔進行訓練，并對未分類的文檔進行類別預測及分類。

目前，對于文本分類處理方法大多是針對長文本分類提出的。所謂長文本是指篇幅較長，包含了較多內容的文本文件。不同于長文本，短文本具有關鍵詞特征稀疏、語境不完整和語義信息模糊的特點，使得傳統的文本表示方法在短文本處理時難以較好地量化特征在分類時的有用性。

此外，隨著大數據時代的到來，對海量數據處理的實時性、可靠性、可擴展性等有了更高的要求。在這種情況下，Hadoop、Spark等海量數據處理平臺應運而生。然而，傳統的算法大多數都是在單機環境下進行數據處理，尚未有效地擴展到并行、分布式計算平臺，使之能適應大數據處理能力的需求。

發明內容

本發明的主要目的在于克服現有技術的缺點與不足，提供一種基于信息熵特征權重量化的海量短文本分布式KNN分類算法。

本發明的另一目的在在于，提供一種基于信息熵特征權重量化的海量短文本分布式KNN分類系統。

為了達到上述第一目的，本發明采用以下技術方案：

基于信息熵特征權重量化的海量短文本分布式KNN分類算法，包括下述步驟：

S1、通過信息熵指標衡量特征在數據集中的分布確定性，將確定性高的特征賦予高權重，反之賦予低權重，得到反映類分布的權重量化方法；

S2、基于Hadoop分布式計算平臺，采用MapReduce計算框架進行設計的，分為兩輪MapReduce操作組合；

在第一輪Map操作中，訓練集被平均拆分為多個子訓練集并分配到進行運算的結點上，每一個待分類的測試數據同時在不同節點上，分別與該節點中的子訓練集進行相似度計算。在第一輪Reduce操作中，在各個節點中對Map計算得到的相似度進行排序，獲得每個節點上與測試樣本數據的局部最相似的k個訓練集樣本；

在第二輪Map操作中，將每個節點中的局部最相似的k個訓練集樣本的相似度和類別進行統計，在第二輪Reduce操作中，各個訓練集樣本以相似度進行投票，選出相似度最大的類別作為測試樣本數據的預測類別；其中第二輪MapReduce操作組可以根據集群節點數目酌情變換成多輪MapReduce操作組合。

優選的，步驟S1中，對于面向類分布均勻數據、基于熵的特征權重量化子方法的具體步驟為：

S111、初試化特征-類別分布矩陣，統計每個特征t在各個類c_i中出現詞頻f(t,c_i)；

S112、計算每個類別c_i的詞頻總數f(c_i)＝∑_tf(t,c_i)；

S113、計算特征在訓練數據集中的熵值:

其中p(t,c_i)＝f(t,c_i)/f(c_i)，n為類別的總數目；

S114、采用邏輯斯蒂方程計算特征的分類貢獻度：

其中，threshold是歸一化閾值。

優選的，面向非均勻類分布數據、基于平衡熵的特征權重量化子方法，考慮到類之間文檔數量的不平衡性，在一個樣本數極少的類中出現一次和在一個樣本數較多的類中出現一次應該給予不同的權重，包括以下步驟：

S121、初始化特征-類別分布矩陣，統計每個特征w在各個類c_i中出現詞頻f(t,c_i)；

S122、計算每個類別c_i的詞頻總數f(c_i)＝∑_tf(t,c_i)；