[發明專利]增量聚類方法和裝置

在審

• 申請號: 201910204066.5
• 申請日: 2019-03-18
• 公開（公告）號: CN110110736A
• 公開（公告）日: 2019-08-09
• 發明（設計）人: 張勇;郭達;張朔銘;鄧海勤;高志勇;宋云鵬
• 申請（專利權）人: 愛動超越人工智能科技（北京）有限責任公司
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 北京路浩知識產權代理有限公司 11002
• 代理人: 王瑩;吳歡燕

本發明實施例提供增量聚類方法和裝置，用于在根據基于密度的層次聚類算法獲得首次聚類結果的基礎上，對首次聚類后每次新增數據點進行聚類。其中，方法包括：對于新增數據點，以全部類的類密度的最大值作為鄰域半徑，獲取所述新增數據點的鄰域內的數據點；根據新增數據點的鄰域內的數據點所屬的每個類的類密度，確定所述新增數據點所屬的類。裝置包括：鄰域掃描模塊和增量聚類模塊。本發明實施例提供的增量聚類方法和裝置，實現了在密度可變的聚類結果的基礎上進行增量聚類。

技術領域

本發明實施例涉及數據處理技術領域，尤其涉及增量聚類方法和裝置。

背景技術

聚類是將物理或抽象對象的集合分成由類似的對象組成的多個類的過程，即將對象分類到不同的類或者簇的過程，同一個類中的對象有很大的相似性，不同類之間的對象有很大的相異性。

聚類方法包括很多種類?；诿芏群突趯哟蔚木垲愃惴m然簡單易行，廣受歡迎，但是現有的基于密度的算法有著一些局限性。

部分基于密度的聚類算法，基于全局密度，只能對數據提供一種比較單一的標簽，使用單一的密度閾值，對于密度不均勻的數據集，不能產生合適的具有特性的聚類效果；部分基于層次的聚類不能自適應的簡化層次成為一種簡單的，可分辨的，具有代表性的，最有意義的聚類；部分基于層次的聚類只是從全局密度閾值中提取一種單一的劃分，這對由不同密度等級的聚類對象，不能得出有意義的聚類；很多聚類方法常常依靠多個具有重要影響的參數。

其中，基于密度的聚類方法與其它的聚類方法不同的是，它不是基于各種距離，而是基于密度，只要一個區域中的點的密度大于某個閥值，就把它加到與之相近的聚類中去。這樣能夠克服基于距離的聚類算法只能發現“類圓形”的聚類的缺點。例如，DBSCAN(Density-Based Spatial Clustering of Applications with Noise)算法就是基于密度的聚類方法中一種典型算法，DBSCAN算法將簇定義為密度相連的點的最大集合，能夠把具有足夠高密度的區域劃分為簇，并可以在噪聲的空間數據庫中發現任意形狀的聚類。DBSCAN算法引入了核心對象的概念和兩個初始參數Eps(掃描半徑)和MinPts(最小包含對象數)。如果存在一個對象，在距它Eps的范圍內有不少于MinPts個對象，則該對象就是核心對象。核心對象和它的Eps范圍內的鄰居對象形成一個簇。在一個簇內如果出現多個對象都是核心對象，則以這些核心對象為中心的簇要合并。但是，此種聚類算法的聚類結果對參數Eps和MinPts的取值非常敏感，即Eps和MinPts的取值不同，產生不同的聚類結果，從而導致聚類結果的不確定性?；诿芏鹊木垲愑捎谄鋮档碾y調節性，聚類的結果在密度大的地方往往數量很大，而密度小的地方數量較少，這對于大多數應用場景(比如定位)來說是不利的條件，因為當數據匹配到密度大的類中時，由于該類的數據很多，會造成在該類中匹配的計算量很大，而且該類中的數據不一定對最后的結果有用。原始的基于密度的聚類對于真實世界中復雜的數據效果并不好。

增量聚類方法是當有一批聚類結果時，新增加一些數據，只對新增的數據進行聚類，并對已有的聚類結果進行增量式修改，不需要對新增數據后的整個數據集進行重新聚類。但是，相關技術中的聚類方法和增量聚類方法均無法同時保證高精確率和高召回率。例如，基于密度層次的HDBSCAN(Hierarchical Density-Based Spatial Clustering ofApplications with Noise)算法能獲得較好的密度可變的聚類結果，但在做增量更新時，無法有效更新已有的聚類狀態，只能在原有的聚類基礎上，靠分類來容納新增的對象。

發明內容

針對現有技術存在的無法在密度可變的聚類結果的基礎上進行增量聚類的問題，本發明實施例提供一種增量聚類方法和裝置。

本發明實施例提供一種增量聚類方法，所述方法用于在根據基于密度的層次聚類算法獲得首次聚類結果的基礎上，對首次聚類后每次新增數據點進行聚類；所述方法包括：