《数据挖掘原理、算法及应用》课件第2章

第2章数据预处理

2.1数据预处理的目的2.2数据清理2.3数据集成和数据变换2.4数据归约2.5数据离散化和概念分层2.6特征选择与提取2.1数据预处理的目的

数据源中的数据可能不完整(如某些属性值的空缺)、含噪声(具有不正确的属性值)和不一致(如同一属性的不同名称)。不完整数据的出现可能有多种原因：某些数据被认为是不必要的，如销售事务数据中顾客的信息并非总是可用的；其他数据没有包含在内，可能只是因为输入时认为是不重要的；由于理解错误，或者因为设备故障相关数据没有记录；某些记录与其他记录的内容不一致而被删除；记录历史或修改的数据可能被忽略。

空缺的数据，特别是某些属性上缺少值的元组可能需要推导。数据含噪声可能有多种原因：数据采集设备可能出故障；在数据录入过程中发生了人为的或计算机导致的错误；可能由于技术的限制，数据传输过程中出现错误；不正确的数据也可能是由命名或所用的数据代码不一致而导致的。重复元组有时也需要进行数据清理。数据清理(DataCleaning)例程通过填补空缺数据平滑噪声数据，识别、删除孤立点，并纠正不一致的数据。异常数据可能使挖掘过程陷入混乱，导致不可靠的输出。数据集成(DataIntegration)指将来自不同数据源的数据合成一致的数据存储。数据变换(DataTransformation)操作，如规格化和聚集，是将数据转换成适于挖掘的形式的预处理过程。数据归约策略有助于从原有的庞大的数据集中获得一个精简的数据集合，并使这一精简数据集保持原有数据集的完整性。在精简数据集上进行的数据挖掘显然效率更高，并且挖掘结果与使用原有数据集的结果基本相同。概化也可以“归约”数据。概化用较高层的概念替换较低层的概念。图2-1对上述数据预处理进行了图解。以上的数据预处理并不互斥，例如，冗余数据的删除既是数据清理，也是数据归约。图2-1数据预处理的形式总之，数据源中的数据一般是含噪声的、不完整的和不一致的。数据预处理技术可以改进数据的质量，从而改善挖掘过程的性能，提高挖掘结果的质量。高质量的决策必然依赖于高质量的数据，因此数据预处理是知识发现过程的重要步骤。2.2数据清理

2.2.1空缺值空缺值是指所关心的某些属性对应的部分属性值是空缺的。在数据挖掘过程中，这些空缺值会对挖掘结果带来影响，因此需要进行相应的处理。主要方法如下：

(1)忽略元组，即不选择有空缺值的元组。此方法不是很有效，除非元组有多个属性缺少值时。

(2)人工填写空缺值。通常数据挖掘所涉及的数据量较大，如果空缺值很多，这种方法比较费时，几乎行不通。

(3)使用一个全局常量填充空缺值，即对一个属性的所有空缺值都使用一个事先确定好的值(如“OK”或-∞)来填补。虽然此方法比较简单，但并非总是正确的，例如空缺值都用“OK”替换，挖掘程序可能误以为它们形成了一个有趣的模式。

(4)使用属性的平均值填充空缺值。例如，若一个顾客的平均收入(income)为16000元，则用此值填补income属性中的所有空缺值。

(5)使用与给定元组属同一类的所有样本的平均值。例如，在分类挖掘中，使用与给定样本属于同一类的其他样本的平均值来填充空缺值。

(6)使用最可能的值填充空缺值：可以用回归、贝叶斯形式化方法的工具或判定树归纳确定最有可能的值。当有空缺值的数据不是孤立点时，此方法有较高的准确性。2.2.2噪声数据

噪声(Noise)是一个测量变量中的随机错误或偏差。下面介绍四种数据平滑技术。

1.分箱(Binning)分箱方法通过考察“邻居”(即周围的值)来平滑存储数据的值。存储的值被划分到若干个箱或桶中。由于仅考察被平滑点邻近的数据，因此分箱方法进行的是局部平滑。例2.1展示了一些分箱技术。在该例中，score数据首先被划分并存入等深(每个箱中的数据个数相等)的箱中。平均值平滑是指将同一箱中的数据全部用该箱中数据的平均值替换。例如，箱1中的值60,65,67的平均值是64，那么该箱中的每一个值被替换为64。类似地，可以使用按箱中值平滑，此时，箱中的每一个值被箱中的中值替换；按箱边界平滑，箱中的最大和最小值被视为箱边界，箱中的每一个值被最近的边界值替换。分箱技术可以采用等深和等宽的分布规则对数据进行平滑，等深指每个箱中的数据个数相同，等宽指每个箱的取值范围相同。分箱也可以作为一种离散化技术使用。【例2.1】[ST][HT]

score排序后的数据(分):60,65,67,72,76,77,84,87,90划分为(等深，深度为3)箱(桶)：箱1:60,65,67箱2:72,76,77箱3:84,87,90采用分箱平滑技术后，用平均值平滑得：箱1:64,64,64箱2:75,75,75箱3:87,87,87用边界值平滑得：箱1:60,67,67箱2:72,77,77箱3:84,84,90

2.聚类(Clustering)孤立点可以被聚类检测。通过聚类可以发现异常数据(Outliters)，相似或相邻近的数据聚合在一起形成了各个聚类集合，而那些位于聚类集合之外的数据，自然被认为是异常数据(孤立点)。直观地看，落在聚类集合之外的值被视为孤立点，如图2-2所示。孤立点将被视为噪声数据而消除。图2-2孤立点可以被聚类分析检测

3.计算机检查和人工检查结合

通过人与计算机相结合的检查方法，可以帮助识别孤立点。例如，利用机遇信息论方法可以帮助识别用于手写符号库中的异常模式，所识别出的异常模式可以输出到一个列表中，然后由人对这一列表中的各异常模式进行检查，并最终确认无用的模式。这种人机结合检查的方法比单纯利用手工方法手写符号库进行检查要快得多。

4.回归(Regression)可以利用拟合函数对数据进行平滑。例如，线性回归需要找出适合两个变量的“最佳”直线，使得一个变量能够预测另一个。多线性回归是线性回归的扩展，它涉及多于两个变量。利用回归分析方法获得的拟合函数，能够帮助平滑数据并除去其中的噪声。

许多数据平滑的方法也是离散化的数据归约方法。例如，上面介绍的分箱技术减少了每个属性的不同值的数量。概念分层是一种数据离散化形式，也可以用于数据平滑。例如，score的概念分层可以把score的值映射到优、良、中、及格和不及格，从而减少了挖掘过程所处理的值的数量。有些分类方法有内置的数据平滑机制，如神经网络。2.2.3不一致数据现实世界的数据可能常出现数据记录内容的不一致。有些数据不一致可以用其与外部的关联手工加以解决。例如，数据输入时的错误可以与原稿进行对比来加以纠正。知识工程工具也可以用来检测违反限制的数据。例如，知道属性间的函数依赖，可以查找违反函数依赖的值。由于同一属性在不同数据库中的取名不规范，常常使得在进行数据集成时，不一致的情况发生，也可能存在冗余。2.3数据集成和数据变换

2.3.1数据集成数据分析任务多半涉及数据集成。数据集成将多个数据源中的数据结合起来存放在一个一致的数据存储(如数据仓库)中。数据源可能涉及多个数据库、数据立方体或一般文件。在数据集成时，需要解决以下几个问题：

(1)模式集成的过程中涉及到的实体识别问题。这类问题主要是来自多个信息源的现实世界的实体如何才能“匹配”的问题。例如，确信一个数据库中的customer_id和另一个数据库中的cust_number指的是同一实体。通常，数据库和数据仓库中的元数据(关于数据的数据)可以帮助避免模式集成中的错误。

(2)冗余问题。冗余是数据集成中的另一个重要问题。如果一个属性可以从其他属性中推演出来，该属性就是冗余的，如年薪。属性或维命名的不一致也可能导致数据集中的冗余。利用相关分析可以帮助发现一些数据冗余情况。例如，给定两个属性，根据可用的数据，这种分析可以度量一个属性能在多大程度上蕴涵另一个属性。属性A和B之间的相关性可用下式度量：其中，n是元组个数；σA和σB分别为属性A和B的标准差。如果(2.1)式的值大于0，则A和B是正相关的，意味着A的值随B的值增加而增加。该值越大，说明A、B正相关关系越密切。因此，一个很大的值表明A(或B)可以作为冗余而被去掉。如果结果值等于0，则A和B是独立的，两者之间没有关系。如果结果值小于0，则A和B是负相关的，一个值随另一个值减少而增加，这表明每一个属性都阻止另一个属性出现。(2.1)式可以用来检测（1）中的customer_id和cust_number的相关性。除了检测属性间的冗余外，还应当检测元组级的“重复”。重复是指对于同一数据，存在两个或多个相同的元组。

(3)数据集成过程中的数据值冲突的检测与处理问题。例如，对于同一实体，不同数据源的属性值可能不一致。这可能是因为表示的差异、比例尺度或编码不同造成的。例如，长度属性可能在一个系统中以公制单位存放，而在另一个系统中以英制单位存放；价格属性不同地点采用不同的货币单位。数据在语义上的差异，是数据集成的巨大挑战。2.3.2数据变换数据变换将数据转换成适合于挖掘的形式。常用的数据变换方法如下：

(1)平滑(smoothing)：帮助去除数据中的噪声。这种技术包括分箱、聚类和回归。

(2)聚集：对数据进行汇总和聚集操作。例如，可以聚集日销售数据，计算月和年销售额。通常，这一步用来为多粒度数据分析构造数据立方体。

(3)数据概化：用更抽象的概念来取代低层次或数据层的数据对象。例如，分类的属性，如price，可以概化为较高层的概念，如cheap、moderatelypriced或expensive。类似地，数值属性，如age，可以映射到较高层概念，如young、middleage和senior。

(4)规范化：将有关属性数据按比例投射到特定的小范围内，如-1.0~1.0或0.0~1.0。规范化可以消除数值型属性因大小不一而造成的挖掘结果偏差。对于分类算法，如涉及神经网络的算法或诸如最临近分类和聚类的距离度量分类算法，规范化特别有用。如果使用神经网络后向传播算法进行分类挖掘，训练样本的规范化能够提高学习的速度。有许多数据规范化的方法，此处介绍三种：最小—最大规范化、z-score规范化和按小数定标规范化。最小—最大规范化方法是对初始数据进行一种线性变换。假定，minA和maxA分别为属性A的最小值和最大值。最小—最大规范化方法通过下式(2.2)将A的值v映射到区间［new_minA,new_maxA］中的v′。最小—最大规范化保留了原始数据中存在的关系。如果将来遇到目前属性A取值范围之外的数据，则该方法将面临“越界”错误。

【例2.2】假定某属性的最小与最大值分别为$8000和$14000。要将其映射到区间［0.0，1.0］。按照最小-最大规范化方法对属性值进行缩放，则属性值$12600将变换为

z-score(零—均值)规范化方法根据属性A的平均值和标准差对A进行规范化。A的值v被规范化为v′，由下式计算：(2.3)其中，和σA分别为属性A的平均值和标准差。该方法常用于属性A最大值和最小值未知的情况，或孤立点左右了最大—最小规范化的情况。

【例2.3】若属性income的平均值和标准差分别为$32000和$17000,则使用z-score规范化后，值$65600被转换为按小数定标规范化方法通过移动属性A的小数点位置进行规范化。小数点的移动位数依赖于A的最大绝对值。

A的值v被规范化为v′，由下式计算：(2.4)其中，j是使得max(|v′|)<1的最小整数。【例2.4】假定A的值为-859~653。A的最大绝对值为859。使用按小数定标规范化方法，用1000(即j=3)除每个值。这样，-859被规范化为-0.859。注意，规范化使得原始数据改变了很多，必须保留规范化参数(如平均值和标准差，如果使用z-score规范化)，以便将来的数据可以用一致的方式规范化。

(5)属性构造(或特征构造)：由已有的属性构造和添加新的属性，以帮助挖掘更深层次的模式知识，提高挖掘结果的准确性。例如，可根据属性height和width添加属性area。属性构造可以减少使用判定树算法分类的分裂问题。通过组合属性，可以帮助发现所遗漏的属性间的相互关系，而这对于数据挖掘是十分重要的。2.4数据归约

数据归约技术可以用来得到数据集的归约表示，它比源数据集小得多，但仍接近于保持原数据的完整性。在归约后的数据集上挖掘将更高效，并能产生相同(或几乎相同)的分析结果。数据归约的策略如下：

(1)数据立方体聚集：主要用于构造数据立方体。

(2)维归约：可以检测并删除不相关、弱相关或冗余的属性或维(数据仓库中的属性)。

(3)数据压缩：利用编码技术压缩数据集的大小。

(4)数值压缩：用较小的数据表示数据或估计数据，如用参数模型(只需要存放模型参数，而不是实际数据)或非参数方法，如聚类、抽样和使用直方图。

(5)离散化和概念分层产生：利用取值范围或更高层次的概念来代替原始数据。概念分层允许挖掘多个抽象层上的模式知识，是数据挖掘的一种强有力的工具。下面详细地介绍几种常用的数据规约策略。2.4.1维归约数据集可能包含成百上千的属性，但大部分属性与挖掘任务不相关，属于冗余属性。例如，分析银行顾客的信用度时，诸如顾客的电话号码、地址等属性与任务不相关。维归约通过减少或删除不相关的属性(或维)减少数据集的规模。通常使用属性子集选择方法。属性子集选择的目标是找出最小属性集，使得数据类的概率分布尽可能地接近原属性集的概率分布。在规约后的属性集上进行挖掘，不仅减少了出现在发现模式上的属性的数目，而且使得模式更易于理解。对于属性子集选择，通常使用压缩搜索空间的启发式算法。属性子集选择的基本启发式方法包括以下几种：

(1)逐步向前选择。方法从空属性集开始，每次从原来属性集合中选择一个当前最优的属性添加到当前属性子集中。直到无法选择出最优属性或满足一定阈值为止。

(2)逐步向后删除。该方法从一个全属性集开始，每次从当前属性集中选择一个当前最差的属性并将其从当前属性集中消去，直到无法选择出最差的属性为止或满足一定阈值为止。

(3)向前选择和向后删除的结合。向前选择和向后删除方法可以结合在一起，每一步选择一个最好的属性，并在剩余属性中删除一个最坏的属性。方法(1)~(3)的结束条件可以有多种。可以用一个阈值来确定是否停止属性选择过程。

(4)判定树归纳：通常用于分类的决策树算法也可以用于构造属性子集，如ID3和C4.5。判定树归纳构造对原数据进行分类归纳学习，获得一个初始判定树，没有出现在树中的属性均被认为是不相关的属性，出现在树中的属性就可以得到一个较优的属性集。2.4.2数据压缩数据压缩就是利用数据编码或数据转换将原始数据集合压缩为一个较小规模的数据集合。可以不丢失任何信息地还原数据的压缩称为无损压缩；构造原始数据的近似表示称为有损压缩。本小节介绍两种流行的和有效的有损数据压缩方法：小波变换和主要成分分析。

1.小波变换离散小波变换(DWT)是一种线性信号处理技术，该技术可以将一个数据向量D转换为另一个数据向量D′(小波相关系数)。两个向量具有相同的长度。小波变换后的数据可以裁减。仅存放一小部分最强的小波系数，就能保留近似的压缩数据。例如，保留大于用户设定的某个阈值的小波系数，其他系数置为0。这样，结果数据表示非常稀疏，若在小波基础上进行的话，利用数据稀疏特点的操作使得计算效率得到大大提高。该技术也能用于消除噪声，并且不会平滑掉数据的主要特性，使得它们也能有效地用于数据清理。给定一组系数，使用所用的DWT的逆，可以还原源数据的近似。流行的小波变换包括Haar_2、Daubechies_4和Daubechies_6变换。应用离散小波变换的一般过程使用一种分层的算法，它在每次迭代时将数据减半，从而获得更快的计算速度。该方法步骤如下：

(1)输入数据向量的长度L，它必须是2的整数幂。必要时，需要在数据向量后添加0，以满足上述条件。

(2)每次变换涉及两个函数。第一个对数据进行平滑，如求和或加权平均；第二个进行带权差分，以获得数据的主要特征。该步将数据一分为二，产生两个长度为L/2的数据集，它们分别代表输入数据平滑后的低频部分和高频部分。

(3)循环使用两个函数作用于数据集，直到结果数据集的长度为2。由以上步骤处理得到的结果即为数据变换的小波系数。类似地，可以使用矩阵乘法对输入数据进行处理，以得到小波系数。所用的矩阵依赖于具体的DWT。矩阵必须是标准正交的，即它们的列是单位向量并相互正交，使得矩阵的逆是它的转置。

小波变换还可以用于多维数据，如数据立方体。具体操作方法为：先对第一维数据进行变换，然后对第二维进行变换，如此下去。计算的复杂性与立方体的单元个数呈线性关系。对于稀疏或倾斜数据和具有有序属性的数据，小波变换能够得到很好的结果。小波变换有许多实际应用，包括指纹图像压缩、计算机视觉、时间序列、数据分析和数据清理。

2.主要成分分析

假定待压缩的数据由N个元组或数据向量组成，取自k个维。主要成分分析(PCA，又称Karhunen－Loeve或K－L方法)从k维数据中寻找出c个正交向量，这里c≤k。通过该方法，原数据被投影到一个较小的空间，实现数据的压缩。PCA可以作为一种维归约形式使用。然而，不同于属性子集选择保留原属性集的一个子集来减少属性集的大小，PCA方法通过创建一个替换的、较小的变量集来“组合”属性的精华。原数据可以投影到此较小的集合中。主要处理步骤如下：

(1)对输入数据规范化，使得每个属性的数据值都落在相同的数值范围内。

(2)计算c个规范正交向量，作为规范化输入数据的基。这些向量是单位向量，两两间相互垂直。这些向量被称为主要成分。输入数据都可以表示为主要成分的线性组合。(3)对c个主要成分按照“重要性”进行递减排序。

(4)根据给定的用户阈值，消去“意义”较低的主要成分。使用最强的主要成分，应当可能重构原数据的很好的近似值。

PCA方法的计算量不大，并且可以用于有序和无序的属性，还可以处理稀疏和倾斜数据。高维数据可以通过将问题归约为2维来处理。与数据压缩的小波变换相比，PCA能较好地处理稀疏数据，而小波变换更适合高维数据的处理变换。2.4.3数值归约

数值规约通过选择替代的、较小的数据表示形式来减少数据量。主要包括有参数与非参数两种基本方法。所谓有参数方法，就是利用一个模型来评估数据，因此只需要存储模型参数即可，而不是实际数据(孤立点也可能被存放)。例如数线性模型，它可以估计离散的多维概率分布。无参方法用于存储利用直方图、聚类和选样归约后的数据集。

1.回归和对数线性模型

回归和对数线性模型可以用来近似给定数据。线性回归方法利用一条直线对数据进行拟合。例如，将随机变量Y(称做响应变量)表示为另一随机变量X(称为预测变量)的线性函数：

Y=α+βX

(2.5)这里，假定Y的方差是常量，系数α和β(称为回归系数)分别为直线的截距和斜率。系数可以用最小二乘法求得，使得分离数据的实际直线与该直线间的误差最小。多元回归是线性回归的扩展，响应变量是多维特征向量的线性函数。对数线性模型(loglinearmodel)近似离散的多维概率分布。该方法能够根据构成数据立方的较小数据块，对其一组属性的基本单元分布概率进行估计，并且可以由较低阶的数据立方体构造较高阶的数据立方体。这样，对数线性还可以进行数据压缩(因为较小阶的方体总共占用的空间小于基本方体占用的空间)，同时具有一定的数据平滑效果(因为与用基本方体进行估计相比，用较小阶的方体对单元进行估计选样变化小一些)。回归和对数线性模型都可以用于稀疏数据和异常数据处理。虽然两种方法都可以用于异常数据，但回归模型的效果好于对数线性模型。回归模型处理高维数据时计算复杂度较大，而对数线性模型具有好的可伸缩性，可以扩展到10维左右。

2.直方图直方图使用分箱方法近似数据分布，是一种常用的数据归约方法。属性A的直方图(histogram)将A的数据分布划分为若干个不相交的子集，或称桶。子集(桶)沿水平轴显示，而高度(和面积)表示值的平均频率。如果每个桶只代表单个属性值/频率对，则该桶称为单桶。通常，桶表示给定属性的一个连续区间。

【例2.5】下面是某商场销售的商品的价格清单(按照递增的顺序排列，括号中的数字表示改价格产品销售的数目)：2(3)，5(6)，8(2)，10(6)，13(9)，15(5)，18(4)，20(7)，21(10)，23(4)，26(8)，28(7)，29(3)，30(8)图2-3使用单桶显示了这些数据的直方图。为进一步压缩数据，通常让一个桶代表给定属性的一个连续值域。在图2-4中每个桶代表商品价格的一个不同的$10区间。

图2-3使用单桶的商品价格直方图—每个桶代表一个商品价格/频率对图2-4商品价格的等宽直方图，值被聚类使得每个桶都有$10宽构造直方图的数据集划分方法有以下几种：

(1)等宽。在等宽的直方图中，每个桶的宽度区间是一个常数(如图2-4中每个桶的宽度为＄10)。

(2)等深(或等高)。在等深的直方图中，每个桶中的数据个数为一个常数(即每个桶大致包含相同个数的临近数据样本)。

(3)V最优。给定桶个数，如果考虑所有可能的直方图，那么V最优直方图是具有最小方差的直方图。直方图的方差是每个桶代表的原数据的加权和，其中权等于桶中值的个数。

(4)MaxDiff。在MaxDiff直方图中，我们考虑每对相邻值之间的差。桶的边界是具有β-1个最大差的对，其中β是由用户指定的阈值。

V-最优和MaxDiff是更精确和实用的方法。对于近似稀疏和稠密数据以及高倾斜和一致的数据，直方图具有较高的效能。直方图可以推广到多属性数据集，多维直方图能够描述属性间的依赖。研究发现，这种直方图对于多达5个属性能够有效地近似表示数据。对于更高维、多维直方图的有效性尚需进一步研究。对于存放具有高频率的孤立点，单桶是有用的。

3.聚类

聚类技术将数据行视为对象。聚类分析所得到的组或类有下述性质：同一类或类中的对象比较相似，不同组或类中的对象彼此不相似。一般的类似性基于多维空间的距离表示，用对象在空间中的“接近”程度定义。聚类的“质量”可以用“直径”表示，直径是指一个聚类中两个任意对象的最大距离。质心距离是聚类质量的另一种度量，以组或类质心(表示“平均对象”，或聚类空间中的平均点)到每个聚类对象的平均距离。图2-5所示为某城市内的大学位置的2D图，每个聚类的质心用“＋”显示，两个数据聚类如图所示。图2-5某城市的大学位置2D图在数据归约时，用数据的聚类替换原始数据。该技术的有效性依赖于数据的性质。如果数据能够组织成不同的聚类，该方法将是有效的。

4.选样

选样可以作为一种数据归约技术使用，它采用数据的较小随机样本(子集)表示大的数据集。假定大的数据集D包含N个元组，几种选样方法如下:

(1)简单选择n个样本，不回放(SRSWOR)。由D的N个元组中抽取n个样本(n<N)，其中D中任何元组被抽取的概率均为1/N。即所有元组是等可能的。

(2)简单选择n个样本，回放(SRSWR)。该方法类似于SRSWOR，不同在于当一个元组被抽取后，记录它，然后放回去。这样，一个元组被抽取后，它又被放回D，以便它可以再次被抽取。这样，最后的n个样本数据集中可能会出现相同的数据行。

(3)聚类选样。如果D中的元组被分组放入M个互不相交的“聚类”，则可以得到聚类的m个简单随机选样，这里m<M。

(4)分层选样。如果D被划分成互不相交的部分，称做“层”，则通过对每一层的简单随机选样就可以得到D的分层选样。特别是当数据倾斜时，这可以帮助确保样本的代表性。例如，可以得到关于顾客数据的一个分层选样，其中分层对顾客的每个年龄组创建。这样，具有最少顾客数目的年龄组肯定能够得到表示。采用选样进行数据归约的优点是，得到样本的花费正比例于样本的大小n，而不是数据的大小N。因此，选样的复杂性子线性(Sublinear)于数据的大小。其他数据归约技术至少需要完全扫描D。对于固定的样本大小，选样的复杂性仅随数据的维数d线性地增加，而其他技术，如使用直方图，复杂性随d指数增长。用于数据归约时，选样最常用来回答聚集查询。在指定的误差范围内，可以确定(使用中心极限定理)估计一个给定的函数在指定误差范围内所需的样本大小。样本的大小n相对于N可能非常小。对于归约数据集的逐步求精，选样是一种自然选择。这样的集合可以通过简单地增加样本大小而进一步提炼。2.5数据离散化和概念分层

2.5.1数值数据的离散化和概念分层生成对于数值属性，由于数据的可能取值范围的多样性和数据值的更新频繁，构造数值属性的概念分层是比较困难的。数值属性的概念分层可以根据数据分布分析自动地构造。下面介绍五种主要的数值概念分层生成方法：分箱、直方图分析、聚类分析、基于熵的离散化和通过“自然划分”的数据分段。

1.分箱前面讨论了数据平滑的分箱方法。此方法也是离散化方法。例如，通过将数据分布到箱中，并用平均值或中值替换方法对箱值进行平滑，可以将属性值离散化。递归地应用这些操作处理每次的结果，就可以产生一个概念层次树。

2.直方图分析前面讨论的直方图也可以用于离散化处理。图2-6给出了一个等宽直方图，显示某给定数据集的数值分布。例如，大部分数据分布在0~2171。例如，在等宽直方图中，将值划分成相等的部分或区间(如(0,2171)，(2171,4342)，…，(8685,10860))。直方图分析算法递归地用于每一部分，将自动地产生多级概念分层，直到到达用户指定的层次水平后结束划分。图2-6显示某数据集数值的分布直方图

3.聚类分析聚类算法可以将数据划分成若干类或组。每一个类形成概念分层的一个节点，而所有的节点在同一概念层。每一个类还可以进一步分成若干子类，形成较低的概念层。类也可以合并在一起，以形成分层结构中较高的概念层。

4.基于熵的离散化熵(Entropy)是一种基于信息的度量，可以用来递归地划分数值属性A的值，形成分层的离散化。这种离散化形成属性的数值概念分层。给定一个数据元组的集合S，基于熵对A离散化的方法如下：

(1)A的每个值都可以认为是一个潜在的区间边界或阈值T。例如，A的值v可以将样本S划分成分别满足条件A<v和A≥v的两个子集，这样就创建了一个二元离散化。

(2)对给定的数据集S,所选择的阈值是这样的值，它使其后划分得到的信息增益最大。信息增益(InformationGain)为(2.6)其中，S1和S2分别对应于S中满足条件A<T和A≥T的一个划分。对于给定的集合，它的熵函数Ent可以根据集合中样本的类分布计算获得。例如，给定m个类，S1的熵为(2.7)其中，pi是类i在S1中的概率，等于S1中类i的样本数除以S1中的样本总数。Ent(S2)的值可以类似地计算。

(3)确定阈值的过程递归地用于所得到的每个划分，直到满足某个终止条件，如Ent(S)-I(S,T)>δ

(2.8)

基于熵的离散化可以压缩数据量。与其他方法不同的是，基于熵的方法利用了类别信息，这使得区间边界定义的分类挖掘结果更加准确。这里介绍的信息增益和熵也用于判定树归纳。

5.通过自然划分分段尽管分箱、直方图、聚类和基于熵的离散化都可以帮助构造数值概念层次树，但是用户希望得到数值区域被划分为相对一致的、易于阅读的、看上去更自然直观的区间。例如，更希望将年薪划分成像($4000，$8000)的区间，而不是像由某种复杂的聚类技术得到的($4263.52，$6471.38］。利用3-4-5规则可以将数值量分解为相对统一、自然的区间。该规则一般将数值范围递归地和逐层地将给定的数据区域划分为3、4或5个等宽区间。该规则如下：

(1)若一个区间在最高有效位上包含3、6、7或9个不同的值，则将该区间划分成3个区间(对于3、6和9，划分成3个等宽区间；而对于7，按2-3-2分组，划分成3个区间)。

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

(3)如果它在最高有效位上包含1、5或10个不同的值，则将区间划分成5个等宽区间。

(4)将该规则递归地用于每个区间，就可以得到数值属性创建的概念分层树。由于在数据集中可能有特别大的正值和负值，最高层分段简单地按最小和最大值划分可能导致与实际结果背离。例如，在考试成绩中，少数人的成绩可能比较接近满分。按照最高分分段可能导致高度倾斜的分层。因此最初的区间分解需要根据包含大多数取值的区间(例如，从5%到95%之间的区域)进行。不在这个区域的特别高和特别低的值划分为单独的区间。2.5.2分类数据的概念分层生成分类数据(CategoricalData)是离散数据。一个分类属性具有有限个(但可能很多)不同值，且值之间无序。例如电话号码、家庭住址和商品类型。分类数据的概念分层主要有以下几种方法。

(1)属性的部分序由用户或专家在模式级显式地说明。通常，分类属性或维的概念分层涉及一组属性。通过在(数据库)模式定义时指定各属性的有序关系，可以很容易地构造概念分层。例如，关系数据库或数据仓库的维location可能包含一组属性：street,city,province_or_state和country。可以在模式级说明一个全序，如street<city<province_or_state<country，来定义层次结构。

(2)通过数据聚合描述层次树。这是人工地定义概念分层结构方法。在大型数据库中，显式的值穷举定义整个概念分层是不现实的。然而，对于一小部分中间层数据，可以进行显式的分组。例如，在模式级说明了province和country形成一个分层后，可以人工地添加某些中间层。

(3)定义一组不说明顺序属性集。用户可以定义一个属性集，形成概念分层，但并不显式说明它们的顺序。系统将自动地产生属性的序，以便构造有意义的概念层次树。没有数据语义的知识，获得一组属性的顺序关系是很困难的。

【例2.6】假定用户对于商场的维location选定了属性集：街道(street)、国家(country)、省(province)和城市(city)，但没有指出属性之间的层次序。

location的概念分层可以按步骤自动地产生。首先，根据每个属性的不同值个数，将属性按降序排列，获得顺序(每个属性的不同值数目在括号中)：country(12)，province(337)，city(2867)，street(589431)。其次，按照排好的次序，自顶向下产生分层，第一个属性在最顶层，最后一个属性在最底层。分层结果如图2-7所示。最后，用户可以考察所产生的分层，如果必要的话，可以对层的顺序进行局部调整，以使其能够反映所期望的属性间的相互联系。此例不需要修改产生的分层。图2-7一个基于不同属性值个数的模型概念分层的自动产生注意，启发知识并非始终正确。例如，在一个数据库中，时间维可能包含20个不同的年，12个不同的月，每星期7个不同的天。然而，这并不意味着时间分层应当是“year<month<days_of_the_week”，days_of_the_week在分层结构的最顶层。

(4)只说明部分属性集。有时用户仅能提供概念层次树所涉及的一部分属性。例如，用户仅能提供地点(location)所有分层的相关属性的部分属性，如说明了街道(street)和城市(city)。这种情况就需要利用数据库模式定义中有关属性间的语义联系，来获得层次树的所有属性。必要时用户可以对所获得的相关属性集进行修改完善。2.6特征选择与提取

2.6.1基本概念

(1)特征形成。表示被识别的对象生成的一组基本特征，它可以是计算出来的(当识别对象是波形或数字图像时)，也可以是用仪表或传感器测量出来的(当识别对象是实物或某种过程时)，这样产生出来的特征叫做原始特征。

(2)特征提取。原始特征的数量可能很大，或者说样本处于一个高维空间中。特征提取是将维数比较多的空间最终压缩到维数比较少的空间，为下一步的特征筛选而服务的过程，它把原特征空间众多特征进行某种组合(通常是线性组合)，从而减少特征，降低维数。所谓特征提取，在广义上就是指一种变换。若Y是测量空间，X是特征空间，则变换A:Y→X就叫做特征提取器。

(3)特征选择。从一组特征中抽取最有效的特征以达到降低特征空间维数的目的，这个过程叫做特征选择。特征提取和特征选择并不是截然分开的。例如，先将最初的特征空间变换到维数较低的空间，在这个空间中再进行特征选择，进一步降低维数。也可以先进行特征选择，去掉那些没有明显分类信息的特征，再进行变换以降低维数。2.6.2特征提取我们的目的是为了能够在低维空间中更好地进行分类，因此变换的有效性最好用分类器的错误概率来衡量。可惜的是，在大多数情况下，错误概率的计算是十分复杂的，因此不得不用另外一些准则来确定特征提取方法。

1.按欧式距离度量的特征提取方法两个特征向量之间的距离是它们相似度的一种很好度量。假使对应同一类别的样本在特征空间中聚集在一起，而不同类别的样本互相离得较远，分类比较容易。因此在给定维数D的特征空间中，我们应采用这样的d个特征，它们使各类尽可能远地互相分开。使用表示第ωi类的第k个样本与第ωj类的第l个样本之间的距离，我们应该选择这样的特征x*，使c个类别各样本之间的平均距离J(x)为最大，即即这里ni表示设计集S中ωi的训练样本数。式中Pi是第i类的先验概率，当这些先验概率未知时，也可以用训练样本数进行估计，即，这里n是设计集的样本总数。

2.按概率距离判别的特征提取方法设原始特征y与二次特征x之间有映射关系：x=WTy，则原空间中一个矩阵A经映射后