用SVM算法构造垃圾邮件分类器

前言

在之前的学习中，已经学习过了支持向量机的算法，在这部分内容中，需要使用2维数据实现带有高斯核函数的支持向量机算法，并利用支持向量机算法实现垃圾邮件的分类，具体实现如下。

使用线性核函数的svm算法

数据集1的线性决策边界
首先，加载一个2维数据集，该数据集可以被线性边界分割为正样本和负样本，具体实现代码和效果如下所示：

import matplotlib.pyplot as plt
import numpy as np
import scipy.io as scio
from sklearn import svm
plt.ion()
np.set_printoptions(formatter={'float': '{: 0.6f}'.format})

data = scio.loadmat('ex6data1.mat')
X = data['X']
y = data['y'].flatten()
m = y.size

绘图函数实现代码如下所示，根据y值的不同，得到两种不同的散点图。

def plot_data(X, y):
    plt.figure()

    pos = np.where(y == 1)[0]
    neg = np.where(y == 0)[0]

    plt.scatter(X[pos, 0], X[pos, 1], marker="+", c='b')
    plt.scatter(X[neg, 0], X[neg, 1], marker="o", c='y', s=15)

实现效果如下所示

通过使用sklearnpython包中的svm模块，利用svm算法实现线性分类，由之前的学习可知，变量 $C$ 所起的作用于逻辑回归中的正则化参数 $\frac{1}{\lambda}$ 相似，不同的 $C$ 值对决策边界有不同的影响，具体如下所示：

def visualize_boundary(clf, X, x_min, x_max, y_min, y_max):
    h = 0.02
    xx, yy = np.meshgrid(np.arange(x_min, x_max, h), np.arange(y_min, y_max, h))

    Z = clf.predict(np.c_[xx.ravel(), yy.ravel()])
    Z = Z.reshape(xx.shape)
    plt.contour(xx, yy, Z, levels=[0], colors='r')

c = 1
clf = svm.SVC(c, kernel='linear', tol=1e-3)
clf.fit(X, y)

plot_data(X, y)
visualize_boundary(clf, X, 0, 4.5, 1.5, 5)

$C=1$ 时，决策边界如下所示：

C=1

$C=1000$ 时，所绘制的决策边界如下所示：

C=1000

可以由以上图片看出， $C$ 的大小影响着线性决策边界，其所起的作

用于逻辑回归中正则化参数一样， $C$ 太大，可能会导致过拟合问题。

使用高斯核函数的SVM算法

对于非线性的分类任务，常用带有高斯核函数的SVM算法来实现，具体如下所示：

高斯核函数
根据高斯核函数的原理，具体实现代码如下所示

def gaussian_kernel(x1, x2, sigma):
    x1 = x1.flatten()
    x2 = x2.flatten()
    sim = 0
    sim = np.exp(np.sum((x1 - x2) ** 2) / (-2*sigma**2))
    return sim

绘制非线性决策边界
如下代码所示，加载数据集2，并绘制其散点图，可以很明显地看出是非线性的数据

data = scio.loadmat('ex6data2.mat')
X = data['X']
y = data['y'].flatten()
m = y.size
plot_data(X, y)

如下代码所示，使用带有高斯核函数的svm算法绘制非线性的决策边界，如下所示：

c = 1
sigma = 0.1


def gaussian_kernel(x_1, x_2):
    n1 = x_1.shape[0]
    n2 = x_2.shape[0]
    result = np.zeros((n1, n2))

    for i in range(n1):
        for j in range(n2):
            result[i, j] = gk.gaussian_kernel(x_1[i], x_2[j], sigma)

    return result


clf = svm.SVC(c, kernel='rbf', gamma=np.power(sigma, -2))
clf.fit(X, y)
plot_data(X, y)
visualize_boundary(clf, X, 0, 1, .4, 1.0)

实现效果如下所示：

用SVM算法实现邮件分类

许多邮件服务商能够对垃圾邮件的识别具有很高的精确度，通过SVM算法，可以实现自己的邮件过滤器，具体实现，如下所示。
利用SVM算法，通过训练能够区分给定的邮件(变量 $x$ )，是垃圾邮件( $y=1$ )还是正常邮件( $y=0$ )。在这个过程中，需要将每份邮件转化为特征向量 $x \in R^n$ 。

邮件处理

一封邮件格式如下所示，需要对文本邮件做必要处理。

小写转化
需要将文本格式的邮件中的大写字母全部转化为小写，如下代码所示

email_contents = email_contents.lower()

过滤html标签
将文本格式中的HTML标签删除，用python实现如下所示：

email_contents = re.sub('<[^<>]+>', ' ', email_contents)

URL处理
需要将所有URL标签转化为字符串httpaddr，如下代码所示：

email_contents = re.sub('(http|https)://[^\s]*', 'httpaddr', email_contents)

email地址处理
所有的email地址将会被字符串emailaddr替换，如下所示：

 email_contents = re.sub('[^\s]+@[^\s]+', 'emailaddr', email_contents)

数字处理
所有的数字将会被替换为字符串number，如下所示：

email_contents = re.sub('[^\s]+@[^\s]+', 'emailaddr', email_contents)

$的处理
所有的$符将会被替换为字符串dollar,如下所示

email_contents = re.sub('[$]+', 'dollar', email_contents)

经过以上步骤处理之后的邮件格式如下图所示

词汇表

经过以上处理，得到词汇列表，接下来要做的就是将筛选出来哪些词汇可以用来构建邮件分类器。
为了构建一个合适的邮件分类器，需要选择一些使用频率最高的词汇，（如果选择一些使用频率很小的词汇，可能会导致过拟合问题）。根据在垃圾邮件语料库中至少出现了100次以上的单词可以添加到词汇表中的要求，最终，词汇表中有1899个单词。在实践中，一个词汇表中通常有10000到50000个单词。
有了词汇表，可以将预处理的电子邮件中的每个单词映射到包含词汇表中单词的索引的单词索引列表。所谓单词索引列表就是每个单词所对应的数字索引所组成的列表，具体如下图所示：

邮件的文本经过处理，可以得到以下的数字索引，如下所示：

以上过程用python实现如下所示

def process_email(email_contents):
    vocab_list = get_vocab_list()

    word_indices = np.array([], dtype=np.int64)
    email_contents = email_contents.lower()
    email_contents = re.sub('<[^<>]+>', ' ', email_contents)
    email_contents = re.sub('[0-9]+', 'number', email_contents)
    email_contents = re.sub('(http|https)://[^\s]*', 'httpaddr', email_contents)
    email_contents = re.sub('[^\s]+@[^\s]+', 'emailaddr', email_contents)
    email_contents = re.sub('[$]+', 'dollar', email_contents)
    print('==== Processed Email ====')
    stemmer = nltk.stem.porter.PorterStemmer()
    tokens = re.split('[@$/#.-:&*+=\[\]?!(){\},\'\">_<;% ]', email_contents)
    for token in tokens:
        token = re.sub('[^a-zA-Z0-9]', '', token)
        token = stemmer.stem(token)
        if len(token) < 1:
            continue

        for i in range(1, len(vocab_list) + 1):
            if vocab_list[i] == token:
                word_indices = np.append(word_indices, i)

        print(token)

    print('==================')

    return word_indices


def get_vocab_list():
    vocab_dict = {}
    with open('vocab.txt') as f:
        for line in f:
            (val, key) = line.split()

            vocab_dict[int(val)] = key

    return vocab_dict

plt.ion()
np.set_printoptions(formatter={'float': '{: 0.6f}'.format})
print('Preprocessing sample email (emailSample1.txt) ...')
file_contents = open('emailSample1.txt', 'r').read()
word_indices = process_email(file_contents)

提取邮件中的特征

有了以上过程，需要从文本邮件中得到特征向量 $x$ ，具体实现思路是：如果词汇表中第 $i$ 个单词出现在邮件中，则用 $x_i=1$ 表示，否则用 $x_i =0$ 表示。最后，可以得到一个 $x$ 的 $n$ 维向量，如下所示：

具体实现代码如下所示：

def email_features(word_indices):
    n = 1899
    features = np.zeros(n + 1)
    features[word_indices - 1] = 1
    return features

为垃圾邮件分类训练SVM算法

完成了邮件特征变量的提取之后，可以利用4000个训练样本和1000个测试样本训练SVM算法，每个原始的邮件将会被转化为一个 $x \in R^{1900}$ 的向量（词汇表中有1899个词汇， $x_0=1$ 会被添加到向量中，最后，得到的向量包含1900个数字）。载入数据集之后，用变量 $y=1$ 表示垃圾邮件，而 $y=0$ 表示非垃圾邮件可就可以训练SVM算法了。具体实现代码如下所示：

data = scio.loadmat('spamTrain.mat')
X = data['X']
y = data['y'].flatten()

print('Training Linear SVM (Spam Classification)')
print('(this may take 1 to 2 minutes)')

c = 0.1
clf = svm.SVC(c, kernel='linear')
clf.fit(X, y)

p = clf.predict(X)
print('Training Accuracy: {}'.format(np.mean(p == y) * 100))

通过以上代码，运行后，得到的精确度如下所示：

最后，载入测试集数据，利用SVM算法构造的分类器，得到其训练精度如下所示：