標本集合X = \{ x_i ; 1 \leq 1 \leq n \} (標本数n)を考える。
クラスタ数をkとする。
はじめに，全ての標本x_i \in Xについて，ランダムに所属するクラスタc_i (1 \leq c_i \leq k)を割り当てておく。(x_i \mapsto c_i)
次のステップ1，ステップ2を更新されなくまで繰り返し行う。
ステップ1: クラスタC (1 \leq C \leq k)について，所属する標本の重心を求める。これをm_Cとする。
ステップ2: 全ての標本x_i \in Xについて，最も重心の近いクラスタを選び，それを新たなc_iとする。すなわち各iについてc_i = \textrm{arg}\min_{1 \leq C \leq k} || x_i - m_C ||とする。
以上により標本x_iの所属するクラスタc_iを決定する。