利用决策树推荐电视节目的方法和装置

暂无

技术领域
本发明涉及一种用于推荐电视节目的方法和装置，特别是涉及到 通过使用决策树来推荐电视节目的方法和装置。
背景技术
由于电视观众可接收到的电视频道，连同这些频道中节目内容 的多样性增加了，电视观众确定感兴趣的电视节目变得越来越复杂。 历史上，电视观众通过分析印制的电视节目指南来确定感兴趣的电视 节目。通常，这种印制的电视节目指南包括依照时间和日期、频道和 标题排列的可收电视节目的网格列表。由于电视节目的增加，使用这 种印制的指南来有效确定所需电视节目已经变得不切实际了。
新近，电视节目指南已经可以通过电子版本得到，通常称为电子 节目指南(EPGs)。象印制的电视节目指南一样，电子节目指南也包 括根据时间和日期、频道和题目排列的可收电视节目的列表网格。然 而，电子节目指南允许观众根据个人的喜好来排序或搜索可收电视节 目。而且，电子节目指南允许可收电视节目的屏幕显示。
尽管电子节目指南允许观众比常规印制的指南更有效地确定所 需的电视节目，它们也受到一些限制，如果能够克服这些限制，会进 一步提高观众确定所需节目的能力。例如，许多观众对某类电视节目 具有一个特别的喜好或偏爱，如基于运动的节目或体育节目。这样， 可以将这些观众的喜好应用到电子节目指南中，来获得一组能够满足 特定观众兴趣的推荐节目。
为此，已有许多工具被建议或提出用来推荐电视节目。例如可以 从加利福尼亚的Sunnyvale的Tivo公司购买的TivoTM系统，允许观 众使用“赞同和否决”的特性来为节目定级，并由此分别表明观众喜 欢和不喜欢的节目。据此，TiVo接收器将记录的观众喜好与接收到 的节目数据，如电视节目指南相比较，使推荐的节目适合每一个观 众。
因此，基于观众以往的观看历史以及一个包括观众喜好的概况描 述，这种推荐电视节目的工具提供了观众可能喜欢的节目选择。实际 上，这种用于推荐电视节目的工具通常需要清晰的用户概况信息。但 是，观众可能不会花费在一个用户概况中充分描述他们的观看喜好所 需的时间。所以，需要一个基于观众以往观看历史的用于推荐电视节 目的方法和装置。进一步需要一个不需任何清晰的观众概况信息的用 于推荐电视节目的方法和装置。
发明内容
总的来说，本发明公开了一种利用决策树来推荐电视节目的方法 和装置。根据本发明的一个方面，基于一个用户以往的观看历史，利 用归纳原理来确定一套可以满足特定观众兴趣的推荐的电视节目。
本发明监控一个用户的观看历史并分析用户实际观看的节目(正 例)和该用户不观看的节目(负例)。针对每一个正和负的节目例子 (即观看和不观看的节目)，在用户概况中对若干节目的属性进行分 类，诸如给定节目的时间、日期、持续时间、频道、等级、题目和种 类。而后不同的属性被放置到基于每个属性的平均信息量等级的分类 决策树中。决策树的每个叶节点对应于一个定位在相应的叶节点的节 目的正或负的推荐信息。决策树试图覆盖尽可能多的正例而不覆盖负 例。
如果有用户简档，本发明的电视节目推荐器对其进行处理，并处 理用户的观看历史，以产生一个决策树。利用一个实现“自顶向下的 划分和控制”方法的决策树处理来建立决策树。而后，决策树可以被 用于一个电子节目指南中以进行节目推荐。例如，节目推荐可以是一 套可以满足一个特定观众的兴趣的推荐节目。
附图说明
通过参考下面的详细描述和附图，来更全面地理解本发明，并了 解本发明的进一步的特征和优势。
图1说明一个依照本发明的电视节目推荐器；
图2说明一个分类决策树，该树基于电视节目的每个属性的平均 信息量的级别，将节目的不同属性放置于决策树中；
图3是一个描述体现本发明原理的示例决策树处理的流程图；
图4是一个描述体现本发明原理的示例决策树建立子程序的流 程图；
图5是一个说明根据熟知的技术产生一个决策树的样本表；和
图6说明对应于表5例子产生的决策树。
具体实施方式
图1说明一个依照本发明的电视节目推荐器100。公布的电视节 目推荐器100利用归纳原理来确定一套可以满足一个特定观众兴趣 的电视节目。本发明监控一个用户的观看历史并分析用户实际观看的 节目(正例)和该用户不观看的节目(负例)。而后，本发明通过建 立一个试图覆盖尽可能多的正例而不覆盖负例的决策树来判定正的 或负的例子。
根据本发明的另一个特征，电视节目推荐器100无需任何清晰的 来自用户的概况信息即可进行电视节目推荐。如果可以得到，清晰的 用户概况信息可以增进电视节目推荐器100产生的推荐。通常，电视 节目推荐器100通过观察用户超时观看习惯并概括用户观看习惯并 建立一个试图覆盖尽可能多的正例而没有负例的用户概况来进行学 习。
如图1所示，如果可以得到，电视节目推荐器100处理一个用户 概况120，和一个用户观看历史130，来产生一个决策树200。注意， 用户观看历史130的处理结果可以以更新用户概况120的形式来存 储。决策树200可以被用于一个电子节目指南140，来进行节目推荐。 例如，节目推荐可以是一套可以满足一个特定观众的兴趣的推荐节 目。
如图1所示，电视节目推荐器100包括一个决策树处理300，在 下面结合图3进一步讨论，通过调用一个决策树建立子程序400为用 户产生一个决策树，该过程将在下面结合图4进一步讨论。电视节目 推荐器100可以具体化为任何的计算机装置，如个人计算机或工作站 等，包括一个处理器，如一个中央处理单元(CPU)，和存储器，如 随即存储器和只读存储器。
对于每个正的和负的节目例子(即观看和不观看的节目)，对若 干个熟知的属性在用户概况中进行了分类，如给定节目的时间、日 期、观看时间、频道、级别、题目和类型等。如图2所示，基于每个 属性的平均信息量的级别，不同的属性被放置到分类的决策树200 中。示例的决策树200包括一个根节点205和若干个子节点，如子节 点210、220、245、250、260、265和270。决策树200中的每个节 点和子节点对应于用户概况中一个给定的属性。决策树200中的每个 叶节点，如叶节点225、230、235、240和281-293对应于定位于相 应叶节点的节目的正的或负的推荐。
例如，如果在训练数据中一个给定的节目具有一个大于45分钟 但小于或等于65分钟的观看时间，并是一个西部的(类型)节目， 则该节目将作为一个正的例子被归类到叶节点235之下。此后，如果 在该测试数据中一个给定的节目的这些属性具有满足这一条件的 值，则该节目将是一个推荐的节目。
如图3所示，利用一个实现“自顶向下的划分和控制”(“top-down divide and conquer”)方法的决策树处理300建立决策树200。而 后决策树200可以转化为一个规则。该决策树规则允许本发明性能的 内省分析。本发明的决策树技术是基于Ross Quinlan的公认的理论， 例如，可以参考CA 1990，Palo Alto，Morgan Kaufmann出版社的“机 器学习程序”的C4.5，该内容可以被用于实时并可延伸到用于任何 数目的种类。
决策树原理
决策树是基于公认的在20世纪50年代后期由Hunt等人提出的 学习概念的理论，例如，可参见Hunt等人的1966年纽约学术出版社 的“归纳实验”。它被进一步延伸并通过如下的文献使其普及：Breiman 等著，CA(Wadsworth，1984)，Belmont的“分类和回归树”；(1983) 加利福尼亚Palo Alto的Morgan Kaufmann出版社出版的Quinlan J. R.的“有效的分类过程学习及其在象棋游戏中的应用”，Michalski R.S.、Carbonel 1 J.G.和Mitchell T.M.(Eds.)著，“机器学习： 一种人工方法”的Vol.1；(1990)加利福尼亚Palo Alto的Morgan Kaufmann出版社出版的Quinlan J.R.著“概率决策树”、Kodratoff Y.和Michalski R.S(Rds.)著，“机器学习：一种人工方法”的 Vol.3；和(1993)CA，Sam Mateo的Morgan Kaufmann出版社出版 的Quinlan J.R.的C4.5：“机器学习程序”。
构造一个决策树的基本方法是：令T为一组训练的事件，并把类 表示为{C1，C2，...，Ck}。存在下面三种可能性：
T包含一个或多个事件，均属于一个单一类别C j ：
T的决策树是一个标识类型 C j的叶。
T不包含任何事件：
该决策树仍是一个叶，但是与该叶相关的类型必须从T以外的信 息来确定。例如，可以借助于有关领域的背景知识来选择该叶。
T包含属于一个混合类型的时间
在这种情况下，该方法将把T提炼到似乎是超前的单类事件集合 的子集中。基于一个属性，选择一个具有一个或多个相互独立的输出 {O1，O2，...，On}的测试。T被分配到子集T1，T2，...，Tn中，其中Ti包 括T中具有所选输出中的输出Oi的所有事件。T的决策树包括一个标 识该测试的一个决策节点，和一个每个可能输出的分枝。按递归的方 式，同样的构建树的方法被应用到训练事件的每个子集中，这样第i 个分枝通往由训练事件子集Ti构造的决策树。
建立树的处理取决于选择一个适当的测试。任何以非无效方式划 分T以便至少有两个子集{Ti}为非空的测试最终将T分配成为单类型 子集，即使所有或大部分的子集包含一个单一训练事件。但是，本发 明的目的不仅仅是根据分配来建立一个树，而是建立一个能够展现数 据集结构并能够预测未见事件的树。通常是根据增益标准，基于信息 理论来选择测试，解释如下。
假设有一些具有n个可能输出的测试，把训练事件T集分成子集 T1，T2，...，Tn。如果不探查Ti的后续分类而评估这个测试，我们仅 能获得的信息是T和其子集中类别的分布。设S为任意的事件子集， freq(Ci，S)表示S中属于类Ci的事件数目，|S|为集S中的事件数目。 支持选择测试的标准的信息理论如下：通过一条消息传达的信息取决 于它的概率并以位的形式用该概率的以2为底的对数来测量。例如， 如果有8个可能的消息，则由其中任何一个所传递的信息为-log2(1/8) 或3位。如果从属于某一Cj的事件集S中随机选择了一个事件，则该 消息应具有一个概率：
$\frac{\mathrm{freq}(C_j,S)}{\left|S\right|}$
消息传递的信息为：
${-\log }_2\left[\frac{\mathrm{freq}(C_j,S)}{\left|S\right|}\right]$ 位
为了从这样一个属于类成员的消息中发现预期的信息，我们对类 按其在S中的频率的比例进行累加，得到：
$\mathrm{info}\left(S\right)=-\underset{j=1}{\overset{k}{\Sigma }}\frac{\mathrm{freq}(C_j,S)}{\left|S\right|}\times {\log }_2\left[\frac{\mathrm{freq}(C_j,S)}{\left|S\right|}\right]$ 位。
如果用到训练事件集中，则用info(T)来测量确定T中一个事件 的类所需的平均信息量。这个量通常被称为集S的平均信息量。当依 照一个测试X的n个输出分配了T时，那么可以发现该预期的信息为 子集的加权累加和，由下面的公式给出：
${\mathrm{info}}_X\left(T\right)=\underset{i=1}{\overset{n}{\Sigma }}\left|\frac{\mathrm{Ti}}{T}\right|\times \mathrm{info}\left(T_i\right)$
用下面的量：
gain(X)＝info(T)-infoX(T)
来度量依照测试X通过分配T来获得的信息，该量通常被称为增 益标准。然后，这一标准选择一个测试来最大化信息增益，该增益通 常被当作是测试X和类之间的相互信息。
尽管增益标准给出良好的结果，但是仍具有一个严重的不足，也 就是很强地偏重于具有许多输出的测试[Quinan，1990]。例如，考虑 一个假定的医疗诊断任务，其中一个属性包括患者识别。由于每个这 种识别应该是唯一的，分配一套该属性值的训练事件将会导致大量的 子集，每个子集仅包含一个事件。由于所有这些一个事件的子集会包 含一个单类的事件，infox(T)将等于0。这样通过使用该属性来分配 该训练事件集所获得的信息增益是最大的。但是，从预测的观点上 看，这样的分配是没有多大用途的。
通过规一化来调整增益标准固有的偏重，其中调整可归于具有多 个输出的测试的明显的增益。现在考虑属于一个事件的消息的信息内 容，该内容表示的不是该事件所属的类，而是测试的输出。类似于 info(S)的定义，有：
$\mathrm{splitinfo}\left(X\right)=-\underset{i=1}{\overset{n}{\Sigma }}\frac{\left|T_i\right|}{\left|T\right|}\times {\log }_2\left[\frac{\left|T_i\right|}{\left|T\right|}\right]$
该式表示通过将T划分为n个子集产生的潜在的信息，而信息增 益用来衡量关于同一划分所产生的分类的信息。然后，表达式gain ratio(X)＝gain(X)/split info(X)表示通过分离产生的信息比例。当 分离信息很小时，该比例是不稳定的。为了避免这种情况，增益率标 准选择一个测试来最大化遵从于一个限制的比率，该限制是信息增益 必需至少要同所有检测的测试事件的平均增益一样大。
上面对构建一个决策树的描述是基于假定能够确定一个事件的 测试的输出。但是，实际上数据是不明的属性值。这是可能是因为该 值不是关于一个特定的事件的，当数据被收集到时不被存储，或者不 能通过负责登记数据的对象来辨别。这种不完善通常存在于实际数据 中。那么我们有两种选择：要么必需放弃很大比例的可用数据，并且 声明一些测试事件是不可分类的，要么必需修改算法，来处理不明的 属性值。在多数情况下，前者是不能接受的，因为它削弱了发现模式 的能力。那么，可以按如下步骤实现处理不明的属性值所作的对标准 的修正：
设T为训练集，X为基于某一属性A的一个测试，并假设仅在T 中事件的一部分F中A的值是已知的，除非仅考虑具有已知A值的事 件，info(T)和infox(T)的计算如前面所述。那么，增益的定义可以 修改为：
gain(X)＝已知概率A×(info(T)-infox(T))+未知概率A×0
＝F×(info(T)-infox(T))
增益的这一定义只是通过考虑具有已知的相关属性值的事件而 得到的明显的增益，乘以训练集中这种事件的一部分。类似地，也可 以通过考虑具有未知值的作为一个附加组的事件来改变split info(X)。如果一个测试有n个输出，如同该测试将事件划分为n+1 个子集来计算它的分离信息。利用增益和分裂信息的修正的定义，按 下面的方法来实现训练集的分配。当具有已知输出Qi的T中一个的事 件被赋给子集Ti时，该事件属于子集Ti的概率为1，属于其它子集的 概率为0。但是，当输出为未知时，仅可以进行一个薄弱的概率声明。 如果事件具有一个已知的输出，加权值为1；如果事件具有一个未知 的输出，加权值仅是输出Qi在该点上的概率。每个子集Ti为一个可 能是一部分事件的集合，这样|Ti|可以解释为事件集中一部分事件加 权值的和。T中训练事件具有非1起始的加权值是可能的，因为T可 以是一个早期划分的子集。通常，T中的一个具有加权值w的，其输 出为未知的事件被赋给每一个具有下面的加权值的子集Ti
w×输出Qi的概率
后期的概率是按照T中已知具有输出Oi的事件的加权值的累加 和除以本次测试T中具有已知输出的事件的加权值的累加和来估算 的。
如果我们假设类型为“观看的节目”和“不观看的节目”，则DT 的格式是这样，以至它具有节点和叶，其中节点对应于一些将运行的 测试，而叶对应于这两个类型。现在测试一个未知的事件(节目)包 括解析该树以确定未知事件属于哪一个类型。但是，如果在一个特定 的决策节点上，我们遇到一种情况，其中相应的属性值是未知的，这 样测试的输出不能确定，则系统探查所有可能的输出并联合产生的分 类。因为现在可能有多个从树的根或从子树到叶的路径，那么，分类 可以是一个类分布，而不是一个单一的类。当获得了未见的事件类分 布时，该具有最高概率的类被指定为预计的类。
图3是一个描述体现本发明原理的示例决策树处理300的流程 图。如图3所示，决策树处理300最初在步骤310中从训练数据中选 择一个随机的子集W。随后，决策树处理300执行建立决策树的子程 序400，将在下面结合图4来进一步讨论，在步骤320中为当前窗口 W建立一个决策树。
一旦建立决策树子程序400为当前的窗口W建立了决策树，在步 骤330中搜索训练集查找决策树的例外。如前面指出的，决策树从给 树的整个例子集中随机选择一个正的和负的例子的子集，并利用该子 集建立一个决策树。而后，决策树处理300在步骤330中在剩余的例 子中应用这一产生的树。如果例子被错误地分类，则决策树处理300 按照下面的方式增加该错误分类的例子(例外)到最初产生的随机子 集中。如果在步骤330中发现决策树的例外，则在步骤340中一个或 多个例外被插入到窗口W中，程序控制重复步骤320。如果在步骤330 中没有发现决策树的例外，则程序控制结束。这一过程持续到从一个 迭代到下一个迭代中没有发现性能的改进为止。
在进一步的改变中，基于一个用户喜欢和不喜欢什么，用户在何 处为节目评级，如1-5级的假定，给决策树处理300一些例子。这 些等级可以以这样的方式被合并到决策树中，以便增加一些偏重。就 是说，仅当用户的等级超过预定(或用户指定的)值，如3时，决策 树处理300增加错误分类的例子。换句话说，用户指出对于他或她来 讲系统能够推荐他或她喜欢或不喜欢的节目是多么重要。在这种方式 中，本发明将更适合于用户的喜欢或不喜欢。同样，当系统不试图覆 盖所有例子时，将会有性能上的改进。
图4是一个描述体现本发明原理的示例决策树建立子程序400的 流程图；如图4所示，在步骤410中，建立子程序400的决策树最初 选择能够最小化下面的平均信息量函数H的最好的属性。
H＝∑-P(i)log P(i)
其中P(i)为是与第i个类相关的概率。而后，在步骤420中 通过该属性将训练实例分类加入到子集中。
最后，在步骤430中递归重复该过程，直至每个子集包含一个类 型的实例或满足一个预定的统计标准。然后程序控制返回到决策树处 理300(步骤330)。
决策树例子
图5是一个根据熟知的技术产生一个决策树的样本表500。如图 5所示，表500包括多个记录，每个记录关联到属性的尺寸、颜色和 外表的不同组合，分别在栏520、530、540中标出。每个记录都被分 类到一个给定的类，在栏510中标出。
根据建立子程序400的决策树，决策树是在步骤410中通过首次 计算每个属性(尺寸、颜色、外表)的平均信息量来构建的。计算如 下：
尺寸： $H=\frac{1}{6}[-\frac{1}{1}\log \frac{1}{1}]+\frac{4}{6}[-\frac{2}{4}\log \frac{2}{4}-\frac{2}{4}\log \frac{2}{4}]+\frac{1}{6}[-\frac{1}{1}\log \frac{1}{1}]=0.462$
颜色： $H=\frac{3}{6}[-\frac{2}{3}\log \frac{2}{3}-\frac{1}{3}\log \frac{1}{3}]+\frac{3}{6}[-\frac{3}{3}\log \frac{3}{3}]=0.318$
外表： $H=\frac{5}{6}[-\frac{3}{5}\log \frac{3}{5}-\frac{2}{5}\log \frac{2}{5}]+\frac{1}{6}[-\frac{1}{1}\log \frac{1}{1}]=0.56$
在步骤420中，选择属性“颜色”作为根结点605，因为该属性 具有最小的平均信息量。所以，从属性中移除属性“颜色”，在步骤 430中重复这一过程，如下：
尺寸： $H=\frac{1}{3}[-\frac{1}{1}\log \frac{1}{1}]+\frac{2}{3}[-\frac{2}{2}\log \frac{2}{2}]=0$
外表： $H=\frac{3}{3}[-\frac{2}{3}\log \frac{2}{3}-\frac{1}{3}\log \frac{1}{3}]=0.636$
在第二次审核数据时，在步骤420选择属性“尺寸”作为第二个 决策节点610，因为该属性具有最小的平均信息量。得到的决策树如 图6所示。
一旦产生了依照本发明的决策树200，该决策树就可以被应用到 一个电子节目指南140中来确定一套将可能满足用户兴趣的电视节 目。对于电子节目指南140中的每一个节目，要贯穿决策树来把该节 目归类到一个叶节点。基于该指定的叶节点，得出一个给定的节目是 正的或负的推荐。
应当清楚，这里显示和描述的实施方案和变动不仅仅是说明本发 明的原理，那些本技术领域的熟练人员可以在不背离本发明的范围和 宗旨的前提下对本发明进行不同的修改。