首页 » 机器学习实战 » 机器学习实战全文在线阅读

《机器学习实战》9.2 连续和离散型特征的树的构建

关灯直达底部

在树的构建过程中,需要解决多种类型数据的存储问题。与第3章类似,这里将使用一部字典来存储树的数据结构,该字典将包含以下4个元素。

  • 待切分的特征。
  • 待切分的特征值。
  • 右子树。当不再需要切分的时候,也可以是单个值。
  • 左子树。与右子树类似。

这与第3章的树结构有一点不同。第3章用一部字典来存储每个切分,但该字典可以包含两个或两个以上的值。而CART算法只做二元切分,所以这里可以固定树的数据结构。树包含左键和右键,可以存储另一棵子树或者单个值。字典还包含特征和特征值这两个键,它们给出切分算法所有的特征和特征值。当然,读者可以用面向对象的编程模式来建立这个数据结构。例如,可以用下面的Python代码来建立树节点:

class treeNode:    def __init__(self, feat, val, right, left):        featureToSplitOn = feat        valueOfSplit = val        rightBranch = right        leftBranch = left  

当使用C++这样不太灵活的编程语言时,你可能要用面向对象编程模式来实现树结构。Python具有足够的灵活性,可以直接使用字典来存储树结构而无须另外自定义一个类,从而有效地减少代码量。Python不是一种强类型编程语言 ,因此接下来会看到,树的每个分枝还可以再包含其他树、数值型数据甚至是向量。

本章将构建两种树:第一种是9.4节的回归树(regression tree),其每个叶节点包含单个值;第二种是9.5节的模型树(model tree),其每个叶节点包含一个线性方程。创建这两种树时,我们将尽量使得代码之间可以重用。下面先给出两种树构建算法中的一些共用代码。

函数createTree的伪代码大致如下:

找到最佳的待切分特征:      如果该节点不能再分,将该节点存为叶节点      执行二元切分      在右子树调用createTree方法      在左子树调用createTree方法     

打开文本编辑器,创建文件regTrees.py并添加如下代码。

程序清单9-1 CART算法的实现代码

from numpy import *def loadDataSet(fileName):    dataMat =     fr = open(fileName)    for line in fr.readlines:        curLine = line.strip.split(/'t/')        #❶  将每行映射成浮点数        fltLine = map(float,curLine)        dataMat.append(fltLine)    return dataMatdef binSplitDataSet(dataSet, feature, value):    mat0 = dataSet[nonzero(dataSet[:,feature] > value)[0],:][0]    mat1 = dataSet[nonzero(dataSet[:,feature] <= value)[0],:][0]    return mat0,mat1def createTree(dataSet, leafType=regLeaf, errType=regErr, ops=(1,4)):    feat, val = chooseBestSplit(dataSet, leafType, errType, ops)    #❷ 满足停止条件时返回叶节点值    if feat == None: return val    retTree = {}    retTree[/'spInd/'] = feat    retTree[/'spVal/'] = val    lSet, rSet = binSplitDataSet(dataSet, feat, val)    retTree[/'left/'] = createTree(lSet, leafType, errType, ops)    retTree[/'right/'] = createTree(rSet, leafType, errType, ops)    return retTree  

上述程序清单包含3个函数:第一个函数是loadDataSet ,该函数与其他章节中同名函数功能类似。在前面的章节中,目标变量会单独存放其自己的列表中,但这里的数据会存放在一起。该函数读取一个以tab键为分隔符的文件,然后将每行的内容保存成一组浮点数❶。

第二个函数是binSplitDataSet,该函数有3个参数:数据集合、待切分的特征和该特征的某个值。在给定特征和特征值的情况下,该函数通过数组过滤方式将上述数据集合切分得到两个子集并返回。

最后一个函数是树构建函数createTree,它有4个参数:数据集和其他3个可选参数。这些可选参数决定了树的类型:leafType给出建立叶节点的函数;errType代表误差计算函数;而ops是一个包含树构建所需其他参数的元组。

函数createTree是一个递归函数。该函数首先尝试将数据集分成两个部分,切分由函数chooseBestSplit完成(这里未给出该函数的实现)。如果满足停止条件,chooseBestSplit将返回None和某类模型的值❷。如果构建的是回归树,该模型是一个常数。如果是模型树,其模型是一个线性方程。后面会看到停止条件的作用方式。如果不满足停止条件,chooseBestSplit将创建一个新的Python字典并将数据集分成两份,在这两份数据集上将分别继续递归调用createTree函数。

程序清单9-1的代码很容易理解,但其中的方法 chooseBestSplit现在暂时尚未实现,所以函数还不能看到createTree的实际效果。但是下面可以先测试其他两个函数的效果。将程序清单9-1的代码保存在文件regTrees.py中并在Python提示符下输入如下命令:

>>> import regTrees>>> testMat=mat(eye(4))>>> testMatmatrix([[ 1., 0., 0., 0.],        [ 0., 1., 0., 0.],        [ 0., 0., 1., 0.],        [ 0., 0., 0., 1.]])  

这样就创建了一个简单的矩阵,现在按指定列的某个值来切分该矩阵。

>>> mat0,mat1=regTrees.binSplitDataSet(testMat,1,0.5)>>> mat0matrix([[ 0., 1., 0., 0.]])>>> mat1matrix([[ 1., 0., 0., 0.],       [ 0., 0., 1., 0.],         [ 0., 0., 0., 1.]])        

很有趣吧。下面给出回归树的chooseBestSplit函数,还会看到更有趣的结果。下一节将针对回归树构建,在chooseBestSplit函数里加入具体代码,之后就可以使用程序清单9-1的CART算法来构建回归树。