K-Means Clusteringとは何か？

K-means clusteringは、無教師学習アルゴリズムであり、無教師学習アルゴリズムの中で、K-means clusteringは最も広く使用されている可能性があります。これは、その力とシンプルさによるものです。K-means clusteringは、どのようにして機能するのでしょうか？

簡単な答えは、K-means clusteringは、望ましい数のクラスの参照点（セントロイド）を作成し、次にデータポイントを、どの参照点に最も近いかに基づいてクラスタに割り当てることで機能するということです。K-means clusteringの簡単な定義ですが、K-means clusteringについてより深く理解するために、詳しく見てみましょう。

クラスタリングの定義

K-means clusteringを実行するために使用される正確なアルゴリズムを調べる前に、クラスタリング全般について定義してみましょう。

クラスターは、単にアイテムのグループであり、クラスタリングは、アイテムをこれらのグループに配置することです。データサイエンスの意味では、クラスタリングアルゴリズムは、2つのことを行うことを目的としています：

• クラスター内のすべてのデータポイントが可能な限り互いに似ていることを保証します。
• 異なるクラスター内のすべてのデータポイントが可能な限り互いに異なることを保証します。

クラスタリングアルゴリズムは、類似性の尺度に基づいてアイテムをグループ化します。これは、データセット内のさまざまなグループの「セントロイド」を見つけることで行われることが多いですが、独自に行われるわけではありません。さまざまなクラスタリングアルゴリズムがありますが、すべてのクラスタリングアルゴリズムの目的は、データセットに固有のグループを決定することです。

K-Means Clustering

K-Means Clusteringは、最も古くからあるクラスタリングアルゴリズムの1つであり、ベクトル量子化に基づいて動作します。空間上に原点として選択された点があり、そこからデータセット内のすべてのデータポイントにベクトルが描かれます。

一般に、K-means clusteringは、5つの異なるステップに分解できます：

• すべてのインスタンスをサブセットに配置します。サブセットの数はKに等しくなります。
• 新しく作成されたクラスタパーティションの平均点/セントロイドを見つけます。
• これらのセントロイドに基づいて、各ポイントを特定のクラスタに割り当てます。
• すべてのポイントからセントロイドまでの距離を計算し、ポイントをセントロイドからの距離が最小のクラスタに割り当てます。
• ポイントがクラスタに割り当てられた後、クラスタの新しいセントロイドを見つけます。

上記のステップは、トレーニングプロセスが完了するまで繰り返されます。

初期段階では、セントロイドはデータポイントのどこかに配置されます。
Photo: Weston.pace via wikimedia commons, GNU Free Documentation License (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_1.svg)

あるいは、セントロイドが配置された後、K-means clusteringを、ラベル付けとセントロイドの更新の2つの異なるフェーズの間で交互に切り替えることができます。

2番目のステップでは、ユークリッド距離などの距離尺度を使用して、与えられたポイントがどのセントロイドに最も近いかを計算し、ポイントをそのセントロイドのクラスに割り当てます。 Photo: Weston.pace via Wikimedia Commons, GNU Free Doc License (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_2.svg)

データポイントのラベル付け段階では、各データポイントに、最も近いセントロイドに属するクラスタを指定するラベルが割り当てられます。最も近いセントロイドは、通常、ユークリッド距離の2乗を使用して決定されますが、データに応じて、Manhattan距離、Cosine距離、Jaccard距離などの他の距離尺度を使用することもできます。

3番目のステップでは、セントロイドが、クラスタ内にあるすべてのデータポイントの平均距離で計算されます。クラスは再割り当てされます。 Photo: Weston.pace via Wikiemedia Commons, CC SA 3.0 (https://commons.wikimedia.org/wiki/File:K_Means_Example_Step_3.svg)

セントロイドの更新段階では、セントロイドは、クラスタ内にあるすべてのデータポイントの平均距離で計算されます。

「K」の適切な値を選択する方法

K-means clusteringは無教師学習アルゴリズムであり、クラスの数は事前にわかっていないため、「K」の適切な値を決定するにはどうすればよいのでしょうか？

「K」の適切な値を選択するための1つのテクニックは、「肘法」と呼ばれます。肘法では、さまざまな「K」値に対してK-means clusteringアルゴリズムを実行し、通常はSum of Squared Error (SSE)という精度尺度を使用して、どの「K」値が最も良い結果をもたらすかを判断します。SSEは、クラスタのセントロイドとクラスタ内のデータポイントの平均距離を計算することで決定されます。

「肘法」という用語は、SSEを「K」値の関数としてプロットすると、線プロットが「K」値の最初のいくつかの値に対して急激に減少するが、その後平坦になる「肘」のような形状になるためにつけられた名前です。このような場合、「K」の値は「肘」に位置するものが最適であり、そこ以降の値では急激に減少する利点が得られないためです。

ミニバッチK-Means Clustering

データセットが大きくなるにつれて、計算時間も増加します。基本的なK-means clusteringは、巨大なデータセットで実行すると、完了するまでに長い時間がかかる可能性があります。したがって、K-means clusteringの空間的および時間的コストを削減できるように、K-means clusteringの改良版が開発されています。

ミニバッチK-means clusteringは、K-means clusteringのバリエーションであり、考慮されるデータセットのサイズが制限されています。通常のK-means clusteringは、バッチ全体/データセット全体で動作しますが、ミニバッチK-means clusteringは、データセットをサブセットに分割します。ミニバッチは、データセット全体からランダムにサンプリングされ、各新しいイテレーションのために新しいランダムサンプルが選択され、セントロイドの位置を更新するために使用されます。

ミニバッチK-Meansクラスタリングでは、クラスターはミニバッチ値と学習率の組み合わせで更新されます。学習率は、イテレーションごとに減少します。学習率は、特定のクラスタに配置されるデータポイントの数の逆数です。学習率を減少させることで、新しいデータの影響が減り、クラスターに変更がない場合に収束が達成されます。

ミニバッチK-Meansクラスタリングの有効性に関する研究の結果は、クラスターの品質に若干のトレードオフがあるものの、計算時間を大幅に削減できることを示しています。

K-Means Clusteringの応用

K-means clusteringは、データポイントを明確なグループ/クラスにセグメント化できる状況で安全に使用できます。K-means clusteringの一般的なユースケースの例を以下に示します。

K-means clusteringは、トピック、タグ、単語の使用、メタデータなどのドキュメントの特徴に基づいてドキュメントをグループ化するために使用できます。K-means clusteringは、投稿やコメントなどの活動パターンに基づいて、ユーザーをボットまたはボット以外のユーザーに分類するために使用できます。K-means clusteringは、合併症、年齢、患者の歴史などの特徴に基づいて、人々をグループに分けるために使用できます。

K-means clusteringは、レコメンデーションシステムの作成などのよりオープンなタスクにも使用できます。Netflixのようなシステムのユーザーは、視聴パターンに基づいてグループ化され、類似のコンテンツを推奨できます。K-means clusteringは、不正または不良アイテムの潜在的なインスタンスを強調する、異常検出タスクに使用できます。