项目3数据规约

项目3 数据规约

3.1 实验目的

（1）理解维归约、案例归约与值技术归约(即数据压缩)的区别；

（2）理解数据挖掘过程的预处理阶段中数据归约的优点；

（3）重点掌握利用主成分分析方法对数据进行维归约，理解特征构成和特征选择的基本原则；

（4）重点掌握案例归约技术，学会不同情况进行数据归约处理。

3.2 实验原理

在海量数据上进行复杂的数据分析和挖掘将需要很长的时间，使得这种分析不现实或不

可行。虽然大型数据集有得到更佳挖掘结果的潜力，但并不能保证就一定能获得比小型数据

集好的挖掘结果。假如是多维数据，一个主要问题是，在所有维度中搜寻所有挖掘方案之前，是否可以确定这种方法在已归约数据集的挖掘和发现中发挥得淋漓尽致。更一般得是，从一

个可用特征得子集或案例得到一个通解，并且即使搜索空间扩大是也将会保持不变。数据规

约技术可以用来得到数据集的规约表示，它小得多，但仍接近于保持原数据的完整性。这样，在规约后的数据集上挖掘将更有效，并产生相同（或几乎相同）的分析结果。

数据规约的策略包括：数据立方体聚集、属性子集选择、维度规约、数值规约、离散化

和概念分层产生。这里简单介绍维度归约、案例归约与值技术归约。离散化和概念分层产生将在第5章进行介绍。

3.2.1 维规约

用于数据分析的数据可能包含数以百计的属性，其中大部分属性与挖掘任务不相关，是冗余的。

维规约通过删除不相关的属性（或维）减少数据量。通常使用属性子集选择方法。属性

子集选择的目标是找出最小属性集，使得数据类的概率分布尽可能地接近使用所有属性的原分布。在压缩的属性集上挖掘还有其它的优点。它减少了出现在发现模式上的属性的数目，

使得模式更易于理解。对于属性子集选择，通常使用压缩空间的启发式算法。通常，这些算

法是贪心算法，在搜索属性空间时，总是做看上去是最佳的选择。它们的策略是做局部最优选择，期望由此导致全局最优解。在实践中，这种贪心算法是有效的，并可以逼近最优解。 “最好的”（或“最差的”）属性使用统计意义的测试来选择。这种测试假定属性是相互

独立的。也可以使用一些其它属性估计度量，如使用信息增益度量建立分类判定树。 属性子集选择的基本启发式方法包括以下技术：

（１）逐步向前选择：该过程由空属性集开始，选择原属性集中最好的属性，并将它添

加到该集合中。在其后的每一次迭代，将原属性集剩下的属性中最好的属性添加到该集合中。 （２）逐步向后删除：该过程由整个属性集开始，在每一步，删除掉尚在属性集中的最

坏属性。

（３）向前选择和向后删除的结合：向前选择和向后删除方法可以结合在一起，每一步选择一个最好的属性，并在剩余属性中删除一个最坏的属性。

方法（1）到（3）的结束条件可以有多种。过程可以使用一个阀值来确定是否停止属性

选择过程。 （4）判定树归纳：判定树算法最初是用于分类的。该方法构造一个类似于流程图的结

构，其每个内部（非树叶）节点表示一个属性上的测试，每个分支对应于测试的一个输出；

每个外部（树叶）节点表示一个判定类。在每个节点，算法选择“最好”的属性，将数据分成类。当它用于属性子集选择时，树由给定的数据构造。不出现在树中的所有属性假定是不

相关的。出现在树中的属性形成规约后的属性子集。

维度规约使用数据编码或变换，以便得到原数据的规约或“压缩”表示。有一些很好的压缩算法，尽管它们通常是无损的，但是只允许有限的数据操作。这里介绍两种流行、有效

的有损的维度规约方法：小波变换和主成分分析。

离散小波变换（DWT）是一种线性信号处理技术，当用于数据向量X时，将它变换成小波系数向量X’。当这种技术用于数据规约时，每个元组看作一个n维数据向量，即

X=12(,,,)nxxx，描述n个属性在元组上的n个测量值。小波变换后的数据可以截短，仅

存放一小部分最强的小波系数，就能保留近似的压缩数据。给定一组系数，使用所用的DWT的逆，可以构造出原数据的近似。该技术也能用于消除噪声，而不会光滑掉数据的主要特征，

使得它们也能有效地用于数据清理。小波变换用于多维数据，可以按以下方法做：首先将变

换用于第一个维，然后第二个，如此下去。计算复杂性关于数据立方体中单元的个数是线性的。

主成分分析（PCA）搜索k个最能代表数据的n维正交向量，其中nk。这样，原来

的数据投影到一个小得多的空间，导致维度规约。不象属性子集选择通过保留属性集的一个子集来减少属性集的大小，PCA通过创建一个替换的、更小的变量集“组合”属性的基本

要素。原数据可以投影到该较小的集合中。PCA常常揭示先前未曾察觉的联系，并因此允

许解释不寻常的结果。PCA计算开销地，可以用于有序和无序的属性，并且可以处理稀疏和倾斜数据。主成分可以作为多元回归和聚类分析的输入。与小波变换相比，PCA能够更

好地处理稀疏数据，而小波变换更适合于高维数据。 3.2.2 案例规约

抽样可以作为一种数据规约技术使用，因为它允许用数据的小得多的随机样本来表示大型数据集。常用的抽样方法有：无放回简单随机抽样、有放回简单随机抽样、聚类抽样和分

层抽样。采用抽样进行数据规约的优点是，得到样本的开销正比于样本集的大小，而不是数

据集的大小。因此，抽样的复杂度子线性与数据的大小。其他数据规约技术都需要完全扫描整个数据集。

用于数据规约时，抽样最常用于估计聚集查询的回答。在指定的误差范围内，可以确定

估计一个给定的函数所需样本的大小。对于规约数据集的逐步求精，抽样是一种自然选择。通过简单地增加样本大小，这样的集合可以进一步求精。

3.2.3 值技术规约（是不是就是数值规约，回归、直方图、聚类、抽样）

在值技术规约(即数据压缩)时，应用数据编码或变换，以便得到原数据的规约或“压缩”

表示。如果原数据可以由压缩数据重新构造而不丢失任何信息，则所使用的数据压缩技术是无损的。如果只能重新构造原数据的近似表示，则该数据压缩技术是有损的。如小波变换和

主成分分析就是两种流行而有效的数据压缩方法。

这里，我们直观地介绍主成分分析(PCA，又称Karhunen-Loeve或K-L)方法。假定待压缩的数据由N个元组或数据向量组成，取自k个维。PCA搜索c个最能代表数据的k-维正

交向量，这里ck。这样，原来的数据投影到一个较小的空间，导致数据压缩。PCA可以

作为一种维规约形式使用。然而，不像属性子集选择通过保留原属性集的一个子集来减少属性集的大小，PCA通过创建一个替换的、较小的变量集来“组合”属性的精华。原数据可

以投影到该较小的集合中。

基本过程如下： 1）对输入数据规范化，使得每个属性都落入相同的区间。此步确保具有较大定义域的属性

不会主宰具有较小定义域的属性。

2）计算c个规范化规范化正交向量，作为规范化输入数据的基。这些向量是单位向量，每

一个都垂直于另一个。这些向量被称为主要成分。输入数据时主要成分的线性组合。

3）对主要成分按“意义”或强度降序排列。主要成分基本上充当数据的一组新坐标轴，提

供重要的方差信息。对轴进行排序，使得第一个轴显示的数据立方体的方差最大，第二个显示的方差次之，如此下去。

4）既然主要成分根据“意义”降序排列，就可以通过去掉较弱的成分（即方差较小的那些）

来压缩数据。使用最强的主要成分，应当可能重构原数据的很好的近似值。 PCA计算开销低，可以用于有序和无序的属性，并且可以处理稀疏数据和倾斜数据。与小波变换相比，PCA能较好地处理稀疏数据，而小波变换更适合处理高维数据。

可以以200字左右的一小段来描述当前应用研究的困惑。

3.3 实验数据

本次实验将对数据规约的维归约、案例归约和值技术归约等方法进行介绍，利用

SAS/EM模块掌握数据规约技术。

本次实验选用的数据集为“2007 UC San Diego Data Mining Contest”的“Sale Price

Prediction数据”，来源于http://mill.ucsd.edu/index.php?page=Main。（数据已给出，其文件为

EXCEL文件，名为MYFILE4；只采用训练数据名RegressionTrainData.txt，相应的目标变量

“Sale Price”值数据集是RegressionTrainLabels.txt）。关于数据格式问题：原始数据由数字

和文本信息组成，为了更方便使用，将文本信息进行了编码，具体形式见“数据编码方

式.doc”。该数据包含了城市编码、地点编码等38个属性，变量情况如表4.1所示。因数据属性繁杂、元组甚多，将进行数据归约对其进行简化。实验的分析任务是根据该数据给出的

位置信息、住处大小、房屋抵押状态等，预测2005-2006年的房屋售价。

表4.1 原始数据变量汇总表 变量名称 变量含义 变量类型 Site_City_State 城市编码 code Site_Zip 地点编码 code Subdivision_Name 进一步细分的名称 code Zoned_County_Code 区域国家代码 code Flag 国家 code Amount_1 金额1 number Amount_2 金额2 number Tax_Year_Delinquent 违法日期 date Year_Built 建造日期 date Effective_Year_Built 有效的建造日期 date Building_Shape_Code 建筑物形状 code Lot_Size 住处大小 number Finish_Square_Feet_Total 完成的建筑面积 number Finished_Audited_Square_Feet_Total 稽查校正的面积 code Garage_Carport 车库 code Number_Of_Baths_number 浴室数目 number Number_Of_Bedrooms_number 卧室数目 number Number_Of_Units_number 单元数目 number Pool_Code 游泳池 code View_Code 风景 code Document_Date_1 公文时间 date Arms_Length_Transaction_Flag 交易时间长短 code Full_or_Partial_Code 完整或部分编码 code Multiple_APN_Keyed_Flag 复合接入点 code Loan_Amount_1 借贷1数量 number Loan_Amount_2 借贷2数量 number Loan_Amount_3 借贷3数量 number Loan_Type_1 借贷1类型 code Loan_Type_2 借贷2类型 code Loan_Type_3 借贷3类型 code Interest_Rate_Type_1 借贷1利率 code Interest_Rate_Type_2 借贷2利率 code Interest_Rate_Type_3 借贷3利率 code X_Coordinate X坐标 number Y_Coordinate Y坐标 number Census_Tract 人口普查情况 code Geo_Quality_Code 地质情况 code Sale_Price 销售价格 number