李瀟潼 許左琳 馬榮通 龍琦
摘 ?要:聚類算法技術有多種,可以有效應在土木工程中進行運用。本文研究的是凝聚層次聚類算法在土木工程中的應用,分析它的優(yōu)缺點。
關鍵詞:凝聚層次;聚類算法;簇;土木工程
1 凝聚層次聚類算法含義
層次聚類,顧名思義就是要一層一層地進行聚類,可以自下而上地把小的簇合并聚集,也可以從上至下地將大的簇進行分割。自下而上地進行聚類稱為凝聚式層次聚類,自上而下地進行聚類稱為分裂式層次聚類。
2 凝聚層次聚類在土木工程中的應用
3凝聚式層次聚類的主要問題
(1)缺乏全局目標函數(shù)
凝聚層次聚類不能為全局優(yōu)化目標函數(shù),在每一步合并時僅僅局部地確定哪些簇應當合并。
(2)處理不同大小簇的能力,關于處理待合并的簇對的相對大小,有兩種方法解決:一是加權,就是不同簇中的點具有不同的權值;二是非加權,需要考慮每個簇的點數(shù)。
(3)合并決策
對于合并兩個簇,凝聚層次聚類算法可以使用所有點的對趨向于作出最優(yōu)局部決策。但是,一旦進行簇合并,就不能撤銷,這阻礙了局部最優(yōu)標準變成全局最優(yōu)標準的情況。
4優(yōu)點與缺點
層次聚類能產(chǎn)生較高質量的聚類;有些使用這種算法是因為基本應用需要層次結構。但就計算量和存儲需求而言,凝聚式層次聚類算法是昂貴的。
基本凝聚式層次聚類算法使用鄰近度矩陣,這需要存儲m2/2個鄰近度(假定鄰近度矩陣式對稱的),其中m是數(shù)據(jù)點的個數(shù)。記錄簇所需要的空間正比于簇的個數(shù)為m-1,不包括單點簇。因此總的空間復雜度為O(m2)。層次聚類所需要的總時間為O(m2logm)。
參考文獻
[1] ?姚玉欽 李金廣 河北大學學報(自然科學版)[D] 2009-4
[2] ?黃蕾 數(shù)據(jù)流環(huán)境下的聚類挖掘研究[D] 華中科技大學 2007
[3] ?李柯 基于用戶訪問矩陣的網(wǎng)頁推薦模型研究[D] 江蘇大學 2010