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

有效

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

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

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

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

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

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

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

Entropy(t)=Σi=0np(t,ci)log(p(t,ci))]]>

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

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

weight(t)=11+eentropy(t)-threshold]]>

其中，threshold是歸一化閾值；

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

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

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

S123、計算特征-類別詞頻與類別總詞頻的相對比例：

f′(t,c_i)＝f(t,c_i)/f(c_i)；

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

Entropy(t)=Σi=0np(t,ci)log(p(t,ci))]]>

其中，n為類別的總數目；

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

weight(t)=11+eentropy(t)-threshold]]>

其中，threshold是歸一化閾值；

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

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

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

2.根據權利要求1所述的基于信息熵特征權重量化的海量短文本分布式KNN分類方法，其特征在于，步驟S2具體為：

S21、將訓練數據集劃分成n個子集，其中n為Hadoop平臺中負責運算的從屬節點個數；

S22、每個從屬節點在讀入訓練數據子集時，建立一個特征與包含該特征的文檔之間的索引，表示為：<t_i：q_i,…,q_k>，其中t_i是特征，q_i為包含t_i的文檔，該索引用來快速查找包含某個特征的文檔集合，另外，建立一個文檔向量模的緩存單元；

S23、對于一個待分類的測試文檔數據q，同時分派給每個從屬節點，在每個節點中，首先初始化A[1]-A[k]作為q的初始近鄰，A[1]-A[k]按q與A[i]的相似度similarity(q,A[i])降序排序，然后通過查找索引找出包含q中特征的所有訓練集文檔<q_i,…,q_k>作為候選鄰居集合，依次計算q與每個候選鄰居q_i的余弦相似度，q與q_i的相似度的計算公式為：在計算相似度時，查找緩存單元中是否包含帶計算文檔q_i向量的模值||q_i||，若存在，將模值取出進行計算；若不存在，首先計算該文檔向量的模值，然后加入緩存單元，將得到的similarity(q,q_i)與similarity(q,A[i])比較，其中i∈[1,k],找出第一個similarity(q,A[i])<similarity(q,q_i)的A[i]，若i∈[1,k],則將A[j+1]＝A[j],其中j∈[i,k]，并令A[i]＝q_i；否則，繼續與下一個候選鄰居進行相似性計算，最終，A[1]-A[k]即為每個節點中與q局部最相似的k個鄰居；

S24、將每個節點中的局部最相似的k個鄰居采用多路歸并排序算法進行排序找出全局最相似的k個鄰居，將該k個鄰居以相似度進行預測類別投票，取出相似度最大的類別作為q的預測類別。