现在好像什么研究方向都会用到机器学习,所以在大四养老期间学习一下周志华老师的《机器学习》,把不太难的题目写一下。

第1章 绪论

  • 1.1 表 1.1 中若只包含编号为 1 和 4 的两个样例,试给出相应的版本空间。

由于训练数据更少,所以版本空间会更大。

(色泽=青绿;根蒂=*;敲声=*)
(色泽=*;根蒂=蜷缩;敲声=*)
(色泽=*;根蒂=*;敲声=浊响)
(色泽=青绿;根蒂=蜷缩;敲声=*)
(色泽=青绿;根蒂=*;敲声=浊响)
(色泽=*;根蒂=蜷缩;敲声=浊响)
(色泽=青绿;根蒂=蜷缩;敲声=浊响)

第2章 模型评估与选择

  • 2.1 数据集包含1000个样本,其中500个正例、500个反例,将其划分为包含70%样本的训练集和30%样本的测试集用于留出法评估,试估算共有多少种划分方式。

如果采用分层采样,那么训练集和测试集中的正反样本数目比例需要一致,因此总划分方式为:

  • 2.2 数据集包含100个样本,其中正、反例各一半,假定学习算法所产生的模型是将新样本预测为训练样本数较多的类别(训练样本数相同时进行随机猜测),试给出用10折交叉验证法和留一法分别对错误率进行评估所得的结果。

10折交叉验证法:50%

采用分层采样,每次我们可以得到包含5个正样本和5个负样本的测试集,以及包含45个正样本和45个负样本,无论如何,总是可以保证测试集中一般的预测结果正确,就有错误率50%。

留一法:100%

留一法每次取出一个样本作为测试所用,其余作为训练集。假设取出一个正样例,那么训练集中就剩下了49个样本和50个负样本,按照规则,测试样本将被预测为负样本,预测显然是错误的。因此留一法每次对于测试样本的预测结果都是错误的,就有的错误率100%。

第3章 线性模型

  • 3.2 试证明,对于参数w,对率回归的目标函数(3.18)是非凸的,但其对数似然函数(3.27)是凸的。

(3.18)和(3.27)都是二阶可导,因此可以通过二阶导数来判断函数的凹凸性质。

时,,函数是凸的;当时,,函数是凹的。

因此,对数似然函数(3.27)是凸的。

  • 3.3 编程实现对率回归,并给出西瓜数据集3.0a上的结果。

考虑将b合并入w,对数几率回归模型为:

那么模型的最小化目标函数为:

使用梯度下降法进行学习,目标函数的梯度(向量导数)为:

import pandas as pd
import numpy as np
import math


# Logistic regression model
class LogisticRegression:
    d = 0
    w = np.array([])

    def fit(self, X, y, max_rate=100, min_rate=0.001, gd_step=10, epsilon=0.01):
        assert len(X) > 0
        self.d = len(X[0])
        self.w = np.zeros(self.d + 1)
        # Data preprocessor
        n = len(X)
        X = np.transpose(X)
        X = np.append(X, np.ones(n))
        X = np.reshape(X, [self.d+1, -1])
        X = np.transpose(X)
        # Gradient descent
        prev_cost = 0
        next_cost = self.__cost__(X, y, self.w)
        while math.fabs(prev_cost-next_cost) > epsilon:
            neg_grad = -self.__gradient__(X, y, self.w)
            best_rate = rate = max_rate
            min_cost = self.__cost__(X, y, self.w)
            while rate >= min_rate:
                cost = self.__cost__(X, y, self.w+neg_grad*rate)
                if cost < min_cost:
                    min_cost = cost
                    best_rate = rate
                rate /= gd_step
            self.w += neg_grad * best_rate
            prev_cost = next_cost
            next_cost = min_cost

    def predict(self, X):
        X = np.vstack([X.T, np.ones([len(X)])]).T
        return self.__predict__(X, self.w)

    @staticmethod
    def __predict__(x, w):
        return 1.0-1.0/(1.0+np.exp(np.matmul(x, w)))

    @staticmethod
    def __cost__(X, y, w):
        return np.sum(-np.matmul(X, w)*y + np.log(np.exp(np.matmul(X, w)) + 1))

    @classmethod
    def __gradient__(cls, X, y, w):
        return -np.sum(np.transpose(X)*np.transpose(y-cls.__predict__(X, w)), axis=1)

# Read data
data = pd.read_csv('data3.0.csv')
y = (np.array(data['好瓜']) == '是') * 1
X = np.array(data['密度'])
X = np.append(X, data['含糖率'])
X = np.reshape(X, [2, -1])
X = np.transpose(X)

# Training
model = LogisticRegression(dimen=2)
model.fit(X, y)

# Test
acc = 0
for i in range(0, len(X)):
    acc += (model.predict(X[i])>0.5) == y[i]
acc /= len(X)

# Report
print("w", model.w)
print("acc=", acc)

训练结果为:

w = [ 1.89698611  5.9308658  -2.3427455 ]
acc = 0.647058823529
  • 3.4 选择两个UCI数据集比较10折交叉验证法和留一法所估计出的对率回归的错误率。
import numpy as np
from sklearn import datasets, model_selection
from multi_classifier import MultiClassifier

UCI数据集中通常都是多分类问题,所以需要首先实现一下OvA算法:

class MultiClassifier:
    models = []
    tags = []

    def fit(self, X, y, max_rate=100., min_rate=0.001):
        self.tags = np.unique(y)
        self.models.clear()
        for tag in self.tags:
            model = LogisticRegression()
            model.fit(X, y == tag, max_rate=max_rate, min_rate=min_rate)
            self.models.append(model)

    def predict(self, X):
        return self.tags[np.argmax(np.asarray([w.predict(X) for w in self.models]), axis=0)]

scikit learn中包含了K折交叉验证和留一法的实现,所以直接使用。

def ten_fold(X, y, max_rate=100., min_rate=.001):
    total = 0
    hit = 0
    kf = model_selection.KFold(10, True)
    for train_index, test_index in kf.split(X, y):
        X_train, X_test = X[train_index], X[test_index]
        y_train, y_test = y[train_index], y[test_index]
        model = MultiClassifier()
        model.fit(X_train, y_train, max_rate=max_rate, min_rate=min_rate)
        hit += np.sum(model.predict(X_test) == y_test)
        total += len(y_test)
    return hit / total

def leave_one_out(X, y, max_rate=100., min_rate=.001):
    total = 0
    hit = 0
    loo = model_selection.LeaveOneOut()
    for train_index, test_index in loo.split(X, y):
        X_train, X_test = X[train_index], X[test_index]
        y_train, y_test = y[train_index], y[test_index]
        model = MultiClassifier()
        model.fit(X_train, y_train, max_rate=max_rate, min_rate=min_rate)
        hit += np.sum(model.predict(X_test) == y_test)
        total += len(y_test)
    return hit / total

Iris Data Set

iris = datasets.load_iris()
iris_data = iris.data
iris_target = iris.target
print('10折交叉验证法正确率:\t', ten_fold(iris_data, iris_target, max_rate=.001, min_rate=.00001))
print('留一法正确率:\t\t', leave_one_out(iris_data, iris_target, max_rate=.001, min_rate=.00001))
10折交叉验证法正确率:	 0.973333333333
留一法正确率:		 0.966666666667

Wine Data Set

wine = datasets.load_wine()
wine_data = wine.data
wine_target = wine.target
print('10折交叉验证法正确率:\t', ten_fold(wine_data, wine_target, max_rate=.00001, min_rate=.00001))
print('留一法正确率:\t\t', leave_one_out(wine_data, wine_target, max_rate=.00001, min_rate=.00001))
10折交叉验证法正确率:	 0.331460674157
留一法正确率:		 0.331460674157

从结果上看,10折交叉验证法和留一法所估计出的对率回归的正确率(错误率)基本相同。

  • 3.5 编程实现线性判别分析,并给出西瓜数据集3.0a上的结果。

训练:

线性判别分析的原理就是将全部的样本映射到一条直线上,然后使同类样本的投影点尽可能近(协方差尽可能小),异类样本的投影点尽可能远离(均值相差尽可能大),所以优化目标就是:

重写目标函数为:

这个函数的最优解为:

预测:

将对象映射到上,根据最近分类簇中线点作为预测结果

import numpy as np
import pandas as pd


class LDA:
    w = np.array([])
    center = np.array([])

    def fit(self, X, y):
        X = [X[np.where(np.logical_not(y))], X[np.where(y)]]
        mu = np.asarray([np.mean(X[0], axis=0), np.mean(X[1], axis=0)])
        sigma = np.dot((X[0] - mu[0]).T, (X[0] - mu[0])) + np.dot((X[1] - mu[1]).T, (X[1] - mu[1]))
        self.w = np.linalg.solve(sigma, mu[0] - mu[1])
        self.center = np.dot(mu, self.w)

    def predict(self, X):
        return np.argmin(np.abs(np.subtract(np.dot(self.w, X.T), self.center[np.newaxis, :].T)), axis=0)


# Read data
data = pd.read_csv('data3.0.csv')
y = (np.array(data['好瓜']) == '是')
X = np.array(data['密度'])
X = np.append(X, data['含糖率'])
X = np.reshape(X, [2, -1])
X = np.transpose(X)

# Training
model = LDA()
model.fit(X, y)

print("w =", model.w)
print('acc =', np.sum(model.predict(X) == y) / len(y))

运行结果为:

w = [-0.14650982 -0.73871557]
acc = 0.705882352941

第4章 决策树

  • 4.3 试编程实现基千信息墒进行划分选择的决策树算法,并为表 4.3 中数据生成一棵决策树。

信息熵的计算公式为:

对于离散属性,信息增益的计算公式为:

对于连续属性,所有的候选划分点集合为:

信息增益的计算公式为:

其中包含属性a上取值大于t的样本,包含属性a上取值不大于t的样本。

决策树生成算法为:

输入:	训练集D,属性集A
过程:	函数TreeGenerate(D,A)
	生成结点 node;
	if D中样本全属于同一类别C then
		将node标记为C类叶结点; return
	end if
	if A=空 OR D中样本在A上取值相同 then
		将node标记为叶结点,其类别标记为D中样本数最多的类; return
	end if
	从A中选择最优划分属性a;
	for a的每一个值v do
		为node生成一个分支;令Dv表示D中在a上取值为v的样本子集;
		if D为空 then
			将分支结点标记为叶结点,其类别标记为 D 中样本最多的类; return
		else
			以TreeGenerate(Dv,A\{a})为分支结点
		end if
	end for
输出:	以node为根结点的棵决策树

导入数据生成决策树:

import numpy as np
import pandas as pd
import graphviz as gv
from decision_tree import DecisionTree

# Read data
data = pd.read_csv('data3.0.csv')
X = np.array(data[['色泽', '根蒂', '敲声', '纹理', '脐部', '触感', '密度', '含糖率']])
y = np.array(data['好瓜'])

# Training
model = DecisionTree()
model.fit(X, y)
gv.Source(model.export_to_gv(['色泽', '根蒂', '敲声', '纹理', '脐部', '触感', '密度', '含糖率']))

svg

  • 4.4 试编程实现基于基尼指数进行划分选择的决策树算法,为表 4.2 中数据生成预剪枝、后剪枝决策树,并与未剪枝决策树进行比较。

基尼指数是评价样本集合纯度的另外一种指标,基尼指数表示从数据集随机抽取两个样本,其类别标记不一致的概率。因此,基尼指数越小,数据集的纯度越高。 导入数据

import numpy as np
import pandas as pd
import graphviz as gv
from decision_tree import DecisionTree

# Read data
train = pd.read_csv('data2.0train.csv')
train_X = np.array(train[['色泽', '根蒂', '敲声', '纹理', '脐部', '触感']])
train_y = np.array(train['好瓜'])
cv = pd.read_csv('data2.0cv.csv')
cv_X = np.array(cv[['色泽', '根蒂', '敲声', '纹理', '脐部', '触感']])
cv_y = np.array(cv['好瓜'])

未剪枝

从图中可以发现,未剪枝的决策树似乎是过拟合了。

model = DecisionTree(evaluator='gini')
model.fit(train_X, train_y)
gv.Source(model.visualize(['色泽', '根蒂', '敲声', '纹理', '脐部', '触感']))

预剪枝

在每次根据特征进行划分之前,首先在验证集上计算划分前和划分后的准确率:

  1. 划分前准确率:将节点对应的训练集中的多数标记作为分类,计算验证集上的准确率;
  2. 划分后准确率:将训练集和验证集根据最佳属性进行划分,每个划分中训练集中的多数标记就是这个划分对应的标记,根据划分后的分类计算验证集上的正确率。

如果划分后的准确率没有得到提高,那么就不进行划分。

model = DecisionTree(evaluator='gini', pruning='pre')
model.fit(train_X, train_y, cv_X, cv_y)
gv.Source(model.visualize(['色泽', '根蒂', '敲声', '纹理', '脐部', '触感']))

后剪枝

预剪枝是一个自顶向下的过程, 而预剪枝是一个自底向上的过程,对于每一个非叶节点,在验证集上比较直接将训练集多数作为分类和根据子决策树分类的准确率进行比较,如果前者准确率比较高,那么进行剪枝。

model = DecisionTree(evaluator='gini', pruning='post')
model.fit(train_X, train_y, cv_X, cv_y)
gv.Source(model.visualize(['色泽', '根蒂', '敲声', '纹理', '脐部', '触感']))

  • 4.7 图4.2是一个递归算法,若面临巨量数据,则决策树的层数会很深,使用递归方法易导致“栈”溢出。试使用“队列”数据结构,以参数MaxDepth控制树的最大深度,写出与图4.2等价、但不使用递归的决策树生成算法。

参考决策树实现:decision_tree.py

  • 4.8* 试将决策树生成的深度优先搜索过程修改为广度优先搜索,以参数MaxNode控制树的最大结点数,将题4.7中基于队列的决策树算法进行改写对比题4.7中的算法,试析哪种方式更易于控制决策树所需存储不超出内存。

参考决策树实现:decision_tree.py

显然MaxNode控制决策树所需存储更加有效,因为在层数比较高的时候,每一层的节点数量可能会很多,MaxDepth并不能准确控制存储使用量。

  • 4.9 试将4.4.2节对缺失值的处理机制推广到基尼指数的计算中去。
  • 4.10 从网上下载或自己编程实现任慈一种多变量决策树算法,并观察其在西瓜数据集3.0上产生的结果。使用scikit-learn中的决策树学习西瓜数据集3.0。
import pandas as pd
import numpy as np
from sklearn.tree import DecisionTreeClassifier
# Read data
data = pd.read_csv('./data3.0.csv')
X = np.asarray(data[['色泽', '根蒂', '敲声', '纹理', '脐部', '触感', '密度', '含糖率']])
y = np.asarray(data['好瓜'])
# Convert discrete value to continuous value
mapper = [
    {'浅白': 0, '青绿': 1, '乌黑': 2},
    {'硬挺': 0, '稍蜷': 1, '蜷缩': 2},
    {'清脆': 0, '浊响': 1, '沉闷': 2},
    {'清晰': 0, '稍糊': 1, '模糊': 2},
    {'平坦': 0, '稍凹': 1, '凹陷': 2},
    {'软粘': 0, '硬滑': 1}
]
X = X.transpose()
for i in range(0, len(mapper)):
    X[i] = [mapper[i][val] for val in X[i]]
X = X.transpose()
X = X.astype(dtype=float)
y = (y == '是')
# Training
model = DecisionTreeClassifier()
model.fit(X, y);

如果使用默认参数,决策树完全适应数据集。

# Test
print("acc =", np.sum(model.predict(X) == y) / len(X))
acc = 1.0

相关资源

  1. 决策树实现:decision_tree.py
  2. 西瓜数据集2.0:data2.0train.csvdata2.0cv.csv
  3. 西瓜数据集3.0:data3.0.csv