The Sequential Floating Selection

참고 논문 : Floating search methods in feature selection, 1994, P.Pudil, J. Novovicova, J. Kittler

boosting 논문을 보다가 Floating search method 를 이용하여 특징을 제거하는 방법에 대한 간단한 설명으로

이 논문까지 오게되었다.

논문의 설명은 애매하긴한데, 일단 아는데로 정리해보도록 하자.

크게 두가지 방식이 있다.

1. The Sequential Forward Floating Selection Algorithm

2. The Sequential Backward Floating Selection Algorithm

1은 공집합으로부터 좋은 특징을 추가하는 형태이고, 2는 반대로 전체 집합에서 가장 좋지 않은 것부터 차례대로 삭제하는 방식이다.

o The Sequential Forward Floating Selection Algorithm

초기화 X_0 = 공집합, k=0

문제 정의 : 참 간단한 알고리즘 같은데, 이해하는데 꾀나 애를 먹었다. 문제는 J() 함수가 중요한 듯 하다. 특징 집합 X가 있을때, 예를 들어 x_i가 X 집합중에 가장 좋은 것이라고 한다고 해서 J(x_j,..., x_i) 즉 여러개의 특징들이 함께 있을때 J가 항상 좋은 값을 갖는 것은 아닌란 것.. 이와 같은 문제로 인해, 일단 가장 좋은것을 추가하고, 추가한 것을 뺀 상태와, 나머지 다른 것들을 뺀 상태로 J함수로 비교를 함으로써 어떤것이 좋은지 판단하는 것이라고 이해하면 될 듯하다.

Step 1(Inclusion)
Using the basic SFS method, select feature x_k+1 from the set of available measurrements, Y-X_k to form feature set X_k+1, i.e., the most significant feature x_k+1 with respect to the set X_k is added to X_k, Therefore
X_k+1 = X_k+x_k+1

 SFS 방법으로 특징을 선택한다. 즉 가장 좋은 특징을 선택하는 것. 선택된 특징을 추가한다. 일단 추가하는 것.

Step 2(Conditional exclusion)
Find the least significant feature in the set X_k+1. If x_k+1 is the least significant feature in the set X_k+1, i.e.
J(X_k+1 - x_k+1) >= J(X_k+1 - x_j) , 모든 j = 1,2,..., k
then set k=k+1 and return to Step 1, but if x_r, 1<=r <=k, is least significant feature in the set X_k+1, i.e.
J(X_k+1 - x_r ) > J(X_k),
then exclude x_r form X_k+1 to form a new feature set X'_k, i.e.
X'_k = X_k+1 -x_r.

Note that now J(X'_k) > J(X_k). if k=2, the set X_k= X_'k and J(X_k) = J(X'_k) and return to Step 1. else go to Step 3.

현재까지 선택된 특징 집합 중에서, 가장 좋지 않은 특징을 고른다.
만약 이 특징이 바로 전에 추가된 특징이라면, Step 1로 Go!! 하지만, 만약 가장 좋지 않은 특징이, 기존에 추가된 것이라면, 가장 좋지 않는 특징( 즉, 바로 전에 추가된 것이 아닌, 기존 특징 집합에 있던 것)은 제거한다.
이부분이 가장 애매한데, 간단하게 말하면, 현재 추가된 것을 일단 뺀 것, 즉 이전 상태의 특징 집합과, 현재 것을 추가 한 후에, 나머지 특징을 하나씩 빼보면서 검사를 수행한다. 만약, 다른 것을 빼는게 더 좋다면, 새로운 것은 넣고, 이전에 추가된 특징을 빼는 것이다.

Step 3 ( Continuation of conditional exclusion)
Find the least significant feature xs in the set X'_k.
I f J(X'_k-x_s)<= J(X_k-1 ) then set X_k=X'_k, J (X_k)= J(X'_k) and return to Step 1.
I f J(X'_k - x_s ) > J (X_k-1I ) then exclude Xs from X~, to form a newly reduced set
X'_k-1,_ l, i.e.
X'_k-1 = X'_k - x_s,
Set k=k - 1 . Now if k=2, then set X_k=X'_ and
J(Xk) =J (X; ) and return to Step 1, else repeat Step
3.