Social networks have become a popular and powerful communication platform as the mobile technology evolves. To evaluate the influence of a message on a social network, response prediction is crucial in modeling the message propagation and interaction among users. To predict whether a new message will receive responses, we propose a two-stage learning method using a new set of features derived from the messages, the users and theirresponding behaviors. This method first clusters the messages, and then learns the different prediction models from the clusters respectively. The central argument for this two-stage strategy is that the classifiers trained separately from the clustered data sets can focus on particular types of data, reduce the effects of noise, and consequently have an overall higher predictive performance than a single classifier trained from the entire data set. We tested the proposed two-stage learner on Plurk, and compared it withother classifiers. The experimental results show that the two-stage learner outperformed the gradient boosting decision tree learner, the logistic function learner, and the support vector machine for not only the predictive accuracy, but also for the efficiency.