(57)【要約】視聴履歴の標本母集団からステレオタイプを導出するクラスタリング処理のための可能な初期クラスタ集合は、各候補クラスタ集合に対して、候補クラスタ集合内の各クラスタから候補クラスタ集合内の各他のクラスタへの距離に関するメトリックを計算することによって比較される。望ましくは、候補初期クラスタ集合内のクラスタ間の距離の正規化された平均総計であるメトリックは、互いに対して近すぎるクラスタを有する劣った候補を廃棄するのに用いられる。【特許請求の範囲】
【請求項１】
視聴履歴の標本母集団に対応する複数の候補初期クラスタ集合を受信し、各候補クラスタ集合に対して、特定の候補クラスタ集合内の各クラスタから当該特定の候補クラスタ集合内の各他のクラスタへの距離に関するメトリックを計算する制御器を有する、
初期クラスタ集合を評価するシステム。
【請求項２】
前記メトリックは、候補初期クラスタ集合内のクラスタ間の距離の正規化された平均総計である、請求項１記載のシステム。
【請求項３】
前記メトリックは、総計された値の個数について正規化された候補初期クラスタ集合内の各クラスタについての全ての総計されたクラスタ間距離の和に等しい平均クラスタ間正規化距離である、請求項２記載のシステム。
【請求項４】
前記制御器は、前記メトリックに基づいて、劣った候補初期クラスタ集合を棄却する、請求項１記載のシステム。
【請求項５】
前記視聴履歴の標本母集団から推奨システム内のユーザプロファイルを初期的に集めるためにステレオタイプを導出するクラスタリング処理において用いられるべき前記初期クラスタ集合は、前記メトリックに基づいて選択される、請求項１記載のシステム。
【請求項６】
初期クラスタ集合を評価するシステムであって、
視聴履歴の標本母集団を含み、１つ又はそれ以上のステレオタイプを選択的に受信するよう適合されたメモリと、
前記メモリに通信可能に結合され、前記視聴履歴の標本母集団を受信する制御器とを含み、
前記制御器は、視聴履歴の標本母集団に対応する複数の候補初期クラスタ集合を決定し、
各候補初期クラスタ集合に対して、特定の候補クラスタ集合内の各クラスタから当該特定の候補クラスタ集合内の各他のクラスタへの距離に関するメトリックを計算し、
前記メトリックに基づいて１つ又はそれ以上の候補初期クラスタ集合を選択し、
前記１つ又はそれ以上の選択された候補初期クラスタ集合で初期化されたクラスタリング処理を用いて前記視聴履歴の標本母集団から１つ又はそれ以上のステレオタイプを導出する、システム。
【請求項７】
前記メトリックは、候補初期クラスタ集合内のクラスタ間の距離の正規化された平均総計である、請求項６記載のシステム。
【請求項８】
前記メトリックは、総計された値の個数について正規化された候補初期クラスタ集合内の各クラスタについての全ての総計されたクラスタ間距離の和に等しい平均クラスタ間正規化距離である、請求項７記載のシステム。
【請求項９】
前記制御器は、前記メトリックに基づいて、劣った候補初期クラスタ集合を棄却する、請求項６記載のシステム。
【請求項１０】
前記クラスタリング処理によって導出されたステレオタイプは、推奨システムにおいてユーザプロファイルを初期的に集めるために選択的に用いられる、請求項６記載のシステム。
【請求項１１】
視聴履歴の標本母集団に対応する複数の候補初期クラスタ集合を受信する段階と、
各候補クラスタ集合に対して、特定の候補クラスタ集合内の各クラスタから当該特定の候補クラスタ集合内の各他のクラスタへの距離に関するメトリックを計算する段階とを有する、
初期クラスタ集合を評価する方法。
【請求項１２】
特定の候補クラスタ集合内の各クラスタから当該特定の候補クラスタ集合内の各他のクラスタへの距離に関するメトリックを計算する段階は、
候補初期クラスタ集合内のクラスタ間の距離の正規化された平均総計を更に含む、請求項１１記載の方法。
【請求項１３】
特定の候補クラスタ集合内の各クラスタから当該特定の候補クラスタ集合内の各他のクラスタへの距離に関するメトリックを計算する段階は、
総計された値の個数について正規化された候補初期クラスタ集合内の各クラスタについての全ての総計されたクラスタ間距離の和に等しい平均クラスタ間正規化距離を計算する段階を更に含む、請求項１２記載の方法。
【請求項１４】
前記メトリックに基づいて、劣った候補初期クラスタ集合を棄却する段階を更に含む、請求項１１記載の方法。
【請求項１５】
前記視聴履歴の標本母集団から推奨システム内のユーザプロファイルを初期的に集めるためにステレオタイプを導出するクラスタリング処理において用いられるべき前記初期クラスタ集合を、前記メトリックに基づいて選択する段階を更に含む、請求項１１記載の方法。
【請求項１６】
視聴履歴の標本母集団に対応する複数の候補初期クラスタ集合から、各候補クラスタ集合に対して、特定の候補クラスタ集合内の各クラスタから当該特定の候補クラスタ集合内の各他のクラスタへの距離に関するメトリックを計算することにより導出される、少なくとも１つのステレオタイプを含む、信号。
【請求項１７】
前記メトリックは、候補初期クラスタ集合内のクラスタ間の距離の正規化された平均総計である、請求項１６記載の信号。
【請求項１８】
前記メトリックは、総計された値の個数について正規化された候補初期クラスタ集合内の各クラスタについての全ての総計されたクラスタ間距離の和に等しい平均クラスタ間正規化距離である、請求項１７記載の信号。
【請求項１９】
前記メトリックに基づいて確認された劣った候補初期クラスタ集合は、前記少なくとも１つのステレオタイプの導出中に棄却される、請求項１６記載の信号。
【請求項２０】
前記視聴履歴の標本母集団から推奨システム内のユーザプロファイルを初期的に集めるためにステレオタイプを導出するクラスタリング処理において用いられる前記初期クラスタ集合は、前記メトリックに基づいて選択され、前記少なくとも１つのステレオタイプは、推奨システム内でユーザプロファイルを最初に集めるために選択的に使用されうる、請求項１６記載の信号。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、概して、推奨システム用の初期ユーザプロファイルとしてのステレオタイプを形成することに関連し、より特定には、クラスタリングによりステレオタイプを形成するための初期クラスタの選択に関連する。
【背景技術】
【０００２】
ガイド又は特定の活動に関連して利用可能なオプションに関する情報を発生するのに用いられるシステムは、ユーザに対する提案又は推奨情報を発生しうる。かかるシステムの例は、オンライン・ショッピング又は情報検索システム、並びに、特にオーディオ又はビデオ番組、ゲーム等の娯楽コンテンツであるコンテンツの配信のためのシステムを含む。娯楽コンテンツを配信するシステムの場合、自動アクションは、娯楽コンテンツがユーザによって利用されていない間に、利用可能な娯楽コンテンツの少なくとも一部を後のユーザへの提示のためにキャッシュすることといった、提案又は推奨情報の発生によりトリガされうる。
【０００３】
提案又は推奨情報を発生するとき、少なくとも部分的に、好むか好まないかについての明示的なユーザプロファイルを用いることにより、最適な結果が最もよく得られる。一般的には、かかる明示的なユーザプロファイルは、ユーザがプロファイル作成用アンケートにアクセスし全ての項目を記入したときに生成され、そのアンケートではユーザは（ビデオコンテンツの場合は）ジャンル、俳優、監督、タイトル等の様々なメタデータ記述子を評価している。
【０００４】
明示的なユーザプロファイルを集め又は発展させていくことは、一般的にはユーザによって開始されねばならず、しばしばユーザが、俳優の名前やビデオコンテンツのタイトルといったメタデータ記述子の値を個々に入力することを必要とする（又は可能とする）。このことは、ユーザに、プロファイルの作成時に、プロファイルを使用する動作の基礎となるメタデータ記述子の全ての関連のある値を覚えようとすることを強いることとなり、これは困難であるか、そうでなければ不可能である。
【０００５】
他方で、ユーザのプロファイルを作成するためにそこからの選択が行われうる、全ての可能なメタデータ記述子の値をユーザに対して表示することは、一般的には、扱いにくい大きさのリストをユーザが調べねばならないことや、適当な記述子を見逃す危険性がある。特に、クロス・メディア・システム（即ちビデオ、オーディオ、及び／又は、他のコンテンツ）では、ユーザは、何万ものエントリを含むリストから項目を選択及び／又は評価することを要求されるかもしれない。いずれの選択肢も（ユーザが関連のある項目を思い出すことを必要とするもの、又は、ユーザに包括的なリストを提示すること）、又は、２つのアプローチの組合せも、ユーザに対して過度に要求が多く、ユーザが作業に費やそうとするよりも多くの時間を要求し、従って満足のいくものではない。
【０００６】
ユーザプロファイルを初期化するための迅速且つ効果的な技術は、多数のユーザの視聴パターンの解析から得られたステレオタイプを用いるものである。ユーザは、プロファイルを初期化するためにステレオタイプ又は一組のステレオタイプを選択し、その後、ユーザプロファイルをカスタマイズするためにシステムにフィードバックを与える。
【０００７】
ステレオタイプは、クラスタ化アルゴリズムによりユーザのグループの視聴パターン又は履歴から形成されうる。しかしながら、このようにして得られるステレオタイプの質は、用いられるクラスタの初期集合によって左右される。初期のクラスタが遠く離れていればいるほど、クラスタ化処理が安定し、空のクラスタを生じさせない確率が高くなる。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
従って、本願の技術分野では、推奨システムにおいてプロファイルを初期化するためのステレオタイプを発生するときに初期クラスタの質を確実とするシステム及び方法が必要とされる。
【課題を解決するための手段】
【０００９】
従来技術の上述の不利点を克服するために、本発明は、クラスタリング処理を用いて視聴履歴の標本母集団からステレオタイプを導出するシステムにおける使用のために、各候補初期クラスタ集合について計算され、候補初期クラスタ集合内の各クラスタから候補初期クラスタ集合内の各他のクラスタまでの距離に関するメトリックに基づいて、クラスタリング処理のための可能な初期クラスタ集合の比較を提供することを主な目的とする。望ましくは、候補初期クラスタ集合内のクラスタ間の距離の正規化された平均総計であるメトリックは、互いに近すぎるクラスタを有する劣った候補を棄却するのに用いられる。
【００１０】
上述のことは、当業者が以下の本発明の詳細な説明をよりよく理解しうるよう、本発明の特徴及び技術的な利点をやや広く概説したものである。本発明の特許請求の範囲の対象となる本発明の更なる特徴及び利点について以下詳述する。当業者は、開示される概念及び特定の実施例を、本発明の同じ目的を行うために他の構造を変更し設計する基礎として容易に使用しうることを認めるであろう。当業者はまた、かかる同等の構造が、本発明の最も広い形での趣旨及び範囲から逸脱しないことも認識するであろう。
【００１１】
発明を実施するための最良の形態についての以下の説明に進む前に、本願を通じて用いられる幾つかの後又は句の定義について述べておく。「含む」及び「有する」の語、及びそれらの活用形は、制限なしに包含することを意味する。「又は」の語は、包含的であり、及び／又は、を意味する。「に関連する」及び「それに関連する」の句、並びにそれらの活用形は、含む、中に含む、相互に接続される、中に入れる、中に入っている、接続される、結合される、通信可能である、協働する、挟む、並置される、近くにある、固定される、有する、性質を有する等を意味しうる。「制御器」の語は、ハードウエア、ファームウエア、ソフトウエア、又はこれらのうちの少なくとも２つの組合せとして実現される、少なくとも１つの動作を制御するいかなる装置、システム、又はその一部を意味するものとする。尚、任意の特定の制御器に関連付けられる機能は、ローカルに又は遠隔に、中央集中され又は分散されうる。いくつかの語及び句の定義は本願を通じて与えられており、当業者は、いくつかの定義が、かかる定義された語及び句の以前の及び将来の使用に対しての、多くの、そうでなければ殆どの例に与えられることを理解するであろう。
【発明を実施するための最良の形態】
【００１２】
本発明及びその利点のより完全な理解のために、同様の参照符号が同様の要素を示す添付の図面と共に以下の説明を行う。以下に説明する図１乃至図３、並びに、本願明細書において本発明の原理を説明するのに使用する様々な実施例は、例示のためだけのものであって、本発明の範囲をいかなる方法でも制限するものと解釈されるべきではない。当業者は、本発明の原理は任意の適当な構成の装置によって実施されうることを理解するであろう。
【００１３】
図１は、本発明の１つの実施例による推奨システムユーザプロファイルを初期化するためのステレオタイプを形成し与えるシステムを示す。典型的なシステム１００は、推奨システム１０２に通信可能に結合された推奨システムを初期化するのに使用されるステレオタイプを形成し与えるステレオタイプサーバ１０１を含む。推奨システムは、例えば、ビデオ番組受信器、オーディオ受信器、又はセットトップボックス或いはコンピュータ等のインターネットアクセス装置内で実現されうる。
【００１４】
当業者は、ステレオタイプを形成するシステムの完全な構造及び動作については本願には図示又は説明されていないことを認識するであろう。その代わりに、簡単化及び明瞭化のため、本発明に独特な又は本発明の理解に必要なシステムの構造及び動作についてのみ図示し説明する。システムの構造及び動作の残る部分は、従来技術で公知の従来の構造又は慣例に従ったものでありうる。
【００１５】
図２は、本発明の１つの実施例によるステレオタイプの形成を行うシステム制御器を詳細に示す図である。システム制御器２００用の制御器ハードウエア及びプログラミング２０１は、図１に示すステレオタイプサーバにおいて又は同様の装置で実施されうる。或いは、システム制御器２００によって形成されたステレオタイプを、推奨システムを有する複数の装置の夫々へ伝えるために中間装置（図１には図示せず）が使用されうる。制御器のハードウエア、プログラミング、並びに入力及び出力データの部分２０１は、分散形式で、様々な部分を２つ又はそれ以上の装置内に置いて実施されうる。
【００１６】
システム制御器２００は、どのように実施される場合でも、推奨システムを初期化するのに使用されるべきステレオタイプを形成するアルゴリズム２０２を含み、アルゴリズム２０２は、初期クラスタ選択アルゴリズム２０３及びクラスタリングアルゴリズム２０４を含む。制御器２０１によってアクセス可能なメモリ２０５は、標本母集団についての視聴履歴２０６を含み、形成の後は、視聴履歴から導出されたステレオタイプ２０７を含む。
【００１７】
視聴履歴２０６は、視聴領域内の関連のある母集団についての比較的大きい標本集合を含み、例えば電子番組ガイド等に関連する実際の視聴を追跡することや他の手段により決定されうる２つのクラス、即ち「視聴した」及び「視聴していない」というクラスによって分類される番組を含むと想定される。クラスタは、所定の数の視聴履歴を含む初期のランダムに選択されたクラスタを形成し、次に、同じ訓練集合でテストされたときにクラスタについての推奨パフォーマンスの更なる改善がなくなるまでクラスタをインクリメントすることによって、Ｋ平均計算によって形成される。Ｋ平均クラスタリング処理は、このように連続的な繰り返しでクラスタを改善させる。クラスタリングのためのデータセットは、記号データを有する例を含むため、例とクラスタの間の距離を計算するために値の差のメトリックが用いられる。１つのクラスタリング技術による更なる詳細については、ここに参照として組み入れられる「METHOD  AND  APPARATUS  FOR  RECOMMENDING  ITEMS  OF  INTEREST  BASED  ON  STEREOTYPE  PREFERENCES  OF  THIRD  PARTIES」なる名称の２００１年１１月１２日出願の米国特許出願第１０／０１４，１９５号明細書に記載されている。
【００１８】
上述のように、クラスタリングアルゴリズムは、初期クラスタ集合の質に対して非常に敏感である。初期クラスタ間の距離がより大きいことは、クラスタリング処理の安定性をもたらし、初期クラスタが近すぎる場合に生じうる空のクラスタを回避する可能性が高い。クラスタリング処理は、ランダムに選択された初期クラスタをシードとし、他のクラスタ集合に対して１つのクラスタ集合を選択するためのクラスタリング処理の精度といったメトリックを用いて結果が解析される。しかしながら、かかるアプローチでは、初期クラスタ集合について可能な順列の数が莫大であるために、１つのクラスタがなぜ他のクラスタよりも良いのかに関する解析は非常に困難である。
【００１９】
従って、本発明では、クラスタリングアルゴリズムに入力されうる様々な初期クラスタ集合を比較するためのメトリックが考案された。メトリックは、全てのクラスタ間距離を合計し、その数に達するのに用いた加算の数を正規化することによって得られる。このメトリックは、「悪い」初期クラスタ集合を除去することを意図して、初期クラスタ集合を比較し、クラスタ結果のより効果的な解析を可能とするの使用されうる。
【００２０】
初期クラスタ選択アルゴリズム２０３は、様々な可能なクラスタ集合を比較するために平均クラスタ間正規化距離（average  inter-cluster  normalized  distance）を計算する。可能な初期クラスタＣ０，Ｃ１，Ｃ２，．．．，ＣＮ−１，ＣＮの集合の中にはＮ＋１個のクラスタがあり、全てが要素となる視聴履歴の数に関する閾値要件を満たすと仮定して、各クラスタから他の全てのクラスタへのクラスタ間の距離が計算される。例えば、ｓｕｍ＿Ｃ０は、クラスタＣ０から他の全てのクラスタＣ１乃至ＣＮへの距離であり、即ち、Ｃ０からＣ１への距離にＣ１からＣ２への距離を足すこと等を繰り返したものである。同様に、ｓｕｍ＿Ｃ１は、クラスタＣ１からＣ０への距離にクラスタＣ１からＣ２への距離を足すこと等を繰り返したものである。距離の尺度は、ｋ平均アルゴリズムで一般的に用いられるユークリッド距離式（各属性軸に沿った距離の平方の和の平方根）を使用したものでありうる。望ましくは、自己計算（即ちＣ０からＣ０への距離はゼロ）は回避される。各個々のクラスタについての総和は、Ｎ個の値にわたる総和である。
【００２１】
候補集合内の各クラスタから残る全てのクラスタへのクラスタ間距離が計算されると、全ての個々のクラスタについて計算された値の和が得られる。即ち、値ｓｕｍ＿Ｃ０，ｓｕｍ＿Ｃ１，ｓｕｍ＿Ｃ２，．．．，ｓｕｍ＿ＣＮ−１，ｓｕｍ＿ＣＮは総計され、Ｎ＋１個の数にわたる和である。合計は、総計された値の個数について正規化され、全体の計算は、以下の式、
【００２２】
【数１】
2005531059.tif 000002
によって与えられ、式中、ＡｖｇICNDは候補クラスタ集合に対する平均クラスタ間正規化された距離である。この計算は、全ての候補初期クラスタ集合について繰り返され、計算されたメトリックが比較される。候補初期クラスタ集合について、この比較された計算値が小さければ小さいほど、当該集合内でクラスタは近く、当該候補集合は、クラスタリング処理の初期化については、より大きい平均クラスタ間正規化距離を有する候補初期クラスタ集合よりも劣ったものとなる。従って、視聴履歴の標本母集団からステレオタイプを導出するためにクラスタリング処理を初期化するには、より大きい平均クラスタ間正規化距離を有するクラスタ集合が選択される。
【００２３】
図３は、本発明の１つの実施例による視聴履歴の標本母集団からステレオタイプを導出するクラスタリング処理のために１つ又はそれ以上の可能な初期クラスタ集合を選択する方法についての高水準フローチャートを示す。方法３００は、標本母集団視聴履歴を受信することから開始する（ステップ３０１）。まず、各クラスタ内の標本の数に対する閾値要件を満たす候補初期クラスタ集合の可能な順列が決定される（ステップ３０２）。
【００２４】
候補初期クラスタ集合が選択され、当該候補クラスタ集合に対して平均クラスタ間正規化距離が計算される（ステップ３０３）。次に、全ての候補が処理されるまで、他の候補初期クラスタに対して選択及び計算処理が繰り返される（ステップ３０４）。平均クラスタ間正規化距離が全ての可能な初期クラスタ集合に対して計算されると、計算された距離が比較され、最も悪い候補初期クラスタ集合は棄却される（ステップ３０５）。方法は、視聴履歴の他の標本母集団が受信されるまでアイドル状態となる。
【００２５】
本発明は、推奨システムに用いられるユーザプロファイルを最初に集めるのに用いられる適当なステレオタイプを決定するときに用いられる。ステレオタイプは様々な初期クラスタを試すクラスタリング処理によって決定され、本発明によれば、ステレオタイプを導出するときにどちらの初期クラスタがよいかを決定するときに、有意義な初期クラスタの比較が可能となる。
【００２６】
本発明について、完全に機能的なシステムに関して説明したが、当業者は、本発明の機構の少なくとも一部が様々な形の命令を含む機械によって使用可能な媒体の形で配布されることが可能であり、本発明は配布を実際に行うのに用いられる信号を担持する媒体の特定の種類とは無関係に等しく適用可能であることを認めるであろう。機械によって使用可能な媒体の例は、読み出し専用メモリ（ＲＯＭ）又は消去可能な電気的にプログラマブルな読み出し専用メモリ（ＥＥＰＲＯＭ）といった不揮発性のハードコードされた媒体、フレキシブルディスク、ハードディスクドライブ、及びコンパクトディスク読み出し専用メモリ（ＣＤ−ＲＯＭ）又はディジタル・バーサタイル・ディスク（ＤＶＤ）といった記録可能な種類の媒体、並びに、ディジタル及びアナログ通信リンクといった伝送型の媒体を含む。
【００２７】
本発明について詳細に説明したが、当業者は、本発明の最も広い形の趣旨及び範囲を逸脱することなく、開示された発明の様々な変化、代替、変形、強調、ニュアンス、段階的変化、より小さい形、変更、修正、改善、及び模倣がなされうることを理解するであろう。
【図面の簡単な説明】
【００２８】
【図１】本発明の１つの実施例による推奨システムユーザプロファイルを初期化するためのステレオタイプを形成し与えるシステムを示す図である。
【図２】本発明の１つの実施例によるステレオタイプの形成を行うシステム制御器を詳細に示す図である。
【図３】本発明の１つの実施例による視聴履歴の標本母集団からステレオタイプを導出するクラスタリング処理のための１つ又はそれ以上の可能な初期クラスタ集合を選択する処理の高水準フローチャートである。
【図１】
2005531059.tif 000003
【図２】
2005531059.tif 000004
【図３】
2005531059.tif 000005