[發明專利]一種K近鄰相似度優化的密度峰聚類方法

在審

• 申請號: 201710607140.9
• 申請日: 2017-07-24
• 公開（公告）號: CN107392249A
• 公開（公告）日: 2017-11-24
• 發明（設計）人: 葛洪偉;朱慶峰;江明;李莉
• 申請（專利權）人: 江南大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.K近鄰相似度優化的密度峰聚類方法，包括：

(1)計算所有點間距離，算出截斷距離d_c值，利用高斯函數：計算每個數據點的密度，然后利用函數：計算每個點到密度比它大的最近點的距離δ。其中，d_ij表示點i和點j的距離。對于全局密度最大的點，令δ_i＝max_jd_ij。

(2)根據每個點的ρ和δ值畫出決策圖，找出聚類中心。

(3)根據函數：計算點間相似度，找到每個點的K近鄰點。其中X＝(x₁,…,x_d)和Y＝(y₁,…,y_d)是d維空間中的兩個向量，m_i表示第i維上X和Y的平均值的絕對值。

(4)所有的點按照密度從大到小排序，新建空數組Aq，Bq，并把聚類中心依次放入數組Aq。

(5)按照密度從大到小的順序，依次取點i，判斷點i是否已經分配。如果已經分配，取下一個；如果未分配，則進行下一步。

(6)判斷點i是否是密度峰值點。如果不是，取下一個；如果是，判斷點i與指向點j是否連通。如果連通，把點i放入數組Aq末尾；如果不連通，則把點i放入數組Bq末尾。

(7)判斷數組Bq是否為空，如果為空，則將剩余的點分配，結束；如果不為空，則分別從數組Aq中找出一個點j，從數組Bq中找出一個點h，滿足點j與點h距離最近。

(8)判斷點h與點j是否連通，如果連通，則點h的指向點為點j，把點h歸入點j所在族類，并將點h加入數組Aq末尾，并從數組Bq中刪除點h；如果不連通，尋找下一對最近點，判斷。重復，直到數組Bq為空或者數組Bq中剩余點都不與數組Aq中的點連通。

(9)判斷數組Bq是否為空，如果為空，則將剩余的點分配給指向點，結束；如果不為空，則從數組Bq中找出點t，從數組Aq中找出點j，滿足點t與點j距離最近，將點t指向點j，并將點t加入數組Aq末尾，從數組Bq中刪除點t，重復，直到數組Bq為空。

(10)將剩余的點分配給指向點，結束。

2.根據權利要求書1所述的K近鄰相似度優化的密度峰聚類，其中，步驟(6)所述的判斷點i是否為密度峰值點以及點i和點j是否連通，按照如下方法：

(2.1)根據決策圖，選出聚類中心，剩余的點如果不在其指向點的K近鄰內，那么它就是密度峰值點。根據DPC算法定義，聚類中心到密度比它大的最近點距離較遠，所以聚類中心也作為密度峰值點。

(2.2)如果一個點i(樣本點)在點j(指向點)的K近鄰內，則點i與點j連通。否則，從點j的K近鄰內尋找與點i相似度最大的點j_n(第n次找到的點)，判斷點i與點j_n相似度是否大于點i與點j_n-1(第n-1找到的點，j₀＝j)：如果點i與點j_n的相似度大于點i與點j_n-1，并且i點在點j_n的K近鄰內，則點i與點j連通；如果點i與點j_n的相似度大于點i與點j_n-1，但是i點不在點j_n的K近鄰內，則從點j_n的K近鄰內繼續尋找與點i相似度最大的點j_n+1，重復上面的判斷；如果點i與點j_n的相似度小于等于點i與點j_n-1，則點i與點j不連通。