面向大規(guī)模數(shù)據(jù)集的譜聚類方法研究.pdf

1、隨著科學(xué)技術(shù)的發(fā)展，人類收集數(shù)據(jù)的能力大幅度提高，各個行業(yè)都已經(jīng)或正在積累大量的數(shù)據(jù)，人們需要對這些數(shù)據(jù)進行分析推理獲取有意義的信息，而聚類分析研究上取得好的成果，對于數(shù)據(jù)分析推理具有重要的意義。譜聚類方法是眾多聚類分析方法中的一支獨秀，是聚類分析相關(guān)領(lǐng)域的一個研究熱點。譜聚類方法能在任意形狀的樣本空間上聚類，且收斂于全局最優(yōu)解。譜聚類方法能夠揭示數(shù)據(jù)的低維的非線性特性，可以用于各種對象的降維，在降維的同時也將這些對象嵌入到歐式空間，所

2、以譜聚類方法可以執(zhí)行各種數(shù)據(jù)的聚類。但是，譜聚類方法的計算復(fù)雜度過高，故譜聚類方法的諸多優(yōu)點只適合小數(shù)據(jù)集，面向大規(guī)模數(shù)據(jù)集的譜聚類方法研究并不多。當(dāng)今，很多行業(yè)積累的數(shù)據(jù)量都非常龐大，為了獲取大規(guī)模數(shù)據(jù)集更好的聚類分析成果，使得數(shù)據(jù)分析推理更精確、更有效，研究面向大規(guī)模數(shù)據(jù)集的譜聚類方法是必要的。
　　首先，針對大規(guī)模數(shù)值型數(shù)據(jù)集的譜聚類，其Laplacian矩陣特征分解的時間復(fù)雜度及空間復(fù)雜度過高，受增量協(xié)方差無關(guān)方法計算主成

3、分思想的啟發(fā)，提出一種快速計算Laplacian矩陣的前k個最小特征向量的方法。該方法構(gòu)建兩個對稱半正定矩陣，使其前k個最大特征向量與Laplacian矩陣的前k個最小特征向量相同，通過循環(huán)輸入構(gòu)建矩陣的列向量，增量方法計算出Laplacian矩陣的前k個最小特征向量。該方法所用空間為n量級，特征分解時間復(fù)雜度為線性時間，有效解決了譜聚類中Laplacian矩陣特征分解的問題。實驗證明該方法能夠快速特征分解Laplacian矩陣。

4、>　　其次，針對這樣一類大規(guī)模混合型數(shù)據(jù)集，隨著時間的推移，樣本數(shù)量呈爆炸式增長，而樣本的屬性空間變化則逐漸趨于固定范圍，提出一種基于準超圖像映射的譜聚類方法，有效解決了這類混合型數(shù)據(jù)集的劃分問題。量化數(shù)據(jù)集的每個屬性，由每個屬性的量化份數(shù)確定準超圖像的每個維的尺寸，根據(jù)量化公式將大規(guī)模數(shù)據(jù)集映射到準超圖像，并確定像素相似度函數(shù)。使用譜聚類方法劃分準超圖像，則能夠獲得數(shù)據(jù)集的全局分布情況。數(shù)據(jù)集到準超圖像的映射計算是線性的，準超圖像的像

5、素規(guī)模已經(jīng)很小，采用譜聚類所用時間也會很少，而通過映射極大地減小了數(shù)據(jù)的存儲空間，故該方法滿足時間和存儲的要求。實驗結(jié)果表明，該方法能夠迅速處理此類大規(guī)?；旌闲蛿?shù)據(jù)集的劃分問題，同時獲得數(shù)據(jù)的全局分布情況。
　　再次，針對大規(guī)模異構(gòu)信息網(wǎng)絡(luò)的結(jié)構(gòu)特點，利用異構(gòu)信息網(wǎng)絡(luò)的稀疏性，提出一種基于嵌入技術(shù)的異構(gòu)信息網(wǎng)絡(luò)的快速譜聚類方法。從相容的角度將異構(gòu)信息網(wǎng)絡(luò)轉(zhuǎn)化為若干個相容的二部圖，使用隨機映射和一種線性時間求解程序快速計算出每個二部

6、圖的近似commute time嵌入，每個嵌入都存在一個子集指示目標數(shù)據(jù)集，也就是目標數(shù)據(jù)集同時被多個指示子集所指示。使用這些指示子集構(gòu)建一個通用的聚類模型，將所有指示子集的類設(shè)置標號，通過計算指示同一目標對象的指示數(shù)據(jù)與標號相同類的中心點的加權(quán)距離總和，同時劃分所有的指示子集，從而快速獲得通用模型的極小值。實驗結(jié)果表明，該方法聚類準確率高，聚類速度快，能夠有效處理異構(gòu)信息網(wǎng)絡(luò)的劃分問題。
　　最后，針對動態(tài)異構(gòu)信息網(wǎng)絡(luò)劃分問題，

7、利用異構(gòu)信息網(wǎng)絡(luò)的稀疏性，提出一種解決星型模式的動態(tài)異構(gòu)信息網(wǎng)絡(luò)的演化譜聚類方法。從相容的角度將異構(gòu)信息網(wǎng)絡(luò)轉(zhuǎn)化為若干個相容的二部圖。時間平滑每個二部圖結(jié)點間的關(guān)系，使得時間平滑二部圖能夠充分表達某時刻及先前時間結(jié)點間的關(guān)系。稀疏化時間平滑二部圖，由隨機映射和一種線性時間的求解程序快速計算出每個時間平滑二部圖的近似commute time嵌入，獲得指示目標數(shù)據(jù)集的多個指示子集。計算指示同一個目標對象的所有指示數(shù)據(jù)與標號相同類的中心點的加