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

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

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

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

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