The Quest for Machine Learning - Chap3 Classic machine learning algorithms

로지스틱 회귀

선형회귀와 비교했을 때 로지스틱 회귀의 다른 점

로지스틱 회귀는 주로 분류 문제에 사용되고, 선형 회귀는 회귀 문제에 사용됨

로지스틱 회귀는 독립변수와 하이퍼파라미터가 주어졌을 때 종속변수의 기댓값을 얻고, 해당 기댓값에 기반하여 분류 문제를 예측 => $E[y|x;\theta]$

선형회귀는 $y'=\theta^T x + \epsilon$ 의 해를 구하는데 목적이 있음

로지스틱 회귀 공식

$$
\log \frac{p}{1-p} = \theta^T x
$$

$p = P(y=1|x)$ 는 입력 x가 주어졌을 때 양성 클래스로 예측할 확률

한 사건의 odds가 발생확률과 발생하지 않을 확률의 비율 $\frac{p}{1-p}$ 라고 한다면,
로지스틱 회귀는 $y=1|x$ 에 대한 이 사건의 log odds의 선형회귀

Decision Tree

각 Decision Tree 알고리즘에서 사용하는 Heuristic 함수

의사결정 트리 알고리즘의 종류는 ID3, C4.5, CART 등이 있음

ID3 - 최대 정보 이득

1. 샘플 집합 D에 대해 클래스 수가 K인 데이터 세트 D의 empirical entropy

$$
H(D) = - \displaystyle\sum^{k}_{k=1} \frac{|C_k|}{|D|} \log_2 \frac{|C_k|}{|D|}
$$
$C_k$ : 샘플 집합 D에서 k번째 부분집합
$|C_k|$ : 해당 부분 집합 원소의 개수
$|D|$ : 샘플 집합의 원소 개소

2. 샘플 집합 D에 대한 어떤 특징 A의 empirical entropy $H(D|A)$

3. Information Gain $g(D, A)$는 양자 사이의 차이로 나타내게 됨

$$
g(D, A) = H(D) - H(D|A)
$$

분기는 가장 높은 IG를 얻는 방향으로 분할됨

C4.5 - 최대 정보 이득비

데이터 셋 D에 대한 특징 A의 정보 이득비(Information gain ratio)는

$$
g_R(D, A) = \frac{g(D, A)}{H_A(D)}
$$

$H_A(D)$ 는 데이터 셋 D의 A에 관한 엔트로피의 값

CART - 최대 지니 계수

Gini는 데이터의 순도를 의미

$$
Gini(D) = 1 - \displaystyle\sum_{k=1}^{n} \Big( \frac{|C_k|}{|D|} \Big)^2
$$

CART 알고리즘은 매 회마다 지니 계수가 가장 작은 특징과 그에 대응하는 최적의 분리점을 선택해 분류
CART는 이진 트리로, 특징 A에 값에 따라 둘로 나누어 각각을 sub-tree로 보냄

$$
Gini(D|A) = \displaystyle\sum_{i=1}^{n} \frac{|D_i|}{|D|} Gini(D_i)
$$

정리

ID3

• 특징: ID3는 채택 능력 외에 취할 수 있는 값이 많은 특성을 선택하는 경향이 있음
  Information Gain이 반영하는 것은 일정한 조건이 정해진 후 불확실성이 감소하는 정도이기 때문임
  특성에 값이 다양하다는 것은 불순도가 높다는 의미이고, 조건 엔트로피가 작을수록 ig가 커지는 것
• 단점: 모든 데이터마다 다른 값을 가진 특성의 경우는 ID3 알고리즘 사용시에 조건 엔트로피가 0이 되어 일반화 능력이 약함 -> 따라서 C4.5로 ID3에 대해 최적화
• 이산형 변수만 처리 가능
• 분류 문제에 사용가능
• 각 노드에서 여러 branch로 분기 가능 -> 한번 사용한 특성은 하위노드에서 사용 불가
• branching 조정으로 트리의 정확성 및 일반화 컨트롤 가능

C4.5

• 특징: Information Gain 'RATIO' 를 사용함으로써 어느 정도 값이 많은 특성에 대해 페널티를 부여하여 overfitting된 특성이 나타나는 것을 방지하고, Decision tree의 일반화 성능을 향상
• 연속형 변수 처리 가능
• 데이터를 정렬한 후 클래스가 다른 분할선을 분기점으로 설정해서 여러 구간의 이산형 변수로 변환해 분기
• 분류 문제에 사용 가능
• 각 노드에서 여러 branch로 분기 가능 -> 한번 사용한 특성은 하위노드에서 사용 불가
• branching 조정으로 트리의 정확성 및 일반화 컨트롤 가능

CART

• 연속형 변수 처리 가능
• 특성에 대해 이진분할 (Scikit-Learn에서 이 방식 사용) -> 하위 노드에서 특성 다시 사용 가능
• 분류 / 회귀 모두 사용 가능 (회귀에서는 MSE 사용)
• 모든 데이터를 사용해 가능한 트리 구조를 만들어 비교