ビッグデータの機械理解の秘密：クラスタリングアルゴリズムの詳細な説明

クラスタリングは、ビッグデータを理解する上で非常に一般的かつ基本的な方法です。最近、データ サイエンティスト兼プログラマーの Peter Gleeson 氏が freeCodeCamp で詳細な記事を公開しました。この記事では、いくつかのクラスタリング アルゴリズムの基本的な紹介と、シンプルでありながら詳細な例を通じてその動作プロセスについて説明しています。

下の写真を見てください。いろいろな虫やカタツムリがいます。それらをグループに分類してみませんか？

そんなに難しくないので、まずはクモを見つけることから始めましょう！

終わりましたか？必ずしも「正しい答え」があるわけではありませんが、一般的に言えば、これらの虫はクモ、カタツムリ、蝶/蛾、ハチ/スズメバチの 4 つのグループに分けられます。

簡単ですよね？虫が2倍いても違いがわかりますよね？必要なのは、少しの時間と昆虫学への情熱だけです。何万匹いても虫の違いがわかります。

しかし、これら 10 個のオブジェクトを意味のあるグループに分類することは、機械にとって容易ではありません。組合せ論と呼ばれる数学の分野の助けを借りれば、これら 10 個のバグをグループ化する方法は 115,975 通りあることがわかります。バグの数が 20 に増えると、それらをグループ化する方法は 50 兆通り以上になります。バグの数が 100 に達すると、可能な解決策の数は既知の宇宙の粒子の数を超えます。あとどれくらい？私の計算によると、約500,000,000,000,000,000,000,000,000,000,000,000,000,000,000倍となり、想像を絶する天文学的な数字です！

しかし、これらのグループ化スキームのほとんどは意味がなく、膨大な数のグループ化オプションの中で、バグをグループ化する便利な方法はほんのわずかしか見つかりません。

そして、私たち人間はそれを素早く行うことができ、大量のデータを素早くグループ化して理解する能力を当然のことと考える傾向があります。テキスト、画面上の画像、または一連のオブジェクトなど、人間は一般に、提示されたデータを理解するのが非常に得意です。

人工知能と機械学習の鍵は大量の入力データを素早く理解することであることを考えると、これらのテクノロジーを開発するための近道は何でしょうか? この記事では、マシンが大量のデータセットを素早く理解するために使用できる 3 つのクラスタリング アルゴリズムについて説明します。もちろん、他にもアルゴリズムはありますが、これが良いスタートになることを願っています。

この記事では、各クラスタリング アルゴリズムの概要、その仕組みの簡単な紹介、およびより詳細なステップバイステップの実装例を紹介します。これはこれらのアルゴリズムを理解するのに役立つと思います。

3 つのきれいなクラスター、K=3

1. K平均法クラスタリング

1. いつ使うのですか?

どのくらいのグループが見つかるか事前にわかっている場合はどうしますか?

2. 作業方法

アルゴリズムは、各観測値を k 個のクラスのいずれかにランダムに割り当て、各クラスの平均を計算します。次に、各観測値を最も近い平均値を持つカテゴリに再割り当てし、その平均値を再計算します。この手順は、新しい割り当てが必要なくなるまで繰り返されます。

3. 効果的な事例

9 人のサッカー選手のグループがあり、各選手が今シーズンに一定数のゴール (3 ～ 30 とします) を獲得しているとします。次に、それらをグループに分けます（たとえば、3 つのグループ）。

最初のステップでは、アスリートをランダムに 3 つのグループに分け、各グループの平均を計算する必要があります。

グループ1

• プレーヤーA（5ゴール）、プレーヤーB（20ゴール）、プレーヤーC（11ゴール）
• グループ平均 = (5 + 20 + 11) / 3 = 12

グループ2

• 選手D（5ゴール）、選手E（9ゴール）、選手F（19ゴール）
• グループ平均 = 11

グループ3

• プレーヤー G (30 ゴール)、プレーヤー H (3 ゴール)、プレーヤー I (15 ゴール)
• グループの平均 = 16

ステップ 2: 各プレーヤーを、スコアが平均値に最も近いグループに再割り当てします。たとえば、プレーヤー A (5 ゴール) はグループ 2 (平均値 = 11) に再割り当てされます。次に、新しい平均を計算します。

グループ 1 (元の平均 = 12)

• 選手C（11ゴール）、選手E（9ゴール）
• 新しい平均 = (11 + 9) / 2 = 10

グループ2（元の平均 = 11）

• 選手A（5ゴール）、選手D（5ゴール）、選手H（3ゴール）
• 新しい平均 = 4.33

グループ3（元の平均 = 16）

• プレーヤー B (20 ゴール)、プレーヤー F (19 ゴール)、プレーヤー G (30 ゴール)、プレーヤー I (15 ゴール)
• 新しい平均 = 21

各グループの平均が変化しなくなるまで、2 番目の手順を繰り返します。この単純なタスクでは、次の反復で目標が達成されます。これで完了です。元のデータセットから 3 つのクラスターを取得しました。

グループ 1 (元の平均 = 10)

• プレーヤー C (11 ゴール)、プレーヤー E (9 ゴール)、プレーヤー I (15 ゴール)
• 最終平均 = 11.3

グループ2（元の平均 = 4.33）

• 選手A（5ゴール）、選手D（5ゴール）、選手H（3ゴール）
• 最終平均 = 4.33

グループ3（元の平均 = 21）

• 選手B（20ゴール）、選手F（19ゴール）、選手G（30ゴール）、
• 最終平均 = 23

この例では、クラスターは、ディフェンス、ミッドフィールド、オフェンスなど、フィールド上のプレーヤーの位置に対応する可能性があります。データが自然にこれら 3 つのグループに分類されることが合理的に予測できるため、ここで K 平均法が機能します。

このように、パフォーマンス統計のセットが与えられれば、マシンはどのサッカーチームでも選手のポジションをかなり正確に推定できるようになります。これはスポーツ分析に役立つだけでなく、データセットを定義済みのグループに分類するその他の分類タスクにも役立ちます。

4. より微妙な詳細:

上記のアルゴリズムにはいくつかのバリエーションがあります。最初の「シード」クラスタリングはさまざまな方法で実行できます。ここでは、各アスリートをランダムにグループに分け、グループの平均を計算しました。これにより、初期平均値が互いに近くなる可能性が高くなり、後のステップ数が増加します。

シード クラスターを選択する別の方法は、グループごとに 1 人のアスリートのみを設定し、最も近いグループに他のアスリートを割り当てることです。この方法で返されるクラスターは、より敏感な初期シードであるため、変動の大きいデータセットでの繰り返しが減少します。ただし、このアプローチでは、グループの収束にかかる時間が短くなるため、アルゴリズムを完了するために必要な反復回数を削減できる可能性があります。

K-means クラスタリングの明らかな制限は、予想されるクラスターの数について事前に仮定を与える必要があることです。特定のクラスターの適合性を評価する方法もあります。たとえば、クラスター内二乗和は各クラスター内の分散を測定します。クラスタリングが優れているほど、全体的な WCSS は低くなります。

2. 階層的クラスタリング

1. いつ使うのですか?

観測されたデータの潜在的な関係性をさらに調査したい場合は、階層的クラスタリング アルゴリズムを使用できます。

2. 作業方法

まず距離行列を計算します。行列の要素 (i, j) は観測値 i と j 間の距離の尺度を表します。次に、最も近い 2 つの観測値がペアにグループ化され、その平均が計算されます。観測値のペアを 1 つのオブジェクトに結合することで、新しい距離行列を生成します。具体的なマージ プロセスでは、最も近い観測値の各ペアの平均を計算し、すべての観測値がマージされるまで新しい距離マトリックスを入力します。

3. 有効なケース：

以下は、クジラやイルカの種を分類するための非常にシンプルなデータセットです。生物学者として訓練を受けた私としては、通常、より詳細なデータセットを使用してシステムを構築することを保証できます。ここで、これら 6 種の典型的な体長を見てみましょう。この場合、2 回の繰り返し手順を使用します。

ステップ 1: それぞれの種間の距離行列を計算します。この場合、データ ポイント間の距離であるユークリッド距離が使用されます。道路地図上の距離グラフを見るのと同じように距離を計算できます。関連する行と列の交点の値を調べることで、任意の 2 つの種の長さの違いを調べることができます。

ステップ 2: 最も近い 2 つの種 (この場合は、平均体長が 3.3 m のバンドウイルカとオオフラミイルカ) を選択します。手順 1 を繰り返して距離行列を再度計算しますが、今回はバンドウイルカとオオルリカを平均体長 3.3 m に置き換えます。

次に、新しい距離行列を使用して手順 2 を繰り返します。現在、最も近いのはゴンドウクジラとシャチなので、それらの平均体長（7.0m）を計算し、それを新しい用語に統合します。

次に、手順 1 を繰り返して距離行列を再度計算します。ただし、今回はゴンドウクジラとシャチを 1 つの項目に結合し、長さを 7.0 m に設定します。

現在の距離行列を使用して手順 2 を再度繰り返します。すでに結合されている 2 つの用語の間には最も近い距離 (3.7 m) が出現し、ここでこれらの 2 つの用語をより大きな用語 (平均 5.2 m) に結合します。

次に、手順 2 をもう一度繰り返します。ザトウクジラとナガスクジラには最小距離 (5.0m) が出現するため、引き続きこれらを 1 つの項目にマージし、平均 (17.5m) を計算します。

手順 1 に戻り、ザトウクジラとナガスクジラが 1 つの項目に統合された新しい距離行列を計算します。

最後に、手順 2 を繰り返すと、距離行列には 1 つの値 (12.3m) のみが存在し、それらすべてが 1 つの項に結合され、このループを停止できます。まずは最終的なマージを見てみましょう。

これで、ツリー図として描画できるネストされた構造 (JSON を参照) ができました。家系図と同じように読みます。樹形図では、2 つの観測値が近いほど、それらの類似性が高く、関連が深いことを示します。

R-Fiddle.org で生成された樹形図

ツリー図の構造を通じて、データ セットの構造をより深く理解することができます。上記の場合、2 つのメイン ブランチがあり、1 つは HW と FW、もう 1 つは BD、RD、PW、KW です。

進化生物学では、より多くの種と測定値を含む大規模なデータセットが、これらの種間の分類上の関係を推測するためによく使用されます。生物学以外では、階層的クラスタリングは機械学習やデータマイニングでも使用されます。

重要なのは、この方法を使用する場合、K 平均法クラスタリングのようにグループ数を設定する必要がないことです。指定された高さでツリーを「カット」して、結果のクラスターを返すことができます。高さの選択は、データをクラスタ化する解像度に応じて、いくつかの方法で行うことができます。

たとえば、上の図で高さ 10 の線を引くと、2 つのメイン ブランチが 2 つのサブグラフに分割されます。高さ 2 で分割すると、3 つのクラスターが生成されます。

4. 詳細:

ここで紹介する階層的クラスタリング アルゴリズムには 3 つの異なる側面があります。

最も基本的なアプローチは、私たちが使用する凝集プロセスです。このプロセスでは、単一のデータ ポイントから反復処理を行い、大きなクラスターが出現するまでデータ ポイントを集約します。もう 1 つの (より計算集約的な) アプローチは、巨大なクラスターから始めて、独立したデータ ポイントになるまでデータを小さなクラスターに分割することです。

距離行列を計算する方法はいくつかあります。多くの場合、ユークリッド距離 (ピタゴラスの定理を参照) で十分ですが、特殊な状況ではより適した代替方法もあります。

最後に、リンク基準も変更できます。クラスターは異なる距離に基づいて接続されますが、「近い」を定義する方法は柔軟です。上記の例では、各クラスターの平均 (つまり、重心) 間の距離を測定し、最も近いクラスターとペアにしました。しかし、別の定義を使用したい場合もあるでしょう。

たとえば、各クラスターは複数の個別のポイントで構成されます。下の図に示すように、2 つのクラスター間の距離は、任意のポイント間の最小 (または最大) 距離として定義できます。さまざまなシナリオに適した接続基準を定義する他の方法もあります。

赤/青: 重心接続、赤/緑: 最小接続、緑/青: 最大接続

3. グラフコミュニティ検出

1. いつ使うのですか?

データをネットワークまたはグラフとして表現できる場合。

2. 作業方法

グラフ コミュニティは通常、ネットワークの残りの部分よりも密に接続された頂点のサブセットとして定義されます。より具体的な定義に基づいてグラフを識別するためのアルゴリズムは多数あり、その中には、エッジの媒介性、モジュール性の最大化、ウォークトラップ、クリーク浸透、主要固有ベクトルなどがあります (ただし、これらに限定されません)。

3. 効果的な事例

グラフ理論は、ネットワークを研究する数学の分野です。Machine Heart の記事「確率的グラフィカル モデルを理解したいですか? まずグラフ理論の基本的な定義と形式を理解する必要があります」を参照してください。グラフ理論を使用すると、複雑なシステムを「頂点」と「辺」の抽象的な集合としてモデル化できます。

おそらく最も直感的な例はソーシャル ネットワーキングです。頂点は人を表し、頂点を結ぶ辺は友達やフォローし合っているユーザーであることを表します。

ただし、システムをネットワークとしてモデル化するには、さまざまなコンポーネントを効果的に接続する方法を見つける必要があります。グラフ理論のクラスタリングへの革新的な応用としては、画像データからの特徴抽出や遺伝子制御ネットワークの分析などが挙げられます。

これは、私が最近訪問した 8 つの Web サイトを Wikipedia ページのリンクで接続して示す、シンプルでわかりやすいグラフです。このデータは手動でプロットできるほど単純ですが、大規模なプロジェクトの場合は Python スクリプトを記述する方が早いかもしれません。私が書いたものは次のとおりです。

https://raw.githubusercontent.com/pg0408/Medium-articles/master/graph_maker.py

R バージョン 3.3.3 の igraph を使用して描画されたグラフ

これらの頂点の色はグループの関係を示し、サイズは中心性によって決まります。 GoogleとTwitterが最も中心的であることがわかりますよね？

さらに、これらのクラスターは現実世界でも意味を持ちます (常に重要なパフォーマンス指標です)。黄色の頂点は通常、参照/検索サイトであり、青色の頂点はすべてオンライン公開サイト (記事、ツイート、またはコード) であり、オレンジ色の頂点は YouTube と PayPal です (YouTube は元 PayPal 従業員によって設立されたためです)。マシンはかなり良いです！

大規模なシステムを視覚化する便利な方法であることに加えて、ネットワークの真の力は数学的に分析できる能力にあります。上の図のネットワークをより数学的な形に変換してみましょう。以下はネットワークの隣接行列です。

各行と列の交点の値は、対応する頂点のペア間にエッジがあるかどうかを示します。たとえば、Medium と Twitter の間にはエッジがあるため、行と列の交点は 1 になります。同様に、Medium と PayPal の間にもエッジはないため、行と列の交差は 0 になります。

隣接行列はネットワークのすべての特性をエンコードします。これは、貴重な洞察の可能性をすべて解き放つ鍵を与えてくれます。まず、各行または各列の数字を合計すると、各頂点の次数、つまり、その頂点が接続されている他の頂点の数が得られます。この数値は通常、文字 k で表されます。同様に、各頂点の次数を 2 で割ると、リンクとも呼ばれる辺の数が得られ、L で表されます。行/列の数は、ネットワーク内のノードと呼ばれる頂点の数であり、N で表されます。

k、L、N、および隣接行列 A 内の各セルの値のみを知ることで、ネットワークの任意のクラスタリングのモジュール性を計算できます。

ネットワークをグループにクラスタ化していると仮定します。このモジュール性スコアを使用して、このクラスタリングの品質を評価できます。スコアが高いほど、ネットワークが「正確な」グループに分割されていることを意味し、スコアが低いほど、クラスタリングがランダムに近いことを意味します。次の図に示すように:

モジュール性はパーティションの「品質」を測る尺度です。

モジュール性は次の式を使用して計算できます。

式は少し複雑ですが、理解しやすいように分解してみましょう。

M は計算したいモジュール性です。

1/2L は、後半部分を 2L で割ることを意味します。2L は、ネットワーク内のエッジの数の 2 倍です。

Σ 記号は合計を表し、隣接行列 A の各行と列に対して反復されます。この表記法に慣れていない場合は、i、j = 1、N をプログラミング言語の for ループとして考えてください。 Python では、次のように記述できます。

コード内の i と j を含む #stuff とは何ですか?

括弧内の内容は、A_ijから(k_i k_j)/2Lを減算することを意味します。

A_ij は隣接行列の i 行目と j 列目の値を参照します。

k_i と k_j は各頂点の次数です。各行と列のエントリを合計することで求められます。これら 2 つの積を 2L で割ると、ネットワークがランダムに割り当てられた場合の頂点 i と j 間のエッジの予想数が得られます。

全体として、括弧内の項は、ネットワークの実際の構造と、ランダムに組み立てられた場合に予想される構造との差を表します。その値を調べてみると、A_ij = 1 かつ ( k_i k_j ) / 2L が非常に小さいときに、返される値が最大になることがわかります。つまり、頂点 i と j の間に「予期しない」エッジがある場合、取得される値は高くなります。

最後に、括弧内の項にδc_i、c_jを掛けます。 δc_i、c_j は有名ですが、ほとんど無害なクロネッカーデルタ関数です。 Python での説明は次のとおりです。

はい、とても簡単です。クロネッカーのデルタ関数は 2 つの引数を取り、引数が等しい場合は 1 を返し、等しくない場合は 0 を返します。

つまり、頂点 i と j が同じクラスターに配置されている場合は、δc_i、c_j = 1 になります。それ以外の場合は、同じクラスターには配置されていないため、関数は 0 を返します。

括弧内の項にクロネッカーのデルタ関数を掛けると、ネストされた合計 Σ については、同じクラスターに割り当てられている頂点を接続する「予期しない」エッジが多数ある場合に結果が最も高くなることがわかります。したがって、モジュール性は、グラフをどの程度適切に個別のグループにクラスタ化できるかを測る指標です。

2L で割ると、モジュール性の上限は 1 に設定されます。モジュール性が 0 に近いか 0 未満の場合、ネットワークの現在のクラスタリングは役に立たないことを示します。モジュール性が高くなるほど、ネットワークはさまざまなグループに適切にクラスター化されます。モジュール性を最大限に高めることで、ネットワークをクラスタ化する最適な方法を見つけることができます。

クラスタリングがどの程度優れているかを評価する方法を見つける前に、グラフがどのようにクラスタリングされるかを事前に定義する必要があることに注意してください。残念ながら、あらゆるクラスタリングを試してモジュール性スコアが最も高いものを見つけるという力ずくのアプローチは計算量が多く、有限のサンプル サイズでも不可能です。

組合せ論によれば、頂点が 8 個しかないネットワークの場合、クラスタリングには 4140 通りの方法があることがわかります。 16 個の頂点を持つネットワークをクラスター化する方法には 100 億通り以上あります。 32 個の頂点を持つネットワークは、128 セプティリオン (10^21) 以上の方法でクラスター化できます。ネットワークに 80 個の頂点がある場合、クラスター化できる方法の数は、観測可能な宇宙の原子の数を超えます。

したがって、あらゆる可能性を試すことなく、最高のモジュール性スコアを生成するクラスタリングを評価するのに適したヒューリスティックな方法に頼る必要があります。これは、Fast-Greedy Modularity-Maximization と呼ばれるアルゴリズムで、上で説明した凝集型階層クラスタリング アルゴリズムに多少似ています。ただし、Mod-Max は距離に基づいてグループを結合するのではなく、モジュール性の変更に基づいてグループを結合します。

仕組みは次のとおりです:

まず最初に各頂点を独自のコミュニティに割り当て、次にネットワーク全体のモジュール性 M を計算します。

ステップ 1 では、各コミュニティ ペアが少なくとも 1 つの単一エッジでリンクされている必要があります。2 つのコミュニティがマージされると、アルゴリズムは結果として生じるモジュール性の変化 ΔM を計算します。

2 番目のステップは、ΔM の増加が最も大きいグループ ペアを取得して、それらをマージすることです。次に、このクラスターの新しいモジュール性 M を計算して記録します。

手順 1 と 2 を繰り返し、そのたびに ΔM の最大ゲインをもたらすコミュニティのペアを融合し、新しいクラスタリング パターンとそれに対応するモジュール性スコア M を記録します。

すべての頂点が 1 つの巨大なクラスターにグループ化されたら、停止できます。次に、アルゴリズムはこのプロセスでレコードを調べ、最高の M 値を返すクラスタリング パターンを見つけます。これは返されるグループ構造です。

4. 詳細:

すごい！少なくとも人間にとっては、かなりの計算量ですね。グラフ理論は、計算上困難な問題、多くの場合 NP 困難な問題を多く提示しますが、複雑なシステムやデータセットに対する貴重な洞察を提供する大きな可能性も秘めています。ラリー・ペイジはこれを理解しており、彼の有名な PageRank アルゴリズムは完全にグラフ理論に基づいていました。このアルゴリズムは、Google が 10 年足らずでスタートアップからほぼ世界を支配するまでに成長する上で重要な役割を果たしました。

コミュニティ検出は、現在グラフ理論で注目されている研究分野であり、モジュラリティ最大化（便利ではあるが欠点もある）に代わる多くの方法があります。

まず、その集約パターンは、特定のサイズの小さなグループから始まり、徐々により大きなグループへと移行します。これは解像度制限と呼ばれ、アルゴリズムは特定のサイズ以下のグループは検索しません。もう 1 つの課題は、パフォーマンスの大きなピークを超えることです。Mod-Max 方式では、多くの高いモジュール性スコアで構成される「プラトー」が作成される傾向があり、最大スコアの決定が困難になることがあります。

他のアルゴリズムでは、コミュニティを決定するために異なる方法が使用されます。 Edge-Betweenness は、すべての頂点を 1 つの大きなクラスターに集約する分割アルゴリズムです。すべての頂点が分離されるまで、ネットワーク内の「最も重要でない」エッジ データを繰り返し削除し続けます。このプロセスにより、構造内で類似の頂点が互いに近接する階層構造が生成されます。

もう 1 つのアルゴリズムは、グラフ グループ間の重複の可能性を考慮したクリーク パーコレーションです。他のアルゴリズムはグラフ内のランダムウォークに基づいており、隣接行列とその導関数の固有分解から始まるスペクトルクラスタリングアルゴリズムもあります。これらの方法は、コンピューター ビジョンなどの特徴抽出タスクに適用されます。

各アルゴリズムの詳細な応用例を示すことは、この入門書の範囲を超えています。データから有用な情報を抽出する効果的な方法は、数十年前には実現不可能でしたが、現在では活発に研究されている分野です。

IV. 結論

この記事が、機械がビッグデータをどのように理解できるかをより深く理解するきっかけになれば幸いです。将来は急速に変化しますが、その変化の多くは、今後 1 世代か 2 世代以内に実現可能になるテクノロジーによって推進されるでしょう。

はじめに述べたように、機械学習は非常に有望な研究分野であり、正確かつ効率的な方法で解決する必要がある複雑な問題が多数存在します。人間にとっては簡単な作業でも、機械が実行するには革新的なソリューションが必要です。

この分野ではまだやるべきことがたくさん残っており、次の大きな進歩に貢献する人は間違いなく多大な報酬を得ることになるでしょう。この記事を読んでいる人の中に、次の強力なアルゴリズムの発明者になる人がいるかもしれません。すべての素晴らしいアイデアはゼロから始まります。

オリジナル：

https://medium.freecodecamp.com/how-machines-make-sense-of-big-data-an-introduction-to-clustering-algorithms-4bd97d4fbaba

[この記事は、51CTOコラムニストのMachine Heart、WeChatパブリックアカウント「Machine Heart（id:almosthuman2014）」によるオリジナル翻訳です]

この著者の他の記事を読むにはここをクリックしてください