美文网首页
分词算法和模型

分词算法和模型

作者: 今年五年级 | 来源:发表于2021-05-21 17:18 被阅读0次

    一 概念部分

    1.1 信息检索常用术语

    词条化：tokenization
    指的是将给定的字符串拆分成多个子序列，每个子序列称为词条，词条化的过程会去除标点符号空格等停用词，如

    image.png

    词项：term
    指的是经过语言学预处理归一化之后的词条，是索引的最小单位，如英文分词技术在提取词干的时候因为 英文单词有单数复数的变形，-ing和-ed的变形，但是在计算相关性的时候，应该当做同一个单词。比如 apple和apples，doing和done是同一个词，提取词干的目的就是要合并这些改变

    image.png

    词项文档矩阵：Incidence matrix
    指的是词项和文档的包含关系模型，如下图

    image.png

    每列代表一个文档包含的词项信息，每行代表一个词项出现在哪几个文档里

    词项频率：term frequency
    同一个词项在某个文档中出现的次数，如词项zara在文档1出现3次，那么词项zara在该文档中的词频为3

    文档频率：document frequency
    出现某词项的文档的数目，如词项zara出现在文档1和文档3，那么文档频率为2

    1.2 分词算法

    分词可以帮助搜索引擎自动识别语句含义，使搜索结果匹配度最高，分词质量直接影响搜索精确度。分词在文本索引的创建过程和用户提交检索过程中都存在

    1.2.1 英文分词的原理

    • 根据空格，分隔,得到单词组
    • 过滤，排除掉停止词
    • 提取词干

    1.2.2 中文分词的原理

    中文不像因为词与词之间用空格分开，因此分词比较复杂，常用的分词方式有：基于词典匹配的分词，基于语义理解的分词，基于词频统计的分词

    1.2.2.1 基于词典匹配：

    变量声明：m为词典中最长词的字数

    正向最大匹配算法：
    从左往右取m个最大字符组成的字符串，如果匹配成功，则将匹配字符串取出来，匹配不成功，就将字符串最后一个字去掉，然后将剩余的字再执行上面的操作
    如 南京市长江大桥
    首先从左往右取5个字，南京市长江，发现词典中没有该词，则去掉江，留下来南京市长参与

    逆向最大匹配算法：
    从右往左取m个最大字符，如果匹配成功，则将匹配字符串取出来，匹配不成功，就将字符串第一个字去掉，然后将剩余的字再执行上面的操作
    如 南京市长江大桥
    从右往左5个字，市长江大桥，发现词典没有该词，去掉市，剩余的长江大桥再去匹配，找到，然后南京市这3个字找到并分出来

    相对来说，由于中文分词最大的问题是歧义处理，采用逆向匹配的切分算法，处理精度高于正向匹配，产生切分歧义现象较少

    双向最大匹配法
    正向最大匹配法得到的分词结果和逆向最大匹配法的到的结果进行比较，即把所有可能的最大词都分出来，如上面的分为：南京市、南京市长、长江大桥、江、大桥

    1.2.2.2 语义理解分词法：

    基于语义理解模拟人脑对语言和句子的理解，达到识别词汇单元的效果，基本模式是把分词，句法，语义分析并行进行，利用句法和语义分析消除分词的歧义

    目前国内外对汉语语言知识的理解和处理能力没有达到语义层面，具体到语言信息很难组织能机器可直接读取、计算的形式，因此目前基于语义理解的分词系统还处在试验阶段

    1.2.2.3 词频统计分词法：

    通常词是稳定的字的组合，相邻的字搭配在一篇文章中出现的频率越高，则越可能是一个固定的词，相邻的字同时出现的频率或概率更好的反应词的可信度

    实际系统中，通过对准备的中文文章中相邻一起出现的各个字的组合的频率进行统计，统计两个汉字相邻共现概率，统计出来的信息体现了中文环境下汉字之间结合的紧密程度，当紧密程度高于一个阈值，便认为此字组可能构成一个词

    优点：不需要切分词典，只需要对文中的字组合的频率进行统计，同时还可以很好的解决词典未收录新词的问题
    缺点：会抽取出一些共现频率高但不是词的常用字组合，需要专门处理，提高精确度

    实际使用：使用一个基本的常用词词典，将字典分词和统计分词结合使用，发挥匹配分词切分速度快，效率高的优势，同时也发挥了无词典分词结合上下文识别分词，消除歧义的优点

    1.3 倒排索引 inverted index

    文档通常保存在数据库中，如mysql，oracle等，但是搜索引擎数据无法保存到数据库中，因为搜索引擎数据量非常庞大，面对海量数据关系型数据库很难管理，第二点：搜索引擎只需要简单的对数据增删改查，不需要传统数据库的那么多的功能

    一般数据库支持功能太多，牺牲了速度和空间，数据库系统在检索响应时间和并发度都不能满足需求，数据库系统中使用索引来提高表的搜索效率而对某些字段中的值建立目录，而在搜索引擎中使用倒排索引这种数据结构存储网页信息

    倒排索引又称反向索引，用来存储全文检索下某个词项在一个文档或一些文档中出现的位置的映射关系，是文档检索系统中最常用数据结构

    正排索引表示的是：文档与文档中的词项的对应关系
    倒排索引表示的是：词项与文档的对应关系

    加入现在有两个文档doc1和doc2，doc1包含3个关键词项 java，python，c++，doc2中包含4个关键词 java，c++，c#，lua

    则正排索引表示为：

    文档 词项
    doc1 java、python、c++
    doc2 java、c++、c#、lua

    倒排索引表示为：

    词项 文档
    java doc1、doc2
    python doc1
    c++ doc1、doc2
    c# doc2
    lua doc2

    如查找包含关键词“java“的文档，那么结果就是doc1，doc2
    我们在搜索引擎中输入关键词进行查询，就是查找哪些文档包含查询关键词的过程

    实例：使用4条新闻作为文档集合，体验倒排索引构建过程
    新闻标题作为文档内容，连续的整数编号作为文档id

    image.png

    对于文档内容，先经过词条化处理，中文没有英文空格，就经过分词系统进行中文分词以后将矩阵切分为一个个词条，文档1会被分成“人工”，“智能”，“成为”，“互联网”，“大会”，“焦点” 这6个词项

    “人工”这个词在文档1、文档2、文档3中都出现了一次，文档频率（是出现某词项的文档的数目不是文档中词项的出现次数累加）为3，倒排记录表1->2->3

    词项 文档频率 文档频率
    人工 3 1->2->3
    智能 3 1->2->3
    成为 1 1
    互联网 2 1->3

    1.4 TF-IDF权重计算

    TF-IDF(term frequency-inverse document frequency)是一种用于信息检索与数据挖掘的加权技术

    TF-IDF用以评估一字词对于一个文档集或者文档集中一份文件的重要程度。词项的重要性随着它在文件中出现的次数成正比增加，但同时会随着它在文档集中出现的频率成反比下降
    主要思想是：如果一个词项在一篇文档中出现频率非常高，说明其重要性比较高，但是如果这个词项在文档集中其他文档中出现频率也很高，则说明该词项很可能是比较通用且常见的

    1.4.1 TF词频

    统计一份文档中某个词项的词频，则统计该词项在整篇文档中出现次数即可

    image.png

    但是文档有长短之分，一篇3000字的广告中出现“足球”出现3次，我们很难判断文章就是和足球相关的，但是如果一篇140字的微博中同样出现3次“足球”，基本可以判断微博内容和足球相关，因此为了削弱文档长度的影响，一般会将词频标准化，计算方式如下：


    image.png image.png

    词频标准化的方式不止一种，Lucene采用了下面的词频标准化方法

    image.png

    1.4.2 IDF:逆文档频率

    image.png

    如果一个词越常见，那么分母就越大，逆文档频率就越小越接近0。分母之所以要加1，是为了避免分母为0（即所有文档都不包含该词）。log表示对得到的值取对数。

    1.4.3 计算TF-IDF

    实际上是：TF * IDF，即TF-IDF=TF*IDF
    代码部分：

    /**
 * TF-IDF：计算词项对于一个文档或一个文档集中的一份文档的重要程度
 *
 * log(文档集总文档数/(包含某个词的文档数+1))
 *
 */
public class TF_IDF {

    public static void main(String[] args) {
        List<String> doc1= Lists.newArrayList(
                "人工","智能","成为","互联网","大会","焦点"
        );

        List<String> doc2= Lists.newArrayList(
                "谷歌","推出","开源","人工","智能","系统","工具"
        );

        List<String> doc3= Lists.newArrayList(
                "互联网","的","未来","在","人工","智能"
        );

        List<String> doc4= Lists.newArrayList(
                "谷歌","开源","机器","学习","工具"
        );

        List<List<String>> docList= Lists.newArrayList(doc1,doc2,doc3,doc4);

        TfIdfCal tfIdfCal = new TfIdfCal();
        System.out.println("计算谷歌在文档2中的词频 "+tfIdfCal.tf(doc2,"谷歌"));
        System.out.println("计算谷歌的文档频率 "+tfIdfCal.df(docList,"谷歌"));
        System.out.println("计算谷歌的逆文档频率 "+tfIdfCal.idf(docList,"谷歌"));
        System.out.println("计算谷歌对于文档2的TF-IDF "+tfIdfCal.tfIdf(doc2,docList,"谷歌"));

    }

    static class TfIdfCal{
        public double tf(List<String> doc,String term){
            if(doc==null||doc.size()==0)
                throw new IllegalArgumentException();

            double tf= 0;
            for (String str : doc) {
                if(str.equalsIgnoreCase(term))
                    tf++;
            }

            return tf/doc.size();
        }

        public int df(List<List<String>> docs, String term){
            int n=0;
            if(term!=null&& !"".equals(term)){
                for (List<String> doc : docs) {
                    for (String str : doc) {
                        if(term.equalsIgnoreCase(str)){
                            n++;
                            break;
                        }
                    }
                }
            }
            return n;
        }

        public double idf(List<List<String>> docs,String term){
            return Math.log(docs.size()/((double)df(docs,term)+1));
        }

        public double tfIdf(List<String> doc,List<List<String>> docs,String term){
            return tf(doc,term)*idf(docs,term);
        }
    }
}

    1.5 向量空间模型

    vector space model VSM
    成功应用于SMART文本检索系统，上世纪70年底提出。将对文本内容的处理简化为向量空间中的向量运算，它以空间上的相似度表达语义的相似度

    vsm涉及的基本概念

    • 文档(document)：文章中具有一定规模的片段，如句子，段落，段落组甚至整篇文章
    • 词项(term)/特征项(feature term)：对应之前提到的词项，详见一概念部分的1.1信息检索常用术语，是vsm中最小的不可再分的语言单元，可以是字/词/短语等。一个文档的内容被看做是它含有的特征项组成的集合，表示为Document=D(t_1,t_2,...,t_n),其中t_k是特征项，1≤k≤n
    • 词项的权重(term weight)：对于含有n个特征项的文档D(t_1,t_2,...,t_n)，每一个特征项t_k都依据一定的规则被赋予一个权重w_k，表示它们在文档中的重要程度。这样一个文档就可以用它含有的特征项及其特征项所对应的权重锁表示：D=D(t_1,w_1;t_2,w_2;...;t_n,w_n)，简计为D=D(w_1,w_2,...,w_n)，其中w_k就是特征项t_k的权重，1≤k≤n

    一个文档可以看做n维空间中的一个向量

    vsm定义
    给定一个文档D=D(t_1,w_1;t_2,w_2;...;t_n,w_n)，D符合以下两条约定
    （1）各个特征项t_k(1≤k≤n)互异，没有重复
    （2）各个特征项t_k无先后顺序关系（即不考虑文档的内部结构）
    在以上两个约定下，可把特征项t_1,t_2,...,t_n看成一个n维坐标系，而权重w_1,w_2,...,w_n为对应的坐标值。因此，一个文本就表示为n维空间中的一个向量，我们称D=D(t_1,w_1;t_2,w_2;...;t_n,w_n)为文本D的向量空间模型

    image.png

    1.5.1 余弦相似度理论

    任意两个文档D_1和D_2之间的相似性系数Sim(D_1,D_2)指代文档内容的相关程度(degree of relevance),设文档D_1和D_2表示VSM中的两个向量
    D_1=D_1(W_{11},W_{12},...,W_{1n})
    D_2=D_1(W_{21},W_{22},...,W_{2n})
    则，可借助于n维空间中两向量之间的距离来表示文档之间的相似度，一般使用向量的内积来计算
    Sim(D_1,D_2)=\sum_{k=1}^{n}w_{1k}\cdot w_{2k}
    使用两向量余弦值表示相似系数：
    Sim(D_1,D_2)=cos\theta=\frac{\sum_{k=1}^{n}w_{1k}\cdot w_{2k}}{\sqrt{\sum_{k=1}^n(w_{1k})^2\cdot\sum_{k=1}^n(w_{2k})^2}}

    空间直角坐标系中的坐标：
    在空间直角坐标系O-xyz中，对空间任一点A，存在唯一有序实数租(x,y,z)，使 \vec a=x\vec i+y\vec j+z\vec k，有序实数组(x,y,z)叫做向量A在空间直角坐标系O-xyz中的坐标，记做A(x,y,z)，x叫做横坐标，y叫做纵坐标，z叫做竖坐标

    模长公式：
    若\vec a=(a_1,a_2,a_3)，则|\vec a|= \sqrt{ \vec a\cdot\vec a}=\sqrt{a_1^2+a_2^2+a_3^2}

    向量夹角余弦公式：
    如果向量a与向量b的夹角为\theta，那么两向量夹角余弦可以表示为
    \cos\theta=\cos(\vec a,\vec b)=\frac{\vec a\cdot\vec b}{|\vec a|\cdot|\vec b|}=\frac{\sum_{i=1}^n a_i\cdot b_i}{\sqrt{\sum_{i=1}^n(a_i)^2\cdot\sum_{i=1}^n(b_i)^2}}

    夹角的余弦值与向量的指向有关
    当A向量和B向量方向相同时，向量夹角为0，\cos\theta=1
    当A向量和B向量方向相反时，向量夹角为180度，\cos\theta=-1
    当A向量和B向量方向垂直时，向量夹角为90度，\cos\theta=0
    两向量夹角的余弦值从最小-1到最大1之间

    向量夹角余弦值衡量相似度通常用于正空间，即向量余弦值从0到1之间

    如果用两个文档doc1和doc2，doc1和doc2在向量空间中分别以向量\vec d_1和向量\vec d_2表示，关键词查询向量为\vec q,\vec d_1和\vec q的夹角为 \a,\vec d_2和\vec q的夹角为 \beta

    image.png

    则通过计算向量夹角余弦可得查询向量和doc1之间的相似性
    \cos \a=\frac{\vec d_1 \cdot \vec q}{|d_1|\cdot|q|}

    查询向量和doc2之间的相似性
    \cos \beta=\frac{\vec d_2 \cdot \vec q}{|d_2|\cdot|q|}

    比较cos\a, cos\beta的大小可以得到doc1和doc2哪个和查询关键词相关性更大

    应用：
    余弦相似性理论除了应用在信息检索模型以外，在文本挖掘领域用于文件比较，在数据挖掘领域用来度量集群内部凝聚力，在推荐系统中用来比较用户偏好的相似性

    优点：

    • 基于线性代数的简单模型
    • 词组的权重不是二元的
    • 文档和查询之间的相似度取值连续
    • 允许根据文档间可能的相似性排序
    • 允许局部匹配

    1.5.2 如何使用向量空间模型表示文本

    （1）根据训练样本集train.txt生成文本表示所需要的特征项序列D(t_1,t_2,...,t_n)
    （2）根据根据文本特征项序列，对训练样本集和测试样本集中的各个文档进行权重赋值，规范化等处理，将其转化为极其学习算法所需的特征向量

    1.5.3 案例

    public class Vsm {

    public static void main(String[] args) {
        Map<String,Double> m1= Maps.newHashMap();
        m1.put("Hello",1.0);
        m1.put("CSS",2.0);
        m1.put("Lucene",3.0);

        Map<String,Double> m2= Maps.newHashMap();
        m2.put("Hello",1.0);
        m2.put("World",2.0);
        m2.put("Hadoop",3.0);
        m2.put("Java",4.0);
        m2.put("HTML",1.0);
        m2.put("CSS",2.0);

        calCosSim(m1,m2);
    }

    public static double calCosSim(Map<String,Double> v1,Map<String,Double> v2){
        double sclar = 0.0,norm1=0.0,norm2=0.0,similarity;

        Set<String> v1Keys=v1.keySet();
        Set<String> v2Keys=v2.keySet();

        Set<String> both=new HashSet<>();   // 获取两篇文档的公共词项
        both.addAll(v1Keys);
        both.retainAll(v2Keys); // 保留在m2中出现的key
        System.out.println(both);

        for (String str1 : both) {
            sclar+=v1.get(str1)*v2.get(str1);
        }

        for (String str1 : v1.keySet()) {
            norm1+=Math.pow(v1.get(str1),2);
        }

        for (String str2 : v2.keySet()) {
            norm2+=Math.pow(v2.get(str2),2);
        }

        similarity=sclar/Math.sqrt(norm1*norm2);
        System.out.println("sclar:"+sclar);
        System.out.println("norm1:"+norm1);
        System.out.println("norm2:"+norm2);
        System.out.println("similarity::"+similarity);
        return similarity;
    }

}

    1.6 概率检索模型

    相关文章

      网友评论

          本文标题：分词算法和模型

          本文链接：https://www.haomeiwen.com/subject/dawwjltx.html

          延伸阅读

          深度阅读

          • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

          栏目导航

          热点阅读

          关于我们|服务条款|联系我们|分词算法和模型|投稿指南|网站地图|RSS订阅|排版工具|手机版

          提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

          Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

          备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

          本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

          所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！