快速譜聚類算法的研究與應(yīng)用.pdf

1、聚類分析作為一種高效的數(shù)據(jù)分析工具，目前已被廣泛應(yīng)用于數(shù)據(jù)壓縮、計算機視覺、圖像分割、文本聚類、語音識別、生物特征識別和數(shù)據(jù)異常檢測等領(lǐng)域。在傳統(tǒng)的聚類算法中，具有較低計算復雜度的K-means算法和EM算法在大規(guī)模數(shù)據(jù)樣本的聚類問題上得到了廣泛應(yīng)用。然而，這些算法都是基于梯度的算法，當樣本集空間結(jié)構(gòu)非凸時，算法就會陷入局部最優(yōu)從而使得算法的聚類質(zhì)量無法得到保證。
　　 譜聚類算法對數(shù)據(jù)集的空間結(jié)構(gòu)不做強的假設(shè)，能在任意結(jié)構(gòu)分布

2、的樣本空間上聚類且收斂于全局最優(yōu)解。它將復雜的聚類問題轉(zhuǎn)化為權(quán)矩陣的特征值分解問題，使得算法簡單直觀且易于實現(xiàn)。但是譜聚類算法本身也存在較多不足，最為根本的是譜聚類算法建立在相似度矩陣之上，而相似度矩陣的構(gòu)造涉及到多參數(shù)的精確設(shè)置問題，已有的研究表明，譜聚類算法對相似度矩陣異常敏感，而對這些參數(shù)的精確設(shè)置目前仍缺少相應(yīng)的理論指導；此外，譜聚類算法在處理大規(guī)模樣本聚類問題時，其計算復雜度高達O(n3)，存儲復雜度也高達O(n2)，如此高昂

3、的計算代價和存儲需求限制了譜聚類算法在大規(guī)模聚類問題上的應(yīng)用。
　　 本文主要針對上述譜聚類存在的問題進行了研究，利用余弦相似度取代傳統(tǒng)譜聚類算法中的高斯核相似度，避免了相似度圖中參數(shù)的精確設(shè)置問題。在此基礎(chǔ)上，本文針對譜聚類算法的圖像分割和文本聚類問題上存在的高計算復雜度和巨大內(nèi)存需求問題展開研究和討論。在此過程中，本文的創(chuàng)新性成果主要包括以下幾方面：
　　 (1)針對譜聚類在解決圖像分割問題上的高計算復雜度問題和存儲

4、復雜度問題，以及傳統(tǒng)譜聚類算法對參數(shù)精確設(shè)置的要求，本文將余弦相似度引入到圖像分割問題中，基于Nystrom逼近的方法提出了一種快速譜聚類算法NAFSCA。該算法采用Nvstrom逼近的策略，避免了直接計算相似度矩陣W以及直接對權(quán)矩陣W的特征值分解問題，極大的降低了算法的計算復雜度和存儲需求。此外，在計算相似度矩陣的過程中采用了余弦相似度，由于無需進行較為耗時的指數(shù)運算和參數(shù)設(shè)置問題，使得算法的效率得到極大的提高。對比實驗結(jié)果表明，NA

5、FSCA算法比K-means算法等圖像分割算法更加優(yōu)越。
　　 (2)譜聚類算法在解決圖像分割問題時，其權(quán)矩陣異常龐大，針對權(quán)矩陣的計算、存儲和特征值分解上的計算代價高、內(nèi)存消耗大的問題，本文結(jié)合圖像數(shù)據(jù)為窄矩陣的特點，采用矩陣變換的方法，將龐大權(quán)矩陣的特征值分解問題近似轉(zhuǎn)化為小矩陣的特征值分解問題實現(xiàn)間接近似求解，由此提出了一種基于快速譜聚類的圖像分割算法MTFSCA。對比實驗結(jié)果表明，本文的基于矩陣變換方法保證圖像分割質(zhì)量無

6、明顯損失的的情況下，極大的降低了譜聚類算法的計算復雜度和存儲復雜度，算法效率得到明顯提高。
　　 (3)譜聚類算法為解決文本聚類集成問題提供了一種思路，由于K-means算法對初始點的敏感性，會使得聚類集成譜算法的聚類結(jié)果不穩(wěn)定。針對該問題，本文引入了近鄰傳播聚類思想，提出了一種新的的聚類集成譜算法APCESA。該算法先由聚類集成和譜分解得到空間結(jié)構(gòu)相對簡單的文本低維嵌入，然后通過近鄰傳播算法得到最終的聚類結(jié)果，有效克服了由于K