3
wi , J (wi ) =
T wi Sb wi T wi Si wi
i = 1 , 2 , · · · , c,
w, J (w) = w T Sb w w T Sw w c 1
w F (w) = F (w) w∗
w T Sb w wT Sw Lagrange
wT Sw = a = 0 Lagrange L(w, λ) = wT Sb w − λ(wT Sw − a) λ Lagrange w ∂L(w, λ) = Sb w − λSw ∂w Sb w∗ − λSw∗ = 0 Sb w∗ = λSw∗ S S −1 Sb w∗ = λw∗ w∗ S −1 Sb F (w∗ ) = w∗ wi S −1 Sb wi w w
9
C
v
m
v
vT v = 1
1=
i,j =1
αi αj Φ(xi )T Φ(xj ) = αT Kα = mλαT α αT α =
1 mλ
α
v Φ(x)T v =
i=1
m
mαi Φ(x)T Φ(xi ) =
i=1
αi K (x, xi )
K (xi , xj ) 2.2.2 KLDA LDA J (w) = w T Sb w w T Sw w αi Φ(xi )
X = [xr ]T ,
xr = λ 2 vr
1
(xr − xs )T (xr − xs ) = = = = r |δrs | p ≤ n − 1, s
T T xT r xr + xs xs − 2xr
brr + bss − 2brs arr + ass − 2ars
2 −2ars = δrs
xr , r = 1, · · · , n p = n−1 xr , r = 1, · · · , n k, k ≪ n
i = 1, · · · , n
ISOMAP LLE
ISOMAP
ISOMAP ISOMAP ISOMAP ISOMAP m xi fi fi = [Dij ] LDA LLE xi LDA
LLE
geodesic geodesic
ISOMAP D xi
LLE LLE
16
11.
LLE LLE
17
12.
T d2 rs = xr xr + s=1 n
1 n 2 n
n
xT s xs
s=1 n
1 n2
n
r =1 s=1
d2 rs =
xT r xr
r =1
11
1 2 1 brs = xT r xs = − (drs − 2 n
n
d2 rs −
r =1
1 n
n
d2 rs +
s=1
1 n2
n
n
d2 rs ) = ars −ar. −a.s +a..
2 2 2 Λ1 = diag (λ1 , · · · , λk ) 1 1 1
r p
s
V1 = [v1 , · · · , vk ],
2 X = [x1 , · · · , xn ]T = V1 Λ1
1
xr , r = 1, · · · , n |δrs |
k
r
s B
1.
δrs = δrs + c(1 − δ rs ) {δrs } B
)
4. PCA DA LDA PCA DP CA DLDA (A.M. Martinez and A.C. Kak )
6
5. PCA
(Wikipedia
)
6. (Wikipedia
)
7
7. PCA (Wikipedia )
LDA
2.2
KPCA KLDA x1 , x2 , . . . , xm , xi ∈ Rn Φ n , ,
1
p
n−p
T vi vi = 1
V1 = [v1 , · · · , vp ]
2 X = V1 Λ1 1 1
X
1
2 2 2 Λ1 = diag (λ1 , · · · , λp )
{vi }
n {δrs } A B B
{drs }
{δrs } A,
B = V ΛV T = XX T
12
Λ = diag (λ1 , · · · , λp ), xr xs
−1 Sw Sb
(w∗ )T Sb w∗ (w∗ )T Sw∗ =λ ∗ T =λ ∗ T ∗ (w ) Sw (w ) Sw∗
−1 Si Sb
4
x i mT i wi
1≤i≤c
wi |(x − mi )T wi |,
yi = xT wi , k
k = arg min |(x − mi )T wi | wi 2 LDA w
i=1
k
Nk
1 Ni
x
x∈ℜi
, i = 1, 2, · · · , c
c
Ni mi N
3. Si = 4. 1 Ni
Si (x − mi )(x − mi )T
x∈ℜi
, i = 1, 2, · · · , c
Sw Sw =
c
i=1
Ni Si N
5.
Sb
c
Sb =
i=1
Ni (mi − m)(mi − m)T N
m T T (vi xj )(vi xj )T j =1
x
v1, v2 , · · · , vk yi = xT vi , i = 1, 2, · · · , k n k n PCA
,
T T λi vi = vi Cvi = λi = vi
T vi xj
xj
vi
m T vi xj = 0 j =1
λi
19
5. Metric MDS Metric MDS
Metric MDS 6. ISOMAP ISOMAP Metric MDS
PCA
Metric MDS
geodesic ISOMAP
J (w) β
10
2.2.3
2.3
Metric MDS 2.3.1 Metric MDS ISOMAP LLE
Metric MDS Metric multidimensional scaling p D,D D n drs x1 , x2, · · · , xn , xr xs m
n×n
D B, [B ]rs = brs = xT r xs D B
ISOMAP ISOMAP ISOMAP ISOMAP ISOMAP ISOMAP
14
2.3.3
LLE Locally Linear Embedding 10
LLE LLE
LLE 1 2 xi xj xi , xi
LLE xj xi xj xi xi xi ǫ k
9. ISOMAP
10.
15
xj
m
xi = 0
i=1
C= C
1 m
m
xi xT i
i=1
C = V ΛV T Λ = diag (λ1 , λ2 , · · · , λn ) V V T = 1 C p, rank (C ) = p C p
λ1 ≥ λ2 ≥ · · · ≥ λp > 0 k x [y1 , y2 , · · · , yk ]T k = p = n, C PCA C 1 m
(2005210988)
PCA, LDA, KPCA, KLDA, Metric MDS, ISOMAP, LLE
1
256 × 256 4096
1. 2. 3. 4. (PCA) (ICA) (KICA) ISOMAP (LDA) (KDA) LLE (LFA) (KPCA)
1
2
2.1
2.1.1 PCA m PCA(Principal Component Analysis) x1 , x2 , . . . , xm , xi ∈ Rn
r =1 s=1
1 ars = − d2 , 2 rs
ar. =
1 n
ars ,
s
a.s =
1 n
ars ,
r
a.. =
1 n2
sars
r
A,[A]rs = ars B = HAH 1 T 11 , n
H=I− B B = XX T
1 = (1, 1, · · · , 1)T n×p
X = [x1 , · · · , xn ]T
m
2
xi ∈ Rn , x→X
Φ
1 m
m
Φ(xj )Φ(xj )T
j =1
v ∈ F \{0} Φ(xj )(Φ(xj ) v ) =
j =1 T
λv = Cv
m
j =1
Φ(xj )T v Φ(xj ) λm
α1 , · · · , αm
m
v=
j =1
αj Φ(xj )
Kij := Φ(xi )T Φ(xj ) v C λ(Φ(xk )T v ) = (Φ(xk )T Cv ), mλKα = K 2 α α = [α1 , · · · , αm ]T α mλα = Kα k = 1, 2, · · · , m
n
B
B
rri = 0 (i = 1, · · · , p)
r =1
B,
T d2 rs = (xr − xs ) (xr − xs ) T T T d2 rs = xr xr + xs xs − 2xr xs
1 n 1 n
1 drs = n r =1