Classification tree
Regression tree
데이터셋 S
데이터 포인트 $c_1,....,c_n$
- 모든 데이터 포인트가 단 하나의 클래스에 속한다면 엔트로피는 낮고,
- 모든 데이터 포인트가 모든 클래스에 고르게 분포되어 있다면 엔트로피는 높다
In [2]:
from collections import Counter, defaultdict
from functools import partial
import math, random
In [3]:
def entropy(class_probabilities):
"""클래스에 속할 확률을 입력하면 엔트로피를 계산하라"""
return sum(-p * math.log(p, 2) for p in class_probabilities if p)
In [4]:
#각 클래스 레이블의 확률은 별도로 계산
#엔트로피를 구할 때는 어떤 레이블에 어떤 확률값이 주어졌는지까지는 알 필요가 없고,
#레이블과 무관하게 확률 값들만 알면됨
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)
In [5]:
def partition_entropy(subsets):
"""subsets는 레이블이 있는 데이터의 list의 list이다.
그에 대한 파티션 엔트로피를 구하라"""
total_count = sum(len(subset) for subset in subsets)
return sum( data_entropy(subset) * len(subset) / total_count
for subset in subsets )
In [6]:
inputs = [
({'level':'Senior','lang':'Java','tweets':'no','phd':'no'}, False),
({'level':'Senior','lang':'Java','tweets':'no','phd':'yes'}, False),
({'level':'Mid','lang':'Python','tweets':'no','phd':'no'}, True),
({'level':'Junior','lang':'Python','tweets':'no','phd':'no'}, True),
({'level':'Junior','lang':'R','tweets':'yes','phd':'no'}, True),
({'level':'Junior','lang':'R','tweets':'yes','phd':'yes'}, False),
({'level':'Mid','lang':'R','tweets':'yes','phd':'yes'}, True),
({'level':'Senior','lang':'Python','tweets':'no','phd':'no'}, False),
({'level':'Senior','lang':'R','tweets':'yes','phd':'no'}, True),
({'level':'Junior','lang':'Python','tweets':'yes','phd':'no'}, True),
({'level':'Senior','lang':'Python','tweets':'yes','phd':'yes'},True),
({'level':'Mid','lang':'Python','tweets':'no','phd':'yes'}, True),
({'level':'Mid','lang':'Java','tweets':'yes','phd':'no'}, True),
({'level':'Junior','lang':'Python','tweets':'no','phd':'yes'},False)
]
In [7]:
# 1. 가장 낮은 엔트로피를 반환하는 파티션을 찾는다.
def partition_by(inputs, attribute):
"""attribute에 따라 inputs의 파티션을 나누자"""
groups = defaultdict(list)
for input in inputs:
key = input[0][attribute]
groups[key].append(input)
return groups
In [8]:
# 2. 엔트로피를 계산
def partition_entropy_by(inputs,attribute):
"""주어진 파티션에 대응되는 엔트로피를 계산"""
partitions = partition_by(inputs, attribute)
return partition_entropy(partitions.values())
In [9]:
# 3. 전체 데이터셋에 대해 엔트로피를 최소화하는 파티션을 찾는다.
for key in ['level','lang','tweets','phd']:
print(key, partition_entropy_by(inputs, key))
print()
In [10]:
#직급의 가능한 각 값에 대해 가지를 나눠 서브트리를 만들자.
#직급이 Mid인 경우는 예측값이 True
#Senior인 경우 True or False
senior_inputs = [(input, label)
for input, label in inputs if input["level"] == "Senior"]
for key in ['lang', 'tweets', 'phd']:
print(key, partition_entropy_by(senior_inputs, key))
print()
In [11]:
junior_inputs = [(input, label)
for input, label in inputs if input["level"] == "Junior"]
for key in ['lang', 'tweets', 'phd']:
print(key, partition_entropy_by(junior_inputs, key))
print()
직급(level)?
↙(senior) ↓(mid) ↘(junior)
<tweets?> [합격!] <phd?>
↙yes ↘no ↙yes ↘no
[합격!] [불합격!] [불합격!] [합격!]('level',
{'Junior': ('phd', {'no' : True, 'yes': False}),
'Mid': True,
'Senior': ('tweets', {'no': False, 'yes': True})})
In [20]:
def classify(tree, input):
"""의사결정나무 tree로 주어진 입력값 input을 분류"""
# 잎 노드이면 값을 반환
if tree in [True, False]:
return tree
# 그게 아니라면 데이터의 변수로 파티션을 나눔
# key로 변수 값, 값으로 서브트리를 나타내는 dict를 사용하면됨
attribute, subtree_dict = tree
subtree_key = input.get(attribute) # None if input is missing attribute
if subtree_key not in subtree_dict: # 키에 해당하는 서브트리가 존재하지 않을때
subtree_key = None # None 서브트리를 사용
subtree = subtree_dict[subtree_key] # 적절한 서브트리를 선택
return classify(subtree, input) # 입력된 데이터를 분류
In [21]:
def build_tree_id3(inputs, split_candidates=None):
# if this is our first pass,
# all keys of the first input are split candidates
if split_candidates is None:
split_candidates = inputs[0][0].keys()
# count Trues and Falses in the inputs
num_inputs = len(inputs)
num_trues = len([label for item, label in inputs if label])
num_falses = num_inputs - num_trues
if num_trues == 0: # if only Falses are left
return False # return a "False" leaf
if num_falses == 0: # if only Trues are left
return True # return a "True" leaf
if not split_candidates: # if no split candidates left
return num_trues >= num_falses # return the majority leaf
# otherwise, split on the best attribute
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]
# recursively build the subtrees
subtrees = { attribute : build_tree_id3(subset, new_candidates)
for attribute, subset in partitions.items() }
subtrees[None] = num_trues > num_falses # default case
return (best_attribute, subtrees)
In [22]:
print("building the tree")
tree = build_tree_id3(inputs)
print(tree)
In [23]:
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"} ))
In [26]:
#심지어 관찰된 적 없는 값이 변수에 등장하거나 변수 값 자체가 누락되더라도 분류가 가능
print("Intern", classify(tree, { "level" : "Intern" } ))
print("Senior", classify(tree, { "level" : "Senior" } ))
In [25]:
#심지어 관찰된 적 없는 값이 변수에 등장하거나 변수 값 자체가 누락되더라도 분류가 가능
In [27]:
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]
In [ ]: