[發(fā)明專利]一種基于局部密度和測地距離的分層譜聚類方法

在審

• 申請?zhí)枺?/td>: 201510233619.1
• 申請日: 2015-05-08
• 公開（公告）號: CN104778480A
• 公開（公告）日: 2015-07-15
• 發(fā)明（設(shè)計）人: 葛洪偉;張濤;蘇樹智;楊金龍
• 申請（專利權(quán)）人: 江南大學(xué)
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種基于局部密度和測地距離的分層譜聚類方法，包括如下步驟：

(1)輸入數(shù)據(jù)集X＝{x₁,x₂,...,x_n}∈R^d，x_n表示數(shù)據(jù)集中的第n個樣本，n為樣本個數(shù)，d為樣本維數(shù)；

(2)局部密度計算：

令ρ_i為樣本x_i的局部密度，i＝1,2,…n。

ρi=Σj=1n-1e(d(xi,xj)dc)2]]>

其中n為樣本總數(shù)，d(x_i,x_j)為樣本x_i與樣本x_j的歐式距離，d_c為截斷距離。

(3)密度有向圖的構(gòu)造：

(3a)計算樣本點x_i與局部密度高于ρ_i的點間最小距離：

δi=minj:ρj>ρi(d(xi,xj))]]>

(3b)定義集合V_all存放所有點的標(biāo)號，數(shù)組N_neigh存放每個點的最近高密度點標(biāo)號，根據(jù)式可以判斷樣本x_i的最近高密度點標(biāo)號為：

N_neigh(x_i)＝j(luò)

其中局部密度最高的點，沒有與其最近的高密度點。為了方便選擇邊緣點，局部密度最高點的最近高密度點為本身，若局部密度最高點為x_q，則N_neigh(x_q)＝q。

(3c)構(gòu)造密度有向圖：

每個點與其最近的高密度點構(gòu)造有向圖，方向為該點指向其最近的高密度點。

(4)有向圖剪枝和邊緣點集合生成：

N_neigh存放每個點的最近高密度點的標(biāo)號，在N_neigh中沒有出現(xiàn)標(biāo)號的點即是邊緣點，與邊緣點連接的邊需要進行剪枝。在對有向圖進行一次剪枝后，將邊緣點加入集合V_marg。此時，有向圖中又會出現(xiàn)邊緣點，對其進行二次剪枝，將剪枝后邊緣點再次加入集合V_marg。經(jīng)過二次剪枝后，剩下的點稱為非邊緣點，用集合V表示，滿足V_marg∪V＝V_all。

(5)無向連通圖構(gòu)造：

(5a)非邊緣點集合V中的點采用K近鄰方式構(gòu)圖：

尋找集合V中樣本點x_i在集合V中的K個最近鄰樣本點，如果x_j是x_i在集合V中的K個最近鄰樣本點，則P(x_i,x_j)＝1，P(x_j,x_i)＝1；否則P(x_i,x_j)＝0，P(x_j,x_i)＝0。

(5b)邊緣點集合V_marg中的點構(gòu)圖

緣點集合V_marg中的樣本點x_i,根據(jù)式N_neigh(x_i)＝j(luò)將每個邊緣點與其最近的高密度點構(gòu)造連接關(guān)系，則P(x_i,x_j)＝1，P(x_j,x_i)＝1；否則P(x_i,x_j)＝0，P(x_j,x_i)＝0。

(6)計算測地距離

(6a)初始化測地距離矩陣：

dG(xi,xj)=d(xi,xj),ifP(xi,xj)=1∞,other]]>

其中d(x_i,x_j)為樣本點x_i與x_j之間的歐氏距離。

(6b)計算最短路徑：

For?k＝1to?n

d_G(x_i,x_j)＝min{d_G(x_i,x_j),d_G(x_i,x_k)+d_G(x_k,x_j)}

End

(7)計算樣本集X內(nèi)所有點之間的相似度，得到相似度矩陣A，其中A(x_i,x_j)＝0，i＝j(luò)。尺度參數(shù)σ_i＝d(x_i,x_l)，x_l為樣本點x_i的第l個近鄰點。

(8)構(gòu)建度矩陣D和拉普拉斯矩陣L；其中，D為對角矩陣，對角元素表示第i個樣本x_i的度，L＝D^-1/2AD^-1/2；

(9)計算L的前k個最大特征值所對應(yīng)的特征向量，并構(gòu)成矩陣U，然后單位化得到矩陣Y＝[y_ij]_n×k，其中，yij=uij(Σj=1Kuij2)1/2;]]>

(10)將Y的每一行作為k維空間中的一個樣本點，通過K-means算法將這些樣本點聚成k類；當(dāng)且僅當(dāng)Y的第i行被分配為第j類時，將樣本x_i分配為第j類。

2.根據(jù)權(quán)利要求1所述的譜聚類方法，其中步驟(4)按如下過程進行：

(2.1)初始化：V＝V_all，m＝2；其中m為剪枝的次數(shù)，為空集合。

(2.2)將集合V中每個點的最近高密度點標(biāo)號存放在V_temp中；

(2.3)V_temp中重復(fù)出現(xiàn)的標(biāo)號，只保留一個。尋找在集合V中出現(xiàn)而在集合V_temp中未出現(xiàn)的標(biāo)號，加入集合V_marg(V_marg＝V_marg+(V-V_temp))；其中+，-為集合運算。

(2.4)更新集合V＝V_temp，m＝m-1；如果m＞0轉(zhuǎn)至步驟(2.2)，如果m≤0，程序結(jié)束，返回邊緣點集合V_marg和非邊緣點集合V。