土木工程中的凝聚層次聚類算法應(yīng)用研究

李瀟潼 許左琳 馬榮通 龍琦

摘 ?要：聚類算法技術(shù)有多種，可以有效應(yīng)在土木工程中進行運用。本文研究的是凝聚層次聚類算法在土木工程中的應(yīng)用，分析它的優(yōu)缺點。

關(guān)鍵詞：凝聚層次;聚類算法;簇;土木工程

1 凝聚層次聚類算法含義

層次聚類，顧名思義就是要一層一層地進行聚類，可以自下而上地把小的簇合并聚集，也可以從上至下地將大的簇進行分割。自下而上地進行聚類稱為凝聚式層次聚類，自上而下地進行聚類稱為分裂式層次聚類。

2 凝聚層次聚類在土木工程中的應(yīng)用

3凝聚式層次聚類的主要問題

（1）缺乏全局目標(biāo)函數(shù)

凝聚層次聚類不能為全局優(yōu)化目標(biāo)函數(shù)，在每一步合并時僅僅局部地確定哪些簇應(yīng)當(dāng)合并。

（2）處理不同大小簇的能力，關(guān)于處理待合并的簇對的相對大小，有兩種方法解決：一是加權(quán)，就是不同簇中的點具有不同的權(quán)值;二是非加權(quán)，需要考慮每個簇的點數(shù)。

（3）合并決策

對于合并兩個簇，凝聚層次聚類算法可以使用所有點的對趨向于作出最優(yōu)局部決策。但是，一旦進行簇合并，就不能撤銷，這阻礙了局部最優(yōu)標(biāo)準變成全局最優(yōu)標(biāo)準的情況。

4優(yōu)點與缺點

層次聚類能產(chǎn)生較高質(zhì)量的聚類;有些使用這種算法是因為基本應(yīng)用需要層次結(jié)構(gòu)。但就計算量和存儲需求而言，凝聚式層次聚類算法是昂貴的。

基本凝聚式層次聚類算法使用鄰近度矩陣，這需要存儲m2/2個鄰近度（假定鄰近度矩陣式對稱的），其中m是數(shù)據(jù)點的個數(shù)。記錄簇所需要的空間正比于簇的個數(shù)為m-1，不包括單點簇。因此總的空間復(fù)雜度為O（m2）。層次聚類所需要的總時間為O（m2logm）。

參考文獻

[1] ?姚玉欽 李金廣 河北大學(xué)學(xué)報（自然科學(xué)版）[D] 2009-4

[2] ?黃蕾 數(shù)據(jù)流環(huán)境下的聚類挖掘研究[D] 華中科技大學(xué) 2007

[3] ?李柯 基于用戶訪問矩陣的網(wǎng)頁推薦模型研究[D] 江蘇大學(xué) 2010