第
5
章
机器学习:无监督学习
无监督学习就是从无标注数据样本出发,学习数据样本中蕴含的模式,主要应
用场景包括聚类分析(ClusterAnalysis)、关联规则(AssociationRule)、维度缩减
(Dimensionaliteduce)等。在现实世界中,高质量、大规模有标注数据通常难以获
yR
得,作为监督学习的必要补充,通过无监督学习快速将无标注数据进行分类显得尤
为重要。本章将从聚类、特征降维以及模型学习的角度介绍无监督学习,包括Kmeans聚类、主成分分析、特征脸方法、局部线性嵌入以及独立成分分析。
..5.1
K-means聚类
K-means(K均值)原型最早由StuartLloyd于1957年提出,被用于脉码调制
技术。而在1967年,
en发表了相关论文并正式提出了Ks聚
JamesMacQu-mean
类算法。通过聚类算法,将大量数据样本根据其特征相似性分为若干个簇,从而
方便用户对数据进一步分析。K-means聚类算法要求特征变量连续且没有异常
数据。它实现起来比较简单,聚类效果也不错,因此具有较为广泛的应用。
5.1
Kmas聚类原理
1.-en
K-means聚类算法解决的问题是,在没有标签数据的前提下,使算法根据距
离的远近将
n
个数据最优地划分为
k
个类(簇)。它是无监督学习中比较常见的
一种算法,原理简单易懂。本质是通过循环,不断迭代类中心点,计算各个数据到
新的类中心点的距离并根据距离最近的原则重新归类,当类内距离最小、类间距
离最大时,即可停止迭代(在使用过程中,常常会限定迭代次数,以防算法陷入死
循环。当达到预先设定的循环次数或类中心点不再发生变化时,则停止迭代并得
到最终聚类结果)。其中,K-means聚类算法得到的聚类结果很容易受初始值影
响,为了达到上述“局部最优解”,可以利用不同的初始值重复几次,常用的初始化
方法包括forgy以及randompartition。
5.1.2
K-means聚类算法
n
假设待聚类样本集合为D={}1,
d
,K-means聚类算法的目标是将
数据集划分为k(k<n)类,使得划分后的
k
个子集合满足类内的误差平方和最
小。在StuartLloyd提出的经典K-means聚类算法中,采取迭代优化策略,有效
xjj=xj
∈R
116人工智能基础:算法与编程
地求解目标函数的局部最优解。具体的算法流程如下。
1.初始化聚类中心
初始化k个聚类中心c={c1,c2,…,ck},cj∈Rd(1≤j≤k), 每个聚类中心cj所在的集
合记作Gj。
2.对数据进行聚类
该步骤的目标是将每个待聚类数据放入唯一一个聚类集合中,首先通过设定的相似度/
距离函数计算每个待聚类数据和k个聚类中心的距离。以最常见的欧氏距离为例,计算xi
和cj之间的欧氏距离:
dist(xi,cj)=Σ do=1 (xi,o-cj,o)2(1≤i≤n,1≤j≤k)
将每个xi归并到与其距离最短的聚类中心所在的聚类集合中,即argmin cj∈Cdist(xi,cj) 。
3.更新聚类中心
根据聚类结果更新聚类中心,即根据每个聚类集合中所包含的数据,求均值得到该聚类
集合新的中心:
cj=1 |Gj|Σ xi∈Gjxi
由此可以看出,K-means聚类的名称来源于此,而求取均值的操作简单高效,因此K-
means聚类算法在大规模数据上可以得到更为高效的应用。
4.
迭代
迭代的过程即根据新的聚类中心,重复执行步骤2与步骤3,在达到停止条件时终止迭
代,从而得到最终的聚类结果。聚类迭代的停止条件判断并不唯一,通常使用的方法包括以
下两种。
(1)达到最大迭代次数。
(2)聚类中心不再变化。
从另一个角度理解K-means聚类算法,最小化所有数据与聚类中心的距离等同于最小
化每个类簇的方差。K-means在迭代过程中需要不断减少簇内数据与聚类中心的欧氏距
离,这相当于簇内数据方差最小化的目标函数:
argminΣ(k) Σ‖x-ci‖2=argminΣ(k) |Gi|varGi
G
i=1x∈Gi G
i=1
其中,第
i
个聚类簇的方差为
1
var(Gi)|Gi|Σ‖xci‖2
=
x∈Gi
通常而言,聚类算法的目标是得到一个类内距离小(或称为类内相似性大)而类间距离
大(或称为类间相似性小)的聚类结果。K-means聚类就是通过最小化簇内方差来实现类
内相似性最大化,即最小化每个簇内的数据方差从而使得最终聚类结果中的数据所呈现出
来的差异性最小。
例5.假设有8个点:(3,1),(3,2),(4,1),(4,2),(1,3),(1,4),(2,3),(2,4)。
1
使用K-means聚类算法对其进行聚类。设初始聚类中心分别为(0,4)和(3,3)。请写出详
细的计算过程。
第5章 机器学习:无监督学习1 17
解:
第一步:列出数据表格,如表5.1所示。
表5.1 数据表格
a b
x1 3 1
x2 3 2
x3 4 1
x4 4 2
x5 1 3
x6 1 4
x7 2 3
x8 2 4
第二步:初始聚类中心分别为c1(0,4)和c2(3,3),计算各点到两中心的距离,如表5.2
所示。
表5.2 各点到两中心的距离
c1(0,4) c2(3,3)
x1(3,1) 4.242 2√
x2(3,2) 3.605 1√
x3(4,1) 5 2.236√
x4(4,2) 4.472 1.414√
x5(1,3) 1.414√ 2
x6(1,4) 1√ 2.236
x7(2,3) 2.236 1√
x8(2,4) 2 1.414√
第三步:根据表5.2分成两簇{x1,x2,x3,x4,x7,x8},{x5,x6}。重新计算新的聚类中
心c3,c4。并计算新的距离表,如表5.3所示。
c3 = 3+3+4+4+2+2
6 ,1+2+1+2+3+4
6
.
è .
.
. ÷
=(3,2.167)
c4 = 1+1
2 ,3+4
2
.
è .
.
. ÷
=(1,3.5)
表5.3 新的距离表1
c3(3,2.167) c4(1,3.5)
x1(3,1) 1.167√ 3.201
续表
1 18 人工智能基础:算法与编程
c3(3,2.167) c4(1,3.5)
x2(3,2) 0.167√ 2,5
x3(4,1) 1.536√ 3.905
x4(4,2) 1.013√ 3.354
x5(1,3) 2.166 0.5√
x6(1,4) 2.712 0.5√
x7(2,3) 1.301 1.118√
x8(2,4) 2.088 1.118√
第四步:根据表5.3分成两簇{x1,x2,x3,x4},{x5,x6,x7,x8}。重新计算新的聚类中
心c5,c6。并计算新的距离表,如表5.4所示。
c5 = 3+3+4+4
4 ,1+2+1+2
4
.
è .
.
. ÷
=(3.5,1.5)
c6 = 1+1+2+2
4 ,3+4+3+4
4
.
è .
.
. ÷
=(1.5,3.5)
表5.4 新的距离表2
c5(3.5,1.5) c6(1.5,3.5)
x1(3,1) 0.707√ 2.915
x2(3,2) 0.707√ 2.121
x3(4,1) 0.707√ 3.535
x4(4,2) 0.707√ 2.915
x5(1,3) 2.915 0.707√
x6(1,4) 3.535 0.707√
x7(2,3) 2.121 0.707√
x8(2,4) 2.915 0.707√
第五步:根据表5.4分成两簇{x1,x2,x3,x4},{x5,x6,x7,x8},和第四步分簇一致,停
止计算。
5.1.3 K-means聚类算法特点
1.优点
由上述算法流程可以看出,K-means聚类算法思想简单,容易理解。当数据分布接近
高斯分布的时候,聚类效果非常不错。而对于大多数样本也可以获得较好的聚类效果,尽管
是局部最优,但依然可以满足大部分任务。并且K-means聚类算法在处理大数据集的时
候,可以保证较好的伸缩性。
此外,K-means聚类算法收敛速度很快。首先,在样本分配阶段,需要计算kn 次误差
第5章机器学习:无监督学习119
平方和,计算复杂度为O(knd) 。其次,在更新聚类中心阶段,计算复杂度为O(nd) 。如果
迭代次数为t,则算法的计算复杂度为O(kndt) 。因此可以看出,K-means聚类算法针对n
个样本个数具有线性的计算复杂度,是一种非常高效的大数据聚类算法。
2.缺点
K-means聚类算法需要事先指定聚类数k,不同k值得到的结果不一样,而很多时候并
不知道数据应该被聚为多少类。通常使用的方法是遍历一个范围内的候选值然后测试错误
率,但通常因为可选范围较大而并不切实际。
K-means聚类算法对初始的聚类中心较为敏感,不同的选取方式对聚类的结果有较大
影响。这是由于K-means聚类算法仅对目标函数求取近似局部最优解,不能保证得到全局
最优解,即在一定数据分布下聚类结果会因为初始化的不同产生很大偏差。
K-means聚类算法对异常数据非常敏感。K-means聚类算法假设数据是没有离群点
的,它对离群点的处理与其他数据一样,然而离群点对均值计算影响较大,会让聚类中心偏
离没有离群点的中心,从而影响聚类效果。为此,可以使用目标函数或K-medoids算法来
减小离群点对聚类结果的影响。K-medoids算法选取的中心点(medoids)属于聚类簇中的
一个点,这是与K-means聚类算法的主要区别。
每个样本只能归到某个固定类别,即K-means聚类算法对每个数据的归属判定非1即
0,不可能同属于多个类别,这种聚类方法被称为“硬聚类”。然而,由于数据或初始值的轻微
这些数据点可能有更好的归属判定方式。
改变,聚类边缘的数据点很容易被改变聚类类别,
例如,高斯混合模型,通过概率的形式判定数据的归属,通过设置属于不同簇的概率来判断
每个数据点的归属方式。
K-means聚类算法对数据的尺度很敏感,也就是说,对数据所在的坐标空间敏感,例
如,某个长度特征以cm 还是以m为单位对最终的聚类结果有较大的影响,这是由于欧氏距
离假设数据每个维度的重要性是一样的。
经典的K-means聚类算法采取二次欧氏距离作为相似性度量,并且假设目标函数的误
差服从标准的正态分布,因此,K-means聚类算法在处理非标准正态分布或非均匀分布的
数据时效果较差。
5.1.4
K-means聚类算法的改进
1.
聚类中心初始化的改进
在标准K-means聚类算法中,初始聚类中心使用随机采样的方式,不能保证得到的期
望聚类结果。为了获得更好的聚类结果,可以多次随机初始化聚类中心,通过对比多组结果
从而选择最优聚类结果。但是这样做会大大影响计算时间,那么如何更好地初始化聚类
中心?
其中最有效简单的改进方式是DavidArthur提出的K-means++ 聚类算法,该算法能
够有效地产生初始的聚类中心,保证初始化后的Kmenlg的近似解。首
c1},
-as可以得到O(ok)
先随机初始化一个聚类中心C={然后通过迭代计算最大概率值:
x
* dist(x,C)
=argmax dist(xj
,C)
x
Σ
j=1,2,…,
n
120人工智能基础:算法与编程
然后将x*加入到下一个聚类中心:
C←C∪{x*}
直到选择k个中心。
K-means++ 聚类算法的计算复杂度为O(knd), 没有增加过多的计算负担,同时可以
保证算法更有效地接近于最优解。
2.类别个数的自适应确定
聚类算法中的类别数对聚类效果有较大的影响,而该参数根据自身的先验知识或启发
式来确定。例如,事先已经知道数据特征的大致分布或样本中包含的属性个数,如数字、性
别等,那么如何在算法中加入自适应决定类别个数的过程?
ISODATA 算法是经典的改进方法,该算法与K-means聚类算法在基本原则上一致,
即通过计算误差平方和最小来实现聚类。但是ISODATA 算法在迭代过程中引入类别的
合并与分开机制。在每次迭代的过程中,ISODATA 算法首先在固定类别数的前提下进行
聚类,然后根据设定样本之间的距离阈值进行合并操作,并根据每一组类别Gi中样本协方
差矩阵信息来判断是否分开。
ISODATA 算法在K-means聚类算法的基础上引入了启发式重初始化,相比于经典的
K-means聚类算法,计算效率大打折扣。
3.面向非标准正态分布或非均匀分布数据的算法改进
如图5.1所示,针对非标准正态分布和非均匀分布的数据时,K-means聚类算法不能得
到预期结果,原因在于假设相似度度量为欧氏距离,而在实际数据集合中该假设不一定都会
成立。
图5.
1彩图
图5.非标准正态分布(上)和非均匀分布样本(下)的聚类结果
1
为了克服该假设的局限性,K-means聚类算法需要推广到更广义的度量空间。经典的
两种改进框架为KernelK-means和谱聚类SpectralClustering。
第5章 机器学习:无监督学习1 21
KernelK-means聚类算法将数据点xi 通过某种映射方式xi→.(xi)映射到新的高维
空间Φ,在该空间中数据点之间的内积可以通过对应的核函数进行计算,即:
k(xi,xj)=.(xi)T.(xj)
借助核函数,可以在新的高维空间对数据进行K-means聚类,样本之间的相似性度量
就取决于核函数的选择。
谱聚类算法尝试着变换数据的度量空间,首先需要求取数据集合的仿射矩阵,然后计算
仿射矩阵的特征向量,利用得到的特征向量进行K-means聚类。仿射矩阵的特征向量隐含
地重新定义样本点的相似性。
4.二分K-means聚类
按照K-means聚类规则很容易陷入局部最小值,为了克服这一问题,提出了二分Kmeans
聚类算法。它首先将所有数据点作为一个簇,然后将该簇一分为二,之后选择其中一
个簇继续进行划分,选择哪一个簇进行划分取决于对其划分是否可以最大程度降低误差平
方和,不断重复上述划分过程,直到得到用户指定的聚类簇数目为止。
5.1.5 K-means聚类算法的Python实现
import numpy as np
import random
import matplotlib.pyplot as plt
def distance(point1, point2): #计算距离(欧几里得距离)
return np.sqrt(np.sum((point1 - point2)**2))
def k_means(data, k, max_iter=10000):
centers = {} #初始聚类中心
#初始化,随机选k 个样本作为初始聚类中心。random.sample(): 随机不重复抽取k 个值
n_data = data.shape[0] #样本个数
for idx, i in enumerate(random.sample(range(n_data), k)):
#idx 取值范围[0, k-1],代表第几个聚类中心;data[i]为随机选取的样本作为聚类
#中心
centers[idx] = data[i]
#开始迭代
for i in range(max_iter): #迭代次数
print("开始第{}次迭代".format(i+1))
clusters = {} #聚类结果,聚类中心的索引idx -> [样本集合]
for j in range(k): #初始化为空列表
clusters[j] = []
for sample in data: #遍历每个样本
distances = [] #计算该样本到每个聚类中心的距离(只会有k 个元素)
for c in centers: #遍历每个聚类中心
#添加该样本点到聚类中心的距离
distances.append(distance(sample, centers[c]))
1 22 人工智能基础:算法与编程
idx = np.argmin(distances) #最小距离的索引
clusters[idx].append(sample) #将该样本添加到第idx 个聚类中心
pre_centers = centers.copy() #记录之前的聚类中心点
for c in clusters.keys():
#重新计算中心点(计算该聚类中心的所有样本的均值)
centers[c] = np.mean(clusters[c], axis=0)
is_convergent = True
for c in centers:
if distance(pre_centers[c], centers[c]) > 1e-8: #中心点是否变化
is_convergent = False
break
if is_convergent == True:
#如果新旧聚类中心不变,则迭代停止
break
return centers, clusters
def predict(p_data, centers): #预测新样本点所在的类
#计算p_data 到每个聚类中心的距离,然后返回距离最小所在的聚类
distances = [distance(p_data, centers[c]) for c in centers]
return np.argmin(distances)
.. 5.2 主成分分析
在一些应用场景中,需要处理的数据的特征维度非常高。以图像为例,对于高和宽都为
100px的图像,如果将所有像素拼接起来成为一个向量,这个向量的维度为10000。一般情
况下,数据的各个指标之间存在着一定的相关性,从而增加了问题分析的复杂性,并且直接
利用这些指标构建机器学习模型会显著降低运算效率。如果分别对数据的每个指标进行分
析,由于分析通常是孤立的,不能完全利用数据中的信息,因此盲目减少指标会损失较多有
用的信息,从而产生错误的结论。
因此,在减少需要分析的指标同时,尽量减少原指标所包含信息的损失,使得样本数据
能够达到全面分析问题的目的。由于各变量之间存在一定的相关关系,因此可以将关系紧
密的变量变成尽可能少的新变量,使这些新变量是两两不相关的,那么就可以用较少的综合
指标分别代表存在于各个变量中的各类信息。主成分分析(PrincipalComponentAnalysis,
PCA)就是达到这种目的的方法之一。
5.2.1 主成分分析原理
主成分分析属于典型的数据降维方法,降维是一种对高维度数据进行预处理的方法。
即将高维度数据保留下最重要的一些特征,去除数据噪声与不重要的特征,从而实现提升数
据处理速度的目的。例如,对于图像数据,要求保持视觉对象区域构成的空间分布;对于文
本数据,要求保持文本之间的(共现)相似或不相似的特性。在实际的生产和应用中,降维在
第5章 机器学习:无监督学习1 23
一定的信息损失范围内,可以节省大量的时间和成本。在介绍主成分分析之前,先回顾相关
的数学知识,包括方差、协方差、相关系数。
1.方差
方差描述了样本数据的波动程度,当数据分布比较分散(即数据在平均值附近波动比较
大)时,方差就大,反之则小。方差等于各个数据与样本均值之差的平方和的平均数,假设有
n 个数据,记为X ={xi}(i=1,2,…,n),那么样本方差(samplevariance)为
var(X )= 1 n -1Σn
i=1 (xi -u)2
其中,u 是样本均值,u= Σn
i=1
( xi )/n。上述样本方差公式里分母为n-1的目的是让对方差
的估计是无偏估计。
2.协方差
协方差用于衡量两个变量之间的相关度,方差是协方差的一种特例,即当两个变量是相
同情况。假设有两个变量,观察到不同时刻两个变量的取值,记作(X ,Y)={(xi,yi)|i=1,
…,n},那么两个变量的协方差为
cov(X ,Y)= 1 n -1Σn
i=1 (xi -E(X ))(yi -E(Y))
其中,E(X )与E(Y)分别表示X 和Y 的样本均值,分别定义为
E(X )=1 nΣn
i=1
xi,E(Y)=1 nΣn
i=1
yi
表5.5给出了一组身高(X )与体重(Y)方差与协方差的例子。
表5.5 方差与协方差的计算例子(无偏估计)
身高X/cm 体重Y/500g X-E(X) Y-E(Y) [X-E(X)][Y-E(Y)]
1 152 92 -19.4 -39.7 770.2
2 185 162 13.6 30.3 412.1
3 169 125 -2.4 -6.7 16.1
4 172 118 0.6 -13.7 -8.2
5 174 122 2.6 -9.7 -25.2
6 168 135 -3.4 3.3 -11.2
7 180 168 8.6 36.3 312.2
E(X )=171.4 E(Y)=131.7 var(X )=94.2 var(Y)=592.8 cov(X ,Y)=209.4
对于一组二维变量(例如,身高-体重、广告投入-商品销售、天气状况-旅行计划等),可通
过计算它们之间的协方差值来判断这组数据给出的二维变量是否存在关联关系。
当协方差cov(X ,Y)>0时,则X 与Y 正相关。
当协方差cov(X ,Y)<0时,则X 与Y 负相关。
当协方差cov(X ,Y)=0时,则X 与Y 不相关。
从表5.5中可以看出,身高较高的体重一般会比较大,同样,体重大的身高一般也比较
124人工智能基础:算法与编程
高,得到的结果也是正相关的,计算出来的结果也非常符合直觉认知。
3.相关系数
由于协方差计算的结果会受到变量取值尺度的影响,而皮尔逊相关系数(Pearson
CorrelationCoefficient)通过将两组变量之间的关联度规范到一定取值范围内很好地解决
了这个问题。它的定义方式如下:
corr(X,Y)= cov(X,Y)
var(X)var(Y) = cov(X,Y)
σxσy
其中,σx与σy分别表示X与Y的标准差。
根据施瓦茨不等式可以得到皮尔逊相关系数的性质如下:
|corr(X,Y)|≤1
当corr(X,Y)=1时,说明两个随机变量完全正相关,即满足Y=aX+b,a>0。考虑
corr(X,X),两个随机变量相同,一定满足线性关系,此时,cov(X,X)=var(X),容易得到
corr(X,Y)=1。当corr(X,Y)=-1时,说明两个随机变量完全负相关,即满足Y=-aX+b,
a>0。而当0<|corr(X,Y)|<1时,说明两个随机变量之间存在一定的线性关系。其中,
正相关即表示变量X增加的情况下,变量Y也随之增加;而负相关表示变量X减少的情况
下,变量Y随之增加。以表5.5为例,身高体重的相关系数为corr(X,Y)=209.4/(9.7×24.3)=
0.888。
从上述定义可以看出,皮尔逊相关系数具有对称的属性,即:
coX
,=oY,
r(Y)cr(X)
由上述定义可以得出如下性质:皮尔逊相关系数描述了两个变量的线性相关程度,如
果|cor(Y)|的取值越大, cor(Y)|=0
X,则两者之间存在相关程度较大的线性关系。而当|X,
时,表示两者之间不存在线性关系,但不是没有关系,可能存在其他非线性关系。
4.主成分分析
回到特征降维,降维需要尽可能将数据向方差最大的方向进行投影,使得数据所包含的
信息丢失尽可能少,且保留最主要的特征成分, 2(所示,
从而增加特征的判别性。如图5.a)
这些二维数据向一维空间投影时,向
y
方向投影明显比向
x
方向投影的降维意义更大,因
为在
y
方向的特征具有更大的方差,从而使得特征具有更强的判别性;而图5.则往黑
线方向投影效果更好。这些投影方式更好地保留了未降维之前数据的离散程度
2
。
(b)
图5.
2
PCA降维示意图
主成分分析的思想是将
d
维特征数据映射到
l
维空间(一般d.l),这
l
维是全新的正
交特征也被称为主成分,是在原始
d
维特征数据的基础上重新构造的
l
维特征。主成分分