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 条评论
登录 后参与评论

相关文章

来自专栏数说工作室

统计师的Python日记【第5天:Pandas,露两手】

本文是【统计师的Python日记】第5天的日记 回顾一下: 第1天学习了Python的基本页面、操作,以及几种主要的容器类型; 第2天学习了python的函数、...

4087
来自专栏林冠宏的技术文章

C语言版flappy bird黑白框游戏

      在此记录下本人在大一暑假,2014.6~8这段时间复习C语言,随手编的一个模仿之前很火热的小游戏----flappy bird。代码bug基本被我找...

2667
来自专栏数据结构与算法

42:出书最多

42:出书最多 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 假定图书馆新进了m(10 ≤ m ≤ 999)本图书,它们...

2585
来自专栏Python中文社区

遗传算法框架GAFT优化小记

專 欄 ❈PytLab,Python 中文社区专栏作者。主要从事科学计算与高性能计算领域的应用,主要语言为Python,C,C++。熟悉数值算法(最优化方法,...

1768
来自专栏编程

文本提取仨兄弟

周二 · 函数  关键词:left、right、mid 1语法 =Left(text,[num_chars]) =Right(text,[num_chars])...

1858
来自专栏数据小魔方

R语言数据清洗实战——高效list解析方案

list是R语言中包容性最强的数据对象,几乎可以容乃所有的其他数据类型。 但是包容性最强也也意味着他对于内部子对象的类型限制最少,甚至内部可以存在递归结构,这样...

3404
来自专栏北京马哥教育

详解 Python qrcode 二维码模块

1、version:控制二维码的大小,取值范围从1到40。取最小值1时,二维码大小为21*21。取值为 None (默认)或者使用fit=true参数(默认)时...

960
来自专栏IMWeb前端团队

前沿技术解密——VirtualDOM

作为React的核心技术之一Virtual DOM,一直披着神秘的面纱。 实际上,Virtual DOM包含: Javascript DOM模型树(VTre...

1859
来自专栏机器学习实践二三事

Python-OpenCV(5)

这次咱们比较下,python的函数、numpy的函数和OpenCV的函数的效率问题,让大家对功能相同的情况下如何选择合适的函数有比较直观的认识 程序(语句)运行...

1757
来自专栏我是攻城师

图形数据库之Neo4j核心概念介绍(二)

3566

扫描关注云+社区