Abstract: Clustering is one of the most widely used data mining algorithm.In order to improve the quality of clustering results,we present a k-means algorithm based on optimization of attribute weight using Lagrange multiplier method.The algorithm uses the weight value for each attribute to determine the importance of that attribute while computing the distance between an instance and the centroid of a cluster.In each iteration of clustering,it computes the optimal weight of attributes according to the change of centroid vector which minimizes the sum of distance between each instance and the centroid.The experimental results demonstrate that the quality of clustering results can be improved significantly with the algorithm comparing with the traditional k-means algorithm.