【信息科学与工程学】【数据科学】第五十五篇 大数据算法

大数据领域算法众多涵盖不同子领域。以下表格选取了部分核心与代表性算法并按您要求的格式进行整理。编号算法/模型名称算法逐步推理思考的数学方程式 (核心)关联知识复杂度 (时间复杂度)数据类型1MapReduce​1.Map阶段:k1, v1 - list(k2, v2)2.Shuffle Sort: 按键k2分组排序。3.Reduce阶段:k2, list(v2) - list(k3, v3)分布式计算、函数式编程、容错处理O(n)取决于数据量和任务海量、非结构化/结构化批数据2PageRank​PR(pi​)N1−d​d∑pj​∈M(pi​)​L(pj​)PR(pj​)​其中PR为页面权重d为阻尼因子L为出链数N为总页面数。迭代计算直至收敛。图论、线性代数、迭代计算O(n*k)n为页面数k为迭代次数图数据 (网页链接关系)3K-Means​1. 目标函数误差平方和: (J \sum{j1}^{k} \sum{x \in C_j}x - \mu_j4Apriori​1. 支持度: Support(X)Ncount(X)​2. 频繁项集生成: 基于先验性质频繁项集的所有子集也必须是频繁的逐层搜索。3. 关联规则生成: 置信度 Confidence(X→Y)Support(X)Support(X∪Y)​关联规则、集合论、搜索算法O(2^n) 最坏情况实际通过剪枝优化事务型数据 (购物篮数据)5TF-IDF​1. 词频: TF(t,d)∑t′∈d​ft′,d​ft,d​​2. 逆文档频率: (IDF(t, D) \log \frac{N}{{d \in D: t \in d}} )3. 综合权重: TF-IDF(t,d,D)TF(t,d)×IDF(t,D)信息检索、文本挖掘、向量空间模型6Bloom Filter​1. 初始化一个长度为m、全为0的位数组。2.添加元素: 使用k个哈希函数计算元素值将对应位数组位置置1。3.查询元素: 计算k个哈希值若所有对应位均为1则“可能存在”任一为0则“肯定不存在”。概率数据结构、哈希函数、空间效率O(k)插入和查询均为常数时间任意可哈希的数据对象7梯度提升决策树 (GBDT)​1. 模型为加法模型: Fm​(x)Fm−1​(x)γm​hm​(x)2. 每一轮拟合当前模型的负梯度残差: rim​−[∂F(xi​)∂L(yi​,F(xi​))​]F(x)Fm−1​(x)​3. 通过决策树h_m(x)拟合r_{im}并计算最优步长γ_m。集成学习、决策树、梯度下降、损失函数O(nmd*log n)n样本数m树数量d特征数数值/类别型特征监督数据8Dijkstra算法​1. 初始化距离: 起点dist[s]0其余dist[v]∞。2. 循环从优先队列中取出未处理且dist最小的顶点u。3. 松弛操作: 对u的每个邻接点v若dist[u] w(u, v) dist[v]则更新dist[v]。图论、贪心算法、优先队列O(|E| |V|log |V|) (使用斐波那契堆)带权有向/无向图数据9LSH (局部敏感哈希)​核心思想: 将相似的数据点以高概率映射到同一个哈希桶中。例如对于余弦相似度随机超平面哈希函数为: h(v)sign(r⋅v)其中r是随机向量。相似向量有更高概率得到相同符号。近似最近邻搜索、概率论、度量空间O(n*L)n数据点L哈希表数量高维特征向量10流式处理 (如滑动窗口平均)​对于无限流数据维护一个固定大小W的窗口。窗口和更新: St​St−1​xt​−xt−W​当前窗口平均值: xˉt​WSt​​数据流模型、滑动窗口、实时计算O(1)每次更新为常数时间无界、有序的流数据说明“所有算法”的界定大数据领域极其广泛算法数以千计上表仅列出跨领域通用或子领域基石性的部分算法作为示例。“数学方程式”列由于篇幅限制表格中展示的是算法最核心的数学表达或计算步骤而非完整的逐步推导。完整的推导通常需要结合论文或教材。复杂度表中给出的是理论时间复杂度的渐进上界大O表示法。实际运行效率受数据分布、并行化程度、具体实现和硬件资源影响巨大。扩展领域其他重要领域如深度学习CNN, RNN, Transformer、实时计算Storm, Flink底层算子、分布式协同Paxos, Raft等均有其核心算法集受表格篇幅所限未逐一列出。编号算法/模型名称算法逐步推理思考的数学方程式 (核心)关联知识复杂度 (时间复杂度)数据类型11随机森林​1. 自助采样(Bootstrap)得到k个训练集。2. 为每个训练集构建决策树节点分裂时从随机子集中选最优特征。3. 分类任务投票回归任务平均。 f^​K1​∑k1K​Tk​(x)集成学习、Bagging、决策树、特征重要性O(k * n * log(n) * m)k树数量n样本数m特征数数值/类别型特征监督数据12支持向量机​1. 优化目标硬间隔: (\min_{w,b} \frac{1}{2}w13隐狄利克雷分布​1. 文档生成过程- 从狄利克雷分布 Dir(α)采样得到文档的主题分布 θd​。- 对文档中每个词a. 从 Multinomial(θd​)采样一个主题 zdn​。b. 从主题 zdn​对应的词分布 ϕzdn​​(来自 Dir(β)) 中采样一个词 wdn​。2. 通过吉布斯采样或变分推断求解参数。主题模型、贝叶斯推断、概率图模型O(nki)n总词数k主题数i迭代次数文本数据集合14协同过滤​1.用户-物品评分矩阵​ Rm×n​。2.基于用户的CF: 预测评分 (\hat{r}{ui} \bar{r}u \frac{\sum{v \in N(u)} sim(u, v) \cdot (r{vi} - \bar{r}v)}{\sum{v \in N(u)}sim(u, v)} )3.基于物品的CF: 预测评分 (\hat{r}{ui} \frac{\sum{j \in N(i)} sim(i, j) \cdot r{uj}}{\sum{j \in N(i)}sim(i, j)15XGBoost​1. 目标函数 损失函数 正则化项: Obj(t)∑i1n​L(yi​,y^​i(t−1)​ft​(xi​))Ω(ft​)2. 二阶泰勒展开近似: Obj(t)≈∑i1n​[gi​ft​(xi​)21​hi​ft2​(xi​)]Ω(ft​)其中 gi​,hi​为一阶和二阶梯度。3. 定义树结构求解最优叶节点权重和分裂增益。梯度提升、决策树、正则化、分布式计算与GBDT类似但工程优化极佳数值/类别型特征监督数据16Word2Vec​1.Skip-gram目标: 最大化给定中心词 wc​下上下文词 wo​的平均对数概率: (\frac{1}{T} \sum{t1}^{T} \sum{-c \le j \le c, j \ne 0} \log p(w_{tj}w_t) )2. 使用softmax: (p(w_ow_c) \frac{\exp(u{o}^T v_c)}{\sum{w1}^{W} \exp(u_{w}^T v_c)} )常通过负采样优化。词嵌入、分布式表示、神经网络、自然语言处理17Transformer (编码器)​1.自注意力机制: Attention(Q,K,V)softmax(dk​​QKT​)V其中Q, K, V由输入线性变换得到。2.多头注意力: 将多个自注意力头的结果拼接并线性变换。3.前馈网络: FFN(x)max(0,xW1​b1​)W2​b2​。4. 残差连接与层归一化。自注意力、位置编码、深度神经网络、并行计算O(n² * d)n序列长度d模型维度序列数据文本、时序18HyperLogLog​1. 将元素通过哈希函数映射为二进制串。2. 观察二进制串前导零的最大数量​ρ。3. 分桶m个取平均以降低估计误差。4. 基数估计值: Eαm​m2Z−1其中 Z∑j1m​2−M[j]M[j]为第j桶的ρ最大值。基数估计、概率统计、哈希函数、流式统计O(n)n为数据流中唯一元素数量海量数据流的独立元素计数19t-SNE​1. 在高维空间计算数据点对之间的条件概率相似度: (p_{j|i} \frac{\exp(-x_i - x_j20C4.5 (决策树)​1. 计算每个特征A的信息增益比: GainRatio(A)SplitInfo(A)Gain(A)​2. 信息增益: (Gain(A) Entropy(S) - \sum_{v \in Values(A)} \frac{S_v}{S21FP-Growth​1. 扫描数据集构建频繁项头表和FP树。2. 从FP树的叶节点项头表底部开始为每个频繁项构建条件模式基。3. 对每个条件模式基递归构建条件FP树并挖掘频繁项集。关联规则、频繁模式树、深度优先搜索O(n * p)n事务数p频繁1-项集平均长度事务型数据22KNN​1. 给定测试样本计算它与训练集中所有样本的距离如欧氏距离。2. 选取距离最近的k个训练样本邻居。3. 分类任务统计k个邻居中最多数的类别回归任务取k个邻居目标值的平均。惰性学习、距离度量、特征归一化O(n * d)查询时需计算与所有训练样本的距离数值型特征向量监督数据23AdaBoost​1. 初始化样本权重 wi(1)​1/N。2. 对于每轮ta. 训练一个弱分类器 ht​使其最小化加权误差 ϵt​。b. 计算该分类器权重 αt​21​ln(ϵt​1−ϵt​​)。c. 更新样本权重: wi(t1)​wi(t)​exp(−αt​yi​ht​(xi​))/Zt​Zt​为归一化因子。3. 最终强分类器: H(x)sign(∑t1T​αt​ht​(x))集成学习、Boosting、加法模型O(T * f(n))T迭代次数f(n)是弱分类器训练复杂度数值/类别型特征监督数据24EM算法​1.E步期望: 基于当前参数 θ(t)计算隐变量 Z的后验概率 Q(z∥x,θ(t))。2.M步最大化: 更新参数 θ(t1)argmaxθ​∑z​Q(z∥x,θ(t))logP(x,z∥θ)。3. 迭代直至收敛。最大似然估计、隐变量模型、高斯混合模型迭代算法每次迭代复杂度取决于具体模型含隐变量的不完全数据25Bellman-Ford​1. 初始化距离数组dist[]起点为0其余为∞。2. 对每条边松弛V-1次: 如果dist[u] w(u, v) dist[v]则更新dist[v] dist[u] w(u, v)。3. 再检查一次所有边若还能松弛则说明存在负权环。图论、动态规划、单源最短路径26最小哈希​1. 定义特征矩阵的行的一个随机排列。2. 对于每个集合列其最小哈希值为在该排列下第一个出现“1”的行索引。3. 使用多个随机排列生成签名矩阵。4. 两个集合的Jaccard相似度 ≈ 它们的签名向量中对应位置值相等的比例。集合相似度估计、Jaccard相似度、哈希O(n * m)n特征数m集合数但通过哈希函数模拟排列可优化集合数据如文档的词袋表示27CURE聚类​1. 对数据集进行随机采样。2. 对采样点进行预聚类如层次聚类。3. 对每个簇选取固定数量的分散的点作为代表点并将其向簇中心收缩以消除噪声影响。4. 对所有代表点进行聚类并将剩余点分配到最近的簇。层次聚类、采样、对噪声和形状鲁棒O(n² log n) 最坏采样后大幅降低数值型数据尤其对非球形簇有效28PrefixSpan​1. 扫描数据库找出所有长度为1的频繁序列。2. 为每个频繁项α构建其对应的投影数据库。3. 在投影数据库上递归地挖掘以α为前缀的更长频繁序列。序列模式挖掘、投影数据库、深度优先搜索O(n * m)n序列数m频繁模式长度序列数据如用户行为序列29SVD (奇异值分解)​将矩阵 Am×n​分解为: AUΣVT其中 Um×m​Σm×n​(对角阵)Vn×n​是酉矩阵。取前k个最大奇异值及其对应向量得到降维或近似矩阵: Ak​Uk​Σk​VkT​线性代数、矩阵分解、降维、推荐系统O(min(m²n, mn²))完整SVD截断SVD可优化任何实数矩阵如评分矩阵、词-文档矩阵30Count-Min Sketch​1. 初始化d个长度为w的计数器数组对应d个哈希函数。2.更新频次1: 对元素x计算d个哈希值 hj​(x)对每个数组j将位置 hj​(x)的计数器加1。3.查询频次: 返回 f^​(x)min1≤j≤d​count[j][hj​(x)]流数据、频率估计、概率数据结构O(d)更新和查询均为常数时间数据流中的元素如IP、搜索词总结以上补充的20个算法与之前的10个共同构成了大数据处理中机器学习、数据挖掘、实时计算和图计算等核心任务的工具箱。实际应用中需要根据数据规模、特征、业务目标和计算资源来选择和组合这些算法。