Automatische Erkennung von Transaktionen zwischen eigenen Bankkonten

Vielleicht sind Sie auch schon mal darüber gestolpert: Das Online Banking vieler Banken erkennt Transaktionen zwischen Ihren verschiedenen Konten nicht als solche. Eine Überweisung vom Tagesgeld auf das Girokonto zum Beispiel wird als höhere Ein- und Ausgabe angezeigt, obwohl sie natürlich eigentlich nichts an Ihren Ein- und Ausgaben ändert.

In diesem Blog beschreiben wir einen von uns für ein MVP einer Finanzmanagement-App entwickelten Algorithmus der dieses Problem lösen kann. Das Problem ist wie folgt: Jede Transaktion in einem der Konten einer Person (z.b. Girokonten, Kreditkarten, Tagesgeld, etc. ) könnte entweder zu einer anderen Transaktion in einem anderen Ihrer Konten gehören, wir nennen diese beiden dann ein internes Transaktionspaar, oder auch nicht (dann ist es eine externe Transaktion).

In einigen Fällen kann man diese internen Transaktionspaare leicht erkennen da zum Beispiel der Name des Kontoinhabers als Empfänger und Auftraggeber auftaucht. Oft ist es aber schwieriger, da der Name vielleicht leicht anders geschrieben ist, oder auch kein Auftraggebername auftaucht, sondern nur z.B. “Kreditkartenabrechnung”. Unser Algorithmus muss solche Fälle also abdecken und sollte robust genug sein um möglichst alle interne Transaktionspaare automatisch zu erkennen.

 

Algorithmus

Bevor wir den Algorithmus en detail beschreiben, hier zunächst eine kurze Übersicht. Aus der großen Menge von in Frage kommenden Transaktionspaaren muss der Algorithmus entscheiden welche davon interne Transaktionspaare sind, und welche nicht. Der Ablauf dafür ist wie folgt:

  1. Ausgehend von der Liste aller Transaktionen, stelle alle möglichen Transaktionspaare zusammen
  2. Rechne einen Unterschiedsindikator der beiden Transaktionen jedes möglichen Transaktionspaars aus
  3. Lerne interne Transaktionenspaare von externen Transaktionen zu unterscheiden an Hand der Unterschiede Ihrer Unterschiedsindikatoren
  4. Finde die am besten passenden unter den möglichen Transaktionspaaren, und entscheide ob diese ein internes Transaktionspaar sind oder nicht

1. Mögliche Transaktionspaare

Der Algorithmus benötigt die Liste der Transaktionen aller Konten einer Testperson. Jede Transaktion ist dann eine Zeile in einer Tabelle, mit Spalten die unter anderem das Datum, der Geldwert, die Betreffzeile, den Namen von Sender und Empfänger und die Kontonummer angeben — insgesamt eine Anzahl von $M$ Eigenschaften (“Features”).

Wir können die Anzahl der in Frage kommenden Paare von jeweils zwei Transaktionen stark reduzieren, in dem wir alle Transaktionen in Gruppen einordnen, deren Geldwert betragsmäßig gleich ist. Als Beispiel, alle Transaktionen mit Geldwert von +1000 Euro und -1000 Euro fallen in eine Gruppe. Alle möglichen Transaktionspaare ergeben sich dann als alle möglichen Kombination einer positiven mit einer negativen Transaktion innerhalb dieser Gruppe.

Die resultierende Liste von möglichen Transaktionspaaren ist dadurch viel kleiner als durch eine naive Bildung aller möglichen Kombination von Transaktionen. Bei den Kontodaten unserer Testpersonen zum Beispiel reduziert sich dadurch die Anzahl der möglichen Transaktionspaare von 3 Millionen auf ca. 2500, was das Problem deutlich vereinfacht.

2. Ähnlichkeit von Transaktionen

Für jedes mögliche Transaktionspaar rechnen wir aus verschiedene Kombinationen der $M$ Features der beiden Transaktionen einen Unterschiedsvektor aus. Um das anschaulicher zu machen: Ein Eintrag in diesem Unterschiedssvektor beschreibt zum Beispiel wie weit das Datum der beiden Transaktionen auseinander liegen, ein anderer wie sehr sich die Namen von Sender und Empfänger der Transaktion unterscheiden und ein weiterer beschreibt ob die Kontonummer von Sender und Empfänger gleich sind.

Je nach Art des Features benutzen wir unterschiedliche Maße für Unterschiedlichkeiten: Bei Kontonummern testen wir auf Gleichheit, bei textartigen Features benutzen wir Maße basierend entweder auf dem längste gleichen Teiltext, oder testen einfach ob ein Text den anderen enthält.

So erhalten wir für jedes mögliche Transaktionspaar einen Unterschiedsvektor der 12 Dimensionen hat — was soll man sich darunter vorstellen? Jede dieser Dimensionen beschreibt einen anderen Aspekt der Unterschieden zwischen den beiden Transaktionen: Eine bezieht sich auf den zeitlichen Abstand, Unterschiede in der Betreffzeile, und so weiter. Um die 12-dimensionalen Unterschiedsvektor anschaulicher in zwei Dimensionen darzustellen, benutzen wir eine Technik namens T-Distributed Stochastic Neighbor Embedding oder kurz t-SNE. Wir nutzen die Implementierung von t-SNE im Open Source Paket Scikit-learn.

 

In Abbildung 1 sieht man die Unterschiedsvektoren der ca. 2500 möglichen Transaktionspaare als farbige Punkte. Unterschiedsvektoren die sich in Ihrem 12-dimensionalen Raum stark unterscheiden, werden durch t-SNE als zwei weit voneinander entfernt liegende Punkte im zwei Dimensionen dargestellt, und anders herum liegen die Punkte zweier ähnliche Unterschiedsvektoren nah beieinander. Datenpunkte die zu internen Transaktionspaaren gehören haben wir blau dargestellt, alle anderen in rot. Man sieht dass es zwar Muster gibt — die meisten blauen Punkte liegen in einer Ecke — aber einfach zu beschreiben oder gar zu trennen scheinen sie noch nicht.

3. Unterscheidung von internen und externen Transaktionspaaren

Um die statistischen Unterschiede zwischen externen und internen Transaktionspaaren sicher zu erkennen (also die roten und blauen Punkte in Abbildung 1 zu unterscheiden), benutzen wir Methoden des überwachten statistischen Lernens: Wir markieren die externen Transaktionspaare in den Daten einer Testperson als solche, und benutzen einen Algorithmus der den Zusammenhang von Unterschiedsvektor zu Transaktionsklasse (intern oder extern) lernen kann. Sobald dieser Zusammenhang gelernt ist, können wir basierend darauf entscheiden welche der möglichen Transaktionspaare interne, und welche externe sind.

Zur Klassifikation in externe und interne Transaktionspaare benutzen wir eine Support Vector Machine. Anschaulich gesprochen, während es unmöglich ist in der zweidimensionalen Darstellung von Abbildung 1 eine saubere Trennung von roten und blauen Punkten durch eine Linie zu erreichen, ist in dies in einem hochdimensionalen Raum oft sehr gut möglich. Dort lassen sich die Punkte der beiden Klassen oft sauber durch eine Entscheidungsgrenze trennen — eine Support Vector Machine automatisiert und vereinfacht diese Schritte.

Wir benutzen die Implementierung eines Support Vector Classifiers in Scikit-learn mit einem Kernel aus radialen Basisfunktionen, und passen die Parameter bis die Fehler erster und zweiter Art bei der Klassifikation verschwindend gering sind.

Jetzt können wir zu jedem möglichen internen Transaktionspaar mit dem Support Vector Classifier vorhersagen ob dieses Paar eine interne Transaktion ist, ob es also eine Transaktion zwischen meinen eigenen Konten beschreibt, oder nicht.

4. Auswahl aus den möglichen Transaktionspaaren

Im letzten Schritt müssen wir sicherstellen dass jede Transaktion maximal Teil eines internen Transaktionspaars ist, alles andere würde ja wenig Sinn machen. Das ist nicht automatisch der Fall, da der Support Vector Classifier, wie im letzten Abschnitt beschrieben, einige der möglichen Transaktionspaare als interne klassifizieren könnte die damit eine Transaktion mehr als einmal beinhalten.

Wir wollen jede Transaktionen dem Transaktionspaar zuordnen, mit dem sie zusammen laut unserem Support Vector Classifier am ehesten ein internes Transaktionspaar darstellen — oder, falls keins der Paare danach aussieht, die Transaktion als extern klassifizieren. Es gibt verschiedene Wege dieses Problem anzugehen:

  • Formulierung als Binary Integer Linear Programming Optimierungsproblem
  • Durch Simulated Annealing, einen Markov Chain Monte Carlo Algorithmus  der den Raum der möglichen Transaktionspaare zufällig durchschreitet bis zumindest ein lokales Optimum gefunden ist
  • Eine heuristische Methode, die Transaktionen nacheinander zu dem “passendsten” Transaktionspaar zuweist (nicht notwendigerweise dem optimalen)

Wir probieren zuerst die heuristische Methode aus. Diese geht von der Liste der Transaktionen mit positivem Geldbetrag aus und geht diese nacheinander durch. Sie weist jeder dieser Transaktionen entweder der am besten passenden (laut Schätzung des Support Vector Classifiers) negativen Transaktion zu, oder klassifiziert sie, falls keine negative Transaktion passend genug erscheint, als externe Transaktion.
Alternativ implementieren wir eine simulated annealing Methode, die allerdings wesentlich höhere Laufzeiten hat. Da wir mit der heuristischen Methode schon sehr gute Ergebnisse erreichen, begnügen wir uns erst mal mit dieser.

Performance und Validierung

Wir können den Algorithmus validieren in dem wir Ihn auf eine Liste von Transaktionen anwenden, die wir nicht zum Trainieren und Entwickeln verwendet haben (Cross Validation). Hierzu benutzen wir die Transaktionen der Konten einer anderen Testperson — und erreichen auch hier sehr gute Ergebnisse. Die Fehler erster und zweiter Art sind sehr klein und liegen beide unterhalb von 5%. Ständen weitere Daten zur Verfügung würde man diese Validierungsmethode weiter ausbauen, und damit den Algorithmus weiter optimieren.


Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.