パーティーゲームでできること

こんかいは、パーティーゲーム(複数人でやるゲーム)を作るとしたらどんなことができるか考えてみました。スマホのゲームについて考えています。備忘録的な感じなので興味があれば見てください。

どんなシチュエーション?

東京に友達が遊びに来たとします。せっかく遊びに来たし何か一緒にできることはないかなと考えています。そんなときにできるようなゲームを考えたいなと思いました。ゲームを考えると言ってもガッツリモチーフを考えるのではなく、探しものをするゲームのようなざっくりな内容を考えていきます。

複数人のメリットって?

ゲームの中身を考えるために複数人がいるメリットについて考えました。一つ一つ詳しく説明していきたいと思います。

  • 役割を決めることができる。

これは鬼ごっこのようなものですね、鬼がいて逃げる人がいる。ゲームの目的は鬼が制限時間内に逃げる人を捕まえる。役割を作ることで行動に目的ができ、それがゲームへとつながります。

  • 意見のぶつけ合いができる。

なにか、2つの選択肢があるとします。その選択肢に制限時間もあったとします。人はそれぞれ違う考えを持っているので、意見が別れるかもしれません。でも制限時間があるのでどちらかに決めるらめに話し合いをしないといけません。そして、話し合いによって決まった意見でもどちらかに責任が生じるでしょう。正解をしたときには歓喜の気持ちが、失敗したときには責任のなすりつけがありますが、それもまた楽しいひとときになると思います。これは一体感を高めていますね。

  • 対戦・協力することができる

タブレットなどを使う場合、画面は大きいので二分割して何かを行うことができます。二分割で思いつくのはぷよぷよテトリスなどですね。どちらも対戦をすることができます。それ以外にも、コントローラを2つ表示させて協力プレーができると思います。スマホなど小さい端末の場合は難しいかもしれませんが、二人で操作できればとても大きな一体感が得られると思います。

どんなゲームが考えられる?

ではそのメリットを使ったゲームを考えてみたいと思います。

  • 役割を決めることができる。
    • 野球ゲーム : ピッチャーとキャッチャーに分かれて投げた打ったの野球を行う。画面は二分割でピッチャー側では指の奇跡でボールを投げて、バッター側ではそのボールを打つなどが考えられます。
    • 推理ゲーム : 警察と犯人にわけて、推理ゲームをします。たとえばお互い自分のターンにだけ画面を見ることにして犯人は事件のヒントを出します。警察はそのヒントから犯人が誰かを見つけ出します。これは二人以上じゃないといけませんね。
  • 意見のぶつけ合いができる。
    • 脱出ゲーム : 普通の脱出ゲームです。一人でも楽しめますが複数人で考えるといろいろな意見が出てくると思います。その中で正解に導けた場合はかなりの達成感と一体感ができると思います。
    • クイズゲーム : ネプリーグで最後行うゲームのようなものです。二択クイズを連続で正解していくゲームです。一回でも間違えたらゲーム終了となります。それぞれのクイズには制限時間があり、その時間内で決めないといけません。複雑なルールではないので楽しめると思います。
  • 対戦・協力ができる。
    • 落ち物対戦ゲーム : ぷよぷよテトリスですね。パズドラのようなゲームでもいいと思います。基本的には対戦として楽しいですが、共通の敵をゲームで得たスコアで倒すとしたら協力にもなると思います。
    • サポートマリオゲーム : マリオを誰かが操作して、マリオが進みやすいように道を作ってあげるようなゲームですね。wii u でこのようなゲームが出ていたと思います。言いたいことは主人公とサポート役に別れて協力してゴールを目指す形ということですね。

まとめ

まとめると、複数人いるので対戦や協力で目的を達成することが多いと思います。話し合いをする要素があれば一体感が得られると思います。どちらにしても複雑なゲームよりも単純だけど奥が深いゲームのほうがやりやすいと思います。理由は人数が多いほどゲームを始めるハードルが高いからです。今回は備忘録として色々書きましたが、まだまだ考えられることは多いと思いますし、実際は画面が小さいなどのデメリットがあると思いますので、それにも対処した面白いゲームをつくれたらなと考えています。

以上

具体例!!トピックモデルのトピックってなに?

こんにちは、最近はコロナ社のトピックモデルによる統計的潜在意味解析を読んでいます。

トピックモデルは少し前から注目されている自然言語処理の技術です。今更ですが、良い本に巡り会えたので勉強しています。

今日はその本のなかでも序章にあたる部分の中で、トピックが何なのかについて話せたらなと思っています。

僕の知識の中で話しているので、おかしいところもあると思います。その場合は指摘していただけるとありがたいです。

はじめに

トピックモデルにおけるトピックとは単語の潜在的な意味のことを言います。

といっても、潜在的な意味ってどういう意味?となると思いますので、今回の記事では潜在的な意味について学んだことを話したいと思います。

簡単に言うと、潜在的な意味とは単語の共起性によって発生する物です。

共起性? 同じ単語でも違った意味?

共起性といきなり言われてもわからないと思います。

例えば

  • I play baseball.
  • I play piano.

この2つの文章では、どちらもplayが使われています。ここで、ニュースサイトでこれらの文章が別々の記事の中でそれぞれの文章が記載されていることを考えてください。この2つの文章が掲載されている記事のジャンルで考えると、上はスポーツ関連、下は音楽関連になります。

このように、playだけではなく複数の単語と使うことによって意味が発生しています。このような性質を共起性と言います。

そして、単語や文章の潜在的な意味とは、この共起性によって発生した意味のことを言います。

なので、例では1つめのplayはスポーツの意味を持ち、2つめのplayは音楽の意味を持ちます。
そしてこのスポーツや音楽がトピックモデルにおけるトピックとなります。

実際このトピックというものはラベル付けされているわけではありません。文章が与えられた際の文章内の単語頻度などといった共起性からトピックを機械的に見つけることになります。

このトピックは単語や文章ごとに設定することができ、トピックモデルを用いることで文章内の単語や文章そのもののトピックを得ることができます。

さらに、このトピックを使うことで文章や単語の類似性を簡単に判断できるようになります。

単語の類似度がわかる?

例えば、レストランに特化したニュースサイトのトピックモデルを作ったとします。その中でカルボナーラとアラビアータと寿司の特集がそれぞれ別々の記事で掲載されていました。

トピックという単位で考えた場合、カルボナーラとアラビアータと寿司は似ているでしょうか?

トピックモデルの学習に使う文章によっても変わってきますが、トピックとして

  • 和食レストラン
  • 中華レストラン
  • 洋食レストラン

が学習されているとします。

この時

  • カルボナーラは洋食レストラン
  • アラビアータは洋食レストラン
  • 寿司は和食レストラン

となります。

よって、レストランで考えるとにはカルボナーラとアラビアータは似ていて、カルボナーラと寿司は似ていないとなります。

他にも色々ありますが、このようにトピックという単位で類似度を測れることがトピックモデルの利点になります。

まとめ

今回は、簡単にトピックモデルで使われるトピックについて解説してみました。単語の背印材的な意味がトピックであり、それは共起性によって発生することを話しました。

レストランの例を発展させると、レストラン検索サイトでのトピックによる柔軟な検索サービスなどができると思います。そのように考えると、他にもいろいろな応用が考えられて楽しい分野だなと感じます。

数学的なトピックモデルの形式はこれから解説していきたいと思いますが、まずはアプリケーションを作るなどして、応用についても一緒に考えていきたいと思います。

黒歴史のメリット(ゲーム作り編)

こんにちは,最近技術を学んでも自分の言葉にするのが難しくてブログを更新していませんでした.なので今日は学生時代のゲーム制作に感じたことについて書いていきたいと思います.

結論は学生時代に黒歴史なゲームを作ることはそれ以降のゲーム作成で確実にメリットになるということです.

はじめに

黒歴史とは,過去何も知らない頃に起こした出来事や物事の事です.後で見返してうわぁ...と思ってしまうものです.何も知らないのですからそう感じるのも当たり前です.例えばゲームの改造についてネット掲示板で聞くとかそんなものですね.

ゲーム作成は本記事ではc++DirectXを使ってゲームを作ることです.今の世の中とてもすごいゲームが開発されています.個人で作れるゲームというのはたかが知れていますが,誰でも始めは簡単なゲームから作っていきます.

学生時代のゲームが黒歴史になるまで

学生時代は自分の作りたいゲームを作っていきます.僕もFPSゲームとか無双をモチーフにしたアクションゲームなどを作りました.これらのゲームは個人で作っているので棒人間が出てきたり,無駄に入り組んだステージにしたりするんですよね.そしてそのままの状態で就活に入っていきます.

ゲームを作るのが好きだったので就活ではゲーム業界を希望しました.ゲーム会社では製作物を使った面接が良くあります.自分が良しと思ったゲームを持っていって,見せて,頑張って,解説します.面接官も自分の作ったゲームを理解しようよ実際にやってくれますが,自分本位で作ったゲームはだいたい面接官がうまく操作できず微妙な雰囲気になります.

僕の場合は坂を下っていくようなアクションゲームを見せたのですが,ジャンプの仕方やスキルの使い方が分かりづらくて穴に落ち続け,微妙な雰囲気になりました.

フラッシュバック

これを黒歴史というかはわかりませんが,この微妙な雰囲気って結構きついんですよね.その時はそれで終わっても,あとで布団の中で後悔します.そして,ふとした瞬間に頭の中で出てきて,眠れない夜を過ごしたりします.

でもこれは,とてもいいことだと思います.ゲームを作っているときに操作をしていて思い出します.今作っているゲームをあの時の面接官にやってもらったら,また沈黙が生まれるんだろうなって.

この感覚はゲーム作りで大切なものになります.そしてこの感覚を手に入れることができるのは学生のうちだけだともいます.それは作りたいものを作っているからです.会社に就職してみんなで面白いゲームをつくって,確かに達成感や技術は上がると思います.でも,いざ一人で始めたときにゲームの操作性の不自由さも自分の熟練度などで忘れてゲームを作ってしまいます.ゲーム作成時に思いとどまって改善できるのはフラッシュバックがあるから,つまり黒歴史があるからだと思います.

まとめ

長々と書いてしましたが,実はこのブログも文章を書く練習になっています.たぶん来年あたりにこれを読んで黒歴史に感じていると思います.うまく自分の気持ちを伝えられない.相手が理解してくれない時の沈黙.これをまた感じることになります.そして文章を書くたびにフラッシュバックしてきます.でもそのフラッシュバックなしにはいいものは作れません.そしてフラッシュバックを作るために実際にゲームを作るなどの挑戦も必要です.僕はこのフラッシュバックを大事にしていきたいと思います.

サポートベクターマシーンを基礎から読んでみた

こんにちは,今日もコロナ社から出版されている自然言語シリーズの自然言語のための機械学習入門をよんだので,それについて書いていこうと思います.

はじめに

サポートベクターマシンSVM)は一時期すごくはやっていましたね.今はニューラルネットワークが話題ではありますが,原理的な解析ができることからSVMを使う人も多いそうです.

SVMは二値分類を行います.たとえば,身長体重から女性か男性かみたいな問題です.それを応用して複数分類や回帰問題に発展させていることも多いようです.

SVMが良く使われる理由は全体的に良い分類を行ってくれるからだそうです.といってもよくわからないと思います.ニューラルネットワークなどは与えられた値からその値を分類するように頑張るのですが,SVMは与えられた値以外にも対応する性質を持った分類を行ってくれます.その秘密は二つのクラスがあった場合に「どちらのクラスからもなるべく遠い位置でわける」というマージン最大化という仕組みを導入しているからです.今回は,そのマージン最大化について説明して,SVMを実際に解いていこうと思います.

分類の方法

いま,あるデータxに対して正解となるクラスy(+1 or -1)が与えられているとき,それらデータをクラスで分ける平面をwと仮定して,平面で分離する式を以下のように定義します.

{
f(x) = w \cdot x - b ≧ 0
}

つまり,fはxが入力されたときに0以上ならクラス(+1)に未満ならクラス(-1)に属するということです.マージン最大化とはこの平面と各クラスの最も近いデータとの距離の最大化のことを言います.

マージン最大化

データを分離する平面に最も近いデータを{x_+}として,データから平面に垂線を伸ばした時の交点を{x_*}とする.ここで,{x_*}は平面上にあるため,{w \cdot x_* = b}となります.

パラメータbを調節することで平面を移動させることができます.よって{ w \cdot x_+ -b = 1 }となるような平面を仮定すると,

{
w \cdot ( x_+ - x_* ) = w \cdot x_+ - w \cdot x_* = (b + 1) - b = 1
}

と,することができ,{w}{x_+ - x_*}が同じ方向を向いていることから,

{
w \cdot ( x_+ - x_* ) = |w||x_+ - x_*| = 1  \\ |x_+ - x_*| = \frac{1}{|w|}
}

となります.つまり,マージン{|x_+ - x_*|}の距離は{\frac{1}{|w|}}となり,これの最大化がSVMの解く問題になるということです.

厳密制約でのSVM

厳密制約というのはデータが過不足なくクラスに分けられている状態でのSVMの学習ということです.実際は外れ値や選択する特徴の表現不足で厳密なデータを用意するのは難しいですが,実践への導入として解説したいと思います.

先ほど,解くべき問題は{\frac{1}{|w|}}の最大化といいましたが,これは扱いにくいので,{|w|}の最小化として,さらに,絶対値は扱いにくいので{w^2}の最小化とします.解くべき問題は変わっていません.

先ほど仮定した{ w \cdot x_+ -b = 1 }を満たすために,クラス(y=+1)のときは{f(x)≧1}であり,クラス(y=-1)のときは{f(x)≦-1}を満たす必要があるとすると,二つの条件は以下のようにまとめることができる.

{
y^{(i)}(w \cdot x^{(i)} - b) ≧ 1
}

よって,以下の最適化問題を解くことになる.

{
min.   \frac{1}{2}w^2 \\
s.t.   y(w \cdot x -b) -1 ≧ 0; \forall i
}

この不等式制約付き最適化問題は凸問題であるので,ラグランジュ方程式を用いてデータ数分だけラグランジュ乗数{α_i}を導入すると,ラグランジュ関数は以下のようになります.

{
L(w,b,α) = \frac{1}{2}w^2 - \displaystyle \sum_i α_i(y^{(i)}(w \cdot x^{(i)}-b)-1)
}

これをそれぞれのパラメータで偏微分して0とおくと

{
\frac{\partial L}{\partial w} = w - \displaystyle \sum_i α_i y^{(i)} x^{(i)} = 0\\
w = \displaystyle \sum_i α_i y^{(i)} x^{(i)} \\
\\
\frac{\partial L}{\partial b} = \displaystyle \sum_i α_i y^{(i)} = 0
}

これを,ラグランジュ関数に入れると以下のようにαのみの関数となり,変形することができる.

{
\begin{align}
L(w,b,α) &= \frac{1}{2}\sum_{i,j} α_i α_j y^{(i)} y^{(j)}  x^{(i)} \cdot x^{(j)} - \displaystyle \sum_i α_i(y^{(i)}(\displaystyle \sum_j α_j y^{(j)} x^{(j)} \cdot x^{(i)}-b)) + \displaystyle \sum_i α_i \\
&= -\frac{1}{2}\sum_{i,j} α_i α_j y^{(i)} y^{(j)}  x^{(i)} \cdot x^{(j)} + b \displaystyle \sum_i α_i y^{(i)} + \displaystyle \sum_i α_i \\
\end{align}
}

これでもともパラメータがなくなったので,あととはラグランジュ関数を最大にするαをもとめることで,はじめにもとめた,分類関数f(x)を求めることができます.しかしこの問題は二次計画問題となり解析的に解くことが難しくなっています.なので逐次的に解くなど工夫する必要があります.

おわりに

SVMで一番難しい,というかわかりづらい概念は{ w \cdot x_+ -b = 1 }となるような平面を仮定するところだと思います.これは,平面を平行移動して距離関数が1となるような制約が必要という意味になります.そのため,ラグランジュ関数の制限の項で用いられています.距離は絶対値であるので+方向-方向でも同様に1にするためにラベルを+1,-1とすることが大事であるといえます.今回は厳密回を求めましたが,通常はそのような式は使えません.また,今回は線形分離を行いましたが,カーネルトリックを利用した非線形分離にも拡張することができます.今後そのような例も解説していこうと思います.

自然言語のナイーブベイズ分類を考えてみた

こんにちは,今日もコロナ社から出版されている自然言語シリーズの自然言語のための機械学習入門を読んでみましたので簡単に内容をまとめたいと思います.

初めに

 
 分類問題は事前に定義されたグループに分類対象を振り分ける処理のことを言います.たとえば,迷惑メールのフィルタリングみたいなものです.迷惑メールの文章からどのような文章が迷惑メールなのかを学習し,迷惑メールかどうかの判断をします.この分類はいくつか提案されていますが,ここでは,ナイーブベイズ分類,SVMを用いたもの,対数線形モデルを用いたもののうちのナイーブベイズ分類について解説したいと思います.

ナイーブベイズ分類とは?

 ナイーブベイズ分類は文章の出現頻度をモデル化することによって分類を行います.ナイーブベイズのモデル化はベルヌーイ分布を用いたものと多項分布を用いたものがあります.ベルヌーイ分布は文章内に単語が存在しているかいないかで分類をおこないますが,多項式分布は文章内に単語がどれほど存在しているかで判断しています.そこで,今回は認識精度の面から多項分布でのモデル化について解説します.

問題の数式化

 
 まず初めに求める問題を定式化します.分類ですので,ある分類したいクラスC(スポーツや政治)に文章dが当てはまるかどうかが重要になります.つまり,文章dが与えられたときにクラスCである確率を求めます.そして,以下のようにベイズの法則からCを求める式を算出します.

{
P(c|d) = \frac{P(c)P(d|c)}{P(c)}
}

{
c_{max} = \displaystyle \arg \max_c \frac{P(c)P(d|c)}{P(c)}
      = \displaystyle \arg \max_c P(c)P(d|c)
}

ほんとうは,P(c|d)を求めたいのですが,dは文章ですので組み合わせが膨大になります.そこで,P(d|c)という問題へと変換しました.

多項モデル

多項式分布を覚えていますか?多項式分布では発生確率を持つ単語が文章内に複数回発生したときの文章の発声確率をモデル化できました.これをクラス内単語の発生確率が複数回発生したとして文章の発生確率をモデル化しものが多項モデルです.文章dの中に単語wが{n_{w,d}}回起こる確率は,多項分布を用いて以下のように決まります.ここで,{q_{w,c}は属するクラスがcであったときに単語wが発生する確率です.

{
\frac{(\displaystyle \sum_w n_{w,d})!}{\displaystyle \prod_{w \in V}n_{w,d}!} 
\displaystyle \prod_{w \in V} q_{w,c}^{n_{w,d}}
}

これで,クラス内にある単語が発生する確率を求めることができたので,クラスCに単語が属する確率P(d|c)は以下のようになります.

{
P(d|c) = P(K=\displaystyle \sum_w n_{w,d}) \frac{(\displaystyle \sum_w n_{w,d})!}{\displaystyle \prod_{w \in V}n_{w,d}!} 
\displaystyle \prod_{w \in V} q_{w,c}^{n_{w,d}}
}

つまりは,これを用いると,以下の式を最大にするようなクラスCが文章dの属するクラスということになります.

{
c = \displaystyle \arg \max_c P(c)P(d|c) 
= \displaystyle \arg \max_c P(c)P(K=\displaystyle \sum_w n_{w,d}) \frac{(\displaystyle \sum_w n_{w,d})!}{\displaystyle \prod_{w \in V}n_{w,d}!} 
\displaystyle \prod_{w \in V} q_{w,c}^{n_{w,d}}

}

実際には最尤推定を用いて確率の値を求めていきます.今回は解き終わった結果を見てみたいと思います.

{
P(c) = \frac{N_c}{\displaystyle \sum_c N_c} \\
q_{w,c} = \frac{ n_{w,c} }{\displaystyle \sum_w n_{w,c} }
}

P(c)はあるクラスに属する文章の数を全体の文章の数で割っていて,{q_{w,c}}はクラスcに属するある文章の出現回数をクラスcに属する全ての文章の出現回数を割っていて,直観的だとわかります.

おわりに

分類問題は自然後処理の中でも特に応用範囲が大きいものだと思います.迷惑メールの他にも品詞の分類などがあります.ナイーブベイズ分類は分類問題の中でも直観的にわかりやすいモデルになっています.そのため結果の原因の特定が容易にできるためいまもよく使われているみたいです.今回は最尤推定を使って分布の確率を求めましたが,ある確率が0になってしまい全体として正常に動作しない問題が発生することもあるため,実用の場合はMAP推定を用いてディクレ分布を事前分布として計算すると良いそうです.

ゲームに用いるなら

プレイヤーがNPCと話せると仮定したときに,話した内容で相手がどう感じるのかを分類器として作成して置いたら,感情で会話できるようなシステムができるかなって感じました.そうしたら,ボスまでの道を教えてくれる情報屋さんをどう懐柔するかなど,ゲームにおける会話の幅が広がると感じました.

ひさびさにビジネス書を読んでみました

こんにちは,今日は「稼ぎたければ捨てなさい」という本を読んで見た感想と思ったことを書いていきたいとおもいます.

はじめに

 この本は起業するうえでの心得のようなものが掛かれていました.内容は集客についてが多い印象でした.僕がこの本から読み取ったことは「今の事業に対する考え方」「見込み顧客とは」「成功パターンの考え方」についてです.内容はどこのビジネス本でも言っていることで多いです.まとめると,「顧客をしっかり固定してその人に合った集客を行う」ということです.

今の事業に対する考え

 終戦から現代までの事業は「いいものを作る」という方針でした.粗悪品が多く,いいものを作ると売れる時代ということです.現代について考えると,製作技術の発展から100円ショップでもかなりのクオリティのものが売られています.そのような現代で重要となるのは誰に届けたいかを明確にする.そして,その人に合った事業に集中することです.スマホを例にとると,たくさんの良い機能を持ったスマホは売れません.それは技術の押し付けだからです.購入者が必要なのは自分が使う機能だけであり,自分がそれを使っている未来を想像できるものが売れるものになります,なので,今の時代は届けたい人を明確にし,一つの重要な機能に集中することが大切になります.

見込み顧客

 誰に売るのかを考えるときに見込み顧客という概念が登場します.見込み顧客は自分の商品に興味を持ってくれる人ではなく,買ってくれるような人となります.例えばSNSゲームを長時間やっているが課金は絶対にやらない人がいます.対してゲームは長時間やらないが好きで課金をよくする人がいます.ここで言う見込み顧客というのはゲームに興味がありかつ課金に対する抵抗が少ない人の事を言います.そのような顧客の集客は競合他社,類似市場と集客していく必要があります.

成功パターン

 高齢者向けの事業をSNSで宣伝しても効果はありませんがチラシによる集客は効果があります.デジタルの時代に流されず事業の見込み顧客にあった集客が大切になります.集客にはいろいろなパターンがあります.SNS,チラシ,セミナー,ブログいろいろ試してみてやっと着いた顧客の共通点にあうような集客が大切になります.小さくてもいいので要は成功事例があればそれが自分にとっての成功パターンということです.これは,小さい範囲にも言えます.技術的なアプリの宣伝のためにブログを書くのであれば,Qiitaのような技術に興味がある人が多く集まるサービスで宣伝すると受けがいい,など考える必要があります.

終わりに

 ビジネス本は久しぶりに読みました.文章の言葉遣いに違和感がありましたが,内容をまとめると集客できそうな分野に対して事業を行っていくことが必要というようなことが書かれています.それは守銭奴になるということではなく,その分野に価値を求めている人が多いということ.そして,その人たちからお金を奪うのではなく,価値を届けることが企業の目的になってくるということです.また,そうすることで,道に迷うことなく,その人たちに一番効果的に届く方法をを知れると思いました.
 他にも「人間の脳の構造から同アプローチしていくか」,「Uberが何で売れたか」など面白い内容も多く面白い内容だったと思います.

クラスタリングについて読んでみた

こんにちは今日もコロナ社から出版されている自然言語シリーズの自然言語のための機械学習入門を読んでみました.クラスタリングは文章の性質の違いを明確にするために使われることがあるようです.

はじめに

 クラスタリングはデータを似た者同士で分けることです.分類との違いはわける数(クラスタ数)が決まっていない点です.データの性質の違いでクラスタリングができれば,その性質によって異なる処理を効率的に行うことが可能となります.クラスタリングの種類としては「凝集型クラスタリング」「k-平均法」「混合正規分布」などがあります.また,混合正規分布などはEMアルゴリズムという枠組みの一部です.

凝集型クラスタリング

 データがある空間に分布しているとき,個々のデータ間の関係から階層関係を作り出すクラスタリングです.データが徐々にまとまっていくことからボトムアップクラスタリングとも呼ばれています.概念図を以下に示します.

f:id:tkymx83:20170228211035p:plain:w300

”近いもの”を併合していき,併合の回数を階層数とした木構造を作り出します.併合の回数を任意にすることでクラスタリング数を管理することができます.

この”近いもの”はデータ間の距離になっています.データは併合が進む毎に集合となっていきます.そして,この集合通しの併合の仕方(集合の類似度関数)がいくつか定義されています.

  • 単連結法

 集合の各データどうしの類似度で最も大きいものを集合の類似度とします.

  • 完全連結法

 集合の各データどうしの類似度で最も小さいものを集合の類似度とします.

  • 重心法

 集合の各データの平均の類似度を集合の類似度とします.

凝集型クラスタリングでは,集合どうしの類似度が最も大きいものから合体していくため,単連結法では鎖状に伸びる傾向があり,完全連結法では円状に大きくなる傾向があります.これら方法はタスクによって使い分けることが重要となります.

k-平均法

 ラスタリング数を任意で決め,適当にデータをわけ,徐々に良いクラスタリングを行っていく方法です.各クラスタは平均ベクトルを持っていて,二段階のクラスタリングを繰り返し行っていきます.一段階目では,データは最も類似した平均ベクトルをもつクラスタに所属します.二段階目では,クラスタの平均ベクトルをクラスタ内データの平均として計算します.これを収束するまで繰り返すことでクラスタリングをおこなっていきます.k-平均法はよく使われるアルゴリズムですが,クラスタ数は固定なので適切なクラスタ数の選択が必要になります.

混合正規分布

 k-平均法では,データはどれかのクラスタに必ず属していました.しかし,80%はクラスタ1で20%はクラスタ2という場合もあると思います.これを実現するために各クラスタ正規分布で表現しデータはクラスタまでの距離からそのクラスタである確率p(c|x)を持ちます.このP(c|x)はデータxがクラスタcに属している確率を表しており事後確率となり計算が困難になります.そこで,P(x|c)としてクラスタcでのデータxの発生確率(正規分布)を以下のように仮定して

{
 P(x_i|c) = \frac{1}{\sqrt{ (2\piσ^2)^d }} \exp ( -\frac{|x_i-m_c|^2}{2σ^2} ) 
}

以下のようにベイズの定理から事後確率の変換をおこないます.

{
P(c|x_i) = \frac{P(x_i,c)}{P(x_i)} = \frac{P(c,x_i)}{\displaystyle \sum_c P(c,x_i) }
= \frac{P(c)P(x_i|c)}{\displaystyle \sum_c P(x)P(x_i|c)}
= \frac{P(c)\exp (-\frac{|x_i-m_c|^2}{2σ^2})}{\displaystyle \sum_c P(x)\exp (-\frac{|x_i-m_c|^2}{2σ^2})}
}

データxの生起確率は複数の正規分布からなっており,混合正規分布と呼ばれます.また,今回の例では,分散σは固定であり,クラスタごとの平均ベクトルmcのみ変化するとしています.

次に「各クラスタの平均ベクトル」を算出します.k-平均法では各クラスタ内データの平均を求めていました.混合正規分布を用いる場合は,以下のように,全てのデータの重み付平均を求めることになります.

{
m_c = \frac{ \displaystyle \sum_{x_i \in {\bf D}} P(c|x_i)x_i }
           { \displaystyle \sum_{x_i \in {\bf D}} P(c|x_i)}
}

のように計算されます.このように新たな正規分布を更新することでクラスタリングを進めていきます.

EMアルゴリズム

 k-平均法も混合正規分布もに二段階のクラスタリングを行っていました.混合正規分布を例にとると,確率の計算(正規分布)とパラメータの推定(平均ベクトル)を繰り返していました.このような枠組みをEMアルゴリズムと言います.

 もし,データxiが属するクラスタcが分かっていた場合,以下の最尤推定で分布のパラメータ(正規分布の平均や分散など)を求めることができます.

{
\displaystyle \sum_{x_i \in {\bf D}} logP(c,x_i;θ)
}

しかし,初めはデータxiの属するクラスタcはわかりません.なので,代わりにすべてのクラスタに対して確率P(c|x)を重みとして以下のように尤度を足し合わせたものを最大化します.

{
\displaystyle \sum_{x_i \in {\bf D}} \displaystyle \sum_c P(c|x_i;θ')logP(c,x_i;θ)
}

ここで,θ'は事前に計算されたパラメータ(計算始めは初期化される)です.この関数はQ関数と呼ばれ,前のパラメータθ'と今のパラメータθを区別して以下のように定義されます.

{
Q(θ;θ') = \displaystyle \sum_{x_i \in {\bf D}} \displaystyle \sum_c P(c|x_i;θ')logP(c,x_i;θ)
}

このQ関数を最大化するようなθを求めることでクラスタリングを行っていきます.EMアルゴリズムのEステップでは,P(c|x;θ')を計算し,Mステップではこの結果を用いてQ関数を最大にするθを求めていきます.

おわりに

 今回クラスタリングについてみていきました.始めに行っておくと,EMアルゴリズムは枠ぐみであり具体例がk-平均方や混合正規分布によるクラスタリングとなります.なので,EMアルゴリズムを扱うライブラリというのは存在しません.凝集型クラスタリングは局所的な合体から始まることから大局的なクラスタリングが難しくなります.対してEMアルゴリズムを用いる繰り返しの方法は大局的なクラスタリングができます.しかし,クラスタ数の選定という問題も生じます.なので,クラスタリングが本当にうまくいったのかという評価基準(自分のタスクに合った)をじっくり考えることが大事になると思います.