机器学习恋爱宝典——建棵决策树，看看男神有多远

每天中午小青都会偷偷地站在大学操场边的樱花树下，这里可以看到篮球场的全貌，又不会被聚在场边为篮球队员加油的男男女女发现。她目不转睛地看着在场上挥洒汗水的阿宏，阳光撒在高大的身影上，一切是那么美好。

不知从什么时候开始，小青每天都想见一见阿宏，无论在球场上、在教室里、在图书馆，哪怕只见一面，哪怕阿宏根本不知道她是谁。她打听到了阿宏的课表，会在上课时，找到他附近的位置坐下，想象着他也许已经注意到了自己。她不敢和他讲话，因为他是那么的优秀，而自己笨嘴拙舌，很不擅长与人打交道。但却忍不住地猜想，也许他正好喜欢她这个类型，也许他也正想认识她。

他喜欢什么类型的女孩？自己算不算一个？这些想法在小青脑海中萦绕，如百爪挠心。于是小青搜集到了追求过阿宏的所有女生的信息。

表1 追求过阿宏的女生信息

身处计算机学院、专业方向为机器学习的小青，自然知道决策树是一种对数据进行分类的树形结构。现在每个女生都具有多种特征，如成绩、身高等，同时每个特征又有一些对应的值。这些女生可能与阿宏约会成功或者未成功，这即为她们的分类。这些数据可以作为训练数据来生成决策树，然后使用自己的数据进行预测，从而推断出自己和阿宏交往的可能性。

小青查找了相关资料，发现生成决策树有很多种算法，其中一种常用的，便是ID3算法。要使用ID3算法，则必须要计算信息增益，而信息增益又和信息熵息息相关。信息熵是用来度量随机变量的不确定性的。设x是一个取有限值的离散变量，其概率分布为

那么其信息熵为

可以想象，在X的每个取值的概率都近似时，考察X的一次取值，是难以正确估计到X的值的，因此X的不确定性大。相反假设X取某值的概率为99%，那么就比较确定X很可能取到这个值。而相近的概率会使得H(X)的值变大。因此H(X)越大，说明X的取值越不确定。另一个概念是条件熵，它表示在确定随机变量X的情况下，随机变量Y的信息熵，表示为

信息增益表示的是，当确定了某个特征后，使得整个数据集的确定性增加的量。也就是说，如果小青不知道这15个女生的具体信息，只知道有几个女生约会成功，那么她是没法判断自己应当被归到哪类去的（约会成功与否），不确定性很大。但如果她又多知道了这15个女生的成绩信息，她就有可能从种推断出某些信息，比如男神偏爱成绩好的女生，她就能稍稍确定自己的机会有多大，这就使得分类结果更加确定。也就是知道成绩这一特征的信息，会使得信息熵减少，信息增益变大。

这又涉及到另一问题，即每个特征的分类能力是不一样的。比如可能对于男神来说，女生的身高并不会对约会结果造成任何影响，高也行矮也行，重要的是其他属性，那么身高这个特征就没有任何分类能力。一般来说，信息增益越大，表示知道某一属性对于最终分类的确定性增加的越多，特征分类能力越强。建树时，应首先选择分类能力强的特征，舍弃基本没有分类能力的特征。

了解了这些，小青便使用15个女生的数据开始建立决策树。根据ID3算法，树的每一层都需要计算未使用的特征的信息增益。小青看了下数据，15个女生种，4个和男神约会了，11个没有，据此她写下了计算过程：

之后依次按照条件熵公式：

分别计算15个女生8个特征的信息增益。小青看了下成绩特征，发现15个女生种，4个成绩很好、6个一般、5个较差。而在4个成绩好的种，1个成功和阿宏约会了；在6个成绩一般的种，没有和男神约会的；在5个成绩较差的种，3个和男神约会。将这些数据代入公式，可得成绩特征的信息增益为0.089。

以同样的方法，小青算出了所有特征的信息增益，并选择信息增益最大的样貌特征作为第一层决策树结点，并按照此特征的值将所有数据分开。

可以发现，所有样貌为很漂亮的女生，都和阿宏约会成功；而样貌较差的女生，都没有和阿宏交往成功；而长相一般的，只有少数约会成功。小青看到这个结果，轻轻叹了口气。也许我不算丑吧，也许还有希望，也许……她暗暗想着，继续处理数据。

方法是一样的，但是现在只需考虑相貌一般的女生的数据集，因为漂亮和一般的数据集，分类是一样的了，就没必要再处理了。小青计算出了此数据集中除样貌外所有特征的信息增益比。

情商和身材得到了一样的数值，按照算法，随意选择一个即可。小青选择了情商，并以此分割了数据集。在相貌一般的数据集中，所有情商高的，都和阿宏约会成功；而所有情商低的都约会失败；一般的有少数成功。

小青不再看电脑，她静静地看向窗外。她知道自己不擅长与人交往，也从不是一个讨喜的人。她总觉得很多人在讲话时在打着她不懂的暗语，暗号对上了，他们便会心地相视一笑，仿佛他们参加了什么神秘团体。在一旁的她却怎么也理解不了，自然也无法加入这个神秘团体。她很羡慕这些人，他们在社会中收放自如，一举一动仿佛都在嘲笑着像她这样，在社交场合中只会傻傻陪笑的人。

她知道自己的情商不高，甚至是低的。但这次她不想就这么放弃。情商是可以练习的，也许无法做到如鱼得水，但或许可以不像现在这么糟糕。她想，这一次，不仅仅为了阿宏，也是为了自己。面对喜欢的人，连正常的交流都做不到，她不想这样下去了。

完成最后一点数据吧，她想，看看普通情商的人还有什么可以吸引阿宏的。小青使用样貌普通且情商普通的女生的数据集，按照之前方法计算了剩余特征的信息增益，其中身材特征的信息增益最大。使用身材特征分割数据集，发现仅有身材很好的女生和阿宏成功交往。至此决策树已生成成功。

夜已经深了。小青也想清楚了。对于遥不可及的男神，无非两种做法：让他喜欢现在的自己，或者变成他喜欢的样子，哪一个都不简单。但有时喜欢一个人并非只为了和他在一起。在喜欢一个人的过程中，你可能才会了解，自己究竟想要成为什么样的人。而在你眼里发光的那个人，正是你成长的动力。

小青合上电脑，钻进被窝。

“明天或许一切都不一样了”。

===================================

我们致力于推广普及人工智能(AI), 让AI走进每个人的生活~

欢迎分享AI相关的人物轶事、工业应用、科普常识、动态前沿~

《万众AI》 2017年第十一期