Computer Engineering and Applications 计算机工程与应用 2013，49（1） 167 MDL 理论的多属性值域划分方法 陈爱萍 1，范媛媛 2 CHEN Aiping1, FAN Yuanyuan2 1.金陵科技学院 信息技术学院，南京 211169 2.焦作师范高等专科学校 计算机与信息工程系，河南 焦作 454000 1.School of Information Technology, Jinling Institute of Technology, Nanjing 211169, China 2.Department of Computer and Information Engineering, Jiaozuo Teachers College, Jiaozuo, Henan 454000, China CHEN Aiping, FAN Yuanyuan. Value domain partition method of multiple attributes based on MDL principle. Computer Engineering and Applications, 2013, 49（1）：167-170. Abstract：Value domain partition methods of continuous attributes are important research in data mining and machine learning. Many discretization methods are proposed, and most tend to discuss the discretization of 1-dimension attribute without considering the relationship among the attributes, which is difficult to get optimal discretization results. This paper proposes a value domain partition method of multiple attributes based on MDL principle. It derives a measurement function of multiple attributes partition by defining model selection of multiple attributes. The paper also designs a reasonable algorithm to find the best discretization result. Performance evaluation and analysis demonstrate that the proposed approach improves the classification and learning ability of Naive Bayes classifier. Key words：data mining; discretization; Minimum Description Length Principle（MDLP）; Naive Bayes 摘 要：连续属性值域划分方法是数据挖掘和机器学习领域的重要课题。但已有的大量离散化方法倾向于研究一维属性 离散化问题，没有考虑多属性之间的相互关系，难于获得最佳的离散化结果。提出一种基于最小描述长度理论的多属性 划分方法，通过定义多属性的模型选择问题，推导出多属性划分衡量函数；设计一种合理的算法来寻找最好的离散化结 果。性能评价与分析表明，该方法在 Naive 贝叶斯分类器上有很好的分类学习能力。 关键词：数据挖掘；离散化；最小描述长度理论；Naive 贝叶斯 文献标志码：A 中图分类号：TP18 doi：10.3778/j.issn.1002-8331.1106-0009 1 引言 数据挖掘是一种从大型复杂数据库中提取有用信息 的强有力的工具。大量现实世界中的数据均以连续属性 值的类型呈现，然而，数据挖掘和机器学习等算法无法处 理连续性属性，因此，连续属性值域划分方法，即数据离散 化技术成为该领域的重要研究课题之一。好的离散化方 法要衡量两个指标：一是尽量减少数据在离散化过程中的 信息损失；二是要考虑属性间的相互依赖关系，以达到离 散化的最简形式。 连续属性离散化的研究已经取得大量的成果，研究人 员从不同领域提出了多种离散化算法[1-10]，主要可分以有监 督和无监督离散化。有监督离散化方法使用决策类信息， 无监督离散化则不考虑类的信息。Fayyad 提出的熵方法[1]， Kurgan 提出的类与属性之间关联度最大化的启发式 CAIM （Class-Attributes Interdependence Maximum，CAIM）算法[2]， 考虑类与属性值的空间分布信息的 CAIM 算法[3]，以及 Tsai 提出的 CACC 算法[4]，基于卡方统计的 Chimerge[5]和 Khiops[6] 算法，基于区间距离的属性值域划分 IDD 方法 [7]都是有监 督离散化的典型算法。传统的无监督属性划分方法包括 等宽离散化（Equal Width Discretization，EWD）和等频离 散化（Equal Frequency Discretization，EFD）[8]；基于核密度 评估方法（Kernel Density Estimation，KDE）[9]是最新的无 监督算法。 然而，已有的离散化方法均是针对单属性的离散化， 没有考虑多属性之间的内在关系。由于决策类由多个属 性共同决定，而不是由单个属性所决定，因此，单属性值域 划分的结果往往不是最优的，提出一种基于 MDL 理论的 多属性值域划分方法（Multiple Attributes Partition，MAP）， 基金项目：金陵科技学院自然科学基金（No.208.40410826）；金陵科技学院博士启动基金（No.JIT-B-01）。 作者简介：陈爱萍（1973—），女，讲师，主要研究方向：模式识别与数据挖掘；范媛媛（1976—），女，讲师，主要研究方向：多媒体教学、数据 库技术。E-mail：chenaiping_2008@126.com 收稿日期：2011-06-08 修回日期：2011-10-21 文章编号：1002-8331（2013）01-0167-04 

168 2013，49（1） Computer Engineering and Applications 计算机工程与应用 通过定义多属性的模型选择问题，推导出多属性划分衡量 函数；同时设计一种合理的算法来寻找最好的离散化结 果。性能评价与分析表明，该方法在 Naive 贝叶斯分类器 上有很好的分类学习能力。 2 MAP 方法 最小描述长度理论是一种归纳推理工具，能够通用地 解决模型选择问题，普遍被应用到选择最优分类模型问题 上。MAP 方法基于最小描述长度理论 [11]获得有效的多属 性划分衡量函数，MDLP 可以把属性值域划分问题看成是 一个信息通信的编码问题，试图最小化模型 M 转换的信息 总量和给定模型下的数据 D 转化的信息总量，即找到最好 的模型来最小化： p( m( 对于给定 N 个样本的数据集，决策类数为 S, a （1） 为任意 一个连续属性，1 £ i £ m ，m 为属性个数，则对于单属性来 说，可以将连续属性 a 的值域离散成 I 个区间，属性 a 的 i 每个值都可以划分到离散的 I 个区间的某一个区间中。 )D = -log )M - log )D|M p( a a i i } { 对于多属性值域划分问题，定义一个 δ 变量的值域划 }  I I , 1 δ ，其 中 ，1 £ 分问题的组合概率模型 M, 包括三个参数部分：{ { } { N ( )2 + δ £ m ，1 £ i( )k £ I } } ， 1 £ k £ δ ，I 指第 k 属性的离散区间数； 指 k 属性中第 i( )k 个区间的样本数（ i( )k 指 k 属性中 } {  I 2 和 { ( )2 i ( )δ + ( )1 + ( )δ j N N N ( )1 i 1 i 2 i δ i k k i N k i ( )k + i ( )1 i } } ( )δ + ( )2 i 指 δ 连 ( )1 i ( )2 i ( )δ j i 数。因此，模型 M 的概率为： 的区间下标，即 k 属性中的第几个区间）；N 续属性中{ N i( )1 i( )2  i( )δ 联合区间的 j 类样本数 (1 £ j £ S) ； 为 δ 连续属性中 { i( )1 i( )2  i( )δ 联合区间的样本   { { { pæ èç æ ç è )I } { } 为第 k 个属性中离散区间数的先验概率；p( { } { ( )1 + } ö p( )I | I ø÷ ( )1 +  { } { |{ }I } { { } | I } { }   { } ( )δ + ö )I p( ø÷ } { ( )δ + δ,i ö ÷ ø N ( )1 i pæ èç } ö ÷ ø } | I    p( ( )2 + pæ èç )M = p { }I ( )2 i ( )2 i p( { ( )δ + ( )2 + æ ç è ( )2 + ( )1 + ( )δ j ( )δ j ö ø÷ N N N N N N N N ( )1 i N N N 2i 1i = δi 1,i 2,i δ,i 1,i 2,i × 1 1 2 2 k k δ δ i i N  N k 1 +  N k 2 + } + k I k  N  N 的 概 率 ；p( { } 的概率。 N ( )1 i ( )2 i i ( )δ j ( )1 i ( )δ 1 ( )2 i ( )2 i 下面给出 p( i ( )1 i ( )δ 2 )M 具体的获取方法。由于每个属性的区 ( )2 i ( )δ S i k )I    p p( 为参 量 { { N ( )1 i i （2） ) } 为 ( )k + ) } k i 间数被分布在 1 到 N 之间，因此有： p( )I k = 1 N 根据组合学理论，在给定 I 的情况下，N k k i ( )k + 可能的 举一个简单的例子解释上面概率的获得，假设仅针对 的情况下， } } 2 1 2  = 3 ，则在给定 I 1 1 2 2 { 1 1 3 { 1 3 1 { } 数据集的第一个属性， N = 5,  I 1 { }N } ( )1 + 2 2 1 和 { { 的 可 能 选 择 有 ：{ 3 1 1 ，即 C 3 - 1 5 - 1 同理，对于给定的 { }I } } i k k i N ( )k + = 6 种选择。 和{ } } { 1 Õ 2 Õ ( )1 = 1 ( )2 = 1   { } { |{ }I δ C S - 1 ( )δ = 1 ( )2 ( )1 ö ÷ ø } } ( )k + N = k i N k I I i i i i I i 的组合数有 Õ { p æ ç è N ( )1 i ( )2 i i ( )δ j ，{ N ( )1 i ( )2 i i } ( )δ j 可能 种，则有： - 1 ( )δ + i Õ I 1 Õ ( )1 = 1 因此 i 1 2 Õ ( )2 = 1 I i I δ C S - 1 ( )δ = 1 ( )2 ( )1 N i i i i （5） - 1 ( )δ + -1 × I p( )N δ )M = ( δ C I k = 1 Õ -1 × æ è Õ  æ èç ö - 1 k ø N - 1 2 Õ ( )2 = 1 取模型概率的负对数： N + å 1 Õ ( )1 = 1 )M = δ log -log p( δ I i i a a log C I - 1 k N - 1 a + I δ C S - 1 ( )δ = 1 ( )2 ( )1 N i i i i -1 ö ø÷ - 1 ( )δ + （6） k = 1 I I I δ å 1 å 2  å ( )δ = 1 ( )2 = 1 ( )1 = 1 i i i log a C S - 1 ( )2 ( )1 N i i i - 1 ( )δ + （7） δ }  I I 1 区间后，样本分布的概率即为 p( 在 给 定 模 型 M 的 情 况 下 ，数 据 属 性 值 域 被 分 割 为 { )D|M ，对它  I 2 )D|M ，可 被 解 释 为 信 息 熵 理 论 的 取 负 对 数 ，即 -log Shannon 编码长度，因此，模型选择问题转换成了编码问 )D|M 。下面，先介 题。通过信息熵理论可以获得 -log 绍信息熵的基本概念。 p( p( a a 信息熵可以衡量随机变量的不确定性，它反映了随机 变量对应类分布的特性，熵值越大，不确定性越大，反之亦 然；当每个类含有等数量样本时，熵取最大值 log S ，当区 间中仅有一个类时，熵取最小值。在属性值域划分问题 中，不确定性表现为信息丢失。 a 定义 1 设 X 是取有限值的随机变量，P i 1 2 n ，则 X 的熵定义为： H ( n )X = å i = 0 × log p i ( 1/p ) i a = P{ X = x }  i = i （8） S N )R 对于第 k 个属性中的区间 R H ( 对于第 k 个属性的 I 个区间 { = -å k i N k i N log j = 1 N a i j j i k k ，其信息熵可被定义为： （9）   R R 1  R 2 I } ，如果独 组合数有 C I - 1 k N - 1 { pæ èç N k i ( )k + 种，则有： } | I = 1 C I - 1 k N - 1 ö ø÷ k （3） 立地对待每一个区间，可以得到相邻两区间的总体熵，即 带有权重的每个区间熵的和： H ( )a k = H (   R R 1  R 2 I I N = å ) i = 1 ( )k + k i N H ( )R i （10） 这样，转换区间 R 中每个样本点的平均香浓编码长度 i ，因 此 ，转 换 所 有 区 间 总 的 消 耗 为 N ´ （4） 为 N k i ( )k + ´ H ( )R i 

陈爱萍，范媛媛：MDL 理论的多属性值域划分方法 2013，49（1） 169 H (   R R 1  R 2 I ) I = å N i = 1 k i ( )k + ´ H ( )R i 。 基 于 相 同 的 规 则 ， 可以定义多属性下联合区间的熵： H ( ||a = ) a |a 1 2 δ I I I - å 1 å 2  å δ å ( )δ = 1 ( )2 = 1 ( )1 = 1 j = 1 i i i S N N ( )δ j i ( )1 i ( )2 i N log a ( )δ j i ( )1 i ( )2 i N （11） 在多属性值域划分问题中，转换所有联合区间{ R ,R 1 } ,,R )D|M 。因此，获 2 I ) ，即 -log p( a δ 2 总的消耗为 N ´ H ( ||a a |a 1 )D 如下： 得公式（1）中的 m( p( )M - log N + å )D = -log δ log m( log a δ a p( )D|M = C I - 1 i N - 1 a + a I i = 1 I log I δ å 1 å 2  å ( )1 = 1 ( )δ = 1 ( )2 = 1 i N ´ H ( ||a a |a 1 2 i i C S - 1 ( )2 ( )1 N i i i + - 1 ( )δ + a ) δ （12） 对公式（12）直观的合理解释：第一项对应离散化所产 生的区间数的选择；第二项对应于多变量下区间边界的选 择；第三项呈现了多变量下每个区间中决策类的分布状 况；最后一项表示编码模型 M 的概率。因此，式（12）综合 地反映了对断点划分选择的一个好的评价，将其作为 MAP 方法的多属性值域划分衡量函数，即离散化标准。 δ 2 ) a |a 1 ||a 一个好的离散化方法不仅应该有一个好的离散化标 准，而且应该有一个好的断点规则，即控制离散化导致的 信息损失。式（12）中的 H ( 恰恰衡量了多属性 值 域 划 分 下 导 致 的 不 一 致 ，控 制 了 信 息 丢 失 情 况 ；当 H ( = 0 时，没有产生任何的分类错误或信息丢 失。根据公式（12）的标准容易看出，要想求出多属性下最 优的联合区间方案，当 δ 比较大时，则需要很高的时间复杂 度：O( )N δ ，为了很好地权衡时间复杂度与离散化质量，提 出了有效的启发式的多属性离散化算法： ||a a |a 1 ) 2 δ 步骤 1 初始化 δ 值 (δ £ m) ：O( )1 。仿真中，通过调整 其值以找到最好的学习精度。 步骤 2 对 δ 个属性同时进行离散化。首先，将每一个 ) N 。初始，整个属性 连续属性值从小到大排序：O( 值域视为一个区间。对于每个属性（此时 δ =1），找到具有 最小 m( )D 值的断点为初始最佳断点，将 δ 个选好的断点 作为初始最佳的联合断点：O( δ × N 。 N log ) a 步骤 3 在 δ 个 属 性 中 ，将 所 有 断 点 的 m( )D 值 均 求 )D 值的断点添加到初始的最佳联合 出，选择具有最小 m( 断 点 中 ，如 果 H ( = 0 ，继 续 此 操 作 ；如 果 a |a 1 H ( 2 骤 2；O( > 0 ，则对下一组 δ 属性进行离散化，跳到步 δ × N 。 ) m ) ||a ||a a |a 1 ) m 2 步骤 4 对剩余小于 δ 的属性进行离散化，执行步骤 2 和 3；O( δ × N 。 ) 分析 MAP 算法的时间复杂度：步骤 2 对连续属性值排 δ × N ；步骤 3 和 4 找 δ 属性中所有断点的 m( N ) ，找到初始最佳的联合断点的时间 )D 值的 的最坏时间复杂度为 ||a ) a 序的时间为 O(N log ) 为 O( δ × N ，计算 H ( 时间为 O( O( ) δ × N ；综上所述，算法总的时间复杂度为 O( ) a |a 1 2 m ) N 。 N log a 3 性能仿真 3.1 UCI 数据集实验结果 在性能仿真中，采用 Chimerge、CAIM、基于熵的多区 间离散化（Ent-MDLP）[1]、EWD 和提出的 MAP 方法，对 UCI 机器学习数据库 [12]中的 8 个数据集（见表 1）进行属性值域 划分。Naive Bayes 分类器对属性划分后的数据进行分类 识别预测，采用五折交叉验证的方法[13]，对平均学习精度进 行对比（见表 2）。注意：很多数据挖掘分类算法，如 Naive Bayes 分类器、决策树等，内部执行了信息熵和概率等计 算，对于连续数据，它们将无法正常工作，因此必须将连续 属性进行离散化。而对于 SVM 等数据挖掘技术，它执行的 是数据内部的核函数计算，要用到数据值的本身信息，因 此不必要进行离散化。因此，采用 Naive Bayes 分类器来 验证 MAP 离散化方法的性能。 表 1 数据参数描述 数据集 实值属性个数 类数 数据大小/Byte Labor Iris Wine Glass Ionosphere Pima Vehicle Satimage 8 4 13 9 34 8 18 36 2 3 3 7 2 2 4 6 57 150 178 214 351 768 846 6 435 表 2 Naive Bayes 平均学习精度 （%） 数据集 Labor Iris Wine Glass Ionosphere Pima Vehicle Satimage EWD 90.5 92.6 90.7 71.4 82.6 74.7 62.7 74.3 属性划分方法 Ent-MDLP Chimerge 94.9 95.5 92.5 79.3 92.9 85.3 69.6 80.8 93.7 94.3 88.2 74.2 86.9 77.9 62.5 81.6 CAIM 93.2 93.3 92.3 75.8 92.0 79.6 68.4 79.5 MAP 96.1 96.2 95.9 87.9 94.7 87.6 76.1 85.6 MAP 算法依赖参数 δ ，如何决定最好的参数仍然是一 个开放性问题，并且超出了研究的范围。本文取 δ = 2 。直 觉地，考虑越多的连续属性，即 δ 越大，精度应该越高；然 而 ，如 果 δ 太 大 ，会 导 致 过 多 的 区 间 ，这 样 会 使 得 Naive Bayes 的分类精度降低，细节可参考文献[14]。 表 2 为不同离散化方法的 Naive Bayes 分类器平均学 习精度。从表 2 中可以看出，MAP 算法的 Naive Bayes 平 

170 2013，49（1） Computer Engineering and Applications 计算机工程与应用 均学习精度均有所上升，这一点正是属性值域方法期望得 到的结果，充分显示了 MAP 算法的优势。 3.2 在 Sonar Sensor 数据上的应用 由于 Sonar Sensor 收集到的声纳信号特征较多，故采 用 MAP 方法处理数据，目的是洞察 MAP 的有效性。Sonar Sensor 从不同的角度和不同的条件下收集声纳信号的 208 个 样 本 的 Sonar 数 据 集 [12]，跨 越 90°的 圆 柱 体 和 180°的 岩 石，其中 111 个样本为金属圆柱体反弹的声纳信号；97 个样 本为圆柱形的岩石反弹的声纳信号。每个样本包含 60 个 特征，每个特征值的范围在 0 到 1.0 之间。每个数值代表在 一个特定频段的能量。除了 Sensor 采集的数据外，不需要 任何其他信息。该方法由于只与 Sensor 采集的数据有关， 在海量数据中已经包括了 Sensor 的性能、参数、工作模式 等信息，因此可以推广到其他类型的传感器建模中，具有 一定的通用性。 将 Sonar 数据集分别用上述属性值域方法进行量化， 采 用 Naive Bayes 分 类 器 将 量 化 的 结 果 进 行 分 类 识 别 预 测，表 3 为平均识别精度进行对比的结果。 表 3 Naive Bayes 平均识别精度对比结果 （%） 离散后不同样本 占样本总数比例 识别精度 方法 NB Ent-MDLP+NB EWD+NB Chimerge+NB CAIM+NB MAP+NB 76.8 79.6 74.9 85.7 83.2 88.7 — 89.4 87.9 90.6 89.4 85.3 从表 3 中可以明显看出，对于 Sonar 数据集而言，MAP 离散后得到的不同样本数占样本总数的比例最少，与其他 离散化方法相比，MAP 可以得到相对简化的数据，大大简 化了数据，降低了存储要求；对于声纳信号的识别来说，基 于 MAP 的 Naive Bayes 分类识别精度最高，这正是数据挖 掘技术期望得到的结果，充分显示了 MAP 的优势。 3.3 在乳腺肿瘤诊断上的应用 乳腺癌是当今发病率很高的疾病之一，不及时治疗很 容易导致死亡。因此，及时准确地诊断出患者的乳腺肿瘤 是良性还是恶性极为重要，对后期的治疗也有很大的作 用。随着存储技术的发展，医学病例库日益增大，因此，简 化信息系统、筛选出有用的信息对后续的学习极为重要， 同时减轻了医生的工作量，提高了判断的准确性和客观性。 这里将说明 MAP 在乳腺肿瘤诊断中的有效性，实验数 据来自于 UCI机器学习数据库中的 Breast Cancer Wisconsin 数据集。将 Breast Cancer Wisconsin 删掉特征值不全的病 例 样 本 ，剩 下 683 个 病 例 样 本 ，病 理 检 测 有 9 项（Clump Thickness、Uniformity of Cell Size、Uniformity of Cell Shape、Marginal Adhension、Single Epithelial Cell Size、 Bare Nuclei、Bland Chromatin、Normal Nucleoli、Mitoses）， 即 9 个特征，每个特征取值范围[1，10]；病情状况分为两类： 一类表示肿瘤为恶性，另一类表示肿瘤为良性。这样，每 个样本有 9 个连续特征，1 个决策类标签。 将 Breast Cancer Wisconsin 用提出的 MAP 算法进行 离散化，然后分别使用 Naive 贝叶斯和 MAP+Naive 贝叶斯 对量化前和量化后的数据进行分类预测，采用 10 折交叉验 证的方法对平均正确识别率进行对比。实验结果表明，未 经过量化处理的 BCW 病例数据集进行 Naive 贝叶斯分类 预测的测试正确识别率为 92.55%，而 MAP+Naive 贝叶斯 分类方法的测试正确识别率为 99.27%，比未被量化数据的 Naive 贝 叶 斯 预 测 精 度 高 出 6.72 个 百 分 点 。 这 相 当 于 每 1 000 个患者中就多出约 67 个患者可以被准确地诊断出肿 瘤为良性还是恶性，对患者及时治疗有很大帮助，而且精 度达到了很高，在医学数据挖掘中有着良好的发展前景。 4 结束语 数据挖掘在数据库和信息决策等领域起到非常重要 的作用，而数据离散化是数据挖掘、机器学习中的重要预 处理过程。基于最小描述长度原理，提出一种多属性值域 划分方法，最优地选择离散化结果，对连续数据合理、有效 地进行离散化。实验结果表明，该方法明显地提高了 Naive Bayes 分类器的学习精度。 参考文献： [1] Fayyad U，Irani K.Multi-interval discretization of continuous- valued attributes for classification learning[C]//Proceedings of the 13th International Joint Conference on Artificial Intelli- gence.San Mateo，CA：Morgan Kaufmann，1993：1022-1027. [2] Kurgan L A，Cios K J.CAIM discretization algorithm[J].IEEE Transactions on Knowledge and Data Engineering，2004，16 （2）：145-153. [3] Yang Ping，Yang Tianshe，Du Xiaoning.A class-attribute inter- dependency maximization based algorithm for discretization[J].Control and Decision，2011，26（4）：592-596. supervised [4] Tsai C J，Lee C I，Yang W P.A discretization algorithm based on class-attributes contingency coefficient[J].Information Sci- ences，2008，178（3），714-731. [5] Kerber R.Chimerge：discretization of numeric attributes[C]// Proceedings the 9th National Conference on Artificial Intel- ligence.[S.l.]：AAAI Press，1992：123-128. [6] Boulle M.Khiops：a statistical discretization method of con- tinuous attributes[J].Machine Learning，2004，55：53-69. [7] Ruiz F J，Angulo C，Agell N.IDD：a supervised interval distance-based method for discretization[J].IEEE Transac- tions on Knowledge and Data Engineering，2008，20（9）： 1230-1238. （下转 198 页）