(57)【要約】  推奨テレビ番組のような対象品目を利用者に対して該利用者の視聴履歴又は購入履歴が利用可能になる前に推奨する方法及び装置を開示する。第３者視聴又は購入履歴が処理されて、典型的な視聴者によって選定された品目の典型的なパターンを反映するステレオタイプ・プロフィールを生成する。利用者は最も適切なステレオタイプを生成ステレオタイプ・プロフィールから選定し得、それによって該利用者のプロフィールを該利用者の自らの興味に最も近い品目によって初期化する。第３者視聴又は購入履歴（データ・セット）がクラスタに分割される、１つのクラスタにおけるポイント（例えば、テレビ番組）が他のいかなるクラスタよりもそのクラスタの平均値に近い、クラスタ化ルーチンを開示する。更に、クラスタの記号的平均値を算定する平均値算定ルーチンを開示する。
2005509967.tif 000002
【特許請求の範囲】
【請求項１】
利用者の選好を示す利用者プロフィールを更新する方法であって：
少なくとも１つの第３者によって選定された品目を表す第３者選定履歴を取得する工程；
前記第３者選定履歴を品目のクラスタに分割する工程；
前記クラスタの少なくとも１つの選定を前記利用者から受領する工程；及び
前記利用者プロフィールを前記少なくとも１つの選定クラスタからの品目によって更新する工程；
を有することを特徴とする方法。
【請求項２】
請求項１記載の方法であって、更に：
前記利用者プロフィールに基づいて品目を推奨する工程；
を有することを特徴とする方法。
【請求項３】
請求項１記載の方法であって、更に：
前記クラスタの各々にラベルを割り当てる工程；
を有することを特徴とする方法。
【請求項４】
請求項３記載の方法であって、前記利用者が前記割り当てられたラベルに基づいて前記少なくとも１つのクラスタを選定することを特徴とする方法。
【請求項５】
請求項１記載の方法であって、前記分割する工程が更に：
k-平均値法クラスタ化ルーチンを使用する工程；
を有することを特徴とする方法。
【請求項６】
請求項１記載の方法であって、前記品目が番組、コンテンツ及び商品の種類のうちの少なくとも１つのものであることを特徴とする方法。
【請求項７】
利用者の選好を示す利用者プロフィールを更新するシステムであって：
コンピュータによって判読可能なコードを記憶する記憶装置；及び
前記記憶装置に動作上、結合された処理装置；
を有し、該処理装置が：
少なくとも１つの第3者によって選定された品目を示す第３者選定履歴を取得する工程；
前記第3者選定履歴を品目のクラスタに分割する工程；
前記クラスタの少なくとも１つの選定を前記利用者から受領する工程；及び
前記利用者プロフィールを前記少なくとも１つの選定クラスタからの品目によって更新する工程；
を行うよう構成されていることを特徴とするシステム。
【請求項８】
請求項７記載のシステムであって、前記処理装置が：
前記選定クラスタに基づいて品目を推奨する工程；
を行うよう構成されていることを特徴とするシステム。
【請求項９】
利用者の選好を示す利用者プロフィールを更新する製造物品であって：
コンピュータによって判読可能な媒体；
を有し、該媒体は該媒体上にコンピュータによって判読可能なコード手段を有し、該コンピュータによって判読可能なコード手段は：
少なくとも１つの第3者によって選定された品目を示す第３者選定履歴を取得する工程；
前記第3者選定履歴を品目のクラスタに分割する工程；
前記クラスタの少なくとも１つの選定を前記利用者から受領する工程；及び
前記利用者プロフィールを前記少なくとも１つの選定クラスタからの品目によって更新する工程；
を有することを特徴とする製造物品。
【請求項１０】
請求項９記載の製造物品であって、前記コンピュータによって判読可能なコード手段が更に：
前記選定クラスタに基づいて品目を推奨する工程；
を有することを特徴とする製造物品。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、テレビ番組のような、対象品目を推奨する方法及び装置に関し、特に、利用者の購入又は視聴履歴が利用可能である以前に、番組及び他の対象品目を推奨する手法に関する。
【背景技術】
【０００２】
テレビ視聴者が利用可能なチャンネル数が、そのようなチャンネル上で利用可能な番組コンテンツの多様性に加えて、増加するにつれて、テレビ視聴者が対象テレビ番組を見分けるのはますます難しくなってきている。電子番組ガイド（ＥＰＧ）は利用可能なテレビ番組を、例えば、題名、時間、日付及びチャンネルによって、特定し、個人別選好に応じて、利用可能なテレビ番組を検索又はソートすることを可能にすることによって、対象番組を特定することを容易にする。
【０００３】
テレビ番組及び他の対象品目を推奨する、多数の推奨ツールが提案又は提唱されている。テレビ番組推奨ツールは、例えば、視聴者選好をＥＰＧに当てはめて特定視聴者が関心を持ち得る推奨番組群を取得する。一般に、テレビ番組推奨ツールは明示的又は暗黙的ツールを用いるか、上述の何らかの組み合わせを用いて、視聴者選好を取得する。暗黙的テレビ番組推奨ツールはテレビ番組の推奨を視聴者の視聴履歴から導き出された情報に基づいて、知らず知らずのうちに、生成する。一方、明示的テレビ番組推奨ツールは、明示的に視聴者に、題名、ジャンル、俳優、チャンネル及び日時のような、番組の属性についての選好について尋ねて、視聴者プロフィールを導き出して推奨を生成する。
【特許文献１】米国特許出願公開第09/819286号明細書
【特許文献２】米国特許出願公開第09/466406号明細書
【特許文献３】米国特許出願公開第09/498271号明細書
【特許文献４】米国特許出願公開第09/627139号明細書
【非特許文献１】Stanfill及びWaltz、“Toward  Memory-Based  Reasoning”、Communications  of  the  ACM、1986年、29:12号、1213-1228頁
【非特許文献２】Cost及びSalzberg、“A  Weighted  Nearest  Neighbor  Algorithm  For  Learning  With  Symbolic  Features”、Machine  Learning、  Kluwer  Publishers(Boston、MA)、1993年、10号、57-58頁
【非特許文献３】J.  Kittler他、”Combing  Classifiers”、Proc.  of  the  13th  Int’l  Conf.  on  Pattern  Recognition“、オーストリア、Vienna、1996年、II号、897-901頁
【発明の開示】
【発明が解決しようとする課題】
【０００４】
現在利用可能な推奨ツールは利用者が対象品目を特定するのを助力するが、多数の制限を受け、そしてそれは、克服された場合、そのような推奨ツールの利便性及び性能を大きく向上させ得る。例えば、明示的推奨ツールの徹底的な実施においては、初期化するのが非常に冗長で、各新規利用者が粗粒度レベルで該新規利用者の選好を特定する非常に詳細な調査に回答することを必要とする。暗黙的テレビ番組推奨ツールがプロフィールを、知らず知らずのうちに視聴行動を観察することによって、導き出す一方、正確になるには長期間を要する。更に、そのような暗黙的テレビ番組推奨ツールは何らかの推奨を行い始めるのに少なくとも最小量の視聴履歴を必要とする。したがって、そのような暗黙的テレビ番組推奨ツールは、推奨ツールが最初に取得される際に、如何なる推奨をも行うことができない。
【０００５】
したがって、テレビ番組のような品目を、十分な個人別視聴履歴が利用可能になる前に、知らず知らずのうちに推奨し得る、方法及び装置についてのニーズが存在する。更に、第3者の視聴行動に基づいて特定の利用者についての番組推奨を生成する方法及び装置についてのニーズが存在する。
【課題を解決するための手段】
【０００６】
一般に、利用者に対して、推奨テレビ番組のような、対象品目を推奨する方法及び装置を開示する。本発明の一特徴によれば、推奨は、例えば、利用者が最初に当該推奨ツールを取得した際のように、利用者の視聴履歴又は購入履歴が利用可能になる前に、生成し得る。最初に、1つ以上の第3者からの視聴履歴又は購入履歴が利用されて特定利用者に対する対象品目を推奨する。第３者視聴又は購入履歴は更に大きな母集団の典型を示す人口統計を有する標本集団から取得される。
【０００７】
第３者視聴又は購入履歴は、典型的な視聴者によって選定された品目の典型的パターンを反映する、ステレオタイプ・プロフィールを生成するよう処理される。ここで用いられるように、ステレオタイプ・プロフィールはある程度お互いが類似している品目（データ・ポイント）のクラスタである。したがって、特定のクラスタは特定のパターンを表す第3者視聴又は購入履歴からの選定品目の特定セグメントに相当する。ステレオタイプ・プロフィールが本発明によって生成されると、利用者は最も適切なステレオタイプを選定し得、それによって、該利用者のプロフィールを、該利用者自らの興味に最も近い品目によって初期化する。ステレオタイプ・プロフィールは更に、各個別利用者の特定の、個人視聴行動に向けて、選定パターン及び何らかのフィードバックが設けられることによって、調整されて発展する。
【０００８】
第３者視聴又は購入履歴（データ・セット）がクラスタに分割されて、１つのクラスタにおけるポイント（例えば、テレビ番組）が、他のいかなるクラスタよりも、そのクラスタの平均値に近いような、クラスタ化ルーチンを開示する。更に、クラスタの記号的平均値を算定する平均値算定ルーチンを開示する。テレビ番組のような、特定のデータ・ポイントが、クラスタに、該データ・ポイントと各クラスタとの間の距離に基づいて各クラスタの平均値を用いて割り当てられる。クラスタ化性能評価ルーチンはクラスタ生成を停止する、あらかじめ定義された基準がいつ充足されたかを判定する。
【発明を実施するための最良の形態】
【０００９】
図１は本発明によるテレビ番組推奨ツール100を示す。図１に表すように、例示的テレビ番組推奨ツール100は、特定視聴者向け対象番組を特定するよう、図２とともに説明する番組データベース200中の番組を評価する。推奨番組群は視聴者に向けて、例えば、（図なしの）セット・トップ端末/テレビを用いて周知の画面上プレゼンテーション手法を用いて、表示される。ここでは本発明をテレビ番組の推奨に関連して示す一方、本発明は、視聴履歴又は購入履歴のような、利用者行動の評価に基づいた如何なる自動生成推奨にも適用し得る。
【実施例】
【００１０】
本発明の一特徴によれば、テレビ番組推奨ツール100は、利用者が最初にテレビ番組推奨ツール100を取得する際のように利用者の視聴履歴140が利用可能になる前に、テレビ番組推奨を生成し得る。図１に表すように、テレビ番組推奨ツール100は最初に1つ以上の第３者からの視聴履歴130を利用して特定利用者に対して対象番組を推奨する。一般に、第3者視聴履歴130は、年齢、収入、性別及び教育のような、更に大きな母集団の典型を示す人口統計を有する1つ以上の標本集団の視聴習慣に基づくものである。
【００１１】
図１に表すように、第３者視聴履歴130は特定の母集団による視聴/非視聴番組群を有する。視聴番組群は該特定の母集団によって実際に視聴された番組を観察することによって取得される。視聴されない番組群は、例えば、番組データベース200中の番組を無作為標本抽出することによって、取得される。視聴されない番組群が「Adaptive  Sampling  Technique  for  Selecting  Negative  Examples  for  Artificial  Intelligence  Applications」と題する、西暦2001年3月28日付特許出願（特許文献１参照。）の教示によって取得される別の実施例もある。
【００１２】
本発明の別の特徴によれば、テレビ番組推奨ツール100は、典型的な視聴者によって視聴されるテレビ番組の典型的なパターンを反映するステレオタイプ・プロフィールを生成するよう、第３者視聴履歴130を処理する。更に以下に説明するように、ステレオタイプ・プロフィールは、ある程度お互いに類似しているテレビ番組（データ・ポイント）のクラスタである。したがって、特定のクラスタは特定のパターンを表す第３者視聴履歴130からのテレビ番組の特定セグメントに対応する。
【００１３】
第３者視聴履歴130はある特定のパターンを表す番組のクラスタを設けるよう本発明によって処理される。その後、利用者は最も適切なステレオタイプを選定し得、それによって該利用者のプロフィールを該利用者自らの興味に最も近い番組によって初期化する。ステレオタイプ・プロフィールは更に、その記録パターン、及び番組に対するフィードバックに応じて、各個別利用者の特定の、個人視聴行動に向けて調整されて発展する。一実施例においては、番組スコアを判定する際に、利用者の自らの視聴履歴140からの番組に第３者視聴履歴からの番組よりも高い重みづけを与え得る。
【００１４】
テレビ番組推奨ツール100は、中央処理装置（ＣＰＵ）のような処理装置115、及びＲＡＭ（読み込み書き込み記憶装置）及び/又はＲＯＭ（読み取り専用記憶装置）のような、記憶装置120を有する、パーソナル・コンピュータ又はワークステーションのような、如何なる算定装置としてでも実施され得る。テレビ番組推奨ツール100は更に、例えば、（図なしの）セット・トップ端末又は表示装置における、特定用途向け集積回路（ＡＳＩＣ）として実施され得る。更に、テレビ番組推奨ツール100はティーヴォ（Tivo）（商標）の、ティーヴォ（Tivo）社（カリフォルニア州サニーヴェール）から商用で入手可能な、システムのような、如何なる利用可能なテレビ番組推奨ツールとしてでも実施し得、又、「Method  and  Apparatus  for  Recommending  Television  Programming  Using  Decision  Trees」と題する、西暦1999年12月17日付特許出願（特許文献２参照。）、「Bayesian  TV  Show  Recommender」と題する、西暦2000年2月4日付特許出願（特許文献３参照。）、及び「Three-Way  Media  Recommendation  Method  and  System」と題する、西暦2000年７月２７日付特許出願（特許文献４参照。）に記載されたテレビ番組推奨ツール、若しくはそれらの如何なる組み合わせとしてでも、本発明の特徴および機能を実行するようここで変更されたように、実施し得る。
【００１５】
図１に表して、図２乃至８とともに更に以下に説明するように、テレビ番組推奨ツール100は番組データベース200、ステレオタイプ・プロフィール処理300、クラスタ化ルーチン400、平均値算定ルーチン500、距離算定ルーチン600及びクラスタ性能評価ルーチン800を有する。一般に、番組データベース200は周知の電子番組ガイドとして実施され得、特定の時間間隔において入手可能な各番組についての情報を記録する。ステレオタイプ・プロフィール処理300は(i)典型的な視聴者によって視聴されるテレビ番組の典型的なパターンを反映するステレオタイプ・プロフィールを生成するよう第３者視聴履歴130を処理して；(ii)利用者が最も適切なステレオタイプを選定することを可能にして；かつ、(iii)選定ステレオタイプに基づいた推奨を生成する。
【００１６】
クラスタ化ルーチン400は、１つのクラスタにおけるポイント（テレビ番組）が他のいかなるクラスタよりもそのクラスタの平均値（質量中心）に近くなるように、第3者視聴履歴130（データ・セット）をクラスタに分割するよう、ステレオタイプ・プロフィール化処理300によって呼び出される。クラスタ化ルーチン400は平均値算定ルーチン500を呼び出してクラスタの記号的平均値を算定する。距離算定ルーチン600は、特定のテレビ番組と、特定のクラスタの平均値との間の距離に基づいてテレビ番組が各クラスタにどれくらい近いかを評価するよう、クラスタ化ルーチン400によって呼び出される。最後に、クラスタ化ルーチン400は、クラスタの生成を停止する基準がいつ充足されたかを判定するよう、クラスタ化性能評価ルーチン800を呼び出す。
【００１７】
図２は図１の番組データベース（EPG）200からの見本テーブルである。上記のように、番組データベース200は特定の時間間隔において入手可能な各番組についての情報を記録する。図２に表すように、番組データベース200は、各々が特定の番組と関係する、記録205乃至220のような、複数の記録を有する。各番組について、番組データベース200はフィールド240及び245各々における番組に関係する日時及びチャンネルを示す。更に、各番組の、題名、ジャンル及び俳優がフィールド250、255及び270において特定される。番組の長さ及び説明のような、（図なしの）他の周知の特徴も更に、番組データベース200に有し得る。
【００１８】
図３は本発明の特徴を組み込んだステレオタイプ・プロフィール処理300の例示的実施形態を説明する流れ図である。上記のように、ステレオタイプ・プロフィール処理300は(i)典型的な視聴者によって視聴されるテレビ番組の典型的なパターンを反映するステレオタイプ・プロフィールを生成するよう、第３者視聴履歴130を処理して；(ii)利用者が最も適切なステレオタイプを選定してそれによって当該利用者のプロフィールを初期化することを可能にして；かつ(iii)選定ステレオタイプに基づいて推奨を生成する。第3者視聴履歴130の処理はオフライン、例えば、工場内、にて実行され得、テレビ番組推奨ツール100は利用者による選定用生成ステレオタイプ・プロフィールがインストールされた利用者に向けて設け得ることを特筆する。
【００１９】
したがって、図３に表すように、ステレオタイプ・プロフィール処理300はまず、工程310中に第３者視聴履歴130を収集する。その後、ステレオタイプ・プロフィール処理300は、図４とともに下記に説明するように、工程320中に、ステレオタイプ・プロフィールに対応する番組のクラスタを生成するよう、クラスタ化ルーチン400を実行する。更に下記に説明するように、例示的クラスタ化ルーチン400は「k-平均値法」クラスタ化ルーチンのような、管理されていないデータ・クラスタ化アルゴリズムを、視聴履歴データ・セット130に対して用い得る。上記のように、クラスタ化ルーチン400は、１つのクラスタにおけるポイント（テレビ番組）が他の如何なるクラスタよりもそのクラスタの平均値（質量中心）に近くなるよう、第3者視聴履歴130（データ・セット）をクラスタに分割する。
【００２０】
ステレオタイプ・プロフィール処理300は更に、工程330中に、1つ以上の各ステレオタイプ・プロフィールを特徴付けるラベルを各クラスタに割り当てる。一例示的実施例においては、クラスタの平均値はクラスタ全体についての典型的なテレビ番組となって、該平均値番組の特徴を、クラスタをラベル化するのに用い得る。例えば、テレビ番組推奨ツール100は、ジャンルが各クラスタについての、優性の、すなわち、特徴付ける、特徴であるよう、構成し得る。
【００２１】
ラベルされたステレオタイプ・プロフィールは、工程340中に、利用者の興味に最も近いステレオタイプ・プロフィールの選定のために各利用者に対して示される。各選定クラスタを構成する番組はそのステレオタイプの「典型的な視聴履歴」として考えることができ、各クラスタについてのステレオタイプ・プロフィールを構築するのに用いられ得る。したがって、工程350中に、選定ステレオタイプ・プロフィールからの番組を有する視聴履歴が利用者に向けて生成される。最後に、上記工程において生成された視聴履歴が、番組推奨を取得するよう、工程360中に番組推奨ツールに当てはめられる。番組推奨ツールは、当業者には明白なように、上記で参照されたような、ここにおいて変更された、如何なる従来の番組推奨ツールとしてでも実施し得る。プログラムの制御は工程370中に終了する。
【００２２】
図４は本発明の特徴を組み込んだクラスタ化ルーチン400の例示的実施形態を説明する流れ図である。上記のように、クラスタ化ルーチン400はステレオタイプ・プロフィール処理300によって工程320中に呼び出されて、１つのクラスタにおけるポイント（テレビ番組）が他の如何なるクラスタよりもそのクラスタの平均値（質量中心）に近くなるよう、第３者視聴履歴130（データ・セット）をクラスタに分割する。一般に、クラスタ化ルーチンは標本データ・セットにおける例のグループ分けを見出す、管理されていない、タスクを重点的に取り扱う。本発明はデータ・セットをｋのクラスタにk-平均値法クラスタ化アルゴリズムを用いて分割する。以下に説明するように、クラスタ化ルーチン400に対する２つの主要パラメータには：(i)図６とともに以下に説明する、最も近いクラスタを見出す距離メトリック；及び(ii)生成するクラスタ数、ｋ；がある。
【００２３】
例示的クラスタ化ルーチン400は、例データを更にクラスタ化しても如何なる分類精度の向上をももたらさない場合に安定値ｋに達するという条件で、ｋの動的値を利用する。更に、クラスタ・サイズが、空のクラスタが記録される時点まで増加される。したがって、クラスタ化は、クラスタの自然レベルに達した際に停止する。
【００２４】
図４に表すように、クラスタ化ルーチン400はまず、工程410中にｋのクラスタを定める。例示的クラスタ化ルーチン400はクラスタの最低数、例えば２、を選択することによって開始する。この固定数について、クラスタ化ルーチン400は視聴履歴データ130全体を処理して、数回の繰り返し後、安定的（すなわち、アルゴリズムが更に一度繰り返したとしても、１つのクラスタから別のクラスタに移動する番組はない）と考えられ得る２つのクラスタに達する。現時のｋのクラスタは工程420中に1つ以上の番組によって初期化される。
【００２５】
１つの例示的実施形態においては、クラスタは工程420中に第３者視聴履歴130から選定された、いくつかのシード番組によって初期化される。クラスタを初期化する番組は無作為に又は順次に選定し得る。順次実施形態においては、クラスタは視聴履歴130における最初の番組から始まる番組か、視聴履歴130における任意の点で始まる番組によって初期化し得る。更に別の変形例においては、各クラスタを初期化する番組数は更に変動させ得る。最後に、クラスタは第3者視聴履歴130における番組から無作為に選定された特徴値を有する1つ以上の「仮想の」番組によって初期化し得る。
【００２６】
その後、クラスタ化ルーチン400は、図５とともに以下に説明する、平均値算定ルーチン500を、工程430中に各クラスタの現時の平均値を算定するよう初期化する。クラスタ化ルーチン400は更に、図６とともに以下に説明する、距離算定ルーチン600を、工程440中に、第３者視聴履歴130中の各番組の各クラスタまでの距離を判定するよう、実行する。視聴履歴130中の各番組は更に工程460中に最も近いクラスタに割り当てられる。
【００２７】
工程470中に、１つのクラスタから別のクラスタに移動した番組があるかを判定するテストを行う。工程470中に番組が１つのクラスタから別のクラスタに移動したと判定された場合、プログラム制御は工程430に戻って、クラスタの安定群が特定されるまで上記に説明した方法で続行する。しかしながら、工程470中に、１つのクラスタから別のクラスタに移動した番組はないと判断された場合には、プログラム制御は工程480に進む。
【００２８】
工程480中には、特定の性能基準が充足されたか、空のクラスタが特定されたか（集合的に、「停止基準」と呼ぶ。）を判定するテストを更に行う。工程480中に停止基準が充足されていない場合、ｋの値は工程485中に増加されてプログラム制御は工程420に戻って上記の方法によって続行する。しかしながら、工程480中に停止基準が充足されたと判断された場合、プログラム制御は終了する。停止基準の評価は更に以下に図８とともに説明する。
【００２９】
例示的クラスタ化ルーチン400は番組を１つのクラスタに配置するので、クリスプなクラスタと呼ばれるものを生成する。更に別の変形例はファジーなクラスタ化を利用し、そしてそれによって特定の例（テレビ番組）が部分的に多くのクラスタに属することを可能にする。ファジーなクラスタ化方法においては、テレビ番組は重みづけが割り当てられ、そしてそれはテレビ番組がどの程度クラスタ平均値に近いかを表す。重みづけはクラスタ平均値からのテレビ番組の距離の逆２乗に従属し得る。単一のテレビ番組に関係するクラスタ重みづけ全部の和は１００％になるはずである。
【００３０】
クラスタの記号的平均値の算定
図5は本発明の特徴を組み込んだ平均値算定ルーチン500の例示的実施形態を説明する流れ図である。上記のように、平均値算定ルーチン500はクラスタ化ルーチン400によって呼び出されてクラスタの記号的平均値を算定する。数値データについては、平均値は分散値を最小化する値である。この考え方を記号的データにまで広げることによって、クラスタの平均値を、クラスタ内分散値（したがってクラスタの半径又は領域）を最小化する、xμの値を見出すことによって特定し得、
【００３１】
【数１】
2005509967.tif 000003
【００３２】
【数２】
2005509967.tif 000004
で、Jは同様のクラス（視聴又は非視聴）からのテレビ番組のクラスタで、ｘiは番組iについての記号的特徴値で、xμはVar(J)を最小化するような、Jにおけるテレビ番組の１つからの特徴値である。
【００３３】
したがって、図５に表すように、平均算定ルーチン500は、工程510中に、最初に現在特定クラスタJにある番組を特定する。対象の現時の記号的属性について、工程520中で、クラスタの分散値が式(1)を用いて、考えられる各記号的値xμについて算定される。分散値を最小化する記号的値xμが工程530中に平均値として選定される。
【００３４】
工程540中に考慮する記号的属性が更にあるかを判定するテストを行う。工程540中で考慮する記号的属性が更にあると判定された場合、プログラム制御は工程520に戻って上記に説明した方法によって続行する。しかしながら、工程540中で、考慮する記号的属性が更にないと判定された場合、プログラム制御はクラスタ化ルーチン400に戻る。
【００３５】
算定上、Jにおける各記号的特徴値はｘμとして試されて分散値を最小化する記号的値がクラスタJにおける対象記号的属性の平均値となる。2つの種類の平均値、すなわち、特徴ベースの平均値と番組ベースの平均値との算定が考えられる。
【００３６】
特徴ベースの記号的平均値
ここに説明する例示的平均値算定ルーチン500は特徴ベースであり、結果として生じるクラスタ平均値はクラスタJにおける例（番組）から取り出された特徴値を有するが、それは記号的属性の平均値がその考えられる値の１つでなければならないからである。しかしながら、クラスタ平均値は「仮想の」テレビ番組であり得ることを特筆する。この仮想番組の特徴値は例の１つ（例えば、「EBC」）から取り出されたチャンネル値と別の例（例えば、現実には「EBC」では放送されない「BBCワールド・ニュース」）から取り出された題名値を有し得る。したがって、最小分散値を表す如何なる特徴値をもその特徴の平均値を表すよう選定される。平均値算定ルーチン500は、工程540中に、全ての特徴位置について、全ての特徴（すなわち、記号的属性）が考慮されたことが判定されるまで、繰り返される。そのようにして取得された、結果として生じる仮想の番組はクラスタの平均値を表すのに用いられる。
【００３７】
番組ベースの記号的平均値
別の変形例においては、分散値についての式(1)において、xiはテレビ番組i自体であり得、同様にxμは、クラスタJ中の番組群における分散値を最小化する、クラスタJ中の番組である。この場合においては、個別の特定値間ではなく番組間の距離が最小化するのに適切なメトリックである。更に、この場合において結果として生じる平均値は仮想的な番組ではなくて、ちょうどJ群から選ばれた番組である。そのようにしてクラスタJ中で見出された、クラスタJ中の番組全てにおける分散値を最小化する、如何なる番組をもクラスタの平均値を表すのに用い得る。
【００３８】
複数の番組を用いた記号的平均値
上記の例示的平均値算定ルーチン500は、（特徴ベースの実施形態か番組ベースの実施形態かにかかわらず）考えられる各特徴について単一の特定値を用いてクラスタの平均値を特徴付ける。しかしながら、平均値算定中に各特徴について１つの特徴値のみに依存することは、平均値がクラスタについての典型的クラスタ中心ではもはやないので、不適切なクラスタ化につながることが多いことが判った。すなわち、1つの番組のみでクラスタを表すのは望ましくないかもしれず、むしろ、平均値又は複数の平均値を表す複数の番組を、クラスタを表すのに利用し得る。したがって、別の変形例においては、クラスタは考えられる各特徴について複数の平均値又は複数の特徴値によって表し得る。したがって、分散値を最小化する、（特徴ベースの記号的平均値についての）Nの特徴又は（番組ベースの記号的平均値についての）Nの番組が工程530中に選定され、Nはクラスタの平均値を表すのに用いられる番組数である。
【００３９】
番組とクラスタとの間の距離の算定
上記のように、距離算定ルーチン600はクラスタ化ルーチン400によって呼び出されてテレビ番組から各クラスタまでどの程度近いかを特定のテレビ番組と特定クラスタの平均値との間の距離に基づいて評価する。算定距離メトリックは標本データ・セットにおけるさまざまな例の間の相違を数量化してクラスタの領域について判定する。利用者プロフィールのクラスタ化を可能するためには、視聴履歴における如何なる２つのテレビ番組の間の距離をも算定する必要がある。一般に、お互いに近いテレビ番組は１つのクラスタに入る傾向がある。ユークリッド距離、マンハッタン距離、及びマハラノビス距離のような、数値ベクトル間の距離を算定する多数の比較的簡単な手法が存在する。既存の距離算定手法は、しかしながら、テレビ番組ベクトルの場合には用いることができないが、これはテレビ番組が主として記号的特徴値を有するからである。例えば、2001年3月22日の午後8時に「EBC」で放送された「悪魔」の一話及び2001年3月25日の午後8時に「FEX」で放送された「サイモンズ」の一話のような２つのテレビ番組は以下の特徴ベクトルを用いて表し得る：
題名：悪魔                題名：サイモンズ
チャンネル：EBC          チャンネル：FEX
放送日：2001年3月22日  放送日：2001年3月25日
放送時間：20：00            放送時間：20：00
明らかに、既知の数値距離メトリックを特徴値「EBC」と特徴値「FEX」との間の距離を算定するのに用いることはできない。値差分メトリック（VDM）は記号的特徴値領域における特徴値間の距離を測定する既存の手法である。VDMの手法は各特徴の考えられる各値についてのインスタンス全ての分類の類似性を考慮する。この方法を用いることによって、特徴の値全ての間の距離を特定するマトリックスが、訓練群における例に基づいて統計的に導き出される。記号的特徴値間の距離を算定するVDM手法は更に詳細に説明されているものがある（例えば、非特許文献１参照。）
本発明は、２つのテレビ番組又は他の対象品目間の特徴値間の距離を算定するのに、VDM手法又はその変形例を利用する。元のVDMは、２つの特徴値間の距離算定において重みづけ項を使用するので、距離メトリックを非対称にする。変形VDM（MVDM）は当該重みづけ項を除外して距離マトリックスを対称にする。記号的特徴値間の距離を算定するMVDM手法の更に詳細な説明をしているものもある（例えば、非特許文献２参照。）
MVDMによれば、V1及びV2の２つの値の間の距離δは、特定の特徴について、
【００４０】
【数３】
2005509967.tif 000005
によって示される。本発明の番組推奨環境においては、MVDM式(3)は、特に「視聴」及び「非視聴」のクラスを扱うよう変換される。
【００４１】
【数４】
2005509967.tif 000006
式(4)においては、V1及びV2は対象とする特徴について考えられる2つの値である。上記の例について続けると、特徴「チャンネル」について、第１値V1は「EBC」に等しくて、第２値V2は「FEX」に等しい。該値の間の距離は当該例が分類される全てのクラスの和である。本発明の例示的番組推奨ツール実施例について適切なクラスは「視聴」及び「非視聴」である。C1iはV1（「EBC」）がクラスi(iはクラス視聴を意味する1に等しい)に分類された回数で、C1(「C1_total」)はV1がデータ・セット中に発生した合計回数である。値「r」は定数で、通常１に設定される。
【００４２】
式(4)によって定義されたメトリックは、全ての分類について同様の相対頻度で発生する場合には、値を相似のものとして特定する。項C1i/C1は、対象とする特徴が値V1を有するとすると、残余中央値がiとして分類される可能性を表す。したがって、２つの値は、該値が考えられる全ての分類について相似の可能性を示す場合、相似である。式(4)は2つの値の間の全体的な相似を、全ての分類においての該値の可能性の差分の和を見出すことによって算定する。２つのテレビ番組の間の距離は２つのテレビ番組ベクトルの対応する特徴値の間の距離の和である。
【００４３】
図７Aは特徴「チャンネル」に関係する特徴値についての距離表の一部である。図７Aは各クラスについての各チャンネル特徴の発生数をプログラム化している。図7Aに表す値は例示的第３者視聴履歴130から取ってきたものである。
【００４４】
図７Bは、MVDM式(4)を用いて、図７Aに表す例示的統計から算定された各特徴値対の間の距離を表示する。直感的に言えば、「EBC」と「ABS」は、大部分はクラス「視聴」において発生し、クラス「非視聴」においては発生しない（「ABS」は「非視聴」の構成部分がわずかにある）ので、お互いに「近い」はずである。図７Bは、「EBC」と「ABS」との間の距離が（非ゼロの）小さな値であることによって、直感を強めるものである。「ASPN」は、一方、大部分がクラス「非視聴」において発生し、したがって、このデータ・セットについては、「EBC」と「ABS」との両方から「遠い」はずである。図７Bは、「EBC」と「ASPN」との間の距離を、2.0の考えられる最大距離に対して、1.895になるようプログラム化される。同様に、「ABS」と「ASPN」との間の距離は1.828の値で高くなっている。
【００４５】
したがって、図６に表すように、距離算定ルーチン600はまず、工程610中で第３者視聴履歴130において番組を特定する。現時の対象番組について、距離算定ルーチン600は式(4)を用いて工程620中に各記号的特徴値の、（平均値算定ルーチン500によって判定された）各クラスタ平均値に対応する特徴までの、距離を算定する。
【００４６】
現時の番組とクラスタ平均値との間の距離は工程630中に、対応する特徴値間の距離を総計することによって、算定される。工程640中に、第3者視聴履歴130において対象とする番組が更にあるかを判定するテストを行う。工程640中で、第３者視聴履歴130において対象とする番組が更にあると判断された場合、工程650中で次の番組が特定されてプログラム制御は工程620に進んで上記の方法で続行する。
【００４７】
しかしながら、工程640中で第３者視聴履歴130において対象とする番組が更にないと判定された場合、プログラム制御はクラスタ化ルーチン400に戻る。
【００４８】
上記の「複数の番組から導き出された記号的平均値」のように、クラスタの平均値は、（特徴ベースの実施形態か番組ベースの実施形態かにかかわらず）考えられる各特徴についての特徴値数を用いて特徴付け得る。複数の平均値から生じる結果は更に、距離算定ルーチン600の変形例によって投票を通じたコンセンサス決定に達するようプールされる。例えば、今度は工程620中で、番組の特定の特徴値とさまざまな平均値に対応する特徴値の各々との距離が算定される。該最小距離結果はプールされて、例えば、多数決又は専門家をコンセンサス決定に達するよう寄せ集めることによって、投票に用いられる。そのような手法を更に詳細に説明したものもある（例えば、非特許文献３参照。）。
【００４９】
停止基準
上記のように、クラスタ化ルーチン400は、図8に表すように、クラスタ化性能評価ルーチン800を呼び出して、クラスタの生成を停止する基準がいつ充足されたかを判定する。例示的クラスタ化ルーチン400は、ｋの動的値を、例データのクラスタ化を更に行っても分類精度における向上を何らもたらさなくなる際に安定値ｋに達するという条件で、使用する。更に、クラスタ・サイズは、空のクラスタが記録される時点まで増加し得る。したがって、クラスタ化は、クラスタの自然レベルに達した際に停止する。
【００５０】
例示的クラスタ化性能評価ルーチン800は、第３者視聴履歴130からの番組のサブセット（テスト・データ・セット）を用いてクラスタ化ルーチン400の分類精度をテストする。当該テスト・セットにおける各番組について、クラスタ化性能評価ルーチン800は該番組に最も近いクラスタ（どのクラスタ平均値が最も近いか）を判定して、クラスタ及び対象番組についてクラス・ラベルを比較する。整合クラス・ラベルの割合をクラスタ化ルーチン400の精度と解釈する。
【００５１】
このようにして、図８のように、クラスタ化性能評価ルーチン800はまず、工程810中で、第３者視聴履歴130からの番組のサブセットをテスト・データ・セットの役目を担うよう、収集する。その後、クラス・ラベルが各クラスタに対して工程820中に、クラスタ中の視聴および非視聴番組の割合に基づいて割り当てられる。例えば、クラスタ中の番組の大部分が視聴されている場合、該クラスタは「視聴」のラベルが割り当てられる。
【００５２】
テスト・セットにおいて各番組に最も近いクラスタが工程830中に特定されて、割り当てられたクラスタについてのクラス・ラベルが、番組が実際に視聴されたかどうかについて、比較される。クラスタの平均値を表すのに複数の番組を用いた実施形態においては、（各番組までの）平均距離又は投票手法が使用され得る。整合クラス・レベルの割合が、工程840中で、プログラム制御がクラスタ化ルーチン400に戻る前に、判定される。クラスタ化ルーチン400は、分類精度があらかじめ定義された閾値に達した場合、終了する。
【００５３】
ここで表して説明した実施例及び変形例は単に本発明の原理を示すものであって、さまざまな変更が当業者によって、本発明の範囲及び精神から逸脱することなく、実施し得ることを特筆する。
【図面の簡単な説明】
【００５４】
【図１】本発明による、テレビ番組推奨ツールの概略構成図である。
【図２】図１の例示的番組データベースからの見本テーブルである。
【図３】本発明の原理を実施する、図１のステレオタイプ・プロフィール化処理を説明する流れ図である。
【図４】本発明の原理を実施する、図１のクラスタ化ルーチンを説明する流れ図である。
【図５】本発明の原理を実施する、図１の平均値算定ルーチンを説明する流れ図である。
【図６】本発明の原理を実施する、図１の距離算定ルーチンを説明する流れ図である。
【図７Ａ】各クラスについて各チャンネルの特徴値の発生数を示す、例示的チャンネル特徴値発生テーブルからの見本テーブルである。
【図７Ｂ】図７Ａに表す例示的統計から算定された各特徴値対間の距離を示す例示的特徴値対距離テーブルからの見本テーブルである。
【図８】本発明の原理を実施する、図１のクラスタ化性能評価ルーチンを説明する流れ図である。
【図１】
2005509967.tif 000007
【図２】
2005509967.tif 000008
【図３】
2005509967.tif 000009
【図４】
2005509967.tif 000010
【図５】
2005509967.tif 000011
【図６】
2005509967.tif 000012
【図７Ａ】
2005509967.tif 000013
【図７Ｂ】
2005509967.tif 000014
【図８】
2005509967.tif 000015
【国際調査報告】
2005509967.tif 000016
2005509967.tif 000017
2005509967.tif 000018