データサイエンスとデータベース

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

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

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

K-Meansクラスタリング

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

レールは何に使用されますか

K-Means

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

割り当て手順：データセットのm個のポイントのそれぞれが、k個の重心の最も近いもので表されるクラスターに割り当てられます。各ポイントについて、各重心までの距離を計算し、最も遠いものを選択するだけです。
更新手順：クラスターごとに、クラスター内のすべてのポイントの平均として新しい重心が計算されます。前のステップから、クラスターに割り当てられた一連のポイントがあります。ここで、そのようなセットごとに、クラスターの新しい重心を宣言する平均を計算します。

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

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

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

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

Java（インストール）

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

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

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

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

親和性の伝播

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

親和性の伝播

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

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

データポイント間の類似性。ポイントが別のポイントの模範となるのにどれだけ適しているかを表します。同じクラスターに属することができないなど、2つのポイント間に類似性がない場合は、実装に応じて、この類似性を省略したり、-Infinityに設定したりできます。
設定。各データポイントが模範となるのに適しているかどうかを表します。この役割に有利な点となる先験的な情報があるかもしれないので、好みを通してそれを表すことができます。

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

機械学習アルゴリズムの書き方

親和性の伝播

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

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

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