インテル® DAAL 2018 デベロッパー・ガイド

詳細

np 次元の特徴ベクトルのセット X = { x1= (x11,…,x1p), ..., xn= (xn1,…,xnp) } および正の整数 k で、目的関数 (総合誤差) を最小化する kp 次元のベクトルのセット C = { c1, ..., ck } を見つけます。



ここで、d2(xi,C) は、ユークリッド距離のように、xi から C の最も近い中心までの距離です。

ベクトル c1,…,ck はセントロイドと呼ばれます。計算を開始するには、アルゴリズムにセントロイドの初期値が必要です。

セントロイド初期化

セントロイド初期化は、以下の方法を使用して行います。

  • データセット X から最初の k 特徴ベクトルを選択します。

  • 次の (単純なランダム・サンプリング) アルゴリズムを使用してデータセットから k 特徴ベクトルをランダムに選択します。アルゴリズムは次の操作を行います。

    1. 等確率で X から特徴ベクトル xi の 1 つを選択します。

    2. X から xi を除外して、現在の中心のセットに追加します。

    3. 中心のセットがサイズ k に達するまでステップ 1 から繰り返します。

  • 総合誤差 ΦX(C) の寄与度に比例する確率で中心を選択する K-Means++ アルゴリズム [Arthur2007] は、以下のスキームに従います。

    1. 等確率で X から特徴ベクトル xi の 1 つを選択します。

    2. X から xi を除外して、現在の中心のセット C に追加します。

    3. X の各特徴ベクトル xi について、現在の中心のセット C から最小距離 d(xi, C) を計算します。

    4. 確率 X から特徴ベクトル xi の 1 つを選択します。

    5. 中心のセット C がサイズ k に達するまでステップ 2 から繰り返します。

  • 並列 K-Means++ アルゴリズム [Bahmani2012] は次の操作を行います。

    1. 等確率で X から特徴ベクトル xi の 1 つを選択します。

    2. X から xi を除外して、現在の中心のセット C に追加します。

    3. 次の操作を nRounds 回繰り返します。

      1. X から各特徴ベクトル xi について、現在の中心のセット C から最小距離 d(xi, C) を計算します。

      2. 確率 X から L=oversamplingFactor*k 特徴ベクトル xi を選択します。

      3. X から前のステップで選択した xi ベクトルを除外して、現在の中心のセット C に追加します。

    4. ciC で、wiC のどのポイントよりも ci に近い X のポイント数になるように設定します。

    5. 重み wi で K-Means++ アルゴリズムを C のポイントに適用します。これは、次の確率がステップ 4 で使用されることを意味します。



    アルゴリズム・パラメーターは、各ラウンドで選択される候補の数 L とラウンド数を定義します。

    • L=O(k) になる oversamplingFactor を選択します。

    • O(logΦx(C)) のように nRounds を選択します。ここで、Φx(C) は最初の中心を選択したときの目標関数の推定です。[Bahmani2012] では、nRounds を 8 以下の定数値に設定することを推奨しています。

計算

目標関数の計算には、ベクトル間のユークリッド距離の計算 ||xj- mi|| が含まれます。アルゴリズムは、特徴ベクトル ab の間のユークリッド距離: d(a,b) = d1(a,b) + d2(a,b) を使用します。ここで、d1 は連続特徴の計算に使用されます。

d2 は二項カテゴリカル特徴の計算に使用されます。

これらの式で、γ はクラスタリングの二項カテゴリカル特徴の影響の重み、p1 は連続特徴の数、p2 は二項カテゴリカル特徴の数です。アルゴリズムは非二項カテゴリカル特徴をサポートしないことに注意してください。

K 平均法アルゴリズムは、Lloyd メソッド [Lloyd82] を使用してセントロイドを計算します。各特徴ベクトル x1,…,xn で、特徴ベクトルを含むクラスターのインデックスを計算することもできます。