[차원 축소] 지역 선형 임베딩 LLE

◈  '차원 축소' 목차 ◈

1. 투영, 매니폴드

2. PCA, 랜덤 PCA, 점진적 PCA

3. 커널 PCA

4. MDS, Isomap

5. 지역 선형 임베딩 LLE

    지역 선형 임베딩이 무엇인지 그리고 알고리즘이 어떻게 동작하는 지 살펴보자.

6. t-SNE

---

1. LLE

지역 선형 임베딩 Locally Linear Embedding 은 또 다른 강력한 비선형 차원 축소 기술이다. 

LLE는 이전 알고리즘처럼 투영에 의존하지 않는 매니폴드 학습이다. 

 

LLE는 좁은 범위에서 구축한 선형 모델을 연결하면 다양체, 매니폴드를 구현할 수 있다는 알고리즘이다.

간단히 말해, LLE는 먼저 각 훈련 샘플이 가장 가까운 이웃에 얼마나 선형적으로 연관되어 있는 지 측정한다.

그런 다음 국부적인 관계가 가장 잘 보존되는 훈련 세트의 저차원 표현을 찾는다. 

이런 방법은 특히 잡음이 너무 많지 않은 경우 꼬인 매니폴드를 펼치는 데 잘 작동한다. 

 

★ 장점

- 사용하기 편하다.

- 최적화가 극소 최소점으로 가지 않는다.

- 비선형 임베딩 생성이 가능하다. 

 

 

2. LLE 알고리즘

step1. 선형적 지역 관계 모델링

각 훈련 샘플이 가장 가까운 이웃에 얼마나 선형적으로 연관되어 있는 지 측정한다. 

 

각 훈련 샘플 x(i)에 대해 가장 가까운 k개의 샘플을 찾는다.

그런 다음 이 이웃에 대한 선형 함수로 x(i)를 재구성한다. 

 

 

 

step2. 관계를 보존하는 차원 축소

가능한 한 이 관계가 보존되도록 훈련 샘플을 d차원 공간 (d<n)으로 매핑한다. 

 

 

 

첫 번째 단계는 샘플을 고정하고 최적의 가중치를 찾는 과정이고

두 번째 단계는 가중치를 고정하고 저차원의 공간에서 샘플의 최적 위치를 찾는 과정이다. 

 

 

 

※ 계산 복잡도

사이킷런이 제공하는 LLE 의 계산 복잡도는 k개의 가까운 이웃을 찾는데 O(m(log(m)nlog(k)), 가중치 최적화에 O(mnk^3), 저차원 표현을 만드는 데 O(dm^2) 이다.  불행하게도 마지막 항의 m^2 때문에 이 알고리즘은 대량의 데이터 셋에 적용하기는 어렵다.

 

 

3. LocallyLinearEmbedding 

사이킷런에서 LocallyLinearEmbedding 을 통해 지역 선형 임베딩 모델을 구현할 수 있다.

from sklearn.manifold import LocallyLinearEmbedding

lle = LocallyLinearEmbedding(n_components=2, n_neighbors=10)
X_reduced = lle.fit_transform(X)