جواب «Step 2: Grow the Advisor Tree» چالش 2 از جلسهی 52
سؤال
قدم ۲: داده به ۲۱ نفر آموزش و ۷ نفر آزمون تقسیم شده و تابعهای جلسههای ۵۰ و ۵۱ آمدهاند، اما build بخش تقسیم و صدا زدن بازگشتی را ندارد. آن را کامل کن. بعد از خروجی قدم ۱ باید قانونها بیاید (ده خط، از if art < 16: تا -> art، با if maths < 17: در عمق سوم) و بعد train: 20 / 21.
راهنما
هر ردیف با rows[i][f] < t به چپ یا راست برود؛ بعد build(left_rows, left_labels, depth + 1, max_depth, min_samples) و همین برای راست.
یک جواب درست
DATA = '''
maths,science,literature,art,likes_people,likes_building,field
18,15,12,10,0,1,maths
17,14,13,11,0,1,maths
19,16,11,9,1,1,maths
16,13,14,12,0,1,maths
18,17,12,13,0,0,maths
15,14,10,11,0,1,maths
17,12,15,10,1,1,maths
14,18,13,10,1,0,science
15,19,12,11,1,0,science
13,17,14,12,1,0,science
16,18,11,10,1,0,science
12,16,15,13,1,0,science
15,17,13,9,0,0,science
14,16,12,14,1,1,science
11,12,18,13,1,0,humanities
10,13,17,12,1,0,humanities
12,11,19,14,1,0,humanities
13,14,16,11,1,0,humanities
9,12,18,15,0,0,humanities
12,13,17,10,1,1,humanities
11,15,16,12,1,0,humanities
10,11,14,18,0,0,art
12,12,15,19,1,0,art
11,13,13,17,0,1,art
13,11,16,18,1,0,art
9,10,14,16,0,0,art
14,12,12,17,0,1,art
12,14,15,16,1,0,art
'''.strip()
lines = DATA.splitlines()
names = lines[0].split(",")[:-1]
rows = []
labels = []
for line in lines[1:]:
parts = line.split(",")
rows.append([int(v) for v in parts[:-1]])
labels.append(parts[-1])
print("features:", names)
print("students:", len(rows))
for field in ["maths", "science", "humanities", "art"]:
print(field, labels.count(field))
# ---- step 2: build the tree on 3 of every 4 students
train_rows = [rows[i] for i in range(len(rows)) if i % 4 != 3]
train_labels = [labels[i] for i in range(len(rows)) if i % 4 != 3]
test_rows = [rows[i] for i in range(len(rows)) if i % 4 == 3]
test_labels = [labels[i] for i in range(len(rows)) if i % 4 == 3]
def gini(group):
if len(group) == 0:
return 0.0
score = 1.0
for c in sorted(set(group)):
p = group.count(c) / len(group)
score -= p * p
return score
def split(rows, labels, f, t):
left = [labels[i] for i in range(len(rows)) if rows[i][f] < t]
right = [labels[i] for i in range(len(rows)) if rows[i][f] >= t]
return left, right
def weighted_gini(left, right):
n = len(left) + len(right)
return len(left) / n * gini(left) + len(right) / n * gini(right)
def best_split(rows, labels):
best = None
for f in range(len(rows[0])):
for t in sorted(set(row[f] for row in rows))[1:]:
left, right = split(rows, labels, f, t)
score = weighted_gini(left, right)
if best is None or score < best[0]:
best = (score, f, t)
return best
def majority(labels):
return max(sorted(set(labels)), key=labels.count)
def build(rows, labels, depth, max_depth, min_samples):
if depth == max_depth or len(rows) < min_samples or gini(labels) == 0:
return {"leaf": majority(labels)}
best = best_split(rows, labels)
if best is None:
return {"leaf": majority(labels)}
score, f, t = best
left_rows, left_labels, right_rows, right_labels = [], [], [], []
for i in range(len(rows)):
if rows[i][f] < t:
left_rows.append(rows[i])
left_labels.append(labels[i])
else:
right_rows.append(rows[i])
right_labels.append(labels[i])
left = build(left_rows, left_labels, depth + 1, max_depth, min_samples)
right = build(right_rows, right_labels, depth + 1, max_depth, min_samples)
if "leaf" in left and "leaf" in right and left["leaf"] == right["leaf"]:
return left # both sides say the same thing: the question is useless
return {"feature": f, "threshold": t, "left": left, "right": right}
def predict(node, row):
while "leaf" not in node:
if row[node["feature"]] < node["threshold"]:
node = node["left"]
else:
node = node["right"]
return node["leaf"]
def print_rules(node, names, indent=""):
if "leaf" in node:
print(indent + "-> " + node["leaf"])
return
print(indent + "if " + names[node["feature"]] + " < " + str(node["threshold"]) + ":")
print_rules(node["left"], names, indent + " ")
print(indent + "else:")
print_rules(node["right"], names, indent + " ")
tree = build(train_rows, train_labels, 0, 3, 2)
print_rules(tree, names)
right = sum(1 for i in range(len(train_rows)) if predict(tree, train_rows[i]) == train_labels[i])
print("train:", right, "/", len(train_rows))
اول خودت امتحان کن؛ جوابهای دیگر هم قبول است. برگرد و خودت حلش کن