次の方法で共有

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

  • [アーティクル]

このセクションでは、クラスタリング モデルの動作を制御するために使用できるパラメーターなど、Microsoft クラスタリング アルゴリズムの実装について説明します。 クラスター モデルの作成時や処理時のパフォーマンスを向上させる方法に関するアドバイスも含まれています。

クラスター モデルの使用方法の詳細については、次のトピックを参照してください。

Microsoft クラスタリング アルゴリズムの実装

Microsoft クラスタリング アルゴリズムには、クラスターを作成し、クラスターにデータ ポイントを割り当てる 2 つの方法が用意されています。 1 つ目の K-Means アルゴリズムは、ハード クラスタリングの手法です。 この手法では、データ ポイントが所属できるクラスターは 1 つだけであるため、そのクラスターの各データ ポイントのメンバーシップについて 1 つの確率が計算されます。 2 つ目の Expectation Maximization (EM) 手法は、 ソフト クラスタリング の手法です。 この手法では、データ ポイントが常に複数のクラスターに所属するため、データ ポイントとクラスターの組み合わせごとに確率が計算されます。

どちらのアルゴリズムを使用するかは、 CLUSTERING_METHOD パラメーターを設定して選択できます。 既定のクラスタリング手法はスケーラブル EM です。

EM クラスタリング

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 (予想最大化) クラスタリングを大規模なデータベースにスケーリングする」を参照してください。

K-Means クラスタリング

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

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

K-Means アルゴリズムは、平均への距離を簡単に計算できる連続属性のクラスターの作成に使用されるのが一般的ですが、 ただし、Microsoft の実装では、確率を使用して、個別の属性をクラスター化するために k-means メソッドを調整します。 不連続属性の場合、特定のクラスターからデータ ポイントまでの距離は次のように計算されます。

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 クラスタリング アルゴリズムへの更新

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

注意

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

Microsoft クラスタリング アルゴリズムのカスタマイズ

Microsoft クラスタリング アルゴリズムでは、結果として得られるマイニング モデルの動作、パフォーマンス、精度に影響を与えるいくつかのパラメーターがサポートされています。

アルゴリズム パラメーターの設定

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

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

id メソッド
1 スケーラブル EM
2 非スケーラブル EM (Non-scalable 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 です。

ModelingFlags

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

モデリング フラグ 説明
MODEL_EXISTENCE_ONLY 列が、Missing および Existing の 2 つの可能な状態を持つ列として扱われます。 NULL は Missing 値になります。

マイニング モデル列に適用されます。
NOT NULL 列に NULL を含めることはできません。 モデルのトレーニング中に NULL が検出された場合はエラーが発生します。

マイニング構造列に適用されます。

要件

クラスタリング モデルは、キー列と入力列を含んでいる必要があります。 入力列は、予測可能列として定義することもできます。 Predict Only に設定されている列は、クラスターの作成には使用されません。 クラスター内のそれらの値の分布は、クラスターの作成後に算出されます。

入力列と予測可能列

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

列 コンテンツの種類
入力属性 Continuous、Cyclical、Discrete、Discretized、Key、Table、Ordered
予測可能な属性 Continuous、Cyclical、Discrete、Discretized、Table、Ordered

注意

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

参照

Microsoft クラスタリング アルゴリズム
クラスタリング モデルのクエリ例
クラスター モデルのマイニング モデル コンテンツ (Analysis Services - データ マイニング)