[發(fā)明專利]一種對關系網絡圖中的節(jié)點進行聚類的方法及裝置

在審

• 申請?zhí)枺?/td>: 201910060474.8
• 申請日: 2019-01-22
• 公開（公告）號: CN110032603A
• 公開（公告）日: 2019-07-19
• 發(fā)明（設計）人: 崔卿
• 申請（專利權）人: 阿里巴巴集團控股有限公司
• 主分類號: G06F16/28
• 分類號: G06F16/28
• 代理公司: 北京億騰知識產權代理事務所(普通合伙) 11309
• 代理人: 陳霽;周良玉

本說明書實施例提供一種對關系網絡圖中的節(jié)點進行聚類的方法及裝置，所述關系網絡圖包括多個節(jié)點，所述方法包括：首先獲取所述關系網絡圖的鄰接信息，所述鄰接信息記錄了各個節(jié)點之間是否具有連接邊，以及連接邊的邊長；然后根據所述鄰接信息，確定以各個節(jié)點為中心節(jié)點的各個鄰居節(jié)點集合，以及各個鄰居節(jié)點集合中節(jié)點之間的最短連接邊；再確定各個最短連接邊中邊長小于預設閾值的至少一個第一邊；對于各個第一邊，將第一邊連接的兩個節(jié)點聚為同一類簇，并將所述兩個節(jié)點進行合并；并且根據合并之后的節(jié)點，更新所述鄰接信息，更新后的所述鄰接信息用于再次進行合并。

技術領域

本說明書一個或多個實施例涉及計算機信息處理領域，尤其涉及對關系網絡圖中的節(jié)點進行聚類的方法及裝置。

背景技術

在進行數據分析，特別是大數據分析時，聚類是一種常用的分析方法。聚類是指將物理或抽象對象的集合分成由類似的對象組成的多個類的過程。聚類可以把相似的對象劃分到一個類，使得同一個類內的對象比較相似，而不同類之間的對象差異較大。

隨著智能手機的普及，用戶日常生活產生的數據量迅速增加，這給聚類算法的性能帶來了挑戰(zhàn)。因此，需要一種能夠高效地對大規(guī)模數據進行聚類的方法。

發(fā)明內容

本說明書一個或多個實施例描述了一種對關系網絡圖中的節(jié)點進行聚類的方法，可以在一輪迭代中同時合并多對兩兩節(jié)點，提高了計算效率，可高效完成大規(guī)模數據以及超大規(guī)模數據的聚類。

根據第一方面，提供一種對關系網絡圖中的節(jié)點進行聚類的方法，所述關系網絡圖包括多個節(jié)點和多個連接邊，所述方法包括：

獲取所述關系網絡圖的鄰接信息，所述鄰接信息記錄了各個節(jié)點之間是否具有連接邊，以及連接邊的邊長；

根據所述鄰接信息，確定以各個節(jié)點為中心節(jié)點的各個鄰居節(jié)點集合，以及各個鄰居節(jié)點集合中節(jié)點之間的最短連接邊；其中，所述鄰居節(jié)點集合包括對應的中心節(jié)點，以及與該對應的中心節(jié)點的連接階數不超過預定階數k的鄰居節(jié)點，k為大于1的整數；

確定各個最短連接邊中邊長小于預設閾值的至少一個第一邊；

對于各個第一邊，將第一邊連接的兩個節(jié)點聚為同一類簇，并將所述兩個節(jié)點進行合并；

根據合并之后的節(jié)點，更新所述鄰接信息，更新后的所述鄰接信息用于再次進行節(jié)點合并。

在一個實施例中，所述關系網絡圖中的節(jié)點對應于樣本，所述連接邊的邊長對應于樣本之間的相似度或關聯緊密度。

在一個實施例中，所述獲取所述關系網絡圖的鄰接信息包括：

獲取所述關系網絡圖的鄰接矩陣，通過所述鄰接矩陣確定相互連接的節(jié)點；

獲取各個節(jié)點的嵌入向量；

根據各個節(jié)點的嵌入向量計算所述相互連接的節(jié)點之間的連接邊的邊長。

在一個實施例中，所述獲取所述關系網絡圖的鄰接信息包括：

獲取所述關系網絡圖的距離矩陣，所述距離矩陣用作所述鄰接信息。

在一個實施例中，所述確定鄰居節(jié)點集合包括：

遍歷所述關系網絡圖的鄰接信息，以得到各個節(jié)點的1階鄰居節(jié)點；

對于各個節(jié)點，將其n階鄰居節(jié)點的1階鄰居節(jié)點中的第一鄰居作為各個節(jié)點的n+1階鄰居節(jié)點，添加到該節(jié)點對應的鄰居節(jié)點集合中，直到n達到k-1；其中，第一鄰居為各個節(jié)點的n階鄰居的1階鄰居中排除了各個節(jié)點的n-1階鄰居后的鄰居節(jié)點。

在一個實施例中，所述至少一個第一邊的數目為1時，在更新所述鄰接信息后，所述方法還包括：

根據更新后的鄰接信息，確定更新后的關系網絡圖中的最短邊；