基于MPI并行編程的譜聚類算法

　　譜聚類算法由于其可識別非凸數(shù)據(jù)分布、可有效避免局部最優(yōu)解、不受數(shù)據(jù)點維數(shù)限制等優(yōu)點，在許多領(lǐng)域得到廣泛應(yīng)用。然而，隨著數(shù)據(jù)量的增大和數(shù)據(jù)維數(shù)的增多，在保證聚類準(zhǔn)確性的前提下，盡可能降低計算時間將變得非常必要。此外，影響譜聚類算法聚類質(zhì)量的因素除數(shù)據(jù)集本身外，還與所采用的求解距離矩陣的方法、相似性矩陣的尺度參數(shù)、Laplacian矩陣形式等多種因素相關(guān)。針對以上問題，首先對于大規(guī)模數(shù)據(jù)問題，將MPI并行編程模型應(yīng)用于譜聚類算法；然后利用￡最近鄰方法對譜聚類算法中較大維數(shù)的Laplacian矩陣進(jìn)行近似轉(zhuǎn)化，同時用局部尺度（Local Scaling）參數(shù)對算法中的尺度參數(shù)進(jìn)行自動調(diào)節(jié)。基于上述分析，提出了一種譜聚類并行實現(xiàn)算法，即稀疏化局部尺度并行譜聚類算法SLSPSC，并在四個數(shù)據(jù)集上進(jìn)行了測試，與現(xiàn)有的并行譜聚類算法PSC在運(yùn)行時間和聚類質(zhì)量兩方面做了比較分析。實驗結(jié)果顯示，該算法降低了求解Laplacian矩陣的總時間，同時部分?jǐn)?shù)據(jù)集聚類質(zhì)量得到較大提高。