|
In data mining, ''k''-means++〔http://theory.stanford.edu/~sergei/slides/BATS-Means.pdf Slides for presentation of method by Arthur, D. and Vassilvitskii, S. 〕 is an algorithm for choosing the initial values (or "seeds") for the ''k''-means clustering algorithm. It was proposed in 2007 by David Arthur and Sergei Vassilvitskii, as an approximation algorithm for the NP-hard ''k''-means problem—a way of avoiding the sometimes poor clusterings found by the standard ''k''-means algorithm. It is similar to the first of three seeding methods proposed, in independent work, in 2006 by Rafail Ostrovsky, Yuval Rabani, Leonard Schulman and Chaitanya Swamy. (The distribution of the first seed is different.) ==Background== The ''k''-means problem is to find cluster centers that minimize the intra-class variance, i.e. the sum of squared distances from each data point being clustered to its cluster center (the center that is closest to it). Although finding an exact solution to the ''k''-means problem for arbitrary input is NP-hard, the standard approach to finding an approximate solution (often called Lloyd's algorithm or the ''k''-means algorithm) is used widely and frequently finds reasonable solutions quickly. However, the ''k''-means algorithm has at least two major theoretic shortcomings: * First, it has been shown that the worst case running time of the algorithm is super-polynomial in the input size. * Second, the approximation found can be arbitrarily bad with respect to the objective function compared to the optimal clustering. The ''k''-means++ algorithm addresses the second of these obstacles by specifying a procedure to initialize the cluster centers before proceeding with the standard ''k''-means optimization iterations. With the ''k''-means++ initialization, the algorithm is guaranteed to find a solution that is O(log ''k'') competitive to the optimal ''k''-means solution. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「K-means++」の詳細全文を読む スポンサード リンク
|