猪小花1号

个人签名

282篇博客

决策树技术在交友类产品中的应用(上篇)

猪小花1号2018-08-24 11:02

1.    概述

决策树算法是一种归纳分类算法,它通过对训练集的学习,挖掘出有用的规则,用于对新集进行预测。决策树算法可设计成具有良好可伸缩性的算法,能够很好地与超大型数据库结合,处理相关的多种数据类型,并且,其运算结果容易被人理解,其分类模式容易转化成分类规则。因此,在过去的几十年中,决策树算法在机器学习(machine learning)和数据挖掘( data mining) 领域一直受到广泛地重视。本文将介绍决策树在交友类产品中的应用,重点将结合交友产品中用户偏好数据集阐述决策树的构造过程,并对常见的决策树构建算法进行对比。此外,本文介绍了决策树模型在交友类产品中的实际运用。


2.    决策树介绍

本文通过交友应用中一个用户交友偏好的实例,对决策树相关的一些概念进行详细的介绍。


2.1 决策树结构概述

2.1是某一个用户Alice交友对象的属性以及该用户对于这些对象的喜好程度。属性包括姓名年龄职业月薪......喜好程度,每一行是一个用户对象的样本,每一列是一个属性(字段)。这里把这个表记做数据集D。

此处需要解决的问题是,根据数据集D,建立一个用户偏好分析模型,并根据这个模型,产生一系列规则。当某个用户未来的某个时刻遇到新的一个用户时,依据这些规则,即该新用户的年龄、职业、月薪等属性,来预测对其的喜好程度,从而决定是否把这个新的用户推荐出来,以及确定推荐的优先度等等。这里的用户偏好分析模型,就可以用一棵决策树来表示。

在这个案例中,研究的重点是喜好程度这个属性。对于一个用户来说,当给定一个喜好程度未知的客户,要根据他/她的其他属性来估计喜好等级的值是喜欢一般还是不喜欢,也就是说,要把对该用户的喜好程度分到喜好等级为喜欢一般不喜欢3个类别的某一类别中去。这里把喜好等级这个属性称为类标号属性。数据集D信用等级属性的全部取值就构成了类别集合:C={喜欢一般不喜欢”}

(1) 构建决策树


在决策树方法中,有两个基本的步骤。其一是构建决策树,其二是将决策树应用于新数据的预测。大多数研究都集中在如何有效地构建决策树,而应用则相对比较简单。构建决策树算法比较多,常见的算法有ID3C4.5CART等算法。采用其中的某种算法,输入训练数据集,就可以构造出一棵类似于图2.1所示的决策树。

一棵决策树是一棵有向无环树,它由若干个节点分支分裂谓词以及类别组成。

节点是一棵决策树的主体。其中,没有父亲节点的节点称为根节点,如图2.1中的顶部的年龄节点;没有子节点的节点称为叶子节点,如底部用方框标识的一系列节。一个节点按照某个属性分裂时,这个属性称为分裂属性,如根节点按照年龄被分裂,这里年龄就是分裂属性,同理,职业月薪也是分裂属性。每一个分支都会被标记一个分裂谓词,这个分裂谓词就是分裂父节点的具体依据,例如在根节点分裂时,产生两个分支,对应的分裂谓词分别是年龄<30”年龄>=30”。另外,每一个叶子节点都被确定一个类标号,这里是不喜欢一般或者喜欢

基于以上描述,下面给出决策树的定义:

给定一个数据集D={t1,t2,…,tn},其中ti=(ti1,ti2,…tih)D中的第i个样本,i=1,2,…,n,共n个样本;数据集模式包含的属性集A={A1,A2,…Ah},共h个属性;tij是第i个样本的第j个属性。同时给定类别标号集合C={C1,C2,Cm},共m个类别。对于数据集D,决策树是指具有下列3个性质的树:

(a) 每个非叶子节点都被标记一个分裂属性Ai;

(b)  每个分支都被标记一个分裂谓词,这个分裂谓词是分裂父节点的具体规则;

(c)  每个叶子节点都被标记一个类别标号CjC

由此可以看出,构建一棵决策树,关键问题就在于,如何选择一个合适的分裂属性来进行一次分裂,以及如何制定合适的分裂谓词来产生相应的分支。各种决策树算法的主要区别也正在于此。

(2) 修剪决策树

利用决策树算法构建一个初始的树之后,为了有效地分类,还要对其进行剪枝。这是因为,由于数据表示不当、有噪音等原因,会造成生成的决策树过大或过度拟合。因此为了简化决策树,寻找一颗最优的决策树,剪枝是一个必不可少的过程。

通常,决策树越小,就越容易理解,其存储与传输的代价也就越小,但决策树过小会导致错误率较大。反之,决策树越复杂,节点越多,每个节点包含的训练样本个数越少,则支持每个节点样本数量也越少,可能导致决策树在测试集上的分类错误率越大。因此,剪枝的基本原则就是,在保证一定的决策精度的前提下,使树的叶子节点最少,叶子节点的深度最小。要在树的大小和正确率之间寻找平衡点。

常有的剪枝方法有预剪枝和后剪枝两种。

预剪枝,是指在构建决策树之前,先制定好生长停止准则(例如指定某个评估参数的阈值),在树的生长过程中,一旦某个分支满足了停止准则,则停止该分支的生长,这样就可以限制树的过度生长。采用预剪枝的算法有可能过早地停止决策树的构建过程,但由于不必生成完整的决策树,算法的效率很高,适合应用于大规模问题。

后剪枝,是指待决策树完全生长结束后,再根据一定的准则,剪去决策树中那些不具一般代表性的叶子节点或者分支。这时,可以将数据集划分为两个部分,一个是训练数据集,一个是测试数据集。训练数据集用来生成决策树,而测试数据集用来对生成的决策树进行测试,并在测试的过程中通过剪枝来对决策树进行优化。


 (3) 生成预测规则


在构建一棵决策树并进行优化之后,就可以根据这棵决策树来生成一系列规则。这些规则往往采用条件判断,即if then…”的形式。从根节点到叶子节点的每一条路径,都可以生成一条规则。这条路径上的分裂属性和分裂谓词形成规则的前件(if部分),叶子节点的类标号形成规则的后件(then部分)。

例如,图2.1的决策树可以形成以下5条规则:

利用以上规则,当出现未知类别的观测样本时,即可根据其年龄、职业、月薪等属性预测该样本是属于哪一个喜好等级的类别。

此外,若要决策树能够输出连续的预测值,可以将决策问题看成是一个回归问题从而建立回归树。

2.2 决策树的构建算法


本文主要介绍经典的ID3C4.5构建算法


ID3算法是最有影响力的决策树算法之一,由Quinlan提出。然后由于ID3算法的存在某些弱点,因此被改善之后得到了C4.5算法。


2.2.1 ID3算法


任何一个决策树算法,其核心步骤都是为每一次分裂确定一个分裂属性,即究竟按照哪一个属性来把当前数据集划分为若干个子集,从而形成若干个树枝

ID3算法采用信息增益为度量来选择分裂属性的。哪个属性在分裂中产生的信息增益最大,就选择该属性作为分裂属性。而信息增益,则借鉴了信息熵的概念。熵是数据集中的不确定性、突发性或随机性的程度的度量。当一个数据集中的记录全部都属于同一类的时候,则没有不确定性,这种情况下的熵为0

例如在一次分裂中,数据集D被按照分裂属性年龄分裂为两个子集D1D2,如图2.2所示。

其中,H(D)H(D1)H(D2)分别是数据集DD1D2的熵。那么,按照年龄将数据集D分裂为D1D2所得到的信息增益为:

其中,P (D1)D中样本被划分到D1中的概率,P (D2)D中样本被划分到D2中的概率,P (D1) * H (D1) + P (D2) * H (D2)H (D1)H (D2)的加权和。显然,如果D1D2中的数据越纯,H (D1)H (D2)就越小,信息增益就越大。

按照这个方法,测试每一个属性的信息增益,选择增益最大的属性作为分裂属性。

S是由s个样本组成的数据集,若S的类标号有m个不同的取值,即有m个不同的类Ci,i=1,2,,m。记属于类别Ci的样本集为Si,则数据集S的熵为:

其中,pi是任意样本属于类别Ci的概率,用si/s来估计。

结合到每个属性上,设S的某个属性A具有v个不同的值A={a1,a2,,av},根据属性A将数据集划分为v个不同的子集{S1,S2,,Sv},子集Sj中所有的样本的属性值都等于aj, j=1,2,,v。在分裂为v个子集后,任意一个子集Sj的熵为:

其中,sij(i=1,2,,m)是子集sj中属于类别Ci的样本,pij=sij/|sj|Sj中的样本属于类别Ci的概率,|sj|是子集sj中的样本数量。

所以,S按照属性A划分的v个子集的熵加权和为:

当按照属性A将数据集S分裂,得到的信息增益计算如下:

决策树分类的基本原则是,数据集被分裂为若干个子集后,要使每个子集中的数据尽可能的,也就是说子集中的记录要尽可能属于同一个类别。套用熵的概念,即要使分裂后各子集的熵尽可能的小。

ID3算法是一个从上到下、分而治之的归纳过程。其核心是:在决策树各级节点上选择分裂属性时,通过计算信息增益来选择属性,以使得在每一个非叶节点进行测试时,能获得关于被测试样本最大的类别信息。其具体方法是:检测所有的属性,选择信息增益最大的属性产生决策树节点,由该属性的不同取值建立分支,再对各分支的子集递归调用该方法建立决策树节点的分支,直到所有子集仅包括同一类别的数据为止。最后得到一棵决策树,它可以用来对新的样本进行分类。

ID3算法描述如下:

ID3算法是一种典型的决策树分析算法,后来发展的许多决策树算法都是以ID3算法为基础发展而来的。

ID3算法的优点在于它构建决策树的速度比较快,它的计算时间随问题的难度只是线性地增加,适合处理大批量数据集。

同时,ID3算法的不足之处也是突出的,包括以下几点。

1ID3算法对训练样本的质量的依赖性很强,训练样本的质量主要是指是否存在噪声和是否存在足够的样本。

2ID3算法只能处理分类属性(离散属性),而不能处理连续属性(数值属性)。在处理连续属性时,一般要先将连续属性划分为多个区间,转化为分类属性。例如年龄,要把其数值事先转换为诸如小于2020~30大于30这样的区间,再根据年龄值落入了某一个区间取相应的类别值。通常,区间端点的选取包含着一定的主观因素和大量的计算。

3ID3算法生成的决策树是一棵多叉树,分支的数量取决于分裂属性有多少个不同的取值。这不利于处理分裂属性取值数目较多的情况。因此目前流行的决策树算法大多采用二叉树模型。

4ID3算法不包含对树的修剪,无法对决策树进行优化。

正因为ID3还存在着许多不足的地方,QuinlanID3算法进行了改进,提出了ID3的改进算法C4.5

    

相关阅读:决策树技术在交友类产品中的应用(下篇)

网易云新用户大礼包:https://www.163yun.com/gift

本文来自网易实践者社区,经作者蒋惟授权发布。