OneR 算法实现分类

不可言诉的深渊

发布于 2019-07-26 17:35:34

1.3K0

发布于 2019-07-26 17:35:34

文章被收录于专栏：Python机器学习算法说书人 Python机器学习算法说书人Python机器学习算法说书人

分类是数据挖掘中最常用的方法之一，不论是实际应用还是科研，都少不了它的身影。对于分类问题我们通常能拿到表示实际对象或事件的数据集，我们知道数据集中每一条数据所属的类别，这些类别把一条条数据划分为不同的类。什么是类别？类别的值又是怎么回事？我们来看下面几个例子。

根据检测数据确定植物的种类。类别的值为“植物属于哪个种类？”。
判断图像中有没有狗。类别是“图像里有狗吗？”。
根据化验结果，判断病人有没有患上癌症。类别是“病人得癌症了吗？”。

上述三个问题有两个是二值（是/否）问题，但正如第一个确定植物类别的问题，多个类别的情况也很常见。

分类应用的目标是，根据已知类别的数据集，经过训练得到一个分类模型，再用模型对未知的数据进行分类。例如，我们可以对收到的邮件进行分类，标注哪些是希望自己收到的，哪些是垃圾邮件，然后用这些数据训练分类模型，实现一个垃圾邮件过滤器，这样以后再收到邮件，就不用自己去确认它是不是垃圾邮件了，过滤器就能帮你搞定。

准备数据集

我们接下来将使用著名的 Iris 植物分类数据集。这个数据集共有150条植物数据，每条数据都给出了四个特征：sepal length、sepal width、petal length、petal width（分别表述萼片和花瓣的长与宽），单位均为 cm。这是数据挖掘的经典数据集之一（1936 年就用到了数据挖掘领域！）。该数据集共有三种类别：Iris Setosa（山鸢尾）、Iris Versicolour（变色鸢尾）、Iris Virginica（维吉尼亚鸢尾）。我们这里的分类目的是根据植物的特征推测它的种类。

scikit-learn 库内置了该数据集，可直接导入。

from sklearn.datasets import load_iris
dataset = load_iris()
X = dataset.data
y = dataset.target

用 print(dataset.DESCR)查看数据集，大概了解一下，包括特征的说明。

数据集中各特征值为连续型，也就是有无数个可能的值。测量得到的数据就是这个样子，比如，测试结果可能是 1、1.2、1.25，等等。连续值的另一个特点是，如果两个值相近，表示相似度很大。一种萼片长 1.2 cm 的植物一种萼片长 1.25 cm 的植物很相像。

与此相反，类别的类型为离散型。虽然常用数字表示类别，但是类别值不能从数值大小比较相似性。Iris 数据集用不同的数字表示不同的类别，比如类别 0、1、2 分别表示 Iris Setosa、Iris Versicolour、Iris Virginica。但是这不能说明前两种事物，要比第一种和第三种更接近——尽管单看表示类别的数字时确实如此。在这里，数字表示类别，只能用来判断两种植物是否属于是否属于同一种类别，而不能说明是否相似。

数据集的特征为连续值，而我们即将使用的算法使用类别型特征值，因此我们需要把连续值转换为类别型，这个过程叫做离散化。

最简单的离散化算法，莫过于确定一个阈值，将低于该阈值的特征置位 0，高于阈值的置为 1。我们把某项特征的阈值设定为该特征所有特征值的均值。每个特征均值的计算方法如下。

attribute_means = X.mean(axis=0)

我们得到了一个长度为 4 的数组，这正好是特征的数量。数组的第一项是第一个特征的均值，以此类推。接下来，用该方法将数据集打散，把连续的特征值转换为类别型。

X_d = np.array(X >= attribute_means, dtype='int')

后面的训练和测试，都将使用新得到的 X_d 数据集（打散后的数组 X），而不再使用原来的数据集（X）。

实现 OneR 算法

OneR 算法的思路很简单，它根据已有的数据中，具有相同特征值的个体最可能属于哪个类别进行分类。OneR 是 One Rule（一条规则）的简写，表示我们只选取四个特征中分类效果最好的一个用作分类依据。

算法首先遍历每个特征的每一个取值，对于每一个特征值，统计它在各类别中的出现次数，找出它出现次数最多的类别，并统计它在其他类别中的出现次数。

举例来说，加入数据集的某一个特征可以取 0 或 1 两个值。数据集共有三个类别。特征值为 0 的情况下，A 类有 20 个这样的个体，B 类有 60 个，C 类也有 20 个。那么，特征值为 0 的个体最可能属于 B 类，当然还有 40 个个体确实是特征值为 0，但是它们不属于 B 类。将特征值为 0 的个体分到 B类的错误率就是 40%。因为有 40 个这样的个体分别属于 A 类和 C 类。特征值为 1 时，计算方法类似，不再赘述；其他各特征值最可能属于的类别及错误率的计算方法也一样。

统计完所有的特征值及其在每个类别的出现次数后，我们再来计算每个特征的错误率。计算方法把它的各个取值的错误率相加，选取错误率最低的特征作为唯一的分类准则（OneR），用于接下来的分类。

现在，我们就来实现该算法。首先创建一个函数，根据待预测数据的某项特征值预测类别，并给出错误率。在这之前需要导入 defaultdict 和 itemgetter 类。

from collections import defaultdict
from operator import itemgetter

下面创建函数，参数分别是数据集、类别数组、选好的特征索引值、特征值。

def train_feature_value(x, y_true, feature_index0, value):
    # 接下来遍历数据集中每一条数据（代表一个个体），统计具有给定特征值的个体在各个类别中出现的次数。
    class_counts = defaultdict(int)
    for sample, y0 in zip(x, y_true):
        if sample[feature_index0] == value:
            class_counts[y0] += 1
    # 对 class_counts 字典进行排序，找到最大值，就能找出具有给定特征值的个体在哪个类别中出现次数最多。
    sorted_class_counts = sorted(class_counts.items(), key=itemgetter(1), reverse=True)
    most_frequent_class = sorted_class_counts[0][0]
    # 接着计算该规则的错误率。OneR 算法会把具有该项特征值的个体统统分到上面找到的出现次数最多的类别中。错误率为具有该特征的个体
    # 在其他类别（除出现次数最多的类别之外的）中的出现次数，它表示的是分类规则不适用的个体的数量。
    incorrect_predictions = [
        class_count for class_value, class_count in class_counts.items()if class_value != most_frequent_class]
    error = sum(incorrect_predictions)
    # 最后返回使用给定特征值得到的待预测个体的类别和错误率。
    return most_frequent_class, error

对于某项特征，遍历其每一个特征值，使用上述函数，就能得到预测结果和每个特征值所带来的错误率，然后把所有的错误率累加起来，就能得到该特征的总错误率。我们来定义一个函数，实现这些操作。

函数如下，这次只用到三个参数，上面已经介绍过。

def train_on_feature(x, y_true, feature_index0):
    # 接下来找出给定特征共有几种不同的取值。下面这行代码 x[:, feature_index0]以数组的形式返回由 feature_index0 所指的列。然后
    # 用 set 函数将数组转化为集合，从而找出有几种不同的取值。
    values = set(x[:, feature_index0])
    # 再创建字典 predictors0，用作预测器。字典的键为特征值，值为类别。比如键为 1.5、值为 2，表示特征值为 1.5 的个体属于类别
    # 2。创建 errors0 列表，存储每个特征值的错误率。
    predictors0 = {}
    errors0 = []
    # 函数的主干部分遍历选定特征的每个不同的特征值，用前面定义的 train_feature_value()函数找出每个特征值最可能的类别，计算错误
    # 率，并将其保存到预测器 predictors0 和 errors0 中。
    for current_value in values:
        most_frequent_class, error = train_feature_value(x, y_true, feature_index0, current_value)
        predictors0[current_value] = most_frequent_class
        errors0.append(error)
    # 最后，计算该规则的总错误率，返回预测器及总错误率。
    total_error0 = sum(errors0)
    return predictors0, total_error0

测试算法

分类问题的目标是建立一个能够根据已有知识对没有见过的个体进行分类的模型。

我们因此把机器学习流程分为两步：训练和测试。在训练阶段，我们从数据集中取一部分数据，创建模型。在测试阶段，我们测试模型在数据集上的分类效果。考虑到模型的目标是对新个体进行分类，因此不能用测试数据训练模型，因为这样做容易导致过拟合问题。

过拟合指的是模型在训练集上表现很好，但对于没有见过的数据表现很差。解决方法很简单：千万不要用训练数据测试算法。详细的处理方法很复杂；我们这里简单化处理，把数据集分为两个小部分，分别用于训练和测试。具体流程接下来会介绍。

scikit-learn 库提供了一个将数据集切分为训练集和测试集的函数。

from sklearn.model_selection import train_test_split

该函数根据设定的比例（默认把数据集的 25%作为测试集）将数据及随机切分为两部分，以确保测试结果的可信度。

X_train, X_test, y_train, y_test = train_test_split(X_d, y, random_state=14)

这样我们就得到了两个数据集：训练集 X_train 和测试集 X_test。y_train 和 y_test 分别为以上两个数据集的类别信息。

切分函数的第三个参数 random_state 用来指定切分的随机状态。每次切分，使用相同的随机状态，切分结果相同。虽然看起来是随机的，但是它所使用的算法是确定的，输出结果也是一致的。把 random_state 的值设置为 None，每次切分结果将是真正随机的。

接下来，计算所有特征值的目标类别（预测器）。记得只是用训练集。遍历数据集中的每个特征，使用我们先前定义的函数 train_on_feature()训练预测器，计算错误率。

all_predictors = {}
errors = {}
for feature_index in range(X_train.shape[1]):
    predictors, total_error = train_on_feature(X_train, y_train, feature_index)
    all_predictors[feature_index] = predictors
    errors[feature_index] = total_error

然后找出错误率最低的特征，作为分类的唯一规则。

best_variable, best_error = sorted(errors.items(), key=itemgetter(1))[0]

对预测器进行排序，找到最佳特征值，创建 model 模型。

model = {'variable': best_variable, 'predictor': all_predictors[best_variable]}

model 模型是一个字典结构，包含两个元素：用于分类的特征和预测器。有了模型后就可以根据特征值对没有见过的数据进行分类。

我们经常需要一次对多条数据进行预测，为此实现了下面这个函数，通过遍历数据集中的每条数据来完成预测。

def predict(x_test, model0):
    variable = model0['variable']
    predictor = model0['predictor']
    y_predicted0 = np.array([predictor[int(sample[variable])]for sample in x_test])
    return y_predicted0

我们用上面这个函数预测测试集中每条数据的类别。

y_predicted = predict(X_test, model)

比较预测结果和实际类别，就能得到正确率是多少。

accuracy = np.mean(y_predicted == y_test)*100
print("The test accuracy is {:.1f}%".format(accuracy))

最后给出整个程序的完整源代码和运行结果。

from sklearn.datasets import load_iris
import numpy as np
from collections import defaultdict
from operator import itemgetter
from sklearn.model_selection import train_test_split
dataset = load_iris()
X = dataset.data
y = dataset.target
attribute_means = X.mean(axis=0)
X_d = np.array(X >= attribute_means, dtype='int')


def train_feature_value(x, y_true, feature_index0, value):
    # 接下来遍历数据集中每一条数据（代表一个个体），统计具有给定特征值的个体在各个类别中出现的次数。
    class_counts = defaultdict(int)
    for sample, y0 in zip(x, y_true):
        if sample[feature_index0] == value:
            class_counts[y0] += 1
    # 对 class_counts 字典进行排序，找到最大值，就能找出具有给定特征值的个体在哪个类别中出现次数最多。
    sorted_class_counts = sorted(class_counts.items(), key=itemgetter(1), reverse=True)
    most_frequent_class = sorted_class_counts[0][0]
    # 接着计算该规则的错误率。OneR 算法会把具有该项特征值的个体统统分到上面找到的出现次数最多的类别中。错误率为具有该特征的个体
    # 在其他类别（除出现次数最多的类别之外的）中的出现次数，它表示的是分类规则不适用的个体的数量。
    incorrect_predictions = [
        class_count for class_value, class_count in class_counts.items()if class_value != most_frequent_class]
    error = sum(incorrect_predictions)
    # 最后返回使用给定特征值得到的待预测个体的类别和错误率。
    return most_frequent_class, error


def train_on_feature(x, y_true, feature_index0):
    # 接下来找出给定特征共有几种不同的取值。下面这行代码 x[:, feature_index0]以数组的形式返回由 feature_index0 所指的列。然后
    # 用 set 函数将数组转化为集合，从而找出有几种不同的取值。
    values = set(x[:, feature_index0])
    # 再创建字典 predictors0，用作预测器。字典的键为特征值，值为类别。比如键为 1.5、值为 2，表示特征值为 1.5 的个体属于类别
    # 2。创建 errors0 列表，存储每个特征值的错误率。
    predictors0 = {}
    errors0 = []
    # 函数的主干部分遍历选定特征的每个不同的特征值，用前面定义的 train_feature_value()函数找出每个特征值最可能的类别，计算错误
    # 率，并将其保存到预测器 predictors0 和 errors0 中。
    for current_value in values:
        most_frequent_class, error = train_feature_value(x, y_true, feature_index0, current_value)
        predictors0[current_value] = most_frequent_class
        errors0.append(error)
    # 最后，计算该规则的总错误率，返回预测器及总错误率。
    total_error0 = sum(errors0)
    return predictors0, total_error0


X_train, X_test, y_train, y_test = train_test_split(X_d, y, random_state=14)
all_predictors = {}
errors = {}
for feature_index in range(X_train.shape[1]):
    predictors, total_error = train_on_feature(X_train, y_train, feature_index)
    all_predictors[feature_index] = predictors
    errors[feature_index] = total_error
best_variable, best_error = sorted(errors.items(), key=itemgetter(1))[0]
model = {'variable': best_variable, 'predictor': all_predictors[best_variable]}


def predict(x_test, model0):
    variable = model0['variable']
    predictor = model0['predictor']
    y_predicted0 = np.array([predictor[int(sample[variable])]for sample in x_test])
    return y_predicted0


y_predicted = predict(X_test, model)
accuracy = np.mean(y_predicted == y_test)*100
print("The test accuracy is {:.1f}%".format(accuracy))