Detect outlier first, if you data set maybe contain outlier.
Try the isolationForest method, it's fast and efficient to detect the outliers.
update:
isolationForest
papers:https://cs.nju.edu.cn/zhouzh/zhouzh.files/publication/tkdd11.pdf
python code:http://scikit-learn.org/dev/modules/generated/sklearn.ensemble.IsolationForest.html