{"cells":[{"metadata":{"_uuid":"8f2839f25d086af736a60e9eeb907d3b93b6e0e5","_cell_guid":"b1076dfc-b9ad-4769-8c92-a6c4dae69d19","trusted":true},"cell_type":"markdown","source":"# The final touch of Elo data demystification!\n\nI hope most of you have followed my previous work - if not - I encourage to read my previous work, so you would understand the context I am going to talk in this kernel.\n\nI suggest to read them in the following order:\n\n- https://www.kaggle.com/raddar/towards-de-anonymizing-the-data-some-insights\n- https://www.kaggle.com/raddar/target-true-meaning-revealed\n- https://www.kaggle.com/raddar/card-id-loyalty-different-points-in-time (bonus)\n- https://www.kaggle.com/raddar/merchant-id-imputations (bonus)\n\nIn this kernel I am going to show you some interesting things you can do, when you know how the target is calculated!\n\n### And it is one of the most interesting puzzles in the competition - so sit back, relax and enjoy!\n\nLet's read the data first and do data unscaling as discussed in previous kernels:"},{"metadata":{"trusted":true,"_uuid":"bda429ec6baa65616e3f5101c32443c77f420871"},"cell_type":"code","source":"import numpy as np\nimport pandas as pd\nimport itertools\n\npd.set_option('display.float_format', '{:.10f}'.format)\n\ntrain = pd.read_csv('../input/train.csv')\ncols = ['card_id','merchant_id','month_lag','purchase_amount','purchase_date','authorized_flag']\nhistorical_transactions = pd.read_csv('../input/historical_transactions.csv',usecols=cols).fillna('')\nnew_merchant_transactions = pd.read_csv('../input/new_merchant_transactions.csv',usecols=cols).fillna('')\n\nhistorical_transactions['purchase_amount'] = np.round(historical_transactions['purchase_amount'] / 0.00150265118 + 497.06,2)\nnew_merchant_transactions['purchase_amount'] = np.round(new_merchant_transactions['purchase_amount'] / 0.00150265118 + 497.06,2)\ntrain['target'] = 2**train['target']\n\n#only interested in authorized transactions:\nhistorical_transactions = historical_transactions.loc[historical_transactions['authorized_flag']=='Y'].reset_index(drop=True)","execution_count":null,"outputs":[]},{"metadata":{"_uuid":"f7d127a7c27873374fa7dc5d014dfb68c74c8ce5"},"cell_type":"markdown","source":"Here I will start with some simple data exploration which is going to be useful for later insights and calculations.\n\nWe are going to use the information about each card having different observation (reference) date. For each `card_id` the `historical_transactions` and `new_merchant_transactions` tables are split based on the reference date. So here comes the question - is it possible to create `new_merchant_transactions` table for any reference date for any `card_id`?\n\nIf you would think about it, you can only do that by shifting the reference date back in time, and not the future. We already know that `new_merchant_transactions` table should contain only new merchants (meaning not present in `historical_transactions`) for each `card_id`. So in general, we could extract information like `(card_id, merchant_id, purchase_date)`, which would represent the first appearance of `merchant_id` for the specific `card_id`.\n\nLet's try that!"},{"metadata":{"trusted":true,"_uuid":"1e8c3fb666f61d00ef0a2f3872edca0106cb8ef8"},"cell_type":"code","source":"# adding \"new merchant\" flag for each transaction\nfirst_hist_merchant_transaction = historical_transactions.groupby(['card_id','merchant_id'])['month_lag'].min().reset_index(name='month_lag')\nfirst_new_merchant_transaction = new_merchant_transactions.groupby(['card_id','merchant_id'])['month_lag'].min().reset_index(name='month_lag')\nfirst_hist_merchant_transaction['new'] = 1\nfirst_new_merchant_transaction['new'] = 1\nhistorical_transactions = historical_transactions.merge(first_hist_merchant_transaction, on = ['card_id','merchant_id','month_lag'], how = 'left')\nnew_merchant_transactions = new_merchant_transactions.merge(first_new_merchant_transaction, on = ['card_id','merchant_id','month_lag'], how = 'left')\nhistorical_transactions.loc[pd.isnull(historical_transactions['new']),'new'] = 0\nnew_merchant_transactions.loc[pd.isnull(new_merchant_transactions['new']),'new'] = 0","execution_count":null,"outputs":[]},{"metadata":{"_uuid":"42bb51861103408000f909136806389a0e021157","trusted":true},"cell_type":"markdown","source":"Let's look at the `purchase_amount` distribution by `month_lag` and `new` flag:"},{"metadata":{"trusted":true,"_uuid":"4b2849b008dae79e2078c35a3bb2de358580411d"},"cell_type":"code","source":"dist_hist = historical_transactions.groupby(['new','month_lag'])['purchase_amount'].sum().reset_index(name='total_purchase_amount')\ndist_new = new_merchant_transactions.groupby(['new','month_lag'])['purchase_amount'].sum().reset_index(name='total_purchase_amount')\ndist = pd.concat([dist_hist, dist_new]).reset_index(drop=True)","execution_count":null,"outputs":[]},{"metadata":{"trusted":true,"_uuid":"c8b1b48413b017ed893b333f523abe710c0bf3c0"},"cell_type":"code","source":"dist.pivot('month_lag','new','total_purchase_amount')","execution_count":null,"outputs":[]},{"metadata":{"_uuid":"303e23f55393f8b8ab051ea33c9fed6f13cab83b"},"cell_type":"markdown","source":"As you can see, we are missing transactions worth of 160-170 million (based on lag=-2,-1,0) for each future month.\n\nThe idea of this kernel is try to reverse engineer missing future transactions using `historical_transactions` and `target` information alone!\n\n# Let's start!\n\nAs I found out earlier, the `target` is calculated as a ratio of future/historical transactions. After digging the data around I found that the most likely formula is:\n\n\\begin{equation*}\ntarget(card\\_id) = \\frac{\\sum_{m} sum\\_future\\_purchase\\_amount (m,card\\_id)/2}{\\sum_{m} last\\_historic\\_transaction\\_purchase\\_amount (m, card\\_id)}\n\\end{equation*}\n\nwhere *m* represents  set of merchants, and only such merchants appearing both in historical **and** future transactions. The tricky part of this formula is that we do not know the most important part - *m*. If we knew *m*, we could easily reverse engineer the upper part of the formula, as `target` is given, and it is easy to calculate the denominator part of the ratio.\n\nSo, we can actually transform the problem into this:\n\n\\begin{equation*}\nloyal\\_spending(card\\_id)  = 2* target(card\\_id) * \\sum_{m} last\\_transaction\\_purchase\\_amount (m, card\\_id)\n\\end{equation*}\n\nwhere we try to estimate `loyal_spending` by looking for most likely *m*.\n\nIf we knew `loyal_spending` for each `card_id`, we could fill in the previous table easily! On top of that, we could build models which could directly try to predict `loyal_spending` for each `card_id` and use that in our model stack!\n\n# Combinatorics!\n\nSo how does one decide the set of *m* for each `card_id`? You will see, that this is actually a very interesting combinatorics problem!\n\nBut first, I want to remind everyone, that we are dealing with money - which means `purchase_amount` is a 2 decimal precision float. This is a very important piece of information to solve the puzzle. Why? You would expect `loyal_spending` also to have a precise 2 decimal precision float - sum of money is still money :)\n\nSo the idea is quite simple:\n\n- start with empty set of possible solutions `M`\n- take a candidate set `m` - set having 1 to N `merchant_id`'s from the pool of historic merchants\n- calculate `loyal_spending` based on the formula above\n- check if the `loyal_spending` rounds up to 2 decimal points nicely\n- if it rounds up - add `m` to your pool of solutions `M`\n- iterate `n` times or untill all possible `merchant_id` permutations are exhausted\n\nIf `M` contains only one solution - you got lucky, as you have identified a single solution for the given `target` value and `historical_transactions`. However, if `M` contains more than one solution, this is where you have to make assumptions and decide which is the most likely solution. I am going to cover this later.\n\n"},{"metadata":{"_uuid":"1a078b49b92fac0bf983fad2e14dde521a1f3ab4"},"cell_type":"markdown","source":"# Enough theory - start coding!\n\nNot yet... :) Before doing anything let's decide on a strategy how to select a best solution `m` from the pool of solutions `M`. The simpliest and most straightforward way I could think of was to calculate the average `month_lag` with the associated merchants, and use the solution, which  `average_month_lag` is closest to 0 - thus we give the higher priority to merchants who have appeared closest to the reference date. \n\nThere is still a possible tie situation, where 2 or more `m` sets have the same `average_month_lag` metric. For now I decided just to pick the first `m`, but of course, this could be made more sophisticated. However, sophisticated solution is not necesarilly better, as we cannot actually measure the error we are going to make (actually we can do the retrospective analysis, but it is out of scope).\n\nIf you feel it is hard to follow - relax!\nI have presented the process, but I am pretty sure you are going to re-read all of this when we do some actual coding and everything will make sense!"},{"metadata":{"_uuid":"71ed2f9324047dd4bf93820802e7040cbd7d4a6a"},"cell_type":"markdown","source":"# The code! \n\nFirst, let's extract the last `purchase_amount` for each `(card_id, merchant_id)`. It is necessary, because only last transaction matters in loyalty calculations:"},{"metadata":{"trusted":true,"_uuid":"1ab280102fc39ad41f33203a77a68b3894089abe"},"cell_type":"code","source":"historical_transactions = historical_transactions.sort_values(['card_id','purchase_date']).reset_index(drop=True)\nhistorical_transactions = historical_transactions.groupby(['card_id','merchant_id']).tail(1).reset_index(drop=True)","execution_count":null,"outputs":[]},{"metadata":{"_uuid":"833d1f3a065666954cfce96c45f881dc786698a1"},"cell_type":"markdown","source":"We want to avoid using pandas in further calculations, as it is extremely slow in indexing the data on such huge tables. Therefore, let's transform the data into useful python dicts containing the relevant information for our task."},{"metadata":{"trusted":true,"_uuid":"17d4d51bd51cda57737833509821f8826c564cb3"},"cell_type":"code","source":"# month lags\namtmth = historical_transactions[['card_id', 'purchase_amount','month_lag']].groupby(['card_id', 'purchase_amount'])['month_lag'].max().reset_index()\namtmth = amtmth.groupby('card_id').apply(lambda x: dict(zip(x['purchase_amount'],x['month_lag']))).reset_index(name = 'dict')\namtmth = dict(zip(amtmth['card_id'],amtmth['dict']))\n\n# purchase amounts \namtpurch = historical_transactions.groupby('card_id')['purchase_amount'].apply(list).reset_index(name='amounts')\namtpurch = dict(zip(amtpurch['card_id'],amtpurch['amounts']))\n\n# targets\ntarget = dict(zip(train['card_id'],train['target']))","execution_count":null,"outputs":[]},{"metadata":{"_uuid":"fc29d5f3dab19c1168b1a0210a5b98d0a5c1bb20"},"cell_type":"markdown","source":"This is the function I am going to use which does most of what I have discussed above:"},{"metadata":{"trusted":true,"_uuid":"e6323207dbb932d9185145c9e090abf48283cc73"},"cell_type":"code","source":"def get_future_amount(trainnum, max_combinations = 100000):\n    \"max_combinations: number of possible combinations to explore (less - faster, more - slower)\"\n\n    card_id = train['card_id'][trainnum]\n    k = 1\n    \n    #collection of possible solutions\n    comb = {}\n    comb2 = {}\n    \n    for i in range(1, 10):\n        # we want to fully exhaust solutions of length 1 and 2\n        # if we found something, do not go into deeper permutation levels\n        # 2 is arbitrary and can be tuned. However, starting from 3 performance drops significantly\n        if (len(comb) > 0) and (i > 2):\n            break\n        # need to set hard limit or else we are doomed :)\n        if k == max_combinations:\n            break    \n        for subset in itertools.combinations(amtpurch[card_id], i):\n            k+=1\n            if k == max_combinations:\n                break\n            amt = np.round(np.sum(subset), 2)\n            amt_month = np.mean([amtmth[card_id][x] for x in subset])\n            amt_target = amt * target[card_id] * 2 #this is the loyalty formula as discussed earlier!!!\n            # let's see if it rounds up nicely...\n            if np.round(amt_target, 2) == np.round(amt_target, 5):      \n                comb[tuple(sorted(subset))] = np.round(amt_target, 2), amt_month\n            # backup plan with higher error tolerance...\n            if np.round(amt_target, 2) == np.round(amt_target, 4):      \n                comb2[tuple(sorted(subset))] = np.round(amt_target, 2), amt_month\n    \n    # if no higher precision combinations found, use combinations with lower precision\n    if len(comb) == 0:\n        comb = comb2\n    \n    best = np.nan\n    if len(comb) > 0:       \n        q = [z[0] for z in comb.values()]\n        m = [z[1] for z in comb.values()]\n        best = q[np.argmax(m)]\n    return comb, best, target[card_id]","execution_count":null,"outputs":[]},{"metadata":{"_uuid":"cd585e8853de56a2fc55d11e3adff3772186d95c"},"cell_type":"markdown","source":"The function is quite costly - I would recomend to run it with multiprocessing while running on all `card_id` (takes couple of hours on 12 threads). Let's take a look at the first `card_id` in the train:"},{"metadata":{"trusted":true,"_uuid":"eb45f010676583ca9e5da0b93d59499c74712b49"},"cell_type":"code","source":"get_future_amount(0)","execution_count":null,"outputs":[]},{"metadata":{"_uuid":"2499f8ec222010605d49709a8d1cc0f6a49b852e"},"cell_type":"markdown","source":"There is a lot of information here, let's go it step by step:\n\n- The first element is dictionary of valid merchant proposals with their respective last `purchase_amount` (actual `merchant_id` does not matter - the amount does!). \n\n- dict keys represents the actual `purchase_amount`'s used to derive the `loyal_spending`. \n\n- dict values represents a) `loyal_spending` b) `average_month_lag` as discussed earlier.\n\n- The second element is the final `loyal_spending` selected from the given candidates (based on `average_month_lag`)\n\n- Third element is just for debug purposes - train target value\n\n\nEverything is quite simple here. Let's do simple maths. Sum of merchant historic transactions for possible `loyal_spending` are:\n\n`6.5 + 73.93 = 80.43`\n\n`19 + 129.95 = 148.95`\n\n`17.4 + 530.76 = 548.16`\n\n`120.67 + 530.76 = 651.43`\n\n`50 + 166.49 = 216.49`\n\n`5.3 + 166.49 = 171.79`\n\nWe know, that `target = 0.5663309969446729`. \n\nLet's put all that into `loyal_spending` formula:\n\n`loyal_spending = 2 * 0.5663309969446729 * 80.43 = 91.1000041685201`\n\n`loyal_spending = 2 * 0.5663309969446729 * 148.95 = 168.710003989818`\n\n`loyal_spending = 2 * 0.5663309969446729 * 584.16 = 620.879998570384`\n\n`loyal_spending = 2 * 0.5663309969446729 * 651.43 = 737.850002679337`\n\n`loyal_spending = 2 * 0.5663309969446729 * 216.49 = 245.209995057105`\n\n`loyal_spending = 2 * 0.5663309969446729 * 171.79 = 194.580003930251`\n\nAll these round up nicely to 2 digit precision float. \n\nAs discussed earlier, each of `loyal_spending` values are all possible. However, we already made a decision to pick one with closest to reference date  (using`average_month_lag`). This means that total loyal spending for this `card_id`  is 194.58 over 2 months. "},{"metadata":{"_uuid":"939039d90efcee477a0c0a10b53d19928e5bbe30"},"cell_type":"markdown","source":"Let's take a look how this `card_id` looks like in `historic_transactions` table (which has last transactions filetered already):"},{"metadata":{"trusted":true,"_uuid":"22c46c0a15c8724ab2c487a43e93898fa63ae280"},"cell_type":"code","source":"historical_transactions[historical_transactions['card_id']==train['card_id'][0]]","execution_count":null,"outputs":[]},{"metadata":{"_uuid":"b0ba65a63dcda54b06c8ade52ba42fb0a93c318c"},"cell_type":"markdown","source":"Based on that we can now pinpoint which actual `merchant_id`'s were used in loyalty calculation: `M_ID_1df4c6f47a` (`purchase_amount = 5.30`) and `M_ID_820c7b73c8` (`purchase_amount = 166.49`), and in the next 2 months a person spent 194.58 on these 2 merchants. How awesome is that?! - we were able to reverse engineer the data we were not provided in this competition! (I feel a bit confused why they did not provide such transactions for train part, but that is another topic...)"},{"metadata":{"_uuid":"c3316622c53774da3dc3da874a0e80fe832aea25"},"cell_type":"markdown","source":"To wrap it up let's run all of this for first 100 cards in train set just to see if we generalize this function well enough:"},{"metadata":{"trusted":true,"_uuid":"652b2fc65bc0e192820309a2bbd6e6df3f68f48b"},"cell_type":"code","source":"out = []\n\nfor i in range(100):\n    out.append(get_future_amount(i)[1])","execution_count":null,"outputs":[]},{"metadata":{"trusted":true,"_uuid":"fe0c2cf8fd7b583dfdfa754e1ee84590bf6a4ac6"},"cell_type":"code","source":"train['loyal_spending'] = np.nan\ntrain['loyal_spending'][0:100] = out\ntrain.head(100)","execution_count":null,"outputs":[]},{"metadata":{"_uuid":"8313501d3bdc294e701031ed8c35f1fe4b64dc15"},"cell_type":"markdown","source":"It seems all is good and the logic transfers for most of other `card_id`'s as well!"},{"metadata":{"_uuid":"65fe8cc853379f04d933198ec7d35cdb2b25391a"},"cell_type":"markdown","source":"# P.S.\n\nAlthough I spent a lot of time on finding the formula for `loyal_spending` calculations, I am still not 100% confident with that formula. However, if you were able to find other, better working formula, you could easily reproduce the following steps and get the results in the same way I did."},{"metadata":{"_uuid":"5ca1e525897e9c9b43abde9c894c0833aae7ff0d"},"cell_type":"markdown","source":"# What's next?\n\nThe findings are universal and applicable to all the `card_id`'s. This means that you can use calculated `loyal_spending` as a target for your new meta model and hope the stacking model would improve.\n\nIn my experience such approach did not give too much uplift -  I personally expected such approach to provide *killer* models in the stack. This may be related to the `m` selection process which I believe still involves high error rate.\n\nHowever, such type of models are in our final stack submission, thus proven useful!\n\n# Thank you for following!\n\n## upvote if you liked the content :)\n\n### see you all in next competitions - I hope to not stop making kernels in the future."},{"metadata":{"_uuid":"d06215b7f10127727b24cd344ccb5596b9179f64"},"cell_type":"markdown","source":""},{"metadata":{"_cell_guid":"79c7e3d0-c299-4dcb-8224-4455121ee9b0","collapsed":true,"_uuid":"d629ff2d2480ee46fbb7e2d37f6b5fab8052498a","trusted":false},"cell_type":"markdown","source":""}],"metadata":{"kernelspec":{"display_name":"Python 3","language":"python","name":"python3"},"language_info":{"name":"python","version":"3.6.6","mimetype":"text/x-python","codemirror_mode":{"name":"ipython","version":3},"pygments_lexer":"ipython3","nbconvert_exporter":"python","file_extension":".py"}},"nbformat":4,"nbformat_minor":1}