クラスタリング装置、クラスタリング方法及びクラスタリングプログラム
【課題】タグの再利用時において、タグの曖昧性を解消し、タグ数の爆発を防止すること。
【解決手段】全体タグ集合に対して階層的クラスタリングを行ってデンドログラムを構築し、下層から上層を特定可能にするボトムアップなインデックスを事前に生成しておき、上位アプリケーションから要求があった際に、生成されたインデックスを参照して全体タグ集合を複数の部分タグ集合にクラスタリングする。
【解決手段】全体タグ集合に対して階層的クラスタリングを行ってデンドログラムを構築し、下層から上層を特定可能にするボトムアップなインデックスを事前に生成しておき、上位アプリケーションから要求があった際に、生成されたインデックスを参照して全体タグ集合を複数の部分タグ集合にクラスタリングする。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、協調的分類システムおいて資源情報に付与された分類軸を再利用する技術に関する。
【背景技術】
【０００２】
昨今、ＵＲＬ（ブックマーク）、写真、動画像、静止画像、本、論文といった様々な資源情報を一次的作成者と異なる第三者が分類整理し、その分類結果を広く共有することにより、鮮度の高い情報を閲覧者に提供できる協調的分類システム（Collaborative/Social Tagging System）が隆盛している。
【０００３】
図１５は、協調的分類システムにおける分類軸（以下、タグという）の分類例を示す図である。資源情報の一例としてＵＲＬを示している。上記第三者である分類者により、ＵＲＬの記載内容「サッカーニュース『今日の結果』」に基づいて、その記載内容に関連する複数のタグ「ｎｅｗｓ」「ｓｏｃｃｅｒ」「面白い」が生成されている。
【０００４】
図１６は、分類者により生成されたタグを再利用する流れを説明する図である。協調的分類システムは、分類者によるタグの自由生成や、生成されたタグを上記ＵＲＬに付与すること（関連付けること）を可能とし、分類結果格納データベース１２に予め格納して再利用している。すなわち、分類者による資源情報の分類結果とも言えるタグを収集し、閲覧者に提供される提示情報を生成する過程において、上記ＵＲＬの記載内容を記述する目的で付与されたタグを分類結果格納データベース１２から読み出して再利用することを実現している。
【０００５】
一方、第三者によるタグの生成や分類対象へのタグ付与が自由であるがゆえに、タグの曖昧性や、タグ数の爆発といった問題が顕在化している。タグが曖昧であるとは、一つのタグが複数の意味を持つこと（多義タグ）や、表記は異なるが意味が同じであること（同義タグ）であることをいう。このような曖昧性や、タグ付け時点での第三者（すなわち、分類者）の感情や好み、世の流行、他の第三者によって付与されたタグの傾向等の影響に起因するタグ数の爆発により、タグを再利用することが困難となっている（非特許文献１参照）。
【０００６】
しかしながら、そのような困難性を有しているにも関わらず、第三者によって付与されたタグを利用すると、提示情報本来には必ずしも含まれない第三者視点特有のタグで資源情報の意味を的確に表現することが可能となり、自動タグ付け（オートタギング）では収集困難な感想や意見を表した主観的タグ（例えば、「これはすごい」、「ｃｏｏｌ」、「後で読む」等）を収集できるため、タグ付けされた情報の記述に度々利用されている。
【０００７】
例えば、写真をタグ付けできるサービスとして「ｆｌｉｃｋｅｒ」（http://filckr.com）、ソーシャルブックマークサービスとして「ｄｅｌ．ｉｃｉｏ．ｕｓ」（http://del.icio.us）や「はてなブックマーク」（http://b.hatena.ne.jp）や「ｇｏｏ ｂｏｏｋｍａｒｋ」（http://bookmark.goo.ne.jp）、動画をタグ付けできるサービスとして「ｙｏｕｔｕｂｅ」（http://youtube.com）、書籍をタグ付けできるサービスとして「米アマゾン」（http://www.amazon.com）、学術論文をタグ付けできるサービスとして「ＣｉｔｅＵＬｉｋｅ」（http://www.citeulike.org/）等が提供されている。なお、実際のサービスでは、付与されたタグ集合のうち、利用頻度の高い順に必要な個数のタグを選択して、提示情報の記述に用いられている。
【０００８】
ここで、どの程度のタグ数を用いて提示情報を生成することが適切であるかが問題である。一般に、商品推薦においては、より多様な商品を推薦する方がユーザ満足度の向上につながるという仮説がある。その仮説に基づいて、推薦結果を多様化する手法が提案されている（非特許文献２）。また、ウェブ検索や画像検索においても、やはり同様の仮説に基づく推薦結果の多様化方法が提案されている（ウェブ検索については非特許文献３，４、画像検索については非特許文献５，６参照）。いずれも、多様な商品をユーザに推薦した後に、そのユーザの要求に基づいてオンデマンドで推薦商品をクラスタリングする手法（Ｐｏｓｔ−Ｐｒｏｃｅｓｓｉｎｇ）である。図１７には、そのような従来手法として、ユーザから要求があった後に、要求点ｒから｜ｍ｜以下の距離を計算し、その距離内の領域を特定の方向で分割して商品をクラスタリングする手法が示されている。なお、クラスタリングとは、全体集合を一部又は全部の部分集合にすることをいう。
【０００９】
すなわち、上記商品をタグに対応させると、出来る限り多くのタグを用いて提供情報を生成することが従来技術であったと言える。
【先行技術文献】
【非特許文献】
【００１０】
【非特許文献１】Scott Golder、外１名、「The Structure of Collaborative Tagging Systems」、Journal of Information Science、2006年
【非特許文献２】Cai-Nicolas Ziegler、外３名、「Improving recommendation lists through topic diversification」、Proc. WWW、2005年
【非特許文献３】Filip Radlinski、外１名、「Improving personalized web search using result diversification」、Proc. SIGIR、2006年
【非特許文献４】Rakesh Agrawal、外１名、「Diversifying search results」、Proc WSDM、2009年
【非特許文献５】Kai Song、外３名、「Diversifying the image retrieval results」、Proc. ACM Multimedia、2006年
【非特許文献６】Reinier H. van Leuken、外３名、「Visual diversification of image search results」、Proc. WWW、2009年
【非特許文献７】神嶌 敏弘、「データマイニング分野のクラスタリング手法（１）」、人口知能学会誌、18巻1号、2003年1月
【発明の概要】
【発明が解決しようとする課題】
【００１１】
しかしながら、タグの再利用時において多くのタグを用いた場合には、前述したように曖昧性を含む複数のタグが存在し、類似する内容を表す複数のタグが収集表示される場合があるため、閲覧者の満足度は低下し、タグの再利用性が低下するという問題がある。
【００１２】
本発明は、上記課題を鑑みてなされたものであり、タグの再利用時において、タグの曖昧性を解消し、タグ数の爆発を防止することを課題とする。
【課題を解決するための手段】
【００１３】
請求項１に記載の本発明は、所定の情報を特徴付ける複数の分類軸のうち類似度の高い分類軸を階層状に順次併合する樹状図を構築し、前記樹状図を探索して下層から上層を特定可能なインデックスを生成して記憶手段に記憶しておく階層的クラスタリング手段、を有することを特徴とする。
【００１４】
本発明によれば、所定の情報を特徴付ける複数の分類軸のうち類似度の高い分類軸を階層状に順次併合する樹状図を構築し、樹状図を探索して下層から上層を特定可能なインデックスを生成して記憶手段に記憶しておくため、後段のクラスタリング処理を高速化することが可能となる。
【００１５】
請求項２に記載の本発明は、前記記憶手段から読み出した前記インデックスを参照し、前記上層が同一の分類軸を併合してクラスタ化することを所期のクラスタ数になるまで繰り返す部分クラスタリング手段、を更に有することを特徴とする。
【００１６】
本発明によれば、記憶手段から読み出したインデックスを参照し、上層が同一の分類軸を併合してクラスタ化することを所期のクラスタ数になるまで繰り返すため、タグの曖昧性を解消し、タグ数の爆発を防止することが可能となる。
【００１７】
請求項３に記載の本発明は、所定の情報を特徴付ける複数の分類軸のうち類似度の高い分類軸を階層状に順次併合する樹状図を構築し、前記樹状図を探索して下層から上層を特定可能なインデックスを生成して記憶手段に記憶しておくステップ、を有することを特徴とする。
【００１８】
本発明によれば、所定の情報を特徴付ける複数の分類軸のうち類似度の高い分類軸を階層状に順次併合する樹状図を構築し、樹状図を探索して下層から上層を特定可能なインデックスを生成して記憶手段に記憶しておくため、後段のクラスタリング処理を高速化することが可能となる。
【００１９】
請求項４に記載の本発明は、前記記憶手段から読み出した前記インデックスを参照し、前記上層が同一の分類軸を併合してクラスタ化することを所期のクラスタ数になるまで繰り返すステップ、を更に有することを特徴とする。
【００２０】
本発明によれば、記憶手段から読み出したインデックスを参照し、上層が同一の分類軸を併合してクラスタ化することを所期のクラスタ数になるまで繰り返すため、タグの曖昧性を解消し、タグ数の爆発を防止することが可能となる。
【００２１】
請求項５に記載の本発明は、請求項３又は４に記載した各ステップをコンピュータに実行させることを特徴とする。
【発明の効果】
【００２２】
本発明によれば、タグの再利用時において、タグの曖昧性を解消し、タグ数の爆発を防止することができる。
【図面の簡単な説明】
【００２３】
【図１】クラスタ化の概念を説明する図である。
【図２】階層的クラスタリングによって構築されるデンドログラムの一例を示す図である。
【図３】多様なタグで提示情報を記述するメリット・デメリットを説明する図である。
【図４】全体システムの機能ブロック構成を概略的に示す図である。
【図５】クラスタリング装置の機能ブロック構成を概略的に示す図である。
【図６】クラスタリング装置の全体処理フローを示す図である。
【図７】部分タグ集合へのクラスタリングを説明する図である。
【図８】階層的クラスタリング部の処理フローを示す図である。
【図９】デンドログラムとボトムアップインデックスの一例を示す図である。
【図１０】部分クラスタリング部の処理フローを示す図である。
【図１１】部分クラスタリング部の処理フローの一例を示す図である。
【図１２】部分クラスタリングの遷移を説明する図である。
【図１３】タグの所属クラスタの遷移を説明する図である。
【図１４】クラスタリングされたタグ集合の一例を示す図である。
【図１５】協調的分類システムにおける分類軸の分類例を示す図である。
【図１６】分類者により生成されたタグを再利用する流れを説明する図である。
【図１７】従来のクラスタ化の概念を説明する図である。
【発明を実施するための形態】
【００２４】
以下、本発明を実施する一実施の形態について図面を用いて説明する。但し、本発明は多くの異なる様態で実施することが可能であり、本実施の形態の記載内容に限定して解釈すべきではない。
【００２５】
本実施の形態に係るクラスタリング装置の構成及び処理について説明する前に、理解を容易にするために本発明の概要について事前説明する。本実施の形態は、背景技術で説明した協調的分類システムにおいて、付与された分類軸（以下、タグという）を利用して閲覧者への提供情報を生成する際に、第三者によって生成された様々なタグをできる限り多様かつ高速に選択することにより、タグの再利用時におけるタグの曖昧性を解消し、タグ数の爆発を防止することにある。
【００２６】
すなわち、図１に示すように、図１７に示した対象タグ以外に複数のタグを考慮した状態で全てのタグを事前にクラスタリングしておき（Ｐｒｅ−Ｐｒｏｃｅｓｓｉｎｇ）、その事前クラスタリングの結果をインデックスとして利用することにより、従来よりも高速にタグの多様化を行うものである。
【００２７】
なお、クラスタリングには、分割最適化手法と階層的手法があるが（非特許文献７参照）、本実施の形態では階層的手法を用いる。すなわち、階層的クラスタリングにより構築されるタグ集合上のデンドログラムを利用している。ここで、階層的クラスタリングによって構築されるデンドログラムの特徴について以下説明する。
【００２８】
図２は、階層的クラスタリングによって構築されるデンドログラムの一例を示す図である。このデンドログラムは、２分木構造を有し、類似性の高いタグを１つずつ纏めていくと最後には全体のタグ集合になり（凝集型）、逆に、全体のタグ集合を半分に分割していく操作を繰り返すと最後にはそれぞれ単独のタグになる（分岐型）という特徴がある。本発明は、凝集型又は分岐型のいずれのアルゴリズムにも適用可能であるが、分岐型について説明する。
【００２９】
図２の中間ノードに付与されている数字は、全体集合を上層ノードから下層ノードに向けて順番に分割する順番を表している。例えば、根ノードからたどり、２番の中間ノードでデンドログラムをカットすると、全体集合は２分割される。引き続き、３番の中間ノードでカットすると、全体集合は３分割される。さらに４番の中間ノードでカットすると４分割（図２に示すＡ〜Ｄ）され、結果として中間ノードの数字で全体集合をクラスタリングしたことになる。この性質により、いったんデンドログラムをタグ集合上に構築すると、タグの総数以下の任意の個数にカットすることが可能となる。なお、カットとはクラスタリングすることをいう。
【００３０】
一方、通常の分割最適化手法では、タグ集合をいくつかにカットしてクラスタリングすることはデータに依存しており、チューニングされる項目の一つである。本実施の形態で用いる階層的クラスタリングでは、いったんデンドログラムをタグ集合上に構築すれば、任意の個数のクラスタリング結果をデンドログラムのカットのみで得ることができる。つまり、階層的クラスタリングを構築してデンドログラムを生成することは、任意のクラスタ数を生成することが可能となることに等しい。
【００３１】
なお、本実施の形態は、多様なタグ集合は有効であることを前提としている。多様なタグの集合とは、互いに意味が似通っていないタグの集まり、又は、似通っているタグも含まれるが大きく意味の異なるタグを含むタグの集まりである。多様なタグの集合として、「Ｗｅｂ」「エッセイ」「Ｇｏｏｇｌｅ」「後で読む」「ＨＴＴＰ」を一例に挙げることができる。一方、多様でないタグの集合とは、どれも意味的に近い内容を表しており、例えば、「Ｗｅｂ」「Ｗｅｂ２．０」「ＷＷＷ」「Ｉｎｔｅｒｎｅｔ」「ＨＴＴＰ」等を挙げることができる。
【００３２】
参考までに、多様なタグで提示情報を記述するメリット・デメリットを図３に示す。「サッカー」「ゴール」「ニュース」「ｓｏｃｃｅｒ」といった類似度の高いタグ集合を提示するよりも、「サッカー」「ブラジル」「ニュース」「珍プレー」といった類似度の低い多様なタグ集合の方が、提示情報から適切に情報を把握することが可能となる。
【００３３】
次に、本実施の形態に係るクラスタリング装置を有する全体のシステム構成について説明する。図４は、全体システムの機能ブロック構成を概略的に示す図である。全体システムは、タグの分類者や提示情報の閲覧者（以下、ユーザと総称する）が利用するクライアント端末５と、インターネット等の通信ネットワーク３を介してクライアント端末５と通信可能な協調的分類システム１とで構成されている。
【００３４】
協調的分類システム１は、ネットワークサービスとして提供され、ユーザはクライアント端末５に搭載されたウェブブラウザやクライアントアプリケーションを通じて該ネットワークサービスを利用することができる。具体的には、ＬＡＮやルータ等の通信部１１と、データを格納する分類結果格納データベース１２と、実際に処理を実現するクラスタリング装置１３とで構成されている。
【００３５】
なお、協調的分類システム１は、背景技術で説明したように、分類者によるタグの自由生成や、生成されたタグを分類対象に付与することを可能とするアプリケーションを具備しているが、当該アプリケーションに係る具体的機能、処理内容の説明は省略する。協調的分類システム１の一例として、ソーシャルブックマークサービス（Social Bookmark Service：各ユーザのブックマークをネットワークを通じて共有するシステム）が挙げられる。
【００３６】
通信部１１は、協調的分類システム１による外部又は内部への通信、又は内部間通信等の通信をネットワークレベルで実現している。
【００３７】
分類結果格納データベース１２は、背景技術で説明したように、ＵＲＬ（ブックマーク）、写真、動画像、静止画像、本、論文といった様々な資源情報に基づいて分類者によって自由生成されたタグや、資源情報に付与されたタグを読出可能に格納しておく機能を有している。
【００３８】
なお、本実施の形態では、タグが予め生成されて分類結果格納データベース１２に格納されていればよく、クラスタリング装置１３は、どのような方法に基づいて生成されたタグであっても、どのような種類のタグであっても、後述する処理を実行することにより、タグの生成方法やタグの種類に関係なく同様の効果を得ることができる。
【００３９】
クラスタリング装置１３は、図５に示すように、通信インタフェース１３１と、階層的クラスタリング部１３２と、部分クラスタリング部１３３と、代表タグ選択部１３４と、記憶部１３５とで構成されている。
【００４０】
通信インタフェース１３１は、通信部１１や分類結果格納データベースとの間の通信を仲介する機能を有している。
【００４１】
階層的クラスタリング部１３２は、複数のタグ（以下、全体タグ集合という）を階層的にクラスタリングしてデンドログラムを構築するクラスタリング部１３２ａと、デンドログラムを探索してボトムアップなインデックスを生成するインデックス生成部１３２ｂとで構成されている。
【００４２】
部分クラスタリング部１３３は、生成されたインデックスを参照するインデックス参照部１３３ａと、参照インデックスを利用して全体タグ集合を複数の部分タグ集合にクラスタリングするソーティング部１３３ｂとで構成されている。
【００４３】
代表タグ選択部１３４は、各部分タグ集合から任意の代表タグをそれぞれ選択する機能を有している。
【００４４】
記憶部１３５は、構築されたデンドログラムや生成されたインデックスを読出可能に記憶しておく機能を有している。なお、このような記憶部１３５としては、例えば、ＲＯＭやＲＡＭ等のメモリや、ハードディスク等の記憶装置で実現可能である。
【００４５】
なお、クラスタリング装置１３を構成している上記各機能部は、単一のサーバ装置で実現することも可能であるし、複数のサーバ装置に各機能を分散配置させた構成で実現することも可能である。
【００４６】
次に、上記構成を有するクラスタリング装置１３の処理フローについて説明する。図６は、クラスタリング装置の全体処理フローを示す図である。
【００４７】
最初に、階層的クラスタリング部１３２により、全体タグ集合が階層的クラスタリングされてデンドログラムが構築され、ボトムアップなインデックスが事前に生成される（Ｓ１）。
【００４８】
次いで、クライアント端末５やその他の上位アプリケーションから要求があった際に、部分クラスタリング部１３３により、Ｓ１で生成されたインデックスが参照され、全体タグ集合が複数の部分タグ集合にクラスタリングされる（Ｓ２）。
【００４９】
最後に、代表タグ選択部１３４により、個別にクラスタ化された各部分タグ集合から最頻出な代表タグがそれぞれ選択され、選択されたｋ個の多様なタグ集合が要求元の上位アプリケーションに返される（Ｓ３）。
【００５０】
ここで、生成されるインデックスがボトムアップであり、そのボトムアップなインデックスを利用してクラスタリングする理由について説明する。
【００５１】
トップダウンにインデックスを生成して部分タグ集合にクラスタリングすることも可能である。例えば、図７に示すように、全体のタグ（Ｔ１〜Ｔ１５）ではなく、斜線タグ（Ｔ１，Ｔ４，Ｔ７，Ｔ９，Ｔ１３，Ｔ１４）を用いて部分タグ集合にクラスタリングする場合について説明する。この場合、全てのタグ（Ｔ１〜Ｔ１５）を部分タグ集合にクラスタリングする場合よりも少ないカット数でクラスタリング可能であるため、中間ノードの分割順位（図７の○で囲まれた数字）は図２に示した場合と異なり、クラスタリングされる部分タグ集合の個数も異なる。
【００５２】
そして、ある中間ノードで集合を分割する際に、分割されてできる部分集合に斜線タグが含まれているか否かを探査することによって、部分タグ集合にクラスタリングできる。
【００５３】
しかしながら、部分タグ集合に斜線タグが存在するかどうかは、デンドログラムを葉ノード（最下層のタグ）まで辿らなければ判定できないため、効率的に部分タグ集合にクラスタリングすることができない。
【００５４】
そこで、本実施の形態では、全体タグ集合上のデンドログラムをボトムアップインデックスとして事前に実体化しておき、ボトムアップに部分タグ集合にクラスタリングしている。
【００５５】
次に、階層的クラスタリング部１３２の処理フローについて具体的に説明する。図８は、階層的クラスタリング部の処理フローを示す図である。
【００５６】
最初に、クラスタリング部１３２ａにより、分類結果格納データベース１２から複数のタグが読み出され、類似度の高いタグが階層状に順次併合されたデンドログラム（樹状図）が構築される（Ｓ１１）。
【００５７】
最後に、インデックス生成部１３２ｂにより、Ｓ１１で構築されたデンドログラムが探索されて、下層から上層を特定可能なボトムアップインデックスが生成されて記憶部１３５に記憶される（Ｓ１２）。
【００５８】
以上から、Ｓ１１により、図９（ａ）に示すようなデンドログラム（全体タグ集合（Ｔ１〜Ｔ１５）上の二分木）が構築され、Ｓ１２により、図９（ｂ）に示すようなボトムアップインデックスが生成される。
【００５９】
通常の階層的クラスタリングの利用シーンでは、このデンドログラム自体は、タグ間の関係を把握することを目的とした可視化に利用される程度であるが、本実施の形態では、この階層をボトムアップなインデックスとして保持する。ボトムアップなインデックスは、デンドログラム中の下層ノードをキーとした索引であり、ある下層ノード（以下、子ノードという場合もある）から上層ノード（以下、親ノードという場合もある）を取得することができる。デンドログラムを構築すれば、デンドログラムを１回スキャンすることによりボトムアップインデックスを生成可能となる。
【００６０】
すなわち、階層的クラスタリング部１３２により、全体タグ集合が階層的クラスタリングされてデンドログラムが構築され、ボトムアップなインデックスが事前に生成されるので、後段の部分クラスタリング部１３３によるクラスタリング処理を高速化することが可能となる。
【００６１】
なお、階層的クラスタリングのアルゴリズムとしては分割型、併合型の双方を利用可能であるが、併合型のアルゴリズムはデンドログラム構築と同時にボトムアップインデックスを生成することもできるため、分岐型のアルゴリズムを用いるよりも高速にボトムアップインデックスを生成することが可能となる。
【００６２】
次に、部分クラスタリング部１３３の処理フローについて具体的に説明する。図１０は、部分クラスタリング部の処理フローを示す図である。
【００６３】
最初に、インデックス参照部１３３ａにより、階層的クラスタリング部１３２によって生成されたインデックス（図９（ｂ）参照）が記憶部１３５から読み出される（Ｓ２１）。
【００６４】
最後に、ソーティング部１３３ｂにより、Ｓ２１で読み出されたインデックスを参照し、上層（親）が同一のタグを併合して部分タグ集合化（クラスタ化）することが、所期の部分タグ集合数（クラスタ数）になるまで繰り返される（Ｓ２２）。
【００６５】
すなわち、部分クラスタリング部１３３は、最初に１つのタグを１つのクラスタと見做してクラスタ数を初期化し、デンドログラムをボトムアップに登りながら併合を発見する度にクラスタをマージしていくボトムアップな処理を行うことを特徴としている。以下、Ｔ１，Ｔ４，Ｔ７，Ｔ９，Ｔ１３，Ｔ１４をクラスタリング対象タグとして、Ｓ２２における処理フローの一例を以下説明する。図１１は、部分クラスタリング部の処理フローの一例を示す図である。
【００６６】
最初に、アプリケーションが要求する指定クラスタ数ｋ、クラスタリング対象となる部分タグ集合Ｔ’、事前に取得したボトムアップインデックスＩＤＸの入力を受け付ける（Ｓ３１）。指定クラスタ数ｋは３、部分タグ集合Ｔ’はＴ１，Ｔ４，Ｔ７，Ｔ９，Ｔ１３，Ｔ１４、ボトムアップインデックスＩＤＸは図９（ｂ）であるとする。
【００６７】
次いで、その時点の一時クラスタ数ｃ（＝｜Ｔ’｜）と、部分タグ集合Ｔ’の親ノードの分割順位をボトムアップインデックスＩＤＸから取得して降順にソートした親ノードリストＰと、親ノードリストＰの中で最も分割順位が大きいノードの親ノードの分割順位が設定された位置ポインタｃｐとを一時変数として設定する（Ｓ３２）。部分タグ集合Ｔ’がＴ１，Ｔ４，Ｔ７，Ｔ９，Ｔ１３，Ｔ１４であることから、この時点で、ｃ＝６、Ｐ＝５，７，８，１１，１４，１５、ｃｐ＝１３が設定される。
【００６８】
次いで、一時クラスタ数ｃと、指定クラスタ数ｋとが比較され（Ｓ３３）、一時クラスタ数ｃが指定クラスタ数ｋよりも大きい場合には、一時クラスタ数ｃが指定クラスタ数ｋに一致するまで以下説明するＳ３４〜Ｓ３９の処理が繰り返される。
【００６９】
次いで、Ｓ３３での比較の結果、一時クラスタ数ｃが指定クラスタ数ｋよりも大きい場合には、親ノードリストＰの中で最も分割順位が大きいノードの親ノードの分割順位をボトムアップインデックスＩＤＸから取得し、位置ポインタｃｐに設定する（Ｓ３４）。親ノードリストＰは変更されていないため、初期の一時値と同じｃｐ＝１３が設定される（図１２、図１３に示す時点Ａ参照）。
【００７０】
次いで、Ｓ３４で新たに設定された位置ポインタｃｐが親ノードリストＰに含まれるか否かを判定する（Ｓ３５）。図１２、図１３の時点Ａを参照すると、ｃｐ＝１３は、Ｐの中に含まれていない。
【００７１】
次いで、Ｓ３５での判定の結果、位置ポインタｃｐが親ノードリストＰに含まれていない場合には、親ノードリストＰの中で最も分割順位が大きいノードの親ノードの分割順位をボトムアップインデックスＩＤＸから取得し、その最も大きいノードの分割順位を、取得した親ノードの分割順位と交換して降順に並び替えた後に、Ｓ３３に戻る（Ｓ３６）。これにより、Ｐ＝５，７，８，１１，１３，１４が設定される。
【００７２】
その後、Ｓ３３、Ｓ３４の処理により、ｃｐ＝１２が設定される（図１２、図１３に示す時点Ｂ参照）。同様に、Ｓ３６、Ｓ３３、Ｓ３４の処理により、Ｐ＝５，７，８，１１，１２，１３、ｃｐ＝１２が設定される（図１２、図１３に示す時点Ｃ参照）。
【００７３】
次いで、Ｓ３５での判定の結果、位置ポインタｃｐが親ノードリストＰに含まれている場合には、これまで処理対象であった部分タグ集合の親ノードと同じ親ノードの他の部分タグ集合が存在すると判断できるため、親ノードリストＰの中で最も大きいノードの分割順位を削除することで、２つの部分タグ集合を併合する（Ｓ３７）。
【００７４】
次いで、親ノードリストＰを降順に並び替え（Ｓ３８）、一時クラスタ数ｃから１を引いた（Ｓ３９）後に、Ｓ３３に戻る。
【００７５】
その後、Ｓ３３、Ｓ３４の処理により、ｃｐ＝４が設定される（図１２、図１３に示す時点Ｄ参照）。同様に、Ｓ３３〜Ｓ３９の処理を繰り返すことにより、現在の処理時点は、図１２、図１３に示す時点Ｅであるとする。
【００７６】
次いで、Ｓ３３での比較の結果、一時クラスタ数ｃが指定クラスタ数ｋよりも大きくない場合には、ｋ個にクラスタリングされた部分タグ集合を出力する（Ｓ４０）。これにより、Ｐ＝３を親ノードとする部分タグ集合（Ｔ１３とＴ１４）と、Ｐ＝４を親ノードとする部分タグ集合（Ｔ１とＴ４）と、Ｐ＝５を親ノードとする部分タグ集合（Ｔ７とＴ９）とが出力される。なお、前述したように、Ｓ４０の処理後、代表タグ選択部１３４により、各部分タグ集合から最頻出な代表タグがそれぞれ選択され、選択されたｋ個の多様なタグ集合が要求元の上位アプリケーションに返される。
【００７７】
以上より、図１４に示すように、第三者によって付与された多数のタグ集合から、閲覧者のユーザ満足度を高める多様なタグ集合を高速に提供することが可能となる。
【００７８】
本実施の形態によれば、全体タグ集合に対して階層的クラスタリングを行ってデンドログラムを構築し、下層から上層を特定可能にするボトムアップなインデックスを事前に生成しておき、上位アプリケーションから要求があった際に、生成されたインデックスを参照して全体タグ集合を複数の部分タグ集合にクラスタリングするので、部分タグ集合へのクラスタリングを高速に実行することができ、タグの再利用時において、タグの曖昧性を解消し、タグ数の爆発を防止することが可能となる。
【００７９】
また、協調的分類システムにおいて収集されたタグの集合を、みなによって合意のとれた客観的タグと、分類軸としてはノイズとなる主観的タグの２つの区分することを実現し、又は人手による区別を支援することにより、サービス提供者のタグの利活用を容易にすることができる。
【００８０】
通常のソーシャルブックマークサービスで利用されているタグの選択方法として、タグ付け回数の多い順に上位からｋ件を取得するという方法がある。しかしながら、単なるタグ付け回数順では、必ずしも本実施の形態で説明したような多様なタグ集合が選ばれるとは限らない。
【００８１】
また、別の方法として、人手でタグが属するカテゴリ辞書を構築し、できるだけ多くの異なるカテゴリに属するタグ集合を選ぶという教師ありの方法が考えられる。しかしながら、協調的分類システムでは第三者が毎時毎分にタグ付け続けるため、辞書を用いた手法では未知タグや意味の不明瞭なタグ（例えば、顔文字や絵文字等）のカテゴリを推測することが困難である。本実施の形態によれば、第三者がタグを分類した結果のみから類似性に関するタグ間の距離を用いてクラスタリングしているので、辞書などを必要とすることなく、教師なしで多様なタグ集合を取得することができる。
【００８２】
最後に、本実施の形態で説明したクラスタリング装置は、コンピュータで構成され、各機能ブロックの各処理はプログラムで実行される。また、本実施の形態で説明したクラスタリング装置をプログラムとして光記憶装置や磁気記憶装置等の記録媒体に読出可能に記録し、この記録媒体をコンピュータに組み込んだり、若しくは記録媒体に記録されたプログラムを、任意の通信回線を介してコンピュータにダウンロードしたり、又は記録媒体からインストールし、該プログラムでコンピュータを動作させることにより、上述した各処理動作をクラスタリング装置として機能させることができるのは勿論である。
【符号の説明】
【００８３】
１…協調的分類システム
１１…通信部
１２…分類結果格納データベース
１３…クラスタリング装置
１３１…通信インタフェース
１３２…階層的クラスタリング部
１３２ａ…クラスタリング部
１３２ｂ…インデックス生成部
１３３…部分クラスタリング部
１３３ａ…インデックス参照部
１３３ｂ…ソーティング部
１３４…代表タグ選択部
１３５…記憶部
３…通信ネットワーク
５…クライアント端末
Ｓ１〜Ｓ３、Ｓ１１〜Ｓ１２、Ｓ２１〜Ｓ２２、Ｓ３１〜Ｓ４０…ステップ
【技術分野】
【０００１】
本発明は、協調的分類システムおいて資源情報に付与された分類軸を再利用する技術に関する。
【背景技術】
【０００２】
昨今、ＵＲＬ（ブックマーク）、写真、動画像、静止画像、本、論文といった様々な資源情報を一次的作成者と異なる第三者が分類整理し、その分類結果を広く共有することにより、鮮度の高い情報を閲覧者に提供できる協調的分類システム（Collaborative/Social Tagging System）が隆盛している。
【０００３】
図１５は、協調的分類システムにおける分類軸（以下、タグという）の分類例を示す図である。資源情報の一例としてＵＲＬを示している。上記第三者である分類者により、ＵＲＬの記載内容「サッカーニュース『今日の結果』」に基づいて、その記載内容に関連する複数のタグ「ｎｅｗｓ」「ｓｏｃｃｅｒ」「面白い」が生成されている。
【０００４】
図１６は、分類者により生成されたタグを再利用する流れを説明する図である。協調的分類システムは、分類者によるタグの自由生成や、生成されたタグを上記ＵＲＬに付与すること（関連付けること）を可能とし、分類結果格納データベース１２に予め格納して再利用している。すなわち、分類者による資源情報の分類結果とも言えるタグを収集し、閲覧者に提供される提示情報を生成する過程において、上記ＵＲＬの記載内容を記述する目的で付与されたタグを分類結果格納データベース１２から読み出して再利用することを実現している。
【０００５】
一方、第三者によるタグの生成や分類対象へのタグ付与が自由であるがゆえに、タグの曖昧性や、タグ数の爆発といった問題が顕在化している。タグが曖昧であるとは、一つのタグが複数の意味を持つこと（多義タグ）や、表記は異なるが意味が同じであること（同義タグ）であることをいう。このような曖昧性や、タグ付け時点での第三者（すなわち、分類者）の感情や好み、世の流行、他の第三者によって付与されたタグの傾向等の影響に起因するタグ数の爆発により、タグを再利用することが困難となっている（非特許文献１参照）。
【０００６】
しかしながら、そのような困難性を有しているにも関わらず、第三者によって付与されたタグを利用すると、提示情報本来には必ずしも含まれない第三者視点特有のタグで資源情報の意味を的確に表現することが可能となり、自動タグ付け（オートタギング）では収集困難な感想や意見を表した主観的タグ（例えば、「これはすごい」、「ｃｏｏｌ」、「後で読む」等）を収集できるため、タグ付けされた情報の記述に度々利用されている。
【０００７】
例えば、写真をタグ付けできるサービスとして「ｆｌｉｃｋｅｒ」（http://filckr.com）、ソーシャルブックマークサービスとして「ｄｅｌ．ｉｃｉｏ．ｕｓ」（http://del.icio.us）や「はてなブックマーク」（http://b.hatena.ne.jp）や「ｇｏｏ ｂｏｏｋｍａｒｋ」（http://bookmark.goo.ne.jp）、動画をタグ付けできるサービスとして「ｙｏｕｔｕｂｅ」（http://youtube.com）、書籍をタグ付けできるサービスとして「米アマゾン」（http://www.amazon.com）、学術論文をタグ付けできるサービスとして「ＣｉｔｅＵＬｉｋｅ」（http://www.citeulike.org/）等が提供されている。なお、実際のサービスでは、付与されたタグ集合のうち、利用頻度の高い順に必要な個数のタグを選択して、提示情報の記述に用いられている。
【０００８】
ここで、どの程度のタグ数を用いて提示情報を生成することが適切であるかが問題である。一般に、商品推薦においては、より多様な商品を推薦する方がユーザ満足度の向上につながるという仮説がある。その仮説に基づいて、推薦結果を多様化する手法が提案されている（非特許文献２）。また、ウェブ検索や画像検索においても、やはり同様の仮説に基づく推薦結果の多様化方法が提案されている（ウェブ検索については非特許文献３，４、画像検索については非特許文献５，６参照）。いずれも、多様な商品をユーザに推薦した後に、そのユーザの要求に基づいてオンデマンドで推薦商品をクラスタリングする手法（Ｐｏｓｔ−Ｐｒｏｃｅｓｓｉｎｇ）である。図１７には、そのような従来手法として、ユーザから要求があった後に、要求点ｒから｜ｍ｜以下の距離を計算し、その距離内の領域を特定の方向で分割して商品をクラスタリングする手法が示されている。なお、クラスタリングとは、全体集合を一部又は全部の部分集合にすることをいう。
【０００９】
すなわち、上記商品をタグに対応させると、出来る限り多くのタグを用いて提供情報を生成することが従来技術であったと言える。
【先行技術文献】
【非特許文献】
【００１０】
【非特許文献１】Scott Golder、外１名、「The Structure of Collaborative Tagging Systems」、Journal of Information Science、2006年
【非特許文献２】Cai-Nicolas Ziegler、外３名、「Improving recommendation lists through topic diversification」、Proc. WWW、2005年
【非特許文献３】Filip Radlinski、外１名、「Improving personalized web search using result diversification」、Proc. SIGIR、2006年
【非特許文献４】Rakesh Agrawal、外１名、「Diversifying search results」、Proc WSDM、2009年
【非特許文献５】Kai Song、外３名、「Diversifying the image retrieval results」、Proc. ACM Multimedia、2006年
【非特許文献６】Reinier H. van Leuken、外３名、「Visual diversification of image search results」、Proc. WWW、2009年
【非特許文献７】神嶌 敏弘、「データマイニング分野のクラスタリング手法（１）」、人口知能学会誌、18巻1号、2003年1月
【発明の概要】
【発明が解決しようとする課題】
【００１１】
しかしながら、タグの再利用時において多くのタグを用いた場合には、前述したように曖昧性を含む複数のタグが存在し、類似する内容を表す複数のタグが収集表示される場合があるため、閲覧者の満足度は低下し、タグの再利用性が低下するという問題がある。
【００１２】
本発明は、上記課題を鑑みてなされたものであり、タグの再利用時において、タグの曖昧性を解消し、タグ数の爆発を防止することを課題とする。
【課題を解決するための手段】
【００１３】
請求項１に記載の本発明は、所定の情報を特徴付ける複数の分類軸のうち類似度の高い分類軸を階層状に順次併合する樹状図を構築し、前記樹状図を探索して下層から上層を特定可能なインデックスを生成して記憶手段に記憶しておく階層的クラスタリング手段、を有することを特徴とする。
【００１４】
本発明によれば、所定の情報を特徴付ける複数の分類軸のうち類似度の高い分類軸を階層状に順次併合する樹状図を構築し、樹状図を探索して下層から上層を特定可能なインデックスを生成して記憶手段に記憶しておくため、後段のクラスタリング処理を高速化することが可能となる。
【００１５】
請求項２に記載の本発明は、前記記憶手段から読み出した前記インデックスを参照し、前記上層が同一の分類軸を併合してクラスタ化することを所期のクラスタ数になるまで繰り返す部分クラスタリング手段、を更に有することを特徴とする。
【００１６】
本発明によれば、記憶手段から読み出したインデックスを参照し、上層が同一の分類軸を併合してクラスタ化することを所期のクラスタ数になるまで繰り返すため、タグの曖昧性を解消し、タグ数の爆発を防止することが可能となる。
【００１７】
請求項３に記載の本発明は、所定の情報を特徴付ける複数の分類軸のうち類似度の高い分類軸を階層状に順次併合する樹状図を構築し、前記樹状図を探索して下層から上層を特定可能なインデックスを生成して記憶手段に記憶しておくステップ、を有することを特徴とする。
【００１８】
本発明によれば、所定の情報を特徴付ける複数の分類軸のうち類似度の高い分類軸を階層状に順次併合する樹状図を構築し、樹状図を探索して下層から上層を特定可能なインデックスを生成して記憶手段に記憶しておくため、後段のクラスタリング処理を高速化することが可能となる。
【００１９】
請求項４に記載の本発明は、前記記憶手段から読み出した前記インデックスを参照し、前記上層が同一の分類軸を併合してクラスタ化することを所期のクラスタ数になるまで繰り返すステップ、を更に有することを特徴とする。
【００２０】
本発明によれば、記憶手段から読み出したインデックスを参照し、上層が同一の分類軸を併合してクラスタ化することを所期のクラスタ数になるまで繰り返すため、タグの曖昧性を解消し、タグ数の爆発を防止することが可能となる。
【００２１】
請求項５に記載の本発明は、請求項３又は４に記載した各ステップをコンピュータに実行させることを特徴とする。
【発明の効果】
【００２２】
本発明によれば、タグの再利用時において、タグの曖昧性を解消し、タグ数の爆発を防止することができる。
【図面の簡単な説明】
【００２３】
【図１】クラスタ化の概念を説明する図である。
【図２】階層的クラスタリングによって構築されるデンドログラムの一例を示す図である。
【図３】多様なタグで提示情報を記述するメリット・デメリットを説明する図である。
【図４】全体システムの機能ブロック構成を概略的に示す図である。
【図５】クラスタリング装置の機能ブロック構成を概略的に示す図である。
【図６】クラスタリング装置の全体処理フローを示す図である。
【図７】部分タグ集合へのクラスタリングを説明する図である。
【図８】階層的クラスタリング部の処理フローを示す図である。
【図９】デンドログラムとボトムアップインデックスの一例を示す図である。
【図１０】部分クラスタリング部の処理フローを示す図である。
【図１１】部分クラスタリング部の処理フローの一例を示す図である。
【図１２】部分クラスタリングの遷移を説明する図である。
【図１３】タグの所属クラスタの遷移を説明する図である。
【図１４】クラスタリングされたタグ集合の一例を示す図である。
【図１５】協調的分類システムにおける分類軸の分類例を示す図である。
【図１６】分類者により生成されたタグを再利用する流れを説明する図である。
【図１７】従来のクラスタ化の概念を説明する図である。
【発明を実施するための形態】
【００２４】
以下、本発明を実施する一実施の形態について図面を用いて説明する。但し、本発明は多くの異なる様態で実施することが可能であり、本実施の形態の記載内容に限定して解釈すべきではない。
【００２５】
本実施の形態に係るクラスタリング装置の構成及び処理について説明する前に、理解を容易にするために本発明の概要について事前説明する。本実施の形態は、背景技術で説明した協調的分類システムにおいて、付与された分類軸（以下、タグという）を利用して閲覧者への提供情報を生成する際に、第三者によって生成された様々なタグをできる限り多様かつ高速に選択することにより、タグの再利用時におけるタグの曖昧性を解消し、タグ数の爆発を防止することにある。
【００２６】
すなわち、図１に示すように、図１７に示した対象タグ以外に複数のタグを考慮した状態で全てのタグを事前にクラスタリングしておき（Ｐｒｅ−Ｐｒｏｃｅｓｓｉｎｇ）、その事前クラスタリングの結果をインデックスとして利用することにより、従来よりも高速にタグの多様化を行うものである。
【００２７】
なお、クラスタリングには、分割最適化手法と階層的手法があるが（非特許文献７参照）、本実施の形態では階層的手法を用いる。すなわち、階層的クラスタリングにより構築されるタグ集合上のデンドログラムを利用している。ここで、階層的クラスタリングによって構築されるデンドログラムの特徴について以下説明する。
【００２８】
図２は、階層的クラスタリングによって構築されるデンドログラムの一例を示す図である。このデンドログラムは、２分木構造を有し、類似性の高いタグを１つずつ纏めていくと最後には全体のタグ集合になり（凝集型）、逆に、全体のタグ集合を半分に分割していく操作を繰り返すと最後にはそれぞれ単独のタグになる（分岐型）という特徴がある。本発明は、凝集型又は分岐型のいずれのアルゴリズムにも適用可能であるが、分岐型について説明する。
【００２９】
図２の中間ノードに付与されている数字は、全体集合を上層ノードから下層ノードに向けて順番に分割する順番を表している。例えば、根ノードからたどり、２番の中間ノードでデンドログラムをカットすると、全体集合は２分割される。引き続き、３番の中間ノードでカットすると、全体集合は３分割される。さらに４番の中間ノードでカットすると４分割（図２に示すＡ〜Ｄ）され、結果として中間ノードの数字で全体集合をクラスタリングしたことになる。この性質により、いったんデンドログラムをタグ集合上に構築すると、タグの総数以下の任意の個数にカットすることが可能となる。なお、カットとはクラスタリングすることをいう。
【００３０】
一方、通常の分割最適化手法では、タグ集合をいくつかにカットしてクラスタリングすることはデータに依存しており、チューニングされる項目の一つである。本実施の形態で用いる階層的クラスタリングでは、いったんデンドログラムをタグ集合上に構築すれば、任意の個数のクラスタリング結果をデンドログラムのカットのみで得ることができる。つまり、階層的クラスタリングを構築してデンドログラムを生成することは、任意のクラスタ数を生成することが可能となることに等しい。
【００３１】
なお、本実施の形態は、多様なタグ集合は有効であることを前提としている。多様なタグの集合とは、互いに意味が似通っていないタグの集まり、又は、似通っているタグも含まれるが大きく意味の異なるタグを含むタグの集まりである。多様なタグの集合として、「Ｗｅｂ」「エッセイ」「Ｇｏｏｇｌｅ」「後で読む」「ＨＴＴＰ」を一例に挙げることができる。一方、多様でないタグの集合とは、どれも意味的に近い内容を表しており、例えば、「Ｗｅｂ」「Ｗｅｂ２．０」「ＷＷＷ」「Ｉｎｔｅｒｎｅｔ」「ＨＴＴＰ」等を挙げることができる。
【００３２】
参考までに、多様なタグで提示情報を記述するメリット・デメリットを図３に示す。「サッカー」「ゴール」「ニュース」「ｓｏｃｃｅｒ」といった類似度の高いタグ集合を提示するよりも、「サッカー」「ブラジル」「ニュース」「珍プレー」といった類似度の低い多様なタグ集合の方が、提示情報から適切に情報を把握することが可能となる。
【００３３】
次に、本実施の形態に係るクラスタリング装置を有する全体のシステム構成について説明する。図４は、全体システムの機能ブロック構成を概略的に示す図である。全体システムは、タグの分類者や提示情報の閲覧者（以下、ユーザと総称する）が利用するクライアント端末５と、インターネット等の通信ネットワーク３を介してクライアント端末５と通信可能な協調的分類システム１とで構成されている。
【００３４】
協調的分類システム１は、ネットワークサービスとして提供され、ユーザはクライアント端末５に搭載されたウェブブラウザやクライアントアプリケーションを通じて該ネットワークサービスを利用することができる。具体的には、ＬＡＮやルータ等の通信部１１と、データを格納する分類結果格納データベース１２と、実際に処理を実現するクラスタリング装置１３とで構成されている。
【００３５】
なお、協調的分類システム１は、背景技術で説明したように、分類者によるタグの自由生成や、生成されたタグを分類対象に付与することを可能とするアプリケーションを具備しているが、当該アプリケーションに係る具体的機能、処理内容の説明は省略する。協調的分類システム１の一例として、ソーシャルブックマークサービス（Social Bookmark Service：各ユーザのブックマークをネットワークを通じて共有するシステム）が挙げられる。
【００３６】
通信部１１は、協調的分類システム１による外部又は内部への通信、又は内部間通信等の通信をネットワークレベルで実現している。
【００３７】
分類結果格納データベース１２は、背景技術で説明したように、ＵＲＬ（ブックマーク）、写真、動画像、静止画像、本、論文といった様々な資源情報に基づいて分類者によって自由生成されたタグや、資源情報に付与されたタグを読出可能に格納しておく機能を有している。
【００３８】
なお、本実施の形態では、タグが予め生成されて分類結果格納データベース１２に格納されていればよく、クラスタリング装置１３は、どのような方法に基づいて生成されたタグであっても、どのような種類のタグであっても、後述する処理を実行することにより、タグの生成方法やタグの種類に関係なく同様の効果を得ることができる。
【００３９】
クラスタリング装置１３は、図５に示すように、通信インタフェース１３１と、階層的クラスタリング部１３２と、部分クラスタリング部１３３と、代表タグ選択部１３４と、記憶部１３５とで構成されている。
【００４０】
通信インタフェース１３１は、通信部１１や分類結果格納データベースとの間の通信を仲介する機能を有している。
【００４１】
階層的クラスタリング部１３２は、複数のタグ（以下、全体タグ集合という）を階層的にクラスタリングしてデンドログラムを構築するクラスタリング部１３２ａと、デンドログラムを探索してボトムアップなインデックスを生成するインデックス生成部１３２ｂとで構成されている。
【００４２】
部分クラスタリング部１３３は、生成されたインデックスを参照するインデックス参照部１３３ａと、参照インデックスを利用して全体タグ集合を複数の部分タグ集合にクラスタリングするソーティング部１３３ｂとで構成されている。
【００４３】
代表タグ選択部１３４は、各部分タグ集合から任意の代表タグをそれぞれ選択する機能を有している。
【００４４】
記憶部１３５は、構築されたデンドログラムや生成されたインデックスを読出可能に記憶しておく機能を有している。なお、このような記憶部１３５としては、例えば、ＲＯＭやＲＡＭ等のメモリや、ハードディスク等の記憶装置で実現可能である。
【００４５】
なお、クラスタリング装置１３を構成している上記各機能部は、単一のサーバ装置で実現することも可能であるし、複数のサーバ装置に各機能を分散配置させた構成で実現することも可能である。
【００４６】
次に、上記構成を有するクラスタリング装置１３の処理フローについて説明する。図６は、クラスタリング装置の全体処理フローを示す図である。
【００４７】
最初に、階層的クラスタリング部１３２により、全体タグ集合が階層的クラスタリングされてデンドログラムが構築され、ボトムアップなインデックスが事前に生成される（Ｓ１）。
【００４８】
次いで、クライアント端末５やその他の上位アプリケーションから要求があった際に、部分クラスタリング部１３３により、Ｓ１で生成されたインデックスが参照され、全体タグ集合が複数の部分タグ集合にクラスタリングされる（Ｓ２）。
【００４９】
最後に、代表タグ選択部１３４により、個別にクラスタ化された各部分タグ集合から最頻出な代表タグがそれぞれ選択され、選択されたｋ個の多様なタグ集合が要求元の上位アプリケーションに返される（Ｓ３）。
【００５０】
ここで、生成されるインデックスがボトムアップであり、そのボトムアップなインデックスを利用してクラスタリングする理由について説明する。
【００５１】
トップダウンにインデックスを生成して部分タグ集合にクラスタリングすることも可能である。例えば、図７に示すように、全体のタグ（Ｔ１〜Ｔ１５）ではなく、斜線タグ（Ｔ１，Ｔ４，Ｔ７，Ｔ９，Ｔ１３，Ｔ１４）を用いて部分タグ集合にクラスタリングする場合について説明する。この場合、全てのタグ（Ｔ１〜Ｔ１５）を部分タグ集合にクラスタリングする場合よりも少ないカット数でクラスタリング可能であるため、中間ノードの分割順位（図７の○で囲まれた数字）は図２に示した場合と異なり、クラスタリングされる部分タグ集合の個数も異なる。
【００５２】
そして、ある中間ノードで集合を分割する際に、分割されてできる部分集合に斜線タグが含まれているか否かを探査することによって、部分タグ集合にクラスタリングできる。
【００５３】
しかしながら、部分タグ集合に斜線タグが存在するかどうかは、デンドログラムを葉ノード（最下層のタグ）まで辿らなければ判定できないため、効率的に部分タグ集合にクラスタリングすることができない。
【００５４】
そこで、本実施の形態では、全体タグ集合上のデンドログラムをボトムアップインデックスとして事前に実体化しておき、ボトムアップに部分タグ集合にクラスタリングしている。
【００５５】
次に、階層的クラスタリング部１３２の処理フローについて具体的に説明する。図８は、階層的クラスタリング部の処理フローを示す図である。
【００５６】
最初に、クラスタリング部１３２ａにより、分類結果格納データベース１２から複数のタグが読み出され、類似度の高いタグが階層状に順次併合されたデンドログラム（樹状図）が構築される（Ｓ１１）。
【００５７】
最後に、インデックス生成部１３２ｂにより、Ｓ１１で構築されたデンドログラムが探索されて、下層から上層を特定可能なボトムアップインデックスが生成されて記憶部１３５に記憶される（Ｓ１２）。
【００５８】
以上から、Ｓ１１により、図９（ａ）に示すようなデンドログラム（全体タグ集合（Ｔ１〜Ｔ１５）上の二分木）が構築され、Ｓ１２により、図９（ｂ）に示すようなボトムアップインデックスが生成される。
【００５９】
通常の階層的クラスタリングの利用シーンでは、このデンドログラム自体は、タグ間の関係を把握することを目的とした可視化に利用される程度であるが、本実施の形態では、この階層をボトムアップなインデックスとして保持する。ボトムアップなインデックスは、デンドログラム中の下層ノードをキーとした索引であり、ある下層ノード（以下、子ノードという場合もある）から上層ノード（以下、親ノードという場合もある）を取得することができる。デンドログラムを構築すれば、デンドログラムを１回スキャンすることによりボトムアップインデックスを生成可能となる。
【００６０】
すなわち、階層的クラスタリング部１３２により、全体タグ集合が階層的クラスタリングされてデンドログラムが構築され、ボトムアップなインデックスが事前に生成されるので、後段の部分クラスタリング部１３３によるクラスタリング処理を高速化することが可能となる。
【００６１】
なお、階層的クラスタリングのアルゴリズムとしては分割型、併合型の双方を利用可能であるが、併合型のアルゴリズムはデンドログラム構築と同時にボトムアップインデックスを生成することもできるため、分岐型のアルゴリズムを用いるよりも高速にボトムアップインデックスを生成することが可能となる。
【００６２】
次に、部分クラスタリング部１３３の処理フローについて具体的に説明する。図１０は、部分クラスタリング部の処理フローを示す図である。
【００６３】
最初に、インデックス参照部１３３ａにより、階層的クラスタリング部１３２によって生成されたインデックス（図９（ｂ）参照）が記憶部１３５から読み出される（Ｓ２１）。
【００６４】
最後に、ソーティング部１３３ｂにより、Ｓ２１で読み出されたインデックスを参照し、上層（親）が同一のタグを併合して部分タグ集合化（クラスタ化）することが、所期の部分タグ集合数（クラスタ数）になるまで繰り返される（Ｓ２２）。
【００６５】
すなわち、部分クラスタリング部１３３は、最初に１つのタグを１つのクラスタと見做してクラスタ数を初期化し、デンドログラムをボトムアップに登りながら併合を発見する度にクラスタをマージしていくボトムアップな処理を行うことを特徴としている。以下、Ｔ１，Ｔ４，Ｔ７，Ｔ９，Ｔ１３，Ｔ１４をクラスタリング対象タグとして、Ｓ２２における処理フローの一例を以下説明する。図１１は、部分クラスタリング部の処理フローの一例を示す図である。
【００６６】
最初に、アプリケーションが要求する指定クラスタ数ｋ、クラスタリング対象となる部分タグ集合Ｔ’、事前に取得したボトムアップインデックスＩＤＸの入力を受け付ける（Ｓ３１）。指定クラスタ数ｋは３、部分タグ集合Ｔ’はＴ１，Ｔ４，Ｔ７，Ｔ９，Ｔ１３，Ｔ１４、ボトムアップインデックスＩＤＸは図９（ｂ）であるとする。
【００６７】
次いで、その時点の一時クラスタ数ｃ（＝｜Ｔ’｜）と、部分タグ集合Ｔ’の親ノードの分割順位をボトムアップインデックスＩＤＸから取得して降順にソートした親ノードリストＰと、親ノードリストＰの中で最も分割順位が大きいノードの親ノードの分割順位が設定された位置ポインタｃｐとを一時変数として設定する（Ｓ３２）。部分タグ集合Ｔ’がＴ１，Ｔ４，Ｔ７，Ｔ９，Ｔ１３，Ｔ１４であることから、この時点で、ｃ＝６、Ｐ＝５，７，８，１１，１４，１５、ｃｐ＝１３が設定される。
【００６８】
次いで、一時クラスタ数ｃと、指定クラスタ数ｋとが比較され（Ｓ３３）、一時クラスタ数ｃが指定クラスタ数ｋよりも大きい場合には、一時クラスタ数ｃが指定クラスタ数ｋに一致するまで以下説明するＳ３４〜Ｓ３９の処理が繰り返される。
【００６９】
次いで、Ｓ３３での比較の結果、一時クラスタ数ｃが指定クラスタ数ｋよりも大きい場合には、親ノードリストＰの中で最も分割順位が大きいノードの親ノードの分割順位をボトムアップインデックスＩＤＸから取得し、位置ポインタｃｐに設定する（Ｓ３４）。親ノードリストＰは変更されていないため、初期の一時値と同じｃｐ＝１３が設定される（図１２、図１３に示す時点Ａ参照）。
【００７０】
次いで、Ｓ３４で新たに設定された位置ポインタｃｐが親ノードリストＰに含まれるか否かを判定する（Ｓ３５）。図１２、図１３の時点Ａを参照すると、ｃｐ＝１３は、Ｐの中に含まれていない。
【００７１】
次いで、Ｓ３５での判定の結果、位置ポインタｃｐが親ノードリストＰに含まれていない場合には、親ノードリストＰの中で最も分割順位が大きいノードの親ノードの分割順位をボトムアップインデックスＩＤＸから取得し、その最も大きいノードの分割順位を、取得した親ノードの分割順位と交換して降順に並び替えた後に、Ｓ３３に戻る（Ｓ３６）。これにより、Ｐ＝５，７，８，１１，１３，１４が設定される。
【００７２】
その後、Ｓ３３、Ｓ３４の処理により、ｃｐ＝１２が設定される（図１２、図１３に示す時点Ｂ参照）。同様に、Ｓ３６、Ｓ３３、Ｓ３４の処理により、Ｐ＝５，７，８，１１，１２，１３、ｃｐ＝１２が設定される（図１２、図１３に示す時点Ｃ参照）。
【００７３】
次いで、Ｓ３５での判定の結果、位置ポインタｃｐが親ノードリストＰに含まれている場合には、これまで処理対象であった部分タグ集合の親ノードと同じ親ノードの他の部分タグ集合が存在すると判断できるため、親ノードリストＰの中で最も大きいノードの分割順位を削除することで、２つの部分タグ集合を併合する（Ｓ３７）。
【００７４】
次いで、親ノードリストＰを降順に並び替え（Ｓ３８）、一時クラスタ数ｃから１を引いた（Ｓ３９）後に、Ｓ３３に戻る。
【００７５】
その後、Ｓ３３、Ｓ３４の処理により、ｃｐ＝４が設定される（図１２、図１３に示す時点Ｄ参照）。同様に、Ｓ３３〜Ｓ３９の処理を繰り返すことにより、現在の処理時点は、図１２、図１３に示す時点Ｅであるとする。
【００７６】
次いで、Ｓ３３での比較の結果、一時クラスタ数ｃが指定クラスタ数ｋよりも大きくない場合には、ｋ個にクラスタリングされた部分タグ集合を出力する（Ｓ４０）。これにより、Ｐ＝３を親ノードとする部分タグ集合（Ｔ１３とＴ１４）と、Ｐ＝４を親ノードとする部分タグ集合（Ｔ１とＴ４）と、Ｐ＝５を親ノードとする部分タグ集合（Ｔ７とＴ９）とが出力される。なお、前述したように、Ｓ４０の処理後、代表タグ選択部１３４により、各部分タグ集合から最頻出な代表タグがそれぞれ選択され、選択されたｋ個の多様なタグ集合が要求元の上位アプリケーションに返される。
【００７７】
以上より、図１４に示すように、第三者によって付与された多数のタグ集合から、閲覧者のユーザ満足度を高める多様なタグ集合を高速に提供することが可能となる。
【００７８】
本実施の形態によれば、全体タグ集合に対して階層的クラスタリングを行ってデンドログラムを構築し、下層から上層を特定可能にするボトムアップなインデックスを事前に生成しておき、上位アプリケーションから要求があった際に、生成されたインデックスを参照して全体タグ集合を複数の部分タグ集合にクラスタリングするので、部分タグ集合へのクラスタリングを高速に実行することができ、タグの再利用時において、タグの曖昧性を解消し、タグ数の爆発を防止することが可能となる。
【００７９】
また、協調的分類システムにおいて収集されたタグの集合を、みなによって合意のとれた客観的タグと、分類軸としてはノイズとなる主観的タグの２つの区分することを実現し、又は人手による区別を支援することにより、サービス提供者のタグの利活用を容易にすることができる。
【００８０】
通常のソーシャルブックマークサービスで利用されているタグの選択方法として、タグ付け回数の多い順に上位からｋ件を取得するという方法がある。しかしながら、単なるタグ付け回数順では、必ずしも本実施の形態で説明したような多様なタグ集合が選ばれるとは限らない。
【００８１】
また、別の方法として、人手でタグが属するカテゴリ辞書を構築し、できるだけ多くの異なるカテゴリに属するタグ集合を選ぶという教師ありの方法が考えられる。しかしながら、協調的分類システムでは第三者が毎時毎分にタグ付け続けるため、辞書を用いた手法では未知タグや意味の不明瞭なタグ（例えば、顔文字や絵文字等）のカテゴリを推測することが困難である。本実施の形態によれば、第三者がタグを分類した結果のみから類似性に関するタグ間の距離を用いてクラスタリングしているので、辞書などを必要とすることなく、教師なしで多様なタグ集合を取得することができる。
【００８２】
最後に、本実施の形態で説明したクラスタリング装置は、コンピュータで構成され、各機能ブロックの各処理はプログラムで実行される。また、本実施の形態で説明したクラスタリング装置をプログラムとして光記憶装置や磁気記憶装置等の記録媒体に読出可能に記録し、この記録媒体をコンピュータに組み込んだり、若しくは記録媒体に記録されたプログラムを、任意の通信回線を介してコンピュータにダウンロードしたり、又は記録媒体からインストールし、該プログラムでコンピュータを動作させることにより、上述した各処理動作をクラスタリング装置として機能させることができるのは勿論である。
【符号の説明】
【００８３】
１…協調的分類システム
１１…通信部
１２…分類結果格納データベース
１３…クラスタリング装置
１３１…通信インタフェース
１３２…階層的クラスタリング部
１３２ａ…クラスタリング部
１３２ｂ…インデックス生成部
１３３…部分クラスタリング部
１３３ａ…インデックス参照部
１３３ｂ…ソーティング部
１３４…代表タグ選択部
１３５…記憶部
３…通信ネットワーク
５…クライアント端末
Ｓ１〜Ｓ３、Ｓ１１〜Ｓ１２、Ｓ２１〜Ｓ２２、Ｓ３１〜Ｓ４０…ステップ
【特許請求の範囲】
【請求項１】
所定の情報を特徴付ける複数の分類軸のうち類似度の高い分類軸を階層状に順次併合する樹状図を構築し、前記樹状図を探索して下層から上層を特定可能なインデックスを生成して記憶手段に記憶しておく階層的クラスタリング手段、
を有することを特徴とするクラスタリング装置。
【請求項２】
前記記憶手段から読み出した前記インデックスを参照し、前記上層が同一の分類軸を併合してクラスタ化することを所期のクラスタ数になるまで繰り返す部分クラスタリング手段、
を更に有することを特徴とする請求項１に記載のクラスタリング装置。
【請求項３】
所定の情報を特徴付ける複数の分類軸のうち類似度の高い分類軸を階層状に順次併合する樹状図を構築し、前記樹状図を探索して下層から上層を特定可能なインデックスを生成して記憶手段に記憶しておくステップ、
を有することを特徴とするクラスタリング方法。
【請求項４】
前記記憶手段から読み出した前記インデックスを参照し、前記上層が同一の分類軸を併合してクラスタ化することを所期のクラスタ数になるまで繰り返すステップ、
を更に有することを特徴とする請求項３に記載のクラスタリング方法。
【請求項５】
請求項３又は４に記載した各ステップをコンピュータに実行させることを特徴とするクラスタリングプログラム。
【請求項１】
所定の情報を特徴付ける複数の分類軸のうち類似度の高い分類軸を階層状に順次併合する樹状図を構築し、前記樹状図を探索して下層から上層を特定可能なインデックスを生成して記憶手段に記憶しておく階層的クラスタリング手段、
を有することを特徴とするクラスタリング装置。
【請求項２】
前記記憶手段から読み出した前記インデックスを参照し、前記上層が同一の分類軸を併合してクラスタ化することを所期のクラスタ数になるまで繰り返す部分クラスタリング手段、
を更に有することを特徴とする請求項１に記載のクラスタリング装置。
【請求項３】
所定の情報を特徴付ける複数の分類軸のうち類似度の高い分類軸を階層状に順次併合する樹状図を構築し、前記樹状図を探索して下層から上層を特定可能なインデックスを生成して記憶手段に記憶しておくステップ、
を有することを特徴とするクラスタリング方法。
【請求項４】
前記記憶手段から読み出した前記インデックスを参照し、前記上層が同一の分類軸を併合してクラスタ化することを所期のクラスタ数になるまで繰り返すステップ、
を更に有することを特徴とする請求項３に記載のクラスタリング方法。
【請求項５】
請求項３又は４に記載した各ステップをコンピュータに実行させることを特徴とするクラスタリングプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【公開番号】特開２０１１−２１６０２１（Ｐ２０１１−２１６０２１Ａ）
【公開日】平成２３年１０月２７日（２０１１．１０．２７）
【国際特許分類】
【出願番号】特願２０１０−８５４１８（Ｐ２０１０−８５４１８）
【出願日】平成２２年４月１日（２０１０．４．１）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２３年１０月２７日（２０１１．１０．２７）
【国際特許分類】
【出願日】平成２２年４月１日（２０１０．４．１）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]