在項目推薦器中評估這些項的接近度的方法及裝置的製作方法

2023-05-28 06:42:56 2

專利名稱：在項目推薦器中評估這些項的接近度的方法及裝置的製作方法
技術領域：
本發明與名為「Method and Apparatus for Partitioning aPlurality of Items into Groups of Similar Items in aRecommender of Such Items」(代理人案卷號為US010568)的美國專利申請，名為「Method and Apparatus for Generating AStereotypical Profile for Recommending Items of InterestUsing Item-Based Clustering」(代理人案卷號為US010569)的美國專利申請，名為「Method and Apparatus for Recommending Itemsof Interest Based on Preferences of a Selected Third Party」(代理人案卷號為US010572)的美國專利申請，名為「Method andApparatus for Recommending Items of Interest Based onStereotype Preferences of Third Parties」(代理人案卷號為US010575)的美國專利申請，以及名為「Method and Apparatus forGenerating A Stereotypical Profile for Recommending Items ofInterest Using Feature-Based Clustering」(代理人案卷號為US010576)的美國專利申請相關，每一件均同此發明同時申請，均被轉讓給本發明的受讓人，並在此併入作為參考。
本發明涉及用於推薦感興趣的項，諸如電視節目的方法及裝置，並且更具體地，涉及用於在可得到用戶的購買或觀看歷史記錄之前推薦感興趣的節目或其它項的技術。
隨著電視觀眾可用的頻道數目增多，以及存在於這些頻道上的節目的多樣性，對於電視觀眾來說，識別感興趣的電視節目已經日益變得複雜。電子節目嚮導(EPG)通過例如，名稱、時間、日期以及頻道來識別有用的電視節目，以及通過允許依照個性化的偏好搜尋或分類有用的電視節目來方便對感興趣節目的識別。
許多推薦工具已經被計劃或建議用來推薦感興趣的電視節目或其它項目。電視節目推薦工具例如將觀眾偏好應用於EPG以得到一組對於一特定觀眾可能是感興趣的推薦節目。一般地，電視節目推薦工具使用隱含的或明顯的技術，或是使用上述技術的一些組合來獲得觀眾的偏好。隱含的電視節目推薦工具以不強迫別人接受的方式，根據從觀眾的觀看歷史記錄得到的信息生成電視節目推薦。另一方面，明顯的電視節目推薦工具明確地詢問觀眾有關他們對於節目屬性，諸如名稱、類型、演員、頻道以及日期/時間的偏好，以得出觀眾簡表並生成推薦。
雖然當前可用的推薦工具協助用戶來識別感興趣的項目，但是它們也受到許多限制，如果它們克服了這些限制，將會很大地改進這些推薦工具的便利性和性能。例如，為了成為綜合性質的，明顯的推薦工具的初始化非常冗長，需要每一個新用戶回答有關在粗粒度級上指定他們的偏好的非常詳細的調查。雖然隱含的電視節目推薦工具通過觀察觀看行為而不引人注目地得到一個簡表，但是它們需要長的時間來變得準確。另外，這些隱含的電視節目推薦工具至少需要一最小數量的觀看歷史記錄以便開始做出任何推薦。因此，在當第一次獲得推薦工具時，這些隱含的電視節目推薦工具並不能夠做出任何推薦。
因此，需要一種能夠在可得到足夠的個性化的觀看歷史記錄之前，不引人注意地推薦諸如電視節目的項目的方法及裝置。另外，需要一種根據第三方的觀看習慣來為一給定的用戶生成節目推薦的方法及裝置。
總體上，公開了一種向用戶推薦感興趣的項目，諸如電視節目推薦的方法及裝置。根據本發明的一個方面，在可得到用戶的觀看歷史記錄或購買歷史記錄之前-諸如在當用戶第一次獲得推薦器時生成推薦。最初，採用來自一個或多個第三方的觀看歷史記錄或購買歷史記錄來向特定用戶推薦感興趣的項目。
處理第三方觀看或購買歷史記錄以生成反映由有代表性的觀眾所選定項目的典型樣式的定型簡表(stereotype profile)。每個定型簡表都是在某些方面彼此相類似的項目(數據點)的一個群(claster)。用戶選擇感興趣的定型以便用最接近他或她自己的興趣的項目來初始化他或她的簡表。
聚類例程把第三方觀看或購買歷史記錄(數據集)劃分成群，以使得在一個群內的點(例如，電視節目)比其它任何群更接近該群的平均值(mean)。還公開了用於計算一個群的符號平均值的平均值計算例程。利用各個群的平均值，根據數據點至各個群之間的距離來把諸如電視節目的給定數據點分配給群。
所公開的距離計算例程根據給定電視節目與給定群的平均值之間的距離來評估電視節目與各個群的接近度。計算出的距離量度量化在樣本數據集內的各種例子之間的差別以確定一個群的範圍。採用值差量度(VDM)技術或其變更來計算兩個電視節目之間的特徵值之間的距離。根據已知的修改的VDM(MVDM)技術，用下式給出對於特定特徵的兩個值之間的距離δδ(V1，V2)＝∑|C1i/C1-C2i/C2|r其中V1和V2是對於考慮中的特徵的兩個可能的值。在說明性實施例的節目推薦環境中，感興趣的類別為「被觀看」和「未被觀看」。一般地，所公開的距離計算例程在如果這些值對於所有的分類都以相同的相對頻率出現時，就將這些值看作是相似的。
通過參照下面的詳細描述以及附圖將獲得對本發明以及本發明的進一步的特徵和優點的更完全理解。


圖1是本發明的電視節目推薦器的示意框圖；圖2是取自圖1的示例性節目資料庫的樣本表；圖3是描述具體化本發明原理的圖1的定型簡表處理的流程圖；圖4是描述具體化本發明原理的圖1的聚類例程的流程圖；圖5是描述具體化本發明原理的圖1的平均值計算例程的流程圖；圖6是描述具體化本發明原理的圖1的距離計算例程的流程圖；圖7A是取自示例性頻道特徵值出現表的一樣本表，該示例性頻道特徵值出現表表示對於各個類別的各個頻道特徵值的出現數目；圖7B是取自示例性特徵值對距離表的一樣本表，該示例性特徵值對距離表表示從圖7A所示的示例性計數計算出的各個特徵值對之間的距離；以及圖8是描述具體化本發明原理的圖1的聚類性能評估例程的流程圖。
圖1說明了本發明的電視節目推薦器100。如圖1所示，該示例性電視節目推薦器100評估如在下面結合圖2所論述的節目資料庫200內的節目以識別特定觀眾感興趣的節目。能夠例如使用採用眾所周知的屏上呈現技術的頂置終端/電視(未示出)來把一組推薦節目呈現給觀眾。雖然這裡是在電視節目推薦的上下文中說明了本發明，但是本發明能夠應用於任何根據用戶行為，諸如觀看歷史記錄或購買歷史記錄而自動生成的推薦。
根據本發明的一個特徵，電視節目推薦器100能夠在用戶的觀看歷史記錄140可得到之前，諸如當用戶第一次得到該電視節目推薦器100時生成電視節目推薦。如圖1所示，電視節目推薦器100最初採用來自一個或多個第三方的觀看歷史記錄130來推薦特定用戶感興趣的節目。一般地，該第三方觀看歷史記錄130是基於具有代表大量人數的人口統計狀況，諸如年齡、收入、性別及教育的一個或多個採樣人數的觀看習慣。
如圖1所示，第三方觀看歷史記錄130由一組被給定人數觀看以及未被給定人數觀看的節目組成。通過觀察被該給定人數實際觀看的節目來獲得被觀看的該組節目。通過例如隨機採樣節目資料庫200內的節目來獲得未被觀看的該組節目。在一進一步的變更中，根據序列號為No.09/819,286、申請日為2001年3月28日、名稱為「AnAdaptive Sampling Technique for Selecting Negative Examplesfor Artifical Intelligence Applications」的美國專利申請的教導來獲得未被觀看的該組節目，該篇申請被轉讓給本發明的受讓人並在此併入作為參考。
根據本發明的另一個特徵，電視節目推薦器100處理第三方觀看歷史記錄130以生成反映由有代表性的觀眾所觀看的電視節目的典型樣式的定型簡表。如下面進一步論述的，定型簡表是在某些方面彼此相似的電視節目(數據點)的群。因而，一給定的群對應於取自展示特定樣式的第三方觀看歷史記錄130的一特殊片段的電視節目。
根據本發明來處理第三方觀看歷史記錄130以提供展示某些特定樣式的節目群。此後，用戶能夠選擇最相關的定型並因此用與他或她自己的興趣最接近的節目來初始化他或她的簡表。然後根據每個單獨用戶他們自己的記錄樣式以及給予節目的反饋，該定型的簡表調整並向每個單獨用戶的特定的、個人觀看行為發展。在一實施例中，當確定節目得分時，可以對取自用戶自己的觀看歷史記錄140的節目比取自第三方觀看歷史記錄130的節目給予更高的加權。
電視節目推薦器100可以具體化為任何計算設備，諸如個人計算機或工作站，其含有諸如中央處理單元(CPU)的處理器115，以及諸如RAM和/或ROM的存儲器120。電視節目推薦器100還可以具體化為例如在頂置終端或顯示器(未示出)內的專用集成電路(ASIC)。另外，電視節目推薦器100可以具體化為任何可得到的電視節目推薦器諸如從加利福尼亞桑尼維爾的Tivo有限公司商業地可購買到的TivoTM系統，或者是在序列號為No.09/466,406、申請日為1999年12月17日、名稱為「Method and Apparatus for Recommending TelevisionProgramming Using Decision Trees」的美國專利申請，序列號為No.09/498,271、申請日為2000年2月4日、名稱為「Bayesian TVShow Recommender」的美國專利申請，以及序列號為No.09/627,139申請日為2000年7月27日、名稱為「Three-Way MediaRecommendation Method and System」的美國專利申請，或它們的任何組合中描述的電視節目推薦器，每一種都在這裡被併入作為參考，按照這裡所修改的以完成本發明的特徵和功能。
如圖1所示以及在下面結合圖2-8進一步論述的，電視節目推薦器100包括節目資料庫200、定型簡表過程300、聚類例程400、平均值計算例程500、距離計算例程600以及聚類性能評估例程800。一般地，節目資料庫200可以具體化為眾所周知的電子節目嚮導並可以為在給定時間間隔內可用的每個節目記錄信息。定型簡表過程300(i)處理第三方觀看歷史記錄130以生成反映有代表性的觀眾所觀看的電視節目的典型樣式的定型簡表；(ii)允許用戶選擇最為相關的定型並因此初始化他或她的簡表；以及(iii)基於選定的定型生成推薦。
由定型簡表過程300調用聚類例程400以把第三方觀看歷史記錄130(數據集)劃分成群，以使在一個群內的點(電視節目)比其它任何群更接近該群的平均值(質心)。聚類例程400調用平均值計算例程500以計算一個群的符號平均值。由聚類例程400調用距離計算例程600以根據在給定電視節目與給定群的平均值之間的距離來評估一電視節目與各個群的接近度。最後，聚類例程400調用聚類性能評估例程800以確定何時已滿足用於創建群的停止標準。
圖2是取自圖1的節目資料庫(EPG)200的樣本表。如先前指出的，節目資料庫200為在給定時間間隔內可用的各個節目記錄信息。如圖2所示，節目資料庫200含有諸如記錄205-220條的多條記錄，每一條記錄都與一給定的節目有關。對於每個節目，節目資料庫200分別在欄240及欄245內表示出與該節目有關的日期/時間以及頻道。另外，分別在欄250、255和270內為各個節目標識出名稱、類型以及演員。另外的眾所周知的特徵(未示出)-諸如節目的持續時間以及說明也能夠包含在節目資料庫200內。
圖3是描述結合了本發明特徵的定型簡表過程300的示例性實現的流程圖。如先前指出的，定型簡表過程300(i)處理第三方觀看歷史記錄130以生成反映有代表性的觀眾所觀看的電視節目的典型樣式的定型簡表；(ii)允許用戶選擇最為相關的定型並因此初始化他或她的簡表；以及(iii)基於選定的定型生成推薦。注意，可以例如，在工廠內脫機執行對第三方觀看歷史記錄130的處理，並且能夠向用戶提供安裝了所生成的定型簡表以由用戶進行選擇的電視節目推薦器100。
因而，如圖3所示，定型簡表過程300一開始在步驟310期間收集第三方觀看歷史記錄130。此後，定型簡表過程300在步驟320期間執行下面結合圖4所論述的聚類例程400以生成相應於定型簡表的節目群。如下面進一步論述的，該示例性的聚類例程400可以對觀看歷史記錄數據集130採用一種無監督數據聚類算法，諸如「k-平均值」聚類例程。如先前指出的，聚類例程400把第三方觀看歷史記錄130(數據集)劃分成群，以使一個群內的點(電視節目)比其它任何群更接近該群的平均值(質心)。
然後，定型簡表過程300在步驟330期間把表徵每個定型簡表的一個或多個標籤分配給每個群。在一示例性的實施例中，該群的平均值變成為對於整個群的有代表性的電視節目，並且該平均值節目的特徵能夠用於標記該群。例如，電視節目推薦器100能夠被配置成使得類型對每個群是主要因素或是定義特徵。
在步驟340期間，把被標記的定型簡表呈現給每個用戶以便選擇最接近該用戶的興趣的定型簡表。組成每個選定群的節目能夠被視為那個定型的「典型觀看歷史記錄」，並且能夠被用來為每個群建造一定型簡表。因而，在步驟350期間為用戶生成觀看歷史記錄，該記錄由來自選定定型簡表的節目組成。最後，在步驟360期間把在上一步驟生成的觀看歷史記錄加到節目推薦器上以得到節目推薦。節目推薦器可以具體化為任何常規的節目推薦器，諸如上面所涉及的那些推薦器，雖然在這裡進行了修改，但是對於本領域內的那些普通技術人員來說是顯而易見的。在步驟370期間程序控制終止。
圖4是描述結合了本發明特徵的聚類例程400的示例性實現的流程圖。如先前指出的，由定型簡表過程300在步驟320期間調用聚類例程400來把第三方觀看歷史記錄130(數據集)劃分成群，以使一個群內的點(電視節目)比其它任何群更接近該群的平均值(質心)。一般地，到聚類例程集中於在一樣本數據集內尋找例子分組的無監督任務。本發明使用k-平均值聚類算法來把數據集劃分成k個群。如下文論述的，聚類例程400的兩個主要參數是(i)用於尋找最接近的群的距離量度，在下面結合圖6進行論述；以及(ii)k，要創建的群的數目。
該示例性的聚類例程400採用動態值k，具有這樣的條件，即，當示例數據的進一步聚類在分類精度上沒有產生任何改進時已經達到一穩定的k。另外，群的大小被遞增到空群所被記錄的那個點。因此，當已經達到這些群的平常水平時，聚類停止。
如圖4所示，聚類例程400一開始在步驟410期間建立k個群。該示例性的聚類例程400通過選擇最小數目的群，比如說兩個而開始。對於這一固定的數目，聚類例程400處理整個觀看歷史記錄數據集130並且通過數次重複，到達可以被看作是穩定的兩個群(即，沒有節目將從一個群移到另一個群，即使該算法將經歷另一次重複)。在步驟420期間用一個或多個節目來初始化當前的k個群。
在一示例性的實現中，在步驟420期間，用從第三方觀看歷史記錄130中選出的一些種子節目來初始化這些群。可以隨機地或是順序地選擇用於初始化這些群的節目。在順序實現中，可以用從觀看歷史記錄130內的第一個節目開始的那些節目來初始化這些群，或是用起始於觀看歷史記錄130內的任意一點的那些節目來初始化這些群。在再一種變更中，初始化各個群的節目數目還可以被改變。最後，用一個或多個「假定的」節目來初始化這些群，這些「假定的」節目由從第三方觀看歷史記錄130內的節目中隨機選取的特徵值組成。
此後，聚類例程400在步驟430期間啟動平均值計算例程500以計算各個群的當前平均值，將在下面結合圖5論述平均值計算例程500。然後，聚類例程400在步驟440期間執行距離計算例程600以確定在第三方觀看歷史記錄130內的各個節目與各個群之間的距離，將在下面結合圖6論述距離計算例程600。然後，在步驟460期間，把觀看歷史記錄130內的各個節目分配給最接近的群。
在步驟470期間，執行測試以確定是否有節目已經從一個群移到了另一個群。如果在步驟470期間確定一節目已從一個群移到了另一個群，則程序控制返回到步驟430並按照上述方式繼續，直到識別出一組穩定的群。而如果在步驟470期間確定沒有節目從一個群移到了另一個群，則程序控制進到步驟480。
在步驟480期間執行進一步的測試以確定是否已滿足特定的性能標準，或是是否識別出空的群(總稱為「停止標準」)。如果在步驟480期間確定尚未滿足停止標準，則在步驟485期間遞增k的值，並且程序控制返回到步驟420並按照上述方式繼續。而如果在步驟480期間確定已滿足停止標準，則程序控制終止。將在下面結合圖8進一步論述該停止標準的評估。
該示例性的聚類例程400把節目只放到一個群內，從而創建所謂的「脆」(crisp)群。進一步的變更將會採用模糊聚類，其允許一特殊的例子(電視節目)部分地屬於許多個群。在模糊聚類方法中，給電視節目分配加權，該加權表示了電視節目到群平均值有多近。該加權能夠視該電視節目與群平均值之間的距離的二次方的倒數而定。與單個電視節目有關的所有群的加權的總和必須總計為100％。
群的符號平均值的計算圖5是描述結合了本發明特徵的平均值計算例程500的示例性實現的流程圖。如先前指出的，由聚類例程400調用平均值計算例程500來計算一個群的符號平均值。對於數字數據，該平均值是最小化方差的一個值。把這一概念擴展到符號數據，能夠通過尋找最小化群內方差的xμ值來確定一個群的平均值(並因此確定此群的半徑或範圍)。
Var(J)＝∑i∈J(xi-xμ)2(1)群半徑R(J)=Var(J)---(2)]]>其中J是一個源自同一類(被觀看或未被觀看)的電視節目群，xi是對應演出i的符號特徵值，xμ是來自J內的其中一個電視節目的特徵值以使它最小化Var(J)。
因此，如圖5所示，平均值計算例程500一開始在步驟510期間識別當前處於一給定群J內的節目。對於正在考慮中的該當前的符號屬性，在步驟520期間使用等式(1)來為每個可能的符號值xμ計算群J的方差。在步驟530期間，將最小化該方差的符號值xμ選作為平均值。
在步驟540期間執行測試以確定是否存在需要考慮的另外的符號屬性。如果在步驟540期間確定了存在需要考慮的另外的符號屬性，則程序控制返回到步驟520並按照上述方式繼續。而如果在步驟540期間確定了沒有需要考慮的另外的符號屬性，則程序控制返回到聚類例程400。
在計算上，J內的每個符號特徵值都被嘗試作為xμ，並且最小化該方差的符號值變成為群J內的考慮中的符號屬性的平均值。有兩種可能的平均值計算類型，稱為基於顯示的平均值以及基於特徵的平均值。
基於特徵的符號平均值這裡論述的示例性平均值計算例程500為基於特徵的，其中結果群平均值由從群J內的例子(節目)中抽取出的特徵值組成，這是因為符號屬性的平均值必須是符號屬性的可能的值之一。然而需要注意，群平均值可以是「假定的」電視節目，這一點很重要。該假定節目的特徵值可以包括從這些例子之一(比方說，EBC)抽取出的頻道值，以及從這些例子中的另外一個(比方說，BBC世界新聞，實際上它從未在EBC上播出)抽取出的名稱值。因此，展示最小方差的任何一個特徵值被選定用來代表那一個特徵的平均值。對於所有特徵位置，重複平均值計算例程500，直到在步驟540期間確定了所有特徵值(即，符號屬性)已經被考慮。由此得到的結果假定節目被用來代表此群的平均值。
基於節目的符號平均值在一進一步的變更中，在用於方差的等式(1)中，xi可以是電視節目i本身，以及類似地，xμ可以是群J內的、最小化群J內節目組上的方差的節目。在此情形中，這些節目之間的、而不是單獨的特徵值之間的距離是要被最小化的相關量度。另外，在此情形中的結果平均值不是假定的節目，而正是從集合J中選出的一個節目。在群J內如此找到的、最小化群J內的所有節目上的方差的任何一個節目被用來代表此群的平均值。
使用多個節目的符號平均值上面論述的示例性平均值計算例程500使用用於各個可能的特徵的一個單獨的特徵值表徵了一個群的平均值(不論是按照基於特徵的實現，還是按照基於節目的實現)。然而已經發現，在平均值計算期間僅僅依靠用於各個特徵的一個特徵值常常會導致不適當的聚類，這是由於該平均值不再是這個群的代表性的群中心。換言之，可能不希望僅僅用一個節目來代表一個群，而是可以用表示平均值或是多個平均值的多個節目代表一個群。因此，在一進一步的變更中，可以用多個平均值或是對於各個可能特徵的多個特徵值來代表一個群。因而，在步驟530期間選擇最小化方差的N個特徵值(對應基於特徵的符號平均值)或N個節目(對應基於節目的符號平均值)，其中N是用來代表一個群的平均值的節目數。
節目與群之間的距離計算如先前指出的，由聚類例程400調用距離計算例程600以根據給定的電視節目與給定群的平均值之間的距離來評估電視節目與各個群的接近度。計算出的距離量度量化樣本數據集內的各種例子之間的差別以確定一個群的範圍。為了能夠聚類用戶簡表，必須計算在觀看歷史記錄內的任何兩個電視節目之間的距離。一般地，彼此接近的電視節目趨向於落入一個群內。存在許多相對簡單的技術用來計算數字值向量之間的距離，諸如歐幾裡德距離，曼哈頓距離，以及馬哈拉諾比斯距離。
然而現有的距離計算技術不能用在電視節目向量的情形中，這是因為電視節目主要是由符號特徵值組成。例如，能夠用下面的特徵向量來表示兩個電視節目，諸如2001年3月22日晚上8點EBC播出的「朋友」劇目，以及2001年3月25日晚上8點FEX播出的「西蒙一家」劇目名稱朋友 名稱西蒙一家頻道EBC頻道FEX播出日期2001-03-22 播出日期2001-03-25播出時間2000 播出時間2000
顯然，已知的數字距離量度不能用來計算特徵值「EBC」與「FEX」之間的距離。值差量度(VDM)是用於測量符號特徵值域內的特徵值之間的距離的現有技術。VDM技術考慮對於各個特徵的每個可能的值的所有例子的總體分類相似性。使用這一方法，根據訓練集內的例子而統計地導出一個定義所有特徵值之間的距離的矩陣。對於用於計算符號特徵值之間的距離的VDM技術的更為詳細的論述，參見例如ACM通訊，2912，1213-1228(1986)上刊載的由Stanfill與Waltz所著的「Toward Memory-Based Reasoning」一文，在此將其併入作為參考。
本發明採用VDM技術或其變更來計算兩個電視節目之間的、或其它感興趣的項目之間的特徵值之間的距離。最初的VDM建議在兩個特徵值之間的距離計算中採用加權項，這使得距離量度為不對稱的。修改的VDM(MVDM)省略了該加權項以使距離矩陣是對稱的。對於用於計算符號特徵值之間的距離的MVDM技術的更為詳細的論述，參見例如麻薩諸塞州，波士頓，Kluwer出版社(1993)的Machine Learning第10卷，57-58上刊載的由Cost與Salzberg所著的「A WeightedNearest Neighbor Algorithm For Learning With SymbolicFeatures」一文，在此將其併入作為參考。
根據MVDM，用下式給出對於一特定特徵的兩個值，V1與V2之間的距離δδ(V1，V2)＝∑|C1i/C1-C2i/C2|r(3)在本發明的節目推薦環境中，變換MVDM等式(3)專門用來處理「被觀看」和「未被觀看」的類。
(V1,V2)=|C1_watchedC1_total-C2_watchedC2_total|+]]>|C1_not_watchedC1_total-C2_not_watchedC2_total|---(4)]]>在等式(4)中，V1和V2是對於在考慮中的特徵的兩個可能的值。繼續上面的例子，對於特徵「頻道」，第一個值V1等於「EBC」，第二個值V2等於「FEX」。這兩個值之間的距離為這些例子被分類到的所有類別上的總和。對於本發明的該示例性節目推薦器實施例的有關類別為「被觀看」和「未被觀看」。C1i是V1(EBC)被分到類別i(i等於意指被觀看類別的1)的次數，而C1(C1_total)是V1出現於數據集內的總次數。值「r」為常數，通常被設置成1。
在如果這些值對於所有分類都以同一相對頻率出現時，用等式(4)定義的該量度就將這些值看成是相似的。C1i/C1項表示平均值餘數將被分類為i的似然性，假定所討論的這一特徵具有值V1。因此，如果兩個值對所有可能的分類都給出相似的似然性，則這兩個值是相似的。等式(4)通過尋找在所有分類上的這些似然性的差異之和來計算兩個值之間的總相似性。兩個電視節目之間的距離為這兩個電視節目向量的相應特徵值之間的距離的和。
圖7A是用於與特徵「頻道」有關的特徵值的一部分距離表。圖7A規劃對於各個類別的各個頻道特徵值出現的數目。圖7A所示的值是已經從示例性的第三方觀看歷史記錄130中取出的。
圖7B顯示了利用MVDM等式(4)從圖7A所示的示例性計數中計算出的各個特徵值對之間的距離。直觀地，EBC與ABS應該彼此「接近」，因為它們主要出現在被觀看類別中，而不出現在未被觀看類別中(ABS具有少的未被觀看成分)。圖7B用EBC與ABS之間的小的(非零)距離來確認了這一直覺。另一方面，ASPN主要出現在未被觀看類別中並因此應當「遠離」EBC與ABS，對於該數據集。圖7B將EBC與ASPN之間的距離規劃為1.895，處於最大的可能距離2.0之外。類似地，ABS與ASPN之間的距離具有1.828高的一個值。
因此，如圖6所示，距離計算例程600一開始在步驟610期間識別第三方觀看歷史記錄130內的節目。對於正在考慮中的當前節目，距離計算例程600在步驟620期間使用等式(4)來計算各個符號特徵值到各個群平均值(用平均值計算例程500確定)的相應特徵的距離。
在步驟630期間通過合計相應的特徵值之間的距離來計算當前節目與群平均值之間距離。在步驟640期間執行測試以確定在該第三方觀看歷史記錄130內是否有另外的要被考慮的節目。如果在步驟640期間確定了在該第三方觀看歷史記錄130內有另外的要被考慮的節目，則在步驟650期間識別下個節目，並且程序控制進到步驟620並按照上面描述的方式繼續。
而如果在步驟640期間確定了在該第三方觀看歷史記錄130內沒有另外的要被考慮的節目，則程序控制返回到聚類例程400。
如先前在題為「從多個節目導出的符號平均值」的小節內所論述的，可以用許多對於各個可能的特徵的特徵值來表徵一個群的平均值(不論是在基於特徵的實現中，還是在基於節目的實現中)。然後用距離計算例程600的變更來集中來自多平均值得出的結果以通過投票來達成一致的決定。例如，現在在步驟620期間計算一個節目的給定特徵值與對於各種方法的各個相應的特徵值之間的距離。最小距離結果被集中並用於投票，例如通過採用多數投票或專家的混合以便達成一致的決定。對於這些技術的更為詳細的論述，參見例如在第13屆圖案識別國際會議會刊，第II卷，897-901，奧地利，維也納(1996)上刊載的由J.Kittler等人所著的「Combing Classifiers」一文，在此將其併入作為參考。
停止標準如先前指出的，聚類例程400調用圖8所示的聚類性能評估例程800來確定何時已滿足用於創建群的停止標準。該示例性聚類例程400採用動態k值，具有這樣的條件，即，當示例數據的進一步聚類在分類精度上沒有產生任何改進時已經達到一穩定的k。另外，群的大小被遞增到空群所被記錄的那個點。因此，當已經達到這些群的平常水平時，聚類停止。
該示例性聚類性能評估例程800使用第三方觀看歷史記錄130的節目子集(測試數據集)來測試聚類例程400的分類精度。對於該測試集內的每個節目，聚類性能評估例程800確定與其最接近的群(該群的平均值是最接近的)，並比較該群的類別標籤與考慮中的節目。匹配的類別標籤的百分數轉換為聚類例程400的精度。
因此，如圖8所示，聚類性能評估例程800一開始在步驟810期間從第三方觀看歷史記錄130收集節目子集以作為測試數據集。此後，在步驟820期間根據該群內被觀看和未被觀看的節目的百分數而把類別標籤分配給各個群。例如，如果該群內的大多數節目都被觀看了，則可以給這個群分配「被觀看」標籤。
在步驟830期間識別與測試集內的各個節目最接近的群並比較該指定的群的類別標籤以確定該節目是否被實際觀看。在其中用多個節目來代表一個群的平均值的實現中，可以採用平均值距離(到各個節目的)或投票方案。在程序控制返回到聚類例程400之前，在步驟840期間確定匹配的類別標籤的百分數。如果分類精度已達到預定的閾值，則聚類例程400將終止。
應當理解這裡所示出並描述的實施例以及變更僅僅說明本發明的原理，可以由本領域的那些技術人員在不脫離本發明的範圍和精神的情況下來實現各種修改。
權利要求
1.一種用在推薦器(100)內用於評估兩個項(205，210，220)的接近度的方法，所述項(205，210，220)中的每一項都用至少一個符號特徵來表徵，所述方法包括步驟根據對於所述符號特徵值的每個可能值的所有例子的總的分類相似性來計算所述兩個項(205，210，220)的相應的符號特徵值之間的距離；以及合計各個所述符號特徵值之間的距離以確定所述兩個項(205，210，220)的接近度。
2.權利要求1的方法，被安排用於把一項(205，210，220)分配給一組項或多組項，所述項(205，210，220)中的每一項都用至少一個符號特徵來表徵，所述方法包括步驟計算所述項的相應的符號特徵值與各個所述組內的至少一項之間的距離，所述距離是基於對於所述符號特徵值的每個可能值的所有例子的總的分類相似性；合計各個所述特徵值之間的距離以確定所述項與各個所述組內的至少一項之間的接近度；以及把所述項分配給與最小距離值有關的所述組。
3.權利要求1或2的方法，其中所述計算步驟採用值差量度(VDM)技術來計算所述符號特徵之間的距離。
4.權利要求1或2的方法，其中所述計算步驟採用修改的值差量度(VDM)技術來計算符號特徵之間的所述距離。
5.權利要求1或2的方法，其中用下式給出對於一特定符號特徵的兩個值，V1與V2之間的所述距離δδ(V1，V2)＝∑|C1i/C1-C2i/C2|J其中C1i是V1被分到類別i內的次數，而C1是V1出現於數據集內的總次數。
6.權利要求1或2的方法，其中所述項(205，210，220)為節目，感興趣的類別為「被觀看」和「未被觀看」，並用下式給出對於一特定符號特徵的兩個值，V1與V2之間的所述距離δ(V1,V2)=|C1_watchedC1_total-C2_watchedC2_total|+]]>|C1_not_watchedC1_total-C2_not_watchedC2_total|]]>其中C1i是V1被分到類別i內的次數，而C1_total是V1出現於數據集內的總次數。
7.權利要求1或2的方法，其中所述項(205，210，220)中的一項為群平均值。
8.權利要求1或2的方法，其中所述項(205，210，220)為節目。
9.權利要求1或2的方法，其中所述項(205，210，220)為內容。
10.權利要求1或2的方法，其中所述項(205，210，220)為產品。
11.一種用在推薦器(100)內的用於評估兩個項(205，210，220)的接近度的系統(100)，所述項(205，210，220)中的每一項都用至少一個符號特徵來表徵，所述系統包括用於根據對於所述符號特徵值的每個可能值的所有例子的總的分類相似性來計算所述兩個項(205，210，220)的相應的符號特徵值之間的距離的裝置；以及用於合計各個所述符號特徵值之間的距離以確定所述兩個項(205，210，220)的接近度的裝置。
12.權利要求11的系統，進一步包括存儲器(120)，用於存儲計算機可讀代碼；以及處理器(115)，可操作地耦合於所述存儲器(120)，所述處理器(115)被配置成根據對於所述符號特徵值的每個可能值的所有例子的總的分類相似性來計算所述兩個項(205，210，220)的相應的符號特徵值之間的距離；以及合計各個所述符號特徵值之間的距離以確定所述兩個項(205，210，220)的接近度。
13.一種電腦程式產品，使可編程的設備在當執行所述電腦程式產品時起到如權利要求11所限定的系統的作用。
全文摘要
公開了一種在可得到用戶的觀看歷史記錄或購買歷史記錄之前，向用戶推薦感興趣的項目，諸如電視節目推薦的方法及裝置。處理第三方觀看或購買歷史記錄以生成反映由有代表性的觀眾所選定的典型項目樣式的定型簡表。用戶能夠從所生成的定型簡表中選擇最相關的定型，從而用最接近他或她自己的興趣的項目來初始化他或她的簡表。聚類例程把第三方觀看或購買歷史記錄(數據集)劃分成群，以使得在一個群內的點(例如，電視節目)比其它任何群更接近該群的平均值。距離計算例程根據給定的電視節目與給定的群的平均值之間的距離來評估電視節目與各個群的接近度。
文檔編號G06Q30/00GK1585954SQ02822478
公開日2005年2月23日 申請日期2002年10月22日 優先權日2001年11月13日
發明者S·V·R·古特塔, K·庫拉帕蒂 申請人:皇家飛利浦電子股份有限公司