公开/公告号CN104820702A
专利类型发明专利
公开/公告日2015-08-05
原文格式PDF
申请/专利权人 中国地质大学(武汉);
申请/专利号CN201510237748.8
申请日2015-05-12
分类号G06F17/30(20060101);
代理机构42214 武汉华旭知识产权事务所;
代理人刘荣;周宗贵
地址 430074 湖北省武汉市洪山区鲁磨路388号
入库时间 2023-12-18 10:16:50
法律状态公告日
法律状态信息
法律状态
2018-05-22
授权
授权
2015-09-02
实质审查的生效 IPC(主分类):G06F17/30 申请日:20150512
实质审查的生效
2015-08-05
公开
公开
技术领域
本发明涉及一种基于决策树的属性加权方法及文本分类方法,属于人工智能数据挖掘分类技术领域。
背景技术
朴素贝叶斯文本分类器因为其简单性和高效性经常被用来处理文本分类问题,但是它的属性独立假设在使它变得高效的同时在一定程度上影响了它的分类性能。给定一篇文档d,该文档被表示成单词向量的形式<w1,w2,…,wm>,多项式朴素贝叶斯(MNB),补集朴素贝叶斯(CNB)和两者的结合模型(OVA)分别用公式1,2和3来分类文档d。
上述公式中符号C是类标记的集合,是类别c的补集(即除类别c以外的其他类),m是单词的数目,wi(i=1,2,…m)是文档d中出现的第i个单词,fi是单词wi在文档d中出现的频率,先验概率p(c)和能够分别用公式4和5进行估计,条件概率p(wi|c)和分别用公式6和7来估计。
上述公式中n是训练文档的数目,l是文档的类别数目,cj是第j篇文档的类标记,fji是第j篇文档中单词wi的频率,并且δ(·)是一个二元函数,当它的两个参数相同时为1否则为0。
尽管这些文本分类算法已经被证明了较高的性能,他们的条件独立性假设在现实中很少成立。因此通过释放它们的条件独立性来提高文本分类器的分类精度是很自然的。许多方法已经被提出了,例如局部学习、实例加权和属性加权。但是,目前已有的算法都是以花费简洁性和执行时间为代价来提高朴素贝叶斯文本分类器的性能。
如何学习属性的权值在构建一个属性加权的朴素贝叶斯文本分类器中是一个关键的问题。为了学习属性的权值,出现了x2统计的属性加权方法,简单表示为Rw,c。这种加权的朴素贝叶斯分类器通过在训练阶段精确的测量项类之间的依赖来提高基本朴素贝叶斯文文本分类器的性能,因此就结果来说文本分类精度极大受限。
另有一种基于CFS的属性加权方法。这种方法首先执行一个基于关联的属性选择过程(CFS)从整个属性空间中选择最好的属性子集,然后赋予较大的权值给选择的属性和较小的权值给未选择的属性。但是CFS属性加权方法的启发式搜索过程具有过高的时间复杂度,对于高维甚至超过万维的文本数据是不适用的。
发明内容
为了解决现有技术的不足,本发明提供了一种基于决策树的属性加权方法及文本分类方法,改善了原来的朴素贝叶斯文本分类器分类精度,同时维持原来朴素贝叶斯算法的简洁性和时间复杂度。
本发明为解决其技术问题所采用的技术方案是:提供了一种基于决策树的属性加权方法,包括以下步骤:
(1)对于一个已知的训练文档集D,训练文档集D中的任意一篇文档d表示为单词向量形式d=<w1,w2,...wm>,其中wi为文档d中的第i个单词,m为文档d中单词的数目;
利用以下公式计算该训练文档集D中的各个属性的信息增益率:
其中,GainRatio(D,wi)表示单词wi划分训练文档集D的信息增益率, Gain(D,wi)表示单词wi划分训练文档集D的信息增益,SplitInfo(D,wi)表示训练文档集D关于单词wi的分裂信息;
Gain(D,wi)通过以下公式计算:
其中,|Dv|是训练文档集D中单词wi的取值为v的文档数目,Entropy(D)是训练文档集D的熵,通过以下公式计算:
其中,C是类标记的集合,c是C中的一个类标记,p(c)是训练文档集D中类别为c的概率;p(c)通过以下公式计算得到:
其中,n是训练文档集D中的文档数目,s是文档的类别的数目,cj是第j篇文档的类标记,δ(cj,c)表示一个二元函数,当它的两个参数相同时值为1否则为0;
SplitInfo(D,wi)通过以下公式计算得到:
(2)用信息增益率作为划分标准建立决策树,所述决策树为二叉树,二叉树在生长的每一步选择具有最大信息增益率的单词作为测试属性,单词出现的频率为0或者非0作为测试结果;
(3)遍历决策树,记录每个单词wi在决策树中测试的的最小深度di;
(4)对于训练文档集D中的每个单词wi,若其在决策树中出现,则将它的权值Wi设置为否则将它的权值Wi设置为1。
本发明同时提出了一种依托于所述基于决策树的属性加权方法的多项式朴素贝叶斯文本分类方法,通过以下公式对文档d进行分类:
其中,fi表示单词wi在文档d中出现的频率,为已知量;p(wi|c)表示条件概率,通过以下公式计算得到:
其中,fji表示训练文档集D中第j篇文档中出现单词wi的频率,n为训练文档集D中文档的数目,fji和n均为已知量。
本发明同时提出了一种依托于所述基于决策树的属性加权方法的补集朴素贝叶斯文本分类方法,通过以下公式对文档d进行分类:
其中,fi表示单词wi在文档d中出现的频率,为已知量;通过以下公式计算得到:
其中,表示一个二元函数,当它的两个参数相同时值为1否则为0;
表示条件概率,通过以下公式计算得到:
本发明同时提出了一种依托于所述基于决策树的属性加权方法的多项式与补集相结合的朴素贝叶斯文本分类方法,通过以下公式对文档d进行分类:
其中,fi表示单词wi在文档d中出现的频率,为已知量;通过以下公式计算得到:
其中,表示一个二元函数,当它的两个参数相同时值为1否则为0;p(wi|c)表示条件概率,通过以下公式计算得到:
其中,fji表示训练文档集D中第j篇文档中出现单词wi的频率,n为训练文档集D中文档的数目,fji和n均为已知量;表示条件概率,通过以下公式计算得到:
本发明基于其技术方案所具有的有益效果在于:本发明不仅把学习到的权值合并到朴素贝叶斯文本分类器的分类公式中,而且将学到的权值合并到条件概率估计里面,不仅可以改善朴素贝叶斯文本分类器的分类性能,而且也不会招致较高的时间花费。利用依托于基于决策树的属性加权方法的多项式朴素贝叶斯文本分类方法、依托于基于决策树的属性加权方法的补集朴素贝叶斯文本分类方法,以及依托于基于决策树的属性加权方法的多项式与补集相结合的朴素贝叶斯文本分类方法分别对文本进行分类,与现有的基于CFS属性加权方法的文本分类方法相比,避免了启发式搜索过程,具有更低的时间复杂度,同时与基于x2统计的属性加权方法的文本分类方法相比,具有更好的分类精度。在大量标准且广泛使用的文本数据集上的实验结果证明了本发明提出的方法的有效性。
具体实施方式
下面结合实施例对本发明作进一步说明。
本发明提供了一种基于决策树的属性加权方法,包括以下步骤:
(1)对于一个已知的训练文档集D,训练文档集D中的任意一篇文档d表示为单词向量形式d=<w1,w2,...wm>,其中wi为文档d中的第i个单词,m为文档d中单词的数目;
利用以下公式计算该训练文档集D中的各个属性的信息增益率:
其中,GainRatio(D,wi)表示单词wi划分训练文档集D的信息增益率,Gain(D,wi)表示单词wi划分训练文档集D的信息增益,SplitInfo(D,wi)表示训练文档集D关于单词wi的分裂信息;
Gain(D,wi)通过以下公式计算:
其中,|Dv|是训练文档集D中单词wi的取值为v的文档数目,Entropy(D)是训练文档集D的熵,通过以下公式计算:
其中,C是类标记的集合,c是C中的一个类标记,p(c)是训练文档集D中类别为c的概率;p(c)通过以下公式计算得到:
其中,n是训练文档集D中的文档数目,s是文档的类别的数目,cj是第j篇文档的类标记,δ(cj,c)表示一个二元函数,当它的两个参数相同时值为1否则为0;
SplitInfo(D,wi)通过以下公式计算得到:
(2)用信息增益率作为划分标准建立决策树,所述决策树为二叉树,二叉树在生长的每一步选择具有最大信息增益率的单词作为测试属性,单词出现的频率为0或者非0作为测试结果;
(3)遍历决策树,记录每个单词wi在决策树中测试的的最小深度di;
(4)对于训练文档集D中的每个单词wi,若其在决策树中出现,则将它的权值 Wi设置为否则将它的权值Wi设置为1。
本发明同时提出了一种依托于所述基于决策树的属性加权方法的多项式朴素贝叶斯文本分类方法,通过以下公式对文档d进行分类:
其中,fi表示单词wi在文档d中出现的频率,为已知量;p(wi|c)表示条件概率,通过以下公式计算得到:
其中,fji表示训练文档集D中第j篇文档中出现单词wi的频率,n为训练文档集D中文档的数目,fji和n均为已知量。
本发明同时提出了一种依托于所述基于决策树的属性加权方法的补集朴素贝叶斯文本分类方法,通过以下公式对文档d进行分类:
其中,fi表示单词wi在文档d中出现的频率,为已知量;通过以下公式计算得到:
其中,表示一个二元函数,当它的两个参数相同时值为1否则为0;
表示条件概率,通过以下公式计算得到:
本发明同时提出了一种依托于所述基于决策树的属性加权方法的多项式与补集相结合的朴素贝叶斯文本分类方法,通过以下公式对文档d进行分类:
其中,fi表示单词wi在文档d中出现的频率,为已知量;通过以下公式计算得到:
其中,表示一个二元函数,当它的两个参数相同时值为1否则为0;p(wi|c)表示条件概率,通过以下公式计算得到:
其中,fji表示训练文档集D中第j篇文档中出现单词wi的频率,n为训练文档集D中文档的数目,fji和n均为已知量;表示条件概率,通过以下公式计算得到:
将本发明的基于决策树的属性加权方法运用到属性加权的朴素贝叶斯文本分类器(FWNBTC),产生的模型叫做决策树加权的朴素贝叶斯文本分类器(DTWNBTC)。当基分类器分别是多项式朴素贝叶斯(MNB)、补集朴素贝叶斯(CNB)以及两者结合的模型(OVA)时,最终的模型分别称为DTWMNB、DTWCNB和DTWOVA,这三个模型所采用的文本分类方法分别为本发明的依托于基于决策树的属性加权方法的多项式朴素贝叶斯文本分类方法、依托于基于决策树的属性加权方法的补集朴素贝叶斯文本分类方法,以及依托于基于决策树的属性加权方法的多项式与补集相结合的朴素贝叶斯文本分类方法。
将基于x2统计的属性加权方法(Rw,c)分别运用到多项式朴素贝叶斯(MNB)、补集朴素贝叶斯(CNB)以及两者结合的模型(OVA)时,产生的模型分别为Rw,c-MNB、Rw,c-CNB以及Rw,c-OVA。
将基于相关性的属性加权方法(CFS)分别运用到多项式朴素贝叶斯(MNB)、补集朴素贝叶斯(CNB)以及两者结合的模型(OVA)时,产生的模型分别为FWMNB、 FWCNB以及FWOVA。
下面三组实验分别针对三种不同的基分类器对基于不同属性加权方法的分类器进行对比。
实验一:MNB、Rw,c-MNB、FWMNB和DTWMNB的比较。
实验二:CNB、Rw,c-CNB、FWCNB和DTWCNB的比较。
实验三:OVA、Rw,c-OVA、FWOVA和DTWOVA的比较。
三组实验中,15个广泛使用的文本分类标准数据集被测试。这些数据集来自不同领域并且代表不同的数据特征。表1详细描叙了这15个数据集的主要特征,具体的数据可从WEKA平台的网站上下载。需要注意的是,19个标准文本分类数据集中的其他4个大数据没有包含,是因为4个大数据集包含了非常多的属性和文档,所以为了减少实验的运行时间,在实验中,去掉了“la1s”、“la2s”、“new3s”以及“ohscal”这4个数据集。
表2、表4和表6分别显示了各方法在每个数据集上通过10次10折交叉验证的分类精度,表的底部列出了平均分类精度。在所有数据集上的算术平均值提供了一个关于相对性能的整体概述。
接下来,运用Friedman测试比较在多个数据集上比较MNB、Rw,c-MNB、FWMNB和DTWMNB。Friedman测试是重复测量的ANOVA的一个非参数等价。运用Friedman测试获得的算法的平均排序分别总结在表2底部。对于4个算法和15个数据集,FF分别根据具有3和42个自由度:15.829545、21.195531和48.5的F分布来分布。这些值都大于α=0.05时F的临界值F(3,42)。因此拒绝空假设,并且继续运用Nemenyi和Bergmann测试来进一步分析哪些算法对是显著不同的。表3、表5和表7列出了获得的z-values和p-values,并且表明了哪些算法对是显著不同的。
从这些实验结果可以看出,本发明的基于决策树的属性加权方法,运用到各种基分类器产生的新的文本分类方法,很少降低原来朴素贝叶斯文本分类器的性能,并且在许多情况下显著地提高了它们的性能。而且,本发明的基于决策树的属性加权方法,运用于各种基分类器后,明显超出所有其他现有的属性加权方法构建的分类器,优点总结如下:
1、就MNB而言,算法的平均排序是:DTWMNB(1.4),FWMNB(2.0667),Rw,c-MNB(3.0667)和MNB(3.4667);DTWMNB明显好于它的比较对象:MNB,Rw,c-MNB;
2、就CNB而言,算法的平均排序是:DTWCNB(1.3667),FWCNB(2.1333),Rw,c-CNB(2.7667),和CNB(3.7333);DTWCNB明显好于它的比较对象:CNB和Rw,c-CNB;
3、就OVA而言,算法的平均排序是:DTWOVA(1.2667),FWOVA(1.8),Rw,c-OVA(3.4667),和OVA(3.4667);DTWMNB明显好于它的比较对象:OVA和Rw,c-OVA;
4、本发明的基于决策树的属性加权方法应用于三种基分类器时,明显好于所有其他的比较对象:当前存在的基于x2统计的属性加权方法(Rw,c),以及当前存在的基于CFS的属性加权方法。
表1实验中使用的数据集
表2 MNB作基分类器的分类精度比较
表3 MNB作基分类器时对于a=0.05的p-values
Nemenyi测试拒绝未调整P-value≤0.008333的假设:
1、MNB vs.DTWMNB
2、Rw,c-MNB vs.DTWMNB
3、MNB vs.FWMNB
Bergmann测试拒绝这些假设:
1、MNB vs.FWMNB
2、MNB vs.DTWMNB
3、Rw,c-MNB vs.FWMNB
4、Rw,c-MNB vs.DTWMNB
表4 CNB作基分类器的分类精度比较
表5 CNB作基分类器时对于a=0.05的p-values
Nemenyi测试拒绝未调整P-value≤0.008333的假设:
1、CNB vs.DTWCNB
2、CNB vs.FWCNB
3、Rw,c-CNB vs.DTWCNB
Bergmann测试拒绝这些假设:
1、CNB vs.FWCNB
2、CNB vs.DTWCNB
3、Rw,c-CNB vs.DTWCNB
表6 OVA作基分类器的分类精度比较
表7 OVA作基分类器时对于a=0.05的p-values
Nemenyi测试拒绝未调整P-value≤0.008333的假设:
1、OVA vs.DTWOVA
2、Rw,c-OVA vs.DTWOVA
3、OVA vs.FWOVA
4、Rw,c-OVA vs.FWOVA
Bergmann测试拒绝这些假设:
1、OVA vs.FWOVA
2、OVA vs.DTWOVA
3、Rw,c-OVA vs.FWOVA
4、Rw,c-OVA vs.DTWOVA 。
机译: 一种基于分数的文本单元分类方法,计算机程序产品及其计算机
机译: 带有自动决策树的文本生成器,用于基于更改的输入数据创建文本
机译: 带有自动决策树的文本生成器,用于基于更改的输入数据创建文本