5数据挖掘过程讲诉.ppt

5.2.5 数据归约——数值归约 采用选样进行数据归约的优点是，选样的复杂性子线性（sublinear）于数据的大小。其他数据归约技术至少需要完全扫描D。 对于固定的样本大小，选样的复杂性仅随数据的维数d线性地增加；而其他技术，如使用直方图，复杂性随d指数增长。 用于数据归约时，选样通常用来回答聚集查询。在指定的误差范围内，可以确定（使用中心极限定理）估计一个选定的函数在指定误差范围内所需的样本大小。样本的大小n相对于N可能非常小。 对于归约数据集的逐步求精，选样是一种自然选择。这样的集合可以通过简单地增加样本而进一步提炼。 5.2.6 离散化和概念分层生成 通过将属性域划分为区间，离散化技术可以用来减少给定连续属性值的个数。通常，这种方法是递归的，大量的时间花在每一步的数据排序上。因此，待排序的不同值越少，这种方法就应当越快。许多离散化技术都可以递归使用，以便提供属性值的分层或多分解划分——概念分层。 对于给定的数值属性，概念分层定义了该属性的一个离散化。通过收集并用较高层的概念替换较低层的概念，概念分层可以用来归约数据。 通过这种数字概化，尽管细节丢失了，但概化后的数据更有意义、更容易理解，并且所需的空间比原数据少。在归约的数据上进行挖掘，与在大的、未概化的数据上挖掘相比，所需的I/O操作更少，并且更有效。 （1）数值数据的离散化和概念分层的生成 （2）分类数据的概念分层生成 数值数据的离散化和概念分层的生成 数值属性的概念分层可以根据数据分布分析自动地构造。 数值概念分层生成主要有5种方法：分箱、直方图分析、聚类分析、基于熵的离散化和通过“自然划分”的数据分段。 1）分箱 通过将数据分布到箱中，并用箱中的平均值或中值替换箱中的每个值，可以将属性值离散化。 这些技术可以递归地作用于结果划分，产生概念分层。 数值数据的离散化和概念分层的生成 2）直方图分析 直方图分析算法递归地用于每一部分的划分中，自动地产生多个概念分层，直到到达一个预先设定的概念层数，过程终止。 也可以对每一层使用最小区间长度来控制递归过程。 最小区间长度设定每层每部分的最小宽度，或每层每部分中值的最小数目。 3）聚类分析 聚类算法可以用来将数据划分为簇或群。 每一个簇形成概念分层的一个节点，而所有的节点在同一概念层。 每一个簇可以进一步化分成若干子簇，形成较低的概念层。 簇也可以聚集在一起，以形成分层结构中较高的概念层。 数值数据的离散化和概念分层的生成 4）基于熵的离散化 一种基于信息的度量称作熵（entropy），可以用来递归地划分数值属性A的值，产生分层的离散化，这种离散化形成属性的数值概念分层。 给定一个数据元组的集合S，基于熵对A离散化的方法如下： A的每个值可以认为是一个潜在的区间边界或阈值T。例如，A的值v可以将样本S划分成分别满足条件A＜v和A≥v的两个子集，这样就创建了一个二元离散化。 给定S，所选择的阈值是这样的值，它使其后划分得到的信息增益最大。信息增益（information gain）是 数值数据的离散化和概念分层的生成 对于给定的集合，它的熵函数Ent根据集合中样本的类分布来计算。例如，给定m个类，S1的熵是 取定阈值的过程递归地用于所得到的每个划分，直到满足某个终止条件，如 基于熵的离散化可以压缩数据量。与迄今为止提到的其他方法不同，基于熵的离散化使用类信息。这使得它更有可能将区间边界定义在准确位置，有助于提高分类的准确性。 数值数据的离散化和概念分层的生成 5）通过自然划分分段 3—4—5规则可以用于将数值数据划分成相对一致和直观的区间。一般地，该规则根据重要的数字上的值区域，递归地和逐层地将给定的数据区域划分为3，4或5个等宽区间。该规则如下： 如果一个区间在最高有效位上包含3，6，7或9个不同的值，则将该区间划分为3个区间（对于3，6和9，划分为3个等宽区间；而对于7，按2—3—2分组，划分成3个区间）。 如果它在最高有效位上包含2，4或8个不同的值，则将区间划分成4个等宽区间。 数值数据的离散化和概念分层的生成 如果它在最高有效位上包含1，5，10个不同的值，则将区间化分成5个等宽区间。 该规则可以递归地用于每个区间，为给定的数值属性创建概念分层。由于在数据集中可能有特别大的正值和负值，最高层分段简单地按最小和最大值可能导致扭曲的结果。 顶层分段可以根据代表给定数据大多数的数据区间（例如，第5个百分为数到第95个百分位数）进行。超出顶层分段的特别高和特别低的值将用类似的方法形成单独的区间。 数值数据的离散化和概念分层的生成 例5.8 假定某公司所有分部1999年的利润覆盖了一个很宽的区间，由-$351,976.00到$4,700,896.50。用户希望自动地产生利润的概念分层。为了改进可读性，