Gadzan

有监督与无监督学习,KNN与KMeans

从有监督学习到无监督学习

有监督学习和无监督学习,是机器学习两个大的类别。我们之前讲的都是有监督学习,毕竟有监督学习现阶段还是机器学习在实际应用中的主流。

有监督学习(Supervised Learning)

所谓有监督学习,即:

  • 训练数据同时拥有输入变量($x$)和输出变量($y$);

  • 用一个算法把从输入到输出的映射关系——$y = f(x)$——学习出来;

  • 当我们拿到新的数据 $x'$ 后,就可以通过已经被学习出的 $f(\cdot)$,得到相应的 $y'$。

有监督学习就像在学校上课——老师给我们留作业,盯着我们做作业,再给我们判作业。

每道作业题(输入变量),都有正确答案(输出变量);而整个算法运行的过程,就像有一个老师在监督着学生的每个解答,跟随指导,一旦出现错题立刻予以纠正——把有可能“跑偏”的参数给“拽”回来。

等到老师觉得学生已经掌握了现在的知识,就可以下课了——有监督学习在算法获得可接受的性能之后便停止。

无监督学习(Unsupervised Learning)

无监督学习和有监督学习相对,即:

  • 训练数据只有输入变量($x$),并没有输出变量

  • 无监督学习的目的是将这些训练数据潜在的结构或者分布找出来,以便于我们对这些数据有更多的了解。

无监督学习没有正确答案也没有老师,只有算法自己在数据中探索,去发现蕴含在数据之中的有趣结构。

比较起来,有监督学习可以类比人类学习已有知识;而无监督学习则更像是去探索新的课题。

半监督学习(Semi-supervised Learning)

还有一种介于有监督和无监督之间的半监督学习,或者说是一种混合应用有监督和无监督学习的方法。

它所对应的场景是:有一部分训练数据的输入变量($x$)有对应的输出变量($y$),另一些则没有

有监督学习虽然有效,但标注数据(给训练数据的 $x$ 指定正确的 $y$)在目前还是一种劳动力密集型的人工劳动,所需投入巨大。

在现实当中,出现了一些问题,如果用有监督学习效果会比较好,可惜标注数据太少,大量数据都没有被人工标注过。

在这种情况下,我们可以尝试:

  • 首先,用无监督学习技术来发现和学习输入变量的结构;

  • 然后,用有监督学习对未标注数据的输出结果进行“猜测”;

  • 最后,再将带着猜测标签的数据作为训练数据训练有监督模型。

这就是半监督学习

下图可见这三类学习算法的差异:

发展趋势

单纯就机器学习而言,目前,无论是模型、算法的研究还是在实际问题上的应用,都以有监督学习为主流。

原因很简单:有监督学习的预测结果可控,优化目标明确,因此只要方法得当,数据质量好,一般模型质量也能比较好。

而无监督学习呢,最终能得出什么结果,可能建模的人自己都不知道;有了结果也不知道往哪个方向去调优;现有的数据好不容易调出了一个可以接受的结果,新数据进来,重新学习后的模型和之前大相径庭……

不过随着大数据时代的来临,各行各业各类数据存量和增量迅速攀升,无监督学习的重要性也随之悄然提升。

究其原因,还是那个最简单的因素:成本——对有监督学习而言,没有标注数据,一切都是空谈,而标注工作需要投入大量人工成本:

  • 有些数据,虽然样本标注相对简单,但因为和业务结合紧密而随时需要调整标注原则;

  • 有些数据,需要的标注量极大,比如图片标注,一张人体或人脸图片就需要标出少则十几个多则几十个关键点;

  • 还有些数据,需要深厚的领域知识才有可能做出标注,比如医学图像的诊断等;

而所有的数据当被派遣给不同的标注人做标注后,又都面临着一致性的问题。

一面是大量易得的源数据,另一面是高昂的标注成本。这种客观的情况,也促进了半监督学习等中间地带方法的出现和应用。

当然,从实际的效用角度而言,真正应用于实际问题解决的模型还是以有监督学习为主。不过在当前大数据技术普及的背景之下,数据分析,机器学习,特别是深度学习方法的研究中,无监督学习越来越被重视。

从今天开始,我们就要进入无监督模型的学习。首先,我们来讲讲:KNN

其实 KNN 是一个有监督学习算法,为什么要放在无监督学习的第一课来讲呢?这个稍后再解释。

KNN 算法

KNN(K-Nearest Neighbor,译作 K-近邻居)算法,是一种既可以用于分类,又可以用于回归的非参数统计方法。

KNN 是一种基于实例的学习,是所有机器学习算法中最简单的一个。

KNN 算法原理

KNN 算法的基本思想是:

  • 训练数据包括样本的特征向量($x$)和标签($y$);

  • $k$ 是一个常数,由用户来定义;

  • 一个没有标签的样本进入算法后,首先找到与它距离最近的 $k$ 个样本,然后用它这 $k$ 个最近邻居的标签来确定它的标签。

KNN 算法的步骤如下。

  1. 算距离:给定未知对象,计算它与训练集中的每个样本的距离——特征变量是连续的情况下,将欧氏距离作为距离度量;若特征是离散的,也可以用重叠度量或者其他指标作为距离,这要结合具体情况分析。

  2. 找近邻:找到与未知对象距离最近的 $k$ 个训练样本。

  3. 做分类/回归:在这 $k$ 个近邻中出现次数最多的类别作为未知对象的预测类别(多数表决法),或者是取 $k$ 个近邻的目标值平均数,作为未知对象的预测结果。

多数表决法有个问题:如果训练样本的类别分布不均衡,出现频率较多的样本将会主导预测结果。

这一问题的解决办法有多种,其中常见的一种是:不再简单计算 $k$ 个近邻中的多数,而是同时考虑 $k$ 个近邻的距离,$k$ 近邻中每一个样本的类别(或目标值)都以距离的倒数为权值,最后求全体加权结果。

有监督学习算法 KNN VS 无监督学习算法 KMeans

前面说了,KNN 是有监督学习模型。无论是做分类还是做回归,KNN 的每个训练样本都带有一个标签(目标值或类别)。

既然是有监督学习算法,我们为什么样要放在这一章讲呢?就是为了和 KMeans 做对比!

为什么要和 KMeans 做对比呢?

原因之一是:这两个算法虽然非常不同,但却经常被初学者搞混,可能是因为名字乍看有几分形似吧。

原因之二是:两者都有一个 $k$——这个 $k$ 还都是一个需要用户主动指定的常数。两个 $k$ 虽然含义和作用不同,但在重要性程度和取值的“艺术性”上,却颇有些异曲同工之妙。

KNN 的 k

在 KNN 算法中,假设训练样本一共有 $m$ 个,当一个待预测样本进来的时候,它要与每一个训练样本进行距离计算,然后从中选出 $k$ 个最近的邻居,根据这 $k$ 个近邻标签确定自己的预测值。

此处的 $k$,是一个正整数。若 $k = 1$,则该对象的预测值直接由最近的一个样本确定。若 $k=m$,则整个训练集共同确定待测样本。

通常情况下,$k > 1$,但也不会太大,是一个较小的正整数。具体取何值最佳,则取决于训练数据和算法目标。

一般情况下, $k$ 值越大,受噪声的影响越小;但 $k$ 值越大,也越容易模糊类别之间的界限。

比如下面这个例子,用 KNN 做分类,黄色为 A 类,紫色为 B 类,红色的是待测样本。

当我们取 $k=3$ 时,根据多数选举法,预测结果为 B;但当 $k=6$ 时,依然是根据多数选举法,预测结果就成为了 A。

可见,$k$ 的取值大小,直接影响着算法的结果。

当然,超参数的选择并不是 KNN 独有的问题,而是一个机器学习常见的共性问题。

专门有一系列超参数最优化方法(例如网格搜索法、随机搜索法、贝叶斯最优化法等),来帮助我们选择最佳的超参数。

因为 $k$ 是 KNN 算法唯一的超参数,因此,它对于 KNN 尤其重要。这一点和 KMeans 的 $k$ 参数之于 KMeans,颇为神似。

什么是聚类(Clustering)

聚类并非一种机器学习专有的模型或算法,而是一种统计分析技术,在许多领域得到广泛应用。

广义而言,聚类就是通过对样本静态特征的分析,把相似的对象,分成不同子集(后面我们将聚类分出的子集称为“簇”),被分到同一个子集中的样本对象都具有相似的属性。

在机器学习领域,聚类属于一种无监督式学习算法。

许多聚类算法在执行之前,需要指定从输入数据集中产生的分簇的个数。除非事先准备好一个合适的值,否则必须决定一个大概值,这是当前大多数实践的现状。我们今天要讲的 KMeans 就是如此。

常用的几种距离计算方法

通常情况下,在聚类算法中,样本的属性主要由其在特征空间中的相对距离来表示。这就使得距离这个概念,对于聚类非常重要。

在正式讲解聚类算法之前,我们先来看几种最常见的距离计算方法。

欧氏距离(又称 2-norm 距离)

在欧几里德空间中,点 $x =(x_1,...,x_n)$ 和 $y =(y_1,...,y_n)$ 之间的欧氏距离为:

$ {d(x,y)={\sqrt {(x_{1}-y_{1})^{2}+(x_{2}-y_{2})^{2}+\cdots +(x_{n}-y_{n})^{2}}}={\sqrt {\sum_{i=1}^{n}(x_{i}-y_{i})^{2}}}} $

在欧几里德度量下,两点之间线段最短。

余弦距离(又称余弦相似性)

两个向量间的余弦值可以通过使用欧几里德点积公式求出:

${{a} \cdot {b} =\left|{a} \right|\left|{b} \right|\cos \theta } $

所以:

$\cos(\theta) = \frac{ {a} \cdot {b}} {|| {a}|| \ || {b} ||}$

也就是说,给定两个属性向量 $A$ 和 $B$,其余弦距离(也可以理解为两向量夹角的余弦)由点积和向量长度给出,如下所示:

$\cos(\theta )={A\cdot B \over |A||B|}={\frac {\sum \limits_{{i=1}}^{{n}}{A_{i}\times B_{i}}}{{\sqrt {\sum \limits_{{i=1}}^{{n}}{(A_{i})^{2}}}}\times {\sqrt {\sum \limits_{{i=1}}^{{n}}{(B_{i})^{2}}}}}}$

这里的 $ A_{i}$ 和 $B_{i}$ 分别代表向量 $A$ 和 $B$ 的各分量。

给出的余弦相似性范围从 $-1$ 到 $1$:

  • $-1$ 意味着两个向量指向的方向截然相反;

  • $1$ 表示它们的指向是完全相同的;

  • $0$ 则表示它们之间是独立的;

  • $[-1, 1]$ 之间的其他值则表示中间程度的相似性或相异性。

曼哈顿距离(Manhattan Distance, 又称 1-norm 距离)

曼哈顿距离的定义,来自于计算在规划为方型建筑区块的城市(如曼哈顿)中行车的最短路径。

假设一个城市是完备的块状划分,从一点到达另一点必须要沿着它们之间所隔着的区块的边缘走,没有其他捷径(如下图):

因此,曼哈顿距离就是:在直角坐标系中,两点所形成的线段对 $x$ 和 $y$ 轴投影的长度总和。

从点 $(x_1, y_1)$ 到点 $(x_2, y_2)$,曼哈顿距离为:

${ \left|x_{1}-x_{2}\right|+\left|y_{1}-y_{2}\right|} $

其他距离

除了上述最常用的几种距离之外,还有其他多种距离计算方法,例如:Infinity norm(又称 Uniform norm,一致范式)、马氏距离、汉明距离(Hamming Distance)等。

在本课的例子中,计算距离时,如无特别说明,采用的都是欧氏距离。

KMeans

什么是 KMeans

简单来说,KMeans 是一种聚类方法,$k$ 是一个常数值,由使用者指定,这种算法负责将特征空间中的 $n$ 个向量聚集到 $k$ 个簇中。

比如,下图就是一个 $k=3$ 的 KMeans 算法聚类前后的情况。

算法步骤

其算法运行过程大致如下:

Step 0:用户确定 $k$ 值,并将 $n$ 个样本投射为特征空间(一般为欧氏空间)中的 $n$ 个点($k \leqslant n$);

Step 1:算法在这 $n$ 个点中随机选取 $k$ 个点,作为初始的“簇核心”;

Step 2:分别计算每个样本点到 $k$ 个簇核心的距离(这里的距离一般取欧氏距离或余弦距离),找到离该点最近的簇核心,将它归属到对应的簇;

Step 3:所有点都归属到簇之后,$n$ 个点就分为了 $k$ 个簇。之后重新计算每个簇的重心(平均距离中心),将其定为新的“簇核心”;

Step 4:反复迭代 Step 2 - Step 3,直到簇核心不再移动为止。

算法的执行过程可用下图直观地表现出来:

计算目标和细节

上面给出的 Step 3 在一次各个点归入簇中的迭代完成后,要重新计算这个簇的重心位置。

重心位置是根据簇中每个点的平均距离来计算的。这个平均距离如何算出?

要明确算法细节,首先要搞清楚 KMeans 算法的目标——在用户提供了 $k$ 值之后,以一种什么样的原则来将现有的 $n$ 个样本分成 $k$ 簇才是最理想的?

目标

有 $n$ 个样本 $(x_1, x_2, …, x_n)$, 每个都是 $d$ 维实向量,KMeans 聚类的目标是将它们分为 $k$ 个簇($k \leqslant n$),这些簇表示为 $S = (S_1, S_2, …, S_k)$。

KMeans 算法的目标是使得簇内平方和(Within-cluster Sum of Squares,WCSS )最小:

$min \sum_{i=1}^{k}\sum_{ {x} \in S_{i}}\left| {x} -{{\mu }}_ {i}\right|^{2}$

其中 $\mu_i$ 是 $S_i$ 的重心。

分配

Step 2 又叫做分配(Assignment)。

设此时为时刻 $t$,$t$ 时刻 $S_i$ 的簇核心为 $\mu_i^{(t)}$。

将某个样本点 $x_p$ 归入到簇 $S_i^{(t)}$ 的原则是:它归入该簇后,对该簇 WCSS 的贡献最小:

$S_{i}^{{(t)}}=
\begin{Bmatrix}
x_{p}:\left|x_{p}-\mu_{i}^{{(t)}}\right|^{2}\leqslant \left|x_{p}-\mu_{j}^{{(t)}}\right|^{2} \ \ \forall j,\ \ 1\leqslant j\leqslant k
\end{Bmatrix}$

因为 WCSS 等于簇中各点到该簇核心的欧氏距离平方和,又因为在每次进行 Step 2 之前,我们已经认定了当时所有簇的簇核心 $\mu_i^{(t)},i=1,2, ..., k$ 已经存在。

因此只要把 $x_p$ 分配到离它最近的簇核心即可 。

注意:尽管在理论上 $ x_{p}$ 可能被分配到 $2$ 个或者更多的簇,但在实际操作中,它只被分配给一个簇。

更新

Step 3 又叫做更新(Update)。

这一步要重新求簇核心,具体计算非常简单,对于该簇中的所有样本求均值就好:

$ \mu_{i}^{{(t+1)}}={\frac {1}{\left|S_{i}^{{(t)}}\right|}}\sum_{{x_{j}\in S_{i}^{{(t)}}}}x_{j}$

其中 $|S_i|$ 表示 $S_i$ 中样本的个数。

启发式算法

启发式算法(Heuristic Algorithm):是一种基于直观或经验构造的算法。

相对于最优化算法要求得待解决问题的最优解,启发式算法力求在可接受的花费(消耗的时间和空间)下,给出待解决问题的一个可行解,该可行解与最优解的偏离程度一般不能被预计。

启发式算法常能发现不错的解,但也没办法证明它不会得到较坏的解;它通常可在合理时间解出答案,但也没办法知道它是否每次都可以这样的速度求解。

虽然有种种不确定性,且其性能无法得到严格的数学证明,但启发式算法直观、简单、易于实现。

即使在某些特殊情况下,启发式算法会得到很坏的答案或效率极差,然而造成那些特殊情况的数据组合,也许永远不会在现实世界出现。

因此现实世界中启发式算法常用来解决问题。

上面我们讲的是最常见的用于实现 KMeans 的启发式算法:Lloyd's 算法。

Lloyd's 算法是一种很高效的算法,通常情况,它时间复杂度是 $O(nkdi)$,其中 $n$ 为样本数,$k$ 为簇数,$d$ 为样本维度数,而 $i$ 为从开始到收敛的迭代次数。

如果样本数据本身就有一定的聚类结构,那么收敛所需的迭代次数通常是很少的,而且一般前几十次迭代之后,再进行迭代,每次的改进就很小了。

因此,在实践中,Lloyd's 算法往往被认为是线性复杂度的算法,虽然在最糟糕的情况下时间复杂度是超多项式(Superpolynomial)的。

目前,Lloyd's 算法是 KMeans 聚类的标准方法。

当然,每一次迭代它都要计算每个簇中各个样本到簇核心的距离,这是很耗费算力的。

不过好在,大多数情况下,经过头几轮的迭代后,各个簇就相对稳定了,大多数样本都不会再改变簇归属,可以利用缓存和三角形公理来简化后续的计算。

局限

KMeans 简单直观,有了启发式算法后,计算复杂度也可以接受,但存在以下问题。

  • $k$ 值对最终结果的影响至关重要,而它却必须要预先给定。给定合适的 $k$ 值,需要先验知识,凭空估计很困难,或者可能导致效果很差。

  • 初始簇核心一般是随机选定的,偏偏它们又很重要,几乎可以说是算法敏感的——一旦选择的不合适,可能只能得到局部的最优解,而无法得到全局的最优解。当然,这也是由 KMeans 算法本身的局部最优性决定的。

这也就造成了 KMeans 的应用局限,使得它并不适合所有的数据。

例如,对于非球形簇,或者多个簇之间尺寸和密度相差较大的情况,KMeans 就处理不好了。

实例(对比 KMeans 和 KNN)

KMeans 实例

下面是一个简单的 KMeans 实例,其中的训练样本是10个人的身高(cm)、体重(kg)数据:

from sklearn.cluster import KMeans
import numpy as np
import matplotlib.pyplot as plt

X = np.array([[185.4, 72.6], [155.0, 54.4], [170.2, 99.9], [172.2, 97.3], [157.5, 59.0], [190.5, 81.6], [188.0, 77.1], [167.6, 97.3], [172.7, 93.3], [154.9, 59.0]])

kmeans = KMeans(n_clusters=3, random_state=0).fit(X)
y_kmeans = kmeans.predict(X)
centroids = kmeans.cluster_centers_

plt.scatter(X[:, 0], X[:, 1], s=50);
plt.yticks(())
plt.show()

plt.scatter(X[:, 0], X[:, 1], c=y_kmeans, s=50, cmap='viridis')
plt.scatter(centroids[:, 0], centroids[:, 1], c='black', s=200, alpha=0.5);
plt.show()

原始训练输入如下:

KMeans 聚类后,它们被分到3个簇:

我们可以预测一下两个新的样本:

print(kmeans.predict([[170.0, 60], [155.0, 50]]))

得到输出如下:

[1 1]

1 对应的是哪个簇呢?我们看看训练样本的归属:

print(y_kmeans)

输出为:

[0 1 2 2 1 0 0 2 2 1]

可见,1 对应的是分簇图中左下角的那一簇。

KNN 实例

同样的问题,如果我们要用 KNN 来解决,应该如何呢?我们指望只输入原始身高体重数据是不够的,还必须要给每组数据打上标签,将标签也作为训练样本的一部分。

如何打标签呢?我们就用上面 KMeans 的输出好了:

from sklearn.neighbors import KNeighborsClassifier

    X = [[185.4, 72.6],
    [155.0, 54.4],
    [170.2, 99.9],
    [172.2, 97.3],
    [157.5, 59.0],
    [190.5, 81.6],
    [188.0, 77.1],
    [167.6, 97.3],
    [172.7, 93.3],
    [154.9, 59.0]]
    y = [0, 1, 2, 2, 1, 0, 0, 2, 2, 1]

    neigh = KNeighborsClassifier(n_neighbors=3)
    neigh.fit(X, y)

然后我们也来预测和 KMeans 例子中同样的新数据:

print(neigh.predict([[170.0, 60], [155.0, 50]]))

最后输出结果为:

[1 1]


打赏码

知识共享许可协议 本作品采用知识共享署名 4.0 国际许可协议进行许可。

评论