当前课程知识点:大数据机器学习 > 第十一章 降维与度量学习 > 2. 降维嵌入 > 2.降维嵌入
刚才我们介绍了KNN
其中有一个重要的假设
就是任意测试的样本X
附近任意小的δ距离范围内
也就是说
训练样本的采样密度足够大
称为密采样也就是dense sample
这一假设在实际问题中
究竟难不难满足呢
好 假设我们取δ=0.01
在一维属性的情况下
那么就需要一百个样本点
在归一化的属性取值范围内
在随机分布的情况下
每个样本点在其附近0.01的距离内
都能找到一个训练样本
此时
最近邻分类器的错误率
不超过贝叶斯最优分类器的错误率的两倍
然而
这仅是属性维数为一的情形
如果有更多的属性
那情况会发生怎样的变化呢
假如 我们属性维数为十
若还是要要求样本满足密采样的条件
则至少需要十平方的十次方
就等于10的20次方的样本数
而我们实际的问题中
属性维数往往成千上万
按照这样的情况所需的样本数目
是无法达到的天文数字
高维空间也会给距离计算带来很大的麻烦
例如
当维数很高的时候
甚至连计算内积都不再容易
在高维情形下
出现的数据样本稀疏 距离计算困难等问题
是所有机器学习方法共同的问题
那么
我们把这个就称为
维数灾难 curse of dimensionality
降维
也就是通过某种数学变换
将原始的高维属性空间
转变到一个低维的子空间
在这个子空间当中
样本密度大幅提高
这就可以满足刚才我们的假设
这样呢
距离的计算也变得更为容易
那么 为什么能降维呢
这是因为在很多时候
人们观测或收集到的数据样本
虽然是高维的
但与学习任务密切相关的
或许仅仅是某些低维分布
也就是说
高维空间当中的一个低维嵌入起到了关键的作用
下面我们介绍多维缩放方法
MDS是2001年提出的
它是一种经典的数据降维方法
同时呢也是一种数据的可视化方法
这个问题的起源是当我们仅能获得
物体之间的相似性矩阵时
如何由此来重构
它们的欧几里德的坐标
我们举一个例子
对一个国家的许多城市而言
假如
我们并不能确定它们的经纬度信息
却知道所有城市两两之间的距离
我们就可以通过MDS方法
将这些代表相似性的距离数据
呈现在二维坐标上
这里呢
我们主要介绍MDS
作为降维方法的原理和方法
它的主要特点是
原始空间样本距离
等于低维空间样本距离
也就是说
我们假定M个样本
在原始空间的距离矩阵为D∈Rm乘以m
它的第I行第J列的元素
distance为样本XI到XJ的距离
我们的目标是获得样本
在降维以后的d‘维空间
表示为Z∈Rd’乘以m
d’<=d
且任意两个样本
在DPM维空间中的欧式距离
等于原始空间中的距离
也就是||zi-zj||=distij
但是 在我们进行降维前
我们需要搞清以下这些问题
MDS接收的输入是一个距离矩阵D
也就是说
我们在只知道样本距离的情况下
为欧式距离去降维
那么 就会丢失一些信息
首先
对点做平移点之间的距离是不变的
其次
对点做旋转翻转点之间的距离也是不变的
我们令B=ZTZ∈Rm乘m
B为降维后样本的内积矩阵
bij=zTizj
则有dist平方ij=||zi||平方+||zj||平方-2zTizj
=bii+bjj-2bij
我们把降维后的样本在Z呢中心化
也就是∑i=1到m zi=0
显然矩阵B行与列的和均为0
也就是西格玛j=1到m
bij=西格玛i=1到m bij=0
由矩阵B的迹=trB=西格玛i=1到m bii
则可以得到这三个方程
三个方程的左边分别表示
原始距离矩阵D
各列元素的平方和
各行元素的平方和
以及矩阵中各元素的平方和
方程的右边呢是降维后样本的内积矩阵的元素值
我们把方程左边的这些矩阵D中
行或列的元素的平方和
用简化的形式进行表示
如下所示
这样我们就可以得到
降维后样本的内积矩阵
也就是矩阵的元素bij
可以由下式来进行表示
也就是用距离D中的行或列的元素
元素的平方和以及所有元素
平方和等值进行求取得到
有了这个内积矩阵以后呢
我们下一步进行
矩阵的特征值分解
重构特征向量矩阵
从而得到每一个降维后的向量
具体方法如下
对矩阵B作特征值分解
B=VλVT
其中λ=对角阵λ1λ2一直到λd
为特征值构成的对角矩阵
其中λ1大于等于λ2大于等于一直到λD
假定其中有 d*个非零的特征值
构成了λ*=对角阵λ1λ2一直到λd*
我们令 V*表示相应的特征向量矩阵
这样
降维后的特征向量矩阵就为
z=λ* 2分之一次方乘以 V转置
就属于Rd*乘以m
这样就得到了降维后的特征向量
一般来说
我们如果想获得低维子空间
最简单的呢
是对原始的高维空间进行线性变换
我们给定低维空间当中的样本
X = xi x2一直到xm属于Rd乘以m
变换以后呢
就得到了d‘维的空间中的样本
Z = WT乘以X
其中W属于Rd乘以d‘是变换矩阵
Z就属于Rd‘xm 是样本在新空间当中的表达
变换矩阵w是d’个低维向量
每个生成的降维后的向量
zi=WTxi
也就是第I个样本与这d’向量
分别作内积而得到的
如果WI和wj正交
则新坐标系是一个正交坐标系
此时呢
W就为正交变换
-1.机器学习定义和典型应用
-2.机器学习和人工智能的关系
-3.深度学习方法和其它人工智能方法的共性和差异
-4.机器学习和数据挖掘的关系
-5.机器学习和统计学习的关系
-6.机器学习的发展历程
-7.大数据机器学习的主要特点
-第一章 概述--7.大数据机器学习的主要特点
-1机器学习的基本术语
-2.监督学习
--2.监督学习
-3.假设空间
--3.假设空间
-4.学习方法三要素
-第二章 机器学习基本概念--4.学习方法三要素
-5.奥卡姆剃刀定理
-6.没有免费的午餐定理
-7.训练误差和测试误差
-8.过拟合与模型选择
-第二章 机器学习基本概念--8.过拟合与模型选择
-9.泛化能力
--9.泛化能力
-10.生成模型和判别模型
-1.留出法
--1.留出法
-2.交叉验证法
--2.交叉验证法
-3.自助法
--3.自助法
-4.性能度量
--4.性能度量
-5.PR曲线
--5.PR曲线
-6.ROC和AUC曲线
-第三章 模型性能评估--6.ROC和AUC曲线
-7.代价敏感错误率
-8.假设检验
--8.假设检验
-9.T检验
--9.T检验
-10.偏差和方差
--10.偏差和方差
-1.感知机模型
--1.感知机模型
-第四章 感知机--1.感知机模型
-2.感知机学习策略
-3.感知机学习算法
-第四章 感知机--3.感知机学习算法
-1.原型聚类描述
--1.原型聚类描述
-第五章 聚类--1.原型聚类描述
-2.性能度量
--2.性能度量
-第五章 聚类--2.性能度量
-3.1原型聚类 k均值算法
-3.2 原型聚类 学习向量算法
-3.3 原型聚类 密度聚类
-第五章 聚类--3.3 原型聚类 密度聚类
-3.4原型聚类 层次聚类
-1.综述
--1.综述
-2.概率图模型
--2.概率图模型
-第六章 贝叶斯分类器及图模型--2.概率图模型
-3.贝叶斯网络
--3.贝叶斯网络
-第六章 贝叶斯分类器及图模型--3.贝叶斯网络
-4.朴素贝叶斯分类器
-第六章 贝叶斯分类器及图模型--4.朴素贝叶斯分类器
-5.半朴素贝叶斯分类器
-第六章 贝叶斯分类器及图模型--5.半朴素贝叶斯分类器
-6.贝叶斯网络结构学习推断
-7.吉布斯采样
--7.吉布斯采样
-第六章 贝叶斯分类器及图模型--7.吉布斯采样
-开头
--开头
-1.决策树模型与学习基本概念
-2.信息量和熵
--2.信息量和熵
-第七章 决策树和随机森林--2.信息量和熵
-3.决策树的生成
--3.决策树的生成
-4.决策树的减枝
--4.决策树的减枝
-5.CART算法
--5.CART算法
-6.随机森林
--6.随机森林
-简介
--简介
-1.逻辑斯谛回归模型
-第八章 逻辑斯谛回归与最大熵模型--1.逻辑斯谛回归模型
-2.最大熵模型
--2.最大熵模型
-3.模型学习的最优化方法
-第八章 逻辑斯谛回归与最大熵模型--3.模型学习的最优化方法
-1.开头
--1.开头
-2.SVM简介
--2.SVM简介
-3.线性可分支持向量机
-第九章 SVM--3.线性可分支持向量机
-4. 凸优化问题的基本概念
-第九章 SVM--4. 凸优化问题的基本概念
-5.支持向量的确切定义
-6.线性支持向量机
-第九章 SVM--6.线性支持向量机
-svm相关拓展资料
-开头
--开头
-第十章 核方法与非线性SVM--开头
-1.泛函基础知识
--1.泛函基础知识
-第十章 核方法与非线性SVM--1.泛函基础知识
-2. 核函数和非线性支持向量机
-第十章 核方法与非线性SVM--2. 核函数和非线性支持向量机
-3. 序列最小最优化算法
-第十章 核方法与非线性SVM--3. 序列最小最优化算法
-开头
--开头
-1. k近邻学习
--1. k近邻学习
-第十一章 降维与度量学习--1. k近邻学习
-2. 降维嵌入
--2.降维嵌入
-第十一章 降维与度量学习--2. 降维嵌入
-3. 主成分分析
--3.主要成分分析
-第十一章 降维与度量学习--3. 主成分分析
-4. 核化线性降维
--4.核化线性降维
-5. 流型学习和度量学习
-1. 提升方法Adaboost算法
-第十二章 提升方法--1. 提升方法Adaboost算法
-2. Adaboost算法的训练误差分析
-3. Adaboost算法的解释
-4. Adaboost的实现
-第十二章 提升方法--4. Adaboost的实现
-adaboost拓展资料
-开头
--开头
-1. 问题提出
--1. 问题提出
-2. EM算法的引入
-3. EM算法的收敛性
-4. EM算法在高斯混合模型学习中的应用
-5. EM算法的推广
-第十三章 EM算法及混合高斯模型--3. EM算法的收敛性
-开头
--开头
-1. 计算学习理论的基础知识
-第十四章 计算学习理论--1. 计算学习理论的基础知识
-2. 概率近似正确学习理论
-3. 有限假设空间
--3.有限假设空间
-4. VC维
--4. VC维
-第十四章 计算学习理论--4. VC维
-5. 学习稳定性
--5. 学习稳定性
-开头
--开头
-1. 隐马尔科夫模型的基本概念
-第十五章 隐马尔可夫模型--1. 隐马尔科夫模型的基本概念
-2. 概率计算算法
-3. 学习算法
--3.学习算法
-第十五章 隐马尔可夫模型--3. 学习算法
-4预测算法
--4. 预测算法
-第十五章 隐马尔可夫模型--4预测算法
-开头
--开头
-1.概率无向图模型
-第十六章 条件随机场--1.概率无向图模型
-2.条件随机场的定义与形式
-第十六章 条件随机场--2.条件随机场的定义与形式
-3.条件随机场的计算问题
-4.条件随机场的学习算法
-5.条件随机场的预测算法
-第十六章 条件随机场--5.条件随机场的预测算法
-开头
--开头
-1.精确推断法:变量消去法和信念传播法
-第十七章 概率图模型的学习与推断--1.精确推断法:变量消去法和信念传播法
-2.近似推断法:MCMC和变分推断
-第十七章 概率图模型的学习与推断--2.近似推断法:MCMC和变分推断
-1.神经网络的发展历程
-2.神经网络的基本概念以及常见的神经网络(一)
-第十八章 神经网络和深度学习--2.神经网络的基本概念以及常见的神经网络(一)
-3.神经网络的基本概念以及常见的神经网络(二)
-4.玻尔兹曼机
--4.玻尔兹曼机
-5.深度学习
--5.深度学习
-第十八章 神经网络和深度学习--5.深度学习
-1. 深度学习简介和架构设计
-2. 计算图形式的反向传播算法
-3.深度学习的正则化方法(一)
-4.深度学习的正则化方法(二)
-1.深度学习的优化问题
-第二十章 深度学习优化方法--1.深度学习的优化问题
-2.神经网络优化的挑战
-3.神经网络的优化算法
-第二十章 深度学习优化方法--3.神经网络的优化算法
-4.相关策略
--4.相关策略
-第二十章 深度学习优化方法--4.相关策略