基于Spark平臺的聚類算法的優(yōu)化與實現(xiàn).pdf

1、現(xiàn)代信息社會中，隨著數(shù)據(jù)量的增大，對大規(guī)模數(shù)據(jù)集進行聚類分析并生成有用信息的需求也在不斷增加。如今對于大規(guī)模數(shù)據(jù)的聚類分析主要有以下難點:第一，聚類對機器內(nèi)存容量的需求超出了單一計算機的硬件能力;第二，聚類分析時間過長，效率無法得到提高。于是，對大規(guī)模數(shù)據(jù)上聚類算法的優(yōu)化，可以歸結(jié)為對數(shù)據(jù)規(guī)模的優(yōu)化以及對算法在分布式平臺上的優(yōu)化。近年來，分布式計算平臺Spark得到了廣泛關(guān)注，Spark可以對于大規(guī)模數(shù)據(jù)進行內(nèi)存上的迭代計算，使計算變得

2、更加迅速，有著其它分布式平臺無法比擬的優(yōu)勢。
　　本文主要研究了基于Spark平臺上特定的聚類分析算法的優(yōu)化和實現(xiàn);與此同時，對于聚類數(shù)據(jù)進行一定的預(yù)處理，可以在其不改變聚類效果的前提下減少數(shù)據(jù)規(guī)模，提高運行效率。論文選取了近年來被提出且被廣泛應(yīng)用的聚類算法:近鄰傳播聚類與譜聚類作為優(yōu)化對象。論文的主要工作如下:
　　(1)針對聚類算法的數(shù)據(jù)規(guī)模問題，本文通過引入一種新的參數(shù):閾值，對原始數(shù)據(jù)進行預(yù)處理。該方法根據(jù)聚類算法需

3、要生成的類簇數(shù)，針對數(shù)據(jù)在空間中的密度計算出一定的閡值，在生成相似度矩陣時將低于該閾值的相似度數(shù)據(jù)刪除，保留有效的相似度數(shù)據(jù)，從而優(yōu)化數(shù)據(jù)結(jié)構(gòu)并生成稀疏矩陣，在保證聚類效果不發(fā)生變化的同時減小數(shù)據(jù)規(guī)模。
　　(2)對于近鄰傳播聚類算法，本文提出了一種基于Spark平臺上的分塊式的近鄰傳播聚類算法。通過在Spark平臺使用二維索引的數(shù)據(jù)結(jié)構(gòu)按照行進行分塊并分配到每臺機器中，在算法迭代中按照行分塊計算歸屬度矩陣，并將生成結(jié)果按列存儲;

4、再按照列分塊計算吸引度矩陣，并將生成結(jié)果按行存儲，不斷迭代最終生成聚類結(jié)果。從而實現(xiàn)算法在Spark平臺上數(shù)據(jù)的并行化，減少機器之間的數(shù)據(jù)傳輸，提高聚類算法的效率。
　　(3)對于譜聚類算法，本文提出了一種基于Spark平臺上并行Lanczos分解的的譜聚類算法。首先引入一種并行的Lanczos分解方法對原始拉普拉斯矩陣分解生成三元對角矩陣，降低了分解特征值計算的時間復(fù)雜度，該矩陣能夠保留原矩陣的特征且很容易使用QR分解求解出其特