[發明專利]一種基于MPI的ML-KNN多標簽中文文本分類方法

有效

• 申請號: 201710026254.4
• 申請日: 2017-01-13
• 公開（公告）號: CN106886569B
• 公開（公告）日: 2020-05-12
• 發明（設計）人: 王進;晏世凱;邵帥;李穎;歐陽衛華;胡峰;李智星;鄧欣;陳喬松;雷大江
• 申請（專利權）人: 重慶郵電大學
• 主分類號: G06F16/35
• 分類號: G06F16/35;G06K9/62
• 代理公司: 重慶市恒信知識產權代理有限公司 50102
• 代理人: 劉小紅

本發明請求保護一種基于MPI的ML?KNN多標簽中文文本分類方法，涉及文本分類和機器學習中的多標簽分類算法。為解決ML?KNN算法在具體實現中大規模文本分類問題和求解優化問題，控制計算的時間和空間的開銷，本發明采用的技術方案是，采用MPI編程實現中文文本數據的預處理、特征提取、ML?KNN算法及分類的并行化。相比傳統的串行多標簽中文文本分類方法，本發明極大的提高了多標簽中文文本分類的效率。同時，在數據量一定的情況下，算法的效率一般會隨著計算資源(進程數)的增加而增加。值得一提的是，在基于MPI并行化ML?KNN步驟中，對數據集進行劃分時既可以以樣本為單位劃分，又可以以特征為單位劃分，這使得本發明在處理高維文本數據的時候，具有更大的優勢。

技術領域

本發明涉及機器學習和高性能計算領域，具體涉及一種基于MPI編程并行化多標簽分類算法ML-KNN。

背景技術

近年來，信息技術迅猛發展，互聯網數據規模隨之呈海量增長，其表現形式也愈加豐富，然而傳統的監督學習認為每個樣本只有一個標簽，對事物的復雜語義信息缺乏準確表述的能力，多標簽學習(Multi-Label Learning)應運而生。多標簽學習認為單個樣本存在多個標簽與之關聯，與多個標簽關聯的樣本能夠更好的表述。近年來，多標簽學習問題受到了機器學習學術界和工業界越來越多的重視，已成為機器學習界的研究熱點之一。

ML-KNN(multi-label k Nearest Neighbor)是張敏靈和周志華提出的一種多標簽分類算法，該算法是由經典的單標簽學習算法KNN(k Nearest Neighbor)改進而來的。ML-KNN首先求出待預測樣本的k個最近鄰類別標簽出現的先驗概率和后驗概率，再基于最大化后驗概率的原則去確定待預測樣本的標簽集。算法在文本分類、生物信息學、信息檢索、網頁挖掘等諸多領域表現出了良好的效果。

設Ξ為特征空間，Ψ是有限個標簽的集合。對于任一樣本x(x∈Ξ)，其標簽的集合為樣本x的類別向量，向量中的元素為(l∈Ψ)，若l∈Y，則的值為1，否則為0。此外，定義N(x)為樣本x在訓練集中的K近鄰的集合，其中樣本之間相似度用歐氏距離度量，則成員統計向量被定義為：

用于統計在樣本x的K近鄰中標簽為l的樣本的個數。

對于測試樣本t，表示事件：樣本t含有標簽l；則表示事件：樣本t不含標簽l；表示事件：在樣本t的K近鄰中，恰好有j個樣本含有標簽l。利用最大化后驗概率準則(Maximum aPosteriori，MAP)，測試樣本t的標簽向量為：

通過貝葉斯公式，上式可轉換為：

是成立的先驗概率，通過統計訓練集中與標簽l相關的樣本數量得到；表示當成立時，測試樣本t的K近鄰中有個樣本含有標簽l的概率。

2.多標簽文本分類

Internet上存在的海量數據主要包括文本、聲音、圖像數據等。其中，文本數據與其他數據相比，具有占用網絡資源小的特點，這使得網上的數據大多是以文本的形式呈現的。為了有效的管理和利用這些文本數據，從中發現有價值的信息，基于內容的信息檢索和數據挖掘技術倍受關注。而文本分類技術是信息檢索的基礎，其主要任務是按照預先定義的主題類別，為文檔集合中的每個文檔確定一個類別。

文本分類最初是應信息檢索的需求而出現的，早期以人工構建分類器為主，經過幾十年的發展，基于機器學習的文本分類技術成為了主流，該方法包涵文本預處理，特征選擇，分類器的構建三個步驟，實現了文本的自動分類。在互聯網廣泛使用的今天，網絡信息快速膨脹，基于機器學習的文本分類技術已成為信息檢索與數據挖掘領域的核心技術。