数据铺子使用R的统计学习：算法和实践（一）：MDS（2）
###因为表示数学符号不方便，正文中一般用[ ]表示元素下标，用( )表示矩阵或函数，请大家
####按文意甄别
一个简单的例子和一些术语
一个经典的例子。关于MDS的易于理解的经典案例往往来自地理方面(本例最早来自文献[4]）：
关于美国十个城市间飞行里程的数据。这十个城市是：亚特兰大（Atlanta）、芝加哥（Chicago）、丹佛（Denver）、休斯顿（Houston）、洛杉矶（Los Angeles）、迈阿密（Miami）、纽约（New York）、旧金山（Sanfran）、西雅图（Seattle）和华盛顿（Wash•DC）。用MDS分析这个数据集，绘出一张“真实”的地图。数据取自http://lem.gdcc.edu.cn/jiaox/epd/contents/softstudy/sas/jlfx01-left1.HTM。
把数据按照表格中的形式整理为csv文件。使用R函数cmdscale（stats包，使用经典标度）
city<-read.csv('airline.csv',header=TRUE)
city1<-city[,-1]#这个数据集的第一列是名字，先把它去掉
for (i in 1:9)
for(j in(i+1):10)
city1[i,j]=city1[j,i] #把上三角部分补足
rownames(city1)<-colnames(city1) #再把行名加回来
city2<-as.dist(city1, diag = TRUE, upper = TRUE)#转换为dist类型
city3<-as.matrix(city2) #转化为矩阵
citys<-cmdscale(city3,k=2) #计算MDS，为可视化，取前两个主坐标plot(citys[,1],citys[,2],type='n') #绘图
text(citys[,1],citys[,2],labels(city2),cex=.7)#标上城市名字
看看图和真实的地图方向(东西海岸)是反的阿，没关系，修改一下：
plot(-citys[,1],citys[,2],type='n')
text(-citys[,1],citys[,2],labels(city2),cex=.7)
现在就是真实地图的结构了。
下面用ggmap包画张地图，对比一下：
MDS建立于实体(entity)的成对比较之上。实体的接近程度称为“邻近”（Proximity），
邻近可以是定量的，如真实实体的物理距离，对顺序尺度（ordinal scale）的主观判断，也可以是定性的，如在心理测量中关于相似或者相异程度的主观评分。
设δ[i，j]表示i，j两个实体的相异程度，对全部的n个实体X[1]…X[n]，我们可以得到矩阵
Δ =（δ[i，j]），这称为距离矩阵（Proximity Matrices）。这个矩阵是通常写为一个下三角的非负的矩阵（主对角线一般为0）。在可度量（metric）距离之下，满足三角不等式。（注：在某些心理测量实验中，距离矩阵可能是非对称的，一种调整的方法是取对角线两侧的对应元素均值，使之对称）。关于距离矩阵的构建在某些问题里可能相当复杂。可参考[2]。
MDS的目的是寻找一个低维（ t维）空间，其上对应n个实体的点为Y[1]，…,Y[n]，
他们的距离d[i,j]与δ[i，j]尽量接近。Y 称为MDS的一个解，在进行可视化时也可以称为拟合构图。所以，MDS是在寻找关于解的优化算法。
2.经典标度法（Classical Scaling）
经典标度法是MDS系列算法中最早出现的一种。尽管经典标度法可视为最小二乘标度法在某种情形下的一个特例，探讨经典标度法的算法仍有助对MDS的理解。
关于经典标度法的算法如下：（读书笔记嘛，直接截取书里边的内容）
关于算法的细节可以参考[1]，[3]。
说明：B = HAH，来源于对观察距离δ[i，j]的平方和展开。这个算法就是特征值分解，其思想和主成分分析（PCA）非常相似。在欧氏距离之下，这种算法求得的主坐标（principal coordinates）相当于PCA中前t个主成分的得分。
关于维度的选取
一种常用方法是按照矩阵B的特征值的结构来选择维数。（类似于PCA对主成分的选择）把正特征值按从大到小排列，变得稳定即可。当然处于可视化的考虑，一般都是选择维数为2或3。
下面继续美国城市航线的例子，看看经典标度的效果：
a<-cmdscale(city3, k = 2, eig = TRUE)#结果是一个列表
#观察其特征值（矩阵B的特征值）：
a$eig
[1] 9.509732e+06 1.719867e+06 4.151052e+05 2.950924e+03 1.560345e+03 -1.164153e-10 -2.628176e+03 -3.497864e+03 -2.268600e+04 -5.233140e+05
#绘原始距离和估计距离的散点图
city2d<-data.frame(a［1］)#把前两个主坐标取出
city2d11<-dist(city2d, method = "euclidean",diag=FALSE)#生成距离矩阵
city2dv1<-as.vector(city2d11)
city2<-as.dist(city1, diag = FALSE)
city2v<-as.vector(city2)
c<-data.frame(city2v,city2dv1)
library(ggplot2)
p<-ggplot(data=c,aes(x=city2v,y=city2dv1))+
geom_point(pch=19,colour='red',size=2,alpha=.6)+
stat_smooth(method=lm)
update_labels( p,list(x="Observed Distance",y="Estimated Distance"))
#绘残差图
res<-c[,1]-c[,2]
d=data.frame(res,x=c(1:45))
ggplot(data=d,aes(y=res,x=x))+
geom_point(pch=19,colour='red',size=2,alpha=.6)+
geom_text(data=d,colour="black",aes(x=x,y=res+10,label=x,fontface=1),size=3)
得到原始距离和由前2个主坐标得到的拟合距离的散点图和残差图,拟合的效果还可以。明显的过拟合和拟合不足的点基本都和丹佛有关，哪位熟悉美国航线的给解释一下？
参考：
[1] Modern Multivariate Statistical Techniques（第13章）
http://book.douban.com/subject/3649744/
[2] Modern Multidimensional Scaling
http://book.douban.com/subject/2852629/
[3]方开泰，实用多元统计分析（第12章）
[4]Kruskal JB, Wish M (1978). Multidimensional Scaling, volume 07-011 of Sage University Pa-per Series on Quantitative Applications in the Social Sciences. Sage Publications, Newbury
Park.
####按文意甄别
一个简单的例子和一些术语
一个经典的例子。关于MDS的易于理解的经典案例往往来自地理方面(本例最早来自文献[4]）：
关于美国十个城市间飞行里程的数据。这十个城市是：亚特兰大（Atlanta）、芝加哥（Chicago）、丹佛（Denver）、休斯顿（Houston）、洛杉矶（Los Angeles）、迈阿密（Miami）、纽约（New York）、旧金山（Sanfran）、西雅图（Seattle）和华盛顿（Wash•DC）。用MDS分析这个数据集，绘出一张“真实”的地图。数据取自http://lem.gdcc.edu.cn/jiaox/epd/contents/softstudy/sas/jlfx01-left1.HTM。
把数据按照表格中的形式整理为csv文件。使用R函数cmdscale（stats包，使用经典标度）
city<-read.csv('airline.csv',header=TRUE)
city1<-city[,-1]#这个数据集的第一列是名字，先把它去掉
for (i in 1:9)
for(j in(i+1):10)
city1[i,j]=city1[j,i] #把上三角部分补足
rownames(city1)<-colnames(city1) #再把行名加回来
city2<-as.dist(city1, diag = TRUE, upper = TRUE)#转换为dist类型
city3<-as.matrix(city2) #转化为矩阵
citys<-cmdscale(city3,k=2) #计算MDS，为可视化，取前两个主坐标plot(citys[,1],citys[,2],type='n') #绘图
text(citys[,1],citys[,2],labels(city2),cex=.7)#标上城市名字
看看图和真实的地图方向(东西海岸)是反的阿，没关系，修改一下：
plot(-citys[,1],citys[,2],type='n')
text(-citys[,1],citys[,2],labels(city2),cex=.7)
现在就是真实地图的结构了。
 |
下面用ggmap包画张地图，对比一下：
 |
MDS建立于实体(entity)的成对比较之上。实体的接近程度称为“邻近”（Proximity），
邻近可以是定量的，如真实实体的物理距离，对顺序尺度（ordinal scale）的主观判断，也可以是定性的，如在心理测量中关于相似或者相异程度的主观评分。
设δ[i，j]表示i，j两个实体的相异程度，对全部的n个实体X[1]…X[n]，我们可以得到矩阵
Δ =（δ[i，j]），这称为距离矩阵（Proximity Matrices）。这个矩阵是通常写为一个下三角的非负的矩阵（主对角线一般为0）。在可度量（metric）距离之下，满足三角不等式。（注：在某些心理测量实验中，距离矩阵可能是非对称的，一种调整的方法是取对角线两侧的对应元素均值，使之对称）。关于距离矩阵的构建在某些问题里可能相当复杂。可参考[2]。
MDS的目的是寻找一个低维（ t维）空间，其上对应n个实体的点为Y[1]，…,Y[n]，
他们的距离d[i,j]与δ[i，j]尽量接近。Y 称为MDS的一个解，在进行可视化时也可以称为拟合构图。所以，MDS是在寻找关于解的优化算法。
2.经典标度法（Classical Scaling）
经典标度法是MDS系列算法中最早出现的一种。尽管经典标度法可视为最小二乘标度法在某种情形下的一个特例，探讨经典标度法的算法仍有助对MDS的理解。
关于经典标度法的算法如下：（读书笔记嘛，直接截取书里边的内容）
 |
经典标度算法 |
关于算法的细节可以参考[1]，[3]。
说明：B = HAH，来源于对观察距离δ[i，j]的平方和展开。这个算法就是特征值分解，其思想和主成分分析（PCA）非常相似。在欧氏距离之下，这种算法求得的主坐标（principal coordinates）相当于PCA中前t个主成分的得分。
关于维度的选取
一种常用方法是按照矩阵B的特征值的结构来选择维数。（类似于PCA对主成分的选择）把正特征值按从大到小排列，变得稳定即可。当然处于可视化的考虑，一般都是选择维数为2或3。
下面继续美国城市航线的例子，看看经典标度的效果：
a<-cmdscale(city3, k = 2, eig = TRUE)#结果是一个列表
#观察其特征值（矩阵B的特征值）：
a$eig
[1] 9.509732e+06 1.719867e+06 4.151052e+05 2.950924e+03 1.560345e+03 -1.164153e-10 -2.628176e+03 -3.497864e+03 -2.268600e+04 -5.233140e+05
#绘原始距离和估计距离的散点图
city2d<-data.frame(a［1］)#把前两个主坐标取出
city2d11<-dist(city2d, method = "euclidean",diag=FALSE)#生成距离矩阵
city2dv1<-as.vector(city2d11)
city2<-as.dist(city1, diag = FALSE)
city2v<-as.vector(city2)
c<-data.frame(city2v,city2dv1)
library(ggplot2)
p<-ggplot(data=c,aes(x=city2v,y=city2dv1))+
geom_point(pch=19,colour='red',size=2,alpha=.6)+
stat_smooth(method=lm)
update_labels( p,list(x="Observed Distance",y="Estimated Distance"))
#绘残差图
res<-c[,1]-c[,2]
d=data.frame(res,x=c(1:45))
ggplot(data=d,aes(y=res,x=x))+
geom_point(pch=19,colour='red',size=2,alpha=.6)+
geom_text(data=d,colour="black",aes(x=x,y=res+10,label=x,fontface=1),size=3)
 |
散点图 |
 |
残差图 |
得到原始距离和由前2个主坐标得到的拟合距离的散点图和残差图,拟合的效果还可以。明显的过拟合和拟合不足的点基本都和丹佛有关，哪位熟悉美国航线的给解释一下？
参考：
[1] Modern Multivariate Statistical Techniques（第13章）
http://book.douban.com/subject/3649744/
[2] Modern Multidimensional Scaling
http://book.douban.com/subject/2852629/
[3]方开泰，实用多元统计分析（第12章）
[4]Kruskal JB, Wish M (1978). Multidimensional Scaling, volume 07-011 of Sage University Pa-per Series on Quantitative Applications in the Social Sciences. Sage Publications, Newbury
Park.
> 我来回应