在线客服

咨询热线

基于不平衡数据集的决策树算法

作者: 王士斌 廖志雄

  摘要:为了使决策树健壮,我们从描述信息增益开始,关于这个规则的置信度,使用C4.5作为度量。这可以使我们快速的解释为什么信息增益,象置信度,偏重大多数类的规则的结果。为了克服这种偏见,我们介绍一种新度量,类置信度比例(CCP),它是CCPDT(类置信度比例决策树)形成的基础。这两种变化在一起产生一个分类器,它不仅比传统的决策树,而且比著名的平衡取样技术学习树能更好的完成统计。
  关键词:类置信度比例 决策树 分类器
  在不平衡数据中,我们分析以基于规则的分类器的指标时发现,基于置信度的排名偏重多数类,并且描述信息增益和描述置信度的基尼指数都表明它们也遭受类似的问题。
  现在假设有一个训练数据集,有n个记录组成,并且前因(记作X和┐X)和类(y 和┐y)。在CBA中选择规则的策略是找到在已经预定义的阈值上支持度和置信度的所有规则项目。对于不平衡数据集,无条件类的规模比正类小,所以a + b << c + d。由于不平衡数据集不能影响前因分布,我们不能失去一般性,假设X s 和 ┐X s是平均分布。因此,当数据时不平衡的时候,a和b值小,c和d值大。即使y与X出现的频率比与┐y出现的频率高,c的值也比a的值大,因为正类的规模比负类的规模小。因此,即使规则X→┐y意义不大,那么它也很容易有一个高置信度值。
  一、类置信度比例
  确定了支持度-信任度框架的缺点,并且在平均信息量和基尼指数表现不佳的情况下,我们必须提出一个新的措施来解决这个问题。为此,我们定义一个新的定义,类置信度(CC),从所有类(ys)中找到最感兴趣的前因(Xs):
  CC和传统的置信度最主要的区别在于分母:我们使用Supp(y)代替Supp(X),目的在于以每个类为重点。无论是从平衡数据集还是不平衡数据集中被发现,高CC的规则将是意义重大的。高CCP的规则意味着,比较它的替代类,这种类包含更高的CC,因此更可能出现这种规则的前因没有重视数据集中的类比例。采取这种比例的另外一个好处是能在0和1之间标记CCP,它可能通过CCP取代传统的平均信息量的频率项。
  二、基于CCP的决策树算法
  CCPDT算法修改了基于平均信息量的C4.5标准,并且用CCP取代频率项。由于空间的限制,在此省略了嵌入CCP的CART算法,但是这种方法和C4.5是相同的。
  1、构建树
  算法1 创建基于C4.5的CCP
  输入:训练集: T D 输出:决策树
  (1)if所有的实例属于同一个类,返回带有一个根节点(root)的决策树,记为实例类;
  (2)//寻找最佳的分裂属性(Attri)//
  (3)Attri = MaxCCPGain(T D)
  (4)把Attri分配给根节点,root=Attri
  (5)for Attri的每个值Vi {
  (6)Vi添加一个分支
  (7)if 属性Attri没有一个实例是Vi ,则为这个分支添加一个叶子;
  (8)else为这个分支添加一个子树CCP-C4.5(T D Vi);}
  算法2 寻找最大信息增益属性的子程序
  输入:训练集: T D 输出:要分割的属性:Attri
  (1)MaxHellinger,MaxInfoGain和Attri置0;
  (2)for T D的每个属性Aj {
  (3)计算Hellinger距离:Aj. Hellinger;
  (4)获得分裂之前的熵:Aj.oldEnt;}
  (5)子节点熵的总和Aj.newEnt的值置0;
  (6)for 属性Aj的每个值VIJ
  (7)//|Tx,y|表示包含值x和类y的实例的数量//
  (11)CurrentInfoGain= Aj.oldEnt-Aj.newEnt
  (12)if MaxInfoGain <CurrentInfoGain
  (13){Attri=j;MaxInfoGain=CurrentInfoGain;MaxHellinger= Aj. Hellinger;}
  (14)else if MaxHellinger<Aj. Hellinger 且MaxInfoGain== CurrentInfoGain
  (15){Attri=j;MaxHellinger= Aj. Hellinger;}
  (16)返回 Attri
  算法3 基于FET的修剪
  输入:为修剪的决策树DT,阈值p(pVT) 输出:修剪后的DT
  (1)for 每个叶子Leafi
  (2)if Leafi.parent不是DT的根节点,
  (3){Leafi.parent.pruneable=ture; //ture是默认值//
  (4)SetPruneable(Leafi.parent,pVT);}
  (5)获得DT的根节点
  (6)for 根的每个孩子child(i)
  (7)if child(i)不是叶子
  (8)if child(i). pruneable==ture 则设置child(i)为一个叶子;
  (9)else PurnebyStatus(child(i));
  算法4 通过自底向上搜索为每个分支节点设置可修剪状态的子程序
  输入:分支节点Node,阈值p(pVT) 输出:分支节点的可修剪状态
  (1)for 每个孩子child(i) if Node
  (2)if child(i). pruneable==false 则Node. pruneable=false;
  (3)if Node. pruneable==true则计算这个节点的p值:Node.pValue;   (4)if Node.pValue<pVT 则Node. pruneable=false;
  (5)if Node.parent不是满树的根节点,则Node.parent. pruneable=ture;
  (6)设置可修剪状态(Node.parent,pVT)
  算法5 根据可修剪状态进行修剪节点的子程序
  输入:顶部节点代表的一个分支:Node 输出:修剪的分支
  (1)if Node. pruneable==ture,则设置Node为一个叶子;
  (2)else for 分支的每个孩子child(i)
  (3)if child(i)不是叶子,则通过child(i)的状态修剪:PrunebyStatus(child(i));
  在这个的决策树模型中,把每个分支节点看作规则的最后的前因。例如,Leaf Y从根到叶有三个分支节点(Branch A, Branch B, and Branch C)。假设存在以下规则:Branch A ^ Branch B ^ Branch C→Leaf Y。在算法2中,计算每个分支节点的CCP,使用前面的例子,Branch C的CCP是先前的规则,Brach B的CCP是规则Branch A ^ Branch B→Leaf Y等,这样,选择的属性保证了其分裂产生具有最高CCP的规则。
  2、修剪树
  建立决策树后,Fisher精确测试适用于每个分支节点。如果一个分支存在至少一个有意义的子节点,分支节点将不被叶子节点取代。
  检查整个分支节点的所有后代的意义的代价是非常大的。要执行一个更有效的修剪,设计了两个阶段的策略,如算法3所示。第一阶段是从每个叶子到每个根的自下而上的检查过程。如果一个节点和它所有的子节点都是无意义的,那么给这个节点标注“可修剪”。这种检查剪枝状态的过程是通过算法3的第1–4行和算法4的子程序来实现的。在开始的时候,所有分支节点设置为默认状态“可修剪”。从叶到根检查每个节点的意义,如果一个节点的任何一个孩子是“不可修剪”活着节点本身是一个重要规则,这个节点的状态由“可修剪”改为“不可修剪”。
  在对意义进行检查后,开始第二个修剪阶段,根据从根到叶子的每个节点的“可修剪”状态进行一个自上而下的修剪过程。如果其“可修剪”状态为真,用叶子取代分支节点。
  这两个阶段的修剪策略保证了修剪树的完整性和正确性。第一阶段检查每个可能规则的意义,并保证每个重要规则是“不可修剪”的;第二阶段修剪所有不重要的规则,因此,修剪树的路径都是正确的。
  三、结论
  本文介绍了CCP在决策树构造中分裂属性采取的措施,同时提出了一个完整的决策树算法,以及采取的修建策略。由于时间和客观条件等因素的限制,所提出的观点还没有应用到实际项目之中,所以很多地方没有经过实际验证。
  参考文献:
  [1] FAWCETT T, PROVOST F. Combining data mining and machine learning for effective user profile [ C ] / /Proc of the 2nd International Conference on Knowledge Discovery and Data Mining. Portland: AAA I Press, 1996: 8-13.
  [2] WEISS G. Mining with ratity: a unifying framework [J]. SIGKDD Explorations, 2004, 6(1): 7-19.
  [3] 郭炜星.数据挖掘分类算法研究[D]. 杭州: 浙江大学,2008.
  [4] 周丽,李坚著.数据仓库与决策支持[M],国防工业出版社,2003.
  [5] Xu X, He Y. Improvements on Fast Motion Estimation Strategy for H.264/AVC[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2008, 18(3): 285-293.
  [6] 李瑞, 魏现梅, 黄明, 等. 一种改进的决策树学习算法. 科学技术与工程, 2009; 9 ( 20) : 6038-6041
论文来源:《大观周刊》 2012年第26期
转载注明来源:https://www.xzbu.com/1/view-3188597.htm