(57)【要約】ユーザの視聴履歴又は購入履歴が利用できる前にテレビ番組推薦のようなユーザに関心があるアイテムを推薦する方法及び装置を開示する。第三者の視聴又は購入履歴は、代表的な視聴者によって選択されたアイテムの典型的なパターンを反映する習癖プロファイルを発生するように処理される。ユーザは、発生した習癖プロファイルから最も関連のある一つ以上の習癖を選択することができ、これによって、視聴者自身の関心に最も近接するアイテムを有するプロファイルを初期化する。クラスタ化ルーチンは、ｋ平均クラスタ化アルゴリズムを用いて、第三者の視聴又は購入履歴（データセット）をクラスタに分割し、１クラスタのポイント（例えば、テレビ番組）が、他のクラスタに比べて当該クラスタの平均に近づくようにする。ｋの値は、クラスタのコンパクト性の測定に従って増分される。
2005531243.tif 000002
【特許請求の範囲】
【請求項１】
複数のアイテムを同様なアイテムに分割する方法であって、前記複数のアイテムが、少なくとも一人の第三者による選択履歴に対応し、
前記選択履歴をｋ個のクラスタに分割し、ｋが少なくとも２の初期値を有するステップと、
前記ｋ個のクラスタの各々に対して少なくとも一つの平均アイテムを識別するステップと、
前記複数のアイテムの各々を、距離マトリックスに基づいて前記ｋ個のクラスタの一つに割り当てるステップと、
前記ｋ個のクラスタの少なくとも一つに対するクラスタのコンパクト性の測定を決定するステップと、
予め決定された基準が前記クラスタのコンパクト性の測定によって適合されていない場合にｋの値を増分し、前記ステップを繰り返すステップとを具えることを特徴とする方法。
【請求項２】
前記ｋの値を増分するステップを、前記ｋの更なる増分によって分類精度が更に向上しなくなるまで繰り返すことができることを特徴とする請求項１記載の方法。
【請求項３】
前記予め設定された基準が特定のクラスタによって適合された場合に前記特定のクラスタを許容するステップを更に具えることを特徴とする請求項１記載の方法。
【請求項４】
前記分割するステップが、ｋ平均クラスタ化ルーチンを用いるステップを更に具えることを特徴とする請求項１記載の方法。
【請求項５】
前記複数のアイテムを番組とすることを特徴とする請求項１記載の方法。
【請求項６】
前記複数のアイテムをコンテントとすることを特徴とする請求項１記載の方法。
【請求項７】
前記複数のアイテムをプロダクトとすることを特徴とする請求項１記載の方法。
【請求項８】
前記距離マトリックスが、記号的な特徴値のあり得る値の各々に対する全ての場合の分類の全体に亘る類似にも続いた二つのアイテムの対応する記号的な特徴値間の距離に基づくことを特徴とする請求項１記載の方法。
【請求項９】
前記記号的な特徴値間の距離を、値差マトリックス（ＶＤＭ）技術を用いて算出することを特徴とする請求項８記載の方法。
【請求項１０】
前記ｋ個のクラスタの各々に対して少なくとも一つの平均アイテムを識別するステップが、
前記複数のアイテムの各々に対する変数を算出するステップと、
前記変数を記号的な平均地として最小にする少なくとも一つのアイテムを選択するステップとを更に具えることを特徴とする請求項１記載の方法。
【請求項１１】
複数のアイテムを同様なアイテムに分割するシステムであって、前記複数のアイテムが、少なくとも一人の第三者による選択履歴に対応し、
コンピュータ読出し可能コードを格納するメモリと、
前記メモリに作動的に結合したプロセッサとを具え、前記プロセッサを、
前記選択履歴をｋ個のクラスタに分割し、ｋが少なくとも２の初期値を有し、
前記ｋ個のクラスタの各々に対して少なくとも一つの平均アイテムを識別し、
前記複数のアイテムの各々を、距離マトリックスに基づいて前記ｋ個のクラスタの一つに割り当て、
前記ｋ個のクラスタの少なくとも一つに対するクラスタのコンパクト性の測定を決定し、
予め決定された基準が前記クラスタのコンパクト性の測定によって適合されていない場合にｋの値を増分し、前記ステップを繰り返すように構成したことを特徴とするシステム。
【請求項１２】
前記プロセッサを、前記ｋの更なる増分によって分類精度が更に向上しなくなるまで前記ｋの値を増分するようにも構成したことを特徴とする請求項１１記載のシステム。
【請求項１３】
前記プロセッサを、前記予め設定された基準が特定のクラスタによって適合された場合に前記特定のクラスタを許容するようにも構成したことを特徴とする請求項１１記載のシステム。
【請求項１４】
前記プロセッサが、ｋ平均クラスタ化ルーチンを用いて前記分割を行うことを特徴とする請求項１１記載のシステム。
【請求項１５】
前記距離マトリックスが、記号的な特徴値のあり得る値の各々に対する全ての場合の分類の全体に亘る類似にも続いた二つのアイテムの対応する記号的な特徴値間の距離に基づくことを特徴とする請求項１１記載のシステム。
【請求項１６】
前記記号的な特徴値間の距離を、値差マトリックス（ＶＤＭ）技術を用いて算出することを特徴とする請求項１５記載のシステム。
【請求項１７】
前記プロセッサが、
前記複数のアイテムの各々に対する変数を算出し、
記号的な平均値として前記変数を最小にする少なくとも一つのアイテムを選択することによって、前記ｋ個のクラスタの各々に対する少なくとも一つの平均アイテムを識別することを特徴とする請求項１１記載のシステム。
【請求項１８】
前記平均が複数のアイテムを具え、前記選択履歴の所定のアイテムに対する距離マトリックスが、前記所定のアイテムと前記平均を具える各アイテムとの間の距離に基づくことを特徴とする請求項１１記載のシステム。
【請求項１９】
複数のアイテムを同様なアイテムに分割する製造物であって、前記複数のアイテムが、少なくとも一人の第三者による選択履歴に対応し、
組み込まれたコンピュータ読出し可能コード手段を有するコンピュータ読出し可能媒体を具え、前記コンピュータ読出し可能プログラムコード手段が、
前記選択履歴をｋ個のクラスタに分割するステップと、
前記ｋ個のクラスタの各々に対して少なくとも一つの平均アイテムを識別するステップと、
前記複数のアイテムの各々を、距離マトリックスに基づいて前記ｋ個のクラスタの一つに割り当てるステップと、
前記ｋ個のクラスタの少なくとも一つに対するクラスタのコンパクト性の測定を決定するステップと、
予め決定された基準が前記クラスタのコンパクト性の測定によって適合されていない場合にｋの値を増分するステップとを具えることを特徴とする製造物。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、本発明の譲受人に譲り受けられるとともに参照することによってここに組み込まれた２００１年１１月１３日出願の発明の名称”Method and Apparatus for Partitioning a Plurality of Items into Groups of Similar Items in a Recommender of Such Items”の米国特許出願番号１０／０１４，２１６号に関連する。
【０００２】
本発明は、テレビ番組のような関心のあるアイテムを推薦する方法及び装置に関し、更に詳しくは、ユーザの購入又は視聴履歴が利用できる前に関心のある番組又は他のアイテムを推薦する技術に関する。
【背景技術】
【０００３】
チャンネル上で利用できる番組コンテントの多様性に従ってテレビ視聴者に利用できるチャンネル数が増大すると、関心のあるテレビ番組を識別するためのテレビ視聴者の試みが著しく増大する。電子番組ガイド（ＥＰＧ）は、例えば、タイトル、時間、日付及びチャンネルによって利用できるテレビ番組を識別し、利用できるテレビ番組を個人的な好みに従って探索され又は分類できるようにすることによって、関心のある番組の識別を容易にする。
【０００４】
複数の推薦ツールが、関心のあるテレビ番組及び他のアイテムを推薦するために提案又は示唆されている。テレビ番組推薦ツールは、例えば、視聴者の好みをＥＰＧに適用して、特定の視聴者の関心がありうる推薦された番組のセットを取得する。一般に、テレビ番組推薦ツールは、暗示若しくは明示の(implicit or explicit)技術を用いて又は上記のものの一部の組合せを用いて視聴者の好みを取得する。暗示のテレビ番組推薦ツールは、目立たない方法で視聴者の視聴履歴から取得した情報に基づいてテレビ番組の推薦を行う。それに対して、明示のテレビ番組推薦ツールは、視聴プロファイルを取得するとともに推薦を行うために、タイトルや、ジャンルや、俳優や、チャンネルや、日付／時間のような番組の属性について視聴者に明示的に問い合わせる。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
現在使用できる推薦ツールが、関心のあるアイテムを識別する際にユーザの手助けをする間、そのツールは、複数の制約を被り、かかる制約は、克服される場合には、推薦ツールの便宜及びパフォーマンスが著しく向上することができる。例えば、理解力があるようにするために、明示の推薦ツールは、非常に頻繁に初期化を行い、粒度(granularity)の粗レベル(coarse level)で好みを指定する非常に詳細な抽出標本に応答するよう新たなユーザのそれぞれに要求する。暗示のテレビ番組推薦ツールが、視聴動作を観察することによって目立たなくプロフィールを取得する間、ツールは、正確になるために長時間を要する。さらに、そのような暗示のテレビ番組推薦ツールは、少なくとも最小量の視聴履歴に対して任意の推薦を開始することを要求する。したがって、そのような明示のテレビ番組推薦ツールは、推薦ツールが最初に取得されたときに任意の推薦を行うことができない。
【０００６】
したがって、十分な個人視聴履歴が利用できる前にテレビ番組のようなアイテムを目立たなく推薦することができる方法及び装置が必要となる。さらに、第三者の視聴習癖に基づいて所定のユーザに対する番組の推薦を行う方法及び装置が必要となる。
【課題を解決するための手段】
【０００７】
一般に、テレビ番組推薦のような関心のあるアイテムをユーザに推薦する方法及び装置が開示されている。本発明の一態様によれば、推薦は、ユーザが最初に推薦を取得したときのようにユーザの視聴履歴又は購入履歴が利用できる前に行われる。最初に、一人以上の第三者からの視聴履歴又は購入履歴は、関心のあるアイテムを特定のユーザに推薦するために用いられる。
【発明の効果】
【０００８】
第三者の視聴又は購入履歴は、代表的な視聴者によって選択されたアイテムの典型的なパターンを反映する習癖プロファイルを発生するように処理される。各習癖プロファイルは、幾分互いに類似したアイテムのクラスタ（データポイント）となる。ユーザは、ユーザ自身の関心に最も近いユーザのプロファイルを初期化するために関心のある一つ以上の習癖を選択する。
【０００９】
クラスタ化ルーチンは、第三者の視聴又は購入履歴（データセット）をクラスタに分割して、１クラスタのポイント（例えば、テレビ番組）が、他のクラスタよりもクラスタの平均に近くなるようにする。クラスタの記号的な平均を算出する平均算出ルーチンも開示されている。テレビ番組のような所定のデータポイントは、各クラスタの平均を用いて、各クラスタに対するデータポイント間の距離に基づいてクラスタに割り当てられる。
【００１０】
開示された距離算出ルーチンは、所定のテレビ番組と所定のクラスタの平均との間の距離に基づいて各クラスタに対するテレビ番組の近接を評価する。算出された距離マトリックスは、クラスタの範囲を決定するために標本データセットの種々の例の間の区別を行う。値差メトリック（ＶＤＭ:Value Difference Metric）技術又はその変形は、二つのテレビ番組間の特徴値間の距離を算出するのに用いられる。
【００１１】
本発明の一例は、テレビ番組に対する習癖の有意味性(meaningfulness)を測定するためにクラスタのコンパクト性を使用することを意図する。例えば、クラスタのコンパクト性は、クラスタの希薄性／緊密性(sparse/tight)の程度を示す。緊密なクラスタは、当該クラスタに示したテレビジョンが非常に互いに類似していることを意味する。希薄なクラスタは、クラスタが当該クラスタの平均から離間するとともに場合によっては非常に互いに相違することを示すテレビジョンからなることを意味する。
【００１２】
これを考慮すると、本発明の一態様は、習癖の発生中に用いられるクラスタの数を増分するための目安としてクラスタのコンパクト性を使用することを意図する。
【発明を実施するための最良の形態】
【００１３】
本発明の更に完全な理解を、本発明の他の形態及び利点とともに、以下の詳細な説明及び図面を参照して取得する。
図１は、本発明によるテレビ番組推薦システム１００を示す。図１に示すように、本実施の形態のテレビ番組推薦システム１００は、図２に関連して後に説明するように特定の視聴者に関心のある番組を識別するために番組データベース２００の番組の評価を行う。推薦された番組を、例えば、周知のオンスクリーン提供技術を用いて（図示しない）セットトップ端末／テレビジョンを用いて視聴者に提供することができる。本発明を、ここではテレビ番組の推薦の状況で説明したが、本発明を、視聴履歴や購入履歴のようなユーザの行為の評価に基づく自動的に発生した推薦に適用することができる。
【００１４】
本発明の形態によれば、テレビ番組推薦システム１００は、ユーザが最初にテレビ番組推薦システム１００を取得したときのようにユーザの視聴履歴１４０が利用できる前にテレビ番組推薦を発生することができる。図１に示すように、テレビ番組推薦システム１００は、先ず、関心のある番組を特定のユーザに推薦するために一人以上の第三者からの視聴履歴１３０を利用する。一般的に、第三者の視聴履歴１３０は、収入や、性別や、教育のようなデモグラフィーを有する一つ以上の標本母集団の視聴習癖に基づき、それは、更に大きな母集団の表示となる。
【００１５】
図１に示すように、第三者の観察履歴１３０は、与えられた母集団によって視聴され又は視聴されない番組のセットを具える。視聴された番組のセットは、与えられた母集団によって実際に視聴された番組を観察することによって取得される。視聴されなかった番組のセットは、例えば、任意に番組データベース２００の番組をサンプリングすることによって取得される。他の変形において、視聴されない番組のセットは、本発明の譲受人に譲り受けられるとともに参照することによってここに組み込まれた”An Active Sampling Technique for Selecting Negative Examples for Artificial Intelligence Application”の名称の２００１年３月２８日に出願された米国特許出願番号０９／８１９，２８６の教示に従って取得される。本発明の他の態様によれば、テレビ番組推薦システム１００は、代表的な視聴者によって視聴されたテレビ番組の典型的なパターンを反映する定型プロファイルを発生するために第三者視聴履歴１３０を処理する。後に更に説明するように、定型クラスタを、互いに類似したテレビ番組のクラスタ（データ点）とする。したがって、与えられたクラスタは、特定のパターンを示す第三者の視聴履歴１３０からのテレビ番組の特定のセグメントに対応する。
【００１６】
第三者の視聴履歴１３０は、ある特定のパターンを示す番組のクラスタを提供する本発明によって処理される。その後、ユーザは、最も関連のなる一つ以上の定型を選択し、これによって、ユーザの関心に最も近い番組を有するユーザのプロファイルを初期化することができる。その後、定型プロファイルは、記録パターン及び番組に付されたフィードバックに応じて、個別のユーザの特定の個人的な視聴行為に向かう調整及び進展を行う。一実施の形態のおいて、ユーザ自身の視聴履歴１４０からの番組に対して、第三者の視聴履歴１３０からの番組より多い番組スコアを決定するときに更に高い重み付けを行うことができる。
【００１７】
テレビ番組推薦システム１００を、中央処理ユニット（ＣＰＵ）のようなプロセッサ１１５及びＲＡＭ及び／又はＲＯＭのようなメモリ１２０を有するパーソナルコンピュータ又はワークステーションのような任意の演算装置として実施することができる。テレビ番組推薦システム１００を、例えば、（図示しない）セットトップ端末又はディスプレイの特定用途向け集積回路（ＡＳＩＣ）として実施することもできる。さらに、テレビ番組推薦システム１００を、カリフォルニア州のサニーベール(Sunnyvale)ノＴｉｖｏ，Ｉｎｃ．，から市販されているＴｉｖｏ（登録商標）システムのような任意の利用できるテレビ番組推薦システム、又は”Method and Apparatus for Recommending Television Programming Using Decision Trees”の名称の１９９９年１２月１７日に出願された米国特許出願番号０９／４６６，４０６、”Bayesian TV Show Recommender”の名称の２０００年２月４日に出願された米国特許出願番号０９／４９８，２７１及び”Three-Way Media Recommendation Method and System”の名称の２０００年７月２７日に出願された米国特許出願番号０９／６２７，１３９に記載されたテレビ番組推薦システム又はその任意の組合せとして実施することができ、その各々は、本発明の形態及び機能を実施するためにここの変形例として、参照することによってここに組み込まれる。
【００１８】
図１に示すとともに、図２〜８に関連して後に更に説明するように、テレビ番組推薦システム１００は、番組データベース２００と、定型プロファイルプロセス３００と、クラスタ化ルーチン４００と、平均算出ルーチン５００と、距離算出ルーチン６００と、クラスタパフォーマンスアセスメントルーチン８００とを有する。一般に、番組データベース２００を、周知の電子的な番組ガイドとして実施することができ、それは、所定の時間間隔で利用できる各番組の情報を記録する。定型プロファイルプロセス３００は、（ｉ）代表的な視聴者によって視聴されたテレビ番組の典型的なパターンを反映する定型プロファイルを発生するために第三者の視聴履歴１３０を処理し、（ii）最も関連のある一つ以上の定型を選択し、これによってユーザのプロファイルを初期化することをユーザに許可し、（iii）選択された定型に基づく推薦を発生する。
【００１９】
クラスタ化ルーチン４００が定型プロファイルプロセス３００によって呼び出され、一つのクラスタのポイント（テレビ番組）が、他のクラスタに比べて当該クラスタの平均（重心）に近くなるように、第三者の視聴履歴１３０（データセット）をクラスタに分割する。クラスタルーチン４００は、クラスタの記号的な平均(symbolic mean)を算出するために平均算出手段を呼び出す。距離算出ルーチン６００は、与えられたテレビ番組と与えられたクラスタの平均との間の距離に基づいて各クラスタに対するテレビ番組の近接を評価するために、クラスタ化ルーチン４００に呼び出される。最後に、クラスタ化ルーチン４００は、クラスタを形成するのを止める基準を満足するときを決定するために、クラスタ化パフォーマンスアセスメントルーチン８００を呼び出す。
【００２０】
図２は、図１の番組データベース（ＥＰＧ）からの標本テーブルである。既に説明したように、番組データベース２００は、一定の時間間隔で利用できる各プログラムの情報を記録する。図２に示すように、番組データベース２００は、与えられた番組にそれぞれ関連した記録２０５〜２２０のような複数の記録を有する。各番組に対して、番組データベース２００は、日付／時刻及びフィールド２４０〜２４５の番組に関連したチャンネルを示す。さらに、各番組のタイトル、ジャンル及び俳優が、フィールド２５０，２５５及び２７０でそれぞれ識別される。番組の開始から終了までの時間及び説明のような他の周知の形態（図示せず）を、番組データベース２００に含めることもできる。
【００２１】
図３は、本発明による形態を組み込む定型プロファイルプロセス３００の実現例を説明するフローチャートである。既に説明したように、定型プロファイルプロセス３００は、（ｉ）代表的な視聴者によって視聴されたテレビ番組の典型的なパターンを反映する定型プロファイルを発生するために第三者の視聴履歴１３０を処理し、（ii）最も関連のある一つ以上の定型を選択し、これによってユーザのプロファイルを初期化することをユーザに許可し、（iii）選択された定型に基づく推薦を発生する。第三者の視聴履歴１３０のプロセスを、例えば工場内でオフラインで実行することができ、テレビ番組推薦システム１００を、ユーザによる選択に対して発生した定型プロファイルをインストールしたユーザに提供することができる。
【００２２】
したがって、図３に示すように、定型プロファイルプロセス３００は、先ず、ステップ３１０中で第三者の視聴履歴１３０を収集する。その後、定型プロファイルプロセス３００は、図４に関連して後に説明するように、ステップ３２０中でクラスタ化ルーチン４００を実行して、定型プロファイルに対応する番組のクラスタを発生する。後に更に説明するように、クラスタ化ルーチン４００の一例は、視聴履歴データセット１３０に知恵して”ｋ-means”のような教師なし(unsupervised)データクラスタ化アルゴリズムを用いることができる。既に説明したように、クラスタ化ルーチン４００は、第三者の視聴履歴１３０（データセット）をクラスタに分割して、一つのクラスタのポイント（テレビ番組）が他のクラスタに比べて当該クラスタの平均（重心）に近接するようにする。
【００２３】
その後、定型プロファイルプロセス３００は、各定型プロファイルを特徴付けるステップ３３０中に一つ以上のラベルを各クラスタに割り当てる。一実施の形態において、クラスタの平均は、全クラスタに対する代表的なテレビ番組となり、平均的な番組の特徴を、クラスタにラベル付けするために使用することができる。例えば、テレビ番組推薦システム１００を、ジャンルが支配的であり、すなわち、各クラスタに対する形態を規定するように構成することができる。
【００２４】
ラベル付けされた定型プロファイルは、ステップ３４０中、ユーザの関心に最も近い一つ以上のプロファイルを選択するよう各ユーザに提供される。選択されたクラスタをそれぞれ構成する番組を、当該定型の「典型的な視聴履歴」と考えることができ、各クラスタに対する定型プロファイルを構成するのに使用することができる。したがって、視聴履歴は、選択した定型プロファイルから番組を構成するステップ３５０中に各ユーザに対して発生される。最後に、以前のステップで発生した視聴履歴は、番組推薦を取得するためにステップ３６０中に番組推薦システムに供給される。プログラム推薦システムを、当業者には明らかなように、ここでの変形として既に参照したような任意の通常の番組推薦システムとして実施することができる。番組制御はステップ３７０中に終了する。
【００２５】
図４は、本発明の特徴を組み込んだクラスタ化ルーチン４００の実現の一例を説明するフローチャートである。既に説明したように、ステップ３２０中に、クラスタ化ルーチン４００が定型プロファイルプロセス３００によって呼び出され、一つのクラスタのポイント（テレビ番組）が、他のクラスタに比べて当該クラスタの平均（重心）に近くなるように、第三者の視聴履歴１３０（データセット）をクラスタに分割する。一般に、クラスタ化ルーチンは、標本データセットの例のグループ分けを見つける教師なしタスクに集中する。本発明は、ｋ−ｍｅａｎクラスタ化アルゴリズムを用いてデータセットをｋクラスタに分割する。後に説明するように、クラスタ化ルーチン４００に対する二つの主要パラメータは（ｉ）図６に関連して後に説明するように最も近いクラスタを見つけるための距離と、（ii）形成すべきクラスタの個数ｋとである。
【００２６】
見本データ(example data)の更なるクラスタ化によって分類精度が更に向上しない安定したｋの値に到達する状況では、本実施の形態のクラスタ化ルーチン４００は、ｋのダイナミック値を採用する。さらに、クラスタサイズは、空クラスタが記録されるポイントまで増大する。したがって、クラスタ化は、自然レベル(natural level)のクラスタに到達したときに止まる。
【００２７】
図４に示すように、クラスタ化ルーチン４００は、先ず、ステップ４１０中にｋ個のクラスタを確立する。本実施の形態のクラスタ化ルーチン４００は、クラスタの最小値、例えば２を選択することによって開始する。この固定値に対して、クラスタ化ルーチン４００は、全視聴履歴データセット１３０を処理し、複数の繰返しに亘って、安定した（、すなわち、アルゴリズムを更に繰り返しても番組があるクラスタから他のクラスタに移動しない）と考えることができる二つのクラスタに到達する。現在のｋ個のクラスタは、ステップ４２０中に一つ以上の番組によって初期化される。
【００２８】
実現の一例において、クラスタは、第三者の視聴履歴１３０から選択したあるシード番組(seed program)によってステップ４２０中に初期化される。クラスタを初期化する番組を、任意に又は順次選択することができる。順次の実現において、クラスタを、視聴履歴１３０の最初の番組で開始する番組又は視聴履歴１３０の任意のポイントで開始する番組によって初期化される。更に別の変形例において、各番組を初期化する番組数を変更することもできる。最後に、クラスタを、第三者の視聴履歴１３０の番組から任意に選択した特徴値(feature value)からなる一つ以上の「仮定」番組によって初期化される。
【００２９】
その後、クラスタ化ルーチン４００は、各クラスタの現在の平均を算出するステップ４３０中に、図５に関連して後に説明する平均算出ルーチン５００を初期化する。その後、クラスタ化ルーチン４００は、第三者の視聴履歴１３０の各番組の距離を各クラスタに対して決定するステップ４４０中に、図６に関連して後に説明する距離算出ルーチン６００を実行する。ステップ４６０中、視聴履歴１３０の各番組が、最も近いクラスタに割り当てられる。
【００３０】
任意の番組があるクラスタから他のクラスタに移動したか否かを決定するテストが、ステップ４７０中に実行される。番組があるクラスタから他のクラスタに移動したことがステップ４７０中で決定されると、番組制御は、ステップ４３０に戻り、安定したセットのクラスタが識別されるまで既に説明したように継続する。しかしながら、番組があるクラスタから他のクラスタに移動しなかったことがステップ４７０中で決定されると、番組制御がステップ４８０に進む。
【００３１】
指定されたパフォーマンス基準を満足したか否か又は空クラスタが識別されたか否か（ひとまとめに「停止基準」）を決定する更なるテストが、ステップ４８０中に実行される。停止基準が満足されないことがステップ４８０中に決定されると、ステップ４８５中にｋの値が増分され、番組制御が、ステップ４２０に戻り、既にしたようにして継続する。しかしながら、停止基準が満足されたとステップ４８０中に決定される場合、番組制御が終了する。停止基準の評価を、図８に関連して後に更に説明する。
【００３２】
本実施の形態のクラスタ化ルーチン４００は、一つのクラスタのみに番組を配置し、したがって、クリスプクラスタ(crisp cluster)と称されるものを形成する。他の変形例はファジィクラスタ化を採用し、これによって、特定例（テレビ番組）が部分的に複数の番組に属することができる。ファジィクラスタ化法において、テレビ番組には、テレビ番組をクラスタ平均に近づける方法を表す重み付けが割り当てられる。重み付けは、テレビ番組のクラスタ平均からの距離の逆二乗に依存する。単一のテレビ番組に関連したクラスタ重み付けの和は、合計１００％となる必要がある。
【００３３】
クラスタの記号的な平均の算出
図５は、本発明の特徴を組み込む平均算出ルーチン５００の実現の一例を説明するフローチャートである。既に説明したように、平均算出ルーチン５００は、クラスタの記号的な平均を算出するためにクラスタ化ルーチン４００によって呼び出される。数値的なデータに対して、平均は、変数を最小にする値となる。記号データの概念を拡張すると、クラスタの平均は、クラスタ間(intra-cluster)変数（したがって、クラスタの半径又は範囲）を最小にするｘμの値を見つけることによって規定することができる。
【００３４】
【数１】
2005531243.tif 000003
ここで、Ｊを、（視聴された又は視聴されない）同一分類からのテレビ番組のクラスタとし、ｘiを、ショーｉに対する記号的な特徴値とし、ｘμを、Ｖar（Ｊ）を最小にするようなテレビ番組の一つからの特徴値とする。
したがって、図５に示すように、平均算出ルーチン５００は、先ず、ステップ５１０中に、所定のクラスタＪにおける現在の番組を識別する。考察中の現在の記号的な属性に対して、クラスタＪの変数が、あり得る記号的な値ｘμのそれぞれに対してステップ５２０中に式（１）を用いて算出される。変数を最小にする記号的な値ｘμが、ステップ５３０中に平均値として選択される。
【００３５】
考察すべき他の記号的な属性が存在するか否かを決定するテストが、ステップ５４０中に実行される。考察すべき他の記号的な属性が存在することがステップ５４０中に決定されると、番組制御は、ステップ５２０に戻り、既に説明した方法で継続する。しかしながら、考察すべき他の記号的な属性が存在しないことがステップ５４０中に決定された場合、番組制御はクラスタ化ルーチン４００に戻る。
【００３６】
演算的には、Ｊの記号的な特徴値の各々はｘμとして試みられ、変数を最小にする記号的な値は、クラスタＪで考察中の記号的な属性に対する平均となる。あり得る２タイプの平均算出、すなわち、ショーに基づく平均及び特徴に基づく平均が存在する。
【００３７】
ここで説明する平均算出ルーチン５００の一例は、特徴に基づくものであり、この場合、結果的に得られるクラスタ平均は、クラスタＪの例（番組）から抽出した特徴値によって構成される。その理由は、記号的な属性をあり得る値の一つとする必要があるからである。しかしながら、クラスタ平均を「仮定的な」テレビ番組とできることに注目するのが重要である。このハイポテリカルな番組の特徴値は、例の一つから抽出されたチャンネル値（例えば、ＥＢＣ）及び例の他のものから抽出されたタイトル値（例えば、実際にはＥＢＣで放送されていないＢＢＣワールドニュース）を有することができる。したがって、最小の変数を示す任意の特徴値は、その特徴の平均を表すように選択される。全ての特徴（すなわち、記号的な属性）が考察されたことがステップ５４０中に決定されるまで、平均算出ルーチン５００が全ての特徴位置に対して繰り返される。このようにして結果的に得られるハイポテティカルな番組は、クラスタの平均を表すために使用される。
【００３８】
番組に基づく記号的な平均
他の変形例において、式（１）における変数に対して、ｘiを、テレビ番組ｉそれ自体とすることができ、同様に、ｘμを、クラスタＪの番組のセットに亘って変数を最小にするクラスタＪの一つ以上の番組とする。この場合、番組間であるが個別の特徴値間でない距離は、最小にすべき関連の距離となる。さらに、この場合に結果的に得られる平均は、仮定的な番組ではなく、セットＪから正確に取り出された番組である。クラスタＪの全ての番組に亘って変数を最小にする、このようにしてクラスタＪで見つけられる任意の番組は、クラスタの平均を表すために用いられる。
【００３９】
複数の番組を用いた記号的な平均
既に説明した平均算出ルーチンの一例は、（特徴に基づいて又は番組に基づいて実現される）あり得る特徴の各々に対する単一の特徴値を用いてクラスタの平均を特徴付ける。し
かしながら、平均算出中の各特長に対して一つの特徴値のみに依存することによって、しばしば不適切なクラスタ化となることを見つけた。その理由は、平均がもはやクラスタのクラスタ中心を表さないからである。換言すれば、クラスタを１番組のみによって表すのが望ましくなく、複数の番組が平均を表すのが望ましく、すなわち、クラスタを表すために複数の平均を用いることができる。したがって、他の変形例において、クラスタを、複数の平均又はあり得る特徴に対する複数の特徴値によって表すことができる。したがって、変数を最小にする（特徴に基づく記号的な平均に対する）Ｎ個の特徴又は（番組に基づく記号的な平均に対する）Ｎ個の番組が、ステップ５３０中に選択され、この場合、Ｎを、クラスタの平均を表すのに用いられる番組数とする。
【００４０】
番組とクラスタとの間の距離算出
既に説明したように、距離算出ルーチン６００が、所定のテレビ番組と所定のクラスタとの間に基づいて書くクラスタに対するテレビ番組の近接を評価するためにクラスタ化ルーチン４００によって呼び出される。算出した距離は、クラスタの程度を決定するために設定された標本データの種々の例間の区別を明示する。ユーザプロファイルをクラスタ化することができるようにするために、視聴履歴の任意の二つのテレビ番組間の距離を算出する必要がある。一般に、互いに近接するテレビ番組が１クラスタ内にある傾向にある。複数の比較的直接的な技術が、ユークリッド距離や、マンハッタン距離や、マハロノビス(Mahalanobis)距離のような数値ベクトル間の距離を算出するために存在する。
【００４１】
しかしながら、現存する距離算出技術をテレビ番組のベクトルの場合に用いることができない。その理由は、テレビ番組が主に複数の記号的な特徴値を有するからである。例えば、２００１年３月２２日午後８時にＥＢＣで放送された”Friend”のエピソード及び２００１年３月２５日午後８時にＦＥＸで放送された”The Simons”のエピソードのような二つのテレビ番組を、以下の特徴ベクトルを用いて表すことができる。
タイトル：Friend              タイトル：The Simons
チャンネル：ＥＢＣ            チャンネル：ＦＥＸ
放送日：２００１年３月２２日  放送日：２００１年３月２５日
放送時間：２０００            放送時間２０００
【００４２】
明らかに、特徴値ＥＢＣとＦＥＸとの間の距離を算出するために数値的な距離を用いることができない。数値距離マトリックス（ＶＤＭ:value difference metric）は、記号的な特徴の数値範囲の特徴の値間の距離を測定する現存の技術である。ＶＤＭ技術は、各特長のあり得る値のそれぞれに対する全ての分類の全体に亘る類似を考慮する。この方法を用いることによって、特徴の全ての値間の距離を規定する行列は、トレーニングセットの例に基づいて統計的に取得される。記号的な特徴値間の距離を算出するＶＤＭ技術の更に詳細な説明は、例えば、参照することによってここに組み込まれたStanfill及びWaltzの”Toward Memory-Based Reasoning,” Communications of the ACM, 29:12, 1213-1228 (1986)を参照されたい。
【００４３】
本発明は、関心のある二つのテレビ番組間又は他のアイテム間の特徴値の間の距離を算出するＶＤＭ技術又はその変形を用いる。本来のＶＤＭの提案は、二つの特徴値間の距離算出に重み付け項を使用し、これによって、距離マトリックスを非対称にする。変形したＶＤＭ（ＭＶＤＭ）は重み付け項を省略し、これによって距離マトリックスを対称にする。記号的な特徴値間の距離を算出するＭＶＤＭ技術の更に詳細な説明は、例えば、参照することによってここに組み込まれたCostとSalzbergによる”A Weighted Nearest Neighbor Algorithm for Learing With Symbolic Features”,Machine Learning, Vol. 10, 57-58, Bolton, MA, Kluwer Publishers (1993)を参照されたい。
【００４４】
ＭＶＤＭによれば、特定の特徴に対する値Ｖ１とＶ２との間の距離δは、
【００４５】
【数２】
2005531243.tif 000004
によって与えられる。
【００４６】
本発明の番組推薦環境において、ＭＶＤＭ式（３）は、特に分類”watched”及び”not-watched”を取り扱うよう変換される。
【００４７】
【数３】
2005531243.tif 000005
【００４８】
式（４）において、Ｖ１及びＶ２を、考察中の特徴の二つのあり得る阿智亜とする。上記例を継続すると、特徴「チャネル」に対して、第１の値Ｖ１はＥＢＣに等しくなり、第２の値Ｖ２はＦＥＸに等しくなる。値間の距離は、例が分類される全ての分類に亘る総和となる。本発明の番組推薦の例に対する関連の分類は、”Watched”及び”Not-Watched”である。Ｃ１ｉは、分類ｉ（ｉは、分類Watchedを伴う１に等しい。）に分類されたＶ１（ＥＢＣ）の数であり、Ｃ１（Ｃ１＿total）は、データセットに生じたＶ１の総数である。値ｒは、通常１に設定される定数である。
【００４９】
式（４）によって規定された行列は、全ての分類に対して同一の相対度数で生じる場合には同様なものとして値を識別する。項Ｃ１ｉ／Ｃ１は、式の特徴が値Ｖ１を有する場合に中心残余(central residue)がｉとして分類される可能性を表す。したがって、二つの値は、全てのあり得る分類に対して同様な可能性を与える場合には互いに類似する。式（４）は、全ての分類全体に亘るこれら可能性の差の総和を見つけることによって二つの値間の全体に亘る類似を算出する。二つのテレビ番組間の距離は、二つのテレビ番組ベクトルの対応する特徴値間の距離の和となる。
【００５０】
図７Ａは、特徴「チャンネル」に関連した特徴値の距離テーブルの部分を示す。図７Ａは、各分類の各チャンネル特徴値の発生数をプログラムする。図７Ａに示す値は、第三者の視聴履歴１３０の例から取り出した。
【００５１】
図７Ｂは、ＭＶＤＭ式（４）を用いて図７Ａに示した計数例から算出した各特徴値対間の距離を示す。直感的には、ＥＢＣ及びＡＢＳが互いに「近接する」必要がある。その理由は、これらが、視聴された分類で最も生じるとともに、非視聴分類で生じない（ＡＢＳは、小さい非視聴成分を有する。）からである。図７Ｂは、ＥＢＣとＡＢＳとの間の小さい（零でない）距離でこの直感を確証する。それに対して、ＡＳＰＮは、非視聴分類で最も生じ、したがって、このデータセットに対してＥＢＣとＡＢＳの両方から「離間する」必要がある。図７Ｂは、ＥＢＣとＡＰＳＮとの間の距離を、２．０のあり得る最大距離から１．８９５にプログラムする。同様に、ＡＢＳとＡＳＰＮとの間の距離は、１．８２８の値の大きなものとなる。
【００５２】
したがって、図６に示すように、距離算出ルーチン６００は、先ず、ステップ６１０中に第三者の視聴履歴１３０の番組を識別する。現在考察中の番組に対して、距離算出ルーチン６００は、（平均算出ルーチン５００によって決定された）各クラスタ平均の対応する特徴に対する記号的な特徴値のそれぞれの距離をステップ６２０中に算出するために式（４）を用いる。
【００５３】
現在の番組とクラスタ平均との間の距離は、対応する特徴値間の距離を一体にすることによってステップ６３０中に算出される。考察すべき他の番組が第三者の視聴履歴１３０に存在するか否かを決定するテストが、ステップ６４０中に実行される。考察すべき他の番組が第三者の視聴履歴１３０に存在することがステップ６４０中に決定される場合、次の番組がステップ６５０中に識別され、番組制御は、ステップ６２０に進み、既に説明したように継続する。
【００５４】
しかしながら、考察すべき他の番組が第三者の視聴履歴１３０に存在しないことがステップ６４０中に決定される場合、番組制御がクラスタ化ルーチン４００に戻る。
【００５５】
「複数番組から取得した記号的な平均」の表題のサブセクションで既に説明したように、クラスタの平均を、特徴に基づく実現であるか番組に基づく実現であるかの）あり得る特徴の各々に対する複数の特徴値を用いることによって特徴付けることができる。複数の平均からの結果は、投票を通じた合意の決定に到達するために距離算出ルーチン６００の変動によってプールされる。例えば、距離は、番組の所定の特徴値と種々の平均に対する対応する特徴値の各々との間でステップ６２０中に算出される。最小距離結果は、プールされ、例えば、合意の決定に到達するための多数決又は専門家の混成(mixture of expert)を用いることによって投票に用いられる。そのような技術の更に詳細な説明は、例えば、参照によってここに組み込んだj. Kittlerなどによる”Combining Classifiers,” in Proc. of the 13th Int’l Conf. On Pattern Recognition, Vol. II, 897-901, Vienna, Austria, (1996)を参照されたい。
【００５６】
基準停止
既に説明したように、クラスタ化ルーチン４００は、クラスタを形成するための基準の停止が満足されたときを決定するために、図８に示すクラスタ化パフォーマンスアセスメントルーチン８００を呼び出す。クラスタ化ルーチン４００の一例は、例示データを更にクラスタ化しても分類精度が更に向上しないときに安定したｋに到達しないことを条件にして、ｋのダイナミック値を用いる。さらに、クラスタサイズを、空クラスタが記録されたポイントまで増大することができる。したがって、クラスタ化は、クラスタのナチュラルレベルに到達したときに停止する。
【００５７】
好適な実施の形態において、ｋの値を増分するために、現在の結果的に生じるクラスタのコンパクト性を測定する決定を行う。この決定をステップ４８０で実行することができる。クラスタのコンパクト性を、当該クラスタが当該クラスタの平均に（距離的に）近接する番組数を決定することによって測定することができる。そのような複数の決定を、例えば、予め設定された基準に適合した場合にクラスタを許容するように行うことができる。許容されたクラスタを、（当該クラスタにおける更なる追加及び／又は削除なしの）更なる変形から除くことができる。予め設定された基準を、例えば、当該クラスタの番組の５０％がクラスタ半径の２５％以内にある場合に任意のクラスタによって適合させることができる。この予め設定された基準に適合しない場合、他のクラスタ（すなわち、ｋの値の増分）を追加することができる。しかしながら、例えば、当該クラスタの番組の７５％がクラスタ半径の２５％以内にある場合に他の基準を用いることができることを理解すべきである。
【００５８】
クラスタ化パフォーマンスアセスメントルーチン８００の一例は、クラスタ化ルーチン４００の分類精度をテストするために第三者の視聴履歴１３０（テストデータセット）からの番組のサブセットを用いる。テストセットの各々に対して、クラスタ化パフォーマンスアセスメントルーチン８００は、（クラスタ平均に最も近い）最も近接するクラスタを決定し、クラスタに対する分類ラベルと考察中の番組とを比較する。整合した分類ラベルの割合は、クラスタ化ルーチン４００の精度に変換する。
【００５９】
したがって、図８に示すように、クラスタ化パフォーマンスアセスメントルーチン８００は、先ず、テストデータセットとして使用するためにステップ８１０中に第三者の視聴履歴１３０から番組のサブセットを収集する。その後、分類ラベルは、視聴され及び視聴されないクラスタの番組の割合の基づいてステップ８２０中に各クラスタに割り当てられる。例えば、クラスタ中の番組のほとんどが視聴される場合、クラスタは、「視聴」のラベルに割り当てることができる。
【００６０】
テストセットの各番組に最も近接するクラスタがステップ８３０中に識別され、割り当てられたクラスタの分類ラベルは、番組が実際に視聴されたか否かについて比較される。クラスタの平均を表すために複数の番組が用いられる実現において、（各番組に対する）平均距離又は投票形態を用いることができる。整合した分類ラベルの割合は、番組制御がクラスタ化ルーチン４００に戻る前にステップ８４０中に決定される。クラスタ化ルーチン４００は、分類精度が予め設定されたしきい値に到達したときに終了する。
【００６１】
ここに図示し及び説明した実施の形態及び変形例は、本発明の原理を単に示したに過ぎず、種々の変更を、本発明の範囲及び精神を逸脱することなく当業者によって実現することができる。
【図面の簡単な説明】
【００６２】
【図１】本発明によるテレビ番組推薦システムの線形ブロック図である。
【図２】図１の番組データベースの例からの標本テーブルである。
【図３】本発明の原理を用いる図１の習癖プロファイル処理を説明するフローチャートである。
【図４】本発明の原理を用いる図１のクラスタ化ルーチンを説明するフローチャートである。
【図５】本発明の原理を用いる図１の平均算出ルーチンを説明するフローチャートである。
【図６】本発明の原理を用いる図１の距離算出ルーチンを説明するフローチャートである。
【図７Ａ】各分類に対する各チャンネル特徴値の発生数を表すチャンネル特徴値発生テーブルの一例からの標本テーブルである。
【図７Ｂ】図７Ａに示す計数例から算出した各特徴値対間の距離を表す特徴値対距離テーブルの例からの標本テーブルである。
【図８】本発明の原理を用いる図１のクラスタ化パフォーマンスアセスメントルーチンを説明するフローチャートである。
【図１】
2005531243.tif 000006
【図２】
2005531243.tif 000007
【図３】
2005531243.tif 000008
【図４】
2005531243.tif 000009
【図５】
2005531243.tif 000010
【図６】
2005531243.tif 000011
2005531243.tif 000012
【図８】
2005531243.tif 000013
【国際調査報告】
2005531243.tif 000014
2005531243.tif 000015
2005531243.tif 000016