人工知能学会研究会資料
SIG-SWO-A602-07

セマンティックウェブとオントロジー研究会
Folksonomy の 3 部グラフ構造を利用したタグクラスタリング
丹羽 智史† a)土肥拓生† b)

本位田真一†,†† c)

Tag Clustering Method based on Folksonomy Tri-Partite Graph Analysis
Satoshi NIWA†a) , Takuo DOI†b) , and Shinichi HONIDEN†,††c)

Abstract.
近年新しいドキュメント分類の形態として Folksonomy(フォクソノミー) が注目されている.Folksonomy は従来の Taxonomy とは対照的に, エンドユーザによるボトムアップでフラットな分類を実現する.Folksonomy は分類
速度, 分類の実用性, 分類の適応性など多くの面で優れており, 各種 Web Filtering 技術に応用可能な大きなポテン
シャルを有しているのにも関わらず, 現在のところ十分に活用されていない. 本論文において我々は Folksonomyの性質を分析し,Folksonomy の 3 部グラフ構造を利用することで Synonym 問題など Folksonomy 固有の問題
を解決しながら効率的に分類データを構造化する手法を提案し,Folksonomy の応用への道を開く.
Keywords. Folksonomy,Taxonomy,Web マイニング,Web フィルタリング

1. は じ め にClassification filter

近年 Web で生み出される情報は日々増加の一途をたどり, また情報ソースも従来のニュースサイトなどに加えブログ,SNS などと多様化がすすんでいる. 我々
User

は限られた時間の中でより効率的に Web の情報を収Evaluation filter

集, 処理する必要にせまられている.
図 1 Web Content Filtering

Web の膨大なドキュメントの中から自分が必要としている情報を取捨選択してくれる技術を Web フィル
タリング技術と呼ぶ.Web フィルタリング技術は主にᵱᶃᵿᶐᶁᶆᴾᶃᶌᶅᶇᶌᶃ

ᵟᶅᶅᶐᶃᶅᵿᶒᶍᶐᴾᵱᶍᶁᶇᵿᶊᴾᶌᶃᶕᶑᴾᶑᶇᶒᶃᴾ

ᵡᶍᶌᶒᶃᶌᶒᶑᴾᶃᶔᵿᶊᶓᵿᶒᶇᶍᶌ

Ṻᶕᶃᶀᵋᶊᶇᶌᶉᴾᵿᶌᵿᶊᶗᶑᶇᶑ

ᶣ
ᶌᶍᶌᶃ

Ṻ
ᶃᶌᶂᵋᶓᶑᶃᶐᴾᶔᶍᶒᶇᶌᶅ

ᵡᶍᶌᶒᶃᶌᶒᶑᴾᶁᶊᵿᶑᶑᶇᶄᶇᶁᵿᶒᶇᶍᶌ

ᶉᶃᶗᶕᶍᶐᶂᴾᶋᵿᶒᶁᶆᶇᶌᶅ

ᶉᶃᶗᶕᶍᶐᶂᴾᶋᵿᶒᶁᶆᶇᶌᶅ

ᶃᶌᶂᵋᶓᶑᶃᶐᴾᶁᶊᵿᶑᶑᶇᶄᶇᶁᵿᶒᶇᶍᶌ
(QNMUQPQO [ᵡᶍᶌᶒᶃᶌᶒᶑᴾᶌᶃᶕᶌᶃᶑᶑ

ᶣ
ᵿᴾᶄᶃᶕᴾᶂᵿᶗᶑṺᵿᴾᶄᶃᶕᴾᶆᶍᶓᶐᶑ

Ṻ
ᵿᴾᶄᶃᶕᴾᶆᶍᶓᶐᶑ

ᵡᶍᶌᶒᶃᶌᶒᶑᴾᶂᶍᶋᵿᶇᶌ

ṻṵᵟᶌᶗᴾᶁᶍᶌᶒᶃᶌᶒᶑᴾᶍᶌᴾᶕᶃᶀ ᵡᶍᶌᶒᶃᶌᶒᶑᴾᶕᶇᶒᶆᴾᵰᵱᵱᴾᵆᶍᶐᴾᵟᶒᶍᶋᵇᴾᶄᶃᶃᶂᶑ

ᵣᶖᵿᶋᶎᶊᶃᶑ

コンテンツ評価機能, コンテンツ分類機能の 2 つの機能を有する (図 1).
図 2 は現在広く普及している Web フィルタリング
技術を独自の基準で分類した表である.

Google [10] などの検索エンジンはドキュメント間のハイパーリンク構造を解析し, ページランク [2] を求めることでドキュメントの評価を行っている. またドキュメント内に現れるキーワードをもとに分類を行っᾎᵟᶌᶗᴾᶁᶍᶌᶒᶃᶌᶒᶑᴾᶌᶍᶒᶇᶄᶇᶃᶂᴾ
ᶀᶗᴾᶃᶌᶂᴾᶓᶑᶃᶐᶑᴾ

図 2 Modern Web Filtering Servicesている.RSS リーダーなどのアグリゲーターは Web 上で公開されている RSS フィードや ATOM フィードを定期的に巡回し, ドキュメントの更新を確認する. ペー
†
††

東京大学
国立情報学研究所a) E-mail: niwa@nii.ac.jpb) E-mail: tdoi@nii.ac.jpc) E-mail: honiden@nii.ac.jp

ジランクなどのコンテンツ評価の仕組みは無いが, 検索エンジンよりも新しい情報を集めることができる.
本論文では第 3 の項目であるソーシャルニュースサ
イトに注目したいと思う digg [8] や del.icio.us [9] はエ

07-01

人工知能学会研究会資料 SIG-SWO-A602-07

ンドユーザによるドキュメントクリッピングサービス
Taxonomyである. サービスごとに仕組みは若干異なるが, ユーザ

Folksonomyに人気のあるドキュメントにはポイントが溜まっていき, ドキュメントの分類もユーザ自身が行う点は共通している. したがってドキュメント評価もドキュメン
ト分類も完全にエンドユーザに依存しているのが特徴

Arts

Business

Movies

Jobs

ComputerMovies

Jobs

Software

Arts
TV

である.

Internet
Investing Software

Internet
TV

del.icio.us などで用いられているユーザによるドキュメ ン ト 分 類 の 仕 組 み は Folksonomy と 呼 ば れる [5].Folksonomy は分類の速さ, 分類結果の実用性

ᵦᶇᶃᶐᵿᶐᶁᶆᶇᶁᵿᶊᴾᶁᶊᵿᶑᶑᶇᶄᶇᶁᵿᶒᶇᶍᶌ
ᶀᶗᴾᵿᶓᶒᶆᶍᶐᶇᶒᶗ

ᵤᶊᵿᶒᴾᶁᶊᵿᶑᶑᶇᶄᶇᶁᵿᶒᶇᶍᶌ
ᶀᶗᴾᶃᶌᶂᴾᶓᶑᶃᶐᶑ

などが非常に優れており,Web Filtering の各種技術へ応用できる高いポテンシャルを有しているが, 現状で

図 3 Taxonomy and Folksonomy

は十分にそのポテンシャルが活かされていないように感じる.

ユーザがそれぞれの文書に タグ付け を行うことに

我々は過去の研究において Folksonomy のデータをよって構築されていく. タグ付けとはユーザが対象文

利用することで高精度でユーザの趣味嗜好に一致した書の特徴を端的に表すキーワードを自分の主観によっ

Web ドキュメントを推薦する Web Recommneder をて選択する行為であり, 任意のキーワードを文書にタ構築し,Folksonomy の有用性を示した [1].

グ付けすることができる. また 1 つの文書に複数のタ

本論文では Folksonomy の性質を分析し,Folkson-

グを付けることもできる.Folksonomy においては分類

omy の 3 部グラフ構造を利用したタグのクラスタリン

フェーズがそのまま分類構造の構築フェーズを兼ねる.

グ手法を提案することで Folksonomy の各種技術への加えて,Folksonomy の分類構造はフラットである.

さらなる応用の道を開く.
本論文の構成は以下のようになっている.2 章では

2. 2 Social Bookmark Service(ソーシャルブ

Folksonomy の基本的な仕組み, 利点及び問題点につックマークサービス)
Social Bookmark Service(以下 SBS) はオンラインいて述べる.3 章では Folksonomy の 3 部グラフ構造に

上で Web ページのブックマークを管理・共有するため基づき Folksonomy の性質に関する仮説を立てる.4 章の Web ベースのサービスである. 個々のユーザは今ま

では仮説をもとに Folksonomy のタグをクラスタリン

で自分のブラウザで管理していたのと同じように SBSグする手法を提案する.5 章では実験によって仮説を検上でブックマークを管理することができる. また SBS

証する.

上では登録している全てのユーザのブックマークが公2. Folksonomy(フォクソノミー)
2. 1 Folksonomy とは開されているので, 自分と趣味嗜好が似ている他ユー
ザのブックマークを参考に情報収集に役立てることができる.

Folksonomy は別名 Social Tagging(ソーシャル・タ

SBS 上でのブックマーク文書の分類には Folkson-

ギング) とも呼ばれ, 伝統的な分類手法である Taxon-

omy が用いられていることが多い. 多くの SBS では

omy と対比されることが多い. 図 3 は Taxonomy とブックマークを登録する際に同時にタグ入力を求めら

Folksonomy の分類構造を図示している.

れる. 本節で SBS を紹介したのは,SBS が現状で最も大Taxonomy は少数の権威, 担当者があらかじめ分類

規模な Folksonomy の使用例となっているためである.

ヒエラルキーを構築しておき, その後に個々の分類被

現在世界最大の SBS である del.icio.us では 500,000

対象物（今回の場合は文書）をヒエラルキーの最下層

人以上の会員のブックマークデータとそれに付随するに組みいれていくトップダウンな分類手法である. 分

タグのデータが公開されている（図 4）. 本論文では類構造の構築フェーズと分類フェーズが分かれている

SBS 上のデータを用いて Folksonomy の性質を分析のが特徴である.

する.

Folksonomy はこれとは対象的にボトムアップな分類手法である.Folksonomy の分類構造は個々のエンド

2. 3 Folksonomy を扱う上での難しさ
Folksonomy のタグデータを処理する際には, 以下

07-02

人工知能学会研究会資料 SIG-SWO-A602-07

する分類速度に強みをもつ.
（ 2 ） 分類が実用的

Folksonomy では各々のユーザが自分自身にとって最も使い勝手がよくなるように文書のタグ付けを行う.
結果として多くのエンドユーザにとって実用的な分類

jimbobbがなされる.
productivity（ 3 ） 分類構造が動的に変化する

work
lifehacks

howto

Folksonomy ではユーザの分類行動を反映して分類構

tips

造が動的に変わっていく. そのためその時代のパラダ
イムやユーザの意識に適応した分類構造が自動的に構
productivity

work

tips

築されていく.
careerofficemanagement

これらの特長を見ると Folksonomy は Document

Classiﬁcation, Recommendation, Web Personaliza-

selectie1

tion など多くの分野に応用できる非常に大きなポテン
図 4 Folksonomy in del.icio.us

シャルを持っているといえる. しかし現時点では Folk-

sonomy は例えばタグによる文書検索（タグサーチ）
Synonymtagsなど非常に限定された方法でしか利用されていない.

Gaps between
tagging levelbusiness

Folksonomy の技術応用を実現するために Folksongolf

footballbaseballomy の性質を分析し,Synonym 問題などを解決しながらフラットな Folksonomy を構造化する方法を提案す

biz
ɓȸɍȹ

sportsるのが本論文のねらいである.

3. Folksonomy に関する仮説
図 5 Diﬃculty in Dealing with Folksonomy

この章では以降 Folksonomy を分析する上で基礎となる,Folksonomy の性質に関する我々の仮説を展開すの点に注意する必要がある.
（ 1 ） Synonym(シノニム) の問題

る. 以下は我々の仮説の概略である.
タグ間のドキュメントベースの共起率とユーザベー

Folksonomy ではタグに任意のキーワードを選択でき

スの共起率の双方を計算することでタグどうしの関係

るため, 同じ意味の異なるタグが混在する事態が頻繁に性の推定精度が大幅に向上する起こる（図 5 左）.Synonym なタグはデータの冗長性をもたらすので, 可能な限り同種タグとしてまとめてしまず, ドキュメントベースの共起率とユーザベースの共起率の定義について説明していく.

まうのが望ましい. 本論文では 2 つのタグが Synonym

3. 1 2 タグ間の共起率か否かを高確率で判定するための手法を提案する.

3. 1. 1 ドキュメントベースの共起率（ 2 ） タグの分類抽象度の問題

キーワードどうしの共起率は文書検索や文書分類なFolksonomy では個々のユーザが自分に使い勝手を基どの分野で頻繁に利用される. 通常は 1 つのドキュメ

準にタグを選択するため, さまざまな抽象度のタグがント内に 2 つのキーワードが同時に出現する確率を意

混在してしまう (図 5 右). 本論文ではタグのクラスタ

味し, この値が高いほど 2 つのキーワードの関連性がリングによる構造化によりこの問題の解決を試みる.

高いとみなされる.

2. 4 Folksonomy の特長
Folksonomy は既存の Taxonomy と比較して以下のここではタグ間のドキュメント共起率を

1 つのド

キュメントに 2 つのタグが同時にラベリングされる確ような特長を有する率 と定義する. 共起率の計算方法としては以下に示す（ 1 ） 分類が速い

AEMI(Augmented Expected Mutual Information)

Folksonomy では何百〜何万人ものユーザが分類を行を用いる [7].

うため分類速度がとても速い. とくに新しい記事に対

07-03

人工知能学会研究会資料 SIG-SWO-A602-07とを利用してタグ間の共起率をドキュメントベースと
2
4
3
PD ( B = b) =41
PD ( A = a, B = b) =4
PD ( A = a ) =2
3
2
PU ( B = b) =3
1
PU ( A = a, B = b) =3
PU ( A = a ) =

tag a

tag b

ユーザベースの双方から測定することができる (図 6).
我々はこの 2 つの異なる共起率に利用して以下のような仮説を展開する.

3. 2 仮MIU ( A, B) = −0.041

MI D ( A, B) = −0.044

AEMI D ( A, B) = −0.038

説

3. 2. 1 Synonym 関係

AEMIU ( A, B) = −0.035

以下は Synonym 関係のタグに関する我々の仮説である.

2 つのタグが Synonym 関係の場合, それらのユー

図 6 Co-Occurrence Rate between Tag a and b

ザベース共起率 (AEM IU ) はドキュメントベース共

M ID = PD (a, b) log

起率 (AEM ID ) に比べて大幅に低い傾向にある

PD (a, b)
PD (a)PD (b)2 章でも述べたが,business と biz のように同じ意味

AEM ID = M ID (A = a, B = b) + M ID (A = ā, B = b̄)で別表記のタグを Synonym 関係にあるという.Folk− M I (A = a, B = b̄) − M I (A = ā, B = b)sonomy において Synonym タグが生じるのは, 異なる
D

D

ユーザ間でどのタグを使うかに関するコンセンサスが式中に出現する A,B は 2 つのタグ a,b に関連する

とれていないことに起因する. したがって Synonym 関

変数である.PD (A = a) は任意のドキュメントにタグ係にある 2 タグが同一ユーザによって用いられている

a がラベリングされる確率を表す. 逆に PD (A = ā) は可能性は低い. それに対し,Synonym タグどうしは意

任意のドキュメントにタグ a がラベリングされない確

味は同じなので同一のドキュメントにラベリングされ率を表す.PD (A = a, B = b) は任意のドキュメントにている可能性が非常に高い. 一般にユーザベースの共起

タグ a,b が同時にラベリングされる確率を表す.

率とドキュメントベースの共起率は正の相関関係にあM ID はこれらの値から導き出したタグ a,b 間の共
起率の 1 つの指標であり,AEM ID は M ID を利用しると考えられるので, この特徴を利用すれば Synonym
関係の判定を高精度で行うことができるだろう.

てより精細に共起率を算出している.

3. 2. 2 Conﬂict 関係

3. 1. 2 ユーザベースの共起率ところで, 図 3 や図 6 で示されているように Folk-

タグを Conﬂict 関係にあると定義する. 例えば man とsonomy の構造の実体はユーザ, ドキュメント, タグのwoman,mac と windows など同レベルの異なる事象

本論文中では意味的に対立もしくは競合している 2

3 種のノードによって構成される 3 部グラフである. しを表している場合, これらは Conﬂict 関係にある.Syn-

たがってタグ間の共起率は前節のようなドキュメント

onym 関係同様,Conﬂict 関係に対しても 2 つの共起率

ノード上の共起率だけでなく, ユーザノード上の共起をもとに次の仮説を立てた.

率という観点からも測れる.

2 つのタグが Conﬂict 関係の場合, それらのユーザ

以下, 前節と同様にユーザベースのタグ間共起率

AEM IU を定義する.

ベース共起率 (AEM IU ) はドキュメントベース共起率 (AEM ID ) に比べて高い傾向にある
この仮説は mac と windows のような対照関係にあM IU = PU (a, b) log

PU (a, b)
PU (a)PU (b)るタグは同一ユーザによって利用されている可能性が高いが, 同一ドキュメントにラベリングされている可AEM IU = M IU (A = a, B = b) + M IU (A = ā, B = b̄)能性は低いという仮定に基づいている. ただしこれらのタグが同一ドキュメントに現れる確率は低いといっ− M IU (A = a, B = b̄) − M IU (A = ā, B = b)ても一定数見込まれるため,Synonym 仮説ほどには顕PU (A = a) は任意のユーザがタグ a を用いたこと著な特徴が現れないのではないかというのが仮説を立があるか否かの確率を表す.PD (A = a, B = b) は任意てた段階での予想である.

のユーザがタグ a とタグ b の両方を用いたことがある

3. 2. 3 Relevant 関係

か否かの確率を表す.

最後に, 意味的な相関度が高い 2 タグのうち Syn-

このように,Folksonomy が 3 部グラフ構造であるこ

onym 関係でも Conﬂict 関係でもないものを Rele-

07-04

人工知能学会研究会資料 SIG-SWO-A602-07

AEMI Dᵦᵧᵥᵦᵪᵭᵵᵰᶃᶊᶃᶔᵿᶌᶒᴾ
ᶒᵿᶅᶑᵡᶍᶌᶄᶊᶇᶁᶒᶇᶌᶅᴾ
ᶒᵿᶅᶑᵱᶗᶌᶍᶌᶗᶋᴾ
ᶒᵿᶅᶑᵳᶌᶐᶃᶊᵿᶒᶃᶂᴾ
ᶒᵿᶅᶑ

ᵦᵧᵥᵦ

1. Calculate co-occurrence rate between tags

2. Detect synonym tags and combine them

AEMIU
ᵪᵭᵵ

3. Calculate degree of relevance between tags
4. Calculate degree of conflict between tags

5. Cluster tags

AEMI D indicates co-occurrence rate of two tags on the same document
AEMIU indicates co-occurrence rate of two tags on the same user

図 7 Our Assumptions about Folksonomy Tag Relations

図 8 Our Tag Clustering Method

いので,Synonym 関係のタグや Relevant 関係のタグ

vant 関係と定義する.Relevant 関係の例としては soft-

をクラスタ化して次元数を圧縮する必要があるだろう.

ware と programming,food と recipe などがあげられこの章では 3 章で述べた我々の仮説の応用例とし

る.Relevant 関係に関する仮説は以下のとおりである.

て,Folksonomy タグをクラスタリングする方法を示す.

2 つのタグが Relevant 関係の場合, それらのユー
ザベース共起率 (AEM IU ) とドキュメントベース共
起率 (AEM ID ) は共に高い傾向にある
この仮説は意味的な相関度の高い 2 タグは同一ユー
ザにも利用されやすく, また同一ドキュメントにもラ
ベリングされやすいという仮定に基づいている.

4. 2 タグクラスタリングの手順
図 8 はタグクラスタリングの手順を示している. 以
下, これらの手順について順に説明していく.

4. 2. 1 共起率の計算
タグ間の共起率を求める. 共起率は前章で述べた

AEM ID と AEM IU の 2 つについてそれぞれ求める.

図 7 は Folksonomy のタグの関係性に関する我々の計算の際はドキュメントベースの共起もユーザベース

仮説を 2 つの共起率を軸にまとめたマトリックスであの共起も全く見られない 2 タグ間については計算しなる. これらの仮説の妥当性については 5 章にて評価実いなどして, 全く無関係だと思われる 2 タグ間の計算

験を行う.

を省く.

4. Folksonomy タグのクラスタリング

4. 2. 2 Synonym タグの融合
3.2.1 で述べた Synonym タグに関する我々の仮説

4. 1 タグクラスタリングの必要性を も と に Synonym タ グ を 検 出 す る.

タグは Folksonomy を扱う上で最も重要な存在だ

AEM ID が十分に高く AEM IU が十分に低くなる

が,Taxonomy のカテゴリのような意味的な構造化がような 2 タグを Synonym 関係とみなすのだが, その全くなされていない.del.icio.us を例にとると数万種類判定を行うためには適切な閾値を設定してやる必要がを越えるタグが用いられており, 中には特定のユーザある. 今回はあらかじめ人間が作った訓練データからしか用いていないような希少タグも存在するし,news

決定木を生成する教師付き学習を用いて Synonym の

具体的にはや blog のように頻繁に用いられるタグも存在する. 先

判定を行う. 決定木生成の詳細と判定精度の評価は次に述べた Synonym 関係のように意味が同一のタグや章を参照のこと.

Relevant 関係のように意味的な相関度の高いタグどうしも区別なくフラットに入り混じっている.

Folksonomy を Web Recommender などに応用す

Synonym 関係と判定されたタグどうしは 1 つにまと
められ, 以降のフェーズでは同一タグとして扱われる.

4. 2. 3 相関度の計算

る場合, 例えばドキュメントに付与されたタグをもとに

我々のクラスタリングではより意味的な相関度が高

そのドキュメントをベクトル化するといった用法が想いタグどうしがクラスタ化されることをめざす. この定される. その場合も 1 種類のタグを 1 つの次元にそフェーズでは 3.2.3 で述べた仮説をもとにタグ間の相のままマッピングしていたのでは非常に計算効率が悪

関度 (degree of relevance) を計算する. 相関度を測る

07-05

人工知能学会研究会資料 SIG-SWO-A602-07

degree_of_conflict
0.007
degree_of_relevance 0.07

tag

Remove connection with thesmallest degree_of_relevance

tag
0.006
0.07

0.014
0.08

0.012
0.05

tag

0.002
0.02

0.001
0.04

tag
tag
0.43
0.07

0.002
0.03

0.003
0.06

Remove connection with thelargest degree_of_confilct

0.32
0.07

tag
0.001

1. Manual Input

tag

0.08
main(){
cluster0 ť The cluster composed of all the tags
divideCluster(cluster0);}

divideCluster(cluser){
if (cluster_size < MinClusterSize) return;
Connect all the tags in cluster
while (true) {Remove connection with the smallest degree_of_relevance
Remove connection with the largest degree_of_conflict
Define each connected component as childif (children_number > 1) break;}for each child { divideCluster(child); }}図 9 Our Tag Clustering Algorithm

3. Build a Decision Tree

2. Calculate Co-occurrence

図 10 Evaluation Method

スタにも同様のアルゴリズムを再帰的に適用していく.
この分割アルゴリズムの特徴は同一クラスタ内における最小の相関度を高く, 最大の対立度を低く設定できる点にある. クラスタの分割はクラスタのサイズが基準値には以下の値を用いる.

閾値以下になった時点で止める.

5. 評 価 実 験relevance(A, B) = AEM ID (A, B) × AEM IU (A, B)
4. 2. 4 対立度の計算
相関度とは逆に, 我々のクラスタリングでは意味的な対立度が高いタグどうしは別クラスタに分断されることをめざす. このフェーズでは 3.2.2 で述べた仮説をもとにタグ間の対立度 (degree of conﬂict) を計算する. 対立度を測る基準値には以下の値を用いる.

この章では 3 章で述べた我々の仮説の検証を行う.
具体的にはドキュメントベースとユーザベースの 2 種
類のタグ共起率を用いることで, 既存のドキュメント
ベースのみの場合に比べどれほど Synonym 関係などの判定精度が向上するかを検証する.

Folksonomy のサンプルデータは del.icio.us 上で2006 年 7 月中に公開されているデータを用いた.21,000
人のユーザ,8400 種類のタグ,220,000 エントリ分のデータを使用した.

conf lict(A, B) =AEM IU (A, B)
AEM ID (A, B)

4. 2. 5 クラスタリングの実行
タグ間の相関度と対立度をもとにクラスタリングを

5. 1 評 価 方 法
図 10 は評価手順を示している. 以下, それぞれの手順について順に説明する.

5. 1. 1 人手によるタグ間の関係入力実行する. 図 9 はクラスタリングアルゴリズムを示す.

この評価実験の目的は我々の仮説を用いることでタまず初めに全てのタグを 1 つの巨大なクラスタとみグ間の意味的関係の推定が高精度で行えるようになるなし, これを再帰的に分割していく.Synonym タグはことを示すことである. したがって, 評価のためにはタ

既にまとめられおり, このフェーズでは 1 つのタグとグ間の意味的関係に対する正解をあらかじめ用意してして扱う.1 つのクラスタを分割する手順は以下のとおおく必要がある. 今回我々は人間による手入力によっりである.

てタグ間の意味的関係を定義した.

まず, クラスタ内に含まれるタグ間の接続のうち最del.icio.us 上で用いられているタグのうち最も使用も相関度が低いものを取り除く. 次に最も対立度が高い

頻度の高い上位 200 個のタグ間の関係について Syn-

ものを取り除く. これをクラスタ内の連結成分が 2 つonym,Relevant,Conﬂict,Not Related のうちから手動以上に分解するまで続ける. さらに分割された子クラで選択し入力を行った. その際,AEM ID と AEM IU

07-06

人工知能学会研究会資料 SIG-SWO-A602-07

Relations

AEMIU

Conflict

Relevant

Synonym

ConflictNot
related

Total

Attributes

Relevant

PD ( A), PD ( B ), AEMI D ( A, B) 13%

12%

16%

53%

35.0%

PU ( A), PU ( B ), AEMIU ( A, B) 11%

1.3%

8.4%

43%

27.6%

AEMI D ( A, B), AEMIU ( A, B)

54%

72%

32%

65%

57.8%

AEMI D ( A, B), AEMI U ( A, B),

66%

92%

52%

75%

70.8%

AEMI D ( A, B)
AEMI U ( A, B)

Synonym

Not related

AEMI D図 12 Classiﬁcation Accurecy of Each Decision Tree

用による分類精度の向上を示すため, 訓練データの入力属性を様々に変えて複数の決定木を生成し, それら

図 11 Distribution of the Training Setの分類精度の比較を行った.
図 12 は 各々の 決 定 木 の 分 類 精 度 の 比 較 表 で
あ る. 例 え ば 一 番 左 上 の マ ス (13% の マ ス) はがともに十分に低い 2 タグについてははじめから Not

PD (A),PD (B),AEM ID (A, B) の 3 つの属性をもとRelated とみなすことで入力の手間をおさえた.

に生成した分類木が Relevant 関係の 2 タグを Rele-

入力値の偏りを防ぐため,4 人の人間が全く同じデー
タについて入力を行った.4 人のうち 3 人以上が同じ関vant 関係だと正しく判定する確率が 13% であることを意味する.

係を入力した場合にのみ正解データに組み込んだ. そこれを見ると, ドキュメントベースの情報のみを使っうでないデータに関しては慎重な議論の後再度入力をた決定木の総合分類精度が 35.0% , ユーザベースの情行った.

報のみを使った決定木の総合分類精度が 27.6% に対

5. 1. 2 タグ間の共起率の計算

し AEM ID と AEM IU の双方を利用した場合の分類

人力で入力された各タグの組み合わせに対し精度は 57.8% と極めて高くなっているのがわかる. とAEM ID ,AEM IU の 2 種類の共起率を計算し, 人力入

くに Synonym 関係の分類精度の向上が著しい.

力による関係データと合わせて訓練データとする.

5. 1. 3 決定木の生成

ま た, 属 性 値 に AEM ID と AEM IU の 他 にAEM IU (A,B)
を加えて決定木を生成すると,Synonym
AEM ID (A,B)

訓練データをもとに決定木を生成する. 今回はデー関係の分類精度と Conﬂict 関係の分類精度がさらに大タマイニングツールとして Weka3 [11] を用いた. 決定

きく向上する. これは Synonym 関係と Conﬂict 関係

木の生成アルゴリズムには J48 を用いた.

の判定には AEM ID と AEM IU の大小比が大きな意

5. 2 評 価 結 果
5. 2. 1 タグ間の関係の分布
図 11 は 実 験 で 用 い た 訓 練 デ ー タ の 統 計 的 な 分味を持つという我々の仮説を裏付けている.

6. 関 連 研 究布である. 横軸と縦軸がそれぞれ計算によって求めPeter Mika は Folksonomy を Actor-Concept-

られた 2 タグ間の AEM ID と AEM IU を表し, 各Instance から成る 3 部グラフ構造と定義した [4].Peter

点 の 色 が 人 力 で 入 力 し た 2 タ グ 間 の 関 係 性 (Syn-Mika はこれを従来の Concept-Instace 型の 2 部グラ

onym,Relevant,Conﬂict,Not Related) を表す.

フ構造のオントロジに社会的な次元 (Social Dimen-

Not Related は AEM ID と AEM IU が低い領域に集中し,Relevant は逆に右上方向に広く広がっているsion) が加わったものだと主張し,Folksonomy をもとにオントロジを構築する可能性を示した.

のがわかる.Conﬂict は Relevant の領域と大きく被る

丹羽らも同様に Folksonomy の 3 部グラフ構造にものの, 全体的に AEM ID が低い領域に分布している.

注目した [1]. 丹羽らは Folksonomy によって従来の最も特徴がわかりやすいのが Synonym で,AEM IU

User-Instance 型の 2 部グラフ構造からなる協調フィが低い領域に独自の塊を作っている.

ルタリングを拡張し, 高精度の Web 推薦システムを構

5. 2. 2 決定木の分類精度
我々は AEM ID と AEM IU の 2 種類の共起率の併築する手法を提案した.

Scott Golder ら は Folksonomy(彼 ら は Collabo-

07-07

人工知能学会研究会資料 SIG-SWO-A602-07

rative Tagging という言葉を使った) の構造を解析[10]Google : http://google.com/

し,Folksonomy 特有の性質の発見を試みた [6]. 彼らは[11]

Weka3 : http://www.cs.waikato.ac.nz/ml/weka/

Folksonomy におけるユーザ行動, タグの使用率, 使われているタグの種類, ブックマークの人気などに関して興味深い法則を発見した. 本論文で提唱した Folk-

sonomy タグの 2 種類の共起率に関する仮説は彼らの発見した法則をさらに発展させ, 補う形となっている.
大向らは Folksonomy におけるユーザどうしのつながり (Personal Network) に注目し,Personal Network
を活用する SBS の新しい仕組みを提案した [3].

7. ま と め
我々は Folksonomy の 3 部グラフ構造から導かれる

2 種類のタグ共起率を併用することで,Synonym 関係などのタグどうしの意味的関係を高精度で推定する手法を提案した. この分類手法は Folksonomy の普遍的な性質に関する我々の仮説に基づいており, 評価実験を行って仮説の妥当性を検証した.
この分類手法を用いることで Folksonomy を扱う上で特有の問題である Synonym 関係の判定を自然言語処理を利用すること無く 90%以上の精度で行うことに
成功した.
文
[1]

献

Satoshi Niwa, Takuo Doi, Shinichi Honiden : Web
Page Recommender System based on Folksonomy
Mining, 3th International Conference on Information Technology : New Generations, (2006).

[2]

Larry Page, Sergey Brin, R. Motwani, T. Winograd :The PageRank Citation Ranking: Bringing Order tothe Web, (1998).

[3]

Ikki Ohmukai, Masahiro Hamasaki, Hideaki Takeda: A Proposal of Community-based Folksonomy withRDF Metadata, 4th International Semantic Web
Conference, (2005).

[4]Peter Mika : Ontologies are us: A uniﬁed model ofsocial networks and semantics, 4th International Semantic Web Conference, (2005).

[5]

J Golbeck, B Parsia, J Hendler :Folksonomies-

Cooperative Classiﬁcation and Communication ThroughShared Metadata, (2004).
[6]

Scott Golder, Bernardo A. Huberman (HP Labs): The Structure of Collaborative Tagging Systems,
Journal of Information Science, 32(2). 198-208,(2006).

[7]

Chan, P.K. : A non-invasive learning approach tobuilding web user proﬁles, KDD-99 Workshop on
Web Usage Analysis and User Proﬁling, (1999).

[8]

digg : http://digg.com/[9]

del.icio.us : http://del.icio.us/

07-08