本論文的主要目標是利用使用者輸入的Query Logs，搭配Basket-based和Item-based的機率模型實作一個關鍵字推薦系統。
研究一開始，我們先設計了小工具來蒐集使用者輸入的Query Logs ，以這些資料做為我們推薦的基礎，搭配機率模型經過計算後，產生一組推薦清單並依照分數排序再推薦給使用者。本系統推薦的關鍵字主要是屬於Query Expansion的類型，根據使用者輸入的關鍵字組合，找出其他對使用者有幫助的關鍵字，並加回原始的組合當中做為推薦的結果。
在實際請使用者實驗過後，我們利用Precision-Recall的方法來評估推薦的成效。透過統計數據可以發現，使用Basket-based和Item-based的機率模型來推薦關鍵字，的確是可以推薦出對使用者有幫助的關鍵字。

The main goal of this thesis is to design a query recommend system by utilizing users query logs combined with Basket-based and Item-based probabilistic model.
At the beginning of the research, we design tools to collect the query logs entered by users, which is the basic of our recommendation, combined these with probabilistic model to create a recommendations list arranged by score sequence，and finally recommend it to the users. The system, which recommends keywords mainly belonging to the method of query expansion, will try to find other helpful keywords based on the users query and add these new words to the original query as the recommending results.
After practically being used by users, we utilize Precision-Recall method to evaluate the results. Judging by statistic, we can find out that basket-based and Item-based probabilistic model successfully creates helpful key words recommendations to the users.

目錄
第一章	緒論	1
1.1	研究動機	2
1.2	研究目的	5
1.3	研究內容	7
1.4	論文內容與大綱	9
第二章	背景知識與相關研究	10
2.1	關鍵字推薦	10
2.2	Basket-based和Item-based推薦系統	13
第三章	系統架構與設計	16
3.1	Query Logs資料蒐集	16
3.1.1	Meta-search Engine	17
3.1.2	Firefox 擴充套件	21
3.2	關鍵字推薦系統	24
3.2.1	推薦流程和機制	25
3.2.2	條件機率(Conditional Probability)	31
3.2.3	不可取代性(Unsubstitutability)	33
第四章	系統實作與結果	34
4.1	系統介面與功能	35
4.2	實驗環境與流程	37
4.2	實驗結果與討論	41
第五章	結論與未來研究方向	51
5.1	結論	51
5.2	未來研究方向	53
參考文獻	55
附錄-英文論文	57

圖目錄
圖 1	Meta-search Engine介面	17
圖 2	Google搜尋API的片段程式碼	18
圖 3	Google搜尋API回傳結果的結構內容	19
圖 4	Meta-search Engine蒐集到的Query logs	20
圖 5	Firefox擴充套件	21
圖 6	Firefox擴充套件蒐集到的Query Logs	22
圖 7	關鍵字推薦系統主要流程	25
圖 8	資料前處理後的Token資料	26
圖 9	資料前處理後的Token Pair資料	26
圖 10	Basket-based推薦和Item-based推薦的主要流程	27
圖 11	關鍵字推薦系統介面	35
圖 12	實驗環境介面	37
圖 13	實驗步驟一	38
圖 14	實驗步驟二和三	39
圖 15	實驗步驟四	39
圖 16	Precision-Recall折線圖	44
圖 17	整體的Precision-Recall折線圖	45
圖 18	平均Precision次數分佈，n=91	47

表目錄
表 1	使用者回饋的比例分布，n=1,637	41
表 2	每個排名的Precision和Recall值	42
表 3	固定區間的Precision-Recall	43
表 4	整體的Precision-Recall	45
表 5	查詢關鍵字範例	48
表 6	推薦結果範例	49

[1]	Jansen, B.J. and Spink, A. and Bateman, J. and Saracevic, T. (1998) “Real life information retrieval: a study of user queries on the Webqueries on the Web”. ACM SIGIR Forum, Vol. 32, No. 1, pp.5-17.
[2]	Baeza-Yates, R. (2005) “Web usage mining in search engines”.  Web mining: applications and techniques, pp.307-321.
[3]	Wen, J.R. and Nie, J.Y. and Zhang, H.J. (2001) “Clustering user queries of a search engine”. Proceedings of the 10th international conference on World Wide Web, pp.162-168.
[4]	Baeza-Yates, R. and Hurtado, C. and Mendoza, M. (2005) “Query recommendation using query logs in search engines”. Current Trends in Database Technology-EDBT 2004 Workshops, pp.395-397.
[5]	Salton, G. and Buckley, C. (1997) “Improving retrieval performance by relevance feedback”. Readings in information retrieval, pp.355-364.
[6]	Cui, H. and Wen, J.R. and Nie, J.Y. and Ma, W.Y.(2002) “Probabilistic query expansion using query logs”.  Proceedings of the 11th international conference on World Wide Web, pp.325-332.
[7]	Fonseca, B.M. and Golgher, P.B. and De Moura, E.S. and Ziviani, N. (2003) “Using association rules to discover search engines related queries”. Web Congress, 2003. Proceedings. First Latin American, pp.66-71.
[8]	Jones, R. and Rey, B. and Madani, O. and Greiner, W. (2006) “Generating query substitutions”. Proceedings of the 15th international conference on World Wide Web, pp.387-396.
[9]	Li, M. and Dias, B. and El-Deredy, W. and Lisboa, P.J.G. (2007) “A probabilistic model for item-based recommender systems”. Proceedings of the 2007 ACM conference on Recommender systems, pp.129-132.
[10]	Dupret, G. and Mendoza, M. (2006) “Automatic query recommendation using click-through data”. Professional Practice in Artificial Intelligence, pp.303-312.
[11]	Boldi, P. and Bonchi, F. and Castillo, C. and Donato, D. and Vigna, S. (2009) “Query suggestions using query-flow graphs”. Proceedings of the 2009 workshop on Web Search Click Data, pp.56-63.
[12]	Mei, Q. and Zhou, D. and Church, K. (2008) “Query suggestion using hitting time”. Proceedings of the 17th ACM conference on Information and knowledge management, pp. 469-478.
[13]	K‥onig, A.C. and Gamon, M. and Wu, Q. (2009) “Click-through prediction for news queries”. Proceedings of the 32nd international ACM SIGIR conference on Research and development in information retrieval, pp. 347-354.
[14]	He, Q. and Jiang, D. and Liao, Z. and Hoi, S. and Chang, K. and Lim, E.P. and Li, H. (2009) “Web query recommendation via sequential query prediction”. Data Engineering, 2009. ICDE'09. IEEE 25th International Conference on, pp. 1443-1454.
[15]	Baeza-Yates, R. and Tiberi, A. (2007) “Extracting semantic relations from query logs”. Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 76-85.