2.5.4 数值归约

2.5.4 数值归约

“我们能通过选择替代的、‘较小的’数据表示形式来减少数据量吗？”数值归约技术确实可以用于这一目的。这些技术可以是参数的，也可以是非参数的。参数方法使用一个模型估计数据，只需要存放数据参数，而不是实际数据。（离群点也可能存放。）对数线性模型是一个例子，它估计离散的多维概率分布。存放数据归约表示的非参数方法包括直方图、聚类和抽样。

我们来看看上面提到的每种数值归约技术。

1. 回归和对数线性模型

回归和对数线性模型可以用来近似给定的数据。在（简单）线性回归中，对数据建模，使之拟合到一条直线。例如，可以用以下公式，将随机变量y（称作响应变量）建模为另一随机变量x（称为预测变量）的线性函数y = wx + b （2-14）

其中，假定y的方差是常量。在数据挖掘中，x和y是数值数据库属性。系数w和b（称作回归系数）分别为直线的斜率和Y轴截距。系数可以用最小二乘方法求解，它最小化分离数据的实际直线与直线估计之间的误差。多元线性回归是（简单）线性回归的扩充，允许响应变量y建模为两个或多个预测变量的线性函数。

对数线性模型（log-linear model）近似离散的多维概率分布。给定n维（例如用n个属性描述）元组的集合，可以把每个元组看作n维空间的点。可以使用对数线性模型基于维组合的一个较小子集，估计离散化的属性集的多维空间中每个点的概率。这使得高维数据空间可以由较低维空间构造。因此，对数线性模型也可以用于维归约（由于低维空间的点通常比原来的数据点占据较少的空间）和数据光滑（因为与较高维空间的估计相比，较低维空间的聚集

估计较少受抽样方差的影响）。

回归和对数线性模型都可以用于稀疏数据，尽管它们的应用可能是受限制的。虽然两种方法都可以处理倾斜数据，但是回归可望更好。当用于高维数据时，回归可能是计算密集的，而对数线性模型表现出很好的可伸缩性，可以扩展到10维左右。回归和对数线性模型将在6.11节进一步讨论。

2. 直方图

直方图使用分箱来近似数据分布，是一种流行的数据归约形式。直方图曾在2.2.3节介绍过。属性A的直方图将A的数据分布划分为不相交的子集或桶。如果每个桶只代表单个属性值/ 频率对，则该桶称为单桶。通常，桶表示给定属性的一个连续区间。

例2-5 直方图。下面的数据是AllElectronics通常销售的商品的单价表（按美元取整）。

已对数据进行了排序：1, 1, 5, 5, 5,5, 5, 8, 8, 10, 10, 10, 10, 12, 14, 14, 14, 15, 15, 15, 15, 15, 15, 18, 18, 18, 18, 18, 18, 18, 18, 20, 20, 20, 20, 20, 20, 20, 21, 21, 21, 21, 25, 25, 25, 25, 25, 28, 28, 30, 30, 30。

图2-18使用单桶显示了这些数据的直方图。为进一步压缩数据，通常让每个桶代表给定属性的一个连续值域。在图2-19中每个桶代表price的一个不同的10美元区间。

图2-19 price的等宽直方图，值聚集使得每个桶都有一致的宽度为10美元

“如何确定桶和属性值的划分？”有一些划分规则，包括如下：

. 等宽：在等宽直方图中，每个桶的宽度区间是一致的（如图2-19中每个桶的宽度为10 美元）。

. 等频（或等深）：在等频直方图中，创建桶，使得每个桶的频率粗略地为常数（即每个桶大致包含相同个数的邻近数据样本）。

. V最优：给定桶的个数，如果我们考虑所有可能的直方图，则V最优直方图是具有最小方差的直方图。直方图的方差是每个桶代表的原来值的加权和，其中权等于桶中值的个数。

. MaxDiff: 在MaxDiff直方图中，考虑每对相邻值之间的差。桶的边界是具有β－1个最大差的对，其中β是用户指定的桶数。

V最优和MaxDiff直方图看来是最准确和最实用的。对于近似稀疏和稠密数据，以及高倾斜和均匀的数据，直方图是高度有效的。上面介绍的单属性直方图可以推广到多属性。多维直方图可以表现属性间的依赖。业已发现，这种直方图能够有效地近似多达5个属性的数据。对于高维的多维直方图的有效性尚需进一步研究。对于存放具有高频率的离群点，单桶是有用的。

3. 聚类

聚类技术将数据元组视为对象。它将对象划分为群或簇，使一个簇中的对象相互“相似”， 而与其他簇中的对象“相异”。通常，相似性基于距离函数，用对象在空间中的“接近”程度定义。簇的“质量”可以用直径表示，直径是簇中任意两个对象的最大距离。质心距离是簇质量的另一种度量，定义为由簇质心（表示“平均对象”，或簇空间中的平均点）到每个簇对象的平均距离。2.3.2节的图2-12显示关于在城市中位置的顾客数据2-D图，其中每个簇的质心用“+”显示，三个数据簇是可见的。

在数据归约中，用数据的簇表示替换实际数据。该技术的有效性依赖于数据的性质。如果数据能够组织成不同的簇，该技术有效得多。在数据库系统中，多维索引树主要用于对数据的快速访问。它也能用于分层数据的归约，

提供数据的多维聚类。这可以用于提供查询的近似回答。对于给定的数据对象集，索引树递归地划分多维空间，其树根节点代表整个空间。通常，这种树是平衡的，由内部节点和树叶节点组成。每个父节点包含关键字和指向子女节点的指针，子女节点一起表示父节点代表的空间。每个树叶节点包含指向它所代表的数据元组的指针（或实际元组）。

这样，索引树可以在不同的分辨率或抽象层存放聚集和细节数据。它提供了数据集的分层聚类，其中每个簇有一个标记，存放该簇包含的数据。如果我们把父节点的每个子女看作一个桶，则索引树可以看作一个分层的直方图。例如，考虑图2-20所示B+树的根，具有指向数据键986，3396，5411，8392和9544的指针。假设该树包含10 000个元组，其键值由1～9999。树中的数据可以用6个桶的等频直方图近似，其键值分别从1～985，986～3395，3396～5410， 5411～8391，8392～9543，9544～9999。每个桶大约包含10 000/6个数据项。类似地，每个桶进一步分成更小的桶，允许在更细的层次聚集数据。作为一种数据归约形式使用多维索引树依赖于每个维上属性值的次序。二维或多维索引树包括R树、四叉树和它们的变形。它们都非常适合处理稀疏数据和倾斜数据。

 

图2-20 给定数据集的B+树的根

有许多定义簇和簇质量的度量。聚类方法将在第7章进一步讨论。

4. 抽样

抽样可以作为一种数据归约技术使用，因为它允许用数据的小得多的随机样本（子集）表示大型数据集。假定大型数据集D包含N个元组。我们看看可以用于数据归约的、最常用的对D的抽样方法，如图2-21所示。

. s个样本无放回简单随机抽样（SRSWOR）：从D的N个元组中抽取s个样本（s < N），其中D中任意元组被抽取的概率均为1/N，即所有元组的抽取是等可能的。

. s个样本有放回简单随机抽样（SRSWR）：该方法类似于SRSWOR，不同在于每次一个元组从D中抽取后，记录它，然后放回原处。也就是说，一个元组抽取后，放回D，以便它可以再次被抽取。

. 聚类抽样：如果D中的元组分组放入M个互不相交的“簇”，则可以得到s个簇的简单随机抽样（SRS），其中s < M。例如，数据库中元组通常一次检索一页，这样每页就可以视为一个簇。例如，可以将SRSWOR用于页，得到元组的簇样本，由此得到数据的归约表示。也可以利用其他携带更丰富语义信息的聚类标准。例如，在空间数据库，可以基于不同区域位置上的邻近程度地理地定义簇。

. 分层抽样：如果D划分成互不相交的部分，称作层，则通过对每一层的SRS就可以得到D的分层样本。特别是当数据倾斜时，这可以帮助确保样本的代表性。例如，可以得到关于顾客数据的一个分层样本，其中分层对顾客的每个年龄组创建。这样，具有顾客最少数目的年龄组肯定能够被表示。采用抽样进行数据归约的优点是，得到样本的花费正比于样本集的大小s，而不是数据集的大小N。因此，抽样的复杂度子线性（sublinear）于数据的大小。其他数据归约技术至少需要完全扫描D。对于固定的样本大小，抽样的复杂度仅随数据的维数n线性地增加；而其他技

术，如使用直方图，复杂度随n指数增长。

用于数据归约时，抽样最常用来估计聚集查询的回答。在指定的误差范围内，可以确定（使用中心极限定理）估计一个给定的函数所需的样本大小。样本的大小s相对于N可能非常小。

对于归约数据集的逐步求精，抽样是一种自然选择。通过简单地增加样本大小，这样的集合可以进一步求精。

 

图2-21 抽样可以用于数据归约