CS-246[大数据挖掘]

CS246: Mining Massive Data Sets

大数据挖掘

• 课程网站：CS246: Mining Massive Data Sets Winter 2024
• 概要：用于分析大数据[Massive Data]的数据挖掘和机器学习算法。
• 课程版本：24Winter 学习时间：24Fall
• 本博客记录自己的学习过程以及用于复习和回顾。

• 课程重点将放在MapReduce和Spark作为创建可以处理大量数据的并行算法的工具。
• 主题包括：频繁项目集和关联规则、高维数据中的近邻搜索、局部敏感散列（LSH）、维度减少、推荐系统、聚类、链接分析、大规模监督机器学习、数据流、结构化数据挖掘网络、网络广告。

Section0：Intruduction

• 本课程主要涉及数据挖掘，即对数据的分析；绝大多数涉及机器学习技术

• 主要课程内容可以划分为几个模块：

Section1： MapReduce and Spark

分布式计算

• 解决大规模数据计算的问题
• 在不同的节点进行数据的存储和计算
• 数据存储：分布式文件系统（GFS【Google】、HDFS【Hadoop】）
• 分布式计算模型：MapReduce、Spark

MapReduce

• 主要的三个步骤：Map、Group by key、Reduce、
• Map：对每一个Item/entry 使用Mapper进行映射为一个 key-value pair，键值对的含义具体由应用制定；
• Group by key：使用key对所有键值对进行排序；
• Reduce：对同一个Group内的键值对进行规约操作。

• 例子：词频统计（将词汇作为key，词频作为value；Group by key将相同词排序在一起；Reduce进行合并）

• MR过程如何进行分布式多机计算？并行进行Map后，在Group阶段每台机器收集各自的pair进行规约。

Spark：对MapReduce的扩展

• MapReduce存在什么问题：

  • 性能瓶颈：为了节约内存，使用硬盘[以及文件系统]进行存储和读写，由于数据复制、磁盘I/O和序列化，MapReduce会产生大量开销（Mapper从disk读进行映射，写回disk；然后Reducer又要从disk读取进行规约，再写回）
  • 运用困难：Map-Reduce的逻辑有时无法运用到一些大数据计算的任务中；（强编程范式，比较死板）
  

• Spark内存计算，速度性能由于MR；Spark支持除了Map和Reduce更多高阶操作；Spark开发难度低（高阶API）

• 什么是Spark？四个主要接口

• 核心数据结构： Resilient Distributed Dataset (RDD) 弹性分布式数据集
  • 什么是弹性？什么是分布式？

• Spark使用Scala语言开发，支持其他例如 Java/Python 等语言。
• 例如：RDD in 词频统计

• 如上所示，可以看到Spark的 RDD的数据流是一个DAG（有向无环图）。
  • 有利于数据恢复（当某一计算节点失效只需回复到上一阶段，而无需重新从头开始），这就是弹性。
• RDD支持两种操作：Transformations 以及 Actions

MapReduce应用

• 数据库表连接操作：

Section2：Frequent Itemsets Mining & Association Rule

频繁项集挖掘 和 关联规则

概念解析：

Items and baskets 是数据挖掘中一个常见的概念，尤其是在市场篮分析（Market Basket Analysis）中。这些术语通常用于描述消费者购买行为或其他事务性数据。以下是这些概念的详细解释：

1. Items（项目）

• 定义: 项目（Items）指的是单个的产品、商品或对象。在市场篮分析中，项目可以是任何可以被购买或交易的东西。例如，在超市里，一个项目可以是牛奶、面包、鸡蛋等商品。
• 例子
  • 在电子商务网站中，项目可以是用户可以购买的各种商品，如手机、书籍、衣服等。
  • 在音乐流媒体服务中，项目可以是不同的歌曲、专辑或艺术家。

2. Baskets（篮子）

• 定义: 篮子（Baskets）是指一组项目的集合，通常表示一次交易或购买行为。在市场篮分析中，每个篮子代表一位顾客在一次购物中所购买的所有项目。
• 例子
  • 在超市购物中，篮子可以表示一个顾客在一次购物中购买的所有商品，如 {牛奶, 面包, 鸡蛋}。
  • 在在线购物中，篮子可能表示用户在一次交易中购买的所有物品，如 {手机, 充电器, 耳机}。
  • 在图书馆的借阅记录中，篮子可以表示一个读者一次借阅的所有书籍。

市场篮分析（Market Basket Analysis）: 通过分析顾客的购物篮（baskets），发现哪些项目（items）经常一起购买。例如，超市可能会发现牛奶和面包经常一起被购买，于是可以在促销活动中捆绑销售这些商品。

• Items 和 Baskets 都是抽象的，在不同的应用场景中有不同的含义。

Frequent Itemsets Mining

• 频繁项集是指在交易数据库中频繁出现的一组项目。简单来说，频繁项集是那些在多个事务中共同出现的项目组合。
• 一个项目集的频繁程度通常通过它的支持度（Support）来衡量。支持度指的是在所有交易中，包含某个项集的交易所占的比例（或者绝对数量）。
• 频繁项集挖掘的目标是找到所有的项集，这些项集的支持度至少达到预先定义的最小支持度阈值（Minimum Support Threshold）。

Association Rule

• 关联规则用于揭示频繁项集之间的强关联关系，通常表示为$A \Rightarrow B$，意思是“如果 A 发生，那么 B 也很可能发生”。
• 关联规则由两部分组成：前件（Antecedent，A）和后件（Consequent，B），它们都是频繁项集。

评价指标

• 支持度（Support）: 一个规则的支持度是前件和后件共同出现的概率。它表示了整个数据库中该规则适用的程度。
  $\text{Support}(A \Rightarrow B) = P(A \cup B)$

• 置信度（Confidence）: 置信度衡量了在前件发生的情况下，后件发生的概率。
  $ \text{Confidence}(A \Rightarrow B) = P(B|A) = \frac{\text{Support}(A \cup B)}{\text{Support}(A)} $

• 存在什么问题？当$P(B)$较大时，置信度虽然很高，但是没有实际意义。

• 解决：兴趣度（Interest）
  $Interest(I→j)=conf(I→j)−P(j)=∣P(j∣I)−P(j)∣$

• 兴趣度使用绝对值的意义在于 判断其正相关关系或者是负相关关系。

如何找到关联规则？

• 如下是一个例子：

1. 定义阈值信息。
2. 首先找到所有的频繁项集（这里可以筛选掉一些非最大化的频繁项，具体的方法之后详细给出）
3. 根据如下式子，进行关联规则的生成。（在每一个频繁项中，挑选其子集进行判断和生成）

• Step2 中需要找到所有的频繁项集，如何实现？
  • 朴素的暴力算法实现的话，以寻找两个item大小的频繁子集问题为例，需要两次循环遍历计算每一个pair的出现次数。
  • 当 Baskets 的items的数量过大，内存无法容下。（内存问题）

A-priori 算法

• 基于一个思想：即如果一个item的出现次数都没有超过阈值，那么不可能有频繁项集包含该item。
• 所有的出现次数超过阈值的单个item称为frequent item，任何频繁项集只能由这些freq. item组成。
• 算法流程：逐步的过滤和构造

• 从freq. item（size=1），逐渐构造更大size的item set；

更多算法

• 更多的频繁项集挖掘的算法包括：随机采样Backets的子集进行寻找、分块载入内存进行查找

Section3: Locality-Sensitive Hashing

• 一种最近邻算法

• 局部敏感哈希，一种用于高维数据的近似最近邻搜索的技术。

• 主要目标：将高维空间中的相似数据点映射到同一个桶（bucket）中，以便快速发现相似的项。

文档相似性检测

• 如下图所示，文档相似性检测是一个经典的任务；在文档数量极大的前提下，如果两两比较开销巨大。

如何定义文档之间的相似性？

• 将文档视为一个集合，定义集合之间的相似度使用 Jaccard similarity

• 进行文档相似性检测的三个典型的步骤和模型图如下图所示（其中第三步使用了LSH）。

• 三个步骤：

  1. Shingling（n-gram特征提取）

     定义: Shingling是将文档转换为一个集合表示的过程，这个集合由文档中的特征（通常是n-gram或k-shingle）构成。

     • n-gram: 指文档中连续的n个字符或n个单词序列。例如，对于文本 “chatgpt is cool”，若n=3的字符shingle包括 “cha”, “hat”, “atg”, “tgp”, “gpt”, “pt “, “t i”, “ is”, “is “, “s c”, “ co”, “coo”, “ool”。

     • 集合表示: 每个文档都可以被表示为这些n-gram的集合。通过这种方式，不同文档中相同的n-gram可以反映它们之间的相似性。这种集合表示可以转换为布尔向量，其中向量的每一维表示一个n-gram是否存在于文档中。

     目标: 将文档表示为一个n-gram集合，以捕捉文档中局部的字符或词的相似性。通过这种表示，可以进一步进行相似性计算。

     优点包括：改变单个word只会影响其周围最多距离为1的特征；非常直观，具有相似内容的文档会有相同的n-gram特征。

  2. Min-Hashing

     定义: Min-Hashing是一种哈希技术，它将大的集合（如shingles集合）转换为短的签名（signature），同时保留集合之间的相似性特征。

     • 过程: Min-Hashing使用多个哈希函数，对每个文档的shingle集合进行哈希。对于每个哈希函数，它选择哈希值最小的shingle作为文档的“最小哈希值”（min-hash）。通过使用多种不同的哈希函数，可以为每个文档生成一个签名，即一个哈希值的向量。

     • 保留相似性: 如果两个文档相似，它们的shingle集合有较大的重叠，那么它们在多个哈希函数下得到相同最小哈希值的概率也会较高。因此，通过比较签名，可以近似地衡量两个文档之间的相似性。

       （低维度的签名能够保持相似性的原因如下图公式所示，假设其中的哈希函数$h_{\pi}$是一个序列变换，那么在进行序列变换后能够保持相同的概率即为其相似性）

       

     目标: 将大的shingles集合转换为较短的签名，减少数据规模，同时保持文档之间的相似性特征。这使得在大规模数据集中进行相似性比较更加高效。

     • 如下图所示，Min-Hashing中的哈希函数使用的是Permutation序列变换；对于一个特定文档，例如matrix中的一列，运用一个序列变换后的最小的1值可以表征这个哈希函数对这个文档转换后的值。所以一个文档可以表征为#permutation维度的签名向量。
     • 从而实现一个 shingles集合bool向量转换为一个低维的签名的降维。
     

  3. Locality-Sensitive Hashing (LSH)

     

     定义: LSH 是一种哈希技术，专注于将相似的签名（signature，签名在第二步min-hashing中已经实现）映射到同一个桶（bucket）中，使得相似的文档有更高的概率成为候选对（candidate pairs）。

     • 过程: LSH使用多组哈希函数，将Min-Hashing生成的签名映射到不同的桶中。每组哈希函数根据签名的不同部分进行哈希，以此确保相似的签名映射到相同桶中的概率较大。不同组哈希函数可以组合使用，进一步提高准确性。

     • 候选对: 通过LSH，将落在同一桶中的签名视为候选对。这些候选对可能来自相似的文档，因此只需对这些候选对进行进一步精确的相似性计算，而无需对所有文档进行两两比较。

     目标: 使用LSH，快速找到可能相似的文档对，大幅减少需要进行精确相似性计算的对数，从而提高大规模相似性检测的效率。

     如何处理min-hash矩阵？

     • 需要将min-hash矩阵划分为一个个band，对这些band进行单独的哈希映射。
     
     • 图解：
     

LSH算法误差

• LSH算法是一个近似算法，不可避免的存在误差和错误。可以从概率的角度进行解释。
• 误差主要体现在两类错误上：误判（false positives）和漏判（false negatives）。

漏判（false negatives）

• 1. 目标是找到相似度大于0.8的doc pair，其中每一个bond有5行，一共有20个bonds。
  2. 假设文档C1和C2在相似性为0.8的前提假设下，计算漏判false negatives的概率如下所示：（即计算两个文档在20个bonds中没有任何一个bond被划分入同一个bucket的概率）
  3. 概率：即只有0.035%的概率存在漏判的可能。
  

误判（false positives）

• 1. 假设文档C1和C2在相似性为0.3的前提假设下，计算误判（false positives）的概率如下所示：（即计算两个文档在20个bonds中存在任何一个bond被划分入同一个bucket的概率）
  2. 概率：有4.74%的可能性存在误判。

抉择（Trade off）

• 通过调整 #band 以及 rows per band 可以调整 false positives 以及 false negatives 的概率。
• 但是这是一个trade off。
• 当降低#band时，rows per band 会上升，那么两个文档完全相同的可能性就会减少。那么FN概率显然上升，FP概率显然下降。

参数选择是一个重点

• 调整$b、r$ 来得到一个在指定的相似性阈值下的高效模型。

• 理想curve 以及 实际 curve 如下图所示：

Section3.5: Theory of LSH

如何理解LSH的 Locality-Sensitive？

• 位置敏感，核心是位置（也解释points之间的距离）。如果两个对象在原始空间中距离足够接近，那么它们在散列空间中也有很高的概率被映射到相同的散列桶中。

• 重点内容：这是一个LSH的常用定义。

• 例如：Min-Hash的位置敏感性如下：

• LSH在上述的内容用于文档的相似性检测，更加广泛地说：用于在一个巨大的稀疏矩阵中，找到Jaccard相似性高的columns

• 事实上，是一种 距离检测（使用的是Jaccard距离，即：

• 如何将LSH泛化到其他类型的距离？例如欧拉距离、cos距离等等。

LSH For Cos-distance：Random Hyperplanes

• 随机超平面 vs Min-Hash

• Random Hyperplanes 是一种用于 Locality-Sensitive Hashing (LSH) 的技术，主要应用于高维空间中的相似性搜索，特别是用于处理点之间的余弦相似度（Cosine Similarity）。其核心思想是利用随机生成的超平面将数据点划分到不同的区域，从而实现对数据点的分类和相似性判断。

工作原理

1. 定义超平面：在 ( d ) 维空间中，一个超平面可以由一个法向量（即垂直于超平面的向量）来表示。通过随机生成多个法向量，我们可以定义多个超平面。

2. 投影和分类：对于每个数据点，将其投影到由超平面定义的空间中。具体来说，计算数据点和超平面法向量的内积：

   • 如果内积为正，则认为该点在超平面的“正”侧。
   • 如果内积为负，则认为该点在超平面的“负”侧。

3. 生成哈希签名：通过多个随机超平面来定义一组哈希函数，每个超平面对数据点产生一个比特值（正侧记为1，负侧记为0）。将这些比特值组合起来就得到了一个签名或哈希码。相似的点在这些超平面下有更高的概率生成相同的哈希码。

4. 相似性判断：在查询时，将查询点通过相同的超平面集合进行哈希，得到哈希码。然后在哈希空间中查找具有相同或相似哈希码的点，从而实现高效的相似性搜索。

余弦距离

• 两个高维数据点之间的余弦距离就是两个向量之间的夹角(0-180度)

• 重点：将x和y哈希到随机超平面的同一边的概率 就是 其余弦相似性。

• 证明：只有随机超平面在两个向量之间的时候hash为-1，否则是+1；概率为$d(x,y)/\pi$

LSH For Euclidean Distance：Line Projection

• 主要的是思想是：哈希函数使用随机选择的一条直线， 将数据点投影到该直线。在直线上定义散列桶，越接近的数据点散列到同一个桶的概率更高。

主要的步骤：

1. 随机投影：选择一个随机方向（向量），即从一个高斯分布中随机抽取一个向量。这个随机向量用来定义一条投影线。
2. 计算投影值：对于每个数据点，将其投影到这个随机向量上。计算该点在随机向量上的投影值，即点与随机向量的内积。
3. 分配散列桶：将这些投影值划分为若干区间，每个区间对应一个散列桶。数据点根据它们的投影值落入相应的桶中。
4. 重复多次：由于单一的随机投影不足以可靠地区分点的距离关系，因此通常会重复多次，使用多个随机投影向量，并组合它们的结果来形成最终的散列签名。