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