クラスタリングアルゴリズム：最初から最先端まで

公開: 2022-03-11

データサイエンティストになるのは悪い時期ではありません。 会話を「ビッグデータ」に向けると、真面目な人があなたに興味を持ってくれるかもしれません。「人工知能」や「機械学習」に言及すると、他のパーティーの観客も興味をそそられます。 グーグルでさえ、あなたは悪くないと思っており、あなたはさらに良くなっていると思っています。 データサイエンティストが魔法をかけるのに役立つ「スマート」アルゴリズムはたくさんあります。 すべてが複雑に見えるかもしれませんが、アルゴリズムを少し理解して整理すれば、必要なアルゴリズムを見つけて適用することはそれほど難しくありません。

データマイニングや機械学習のコースは、シンプルで便利なため、通常はクラスタリングから始まります。 これは、教師なし学習のやや広い領域の重要な部分であり、説明したいデータにはラベルが付けられていません。 ほとんどの場合、これは、ユーザーが期待される出力について多くの情報を提供しなかった場合です。 アルゴリズムにはデータしかなく、可能な限り最善を尽くす必要があります。 私たちの場合、クラスタリングを実行する必要があります。つまり、データを類似のデータポイントを含むグループ（クラスター）に分離し、グループ間の非類似度は可能な限り高くします。 データポイントは、クライアントなど、あらゆるものを表すことができます。 クラスタリングは、たとえば、類似したユーザーをグループ化してから、各クラスターで異なるマーケティングキャンペーンを実行する場合に役立ちます。

K-Meansクラスタリング

必要な紹介の後、データマイニングコースは常にK-Meansで継続されます。 効果的で広く使用されている、万能のクラスタリングアルゴリズム。 実際に実行する前に、データポイント間の距離関数（たとえば、空間内のポイントをクラスター化する場合はユークリッド距離）を定義し、必要なクラスターの数（k）を設定する必要があります。

K-Means

アルゴリズムは、開始重心（クラスターの「中心」）としてk点を選択することから始まります。 k個のランダムなポイントを選択することも、他のアプローチを使用することもできますが、ランダムなポイントを選択することから始めるのがよいでしょう。 次に、次の2つの手順を繰り返します。

  1. 割り当て手順：データセットのm個のポイントのそれぞれが、k個の重心の最も近いもので表されるクラスターに割り当てられます。 各ポイントについて、各重心までの距離を計算し、最も遠いものを選択します。

  2. 更新手順：クラスターごとに、クラスター内のすべてのポイントの平均として新しい重心が計算されます。 前のステップから、クラスターに割り当てられた一連のポイントがあります。 ここで、そのようなセットごとに、クラスターの新しい重心を宣言する平均を計算します。

各反復の後、図心はゆっくりと移動し、各ポイントから割り当てられた図心までの合計距離はますます低くなります。 2つのステップは、収束するまで、つまりクラスター割り当てに変更がなくなるまで交互に行われます。 何度か繰り返した後、同じ重心のセットが各重心に割り当てられるため、再び同じ重心になります。 K-Meansは、局所最適に収束することが保証されています。 ただし、それが必ずしも全体として最良のソリューションである必要はありません（グローバル最適）。

最終的なクラスタリングの結果は、最初の重心の選択に依存する可能性があるため、この問題について多くの考慮が払われています。 簡単な解決策の1つは、ランダムな初期割り当てを使用してK-Meansを数回実行することです。 次に、各ポイントからそのクラスターまでの距離の合計が最小の結果を選択することで、最良の結果を選択できます。これは、最初に最小化しようとしているエラー値です。

初期点を選択する他のアプローチは、離れた点の選択に依存する可能性があります。 これにより、より良い結果が得られる可能性がありますが、外れ値に問題​​がある可能性があります。これらのまれな単独のポイントは、単に「オフ」であり、エラーである可能性があります。 それらは意味のあるクラスターからはほど遠いため、そのような各ポイントは最終的に独自の「クラスター」になる可能性があります。 良いバランスはK-Means++バリアント[ArthurandVassilvitskii、2007]であり、その初期化ではランダムなポイントが選択されますが、確率は以前に割り当てられた重心からの二乗距離に比例します。 遠くにあるポイントは、開始重心として選択される可能性が高くなります。 したがって、ポイントのグループがある場合、その確率が加算されるにつれて、グループからポイントが選択される可能性も高くなり、前述の外れ値の問題が解決されます。

K-Means ++は、PythonのScikit-learnK-Means実装のデフォルトの初期化でもあります。 Pythonを使用している場合は、これが最適なライブラリである可能性があります。 Javaの場合、Wekaライブラリは良いスタートかもしれません：

Java（Weka）

 // Load some data Instances data = DataSource.read("data.arff"); // Create the model SimpleKMeans kMeans = new SimpleKMeans(); // We want three clusters kMeans.setNumClusters(3); // Run K-Means kMeans.buildClusterer(data); // Print the centroids Instances centroids = kMeans.getClusterCentroids(); for (Instance centroid: centroids) { System.out.println(centroid); } // Print cluster membership for each instance for (Instance point: data) { System.out.println(point + " is in cluster " + kMeans.clusterInstance(point)); }

Python（Scikit-learn）

 > >> from sklearn import cluster, datasets > >> iris = datasets.loadiris() > >> Xiris = iris.data > >> yiris = iris.target > >> kmeans = cluster.KMeans(nclusters=3) > >> kmeans.fit(Xiris) KMeans(copy_x=True, init='k-means++', ... > >> print(kmeans.labels[::10]) [1 1 1 1 1 0 0 0 0 0 2 2 2 2 2] > >> print(yiris[::10]) [0 0 0 0 0 1 1 1 1 1 2 2 2 2 2]

上記のPythonの例では、標準のサンプルデータセット「Iris」を使用しました。このデータセットには、3種類のアイリスの花びらとがく片の寸法が含まれています。 これらを3つのクラスターにクラスター化し、得られたクラスターを実際の種（ターゲット）と比較して、完全に一致することを確認しました。

この場合、3つの異なるクラスター（種）があることがわかり、K-Meansはどちらが一緒になるかを正しく認識しました。 しかし、一般的に、適切な数のクラスターkをどのように選択するのでしょうか。 この種の質問は、機械学習では非常に一般的です。 より多くのクラスターを要求すると、クラスターは小さくなるため、合計エラー（ポイントから割り当てられたクラスターまでの距離の合計）は小さくなります。 では、kを大きく設定するのは良い考えですか？ k = mで終わる場合があります。つまり、各ポイントは独自の重心であり、各クラスターには1つのポイントしかありません。 はい、合計エラーは0ですが、データの簡単な説明は得られませんでした。また、表示される可能性のあるいくつかの新しいポイントをカバーするのに十分な一般的でもありません。 これは過剰適合と呼ばれ、私たちはそれを望んでいません。

この問題に対処する方法は、クラスターの数が多い場合にペナルティを含めることです。 そのため、現在、エラーだけでなく、エラー+ペナルティも最小限に抑えようとしています。 クラスターの数を増やすと、エラーはゼロに向かって収束しますが、ペナルティは大きくなります。 ある時点で、別のクラスターを追加することによるゲインは、導入されたペナルティよりも少なくなり、最適な結果が得られます。 この目的でベイズ情報量基準（BIC）を使用するソリューションは、X-Meansと呼ばれます[Pelleg and Moore、2000]。

適切に定義する必要があるもう1つのことは、距離関数です。 時にはそれは単純な作業であり、データの性質を考えると論理的な作業です。 空間内のポイントの場合、ユークリッド距離は明らかな解決策ですが、さまざまな「単位」の特徴や離散変数などでは扱いにくい場合があります。これには、多くのドメイン知識が必要になる場合があります。 または、機械学習に電話してサポートを求めることもできます。 実際に距離関数を学ぶことができます。 グループ化の方法がわかっているポイントのトレーニングセット（つまり、クラスターでラベル付けされたポイント）がある場合は、教師あり学習手法を使用して適切な関数を見つけ、それをまだクラスター化されていないターゲットセットに適用できます。 。

K-Meansで使用される方法は、2つの交互のステップがあり、期待値最大化（EM）法に似ています。 実際には、EMの非常に単純なバージョンと見なすことができます。 ただし、同じ原則のいくつかを共有している場合でも、より複雑なEMクラスタリングアルゴリズムと混同しないでください。

EMクラスタリング

したがって、K-Meansクラスタリングでは、各ポイントは1つのクラスターにのみ割り当てられ、クラスターはその重心によってのみ記述されます。 重なり合っているクラスターや円形ではないクラスターで問題が発生する可能性があるため、これはあまり柔軟ではありません。 EMクラスタリングを使用すると、さらに一歩進んで、各クラスターをその重心（平均）、共分散（楕円クラスターを持つことができるように）、および重み（クラスターのサイズ）で表すことができます。 ポイントがクラスターに属する確率は、多変量ガウス確率分布（多変量-複数の変数に依存）によって与えられるようになりました。 これは、ポイントがガウスの「ベル」の下にある確率、つまり、クラスターに属するポイントの確率を計算できることも意味します。

EM

ここで、各ポイントについて、現在のクラスターのそれぞれに属する確率を計算することによってEM手順を開始します（これも最初にランダムに作成される可能性があります）。 これがEステップです。 1つのクラスターがポイントの本当に良い候補である場合、その確率は1に近くなります。 ただし、2つ以上のクラスターが受け入れ可能な候補になる可能性があるため、ポイントにはクラスター全体に確率の分布があります。 1つのクラスターに限定されないポイントのアルゴリズムのこのプロパティは、「ソフトクラスタリング」と呼ばれます。

Mステップは、前のクラスターセットへのポイントの割り当てを使用して、各クラスターのパラメーターを再計算するようになりました。 クラスターの新しい平均、共分散、および重みを計算するために、各ポイントデータは、前のステップで計算されたように、クラスターに属する確率によって重み付けされます。

これらの2つのステップを交互に実行すると、収束するまで対数尤度の合計が増加します。 繰り返しになりますが、最大値はローカルである可能性があるため、アルゴリズムを数回実行して、より良いクラスターを取得できます。

ここで、ポイントごとに1つのクラスターを決定する場合は、最も可能性の高いクラスターを選択するだけです。 確率モデルがあるので、それを使用して同様のデータを生成することもできます。つまり、観測したデータに類似するより多くのポイントをサンプリングすることができます。

アフィニティの伝播

Affinity Propagation（AP）は、2007年にFrey and Dueckによって発行され、その単純さ、一般的な適用性、およびパフォーマンスのためにますます人気が高まっています。 ステータスを最先端からデファクトスタンダードに変更しています。

アフィニティの伝播

K-Meansおよび同様のアルゴリズムの主な欠点は、クラスターの数を選択し、ポイントの初期セットを選択する必要があることです。 代わりに、Affinity Propagationは、データポイントのペア間の類似性の入力測定値を取り、同時にすべてのデータポイントを潜在的な模範と見なします。 実数値のメッセージは、高品質のエグザンプラと対応するクラスターのセットが徐々に出現するまで、データポイント間で交換されます。

入力として、アルゴリズムでは2つのデータセットを提供する必要があります。

  1. データポイント間の類似性。ポイントが別のポイントの模範となるのにどれだけ適しているかを表します。 同じクラスターに属することができないなど、2つのポイント間に類似性がない場合は、実装に応じて、この類似性を省略または-Infinityに設定できます。

  2. 設定。各データポイントが模範となるのに適しているかどうかを表します。 この役割に有利な点となる先験的な情報があるかもしれないので、好みを通してそれを表すことができます。

類似性とプリファレンスの両方が単一のマトリックスで表されることが多く、主対角線上の値がプリファレンスを表します。 行列表現は、密集したデータセットに適しています。 ポイント間の接続がスパースである場合、nxnマトリックス全体をメモリに格納するのではなく、接続されたポイントとの類似点のリストを保持する方が実用的です。 舞台裏では、「ポイント間でメッセージを交換する」ことは、マトリックスを操作することと同じであり、視点と実装の問題にすぎません。

アフィニティの伝播

次に、アルゴリズムは収束するまで、何度も反復を実行します。 各反復には、2つのメッセージパッシングステップがあります。

  1. 責任の計算：責任r（i、k）は、ポイントiの他の潜在的な模範を考慮に入れて、ポイントkがポイントiの模範として機能するのにどれだけ適しているかについての蓄積された証拠を反映します。 責任は、データポイントiから候補の模範ポイントkに送信されます。

  2. 可用性の計算：可用性a（i、k）は、ポイントkがエグザンプラである必要があるという他のポイントからのサポートを考慮して、ポイントiがポイントkをエグザンプラとして選択することがどれほど適切であるかについての蓄積された証拠を反映します。 可用性は、候補の模範ポイントkからポイントiに送信されます。

責任を計算するために、アルゴリズムは前の反復で計算された元の類似性と可用性を使用します（最初は、すべての可用性がゼロに設定されています）。 責任は、ポイントiとポイントkの間の入力類似性をそのエグザンプラとして設定し、ポイントiと他の候補エグザンプラの間の類似性と可用性の合計の最大値を差し引いたものに設定されます。 ポイントがエグザンプラにどれだけ適しているかを計算する背後にある論理は、最初の先験的選好が高い場合はそれがより好まれますが、それ自体が良い候補であると見なす同様のポイントがある場合は責任が低くなるため、'がありますある反復で一方が決定されるまで、2つの間の競争」。

次に、可用性の計算では、計算された責任を、各候補者が優れた模範となるかどうかの証拠として使用します。 可用性a（i、k）は、自己責任r（k、k）に、候補の模範kが他のポイントから受け取る積極的な責任の合計を加えたものに設定されます。

最後に、値の変化があるしきい値を下回った場合や、反復の最大数に達した場合など、手順を終了するためのさまざまな停止基準を設定できます。 アフィニティ伝播手順の任意の時点で、責任（r）と可用性（a）の行列を合計すると、必要なクラスタリング情報が得られます。ポイントiの場合、最大r（i、k）+ a（i、k）のkはポイントを表します。私は模範です。 または、エグザンプラのセットだけが必要な場合は、主対角線をスキャンできます。 r（i、i）+ a（i、i）> 0の場合、点iは模範です。

K-Meansや同様のアルゴリズムでは、クラスターの数を決定するのが難しい場合があることがわかりました。 APを使用する場合、明示的に指定する必要はありませんが、最適と思われるクラスターよりも多いまたは少ないクラスターを取得する場合は、調整が必要になる場合があります。 幸い、設定を調整するだけで、クラスターの数を増減できます。 プリファレンスをより高い値に設定すると、クラスターが増えることになります。これは、各ポイントが模範となるのに「より確実」であり、したがって「打ち負かす」ことが難しく、他のポイントの「支配」に含めることが難しいためです。 逆に、設定を低く設定すると、クラスターが少なくなります。 彼らが「いや、いや、お願いします、あなたはより良い模範です、私はあなたのクラスターに参加します」と言っているかのように。 原則として、すべてのプリファレンスを、中程度から多数のクラスターの類似度の中央値、またはクラスターの数が中程度の場合の類似度の最小値に設定できます。 ただし、ニーズにぴったり合う結果を得るには、設定を調整して数回実行する必要がある場合があります。

データセットをいくつかのサブセットに分割し、それらを別々にクラスタリングしてから、第2レベルのクラスタリングを実行することにより、2次の複雑さを処理するアルゴリズムの変形として、階層的親和性の伝播についても言及する価値があります。

最終的には…

クラスタリングアルゴリズムにはさまざまなものがあり、それぞれに、データの種類、時間の複雑さ、弱点などに関する長所と短所があります。 より多くのアルゴリズムについて言及すると、たとえば、階層的凝集クラスタリング（またはリンケージクラスタリング）があります。これは、必ずしも円形（または超球形）クラスターがなく、クラスターの数が事前にわからない場合に適しています。 これは、各ポイントが個別のクラスターであるところから始まり、すべてが1つの大きなクラスターになるまで、各ステップで2つの最も近いクラスターを結合することによって機能します。

階層的凝集クラスタリングでは、樹形図（樹形図）を適切と思われる場所で水平にカットすることで、後でクラスターの数を簡単に決定できます。 また、繰り返し可能です（同じデータセットに対して常に同じ答えが得られます）が、より複雑です（2次式）。

階層的凝集クラスタリング

次に、DBSCAN（ノイズのあるアプリケーションの密度ベースの空間クラスタリング）も言及する価値のあるアルゴリズムです。 密集したポイントをグループ化し、近くのポイントがある任意の方向にクラスターを拡張して、さまざまな形状のクラスターを処理します。

これらのアルゴリズムは独自の記事に値するものであり、後で別の投稿で調べることができます。

どちらのアルゴリズムをいつ使用するかを知るには、試行錯誤の経験が必要です。 幸いなことに、さまざまなプログラミング言語でさまざまな実装が行われているため、それらを試してみるには、少しだけ進んでプレイする必要があります。

関連：機械学習理論とその応用の紹介