Drzewa decyzyjne to jedna z najbardziej intuicyjnych i wszechstronnych technik analizy danych, stosowanych zarówno w statystyce, jak i uczeniu maszynowym. Niezwykła w swojej prostocie metoda potrafi dostarczyć potężnych wyników. W tym wpisie zajmiemy się metrykami, dzięki którym możemy dokonać najlepszego podziału. Najpierw trochę teorii…
Teoria
Współczynnik Giniego
Stosowana w statystyce miara koncentracji (nierównomierności) rozkładu zmiennej losowej. Wzór na współczynnik Giniego jest następujący:
G = 1 – \sum_{i=1}^{n} p_i^2
Gdzie:
* G: współczynnik Giniego,
* p_{i}: Prawdopodobieństwo wystąpienia i-tej klasy.
* n_{n}: Liczba klas.
Jeśli współczynnik Giniego wynosi „0”, oznacza to idealną równość (każda klasa jest równo reprezentowana). Wartość „1” oznacza całkowitą nierówność (tylko jedna klasa jest reprezentowana).
Entropia
Jest miarą stopnia nieuporządkowania układu.
H = -\sum_{i=1}^{n} p_i \log_2(p_i)
Gdzie:
* H: entropia,
* p_{i}: Prawdopodobieństwo wystąpienia i-tej klasy.
* n_{n}: Liczba klas.
Entropia jest najwyższa, gdy wszystkie klasy są równo reprezentowane (50:50), i najniższa, gdy tylko jedna klasa jest reprezentowana.
Zysk informacyjny
Zysk informacyjny to miara, która określa, jak dobrze dana cecha dzieli zbiór uczący na klasy. Jest to różnica między entropią przed podziałem a entropią po podziale, ważoną według liczby instancji w każdym podzbiorze. Zysk informacyjny można wyrazić wzorem:
IG(T, a) = H(T) – \sum_{v \in a} \frac{|T_v|}{|T|} H(T_v)
Gdzie:
* IG(T,a): Zysk informacyjny dla atrybutu a w zbiorze T.
* H(T): Entropia zbioru T przed podziałem.
* \sum_{v \in a}: Suma po wszystkich wartościach atrybutu a.
* |T_v|: Liczba elementów w podzbiorze T z wartością atrybutu v.
* |T|: Łączna liczba elementów w zbiorze T.
* H(T_v): Entropia podzbioru T z wartością atrybutu v po podziale.
Zysk informacyjny mierzy spadek entropii po podziale zbioru T według atrybutu a. Jeżeli zysk informacyjny jest wysoki, oznacza to, że atrybut aa dobrze rozdziela zbiór TT na klasy.
Przykład
Weźmy zbiór, składający się z 10 kulek. Na podstawie ich wielkości (predyktor – wpisany w kulkę), chcielibyśmy dokonać podziału, tak, żeby w zbiorze znalazły się kulki tego samego koloru (zmienna modelowana):
W którym miejscu najlepiej dokonać podziału? Policzymy to, najpierw pythonem, a później sprawdźmy jeszcze “ręcznie” dla najlepszego podziału.
Współczynnik Giniego
def gini_index(data, target_name='Color'):
elements, counts = np.unique(data[target_name], return_counts=True)
gini = 1 - np.sum((counts / np.sum(counts)) ** 2)
return gini
def gini_gain(data, split_attribute_name, target_name='Color'):
total_gini = gini_index(data)
unique_values = sorted(np.unique(data[split_attribute_name]))
gini_gains = {}
for i in range(len(unique_values) - 1):
val = (unique_values[i] + unique_values[i + 1]) / 2
left_split = data[data[split_attribute_name] <= val]
right_split = data[data[split_attribute_name] > val]
left_gini = gini_index(left_split)
right_gini = gini_index(right_split)
left_weight = len(left_split) / len(data)
right_weight = len(right_split) / len(data)
split_gini = left_weight * left_gini + right_weight * right_gini
gain = total_gini - split_gini
gini_gains[val] = gain
return gini_gains
gini_gains = gini_gain(data, 'Size')
print('Gini Gains for each split:\n')
for split_val, gain in gini_gains.items():
print(f'Split at > {int(split_val)}: {gain:.4f}')
Gini Gains for each split: Split at > 2: 0.0356 Split at > 3: 0.0050 Split at > 4: 0.0300 Split at > 5: 0.1633 Split at > 6: 0.0610 Split at > 7: 0.0050 Split at > 8: 0.0800
Przed podziałem:
G =1−(0.6)^2−(0.4)^2 = 1−0.36−0.16 = 0.48
Po podziale (pierwszy zbiór):
G_1 =1−(0.25)^2−(0.75)^2 = 1−0.0625−0.5625 = 0.375
Po podziale (drugi zbiór):
G_2 = 1−(0.83)^2−(0.17)2 = 1−0.6889−0.0289 = 0.2822
Zysk informacyjny:
IG(D, a) = Gini(D) – \sum_{v \in a} \frac{|D_v|}{|D|} Gini(D_v)
IG(D, a) = 0.48 – \left( \frac{4}{10} \cdot 0.375 + \frac{6}{10} \cdot 0.2778 \right) = 0.48 – (0.15 + 0.1667) = 0.1633
Entropia
def entropy(target_col):
elements, counts = np.unique(target_col, return_counts=True)
entropy = -np.sum([(counts[i] / np.sum(counts)) * np.log2(counts[i] / np.sum(counts)) for i in range(len(elements))])
return entropy
def information_gain(data, split_attribute_name, target_name='Color'):
total_entropy = entropy(data[target_name])
unique_values = sorted(np.unique(data[split_attribute_name]))
info_gains = {}
for i in range(len(unique_values) - 1):
val = (unique_values[i] + unique_values[i + 1]) / 2
left_split = data[data[split_attribute_name] <= val]
right_split = data[data[split_attribute_name] > val]
left_entropy = entropy(left_split[target_name])
right_entropy = entropy(right_split[target_name])
left_weight = len(left_split) / len(data)
right_weight = len(right_split) / len(data)
split_entropy = left_weight * left_entropy + right_weight * right_entropy
info_gain = total_entropy - split_entropy
info_gains[val] = info_gain
return info_gains
info_gains = information_gain(data, 'Size')
print('Information Gains for each split:\n')
for split_val, gain in info_gains.items():
print(f'Split at > {int(split_val)}: {gain:.4f}')
Information Gains for each split: Split at > 2: 0.0790 Split at > 3: 0.0074 Split at > 4: 0.0464 Split at > 5: 0.2564 Split at > 6: 0.0913 Split at > 7: 0.0074 Split at > 8: 0.1445
Przed podziałem:
p_{red} = 6/10
p_{blue} = 4/10
H = – 0.6 \log_2(0.6) – 0.4 \log_2(0.4) = 0.442 + 0.529 = 0.97
Po podziale (pierwszy zbiór):
p_{red} = 1/4
p_{blue} = 3/4
H = – 0.25 \log_2(0.25) – 0.75 \log_2(0.75) = 0.5 + 0.31 = 0.81
Po podziale (drugi zbiór):
p_{red} = 5/6
p_{blue} = 1/6
H = – 0.83 \log_2(0.83) – 0.17 \log_2(0.17) = 0.22 + 0.43 = 0.65
Zysk informacyjny:
IG(T, a) = H(T) – \sum_{v \in a} \frac{|T_v|}{|T|} H(T_v) IG(T, a) = 0.97 – [(4/10 * 0.81) + (6/10 * 0.65)] = 0.256