[發明專利]一種基于數據密度峰值的自標記半監督分類方法及裝置

在審

• 申請號: 201611136106.X
• 申請日: 2016-12-12
• 公開（公告）號: CN106778859A
• 公開（公告）日: 2017-05-31
• 發明（設計）人: 吳迪;李超華;尚明生;羅辛;袁野
• 申請（專利權）人: 中國科學院重慶綠色智能技術研究院;深圳市新利迪科技有限公司
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明提供一種基于數據密度峰值的自標記半監督分類方法及裝置，屬于計算機數據處理技術領域。

背景技術

在當今大數據時代，互聯網上每天都會產生大量的信息，且每天都在以驚人的速度膨脹，諸如新聞評論、BBS、博客、聊天室、聚合新聞(RSS)等應用每時每刻都會產生大量的數據，這些數據中包含人們對社會各種現象的各種觀點和立場，話題涉及政治、經濟、軍事、娛樂、生活等各個領域。如何在有限的時間范圍內對海量數據進行處理和分析，是當前計算機數據處理系統所面臨的嚴重挑戰，而機器學習正是解決上述問題的有效手段。

數據分類是機器學習的基本任務，是圖像視覺分析、文本分析、語音識別、輿情預警等領域的基礎工作。數據分類包含兩種形式，即監督分類與半監督分類。監督分類是數據樣本全部具有標簽；半監督分類是部分數據樣本具有標簽，部分數據樣本不具有標簽。在實際中，由于對數據進行標簽通常需要專家知識，導致帶標簽數據獲取代價太大，因而無標簽數據比帶標簽數據將多得多。因此，從可應用的信息量角度看出，半監督分類在現實應用中有更強的需求。

目前，半監督分類模型粗略的可分為四類，分別是生成式模型、基于圖的模型、半監督支持向量機模型和自標記模型。其中，自標記模型不需要具體的假設，其通過迭代的自我訓練和標記方式實現半監督分類，是目前研究的熱點。但是，現有的自標記半監督分類方法還存在不足，主要有兩點局限：一是某些方法對數據集形狀敏感，不能很好的解決非球形數據的適應性問題，導致陷入局部最優解；二是某些算法效率較低，在每次迭代過程中需要重新計算相關參數，導致大數據處理能力不足。

2014年6月，Rodriguez和Laio在《Science》雜志上發表了“一種基于數據密度峰值的聚類方法”(簡稱其為DPClus)，它通過定義兩個參數“局部密度”和“到具有更高局部密度點的最近鄰距離”來挑選出類中心點，然后再將其他所有數據樣本按照一個向量NNeigh(NNeigh[i]＝j表示第i個對象要劃分到與第j個對象相同的類中)的指示，在O(n)的時間復雜度上實現了數據聚類。DPClus具有思想簡單、效率高、準確性高、對數據形狀魯棒等優點，因此，將DPClus聚類算法引入自標記半監督分類模型，可解決現有自標記半監督分類模型非球狀數據適應性差和大數據處理能力不足的缺點。

發明內容

為了解決上述背景技術中現有的自標記半監督分類方法非球狀數據適應性差和大數據處理能力不足的問題，本發明基于數據密度峰值的聚類方法，提供一種自標記半監督分類方法及裝置，來對海量大數據實現快速準確的分類處理。

本發明提供一種基于數據密度峰值的自標記半監督分類方法，該方法包括如下步驟：

第一步：通過計算DPClus聚類方法定義的兩個參數“局部密度”和“到具有更高局部密度點的最近鄰距離”，得出目標向量NNeigh，發現數據內部結構特征，進一步利用標記數據集中帶標簽數據樣本的信息確定類中心點，構造一個類似于圖的數據空間結構；

第二步：根據第一步得出的數據空間結構，進入迭代訓練過程；首先，利用標記數據集中的帶標簽數據樣本訓練分類器；其次，根據數據空間結構，從未標記數據集中選出被標記數據集中所有帶標簽數據樣本所指向的下一個無標簽數據樣本；最后，利用訓練好的分類器，對選出的無標簽數據樣本進行類別標簽判別，并將判別后的數據樣本加入到標記數據集中；重復迭代以上過程，直至標記數據集中帶標簽數據樣本所指向的所有下一個無標簽數據樣本都被選出，并被判別類別標簽后加入到標記數據集中，才停止迭代；

第三步：根據第一步得出的數據空間結構，再次進入迭代訓練過程；首先，利用標記數據集中的帶標簽數據樣本訓練一個分類器；其次，根據數據空間結構，從未標記數據集中選出被標記數據集中所有帶標簽數據樣本所指向的上一個無標簽數據樣本；最后，利用訓練好的分類器，對選出的無標簽數據樣本進行類別標簽判別，并將判別后的數據樣本加入到標記數據集中；重復迭代以上過程，直至所有的無標簽數據樣本都被選出，并被判別類別標簽后加入到標記數據集中，才停止迭代；

第四步：利用最終的標記數據集，訓練分類器，完成訓練。

所述參數“局部密度”的計算公式如下：

其中，d_ij代表是第i個數據樣本x_i和第j個數據樣本x_j之間的距離，該距離度量可以是任一種距離度量形式；d_c是截斷距離。

所述參數“到具有更高局部密度點的最近鄰距離”的計算公式如下：