ドキュメンテーション

最新のリリースでは、このページがまだ翻訳されていません。 このページの最新版は英語でご覧になれます。

kmeans

k 平均クラスタリング

構文

  • idx = kmeans(X,k)
  • idx = kmeans(X,k,Name,Value)
  • [idx,C] = kmeans(___)
  • [idx,C,sumd] = kmeans(___)
  • [idx,C,sumd,D] = kmeans(___)

説明

idx = kmeans(X,k)k 平均クラスタリングを実行して n 行 p 列のデータ行列 X の観測を k クラスターに分割し、観測ごとにクラスター インデックスを含む n 行 1 列のベクトル (idx) を返します。X の行は観測に対応し、列は変数に対応します。

既定では、kmeans は二乗ユークリッド距離法および k 平均++ アルゴリズムをクラスター中心の初期化に使用します。

idx = kmeans(X,k,Name,Value) は、1 つ以上の Name,Value のペア引数により指定された追加オプションを使用しクラスター インデックスを返します。

たとえば、コサイン距離、新たな初期値を使用するクラスタリングの反復回数または並列計算の使用回数を指定します。

[idx,C] = kmeans(___) は、kp 列の行列 C の k クラスター重心位置を返します。

[idx,C,sumd] = kmeans(___) は、点と重心間距離のクラスター内合計を k 行 1 列のベクトル sumd で返します。

[idx,C,sumd,D] = kmeans(___) は、各点からすべての重心までの距離を n 行 k 列の行列 D で返します。

すべて折りたたむ

k 平均クラスタリング アルゴリズムの学習

k 平均クラスタリングを使用するクラスター データ。このとき、クラスター領域をプロットします。

フィッシャーのアヤメのデータセットを読み込みます。花弁の長さと幅を予測子として使用します。

load fisheriris
X = meas(:,3:4);

figure;
plot(X(:,1),X(:,2),'k*','MarkerSize',5);
title 'Fisher''s Iris Data';
xlabel 'Petal Lengths (cm)';
ylabel 'Petal Widths (cm)';

クラスターが大きいほど、分散がより低い領域とより高い領域に分割されているようです。つまり、大きなクラスターは、2 つのクラスターがオーバーラップしている可能性があります。

データをクラスタリングします。k = 3 クラスターを指定します。

rng(1); % For reproducibility
[idx,C] = kmeans(X,3);

既定では、kmeans は重心の初期化および 2 乗ユークリッド距離に k 平均++ アルゴリズムを使用します。名前と値のペアの引数 'Replicates' を設定して、より低い局所的最小値を検索することをお勧めします。

idx は、X の観測値に対応する予測クラスター インデックスのベクトルです。C は、最終重心位置を含む 3 行 2 列の行列です。

kmeans を使用して各重心からグリッド上の点までの距離を計算します。これを行うには、重心 (C) およびグリッド上の点を kmeans へ渡し、アルゴリズムの反復を 1 回実行します。

x1 = min(X(:,1)):0.01:max(X(:,1));
x2 = min(X(:,2)):0.01:max(X(:,2));
[x1G,x2G] = meshgrid(x1,x2);
XGrid = [x1G(:),x2G(:)]; % Defines a fine grid on the plot

idx2Region = kmeans(XGrid,3,'MaxIter',1,'Start',C);...
    % Assigns each node in the grid to the closest centroid
Warning: Failed to converge in 1 iterations. 

kmeans は、アルゴリズムが収束しないことを示す警告を表示します。これは、反復が 1 回のみ実行されることから予想できます。

クラスターの領域をプロットします。

figure;
gscatter(XGrid(:,1),XGrid(:,2),idx2Region,...
    [0,0.75,0.75;0.75,0,0.75;0.75,0.75,0],'..');
hold on;
plot(X(:,1),X(:,2),'k*','MarkerSize',5);
title 'Fisher''s Iris Data';
xlabel 'Petal Lengths (cm)';
ylabel 'Petal Widths (cm)';
legend('Region 1','Region 2','Region 3','Data','Location','Best');
hold off;

2 つのクラスターにデータを分割

標本データを無作為に生成します。

rng default; % For reproducibility
X = [randn(100,2)*0.75+ones(100,2);
    randn(100,2)*0.5-ones(100,2)];

figure;
plot(X(:,1),X(:,2),'.');
title 'Randomly Generated Data';

データ内に 2 つのクラスターが存在するように見えます。

データを 2 つのクラスターに分割し、5 つの初期値から最適な割り当てを選択します。最終出力を表示します。

opts = statset('Display','final');
[idx,C] = kmeans(X,2,'Distance','cityblock',...
    'Replicates',5,'Options',opts);
Replicate 1, 4 iterations, total sum of distances = 201.533.
Replicate 2, 6 iterations, total sum of distances = 201.533.
Replicate 3, 4 iterations, total sum of distances = 201.533.
Replicate 4, 4 iterations, total sum of distances = 201.533.
Replicate 5, 3 iterations, total sum of distances = 201.533.
Best total sum of distances = 201.533

既定では、k 平均++ を使用して複製をそれぞれ初期化します。

クラスターとクラスター重心をプロットします。

figure;
plot(X(idx==1,1),X(idx==1,2),'r.','MarkerSize',12)
hold on
plot(X(idx==2,1),X(idx==2,2),'b.','MarkerSize',12)
plot(C(:,1),C(:,2),'kx',...
     'MarkerSize',15,'LineWidth',3)
legend('Cluster 1','Cluster 2','Centroids',...
       'Location','NW')
title 'Cluster Assignments and Centroids'
hold off

idxsilhouetteへ渡すことで、クラスターがどの程度適切に分離されたかを判断できます。

並列計算を使用するクラスター データ

大きなデータセットのクラスタリングでは、特にオンライン更新 (既定で設定されている) を使用すると時間がかかる場合があります。Parallel Computing Toolbox™ ライセンスを保有して、ワーカーのプールを呼び出す場合、kmeans は各クラスタリング タスク (または複製) を並列で実行します。したがって、Replicates > 1 の場合、並列計算により収束の時間が減少します。

混合ガウス モデルから大きなデータセットを無作為に生成します。

Mu = bsxfun(@times,ones(20,30),(1:20)'); % Gaussian mixture mean
rn30 = randn(30,30);
Sigma = rn30'*rn30; % Symmetric and positive-definite covariance
Mdl = gmdistribution(Mu,Sigma);

rng(1); % For reproducibility
X = random(Mdl,10000);

Mdl は、20 成分を含む 30 次元のgmdistribution モデルです。X は、Mdl から生成される 1000030 列のデータ行列です。

ワーカーの並列プールを呼び出します。並列計算のオプションを指定します。

pool = parpool;                      % Invokes workers
stream = RandStream('mlfg6331_64');  % Random number stream
options = statset('UseParallel',1,'UseSubstreams',1,...
    'Streams',stream);
Starting parallel pool (parpool) using the 'local' profile ... connected to 2 workers.

RandStream の入力引数 'mlfg6331_64' は、乗法ラグ フィボナッチ発生器のアルゴリズムの使用を指定します。options は、推定を制御するためのオプションを指定するフィールドを含む構造体配列です。

コマンド ウィンドウは 2 つのワーカーが利用可能であることを示します。ワーカーの数はシステムにより異なる場合があります。

k 平均クラスタリングを使用するデータをクラスター化します。データには k =20 のクラスターがあると指定し、反復回数を増加させます。通常、目的関数には局所的最小値が含まれます。10 個の複製を指定して、より低い局所的最小値の検出に役立てます。

tic; % Start stopwatch timer
[idx,C,sumd,D] = kmeans(X,20,'Options',options,'MaxIter',10000,...
    'Display','final','Replicates',10);
toc % Terminate stopwatch timer
Replicate 4, 121 iterations, total sum of distances = 7.58059e+06.
Replicate 7, 234 iterations, total sum of distances = 7.5904e+06.
Replicate 3, 146 iterations, total sum of distances = 7.59086e+06.
Replicate 2, 179 iterations, total sum of distances = 7.57758e+06.
Replicate 6, 118 iterations, total sum of distances = 7.58614e+06.
Replicate 5, 88 iterations, total sum of distances = 7.59462e+06.
Replicate 1, 99 iterations, total sum of distances = 7.57765e+06.
Replicate 9, 147 iterations, total sum of distances = 7.57639e+06.
Replicate 10, 107 iterations, total sum of distances = 7.60079e+06.
Replicate 8, 144 iterations, total sum of distances = 7.58117e+06.
Best total sum of distances = 7.57639e+06
Elapsed time is 123.857736 seconds.

コマンド ウィンドウは、各複製の反復回数および端末の目的関数の値を表示します。出力引数には複製 9 の結果が含まれます。これは複製が距離の総和の最小値であるためです。

関連する例

入力引数

すべて折りたたむ

X — データ数値行列

データ。数値行列として指定します。X の行は観測値に対応し、列は変数に対応します。

X が数値ベクトルの場合、kmeans はこれを向きに関係なく n 行 1 列のデータ行列として扱います。

データ型: single | double

k — クラスターの数正の整数

データ内のクラスターの数。正の整数として指定します。

データ型: single | double

名前/値のペアの引数

オプションの Name,Value の引数ペアをコンマ区切りで指定します。ここで、Name は引数名で、Value は対応する値です。Name は単一引用符 (' ') で囲まなければなりません。Name1,Value1,...,NameN,ValueN のように、複数の名前と値のペアの引数を任意の順序で指定できます。

例: 'Distance','cosine','Replicates',10,'Options',statset('UseParallel',1) は、コサイン距離、開始値の異なる 10 の複製クラスターおよび並列計算の使用を指定します。

'Display' — 表示する出力レベル'off' (既定値) | 'final' | 'iter'

コマンド ウィンドウで表示する出力レベル。'Display' と文字列で構成されるコンマ区切りのペアとして指定します。以下は使用可能なオプションです。

  • 'final' — 最後の反復の結果の表示

  • 'iter' — 反復の結果の表示

  • 'off' — 表示しない

例: 'Display','final'

データ型: char

'Distance' — 距離測定'sqeuclidean' (既定値) | 'cityblock' | 'cosine' | 'correlation' | 'hamming'

最小化に使用する p 次元空間内の距離測定。'Distance' と文字列で構成されるコンマ区切りのペアとして指定します。

kmeans は、サポートされているさまざまな距離測定に対する重心クラスターをそれぞれ計算します。次の表は、使用可能な距離測定をまとめたものです。式では、x は観測 (つまり X の行)、c は重心 (行ベクトル) です。

距離測定説明
'sqeuclidean'

2 乗ユークリッド距離 (既定の設定)。各重心は、そのクラスターの点の平均です。

d(x,c)=(xc)(xc)

'cityblock'

L1 距離など、絶対差分の合計。各重心は、そのクラスターの点の成分単位の中央値です。

d(x,c)=j=1p|xjcj|

'cosine'

1 から、ベクトルとして扱われる点の間の夾角の余弦を引いた値。各重心は、そのクラスターの点を単位ユークリッド長に正規化した後の平均です。

d(x,c)=1xc(xx)(cc)

'correlation'

1 から、値の系列として扱われる点の間の標本相関を引いた値。各重心は、そのクラスターの点を中心にシフトしてゼロ平均と単位標準偏差に正規化した後の、それらの点の成分単位の平均です。

d(x,c)=1(xx¯)(cc¯)(xx¯)(xx¯)(cc¯)(cc¯),

ここでは以下になります。

  • x¯=1p(j=1pxj)1p

  • c¯=1p(j=1pcj)1p

  • 1p は p 1 の行ベクトルです。

'hamming'

この測定はバイナリ データのにみ適しています。

これは異なるビットの割合です。各重心は、そのクラスターの点の成分単位の中央値です。

d(x,y)=1pj=1pI{xjyj},

ここで I はインジケーター関数です。

例: 'Distance','cityblock'

データ型: char

'EmptyAction' — クラスターがすべてのメンバー観測を失う場合に実行するアクション。'singleton' (既定値) | 'error' | 'drop'

クラスターがすべてのメンバー観測を失う場合に実行するアクション。'EmptyAction' および文字列で構成されるコンマ区切りのペアとして指定します。次の表は、使用できるオプションの一覧です。

説明
'error'

空のクラスターを誤差として処理します。

'drop'

空になったすべてのクラスターを削除します。kmeans は、C および D 内の対応する戻り値を NaN に設定します。

'singleton'

その重心から最も遠くに位置する 1 つの点で構成される新しいクラスターを作成します (既定値)。

例: 'EmptyAction','error'

データ型: char

'MaxIter' — 最大反復回数100 (既定値) | 正の整数

最大反復回数。'MaxIter' と正の整数で構成されるコンマ区切りのペアとして指定します。

例: 'MaxIter',1000

データ型: double | single

'OnlinePhase' — オンライン更新フラグ'on' (既定値) | 'off'

オンライン更新フラグ。'OnlinePhase' および'on' または 'off' のいずれかで構成されるコンマ区切りのペアとして指定します。

OnlinePhaseon の場合 (既定値)、kmeans はバッチ更新フェーズだけでなく、オンライン更新フェーズを実行します。オンライン フェーズは、大規模なデータセットでは時間がかかる場合がありますが、距離基準の局所的最小値になる解が保証されます。つまり、任意の 1 点を他のクラスターに移動すると距離の総和が増大するデータ分割を検出します。

例: 'OnlinePhase','off'

データ型: char

'Options' — 近似基準を最小化する反復アルゴリズムの制御オプション[] (既定値) | statset によって返される構造体配列

近似基準を最小化する反復アルゴリズムの制御オプション。statset により返される 'Options' と構造体配列で構成されるコンマ区切りのペアとして指定します。これらのオプションには Parallel Computing Toolbox™ が必要です。

次の表は、使用できるオプションの一覧です。

オプション説明
'Streams'RandStream オブジェクトまたはそのようなオブジェクトのセル配列。Streams を指定しないと、kmeans には既定のストリームが使用されます。Streams を指定する場合、以下の場合を除き単一オブジェクトを使用します。
  • 開いている並列プールがある

  • UseParalleltrue

  • UseSubstreamsfalse

この場合は、並列プールと同じサイズのセル配列を使用します。並列プールが開いていない場合、Streams は単一の乱数ストリームを提供しなければなりません。

'UseParallel'
  • trueReplicates > 1 の場合および Parallel Computing Toolbox のワーカーの並列プールが開いている場合、それぞれの複製に k 平均が実行されます。

  • Parallel Computing Toolbox がインストールされていないか、ワーカーの並列プールが開いていない場合、計算は逐次モードで行われます。既定の設定は default (逐次計算) です。

'UseSubstreams'再生成可能な方法で並列計算する場合に true に設定します。既定値は false です。再現性のある計算を行うには、Streams をサブストリームを許可する型、'mlfg6331_64' または 'mrg32k3a' に設定します。

予測結果をより確実にするために、parpool を使用し、並列プールを明示的に作成してから kmeans を呼び出し 'Options',statset('UseParallel',1) を設定します。

例: 'Options',statset('UseParallel',1)

データ型: struct

'Replicates' — 新規の初期クラスター重心位置を使用するクラスタリングの反復回数1 (既定値) | 正の整数

新規の初期クラスター重心位置を使用するクラスタリングの反復回数。'Replicates' と整数で構成されるコンマ区切りのペアとして指定します。kmeans は最低の sumd をもつ解を返します。

3-D 配列を名前と値のペアの引数 'Start' の値として指定することで、'Replicates' を暗黙的に設定できます。

例: 'Replicates',5

データ型: double | single

'Start' — 初期クラスター重心位置を選択する方法'plus' (既定値) | 'cluster' | 'sample' | 'uniform' | 数値行列 | 数値配列

初期クラスター重心位置 (または "シード") を選択する方法。'Start' と文字列、数値行列または数値配列で構成されるコンマ区切りのペアとして指定します。次の表は、シードの選択に使用可能なオプションをまとめています。

説明
'cluster'X の無作為な 10% 副標本で予備クラスタリング フェーズを実行します。この予備フェーズは 'sample' を使用して初期化されます。
'plus' (既定の設定)クラスター中心の初期化に k 平均++ アルゴリズムを実装して k シードを選択します。
'sample'k 観測値を X から無作為に選択します。
'uniform'k 点を一様に無作為に X の範囲から選択します。ハミング距離には無効です。
数値行列k 行 p 列の行列の重心開始位置。Start の行はシードに対応します。Start の最初の次元から k が推測されるので、k に対して [] を渡すことができます。
数値配列k 行 p-r 列重心開始位置の配列各ページの行はシードに対応します。3 番目の次元がクラスタリング ルーチンの複製を呼び出します。ページ j には複製 j のシードのセットが含まれています。3 番目次元の大きさから複製 (名前と値のペアの引数 'Replicates' により指定される) の数が推測されます。

例: 'Start','sample'

データ型: char | double | single

    メモ:   NaN は欠損データとして扱われ、最低 1 つの NaN を含む X の任意の行を削除します。X の行を削除することで標本サイズが減少します。

出力引数

すべて折りたたむ

idx — クラスター インデックス数値列ベクトル

クラスター インデックス。数値列ベクトルとして返されます。idx には X と同数の行があり、各行は対応する観測のクラスター割り当てを示します。

C — クラスター重心位置数値行列

クラスター重心位置。数値行列として返します。Ck 行 p 列の行列です。ここで、行 j はクラスター j の重心です。

sumd — 点と重心間の距離のクラスター内合計数値列ベクトル

クラスター内での点から重心までの距離の合計。数値行ベクトルとして返されます。sumdk 行 1 列のベクトルです。ここで要素 j はクラスター j 内の点と重心までの距離の合計です。

D — 各点からすべての重心までの距離数値行列

各点からそれぞれの重心までの距離。数値行列として返されます。D は n 行 k 列の行列です。ここで、要素 (j、m) は観測 j から重心 m までの距離です。

詳細

すべて折りたたむ

k 平均クラスタリング

"k 平均クラスタリング" つまり、ロイドのアルゴリズム [2] は、データを分割する反復アルゴリズムであり、重心によって定義された 1 つの k クラスターに観測値 n を割り当てます。ここで、アルゴリズムを開始する前に k を選択します。

アルゴリズムは、以下のように実行されます。

  1. k 初期クラスター中心 ("重心") を選択します。たとえば、観測 k を ('Start','sample' を使用して) 無作為に選択するか、クラスター中心の初期化 (既定の設定) にk 平均++ アルゴリズムを使用します。

  2. すべての観測について各重心までの点とクラスター重心間の距離を計算します。

  3. 続行するには、以下の 2 つの方法があります (OnlinePhase により指定)。

    • バッチの更新 ― 各観測を最も重心の近いクラスターに割り当てる。

    • オンライン更新 ― 再割り当てによりクラスター内合計、点とクラスター重心間の距離が減少する場合、観測を異なる重心に個別に割り当てる。

    詳細は、アルゴリズムを参照してください。

  4. 各クラスター内の観測の平均を計算し、新規の重心位置 k を取得します。

  5. クラスター割り当ての変化がなくなるか、反復回数が最大になるまで、手順 2 から 4 を繰り返します。

k 平均++ アルゴリズム

k"平均++ アルゴリズム" は、経験則を使用して k 平均クラスタリングの重心シードを検出します。Arthur および Vassilvitskii [1] によると、k 平均++ はロイドのアルゴリズムの実行時間および最終的な解の質を改善します。

k 平均++ アルゴリズムは以下のようにシードを選択し、クラスターの数を k と仮定します。

  1. 観測を一様に無作為にデータセット X から選択します。選択された観測値は最初の重心であり、c1 で示されます。

  2. 各観測から c1 までの距離を計算します。距離の観測 m は cj d(xm,cj) から派生していると示します。

  3. 次の重心 c2 を X から次の確率で無作為に選択します。

    d2(xm,c1)j=1nd2(xj,c1).

  4. 中心 j を選択するには、以下を行います。

    1. 各観測から各重心までの距離を計算します。各観測を最も近い重心に割り当てます。

    2. m = 1,...,n および p = 1,...,j – 1 の場合、重心 j を X から次の確率で無作為に選択します。

      d2(xm,cp){h;xhCp}d2(xh,cp),

      ここで Cp は重心 cp に最も近い観測すべての集合で、xm は Cp に属します。

      つまり、それぞれの中心を続けて選択するには、それ自体から、既に選択された、最も近い中心までの距離に比例する確率になります。

  5. k 重心が選択されるまでステップ 4 を繰り返します。

Arthur と Vassilvitskii [1] の実証によると、k 平均++ は複数のクラスターの方向へのシミュレーション分析を使用して、ロイドのアルゴリズムよりも、低いクラスター内の合計と、点とクラスター重心間の距離の二乗和への収束をより迅速に達成します。

アルゴリズム

  • kmeans は、2 つのフェーズの反復アルゴリズムを使用して、すべての k クラスターにわたって合計される点と重心間距離の総計を最小化します。

    1. この最初のフェーズでは、"バッチ更新" を使用します。この更新の反復では、最も近いクラスター重心に点を一度に再割り当てした後、クラスター重心を計算し直します。このフェーズでは、局所的最小値となる解に収束されないこともあります。つまり、1 つの点を他のクラスターに移動するデータ分割がと距離の総和を増大させます。これは、規模の小さなデータセットでよく発生します。バッチ フェーズは高速ですが、2 番目のフェーズの開始点となる解だけが概算される可能性があります。

    2. 2 番目のフェーズでは、"オンライン更新" を使用します。この更新では、点を個別に再割り当てし、再割り当てすることで距離の合計が減少する場合は、各再割り当ての後にクラスター重心を再計算します。このフェーズでの各反復は、すべての点を経過する 1 つの引き渡しで構成されます。このフェーズは局所的最小値に収束されます。ただし、距離の総和がより低い局所的最小値が他にある可能性もあります。一般に大域的最小値の検出は、開始点を網羅的に選択することで解決します。しかし、通常は無作為な開始点をもつ複製を複数使用すると、結果的に解は大域的最小値になります。

  • Replicates = r > 1 および Startplus (既定値) の場合、k 平均++ アルゴリズムに従って、さまざまなシードの集合 r が選択される可能性もあります。

  • OptionsUseParallel および Replicates > 1 を有効にした場合、各ワーカーはシードとクラスターを並列で選択します。

参照

[1] Arthur, David, and Sergi Vassilvitskii. “K-means++: The Advantages of Careful Seeding.” SODA ‘07: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms. 2007, pp. 1027–1035.

[2] Lloyd, Stuart P. “Least Squares Quantization in PCM.” IEEE Transactions on Information Theory. Vol. 28, 1982, pp. 129–137.

[3] Seber, G. A. F. Multivariate Observations. Hoboken, NJ: John Wiley & Sons, Inc., 1984.

[4] Spath, H. Cluster Dissection and Analysis: Theory, FORTRAN Programs, Examples. Translated by J. Goldschmidt. New York: Halsted Press, 1985.

この情報は役に立ちましたか?