実用アルゴリズム の 基礎。

〇  「動的計画法」と機械学習の基礎「類似度」を知る。

「動的計画法」の レーベンシュタイン距離。

多くの人にとって、アルゴリズムの学習の最初の壁となるのが、「動的計画法」ではないでしょうか。動的計画法は、「問題の部分的な結果を記録・利用しながら、最終的な結果を求める」手法の総称です。クイックソートや深さ優先探索のような手法よりも、1 段か2段、抽象的な概念である点と、アルゴリズムを可視化しにくい点が、難しく感じる原因なのだと思われます。また、“動的計画法”という名称が内容に合っていないことも、動的計画法をわかりにくくしていると言えるでしょう。

しかし、多くの有用なアルゴリズムは動的計画法の手法を使っているので、避けて通ることはできません。

ここでは、動的計画法で「レーベンシュタイン距離」（編集距離）を求める例を通して、動的計画法とレーベンシュタイン距離の両方を解説します。レーベンシュタイン距離とは、2つの文字列の類似度を表す数値です。

動的計画法でレーベンシュタイン距離を求める過程では、問題の部分的な結果を記録するための“表”が出てきます。この表は、動的計画法の過程をわかりやすい形で可視化したものと言えます。この表を見ることで、動的計画法を視覚的にも理解できるようになると思います。

「うさぎ」と「うなぎ」の距離は1。

前述したように、レーベンシュタイン距離は2つの文字列の類似度を表す値です。値が0の場合、2つの文字列は同じで、値が大きくなるほど2つの文字列の類似度は低い、ということになります。例えば、「うさぎ」と「うなぎ」のレーベンシュタイン距離は1、「うさぎ」と「ねこ」のレーベンシュタイン距離は3です。「うさぎ」と「うなぎ」は似ていますから1で、「うさぎ」と「ねこ」は全く似ていませんから3、という結果は直感にも合致するものだと思います。レーベンシュタイン距離を使うと、2つの文字列の類似度を明確な数値で表せるので、自然言語処理の分野でいろいろと便利なのです。

レーベンシュタイン距離の算出は簡単です。1文字の「挿入」「削除」「置換」の操作を行って、一方の文字列をもう一方の文字列に変えるのに、最小何回の操作が必要かを考えるだけです。その最小の操作回数がレーベンシュタイン距離になります。

例えば、「うさぎ」を「うなぎ」に変えるには、「さ」を「な」に「置換」するだけです。操作は1回なので、レーベンシュタイン距離は1です。

「うさぎ」を「ねこ」に変えるには、「う」を「ね」に「置換」し、「さ」を「こ」に置換し、「ぎ」を「削除」する必要があります。操作は3 回なので、レーベンシュタイン距離は3です。

表を使って計算する。

では、動的計画法で「うさぎ」と「うなぎ」のレーベンシュタイン距離を計算してみましょう。まず、「うさぎ」と「うなぎ」の文字列から、図1のような表を作ります。0から3の値を図1のように設定する点が重要です。

図1、レーベンシュタイン距離を求めたい2つの文字列からこのような表を作る。

次に、左上の空白のマスから、次のルールで値を書き込んでいきます。

「う」行と「う」列の空白のマスであれば、図2のようになります。

図2、ルールに従って、空白のマスの値を計算して、結果をマスに記録しておく。

この作業を繰り返していくと、最終的に図3の表になります。そして、この表の右下のマスの値が、レーベンシュタイン距離になっています。まさに、問題の部分的な結果を記録・利用しながら、最終的な結果を求めています。

図3、表が完成。レーベンシュタイン距離を算出できた。

レーベンシュタイン距離を求めるlevenshtein関数とその利用例をリスト1に示します。levenshtein関数の中身は、図1から図3で説明した通りの内容です。このリストでも「うさぎ」と「うなぎ」のレーベンシュタイン距離と、「うさぎ」と「ねこ」のレーベンシュタイン距離を求めています。実行結果は次の通りです。

リスト1、レーベンシュタイン距離を求めるlevenshtein関数とその利用例のプログラム。

 

 

 

表の中身も表示しています。動的計画法の過程を確認してみましょう。

［機械学習］ コサイン類似度。

「コサイン類似度」は、機械学習で使われる最も基本的なアルゴリズムの一つです。コサイン類似度を使うと、2つのデータの類似度を計測できます。

コサイン類似度の求め方は簡単です。例えば、[a₀,a₁]と[b₀, b₁]という2つのデータがあるとき、これらをベクトルと考え、図1の式の計算を行います。このcosθの値がコサイン類似度になります。

図1、コサイン類似度の計算式。

図形的には、2つのベクトルのなす角θのcosθがコサイン類似度です（図2）。

図2、2つのベクトルのなす角θのcosθがコサイン類似度。

コサイン類似度の値は-1から1の範囲で、「1に近いほど2つのデータは似ている」、「-1に近いほど2つのデータは似ていない」と解釈します。

コサイン類似度の利用例。

コサイン類似度の簡単な利用例を示しましょう。

表1は、ある商店の長年のお得意さん12人（顧客番号0～11）の香水とネクタイの年間売り上げのデータです。

表1、ある商店の長年のお得意さん12人（顧客番号0～11）の香水とネクタイの年間売り上げのデータ。

さて最近、新しいお得意さんのデータも入手できました。新しいお得意さんの香水の年間売り上げは50で、ネクタイの年間売り上げは51でした。では、この新しいお得意さんの消費行動に最も近い長年のお得意さんは誰でしょうか？

このような問題は、長年のお得意さんの各データと新しいお得意さんのデータのコサイン類似度を計算して、最も1に近い組み合わせを求めるだけで解決します。この問題を解くプログラムはリスト1のようになります。

リスト1、長年のお得意さんの各データと新しいお得意さんのデータのコサイン類似度を求めるプログラム。

リスト1のcos_similarity関数は、図1の式をそのままコードにしたものです。この関数を使って長年のお得意さんの各データ（ec_data）と新しいお得意さんのデータ（newc_data）のコサイン類似度を計算し、1に近い順にソートして結果を表示しています。

リスト1の実行結果は図3のようになります。結果を見ると、新しいお得意さんの消費行動に最も近いのは顧客番号2のお得意さんであることがわかります。

図3、リスト1の実行結果。

データの次元が増えても同じように計算できる。

ここまではデータの要素が2個（香水とネクタイ）、すなわち2次元の例で説明しましたが、データの要素がどれだけ増えても、コサイン類似度は同じように計算できます。データの要素がn個、すなわちn次元の場合のコサイン類似度の式は図4のようになります。

図4、n次元の場合のコサイン類似度の計算式。

データの要素が4個以上（4次元以上）になると、ベクトルはもちろん、ベクトルのなす角も可視化できなくなります。ただし、本質的には2次元の場合の図2と同様です。リスト2は、2つの4次元のデータ（ベクトル）のコサイン類似度を求める関数の実装例です。このcos_similarity_4d関数を使って、例えば、[-8, 15, -8,-21]と[11, -20, 9, 15]のコサイン類似度を求めてみましょう。

 

リスト2、2つの4次元のデータ（ベクトル）のコサイン類似度を求める関数の実装例。

実行すると、-0.9563980820525706と表示されます。-1に近いので、2つのデータは似ていないとわかります。