haoming

机器学习:基于Javascript的朴素贝叶斯文档分类算法

haoming · 2017-01-15翻译 · 1104阅读 原文链接

今天我们将要学习一个伟大的机器学习技术应用--文档分类。我们将会使用我最喜欢的工具,朴素贝叶斯分类器。

> 这篇文章是Machine Learning in Javascript系列的一部分,这个系列用Javascript编写例子教授最本质的机器学习算法。我使用Javascript是因为它非常著名而且被广泛支持,这使得它成为一个卓越的教学语言。在文章的底部有一个邮件列表,如果你想要在新文章发布的时候被通知你也可以关注我的twitter: @bkanber. > 如果你只是在查找示例代码 向下滚动!

介绍和动机

文档分类是我最喜欢的任务之一。“文档分类”就像你所想的一样:对于一个给定的文档和一个标签集,给这个文档选择一个最合适的标签。标签(或者类或者类别)可以是下面这些东西:

  • “垃圾邮件”或者“非垃圾邮件”(大部分的邮箱客户端使用某种形式的贝叶斯垃圾邮件检测算法)

  • “男性作者”或者“女性作者”(是的,文档中存在暗示作者性别的线索)

  • “技术类”,“政治类”,“金融类”,“体育类”(如果你需要对报纸上的老文章进行自动分类)

今天我们将要解决一个简单的问题:语言检测。换一种说法就是:“对于一段给定的文本判断它是西班牙语,英语还是法语”。

自然语言处理基础

首先,我们必须要改变我们看待“文档”的方式。本质上,文档只是有序字符的集合。字符可以是字母也可以不是。字符组成单词,单词带有含义。有时候标点符号会改变单词的含义,有时候标点符号并不重要(see what I did here?)。我们通常通过研究文档中的单个单词来研究文档。如果实际环境要求的话有时候我们会一次研究多个单词(单词对叫做“bigram”),但是因为本文只是贝叶斯系列的“第一部分”所以我们将暂时只考虑单个单词(unigram)。

因为自然语言本身是非常古怪和复杂的,我们通常会努力地简化它;即我们会努力地减小系统的熵。如果你同时考虑大写和小写字母的话,你可以创造730万个不同的四字母单词。如果你只考虑小写字母的话,这个数字会减低到45万。为什么简化很重要,因为你想要你的系统处理尽可能多的数据,而分别处理"YOU'RE"和"you're"和"You're"会把关于同一个概念的知识分割开。把这些全部转化为一个简单的"you're"是最好的,因为它允许你去研究"you're"这个词的概念而不是这个词的不同语法。

当然更多的高级数据科学家会承认说有时你确实需要语言的这些古怪特性留在你的系统中。举个例子,在识别垃圾邮件时,事实证明"offer"和"OFFER"是两个非常不同的东西。因为这个原因,通常垃圾邮件检测算法不会基于字符大小写来标准化文档。类似的,"money back"和"money back!!!!"也有非常不同的意义,所以垃圾邮件检测算法通常会把标点符号原封不动的保存下来。

你可能也会决定说你想要把"imagine","imagination","imaginary"这三个单词的意义统一起来。要做到这点,你可以砍掉每个单词的结尾,把它们转化为"imagin"--它既不是一个动词也不是一个名词,既不是单数也不是复数它仅仅是一个概念。这个概念是"词根",它用于把具有相同意义的不同单词当成同一个实体来处理。这些熵减技术在整个机器学习中都非常重要,因为学习算法的训练集通常是有限的。

把一个文档划分为可以研究的离散块的过程叫做"tokenization"。我们暂时会使使用简单的tokenization技术:我们移除所有的标点符号,将字符转化为小写,然后通过空格把文档划分为token。

贝叶斯定理

我不会讨论关于贝叶斯定理的数学,因为有兴趣的读者可以凭借自己的力量轻易地学会概率论基础和贝叶斯定理。取而代之,我会专注于让你对这一重要的概率论工具有直觉上的认知。

我们试图求出一个未知的文档是用什么语言写作的。我们有一堆预标记的英语,法语和西班牙语文档。因为在上文我们明确说我们可以通过检查文档中单个单词来了解文档,所以让我们从这里开始吧。

如果你关注文档中的一个单词,你可以轻易地计算出它在训练数据中的频次。使用这个信息,你可以确定特定语言使用特定单词的概率。举个例子,"Vous"在所有法语文档中都出现了(100%),西班牙语文档中没有出现,少部分英语文档中有出现(5%)。这是一个伟大的线索!这个文档是法语文档。

但是不对,我们不可以这么快下结论。因为“vous”当然是一个法语词汇但不意味着文档本身是一个法语文档。它可能是一篇英文小说引用了一个法语字符。所以我们不能像刚刚尝试的那样只是简单地看“法语文档包含'vous'的概率” 。反过来,我们需要确定“对于一个有'vous'单词的文档是法语文档的概率”。幸运的是,贝叶斯定理就是这么做的。如果我们把上面捏造的数代入贝叶斯定理,我们会发现如果文档中有'vous',那么有98%的机会,这个文档是法语文档。计算公式非常的简单,请看:贝叶斯定理.

当然,如果文档中的下一个短语是“said Jean Pierre, the French museum curator”,我们就知道这个文档是法语文档的概率低了很多。所以我们会按顺序查看每个单词,计算“给定的单词出现在文档的条件下文档是(法语|英语|西班牙语)的概率”。我们把这些单独的概率联合起来求出一个整体的“在这些单词都出现在文档的条件下文档是法语的概率”。如果这个概率足够高,我们就认为它是法语文档。

为什么它有效

朴素贝叶斯分类器之所以被这样叫是因为它假设文档中的每一个单词和它的下一个单词无关。这是一个朴素假设。但事实是,虽然朴素,它确是一个优秀的简化假设;像这样单独地研究单词可以得到非常好的结果。你也可以研究bigram(双字词)或者trigram(三字词)(两个或三个单词的集合),那时,这个分类器不再朴素但它将需要更多的训练数据和存储空间。

朴素贝叶斯分类器对于文档分类工作良好的原因是,它使得在给定语言单词的频数与它的统计重要性相关。单词“a”在很多语言中都会出现。甚至在你的英语训练集中它可能100%出现。但这不意味着有这个单词的文档是英语文档。我们使用贝叶斯来把‘a’出现在英语文档中的概率(100%)转化为,在a出现的条件下文档是英语文档的概率(可能50%)。

因此,在所有类别中都有的共同部分被赋予一个较小的权重,只在一个类别中独有的部分被赋予一个较大的权重。最终结果非常的优越,算法虽然简单,但错误率低(相对低)。这不是魔术,这里也没有神经网络,这里也没有“智能”,它只是数学和概率论。

代码: 训练

像往常一样,让我们深入代码吧。文档分类器需要做的第一件事就是用给定的文本和文本标签进行训练。因为我决定构建一个尽可能通用的分类器,我们将不会硬编码标签甚至都不会限制使用的标签数目。(虽然只有两个标签的朴素贝叶斯分类器比较容易构建比如垃圾邮件/非垃圾邮件分类器。)

Bayes.train = function (text, label) {  
    registerLabel(label);
    var words = tokenize(text);
    var length = words.length;
    for (var i = 0; i < length; i++)
        incrementStem(words[i], label);
    incrementDocCount(label);
};

registerLabel函数把标签(label)添加到“数据库”(本例中,数据库是localStorage)中以便后面我们可以取回标签(label)列表。

在这个案例中我们的tokenize函数实现的非常简单。我们将在其它文章中讨论更有趣的tokenization技术(tokenization是分类器中非常重要的一个部分)。以下是我们的一个浅显直白的实现:

var tokenize = function (text) {  
    text = text.toLowerCase().replace(/\W/g, ' ').replace(/\s+/g, ' ').trim().split(' ').unique();
    return text;
};

在这个案例中,我们使用unique()函数,因为我们只是关心一个单词是否出现在文档中,而不关心它出现的次数。在某些特定的情况下,考虑一个单词在文档中出现的次数可能会得到更好的结果。

然后我们遍历每个单词(“token”),然后以它和标签(label)为实参调用incrementStem函数。这个函数也非常简单,它只记录某一类(label)文档中出现该单词的文档的数目。

最后,我们调用incrementDocCount函数,它记录某一类(label)文档的总数目。

训练的最终结果是,我们有一个数据库,它存储我们曾看到的每一个label(在这个例子中即是“英语”,“西班牙语”,“法语”),并且存储了某个label下某个单词出现的次数(例如,“le”在法语文档中出现了30次),还有每个label的文档数目(例如,总共有40个法语文档)。

代码: 预测

如上文展示的那样,训练一个朴素贝叶斯分类器是如此的简单和快速。预测一个给定文档的label则稍微有点困难,但是对于理解概率论的人来说,写一个预测算法并不难。如果你不理解概率论那也没有关系,你可以先花时间研读朴素贝叶斯分类器然后再回来研究这个例子。

我们的预测函数将会做的第一件事(除了初始化变量,细节请查看JSFiddle)是记录一些量。

for (var j = 0; j < labels.length; j++) {  
    var label = labels[j];
    docCounts[label] = docCount(label);
    docInverseCounts[label] = docInverseCount(label);
    totalDocCount += parseInt(docCounts[label]);
}

我们的目标是为后面计算特定的概率做准备。为了实现这个目的,我们需要知道每类(label)文档的数目(docCounts),我们也需要不属于此类(label)的文档数目(docInverseCounts)。最后我们需要知道所有文档的数目。

你可以翻转这个函数然后通过从总文档数目中减去某类(label)文档数目来得到非某类(label)文档数目--事实上这个方法更好也更快,但我用一个显式的docInverseCount函数来实现,因为它使得代码更易读。

基于上面的信息我们可以确定,任何一个文档是法语文档的概率。我们也可以知道任何一个文档不是法语文档的概率。

for (var j = 0; j < labels.length; j++) {  
    var label = labels[j];
    var logSum = 0;
    ...

然后,对于每一个label我们建立一个logSum变量,它将存储文档属于这个label的概率。

for (var i = 0; i < length; i++) {  
    var word = words[i];
    var _stemTotalCount = stemTotalCount(word);
    if (_stemTotalCount === 0) {
        continue;
    } else {
        var wordProbability = stemLabelCount(word, label) / docCounts[label];
        var wordInverseProbability = stemInverseLabelCount(word, label) / docInverseCounts[label];
        var wordicity = wordProbability / (wordProbability + wordInverseProbability);

        wordicity = ( (1 * 0.5) + (_stemTotalCount * wordicity) ) / ( 1 + _stemTotalCount );
        if (wordicity === 0)
            wordicity = 0.01;
        else if (wordicity === 1)
            wordicity = 0.99;
   }

    logSum += (Math.log(1 - wordicity) - Math.log(wordicity));
}
scores[label] = 1 / ( 1 + Math.exp(logSum) );

上面的代码是算法的核心。对于我们考虑的每一个标签,我们都会分别用文档中的每一个单词来计算它的概率。_stemTotalCountFor变量存放单词在所有训练文档中出现的次数。如果这个单词从未在训练数据中出现过,那么就跳过它,我们没有任何关于它的信息,为什么还要用它呢?

wordProbability变量代表“这个单词出现在[法语|英语|西班牙语]文档中的概率”。如果训练数据中有40个法语文档,其中30个有“le”这个单词那么这个值是0.75。wordInverseProbability变量是单词出现在其它类文档的概率。

难以理解的变量wordicity是对上面的两个变量应用贝叶斯定理后得到的结果。wordProbability变量代表“[法语]文档中有[le]的概率”,而wordicity变量代表“含有[le]的文档是[法语]文档的概率”。这个个区别虽然很微妙但是很重要。如果你很难理解在这一点上的区别,我强烈推荐你大声朗读这两个短语,并且在确保你已经理解了这个差异之前先停下来。

上面求wordicity的代码同样假设了,英语,法语和西班牙语文档是同样常见的(这里的意思是说,一个文档是任何语种的文档的先验概率都是50%)。这个假设稍微简化了这个计算,但是如果你想你也可以考虑每个语言的先验概率。后文会讨论这一点。

对于在训练数据中只出现了几次的单词我们在变量wordicity定义下面的一行代码中对它的概率进行调整。例如,如果一个单词只出现了一下,你就无法从这个单词中得到足够多的信息来决定这篇文档是法语还是西班牙语,所以需要进行概率调整。如果一个单词在训练数据中出现的次数较少,我们对wordicity进行一个加权调整,使它的值接近50%。等式中的“0.5”是我们希望调整到的值,等式中的“1”是权重--如果增大权重,wordicity的值调整到0.5的速度将减慢。如果你有一个很大的训练数据集,你可以设置权重为5或者10或20或者50(取决于你的数据集有多大)。因为我有一个非常小的训练集(我的训练集只有15篇文章),我把权重设置为1,但事实上,我甚至应该完全省略掉这行调整代码。这里我只想要展示说,你可以调整那些很少出现的单词的概率。

下面一部分代码,因为我们将要使用log函数,所以我们避免让wordicity取0或者1因为者两个值会使我们的结果无意义。

logSum这行代码并不是数学公式的一部分而是实际工程上的考虑。在计算了每个单词的wordicity以后我们需要用某种方法把这些概率联合起来。这样做的正常数学方法是,将每个概率相乘,然后除以每个互补概率(即1-概率)的乘积加上原本概率的乘积。不幸的是,浮点数计算是不精确的,你可能会遭遇“浮点数下溢”--数字太小了以至于浮点数运算无法处理。所以,取而代之,我们取分子和分母(概率是分母互补概率是分子)的对数,然后再把对数相加。

最后,在我们用logSum行的代码联合了每个单独单词的概率以后,我们撤销我们刚刚使用的log函数使概率回到0到1之间。注意,这一步发生在“遍历每个单词”的循环外,但仍然在“遍历每个label”的循环中。

重要的假设和注意事项

我想要指出的是,我们在上面做了一个大的简化假设:我们假设英语,法语和西班牙语文档都是以相等的概率出现(50%)。在我们的例子中,由于我们将只会用这个分类器预测其中一种语言的文档,这是一个可以接受的假设,但在现实世界中,这不一定是对的。

贝叶斯分类算法允许你考虑文档语言的先验概率(意味着,你不需要考虑文档的内容,而基于文档总数中英语文档的数量确定文档是英语文档的概率), 但是我把这一步省略掉了。把它加到算法中并不困难,只要在wordicity的计算中添加几项就可以了。我将会写的下一篇关于贝叶斯的文章,将会使用定理的完整形式。

最后,请注意,在训练算法上这件事上我是非常懒惰的。你可以从JSFiddle中看到,每种语言我只用了5个段落来训练。这还远远不够,因为分类器只认识在训练数据集中出现的单词。我发现这个示例对于句子和段落(从新闻站点复制粘贴内容来实验)的识别效果很好,但对简单的单词和短语识别效果不佳。 举个例子,对于“la tortuga”(西班牙语乌龟的意思),因为在训练数据集中没有出现过“tortuga”,所以算法将认为它是法语,因为“la”在法语中出现的概率比西班牙语高。一个更大的训练数据集可以修复这个问题。

结果

我们基本上完成了。现在我们要做的事情是,报告文档属于每种语言的概率,或者直接报告文档属于的语言。尝试粘贴一些英语,法语,或者西班牙语新闻文本到下面的JSFiddle--你应该可以看到预测的语言和预测的概率。这个算法对于句子和段落的效果比较好因为预测的文档中单词的数目越多,文档中的单词在训练数据集中出现的概率就越高,预测就越准确。

到目前为止,算法对从新闻网站复制粘贴而来的句子的正确率是100%。在下面自己尝试和研究一下吧。

如果你喜欢这篇文章或者觉得它有用,你可以考虑:

  • 和你的Facebook或Twitter好友分享。

  • 在Hacker News或者Reddit中讨论它。

  • 在下方的评论区中讨论它。

  • 在Twitter上关注我@bkanber

  • 阅读其它的ML in JS文章

  • 订阅下面的ML in JS邮件列表-我只会发送关于新文章的邮件,你不会收到垃圾邮件,你的个人信息也不会被泄漏。

译者haoming尚未开通打赏功能

相关文章