爱做片视频网站,今天特大新闻最新消息,网站搭建推广优化,wordpress ueeshop论文里面看到了谱哈希用来找子集的用处#xff0c;不管有没有用#xff0c;先转再说
原文地址#xff1a;http://blog.sina.com.cn/s/blog_67914f290101d2xp.html
最近看了有关谱哈希的一些东西#xff0c;记录一下备忘。理解十分粗浅#xff0c;敬请各位大牛指导。 一、…论文里面看到了谱哈希用来找子集的用处不管有没有用先转再说
原文地址http://blog.sina.com.cn/s/blog_67914f290101d2xp.html
最近看了有关谱哈希的一些东西记录一下备忘。理解十分粗浅敬请各位大牛指导。
一、基本概念语义哈希(semantic hashing)是为每个对象图像或文本寻找一种二进制编码使两个对象的相似度与其编码之间的海明距离相关即相似度高的对象对应的编码海明距离小相似度低的对象对应的编码海明距离大。而为每个对象寻找这么一个最优化的编码是NP难解问题通过松弛优化条件得到一种谱问题这个问题的结果是拉普拉斯算子的特征向量的一个子集。这种对松弛后问题的解决方法就是谱哈希。二、计算编码好的编码要满足以下条件容易计算短但能表示整个数据集其海明距离与原对象之间的相似度相关。松弛后谱问题的结果是带权拉普拉斯-贝尔特拉米算子的特征方程通过构造这样的特征方程并计算其前k个最小的特征值最后所得到的编码与特征值相关。整个过程涉及比较高级的数学知识超过了我的知识范围因此理解的十分粗浅。三、源码分析PDF和源码的下载地址http://www.cs.huji.ac.il/~yweiss/SpectralHashing/源码中与谱哈希相关的主要有以下几个文件trainSH.mcompressSH.mdistMat.mhammingDist.mevaluation.m。下面一一介绍。1、trainSH.m。输入数据矩阵每一行代表一个点通过训练得到谱哈希中所需的若干参数包括对数据矩阵的PCA主成分分析处理及生成特征方程。主成分分析是一种对数据降维的方法减少数据量的同时能尽量避免有用信息的流失。对一个矩阵提取主成分即对矩阵中的每一行对应的向量提取主成分对一个数据矩阵每一行即每一数据点可看做所有随机变量的一次取值而每一列即每一维可看做一个随机变量只看矩阵中的其中一行不妨设第一行其元素值为x1,x2,…,xd则其主成分是d个随机变量的一个线性组合即ai1x1ai2x2…aidxd而ai1,ai2,…,aid是随机变量X1,X2,…,Xd的相关矩阵的第i个特征向量。因此计算矩阵X的协方差矩阵矩阵X有d列代表d维也代表d个随机变量协方差矩阵中元素即是d个随机变量两两之间的协方差Cov矩阵Cov为d*d矩阵计算矩阵Cov的特征向量和特征值并从大到小取出前k个特征值对应的特征向量组成变换矩阵TT为d*k矩阵计算X*T即提取出X的前k个主成分因为X*T是s*k矩阵s为矩阵X原先的长度故X由原先的d维降到了k维并且这k维包含了X最多的信息。原文中说选取了从小到大的k个特征值而源码实现中选取了从大到小的k个特征值源码实现中应该是正确的选择也许我对原文理解有误如果有熟悉谱哈希的希望同志们能留言相告。2、compressSH.m。输入数据矩阵和参数来自trainSH.m的输出输出U和B。U是k个特征方程的值是个s*k的矩阵每一行代表一个数据点每一列代表一个特征方程的值用来生成二进制编码。B是s*ceil(k/8)的矩阵其中B(i,j)的值等于矩阵U的第i行的第(j-1)*81到第j*8个元素如j1则是第1到第8个元素j2则是第9到第16个元素以此类推的压缩十进制值。即先将矩阵U的元素按其正负转换成1和0正对应1负对应0然后将8个01值转换成十进制即得到B中的元素值8个01值中维度较低的值处于低位维度高的值处于高位。比如U的第一行的前八个数为1,-0.7,-0.5,1,0.3,-0.4,0.2,1转换后为10011011左边为低位右边为高位转换成十进制数位217则B(1,1)217。3、hammingDist.m。输入B1B2compressSH.m的输出设B1为s1*ceil(k/8)矩阵B2为s2*ceil(k/8)矩阵则输出为s1*s2矩阵D其中D(i,j)为B1第i行与B2第j行的海明距离DcompressDist(B1,B2)。设B1第1行为12 14B2第2行为23 41则B1第1行转换为二进制为0000110000001110B2第2行转换为二进制为0001011100101001其海明距离为8则D(1,2)8。4、distMat.m。输入为两个矩阵或一个矩阵。若输入两个矩阵计算两个矩阵两两行之间的欧式距离若是一个矩阵计算该矩阵中两两行之间的欧式距离。输入一个矩阵即为输入两个相同矩阵下只考虑输入为两个矩阵。设这两个矩阵为M1和M2M1为s1*d矩阵M2为s2*d矩阵则输出的距离矩阵D为s1*s2矩阵其中D(i,j)为M1第i行和M2第j行的欧式距离l2准则下的欧式距离。5、evaluation.m。这里面包括确定kNN问题中的k值即距离为k以内的点方视为近邻及对查询集计算其查准率与查全率。首先对训练集数据集进行训练设训练集为矩阵M计算distMat(M)得到矩阵D矩阵D中第i行各元素表示M中第i行与其余各行之间的欧式距离。对D按行进行排序并求出某选定列的平均值作为近邻查询的半径。若选定第3列因为第3列的各值表示全部数据集中每一点与其他各点的欧式距离的第三小值因此可以将此值作为要平均查找3个近邻时所需的半径阈值。返回的查全率(recall)与查准率(precision)均是n*1矩阵其中n在程序中定义recall和precision中的第i行表示查找海明距离小于i的点作为候选点在选出的候选点集中计算对应的查全率与查准率。evaluation.m中第24行中score zeros(20,1)即初始n设置为20用户可以根据自己数据的特点进行修改。6、Demo。写Demo的步骤如下1利用训练集及要查找的平均近邻数确定可视为近邻的最大距离确定True Neighbor。2计算查询集中每个查询子与所有点之间的距离并得到一个近邻矩阵N。N(i,j)为1表明第i个查询子与第j个数据点是True Neighbor为0表示不是True Neighbor。该矩阵用于计算spectral hashing查询结果的recall和precision值。3利用spectral hashing算法为每个数据点分配二进制编码并计算查询子与各数据点之间的海明距离。4定义确定候选集的阈值N该阈值内查找到的所有点数候选集点数n候选集中是True Neighbor的点数M所有查询子的True Neighbor点数。则recalln/Mprecisionn/N查全率与查准率的宏观值。这个并不是绝对的根据自己的实际情况来写。四、注意因为在谱哈系松弛过程中有数据点符合均匀分布的假设因此这种方法不适用于维度通常很高并且数据矩阵特别稀疏的文本查询。普通文本集都具有数万至数百万级别的维度并且数据矩阵极为稀疏这种数据集应用谱哈系所得结果会很差而如果要得到较好的结果只能对其进行预降维这样会损失很多信息也不会得到特别好的结果。因此谱哈系通常更适用于图像检索。
