2.6.1 数值数据的离散化和概念分层产生

2.6.1 数值数据的离散化和概念分层产生

对于数值属性说明概念分层是困难的和令人乏味的，这是由于数据的可能取值范围的多样性和数据值的更新频繁。这种人工地说明还可能非常随意。

数值属性的概念分层可以根据数据离散化自动构造。考察如下方法：分箱、直方图分析、基于熵的离散化、χ2合并、聚类分析和通过直观划分离散化。一般，每种方法都假定待离散化的值已经按递增序排序。

1. 分箱

分箱是一种基于箱的指定个数自顶向下的分裂技术。2.3.2节讨论了数据光滑的分箱方法。这些方法也可以用作数值归约和概念分层产生的离散化方法。例如，通过使用等宽或等频分箱，然后用箱均值或中位数替换箱中的每个值，可以将属性值离散化，就像分别用箱的均值或箱的中位数光滑一样。这些技术可以递归地作用于结果划分，产生概念分层。分箱并不使用类信息，因此是一种非监督的离散化技术。它对用户指定的箱个数很敏感，也容易受离群点的影响。

2. 直方图分析

像分箱一样，直方图分析也是一种非监督离散化技术，因为它也不使用类信息。直方图将属性A的值划分成不相交的区间，称作桶。直方图已在2.2.3节介绍。定义直方图的划分规则已在2.5.4节介绍。例如，在等宽直方图中，将值分成相等的划分或区间（如图2-19的price， 其中每个桶宽度为10美元）。使用等频直方图，理想地分割值使得每个划分包括相同个数的数据元组。直方图分析算法可以递归地用于每个划分，自动地产生多级概念分层，直到达到预先设定的概念层数过程终止。也可以对每一层使用最小区间长度来控制递归过程。最小区间长度设定每层每个划分的最小宽度，或每层每个划分中值的最少数目。正如下面介绍的那样，直方图也可以根据数据分布的聚类分析进行划分。

3. 基于熵的离散化

熵（entropy）是最常用的离散化度量之一。它由Claude Shannon在信息论和信息增益概念的开创性工作中首次引进。基于熵的离散化是一种监督的、自顶向下的分裂技术。它在计算和确定分裂点（划分属性区间的数据值）时利用类分布信息。为了离散数值属性A，该方法选择A的具有最小熵的值作为分裂点，并递归地划分结果区间，得到分层离散化。这种离散化形成A的概念分层。

设D由属性集和类标号属性定义的数据元组组成。类标号属性提供每个元组的类信息。该集合中属性A的基于熵的离散化基本方法如下：

（1）A的每个值都可以看作一个划分A的值域的潜在的区间边界或分裂点（记作split_ point）。也就是说，A的分裂点可以将D中的元组划分成分别满足条件A≤split_point和A > split_point的两个子集，这样就创建了一个二元离散化。

（2）正如上面提到的，基于熵的离散化使用元组的类标号信息。为了解释基于熵的离散化的基本思想，必须考察一下分类。假定要根据属性A和某分裂点上的划分将D中的元组分类。理想地，希望该划分导致元组的准确分类。例如，如果有两个类，希望类C1的所有元组落入一个划分，而类C2的所有元组落入另一个划分。然而，这不大可能。例如，第一个划分可能包含许多C1的元组，但也包含某些C2的元组。在该划分之后，为了得到完全的分类，我们还需要多少信息？这个量称作基于A的划分对D的元组分类的期望信息需求，由下式给出

其中，D1和D2分别对应于D中满足条件A≤split_point和A > split_point的元组，|D|是D中元组的个数，如此等等。给定集合的熵函数Entropy根据集合中元组的类分布来计算。例如，给定

m个类C1, C2, ., Cm，D1的熵是m

其中，pi是D1中类Ci的概率，由D1中Ci类的元组数除以D1中的元组总数|D1|确定。这样，在选择属性A的分裂点时，我们希望选择产生最小期望信息需求（即min(InfoA(D))）的属性值。这将导致在用A≤split_point和A > split_point划分之后，对元组完全分类（还）需要的期望信息量最小。这等价于具有最大信息增益的属性-值对（这方面的进一步细节在第6章讨论分类时给出）。注意，Entropy(D2)的值可以类似于式（2-16）计算。

你可能会说，“但是我们的任务是离散化，而不是分类！”是这样。我们使用分裂点将A的值域划分成两个区间，对应于A≤split_point和A > split_point。

（3）确定分裂点的过程递归地用于所得到的每个分划，直到满足某个终止标准，如当所有候选分裂点上的最小信息需求小于一个小阈值ε，或者当区间的个数大于阈值max_interval 时终止。

基于熵的离散化可以减少数据量。与迄今为止提到的其他方法不同，基于熵的离散化使用类信息。这使得它更有可能将区间边界（分裂点）定义在准确位置，有助于提高分类的准确性。这里介绍的熵和信息增益度量也用于决策树归纳。这些度量将在6.3.2节更详细地讨论。

4. 基于χ2分析的区间合并

ChiMerge是一种基于χ2的离散化方法。到目前为止我们研究的离散化方法都使用自顶向下的分裂策略。ChiMerge正好相反，采用自底向上的策略，递归地找出最佳邻近区间，然后合并它们，形成较大的区间。这种方法是监督的，它使用类信息。其基本思想是，对于精确的离散化，相对类频率在一个区间内应当相当一致。因此，如果两个邻近的区间具有非常类似的类分布，则这两个区间可以合并。否则，它们应当保持分开。

ChiMerge过程如下。初始，将数值属性A的每个不同值看作一个区间。对每对相邻区间进行χ2检验。具有最小χ2值的相邻区间合并在一起，因为低χ2值表明它们具有相似的类分布。该合并过程递归地进行，直到满足预先定义的终止标准。

χ2统计量在2.4.1节讨论数据集成时引入，那里我们解释使用它检测两个分类属性之间的相关（式（2-9））。由于ChiMerge将区间看作离散类别，可以使用式（2-9）。χ2统计量检验假设给定属性的两个相邻区间是类独立的。按照例2-1的方法，可以构造数据的相依表。该相依表有两列（代表两个相邻区间）和m行，其中m是不同类的个数。使用式（2-9），单元值oij是第i个区间中第j个类的元组计数。类似地，oij的期望频率是eij = (区间i中元组的个数)×(类j中元组的个数) / N，其中N是数据元组的总数。一个区间对的低χ2值表明区间是类独立的，因此合并。

终止判定标准通常由三个条件决定。首先，当所有相邻区间对的χ2值都低于由指定的显著水平确定的某个阈值时合并停止。χ2检验的置信水平值太高（或非常高）可能导致过分离散化，而太低（或非常低）的值可能导致离散化不足。通常，置信水平设在0.10～0.01之间。

其次，区间数可能少于预先指定的max-interval，如10～15。最后，回想一下ChiMerge的前提是区间内相对类频率应当相当一致。实践中，某些不一致是允许的，尽管不应当超过某个预先指定的阈值，如3%，这可以由某训练数据估计。最后一个条件可以用来删除数据集中不相关的属性。

5. 聚类分析

聚类分析是一种流行的数据离散化方法。通过将属性A的值划分成簇或组，聚类算法可以用来离散化数值属性A。聚类考虑A的分布以及数据点的邻近性，因此，可以产生高质量的离散化结果。遵循自顶向下的划分策略或自底向上的合并策略，聚类可以用来产生A的概念分层，其中每个簇形成概念分层的一个节点。在前者，每一个初始簇或划分可以进一步分解成若干子簇，形成较低的概念层。在后者，通过反复地对邻近簇进行分组，形成较高的概念层。数据挖掘的聚类方法将在第7章研究。

6. 根据直观划分离散化

尽管上面的离散化方法对于数值分层的产生是有用的，但是许多用户希望看到数值区域划分为相对一致的、易于阅读、看上去直观或“自然”的区间。例如，更希望将年薪划分成像（50 000美元，60 000美元] 的区间，而不是像由某种复杂的聚类技术得到的（51 263.98美元, 60 872.34美元] 那样的区间。

3-4-5规则可以用来将数值数据分割成相对一致、看上去自然的区间。一般，该规则根据最高有效位的取值范围，递归逐层地将给定的数据区域划分为3、4或5个相对等宽的区间。我们将用一个例子解释这个规则的用法。规则如下：

. 如果一个区间在最高有效位包含3, 6, 7或9个不同的值，则将该区间划分成3个区间（对91 于3, 6和9，划分成3个等宽的区间；而对于7，按2-3-2分组，划分成3个区间）。

. 如果它在最高有效位包含2, 4或8个不同的值，则将区间划分成4个等宽的区间。

. 如果它在最高有效位包含1, 5或10个不同的值，则将区间划分成5个等宽的区间。该规则可以递归地用于每个区间，为给定的数值属性创建概念分层。现实世界的数据常常包含特别大的正和负的离群值，基于最小和最大数据值的自顶向下离散化方法可能导致扭曲的结果。例如，在资产数据集中，少数人的资产可能比其他人高几个数量级。按照最高资产值离散化可能导致高倾斜的分层。这样，顶层离散化可以根据代表给定数据大多数的数据值区间（例如，第5个百分位数到第95个百分位数）进行。超出顶层离散化区间的特别高和特别低的值可以用类似的方法单独处理成不同的区间。

下面是一个自动构造数值分层的例子，解释3-4-5规则的使用。

例2-6 根据直观划分产生数值概念分层。假定AllElectronics不同分店2004年的利润覆盖了一个很宽的区间－351 976.00美元～4 700 896.50美元。用户希望自动地产生利润的概念分层。为了改进可读性，我们使用记号(l.r ]表示区间(l, r ]。例如，(－1 000 000美元.0美元] 表示由－1 000 000美元（开的）到0美元（闭的）的区间。

假定第5个百分位数和第90%个百分位数中的数据在－159 876美元和1 838 761美元之间。使用3-4-5规则的结果如图2-23所示。

图2-23 根据3-4-5规则，profit概念分层的自动产生

（1）根据以上信息，最小和最大值分别为MIN =－351 976.00美元和MAX = 4 700 896.50 美元。对于离散化的顶层或第一层，要考虑的最低（第5个百分位数）和最高（第95个百分位数）值是：LOW =－159 876美元，HIGH = 1 838 761美元。

（2）给定LOW和HIGH，最高有效位（msd）在百万美元数字位（即msd = 1 000 000）。LOW向下对百万美元数字位取整，得到LOW' =－1 000 000美元；HIGH向上对一百万美元数

字位取整，得到HIGH' = + 2 000 000美元。

（3）由于该区间在最高有效位上跨越了三个不同的值，即(2 000 000－(－1 000 000)) / 1 000 000 = 3，根据3-4-5规则，该区间划分成三个等宽的区间：(－1 000 000美元.0美元]、(0美元.1 000 000美元]和(1 000 000美元.2 000 000美元]。这代表分层结构的最顶层。

（4）现在考察MIN和MAX的值，看它们“适合”在第一层划分的什么地方。由于第一个92 区间(－1 000 000美元.0美元]覆盖了MIN值（即LOW' < MIN），我们可以调整该区间的左边界，93 使区间更小。MIN的最高有效位在10万数字位。MIN向下对10万数字位取整，得到MIN' = －400 000美元。因此，第一个区间重新定义为(－400 000美元.0美元]。

由于最后一个区间(1 000 000美元.2 000 000美元]不包含MAX值，即MAX > HIGH'，我们需要创建一个新的区间来覆盖它。MAX向上对最高有效位取整，新的区间为(2 000 000美元.5 000 000美元]。因此，分层结构的最顶层包含4个区间：(－400 000美元.0美元]，(0美元.1 000 000美元]，(1 000 000美元.2 000 000美元]和(2 000 000美元.5 000 000美元]。

（5）递归地，每一个区间可以根据3-4-5规则进一步划分，形成分层结构的下一个较低层：

. 第一个区间(－400 000美元.0美元]划分成4个子区间：(－400 000美元.－300 000美元]， (－300 000美元.－200 000美元]，(－200 000美元.－100 000美元]和(－100 000美元.0美元]。

. 第二个区间(0美元.1 000 000美元]划分成5个子区间：(0美元.200 000美元]，(200 000美元.400 000美元]，(400 000美元.600 000美元]，(600 000美元.800 000美元]和(800 000美元.1 000 000美元]。

. 第三个区间(1 000 000美元.2 000 000美元]划分成5个子区间：(1 000 000美元.1 200 000美元]，(1 200 000美元.1 400 000美元]，(1 400 000美元.1 600 000美元]，(1 600 000美元.1 800 000美元]和(1 800 000美元.2 000 000美元]。

. 最后一个区间(2 000 000美元.5 000 000美元]划分成3个子区间:(2 000 000美元.3 000 000 美元]，(3 000 000美元.4 000 000美元]和(4 000 000美元.5 000 000美元]。

类似地，如果必要，3-4-5规则可以在更深层继续迭代执行。