Algorithmen für maschinelles Lernen können kategoriale Variablen nicht verarbeiten. Aber Entscheidungsbäume (DTs) können. Klassifizierungsbäume erfordern auch kein numerisches Ziel. Unten ist eine Darstellung eines Baumes, der eine Untergruppe von kyrillischen Buchstaben in Vokale und Konsonanten einteiliert. Es verwendet keine numerischen Merkmale – es existiert jedoch.
Viele fördern auch die mittlere Zielcodierung (MTE) als clevere Methode, um kategoriale Daten in numerische Kind umzuwandeln-ohne den Merkmalsraum als One-Scorching-Codierung aufzublasen. Ich habe jedoch keine Erwähnung dieser inhärenten Verbindung zwischen MTE und Resolution Tree Logic zu TDs gesehen. Dieser Artikel befasst sich genau mit dieser Lücke durch ein veranschaulichendes Experiment. Insbesondere:
- Ich werde mit einer kurzen Zusammenfassung der Artwork und Weise beginnen, wie Entscheidungsbäume Behandeln Sie kategoriale Merkmale.
- Wir werden sehen, dass dies zu einer rechnerischen Herausforderung für Funktionen mit hoher Kardinalität wird.
- Ich werde demonstrieren, wie die mittlere Zielcodierung auf natürliche Weise als Lösung für dieses Downside auftritt – im Gegensatz zu Beschriftungscodierung.
- Sie können mein Experiment mit dem Code aus reproduzieren Github.
Ein kurzer Hinweis: One-Scorching-Codierung wird oft von Followers der mittleren Zielcodierung ungünstig dargestellt-aber es ist nicht so schlimm, wie sie vermuten lassen. Tatsächlich belegte es in unseren Benchmark -Experimenten häufig den ersten Platz unter den 32 kategorialen Codierungsmethoden, die wir bewertet haben. (1)
Entscheidungsbäume und der Fluch der kategorialen Merkmale
Entscheidungsbaumlernen ist ein rekursiver Algorithmus. Bei jedem rekursiven Schritt iteriert es alle Funktionen und sucht nach dem besten Cut up. Es reicht additionally aus, zu untersuchen, wie eine einzige rekursive Iteration mit einem kategorialen Merkmal umgeht. Wenn Sie sich nicht sicher sind, wie sich diese Operation auf die Konstruktion des vollen Baumes verallgemeinert, schauen Sie sich hier an (2).
Für eine kategoriale Funktion bewertet der Algorithmus alle möglichen Möglichkeiten, die Kategorien in zwei nicht leere Sätze zu unterteilen, und wählt die aus, die die höchste Cut up -Qualität ergibt. Die Qualität wird typischerweise unter Verwendung von Gini -Verunreinigungen für binäre Klassifizierung oder mittlerer quadratischer Fehler für die Regression gemessen – beide sind besser, wenn sie niedriger sind. Siehe ihren Pseudocode unten.
# ---------- Gini impurity criterion ----------
FUNCTION GiniImpurityForSplit(cut up):
left, proper = cut up
complete = dimension(left) + dimension(proper)
RETURN (dimension(left)/complete) * GiniOfGroup(left) +
(dimension(proper)/complete) * GiniOfGroup(proper)
FUNCTION GiniOfGroup(group):
n = dimension(group)
IF n == 0: RETURN 0
ones = rely(values equal 1 in group)
zeros = n - ones
p1 = ones / n
p0 = zeros / n
RETURN 1 - (p0² + p1²)# ---------- Imply-squared-error criterion ----------
FUNCTION MSECriterionForSplit(cut up):
left, proper = cut up
complete = dimension(left) + dimension(proper)
IF complete == 0: RETURN 0
RETURN (dimension(left)/complete) * MSEOfGroup(left) +
(dimension(proper)/complete) * MSEOfGroup(proper)
FUNCTION MSEOfGroup(group):
n = dimension(group)
IF n == 0: RETURN 0
μ = imply(Worth column of group)
RETURN sum( (v − μ)² for every v in group ) / nNehmen wir an, die Funktion hat eine Kardinalität okay. Jede Kategorie kann zu einer der beiden Sätze gehören, die 2 gebenᵏ Gesamtkombinationen. Ohne die beiden trivialen Fälle, in denen einer der Units leer ist, werden wir 2 übrig bleibenᵏ–2 Machbare Spaltungen. Beachten Sie als nächstes, dass wir uns nicht um die Reihenfolge der Units kümmern – Spaltungen wie {{A, B}, {C}} und {{C}, {a, b}} sind äquivalent. Dies senkt die Anzahl der eindeutigen Kombinationen in zwei Hälften, was zu einer endgültigen Anzahl von (2) führtᵏ–2)/2 Iterationen. Für unser oben genannter Spielzeugbeispiel mit Ok = 5 Kyrillische Buchstaben, diese Zahl ist 15. Aber wann Ok = 20Es Luftballons auf 524.287 Kombinationen – genug, um das DT -Coaching erheblich zu verlangsamen.
Die mittlere Zielcodierung löst das Effizienzproblem
Was wäre, wenn man den Suchraum von (2) reduzieren könnteᵏ–2)/2 zu etwas überschaubarer – ohne die optimale Spaltung zu verlieren? Es stellt sich heraus, dass dies in der Tat möglich ist. Man kann theoretisch zeigen, dass die mittlere Zielcodierung diese Reduzierung ermöglicht (3). Wenn die Kategorien in der Reihenfolge ihrer MTE -Werte angeordnet sind und nur aufteilt, die diese Reihenfolge respektieren, werden die optimalen Cut up – gemäß Gini -Verunreinigung für die Klassifizierung oder mittlerer quadratischer Fehler für die Regression – unter ihnen sein. Es gibt genau Ok-1 Solche Spaltungen, eine dramatische Reduktion im Vergleich zu (2ᵏ–2)/2. Der Pseudocode für MTE ist unten.
# ---------- Imply-target encoding ----------
FUNCTION MeanTargetEncode(desk):
category_means = common(Worth) for every Class in desk # Class → imply(Worth)
encoded_column = lookup(desk.Class, category_means) # exchange label with imply
RETURN encoded_columnExperiment
Ich werde die theoretischen Ableitungen, die die oben genannten Ansprüche stützen, nicht wiederholen. Stattdessen habe ich ein Experiment entworfen, um sie empirisch zu validieren und ein Gefühl für die Effizienzgewinne zu erhalten, die von MTE gegenüber der nativen Partitionierung erzielt wurden, die alle möglichen Spaltungen umfassend iteriert. Im Folgenden erkläre ich den Datengenerierungsprozess und den Experiment -Setup.
Daten
Um synthetische Daten für das Experiment zu generieren, habe ich eine einfache Funktion verwendet, die einen Zwei-Spalt-Datensatz erstellt. Die erste Spalte enthält N unterschiedliche kategoriale Ebenen, jeweils wiederholt M mal, was zu insgesamt führt N × m Reihen. Die zweite Spalte repräsentiert die Zielvariable und kann je nach Eingabeparameter entweder binär oder kontinuierlich sein. Unten finden Sie den Pseudocode für diese Funktion.
# ---------- Artificial-dataset generator ----------
FUNCTION GenerateData(num_categories, rows_per_cat, target_type='binary'):
total_rows = num_categories * rows_per_cat
classes = ('Category_' + i for i in 1..num_categories)
category_col = repeat_each(classes, rows_per_cat)
IF target_type == 'steady':
target_col = random_floats(0, 1, total_rows)
ELSE:
target_col = random_ints(0, 1, total_rows)
RETURN DataFrame{ 'Class': category_col,
'Worth' : target_col }Experiment -Setup
Der experiment Die Funktion übernimmt eine Liste von Kardinalitäten und ein Spaltkriterium – entweder Gini -Verunreinigungen oder mittlerer quadratischer Fehler, abhängig vom Zieltyp. Für jede kategoriale Function-Kardinalität in der Liste generiert es 100 Datensätze und vergleicht zwei Strategien: eine erschöpfende Bewertung aller möglichen Kategorienaufteilungen und der eingeschränkten, mTE-informierten Bestellung. Es misst die Laufzeit jeder Methode und prüft, ob beide Ansätze den gleichen optimalen Cut up -Rating erzeugen. Die Funktion gibt die Anzahl der Übereinstimmungsfälle zusammen mit durchschnittlichen Laufzeiten zurück. Der Pseudocode ist unten angegeben.
# ---------- Cut up comparability experiment ----------
FUNCTION RunExperiment(list_num_categories, splitting_criterion):
outcomes = ()
FOR okay IN list_num_categories:
times_all = ()
times_ord = ()
REPEAT 100 instances:
df = GenerateDataset(okay, 100)
t0 = now()
s_all = MinScore(df, AllSplits, splitting_criterion)
t1 = now()
t2 = now()
s_ord = MinScore(df, MTEOrderedSplits, splitting_criterion)
t3 = now()
times_all.append(t1 - t0)
times_ord.append(t3 - t2)
IF spherical(s_all,10) != spherical(s_ord,10):
PRINT "Discrepancy at okay=", okay
outcomes.append({
'okay': okay,
'avg_time_all': imply(times_all),
'avg_time_ord': imply(times_ord)
})
RETURN DataFrame(outcomes)Ergebnisse
Sie können mein Wort dafür nehmen oder das Experiment wiederholen (Github) – aber die optimalen Cut up -Scores beider Ansätze stimmten immer überein, genau wie die Theorie vorhersagt. Die folgende Abbildung zeigt die Zeit, die für die Bewertung von Splits als Funktion der Anzahl der Kategorien erforderlich ist. Die vertikale Achse befindet sich auf einer logarithmischen Skala. Die Linie, die eine ausführliche Bewertung darstellt, erscheint in diesen Koordinaten linear, was bedeutet, dass die Laufzeit exponentiell mit der Anzahl der Kategorien wächst – was die zuvor diskutierte theoretische Komplexität bestätigt. Bereits in 12 Kategorien (in einem Datensatz mit 1.200 Zeilen) dauert die Überprüfung aller möglichen Spaltungen etwa eine Sekunde-drei Größenordnungen langsamer als der MTE-basierte Ansatz, der den gleichen optimalen Cut up ergibt.
Abschluss
Entscheidungsbäume können kategoriale Daten nativ verarbeiten, aber diese Fähigkeit erfolgt zu einer Rechenkosten, wenn die Kategorie zählt. Die mittlere Zielcodierung bietet eine prinzipielle Abkürzung, wodurch die Anzahl der Kandidatenaufteilungen drastisch verringert wird, ohne das Ergebnis zu beeinträchtigen. Unser Experiment bestätigt die Theorie: MTE-basierte Order findet den gleichen optimalen Cut up, aber exponentiell schneller.
Zum Zeitpunkt des Schreibens, scikit-learn unterstützt kategoriale Merkmale nicht direkt. Was denkst du additionally – wenn Sie die Daten mit MTE vorab zusammenarbeiten, entspricht der resultierende Entscheidungsbaum einem, das von einem Lernenden erstellt wurde, der kategoriale Merkmale nativ übernimmt?
Referenzen
(1) Ein Benchmark und eine Taxonomie kategorischer Encoder. Auf Knowledge Science. https://towardsdatascience.com/a-benchmark-and-taxonomy-of-categorical-coder-9b7a0dc47a8c/
(2) Bergbauregeln aus Daten. Auf Knowledge Science. https://towardsdatascience.com/mining-rules-from-data
(3) Hastie, Trevor, Tibshirani, Robert und Friedman, Jerome. Die Elemente des statistischen Lernens: Knowledge Mining, Inferenz und Vorhersage. Vol. 2. New York: Springer, 2009.