Подходы к агрегации данных и извлечению факторов в задаче поиска мошенничества в банковских транзакциях © О. И. Травкин Московский государственный университет имени М. В. Ломоносова, Москва travkin.o.i@gmail.com Аннотация Россия является самой быстрорастущей страной по объёму потерь от мошенничества с банковскими В данной статье проводится обзор подходов к картами [11]. агрегации данных и извлечению факторов для Нетрудно увидеть, что проблема выявления исследования потребительского поведения клиентов мошенничества в банковских транзакциях стоит в задаче поиска мошенничества в банковских достаточно остро. Эффективный инструмент транзакциях. Для выявления мошеннических решения проблемы мошенничества – использование операций с банковскими картами очень важно алгоритмов машинного обучения. Но для этого, в анализировать историческое потребительское первую очередь, необходимо определить факторы, поведение клиентов. В данной статье рассмотрено позволяющие выявлять мошеннические операции. два подхода. Первый подход – на основе трёх Особенностью рассматриваемой области является профилей клиентов: глобального, локального и то, что использование сырых данных (поток частотно-временного. Глобальный профиль строится транзакций) не даёт приемлемого результата [5]. с помощью кластеризации клиентов исходя из Поэтому данная работа будет сосредоточена на том, характеристик их транзакций, что позволяет более чтобы сделать обзор существующих подходов к точно работать с новыми или неактивными агрегации и извлечению факторов из клиентами. Локальный профиль – исходя из транзакционных данных. При таком подходе исторического потребительского поведения каждого учитывается важная для выявления мошенничества клиента. Частотно-временной профиль – с помощью информация о прошлом поведении клиента и его анализа паттернов в операциях клиентов, потребительских привычках. построенных на основе частот совершения Существуют различные алгоритмы машинного транзакций за определённый промежуток времени. обучения, а также различные подходы к обучению. Второй подход – RFM (Recency-Frequency- Для эффективного и качественного решения задачи Monetary). Его суть заключается в расчёте выявления мошенничества необходимо выбрать периодичности, частоты и объёма проводимых такой подход и алгоритм, который наилучшим клиентом операций за определённый промежуток образом впишется в рассматриваемую область. Есть времени. Кроме этого, предлагается модификация основания полагать, что наилучшим вариантом алгоритма DBSCAN для частичного обучения, будет подход с частичным обучением. Он учитывают которая может позволить значительно улучшить кластерную структуру неразмеченных данных, точность результатов поиска мошенничества на одновременно учитывая размеченные обучающие основе выявленных профилей и RFM характеристик. примеры. В статье будет приведено обоснование Работа частично поддержана РФФИ (гранты 14- того, почему частичное обучение подходит для 07-00548, 16-07-01028). решения задачи мошенничества с банковскими картами наилучшим образом. Кроме того, будет 1 Введение предложена модификация алгоритма DBSCAN для выявления мошенничества в банковских Число пользователей банковских карт в России транзакциях на основе алгоритмов частичного растёт стремительно. К сожалению, ещё более обучения, тестирование которой будет проведено в стремительно растёт количество мошенничества с рамках следующих работ. картами. По данным компании FICO за 2013 год Дальнейшее изложение будет организовано следующим образом: в секции 2 будет дано описание Труды XVIII Международной конференции предметной области, в секции 3 – приведён перечень DAMDID/RCDL’2016 «Аналитика и управление методов, используемых для выявления данными в областях с интенсивным мошенничества с банковскими картами. В секции 4 использованием данных», Ершово, 11-14 октября будет дан обзор подходов к агрегации данных и 2016 извлечению факторов. Далее, в секции 5 будет 257 рассмотрен алгоритм на основе частичного транзакции, чтобы разделить их на небольшие обучения. В секции 6 приведены результаты кластеры, максимально непохожие друг на друга. эксперимента по применению алгоритма к Если новая транзакция не попадает в один из симуляционным данным. кластеров, считающийся нормальным, то срабатывает триггер для такой транзакции [4]. В 2 Предметная область тоже время большинство работ рассматривает обучение с учителем, которое использует прошлые Мошенничество с банковскими картами принято мошеннические транзакции, чтобы сделать вывод о делить на две большие категории: заявочное и подозрительности текущих. Наиболее поведенческое мошенничество. Заявочное распространённым инструментом в данной мошенничество может возникнуть при получении предметной области для обучения с учителем новой карты в компании эмитенте [4]. Для являются искусственные нейронные сети [2,6,9, предотвращения мошенничества такого типа часто 12,15,21,23], так как обычно с их помощью используют кредитный скоринг. Что касается достигается более высокое качество. Тем не менее, поведенческого мошенничества, то его делят на 4 получаемые модели не интерпретируемы. В типа: кража почты (ситуация, когда мошенник последнее время также часто используются получает доступ к конверту с картой до того, как она ансамбли методов, например, метод случайного леса придёт к законному владельцу), потерянные и [3,8,26]. К оставшимся методам, используемым для украденные карты, подделанные карты (создание выявления мошенничества, можно отнести физической копии карты) и «без предоставления рассуждения на основе прецедентов [25], карты». Мошенничество «без предоставления Байесовские сети [15], деревья решений [20], карты», в отличие от трёх предыдущих не требует логистическую регрессию [3,21], скрытые наличия самой карты – оно совершается удалённо с Марковские цепи [22], ассоциативные правила [19], помощью украденной информации о реквизитах метод опорных векторов [3] и генетические кары [5]. Это очень удобный способ мошенничества, алгоритмы [10]. так как он почти полностью анонимный. Финансовые институты борются с 4 Стратегия агрегации данных мошенничества на двух уровнях: противодействие мошенничеству и выявление мошенничества [4]. При разработке моделей выявления Противодействие мошенничеству включает в себя мошенничества с кредитными картами, обычно, все действия и меры направленные на то, чтобы изначально доступен только сырой набор данных, мошенничество никогда не случилось. Сюда можно включающий в себя исключительно информацию по отнести активацию карты перед первым индивидуальным транзакциям. В Таблице 1 использованием, одноразовые пароли, пин-код и так перечислены атрибуты, которые присутствуют в далее. Что касается выявления мошенничества, то большинстве выборок данных о транзакциях. сюда относятся системы и практики по скорейшему выявлению мошенничества, если оно уже произошло Таблица 1 Типичный состав атрибутов [4]. Чем скорее мошенничество будет выявлено, тем Имя атрибута Описание меньше будут потери от него, так как карта и все Уникальный идентификатор Transaction ID транзакции по ней будут заблокированы. транзакции В данной статье рассматриваются подходы к Time Дата и время транзакции выявлению поведенческого мошенничества. Прежде Account number Идентификатор клиента всего, необходимо дать определение мошенничеству Card number Идентификатор карты в рамках выбранной категории: операцию с Transaction type Internet, ATM, POS… банковской картой клиента будем называть Amount Сумма транзакции мошеннической, если она совершается без ведома Currency Валюта транзакции клиента и против его интересов. Кроме того, Merchant code Код вида торговой точки (MCC Code) необходимо учитывать, что мы можем выявить Merchant group Группа торговой точки только те мошеннические операции, которые Country Страна проведения транзакции реализовались достаточное число раз, не похожи по некоторым своим характеристикам на предыдущие Чаще всего сырых данных недостаточно для операции клиента [15], но похожи на предыдущие построения качественной модели [5], так как при выявленные мошеннические транзакции [18]. выявлении мошенничества необходимо учитывать поведенческие особенности каждого клиента. Для 3 Методы выявления мошенничества этого создаётся набор новых переменных, включающих в себя информацию о предыдущих Наибольший интерес представляют транзакциях. Для создания таких переменных статистические методы выявления мошенничества. применяют так называемую стратегию агрегации Они делятся на две большие группы: обучение с [26]. Данный подход наиболее популярен на текущий учителем и обучение без учителя. Обучение без момент. Смысл агрегации – собрать информацию о учителя использует характеристики клиента или его транзакциях клиента за последнее время: сумму и 258 количество транзакций в разрезе карты, страны, помощью рассчитывается вероятность операции в валюты, вида торговой точки и так далее. Один из контексте предыдущих. Для этого строятся подходов к учёту поведенческих особенностей одномерные гистограммы по значениям каждого из клиента основан на профилировании, когда для атрибутов. Гистограммы нормируются так, чтобы каждого клиента выделяются три составляющие: максимальная высота столбца была равна единице. глобальный профиль, локальный профиль и Чтобы оценить аномальность транзакции частотно-временной профиль [18]. Кроме того, рассчитывается следующая величина для каждой существует RFM подход, который позволяет транзакции в контексте оцененного распределения: разносторонне исследовать исторический 1 потребительский профиль клиента с помощью 𝑙𝑙𝑙𝑙𝑙𝑙 ℎ𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖 (𝑡𝑡𝑖𝑖 ) расчёта периодичности, частоты и объёма транзакций в различных разрезах [24]. где 𝑡𝑡𝑖𝑖 – это 𝑖𝑖-ый атрибут транзакции 𝑡𝑡, ℎ𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖 (𝑡𝑡𝑖𝑖 ) – высота столбца гистограммы, в который попало 4.3 Глобальный профиль новое значение. Если пришло значение фактора, которое не встречалось ранее для этого клиента, то Глобальное профилирование необходимо для для него в гистограмме используется частота, того, чтобы определить глобальные группы рассчитанная по его кластеру из глобального клиентов, основанные на характеристиках их профиля. Если это не возможно, то используется транзакций. Это поможет охарактеризовать тех, о частота, оценённая на всей выборке. Таким же ком не достаточно данных в обучающей выборке образом действуем и с клиентами, данных по [18]. Алгоритм профилирования следующий. В которым очень мало. первую очередь, для каждого пользователя рассчитываются: общее количество транзакций, Выбор временного периода для расчёта средняя сумма транзакций, среднее время между эмпирического распределения очень важен [1]. Мы двумя последовательными транзакциями, число остановимся на 2-х временных интервалах: 7 дней – транзакций из других стран, типичное (модальное) для учёта наиболее актуальных потребительских время (часовой интервал) транзакции. Кластеризация трендов и 4 недели – для выявления более производится с помощью итеративной версии долгосрочных потребительских особенностей. DBSCAN с использованием расстояния Обновление частот гистограмм должно Махаланобиса [16]. Итеративная версия осуществляться с периодичностью, не большей чем используется для того, чтобы избежать некоторых минимальное временное окно. В нашем случае – это недостатков алгоритма DBSCAN, возникающих при 7 дней. Идеальный вариант - ежедневно. Обновление применении на несбалансированной выборке с происходит с использованием экспоненциального несколькими большими и множеством маленьких сглаживания. Это позволяет не делать расчёты со кластеров. Количество итераций и начальные старыми данными, снижая нагрузку на значения для алгоритма подбираются эмпирически вычислительную систему, и, в тоже время, позволяет [18]. учесть прошлую информацию о сделках в Обновление кластеров происходит с некоторой распределении факторов: периодичностью, например, раз в месяц. Более ℎ𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖 (𝑡𝑡𝑖𝑖 ) = 𝑎𝑎 ∗ ℎ𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖 (𝑡𝑡𝑖𝑖 )𝑡𝑡 + (1 − 𝑎𝑎) ∗ ℎ𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖 (𝑡𝑡𝑖𝑖 )𝑡𝑡−1 , частое переобучение почти не имеет смысла в виду где параметр 𝑎𝑎 выбирается эмпирически. того, что будет относительное небольшое количество Предлагается строить гистограммы для данных и характеристики клиентов меняются не так следующих атрибутов: номинальные – Merchant быстро. code, Merchant group, Country, Currency, Transaction После того, как выборка разбита на кластеры, нам type; интервальные – Amount, Time. Для необходимо уметь быстро определять номинальных переменных мы просто подсчитываем принадлежность новой заявки к тому или иному частоту появления каждой группы. Для кластеру. Для этих целей можно использовать дерево интервальных – проводится процедура разбиения на решений, которое будет обучено на полученных интервалы. Для Time – оно переводится в часы, кластерах на основе тех же факторов. округляясь в большую сторону если минут больше чем 30 и в меньшую в противоположном случае, 4.2 Локальный профиль например: 21.03.2011 21:31 станет 22. Далее Локальный профиль необходим для того, чтобы считается частота появления каждого часа. Для охарактеризовать индивидуальные поведенческие Amount – разбивается на 10 равномерных интервалов закономерности в транзакциях клиента. Процесс между максимальным и минимальным значением локального профилирования состоит в для клиента за период и подсчитывается число аппроксимации эмпирического распределения попаданий в каждый из интервалов [13]. атрибутов транзакций гистограммой [18]. Выбран 4.3 Частотно-временной профиль именно этот способ ввиду его простоты, наглядности и эффективности. С помощью данного профиля выявляются В процессе работы алгоритма для каждой новой мошеннические транзакции, которые маскируются транзакции используется метод HBOS [13]. С его под не мошеннические. Примером могут служить 259 небольшие по сумме, но очень частые транзакции, обнаружения кластеров в пространстве которые не будут пойманы с помощью локального рассматриваемых признаков, но это приводит к или глобального профилей. другим, возможно более серьёзным проблемам. Без Таким образом, для каждого клиента использования размеченных обучающих примеров, рассчитывается абсолютная сумма транзакций в этот полученные результаты могут быть день, количество транзакций в день и максимальное непредсказуемыми и тяжело трактуемыми. Именно количество транзакций в день за последнее время. поэтому алгоритмы обучения без учителя не Для каждого из этих факторов рассчитывается получили широкого распространения в решении среднее значение и стандартное отклонение за проблемы выявления мошенничества в банковских выбранный период. Аномальной будет считаться та транзакциях. Наилучшим компромиссом в транзакция, которая выходит за интервал: среднее рассматриваемой ситуации будут алгоритмы с значение +/- стандартное отклонение. Для редко частичным обучением, которые находятся расплачивающихся картами клиентов данный посередине между двумя упомянутыми ранее профиль не создаётся. Обновление среднего типами. значения также происходит с помощью экспоненциального сглаживания. Таблица 2 Разрезы для расчёта факторов в рамках RFM 4.4 RFM Время, прошедшее с предыдущей Recency RFM подход основывается на расчёте транзакции периодичности, частоты и объёма транзакций MC для данного вида торговой точки клиента в различных разрезах и за различные MC Category для данной категории торговой периоды времени [24]. В первую очередь определим точки временные периоды. Возьмём такие же, как для Global для всех транзакций клиента построения локального профиля. Теперь Country для всех транзакций в той же стране определимся с разрезами. Наиболее удобным для всех транзакций в той же Currency форматом для представления изучаемых разрезов и валюте Transaction type для всех транзакций того же типа полученных факторов будет таблица, которая Frequency Общее количество транзакций изображена далее. MC для данного вида торговой точки Таким образом, мы видим, что RFM подход является для данной категории торговой аналогом частотно-временного профиля, но более MC Category точки детализированным. Кроме того, в рамках данного Global для всех транзакций клиента подхода выделаются факторы, характеризующие Country для всех транзакций в той же стране первичность транзакции в рассматриваемом для всех транзакций в той же Currency временном интервале. Таким образом, оба подхода валюте могут быть гармонично объединены в один, что Transaction type для всех транзакций того же типа должно повысить ранжирующие способности Monetary Value Средняя сумма транзакции моделей, построенных на извлечённых факторах. MC для данного вида торговой точки для данной категории торговой MC Category 5 Частичное обучение точки Global для всех транзакций клиента Одной из особенностей мошенничества с Country для всех транзакций в той же стране банковскими картами является то, что возможности для всех транзакций в той же Currency банка по разметке обучающих данных сильно валюте ограничены. Лишь небольшая доля сделок попадает Transaction type для всех транзакций того же типа в расследования специалистов противодействия Event Первая покупка? мошенничеству, а клиенты не всегда сообщают о occurrence фактах мошенничества с их картами. Это приводит к MC для данного вида торговой точки тому, что в данных очень мало размеченных для данной категории торговой MC Category транзакций, а те что размечены имеют тенденцию точки быть мошенническими. Всё это снижает Global для всех транзакций клиента Country для всех транзакций в той же стране эффективность методов обучения с учителем. Кроме для всех транзакций в той же того, мошенники часто меняют свои стратегии Currency валюте вывода средств, чтобы оставаться непойманными, Transaction type для всех транзакций того же типа что снижает эффективность методов обучения с учителем ещё сильнее, так как алгоритмы этого типа наиболее чувствительны к тем мошенническим схемам, которые встречаются в выборке для 5.1 Основные принципы обучения наиболее часто. Одним из решений Задача частичного обучения ставится следующим описанных сложностей могло бы стать образом. Есть множество объектов 𝑋𝑋 и множество использование алгоритмов машинного обучения без классов 𝑌𝑌. 𝑋𝑋 𝑙𝑙 = {𝑥𝑥1 , … , 𝑥𝑥𝑙𝑙 },{𝑦𝑦1 , … , 𝑦𝑦𝑙𝑙 } – размеченная учителя, для выявления аномальных транзакций или выборка, 𝑋𝑋 𝑘𝑘 = {𝑥𝑥𝑙𝑙+1 , … , 𝑥𝑥𝑙𝑙+𝑘𝑘 } – неразмеченная 260 выборка. Необходимо построить алгоритм 5.3 DBSCAN классификации a: 𝑋𝑋 → 𝑌𝑌. DBSCAN (Density Based Spatial Clustering of Существует несколько подходов к решению Applications with Noise) [17] – это алгоритм данной задачи. Первый и наиболее простой подход – кластеризации, основанный на плотности и это эвристические методы, такие как self-training и работающий следующим образом: пусть имеются co-learning. Такие подходы требуют многократного точки в некотором пространстве, алгоритм обучения, поэтому вычислительно неэффективны. объединяет вместе точки, находящиеся близко друг к Второй – модификации методов кластеризации. Он другу (которые имеют много близкорасположенных достаточно прост в реализации (необходимо внести соседей), а те точки, что лежат в областях с низкой лишь некоторые ограничения), но, как правило, плотностью (ближайшие соседи расположены трудоёмкий в вычислениях. Наконец, модификации далеко) оставляет в качестве шума. методов классификации. Данный подход реализуется сложнее, но даёт более вычислительно-эффективные Перейдём к модификации данного алгоритма для методы. возможности использования частичного обучения с учётом ограничений, накладываемых предметной 5.2 Применение в области выявления областью. Основные функции: мошенничества с банковскими картами 1. expandCluster (D, Dl, P, NeighborPts, C, eps, MinPts) – функция расширения кластера за Применение методов частичного обучения в счёт соседей, обладающих необходимыми задачах поиска мошеннических транзакций весьма параметрами eps и MinPts. перспективна ввиду причин, перечисленных выше. 2. trueEps (D, Dl, P) – функция рассчитывающая Но, к сожалению, существуют ограничения, которые eps и MinPts для оптимальной кластеризации. должны быть наложены на алгоритмы и в рамках Здесь D – все не размеченные точки, Dl – все частичного обучения. В ситуации, когда мы имеем размеченные точки, P – точка вокруг которой практически один размеченный класс, выбор ищются соседи, NeighborPts – соседи алгоритмов существенно ограничен: модификации рассматриваемой точки с необходимыми алгоритмов классификации будут заведомо хуже или параметрами eps и MinPts. вовсе не применимы, так как для них необходима В данной реализации поиск кластеров выборка хотя бы с двумя размеченными классами. производится вокруг уже известных (размеченных) Прежде чем окончательно определиться с мошеннических наблюдений, что позволяет выявить используемым алгоритмом, необходимо сделать другие потенциально мошеннические транзакции, а предположение о структуре данных. Вероятнее одна точка может принадлежать сразу нескольким всего, что мошеннические операции представляют кластерам. Смысл этих изменений в том, чтобы собой небольшие скопления в пространстве позволить алгоритму разбивать всё пространство на признаков. Это обосновано тем, что мошенники области, каждая из которых характеризуется часто действуют очень схожим образом: некоторой мерой, отражающей шанс того, что в ней отрабатывают определённую работающую схему до содержатся мошеннические транзакции. Причём тех пор, пока её не закроют, либо мошеннические некоторые из областей, вероятно, будут содержать в действия совершает вредоносная программа на себе другие полученные области. Такой подход электронном устройстве клиента, которая действует позволяет более тонко управлять процессом по чёткому алгоритму. В тоже время поведение выявления мошенничества в зависимости от мошенников изменчиво, так как они находятся в соотношения цены ошибки первого и второго рода. постоянном поиске новых лазеек в системах Алгоритм выполняет следующие действия: для противодействия и выявления мошенничества. каждой размеченной точки он находит другую Исходя из представленных выше предположений, ближайшую размеченную точку и строит наилучшим будет тот алгоритм, который умеет гиперсферу, диаметром которой является прямая, выделять небольшие плотные скопления и ему не соединяющая две эти точки (𝑒𝑒𝑒𝑒𝑒𝑒′). С помощью нужно задавать их количество. Одним из возможных гиперсферы мы оцениваем плотность точек в вариантов являются алгоритмы на основе плотности, пространстве между двумя выбранными например, DBSCAN. В данной работе будет (подразумевается, что они принадлежат одному рассмотрена модификация данного алгоритма под кластеру) для того, чтобы подобрать параметры поставленную задачу частичного обучения с одним DBSCAN, максимально отражающие структуру размеченным классом. данных кластера. Параметру алгоритма eps Стоит отметить, что на текущий момент присваивается значение равное радиусу сферы, существуют реализации алгоритма DBSCAN с умноженное на долю объёма гиперсферы, не частичным обучением, например [14], но они не заполненную точками: пригодны для применения в рамках описанной ранее 0.5 ∗ 𝑒𝑒𝑒𝑒𝑠𝑠 ′ ∗ (1 − (𝑉𝑉 𝑜𝑜𝑜𝑜 𝑛𝑛−𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐)∗𝑙𝑙𝑙𝑙𝑙𝑙�𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑�𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠(𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡ℎ𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏)�� ) предметной области, где преобладают наблюдения с (𝑉𝑉 𝑜𝑜𝑜𝑜 𝑛𝑛−𝑠𝑠𝑠𝑠ℎ𝑒𝑒𝑒𝑒𝑒𝑒) одним размеченным классом. 261 Рассмотрим выражение: 5.4 Отбор факторов (𝑉𝑉 𝑜𝑜𝑜𝑜 𝑛𝑛−𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐)∗𝑙𝑙𝑙𝑙𝑙𝑙�𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑�𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠(𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡ℎ𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏)�� , Одним из важнейших этапов в процессе (𝑉𝑉 𝑜𝑜𝑜𝑜 𝑛𝑛−𝑠𝑠𝑠𝑠ℎ𝑒𝑒𝑒𝑒𝑒𝑒) кластеризации является отбор факторов. Включение где trueNeighbors – это число точек внутри незначимых или сильно коррелирующих факторов гиперсферы, (𝑉𝑉 𝑜𝑜𝑜𝑜 𝑛𝑛 − 𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐) – объём гиперкуба, может привести к тому, что адекватные кластеры не построенного вокруг точки, будут найдены. Существует два очевидных подхода 𝑙𝑙𝑒𝑒𝑒𝑒 �𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑𝑑�𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠(𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡𝑡ℎ𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏)�� – число по отбору факторов для кластеризации: уникальных точек, приведённых к необходимой использование априорных соображений и анализ шкале, (𝑉𝑉 𝑜𝑜𝑜𝑜 𝑛𝑛 − 𝑠𝑠𝑠𝑠ℎ𝑒𝑒𝑒𝑒𝑒𝑒) – объём гиперсферы. важности факторов на специально подготовленной Фактически, это отношение выражает долю объёма размеченной выборке. В нашем случае априорные гиперсферы, заполненную точками. Процесс соображения учтены полностью ввиду специфики шкалирования – это преобразование коррдинат точек подготовки факторов (подробнее об этом в секции 4). к такому виду, чтобы можно было заполнить Что касается анализа на размеченной выборке, то гиперсферу неперсекающимися гиперкубами этот способ кажется очень удобным в рамках определённого размера, построенными вокруг точек. поставленной задачи. Таким образом для отбора Например, заполним гиперсферу гиперкубами со факторов предлагается использовать деревья стороной 𝑘𝑘 = 𝑒𝑒𝑒𝑒𝑠𝑠 ′ /100, тогда, если мы преобразуем решений. Это связано с необходимостью учитывать каждую координату как 𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟(𝑥𝑥𝑖𝑖 /𝑘𝑘, 0) ∗ 𝑘𝑘, то возможную нелинейность факторов относительно сможем заполнить всё пространство внутри мошенничества, а деревья решений являются гиперсферы не персекающимися гиперкубами со наиболее простым и понятным подходом для стороной 𝑘𝑘. Таким образом, каждую уникальную решения таких задач. Один из возможных вариантов точку (некоторые из них могли сойтись в одну из-за реализации подхода к отбору факторов на основе округления) мы заменяем гиперкубом и складываем деревьев решений заключается в следующем: для их площади, получая оценку площади, занятой каждого фактора строится своё дерево решений, точками. Поделив это на объём гиперсферы, которое предсказывает известные факты который можно приближённо вычислить (для n>3) мошенничества против всего остального. 1 2𝜋𝜋𝜋𝜋 0.5∗𝑛𝑛 Предварительно отбираем обучающую выборку по формуле: 𝑉𝑉𝑛𝑛 (𝑅𝑅) ~ ∗� � ∗ 𝑅𝑅𝑛𝑛 , и вычитая следующим образом: берём все размеченные данные, √𝜋𝜋∗𝑛𝑛 𝑛𝑛 из единицы, получаем долю объёма сферы, не а потом дополняем их неразмеченными так, чтобы заполненную точками. Умножая это на 𝑒𝑒𝑒𝑒𝑒𝑒′ соотношение мошеннических транзакций к получаем величину 𝑒𝑒𝑒𝑒𝑒𝑒, которая тем больше, чем остальным было 1:1. Дальнейший алгоритм построен меньше заполнена гиперсфера. Этот же коэффициент следующим образом: фактор разбивается на 40 применяем для определения оптимального MinPts: равномерных интервалов (для интервальных чем меньше заполнена сфера, тем меньше надо факторов), каждому интервалу присваивается номер, соседних точек для включения в кластер. Далее и на этих номерах строится дерево решений, которое алгоритм, используя полученные параметры MinPts и в итоге должно выдать не более чем 7 итоговых eps, находит соседей двух рассматриваемых точек, интервалов. Для номинальных переменных в дереве объдиняет их и действует по схеме функции используются их фактические значения. Разбиение expandCluster. на 40 интервалов необходимо для того, чтобы обезопаситься от переобучения и получения очень Таким образом, мы получили алгоритм, маленьких итоговых интервалов. Для номинальных принимающий на вход две выборки (размеченные и (категориальных) переменных также используется не размеченные) и подбирающий все необходимые дерево решений, но без предварительного разбиения параметры для выявления кластеров автоматически. на интервалы. После этого рассчитывается Это позволяет исключить практически все коэффициент Gini для каждой переменной, общеизвестные недостатки оригинального отражающий способность фактора к ранжированию. алгоритма DBSCAN: нет проблемы с граничными Порог отсечения по Gini для факторов подбирается точками, так как фактически есть только один тип эмпирически. Полученный список значимых для кластера; значения параметров MinPts и eps факторов проверяем на корреляцию и исключаем подбираются автоматически; нет проблемы с один из тех, по кому корреляция составила более различной плотностью кластеров, так как параметры 70%. Предпочтение отдаётся фактору, имеющему подбираются индивидуально для каждого больший Gini. Таким образом, получаем финальный потенциального кластера. К сожалению, все эти список факторов для кластеризации. изменения делают алгоритм более трудоёмким с точки зрения вычислений. Для того, чтобы облегчить вычисления, можно ограничивать возможные 5.5 Обработка результатов значения eps, так как в расмотрении очень больших областей смысла нет. Кроме того, есть потенциал в В результате применения описанного алгоритма, распараллеливании данного алгоритма и применении на выходе получаем набор кластеров, каждый из технологий Apache Spark [20]. 262 которых характеризуется некоторой мерой, находящиеся внутри кластера также являются отражающей шанс того, в нём содержатся мошенническими (данное предположение не мошеннические транзакции, например, плотность использовалось для бучения, а только для расчёта кластера: отношение количества элементов в качества). В результате оценивалось то, насколько кластере к оценке объёма кластера. Кроме того, точно и полно выделенные кластеры соответствуют можно учитывать расстояние от точки до центра реальным мошенническим кластерам. кластера, корректируя вероятность быть Для того чтобы оценить качество разработанного мошеннической для конкретной точки внутри алгоритма, результаты его работы были сравнены с кластера. результатами алгоритма HDBSCAN [7]. Его Теперь мы можем каждой новой транзакции основные преимущества в том, что он применяет поставить в соответствие выбранную меру, чтобы алгоритм DBSCAN к данным, используя различные определить её шансы быть мошеннической значения параметра eps, подбирая лучшую (предварительно отнеся её к одному из кластеров). кластеризацию, на основе стабильности данного Далее, в зависимости от политики банка, параметра. Для работы алгоритм требует только применяются различные меры по борьбе с один параметр – минимальный размер кластера. мошенничеством. После применения алгоритма HDBSCAN так же оценивалось то, насколько точно и полно 6 Результаты эксперимента выделенные кластеры соответствуют реальным кластерам. Единственным исключением было то, что Результаты работы алгоритма были оценены на кластеры, которые не содержали изначально 10 симуляционных двумерных выборках. Двумерная размеченные данные, исключались из анализа для выборка была выбрана в виду наибольшей повышения точности. наглядности результатов. Выборки были В результате была получена оценка среднего сформированы следующим образом. Вокруг трёх индекса Джини для алгоритма с частичным последовательно расположенных опорных точек обучением: 85%, и для алгоритма HDBSCAN: 71,7%. были сформированы кластеры различной плотности. Таким образом, мы видим, что предложенный Кластеры формировались таким образом, чтобы подход оказывается в среднем лучше на 13 точки внутри каждого кластера были распределены процентных пунктов. нормально по обеим координатам со средним значением равным соответствующей координате Заключение опорной точки. По такому же принципу в каждый из кластеров в небольшом количестве, В данной статье произведён обзор подходов к пропорциональном его размеру, были добавлены агрегации данных и извлечению факторов в задаче размеченные (мошеннические) точки. После этого, поиска мошенничества с банковскими картами. равномерно по всему рассматриваемому Кроме того, обсуждалась предобработка данных с пространству были добавлены точки шума, а также использованием деревьев решений и отбор факторов размеченные точки, не попадающие в кластеры. для оптимальной кластеризации, а также Пример на рисунке ниже. Укрупнённые точки – это представлен новый алгоритм, являющийся размеченные (мошеннические) точки. модификацией DBSCAN для применения в задаче частичного обучения. Как показали эксперименты на симуляционных данных, данный алгоритм получает устойчивые положительные результаты на различных выборках без подбора параметров, необходимых классическому DBSCAN, кроме того, алгоритм показал себя лучше, чем алгоритм HDBSCAN. В следующих работах будет произведено тестирование всех описанных подходов на реальных данных банковских транзакций. Литература [1] Alejandro Correa Bahnsen, Djamila Aouada, Рисунок 1 Пример симуляционной выборки Aleksandar Stojanovic, Björn Ottersten. Feature engineering strategies for credit card fraud detection. Expert Systems With Applications 51 pp. 134–142, В рамках рассматриваемой задачи данный алгоритм 2016. будет применяться для классификации транзакций, [2] Aleskerov, E., Freisleben, B., Rao, B. Cardwatch: A поэтому в качестве метрики качества было решено neural network based database mining system for использовать индекс Джини. Чтобы рассчитать credit card fraud detection. In: Computational данный индекс, предполагалось, что точки, Intelligence for Financial Engineering (CIFEr), 263 1997., Proceedings of the IEEE/IAFE 1997. IEEE, [16] Mahalanobis, Prasanta Chandra. On the generalised p. 220–226, 1997. distance in statistics. Proceedings of the National [3] Bhattacharyya, S., Jha, S., Tharakunnel, K., Institute of Sciences of India 2 (1). p. 49–55, 1936. Westland, J. C. Data mining for credit card fraud: A [17] Martin Ester, Hans-Peter Kriegel, Jiirg Sander, comparative study. Decision Support Systems 50 Xiaowei Xu. A density-based algorithm for (3), p. 602–613, 2011. discovering clusters in large spatial databases with [4] Bolton, R. J., & Hand, D. J. Statistical fraud noise. Proceedings of the Second International detection: A review. Statistical Science, 17(3), p. Conference on Knowledge Discovery and Data Mining (KDD-96). AAAI Press. p. 226–231, 1996. 235–249, 2002. [18] Michele Carminati, Roberto Caron, Federico Maggi, [5] Bolton, R. J., & Hand, D. J. Unsupervised profiling Ilenia Epifani, Stefano Zanero. BankSealer: An methods for fraud detection. In Conference on credit Online Banking Fraud Analysis and Decision scoring and credit control, Edinburgh, 2001. Support System. ICT Systems Security and Privacy [6] Brause, R., Langsdorf, T., Hepp, M. Neural data Protection, Volume 428 of the series IFIP Advances mining for credit card fraud detection. In: in Information and Communication Technology, p. Proceedings. 11th IEEE International Conference on 380-394, 2014. Tools with Artificial Intelligence. IEEE, p. 103–106, [19] S´anchez, D., Vila, M., Cerda, L., Serrano, J.-M. 1999. Association rules applied to credit card fraud [7] Campello R., Moulavi D., and Sander J. Density- detection. Expert Systems with Applications 36 (2), Based Clustering Based on Hierarchical Density p. 3630–3640, 2009. Estimates. In Advances in Knowledge Discovery [20] Sandy Ryza, Uri Laserson, Sean Owen, Josh Wills. and Data Mining, Springer. P. 160-172, 2013. Advanced Analytics with Spark, Patterns for [8] Dal Pozzolo, A., Caelen, O., Le Borgne, Y.-A., Learning from Data at Scale. O'Reilly, Pages: 276, Waterschoot, S., Bontempi, G. Learned lessons in 2015. credit card fraud detection from a practitioner [21] Shen, A., Tong, R., Deng, Y. Application of perspective. Expert Systems with Applications 41 classification models on credit card fraud detection. (10), p. 4915–4928, 2014. In: Service Systems and Service Management, 2007 [9] Dorronsoro, J. R., Ginel, F., Sgnchez, C., Cruz, C. International Conference on. IEEE, p. 1–4, 2007. Neural fraud detection in credit card operations. [22] Srivastava, A., Kundu, A., Sural, S., Majumdar, A. Neural Networks, IEEE Transactions on 8 (4), p. K. Credit card fraud detection using hidden markov 827–834, 1997. model. Dependable and Secure Computing, IEEE [10] Duman, E., Elikucuk, I. Solving credit card fraud Transactions on 5 (1), p. 37–48, 2008. detection problem by the new metaheuristics [23] Syeda, M., Zhang, Y.-Q., Pan, Y. Parallel granular migrating birds optimization. In: Rojas, I., Joya, G., neural networks for fast credit card fraud detection. Cabestany, J. (Eds.), Advances in Computational In: Proceedings of the 2002 IEEE International Intelligence. Vol. 7903 of Lecture Notes in Conference on Fuzzy Systems. Vol. 1. IEEE, p. 572– Computer Science. Springer Berlin Heidelberg, p. 577, 2002. 62–71, 2013.. [24] Veronique Van Vlasselaer, Cristian Bravo, Olivier [11] FICO. Evolution of card fraud in Europe. Russia Caelen, Tina Eliassi-Rad, Leman Akoglu, Monique http://www.fico.com/landing/fraudeurope2013/cou Snoeck, Bart Baesens, APATE: A Novel Approach ntry.php?countrycode=RUS for Automated Credit Card Transaction Fraud [12] Ghosh, S., Reilly, D. L. Credit card fraud detection Detection using Network-Based Extensions, with a neural-network. In: Proceedings of the Decision Support Systems, 2015. Twenty-Seventh International Conference on [25] Wheeler, R., Aitken, S. Multiple algorithms for System Sciences. Vol. 3. IEEE, p. 621–630, 1994. fraud detection. Knowledge-Based Systems 13 (2), p. 93–99, 2000. [13] Goldstein, M., Dengel, A. Histogram-Based Outlier Score (HBOS): A Fast Unsupervised Anomaly [26] Whitrow, C., Hand, D. J., Juszczak, P., Weston, D., Detection Algorithm, 2012. Adams, N. M. Transaction aggregation as a strategy for credit card fraud detection. Data Mining and [14] Levi Lelis, Jörg Sander. Semi-Supervised Density- Knowledge Discovery 18 (1), p. 30–55, 2009. Based Clustering. ICDM '09 Proceedings of the 2009 Ninth IEEE International Conference on Data Mining. p. 842-847. 2009 Data aggregation and feature extraction [15] Maes, S., Tuyls, K., Vanschoenwinkel, B., Manderick, B. Credit card fraud detection using strategies for credit card fraud detection Bayesian and neural networks. In: Proceedings of Oleg Travkin the 1st international naiso congress on neuro fuzzy This paper provides an overview of approaches to data technologies, 2002. aggregation and feature extraction strategies for credit 264 card fraud detection. In order to identify credit card transactions that are based on its frequency for a certain fraud, it is very important to analyze historical spending period of time. The second approach is called RFM behavior of customers. This paper discusses two (Recency-Frequency-Monetary). Within this approach approaches. The first approach is based on global, local the recency, the frequency and monetary volume of and temporal customer profiles. Global profile is built via customer transactions are calculated for a certain period clustering customers based on characteristics of of time. In addition, we proposed semi-supervised transactions, that allows analyze new or inactive modification of DBSCAN algorithm, which may allow customers more accurate. Local profile is based on to significantly improve the accuracy of modeling of historical consumer behavior of each client. Temporal fraud based on identified profiles and RFM profile is based on analyzing patterns in customer characteristics. 265