Walmart and Random Forest
Contributed by William Aiken. He took NYC Data Science Academy 12 week full time Data Science Bootcamp program between Sept 23 to Dec 18, 2015. The post was based on his fourth class project(due at 8th week of the program).
==================
In the recent Walmart Kaggle competition I used a Random Forest classifier to solve a market basket problem. A market basket model is built on the idea there exists relationships between items purchased together. For example, a person purchasing a new toothbrush is more likely to also purchase toothpaste than motor oil in the same shopping. Retailers use these market basket relationships in the design of their stores for ease of use and also to increase sales. In this specific problem Walmart has broken up their shopping trips into 38 unique 'TripType'. They give you a training data set with over 600,000 rows and a test data set of the same size. The training data set contained the 'TripType' and it was your job to predict the 'TripType' of the test set. The 'TripTypes' were numeric dummy variables and contain no explicit information. Each row in the data sets contained features about one item purchased. Participants were given a 'Upc' code, a 'Weekday', 'DepartmentDescription', 'ScanCount', and 'VisitNumber'. You are also given a 'FinelineNumber' which was used as internal market basket classifier for an item. Unlike a Upc number which was unique to an item, the 'FinelineNumber' was shared by items commonly purchased together. Toothpaste and toothbrushes might share a 'FinelineNumber'. Participants were not allowed to use any external data in this contest. There was plenty of information to extract from the data already given. In the Walmart Kaggle forum, the person at the top of the leader board made a post stating that the secret to success in this contest would hinge on feature engineering and not so much on complicated ensemble methods. Based on that advice, I leapt directly into generating new features.
I looked at the columns in the data set and thought about what information was there but not explicitly stated. Feature engineering is also an example of where domain knowledge is important. I thought about shopping trips and what are the things that make trips different. Trips are different in their composition and quantity of items. Through some very simple arithmetic operations one would be able to generate other features that improves the granularity of the dataset. They tell you that any item that has a negative 'Scan Count' is a returned item. Could that be an important feature? Because you have the 'Scan Count' and the 'VisitNumber' you are able to calculate both the total number of items purchased and also the percentage of each trip that belongs to a specific item. Once you have the total number of items in each trip, you are also able to generate features to show the percentage of each trip that belongs to a 'FinelineNumber' and a 'DepartmentDescription'. It also should be noted that there were some missing data in both the training and test set. I replaced the NaNs with a proxy value not found in the data set. If you try deleting the rows based on the logic that they comprise such a small percentage of the data set, you will run into problems with your test submission, Kaggle expects the submission to have certain dimensions. My code for this feature engineering is shown below.
Returned = grpwall.merge(pd.DataFrame({'ItemReturned':grpwall.ScanCount <= 0}),\ left_index = True, right_index = True) Returned['RealSC'] = Returned.ScanCount Returned['RealSC'].ix[Returned.ItemReturned]=0 containsReturned = Returned.merge(pd.DataFrame\ ({'ContainsReturned':Returned.groupby('VisitNumber').sum().ItemReturned>=1}),\ left_on=['VisitNumber'], right_index=True) NumberReturned = containsReturned.merge(pd.DataFrame\ ({'NumReturned':containsReturned.groupby('VisitNumber').sum().ItemReturned}),\ left_on=['VisitNumber'], right_index=True) nUnqItems = NumberReturned.merge(pd.DataFrame\ ({'itemcount':NumberReturned.groupby('VisitNumber').size()}),\ left_on=['VisitNumber'], right_index=True) addFeats = nUnqItems.merge(pd.DataFrame\ ({'totalcount':nUnqItems.groupby('VisitNumber').sum().RealSC}),\ left_on=['VisitNumber'], right_index=True) grpUpc = pd.DataFrame({'percentTrip':addFeats.groupby\ (['VisitNumber','Upc']).size()/addFeats.groupby(['VisitNumber']).size()}) prcntTrip = addFeats.merge(grpUpc, left_on=['VisitNumber', 'Upc'], right_index = True) grpLineItem = pd.DataFrame({'percentLineTrip':addFeats.groupby\ (['VisitNumber','FinelineNumber']).size()/addFeats.groupby(['VisitNumber']).size()}) prcntTripII = prcntTrip.merge(grpLineItem, left_on=['VisitNumber', 'FinelineNumber'], right_index = True) grpDepartItem = pd.DataFrame({'percentDepartTrip':addFeats.groupby\ (['VisitNumber','DepartmentDescription']).size()/addFeats.groupby(['VisitNumber']).size()}) prcntTripIII = prcntTripII.merge(grpDepartItem,\ left_on=['VisitNumber', 'DepartmentDescription'], right_index = True)
Once you have your new features it's time to run some models. I chose Random Forest due to it's ability to handle the large amounts of categorical features contained in the data set. It also avoids the issue of over-fitting the data based on the way that the trees are built. Each tree is built on a random subset of features that reduces the correlation between trees. There is a beautiful library for Python called Scikit-learn that will have you building random forests in no time. I split my training set in a 80/20 split, saving the 20% as a validation to get an estimate of the test error rate. I then built my model on the entire training set and then made a prediction with my test set. I ran Random Forest a number of times as I engineered different features and you can see the results of my Kaggle submissions below. Kaggle uses logloss as a measure of accuracy, it can be thought of as the amount of entropy attached to a prediction.
It should be noted that the features that I mentioned above were not the only features that I tried and you can see from my Kaggle results not every feature adds to the predictive power of your model. Once I had features that I was happy with, it was time to tune Random Forest. While just making submissions based on each new feature that improved my estimate of the test error was a reasonable process for feature engineering, it wouldn't work for parameter tuning. There are way too many possible parameter options to use such an inefficient process. The best way to tune your parameters is to use a grid search with cross validation. In this process you create a matrix of all ranges of values for your parameters. You then run Random Forest on all of these possible parameter values and record the estimated accuracy. This will give you the best combination of parameter values. You used cross validation because multiple splits will give you a better estimate of the test error than one split alone. I used code directly from the Scikit-learn documentation for this process. This method gave me the optimized parameters that provided my best score. I'm continuing to work on the Walmart problem but with two advancements. I'm trying to see if XGBoost gives me better results than Random Forest (not yet) and I'm also moving my work on to an AWS instance to improve speed. If you want to see what I did in its entirety please check out my Github link at the top of the page.
About Author
