ทำความเข้าใจโดยการนำไปใช้: แผนผังการตัดสินใจ

เผยแพร่ซ้ำโดยเพลโต

ผู้ติดตาม: 0

ความเข้าใจโดยการดำเนินการ: ต้นไม้การตัดสินใจ
ภาพโดยผู้เขียน

โมเดลแมชชีนเลิร์นนิงขั้นสูงมากมาย เช่น ป่าสุ่มหรืออัลกอริธึมการเพิ่มการไล่ระดับสี เช่น XGBoost, CatBoost หรือ LightGBM (และแม้กระทั่ง ตัวเข้ารหัสอัตโนมัติ!) อาศัยส่วนผสมร่วมที่สำคัญ: the ต้นไม้ตัดสินใจ!

หากปราศจากความเข้าใจแผนผังการตัดสินใจ ก็เป็นไปไม่ได้เลยที่จะเข้าใจอัลกอริทึมการบรรจุถุงขั้นสูงหรือการเพิ่มการไล่ระดับสีใดๆ ที่กล่าวมาข้างต้น ซึ่งเป็นเรื่องน่าอับอายสำหรับนักวิทยาศาสตร์ข้อมูลทุกคน! ดังนั้น ให้เราเข้าใจการทำงานภายในของแผนผังการตัดสินใจโดยการใช้หนึ่งใน Python

ในบทความนี้คุณจะได้เรียนรู้

เหตุผลและวิธีที่ต้นไม้การตัดสินใจแยกข้อมูล
ข้อมูลที่ได้รับและ
วิธีใช้แผนผังการตัดสินใจใน Python โดยใช้ NumPy

คุณสามารถหารหัสได้ที่ Github ของฉัน.

ต้นไม้ตัดสินใจขึ้นอยู่กับการทำนาย รุนแรง ชุดข้อมูลออกเป็นส่วนย่อยๆ ในแบบเรียกซ้ำ

ความเข้าใจโดยการดำเนินการ: ต้นไม้การตัดสินใจ
ภาพโดยผู้เขียน

ในภาพด้านบน คุณจะเห็นตัวอย่างหนึ่งของการแยก — ชุดข้อมูลดั้งเดิมถูกแยกออกเป็นสองส่วน ในขั้นตอนต่อไป ทั้งสองส่วนจะถูกแยกออกอีกครั้ง และอื่นๆ สิ่งนี้จะดำเนินต่อไปจนกว่าจะถึงเกณฑ์การหยุดบางอย่าง เช่น

หากการแยกส่งผลให้ส่วนหนึ่งว่างเปล่า
หากถึงความลึกของการเรียกซ้ำ
ถ้า (หลังจากการแยกครั้งก่อน) ชุดข้อมูลประกอบด้วยเพียงไม่กี่องค์ประกอบ ทำให้การแยกเพิ่มเติมไม่จำเป็น

เราจะหารอยแยกเหล่านี้ได้อย่างไร? และทำไมเราถึงสนใจ? ลองหากัน

แรงจูงใจ

สมมติว่าเราต้องการแก้ a ไบนารี ปัญหาการจำแนกประเภท ที่เราสร้างขึ้นเองในขณะนี้:

import numpy as np
np.random.seed(0) X = np.random.randn(100, 2) # features
y = ((X[:, 0] > 0) * (X[:, 1] < 0)) # labels (0 and 1)

ข้อมูลสองมิติมีลักษณะดังนี้:

ความเข้าใจโดยการดำเนินการ: ต้นไม้การตัดสินใจ
ภาพโดยผู้เขียน

เราจะเห็นว่ามีสองคลาสที่แตกต่างกัน — สีม่วงประมาณ 75% และสีเหลืองประมาณ 25% ของกรณี หากคุณป้อนข้อมูลนี้ไปยังแผนผังการตัดสินใจ จำแนกต้นนี้มีความดำริดังนี้

“มีสองป้ายที่แตกต่างกัน ซึ่งยุ่งเกินไปสำหรับฉัน ฉันต้องการขจัดความยุ่งเหยิงนี้ด้วยการแบ่งข้อมูลออกเป็นสองส่วน ส่วนเหล่านี้ควรจะสะอาดกว่าข้อมูลทั้งหมดก่อนหน้านี้” — ต้นไม้ที่ได้สติ

ต้นไม้ก็เช่นกัน

ความเข้าใจโดยการดำเนินการ: ต้นไม้การตัดสินใจ
ภาพโดยผู้เขียน

ต้นไม้ตัดสินใจที่จะแยกออกตามแนว x-แกน. สิ่งนี้มีผลให้ส่วนบนสุดของข้อมูลสมบูรณ์แบบ สะอาด หมายความว่าคุณจะพบเท่านั้น ชั้นเดียว (สีม่วงในกรณีนี้) ที่นั่น

อย่างไรก็ตามส่วนล่างยังคงอยู่ ยุ่งแม้จะยุ่งกว่าเดิมในแง่หนึ่ง อัตราส่วนคลาสเคยอยู่ที่ประมาณ 75:25 ในชุดข้อมูลทั้งหมด แต่ในส่วนที่เล็กกว่านี้จะอยู่ที่ประมาณ 50:50 ซึ่งผสมกันเท่าที่จะเป็นไปได้

หมายเหตุ ที่นี่ไม่สำคัญว่าสีม่วงและสีเหลืองจะแยกออกจากกันอย่างสวยงามในภาพ เพียงแค่ จำนวนดิบของฉลากต่างๆ ในสองส่วนนับ.

ความเข้าใจโดยการดำเนินการ: ต้นไม้การตัดสินใจ
ภาพโดยผู้เขียน

ถึงกระนั้น นี่ก็ยังดีพอสำหรับก้าวแรกสำหรับต้นไม้ และมันก็ดำเนินต่อไป แม้ว่ามันจะไม่ทำให้เกิดการแตกแยกอีกในด้านบน ปลาเดยส์ อีกต่อไปก็สามารถสร้างรอยแยกด้านล่างขึ้นมาใหม่เพื่อทำความสะอาดได้

ความเข้าใจโดยการดำเนินการ: ต้นไม้การตัดสินใจ
ภาพโดยผู้เขียน

อีกอย่าง, แต่ละส่วนที่แยกจากกันทั้งสามนั้นสะอาดหมดจด, เนื่องจากเราพบเพียงสีเดียว (ฉลาก) ต่อส่วน.

การคาดการณ์เป็นเรื่องง่ายมากในตอนนี้: หากมีจุดข้อมูลใหม่เข้ามา คุณเพียงแค่ตรวจสอบว่าจุดใด สามส่วน มันอยู่และให้สีที่สอดคล้องกัน ตอนนี้ทำงานได้ดีเพราะแต่ละส่วนคือ ปลาเดยส์. ง่ายใช่มั้ย?

ความเข้าใจโดยการดำเนินการ: ต้นไม้การตัดสินใจ
ภาพโดยผู้เขียน

ตกลงเรากำลังพูดถึง ปลาเดยส์ และ ยุ่ง ข้อมูล แต่จนถึงขณะนี้คำเหล่านี้เป็นเพียงแนวคิดที่คลุมเครือเท่านั้น การที่เราจะนำอะไรไปปฏิบัติเราต้องหาวิธีกำหนด การรักษาความสะอาด.

มาตรการรักษาความสะอาด

สมมติว่าเรามีป้ายกำกับบางอย่าง ตัวอย่างเช่น

y_1 = [0, 0, 0, 0, 0, 0, 0, 0] y_2 = [1, 0, 0, 0, 0, 0, 1, 0]
y_3 = [1, 0, 1, 1, 0, 0, 1, 0]

โดยสัญชาตญาณ ใช่₁ เป็นฉลากชุดที่สะอาดที่สุดรองลงมา ใช่₂ แล้วก็ ย₃. จนถึงตอนนี้ดีมาก แต่เราจะใส่ตัวเลขให้กับพฤติกรรมนี้ได้อย่างไร? บางทีสิ่งที่ง่ายที่สุดที่นึกถึงคือสิ่งต่อไปนี้:

แค่นับจำนวนศูนย์และจำนวนหนึ่ง คำนวณผลต่างสัมบูรณ์ เพื่อให้ดีขึ้น ให้ทำให้เป็นมาตรฐานโดยการหารด้วยความยาวของอาร์เรย์

ตัวอย่างเช่น ใช่₂ มีทั้งหมด 8 รายการ — เลขศูนย์ 6 ตัว และเลขศูนย์ 2 ตัว ดังนั้นการกำหนดขึ้นเองของเรา คะแนนความสะอาด จะเป็น |6 – 2| / 8 = 0.5. ง่ายต่อการคำนวณคะแนนความสะอาดของ ใช่₁ และ ย₃ คือ 1.0 และ 0.0 ตามลำดับ ที่นี่ เราสามารถเห็นสูตรทั่วไป:

ความเข้าใจโดยการดำเนินการ: ต้นไม้การตัดสินใจ
ภาพโดยผู้เขียน

ที่นี่ น และ น เป็นจำนวนศูนย์และหนึ่งตามลำดับ n = n₀ + n₁ คือความยาวของอาร์เรย์และ พี₁ = n₁ / n เป็นส่วนแบ่งของ 1 ป้าย

ปัญหาของสูตรนี้คือ ปรับให้เหมาะกับกรณีของสองคลาสโดยเฉพาะแต่บ่อยครั้งที่เราสนใจการจำแนกประเภทหลายชั้น สูตรหนึ่งที่ใช้ได้ดีทีเดียวคือ วัดสิ่งเจือปน Gini:

ความเข้าใจโดยการดำเนินการ: ต้นไม้การตัดสินใจ
ภาพโดยผู้เขียน

หรือกรณีทั่วไป:

ความเข้าใจโดยการดำเนินการ: ต้นไม้การตัดสินใจ
ภาพโดยผู้เขียน

มันทำงานได้ดีจน scikit-learn นำมาใช้เป็นมาตรการเริ่มต้น สำหรับตน DecisionTreeClassifier ชั้นเรียน

ความเข้าใจโดยการดำเนินการ: ต้นไม้การตัดสินใจ
ภาพโดยผู้เขียน

หมายเหตุ มาตรการ Gini ความยุ่งเหยิง แทนความสะอาด ตัวอย่าง: ถ้ารายการประกอบด้วยคลาสเดียวเท่านั้น (=ข้อมูลที่สะอาดมาก!) ดังนั้นคำศัพท์ทั้งหมดในผลรวมจะเป็นศูนย์ ดังนั้นผลรวมจึงเป็นศูนย์ กรณีที่แย่ที่สุดคือถ้าทุกคลาสแสดงจำนวนครั้งที่แน่นอน ซึ่งในกรณีนี้ Gini คือ 1–1/C ที่ไหน C คือจำนวนชั้นเรียน

ตอนนี้เรามีมาตรการสำหรับความสะอาด/ความยุ่งเหยิงแล้ว เรามาดูกันว่าจะใช้เพื่อหารอยแยกที่ดีได้อย่างไร

การหาสปลิต

มีหลายแยกให้เราเลือก แต่แบบไหนดี? ให้เราใช้ชุดข้อมูลเริ่มต้นอีกครั้ง ร่วมกับการวัดสิ่งเจือปน Gini

ความเข้าใจโดยการดำเนินการ: ต้นไม้การตัดสินใจ
ภาพโดยผู้เขียน

เราจะไม่นับคะแนนในตอนนี้ แต่สมมติว่า 75% เป็นสีม่วงและ 25% เป็นสีเหลือง การใช้คำจำกัดความของ Gini ความไม่บริสุทธิ์ของชุดข้อมูลทั้งหมดคือ

ความเข้าใจโดยการดำเนินการ: ต้นไม้การตัดสินใจ
ภาพโดยผู้เขียน

หากเราแยกชุดข้อมูลตาม x-axis อย่างที่เคยทำมาก่อน:

ความเข้าใจโดยการดำเนินการ: ต้นไม้การตัดสินใจ
ภาพโดยผู้เขียน

พื้นที่ ส่วนบนมีสิ่งเจือปน Gini 0.0 และส่วนล่าง

ความเข้าใจโดยการดำเนินการ: ต้นไม้การตัดสินใจ
ภาพโดยผู้เขียน

โดยเฉลี่ยแล้ว ทั้งสองส่วนมีค่าความไม่บริสุทธิ์ของ Gini (0.0 + 0.5) / 2 = 0.25 ซึ่งดีกว่า 0.375 ของชุดข้อมูลทั้งหมดก่อนหน้านี้ เรายังสามารถแสดงออกในแง่ของสิ่งที่เรียกว่า ข้อมูลที่ได้รับ:

การรับข้อมูลของการแยกนี้คือ 0.375 – 0.25 = 0.125

ง่ายอย่างนั้น ยิ่งได้รับข้อมูลสูง (เช่น สิ่งเจือปน Gini ยิ่งต่ำ) ก็ยิ่งดี

หมายเหตุ การแบ่งเริ่มต้นที่ดีพอๆ กันอีกอันหนึ่งจะอยู่ในแนวแกน y

สิ่งสำคัญที่ต้องจำไว้คือมันมีประโยชน์ ชั่งน้ำหนักสิ่งเจือปน Gini ของชิ้นส่วนตามขนาดของชิ้นส่วน. ตัวอย่างเช่น สมมุติว่า

ส่วนที่ 1 ประกอบด้วย 50 datapoints และมีค่า Gini impurity เท่ากับ 0.0 และ
ส่วนที่ 2 ประกอบด้วย 450 datapoints และมีค่า Gini impurity เท่ากับ 0.5

ดังนั้นสิ่งเจือปน Gini โดยเฉลี่ยไม่ควรเป็น (0.0 + 0.5) / 2 = 0.25 แต่ควรเป็น 50 / (50 + 450) * 0.0 + 450 / (50 + 450) * 0.5 = 0.45.

โอเค แล้วเราจะหารอยแยกที่ดีที่สุดได้อย่างไร คำตอบง่ายๆ แต่ได้ใจความคือ

เพียงลองใช้การแยกทั้งหมดแล้วเลือกตัวแยกที่ได้รับข้อมูลสูงสุด มันเป็นวิธีการเดรัจฉานบังคับ

เพื่อให้แม่นยำยิ่งขึ้น ต้นไม้การตัดสินใจมาตรฐานจึงใช้ แยกตามแกนพิกัดเช่น xᵢ = ค สำหรับคุณสมบัติบางอย่าง i และเกณฑ์ c. ซึ่งหมายความว่า

ส่วนหนึ่งของข้อมูลแยกประกอบด้วยจุดข้อมูลทั้งหมด x กับ xᵢ คและ
ส่วนอื่นของคะแนนทั้งหมด x กับ xᵢ ≥ ค.

กฎการแยกอย่างง่ายเหล่านี้ได้รับการพิสูจน์แล้วว่าดีพอในทางปฏิบัติ แต่แน่นอนว่าคุณสามารถขยายตรรกะนี้เพื่อสร้างการแยกอื่นๆ ได้ (เช่น เส้นทแยงมุม เช่น xᵢ + 2xⱼ = 3, ตัวอย่างเช่น).

เยี่ยมมาก นี่คือส่วนผสมทั้งหมดที่เราต้องทำตอนนี้!

เราจะใช้แผนผังการตัดสินใจตอนนี้ เนื่องจากมันประกอบด้วยโหนด ให้เรานิยาม a Node ชั้นแรก

from dataclasses import dataclass @dataclass
class Node: feature: int = None # feature for the split value: float = None # split threshold OR final prediction left: np.array = None # store one part of the data right: np.array = None # store the other part of the data

โหนดรู้คุณสมบัติที่ใช้สำหรับการแยก (feature) เช่นเดียวกับค่าการแยก (value). value ยังใช้เป็นที่เก็บข้อมูลสำหรับการทำนายขั้นสุดท้ายของแผนผังการตัดสินใจ เนื่องจากเราจะสร้างไบนารีทรี แต่ละโหนดจำเป็นต้องทราบลูกซ้ายและขวาตามที่จัดเก็บไว้ใน left และ right .

ทีนี้มาดำเนินการใช้แผนผังการตัดสินใจจริงกัน ฉันทำให้มันเข้ากันได้กับ scikit-learn ดังนั้นฉันจึงใช้บางคลาสจาก sklearn.base . หากคุณไม่คุ้นเคย ลองอ่านบทความของฉันเกี่ยวกับ วิธีสร้างโมเดลที่เข้ากันได้กับ scikit-learn.

มาปฏิบัติกันเถอะ!

import numpy as np
from sklearn.base import BaseEstimator, ClassifierMixin class DecisionTreeClassifier(BaseEstimator, ClassifierMixin): def __init__(self): self.root = Node() @staticmethod def _gini(y): """Gini impurity.""" counts = np.bincount(y) p = counts / counts.sum() return (p * (1 - p)).sum() def _split(self, X, y): """Bruteforce search over all features and splitting points.""" best_information_gain = float("-inf") best_feature = None best_split = None for feature in range(X.shape[1]): split_candidates = np.unique(X[:, feature]) for split in split_candidates: left_mask = X[:, feature] split X_left, y_left = X[left_mask], y[left_mask] X_right, y_right = X[~left_mask], y[~left_mask] information_gain = self._gini(y) - ( len(X_left) / len(X) * self._gini(y_left) + len(X_right) / len(X) * self._gini(y_right) ) if information_gain > best_information_gain: best_information_gain = information_gain best_feature = feature best_split = split return best_feature, best_split def _build_tree(self, X, y): """The heavy lifting.""" feature, split = self._split(X, y) left_mask = X[:, feature] split X_left, y_left = X[left_mask], y[left_mask] X_right, y_right = X[~left_mask], y[~left_mask] if len(X_left) == 0 or len(X_right) == 0: return Node(value=np.argmax(np.bincount(y))) else: return Node( feature, split, self._build_tree(X_left, y_left), self._build_tree(X_right, y_right), ) def _find_path(self, x, node): """Given a data point x, walk from the root to the corresponding leaf node. Output its value.""" if node.feature == None: return node.value else: if x[node.feature] node.value: return self._find_path(x, node.left) else: return self._find_path(x, node.right) def fit(self, X, y): self.root = self._build_tree(X, y) return self def predict(self, X): return np.array([self._find_path(x, self.root) for x in X])

และนั่นแหล่ะ! คุณสามารถทำทุกสิ่งที่คุณรักเกี่ยวกับ scikit-learn ได้เลย:

dt = DecisionTreeClassifier().fit(X, y)
print(dt.score(X, y)) # accuracy # Output
# 1.0

เนื่องจากต้นไม้ไม่เป็นระเบียบ มันจึงมากเกินไป ดังนั้นคะแนนรถไฟที่สมบูรณ์แบบ ความแม่นยำจะแย่ลงหากไม่ได้ดูข้อมูล เรายังสามารถตรวจสอบลักษณะของต้นไม้ได้ผ่านทาง

print(dt.root) # Output (prettified manually):
# Node(
# feature=1,
# value=-0.14963454032767076,
# left=Node(
# feature=0,
# value=0.04575851730144607,
# left=Node(
# feature=None,
# value=0,
# left=None,
# right=None
# ),
# right=Node(
# feature=None,
# value=1,
# left=None,
# right=None
# )
# ),
# right=Node(
# feature=None,
# value=0,
# left=None,
# right=None
# )
# )

ตามภาพจะเป็นดังนี้

ความเข้าใจโดยการดำเนินการ: ต้นไม้การตัดสินใจ
ภาพโดยผู้เขียน

ในบทความนี้ เราได้ดูรายละเอียดว่าแผนผังการตัดสินใจทำงานอย่างไร เราเริ่มต้นด้วยแนวคิดที่คลุมเครือแต่เข้าใจได้ง่าย และเปลี่ยนให้เป็นสูตรและอัลกอริทึม ในท้ายที่สุด เราสามารถใช้แผนผังการตัดสินใจตั้งแต่เริ่มต้น

คำเตือน: ต้นไม้การตัดสินใจของเรายังไม่สามารถทำให้เป็นมาตรฐานได้ โดยปกติเราจะกำหนดพารามิเตอร์เช่น

ความลึกสูงสุด
ขนาดใบ
และได้รับข้อมูลน้อยที่สุด

และอื่น ๆ อีกมากมาย โชคดีที่สิ่งเหล่านี้ไม่ยากที่จะนำไปใช้ ซึ่งทำให้เป็นการบ้านที่สมบูรณ์แบบสำหรับคุณ ตัวอย่างเช่น หากคุณระบุ leaf_size=10 เป็นพารามิเตอร์ ดังนั้นโหนดที่มีตัวอย่างมากกว่า 10 ตัวอย่างไม่ควรแยกอีกต่อไป นอกจากนี้การใช้งานนี้คือ ไม่มีประสิทธิภาพ. โดยปกติแล้ว คุณไม่ต้องการจัดเก็บบางส่วนของชุดข้อมูลในโหนด แต่เก็บเฉพาะดัชนีแทน ดังนั้นชุดข้อมูล (อาจมีขนาดใหญ่) ของคุณจึงอยู่ในหน่วยความจำเพียงครั้งเดียว

สิ่งที่ดีคือคุณสามารถคลั่งไคล้ได้ทันทีด้วยเทมเพลตแผนผังการตัดสินใจนี้ คุณสามารถ:

ใช้การแยกแนวทแยงเช่น xᵢ + 2xⱼ = 3 แทนที่จะเป็นเพียงแค่ xᵢ = 3,
เปลี่ยนตรรกะที่เกิดขึ้นภายใน leaf นั่นคือคุณสามารถเรียกใช้การถดถอยโลจิสติกภายในแต่ละ leaf แทนการลงคะแนนเสียงข้างมาก ซึ่งช่วยให้คุณ ต้นไม้เชิงเส้น
เปลี่ยนขั้นตอนการแยก เช่น แทนที่จะใช้กำลังดุร้าย ให้ลองใช้ชุดค่าผสมแบบสุ่มและเลือกชุดที่ดีที่สุด ซึ่งจะช่วยให้คุณ ลักษณนามต้นไม้พิเศษ
และอื่น ๆ.

ดร.โรเบิร์ต คูเบลอร์ เป็นนักวิทยาศาสตร์ข้อมูลที่ Publicis Media และผู้แต่งที่ Towards Data Science

Original. โพสต์ใหม่โดยได้รับอนุญาต