近邻测量（ Measurement of Proximity）读书笔记

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是否要被算作“相同”，基于不同情况可以 认为其无须代入计算，或将其视为“相同”。可供选择的量度方法见书的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.依据可以使用的那些变量），接着计算类内部的统计性质，给丢失的数据赋值，最后再拿这所有的样本变量聚类并重复最后的两步直到赋的值和类结构不再变化。实际应用中可以使用多种估算方法，如果各种方法给出的值差不多，则可以有信心的使用估算丢失值的处理方法。