
第52卷第3期
2 0 1 2 年 5 月
大 连 理 工 大 学 学 报
Journal of Dalian University of Technology
Vol .52 , No .3
May 2 0 1 2
文章编号 :1000‐8608(2012)03‐0443‐05
基 于 改 进
χ
2
统 计 的 数 据 离 散 化 算 法
桑 雨
1
, 李 克 秋
倡 1
, 闫 德 勤
2
( 1 .大连理工大学 计算机科学与技术学院 ,辽宁 大连 116024 ;
2 .辽宁师范大学 计算机与信息技术学院 ,辽宁 大连 116029 )
摘要 :
在基于
χ
2
统计独立性的离散化算法中 ,自由度与期望频数的选取直接影响
χ
2
计算的
准确性 ,从而影响离散化的性能 .为此 ,提出了一种基于改进
χ
2
统计的数据离散化算法 ,提高
了基于统计独立性离散化算法的质量 .首先 ,分析了
χ
2
函数中自由度选取的不足 ,给出了自
由度选取的修正方案 ;其次 ,根据数据类分布等特点 ,提出了期望频数的改进方案 ,克服了不
同数据集赋予相同期望频数的缺陷 ,提高了
χ
2
计算的准确性 .实验结果表明 ,改进的方法显
著提高了 C4 .5 决策树与 Naive 贝叶斯分类器的学习精度 .
关键词 :离散化 ;数据挖掘 ;
χ
2
统计
中图分类号 :TP18 文献标志码 :A
收稿日期 :2010‐09‐18 ; 修回日期 :2012‐03‐28 .
基金项目 :教育部新世纪优秀人才支持计划资助项目 (NCET‐07‐0132) .
作者简介 :桑 雨(1982‐) ,男 ,博士生 ;李克秋
倡
(1971‐) ,男 ,博士 ,教授 ,博士生导师 ,E‐mail :keqiu@ dlut .edu .cn .
0 引 言
随着数据库中信息量的增加以及信息管理水
平的不断提高 ,涌现了各种类型的数据来描述客
观世界 .在应用机器学习从数据中提取知识时 ,涉
及的数据通常包括离散值(如男 、女)和连续值(如
身高 、温度等) .然而 ,大多数的数据挖掘 、归纳学
习等算法仅仅适用于使用离散化方法描述的样
本 ,如 C4 .5
[1]
和 AQ 算法
[2]
等 .因此 ,连续属性必
须进行离散化 ,其实质是分割连续属性的值域 ,转
化成若干个有意义的区间 ,简化数据 ,提高分类器
的学习精度 .
离散化算法的类型有
[3]
考虑类信息的有监督
类型和不考虑类信息的无监督类型 ;考虑整体样
本的全局型和考虑部分样本的局部型 ;相邻区间
合并的自底向上型 (bottom‐up)和区间分割的自
顶向下型(top‐down) .EQW 和 EQF
[3]
是实现简
单且计算消耗低的自顶向下无监督离散化算法 .
著名的自顶向下有监督离散化算法包括基于信息
熵理论的算法 ,如 Ent‐MDLP
[4]
;基于类属性相互
依赖的算法 ,如 CACC
[5]
.Ent‐MDLP 通过定义信
息熵标准来最小化模型总的信息量 ,同时利用
MDLP 来决定合适的离散区间数 .CACC 是目前
最新的基于类‐属性相互依赖的离散化算法 ,它提
出了一个启发式断点选择标准 ,考虑了所有样本
的分布信息 ,并且避免了过拟合现象 ,产生了理想
的离散化方案 .著名的自底向上有监督离散化算
法包 括基 于 统 计学 理 论 的 Chi2‐based 相 关 算
法
[6 ~ 9 ]
,如 ChiMerge
[6]
和 Extended Chi2
[9]
等 .它
们首先初始化区间 ,采用
χ
2
统计来判断当前相邻
区间是否被合并 ,并且通过不一致衡量标准来判
断离散化进程是否结束 .
基于
χ
2
统计的方法是目前最有效的离散化
算法之一 .自由度与期望频数的选取直接影响
χ
2
计算的准确性 ,从而影响离散化的性能 .本文提出
一种基于改进
χ
2
统计的数据离散化算法 ,该算法
考虑相邻区间数对自由度的影响 .此外 ,对于没有
在相邻区间中出现的类 ,期望频数均取一个预先
给定的常数 ,忽视了自身的内在信息对期望频数
的影响 ,导致计算
χ
2
不准确 ,区间合并顺序不合
理 ,从而降低了学习精度 .因此 ,本文给出自由度
与期望频数的合理改进方案 .
1 基础知识
1 .1 粗糙集
[10 ]
设 S
=
(U ,A ,V ,F) 是一个信息系统 ,其中