учитывая 10 функций y = a + bx и 1000 (x, y) точек данных, округленных до целых, как получить 10 лучших (a, b) кортежей?

Question

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

fee = fixed + variable*transaction_price

«Схема оплаты» - это пара (fixed, variable), используемая группой кредитных карт, например, «MasterCard Business дебетовые золотые карты, выпущенные Первым Национальным банком Голливуда». Мы считаем, что в любое время используется менее 10 различных схем оплаты, но мы не получаем полный или текущий список схем оплаты от наших партнеров. (да, я знаю, что некоторые «схемы оплаты» сложнее, чем приведенное выше уравнение, из-за ограничений и других ошибок, но известно, что в наших транзакциях используется только a + bx схем).

Вот проблема, которую мы пытаемся решить: мы хотим использовать данные о сборах для каждой транзакции для определения используемых схем оплаты. Затем мы можем сравнить этот список с схемами оплаты, которые каждый клиент должен использовать в зависимости от своего банка.

Данные, которые мы получаем о каждой транзакции, являются кортежем данных: (card_id, transaction_price, fee).

transaction_price и fee в целых центах. Банк переворачивает дробные центы за каждый переход до тех пор, пока кумулятивный доход не станет больше одного цента, а затем к суммам этой транзакции будет добавлен «округлый цент» Мы не можем предсказать, к какой транзакции будет прикреплен «цент округления».

card_id идентифицирует группу карт с одинаковой схемой оплаты. В обычный день из 10 000 транзакций может быть несколько сотен уникальных card_id. Несколько card_id разделят схему оплаты.

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

card_id    transaction_price       fee        fixed        variable
=======================================================================
12345      200                     22         ?            ?
67890      300                     21         ?            ?
56789      150                      8         ?            ?
34567      150                      8         ?            ?
34567      150    "rounding cent"-> 9         ?            ?
34567      150                      8         ?            ?

Конечным результатом, который мы хотим, является такой короткий список с 10 или менее записями, показывающими схемы оплаты, которые лучше всего соответствуют нашим данным. Как это:

fee_scheme_id       fixed     variable
======================================
1                      22            0
2                      21            0
3                       ?            ?
4                       ?            ?
...

Средняя плата составляет около 8 центов. Это означает, что центы округления оказывают огромное влияние, а приведенный выше вывод требует много данных.

Средняя транзакция составляет 125 центов. Цены сделок всегда находятся в пределах 5 центов.

Мы хотим получить краткий список схем оплаты, которые «соответствуют» 98% + 3000 транзакций, которые каждый клиент получает каждый день. Если данных недостаточно для достижения достоверности 98%, мы можем использовать данные за несколько дней.

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

Есть предложения, как подойти к этой проблеме? Реализация может быть на C # или T-SQL, в зависимости от того, какой алгоритм имеет смысл.

Answer 1

Преобразование Хафа

Рассмотрите вашу проблему с точки зрения изображения: если вы разместите свои входные данные на графике цена / плата, записи каждой схемы будут образовывать прямую линию (с шумом округления центов). Рассмотрите карту плотности вашего графика как изображение, и задача сводится к поиску прямых линий на изображении. Это просто работа преобразования Хафа .

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

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

Answer 2

Учитывая, что требования к хранилищу для обрабатывающего запроса равны 2 с дневной стоимостью данных транзакций, я предполагаю, что такое хранилище не является проблемой, поэтому:

• Первый проход: сгруппируйте транзакции для каждого идентификатора карты по транзакции, сохраняя идентификатор карты, транзакцию и среднюю комиссию.Это легко сделать в SQL.Это предполагает, что нет выбросов - но вы можете поймать их на этом этапе, если это потребуется.Результирующее количество строк гарантированно не будет больше числа необработанных точек данных.

• Второй проход: для каждой группы обходятся эти новые точки данных (с курсором или в C #) ирассчитать среднее значение б.Снова любые выбросы могут быть обнаружены при желании после этой стадии.

• Третий проход: для каждой группы вычисляют среднее значение a, теперь, когда b известно.Это базовый SQL.Выбросы как всегда

Если вы решите сделать второй шаг в курсоре, вы можете вставить все это в хранимую процедуру.

Различные группы card_id, которые используют одинаковыеСхема сборов теперь может объединяться (извините, это неправильное слово, не являющееся английским) в схемы сборов, округляя a и b с разумной точностью и снова группируя.

Answer 3

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

Увы, наивная версия известна как медленная , если у вас много входных данных (1000 точек среднего размера) и если вы хотите получить результаты с высокой точностью (масштабируется как size_of_the_input / (rho_precision * theta_precision)).

Существует более быстрый подход на , основанный на 2 ^ n-деревьях , но в Интернете существует несколько реализаций, чтобы просто подключить его. (Недавно я сделал одну на C ++в качестве испытательного стенда для проекта, в котором я участвую. Может быть, я его почистю и где-нибудь опубликую.)

---

Если есть какой-то дополнительный порядок для данных, вы можете сделать лучше(т.е. образуют ли отрезки отрезков кусочную функцию?).

---

Наивное преобразование Хафа

Определение аккумулятора в (тета, ро) пространстве, охватывающем [-pi, pi) и [0, max (гипотенуза (x, y)] как двумерный массив.

Foreach point in the input data
   Foreach bin in theta
      find the distance rho of the altitude from the origin to 
      a line through (a,y) and making angle theta with the horizontal
      rho = x cos(theta) + y sin(theta)
      and increment the bin (theta,rho) in the accumulator
Find the maximum bin in the accumulator, this 
represents the most line-like structure in the data
if (theta !=0) {a = rho/sin(theta); b = -1/tan(theta);}

Надежное получение нескольких строк за один проход требует немного больше бухгалтерии, но это не намного сложнее.

Вы можете немного улучшить результат, сгладив данные возле пиков-кандидатов и подгоняя их для полученияточность суб-бина, которая должна быть быстрее, чем использование меньших бинов, и должна плавно улавливать эффект «округления» центов.

Answer 4

Вы рассматриваете округление цента как значительный источник шума в своих вычислениях, поэтому я бы сосредоточился на минимизации шума из-за этой проблемы.Самый простой способ сделать это IMO - увеличить размер выборки.

Вместо просмотра ваших данных, когда тысячи y = mx + b (+ округление) группируют ваши данные в большие подмножества:

Если вы объедините X транзакций с одним и тем же и посмотрите на это как (сумма X сборов) = (переменная ставка) * (сумма X транзакций) + X (базовые ставки) (+ округление) вашего числа округления, шум, скорее всего, снизится дона обочине.

Получите достаточно групп размера 'X', и вы сможете составить довольно точное представление о реальных числах.