Proximity(鄰近)是聚類中一個重要的概念。拿到一個n*p的數據矩陣后（n個樣本，p種feature），通常我們會計算一個n*n的矩陣，然后在這個矩陣的基礎上進 行聚類。矩陣里的元素可以是相似度（Similarity），相異度(dissimilarity) 或距離(distance)，它們統稱為proximity。
為了得到鄰近度(proximity),可以通過直接和間接的方法。所謂直接的方法，就是通過觀察者主觀的感覺給出兩個樣本之間的相似或相異度。而更普遍的間接方法則是通過n*p矩陣來計算得到所要求的n*n矩陣。
我們得分別考慮分類數據，連續數據，和混合數據。
首先是categorical data（分類數據），這類數據中的變量的取值是離散的有限個。其中最特殊的是二分的數據，即各個變量的取值非零即一。計算較為簡單，兩個樣本的各個變量的比較無非四種情況：1-1,1-0,0-1,0-0。分別計數成 a,b,c,d。其中唯一需要注意的是0-0是否要被算作“相同”，基于不同情況可以 認為其無須代入計算，或將其視為“相同”?？晒┻x擇的量度方法見書的P38，方法S1-S6。對于類別超過兩個的情況，則分別看兩個樣本的各個變量是否相同，來計算分數，然后對總變量數取平均。對于這個算法的進一步修正是，對前面的計數加一個指數修正，這用于序列間距離的計算上，因為這時堿基的差異度與序列之間的演化距離并非正比。
對于連續數據，就需要定義一個距離（distance, dissimilarity）的量度了。這個量度d(i,j)需要滿足三角不等式。即對于任何的樣本點i,j,m有 :d(i,j)+d(j,m)>=d(i,m),而d(i,i)=0。常用的量度方法包括歐氏距離，城市街區距離，閔可夫距離，堪培拉距離(Canberra distance)，帕松相關性和角分離度。這幾種距離都可以結合上權重計算。前面的三種方法是基于距離的，堪培拉距離相當于二分數據里度量方法的延伸，而最后兩種方法是基于數據的相關系數。當用兩樣本之間數據的相關性作為量度時，有幾點需要注意，一是需要對數據矩陣的行進行標準化，而非對列作；第二，相關系數的量度無法體現兩個樣本之間差別的大小（只能體現方向，想象一下標準化使得各個樣本成為空間里的單位矢量）。所以它的適用于所有的變量都在一個標度上測量，或者精確的數值只要求提供樣本間相對的信息。距離矩陣的一個重要的屬性是，它是否是歐幾里得的。也就是說這個矩陣所規定的各個點是否可以存在于歐幾里得空間里。當矩陣符合這一條件時，距離可以等同于物理距離來看待。記住，一個歐幾里得的距離矩陣一定是可度量的（滿足三角不等式），而可度量的距離矩陣不一定是歐幾里得的。上面提到的量度方法中，只有歐氏距離是歐幾里得的（廢話）。對于其他的度量矩陣可以通過P43頁的公式3.6變換來使得它成為歐幾里得的，前提是相似性矩陣中的元素是正定的。更進一步，對于任何的相異矩陣，都存在一個常數，使得這個矩陣通過一個變換成為歐幾里得的（公式3.7,3.8)。
最后是混合數據的情況。當連續數據和分類數據混合在一起的時候，有兩種對策：一是將各個變量二分，然后使用二分數據計算相似性量度的方法；二是，對每種變量，分別構建一個相異性的量度，然后可以結合權重或不結合，將它們混在一起構成一個系數。值得記下來的是Gower的general similarity measure:
s_{ij}=frac{sum_{k=1}^{p}w_{ijk}s_{ijk}}{sum_{k=1}^{p}w_{ijk}}
其中w_{ijk}是權重，一般設為0或1，代表該數據點是否可用。s_{ijk}是
第k個變量的相似性量度，對于分類數據，按照之前的方法作，由于w可以用來控制分類數據里的0-0 match，所以s的計算就可以簡單的考慮為相同就加分，不同就零蛋；對于連續數據，Gower建議使用這個相似性量度:
s_{ij}=1-|x_{ik}-x_{jk}|/R_{k}
R_{k}是第k個變量的幅度(range)。這個general similarity measure在沒有丟失數據的情況下可以使用3.6公式對應為歐幾里得的距離矩陣。
?
接下來的議題是如何計算組與組之間的鄰近度。有兩個基本的方法可供選擇。
一是，從鄰近矩陣出發，利用兩組的樣本之間的距離值來計算。比如用兩組間最小的樣本距離值來表示（nearest neighbour distance），最大的距離值(furthest neighbour distance),或者用兩組樣本之間所有距離的平均值來表示。這三種技術分別對應于single linkage（單連鎖）聚類，complete linkage(全連鎖)聚類和group average（組平均）聚類。
另一種方法是，通過組內數據的統計性質得到一個可以代表該組的觀察量，然后用它們之間的距離表示組與組之間的距離。最容易想到的方法是計算各個變量的平均值，以它們來表示整個組。更合適的做法是利用上組內的統計性質。如 Mahalanobis距離（P46,公式3.13)，它利用了兩組數據內部的協方差矩陣。當兩組的中心變大，或組內的差異性變小時，Mahalanobis距離變大。使用這一公式 的前提是，認為兩組數據的協方差矩陣是相似的。當這個條件不滿足時，可以使用P47公式3.14或3.15，其中3.15稱為normal information radius(NIR)，可以看成是Mahalanobis距離的一般形式。上面的方法是適用于連續數據的，對于分 類數據，則有其他的方法。像公式3.17，統計組內第k個變量第l類出現的比率；而公式3.18則是Mahalanobis距離的衍生，用分類變量代替量化的變量，實質是計算所有變量所有分類各自占的比率，然后聯合在一起構建矢量p，并計算組內p 的協方差矩陣。當變量呈多項式分布式，3.18等同于3.17。
關于權重的選擇。給變量加上權重相當于指定變量的重要性。這種指定可以是由研究者給出或者由數據矩陣數據中(not 距離矩陣)計算得出。對后者的最普遍的想法是讓權重反比于對應變量可變化性。這個可變化性(variability)可以是變量的標準差，也可能是變量的變化范圍(range)。后者的效果一般比前者好。上面的做法將使得變化性更強的變量的重要性降低，然而考慮到聚類的目的是分組，那么就不應該降低有可能使得組間差異變大的變量的重要性。因而，較為合適的辦法是盡量使得在同一組內變量的變化小一些，而在組間變量的變化大一些。這就需要在未知聚類結構的情況下作出估算。
方法一：通過估算類內部的變化性來決定權重的方法。這種方法是權重選擇中效果最好的。當得到估計的類內部的變化性后，比如協方差矩陣后，可以方便地使用前面提到的Mahalanobis公式計算兩點間的距離。由Art等人于1982年提出，使用步進算法(iterative algorithm)，找出一對對的可能在同一個類中的樣本，然后使用這種近似的類來計算出一個類內的協方差矩陣W^{*}。
方法二：后來Gnanadesikan 于1995年進一步發展了這個方法，估算一個類間的協方差矩陣B^{*}，用diag(B^{*})(diag(W^{*}))^{-1}代替W^{*}用在類似 Mahalanobis距離的計算中。后面這種方法據說更能強調那些可以突出類結構的 變量。
方法三：De Soete提出這樣為每個變量找到權重，使權重后的歐幾里得距離最小化某個標準使得其偏離超測度（ultrametricity）。這種方法傾向于優化一個層級樹(chapter 4)。
方法四：變量選擇。主旨是找出一個原來變量的子集進行后續的聚類研究。這種做法的例子是Fowlkes等在1988年發明的正向選擇方法。結果是對于選中的 變量，權重為一，排除的變量權重為零。
Gnanadesikan等在1995年的評價中指出：1、相同的權重，標準差權重，范圍權重基本上沒有效果，但是其中range權重稍好些；2、方法一總體表現優良； 3、方法二當一些變量擁有強的類結構時能加強聚類效果；4、方法三常常表現得比相同權重和標準差權重還要差；5、方法四中的正向選擇常常處在表現更好的方法中。
對權重選擇的一些建議：1、主觀的確定變量的權重往往反映了數據已存在的分類，因此對聚類分析沒有幫助；2、沒有一個絕對好的權重選擇方法，方法的好壞往往取決于未知的類結構，盡管如此，大多數時候應該選擇上面提到的方法二，而流行的一股腦的把所有的變量都放進分析中（相同權重）或是使用標準差計算權重的方法似乎沒有效果。
另一個重要的問題是標準化，因為常常各個變量是在不同的測度不同的單位和標準下測量的。當所有的變量都是連續的測度下測得的，常常計算變量的標準差，然后簡單的使各個變量單位化再進行分析(autoscaling,or standard scoring)。另一個方法則是對每個變量除以它們各自的變化范圍(range)，這常常表現得比前一個方法要好。由于標準化可以看作一種權重選擇，前面關于權重選擇的分析和建議同樣適用于此。一般建議不使用變量全局的變化作為標準化的依據，而通過估算類內部的變量變化性來確定如何標準化。而最最好的解決這一問題的方法是，使用一種在數據縮放時沒有影響的聚類方法。
關于鄰近度度量方法的選擇。方法太多了，沒有一個絕對的適用于任何情況的選擇，但有些注意點得記住:1、數據的性質會很強的影響到量度方法的選擇；2、數據的測度影響方法的選擇，如是否是二分的數據，是樣本的大小（size) 重要還是形狀(shape)重要等等；3、聚類方法與系數的選取存在聯系。
在多變量研究中常遇到的問題是，某些數據會有遺失。最簡單（但最好的）的處理方法是只是用沒有數據遺失的那些樣本進行聚類分析。另一種方法是使用 Gower′s general similarity measure來構建鄰近度矩陣，但如果單個樣本遺失的數據較多，這樣建立的鄰近度矩陣就變得不可信，最好還是扔掉這個樣本！根據統計信息估算丟失的值不是值得推薦的辦法。為了估計這些值，用全局的統計信息是不合適的，最好當然是使用類內部的統計信息，因此有了步進的流程來計算這些值。先使用沒有丟失數據的樣本聚類，然后將丟失數據的樣本歸入某些類中（e.g.依據可以使用的那些變量），接著計算類內部的統計性質，給丟失的數據賦值，最后再拿這所有的樣本變量聚類并重復最后的兩步直到賦的值和類結構不再變化。實際應用中可以使用多種估算方法，如果各種方法給出的值差不多，則可以有信心的使用估算丟失值的處理方法。
凡是有該標志的文章，都是該blog博主Caoer（草兒）原創，凡是索引、收藏
、轉載請注明來處和原文作者。非常感謝。