DEIM Forum 2013 D3-2

手順の対応関係に基づくハウツー情報の階層化
湯本 高行†† 兵庫県立大学大学院工学研究科 〒 671–2201 兵庫県姫路市書写 2167
E-mail: †yumoto@eng.u-hyogo.ac.jp
あらまし

料理のレシピなどのハウツー情報を検索する需要は高いが，ハウツー情報に特化した検索・閲覧手法は実現されていない．そこで本研究では，ハウツー情報の検索結果を，手順の対応関係に基づいて階層化する手法を提案する．ここで手順とはハウツー情報を構成する単位であり，動作とその対象のペアとして表現する．2 つのハウツー情報の間で手順の対応関係を求め，これに基づいて関連度を計算する．関連度は共通度，被覆度，ばらつき度を用いて定義される．この関連度の大小関係に基づき，ハウツー情報を階層化する．この階層化では関連するハウツー情報の集合が 1 つのツリーを構成し，深い階層にあるハウツー情報ほど詳しい情報を含む．
キーワード

ハウツー情報，手順，情報検索，情報抽出

Takayuki YUMOTO†† Graduate School of Engineering, University of Hyogo
2167 Shosha, Himeji, Hyogo, 671–2201 Japan
E-mail: †yumoto@eng.u-hyogo.ac.jp

1. は じ め に
近年，Web 情報検索は一般的になり，その用途も多様化して

2. 関 連 研 究
我々の研究では，ハウツー情報検索・提示は以下のような段いる．中村らの 2006 年の調査によると，検索した時に知ろう階に分けて実行する．としているものの中で「方法・手段」は「検索キーワードの意（ 1 ） ハウツー情報の収集・抽出

味・定義」や「もの」に次いで多く，1000 人中 575 人がよく（ 2 ） ハウツー情報のモデル化検索すると回答している [1]．すなわち，方法や手段などのハウ（ 3 ） ハウツー情報の提示

ツー情報に対する需要は高いと言える．

それぞれに対して関連研究をまとめる．

これに対して，ハウツー情報のうち，レシピなど一部のドメ

2. 1 ハウツー情報の収集・抽出インに特化した検索エンジンやハウツー情報のみを登録できる検索対象を特定のサイトに限定しない場合には，まずハウサイトなどは存在するが，ハウツー情報を自動的に収集したり，ツー情報の収集が必要になる．多くの場合，Web 検索を行うこ閲覧を効果的に行う手法については不十分な状況にある．野中とになるが，検索クエリによっては，ハウツー情報以外に本のらはハウツー情報を効率的に発見するために，Web ページから目次やショッピングサイトのページが含まれたり，むしろハウハウツー情報を抽出し，見やすさによってランキングする手法

ツー情報以外のページが占める割合の方が多くなってしまうこを提案している [2]．しかし，この手法では，同じキーワードをとがある．これに対して，あらかじめドメインを限定すること含むハウツー情報でも内容が異なるものが含まれる可能性があができれば，小久保らの検索隠し味 [3] のように機械学習を用り，1 次元のランキングでは不十分であると考えられる．

いることによってハウツー情報を多く含むようにクエリ拡張を

そこで本研究では，ハウツー情報の検索結果に対して，関連行い，ハウツー情報の収集効率を向上させることができる．このあるハウツー情報を階層的にまとめてツリーのリストとしてれに対して，野中らはハウツー情報の抽出を同時に行うことで提示する手法を提案する．作成するツリーでは，深い階層にあハウツー情報の判定も行う手法を提案している [2]．

るハウツー情報ほど説明が詳しい．ハウツー情報間の関連は，また，ハウツー情報の抽出についてであるが，汎用的な HTMLハウツー情報の構成要素である手順の対応関係によって判定す文書からの本文抽出 [4], [5] を利用する方法が考えられる．しかる．なお，手順は動作とその対象のペアとして表現する．

し，Web ページによってはブログなどのように本文中にハウツー情報以外を含む場合も存在するため，ハウツー情報に特化した抽出手法が必要になる．これについては，野中らのように自立動詞または「する」の直前の名詞を動作とする．また，格手がかり表現を用いた手法 [2] や小澤らのようにこれに加えて助詞の「は」または「を」が続く名詞またはそれらの名詞と並機械学習を併用した手法 [6] などが提案されている．本研究で列関係にある名詞を対象とする．さらに，「を」が続く名詞よりは，ハウツー情報の収集と抽出の両方を行うため，野中らの手も「は」が続く名詞を優先することとする．なお，この段階で法を利用する．

は，対象は集合として扱う．

2. 2 ハウツー情報のモデル化（ 4 ） 省略された対象の補完：(3) の処理で対象が取得できハウツー情報をモデル化する方法であるが，これに関しては，ない場合は，以下の処理をする．

レシピについて多くの研究がなされている．Miyamori はレシ•

重文を構成する文のうち，後ろに部分から抽出された手ピなどのアイテムの妥当性を評価するために，それを構成する

順の場合は，前の部分から抽出された手順の対象によって補完材料とその分量によってアイテムをモデル化し，それを基準とする．たとえば，「野菜を切って，炒める」という文は，「野菜を比較する手法を提案している [7]．この手法では，基準はユーザ切って」と「炒める」からなる重文である．この場合，「炒める」が事前に与えるとしており，ユーザに知識が要求される．また，の対象は「野菜を切って」の対象である，「野菜」になる．

浜田らはレシピから，素材 (本研究で「対象」と呼ぶもの) と動•作をノードとする，データフローグラフを生成する手法を提案（ 5 ） 手順の分割：対象の部分が集合になっている手順を，している [8]．この手法では，レシピに特化した辞書などが必要

対象が集合でないような手順に分割する．たとえば，(炒める,となるため，ハウツー情報全般に用いることが難しい．これに{ 肉, 野菜 }) という手順を，(炒める, 肉), (炒める, 野菜) の 2

対して我々は動作と対象のペアのリストで表現する方法を提案

つの手順に分割する．

しており [9]，本研究でもこれを用いる．

上記以外の場合は，この段階では対象を確定させない．

3. 2 ハウツー情報間の関係の発見

2. 3 ハウツー情報の提示

3. 2. 1 手順間の対応関係

ハウツー情報の提示方法としては，まずランキングが考えら動作と対象がそれぞれ一致していれば，2 つの手順は対応しれる．ハウツー情報に対して有効なランキングの尺度としては，ているとみなす．動作間または対象間は以下のいずれかの条件

わかりやすさや見やすさ [2], [10], [11] を利用する方法が考えらを満たしていれば一致しているとみなす．

れる．しかし，1 つの目的に対して複数の方法が存在する場合•

は，ランキング中に方法の異なるハウツー情報が混在してしま•

日本語 WordNet [13] で同じ概念に分類される．

う．これに対して，検索結果のクラスタリング [12] によって内•Wikipedia で対象とする語と一致するリンクアンカーか形態素解析した結果の読みが同じである．

容の近さに基づき，検索結果を整理して提示する方法がある．

ら同一のページにリンクしている．

本研究では内容の近さだけではなく，内容の対応関係と詳しさ

これらの条件を同義語判定の条件と考えた場合，再現率は高いに応じて階層化を行う．

が適合率は低いことが予想される．たとえば，白川ら [14] はWikipedia データ上でリンクされる頻度を考慮することによっ3. ハウツー情報の階層化て異義語の判定を行っており，これを応用することで同義語の3. 1 ハウツー情報の抽出判定を行うことも考えられる．しかし，本研究では，判定はハWeb 検索を行い，得られた Web ページに対して，野中らのウツー情報の手順を構成する語に対して限定的に行われるため，手法 [2] によってハウツー情報の抽出を行う．我々はハウツー同音異義語などによる問題が起こりにくいと考えている．一方，情報を手順のリストとして表現する．また，手順を動作とそのハウツー情報では表記ゆれが問題となることが非常に多いため，対象のペアとして表現する．ここで，ハウツー情報を h，手順再現率を重視して，上記の条件を採用することとする．

を si (i = 1, · · · , n)，手順 si の動作と対象をそれぞれ ai , ti とすると，以下のような関係になる．

また，「入れる」，「足す」，「加える」，「追加する」についてはハウツー情報においては同じ意味で使われることが多いため，

h = ⟨s1 , s2 , · · · , sn ⟩(1)

si = (ai , ti )(2)

動作がこれらのいずれかの語どうしであれば，一致しているとみなす．
さらに，ハウツー情報の抽出の際に対象が確定していない手

手順は，文献 [9] で提案したアルゴリズムを改良し，以下のよ順についてはその手順より前に出現した対象のいずれかであれうに抽出する．

ば一致するとみなす．たとえば，i 番目の手順の対象 ti が確定（ 1 ） 文への分割：句点を基準に文に分割する．この段階でしていない場合は，対象 t1 , · · · , ti−1 のいずれかと一致するかは重文を残したままにする．

どうかで対応関係を判定する．

（ 2 ） 説明文かどうかの判定：文末の表現に注目して，過去

3. 2. 2 対象の類似性の経験について述べた文，状態について述べている文，感想な与えられた 2 つのハウツー情報が同一のものであることを保どを述べている文，疑問文などを排除することで消去法で説明証するため，使用している対象がどの程度類似しているかを事

文のみを抽出する．

前に検証する．ここでハウツー情報 h を構成する対象の集合を（ 3 ） 動作と対象の抽出：説明文を形態素解析した結果を文Th で表す．ハウツー情報 h1 , h2 の対象の類似度を以下のようの末尾から分析し，品詞のパターンから動作と対象を決定する．に定義する．

sim(h1 , h2 ) =|Th1 ∩ Th2 |max(|Th1 |, |Th2 |)(3)4= 0.80
5|T | は T に 含 ま れ る 対 象 の 数 で あ る ．こ こ で は 対 象 が 大きく異なるものハウツー情報は別の目的であると考え，

sim(h1 , h2 ) < θsim のときは h1 と h2 は別の目的であるとみなす．なお，θsim は 0 以上 1 以下のしきい値である．

図13. 2. 3 ハウツー情報間の関係
ハウツー情報間の関係を定義するにあたって，まず，2 つのハウツー情報の関連度を定義する．この関連度は方向を持ち，被覆度の例

SDmin+2222

ハウツー情報 h1 から見た h2 との関連度の強さを表現する．ま8= 0.80
10た，以下の条件を満たす場合に値が大きくなると考える．

32（ 1 ） h2 が h1 と共通の手順を多く含む．

12+SD（ 2 ） h1 と共通の手順が h2 に広く分布している．
図2

これらのそれぞれを表現するための指標を定義する．

ばらつき度の例

まず，前者を表現するために，h1 と h2 の共通度 com(h1 , h2 )られる．そこで，手順間のばらつきを表現するため，ばらつきを以下のように定義する．

com(h1 , h2 ) =度を定義する．ばらつき度は disp(h1 , h2 ) は h1 に含まれる手|h1 ∩ h2 |
|h1 |

(4)

ただし，|h1 | は h1 に含まれる手順の数，|h1 ∩ h2 | は h1 と h2に共通して含まれる手順の数である．たとえば，h1 が 4 つの手順からなり，そのうちの 3 つが h2 に含まれていた場合，順が h2 でどの程度均等に広く分布しているかを表す指標である．0 以上 1 以下の値をとり，1 の時に最も均等に出現している（ばらついている）ことを表す．ばらつき度を定義するにあたり，2 乗距離 SD(h1 , h2 ) を以下のように定義する．

SD(h1 , h2 ) =com(h1 , h2 ) = 3/4 = 0.75 である．共通度は 0 以上 1 以下の値∑

{dh2 (si , sj )}2(7)i,jをとり，この値が大きいほど 2 つのハウツー情報は共通していただし，i, j は以下の 2 条件を満たすような任意の組合せでると言える．
続いて，後者に対応する指標であるが，被覆度とばらつきある．

度の 2 種類を定義し，これらを組み合わせて用いる．被覆度（ 1 ） si , sj は i < j の順で h2 に含まれると共に h1 にも含cover(h1 , h2 ) は h1 に含まれる手順が h2 にどの程度広く分布まれる．

しているかを表す指標であり，0 以上 1 以下の値をとる．被覆（ 2 ） i < k < j かつ sk ∈ h1 ∩ h2 を満たすような k は存在度を定義するにあたって，ハウツー情報 h における手順 si , sj

しない．
すなわち，2 乗距離は h1 , h2 の両方に含まれ，かつ隣り合う手の距離 dh (si , sj ) を以下のように定義する．

順の間の距離の 2 乗の総和である．この 2 乗距離は h2 内で等dh (si , sj ) = |i − j|(5)

なお，i, j はハウツー情報 h での出現順を表す．これを用いて，間隔に出現する場合に最小となり，その値 SDmin は以下のように計算できる．

被覆度 cover(h1 , h2 ) は以下のように定義する．

maxcover(h1 , h2 ) =s,s′ ∈h1 ∩h2SDmin (h1 , h2 )′dh2 (s, s )maxdh2 (s, s′ )′= (6)s,s ∈h2maxs,s′ ∈h1 ∩h2

dh2 (s, s′ )|h1 ∩ h2 | − 1max′

h1 ∩ h2 は h1 , h2 をそれぞれを手順の集合と見なしたときの積=集合である．つまり，式 (6) の分子は h1 と共通して含まれる

 × (|h1 ∩ h2 | − 1))2(なお，s ∈ h は手順 s がハウツー情報 h に含まれることを示し，

2s,s ∈h1 ∩h2

dh2 (s, s′ )|h1 ∩ h2 | − 1(8)手順が h2 のどのくらいの範囲に分布しているかを表し，分母2 乗距離の逆数を 1/SDmin で正規化すると，0 以上 1 以下のはその最大値によって正規化している．

値となる．この値をばらつき度とし，以下のように定義する．

ここで例を示す．図 1 はそれぞれの四角が h2 を構成する手

disp(h1 , h2 ) =順を表し，そのうち色がついたものが h1 にも含まれる手順であるとする．つまり，h2 が 6 つの手順からなり，そのうち，1SDmin (h1 , h2 )SD(h1 , h2 )

図 2 を 用 い て 説 明 す る ．こ の 場 合 ，SD(h1 , h2 ) = 32 +番目，4 番目，5 番目の手順が h1 にも含まれていることを示し1ている．この場合，cover(h1 , h2 ) = 4/5 = 0.80 である．

disp(h1 , h2 ) = 8/10 = 0.80 である．

一方，被覆度が高くても，対応する手順が一箇所に集中して存在している場合は，2 つのハウツー情報は関連が弱いと考え(9)2= 10，SDmin (h1 , h2 ) = 42 /(3 − 1) = 8 で あ る た め ，関連度 rel(h1 , h2 ) はこれらの値の相乗平均として以下のように定義する．

表 2 使用したページのタイトル

rel(h1 , h2 )=√3com(h1 , h2 ) × cover(h1 , h2 ) × disp(h1 , h2 )ID タイトル(10)

関連度には方向性があり，以下のような関係が考えられる．

•rel(h1 , h2 ) >= θrel ∧ rel(h2 , h1 ) >= θrel : h1 と h2 は同じ

内容について説明している．

•rel(h1 , h2 ) >= θrel ∧ rel(h2 , h1 ) < θrel : h2 は h1 より詳しい内容を説明している．

h1

だしも水もいっさい使わない肉じゃがh2

洋風トマト肉じゃがh3

肉じゃがレシピh4

だしいらずの肉じゃが

h5

基本のおかず・肉じゃが

h6

肉じゃがのレシピ・作り方

θrel はしきい値である．一方，どちらの方向からの関連度も低h1

い場合，2 つのハウツー情報の目的は異なっているとみなす．

h3 , h4h5h63. 3 階層化のアルゴリズム
ハウツー情報の詳しさに応じて階層化することで，検索結

h2

果をツリーのリストとして提示する．このツリーは，ノード
図 3 提案手法による階層化の結果を (複数の) ハウツー情報，エッジを詳細関係とみなし，同じ内容について説明しているハウツー情報を同一のノード，詳しい内容について説明しているハウツー情報に対応するノードを子ノードとするツリーである．このようなツリーのリストを L = ⟨R1 , R2 , · · · , Rm ⟩ で表現する．ただし，Rj はツリーとする．
野中ら [2] の手法によってハウツー情報を抽出し，3.1 節の手法で手順を抽出したものに対して，ツリーのリスト L は以下のように作成される．

す．図 3 では，四角はノードを表し，1 つ以上のハウツー情報が対応する．ノード間にはエッジが存在し，最も左側のノードが根となるツリーを構成する．h1 を根とするツリーと h2 のみからなるツリーの 2 つからなるリストが作成された．h1 は簡略化されたつくり方で，h3 , h4 , h5 , h6 はいずれも h1 よりも手のかかるつくり方であった．h3 と h4 はどちらもオーソドックスなレシピであり，説明は類似していた．h5 にはこれらよりも詳しい説明があった．h6 は詳しい説明がされていたが，隠し味（ 1 ） L ← ⟨ ⟩ とする．
（ 2 ） 手順の数が少ないハウツー情報 hk から順に (3) を実行する．
（ 3 ） L = ⟨R1 , · · · , Rm ⟩ の Rj の根 root(Rj ) に対して，式(11) および式 (12) を満たすものを探し，(4) を実行する．などが違っていた．また，h2 は洋風肉じゃがのレシピであり，他のものとは材料が異なっていた．
提案手法を用いなかった場合との比較結果について述べる．
類似度による判定を行わず，関連度のみで階層化を行った場合
は，h2 と h3 , h4 の関連度が高くなり，目的が異なるハウツー

sim(hk , root(Rj )) >= θsim(11)

情報が同一のツリーに混在してしまった．類似度を併用するこrel(hk , root(Rj )) >= θrel(12)とによって，目的が異なるハウツー情報の混在は避けられる．

これらを満たすものが存在しない，もしくは L = ⟨ ⟩ の場合は，hk を根とするツリーを作成し，L に追加する．

また，関連度の代わりに共通度を用いて階層化を行った場合は，h3 , h4 間の共通度よりも h5 , h6 間の共通度が高くなり，人の感覚と異なる結果になった．このように，共通度，被覆度，ばら（ 4 ） 以下の (a)〜(c) を実行し，Rj に対して hk を追加する．

つき度を併用することで人の感覚に近い階層化が期待できる．

（ a ） 式 (13) を満たす場合は root(Tj ) に追加する．

rel(root(Rj ), hk ) >= θrel5. お わ り に(13)
本研究では，手順の対応関係に基づいてハウツー情報の検索（ b ） 式 (13) を満たさない場合は，root(Rj ) の子を根とす
る部分木 Rj′ に対し，式 (14) を満たすかどうか調べ，満たすものについては R′ に対して hk を追加する処理として (4) と同様の処理を行う．

rel(hk , root(Rj′ )) >= θrel

結果を階層的にまとめ，ツリーのリストとして提示する手法を提案した．具体的には，手順を動作とその対象のペアとして表現し，日本語 WordNet および Wikipedia を用いて，手順間の対応関係を発見する手法を提案した．また，この対応関係を用(14)（ c ） 式 (14) を満たす Rj′ が存在しない場合は，root(Rj ) の新たな子として hk を追加する．

4. 実 行 例

いてハウツー情報間の関連度を定義し，これに基づいてハウツー情報を階層化する手法を提案した．関連度は共通度，被覆度，ばらつき度を用いて定義される．
今後は手順間の対応関係，対象の類似度，ハウツー情報間の関連度のそれぞれについて評価実験を行うと共に，実例の規模や数を増やして考察を行う．

実行例として，肉じゃがのレシピを提案手法によって階層化した結果について説明する．表 1 に URL，表 2 にタイトルを謝示す．手順の数の昇順に h1 , h2 , h3 , h4 , h5 , h6 であった．な

本研究の一部は，平成 24 年度科研費若手研究 (B)「情報の詳お，θsim = 0.40, θrel = 0.42 とした．階層化の結果を図 3 に示辞表 1 使用したページの URL

ID URLh1

http://cookpad.com/recipe/5629h2

http://cookpad.com/recipe/956932

h3

http://recipe.inoinox.com/gohan/nikujyaga.html

h4

http://www.kikkoman.co.jp/homecook/search/recipe.php?numb=00000596

h5

http://erecipe.woman.excite.co.jp/features/okazu/o16.html

h6

http://erecipe.woman.excite.co.jp/detail/246ff0f634c81a014920b3bc14f1ef9c.html

細関係に基づく Web ページの組織化」(課題番号：24700097)によるものです．ここに記して謝意を表すものとします．
文

献[1] “情報検索に対する信憑性に関する調査” ，http://www.dl.
kuis.kyoto-u.ac.jp/i-explosion/report/index.html[2] 野中 諒志，湯本 高行，新居 学，高橋 豐，“概要・詳細の見やすさに基づく手法情報のランキングと閲覧支援” ，WebDB Forum2010, 2A-1 (2010).
[3] 小久保 卓，小山 聡，山田 晃弘，北村 泰彦，石田 亨，“検索隠し味を用いた専門検索エンジンの構築”，情報処理学会論文誌，
Vol.43，No.6，pp.1804-1813 (2002).
[4] 鶴田 雅信, 増山 繁, “レイアウト情報を用いた Web ページの主要な DOM ノードの抽出法”, 人工知能学会論文誌, Vol.25,No.6, pp.742–756 (2010).
[5] Deng Cai, Shipeng Yu, Ji-Rong Wen, Wei-Ying Ma, “VIPS:A VIsion based Page Segmentation Algorithm”，Microsoft
Technical Report (2003).
[6] 小澤 俊介, 内元 清貴, 松原 茂樹, “モノの使われ方の情報がノウ
ハウ獲得に与える影響”, 電子情報通信学会論文誌 D, Vol.J95-D,
No.3, pp.506-517 (2012).
[7] Hisashi Miyamori, “Assisting the Validity Assessment ofItems based on Composition Similarity”, Proceedings of theACM multimedia 2009 workshop on Multimedia for cookingand eating activities, pp.15–21(2009).
[8] 浜田 玲子, 井手 一郎, 坂井 修一, 田中 英彦, “料理テキスト
教材における調理手順の構造化”, 電子情報通信学会論文誌,
J85-D-II(1), pp.79–89 (2002).
[9] 湯本 高行, “Web 上のハウツー情報からの構成要素の抽出”, 情報処理学会第 153 回データベースシステム研究発表会, A-1-3(2011).
[10] Satoshi Sato, Suguru Matsuyoshi, and Yohsuke Kondoh,“Automatic Assessment of Japanese Text Readability Basedon a Textbook Corpus”, Proceedings of the 6th International Conference on Language Resources and Evaluation,
pp.654–660 (2008).
[11] Makoto Nakatani, Adam Jatowt, and Katsumi Tanaka,“Easiest-First Search: Towards Comprehension-based WebSearch”, Proceeding of the 18th ACM conference on Information and knowledge management, pp.2057–2060 (2009).
[12] Douglass R. Cutting, David R. Karger, Jan O. Pedersenand John W. Tukey, “Scatter/Gather: A Cluster-based Approach to Browsing Large Document Collections”, Proc. ofSIGIR ’92, pp. 318–329 (1992).
[13] Francis Bond, Hitoshi Isahara, Sanae Fujita, Kiyotaka Uchimoto, Takayuki Kuribayashi and Kyoko Kanzaki, “Enhancing the Japanese WordNet”, The 7th Workshop on AsianLanguage Resources, in conjunction with ACL-IJCNLP2009 (2009).
[14] 白川 真澄, 中山 浩太郎, 荒牧 英治, 原 隆浩, 西尾 章治郎,
“Wikipedia と Web の情報を組み合わせたオントロジー構築の試み”, 電子情報通信学会論文誌 D, Vol.J94-D, No.3, pp.525539(2011).