Decision Tree는 overfitting될 가능성이 높다는 약점을 가지고 있습니다. 가지치기를 통해 트리의 최대 높이를 설정해 줄 수 있지만 이로써는 overfitting을 충분히 해결할 수 없습니다. 그러므로 좀더 일반화된 트리를 만드는 방법을 생각해야합니다. 이는 Random Forest(랜덤 포레스트)의 기원이 되는 아이디어입니다.

Random forest는 ensemble(앙상블) machine learning 모델입니다. 여러개의 decision tree를 형성하고 새로운 데이터 포인트를 각 트리에 동시에 통과시키며, 각 트리가 분류한 결과에서 투표를 실시하여 가장 많이 득표한 결과를 최종 분류 결과로 선택합니다.

랜덤 포레스트가 생성한 일부 트리는 overfitting될 수 있지만, 많은 수의 트리를 생성함으로써 overfitting이 예측하는데 있어 큰 영향을 미치지 못 하도록 예방합니다. 이번 포스팅에서는 랜덤 포레스트에 대해서 알아보도록 하겠습니다.

Bagging

랜덤 포레스트는 제일 먼저 bagging 이라는 과정을 거칩니다. Bagging은 트리를 만들 때 training set의 부분집합을 활용하여 형성하는 것을 말합니다. 예를 들어, training set에 1000 개의 데이터가 존재한다고 가정하면 각 트리를 생성할 때 100 개의 데이터만 임의로 선택하여 트리를 만드는데 활용할 수 있는 것입니다. 즉 모든 트리는 각기 다른 데이터를 바탕으로 형성되지만 모두 training set의 부분집합입니다.

이렇게 100 개의 데이터를 임의로 선택할 때 한가지 중요한 것은 바로 중복을 허용한다는 것입니다(with replacement). 이렇게 중복을 허용함으로써 1000 개의 training set에서 100 개만 뽑기보다 1000 개씩 매번 뽑아도 unique한 데이터셋을 형성할 수 있으므로 N 개의 training set이 있다면 임의로 N 개의 데이터를 중복을 허용하여 선택함으로써 각 트리를 형성합니다.

Bagging Features

랜덤 포레스트는 트리를 형성할 때 데이터셋에만 변화를 주는 것이 아닌 feature를 선택하는데 있어서도 변화를 줍니다. Feature를 선택할때도 기존에 존재하는 feature의 부분집합을 활용합니다. 예를 들어, 자동차 데이터셋에 다음과 같은 feature들이 있고 이를 통해 자동차의 등급(very good, good, acceptable, unacceptable)을 분류한다고 생각해봅시다.

• 가격
• 유지 보수 비용
• 문의 개수
• 탑승 인원 수
• 트렁크 사이즈
• 안전 등급

위 데이터를 제일 처음 분류할 때, 고려할 feature를 임의로 선택하여 가격과 문의 개수, 그리고 안전 등급 3개의 feature중에 선택할 수 있습니다. 여기서 선택된 best feature로 데이터를 분류한 뒤에는 마찬가지로 고려할 feature를 임의로 선택하여 유지 보수 비용과 문의 개수, 그리고 트렁크 사이즈 3개의 feature중에 선택할 수 있습니다. 이러한 과정을 트리가 만들어질 때 까지 반복합니다.

위 예에서는 단지 3개의 feature만을 임의로 선택하였는데 이는 예시로 든 feature 수가 적기 때문이고, 일반적으로 M 개의 feature가 존재할 때, 임의로 선택하는 feature의 수는 $\sqrt{M}$ 을 활용합니다. 즉, 25 개의 feaure가 존재한다면 임의로 5개의 feature를 선택하고 그 중에서 가장 information gain이 높은 feature를 선택하여 데이터를 분류하게 됩니다.

Classify

여러개의 트리를 형성하였다면 이제 classify를 수행할 수 있습니다. 예를 들어, 8 개의 트리를 형성하고 임의의 자동차 데이터를 각 트리에 전달하였을 때 나온 결과가 다음과 같다고 가정해봅시다.

["very good", "very good", "good", "very good", "acceptable", "very good", "good", "very good"]

위 결과에서 very good 이 5 번 등장하여 가장 많은 득표수를 나타냈으므로 임의의 자동차는 very good 으로 분류될 것입니다. Test 단계에서는 모든 데이터셋에 대해서 위 과정을 거치게 되고, 그렇게 나온 결과와 ground truth를 비교하여 accuracy를 측정하게 됩니다.

Python Implement

이전 포스팅 Decision Tree(의사 결정 트리) 개념 정리 에서 다룬 코드들(build_tree 등)을 그대로 사용하도록 하겠습니다. 다만 트리의 맨 끝 노드를 나타내는 Leaf와 내부 노드를 나타내는 Internal_Node 클래스를 먼저 정의하도록 하겠습니다.

class Leaf:
  def __init__(self, labels, value):
    self.labels = Counter(labels)
    self.value = value

class Internal_Node:
  def __init__(self, feature, branches, value):
    self.feature = feature
    self.branches = branches
    self.value = value

다음으로 랜덤 포레스트를 구현하기 위해 필요한 로직을 추가하도록 하겠습니다. 제일 먼저 feature bagging을 수행하는 find_best_split_subset() 메서드를 기존에 작성한 find_best_split() 에 한 줄을 추가함으로써 새롭게 작성하겠습니다. 아래 코드는 위에서 언급한 자동차 데이터셋의 feature를 바탕으로 bagging을 수행하는 코드입니다.

def find_best_split_subset(dataset, labels, num_features):
  # 주어진 총 6개의 feature에서 3개의 feature를 중복을 허용하지 않고 임의로 선택합니다
  features = np.random.choice(6, 3, replace=False)
  best_gain = 0	# 데이터를 특정 feature로 분할하였을 때 가장 높게 측정된 information_gain
  best_feature = 0	# 데이터를 분할 할 feature의 index
  for feature in features:
    data_subsets, label_subsets = split(dataset, labels, feature)
    gain = information_gain(labels, label_subsets)
    if gain > best_gain:
      best_gain, best_feature = gain, feature
  return best_feature, best_gain

위 코드를 활용하여 여러 트리를 생성하는 build_tree_forest() 메서드를 새롭게 만들겠습니다. 기존에 bestgain이 0일때 Counter(labels) 를 반환하는 로직을 Leaf 객체를 반환하도록 수정하였고, 마지막에 branches를 반환하는 로직에서 `InternalNode객체를 반환하도록 수정하였습니다. 그 외의 로직은build_tree()` 에서와 같습니다.

def build_tree_forest(data, labels, n_features, value=""):
  # 데이터를 분할 할 최적의 feature를 찾습니다
  best_feature, best_gain = find_best_split_subset(data, labels, n_features)
  # 만약 분할 후의 information_gain이 0에 근사하면 해당 노드는 더 분할 할 필요가 없으므로 리턴합니다
  if best_gain < 0.00000001:
    return Leaf(Counter(labels), value)
  # 데이터를 찾은 best feature로 분할합니다
  data_subsets, label_subsets = split(data, labels, best_feature)
  branches = []
  # 분할 후 각 그룹에 대해서 build_tree_forest 함수를 재귀적으로 호출합니다
  for i in range(len(data_subsets)):
    branch = build_tree_forest(data_subsets[i], label_subsets[i], n_features, data_subsets[i][0][best_feature])
    branches.append(branch)
  return Internal_Node(best_feature, branches, value)

마지막으로 bagging을 수행하여 랜덤 포레스트를 형성하는 make_random_forest() 메서드를 새롭게 작성하도록 하겠습니다.

def make_random_forest(n, training_data, training_labels):
  trees = []	# 형성한 트리를 저장하는 배열
  # 트리의 개수(n)만큼 트리를 형성합니다.
  for i in range(n):
    # training set의 개수만큼 데이터를 중복을 허용하지 않고 선택합니다
    indices = [random.randint(0, len(training_data)-1) for x in range(len(training_data))]
		# 선택한 데이터들로 데이터셋을 만듭니다
    training_data_subset = [training_data[index] for index in indices]
    training_labels_subset = [training_labels[index] for index in indices]
		# 위에서 만든 데이터셋으로 트리를 형성하고 배열에 추가합니다
    tree = build_tree_forest(training_data_subset, training_labels_subset, 2)
    trees.append(tree)
  return trees

이로써 순수 Python으로 랜덤 포레스트를 구현할 수 있었습니다.

Scikit-Learn

역시나 scikit-learn 모듈은 RandomForestClassifier 라는 랜덤 포레스트 클래스를 제공함으로써 손쉽게 랜덤 포레스트를 구현할 수 있도록 해줍니다. 위 클래스는 sklearn.ensemble 이란 모듈에 포함되어 있습니다.

RandomForestClassifier 는 DecisionTreeClassifier 와 거의 비슷한 방법으로 학습하고 테스트할 수 있습니다. 우선 RandomForestClassifier 를 생성할 때, 트리를 얼마나 형성할 것인지 나타내는 n_estimators 파라미터를 정의해야 합니다.

from sklearn.ensemble import RandomForestClassifier
# 2000개의 트리를 형성하도록 설정합니다
classifier = RandomForestClassifier(n_estimators=2000)

다음으로는 DecisionTreeClassifier 와 동일하게 .fit() , .predict(), .score() 메서드를 활용할 수 있습니다.

classifier.fit(training_data, training_labels)
score = classifier.score(testing_points, testing_labels)
print(score)

Review

지금까지 랜덤 포레스트에 대하여 알아보았습니다. 이번 포스팅에서 배운 내용을 정리하면 다음과 같습니다.

• A random forest is an ensemble machine learning model. It makes a classification by aggregating the classifications of many decision trees.
• Random forests are used to avoid overfitting. By aggregating the classification of multiple trees, having overfitted trees in a random forest is less impactful.
• Every decision tree in a random forest is created by using a different subset of data points from the training set. Those data points are chosen at random with replacement, which means a single data point can be chosen more than once. This process is known as bagging.
• When creating a tree in a random forest, a randomly selected subset of features are considered as candidates for the best splitting feature. If your dataset has n features, it is common practice to randomly select the square root of n features.

References

• Codecademy
• scikit-learn 랜덤 포레스트(Random Forest)