降维是机器学习中很有意思的一部分,很多时候它是无监督的,能够更好地刻画数据,对模型效果提升也有帮助,同时在数据可视化中也有着举足轻重的作用。
一说到降维,大家第一反应总是PCA,基本上每一本讲机器学习的书都会提到PCA,而除此之外其实还有很多很有意思的降维算法,其中就包括isomap,以及isomap中用到的MDS。
ISOMAP是‘流形学习’中的一个经典算法,流形学习贡献了很多降维算法,其中一些与很多机器学习算法也有结合,但上学的时候还看了蛮多的机器学习的书,从来没听说过流形学习的概念,还是在最新的周志华版的《机器学习》里才看到,很有意思,记录分享一下。
流形学习
流形学习应该算是个大课题了,它的基本思想就是在高维空间中发现低维结构。比如这个图:
这些点都处于一个三维空间里,但我们人一看就知道它像一块卷起来的布,图中圈出来的两个点更合理的距离是A中蓝色实线标注的距离,而不是两个点之间的欧式距离(A中蓝色虚线)。
此时如果你要用PCA降维的话,它 根本无法发现这样卷曲的结构 (因为PCA是典型的 线性降维 ,而图示的结构显然是非线性的),最后的降维结果就会一团乱麻,没法很好的反映点之间的关系。而流形学习在这样的场景就会有很好的效果。
我对流形学习本身也不太熟悉,还是直接说算法吧。
ISOMAP
在降维算法中,一种方式是提供点的坐标进行降维,如PCA;另一种方式是提供点之间的距离矩阵,ISOMAP中用到的MDS(Multidimensional Scaling)就是这样。
在计算距离的时候,最简单的方式自然是计算坐标之间的欧氏距离,但ISOMAP对此进行了改进,就像上面图示一样:
1.通过kNN(k-Nearest Neighbor)找到点的k个最近邻,将它们连接起来构造一张图。
2. 通过计算同中各点之间的最短路径,作为点之间的距离 i j
放入距离矩阵 D
3. 将 D 传给经典的MDS算法,得到降维后的结果。
ISOMAP本身的 核心就在构造点之间的距离 ,初看时不由得为其拍案叫绝,类似的思想在很多降维算法中都能看到,比如能将超高维数据进行降维可视化的t-SNE。
ISOMAP效果,可以看到选取的最短路径比较好地还原了期望的蓝色实线,用这个数据进行降维会使流形得以保持:
ISOMAP算法步骤可谓清晰明了,所以本文主要着重讲它中间用到的MDS算法,也是很有意思的。
经典MDS(Multidimensional Scaling)
如上文所述,MDS接收的输入是一个距离矩阵 D
,我们把一些点画在坐标系里:
如果只告诉一个人这些点之间的距离(假设是欧氏距离),他会丢失那些信息呢?
a. 我们对点做平移,点之间的距离是不变的。
b. 我们对点做旋转、翻转,点之间的距离是不变的。
所以想要从 D
还原到原始数据 是不可能的,因为只给了距离信息之后本身就丢掉了很多东西,不过不必担心,即使这样我们也可以对数据进行降维。
我们不妨假设:
是一个 n × 的矩阵,n为样本数,q是原始的维度
计算一个很重要的矩阵 B :
= ( n × n ) = ( ) ( ) ( 是 一 组 正 交 基 )
可以看到我们通过 对 做正交变换并不会影响 B 的值,而 正交变换刚好就是对数据做旋转、翻转操作的 。
所以如果我们想通过 B 反算出 ,肯定是没法得到真正的 , 而是它的任意一种正交变换后的结果。
B中每个元素的值为:
b i j = ∑ k = 1 x i k x j k
计算距离矩阵 D ,其中每个元素值为:
= ( x i ? x j ) 2 = ∑ k = 1 ( x i k ? x j k ) 2 = ∑ k = 1 x 2 i k + x 2 j k ? 2 x i k x j k = b i i + b j j ? 2 b i j \tag{dij_square}\label{dij_square}
这时候我们有的只有 D ,如果能通过 D 计算出 B ,再由 B 计算出 ,不就达到效果了吗。
所以思路是:从D->B->X
此时我们要对X加一些限制,前面说过我们平移所有点是不会对距离矩阵造成影响的,所以我们就把 数据的中心点平移到原点 ,对X做如下限制(去中心化):
∑ i = 1 n x i k = 0 , o r a l l k = 1..
所以有
∑ j = 1 n b i j = ∑ j = 1 n ∑ k = 1 x i k x j k = ∑ k = 1 x i k ∑ j = 1 n x j k = 0
类似的
∑ i = 1 n b i j = ∑ i = 1 n ∑ k = 1 x i k x j k = ∑ k = 1 x j k ( ∑ i = 1 n x i k ) = 0
可以看到即 B 的任意行(row)之和以及任意列(column)之和都为0了。
设T为 B
的trace,则有:
∑ i = 1 n 2 i j = ∑ i = 1 n b i i + b j j ? 2 b i j = + n b j j + 0
∑ j = 1 n 2 i j = ∑ j = 1 n b i i + b j j ? 2 b i j = n b i i + + 0
∑ i = 1 n ∑ j = 1 n 2 i j = 2 n
得到B:根据公式 我们有:
b i j = ? 1 2 ( 2 i j ? b i i ? b j j )
而(根据前面算 ∑ n i = 1 2 i j , ∑ n j = 1 2 i j 和 ∑ n i = 1 ∑ n j = 1 2 i j 的公式可以得到)
b i i b j j 2 n = + 1 n ∑ j = 1 n 2 i j = + 1 n ∑ i = 1 n 2 i j = 1 n 2 ∑ i = 1 n ∑ j = 1 n 2 i j
所以
= ? 1 2 ( 2 i j ? b i i ? b j j ) = ? 1 2 ( 2 i j ? 1 n ∑ j = 1 n 2 i j ? 1 n ∑ i = 1 n 2 i j + 2 n ) = ? 1 2 ( 2 i j ? 1 n ∑ j = 1 n 2 i j ? 1 n ∑ i = 1 n 2 i j + 1 n 2 ∑ i = 1 n ∑ j = 1 n 2 i j ) = ? 1 2 ( 2 i j ? 2 i ? ? 2 ? j + 2 ? ? )
可以看到 2 i ? 是 D 2 行均值; 2 ? j 是列均值; 2 ? ? 是矩阵的均值。
这样我们就可以通过矩阵 D
得到矩阵 B 了
因为B是对称的矩阵,所以可以通过特征分解得到:
B = Λ ? 1 = Λ
在最开始我们其实做了一个假设, 即 D 是由一个 n × 的数据生成的,如果事实是这样的, D 会是一个对称实矩阵,此时得到的 B 刚好会有 个非0的特征值,也就是说 B 的秩等于 ,如果我们想还原 ,就选择前 个特征值和特征向量;如果想要达到降维的目的,就选择制定的 p 个( p < )。
此时我们选择前 p
个特征值和特征向量,(这一步和PCA里面很类似):
B ? = ? Λ ? ? ? ( n × p ) , Λ ? ( p × p )
所以有( Λ 是特征值组成的对角矩阵):
B ? = ? Λ ? 1 2 ? Λ ? 1 2 ? = ? ?
因此
? = ? Λ ? 1 2
如果选择 p = 的话,此时得到的 ? 就是原数据去中心化并做了某种正交变换后的值了。
MDS的例子
举个例子:拿美国一些大城市之间的距离作为矩阵传进去,简单写一写代码:
import numpy as np
import matplotlib.pyplot as plt
def mds(D,q):
D = np.asarray(D)
DSquare = D**2
totalMean = np.mean(DSquare)
columnMean = np.mean(DSquare, axis = 0)
rowMean = np.mean(DSquare, axis = 1)
B = np.zeros(DSquare.shape)
for i in range(B.shape[0]):
for j in range(B.shape[1]):
B[i][j] = -0.5*(DSquare[i][j] - rowMean[i] - columnMean[j]+totalMean)
eigVal,eigVec = np.linalg.eig(B)
X = np.dot(eigVec[:,:q],np.sqrt(np.diag(eigVal[:q])))
return X
D = [[0,587,1212,701,1936,604,748,2139,2182,543],
[587,0,920,940,1745,1188,713,1858,1737,597],
[1212,920,0,879,831,1726,1631,949,1021,1494],
[701,940,879,0,1374,968,1420,1645,1891,1220],
[1936,1745,831,1374,0,2339,2451,347,959,2300],
[604,1188,1726,968,2339,0,1092,2594,2734,923],
[748,713,1631,1420,2451,1092,0,2571,2408,205],
[2139,1858,949,1645,347,2594,2571,0,678,2442],
[2182,1737,1021,1891,959,2734,2408,678,0,2329],
[543,597,1494,1220,2300,923,205,2442,2329,0]]
label = ['Atlanta','Chicago','Denver','Houston','Los Angeles','Miami','New York','San Francisco','Seattle','Washington, DC']
X = mds(D,2)
plt.plot(X[:,0],X[:,1],'o')
for i in range(X.shape[0]):
plt.text(X[i,0]+25,X[i,1]-15,label[i])
plt.show()
最后画出来的图中,各个城市的位置和真实世界中的相对位置都差不多:
注意,这个例子中其实也有‘流形’在里面,因为我们的地球其实是一个三维,而城市间距离刻画的是在球面上的距离,所以最后如果你去看求出来的特征值,并不像前面说的那样只有q个非0的值。数据分析师培训
数据分析咨询请扫描二维码
CDA数据分析师在中国航信高科技产业园进行了面向测试度量的数据分析培训课程,培训人数近2 ...
2024-05-01CDA数据分析师走进深圳迈瑞生物医疗电子股份有限公司,在迈瑞总部展开了为期两天的培训,本次课程参训人员线上及线下近百人, ...
2024-05-01CDA数据分析师在合肥市对合肥阳光新能源科技有限公司开展了为期8天的企业内训。 合肥阳光新能源科技 ...
2024-05-01CDA数据分析师走进海尔大学,进行了《数据治理与数据中台建设的道与术》专题培训,培训现场爆满,近百人参加了此次培训。 ...
2024-05-01在中国银行苏州分行培训中心开始数据分析师培训,此次培训课程共10天内容,包括Excel、MySQL、概率论与数理统计、SPSS等内容, ...
2024-05-01从实际的业务需求出发,结合行业的典型应用特点,围绕实际的商业问题,探讨数据挖掘、机器学习模型在金融领域的应用,包括获客、信用评分、细分画像、交叉销售、反欺诈、违规识别、时序预测、运筹优化、流程挖掘九个方面,形成 ...
2024-05-01本次培训课程为线上+线下的模式,由于学员编程能力不一、部分学员没有编程基础,故提供统计学、python基 ...
2024-05-01华夏银行信用卡中心-机器学习培训 1、课程亮点 取材于业界一流企业和顶级咨询公司的行业实践;已经被证明是人人 ...
2024-05-01主 题:数据中台建设及数据分析应用主题分享 1. 数据中台市场洞察 2. 主流数据中台产品比较 3. 某企业数据中 ...
2024-05-01围绕“数据驱动”战略,全力打造我行 300 人数字化人才梯队,着力培养数字化管理人才、大数据专业团队 ...
2024-05-01在当今数据驱动的商业环境中,数据分析成为了企业决策的重要依据。通过对大量数据的收集、处理和分析,企业能够更好地理解市场 ...
2024-04-29在人工智能(AI)的世界里,提示词(Prompt)是一种强大的工具,它能够引导AI按照用户的需求产生特定的输出。本文将深入探讨AI ...
2024-04-29CDA立足未来职场,拓展前沿视野——对外经贸大学保险学院举办“三全育人大讲堂”分享行业最新动态。 ...
2024-04-294月2日,CDA数据分析师创始发起人兼协会理事长赵坚毅博士受邀在浙江万里学院举办了一场以“数字化能力在职场中的作用” ...
2024-04-29随机森林(Random Forests)现在机器学习中比较火的一个算法,是一种基于Bagging的集成学习方法,能够很好地处理分类和回归的问 ...
2022-12-23方差分析是数据分析中常用的一种统计分析方法,接下来让我们简单了解一下方差分析的基本思想和原理吧。 方差分析(Analysis ...
2022-12-23来源:关于数据分析与可视化 关于streamlit-aggrid 数据排序 表格样式的调整 数据 ...
2022-08-03作者:麦叔 定义 「把上面晦涩的概念汇成一句话就是:」 ❝ 回调函数就是一个被作为参 ...
2022-08-03现今,高学历人群日益增多,物以稀为贵的高学历光环淡去。无论本科生还是研究生,甚至博士生,求职竞争力都大不如前,就业压力越来越大。
2022-06-01某家企业10个人面试,有9个本科生……如何脱颖而出,除得体的举止和良好的沟通力外,证书成重要筹码,这也是很多人考证的关键所在。
2022-04-14