數(shù)學(xué)建模-聚類分析

數(shù)學(xué)建模-聚類分析數(shù)學(xué)建模-聚類分析數(shù)學(xué)建模-聚類分析資料僅供參考文件編號：2022年4月數(shù)學(xué)建模-聚類分析版本號：A修改號：1頁次：1.0審核：批準(zhǔn):發(fā)布日期：聚類模型聚類，或稱分集，即所謂“物以類聚”，它是按某種相似規(guī)則對給定樣本集、指標(biāo)簇進(jìn)行某種性質(zhì)的劃分，使之成為不同的類．將數(shù)據(jù)抽象化為樣本矩陣，表示第個樣本的第個變量的值．聚類目的，就是從數(shù)據(jù)出發(fā)，將樣本或變量分成類．其方法大致有如下幾個．（1）聚類法．即譜系聚類法．將個樣本看成類，將性質(zhì)最接近的兩類并為一新類，得類；再從類中找出最接近的兩類加以合并，得類；繼之，最后所有樣本都成一類，得一聚類譜系，從譜系中可確定劃分多少類，每類含有哪些樣本．（2）分解法．它是系統(tǒng)聚類的逆過程，將所有樣本視為一類，按某種最優(yōu)準(zhǔn)則將它分成兩類，繼之，每一類都分到只含一個樣本為止．（3）動態(tài)聚類．即快速聚類法．將個樣本粗糙地分成若干類，然后用某中最優(yōu)準(zhǔn)則進(jìn)行調(diào)整，直至不能調(diào)整為止．（4）有序樣本聚類．按時間順序，聚在一類的樣本必須是次序相鄰的樣本．（5）模糊聚類．它是將模糊數(shù)學(xué)用于樣本聚類．（6）運(yùn)籌學(xué)聚類．它是將聚類問題化為線性規(guī)劃、動態(tài)規(guī)劃、整數(shù)規(guī)劃模型的聚類．（7）神經(jīng)網(wǎng)絡(luò)聚類．它是將樣本按自組織特征映射的方法進(jìn)行，也是我們要加以敘述的一個重點(diǎn)．（8）預(yù)測中聚類．它是聚類在預(yù)測中的應(yīng)用，以彌補(bǔ)非穩(wěn)定信號回歸的預(yù)測與分析．這里主要介紹譜系聚類法和快速聚類法．一、距離定義樣本矩陣，是維空間中個點(diǎn)，以距離量度樣本之間的貼近度，就是距離聚類方法．最常用的第個與第個樣本的明考斯基距離為式中為一正整數(shù)．當(dāng),就是歐幾里德距離；當(dāng)，就是絕對距離，或稱“城市街道”距離．而切比雪夫距離為設(shè)是變量的協(xié)方差矩陣，,為第行與第行個變量構(gòu)成的向量，則馬哈蘭羅比斯距離定義為根據(jù)距離的定義，就獲得距離矩陣由距離性質(zhì)可知，為實(shí)對稱矩陣，越小，兩樣本就越相似，其中，根據(jù)的個點(diǎn)分類，依聚類準(zhǔn)則分為不同的類．對常用的系統(tǒng)聚類準(zhǔn)則有：最短距離；最長距離；質(zhì)心距離；平均距離；平方距離．根據(jù)我們講述的多彈頭導(dǎo)彈要求，這里以最短距離為例加以簡要分析．其它幾種距離的分析可見參考文獻(xiàn)REF_Ref5\r\h[10]．令與中分別有與個樣本，其均值分別為與，則最短距離定義為：二、譜系聚類法例題假如抽取5個樣本，每個樣本只測一個指標(biāo)，即數(shù)據(jù)為=[1，0；2，0；，0；6，0；8，0]試以最短距離準(zhǔn)則進(jìn)行距離聚類說明．解這時，樣本間的絕對距離、歐幾里德距離或切比雪夫距離均一致，見表．以最短距離準(zhǔn)則聚類．對于某步，假定具有樣本為的第集合與樣本為的第集合，聚成為具有樣本為的第集合，則第集合與第集合的最短距離，可寫為表絕對距離數(shù)據(jù)1268102006080表中數(shù)據(jù)1、2、、6、8視為二叉數(shù)葉子，編號為1、2、3、4、5．當(dāng)每一個樣本看成一類時，則式子變?yōu)椋钚【嚯x為1，即1與2合聚于6號，得表．表中表一次合聚{1，2}68{1，2}006080表中最小距離為，即與6合聚于7，得表．表中．表二次合聚{1，2}{4，5，6}8{1，2}0{，6}080表中最小距離為2，即{，6}元素（為7號）與8（為5號）合聚于8號，得表．表中表三次合聚{1，2}{，6，8}{1，2}0{，6，8}0最后集合{1，2}與{，6，8}聚成一集叢．于是，由繪得最短距離聚類譜系如圖所示，由圖看出分兩類比較合適．1號、2號數(shù)據(jù)合聚于6號，最小聚距為1；3號、4號數(shù)據(jù)合聚于7號，最小聚距為；7號于5號數(shù)據(jù)合聚于8號，最小聚距為2；最后6號和8號合聚，最小聚距為．于是linkage返回矩陣28最6短1聚距012345聚類譜號圖最短距離聚類譜系依上述方法聚類獲得的譜系的樹葉是獨(dú)立樣本類的編號，為1，2，…，；是的矩陣，第1列、第2列的樹是二叉樹合聚的一對編號，該編號或為樣本編號或為前面的合聚編號；第3列的數(shù)是對應(yīng)于該對合聚時的距離．合聚編號按順序編，即第1合聚于、第2合聚于、第3合聚于，依此順序編之．同時，按上述聚類準(zhǔn)則獲得的矩陣，第3列距離值由首值到最后值是單調(diào)遞增的．三、快速聚類法上面，我們重點(diǎn)介紹了譜系聚類法．譜系聚類法的特點(diǎn)是樣品一旦被歸到某個類后就不變了，這就要求分類方法要比較準(zhǔn)確．又樣品容量較大時，譜系聚類法的計算量過大．為了彌補(bǔ)譜系聚類法的不足，產(chǎn)生了快速聚類法，又稱為動態(tài)聚類法．快速聚類法先將樣品粗略地分一下類，然后再按照某種原則進(jìn)行修正，直至分類比較合理為止．快速聚類的過程大致可由圖表示．理論研究及計算實(shí)踐都表明，快速聚類法是快速有效的聚類方法．合理選擇聚點(diǎn)初始分類分類是否合理最終分類修改分類不合理圖快速聚類的過程圖下面來介紹一下快速聚類法的步驟：1．選擇聚點(diǎn)聚點(diǎn)（種子）是一批有代表性的樣品，它的選擇決定了初始分類，對最終分類有較大影響．在進(jìn)行快速聚類法前，要根據(jù)研究問題的要求及了解程度先定下分類數(shù)，這樣就可以在每一類中選擇一個有代表性的樣品作為聚點(diǎn)（初始聚點(diǎn)）．選擇聚點(diǎn)有下列方法：1）經(jīng)驗選擇．如果對研究對象比較了解，根據(jù)以往經(jīng)驗定下個樣品作為聚點(diǎn)．2）將個樣品人為地（或隨機(jī)地）分成類，以每類的中心作為聚點(diǎn)．3）最小最大原則．設(shè)要將個樣品分成類，先選擇所有樣品中相距最遠(yuǎn)的兩個樣本為前兩個聚點(diǎn)，即選擇，使然后，選擇第3個聚點(diǎn)，使得與前兩個聚點(diǎn)的距離最小者等于所有其余的與兩個樣品的較小距離中最大的，用公式表示為．然后按相同的原則選取，依次下去，直至選定個聚點(diǎn)．選取過程可以用遞推公式表達(dá)．若已選了個聚點(diǎn)，則第個聚點(diǎn)選取原則為．利用SPSS軟件中Classify→K-MeansCluster過程進(jìn)行分析時，分類數(shù)是事先給定的．2．快速聚類法的計算步驟．1)設(shè)個初始聚點(diǎn)的集合是．用下列原則實(shí)現(xiàn)初始分類．記．這樣，將樣品分成不相交的類．以上初始分類的原則是每個樣品以最靠近的初始聚點(diǎn)歸類．依照以上計算，得到一個初始分類．2）從出發(fā)，計算新的聚點(diǎn)集合．以的重心作為新的聚點(diǎn)：．其中是中的樣品數(shù)．這樣，得到新的聚點(diǎn)聚合：．從出發(fā)，將樣品作新的分類．記．得到分類，這樣，依次重復(fù)計算下去．3）設(shè)在第步得到分類．在以上遞推計算過程中，是類的重心．不一定是樣品，又一般不是的重心．當(dāng)逐漸增大時，分類趨于穩(wěn)定．此時，就會近似為的重心，從而，算法即可結(jié)束．實(shí)際計算時，從某一步開始，分類與完全相同，計算即告結(jié)束．記，．理論上可以證明：當(dāng)增加時，為單調(diào)減少有下界序列，故存在，即會逐步趨于穩(wěn)定．依此分類，分類結(jié)果也將逐步穩(wěn)定，即上述快速聚類法具有收斂性．設(shè)，．給定，若，則遞推計算過程結(jié)束．根據(jù)第2章模擬的隨機(jī)數(shù)，以點(diǎn)處的模擬數(shù)據(jù)（見表）為例，利