2.5 数据归约

2.5 数据归约

假定你由AllElectronics数据仓库选择了数据用于分析。该数据集将非常大！对海量数据进行复杂的数据分析和挖掘将需要很长时间，使得这种分析不现实或不可行。

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

（1）数据立方体聚集：聚集操作用于数据立方体结构中的数据。

（2）属性子集选择：可以检测并删除不相关、弱相关或冗余的属性或维。

（3）维度归约：使用编码机制减小数据集的规模。

（4）数值归约：用替代的、较小的数据表示替换或估计数据，如参数模型（只需要存放模型参数，而不是实际数据）或非参数方法，如聚类、抽样和使用直方图。

（5）离散化和概念分层产生：属性的原始数据值用区间值或较高层的概念替换。数据离散化是一种数据归约形式，对于概念分层的自动产生是有用的。离散化和概念分层产生是数据挖掘强有力的工具，允许挖掘多个抽象层的数据。我们将离散化和概念分层的自动产生推迟到2.6节，用整整一节讨论该问题。

策略1～4在本节的剩余部分讨论。用于数据归约的计算时间不应当超过或“抵消”对归约数据挖掘节省的时间。

2.5.1 数据立方体聚集

想像你已经为分析收集了数据。这些数据由AllElectronics 2002~2004年每季度的销售数据组成。然而，你感兴趣的是年销售（每年的总和），而不是每季度的总和。可以对这种数据聚集，使得结果数据汇总每年的总销售，而不是每季度的总销售。该聚集如图2-13所示。结果数据集小得多，并不丢失分析任务所需的信息。

图2-13 AllElectronics的给定分店2002～2004年的销售数据。在左部，销售数据按季度显示。在右部，数据聚集以提供年销售额

数据立方体在第3章介绍数据仓库时详细讨论。这里，我们简略介绍一些概念。数据立方体存储多维聚集信息。例如，图2-14显示了一个数据立方体，用于AllElectronics所有分店每类商品年销售多维分析。每个单元存放一个聚集值，对应于多维空间的一个数据点。（为清晰起见，只显示了某些单元的值。）每个属性可能存在概念分层，允许在多个抽象层进行数据分析。例如，branch的分层使得分店可以按地址聚集成地区。数据立方体提供对预计算的汇总数据进行快速访问，因此，适合联机数据分析处理和数据挖掘。

图2-14 AllElectronics的销售数据立方体

在最低抽象层创建的立方体称为基本方体（base cuboid）。基本方体应当对应于感兴趣的个体实体，如sales或customer。换言之，最低层应当是对于分析可用的或有用的。最高层抽象的立方体称为顶点方体（apex cuboid）。对于图2-14的销售数据，顶点方体将给出一个汇总74 值—所有商品类型、所有分店三年的总销售额。对不同抽象层创建的数据立方体称为方体（cuboid），因此数据立方体可以看作方体的格（lattice of cuboids）。每个较高层抽象将进一步减少结果数据的规模。当回答数据挖掘查询时，应当使用与给定任务相关的最小可用方体。该问题将在第3章讨论。

2.5.2 属性子集选择

用于分析的数据集可能包含数以百计的属性，其中大部分属性与挖掘任务不相关或冗余。例如，如果分析任务是按顾客听到广告后是否愿意在AllElectronics买流行的新款CD，将顾客分类，与属性age或music_taste不同，诸如顾客的电话号码等属性多半是不相关的。尽管领域专家可以挑选出有用的属性，但这可能是一项困难而费时的任务，特别是当数据的行为不清楚的时候更是如此（因此，需要分析!）。遗漏相关属性或留下不相关属性都是有害的，会导

致所用的挖掘算法无所适从。这可能导致发现质量很差的模式。此外，不相关或冗余的属性增加可能会减慢挖掘进程。

属性子集选择

通过删除不相关或冗余的属性（或维）减小数据集。属性子集选择的目标是找出最小属性集，使得数据类的概率分布尽可能地接近使用所有属性得到的原分布。对减小的属性集挖掘还有其他优点。它减少了出现在发现模式的属性数目，使得模式更易于理解。

“如何找出原属性的一个‘好的’子集？”对于n个属性，有2n个可能的子集。穷举搜索找出属性的最佳子集可能是不现实的，特别是当n和数据类的数目增加时。因此，对于属性子集选择，通常使用压缩搜索空间的启发式算法。通常，这些方法是贪心算法，在搜索属性空间时，总是做看上去当时最佳的选择。策略是做局部最优选择，期望由此导致全局最优解。在实践中，这种贪心方法是有效的，并可以逼近最优解。

“最好的”（和“最差的”）属性通常使用统计显著性检验来确定。这种检验假定属性是相互独立的。也可以使用其他属性评估度量，如建立分类决策树使用信息增益度量。

属性子集选择的基本启发式方法包括以下技术，其中一些图示在图2-15中。

在机器学习，属性子集选择称作特征子集选择。

信息增益度量在第6章详细介绍。在2.6.1节中结合属性离散作了简要介绍。

图2-15 属性子集选择的贪心（启发式）方法

（1）逐步向前选择：该过程由空属性集作为归约集开始，确定原属性集中最好的属性，并将它添加到归约集中。在其后的每一次迭代步，将剩下的原属性集中最好的属性添加到该集合中。

（2）逐步向后删除：该过程由整个属性集开始。在每一步，删除尚在属性集中最差的属性。

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

（4）决策树归纳：决策树算法，如ID3、C4.5和CART最初是用于分类的。决策树归纳构造一个类似于流程图的结构，其中每个内部（非树叶）节点表示一个属性的测试，每个分枝对应于测试的一个输出；每个外部（树叶）节点表示一个类预测。在每个节点，算法选择“最好”的属性，将数据划分成类。

当决策树归纳用于属性子集选择时，由给定的数据构造决策树。不出现在树中的所有属性假定是不相关的。出现在树中的属性形成归约后的属性子集。方法的结束标准可以不同。该过程可以使用一个度量阈值来决定何时停止属性选择过程。