Fayyad等在paper[1]提到过一种连续值离散化的方法：MDPLP。下面简单来看下：
1.介绍
分类学习算法通常要使用启发法（heuristics）来在多个属性值和类的组合间的可能关系空间上进行搜索。其中有一种这样的启发法（heuristic），它被使用在数据集中的分类上的选择局部最小化信息熵（比如ID3算法、C4､CART等）
机器学习中的属性可以是类别型的，也可以是连续型（数值型）。上述提到的属性选择过程假设所有的属性都是类别型的。连续型的属性在选择之前需要进行离散化（discretized），通过通过将属性的range范围进行划分成subrange范围。总体上，离散化是一个简单的逻辑条件，将数据划分成至少两个子集。
本文主要关注连续型属性的离散化。首先来看下二元离散化（binary discretization）。接着来看多区间离散化（multi-interval discretization）。
2.二元离散化
连续值属性通常在决策树生成时通过将它的值范围离散化成两个区间。对于连续型属性A，阈值为T， $ A \leq T $被分配到左分枝，$ A \gt T $被分配到右分枝。我们将该阈值T称为分割点（cut point）。该方法被用于ID3算法以及它的变种CART算法中的GID3。它可以被用于任何分类树算法，或者用来处理将连续型属性划分成二个区间的规则。尽管这里我们将它应用于离散化，在决策树生成的topdown的特定上下文也有使用。
假设在一个节点（样本集S具有N个样本）上对一个属性进行分枝。对于每个连续型属性A，我们在值的范围上选择最好的（“best”）分割点$ T_A $。样本首先通过属性A的值升序排列，在排完序序列中每个后继样本对（example pair）间的中点会作为一个潜在的分割点进行评估。这样，对于每个连续值属性，会发生N-1次评估（假设样本没有相同的属性值）。对于候选分割点T的每次评估，数据都会划分成两个集合，结果分区的分类熵（class entropy）会被计算。回忆一下，该离散化过程也会在决策树中的每个节点被执行。
样本集S通过T划分成两个子集：S1和S2 。假设存在K个类：$ C_1, …, C_k $，让$ P(C_i, S) $是S中含有类别$C_i$的样本比例。那么子集S的分类熵（class entropy）被定义成：
\[Ent(S) = - \sum_{i=1}^{k} P(C_i,S) log(P(C_i,S))\]其中的log基数取2 。 Ent(S)用来衡量在S中的指定的分类信息量，单位为：bits。在集合S被划分成S1和S2后，为了评估生成的分类熵，我们采用它们生成的分类熵的加权平均：
定义1：对于一个样本集S，一个属性A，一个分割值T：假设$ S_1 \in S $是在样本S中的子集，它的A属性值$\leq T$，并且满足$ S_2 = S - S_1 $。分区的分类信息熵通过T索引，E(A,T;S)被定义成：
\[E(A,T;S) = \frac{|S_1|}{|S|} Ent(S_1) + \frac{|S_2|}{|S|} Ent(S_2)\]…(2)
A的二分离散化通过选择分割点$T_A$来决定，其中$E(A, T_A; S)$是所有候选分割点中的最小值。
2.1 分割点选择的讨论
选择标准（selection criterion）的主要问题之一是：它的开销相当昂贵。尽管它是多项式复杂度，它为每个属性必须评估N-1次（假设有N个不同值的样本）。因为机器学习问题通常被设计成很大的训练量，N通常很大。当对一个类别型（离散化）属性进行时，该标准（criterion）只需要对r个分区进行单次评估即可，其中r为类别的数目。通常$ r « N$。确实，像ID3这样的算法在运行连续型属性时确实会慢许多。
其它缺点是：该算法具有一个天生的缺陷，当超过两个分类时，会生成”坏（bad）”的分割点。该缺点基于一个事实：该算法尝试最小化侯选二元划分集合的加权平均熵（如方程1所示）。分割点可能因此将一个分类的样本以最小化平均熵的方式进行分割。图1展示了这种情况。分割点并不会落在边界B1或B2上的其中之一，则是会落在两边的平均熵最小的点上。
这不是我们所期望的，因为它没必要将相同分类的样本分隔开，产生更大（但质量更低）的树。
然而，这些缺点不会被证明是对的。下面的理论1会展示，不管有多少分类，不管如何离散化，分割点将总是发生在两个类的边界上（见定义2, 它会对边界点有一个精准的说明）。这确实是该启发法（heuristic）的一个期待的特性，因为它展示了该启发法（heuristic）是“表现良好的（well-behaved）”。它告诉我们该启发法（heuristic）将从不选择一个在结果上（目的论：teleological）被认为是“坏”的分割（cut）。另外，该结果将帮助我们在不改变该功能的情况下提升算法的效果。
2.2 分割点总是在边界上
我们展示了属性A的值$ T_A $会最小化平均分类熵$E(A,T_A;S)$: 对于一个训练集S，必须总是在排序后样本序列不同分类的两个样本间的值。假设A(e)表示样本$ e \in S$的A值。
定义2：范围A中的值T是一个边界点，因此存在两个样本：$ e_1, e_2 \in S$具有不同的分类。比如：$A(e_1) < T < A(e_2) $，不存在着这样的样本$e’ \in S$，使得：$A(e_1) < A(e’) < A(e_2) $。
理论1：如果T能最小化E(A,T;S)，那边T就是一个边界点
证明：相当长，忽略。见paper[5]
推论1 用于ID3的该算法，可用于为连续型属性发现一个二分划分，将总是在排好序的属性样本对一个边界点划分数据。
证明：跟据理论1和定义。
推论1的第一个含义是，它可用于支持在离散化时最小化熵。我们使用信息熵的启发法（heuristic），因为我们知道，它控制一些衡量离散化需要的属性。然而，本身并不能排除不希望的情况，比如，图1中的情况。推论声明，“明显坏（obviously bad）”的分割从不会被该启发法（heuristic）所喜欢。该结果可进一步支持在离散化中使用该启发法（heuristic），因为它告诉我们，该启发法（heuristic）从目的论（teleological）的角度是表现良好的。
另外，推论1可以被用于在完全不需要更改效果的情况下增加算法的效果。通过对属性A的值进行排序之后，该算法只需要检查边界点b，而非所有的N-1个侯选。注意：$ k-1 \leq b \leq N-1 $。因为常通k « N，我们会期望节省很大的计算开销。我们演示了对ID3算法的所要评估的潜在分割点的数目上有极大的加速。ID3将连续值属性划分成两个区间。算法会检查多个区间，使用该过程的一个泛化版本（比如：下一节中要讲的一个）来达到更高的加速。算法会搜索规则，而非决策树，在离散化时会花费更多的开销。评估过程的计算加速只是推论1的一个附带效果。它的语义重要性是本文关注的，因为它证明了我们的泛化相同的算法，来生成多个区间，而非两个。
3.泛化该算法
推论1也提供了对扩展该算法的支持，在单个离散化过程中来抽取多个区间，而非两个。该动机是获取更好（“better”）的树。
训练集会做一次排序，接着算法会使用递归，总是选择最好的分割点。所使用的一个原则是：避免对一个给定区间做更进一步的二元划分。事实上，只会考虑这样的边界点：让自顶向下（top-down）的区间的得到更可行（因为该算法从不会在top上提交一个”bad”分割点），并且能减小计算开销。
为了合理地定义这样的一个算法，我们需要用公式来表示这个原则（criterion），以决定对一个给定样本做限制划分。该criterion需要理论支持。期望的测试将在后续被用于验证该理由是否合理。
从树生成的角度上看，为什么多区间（multiple range）的派生版本比二元区间（binary range）有更大的优点呢？通常，“感兴趣（interesting）”的范围可以是在属性值范围内的一个内部区间。为了得到这样的一个区间，单次做二元区间划分（”binary-interval-at-a-time”）的方法将导致不必要的、并会对样本做出超出感兴趣区间范围的过多划分。例如，假设，对于在[0,40]的属性值A，子区间 $ 12 < A \leq 20$是我们感兴趣的。假设A的范围离散化成：$ (-\infty,12), [12,20), [20,25), [25,\infty) $。给定一个算法，比如GID3,它能过滤出不相关的属性值，原则上可以获得如图2(a)所示的决策树。属性选择算法决定着只有2/4的区间是相关的。在区间外的样本会被分组到图中label=S的子集。
为了选择如图2(b)中生成的决策树两个区间范围，可以只使用一个二分区间离散化算法。注意，集S没必要划分成两个子集S1和S2 。对于第一棵树，该算法有机会使用一些其它的属性对S进行划分。该选项在第二种情况下不再使用，进一步的属性选择基于更小的子集：S1和S2. 必要的，这会导至相同的排序问题，会造成不相关值问题（irrelevant valus problem）。关于GID3如何处理该问题，以及如何只有一个子集的值被分支超出了本文的范围。
3.1 分割还是不分割？
给定集合S和一个潜在的二元划分$ \pi_{T}$，它表示在集合S上对属性A的分割值T，我们需要决定是否接受这次划分。该问题天然可以公式化成一个二分决策问题：接受或者拒绝$\pi_T$。假设HT为假设函数，其中$\pi_T$决定着是否接受。也就是说，HT是分类器，它会测试A的值，而非T，接着会对样本进行分类：根据在E中的样本小于T的值，A值<T。相似的，让NT来表示表示零假设（null hypothesis）：该假设会导致$\pi_T$被拒绝。NT会根据E中的类别来对所有样本进行分类，不需要检查A值。因为接受或拒绝都只是可能的动作，其中之一必然是正确的；另一个不正确。当然，没有其它办法来直接决定哪个是正确的。
假设$d_A$表示决定着接受划分$ \pi_T$，$d_R$表示拒绝。该情况中可能的决策集合是$ D= \lbrace d_A, d_R \rbrace $，我们具有待解决的一个二分决策问题。如果我们分配了一个cost给错误的决策，那么与一个决策规则（在$ {d_A, d_R} $间进行选择）相关的期望cost如下：
\[B = c_{11} Prob(d_A \wedge HT) + c_{22} Prob (d_R \wedge NT) + c_{12} Prob(d_A \wedge NT) + c_{21} Prob (d_R \wedge HT)\]其中$c_{11}$和$c_{12}$表示做出正确选择的costs，而$c_{12}$和$c_{21}$表示做出错误决策的costs。这是期望贝叶斯风险（expected Bayes risk），决策规则被用于选择 $ \lbrace d_A, d_R \rbrace $的其中之一。贝叶斯决策原则（Bayes decision criterion），会调用选择决策规则来最小化期望的cost。
由于我们知道，分配给$c_{12}$和$ c_{21} $是什么值，我们会对均匀error cost分配做重排序。如果$ c_{11} = c_{22} = 0$和 $ c_{12} = c_{21} = 1$，那么最小化Bayes risk会减小一个决策规则PEC（Probalility-of-Error Criterion），它会最小化做出错误决策的概率。接着，它会通过一个简单的派生来展示Bayes决策原则来减小采用的决策规则，给定数据集S，选择假设HT，$ Prob(HT | S)$是计算假设的最大量。我们将该决策原则适用成”贝叶斯决策策略（Bayesian Decision Strategy）”。该策略有时也被称为MAP原则（maximum a posteriori），等价于PEC。
对于我们的决策问题，Bayesian decision strategy会选择$d \in D$的决策，它对应于在数据集S上具有最大概率的hypothesis：这样，如果$ Prob(HT | S) > Prob (NT |S)$，那么我们选$ d_A$。如果我们有一个方法来决策着上述两个要解决问题的概率：简单地选择hypothesis，它具有更高的概率，Bayesian决策策略会保障这是最好的策略。不幸的是，没有简单的方法来直接计算这样的概率。然而，我们应采用这样的方法：它将允许我们直接估计哪个概率更大。
3.2 MDLP(最小描述长度原则)
一个对象的最小描述长度（minimum description）被定义成所需的最小的位数，来唯一指定对象脱离于通用的所有对象。
我们会展示该决策问题，给定一个固定的样本集合，我们使用MDLP来猜测带有更高概率的hypothesis。MDLP是一个通用的原则，它的目的是，对自然界中天然的偏差进行编码，朝着更简单的理论来解释数据的相同部分。MDLP被Rissanen引入，之后被其它人使用。定义如下：
定义3：给定一个假设集合，以及一个数据集S，MDLP会调用假设HT来：$ MLength(HT) + MLength(S |HT) $是在假设集上的最小值。MLength(HT)表示对HT编码的最小可能长度，而 $ MLength(S |HT) $是对给定hypothesis编码的最小编码长度。
为了方便，我们假设长度的单位是：bits。数据的编码可以被认为是对数据点进行编码，它们是对于hypothesis HT来说“异常点（exceptions）”。如果HT能完全拟合数据，那么后一项将为0.
MDLP原则不必要要求与之前讨论的决策原则不同。它可以轻易地展示MDLP和Bayesian risk minimization strategy在理论上是相互相关的。由于篇幅原因，我们忽略了派生版本，它包含着可以包含对数据集S的hypothesis H所需要指定的bits数：$ -log_2 (Prob(H|S)) $，使用Bayes’ rule。最终获得的表达式等价于MDLP。这可以看成是采用MDLP的动机。
基于最早的争论，如果我们具有一种方法来发现真实的hypotheses的最小编码长度，那么采用MDLP来选择一个完整hypotheses的集合会导致使用最大MAP的hypothesis。接着，它等价于PEC决策原则。这意味着，选中的hypothesis将会最小化做出错误选择决策的概率。然而，在物理世界中，我们不会访问概率分布。因而，MDLP被用于对cost的估计，来在hypotheses间做比较。
3.3 应用MDLP：编码问题
现在，一个问题是编码问题（coding problem）。在我们的情况下，决策问题相当简单。完整的hypotheses包含了两个元素：{HT, NT}。我们应采用Quinlan和Rivest的公式，他们在属性选择上使用MDLP来尝试生成紧凑的决策树。在我们的情况下，该问题相当简单。
使用该公式，该问题需要解决的问题是通信问题。目标是通信一个方法（分类器），它可以允许接收器（receiver）来决定在数据集中的样本分类label。假设一个发送器（sender）具有整个训练数据样本集。而接收器具有没有该分类label的样本。sender只需要将合理的分类labeling传送给receiver。sender必须选择最短描述来指定该分类。
对Null Theory NT进行编码：在NT的情况下，sender必须简单地传递在S中的样本的类别。sender发送了N条消息，每个都是一个被编码过的类别label（其中N=$ | S | $）。为了编码在S中的样本的类别，我们必须使用一个最优化算法（比如：Huffman coding）来生成编码来优化平均编码长度。因为我们必须传递在集合S中每个样本的类别，将平均编码长度l乘以N给出了总的cost。另外，需要传递“code book”来用于解码类别。传递的code book的包含了每个类别对应的code word。因而，如果存在着K个分类，code book的长度可以通过(k * l)进行预估。注意，K是一个常数，不能随着N增长，因此，code book的cost是一个小的常数开销。
对划分HT进行编码：选中的分割点会对样本分区，必须由sender根据每两个子集中的分类编码来指定。指定分割点的开销为$log_2(N-1)$ bits，因为我们需要指定序列（分割点在之间落的地方）中N-1个样本的其中之一。
分类器HT对应于二分划分，$ \pi_T $，将集合S划分成子集：S1和S2。其中Sender必须传递分割点的一个说明书，根据S1中的类别序列，根据S2中的类别。再者，我们感兴趣的是，对S1和S2中的类别编码使最小化平均长度，如同在S中的类别编码所做的。其中$ l_1 $和$ l_2 $是对应于S1和S2各自的最小化平均编码长度（单位：bits）。传递HT的cost随着HT的数据一起：
\(log_2(N-1) + | S_1 | \cdot l_1 + | S_2 | \cdot l_2\) (bits)
我们也需要为S1和S2的类别编码各自传递code books。不同于传递S的情况(k个类别)，该情况我们必须通知receiver，哪个类别的子集会在两个子集S1和S2的其一中被表示，接着传递各自的code books。因为我们知道我们的划分是非平凡解（non-trivial）的，例如：$ S_1 \neq S_2 \neq \emptyset $，我们知道S1可能具有$2^k-1$个可能的k个类别的子集。使用一个长度派生版本，它可以被表示成：
\[G_k = [ \sum_{k_1=1}^{k-1} (C_{k_1}^{k}) 2^{k_1}] + 2^k - 1 = 3^k - 2\]是可能的划分数目，超出我们需要指定的。由于我们需要$ log_2(G_k) $ bits。注意：$ log_2(G_k) < 2 log_2(2^k-1) < 2k$.
##