南京大学学报(自然科学版) ›› 2013, Vol. 49 ›› Issue (4): 403–410.

• •    下一篇

一种基于局部稀疏线性嵌入的降维方法及其应用

冷亦琴;张莉;杨季文;   

  • 出版日期:2013-08-30 发布日期:2013-08-30
  • 作者简介:苏州大学计算机科学与技术学院;
  • 基金资助:
    基金:国家自然科学基金(61033013);;江苏省自然科学基金(BK2011284,BK201222725);;江苏省青蓝工程;;苏州大学国家自然科学基金预研(SDY2011B09)

Ad i m e n s i o n - r e d u c t i o nm e t h o db a s e do n l o c a l l ya n ds p a r s e l y l i n e a r e m b e d d i n ga n d i t sa p p l i c a t i o n

L e n gY i - Q i n , Z h a n gL i , Y a n gJ i - W e n
  

  • Online:2013-08-30 Published:2013-08-30
  • About author:( S c h o o l o fC o m p u t e rS c i e n c ea n dT e c h n o l o g y , S o o c h o wU n i v e r s i t y , S u z h o u , 2 1 5 0 0 6 , C h i n a )

PDF (PC)

797

摘要： 局部线性嵌入(LLE)是一种非线性的降维方法.LLE方法采用的近邻邻域大小是全局一致的,而且如果近邻个数过大则可能会把非同一个线性空间的点选作为近邻点.本文对LLE方法进行了改进,提出了一种局部稀疏线性嵌入(LSLE)降维法.在LSLE方法中,用解0范数问题的正交匹配追踪(OMP)方法来解线性表示问题.每个样本点都可以用K个近邻点中最能表示该数据的几个样本点稀疏表示.实验表明,在有监督学习和无监督学习应用上,LSLE方法是可行的.

Abstract: M a n i f o l dl e a r n i n g h a sb e e n w i d e l yr e s e a r c h e di n m a c h i n el e a r n i n g , c o m p u t e rv i s i o n a n d p a t t e r n
r e c o g n i t i o n. A sac l a s s i c a lm e t h o do fm a n i f o l d l e a r n i n g , l o c a l l y l i n e a r e m b e d d i n g ( L L E ) a t t r a c t s a l o t o f a t t e n t i o n . T h e
L L Em e t h o dh a sm e r i t sw i t he a s y i m p l e m e n t i o na n ds m a l l c o m p u t i o n a l c o m p l e x i t y . T h eb a s i c i d e ab e h i n dt h eL L E
m e t h o d i s t h a t e a c hd a t ap o i n t a n d i t sn e i g h b o r s l i eo no rb e c l o s e t oa l o c a l l y l i n e a rp a t c ho f t h em a n i f o l d i f t h e r e i s
s u f f i c i e n td a t a . T h e nt h el o c a lg e o m e t r yo ft h e s ep a t c h e si sd e s c r i b e db yu s i n gl i n e a rc o e f f i c i e n t s w h i c hc a n
r e c o n s t r u c te a c hd a t ap o i n t f r o mi t sn e i g h b o r s . H o w e v e r , t h en e i g h b o r n u m b e r i sg l o b a l l y f i x e dp a r a m e t e r i n t h eL L E
m e t h o d . I na d d i t i o n , al a r g e rn e i g h b o rn u m b e r w o u l dr e s u l ti ns e l e c t i n gp o i n t sf r o m a n o t h e rl i n e a rs p a c ea s
n e i g h b o r s . I nr e c e n ty e a r s , c o m p r e s s e ds e n s i n gh a sa t t r a c t e ds u b s t a n t i a la t t e n t i o ni ns i g n a lp r o c e s s i n g , m a c h i n e
l e a r n i n g , c o m p u t e rv i s i o n , e t c . T h e r ei st h es i m i l a rl i n e a rr e p r e s e n t a t i o np r o b l e mi nc o m p r e s s e ds e n s i n g
, o rs p a r s e
s i g n a l r e c o n s t r u c t i o n . S of a r , a l o t so fm e t h o d s f o rs p a r s es i g n a l r e c o n s t r u c t i o nh a v eb e e np r o p o s e d . G e n e r a l l y , t h r e e
m a i nt e c h n i q u e so rt h e i rc o m b i n a t i o n sa r ea v a i l a b l et oo b t a i nas p a r s er e p r e s e n t a t i o n , i n c l u d i n gz e r o - t r a p p e dl o s s
f u n c t i o n s , s p a r s er e g u l a r i z a t i o na n dm a t c h i n gp u r s u i t . H e r e , w e f o c u so nm a t c h i n gp u r s u i tm e t h o d s , w h i c ha r eg r e e d y
t os o l v e t h e0 - n o r mp r o b l e m. I nf a c t , t h e0 - n o r mr e g u l a r i z a t i o ni st h ed e s i r a b l eo n et oo b t a i ns p a r s e n e s s , b u tt h e
0 - n o r mr e g u l a r i z a t i o ni ss od i s c o n t i n u o u st h a ti ti sv e r yd i f f i c u l tt oo p t i m i z et h eo b j e c t i v ef u n c t i o nc o n t a i n i n gi t .
T h e r e f o r e , t h eg r e e d y m a t c h i n gp u r s u i tm e t h o d sa r et h eb e s to n e sf o rf i n d i n gt h e0 - n o r m p r o b l e m. T h i sp a p e r
p r o p o s e sa l o c a l l ya n ds p a r s e l y l i n e a r e m b e d d i n g ( L S L E ) , w h i c h i m p r o v e s t h eL L Em e t h o d . I n t h eL S L Em e t h o d , w e
i n t r o d u c eo r t h o g o n a lm a t c h i n gp u r s u i t ( OMP ) m e t h o dw h i c hs o l v e st h e0 - n o r m p r o b l e mo fl i n e a rr e p r e s e n t a t i o n .
E a c hs a m p l e i sw e l ls p a r s e l yr e p r e s e n t e dw i t hi t sc l o s e dn e i g h b o r s . E x p e r i m e n t a lr e s u l t so ns o m er e a l - w o r l dd a t a

[ 1 ] R o w e i s S , S a u l L.N o n l i n e a r d i m e n s i o n a l i t y r e d u c t i o nb yl o c a l l yl i n e a re m b e d d i n g . S c i e n c e , 2 0 0 0 , 2 9 0 : 2 3 2 3~2 3 2 6.
[ 2 ] T e n e n b a u m J , V i nd eS i l v a , L a n g f o r dJ . A g l o b a l g e o m e t r i cf r a m e w o r kf o rn o n l i n e a rd i m e n s i o n a l i t y r e d u c t i o n . S c i e n c e , 2 0 0 0 , 2 9 0 : 2 3 1 9 ~2 3 2 3 .
[3 ] B e l k i nM , N i y o g iP. L a p l a c i a ne i g e n m a p sf o rd i - m e n s i o n a l i t yr e d u c t i o na n dd a t ar e p r e s e n t a t i o n . N e u r a lC o m p u t a t i o n , 2 0 0 3 , 1 5 ( 6 ) : 1 3 7 3~1 3 9 6.
[4 ] D o n o h oD , G r i m e s C. H e s s i a ne i g e n m a p s : n e w l o c a l l yl i n e a re m b e d d i n gt e c h n i q u e sf o rh i g hd i - m e n s i o n a l d a t a .P r o c e e d i n g s o f t h e N a t i o n a l A c a d e m y o f S c i e n c e s , t h e U n i t e d S t a t e s o f
Am e r i c a , 2 0 0 3 , 1 0 0 : 5 5 9 1~5 5 9 6.
[ 5 ] Z h a n g Z , Z h a H.P r i n c i p a l m a n i f o l d s a n d n o n l i n e a rd i m e n s i o nr e d u c t i o nv i al o c a lt a n g e n t s p a c e a l i g n m e n t . S y m p o s i u m o n D i s c r e t e  l g o r i t h m s , S c i e n t i f i cC o m p u t i n g , 2 0 0 4 , 2 6 ( 1 ) : 3 1 3~3 3 8.
[ 6 ] Y a n D Q , L i u S L , L i Y Y. A n e m b e d d i n g 9 0 4 · d i m e n s i o nr e d u c t i o na l g o r i t h mb a s e do ns p a r s ea - n a l y s i s . A c t a A u t o m a t i c aS i n i c a , 2 0 1 1 , 3 7 ( 1 1 ) : 1 3 0 6~1 3 1 2 ( 闫德勤, 刘胜蓝, 李燕燕 . 一种基于
稀疏嵌入分析的降维方法 . 自动化学报, 2 0 1 1 , 3 7 ( 1 1 ) : 1 3 0 6~1 3 1 2 ) .
[ 7 ] E l a d M , A h a r o n M. I m a g ed e n o i s i n gv i as p a r s e a n d r e d u n d a n t r e p r e s e n t a t i o n s o v e r l e a r n e d d i c t i o n a r i e s .I E E E T r a n s a c t i o n s o n I m a g e P r o c e s s i n g , 2 0 0 6 , 1 5 ( 1 2 ) : 3 7 3 6~3 7 4 5.
[8 ] B a r a n i u k M. Al e c t u r eo nc o m p r e s s i v es e n s i n g .    E E ES i g n a lP r o c e s s i n g M a g a z i n e , 2 0 0 7 , 2 4 ( 4 ) : 1 1 8~1 2 1.
[ 9 ] D o n o h oD. C o m p r e s s e d s e n s i n g . I E E ET r a n s a c t i o n so n I n f o r m a t i o nT h e o r y , 2 0 0 6 , 5 2 : 1 2 8 9 ~ 1 3 0 6 .
[ 1 0 ] C h e nS , B i l l i n g sS A , L u o W. O r t h o g o n a ll e a s t s q u a r e s m e t h o d sa n dt h e i ra p p l i c a t i o nt o n o n - l i n e a rs y s t e mi d e n t i f i c a t i o n . I n t e r n a t i o n a lJ o u r n a l
o fC o n t r o l , 1 9 8 9 , 5 0 : 1 8 7 3~1 8 9 6.
[1 1 ] P a t i Y C , R e z a i i f a r R , K r i s h n a p r a s a d P S .O r t h o g o n a lm a t c h i n gp u r s u i t : R e c u r s i v ef u n c t i o n a p p r o x i m a t i o n w i t ha p p l i c a t i o n st o w a v e l e td e - c o m p o s i t i o n .P r o c e e d i n g s o n R e c o r d o f t h e
T w e n t y - S e v e n t h A s i l o m a r C o n f e r e n c e : S i g n a l , S y s t e m sa n dC o m p u t e r s , 1 9 9 3 , 1 : 4 0~4 4.
[ 1 2 ] D e V o r eR , R o n a l dA. D e t e r m i n i s t i cc o n s t r u c t i o n s  f c o m p r e s s e d s e n s i n g m a t r i c e s .J o u r n a l o f C o m p l e x i t y , 2 0 0 7 , 2 3 : 9 1 8~9 2 5.
[ 1 3 ] C a n d é sE J , W a k i n M B. A ni n t r o d u c t i o nt o c o m p r e s s e d s a m p l i n g . I E E E S i g n a l P r o c e s s i n g M a g a z i n e , 2 0 0 8 , 2 5 : 2 1~3 0.
[ 1 4 ] D o n o h o D L , T s a i g Y , D r o r iI , e ta l . S p a r s e s o l u t i o n o fu n d e r d e t e r m i n e d s y s t e m so fl i n e a r e q u a t i o n s b y s t a g e w i s e o r t h o g o n a l m a t c h i n g
p u r s u i t .I E E E T r a n s a c t i o n s o n I n f o r m a t i o n T h e o r y , 2 0 1 2 , 5 8 ( 2 ) : 1 0 9 4~1 1 2 1.
[ 1 5 ] K o u r o p t e v aO , O k u nO , H a d i dA , e ta l . B e y o n d l o c a l l y l i n e a r e m b e d d i n g a l g o r i t h m.T e c h n i c a l R e p o r t , M a c h i n e V i s i o n G r o u p , U n i v e r s i t y o f O u l u , 2 0 0 2 : 1~4 9.
[ 1 6 ] S a u lL , R o w e i sS . T h i n kg l o b a l l y , f i tl o c a l l y : u n -s u p e r v i s e d l e a r n i n g o f l o w d i m e n s i o n a l m a n i f o l d s .T h e J o u r n a l o f M a c h i n e L e a r n i n g R e s e a r c h , 2 0 0 3 , 4 : 1 1 9~1 5 5.
[ 1 7 ] Z h a n gL , Z h o uWD. O n t h e s p a r s e n e s so f 1 - n o r m s u p p o r t v e c t o rm a c h i n e s . N e u r a lN e t w o r k s , 2 0 1 0 , 2 3 : 3 7 3~3 8 5.
[ 1 8 ] C h e n C K , Y u Y M , S h iJ .A f a s t s p a r s e r e p r e s e n t a t i o n b a s e d c l a s s i f i c a t i o n . J o u r n a l o f N a n j i n gU n i v e r s i t y ( N a t u r eS c i e n c e s ) , 2 0 1 2 , 4 8 1 ) : 7 1~7 6. ( 陈才扣, 喻以明, 史俊 . 一种快速的
基于稀 疏 表 示 分 类 器 . 南 京 大 学 学 报 ( 自 然 科 学) , 2 0 1 2 , 4 8 ( 1 ) : 7 1~7 6 ) .
[ 1 9 ] W e n G H , J i a n g L J , W e n J .D y n a m i c a l l y d e t e r m i n i n gn e i g h b o r h o o dp a r a m e t e rf o rl o c a l l y l i n e a re m b e d d i n g . J o u r n a lo fS o f t w a r e , 2 0 0 8 , 9 ( 7 ) : 1 6 6 6~1 6. ( 文贵华, 江丽君, 文 军 . 邻域参
数动态变化的局部线性嵌入 . 软件学报, 2 0 0 8 , 9 ( 7 ) : 1 6 6 6~1 6 7 3 ) .
[ 2 0 ] h t t p : / / a r c h i v e . i c s . u c i . e d u / m l /
[ 2 1 ] B i a nZ Q , Z h a n gX G. P a t t e r nR e c o g n i t i o n . T h e  r d E d i t i o n . B e i j i n g : T s i n g h u a U n i v e r s i t yP r e s s , 2 0 0 0 , 3 3 8. ( 边肇祺, 张学工 . 模式识别 . 第二版 .  北京: 清华大学出版社, 2 0 0 0 , 3 3 8 ) .
[ 2 2 ] h t t p : / / y a n n . l e c u n . c o m / e x d b / m n i s t /
[ 2 3 ] S u n J , L i u J , Z h a o L.C l u s t e r i n g A l g o r i t h m R e s e a r c h. J o u r n a lo fS o f t w a r e , 2 0 0 8 , 1 9 ( 1 ) : 4 8~ 6 1. ( 孙吉贵, 刘杰, 赵连宇 . 聚类算法研究 . 软件学报, 2 0 0 8 , 1 9 ( 1 ) : 4 8~6 1 ) .
No related articles found!
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!

版权所有 © 2021 《南京大学学报(自然科学)》

地址：江苏省南京市鼓楼区汉口路22号，南京大学学报编辑部，210093

电话：025-83592704 , 传真：025-83592704        技术支持：北京玛格泰克科技发展有限公司