Wrapper Selection의 종류 - Forward & Backward Greedy, Genetic & Local Search

이 포스팅은 개인적은 공부를 남기는 포스팅입니다. 잘못된 부분이 있다면 댓글로 알려주시면 감사합니다.

Wrapper Selection은 Feature Selection에 예측 모델에 서로 피처들의 부분 집합을 만들어 테스트 하여 최적화된 부분 집합을 선택하는 방법입니다.

Wrapper Selection에는 Forward Greedy, Backward Greedy, Genetic Search, Local Search 4가지 방법이 대표적입니다.

4가지 방법에 대해 간략하게 정리해보겠습니다.

1. Forward Greedy (Forward Selection)

Forward Greedy는 Forward Selection으로도 불립니다. 변수를 하나씩 추가하며 모델의 성능을 측정하며 가장 좋은 성능을 보인 변수를 선택하는 방법입니다.

1. Feature를 선택하지 않고 시작한다.
2. Feature를 하나씩 선택하여 모델의 성능을 측정하며 성능이 가장 좋은 Feature를 선택합니다.
3. 앞서 선택된 Feature에 모델을 하나씩 추가로 선택하여 모델을 측정하여 최고의 성능을 측정하고 가장 좋은 Feature 집합을 선택합니다.
4. 3번의 작업을 반복하여 원하는 성능 또는 원하는 Feature 개수가 뽑힐 때 까지 반복 합니다.
   
   

모델로 성능을 측정하며 Feature를 하나씩 선택해 나가는 방법으로 최적의 Feature 조합을 얻어 낼 수 있습니다.

2. Backward Greedy - Backward Selection

Backward Greedy는 Backward Selection으로도 불립니다. 이 방법은 Forward Greedy와 반대로 수행합니다.

모든 Feature를 가지고 있는 집합에서 하나의 변수를 제거하여 모델을 테스트 하며 가장 영향도가 적은 Feature을 빼는 방법입니다.

1. 모든 Feature를 선택하고 시작합니다.
2. Feature를 하나씩 빼 모델의 성능을 측정하며 성능에 가장 영향도가 적은 Feature를 제거합니다.
3. 2번의 작업을 반복하여 정해진 성능 또는 원하는 Feature 개수가 제거 될때 까지 반복합니다.
   
   

3. Genetic Search

서로 요소들을 선택하여 합치는 방법

돌연변이 생성 방법

Genetic Search 또는 Genetic algorithms이라 불리는 방법으로 유전자가 진화하는 방식과 같이 서로 다른 부분 집합의 일부 요소들만 선택하여 합치거나 돌연변이 같이 기존 요소를 빼고 없는 요소를 추가하여 모델의 성능을 측정하여 최적화된 Feature를 찾아내는 방식입니다.

4. Local Search

Hill Climbing Algorithm이라고도 불리우며 가까운 Feature 중 가장 성능이 좋은 Feature를 선택하는 방식입니다. Hill Climbing Alogorithm의 간단한 예로 이해해 보겠습니다.

출발선에 있는 데이터가 높은 곳을 향해 간다고 생각해봅시다. 주변(정해진 거리만큼)에 어떤 지점을 선택했을때 높은 곳을 향해 갈 수 있는지 판단하고 그점을 선택하여 높은 곳으로 반복해서 진행합니다. 계속 올라 갔을때 주변에 어떤 것을 선택해도 높이 올라갈 수 없다면 멈춥니다.

이렇게 주변에 있는 Feature 중 가장 높은 성능을 보이는 하나의 Feature를 선택하고 최고의 성능이 나타날때까지 반복하여 Feature의 집합을 찾아내는 방식입니다.

참고 및 사진 출처

 

https://blog.usejournal.com/understanding-the-genetic-algorithm-4eac04a07a59

https://www.semanticscholar.org/paper/HCCA%3A-A-Cryptogram-Analysis-Algorithm-Based-on-Hill-Zhang-Li/18d63fb873f9711cc5470d874f513f39d67978e3