机器学习-相似度度量

13计算机技术Xxxxxxxxxxx目录相似性度量主要相似度度量算法度量学习部分算法实践机器学习相似度概述流形学习相似性度量机器学习相似度概述相似度度量机器学习的目的就是让机器具有类似于人类的学习、认识、理解事物的能力。计算机对大量的数据记录进行归纳和总结，发现数据中潜在的规律，给人们的生活带来便利。对数据记录和总结中常用到聚类算法。聚类算法就是按照对象间的相似性进行分组，因此如何描述对象间相似性是聚类的重要问题。相似度度量机器学习相似度概述相似度度量刻画数据样本点之间的亲疏远近程度主要有以下两类函数：（1）相似系数函数：两个样本点愈相似，则相似系数值愈接近1；样本点愈不相似，则相似系数值愈接近0。这样就可以使用相似系数值来刻画样本点性质的相似性。（2）距离函数：可以把每个样本点看作高维空间中的一个点，进而使用某种距离来表示样本点之间的相似性，距离较近的样本点性质较相似，距离较远的样本点则差异较大。相似度度量机器学习相似度概述主要相似度算法机器学习相似度概述主要相似度算法欧氏距离标准化欧氏距离闵可夫斯基距离曼哈顿距离切比雪夫距离马氏距离汉明距离夹角余弦杰卡德距离&杰卡德相似系数主要相似度算法机器学习相似度概述欧式距离欧氏距离（Euclideandistance）也称欧几里得距离，它是一个通常采用的距离定义，它是在m维空间中两个点之间的真实距离。也可以用表示成向量运算的形式：主要相似度算法机器学习相似度概述标准欧式距离由于特征向量的各分量的量纲不一致(比如说身高和体重)，通常需要先对各分量进行标准化，使其与单位无关。假设样本集X的均值(mean)为m，标准差(standarddeviation)为s，那么X的“标准化变量”表示为：（160cm，60kg）（170cm，50kg）标准化后的值=(标准化前的值－分量的均值)/分量的标准差主要相似度算法机器学习相似度概述加权欧式距离加权欧式距离：在距离计算时，考虑各项具有不同的权重。公式如下：主要相似度算法机器学习相似度概述曼哈顿距离曼哈顿距离，也称为城市街区距离，是一种使用在几何度量空间的几何学用语，用以标明两个点在标准坐标系上的绝对轴距总和：X(2,4),Y(1,6)dist(X,Y)=|2-1|+|4-6|=3主要相似度算法机器学习相似度概述闵可夫斯基距离闵可夫斯基距离（闵氏距离）不是一种距离，而是一组距离的定义。闵氏距离是欧氏距离的推广，是对多个距离度量公式的概括性的表述。公式如下：其中p是一个变参数。当p=1时，就是曼哈顿距离；当p=2时，就是欧氏距离；当p→∞时，就是切比雪夫距离。根据变参数的不同，闵氏距离可以表示一类的距离主要相似度算法机器学习相似度概述切比雪夫距离切比雪夫距离是由一致范数（或称为上确界范数）所衍生的度量，也是超凸度量的一种。在数学中，切比雪夫距离(L∞度量)是向量空间中的一种度量，二个点之间的距离定义是其各坐标数值差的最大值。X(2,4),Y(1,6)dist(X,Y)=max{|2-1|,|4-6|}=2主要相似度算法机器学习相似度概述马氏距离表示数据的协方差距离。它是一种有效的计算两个未知样本集的相似度的方法。与欧式距离不同的是它考虑到各种特性之间的联系（例如：一条关于身高的信息会带来一条关于体重的信息，因为两者是有关联的）并且是尺度无关的)，即独立于测量尺度。C为X,Y的协方差矩阵，如果协方差矩阵为单位矩阵,那么马氏距离就简化为欧式距离,如果协方差矩阵为对角阵,则其也可称为正规化的欧氏距离。主要相似度算法机器学习相似度概述汉明距离两个等长字符串s1与s2之间的汉明距离定义为将其中一个变为另外一个所需要作的最小替换次数。例如字符串“1111”与“1001”之间的汉明距离为2。汉明距离就是表示X,Y取值不同的分量数目。只适用分量只取-1或1的情况。主要相似度算法机器学习相似度概述杰卡德相似系数&杰卡德距离卡德距离：是与杰卡德相似系数相反的概念，杰卡德距离用两个集合中不同元素占所有元素的比例来衡量两个集合的区分度。杰卡德距离可用如下公式表示：杰卡德相似系数：两个集合A和B的交集元素在A，B的并集中所占的比例，称为两个集合的杰卡德相似系数，用符号J(A,B)表示。杰卡德相似系数是衡量两个集合的相似度一种指标。主要相似度算法机器学习相似度概述杰卡德相似系数&杰卡德距离例如，A（0,1,1,0）和B（1,0,1,1）。我们将样本看成一个集合，1表示集合包含该元素，0表示集合不包含该元素。p：样本A与B都是1的维度的个数q：样本A是1而B是0的维度的个数r：样本A是0而B是1的维度的个数s：样本A与B都是0的维度的个数那么样本A与B的杰卡德相似系数可以表示为：此处分母之所以不加s的原因在于：对于杰卡德相似系数或杰卡德距离来说，它处理的都是非对称二元变量。非对称的意思是指状态的两个输出不是同等重要的。主要相似度算法机器学习相似度概述余弦相似度余弦相似度用向量空间中两个向量夹角的余弦值作为衡量两个个体间差异的大小。相比距离度量，余弦相似度更加注重两个向量在方向上的差异，而非距离或长度上。主要相似度算法机器学习相似度概述调整余弦相似度余弦相似度更多的是从方向上区分差异，而对绝对的数值不敏感，因此没法衡量每个维度上数值的差异。需要修正这种不合理性，就出现了调整余弦相似度，即所有维度上的数值都减去一个均值。用户对内容评分，按5分制，X和Y两个用户对两个内容的评分分别为（1,2）和（4,5），使用余弦相似度得到的结果是0.98，两者极为相似。但从评分上看X似乎不喜欢两个这个内容，而Y则比较喜欢。比如X和Y的评分均值都是3，那么调整后为(-2,-1)和(1,2)，再用余弦相似度计算，得到-0.8，相似度为负值并且差异不小，但显然更加符合现实。主要相似度算法机器学习相似度概述皮尔森相似度|调整余弦相似度|=|皮尔森相似度|主要相似度算法机器学习相似度概述斯皮尔曼相关斯皮尔曼相关性可以理解为是排列后（Rank）用户喜好值之间的Pearson相关度。皮尔曼相关度的计算舍弃了一些重要信息，即真实的评分值。但它保留了用户喜好值的本质特性——排序（ordering），它是建立在排序（或等级，Rank）的基础上计算的。主要相似度算法机器学习相似度概述度量学习机器学习相似度概述度量学习现有的大部分算法对图像进行特征提取后化为向量的表达形式，其本质是把每一幅用于训练的图像通过某种映射到欧氏空间的一个点，并利用欧氏空间的良好性质在其中进行学习器的训练。但定义图像特征之间的欧氏距离未必能很好反映出样本之间的相似。通过训练样本寻找一种能够合理描述当前样本相似度的距离度量，能够大大提高学习器的性能。度量学习是机器学习的一个重要分支，通过有标记样本或结合未标记样本，寻找一个能够在给定指标下最恰当刻画样本相似度的距离矩阵或距离函数。度量学习机器学习相似度概述度量学习度量学习包括监督度量学习和半监督度量学习。监督度量学习主要是利用标注样本学习一个反映样本语义关系的度量函数，使语义上相近的样本之间距离较近，反之则较远。半监督度量学习则是利用了标注样本，也利用了未标注样本。度量学习机器学习相似度概述监督度量学习利用携带标注信息的训练数据进行距离度量学习，能更好的降低“语义鸿沟”的影响。监督的距离度量学习的主要思想是，利用标注数据学习一个度量矩阵，对样本进行映射变换，使得在变换后的度量空间中，同类样本之间的距离变小，异类样本之间的距离变大，或使得相似的样本距离变小，不相似的样本距离变大。可以通过设定不同的标注信息，使得距离度量结果符合不同的相似度评判标准，因此度量方式的选择更加自由。度量学习机器学习相似度概述监督度量学习（1）基于凸规划的全局距离度量学习方法：该方法学习一个度量矩阵，使非相似样本间距离的平方和最大，同时使相似样本间距离的平方和小于一定值。（2）近邻成分分析：以概率的方式定义点的软邻域，然后通过最大化训练样本的留一法分类错误率学习距离度量矩阵。该方法在训练度量矩阵的同时，保持了相邻数据点之间关系，但不一定能全局最优。（3）区分性成分分析：通过学习一种最优的数据转换使不同“团簇”间的方差和最大，所有“团簇”内的方差和最小。度量学习机器学习相似度概述(1)E.P.Xing,A.Y.Ng,M.I.Jordan,S.Russell．DistanceMetricLearningwithApplicationtoClusteringwithSide-information[J].AdvancesinNeuralInformationProcessingSystems,2002,15:505-512.(2)J.Goldberger,S.Roweis,G.Hinton,R.Salakhutdinov．Neighbourhoodcomponentsanalysis[A].InAdvancesinNeuralInformationProcessingSystems[C].Washington,MITPress,2004:13-18.(3)S.C.H.Hoi,W.Liu,M.R.Lyu,W.Y.Ma．Learningdistancemetricswithcontextualconstraintsforimageretrieval[A].Proceedingsofthe2006IEEEComputerSocietyConferenceonComputerVisionandPatternRecognition[C].Vienna,Austria,2006:2072-2078.监督度量学习（4）基于信息论的距离度量学习方法：在满足约束信息的同时，使学习到的度量矩阵M和根据某种先验知识给出的度量矩阵M0之间的KL散度最小。（5）最大边界近邻分类：分类方法是将样本的K最近邻保持在同一类别中，同时使异类样本之间的边界最大。其损失函数的第一项是惩罚输入样本和其最近邻间的距离，第二项是惩罚异类样本间较小的距离。度量学习机器学习相似度概述(4)J.V.Jason.Davis,B.Kulis,P.Jain,etal．Information-theoreticmetriclearning[A].InProceedingsoftheInternationalConferenceonMachineLearning[C].Florida,USA,2007:209-216.(5)K.Q.Weinberger,J.Blitzer,L.K.Saul．Distancemetriclearningforlargemarginnearestneighborclassification[J].JournalofMachineLearningResearch,2009(10):207-244.(6)吕秀清，图像度量学习技术[D]，2013半监督度量学习监督度量学习只利用了有限的标注数据，且常会遇到训练数据不足的问题，而实际中却有大量未标注的数据存在。半监督度量学习通过对未标注数据加以利用，以获得更准确的模型。（1）07年，一种基于核的半监督距离度量学习方法（2）09年，通过保留类似于LLE局部线性嵌嵌入）的局部关系学习距离度量（3）Laplacian正则化距离度量学习（LRML），将样本点的近邻看作相似点，联合已有标注数据学习距离度量。度量学习机器学习相似度概述(1)D.Yeung,H.Chang．Akernelapproachforsemi-supervisedmetriclearning[J].IEEETransactionsonNeuralNet-works,2007,18(1):141–149.(2)M.Baghshah,S.Shouraki．Semi-supervisedmetriclearningusingpairwiseconstraints[A].Proceedingsofthe21stinternationaljontconferenceonArtificalintelligence[C].Pasadena,California