Data preparation and machine learning algorithm for click prediction
Some suggestions


Remove items appearing too infrequently in the data. That will reduce the dimensionality by several orders of magnitude. If a feature occurs less than say 10 times, it's likely that it's not adding any predictive value, and it may lead to overfitting due to low frequency
Try a Linear SVM instead. They handle large dimensional data very well in terms of not overfitting. They also often have the option to assign relative weights to different classes, which may help address your unbalanced problem above. The sklearn svm (which simply wraps some other packages such as libsvm) has this option.
Don't use the ID column. Producing a model per user will most probably lead to overfitting. Instead, feed in attributes that describe the user that allows the model to generalize over similar users. You could try fitting a separate model per user, but you need a lot of data per user to do this well.
It sounds like you really need to try some feature selection here, to reduce the dimensionality of the problem. But try 1 and 2 first, as they may give you good results sooner (although the end solution may still work better with some good feature selection). Sklearn again has a number of options for feature selection.