【正文】 第四步 ， 在第三步中所得到的新的 6 6階距離矩陣中 ， 非對角線元素中最小者為 為d6,11=， 故將 G6和 G11歸并為一類 ， 記為G13， 即 G13={G6， G11}={G6， （ G5， G7） }。 工商管理學院信息管理教研室 再按照最短距離法遞推公式計算 1G13G12G14G， ， 與 階距離矩陣 D(6) ： 之間的距離 ， 可得到一個新的4 4 工商管理學院信息管理教研室 G1 G12 G13 G14 G1 0 G12 0 G13 0 G14 0 第六步 ， 在第五步中所得到的新的 4 4階距離矩陣中 ， 非對角線元素中最小者為 d12,14=,故將 G12和 G14歸并為一類 ,記為 G15,即 G15={G12,G14}={(G2， G8),(G3,(G4， G9))}。 工商管理學院信息管理教研室 再按照最短距離法遞推公式計算 13G 16G與 陣 D(8) ： 之間的距離 ， 可得到一個新的 2 2階距離矩 工商管理學院信息管理教研室 G13 G16 G13 0 G16 0 第八步，將 G13和 G16歸并為一類。 綜合上述聚類過程，可以做出最短距離聚類譜系圖（如下圖所示）。 對于前述之例，最長 (遠 )距離聚類法的聚類過程如下： 第一步 ， 在 9 9階距離矩陣 D中 ， 非對角 工商管理學院信息管理教研室 ? ?9410 , GGG ?元素中最小者是 ，故首先將第 ?d10G4區(qū)與第 9區(qū)并為一類 ， 記為 ， 即 1G 2G3G 5G 6G 7G 8G 10G分別按照最長距離法遞推公式計算 ， ， ， ， ， ， 與 之間的距離 得： D1,10=max{d14,d19}=max{,}= D2,10=max{d24,d29}=max{,｝ = D3,10=max{d34,d39}=max{,}= D5,10=max{d54,d59}=max{,}= D6,10=max{d64,d69}=max{,}= D7,10=max{d74,d79}=max{,}= D8,10=max{d84,d89}=max{,}= 工商管理學院信息管理教研室 工商管理學院信息管理教研室 1G 2G 3G 5G 6G 7G8G 10G這樣就得到 ， ， ， ， ， ， 上的一個新的 8 8階距離矩陣 D(2) ： ， G1 G2 G3 G5 G6 G7 G8 G10 G1 0 G2 0 G3 0 G5 0 G6 0 G7 0 G8 0 G10 0 第二步 ， 在上一步驟中所得到的新的8 8階距離矩陣中 ， 非對角元素中最小者為d57=， 故將 G5與 G7歸并為一類 ， 記為 G11，即 G11={G5， G7}。 再分別按最長距離法遞推公式 工商管理學院信息管理教研室 計算 1G12G3G 6G 11G10G， ， ， ， 與 離 ， 可得到一個新的 6 6階距離矩陣 D(4) ： 之間的距 工商管理學院信息管理教研室 G1 G3 G6 G10 G11 G12 G1 0 G3 0 G6 0 G10 0 G11 0 G12 0 第四步 ， 在第三步中所得到的新的 6 6階距離矩陣中 ， 非對角線元素中最小者為 為d3,10=， 故將 G3和 G10歸并為一類 ， 記為G13， 即 G13={G3， G10}={G3， （ G4， G9） }。 工商管理學院信息管理教研室 再按照最長距離法遞推公式計算 6G13G11G14G， ， 與 階距離矩陣 D(6) ： 之間的距離 ， 可得到一個新的4 4 工商管理學院信息管理教研室 G6 G11 G13 G14 G6 0 G11 0 G13 0 G14 0 第六步 ， 在第五步中所得到的新的 4 4階距離矩陣中 ， 非對角線元素中最小者為 d6,11=,故將 G6和 G11歸并為一類 ,記為 G15,即 G15=｛ G6， G11｝ =｛ (G6， （ G5， G7） )｝ 。 工商管理學院信息管理教研室 再按照最長距離法遞推公式計算 15G 16G與 陣 D(8) ： 之間的距離 ， 可得到一個新的 2 2階距離矩 工商管理學院信息管理教研室 G15 G16 G15 0 G16 0 第八步，將 G15和 G16歸并為一類。 綜合上述各聚類步驟，可做出最長距離聚類的譜系圖（如下圖所示）。 它先把各個分類對象單獨視為一類 ， 然后根據(jù)距離最小或相似系數(shù)最大的原則 ， 依次選出一對分類對象 ， 并成新類 。 每一次歸并 ， 都劃去該對象所在的行與行序相同的列 。 工商管理學院信息管理教研室 例 用直接聚類法對某地區(qū)的九個農(nóng)業(yè)區(qū)進行聚類分析 ， 距離矩陣如下： 工商管理學院信息管理教研室 ???????????????????????????????0)d(D99ij 第一步 ， 在距離矩陣 D中 ， 除對角線元素以外 ， d49=d94= ， 故將第 4區(qū)與第 9區(qū)并為一類 ， 劃去第 9行和第 9列； 工商管理學院信息管理教研室 ???????????????????????????????0)d(D99ij 第二步 ， 在余下的元素中 ， 除對角線元素以外 ， d75=d57= ， 故第 5區(qū)與第 7區(qū)并為一類 ， 劃掉第 7行和第 7列； 工商管理學院信息管理教研室 ???????????????????????????????0)d(D99ij 第三步 ， 在第二步之后余下的元素之中 ，除對角線元素以外 ， d82=d28= ，故將第 2區(qū)與第 8區(qū)并為一類 ， 劃去第 8行和第8列； 工商管理學院信息管理教研室 ???????????????????????????????0)d(D99ij 第四步 ， 在第三步之后余下的元素中 ， 除對角線元素以外 ， d43=d34= ， 故將第 3區(qū)與第 4區(qū)并為一類 ， 劃去第 4行和第 4列 ， 此時 ，第 9區(qū)已歸并為一類 。 工商管理學院信息管理教研室 ???????????????????????????????0)d(D99ij 第八步 ， 在第七步之后余下的元素中 ， 除去對角線元素以外 ， 只有 d51=d15=， 故將第 1區(qū)與第 5區(qū)并為一類 ， 劃去第 5行和第 5列 ， 此時 ，第 1， 2， 3， 4， 5， 6， 7， 8， 9區(qū)均歸并為一類 。 因此直接聚類法并不是最好的系統(tǒng)聚類法 。 工商管理學院信息管理教研室 中間距離法或中線法 (MEDian method) 如果類與類之間的距離既不采用兩類間的最近距離 ， 也不采用最遠的距離 ， 而是采用介于兩者間的距離 ， 這種方法稱為中間距離法 。 4/1???rkDqkD pkDpqDpqD常取 ， 此時由初等幾何知 就是以 ， ， 為邊的三角形中 重心法 (CENtroid method) 上述的 最短距離法 、 最長距離法 、 中間距離法 在定義類與類之間的距離時 ， 沒有考慮每一類中所包含的 樣品個數(shù) 。 對樣品分類而言 ， 每一類的重心就是屬于該類樣品的均值 。 重心分別為 ， 和 。 pG qG rG當某步類 和 合并為 ： )( qpr mmm ??? ?qpr GGG ,?， 且 則 工商管理學院信息管理教研室 距離的遞推公式為 kGrG與其它類 類平均法是一種使用比較廣泛 、 聚類效果較好的方法 。 顯然 ， 可變類平均法是由類平均法和中間距離法適當推 工商管理學院信息管理教研室 時就是下面介紹的可變法 )。 當 常取負值，如 ???41???可變類平均法的分類效果與 的選擇關系 極大 ， 當 接近 1時一般分類效果不好 ， 在實 用中 。 離差 (距離 )平方和法 (WARD) 工商管理學院信息管理教研室 離差平方和法是 Ward(1936)提出的，也稱為 Ward法。 離差平方和為 m kkGGG , 21 ?tmtG)(tXtG)()(tiXtGi ),2,1( tmi ??tG假定已將 個樣品分為 類 ， 記為 ， 表示 類的樣品個數(shù) ， 表示 的重心 ， 表示 中第 個樣品 ， 則 中樣品的 工商管理學院信息管理教研室 )()( )()( )(1)()()(ttiTmittit XXXXWt??? ??為一數(shù)值。 k W當 固定時 ， 要選擇使 工商管理學院信息管理教研室 Ward法的基本思想是 ， 先將 ， 成一類，此時 m0?W個樣品各自 然后每次將其中某兩類合 并為一類 ， 因每縮小一類離差平方和就要增加 ，每次選擇使增加最小的兩類進行合并 ， 直至所有樣品合并為一類為止 。 利用 ???????????????qprmirqiTrqimirpiTrpimtrrtTrrtrXXXXXXXXXXXXW1)()()()()()(1)()()()()()(1)()()()()()()()( )()()()(。 2pqd pG qG)( pX )(qX),( )()(22 qppq XXdd ?其中 表示 , 的重心 與 的平 方： 。但它要求樣品間距離必須采用歐氏距離。 如 最大似然譜系聚類(EML)、 密度估計法 (DEN)、 兩階段密度估計法 (TWO)等 。 工商管理學院信息管理教研室 工商管理學院信息管理教研室 pG qG rG設 和 合并為 ： ? ?qpr GGG ,?， kG),( qpk ? 的平方距離為： rG 與其它類 則 222222qkpkpqqkqpkprk DDDDDD ?????????類方法有不同的取值 (如下表所示 )。并類距離有單調性符合系統(tǒng)聚類法的基本思想。 滿 足 。 (2)空間的濃縮與擴張 以前述之例來說明該性質 。 對系統(tǒng)聚類方法，有如下結論： 類平均法 (或中間距離法 )比最短距離法擴張 ， 而且比最長距離法濃縮；類平均法比重心法擴張 ， 而且