[發明專利]基于組合凸線性感知器的兩類文本分類方法

有效

• 申請號: 201610083975.4
• 申請日: 2016-02-06
• 公開（公告）號: CN105760471B
• 公開（公告）日: 2019-04-19
• 發明（設計）人: 李玉鑑;王曼麗
• 申請（專利權）人: 北京工業大學
• 主分類號: G06F16/35
• 分類號: G06F16/35
• 代理公司: 北京思海天達知識產權代理有限公司 11203
• 代理人: 劉萍

1.一種基于組合凸線性感知器的兩類文本的分類方法，其特征在于包括以下步驟：

步驟一，收集文本數據集，將收集得到的文本數據集分為訓練樣本集和測試樣本集；

步驟二，預處理數據集，方法如下：

對文本數據樣本進行分詞，實現單詞字符小寫化、去停用詞以及刪除標點符號的初步處理，同時，統計每個測試樣本以及訓練樣本的詞頻；

步驟三，對訓練樣本集，提取出總詞表，方法如下：

對于總詞表中的每一個詞項，統計包含該詞項的正類樣本個數和負類樣本個數，過濾掉訓練樣本集中所有正、負類文檔頻率均小于3的詞項，得到總詞表；

步驟四，對訓練樣本集進行特征選取，得到特征向量表；具體方法如下：

對于步驟三得到的總詞表中的每一個詞項，計算詞項t對于文本類別c_i的χ²統計值χ²(t,c_i)；若χ²統計值越高，說明它與該類之間的相關性越大，同時攜帶的類別信息也比較多，計算公式如下：

其中，N表示訓練樣本集中的文本總數，A表示屬于c_i類且包含t的文檔頻數，B表示不屬于c_i類但是包含t的文檔頻數，C表示屬于c_i類但是不包含t的文檔頻數，D是既不屬于c_i也不包含t的文檔頻數；

步驟五，為數據集中所有樣本特征項賦權值，得到每個樣本的向量表示；采用tf·idf的賦權值方法，其中tf是詞頻，idf是逆向文件頻率；對于詞項t_k，令文本d關于t_k的權值為ω_k，產生文本d的向量表示d＝(ω₁,ω₂，…ω_k…,ω_n)；根據tf·idf計算權值ω_k的公式為：

ω_k＝tf_k·idf_k

其中，tf_k表示詞項t_k在文檔d中的出現頻率，已由步驟二得到，idf_k值的計算方法如下：

其中，N表示訓練樣本集中的文本總數，df_k表示包含t_k的所有文檔數目；

步驟六，對步驟五得到的所有樣本向量組，包括訓練集與測試集的所有數據，采用主成分分析對文本特征信息進行降維；這里，將訓練樣本集處理得到k維向量集合稱為T1，將測試樣本集處理得到k維向量集合稱為T2；其中，T2即最終的測試樣本集合；

步驟七，對T2每一個測試樣本t，利用SMA算法構造組合凸線性感知器，從而判斷測試樣本的類別；其中，判斷測試樣本類別的具體步驟如下：

(1)輸入由步驟六得到的訓練樣本集合T1和測試樣本集合T2；

(2)將T1分為正類樣本集合X'和負類樣本集合Y'，P為正類文本個數，F為負類文本個數：

X'＝{x_i,1≤i≤P},Y'＝{y_j,1≤j≤F}；

(3)根據SMA算法構造X'關于Y'組合凸線器，其構造步驟如下：

①找到當前X'關于Y'最近的兩個樣本，即對X'中的任意向量樣本x_i，對Y'中的任意向量樣本y_j，計算x_i與y_j的距離d_ij＝d(x_i,y_j)，公式如下：

比較所有d_ij的值，得到當前所有d_ij的最小值d_min，即d_min＝min{d_ij,1≤i≤P,1≤j≤F}；

如果d_min＜ε，ε取值0.000001，則輸出“X'和Y'不可分”，停止并退出；

②使用I和J分別用于存儲X'和Y'的指標，即I＝{i,1≤i≤P},J＝{j,1≤j≤F}；g用于存貯凸線器的組別數，l_g存貯第g組凸線器含有的線性判別函數的個數，g、l_g初值均賦為1，即g＝1，l_g＝1；

③分配數據空間J₁用于存貯J的子集，并把J賦給J₁，即J₁＝J；

④分配數據空間I₁用于存貯I的子集，并把I賦給I₁，即I₁＝I；

⑤找到當前I₁關于J₁最近的兩個樣本x_m和y_n，m和n的值計算公式如下：

(m,n)＝argmin{d_ij,i∈I₁,j∈J₁}；

⑥得到第g組的第l_g個線性判別函數計算公式如下：

其中，

⑦使用上一步得到的線性判別函數將I₁中已正確劃分類別的數據去除，形成新的I₁集，即從I₁中刪除所有滿足條件的指標i，I₁更新為：

⑧如果I₁仍存在數據未正確劃分類別，那么繼續求第g組的下一個線性判別函數，先更新l_g，l_g的值增加1，再求當前J₁中單個點距整個新I₁集的最近點對，即計算m＝argmin{d_in,i∈I₁}，返回步驟⑥；否則，用L_g存貯l_g的當前值，顯然，L_g表示X'關于Y'的組合凸線器中的第g組線性判別函數的總個數；

⑨將J₁中已正確劃分類別的數據去除，即從J₁中刪除所有滿足條件的指標j，J₁更新為：

⑩如果J₁中仍存在數據未正確劃分類別，那么繼續求下一組凸線器，先更新g，g的值增加1，再返回步驟⑤；否則，用變量G存貯g的當前值，顯然，G表示X'關于Y'的組合凸線器包含的線性判別函數的總組數；

(4)得到X'關于Y'的組合凸線器MCLP，即

其中：

(5)根據該組合凸線器MCLP，由決策函數判斷T2中每一個測試樣本t的類別，具體決策函數如下：

其中，+1表示正類，-1表示負類。