根据第三方的原本定型的概况推荐感兴趣项目的方法和设备

摘要

本发明公开了一种方法和设备，用于在得到用户的观看历史和购买历史之前向用户推荐感兴趣的项目如电视节目推荐。处理第三方的观看历史或购买历史以产生反映由具有代表性的电视观众选择的项目的典型分布的原本定型的概况。用户可以从所产生的原本定型的概况中选择最相关的原本定型(一个或多个)，借此利用最接近他或她的兴趣的项目来启动他或她的概况。公开了一种分组程序，用于把第三方的观看历史或购买历史(数据组)分隔成多个集合，从而使一个集合中点(如电视节目)比任何其它的集合更接近这个集合的平均值。还公开了一种平均值计算程序，用于计算集合的符号平均值。

说明书

相关申请的交叉引用

本发明涉及题目为“用于评价项目的推荐器中项目的接近程度的方法和设备”的美国专利申请(代理人登记号US 010567)、题目为“在项目的推荐器中把多个项目分隔成由类似项目组成的组的方法和设备”的美国专利申请(代理人登记号US 010568)、题目为“使用基于项目的分组方法产生感兴趣的推荐项目的原本定型(stereotype)的概况(profile)的方法和设备”的美国专利申请(代理人登记号US010569)、题目为“基于所选的第三方的爱好推荐感兴趣项目的方法和役备”的美国专利申请(代理人登记号US 010572)、题目为“使用基于特征的分组方法产生推荐感兴趣项目的原本定型的概况的方法和设备”的美国专利申请(代理人登记号US 010576)，这里所说的每个申请都是同时提交的，并且都转让给本发明的受让人，这里参照引用了这些申请。

技术领域

本发明涉及推荐感兴趣项目例如电视节目的方法和设备，更加具体地说，涉及在可利用用户的购买或观看历史之前推荐感兴趣的节目和其它项目的技术。

背景技术

随着电视观众可利用的频道数目的增多，而且在每个这样的频道上可得到的电目内容多种多样，识别感兴趣的电视节目对于电视观众的挑战越来越大。电子节目指南(EPG)识别可利用的电视节目，例如通过题目、时间、日期、和频道进行识别，并且电子节目指南通过允许按照个人爱好来搜寻或存储可利用的电视节目来促进对于感兴趣的电视节目的识别。

为了推荐感兴趣的电视节目和其它项目，已经提出或者建议一系列推荐工具。电视节目推荐工具例如利用电视观众对于电子节目指南(EPG)的爱好来获得可能对特定观众感兴趣的一组推荐的电视节目。在一般情况下，电视节目推荐工具使用隐含的或明显的技术或这二者的组合来获得电视观众的爱好。隐含的电视节目推荐工具根据从电视观众的观看历史得到的信息以非强制性的方式产生电视节目推荐结果。另一方面，明显的电视节目推荐工具直接明显地询问电视观众他们对节目属性的爱好，如题目、形式、演员、频道、日期/时间，从而可以得出观众的概况并产生推荐意见。

虽然当前可以利用的推荐工具对于用户识别感兴趣的电视节目有所帮助，但它们还存在一系列限制，如果克服了这些限制，就能够极大地改善这种推荐工具的性能并提高方便性。例如，为了更加全面，明显的推荐工具启动起来是非常缓慢的，需要每个新的用户响应极其详细的调查，以大致的粗糙的水平规定他们的爱好。虽然隐含的电视节目推荐工具通过观察电视观众的观看行为非强制性地得到电视观众的概况，但它们需要很长时间才能变为准确。此外，这种隐含的电视节目推荐工具至少需要有一个最低数量的观众历史才能开始进行任何推荐。这样，这种隐含的电视节目推荐工具在刚刚获得时就不可能进行任何推荐。

因此，需要一种方法和设备，它能在得到足够多的个人观看历史之前非强制性地推荐项目，如电视节目。此外，需要一种方法和设备，它能根据第三方的观察习惯对于指定的用户产生电视节目推荐意见。

发明内容

一般来说，本发明公开了一种方法和设备，用于向用户推荐感兴趣的项目，如电视节目推荐。按照本发明的一个方面，在得到用户的观看历史和购买历史之前，例如在用户刚刚获得推荐器时，可以产生推荐意见。在一开始，使用来自于一个或多个第三方的观看历史或购买历史向某个特定用户推荐感兴趣的项目。第三方的观看历史或购买历史是从代表较大人群的具有人口统计意义的采样人群获得的。

对于第三方的观看历史或购买历史进行处理，以产生反映由具有代表性的电视观众选择的项目的典型分布(patterns)的原本定型的概况。如这里使用的，原本定型的概况是按某种方式彼此相似的一些项目的集合(数据点)。因此，一个指定的集合对应于从第三方的观看历史或购买历史选择出来的表示一个特定分布的一个特定的项目段。一旦按照本发明产生了原本定型的概况，用户就可以选择最接近的原本定型(一个或多个)，借此可利用最接近他或她自己的兴趣的项目来启动他或她的概况。所说的原本定型的概况然后根据它们的选择的分布进行调节并向特定的每个单个用户的个人观察行为靠拢，并且都提供反馈信息。

公开了一种分组(clustering)程序(routine)，把第三方的观看历史或购买历史(数据组)分成各种集合(cluster)，从而使一个集合内的点(例如电视节目)比任何其它的集合中的点更接近这个集合的平均值。还公开了一种平均值计算程序，用于计算一个集合的符号平均值。使用每个集合的平均值并根据到每个集合的数据点之间的距离把一个指定的数据点(例如一个电视节目)分配给一个集合。一个分组性能评估程序确定什么时候满足用于产生集合的预定停止标准。参照以下的详细描述和附图可获得对本发明的更加全面的理解以及本发明的其它特征和优点。

附图说明

图1是按照本发明的电视节目推荐器的示意框图；

图2是来自于图1的典型节目数据库的采样表；

图3是描述实施本发明原理的图1的原本定型的概况的流程图；

图4是描述实施本发明原理的图1的分组程序的流程图；

图5是描述实施本发明原理的图1的平均值计算程序的流程图；

图6是描述实施本发明原理的图1的距离计算程序的流程图；

图7A是从典型的频道特征值发生表得到的一个采样表，表示每个类别的每个频道特征值的发生数；

图7B是从典型特征值对距离表得到的采样表，表示从图7A所示的典型计数计算的每个频道特征值对之间的距离；

图8是描述实施本发明原理的图1的分组性能评估程序的流程图。

具体实施方式

图1表示按照本发明的一个电视节目推荐器100。如图1所示，典型电视节目推荐器100在节目数据库200中评估节目，以识别特定电视观众感兴趣的电视节目，下面将结合图2讨论节目数据库200。使用众所周知的屏幕上显示技术可以将这组推荐的电视节目显示给观众，例如使用机顶盒终端/电视(未示出)。虽然这里说明的本发明围绕着电视节目的推荐，但是本发明可以应用到基于对用户行为的评估(如观看历史或购买历史)的任何自动产生推荐意见的场合。

按照本发明的一个特征，电视节目推荐器100可以在获得用户的观看历史140之前例如在用户刚获得电视节目推荐器100时产生电视节目推荐意见。如图1所示，电视节目推荐器100在开始时使用来自于一个或多个第三方的观看历史130来推荐对于特定用户感兴趣的推荐的电视节目。在一般情况下，第三方的观看历史130是基于代表较大人群的、具有人口统计意义的(如年纪、收入、性别、和教育)、一个或多个采样人群的观看习惯(habit)。

如图1所示，第三方的观看历史130由指定的人群观看的和不观看的一组节目构成。通过观察指定人群实际观看的节目来获得观看的节目组。例如通过随机采样节目数据库200中的节目，可获得不看的节目组。按另一种变化，按照美国专利申请序列号NO.09/819286(2001年3月28日提交，题目为“用于选择人工智能应用的否定实例的自适应采样技术”)的教导来获得不看的节目组，该申请转让给本发明的受让人，并在这里参照引用。

按照本发明的另一特征，电视节目推荐器100处理第三方的观看历史130，产生反映由具有代表性的电视观众的典型分布的原本定型的概况。如下面还要更加详细说明的，原本定型的概况是按某种方式彼此相似的电视节目的一个集合(数据点)。于是，指定的集合对应于来自于第三方的观看历史130的表现特定分布的电视节目的一个特定的区段。

按照本发明处理第三方的观看历史130，提供展示某种特定分布的节目集合。因此，用户能够选择最相关的原本定型(一个或多个)，借此，利用最接近他或她自己的兴趣的节目来启动他或她的原本定型的概况。原本定型的概况然后进行调节，并且根据它们的记录的分布向特定的、每个单个用户的个人观看行为靠拢，并且向节目提供反馈。在一个实施例中，当确定节目的评分的时候，给予来源于用户自己的观看历史140的节目的权重大于给予来源于第三方的观看历史130的节目的权重。

电视节目推荐器100可以实施成任何计算装置，如个人计算机或工作站，计算装置包含处理器115(如中央处理单元(CPU))和存储器120(如RAM和/或ROM)。电视节目推荐器100还可以实施成例如在机顶盒终端或显示器(未示出)中的特殊应用集成电路(ASIC)。此外，电视节目推荐器100还可以实施成任何可以利用的电视节目推荐器，如在Tivo公司(Sunnyvale，California)可以买到的Tivo^TM系统，或者在下述文献中描述的各种电视节目推荐器：美国专利申请序列号NO.09/466406(1999年12月17日提交，题目为“使用判别树推荐电视节目的方法和设备”)、美国专利申请序列号MO.09/498271(2000年2月4日提交，题目为“贝叶斯电视播出节目推荐器”)、和美国专利申请序列号NO.09/627139(2000年7月27日提交，题目为“3路介质推荐方法和系统”)，或者这些电视节目推荐器的任意组合，这里参照引用了上述每个美国专利申请，并且对它们进行改进以实现本发明的特征和功能。

如图1所示，并且下面还要结合附图2-8作详细描述，电视节目推荐器100包括：节目数据库200、原本定型的概况过程300、分组程序400、平均值计算程序500、距离计算程序600、和集合性能评估程序800。在一般情况下，节目数据库200可以实施为公知的电子节目指南，并且记录在指定的时间间隔内可以得到的每个节目的信息。原本定型的概况过程300(i)用于处理第三方的观看历史130，产生反映由具有代表性的电视观众观看的电视节目的典型分布的原本定型的概况；允许用户选择最相关的原本定型(一个或多个)，并由此启动他或她的概况；(iii)根据所选的原本定型产生推荐意见。

分组程序400由原本定型的概况过程300调用，将第三方的观看历史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。然后，在步骤320，原本定型的概况过程300执行分组程序400，下面还要结合图4对此作详细描述，从而可以产生对应于原本定型的概况的节目集合。如以下所述的，典型的分组程序400对于观看历史数据组130可以使用非监视性的数据分组算法，例如“k平均值”集合程序。如以上所述，分组程序400把第三方的观看历史130(数据组)分隔成多个集合，使得一个集合中的点(电视节目)比任何其它的集合的点更靠近这个集合的平均值(形状的中心)。

原本定型的概况过程300然后在步骤330对每个集合分配一个或多个标记(一个或多个)，使每个原本定型的概况特征化。在一个典型的实施例中，集合的平均值变为整个集合的具有代表性的电视节目，并且可以使用平均值的特征标记集合。例如，可以配置电视节目推荐器100，以使节目的形式成为每个集合的支配特征或决定性特征。

在步骤340，向每个用户显示经过标记的原本定型的概况，以便选择最接近用户兴趣的原本定型的概况。构成每个所选集合的节目可以被认为是这个原本定型的“典型观看历史”，并且可以用来构造每个集合的原本定型的概况。这样，在步骤350，对于用户产生了观看历史，它由来自于所选的原本定型的概况的节目构成。最后，在步骤360，将在前一步骤产生观看历史加到电视节目推荐器以获得节目的推荐意见。电视节目推荐器可以实施为任何常规的节目推荐器，如以上引用的那些，在这里进行了改进，这对于本领域的普通技术人员来说是显而易见的。在步骤370，节目控制终止。

图4是描述加入本发明特征的分组程序400的典型实施方案的流程图。如以上所述，分组程序400在步骤320期间由原本定型的概况过程300调用，将第三方的观看历史130(数据组)分隔成多个集合，使得在一个集合中的点(电视节目)比任何其它的集合中的点更加靠近这个集合的平均值(形状中心)。在一般情况下，分组程序的主要的非监视性任务是在采样数据组中寻找实例组。本发明使用k平均值分组算法将数据组分成k个集合。如下面将要描述的，分组程序400的两个主要参数是(i)用于寻找最接近的集合的距离度量标准(metric)，下面将结合图6进行讨论；(ii)要产生的集合(clusters)的数量k。

在进一步分组实例数据不能产生分类精度的任何改进时k已经稳定的条件下，典型的分组程序400使用k的动态值。此外，对于记录空集合的点，增加集合的大小。这样，当达到集合的常态水平时，分组停止。

如图4所示，在步骤410，分组程序400在一开始时建立k个集合。典型的分组程序400是从选择最小数目的集合例如2个集合开始的。对于这一固定数，分组程序400处理整个观看历史数据组130，并且经过几次迭代达到能够被认为是稳定的两个集合(稳定的含义就是，即使继续该算法到另一次迭代，也没有任何一个节目会从一个集合移动到另一个集合)。在步骤420，可以利用一个或多个节目启动当前的k个集合。

在一个典型的实施方案中，在步骤420中，利用从第三方的观看历史130中选出的某些种节目启动这些集合。可以随机地或者按照顺序地选择启动集合的节目。在按照顺序选择的实施方案中，启动集合的节目从观看历史130中的第一个节目开始，或者从观看历史130中的一个随机点的节目开始。在下一个变型中，启动每个集合的节目的数目还可以改变。最后，还可以利用一个或多个“假想的”节目启动集合，所说的“假想的”节目由从第三方的观看历史130中的节目中随机选择出来的特征值组成。

然后，在步骤430，分组程序400启动下面要结合图5讨论的平均值计算程序500，以计算每个集合的当前平均值。然后，在步骤440，分组程序400执行下面要结合图6讨论的距离计算程序600，以确定第三方的观看历史130中的每一节目到每个集合的距离。然后，在步骤460，将观看历史130中的每个节目分配给最近的集合。

在步骤470进行测试，确定是否有任何节目从一个集合移动到另一个集合。如果在步骤470确定有节目从一个集合移动到另一个集合，则节目控制返回到步骤430，按照以上所述的方式继续进行，直到识别出一个稳定的集合组时为止。然而，如果在步骤470确定没有节目从一个集合移动到另一个集合，则节目控制前进到步骤480。

在步骤480进行另一种测试，确定是否满足规定的性能标准或者确定是否识别出一个空的集合(统称为“停止标准”)。如果在步骤480确定不满足所说的停止标准，则在步骤485增加k的值，并且节目控制返回到步骤420，按照以上所述的方式继续。但如果在步骤480确定：已经满足停止标准，则节目控制终止。下面还要结合附图8对停止标准的估算作进一步地讨论。

典型的分组程序400将节目只放置在一个集合中，因而产生所谓的轮廓鲜明集合。另一种变化可能是使用轮廓模糊的集合，允许特定的实例(电视节目)部分地属于多个集合。按照模糊集合方法，为一个电视节目分配一个权重，权重代表这个电视节目接近集合平均值的程度。这个权重可能取决于电视节目距集合平均值的距离的平方的倒数。与单个电视节目相关的所有集合的权重的总和最多必须加到100％。

集合的符号平均值的计算

图5是一个流程图，描述加入本发明特征的平均值计算程序500的典型实施方案。如以前所述，平均值计算程序500由分组程序400调用，用于计算集合的符号平均值。对于数字数据，平均值是使变化最小的数值。若将这一构思扩到符号数据，一个集合的平均值可通过寻找x_μ值确定，所说的x_μ值使集合间的变化最小(因而集合的半径或大小最小)，

Var(J)＝∑_i∈J(x_i-x_μ)²          (1)

集合的半径 $>>R>>(>J>)>>=>>Var>>(>J>)>\; >->->->>(>2>)>>>s>$

这里，J是来自于相同类别(进行观看，或者不进行观看)的电视节目的一个集合，xi是节目i的符号特征值，x_μ是来自于集合J中电视节目之一并使Var(J)最小的特征值。

于是，如图5所示，在步骤510，平均值计算程序500一开始就识别当前在指定的集合J内的节目。对于正在考虑的当前符号属性，在步骤520使用方程(1)对于每个可能的符号值x_μ计算集合J的变化。在步骤530，选择使这个变化最小的符号值x_μ作为平均值。

在步骤540进行测试，以确定是否还有需要考虑的附加符号属性。如果在步骤540确定还有需要考虑的附加符号属性，则节目控制返回到步骤520，按以上所述的方式继续进行。然而，如果在步骤540确定没有需要考虑的附加的符号属性，则节目控制返回到分组程序400。

通过计算，对于集合J中的每个符号特征值进行是否是x_μ的试探，并且使所说的变化最小的符号值成为集合J中正在考虑的符号属性的平均值。这里平均值计算可能有两种类型，即基于节目的平均值和基于特征的平均值。

基于特征的符号平均值

这里讨论的典型的平均值计算程序500是基于特征的，其中最终的集合平均值是由从集合J中的实例(节目)中提取的特征值构成的，因为符号属性的特征值必须是它的可能的数值之一。重要的是要记住，集合的平均值还可以是“假想的”电视节目。这种假想的节目的特征值可能包括从一个实例(例如说EBC)中提取的频道值以及从另一个实例中提取的题目值(例如说“BBC世界新闻”，然而在实际上，“BBC世界新闻”从来不在EBC上广播)。这样，选择展示最小变化的任何特征来代表这个特征的平均值。对于所有的特征位置重复平均值计算程序500，直到在步骤540确定已经考虑了所有的特征(即符号属性)时为止。使用这样获得的最终的假想的节目来代表集合的平均值。

基于节目的符号平均值

在下一种变型中，在用于变化的方程(1)中，xi可以是电视节目i本身，类似地，x_μ是集合J中使集合J中节目组上的变化最小的节目(一个或多个)。在这种情况下，在节目之间的距离(不是单个特征值)是使其变为最小的相关度量标准。此外，在这情况下的最终平均值不是一个假想的节目，而是真正从集合J中拾取的一个节目。使用在集合J中这样找到的并且使集合J中所有节目上的变化最小的任何节目代表这个集合的平均值。

使用多个节目的符号平均值

以上讨论的典型平均值计算程序500使用每个可能的特征的特征值使集合的平均值特征化(不管是基于特征的实施方案还是基于节目的实施方案)。然而已经发现，在平均值计算期间，只依靠每个特征的一个特征值经常会导致不正确的分组，因为这个平均值不再是这个集合的具有代表性的集合中心。换言之，不期望只通过一个节目代表一个集合，与此相反，多个节目代表这个平均值，或者，可以使用多种方式代表这个集合。因而，在进一步的变化中，由每个可能的特征的多种方式或多个特征值代表一个集合。于是，在步骤530，选择可以使所说的变化最小的N个特征(对于基于特征的符号平均值)或N个节目(对于基于节目的符号平均值)，这里的N是用来表示一个集合的平均值的节目数。

在节目和集合之间的距离计算

如以上所述，距离计算程序600由分组程序400调用，用于根据一个指定的电视节目和指定的集合的平均值之间的距离估算这个电视节目接近每个集合的程度。计算得到的距离度量标准将决定一个集合的范围大小的采样数据组中的各个实例之间的区别特征量化。为了能够分组用户的概况，必须计算在观看历史中任何两个电视节目之间的距离。在一般情况下，彼此靠近的电视节目超向于落入一个集合内。存在一系列相对来说简单的技术可以计算数字数值矢量之间的距离，例如欧几里得距离、Manhattan距离、Mahalanobis距离。但在电视节目矢量的情况下，不可能使用现有的距离计算技术，因为电视节目主要是由符号特征值组成的。例如，两个电视节目：2001年3月22日下午8点在EBC台上播放的一个选段“恶魔”和2001年3月25日下午8点在FEX台上广播的一个选段“西蒙斯(Simons)”可以使用以下的特征矢量表示：

题目：恶魔                  题目：西蒙斯(Simons)

频道：EBC                   频道：FEX

播放日期：2001-03-22        播放日期：2001-03-25

播出时间：200               播出时间：2000

显然，已知的数值距离度量标准不可能用来计算特征值“EBC”和“FEX”之间的距离。在符号特征值域内度量特征值之间的距离的一种现有的技术是“数值差度量标准”(VDM)。VDM技术把每个特征的每个可能的数值的所有情况分类的整体相似性考虑在内。使用这种方法，根据训练组内的实例，按照统计学方法导出一个矩阵，这个矩阵可以确定一个特征的所有值之间的距离。对于计算符号特征值之间的距离的VDM技术的更加详细的讨论，例如可以参见Stanfill和Waltz的“面向基于存储的合理性”(ACM通信，29：12，1213-1228，1986)，这里参照引用了该文献。

本发明使用了VDM技术或者它的变型来计算两个电视节目之间的特征值之间的距离或者其它感兴趣的项目。最初的VDM建议技术在两个特征值之间的距离计算中使用了一个权重项，这使距离度量标准不对称。一种改进的VDM(MVDM)省去了权重项，以使距离矩阵对称。对于计算符号特征值之间的距离的MVDM技术的更加详细的讨论，例如参见Cost和Salzberg的“用于学习符号特征的一种加权的最近相邻算法”(机器学习，第10卷，第57-58页，Boston，MA，Kluwer出版社，1993年)，这里参照引用了该文献。按照MVDM，对于一个特定的特征，在两个值V1和V2之间的距离δ由下式给出：

δ(V1，V2)＝∑|C1i/C1-C2i/C2|^r                 方程(3)

在本发明的节目推荐环境中，MVDM方程(3)转变成具体处理类别：“观看的”和“非观看的”。

$>>\delta >>(>V>1>,>V>2>)>>=>|>>>C>1>\_>watched>>>C>1>\_>total>\; >->>>C>2>\_>watched>>>C>2>\_>total>\; >|>+>>s>$

$>>|>>>C>1>\_>not>\_>watched>>>C>1>\_>total>\; >->>>C>2>\_>not>\_>watched>>>C>2>\_>total>\; >|>>s>方程(4)$

在方程(4)中，V1和V2是两个正在考虑的可能的特征值。若计算上述实例，对于这个“特征”频道，第一值V1等于“BBC”，第二值V2等于“FEX”。这些值之间的距离是对于实例被分类成的所有分类的总和。对于本发明典型节目推荐器实施例的相关类别是“观看的”和“非观看的”。C1i是V1(EBC)分类为类别i(i＝1意味着是类别“观看的”)的次数，C1(C1_total)是在该数据组中发生V1的总次数。值“r”是一个常数，通常设定为1。

由方程(4)确定的度量标准用于识别对于所有的类别以相同的相关频度发生的一些相似的数值。项C1i/C1代表在考虑中的特征具有值V的条件下中心余项分类为i的似然率。这样，如果两个数值对于所有可能的分类给出相似的似然率，则这两个值就是相似的。方程(4)通过寻找对于所有分类的这些似然率之差的总和来计算两个值之间的总的相似性。在两个电视节目之间的距离就是在两个电视节目矢量的对应的特征值之间的距离之和。

图7A是与特征“频道”有关的特征值的距离表的一部分。图7A表示每个类别的每个频道特征值的发生数。图7A中表示的数值取自典型的第三方的观看历史130。

图7B表示使用MVDM方程(4)从如图7A所示的典型计数计算出来的每个特征值对之间距离。从直觉上看，EBC和ABS彼此应该很“接近”，因为它们在大多数情况下出现在“观看的”类别中，而不出现在“非观看的”类别中(ABS有很小的“非观看的”分量)。图7B确认了这一个直觉，在EBC和ABS之间有很小(非零)的中距离。另一方面，ASPN在大多数情况下出现在“非观看的”类别中，因此对于这个数据组而言，ASPN距EBS和ABS这两者都很“遥远”。图7B列出了EBC和ASPN之间的距离，这个距离是1.895，而它的最大可能的值仅为2.0。类似地，在ABS和ASPN之间的距离也很大，其数值为1.828。

这样，如图6所示，在步骤610，距离计算程序600在一开始就识别在第三方的观看历史130中的节目。在步骤620，对于当前正在考虑的节目，距离计算程序600使用方程(4)计算每个符号特征值到每个集合平均值(由平均值计算程序500确定)的对应特征的距离。

在步骤630，通过聚集在对应特征值之间的距离来计算当前节目和集合平均值之间的距离。在步骤640进行测试，确定在第三方的观看历史130中是否还有需要考虑的附加节目。如果在步骤640确定在第三方的观看历史130中还有需要考虑的附加节目，则在步骤650识别下一个节目，并且按以上所述的方式继续。

然而，如果在步骤640确定在第三方的观看历史130中没有需要考虑的附加节目，则节目控制返回到分组程序400。

如以上在小标题“从多个节目导出的符号平均值”中所讨论的，使用每个可能特征的多个特征值可使集合的平均值特征化(不管是基于特征的实施方案还是基于节目的实施方案)。通过距离计算程序600的变化来汇总来自于多种方式的结果，以便通过表决得到一致的决定。例如，现在在步骤620计算一个节目的指定的特征值和各种方式得到的对应的特征值之间的距离。例如，通过使用多数表决方式或者多个专家的表决方式来达到一致决定，从而可以汇总并使用最小距离结果。对于这种技术的更加详细的讨论，例如参见J.Kittler等人的“梳理分类法”(有关图形识别的第13届国际会议会议录，第II卷，897-901，维也纳，奥地利，1996年)，这里参照引用了该文献。

停止标准

如以上所述，分组程序400调用集合性能评估程序800，如图8所示，确定什么时候满足产生集合的停止标准。典型的分组程序400使用动态k值，其条件是：当进一步分组实例数据对于分类精度没有任何改善时已经达到稳定的k。此外，集合的大小可以增加到可以记录空集合的点。这样，当达到集合的常态水平时，分组停止。

典型的集合性能评估程序800使用来自于第三方的观看历史130的节目子集(测试数据组)来测试分组程序400的分类精度。对于测试组中的每个节目，集合性能评估程序800确定最接近它的集合(这个集合的平均值是最近的)，并且比较集合的类别标记和正在考虑的节目。匹配的类别标记的百分数翻译成分组程序400的精度。

这样，如图8所示，在步骤810，集合性能评估程序800开始收集来自于第三方的观看历史130的节目子集，用作测试数据组。然后，在步骤820，根据集合中观看的节目和非观看的节目的百分数，为每个集合分配一个类别标记。例如，如果观看一个集合中的大多数节目，这个集合就可以分配到一个标记“观看的”。

在步骤830，识别最接近测试组中每个节目的集合，将分配过标记的集合的类别标记与这个节目实际上是否正在被观看的情况进行比较。在使用多个节目代表一个集合的平均值的实施方案中，可以使用(到每个节目)的平均距离或表决方案。在步骤840确定匹配的类别标记的百分数，而后节目控制返回到分组程序400。如果分类精度已经达到预定阈值，则分组程序400终止。

应该理解，这里表示并描述的实施例和变化只是说明本发明的原理，本领域的普通技术人员在不偏离本发明范围和构思的条件下可以实现各种改进。