基于模糊决策树的个性化推荐系统 http://www.paper.edu.cn 王璇 河海大学计算机及信息工程学院，江苏南京（210098） Email: wangxuan19842003@yahoo.com.cn 摘 要：本文通过模糊决策树产生模糊规则，然后利用模糊推理系统进行个性化推荐，最后， 结合本文提出的推荐系统模型，设计了一个模糊推荐系统的软件构架，实现了系统原型，通 过对系统进行推荐实验验证了基于模糊的个性化推荐系统的有效性和推荐结果的准确性。 关键词：模糊决策树; 个性化推荐; 逻辑推理 中图分类号：TP 1. 引言 当今社会信息膨胀，面对如此大的数量级的信息，想要找到所需的也是一件不容易的事 情。搜索引擎的出现为用户提供极大的方便，但是搜索引擎也有需要关键字、所得非所需等 缺点，因此，很多学者提出个性化服务的概念。 个性化服务可以针对不同的用户提供不同的服务，帮助用户找到所需要的信息，同时也 可以满足用户对个性化的需求。个性化服务技术正在不断成熟，越来越多的新技术被应用到 现实中。个性化技术已成为一项迫切而重要的课题，个性化推荐技术的研究将具有很高的学 术价值和应用前景。 传统个性化推荐系统面临的另一个问题是对于商品的描述过于单调, 商品的属性被简 单的用是或否所表示, 在一些具有模糊度的属性描述上表达不力。以电影推荐中{科幻, 爱情, 恐怖, 武侠, 枪战}论域为例, 一部电影通常同时对应于论域中好几项,每一项的侧重都有所 不同。如果简单地用0 或1 描述。通过分析发现, 人的喜好很难用喜欢或不喜欢来进行决断, 其本身也是一个具有一定模糊度的概念。而模糊逻辑很好的解决这个问题，通过模糊逻辑能 比较准确的反映用户喜欢或者不喜欢的程度，并不是简单的非此即彼。 本文介绍了Fuzzy-ID3算法生成模糊规则，然后将这些规则代人模糊推理中，进行个性 化推荐。 2. 模糊决策树简介 当进行模糊推理的时候，模糊规则的获得就显得很重要。模糊规则的好坏直接影响到整 个个性化推荐系统的准确度。传统使用的统计方法,基本上只能获得这些数据的表层信息,而 不能挖掘出数据间潜在的相关性。这就需要有一种能够从这些海量数据中寻求有用信息的工 具,数据挖掘就是在这种背景下应运而生的。 模糊决策树算法是传统决策树算法的一个扩充和完善,使得决策树学习的应用范围扩大 从而能够处理不确定性。 它合理地处理了学习和推理过程中的不精确信息,具有更强的分类 能力及稳健性,由于能生成不同水平和不同置信度的规则,为决策者提供丰富的决策信息。 目前,决策树已成为一种重要的数据挖掘方法,而在决策树构造中, ID3 算法是最具有影 响的一种决策树生成算法,是1986 年由Quinlan提出的,但该算法不能很好地处理数据模糊性 和不确定性问题,而模糊推理恰好补充了这一缺陷。模糊决策树利用模糊划分的概念,解决了 数值属性问题;通过引入模糊集理论中的模糊隶属函数,来处理模糊(不确定性) 数据集的学 习问题。模糊决策树作为一种数据挖掘方法,集成了模糊理论和决策树的优点,不仅具有很强 的决策分析能力,而且能很好地处理模糊性和不确定性问题[1]。 - 1 - 

http://www.paper.edu.cn 3. 模糊决策树算法 构造模糊决策树最主要的且一般使用的有2种算法。Fuzzy ID3 算法就是其中之一，它 最初由 Quinlan在清晰事例中提出后由许多研究者发展完善。Fuzzy ID3 算法所使用的启发 式信息是最小模糊熵，将其应用于符号值属性类分明的数据时，也就是经典的ID3算法，它 将模糊理论引入到传统ID3 算法中,以提高决策树处理数值属性和模糊性等问题的能力。第 二种是所提出Yuan和Shaw的Min-ambiguity算法，它与Fuzzy ID3 算法不同之处是使用可能 性分布的不确定性来选择扩展属性[2]。 以下介绍的是Fuzzy ID 3算法： 设 有 一 个 模 糊 化 后 的 示 例 集 合 D={ 1 ,.., ,.., m A 和一个模糊类属性C={ 1 n d ,.., u } ， 每 个 iu 由 n 个 模 糊 特 征 属 性 u u , 2 C }来描述，每个Ai又由模糊语言变量，即属 , A A 1 2 性值组成，表示为 iA ={ 2 , C C A }（i=1，2，..，n）[3]。 ik A A i i 1 , 2 ,.., （1）用户根据实际需求以及所处理数据的特性，选择类别标志属性和决策树的决策属 性集，并确定取定包含度阈值β和割集阈值α，将小于α的隶属度值设为0。FDT 算法中, α体 现了一定的抗干扰性, 当α较大时, FDT 算法能够滤除一些无关的信息, 如应用中某些较少 出现的或正确值附近的波动信息. 但α太大, 也可能滤除某些有用的信息。而β 则体现了模糊 决策规则成立的条件, 即只有规则的包含度大于β, 模糊规则才能成立, 一般情况下β> 0. 5[4]； 为A的一个模糊分割。称 （2）选取所有属性中模糊信息熵最小的属性作为根节点; 模糊信息熵的公式如下： 设A，Ai（i=1，2，3..m） F(u),{Ai|i=1,2..m} M Ai ( ) m ∑ M Al ( ∈ M Ai ( ) m ∑ M Al ( = −∑ H A （ ） log ) ) 1 = m i l 1 = l 1 = A u ( ) M A （ ） = ∑ 其中 （3）如果当前节点满足以下条件,该节点为叶子节点,计算各类的置信度CF 的值, CFi =M ，A（u）为隶属度函数 u U ∈ ( D ∩ Ci)/M ( D)=M ( DCi)/M ( D)，选取最大的作为节点的类别标记并记录,返回; 条件a. 属性已经全部使用; b．某个分类的相对频率大于或等于给定阈值β; c．所有分类的隶属度的总和小于给定阈值γ; （4）否则，对节点进行模糊分割，分割步骤如下： ①对D中的所有属性Ai，计算启发式H(d;Ai)的值，选取使之最大的属性A作为该节点的 测试属性; ②将D按A的模糊属性值进行分割，得到D ∩ A 1 , D ∩ A 2 ,..,D ∩ A N，分别产生新的节 点t1，t2，…，tn; ③依次用D ∩ A 1 , D ∩ A 2 ,..,D ∩ A N代替D，重复步骤2。 模糊基本思想就是避免对某些数值的精确描述, 因此FDT 算法不可避免存在着漏去的 事例, 但随着α和β的上升, 其覆盖率也上升, 而错误率则下降. 实际上, 覆盖率为100% 也 - 2 - 

http://www.paper.edu.cn 不必要, 因为它不可能覆盖领域的全部事实, 就是覆盖了全部训练集, 在测试集中也会出现 训练集之外的事例, 导致出错, 因此达到训练集绝大部分即可[4]。 4. 基于改进模糊决策树的模糊规则 本文将用MovieLens作为训练集，产生模糊规则。MovieLens是明尼苏达州立大学计算 机科学系GroupLens研究小组搜集的主要用于研究个性化算法的数据集，它包括943个用户对 1682部电影的100，000个评分记录，评分值范围为1－5，每个用户至少评价了20部电影[5]。 当将模糊决策树用于挖掘用户模糊兴趣规则时，由于设计到用户的兴趣模型，本体提 出一种加权的模糊决策树，本算法与一般的模糊决策树的算法一个不同的地方是在计算模糊 增益时加入一个权值，使得挖掘出的规则更能与用户的兴趣模型相合。而其他的步骤与一般 的糊决策树的算法相同。 具体的模糊增益的计算公式如下： I(A;B)=q*( H(A)-H(A|B)) ,其中q为权值 首先计算权值q。先将选取movieLens的一部分作为训练集。通过sql语句查询出训练集 中用户的性别，年龄，职业，以及对某一类电影的评分。比如说：可以查到用户1的性别为 男，年龄为23，职业为作家，以及他对动作类电影的评分。将年龄作为一个模糊集合，查询 的用户部分作为条件部分，对某一类电影的评分高低做为结论模糊集合，通过普通的模糊决 策树算法，得到形如如下的模糊规则： 如果用户性别为男，年龄为年轻，职业为工程师，他喜欢科幻电影，cf=0.8； 通过用户的个人信息如性别等，按照模糊规则，找到相应的cf值付给权值q，然后通过sql语 句查询出除了该用户还有多少其他用户也对他评分的电影评过分，然后继续用sql语句查询 这些用户都评分过那些相同的电影，将对相同电影评过分的用户对这些电影的评分提取出 来，这样做的目的是减少系统处理无关数据的花费。在模糊规则被使用前，我们的输入变量 应当被模糊化处理从而得到其对应的模糊集合，这些数据还要经过模糊化才能供模糊决策树 使用。将输入看出如下不同的模糊意义上的集合：用户兴趣度为喜欢、用户兴趣度为一般、 用户兴趣度为讨厌，使用的隶属度函数分别对应为兴趣度讨厌，喜欢用S曲线函数，兴趣度 一般用高斯函数。例如，用户对电影1，2，3，4进行了评分，通过查询得到与他评过相同的 电影用户评分其他电影的数据，然后进行模糊化，得出部分的模糊数据集如表1所示： - 3 - 

表 1 模糊数据集 电影3 电影4 喜 欢 电影1 讨 一 厌 般 0.8 0.9 0 0.6 0.9 0 0.6 0.9 0 0.6 0.9 0 0.6 0.9 0 0.8 0.9 0 0.6 0.9 0 0 0.8 0.9 0 0.9 0.7 0 0.8 0.9 0 0.8 0.9 0 讨 厌 0 0 0 0 0 0 0 0.7 0.9 0 0 0 0 0 一 讨 厌 喜 欢 电影2 一 般 般 0.9 0.7 0.7 0.9 0.8 0.9 0.7 0 0.8 0.9 0 0.9 0.9 0.8 0.9 0 0.8 0.9 0 0.6 0.9 0.8 0.9 0 0.9 0.7 0 0.9 0.9 0.7 0.7 0.9 0.9 0.9 0.7 0 0.8 0.9 0 0.9 0.9 0.7 0.9 0.8 0.9 0.9 0.7 0 喜 欢 0 0.9 0.7 0.7 0.9 0.7 0.7 0 0.7 0.7 0 0.7 讨 厌 0 0.7 0 0 0.7 0 0 0 0 0 0 0 一 般 0.9 0 0.8 0.8 0.9 0.9 0.8 0.8 0.8 0.8 0.8 0.9 http://www.paper.edu.cn 电影5 电影6 喜 欢 0.7 0.9 0.9 0.9 0 0.7 0.9 0.9 0.9 0.9 0.9 0.7 讨 厌 0 0.7 0 0.7 0 0 0.7 0 0 0 0 0 一 般 0.8 0 0.9 0.9 0.8 0.9 0.9 0.9 0.9 0.9 0.9 0.9 喜 一 讨 喜 般 厌 欢 欢 0.9 0 0.6 0.9 0.9 0.7 0.9 0 0.7 0 0.6 0.9 0.6 0.9 0 0 0.9 0 0.6 0.9 0.6 0.9 0.7 0 0.8 0.9 0 0 0.7 0 0.9 0.7 0.8 0.9 0.7 0 0.9 0.7 0.7 0 0.7 0 0.8 0.9 0.8 0.9 0.7 0 然后根据改进的FuzzyID3算法，得到了一个模糊决策树，如图1所示: 讨厌 一般 喜欢 一般 讨厌 讨厌 5 3 1 一般 一般 一般 图 1 模糊决策树 一般 喜欢 喜欢 喜欢 喜欢 喜欢 喜欢 决策树推理是从根节点开始,通过重复地进行属性及其取值的比较,沿着决策树的分支向 下搜索,一直到达叶节点,得到所要的结论。而模糊决策树总是以某个信任度(隶属度) 沿着多 个分支向下的搜索,最终到达多个叶节点(同一实例属于多个叶节点) 。生成决策树之后,接下 来要做的就是将模糊决策树以规则形式表示出来。 模糊决策树的每个节点都对应一条模糊规则，从决策树的根节点到任一个叶节点所形成 的一条路径就构成了一条分类规则。IF—THEN分类规则表达方式易于被人理解[6]。和传统 决策树一样,模糊决策树也可表示成if -then 形式的分类规则。根据图1所生成的模糊决策树 可以得到如下规则： - 4 - 

http://www.paper.edu.cn if 用户对 电影5的感觉为讨厌，then 他用户对 电影6的感觉为一般； if 用户对 电影5的感觉为一般，and 用户对 电影3的感觉为讨厌，then 他用户对 电影 6的感觉为喜欢； if 用户对 电影5的感觉为一般，and 用户对 电影3的感觉为一般，and 用户对 电影1 的感觉为一般，then 他用户对 电影6的感觉为一般； if 用户对 电影5的感觉为一般，and 用户对 电影3的感觉为一般，and 用户对 电影1 的感觉为讨厌，then 他用户对 电影6的感觉为一般； if 用户对 电影5的感觉为一般，and 用户对 电影3的感觉为一般，and 用户对 电影1 的感觉为喜欢，then 他用户对 电影6的感觉为喜欢； if 用户对 电影5的感觉为一般，and 用户对 电影3的感觉为喜欢，then 他用户对 电影 6的感觉为喜欢； if 用户对 电影5的感觉为喜欢，then 他用户对 电影6的感觉为喜欢 将得到的规则代入个性化推荐系统，即能实现基于模糊推理的个性化服务。 5. 结束语 由于使用了模糊逻辑，这样使基于模糊推理的个性化系统更加符合人的思维习惯，并且 这样得到的模糊规则更加的切合实际，相当于传统的规则，更加准确。 模糊决策树作为一种数据挖掘方法， 继承了模糊理论和决策树的优点， 不仅具有很强 的决策分析能力，而且能很好地处理模糊性和不确定性问题。另外，模糊决策树学习是以实 例为基础的归纳学习，还能实现知识的自动获取与表示，且所得的知识具有很高的推理效率。 本文的创新在于将改进的模糊决策树算法应用到个性化推荐系统上，提出了一种用模糊 决策树挖掘产生模糊规则，然后代人模糊推理进行个性化推荐的方法。实验证明这种方法相 当于普通规则的个性化推荐系统，准确率有很大的提高。 参考文献 [1] 姚笑秋 ,何仁刚 ,陆秋．《模糊决策树在高校师资管理中的应用》【J】，计算机技术与发展，2007/05： Fuzzy Decision Tree Wang Xuan College of Computer & Information Engineering,Hohai University, Nanjing(210098) Abstract In this paper, Fuzzy rules are made by the fuzzy decision tree, then the system make fuzzy reasoning and produce personalized recommendations. Finally, this paper designed fuzzy recommend system software architecture and the system prototype. The results with experimental verification of the fuzzy-based personalized recommendation system are considered to be effectiveness and accuracy. Keywords: fuzzy decision tree; personalized Recommendation; logic inference - 5 - 20-26 1999/07：825-828 [2] 王金凤，王熙照．《两种模糊决策树算法的对比研究》【J】，计算机工程与应用，2003/29：92-95 [3] 谢竞博．《关于模糊决策树生产过程中启发式算法的研究》【D】，保定：河北大学，2004 [4] 娄臻亮,张永清．《模糊决策树算法及其在注塑模浇口设计中的知识获取》【J】，上海交通大学学报， [5] 张丙奇．《个性化需求的描述、获取与推断—案例研究》【D】，北京：中国科学院研究生院，2005 [6] 王煜，王正欧．《基于模糊决策树的文本分类规则抽取》【J】，计算机应用，2005/07：1634-1637 Personalized Recommendation System Base Of