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

暂无

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