データサイエンティストになるには悪い時代ではありません。 あなたが「ビッグデータ」に話を向けると、真面目な人たちはあなたに興味を持つかもしれませんし、「人工知能」や「機械学習」に言及すると、他のパーティーの人たちは興味を持つことでしょう。 Googleでさえ、あなたは悪くないし、さらに良くなっていると考えているのです。 データサイエンティストのワザを助ける「賢い」アルゴリズムがたくさんある。 すべてが複雑に見えるかもしれませんが、アルゴリズムを少し理解して整理すれば、必要なものを見つけて適用することはそれほど難しくありません。
データマイニングや機械学習に関するコースでは、シンプルかつ便利なので、通常はクラスタリングから始めることになります。 これは教師なし学習というやや広い分野の重要な部分であり、説明したいデータがラベル付けされていない場合です。 多くの場合、これはユーザーが期待される出力が何であるかの情報をあまり与えていない場合です。 アルゴリズムはデータしか持っていないので、できる限りのことをするはずです。 この場合、クラスタリング、つまり、データを類似のデータポイントを含むグループ（クラスタ）に分離し、グループ間の非類似度をできるだけ高くすることを行う必要があります。 データポイントは、顧客など、あらゆるものを表すことができます。
K-Means Clustering
必要な導入の後、データマイニングのコースは常に K-Means で継続します。 実際に実行する前に、データ ポイント間の距離関数 (たとえば、空間内のポイントをクラスタリングする場合はユークリッド距離) を定義し、希望するクラスタ数 (k) を設定する必要があります。 任意の k 個のランダムなポイントを選択することもできますし、他の方法を使用することもできますが、ランダムなポイントを選択することは良いスタートとなります。
-
割り当てステップ： データセットからのm個の点のそれぞれを、k個のセントロイドのうち最も近いものによって表されるクラスタに割り当てます。
-
更新ステップ： 各クラスタについて、新しいセントロイドがクラスタ内のすべての点の平均として計算される。 前のステップから、クラスタに割り当てられた点の集合がある。
反復のたびにセントロイドはゆっくりと移動し、各点からその割り当てられたセントロイドまでの総距離はどんどん小さくなっていく。 この2つのステップは収束するまで、つまりクラスタの割り当てにこれ以上変化がなくなるまで交互に行われる。 何回か繰り返すと、同じ点のセットが各セントロイドに割り当てられるので、再び同じセントロイドになる。 K-Meansは局所最適に収束することが保証されている。 しかし、それは必ずしも全体的な最適解（全体最適）である必要はありません。
最終的なクラスタリング結果は初期セントロイドの選択に依存することがあるので、この問題には多くの考察がなされています。 1つの簡単な解決策は、ただK-Meansをランダムな初期割り当てで数回実行することである。 その後、各ポイントからそのクラスタまでの距離の合計が最小になるもの、つまり、そもそも最小化しようとしている誤差値を取ることによって、最良の結果を選択することができます。
初期ポイントを選択する他のアプローチは、遠いポイントを選択することに頼ることができます。 これはより良い結果をもたらしますが、外れ値、つまり単にいくつかの誤差である可能性のある「外れ」ただけのまれな点についての問題が発生する場合があります。 これらは意味のあるクラスタから遠く離れているため、そのような点はそれ自身の「クラスタ」になってしまうかもしれない。 良いバランスはK-Means++で、その初期化はランダムな点を選ぶが、以前に割り当てられたセントロイドからの2乗距離に比例した確率で選ぶことになる。 より遠くにある点は，より高い確率で開始のセントロイドとして選択されることになる． その結果、点のグループがある場合、グループからの点が選択される確率は、それらの確率が加算されるにつれて高くなり、私たちが述べた外れ値の問題を解決します。
K-Means++ は Python の Scikit-learn K-Means 実装のデフォルト初期化でもあります。 Python を使用している場合、これはあなたの選択したライブラリであるかもしれません。
Java (Weka)
// Load some dataInstances data = DataSource.read("data.arff");// Create the modelSimpleKMeans kMeans = new SimpleKMeans();// We want three clusterskMeans.setNumClusters(3);// Run K-MeanskMeans.buildClusterer(data);// Print the centroidsInstances centroids = kMeans.getClusterCentroids();for (Instance centroid: centroids) { System.out.println(centroid);}// Print cluster membership for each instancefor (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)> >> print(yiris)上記の Python の例では、3 種類のアイリスについて花弁と萼片を含む標準例のデータセット ‘Iris’ を使用しました。
この場合、3つの異なるクラスタ（種）があることがわかり、K-Meansはどれが一緒になるかを正しく認識しました。 しかし、一般的に良いクラスタ数kはどのように選べばよいのでしょうか。 このような疑問は、機械学習ではよくあることです。 クラスタ数を多くすれば、クラスタが小さくなるので、誤差（点から割り当てられたクラスタまでの距離の合計）が小さくなります。 では、kを大きく設定すれば良いのでしょうか？ 結局、k = m、つまり、各点がそれぞれのセントロイドとなり、各クラスタには1点しかない、ということになりそうです。 この場合、誤差は0になりますが、データをより単純に記述することはできず、また新しい点が現れるかもしれないので、それをカバーできるほど一般的ではありません。 これはオーバーフィットと呼ばれ、我々はそれを望んでいません。
この問題に対処する方法は、より大きなクラスタ数に対する何らかのペナルティを含むことです。 つまり、誤差だけでなく、誤差＋ペナルティを最小化しようとするわけです。 クラスタ数を増やすと、誤差はゼロに収束するだけですが、ペナルティは大きくなります。 ある時点で、別のクラスタを追加することによる利得が、導入されたペナルティよりも小さくなり、最適な結果が得られるでしょう。 この目的のためにベイズ情報量規準（BIC）を使用するソリューションは、X-Meansと呼ばれています。
もうひとつ、適切に定義しなければならないのは、距離関数です。 それはデータの性質からして論理的なものであり、簡単な作業である場合もあります。 空間の点については、ユークリッド距離は明白な解決策ですが、異なる「単位」の特徴、離散変数などについては厄介な場合があります。 これには、多くのドメイン知識が必要かもしれない。 また、機械学習に助けを求めることもできる。 実際に距離関数を学習してみるのである。 もし、どのようにグループ化されるべきかがわかっている点（つまり、クラスタにラベル付けされた点）の訓練セットがあれば、教師あり学習技術を使って良い関数を見つけ、それをまだクラスタ化されていないターゲットセットに適用することができる。 実際、これはEMの非常に単純なバージョンと考えることができる。
EM クラスタリング
つまり、K-Means クラスタリングでは各ポイントは1つのクラスタに割り当てられ、クラスタはそのセントロイドによってのみ記述される。 これでは、クラスタが重なっていたり、円形でないクラスタがあったりして、あまり柔軟性がない。 EMクラスタリングでは、さらに一歩進んで、各クラスタをセントロイド（平均）、共分散（楕円形のクラスタができるように）、重み（クラスタの大きさ）で表現できるようになりました。 ある点がクラスターに属する確率は、多変量ガウス確率分布（multivariate – 複数の変数に依存する）で与えられるようになりました。 1678>
ここで各点について、現在の各クラスタ（これも最初にランダムに作られる）に属する確率を計算して、EM手順を開始します。 これがEステップである。 もし1つのクラスタがある点に対して本当に良い候補であれば、それは1に近い確率を持つことになる。 しかし、2つ以上のクラスタが許容できる候補となりうるので、点はクラスタ間の確率の分布を持つことになる。 このように1つのクラスタに限定されない点のアルゴリズムの特性を「ソフトクラスタリング」と呼ぶ。
ここでMステップでは、以前のクラスタのセットへの点の割り当てを使用して、各クラスタのパラメータを再計算する。 クラスタの新しい平均、共分散、重みを計算するために、各ポイントデータは前のステップで計算されたように、クラスタに属する確率で重み付けされる。
これらの2つのステップを交互に行うと、収束するまで総対数尤度を増加させることができる。 繰り返しになるが、最大値は局所的なものかもしれないので、より良いクラスタを得るためにアルゴリズムを数回実行することができる。
今、各ポイントについて1つのクラスタを決定したい場合、単純に最も確率の高いものを選択することができる。
Affinity Propagation
Affinity Propagation (AP) は 2007 年に Frey と Dueck によって発表され、その単純さ、一般への適用性、および性能により、ますます人気が出てきている。 1678>
K-Means や同様のアルゴリズムの主な欠点は、クラスタ数を選択しなければならないことと、ポイントの初期セットを選択しなければならないことです。 親和性伝播は、代わりに、データポイントのペアの間の類似性の測定値を入力として取り、同時にすべてのデータポイントを潜在的な模範として考慮します。
入力として、このアルゴリズムは 2 つのデータ セットを提供する必要がある。
プリファレンス：各データ点が模範となるのに適しているかどうかを表す。
類似度とプリファレンスの両方が1つの行列で表されることが多く、主対角線上の値はプリファレンスを表す。 行列表現は密なデータセットに適している。 点間の接続がまばらな場合、n×n の行列全体をメモリに格納するのではなく、接続された点に対する類似性のリストを保持する方がより実用的です。
次に、アルゴリズムは収束するまで、いくつかの繰り返しを実行します。 各反復には2つのメッセージパッシングステップがある：
-
責任を計算する。 責任r（i、k）は、点iの他の潜在的な模範を考慮に入れて、点kが点iの模範として機能するのにいかに適しているかの蓄積された証拠を反映する。 利用可能性a（i，k）は、点kが模範となるべきであるという他の点からの支持を考慮して、点iが点kをその模範として選択することがいかに適切であるかについての蓄積された証拠を反映するものである。 1678>
責任を計算するために、アルゴリズムは前の反復で計算された元の類似度と有用性を使用する（最初は、すべての有用性はゼロに設定される）。 責任度は、点iとその模範となる点kとの間の入力類似度から、点iと他の模範候補との間の類似度と利用可能性の合計のうち最大のものを差し引いたものに設定される。 ある点が模範にどれだけふさわしいかを計算する論理は、最初の先験的な好みが高ければより好まれるが、自分自身を良い候補と考える類似点があれば責任は低くなり、ある反復で一方が決定されるまで、両者の間に「競争」がある、というものだ。
そこで、利用可能性の計算では、各候補が良い模範になるかどうかの証拠として、計算した責任を用いる。 利用可能性a（i，k）は自己責任r（k，k）に模範候補kが他の点から受ける正の責任の合計を加えたものに設定される。
最後に、値の変化がある閾値を下回ったとき、または反復の最大数に達したときなど、手順を終了させる異なる停止基準を持つことが可能である。 Affinity Propagation 手続きの任意の時点で、Responsibility (r) と Availability (a) 行列を合計すると、必要なクラスタリング情報が得られます： ポイント i について、最大の r(i, k) + a(i, k) を持つ k はポイント i の模範を表します。 また，模範解答の集合が必要なだけであれば，主対角線を走査することもできます． r(i, i) + a(i, i) > 0なら、点iは模範です。
K-Means や同様のアルゴリズムでは、クラスタ数の決定が厄介なことがあることを見てきました。 AP では、明示的に指定する必要はありませんが、最適と思われるクラスタより多いか少ないかを得る場合、まだいくつかのチューニングが必要な場合があります。 幸いなことに、プリファレンスを調整するだけで、クラスタ数を減らしたり増やしたりすることができる。 プリファレンスを高い値に設定すると、各ポイントが模範となる適性を「より確信」するため、他のポイントの「支配」の下に「倒す」ことが難しくなり、クラスタが増えることになる。 逆に、プリファレンスを低く設定すると、クラスタが少なくなります。まるで、「いやいや、お願いだから、あなたの方が模範的だから、あなたのクラスタに入りましょう」と言っているようなものです。 一般的なルールとして、クラスタの数が中程度から多い場合はすべてのプリファレンスを類似度の中央値に設定し、クラスタの数が中程度であれば類似度の最小値に設定することがあります。 1678>
Hierarchical Affinity Propagation は、データセットをいくつかのサブセットに分割し、それらを別々にクラスタリングし、次に 2 階層のクラスタリングを実行することによって 2 次的複雑さに対処するアルゴリズムの変種として、言及する価値があります。
In The End…
クラスタリング アルゴリズムの全範囲があり、それぞれどのタイプのデータを扱うか、時間の複雑さ、弱点などに関して長所と短所がある。 たとえば、Hierarchical Agglomerative Clustering (または Linkage Clustering) は、必ずしも円形の (または超球状の) クラスタがなく、クラスタの数を事前に知らない場合に有効です。
階層的凝集型クラスタリングでは、デンドログラム（樹形図）を適切と思われるところで水平に切断することにより、後からクラスタ数を簡単に決めることができます。 また、再現性がありますが（同じデータセットに対して常に同じ答えを出す）、複雑度（2次関数）が高くなります。
それから、DBSCAN (Density-Based Spatial Clustering of Applications with Noise) も言及に値しますアルゴリズムです。 これは、密接に詰め込まれた点をグループ化し、近くに点がある任意の方向にクラスタを展開し、その結果、さまざまな形状のクラスタを処理します。
これらのアルゴリズムはそれ自身の記事に値するので、後で別の記事で調査できます。 幸運なことに、さまざまなプログラミング言語でさまざまな実装があるので、それらを試してみるには、遊ぶ意欲が少しあればよいのです。