相似度

• 以图搜图
• • 均值哈希
  • 感知哈希
  • 差值哈希
  • 汉明距离
  • 余弦相似度
  • • 提取图片特征的几个方法
    • • 例举
• 文本相似度
• • TF-IDF算法
  • • TF词频
    • IDF逆文档频率
    • TF-IDF
    • 实现
    • • 分词实现
      • IDF逆文档频率实现
      • TF词频实现
      • TF-IDF实现
  • 余弦相似度
• 其他相似度
• • 欧拉距离
  • • L1范数
    • L2范数
    • Lp范数
  • Jaccard相似度
• 写在后面
• • jieba库
  • 深度学习取特征
  • 存储特征向量快速检索
  • 怎么选取相似度算法？
  • 更加深入进去
  • • 推荐系统
    • 鉴别盗版视频
    • 项目链接

以图搜图

许多搜索引擎会提供一个功能，那便是以图搜图；顾名思义，输入一张图，得到对应的结果。比如找一件衣服的时候，使用文字较为抽象，而图片则较为直观。

均值哈希

步骤：

读取图片

图片尺寸缩放为 $32\ast 32$

转灰度图

计算得到平均值 $x$

$img[i,j]\le x$ 的置为 $0$，否则置 $1$

def avgHash(imgPath):# 读取图片img = cv2.imdecode(np.fromfile(imgPath, dtype=np.uint8), -1)# 转为设定好的尺寸(32, 32)img = cv2.resize(img, size)# 转为灰度图img = cv2.cvtColor(img, cv2.COLOR_RGB2GRAY)# 获取图片尺寸大小height, width = img.shape# 计算图片像素平均值avg = 0for i in range(height):for j in range(width):avg += img[i][j]avg /= (height * width)# 二值化, 计算均值hashhkey = ""for i in range(height):for j in range(width):if img[i][j] <= avg:hkey = hkey + "0"else:hkey = hkey + "1"return hkey

感知哈希

步骤：

读取图片

图片尺寸缩放为 $32\ast 32$

转灰度图

$dct$ 变换，将图片转到频域

取图片左上角的低频 $8\ast 8$ 部分，计算得到平均值 $x$

左上角的低频 $8\ast 8$ 部分的 $img[i,j]\le x$ 的置为 $0$，否则置 $1$

def dctHash(imgPath):# 读取图片img = cv2.imdecode(np.fromfile(imgPath, dtype=np.uint8), -1)# 转为设定好的尺寸(32, 32)img = cv2.resize(img, size)# 转为灰度图img = cv2.cvtColor(img, cv2.COLOR_RGB2GRAY)# dct变换img = cv2.dct(np.array(img, np.float32))# 获取图片尺寸大小height, width = img.shapeheight //= 4width //= 4# 计算图片像素平均值avg = 0for i in range(height):for j in range(width):avg += img[i][j]avg /= (height * width)# 二值化, 计算均值hashhkey = ""for i in range(height):for j in range(width):if img[i][j] <= avg:hkey = hkey + "0"else:hkey = hkey + "1"return hkey

差值哈希

步骤：

读取图片

图片尺寸缩放为 $32\ast 33$

转灰度图

若$img[i,j]\le img[i,j+1]$ 则置为 $1$，否则置为 $0$

def differenceHash(imgPath):# 读取图片img = cv2.imdecode(np.fromfile(imgPath, dtype=np.uint8), -1)# 转为设定好的尺寸(32, 32+1)img = cv2.resize(img, (size[0], size[1]+1))# 转为灰度图img = cv2.cvtColor(img, cv2.COLOR_RGB2GRAY)# 获取图片尺寸大小height, width = img.shape# 计算差值hashhkey = ""for i in range(height):for j in range(width-1):if img[i][j] <= img[i][j+1]:hkey = hkey + "0"else:hkey = hkey + "1"return hkey

汉明距离

汉明编码是与信息位置相关的一种编码方式；上面的几种哈希算法最后得到的是汉明编码，因此可以使用汉明距离来进行相似度的计算。

步骤：

进行异或运算C=A^B

统计C中1的个数

def hamming(s1, s2):if len(s1) != len(s2):raise Exception("{0} len({1}) != {2} len({3})".format(s1, len(s1), s2, len(s2)))slen = (len(s1) + len(s2)) / 2.0return 1.0 - sum([ch1 != ch2 for ch1, ch2 in zip(s1, s2)]) / slen

余弦相似度

余弦相似度，是通过计算两个向量的夹角余弦值来评估他们的相似度。

$$余弦相似度=cos(\theta )=\frac{{\sum }_{i=1}^n{A}_i{B}_i}{\sqrt{{\sum }_{i=1}^n(A_i{)}^2}\sqrt{{\sum }_{i=1}^n(B_i{)}^2}}$$

提取图片特征信息制作成向量，再使用余弦相似度算法进行计算。

def cosin(v1, v2):# 点乘num = float(np.dot(v1, v2))# np.linalg.norm求范数, 默认是l2范数denom = np.linalg.norm(v1) * np.linalg.norm(v2)# 结果归一化到[0, 1]区间return 0.5 + 0.5 * (num / denom) if denom != 0 else 0

提取图片特征的几个方法

深度模型特征提取层的作为特征向量

使用K聚类等算法拿到特征向量

自定义自己的算法，比如简单缩放图片尺寸 $32\ast 32$ 后，取每行像素的平均值

SIFT、HOG、SURF、ORB、LBP、HAAR，这些方式或许不需要用余弦相似度

给出图像主题色提取的算法链接

例举

随意的一种方式，准确率较低。

def feature(imgPath):# 读取图片img = cv2.imdecode(np.fromfile(imgPath, dtype=np.uint8), -1)# 转为设定好的尺寸(32, 32)img = cv2.resize(img, size)# 转为灰度图img = cv2.cvtColor(img, cv2.COLOR_RGB2GRAY)# 获取图片尺寸大小height, width = img.shape# 计算图片像素平均值feature = []for i in range(height):avg = 0cnt = 0for j in range(width):if img[i][j] == 255:continueavg += img[i][j]cnt += 1feature.append(avg / (cnt if cnt != 0 else 1))return np.array(feature) / 255

文本相似度

搜索引擎大家都知道，像Google和百度这样的搜索引擎是通过关键字信息获取到$WWW$中对应的文章结果。

TF-IDF算法

关键词提取是文本挖掘领域一个很重要的部分，通过对文本提取的关键词可以窥探整个文本的主题思想，进一步应用于文本的推荐或文本的搜索。TF-IDF则是其中一种提取关键词的算法。

TF词频

$$词频(TF)=\frac{W在文档中出现的次数C}{文档总词数S}$$

IDF逆文档频率

$$逆文档频率(IDF)=log(\frac{文档总数D}{包含W的文档数N+1})$$

TF-IDF

TF-IDF的公式与信息熵非常相似。关于相对熵与TF-IDF的关系，其实是相对熵可以给以上TF-IDF计算公式在某种特定条件下的一个数学解释，从相对熵并不能推导出TF-IDF。引用与信息熵与TF-IDF
$$TF-IDF=词频(TF)\cdot 逆文档频率(IDF)$$

实现

分词实现

先使用jieba分词。

def getJiebaWs(s):# 分词后的列表ws = []# jieba分词it = jieba.cut(s)# 存储分词结果for w in it:ws.append(w)# 返回分词列表return wsdef getWords():# 所有文档的分词words = []# allWord是所有文档for word in range(len(allWord)):# word是一篇文档words.append(getJiebaWs(word))# 返回所有文档的分词结果return words

IDF逆文档频率实现

输入所有分词好后的文档。

def idf(words):# idf字典idfFreq = {}# 总文档数wordsNum = len(words)# 每篇文档for word in words:# 包含w的文档数for w in word:# 已经计算w的idf则跳过if w in idfFreq.keys():continue# 记录w出现在几篇文档中cnt = 0for d in words:if w in d:cnt += 1# idf公式idfFreq[w] = np.math.log(wordsNum / (cnt + 1))# 返回idf字典return idfFreq

TF词频实现

输入分词好后的文档。

def tf(ws):# tf字典tfFreq = {}# 总词数wsNum = len(ws)# 每个字for w1 in ws:# w1已计算过if w1 in tfFreq.keys():continue# 统计w1在ws中出现的次数cnt = 0for w2 in ws:if w1 == w2:cnt += 1# tf公式tfFreq[w1] = cnt / wsNum# 返回tf字典return tfFreq

TF-IDF实现

输入 $TF$ 字典和 $IDF$ 字典。

def tfidf(tfFreq, idfFreq):# 词向量vec = {}# 只记录有效的词频率for k in tfFreq.keys():if k in idfFreq.keys():vec[k] = tfFreq[k] * idfFreq[k]else:vec[k] = tfFreq[k] * 0.0# 返回词向量return vec

余弦相似度

def cosin(serachVec, vec):num = 0.0serachVecNorm = 0.0vecNorm = 0.0# 分子结果for k in serachVec.keys():if k in vec.keys():num += serachVec[k] * vec[k]# 分母结果for k in serachVec.keys():serachVecNorm += serachVec[k] * serachVec[k]for k in vec.keys():vecNorm += vec[k] * vec[k]denom = np.math.sqrt(serachVecNorm) * np.math.sqrt(vecNorm)# 归一化到[0, 1]return 0.5 + 0.5 * (num / denom) if denom != 0 else 0

其他相似度

还有非常多的相似度算法，列举以下几个。还有未列举出来的：皮尔逊相关系数等。

欧拉距离

欧拉距离，来自于欧式几何，在数学上也可以成为范数。

L1范数

$$\sum _{i=1}^n|x_i-y_i|$$

L2范数

$$(\sum _{i=1}^n|x_i-y_i{|}^2{)}^{\frac{1}{2}}$$

Lp范数

$$(\sum _{i=1}^n|x_i-y_i{|}^p{)}^{\frac{1}{p}}$$

Jaccard相似度

用于集合的相似度计算。
$$S=\frac{2\cdot |X\cap Y|}{|X|+|Y|}$$

写在后面

jieba库

分析jieba库源码，可以知道jieba的IDF语料库是通过pip一起下来的，在jieba/jieba/analyse/idf.txt中。

jieba是支持获取TF-IDF的，以上的写法是为了解原理。

深度学习取特征

目前主流是通过深度学习获取对应的特征向量，再进行一个相似度的检测的。

存储特征向量快速检索

每次重新计算所有文本或者图片的特征是非常慢的，因此会使用一些cache技术来达到快速检索的目的。

怎么选取相似度算法？

通过分析数据之间的信息来选。

例如，为什么图片hash算法不能用余弦相似度？因为图片hash算法与位置相关，不能直接抛弃位置信息。

那换种角度去思考，与文本处理类似；每张图片与所有图片集都具有一定相关性的时候，或许就可以使用余弦相似度了。比如：深度学习取到的图片特征向量就可以使用。

更加深入进去

推荐系统

推荐系统必要的一个条件就是需要知道信息与信息之间的相关性。

鉴别盗版视频

youtobe中使用到了相似度的算法，用于鉴别原版和盗版视频；大致思路：获取视频特征值(应该有做压缩，或者计算hash)，接着进行相似度计算来过滤盗版视频。

项目链接

本篇相似度项目链接

总结

以上是生活随笔为你收集整理的相似度算法和应用的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。