高層結(jié)構(gòu)方案設(shè)計(jì)的K-Means 聚類分析法

張世海 張世忠 段慧杰

(南陽(yáng)理工學(xué)院，南陽(yáng) 473004)

1 引言

實(shí)際工程中大部分高層建筑的結(jié)構(gòu)方案設(shè)計(jì)都是在已有相似工程實(shí)例結(jié)構(gòu)方案基礎(chǔ)上的整合和改進(jìn)，若干相似實(shí)例的快速獲取是高質(zhì)與高效進(jìn)行結(jié)構(gòu)方案設(shè)計(jì)的基礎(chǔ)和關(guān)鍵。聚類是一種按照對(duì)象間相似性進(jìn)行無(wú)監(jiān)督分類(或分簇)的過(guò)程［1］，而非監(jiān)督的聚類是根據(jù)實(shí)際數(shù)據(jù)的特征，按照以某種度量為標(biāo)準(zhǔn)的數(shù)據(jù)之間的相似性，把一組沒有劃分類的對(duì)象集劃分成一系列有意義的不同的類，把特征屬性相似的歸為一類，不相似的作為另一類，使同一類之間相似性最小化，不同類之間相似性最大化，即聚類具有分組數(shù)未知、沒有關(guān)于聚類的任何先驗(yàn)性知識(shí)、不需要用訓(xùn)練樣本進(jìn)行學(xué)習(xí)和訓(xùn)練、聚類結(jié)果動(dòng)態(tài)、不同相似性度量和不同的目的要求將產(chǎn)生不同的聚類結(jié)果等特征。而工程實(shí)例的結(jié)構(gòu)方案千變?nèi)f化，很難對(duì)其結(jié)構(gòu)方案進(jìn)行確切的分類，顯然，利用聚類分析的方法可以幫助設(shè)計(jì)者從大量沒有結(jié)構(gòu)方案分類的工程實(shí)例庫(kù)中快速獲取若干相似實(shí)例，據(jù)此即可進(jìn)行當(dāng)前結(jié)構(gòu)的方案設(shè)計(jì)。聚類分析的算法較多，而k-means 算法是一種應(yīng)用最廣泛的方法［2-4］，為此，本文將探索利用基于k-means 的聚類方法，來(lái)進(jìn)行高層建筑結(jié)構(gòu)智能方案設(shè)計(jì)。

2 k-means 算法

2.1 k-均值算法的基本思想

k-均值算法以最終分類個(gè)數(shù)k 為參數(shù)，把n 個(gè)數(shù)據(jù)對(duì)象{xj}n分為k 個(gè)聚類{ci}k，以使聚類內(nèi)有較高的相似度，相似度根據(jù)一個(gè)聚類中數(shù)據(jù)對(duì)象的平均值(被看做聚類的重心)來(lái)進(jìn)行計(jì)算。

2.2 k-均值算法的流程

首先從n 個(gè)數(shù)據(jù)對(duì)象中隨機(jī)地選擇k 個(gè)對(duì)象，作為初始的聚類中心，對(duì)剩余的每個(gè)對(duì)象，根據(jù)其與各個(gè)聚類中心的距離或相似度，分別將它們賦予與它們最近或最相似的聚類;然后，重新計(jì)算每個(gè)聚類的平均值作為新的類心并調(diào)整各樣本的類別;不斷重復(fù)上述過(guò)程，直到各樣本到其判屬類心的距離平方之和最小或評(píng)價(jià)函數(shù)(或目標(biāo)函數(shù)、準(zhǔn)則函數(shù)、標(biāo)準(zhǔn)測(cè)度函數(shù))收斂為止。

2.3 k-均值算法的準(zhǔn)則函數(shù)JW

準(zhǔn)則函數(shù)JW定義為各聚類內(nèi)所有對(duì)象的平均誤差之和，即計(jì)算類內(nèi)的每個(gè)點(diǎn)到它所屬類中心的距離平方和。設(shè)有待分類樣本集x={x1，x2，…，xn}，在某種相似性測(cè)度基礎(chǔ)上被分劃為c 類{xi(j);j=1，2，…，c;i=1，2，…，nj}，其中上角標(biāo)j 表示類別，下角標(biāo)i 表示類內(nèi)模式的序號(hào)，Σnj=n，類內(nèi)距離準(zhǔn)則函數(shù)Jw定義為:

式中，mj表示ωj類的中心或模式均值向量，按下式確定。

公式(1)表征了各樣本到其所屬類中心距離的平方和。聚類的目標(biāo)是使Jw取最小，即Jw→min，因Jw值越大，說(shuō)明某些樣本沒有就近分類，在此意義上聚類效果不好，應(yīng)重新調(diào)整分劃。這種準(zhǔn)則也稱為誤差平方和準(zhǔn)則。

顯然，Jw是各樣本xi(i ∈［1，n］)和類心mj(j∈［1，c］)的函數(shù)，在樣本集{xi}n 給定條件下，Jw的值取決于類心集{mj}c 的選取，類心集的確定相應(yīng)于樣本類別的分劃。該準(zhǔn)則適用于同類樣本比較密集，且各類別樣本分布區(qū)域體積差別不大的情況，否則采用上述準(zhǔn)則可能是不適宜的。例如，當(dāng)某一類樣本數(shù)目較多而另一類樣本較少，兩類樣本所占空間大小明顯不同，兩類間的距離又不足夠大時(shí)，樣本較多的那一類中一些邊緣處的樣本可能距離另一類的類心更近一些。

2.4 k-均值算法步驟描述

輸入:包含n 個(gè)對(duì)象的數(shù)據(jù)庫(kù)D=X={xj}n及期望聚類的簇?cái)?shù)目k。

輸出:k 個(gè)簇，使平方誤差準(zhǔn)則最小。

k-均值算法:

(1)assign initial value for means m1s，m2s，…，mks;//隨機(jī)選擇k 個(gè)對(duì)象作為初始的聚類中心:m1s，m2s，…，mks，置迭代步數(shù)s=0

(2)repeat

(3)For j=1 to n Do assign each xjto the cluster which has the closest center(mean);//將待分類的每個(gè)對(duì)象xj∈{xj}n按最小距離原則賦給k 個(gè)初始的聚類中心中的某一類，或根據(jù)聚類中數(shù)值對(duì)象的平均值，將每個(gè)數(shù)據(jù)對(duì)象重新賦給最相似的簇。即如果djl(s)=min［dji(s)］，j=1，2，…，n，則判xj∈cl(s+1)。其中，dji(s)表示xj和類ci(s)的中心mi(s)間的距離。于是產(chǎn)生了新的聚類ci(s+1)(i=1，2，…，k)。

(4)For i=1 to k Do calculate new center for each cluster;//按公式3 計(jì)算重新分類后每個(gè)聚類中數(shù)據(jù)對(duì)象的平均值或類中心，更新聚類平均值。其中，ni(s +1)為ci(s +1)類中所含樣本數(shù)。

因該步采用了平均的方法計(jì)算調(diào)整后k 個(gè)聚類的中心，故稱該方法為k-均值法。

(5)Compute JW;// 按公式4 計(jì)算評(píng)價(jià)函數(shù)JW。

(6)UNTIL convergence criteria is met//平均誤差JW≤ε 或者JW不在明顯地變化或者mi(s +1)=mi(s)(i=1，2，…，c)則結(jié)束，否則，s=s+1，轉(zhuǎn)3)。

3 基于k-means 聚類分析的高層結(jié)構(gòu)智能方案設(shè)計(jì)

在高層建筑結(jié)構(gòu)方案設(shè)計(jì)的聚類分析過(guò)程中，存在多種類型的數(shù)據(jù)，而k-means 算法能有效地對(duì)數(shù)值屬性進(jìn)行聚類分析，因此，可利用k-means 算法的這一特征，通過(guò)對(duì)工程實(shí)例的結(jié)構(gòu)高度、長(zhǎng)寬比、高寬比、場(chǎng)地類別、設(shè)防烈度等數(shù)值型屬性信息的聚類分析，來(lái)進(jìn)行高層建筑結(jié)構(gòu)方案設(shè)計(jì)。以下給出基于k-means 算法聚類的高層結(jié)構(gòu)方案設(shè)計(jì)實(shí)例檢索方法和工程實(shí)例。

3.1 輸入樣本與聚類數(shù)確定

采用表1 中給出的26 個(gè)工程實(shí)例數(shù)據(jù)中的高度、高寬比、長(zhǎng)寬比3 個(gè)數(shù)值型屬性為聚類和實(shí)例檢索依據(jù)，其中，利用前20 個(gè)數(shù)據(jù)進(jìn)行聚類，利用后6個(gè)數(shù)據(jù)進(jìn)行實(shí)例檢索，確定的聚類數(shù)目k=4。為解決屬性間的不可公度性，需對(duì)各屬性進(jìn)行標(biāo)準(zhǔn)化或歸一化處理，通過(guò)標(biāo)準(zhǔn)化處理后將各個(gè)屬性值轉(zhuǎn)化為［0，1］區(qū)間上的數(shù)值［5］。標(biāo)準(zhǔn)化處理后的樣本輸入矩陣為X，聚類后的待檢索輸入樣本矩陣為Y。

3.2 樣本分類原則與評(píng)價(jià)函數(shù)確定

按最小距離原則將每個(gè)數(shù)據(jù)樣本賦給最相似的簇，按公式(4)給出的平均誤差公式計(jì)算評(píng)價(jià)函數(shù)JW值。

3.3 聚類過(guò)程與結(jié)果

按前述k-均值算法步驟進(jìn)行聚類分析，聚類結(jié)果見表2。圖2 給出了第1－6 步聚類結(jié)果，圖3 給出了評(píng)價(jià)函數(shù)JW隨迭代次數(shù)增加的變化曲線，圖4給出了聚類數(shù)k 由2 變化到10 時(shí)JW隨k 單調(diào)減小變化曲線，顯然，當(dāng)k=4 時(shí)JW的曲率變化最大，此時(shí)的分類數(shù)是比較接近從樣本幾何分布上看最優(yōu)的類數(shù)。

表1 高層建筑工程實(shí)例屬性信息(部分)

表2 k-均值算法聚類結(jié)果

圖1 k-means 聚類結(jié)果(4 類，第1－6 步)

3.4 聚類結(jié)果檢驗(yàn)

根據(jù)4 個(gè)中心及其相應(yīng)的聚類結(jié)果，即可利用待輸入樣本矩陣Y 進(jìn)行其相似實(shí)例聚類，以確定與當(dāng)前方案相似的工程實(shí)例，據(jù)此就能確定結(jié)構(gòu)型式及其結(jié)構(gòu)方案。首先，可確定樣本矩陣中每個(gè)待輸入樣本與各個(gè)聚類中心的距離;然后，根據(jù)最小距離原則確定其所屬的類別及其相似的工程實(shí)例;最后，再根據(jù)相似工程實(shí)例方案的類別或相似實(shí)例中出現(xiàn)頻次最高的結(jié)構(gòu)方案類別作為當(dāng)前的結(jié)構(gòu)方案設(shè)計(jì)依據(jù)［6］。下式給出了6 個(gè)待輸入樣本與4 個(gè)聚類中心間的距離矩陣D，其中，dij為樣本yi與聚類中心cj之間的距離。

由上述距離矩陣，根據(jù)最小距離原則可確定6 個(gè)待輸入實(shí)例所屬的類別分別為:2、1、2、3、2、2，各類的相似實(shí)例見表2，由此即可根據(jù)所屬類中的相似實(shí)例的結(jié)構(gòu)方案進(jìn)行當(dāng)前結(jié)構(gòu)方案的設(shè)計(jì)與創(chuàng)新。

4 結(jié)論

在給出了k-均值算法的基本思想、準(zhǔn)則函數(shù)、步驟流程等基礎(chǔ)上，將具有無(wú)導(dǎo)師學(xué)習(xí)特征的聚類分析理論和方法引入高層結(jié)構(gòu)智能方案設(shè)計(jì)，建立了基于K-Means 聚類分析方法的高層結(jié)構(gòu)智能方案設(shè)計(jì)實(shí)例獲取方法，給出了工程應(yīng)用實(shí)例:以表1 中的26 個(gè)工程實(shí)例數(shù)據(jù)為依據(jù)，對(duì)前20 個(gè)工程實(shí)例數(shù)據(jù)進(jìn)行了聚類分析，并給出了聚類結(jié)果及聚類過(guò)程的空間分布圖、評(píng)價(jià)函數(shù)JW隨迭代次數(shù)增加的變化曲線、聚類數(shù)k 由2 變化到10 時(shí)JW隨k 單調(diào)減小變化曲線，并對(duì)后6 個(gè)實(shí)例數(shù)據(jù)進(jìn)行了實(shí)例聚類，給出了相似實(shí)例，為高層建筑結(jié)構(gòu)方案智能設(shè)計(jì)開拓了嶄新的途徑和方法。

［1］Jain A，Murty M，F(xiàn)lynn P.Data clustering:A review.ACM Computing Surveys (CSUR)，1999，31 (3):264-323.

［2］Macqueen J.Some methods for classification and analysis of multivariate observations.In:Proceedings of the 5thBerkely Symposium on Mathematical Statistics and Probability，Berkely，CA，1967，vol.1，281-297.

［3］Huang J Z，Ng M K，Rong H-Q，Li Z-C.Automated variable Weighting in k-Means Type Clustering.IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27(5):657-668.

［4］Wagstaff K，Cardie C，Rogers S.Constrained k-means cluserring with background knowledge.In:Proceedings of the 8thInternational Conference on Machine Learning，Morgan，Kaufmann，2001:577-584.

［5］張世海.高層建筑結(jié)構(gòu)智能方案設(shè)計(jì)方法研究，哈爾濱工業(yè)大學(xué)博士后研究工作報(bào)告，2009.

［6］Shihai Zhang，Changyong Wang Shujun Liu.Intelligent scheme design of high-rise structure for K-means-based case retrieval.Proceedings of the 2010 Second WRI Global Congress on Intelligent Systems(GCIS’2010).Sponsored by Wuhan University of Technology and World Research Institutes.Los Almitos，California Washington·Tokyo GCIS’2010(vol.3):241-244.