超個体型データセンターにおける群知能クラスタリングの利用構想
※提案手法は、まだジャストアイデアですので、コメントやアドバイス等大歓迎です。
※群知能についても勉強中ですので、こちらもコメント大歓迎です。
目次
0. スライド
本記事は、以下のスライドについて説明します。 speakerdeck.com
1. 背景
私の所属するさくらインターネット研究所では、研究所全体のビジョン（超個体型データセンターを目指す当研究所のビジョン – さくらインターネット研究所）を掲げています。是非ブログを読んでほしいところですが、本記事でも簡単に私なりの解釈でまとめてみます。
一言でいうと「超個体型データセンター」です。もう少し詳しく説明してみます。現在はデータセンターに巨大なコンピューティングリソースが存在していますが、今後はレイテンシ／セキュリティ／コスト等の要件から、あらゆる場所や社会、組織に分散して溶け込んでいくことが予想されます。ただし、ただの分散ではなく"自律的に"分散あるいは"有機的に"結合するハイブリッド構造をとると考えています。そして、その自律的なハイブリッド構造によって現場最適化あるいは全体最適化を実現し、我々をよりインテリジェンスに支えてくれるデータセンター、それが「超個体型データセンター」です。 超個体とはなにかについては、Wikipedia（超個体 - Wikipedia）を読んでいただくと、なんとなくイメージしていただけるかと思います。
2. アプローチ
私自身は、インフラエンジニアやネットワークエンジニアではなく、機械学習を使った異常検知などを研究する者です。その観点から、コンセプトを実現するためにできるアプローチを考えてみます。
「各個体が自律的に機能しながらも、局所的かつ全体的に統率されている」という超個体的イメージは、私の中で機械学習における「逐次学習する特徴ベクトル」と「クラスタリング」の関係性のイメージと一致しています。何らかのノード（ホスト、VM、コンテナ、プロセスなど）を逐次学習によって動的な特徴ベクトルを形成し、各ノードを動的にクラスタリングすることができれば、（特徴ベクトルの定義によりますが、）クラスタリングを利用した異常検知やルーティングの最適化、（キャッシュ）サーバの最適配置など超個体型データセンターの実現に向けた要素研究につながりそうです。
そのため私の研究テーマは、「（逐次学習する）特徴ベクトル」と「クラスタリング」に設定しています。特徴ベクトルについては、また別の記事にまとめていきたいと思いますが、本記事ではクラスタリングについて紹介します。特に私は、超個体と親和性が高そうな「群知能を用いたクラスタリング」について調査、研究を進めています。本記事では、群知能の簡単な説明と新しい群知能のアイデアを紹介します。
3. 群知能
3.1 群知能とは
群知能とは、個体間の局所的で簡単なやり取りを通し、全体が高度な動きをする現象を模倣した人工知能技術です。こちらも詳しくは、Wikipedia（群知能 - Wikipedia）を御覧ください。
本記事では、群知能の代表例として蟻コロニー最適化（ACO）と粒子群最適化（PSO）を簡単に説明します。
3.1.1 蟻コロニー最適化（ACO）
蟻コロニー最適化（ACO）は、蟻の採餌行動に着想を得た最適化手法です。蟻はランダムに巣の周りを探索し、地面にフェロモンを残します。そして餌を見つけるとフェロモン量を補強しながら巣に戻ります。他の蟻はフェロモンが強い道を選ぶため、フェロモンを補強する行動をとります。ただし、フェロモンは一定時間で蒸発します。これら一連の動作を繰り返すことにより、余計な道は消えて餌までの最短距離が自動的に選択されます。 ACOは、最適経路が求まるアルゴリズムであるため、すでに通信ネットワークへの適用研究も行われています[1]。
3.1.2 粒子群最適化（PSO）
粒子群最適化（PSO）[2]は、餌を探す鳥の群れなどの行動に着想を得た最適化手法です。ACOでは、蟻が最適な経路を作るアルゴリズムでしたが、PSOは個々の鳥そのものが解となります。以下の図のように、各鳥が今までに得た最良な場所、他の鳥が得た最良の場所、現在の慣性因子を考慮して次に向かうべき場所を決定します。この条件で移動を繰り返すことによって、最適な位置に鳥たちが集まり、その点が最適解となります。収束の様子を表す図として@sz_drさんの図がわかりやすいので引用させてもらいました（←引用に問題があれば削除します）。
粒子群最適化による解の収束の様子 画像出典元： 粒子群最適化法(PSO)で関数の最小値を求める - Qiita
3.2 群知能クラスタリング
よく用いられる一般的なクラスタリングとして、非階層的クラスタリング手法（例えば、k-means法）と階層的クラスタリング手法が挙げられます。それらが、どういうものでそれぞれどういう利点、欠点があるのかは#02 位置と集団を見抜く / 4. クラスタ生成の統計アルゴリズム – Antecanis Inc.がわかりやすかったので、詳しい説明はそちらをご覧ください。ここでは、それら一般手法と群知能を用いたクラスタリングをざっくり比較してみます。k-means法は、階層的クラスタリングよりも計算コストが小さい点、改良性がある点が強みだとされています。ここでいう改良性とは、新しいデータが追加された時に容易にいずれかのクラスタに割当できるかどうかを意味します。k-means法であれば、どのクラスタ中心に近いかを計算するだけでクラスタリングできますが、階層型の場合は基本的にゼロから再計算をする必要があります。ところが、k-means法は、階層性を考慮しない点や再現性がない（初期値に依存してしまう）点が欠点として挙げられ、それぞれ得意不得意が存在します。
ここで、私が描いている「逐次学習する特徴ベクトルによるクラスタリング」を実現するためには、どういうクラスタリングが必要かを考えてみます。まず、逐次的に特徴ベクトルが変化し、それに応じてクラスターも逐次的に変化してほしいので、改良性が必要です。次に、階層性も必要だと考えています。例えば異常検知への応用を想定した場合、DoS攻撃というクラスタの中にもSYNフラッド攻撃やUDPフラッド攻撃など細かなクラスタが存在することが予想され、階層性を考慮したクラスタリングとの親和性が高そうです。また、異常を人間が理解しやすいように可視化する場合にも、階層性を持っている方が有用であることが予想されます。ところが、先に述べた階層性、非階層性の２種類の手法では、その改良性と階層性の両方を持っていません。そこで注目したのが群知能を用いたクラスタリングです。群知能を用いたクラスタリングは、各個体間の類似性に基づいたクラスタリングによる階層性を考慮でき、新しいデータが追加に対しても類似性に基づいて動的にクラスタに割り当てられる改良性も備えています。群知能を用いたクラスタリングに代表例を次節から説明します。
3.1.1 蟻コロニークラスタリングモデル（ACCM）
蟻コロニークラスタリングモデル（ACCM）[2]は、蟻が幼虫の仕分けをする行動に基づいたクラスタリングアルゴリズムです。蟻は知覚範囲内に同じ種類の幼虫が存在するかどうかを判断します。もし周りに幼虫がいない、もしくは同じ種類の幼虫があまりいない場合には拾う行為をし、周りに同じ幼虫がいる場合に幼虫を下ろします。この作業を繰り返すことにより、小さなクラスタは縮小、消滅し、大きなクラスタはより大きなものに成長します。
3.1.2 Flockアルゴリズム
Flockアルゴリズム[2]は、鳥などの群れの動きを模倣するアルゴリズムを取り入れたアルゴリズムです。鳥が群れを作る行動である1. 同種の群れの近くで留まる(Flock)、2. 同種でない群れから離れる（衝突回避）、3. 最近傍の鳥と速度を合わせる（速度調整）の３つの規則を利用してクラスタリングをします。この規則に従って各個体を動かすことにより種類別のクラスタリングが可能となります。
4 提案手法
以上で紹介した既存の群知能クラスタリングを利用し、超個体型データセンターにつながる研究をしていくことを考えています。その一方で、新しい群知能クラスタリングを提案するための調査やアイデア出しを行っています。例えば、私は材料工学分野の研究をしてきましたので、それに関連する群知能が提案できないか考えています。本章では、新しい群知能クラスタリングの提案のための調査および提案を簡単に紹介します。
4.1 関連研究
4.1.1 荷電系探索 (CSS)
荷電系探索 (CSS)[3] は、物理学と力学の法則（クーロンの法則とガウスの法則とニュートン力学）に基づいた最適化手法です。適用度の値を電荷の値と定義することで、粒子間距離と合わせて電場やクーロン力が計算できます。そのクーロン力に従って粒子をどのように動かすかをニュートン力学により決定し、最適解を求めることができます（クラスタリングも可能[4]） 。PSOと同様に粒子そのものが解を表す手法です。
4.1.2 シミュレーテッドアニーリング（SA）
シミュレーテッドアニーリング（SA）は、材料工学における焼きなまし（アニーリング）という物理プロセスに着想を得た最適化手法です。アニーリングとは、物質を融解状態になるまで加熱し，徐々に冷却する操作のことであり、このアニーリングにより，分子がエネルギーが最も少ない状態に配列し，結晶構造を形成させることができます。この概念を最適化計算に利用しています。新しい点はランダムに生成され、その新しい点が現在の点より改善される場合は受け入れ、改悪される場合も一定の確率で受け入れます。その確率は、温度が高いほど、また変化量（新しい点と現在の差）が小さいほど受け入れる確率が高くなる関数となっています。それにより、高温では大域的な解の探索、低温では局所的な探索が行えるため、局所解に陥ることを避けることができます。
シミュレーテッドアニーリング（SA） 画像出典元：Wikipedia
4.1.2 PSO+SA
粒子群最適化（PSO）とシミュレーテッドアニーリング（SA）を組み合わせた手法の提案がすでにいくつか報告されている[5,6]。PSOは、単純、高速、且つ実装が容易ですが、粒子群の最適粒子が局所最適になってしまうと、粒子群が局所最適から飛び出すことは非常に難しくなる場合があります。一方でＳＡは、局所最適から飛び出して大域的最適値に近づくことができるように確率的にジャンプする性質を持っています。そこで、それらを組み合わせることにより、簡単で実装しやすいだけでなく、局所最適を避ける能力を強化し、収束の速度と精度も改善することが報告されています。
4.2 提案手法
以上の関連研究を含めて以下の手法を提案する。
4.2.1 CSS-SAハイブリッド法（核生成モデル？）を用いたクラスタリング
簡単にいうと荷電系探索 (CSS) とシミュレーテッドアニーリング（SA）の組み合わせ手法です。局所探索と大域的探索の両方を強化できるPSO+SAのPSOをCSSに置き換え、さらにクラスタリングに利用しようというものです。そうすることによって、液体状態から温度を下げることによって核が生成されるアナロジーで捉えることができ、そこから新しい発想が得られないかというアイデアです。本手法では、粒子間類似度が温度の力よりも大きくなった時に結合（粒子間の手を結ぶ）とみなすことによって、類似度の高いものから順に結合していき（階層性）、最低温度を特定の温度に設定することでその時点でのクラスターが生成されると予想しています。また、最低温度の設定によって改良性も持たせることができ、温度を上げ直すせば全体のクラスタリングをリセットすることもできると考えています。
まだジャストアイデア段階ですので、調査や実装をもう少し進める必要がありますが、この手法の強みを明確化できれば面白いかもしれないなぁと思っています。
4.2.2 ゾーンメルト型異常検知を用いたクラスタリング、および異常検知【おまけ】
こちらはCSS-SAハイブリッド法よりもジャストアイデアです。まずゾーンメルト法とは、不純物の多い金属のインゴットから純度の高いインゴットを精製するための不純物分離法です。その概念をクラスタリングに利用できないかというものです。部分的に（ゾーンに分けて）クラスタリングを行い、前の部分との類似性で紐付けることにより、最終的に異常を押し出すような異常検知に応用ができないかと考えています。
5. おわりに
さくらインターネット研究所のコンセプト「超個体型データセンター」から自分自身の興味に落とし込んだ結果「逐次学習する特徴ベクトルによるクラスタリング」の研究を進めたいと現在は考えています。そして、クラスタリングは、階層性と改良性の両方が得られる利点を持つ群知能クラスタリングに興味を持ち、特に取り組んでいきたいと考えています。また、既存の群知能クラスタリングを利用して、異常検知やサーバの最適配置のような様々な応用に落とし込む研究を進めるのはもちろん、自分自身のバックグラウンド（材料工学）を活かした新しい手法を提案できればさらに嬉しいなという気持ちです。まだまだ関連研究も調査段階ですし、アイデアもジャストアイデアな感じですが、今回のようにアウトプットをして、様々な方からフィードバックを貰って、深めていければと思っています。
