[發明專利]一種基于對稱非負矩陣分解的改進譜聚類及并行化方法

有效

• 申請號: 202010410767.7
• 申請日: 2020-05-15
• 公開（公告）號: CN111767941B
• 公開（公告）日: 2022-11-18
• 發明（設計）人: 姜加鳳;雷詠梅
• 申請（專利權）人: 上海大學
• 主分類號: G06K9/62
• 分類號: G06K9/62
• 代理公司: 上海上大專利事務所(普通合伙) 31205
• 代理人: 何文欣

本發明公開了一種基于對稱非負矩陣分解的改進譜聚類及并行化方法。通過單向循環多輪迭代的方法進行不同分區中樣本點間相似度的并行計算，并采用t近鄰的方法稀疏化相似度矩陣。通過交替方向乘子法來迭代求出與正交約束松弛的譜聚類目標函數等價的對稱非負矩陣分解的最優解，避免使用拉普拉斯矩陣進行SVD特征分解。利用改進的K?means算法對通過對稱非負矩陣分解得到的特征向量子集進行聚類。本發明對改進譜聚類算法的計算步驟基于Spark大數據計算框架進行了并行設計及實現，使得算法不僅在聚類效果上優于傳統算法，進一步解決了傳統譜聚類算法在大規模數據集中計算耗時過長甚至無法完成計算的問題。

技術領域

本發明提出了一種改進譜聚類及并行化方法，涉及機器學習、大數據聚類和并行計算領域。

背景技術

譜聚類算法基于譜圖理論，將聚類問題轉化為圖的最優劃分問題，由于其能夠實現對非凸等任意形狀的樣本空間的聚類、可有效避免局部最優解、并且可以應用于高維數據的聚類等優點，成為機器學習領域聚類算法中的研究熱點。然而，隨著大規模數據的普及，傳統譜聚類算法由于計算相似度矩陣時空間存儲代價大、特征分解的時間復雜度高，存在計算耗時過長甚至無法完成計算的問題，這在實際的大數據應用中是致命的，限制了其在很多領域上的應用。

近年來對于譜聚類算法的研究主要集中在兩方面。一方面，通過在算法的實現層面上進行優化，提升算法的執行效率。針對存儲相似度矩陣空間復雜度過高的問題，一類解決方法是使相似度矩陣中一些無關緊要的元素歸零，將矩陣稀疏化。另一類方法是按照行或列對相似性矩陣進行采樣，得到原始矩陣的低秩近似。

針對拉普拉斯矩陣特征分解時間復雜度高的問題，有研究者提出基于Spark平臺采用Lanczos分解方法將拉普拉斯矩陣分解成實對稱對角矩陣，再進行QR分解來提高算法的運行效率。對于最后的聚類方式，針對普遍使用的K-means聚類方法由于初始聚類中心的隨機選取，存在受離群點的影響大并且聚類結果差異大的問題，有研究者使用K-means++預采樣過程來確定初始聚類中心，但由于其聚類中心點選擇過程中的內在有序性，在擴展方面存在著性能方面的問題。

另一方面，隨著MPI、MapReduce并行計算模型的應用以及Hadoop、Spark等分布式并行框架的興起，實現算法的并行化是提高大數據分析算法運行效率的不錯的選擇。Song等人利用MPI并行環境設計出并行譜聚類算法并使用大量的數據進行聚類實驗，解決了傳統的譜聚類算法中存在的計算性能瓶頸的問題，但存在通信開銷較大、對控制的要求比較高的缺點。Fei Gao等人提出了一種分布式近似譜聚類算法。這種算法同樣也是基于MapReduce編程模型進行設計，并在Hadoop平臺之上實現。與MPI和Hadoop系統相比，當前應用廣泛的Spark并行計算框架具有良好的優越性。MPI編程模型比較低層次，需要用戶理解處理數據流機制和底層架構。Spark提供抽象化編程模型，用戶只需要專注于算法的邏輯實現，并不用關心節點之間的通信、失效和恢復等問題。Hadoop只基于map和reduce這兩種抽象實現為用戶提供高層次的MapReduce編程模型，而map和reduce操作會產生很多中間數據，頻繁的磁盤I/O讀寫限制了任務的高效運行。Spark編程模型將所有數據都抽象成具有豐富的并行操作算子的RDD，基于內存進行RDD的迭代計算，減少了中間結果在磁盤上的讀寫操作，優化了迭代算法的工作負載。

發明內容

為解決傳統譜聚類算法由于相似度矩陣計算和拉普拉斯矩陣特征分解空間復雜度、時間復雜度高而無法應用于大規模數據集的問題，本發明提出了一種基于對稱非負矩陣分解的改進譜聚類及并行化方法。對改進譜聚類算法的計算步驟基于Spark大數據計算框架進行了并行設計及實現，使得算法不僅在聚類效果上優于傳統算法，進一步解決了傳統譜聚類算法在大規模數據集中計算耗時過長甚至無法完成計算的問題。

本發明采用如下技術方案：

基于對稱非負矩陣分解的改進譜聚類及并行化方法，包括以下步驟：