Двухэтапный метод поиска нечётких дубликатов с использованием элементов теории графов

В данной работе рассматривалась проблема поиска нечётких дубликатов среди пользователей интернет-сервиса. Было предложено решение этой проблемы с использованием двухэтапного метода: поиск кандидатов в дубликаты и скоринг найденных кандидатов. Первый этап —— поиск кандидатов —— происходит с использованием такой структуры, как прямой и обратный индексы (direct and inverted indexes). На втором этапе из найденных пользователей строится граф, описывающий связи между ними. Вершинами графа являются пользователи, а ребрами —— признаки, по которым оно были найдены в индексной структуре. В дальнейшем задача сводится к задаче бинарной классификации на классы фрод/не-фрод пар "опорный пользователь"-"кандидат". В качестве признаков используются как контентные признаки пользователей, так и графовые признаки. Графовые признаки, используемые в работе, можно разбить на два вида: признаки, относящиеся к графу целиком, и признаки, относящиеся к конкретной паре пользователей. В рамках экспериментальной части работы были опробованы различные алгоритмы машинного обучения, предназначенные для классификации, а также проведена оценка качества и скорости их работы. Основными преимуществами предложенного метода является возможность его использования в онлайн-режиме, потоковое обогащение данных, а также его относительная интерпретируемость, благодаря способу получения кандидатов. Ключевые слова: МАШИННОЕ ОБУЧЕНИЕ, КЛАССИФИКАЦИЯ, ПОИСК НЕЧЁТКИХ ДУБЛИКАТОВ, ТЕОРИЯ ГРАФОВ.