有贊搜索引擎實踐(算法篇)

18 April 2016

1. 搜索算法總體架構

在上篇文章(工程篇)中, 我們介紹了有贊搜索引擎的基本框架. 搜索引擎主要3個部件構成. 第一, hadoop集群, 用于生成大規模搜索和實時索引; 第二, ElasticSearch集群, 提供分布式搜索方案; 第三, 高級搜索集群, 用于提供商業搜索的特殊功能.

商業電商搜索由于搜索的特殊性, 獨立的ElasticSearch集群是無法滿足多樣的算法需求的, 我們在搜索的各個部件上都有相應的算法插件, 用于構建商業電商搜索引擎的算法體系.

1.1 索引過程

創建索引過程從原始數據創建倒排索引的過程. 這個過程中我們對商品(doc)進行分析, 計算商品靜態分, 并對商品進行相似度計算. 商品的靜態分對于提升搜索引擎質量起到至關重要的作用, 相當于網頁搜索的pagerank, 想象一下如果沒有pagerank算法, 網頁搜索的質量會有多么差. 在電商搜索中, 最常見的問題是相似商品太多, 必須在建立索引過程中就對商品間的相似度進行預計算, 以便在檢索過程中進行有效去重.

創建索引的過程如下.

step 1. 計算每個doc的靜態分
step 2. 計算兩兩doc的相似度
step 3. 根據相似度和其他信息對數據進行分庫
step 4. 建立ES索引

1.2 檢索過程

檢索過程是搜索引擎接收用戶的query進行一系列處理并返回相關結果的過程. 商業搜索引擎在檢索過程中需要考慮2個因素: 1) 相關性 2) 重要性.

相關性是指返回結果和輸入query是否相關, 這是搜索引擎基本問題之一, 目前常用的算法有BM25和空間向量模型. 這個兩個算法ElasticSearch都支持, 一般商業搜索引擎都用BM25算法. BM25算法會計算每個doc和query的相關性分, 我們使用Dscore表示.

重要性是指商品被信賴的程度, 我們應該吧最被消費之信賴的商品返回給消費者, 而不是讓消費之自己鑒別. 尤其是在商品充分競爭的電商搜索, 我們必須賦予商品合理的重要性分數, 才能保證搜索結果的優質. 重要性分, 又叫做靜態分, 使用Tscore表示.

搜索引擎最終的排序依據是:

Score = Dscore * Tscore

即綜合考慮靜態分和動態分, 給用戶相關且重要的商品.

檢索的過程大致抽象為如下幾個步驟.

step 1. 對原始query進行query分析
step 2. 在as中根據query分析結果進行query重寫
step 3. 在as中使用重寫后的query檢索es
step 4. 在es查詢過程中根據靜態分和動態分綜合排序
step 5. 在as中吧es返回的結果進行重排
step 6. 返回結果

下面幾章闡述幾個重點技術.

2. 商品靜態分計算技術

在電商搜索引擎里面商品的靜態分是有網頁搜索里面的pagerank同等的價值和重要性, 他們都是doc固有的和查詢query無關的價值度量. pagerank通過doc之間的投票關系進行運算, 相對而言商品的靜態分的因素會更多一些. 商品靜態計算過程和pagerank一樣需要解決如下2個問題: 1. 穩定性. pagerank可以保證一個網站不會因為簡單鏈接堆砌可以線性提升網站的排名. 同樣, 商品靜態分的計算不可以讓商品可以通過增加單一指標線性增加分值(比如刷單對搜索引擎的質量的影響).
2. 區分度. 在保證穩定性的基礎上商品靜態分要有足夠的區分度可以保證同樣搜索的條件下, 排在前面的商品的質量比排在后面的商品的質量高.

我們假設商品的靜態分有3個決定性因素, 1.下單數, 2. 好評率 3. 發貨速度

靜態分我們使用Tsocre表示, Tscore可以寫成如下形式:

Tscore = a * f(下單數) + b * g(好評率) + c * h(發貨速度)

a,b,c是權重參數, 用于平衡各個指標的影響程度. f,g,h是代表函數用于把原始的指標轉化成合理的度量.

首先, 我們需要尋找合理的代表函數.

首先對各個指標取log. log的導數是一個減函數, 表示為了獲得更好的分數需要花費越來越多的代價.

標準化. 標準化的目的讓各個度量可以在同一區間內進行比較. 比如下單數的取值是0~10000, 而好評率的取值為0~1. 這種情況會影響到數據分析的結果和方便性, 為了消除指標之間的量綱的影響, 需要進行數據標準化處理, 以解決數據指標之間的可比性.最常用的標準化方法是z-score標準化方法.

z-score 標準化方法

"概率論"告訴我們對于滿足正態分布的數據來說, 均值前后3個z-score的范圍可以覆蓋99%的數據. 經驗地, 我們把>5個zscore 或者小于 -5個zscore的分數設置成5*zscore或者-5zscore. 特別說明的是, 我們不建議使用min-max標準化方法. 這種方法又叫離差標準化, 是對原始數據的線性變換, 使結果值映射到[0-1]之間, 轉化函數如下: 這種方法非常不穩定, 假設一個奇異點是第二大的值的1000倍, 會讓大部分的值都集中在0~0.01, 同樣失去了歸一化的目的.

圖一是使用min-max歸一化后的數據分布, 顯然大部分數據被"壓扁"在很小的范圍; 圖二使用log歸一化后的數據分布, 由于log緩解了增長速度, 可以看出來已經有一個不錯的結果了, 圖三是在log的基礎上進行z-score歸一化, 可以看出來, z-score讓數據變得非常平滑. (圖一: min-max歸一化) (圖二: log歸一化) (圖三: log-zscore歸一化)

最后, 選擇合適的權重 經過log-zscore歸一化以后, 我們基本上吧f,g,h的表示的代表函數說明清楚. Tscore = af(下單數) + bg(好評率) + c*h(發貨速度), 下一步就是確定a,b,c的參數. 一般有兩個方法:

a) 專家法. 根據我們的日常經驗動態調整權重參數;
b) 實驗法. 首先在專家的幫助下賦一個初始值, 然后改變單一變量的方法根據abtest的結果來動態調整參數.

3. 商品標題去重

商品標題去重在電商搜索中起到重要作用, 根據數據, 用戶通過搜索頁購買商品80%選擇搜索的前4頁. 商品標題的重復會導致重要的頁面沒有含金量, 極大降低了搜索的購買率.

舉個例子:

Title1:美味/香蕉/包郵/廣東/高州/香蕉/banana//無/催熟劑/

Title2:美味/香蕉/廣東/高州/香蕉//非/粉蕉/包郵/

首先, 進行特征向量化

這里用到 "bag of word" 技術, 將詞匯表作為空間向量的維度, 標題的每個term的詞頻作為這個feature的值. 以這個例子來說. 這個詞匯的維度為: 美味(0), 香蕉(1), 包郵(2), 廣東(3), 高州(4), banana(5),無(6), 催熟劑(7),非(8),粉蕉(9) 位置: 0,1,2,3,4,5,6,7,8,9

Title1: 1,2,1,1,1,1,1,1,0,0
Title2: 1,2,1,1,1,0,0,0,1,1

這個每個title都用一個固定長度的向量表示.

再次, 計算兩兩相似度

相似度一般是通過計算兩個向量的距離實現的, 不失一般性, 在這里我們使用1-cosine(x,y)來表示兩個向量的距離. 這是一個"All Pair Similarity"的問題, 即需要兩兩比較, 復雜度在O(n^2). 在商品量巨大的時候單機很難處理. 我們給出兩種方法用于實現"All Pair Similarity".

方法一: spark的矩陣運算.

rddRows = sc.parallelize(["1 0 2 0 0 1", "0 0 4 2 0 0"])rddRows.map(lambda x: Vectors.dense([float(each) for each in str(x).split(" ")])) mat = RowMatrix(rddRows)simsPerfect = mat.columnSimilarities()

方法二: map-reduce 線性方法. 這個方法參考論文"Pairwise Document Similarity in Large Collections with MapReduce". 可以實現幾乎線性的時間復雜度. 相對于矩陣運算在大規模(10億以上)pair similarity 運算上面有優勢. 這個方法簡單的描述如下: 首先, 按照倒排索引的計算方式計算每個term到doc的映射. 比如3個doc:

doc1 = 我 愛 北京 doc2 = 我 北京 天安門 doc3 = 我 天安門

轉化為倒排格式, 這個需要一次mapper reduce

我 -> doc1, doc2, doc3 愛 -> doc1 北京 -> doc1, doc2 天安門 -> doc2, doc3

然后, 對于value只有一個元素的過濾掉, 對于value大于2個doc的兩兩組合:

doc1,doc2 <---- from: 我 -> doc1, doc2, doc3 doc1,doc3 <---- from: 我 -> doc1, doc2, doc3 doc2,doc3 <---- form: 我 -> doc1, doc2, doc3 doc1,doc2 <---- from: 北京 -> doc1, doc2 doc2,doc3 <---- from: 天安門 -> doc2, doc3

最后, 對于輸出進行聚合,value為重復次數和兩個doc乘積開根號的比.

doc1,doc2 -> 2/(len(doc1)*len(doc2))^1/2 = 0.7 doc1,doc3 -> 1/(len(doc1)*len(doc3))^1/2 = 0.3 doc2,doc3 -> 2/(len(doc2)*len(doc3))^1/2 = 0.3

對于2個title1, title2, 如果X(title1, title2) > 0.7 則認為title1和title2相似, 對于相似的兩個doc, 靜態分大的定義為主doc, 靜態分小的定義為輔doc. 主doc和輔doc分別建庫.

區別于網頁搜索(網頁搜索直接將輔doc刪除), 我們將主doc和輔doc分別建庫. 每一次搜索按比例分別搜主庫和輔庫, 并將結果融合返回. 這樣可以保證結果的多樣性.

4. 店鋪去重

店鋪去重和商品標題去重有點不同. 由于電商特定場景的需要, 不希望搜索結果一家獨大, 這樣會引發強烈的馬太效應. 店鋪去重不能使用如上的方法進行. 因為上面的方法的主要依據是文本相似, 在結果都相關的前提下, 進行適當的取舍. 但是店鋪去重不是這樣的特性.

設想一下, 如果我們根據店鋪是否相同, 把同一店鋪的商品分到主庫和從庫中, 如下圖所示.

A和B代表不同的店鋪.

在搜索香蕉的時候, 的確可以控制A店鋪結果的數量, 但是在搜索"梨"的時候就錯誤的吧B店鋪的梨排在前面了(假設A:梨比B:梨靜態分高).

實際上想達到店鋪去重的效果通過分桶搜索是很容易做的事情. 我們假設每頁搜索20個結果, 我們把索引庫分成4個桶, 每個商品對桶數取模得到所在桶的編號. 這樣可以保證同一店鋪的商品僅在一個桶里面. 搜索的過程每個桶平均分攤搜索任務的25%, 并根據靜態分合并成一頁的結果. 這樣同一保證結果的相對順序, 又達到了店鋪去重的目的.

如上圖所示, 搜索"香蕉", 雖然A店鋪有10個滿足需求的結果, 但是每頁搜索醉倒只有5個結果可以展示.

query分析與Query改寫技術

上面介紹了幾個建立索引過程中幾項技術, 檢索過程中的關鍵技術有很多. 其中最著名的是query分析技術. 我們使用的query分析技術主要包括核心詞識別, 同義詞拓展, 品牌詞識別等等. query分析技術大部分都是NLP研究范圍, 本文就不詳細闡述很多理論知識. 我們重點介紹同義詞拓展技術. 這個技術一般都需要根據自己的商品和和用戶日志特定訓練, 無法像分詞技術和品牌詞識別一樣有標準的庫可以適用.

同義詞拓展一般是通過分析用戶session日志獲取. 如果一個用戶輸入"蘋果手機"沒有得到想要的結果, 他接著輸入"iphone", 我們在"蘋果手機"和"iphone"之間創建一個轉移關系. 基于統計, 我們可以把用戶query創建一個相互聯系的權重圖.
用戶輸入query "蘋果手機", 根據query分析, "蘋果手機"有 "iphone"0.8, "iphone 6"0.5 兩個同義詞. 0.8和0.5分別表示同義的程度. 我們想要"蘋果手機", "iphone", "iphone 6" 3個query同時輸入, 并且按照同義的程度對不同的query賦予不同的權重. ElasticSearch提供的BoostingQuery可以支持這個需求. 參考: https://www.elastic.co/guide/en/elasticsearch/guide/current/boostingquery_clauses.html

原始query:

{"query" {"match": {"query":"蘋果手機"}} }

改寫后的Query

{"query": {"should": [{ "match": {"content": {"query": "蘋果手機","boost": 10 }}},{ "match": {"content": {"query": "iphone","boost": 8}}},{ "match": {"content": {"query": "iphone6","boost": 5}}}]} }

其他比如核心詞識別, 歧義詞糾正等方法差不多, 本文不做詳細闡述.

其他

商業電商搜索算法另外兩個重要技術, 一個是類目體系建立和應用,另一個是個性化技術. 這個兩項技術我們還處在探索階段. 類目體系我們主要使用機器學習的方法進行訓練, 個性化主要通過用戶畫像進行Query改寫來實現. 等我們上線有效果在與大家分享.

小結

搜索算法是一個非常值得一個電商產品持續投入的技術. 一方面我們技術人員要有良好的技術背景, 可以借鑒很多成熟的技術, 避免重復造輪子; 另一方面, 每個產品的搜索都有自身的特點, 需要深入研究產品的特性給出合理的解決方案. 本文給出的案例都具有代表性, 靈活的運用搜索的各方面的技術. 另外, 商業搜索非常看重投入產出比, 我們也需要在眾多方案中尋找捷徑. 比如我們在做類目體系時候, 沒有投入大量的人力資源用于標注數據, 而是通過爬蟲爬取其他電商的數據進行參考, 從而節省了80%的人力資源. 由于筆者能力有限, 文中的方案不保證是問題的最優解, 如果有指正, 請聯系筆者(hongbin@youzan.com).

總結

以上是生活随笔為你收集整理的有赞搜索引擎实践(算法篇)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。