1. 測度定義
“數(shù)學(xué)上，測度(Measure)是一個(gè)函數(shù)，它對(duì)一個(gè)給定集合的某些子集指定一個(gè)數(shù)，這個(gè)數(shù)可以比作大小、體積、概率等等。傳統(tǒng)的積分是在區(qū)間上進(jìn)行的，后來人們希望把積分推廣到任意的集合上，就發(fā)展出測度的概念，它在數(shù)學(xué)分析和概率論有重要的地位” ——wikipedia
聚類之前一定要定義好向量之間的相似程度——即近鄰測度。在聚類過程中我們使用的測度，范圍要更廣泛，首先定義向量之間的測度，接著就是集合與向量，集合之間的測度。
對(duì)于X上的不相似測度(Dissimilarity Measure, DM) d 是一個(gè)函數(shù)：
其中R是實(shí)數(shù)集合，如果d有以下的屬性：
（1.1）
（1.2）
（1.3）
如果又滿足
（1.4）
（1.5）
那么d被稱為度量DM。其中的公式（1.5）也叫三角不等式。稍稍解釋一下（其實(shí)太好理解了），不相似性測度其實(shí)就像我們說的距離一樣，兩個(gè)向量代表兩個(gè)對(duì)象好了。公式1.2定義（向量）對(duì)象自己和自己的距離是d0；公式1.1說明了任意兩個(gè)對(duì)象之間的距離要小于正無窮卻大于自己和自己的距離（你和別人的距離大于你和自己的距離，這不廢話嗎＾＿＾）；公式1.3說明距離的交互性；公式1.4不解釋了，公式1.5就是三角不等式（初中水平）。
同理相似性測度(Similarity Measure, SM)定義為
滿足：
（1.6）
（1.7）
（1.8）
如果又滿足
（1.9）
（1.10）
就把s叫做度量SM。具體同DM，各公式的表達(dá)一目了然哦~~~
從定義和字面上我們都可以看出二者的不同，在表達(dá)相似性時(shí)兩者都可以，只不過度量的角度不同，對(duì)于判別相似，DM越大說明越不相似，越小則越相似，而SM卻正好相反，因此我們也可以聯(lián)想，DM與SM可以利用這種對(duì)立關(guān)系來定義。舉例來說，如果d是一個(gè)DM，那么s=1/d就是一個(gè)SM。
2. 向量之間的近鄰測度
上面的定義只是一個(gè)宏觀的概括，那么具體的向量之間的測度如何計(jì)算呢？下面將詳細(xì)的介紹。
首先對(duì)于實(shí)向量的不相似測度，實(shí)際應(yīng)用中最通用的就是加權(quán)lp度量了：
（2.1）
其中的xi和yi分別是向量x和y中的第i個(gè)值，wi是第i個(gè)權(quán)重系數(shù)，l是向量的維數(shù)（以下公式定義同）。而我們比較感興趣的就是當(dāng)p=1時(shí)，該度量就是加權(quán)Manhattan范數(shù)，而當(dāng)p=2時(shí)就是加權(quán)歐幾里得范數(shù)，當(dāng)p=∞時(shí)就是max1£i£l wi|xi-yi|了。根據(jù)這些DM，我們定義SM為bmax - dp(x,y)。
另外還有一些其他的定義方法，比如
（2.2）
（2.3）
其他懶得列出了，先查閱資料，這里不詳述了。
對(duì)于實(shí)向量的相似性測度，實(shí)際中常用的有：
內(nèi)積：
（2.4）
Tanimoto測度：
（2.5）
其他：
（2.6）
------------------------------------------------take a nap------------------------------------------------------------
對(duì)于離散值的向量，首先必須要搞清楚一個(gè)概念，這里在《模式識(shí)別》的中文譯作中我感覺翻譯的并不好理解，所以這里展開說明一下，那就是一個(gè)叫做相依表(contingency table)的概念。對(duì)于一個(gè)向量x，其元素值屬于有限集F={0,1,…,k-1}，其中k是正整數(shù)。令A(x,y)=[aij], i, j=0,1,…,k-1是一個(gè)k階方陣，其中元素aij代表在x中所有i值所在的位置在y的同樣位置有j值的個(gè)數(shù)。附原文：the number of places where x has the i-th symbol and y has the j-th symbol。舉例來說吧，k=3，且x=[0,1,2,1,2,1]，y=[1,0,2,1,0,1]，那么A(x,y) = [0 1 0, 1 2 0, 1 0 1]。以第一個(gè)0(a00)為例說明，0在A中的位置決定i=0，j=0，在x中0所在的位置是第一個(gè)位置，而y中0所在的位置為第二個(gè)和第五個(gè)，兩個(gè)向量中沒有相同位置上的相同0元素，因此A中第一個(gè)元素a00為0，而A中第二個(gè)為1(a01)，所以i=0，j=1，在x中0所在的位置是第一個(gè)，而y中1所在的位置為第一、四、六個(gè)，因此有一個(gè)相同，所以a01=1。
關(guān)于計(jì)算矩陣A這里附加java代碼實(shí)現(xiàn)，可參考：
1
/** *//**
2
*
3 * @param k
4 * the number of finite set F
5 * @param x
6 * the vector x belongs to F^l
7 * @param y
8 * the vector y belongs to F^l
9 * @return the contingency table A
10 * @author $Jia Yu
11
*/
12
public Integer[][] calContingencyTable(Integer k, Vector<Integer> x,
13 Vector<Integer> y) 
{
14 if (x.size() != y.size())
15 throw new IllegalArgumentException(
16 "The two vectors are not the same size!");
17 Integer[][] A = new Integer[k][k];
18 Integer count_ij;
19
for (int i = 0; i < k; i++) {
20 for (int j = 0; j < k; j++) {
21 count_ij = 0;
22 for (int xi = 0; xi < x.size(); xi++) {
23 if (x.elementAt(xi).equals(i) && y.elementAt(xi).equals(j))
24 count_ij++;
25
}
26 A[i][j] = count_ij;
27 }
28 }
29 return A;
30 }
有了相依表的定義，可以定義離散向量之間的不相似性測度了。
漢明距離：
（2.7）
L1距離：
（2.8）
同樣，相似性測度有
Tanimoto測度：
（2.9）
其中的nx( ny)表示x(y)中非零元素的個(gè)數(shù)。
書本往往教給我們的是基礎(chǔ)而不是應(yīng)用，這些基礎(chǔ)知識(shí)在實(shí)際應(yīng)用中才會(huì)得到更多的改進(jìn)和變化。也許我們不會(huì)簡單的在聚類中應(yīng)用這些測度概念，但是復(fù)雜的組合都是來源于基礎(chǔ)。因此，對(duì)測度的基礎(chǔ)概念一定要牢牢把握。在前一階段做圖像分割時(shí)，聚類算法執(zhí)行的前提之一測度，我就做過多個(gè)實(shí)驗(yàn)，L1和L2范數(shù)，Tanimoto測度等。當(dāng)然不同的圖像特征有不同的計(jì)算距離方法，總之實(shí)際的經(jīng)驗(yàn)告訴我，基礎(chǔ)扎實(shí)后，在應(yīng)用起來是相當(dāng)?shù)捻樖职?/span>~~~（最起碼不會(huì)被復(fù)雜公式嚇到）
3. 特殊情況處理
考慮到實(shí)例向量的特征類型往往是復(fù)雜混合的，這種情況下，如何計(jì)算近鄰測度呢？一些偷懶的做法就是將所有值都看作是實(shí)值類型，把混合向量當(dāng)作實(shí)向量來處理。但是現(xiàn)實(shí)使用中，這樣做的效果往往差強(qiáng)人意。考慮將實(shí)值類型轉(zhuǎn)換成離散類型，這就是著名的離散化了，特征的離散化操作時(shí)特征或?qū)傩赃^濾(filter)的一個(gè)重要的方面。當(dāng)然我最推薦的還是基于自己開發(fā)的應(yīng)用場景，設(shè)計(jì)相關(guān)的近鄰測度。這樣可能通用性比較差，但是如果是問題驅(qū)動(dòng)的話，或者目標(biāo)驅(qū)動(dòng)，那么這個(gè)作為一個(gè)solution也不失優(yōu)良性。當(dāng)然引入模糊測度的概念也是一種解決方法，這里就不細(xì)說了，具體應(yīng)用可以參看有關(guān)模糊和不確定性的文章。另外一點(diǎn)需要說明就是實(shí)例向量中部分特征丟失的情況，對(duì)于丟失數(shù)據(jù)，如果我們知道數(shù)據(jù)的分布，那么合理假設(shè)是一個(gè)替代方案，但是如果為了省事，常用的做法是直接丟棄該實(shí)例向量，或者好點(diǎn)的做法是取所有實(shí)例的平均數(shù)據(jù)作為該維度的替代數(shù)據(jù)。
4. 點(diǎn)與集合之間的測度
隨著聚類過程的不斷進(jìn)行，層次逐漸深入，聚類已經(jīng)不僅僅是判斷點(diǎn)與點(diǎn)之間的相似程度了，點(diǎn)與集合的相似程度也需要計(jì)算。而如何定義向量x和聚類C之間的近鄰性，從而判斷是否將x歸類為C。以下三個(gè)定義經(jīng)常用到。
最大近鄰函數(shù)Max proximity function： 
（4.1）
最小近鄰函數(shù)Min proximity function：
（4.2）
平均近鄰函數(shù)Average proximity function：
（4.3）
其中nc是集合C的勢。
可以看到，這樣的定義在概念理論層次上仍舊將點(diǎn)視作點(diǎn)，將聚類視作集合。另一種情況則是將聚類視作一個(gè)點(diǎn)，因?yàn)辄c(diǎn)與點(diǎn)之間的近鄰測度已經(jīng)可以計(jì)算，那么將集合視為一個(gè)點(diǎn)，就將這個(gè)問題歸約到了點(diǎn)與點(diǎn)之間的問題了。對(duì)聚類進(jìn)行表達(dá)，主要有以下幾種表達(dá)：
1） 點(diǎn)表達(dá)：將聚類視作一個(gè)點(diǎn)，可以是均值點(diǎn)(mean vector)，也可以是均值中心(mean center)，也可以是中值中心(median center)。關(guān)于這幾個(gè)概念和公式，任何的統(tǒng)計(jì)教材里都有涉獵，我就不一一枚舉了。（主要貼公式真的很累，懷念Tex）
2） 超平面表達(dá)：線性聚類中常用。不表。有興趣者去查資料。
3） 超球面表達(dá)：球形聚類中常用。同上。
一切的學(xué)習(xí)都為應(yīng)用，根據(jù)實(shí)際應(yīng)用的不同，我們?cè)诙x這種點(diǎn)與集合之間測度時(shí)候也有很大的靈活性。
5. 集合與集合之間的測度
同樣的，對(duì)于集合與集合的測度，可以同點(diǎn)與集合的測度類似。只要記住一點(diǎn)，那就是集合與集合間的近鄰測度是建立在點(diǎn)與點(diǎn)之間的測度的基礎(chǔ)上的。所以近鄰測度的基礎(chǔ)在點(diǎn)與點(diǎn)之間。當(dāng)然聚類結(jié)果的優(yōu)化是一個(gè)反復(fù)試驗(yàn)的過程，其中也要考慮領(lǐng)域?qū)＜业囊庖姟?/span>
6. 小結(jié)
對(duì)于近鄰測度的學(xué)習(xí)，乍一看像是純數(shù)學(xué)知識(shí)的學(xué)習(xí)，其實(shí)則是對(duì)我們開始聚類算法研究之前的一個(gè)夯實(shí)基礎(chǔ)的復(fù)習(xí)過程。
7. 參考文獻(xiàn)及推薦閱讀
[1]Pattern Recognition Third Edition, Sergios Theodoridis, Konstantinos Koutroumbas
[2] http://zh.wikipedia.org/wiki/%E6%B5%8B%E5%BA%A6%E8%AE%BA
[3]模式識(shí)別第三版, Sergios Theodoridis, Konstantinos Koutroumbas著, 李晶皎, 王愛俠, 張廣源等譯