第 3 章 実用化システムと研究プロジェクト
3.1 オントロジーを用いた TV 番組グラフ作成システム
3.1.4 番組間の関連度計算アルゴリズム
2つの番組間の距離を数式(1)のように定義する。
)) 2 , 1 ( ( ) 2 , 1 (
1
p p D w p
p
R
in
i
∑
i=
=
(1)) 2 , 1 ( p p
R
は番組p 1
と番組p 2
の距離を定義している。nは観点の異なるオントロ ジーの数を示す。D
i( p 1 , p 2 )
はi
番目のオントロジーによって導き出された番組p 1
と 番組p 2
の間の距離である。w
iはi
番目のオントロジーによる 2 番組間の距離への重 みを示す。(2) 番組間の関連度計算方法
まず、特定の番組の EPG 情報から所定のキーワードを抽出する。次にキーワード を基にオントロジーを探索し、その番組が所属するクラスを取得する。そして、2 つ の番組が所属するクラス間の距離を計算する。尚、今回の実装においては隣接するク ラス間の距離は一律 1とし、同一クラス間に所属した番組間の距離は1、親クラスと 子クラスに別れた番組間の距離は2、兄弟クラスに分かれた番組間の距離は3として いる。
表3.1.1 EPG例
図3.1.6 オントロジーと番組
例として、表3.1.1にEPG情報の一部を示す。表3.1.1の1から5までの番組から 出演者やジャンル、地名のキーワードを抽出すると、番組は図 3.1.6 のようにそれぞ れのオントロジーのインスタンスとしてマッピングできる。表3.1.2に図3.1.6に示す 番組間のオントロジー毎の距離計算結果を抜粋した。
作品オントロジー 出演者オントロジー 地名オントロジー
“CSI Crime Scene Investigation” と
“ CSI New York” の距離
1 6 3
“CSI New York” と
”Apollo 13”の距離
5 2 6
“Sleepless in Seattle” と
”Grey’s Anatomy”の距離
3 6 1
表3.1.2 オントロジー別番組間の距離
(3) 重み付けによる関連度の変化
式(1)で定義したように 2 番組間の関係はそれぞれのオントロジーでの距離を合計 したものとなる。そのため、さまざまな観点での距離は結果としてなぜ似ているのか という理由があいまいになってしまうことがある。さらに、どの観点を重視するかは ユーザによって異なる。出演者を重視する人もいればジャンルを重視する人もいる。
表3.1.3に、表3.1.2の値に基づいて、重みの組み合わせを変えて計算した番組間の関
連度を示す。赤い○で囲んだ値が、それぞれの重みの組み合わせにおける番組間の関 連度の最小値(最も似ている 2 番組)である。このように重みを変更すると、関連度が 異なってくることが分かる。本システムでは、重み変更機能を用いることでユーザ毎 に重視する観点をカスタマイズすることができるようになっている。
作品 1 出演者 1 地名 1
作品 2 出演者 1 地名 1
作品 1 出演者 2 地名 1
作品 1 出演者 1 地名 2
“CSI Crime Scene Investigation” と
“ CSI New York” の距離
10 11 16 13
“CSI New York” と
”Apollo 13”の距離
13 18 15 19
“Sleepless in Seattle” と
”Grey’s Anatomy”の距離
10 13 16 11
表3.1.3 重み付けによる番組間関連度の変化
(4) 距離計算の高速化
重み付けを調整した時にリアルタイムに番組間の関連度を再計算するためには、オ ントロジーの大きさに左右されない高速な計算速度が必要となる。多くの場合、オン トロジーは階層構造となっており、計算の度に階層関係をたどっているとオントロジ
ーが大きくなるにつれて計算時間がかかってしまう。そこで階層をたどる回数を減ら すため、ルートから各クラスまでの距離を予め計算しキャッシュしておく。図 3.1.7 の例では、映画Aと映画Bの距離は映画Aが所属するクラス C9と映画Bが所属す るクラスC7の距離である。ルートからクラスC9までのパスP1、ルートからクラス C7までのパスP2を計算しておき、P1とP2の共通パスをP3とすると、P1とP3の 差分とP2とP3の差分を合計した値がC9とC7の距離となる。これにより、オント ロジーの規模に左右されない関連度計算機能を実現している。3.1.6節に速度評価の結 果を示す。
図3.1.7 ルートまでの距離のキャッシュ
3.1.5 番組へのタグ付けとネットワークを介した共有機能