个人博客：http://www.chenjianqu.com/

原文链接：http://www.chenjianqu.com/show-101.html

本文是<视觉SLAM14讲>的学习笔记，今天学习到词袋模型，可以用来计算图像间的相似度。

基本概念

    词袋(Bag-of-Words，BoW)，是用“图像上有哪几种特征”来描述一个图像的方法。图像的词袋模型可以度量两个图像的相似性：首先需要确定BoW中的“单词”，许多单词放在一起，组成“字典”。然后确定一张图像中出现了哪些单词(这里的单词对应的是特征)，把图像转换成了一个向量。最后根据向量，设计一定的计算方式，就能确定图像间的相似性了。

    通过字典和单词，只需一个向量就可以描述整张图像了。该向量描述的是“图像是否含有某类特征”的信息，比单纯的灰度值更加稳定。因为描述向量说的是“是否出现”，而不管它们“在哪儿出现”，所以与物体的空间位置和排列顺序无关，因此称它为Bag-of-Words。在相机发生少量运动时，只要物体仍在视野中出现，就仍然保证描述向量不发生变化。

单词的权重

    一张图像可以提取出N个特征，这N个特征可以对应到字典中的N各单词，即得到了该图像的单词序列。考虑到不同的单词(特征)在区分性上的重要性并不相同，我们希望对单词的区分性或重要性加以评估，给它们不同的权值以起到更好的效果，常用的一种做法称为 TF-IDF（Term Frequency–Inverse Document Frequency,频率-逆文档频率）。TF 部分的思想是，某单词在一个图像中经常出现，它的区分度就高。IDF 的思想是，某单词在字典中出现的频率越低，则分类图像时区分度越高。

    在词袋模型中，在建立字典时计算 IDF 部分。统计某个单词 wi 中的特征数量相对于所有特征数量的比例，作为 IDF 部分。假设所有特征数量为 n，wi 数量为 ni，那么：IDFi=log(n/ni) 。

    TF 部分则是指某个特征在单个图像中出现的频率。假设图像 A 中，单词wi 出现了 ni 次，而一共出现的单词次数为 n，那么：TFi = ni/n。

    单词 wi 的TF-IDF权重：ni = TFi * IDFi

    对于某个图像 A，它的特征点可对应到许多个单词，组成它的 Bag-of Words：A = {(w1,η1),(w2,η2), . . . ,(wn,ηn)} = vA 。通过词袋，我们用单个向量 vA 描述了图像 A。向量 vA 是一个稀疏的向量，它的非零部分指示出图像 A 中含有哪些单词，而这些部分的值为 TF-IDF 的值。

字典的构建

    字典由很多单词组成，而每一个单词代表了一类特征。一个单词与一个单独的特征点不同，它不是从单个图像上提取出来的，而是某一类特征的组合。所以，字典生成问题类似于一个聚类（Clustering）问题。假设对大量的图像提取了N 个特征点，我们想找一个有 k 个单词的字典，每个单词可以看作局部相邻特征点的集合，这可以用经典的 K-means（K 均值）算法解决。K-means算法流程：

1. 随机选取 k 个中心点：c1, . . . , ck；

2. 对每一个样本，计算与每个中心点之间的距离，取最小的作为它的归类；

3. 重新计算每个类的中心点。

4. 如果每个中心点都变化很小，则算法收敛，退出；否则返回 1。

    考虑到字典的通用性，通常会使用一个较大规模的字典，以保证当前使用环境中的图像特征都曾在字典里出现过。为了加快字典的查找效率，常用K叉树表达字典。假定有 N 个特征点，希望构建一个深度为 d，每次分叉为 k 的树，那么做法如下：

1. 在根节点，用 k-means 把所有样本聚成 k 类（实际中为保证聚类均匀性会使用k-means++）。这样得到了第一层。

2. 对第一层的每个节点，把属于该节点的样本再聚成 k 类，得到下一层。

3. 依此类推，最后得到叶子层。叶子层即为所谓的 Words。

如下图：

    最终在叶子层构建了单词，树结构中的中间节点仅供快速查找时使用。这样一个 k 分支，深度为 d 的树，可以容纳 kd 个单词。在查找某个给定特征对应的单词时，只需将它与每个中间结点的聚类中心比较（一共 d 次），即可找到最后的单词，保证了对数级别的查找效率。

相似度计算

    给定两张图像的单词向量vA ,vB，可以通过多种方式计算它们的差异。比如这里使用L1范数形式：

代码实现

    这里使用ORB特征的描述子作为BoW的特征，使用DBoW3库实现词袋模型。字典往往是从更大的数据集中生成的，而且最好是来自目标应该环境类似的地方。我们通常使用较大规模的字典——越大代表字典单词量越丰富，容易找到与当前图像对应的单词。下面是代码实现：

CMakeLists.txt

cmake_minimum_required(VERSION 2.6)
project(dbow3_test)
set( CMAKE_CXX_FLAGS "-std=c++11" )
find_package( OpenCV 3 REQUIRED )
include_directories( ${OpenCV_INCLUDE_DIRS} )
set( DBoW3_INCLUDE_DIRS "/usr/local/include" )
set( DBoW3_LIBS "/usr/local/lib/libDBoW3.a" )
add_executable(dbow3_test main.cpp)
target_link_libraries(dbow3_test ${OpenCV_LIBS} ${DBoW3_LIBS})
install(TARGETS dbow3_test RUNTIME DESTINATION bin)

main.cpp

#include <iostream>
#include <string>
#include <vector>
#include <string.h>
#include <dirent.h>
#include <DBoW3/DBoW3.h>
#include <opencv2/core/core.hpp>
#include <opencv2/highgui/highgui.hpp>
#include <opencv2/features2d/features2d.hpp>

using namespace std;
using namespace cv;

//读取某路径下的所有文件名
int getFiles(const string path, vector<string>& files)
{
    int iFileCnt = 0;
    DIR *dirptr = NULL;
    struct dirent *dirp;
    if((dirptr = opendir(path.c_str())) == NULL)//打开一个目录
        return 0;
    while ((dirp = readdir(dirptr)) != NULL){
        if ((dirp->d_type == DT_REG) && 0 ==(strcmp(strchr(dirp->d_name, '.'), ".png")))//判断是否为文件以及文件后缀名
        files.push_back(dirp->d_name);
        iFileCnt++;
    }
    closedir(dirptr);
    return iFileCnt;
}

//构建字典
void generateDict()
{
    string dataPath = "/media/chen/chen/SLAM/projects_test/DBow3_test/data";
    vector<string> files;
    getFiles(dataPath,files);//获取图片名
    //读取图片并提取ORB描述子
    vector<Mat> descriptors;
    Ptr< Feature2D > detector = ORB::create();
    for(const auto &x: files)
    {
        string picName=dataPath+"/"+x;
        cout << picName << endl;
        vector<KeyPoint> keypoints; 
        Mat descriptor;
        detector->detectAndCompute( imread(picName), Mat(), keypoints, descriptor );
        descriptors.push_back( descriptor );
    }
    DBoW3::Vocabulary vocab;
    vocab.create( descriptors );
    cout<<"vocabulary info: "<<vocab<<endl;
    vocab.save( "../vocabulary.yml.gz" );
    cout<<"done"<<endl;  
}

int main(int argc, char** argv)
{
  //生成字典
  //generateDict();
  
    //用字典判断图像相似度
    //DBoW3::Vocabulary vocab("../vocab_larger.yml.gz");//10张图像得到的字典
    DBoW3::Vocabulary vocab("../vocab_larger.yml.gz");//2900张图像得到的字典
    
    //提取ORB的描述子
    Mat despA,despB,despC;
    Ptr< Feature2D > detector = ORB::create();
    vector<KeyPoint> keypoints; 
    detector->detectAndCompute( imread("../test/A.png"), Mat(), keypoints, despA );
    detector->detectAndCompute( imread("../test/B.png"), Mat(), keypoints, despB );
    detector->detectAndCompute( imread("../test/C.png"), Mat(), keypoints, despC );
    
    //构建图像的单词向量
    DBoW3::BowVector vA,vB,vC;
    vocab.transform(despA,vA );
    vocab.transform(despB,vB );
    vocab.transform(despC,vC );
    
    //比较各图片单词向量的相似度
    double scoreAB=vocab.score(vA, vB);
    double scoreAC=vocab.score(vA, vC);
    double scoreBC=vocab.score(vB, vC);
    double scoreAA=vocab.score(vA, vA);
    
    cout<<"scoreAB:"<<scoreAB<<endl;
    cout<<"scoreAC:"<<scoreAC<<endl;
    cout<<"scoreBC:"<<scoreBC<<endl;
    cout<<"scoreAA:"<<scoreAA<<endl;
    return 0;
}

    代码中的A.png、B.png、C.png分别如下：

    代码输出如下：

Starting: /media/chen/chen/SLAM/projects_test/DBow3_test/build/dbow3_test
scoreAB:0.214842
scoreAC:0.0299757
scoreBC:0.0276582
scoreAA:1
*** Exited normally ***

    可以看到A-B相似，因此得分较高，而A-C、B-C不相似，因此得分较低。

同义词

同义词（synonym）是表、索引和视图等模式对象的一个别名。同义词只是数据库对象的替代名，与视图类似，同义词并不占用实际存储空间，只在数据字典中保存同义词的定义。在使用同义词时，Oracle简单地将它翻译成对应方案的名称。

通过使用同义词，一方面可以简化对象访问，如数据字典视图USER_INDEXES的同义词为IND，数据字典视图USER_SEQUENCES的同义词为SEQ；另一方面可以提高对象访问的安全性，如屏蔽对象所有者、对象名和数据库链接名。

在开发数据库应用程序时，应当尽量避免直接引用表、视图或其他数据库对象打的名称，而改用这些对象的同义词。这样可以避免当管理员对数据库对象做出修改和变动之后，必须重新编译应用程序。使用同义词后，即使引用的对象发生变化，也只需要在数据库中对同义词进行修改，而不必对应用程序做任何改动。

在Oracle中可以创建两种类型的同义词：

• 共用同义词（public synonym）： 共有同义词是由PUBLIC用户组所拥有，数据库中所有的用户都可以使用共有同义词。
• 私有同义词（private synonym）： 私有同义词是由创建它的用户（或方案）所拥有，也称方案同义词（schema synonym）。用户可以控制其他用户是否有权使用属于自己的方案同义词。

在创建同义词时，它所基于的对象可以不存在，并且创建同义词的用户也不需要对基础对象有任何访问权限。

语法如下

CREATE [OR REPLACE][PUBLIC] SYNONYM synonym_name
FOR [schema.]object;

为模式TEMP中的表sys_user创建一个共有同义词public_user，尽管该模式并不存在。

create public synonym public_user
for temp.sys_user;

如果同义词所对应的基础对象不存在，则当用户访问时同义词将重新编译，并验证为无效。

在操作过程中，不能修改或改变同义词，而只能删除。
删除刚刚创建的同义词

drop public synonym public_user;

Oracle在数据字典中将保存创建同义词的定义。通过数据字典视图USER_SYNONYMS，可以查询有关同义词的信息。

相似词处理

1. 简介

同义词挖掘一般有三种思路，借助已有知识库，上下文相关性，文本相似度。

1.1 知识库

可以借助已有知识库得到需要同义词，比如说《哈工大信息检索研究室同义词词林扩展版》和 HowNet，其中《词林》文件数据如下。

Aa01A01= 人 士 人物 人士 人氏 人选
Aa01A02= 人类 生人 全人类
Aa01A03= 人手 人员 人口 人丁 口 食指
Aa01A04= 劳力 劳动力 工作者
Aa01A05= 匹夫 个人
Aa01A06= 家伙 东西 货色 厮 崽子 兔崽子 狗崽子 小子 杂种 畜生 混蛋 王八蛋 竖子 鼠辈 小崽子
Aa01A07= 者 手 匠 客 主 子 家 夫 翁 汉 员 分子 鬼 货 棍 徒
Aa01A08= 每人 各人 每位
Aa01A09= 该人 此人

以上两个知识库是人工编辑的，毕竟数量有限，我们还可以借助众包知识库百科词条获取同义词，比如百度百科，如下图所示，在百度百科搜索“凤梨”，我们可以看到在返回页面结果中的 info box中有一个属性为“别称”，别称中就是凤梨的同义词。除此之外，在百科词条的开头描述中，有如下描述“又称”、“俗称”也是同义词，我们可以利用爬虫把这些词爬下来。

百度搜索和谷歌搜索等搜索工具一般都有重定向页，这也可以帮助我们去挖掘同义词。

使用知识库挖掘同义词的优点是简单易得，而且准确率也高，缺点就是知识库覆盖率有限，不是每个细分领域都有。对于金融、医疗、娱乐等领域都需要各自的知识库。

1.2 上下文相关性

利用上下文相关性挖掘同义词也比较好理解，如果两个词的上下文越相似的话，那么这两个词是同义词的概率就越大。使用词向量挖掘同义词是比较常见的做法，比如使用word2vector训练得到词向量，然后再计算余弦相似度，取最相似的top k个词，就得到了同义词。

word2vector是无监督学习，而且本质上来说它是一个语言模型，词向量只是它的副产品，并不是直接用来挖掘同义词。有篇paper发明了弱监督的同义词挖掘模型DPE，也取得了不错的效果。DPE模型流程如下图，一共分为两个阶段，第一阶段跟word2vector差不多，也是训练词向量，只不过DPE是一种graph embedding的思路，首先从语料中构建语义共现网络，然后通过对网络的边采样训练词向量。第二阶段通过弱监督训练一个打分函数，对输入的一对词判断属于同义词的概率。

基于上下文相关性的同义词挖掘方法的优点是能够在语料中挖掘大量的同义词，缺点是训练时间长，而且挖掘的同义词很多都不是真正意义上的同义词需要人工筛选。这种方法对于词频较高的词效果较好。

1.3 文本相似度

对于这一对同义词“阿里巴巴网络技术有限公司”和“阿里巴巴网络公司”直接去计算上下文相似度可能不太有效，那一种直观的方法是直接计算这两个词的文本相似度，比如使用编辑距离（Levenshtein distance）或者 LCS（longest common subsequence），如果两个词的文本相似度大于阈值的话我们就认为他们是同义词的关系。在这里推荐一个计算文本相似度的Java开源项目,基本上文本相似度算法应有尽有。[ 文本相似度算法 ]

基于文本相似度同义词挖掘方法的优点是计算简单，不同于word2vector，这种方法不需要使用很大的语料，只要这个词出现过一次就可以发现同义词关系。这种方法的缺点是有时候不太靠谱，会挖掘出很多错误的同义词，尤其是当两个词比较短的情况下，比如“周杰伦”和“周杰”，就可能会被认为是同义词。所以这种方法适用于一些较长的文本，特别是专业词汇，术语。

2. 句子相似度计算

2.1 编辑距离

编辑距离，英文叫做 Edit Distance，又称 Levenshtein 距离，是指两个字串之间，由一个转成另一个所需的最少编辑操作次数，如果它们的距离越大，说明它们越是不同。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。

例如我们有两个字符串：string 和 setting，如果我们想要把 string 转化为 setting，需要这么两步：

第一步，在 s 和 t 之间加入字符 e。
第二步，把 r 替换成 t。
所以它们的编辑距离差就是 2，这就对应着二者要进行转化所要改变（添加、替换、删除）的最小步数。

安装：pip3 install distance

import distance

str1 = "公司地址是哪里"
str2 = "公司在什么位置"

def edit_distance(s1, s2):
    return distance.levenshtein(s1, s2)

print(edit_distance(str1, str2))

想要获取相似的文本的话可以直接设定一个编辑距离的阈值来实现，如设置编辑距离为 2

def edit_distance(s1, s2):
    return distance.levenshtein(s1, s2)

strings = [
    '你在干什么',
    '你在干啥子',
    '你在做什么',
    '你好啊',
    '我喜欢吃香蕉'
]

target = '你在干啥'
results = list(filter(lambda x: edit_distance(x, target) <= 2, strings))
print(results)
# ['你在干什么', '你在干啥子']

2.2 杰卡德系数计算

杰卡德系数，英文叫做 Jaccard index, 又称为 Jaccard 相似系数，用于比较有限样本集之间的相似性与差异性。Jaccard 系数值越大，样本相似度越高。

实际上它的计算方式非常简单，就是两个样本的交集除以并集得到的数值，当两个样本完全一致时，结果为 1，当两个样本完全不同时，结果为 0。

算法非常简单，就是交集除以并集，下面我们用 Python 代码来实现一下：

from sklearn.feature_extraction.text import CountVectorizer
import numpy as np

def jaccard_similarity(s1, s2):
    def add_space(s):
        return ' '.join(list(s))

    # 将字中间加入空格
    s1, s2 = add_space(s1), add_space(s2)
    # 转化为TF矩阵
    cv = CountVectorizer(tokenizer=lambda s: s.split())
    corpus = [s1, s2]
    vectors = cv.fit_transform(corpus).toarray()
    # 获取词表内容
    ret = cv.get_feature_names()
    print(ret)
    # 求交集
    numerator = np.sum(np.min(vectors, axis=0))
    # 求并集
    denominator = np.sum(np.max(vectors, axis=0))
    # 计算杰卡德系数
    return 1.0 * numerator / denominator


s1 = '你在干嘛呢'
s2 = '你在干什么呢'
print(jaccard_similarity(s1, s2))

2.3 Word2Vec计算

顾名思义，其实就是将每一个词转换为向量的过程。

Word2Vec的词向量模型是训练的维基百科的中文语库，这里模型有250维和50维，向量维度越大模型越大，计算越复杂，正常使用时，需要小的模型，发现50维的也差不多.

流程：

1. 对句子进行拆词
2. 去除无用的分词
3. 计算句子平均词向量
4. 余弦相似度

对句子进行拆词：Python提供了很对可用库，自行选择
去除无用的分词：删除没用的语气词等，为的是减少对计算句子平均词向量的影响。
计算句子平均词向量用的是AVG-W2V，计算句子平均词向量，所以02步尤为重要
余弦相似度：

余弦相似度 np.linalg.norm(求范数)（向量的第二范数为传统意义上的向量长度
dist1=float(np.dot(vec1,vec2)/(np.linalg.norm(vec1)*np.linalg.norm(vec2)))

def key_words_ask_method(sentence1, sentence2):
    '''
    因为无论是#1:AVG-W2V 2:AVG-W2V-TFIDF 都需要求得平均值，
    除数：决定整个数据的大小  被除数：影响平均值
    所以 分词的标准很重要，可通过自定义词典、停用词 和 语义分析进行适当处理
    '''
    vec1 = sentence_to_vec(sentence1)
    vec2 = sentence_to_vec(sentence2)

    # 零向量直接返回
    if (vec1 == np.zeros(WORD_VECTOR_DIM)).all() == True or (vec2 == np.zeros(WORD_VECTOR_DIM)).all() == True:
        return "不符合相似"

    # score = cos(vec1, vec2)
    # print(score)
    # if score < COSINE_CRITICAL_VALUE:
    #     return "1"
    # else:
    #     return "0"

    # 余弦相似度 np.linalg.norm(求范数)（向量的第二范数为传统意义上的向量长度
    dist1=float(np.dot(vec1,vec2)/(np.linalg.norm(vec1)*np.linalg.norm(vec2)))
    print("score:", dist1)
    if dist1 > 0.92:
        return "两个句子相似"
    else:
        return "两个句子不相似"

参考：

nlp自然语言处理中句子相似度计算

同义词（近义词）算法总结（附代码）