关于数据抽样的简单分析

    这段时间项目中涉及到多维数据抽样的方法，对于抽样算法以前一直也没怎么关注。但是最近从测试的效果来看，整个抽样效果不是很理想，特别是抽样数据的代表性方面我们希望具有均匀的效果。

    最近在网上发现不错的文章就贴上来了

2.5数据规约

Ø 数据归约技术可以用来得到数据集的归约表示，它小得多，但仍接近保持原数据的完整性。这样，对归约后的数据集挖掘将更有效，并产生相同（或几乎相同）的分析结果。
Ø 数据归约的策略如下：
n （1）数据立方体聚集：聚集操作用于数据立方体结构中的数据。
n （2）属性子集选择：可以检测并删除不相关、弱相关或冗余的属性或维。
n （3）维度归约：使用编码机制减小数据集的规模。
n （4）数值归约：用替代的、较小的数据表示替换或估计数据，如参数模型（只需要存放模型参数，而不是实际数据）或非参数方法，如聚类、抽样和使用直方图。
n （5）离散化和概念分层产生：属性的原始数据值用区间值或较高层的概念替换。数据离散化是一种数据归约形式，对于概念分层的自动产生是有用的。离散化和概念分层产生是数据挖掘强有力的工具，允许挖掘多个抽象层的数据。

2.5.1 数据立方体聚集

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

2.5.2 属性子集选择

Ø 遗漏相关属性或留下不相关属性都是有害的，会导致所用的挖掘算法无所适从。这可能导致发现质量很差的模式。此外，不相关或冗余的属性增加可能会减慢挖掘进程。
Ø 属性子集选择通过删除不相关或冗余的属性（或维）减小数据集。属性子集选择的目标是找出最小属性集，使得数据类的概率分布尽可能地接近使用所有属性得到的原分布。对减小的属性集挖掘还有其他优点。它减少了出现在发现模式的属性数目，使得模式更易于理解。
Ø “如何找出原属性的一个‘好的’子集？”对于n个属性，有2^n个可能的子集。穷举搜索找出属性的最佳子集可能是不现实的，特别是当n和数据类的数目增加时。因此，对于属性子集选择，通常使用压缩搜索空间的启发式算法。通常，这些方法是贪心算法，在搜索属性空间时，总是做看上去当时最佳的选择。策略是做局部最优选择，期望由此导致全局最优解。在实践中，这种贪心方法是有效的，并可以逼近最优解。
Ø “最好的”（和“最差的”）属性通常使用统计显著性检验来确定。这种检验假定属性是相互独立的。也可以使用其他属性评估度量，如建立分类决策树使用信息增益度量。
Ø 属性子集选择的基本启发式方法包括以下技术，其中一些图示在图2-15中。

Ø 逐步向前选择：该过程由空属性集作为归约集开始，确定原属性集中最好的属性，并将它添加到归约集中。在其后的每一次迭代步，将剩下的原属性集中最好的属性添加到该集合中。
Ø 逐步向后删除：该过程由整个属性集开始。在每一步，删除尚在属性集中最差的属性。
Ø 向前选择和向后删除的结合：可以将逐步向前选择和向后删除方法结合在一起，每一步选择一个最好的属性，并在剩余属性中删除一个最差的属性。
Ø 决策树归纳：决策树算法，如ID3、C4.5和CART最初是用于分类的。决策树归纳构造一个类似于流程图的结构，其中每个内部（非树叶）节点表示一个属性的测试，每个分枝对应于测试的一个输出；每个外部（树叶）节点表示一个类预测。在每个节点，算法选择“最好”的属性，将数据划分成类。
n 当决策树归纳用于属性子集选择时，由给定的数据构造决策树。不出现在树中的所有属性假定是不相关的。出现在树中的属性形成归约后的属性子集。
n 方法的结束标准可以不同。该过程可以使用一个度量阈值来决定何时停止属性选择过程。

2.5.3 维度规约

Ø 维度归约使用数据编码或变换，以便得到原数据的归约或“压缩”表示。如果原数据可以由压缩数据重新构造而不丢失任何信息，则该数据归约是无损的。如果我们只能重新构造原数据的近似表示，则该数据归约是有损的。有一些很好的串压缩算法。尽管它们通常是无损的，但是只允许有限的数据操作。本节，我们介绍另外两种流行、有效的有损的维归约方法：小波变换和主成分分析。
Ø 小波变换
n 离散小波变换（DWT）是一种线性信号处理技术，当用于数据向量X时，将它变换成数值上不同的小波系数向量X'。两个向量具有相同的长度。当这种技术用于数据归约时，每个元组看作一个n维数据向量，即X = (x1, x2, …, xn），描述n个数据库属性在元组上的n个测量值。
n DWT与离散傅里叶变换（DFT）有密切关系，DFT是一种涉及正弦和余弦的信号处理技术。然而一般地说，DWT是一种更好的有损压缩。也就是说，对于给定的数据向量，如果DWT和DFT保留相同数目的系数，DWT将提供原数据的更准确的近似。因此，对于等价的近似，DWT比DFT需要的空间小。不像DFT，小波空间局部性相当好，有助于保留局部细节。
n 只有一种DFT，但有若干族DWT。图2-16显示了一些小波族。流行的小波变换包括Haar-2, Daubechies-4和Daubechies-6变换。应用离散小波变换的一般过程使用一种分层金字塔算法（pyramid algorithm），它在每次迭代将数据减半，导致很快的计算速度。该方法如下：



u （1）输入数据向量的长度L必须是2的整数幂。必要时（L≥n），通过在数据向量后添加0，这一条件可以满足。
u （2）每个变换涉及应用两个函数。第一个使用某种数据光滑，如求和或加权平均。第二个进行加权差分，产生数据的细节特征。
u （3）两个函数作用于X中的数据点对，即用于所有的测量对（x2i, x2i+1）。这导致两个长度为L/2的数据集。一般，它们分别代表输入数据的光滑后的版本或低频版本和它的高频内容。
u （4）两个函数递归地作用于前面循环得到的数据集，直到得到的数据集长度为2。
u （5）由以上迭代得到的数据集中选择值，指定其为数据变换的小波系数。

n 等价地，可以将矩阵乘法用于输入数据，以得到小波系数。所用的矩阵依赖于给定的DWT。矩阵必须是标准正交的，即列是单位向量并相互正交，使得矩阵的逆是它的转置。尽管受篇幅限制，这里我们不再讨论，但这种性质允许由光滑和光滑-差数据集重构数据。通过将矩阵因子分解成几个稀疏矩阵，对于长度为n的输入向量，“快速DWT”算法的复杂度为O (n)。
n 小波变换可以用于多维数据，如数据立方体。可以按以下方法做：首先将变换用于第一个维，然后第二个，如此下去。计算复杂性关于立方体中单元的个数是线性的。对于稀疏或倾斜数据和具有有序属性的数据，小波变换给出很好的结果。据报道，小波变换的有损压缩比当前的商业标准JPEG压缩好。小波变换有许多实际应用，包括指纹图像压缩、计算机视觉、时间序列数据分析和数据清理。

Ø 主成分分析
n 假定待归约的数据由n个属性或维描述的元组或数据向量组成。主成分分析（principal components analysis）或PCA（又称Karhunen-Loeve或K-L方法）搜索k个最能代表数据的n维正交向量，其中k≤n。这样，原来的数据投影到一个小得多的空间，导致维度归约。不像属性子集选择通过保留原属性集的一个子集来减少属性集的大小，PCA通过创建一个替换的、更小的变量集“组合”属性的基本要素。原数据可以投影到该较小的集合中。PCA常常揭示先前未曾察觉的联系，并因此允许解释不寻常的结果。
n 基本过程如下：
u （1）对输入数据规范化，使得每个属性都落入相同的区间。此步有助于确保具有较大定义域的属性不会支配具有较小定义域的属性。
u （2）PCA计算k个标准正交向量，作为规范化输入数据的基。这些是单位向量，每一个方向都垂直于另一个。这些向量称为主成分。输入数据是主成分的线性组合。
u （3）对主成分按“重要性”或强度降序排列。主成分基本上充当数据的新坐标轴，提供关于方差的重要信息。也就是说，对坐标轴进行排序，使得第一个坐标轴显示数据的最大方差，第二个显示次大方差，如此下去。例如，图2-17显示原来映射到轴X1和X2的给定数据集的前两个主成分Y1和Y2。这一信息帮助识别数据中的分组或模式。
u （4）既然主成分根据“重要性”降序排列，就可以通过去掉较弱的成分（即方差较小）来归约数据的规模。使用最强的主成分，应当能够重构原数据的很好的近似。

Ø PCA计算开销低，可以用于有序和无序的属性，并且可以处理稀疏和倾斜数据。多于2维的多维数据可以通过将问题归约为2维问题来处理。主成分可以用作多元回归和聚类分析的输入。与小波变换相比，PCA能够更好地处理稀疏数据，而小波变换更适合高维数据。

2.5.4 数值规约

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

Ø 回归和对数线性模型
回归和对数线性模型可以用来近似给定的数据。在（简单）线性回归中，对数据建模，使之拟合到一条直线。例如，可以用以下公式，将随机变量y（称作响应变量）建模为另一随机变量x（称为预测变量）的线性函数
y = wx + b
其中，假定y的方差是常量。在数据挖掘中，x和y是数值数据库属性。系数w和b（称作回归系数）分别为直线的斜率和Y轴截距。系数可以用最小二乘方法求解，它最小化分离数据的实际直线与直线估计之间的误差。多元线性回归是（简单）线性回归的扩充，允许响应变量y建模为两个或多个预测变量的线性函数。
对数线性模型（log-linear model）近似离散的多维概率分布。给定n维（例如用n个属性描述）元组的集合，可以把每个元组看作n维空间的点。可以使用对数线性模型基于维组合的一个较小子集，估计离散化的属性集的多维空间中每个点的概率。这使得高维数据空间可以由较低维空间构造。因此，对数线性模型也可以用于维归约（由于低维空间的点通常比原来的数据点占据较少的空间）和数据光滑（因为与较高维空间的估计相比，较低维空间的聚集估计较少受抽样方差的影响）。
回归和对数线性模型都可以用于稀疏数据，尽管它们的应用可能是受限制的。虽然两种方法都可以处理倾斜数据，但是回归可望更好。当用于高维数据时，回归可能是计算密集的，而对数线性模型表现出很好的可伸缩性，可以扩展到10维左右。回归和对数线性模型将在6.11节进一步讨论。

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

“如何确定桶和属性值的划分？”有一些划分规则，包括如下：
n 等宽：在等宽直方图中，每个桶的宽度区间是一致的
n 等频（或等深）：在等频直方图中，创建桶，使得每个桶的频率粗略地为常数（即每个桶大致包含相同个数的邻近数据样本）。
n V最优：给定桶的个数，如果我们考虑所有可能的直方图，则V最优直方图是具有最小方差的直方图。直方图的方差是每个桶代表的原来值的加权和，其中权等于桶中值的个数。
n MaxDiff: 在MaxDiff直方图中，考虑每对相邻值之间的差。桶的边界是具有b－1个最大差的对，其中b是用户指定的桶数。

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

Ø 聚类
聚类技术将数据元组视为对象。它将对象划分为群或簇，使一个簇中的对象相互“相似”，而与其他簇中的对象“相异”。通常，相似性基于距离函数，用对象在空间中的“接近”程度定义。簇的“质量”可以用直径表示，直径是簇中任意两个对象的最大距离。质心距离是簇质量的另一种度量，定义为由簇质心（表示“平均对象”，或簇空间中的平均点）到每个簇对象的平均距离。
在数据库系统中，多维索引树主要用于对数据的快速访问。它也能用于分层数据的归约，提供数据的多维聚类。这可以用于提供查询的近似回答。对于给定的数据对象集，索引树递归地划分多维空间，其树根节点代表整个空间。通常，这种树是平衡的，由内部节点和树叶节点组成。每个父节点包含关键字和指向子女节点的指针，子女节点一起表示父节点代表的空间。每个树叶节点包含指向它所代表的数据元组的指针（或实际元组）。
这样，索引树可以在不同的分辨率或抽象层存放聚集和细节数据。它提供了数据集的分层聚类，其中每个簇有一个标记，存放该簇包含的数据。如果我们把父节点的每个子女看作一个桶，则索引树可以看作一个分层的直方图。例如，考虑图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树、四叉树和它们的变形。它们都非常适合处理稀疏数据和倾斜数据。


Ø 抽样
抽样可以作为一种数据归约技术使用，因为它允许用数据的小得多的随机样本（子集）表示大型数据集。假定大型数据集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可能非常小。对于归约数据集的逐步求精，抽样是一种自然选择。通过简单地增加样本大小，这样的集合可以进一步求精。