<jupyter_start><jupyter_text>**밑바닥부터 시작하는 데이터과학**Data Science from Scratch- https://github.com/joelgrus/data-science-from-scratch/blob/master/first-edition/code-python3/decision_trees.py  **17장 의사결정나무**다양한 **의사결정경로** 와 **결과** 를 나타냅니다1. **분류나무 (Classification Tree) :** 범주형 결과를 반환 합니다1. **회귀나무 (Regression Tree) :** 숫자형 결과를 반환 합니다  **1 엔트로피****얼마만큼의 정보를 담고 있는지** 를 확인하는 방법으로 **데이터 불확실성 (uncertainty)** 을 나타 냅니다1. 특정 $ c_i $ 클래스에 속할 확률 $ p_i $ 을 엔트로피로 계산하면 $ H(S) = -p_1 \log_2 p_1 - ... - p_n \log_2 p_n $$1. **데이터가 단일 클래스에 속한** 경우 : **불확실성은 없고 엔트로피는 낮다** (그룹이 안정적)1. **데이터가 클래스에 고르게 분포된** 경우 : **불확실성과 엔트로피가 높다** (파벌이 많다)<jupyter_code>from collections import Counter, defaultdict
from functools import partial
import math, random

# 클래스에 속할 확률을 입력하면 엔트로피를 계산 합니다
def entropy(class_probabilities):
    return sum(-p * math.log(p, 2) for p in class_probabilities if p)

def class_probabilities(labels):
    total_count = len(labels)
    return [count / total_count
            for count in Counter(labels).values()]

def data_entropy(labeled_data):
    labels = [label for _, label in labeled_data]
    probabilities = class_probabilities(labels)
    return entropy(probabilities)<jupyter_output><empty_output><jupyter_text>**2 파티션 엔트로피와 의사결정나무**1. 의사결정나무는 **여러개의 파티션** 으로 분할된 **여러 데이터셋** 을 비교합니다1. **여러개의 파티션** 을 계산하더라도, **전체에 대한 데이터셋 엔트로피 계산이** 필요 합니다1. 데이터 $ S $ 를 $ q_1, ... q_m $ 의 비율을 찾는 파티션 $ S_i, ... S_m $ 을 나누는 공식은 다음과 같습니다$$ H = q_1 H(S_1) + ... + q_m H(S_m) $$<jupyter_code># subsets는 레이블이있는 데이터의 list 입니다
def partition_entropy(subsets):
    total_count = sum(len(subset) for subset in subsets)
    return sum( data_entropy(subset) * len(subset) / total_count
                for subset in subsets )<jupyter_output><empty_output><jupyter_text>**3 의사결정나무 만들기**의사결정나무는 **결정노드 (Decison Node)** 와 **잎 노드 (leaf node)** 로 구성됩니다1. **결정노드 (Decison Node) :** 질문의 답에 따른 경로를 안내 합니다1. **잎 노드 (leaf node) :** 예측값이 무엇인지를 알려 줍니다<jupyter_code>import json
with open('./data/data.json', 'r') as f:
    inputs = json.load(f)
inputs = inputs['inputs']
len(inputs), inputs[:2]
# attribute 에 따라 inputs 의 파티션을 나눕니다
def group_by(items, key_fn):
    groups = defaultdict(list)
    for item in items:
        key = key_fn(item)
        groups[key].append(item)
    return groups

def partition_by(inputs, attribute):
    return group_by(inputs, lambda x: x[0][attribute])

# 주어진 파티션에 대응되는 엔트로피 계산하기
def partition_entropy_by(inputs,attribute):
    partitions = partition_by(inputs, attribute)
    return partition_entropy(partitions.values())

# 각 데이터에 엔트로피를 최소로 하는 파티션을 찾습니다
for key in ['level','lang','tweets','phd']:
    print(key, ":", partition_entropy_by(inputs, key))
# 직급(level) 을 기준으로 나눌 때 최소 엔트로피를 갖습니다
# 이를 기준으로 직급을 기준으로 SubTree 를 생성합니다.
senior_inputs = [(input, label)
                 for input, label in inputs if input["level"] == "Senior"]

# 위 분석결과 tweets 값이 0으로, 다음 분류기준이 됩니다
for key in ['lang', 'tweets', 'phd']:
    print(key, partition_entropy_by(senior_inputs, key))<jupyter_output>lang 0.4
tweets 0.0
phd 0.9509775004326938<jupyter_text>**5 종합하기**보다 일반화된 방법을 적용해 보겠습니다<jupyter_code># 실제 Tree 구축용 함수
def build_tree_id3(inputs, split_candidates=None):
    # partition 첫단계 실행
    if split_candidates is None:
        split_candidates = inputs[0][0].keys()

    num_inputs = len(inputs) # 입력 데이터에서 True, False 갯수를 확인
    num_trues  = len([label for item, label in inputs if label])
    num_falses = num_inputs - num_trues
    if num_trues  == 0: return False    # True 가 없을때 False 반환
    if num_falses == 0: return True     # False 가 없을때 True 반환
    if not split_candidates:            # 파티션 기준사용할 변수가 없을 때
        return num_trues >= num_falses  # 다수결로 결과를 출력
    
    best_attribute = min(split_candidates,  # 적합한 변수로 파티션을 나눈다
        key=partial(partition_entropy_by, inputs))
    partitions = partition_by(inputs, best_attribute)
    new_candidates = [a for a in split_candidates if a != best_attribute]

    # 재귀적 방법으로 서브Tree 를 구축합니다
    subtrees = { attribute : build_tree_id3(subset, new_candidates)
                 for attribute, subset in partitions.items() }
    subtrees[None] = num_trues > num_falses   # 기본값
    return (best_attribute, subtrees)

print("building the tree")
tree = build_tree_id3(inputs)
tree
# 의사 결정나무 Tree 로 주어진 입력값 inputs 을 분류 합니다
def classify(tree, input):
    # leaf 노드일 때 값을 반환합니다
    if tree in [True, False]: 
        return tree
    # 위에 비해당시 Partition 을 나눕니다
    attribute, subtree_dict = tree
    subtree_key = input.get(attribute)  
    # subtree 가 존재하지 않을 때 None 서브트리를 추가
    if subtree_key not in subtree_dict: 
        subtree_key = None
    # 적절한 SubTree 를 선택합니다
    subtree = subtree_dict[subtree_key]
    return classify(subtree, input)

print("Junior / Java / tweets / no phd", classify(tree,
    { "level" : "Junior",
      "lang" : "Java",
      "tweets" : "yes",
      "phd" : "no"} ))
print("Junior / Java / tweets / phd", classify(tree,
    { "level" : "Junior",
             "lang" : "Java",
             "tweets" : "yes",
             "phd" : "yes"} ))
print("Intern :", classify(tree, { "level" : "Intern" } ))
print("Senior :", classify(tree, { "level" : "Senior" } ))<jupyter_output>Intern : True
Senior : False<jupyter_text>**6 랜덤 포레스트**결정나무의 한계인 **OverFitting**을 방지하는 방법으로 **여러개의 결정나무를 만든 뒤, 다수결과 결과를 결정** 하는 방법 입니다.1. 랜덤한 모델을 찾기위해서 **bootstrap** 을 활용 합니다1. 즉 inputs 이 아닌, **bootstrap_sample(input)** 로 여러모델을 학습한 뒤 결정을 합니다1. 이러한 방식을 **bootstrap aggregation** 또는 **bagging(배깅)** 이라고 합니다<jupyter_code>def forest_classify(trees, input):
    votes       = [classify(tree, input) for tree in trees]
    vote_counts = Counter(votes)
    return vote_counts.most_common(1)[0][0]<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.12449231855906763, 'fraction_numerical': 0.011124845488257108, 'mean_word_length': 3.6086248982912936, 'pattern_counts': {'":': 1, '<': 19, '<?xml version=': 0, '>': 21, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '5', 'dir': 'jupyter-structured-clean-dedup', 'id': '498673', 'license': 'MIT', 'n_tokens_mistral': 2791, 'n_tokens_neox': 3288, 'n_words': 620, 'path': '16.DecisionTree.ipynb', 'repo_name': 'YongBeomKim/data-science-from-scratch', 'size': '5663'}