Drzewa: podział na argumentach
Dzisiejsze zajęcia dotyczą drzew klasyfikujących, omówionych podczas wykładu 5 Najistotniejszym elemntem konstrukcji drzew jest reguła podziału, która decyduje o tym, w jaki sposób poszczególne elementy skupione w danym węźle zostaną przesunięte do swoich węzłów-dzieci. Ze względu na swoja prostotę obliczeniową będziemy korzystać z miary różnorodności danej wskaźnikiem Gini’ego. Przedstawia się ona w następujący sposób, przy czym p ułamkiem obserwacji należących do klasy 1:
\(Q_{G} = 2 p (1 - p)\)
import numpy as np
import pandas as pd
def draw_data(n1, n2, m1, m2, S1, S2):
data1 = np.random.multivariate_normal(m1, S1, n1)
data2 = np.random.multivariate_normal(m2, S2, n2)
data = np.concatenate((data1, data2), axis = 0)
data = pd.DataFrame(data, columns=["x", "y"])
data["klasa"] = np.repeat([0, 1], [n1, n2])
return data
m1, m2 = [-1, -1], [2, 2]
S1 = [[4, 2], [2, 4]]
S2 = [[4, 2], [2, 4]]
n1, n2 = 30, 20
np.random.seed(129)
data = draw_data(n1, n2, m1, m2, S1, S2)przedstawiających się w następujący sposób
import seaborn as sns
import matplotlib.pyplot as plt
def plot_data(data):
g = sns.relplot(data = data, x="x", y="y", hue="klasa", s = 150)
g.ax.spines['top'].set_visible(True)
g.ax.spines['right'].set_visible(True)
g.ax.set_aspect('equal')
plt.axhline(0, color="black", linestyle=":")
plt.axvline(0, color="black", linestyle=":")
for i in range(len(data.index)):
plt.text(data.x[i], data.y[i], i, fontsize=8, fontweight="bold", color = "white", horizontalalignment='center', verticalalignment='center')
return g
g = plot_data(data)
plt.show()
Teraz należy stworzyć cały “silnik” drzewa, czyli zdefiniowac współczynnik Gini’ego oraz funkcję do wyznaczania różnorodności, a dokładniej różnicy różnorodności pomiędzy rodzicem a dziećmi.
gini = lambda tab: 2*tab[0]*tab[1]
def get_Q(data, threshold, name):
tab_parent = data.klasa.value_counts(bins = range(-1, 2)).reindex([0, 1])
tab_left = data.klasa[data[name] <= threshold].value_counts(bins = range(-1, 2)).reindex([0, 1])
tab_right = tab_parent - tab_left
tab_parent_s = tab_parent.sum()
tab_left_s = tab_left.sum()
tab_right_s = tab_right.sum()
tab_parent /= tab_parent_s
tab_left /= tab_left_s
tab_right /= tab_right_s
Q_parent = gini(tab_parent)
Q_left = gini(tab_left)
Q_right = gini(tab_right)
p_left = tab_left_s / tab_parent_s
p_right = 1 - p_left
Q_children = p_left * Q_left + p_right * Q_right
#return Q_children
return Q_parent - Q_childrenW tym momencie nie przedstawia już trudności wyznaczenie różnicy różnorodności dla każdej wartości podziału zarówno argumentu \(x\) jak i \(y\) danych.
thrs_x = np.unique(np.sort(data.x))
thrs_y = np.unique(np.sort(data.y))
Q_x = np.array([get_Q(data, th, "x") for th in thrs_x])
Q_y = np.array([get_Q(data, th, "y") for th in thrs_y])Wartości te można wykreślić i porównać ze sobą.
plt.plot(thrs_x, Q_x, "-bo", label = "składowa x")
plt.plot(thrs_y, Q_y, ls = "-", color = "orange", marker="o", label = "składowa y")
plt.legend()
plt.xlabel("x, y")
plt.ylabel(r"$Q_x$, $Q_y$");
plt.show()
Jak widać z wykresu, maksymalna wartość dla argumentu \(x\) jest większa niż dla \(y\), tak więc ona zostanie wybrana jako dzieląca zbiór danych, przy czym biorąc pod uwagę iż de facto mówimy o całym przedziale, wygodnie jest przyjąć wartość średnią z dwóch sąsiednich punktów
plt.plot(thrs_x, Q_x, "-bo", label = "składowa x")
plt.plot(thrs_y, Q_y, ls = "-", color = "orange", marker="o", label = "składowa y")
plt.legend()
plt.xlabel("x, y")
plt.ylabel(r"$Q_x$, $Q_y$");
id_max = np.nanargmax(Q_x)
xc = (thrs_x[id_max] + thrs_x[id_max + 1])/2
print(xc)## 1.7279067988139545plt.axvline(xc, color = "red", ls = "--")
plt.show()
Można wreszcie zaznaczyć ostateczny podział na oryginalnym wykresie
danych (korzystamy z funckji Rectangle() z modułu
patches).
from matplotlib.patches import Rectangle
g = plot_data(data)
xmin, xmax = g.ax.get_xlim()
ymin, ymax = g.ax.get_ylim()
print(xmin, ymin)## -4.012043198688766 -5.459182373692898g.ax.add_patch(Rectangle((xmin, ymin), xc - xmin, ymax-ymin, color="blue", alpha = 0.2))
plt.show()
Drzewa: poidział danych
Korzystając z powyższych funkcji gini(), norm.tab() oraz get.Q(), możemy teraz zaproponować bardzo prostą funkcję dostosowaną do przypadku dwóch argumentów, która wyszuka najlepszy podział na argumentach oraz korzystając z tego rozdzieli dane.
def split_data(data):
thrs_x = np.unique(np.sort(data.x))
thrs_y = np.unique(np.sort(data.y))
Q_x = np.array([get_Q(data, th, "x") for th in thrs_x])
Q_y = np.array([get_Q(data, th, "y") for th in thrs_y])
if max(Q_x) >= max(Q_y):
Q = Q_x
var = "x"
thrs = thrs_x
else:
Q = Q_y
var = "y"
thrs = thrs_y
id_max = np.nanargmax(Q)
th = (thrs[id_max] + thrs[id_max + 1]) / 2
data_left = data[data[var] <= th]
data_right = data[data[var] > th]
return {"var": var, "var_val": th, "data_left": data_left, "data_right": data_right}Daje to np. możliwość wizualizacji następnego podziału
s0 = split_data(data)
s1 = split_data(s0["data_right"])
g = plot_data(data)
xmin, xmax = g.ax.get_xlim()
ymin, ymax = g.ax.get_ylim()
print(xmin, ymin)## -4.012043198688766 -5.459182373692898g.ax.add_patch(Rectangle((xmin, ymin), s0["var_val"] - xmin, ymax-ymin, color="blue", alpha = 0.2))
g.ax.add_patch(Rectangle((s0["var_val"], s1["var_val"]), xmax - s0["var_val"], ymax - s1["var_val"], color="orange", alpha = 0.2))
g.ax.add_patch(Rectangle((s0["var_val"], ymin), xmax - s0["var_val"], s1["var_val"] - ymin, color="blue", alpha = 0.2))
plt.show()
Warto przy tym zauważyć, że podział “po prawej stronie” jest ostateczny: w prostokątach pozostały jedynie elementy jednej klasy - czyli są to liście.
Drzewa: pełna funkcja
Powyższe rozważania dają nam możliwość wykonania prymitywnej funkcji do implementacji drzewa klasyfikującego w przypadku dwóch argumentów. Funkcja działa rekurencyjnie i ma na celu dopowoadzenie do takiej sytuacji, aby w liściach znajdowały się jedynie elementy jednej klasy
def simple_tree(data, sp):
tab_parent = data.klasa.value_counts(bins = range(-1, 2)).reindex([0, 1])
if gini(tab_parent / tab_parent.sum()) < 1e-6:
print(sp, "lisc klasa 0:", tab_parent[0], "klasa 1:", tab_parent[1])
else:
thrs_x = np.unique(np.sort(data.x))
thrs_y = np.unique(np.sort(data.y))
Q_x = np.array([get_Q(data, th, "x") for th in thrs_x])
Q_y = np.array([get_Q(data, th, "y") for th in thrs_y])
if max(Q_x) >= max(Q_y):
Q = Q_x
var = "x"
thrs = thrs_x
print(sp, "Podzial na X=", end="")
else:
Q = Q_y
var = "y"
thrs = thrs_y
print(sp, "Podzial na Y=", end="")
id_max = np.nanargmax(Q)
th = (thrs[id_max] + thrs[id_max + 1]) / 2
print(np.round(th, 3))
data_left = data[data[var] <= th]
data_right = data[data[var] > th]
sp = sp + "*"
simple_tree(data_left, sp)
simple_tree(data_right, sp)dającej poniższy efekt
simple_tree(data, "*")## * Podzial na X=1.728
## ** Podzial na Y=1.262
## *** Podzial na X=0.977
## **** lisc klasa 0: 25 klasa 1: 0
## **** Podzial na X=1.28
## ***** lisc klasa 0: 0 klasa 1: 1
## ***** lisc klasa 0: 3 klasa 1: 0
## *** Podzial na X=0.925
## **** lisc klasa 0: 0 klasa 1: 3
## **** lisc klasa 0: 1 klasa 1: 0
## ** Podzial na Y=-0.701
## *** lisc klasa 0: 1 klasa 1: 0
## *** lisc klasa 0: 0 klasa 1: 16Moduł sklearn.tree
Oczywiście, celem powyższych rozważań i bardzo prostych funkcji jest
jedynie ilustracja problemu. Do wykorzystania drzew klasyfikujących
użyjemy modułu sklearn.tree. Konstrukcja wyowałnai jest
standardowa:
from sklearn import tree
clf = tree.DecisionTreeClassifier()
clf = clf.fit(data[["x", "y"]], data.klasa)Dysponując już nauczonym drzewem, możemy porównać wyniki z nasza
zgrubną metodą. Wykorzystamy do tego funkcję
export_text()
print(tree.export_text(clf))## |--- feature_0 <= 1.73
## | |--- feature_1 <= 1.26
## | | |--- feature_0 <= 0.98
## | | | |--- class: 0
## | | |--- feature_0 > 0.98
## | | | |--- feature_0 <= 1.28
## | | | | |--- class: 1
## | | | |--- feature_0 > 1.28
## | | | | |--- class: 0
## | |--- feature_1 > 1.26
## | | |--- feature_0 <= 0.92
## | | | |--- class: 1
## | | |--- feature_0 > 0.92
## | | | |--- class: 0
## |--- feature_0 > 1.73
## | |--- feature_1 <= -0.70
## | | |--- class: 0
## | |--- feature_1 > -0.70
## | | |--- class: 1Odwołując się do wcześniej poznanej funkcji
DecisionBoundaryDisplay możemy szybko wykreślić granice
klas (zamiast poprzedniego, mozolnego podejścia):
from sklearn.inspection import DecisionBoundaryDisplay
DecisionBoundaryDisplay.from_estimator(clf, data[["x", "y"]], cmap=plt.cm.coolwarm, alpha = 0.4)## <sklearn.inspection._plot.decision_boundary.DecisionBoundaryDisplay object at 0x000001C4A08A7620>plt.scatter(data.x, data.y, c=data["klasa"], edgecolor="k", cmap=plt.cm.coolwarm)
plt.show()
Nie zmiania to faktu, że najpopularniejszym przedstawieniem drzewa klasyfikacyjnego jest… cóż, właśnie drzewko, czyli graf, który generalnie w graficzny sposób odzwerciedla wczesniej pokazaną informację w formie tekstowej:
plt.figure(figsize=(8, 8))
tree.plot_tree(clf, feature_names=["x", "y"], class_names = ["0", "1"], filled = True)
plt.show()
Z powyższych przedstawień łatwo się domyslić jaką skuteczność ma pełne drzewo, czyli takie, gdzie proces podziału danych prowadzimy aż do pojawienia się elementów tylko jeden klasy w danym węźle. Faktycznie, powtórne podstawienie potwierdzna nasze obserwacje:
from sklearn import metrics
preds = clf.predict(data[["x", "y"]])
print(metrics.classification_report(data.klasa, preds))## precision recall f1-score support
##
## 0 1.00 1.00 1.00 30
## 1 1.00 1.00 1.00 20
##
## accuracy 1.00 50
## macro avg 1.00 1.00 1.00 50
## weighted avg 1.00 1.00 1.00 50Jeśli jednak wykonamy np. pięciokrotną kroswalidację (z podziałem na 5 próbek), to jasne będzie, że budowa pełnego drzewa nie musi być najlepszym rozwiązaniem (podobnie jak budowa klasyfikatora k-nn z nn=1):
from sklearn.model_selection import cross_val_score
from sklearn.model_selection import RepeatedKFold
kf = RepeatedKFold(n_repeats = 5, n_splits = 5)
cross_val_score(clf, data[["x","y"]], data.klasa, cv = kf).mean()## np.float64(0.8839999999999999)Warto pamiętać, że możemy bez problemu wykorzystać technikę drzew do klasyfikacji zbiorów z liczbą klas \(g > 2\) - poniższy przykład odnosi się do irysów - kolejnego gold standard uczenia masyznowego:
from sklearn import datasets
iris = datasets.load_iris()
clf = tree.DecisionTreeClassifier()
clf = clf.fit(iris.data, iris.target)
plt.figure(figsize=(10,10))
tree.plot_tree(clf, feature_names=iris.feature_names, class_names = iris.target_names, filled = True, rounded=True)
plt.show()