推荐系统
线上服务
Redis
召回层
快速筛选掉与目标推荐不相关的Item
单策略召回
多路召回
Embedding召回
局部敏感哈希:在常数时间内搜索到Embedding最近邻
上一节中的Embedding召回方法是通过简单的线性方法逐一计算各个Embedding之间的相似度，显然会带来极大的服务延迟。 在高并发的工业级推荐系统中，必须要优化召回层的执行速度，将时间复杂度从$O(k \times n)$(k为Embedding向量空间的维度，n为物品总数)降低到可以承受的范围里。
现在问题转化为在向量空间中以最快速度搜索与目标Item的Embedding最近邻的过程。传统近邻搜索有“聚类”和“索引”两种方法，但都不适合Embedding空间的情况。
聚类
聚类的思想是把相似的点聚类到一起，在目标点周围快速寻找最近邻。
K-means算法是比较经典的聚类算法，步骤如下：
- 随机指定k个中心点
- 这k个中心点代表k个类，将所有点按照距离的远近指派给与其距离最近的中心点
- 指派完毕后，计算每个类包含的点的平均值并将其作为新的中心点位置
- 新的中心点位置确定后，转2，继续迭代，直至中心点的位置收敛，不再移动
假设将其应用在推荐系统中，就需要我们在离线计算每个Embedding向量的中心点(类别)，线上应用时搜索与其同一类别的Embedding向量即可，照此思想可以大大缩小Embedding的搜索范围，就可以降低搜索的时间复杂度。
但是，边界情况是推荐系统不得不考虑的问题，处于聚类边缘的点的最近邻往往包括相邻聚类的点，如果只在同一类别中进行搜索，就会遗漏这些处于不同类别里的近似点，同时也会落入信息茧房之中。此外，算法开始时的k也不是一个可以很好衡量的参数，如果k选取得过大，离线迭代时速度就会非常缓慢，而k选得过小，在线搜索时，同一类别中的Embedding向量还是很多，并没有大幅减少搜索时间。所以基于聚类的最近邻搜索仍是有一定局限性，为了解决上述问题也会增加冗余过程，得不偿失。
索引
Kd-tree(K-dimension tree)是一种经典的向量空间索引方法，与聚类不同的是它为向量空间中的点(向量)建立一个索引。
Kd-tree的思想在于把高维空间的点分割进独立的空间片区中，直至每个片区中只有一个唯一的点(或者直至所有结点中包含的数据项数量小于等于给定的阈值，比如2)。完成空间索引的构建之后，将这些点放入二叉树中。
二叉搜索树其对应的数据集可以看做一个一维空间，因为其数据集的每一个数据条目都是由单一数值构成，二叉搜索树的分割依据就是按照数值的大小。同理，如果能在多维欧式空间中构建一颗类似原理的BST，那么完成搜索目标的时间复杂度也会大大减小。
多维空间中的数据条目由多个数值组成，如何使用类似BST的方法进行比较呢？Kd-tree选择其中某一个维度进行比较，并根据这个维度进行空间划分。依据所选取的维度，每一次切割都尽量要使数据集一分为二，而每次切割时选择的数据项要以选取维度上对应数值的中位数为标准，使其产生的两个子集可以放入二叉树结点的左右儿子中。如此多次切割直至不能再划分时，形成的二叉树的叶子节点中包含对应的数据条目(向量空间中的点)。
如果在这样的一颗二叉树上寻找某个点的最近邻，只需找其兄弟结点，若数量不够还可以继续向上搜索父结点的兄弟结点的儿子们(即堂兄弟结点)，根据二叉树的性质，这样搜索的速度自然很快。
但是，其边界情况仍是推荐系统不得不考虑的问题。比如，在空间中实际距离更近的点q和点p因为分割的问题，两者不处于树上最近邻的位置(不是兄弟结点甚至不是堂兄弟的关系)。所以按照Kd-tree的索引方法可能仍会遗漏最近邻点，只能保证快速搜索到近似的最近邻点集合。此外，Kd-tree的数据结构和维护过程也较为复杂，弊端较多，不太适合在性能方面推荐系统。
局部敏感哈希
相比于聚类和索引等近邻搜索方法，局部敏感哈希(Locality Sensitive Hashing, LSH)用它的简洁高效完美handle了召回层的需求。
-
基于And操作，能够进一步减少候选集规模，增加计算效率
-
基于Or操作，能够提高召回率，减少遗漏最近邻点的可能性
在前述使用过的数据集上应用局部敏感哈希
from pyspark.ml.feature import BucketedRandomProjectionLSH
from pyspark.ml.linalg import Vectors
# 局部敏感哈希，使用多桶策略保证在常数时间内可以搜索到目标Item的Embedding最近邻，作为召回层生成候选列表
# 使用Spark MLlib的LSH分桶模型:BucketedRandomProjectionLSH
def embeddingLSH(spark, movieEmbMap):
movieEmbSeq = []
for key, embedding_list in movieEmbMap.items():
embedding_list = [np.float64(embedding) for embedding in embedding_list]
movieEmbSeq.append((key, Vectors.dense(embedding_list)))
# 数据集准备，创建一个DataFrame
movieEmbDF = spark.createDataFrame(movieEmbSeq).toDF("movieId", "emb")
# 利用Spark MLlib 自带的分桶局部敏感哈希模型，其中numHashTables参数设定的是一个Embedding对应的桶数，即分桶函数的数量
bucketProjectionLSH = BucketedRandomProjectionLSH(inputCol="emb", outputCol="bucketId",
bucketLength=0.1, numHashTables=3)
bucketModel = bucketProjectionLSH.fit(movieEmbDF)
embBucketResult = bucketModel.transform(movieEmbDF)
print("movieId, emb, bucketId schema:")
embBucketResult.printSchema()
print("movieId, emb, bucketId data result:")
embBucketResult.show(10, truncate=False)
print("Approximately searching for 5 nearest neighbors of the given sample embedding:")
# 给定一个Embedding向量，将其转换为Dense Vector
sampleEmb = Vectors.dense(0.795, 0.583, 1.120, 0.850, 0.174, -0.839, -0.0633, 0.249, 0.673, -0.237)
# 使用bucketProjectionLSH_model自带的函数寻找其最近邻
bucketModel.approxNearestNeighbors(dataset=movieEmbDF, key=sampleEmb, numNearestNeighbors=5).show(truncate=False)
结果如下
# embBucketResult.schema
movieId, emb, bucketId schema:
root
|-- movieId: string (nullable = true)
|-- emb: vector (nullable = true)
|-- bucketId: array (nullable = true)
| |-- element: vector (containsNull = true)
# 前10个movie的Embedding按照多桶局部敏感哈希原理的分桶结果
+-------+-------------------------------------------------------------------------------------------------------------------+------------------------+
|movieId|emb |bucketId |
+-------+-------------------------------------------------------------------------------------------------------------------+------------------------+
|710 |[-0.5111071,0.50438863,1.8513693,0.23458396,-0.44882166,-0.15871468,-0.124460064,-1.2311119,0.59869766,-1.8764442] |[[-6.0], [-9.0], [-3.0]]|
|205 |[0.29628408,-0.41654226,1.143805,-0.3019004,0.12825635,-0.069130205,0.37772354,-0.20516938,-0.27181762,-0.12217015]|[[0.0], [-6.0], [7.0]] |
|45 |[0.6130221,-0.15600249,0.661387,-0.45470318,0.228599,-0.04414679,0.4535038,0.2664382,-0.41018534,0.038817674] |[[-3.0], [-2.0], [4.0]] |
|515 |[0.31498963,-0.3838139,0.34437272,-0.6323954,0.48550555,-0.41461828,0.38806593,-0.07489163,-0.6147391,0.43796948] |[[2.0], [-1.0], [7.0]] |
|574 |[0.052904934,-0.13467973,1.0688442,-0.42235607,-0.14856826,0.3312754,0.61648935,0.15280035,-0.20757616,-0.27220902]|[[-4.0], [-8.0], [4.0]] |
|858 |[-0.3102006,0.56713223,-0.14310305,-0.16539383,-0.12804607,-0.16109817,0.47501242,-0.18505174,0.359562,0.09068517] |[[-7.0], [-1.0], [-5.0]]|
|619 |[-0.39186302,0.23054025,1.1465921,0.040367994,-0.25176704,-0.08718459,-0.05249271,-0.7909765,0.33028358,-1.198281] |[[-3.0], [-6.0], [-1.0]]|
|507 |[0.20856883,0.24598746,0.47044182,-0.16065706,-0.07827129,0.4991506,-0.031586923,-0.10119086,-0.5620659,0.08915071]|[[-2.0], [-1.0], [1.0]] |
|113 |[-0.72815263,0.26236722,1.4721159,-0.23231925,0.04225203,-0.13827243,-0.19969454,-1.0737088,0.18017502,-0.6397825] |[[0.0], [-9.0], [2.0]] |
|34 |[-0.44029653,-0.3508778,0.34412414,0.36146808,0.13711734,0.13438219,0.45183885,0.19798796,0.23603484,0.27684626] |[[1.0], [-9.0], [-1.0]] |
+-------+-------------------------------------------------------------------------------------------------------------------+------------------------+
训练完毕后的BucketLSH model可以使用approxNearestNeighbors()函数获得指定数量的最近邻Embedding
+-------+-------------------------------------------------------------------------------------------------------------------+-----------------------+------------------+
|movieId|emb |bucketId |distCol |
+-------+-------------------------------------------------------------------------------------------------------------------+-----------------------+------------------+
|783 |[0.52841556,0.35948443,0.5445879,0.15192099,0.51500934,-0.51711553,-0.017292202,-0.44987023,0.76398015,-0.35930213]|[[-4.0], [0.0], [-5.0]]|1.2934868995314819|
|216 |[0.8720548,0.33410975,0.4158355,0.29830623,0.10230729,-0.06118736,0.2315479,0.2772035,0.18121752,-0.649445] |[[-8.0], [2.0], [-5.0]]|1.406385940089949 |
|661 |[0.5716868,0.3365735,0.43124142,-0.077825814,0.30620506,-0.34035128,0.16039489,-0.26449445,0.63803244,-0.35367867] |[[-6.0], [0.0], [-4.0]]|1.4284695474424187|
|719 |[0.19356222,0.92130333,0.8998151,0.044217713,0.17359687,-0.5108468,-0.26748997,-0.5147677,0.51631904,-0.6902428] |[[-6.0], [0.0], [-6.0]]|1.4617251171494823|
|104 |[0.24461192,0.86801654,0.5227846,-0.013618191,0.29240727,-0.15529025,-0.22013639,0.5293594,0.35163978,-0.38940087] |[[-6.0], [0.0], [-7.0]]|1.4825116683886987|
+-------+-------------------------------------------------------------------------------------------------------------------+-----------------------+------------------+
