机器学习第十章——降维与度量学习

一、k近邻学习

k近邻(k-Nearest Neighbor，简称kNN)学习是一种常用的监督学习方法，给定测试样本,基于某种间隔度量找出训练集中与其最靠近的k个训练样本,然后基于这k个“邻人”的信息来进行预测.
k近邻学习没有显式的训练过程!是“懒惰学习”(lazy learning)的著名代表，
   “懒惰学习”(lazy learning)在训练阶段仅仅是把样本生存起来,训练时间开销为零,待收到测试样本后再进行处置惩罚;
  “急切学习”(eager learning)在训练阶段就对样本进行学习处置惩罚的方法。
  

k近邻算法：

1. from numpy import *
2. import operator
4. def createDataSet () :
5.     group = array ([[1.0,1.1],[1.0,1.0],[0,0],[0,0.1]])
6.     labels = ['A','A','B','B']
7.     return group, labels
9. group,labels = createDataSet()
11. print(group,'\n',labels)
13. def classify0 (inX,dataSet, labels, k) :
14.     datasetsize = dataSet.shape[0]
15.     diffMat = tile(inX, (datasetsize, 1)) - dataSet
16.     sqDiffMat = diffMat**2
17.     sqDistances = sqDiffMat .sum(axis=1)
18.     distances = sqDistances**0.5
19.     sortedDistIndicies = distances. argsort()
20.     classCount={ }
21.     for i in range(k):
22.         voteIlabel = labels[sortedDistIndicies[i]]
23.         classCount[voteIlabel] = classCount.get(voteIlabel, 0) + 1
24.     sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
25.     return sortedClassCount[0][0]
27. print(classify0 ([0, 0], group,labels,3))
30. def file2matrix (filename) :
31.     fr = open (filename)
32.     arrayOLines = fr.readlines ()
33.     numberOfLines = len (arrayOLines)
34.     returnMat = zeros((numberOfLines , 3 ))
35.     classLabelvector = []
36.     index= 0
37.     for line in arrayOLines:
38.         line = line .strip ()
39.         listFromLine = line. split ('\t')
40.         returnMat [index, : ] = listFromLine [0:3]
41.         classLabelvector.append(int(listFromLine[-1]))
42.         index += 1
43.     return returnMat ,classLabelvector
48. datingDataMat ,datingLabels = file2matrix ('datingTestset2.txt ')
51. import matplotlib
52. import matplotlib.pyplot as plt
53. fig = plt.figure ()
54. ax = fig.add_subplot ( 111)
55. # ax.scatter(datingDataMat[:, 1], datingDataMat[:, 2])
56. ax.scatter(datingDataMat[:, 1], datingDataMat[:, 2],15.0*array(datingLabels), 15.0*array(datingLabels))
57. plt.show()

复制代码

运算结果：

二、低维嵌入

“维数劫难”(curse ofdimensionality )：在高维情况下出现的数据样本稀疏、间隔计算困难等问题,是所有机器学习方法共同面对的严峻障碍。
缓解维数劫难的一个重要途径是降维(dimension reduction)，亦称“维数约简”，即通过某种数学变换将原始高维属性空间转变为一个低维“子空间”(subspace)。
很多时候，人们观测或收集到的数据样本虽是高维的,但与学习使命密切相关的也许仅是某个低维分布,即高维空间中的一个低维“嵌入”(embedding).

“多维缩放”(Multiple Dimensional Scaling,简称MDS)：原始空间中样本之间的间隔在低维空间中得以保持（如上图）。
起首令

其中B为降维后样本的内积矩阵，

 有

再令降维后的样本Z被中心化，使得每列的求和以及每行的求和都为0，即

：

如今我们必要把

 表现出来用于构成B矩阵，根据第上面的式子则有:

且其中

上面三个式子分别表现dist间隔矩阵第i行的均值，第j列的均值，以及整个矩阵的均值。用第一个式子表现出

:

依照西瓜书上的习惯我们把负号提出来

那么:

第四个式子中我们两边同时除以

，那么就会有

至此上面的

表达式则可以全部由均值替代。

矩阵B算出来之后则必要对B进行分解使得

，其中Λ \LambdaΛ就是对角矩阵每个值对应一个特征向量，这些特征向量可以拼成V矩阵，可以找到几个比力小的或者说几乎靠近于0的特征值对应的特征向量然后把特征值和特征向量去掉，重新构成新的特征向量矩阵 (

 )和新的特征值对角阵(

),则Z可表达为

.
三、主身分分析

主身分分析(Principal Component Analysis，简称PCA):一种常用的降维方法
可以表达所有样本的超平面性质：

• 最近重构性:样本点到这个超平面的间隔都足够近;
  
• 最大可分性:样本点在这个超平面上的投影能尽大概分开.
  

基于最近重构性:
考虑整个训练集,原样本点

与基于投影重构的样本点

元之间的间隔为

根据最近重构性,上式应被最小化,考虑到

是标准正交基，

是协方差矩阵,有

基于最大可分性: 
投影后样本点的方差是

,于是优化目标可写为

PCA算法: 

四、核化线性降维

例：三维空间中观察到的3000个样本点,是从本真二维空间中矩形区域采样后以S形曲面嵌入,此情况下线性降维会丢失低维布局．图中数据点的染色显示出低维空间的布局.

非线性降维的一种常用方法，是基于核本领对线性降维方法进行“核化”(kernelized)。
核主身分分析(Kernelized PCA，间称KPCA)：
假定我们将在高维特征空间中把数据投影到由W确定的超平面上，即PCA欲求解

其中

是样本点

在高维特征空间中的像.易知

其中

.假定

是由原始属性空间中的样本点

通过映射

产生，即

.若

能被显式表达出来,则通过它将样本映射至高维特征空间,再在特征空间中实施PCA即可.则：

一般情况下，我们不清楚

的具体情势,于是引入核函数

得：

其中K为k对应的核矩阵，

.
五、流形学习

流形学习(manifold learning)是一类借鉴了拓扑流形概念的降维方法.
   “流形”在局部具有欧氏空间的性质,能用欧氏间隔来进行间隔计算.
  

• 若低维流形嵌入到高维空间中,以轻易地在局部创建降维映射关系,然后再设法将局部映射关系推广到全局.
  
• 当维数被降至二维或三维时,能对数据进行可视化展示.
  

  等度量映射

等度量映射(Isometric Mapping,简称Isomap)[Tenenbaum et al., 2000]的基本出发点,是认为低维流形嵌入到高维空间之后,直接在高维空间中计算直线间隔具有误导性

利用流形在局部上与欧氏空间同胚这个性质,对每个点基于欧氏间隔找出其近邻点,然后就能创建一个近邻连接图,图中近邻点之间存在连接,而非近邻点之间不存在连接,于是,计算两点之间测地线间隔的问题,就转变为计算近邻连接图上两点之间的最短路径问题（Dijkstra算法或Floyd算法）。
Isomap算法形貌：

对近邻图的构建通常有两种做法:
   

• 一种是指定近邻点个数，比方欧氏间隔最近的k个点为近邻点,这样得到的近邻图称为k近邻图;
  
• 另一种是指定间隔阈值
  
  ,间隔小于
  
  的点被认为是近邻点,这样得到的近邻图称为
  
  近邻图.
  

  近邻范围指定得较大,“短路”问题;
  近邻范围指定得较小,“断路”问题.
  局部线性嵌入

局部线性嵌入(Locally Linear Embedding,简称LLE)试图保持邻域内样本之间的线性关系.

如上图所示,假定样本点

的坐标能通过它的邻域样本

,

,

的坐标通过线性组合而重构出来,即

 LLE先为每个样本

找到其近邻下标聚集

，然后计算出基于

中的样本点对

进行线性重构的系数

:

其中

和

均为已知,令

，

有闭式解

LLE在低维空间中保持

不变,于是

对应的低维空间坐标

可通过下式求解:

LLE算法形貌：

六、度量学习

欲对间隔度量进行学习,必须有一个便于学习的间隔度量表达情势.
平方欧氏间隔:

引入属性权重w,得到

将W更换为一个普通的半正定对称矩阵M;于是就得到了马氏间隔(Mahalanobis distance)

其中M亦称“度量矩阵”，而度量学习则是对M进行学习.留意到为了保持间隔非负且对称，M必须是(半)正定对称矩阵,即必有正交基Р使得M能写为

.

 

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。