Нахождение наиболее выгодных перестановок длинных / коротких пар в Python - проблема оптимизации? - PullRequest
Новая
       10

Нахождение наиболее выгодных перестановок длинных / коротких пар в Python - проблема оптимизации?

1 голос
/ 23 января 2020

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

Я могу сделать это sh, просматривая все перестановки, но это очень медленно. (нет ничего удивительного) Я думаю это может быть тип проблемы, подходящей для линейной оптимизации с такой библиотекой, как PuLP.

Вот пример полного решения проблемы. Я намеренно сохраняю данные простыми, но у меня есть 1000 активов, которые мне нужно найти. До финиша sh потребовалось около 45 минут с неэффективным, ручным подходом, который я обрисовал в общих чертах ниже.

Примечание: потому что длинная «Альфа» и короткая «Браво» отличаются от длинных «Браво» и коротко "Альфа", я использую перестановки, а не комбинации.

Редактировать: в случае, если некоторые не знакомы с longing и shorting Я пытаюсь соединить наивысшую прибыль с наименьшей прибылью (с short , я получаю больше прибыли, чем более отрицательное значение)

Логика c будет читать что-то например:

Для всех перестановок узлов добавьте прибыль в один узел к обратной прибыли в два узла, чтобы получить общую прибыль. Найдите пару с самой высокой общей прибылью.

Вот моя очень неэффективная (но работающая) реализация: 

# Sample data
profits = [
    ('2019-11-18', 'Alpha', -79.629698),
    ('2019-11-19', 'Alpha', -17.452517),
    ('2019-11-20', 'Alpha', -19.069558),
    ('2019-11-21', 'Alpha', -66.061564),
    ('2019-11-18', 'Bravo', -87.698670),
    ('2019-11-19', 'Bravo', -73.812616),
    ('2019-11-20', 'Bravo', 198.513246),
    ('2019-11-21', 'Bravo', -69.579466),
    ('2019-11-18', 'Charlie', 66.302287),
    ('2019-11-19', 'Charlie', -16.132065),
    ('2019-11-20', 'Charlie', -123.735898),
    ('2019-11-21', 'Charlie', -30.046416),
    ('2019-11-18', 'Delta', -131.682322),
    ('2019-11-19', 'Delta', 13.296473),
    ('2019-11-20', 'Delta', 23.595053),
    ('2019-11-21', 'Delta', 14.103027),
]

profits_df = pd.DataFrame(profits, columns=('Date','Node','Profit')).sort_values('Date')

profits_df выглядит так: 

+----+------------+---------+-------------+
|    |    Date    |  Node   |   Profit    |
+----+------------+---------+-------------+
|  0 | 2019-11-18 | Alpha   | -79.629698  |
|  4 | 2019-11-18 | Bravo   | -87.698670  |
|  8 | 2019-11-18 | Charlie | 66.302287   |
| 12 | 2019-11-18 | Delta   | -131.682322 |
|  1 | 2019-11-19 | Alpha   | -17.452517  |
+----+------------+---------+-------------+

Чтобы решить проблему вручную, я могу сделать это: 

date_dfs = []

# I needed a way to take my rows and combine them pairwise, this
# is kind of gross but it does work

for date, date_df in profits_df.groupby('Date'):
    tuples = [tuple(x) for x in date_df[['Node', 'Profit']].to_numpy()]
    pp = list(itertools.permutations(tuples, 2))
    flat_pp = [[p[0][0], p[0][1], p[1][0], p[1][1]] for p in pp]
    df = pd.DataFrame(flat_cc, columns=['Long', 'LP', 'Short', 'SP'])
    date_dfs.append(df)

result_df = pd.concat(daily_dfs)
result_df['Pair'] = result_df['Long'] + '/' + result_df['Short']
result_df['Profit'] = result_df['LP'] + result_df['SP'].multiply(-1)

result_df.groupby('Pair')['Profit'].sum().sort_values(ascending=False)

Вычисляя прибыль для всех перестановок каждый день, а затем суммируя их, я получаю следующий результат: 

+-----------------------------+
|            Pair             |
+-----------------------------+
| Bravo/Alpha      149.635831 |
| Delta/Alpha      101.525568 |
| Charlie/Alpha     78.601245 |
| Bravo/Charlie     71.034586 |
| Bravo/Delta       48.110263 |
| Delta/Charlie     22.924323 |
| Charlie/Delta    -22.924323 |
| Delta/Bravo      -48.110263 |
| Charlie/Bravo    -71.034586 |
| Alpha/Charlie    -78.601245 |
| Alpha/Delta     -101.525568 |
| Alpha/Bravo     -149.635831 |
+-----------------------------+

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

Может кто-нибудь предложить подход, который я должен попробовать?

Ответы [ 2 ]

2 голосов
/ 23 января 2020

Краткое описание того, что я сделал:

  1. создать словарь из списка прибыли
  2. запустить перестановки для каждого ключа, пара значений
  3. перебрать каждую пару чтобы получить комбинацию имен и сумм по отдельности.
  4. Сортировка списка контейнеров по имени, по группам по имени, суммирование сумм по каждой группе и загрузка окончательного результата в словарь.
  5. Чтение словарь в массив данных и сортировку значений по прибыли в порядке убывания.

Я считаю, что вся обработка должна быть выполнена до того, как она попадет в кадр данных, и вы должны значительно ускориться: 

from collections import defaultdict
from operator import itemgetter
from itertools import permutations, groupby

d = defaultdict(list)
for k, v,s in profits:
    d[k].append((v,s))

container = []
for k,v in d.items():
    l = (permutations(v,2))
#here I combine the names and the amounts separately into A and B
    for i,j in l:
        A = i[0]+'_'+j[0]
        B = i[-1]+(j[-1]*-1)
        container.append([A,B])

#here I sort the list, then groupby (groupby wont work if you don't sort first)
container = sorted(container, key=itemgetter(0,1))

sam = dict()
for name, amount in groupby(container,key=itemgetter(0)):
    sam[name] = sum(i[-1] for i in amount)

outcome = pd.DataFrame
          .from_dict(sam,
                     orient='index',
                     columns=['Profit'])
          .sort_values(by='Profit',
                       ascending=False)

             Profit
Bravo_Alpha 149.635831
Delta_Alpha 101.525568
Charlie_Alpha   78.601245
Bravo_Charlie   71.034586
Bravo_Delta 48.110263
Delta_Charlie   22.924323
Charlie_Delta   -22.924323
Delta_Bravo -48.110263
Charlie_Bravo   -71.034586
Alpha_Charlie   -78.601245
Alpha_Delta -101.525568
Alpha_Bravo -149.635831

когда я запускал его на своем P C, он составлял 1,24 мс, в то время как урс приходил на 14,1 мс. Надеюсь, кто-то может произвести что-то намного быстрее.

ОБНОВЛЕНИЕ:

Все, что я делал для первого, было излишним. Нет необходимости в перестановке - множитель равен -1. Это означает, что все, что нам нужно сделать, это получить сумму для каждого имени, объединить имена (без повторов), умножить одно из значений на -1 и добавить к другому, а затем, когда у нас будет единовременная сумма для пары, умножить на - 1 снова, чтобы получить обратное. Я получил скорость около 18,6 мкс, которая снимает до 273 мкс при введении pandas. Это значительное ускорение. Большая часть вычислений считывала данные в pandas. Вот так: 

from collections import defaultdict
from operator import itemgetter
from itertools import combinations, chain
import pandas as pd

def optimizer(profits):

    nw = defaultdict(list)
    content = dict()

    [nw[node].append((profit)) for dat,node,profit in profits]

    #sum the total for each key
    B = {key : sum(value) for key ,value in nw.items()}

    #multiply the value of the second item in the tuple by -1
    #add that to the value of the first item in the tuple
    #pair the result back to the tuple and form a dict
    sumr = {(first,last):sum((B[first],B[last]*-1))
                              for first,last 
                              in combinations(B.keys(),2)}

    #reverse the positions in the tuple for each key
    #multiply the value by -1 and pair to form a dict
    rev = {tuple(reversed(k)): v*-1 
           for k,v in sumr.items()}

    #join the two dictionaries into one
    #sort in descending order
    #and create a dictionary
    result = dict(sorted(chain(sumr.items(),
                               rev.items()
                               ),
                  key = itemgetter(-1),
                  reverse=True
                  ))

    #load into pandas
    #trying to reduce the compute time here by reducing pandas workload
    return pd.DataFrame(list(result.values()),
                        index = list(result.keys()),
                        )

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

1 голос
/ 25 января 2020

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

Из тестирования это построение и объединение DataFrames, которые медленная часть. Использовать Numpy довольно просто для создания матрицы цен пары: 

arr = df['profit'].values + df['profit'].multiply(-1).values[:, None]

Производит эту матрицу каждого узла, умноженную на каждый узел: 

+---+-------------+------------+------------+------------+
|   | 0           | 1          | 2          | 3          |
+---+-------------+------------+------------+------------+
| 0 | 0.000000    | 149.635831 | 78.598163  | 101.525670 |
+---+-------------+------------+------------+------------+
| 1 | -149.635831 | 0.000000   | -71.037668 | -48.110161 |
+---+-------------+------------+------------+------------+
| 2 | -78.598163  | 71.037668  | 0.000000   | 22.927507  |
+---+-------------+------------+------------+------------+
| 3 | -101.525670 | 48.110161  | -22.927507 | 0.000000   |
+---+-------------+------------+------------+------------+

Если вы создаете пустой numpy массив с размерами number of nodes * number of nodes, тогда вы можете просто добавить суточный массив в массив итогов: 

total_arr = np.zeros((4, 4))

# Do this for each day
arr = df['profit'].values + df['profit'].multiply(-1).values[:, None]

total_arr += arr

Как только вы это сделаете, вам нужно будет сделать Pandas voodoo назначает имена узлов матрице и разбивает матрицу на отдельные длинные / короткие / прибыльные строки.

Мой оригинальный (исчерпывающий) поиск занял 47 минут с данными за 60 дней. Сейчас до 13 секунд.

Полный рабочий пример: 

profits = [
    {'date':'2019-11-18', 'node':'A', 'profit': -79.629698},
    {'date':'2019-11-19', 'node':'A', 'profit': -17.452517},
    {'date':'2019-11-20', 'node':'A', 'profit': -19.069558},
    {'date':'2019-11-21', 'node':'A', 'profit': -66.061564},
    {'date':'2019-11-18', 'node':'B', 'profit': -87.698670},
    {'date':'2019-11-19', 'node':'B', 'profit': -73.812616},
    {'date':'2019-11-20', 'node':'B', 'profit': 198.513246},
    {'date':'2019-11-21', 'node':'B', 'profit': -69.579466},
    {'date':'2019-11-18', 'node':'C', 'profit': 66.3022870},
    {'date':'2019-11-19', 'node':'C', 'profit': -16.132065},
    {'date':'2019-11-20', 'node':'C', 'profit': -123.73898},
    {'date':'2019-11-21', 'node':'C', 'profit': -30.046416},
    {'date':'2019-11-18', 'node':'D', 'profit': -131.68222},
    {'date':'2019-11-19', 'node':'D', 'profit': 13.2964730},
    {'date':'2019-11-20', 'node':'D', 'profit': 23.5950530},
    {'date':'2019-11-21', 'node':'D', 'profit': 14.1030270},
]

# Initialize a Numpy array of node_length * node_length dimension
profits_df = pd.DataFrame(profits)
nodes = profits_df['node'].unique()
total_arr = np.zeros((len(nodes), len(nodes)))

# For each date, calculate the pairs profit matrix and add it to the total
for date, date_df in profits_df.groupby('date'):
    df = date_df[['node', 'profit']].reset_index()
    arr = df['profit'].values + df['profit'].multiply(-1).values[:, None]
    total_arr += arr

# This will label each column and row
nodes_series = pd.Series(nodes, name='node')
perms_df = pd.concat((nodes_series, pd.DataFrame(total_arr, columns=nodes_series)), axis=1)

# This collapses our matrix back to long, short, and profit rows with the proper column names
perms_df = perms_df.set_index('node').unstack().to_frame(name='profit').reset_index()
perms_df = perms_df.rename(columns={'level_0': 'long', 'node': 'short'})

# Get rid of long/short pairs where the nodes are the same (not technically necessary)
perms_df = perms_df[perms_df['long'] != perms_df['short']]

# Let's see our profit
perms_df.sort_values('profit', ascending=False)

Результат: 

+----+------+-------+-------------+
|    | long | short | profit      |
+----+------+-------+-------------+
| 4  | B    | A     | 149.635831  |
+----+------+-------+-------------+
| 12 | D    | A     | 101.525670  |
+----+------+-------+-------------+
| 8  | C    | A     | 78.598163   |
+----+------+-------+-------------+
| 6  | B    | C     | 71.037668   |
+----+------+-------+-------------+
| 7  | B    | D     | 48.110161   |
+----+------+-------+-------------+
| 14 | D    | C     | 22.927507   |
+----+------+-------+-------------+
| 11 | C    | D     | -22.927507  |
+----+------+-------+-------------+
| 13 | D    | B     | -48.110161  |
+----+------+-------+-------------+
| 9  | C    | B     | -71.037668  |
+----+------+-------+-------------+
| 2  | A    | C     | -78.598163  |
+----+------+-------+-------------+
| 3  | A    | D     | -101.525670 |
+----+------+-------+-------------+
| 1  | A    | B     | -149.635831 |
+----+------+-------+-------------+

Спасибо sammywemmy за помощь в организации проблемы и предложении чего-то полезного.

...