랜덤 포레스트와 k-NN의 관계

1 개요

랜덤 포레스트와 k-NN의 관계

랜덤 포레스트와 k-최근접 이웃 알고리즘과의 관계는 2002년, 이 린(Yi Lin)과 전용호(Jeon, Yongho)에 의해 조명되었다. 이웃 가중치 구조(weighted neighborhoods schemes) 모델을 통해 두가지 알고리즘을 통합할 수 있다. 이 모델은 데이터 집합 [math]\displaystyle{ \mathcal{D}_n =\{(\mathbf{v}_i, Y_i)\}_{i=1}^n }[/math]에서 새로운 데이터 포인트 [math]\displaystyle{ \mathbf{v'} }[/math]의 예측값 [math]\displaystyle{ \hat{Y} }[/math]을 이웃한 데이터 포인트들과 가중치 함수 [math]\displaystyle{ W }[/math]를 통해 구한다.

[math]\displaystyle{ \hat{Y} = \sum_{i=1}^n W(\mathbf{v}_i, \mathbf{v'})Y_i\,, }[/math]

여기서 [math]\displaystyle{ W(\mathbf{v}_i, \mathbf{v'}) }[/math]는 [math]\displaystyle{ i }[/math]번째 데이터 포인트 [math]\displaystyle{ \mathbf{v}_i }[/math]와 새로운 데이터 포인트 [math]\displaystyle{ \mathbf{v'} }[/math]와의 가중치로 음이 아닌 값을 갖고, 임의의 [math]\displaystyle{ \mathbf{v'} }[/math]에 대해 모든 가중치들의 합은 1이 된다. 각 모델에서 가중치 함수는 다음과 같다.

• k-최근접 이웃 알고리즘에서, [math]\displaystyle{ \mathbf{v'} }[/math]와 가장 가까운 k개의 데이터 포인트 [math]\displaystyle{ \mathbf{v}_i }[/math]에 대해 [math]\displaystyle{ W(\mathbf{v}_i, \mathbf{v'}) = {1 \over k} }[/math], 그 외의 데이터 포인트에 대해 [math]\displaystyle{ W(\mathbf{v}_i, \mathbf{v'}) =0 }[/math]
• 결정 트리에서, [math]\displaystyle{ W(\mathbf{v}_i, \mathbf{v'}) }[/math]는 새로운 데이터 포인트 [math]\displaystyle{ \mathbf{v'} }[/math]가 [math]\displaystyle{ \mathbf{v}_i }[/math]와 같은 단말 노드로 떨어질 확률을 의미한다.
• 랜덤 포레스트에서는, 독립적인 가중치 함수 [math]\displaystyle{ W_j }[/math]를 갖는 m개의 트리 집합들의 예측값을 평균내어 사용하기에, 포레스트의 전체의 예측값은 다음과 같이 나타낼 수 있다.

[math]\displaystyle{ \hat{Y} = \frac{1}{m}\sum_{j=1}^m\sum_{i=1}^n W_{j}(\mathbf{v}_i, \mathbf{v'}) \, Y_i = \sum_{i=1}^n\left(\frac{1}{m}\sum_{j=1}^m W_{j}(\mathbf{v}_i, \mathbf{v'})\right) \, Y_i, }[/math]

이 식은 포레스트 전체가 개별 트리의 가중치들의 평균값으로 다시 이웃 가중치 구조(weighted neighborhoods schemes)를 이루는 것을 보여준다. 여기서 [math]\displaystyle{ \mathbf{v'} }[/math]의 이웃 [math]\displaystyle{ \mathbf{v}_i }[/math]는 포레스트 중 적어도 하나의 트리에서 [math]\displaystyle{ \mathbf{v'} }[/math]와 같은 종단 노드로 떨어지는 데이터 포인트를 의미하게 된다. 이렇게 하여 [math]\displaystyle{ \mathbf{v'} }[/math]의 이웃은 트리의 구조와 데이터 집합의 구조에 복합적으로 의존한다. 랜덤 포레스트에서 이웃들의 분포가 각 매개변수들의 지역적 중요성에 따라 달라진다.

2 같이 보기

• 랜덤 포레스트
• k-최근접 이웃 알고리즘

3 참고

• 위키백과 "랜덤 포레스트#k-최근접 이웃 알고리즘과의 관계"