【正文】 工商管理學(xué)院信息管理教研室 ???????????????????????????????0)d(D99ij工商管理學(xué)院信息管理教研室 G10 G11 G12 G13 G14 G15 G16 G17 G1 G2 G8 G3 G4 G9 G6 G5 G7 直接聚類法譜系聚類圖 0 1 2 3 4 5 6 7 根據(jù)上述步驟 ， 我們可以做出聚類過程的譜系圖 : 直接聚類法雖然簡便 ， 但在歸類過程中是劃去行和列的 ， 因而難免有信息損失 。 因此直接聚類法并不是最好的系統(tǒng)聚類法 。 以下給出的聚類方法 ， 僅作為了解 。 工商管理學(xué)院信息管理教研室 中間距離法或中線法 (MEDian method) 如果類與類之間的距離既不采用兩類間的最近距離 ， 也不采用最遠(yuǎn)的距離 ， 而是采用介于兩者間的距離 ， 這種方法稱為中間距離法 。 工商管理學(xué)院信息管理教研室 pG qGrGrGkG當(dāng)某步類 和 合并為 后 ， 按中 間距離法計算新類 與其它類 的類間距 離 ， 遞推公式為 ),041()(21 2222 qpkDDDDpqqkpkrk ?????????上式中： 工商管理學(xué)院信息管理教研室 邊上的中線。 4/1???rkDqkD pkDpqDpqD常取 ， 此時由初等幾何知 就是以 ， ， 為邊的三角形中 重心法 (CENtroid method) 上述的 最短距離法 、 最長距離法 、 中間距離法 在定義類與類之間的距離時 ， 沒有考慮每一類中所包含的 樣品個數(shù) 。 如果將兩類間的距離定義為兩類重心間的距離 ， 這種聚類方法稱為重心法 。 對樣品分類而言 ， 每一類的重心就是屬于該類樣品的均值 。 工商管理學(xué)院信息管理教研室 pG qG rG設(shè)某步將類 和 合并為 它們所 包 含的樣品個數(shù)分別為 pm qm rm)( qpr mmm ??)( pX )(qX )(rX， 和 。 重心分別為 ， 和 。 顯然有 設(shè)某一類 工商管理學(xué)院信息管理教研室 )(1 )()()( qqpprr XmXmmX ??的距離是 kG),( qpk ? )(kXrG的重心為 ， 它 與新類 ? ?)()( , krrk XXdD ?如果樣品間的距離定義為歐氏距離 ， 則有 ),()()(222)()()()(2qpkDmmmmDmmDmmXXXXDpqrqrpqkrqpkrprkTrkrk??????? 類 (組 )平均法 (AVErage linkage) 重心法雖然有較好的代表性 ， 但并未充分利用各個樣品的信息 ， 有人提出用兩類樣品兩兩之間平方距離的平均作為類之間的距離 ， 即 工商管理學(xué)院信息管理教研室 ????qp GjGiijqppq dmmD,22 1采用這種類間距離的聚類方法 ,稱為類平均法 。 pG qG rG當(dāng)某步類 和 合并為 ： )( qpr mmm ??? ?qpr GGG ,?， 且 則 工商管理學(xué)院信息管理教研室 距離的遞推公式為 kGrG與其它類 類平均法是一種使用比較廣泛 、 聚類效果較好的方法 。 ),(222 qpkDmmDmmD qkrqpkrprk ??? 可變類平均法 (FLExiblebeta method) 類平均法的類間距離遞推公式中 ， 沒有反映 工商管理學(xué)院信息管理教研室 pG qG和 之間距離 pqD的影響 ， 可變類平均法 將合并后新類 距離公式進(jìn)一 kGrG與其它類 步推廣為 ),()1( 2222 qpkDDmmDmmD pqqkrqpkrprk ?????????????? 1??其中 是可變參數(shù) ， 一般取 。 顯然 ， 可變類平均法是由類平均法和中間距離法適當(dāng)推 工商管理學(xué)院信息管理教研室 時就是下面介紹的可變法 )。 0??03/1 ???? qp mm ?qp mm ?廣得到的 (當(dāng) 時就是類平均法；當(dāng) 且 時就是中間距離法 。 當(dāng) 常取負(fù)值，如 ???41???可變類平均法的分類效果與 的選擇關(guān)系 極大 ， 當(dāng) 接近 1時一般分類效果不好 ， 在實 用中 。 可變法及 McQuitty相似分析法 (MCQ) 工商管理學(xué)院信息管理教研室 pG qG rG當(dāng)某步類 和 合并為 后 ， 可變法 把 距離的遞推公式定義為 kGrG與其它類 ),()(2)1( 2222 qpkDDDDpqqkpkrk ???????在 SAS/STAT軟件的 CLUSTER過程中使用 0??的遞推公式 2222 qkpkrkDDD??并把此方法稱為 McQuitty相似分析法。 離差 (距離 )平方和法 (WARD) 工商管理學(xué)院信息管理教研室 離差平方和法是 Ward(1936)提出的，也稱為 Ward法。它基于方差分析思想，如果類分得正確，則同類樣品之間的離差平方和應(yīng)當(dāng)較小，不同樣品之間的離差平方和應(yīng)當(dāng)較大。 離差平方和為 m kkGGG , 21 ?tmtG)(tXtG)()(tiXtGi ),2,1( tmi ??tG假定已將 個樣品分為 類 ， 記為 ， 表示 類的樣品個數(shù) ， 表示 的重心 ， 表示 中第 個樣品 ， 則 中樣品的 工商管理學(xué)院信息管理教研室 )()( )()( )(1)()()(ttiTmittit XXXXWt??? ??為一數(shù)值。 )()(tiX)(tX n tW其中 ， 為 維向量 ， 個類的總離差平方和為 k? ??? ??????ktttiTmittiktt XXXXWWt1)()()(1)()()(1)()(達(dá)到極小的分類。 k W當(dāng) 固定時 ， 要選擇使 工商管理學(xué)院信息管理教研室 Ward法的基本思想是 ， 先將 ， 成一類，此時 m0?W個樣品各自 然后每次將其中某兩類合 并為一類 ， 因每縮小一類離差平方和就要增加 ，每次選擇使增加最小的兩類進(jìn)行合并 ， 直至所有樣品合并為一類為止 。 Ward法把兩類合并后增加的離差平方和看成類間的平方距離 ， 即令 )(2 qprpq WWWD ???pG qG和 的平方距離 ,其中 表示 ? ?qpr GGG ,?， 工商管理學(xué)院信息管理教研室 的定義，可得 qpr WWW , qpr GGG ,rW分別為 類中樣品的離差 平方和 。 利用 ???????????????qprmirqiTrqimirpiTrpimtrrtTrrtrXXXXXXXXXXXXW1)()()()()()(1)()()()()()(1)()()()()()()()( )()()()(。經(jīng)整理可得 ? ?)()()( 1 qqpprr XmXmmX ??其中 工商管理學(xué)院信息管理教研室 )()( )()()()(2 qpTqprqppq XXXXmmmD ???當(dāng)樣品間距采用歐氏距離時 ， 上式可表示為 22pqrqppq dmmmD ?的類間距離與重心法只差一個常數(shù)倍。 2pqd pG qG)( pX )(qX),( )()(22 qppq XXdd ?其中 表示 , 的重心 與 的平 方： 。 這表明 Ward法定義 工商管理學(xué)院信息管理教研室 pG qG和 的距離定義為如下遞推公式： kGrG與其它類 當(dāng) 合并為 rG后 ， 可變法把 2222pqkrkqkkrqkpkkrpkrk DmmmDmmmmDmmmmD???????? 在實際應(yīng)用中，離差平方和法應(yīng)用比較廣泛，分類效果較好。但它要求樣品間距離必須采用歐氏距離。 除上述這些系統(tǒng)聚類方法外 ， 還有幾種系 統(tǒng) 聚 類 分 析 方 法 在 SAS/STAT 軟 件 的CLUSTER過程中給出 。 如 最大似然譜系聚類(EML)、 密度估計法 (DEN)、 兩階段密度估計法 (TWO)等 。 工商管理學(xué)院信息管理教研室 三、系統(tǒng)聚類方法的統(tǒng)一和比較 系統(tǒng)聚類方法的統(tǒng)一 上述介紹的各種系統(tǒng)聚類分析方法中 ，除直接聚類法外 ， 其余八種方法的聚類的步驟完全一樣 ， 所不同的是類與類之間的距離用不同的定義方法 ， 因而得到不同的遞推公式 ， Lance和 Williams于 1967年首先給出了統(tǒng)一公式 ， 這樣為編制統(tǒng)一的計算程序提供了很大的方便 。 工商管理學(xué)院信息管理教研室 工商管理學(xué)院信息管理教研室 pG qG rG設(shè) 和 合并為 ： ? ?qpr GGG ,?， kG),( qpk ? 的平方距離為： rG 與其它類 則 222222qkpkpqqkqpkprk DDDDDD ?????????類方法有不同的取值 (如下表所示 )。 p? q? ? ?其中 ， ， 和 是參數(shù) ， 不同的系統(tǒng)聚 八種系統(tǒng)聚類方法的距離參數(shù)值 方法名稱 參 數(shù) 矩陣要求 空間 性質(zhì) 最短距離法 1/2 1/2 0 1/2 各種 D 壓縮 最長距離法 1/2 1/2 0 1/2 各種 D 擴(kuò)張 中間距離法 1/2 1/2 0 歐式距離 保持 重心法 0 歐式距離 保持 類平均法 0 0 各種 D 保持 可變平均法 0 各種 D 不定 可變法 0 各種 D 擴(kuò)張 離差平方和法 0 歐式距離 壓縮 p? q? ? ?1??1??krkmm m??p?? q?041 ????rpmmrqmmrpmmrqmm2)1( ??2)1( ??rpm m)1( ??rqmm)1( ??krkpmmmm??krkqmmmm??工商管理學(xué)院信息管理教研室 系統(tǒng)聚類方法的簡單性質(zhì) (1)單調(diào)性 工商管理學(xué)院信息管理教研室 的，則稱它具有單調(diào)性。并類距離有單調(diào)性符合系統(tǒng)聚類法的基本思想?？梢宰C明，最短距離法、最長距離法、類平均法、可變類平均法、 kD k11 ?D ?D 23 ?D ?D4321 DDDD ???? ?1,2,1, ?? mkD k ?設(shè) 表示系統(tǒng)聚類法中 離 ,如前述 5個產(chǎn)品聚類之例 ,用最短距離時有 : ， ， ， 。 滿 足 。 一個系統(tǒng)聚類法若能 保證 次并類時的距 是嚴(yán)格單調(diào)上升 離差平方和法都具有單調(diào)性，只有重心法和中間距離法不具有單調(diào)性。 (2)空間的濃縮與擴(kuò)張 以前述之例來說明該性質(zhì) 。 比較最短距離法和最長距離法的并類過程及相應(yīng)的距離矩陣可以看出 ， 每一步都有 工商管理學(xué)院信息管理教研室 ),()()( jidd ijij 對一切長短 ? 這種性質(zhì)稱為最長距離法比最短距離法擴(kuò)張；或稱最短距離法比最長距離法濃縮。 對系統(tǒng)聚類方法，有如下結(jié)論： 類平均法 (或中間距離法 )比最短距離法擴(kuò)張 ， 而且比最長距離法濃縮；類平均法比重心法擴(kuò)張 ， 而且比