태태개발일지 - 기계학습(KNN, 의사결정 tree)

KNN &  의사결정나무 

머신러닝 모델은 크게 특정 함수 형태(예: 선형 방정식)를 미리 가정하는 모수적(Parametric) 모델과, 그렇지 않은 비모수적(Non-parametric) 모델로 나뉜다.

KNN(K-Nearest Neighbors)과 의사결정나무(Decision Tree)는 대표적인 비모수적 모델입니다.

이들은 고정된 매개변수 개수를 갖지 않으며, 학습 데이터가 많아질수록 모델의 복잡도도 함께 증가하여 데이터 자체의 형태에 유연하게 대응한다는 특징이 있습니다.

 

KNN (K-Nearest Neighbors)

KNN은 데이터 분류에 있어서 가장 직관적인 알고리즘이다.

 

"입력 공간에서 서로 가까이 있는 데이터들은 같은 정답(클래스)을 가질 확률이 높다"

 

 

1. 새로운 데이터가 들어오면, 미리 정해둔 거리 측정 방식(주로 유클리디안 거리)을 이용해 가장 가까운 K개의 이웃을 찾는다.
2. 이 K개의 이웃들 중에서 가장 많이 등장한 클래스(다수결의 원칙)를 최종 예측값으로 할당한다.

 

베이즈 정리 증명

 

단순히 이웃의 숫자를 세는 것 같지만, 이 방식은 통계학의 베이즈 정리(Bayes' theorem)를 통해 수학적으로 완벽히 증명된다. 

 

 

사전 확률

 

 

사전 확률 p(Cc​)는 전체 데이터셋 중에서 무작위로 선택한 포인트가 클래스 Cc​에 속할 확률을 의미하며, 훈련 데이터의 비율로 다음과 같이 추정한다.

 

여기서 Nc​는 클래스 Cc​의 데이터 수, N은 전체 훈련 데이터의 수다.)

 

클래스 조건부 우도 

이 수식은 "어떤 데이터가 C_c클래스라고 할 때, 그 데이터가 하필 'x'라는 위치 주변에 존재할 확률(밀도)이 얼마나 될까를 묻는 것이다.

 

• V: 새로운 데이터 x를 중심으로 K개의 이웃이 딱 들어갈 만큼의 가상의 원(또는 구)의 부피(Volume)이다.
• N_c: 전체 훈련 데이터 중에서 C_c 클래스에 속하는 전체 데이터의 수이다.
• K_c: 부피 V 안에 들어온 이웃 중 C_c 클래스에 속하는 이웃의 수이다.
• 의미: 전체 C_c 클래스 데이터(N_c) 중 몇 개(K_c)가 x주변 영역(V)에 모여 있는지를 계산하여 밀도를 구한 것이다.

주변 우도 p(x)

클래스 상관없이 "공간 상의 특정 위치 'x'에 어떤 데이터든 존재할 전체 확률"이다.

 

 

• 모든 클래스에 대한 확률을 다 더해서 구합니다 

• 위의 p(x|C_c)수식과 사전확률 p(C_c) = \frac{N_c}{N}를 곱하면 클래스별 개수 N_c가 약분되어 사라진다.
• 결과적으로 모든 클래스의 이웃 수의 합 sum K_c = K만 남게 되어 위와 같이 깔끔하게 정리된다.

 

최종 사후 확률 

우리의 최종 목표인 "데이터가 'x' 위치에 있을 때, 이것이 C_c 클래스일 확률"을 구한다.

 

 

결론: 복잡한 부피(V)나 전체 데이터 수(N)는 모두 약분되어 사라지고, 오직'K개의 이웃 중 해당 클래스가 차지하는 비율'만 남게 된다.

 

 

의사결정나무 (Decision Tree)

의사결정나무는 마치 스무고개 게임처럼, 데이터의 특성(Feature)에 대해 반복적으로 질문을 던지며 데이터를 분류해 나가는 방법이다.

 

 

의사결정나무는 부모 노드에서 자식 노드로 분할할 때, 불순도가 가장 크게 감소하는 방향(정보 이득이 최대가 되는 방향)으로 데이터를 나눈다.

2진 분류에서는 왼쪽 노드와 오른쪽 노드의 불순도만 계산하여, 판단한다.

 

정보 이득 최대화

 

데이터를 쪼갰을 때 '불순도(Impurity)'가 가장 크게 줄어드는 특성을 찾아 분할한다.

• 엔트로피 (Entropy): 노드 내 데이터의 불확실성(무질서도)을 측정한다.
• 지니 불순도 (Gini Impurity): 무작위로 뽑은 데이터가 잘못 분류될 확률을 측정한다.
• 분류 오류 (Classification error): 다수결 클래스에 속하지 않는 데이터의 비율입니다. 보통 가지치기 단계에서 사용됩니다.

 

과적합(Overfitting)

나무가 너무 깊어지면 학습 데이터에만 완벽히 적응하여 새로운 데이터에 취약해진다. 

• 가지치기(Pruning): 중요도가 낮은 가지를 잘라내어 모델을 단순화한다.
• 앙상블(Random Forest): 여러 개의 나무를 만들어 그들의 의견을 종합(다수결)한다.