稍微赚一下文章数跟批币XD
==
5.1 树(Trees)
(1) 请使用 C 语言或任何的虚拟码(pseudo-code)来写出一个算法(algorithm)。
而给予线索二叉树(threaded binary tree)上的一节点(node)，该算法可以
有效率的找出该节点的双亲(parent)。
(2) 请使用 C 语言或任何的虚拟码来写出一个时间复杂度算法(time complexity)
为 O(N) 的算法，来检查一个拥有 N 个节点的树是否为二元搜寻树(binary
search tree)。请简要地解释为什么你写的算法时间复杂度为 O(N)。
(3) 请使用 C 语言或任何的虚拟码来写出在课本第 230 页，练习题 5 当中所描述
的算法(5.6 小节)。请简要地解释你的算法时间复杂度为何。
(4) 请使用 C 语言或任何的虚拟码来写出在课本第 243 页，练习题 6 当中所描述
的算法(5.8 小节)。
(5) 证明你在 5.1(4) 当中所演算法的时间复杂度。
(6) 课本第 247 页，练习题 2 (5.9 小节)。
(7) 课本第 247 页，练习题 4 (5.9 小节)。
5.2 决策树(Decision Tree)
在这个问题中，我们会探究树在人工智能(Articial Intelligence)与机器学习(Machine
Learning)这两个领域上的一种应用。决策树在机器学习上是最早被利用的工具之一。在
决策树中，非叶节点(non-leaf node)代表着我们所考虑的选择(choice)或因素(factor)
，而叶节点(leaf node)则代表了我们在上述因素下最后做出的决定。为了简单起见，我
们只考虑拥有二元性因素(binary factor)的决策树，也就是，二元决策树(binary
decision tree)。
例如：下面的树是一个决定要不要打高尔夫球的二元决策树。如果天气是阴天(cloudy)
的话，则我们会决定去打高尔夫球；如果不是阴天的话，我们会检查今天有没有刮风
(windy)，如果刮风的话，我们只会在天气晴朗(clear)且不潮溼(humid)的情况下去打高
尔夫球。另一方面，如果没有刮风的话，我们只会在没有下雨(rainy)但潮湿的情况下不
去打高尔夫球。
图请见作业的档案。
这样的决策树也被称为"分类树(classification tree)"。它把（晴天，雨天，潮湿）这
三种不同的情况，分类到决策类别 play? = {是(yes), 否(no)} 当中。决策树并不是任
意生成的。事实上，它是借由给予一连串例子，让程式自动学习所得到的结果。换句话
说，你可以用这些例子来教导你的程式。
表请见作业的档案。
决策树可以由上往下以递回的方式来生成。首先，我们需要找到根的分支。在上表的例子
当中，总共有 9 个是及 5 个否（9Y5N）。如果我们考虑的是天气是否晴朗这个因素，我
们可以将这 14 个例子分成 2 个分支：在天气晴朗的分支上有 2Y3N，而另外一个分支则
有 7Y2N；如果我们考虑的因素改为是否为阴天，我们也可以将这 14 个例子分成两个分
支：在阴天的分支上有 4Y0N，而另一个分支则有 5Y5N。我们可以继续确认可能的分支条
件。
要建立好的分支选择，你可以检查在分支之后的乱度(confusion)。对于一个aYbN的
混合物(mixture)，其乱度定义为：
confusion(a, b) = 1 - ( a / ( a + b )) ^ 2 - ( b / ( a + b )) ^ 2
而 (c+e)Y(d+f)N 在分支成为 cYdN 及 eYfN 之后，其总乱度为：
total(c, d, e, f) = (c + d) * confusion(c, d) / (c + d + e + f)
+ (e + f) * confusion(e, f) / (c + d + e + f)
例如：如果以天气是否晴朗来当作分支依据的话，其总乱度为：
5 / 14 * (1 - (2 / 5) ^ 2 - (3 - 5) ^ 2)
+ 9 / 14 * (1 - (7 / 9) ^ 2 - (2 / 9) ^ 2)
如果我们可以找到一个分支条件使得分支完后的总乱度最小，则可以限制住我们产生出
任意的分支。
现在，当我们对根找到一个好的分支，则我们可以把所有的例子分成两个子集合：一个是
根左孩子(left-child)，另一个则是根的右孩子(right-child)。而同样的方法可以分别
用在这两个孩子上，使其又个别产生出两个孩子，依循此法做递回，则可以建出整棵决策
树来。
递回？那终止条件该是什么？如果该节点已经没有乱度存在的话，也就是所有例子组成
aY0N 或 0YbN 的情形时，我们就不需要在继续分支下去了，也就是说该节点在决策树当
中是叶子(leaf)。在这种状况之下，我们可以宣告该叶子有一个最终的决定（是或否）。
下列是一个简单的决策树生成算法：
DecisionTree(examples)
if 在examples当中没有乱度 then
建立一个拥有最终决定的叶子节点并将其回传
else
找到一个可以将总乱度化为最小的分支条件，并将其存在根当中
依此分支条件将example分成两个子集合，分别分配给左小孩和右小孩
令左子树 = DecisionTree(分配给左小孩的examples)
令右子树 = DecisionTree(分配给右小孩的examples)
回传整棵树
end if
在这个问题当中，你需要写一个会根据所给例子来生成相对应之二元决策树的程式。
有趣的是，对于二元决策树，你可以将其表示为 C 语言中的 if(...){...}else{...}。
也就是说，在你的程式建出二元决策树后，它必须自己产生另外一个程式来对以后的例子
做出决定。
(1) 实作出上述的决策树算法。你的程式必须能读入例子，并输出一段程式码来表示
你的程式根据所给例子所建成的二元决策树（格式请参阅课程网）。
(2) 用图示来说明你在程式内部用来表示决策树的资料结构。请尽可能的明确表示。
(3) 以下表的例子来建构函式 f 的二元决策树，并画出你所得的树。
（表请见作业档案）
(4) 请建出你自己的资料集(data set)，该资料集至少要有两个因素，且至少拥有六个
例子。你的程式必须对该资料集建出一个至少两层的决策树。列出所有的例子、画
出生成的决策树，并简单解释所生成的树。
(5) 如果你的分支方法不是采用最小乱度的分支法，而是采用随机分支法，也就是随机
挑选出一个因素当作分支的条件来做分支。由于随机选取的关系，你可能会重新选
取到在上层已经选过的因素。使用问题 5.2(3) 所给的例子，来比较采用最小乱度
分支法所形成的决策树及采用随机分支法所形成的决策树的平均高度（至少一千次
的平均）。简单说明你的发现。
如果你有兴趣扩展你的程式使其在机器学习上更有用处，则你可以在完成作业后，随时
联络老师。