[發(fā)明專利]一種數(shù)據(jù)關(guān)聯(lián)性的確定方法

在審

• 申請(qǐng)?zhí)枺?/td>: 201610261025.6
• 申請(qǐng)日: 2016-04-22
• 公開（公告）號(hào): CN107305639A
• 公開（公告）日: 2017-10-31
• 發(fā)明（設(shè)計(jì)）人: 楊連群;溫晉英;劉樹發(fā)
• 申請(qǐng)（專利權(quán)）人: 楊連群
• 主分類號(hào): G06K9/62
• 分類號(hào): G06K9/62
• 代理公司: 北京華睿卓成知識(shí)產(chǎn)權(quán)代理事務(wù)所(普通合伙)11436
• 代理人: 程淼

技術(shù)領(lǐng)域

本發(fā)明涉及信息技術(shù)領(lǐng)域，具體涉及一種數(shù)據(jù)關(guān)聯(lián)性的確定方法。

背景技術(shù)

聚類分析是根據(jù)對(duì)象之間的相似度將對(duì)象劃分成不同的簇，使得同一簇內(nèi)的對(duì)象相似度最大化，而不同簇之間的對(duì)象相似度最小化。

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

發(fā)明內(nèi)容

本發(fā)明的主要目的在于克服上述現(xiàn)有技術(shù)的缺陷，提供了一種數(shù)據(jù)關(guān)聯(lián)性的確定方法，以解決現(xiàn)有技術(shù)中數(shù)據(jù)關(guān)聯(lián)性確定過程中速度較慢，聚類質(zhì)量不夠高的缺陷，在能夠提供高質(zhì)量的聚類結(jié)果的同時(shí)，保證了較快的處理速度。

本發(fā)明一方面提供一種數(shù)據(jù)關(guān)聯(lián)性的確定方法，包括以下步驟：

第一步，對(duì)圖G的數(shù)據(jù)進(jìn)行聚類，獲得N個(gè)簇，G‘＝{G’_i}，i＝1，2，…，N；

第二步，對(duì)獲得的所述N個(gè)簇，進(jìn)行歸并，生成K個(gè)簇，K＜N；

其中，第一步進(jìn)一步包括以下步驟：

第1.1步，計(jì)算圖G的鄰接矩陣A；

第1.2步，對(duì)每個(gè)節(jié)點(diǎn)添加自環(huán)，即A′：＝A+I,；其中，I為對(duì)角線元素為1的對(duì)角矩陣；

第1.3步，計(jì)算轉(zhuǎn)移概率矩陣M：

M(i,j)代表節(jié)點(diǎn)v_i到節(jié)點(diǎn)v_j的轉(zhuǎn)移概率；

第1.4步，M進(jìn)行擴(kuò)展參數(shù)為e的擴(kuò)展操作，其中，e為大于1的正整數(shù)，得到矩陣M1；

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

第1.5步，對(duì)M1進(jìn)行膨脹參數(shù)為r的膨脹操作，膨脹參數(shù)r為正實(shí)數(shù)，得到矩陣M2；

重復(fù)執(zhí)行步驟1.4、步驟1.5，直至矩陣M2不發(fā)生變化，此時(shí)生成穩(wěn)定的轉(zhuǎn)移矩陣M2；

第1.7步，對(duì)穩(wěn)定的轉(zhuǎn)移矩陣M2并進(jìn)行歸類，獲得N個(gè)簇。

可選的，其中所述第1.7步對(duì)穩(wěn)定的轉(zhuǎn)移矩陣M2并進(jìn)行歸類具體為，對(duì)于M2中的每一行，將吸引節(jié)點(diǎn)與被吸引節(jié)點(diǎn)歸為一類。

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

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

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

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

其中，|G’_i|表示簇G’_i內(nèi)數(shù)據(jù)點(diǎn)的個(gè)數(shù)；EC(G’_i)表示簇G’_i內(nèi)所有邊的權(quán)重和；EC(G’_i，G’_j)表示連接兩個(gè)簇的所有邊的權(quán)重和；

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

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

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

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

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

其中，|G’_i|表示簇G’_i內(nèi)數(shù)據(jù)點(diǎn)的個(gè)數(shù)；EC(G’_i)表示簇G’_i內(nèi)所有邊的權(quán)重和；EC(G’_i，G’_j)表示連接兩個(gè)簇的所有邊的權(quán)重和；