유전 알고리즘을 이용한 특징 선택

이번 포스팅에서는 유전 알고리즘을 이용하여 특징을 선택하는 방법에 대해 알아보겠습니다. 

유전 알고리즘에 대한 설명은 이 포스팅을 참고하시기 바랍니다.

추후에 유전 알고리즘의 테크니컬한 부분을 중심으로 한 번 다루겠습니다.

 

래퍼 방법(wrapper method)

래퍼 방법은 모델의 예측 정확도 측면에서 가장 좋은 성능을 보이는 특징 집합을 구성하는 방법입니다. 다시 말해, 래퍼 방법이 해결하고자 하는 문제는 아래 그림과 같이 원 특징 집합의 부분 집합을 특징 집합으로 사용했을 때의 모델의 예측 정확도를 최대로 하는 부분 집합을 찾는 것입니다.

 

즉, 위 그림에서 원 특징 집합 X 로부터 적절한 특징을 선택하여 구성한 특징 집합 ϕ 를 지도학습 모델에 투입했을 때 나오는 점수(예: 정확도, MAE, 재현율 등)가 가장 좋은 특징 집합을 찾는 것입니다.

가장 좋은 특징 집합을 찾는 것은 현실적으로 불가능하므로 유전 알고리즘을 사용하여 찾아보겠습니다.

 

데이터 및 모델

래퍼 방법은 데이터와 모델이 정의되어야만 사용할 수 있는 특징 선택 방법입니다. 여기서 사용할 데이터는 wdbc 데이터로 특징 30개와 샘플 569개로 구성됩니다.

 

wdbc.csv

0.10MB

 

즉, 구성할 수 있는 특징 집합 개수는 2^30 - 1 으로 약 10억 7백만 정도입니다. 당연히 모든 특징 집합을 하나하나 비교하면 가장 좋은 특징 집합을 찾을 수 있겠지만 특징 집합 하나를 평가하는데 1초만 걸려도 약 817년 후에야 답을 알 수 있습니다.

이 데이터를 불러오고 뒤에서 cross_val_score 함수를 사용하기 위해 임의로 순서를 섞고 특징과 라벨로 분리하겠습니다.

1 import pandas as pd
2 df = pd.read_csv("../../data/classification/wdbc.csv")
3 df = df.sample(frac = 1, random_state = 2022)
4 X = df.drop('y', axis = 1)
5 y = df['y']

• 라인 3: sample 메서드는 데이터프레임의 행 일부를 임의로 샘플링하는 함수입니다. frac은 선택할 행의 비율을 나타내는 인자입니다. frac을 1로 설정하면 원 데이터가 다시 선택되는 것이므로 데이터의 순서를 섞는 효과가 있습니다.

 

모델로는 random_state를 제외한 나머지 하이퍼 파라미터를 기본값으로 설정한 로지스틱 회귀를 사용하겠습니다.

1 from sklearn.linear_model import LogisticRegression
2 model_instance = LogisticRegression(random_state = 2022)

cross_val_score 함수는 5겹 교차 검증 방식으로 모델을 평가하는 함수입니다. 전처리를 효과적으로 하기 어렵고 커스터마이징하기도 어려우나, 이 문제에서는 큰 문제없이 활용할 수 있어서 사용하겠습니다. 이 함수의 주요 인자는 다음과 같습니다.

• estimator: 학습되지 않은 모델 인스턴스
• X: 특징 벡터
• y: 라벨
• scoring: 평가 척도
• cv: 부분 집합(fold) 개수

이 함수의 출력은 ndarray로 i번째 요소는 i번째 부분 집합으로 평가했을 때의 점수입니다. 특징 선택 전에 cross_val_score 함수로 교차 검증을 수행해보겠습니다.

1 result = cross_val_score(model_instance, X, y, cv = 5, scoring = "f1")
2 display(result)

[실행 결과]

array([0.88888889, 0.91358025, 0.91566265, 0.95348837, 0.92857143])

위 실행 결과에서 보듯이 평가 결과가 ndarray로 나오므로 평균을 구해서 평가 지표로 활용하겠습니다.

 

유전 알고리즘 연산자 정의

유전 알고리즘을 구성하는 초기 해 집단 생성, 적합도 함수, 선택 연산자, 교차 연산자, 돌연변이 연산자를 함수 형태로 모두 구현하겠습니다.

 

해 표현 및 초기 해 집단 생성

유전 알고리즘에서 사용하는 해는 이진 인코딩을 사용하여 표현하겠습니다. 임의의 해 z = (z1, z2, ..., zm)의 각 요소는 부울로 True이면 대응되는 위치의 특징을 사용하고 False면 사용하지 않습니다. 래퍼 방법에서 주로 사용하는 해 표현 구조이니 알아두기를 바랍니다. 

파이썬을 이용하여 초기해를 만드는 함수 initialize를 작성하겠습니다.

1 import numpy as np
2 def initialize(n, m):
3     Z = np.random.choice([0, 1], (n, m))
4     Z = Z.astype(bool)
5     return Z

이 함수는 유전자의 개수 n과 특징의 개수 m을 입력받습니다. 우리가 해결할 문제의 데이터에는 30개의 특징이 포함되므로 m을 30으로 설정할 예정입니다.

 

적합도 함수

적합도는 5겹 교차 검증으로 로지스틱 회귀를 학습했을 때의 평균 F1 점수를 사용하겠습니다. 이를 함수로 구현하겠습니다.

1 def fitness(X, y, model, z):
2    score = cross_val_score(model, X.loc[:, z], y, cv = 5, scoring = "f1")
3    return score.mean()

• 라인 2: 해 z를 바탕으로 X의 열을 선택한 특징 벡터 X.loc[:, z]로 5겹 교차 검증을 수행한 결과를 score에 저장합니다.
• 라인 3: score의 평균을 반환합니다.

 

선택 연산자

선택 연산자로는 룰렛 휠 방법을 사용하겠습니다. 그 이유는 탐색 공간이 매우 넓은데, 적합도가 0과 1사이기에 적합도별로 차이가 크게 나기 어려워서 룰렛 휠을 쓰면 다양한 해를 탐색할 수 있기 때문입니다. 함수는 아래와 같이 구현합니다.

1 def selection(Z, S, k):
2     selected_index = []
3     _S = S.copy()
4     for _ in range(k):
5         probs = _S / _S.sum()
6         z_idx = np.random.multinomial(1, probs).argmax()
7         selected_index.append(z_idx)
8         _S[z_idx] = 0
9     return Z[selected_index]

 

교차 연산자

교차 연산자로는 한 점 교차 연산자를 사용하겠습니다.

1 def crossover(X1, X2):
2     point_idx = np.random.choice(range(1, len(X1)))
3     new_X = np.hstack([X1[:point_idx], X2[point_idx:]])
4     return new_X.astype(int)

• 라인 2: 1과 len(X1) 사이의 한 점을 임의로 선택합니다.
• 라인 3: point_idx까지 슬라이싱한 X1과 point_idx부터 슬라이싱한 X2를 병합하여 new_X를 만듭니다.

 

돌연변이 연산자

돌연변이 연산자로는 비트 플립 돌연변이 연산자를 사용하겠습니다.

1 def bit_flip(z, p):
2     probs = np.random.random(len(z))
3     z[probs < p] = 1 - z[probs < p]
4     return z

 

메인 코드

지금까지 작성한 함수를 사용하여 다음과 같이 메인 코드를 작성하겠습니다.

 1 def main(n, m, k, p, q, num_generation):
 2     best_score = -1
 3     Z = initialize(n, m) # 초기해 생성
 4     for _ in range(num_generation):
 5         # 해 평가
 6         S = np.array([fitness(X, y, model_instance, z) for z in Z]) 
 7         current_best_score = S.max()
 8         current_best_features = Z[S.argmax()]
 9         
10         # 최고 해 업데이트
11         if current_best_score > best_score:
12             best_score = current_best_score
13             best_features = current_best_features
14         
15         # k개 해 선택
16         Z_new = selection(Z, S, k) 
17         
18         # 교배 및 돌연변이 연산
19         children = []
20         for _ in range(n - k):
21             parent_idx = np.random.choice(range(k), 2, replace = False)
22             child = crossover(Z_new[parent_idx[0]], Z_new[parent_idx[1]])
23             if np.random.random() < q:
24                 child = bit_flip(child, p)
25             Z_new = np.vstack([Z_new, child])
26         
27         Z = Z_new.astype(bool)
28     
29     return best_features, best_score

• 라인 1: 세대 당 해의 개수 n, 특징 개수 m, 선택할 해의 개수 k, 돌연변이 확률 q, 각 유전 개체가 돌연변이가 될 확률 p, 세대 수 num_generation을 입력으로 받습니다.
• 라인 2: 최고 점수를 -1로 초기화합니다. 적합도가 아무리 작아도 0이므로 0보다 작기만 하면 됩니다.
• 라인 3: 세대 수만큼 평가, 업데이트, 선택, 교배 및 돌연변이 연산을 반복합니다.
• 라인 6: Z에 있는 모든 요소 z에 대해 fitness 함수를 사용하여 계산한 적합도 목록을 S에 저장합니다. S는 max와 argmax 메서드를 사용하기 위해 ndarray로 변환합니다.
• 라인 7 – 8: 현재 세대에서 최고 점수인 current_best_score와 해당 점수를 갖는 최고 특징 집합 current_best_features를 찾습니다.
• 라인 11 – 13: 현재 세대에서 최고 점수인 current_best_score가 지금까지의 최고 점수인 best_score보다 크다면 best_score와 best_features를 각각 업데이트합니다.
• 라인 16: selection 함수를 이용하여 해 집단 Z와 평가 점수 목록 S를 사용하여 k개 해를 선택한 결과를 Z_new에 저장합니다.
• 라인 19: Z_new를 사용하여 만들 자식 해 집단을 children을 빈 목록으로 초기화합니다.
• 라인 20: 한 세대의 해 개수 n에서 선택한 해의 개수 k를 뺀 만큼 반복하여 자식 해를 생성합니다.
• 라인 21: 부모 해 인덱스를 두 개 선정합니다. 이 인덱스는 라인 16에서 정의한 Z_new에서 부모 해를 선택하는데 사용합니다.
• 라인 22: crossover 함수를 사용하여 두 부모 해를 교배하여 자식 해 child를 생성합니다.
• 라인 23 – 24: 확률 q로 돌연변이 연산자를 적용합니다. 이처럼 모든 자식 해에 돌연변이 연산자를 적용하지 않습니다.
• 라인 25: Z_new에 child를 추가합니다.
• 라인 27: Z_new로 Z를 대체합니다. 이때 연산 과정에서 int형으로 바뀌므로 astype(bool)을 사용하여 부울 자료형으로 바꿉니다.
• 라인 29: 최고 특징 집합과 최고 점수를 반환합니다.

 

이제 이 함수를 사용하여 특징 선택을 수행하겠습니다. 먼저 유전 알고리즘의 하이퍼 파라미터를 다음과 같이 설정하겠습니다.

1 n = 20
2 m = X.shape[1]
3 k = 10
4 num_generation = 100
5 p = 0.1
6 q = 0.1

main 함수를 사용하여 최고 특징과 최고 점수를 뽑습니다. main 함수는 각 특징이 선택되는지를 나타내는 부울 배열을 반환하므로 해당 부울 배열을 인덱스로 하여 어떤 특징이 뽑혔는지 확인하겠습니다.

1 best_features, best_score = main(n, m, k, p, q, num_generation)
2 print(X.columns[best_features], best_score)

[실행 결과]

Index(['x1', 'x3', 'x4', 'x5', 'x6', 'x7', 'x8', 'x9', 'x11', 
       'x13', 'x14', 'x16', 'x17', 'x18', 'x19', 'x22', 'x23', 'x24', 'x26', 'x27', 'x28', 'x29'],
      dtype='object') 0.9420215882509126

 

실행 결과에서 보듯이, 평균적으로 0.942 정도의 F1 점수가 나오는 특징 집합을 찾았습니다.