(57)【要約】【課題】クエリーに適合する高次元ベクトルを効率的に検索することが可能な情報処理装置を提供すること。【解決手段】複数の疎なコンテンツベクトルを当該コンテンツベクトルが属する高次元ベクトル空間の部分空間を用いて分類するクラスタリング処理部と、クラスタリング処理部により疎なコンテンツベクトルの分類に用いられた部分空間の中から、クエリーとして入力された入力ベクトルに近いコンテンツベクトルが含まれる部分空間を選択する部分空間選択部と、部分空間選択部により選択された一又は複数の部分空間に含まれるコンテンツベクトルの中から、入力ベクトルに近いコンテンツベクトルを推薦ベクトルとして算出する推薦ベクトル算出部とを備える、情報処理装置が提供される。【選択図】図１
2010015441.tif 000002
【特許請求の範囲】
【請求項１】
複数の疎なコンテンツベクトルを当該コンテンツベクトルが属する高次元ベクトル空間の部分空間を用いて分類するクラスタリング処理部と、
前記クラスタリング処理部により前記疎なコンテンツベクトルの分類に用いられた部分空間の中から、クエリーとして入力された入力ベクトルに近いコンテンツベクトルが含まれる部分空間を選択する部分空間選択部と、
前記部分空間選択部により選択された一又は複数の部分空間に含まれる前記コンテンツベクトルの中から、前記入力ベクトルに近いコンテンツベクトルを推薦ベクトルとして算出する推薦ベクトル算出部と、
を備える、情報処理装置。
【請求項２】
前記クラスタリング処理部は、前記コンテンツベクトルが属する高次元ベクトル空間を複数の低次元の部分空間に分割し、前記高次元ベクトル空間から特定の次元を選択するためのバイナリマスクにより表現される前記低次元の部分空間を用いて前記複数の疎なコンテンツベクトルを分類する、請求項１に記載の情報処理装置。
【請求項３】
前記クラスタリング処理部は、前記疎なコンテンツベクトルの非ゼロ成分を被覆するバイナリマスクを求めることで前記部分空間に対する前記疎なコンテンツベクトルの帰属を定める、請求項２に記載の情報処理装置。
【請求項４】
複数のコンテンツベクトルを包含するように、前記コンテンツベクトルが属する高次元ベクトル空間の部分空間群が生成されるクラスタリングステップと、
前記クラスタリングステップで生成された部分空間群の中から、クエリーとして入力された入力ベクトルに近いコンテンツベクトルが含まれる部分空間が選択される部分空間選択ステップと、
前記部分空間選択ステップで選択された一又は複数の部分空間に対応する前記コンテンツベクトルの中から、前記入力ベクトルに近いコンテンツベクトルが推薦ベクトルとして算出される推薦ベクトル算出ステップと、
を含む、コンテンツ情報の検索方法。
【請求項５】
複数の疎なコンテンツベクトルを当該コンテンツベクトルが属する高次元ベクトル空間の部分空間を用いて分類するクラスタリング処理部を有する第１のサーバと、
前記クラスタリング処理部により前記疎なコンテンツベクトルの分類に用いられた部分空間の中から、クエリーとして入力された入力ベクトルに近いコンテンツベクトルが含まれる部分空間を選択する部分空間選択部を有する第２のサーバと、
前記部分空間選択部により選択された一又は複数の部分空間に含まれる前記コンテンツベクトルの中から、前記入力ベクトルに近いコンテンツベクトルを推薦ベクトルとして算出する推薦ベクトル算出部を有する第３のサーバと、
を含む、情報処理システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置、コンテンツ情報の検索方法、及び情報処理システムに関する。
【背景技術】
【０００２】
近年、情報処理技術、および通信技術の急速な発展に伴い、大量の情報がネットワークを通じて提供されるようになってきた。また、ユーザが保有する情報機器の形態が多様化する中で、多種多様な情報が提供されるようになってきている。例えば、インターネット等の広域ネットワークを介してパーソナルコンピュータ（以下、ＰＣ）等に配信される情報もあれば、テレビジョン受像機等に配信される放送番組や放送情報等もある。
【０００３】
こうした状況の中で、膨大な情報の中からユーザが好む情報（以下、嗜好情報）を効率良く提供するための技術に注目が集まっている。より適切な情報をユーザに提供するために、例えば、複数のユーザが持つ嗜好情報を用いてユーザ同士の関連度を算出し、その関連度を用いてユーザに提供すべきコンテンツ情報を決定する技術が知られている。また、コンテンツ情報の間の類似度を算出し、ユーザが選択したコンテンツの情報に対して高い類似度を有する他のコンテンツ情報をユーザに提供する技術も知られている（特許文献１を参照）。
【０００４】
【特許文献１】特開２００７−２４１８８８号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
こうした関連度や類似度は、コンテンツ情報をベクトル形式で表現したコンテンツベクトル等に基づいて算出される。ところが、こうしたコンテンツベクトルは通常巨大な次元数を持つ高次元ベクトルとなっている。そのため、ユーザがコンテンツ情報を検索するために入力したベクトルと全コンテンツベクトルとの間のマッチング処理を行う際に非常に大きな演算負荷が掛かってしまう。
【０００６】
その結果、多くのユーザからのアクセスがサーバに集中した場合や、サーバに蓄積されるコンテンツの数が増加した場合、各ユーザの入力ベクトルに適合するコンテンツベクトルの検索処理に時間が掛かり、コンテンツ情報の提供に大きな遅延が発生してしまう。
【０００７】
そこで、本発明は、上記問題に鑑みてなされたものであり、本発明の目的とするところは、入力ベクトルに近いコンテンツベクトルの検索にかかる演算負荷を低減することが可能な、新規かつ改良された情報処理装置、コンテンツ情報の検索方法、及び情報処理システムを提供することにある。
【課題を解決するための手段】
【０００８】
上記課題を解決するために、本発明のある観点によれば、複数の疎なコンテンツベクトルを当該コンテンツベクトルが属する高次元ベクトル空間の部分空間を用いて分類するクラスタリング処理部と、前記クラスタリング処理部により前記疎なコンテンツベクトルの分類に用いられた部分空間の中から、クエリーとして入力された入力ベクトルに近いコンテンツベクトルが含まれる部分空間を選択する部分空間選択部と、前記部分空間選択部により選択された一又は複数の部分空間に含まれる前記コンテンツベクトルの中から、前記入力ベクトルに近いコンテンツベクトルを推薦ベクトルとして算出する推薦ベクトル算出部と、を備える、情報処理装置が提供される。
【０００９】
また、前記クラスタリング処理部は、前記コンテンツベクトルが属する高次元ベクトル空間を複数の低次元の部分空間に分割し、前記高次元ベクトル空間から特定の次元を選択するためのバイナリマスクにより表現される前記低次元の部分空間を用いて前記複数の疎なコンテンツベクトルを分類するように構成されていてもよい。
【００１０】
また、前記クラスタリング処理部は、前記疎なコンテンツベクトルの非ゼロ成分を被覆するバイナリマスクを求めることで前記部分空間に対する前記疎なコンテンツベクトルの帰属を定めるように構成されていてもよい。
【００１１】
また、上記課題を解決するために、本発明の別の観点によれば、複数のコンテンツベクトルを包含するように、前記コンテンツベクトルが属する高次元ベクトル空間の部分空間群が生成されるクラスタリングステップと、前記クラスタリングステップで生成された部分空間群の中から、クエリーとして入力された入力ベクトルに近いコンテンツベクトルが含まれる部分空間が選択される部分空間選択ステップと、前記部分空間選択ステップで選択された一又は複数の部分空間に対応する前記コンテンツベクトルの中から、前記入力ベクトルに近いコンテンツベクトルが推薦ベクトルとして算出される推薦ベクトル算出ステップと、を含む、コンテンツ情報の検索方法が提供される。
【００１２】
また、上記課題を解決するために、本発明の別の観点によれば、複数の疎なコンテンツベクトルを当該コンテンツベクトルが属する高次元ベクトル空間の部分空間を用いて分類するクラスタリング処理部を有する第１のサーバと、前記クラスタリング処理部により前記疎なコンテンツベクトルの分類に用いられた部分空間の中から、クエリーとして入力された入力ベクトルに近いコンテンツベクトルが含まれる部分空間を選択する部分空間選択部を有する第２のサーバと、前記部分空間選択部により選択された一又は複数の部分空間に含まれる前記コンテンツベクトルの中から、前記入力ベクトルに近いコンテンツベクトルを推薦ベクトルとして算出する推薦ベクトル算出部を有する第３のサーバと、を含む、情報処理システムが提供される。
【発明の効果】
【００１３】
以上説明したように本発明によれば、入力ベクトルに近いコンテンツベクトルの検索にかかる演算負荷を低減することが可能になる。
【発明を実施するための最良の形態】
【００１４】
以下に添付図面を参照しながら、本発明の好適な実施の形態について詳細に説明する。なお、本明細書及び図面において、実質的に同一の機能構成を有する構成要素については、同一の符号を付することにより重複説明を省略する。
【００１５】
＜実施形態＞
本発明の一実施形態について説明する。本実施形態は、コンテンツの推薦や検索に用いる演算処理を効率的に実行するための情報処理技術に関する。より具体的には、複数の高次元ベクトルの中から、入力ベクトルに最も距離が近いベクトルを効率的に求める情報処理方法に関する。以下の説明においては、ベクトル間の距離として、説明の都合上、次に示すようなコサイン距離を用いて説明することにする。但し、本実施形態は、これに限定されるものではない。
【００１６】
ベクトルｘとベクトルｙとの間のコサイン距離とは、ベクトルｘ、ｙの内積＜ｘ，ｙ＞を各ベクトルの大きさ｜ｘ｜、｜ｙ｜で割った値＜ｘ，ｙ＞／（｜ｘ｜｜ｙ｜）で定義される。
【００１７】
［推薦システム１００の機能構成］
上記の情報処理方法を実現するための具体的な装置としては、例えば、図１に示す推薦システム１００のような機能構成を有する情報処理装置が考えられる。そこで、以下では、図１に示す推薦システム１００の機能構成を例に挙げて本実施形態に係る情報処理方法について説明する。
【００１８】
まず、図１を参照しながら、本実施形態に係る推薦システム１００の機能構成について説明する。図１は、本実施形態に係る推薦システム１００の機能構成を示す説明図である。
【００１９】
図１に示すように、推薦システム１００は、主に、クラスタリングブロック１１０と、検索ブロック１３０とにより構成される。以下、クラスタリングブロック１１０、及び検索ブロック１３０のそれぞれが有する機能、及びその機能により実現される処理の流れについて説明する。
【００２０】
（クラスタリングブロック１１０）
クラスタリングブロック１１０は、記憶部１１２と、クラスタリング処理部１１６とにより構成される。クラスタリングブロック１１０は、コンテンツデータベースに記録されたコンテンツの情報を、内容が近いコンテンツベクトルをひとつのクラスタにまとめて保持する手段である。クラスタリングブロック１１０によるクラスタリング処理は、ユーザが所望するコンテンツの検索処理を実行するに先立ち、コンテンツデータベースに対する事前処理として実行される。
【００２１】
ここで、図３を参照しながら、クラスタリングブロック１１０によるクラスタリング処理の全体的な流れについて簡単に説明しておくことにする。図３は、クラスタリングブロック１１０によるクラスタリング処理の全体的な流れを示す説明図である。
【００２２】
図３に示すように、まず、クラスタリングブロック１１０により、コンテンツデータベースに格納されたコンテンツの情報がベクトル化される（Ｓ１３２）。但し、ここで言うベクトル化とは、コンテンツの属性情報を各成分とするコンテンツベクトルを生成する処理である。次いで、クラスタリングブロック１１０により、後述するバイナリマスクを用いてコンテンツベクトルが帰属する部分空間が定められる（Ｓ１３４）。
【００２３】
次いで、クラスタリングブロック１１０により、部分空間を定めるバイナリマスクと、そのバイナリマスクに帰属するコンテンツベクトルのインデックスとがコンテンツデータベースに格納される（Ｓ１３６）。なお、コンテンツデータベースがサーバに設けられているならば、各部分空間のバイナリマスクとコンテンツベクトルの帰属に関するインデックスとがサーバにアップロードされる。
【００２４】
上記のクラスタリングブロック１１０による事前処理の中で、本実施形態においては、コンテンツベクトルのクラスタリングに係る処理が重要である。以下、各処理の詳細について、記憶部１１２、及びクラスタリング処理部１１６の機能構成に関する説明に交えて述べることにする。
【００２５】
（記憶部１１２）
記憶部１１２には、コンテンツおよびコンテンツ情報が記録されたデータベース（コンテンツデータベース（DB））が格納されている。以下の説明において、コンテンツデータベースにはN個のコンテンツが記録されているものと仮定する。また、１つのコンテンツに関する情報はベクトル形式で１つのコンテンツベクトルとしてコンテンツデータベースに記録されているものと仮定する。そして、コンテンツベクトルはｘｎ（ｎ＝１，２，…Ｎ）と表現される。添え字ｎの順序は任意に付けられる。
【００２６】
以下の説明において、各コンテンツに付与されるコンテンツ情報の項目数（種類）がＤ個であるとする。また、１つの項目はコンテンツベクトルの１つの次元に対応するものとする。そして、ｎ番目（ｎ＝１，２，…）のコンテンツベクトルｘｎは、個々に１つのコンテンツ情報を示す次元成分ｘｎｄ（ｄ＝１，…，Ｄ）を用いて、下記の式（１）のようにＤ次元のベクトルで表現されるものとする。
【００２７】
【数１】
2010015441.tif 000003
【００２８】
一例として、ある放送番組Ｃのコンテンツベクトルｘｎについて考えてみる。コンテンツベクトルｘｎには、例えば、ある俳優Ａが放送番組Ｃに出演するか否かを表す項目（次元成分）ｘｎｄ（１≦ｄ≦Ｄ）が含まれる。もし、俳優Ａが放送番組Ｃに出演する場合、コンテンツベクトルｘｎの次元成分ｘｎｄには１が記録される。一方、俳優Ａが放送番組Ｃに出演しない場合、コンテンツベクトルｘｎの次元成分ｘｎｄには０が記録される。但し、ここで示す次元成分ｘｎｄの値は一例であり、実際には１に限定されず、その項目の度合いの最小値を０とする任意の正数を使用できる。
【００２９】
このように、コンテンツベクトルｘｎの各次元成分ｘｎｄ（ｄ＝１，…，Ｄ）はコンテンツに関する様々なコンテンツ情報を示している。上記の例において、コンテンツ情報は、放送番組Ｃに俳優Ａが出演するか否かを示す情報であった。同様にして、例えば、登録されている１０人の俳優がそれぞれ出演しているか否かを示すコンテンツベクトルを考えることができる。これらの登録された１０人の俳優のうち、ある映画Ｍには３人の俳優（俳優３、俳優５、俳優１０）のみが出演しているとしよう。この映画ＭのコンテンツベクトルｘＭは、下記の式（２）のように表現される。
【００３０】
【数２】
2010015441.tif 000004
【００３１】
このようなコンテンツ情報は、コンテンツの属性を示すメタデータ（属性情報）としてコンテンツに付与されるものである。コンテンツの属性情報としては、例えば、コンテンツのタイトルや出演者の情報等、コンテンツの配給時にコンテンツの管理者が保持している情報がある。その他にも、コンテンツの属性情報には、コンテンツのレビュー文等から抽出されたキーワードや市場調査等の結果から統計的に得られたターゲットの客層に関する情報等も含まれることがある。さらに、コンテンツの自動解析による結果が使用されることもある。
【００３２】
なお、本実施形態に係る情報処理方法は、これらの属性情報に加え、コンテンツベクトルの項目として設定可能な任意の属性情報に対して適用可能である。例えば、コンテンツのジャンルや出演者の特徴、ターゲットとする年齢層、キーワード、或いは、タイトルの属性等もコンテンツベクトルの項目として設定可能である。
【００３３】
上記の例においては、説明の都合上、コンテンツベクトルの次元数を１０とした。しかし、実際に利用されるコンテンツベクトルは、数千次元、数万次元、或いは、これを超えるような膨大な次元数となることが多い。これは、コンテンツベクトルが、データベースに登録されている膨大な数のコンテンツ情報を各次元成分として含むためである。
【００３４】
ところが、１つのコンテンツには、数千人、数万人もの出演者が存在するわけではない。１つのコンテンツに対応するキーワードやジャンルの数についても同様である。そのため、コンテンツ情報の真偽を１（真）、０（偽）の２値で表現した場合、１つのコンテンツベクトルの中で、値が１となる次元成分の数は非常に少なくなる。つまり、コンテンツベクトルの多くは、疎（ｓｐａｒｓｅ）なベクトルとなる。そこで、本実施形態は、このようなコンテンツベクトルの特性を生かして、コンテンツベクトルの検索処理にかかる演算量を低減させる方法を提案する。
【００３５】
このような方法を実現するために、記憶部１１２に記録されたコンテンツベクトルは、クラスタリング処理部１１６により読み出されて部分空間への帰属が定められる。そして、クラスタリング処理で用いられる部分空間を指定するバイナリマスクは、検索ブロック１３０によるコンテンツベクトルの検索処理に利用される。まず、本実施形態に係るクラスタリングについて説明する。なお、本実施形態において実行されるクラスタリングは、閾値を基準にある量を一定値に丸め込む通常の量子化手法とは異なる。本実施形態に係るクラスタリングは、疎なベクトルを部分空間に射影する操作を行うものであり、コンテンツベクトルの群を同じベクトル空間で値を丸める“量子化”に対応するものではない。後述するように、本発明のクラスタリング処理を量子化処理とのアナロジーを用いて説明することができる。
【００３６】
（ベクトルのクラスタリング手法について）
まず、本実施形態に係るクラスタリング手法について説明するに先立ち、一般的なクラスタリング手法について簡単に説明し、その問題点を指摘する。
【００３７】
ベクトルのクラスタリング手法としては、例えば、音声符号化に用いられるｋ平均法（ｋ−ｍｅａｎｓ  ａｌｇｏｒｉｔｈｍ）が知られている。音声符号化の場合、短時間フレームの音声波形がパラメータの組（ベクトル）で表現され、このベクトルがクラスタリングされることで音声圧縮が実現される。クラスタリングにより生成されるコードブックが量子化ベクトルであり、このクラスタリングにおいてｋ平均法が用いられる。
【００３８】
ｋ平均法は、ベクトル空間を複数のクラスタに分割して各クラスタにセントロイドを設定し、各セントロイドにベクトルを対応付けることにより、各ベクトルを量子化する手法である。セントロイドとしては、例えば、各クラスタに属するベクトル群の重心ベクトルが用いられる。
【００３９】
ｋ平均法は、各ベクトルを最も近い距離に位置するセントロイドに割り当てるステップ（ベクトルの対応付けステップ）と、各セントロイドに割り当てられたベクトル群から最適なセントロイドを算出するステップ（セントロイドの最適化ステップ）とを含む。そして、目的関数が収束するまで、これらのステップを繰り返し実行することで各ベクトルの最適なベクトル量子化が実現される。目的関数としては、例えば、歪みが用いられる。
【００４０】
音声符号化におけるベクトルのクラスタリングは、高々数十次元程度のベクトルに対して実行されるものである。そのため、ｋ平均法を用いても量子化ベクトルのデータサイズが問題となることが少ない。ところが、ｋ平均法は、コンテンツベクトルのように数十万次元もの次元数を有する疎な高次元ベクトルに対しては適していない。
【００４１】
ｋ平均法は、上記のようなアルゴリズムに基づいて実行されるため、高次元ベクトルに対しても原理的には用いることができる。しかしながら、高次元ベクトルが疎である場合、ｋ平均法によりベクトル量子化することで量子化ベクトルに含まれる多くの次元成分が０以外の値を持ち、量子化ベクトルが密なベクトルとなってしまう。そのため、量子化ベクトルを用いる演算の演算量が増加したり、量子化ベクトルを保持するために消費されるメモリ量が増加してしまう。
【００４２】
例えば、数十万次元のコンテンツベクトルを考える。上記の通り、コンテンツベクトルは、疎なベクトルである場合が多い。例えば、コンテンツベクトルの次元成分のうち、数十個の次元成分のみが１であり、その他の次元成分が０であるということが多い。ところが、こうしたコンテンツベクトルをｋ平均法でベクトル量子化すると、量子化ベクトルを構成する数十万次元の次元成分の全てに０以外の値（例えば、実数値）が格納され、各コンテンツベクトルは疎なベクトルであるのに、量子化ベクトルは疎なベクトルの特性を失ってしまう可能性がある。
【００４３】
こうした量子化ベクトルは、データベースに格納されてコンテンツベクトルの検索等に利用される。そのため、数十万次元もの次元数を持ち、全次元成分に実数値が格納された巨大な量子化ベクトルは、データベースのメモリ容量を圧迫してしまう。また、データベースサーバに対して量子化ベクトルのアップロードやダウンロードをする際にも、大きな通信負荷を与えてしまう。そのため、アップロードやダウンロードに時間が掛かる等の不便が生じてしまう。さらに、量子化ベクトルと、ユーザによりクエリーとして入力された入力ベクトルとの間のマッチングを行う際にも、そのマッチング処理にかかる演算量が増大してしまうのである。
【００４４】
こうした観点から、ｋ平均法を疎な高次元ベクトルのベクトル量子化に利用するのは好ましくない。そして、コンテンツベクトルのような疎な高次元ベクトルに対し、量子化ベクトルが密にならないようにベクトル量子化する手法の実現が求められているのである。そこで、本実施形態では、ｋ平均法とは異なり、セントロイドを用いずに疎な高次元ベクトルをクラスタリングする手法を提案する。この手法は、後述するクラスタリング処理部１１６により実現される。
【００４５】
（クラスタリング処理部１１６）
クラスタリング処理部１１６は、記憶部１１２に記録されたコンテンツベクトルを読み出してクラスタリングし、各コンテンツベクトルに対応する部分空間を生成する。このとき、クラスタリング処理部１１６は、部分空間を表現するために後述するバイナリマスクを利用する。ここで言うバイナリマスクとは、以下で詳細に説明するように、高次元ベクトルに作用させることで特定の次元成分のみを抽出することが可能な次元フィルタのことを意味する。
【００４６】
（バイナリマスクについて）
バイナリマスクとは、例えば、特定の次元で１、それ以外の次元で０の値を持つベクトルに相当するものである。そして、あるベクトルに対してバイナリマスクを施すとは、そのベクトルと、バイナリマスクに相当するベクトルとの間で各次元成分の積算（成分積又は要素積）を実行することと等価である。クラスタリング処理部１１６は、コンテンツデータベースに格納された全てのコンテンツベクトルが持つ情報が失われないように必要な数だけバイナリマスクを設定する。
【００４７】
以下、具体例を挙げて説明する。例えば、下記の式（３）に示すようなコンテンツベクトルｘｎがコンテンツデータベースに格納されているとしよう。但し、説明の都合上、次元数を１０に限定しているが、実際には数十万といった巨大な次元数を持つ高次元ベクトルに対して好適に用いられる。
【００４８】
【数３】
2010015441.tif 000005
【００４９】
上記の式（３）に示したコンテンツベクトルｘｎは、第１次元成分、第２次元成分、及び第５次元成分にしか値を持たない。従って、第１〜５次元成分のみしか値を参照しなかったとしても、コンテンツベクトルｘｎの持つ情報が欠損することはない。そこで、クラスタリング処理部１１６は、第１〜５次元成分のみを参照するためのバイナリマスクｍｑを設定する。但し、ｍｑはバイナリマスクを表すベクトル量である。第１〜第５次元成分のみを参照するためのバイナリマスクｍｑは、下記の式（４）のように表現される。
【００５０】
【数４】
2010015441.tif 000006
【００５１】
また、次元のインデックスをｄとすると、ｍｑｄ＝１（ｄ＝１〜５）、ｍｑｄ＝０（ｄ〜６〜１０）のようにも表現できる。このような表現を用いると、バイナリマスクｍｑが施されたコンテンツベクトルｘｎは、ｍｑ＊ｘｎ（但し、「＊」は成分積を表す。）で表現される。このとき、ベクトルｍｑ＊ｘｎの各成分（ｍｑｄ＊ｘｎｄ）は、コンテンツベクトルｘｎの各成分ｘｎｄと変わらない。複数のベクトルにこのバイナリマスクを施すとは、それらのベクトルをバイナリマスクで選択した次元のみで計算することにあたり、疎なベクトルとして扱われることになる。本実施形態に係るクラスタリング処理部１１６は、このようなバイナリマスクを用いてコンテンツベクトルのクラスタリングを行なう。
【００５２】
さて、既に述べた通り、あるコンテンツのコンテンツベクトルにおいては、各次元成分の値により、そのコンテンツが所定のメタデータに対応する属性を含むか否かが表現されている。特に、属性の有無に対応して各次元成分の値が２値で表現されることが多い。もちろん、キーワードの出現頻度等の属性に関しては、２値ではなく、１以外に自然数で表現されることもある。しかし、このような場合においても、本実施形態に係るクラスタリング手法が適用できる。
【００５３】
上記のバイナリマスクを用いてコンテンツベクトルのクラスタリングを行う場合、コンテンツベクトルの中で、どの次元成分に０以外の値を持つかという観点でコンテンツベクトルの特徴を捕らえることが、疎なベクトルとして計算を効率的に行うために重要になる。本実施形態に係るクラスタリング手法は、コンテンツベクトルが張るコンテンツ空間内で、コンテンツベクトルの次元成分が０以外の値を持つ次元を被覆可能な次元のバイナリマスクを算出するというものである。ここで言う「次元の」バイナリマスクとは、どの次元に値を持つかという情報を持つバイナリマスクである。
【００５４】
ここで、具体例として、図５に示すコンテンツベクトルＣＶ１、ＣＶ２、ＣＶ３、ＣＶ４を被覆することが可能な次元のバイナリマスクについて述べる。コンテンツベクトルＣＶ１、ＣＶ２、ＣＶ３、ＣＶ４は、それぞれ次元数７のベクトル量であり、ジャンルや出演者等の属性情報を表している。例えば、コンテンツベクトルＣＶ１は、第１次元、第２次元の次元成分が１である。つまり、コンテンツベクトルＣＶ１に対応するコンテンツの属性情報には、これらの次元成分に対応するジャンル１、ジャンル２が含まれている。
【００５５】
これらのコンテンツベクトルＣＶ１、ＣＶ２、ＣＶ３、ＣＶ４を被覆することが可能なバイナリマスクとしては、例えば、図６に示すバイナリマスクｍ１、ｍ２、ｍ３、ｍ４が考えられる。但し、図６は、バイナリマスクｍ１、ｍ２、ｍ３、ｍ４のイメージ図である。例えば、バイナリマスクｍ１は、次元の番号１、２を被覆するようなバイナリマスクを示している。同様に、バイナリマスクｍ２は次元の番号３を、バイナリマスクｍ３は次元の番号２、５、６を、バイナリマスクｍ４は次元の番号４、５を被覆するようなバイナリマスクを示している。
【００５６】
これらのバイナリマスクｍ１、ｍ２、ｍ３、ｍ４を組み合わせることで、各コンテンツベクトル（ＣＶ１、ＣＶ２、ＣＶ３、ＣＶ４）を被覆することが可能なように決定されたものである。例えば、コンテンツベクトルＣＶ１は、第１次元と第２次元にのみ有限の値を持つため、バイナリマスクｍ１により被覆される。コンテンツベクトルＣＶ２は、第１次元、第３次元、第７次元にのみ有限の値を持つため、第１次元を被覆可能なバイナリマスクｍ１、第３次元を被覆可能なバイナリマスクｍ２、第７次元を被覆可能なバイナリマスクｍ３の組み合わせにより被覆される。
【００５７】
このように、各コンテンツベクトルは、それを被覆する次元のバイナリマスクの集合に対応付けられることでクラスタリングされる。このような次元のバイナリマスクの組み合わせが本実施形態に係る部分空間群に相当する。上記の例からも分かるように、本実施形態に係る部分空間群の情報は、コンテンツベクトルが張るコンテンツ空間よりも低い次元のベクトル情報として保持することが可能である。そのため、上記のｋ平均法等における量子化ベクトルとは異なり、疎な高次元ベクトルをクラスタリングして得られる情報量が大幅に低減される。その結果、クラスタリングされた各コンテンツベクトルの情報を保持するのに要するデータ量が少なくて済むと共に、クラスタリングされた各コンテンツベクトルの情報を転送する際にも転送効率が向上するという効果が得られる。
【００５８】
なお、上記のような次元のバイナリマスクを施したコンテンツベクトルの各成分は次元のバイナリマスクを施す前のコンテンツベクトルの各成分と等しくなる。また、バイナリマスクを施した２つのコンテンツベクトルの間における演算結果はバイナリマスクの有無に関わらず等しくなる。ここで言う演算とは、例えば、内積計算やコサイン距離の計算、或いは、ユークリッド距離の計算等である。つまり、バイナリマスクを施すことで、バイナリマスクが指定する次元のみでの計算で完結し、密なベクトルや次元の一致を確認しながら行なう任意の疎なベクトル間の演算を行なわず、計算を効率的に行うことができる。
【００５９】
例えば、下記の式（５）及び式（６）に示す２つの疎なコンテンツベクトルｘ１、ｘ２を考える。ここでは、演算処理の一例として、コンテンツベクトルｘ１、ｘ２の内積計算を考える。
【００６０】
【数５】
2010015441.tif 000007
【００６１】
上記の通り、コンテンツベクトルｘ１は、第１次元、第２次元、第６次元にのみ値を持つ。つまり、このコンテンツベクトルｘ１に対応するコンテンツは、第１番目、第２番目、第６番目の属性を持っている。同様に、コンテンツベクトルｘ２は、第１次元、第６次元、第７次元にのみ値を持つ。つまり、このコンテンツベクトルｘ２に対応するコンテンツは、第１番目、第６番目、第７番目の属性を持っている。
【００６２】
これらのコンテンツベクトルに共通する次元のバイナリマスクｍ１２としては、例えば、第１次元、第２次元、第６次元、第７次元を被覆するバイナリマスクが考えられる。このバイナリマスクｍ１２は、次元のインデックスｄを用いて、下記の式（７）のように表現される。
【００６３】
【数６】
2010015441.tif 000008
【００６４】
ここで、２つのコンテンツベクトルｘ１、ｘ２の内積ｘ１・ｘ２は、下記の式（８）のように表現される。上記の通り、コンテンツベクトルｘ１、ｘ２が共通して０以外の値を持つ次元は、第１次元、第２次元、第６次元、第７次元のみである。そのため、各次元成分の積は、これらの０以外の値を持つ次元成分の積算値の和となる。そのため、上記の式（７）のように設定されたバイナリマスクｍ１２を施したコンテンツベクトルの内積は、下記の式（９）に示すように、バイナリマスクｍ１２を施していないコンテンツベクトルの内積と同じ結果になる。
【００６５】
【数７】
2010015441.tif 000009
【００６６】
このように、バイナリマスクを施しても、２つのコンテンツベクトルの内積値には変化がない。このような性質は、コサイン距離計算やユークリッド距離計算等においても同様である。
【００６７】
さて、複数のコンテンツベクトルに含まれる非ゼロ成分が全て被覆されるようなバイナリマスクは、これらのコンテンツベクトルに対応するコンテンツ群を全てカバーするような属性群の情報を有している。従って、このようなバイナリマスクを指定することは、そのバイナリマスクに対応するコンテンツ群を指定することと実質的に同じことになる。
【００６８】
こうしたことからも、次元のバイナリマスクがｋ平均法等におけるセントロイドと同等の役割を果たすものであることが分かる。
【００６９】
ここで、再びｋ平均法との対比を試みたい。本実施形態に係るバイナリマスクが保持すべき情報は、そのバイナリマスクがカバーすべきコンテンツベクトルの次元情報のみである。そのため、バイナリマスクが保持すべき情報には、次元のインデックスの集合のみが含まれる。一方、コンテンツベクトルの属性情報をｋ平均法でクラスタリングした場合、各クラスタのセントロイドは、全ての次元成分に実数値が格納されたベクトル量となる。
【００７０】
このことから、ｋ平均法のセントロイドと本実施形態に係る次元のバイナリマスクとを対比すると、明らかに次元のバイナリマスクが保持に必要となるデータ量が小さくなることが分かる。その結果、クラスタリングの結果として次元のバイナリマスクの情報を保持する場合は、セントロイドを密なベクトルとして保持する場合に比べて、その保持に要するメモリ量が大幅に低減される。また、その結果としてクラスタリングされたコンテンツベクトルの情報を転送する際にも、その転送効率が大きく改善される。
【００７１】
以上説明したように、次元のバイナリマスクは、コンテンツベクトルにより張られるコンテンツ空間の中から、特定の次元のみで形成される部分空間を選択する次元フィルタである。つまり、次元のバイナリマスクにより、高次元のコンテンツ空間よりも低い次元の部分空間が切り出されるのである。一方、ｋ平均法は、コンテンツ空間を排他的な空間に分割する処理に相当する。そのため、ｋ平均法による空間分割の場合、切り出される部分空間の次元数が元のコンテンツ空間と同じ次元数であり、高次元となる。
【００７２】
このように、本実施形態は、クラスタリング処理部１１６により、次元のバイナリマスクを用いてコンテンツベクトルをクラスタリングする。このとき、クラスタリング処理部１１６は、コンテンツデータベースに格納されたコンテンツベクトルの集合を可能な限り少ないビット（値が１である成分）で被覆することが可能なバイナリマスクを用いる。このようなバイナリマスクは、各コンテンツベクトルをクラスタリングして得られる部分空間群の中で、値１を持つ成分の数（以下、目的関数）が少なくなるように決定される。
【００７３】
クラスタリング処理部１１６は、例えば、図４に示すような繰り返し処理により、上記の目的関数を単調減少に導くことができる。そこで、図４を参照する。
【００７４】
まず、クラスタリング処理部１１６は、あるコンテンツベクトルに対応する部分空間の集合と、そのバイナリマスクが与えられると、その部分空間の集合へのコンテンツベクトルの割り当てを最適化する（Ｓ１５２）。次いで、部分空間の集合と、その部分空間の集合に対応付けられるコンテンツベクトルとの間の対応関係が与えられると、クラスタリング処理部１１６は、各部分空間のバイナリマスクを最適なものに更新する（Ｓ１５４）。次いで、クラスタリング処理部１１６は、目的関数が十分に収束したか否かを判定する（Ｓ１５６）。
【００７５】
ステップＳ１５６において、目的関数が収束していない場合、クラスタリング処理部１１６は、ステップＳ１５２の処理に進行して再びステップＳ１５２、Ｓ１５４の処理を繰り返す。一方、目的関数が収束した場合、クラスタリング処理部１１６は、各コンテンツベクトルが帰属する部分空間を決定する。
【００７６】
ここで、図４のステップＳ１５２に対応する最適化処理の詳細について述べる。ステップＳ１５２の最適化処理は、各コンテンツベクトルが張るコンテンツ空間を被覆することが可能な最小個数のバイナリマスクを決定することに相当する。このようなバイナリマスクの集合は各コンテンツベクトルに対応付けられる。例えば、次元のバイナリマスクとして、下記の式（１０）、式（１１）、式（１２）が与えられているものとする。
【００７７】
【数８】
2010015441.tif 000010
【００７８】
このとき、下記の式（１３）に示すコンテンツベクトルｘは、バイナリマスクｍ１、ｍ２の両方に属する。そのため、バイナリマスクｍ１、ｍ２は、いずれも、ｘが０以外の値を持つ次元成分を全て被覆することが可能なバイナリマスクである。このように候補が複数ある場合、バイナリマスクとしては、コンテンツベクトルｘの成分を被覆する可能性のある次元成分の数（バイナリマスクの次元数）が少ないものが選ばれる。この例では、バイナリマスクｍ２が選ばれる。つまり、コンテンツベクトルｘが帰属するクラスタには、量子化ベクトルとしてバイナリマスクｍ２が割り当てられる。
【００７９】
このように選ぶことで、対象とする次元を効率的に限定することができる。上記の通り、ベクトルｘと任意のベクトルｙとの内積演算を実行する場合、バイナリマスクで対象から外された次元は、たとえｙにおいて非ゼロ成分であったとしても、内積演算には寄与しないからである。
【００８０】
【数９】
2010015441.tif 000011
【００８１】
ここで、図８を参照しながら、上記の割り当て処理の流れについて説明する。図８に示すように、あるコンテンツベクトルｘｎが初期値として与えられる（Ｓ２０２）。次いで、クラスタリング処理部１１６により、ｋ番目の部分空間のバイナリマスクｍｋが取得される（Ｓ２０４）。ステップＳ２０４において、参照されるクラスタのインデックスｋ（初期値ｋ＝１）が設定され、コンテンツベクトルｘｎが属するクラスタのバイナリマスクｍの初期値が設定される。但し、バイナリマスクｍの初期値は、全ての次元成分が１のベクトルとして与えられる。
【００８２】
次いで、クラスタリング処理部１１６により、ベクトルｘｎの次元成分が、取得したバイナリマスクｍｋにより被覆されるか否かが判定される（Ｓ２０６）。ここで実行される判定処理は、ベクトルｘｎが当該バイナリマスクにより定められる部分空間に属するか否かを判定することと等価である。取得したバイナリマスクｍｋにより被覆される場合、クラスタリング処理部１１６は、ステップＳ２０８の処理に進行する。一方、取得したバイナリマスクｍｋにより被覆されない場合、クラスタリング処理部１１６は、再びステップＳ２０４の処理に戻り、一連の処理を繰り返す。
【００８３】
ステップＳ２０８において、クラスタリング処理部１１６は、求めたバイナリマスクｍｋの非ゼロ成分の数が、マスクされるコンテンツベクトルｘｎの非ゼロ成分の数よりも大きいか否かを判定する（Ｓ２０８）。バイナリマスクｍｋの非ゼロ成分の数がコンテンツベクトルｘｎの非ゼロ成分の数よりも大きい場合、クラスタリング処理部１１６は、ステップＳ２１０の処理に進行する。一方、バイナリマスクｍｋの非ゼロ成分の数が、マスクされるコンテンツベクトルｘｎの非ゼロ成分の数よりも小さい場合、クラスタリング処理部１１６は、再びステップＳ２０４の処理に戻り、一連の処理を繰り返す。
【００８４】
ステップＳ２１０において、クラスタリング処理部１１６は、ｘｎを被覆することが可能なバイナリマスクの集合と、そのバイナリマスクｍｋによって定められる部分空間をその部分空間のインデックスであるｋに変更する（Ｓ２１０）。次いで、クラスタリング処理部１１６は、全てのバイナリマスクと比較したか否か（ｋ＝Ｋ？）を判定する（Ｓ２１２）。全てのバイナリマスクと比較した場合、クラスタリング処理部１１６は、一連の処理を終了する。この終了した時点で、与えられたコンテンツベクトルｘｎを被覆する最適なバイナリマスクｍｋと、そのバイナリマスクに属するクラスタの番号ｋが決定されている。
【００８５】
一方、全てのバイナリマスクに対する比較処理が終了していない場合、クラスタリング処理部１１６は、ステップＳ２１４の処理に進行する。ステップＳ２１４において、クラスタリング処理部１１６は、バイナリマスクｍｋのインデックスｋを１だけ増加させる（Ｓ２１４）。次いで、クラスタリング処理部１１６は、再びステップＳ２０４の処理に進行して一連の処理を繰り返す。
【００８６】
以上、各クラスタに対するコンテンツベクトルの割り当て処理について説明した。このように、クラスタリング処理部１１６は、全ての部分空間（クラスタ）に対してコンテンツベクトルの部分空間への帰属の更新を実行する。そして、クラスタリング処理部１１６は、最も非ゼロ成分の数が少ないバイナリマスクを選択するのである。その結果、初期値として与えられたコンテンツベクトルを被覆する最適なバイナリマスクと、それに属するクラスタインデックスとが決定されるのである。
【００８７】
次に、図９を参照しながら、図４のステップＳ１５４に対応するバイナリマスクの最適化処理の流れについて説明する。図９に示すように、クラスタリング処理部１１６は、まず、ｋ番目の部分空間（クラスタ）に割り当てられたコンテンツベクトルのインデックスをひとつ取得する（Ｓ２３２）。次いで、クラスタリング処理部１１６は、割り当てられたコンテンツベクトルの中で、バイナリマスクの最適化処理において未使用のコンテンツベクトルを取得する（Ｓ２３４）。このとき、クラスタリング処理部１１６は、バイナリマスクｍの初期値を全ての次元成分が０のベクトルに設定する。
【００８８】
次いで、クラスタリング処理部１１６は、非ゼロ成分に対応するコンテンツベクトルの次元を表すインデックスを取得する（Ｓ２３６）。次いで、クラスタリング処理部１１６は、取得した次元のインデックスに対応するバイナリマスクの次元の成分の値を１に変更する（Ｓ２３８）。次いで、クラスタリング処理部１１６は、割り当てられた全てのコンテンツベクトルを使用したか否かを判断する（Ｓ２４０）。全てのコンテンツベクトルを使用した場合、クラスタリング処理部１１６は、一連の処理を終了する。この時点において、ｋ番目のクラスタに対応するバイナリマスクが得られている。
【００８９】
一方、ステップＳ２４０において全てのコンテンツベクトルを使用していないと判断した場合、クラスタリング処理部１１６は、ステップＳ２４２の処理に進行する。ステップＳ２４２において、クラスタリング処理部１１６は、クラスタ番号を表すインデックスｋを１増加させる（Ｓ２４２）。次いで、クラスタリング処理部１１６は、再びステップＳ２３４の処理に進行し、一連の処理を繰り返す。
【００９０】
以上説明したように、バイナリマスクの最適化処理は、各部分空間（クラスタ）に対応付けされている全てのコンテンツベクトルを被覆するバイナリマスクを、必要最小限の次元のみマスクするように更新することである。ここで、必要最小限の次元のみのマスクとは、成分の値が１である次元数が最小になるようにするという意味である。上記のような一連の処理により、各クラスタに帰属する全てのコンテンツベクトルを被覆するバイナリマスクが算出され、目的関数を単調非増加（減少又は変化なし）させることができる。
【００９１】
例えば、バイナリマスクｍが下記の式（１４）で与えられており、このバイナリマスクに属するコンテンツベクトルｘ１、ｘ２が下記の式（１５）及び式（１６）で与えられていたとする。この場合、バイナリマスクｍに代えて、これらのコンテンツベクトルｘ１、ｘ２を被覆するのに必要な最小限のバイナリマスクｍ’が、下記の式（１７）のように求められる。
【００９２】
【数１０】
2010015441.tif 000012
【００９３】
上記のバイナリマスクの最適化処理は、目的関数が十分に小さな値に収束するまで繰り返し実行される。この繰り返し処理の流れについて、図１０Ａ、及び図１０Ｂを参照しながら、より詳細に説明する。
【００９４】
図１０Ａに示すように、クラスタリング処理部１１６は、まず、指定したクラスタ数Ｋのバイナリマスクｍ１、…、ｍＫの初期値を与える（Ｓ２５２）。次いで、クラスタリング処理部１１６は、コンテンツデータベースに格納されたｎ番目のコンテンツベクトルｘｎを取得する（Ｓ２５４）。但し、ｎ＝１から開始される。次いで、クラスタリング処理部１１６は、コンテンツデータベースに格納された全てのコンテンツベクトルについて最適化処理が実行されたか否かを判断する（Ｓ２５６）。全てのコンテンツベクトルに最適化処理が実行された場合、クラスタリング処理部１１６は、ステップＳ２６０の処理に進行する。
【００９５】
一方、全てのコンテンツベクトルに最適化処理が実行されていない場合、クラスタリング処理部１１６は、ステップＳ２５８の処理に進行する。ステップＳ２５８において、クラスタリング処理部１１６は、コンテンツベクトルのインデックスｎを１だけ増加させ（Ｓ２５８）、再びステップＳ２５２の処理に戻る。
【００９６】
ステップＳ２６０において、クラスタリング処理部１１６は、クラスタリングにより算出されたｋ番目のクラスタ情報を指し示すポインタを取得する（Ｓ２６０）。但し、ｋ＝１から開始される。次いで、クラスタリング処理部１１６は、ｋ番目のクラスタに対応するバイナリマスクｍｋを更新する（Ｓ２６２）。次いで、クラスタリング処理部１１６は、全てのクラスタについて処理が実行されたか否かを判断する（Ｓ２６４）。全てのクラスタについて処理が実行された場合、クラスタリング処理部１１６は、ステップＳ２６８の処理（図１０Ｂ）に進行する（Ｓ２６４）。
【００９７】
一方、全てのクラスタについて処理が実行されていない場合、クラスタリング処理部１１６は、ステップＳ２６６の処理に進行する。ステップＳ２６６において、クラスタリング処理部１１６は、クラスタのインデックスｋを１だけ増加させ、再びステップＳ２６０の処理に戻る。
【００９８】
ステップＳ２６８において、クラスタリング処理部１１６は、全てのバイナリマスクの非ゼロ成分の数（目的関数）を算出する（Ｓ２６８）。次いで、クラスタリング処理部１１６は、目的関数の減少量が０か否かを判定する（Ｓ２７０）。但し、クラスタリング処理部１１６は、目的関数の減少量が所定量よりも十分に小さいか否かを判定して処理を分岐してもよい。
【００９９】
目的関数の減少量が０の場合、クラスタリング処理部１１６は、ステップＳ２７２の処理に進行する。一方、目的関数の減少量が０でない場合、クラスタリング処理部１１６は、再びステップＳ２５２の処理に戻り、割り当て、及び最適化に係る一連の処理を実行する。
【０１００】
ステップＳ２７２において、クラスタリング処理部１１６は、クラスタリングの処理を終了し、ステップＳ２７４の処理に進行する。そして、クラスタリング処理部１１６は、各クラスタのバイナリマスク、及び各部分空間（クラスタ）に帰属する各コンテンツベクトルのインデックス（ポインタ）をコンテンツデータベースに記録する（Ｓ２７４）。この帰属情報は、コンテンツベクトルの検索用に利用される。
【０１０１】
以上、クラスタリング処理部１１６によるコンテンツベクトルのクラスタリング手法について説明した。本実施形態に係るクラスタリング手法は、次元のバイナリマスクを用いてコンテンツベクトルが張るコンテンツ空間を部分空間に分割し、各コンテンツベクトルの非ゼロ成分を被覆するバイナリマスクを算出して部分空間と各コンテンツベクトルとを対応付けるというものである。
【０１０２】
その際、クラスタリング処理部１１６は、バイナリマスクの非ゼロ成分の数が少なくなるようにバイナリマスクの構成を最適化することで、クラスタとして保持すべき情報量を効率化することができる。また、後述するコンテンツベクトルの検索処理においても、各バイナリマスクの非ゼロ成分が少なく、演算対象とする次元が限定されているので、検索処理にかかる演算量が低減される。
【０１０３】
このようにしてクラスタリング処理部１１６により算出された次元のバイナリマスク、及び各コンテンツベクトルとバイナリマスクとの間の対応関係は、図１に示すように、記憶部１１２に格納されたコンテンツデータベースに記録される。そして、これらの情報は、検索ブロック１３０においてコンテンツベクトルの検索処理に利用される。以下、この検索処理に係る検索ブロック１３０の機能構成について説明する。なお、コンテンツ空間がＫ個のクラスタに分割されているものとして説明する。
【０１０４】
（検索ブロック１３０）
図１に示すように、検索ブロック１３０は、部分空間選択部１３２と、推薦ベクトル検出部１３４とにより構成される。また、部分空間選択部１３２、及び推薦ベクトル検出部１３４には、クエリーとなる入力ベクトルがユーザにより入力される。なお、入力ベクトルは、ユーザの入力情報をコンテンツベクトルのベクトル空間に関する属性値に対応付けることで生成される。さらに、推薦ベクトル検出部１３４からは、入力ベクトルに適合するコンテンツベクトルが推薦ベクトルとして出力される。
【０１０５】
まず、図２を参照しながら、検索ブロック１３０による検索処理の全体的な流れについて説明する。図２は、検索ブロック１３０による検索処理の全体的な流れを示す説明図である。
【０１０６】
図２に示すように、まず、ユーザの嗜好情報がベクトル形式で入力される（Ｓ１０２）。つまり、入力ベクトルが入力される。次いで、検索ブロック１３０により、入力ベクトルにコンテンツベクトルを保持しているであろう部分空間を、バイナリマスクとの演算により選択する（Ｓ１０４）。次いで、検索ブロック１３０により、部分空間に帰属するコンテンツベクトルの集合に限定して検索対象が設定される（Ｓ１０６）。次いで、検索ブロック１３０により、絞り込まれた検索対象に含まれるコンテンツの中から、入力ベクトルに近いコンテンツが選択される（Ｓ１０８）。
【０１０７】
このように、検索ブロック１３０は、入力ベクトルに適合するコンテンツベクトルを２段階に分けて検索する。つまり、検索ブロック１３０は、コンテンツデータベースに記録された全てのコンテンツベクトルと入力ベクトルとを直接比較して検索処理を実行するのではなく、検索処理を２段階に分けて実行する。この検索処理の一段目は、入力ベクトルに近いコンテンツベクトルを大まかに絞り込む処理である。二段目の処理は、絞り込まれた検索範囲から入力ベクトルに適合するコンテンツベクトルを検出する処理である。
【０１０８】
一段目の処理は、部分空間選択部１３２により実行される。また、二段目の処理は、推薦ベクトル検出部１３４により実行される。以下、各段における検索処理について、部分空間選択部１３２、及び推薦ベクトル検出部１３４の機能構成の説明と交えて詳述する。
【０１０９】
（部分空間選択部１３２）
部分空間選択部１３２は、記憶部１１２のコンテンツデータベースに記録された部分空間の集合の中から、入力ベクトルに適合する部分空間を検出する。つまり、部分空間選択部１３２は、入力ベクトルに適合する部分空間（クラスタ）に対応付けられたコンテンツベクトルに検索範囲を絞り込むのである。
【０１１０】
このとき、部分空間選択部１３２は、入力ベクトルと、コンテンツデータベースに格納された全てのバイナリマスクとの間のマッチングを行う。そして、部分空間選択部１３２は、入力ベクトルとの内積が大きいコンテンツベクトルを含んでいる部分空間を選択する。部分空間選択部１３２により選択された部分空間の情報は、推薦ベクトル検出部１３４に入力される。このとき、選択された部分空間に対応するコンテンツベクトルのインデックスが推薦ベクトル検出部１３４に入力されるように構成されていてもよい。
【０１１１】
（入力ベクトルとバイナリマスクとの間のマッチング処理について）
ここで、図１１Ａ、及び図１１Ｂを参照しながら、入力ベクトルと量子化ベクトルとの間のマッチング処理の具体的な流れについて説明する。この処理は、入力ベクトルに近い部分空間（クラスタ）を求める処理に相当する。この処理の中で、全てのクラスタについてバイナリマスクと入力ベクトルとが比較され、バイナリマスクｍと入力ベクトルｙとの間の距離が小さなバイナリマスクが算出される。
【０１１２】
例えば、バイナリマスクｍと入力ベクトルｙとの間の距離Ｆ（ｍ，ｙ）は、
Ｆ（ｍ，ｙ）＝｜ｍ｜＋｜ｙ｜−２×｜ｍ  Λ  ｙ｜
と表現される。但し、｜ｍ｜はバイナリマスクの次元数（非ゼロ成分の数）、｜ｙ｜は入力ベクトルｙの非ゼロ成分の数、｜ｍ  Λ  ｙ｜はｍとｙで共通の非ゼロ成分の数を表す。もし、ｍとｙが一致すればＦ（ｍ，ｙ）はゼロとなる。Ｆ（ｍ，ｙ）はベクトルｍとベクトルｙとの間で共通でない非ゼロ成分の数に対応している。
【０１１３】
図１１Ａに示すように、まず、部分空間選択部１３２は、入力された嗜好情報のベクトル（入力ベクトル）ｙを保持する（Ｓ２９２）。通常、入力ベクトルｙは疎なベクトルとなる。次いで、部分空間選択部１３２は、入力ベクトルｙが持つ非ゼロ成分のインデックスを取得する（Ｓ２９４）。次いで、部分空間選択部１３２は、入力ベクトルｙが持つ非ゼロ成分のインデックスを保持する（Ｓ２９６）。
【０１１４】
次いで、部分空間選択部１３２は、データベースに記録されているｋ番目のクラスタに対応するバイナリマスクを取得する（Ｓ２９８）。但し、ｋ＝１から開始される。次いで、部分空間選択部１３２は、取得したバイナリマスクにより入力ベクトルｙの非ゼロ成分で被覆されるものがあるかを判定する（Ｓ３００）。これはバイナリマスクｍと入力ベクトルｙが両者とも非負のベクトルであることから、内積の演算結果が０であるか否かで判定することもできる。取得したバイナリマスクｍにより入力ベクトルｙの非ゼロ成分が被覆されるのであれば、部分空間選択部１３２は、ステップＳ３０４（図１１Ｂ）の処理に進行する。
【０１１５】
一方、取得したバイナリマスクにより入力ｙの非ゼロ成分をひとつも被覆できない場合、部分空間選択部１３２は、ステップＳ３０２の処理に進行する。ステップＳ３０２において、部分空間選択部１３２は、クラスタのインデックスｋを１だけ増加させ（Ｓ３０２）、再びステップＳ２９８の処理に戻る。
【０１１６】
ステップＳ３０４（図１１Ｂ）において、部分空間選択部１３２は、取得したバイナリマスクとの距離尺度Ｆ（ｍ、ｙ）の値が現時点の候補となる部分空間のバイナリマスクとの距離尺度よりも小さいか否かを比較する（Ｓ３０４）。次いで、部分空間選択部１３２は、比較結果に基づき、部分空間（クラスタ）の候補を更新する（Ｓ３０６）。即ち、以前の候補よりも距離が小さければ、候補となる部分空間のインデックスをｋに変更し、そうでなければ変更を加える。同様にして、部分空間選択部１３２は、距離の小さい部分空間を上位Ｎ個求めることもできる。
【０１１７】
次いで、部分空間選択部１３２は、全ての部分空間（クラスタ）について調べたか否かを判断する（Ｓ３０８）。全ての部分空間（クラスタ）について調べた場合、部分空間選択部１３２は、ステップＳ３１０の処理に進行する。一方、全てのクラスタについて調べていない場合、部分空間選択部１３２は、ステップＳ３０２の処理に進行し、クラスタのインデックスｋを１だけ増加させ（Ｓ３０２）、再びステップＳ２９８の処理に戻る。
【０１１８】
ステップＳ３１０において、部分空間選択部１３２は、ステップＳ３０６における変更後の部分空間（クラスタ）を入力ベクトルｙに近い部分空間（クラスタ）のインデックスとして決定し（Ｓ３１０）、一連の処理を終了する。このようにして、部分空間選択部１３２は、入力ベクトルに近い部分空間（クラスタ）を決定できる。次いで、決定された部分空間（クラスタ）に帰属するコンテンツベクトルの中から、入力ベクトルｙに近いコンテンツベクトルが検出される。但し、この検出処理は、推薦ベクトル検出部１３４により実行される。
【０１１９】
（推薦ベクトル検出部１３４）
推薦ベクトル検出部１３４は、部分空間選択部１３２から入力された部分空間（クラスタ）の情報に基づき、当該部分空間に対応するコンテンツベクトルの中から、入力ベクトルとの間の距離が最も近いコンテンツベクトルを検出する。但し、推薦ベクトル検出部１３４は、複数のコンテンツベクトルを入力ベクトルとの間の距離が近い順に検出してもよい。この場合、複数のコンテンツをユーザに推薦することができるようになる。
【０１２０】
（コンテンツベクトルの検出処理について）
ここで、図１２を参照しながら、部分空間選択部１３２により検出されたクラスタに対応するコンテンツベクトルの中から、入力ベクトルに近いコンテンツベクトルを検出処理の流れについて説明する。
【０１２１】
図１２に示すように、まず、推薦ベクトル検出部１３４は、入力ベクトルｙと、入力ベクトルｙが属するクラスタのインデックスＫを取得する（Ｓ３３２）。次いで、推薦ベクトル検出部１３４は、コンテンツデータベースからクラスタＫに属するコンテンツベクトルを取得する（Ｓ３３４）。次いで、推薦ベクトル検出部１３４は、取得した各コンテンツベクトルと、入力ベクトルｙとの間の類似度を計算し、最も近いコンテンツベクトルを算出する（Ｓ３３６）。これらの一連の処理を経ることで、入力ベクトルｙに最も近いコンテンツベクトルが検出される。
【０１２２】
以上、入力ベクトルに近いクラスタに対応するコンテンツベクトルの集合から、入力ベクトルに最も近いコンテンツベクトルを検出する処理の流れについて説明した。このようにして入力ベクトルに近いコンテンツベクトルが検出された後、推薦ベクトル検出部１３４により、そのコンテンツベクトルに対応するコンテンツがユーザに推薦される。
【０１２３】
［機能構成のまとめ］
本実施形態に係る推薦システム１００は、入力ベクトルとの間の距離が近いコンテンツベクトルを求め、そのコンテンツベクトルに対応するコンテンツをユーザに推薦することを目的としている。また、コンテンツデータベースに記録された全てのコンテンツベクトルとの間で入力ベクトルのマッチング処理（コサイン距離の計算）を実行すると、その演算負荷が非常に大きくなってしまうため、本実施形態は、この演算負荷の低減を図るべく、効率的な計算手法を提案するものである。本実施形態に係る計算手法は、コンテンツベクトルのクラスタリング手法に関する。特に、この手法を用いると、コンテンツベクトルが疎な高次元ベクトルである場合に演算を大きく効率化することができる。
【０１２４】
本実施形態に係る推薦システム１００は、コンテンツベクトルが格納されたコンテンツデータベースに接続されており、コンテンツベクトルを取得することができる。そして、推薦システム１００は、ユーザにより入力された嗜好情報（入力ベクトル）に適合するコンテンツベクトルを検出する。推薦システム１００は、この検出処理を効率的に実行するため、次のような機能構成を有している。
【０１２５】
（データベースに施す事前処理機能）
上記の検出処理を実行する前に、推薦システム１００は、コンテンツデータベースに対して次のような事前処理を施す。（１）コンテンツデータベースに格納された各コンテンツベクトルをクラスタリングする処理。（２）バイナリマスクにより、決定されたコンテンツ空間の各部分空間（クラスタ）を特徴付ける処理。このような事前処理が実行された後で、推薦システム１００は、入力ベクトルに近いコンテンツベクトルを２段階の検索処理により決定する。
【０１２６】
（コンテンツベクトルの検索機能）
（第１段目）検索処理の１段目は、バイナリマスクを用いて、候補となるコンテンツベクトルを検出する処理である。まず、コンテンツデータベースに格納された全ての量子化ベクトルと入力ベクトルとが比較され、入力ベクトルに近い部分空間（クラスタ）が算出される。なお、ここで実行される比較処理は、限定された次元内に包含される疎なベクトルを用いているため、コンテンツベクトルとの間の比較処理に比べて演算負荷が少ない。このようにして算出された部分空間に包含されるコンテンツベクトルが検索範囲に決定される。つまり、第１段目の処理は、検索範囲の絞り込み処理に相当する。
【０１２７】
（第２段目）検索処理の第２段目は、第１段目で決定された量子化ベクトルに対応するコンテンツベクトルの中から、入力ベクトルに近いコンテンツベクトルを決定する処理である。このとき、検索対象となるコンテンツベクトルの数は、コンテンツデータベースに含まれるコンテンツベクトルの数に比べて大きく低減されている。そのため、第２段目の処理に要する演算量は、全てのコンテンツベクトルとの間の比較演算に比べて少なくて済む。
【０１２８】
（コンテンツベクトルのクラスタリング処理の詳細）
上記の検索処理は、コンテンツベクトルが密な場合にも、音声符号化等に用いられるクラスタリングアルゴリズムを適用して実行することができる。しかし、コンテンツベクトルが疎な場合、量子化ベクトルが疎になるようにクラスタリングすることで、より処理効率を高めることができる。こうした観点から、次元のバイナリマスクを用いてコンテンツベクトルが張る高次元のベクトル空間を各クラスタに対応する複数の部分空間に分割する。このとき、コンテンツベクトルを被覆可能なバイナリマスクが選択され、クラスタとコンテンツベクトルとが対応付けされる。
【０１２９】
また、各クラスタに対応するバイナリマスクは、非ゼロ成分の数が少なくなるように最適化される。さらに、各クラスタに対してコンテンツベクトルを割り当てる際にも、コンテンツベクトルに割り当てられるバイナリマスクの非ゼロ成分数が少なくなるように最適化される。これらの最適化処理を繰り返し実行することで、部分空間の情報を保持するのに必要なデータ量が低減される。また、このデータ量が少ないことで転送処理の際にも転送量が低減される。また、部分空間により演算を行なう次元が限定されるため、計算を効率的に行うことができる。
【０１３０】
［次元圧縮との対比説明］
以上説明した本実施形態に係るクラスタリング手法は、コンテンツベクトルの演算のみならず、一般的な高次元ベクトルのベクトル量子化にも好適に用いることができる。そこで、高次元ベクトルの比較処理に用いる次元圧縮方式との違いについて両者を対比して説明する。
【０１３１】
ここで言う次元圧縮方式とは、高次元のベクトルを事前に次元圧縮して低次元のベクトルに変換しておき、入力ベクトルに対しても同じ次元圧縮を施して低次元ベクトル同士を比較するというものである。この次元圧縮には、例えば、主成分分析（ＰＣＡ；Ｐｒｉｎｃｉｐｌｅ  Ｃｏｍｐｏｎｅｎｔ  Ａｎａｌｙｓｉｓ）、潜在意味解析（ＬＳＡ；Ｌａｔｅｓｔ  Ｓｅｍａｎｔｉｃ  Ａｎａｌｙｓｉｓ）、確率的潜在意味解析（ＰＬＳＡ；Ｐｒｏｂａｂｌｉｓｔｉｃ  Ｌａｔｅｎｔ  Ｓｅｍａｎｔｉｃ  Ａｎａｌｙｓｉｓ）等の技術が用いられる。これらの次元圧縮方式を用いることで、少ない演算量で比較処理を行うことができる。
【０１３２】
ところが、これらの次元圧縮方式では、高次元のベクトル空間を近似的に低次元のベクトル空間に圧縮しているため、圧縮した時点で一部の情報が欠落している。一方、本実施形態に係るクラスタリング手法は、近似計算を含まないものである。直感的に記載すると、本実施形態に係るクラスタリング手法が高次元のベクトル空間を複数の部分空間に分割してクラスタリングする手法であるのに対し、次元圧縮方式は高次元のベクトル空間そのものを小さくするという手法である。従って、本実施形態に係るクラスタリング手法は、次元圧縮方式では得られない高い精度の計算（正確な計算）を実現できるのである。
【０１３３】
［応用例１：分散システムへの応用］
ここで、本実施形態に係る推薦システム１００を複数のサーバにより構成される分散システムに応用する例を挙げておくことにする。例えば、図７に示すように、入力ベクトル（ＵＰ）に近いクラスタを検出する処理と、入力ベクトルに近いコンテンツベクトルを決定する処理とを異なるサーバで実行する分散システムが考えられる。
【０１３４】
図７の例では、サーバＡ２００が入力ベクトルとクラスタとのマッチング処理を実行する。入力ベクトルに対応するクラスタを検出すると、そのクラスタの情報を保持しているサーバ（サーバＢ２１０）にアクセスする。そして、サーバＢ２１０に対してクラスタの情報を通知してコンテンツベクトルの検出処理を実行させる。このとき、サーバＡ２００は、サーバＣ２２０、及びサーバＤ２３０に対してアクセスしない。
【０１３５】
サーバＢ２１０は、サーバＡ２００からクラスタの情報を取得すると、自身が保持するコンテンツベクトルの中から入力ベクトルに適合するコンテンツベクトルを検出する。例えば、サーバＡ２００からクラスタ１の情報を取得した場合、サーバＢ２１０は、クラスタ１に対応するコンテンツベクトルの中から入力ベクトルに適合するコンテンツベクトルを検出する。このようにして分散システムを構築することにより、各サーバの計算負荷が低減され、より大規模なコンテンツ検索システム又はコンテンツ推薦システムを実現することが可能になる。
【０１３６】
［応用例２：階層的なベクトル量子化］
本実施形態に係るクラスタリング手法においては、クラスタリングを多段階に行なう枠組みに拡張することができる。この拡張に係る基本的なコンセプトは、上位の処理階層で大まかなクラスタリングを実行し、下位の処理階層で細かいクラスタリングを実行するというものである。個々の階層におけるクラスタリング手法は、既に述べた本実施形態のクラスタリング手法と基本的に同じである。例えば、下位の処理階層においてコンテンツベクトルのクラスタが算出されたとすると、上位の処理階層では、そのクラスタが張るベクトル空間を部分空間に分割して更なるクラスタが算出される。ここでは上位／下位の２階層で論じたが、もちろん、３以上の階層に拡張することもできる。
【０１３７】
［期待される効果］
上記の通り、本実施形態に係る具体的な技術的効果としては、推薦システムにおける検索処理の効率化、部分空間の情報を保持するのに必要なデータ量の低減、及び部分空間の情報を転送する際の転送データ量の低減等がある。これに加えて、次のような効果が期待できる。
【０１３８】
（推薦／検索に関して）
コンテンツデータベースに記録されたコンテンツの中で、ユーザにより入力されたクエリー（入力ベクトル）に近いものを効率的に求めることができるため、ユーザの嗜好に合うコンテンツの検索や推薦を行うサービス全般において広く使用することができるという利点がある。
【０１３９】
例えば、テレビ番組の推薦に利用することができる。この場合、ユーザの視聴履歴からユーザの嗜好に適合するテレビ番組を推薦する際に、推薦すべきコンテンツの算出に使用できる。また、音楽の推薦にも利用できる。具体的には、楽曲検索や推薦に利用することができる。さらに、映画等の動画コンテンツの推薦にも利用できる。この場合、ユーザの入力したキーワードとユーザが過去に視聴した動画コンテンツの視聴履歴から、ユーザの嗜好に近いと判断されるコンテンツを提示することができる。
【０１４０】
さらに、電子機器に搭載されているヘルプ機能のような文書検索にも利用できる。この場合、ユーザの入力したキーワードに近い文書を求めることができる。具体的には、電子機器やソフトウェアの使用説明書等における索引に使用することができる。同様に、ＷＥＢページの解析にも利用することができる。
【０１４１】
ユーザの行動履歴を解析する嗜好抽出処理にも使用できる。本実施形態の技術を応用すれば、クラスタリングによりカテゴライズされた枠組みで履歴情報を扱うことができるようになるため、単純なコンテンツの履歴を用いて嗜好抽出するよりも、例えば、ユーザの行動パターンを抽出したり、ある分野の流行を発見したりするような処理にも応用できる。
【０１４２】
（分散システムに関して）
また、応用例１のように、処理機能を分散させることで、各サーバの処理負荷が低減され、より大規模なコンテンツ提供システムが実現できるようになる。具体的には、入力ベクトルに適合するクラスタを求めるサーバと、あるクラスタに対応付けられたコンテンツから入力ベクトルとの間の距離が近いコンテンツを求めるサーバ群を分けて運用することができる。このように構成することで、分散配置されたサーバ毎にメンテナンスができる上、コンテンツの細かなアップデートがし易くなるというメリットも得られる。
【０１４３】
［ハードウェア構成（情報処理装置）］
上記装置が有する各構成要素の機能は、例えば、図１３に示すハードウェア構成を有する情報処理装置により、上記の機能を実現するためのコンピュータプログラムを用いて実現することが可能である。図１３は、上記装置の各構成要素が有する機能を実現することが可能な情報処理装置のハードウェア構成を示す説明図である。この情報処理装置の形態は任意であり、例えば、パーソナルコンピュータ、携帯電話、ＰＨＳ（Ｐｅｒｓｏｎａｌ  Ｈａｎｄｙ−ｐｈｏｎｅ  Ｓｙｓｔｅｍ）、ＰＤＡ（Ｐｅｒｓｏｎａｌ  Ｄｉｇｉｔａｌ  Ａｓｓｉｓｔａｎｔ）等の携帯情報端末、ゲーム機、又は各種の情報家電等の形態がこれに含まれる。
【０１４４】
図１３に示すように、前記の情報処理装置は、主に、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）９０２と、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）９０４と、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）９０６と、ホストバス９０８と、ブリッジ９１０と、外部バス９１２と、インターフェース９１４と、入力部９１６と、出力部９１８と、記憶部９２０と、ドライブ９２２と、接続ポート９２４と、通信部９２６とにより構成される。
【０１４５】
ＣＰＵ９０２は、例えば、演算処理装置又は制御装置として機能し、ＲＯＭ９０４、ＲＡＭ９０６、記憶部９２０、又はリムーバブル記録媒体９２８に記録された各種プログラムに基づいて各構成要素の動作全般又はその一部を制御する。ＲＯＭ９０４は、例えば、ＣＰＵ９０２に読み込まれるプログラムや演算に用いるデータ等を格納する。ＲＡＭ９０６は、例えば、ＣＰＵ９０２に読み込まれるプログラムや、そのプログラムを実行する際に適宜変化する各種パラメータ等を一時的又は永続的に格納する。これらの構成要素は、例えば、高速なデータ伝送が可能なホストバス９０８によって相互に接続されている。また、ホストバス９０８は、例えば、ブリッジ９１０を介して比較的データ伝送速度が低速な外部バス９１２に接続されている。
【０１４６】
入力部９１６は、例えば、マウス、キーボード、タッチパネル、ボタン、スイッチ、及びレバー等の操作手段である。また、入力部９１６は、赤外線やその他の電波を利用して制御信号を送信することが可能なリモートコントロール手段（所謂、リモコン）であってもよい。なお、入力部９１６は、上記の操作手段を用いて入力された情報を入力信号としてＣＰＵ９０２に伝送するための入力制御回路等により構成されている。
【０１４７】
出力部９１８は、例えば、ＣＲＴ（Ｃａｔｈｏｄｅ  Ｒａｙ  Ｔｕｂｅ）、ＬＣＤ（Ｌｉｑｕｉｄ  Ｃｒｙｓｔａｌ  Ｄｉｓｐｌａｙ）、ＰＤＰ（Ｐｌａｓｍａ  ＤｉｓｐｌａｙＰａｎｅｌ）、又はＥＬＤ（Ｅｌｅｃｔｒｏ−Ｌｕｍｉｎｅｓｃｅｎｃｅ  Ｄｉｓｐｌａｙ）等のディスプレイ装置、スピーカ、ヘッドホン等のオーディオ出力装置、プリンタ、携帯電話、又はファクシミリ等、取得した情報を利用者に対して視覚的又は聴覚的に通知することが可能な装置である。
【０１４８】
記憶部９２０は、各種のデータを格納するための装置であり、例えば、ハードディスクドライブ（ＨＤＤ；Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）等の磁気記憶デバイス、半導体記憶デバイス、光記憶デバイス、又は光磁気記憶デバイス等により構成される。
【０１４９】
ドライブ９２２は、例えば、磁気ディスク、光ディスク、光磁気ディスク、又は半導体メモリ等のリムーバブル記録媒体９２８に記録された情報を読み出し、又はリムーバブル記録媒体９２８に情報を書き込む装置である。リムーバブル記録媒体９２８は、例えば、ＤＶＤメディア、Ｂｌｕ−ｒａｙメディア、ＨＤ  ＤＶＤメディア、コンパクトフラッシュ（登録商標）（ＣＦ；ＣｏｍｐａｃｔＦｌａｓｈ）、メモリースティック、又はＳＤメモリカード（Ｓｅｃｕｒｅ  Ｄｉｇｉｔａｌ  ｍｅｍｏｒｙ  ｃａｒｄ）等である。もちろん、リムーバブル記録媒体９２８は、例えば、非接触型ＩＣチップを搭載したＩＣカード（Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ  Ｃａｒｄ）、又は電子機器等であってもよい。
【０１５０】
接続ポート９２４は、例えば、ＵＳＢ（Ｕｎｉｖｅｒｓａｌ  Ｓｅｒｉａｌ  Ｂｕｓ）ポート、ＩＥＥＥ１３９４ポート、ＳＣＳＩ（Ｓｍａｌｌ  Ｃｏｍｐｕｔｅｒ  Ｓｙｓｔｅｍ  Ｉｎｔｅｒｆａｃｅ）、ＲＳ−２３２Ｃポート、又は光オーディオ端子等のような外部接続機器９３０を接続するためのポートである。外部接続機器９３０は、例えば、プリンタ、携帯音楽プレーヤ、デジタルカメラ、デジタルビデオカメラ、又はＩＣレコーダ等である。
【０１５１】
通信部９２６は、ネットワーク９３２に接続するための通信デバイスであり、例えば、有線又は無線ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、Ｂｌｕｅｔｏｏｔｈ（登録商標）、又はＷＵＳＢ（Ｗｉｒｅｌｅｓｓ  ＵＳＢ）用の通信カード、光通信用のルータ、ＡＤＳＬ（Ａｓｙｍｍｅｔｒｉｃ  Ｄｉｇｉｔａｌ  Ｓｕｂｓｃｒｉｂｅｒ  Ｌｉｎｅ）用のルータ、又は各種通信用のモデム等である。また、通信部９２６に接続されるネットワーク９３２は、有線又は無線により接続されたネットワークにより構成され、例えば、インターネット、家庭内ＬＡＮ、赤外線通信、可視光通信、放送、又は衛星通信等である。
【０１５２】
（機能構成との対応関係について）
上記の推薦システム１００の機能は、上記のハードウェア資源を用いて実現される。例えば、推薦システム１００のうち、クラスタリング処理部１１６、部分空間選択部１３２、推薦ベクトル検出部１３４の機能は、ＲＯＭ９０４、ＲＡＭ９０６、記憶部９２０、又はリムーバブル記録媒体９２８に記録されたコンピュータプログラムに基づいてＣＰＵ９０２により実現される。
【０１５３】
また、記憶部１１２の機能は、ＲＡＭ９０６、記憶部９２０、又はリムーバブル記録媒体９２８により実現されるか、若しくは、通信部９２６を介して接続されたネットワーク９３２上のデータベースサーバにより実現される。さらに、ユーザは、入力部９１６を用いて入力ベクトルの情報（嗜好情報）を推薦システム１００に入力することができる。そして、推薦システム１００により検出されたコンテンツの情報は、出力部９１８に直接出力されたり、通信部９２６を介して接続されたネットワーク９３２上のユーザ端末に出力されたりする。
【０１５４】
以上、添付図面を参照しながら本発明の好適な実施形態について説明したが、本発明は係る例に限定されないことは言うまでもない。当業者であれば、特許請求の範囲に記載された範疇内において、各種の変更例または修正例に想到し得ることは明らかであり、それらについても当然に本発明の技術的範囲に属するものと了解される。
【０１５５】
上記の実施形態においては、具体的に、ユーザにより入力された入力ベクトルに適合するコンテンツベクトルの検索手法について説明した。しかしながら、本実施形態に係る技術は、一般的な高次元ベクトルのクラスタリングや検索処理にも応用できる。
【０１５６】
例えば、クエリーとして入力されたベクトルをｙ、検索対象の高次元ベクトルをｘとして、下記の式（１８）で表現されるベクトルｘ’を効率的に求める問題に拡張できる。下記の式（１８）の中で、Ｆ（ｘ，ｙ）は、ベクトル空間に属する２つのベクトルに対して、両者の内積演算の結果を用いて定められる目的関数である。
【０１５７】
【数１１】
2010015441.tif 000013
【図面の簡単な説明】
【０１５８】
【図１】本発明の一実施形態に係る推薦システムの構成を示す説明図である。
【図２】同実施形態に係る入力ベクトルに対応するコンテンツの検索処理の流れを示す説明図である。
【図３】同実施形態に係るデータベースの事前処理の流れを示す説明図である。
【図４】同実施形態に係るコンテンツベクトルのクラスタリング処理の流れを示す説明図である。
【図５】コンテンツベクトルの一例を示す説明図である。
【図６】バイナリマスクのイメージを概念的に示す説明図である。
【図７】同実施形態に係る分散システムの構成例を示す説明図である。
【図８】同実施形態に係るクラスタリング処理の流れを示す説明図である。
【図９】同実施形態に係るクラスタリング処理の流れを示す説明図である。
【図１０Ａ】同実施形態に係るクラスタリング処理の流れを示す説明図である。
【図１０Ｂ】同実施形態に係るクラスタリング処理の流れを示す説明図である。
【図１１Ａ】同実施形態に係る最適な部分空間の選択処理の流れを示す説明図である。
【図１１Ｂ】同実施形態に係る最適な部分空間の選択処理の流れを示す説明図である。
【図１２】同実施形態に係る最適なコンテンツベクトルの検索処理の流れを示す説明図である。
【図１３】同実施形態に係るハードウェア構成の一例を示す説明図である。
【符号の説明】
【０１５９】
１００    推薦システム
１１０    クラスタリングブロック
１１２    記憶部
１１６    クラスタリング処理部
１３０    検索ブロック
１３２    部分空間選択部
１３４    推薦ベクトル検出部
【図１】
2010015441.tif 000014
【図２】
2010015441.tif 000015
【図３】
2010015441.tif 000016
【図４】
2010015441.tif 000017
【図５】
2010015441.tif 000018
【図６】
2010015441.tif 000019
【図７】
2010015441.tif 000020
【図８】
2010015441.tif 000021
【図９】
2010015441.tif 000022
【図１０Ａ】
2010015441.tif 000023
【図１０Ｂ】
2010015441.tif 000024
【図１１Ａ】
2010015441.tif 000025
【図１１Ｂ】
2010015441.tif 000026
【図１２】
2010015441.tif 000027
【図１３】
2010015441.tif 000028