インテル® DAAL 2018 デベロッパー・ガイド
np 次元の特徴ベクトルのセット X = { x1= (x11,…,x1p), ..., xn= (xn1,…,xnp) } および正の整数 k で、目的関数 (総合誤差) を最小化する kp 次元のベクトルのセット C = { c1, ..., ck } を見つけます。
ベクトル c1,…,ck はセントロイドと呼ばれます。計算を開始するには、アルゴリズムにセントロイドの初期値が必要です。
セントロイド初期化は、以下の方法を使用して行います。
データセット X から最初の k 特徴ベクトルを選択します。
次の (単純なランダム・サンプリング) アルゴリズムを使用してデータセットから k 特徴ベクトルをランダムに選択します。アルゴリズムは次の操作を行います。
等確率で X から特徴ベクトル xi の 1 つを選択します。
X から xi を除外して、現在の中心のセットに追加します。
中心のセットがサイズ k に達するまでステップ 1 から繰り返します。
総合誤差 ΦX(C) の寄与度に比例する確率で中心を選択する K-Means++ アルゴリズム [Arthur2007] は、以下のスキームに従います。
等確率で X から特徴ベクトル xi の 1 つを選択します。
X から xi を除外して、現在の中心のセット C に追加します。
X の各特徴ベクトル xi について、現在の中心のセット C から最小距離 d(xi, C) を計算します。
確率 で X から特徴ベクトル xi の 1 つを選択します。
中心のセット C がサイズ k に達するまでステップ 2 から繰り返します。
並列 K-Means++ アルゴリズム [Bahmani2012] は次の操作を行います。
等確率で X から特徴ベクトル xi の 1 つを選択します。
X から xi を除外して、現在の中心のセット C に追加します。
次の操作を nRounds 回繰り返します。
X から各特徴ベクトル xi について、現在の中心のセット C から最小距離 d(xi, C) を計算します。
確率 で X から L=oversamplingFactor*k 特徴ベクトル xi を選択します。
X から前のステップで選択した xi ベクトルを除外して、現在の中心のセット C に追加します。
ci∈C で、wi がC のどのポイントよりも ci に近い X のポイント数になるように設定します。
重み wi で K-Means++ アルゴリズムを C のポイントに適用します。これは、次の確率がステップ 4 で使用されることを意味します。
アルゴリズム・パラメーターは、各ラウンドで選択される候補の数 L とラウンド数を定義します。
L=O(k) になる oversamplingFactor を選択します。
O(logΦx(C)) のように nRounds を選択します。ここで、Φx(C) は最初の中心を選択したときの目標関数の推定です。[Bahmani2012] では、nRounds を 8 以下の定数値に設定することを推奨しています。
目標関数の計算には、ベクトル間のユークリッド距離の計算 ||xj- mi|| が含まれます。アルゴリズムは、特徴ベクトル a と b の間のユークリッド距離: d(a,b) = d1(a,b) + d2(a,b) を使用します。ここで、d1 は連続特徴の計算に使用されます。
d2 は二項カテゴリカル特徴の計算に使用されます。
これらの式で、γ はクラスタリングの二項カテゴリカル特徴の影響の重み、p1 は連続特徴の数、p2 は二項カテゴリカル特徴の数です。アルゴリズムは非二項カテゴリカル特徴をサポートしないことに注意してください。
K 平均法アルゴリズムは、Lloyd メソッド [Lloyd82] を使用してセントロイドを計算します。各特徴ベクトル x1,…,xn で、特徴ベクトルを含むクラスターのインデックスを計算することもできます。