What do I do when my column has 50% data missing? I have a data set i am pre-processing. However in my categorical columns (3 of them) i have "??" in it's place. They constitute 50% of the data. In fact 3 columns have this. My question is how should i impute this? Do i replace ? with unknown or do i replace it with NaN. 

Since my end goal is a classification problem i will be applying various algos on it such as NB classifier, random forest, decision tree, K neighbours. And sometimes it does not matter whether you impute or not since some algos do it for you
It depends on your knowledge of the problem. First, you should classify why is it missing??

Structurally missing data
Structurally missing data is data that is missing for a logical reason. In other words, it is data that is missing because it should not exist.check this


Structurally missing data is data that is missing for a logical reason. In other words, it is data that is missing because it should not exist.
Missing completely at random (MCAR) No pattern in missing data
Missing at random (MAR)An alternative assumption, known somewhat confusingly as missing at random (MAR), instead assumes that we can predict the value that is missing based on the other data.


Then choose your imputing technique based on your knowledge of the problem if you have other cases you can try (from this source):


Encode NAs as -1 or -9999. This works reasonably well for numerical features that are predominantly positive in value, and for tree-based models in general. This used to be a more common method in the past when the out-of-the box machine learning libraries and algorithms were not very adept at working with missing data.
Casewise deletion of missing data. Here you simply drop all cases/rows from the dataset that contain missing values. In the case of a very large dataset with very few missing values, this approach could potentially work really well. However, if the missing values are in cases that are also otherwise statistically distinct, this method may seriously skew the predictive model for which this data is used. Another major problem with this approach is that it will be unable to process any future data that contains missing values. If your predictive model is designed for production, this could create serious issues in deployment.
Replace missing values with the mean/median value of the feature in which they occur. This works for numerical features. The choice of median/mean is often related to the form of distribution that the data has. For imbalanced data, the median may be more appropriate, while for symmetrical and more normally distributed data, the mean could be a better choice.
Label encode NAs as another level of a categorical variable. This works with tree-based models and other models if the feature can be numerically transformed (one-hot encoding, frequency encoding, etc.). This technique does not work well with logistic regression.
Run predictive models that impute the missing data. This should be done in conjunction with some kind of cross-validation scheme in order to avoid leakage. This can be very effective and can help with the final model.
Use the number of missing values in a given row to create a new engineered feature. As mentioned above, missing data can often have lots of useful signal in its own right, and this is a good way to encode that information.