大数据分析期末复习

大数据与大数据分析简介

定义

大数据概念源于1998年，其主要问题有难获取、难组织、难处理和难理解。其定义为：

在可容忍的时间内，无法用传统IT架构和软硬件工具对其进行全生命周期的感知、传输、存储、管理、计算和服务的数据集合。其是存储、算力、网络发展的产物。

特点

体量巨大、速度极快、模态多样、高不确定

大数据分析的一般流程

数据特征化得到信息
信息知识化得到知识
知识智能化得到决策
决策反馈于数据

大数据分析的四个层次

描述性分析——诊断性分析——预测性分析——指导性分析

数据驱动的自然语言处理

长短时记忆网络LSTM

用于对长句子的切分，捕捉远距离信息，避免长期依赖问题。

LSTM的单元结构

内部状态向量和输出向量
遗忘门、输入门、输出门
- 遗忘门：用于控制上一单元的记忆对当前单元的影响。门控函数为： $f_t = \sigma (W_f \cdot [h_{t-1}, x_t] + b_f)$ 其中， $W_f$ 是权重矩阵，而 $b_f$ 为偏置向量。
- 输入门：用于更新单元状态，控制LSTM对输入的接受程度。门控函数为： $g_i = \sigma(W_i \cdot [h_{t-1}, x_t] + b_f)$ 。
- 输出门：用于确定下一个隐藏状态的值，包含了先前的输入信息。门控函数为： $g_o = \sigma(W_o \cdot [h_{t-1}, x_t] + b_f)$ 。

LSTM元件

Sigmoid门控机制：使用激活函数 $\sigma$ 将门控向量 $g$ 控制在 $[0, 1]$ 区间内。 $0$ 表示关闭， $1$ 表示打开。

使用LSTM模型时，可以使用单层或双层LSTM模型，并且选择是否采用滑动窗口机制，联接窗口内顶层LSTM单元输出。

标签推理层

使用LSTM的输出作为输入，输出得分最高的一组标签。

$s(c^{(1 : n)}, y^{1:n}, \theta) = \sum_{t = 1}^n(A_{y^{(t-1)}y^t} + y_{y^t}^t)$

循环神经网络RNN

执行流程：

将当前状态和先前隐藏状态信息组合成向量
使用tanh激活函数，形成新的隐藏状态或网络记忆

存在的问题：

短时记忆问题，在处理长文本时很容易遗忘先前的信息。
梯度消失问题，（时间是较早的）获得小梯度更新的层会停止学习。
- 梯度是用于更新神经网络的权重值。

文本分类

将一段文本划分到预定义的类别中。经过预处理——文本表示——分类器的步骤。

TestCNN

使用卷积神经网络，利用卷积核捕捉局部特征，应用于由单词的分布式表示组合成的句子表示上。

其模型结构为：预训练——卷积层——池化层——全连接层——Dropout——Softmax

Embedding 嵌入层：将句子变换为词向量矩阵，其中每一行为词向量，每一列表示特征。
Convolution 卷积层：对矩阵进行卷积操作生成特征图，提取局部特征。
MaxPooling 最大池化层：减小维度，保留主要信息。
Fully Connected 全连接层：将池化后的特征组合并用于最终的分类。
Dropout：随机丢弃一部分神经元，防止过拟合。
Softmax层：用于多分类任务，进行归一化，将全连接层的输出转换为概率分布。

文本大数据分析

文本表达

局部性表示

独热表示：用一个词表大小的向量表示一个词，每个词仅在其对应维度上为 $1$ ，其余维度为 $0$ 。适用于哈希表。

每个单词使用向量中独有且相邻的维度，单词之间是相互独立的。

分布式表示

又分为横向组合关系，即可组合的、起到不同语法作用的成分关系，通常使用文档作为上下文，例如：

隐性语义索引 LSI
概率隐性语义索引 PLSI
隐性狄利克雷索引 LDA

或纵向组合关系，即起到同样语法作用的、可相互替换的词，通常使用周边单词作为上下文，例如：

神经网络概率语言模型 NPLM
排序学习模型 C&W
上下文预测模型 Word2Vec
全局上下文模型 GloVe

分布式表示的每个单词由多个特征表示，可以编码不同单词间的语义关联。

分布式表示基于分布语义假设，即单词的语义来自于上下文，其利用上下文的关系进行横向（理解为时间上相关）和纵向（理解为位置上相关）聚合成关系模型。

具有强组合关系的词表示更相似，而具有强替换关系的词表示更不相似。

低秩逼近矩阵

找到一个秩远小于原矩阵 $C$ 的矩阵 $C_k$ ，使二者之差的F-范数最小。

F范数

$||X||_F = \sqrt{\sum_{i = 1}^m\sum_{j = 1}^n x_{ij}^2}$

即，矩阵每个元素的平方和开平方。

隐性语义索引LSI

对词项-文档矩阵 $C$ 进行SVD分解，找到它的某个低秩逼近，作为词项文档的新表示。其过程如：

进行奇异值分解，将矩阵表示为 $C = U_{m \times m} \Sigma_{m \times n} V^T_{n \times n}$ 。其中 $\Sigma$ 为对角阵。
保留 $\Sigma$ 的前 $k$ 个值，其它值置 $0$ ，即将其转换为 $\Sigma_{k \times k}$ 。
得到的低秩逼近矩阵，其一般是由实数构成的稠密矩阵。
- 其中 $U_{m \times k}$ 是相应词项的 $k$ 维表示，每一维是词项在主题空间的对应主题上的映射。
- 其中 $V_{k \times k}$ 是相应文档的 $k$ 维表示，每一维是文档在主题空间的对应主题上的映射。

每一个奇异值可以理解为一个主题维度，而其值代表该主题的相关程度，故LSI是一种主题模型。LSI解决的主要是多词一义和语义关联的问题。

神经网络概率语言模型 NPLM

NPLM通过训练一个语言模型得到单词表示，本质上是一种n-gram模型，即，假定当前词的出现仅依赖于前 $n-1$ 个词。

使用一个三层神经网络，将当前单词的前 $n - 1$ 个单词作为上文输入网络，经过一个隐藏层，在SoftMax层输出当前可能出现任何一个词的概率。

第一层由每个单词的词向量首尾拼接而成。
第二层为全连接层，包括权重矩阵和偏置向量的线性运算，以及激活函数tanh。
第三层为输出层，包括字典长度个节点，并进行归一化，这部分运算时间复杂度受词表长度影响，异常耗时。可表示为。其中：
- $U$ 是隐藏层到输出层的参数。
- $W$ 称为直连边，将输入层的数据在输出层也进行线性运算。

NPLM的核心思路是，相似的输出需要相似的输入。

排序学习模型 C&W

相对于NPLM，C&W的主要改进是同时使用了上下文，以及使用了排序损失函数对单词序列打分，其损失函数定义为 $max[0, 1-(s(w, c)-(w',c))]$ ，其中：

$c$ 表示单词 $w$ 的上下文。
$w'$ 表示将单词 $w$ 替换为一不相关的单词。
$s$ 为打分函数，分数越多说明该段文本越合理。

应尽量使正确短语得分比随机替换后的得分高 $1$ 。

上下文预测模型 Word2Vec

Word2Vec也是神经网络模型，包括CBOW(Continuous B)和SG(Skip Gram)。

CBOW模型

相对于NPLM，CBOW模型删去了中间的非线性隐层，而使用单词上下文数据进行求和等运算后形成一单值用于预测，减少了运算量。

SG模型

使用当前单词预测其前后的所有单词。

全局上下文模型GloVe

GloVe利用单词的共现信息，将全文的统计信息与句子的信息相结合，以期得到单词在语义和语句上更好的表达。使用比值捕捉词语之间的相关和不相关关系。

与Word2Vec的区别

Word2Vec使用单词的上下文信息表示单词，而GloVe是对于词-词共现矩阵进行分解而得到的词的模型。其可以体现出词之间的相似性。

共现矩阵

共现矩阵中的每个值代表：以其横坐标上的单词为中心的一定窗口内，纵坐标的单词在文本中的出现次数。

软约束

对每个单词对应的向量定义软约束 $v_i^T + b_i +b_j \approx \log X_{ij}$ 。是为了得到比值和减法的同态性关系。

其中 $v_i$ 、 $v_j$ 是单词 $w_i$ 、 $w_j$ 的向量， $b_i$ 、 $b_j$ 是单词 $w_i$ 、 $w_j$ 的偏差， $X_{ij}$ 为权重项，正比于共现次数。

损失函数

$J = \sum_{i,j = 1}^{N}f(X_{ij}) (v_i^Tv_j + b_i + b_j - \log X_{ij})^2$

其中

$f(X_{ij}) =\begin{cases}(\frac{X_{ij}}{X_{\text{MAX}}})^\alpha & \text{if } X_{ij} < X_{\text{MAX}} \\1 & \text{otherwise}\end{cases}$

用于防止只从共现率很高的单词对中学习。

句子表示

句子的传统表示方法有：

词集模型
词袋模型
TF-IDF表示

句子的分布式表示方法有：

主题模型
基于单词分布式表示组合的表示方法
由原始语料直接学习的表示方法

词集模型 Set of Words

仅考虑单词是否出现，是一个没有计数的单词集合表。

词袋模型 Bag of Words

在词集模型上加入了出现次数的考量，记录出现的单词和其对应的频数。

TF-IDF模型

全称为 Term Frequency – Inverse Document Frequency （词频-逆向文档频率）。即，使用在本文档中高频，而在其他文档中低频的词汇作为文档的分类依据，视为具有良好的类别区分能力。

TF计算公式如：

$tf_{ij} = \frac{n_{i,j}}{\sum_kn_{k, j}}$

其中 $n_{k,j}$ 是单词 $k$ 在文档 $j$ 中的出现次数。

IDF计算公式如果：

$idf_i = \log\frac{\abs{D}}{abs{{\{j:t_i\ind_j\}}} + 1}$

其中 $\abs{D}$ 是语料库中的文档总数。

TF-IDF值是二者的乘积，将词集模型中的每个单词赋TF-IDF值，便得到文档的TF-IDF表示。

基于单词分布式表示组合的表示方法

句子的分布式表示建立在单词的分布式表示基础上，其主要思想是面向具体任务，对单词的分布式表示进行组合或选择以得到一个向量作为句子的分布式表示，即特征的选取和组合。

基于卷积神经网络CNN的分布式表示

特征向量 $c_i = f(w \cdot x_{i:i+h-1} + b)$

基于循环神经网络RNN的分布式表示

其有5种表示特征的策略：

直接使用最后一个单元的输出作为特征。
使用双向RNN，拼接或均值计算特征。
将所有RNN单元的输出做池化操作，作为句子特征。
添加Attention机制，对每个时间点的输出赋予权重。
RCNN，将所有输出做一层CNN和池化操作得到特征输出。

基于递归神经网络(RecNN)的分布式表示

自底向上，遵循语法规则，最终根节点得到的向量即为该句子的表示向量。其效果依赖于输入文本的语法树，故而时间开销更大。

基于DAN(Deep Averaging Network)的分布式表示

是一种无序模型，在分类层前增加了隐藏层对句子进行特征提取以到深层次的句子表示。也可以理解为由词向量的平均进行句子的表示。

文本中的匹配问题

文本匹配是自然语言中的一个核心问题。

基于启发式规则的文本匹配

直接比较两段文本中同时出现的词，度量其匹配程度。

经典模型：BM25和查询似然模型。

基于隐语义表达的文本匹配

两段文本中同时出现的词和词与词之间的关系都提供贡献度。具体为将一段文本映射到一个向量，然后通过计算向量的相似度衡量文本的匹配度。

文本匹配的评价方法

分类准确率：用于评价分类任务，是一个二分问题，匹配为1，不匹配为0.
P@k：表示前k个文档的排序准确率。
R@k：表示前k个文档的排序召回率。
MAP：平均精度均值，即所有未知的排序准确率均值。
MRR：只考虑预测结果排序中出现的第一个相关文档位置，其倒数即为MRR值。
nDCG：归一化折扣累计收益，即对于匹配度非二分的情况，让相关度越高的排在越前面。
- 计算DCG的公式为 $rel_1 + \sum_{i = 2}^n\frac{rel_i}{\log_2(i+1)}$
- nDCG相当于预测DCG和实际DCG的比值。

知识图谱 Knowledge Graph

知识图谱本质上是一种语义网络，其节点代表实体或概念，边代表各实体之间的语义关系。

其核心是对实体之间关系的表达，提供从关系角度分析问题的能力。

知识图谱中的知识表示

三元组Triple

其结构如：

head：头实体/概念
relation：关系/属性
tail：尾实体/概念

即：head是tail的relation

知识图谱的生命周期

知识建模-知识获取-知识融合-知识存储-知识计算-知识应用

实体抽取

从原始语料中自动识别出指定类型的命名实体，主要包括实体名、缩略词和数学表达式等。

实体抽取的标注方式

BIO方式：
- Begin：实体的开头
- Inside：实体的内部内容
- Outside：实体外的内容
BIOES方式：
- Begin：实体的开头
- Inside：实体的内部内容
- Outside：非实体的内容
- End：实体的结尾
- Single：单字符的实体

基于机器学习的实体抽取方法

隐马尔科夫模型

在给定词语序列 $W$ 的情况下找到概率最大的可能标注序列 $T$ 。即：

$<span class="ql-right-eqno"> (1) </span><span class="ql-left-eqno"> </span><img src="http://www.be-a-quail.com/wp-content/ql-cache/quicklatex.com-55c070389a953de90d79462a8c6bca23_l3.png" height="44" width="447" class="ql-img-displayed-equation quicklatex-auto-format" alt="\begin{align*}T_{max} &= arg_{T}maxP(T|W)&arg_{T}max\frac{P(T)P(W|T)}{P(W)}\end{align*}" title="Rendered by QuickLaTeX.com"/>$

其中 $P(W)$ 可以视为一不相关常数，故问题转化为求 $arg_{T}max P(T)P(W|T)$ 。由于要穷举 $W$ 和 $T$ 的所有情况，该问题是 NP 难的（可以理解为时间复杂度极高）。

马尔科夫假设

马尔科夫假设是，假定当前状态只与其前一时刻状态有关。因此可以把问题化约为：

$T_{max} \approx arg_Tmax \prod_{i = 1}^n P(w_i|t_i)P(t_i|t_{i-1})$

其中 $P(t_i|t_{i-1})$ 称为转移概率，可表示为前一时刻词语出现的频数和两词依次出现的频数之比。

基于深度学习的模型：LSTM-CRF模型

其实现流程为：

Word Representation：融合词汇级和字符级特征
Bi-LSTM Encoding：编码双向语义信息
CRF Decoding：对编码信息进行解码，解决标签依赖关系

关系抽取

抽取方法分类：

基于传统机器学习的方法：
- 有监督方法、半监督方法、远程监督方法、无监督方法
基于深度学习的方法：
- 基于经典神经网络的方法、基于BERT的方法

远程监督关系抽取

通过外部知识库而非人力进行语料标注，以降低标注成本。

对共现了知识库中 $<e_1, R, e_2>$ 存在的 $<e_1, e_2>$ 对的，均标注为具有关系 $R$ 。用分类方法解决抽取问题。可能存在假设关系过强的问题。

“at-least-once”假设，认为至少有一对 $<e_1, e_2>$ 包含关系 $R$ 。引用了多实例学习机制，将任务由句子分类转化为了句袋分类，即进行了句子的聚合。

基于经典神经网络的关系抽取

有基于卷积网络、循环网络、神经网络的关系抽取方法。

基于预训练模型BERT的关系抽取

BERT的全称为基于Transformer的双向编码表征(Bidirectional Encoder
Representations from Transformers) ，是一个预训练的语言模型。

BERT采用遮盖语言模型，生成深层的双向语言表征。其通过一个额外的输出层进行微调，以满足不同的下游任务，而不需要调整BERT本身的结构。

BERT输入一个词语序列，而输出其中单词对应的向量表示。

Transformer

Tramsformer分为编码器和解码器两部分，是典型的序列编码模型。具体来说其执行步骤为：

将输入内容进行嵌入，即向量化表示。
然后，通过正弦/余弦运算为其添加位置信息编码。输入编码=词汇编码+位置编码。
经过多层编码器和解码器输出。
输出的序列由每个单词在序列中的表示加权得到。

多头注意力机制

多头注意力是由多个缩放点积注意力组成，将每个头的注意力的输出进行拼接得到输出向量。

通过多个自注意力机制进行特征提取。自注意力中的Query、Key、Value可以理解为线性层变换，通过 $Attention(Q, K, V) = softmax(\frac{QK^T}{\sqrt{d_k}})V$ 计算出一注意力值。

Linear是一个线性层，合并多个自注意力结果。自注意力计算的意义是将全局信息附加到每一个单词上。

Bert

Bert使用多个Transformer编码器堆叠而成。其训练任务包括：

单词预测：使用词典大小的多分类器预测被遮盖的单词。
下一句话预测：通过二分类器预测，与单词预测同时进行。

可以用于情感分类、文档分类、命名实体识别等任务。

R-BERT

是基于Bert的关系抽取模型。其输入的句子中含有两个待抽取关系的目标实体，在目标实体前后加入标记，然后将整个句子送入Bert。Bert输出的结果中会有整个句子和该两个目标代表的隐向量，使用这些隐向量进行关系分类。

三个部分的输出向量进行拼接并输入全连接层中，最后通过交叉熵进行分类。

知识推理

利用已知信息推断出未知信息的过程。

基于分布式表达的知识计算

包含张量分解方法、基于翻译的方法和神经网络方法。

基于分布式表达的推理

TransE

其基本思想是把关系看作是头尾实体之间的平移(翻译)操作，即三元组中的R表示一种平移关系，满足向量加法的三角形原则。

势能函数 $f(h, r, t) = f_r(h, t) = ||h+r-t||_2$ ，越小则越趋近于正确，要求对于事实，势能函数为0.

损失函数为：

$L = \sum_{(h, r, t) \in \triangle} \sum_{(h, r, t) \in \triangle ' max (0 ,f_r(h, t) +M_{opt} -f_r(h', t'))}$

其中 $\triangle$ 为三元组集， $M_{opt}$ 为最优Margin超参。

关系多样性问题

知识图谱存在一对一、多对多等问题。

Trans系列

TransH：每个关系对应一个超平面，实体在这个平面上进行嵌入。
TransR：允许实体和关系在不同的空间中进行嵌入。
TransA：自适应地决定不同知识图谱的边界超参，使得模型在处理具有多样化关系和属性的知识图谱时表现得更加灵活和有效。

$M_{opt}$ 的问题在于，需要事先考虑特定的候选集，以及不同的知识图谱共享相同的候选集。

TransA的边界超参

其计算方式为 $M_{opt} = \mu M_{ent} + (1 - \mu) M_{rel}$ 。

实体依赖的边界超参

关系依赖的边界超参

大数据分析技术与系统

可扩展算法

算法的扩展性指其时间复杂度的增长性，表示为： $Scalablity_A(N) = \frac{T_A(n)}{n}$ 。当存在常数 $c$ 使 $Scalablity_A(N) = O(log_cn)$ 时，称算法为可扩展的。

特别地，当 $c = 0$ 时算法为线性可扩展的，指算法的运行时间在增加输入规模时保持不变。而当 $A(N) = O(1)$ 时，算法是超可扩展的。

数据分析算法

数据分析算法的特性：

以优化(optimization)为中心
多轮迭代直至收敛
算法目标为最优：没有确定答案(最优点往往无法达到)

传统算法的特性：

以操作(operation)为中心
确定性算法
目标为正确答案：有一个或者多个确定的答案

参数更新方案

同步更新

Bulk Synchronous Parallel (BSP)

每一轮迭代至少设置一个同步点，等候所有节点完成任务，并统一更新参数，再进行下一轮迭代。其在最大程度上模拟了序列计算，具有保障性。

异步更新

完全没有参数同步，存在参数依赖和参数过期等问题。

半同步更新

Stale Synchronous Parallel (SSP)

通过规定执行最快和最慢节点间轮数的最大差异，在一定可容忍的错误率下执行更新。其比同步快而比异步更加准确。

MapReduce

MapReduce的执行分为三个步骤：

Map：对每个词生成计数为1的键值对
Shuffle/Sort：将相同单词的键值整理到一起
Reduce：进行计数，得到每个单词出现的频数

MapReduce得到的结果可以视为词袋模型。

算法的时间开销

注意：这时大O记法不适用。

通信开销：所有进程的IO
过程开销：所有路径上最大的进程开销
运算开销：计算除IO外的运算时间

大数据统计分析

文档相关性分析

第一步 Shingling

将文档视为一个字符串，k-shingling，又称为k-gram，即其中长度为k的子串。由此可以将文档表示为子串集合。

第二步 Min-Hashing

首先将行号随机重新排列，然后得到每一列的最小哈希值是其在排列转换后的行排列次序下第一个列值为1的行的行号。

第三部 LSH（局部敏感哈希）

把原来高维空间上的点都映射到一个或多个哈希表的不同的位置上，使原先在高维空间中接近的点以很大概率被分到一个桶中。

LSH的具体做法是在Min Hashing所得的signature向量的基础上，将每一个向量分为几段，称之为band。
其基本想法是：如果两个向量的其中一个或多个band相同，那么这两个向量就可能相似度较高；相同的band数越多，其相似度高的可能性越大。

Count-Min Sketch

CMS是一种计数算法，通过牺牲准确率来提升效率。