※本文読まなくてもいいので、ぜひ図だけでも見ていってください笑

※このあたりお詳しい人がいたらコメント、補足など大歓迎

目次
0. はじめに
1. 更新版ビジョン
2. 代表的なクラスタリング
3. 群知能クラスタリング[5]
- 3.1 Ant Colony Clustering Model (ACCM)
  - 3.1.1 概要
  - 3.1.2 クラスタリング挙動の可視化
- 3.2 Boids（Bird-oid:仮想的な鳥）、あるいはFlock Algorithm
4. おわりに
5. 参考

0. はじめに

　私のやりたい構想をまとめたブログ（超個体型データセンターにおける群知能クラスタリングの利用構想 - クマガリウムぶろぐ）を実現するためには、群知能クラスタリングと相性が良いのではないかと考えています。そこで、前回のブログ（焼きなまし法と粒子群最適化法の探索挙動を可視化してみた - クマガリウムぶろぐ）では、群知能クラスタリングにつながる最適化アルゴリズムの基本的なところの理解のために可視化を利用して簡単にまとめました。

　今回は、いよいよ(自分の中で)本題の群知能クラスタリングについてまとめていきたいと思います。ここでは、クラスタリング挙動の可視化によって、その特性を簡単にまとめていきます。それぞれのアルゴリズムごとにブログを書いてもいいくらい奥が深いですが、ここでは群知能クラスタリングでどんなことをしたいのかの全体像をなんとなく伝えるだけにします。

1. 更新版ビジョン

　まず群知能クラスタリングについて、私のイメージを図にすると以下のようになります。何かしらの特徴ベクトルを擬獣化（動物として捉える）、あるいは物理の分野の量子化（仮想粒子として捉える）し、それぞれのアナロジーに基づくルールに基づいた自律駆動によって、全体として意味のある状態を作る（クラスタリングが行われる）というものです。この場合の空間は、特徴空間（例えば、縦軸が身長、横軸が体重のようなもの）ではなく、擬獣化した特徴ベクトルを動き回らせるただの人工的な仮想空間を意味します。この点が個人的に非常に面白いと感じいます。つまり、擬獣間の相互作用や周りの環境変数などをこちらで勝手に定義することができ、まるで神が新しい世界を作るかのようなイメージを持つこともできます（←個人的にそんな妄想をしています）。

f:id:kumagallium:20190807094517p:plain:w500

では、これをわれわれの研究所のビジョンである「超個体型データセンター」にどのように当てはめるかを改めて考えてみます。正直、私自身運用の経験やネットワークなどの知識が不足していて、ゴールの明確なイメージはできていませんので、皆さんの経験に当てはめて補完していただきたい。とりあえず私の漠然としたイメージは以下の図の通り。VMやコンテナなどを擬獣化し、巣となるホスト（あるいは、小規模データセンター）を配置することで、類似したVMが集まると同時にホストの最適配置問題に適用できないか、またユーザを環境変数に取り入れることで、ユーザに近いところで配置の最適化が行われることも実現できないかというものです。また、異常な挙動をする個体を検知することも可能になるのではないかと考えています。さらに、VMの集積率が高くなりすぎる、アクセスが集中しすぎる状況が発生した場合には、環境温度が高くなるというルールを取り入れることで自動的に分散する構造もできるかもしれません。もっとこんな応用の方が面白いなどあれば、ぜひ教えていただきたい。

f:id:kumagallium:20190813131256p:plain:w200

2. 代表的なクラスタリング

　群知能クラスタリングを説明する前に、代表的なクラスタリング手法についても簡単に示しておきます。これら代表的なクラスタリング手法については、正しく説明されている本やサイトがあるので、詳しくはそちらで補完してください。

　クラスタリングは、大きく分けて２種類の手法が存在しますので、ここではその観点でまとめます。

2.1非階層型（K-means法）[1,2]

　K-means法は、非階層型のクラスタリング手法として広く利用されている手法の１つです。この手法は、以下の式を最小化する重心を見つけることで、データ点をk個のクラスタに分割します。

${ \displaystyle \sum_{i=0}^{n} \min_{\mu_{j} \in C} \left( || x_i - \mu_j ||^{2} \right) }$

ここで、 $x_i$ は各データ点で、nはデータ点の総数を表します。また、 $\mu_j$ は、各クラスターの重心です。アルゴリズムは以下の通りです。

k個の重心 $\mu_j$ をランダムに配置します。
各データ点 $x_j$ を最も近いクラスタ $j$ に割り当てます。
クラスタごとに、以下の式に基づいて重心を求めます。ここで、 $C_j$ は各クラスタに含まれるデータ集合、 $N_{C_j}$ は各クラスタに含まれるデータ数です。

${ \displaystyle \mu_j = \frac{1}{N_{C_j}} \sum_{x_i \in C_j}^{n} x_i }$

　４. クラスタに変化がなくなるまで、2,3を繰り返します。

　K-means法は、クラスタの重心を求めて分割するという簡単なアルゴリズムであり、計算コストが小さいことから多くの場面でよく用いられている。しかし、重心の初期値にクラスタリング結果が依存したクラスタリングになることや、入れ子構造をしているデータの場合にうまくクラスタリングできない（カーネルを使うなどの工夫をすればできるが）などの問題がある。

2.2 階層型（樹形図：デンドログラム）[2,3,4]

　デンドログラムは、階層型のクラスタリング手法として広く利用されている手法の１つです。ここでは、Ward法とユークリッド距離を利用した場合のアルゴリズムおよび図を示します。

全てのデータ点からユークリッド距離で最も近い点で、一つのグループを作ります。
点が2つ以上集まってグループになった場合は、グループの重心を計算する。
グループ化されたところは重心で考えて、1,2を繰り返して距離が近い順にグループ化を繰り返します。
上記プロセスによって得られた樹形図から、指定のクラスター数で分割します。あるいは、しきい値を元にクラスタ数を決定します。

　階層型クラスタリング手法は、データの構造を直感的に理解しやすくなっている。非階層型クラスタリング手法で課題であった入れ子構造のデータに対してもうまくクラスタリングでき、初期値の依存性もなく再現性があることが知られている。ところが、全データのデータ感の類似度の計算が必要になるため、データ点が多くなった場合に計算コストが膨大になる。この問題に関しては、K-means方で予めクラスターを大まかにクラスタリングしたあとにデンドログラムを適用することで計算コストを下げることも行われたりします。また、時系列的にデータ点の特徴量が変化した場合、非階層型は重心位置をずらす作業をすればよく前回の結果を利用できる（改良性がある）が、階層型は位置から計算する必要がある（改良性がない）などの問題がある。

画像出典元：クラスター分析の手法②（階層クラスター分析） | データ分析基礎知識

2.4 その他

　後述する群知能クラスタリングは、高次元な特徴ベクトルを利用して低次元空間上に類似したものを近い距離に、類似していなものを遠くに配置するという点で、次元圧縮手法とも捉えることができそうです。なので、代表的な次元圧縮手法である、主成分分析（PCA：principal component analysis）や多次元尺度法 (MDS: multi-dimensional scaling) 、t-SNE（t-distributed Stochastic Neighbor Embedding）あたりとの比較も別の機会にまとめたいと思います。

3. 群知能クラスタリング[5]

　上記代表的なクラスタリングの利点、欠点も参考に、群知能クラスタリングと一般的なクラスタリング手法との比較を以下に示しています（群知能クラスタリングにもいろいろありますし、K-meansなども改良されたものもあるので、あくまで私の考えです。鵜呑みにはしないように）。計算コストについては、全体の類似度を計算しない溶けない階層型が一番高く、近傍の類似度の計算でよい群知能クラスタリングは比較的小さく、K-meansが最も小さいと考えられます。特徴ベクトルが時系列的に変わるなどした場合に動的にクラスターを変化できるかどうか（改良性）については、重心を変えるだけで済みそうなK-meansや自律的に個体が移動しそうな群知能（条件設定による）は改良性がありますが、階層型は変わるたびに計算し直す必要がありそうです。再現性については、K-meansは初期値依存性がありますが、階層型にはなく、群知能も設計次第では再現性できそうです。階層性や入れ子構造については、K-meansは考慮できませんが、階層型はもちろんのこと、類似度に基づくクラスタリングを行うう群知能クラスタリングも可能です。群知能を用いたクラスタリングに代表例を次節から説明します。

f:id:kumagallium:20190809144711p:plain:w500

3.1 Ant Colony Clustering Model (ACCM)

3.1.1 概要

　蟻コロニークラスタリングモデル（ACCM）は、蟻が幼虫の仕分けをする行動に基づいたクラスタリングアルゴリズムです。蟻は知覚範囲内に同じ種類の幼虫が存在するかどうかを判断します。もし周りに幼虫がいない、もしくは同じ種類の幼虫があまりいない場合には拾う行為をし、周りに同じ幼虫がいる場合に幼虫を下ろします。この作業を繰り返すことにより、小さなクラスタは縮小、消滅し、大きなクラスタはより大きなものに成長します。

3.1.2 クラスタリング挙動の可視化

　もっとも単純な例として、特徴量として1か-1のどちらかを有する幼虫がいた場合に、ランダムに放たれた幼虫を蟻がどのように仕分けるかの挙動を可視化した図が以下の通りです。ここで、左がランダムに配置された初期値、右がクラスタリング挙動を表しています。黄色と紫の幼虫をクラスタリングすることができれば成功ですが、正しくクラスタリングできていることが確認できます。

また、上記のアルゴリズムに対して、各アリが短期記憶を持つように変更を加えた場合の挙動が以下の通りです。ここでの記憶する内容は、これまで降ろしてきた場所とその点の密度情報です。つまり、今拾った幼虫に対して、これまで降ろしてきた場所の中で最も適した場所をどこかを検索してその場所に移動する行動を取ります。それにより、まだ訪れていない場所に幼虫が降ろされることを防ぐことができ、より効率よくクラスタリングが行われます。

では、より複雑な特徴量を持つデータに対して、どのように動作するのかを見てみます。以下は、Irisデータセットに対してクラスタリングを行った結果です。ランダムに配置された初期値からクラスタリングが行われていることが確認できます。しかし、そもそもIrisデータセットは三種類の花のデータが含まれていますが、setosaはその他の花と特徴が異っていますが、 versicolorとvirginicaは似ている特徴を持っていてクラスタリングが難しいです。なので、実際に以下の図においても、紫（setosa）はクラスタリングがうまくできていますが、他の二種類は完全には分割することはできていないことがわかります。

　上記はシンプルなACCMのアルゴリズムを利用して実装しました。しかし、このアルゴリズムの場合、データによっては離れた距離に同じ種類のクラスタが複数生成されてしまうことがあり、その統合が難しくなってしまう場合があるようです。その課題については、拾い上げる確率に情報エントロピーの効果を取り入れる、類似度の計算式を変更する、記憶の仕方を変更する、適応的にαなどのパラメータを変更するなど様々な改善策が提案されてきています。

3.2 Boids（Bird-oid:仮想的な鳥）、あるいはFlock Algorithm

3.2.1 概要

　Flock アルゴリズム[2]は、鳥などの群れの動きを模倣するアルゴリズムを取り入れたアルゴリズムです。鳥が群れを作る行動である1. 同種の群れの近くで留まる(Flock)、2. 同種でない群れから離れる（衝突回避）、3. 最近傍の鳥と速度を合わせる（速度調整）の３つの規則を利用してクラスタリングをします。この規則に従って各個体を動かすことにより種類別のクラスタリングが可能となります。

3.2.2 クラスタリング挙動の可視化

　ACCMと同様に、まずもっとも単純な例として、特徴量として1か-1のどちらかを有する鳥がいた場合のクラスタリングの結果を以下に示します。ACCMは、蟻（エージェント）が動き回って幼虫（クラスタリングする対象）をクラスタリングしていましたが、Boidsでは種類の異なる鳥そのものが自律的にクラスタリングされる挙動をしていることが確認できます。

　また、Irisデータセットの場合のクラスタリング結果を以下に示します。ACCMと同様に、紫（setosa）はきれいに分離されている一方で、黄色（versicolor）と緑（virginica）は近いところを飛んでいます。ACCMもBoidsも、Irisに対する最終的なクラスターは２つと判断することになります（多くは、鳥の移動速度を遅くしていき、鳥が止まったときの塊で判断している印象）。

3.2.3 入れ子構造のクラスタリング

　入れ子構造のデータに対するクラスタリングについては、あえて節を変えてまとめてみます。まず、以下の特徴をもつ５つのデータを用意します。

これらを描画してみると、入れ子構造のデータをしていることが確認できます。今は、色が分かれているので５種類存在することがわかります。しかし、色がなかった場合、おそらく人間は外側と内側の２種類としてクラスタリングするのではないでしょうか。

では、この特徴量に対してK-means法を適応するとどうなるでしょう。外側と内側の２種類をクラスタリングしたいと思い、クラスター数を２として実行した結果が以下のとおりです。K-means法は、重心を探すだけなので入れ子構造をうまく分けてくれませんでした。

では、階層型のデンドログラムではどうでしょうか。しきい値の設定によりますが、中と外は別ものであることは判断してくれそうです。（ただし、外側と内側の２種類でうまく切り分けてくれるしきい値は、今回は存在しませんでした）

次に、Boidsに適用してみます。クラスタリングの様子は以下の図のとおりです。Boidsの場合、入れ構造であるかどうかは、関係なくデータ点間の類似度（個々では距離）に基づいて動かすため、外側と内側を分離することができます。

以下に、最終的に外側と内側が分離されている様子を示しています。

このクラスタリング結果を、元の図に適用してみた結果が以下の図です。一部クラスタリングミスはあるものの外側と内側が別物であることが分割できていることが確認できます。

3.2.4 補足

　参考文献[5]のアルゴリズム（上記３つのルール）に従って実装しましたが、あまりうまく動いてくれませんでした（どこかミスもあるかもしれない）。なので、後述する変更を加えたアルゴリズムで実装しています。特に、違和感を覚えたのがルール１のFlockの実装でした。参考文献では、類似したk近傍との重心に移動する実装になっていましたが、クラスタリングの終盤になってk匹以上の鳥が重なってしまった場合、現状のクラスターで満足してしまい、別の場所に存在する同じ種類の鳥と合流することをやめてしまいました。そこで、私が行った上記実装は、ルール４として「類似する個体とも一定の距離をとる」という実装も加えてました。これにより、鳥どうしが程よく距離を保てるので、常に同じ種類の鳥を探す行動を取りやすくなりました。

　また、ACCMも同様ですが、Irisのクラスタリングにおいて３種類に分割できなかったことについてどう考えるべきでしょうか。このサイト（クラスタリング (クラスター分析)）に興味深いことが書いてあります。

クラスタリングは探索的 (exploratory) なデータ解析手法であって，分割は必ず何らかの主観や視点に基づいているということです．

Irisが３つに分かれているという前情報（主観）があった上で、クラスタリングして２種類だったということは間違いに感じます。似ているものと似てないものを切り分けるだけなら、２種類でいいかもしれません。入れ子構造の結果も、なんとなく外側と内側で分かれそうと人間が判断しますが、デンドログラムの結果のように、一部切れているところで分けて５種類でも問題ないかもしれません。そもそも５つの特徴量で構成されていたデータである訳ですから、正解とは何なのかということです。

4. おわりに

　我々の研究所で掲げている「超個体型データセンター」というコンプトをベースに、自分がワクワクするシステム、を考えた結果、現状ではこのブログにも紹介したような群知能クラスタリングに基づいた自律分散協調システムを実現することでした。というよりむしろ、個人的にアナロジーを利用して最適化やクラスタリングを行う「群知能」自体に非常に興味があり、今後も続けていきたいなと思っています。　クラスタリングと主観の話（3.2.4 補足）を書きましたが、私が示したビジョンにおいても、綺麗なクラスタリングができる必要はないと考えています。綺麗にクラスタリングできないとしても、類似している個体が集まって動いていることはある程度保証できそうですし、それよりも改良性や再現性、階層性などのメリットを持つクラスタリング手法であることが、私のビジョンにとって重要であると考えています。

　全体的に書きたいことが多すぎて、うまくまとまっていないような気もしますが、見ていただいてありがとうございます。（もうちょっと文章もうまくなりたいし、まとめ上手になりたい。。）

目次