论文部分内容阅读
摘 要：提出基于P-tree的多决策树分类基因表达数据方法PTMDT(P-tree multi-decision tree)。
关键词：基因表达 分类 P-tree
中图分类号TP311.132.3 文献标识码 A 文章编号：1002-2422(2007)03-0050-02
使用The Peano Count Tree(P-tree)结构和的逻辑运算操作，快速地构造出基因表达数据的决策树，用于基因表达数据的分类。实验结果表明PTMDT方法不但可以取得良好的分类精确度，而且在计算速度方面远远好于其它方法。
1 基因表达数据的裁减和离散化
1．1基因表达数据的裁减
基因表达数据是通过基因芯片实验获得的。通常基因表达数据以矩阵形式保存，矩阵第i行对应于第i个基因，第i列对应于第j个实验样本，而矩阵的每个元素aij记录了第i个基因在第j个样品中的表达水平。
在基因数据中，有一部分基因表现的特征在不同类别中差别不明显，被称为不相关基因，因为不相关基因对分类不起作用，所以可以裁减掉这些不相关基因。具体裁减方法是：先把一个基因的表达数据按照已知类别分组，分别计算每组数据的期望和方差。然后计算期望的最大值和最小值的差值，如果这个基因各个类别的方差值都小于这个差值，那么认为这个基因的特征表现在不同类别下是明显的，要保留这个基因，否则认为是不相关基因，把它裁减掉。
1．2 离散基因表达数据
为了利用P-tree结构建立决策树，首先需要对给定的基因表达数据进行离散化处理。例如基因表达数据，根据对数据大小范围的观测，把它们离散成Io、l1、I2、I3四个部分，Io=[0，1]、I1=[1，2]、12=[2，3]、13=[3，4]，每一部分用一个二进制比特串表示，设Io=00，I1=01，I1=10，I3=11。通过这样的离散化处理，表l中的基因表达数据转变成表2中的形式，这样就可使用P-tree结构表示基因表达数据了。
PTMDT方法基于P-tree结构，结合决策树实现了对基因表达数据的分类。使用P-tree结构的目的主要有两点。第一，使用P-tree结构计算信息增益时只需使用P-tree的AND操作，AND操作速度快，减少了建立决策树的时间；第二，在使用P-tree结构建立决策树的过程中，不需要重复扫描数据集获得决策树中间结点包括的子数据集，这是因为和树中结点相对应的P-tree就表示了这个结点包含的数据集，即P-tree中表示为1比特的位置对应的数据就是被该结点包含的数据。
决策树是数据挖掘分类常用的一种方法，决策树中的每个非叶结点选择具有最大信息增益的属性作为测试属性。使用P-tree表示的数据，可以通过如下方法计算一个属性的信息增益值。假设Bo是类别属性，B1,B2,B3是非类别属性．决策树中的每个结点都存储相应的决策路径信息，即存储从树根结点到本结点所经过的决策属性和相应的属性值，如图l中结点N09的决策路径是“B2,,0011,B3,1000”。使用RC表示P-tree根结点的数值。对于给定决策路径B[1]，V[l]，B[2]，V[2]，…，B[t]，V[t]的结点N，结点N对应的P-tree使用下面的公式计算结点N的I(P)
在构造决策树时，首先计算每个基因的信息增益值，选择具有最大信息增益的基因作为决策树根结点的测试属性。根据这个基因所有的属性值，把结点划分为多个孩子结点，然后递归地计算每个孩子结点。
针对单决策树分类精度低的问题，PTMDT方法采用了多决策树分类方法。构建多棵决策树时对树根结点决策基因的选择是依照从最优逐渐递减的原则，即第一棵决策树选择信息增益最大的基因作为根结点的决策基因，第二棵决策树选择信息增益第二大的基因作为根结点的决策基因，以此类推。不同的决策树对同一测试数据可能得到不同的分类结果，取出现次数最多的类型作为测试数据的分类结果。
3 实验结果
为了验证PTMDT方法的有效性，实验应用small roundrole-cell tumors(SRBCT)数据集进行，其中包含63个训练样本和25个测试样本，每个样本包含2303个基因表达值，分成四个类别：EWS(23)，RMS(20)，NB(12)，BL(8)。
对63个训练样本，PTMDT方法的训练精度是100％。表3是用PTMDT方法对20个测试样本进行多决策树分类的时间和精确度，其中运行时间是指PTMDT方法开始运行直到得到最终分类结果总共花费的时间。
给出了PTMDT方法与基于SVM的OVA方法、TSS方法的运行时间和分类精确度的比较。从比较结果可知PTMDT算法在运行时间方面明显优于OVA和TSS方法，在精确度方面接近TSS方法，略高于OVA方法。
4 结束语
文中提出了一个基因表达数据分类方法PTMDT。利用p-tree结构，使得构建决策树的时间大大缩短，并结合多决策树技术，提高了分类的精确度。从实验结果可看出，PT-MDT方法与目前已知优秀分类基因表达数据方法相比，具有良好的分类精确度，并且运行速率较快。
关键词：基因表达 分类 P-tree
中图分类号TP311.132.3 文献标识码 A 文章编号：1002-2422(2007)03-0050-02
使用The Peano Count Tree(P-tree)结构和的逻辑运算操作，快速地构造出基因表达数据的决策树，用于基因表达数据的分类。实验结果表明PTMDT方法不但可以取得良好的分类精确度，而且在计算速度方面远远好于其它方法。
1 基因表达数据的裁减和离散化
1．1基因表达数据的裁减
基因表达数据是通过基因芯片实验获得的。通常基因表达数据以矩阵形式保存，矩阵第i行对应于第i个基因，第i列对应于第j个实验样本，而矩阵的每个元素aij记录了第i个基因在第j个样品中的表达水平。
在基因数据中，有一部分基因表现的特征在不同类别中差别不明显，被称为不相关基因，因为不相关基因对分类不起作用，所以可以裁减掉这些不相关基因。具体裁减方法是：先把一个基因的表达数据按照已知类别分组，分别计算每组数据的期望和方差。然后计算期望的最大值和最小值的差值，如果这个基因各个类别的方差值都小于这个差值，那么认为这个基因的特征表现在不同类别下是明显的，要保留这个基因，否则认为是不相关基因，把它裁减掉。
1．2 离散基因表达数据
为了利用P-tree结构建立决策树，首先需要对给定的基因表达数据进行离散化处理。例如基因表达数据，根据对数据大小范围的观测，把它们离散成Io、l1、I2、I3四个部分，Io=[0，1]、I1=[1，2]、12=[2，3]、13=[3，4]，每一部分用一个二进制比特串表示，设Io=00，I1=01，I1=10，I3=11。通过这样的离散化处理，表l中的基因表达数据转变成表2中的形式，这样就可使用P-tree结构表示基因表达数据了。
PTMDT方法基于P-tree结构，结合决策树实现了对基因表达数据的分类。使用P-tree结构的目的主要有两点。第一，使用P-tree结构计算信息增益时只需使用P-tree的AND操作，AND操作速度快，减少了建立决策树的时间；第二，在使用P-tree结构建立决策树的过程中，不需要重复扫描数据集获得决策树中间结点包括的子数据集，这是因为和树中结点相对应的P-tree就表示了这个结点包含的数据集，即P-tree中表示为1比特的位置对应的数据就是被该结点包含的数据。
决策树是数据挖掘分类常用的一种方法，决策树中的每个非叶结点选择具有最大信息增益的属性作为测试属性。使用P-tree表示的数据，可以通过如下方法计算一个属性的信息增益值。假设Bo是类别属性，B1,B2,B3是非类别属性．决策树中的每个结点都存储相应的决策路径信息，即存储从树根结点到本结点所经过的决策属性和相应的属性值，如图l中结点N09的决策路径是“B2,,0011,B3,1000”。使用RC表示P-tree根结点的数值。对于给定决策路径B[1]，V[l]，B[2]，V[2]，…，B[t]，V[t]的结点N，结点N对应的P-tree使用下面的公式计算结点N的I(P)
在构造决策树时，首先计算每个基因的信息增益值，选择具有最大信息增益的基因作为决策树根结点的测试属性。根据这个基因所有的属性值，把结点划分为多个孩子结点，然后递归地计算每个孩子结点。
针对单决策树分类精度低的问题，PTMDT方法采用了多决策树分类方法。构建多棵决策树时对树根结点决策基因的选择是依照从最优逐渐递减的原则，即第一棵决策树选择信息增益最大的基因作为根结点的决策基因，第二棵决策树选择信息增益第二大的基因作为根结点的决策基因，以此类推。不同的决策树对同一测试数据可能得到不同的分类结果，取出现次数最多的类型作为测试数据的分类结果。
3 实验结果
为了验证PTMDT方法的有效性，实验应用small roundrole-cell tumors(SRBCT)数据集进行，其中包含63个训练样本和25个测试样本，每个样本包含2303个基因表达值，分成四个类别：EWS(23)，RMS(20)，NB(12)，BL(8)。
对63个训练样本，PTMDT方法的训练精度是100％。表3是用PTMDT方法对20个测试样本进行多决策树分类的时间和精确度，其中运行时间是指PTMDT方法开始运行直到得到最终分类结果总共花费的时间。
给出了PTMDT方法与基于SVM的OVA方法、TSS方法的运行时间和分类精确度的比较。从比较结果可知PTMDT算法在运行时间方面明显优于OVA和TSS方法，在精确度方面接近TSS方法，略高于OVA方法。
4 结束语
文中提出了一个基因表达数据分类方法PTMDT。利用p-tree结构，使得构建决策树的时间大大缩短，并结合多决策树技术，提高了分类的精确度。从实验结果可看出，PT-MDT方法与目前已知优秀分类基因表达数据方法相比，具有良好的分类精确度，并且运行速率较快。