注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

行走的馒头

Stay Hungry, Stay Foolish

 
 
 

日志

 
 

十五、Dimensionality Reduction  

2012-10-09 00:04:52|  分类: 统计学习初探索 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

    高维数据通常有很多冗余的信息,通常可以把高维的数据映射到低维的流形上,注意一维的流形是一条光滑的曲线,二维的流形则是光滑的曲面。这样,在低维的流形上就能够比较清晰的反应数据的特征和数据之间的关系,并且容易让人理解。在supervised learning中,Fisher Linear Discriminative Analysis就是通过类内的variance和类间中心点的距离把高维数据投影到低维空间上去。在unsupervised learning,我们可以通过PCA,Principal Curve,Self-Organizing Maps来实现。其中PCA等是把数据线性地投影到新的子空间中去,Principal Curve等则通过非线性的方式映射。

 

Principal Component Analysis

    PCA,也被称之为Karhunen-Loeve transform,是一种被广泛采用的技术,可以用来实现dimensionality reduction,数据的稀疏表示以及feature selection和data visualization。

    PCA可以从两个角度来理解,最终都会殊途同归。两种方式都是把数据空间投影到一个子空间中,这个子空间的基都是正交的,这个子空间被称之为principal subspace。第一种方式从数据variance的角度来看待的,保证数据投影到子空间的variance最大化,。另外一种方式则从距离这个角度处罚,保证投影距离最小化,投影距离可表示所有原数据点到投影点的距离之和。来分别看看这种方式的推导

 

Maximum Variance Formulation

    我们的目的是把原来 维的数据投影到正交的维子空间上,并且保证这些投影数据点的variance最大化。首先考虑的情况,这个子空间的方向不妨用一个单位向量来表示,其中。此时每个数据点的投影点可以表示为。这时这些投影点的variance可以表示为

其中是原数据的sample covariance matrix,表示为

这时目标就变为,使用Lagrange multiplier来求解,就需要最大化。对求偏导,就得到。此时可以看出,其实就是的特征向量。在两边同时左乘,就得到。所以我们只需要使为最大特征值所对应的特征向量,就会取得最大的值,对应最大的特征值,此时的variance就会最大。此时的被称之为first principal component。

    广而言之,对于接下来的principal component,也采取类似的方法,并且保证每一个principal component要与前面的principal component正交。这样一来,如果把数据投影到维的子空间上,要保证投影带点的variance最大,只需要求解covariance matrix 的从大到小的前个特征值,其所对应的特征向量组成特征空间

    对于的matrix进行完全的特征分解所需要的时间复杂度为,如果只计算前个特征值所对应的特征向量,所需时间复杂度可以降为

 

Minimum-Error Formulation

    我们定义维空间上的一组单位正交基为,满足。因为这组正交基是完备的,所以在维空间上的任意一个数据点都可以表示为。根据这些基正交的特性,我们容易得到。这时可以重新表示为。因为目标是把数据投影到维的子空间上,所以不妨用前个正交基来构成这个子空间。所以每个数据点此时被近似表示为

。可以看到,不同的数据点对应的是不相同的,而都是相同的。由于目的是原数据点和近似点尽可能的接近,使用欧式距离作为评价标准,我们目标就是最小化

通过求解可以得到,这时可以得到

此时,目标函数可以改写为

 (15.1)

此时我们需要根据及其限制条件来最小化

不妨先考虑最简单的情况,此时,目标位。通过Lagrange multiplier方法可以看出就是较小的特征值所对应的特征向量。因为正交,所以明显就是较大值所对应的特征向量,此时principal subspace就是

    对于任意,通过对(15.1)使用Lagrange multiplier方法可以得到,。所以此时的前个最小的的特征值所对应的特征向量,相应的,principal space就是前个最大的特征值所对应的特征向量形成的子空间。

    虽然在通常情况下,考虑,但是上的所有的推导和结论都是成立的,这时其实没有进行dimensionality reduction,只是相当于把原来的基进行了一下旋转,转到principal components所对应的位置而已。

 

Probabilistic PCA

    上面提到,PCA是把数据线性的投影到低维的子空间上,换个角度,我们可以通过隐变量和概率的形式来看待PCA,这就是所谓的Probabilistic PCA。

    Probabilistic PCA是一种较为简单的linear-Gaussian模型,其中的marginal和conditional distribution都是高斯的。这里,我们首先假设维的principal subspace中的隐变量。服从高斯分布,并且条件概率也服从高斯分布。其中可表示为可表示为

    容易看出,此时观察到的维数据相当于把维空间上的隐变量进行线性转化后在加上一个高斯噪声,可表示为(15.2)

下面是这个模型的一个简单的示意图

    现在我们需要使用maximum likelihood方法来估计这些参数。其中边缘分布可以表示为,因为这是一个linear-Gaussian模型,其中都是高斯分布的,所以可以表示为。其中是一个的matrix,可表示为,这是通过(15.2)得到的,表示如下

    所以此时中的参数包括了。但是注意这里存在一个问题,假设是一个正交矩阵,并且令。因为有,所以。因此,容易看出,求解得到的并不是唯一的,用不同的正交矩阵对其进行旋转都不会对结果造成影响。

 

Maximum likelihood PCA

    通过上面的分析,可以得到似然函数表示如下

容易求解得到,把其带入似然函数得到

其中是数据的sample covariance matrix。虽然这个式子很复杂,但是幸运的是其有closed-from solution,可表示为是一个的矩阵,其中列向量是的前个最大特征值所对应的特征向量,是一个对角矩阵,对应于的前个最大特征值。是任意的的正交矩阵。这里可以看出的列向量定义了PCA中的principal subspace。的估计为

    通常情况下,为了简便,我们可以设置,但是如果不是通过这种闭形式得到解析解,而是通过使用梯度下降等数值算法或者EM算法来求解,那么得到的的列向量其实很可能不是正交的了,那么此时通常都任意设定。

    可以看到,如果,那么此时

这样我们就得到对高斯分布的一个标准的最大似然估计,用sample covariance去估计covariance matrix。

    传统的PCA可以看做数据从高维投影到低维,相反,Probabilistic PCA则可以看作把数据从低维的隐变量所处的空间映射到高维的空间。Probabilistic PCA最大的优势在于用较少的参数就可以反映高维空间中数据的主要的相关性。一个标准的高斯模型共有个参数,其中表示covariance matrix中的参数个数,表示中心点的参数个数。在高维空间中,往往非常大,这时参数数目也急剧增加。如果我们把covariance matrix设置为对角矩阵,这时其只有个独立的参数,此时总的参数个数与呈线性关系,但这时假定了每个特征维度都是相互独立的,不能很好地反映的他们之间的相关性。而Probabilistic PCA则用一种优雅的方式解决了这个问题,它能够反映最主要的个相关性关系并且保证参数数目与呈线性关系。因为依赖于,而是一个的矩阵,所以中共有个参数。又因为的关系,中有一些冗余的参数,因为是正交矩阵,所以中共有个独立的参数,所以中独立参数的数目为

 

EM algorithm for PCA

    虽然前面看到probabilistic PCA有闭形式的解,但是我们也可以通过使用EM算法来求解,当数据是非常高维的时候,使用EM求解可以减小计算上的开销,因为此时不需要计算非常耗时的sample covariance matrix 。另一方面,EM还可以被用来求解后面会提到的factor analysis模型,那里就不存在闭形式的解了。

    似然函数表示为,容易得到

在E-step中,我们根据上一次迭代中产生的参数估计隐变量的后验分布,

    在M-step中,根据当前隐变量的后验分布,估计新的参数的值。

    通常,计算sample covariance matrix需要的开销,而EM算法只需要的开销,当时,EM算法非常有优势。

 

Factor Analysis

    Factor analysis也是一种linear-Gaussian的隐变量模型,跟probabilistic PCA非常之像。其跟probabilistic PCA的唯一不同之处在条件概率处的covariance matrix有所不同,用diagonal matrix covariance取代了probabilistic PCA中的isotropic covariance。Factor analysis的条件概率表示为。其中是一个的对角矩阵。在factor analysis中,的列向量捕获观察数据之间的相关性,被称之为factor loadings,中的每一个元素代表特征每一维度上独立的noise,被称之为uniquenesses。

    同probabilistic PCA类似,可以表示为,其中。这里类似于probabilistic PCA,在隐变量空间上用一个正交矩阵进行旋转不会产生任何的影响。

    同样的,我们使用maximum likelihood来求解,因为此时没有闭形式的解,所以通过EM来求解。在E-step中,后验概率可解得如下

在M-step中,可得到新估计的参数如下

 

Kernel PCA

    首先我们把数据中心化,使得。然后考虑一个非线性映射把数据映射到一个维的空间上去,注意这里可能,映射得到的数据点为。我们可以在这个新的维空间上进行标准的PCA。如果假设在新的空间上这些数据的中心点也为,那么这时的sample covariance matrix表示为

这时的特征分解可表示为。即

(15.3)

所以可以表示为的线性组合,即。把其带回到(15.3),得到

 (15.4)

在(15.4)两边同时乘上,写成核函数的形式,即

,得到下面的式子

写成矩阵的形式即为,两边都去掉一个,得到

,通过特征分解即可求得。此时数据点的投影值就可以表示为

    到目前为止,都假设了映射后的数据的中心为,如果事实不是这样,需要进行中心化,即。此时核函数相对应的Gram matrix就可以表示为

用矩阵表示为

 

Independent Component Analysis

    在factor analysis中提到,隐变量是高斯分布的,这里ICA考虑隐变量不是高斯分布的情况,其假设个特征是独立的,所以有

。(15.5)

    为了理解这个模型,考虑这样一个应用。在某个房间里,有两个人同时对着两个麦克风说话,这时每个麦克风记录的信号都是两个人的声音信号的线性组合。这里假设我们能够观察到的数据是每个麦克风的信号。可以这样来建模,用两个独立的隐变量来分别表示两个人发出的信号,所以总的隐变量是这两个隐变量组成的一个二维向量,其概率密度可用(15.5)来表示。而我们观察到的麦克风的信号是这个总的隐变量的线性转化。给定一些数据,我们就可以使用maximum likelihood的方法来求解。更一般的,这种模型还可以使用于在一个很喧闹的环境中过滤掉背景噪声等场景。

    通常,隐变量可以设置成下面形式的分布

,相比于高斯分布,它有一个更heavy的尾巴。ICA的求解类似于factor analysis,用maximum likelihood和EM算法来求解。

 

Principal Curves

    在PCA中,principal component line是特征值最大的特征向量对应的那条直线,描绘了对数据最好的线性近似。而Principal curve则是一条一维下的光滑的曲线,在非线性下近似描述数据。如果原来的数据空间为,令表示以为参数在下的一条光滑的曲线。注意这里是一个向量函数,一共有维,每一维都对应着以为参数的smooth function。令表示这条曲线上距离最近的那个点,即投影到曲线上的那个点。如果是一条principal curve,其必须满足下面的条件:所有那些投影到的那些点的平均值等于,这是一种满足对称美的限制,可表示为,用代表了所有投影到它上面的那些数据点。这个限制也被称之为满足self-consistency属性。下面是principal curve的一个示意图

    为了找到一条principal curve ,通常采用下面的迭代步骤

    在步骤(a)中,是固定的,找到曲线使得self-consistency得到保证,在步骤(b)中,曲线是固定的,找到每个数据在曲线上的投影点。这个算法最开始可以设置曲线为linear principal component,然后不断迭代直至最后收敛。在步骤(a)中,前面提到过的scatterplot smoother等方法都可以用来在每个特征上拟合曲线。

    类似于principal curve,principal surface是一个二维的曲面,可表示为,拟合的方法类似于principal curve,只是在步骤(a)中用二维的曲线去拟合。下面是principal surface的一个示意图

 

Self-Organizing Map

    SOM可以看作是带限制条件的K-means。在K-means中,prototypes是每个cluster的中心点。在SOM中,把prototypes映射到特征空间中一维或者二维的流形上,这个流形也被称之为constrained topological map。

不妨考虑二维的情形。可以把数据的个prototypes,,映射到一个二维的格子上去,这个prototypes这时也可以用这个二维格子的坐标来标识,其中,此时。这个二维格子平面可以通过用前两个principal component组成的平面来得到,然后把其均匀的划分成的格子。这里每个格子对应于一个prototype,相应的在数据空间中也可以找到这些prototypes对应的值。每来一个数据,我们这样来更新这些prototypes在数据空间中的位置:首先找到距离最近的那个prototype,这里距离的计算当然是在数据空间上进行的。然后找到的所有邻居,对每个邻居在数据空间中的位置进行更新,表示为

 (15.6)

注意这里的所有邻居是在二维格子上找到的,因为每个prototype在二维格子上都有一个坐标,可以根据这个坐标来找到它的所有邻居,这里可以使用欧拉距离作为距离标准,然后需要定义一个阈值来筛选其他的prototypes是不是这个prototype的邻居。注意这里是其本身的邻居,即它所有的邻居里包括它自己。(15.6)中的称之为学习速率。可以看到,通过(15.6),使得这些prototypes能够尽量在数据空间中靠近样本点,另一方面也使得这些prototypes在这个光滑的二维平面的保持紧密的联系。

    SOM的performance取决于学习速率和distance threshold 。通常来说,在迭代过程中,控制从1逐渐递减到0,而递减到1,可以看作是一个tuning parameter。

    当然,SOM很多的变种,主要体现在prototype位置的更新上,比如可以使用下面的形式。其中是一个递减的函数。可以看到,如果取得足够小,每次更新过程中,只有本身会发生变化,这时其实SOM就退化为K-means的一个on-line版本,最终会收敛到K-means的局部最优上。

    下面是SOM的一个示意图,左边是最初的情形,右边是收敛时的情形。其中较大的空心圆圈表示prototype,有颜色的点表示数据点。每个prototype里的数据点表示这些数据点在数据空间中离这个prototype最近。

 

Multidimensional Scaling

    前面SOMprincipal curve把高维数据投影到低维的流形上,而Multidimensional ScalingMDS)的目标类似,只是所采取的策略有所不同而已。

    MDS的目标同样是把数据映射到低维空间上去,其需寻找在维空间上映射的一些点,使得下面的目标函数最小化。

这个目标函数又叫做stress function

可以看到MDS只需要distance matrix,并不需要原数据点MDS要做的就是在低维空间中尽可能保存高维空间中数据的distance关系。可以用梯度下降法来求解MDS。比如最初给赋予一个初值,然后用梯度下降直至到达极值点为止。

    当然可以对MDS稍作变形,得到优化的目标为

。跟前面的标准相比较,此时更加注重保存较小的distance关系。

    MDS把高维的数据用低维的坐标系统来表示,在SOMPrincipal curve中则更进一步,能够把高维数据用低维的坐标系统映射到低维的流形上。在SOMPrincipal curve中,在高位空间中距离很近的数据点在低维的流形上也离得很近,但是在高维中距离很远的点也可能在流形中距离很近,而MDS则避免了这种情形。

 

Local Methods

    前面的这些方法都是都全局上考虑进行特征空间的转换,下面考虑一些local的方法。

Local Linear embedding

    这种算法用每个数据点的邻居的线性组合来估计这个数据点。算法如下

    Step 1.对于原数据空间的每个数据点,采用欧拉距离找到它的的K-nearest neighbors    

    Step 2.对于每个数据点,使用它的K-nearest neighbors去估计,可得到。其中满足

。为了保证解的唯一性,我们必须保证

    Step 3.根据Step 2.中得到的的值,把数据投影到维的空间上,使下面的目标函数最小化。写成矩阵的形式,可以表示为

    最终的解可表示为矩阵的最小的个特征值(0以外)所对应的特征向量。

 

Local MDS

    首先构造一个集合,一个数据点对中如果数据点在数据点K-nearest neighbors中。这时stress function被修改为

这里是一个很大的常数,表示权重,通常设置为。这种算法考虑到对于不是neighbor的那些点对,尽量减少他们对stress function的影响。当时,stress function变为

,其中。其中第一项希望尽量保持数据的local结构,第二项使不在中的那些点对离得尽量远。下面是MDSlocal MDS的一个示意图。其中橙色得点表示原来的样本点,蓝色的点表示投影后的点。可以看到右图更好的保存了local的结构。

 

 


  评论这张
 
阅读(2390)| 评论(3)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017