相似度测度总结汇总.doc

1 相似度文献总结相似度有两种基本类别：（1）客观相似度，即对象之间的相似度是对象的多维特征之间的某种函数关系，比如对象之间的欧氏距离；（2）主观相似度，即相似度是人对研究对象的认知关系，换句话说，相似度是主观认知的结果，它取决于人及其所处的环境，主观相似度符合人眼视觉需求，带有一定的模糊性13。1.1 客观相似度客观相似度可分为距离测度、相似测度、匹配测度。它们都是衡量两对象客观上的相近程度。客观相似度满足下面的公理，假设对象 A与B 的相似度判别为 ，有:(1) 自相似度是一个常量：所有对象的自相似度是一个常数，通常为 1，即(2) 极大性：所有对象的自相似度均大于它与其他对象间的相似度，即。(3) 对称性：两个对象间的相似度是对称的，即。(4) 唯一性：，当且仅当 。1.1.1 距离测度这类测度以两个矢量矢端的距离为基础，因此距离测度值是两矢量各相应分量之差的函数。设表示两个矢量，计算二者之间距离测度的具体方式有多种，最常用的有： 欧氏距离：Euclidean Distance-based Similarity最初用于计算欧几里德空间中两个点的距离，假设 x，y 是 n 维空间的两个点，它们之间的欧几里德距离是： （1.1）当x，y是两个直方图时，该方法可称为直方图匹配法。可以看出，当 n=2 时，欧几里德距离就是平面上两个点的距离。当用欧几里德距离表示相似度，一般采用以下公式进行转换：距离越小，相似度越大。 （1.2）范围：0,1，值越大，说明d越小，也就是距离越近，则相似度越大。 说明：由于特征分量的量纲不一致，通常需要先对各分量进行标准化，使其与单位无关。欧氏距离能够体现个体数值特征的绝对差异，所以更多的用于需要从维度的数值大小中体现差异的分析。优点：简单，应用广泛缺点：没有考虑分量之间的相关性，体现单一特征的多个分量会干扰结果 曼哈顿距离，绝对值距离(街坊距离或 Manhattan 距离)：原理：曼哈顿距离来源于城市区块距离，是将多个维度上的距离进行求和后的结果。同欧式距离相似，都是用于多维数据空间距离的测度 范围：0,1，同欧式距离一致，值越小，说明距离值越大，相似度越大。 说明：比欧式距离计算量少，性能相对高。 （1.3） 切氏(Chebyshev)距离（棋盘距离/切比雪夫距离）：切比雪夫距离起源于国际象棋中国王的走法，我们知道国际象棋国王每次只能往周围的8格中走一步，那么从棋盘中A格（x1，y1）走到B格（x2，y2）最少需要走几步？ （1.3） 明氏(Minkowski)距离/闵可夫斯基距离： （1.4）可以看出，(1.1)、(1.2)、(1.3)式实际上是(1.4)式当的特殊情况。在实际中较多地使用欧氏距离。显然，在观测量的量纲取定的条件下，两个矢量越相似，距离就越小，反之亦然。值得注意的是，在使用上述距离测度描述具体对象时，量纲选取不同会改变某特征的判断依据，即改变该特征对判断贡献的大小，严重的可造成错误分类。这是因为改变特征矢量某分量的量纲，进行比较的两个矢量的相应的两个分量的数值也将改变。若变小，则其相应的特征在距离测度中“影响作用比重”将变小，即根据其判断分类的作用变小，反之将增大，这样便不能很好地反映事实。马氏(Mahalanobis)距离是不受量纲影响的。 马氏距离(Mahalanobis)：马氏距离定义如下：设n维矢量和是矢量集中的两个矢量，它们的马氏距离 d 定义为 （1.5）式中，。V的含义是这个矢量集的协方差矩阵的统计量。适用场合：1） 度量两个服从同一分布并且协方差矩阵为C的随机变量的差异程度2） 度量与某一类的均值向量的差异程度，判别样本的归属，此时为类均值向量。优点：1） 独立于分量量纲2） 排除了样本之间的相关性影响缺点：不同的特征不能差别对待，可能夸大弱特征 汉明距离（Hamming Distance）在信息论中，两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数。换句话说，它就是将一个字符串变换成另一个字符串所需要替换的字符个数。例如：1011101与1001001之间的汉明距离是2。2143896与2233796之间的汉明距离是3。“toned”与“roses” 之间的汉明距离是3。 巴氏距离（Bhattacharyya）巴氏距离常用于计算直方图间相似度，定义如下： (1.6)其中，x、y为归一化数据向量。Bhattacharyya系数取值在01之间，越靠近1，表示两个模型之间相似度越高。如果，x、y向量未归一化，则巴氏系数的计算定义为： （1.7） Hausdorff距离：Hausdorff距离(Hausdorff distance ,HD)是一种定义于两个点集上的最大最小距离，是描述两组点集之间的相似程度的一种量度，x、y之间的Hausdorff距离定义为： （1.8）式中，为x到y的有向Hausdorff距离；为y到x的有向Hausdorff距离；为某种定义在点集x、y上的距离范数。常用的是欧几里得范数。如果定义(表示空间中的任意点)则Hausdorff距离可定义为,这里称分别为点集y和点集x在空间中的变化距离。由于Hausdorff距离是度量两个点集之间最不匹配点的距离，因此它对远离中心的噪声、漏检点都非常敏感，而这一点，在提取图像特征点集特征时使不可避免的。为了克服这个缺点，需要对Hausdorff距离的定义进行扩展。 改进的部分Hausdorff距离：为获得准确的匹配结果，Sim提出了改进的部分Hausdorff距离（LTS-HD）,它是用距离序列的线性组合来定义的： （1.9）式中，p为x内点的个数，为一个属于0,1的百分数。把点集x中的所有点到点集y的距离按由小到大的顺序排列，将序号为1k的k个距离求和，再求平均。所以，该匹配方法不仅能消除远离中心的错误匹配点的影响，而且对零均值高斯噪声的消除能力明显。因袭，采用LTS-HD用于图像特征点集的匹配，力求在所有可能的变换空间中寻找图像特征点集之间的最优变换，以便通过使LTS-HD最小化来获得最优匹配结果。设g为变换空间T（通常由旋转矩阵R、平移变换向量t、尺度c等变换组成）中的一个变换，则最优匹配变换g0满足 (1.10)0 相关度距离常用于计算直方图间相似度，定义如下： （1.8）1 卡方系数常用于计算直方图间相似度，定义如下： （1.9）（备注：引自基于混合图结构的图像相似度的研究_庄小芳，2013年福建师范大学硕士学位论文第一章，2.2节）2 （未命名）常用于计算直方图间相似度，定义如下： （1.11）其中,N表示图像颜色样点空间,比起前面几个计算公式,该式在给出图像相似度的计算中更为直接,操作也更加简便。（备注：引自基于混合图结构的图像相似度的研究_庄小芳，2013年福建师范大学硕士学位论文第一章，2.2节）3 直方图相交距离直方图相交距离是常用于颜色特征相似性度量的一种方法，常用于计算直方图间相似度。如果有两幅图像,则它们的相交距离定义式如下： （1.12）1.1.2 相似测度这类测度是以两矢量的方向是否相近作为考虑的基础，矢量长度并不重要，同样设。 角度相似系数(夹角余弦) 原理：多维空间两点与所设定的点形成夹角的余弦值。 范围：-1,1，值越大，说明夹角越大，两点相距就越远，相似度就越小。 说明：在数学表达中，如果对两个项的属性进行了数据中心化，计算出来的余弦相似度和皮尔森相似度是一样的，所以皮尔森相似度值也是数据中心化后的余弦相似度。定义：矢量之间的相似度可用它们的夹角余弦来度量。两个矢量x和 y 的夹角余弦定义如下： （1.6）与欧几里德距离类似，基于余弦相似度的计算方法也是把特征点作为n-维坐标系中的一个点，通过连接这个点与坐标系的原点构成一条直线（向量），两个特征点之间的相似度值就是两条直线（向量）间夹角的余弦值。因为连接代表特征点与原点的直线都会相交于原点，夹角越小代表两个特征越相似，夹角越大代表两个特征的相似度越小。同时在三角系数中，角的余弦值是在-1, 1之间的，0度角的余弦值是1，180角的余弦值是-1。借助三维坐标系来看下欧氏距离和余弦相似度的区别：从图上可以看出距离度量衡量的是空间各点间的绝对距离，跟各个点所在的位置坐标（即个体特征维度的数值）直接相关；而余弦相似度衡量的是空间向量的夹角，更加的是体现在方向上的差异，而不是位置。如果保持A点的位置不变，B点朝原方向远离坐标轴原点，那么这个时候余弦相似度cos是保持不变的，因为夹角不变，而A、B两点的距离显然在发生改变，这就是欧氏距离和余弦相似度的不同之处。应用：Cosine 相似度被广泛应用于计算文档数据的相似度及数据挖掘类工作：特点：余弦相似度用向量空间中两个向量夹角的余弦值作为衡量两个个体间差异的大小。相比距离度量，余弦相似度更加注重两个向量在方向上的差异，而非距离或长度上。它对于坐标系的旋转和尺度的缩放是不变的(因矢量的长度已规格化)，但对一般的线性变换和坐标系的平移不具有不变性。 调整余弦相似度 Adjusted Cosine Similarity在余弦相似度的介绍中说到：余弦相似度更多的是从方向上区分差异，而对绝对的数值不敏感。因此没法衡量每个维数值的差异，会导致这样一个情况：比如用户对内容评分，5分制，X和Y两个用户对两个内容的评分分别为(1,2)和(4,5)，使用余弦相似度得出的结果是0.98，两者极为相似，但从评分上看X似乎不喜欢这两个内容，而Y比较喜欢，余弦相似度对数值的不敏感导致了结果的误差，需要修正这种不合理性，就出现了调整余弦相似度，即所有维度上的数值都减去一个均值，比如X和Y的评分均值都是3，那么调整后为(-2,-1)和(1,2)，再用余弦相似度计算，得到-0.8，相似度为负值并且差异不小，但显然更加符合现实。应用：调整余弦相似度和弦相似度，皮尔逊相关系数在推荐系统中应用较多。在基于项目的推荐中GroupLens有篇论文结果表明调整余弦相似度性能要由于余弦相似度和皮尔逊相关系数。 相关系数 它实际上是数据中心化后的矢量夹角余弦。 （1.7）此处将 , 视作两个数据集的样本，和 分别是这两个数据集的平均矢量。相关系数对于坐标系的平移、旋转和尺度缩放是不变的。（备注：该节引自 项德良【SAR 图像相似度评估技术研究】，2012年国防科大硕士论文1.2节。） 指数相似系数 指数相似系数定义如下： （1.8）式中， 为相应分量的方差，n为矢量维数。它不受量纲变化的影响。从函数的构造上看属于距离方式(类似于马氏距离)，但从测度值和相似关系看属于相似测度。（备注：该节引自 项德良【SAR 图像相似度评估技术研究】，2012年国防科大硕士论文1.2节。） 对数似然相似度Ted Dunning在1993年提出一种对数似然比的概念，主要应用于自然文本语言库中两个词的搭配关系问题。它是基于这样一种思想，即统计假设可以确定一个空间的很多子空间，而这个空间是被统计模型的位置参数所描述。似然比检验假设模型是已知的，但是模型的参数是未知的。二项分布的对数似然比对于二项分布的情况，似然函数为 （1.1）式中：的统计模型，试验结果的参数。给定模型的参数。假设二项分布有相同的基本参数集合，那么对数似然比就是 （1.2）式中：当取得某值时，统计模型的最大值。当时，分母取得最大值。当时，分子取得最大值。所以对数似然比简化为 （1.3）式中：二项分布，实验重复的次数，某事发生的概率，该事件发生的次数，。两边取对数可以将对数似然比的公式变形为： （1.4）由于二项分布的对数似然比能够合理的描述两个事物的相似模型，所以常用对数似然比来计算两个事物（用户或物品）的相似度。对数似然相似度基于两个用户共同评估过的物品数目，但在给定物品总数和每个用户评价的情况下，其最终结果衡量的是两个用户有这么多共同物品的“不可能性”，它是一种不考虑具体偏好值的方法。比如在用户物品偏好的二维矩阵中，我们可以将一个用户对所有物品的偏好作为一个向量来计算用户之间的相似度，或者将所有用户对某个物品的偏好作为一个向量来计算物品之间的相似度。备注：引自张明敏，张功萱对数似然相似度算法的MapReduce并行化实现计算机工程与设计2015,36卷，第5期。 Levenshtein 距离,又称编辑距离两个字符串（链）的相似度可以用Levenshtein距离（Levenshtein distance）表示，该距离定义为将一个串变为另一个串所需的最小操作步数，可能的操作有删除、插入、替换Schlesinger and Hlavac ,2002。还可以给字符串元素变换赋一个变换代价，从而使计算得到的相似度（距离）更灵活，更敏感。同样的原理也可以用在图相似度的计算上。下定义可能的结点和弧的变换（删除、插入、替换、重新标注）集合，再给每种变换赋一个变换代价。任一变换序列的代价用单个步骤代价的组合表示（类似代价步骤的和）。将一个图变为另一个图的所有变换集合中具有最小代价值的那个集合就定义了这两幅图间的距离Niemann,1990。用途：常用于字符串距离，类似可用于计算图的距离备注：引用于图像处理、分析与机器视觉（第三版）Milan Sonka ,Vaclav Hlavac, Roger Boyle著，艾海舟，苏延超译P298，9.5.2 图的相似度 统计相关系数-皮尔逊相关系数（Pearson Correlation Coefficient）皮尔逊相关也称积差相关（积矩相关），即相关分析中的相关系数，分别对基于自身总体标准化后计算余弦向量的标准夹角。是英国统计学家皮尔逊于20世纪提出的一种计算直线相关的方法。皮尔逊相关系数一般用来反映两个变量线性相关程度，它的取值在 -1，+1 之间。相关系数的绝对值越大，相关性越强。假设有两个变量，那么；两个变量间的皮尔逊相关系数可以通过以下公式计算：公式一：公式二：公式三：公式四：以上列出四个公式等价，其中E是数学期望，cov表示方差，N表示变量取值的个数。适用范围：当两个变量对的标准差都不为0时，相关系数才有定义，皮尔逊系数适用于：（1） 两个变量之间是线性关系，都是连续数据（2） 两个变量的总体是正态分布，或接近正态的单峰分布（3） 两个变量的观测值是成对的，每对观测值之间互相独立特点：（1）当两个变量的线性关系增强时，相关系数趋于1或-1；（2）当一个变量增大，另一个变量也增大时，表明它们之间是正相关的，相关系数大于0；（3）如果一个变量增大，另一个变量却减小，表明它们之间是负相关的，相关系数小于0；（4）如果相关系数等于0，表明它们之间不存在线性相关关系。 统计相关系数-斯皮尔曼相关（Spearman秩相关）系数-Spearman Correlation（1） 简介在统计学中，斯皮尔曼等级相关系数以Charles Spearman命名，并经常用希腊字母表示其值。斯皮尔曼等级相关系数用来估计两个变量之间的相关性，其中变量间的相关性可以用单调函数来描述。如果两个变量取值的两个集合中均不存在相同的两个元素，那么，当其中一个变量可以表示为另一个变量的很好的单调函数时（即两个变量的变化趋势相同），两个变量之间的可以达到+1或-1。假设两个随机变量分别为（也可以看做是两个集合），它们的元素个数均为N，两个随机变量取的第个值分别用表示。对进行排序（同为升序或降序），得到两个元素排行集合，其中元素分别为在中的排行以及在中的排行。将集合中的元素对应相减得到一个排行差分集合d,其中，。随机变量之间的斯皮尔曼等级相关系数可由或d计算得到，其计算方式如下：公式一：由排行差分集合d计算而得（）：公式二：由排行集合计算而得（斯皮尔曼等级相关系数同时也被认为是经过排行的两个随机变量的皮尔逊相关系数，以下实际是计算的皮尔逊相关系数）：以下是一个计算集合中元素排行的例子（仅适用于斯皮尔曼等级相关系数的计算）变量元素的位置（依降序排列）变量的排行（）1540.2451.33（2+3）/2=2.51.32（2+3）/2=2.51011这里需要注意：当变量的两个值相同时，它们的排行是通过对它们的位置进行平均得到的。（2） 适用范围斯皮尔曼等级相关系数对数据条件的要求没有皮尔逊相关系数严格，只要两个变量的观测值是成对的等级评定资料，或者是由连续变量观测资料转化得到的等级资料，不论两个变量的整体分布形态、样本容量的大小如何，都可以用斯皮尔曼等级相关系数来进行研究。原理：Spearman秩相关系数通常被认为是排列后的变量之间的Pearson线性相关系数。 （3）取值范围：-1.0,1.0，当一致时为1.0，不一致时为-1.0。 （4）说明：计算非常慢，有大量排序。针对推荐系统中的数据集来讲，用Spearman秩相关系数作为相似度量是不合适的。一般用于学术研究或者是小规模的计算。（5）Spearman相关系数的特点：Spearman相关是根据等级资料研究两个变量间相关关系的方法。它是依据两列成对等级的各对等级数之差来进行计算的，所以又称为“等级差数法”1， Spearman相关系数对原始变量的分布不做要求，属于非参数统计方法。因此它的适用范围比Pearson相关系数要广的多。即使原始数据是等级资料也可以计算Spearman相关系数。对于服从Pearson相关系数的数据也可以计算Spearman相关系数，2， 统计效能比Pearson相关系数要低一些（不容易检测出两者事实上存在的相关关系）。3， spearman只要两个变量的观测值是成对的等级评定资料，或者是由连续变量观测资料转化得到的等级资料，不论两个变量的总体分布形态、样本容量的大小如何，都可以用斯皮尔曼等级相关来进行研究。注：spearman与pearson：1. 连续数据，正态分布，线性关系，用pearson相关系数是最恰当，当然用spearman相关系数也可以，就是效率没有pearson相关系数高。2. 上述任一条件不满足，就用spearman相关系数，不能用pearson相关系数。3. 两个定序测量数据之间也用spearman相关系数，不能用pearson相关系数。 4 .只要在X和Y具有单调的函数关系的关系，那么X和Y就是完全Spearman相关的，这与Pearson相关性不同，后者只有在变量之间具有线性关系时才是完全相关的。 统计相关系数-Kendall Rank(肯德尔等级)相关系数（1） 简介在统计学中，肯德尔相关系数是以Maurice Kendall命名的，并经常用希腊字母（tau）表示其值。肯德尔相关系数是一个用来测量两个随机变量相关性的统计值。一个肯德尔检验是一个无参假设检验，它使用计算而得的相关系数去检验两个随机变量的统计依赖性。肯德尔相关系数的取值范围在-1到1之间，当为1时，表示两个随机变量拥有一致的等级相关性，当为-1时，表示两个随机变量拥有完全相反的等级相关性，当为0时，表示两个随机变量是相互独立的。假设两个随机变量分别为（也可以看做是两个集合），它们的元素个数均为N，两个随机变量取的第个值分别用表示。中的对应元素组成一个元素对集合,其包含的元素为。当集合中任意两个元素与的排行相同时（也就是说当出现情况1或2时；情况1: ,情况2：），这两个元素就被认为是一致的。当出现情况3或4时（情况3: ,情况4：），这两个元素就被认为是不一致的。当出现情况5或6时（情况5: ,情况6：），这两个元素既不是一致也不是不一致的。这里有三个公式计算肯德尔相关系数的值：公式一：其中C表示XY中拥有一致性的元素对数（两个元素为一对），D表示XY中拥有不一致性的元素对数。注意：这一公式仅适用于集合X与Y中不存在相同元素的情况（集合中各个元素唯一）公式二：注意：这一公式适用于集合X或Y中存在相同元素的情况（当然，如果X或Y中均不存在相同的元素时，公式二便等同于公式一）。其中C、D与公式一相同；N1、N2分别是针对集合X、Y计算的，现在以计算N1为例，给出N1的由来（N2的计算可以类推）：将X中的相同元素分别组合成小集合，s表示集合X中拥有的小集合数（例如X包含元素：1 2 3 4 3 3 2，那么这里得到的s则为2，因为只有2、3有相同的元素），表示第i个小集合所包含的元素数。N2在集合Y的基础上计算而得。公式三：注意：这一公式中没有再考虑集合、或者中存在相同元素给最后的统计值带来的影响。公式三的这一计算形式仅适用于用表格表示的随机变量X、Y之间相关系数的计算（下面会介绍），参数M稍后会做介绍。以上都是围绕用集合表示的随机变量而计算肯德尔相关系数的，下面所讲的则是围绕用表格表示的随机变量而计算肯德尔相关系数的。通常人们会将两个随机变量的取值制作成一个表格，例如有10个样本，对每个样本进行两项指标些事（指标的取值均为1到3）。根据样本的指标取值，得到以下二维表格（表1）：表1123Sum112032121430123sum25310由表1 可以得到的可以以集合的形式表示为：得到的集合形式后就可以使用以上的公式一或公式二计算的肯德尔相关系数了（注意公式一、公式二的适用条件）当然如果给定的集合形式，那么也是很容易得到它们的表格形式的。这里需要注意的是：公式二也可以用来计算表格形式表示的二维变量的肯德尔相关系是，不过它一般用来计算由正方形表格表示的二维变量的肯德尔相关系数，公式三则只是用来计算由长方形表格表示的二维变量的Kendall相关系数。这里给出公式三种字母的含义，表示长方形表格中行数与列数中较小的一个。表1的行数及列数均为三。（2） 适用范围肯德尔相关系数与斯皮尔曼相关系数对数据的条件要求相同。0 Tanimoto 系数（Tanimoto Coefficient）Tanimoto 系数也称为 广义Jaccard 系数，是 Cosine 相似度的扩展，通常应用于、为布尔向量，即各分量只取0或1的时候，此时表示的是、的公共特征占、具有的所有特征的比例。其实质就是集合交集与并集的比。也多用于计算文档数据的相似度，或两个集合之间的相似程度。范围：0,1，越接近1说明越相似。 1 Jaccard 系数Jaccard 系数主要用于计算符号度量或布尔值度量的个体间的相似度，因为个体的特征属性都是由符号度量或者布尔值标识，因此无法衡量差异具体值的大小，只能获得“是否相同”这个结果，所以Jaccard 系数只关心个体间共同具有的特征是否一致这个问题。如果比较的Jaccard 相似系数，只比较中相同的个数，公式如下：也就是关联的交集除以关联的并集。范围：其值介于0, 1之间，如果两个个体间的特征完全相同，交集等于并集，值为1；如果没有任何关联，交集为空，值为0。1.1.3 匹配测度 （备注：该节引自 项德良【SAR 图像相似度评估技术研究】，2012年国防科大硕士论文1.2节。）这种测度常用于医学和生物的分类中。在有些情况下，特征只有两个状态，对象或具有此特征或不具有此特征。此时，若对象具有此特征，则相应分量定义为 1，而相应分量为 0 表示对象无此特征，这就是所谓的二值特征。对于给定的二值特征矢量x和 y 中的某两个相应分量和，若和，则称和是（1-1）匹配，若和，则称和是（1-0）匹配；若和，则称和是（0-1）匹配；若，则称和是（0-0）匹配，令 （1.9）则a等于两矢量 x 和 y 的(1-1)匹配的特征的数目，b 等于 x 和 y 的(0-1)匹配的特征的数目，c等于x和 y 的(1-0)匹配的特征的数目，e等于x和 y 的(0-0)匹配的特征的数目。对于二值n维特征矢量可定义如下相似性测度： Tanimoto 测度 （1.10）可以看出， s ( x , y )等于x 和 y 都具有的特征的数目与 x和 y 分别具有的特征种类总数之比。这里只考虑(1-1)匹配而不考虑(0-0)匹配。 Rao 测度 （1.11）上式等于(1-1)匹配特征数目和所选用的特征数目之比。 简单匹配系数 （1.12）上式表明，这时匹配系数分子为(1-1)匹配特征数目与(0-0)匹配特征数目之和，分母为所选用的特征数目。 Dice 系数 （1.13）分子、分母无(0-0)匹配，对(1-1)匹配加权。 Kulzinsky 系数 （1.14）上式分子为(1-1)匹配特征数目，分母为(1-0)和(0-0)匹配特征数目之和。1.2 主观相似度1.2.1 结构相似度（SSIM,structural similarity (SSIM) index measurement）（备注：该节引自 项德良【SAR 图像相似度评估技术研究】，2012年国防科大硕士论文1.2节。）结构相似性理论认为，自然图像信号是高度结构化的，即像素间有很强的相关性，特别是空域中最接近的像素，这种相关性蕴含着视觉 场景中物体结构的重要信息；HVS的主要功能是从视野中提取结构信息，可以用对结构信息的度量作为图像感知质量的近似。结构相似性理论是一种不同于以往模 拟HVS低阶的组成结构的全新思想，与基于HVS特性的方法相比，最大的区别是自顶向下与自底向上的区别。这一新思想的关键是从对感知误差度量到对感知结 构失真度量的转变。它没有试图通过累加与心理物理学简单认知模式有关的误差来估计图像质量，而是直接估计两个复杂结构信号的结构改变，从而在某种程度上绕 开了自然图像内容复杂性及多通道去相关的问题.作为结构相似性理论的实现，结构相似度指数从图像组成的角度将结构信息定义为独立于亮度、对比度的，反映场景中物体结构的属性，并将失真建模为亮度、对比度和结构三个不同因素的组合。用均值作为亮度的估计，标准差作为对比度的估计，协方差作为结构相似程度的度量。(from Internet)Zhou Wang 在 2004 年提出一种结构相似度准则 SSIM(Structural Similarity Index Measurement)来衡量光学图像相似度。该准则分析了人眼视觉特性和图像结构之间的关系，从图像空间、人眼视觉和图像结构等方面对SSIM进行了研究，在光学图像的配准、目标识和图像质量评估方面得到了有效验证16。SSIM准则侧重人眼的主观感受，它是从图像的客观信息出发，通过建立模型从而得到的符合人眼视觉的准则。结构相似度定义如下： （1.2.1）为亮度相似度函数，其中，为当、为零时定义的常量。对比度相似度函数定义如下： （1.16）其中，。也为一个常量。结构相似度函数定义如下： （1.17）其中。综上，结构相似度指数(SSIM)定义如下： （1.18）其中均大于 0，为控制三个分量相似度权重的参数。 SSIM ( x , y )越接近于 1，则表明x与 y 越相似，否则越不相似。近年来基于语义测度的主观相似度准则得到越来越多学者的关注。该方法一般在图像分割的基础上，通过构建图像区域子块与语义元数据之间的统计映射关系，实现图像内容的统计语义描述，建立图像之间、图像与语义类别、语义类别之间的分层语义相似测度23-26。该方法充分考虑人眼视觉的语义层面，在图像检索等应用中得到有效验证。1.3 基于像素差值编码的相似度1.3.1 像素差值编码规则 给定一幅 SAR 图像，J 和K 为图像高度和宽度。 G ( x , y )为图像在( x , y )处灰度值。 B 是对应的编码图像，其大小也为， B ( x , y )为 ( x , y )处编码值，定义如下 （2.1）式(2.1)中SAR图像像素值比较是按从左到右、从上到下的顺序。图 2.1所示为SAR图像编码图示。1.3.2 相似性测度及其概率密度函数 和 为待比较的两幅SAR图像， 和 分别为对应的编码图像，基于像素差值编码的相似性测度(Intensity increment code-IIC)定义如下所示： （2.2）式(2.2)中，分别为编码图像和 在 ( x , y )处编码值。衡量了两幅编码图像的相似性，也即反映了两幅SAR图像灰度变化是否一致，评价：该方法对图像噪声、部分遮挡和一定程度模糊有一定鲁棒性。然而该方法着重统计全局图像灰度信息，较少考虑图像局部细节，因此对细节丰富的 SAR 图像并不太适用。1.4 基于 KL 距离准则的相似度比较灰度直方图相似性的方法很多，本文采用一种对称KL准则SKLD(Symmetry Kullback-Leibler Divergence)64。对两个局部梯度比率直方图H 和Q，定义SKLD如下： （3.1）其中，和 分别为 H 和 Q 的MLGRPH特征矢量，N 为特征矢量的维数。由于相似度范围为0,1，即完全相似时，相似度为1，此时SKLD 为0，当完全不相似时，相似度为0，SKLD 为，因此这里需要将SKLD 变换为范围在0,1之间的相似度。我们采用最简单的高斯隶属度函数，如下所示： (3.2)其中，为控制高斯函数宽度的参数，可通过来控制距离与相似度变化关系。1.5 基于hash方法的相似度计算基于hash的相似度计算方法，是一种基于概率的高维度数据的维度削减的方法，主要用于大规模数据的压缩与实时或者快速的计算场景下，基于hash方法的相似度计算经常用于高维度大数据量的情况下，将利用原始信息不可存储与计算的问题转化为映射空间的可存储计算问题，在海量文本重复性判断方面，近似文本查询方面有比较多的应用，google的网页去重1，google news的协同过滤2,3等都是采用hash方法进行近似相似度的计算，比较常见的应用场景Near-duplicate detection、Image similarity identification、nearest neighbor search，常用的一些方法包括I-match，Shingling、Locality-Sensitive Hashing族等方法，下面针对几种常见的hash方法进行介绍。1.5.1 minhash方法介绍 Minhash方法是Locality-sensitive hashing4,5算法族里的一个常用方法，基本的思想是，对于每一个对象的itemlist，将输入的item进行hash，这样相似的item具有很高的相似度被映射到相同的buckets里面，这样尽量保证了hash之后两个对象之间的相似程度和原来是高相似的，而buckets的数量是远远小于输入的item的，因此又达到降低复杂度的目的。 minhash方法用Jaccard进行相似度的计算方法，则对于两个集合 和 ， 和 的相似性的计算方法为： （1.6.1）当两个集合越相似，则该值越接近1，否则越接近0。用minhash方法，将一个集合映射到0-R-1之间的值，以相同的概率随机的抽取一个0-R-1的一个排列，依次排列查找第一次出现1的行。设随机排列为43201(edcab)，对于C1列，第一次出现1的行是R4，所以h(C1) = 3，同理有h(C2)=2, h(C3)=4, h(C4)=3。通过多次抽取随机排列得到n个minhash函数h1,h2,hn，依此对每一列都计算n个minhash值。对于两个集合，看看n个值里面对应相等的比例，即可估计出两集合的Jaccard相似度。可以把每个集合的n个minhash值列为一列，得到一个n行C列的签名矩阵。因为n可远小于R，这样在压缩了数据规模的同时，并且仍能近似计算出相似度。1.5.2 simhash方法介绍simhash方法是在大文本重复识别常用的一个方法，该方法主要是通过将对象的原始特征集合映射为一个固定长度的签名，将对象之间的相似度的度量转化为签名的汉明距离，通过这样的方式，极大限度地进行了降低了计算和存储的消耗。1.5.3 签名计算过程该方法通过对输入特征集合的计算步骤可以描述如下：1， 将一个f维的向量V初始化为0；f位的二进制数S初始化为0；2， 对每一个特征：用传统的hash算法对该特征产生一个f位的签名b。对i=1到f：如果b的第i位为1，则V的第i个元素加上该特征的权重；否则，V的第i个元素减去该特征的权重。 1， 如果V的第i个元素大于0，则S的第i位为1，否则为0；2， 输出S作为签名。通过上述步骤将输入的表示对象的特征集合转化为该对象的一个签名，在完成签名之后，度量两个对象的相似度的差异即变成了对量二者的指纹的K位的差异情况。1.5.4 汉明距离查找优化对于如何快速查找出某一个签名是否与其存在最大差异不超过K个bit的指纹，Detecting Near-Duplicates for Web Crawling这篇论文中进行了介绍。该查找方法的基本思想是利用空间换时间的方法，该方法的依据是需要查找的两个指纹的差异很小，这样可以通过将原始指纹进行分块索引，如果两个指纹的差异很小，则合理的分块后，根据鸽笼原理，其中存在一定数量的块是一致的，通过利用相同的块进行相似的指纹的召回，只需要比对召回的块中有差异的块的bit差异，这样减少了需要比对的数量，节省了比对的时间开销。1.5.5 小结hash方法的相似度计算的主要应用场景，一般是针对大规模数据进行压缩，在保证效果损失可接受的情况下，节省存储空间，加快运算速度，针对该方法的应用，在目前的大规模的互联网处理中，很多相似度的计算都是基于这种近似性的计算，并取得了比较好的效果。设随机排列为43201(edcab)，对于C1列，第一次出现1的行是R4，所以h(C1) = 3，同理有h(C2)=2, h(C3)=4, h(C4)=3。通过多次抽取随机排列得到n个minhash函数h1,h2,hn，依此对每一列都计算n个minhash值。对于两个集合，看看n个值里面对应相等的比例，即可估计出两集合的Jaccard相似度。可以把每个集合的n个minhash值列为一列，得到一个n行C列的签名矩阵。因为n可远小于R，这样在压缩了数据规模的同时，并且仍能近似计算出相似度。1.6 基于主题的相似度计算Bag-of-Words 模型是NLP和IR领域中的一个基本假设。在这个模型中，一个文档(document)被表示为一组单词(word/term)的无序组合，而忽略了语法或者词序的部分。BOW在传统NLP领域取得了巨大的成功，在计算机视觉领域(Computer Vision)也开始崭露头角，但在实际应用过程中，它却有一些不可避免的缺陷，比如：l 稀疏性(Sparseness): 对于大词典，尤其是包括了生僻字的词典，文档稀疏性不可避免；l 多义词(Polysem): 一词多义在文档中是常见的现象，BOW模型只统计单词出现的次数，而忽略了他们之间的区别；l 同义词(Synonym): 同样的，在不同的文档中，或者在相同的文档中，可以有多个单词表示同一个意思；从同义词和多义词问题我们可以看到，单词也许不是文档的最基本组成元素，在单词与文档之间还有一层隐含的关系，我们称之为主题(Topic)。我们在写文章时，首先想到的是文章的主题，然后才根据主题选择合适的单词来表达自己的观点。主题的概念的引入，主要是在原有的基本特征粒度的基础上，引入了更为丰富的隐含层特征，提高了相似性计算的效果，常用的主题分析方法包括Latent Semantic Analysis (LSA) 、 Probabilitistic Latent Semantic Analysis (PLSA)、Latent Dirichlet Allocation ( LDA)。这些方法在分类，聚类、检索、推荐等领域都有着很多的应用，并取得了比较好的效果。下面就LSA及PLSA方法进行简要介绍。1.6.1 LSA（Latent Semantic Analysis）简介LSA的基本思想就是，将document从稀疏的高维Vocabulary空间映射到一个低维的向量空间，我们称之为隐含语义空间(Latent Semantic Space).LSA最初是用在语义检索上，为了解决一词多义和一义多词的问题： 1.一词多义： 美女和PPMM表示相同的含义，但是单纯依靠检索词“美女”来检索文档，很可能丧失掉那些包含“PPMM”的文档。 2.一义多词：如果输入检索词是多个检索词组成的一个小document，例如“清澈 孩子”，那我们就知道这段文字主要想表达concept是和道德相关的，不应该将“春天到了，小河多么的清澈”这样的文本包含在内。 为了能够解决这个问题，需要将词语（term）中的concept提取出来，建立一个词语和概念的关联关系（t-c relationship），这样一个文档就能表示成为概念的向量。这样输入一段检索词之后，就可以先将检索词转换为概念，再通过概念去匹配文档。LSA6,7模型认为特征之间存在某种潜在的关联结构，通过特征-对象矩阵进行统计计算，将高维空间映射到低维的潜在语义结构上，构建出LSA空间模型，从而提取出潜在的语义结构，并用该结构表示特征和对象，消除了词汇之间的相关性影响，并降低了数据维度。增强了特征的鲁棒性LSA利用SVD分解的数学手段来进行计算，数学过程可以表述如下：对于的矩阵A，其中m为特征数，n为样本数。令 ，经过奇异值分解，矩阵A可分解成3个矩阵的乘积：其中，U、V是 和 的正交矩阵，分别称为矩阵A的奇异值对应的左、右奇异向量，是包含所有奇异值的 的对角矩阵，称为A的奇异标准形，其对角元素为矩阵A的奇异值。奇异值按照递减的排列构成对角矩阵 ，取 中前k个最大奇异值构成的，取U和V最前面的k列构成的Uk和的Vk，构建A的k-秩矩阵。（LSA降维的方式就是只取最大的K个奇异值，而其他置为0，于是得到了共生矩阵的近似。） 其中，Uk和Vk 中的行向量分别作为特征向量和对象向量，k是降维后的维数。下图形象的展示了LSA的过程：LSA的优点l 低维空间表示可以刻画同义词，同义词会对应着相同或相似的主题；l 降维可去除部分噪声，是特征更鲁棒；l 充分利用冗余数据；l 无监督/完全自动化；l 与语言无关；LSA的不足l 没有刻画term出现次数的概率模型；l 无法解决多义词的问题；l SVD的优化目标基于L-2 norm 或者是 Frobenius Norm的，这相当于隐含了对数据的高斯噪声假设。而term出现的次数是非负的，这明显不符合Gaussian假设，而更接近Multi-nomial分布；l 对于count vectors 而言，欧式距离表达是不合适的（重建时会产生负数）；l 特征向量的方向没有对应的物理解释；l SVD的计算复杂度很高，而且当有新的文档来到时，若要更新模型需重新训练；l 维数的选择是ad-hoc的；1.6.2 plas介绍 PLSA和LSA基础思想是相同的，都是希望能从term中抽象出概念，但是具体实现的方法不相同。PLSA使用了概率模型，并且使用EM算法来估计P（t|c）和P（c|d）矩阵。 PLSA8,9模型是由Hofmann提出的用于文本检索的概率生成模型，与相比较于LSA，PLSA是基于概率模型的，并直接引入了潜在class变量 zZ=Z1Zk