Thinking in SQL系列之数据挖掘C4.5决策树算法

作者简介:牛超

10多年数据库技术积累,长期从事ORACLE数据库管理与开发工作。精通企业级数据库应用设计、SQL、算法实现、异常分析、性能优化。目前就职于日立咨询(中国)有限公司。Mail:10867910@qq.com

C4.5是一系列用在机器学习和数据挖掘的分类问题中的算法。它的目标是监督学习:给定一个数据集,其中的每一个元组都能用一组属性值来描述,每一个元组属于一个互斥的类别中的某一类。C4.5的目标是通过学习,积累经验,为后续决策服务。

该算法目前能找到各类版本,C、JAVA、PYTHON。而SQL版本闻所未闻,前篇我有提过,数据处理,SQL为王,如何以SQL的思维来实现C4.5决策树算法是本篇的重点。

C4.5的核心是分裂规则,因为它们决定给定节点上的元组如何分裂。本篇实现比较流行的属性选择度量,即信息增益、增益率。这个规则也是要实现的重点功能,后续程序会有介绍。

先祭出为实现该算法的几个数学公式

1、信息增益,又称为熵

按照类标签对训练数据集D的属性集A进行划分,得到信息熵,著名的香农定理:

按照属性集A中每个属性进行划分,得到一组信息熵:

信息增益定义:

分裂信息的度量(类似公式1)

信息增益率定义:

选择具有最大增益率的属性作为分裂属性。

接下来以一个很典型被引用过多次的训练数据集D为例,来说明C4.5算法如何通过分裂规则来选择决策结点。

上面的训练集有4个属性,即属性集合A={天气, 温度, 湿度, 风速};而类标签有2个,即类标签集合C={进行, 取消},分别表示适合户外运动和不适合户外运动,其实是一个二分类问题。上面的图形象地描述了第一次分裂的属性为天气,由左边的学习样本集形成树的第一层。

结合之前提到的5个公式,可以通过下列SQL给出第一次分裂的实现思路:

WITH TDATA AS (
SELECT '晴' OUTLOOK,'炎热' TEMP,'高' HUMIDITY,'弱' WINDY,'取消' ACTION FROM DUAL UNION ALL
SELECT '晴','炎热','高','强','取消' FROM DUAL UNION ALL
SELECT '阴','炎热','高','弱','进行' FROM DUAL UNION ALL
SELECT '雨','适中','高','弱','进行' FROM DUAL UNION ALL
SELECT '雨','寒冷','正常','弱','进行' FROM DUAL UNION ALL
SELECT '雨','寒冷','正常','强','取消' FROM DUAL UNION ALL
SELECT '阴','寒冷','正常','强','进行' FROM DUAL UNION ALL
SELECT '晴','适中','高','弱','取消' FROM DUAL UNION ALL
SELECT '晴','寒冷','正常','弱','进行' FROM DUAL UNION ALL
SELECT '雨','适中','正常','弱','进行' FROM DUAL UNION ALL
SELECT '晴','适中','正常','强','进行' FROM DUAL UNION ALL
SELECT '阴','适中','高','强','进行' FROM DUAL UNION ALL
SELECT '阴','炎热','正常','弱','进行' FROM DUAL UNION ALL
SELECT '雨','适中','高','强','取消' FROM DUAL 
) ,TA AS (
SELECT TDATA.*, 
ACTION ACTION1,
COUNT(1) OVER ( PARTITION BY ACTION ) PA ,
COUNT(1) OVER ( PARTITION BY OUTLOOK ) PW1 ,
COUNT(1) OVER ( PARTITION BY TEMP ) PT1,
COUNT(1) OVER ( PARTITION BY HUMIDITY ) PH1 ,
COUNT(1) OVER ( PARTITION BY WINDY ) PN1,
COUNT(1) OVER ( PARTITION BY OUTLOOK,ACTION ) PW2 ,
COUNT(1) OVER ( PARTITION BY TEMP,ACTION ) PT2,
COUNT(1) OVER ( PARTITION BY HUMIDITY,ACTION ) PH2 ,
COUNT(1) OVER ( PARTITION BY WINDY,ACTION ) PN2,
COUNT(1) OVER () CNT
FROM TDATA
) ,TB AS (
SELECT DISTINCT TYPE , VALUE, ACTION ,CNT , C1 , C2 
FROM TA
UNPIVOT ( 
  (VALUE , C1 , C2 ) FOR TYPE IN (
    (ACTION1 , PA , PA ) AS '0', 
    (OUTLOOK , PW1 , PW2 ) AS 'W',
    (TEMP, PT1 , PT2 ) AS 'T',
    (HUMIDITY ,PH1 , PH2 ) AS 'H',
    (WINDY ,PN1 , PN2 ) AS 'N'
  )
)
) , TC AS (
SELECT TYPE , VALUE , CNT,C1,
SUM( - C2/C1 * LOG(2,C2/C1) ) INFO_J,
DECODE(COUNT(DISTINCT ACTION),1,MIN(ACTION)) PURE_ACTION
FROM TB 
GROUP BY TYPE , VALUE , CNT,C1
ORDER BY 1 , 2 , 3 
) ,TD AS (
SELECT TYPE , 
SUM( - C1/CNT * LOG(2,C1/CNT) ) H_SPLIT_INFO  ,--每个属性的分裂信息度量
SUM( C1/CNT * INFO_J ) INFO --每个属性的统计平均熵
FROM TC 
GROUP BY TYPE
) , TE AS (
SELECT A.TYPE , --属性类别
A.H_SPLIT_INFO , --分裂信息度量
A.INFO , --每个属性的信息熵
B.H_SPLIT_INFO INFO_D,--类别信息熵
B.H_SPLIT_INFO - A.INFO GAIN ,--信息增益
(B.H_SPLIT_INFO - A.INFO) / A.H_SPLIT_INFO IGR --信息增益率
FROM TD A
JOIN TD B
ON B.TYPE = '0'
AND A.TYPE != B.TYPE
) , TF AS (
SELECT TC.TYPE ,ROWNUM RNUM, TC.VALUE ,TC.PURE_ACTION,
1 ALEVEL ,NULL PTYPE , 0 PRNUM
FROM TE
JOIN TC
ON TE.TYPE = TC.TYPE
AND TE.IGR = (SELECT MAX(IGR) FROM TE )
) SELECT * FROM TF 

简单地介绍一下思路:因各个属性A与分类D的信息熵较为独立,为了能同时并行计算,首先构造集合TB,这里使用了反透视UNPIVOT操作,将各属性A转为一个集合TC后计算分类D以及各属性A的分裂度量(公式1、公式4),推入到TD中求统计平均值E(公式2)做为属性A的熵。接着将属性A的增益对分类D信息熵的依赖关系转为JOIN连接(集合TE)后同时计算各个属性的信息增益GAIN与增益率IGR。

如下我们可以单独输出查看TE的结果。

集合TF实现的动作最简单,增益率最大的属性,结果如下:

这样便构建了决策树的第一层,其中第二行是“纯”的,可以直接做为决策树的叶子结点,而剩下的1,3行接着用来分裂其他属性。

通过进一步观察,我们可以发现这个分裂过程是递归的,递归终止的条件是分裂结点全部为叶子。SQL如何递归地找到所有分裂的结点,答案是借助11G的RSF特性。递归主体已经确认,但递归的过程会依赖上一层的属性值来构造新的集合,该用什么方式处理呢?有种方式,提前构造好属性与其它属性的组合E C4N(N=1..3),即N元笛卡尔并集,再与上次递归产生的集合连接后产生新的集合应该可以实现。但考虑到训练集基数可能很大会导致系统开销过高,所以不推荐这种方式。

纯SQL实现既然存在性能问题,我们可以用自定义函数来封装以产生子集合。终于忍不住把PLSQL推上场了?请不要误会,笔者不太会写FOR循环,而是借用动态SQL来构造集合TE,正如前篇所阐述:PLSQL是用来辅助SQL的,而非替代。Thinking in SQL的思想没有变。然后再考虑一下功能通用性,我们可以定义表来存储训练集数据,按批次生成决策树,并将OUTLOOK、WINDY抽象成C1、C2...C10,加上ORACLE很教条的自定义类型,程序就如下变成这样了:

1.创建C45学习训练集表

2.写入要学习的训练数据,启用C1-C4共4个维度分别对应天气、温度、湿度、风速,批次1

3.创建C45决策树类型,因自定义函数需要返回集合

4.属性分裂函数,将文章开始用于疏理思路用的SQL,抽象成一段动态SQL与待绑定变量,执行构造后的SQL返回,详见如下脚本与注释:

CREATE OR REPLACE FUNCTION FUN_DATA_MINING_C45_SPLIT( --C4.5单次分裂
  P_BATCH_ID NUMBER ,--批次ID
  P_ATTR_CNT NUMBER,--属性个数
  P_TYPE NUMBER ,--父结点属性ID
  P_VALUE VARCHAR2 ,--父结点值
  P_RNUM NUMBER DEFAULT NULL--父结点序号
  ) RETURN DATA_MINING_C45_TREENODE_TAB
IS 
  V_SQL VARCHAR2(32767) ;--构造SQL
  V_UNPIVOT_LIST VARCHAR2(4000);--动态反透视子句
  V_TAB DATA_MINING_C45_TREENODE_TAB ;--返回集合
BEGIN 
  V_SQL := '
  WITH TDATA AS (
  SELECT * 
  FROM DATA_MINING_C45_LEARNING_T
  WHERE BATCH_ID = :P_BATCH_ID
  AND ( :P_TYPE IS NULL 
    [DEL]OR C%TYPE% = :P_VALUE [ENTER]OR :P_VALUE IS NULL
   )
  ) ,
  TA AS (
  SELECT TDATA.*, 
  ACTION ACTION1,
  COUNT(1) OVER ( PARTITION BY ACTION ) PA ,
  COUNT(1) OVER ( PARTITION BY C1 ) C1_P1 ,
  COUNT(1) OVER ( PARTITION BY C2 ) C2_P1,
  COUNT(1) OVER ( PARTITION BY C3 ) C3_P1 ,
  COUNT(1) OVER ( PARTITION BY C4 ) C4_P1,
  COUNT(1) OVER ( PARTITION BY C1,ACTION ) C1_P2 ,
  COUNT(1) OVER ( PARTITION BY C2,ACTION ) C2_P2,
  COUNT(1) OVER ( PARTITION BY C3,ACTION ) C3_P2 ,
  COUNT(1) OVER ( PARTITION BY C4,ACTION ) C4_P2,
  COUNT(1) OVER () CNT
  FROM TDATA
  ) ,
  TB AS (
  SELECT DISTINCT 
  TYPE , --类别
  VALUE, --值
  ACTION ,--决策
  CNT , --采样数
  CNT1 , --类别个数
  CNT2 --类别决策个数
  FROM TA
  UNPIVOT ( 
    (VALUE , CNT1 , CNT2 ) FOR TYPE IN (
      (ACTION1 , PA , PA ) AS 0, 
      --动态构造反透视列,列转行
      %V_UNPIVOT_LIST%
    )
  )
  ) --SELECT * FROM TB ORDER BY 1 ,2 
  , TC AS (
  SELECT TYPE , VALUE , CNT,CNT1,
  SUM( - CNT2/CNT1 * LOG(2,CNT2/CNT1) ) INFO_J,
  DECODE(COUNT(DISTINCT ACTION),1,MIN(ACTION)) PURE_ACTION
  FROM TB 
  GROUP BY TYPE , VALUE , CNT,CNT1
  ORDER BY 1 , 2 , 3 
  ) --SELECT * FROM TC 
  ,TD AS (
  SELECT TYPE , 
  SUM( - CNT1/CNT * LOG(2,CNT1/CNT) ) H_SPLIT_INFO  ,--每个属性的分裂信息度量
  SUM( CNT1/CNT * INFO_J ) INFO --每个属性的统计平均熵
  FROM TC 
  GROUP BY TYPE
  ) , TE AS (
  SELECT A.TYPE , --属性类别
  A.H_SPLIT_INFO , --分裂信息度量
  A.INFO , --每个属性的信息熵
  B.H_SPLIT_INFO INFO_D,--类别信息熵
  B.H_SPLIT_INFO - A.INFO GAIN ,--信息增益
  (B.H_SPLIT_INFO - A.INFO) / A.H_SPLIT_INFO IGR --信息增益率
  FROM TD A
  JOIN TD B
  ON B.TYPE = 0
  AND A.TYPE != B.TYPE
  ) , TF AS (
  SELECT TC.TYPE ,ROWNUM RNUM, TC.VALUE ,TC.PURE_ACTION--,
  --1 ALEVEL ,NULL PTYPE , 0 PRNUM
  FROM TE
  JOIN TC
  ON TE.TYPE = TC.TYPE
  AND TE.IGR = (SELECT MAX(IGR) FROM TE )
  ) 
  SELECT DATA_MINING_C45_TREENODE(TYPE ,RNUM , VALUE , PURE_ACTION , :P_TYPE , :P_RNUM ) 
  FROM TF 
  ' ;

5.万事具备,接下来就是递归主体了,一如既往地Thinking in SQL:

5.看看机器学习的成果,子结点通过PARENT_CTYPE,PARENT_RNUM关联父结点:

6.数据看起来太抽象了?头脑影像化一下生成的整个决策树:

可以说,SQL本身做为关系代数的优秀产物,通过并、交、乘、除四则运算可以完成任意集合间的处理变换。在数据处理方面有其它语言不可替代的优势。大数据是吧,正如数学没有边界那样,SQL语言本身没有瓶颈。本篇正好写在ORACLE 12.2的来临之际,拭目以待,支持了CLOUD、SHARDING、HDFS的ORACLE,如何左右大数据领域的话语权。

Thinking in SQL系列文章会持续分享,敬请关注

原文发布于微信公众号 - 数据和云(OraNews)

原文发表时间:2017-03-03

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏菩提树下的杨过

WritableBitmapEx 一瞥

今天在蓝色上看到一篇介绍WritableBitmapEx的贴子(是开源项目),项目地址:http://writeablebitmapex.codeplex.co...

1758
来自专栏上善若水

015android初级篇之传感器的简单使用

要监控传感器的原始数据,你需要实现 SensorEventListener 接口的 onAccuracyChanged() 和onSensorChanged()...

1125
来自专栏Android机器圈

OpenGL ES学习001---绘制三角形

PS:OpenGL ES是什么? OpenGL ES (OpenGL for Embedded Systems) 是 OpenGL三维图形 API 的子集,针对...

33613
来自专栏菩提树下的杨过

Silverlight的自定义tooltip提示工具条

这种应用场景其实很多,比如游戏中装备/魔法的选择菜单,这里借用了"深蓝色右手"的一张图  再比如聊天室中的文本颜色设置  ? 虽然sl的ToolTipServ...

2086
来自专栏PPV课数据科学社区

【学习】七天搞定SAS(六):宏的编写、程序调错

在SAS各种繁杂的PROC之后,还要来看看MACRO才可以嘛。又不能写函数... SAS中的MACRO:宏编写 MACRO主要是DO和%LET的各种组合,前者负...

3256
来自专栏Java帮帮-微信公众号-技术文章全总结

【Java案例】余弦函数

案例描述 在屏幕上画出余弦函数cos(x)曲线,如图1.6所示。 ? 图1.6 余弦函数cos(x)曲线 案例分析 连续的曲线是由点组成的,点与点之间距离比较...

3366
来自专栏程序员互动联盟

【专业技术】Android平台下使用OpenGL

存在问题: 安卓平台下如何使用opengl? 解决方案: 1、GLSurfaceView GLSurfaceView是Android应用程序中实现OpenGl画...

3596
来自专栏debugeeker的专栏

sedna不支持xml schema

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/xuzhina/article/detai...

551
来自专栏cloudskyme

使用R画地图数据

用R画地图数据 首先,从这里下载中国地图的GIS数据,这是一个压缩包,完全解压后包含三个文件(bou2_4p.dbf、bou2_4p.shp和bou2_4p.s...

3837
来自专栏向治洪

android画图之贝塞尔曲线讲解

首先对于《赛贝尔曲线》不是很了解的童鞋,请自觉白度百科、google等等... 为了方便偷懒的童鞋,这里给个《贝赛尔曲线》百科地址,以及一段话简述《贝赛尔曲线...

2087

扫码关注云+社区