数据挖掘1-第三章归约

第三章数据归约本章目标明确基于特征、案例维归约与技术归约的区别。解释数据挖掘过程的预处理阶段中进行数据归约的优点应用相应的统计方法，理解特征选择和特征构成的基本原则。理解特征等级主成分分析方法。区别基于增量和平均样本的案例中的技术。对数据描述，特征的挑选、归约或转换可能是决定挖掘方案质量的最重要的问题。除了影响到数据挖掘算法的属性，它也能决定问题量否可解，或所得到的挖掘模型有多强大。为什么要数据归约：

1.一旦特征数量达到数百，而只有上百条样本用于分析时，对挖掘是相对不够的。

2.由高维度引起的数据超负，使一些挖掘算法不适用。3.1大型数据集的维度预处理数据集的三个主要维度：列（特征），行（案例或样本）和特征的值。它们以平面文件的形式出现。数据归约过程３个基本操作：删除列、删除行、减少列中值的数量（平整特征）。例如：用分箱方法减少值的数量，用特征合并代替原来特征（身体素质指标代替人的身高和体重特征）数据归约的约定是不要降低结果的质量。在数据归约操作时的目标过程：1.计算时间：较简单的数据，也即经过数据归约后的结果，可减少挖掘所消耗的时间。2.预测／描述精度：多数挖掘模型的主要度量标准，它估量了数据归纳和慨括为模型的好坏。3.数据挖掘模型的描述：简单的描述通常来自数据归约，意味着模型能得到更好的理解。理想的情况是维归约后既能减少时间，又能同时提高精度和简化描述。数据归约算法的特征：1.可测性：已归约的数据集可精确确定近似结果的质量。2.可识别性：挖掘前能执行归约算法时能确定近似结果的质量。3.单调性：算法是可迭代的，结果的质量是时间和输入数据质量的一个非递减的函数。4.一致性：结果的质量与时间和输入数据质量有关。5.收益递增：方案在迭代早期可获得大的改进，但随时间递减。6.中断性：算法可在任何时刻停止并给出答案。7.优先权：算法可以暂停并以最小的开销新开始。3.2特征归约在进行数据归约时不但要处理干扰数据和污染数据，而且要处理不相关、相关、冗余数据。为了提高效率，通常单独处理相关特征，只选择与挖掘应用相关的数据，以达到用最小的测量和处理量获得最好的性能。特征归约的目标：更少的数据，以便挖掘算法能更快的学习。更高的挖掘处理精度，以便更好地从数据中归纳出模型。简单的挖掘处理结果，以便理解和使用起来更加容易。更少的特征，以便在下一次数据收集中，通过去除冗余或不相关特征做到节俭。特征归约的目标与任务：

1.特征选择－基于应用领域的知识和挖掘的目标，选择初始数据集中特征的一个子集。

2.特征构成－有一些数据的转换对挖掘方法的结果有惊人影响，因此特征构成是一个比特殊的挖掘技术更有决定性因素。特征构成依赖于应用的知识，交叉学科知识的应用有利于数据准备的改进。特征选择方法：

1.特征排列算法：特征等级列表是根据特有的评估测量标准进行排序的。测量标准基于可用数据的精度、一致性、信息内容、样本之间的距离和特征之间的最终统计相关性。它仅指出特征间的相关性，不提供子集。

2.最小子集算法：返回一个最小特征子集，子集中的特征之间没有等级区别。子集中的特征与挖掘过程相关，其余的则是不相关的。在特征选择过程中需要建立特征评估方案来确定等级排列或特征子集选择，这一点很重要。例如，若一个数据集有３个特征{A1,A2,A3},特征出现或不出现取值0,1，共有23个归约的特征子集,

{0,0,0},{0,0,1},{0,1,0},{0,1,1},{1,0,0},{1,0,1},

{1,1,0},{1,1,1}特征选择的任务是搜索空间中的每一种状态都指定可能特征的一个子集。此问题n=3,空间较小，但大多数挖掘应用，n>20，搜索起点和搜索策略相当重要，常常用试探搜索代替穷举搜索。特征子集选择的两种方法1.自底向上方法：从空集开始，然后从初始特征集选择最相关的特征来写入此集。这种方法采用一种基于一些试探式的特征评估标准。2.自顶向下方法：从原始特征的的完整集合开始，然后根据所选的试探式评估尺度一个一个挑选出不相关的特征，并将其去除。一种可行的特征选择技术是基于均值和方差的比较。它适用于特征的分布是未知的情况，实际情况也不知道特征的分布，如果假设分布是正态，利用统计学可获得好的结果。这种技术仅是一种试探式的、不严密的数学建模工具。如果一个特征描述了不同种类的实体，用特征的方差对特征的均值进行标准化，进行不同类之间的比较。如果均值偏离很远，此特征具有分别两样本的能力，否则该特征的意义不大。基于均值和方差的检验公式设A和B是两个不同类特征的值的集合，n1和n2是相应的样本数。上式基于这样一种假设，已知特征独立于其他特征。主要用于分类问题。例题：下表是一组数据集，有两个输入特征X和Y，C是把样本分成两类的附加特征。假设检验阈值为0.5XYC0.30.7A0.20.9B0.60.6A0.50.5A0.70.7B0.40.9BX和Y特征的值的子集：

XA={0.3,0.6,0.5},XB={0.2,0.7,0.4}YA={0.7,0.6,0.5},YB={0.9,0.7,0.9}计算特征子集的均值和方差：

var(XA)=0.0233,var(XB)=0.6333var(YA)=0.01,var(YB)=0.0133结果分析：选择Ｘ进行归约，因它均值接近，检验结果小于阈值。Ｙ不需要归约，它可能是两类间的区别特征。上述方法分别检验特征。当分别考虑时，一些特征可能是有用的，但是在预测能力上它们可能会是冗余的。如果对特征进行总体的而不是单个的检查，我们就可获得一些关于它们的特性的额外信息。3.4主成分分析最流行的大型数据集维归约的统计方法是

Karhunen-Loeve(K-L)方法，也叫主成分分析。主成分分析方法是将以向量样本表示的初始数据集转换为一个新的导出维度的向量样本集。转换的目标是将不同样本中的信息集中在较小的维度当中。主成分分析的基本概念：将一个n维向量样本集Ｘ={x1,x2,x3,…,xm}转换成一个相同维度的集Ｙ={y1,y2,y3,…,ym}，但数据集Ｙ中将大部分信息内容存在前几维中。分析过程：将输入集维度Ｘ是归约为只有一个维度Ｙ,通过矩阵计算将Ｘ转化为Ｙ。

Y=A·Ｘ选择Ａ以使得Ｙ对已知数据集方差最大，转换中获得一维的Ｙ叫做第一主成分，它是最大方差方向的轴。它是数据点之间的距离平方和以及在它们在成分轴上的投影最小。矩阵A是不可能直接确定，在进行特征转换时，先计算协方差矩阵S。S定义为：通过计算S来实现与m个最大的特征值相对应的m个特征向量定义了n维空间向m维空间的线性转换,且m个特征相互独立。S中的相关知识：

1.Sn×n的特征值是λ1,λ2,…,λn,其中：

λ1≥λ2≥…λn≥02.特征向量e1,e2,…,en对应特征值λ1,λ2,…,λn,称为主轴。变换后的n维空间，第i个成分的方差等于第i个特征值，数据集的大多数信息集中在少数主成分中。变换后数据集有效维度(m)取值标准：则特征选择的标准是根据S的m个最大特征值之和与S的交点比率。（基于Y数据集方差最大准则）主成分分析例子：初始数据集是著名的艾里斯数据集，有4个特征，每一样本是一个4维向量。下表标准化的艾里斯数据的相关矩阵(对称)。Feature1Feature2Feature3Feature4Feature11.0000-0.10940.87180.8180Feature2-0.10941.0000-0.4205-0.3536Feature30.8718-0.42051.00000.9628Feature40.8180-0.35360.96281.0000由相关矩阵直接计算特征值，下表所示Feature特征值Feature12.91082Feature20.92122Feature30.14735Feature40.02062设定阈值R*=0.95,取前两个特征作为特征子集。

R=(2.91082+0.92122)/(2.91082+0.92122+0.14735+0.02062)=0.958>0.953.5值归约减少已知特征的离散值的数目是基于数据归约阶段的第二套技术，这就是特征离散化技术。则将连续型特征的值离散化，使之成为少量的区间，每一个区间映射到一个离散符号。其优点是简化了数据描述并易于理解数据和最终挖掘的结果。例如人的年龄可为儿童、青少年、成人，中年、老年。问题是这种归约处理存在两个问题：

1.什么是分割点?2.怎样选择区间表述？离散化可减少计算的复杂性。每个特征可以单独平整，其过程只执行一次，但需要有关特征的知识。假设一个特征有一列数字值，这些值可以用大于小于运算符由小到大进行排序，可采用分箱的概念将相近的值分组，然后各小组进行平整。均值或中位数，均值或众数适用于中等或大量箱数，边界平整适用于小箱数。例如：有一特征f的值集合是：

{3,2,1,5,4,3,1,7,5,3}，通过分类组成一个有序集合：

{1,1,2,3,3,3,4,5,5,7}分为３个箱：｛1,1,2,3,3,3,4,5,5,7｝

BIN1

BIN2

BIN3下面分别众数、均值和边界对其平整。众数平整：｛1,1,1,3,3,3,5,5,5,5｝

BIN1

BIN2

BIN3均值平整：｛1.33,1.33,1.33,3,3,3,5.25,5.25,5.25,5.25｝

BIN1

BIN2

BIN3边界平整：｛1,1,2,3,3,3,4,4,4,7｝

BIN1

BIN2

BIN3主要问题是找到最好的分割点。理论上，分割点不能独立其他特征来决定。但很多挖掘应用每个特征的试探性决策独立地给出了合适的结果。值归约问题可表述为一个选择k个箱的最优化问题：给出箱的数量k，分配箱中的值，使得一个值到它的箱子的均值或中值的平均距离最小。算法可能非常复杂，通常采用近似最优化算法，下面是一个改进的试探性程序过程步骤：1.对已知的特征的所有值进行分类。2.大概在指定每个箱中分类的相邻值(vi)的均等数目，箱子数已给定。3.当减少全局距离误差(ER)(所有从每个vi到其指定箱子的均值或众数的距离之和)时，把边界元素vi从一个箱中移到下一个(或前一个)箱中。例如：特征f的值集合是{5,1,8,2,2,9,2,1,8,6}分成３个箱(k=3)，采用众数平整箱子。第一次迭代计算：

a)集合排序为:{1,1,2,2,2,5,6,8,8,9}b)分箱为:{1,1,22,2,5,6,8,8,9}

BIN1

BIN2

BIN3c)(i)3个箱子的众数是{1,2,8}，用众数的绝对距离计算总误差：

ER=0+0+1+0+2+3+2+0+0+1=7(iv)在下面的三次迭代中把两个元素从BIN2移到BIN1，一个元素从BIN3移到BIN2,得到ER越来越小，新的分布(最终ER=4，再移动ER增大)为：

{1,1,2,2,25,6,8,8,9}

BIN1

BIN2

BIN3另一特征的值归约算法是用舍入来取得近似值。其算法步骤：

1.整除Y=int(X/10k)2.舍入If(mod(X,10k)≥10k/2)thenY=Y+13.整乘Y=Y*10k

其中k是从最右边起要舍入的位数。例如，如果k=1，数字1450舍入为1450；如果k=2，舍入为1500；如果k=3，舍入为1000。3.7案例归约如果我们没有参与数据收集过程，那么在挖掘时可看作是二次数据分析，挖掘过程与收集数据和选择初始数据的样本集的最优方法没有联系，样本是已知的，质量或好或坏，或者没有先验知识，需要解决案例数据集中使用的维数和样本数目，或者说数据表中的行数。因此案例归约是数据归约中最复杂的任务。案例归约过程实际上是一个取样过程，如果取样已由挖掘技术来管理，就不需要进行案例归约了。在数据分析中出现两种取样过程，第一种，有时数据集本身不过是来自较大的、未知总体的一个样本，取样是数据收集过程的一部分，挖掘对这类取样没有兴趣。第二