(57)【要約】  ユーザの視聴履歴又は購入履歴が利用可能になる前に、テレビ番組リコメンデーションのように、興味のあるアイテムをユーザに推薦する方法及び装置が開示される。第三者の視聴又は購入履歴は、代表的視聴者により選択されたアイテムの典型的なパターンを反映する典型プロファイルを生成するために処理される。ユーザは、前記生成された典型プロファイルから最も関連のある（複数の）典型を選択することができ、これにより彼又は彼女自身の興味に最も近いアイテムによって彼又は彼女のプロファイルを初期化する。クラスタリング・ルーチンは、１つのクラスタ内の点（例えばテレビ番組）がその他のクラスタより当該クラスタの平均に近くなるように、ｋ平均クラスタリング・アルゴリズムを使用して前記第三者の視聴又は購入履歴（データセット）をクラスタに分割する。平均計算ルーチンは、クラスタの記号的平均を計算する。フィーチャに基づく平均計算に対して、２つのアイテム間の距離計算は、フィーチャ（記号的属性）レベルで実行され、結果として生じるクラスタ平均は、前記クラスタ内の標本（番組）から引き出されたフィーチャ値から成る。前記結果として生じるクラスタ平均は、“仮定”テレビ番組であってもよく、この仮定番組の個別のフィーチャ値は、前記標本の何れか１つから引き出される。
2005509968.tif 000002
【特許請求の範囲】
【請求項１】
複数のアイテムJを特徴付ける方法であり、前記アイテムのそれぞれが、少なくとも１つの記号的属性を持ち、前記記号的属性のそれぞれが、少なくとも１つの取り得る記号的値を持つ方法であって、
前記記号的属性のそれぞれに対する前記取り得る記号的値xμのそれぞれに対して前記複数のアイテムJの分散を計算するステップと、前記記号的属性のそれぞれに対して、前記分散を最小化する少なくとも１つの記号的値xμを平均記号的値として選択することにより少なくとも１つの平均アイテムによって前記複数のアイテムJを特徴付けるステップと、
を有する方法。
【請求項２】
前記記号的属性のそれぞれに対する前記平均記号的値が、前記複数のアイテムの前記平均アイテムを有する、請求項１に記載の方法。
【請求項３】
前記記号的属性のそれぞれに対する前記平均記号的値が、１つ以上の仮定アイテムを有する、請求項１に記載の方法。
【請求項４】
前記複数のアイテムの前記少なくとも１つの平均アイテムの少なくとも１つの記号的値を使用して、前記複数のアイテムにラベルを割り当てるステップを更に有する、請求項１に記載の方法。
【請求項５】
前記複数のアイテムが、類似アイテムを含むクラスタである、請求項１に記載の方法。
【請求項６】
前記アイテムが、番組及び／又はコンテンツ及び／又は製品である、請求項１に記載の方法。
【請求項７】
前記分散を計算するステップが、下記のように実行され、
Var(J)=Σi∈J(xi-xμ)2
ここで、Jは、同じクラスのアイテムのクラスタであり、xiは、アイテムiに対する記号的フィーチャ値であり、xμは、前記Var(J)を最小化するようなJ内の前記アイテムの１つの属性値である、請求項１に記載の方法。
【請求項８】
複数のアイテムJを特徴付けるシステムであり、前記アイテムのそれぞれが、少なくとも１つの記号的属性を持ち、前記記号的属性のそれぞれが、少なくとも１つの取り得る記号的値を持つシステムであって、
コンピュータ読取可能コードを記憶するメモリと、
前記メモリに動作的に結合されるプロセッサであって、
前記記号的属性のそれぞれに対する前記取り得る記号的値xμのそれぞれに対して、前記複数のアイテムJの分散を計算し、
前記記号的属性のそれぞれに対して、前記分散を最小化する少なくとも１つの記号的値xμを平均記号的値として選択することにより、少なくとも１つの平均アイテムによって前記複数のアイテムを特徴付けるように
構成された当該プロセッサと、
を有するシステム。
【請求項９】
前記記号的属性のそれぞれに対する前記平均記号的値が、前記複数のアイテムの前記平均アイテムを有する、請求項８に記載のシステム。
【請求項１０】
前記記号的属性のそれぞれに対する前記平均記号的値が、１つ以上の仮定アイテムを有する、請求項８に記載のシステム。
【請求項１１】
前記プロセッサが、更に、前記複数のアイテムの前記少なくとも１つの平均アイテムの少なくとも１つの記号的値を使用して、前記複数のアイテムにラベルを割り当てるように構成される、請求項８に記載のシステム。
【請求項１２】
前記複数のアイテムが、類似アイテムを含むクラスタである、請求項８に記載のシステム。
【請求項１３】
前記プロセッサが、前記分散を下記のように計算し、
Var(J)=Σi∈J(xi-xμ)2
ここで、Jは、同じクラスのアイテムのクラスタであり、xiは、アイテムiに対する記号的フィーチャ値であり、xμは、前記Var(J)を最小化するようなJ内の前記アイテムの１つの属性値である、請求項８に記載のシステム。
【請求項１４】
コンピュータプログラムであって、前記コンピュータプログラムを実行する場合に、プログラム可能な装置が、請求項８乃至１３の何れか一項に記載のシステムとして機能することを可能にするコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、テレビ番組のような興味のあるアイテムを推薦する方法及び装置に関し、特に、ユーザの購入又は視聴履歴が利用可能になる前に興味のある番組及び他のアイテムを推薦する技術に関する。
【背景技術】
【０００２】
テレビ視聴者に対して利用可能なチャネル数が増加したので、このようなチャネル上の利用可能な番組コンテンツの多様化と共に、テレビ視聴者が興味のあるテレビ番組を識別することは次第に難しくなってきている。電子番組ガイド（ＥＰＧ）は、例えば、タイトル、時間、日付及びチャネルにより利用可能なテレビ番組を識別し、前記利用可能なテレビ番組が、個人化された好みにより検索又は分類されることを可能にすることにより、興味のある番組の識別を容易化する。
【０００３】
多くのリコメンデーションツールが、興味のあるテレビ番組及び他のアイテムを推薦するために提示又は提案されてきた。テレビ番組リコメンデーションツールは、例えば、視聴者の好みをＥＰＧに対して利用し、特定の視聴者の興味のあるかもしれない推薦された番組のセットを得る。一般に、テレビ番組リコメンデーションツールは、黙示的若しくは明示的な技法を使用して、又は前述のものの組み合わせを使用して前記視聴者の好みを得る。黙示的なテレビ番組リコメンデーションツールは、目障りでない仕方で、前記視聴者の視聴履歴から引き出される情報に基づいてテレビ番組リコメンデーションを生成する。明示的なテレビ番組リコメンデーションツールは、これに対し、タイトル、ジャンル、俳優、チャネル及び日付／時間のような番組属性に対する好みについて視聴者に明示的に質問をし、視聴者プロファイルを得て、リコメンデーションを生成する。
【０００４】
現在利用可能なリコメンデーションツールは、ユーザが興味のあるアイテムを識別するのを援助するが、前記ユーザは、もし克服すれば、このようなリコメンデーションツールの利便性及び性能を大幅に向上させることができる多数の制限を受けている。例えば、包括的であるために、明示的なリコメンデーションツールは、粗い精度レベルにおいて好みを指定する非常に詳細な調査にそれぞれの新しいユーザが応答することを要求するので、初期化するのに非常に冗漫である。黙示的なテレビ番組リコメンデーションツールは、視聴習慣を観測することにより目障りにならないようにプロファイルを引き出すが、これらは、正確になるまでに長い時間を要する。加えて、このような黙示的なテレビ番組リコメンデーションツールは、如何なるリコメンデーションを作り始めるにも少なくとも最小量の視聴履歴を必要とする。従って、このような黙示的なテレビ番組リコメンデーションツールは、当該リコメンデーションツールが初めに得られた場合には如何なるリコメンデーションも作ることができない。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
従って、十分な個人化された視聴履歴が利用可能になる前に、目障りでないように、テレビ番組のようなアイテムを推薦することができる方法及び装置に対するニーズがある。加えて、第三者の視聴習慣に基づいて所定のユーザに対する番組リコメンデーションを生成する方法及び装置に対するニーズがある。
【課題を解決するための手段】
【０００６】
一般に、テレビ番組リコメンデーションのような、ユーザの興味のあるアイテムを推薦する方法及び装置が開示される。本発明の１つの態様によると、ユーザが初めてリコメンダを得る場合のような、前記ユーザの視聴履歴又は購入履歴が利用可能になる前にリコメンデーションが生成される。最初に、１人以上の第三者の視聴履歴又は購入履歴が、特定のユーザの興味のあるアイテムを推薦するために採用される。
【０００７】
前記第三者の視聴履歴又は購入履歴は、代表的視聴者により選択されたアイテムの典型的なパターンを反映する典型プロファイルを生成するために処理される。各典型プロファイルは、何らかのやり方で互いに類似したアイテム（データ点）のクラスタである。ユーザは、興味のある（複数の）典型を選択し、彼又は彼女自身の興味に最も近いアイテムによって彼又は彼女のプロファイルを初期化する。
【０００８】
クラスタリング・ルーチンは、１つのクラスタ内の点（例えばテレビ番組）がその他のクラスタより当該クラスタの平均に近くなるように、前記第三者の視聴又は購入履歴（データセット）をクラスタに分割する。テレビ番組のような所定のデータ点は、各クラスタの平均を使用して前記データ点と各クラスタとの間の距離に基づいてクラスタに割り当てられる。
【０００９】
平均計算ルーチンは、クラスタの記号的平均を計算するためにも開示される。フィーチャに基づく平均計算のために、２つのアイテム間の距離計算は、フィーチャ（記号的属性）レベルで実行され、結果として生じるクラスタ平均は、前記クラスタ内の標本（番組）から引き出されたフィーチャ値から成る。前記結果として生じるクラスタ平均は、従って、“仮定”テレビ番組であることができ、この仮定番組の個別のフィーチャ値は、前記標本の何れか１つから引き出される。従って、最小分散を示す何れのフィーチャ値でも、当該フィーチャの平均を表すように選択される。
【００１０】
本発明のより完全な理解と本発明の更に他のフィーチャ及び利点とは、以下の詳細な記述及び図面を参照して得られるだろう。
【発明を実施するための最良の形態】
【００１１】
図１は、本発明によるテレビ番組リコメンダ１００を図示する。図１に示されるように、模範的なテレビ番組リコメンダ１００は、図２と併せて下で記述される番組データベース２００内の番組を評価し、特定の視聴者の興味のある番組を識別する。推薦された番組のセットは、例えば、よく知られたオンスクリーン提示技法を使用するセットトップ端末／テレビ（図示されない）を使用して、前記視聴者に提示されることができる。本発明は、テレビ番組リコメンデーションとの関連でここに説明されるが、本発明は、視聴履歴又は購入履歴のようなユーザ習慣の評価に基づく如何なる自動生成リコメンデーションにも応用されることができる。
【００１２】
本発明の１つのフィーチャによると、テレビ番組リコメンダ１００は、ユーザが初めてテレビ番組リコメンダ１００を得る場合のように、前記ユーザの視聴履歴１４０が利用可能になる前にテレビ番組リコメンデーションを生成することができる。図１に示されるように、テレビ番組リコメンダ１００は、最初に１人以上の第三者の視聴履歴１３０を採用し、特定のユーザの興味のある番組を推薦する。一般に、第三者の視聴履歴１３０は、より大きな母集団を表す、年齢、収入、性別及び教養のような統計データを有する１つ以上のサンプル集団の視聴習慣に基づく。
【００１３】
図１に示されるように、第三者の視聴履歴１３０は、所定の母集団により視聴された及び視聴されなかった番組のセットから成る。前記視聴された番組のセットは、前記所定の母集団により実際に視聴された番組を観測することにより得られる。前記視聴されなかった番組のセットは、例えば、番組データベース２００内の番組をランダムにサンプリングすることにより得られる。更に他の変形形態において、前記視聴されなかった番組のセットは、本発明の譲受人に譲渡され、参照によりここに組み込まれる米国特許出願シリアル番号09/819,286、２００１年３月２８日出願、題“An Adaptive Sampling Technique for Selecting Negative Examples for Artificial Intelligence Applications”の教えに従って得られる。
【００１４】
本発明の他のフィーチャによると、テレビ番組リコメンダ１００は、第三者の視聴履歴１３０を処理し、代表的視聴者により視聴されたテレビ番組の典型的なパターンを反映する典型プロファイルを生成する。下で更に論じられるように、典型プロファイルは、何らかのやり方で互いに類似したテレビ番組（データ点）のクラスタである。従って、所定のクラスタは、特定のパターンを示す第三者の視聴履歴１３０からのテレビ番組の特定のセグメントに対応する。
【００１５】
第三者の視聴履歴１３０は、本発明により処理され、ある特定のパターンを示す番組のクラスタを提供する。この後、ユーザは、最も関連のある典型を選択することができ、これにより彼又は彼女自身の興味に最も近い番組によって彼又は彼女のプロファイルを初期化することができる。前記典型プロファイルは、この場合、それぞれ個別のユーザの記録パターン及び番組に与えられたフィードバックに依存して、前記それぞれ個別のユーザの特定の個人的な視聴習慣に対して適応及び進化する。一実施例において、前記ユーザ自身の視聴履歴１４０からの番組は、番組スコアを決定する場合に、第三者の視聴履歴１３０からの番組より高い重みを与えられることができる。
【００１６】
テレビ番組リコメンダ１００は、中央処理ユニット（ＣＰＵ）のようなプロセッサ１１５と、ＲＡＭ及び／又はＲＯＭのようなメモリ１２０とを含むパーソナルコンピュータ又はワークステーションのような如何なる計算装置としてでも実施され得る。テレビ番組リコメンダ１００は、例えば、セットトップ端末又はディスプレイ（図示されていない）において、特定用途向け集積回路（ＡＳＩＣ）として実施されてもよい。加えて、テレビ番組リコメンダ１００は、カリフォルニア、サニーヴェールのTivo, Inc.から市販されているTivo（登録商標）システム、又はそれぞれが参照によりここに組み込まれ、本発明のフィーチャ及び機能を実行するためにここで修正される米国特許出願シリアル番号09/466,406、１９９９年１２月１７日出願、題“Method and Apparatus for Recommending Television Programming Using Decision Trees”と、米国特許出願シリアル番号09/498,271、２０００年２月４日出願、題“Bayesian TV Show Recommender”と、米国特許出願シリアル番号09/627,139、２０００年６月２７日出願、題“Three-Way Media Recommendation Method and System”とに記述されるテレビ番組リコメンダ、又はこれらの組み合わせのような如何なる利用可能なテレビ番組リコメンダとしてでも実施され得る。
【００１７】
図１に示され、図２乃至８と併せて下で更に論じられるように、テレビ番組リコメンダ１００は、番組データベース２００と、典型プロファイル処理部３００と、クラスタリング・ルーチン４００と、平均計算ルーチン５００と、距離計算ルーチン６００と、クラスタ性能評価ルーチン８００とを含む。一般に、番組データベース２００は、よく知られた電子番組ガイドとして実施されてもよく、所定の時間間隔において利用可能である各番組の情報を記録する。典型プロファイル処理部３００は、（i）第三者の視聴履歴１３０を処理し、代表的視聴者により視聴されたテレビ番組の典型的なパターンを反映する典型プロファイルを生成し、（ii）ユーザが最も関連のある（複数の）典型を選択し、これにより彼又は彼女のプロファイルを初期化することを可能にし、（iii）前記選択された典型に基づいてリコメンデーションを生成する。
【００１８】
クラスタリング・ルーチン４００は、典型プロファイル処理部３００により呼び出され、１つのクラスタ内の点（テレビ番組）が、その他のクラスタより当該クラスタの平均（重心）に近くなるように第三者の視聴履歴１３０（データセット）をクラスタに分割する。クラスタリング・ルーチン４００は、クラスタの記号的平均を計算するために平均計算ルーチン５００を呼び出す。距離計算ルーチン６００は、クラスタリング・ルーチン４００により呼び出され、所定のテレビ番組と所定のクラスタの平均との間の距離に基づいて各クラスタに対するテレビ番組の近さを評価する。最後に、クラスタリング・ルーチン４００は、いつクラスタ作成の停止基準が満たされるかを決定するために、クラスタリング性能評価ルーチン８００を呼び出す。
【００１９】
図２は、図１の番組データベース（ＥＰＧ）２００のサンプルの表である。以前示されたように、番組データベース２００は、所定の時間間隔において利用可能である各番組の情報を記録する。図２に示されるように、番組データベース２００は、記録２０５乃至２２０のような複数の記録を含み、それぞれの記録は、所定の番組に関連付けられる。各番組に対して、番組データベース２００は、前記番組に関連した日付／時間及びチャネルをそれぞれフィールド２４０及び２５０に示す。加えて、各番組のタイトル、ジャンル及び俳優が、それぞれフィールド２５０，２５５及び２７０内で識別される。継続時間及び前記番組の解説のような、追加のよく知られたフィーチャ（図示されていない）も、番組データベース２００に含まれることができる。
【００２０】
図３は、本発明のフィーチャを組み込んでいる典型プロファイル処理部３００の模範的な実施を記述するフローチャートである。以前示されたように、典型プロファイル処理部３００は、（i）第三者の視聴履歴１３０を処理し、代表的視聴者により視聴されたテレビ番組の典型的なパターンを反映する典型プロファイルを生成し、（ii）ユーザが最も関連のある典型を選択し、これにより彼又は彼女のプロファイルを初期化することを可能にし、（iii）前記選択された典型に基づいてリコメンデーションを生成する。第三者の視聴履歴１３０の処理は、例えば工場内で、オフラインで実行されてもよく、テレビ番組リコメンダ１００は、ユーザによる選択に対する前記生成された典型プロファイルをインストールされた状態で前記ユーザに提供されることができる。
【００２１】
従って、図３に示されるように、典型プロファイル処理部３００は、最初にステップ３１０の間に第三者の視聴履歴１３０を集める。この後、典型プロファイル処理部３００は、典型プロファイルに対応する番組のクラスタを生成するためにステップ３２０の間に図４と併せて下で論じられるクラスタリング・ルーチン４００を実行する。更に下で論じられるように、模範的なクラスタリング・ルーチン４００は、視聴履歴データセット１３０に対して、“ｋ平均”クラスタリング・ルーチンのような監督されない（unsupervised）データ・クラスタリング・アルゴリズムを採用することができる。以前示されたように、クラスタリング・ルーチン４００は、１つのクラスタ内の点（テレビ番組）がその他のクラスタより当該クラスタの平均（重心）に近くなるように、第三者の視聴履歴１３０（前記データセット）をクラスタに分割する。
【００２２】
典型プロファイル処理部３００は、この場合、ステップ３３０の間に各クラスタに対して１つ以上のラベルを割り当て、前記ラベルは各典型プロファイルを特徴付ける。模範的な実施例において、前記クラスタの平均は、全体的なクラスタに対する代表的テレビ番組になり、前記平均の番組のフィーチャは、前記クラスタにラベルをつけるのに使用されることができる。例えば、テレビ番組リコメンダ１００は、ジャンルが各クラスタの支配的又は定義的フィーチャであるように構成されることができる。
【００２３】
前記ラベルをつけられた典型プロファイルは、前記ユーザの興味に最も近い典型プロファイルの選択のために、ステップ３４０の間に、各ユーザに提示される。各選択されたクラスタを構成する番組は、当該典型の“典型的な視聴履歴”として考えられることができ、各クラスタに対する典型的なプロファイルを作るために使用されることができる。従って、視聴履歴は、ステップ３５０の間に前記ユーザに対して生成され、前記選択された典型プロファイルからの番組から成る。最後に、前のステップで生成された前記視聴履歴は、番組リコメンデーションを得るためにステップ３６０の間に番組リコメンダに対して利用される。前記番組リコメンダは、当業者に明らかであるように、ここで修正された、上で参照されたような如何なる従来の番組リコメンダとして実施され得る。プログラム制御は、ステップ３７０の間に終了する。
【００２４】
図４は、本発明のフィーチャを組み込んでいるクラスタリング・ルーチン４００の模範的な実施を記述するフローチャートである。以前示されたように、クラスタリング・ルーチン４００は、ステップ３２０の間に典型プロファイル処理部３００により呼び出され、１つのクラスタ内の点（テレビ番組）がその他のクラスタより当該クラスタの平均（重心）に近くなるように、第三者の視聴履歴１３０をクラスタに分割する。一般に、クラスタリング・ルーチンは、サンプルデータセット内の標本のグループ分けを見つける監督されないタスクに重点を置く。本発明は、データセットをｋ平均クラスタリング・アルゴリズムを使用してｋ個のクラスタに分割する。この後論じられるように、クラスタリング・ルーチン４００の２つの主要なパラメータは、（i）図６と併せて下で論じられる最も近いクラスタを見つける距離メトリック、及び（ii）作るクラスタ数ｋである。
【００２５】
模範的なクラスタリング・ルーチン４００は、標本データの更に他のクラスタリングが分類精度の向上を生じない場合に安定なｋが達成されているという条件で、ｋの動的な値を採用する。加えて、前記クラスタのサイズは、空のクラスタが記録されるまでインクリメントされる。従って、クラスタリングは、クラスタの自然なレベルが到達された場合に停止する。
【００２６】
図４に示されるように、クラスタリング・ルーチン４００は、最初に、ステップ４１０の間にｋ個のクラスタを確立する。模範的なクラスタリング・ルーチン４００は、クラスタの最小の数、例えば２を選ぶことにより開始する。この固定された数に対して、クラスタリング・ルーチン４００は、全体的な視聴履歴データセット１３０を処理し、幾回か繰り返して、安定と見なされることができる（即ち、前記アルゴリズムが他の繰り返しを経ることになったとしても、何れの番組も一方のクラスタから他方のクラスタに移動しない）２つのクラスタに帰着する。現在のｋ個のクラスタは、１つ以上の番組と共にステップ４２０の間に初期化される。
【００２７】
１つの模範的な実施において、前記クラスタは、ステップ４２０の間に、第三者の視聴履歴１３０から選択された幾つかのシード番組によって初期化される。前記クラスタを初期化するための前記番組は、ランダムに又は順次的に選択されてもよい。順次的な実施において、前記クラスタは、視聴履歴１３０内の第１番組から開始する複数の番組又は視聴履歴１３０内のランダムな点から開始する複数の番組によって初期化され得る。依然として他の変形形態において、各クラスタを初期化する番組の数も、変更され得る。最後に、前記クラスタは、第三者の視聴履歴１３０内の番組からランダムに選択されたフィーチャ値からなる１つ以上の“仮定”番組によって初期化されてもよい。
【００２８】
この後、クラスタリング・ルーチン４００は、各クラスタの現在の平均を計算するためにステップ４３０の間に、図５と併せて下で論じられる平均計算ルーチン５００を開始する。クラスタリング・ルーチン４００は、この場合、各クラスタに対する第三者の視聴履歴１３０内の各番組の距離を決定するためにステップ４４０の間に、図６と併せて下で論じられる距離計算ルーチン６００を実行する。視聴履歴１３０内の各番組は、この場合、ステップ４６０の間に最も近いクラスタに割り当てられる。
【００２９】
何れかの番組が一方のクラスタから他方のクラスタに移動したかどうかを決定するためにステップ４７０の間にテストが実行される。もしステップ４７０の間に番組が一方のクラスタから他方のクラスタに移動したと決定されるならば、プログラム制御は、ステップ４３０に戻り、クラスタの安定なセットが識別されるまで上述の仕方で続行される。しかしながら、もしステップ４７０の間に何れの番組も一方のクラスタから他方のクラスタに移動していないと決定されるならば、プログラム制御はステップ４８０に進む。
【００３０】
指定された性能基準が満たされているかどうか、又は空のクラスタが識別されるかどうか（まとめて、“停止基準”）を決定するために、ステップ４８０の間に、更に他のテストが実行される。もしステップ４８０の間に前記停止基準が満たされていないと決定されるならば、ｋの値は、ステップ４８５の間にインクリメントされ、プログラム制御は、ステップ４２０に戻り、上述の仕方で続行する。しかしながら、もしステップ４８０の間に前記停止基準が満たされたと決定されるならば、プログラム制御は終了する。前記停止基準の評価は、図８と併せて下で更に論じられる。模範的なクラスタリング・ルーチン４００は、１つのクラスタのみの中に番組を配置し、従って、クリスプクラスタ（crisp cluster）と呼ばれるものを作る。更に他の変形形態は、特定の標本（テレビ番組）が複数のクラスタに部分的に属することを可能にするファジィクラスタリングを採用するだろう。前記ファジィクラスタリング方法において、テレビ番組は、テレビ番組がどれだけ前記クラスタの平均に近いかを表す重みを割り当てられる。前記重みは、前記クラスタ平均からの前記テレビ番組の距離の逆２乗に依存することができる。単一のテレビ番組に関連する全てのクラスタの重みの和は、合計１００％にならなければならない。
クラスタの記号的平均の計算
【００３１】
図５は、本発明のフィーチャを組み込んでいる平均計算ルーチン５００の模範的な実施を記述するフローチャートである。以前示されたように、平均計算ルーチン５００は、クラスタリング・ルーチン４００により呼び出され、クラスタの記号的平均を計算する。数値データに対して、前記平均は、分散を最小化する値である。この概念を記号データに拡張して、前記クラスタの平均は、クラスタ内分散（及びこの故に前記クラスタの半径又は大きさ）
Var(J)=Σi∈J(xi-xμ)2  （１）
クラスタ半径R(J)=√(Var(J))  （２）
を最小化するxμの値を見つけることにより定義されることができ、ここでJは、同じクラス（視聴された又は視聴されなかった）のテレビ番組のクラスタであり、xiは、番組iの記号的フィーチャ値であり、xμは、Var(J)を最小化するようなJ内の前記テレビ番組の１つのフィーチャ値である。
【００３２】
従って、図５に示されるように、平均計算ルーチン５００は、最初に、ステップ５１０の間に、現在所定のクラスタJ内にある前記番組を識別する。検討中の現在の記号的属性に対して、クラスタJの前記分散は、各取り得る記号的値xμに対して、ステップ５２０の間に式（１）を使用して計算される。前記分散を最小化する記号的値xμは、ステップ５３０の間に平均値として選択される。
【００３３】
考慮されるべき追加の記号的属性があるかどうか決定するためにステップ５４０の間にテストが実行される。もしステップ５４０の間に考慮されるべき追加の記号的属性があると決定されるならば、プログラム制御は、ステップ５２０に戻り、上述の仕方で続行する。しかしながら、もし考慮されるべき追加の記号的属性がないと決定されるならば、プログラム制御は、クラスタリング・ルーチン４００に戻る。
【００３４】
計算上、J内の各記号的フィーチャ値は、xμとして試行され、前記分散を最小化する記号的値は、クラスタJ内の検討中の記号的属性に対する平均になる。２種類の取り得る平均計算法があり、即ち番組に基づく平均及びフィーチャに基づく平均である。
【００３５】
フィーチャに基づく記号的平均
ここで論じられる模範的な平均計算ルーチン５００は、フィーチャに基づき、結果として生じるクラスタ平均は、クラスタJ内の標本（番組）から引き出されるフィーチャ値から成る。なぜならば記号的属性に対する平均は、取り得る値の１つでなくてはならないからである。しかしながら、前記クラスタ平均は、“仮定”テレビ番組であり得ることに注意することが重要である。この仮定番組のフィーチャ値は、前記標本の１つから引き出されるチャネル値（例えばＥＢＣ）と、前記標本の他の１つから引き出されるタイトル値（例えば、現実にはＥＢＣで放送されていないBBC World News）とを含むことができる。従って、最小分散を示す何れのフィーチャ値も、当該フィーチャの平均を表すために選択される。平均計算ルーチン５００は、ステップ５４０の間に全てのフィーチャ（即ち記号的属性）が考慮されたと決定されるまで、全てのフィーチャ位置に対して繰り返される。このように得られる結果として生じる仮定番組は、前記クラスタの平均を表すために使用される。
【００３６】
番組に基づく記号的平均
更に他の変形形態において、分散の式（１）において、xiは、テレビ番組iそのものであることができ、同様にxμは、クラスタJの中の番組のセットに対する分散を最小化するクラスタJの中の（複数の）番組である。この場合に、前記個別のフィーチャ値ではなく前記番組間の距離は、最小化されるべき関連したメトリックである。加えて、この場合の結果として生じる平均は、仮定番組ではなく、セットJから適切に選定された番組である。クラスタJ内の全ての番組に対する分散を最小化し、クラスタJ内でこのように発見される何れの番組も、前記クラスタの平均を表すのに使用される。
【００３７】
複数の番組を使用する記号的平均
上で論じられた模範的な平均計算ルーチン５００は、（フィーチャに基づく又は番組に基づく実施の何れにしろ）各取り得るフィーチャに対する単一のフィーチャ値を使用して前記クラスタの平均を特徴付ける。しかしながら、前記平均がもはや前記クラスタの代表的クラスタ中心ではなくなると、平均計算の間に各フィーチャに対して１つのフィーチャ値のみを信頼することは、しばしば誤ったクラスタリングを生じることがわかっている。換言すると、１つの番組のみによりクラスタを表すことは望ましくないかもしれないが、むしろ、前記平均又は複数の平均を表す複数の番組が、前記クラスタを表すのに採用され得る。従って、更に他の変形形態において、クラスタは、各取り得るフィーチャに対して複数の平均又は複数のフィーチャ値により表され得る。従って、前記分散を最小化するＮ個のフィーチャ（フィーチャに基づく記号的平均に対して）又はＮ個の番組（番組に基づく記号的平均に対して）が、ステップ５３０の間に選択され、ここでＮは、クラスタの平均を表すのに使用される番組数である。
【００３８】
番組とクラスタとの間の距離計算
以前示されたように、距離計算ルーチン６００は、クラスタリング・ルーチン４００により呼び出され、所定のテレビ番組と所定のクラスタの平均との間の距離に基づいて各クラスタに対するテレビ番組の近さを評価する。計算された前記距離のメトリックは、サンプルデータセット内の様々な標本の間の相違を数値化し、クラスタの範囲を決定する。ユーザプロファイルをクラスタリングすることができるために、視聴履歴内の何れの２つの番組間の距離も計算されなければならない。一般に、互いに近いテレビ番組は、１つのクラスタに分類される傾向にある。ユークリッド距離、マンハッタン距離及びマハラノビス距離のような、数値ベクトル間の距離を計算する多数の相対的に直接の技法が存在する。
【００３９】
しかしながら、テレビ番組は、主として記号的フィーチャ値から成るので、従来の距離計算技法は、テレビ番組ベクトルの場合に使用されることができない。例えば、ＥＢＣで２００１年３月２２日の午後８時から放送される“Fiends”のエピソード及びＦＥＸで２００１年３月２５日の午後８時から放送される“The Simons”のエピソードのような２つのテレビ番組は、以下のフィーチャベクトルを使用して表されることができる。
タイトル：Fiends        タイトル：Simons
チャネル：ＥＢＣ        チャネル：ＦＥＸ
放送日程：2001-03-22    放送日程：2001-03-25
放送時間：2000          放送時間：2000
【００４０】
明らかに、既知の数値的な距離メトリックは、フィーチャ値“ＥＢＣ”と“ＦＥＸ”との間の距離を計算するのに使用されることができない。値差メトリック（Value Difference Metric）（ＶＤＭ）は、記号的フィーチャ値領域内のフィーチャの値の間の距離を測定する既存の技法である。ＶＤＭ技法は、各フィーチャの各取り得る値に対する全ての事例の分類の全体的な類似性を考慮に入れる。この方法を使用して、フィーチャの全ての値の間の距離を定義する行列は、訓練セット内の標本に基づいて統計的に導かれる。記号的フィーチャ値間の距離を計算するＶＤＭ技法のより詳細な解説について、例えば、参照によりここに組み込まれるStanfill and Waltz, “Toward Memory-Based Reasoning”, Communications of the ACM, 29:19, 1213-1228 (1986)を参照する。
【００４１】
本発明は、２つのテレビ番組又は他の興味のあるアイテムの間のフィーチャ値間の前記距離を計算するために、ＶＤＭ技法又はその変形形態を採用する。元のＶＤＭ案は、２つのフィーチャ値間の距離計算において、前記距離メトリックを非対称にする重み項を採用する。修正ＶＤＭ（ＭＶＤＭ）は、距離行列を対象にするために前記重み項を省く。記号的フィーチャ値間の距離を計算するＭＶＤＭ技法のより詳細な解説について、例えば、参照によりここに組み込まれるCost and Saltzberg, “A Weighted Nearest Neighbor Algorithm For Learning With Symbolic Features”, Machine Learning, Vol. 10, 57-58, Boston, MA, Kluwer Publishers (1993)を参照する。
【００４２】
ＭＶＤＭによると、特定のフィーチャに対する２つの値V1とV2との間の距離δは、
δ(V1, V2)=Σ|C1i/C1-C2i/C2|r    式（３）
により与えられる。
【００４３】
本発明の番組リコメンデーション環境において、特に、ＭＶＤＭの式（３）は、クラス“視聴された”及び“視聴されなかった”を処理するように変換される。
【数１】
2005509968.tif 000003
【００４４】
式（４）において、V1及びV2は、検討中のフィーチャに対する２つの取り得る値である。上の例を続けて、第１の値V1は、フィーチャ“チャネル”に対する“ＥＢＣ”に等しく、第２の値V2は、“ＦＥＸ”に等しい。前記値の間の距離は、前記標本が分類される全てのクラスに対する和である。本発明の模範的な番組リコメンダ実施例の関連のあるクラスは、“視聴された”及び“視聴されなかった”である。C1iは、V1（ＥＢＣ）がクラスi（１に等しいiはクラス“視聴された”を示す）に分類された回数であり、C1（C1_total）は、前記データセットにおいてV1が生じた全ての回数である。値“r”は定数であり、通常、１に設定される。
【００４５】
式（４）により定義されたメトリックは、もし値が全ての分類に対して同じ相対的な頻度で生じるならば、当該値を同様であると識別するだろう。項C1i/C1は、当該フィーチャが値V1を持つという条件で、その中央残余（central residue）が、iとして分類されるであろう尤度を表す。従って、２つの値は、もし前記２つの値が全ての取り得る分類に対して同様な尤度を与えるならば、同様である。式（４）は、全ての分類に対するこれらの尤度の差の和を見いだすことにより２つの値の間の全体的な類似性を計算する。２つのテレビ番組間の距離は、前記２つのテレビ番組のベクトルの対応するフィーチャ値間の距離の和である。
【００４６】
図７Ａは、前記フィーチャ“チャネル”に関連した前記フィーチャ値に対する距離の表の一部である。図７Ａは、各クラスに対する各チャネルフィーチャ値の発生数をプログラムする。図７Ａに示される値は、模範的な第三者の視聴履歴１３０から取られた。
【００４７】
図７Ｂは、ＭＶＤＭの式（４）を使用して図７Ａに示される模範的なカウントから計算される各フィーチャ値対の間の距離を表示する。直覚的に、ＥＢＣ及びＡＢＳは、ほとんど前記視聴されたクラスにおいて生じ、前記視聴されなかったクラスにおいては生じない（ＡＢＳは小さな視聴されなかった成分を持つ）ので、ＥＢＣ及びＡＢＳは、互いに“近い”はずである。図７Ｂは、ＥＢＣとＡＢＳとの間の小さな（非ゼロ）距離によりこの直覚を確認する。これに対し、ＡＳＰＮは、ほとんど前記視聴されなかったクラスにおいて生じ、この故に、このデータセットに対してはＥＢＣ及びＡＢＳ両方から“遠い”はずである。図７Ｂは、ＥＢＣとＡＳＰＮとの間の距離が、最大の取り得る距離２．０に対して１．８９５であるようにプログラムする。同様に、ＡＢＳとＡＳＰＮとの間の距離は、大きく、１．８２８の値を持つ。
【００４８】
従って、図６に示されるように、距離計算ルーチン６００は、最初に、ステップ６１０の間に第三者の視聴履歴１３０内の番組を識別する。検討中の現在の前記番組に対して、距離計算ルーチン６００は、ステップ６２０の間に、（平均計算ルーチン５００により決定された）各クラスタ平均の対応するフィーチャに対する各記号的フィーチャ値の距離を計算するために式（４）を使用する。
【００４９】
前記現在の番組と前記クラスタ平均との間の距離は、ステップ６３０の間に対応するフィーチャ値間の距離を合計することにより計算される。ステップ６４０の間に、第三者の視聴履歴１３０内に考慮されるべき追加の番組があるかどうかを決定するためにテストが実行される。もしステップ６４０の間に第三者の視聴履歴１３０内に考慮されるべき追加の番組があると決定されるならば、次の番組は、ステップ６５０の間に識別され、プログラム制御は、ステップ６２０に進み、上述の仕方で続行する。
【００５０】
しかしながら、ステップ６４０の間に、第三者の視聴履歴１３０内に考慮されるべき追加の番組が無いと決定されるならば、プログラム制御は、クラスタリング・ルーチン４００に戻る。
【００５１】
“複数の番組を使用する記号的平均”と題されたサブセクションで以前論じられたように、前記クラスタの平均は、各取り得るフィーチャ（フィーチャに基づく又は番組に基づく実施の何れにしろ）に対する複数のフィーチャ値を使用して特徴付けられることができる。複数の平均からの結果は、この場合、距離計算ルーチン６００の変形形態によりプールされ、投票により合意の決定に帰着する。例えば、ステップ６２０の間に、１つの番組の所定のフィーチャ値と様々な平均に対する対応するフィーチャ値のそれぞれとの間の距離が、ここで計算される。最小距離の結果が、例えば、合意の決定に帰着するように多数決又は混合エキスパート（mixture of experts）を採用することにより投票のためにプールされ、使用される。このような技法のより詳細な解説について、例えば、参照によりここに組み込まれるJ. Kittler et al., “Combining Classifiers”, in Proc. Of the 13th Int’l Conf. On Pattern Recognition, Vol. II, 897-901, Vienna, Austria (1996)を参照する。
【００５２】
停止基準
以前示されたように、クラスタリング・ルーチン４００は、クラスタ作成の停止基準がいつ満たされるかを決定するために、図８に示されるクラスタリング性能評価ルーチン８００を呼び出す。模範的なクラスタリング・ルーチン４００は、更に他の標本データのクラスタリングが分類精度の向上を生じない場合に安定なｋが達成されるという条件で、動的な値ｋを採用する。加えて、クラスタサイズは、空のクラスタが記録されるまでインクリメントされることができる。従って、クラスタの自然なレベルが到達された場合に、クラスタリングは停止する。
【００５３】
模範的なクラスタリング性能評価ルーチン８００は、クラスタリング・ルーチン４００の分類精度をテストするために第三者の視聴履歴１３０（テストデータセット）からの番組のサブセットを使用する。前記テストセット内の各番組に対し、クラスタリング性能評価ルーチン８００は、前記各番組に最も近いクラスタ（どのクラスタ平均が最も近いか）を決定し、前記クラスタに対するクラスラベルと検討中の前記番組とを比較する。マッチしたクラスラベルのパーセンテージは、クラスタリング・ルーチン４００の精度に変換される。
【００５４】
従って、図８に示されるように、クラスタリング性能評価ルーチン８００は、最初に、ステップ８１０の間に第三者の視聴履歴１３０から前記番組のサブセットを集め、前記テストデータセットとして供給する。この後、クラスラベルは、ステップ８２０の間に視聴された及び視聴されなかったクラスタの番組の割合に基づいて各クラスタに割り当てられる。例えば、もしクラスタ内のほとんどの番組が視聴されたならば、前記クラスタは、“視聴された”のラベルを割り当てられることができる。
【００５５】
前記テストセット内の各番組に最も近いクラスタは、ステップ８３０の間に識別され、前記割り当てられたクラスタに対する前記クラスラベルは、前記番組が実際に視聴されたかどうかと比較される。複数の番組が１つのクラスタの平均を表すために使用される実施において、（各番組に対する）平均距離又は投票スキームが採用される。マッチしたクラスラベルの割合は、プログラム制御がクラスタリング・ルーチン４００に戻る前にステップ８４０の間に決定される。クラスタリング・ルーチン４００は、もし前記分類精度が所定の閾値に到達されれば、終了するだろう。
【００５６】
ここに示され、記述された実施例及び変形形態は、単に、本発明の原理を説明するにすぎず、様々な修正が、本発明の範囲及び精神から外れることなく当業者により実施され得ると理解されるべきである。
【図面の簡単な説明】
【００５７】
【図１】本発明によるテレビ番組リコメンダの概略的なブロック図である。
【図２】図１の模範的な番組データベースのサンプルの表である。
【図３】本発明の原理を実施する図１の典型プロファイル処理部を記述するフローチャートである。
【図４】本発明の原理を実施する図１のクラスタリング・ルーチンを記述するフローチャートである。
【図５】本発明の原理を実施する図１の平均計算ルーチンを記述するフローチャートである。
【図６】本発明の原理を実施する図１の距離計算ルーチンを記述するフローチャートである。
【図７Ａ】各クラスに対する各チャネルフィーチャ値の発生数を示す模範的なチャネルフィーチャ値発生表のサンプルの表である。
【図７Ｂ】図７Ａに示された模範的なカウントから計算された各フィーチャ値対間の距離を示す模範的なフィーチャ値対距離表のサンプルの表である。
【図８】本発明の原理を実施する図１のクラスタリング性能評価ルーチンを記述するフローチャートである。
【図１】
2005509968.tif 000004
【図２】
2005509968.tif 000005
【図３】
2005509968.tif 000006
【図４】
2005509968.tif 000007
【図５】
2005509968.tif 000008
【図６】
2005509968.tif 000009
【図７Ａ】
2005509968.tif 000010
【図７Ｂ】
2005509968.tif 000011
【図８】
2005509968.tif 000012
【国際調査報告】
2005509968.tif 000013
2005509968.tif 000014