EdmondFrank's 时光足迹

この先は暗い夜道だけかもしれない それでも信じて進むんだ。星がその道を少しでも照らしてくれるのを。
或许前路永夜,即便如此我也要前进,因为星光即使微弱也会我为照亮前途。
——《四月は君の嘘》

Geek的写作方式——LaTeX 入门

Geek的写作方式——LaTeX 入门

有关LaTex的简介

说道LaTex首先要提到TeX (文本排版系统)
TeX是由著名的计算机科学家Donald E. Knuth(高德纳)发明的排版系统,利用TeX可以很容易地生成高质量的dvi文件,打印输出。利用dvips,dvipdfmx,pdfLaTeX等程序生成pdf,ps,文件,LaTeX2html生成html文件。它在学术界十分流行,特别是数学、物理学和计算机科学界。TeX被普遍认为是一个很好的排版工具,特别是在处理复杂的数学公式时。

而LaTeX使用TeX作为它的格式化引擎。
Leslie Lamport开发的LaTeX是当今世界上最流行和使用最为广泛的TeX宏集。它构筑在Plain TeX的基础之上,并加进了很多的功能以使得使用者可以更为方便的利用TeX的强大功能。使用LaTeX基本上不需要使用者自己设计命令和宏等,因为LaTeX已经替你做好了。因此,即使使用者并不是很了解TeX,也可以在短短的时间内生成高质量的文档。对于生成复杂的数学公式,LaTeX表现的更为出色。

LaTex的应用

  1. 使用 (La)TeX进行简单的中英混排;
  2. 简单的文章组织结构;
  3. 使用 (La)TeX 进行数学公式的排版;
  4. 在 (La)TeX 的文档中插入图片/表格;
  5. 最常见的带有 TeX 的单词的含义;

简单的规则

为了实现强大的排版能力,LaTex背后定义了一些非常严谨的语法和规则。
(1)空格:Latex中空格不起作用。
(2)换行:用控制命令“\”,或“ \newline”.
(3)分段:用控制命令“\par” 或空出一行。
(4)换页:用控制命令“\newpage”或“\clearpage”
(5)特殊控制字符:#,$, %, &, - ,{, }, ^, ~
要想输出这些控制符用下列命令:

\# \$ \% \& \- \{ \} \^{} \~{} 其中 \blackslash 表示“ \”。

在讲具体如何使用LaTex之前,先给大家推荐一下LaTex在线编辑器方便大家做测试。

kityformula:WEB mathematical formulas projects ,同时项目的Github地址在「这里

尝试第一次中英文排版

\documentclass[UTF8]{article}
%这里是导言区
\begin{document}
Blahblahblah... 
你好,世界。etc.
\end{document}

此处的第一行 \documentclass{article} 中包含了一个控制序列(或称命令/标记)。所谓控制序列,是以反斜杠\开头,以第一个空格或非字母 的字符结束的一串文字,他们并不被输出,但是他们会影响输出文档的效果。这里的控制序列是 documentclass,它后面紧跟着的 {article} 代表这个控制序列有一个必要的参数,该参数的值为 article。这个控制序列的作用,是调用名为 “article” 的文档类。

方括号[]包括的可选参数,这里表示采用UTF-8编码。

请注意,(La)TeX 对控制序列的大小写是敏感的。

此处的第二行以 % 开头。在 TeX 风格的文档中,从 “%” 开始,到该行末尾的所有字符,都会被 TeX 系统无视,只作为供人类阅读的注释。除非在 “%” 前加上反斜杠来取消这一特性。

组织你的文章

作者、标题、日期

\documentclass{article}
\title{Cartesian closed categories and the price of eggs}
\author{Jane Doe}
\date{September 1994}
\begin{document}
   \maketitle
   Hello world!
\end{document}

章节和段落

\documentclass[UTF8]{ctexart}
\title{hello,world!}
\author{Liam}
\date{\today}
\begin{document}
\maketitle
\section{你好,世界}
Welcome to 中国.
\subsection{Hello China}
北京是capital of China.
\subsubsection{Hello BeiJing}
\paragraph{Tian'anmen Square}
is in the center of Beijing
\subparagraph{Chairman Mao}
is in the center of 天安门广场。
\subsection{Hello 广东}
\paragraph{中山大学} is one of the best university in 广东。
\end{document}

在文档类 article/ctexart 中,定义了五个控制序列来调整行文组织结构。他们分别是

  • \section{·}
  • \subsection{·}
  • \subsubsection{·}
  • \paragraph{·}
  • \subparagraph{·}

插入目录

在上一节的文档中,找到 \maketitle,在它的下面插入控制序列 \tableofcontents

\documentclass[UTF8]{ctexart}
\title{hello,world!}
\author{Liam}
\date{\today}
\begin{document}
\maketitle
\tableofcontents
\section{你好,世界}
Welcome to 中国.
\subsection{Hello China}
北京是capital of China.
\subsubsection{Hello BeiJing}
\paragraph{Tian'anmen Square}
is in the center of Beijing
\subparagraph{Chairman Mao}
is in the center of 天安门广场。
\subsection{Hello 广东}
\paragraph{中山大学} is one of the best university in 广东。
\end{document}

数学公式排版

数学公式排版功能是LaTeX 最为强大的部分。

数学模式

LaTeX 的数学模式有两种:行内模式 (inline)行间模式 (display)。前者在正文的行文中,插入数学公式;后者独立排列单独成行,并自动居中。

在行文中,使用 可以插入行内公式,使用 [ … ] 可以插入行间公式,如果需要对行间公式进行编号,则可以使用 equation 环境:
eg:

\begin{equation}
...
\end{equation}

上下标

\documentclass{article}
\usepackage{amsmath}
\begin{document}
Einstein 's $E=mc^2$.

\[ E=mc^2. \]

\begin{equation}
E=mc^2.
\end{equation}
\end{document}

示例如下:

在数学模式中,需要表示上标,可以使用 ^ 来实现(下标则是 _)。它默认只作用于之后的一个字符,如果想对连续的几个字符起作用,请将这些字符用花括号 {} 括起来。

根式与分式

根式用 \sqrt{·} 来表示,分式用 \frac{·}{·} 来表示(第一个参数为分子,第二个为分母)。

\documentclass{article}
\usepackage{amsmath}
\begin{document}
\sqrt{x}$, $\frac{1}{2}$.
\[ \sqrt{x}, \]
\[ \frac{1}{2}. \]
\end{document}

示例如下:

运算符号

一些小的运算符,可以在数学模式下直接输入;另一些需要用控制序列生成。
[ \pm\; \times \; \div\; \cdot\; \cap\; \cup\;
\geq\; \leq\; \neq\; \approx \; \equiv ]

示例如下:

连加、连乘、极限、积分等大型运算符分别用 \sum, \prod, \lim, \int生成。他们的上下标在行内公式中被压缩,以适应行高。我们可以用 \limits 和 \nolimits 来强制显式地指定是否压缩这些上下标。
\sum_{i=1}^n i
\prod_{i=1}^n
\sum\limits {i=1}^n i\quad \prod\limits {i=1}^n
[ \lim_{x\to0}x^2 \quad \int_a^b x^2 dx ]
[ \lim\nolimits _{x\to0}x^2\quad \int\nolimits_a^b x^2 dx ]

示例如下:




多重积分可以使用 \iint, \iiint, \iiiint, \idotsint 等命令输入。
[ \iint\quad \iiint\quad \iiiint\quad \idotsint ]

示例如下:

定界符(括号等)

各种括号用 (), [], {}, \langle\rangle 等命令表示;
注意花括号通常用来输入命令和环境的参数,所以在数学公式中它们前面要加 \。

[ \Biggl(\biggl(\Bigl(\bigl((x)\bigr)\Bigr)\biggr)\Biggr) ]

示例如下:

省略号

省略号用 \dots, \cdots, \vdots, \ddots 等命令表示。\dots 和 \cdots 的纵向位置不同,前者一般用于有下标的序列。
[ x_1,x_2,\dots ,x_n\quad 1,2,\cdots ,n\quad
\vdots\quad \ddots ]

示例如下:

矩阵

pmatrix, bmatrix, Bmatrix, vmatrix, Vmatrix 等环境可以在矩阵两边加上各种分隔符。

\[ \begin{pmatrix} a&b\\c&d \end{pmatrix} \quad
\begin{bmatrix} a&b\\c&d \end{bmatrix} \quad
\begin{Bmatrix} a&b\\c&d \end{Bmatrix} \quad
\begin{vmatrix} a&b\\c&d \end{vmatrix} \quad
\begin{Vmatrix} a&b\\c&d \end{Vmatrix} \]

示例如下:




而使用 smallmatrix 环境,可以生成行内公式的小矩阵。

( \begin{smallmatrix} a&b\\c&d \end{smallmatrix} )

示例如下:
this is a little matrix .

公式组

无需对齐的公式组可以使用 gather 环境,需要对齐的公式组可以使用 align 环境。他们都带有编号,如果不需要编号可以使用带星花的版本。

\begin{gather}
a = b+c+d \\
x = y+z
\end{gather}
\begin{align}
a &= b+c+d \\
x &= y+z
\end{align}

示例如下:

分段函数

分段函数可以用cases次环境来实现,它必须包含在数学环境之内。

\begin{equation} y=\begin{cases}
-x,\quad x\leq 0 \\
x,\quad x>0
\end{cases}
\end{equation}

示例如下:

插入图表

在LaTeX文档中插入图片都是通过使用一些latex图形处理宏命令来实现的, 有很多宏命令都支持在在LaTeX文档中插入eps格式的图形文件, 主要有:
(1)用includegraphics宏命令(graphicx包)
(2)用psfig宏命令
(3)用epsfig宏命令
(4)用epsf宏命令
由于插入图片较为麻烦,且不如Markdown语法方便,这里就略过了。有兴趣的朋友可以自行查询下命令的使用方法。

表格

tabular 环境提供了最简单的表格功能。它用 \hline 命令表示横线,在列格式中用 | 表示竖线;用 & 来分列,用 \\ 来换行;每列可以采用居左、居中、居右等横向对齐方式,分别用 l、c、r 来表示。

\begin{tabular}{|l|c|r|}
 \hline
OS& Release& Editor\\
 \hline
Windows & MikTeX & TexMakerX \\
 \hline
Unix/Linux & teTeX & Kile \\
 \hline
Mac OS & MacTeX & TeXShop \\
 \hline
通用& TeX Live & TeXworks \\
 \hline
\end{tabular}

示例如下:

OS Release Editor
Windows MikTeX TexMakerX
Unix/Linux teTeX Kile
Mac OS MacTeX TeXShop
通用 TeX LIve TeXworks

其他

到目前为止,常用的(La)Tex常用的功能已经介绍的基本差不多了。
当然,除此之外,(La)Tex还有一些版面设置,以及常用字母符号输入等功能。
例如我们常用的希腊字母

\alpha \beta \gamma \theta\omega \mu \pi \dots

示例如下:

到此文章基本结束了,但依旧还有十分多的功能(不常用)没有在此文提及。有兴趣的朋友可以自行查询LaTex相关手册

如何在Python中实现决策树算法

如何在Python中实现决策树算法

决策树算法是一种简单的预测算法,但正是因为它模型的简单性,常作为一些高级的组合算法的基础,例如bagging,random forests ,gradient boosting 等等。再者,由于决策树的最终模型和预估行为具有较强的业务相关与可解析性,使得它十分受从业者与领域专家的欢迎,在各行各业中也有十分多的应用。

决策树的优缺点

优点:计算复杂度不高,输出结果易于理解,对中间值的缺失不敏感,可以处理不相关特征数据

缺点:可能会产生过拟合问题

决策树的构建

在构建决策树之前,我们首先要明确的第一个问题就是:在当前的数据集上哪个特征在划分数据分类时起决定性作用。而其中划分数据集的最大原则就是:将无序的数据变得更加有序。

在选择如何去划分数据集的时候,我们可以采用各种不同的方法。但是每种方法都有各自的优缺点。组织杂乱无章的数据的一种方法就是使用信息论度量信息。

在划分数据集之前之后信息发生的变化称为信息增益,而获得信息增益最高的特征就是我们用于划分数据的最好选择。

在评测哪种数据划分方式是最好的数据划分之前,我们必须学习如何计算信息增益,而为了能够计算和理解信息增益,我们又必须先了解一个概念,即:集合信息的度量方式,其被称为香农熵或简称。这个名字来源于信息论之父克劳德×香农

熵:被定义为信息的期望值,如果一个事件发生的概率是,则其信息熵为:

Eg:enter image description here

其中n是分类的数目。

可以这样验证一下:如果这件事发生的概率是1,其信息熵则等于0,因为你知道他一定会发生,丝毫不会觉得惊喜;但是如果这件事的概率趋向于无穷小,比如国足夺得世界杯冠军,那么他的信息熵就会趋向于无穷大。就像你心中听完上一条信息之后,心中可能就有数十万只草泥马奔过一样。

使用Python计算信息的熵

下面我们将以《机器学习实战》一书中给出的例子为基础进一步探讨本文所讲内容。

海洋生物数据表

index 不浮出水面是否可以生存 是否有脚蹼 是否属于鱼类
0
1
2
3
4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#coding:utf-8
# 代码功能:计算香农熵,本代码来源于书籍《机器学习实战》
from math import log #我们要用到对数函数,所以我们需要引入math模块中定义好的log函数(对数函数)

def calcShannonEnt(dataSet):#传入数据集
# 在这里dataSet是一个链表形式的的数据集
    countDataSet = len(dataSet) # 我们计算出这个数据集中的数据个数,在这里我们的值是5个数据集
    labelCounts={} # 构建字典,用键值对的关系我们表示出 我们数据集中的类别还有对应的关系
    for featVec in dataSet: #通过for循环,我们每次取出一个数据集,如featVec=[1,1,'yes']
        currentLabel=featVec[-1] # 取出最后一列 也就是类别的那一类,比如说‘yes’或者是‘no’
        if currentLabel not in labelCounts.keys():
            labelCounts[currentLabel] = 0
        labelCounts[currentLabel] += 1

    shannonEnt = 0.0 # 计算香农熵, 根据公式

    for key in labelCounts:
        prob = float(labelCounts[key])/countDataSet
        shannonEnt -= prob * log(prob,2)


    return shannonEnt
def createDataSet():
    dataSet = [[1,1,'yes'],
              [1,1,'yes'],
              [1,0,'no'],
              [0,1,'no'],
              [0,1,'no']]


    labels = ['no surfacing','flippers']

    return dataSet, labels

myDat,labels = createDataSet()
print(myDat)
print(labels)
calcShannonEnt(myDat)

输出结果:
[[1, 1, ‘yes’], [1, 1, ‘yes’], [1, 0, ‘no’], [0, 1, ‘no’], [0, 1, ‘no’]]
[‘no surfacing’, ‘flippers’]
0.9709505944546686

其中,香农熵越高,则代表混合的数据越多,这点我们可以通过在数据集中添加更多的分类来验证。

1
2
3
myDat[0][-1]='maybe'
print(myDat)
calcShannonEnt(myDat)

输出结果:
[[1, 1, ‘maybe’], [1, 1, ‘yes’], [1, 0, ‘no’], [0, 1, ‘no’], [0, 1, ‘no’]]
1.3709505944546687

划分数据集

分类算法除了需要测量信息熵之外,还需要划分数据集,度量划分数据集的熵,以便判断当前是否正确地划分了数据集。

那么,我们如何确定目前划分数据的方法是否就是最优的划分方法呢?答案就是:信息增益。我们仅需选择使得划分后数据集信息增益最大的特征作为分类的最佳特征即可。

首先假设我们选取了第一个特征“是否需要浮出水面生存”的第一种可能“是”来划分数据集,我们得到划分之后的数据集就是:

[[1, 1, ‘maybe’], [1, 1, ‘yes’], [1, 0, ‘no’]

“否”的话,得到的划分集则是:

[[0, 1, ‘no’], [0, 1, ‘no’]]

其他特征的划分方式也以此类推。

知道如何划分数据集之后,让我们来构建我们下一步的数据划分代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
# 代码功能:划分数据集
def splitDataSet(dataSet,axis,value): #传入三个参数第一个参数是我们的数据集,是一个链表形式的数据集;第二个参数是我们的要依据某个特征来划分数据集
    retDataSet = [] #由于参数的链表dataSet我们拿到的是它的地址,也就是引用,直接在链表上操作会改变它的数值,所以我们新建一格链表来做操作

    for featVec in dataSet:
        if featVec[axis] == value: #如果某个特征和我们指定的特征值相等
        #除去这个特征然后创建一个子特征
            reduceFeatVec = featVec[:axis]
            reduceFeatVec.extend(featVec[axis+1:])
            #将满足条件的样本并且经过切割后的样本都加入到我们新建立的样本中
            retDataSet.append(reduceFeatVec)

    return retDataSet

下面来测试下我们的代码

1
splitDataSet(myDat,0,1)

[Out] [[1, ‘maybe’], [1, ‘yes’], [0, ‘no’]]

1
splitDataSet(myDat,0,0)

[Out] [[1, ‘no’], [1, ‘no’]]

知道怎么划分数据集之后,我们接下来要做的就是遍历整个数据集的特征值,然后循环计算熵,找出最好的分类特征了。

选择最好的数据划分方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def chooseBestFeatureToSplit(dataSet):
    numFeatures = len(dataSet[0])-1
    baseEntropy = calcShannonEnt(dataSet)
    bestInfoGain =0.0
    bestFeature = -1

    for i in range(numFeatures):
        featList = [sample[i] for sample in dataSet]
        uniqueVals = set(featList)
        newEntropy = 0.0
        for value in uniqueVals:
            subDataSet = splitDataSet(dataSet,i,value)
            prob = len(subDataSet)/float(len(dataSet))
            newEntropy += prob * calcShannonEnt(subDataSet)

        infoGain = baseEntropy - newEntropy

        if(infoGain > bestInfoGain):
            bestInfoGain = infoGain
            bestFeature = i

    return bestFeature

这里的choseBestFeatureToSplit()函数的使用是需要满足一定条件的:
1. 数据必须是一种有列表元素组成的列表,而且所有的列表元素都要具有相同的数据长度。
2. 数据的最后一列或者每个实例的最后一个元素是当前实例的类别标签

接下来,我们来运行choseBestFeatureToSplit()函数来计算出最佳分类特征。

1
chooseBestFeatureToSplit(myDat)

[Out] 0

从这里我们可以得到第0个特征是最好用于划分数据集的特征。确实,这个分类特征的选择就我们目测而言也是最好的选择。

知道如何选取特征之后,下一步我们就要如何将上面的函数有机结合在一起构建出决策树。

处理特殊情况

工作原理:
1. 得到原始数据集
2. 基于最好的属性值划分数据集
3. 由于特征值不止一个,将划分后的数据传递到树分支的下一个节点,再重复2操作
4. 程序遍历完所有划分数据集属性或每个分支下所有实例都具有相同分类后结束

1
2
3
4
5
6
7
8
9
10
11
def majorityCnt(classList): # 传入的参数是已经划分完所有特征之后剩余的数据集,
    #例如[['yes'],['yes'],['maybe']]
    classCount={} #创建一个字典
    for vote in classList:
        if vote not in classCount.keys():
            classCount[vote] = 0
        classCount[vote] += 1
        # 根据上述的语句,以及我们的例子,我们最终可以得到的结果如下: {'yes':2,'maybe':1}
        sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1),reverse=True)#这个语句比较复杂,我们在下面详细讲解一下。
# 使用字典iteritems
    return sortedClassCount[0][0]

这里的majorityCnt()函数是为了处理特殊分类而存在的。我们知道如果根据特征来划分属性,每划分一次就会消耗一个特征,如果我们使用完了所有的特征但是类别还没有划分完那我们就可以采用多数表决的方法来确定叶子节点了。

在上面的代码中,我们发现最后我们用排序函数对剩余的类作了降序处理,并只返回了分类个数最多的元素的那个类。这是一种折中的方法,因为对于一些已经使用完特征的数据集,我们不可能清楚地将一些类分离出来,我们就只能统计其中数量最多的那个分类,以次划分。

递归构建决策树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def createTree(dataSet,labels):
    classList = [example[-1] for example in dataSet]

    if classList.count(classList[0]) == len (classList):
        return classList[0]

    if len(dataSet[0]) == 1:
        return majorityCnt(classList)

    bestFeat = chooseBestFeatureToSplit(dataSet)
    bestFeatLabel = labels[bestFeat]

    myTree = {bestFeatLabel:{}}

    del(labels[bestFeatL])

    featValues = [example[bestFeat] for example in dataSet]

    uniqueVals = set(featValues)

    for value in uniqueVals:
        subLabels = labels[:]
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet,bestFeat,value),subLabels)


    return myTree

最后,我们来运行我们的代码来构建出一棵决策树看看。

1
print(createTree(myDat,labels))

输出结果
[‘no surfacing’, ‘flippers’]
0
no surfacing
[‘flippers’]
0
flippers
{‘no surfacing’: {0: ‘no’, 1: {‘flippers’: {0: ‘no’, 1: ‘yes’}}}}

根据返回的结果,我们可以画出以下的决策树。
dt.png

Laplace变换

拉普拉斯变换

对于复值函数,若在复平面上的某一个区域 内收敛于,则称:

为函数的拉普拉斯变换(Laplace)变换(简称拉氏变换),记为

在科技领域,一般是对时间为自变量的函数进行拉普拉斯变换,即在t < 0时,函数无意义或不需要考虑。

线性性质

为常数,

时移性质

,对于,有

频移性质

,则对任意常数a,有

微分性质

,且

这里,

,则

积分性质

,则

,积分收敛,则的拉普拉斯变换存在,且

极限性质

1.初值关系
,则

2.终值关系
的所有奇点在半平面,则

如何构建一个朴素贝叶斯分类器

如何构建一个朴素贝叶斯分类器

概念

朴素贝叶斯分类是一些使用概率论来进行分类的方法中的一种代表。之所以成为为朴素,是因为整个形式化过程只做了最原始,最简单的假设。其具体表现为:在分类过程中,我们都假设为特征条件都是相互独立的,不互相构成影响。而贝叶斯即说明该方法是基于贝叶斯定理的。

朴素贝叶斯是贝叶斯决策理论的一部分,对比其他分类方法而言,其优点有:在数据较少的情况下仍然有效,并且可以处理多类别的问题,而不仅仅是二分类。也存在对输入数据的准备方式较为敏感的缺点。

目前在各方面的应用

  1. 垃圾邮件分类,即著名的贝叶斯过滤器
  2. 文本自动归类
  3. 文本情感的分析,话题分析。

核心思想

beyas.png

现在假设我们有一张如上所示的两类数据的统计参数。
我们现在用p1(x,y)来表示数据点(x,y)属于类别X(图中的蓝点)的概率,用p2(x,y)表示数据点属于类别Y(图中的黄点)的概率。那么对于一个新的数据点(x,y),我们可以用以下的规则来判断它的类别:

也就是说,我们更倾向于选择高概率所对应的类别。这就是贝叶斯决策理论的核心思想。用一句话总结即:选择具有最高概率的决策。

使用条件概率进行分类

从上面的推理我们得到两个分类准则:

但是,这两个准则只是为了简化描述整个分类问题,而真正来说,在使用贝叶斯方法进行分类时,我们需要计算和比较的应该是 p(X|x,y) 和 p(Y|x,y) ,它们所代表的意义是:在给定某个由(x,y)表示的数据点之后,它来自X类别的概率和它来自Y类别的概率分别是多少?知道这点之后,我们来重新定义我们的分类准则:

然后,我们可以再通过贝叶斯公式的转换把未知的概率用已知的概率计算出来。

使用实例:垃圾邮件判别
首先,我们假设有以下的统计数据:

  • 在74封电子邮件中,有30封为垃圾邮件。
  • 在以上的74封电子邮件中,有51封邮件包含“sex”一词。
  • 其中,20封包含了“sex”一词的邮件被认为是垃圾邮件。

知道了以上这些简单的前提条件之后,我们可以尝试通过贝叶斯方法来求解我们下一封收到包含“sex”一词的邮件是垃圾邮件的概率是多少?

其中,公式中的spam代表垃圾邮件的意思(1937年7月5日,美国罐头肉制造商Jay Hormel发布以其名字命名的「Hormel Spiced Ham(荷美尔香料火腿)」,后来通过命名比赛改名为 SPAM(Spiced Pork and Ham),有添加香料(Spices)的猪肉火腿罐头。至于为何 SPAM演变成垃圾邮件呢?有一说法是源于一部英国喜剧团(Monty Python)曾在一出讽刺剧「spam-loving vikings(爱吃肉罐头的维京人),剧中有对夫妻去餐厅用餐,妻子不想吃SPAM罐头,可是在餐厅里有一大群人,高声地唱讼赞美「SPAM」称颂肉罐头的美味多达120次,让其他的用餐客人无可奈何。从此 SPAM就成为「重复、毫无益处、喧宾夺主、令人厌烦邮件」的代名词。就像当年经济萧条,人们买不起鲜肉,而吃的SPAM 肉罐头一样,没有营养成分。)

上面我们得出了一个词对整篇文章的分类判断情况,接下来我们可以进一步扩展这个问题,通过再增加以下为已知前提:

  • 25封邮件包含“money”一词,而其中24封被认为是垃圾邮件。

那么现在当收到一封同时包含“sex”,“money”这两个词的邮件,它为垃圾邮件的可能性又有多大呢?

写到这里我们发现,当我们不断增加相关词进行判定时,上述的贝叶斯推理公式也将越来越复杂。这时,就要开始应用朴素思想了,我们假设“sex”和“money”两者出现的事件都相互独立(虽然现实情况往往并不是这样的,当出现一些广告相关的词词语时,“金钱”一词往往就有很大的几率出现在后文,但这里采用朴素的思想来近似在分类上也足够准确了),这样我们就可以把上面的公式简化成:

这样,假如我们需要对一封收到的电子邮件进行分类的话,我们只要计算出在给出邮件内的词汇的情况下,它为一封垃圾邮件的条件概率即可。当然,这里存在的一个较大的缺陷就是,当一些词语极度相关时,而我们通过假设他们相互独立计算出来的概率可能并不是那么准确。

分类实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
# -*- encoding : utf-8 -*-
class BeyesClassifier::Base
  extend BeyesClassifier::Storage::ActAsStorable
  attr_reader :name
  attr_reader :word_list
  attr_reader :category_list
  attr_reader :training_count

  attr_accessor :tokenizer
  attr_accessor :language

  attr_accessor :thresholds
  attr_accessor :min_prob


  storable :version,:word_list,:category_list,:training_count,:thresholds,:min_prob

  # opts :
  # language
  # stemming : true | false
  # weight
  # assumed_prob
  # storage
  # purge_state ?

  def initialize(name, opts={})
    @version = BeyesClassifier::VERSION

    @name = name

    # This values are nil or are loaded from storage
    @word_list = {}
    @category_list = {}
    @training_count=0

    # storage
    purge_state = opts[:purge_state]
    @storage = opts[:storage] || BeyesClassifier::Base.storage
    unless purge_state
      @storage.load_state(self)
    else
      @storage.purge_state(self)
    end

    # This value can be set during initialization or overrided after load_state
    @thresholds = opts[:thresholds] || {}
    @min_prob = opts[:min_prob] || 0.0


    @ignore_words = nil
    @tokenizer = BeyesClassifier::Tokenizer.new(opts)

  end

  def incr_word(word, category)
    @word_list[word] ||= {}

    @word_list[word][:categories] ||= {}
    @word_list[word][:categories][category] ||= 0
    @word_list[word][:categories][category] += 1

    @word_list[word][:_total_word] ||= 0
    @word_list[word][:_total_word] += 1


    # words count by categroy
    @category_list[category] ||= {}
    @category_list[category][:_total_word] ||= 0
    @category_list[category][:_total_word] += 1

  end

  def incr_cat(category)
    @category_list[category] ||= {}
    @category_list[category][:_count] ||= 0
    @category_list[category][:_count] += 1

    @training_count ||= 0
    @training_count += 1

  end

  # return number of times the word appears in a category
  def word_count(word, category)
    return 0.0 unless @word_list[word] && @word_list[word][:categories] && @word_list[word][:categories][category]
    @word_list[word][:categories][category].to_f
  end

  # return the number of times the word appears in all categories
  def total_word_count(word)
    return 0.0 unless @word_list[word] && @word_list[word][:_total_word]
    @word_list[word][:_total_word].to_f
  end

  # return the number of words in a categories
  def total_word_count_in_cat(cat)
    return 0.0 unless @category_list[cat] && @category_list[cat][:_total_word]
    @category_list[cat][:_total_word].to_f
  end

  # return the number of training item
  def total_cat_count
    @training_count
  end

  # return the number of training document for a category
  def cat_count(category)
    @category_list[category][:_count] ? @category_list[category][:_count].to_f : 0.0
  end

  # return the number of time categories in wich a word appear
  def categories_with_word_count(word)
    return 0 unless @word_list[word] && @word_list[word][:categories]
    @word_list[word][:categories].length
  end

  # return the number of categories
  def total_categories
    categories.length
  end

  # return categories list
  def categories
    @category_list.keys
  end

  # train the classifier
  def train(category, text)
    @tokenizer.each_word(text) {|w| incr_word(w, category) }
    incr_cat(category)
  end

  # classify a text
  def classify(text, default=nil)
    # Find the category with the highest probability
    max_prob = @min_prob
    best = nil

    scores = cat_scores(text)
    scores.each do |score|
      cat, prob = score
      if prob > max_prob
        max_prob = prob
        best = cat
      end
    end

    # Return the default category in case the threshold condition was
    # not met. For example, if the threshold for :spam is 1.2
    #
    #    :spam => 0.73, :ham => 0.40  (OK)
    #    :spam => 0.80, :ham => 0.70  (Fail, :ham is too close)

    return default unless best

    threshold = @thresholds[best] || 1.0

    scores.each do |score|
      cat, prob = score
      next if cat == best
      return default if prob * threshold > max_prob
    end

    return best
  end

  def save_state
    @storage.save_state(self)
  end

  class << self
    attr_writer :storage

    def storage
      @storage = BeyesClassifier::InMemoryStorage.new unless defined? @storage
      @storage
    end

    def open(name)
      inst = self.new(name)
      if block_given?
        yield inst
        inst.save_state
      else
        inst
      end
    end
  end
end

完整代码实现可以参考alexandru大神的github项目stuff-classifier

算法训练和使用

1
2
3
4
5
6
7
8
9
# 训练函数
def train(category, text)
  each_word(text) {|w| increment_word(w, category) }
  increment_cat(category)
end

# 使用
classifier.train :spam, "Grow your penis to 20 inches in just 1 week"
classifier.train :ham,  "I'm hungry, no I don't want your penis"

由于本文主要的目标是讲解贝叶斯算法,所以为了方便分词,主要使用英文语料训练,对于中文邮件分类而言,只要采用分词库分词即可,其他部分不变。

提高准确度与算法优化

计算优化

由于浮点数计算的一些先天性问题,如计算效率慢,精度不准确等。因此我们可以用自然对数来代替原本概率的形式。

拉普拉斯平滑

由于贝叶斯公式依赖的都是用已知概率求未知概率,但是在分类中无法避免的一个情况就是当我们计算即:在已有的训练的垃圾邮件样本中出现的概率是多少时,我们遇到了一个从未在训练样本中出现过的词,那么此时就会导致。这样就会影响整体的判别。

这样由于训练样本不足导致分类器整体质量大大下降的问题很常见,为了解决这个问题,我们可以引入Laplace校准(即我们要讲的拉普拉斯平滑公式),它的原理非常简单,给未出现特征值,赋予一个“小”的值而不是0。

具体平滑方法如下:
假设离散型随机变量z有{1,2,…,k}个值,我们用来表示每个值的概率。假设有m个训练样本中,z的观察值是其中每一个观察值对应k个值中的一个。那么根据原来的估计方法可以得到

简单来说就是出现的比例。

拉普拉斯平滑法将每个k值出现次数事先都加1,即假设他们都出现过一次。
那么修改后的表达式为:

每个z=j的分子都加1,分母加k。可见

这样在保持总体事件发现概率比例基本不变的同时,又避免了0概率的问题。

去除停用词

停用词是指在信息检索中,为节省存储空间和提高搜索效率,在处理自然语言数据(或文本)之前或之后会自动过滤掉某些字或词,这些字或词即被称为Stop Words(停用词)。这些停用词都是人工输入、非自动化生成的,生成后的停用词会形成一个停用词表。但是,并没有一个明确的停用词表能够适用于所有的工具。

通常意义上,Stop Words大致为如下两类:

  1. 第一类是那些应用十分广泛的词,在Internet上随处可见,比如“Web”一词几乎在每个网站上均会出现,对这样的词搜索引擎无 法保证能够给出真正相关的搜索结果,难以帮助缩小搜索范围,同时还会降低搜索的效率。
  2. 第二类就更多了,包括了语气助词、副词、介词、连接词等,通常自身并无明确的意义,只有将其放入一个完整的句子中才有一定作用,如常见的“的”、“在”之类。

为了使得最后用于判别邮件类型的词向量能够更加贴近邮件本身真正想表达的含义,我们可以在读取扫描文本并生成词列表时,先剔除停用词,再进行下一步的概率计算。

常用中文停用词表:
链接: https://pan.baidu.com/s/1o8hw5Cm 密码: crti

常用英文停用词表:
链接: https://pan.baidu.com/s/1jIOOfgM 密码: 7g95

阈值选取

假设我们计算出一封邮件的那么是否我们因为 就可以把它定义为垃圾邮件呢?显然这样做是不合理的,一个好的概率阈值应该是在训练及测试样本上使得发生误判情况最少时所取得的值。通常我们可以定义一个误差评判函数再通过不同阈值在样本上的评分来选取出最佳的阈值。简单实现就如下面的代码所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def classify(text, default=nil)
  # Find the category with the highest probability

  max_prob = 0.0
  best = nil

  scores = cat_scores(text)
  scores.each do |score|
    cat, prob = score
    if prob > max_prob
      max_prob = prob
      best = cat
    end
  end

  # Return the default category in case the threshold condition was
  # not met. For example, if the threshold for :spam is 1.2
  #
  #    :spam => 0.73, :ham => 0.40  (OK)
  #    :spam => 0.80, :ham => 0.70  (Fail, :ham is too close)

  return default unless best
  threshold = @thresholds[best] || 1.0

  scores.each do |score|
    cat, prob = score
    next if cat == best
    return default if prob * threshold > max_prob
  end
  return best
end

最后,写到这里,贝叶斯分类器构建的讲解基本就结束了。通观全篇,我们依旧有个问题并没有解决:朴素贝叶斯分类有一个限制条件,就是特征属性必须有条件独立或基本独立(实际上在现实应用中几乎不可能做到完全独立)。当这个条件成立时,朴素贝叶斯分类法的准确率是最高的,但不幸的是,现实中各个特征属性间往往并不条件独立,而是具有较强的相关性,这样就限制了朴素贝叶斯分类的能力。然而,这个问题也并不是无解的,贝叶斯分类中有一种更高级、应用范围更广的一种算法——贝叶斯网络(又称贝叶斯信念网络或信念网络),信念网络在一定程度上使得模型更接近真实的实际情况,有兴趣的读者可以进一步深入了解。