高層結構方案設計的K-Means 聚類分析法

張世海 張世忠 段慧杰

(南陽理工學院，南陽 473004)

1 引言

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

2 k-means 算法

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

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

2.2 k-均值算法的流程

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

2.3 k-均值算法的準則函數JW

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

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

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

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

2.4 k-均值算法步驟描述

輸入:包含n 個對象的數據庫D=X={xj}n及期望聚類的簇數目k。

輸出:k 個簇，使平方誤差準則最小。

k-均值算法:

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

(2)repeat

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

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

因該步采用了平均的方法計算調整后k 個聚類的中心，故稱該方法為k-均值法。

(5)Compute JW;// 按公式4 計算評價函數JW。

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

3 基于k-means 聚類分析的高層結構智能方案設計

在高層建筑結構方案設計的聚類分析過程中，存在多種類型的數據，而k-means 算法能有效地對數值屬性進行聚類分析，因此，可利用k-means 算法的這一特征，通過對工程實例的結構高度、長寬比、高寬比、場地類別、設防烈度等數值型屬性信息的聚類分析，來進行高層建筑結構方案設計。以下給出基于k-means 算法聚類的高層結構方案設計實例檢索方法和工程實例。

3.1 輸入樣本與聚類數確定

采用表1 中給出的26 個工程實例數據中的高度、高寬比、長寬比3 個數值型屬性為聚類和實例檢索依據，其中，利用前20 個數據進行聚類，利用后6個數據進行實例檢索，確定的聚類數目k=4。為解決屬性間的不可公度性，需對各屬性進行標準化或歸一化處理，通過標準化處理后將各個屬性值轉化為［0，1］區間上的數值［5］。標準化處理后的樣本輸入矩陣為X，聚類后的待檢索輸入樣本矩陣為Y。

3.2 樣本分類原則與評價函數確定

按最小距離原則將每個數據樣本賦給最相似的簇，按公式(4)給出的平均誤差公式計算評價函數JW值。

3.3 聚類過程與結果

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

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

表2 k-均值算法聚類結果

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

3.4 聚類結果檢驗

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

由上述距離矩陣，根據最小距離原則可確定6 個待輸入實例所屬的類別分別為:2、1、2、3、2、2，各類的相似實例見表2，由此即可根據所屬類中的相似實例的結構方案進行當前結構方案的設計與創新。

4 結論

在給出了k-均值算法的基本思想、準則函數、步驟流程等基礎上，將具有無導師學習特征的聚類分析理論和方法引入高層結構智能方案設計，建立了基于K-Means 聚類分析方法的高層結構智能方案設計實例獲取方法，給出了工程應用實例:以表1 中的26 個工程實例數據為依據，對前20 個工程實例數據進行了聚類分析，并給出了聚類結果及聚類過程的空間分布圖、評價函數JW隨迭代次數增加的變化曲線、聚類數k 由2 變化到10 時JW隨k 單調減小變化曲線，并對后6 個實例數據進行了實例聚類，給出了相似實例，為高層建筑結構方案智能設計開拓了嶄新的途徑和方法。

［1］Jain A，Murty M，Flynn 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］張世海.高層建筑結構智能方案設計方法研究，哈爾濱工業大學博士后研究工作報告，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.