1. 测度定义
“数学上，测度(Measure)是一个函数，它对一个给定集合的某些子集指定一个数，这个数可以比作大小、体积、概率等等。传统的积分是在区间上进行的，后来人们希望把积分推广到任意的集合上，就发展出测度的概念，它在数学分析和概率论有重要的地位” ——wikipedia
聚类之前一定要定义好向量之间的相似程度——即近邻测度。在聚类过程中我们使用的测度，范围要更广泛，首先定义向量之间的测度，接着就是集合与向量，集合之间的测度。
对于X上的不相似测度(Dissimilarity Measure, DM) d 是一个函数：
其中R是实数集合，如果d有以下的属性：
（1.1）
（1.2）
（1.3）
如果又满足
（1.4）
（1.5）
那么d被称为度量DM。其中的公式（1.5）也叫三角不等式。稍稍解释一下（其实太好理解了），不相似性测度其实就像我们说的距离一样，两个向量代表两个对象好了。公式1.2定义（向量）对象自己和自己的距离是d0；公式1.1说明了任意两个对象之间的距离要小于正无穷却大于自己和自己的距离（你和别人的距离大于你和自己的距离，这不废话吗＾＿＾）；公式1.3说明距离的交互性；公式1.4不解释了，公式1.5就是三角不等式（初中水平）。
同理相似性测度(Similarity Measure, SM)定义为
满足：
（1.6）
（1.7）
（1.8）
如果又满足
（1.9）
（1.10）
就把s叫做度量SM。具体同DM，各公式的表达一目了然哦~~~
从定义和字面上我们都可以看出二者的不同，在表达相似性时两者都可以，只不过度量的角度不同，对于判别相似，DM越大说明越不相似，越小则越相似，而SM却正好相反，因此我们也可以联想，DM与SM可以利用这种对立关系来定义。举例来说，如果d是一个DM，那么s=1/d就是一个SM。
2. 向量之间的近邻测度
上面的定义只是一个宏观的概括，那么具体的向量之间的测度如何计算呢？下面将详细的介绍。
首先对于实向量的不相似测度，实际应用中最通用的就是加权lp度量了：
（2.1）
其中的xi和yi分别是向量x和y中的第i个值，wi是第i个权重系数，l是向量的维数（以下公式定义同）。而我们比较感兴趣的就是当p=1时，该度量就是加权Manhattan范数，而当p=2时就是加权欧几里得范数，当p=∞时就是max1£i£l wi|xi-yi|了。根据这些DM，我们定义SM为bmax - dp(x,y)。
另外还有一些其他的定义方法，比如
（2.2）
（2.3）
其他懒得列出了，先查阅资料，这里不详述了。
对于实向量的相似性测度，实际中常用的有：
内积：
（2.4）
Tanimoto测度：
（2.5）
其他：
（2.6）
------------------------------------------------take a nap------------------------------------------------------------
对于离散值的向量，首先必须要搞清楚一个概念，这里在《模式识别》的中文译作中我感觉翻译的并不好理解，所以这里展开说明一下，那就是一个叫做相依表(contingency table)的概念。对于一个向量x，其元素值属于有限集F={0,1,…,k-1}，其中k是正整数。令A(x,y)=[aij], i, j=0,1,…,k-1是一个k阶方阵，其中元素aij代表在x中所有i值所在的位置在y的同样位置有j值的个数。附原文：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]。以第一个0(a00)为例说明，0在A中的位置决定i=0，j=0，在x中0所在的位置是第一个位置，而y中0所在的位置为第二个和第五个，两个向量中没有相同位置上的相同0元素，因此A中第一个元素a00为0，而A中第二个为1(a01)，所以i=0，j=1，在x中0所在的位置是第一个，而y中1所在的位置为第一、四、六个，因此有一个相同，所以a01=1。
关于计算矩阵A这里附加java代码实现，可参考：
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)中非零元素的个数。
书本往往教给我们的是基础而不是应用，这些基础知识在实际应用中才会得到更多的改进和变化。也许我们不会简单的在聚类中应用这些测度概念，但是复杂的组合都是来源于基础。因此，对测度的基础概念一定要牢牢把握。在前一阶段做图像分割时，聚类算法执行的前提之一测度，我就做过多个实验，L1和L2范数，Tanimoto测度等。当然不同的图像特征有不同的计算距离方法，总之实际的经验告诉我，基础扎实后，在应用起来是相当的顺手啊~~~（最起码不会被复杂公式吓到）
3. 特殊情况处理
考虑到实例向量的特征类型往往是复杂混合的，这种情况下，如何计算近邻测度呢？一些偷懒的做法就是将所有值都看作是实值类型，把混合向量当作实向量来处理。但是现实使用中，这样做的效果往往差强人意。考虑将实值类型转换成离散类型，这就是著名的离散化了，特征的离散化操作时特征或属性过滤(filter)的一个重要的方面。当然我最推荐的还是基于自己开发的应用场景，设计相关的近邻测度。这样可能通用性比较差，但是如果是问题驱动的话，或者目标驱动，那么这个作为一个solution也不失优良性。当然引入模糊测度的概念也是一种解决方法，这里就不细说了，具体应用可以参看有关模糊和不确定性的文章。另外一点需要说明就是实例向量中部分特征丢失的情况，对于丢失数据，如果我们知道数据的分布，那么合理假设是一个替代方案，但是如果为了省事，常用的做法是直接丢弃该实例向量，或者好点的做法是取所有实例的平均数据作为该维度的替代数据。
4. 点与集合之间的测度
随着聚类过程的不断进行，层次逐渐深入，聚类已经不仅仅是判断点与点之间的相似程度了，点与集合的相似程度也需要计算。而如何定义向量x和聚类C之间的近邻性，从而判断是否将x归类为C。以下三个定义经常用到。
最大近邻函数Max proximity function： 
（4.1）
最小近邻函数Min proximity function：
（4.2）
平均近邻函数Average proximity function：
（4.3）
其中nc是集合C的势。
可以看到，这样的定义在概念理论层次上仍旧将点视作点，将聚类视作集合。另一种情况则是将聚类视作一个点，因为点与点之间的近邻测度已经可以计算，那么将集合视为一个点，就将这个问题归约到了点与点之间的问题了。对聚类进行表达，主要有以下几种表达：
1） 点表达：将聚类视作一个点，可以是均值点(mean vector)，也可以是均值中心(mean center)，也可以是中值中心(median center)。关于这几个概念和公式，任何的统计教材里都有涉猎，我就不一一枚举了。（主要贴公式真的很累，怀念Tex）
2） 超平面表达：线性聚类中常用。不表。有兴趣者去查资料。
3） 超球面表达：球形聚类中常用。同上。
一切的学习都为应用，根据实际应用的不同，我们在定义这种点与集合之间测度时候也有很大的灵活性。
5. 集合与集合之间的测度
同样的，对于集合与集合的测度，可以同点与集合的测度类似。只要记住一点，那就是集合与集合间的近邻测度是建立在点与点之间的测度的基础上的。所以近邻测度的基础在点与点之间。当然聚类结果的优化是一个反复试验的过程，其中也要考虑领域专家的意见。
6. 小结
对于近邻测度的学习，乍一看像是纯数学知识的学习，其实则是对我们开始聚类算法研究之前的一个夯实基础的复习过程。
7. 参考文献及推荐阅读
[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]模式识别第三版, Sergios Theodoridis, Konstantinos Koutroumbas著, 李晶皎, 王爱侠, 张广源等译