Journal of Software Engineering1819-43112152-0941orgz10.3923/jse.2011.116.126YuY.C.WangJ.D.ZhengG.S.JiangY.4201154Pairwise constraints can effectively improve the clustering results. However, noise constraints will seriously affect the performance of clustering. To improve the distributed clustering with constraints, distributed k-means based-on soft constraints, which constraint violations can be effectively dealt with, is presented in this paper. Aiming at the limitation of distributed clustering, such as communication cost and data privacy etc., only positive constraints by chunklets are used in the proposed method. To simplify the treatment of constrained data points, the mean value of chunklet is used as the representative point. Then positive constraints among chunklet are approximately transformed into pairwise positive constraints between each data points from the chunklet and the mean value. Thus, the cluster label of each mean value is regarded as the label estimation of data points from the chunklet. Based on the above approximation, a new measure of partition cost used to deal with constraint violations is defined. Therefore, for unconstrained data points, the within-cluster sum of distance squares can be minimized. Meanwhile, for constrained data points, the sum of distance between data points and corresponding centriods and the cost of constraint violations is minimized too. The experimental results showed that the proposed method decreases the computation complexity of constraint violations. Compared with hard constrained distributed clustering, the clustering accuracy of the proposed method is increased.]]>Bandyopadhyay, S., C. Giannella, U. Maulik, H. Kargupta, K. Liu and S. Datta,2006Bar-Hillel, A., T. Hertz, N. Shental and D. Weinshall,2005Basu, S., A. Banerjee and R.J. Mooney,2004Bilenko, M., S. Basu and R.J. Mooney,2004Davidson, I., K.L. Wagstaff and S. Basu,2006Dhillon, I.S. and D.S. Modha,1999Ester, M., H.P. Kriegel, J. Sander and X. Xu,1996Januzaj, E., H.P. Kriegel and M. Pfeifle,2004Januzaj, E., H.P. Kriegel and M. Pfeifle,2004Johnson, E.L. and H. Kargupta,1999Klusch, M., S. Lodi and G. Moro,2003Kriegel, H.P., P. Kroger, A. Pryakhin and M. Schubert,2005Park, B.H. and H. Kargupta,2002Samatova, N.F., G. Ostrouchov, Al Geist and A.V. Melechko,2002Tasoulis, D.K. and M.N. Vrahatis,2004Yuecheng, Y., W. Jiandong, Z. Guansheng and C. Bin,2011