lle 解析
7页1、【转】 LLE 解析【转】 LLE 解析2011年07月08日数学建模案例分析的大作业用LLE算法,但是原作者网站上提供的源代码有些问题,主要是因为不同版本的Matlab,内置函数eigs返回的特征向量的顺序不同:老版本对应的特征值是升序,而新版本的是降序。 在这个问题中,0总是特征值,对应的特征向量为(1,1,1),这不是我们要的(如果把它放进来,则用它给swiss_roll数据集降维总得到一条粗直线。) 如果你用的是Matlab6.5,则应该把line 65的 Y = Y(:,2:d+1)*sqrt(N); 改为 Y = Y(:,n-d:n-1)*sqrt(N); 打了这个补丁之后,lle.m就可以正常工作了! 我认为LLE算法很漂亮,下面过一下它的设计与实现原作者的paper用lle做关键词即可在Google上搜到。 问题的提法: 给N个D维列向量X1,XN,希望通过映射得到N个d(D)维列向量Y1,YN,要求保持邻域关系:原来离的近的点,映射过来也近。 LLE算法的思想:如果原像Xi能够表示成他邻域内点的线性组合,则像Yi也应该用相同的组合系数表示成对应像点的线性组合。即:局部
2、线性嵌入。 算法骨架 1、求近邻:计算每个Xi的邻居集合Si 直接用2范数下的K近邻,其中K作为算法的参数 2、求权:改变组合系数W,极小化局部线性表出原像的方差 W为NN矩阵,Ei=Xi-jSiWijXj为D维残差向量,极小化E(W)=i|Ei|2,满足如下约束:归一化W行和为1、局部性对于任意i,Wij=0若j不属于Si 3、求像:改变Y1,YN,极小化用W重构Y1,YN的方差 Ei=Yi-jSiWijYj为d维残差向量,极小化E(Y)=i|Ei|2 算法实现细节 1、求近邻 X为D行N列的矩阵,X的第j列为输入向量Xj 向量Xi到Xj的距离为sqrt(|Xi-Xj|2),得到距离方阵distance,然后每行排序,取前k个,对应原下标就是近邻点的编号。在Matlab中实现如下 X2 = sum(X.2,1); distance = repmat(X2,N,1)+repmat(X2,1,N)-2*X*X; sorted,index = sort(distance); neighborhood = index(2:(1+K),:); 这里充分利用了矩阵运算技巧避免了编程中使用循环,不
3、仅使代码紧凑,而且Matlab矩阵运算底层优化了性能。下面逐一解释 a)距离方阵 首先注意到这样一个事实|Xi-Xj|2=|Xi|2+|Xj|2-2,其中为内积。 X2 = sum(X.2,1)是1行N列的矩阵,第j个元素为X第j列的平方和,也就是|Xj|2。 repmat是平铺函数,repmat(X2,N,1)得到NN方阵,每行都是X2,同理repmat(X2,1,N)每列都是X2,是转置的意思。X*X得到NN方阵,(i,j)位置元素为。因此distance就是我们要的距离方阵的平方。 b)省去开平凡 因为我们只需要K近邻,而不需要具体的距离值,而开平方是严格单调函数,保序,因此我们可以省去开平方,节省了计算量。 c)反向索引 sort给矩阵每列排序,并返回置换前后下标的映射关系index:index(i,j)是distance第j列第i小的元素的下标。我们要每列前K小的下标,也就是每个Xi的K近邻。取2:(1+K)是因为Xi到自己的距离总是0最小,排除掉。 任意两个点至少做一次内积O(D),共O(N2)个点对,故复杂度:O(DN2) 2、求权 首先,因为对于任意i,Wij=0若j不
4、属于Si,故W只需要存K行N列即可。 其次,易见E(W)极小当且仅当每一求和项极小,因此我们依次计算W的每一列。固定列i,记x=Xi,w=W第i列,j=Xj,极小化|x-j=1.Kwjj|2,满足归一化约束 j=1.k wj=1。用矩阵语言描述:记B=( 1-x, k-x)为DK矩阵,G=BB为KK方阵(讲义中称之为Gram方阵,半正定,在摄动意义下总可以假设它非奇异),e=(1,1)为K维单位列向量,则问题化为 min |Bw|2也就是min wGw(二次型) s.t. ew=1 用拉格朗日乘数法求此条件极值:做辅助函数F(w,)= wGw-(ew -1) 对每个wj求偏导数令为0得Gw=e,反解出w=G-1e,代入到归一化约束得 =(eG-1e)-1,即最优解w=(eG-1e)-1 G-1e 实际操作时,我们先解线性方程组Gw=e,然后再将解向量w归一化,易见得到的就是上述最优解。 在Matlab中如下实现: W = zeros(K,N); for ii=1:N z = X(:,neighborhood(:,ii)-repmat(X(:,ii),1,K); %计算B C = z*z
《lle 解析》由会员小**分享,可在线阅读,更多相关《lle 解析》请在金锄头文库上搜索。
2020年高考真题——理科综合(全国卷Ⅲ)+Word版含答案
2021年绝味鸭脖策划书
2021年熟食店创业方案
2021年熟食店开店策划
2021年卤菜店创业计划书
2021年周黑鸭网络营销策划方案
东大21年1月考试《现代设计方法》考核作业
谈我国行政管理效率的现状及其改观对策(论文)
单证员考试-备考辅导-复习资料:无贸易背景信用证案分析.docx
土木工程毕业生答辩自述.docx
建筑学毕业后工作状态真实写照.doc
C#代码规范(湖南大学).doc
xx区食药监局2019年工作总结及2020年工作计划
2019年中医院药物维持治疗门诊工人先锋号先进事迹
2019年度xx乡镇林长制工作总结
2019年性艾科工作计划书
2019年人才服务局全国扶贫日活动开展情况总结
关于组工信息选题的几点思考
摘了穷帽子 有了新模样
2019年某集团公司基层党支部书记培训班心得体会
2024-04-08 33页
2024-04-08 10页
2024-04-08 25页
2024-04-08 12页
2024-04-08 10页
2024-04-08 21页
2024-04-08 40页
2024-04-08 34页
2024-04-08 28页
2024-04-08 28页