[發明專利]一種基于GraphX的分布式冪迭代聚類方法和裝置

有效

• 申請號: 201610402954.4
• 申請日: 2016-06-08
• 公開（公告）號: CN107480685B
• 公開（公告）日: 2021-02-23
• 發明（設計）人: 徐曉燕;趙軍;臧天寧;李高超;周淵
• 申請（專利權）人: 國家計算機網絡與信息安全管理中心
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 工業和信息化部電子專利中心 11010
• 代理人: 田衛平

本發明公開了一種基于GraphX的分布式冪迭代聚類方法和裝置。該方法包括：獲取分布式存儲的多個數據；對所述多個數據分別進行數據清洗，得到多個清洗數據；基于所述多個清洗數據中兩兩之間的相似度，構建親和矩陣；基于GraphX，利用設置的隨機初始向量對所述親和矩陣進行迭代處理；利用KMeans++算法，對迭代向量進行聚類處理，并根據處理結果得到所述多個清洗數據的聚類結果。本發明有效地解決了基于圖的聚類算法可擴展性不強、計算復雜度高的問題。

技術領域

本發明涉及數據處理技術領域，特別是涉及一種基于GraphX的分布式冪迭代聚類方法和裝置。

背景技術

冪迭代聚類是在譜聚類的基礎上演化出的一種聚類算法。冪迭代聚類建立在圖論中的譜圖理論基礎上，本質上是將聚類問題轉化為圖的最優劃分問題。與經典的圖聚類選取相似矩陣的幾個特征向量構成低維子空間進行聚類不同，冪迭代聚類對所有的特征向量進行線性組合，對得到的一維子空間進行聚類。所以，冪迭代聚類的效果一般比譜聚類要好。冪迭代聚類的核心計算是矩陣與向量的乘法計算，不需要計算矩陣的特征值和特征向量。所以，冪迭代聚類比譜聚類更加簡單、快速。為了讓該算法應用在大規模數據分析中，研究人員基于多點接口(Multi Point Interface，MPI)并行實現了冪迭代聚類，但仍存在節點失效的問題。還有基于Hadoop MapReduce的冪迭代聚類研究，但由于MapReduce計算框架每次shuffle都要讀寫磁盤，對于需要進行多次迭代的算法存在性能瓶頸。

因此，在現有技術中，基于圖的聚類算法可擴展性不強、計算復雜度高。

發明內容

本發明提供一種基于GraphX的分布式冪迭代聚類方法和裝置，用以克服現有的大多數基于圖的聚類可擴展性不強、計算復雜度高的問題。

針對上述技術問題，本發明是通過以下技術方案來解決的。

本發明提供了一種基于GraphX的分布式冪迭代聚類方法，包括：獲取分布式存儲的多個數據；對所述多個數據分別進行數據清洗，得到多個清洗數據；基于所述多個清洗數據中兩兩之間的相似度，構建親和矩陣；基于GraphX，利用設置的隨機初始向量對所述親和矩陣進行迭代處理；利用KMeans++算法，對迭代向量進行聚類處理，并根據處理結果得到所述多個清洗數據的聚類結果。

其中，所述基于所述多個清洗數據中兩兩之間的相似度，構建親和矩陣，包括：在n個清洗數據中，利用預設的相似度算法sim，計算第i個清洗數據x_i和第j個清洗數據x_j之間的相似度；將計算得到的相似度sim(x_i,x_j)作為n維親和矩陣的第i行、第j列的元素A_ij；其中，1≤i≤n，1≤j≤n，n＞0。

其中，所述利用設置的隨機初始向量對所述親和矩陣進行迭代處理，包括：對所述親和矩陣進行歸一化處理；根據歸一化后的所述親和矩陣，設置隨機初始向量；利用歸一化后的所述親和矩陣和所述隨機初始向量，在GraphX組件中構建圖，并對所述圖進行多次迭代，直到迭代獲得的收斂加速度小于預設的收斂閾值為止。

其中，所述根據歸一化后的所述親和矩陣，設置隨機初始向量，包括：對所述親和矩陣按行進行歸一化處理；利用行歸一化后的親和矩陣初始化預設的初始向量，得到隨機初始向量。

其中，利用KMeans++算法，對迭代向量進行聚類處理，并根據處理結果得到所述多個清洗數據的聚類結果，包括：利用KMeans++算法，對最后一次迭代得到的迭代向量進行聚類處理，得到所述最后一次迭代得到的迭代向量的聚類處理結果；根據所述聚類處理結果，確定所述多個清洗數據的聚類結果；其中，所述最后一次迭代得到的迭代向量中的元素和所述多個清洗數據組成的清洗數據集中的清洗數據一一對應。