Microsoft クラスタリング アルゴリズム テクニカル リファレンス

EM クラスタリングでは、初期クラスター モデルがデータに合わせて反復的に調整され、データ ポイントがクラスター内に存在する確率が判定されます。このプロセスは、その確率論的モデルがデータに適合すると終了します。適合の判定に使用される関数は、与えられたモデルに対するデータの対数尤度です。

このプロセスで空のクラスターが生成された場合や、メンバーシップが指定のしきい値に達していないクラスターがあった場合は、母集団の小さいクラスターが新しいポイントで再シードされ、EM アルゴリズムが再実行されます。

EM クラスタリング手法の結果は確率論的です。つまり、すべてのデータ ポイントがすべてのクラスターに所属しますが、割り当ての確率はそれぞれ異なります。この手法ではクラスターの重複が許可されるため、すべてのクラスター内のアイテムの合計がトレーニング セットのアイテムの合計数を上回る場合もあります。マイニング モデルの結果では、このことを反映してサポートのスコアが調整されます。

EM アルゴリズムは、Microsoft クラスター モデルで使用される既定のアルゴリズムです。このアルゴリズムが既定で使用されるのは、K-Means クラスタリングに比べて次のような利点があるためです。

• データベースのスキャンが 1 回で済む。

• メモリ (RAM) が限られていても動作する。

• 順方向専用カーソルを使用できる。

• サンプリングの手法よりパフォーマンスが高い。

Microsoft の実装には、スケーラブル EM と非スケーラブル EM の 2 つのオプションがあります。既定のスケーラブル EM では、初期スキャンのシードに最初の 50,000 レコードが使用されます。これが成功した場合は、モデルでそのデータのみが使用されます。50,000 個のレコードを使用して適切なモデルを作成できなかった場合は、さらに 50,000 個のレコードが読み取られます。非スケーラブル EM では、サイズにかかわらずデータセット全体が読み取られます。これにより、より正確なクラスターが作成される場合もありますが、必要なメモリの量が大幅に増加する可能性があります。スケーラブル EM では、ローカル バッファーが使用されるため、データの反復処理が大幅に高速化されます。また、非スケーラブル EM よりはるかに効率的に CPU メモリ キャッシュを活用できます。さらに、すべてのデータがメイン メモリに収まる場合でも非スケーラブル EM に比べて 3 倍高速になります。このパフォーマンスの改善によって最終的なモデルの質が低下することもほとんどありません。

Microsoft クラスタリング アルゴリズムの EM の実装に関する技術的なレポートについては、「EM (Expectation Maximization) クラスタリングの大規模データベースへのスケーリング」を参照してください。

K-Means クラスタリングは、クラスター内のアイテム間の相違を最小化し、クラスター間の距離を最大化することによってクラスター メンバーシップを割り当てる、よく知られている手法です。K-Means の "Means" は、クラスターの重心を表します。クラスターの重心とは、任意に選択され、クラスター内のすべてのデータ ポイントの真の平均を表すようになるまで反復的に調整されるデータ ポイントです。"K" は、クラスタリング処理のシードに使用される任意の数のポイントを表します。K-Means アルゴリズムでは、クラスター内のデータ レコードと、クラスターの平均を表すベクトルとの間のユークリッド距離の 2 乗を計算し、その総和が最小値に達したとき、最終的な k 個のクラスターのセットに収束します。

K-Means アルゴリズムでは、各データ ポイントが割り当てられるクラスターは 1 つだけであり、メンバーシップのあいまいさは許容されません。クラスターのメンバーシップは重心からの距離として表されます。

K-Means アルゴリズムは、平均への距離を簡単に計算できる連続属性のクラスターの作成に使用されるのが一般的ですが、Microsoft の実装では、確率を使用することにより、不連続属性に対しても使用できるようになっています。 不連続属性の場合、特定のクラスターからデータ ポイントまでの距離は次のように計算されます。

1 - P(data point, cluster)

注
Microsoft クラスタリング アルゴリズムでは、K-Means の計算に使用される距離関数は公開されておらず、完成したモデルで距離の測定値を使用することはできません。ただし、予測関数を使用して、距離に相当する値を取得することができます。この場合の距離は、データ ポイントがクラスターに属する確率として計算されます。詳細については、「ClusterProbability (DMX)」を参照してください。

K-Means アルゴリズムには、データセットのサンプリング方法が 2 つ用意されています。1 つ目の非スケーラブル K-Means では、データセット全体を読み込んで 1 つのクラスタリング パスを作成します。2 つ目のスケーラブル K-Means では、最初の 50,000 ケースを使用してデータに適合するモデルを作成できなかった場合にのみ追加のケースが読み取られます。

SQL Server 2008 では、Microsoft クラスタリング アルゴリズムの既定の構成が、内部パラメーター NORMALIZATION = 1 を使用するように変更されました。正規化は z スコア統計を使用して実行され、正規分布を想定しています。既定の動作をこのように変更したのは、規模が大きくなって外れ値が増える可能性がある属性の影響を最小限に抑えるためです。 ただし、z スコア正規化により、正規ではない分布 (均一分布など) のクラスタリング結果が異なる可能性があります。この実装の結果として、SQL Server 2005 Analysis Services から 2008 に移行した顧客は、クラスター モデルによって生成される結果が異なることに気付くかもしれません。正規化を回避し、SQL Server 2005 の K-Means クラスタリング アルゴリズムと同じ動作を得るには、[パラメーター設定] ダイアログ ボックスを使用して、カスタム パラメーター NORMALIZATION を追加し、その値を 0 に設定します。

注
NORMALIZATION パラメーターは Microsoft クラスタリング アルゴリズムの内部プロパティであり、サポートされていません。通常、モデルの結果を向上させるには、クラスタリング モデルで正規化を使用することをお勧めします。

次の表は、Microsoft クラスタリング アルゴリズムで使用できるパラメーターを示しています。これらのパラメーターは、結果として得られるマイニング モデルのパフォーマンスと精度の両方に影響を与えます。

• CLUSTERING_METHOD
  アルゴリズムで使用するクラスタリング手法を指定します。使用可能なクラスタリング手法は次のとおりです。

  ID	手法
  1	スケーラブル EM
  2	非スケーラブル EM
  3	スケーラブル K-Means
  4	非スケーラブル K-Means

  既定値は 1 (スケーラブル EM) です。

• CLUSTER_COUNT
  アルゴリズムによって作成されるクラスターの概数を指定します。その数のクラスターをデータから作成できない場合、アルゴリズムでは可能な限り多数のクラスターが作成されます。CLUSTER_COUNT を 0 に設定すると、アルゴリズムではヒューリスティックを使用して、作成するクラスターの数が最適に決定されます。

  既定値は 10 です。

• CLUSTER_SEED
  モデル作成の初期段階にクラスターをランダムに生成するために使用するシード数を指定します。

  この数を変更することにより、初期クラスターの作成方法を変更できます。その後、異なるシードを使用して作成したモデルを比較することができます。シードを変更しても検出されるクラスターがあまり変わらない場合は、モデルが比較的安定していると考えることができます。

  既定値は 0 です。

• MINIMUM_SUPPORT
  クラスターの作成に必要なケースの最小数を指定します。ケースの数がこの数より少ないクラスターは空のクラスターとして扱われ、破棄されます。

  この数を高く設定しすぎると、有効なクラスターを見落とす可能性があります。

  注
  既定のクラスタリング手法である EM を使用すると、指定した値より低いサポート値を持つクラスターが作成される場合があります。これは、各ケースがすべての可能なクラスターのメンバーシップについて評価されるため、中には最小限のサポートしかないクラスターもあるからです。

  既定値は 1 です。

• MODELLING_CARDINALITY
  クラスタリング処理中に作成するサンプル モデルの数を指定します。

  この数を減らすと、適切な候補モデルが作成されなくなる可能性もありますが、パフォーマンスを向上させることができます。

  既定値は 10 です。

• STOPPING_TOLERANCE
  収束に到達し、アルゴリズムによるモデルの作成が完了する時点を決定するための値を指定します。収束に到達するのは、クラスターの確率の全体的な変化が、モデルのサイズで除算された STOPPING_TOLERANCE パラメーターの比率未満のときです。

  既定値は 10 です。

• SAMPLE_SIZE
  CLUSTERING_METHOD パラメーターをスケーラブルなクラスタリング手法のいずれかに設定する場合に、アルゴリズムにより各パスで使用されるケースの数を指定します。SAMPLE_SIZE パラメーターを 0 に設定すると、データセット全体が単一のパスでクラスター化されます。データセット全体を単一のパスで読み込むと、メモリやパフォーマンスの問題が発生する可能性があります。

  既定値は 50000 です。

• MAXIMUM_INPUT_ATTRIBUTES
  選択した機能を呼び出す前にアルゴリズムが処理できる入力属性の最大数を指定します。この値を 0 に設定した場合、属性数の上限はありません。

  属性の数を増やすと、パフォーマンスが大幅に低下する可能性があります。

  既定値は 255 です。

• MAXIMUM_STATES
  アルゴリズムによってサポートされる属性状態の最大数を指定します。属性の状態の数が最大数よりも大きい場合、アルゴリズムでは最も一般的な状態が使用され、残りの状態は無視されます。

  状態の数を増やすと、パフォーマンスが大幅に低下する可能性があります。

  既定値は 100 です。

アルゴリズムでは、次のモデリング フラグがサポートされています。モデリング フラグは、マイニング構造やマイニング モデルを作成するときに定義し、分析時に各列の値をどのように処理するかを指定します。

Microsoft クラスタリング アルゴリズムでは、次の表に示す特定の入力列と予測可能列がサポートされています。マイニング モデルにおけるコンテンツの種類の意味については、「コンテンツの種類 (データ マイニング)」を参照してください。

注
コンテンツの種類 Cyclical および Ordered はサポートされますが、アルゴリズムはこれらを不連続の値として扱い、特別な処理は行いません。