特征工程(中)

主要是搬运《Feature Engineering for Machine Learning》在 Apache.cn上的翻译版本中的第四、五、六章,依旧会根据自己的理解进行小小的修改。

第四章:特征缩放的效果:从词袋到TF—IDF

第五章:类别特征:机器鸡时代的鸡蛋计数

第六章:降维:使用PCA压缩数据集


特征缩放的效果:从词袋到TF—IDF

字袋易于生成,但远非完美。假设我们平等的统计所有单词,有些不需要的词也会被强调。在第三章提过一个例子,Emma and the raven。我们希望在文档表示中能强调两个主要角色。示例中,“Eama”和“raven”都出现了3词,但是“the”的出现高达8次,“and”出现了5次,另外“it”以及“was”也都出现了4词。仅仅通过简单的频率统计,两个主要角色并不突出。这是有问题的。

其他的像是“magnificently,” “gleamed,” “intimidated,” “tentatively,” 和“reigned,”这些辅助奠定段落基调的词也是很好的选择。它们表示情绪,这对数据科学家来说可能是非常有价值的信息。 所以,理想情况下,我们会倾向突出对有意义单词的表示。

Tf-Idf:词袋的小转折

Tf-Idf 是词袋的一个小小的转折。它表示词频-逆文档频。

tf-idf不是查看每个文档中每个单词的原始计数,而是查看每个单词计数除以出现该单词的文档数量的标准化计数。

bow(w,d) = #times word w appears in document d

其中N代表数据集中所有文档的数量。

分数$\frac{\operatorname{bow}(w, d) \times N}{(# \text { documents in which word w appears)}}$就是所谓的逆文件频率。

如果一个单词出现在许多文档中,则其逆文档频率接近1。

如果出现在较少文档中,则逆文档频率要高的多。

或者,对原始逆文档频率进行对数转换(自然对数,即以e为底),可以将1变为0,并使得较大的数字(比1大得多)变小。

如果将tf-idf定义为:

那么每个文档中出现一次的单词都将被有效清零,并且只出现在少数文档中的单词的计数将比以前更大。

看图片来了解它的具体内容。下图展示了一个包含4个句子的简单样例:“it is a puppy,” “it is a cat,” “it is a kitten,” 以及 “that is a dog and this is a pen.” 我们将这些句子绘制在“puppy”,“cat”以及“is”三个词的特征空间上。

现在让我们看看对逆文档频进行对数变换之后,相同四个句子的tf-idf表示。 下图显示了相应特征空间中的文档。可以注意到,单词“is”被有效地消除,因为它出现在该数据集中的所有句子中。另外,单词“puppy”和“cat”都只出现在四个句子中的一个句子中,所以现在这两个词计数得比之前更高(ln(4)=1.38…>1)。因此tf-idf使罕见词语更加突出,并有效地忽略了常见词汇。它与第三章中基于频率的滤波方法密切相关,但比放置严格截止阈值更具数学优雅性。

Tf-Idf的含义

Tf-idf使罕见的单词更加突出,并有效地忽略了常见单词。

测试

Tf-idf 通过乘以一个常量来转换字数统计特性。因此,它是特征缩放的一个例子,这是第2章介绍的一个概念。特征缩放在实践中效果有多好?

具体去原文的第四章)样例 4里看。

首先建立分类数据集

在区分餐厅和夜生活场所的时候,发现两个类别之间的评论数目有很大的差异,这是因为类不平衡数据集。

对于构建模型来说,不平衡的数据集存在一个问题:这个模型会把大部分精力花在比重更大的类上。

针对这种问题,并且在两个类别上都有大量的数据,那么可以用一个较好的方法,是将数目较大的类(餐厅)进行下采样,使之与数目较小的类(夜生活)数目大致相同。

用tf-idf 转换缩放词袋

这个实验的目标是比较词袋,tf-idf以及L2归一化对于线性分类的作用。注意,做tf-idf接着做L2归一化和单独做L2归一化是一样的。所以我们需要只需要3个特征集合:词袋,tf-idf,以及逐词进行L2归一化后的词袋。

在这个例子中,我们将使用Scikit-learn的CountVectorizer将评论文本转化为词袋。所有的文本特征化方法都依赖于标记器(tokenizer),该标记器能够将文本字符串转换为标记(词)列表。在这个例子中,Scikit-learn的默认标记模式是查找2个或更多字母数字字符的序列。标点符号被视为标记分隔符。

测试集上进行特征缩放

特征缩放的一个细微之处是它需要了解我们在实践中很可能不知道的特征统计,例如均值,方差,文档频率,L2范数等。为了计算tf-idf表示,我们不得不根据训练数据计算逆文档频率,并使用这些统计量来调整训练和测试数据。在Scikit-learn中,将特征变换拟合到训练集上相当于收集相关统计数据。然后可以将拟合过的变换应用于测试数据。

当我们使用训练统计来衡量测试数据时,结果看起来有点模糊。测试集上的最小-最大比例缩放不再整齐地映射到零和一。L2范数,平均数和方差统计数据都将显得有些偏离。这比缺少数据的问题好一点。例如,测试集可能包含训练数据中不存在的单词,并且对于新的单词没有相应的文档频。通常的解决方案是简单地将测试集中新的单词丢弃。这似乎是不负责任的,但训练集上的模型在任何情况下都不会知道如何处理新词。一种稍微不太好的方法是明确地学习一个“垃圾”单词,并将所有罕见的频率单词映射到它,即使在训练集中也是如此,正如“罕见词汇”中所讨论的那样。

使用逻辑回归进行分类

逻辑回归是一个简单的线性分类器。通过对输入特征的加权组合,输入到一个sigmoid函数。sigmoid函数将任何实数平滑的映射到介于0和1之间。如下图绘制sigmoid函数曲线。由于逻辑回归比较简单,因此它通常是最先接触的分类器。

该图是sigmoid函数的插图。该函数将输入的实数x转换为一个0到1之间的数。它有一组参数w,表示围绕中点0.5增加的斜率。截距项b表示函数输出穿过中点的输入值。如果sigmoid输出大于0.5,则逻辑分类器将预测为正例,否则为反例。通过改变w和b,可以控制决策的改变,以及决策响应该点周围输入值变化的速度。

在使用默认参数训练逻辑回归分类器时得结果

1
2
3
# Test score with bow features: 0.775873066497
# Test score with l2-normalized features: 0.763514590974
# Test score with tf-idf features: 0.743182905438

矛盾的是,结果表明最准确的分类器是使用BOW特征的分类器。出乎意料我们之外。事实证明,造成这种情况的原因是没有很好地“调整”分类器,这是比较分类器时一个常见的错误。

使用正则化调整逻辑回归

逻辑回归有些华而不实。 当特征的数量大于数据点的数量时,找到最佳模型的问题被认为是欠定的。 解决这个问题的一种方法是在训练过程中增加额外的约束条件。 这就是所谓的正则化,技术细节将在下一节讨论。

逻辑回归的大多数实现允许正则化。为了使用这个功能,必须指定一个正则化参数。正则化参数是在模型训练过程中未自动学习的超参数。相反,他们必须手动进行调整,并将其提供给训练算法。这个过程称为超参数调整。调整超参数的一种基本方法称为网格搜索:指定一个超参数值网格,并且调谐器以编程方式在网格中搜索最佳超参数设置格。 找到最佳超参数设置后,使用该设置对整个训练集进行训练,并比较测试集上这些同类最佳模型的性能。

重点:比较模型时调整超参数

比较模型或特征时,调整超参数非常重要。 软件包的默认设置将始终返回一个模型。 但是除非软件在底层进行自动调整,否则很可能会返回一个基于次优超参数设置的次优模型。 分类器性能对超参数设置的敏感性取决于模型和训练数据的分布。 逻辑回归对超参数设置相对稳健(或不敏感)。 即便如此,仍然有必要找到并使用正确的超参数范围。 否则,一个模型相对于另一个模型的优点可能仅仅是由于参数的调整,并不能反映模型或特征的实际表现。

即使是最好的自动调整软件包仍然需要指定搜索的上限和下限,并且找到这些限制可能需要几次手动尝试。

在本例中,我们手动将逻辑正则化参数的搜索网格设置为{1e-5,0.001,0.1,1,10,100}。 上限和下限花费了几次尝试来缩小范围。 表4-1给出了每个特征集合的最优超参数设置

Method L2 Regularization
BOW 0.1
L2-normalized 10
TF-IDF 0.01

我们也想测试tf-idf和BOW之间的精度差异是否是由于噪声造成的。 为此,我们使用k折交叉验证来模拟具有多个统计独立的数据集。它将数据集分为k个折叠。交叉验证过程通过分割后的数据进行迭代,使用除去某一折之外的所有内容进行训练,并用那一折验证结果。Scikit-Learn中的GridSearchCV功能通过交叉验证进行网格搜索。 下图显示了在每个特征集上训练的模型的精度测量分布箱线图。 盒子中线表示中位精度,盒子本身表示四分之一和四分之三分位之间的区域,而线则延伸到剩余的分布。

通过重采样估计方差

现代统计方法假设底层数据是随机分布的。 数据导出模型的性能测量也受到随机噪声的影响。 在这种情况下,基于相似数据的数据集,不止一次进行测量总是比较好的。 这给了我们一个测量的置信区间。 K折交叉验证就是这样一种策略。 重采样是另一种从相同底层数据集生成多个小样本的技术。

该图是分类器精度在每个特征集和正则化设置下的分布。 准确度是以5折交叉验证的平均准确度来衡量的

在图中,L2归一化后的特征结果看起来非常糟糕。 但不要被蒙蔽了 。准确率低是由于正则化参数设置不恰当造成的 - 实际证明次优超参数会得到相当错误的结论。 如果我们使用每个特征集的最佳超参数设置来训练模型,则不同特征集的测试精度非常接近。

Regularization Parameter BOW normalized Tf-idf
0.00001 0.578971 0.575724 0.721638
0.001 0.751811 0.575724 0.788648*
0.1 0.782839* 0.589120 0.763566
1 0.773818 0.734247 0.741150
10 0.755160 0.776756* 0.721467
100 0.739373 0.761106 0.712309

上面表中每个超参数设置的平均交叉验证分类器准确度。 星号表示最高精度

最终的训练和测试步骤来比较不同的特征集,得到下面的结果

Feature Set Test Accuracy
Bag-of-Words 0.78360708021
L2 -normalized 0.780178599904
Tf-Idf 0.788470738319

适当的调整提高了所有特征集的准确性,并且所有特征集在正则化后进行逻辑回归得到了相近的准确率。tf-idf模型准确率略高,但这点差异可能没有统计学意义。 这些结果是完全神秘的。 如果特征缩放效果不如vanilla词袋的效果好,那为什么要这么做呢? 如果tf-idf没有做任何事情,为什么总是要这么折腾? 我们将在本章的其余部分中探索答案。

深入:发生了什么?

为了明白结果背后隐含着什么,我们必须考虑模型是如何使用特征的。对于类似逻辑回归这种线性模型来说,是通过所谓的数据矩阵的中间对象来实现的。 数据矩阵包含以固定长度平面向量表示的数据点。 根据词袋向量,数据矩阵也被称为文档词汇矩阵。 图3-1显示了一个向量形式的词袋向量,图4-1显示了特征空间中的四个词袋向量。 要形成文档词汇矩阵,只需将文档向量取出,平放,然后将它们堆叠在一起。 这些列表示词汇表中所有可能的单词。 由于大多数文档只包含所有可能单词的一小部分,因此该矩阵中的大多数都是零,是一个稀疏矩阵。

特征缩放方法本质上是对数据矩阵的列操作。特别的,tf-idf和L2归一化都将整列(例如n-gram特征)乘上一个常数。

Tf-idf = 列缩放

Tf-idf和L2归一化都是数据矩阵上的列操作。训练线性分类器归结为寻找最佳的线性组合特征,这是数据矩阵的列向量。 解空间的特征是列空间和数据矩阵的空间。训练过的线性分类器的质量直接取决于数据矩阵的零空间和列空间。 大的列空间意味着特征之间几乎没有线性相关性,这通常是好的。 零空间包含“新”数据点,不能将其表示为现有数据的线性组合; 大的零空间可能会有问题。

列缩放操作如何影响数据矩阵的列空间和空间? 答案是“不是很多”。但是在tf-idf和L2归一化之间有一个小小的差别。

由于几个原因,数据矩阵的零空间可能很大。 首先,许多数据集包含彼此非常相似的数据点。 这使得有效的行空间与数据集中数据的数量相比较小。 其次,特征的数量可以远大于数据的数量。 词袋特别擅长创造巨大的特征空间。 在我们的Yelp例子中,训练集中有29K条评论,但有47K条特征。 而且,不同单词的数量通常随着数据集中文档的数量而增长。 因此,添加更多的文档不一定会降低特征与数据比率或减少零空间。

在词袋模型中,与特征数量相比,列空间相对较小。 在相同的文档中可能会出现数目大致相同的词,相应的列向量几乎是线性相关的,这导致列空间不像它可能的那样满秩。 这就是所谓的秩亏。

秩亏行空间和列空间导致模型空间预留过度的问题。 线性模型为数据集中的每个特征配置权重参数。 如果行和列空间满秩$^1$,那么该模型将允许我们在输出空间中生成任何目标向量。 当模型不满秩时,模型的自由度比需要的更大。 这使得找出解决方案变得更加棘手。

列空间被定义为所有列向量的线性组合:$a_{1} v_{1}+a_{2} v_{2}+\ldots+a_{n} v_{n}$。比方说,特征缩放用一个常数倍来替换一个列向量,$v_{1}=c v_{1}$。但是我们仍然可以通过用$\widetilde{a_{1}}=\frac{a_{1}}{c}$来 替换$a_{1}$,生成原始的线性组合。看起来,特征缩放不会改变列空间的秩。类似地,特征缩放不会影响空间的秩,因为可以通过反比例缩放权重向量中的对应条目来抵消缩放的特征列。

但是,仍然存在一个陷阱。 如果标量为0,则无法恢复原始线性组合;$v_{1}$消失了。 如果该向量与所有其他列线性无关,那么我们已经有效地缩小了列空间并放大了零空间。

如果该向量与目标输出不相关,那么这将有效地修剪掉噪声信号,这是一件好事。 这是tf-idf和L2归一化之间的关键区别。 L2归一化永远不会计算零的范数,除非该向量包含全零。 如果向量接近零,那么它的范数也接近于零。 按照小规范划分将突出向量并使其变大。

另一方面,如图2所示,Tf-idf可以生成接近零的缩放因子。 当这个词出现在训练集中的大量文档中时,会发生这种情况。 这样的话有可能与目标向量没有很强的相关性。 修剪它可以使模型专注于列空间中的其他方向并找到更好的解决方案。 准确度的提高可能不会很大,因为很少有噪声方向可以通过这种方式修剪。

在特征缩放的情况下,L2和tf-idf对于模型的收敛速度确实有促进。 这是该数据矩阵有一个更小的条件数的标志。 事实上,L2归一化使得条件数几乎一致。 但情况并非条件数越多,解决方案越好。 在这个实验中,L2归一化收敛比BOW或tf-idf快得多。 但它对过拟合也更敏感:它需要更多的正则化,并且对优化期间的迭代次数更敏感。

总结

在本章中,我们使用tf-idf作为入口点,详细分析特征变换如何影响(或不影响)模型。Tf-idf是特征缩放的一个例子,所以我们将它的性能与另一个特征缩放方法-L2标准化进行了对比。

结果并不如预期。Tf-idf和L2归一化不会提高最终分类器的准确度,而不会超出纯词袋。 在获得了一些统计建模和线性代数处理知识之后,我们意识到了为什么:他们都没有改变数据矩阵的列空间

两者之间的一个小区别是,tf-idf可以“拉伸”字数以及“压缩”它。 换句话说,它使一些数字更大,其他数字更接近 归零。 因此,tf-idf可以完全消除无意义的单词。

我们还发现了另一个特征缩放效果:它改善了数据矩阵的条件数,使线性模型的训练速度更快。 L2标准化和tf-idf都有这种效果。

总而言之,正确的特征缩放可以有助于分类。 正确的缩放突出了信息性词语,并降低了常见单词的权重。 它还可以改善数据矩阵的条件数。 正确的缩放并不一定是统一的列缩放。

这个故事很好地说明了在一般情况下分析特征工程的影响的难度。 更改特征会影响训练过程和随后的模型。 线性模型是容易理解的模型。 然而,它仍然需要非常谨慎的实验方法和大量的深刻的数学知识来区分理论和实际的影响。 对于更复杂的模型或特征转换来说,这是不可能的。

类别特征:机器鸡时代的鸡蛋计算

一个类别特征,见名思义,就是用来表达一种类别或标签。比如,一个类别特征能够表达世界上的主要城市,一年四季,或者说一个公司的产品(石油、路程、技术)。在真实世界的数据集中,类别值的数量总是有限的。同时这些值一般可以用数值来表示。但是,与其他数值变量不同,分类变量的值不能相互排序。(作为行业类型,石油与旅行无法进行比较)它们被称之为非序数的。

一个简单的问题可以作为测试是否应该是一个分类变量的试金石测试:“两个事情的值不同,或者它们类型不同,这有什么关系吗?”股价为500美元的比股价为100美元的价格高5倍。 所以股票价格应该用一个连续的数字变量表示。 另一方面,公司的产业(石油,旅游,技术等)应该无法被比较的,也就是类别特征。

大的分类变量在交易记录中特别常见。 对于实例中,许多Web服务使用id作为分类变量来跟踪用户具有数百至数百万的值,取决于唯一的数量服务的用户。 互联网交易的IP地址是另一个例子一个很大的分类变量。 它们是分类变量,因为即使用户ID和IP地址是数字,它们的大小通常与任务无关在眼前。 例如,在进行欺诈检测时,IP地址可能是相关的个人交易。 某些IP地址或子网可能会产生更多欺骗性交易比其他人。 但是164.203.x.x的子网本质上并不多欺诈性比164.202.x.x; 子网的数值无关紧要。

文档语料库的词汇可以被解释为一个大的分类变量,类别是唯一的单词。 它可能在计算上很昂贵代表如此多的不同类别。 如果一个类别(例如,单词)出现多个数据点(文档)中的时间,然后我们可以将它表示为一个计数并表示所有的类别通过他们的统计数字。 这被称为bin-counting。 我们用分类变量的共同表示开始讨论,并且最终蜿蜒曲折地讨论了大范围的bin-counting问题变量,这在现代数据集中非常普遍。

对类别特征编码

分类变量的类别通常不是数字。例如,眼睛的颜色可以是“黑色”,“蓝色”,“棕色”等。因此,需要使用编码方法将这些非数字类别变为数字。 简单地将一个整数(比如1到k)分配给k个可能的类别中的每一个都是诱人的。 但是,由此产生的价值观可以互相授权,这在类别中不应该被允许。

One-hot编码

将类别特征进行表示一个最好的办法就是使用一组比特位来表达。每一位代表一个可能的类别。 如果该变量不能一次成为多个类别,那么该组中只有一位可以是1。 这被称为独热编码,它在Scikit Learn中实现sklearn.preprocessing.OneHotEncoder。 每个位都是一个特征。 因此是一个绝对的具有k个可能类别的变量被编码为长度为k的特征向量

对3个城市的类别进行独热编码
City e1 e2 e3
San Francisco 1 0 0
New York 0 1 0
Seattle 0 0 1

热编码非常易于理解。 但它使用的是比严格必要的更多的一点。 如果我们看到k-1位是零,那么最后一位必须是1,因为变量必须具有k个值中的一个。 在数学上,可以写下这个约束条件为“所有位的和必须等于1”。

因此,我们有一个线性的依赖性。 线性相关特征,就像我们一样在tf-idf中发现,有点烦人,因为它意味着训练线性模型不会是唯一的。 特征的不同线性组合可以做出同样的预测,所以我们需要跳过额外条件的来理解特征对预测的影响。

dummy编码

独热编码的问题是它允许k个自由度,其中变量本身只需要k-1。 虚拟编码通过仅使用表示中的k-1个特征来消除额外的自由度。 公共汽车下面有一个特征,由全零矢量表示。 这被称为参考类别。 虚拟编码和独热编码都是在Pandas中以pandas.get_dummies的形式实现的。

表 对3个城市的类别进行dummy编码

City e1 e2
San Francisco 1 0
New York 0 1
Seattle 0 0

使用虚拟编码进行建模的结果比单编码更易解释。这很容易在简单的线性回归问题中看到。 假设我们有一些数据关于三个城市的公寓租赁价格:旧金山,纽约和西雅图。(见表5-3)

表三个不同城市的公寓价格数据集

id city Rent
0 SF 3999
1 SF 4000
2 SF 4001
3 NYC 3499
4 NYC 3500
5 NYC 3501
6 Seattle 2499
7 Seattle 2500
8 Seattle 2501

我们这时能够仅仅依靠城市这一个变量来建立线性回归来预测租金的价格。
线性回归模型可以这样写

习惯上我们还添加一个常量来,这样的话当x全部为0,y不会为0.

通过独热编码,截距项表示目标变量的全局均值租金价格,并且每个线性系数表示该城市的平均租金与全局平均值的差异。

通过虚拟编码,偏差系数代表响应的平均值参考类别的变量y,在这个例子中是纽约市。该第i个特征的系数等于平均响应之间的差异第i类别的值和参考类别的平均值。

表:线性回归学得的系数

id x1 x2 x3 b
one-hot 166.67 666.67 -833.33 3333.33
dummy coding 0 500 -1000 3500

Effect 编码

分类变量编码的另一种变体称为Effect编码。 Effect编码与虚拟编码非常相似,区别在于参考类别现在由所有-1的向量表示。

表: Effect编码表示3个城市

City e1 e2
San Francisco 1 0
New York 0 1
Seattle -1 -1

Effect编码与虚拟编码非常相似,但是在线性回归中更容易被拟合。截距项表示目标的全球平均值变量,单个系数表示各个类别的平均值与全球平均值有多少差异。 (独热编码实际上具有相同的截距和系数,但在这种情况下,每个城市都有线性系数。 在效果编码中,没有单一特征代表参考类别。 因此,参考类别的影响需要分别计算为所有其他类别的系数的负和。

类别变量的优点和缺点

独热,虚拟和效果编码非常相似。 他们每个人都有优点和缺点。 独热编码是多余的,它允许多个有效模型一样的问题。 非唯一性有时候对解释有问题。该优点是每个特征都明显对应于一个类别。 此外,失踪数据可以编码为全零矢量,输出应该是整体目标变量的平均值。

虚拟编码和效果编码不是多余的。 他们产生独特和可解释的模型。 虚拟编码的缺点是它不能轻易处理缺少数据,因为全零矢量已经映射到参考类别。它还编码每个类别相对于参考类别的影响,其中看起来很奇怪。 效果编码通过使用不同的代码来避免此问题参考类别。 但是,所有-1的矢量都是一个密集的矢量,对于存储和计算来说都很昂贵。 因此,Pandas和Scikit Learn等流行的ML软件包选择了虚拟编码或独热编码,而不是效应编码。当类别数量变得非常多时,所有三种编码技术都会失效大。 需要不同的策略来处理非常大的分类变量。

处理大量的类别特征

互联网上的自动数据收集可以生成大量的分类变量。这在诸如定向广告和欺诈检测等应用中很常见。 在有针对性的广告中,任务是根据用户的搜索查询或当前页面将用户与一组广告进行匹配。 功能包括用户ID,广告的网站域,搜索查询,当前页面以及这些功能的所有可能的成对连词。 (查询是一个文本字符串,可以切分成常用的文本特征,但查询通常很短,通常由短语组成,因此在这种情况下最好的行为通常是保持完整,或 通过哈希函数来简化存储和比较)其中每一个都是一个非常大的分类变量。 我们面临的挑战是如何找到一个能够提高内存效率的优秀特征表示,并生成训练速度快的准确模型。

对于这种类别特征处理的方案有:

  1. 对编码不做任何事情。 使用便宜的训练简单模型。 在许多机器上将独热编码引入线性模型(逻辑回归或线性支持向量机)。
  2. 压缩编码,有两种方式 a. 对特征进行哈希—在线性回归中特别常见 b. bin-counting—在线性回归中与树模型都常见

使用one-hot编码是可行的。在微软搜索广告研究中,Graepel等人 [2010]报告在贝叶斯概率回归模型中使用这种二值特征,可以使用简单更新在线进行培训。 与此同时,其他组织则争论压缩方法。 来自雅虎的研究人员 通过特征散列发誓[Weinberger et al。2009年]。 尽管McMahan等人[2013]在谷歌的广告引擎上尝试了功能哈希,并没有找到显着的改进。 然而,微软的其他人则被认为是计数[Bilenko,2015]。

所有这些想法都有利有弊。

特征哈希

散列函数是一个确定性函数,它映射一个潜在的无界整数到有限整数范围[1,m]。 由于输入域可能大于输出范围,多个数字可能会映射到相同的输出。 这被称为a碰撞。 统一的散列函数可确保大致相同数量的数字被映射到每个m箱。 在视觉上,我们可以将散列函数视为一台机器可以吸入编号的球并将它们传送到一个m箱。 球与相同的号码将始终被路由到同一个bin。

散列函数可以为任何可以用数字表示的对象构造(对于可以存储在计算机上的任何数据都是如此):数字,字符串,复杂的结构等

当有很多特征时,存储特征向量可能占用很多空间。 特征散列将原始特征向量压缩为m维通过对特征ID应用散列函数来创建矢量。 例如,如果原件特征是文档中的单词,那么散列版本将具有固定的词汇大小为m,无论输入中有多少独特词汇。

功能散列的另一个变体添加了一个符号组件,因此计数也是从哈希箱中增加或减少。 这确保了内部产品之间散列特征与原始特征的期望值相同。

哈希后内积的值在时间复杂度在O(1/(m**0.5)).所以哈希表m的大小可以根据可接受的错误来选择。在实践中,选择合适的m可能需要一些试验和错误。特征哈希可以用于涉及特征内积的模型矢量和系数,例如线性模型和核心方法。 它一直证明在垃圾邮件过滤任务中取得成功[Weinberger等,2009]。在有针对性的广告案例中,McMahan et al。 [2013年]报告不能将预测误差降低到可接受的水平,除非m的数量级为数十亿。散列特征的一个缺点是散列特征是聚合的原始特征,不再可解释。

在这个例子中,我们将使用Yelp评论数据集来演示存储和,解释性使用的为sklearn的库FeatureHasher。在有针对性的广告案例中,McMahan

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import pandas as pd
import json

js = []
with open('yelp_academic_dataset_review.json') as f:
for i in range(10000):
js.append(json.loads(f.readline()))

review_df = pd.DataFrame(js)

m = len(review_df.business_id.unique())

>>>m
4174

In [4]: from sklearn.feature_extraction import FeatureHasher
...:
...: h = FeatureHasher(n_features=m, input_type='string')
...:
...: f = h.transform(review_df['business_id'])
...:

In [5]: review_df['business_id'].unique().tolist()[0:5]
Out[5]:
['9yKzy9PApeiPPOUJEtnvkg',
'ZRJwVLyzEJq1VAihDhYiow',
'6oRAC4uyJCsJl1X0WZpVSA',
'_1QQZuf4zZOyFCvXc0o6Vg',
'6ozycU1RpktNG2-1BroVtw']


In [6]: f.toarray()
Out[6]:
array([[ 0., 0., 0., ..., 0., 0., 0.],
[ 0., 0., 0., ..., 0., 0., 0.],
[ 0., 0., 0., ..., 0., 0., 0.],
...,
[ 0., 0., 0., ..., 0., 0., 0.],
[ 0., 0., 0., ..., 0., 0., 0.],
[ 0., 0., 0., ..., 0., 0., 0.]])

我们看看特征的存储

1
2
3
4
5
print('Our pandas Series, in bytes: ', getsizeof(review_df['business_id']))
print('Our hashed numpy array, in bytes: ', getsizeof(f))

>>>790104
>>>56

我们可以清楚地看到如何使用特征散列会以计算方式使我们受益,牺牲直接的用户解释能力。 这是一个容易的权衡来接受何时从数据探索和可视化发展到机器学习管道对于大型数据集。

bin-counting

Bin-counting是机器学习中常见的重新发现之一。 从广告点击率预测到硬件分支预测,它已经被重新创建并用于各种应用。 然而,因为它是一种特征工程技术,而不是一种建模或优化方法,所以没有关于该主题的研究论文。

bin-counting的想法非常简单:不是使用分类变量的值作为特征,而是使用目标在该值下的条件概率。 换句话说,我们计算该值与我们希望预测的目标之间的关联统计信息,而不是编码的身份分类值。 对于那些熟悉朴素贝叶斯分类器的人来说,这个统计值应该敲响警钟,因为它是假设所有特性都是独立的类的条件概率。最好举例说明

User Number of clicks Number of non-clicks probability of click QueryHash,AdDomain Number of clicks Number of non-clicks probability of click
Alice 5 120 0.0400 0x598fd4fe,foo.com 5000 30000 0.167
bob 20 230 0.0800 0x50fa3cc0,bar.org 100 900 0.100
joe 2 3 0.400 0x437a45e1,qux.net 6 18 0.250

Bin-counting假定历史数据可用于计算统计。 上表包含分类变量每个可能值的汇总历史计数。 根据用户点击任何广告的次数以及未点击的次数,我们可以计算用户“Alice”点击任何广告的概率。 同样,我们可以计算任何查询 - 广告 - 域组合的点击概率。 在训练时,每当我们看到“爱丽丝”时,都使用她的点击概率作为模型的输入特征。 QueryHash-AdDomain对也是如此,例如“0x437a45e1,qux.net”。

假设有10,000个用户。 独热编码会生成一个稀疏矢量长度为10,000,在列中对应于值的单个1当前数据点。 Bin-counting将所有10,000个二进制列编码为一个功能的真实值介于0和1之间。

除了历史点击概率外,我们还可以包含其他功能:原始计数本身(点击次数和非点击次数),对数比率或任何其他概率的衍生物。 我们的例子是预测广告点击率,通过率。 但该技术很容易应用于一般的二元分类。 它也可以使用通常的技术容易地扩展到多级分类将二元分类器扩展到多个类,即通过一对多优势比或其他多类标签编码。

Bin-counting 的优势和对数比

比值比通常定义在两个二元变量之间。 它通过提出这样一个问题来看待他们的联想强度:“当X为真时,Y有多大可能是真的”。例如,我们可能会问,“Alice点击广告的可能性大于 一般人口?“在这里,X是二进制变量”是Alice是当前用户“,而Y是变量”点击广告与否“。 该计算使用所谓的双向列联表(基本上,四个数字对应于X和Y的四种可能组合)

click Non-Click Total
Alice 5 120 125
Not Alice 995 18880 19875
Total 1000 19000 20000

表:偶然发生的用户点击事件

定输入变量X和目标变量Y,优势比定义为

在我们的例子中,这意味着“爱丽丝点击广告而不是点击的可能性”和“其他人点击而非点击的可能性有多大”之间的比率。在这种情况下,数字是

更简单地说,我们可以看看分子,它检查多少可能性单个用户(Alice)是否点击广告而不是点击。 这适合大型具有许多值的分类变量,而不仅仅是两个。

概率比率可能很容易变得非常小或非常大。 (例如,将会有几乎不会点击广告的用户,也可能是点击广告的用户更频繁得多)日志转换再次来到我们的救援。 另一个对数的有用特性是它将一个划分变为一个减法。

简而言之,bin-counting将分类变量转换为有关的统计信息值。 它变成了一个大的,稀疏的分类变量的二进制表示变成一个非常小,密集的实值数值表示。

在实施方面,垃圾箱计数需要在每个类别之间存储地图及其相关计数。 (其余的统计数据可以从中得到原始计数)。因此它需要O(k)空间,其中k是唯一值的数量的分类变量。

我们采用Kaggle的比赛Avazu举个例子.

Avazu Click数据集

  • 有24个变量,包括’点击’,一个二进制的点击、不点击计数器和’device_id’,用于跟踪显示广告的设备。
  • 完整的数据集包含4,0428,967个观测值,其中有2,686,408个独特的设备。

Avazu竞赛使用广告数据来预测点击率,但我们将使用它来演示如何bin计数可以大大减少大的特征空间流数据量。

Bin-counting例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
>>> import pandas as pd

# train_subset data is first 10K rows of 6+GB set
>>> df = pd.read_csv('data/train_subset.csv')

# How many unique features should we have after?
>>> len(df['device_id'].unique())
7201

# For each category, we want to calculate:
# Theta = [counts, p(click), p(no click), p(click)/p(no click)]

>>> def click_counting(x, bin_column):
... clicks = pd.Series(x[x['click'] > 0][bin_column].value_counts(),
... name='clicks')
... no_clicks = pd.Series(x[x['click'] < 1][bin_column].value_counts(),
... name='no_clicks')

... counts = pd.DataFrame([clicks,no_clicks]).T.fillna('0')
... counts['total_clicks'] = counts['clicks'].astype('int64') +
... counts['no_clicks'].astype('int64')
... return counts

>>> def bin_counting(counts):
... counts['N+'] = counts['clicks']
... .astype('int64')
... .divide(counts['total_clicks'].astype('int64'))
... counts['N-'] = counts['no_clicks']
... .astype('int64')
... .divide(counts['total_clicks'].astype('int64'))
... counts['log_N+'] = counts['N+'].divide(counts['N-'])
... # If we wanted to only return bin-counting properties,
... # we would filter here
... bin_counts = counts.filter(items= ['N+', 'N-', 'log_N+'])
... return counts, bin_counts

# Bin counts example: device_id
>>> bin_column = 'device_id'
>>> device_clicks = click_counting(df.filter(items=[bin_column, 'click']),
... bin_column)
>>> device_all, device_bin_counts = bin_counting(device_clicks)

# Check to make sure we have all the devices
>>> len(device_bin_counts)
7201

>>> device_all.sort_values(by = 'total_clicks', ascending=False).head(4)

clicks no_clicks total N+ N- log_N+
a99f214a 15729 71206 86935 0.180928 0.819072 0.220894
c357dbff 33 134 167 0.197605 0.802395 0.246269
31da1bd0 0 62 62 0.000000 1.000000 0.000000
936e92fb 5 54 59 0.084746 0.915254 0.092593

关于稀有类别

就像罕见的词,罕见的类别需要特殊的处理。 想想一个用户每年登录一次:几乎没有数据可以可靠估计她广告的点击率。 而且,稀有类别会在计数表中浪费空间。解决这个问题的一种方法是通过补偿,一种积累的简单技术一个特殊垃圾箱中所有稀有类别的数量。 如果计数大于a一定的门槛,那么这个类别就有自己的统计数字。 否则,使用来自回退箱的统计数据。 这基本上会恢复单个的统计信息罕见类别与所有罕见类别的统计数据进行比较。 当使用back-off方法,它有助于为统计信息添加二进制指标来自后退箱。

图:如果一个罕见的类别获得计数,它可以使用自己的计数统计数据进行建模,从而超过退避箱的阈值。

还有另一种方法来处理这个问题,称为count-min sketch [Cormode和Muthukrishnan,2005]。 在这种方法中,所有类别,罕见或频繁类似通过多个散列函数进行映射,输出范围为m,远小于类别的数量,k。 当检索一个统计量时,计算所有的哈希值该类别,并返回最小的统计量。 拥有多个散列函数减轻单个散列函数内碰撞的可能性。 该计划有效因为可以做出散列函数次数m,散列表大小小于k,类别的数量,仍然保持较低的整体碰撞可能性。

下图说明。每个项i都映射到计数数组的每一行中的一个单元格。当$C_t$更新到它到达的项目$ i_t$时,$C_t$被添加到每个单元格中,使用$h_1…h_d$函数散列。

防止数据泄露

由于bin计数依赖于历史数据来生成必要的统计数据,因此它需要经过一段数据收集期等待,从而导致学习流程稍有延迟。此外,当数据分布发生变化时,需要更新计数。数据更改越快,重新计算计数的频率就越高。这对于目标广告等应用程序尤其重要,因为在目标广告中,用户偏好和流行的查询变化非常快,并且缺乏对当前发布的适应可能会给广告平台带来巨大损失。

有人可能会问,为什么不使用相同的数据集来计算相关统计量并训练模型?这个想法看起来很天真。这里最大的问题是统计数据涉及目标变量,这是模型试图预测的。使用输出来计算输入特征会导致一个称为泄漏的有害问题。简而言之,泄漏意味着信息被揭示给模型,从而使它有更好的预测的不切实际的优势。当测试数据泄露到训练集中,或者未来的数据泄漏到过去时,可能会发生这种情况。任何时候都会向模型提供在生产中实时进行预测时应该无法访问的信息,这会导致泄漏。 Kaggle的维基提供了更多泄漏示例以及为什么它对机器学习应用程序不利。

如果bin计数程序使用当前数据点的标签来计算输入统计量的一部分,则这构成直接泄漏。防止这种情况的一种方法是在计数收集(用于计算箱计数统计)和训练之间进行严格分离,像下图所示,即使用较早批次的数据点进行计数,将当前数据点用于训练(将分类变量映射到历史统计我们刚刚收集),并使用未来的数据点进行测试。这解决了泄漏问题,但引入了上述延迟(输入统计信息,因此模型将跟踪当前数据)。

事实证明,还有另一种基于差别隐私的解决方案。 如果统计数据的分布保持大致相同或不存在任何一个数据点,则该统计近似是防漏的。 在实践中,增加一个分布拉普拉斯(0,1)的小随机噪声足以掩盖单个数据点的任何潜在泄漏。 这个想法可以结合一次性计算来制定当前数据的统计数据。 Owen Zhang在他的“赢得数据科学竞赛”的演讲中详细介绍了这个技巧。

COUNTS WITHOUT BOUNDS

如果在越来越多的历史数据下统计数据不断更新,原始数量将无限增长。这可能是模型的问题。训练有素的模型“知道”输入数据直至观察到的比例。一个训练有素的决策树可能会说“当x大于3时,预测为1”。一个经过训练的线性模型可能会说“乘以0.7的多个x并查看结果是否大于全局平均值”。这些可能是x介于0和5之间。但是除此之外会发生什么?没有人知道。

当输入计数增加时,模型将需要重新训练以适应当前的比例。如果计数积累得相当缓慢,那么有效量表不会变得太快,并且模型不需要过于频繁地重新训练。但是当计数增加很快时,频繁的再培训将是一个麻烦。

出于这个原因,使用标准化计数通常会更好 以已知的时间间隔为界。例如,估计的点击率是 有界[0,1]之间。另一种方法是采取对数变换,即施加一个 严格的限制,但是当数量非常大时,增加速度会很慢。

这两种方法都不能防止转移投入分布,例如,去年的芭比娃娃现在已经过时,人们将不再点击这些广告。该模型需要重新训练以适应输入数据分布中的这些更根本性的变化,否则整个流程将需要迁移到模型不断适应输入的在线学习环境。

总结

本章详细介绍的每种方法都有其优缺点。下面是权衡的结果。

Plain one-hot encoding

空间复杂度:o(n)使用稀疏向量格式,其中n是数据点的数目。

时间复杂度:o(nk)在线性模型下,其中K是类别的数目

优点:

  • 容易实现
  • 更高的精度
  • 在线学习特别容易扩展

缺点

  • 计算不足
  • 如果类别增加则不能够使用
  • 对线性模型以外的任何其他方法都不可行
  • 对于大数据集需要分布式训练

Feature hashing

空间复杂度:o(n)使用稀疏矩阵格式,其中n是数据点的数量

时间复杂度:o(nm)在线性或内核模型下,其中m是哈希容器的数目。

优点:

  • 容易实现
  • 容易训练
  • 容易扩展到新类别
  • 容易处理稀有类别
  • 在线学习容易扩展

缺点

  • 只能够使用线性或核模型
  • 哈希编码很难解释
  • 精度有争议

Bin-counting

空间复杂度:o(n+k)表示每个数据点的小而密集的表示,加上必须为每个类别保留的计数统计信息。

时间复杂度:o(n)用于线性模型;也可用于非线性模型,如树

优点:

  • 训练快
  • 能够使用树模型
  • 容易扩展到新列类别
  • 容易处理稀有类别
  • 可解释

缺点

  • 需要利用历史信息
  • 对于在线学习有困难
  • 会有数据泄露

正如我们所看到的,这些方法都不完美。使用哪一个取决于所需的模型。线性模型的培训成本更低,因此可以处理非压缩表示,如一个热编码。另一方面,基于树的模型需要对所有特征进行重复搜索以获得正确的分割,因此仅限于小的表示,如bin计数。功能散列位于这两个极端之间,但是对于结果的准确性有着复杂的报告。

Just for fun!
------------- 文章已经到尾 -------------