在上一篇《關鍵詞推薦工具中的使用者引導機制之二：suggestion架構》中， 我們提到， 在使用者在搜尋引擎，或是關鍵詞推薦工具中輸入搜尋query片段的過程中， 我們可以提供suggestion來對使用者搜尋進行引導。 我們可以認為此時使用者的搜尋意圖是不全面的。 而當使用者已經輸入完整query後， 使用者的搜尋用途已經在某種程度上明确了， 此時我們就可以使用相關搜尋， 擴充出與使用者輸入搜尋意圖一緻/類似的高品質query， 引導使用者進行搜尋， 讓使用者更快地擷取資訊， 得到所求。本文會具體介紹相關搜尋類似的關鍵詞推薦系統的政策架構，以及業界常用的相關搜尋挖掘算法。
說簡單一點， 相關搜尋query， 其實也是一個關鍵詞推薦。 和adwords中關鍵詞工具， 或是百度關鍵詞工具不同的地方， 是相關搜尋對品質要求非常高，而給出的結果一般比較少， 即高準确， 低召回。
圖： 百度相關搜尋
圖： Google相關搜尋
以上分别為Baidu和Google的相關搜尋結果， 不知道大家是否發現，Baidu相關搜尋結果多樣性強一些，同時商業價值也強一些（本文不介紹商業價值機制，後文介紹的優化目标中加入商業價值因素即可）。
相關搜尋政策架構
因為相關搜尋就是一個典型的特定場景的關鍵詞推薦系統， 是以相關搜尋從政策架構上，會包含完整的關鍵詞推薦的邏輯。 包括候選詞源觸發(query retrival)、 相關性過濾(filtering)、排序模型排序(ranking)， 以及根據規則進行調整（marketing rule）。 其中每個階段都可以根據最終的優化目标（或者多目标）設計相應架構。
圖：關鍵詞推薦政策架構中的主要處理邏輯，包括query retrival, filtering, ranking, marketing rule幾大邏輯
各元件功能
- 候選詞源觸發(query retrival)：其主要功能是通過各種offline資料挖掘，得到query（或是成份）之間的關系， 擷取到候選的待推薦query，供後續邏輯進行處理。
- 相關性過濾（filtering）：根據應用場景，對不滿足query之間相關性的候選詞進行過濾，以減輕後續邏輯的性能負擔。 相關性過濾的方法可參見《分類模型在關鍵詞推薦系統中的應用》
- 排序(ranking)：根據應用場景的優化目标，對候選詞進行排序。 例如， 如果要提升使用者體驗，那就直接将高相關性的候選詞排在前邊（衡量标準可參見《使用NDCG評估關鍵詞推薦系統的相關性》），如果同時需要考慮商業變現， 那麼可以考慮将能夠擷取到較多廣告點選量的query排到比較靠前的位置
- 業務規則（marketing rule）： 例如， ‘黃賭毒’結果必須過濾，或者帶有某些特定字眼的關鍵詞必須提到比較靠前的位置。。。。 這些規則更多是人為确定的（例如PM确定）
相關搜尋query政策
資料
總的來說，搜尋引擎要挖掘相關搜尋結果，有以下幾類資料可用：
- 網民搜尋session資料（後續簡稱session資料）： 就是網民在搜尋引擎搜尋框中連續輸入的多個query。 這裡有一個假定， 就是同一個session中的query都是有關系的（更進一步， 同一個session中離得近的query更相關； 在多個session中都出現的連續搜尋更相關），該資料可以表示為多個query的序列
- 搜尋點選資料： 即網民輸入某個query後，在搜尋引擎上點選的url，該資料可以簡單表示為<query, url>的pair
- 網頁内容資訊： url對應的網頁内容
相關搜尋的算法， 總的來說都是圍繞上述資料， 其中 1，2類資料我們可以認為是網名的行為資料，而3可以認為是内容資料。 一般而言， 很多算法直接使用1，2類行為資料即能取得較好效果。 也有一些算法會結合網頁内容資訊提升效果。
候選詞源觸發方式
以下是幾種典型的用于相關搜尋的算法：
Beeferman, Doug and Berger, Adam. 2000. Agglomerative Clustering of a Search Engine Query Log. Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2000, 407-416.
使用Agglomerative Clustering方法， 首先使用query點選資料，對query和URL進行聚類， 取得相近query(具體算法介紹參見《搜尋引擎點選日志聚類實作相關搜尋》)；得到query聚類後，在新query到來時，可以先判斷網民query與哪個/些聚類最相近，然後該聚類下的詞，都作為待推薦的關鍵詞後續，進行後續排序過濾。 該方式優點是完全使用網民查詢點選的行為資料，而沒有使用到網民的内容， 或是query的内容； 此類思路和協同過濾類似。
圖： query-點選關系
圖： Agglomerative Clustering Init
圖： Agglomerative Clustering Iterative
Wen, Ji-Rong, Nie, Jian-Yun and Zhang, Hong-Jiang. 2002. Query Clustering Using User Logs. ACM Transactions on Information Systems. January 2002, Vol. 20(1), pp. 59-81.
該方式不僅使用了query-點選資料對query進行了聚類，同時還是用了query内容等資訊。 也就是說， 網民行為和内容， 作為相似度度量的最終标準。
圖： 結合查詢行為及内容相似度度量
BM Fonseca, PB Golgher 2003 Using association rules to discover search engines related queries Web Congress, 2003 - ieeexplore.ieee.org
該方法中直接使用2項關聯規則進行related-query的挖掘， 滿足提前設定的支援度， 置信度門檻值後後， 就作為推薦結果候選
Z Zhang, O Nasraoui 2006 Mining search engine query logs for query recommendation - Proceedings of the 15th international conference …, 2006 - dl.acm.org
該方法， 也是直接使用session資料對相關搜尋結果進行挖掘總的思路也是根據session中共現機率較高的關鍵詞作為高相關的query pair。 其中的一個創新， 是計算session之間的距離的時候， 使用了衰減方式。
論文中認為： session 中的pair， 離得越遠， 相似度就越低， 例如， 假設session中每一步的相似度是d(d屬于(0, 1))， 則兩步的相似度為 d^2， 使用該方式進行衰減， 兩步的相似度為 d + d^2 而不是2d (當然， 實際中也可以選擇， 兩步的相似度， 就是d^2， 而不是d^2 + d)
圖：session中随着間隔的增加，權重衰減
R Baeza-Yates, C Hurtado, M Mendoza 2005 Query recommendation using query logs in search engines Current Trends in Database 2005 - Springer
以該文為代表的方式， 還同時使用了搜尋query和點選URL對應頁面中的term之間的關系， 使用點選URL對應頁面中出現的term作為query的表示，同僚考慮了query的受歡迎程度作為相似度度量。 不過該方法因為挖掘代價較大，是以并未做該類實驗， 畢竟， 簡單也是一種美： ）
其中q為代表特定query的向量， Pop(q,u)為搜尋query q後點選URL u的PV， Tf(ti,u)為在在u對應的網頁中， ti出現的詞頻。
排序過濾
産生了大量候選詞後，一般會使用相關性模型直接過濾高度不相關候選詞（參見《分類模型在關鍵詞推薦系統中的應用》），之後進行排序。 排序時，一般按照優化目标進行排序。例如，假設我們一方面要考慮相關性（使用Q表示），同時要考慮商業變現收入（使用R表示）， 則我們可以将優化目标表示為：
T=Q^(t) * R^(1-t)， 其中t屬于[0，1]，通過調整t來控制在相關性和商業變現收入之間的權衡，該方式也可擴充為更多目标優化場景。
當然，對于現實中的相關搜尋， 可以融合多種政策算法的資料以提高最終品質。
更多内容請參考：
百度關鍵詞工具介紹參見：http://support.baidu.com/product/fc/4.html?castk=24b18bi7062c720d0d596
Beeferman, Doug and Berger, Adam. 2000. Agglomerative Clustering of a Search Engine Query Log. Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2000, 407-416.
Wen, Ji-Rong, Nie, Jian-Yun and Zhang, Hong-Jiang. 2002. Query Clustering Using User Logs. ACM Transactions on Information Systems. January 2002, Vol. 20(1), pp. 59-81.
BM Fonseca, PB Golgher 2003 Using association rules to discover search engines related queries Web Congress, 2003 - ieeexplore.ieee.org
R Baeza-Yates, C Hurtado, M Mendoza 2005 Query recommendation using query logs in search engines Current Trends in Database 2005 - Springer
也可關注我的微網誌： weibo.com/dustinsea
或是直接通路： http://semocean.com