[發明專利]一種最大熵證據C均值聚類方法

在審

• 申請號: 202110624768.6
• 申請日: 2021-06-04
• 公開（公告）號: CN113283523A
• 公開（公告）日: 2021-08-20
• 發明（設計）人: 焦連猛;王豐;楊浩宇;馬皓楠;劉準釓;梁彥;潘泉
• 申請（專利權）人: 西北工業大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 西北工業大學專利中心 61204
• 代理人: 金鳳

本發明公開了一種最大熵證據C均值聚類方法，首先在傳統ECM算法的目標函數中加入熵約束條件；然后針對條件極值問題使用拉格朗日乘子法，引入n個拉格朗日因子，然后對各個變量求導，得到各個變量的極值點，從而最終得到各變量的迭代公式，完成聚類工作。本發明利用信息熵區分樣本相似性的特性對算法進行約束，減少噪聲點對聚類性能的影響，同時將熵作為聚類算法的正則化函數，有效提高了算法的噪聲檢測能力和對觀測值的適當分配能力。

技術領域

本發明屬于數據處理技術領域，具體涉及一種C均值聚類方法。

背景技術

聚類就是將物理或抽象的對象，按照對象間的相似性進行區分和分類的過程，是一種無監督的分類。聚類分析已經被廣泛地應用到很多領域中，包括數據分析、模式識別、市場研究以及圖像處理等。聚類分析的方法可以分很多種，根據其分類思想的不同，可以分為基于劃分的方法、基于分層的方法、基于密度的方法和基于網格的方法等等。在這之中，基于劃分的算法是最常用的聚類算法類型之一，有時也被叫做基于目標函數的聚類算法。然而，傳統的聚類劃分方法是一種硬性劃分，核心思想是把每個待處理的目標樣本嚴格地依照公式劃分到某個類或者簇中。硬性劃分方法的代表是C均值算法。在這個算法中，樣本的隸屬度不是1就是0，而現實中大多數的對象并沒有嚴格的屬性可以用于甄別，所以這種硬性的劃分無法真正地反應出需要分類的對象和類之間的實際關系，反而很容易在聚類時產生錯分、漏分的情況。在硬劃分基礎上改進的模糊劃分將模糊邏輯應用于聚類方法，觀察結果可以屬于不止一個聚類，這種組合將提供更大的靈活性來處理真實世界觀測中的不確定性。但模糊劃分對于邊界和偏離樣本仍得不到符合人類認知的聚類結果。

基于置信函數理論的證據C均值(ECM)很好地解決了這一問題。Dempster-Shafer證據理論(或置信函數理論)與概率論或可能性論一樣，是一個用部分和不可靠信息進行推理的理論框架。它包含不確定性下的不同推理模型。證據劃分允許對象不僅屬于單個聚類，而且屬于描述可能聚類的識別框架的任何子集。因此，證據劃分提供了比其他劃分更精細的劃分結果，這使得它對于解決復雜的數據聚類問題非常有吸引力。然而，當觀測值中有過多噪聲點時，這種方法的性能可能會降低。為減少噪聲點對聚類性能的影響，利用信息熵區分樣本相似性的特性對算法進行約束。

發明內容

為了克服現有技術的不足，本發明提供了一種最大熵證據C均值聚類方法，首先在傳統ECM算法的目標函數中加入熵約束條件；然后針對條件極值問題使用拉格朗日乘子法，引入n個拉格朗日因子，然后對各個變量求導，得到各個變量的極值點，從而最終得到各變量的迭代公式，完成聚類工作。本發明利用信息熵區分樣本相似性的特性對算法進行約束，減少噪聲點對聚類性能的影響，同時將熵作為聚類算法的正則化函數，有效提高了算法的噪聲檢測能力和對觀測值的適當分配能力。

本發明解決其技術問題所采用的技術方案包括如下步驟：

步驟1：在ECM算法的目標函數中加入熵約束條件；

步驟1-1：ECM是基于置信劃分的一種聚類算法，即利用定義在集合Ω＝{ω₁,........ω_c}上的基本置信隸屬函數m_i來表示對象i的類別；對于每個對象i，當i和焦點A_j間的距離d_ij越遠時，m_ij＝m_i(A_j)的值越小；每個類ω_k用一個v_k表示；

定義：

與A_j相關聯的重心通過下式計算：

其中c_j＝|A_j|是A_j的勢；

對象i與任一重心的距離定義如下：