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?Vt
其中，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?Uk?VkT
k其中，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中抽象出概念，但是具体实现的方法不相同。PLSA使用了概率模型，并且使用EM算法来估计P（t|c）和P（c|d）矩阵。 PLSA[8,9]模型是由Hofmann提出的用于文本检索的概率生成模型，与相比较于LSA，PLSA是基于概率模型的，并直接引入了潜在class变量 z∈Z=｛Z1…Zk｝，下面的用文本处理语言来描述该模型。 dzw 图4-1 PLS模型 选定一篇文档的概率p(d)，每篇文档以概率p(z|d)属于一个主题，而给定一个主题，每一个词以概率p(w|z) 产生。将这个过程形成联合的概率模型表达式： p(d,w)?p(d)p(w|d)（7）
p(w|d)??z?Zp(w|z)p(z|d)（8）
则：
p(d,w)??z?Zp(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非负矩阵分解等，然后再做相似度的计算。