JIFANG360.com - 机房360
当前位置： >>
关于企业数据中心功耗的测量
摘要：当前，数据中心业界进行能耗的分配、估计和测量有很多种方式。而在本文中，我们就将与广大读者朋友们共同探讨进行数据中心功耗测量的原因、功耗的测量情况、数据收集后应当如何处理、并还将为大家介绍当前一些可用的新兴技术。
　　当前，业界进行能耗的分配、估计和测量有很多种方式。而在本文中，我们就将与广大读者朋友们共同探讨进行数据中心功耗测量的原因、功耗的测量情况、数据收集后应当如何处理、并还将为大家介绍当前一些可用的新兴技术。
　　为什么要测量数据中心的功耗?
　　假设您作为贵公司数据中心经理接到的电话询问您说：&我们在数据中心的功耗方面做了哪些工作?&您会怎么回答?通常情况下，数据中心经理们并不担心功耗的问题。毕竟，下午7点以后，企业的其他领域可能在没有空调的情况下是可以运转的，但数据中心却是绝对不行的。如果企业需要额外的基于IT的服务，则需要购买并安装必要的硬件。这种方法正在迅速改变，因为1)额外的电力资源通常不可用，2)电力成本正在成为运营数据中心的重要成本，
3)当下，越来越多的企业对于绿色环保举措的采用高度重视，以便被社会认可为优秀的企业，肩负起社会责任，并为遵守各项环保法律法规做好准备。
　　很显然，您企业无法对没有测量的东西实施有效的管理。对于能耗来说尤其如此。因为在这种情况下，单凭经验法则所进行的估计结果很可能是错误的，从而会导致不必要的，有时甚至是相当可观的成本损耗。被认为只会消耗很少能量的设备所消耗的能量往往可能会很多，即使这些设备只是出于闲置状态，并没有执行任何实质的工作任务。
　　第一步是为企业数据中心当前的功耗定下基准。在理想情况下，这将通过提供有用的历史统计数据来进行比较。早期的测量和估计可能很粗糙，但随着时间的推移，数据中心内部和外部的功率部署逐步得到了更好地理解，并且使得测量质量逐步得到改善，因此得以随着时间的推移而改进。
　　管理数据中心功耗的方法有很多种，但如果缺乏一些基准测量，就很难知道从哪里开始着手或采取哪些措施能够产生最大的影响。另外，如果没有基线测量，则不可能显示企业数据中心过去对于能源消费水平的管理以及您企业数据中心能耗的改进情况。
　　效率指标
　　当下，数据中心业界最受关注的能源效率度量指标显然是电源使用效率(PUE)。这是数据中心(包括IT设备在内)所消耗的所有能源量与IT设备所消耗的能耗量之比。总能耗量包括照明、冷却和气流管理设备以及数据中心内部电力分配单元的能耗量。IT设备部分是执行计算任务的设备。
　　PUE = 数据中心总设备能耗/IT设备能耗
　　仅向IT设备供电的数据中心将达到PUE =
1.0，因为分子和分母均为IT设备功率。这显然不符合现实数据中心的运营情况。即使在数据中心的照明系统全部关闭的情况下，也会消耗相应的电力资源以便提供冷却和空气流管理的所需，并且会导致配电效率低下。
　　而企业平均数据中心效率(CADE)这一指标则考虑到了数据中心设施的能源效率、使用率和服务器利用率。
　　CADE =(设施效率)x(IT资产效率)
　　设施效率=向IT设备所提供的能源量/从公共供电公司所获取的能源量
　　IT资产效率=所有服务器中央处理器(CPU)的平均利用率(其通常是一个很小的百分比，例如5%)，直到实施了虚拟化等效率工作。
　　在哪里以及如何测量
　　在数据中心，有多处位置可以测量功率。从最粗略的测量逐步晋级发展到最详细的测量，首先是在电源进入数据中心的位置进行测量。如果数据中心是一处独立的结构，并且只是单纯的依靠公共电力公司的供电。那么，这一测量值将是PUE计算公式中的总功率数。
　　但在很多时候，这并不容易。企业数据中心可能仅仅只占某建筑物中的几层楼层。在这种情况下，应该为数据中心所在楼层或房间单独安装电表。如果数据中心不共享电力或建筑物内的相关设施(如冷却设备)的话，则该电表将记录总功率数量。如果设施和电力是共享的(在城市数据中心尤其如此)，那么数据中心管理人员至少需要估计数据中心的总功耗，其可能来自几个不同的来源(例如，由电表所测量的进入数据中心的总供电量，加上建筑物冷却设备所使用的功率的一定百分比)。
　　经常进行功率测量的下一处位置是不间断电源(UPS)。如果其只是为IT设备供电，那么可以将此数据用于PUE计算的分母。但是，UPS也可能为机架式制冷设备供电。
　　测量功率的第三处位置是机架本身，其本身就带有计量机架配电单元(PDU)的功能。这些测量数据通常被认为代表了整合到机架的IT设备，除非有风扇或机架侧制冷单元。
　　测量功率的第四处位置是机架PDU的各个插座。这些智能PDU通常也会提供融合的机架的功耗测量数据。监测插座层面的功率可确保IT设备功耗可以在PUE计算中识别。通过在各个设备级别提供电源信息，可以采取特定措施来提高效率。
　　测量功率的第五处位置是在CPU上。这给出了实际执行计算工作所消耗的功率的测量。实际上，这在今天尚未广泛使用。在采取实际的节能行动措施方面，CPU级别的测量并不是很有用。因为在大多数情况下，数据中心员工可以对整个设备、刀片服务器或其他IT设备的数据进行更改或削减，而不是CPU。测量数据中心功耗的最典型方法是计量机架式PDU和智能机架式PDU，用于监测单个输出。
　　如何处理收集的数据
　　根据企业数据中心所选择的测量位置和测量方法的不同，可以采取各种不同的提高能效的举措。如果能够提供有用的可操作信息的话，我们建议企业数据中心的管理人员们可以对IT设备使用单独的插座级测量方法。
　　通过监测机架上的功耗，数据中心管理人员们可以确定其原始功率分配是否合理。通常，在铭牌额定值的基础上为IT设备分配功率，但这些铭牌额定值通常都很保守。即使使用铭牌功率的一定百分比，例如70%，功率通常也是过度分配的。这意味着IT设备机架的耗电量将超过实际消耗的功率。这种&闲置的功率&可以被部署到其他地方，但是在负载高峰的情况下，如何知道您数据中心的机架不会很容易遭遇电力资源耗尽的情况呢?
　　定期监测每款设备，并且这一时间间隔越短越好，以确保没有忽略高峰期。通过单个设备的功耗数据，可以设置机架，使设备功耗模式相互补充，从而可以用相同的功率来支持更多的IT设备。如果机架即将消耗尽分配给它的所有电力资源，并因此有妨碍断路器的风险，拥有单独的IT设备功耗数据可让IT管理人员以合理的方式移除设备，从而将断路器跳闸的风险降至最低，同时保持合适的装载量。
　　例如，通过在其自己的数据中心进行测试，美国Raritan公司确定了简单的经验法则的铭牌评级百分比并不起作用。在59台服务器中，15台平均功耗为20%或更低，29台为21%至40%，9台为41%至60%，4台为61%至80%，2台为81%或更多。即使在功耗峰值时，49台服务器的铭牌评级也低于60%。许多数据中心规划人员使用铭牌的70%，这意味着许多数据中心有很多闲置的电源。
　　另一方面，在峰值功耗方面，59台服务器中有5台占了铭牌的81%或更多，因此有可能被关闭的风险。就功耗而言，了解单台设备正在发生什么是很重要的，而不是仅仅掌握一些可能掩盖高端和低端问题的总体平均值。
　　环境传感器及其对功率和冷却效率的影响
　　环境传感器对提高数据中心的电源效率起着非常重要的作用。冷却消耗达到30%或更多数据中心的总功率并不罕见。供应商提供入口温度规格。只要入口温度在规格范围内，服务器就能正常工作。这些规格通常远高于数据中心冷通道中所通常提供的规格。因此，通常可以调高数据中心操作环境的温度，以降低冷却设备的功耗。
　　温度传感器应安置在冷气入口侧的机架底部，中部和上部三分之一处。将IT设备冷却到低于要求的温度会消耗大量电力资源，而并不会带来任何有利的影响。由于缺少机架式仪器，数据中心管理人员经常过度冷却，以确信IT设备不会失效。
　　可用的新技术介绍
　　仅仅在一个时间点拍摄单个功耗快照是不够的。IT设备在凌晨2点可能比上午8点耗能少得多，并且可能在周四下午4点达到峰值功耗。耗电量也可能随着一年中的季节的变化而变化，例如在12月在线销售旺季达到高峰。
　　有些硬件设备可以按用户定义的时间间隔每隔几秒钟执行一次功耗快照拍摄。软件程序可用于将这些数据点转换为用电量的计算，其中度量单位为千瓦小时(kWh)。更为先进的工具可以根据能源使用情况计算碳足迹。凭借实际的单个设备的信息，数据中心的工作人员可以了解生成碳排放量最大的单位，因此得以进行按图索骥的管理。
　　相关考虑要素
　　准确性：由于碳排放量的上限规定，信用机制和交易机制被采纳，准确性变得重要。假设完美的正弦波(现实世界中很少出现)，正负5%偏差的准确度可能是可以接受的，以确定机架在断路器跳闸之前是否以大约25%的边际运行。在处理法规和碳信用额以便在交易中进行验证和交易时，这是不可接受的。对于计费或chargeback退款还不够准确。
　　开放和互操作性：许多数据中心都部署了IT管理系统。为了将这样的系统与功率测量联系起来，需要寻找与现有设备集成和互操作的开放标准。易用性是一个重要考虑因素，因此电源管理对于已经很忙的IT人员来说不会成为一个耗时的项目。
　　安全性：电力资源是数据中心的生命线。确保对电源管理系统的访问是安全的，这一点很重要。查找具有高级别加密功能的系统，如256位高级加密标准(AES)以及设置身份验证，授权和权限的功能。
　　我们希望，下一次如果贵公司的CIO打电话给您，并问道：&我们在数据中心的功耗方面做了些什么工作?&时，您能够参考本文所介绍的内容，并概述一套可行的计划，通过收集相关数据信息以建立一定的基线。现在，收集数据，并采取诸如PUE计算等数据中心指标的方法，将会帮助您企业数据中心更有效地管理电力和电力成本。进而更有信心的接听CIO的电话。
　　关于作者
　　本文作者Herman
Chan是Raritan公司的电力解决方案业务部门的总监，该公司位于美国新泽西州萨默塞特。该业务部门致力于构建数据中心基础架构管理解决方案，以解决与提高正常运行时间，容量规划和效率相关的问题Herman在销售和营销管理，以及网络和数据中心基础设施解决方案的产品管理方面拥有超过15年的经验。他曾在Fountain
Technologies和Panasonic担任过相关管理职位。赫尔曼拥有罗格斯大学经济学学位，并获得ITIL认证。
　　Greg More是Raritan公司电力解决方案业务部门的高级产品营销经理。
Greg在技术营销和产品管理方面拥有超过15年的经验。他曾在摩托罗拉和Integrated Network
Corporation担任过职务。Greg拥有西北大学凯洛格管理学院的工商管理硕士学位和西北大学工业工程学士学位。
　　责任编辑:DJ编辑
扫一扫，订阅更多数据中心资讯
本文地址： 网友评论:
条 阅读次数：
版权声明：凡本站原创文章，未经授权，禁止转载，否则追究法律责任。
·····
随着云计算、大数据、物联网的飞
当前，全球范围内正在酝酿新一轮
由北京电子学会计算机委员会组织
中经名气告诉您法治时代下的电子
随着云计算、大数据时代的到来，
施耐德电气的研发设计人员认为空1 相似度文献总结相似度有两种基本类别： （1）客观相似度，即对象之间的相似度是对象的多维特征之间的某种函数关系，比如 对象之间的欧氏距离； （2）主观相似度，即相似度是人对研究对象的认知关系，换句话说， 相似度是主观认知的结果，它取决于人及其所处的环境，主观相似度符合人眼视觉需求，带 有一定的模糊性[13]。1.1 客观相似度客观相似度可分为距离测度、相似测度、匹配测度。它们都是衡量两对象客观上的相近 程度。客观相似度满足下面的公理，假设对象 A 与 B 的相似度判别为 ? ( A, B) ，有: (1) 自相似度是一个常量：所有对象的自相似度是一个常数，通常为 1，即? ( A, A) ? ? ( B, B) ? 1(2) 极大性：所有对象的自相似度均大于它与其他对象间的相似度，即? ( A, B) ? ? ( A, A)和? ( A, B) ? ? ( B, B) 。(3) 对称性：两个对象间的相似度是对称的，即 ? ( A, B) ? ? ( B, A) 。 (4) 唯一性： ? ( A, B) ? 1 ，当且仅当 A ? B 。1.1.1 距离测度这类测度以两个矢量矢端的距离为基础， 因此距离测度值是两矢量各相应分量之差的函 数。设 x ? ? x1 , x2 ,?, xn ? , y ? ? y1 , y2 ,?, yn ? 表示两个矢量，计算二者之间距离测度的具' '体方式有多种，最常用的有：1.1.1.1欧氏距离：Euclidean Distance-based Similarity最初用于计算欧几里德空间中两个点的距离，假设 x，y 是 n 维空间的两个点，它们 之间的欧几里德距离是：? n ? d ( x, y ) ? x ? y ? ? ? ( xi ? yi ) 2 ? ? i ?1 ?1/ 2（1.1）当 x，y 是两个直方图时，该方法可称为直方图匹配法。 可以看出，当 n=2 时，欧几里德距离就是平面上两个点的距离。当用欧几里德距离表 示相似度，一般采用以下公式进行转换：距离越小，相似度越大。（1.2） 范围：[0,1]，值越大，说明 d 越小，也就是距离越近，则相似度越大。 说明：由于特征分量的量纲不一致，通常需要先对各分量进行标准化，使其与单位无关。欧 氏距离能够体现个体数值特征的绝对差异， 所以更多的用于需要从维度的数值大小中体现差 异的分析。 优点：简单，应用广泛 缺点：没有考虑分量之间的相关性，体现单一特征的多个分量会干扰结果1.1.1.2曼哈顿距离，绝对值距离(街坊距离或 Manhattan 距离)：原理：曼哈顿距离来源于城市区块距离，是将多个维度上的距离进行求和后的结果。同欧式 距离相似，都是用于多维数据空间距离的测度 范围：[0,1]，同欧式距离一致，值越小，说明距离值越大，相似度越大。 说明：比欧式距离计算量少，性能相对高。d ( x, y ) ? ? xi ? yi （1.3）i ?1n1.1.1.3切氏(Chebyshev)距离（棋盘距离/切比雪夫距离） ：切比雪夫距离起源于国际象棋中国王的走法，我们知道国际象棋国王每次只能往周围的 8 格中走一步，那么从棋盘中 A 格（x1，y1）走到 B 格（x2，y2）最少需要走几步？d ( x, y ) ? max xi ? yi （1.3）i1.1.1.4明氏(Minkowski)距离/闵可夫斯基距离：?n ? d ( x, y ) ? ? ? ( xi ? yi )m ? ? i ?1 ?1/ m（1.4）可以看出，(1.1)、(1.2)、(1.3)式实际上是(1.4)式当 m ? 2,1, ? 的特殊情况。在实际中较多地 使用欧氏距离。 显然， 在观测量的量纲取定的条件下， 两个矢量越相似， 距离 d (?) 就越小， 反之亦然。值得注意的是，在使用上述距离测度描述具体对象时，量纲选取不同会改变某特 征的判断依据，即改变该特征对判断贡献的大小，严重的可造成错误分类。这是因为改变特 征矢量某分量的量纲，进行比较的两个矢量的相应的两个分量的数值也将改变。若变小，则 其相应的特征在距离测度中“影响作用比重”将变小，即根据其判断分类的作用变小，反之 将增大，这样便不能很好地反映事实。马氏(Mahalanobis)距离是不受量纲影响的。1.1.1.5马氏距离(Mahalanobis)：马氏距离定义如下： 设 n 维矢量 xi 和 x j 是矢量集 ?x1, x2 ,?, xn ? 中的两个矢量，它们的马氏距离 d 定义为d 2 ( xi , x j ) ? ( xi ? yi )'V ?1( xi ? yi ) （1.5）式中， V ? 统计量。 适用场合： 1） 度量两个服从同一分布并且协方差矩阵为 C 的随机变量 X 与Y 的差异程度 2） 度量 X 与某一类的均值向量的差异程度，判别样本的归属，此时 Y 为类均值向量。 优点： 1） 独立于分量量纲 2） 排除了样本之间的相关性影响 缺点：不同的特征不能差别对待，可能夸大弱特征1 n 1 n ' ( x ? x )( x ? x ) , x ? ? i ? xi 。V 的含义是这个矢量集的协方差矩阵的 i n ? 1 i ?1 n i ?11.1.1.6汉明距离（Hamming Distance）在信息论中， 两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数。 换 句话说，它就是将一个字符串变换成另一个字符串所需要替换的字符个数。 例如： 1011101 与 1001001 之间的汉明距离是 2。 2143896 与 2233796 之间的汉明距离是 3。 “toned”与“roses”之间的汉明距离是 3。1.1.1.7巴氏距离（Bhattacharyya）巴氏距离常用于计算直方图间相似度，定义如下：d Bhattacharyya [ x, y ] ? ? xi ? yii ?1n(1.6)其中，x、y 为归一化数据向量。Bhattacharyya 系数取值在 0~1 之间，越靠近 1，表示两个模 型之间相似度越高。如果，x、y 向量未归一化，则巴氏系数的计算定义为：d Bhattacharyya ( x, y ) ? 1 ? ?i ?1nxi ? yi?x ?? yi ?1 i i ?1nn（1.7）i1.1.1.8Hausdorff 距离：Hausdorff 距离(Hausdorff distance ,HD)是一种定义于两个点集上的最大最小距离，是描述两 组点集之间的相似程度的一种量度，x、y 之间的 Hausdorff 距离定义为：H ( x, y ) ? max(h( x, y ), h( y, x)) （1.8）式中， h( x, y ) ? max min xi ? y j 为 x 到 y 的有向 Hausdorff 距离；xi ?x y j ?yh( y, x) ? max min xi ? y j 为 y 到 x 的有向 Hausdorff 距离； ? 为某种定义在点集 x、y 上y j ?y xi ?x的距离范数。常用的是欧几里得范数。 如果定义 d ? ? min ? ? yi , d ? ? min ? ? xi ( ? 表示空间中的任意点)则 Hausdorffyi ? y xi ?x ^距离可定义为 H ( x, y ) ? max(max d xi , max d yi ) ,这里称 d ? , d ? 分别为点集 y 和点集 x 在空xi ?x yi ? y^^间中的变化距离。 由于 Hausdorff 距离是度量两个点集之间最不匹配点的距离， 因此它对远离中心的噪声、 漏检点都非常敏感，而这一点，在提取图像特征点集特征时使不可避免的。为了克服这个缺 点，需要对 Hausdorff 距离的定义进行扩展。1.1.1.9改进的部分 Hausdorff 距离：为获得准确的匹配结果，Sim 提出了改进的部分 Hausdorff 距离（LTS-HD）,它是用距离 序列的线性组合来定义的：hLTS ( x, y ) ?1 k ? min x ? y (i) （1.9） k i ?1式中， k ? ? ? ，p 为 x 内点的个数， f1 为一个属于[0,1]的百分数。把点集 x 中的所有 ? f1 ? p?点到点集 y 的距离按由小到大的顺序排列， 将序号为 1~k 的 k 个距离求和， 再求平均。 所以， 该匹配方法不仅能消除远离中心的错误匹配点的影响， 而且对零均值高斯噪声的消除能力明 显。因袭，采用 LTS-HD 用于图像特征点集的匹配，力求在所有可能的变换空间中寻找图像 特征点集之间的最优变换，以便通过使 LTS-HD 最小化来获得最优匹配结果。 设 g 为变换空间 T（通常由旋转矩阵 R、平移变换向量 t、尺度 c 等变换组成）中的一个 变换，则最优匹配变换 g0 满足M g0 ( x, y ) ? min H ( x, gy )g?T(1.10)1.1.1.10 相关度距离常用于计算直方图间相似度，定义如下：d correl ( x, y ) ??x ? yi ?1 n ini（1.8）2 i?xi ?1? yi21.1.1.11 卡方系数常用于计算直方图间相似度，定义如下：dChi ?square ( x, y ) ? ?( xi ? yi )2 （1.9） xi ? yi i ?1n（备注：引自《基于混合图结构的图像相似度的研究_庄小芳》 ，2013 年福建师范大学硕士 学位论文第一章，2.2 节）1.1.1.12 （未命名）常用于计算直方图间相似度，定义如下：（1.11） 其中,N 表示图像颜色样点空间,比起前面几个计算公式,该式在给出图像相似度的计算中更为 直接,操作也更加简便。 （备注：引自《基于混合图结构的图像相似度的研究_庄小芳》 ，2013 年福建师范大学硕士 学位论文第一章，2.2 节）1.1.1.13 直方图相交距离直方图相交距离是常用于颜色特征相似性度量的一种方法，常用于计算直方图间相似度。 如果有两幅图像 X 和Y ,则它们的相交距离定义式如下：S ( X ,Y ) ?? min( f ( X ), f (Y ))i ?1 i iN? f (Y )i ?1 iN（1.12）1.1.2 相似测度这类测度是以两矢量的方向是否相近作为考虑的基础，矢量长度并不重要，同样设x ? ? x1 , x2 ,?, xn ? , y ? ? y1 , y2 ,?, yn ? 。' '1.1.2.1角度相似系数(夹角余弦)原理：多维空间两点与所设定的点形成夹角的余弦值。 范围：[-1,1]，值越大，说明夹角越大，两点相距就越远，相似度就越小。 说明：在数学表达中，如果对两个项的属性进行了数据中心化，计算出来的余弦相似度和皮 尔森相似度是一样的，所以皮尔森相似度值也是数据中心化后的余弦相似度。 定义：矢量之间的相似度可用它们的夹角余弦来度量。两个矢量 x 和 y 的夹角余弦定义如 下：cos( x, y ) ?x' y x' y ? 1/ 2 （1.6） ' ' x ? y ? ? ( x x )( y y ) ? ?与欧几里德距离类似，基于余弦相似度的计算方法也是把特征点作为 n-维坐标系中的 一个点，通过连接这个点与坐标系的原点构成一条直线（向量） ，两个特征点之间的相似度 值就是两条直线（向量）间夹角的余弦值。因为连接代表特征点与原点的直线都会相交于原 点，夹角越小代表两个特征越相似，夹角越大代表两个特征的相似度越小。同时在三角系数 中，角的余弦值是在[-1, 1]之间的，0 度角的余弦值是 1，180 角的余弦值是-1。借助三维坐 标系来看下欧氏距离和余弦相似度的区别：从图上可以看出距离度量衡量的是空间各点间的绝对距离，跟各个点所在的位置坐标 （即个体特征维度的数值）直接相关；而余弦相似度衡量的是空间向量的夹角，更加的是体 现在方向上的差异， 而不是位置。 如果保持 A 点的位置不变， B 点朝原方向远离坐标轴原点， 那么这个时候余弦相似度 cos 是保持不变的，因为夹角不变，而 A、B 两点的距离显然在发 生改变，这就是欧氏距离和余弦相似度的不同之处。 应用：Cosine 相似度被广泛应用于计算文档数据的相似度及数据挖掘类工作： 特点： 余弦相似度用向量空间中两个向量夹角的余弦值作为衡量两个个体间差异的大小。 相比距离度量，余弦相似度更加注重两个向量在方向上的差异，而非距离或长度上。它对于 坐标系的旋转和尺度的缩放是不变的(因矢量的长度已规格化)，但对一般的线性变换和坐标 系的平移不具有不变性。1.1.2.2调整余弦相似度―― 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.1.2.3相关系数它实际上是数据中心化后的矢量夹角余弦。r ( x, y ) ?( x ? x )' ( y ? y ) ?( x ? x )' ( x ? x )( y ? y )' ( y ? y ) ? ? ?1/ 2（1.7）此处将 x , y 视作两个数据集的样本， x 和 y 分别是这两个数据集的平均矢量。相关系 数对于坐标系的平移、旋转和尺度缩放是不变的。 （备注：该节引自项德良【SAR 图像相似度评估技术研究】 ，2012 年国防科大硕士论文 1.2 节。 ）1.1.2.4指数相似系数指数相似系数定义如下：e( x , y ) ?? 3 ( xi ? yi )2 ? 1 n exp ? ? ? 4 ? 2 ? （1.8） n i ?1 i ? ?式中，?i2 为相应分量的方差，n 为矢量维数。它不受量纲变化的影响。从函数的构造上看属于距离方式(类似于马氏距离)，但从测度值和相似关系看属于相似测度。 （备注：该节引自项德良【SAR 图像相似度评估技术研究】 ，2012 年国防科大硕士论文 1.2 节。 ）1.1.2.5对数似然相似度Ted Dunning 在 1993 年提出一种对数似然比的概念，主要应用于自然文本语言库中两 个词的搭配关系问题。 它是基于这样一种思想， 即统计假设可以确定一个空间的很多子空间， 而这个空间是被统计模型的位置参数所描述。 似然比检验假设模型是已知的， 但是模型的参 数是未知的。 二项分布的对数似然比 对于二项分布的情况，似然函数为? n1 ? ? n2 ? H ( p1 , p2 ; k1 , n1 , k2 , n2 ) ? p1k1 (1 ? p1 )n1 ?k1 ? ? p1k2 (1 ? p2 )n2 ?k2 ? ? （1.1） ? k1 ? ? k2 ?式中：H ――的统计模型，k1, n1, k2 , n2 ――试验结果的参数。p1, p2 ――给定模型的参数。 假设二项分布有相同的基本参数集合 ( p1 , p2 ) p1 ? p2 ，那么对数似然比 ? 就是????max p H ( p , k1, n1, k2 , n2 ) max p1 , p2 H ( p1, p2 ; k1, n1, k2 , n2 )（1.2）式中： max p H ――当 p 取得某值时，统计模型 H 的最大值。 当 p1 ?k1 k k ?k , p2 ? 2 时，分母取得最大值。当 p ? 1 2 时，分子取得最大值。 n1 n2 n1 ? n2所以对数似然比简化为??max p L( p, k1, n1 ) L( p, k2 , n2 ) max p1 , p2 L( p1, k1, n1 ) L( p2 , k2 , n2 )（1.3）式中： L ――二项分布， n ――实验重复的次数， p ――某事发生的概率， k ――该事件 发生的次数， L( p, k , n) ? pk (1 ? p)n?k 。 两边取对数可以将对数似然比的公式变形为：?2log ? ? 2[log L( p1, k1, n1 ) ? log L( p2 , k2 , n2 ) ? log L( p, k1, n1 ) ? log L( p, k2 , n2 )] （1.4）由于二项分布的对数似然比能够合理的描述两个事物的相似模型， 所以常用对数似然比 来计算两个事物（用户或物品）的相似度。对数似然相似度基于两个用户共同评估过的物品 数目， 但在给定物品总数和每个用户评价的情况下， 其最终结果衡量的是两个用户有这么多 共同物品的“不可能性” ，它是一种不考虑具体偏好值的方法。 比如在用户―物品偏好的二维矩阵中， 我们可以将一个用户对所有物品的偏好作为一个 向量来计算用户之间的相似度， 或者将所有用户对某个物品的偏好作为一个向量来计算物品 之间的相似度。 备注：引自张明敏，张功萱《对数似然相似度算法的 MapReduce 并行化实现》 《计算机工程 与设计》2015,36 卷，第 5 期。1.1.2.6 Levenshtein 距离,又称编辑距离两个字符串（链）的相似度可以用 Levenshtein 距离（Levenshtein distance）表示，该距 离定义为将一个串变为另一个串所需的最小操作步数，可能的操作有删除、插入、替换 [Schlesinger and Hlavac ,2002]。还可以给字符串元素变换赋一个变换代价，从而使计算得到 的相似度（距离）更灵活，更敏感。同样的原理也可以用在图相似度的计算上。下定义可能 的结点和弧的变换（删除、插入、替换、重新标注）集合，再给每种变换赋一个变换代价。 任一变换序列的代价用单个步骤代价的组合表示（类似代价步骤的和） 。将一个图变为另一 个图的所有变换集合中具有最小代价值的那个集合就定义了这两幅图间的距离 [Niemann,1990]。 用途：常用于字符串距离，类似可用于计算图的距离 备注：引用于《图像处理、分析与机器视觉（第三版） 》Milan Sonka ,Vaclav Hlavac, Roger Boyle 著，艾海舟，苏延超译 P298，9.5.2 图的相似度1.1.2.7 统计相关系数--皮尔逊相关系数（Pearson CorrelationCoefficient）皮尔逊相关也称积差相关（积矩相关） ，即相关分析中的相关系数 r ，分别对 X 与Y 基 于自身总体标准化后计算余弦向量的标准夹角。是英国统计学家皮尔逊于 20 世纪提出的一 种计算直线相关的方法。 皮尔逊相关系数一般用来反映两个变量线性相关程度， 它的取值在[-1，+1] 之间。相关系数的绝对值越大，相关性越强。 假设有两个变量 X , Y ，那么；两个变量间的皮尔逊相关系数可以通过以下公式计算： 公式一：? X ,Y ?cov( X , Y )? X?Y?E (( X ? ? X )(Y ? ?Y ))? X?Y?E ( XY ) ? E ( X ) E (Y ) E ( X 2 ) ? E 2 ( X ) E (Y 2 ) ? E 2 (Y )公式二：? X ,Y ?公式三：N ? XY ? ? X ?Y N ? X 2 ? (? X )2N ?Y 2 ? ( ? Y )2? X ,Y ?公式四：? ( X ? X )(Y ? Y ) ? ( X ? X ) (Y ? Y )22? X ,Y ?X Y ? XY ? ? N? ( X) ? X ? ?N2 2( Y) ?Y ? ? N22以上列出四个公式等价，其中 E 是数学期望，cov 表示方差，N 表示变量取值的个数。 适用范围：当两个变量对的标准差都不为 0 时，相关系数才有定义，皮尔逊系数适用于： （1） 两个变量之间是线性关系，都是连续数据 （2） 两个变量的总体是正态分布，或接近正态的单峰分布 （3） 两个变量的观测值是成对的，每对观测值之间互相独立 特点：（1）当两个变量的线性关系增强时，相关系数趋于 1 或-1； （2）当一个变量增大，另一个变量也增大时，表明它们之间是正相关的，相关系数大 于 0； （3）如果一个变量增大，另一个变量却减小，表明它们之间是负相关的，相关系数小 于 0； （4）如果相关系数等于 0，表明它们之间不存在线性相关关系。1.1.2.8统计相关系数--斯皮尔曼相关（Spearman 秩相关）系数 --Spearman Correlation（1） 简介 在统计学中，斯皮尔曼等级相关系数以 Charles Spearman 命名，并经常用希腊字母 ? 表示其值。斯皮尔曼等级相关系数用来估计两个变量 X 、Y 之间的相关性，其中变量间的 相关性可以用单调函数来描述。如果两个变量取值的两个集合中均不存在相同的两个元素， 那么， 当其中一个变量可以表示为另一个变量的很好的单调函数时 （即两个变量的变化趋势 相同） ，两个变量之间的 ? 可以达到+1 或-1。假设两个随机变量分别为 X 、Y （也可以看做是两个集合） ，它们的元素个数均为 N， 两个随机变量取的第 i 个值分别用 X i、Yi 表示。对 X 、Y 进行排序（同为升序或降序） ，得 到两个元素排行集合 x、 y ，其中元素 xi、yi 分别为 X i 在 X 中的排行以及 Yi 在 Y 中的排行。 将集合 x、 y 中的元素对应相减得到一个排行差分集合 d,其中 di ? xi ? yi ， 1 ? i ? N 。随 机变量 X 、Y 之间的斯皮尔曼等级相关系数可由 x、 y 或 d 计算得到，其计算方式如下： 公式一：由排行差分集合 d 计算而得（） ：n? ? 1?6? d i 2i ?1N ( N 2 ? 1)公式二：由排行集合 x、 y 计算而得（斯皮尔曼等级相关系数同时也被认为是经过排行的两 个随机变量的皮尔逊相关系数，以下实际是计算 x、 y 的皮尔逊相关系数） ：??? ( x ? x )( yi ?1 i n 2 n i ?1 i i ?1ni? y)i?(x ? x ) ?( y变量 X i 1 0.2 1.3 1.3 10? y )2以下是一个计算集合中元素排行的例子（仅适用于斯皮尔曼等级相关系数的计算） 元素的位置（依降序排列） 5 4 3 2 1 变量的排行（ xi ） 4 5 （2+3）/2=2.5 （2+3）/2=2.5 1这里需要注意：当变量的两个值相同时，它们的排行是通过对它们的位置进行平均得到的。 （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 相关性不同，后者只有在变量之间具有线性关系时才是完全相关的。1.1.2.9统计相关系数--Kendall Rank(肯德尔等级)相关系数（1） 简介 在统计学中， 肯德尔相关系数是以 Maurice Kendall 命名的， 并经常用希腊字母 ? （tau） 表示其值。 肯德尔相关系数是一个用来测量两个随机变量相关性的统计值。 一个肯德尔检验 是一个无参假设检验， 它使用计算而得的相关系数去检验两个随机变量的统计依赖性。 肯德 尔相关系数的取值范围在-1 到 1 之间， 当 ? 为 1 时， 表示两个随机变量拥有一致的等级相关 性，当 ? 为-1 时，表示两个随机变量拥有完全相反的等级相关性，当 ? 为 0 时，表示两个随 机变量是相互独立的。 假设两个随机变量分别为 X 、Y （也可以看做是两个集合） ，它们的元素个数均为 N， 两个随机变量取的第 i 个值分别用 X i、Yi 表示。 X 、Y 中的对应元素组成一个元素对集合XY ,其包含的元素为 ( X i ,Yi ) 。当集合 XY 中任意两个元素 ( X i ,Yi ) 与 ( X j ,Y j ) 的排行相同时 （也就是说当出现情况 1 或 2 时； 情况 1: X i ? X j且Yi ? Y j ,情况 2：X i ? X j且Yi ? Y j ） ， 这两个元素就被认为是一致的。当出现情况 3 或 4 时（情况 3: X i ? X j且Yi ? Y j ,情况 4： ， 这两个元素就被认为是不一致的。 当出现情况 5 或 6 时 （情况 5: X i ? X j , X i ? X j且Yi ? Y j ） 情况 6： Yi ? Y j ） ，这两个元素既不是一致也不是不一致的。 这里有三个公式计算肯德尔相关系数的值： 公式一：? ?a ?C?D 1 N ( N ? 1) 2其中 C 表示 XY 中拥有一致性的元素对数（两个元素为一对） ，D 表示 XY 中拥有不一致性的元素对数。 注意：这一公式仅适用于集合 X 与 Y 中不存在相同元素的情况（集合中各个元素唯一） 公式二：? ?b ?C?D ( N 3 ? N1)( N 3 ? N 2)注意：这一公式适用于集合 X 或 Y 中存在相同元素的情况（当然，如果 X 或 Y 中均不存 在相同的元素时，公式二便等同于公式一） 。 其中 C、D 与公式一相同；N3 ?s s 1 1 1 N ( N ? 1); N1 ? ? Ui (Ui ? 1); N 2 ? ? Vi (Vi ? 1) 2 i ?1 2 i ?1 2N1、N2 分别是针对集合 X、Y 计算的，现在以计算 N1 为例，给出 N1 的由来（N2 的计 算可以类推） ： 将 X 中的相同元素分别组合成小集合，s 表示集合 X 中拥有的小集合数（例如 X 包含元 素：1 2 3 4 3 3 2，那么这里得到的 s 则为 2，因为只有 2、3 有相同的元素） ， Ui 表示第 i 个 小集合所包含的元素数。N2 在集合 Y 的基础上计算而得。 公式三：? ?c ?C?D 1 2 M ?1 N 2 M注意：这一公式中没有再考虑集合 X 、或者 Y 中存在相同元素给最后的统计值带来的 影响。 公式三的这一计算形式仅适用于用表格表示的随机变量 X、 Y 之间相关系数的计算 （下 面会介绍） ，参数 M 稍后会做介绍。 以上都是围绕用集合表示的随机变量而计算肯德尔相关系数的， 下面所讲的则是围绕用 表格表示的随机变量而计算肯德尔相关系数的。 通常人们会将两个随机变量的取值制作成一个表格，例如有 10 个样本，对每个样本进 行两项指标些事 X 、Y （指标 X 、Y 的取值均为 1 到 3） 。根据样本的 X 、Y 指标取值，得 到以下二维表格（表 1） ： 表1 2 3 Sum X 1Y1 2 3 sum 1 1 0 2 2 2 1 5 0 1 2 3 3 4 3 10由表 1 可以得到 X 及Y 的可以以集合的形式表示为：X ? {11 ， ， 2， 2， 2， 2， 2， 3， 3， 3}; Y ? {1， 2， 11 ， ， 2， 2， 3， 2， 3， 3};得到 X 、Y 的集合形式后就可以使用以上的公式一或公式二计算 X 、Y 的肯德尔相关 系数了（注意公式一、公式二的适用条件）当然如果给定 X 、Y 的集合形式，那么也是很容易得到它们的表格形式的。 这里需要注意的是： 公式二也可以用来计算表格形式表示的二维变量的肯德尔相关系是， 不过它一般用来计算由正方形表格表示的二维变量的肯德尔相关系数， 公式三则只是用来计 算由长方形表格表示的二维变量的 Kendall 相关系数。 这里给出公式三种字母 M 的含义， M 表示长方形表格中行数与列数中较小的一个。表 1 的行数及列数均为三。 （2） 适用范围 肯德尔相关系数与斯皮尔曼相关系数对数据的条件要求相同。1.1.2.10 Tanimoto 系数（Tanimoto Coefficient）Tanimoto 系数也称为广义 Jaccard 系数，是 Cosine 相似度的扩展，通常应用于 x 、 y 为布尔向量，即各分量只取 0 或 1 的时候，此时表示的是 x 、 y 的公共特征占 x 、 y 具有的 所有特征的比例。其实质就是集合交集与并集的比。也多用于计算文档数据的相似度，或两 个集合之间的相似程度。范围：[0,1]，越接近 1 说明越相似。1.1.2.11 Jaccard 系数Jaccard 系数主要用于计算符号度量或布尔值度量的个体间的相似度，因为个体的特征属性 都是由符号度量或者布尔值标识，因此无法衡量差异具体值的大小，只能获得“是否相同” 这个结果，所以 Jaccard 系数只关心个体间共同具有的特征是否一致这个问题。如果比较X 与Y 的 Jaccard 相似系数，只比较 xi和yi 中相同的个数，公式如下：也就是关联的交集除以关联的并集。 范围：其值介于[0, 1]之间，如果两个个体间的特征完全相同，交集等于并集，值为 1；如果 没有任何关联，交集为空，值为 0。1.1.3 匹配测度（备注：该节引自项德良【SAR 图像相似度评估技术研究】 ，2012 年国防科大硕士论文 1.2 节。 ） 这种测度常用于医学和生物的分类中。在有些情况下，特征只有两个状态，对象或具有 此特征或不具有此特征。此时，若对象具有此特征，则相应分量定义为 1，而相应分量为 0 表示对象无此特征，这就是所谓的二值特征。对于给定的二值特征矢量 x 和 y 中的某两个 相应分量 xi 和 yi ，若 xi ? 1 和 yi ? 1 ，则称 xi 和 yi 是（1-1）匹配，若 xi ? 1 和 yi ? 0 ，则 称 xi 和 yi 是 （1-0） 匹配； 若 xi ? 0 和 yi ? 1 ， 则称 xi 和 yi 是 （0-1） 匹配； 若 yi ? 0和xi ? 0 ， 则称 xi 和 yi 是（0-0）匹配，令a ? ? xi yi b ? ? yi (1 ? xi )i ic ? ? xi (1 ? yi ) d ? ? (1 ? xi )(1 ? yi ) （1.9）i i则 a 等于两矢量 x 和 y 的(1-1)匹配的特征的数目，b 等于 x 和 y 的(0-1)匹配的特征 的数目，c 等于 x 和 y 的(1-0)匹配的特征的数目，e 等于 x 和 y 的(0-0)匹配的特征的数目。 对于二值 n 维特征矢量可定义如下相似性测度：1.1.3.1Tanimoto 测度a x' y （1.10） ? ' a ? b ? c x x ? y ' y ? x' ys ( x, y ) ?可以看出， s ( x , y )等于 x 和 y 都具有的特征的数目与 x 和 y 分别具有的特征种类 总数之比。这里只考虑(1-1)匹配而不考虑(0-0)匹配。1.1.3.2Rao 测度a x' y ? （1.11） a?b?c?e ns ( x, y ) ?上式等于(1-1)匹配特征数目和所选用的特征数目之比。1.1.3.3简单匹配系数m( x, y ) ? a?e （1.12） n上式表明，这时匹配系数分子为(1-1)匹配特征数目与(0-0)匹配特征数目之和，分母为所选用 的特征数目。1.1.3.4Dice 系数2a 2 x' y （1.13） ? ' 2a ? b ? c x x ? y ' ym( x , y ) ?分子、分母无(0-0)匹配，对(1-1)匹配加权。1.1.3.5Kulzinsky 系数a x' y （1.14） ? ' b ? c x x ? y' y ? 2x' ym( x, y ) ?上式分子为(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 准则侧重人眼的主观感受，它是从图像的客 观信息出发，通过建立模型从而得到的符合人眼视觉的准则。 结构相似度定义如下：l ( x, y ) ?2uxu y ? C12 ux ? u2 y ? C1（1.2.1）l ( x, y ) 为亮度相似度函数，其中 u x ?义的常量。 对比度相似度函数定义如下：1 N? xi ， uy ?i ?1N1 N?yi ?1Ni， C1 为当 ux 、 uy 为零时定c( x, y ) ?2? x? y ? C22 2 ?x ??y ? C2（1.16）其中 ? x ? (1 N 1 N 2 1/ 2 ， ( x ? u ) ) ? ? ( ( yi ? u y )2 )1/ 2 。 C2 也为一个常量。 ? ? i x y N ? 1 i ?1 N ? 1 i ?1结构相似度函数定义如下：s ( x, y ) ?1 N ? ( xi ? ux )( yi ? uy ) 。 N ? 1 i ?1? x y ? C3 （1.17） ? x? y ? C3其中 ? xy ?综上，结构相似度指数(SSIM)定义如下：SSIM ( x, y ) ? ?l ( x, y )? ?c( x, y)? ? s( x, y)? （1.18）? ? ?其中 ?、?、? 均大于 0，为控制三个分量相似度权重的参数。 SSIM ( x , y )越接 近于 1，则表明 x 与 y 越相似，否则越不相似。 近年来基于语义测度的主观相似度准则得到越来越多学者的关注。 该方法一般在图像分 割的基础上， 通过构建图像区域子块与语义元数据之间的统计映射关系， 实现图像内容的统 计语义描述，建立图像之间、图像与语义类别、语义类别之间的分层语义相似测度[23-26]。 该方法充分考虑人眼视觉的语义层面，在图像检索等应用中得到有效验证。1.3 基于像素差值编码的相似度1.3.1 像素差值编码规则给定一幅 SAR 图像 G( J ? K ) ，J 和 K 为图像高度和宽度。 G ( x , y )为图像在( x , y ) 处灰度值。 B 是对应的编码图像，其大小也为 J ? K ， B ( x , y )为 ( x , y )处编码值，定义 如下?1, G( x, y ? 1) ? G( x, y ) （2.1） B ( x, y ) ? ? ?0, 其他式(2.1)中 SAR 图像像素值比较是按从左到右、从上到下的顺序。图 2.1 所示为 SAR 图像编码图示。1.3.2 相似性测度及其概率密度函数G1 和 G2 为待比较的两幅 SAR 图像， B1 和 B2 分别为对应的编码图像，基于像素差值编码的相似性测度(Intensity increment code-IIC)定义如下所示：riic ?1 J K ???B1( x, y) ? B2 ( x, y ) ? (1 ? B1( x, y ))(1 ? B2 ( x, y ))? （2.2） J ? K x ?1 y ?1式(2.2)中， B1 ( x, y ) ， B2 ( x, y ) 分别为编码图像 B1 和 B2 在 ( x , y )处编码值。 riic 衡量 了两幅编码图像的相似性，也即反映了两幅 SAR 图像灰度变化是否一致， 评价：该方法对图像噪声、部分遮挡和一定程度模糊有一定鲁棒性。然而该方法着重统 计全局图像灰度信息，较少考虑图像局部细节，因此对细节丰富的 SAR 图像并不太适用。1.4 基于 KL 距离准则的相似度比较灰度直方图相似性的方法很多，本文采用一种对称 KL 准则 SKLD(Symmetry Kullback-Leibler Divergence)[64]。对两个局部梯度比率直方图 H 和 Q，定义 SKLD 如下：SKLD( H , Q) ? ? pn log(n ?1NN pn q ) ? ? qn log( n ) （3.1） qn pn n ?1其中， pn 和 qn 分别为 H 和 Q 的 MLGRPH 特征矢量，N 为特征矢量的维数。由于相 似度范围为[0,1]，即完全相似时，相似度为 1，此时 SKLD 为 0，当完全不相似时，相似度 为 0，SKLD 为 ?? ，因此这里需要将 SKLD 变换为范围在[0,1]之间的相似度。我们采用最简 单的高斯隶属度函数，如下所示：2 SKLD( H , Q)? ? Similarity ? exp( ? )?2(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 hashing[4,5]算法族里的一个常用方法，基本的思想 是，对于每一个对象的 itemlist，将输入的 item 进行 hash，这样相似的 item 具有很高的相 似度被映射到相同的 buckets 里面， 这样尽量保证了 hash 之后两个对象之间的相似程度和原 来是高相似的， 而 buckets 的数量是远远小于输入的 item 的， 因此又达到降低复杂度的目的。 minhash 方法用 Jaccard 进行相似度的计算方法，则对于两个集合 性的计算方法为：ci 和 c j ， ci 和 c j 的相似sim(ci , c j ) ?ci ? c j ci ? c j（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)也开始崭露头角， 但在实际应用过程中，它却有一些不可避免的缺陷，比如： ? 稀疏性(Sparseness): 对于大词典，尤其是包括了生僻字的词典，文档稀疏性不可避 免； ? 多义词(Polysem): 一词多义在文档中是常见的现象，BOW 模型只统计单词出现的 次数，而忽略了他们之间的区别； ? 同义词(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） ，这样一个文档就能表示成为概念的向量。这样输入一段检索词之后， 就可以先将检索词转换为概念，再通过概念去匹配文档。LSA[6,7]模型认为特征之间存在某种潜在的关联结构， 通过特征-对象矩阵进行统计计算， 将高 维空间映射到低维的潜在语义结构上，构建出 LSA 空间模型，从而提取出潜在的语义结构， 并用该结构表示特征和对象，消除了词汇之间的相关性影响，并降低了数据维度。增强了特 征的鲁棒性 LSA 利用 SVD 分解的数学手段来进行计算，数学过程可以表述如下： 对于 m ? n 的矩阵 A，其中 m 为特征数，n 为样本数。令k ?? min(m, n), rank ( A) ? r, k ? r ，经过奇异值分解，矩阵 A 可分解成 3 个矩阵的乘积：A ? U ?V t其中， U、 V 是 m ? r 和 n ? r 的正交矩阵， 分别称为矩阵 A 的奇异值对应的左、 右奇异向量，?是包含 A 所有奇异值的 r ? r 的对角矩阵，称为 A 的奇异标准形，其对角元素为矩阵 A的奇异值。 奇异值按照递减的排列构成对角矩阵?， 取?中前 k 个最大奇异值构成?k的，取 U 和 V 最前面的 k 列构成 m ? k 的 Uk 和 n ? k 的 Vk，构建 A 的 k-秩矩阵 Ak (m ? n) 。 （LSA 降维的方式就是只取最大的 K 个奇异值，而其他置为 0，于是得到了共生矩阵的近似。 ）Ak ? U k ? VkTk其中，Uk 和 Vk 中的行向量分别作为特征向量和对象向量，k 是降维后的维数。 下图形象的展示了 LSA 的过程：LSA 的优点 ? 低维空间表示可以刻画同义词，同义词会对应着相同或相似的主题； ? 降维可去除部分噪声，是特征更鲁棒； ? 充分利用冗余数据； ? 无监督/完全自动化； ? 与语言无关； LSA 的不足 ? 没有刻画 term 出现次数的概率模型； ? 无法解决多义词的问题；?? ? ? ?SVD 的优化目标基于 L-2 norm 或者是 Frobenius Norm 的，这相当于隐含了对数据的高 斯噪声假设。而 term 出现的次数是非负的，这明显不符合 Gaussian 假设，而更接近 Multi-nomial 分布； 对于 count vectors 而言，欧式距离表达是不合适的（重建时会产生负数） ； 特征向量的方向没有对应的物理解释； SVD 的计算复杂度很高，而且当有新的文档来到时，若要更新模型需重新训练； 维数的选择是 ad-hoc 的；1.6.2 plas 介绍PLSA 和 LSA 基础思想是相同的，都是希望能从 term 中抽象出概念，但是具体实现的方法不相[8,9]模型 是由 Hofmann 提出的用于文本检索的概率生成模型，与相比较于 LSA，PLSA 是基于概率模 型的，并直接引入了潜在 class 变量 z∈Z=｛Z1…Zk｝ ，下面的用文本处理语言来描述该模型。同。PLSA 使用了概率模型，并且使用 EM 算法来估计 P（t|c）和 P（c|d）矩阵。 PLSAdzw图4-1 PLS 模型 选定一篇文档的概率 p(d)，每篇文档以概率 p(z|d)属于一个主题，而给定一个主题，每一个 词以概率 p(w|z) 产生。将这个过程形成联合的概率模型表达式：p(d , w) ? p(d ) p( w | d ) （7）p( w | d ) ? ? z?Z p( w | z ) p( z | d ) （8）则：p(d , w) ? ?z?Z p( z) p( w | z) p(d | z) （9）在 PLSA 实际的使用过程中，存在着 overfit 的风险，一般训练过程是通过 EM 算法，进行模 型参数训练，获得 p(z|d)、p(w|z)概率。 PLSA 和其相关的变形，在分类、聚类、检索等方面，特征相关性计算等方面，获得 了广泛的应用，并取得了比较好的效果。 pLSA 的优势 ? 定义了概率模型，而且每个变量以及相应的概率分布和条件概率分布都有明确的物 理解释；相比于 LSA 隐含了高斯分布假设，pLSA 隐含的 Multi-nomial 分布假设更符合文本特 性； ? pLSA 的优化目标是是 KL-divergence 最小，而不是依赖于最小均方误差等准则； ? 可以利用各种 model selection 和 complexity control 准则来确定 topic 的维数； pLSA 的不足 ? 概率模型不够完备：在 document 层面上没有提供合适的概率模型，使得 pLSA 并不 是完备的生成式模型， 而必须在确定 document i 的情况下才能对模型进行随机抽样； ? 随着 document 和 term 个数的增加，pLSA 模型也线性增加，变得越来越庞大； ? 当一个新的 document 来到时，没有一个好的方式得到$p(d_i)$; ? EM 算法需要反复的迭代，需要很大计算量； 针对 pLSA 的不足，研究者们又提出了各种各样的 topic based model, 其中包括大名鼎鼎 的 Latent Dirichlet Allocation (LDA)。?1.6.3 小结主题方法的引入，在一定程度上弥补了 BOW 的假设的独立性，在工业中，主题的方法 也越来越多的应用到实际的机器学习中，包括在图像处理领域、传统的分类、聚类、检索等 方面，都取得了比较好的效果。 相似度的计算在数据挖掘方面有着广泛的应用， 根据不同的应用场景， 各种方法各有其 优劣特点，对于相似度效果的影响，除了方法本身之外，合理有效的特征的选择和使用也是 至关重要的，同时，根据应用场景的不同，选择合理的方法，对于解决问题，有着重要的作 用。1.7 图像相似度相关分类1.7.1 图像相似度的概念图像相似度的概念可以总结如下 1-1.图像的相似度取决于图像上具体内容的相似程度,如通过像素级比较或某些特定点的比 较和分析得到相似度。 1-2.基于语义相似度的图像相似度计算,通过图像空间上下文和情景上下文的联系,得到图像 的一些基本信息进行比较,它是图像目标实体的高层联系,抽象程度高,理论还不成熟。 1-3.计算将一个图转换成另一个图的花费,即预先定义各种变换的操作集合,将两个图之间的 最小变化步骤定义为两图的相似度,即图像编辑距离。 1-4.将图像结构化,通过计算公式得出两图的最大公共子图,该公共子图能最大的表达两个图 的共有信息,定义最大公共子图为两图的相似度。 1-5.定义一个大图可以同时包含两个图像,称为两图的最大关联图,从关联图中获得最大子团 表示两图的相似度。 1-6.将图像分解成若干部分,分别计算各个部分的相似度,再综合得到整个图像的相似度。1.7.2 图像相似度的分类根据相似度计算参考的原理不同,可将图像相似度算法分为三大类。 1、基于像素灰度相关的相似度算法，如直方图法等。 2、基于图像特征点的相似度算法:该算法抗干扰能力强。 3、基于特定理论的图像相似度算法:这一类的算法在图像拓扑结构的基础上进行，但没 有一个特定的定义。如基于相似度矩阵的算法,利用图节点区域的相似度,迭代计算得出总体 相似度;基于最大子图或关联图的相似度算法等,这类算法因所处理的图像类型的不同而各有 优劣,图像拓扑结构作为图像稳定性特征之一,使得这类算法具有较好的鲁棒性,关于这一方 面的研究还仍有待继续努力。1.7.2.1 直方图匹配。比如有图像 A 和图像 B，分别计算两幅图像的直方图，HistA，HistB，然后计算两个直方 图的归一化相关系数（巴氏距离，直方图相交距离）等等。 这种思想是基于简单的数学上的向量之间的差异来进行图像相似程度的度量，这种方法 是目前用的比较多的一种方法，第一，直方图能够很好的归一化，比如通常的 256 个 bin 条 的。 那么两幅分辨率不同的图像可以直接通过计算直方图来计算相似度很方便。 而且计算量 比较小。 这种方法的缺点: 1、直方图反映的是图像像素灰度值的概率分布，比如灰度值为 200 的像素有多少个， 但是对于这些像素原来的位置在直方图中并没有体现， 所以图像的骨架， 也就是图像内部到 底存在什么样的物体， 形状是什么， 每一块的灰度分布式什么样的这些在直方图信息中是被 省略掉得。 那么造成的一个问题就是， 比如一个上黑下白的图像和上白下黑的图像其直方图 分布是一模一样的，其相似度为 100%。 2、两幅图像之间的距离度量，采用的是巴氏距离或者归一化相关系数，这种用分析数 学向量的方法去分析图像本身就是一个很不好的办法。 3、就信息量的道理来说，采用一个数值来判断两幅图像的相似程度本身就是一个信息 压缩的过程，那么两个 256 个元素的向量（假定直方图有 256 个 bin 条）的距离用一个数值 表示那么肯定就会存在不准确性。 改进： 1， FragTrack 算法，其对图像分成横纵的小块，然后对于每一个分块搜索与之最匹配 的直方图。 来计算两幅图像的相似度， 融入了直方图对应位置的信息。 但是计算效率上很慢。 2，计算一个图像外包多边形，得到跟踪图像的前景图后计算其外包多边形，根据外包 多边形做 Delauny 三角形分解，然后计算每个三角形内部的直方图，对于这两个直方图组进 行相似距离计算。这样就融入了直方图的位置信息1.7.2.2基于矩阵分解的方法方法描述：将图像 patch 做矩阵分解，比如 SVD 奇异值分解和 NMF 非负矩阵分解等，然后 再做相似度的计算。方法思想： 因为图像本身来讲就是一个矩阵， 可以依靠矩阵分解获取一些更加鲁棒的特征来 对图像进行相似度的计算。 基于 SVD 分解的方法优点：奇异值的稳定性，比例不变性，旋转不变性和压缩性。即奇异 值分解是基于整体的表示，不但具有正交变换、旋转、位移、镜像映射等代数和几何上的不 变性,而且具有良好的稳定性和抗噪性，广泛应用于模式识别与图像分析中。对图像进行奇 异值分解的目的是得到唯一、稳定的特征描述，降低特征空间的维度，提高抗干扰能力。 基于 SVD 分解的方法缺点是：奇异值分解得到的奇异矢量中有负数存在，不能很好的解释 其物理意义。 基于 NMF 分解的方法：将非负矩阵分解为可以体现图像主要信息的基矩阵与系数矩阵，并 且可以对基矩阵赋予很好的解释，比如对人脸的分割，得到的基向量就是人的“眼睛”、“鼻 子”等主要概念特征，源图像表示为基矩阵的加权组合，所以，NMF 在人脸识别场合发挥着 巨大的作用。 基于矩阵特征值计算的方法还有很多，比如 Trace 变换，不变矩计算等。1.7.2.3基于特征点方法方法描述：统计两个图像 patch 中匹配的特征点数，如果相似的特征点数比例最大，则认为 最相似，最匹配 方法思想：图像可以中特征点来描述，比如 sift 特征点，LK 光流法中的角点等等。这样相似 度的测量就转变为特征点的匹配了。 以前做过一些实验，关于特征点匹配的，对一幅图像进行仿射变换，然后匹配两者之间的特 征点，选取的特征点有 sift 和快速的 sift 变形版本 surf 等。 方法优点：能被选作特征点的大致要满足不变性，尺度不变性，旋转不变等。这样图像的相 似度计算也就具备了这些不变性。 方法缺点：特征点的匹配计算速度比较慢，同时特征点也有可能出现错误匹配的现象。1.7.2.4基于峰值信噪比（PSNR）的方法当我们想检查压缩视频带来的细微差异的时候， 就需要构建一个能够逐帧比较差视频差异的 系统。最常用的比较算法是 PSNR( Peak signal-to-noise ratio)。这是个使用“局部均值误差”来 判断差异的最简单的方法，假设有这两幅图像：I1和 I2，它们的行列数分别是 i，j，有 c 个 通道。每个像素的每个通道的值占用一个字节，值域[0,255]。注意当两幅图像的相同的话， MSE 的值会变成0。这样会导致 PSNR 的公式会除以0而变得没有意义。所以我们需要单独的 处理这样的特殊情况。 此外由于像素的动态范围很广， 在处理时会使用对数变换来缩小范围。在考察压缩后的视频时，这个值大约在 30 到 50 之间，数字越大则表明压缩质量越好。 如果图像差异很明显， 就可能会得到 15 甚至更低的值。 PSNR 算法简单， 检查的速度也很快。 但是其呈现的差异值有时候和人的主观感受不成比例。 所以有另外一种称作结构相似性的算法做出了这方面的改进。1.7.2.5图像模板匹配一般而言，源图像与模板图像 patch 尺寸一样的话，可以直接使用上面介绍的图像相似 度测量的方法；如果源图像与模板图像尺寸不一样，通常需要进行滑动匹配窗口，扫面个整 幅图像获得最好的匹配 patch。 在 OpenCV 中对应的函数为：matchTemplate()：函数功能是在输入图像中滑动窗口寻找 各个位置与模板图像 patch 的相似度。相似度的评价标准（匹配方法）有：CV_TM_SQDIFF 平方差匹配法（相似度越高，值越小） ，CV_TM_CCORR 相关匹配法（采用乘法操作，相似度 越高值越大） ，CV_TM_CCOEFF 相关系数匹配法（1表示最好的匹配，-1表示最差的匹配） 。 CV_TM_SQDIFF 计算公式：CV_TM_CCORR 计算公式：有一种新的用来计算相似度或者进行距离度量的方法：EMD，Earth Mover's Distances EMD is defined as the minimal cost that must be paid to transform one histograminto the other, where there is a “ground distance” between the basic featuresthat are aggregated into the histogram。 光线变化能引起图像颜色值的漂移， 尽管漂移没有改变颜色直方图的形状， 但漂移引起 了颜色值位置的变化，从而可能导致匹配策略失效。而 EMD 是一种度量准则，度量怎样将 一个直方图转变为另一个直方图的形状， 包括移动直方图的部分 （或全部） 到一个新的位置， 可以在任意维度的直方图上进行这种度量。 在 OpenCV 中有相应的计算方法：cvCalcEMD2()。结合着 opencv 支持库，计算直方图均 衡后与原图的 HSV 颜色空间直方图之间的 EMD 距离。1.7.2.6基于特定理论的图像相似度算法这一类的相似度算法大都是建立在图结构的基础上进行的。 假定分割后的图像其区域都 具有独立性和唯一性,那么通过属性特征提取和区域空间关系的描述,就可以把图像对应地描 述成图结构。因此,对图结构的相似度计算就可以从一定程度上代表图像之间的相似情况。1.7.2.6.1 相似度传播法为了计算图的相似度,文献[34]提出了这样一个理论,如果两个图节点的邻居节点是相似 的,则这两个节点也是相似的。换句话说,这两个节点的相似度的一部分传播给了它们各自的邻居。这样经过一系列的迭代,这种相似度就会传遍整个图,从而我们就可以得出两个图的最 终整体相似度。因此,根据这种相似度观点,可以对两个图构造出一个相似度矩阵,将图中两两 节点间的相似度都当成矩阵的一个元素,然后通过矩阵的相关运算,得出最终的一个相似度计 算公式。其过程可为如下所示:相似度矩阵是用于描述图结构的相似程度的一个整体情况的有效工具,最早是在 UUman 的算法中进行定义,而在随后的各种算法中也得到了很好的应用。相似度传播算法是基于矩 阵的基本运算来进行的,矩阵运算是单纯的数学运算,从数学运算的角度上去比较两个图之间 的相似度,虽然简便了很多,但同时也容易丢失图像的信息。因此,该算法准确性方面还不够。1.7.2.6.2 基于关联图的相似度算法1.7.2.6.3 基于最大公共子图的相似度算法1.7.2.6.4 节点迭代匹配算法参照整体相似度等于各部分相似度之和的原则,节点迭代匹配算法提出了图像匹配错误 等于节点错误和对应边错误之和的思想_。 该算法将匹配过程进行了 K 次的迭代,K 由图节点数决定。通过 k 次的迭代,可以获得匹配错误最小的两图之间的节点匹配,并计算出其匹配错 误。 首先必须定义几个矩阵分别用来表示节点的错误差,可能的节点匹配对等。接着还要定 义节点匹配错误的计算公式和边匹配错误计算公式,最后依据匹配错误的大小来确定两个图 的相似度。将这种图匹配算法应用于图像检索,取得了很好的实验效果如图 1-7 所示的是两 个图像的属性图结构。通过计算可以得到图 1-7 示例中两幅图像的匹配错误,并依此进行图像的搜索或匹配。 但同时可以发现该算法存在不足之处,它无法给出两幅图像的确切的相似度,仅能给出其匹配 错误,无法定量的描述其相似程度,这也是该算法应要进一步改善的地方1.8 基于本体的语义相似度测度算法基于本体的语义相似度算法主要包括概念信息量法，语义距离法、基于属性的语义相似度、 混合式语义相似度等方法。1.8.1 概念信息量法：概念信息量法以信息论和概率统计为基础，需要进行大量的文集统计工作。1.8.2 基于概念属性的相似度计算在本体结构中，概念的属性是决定语义相似度的重要因素［１４］ 。当两个概念拥有的相同属性 越多，表明这两个概念间的语义相似度越大。概念属性的相似度计算公式为：Sim Att ( S , F ) ?Count (att ( S ) ? att ( F )) （1） Count (att ( S ) ? att ( F ))其中， att ( S ) 表示实体 S 属性的集合； att ( F ) 表示实体 F 属性的集合； Count () 表示统计出的属性个数。若实体的某种相应的性质不存在时，则不用表示 S 、 F 在该性质上的相似 度。1.8.3语义距离语义距离是指本体结构中任意两个概念节点之间的最短路径长度。 基本假设如下：两概念的语义距离越大，其相似度越低，反之相似度越高。 设实体 a、b 分别对应语义知识库中的概念 con1、con2，记 sim_sem(con1,con2)为二者 的语义相似度，因此 sim_sem(a,b)=sim_sem(con1,con2)。 设 Dist(con1,con2)为本体中两概念的最短语义距离，则语义相似度与语义距离之间存在 如下关系： （1） 当 Dist(con1,con2)=0 时，sim_sem(con1,con2)=1，表示完全相同。 （2） 当 Dist(con1,con2)等于无穷大时，sim_sem(con1,con2)=0，表示完全不相似或不 相关。 用公式表示如下：sim_sem(a,b)=sim_sem(con1,con2)=d （4） Dist (con1,con2)+d2基于语义距离的语义相似度算法中,影响语义的主要因子有:概念深度,概念密度,关系类 型,关联强度和概念属性等。本文主要对前三者进行介绍。 概念深度： 概念深度指概念节点与根节点的最短路径中包括的边数.概念深度对语义相似度的影响 基于以下思想:以 “IS-A” 关系建立的本体概念树中,每一概念是其上位概念的细化,越到下层, 概念所指的对象越具体,内涵越丰富.同等语义距离下,两个概念节点的深度越大,相似度越高, 反之相似度越低;相反,同等语义距离下二者的概念层次差越小,则二者的语义相似度越高,反 之相似度越低. 定义 Dep(con) 为概念 con 的深度;设 root 为根节点,令其深度为１,即 Dep(root)＝１. 任意非根节点概念 con 的深度 Dep(con)＝Dep(Parent(con))＋１,其中 Parent(con)为 con 的直接上位概念节点。 Dep(tree)为本体树的深度， Deep(tree) ? max( Dep(coni )),(i ? 1,2,...n) ,其中 n 为概 念的总数, coni 为本体中的任意概念. 因此,概念深度对语义相似度影响因子 Ps 的计算如式(５),且满足 Ps∈(０,１]Ps ?Dep(con1 ) ? Dep(con2 ) Dep(con1 ) ? Dep(con2 ) ? 2 Dep(tree)(5)概念密度: 本体层次中,局部区域概念密度越大,说明该区域概念细化程度越大,该处概念分类越具 体,在其他因素相同的条件下,直接概念子节点间的语义相似度就越高. 定义Child(con)为概念con所包含的直接子节点的个数;Child(tree)为本体树中各概念节点 中子节点数的最大值.设两个概念con１和con２最近共同祖先为cona ,其直接子节点的个数为 Child (cona ) ;则概念密度对语义相似度影响因子 Pm 计算如式(６),且满足Pm ∈(０,１]Pm ?Child (cona ) （6） Child (tree)关系类型： 本体中概念通过各种关系联系在一起,不同关系类型对概念语义相似度的影响也有所不 同.如上下位的“同义关系”所表征的语义相似度应大于“整体--部分”关系所表征的语义相 似度.在关系类型不多的情况下,可采用专家打分的方法来确定关系类型的语义强度.设Pr 为 关系强度,则Pr∈(０,１]1.8.4 改进的语义相似度算法改善算法1： sim _ sem(a, b) ? (d )? ? Ps ? ? Pm? ? Pr? Dist (con1,con 2 )+d2(7)式中， ? , ? , ? , ? 为调节因子，且满足 ? ? ? ? ? ? ? ? 1 。由于语义距离在相似度计算中占 主导地位,其他因子起辅助作用,所以 ? 的权重相对较大,而 ? 、 ? 、 ? 的权重相对较小.该语 义相似度模型中权重大小的设置,除遵循上述原则外,可采用与用户交互或大样本数据进行训 练的方法对初始权重进行修正,以满足不同上下文应用环境的要求. 改善算法2：Weight( S, F ) ? ? ?Weight Type (S , F ) ? ? ?Weight Depth (S , F ) ? ? ?Weight Density (S , F )() 其中，Weight ( S , F ) 为有向边权重；Weight Type ( S, F ) 是概念的不同的（关系类型）对应的 语义距离的权重； Weight Depth ( S , F ) 是概念结点 S、F 之间的（概念深度）语义距离权重；Weight Density ( S, F ) 表示概念节点 S、F 之间有向边（概念密度）的权重关系；α、β、γ是可调节因子，且α＋β＋γ＝１。 由于有向边权重的大小与概念节点间的距离成反比， 因此权重大小与有向边语义距离的 关系如下：Dist(S,F)=1 Weight ( S , F )(3)其中， Dist(S,F) 为概念节点间的距离。 综上所述，可得到的改进的语义距离相似度计算方法如下：sim_sem(a,b)=sim_sem(con1,con2)=?Dist (con1,con2)+?2（4）其中， SimDist (S,F) 为语义距离相似度； ? 为可调节因子，且为大于 0 的实数。1.8.5 语义相似度计算将基于语义距离的方法与基于属性的方法相结合，可以得到实体语义相似度计算公式:Sim(S,F)=?1 ? SimAtt (S,F)+?2 ? SimDist (S,F) （5）其中， Sim(S,F) 为实体语义相似度， ?1 +?2 ? 1 ，且 ?1、?2 大于 0。1.9 文本语义相似度模型1.9.1 基于 V SM 的相似度模型1.9.2 基于 WordNet 的相似度模型1.9.3 基于 FrameNet 的相似度模型
1.9.4 基于树核函数的相似度模型
赞助商链接}