10.1 k近邻学习(KNN)
"急切学习":在训练阶段对训练样本进行学习处理的方法。
"懒惰学习":在训练阶段仅仅是把训练样本保存起来,训练时间开销为零,待收到测试样本后再进行处理,没有显式的训练过程。
KNN是一种不仅仅是一种监督学习方法,同时也是懒惰学习的代表。
-
KNN的工作机制
给定测试样本,基于某种距离度量找出训练集中与其最靠近的k个训练样本,然后基于这k个近邻样本的信息来进行预测。
在分类任务中,使用"投票法",即选择k个近邻样本中出现最多的类别标记作为预测结果。
在回归任务中,使用"平均法",即将k个近邻样本的实值输出标记的平均值作为预测结果。
除此之外,为了更加准确,我们可以基于距离进行加权平均和加权投票,距离测试样本越近的训练样本的权重更大。
k是一个重要参数,当k取不同值时,分类结果可能不同;而且若采用不同的距离计算,找出的近邻样本也会不同,结果也会有所差别。 -
最近邻分类器(k=1)在二分类问题上的性能讨论
假设距离计算能够合适的找到近邻样本。给定测试样本x,近邻样本为z,则1NN分类器分类错误的概率为
KNN代码实现
import numpy as np
import pandas as pd
import matplotlib.pylab as plt
data_=pd.read_csv('vehicle.csv')
print(data_)
feature=np.array(data_.iloc[:,0:2]) # 将参数与特征进行分离,返回数据类型为数组,这里只拿去前两列
#print(feature)
labels = data_['label'].tolist() # 将'label'标签提取出来转换为列表类型,方便后续使用
#print(labels)
# 数据可视化
plt.scatter(data_['length'][data_['label']=='car'],data_['width'][data_['label']=='car'],c='y') #先取length的数值,里面有car和truck的长度,再单独取label那一行为car的值
plt.scatter(data_['length'][data_['label']=='truck'],data_['width'][data_['label']=='truck'],c='r') #先取width的数值,里面有car和truck的长度,再单独取label那一行为truck的值
#print(data_['length'])
#print(plt.show())
test = [4.7,2.1] # 待测样本
numSamples = data_.shape[0] # 读取矩阵的长度,这里是读取第一维的长度# 运行结果:150
diff_= np.tile(test,(numSamples,1)) #这里表示test列表竖向重复150次,横向重复1一次,组成一个素组
# numpy.tile(A,B)函数:A=[4.7,2.1],B=(3,4),意思是列表A在行方向(从上到下)重复3次,在列放心(从左到右)重复4次
diff = diff_-feature # 利用这里的实验值和样本空间里的每一组数据进行相减
squreDiff = diff**2 # 将差值进行平方
squreDist = np.sum(squreDiff,axis=1) # 每一列横向求和,最后返回一维数组
distance = squreDist ** 0.5
sorteDisIndices = np.argsort(distance) # 排序
k=9 # k个最近邻
classCount = {} # 字典或者列表的数据类型需要声明
label_count=[] # 字典或者列表的数据类型需要声明
for i in range(k):
voteLabel = labels[sorteDisIndices[i]]
classCount[voteLabel] = classCount.get(voteLabel,0) + 1
label_count.append(voteLabel)
from collections import Counter
word_counts = Counter(label_count)
top = word_counts.most_common(1) # 返回数量最多的值以及对应的标签
#print(word_counts)
#print(top)
# 利用sklearn进行实现
import numpy as np
import pandas as pd
import matplotlib.pylab as plt
data_=pd.read_csv('vehicle.csv')
feature=np.array(data_.iloc[:,0:2]) # 将参数与特征进行分离,返回数据类型为数组,这里只拿去前两列
labels = data_['label'].tolist() # 将'label'标签提取出来转换为列表类型,方便后续使用
from sklearn.model_selection import train_test_split
feautre_train,feautre_test,label_train,label_test=train_test_split(feature,labels,test_size=0.2)
# 指出训练集的标签和特征以及测试集的标签和特征,0.2为参数,对测试集以及训练集按照2:8进行划分
from sklearn.neighbors import KNeighborsClassifier
model=KNeighborsClassifier(n_neighbors= 9)
model.fit(feautre_train,label_train) # 现在只需要传入训练集的数据
prediction=model.predict(feautre_test)
#print(prediction)
labels=['car','truck']
classes=['car',
'truck']
from sklearn.metrics import classification_report
result_=classification_report(label_test,prediction,target_names = classes,labels=labels,digits=4)
# target_names:类别;digits:int,输出浮点值的位数
print(result_)
代码链接:
https://www.cnblogs.com/lmcltj/p/11010211.html
10.2 低维嵌入
在现实中其实很难达到上述任意测试样本x都能在任意范围内找到训练样本z,即训练样本的采样密度足够大的假设。随着属性的增加,维度越来越大,那么所要求的训练样本会更多,采样密度更大,越难达到假设。
维数灾难
在高维情形下出现的数据样本稀少、距离计算困难等问是所有机器学习方法共同面对的严重障碍,被称为"维数灾难"。
缓解维数灾难的一个重要途径是降维,即通过某种数字变换将原始高维属性空间转变为一个低维子空间,在这个子空间中样本密度大幅度提高,距离计算也变得容易。
之所以可以降维,是因为数据样本虽然是高维的,但是与学习任务密切相关的或许只是某个低维分布,即高维空间中的一个低维''嵌入"。
-
MDS降维法
若要求原始空间中样本之间的距离在低维空间中得以保持,可以使用多维缩放(MDS)。这是一种经典的降维方法。假定m个样本在原始空间d的距离矩阵为D∈Rmxm;
距离矩阵D中第i行j列元素distij为原始空间中样本xi到xj的距离。
我们目标是获得样本在低维空间d'的表示Z∈Rd'xm,d'≤d,
且任意两个样本在低维空间d'中的欧氏距离等于原始空间d中的欧式距离,即||zi-zj||=distij
令降维后样本的内积矩阵为B=ZTZ∈Rmxm,B中任意元素bij=ziTzj。
则有对内积矩阵B进行特征值分解,就可以得到降维后的样本矩阵Z。
令B=VAVT,其中有
A=diag(λ1,λ2,……,λd),是由特征值构成的对角矩阵,λ1≥λ2≥……≥λd;而V为特征向量构成的矩阵。
假设有d个非零特征值,构成的对角矩阵为A*=diag(λ1,λ2,……,λd*),V*表示相应的特征向量矩阵。Z的表达式为
特征值分解的理解
https://blog.csdn.net/yzy_1996/article/details/100540556
MDS代码实现
import numpy
from sklearn import metrics,datasets,manifold
from scipy import optimize
from matplotlib import pyplot
import pandas
import collections
def generate_circle_data():
xx=numpy.zeros((1200,3))
x1=numpy.ones((400,))+0.5*numpy.random.rand(400)-0.5
r1=numpy.linspace(0,2*numpy.pi,20)
r2=numpy.linspace(0,numpy.pi,20)
r1,r2=numpy.meshgrid(r1,r2)
r1=r1.ravel()
r2=r2.ravel()
xx[0:400,0]=x1*numpy.sin(r1)*numpy.sin(r2)
xx[0:400,1]=x1*numpy.cos(r1)*numpy.sin(r2)
xx[0:400,2]=x1*numpy.cos(r2)
x1=3*numpy.ones((400,))+0.6*numpy.random.rand(400)-0.6
xx[400:800,0]=x1*numpy.sin(r1)*numpy.sin(r2)
xx[400:800,1]=x1*numpy.cos(r1)*numpy.sin(r2)
xx[400:800,2]=x1*numpy.cos(r2)
x1=6*numpy.ones((400,))+1.1*numpy.random.rand(400)-0.6
xx[800:1200,0]=x1*numpy.sin(r1)*numpy.sin(r2)
xx[800:1200,1]=x1*numpy.cos(r1)*numpy.sin(r2)
xx[800:1200,2]=x1*numpy.cos(r2)
target=numpy.zeros((1200,))
target[0:400]=0
target[400:800]=1
target[800:1200]=2
target=target.astype('int')
return xx,target
def get_data():
data=datasets.load_iris()
return data.data,data.target
def calculate_distance(x,y):
d=numpy.sqrt(numpy.sum((x-y)**2))
return d
def calculate_distance_matrix(x,y):
d=metrics.pairwise_distances(x,y)
return d
def cal_B(D):
(n1,n2)=D.shape
DD=numpy.square(D)
Di=numpy.sum(DD,axis=1)/n1
Dj=numpy.sum(DD,axis=0)/n1
Dij=numpy.sum(DD)/(n1**2)
B=numpy.zeros((n1,n1))
for i in xrange(n1):
for j in xrange(n2):
B[i,j]=(Dij+DD[i,j]-Di[i]-Dj[j])/(-2)
return B
def MDS(data,n=2):
D=calculate_distance_matrix(data,data)
B=cal_B(D)
Be,Bv=numpy.linalg.eigh(B)
# print numpy.sum(B-numpy.dot(numpy.dot(Bv,numpy.diag(Be)),Bv.T))
Be_sort=numpy.argsort(-Be)
Be=Be[Be_sort]
Bv=Bv[:,Be_sort]
Bez=numpy.diag(Be[0:n])
# print Bez
Bvz=Bv[:,0:n]
Z=numpy.dot(numpy.sqrt(Bez),Bvz.T).T
return Z
def test_iris():
data,target=get_data()
Z=MDS(data)
figure1=pyplot.figure()
pyplot.subplot(1,2,1)
pyplot.plot(Z[target==0,0],Z[target==0,1],'r*',markersize=20)
pyplot.plot(Z[target==1,0],Z[target==1,1],'bo',markersize=20)
pyplot.plot(Z[target==2,0],Z[target==2,1],'gx',markersize=20)
pyplot.title('CUSTOM')
pyplot.subplot(1,2,2)
Z1=manifold.MDS(n_components=2).fit_transform(data)
pyplot.plot(Z1[target==0,0],Z1[target==0,1],'r*',markersize=20)
pyplot.plot(Z1[target==1,0],Z1[target==1,1],'bo',markersize=20)
pyplot.plot(Z1[target==2,0],Z1[target==2,1],'gx',markersize=20)
pyplot.title('SKLEARN')
pyplot.show()
def test_ball():
data,target=generate_circle_data()
Z=MDS(data)
figure1=pyplot.figure()
pyplot.subplot(1,2,1)
pyplot.plot(Z[target==0,0],Z[target==0,1],'r*',markersize=10)
pyplot.plot(Z[target==1,0],Z[target==1,1],'bo',markersize=10)
pyplot.plot(Z[target==2,0],Z[target==2,1],'gx',markersize=10)
pyplot.title('CUSTOM')
pyplot.subplot(1,2,2)
Z1=manifold.MDS(n_components=2).fit_transform(data)
pyplot.plot(Z1[target==0,0],Z1[target==0,1],'r*',markersize=10)
pyplot.plot(Z1[target==1,0],Z1[target==1,1],'bo',markersize=10)
pyplot.plot(Z1[target==2,0],Z1[target==2,1],'gx',markersize=10)
pyplot.title('SKLEARN')
pyplot.show()
if __name__=='__main__':
# test_ball()
test_iris()
代码链接:https://blog.csdn.net/zhangweiguo_717/article/details/69663452
10.3 主成分分析
主成分分析(PCA)直接通过一个线性变换,将原始空间中的样本投影到新的低维空间中。PCA采用一组新的基向量W来表示样本点,其中每一个基向量都是原来基向量的线性组合,通过使用尽可能少的新基向量来表出样本,从而达到降维的目的。即Z = WTX。
实际上就是利用新基向量将原来样本投影到一个由新基向量确定的超平面上。要用一个超平面对空间中所有高维样本进行恰当的表达应具有这样的性质:
- 根据最近重构性推导
假定数据样本进行了中心化,即Σixi=0;
假定投影变换后得到的新坐标系为{w1,w2,...,wd},其中wi是标准正交基向量,即||wi||² = 1, wiTwj=0。
若维度从d降低到d',则样本点xi在低维坐标系中的投影是zi=(zi1,zi2,zi3,…,zid'),其中 zij=wjTxi 指xi在低维坐标系下第j维的坐标。
若基于zi来重构xi,则会得到x~i=Σd'j=1zijwj。
那么,原来样本点xi与重构样本点x~i之间的距离为
- 根据最大可分性
样本点均在新空间中超平面上的投影是WTxi,若所有样本点的投影能尽可能分开,则应该使投影后样本点的方差最大化。
可以看出两个性质推导之后的优化目标是等价的。接着使用拉格朗日乘子法求解上面的优化问题,得到:
PCA代码实现
from numpy import *
def loadDataSet(fileName, delim='\t'):
fr = open(fileName)
stringArr = [line.strip().split(delim) for line in fr.readlines()]
datArr = [map(float,line) for line in stringArr]
return mat(datArr)
def pca(dataMat, topNfeat=9999999): #topNfeat 降维后的维度
meanVals = mean(dataMat, axis=0) #按列求均值,即每一列求一个均值,不同的列代表不同的特征
#print meanVals
meanRemoved = dataMat - meanVals #remove mean #去均值,将样本数据的中心点移到坐标原点
print meanRemoved
covMat = cov(meanRemoved, rowvar=0) #计算协方差矩阵
#print covMat
eigVals,eigVects = linalg.eig(mat(covMat)) #计算协方差矩阵的特征值和特征向量
#print eigVals
#print eigVects
eigValInd = argsort(eigVals) #sort, sort goes smallest to largest #排序,将特征值按从小到大排列
#print eigValInd
eigValInd = eigValInd[:-(topNfeat+1):-1] #cut off unwanted dimensions #选择维度为topNfeat的特征值
#print eigValInd
redEigVects = eigVects[:,eigValInd] #reorganize eig vects largest to smallest #选择与特征值对应的特征向量
print redEigVects
lowDDataMat = meanRemoved * redEigVects #transform data into new dimensions #将数据映射到新的维度上,lowDDataMat为降维后的数据
print lowDDataMat
reconMat = (lowDDataMat * redEigVects.T) + meanVals #对原始数据重构,用于测试
print reconMat
return lowDDataMat, reconMat
def replaceNanWithMean(): #均值代替那些样本中的缺失值
datMat = loadDataSet('secom.data', ' ')
numFeat = shape(datMat)[1]
for i in range(numFeat):
meanVal = mean(datMat[nonzero(~isnan(datMat[:,i].A))[0],i]) #values that are not NaN (a number) # .A表示把矩阵转化为数组array
#nonzero(~isnan(datMat[:,i].A))[0] 返回非0元素所在行的索引;
#>>> nonzero([True,False,True])
# (array([0, 2]),) 第0个和第3个元素非0
#~isnan()返回Ture or False
datMat[nonzero(isnan(datMat[:,i].A))[0],i] = meanVal #set NaN values to mean
return datMat
import matplotlib.pyplot as plt
fig=plt.figure()
ax=fig.add_subplot(111)
import pca
dataMat=pca.loadDataSet('testSet.txt')
lowDMat, reconMat = pca.pca(dataMat,1)
ax.scatter(dataMat[:,0].flatten().A[0], dataMat[:,1].flatten().A[0],marker='^',s=90)
ax.scatter(reconMat[:,0].flatten().A[0], reconMat[:,1].flatten().A[0],marker='o',s=50,c='red')
plt.show() #由两维降为1维数据,降维后为一条红色直线,该方向是样本方差最大的方向,即样本离散程度最大的方向,该方向,将原来的2维数据融合为1维上
lowDMat, reconMat = pca.pca(dataMat,2)
plt.show() #保留原来的2维数据,画图后可看出,数据样本是重合的
代码链接:https://blog.csdn.net/qq_29422251/article/details/79279446
PCA详细讲解以及例子
https://www.cnblogs.com/jerrylead/archive/2011/04/18/2020209.html
10.4 核化线性降维
如SVM在处理非线性可分时,通过引入核函数将样本投影到高维特征空间,接着在高维空间再对样本点使用超平面划分。同样的,若我们的样本数据点不是线性分布,就需要引入核函数,即先将样本映射到高维空间,再在高维空间中使用线性降维的方法。
非线性降维的常用方法是核化主成分分析(KPCA)
KPCA的一个重要之处:即空间中的任一向量,都可以由该空间中的所有样本线性表示。
假定我们将在高维特征空间中把数据投影到由W确定的超平面上,即PCA欲求解
假定zi是由原始属性空间中的样本点xi通过映射φ产生的,即zi=φ(xi)。
若核函数的形式已知,就可以将低维坐标变为高维坐标,这时只需将数据映射到高维特征空间,再在高维空间中运用PCA即可。有
但是一般情况下,我们并不知道具体的映射规则,则引入核函数
10.5 流形学习
流形学习(manifold learning)是一种借助拓扑流形概念的降维方法。
流形是指在局部与欧式空间同胚的空间,即在局部与欧式空间具有相同的性质,能用欧氏距离计算样本之间的距离。这样使得高维空间的分布即使复杂,也能够具有欧氏空间的性质。有两种常用的流形学习方法如下
1. 等度量映射
等度量映射(Isomap)试图在降维前后保持邻域内样本之间的距离。
等度量映射的基本出发点是:高维空间中的直线距离具有误导性,因为有时高维空间中的直线距离在低维空间中是不可达的。如下图
因此利用流形在局部上与欧式空间同胚的性质,可以使用近邻距离来逼近测地线距离,即对于一个样本点,找出邻近点与其连接,它与近邻内的样本点之间是可达的,且距离使用欧式距离计算,这样整个样本空间就形成了一张近邻图,高维空间中两个样本之间的距离就转为最短路径问题。
-
Isomap算法流程
在近邻连接图上计算两点间的最短路径,可采用著名的Dijkstra算法或Floyd算法,得到高维空间中任意两点之间的距离后便可以使用MDS算法来其计算低维空间中的坐标。 -
近邻图的构建
1)指定近邻点个数,像kNN一样选取k个最近的邻居,例如欧氏距离最近的k个点为近邻点,这样得到的近邻图称为k近邻图。
2)指定邻域半径e,距离小于该阈值e的被认为是它的近邻点,得到的近邻图为e近邻图。两种方式均有不足:
a. 若邻域范围指定过大,则会造成“短路问题”,即本身距离很远却成了近邻,将距离近的那些样本扼杀在摇篮。
b. 若邻域范围指定过小,则会造成“断路问题”,即有些样本点无法可达了,整个世界村被划分为互不可达的小部落。
2. 局部线性嵌入(LLE)
Isomap算法保持邻域距离,而LLE算法试图去保持邻域内的线性关系。假定样本xi的坐标可以通过它的邻域样本xj、xk、xl的坐标通过线性组合重构,则有:
-
LLE算法步骤
LLE算法主要有两步
1)第一步为每个样本xi找出近邻样本的下标集合Q,根据近邻关系Q计算出xi的邻域重构系数wi:
2)由于邻域重构系数在低维空间中不变,则x在低维空间中对应的样本zi求解如下:
通过矩阵M,可以将优化问题写为 -
LLE的具体流程
LLE(局部线性嵌入)matlab代码实现
https://blog.csdn.net/qq_30683589/article/details/82685100
10.6 度量学习
度量学习的动机
降维的目的是找到一个空间能够更好地进行学习提高性能。每个空间对应了在样本属性上定义的一个距离度量,而寻找合适的空间,就是在找一个合适的距离度量。度量学习就是找出合适的距离度量。-
距离度量表达式
对于两个d维样本xi和xj,且假定不同属性的重要性不同,则要引入权重w,则有此时各个属性之间都是相互独立无关的,但现实中往往会存在属性之间有关联的情形,例如:身高和体重一般是正相关的。这样计算距离就不能分属性单独计算,因此将W替换为半正定对称矩阵M,得到马氏距离
从上式看出,xi和xj已知,也就是说,度量学习实际上是对度量矩阵进行学习。因此,对M学习就要有学习目标。
如希望提高近邻分类器的性能,则可以将M嵌入到近邻分类器的评价指标错误率中去,通过优化该性能指标从而求得M。
除此之外,还可以将相似度作为优化目标。例如
不同的度量学习方法针对不同目标获得"好"的半正定对称距离度量矩阵M。
若M是一个低秩矩阵,则通过对M进行特征值分解,总能找到一组正交基,其正交基数目是M的秩R(M)小于原属性数d。
于是,度量学习学得的结果可得到降维矩阵P用于降维。