这是Databricks和Uber Engineering之间的一篇跨博客文章。Yun Ni是Uber机器学习平台团队的软件工程师，Kelvin Chu是Uber复杂数据处理/讲话团队的技术首席工程师，Joseph Bradley是Databricks机器学习团队的软件工程师。全球用户每天都有500万次Uber旅行，因此Uber工程师必须确保数据的准确性。如果使用正确，元数据和聚合数据可以快速检测平台滥用，从垃圾邮件到假帐户和支付欺诈。放大正确的数据信号可以使检测更精确，从而更可靠。为了解决我们系统和其他系统中的这一挑战，Uber工程和Databricks合作为apachespark2.1贡献了局部敏感散列（LSH）。LSH是一种随机算法和散列技术，常用于大规模机器学习任务，包括聚类和近似近邻搜索。在本文中，我们将演示Uber如何使用这个强大的工具来大规模检测欺诈旅行。为什么是LSH？在Uber Engineering实施LSH之前，我们使用N^2方法筛选行程；虽然准确，但N^2方法对于Uber的规模和规模来说，最终过于耗时、大量且依赖硬件。LSH的一般思想是使用一系列函数（称为LSH族）将数据点散列到bucket中，使得彼此相邻的数据点以很高的概率位于同一个bucket中，而相距较远的数据点则可能位于不同的bucket中。这使得识别具有不同程度重叠的行程变得更加容易。作为参考，LSH是一种多用途技术，有多种应用，包括：近似重复检测：LSH通常用于对大量文档、网页和其他文件进行重复数据消除。全基因组关联研究：生物学家经常使用LSH来识别基因组数据库中相似的基因表达。大规模图像搜索：Google使用LSH和PageRank来构建他们的图像搜索技术VisualRank。音频/视频指纹：在多媒体技术中，LSH被广泛用作a/V数据的指纹技术。优步的LSHUber的主要LSH用例是基于空间属性检测类似的出行，这是识别欺诈司机的一种方法。Uber工程师在2016年Spark峰会上介绍了这个用例，他们讨论了我们团队在Spark框架中使用LSH的动机，以广播加入所有旅行并筛选欺诈的旅行。我们在Spark上使用LSH的动机有三个：Spark是Uber运营不可或缺的一部分，许多内部团队目前使用Spark进行各种类型的复杂数据处理，包括机器学习、空间数据处理、时间序列计算、分析和预测，以及特别的数据科学探索。事实上，Uber几乎在YARN和Mesos上使用了几乎所有的Spark组件，如MLlib、Spark SQL、Spark流和直接RDD处理；因为我们的基础设施和工具都是围绕Spark构建的，我们的工程师可以轻松地创建和管理Spark应用程序。Spark使得在进行任何实际的机器学习之前进行数据清理和特征工程是非常有效的，使得数字处理变得更快。Uber收集的大量数据使得用基本方法解决这个问题变得不可扩展且非常缓慢。我们不需要这个方程的精确解，所以不需要购买和维护额外的硬件。在这种情况下，近似值为我们提供了足够的信息来判断潜在的欺诈行为，在这种情况下，它足以解决我们的问题。LSH允许我们用一些精度来换取大量的硬件资源。基于这些原因，通过在Spark上部署LSH来解决这个问题对于我们的业务目标来说是正确的选择：scale、scale和scale。在高层次上，我们使用LSH的方法有三个步骤。首先，我们为每个行程创建一个特征向量，将其分解为大小相等的区域段。然后，利用MinHash对Jaccard距离函数进行向量散列。最后，我们要么批量进行相似性连接，要么实时进行k近邻搜索。与检测欺诈的基本暴力方法相比，我们的数据集使Spark作业更快地完成整个数量级（从使用N^2方法的大约55小时到使用LSH的4小时）。简易教程为了最好地演示LSH是如何工作的，我们将通过一个在wikipediaextraction（WEX）数据集中使用MinHashLSH的示例来查找类似的文章。每个LSH族都链接到其度量空间。在Spark 2.1中，有两个LSH估计器：欧氏距离的bucketedradandomprojectionshMinHashLSH用于Jaccard距离在这个场景中，我们将使用MinHashLSH，因为我们将使用单词计数的实值特征向量。加载原始数据在建立了Spark集群并安装了WEX数据集之后，我们根据集群大小将WEX数据的样本上传到HDFS。在sparkshell中，我们将样本数据加载到HDFS中//从HDFS读取RDD进口org.apache.spark网站.ml.特征._进口org.apache.spark网站.利纳格._进口org.apache.spark网站.sql.types._值df=spark.read.option（"分隔符"，"\t"）.csv（"/user/hadoop/测试数据.tsv")已用DFVAL=数据框选择（col（"c1"）.as（"title"）、col（"\u c4"）.as（"content"））。过滤器（col（"content"）！==空）数据流显示()图1:Wikipedia文章用标题和内容表示。图1显示了前面代码的结果，按标题和主题显示了文章。我们将使用这些内容作为哈希键，并在下面的实验中大致找到类似的Wikipedia文章。准备特征向量MinHash是一种非常常见的LSH技术，用于快速估计两个集合之间的相似程度。在Spark中实现的MinHashLSH中，我们将每个集合表示为一个二进制稀疏向量。在这一步中，我们将把Wikipedia文章的内容转换成向量。使用下面的功能工程代码，我们将文章内容拆分为单词（Tokenizer），创建单词计数的特征向量（CountVectorizer），并删除空项目：//标记wiki内容val tokenizer=new tokenizer（）.setInputCol（"content"）.setOutputCol（"words"）val字df=标记器转换（数据流）//每个wiki内容的矢量字数计数val词汇大小=1000000val cvModel:CountVectorizerModel=new CountVectorizer（）.setInputCol（"words"）.setOutputCol（"features"）.setVocabSize（vocabSize）.setMinDF（10）.fit（wordsDf）val isNoneZeroVector=udf（{v:Vector=>v.numNonzeros>0}，数据类型.布尔类型)val矢量DDF=cvModel.transform（wordsDf）.filter（isNoneZeroVector（col（"features"））。选择（col（"title"），col（"features"））矢量显示()图2：在对代码进行功能工程之后，Wikipedia文章的内容被转换成二进制稀疏向量。拟合和查询LSH模型为了使用MinHashLSH，我们首先使用以下命令在特征化数据上拟合MinHashLSH模型：val mh=new MinHashLSH（）.setNumHashTables（3）.setInputCol（"功能"）.setOutputCol（"哈希值"）val模型=mh.配合（矢量DDF）我们可以使用LSH模型进行多种类型的查询，但在本教程中，我们首先对数据集运行一个特征转换：模型.转换（矢量DDF）.show（）这个命令为我们提供了散列值，这些散列值对于手动连接和特性生成非常有用。图3:MinHashLSH将添加一个新列来存储散列。每个散列都表示为一个向量数组。接下来，我们运行一个近似的最近邻搜索来找到离目标最近的数据点。为了便于演示，我们搜索内容与短语"美国"大致匹配的文章。val键=向量.稀疏（声音大小，顺序((cvModel.词汇表.indexOf（"联合"），1.0(cvModel.词汇表.indexOf（"州"），1.0）值k=40model.approxNearest nearchneighbors模型（vectorizedDf，key，k）.show（）图4：近似近邻搜索发现维基百科中与"美国"相关的文章最后，我们运行一个近似相似度连接，以在同一个数据集中找到相似的文章对：//自连接val阈值=0.8model.approxSimilarityJoin（vectorizedDf，vectorizedDf，threshold）.过滤器（"distCol！=0"。显示（）在使用self-join的同时，我们还可以连接不同的数据集以获得相同的结果结果。图5： 近似相似性连接列出类似的Wikipedia文章，设置哈希表的数量。图5演示了如何设置哈希表的数量。对于近似相似连接和近似最近邻命令，可以使用哈希表的数量来权衡运行时间和误报率（或放大率）。增加哈希表的数量将增加准确性（正），但也会增加程序的通信成本和运行时间。默认情况下，哈希表的数量设置为1。为了获得在spark2.1中使用LSH的更多实践，您还可以在Spark发行版中为BucketRandomProjectionLSH和MinHashLSH运行较小的示例。性能试验为了衡量性能，我们在WEX数据集上对MinHashLSH的实现进行了基准测试。使用AWS云，我们使用16个执行器（m3.xlarge实例）对一个WEX数据集样本执行近似近邻搜索和近似相似性连接。图6:numHashTables=5时，近似最近邻的运行速度比完全扫描快2倍（如右图所示）。当numHashTables=3时，近似相似性联接比完全联接和过滤器（如左图所示）快3-5倍。在上面的表中，我们可以看到，在哈希表的数量设置为5的情况下，近似最近邻的运行速度比完全扫描快2倍，而近似相似性连接的运行速度要快3-5倍，这取决于输出行和哈希表的数量。我们的实验还表明，尽管这些算法运行时间短，但与作为地面真实情况的暴力方法的结果相比，它们获得了较高的精度。同时，对于返回的40行，近似最近邻搜索达到了85%的准确率，而我们的近似近邻搜索与之相似