CART 6

System-Voraussetzungen | Weitere Informationen

Was ist CART?

CART ist ein Akronym fuer 'Classification and Regression Trees' (Klassifikations- und Regressionsbäume), eine Prozedur mit Entscheidungsbaeumen, die 1984 von den weltbekannten Statistikern der UC (Universitaet von Kalifornien) in Berkeley und Stanford, Leo Breiman, Jerome Friedman, Richard Olshen, and Charles Stone entwickelt wurde. Ihre bahnbrechende Arbeit schuf das neue Gebiet der hochentwickelten, mathematisch und theoretisch fundierten Entscheidungsbaeume.
Die CART-Methode loest eine Reihe von Problemen hinsichtlich Leistungsfaehigkeit, Exaktheit von Verfahren, mit der viele derzeitige Entscheidungsbaum-Methoden noch immer kaempfen. CART's Neuerungen beinhalten:

• Loesung des Problem von 'wie weit soll der Baum wachsen?'
• ausschliessliche Benutzung von zweifach (binaere) splits
• automatischer Überpruefung und Validierung des Baumes
• voellig neue Methode fuer die Behandlung fehlender Werte.
  

Warum ist Salford Systems' CART das einzig echte CART?

Salford Systems' CART ist das einzige Entscheidungsbaum-Programm, das auf dem Original-Code von Breiman, Friedman, Olshen, and Stone basiert.
Da der Code urheberrechtlich geschuetzt ist, ist CART die einzig wirkliche Umsetzung dieser Klassifikations- und Regressionsbäume-Methode. Zusaetzlich wurde die Prozedur durch neue Merkmale und Fähigkeiten, die in exklusiver Zusammenarbeit mit den Schoepfern entwickelt wurden, wesentlich verbessert. Die Urheber arbeiten auch weiterhin mit Salford Systems zusammen, um CART zu verbessern und die naechste Generation von Data Mining Programmen zu entwickeln.
Waehrend einige andere Produkte zur Erstellung von Entscheidungsbaeumen- fuer sich in Anspruch nehmen, Merkmale dieser Technologie zu beinhalten, sind sie dennoch nicht faehig echte CART-Baeume zu reproduzieren. Ausserdem fehlen diesen meist wichtige grundlegende Komponenten, die die Leistungsfaehigkeit und Genauigkeit gewaehrleisten.

Was ist ein Entscheidungsbaum?

Ein Entscheidungsbaum aehnelt einem Flussdiagramm (Flow Chart), wobei der Baum ein Klassifikationssystem oder Vorhersagemodell darstellt. Der Baum ist wie eine Reihe einfacher Fragen aufgebaut und die Antworten zu diesen Fragen markieren den Weg den Baum hinab. Der erreichte Endpunkt bestimmt die Klassifizierung oder Vorhersage durch das Modell, welches eine qualitative Aussage (z.B. diese Gruppe interessiert sich fuer Ihr Produkt) oder eine numerische Vorhersage (z.B. der Verkauf wird sich um 15 Prozent steigern) sein kann.
Der unten dargestellte, einfache Entscheidungsbaum zum Beispiel sagt vorher, ob der Empfaenger eines Werbeangebots per Post antwortet oder nicht. Die Frage "Ist die Kreditwürdigkeit = 600?" teilt den Wurzel- oder Elternknoten in zwei Aeste und schickt die "Ja"-Faelle in den linken 'Kind'knoten und die "Nein"-Faelle nacht rechts. Da im linken Ast die 'Antworter' dominieren, werden wir zukünftige Angebote an dieses Kundensegment schicken; der rechte Ast wird von 'Nicht-Antwortern' dominiert und so werden wir dieses Segment nicht anschreiben.

Warum ist CART so einfach zu interpretieren?

Wie oben beschrieben, werden die Ergebnisse eines Data Mining-Projektes oft in einem baumfoermigen, anschaulichen Diagramm dargestellt. Aufgedeckte Beziehungen und Muster in den Daten - sogar in sehr komplexen Datenbanken mit hunderten von Variablen - werden als Flussdiagramm praesentiert. Vergleicht man dies mit den komplexen Parametern einer logistischen Regressionsanalyse oder dem Ergebnis der Berechnungen eines "neural nets", wird der Reiz von Entscheidungsbaeumen offensichtlich.
Die anschauliche Darstellung ermoeglicht die hierarchische Wechselwirkung der Variablen zu erfassen. Oft wird vorher bekanntes Wissen ueber wichtige Datenbeziehungen bestaetigt, was weiteres Vertrauen in die Verlaesslichkeit und Nuetzlichkeit des CART-Modells schafft. Ausserdem sind die Modelle einfach zu verstehen und leicht auf neue Daten anzuwenden weil einfache Wenn-Dann-Regeln vom Baum abgelesen werden koennen.

Wie wächst ein Entscheidungsbaum?

Es gibt mehrere Arten einen Entscheidungsbaum wachsen zu lassen aber CART benutzt ausschliesslich binaere oder Zweifach-Splits, die jeden Eltern-Knoten in genau zwei Kind-Knoten aufteilen, indem an jedem Entscheidungspunkt eine Frage mit Ja/Nein-Antwort gestellt wird. CART sucht nach Fragen, die Knoten in relativ homogene Kind-Knoten teilt wie z.B. eine Gruppe, die ueberwiegend aus Interessenten besteht oder Personen mit hohen Kreditrisiken oder Personen die Gelaendewagen gekauft haben. Wahrend der Baum waechst, werden die Knoten immer homogener und es werden wichtige Segmente identifiziert.
Andere Methoden, wie z.B. CHAID, favorisieren Mehrweg-Splits, die zwar grafisch ansprechende Baume ergeben, deren Modelle aber in weniger genauen Splits resultieren.

Warum ist CART unter Entscheidungsbaum-Programmen einzigartig?

Ein volles Jahrzehnt Forschung bildet die Basis für stabile Leistung und verlaessliche Resultate mit CART. Die fundierte Methodik von CART ist gekennzeichnet durch:
Verlaessliche Beschneidungs-Strategie - CART's Entwickler haben festgestellt, dass keine Stop-Regel verlaesslich genug waere, um einen optimalen Baum zu erhalten; deshalb hatten sie die Idee, Baeume zunaechst 'wuchern' zu lassen um sie anschliessend zurueckzuschneiden. Diese fuer CART fundamentale Idee sorgt dafür, dass wichtige Strukturen nicht durch zu fruehes Stoppen des Wachstums uebersehen werden.
Maechtiger binaerer Split-Suche-Ansatz - CART's binaere Entscheidungsbaeume gehen sparsam mit Daten um und finden viele Struktur bevor zu wenig Daten uebrig sind, um aus ihnen zu lernen. Andere Entscheidungsbaum-Ansaetze benutzen Mehrweg-Splits, die die Daten schnell fragmentieren und es hierdurch schwierig machen, Regeln aufzuspueren, deren Entdeckung groessere Datenmengen erfordern.
Automatische Selbstueberprueufung - bei der Suche nach Mustern in Datenbanken ist es wesentlich, der 'Ueberanpassungs'-Falle zu entgehen und zu vermeiden, Muster zu finden, die lediglich auf die Trainingsdaten zutreffen. CART's eingebaute Testprozeduren stellen sicher, dass die gefundenen Muster auch auf neue Datensaetze zutreffen. Ausserdem sind die Testprozeduren und Auswahl des optimalen Baumes ein integraler Teil des CART-Algorithmus, wohingegen in anderen Entscheidungsbaum-Techniken die Ueberpruefung erst anschliessend erfolgt und die Baumauswahl dem Anwender ueberlassen wird.
Zusaetzlich loest CART viele verschiedene angewandte modellierungs Probleme durch eine einzigartige Kombination automatisierter Verfahren:

• Ersatz-Teiler (surrogates) gehen intelligent mit fehlenden Werten um
• Anpassbare 'Strafen' fuer fehl Klassifikation helfen, teure Irrtuemer zu vermeiden
• Mehrfache Baeume, die "Committee of expert"-Methode steigert die Genauigkeit der Ergebnisse
• Alternative Teilungskriterien bringen Fortschritt wenn andere Kriterien versagen.
  

Welche Kriterien fuer das Wachstum von Baeumen (splitting criteria) bietet CART?

CART beinhaltet sieben Teilungskriterien die nur eine Variable berücksichtigen- Gini, Symgini, Twoing, ordered twoing und "class probability" fuer Klassifikationsbaeume, sowie kleinste Quadrate und kleinste absolute Abweichung fuer Regressions Baeume. Hinzu kommte ein multi-variables Splitting-Kriterium, die 'linear combinations' -Methode. Die voreingestellte Gini-Methode ergibt meist die besten Resultate aber unter bestimmten Umstaenden koennen andere Methoden genauere Modelle liefern.
CARTs einzigartige 'Twoing'-Prozedur zum Beispiel ist auf Klassifikationsaufgaben mit vielen Klassen abgestimmt, wie z.B. die Frage welches von 170 Produkten ein bestimmter Verbraucher auswaehlen wuerde.
Fuer schwierige Probleme, in denen sogar von den besten Modelle eine relativ geringe Genauigkeit erwartet wuerde, sind andere Teilungskriterien verfuegbar. Demographische Daten sind z. B. oft schwache Praediktoren fuer die Segmentierung von Meinungen oder Wahlergebnissen. Spezielle Optionen in CART koennen die Vorhersage-Genauigkeit solcher Modelle extrem erhoehen. Weitere einzigartige Kriterien sind fuer Aufgabenstellungen mit ungleichen Falsch-Klassifizierungs-Kosten, geordneten Zielvariablen und kontinuierlichen abhaengigen Variablen verfuegbar.
Um bestimmte Datenstrukturen effektiver zu bearbeiten bietet CART auch Splits fuer linear Kombinationen von kontinuierlichen Vorhersage-Variablen. Bei dieser Option sucht CART nach gewichteten Durchschnitten der Vorhersage-Variablen um diese als Teilungskriterien zu nutzen. Diese gewichteten Durchschnitte koennen wichtige Datenbankstrukturen aufdecken und neue kritische Groessen entdecken.

Was sind 'adujustierbare Strafen fuer Fehlklassifikationen"?

Anders als viele andere data-mining Instrumente ist CART auch fuer solche Situationen geeignet, in denen Falscheinteilungen oder Faelle, die fehlerhaft klassifiziert wurden, ernster sind als andere.
CART-Benutzer koennen hoehere Strafen fuer Fehlklassifikationen bestimmter Daten vorsehen und das Programm wird den Baum von diesem Fehlertyp wegleiten. Zusaetzlich wird CART, wenn es keine korrekte Klassifikation garantieren kann, versuchen sicherzustellen, dass die Fehler die es macht, weniger kostspielig sind. Wenn z.B. 'Kreditrisiko' als gering, maessig oder hoch eingestuft werden kann, waere es kostspieliger eine Person mit hohem Risiko als geringes Riskiko einzustufen als als maessiges Risiko. Traditionelle data-mining Instrumente koennen solche Irrtuemer nicht unterscheiden.

Was sind "intelligente Ersatzteiler fuer fehlende Werte"?

CART ersetzt fehlende Werte in Datenbanken mittels 'Stellvertretern' (Ersatzteilern). Dies sind Hilfsregeln, die versuchen die Aktionen des Hauptsplits genau imitieren.
Angenommen dass, in einem gegebenen Modell, CART die Daten anhand des Haushaltseinkommens teilt. Wenn kein Wert fuer das Einkommen verfuegbar ist, koennte CART das Bildungsniveau als guten Ersatz betrachten.
Der Ersatzteiler enthaelt Informationen, die typischerweise denen aehnlich sind, die im Hauptteiler gefunden werden koennen. Andere Produkte behandeln alle Datensaetze mit fehlenden Werten als haetten all diese Datensaetze denselben fehlenden Wert; mit einem solchen Ansatz landen all solche unvollstaendigen Datensaetze im gleichen Kasten eines Baumes. In CART wird jeder Datensatz so verarbeitet, dass fuer ihn spezielle Werte benutzt werden; dies erlaubt, Datensaetze mit verschiedenen Datenstrukturen auch unterschiedlich zu behandeln, was zu einer besseren Charakterisierung der Daten fuehrt.
Durch die Benutzung von Stellvertretern erzeugt CART robuste und verlaessliche Vorhersagemodelle, sogar wenn es fuer sehr grosse Datenbanken mit Hunderten von Variablen und vielen fehlenden Werten benutzt wird. CART's Identifizierung von Ersatz-Vorhersagevariablen bietet auch einen effektiven Weg, guenstige Vorhersage-Mechanismen zu entdecken. Wenn das beste Splitkriterium in einem Baum eine teure oder schwer erhältliche Information beinhaltet, kann statt dessen ein guenstigerer Stellvertreter erwogen werden.

Was steckt hinter CART's "automatischer Selbstvalidierung"?

CART benutzt zwei Testprozeduren um den 'optimalen' Baum auszuwaehlen. Der optimale Baum ist der Baum mit den geringsten gesamten Fehlklassifikationskosten und damit der hoechsten Genauigkei. Beide Prozeduren, eine fuer kleine und eine fuer grosse Datenmengen, sind voellig automatisiert und stellen sicher, dass der optimale Baum vorhandene Daten genau klassifiziert und zukünftige Resultate möglichst exakt vorhersagt.
Fuer kleinere Datenmengen und Faelle, in denen der Analyst keine Daten fuer Testzwecke zurueckhalten möchte, benutzt CART das Verfahren der "Kreuzvalideriung" (cross-validation). Dies wird haeufig in der medizinischen Forschung genutzt, aber ein Mangel an Trainingsdaten kann bei Studien jeglicher rarer Ereignisse vorkommen, wie z.B. spezielle Arten von Betrug. Bei Kreuzvalidierung werden typischerweise zehn verschiedenen Baeume erzeugt, jeder aus verschiedenen 90 Prozent der gesamten Datenmenge. Wenn die Resultate aller zehn Baeume zusammengefuehrt werden, wird eine sehr verlaessliche Bestimmung der optimalen Baumgroesse erreicht. Fuer grosse Datenmengen waehlt CART automatisch Testdaten aus oder benutzt vorab definierte Testdatensaetze oder Testdatengruppen um den Baum zu validieren.

Was ist "multiple-tree, committee-of-expert method," oder "bootstrap aggregation"?

Der Gebrauch von mehreren Baeumen in einem Expertenkomittee is eine relativ neue Technik und einer der Erfinder von CART hat einen ueberaus effektiven Weg entwickelt, Baueme zu kombinieren. Vorhersagefehler koennen bis zu 50 Porzent reduziert werden indem CART dazu gebracht wird, 50 oder mehr willkuerliche Stichproben aus den Trainingsdaten zu ziehen, einen eigenen Baum für jede Probe zu erstellen und dann diesen verschiedenen Bauemen zu erlauben, die beste Klassifizierung zu 'waehlen'. Die Kombination von Baeumen kann einen deutlichen Leistungsvorsprung gegenueber jeglichen anderen data-mining-Prozeduren bringen, wenn sie sinnvoll eingesetzt wird.

Wann ist die Nutzung von CART als Einzelloesung vorteilhaft?

Die meisten data-mining-Projete beinhalten Klassifizierungen, um Einblick in die Strukturen vorhandener Daten zu gewinnen, sowie die Erstellung eines Vorhersagemodells aus diesen Strukturen. Typische Klassifizierungsprojekte sind das Trennen von Profitablem und Unprofitablem, das Entdecken von fehlerhaften Behauptungen, die Identifizierung von Mehrfachkaeufern, die Beschreibung wertvoller Kunden oder das Markieren von riskanten Kreditantraegen.
CART ist ein Klassifizierungsinstrument auf dem neuesten Stand der Technik, das als Einzelloesung jegliche Klassifizierungsaufgabe loesen und robuste, akkurate Vorhersagemodelle liefern kann. Das Programm bewaeltigt die zentralen Herausforderungen des data-mining indem es Klassifizierung fuer kategoriale Variablen (z.B. Ja - Nein) und Regressionen fuer kontinuierliche Variablen (z.B. Umsatzzahlen) ermöglicht.
Zusaetzlich zu seiner Genauigkeit bietet CART drei entscheidende Vorteile gegenueber anderen data-mining-Instrumenten. Erstens ist CART auch fuer Anfaenger leicht zugaenglich und erfordert keine uebermaessigen technischen Fertigkeiten vom Benutzer. CART's neue, benutzerfreundliche graphische Oberflaeche und Benutzerhandbuch fuehrt den Anwender schnell durch den Analyseprozess und die Voreinstellungen funktionieren so gut, dass auch viele erfahrene Experten diese nicht aendern. Zweitens sind CART-Resultate extrem einfach zu interpretieren; das baumfoermige Diagramm verdeutlicht die wichtigsten Prädiktoren. Und schliesslich ist CART erheblich preiswerter als andere data-mining-Programmpakete waehrend die Ergebnisse der Projekte vergleichbar sind.

Wie kann CART andere data-mining Programmpakete ergaenzen?

CART ist eine hervorragende Ergaenzung von data-mining-Programmpaketen wie SAS®. Im ersten Schritt eines data-mining-Projektes kann CART die wichtigsten Variablen aus einer grossen Liste von potentiellen Prädiktoren finden. Ein Neuronales Netz oder andere data-mining-Techniken werden nachhaltig beschleunigt wenn sie auf die Top-Variablen aus dem CART-Model konzentriert werden kann. Vor allem bei "neural nets" umgeht CART 'das Rauschen' sowie irrelevante Variablen und waehlt schnell und effektiv die besten Variablen fuer den Input aus. Das Ergebnis sind deutliche Verbesserungen der Trainingsgeschwindigkeit eines "neural nets" und ebenfalls genauere bzw. robustere "neural nets". Ausserdem kann der Output von CART- oder die 'vorhergesagten Werte' als Input eines "neural net" genutzt werden.
CART kann ausserdem genutzt werden, um:

• Leistungen zu "Benchmarken",
• Wichtige Wechselwirkungen, die in statistischen Modellen enthalten sein sollten, zu endecken
• Variablen mit fehlenden Werten, Werte zuweisen.
  

Wie schnell erzeugen CART Resultate?

CART's effizienter Algorithmus erzeugt Resultate sehr viel schneller als andere Methoden wie z.B. "neural nets". Auf einem industrieueblichen Server erzeugt CART bei 300.000 Datensaetzen und 1.000 Variablen, Ergebnisse in unter einer Stunde.
Ueblichere Probleme mit 100.000 Datensaetzen und 450 Variablen laufen in ca. 10 Minuten waehrend 100 Variablen und eine Million Datensaetze weniger als 30 Minuten benoetigen.
Explorative Auswertungen, die auf Teilmengen groesserer Datenbanken basieren, koennen sogar noch schneller durchgefuehrt werden; z.B. werden 30.000 Datensaetzen mit 100 ausgewaehlten Input-Variablen in weniger als fuenf Minuten durchgerechnet.

System-Voraussetzungen

Weitere Informationen

• CART Homepage (Salford Systems).

• CART DM Review