譜聚類(lèi)算法的改進(jìn).pdf

1、當(dāng)前，聚類(lèi)分析是國(guó)際數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)領(lǐng)域中的研究熱點(diǎn)之一。作為一種較新的聚類(lèi)分析方法的譜聚類(lèi)方法具有傳統(tǒng)聚類(lèi)方法不具有的許多優(yōu)點(diǎn)，如譜聚類(lèi)方法簡(jiǎn)單直觀、容易實(shí)現(xiàn)、能得到全局最優(yōu)解和能對(duì)任意形狀的數(shù)據(jù)空間進(jìn)行聚類(lèi)分析等等。
　　傳統(tǒng)譜聚類(lèi)方法以關(guān)聯(lián)矩陣為基礎(chǔ)，構(gòu)建 Laplacian矩陣，從而計(jì)算出矩陣的特征值和特征向量，接下來(lái)根據(jù)某種規(guī)則選取一個(gè)或多個(gè)特征向量進(jìn)行聚類(lèi)分析。然而，上述過(guò)程至少存在兩個(gè)亟需解決的問(wèn)題，一是，如何設(shè)置

2、構(gòu)造關(guān)聯(lián)矩陣所需的尺度參數(shù)；二是，直接對(duì)Laplacian矩陣進(jìn)行特征值分解的計(jì)算復(fù)雜度高達(dá)O(n3)。這兩個(gè)問(wèn)題制約了傳統(tǒng)譜聚類(lèi)方法在實(shí)際中的應(yīng)用。為了改進(jìn)譜聚類(lèi)算法，本文作了如下工作：
　?。?）研究表明，低秩逼近技術(shù)和采樣技術(shù)一樣可以解決矩陣的特征值分解的計(jì)算復(fù)雜度高的問(wèn)題，而且低秩逼近技術(shù)的逼近誤差要低于采樣技術(shù)。為此，本文將低秩逼近技術(shù)與傳統(tǒng)譜聚類(lèi)算法結(jié)合起來(lái)提出了一個(gè)新的譜聚類(lèi)算法，命名為基于低秩逼近技術(shù)的譜聚類(lèi)算法。

3、實(shí)驗(yàn)結(jié)果表明，新的算法能夠在降低算法的逼近誤差的同時(shí)，取得較高的執(zhí)行效率和較好的聚類(lèi)效果。
　　（2）雖然低秩逼近技術(shù)和采樣技術(shù)可以大大的降低譜聚類(lèi)算法的計(jì)算復(fù)雜度，但是二者均基于抽樣技術(shù)。眾所周知，在抽樣技術(shù)中無(wú)論樣本點(diǎn)是被隨機(jī)抽取或是采用其它較復(fù)雜的方法抽取，這些樣本點(diǎn)均不能夠完全地代表整個(gè)數(shù)據(jù)集合且不能正確地捕獲到整個(gè)數(shù)據(jù)集合的幾何結(jié)構(gòu)。因而，需要引入不涉及采樣技術(shù)的其它手段來(lái)獲得譜聚類(lèi)的特征空間。為此，本文將通勤時(shí)間與傳統(tǒng)