次の方法で共有

  • [アーティクル]

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 (Expectation Maximization) クラスタリングの大規模データベースへのスケーリング」を参照してください。

K-Means クラスタリング

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 ケースを使用してデータに適合するモデルを作成できなかった場合にのみ追加のケースが読み取られます。

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

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 です。

モデリング フラグ

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

モデリング フラグ

説明

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 はサポートされますが、アルゴリズムはこれらを不連続の値として扱い、特別な処理は行いません。