As the age of big data evolves, outsourcing of data mining tasks to multi-cloud environments has become a popular trend. To ensure the data privacy in outsourcing of mining tasks, the concept of support anonymity was proposed to hide sensitive information about patterns. Existing methods that tackle the privacy issues, however, do not address the related parallel mining techniques. To fill this gap, we refer to a pseudo-taxonomy based technique, called as k-support anonymity, and improve it into multi-cloud environments. This has several advantages. First, outsourcing to multi-cloud environments can meet the requirement of great computational resources in big data mining, and also parallelize the mining tasks for better efficiency. Second, the data that we send out to a cloud can be partial. An assaulter who gets the data in one cloud can never re-construct the original data. That means it is more difficult for an assailant to violate the privacy in outsourced data. Experimental results also demonstrated that our approaches can achieve good protection and better computation efficiency.