HMM: ловим мошеннические транзакции

    Три года я проработал в Сербии iOS-евангелистом - было два профильный проекта и один Machine Learning-овый.

    Если вам стало интересно - добро пожаловать в мир HMM.

    Постановка задачи

    Австрийский банк. У него много клиентов, у клиентов открыт счет в этом банке. В течении года клиент тратит средства со своего счета. Ходит в магазины, гасит коммунальные платежи и пр. Каждое списание денег со счета назовем транзакцией. Дана последовательность транзакций за определенное время (скажем год). Надо обучить машину, чтобы она начала проверять новые транзакции как достоверные или подозрительные. И выдавала предупреждение в последнем случае. Для решения задачи надо использовать Hidden Markov Model.

    Введение в HMM

    Я болею коронавирусом каждый год 10 дней подряд. Остальные дни здоров, как бык.

    Представим эту последовательность из 365 символов в виде массива. h означает здоров, l - болен.

    days{365} = {hhhhhhhhhhllllllllllhhhhhhhhhhhhhhhhhhhhhhhh...hhhhh}

    Вопрос - Какова вероятность, что я сегодня болен?

    \frac{10}{365}= 3 процента

    Если вам понятен ответ, то читайте дальше, через 15 минут вы станете экспертом по HMM. Если нет - ставьте плюс и идите ужинать.

    Изменим вопрос - Какова вероятность, что я завтра буду больным?

    Вы резонно уточните: -А сегодня я болен или здоров?

    Если болен (смотрите на последовательность - таких больных дней всего 10), то с вероятностью \frac{9}{10}= 90 процентов завтра я продолжу болеть и с вероятностью 10 процентов стану здоров.

    А если я сегодня здоров? - то с вероятностью

    \frac{1}{355}= 0.3 процента я завтра заболею и с вероятностью 99.7% буду здоров.

    Если вы сегодня больны, то с вероятностью 10% завтра вы будете здоровы и 90% продолжите болеть.

    Получили 4 числа, которые красиво вписываются в матрицу 2 на 2 - вуаля! эта матрица и есть Марковский слой. Уберем проценты, оставим чистые вероятности в диапазоне от 0 до 1, как того требует наука.

    здоров

    болен

    здоров

    0.997

    0.003

    болен

    0.10

    0.90

    Еще раз взглянем на матрицу и прочитаем слева направо, что если ты сегодня здоров, завтра с вероятностью 0.997 ты останешься здоров, а с вероятностью 0.003 заболеешь и так далее.

    Формализуем транзакции

    Чем отличается последовательность транзакций от череды болен/здоров? Ничем.

    Для доказательства этого возьмем список транзакций, который мне предоставил Сбережении по моей просьбе.

    27.10.2020 00:00 GAZPROMNEFT AZS 219    2507,43 118 753,95 28.10.2020 / 298380 Автомобиль
     26.10.2020 14:45 SPAR 77                319,73 121 261,38 27.10.2020 / 220146 Супермаркеты
     26.10.2020 14:38 ATM 60006475           4800,00 121 581,11 26.10.2020 / 213074 Выдача наличных
     25.10.2020 17:52 EUROSPAR 18            970,02 126 381,11 26.10.2020 / 259110 Супермаркеты
     25.10.2020 00:00 Tinkoff Card2Card      20000,00 127 351,13 26.10.2020 / 253237 Перевод с карты
     22.10.2020 14:22 SBOL перевод 4276      7000,00 147 351,13 22.10.2020 / 276951 Перевод с карты
     22.10.2020 12:18 STOLOVAYA              185,00 154 351,13 23.10.2020 / 279502 Рестораны и кафе
     21.10.2020 16:46 MEGAFON R9290499831    500,00 154 536,13 21.10.2020 / 224592 Комунальные платежи, связь, интернет.
     21.10.2020 14:17 SPAR 77                987,03 155 036,13 22.10.2020 / 219015 Супермаркеты
     21.10.2020 13:42 PYATEROCHKA 646        289,93 156 023,16 22.10.2020 / 294539 Супермаркеты
     21.10.2020 00:00 MEBEL                  75,00 156 313,09 22.10.2020 / 279935 Прочие расходы
     19.10.2020 14:54 SPAR 77                552,92 132 044,80 20.10.2020 / 208987 Супермаркеты
     19.10.2020 00:00 MOBILE FEE             60,00 132 597,72 20.10.2020 / - Прочие операции
     16.10.2020 14:19 SPAR 77                579,39 132 657,72 17.10.2020 / 229627 Супермаркеты
     12.10.2020 13:33 STOLOVAYA              185,00 133 237,11 13.10.2020 / 261374 Рестораны и кафе
     12.10.2020 00:00 OOO MASTERHOST         1000,00 133 422,11 13.10.2020 / 268065 Прочие расходы
     11.10.2020 12:09 SPAR 77                782,87 134 422,11 12.10.2020 / 275816 Супермаркеты
     10.10.2020 14:52 SBOL перевод           400,00 135 204,98 10.10.2020 / 276925 Перевод с карты
     09.10.2020 13:29 SBOL перевод 5484*     1000,00 135 604,98 09.10.2020 / 229184 Перевод с карты
     09.10.2020 11:55 MAGNIT MK KRYUCHYA     274,00 136 604,98 10.10.2020 / 209914 Супермаркеты
    

    Напишем на питоне скрипт, который вытащит последовательность моих транзакций в рублях и нарисует график

    def readtrans():
        with open ("assets/trans.txt", "r") as file:
            grades = file.read()
        pattern = '(\d{2,5}),\d\d'
        result = re.findall(pattern, grades)
        r = list(map(int, result[0::2]))
        return r
    
    data = readtrans()
    t = list(range(len(data)))
    df = pd.DataFrame({'number':t, 'amount':data})
    ax1 = df.plot.bar(x='number', y='amount', rot=0, width=1.5)
    
    

    Упростим картину - дешевые транзакции (менее 10$) обозначим буквой l, дорогие свыше 100$ буквой h, остальные - буквой m.

    Наша последовательность стала выглядеть подозрительно знакомо

    print(observations[:20])
    trans[] = ['m', 'm', 'm', 'l', 'm', 'm', 'h', 'm', 'l', 'l', 'm', 'l', 'l', 'l', 'l', 'l', 'l', 'm', 'l', 'l']

    Теперь напишем Марковский слой для транзакций. Это будет матрица 3 на 3, поскольку у нас 3 возможных типа транзакций = {l,m,h}

    [[0.5 0.3 0.2]
     [0.6 0.3 0.1]
     [0.7 0.3 0.0]]

    Расшифровываем последнюю строку матрицы - если последняя транзакция была дорогая, то с вероятностью 0.7 последующая операция будет дешевой, с вероятностью 0.3 - средней и никогда снова дорогой.

    Эта матрица, этот явный Марковский слой характеризует каждого клиента банка. То есть легко пересчитать данную матрицу при поступлении нового платежа и по какой-то метрике сравнить с канонической. Если отклонение большое - транзакция подозрительна.

    -Так просто?! - воскликнет читатель. Да, но за построение такой простой модели банк много денег не заплатит. Надо ввести еще один Марковский слой (невидимый), и алгоритм сразу станет красивее, сложнее и наукоёмчее. И потянет на кандидатскую диссертацию.

    Скрытый Марковский слой

    Посмотри, читатель, на подробную расшифровку моих платежей. Многие действия повторяются - походы в столовую, пятёрочка, спар, Газпромнефть, мобильный платеж...

    То есть существует набор периодических однотипных событий, число которых мы не знаем и Марковский слой для которых невозможно построить. Как построишь, если ничего не знаешь конкретно?! Вот именно. Но мы знаем, что эти события происходят и их примерно 4-6 штук. Поход в магазин. Столовая. Еще что-то. И так далее. И что мы точно знаем, что после похода в столовую мы никогда не опустошаем свой кошелек на сумму более 300 рублей.

    Таким образом, мы можем задать матрицу невидимого слоя 5 на 5 (предположим 5 на 5) в которой будет 20 неизвестных чисел.

    [[a1 a2 a3 a4 a5]
     [b1 b2 b3 b4 b5]
     [c1 c2 c3 c4 c5]
     [x1 x2 x3 x4 x5]
     [y1 y2 y3 y4 y5]]

    Именно 20, а не 25 (отвечать будет Ягуар). Это точно такой же Марковский слой, что мы строили раньше, но основанный на 5 событиях.

    И чтобы связать два слоя (видимый с платежами и невидимый с событиями) мы заведем матрицу перехода размера 5 на 3.

    В чем смысл матрицы перехода? В том, что после невидимого события a (поход в столовую)

    у нас произойдет с разной степенью вероятности либо l-платеж, либо m-платеж, либо h-платеж. Скорее всего после похода в столовую эта строка будет такая

    [0.96 0.04 0.0]

    Что означает невозможность потратить более 100 долларов в нашей технопарковской столовой. Даже с приглашенной девушкой.

    Таким образом, у нас есть известная матрица вероятностей с явного слоя, неизвестные 20 значений в матрице с невидимого слоя и 10 неизвестных значений из переходной матрицы.

    И мы можем найти эти 20+10 неизвестных величин, потому что у нас есть история платежей!

    Это прекрасно и это называется обучить систему!

    После того как вы обучите систему, вы легко проверите по упомянутому выше алгоритму входящую транзакцию на подозрительность.

    Обучение

    В питоне есть библиотека hmm, в которой существует метод обучения - ему надо подать ваши три матрицы, и серию последовательностей из транзакций. Алгоритм такой, что вы разбиваете историю ваших транзакций порциями штук по 15-20 и скармливаете ее, пока система не обучится.

    Процесс сходимости хорошо виден на графике.

    После этого вы обученной системе подаете новую транзакцию и она по выбранному вами критерию отбраковывает ее или одобряет.

    Питон против Сишарпа

    Работодатель обязал меня использовать библиотек Accord и язык C#

    using Accord.MachineLearning;
    using Accord.Statistics.Models.Markov;
    using Accord.Statistics.Models.Markov.Learning;
    using Accord.Statistics.Models.Markov.Topology;
    using Comtrade.FMS.Common;
    

    Согласно контракту я не могу разглашать код, поэтому написал аналог на Питоне (я не знаю оба языка) и частично смог повторить результат. Но по скорости обучения Питон сильно проигрывает Си-шарпу. Правда, я run-ил программу на разного класса компьютерах)) В Словении это был сервер работодателя. Питон для Хабра пыхтел на 2010 года макбуке.

    Приведу одну строку кода, в которой зашифрован метод обучения.

    var teacher = new BaumWelchLearning(hmm)

    Детали метода Баум-Уэлша вы поймете, прочитав соответствующую литературу и настроив свои мозги на стат. процессы.

    Успехов и хорошей карьеры в банковских IT структурах!

    Комментарии 7

      0
      У меня только один вопрос по итогу прочтения статьи.
      Как это по-русски?
      MAGNIT MK KRYUCHYA
      Я знаю, что Магнит рандомайзером называет каждый свой магазин каким-либо словом. И вроде как обычно это прилагательное. Тут-то что за слово? Крючья?
      0

      Простите, но если 10 дней в году вы гарантированно болеете, а сейчас здоровы, то в знаменателе должно быть (365 — дата)… разве нет? поставил плюс, ушел ужинать.

        0
        Вадим, спасибо, что поделились опытом!
        Мне мозгов не хватит, чтобы воспроизвести этот эксперимент. Позвольте обнаглеть и попросить у вас минимальный пример кода на питоне?
        0
        В начале статьи сказано про Сербию, в конце — про Словению, вы точно нам правду говорите?
          0
          Я работал (см код) в Comtrade. У компании офисы почти во всей Югославии — в Белграде, Сараево, Любляне, Мариборе и Крагуеваце. Математическое отделение в Любляне (там был этот проект), а основное время сидел в Крагуеваце (Сербия).

        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

        Самое читаемое