机器学习实战笔记 – 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-近邻算法在机器学习实战中的总结,在下一节我们将介绍决策树。

机器学习技法笔记 – Matrix Factorization(矩阵分解)

Linear Network Hypothesis

一言以概之,Matrix Factorization是一种提取数据集隐藏特征的技术。

对于一些已有特征是类别(Categorical)的机器学习问题,我们通常需要对这些特征进行编码。

例如我们有关于用户信息的数据集,其输入为例如ID、血型、生日、爱好,输出则是某一个用户对多部电影的评分。

我们希望预测:对于一个数据集样本外的用户,他可能对现有的多部电影如何评分。

我们将以一个\(N-\tilde{d}-M\)的网络来说明Matrix Factorization是如何工作的:

可以看到,该网络具有一个输入层,一个隐含层,一个输出层。

我们用\(V^T\)与\(W\)表示每层网络的权重,在本问题中,输入X是一个\(N\)维列向量(\(N×1\)),因为该网络是一个\(N-\tilde{d}-M\)的网络,易知\(V^T\)是维度为\(\tilde{d}×N\),而\(W\)的维度为\(M×\tilde{d}\)

则输出层具有以下形式:

$$h(x) = W^TVx$$

为了简化问题,我们假设在本问题中只有一个特征(性别)需要被编码,那么对于输入\(x\)来说,这个列向量矩阵是非常稀疏的,它可能具有以下形式:

$$x = \begin{bmatrix} 0 & 1 & 0 & 0 \end{bmatrix}^T$$

试想,这样一个稀疏向量对矩阵\(V\)进行线性组合,结果显而易见地将是仅有在向量\(x\)中不为零的列\(n\)将会在矩阵\(V\)中保留下来,所以我们的\(h(x)\)可以进行如下简化:

$$h(x) = W^Tv_{n}$$

其中,\(v_n\)是矩阵\(V\)的第\(n\)列。

Basic Matrix Factorization

对于Matrix Factorization,我们希望:

$$y ≈ h(x) = W^Tv_{n} = W^TVx$$

在本问题中,输出\(y\)是一个\(M×1\)的列向量,代表了用户对每部电影的评分。

同时我们知道\(v_{n}\)是一个\(\tilde{d}×1\)的列向量,而\(W^T\)是\(M×\tilde{d}\)的矩阵,那么对于某一部电影的评分则有以下形式:

$$y_{m} = w_{m}^Tv_{n}$$

其中,\(w_m^T\)是矩阵\(W\)的第\(m\)行。

而\(W^TV\)与\(w_{m}^Tv_{n}\)的关系则有下图:

我们认为,\(W\)与\(v_n\)分别描述了电影的特征与用户的特征。

一个直观的结论即是,当\(v_n\)在对\(W\)做线性组合时,如果在用户特征矩阵(列向量)\(v_n\)与在电影特征矩阵\(W\)的第\(m\)行的内积,即是用户\(n\)对电影\(m\)的评分。

这个分数直观的反映了用户的某些特征对电影的某些特征的“接近程度”。

所以,Matrix Factorization的学习过程即最优化\(w_m^T\)与\(v_n\)的过程。

定义Matrix Factorization的Error Function如下:

$$E_{in}({w_m}, {v_n}) = \sum_{m = 1}^{M} \left( \sum\left( y_{nm} – w_m^T v_n \right)^2\right)$$

问题转化为了一个具有两个变量的最优化问题。

与上节在RBF Network中介绍的k-Means的最优化问题相同,我们首先为\(W\)与\(V\)设置初始值,然后固定一个优化另一个。

每一个优化过程都是一个Linear Regression的过程,最终他们将收敛于\(E_{in} = 0\)

这种算法被称为Alternating Least Squares,其具体流程如下:

我们可以发现,Matrix Factorization与Linear AutoEncoder具有相似和不同之处:

相对于Linear AutoEncoder而言,其最优解是一个全局的最优解,而对于Matrix Factorization而言,其最优解是一个局部的最优解。

它们都是一种网络的模型,用于提取数据集的隐藏特征。

Stochastic Gradient Descent

除了Alternating Least Squares,SGD同样可以用于求解Matrix Factorization的局部最优解。

同时SGD可能在一些情况相对于Alternating Least Squares而言具有更好的性能,同时由于实现简单,在实际问题在更常使用。

对于原Error Function:

$$err(v_n, w_m) = \left( y_{nm} – w_m^T v_n \right)^2$$

分别对\(v_n\)与\(w_m\)求其梯度:

$$\nabla_{v_n}\text{err}(n, m) = – 2(y_{nm} – w_m^T v_n)w_m\\ \nabla_{w_m}\text{err}(n, m) = – 2(y_{nm} – w_m^T v_n)v_n$$

我们可以发现\(w_m\)的梯度值正比于\(v_n\),反之亦然。

我们可以通过这一性质简化SGD的过程,我们通过计算下式:

$$\tilde{y}_{nm} = (y_{nm} – w^T_{m}v_{n})$$

然后通过下式更新变量:

$$v_n^{new} ← v_n^{old} + \eta ·  \tilde{y}_{nm} w_{m}^{old} \\ w_m^{new} ← w_m^{old} + \eta ·  \tilde{y}_{nm} v_{n}^{old}$$

从而通过SGD来做Matrix Factorization的训练过程。

Summary of Extraction Models

某种意义上,Feature Transform(特征转换)即是一种Extraction Models,截至目前,我们已经介绍了多种Aggregation Model,每种Aggregation Model都具有自己的Extraction Models,下图是一个简略的总结:

我们可以看到,各个Aggregation Model用于提取数据模型特征的方法不尽相同,具体的每一个方法,我们在前几章均已经做了详细的介绍。

最后我们将Neural Network、RBF Network、Matrix Factorization做一个简单的整理:

对于这三种非线性的模型,他们的优点是明显的,即他们足够强大,如果数据量足够大、隐含层足够多,他们的泛化能力将会非常强大。

但是缺点也显而易见,即这些模型面对的问题本身可能是非凸的,即可能本身没有一个最优解,同时我们需要时刻注意Regularization与Validation,以避免Overfitting的发生。

以上是对Matrix Factorization在台湾大学机器学习技法课程的笔记总结。

至此,所有课程中相关的机器学习技法已经全部介绍完毕了。

在下一篇文章中,我们将会对机器学习技法做最后的总结。

 

机器学习技法笔记 – Radial Basis Function Network(RBF Network)

RBF Network Hypothesis

一言以概之的说,RBF Network是一种根据RBF的线性组合。

其中每一个RBF用于描述了某个数据点与某个聚类的相似度,然后将他们进行线性组合而成的网络,即是RBF Network。

它和使用了Gaussian Kernel的SVM具有相似之处,即某种意义上它们都是通过计算某个数据点与样本中某个点的相似度来进行分类或者预测的。

在SVM中,用于参与计算的通常是那些支撑向量:

而在RBF Network中我们的\(h(x)\)通常具有以下形式:

$$h(x) = sign(\sum^{M}_{m=1} \beta_{m}RBF(x, \mu_{m}) + b)$$

其中\(\beta_{m}\)是每个RBF的权重,其中\(\mu_{m}\)通常是某个聚类算法生成的簇中某个代表点。

不同于神经网络通过多权重和多个隐含层计算下层输入与输出,RBF Network通常具有以下图像化的描述:

RBF Network Learning

那么如何训练RBF Network Learning呢?

我们首先介绍一种简单的方法,即Full RBF Network。

在Full RBF Network中,在上节的\(h(x)\)中,\(M=N\),即RBF的数量即数据集的大小,而\(\mu_m=x_m\),即对于每一个RBF,它的代表点即是\(x_m\),而令\(\beta_m=1 · y_m\),即每个RBF平权,则Full RBF Network具有以下形式:

$$g_{uniform}(x) = sign(\sum^{M}_{m=1} y_{m}exp(-\gamma \Vert{x-x_{m}}\Vert^2))$$

Full RBF Network也被称为Nearest Neighbor,观察上式,可以发现上式中\(g(x)\)正是在寻找某个与\(x_m\)距离最近的\(x\),其中:

$$exp(-\gamma \Vert{x-x_{m}}\Vert^2)$$

根据\(\gamma\)的取值与指数函数的性质,与代表点距离越近的点使得函数值越接近\(1\),而偏离的点衰减很快。

我们可以通过寻找数据集中\(k\)个最具代表性的点,来组成具有\(k\)个RBF构成的RBF Network。

这又被称之为k Nearest Neighbor(k近邻)。

回到Full RBF Network的话题,无论是采用全部数据作为代表点还是前\(k\)个代表点,如何最优化\(\beta\)矩阵也是一个重要话题。

此时的RBF Network某种意义上可以类比于一个Linear Blending Model,我们可以添加Regularizer后通过解Linear Regression的问题得到最优的\(beta\)矩阵,它具有以下形式:

$$\beta = (Z^TZ + \lambda I)^{-1}Z^Ty$$

但是显然\(E_{in} = 0\)与Full RBF并不是我们想要的,它显然可能会导致Overfitting,接下来我们将介绍k-means算法,来解决这个问题。

k-Means Algorithm

无论是采用Full RBF Network还是K Nearest Neighbor,我们都可能遇到这种情况,如果\(x_1 ≈ x_2\), 如果\(x_1, x_2\)都作为代表点参与RBF Network,这显然是冗余的。

我们可以将\(N\)个数据点通过聚类分成\(M\)个簇,为每一个簇选择最具代表性的\(\mu_m\),通过这种方法将产生\(M\)个RBF。

这种算法被称为k-Means Algorithm,它的具体工作方式总是希望最小化下式:

不过显然可以预见的是,上式因为具有两组变量需要最优化,我们必须先固定一组变量进行最优化。

我们首先假设\(M\)个簇已经确定,即有\(S_1, ···, S_M\),我们首先固定了\(S_m\),来优化\(\mu_m\),对原式求梯度得:

由于判断数据点是否属于\(S_m\)的布尔运算,所以将有右式的结果。

令原式等于\(0\),可以发现:

$$\mu_m = \frac{-2 · \underset{x_n∈S_m}{\sum x_n}}{\vert{S_m}\vert}$$

但是在实际的k-Means算法中,我们通常先初始化\(\mu_m\),然后优化\(S_m\),然后重复上述步骤,直至收敛(\(E_{in} = 0\)):

这就是k-Means算法。

将k-Means结合RBF Network,则有以下步骤:

我们首先通过k-Means获得\(M = k\)个\(\mu_m\),然后得到\(M\)个RBF,然后再通过Linear Blending得到RBF Network:

k-Means and RBF Network in Action

以下分别是k-Means与Full RBF Network的运行效果图:

以上是对Radial Basis Function Network在台湾大学机器学习技法课程的笔记总结。

在下一篇文章中,将会讨论Matrix Factorization。