[發明專利]一種基于邊緣侵蝕的聚類方法

在審

• 申請號: 201710690910.0
• 申請日: 2017-08-14
• 公開（公告）號: CN107491785A
• 公開（公告）日: 2017-12-19
• 發明（設計）人: 趙萬磊;鄧稱浩;王菡子
• 申請（專利權）人: 廈門大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 廈門南強之路專利事務所(普通合伙)35200
• 代理人: 馬應森,曾權

技術領域

本發明涉及聚類問題，尤其是涉及一種基于邊緣侵蝕的聚類方法。

背景技術

聚類問題源自于一系類的應用，如文本/網頁聚類、模式識別、圖像鏈接、圖像分割、通過向量量化進行的數據壓縮以及生物信息學。最近30年有大量的聚類算法被提出，但是各種算法都有不少的缺陷：

1.k-means是最通用的聚類算法，需要指定聚類數目，并且這種算法傾向于發現簇大小差不多的球狀簇；

2.DBSCAN是基于密度的聚類，能發現任意形狀的簇，但需要給出區別類的閾值，而這個閾值通常是很難確定的。

clusterDP是2014年在《Science》上發表的，綜合表現較好的算法，但是仍然需要指定聚類數目，且適用于類的中間到邊緣密度依次遞減的情形。

發明內容

本發明的目的在于以克服聚類算法的上述缺陷，提供一種基于邊緣侵蝕的聚類方法，

本發明包括以下步驟：

1)計算輸入數據每個點的近鄰關系或者直接獲得每個數據點的近鄰關系；

在步驟1)中，所述計算輸入數據每個點的近鄰關系的具體方法可為：計算每兩個點之間的距離，獲得每個點周圍的近鄰關系，找出每個點周圍的近鄰關系可包括但不限于以下方式：

(1)找出每個點距離范圍d內的所有點作為該點的近鄰；所述距離范圍為任何可算出近鄰關系的距離度量，支持多種近鄰關系，對于輸入數據每個點的密度即周圍鄰接點數可以被估計的情形都適用；所述距離包括歐氏距離，余弦距離，漢明距離等；

(2)找出距離每個點距離范圍d內的所有點作為該點的近鄰，若該點的近鄰數量少于k，則繼續加入距離超過d的點，直到其近鄰數等于k；所述d和k均為給定參數，d和k的選擇可根據具體問題選定，第一種近鄰關系稱之為對稱關系，第二種近鄰關系稱之為非對稱關系。

2)計算邊緣侵蝕密度；

在步驟2)中，所述計算邊緣侵蝕密度的具體方法可為：

(1)初始時以每點周圍近鄰點數量作為每個點的密度；

(2)刪除密度最小的點，若有多個點同時擁有最小密度，則同時刪除；

(3)重新計算刪除密度最小點之后，剩余點的密度；

(4)重復步驟(2)和步驟(3)直到所有的點都被刪除；

經過上述4個步驟，獲得每個點被刪除的先后順序，以刪除點的順序作為點的等級，先刪除的點等級較低，后刪除的點等級較高，同時刪除的點等級相同。

3)根據所述點的等級高低依次分配類標簽，具體方法如下：

(1)按照點的等級由高到低排列，即刪除先后順序的逆序；

(2)依次訪問每個點，若當前點的近鄰沒有類標，則分配一個新的類標，若有，則用已被標記的近鄰中離當前點最近的點的類標標記當前點；

(3)重復步驟(2)直到所有點被標記；按照剔除點的順序的逆序分配類標簽，類中心區域將最先被標記，一個類標簽將從類中心向外擴展，自動終止于類的邊界，類的邊界即為那些初始密度較低的點，所述類中心區域為高密度區域。

本發明的聚類有以下優勢：

1.無須指定聚類數目，通常只需要在獲得近鄰關系時使用一個閾值，這種判斷是否近鄰的閾值通常是很容易確定的；

2.可以發現任意形狀的聚類，因任意形狀的簇通常滿足邊緣密度最小；

3.聚類效果在各種數據集上取得了很好的效果，優于著名的DBCAN，AP，k-means和clusterDP算法；

4.近鄰關系可以使用一些近似算法獲得，在已有近鄰關系的前提下，由于每次更新近鄰密度僅僅涉及很少的點，因此很容易達到時間復雜度僅為O(n·log(n))，其中n為輸入要聚類的點的數目。

附圖說明

圖1是本發明方法在Aggregation測試集上的聚類結果。數據是人工生成的2維點。一個形狀代表點被本發明方法認定為一個類。

圖2是本發明方法在S2測試集上的聚類結果。數據是人工生成的2維點。一個形狀代表點被本發明方法認定為一個類。

圖3是本發明方法在Flame測試集上的聚類結果。數據是人工生成的2維點。一個形狀代表點被本發明方法認定為一個類。

圖4是本發明方法在Spiral測試集上的聚類結果。數據是人工生成的2維點。一個形狀代表點被本發明方法認定為一個類。

具體實施方式

以下實施例將結合附圖對本發明作進一步的說明。

本發明實施例包括以下步驟：