技術領域

本發明涉及信息技術領域，具體涉及一種數據關聯性的確定方法。

背景技術

聚類分析是根據對象之間的相似度將對象劃分成不同的簇，使得同一簇內的對象相似度最大化，而不同簇之間的對象相似度最小化。

聚類分析中的圖聚類是指把圖分成互不相交的一些子圖，使得同一子圖內的節點具有較高的緊密性，而子圖之間的各節點緊密性較低。一個圖通常表示為G＝(V,E,W)，其中V是節點的集合,E是邊的集合，W是邊權重。圖聚類問題就是把圖G劃分成K個互不相交的子圖G_i＝(V,E,W),i＝1,2,…,K。現有技術中的圖聚類方法存在以下不足之處：1)分割質量不夠高，易產生小聚類；2)計算速度較慢等問題.

發明內容

本發明的主要目的在于克服上述現有技術的缺陷，提供了一種數據關聯性的確定方法，以解決現有技術中數據關聯性確定過程中速度較慢，聚類質量不夠高的缺陷，在能夠提供高質量的聚類結果的同時，保證了較快的處理速度。

本發明一方面提供一種數據關聯性的確定方法，包括以下步驟：

第一步，對圖G的數據進行聚類，獲得N個簇，G‘＝{G’_i}，i＝1，2，…，N；

第二步，對獲得的所述N個簇，進行歸并，生成K個簇，K＜N；

其中，第一步進一步包括以下步驟：

第1.1步，計算圖G的鄰接矩陣A；

第1.2步，對每個節點添加自環，即A′：＝A+I,；其中，I為對角線元素為1的對角矩陣；

第1.3步，計算轉移概率矩陣M：

M(i,j)代表節點v_i到節點v_j的轉移概率；

第1.4步，M進行擴展參數為e的擴展操作，其中，e為大于1的正整數，得到矩陣M1；

M1＝M_exp＝Expand(M,e)＝M^e

第1.5步，對M1進行膨脹參數為r的膨脹操作，膨脹參數r為正實數，得到矩陣M2；

重復執行步驟1.4、步驟1.5，直至矩陣M2不發生變化，此時生成穩定的轉移矩陣M2；

第1.7步，對穩定的轉移矩陣M2并進行歸類，獲得N個簇。

可選的，其中所述第1.7步對穩定的轉移矩陣M2并進行歸類具體為，對于M2中的每一行，將吸引節點與被吸引節點歸為一類。

可選的，其中所述重復執行步驟1.4、步驟1.5之前，將M2中的每列中接近零值的元素移除。

可選的，所述第二步具體為：

第2.1步，針對N個簇中的每個簇G’_i，計算與其鄰近的每個簇G’_j之間的相似度；

其中，RC為簇之間的近似度，RI為簇之間的互連度；α是互連度的重要度參數；

其中，|G’_i|表示簇G’_i內數據點的個數；EC(G’_i)表示簇G’_i內所有邊的權重和；EC(G’_i，G’_j)表示連接兩個簇的所有邊的權重和；

第2.2步，針對G’_i，獲得與其所有鄰近簇之間的相似度中的最大值Sim_max；

第2.3步，判斷相似度中的最大值Sim_max是否超過第一閾值，若判斷結果為是，則G’_i與該最大值對應的簇進行合并；若判斷結果為否，則將G’_i從G‘集合中移除，將其加入結果簇G＝{G₁,G₂,…,G_K}中；

第2.4步，重復第2.1步至第2.3步直至G‘集合中為空。

可選的，所述第二步具體為：

第2.1步，針對N個簇中的每個簇G’_i，計算與其鄰近的每個簇G’_j之間的近似度RC以及互連度RI；

其中，|G’_i|表示簇G’_i內數據點的個數；EC(G’_i)表示簇G’_i內所有邊的權重和；EC(G’_i，G’_j)表示連接兩個簇的所有邊的權重和；