[發明專利]一種簇心更新方法、裝置及K-means聚類分析方法、裝置

在審

• 申請號: 201810156872.5
• 申請日: 2018-02-24
• 公開（公告）號: CN108364026A
• 公開（公告）日: 2018-08-03
• 發明（設計）人: 張騰飛;王慧研;岳東;馬福民;歐陽志友;鄧松
• 申請（專利權）人: 南京郵電大學
• 主分類號: G06K9/62
• 分類號: G06K9/62;G06N99/00
• 代理公司: 南京正聯知識產權代理有限公司 32243
• 代理人: 王素琴

本發明公開了一種簇心更新方法、裝置及K?means聚類分析方法、裝置，其中所述簇心更新方法包括：對所有簇逐個計算簇中第一類對象決定的第一簇心、簇中第二類對象決定的第二簇心；計算待更新簇心所在簇的第一簇心與其他簇的第一簇心的第一距離之和；計算待更新簇心所在簇的第二簇心與其他簇的第二簇心的第二距離之和；根據下列公式計算待更新簇心所在簇中第一類對象的權值：根據下列公式確定新的簇心：本發明能夠體現出下近似對象和邊界區域對象的分散程度對于更新簇心的影響；能夠使得簇間距離更大，簇的邊界更加清晰，聚類效果更好。

技術領域

本發明涉及聚類分析技術領域，具體涉及一種簇心更新方法、裝置及K-means聚類分析方法、裝置。

背景技術

聚類分析作為一種無監督學習方法，是數據挖掘領域十分重要的研究內容，廣泛應用于圖像識別、信息檢索、生物信息挖掘以及基因分析等領域。粗糙K-means算法是一種經典的聚類分析方法，其方法步驟主要包括：首先確定初始簇心，分別計算各個待聚類對象到各個簇心的距離，根據各個距離確定各個待聚類對象為各個簇心所在的簇的下近似對象或邊界區域對象；然后根據各個簇的下近似對象和邊界區域對象更新簇心，再分別計算各個待聚類對象到各個簇心的距離，根據各個距離確定各個待聚類對象為各個簇心所在的簇的下近似對象或邊界區域對象……如此進行多次迭代，直至達到迭代截止條件，完成一輪迭代過程，以最終簇心確定的下近似對象及邊界區域對象為聚類結果。其中下近似對象是可以確定屬于某簇的對象，邊界區域對象是不能夠確定是否屬于該簇的對象。

現有粗糙K-means算法中，一個簇的簇心更新方法通常為：為簇中的下近似對象設置第一固定權值，為簇中的邊界區域對象

設置第二固定權值，以下近似對象和邊界區域對象的加權之和作為新的簇心。一整輪迭代過程中通常都會采用同樣的一組第一固定權值、第二固定權值(例如，第一固定權值為0.7，第二固定權值為0.3)?；蛘哌M一步地，還會另外設置不同的一組第一固定權值、第二固定權值(例如，第一固定權值為0.6，第二固定權值為0.4)，比較各組權值的聚類分析結果，以最優的結果作為最終的聚類分析結果。

然而，發明人發現，當簇中下近似對象和邊界區域對象的數量均相同時，假設有情形一：下近似對象集中于原簇心附近、邊界區域對象遠離原簇心，情形二：下近似對象和邊界區域對象相對均勻地分布在原簇心周圍，現有簇心更新方法對于情形一和情形二的簇心更新結果有時是相同的，無法體現下近似對象和邊界區域對象的分散程度對于更新簇心的影響。

發明內容

有鑒于此，本發明實施例提供了一種簇心更新方法、裝置及K-means聚類分析方法、裝置，以解決現有方法無法體現下近似對象和邊界區域對象的分散程度對于更新簇心的影響的問題。

根據第一方面，本發明實施例提供了一種簇心更新方法，簇由第一類對象和第二類對象組成，并且所述第一類對象和第二類對象中的一者為下近似對象，另一者為邊界區域對象；所述方法包括：對其他所有簇逐個計算簇中下近似對象決定的預簇心；計算待更新簇心所在簇的第一類對象決定的第一簇心與其他所有簇的預簇心的第一距離之和；計算待更新簇心所在簇的第二類對象決定的第二簇心與其他所有簇的預簇心的第二距離之和；

根據下列公式計算待更新簇心所在簇中第一類對象的權值：其中，w_i為待更新簇心所在簇i中第一類對象的權值，D₁為所述第一距離之和，D₂為所述第二距離之和，n為指數，并且n＞0；

根據下列公式確定新的簇心：其中，v_i為待確定的簇心，x_n為簇i中的對象，C_i為簇i中的第一類對象的集合，為簇i中的第二類對象的集合，N為簇i中的第一類對象的個數，為簇i中的第二類對象的個數。