决策树算法

决策树算法借助于树的分支结构实现分类。下图是一个决策树的示例，树的内部结点表示对某个属性的判断，该结点的分支是对应的判断结果;叶子结点代表一个类标。

上表是一个预测一个人是否会购买购买电脑的决策树，利用这棵树，我们可以对新记录进行分类，从根节点(年龄)开始，如果某个人的年龄为中年，我们就直接判断这个人会买电脑，如果是青少年，则需要进一步判断是否是学生;如果是老年则需要进一步判断其信用等级，直到叶子结点可以判定记录的类别。

决策树算法有一个好处，那就是它可以产生人能直接理解的规则，这是贝叶斯、神经网络等算法没有的特性;决策树的准确率也比较高，而且不需要了解背景知识就可以进行分类，是一个非常有效的算法。决策树算法有很多变种，包括ID3、C4.5、C5.0、CART等，但其基础都是类似的。下面来看看决策树算法的基本思想：

算法：GenerateDecisionTree(D,attributeList)根据训练数据记录D生成一棵决策树.

输入：

数据记录D，包含类标的训练数据集;

属性列表attributeList，候选属性集，用于在内部结点中作判断的属性.

属性选择方法AttributeSelectionMethod()，选择最佳分类属性的方法.

输出：一棵决策树.

过程：

构造一个节点N;

如果数据记录D中的所有记录的类标都相同(记为C类)：

则将节点N作为叶子节点标记为C，并返回结点N;

如果属性列表为空：

则将节点N作为叶子结点标记为D中类标最多的类，并返回结点N;

调用AttributeSelectionMethod(D,attributeList)选择最佳的分裂准则splitCriterion;

将节点N标记为最佳分裂准则splitCriterion;

如果分裂属性取值是离散的，并且允许决策树进行多叉分裂：

从属性列表中减去分裂属性，attributeLsit -= splitAttribute;

对分裂属性的每一个取值j:

记D中满足j的记录集合为Dj;

如果Dj为空：

则新建一个叶子结点F，标记为D中类标最多的类，并且把结点F挂在N下;

否则：

递归调用GenerateDecisionTree(Dj,attributeList)得到子树结点Nj，将Nj挂在N下;

返回结点N;

算法的1、2、3步骤都很显然，第4步的最佳属性选择函数会在后面专门介绍，现在只有知道它能找到一个准则，使得根据判断结点得到的子树的类别尽可能的纯，这里的纯就是只含有一个类标;第5步根据分裂准则设置结点N的测试表达式。在第6步中，对应构建多叉决策树时，离散的属性在结点N及其子树中只用一次，用过之后就从可用属性列表中删掉。比如前面的图中，利用属性选择函数，确定的最佳分裂属性是年龄，年龄有三个取值，每一个取值对应一个分支，后面不会再用到年龄这个属性。算法的时间复杂度是O(k*|D|*log(|D|))，k为属性个数，|D|为记录集D的记录数。

主要的路径节点编码是?

国内关于主要基于视觉的机器人导航中的路径节点编码问题的文献并不多见。对基于轨线引导的机器人视觉导航中的停靠位标识进行了设计和识别，停靠位标识为3 × 3 的方格。

利用上述方法，机器人根据识别出的停靠位标识进行停靠并完成特定任务，解决的是简单轨线导航中机器人的停靠问题，并没有涉及复杂导航线交叉路口处路径节点的识别和导航问题。王宁等设计了一种二进制编码方案。

该方案设计容易，算法简单，不失为一种简单有效的路径节点编码方案，但是，由于方块形二进制图案不具有对称性，容易受到摄像头角度问题带来的图像畸变影响，鲁棒性差，同时为了保证机器人从各个方向上识别结果的一致性，必须在路径节点各个方向上都要设置一个同样的节点编码图案，这无疑增加了工程量，也存在节点编码的重复识别问题。为克服该问题，我们提出一种具有各向同性的二进制圆环编码方案，无需重复设置编码图案，实施起来更加简单方便、利于扩展、准确可靠。