譜劃分算法中特征向量選取方法的研究.pdf

1、隨著信息技術(shù)的急速發(fā)展，數(shù)據(jù)的規(guī)模呈爆炸式增長。作為數(shù)據(jù)分析和知識發(fā)現(xiàn)中廣泛運用的技術(shù)，劃分方法在很多領(lǐng)域已經(jīng)得到了廣泛的關(guān)注。圖作為一種基本的數(shù)據(jù)結(jié)構(gòu)在復雜網(wǎng)絡(luò)及其相互作用的建模中變得越來越重要。為了進一步分析和處理海量數(shù)據(jù)中的內(nèi)在聯(lián)系及意義，基于圖的劃分問題已經(jīng)成為數(shù)據(jù)挖掘領(lǐng)域中一個活躍和重要的課題。
　　 圖的劃分是一個NP 完全問題，雖然人們已經(jīng)探索出一些有效的算法，但隨著數(shù)據(jù)規(guī)模的不斷擴大和新問題的不斷涌現(xiàn)，很多算法已

2、無法適應(yīng)問題的需要。近幾年譜劃分已經(jīng)成為最流行的劃分算法之一，與傳統(tǒng)的算法相比，它能在任意的樣本空間上進行劃分，且收斂于全局最優(yōu)解，是圖論和譜分解理論在劃分領(lǐng)域上的一種很好的結(jié)合。如今很多關(guān)于這方面的新算法和文獻已經(jīng)發(fā)表，經(jīng)研究發(fā)現(xiàn)，這些不同方法之間的差別主要在特征向量的選擇上。本文主要研究譜劃分算法中特征向量的選取問題，從而說明對于具有不同規(guī)模和結(jié)構(gòu)的圖，應(yīng)該如何有效的選擇合適的特征向量進行劃分。我們通過三個方法來討論這個問題：(1)