Dasein's ‎Archive

Chapter 6. 통계적 머신러닝

1. K 최근접 이웃

- K 최근접 이웃(KNN; k-nearest neighbor) 알고리즘의 아이디어

• 특징들이 가장 유사한(즉, 예측변수들이 유사한) K개의 레코드를 찾는다.
• 분류 : 이 유사한 레코드들 중에 다수가 속한 클래스가 무엇인지 찾은 후에 새로운 레코드를 그 클래스에 할당한다.
• 예측(KNN 회귀라고도 함) : 유사한 레코드들의 평균을 찾아서 새로운 레코드에 대한 예측값으로 사용한다.

- KNN은 가장 간단한 예측/분류 방법 중 하나이다. 회귀와는 달리 모델을 피팅하는 과정이 필요 없다.

- KNN이 완전히 자동화된 방법은 아니다. 특징들이 어떤 척도에 존재하는지, 가까운 정도를 어떻게 측정할 것인지, K를 어떻게 설정할 것인지에 따라 예측 결과가 달라진다.

- 모든 예측변수들은 수치형이어야 한다.

1) 거리지표

- 유사성(similarity) 혹은 근접성(nearness)은 거리 지표를 통해 결정된다. 이 지표는 $(x_1, x_2, \cdot\cdot\cdot,x_p)$와 $(u_1, u_2, \cdot\cdot\cdot, u_p)$가 얼마나 멀리 떨어져 있는지 측정하는 함수라고 할 수 있다.

※ 유클리드 거리(Euclidean distance)

- 유클리드 거리는 특별히 계산상의 이점이 있다. KNN은 $K$ x $n$(데이터 개수) 번만큼 쌍대가 필요하기 때문에 데이터 개수가 커질수록 계산량이 더 중요해진다.

$\sqrt{(x_1-u_1)^2+(x_2-u_1)^2+\cdot\cdot\cdot+(x_p-u_p)^2}$

※ 맨하탄 거리(Manhattan distance)

- 맨하탄 거리는 한 번에 대각선이 아닌 한 축방향으로만 움직일 수 있다고 할 때, 두 점 사이의 거리라고 할 수 있다.

- 점과 점 사이의 이동 시간으로 근접성을 따질 때 좋은 지표가 된다.

$\mid{x_1-u_1}\mid+\mid{x_2-u_2}\mid+\cdot\cdot\cdot+\mid{x_p-u_p}\mid$

2) 원-핫 인코더

- 대부분의 통계 모델이나 머신러닝 모델에서 몇 가지 요인(문자열) 변수를 포함하고 있는 형태의 변수는, 같은 정보를 담고 있는 이진 가변수의 집합으로 변환해야 한다.

- 선형회귀나 로지스틱 회귀에서 원-핫 인코딩은 다중공선성과 관련된 문제를 일으킨다. 이런 경우 한 가변수를 생략하는 방법이 있다. 하지만, KNN이나 다른 방법에서는 이것이 문제가 되지 않는다.

3) 표준화(정규화, z점수)

- 표준화 혹은 정규화란, 모든 편수에서 평균을 빼고 표준편차로 나누는 과정을 통해 변수들을 모두 비슷한 스케일에 놓는다.

$z = \frac{x-\bar{x}}{s}$

- 이 값을 일반적으로 z 점수라고 부른다. 이는 평균으로부터 표준편차만큼 얼마나 떨어져 있는지를 의미한다. 이를 통해 변수의 스케일로 인한 영향을 줄일 수 있다.

- KNN이나 다른 알고리즘(예로 주성분분석과 클러스터링)에서는 데이터를 미리 표준화하는 것이 필수이다.

4) K 선택하기

- K를 잘 선택하는 것은 KNN의 성능을 결정하는 아주 중요한 요소이다.

- K가 너무 작으면 데이터의 노이즈 성분까지 고려하는 오버피팅 문제가 발생한다.

- K 값이 클수록 결정 함수를 좀 더 부드럽게 하는 효과를 가져와 학습 데이터에서의 오버피팅 위험을 낮출 수 있다.

- 반대로 K를 너무 크게 하면 결정 함수가 너무 과하게 평탄화되어(오버스무딩) 데이터의 지역 정보를 예측하는 KNN의 기능을 잃어버리게 된다.

- 특히 홀드아웃 데이터 또는 타당성검사를 위해 따로 떼어놓은 데이터에서의 정확도를 가지고 K 값을 결정하는 데 사용한다.

5) KNN을 통한 피처 엔지니어링

- KNN은 구현이 간단하고 직관적이다 보니 널리 활용된다.

- 성능 면에서는, 다른 복잡한 분류 방법들에 비해 그렇게 경쟁력이 있다고 보기 어렵다.

- 실용적인 측면에서, 다른 분류 방법들의 특정 단계에 사용할 수 있게 모델에 '지역적 정보(local knowledge)'를 추가하기 위해 KNN을 사용할 수 있다.

• KNN은 데이터에 기반하여 분류 결과(클래스에 속할 확률)를 얻는다.
• 이 결과는 해당 레코드에 새로운 특징(피처)으로 추가된다. 이 결과를 다른 분류 방법에 사용한다. 원래의 예측변수들을 두 번씩 사용하는 셈이 된다.

- 예측 능력을 높이기 위해 피처(예측 변수)들을 새롭게 만들어내기 위한, '피처 엔지니어링' 개념으로 볼 수 있다.

- K 최근접 이웃(KNN) 방법이란 유사한 레코드들이 속한 클래스로 레코드를 분류하는 방법이다.
- 유사성(거리)은 유클리드 거리나 다른 관련 지표들을 이용해 결정한다.
- 가장 가까운 이웃 데이터의 개수를 의미하는 K는 학습 데이터에서 얼마나 좋은 성능을 보이는지를 가지고 결정한다.
- 일반적으로 예측변수들을 표준화한다. 이를 통해 스케일이 큰 변수들의 영향력이 너무 커지지 않도록 한다.
- 예측 모델링의 첫 단계에서 종종 KNN을 사용한다. 이렇게 얻은 값을 다시 데이터에 하나의 예측변수로 추가해서 두 번째 단계의 (KNN이 아닌) 모델링을 위해 사용한다.

2. 트리 모델

- 트리 모델은 회귀 및 분석 트리(CART; classification and regression tree), 의사 결정 트리(decision tree), 혹은 단순히 그냥 트리(tree)라고도 불린다.

- 트리 모델들과 여기서 파생된 강력한 랜덤 포레스트(random forest)와 부스팅 같은 방법들은 회귀나 분류 문제를 위해 데이터 과학에서 가장 널리 사용되는 강력한 예측 모델링 기법들의 기초라고 할 수 있다.

- 트리 모델이란 if-then-else 규칙의 집합체라고 할 수 있다. 따라서 이해하기도 쉽고 구현하기도 쉽다.

- 회귀나 로지스틱 회귀와 반대로 트리는 데이터에 존재하는 복잡한 상호관계에 따른 숨겨진 패턴들을 발견하는 능력이 있다.

- KNN이나 나이브 베이즈 모델과 달리, 예측변수들 사이의 관계로 단순 트리 모델을 표시할 수 있고 쉽게 해석이 가능하다.

- 트리 모델을 얻기 위해 사용되는 R 패키지로는 rpart와 tree가 있다.

1) 재귀 분할 알고리즘

- 재귀 분할은 간단하면서도 직관적인 방법이다. 예측변수 값을 기준으로 데이터를 반복적으로 분할해나간다. 분할할 때에는 상대적으로 같은 클래스의 데이터들끼리 구분되도록 한다.

- 응답변수 $Y$와 $P$개의 예측변수 집합 $X_j(j=1,\cdot\cdot\cdot,P)$가 있다고 가정하자.

1. 각 예측변수 $X_j$에 대해.
   1. $X_j$에 해당하는 각 변수 $s_j$에 대해
      1. $A$에 해당하는 모든 레코드 $X_j < s_j$인 부분과 나머지 $X_j \geq s_j$인 부분으로 나눈다.
      2. $A$의 각 하위 분할 영역 안에 해당 클래스의 동질성을 측정한다.
   2. 하위 분할 영역 내에서의 클래스 동질성이 가장 큰 $s_j$ 값을 선택한다.
2. 클래스 동질성이 가장 큰 변수 $X_j$와 $s_j$ 값을 선택한다

- 알고리즘의 재귀부분

1. 전체 데이터를 가지고 $A$를 초기화한다.
2. $A$를 두 부분 $A_1$과 $A_2$로 나누기 위해 분할 알고리즘을 적용한다.
3. $A_1$과 $A_2$ 각각에서 2번 과정을 반복한다.
4. 분할을 해도 더 이상 하위 분할 영역의 동질성이 개선되지 않을 정도로 충분히 분할을 진행했을 때, 알고리즘을 종료한다.

- 각 영역은 해당 영역에 속한 응답변수들의 다수결 결과에 따라 0 또는 1로 예측결과를 결정한다.

2) 동질성과 불순도 측정하기

- 각 분할 영역에 대한 동질성, 즉 클래스 순도(class purity)를 측정하는 방법이 필요하다.

- 해당 파티션 내에서 오분류된 레코드의 비율 $p$로 예측의 정확도를 표시할 수 있으며 이는 0(완전)에서 0.5(순수 랜덤 추측) 사이의 값을 갖는다.

- 지니 불순도(Gini impurity)와 엔트로피(entropy)가 대표적인 불순도 측정 지표이다.

- 분할 영역 $A$의 지니 불순도와 엔트로피는 아래와 같다.

- 지니 불순도 : $I(A) = p(1-p)$

- 앤트로피 :  $I(A) = -p log_{2}(p)-(1-p)log_{2}(1-p)$

* 지니 불순도를 지니 계수(Gini coefficient)와 혼동하지 않도록 한다. 둘 다 모두 개념적으로 비슷하지만 지니 계수는 이진 분류 문제로 한정되며, AUC 지표와 관련이 있는 용어다.

3) 트리 형성 중지하기

- 가지치기를 하는 가장 일반적인 방법은 홀드아웃 데이터에서의 에러가 최소가 되는 지점까지 가지치기를 진행하는 것이다.

- 좋은 일반화 성능을 얻기 위해 언제 트리 성장을 멈춰야 하는지 결정하는 방법이 필요하다. 가지 분할을 멈추는 대표적인 두 가지 방법이 있다.

• 분할을 통해 얻어지는 하위 영역 또는 말단 잎의 크기가 너무 작다면 분할하는 것을 멈춘다. rpart 함수에서 minsplit이나 minbucket 같은 파라미터를 이용해 최소 분할 영역 크기나 말단 잎의 크기를 조절할 수 있다. 기본값은 각각 20과 70이다.
• 새로운 분할 영역이 '유의미'한 정도로 불순도를 줄이지 않는다면 굳이 분할하지 않는다. rprat 함수에서 트리의 복잡도를 의미하는 복잡도 파라미터(complecity parameter)인 cp를 이용해 이를 조절한다. 트리가 복잡해질 수록 cp의 값이 증가한다. 실무에서는 트리의 복잡도가 추가적으로 늘어나는 만큼 cp를 벌점으로 간주해 트리성장을 제한하는 데 사용된다.

- 첫 번째 방법은 탐색 작업에 유용할 수 있지만 최적값(새로운 데이터에 대한 예측 정확도를 최대화하기 위한 값)을 결정하기가 매우 어렵다. 복잡도 파라미터 cp를 이용하면 어떤 크기의 트리가 새로운 데이터에 대해 가장 좋은 성능을 보일지 추정할 수 있다.

• cp가 매우 작다면 트리는 실제 의미 있는 신호뿐 아니라 노이즈까지 학습하여 오버피팅되는 문제가 발생한다.
• cp가 너무 크다면 트리가 너무 작아 예측 능력을 거의 갖지 못한다.

- 최적의 cp를 결정하는 것은 편향-분산 트레이드오프를 보여주는 하나의 대표적인 예이다.

- cp를 추정하는 가장 일반적인 방법은 교차타당성 검정을 이용하는 것이다.

1. 데이터를 학습용 데이터와 타당성검사용 (홀드아웃) 데이터로 나눈다.
2. 학습 데이터를 이용해 트리를 키운다.
3. 트리를 단계적으로 계속해서 가지치기한다. 매 단계마다 학습 데이터를 이용해 cp를 기록한다.
4. 타당성검사 데이터에 대해 최소 에러(손실)를 보이는 cp를 기록한다.
5. 데이터를 다시 학습용 데이터와 타당성검사용 데이터로 나누고, 마찬가지로 트리를 만들고 가지치기하고 cp를 기록하는 과정을 반복한다.
6. 이를 여러 번 반복한 후 각 트리에서 최소 에러를 보이는 cp 값의 평균을 구한다.
7. 원래 데이터를 이용해 위에서 구한 cp의 최적값을 가지고 트리를 만든다.

4) 트리 활용하기

* 트리 모델의 장점

• 트리 모델은 데이터 탐색을 위한 시각화가 가능하다. 이는 어떤 변수가 중요하고 변수 간에 어떤 관계가 있는지를 보여준다. 트리 모델은 예측변수들 간의 비선형 관계를 담아낼 수 있다.
• 트리 모델은 일종의 규칙들의 집합이라고 볼 수 있다. 따라서 실제 구현 방법에 대해서, 아니면 데이터 마이닝 프로젝트 홍보에 대해서 비전문가들과 대화하는 데 아주 효과적이라고 할 수 있다.

- 예측에 관해서는, 다중 트리에서 나온 결과를 이용하는 것이 단일 트리를 이용하는 것보다 보통은 훨씬 강력하다.

- 특히, 랜덤 포레스트와 부스팅 트리 알고리즘은 거의 항상 우수한 예측 정확도나 성능을 보여준다.

- 의사 결정 트리는 결과를 분류하거나 예측하기 위한 일련의 규칙들을 생성한다.
- 이 규칙들은 데이터를 하위 영역으로 연속적으로 분할하는 것과 관련이 있다.
- 각 분할 혹은 분기는 어떤 한 예측변수 값을 기준으로 데이터를 위아래 두 부분으로 나누는 것이다.
- 각 단계마다, 트리 알고리즘은 결과의 불순도를 최소화하는 쪽으로 영역 분할을 진행한다.
- 더 이상 분할이 불가능할 때, 트리가 완전히 자랐다고 볼 수 있으며 각 말단 노드 혹은 잎 노드에 해당하는 레코드들은 단일 클래스에 속한다. 새로운 데이터는 이 규칙 경로를 따라 해당 클래스로 할당된다.
- 완전히 자란 트리는 데이터를 오버피팅하기 때문에, 노이즈를 제외한 신호에만 반응하도록 트리에 가지치기를 수행해야 한다.
- 랜덤 포레스트나 부스팅 트리 같은 다중 트리 알고리즘은 우수한 예측 성능을 보장한다. 하지만 규칙에 기반을 둔 단일 트리의 방법의 장점이라고 할 수 있는 전달 능력은 잃어버린다.

< 참고자료 >
1. Peter Brucs & Andrew Brucs(2018). 데이터 과학을 위한 통계. 한빛미디어. 이용준 옮김.