机器学习实战笔记 – 朴素贝叶斯(Naive Bayesian)

Intro

朴素贝叶斯算法通过输入向量在已经在样本中且属于某一个分类的条件概率来进行分类即:

$$ p(c_{i}|x, y)$$

本算法通过选取最大的概率\(p\)来确定输入所属的分类。

在本节中,我们将以一个垃圾邮件过滤器为例,通过朴素贝叶斯来对一封邮件是否属于垃圾邮件进行分类。而对于一封邮件是否属于垃圾邮件,我们通过计算条件概率:\(p(BAD|WORDS)\)与\(p(GOOD|WORDS)\)后比大小来进行判定。

为了计算\(p(BAD|WORDS)\),我们需要用到贝叶斯准则:

$$p(BAD|WORDS) = \frac{p(WORDS)p(BAD)}{p(WORDS)}$$

首先对训练集中的所有邮件构建词表,即构造一个\(n\)维向量,其中\(n\)为训练集中所有邮件出现过的单词的数量(重复不计)。

其中,\(p(BAD)\)为训练集所有邮件中垃圾邮件的出现概率,而\(p(WORDS)\)表示训练集中每一封邮件的词向量中每一个词在所有邮件的词向量出现的概率,需要注意的是\(p(WORDS)\)是一个向量。这里用到了条件独立性假设,即假设所有词出现的概率都相互独立,所以对于\(p(WORDS)\),可以通过计算\(p(WORD_i)\)得到。而对于\(p(WORDS|BAD)\),可以通过训练集中类别为垃圾邮件的词向量集合累加在除以总次数得到。

在本问题中,我们无需计算\(p(WORDs)\),因为对于垃圾邮件的是非,他们的\(p(WORD)\)是相同的。

最后我们通过输入向量与\(p(WORDS) × p(BAD/GOOD)\)相乘,然后比较大小,从而选择较大概率的分类作为结果。

朴素贝叶斯具有以下特点:

优点:数据较少时仍然有效,可以处理多类别问题。

缺点:对输入数据非常敏感。

适用数据类型:标称型。

Algorithm

  1. 数据预处理,建立独立特征表,将训练集数据处理为特征表长度维度的向量。
  2. 对于每个标签,分别求该标签的概率\(p^{C_i}\)与训练集中属于该标签的向量每个独立特征的概率\(p^{c_i}_i\)。
  3. 将输入与\(p^{c_i}_i\)和\(p^{C_i}\)相乘,选择较大的作为分类结果。

Code

def train(training_set, labels):

    training_set_size = len(training_set)

    vector_size = len(training_set[0])

    bad_probability = np.sum(labels) / float(len(labels))

    # For performance, we use ones(vector_size) to replace zeros(vector_size)

    vector_of_every_words_sum_bad = np.ones(vector_size)

    vector_of_every_words_sum_good = np.ones(vector_size)

    # For performance, we use 2.0 to replace 0.0

    word_vectors_sum_bad = 2.0

    word_vectors_sum_good = 2.0

    for index in range(training_set_size):

        if labels[index] == 1:
            
            vector_of_every_words_sum_bad += training_set[index]

            word_vectors_sum_bad += np.sum(training_set[index])

        if labels[index] == 0:

            vector_of_every_words_sum_good += training_set[index]

            word_vectors_sum_good += np.sum(training_set[index])

    # For accuracy, we use log to replace direct divide into ln(x)

    vector_of_every_word_and_bad_probability = np.log(vector_of_every_words_sum_bad / word_vectors_sum_bad)

    vector_of_every_word_and_good_probability = np.log(vector_of_every_words_sum_good / word_vectors_sum_good)

    return vector_of_every_word_and_bad_probability, vector_of_every_word_and_good_probability, bad_probability


def classify(vector, p0, p1, p):

    # For accuracy, we use ln(x) to raplace origin bad probability

    aye = np.sum(vector * p0) + np.log(p)

    nay = np.sum(vector * p1) + np.log(1 - p)

    return 1 if aye > nay else 0

Summary

以上是对朴素贝叶斯算法在机器学习实战中的总结,在下一节我们将介绍Logistic回归。

机器学习实战笔记 – 决策树(Decision Tree)

Intro

决策树的核心算法有多种实现,如在机器学习技法介绍的C&RT,以及未涉及的C4.5,以及本书中介绍的ID3。

对于ID3,我们首先定义某个符号或者分类\(x_i\)的信息如下:

$$l(x_i) = -\log_{2}{p(x_i)}$$

其中,\(p(x_i)\)为某符号或者分类在训练集\(D_{train}\)中在所有的符号或者分类中出现的频率,接着我们定义信息熵\(H\):

$$H = – \sum^{n}_{i=1} p(x_i) \log_{2}{p(x_i)}$$

可以看出,信息熵\(H\)其实是求所有符号或分类的期望。

在本节中,决策树的构建算法将选择一个特征及其取值对训练集进行分割,使用该特征及其取值分割训练集可以使得分割后的\(n\)子训练集集信息熵相对于原信息熵增益最大,然后再递归地对子训练集使用该算法,直到训练集特征归一,即无法继续分割。

决策树算法具有如下特点:

优点:计算复杂度低、图形化表示后具有树形结构易于理解、对数据缺失不敏感。

缺点:如果没有Regularization,会出现Overfitting。

适用数据类型:数值型、标称型。

Algorithm

  1. 数据预处理,本算法只支持标称型数据,需要将所有的数值型数据转化为标称型;
  2. 构建决策树根节点,计算原始信息熵,初次选择最佳分割特征,存储最佳分割特征索引;
  3. 根据最佳分割特征及其取值分割训练集,得到的子训练集将原最佳特征列移除;
  4. 对于每一个得到的子训练集重复步骤2到步骤4,直到没有特征可以分割;
  5. 返回决策树;

Code

由于函数与变量名严格按照Objective-C风格命名,表意清晰,故将注释略去。

def create_decision_tree(data_set, tags):

    labels = [vector[-1] for vector in data_set]

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

    if len(data_set[0]) == 1:
        return classify(labels)

    best_split_feature_index = get_index_of_best_split_feature(data_set)

    best_split_feature_tag = tags[best_split_feature_index]

    decision_tree = {best_split_feature_tag: {}}

    del(tags[best_split_feature_index])

    best_split_features = [vector[best_split_feature_index] for vector in data_set]

    best_split_features_set = set(best_split_features)

    for best_split_feature in best_split_features_set:

        sub_tags = tags[:]

        sub_data_set = split_data_set(data_set, best_split_feature_index, best_split_feature)

        sub_decision_tree = create_decision_tree(sub_data_set, sub_tags)

        decision_tree[best_split_feature_tag][best_split_feature] = sub_decision_tree

    return decision_tree

Summary

以上是对决策树算法在机器学习实战中的总结,在下一节我们将介绍朴素贝叶斯。

机器学习实战笔记 – k-近邻算法(K Nearest Neighbors)

Intro

k-近邻算法通过计算输入向量与训练集向量的距离来进行分类,在本书中我们使用欧式距离(Euclidean Distance):

$$d_{12} = \sqrt{(x_1 – x_2)^2 + (y_1 – y_2)^2 + (z_1 – z_2)^2}$$

本算法将输入向量与训练集中所有向量的欧氏距离从小到大排序,通过对比前k个训练集中的向量的标签,选择出现次数较多的标签,作为分类结果。

优点:精度高、鲁棒性好、只需要做简单的预处理。

缺点:时间、空间复杂度高。

适用数据类型:数值型、标称型。

在本节中,作者通过一部电影中出现打斗镜头和接吻镜头的的次数来判定一部电影是否是动作片还是爱情片。

Algorithm

  • 数据预处理,对于数值型问题,首先需要对输入向量与训练集进行归一化处理(Normalize),防止较大的数据对欧氏距离的结果造成干扰;
  • 计算输入向量与训练集中所有向量的欧氏距离;
  • 将计算结果从小到大排序;
  • 选取前k个样本集中的向量,统计每个向量所对应的标签在k个标签中出现的频率。
  • 返回出现频率最高的标签作为分类结果。

Code

def classify(x, training_set, training_labels, k):

    rows, columns = training_set.shape                              # 获取训练集矩阵的行、列数

    offset_matrix = tile(x, (rows, 1)) - training_set               # 将输入向量复制 rows 行,并与训练集矩阵相减

    square_offset_matrix = offset_matrix ** 2                       # 对结果矩阵中每一组行向量求平方

    offset_sum = square_offset_matrix.sum(axis=1) ** 0.5            # 求每一组行向量的和并开方

    sorted_index_of_offset_sum = offset_sum.argsort()               # 对欧氏距离数组的索引从小到大排序

    label_count = {}                                                # 创建标签字典,键为标签名,值为标签出现次数

    for i in range(k):
        label = training_labels[sorted_index_of_offset_sum[i]]      # 获得第k个索引对应的向量的标签
        label_count[label] = label_count.get(label, 0) + 1          # 将第k个索引对应的向量的标签出现次数+1并存储在标签字典

    sorted_class_count = sorted(label_count.iteritems(),            # 对标签字典的值(标签出现次数)逆序排序
                                key=operator.itemgetter(1),
                                reverse=True)

    return sorted_class_count[0][0]                                 # 输出出现次数最大的键值

Summary

以上是对k-近邻算法在机器学习实战中的总结,在下一节我们将介绍决策树。