傳統桌面檢索引擎，包括Google Desktop Search、TFIDF向量空間檢索系統等，回傳文章的排名往往仍須使用者花費心思逐步過濾，才能取得真正所需求的文章。為改善文章排名，本研究採用兩階段分群方式。第一階段將底層檢索引擎回傳文章的Snippet分成兩群，一群排名在前，包含所有查詢句字詞；一群排名在後，包含部分或不包含查詢句字詞。第二階段就包含所有查詢句的Snippet群，利用群平均聚合分群法(Group-Average Agglomerative Clustering,GAAC)形成群集。先挑出非單一Snippet群，以其最後結合相似度由高到低決定群間排名。而針對群內排名，則以最終結合子群之最後結合相似度由高到低決定排名。最後，再挑出剩餘單一Snippet群，以其底層檢索系統回傳原始排名順序，遞補於前述分群結果之後，即為重新調整Snippet排名。
本研究採用中文標準新聞文件集共49210篇，經由Google Desktop Search及TFIDF向量空間檢索系統回傳原始排名結果，再透過雜訊過濾，斷詞、特徵詞選取、建立Snippet向量、兩階段分群等處理重新排名，最後與原始排名做比較。結果顯示經由上述分群調整作法，確實有改善原始檢索系統之排名且速度不慢。

Traditional desktop search engines such as Google desktop search or the TFIDF vector space retrieval system usually return a document ranking which still takes time to filter the desired documents. To improve the document ranking, this work proposes a two stage clustering scheme. Based on the returned snippets, the first stage divides the documents into two groups. The first group contains all keywords in the query and the second group contains partial or no query keywords. The ranking of the first group will be ahead of the second group. In the second stage, the first group is further applied the Group-Average Agglomerative Clustering (GACC) to form hierarchical clusters that all have a combination similarity above a given threshold. Based on the GAAC result, non-singleton clusters are ordered from high to low by their last combination similarity. Within each cluster, the two last combining subclusters are also ordered from high to low by their last combination similarity. Having a combination similarity of 0, singleton clusters will be located behind following their initial snippet order.
  As test dataset, a standard Chinese news dataset is used which consists of 49210 documents and 42 enquiry topics. An original document ranking is obtained from Google Desktop Search and a TFIDF vector space retrieval system respectively. Then the snippets are tokenized and filtered to extract the representative keywords and form the snippet vectors.  The snippets then go through the two stage clustering scheme to adjust their ranking. The result shows that the two stage clustering scheme can improve the document ranking and the processing time is short.

目錄
第一章 研究背景與動機	1
第二章 文獻探討	2
2.1	中文斷詞	2
2.2	文件向量模型與文件相似度	2
2.3	文件分群	5
2.4	分群法在檢索上的應用	8
2.5	評估指標	11
2.6	參數調整方式	13
2.6.1	田口式實驗計畫法	13
2.6.2	最陡坡降法	14
2.6.3	機器學習法	14
第三章 方法介紹	16
3.1	問題描述	16
3.2	第一階段利用查詢句作預先分群	17
3.3	第二階段群平均聚合法	18
3.4	終止條件	21
3.4.1	門檻值的設定	21
3.4.2	門檻值和雜訊關係	22
3.5	排名演算法	23
3.6	系統架構圖	25
3.7	分群法調整排名計算範例	27
第四章 實作架構	32
4.1	實驗環境	32
4.2	資料集	32
4.3	訓練及測試流程	35
4.4	測試架構	36
4.5	實驗方法	37
4.5.1	實驗一：Google Desktop排名改良(TITLE查詢句)	39
4.5.1.1門檻值取法	39
4.5.1.2	實驗內容	41
4.5.2	實驗二：Google Desktop排名改良(CONC查詢句)	46
4.5.2.1	門檻值取法	46
4.5.2.2.	實驗內容	48
4.5.3	實驗三：TFIDF排名改良(TITLE查詢句)	52
4.5.3.1	門檻值取法	52
4.5.3.2	實驗內容	54
4.5.4	實驗四：TFIDF排名改良(CONC查詢句)	59
4.5.4.1	門檻值取法	59
4.5.4.2	實驗內容	61
4.5.5	本系統提升比之比較	66
4.5.6	統計檢定結果分析	69
4.5.6.1	檢定資料說明	69
4.5.6.2	Google Desktop檢定	70
4.5.6.3	TFIDF向量空間檢索系統檢定	73
4.5.7	時間複雜度	76
第五章 結論	77
參考文獻	80
附錄A：問題集彙整表	83
附錄B：實驗一GDS在TITLE查詢句實驗數據	85
附錄C：實驗二GDS在CONC查詢句實驗數據	92
附錄D：實驗三TFIDF在TITLE查詢句實驗數據	97
附錄E：實驗四TFIDF在CONC查詢句實驗數據	105

 
表目錄
表一：聚合分群演算法	6
表二：分群法的應用分類表	9
表三：檢索系統評估指標	11
表四：本機檢索系統某次查詢回傳頁面排名效果	16
表五：第一階段包含全部查詢句分群演算法	17
表六：第二階段群平均聚合演算法	19
表七：排名演算法	23
表八：原始頁面排名表	27
表九：調整頁面排名效果	31
表十：CIRB030新聞集原始文件數表	33
表十一：CIRB030答案集相關層級表	34
表十二：資料集49210篇文章斷詞前後之統計資料	34
表十三：實驗設計輸入及輸出	38
表十四：門檻值h彙整表	38
表十五：GDS在TITLE查詢句下三階段的平均精準度及提昇比	41
表十六：GDS在TITLE查詢句下三階段的平均F1值及提昇比	42
表十七：GDS在CONC查詢句下三階段的平均精準度及提昇比	48
表十八：GDS在CONC查詢句下三階段的平均F1值及提昇比	49
表十九：TFIDF在TITLE查詢句下三階段的平均精準度及提昇比	54
表二十：TFIDF在TITLE查詢句下三階段的平均F1值及提昇比	55
表二十一：TFIDF在CONC查詢句下三階段的平均精準度及提昇比	61
表二十二：TFIDF在CONC查詢句下三階段的平均F1值及提昇比	62
表二十三：本系統相對於Google Desktop檢索回傳文章之平均提升比 (TITLE查詢句)- 實驗一彙整	66
表二十四：本系統相對於Google Desktop檢索回傳文章之平均提升比	67
表二十五：本系統相對於TFIDF檢索回傳文章之平均提升比	67
表二十六：本系統相對於TFIDF檢索回傳文章之平均提升比	67
表二十七：本系統四個實驗檢索回傳表現：	69
表二十八：SPSS－符號等級檢定－Google Desktop	70
表二十九：SPSS－檢定統計量－Google Desktop	72
表三十：SPSS－符號等級檢定－TFIDF	73
表三十一：SPSS－檢定統計量－TFIDF	74
表三十二：第二階段分群耗費時間表	76
 
圖目錄
圖一:SNAKET系統示意圖[22]	10
圖二：系統架構圖	25
圖三：集合A的聚合樹狀圖	29
圖四：訓練與測試流程圖	35
圖五：測試架構圖	36
圖六：TITLE查詢句回傳平均精準度	43
圖七：TITLE查詢句回傳平均F值	45
圖八：CONC查詢句回傳平均精準度	50
圖九：CONC查詢句回傳平均F值	51
圖十：TITLE查詢句回傳平均精準度	57
圖十一：TITLE查詢句回傳平均F1值	58
圖十二：CONC查詢句回傳平均精準度	64
圖十三：CONC查詢句回傳平均F1值	65

[1]中央研究院中文詞知識庫小組，CIRB030，中文新聞語料庫http://godel.iis.sinica.edu.tw/CKIP/publication.htm，民國95。
[2]宋永杰， 以聚合法(AGNES)提升檢索效果之研究-以中文新聞為例，淡江大學，2007。
[3]李輝煌，田口方法 : 品質設計的原理與實務，高立圖書公司，2000。
[4]Schenker, A. , Last, M. and Kandek, A. , “A Term-Based Algorithm for Hierarchical Clustering of Web Documents , ” IFSA World Congress and 20th NAFIPS International Conference, vol.5, pp.3076-3081, 2001.
[5]Anagnostopoulos, A., Broder r.Z. and Punera, k. , “Effective and efficient classification on a search-engine Model ,” Knowledge and Information Systems, London Limited, vol.16, pp.129–154 , 2007.
[6]Tsai, C.H., “MMSEG: A word identification system for mandarin Chinese text based on two variants of the maximum matching algorithm,” http://technology.chtsai.org/mmseg/, 1996.
[7]Chen, C. H. and Hsu, C. C., “Synonyms Extraction Using Web Content Focused Crawling,” Lecture Notes in Computer Science, Berlin Heidelberg, vol.4993, pp.286-297, 2008.
[8]Manning, C. D., Raghavan, P. and Schutze, H. , Introduction to Information Retrieval , Cambridge University Press, 2008.
[9]Palmer, C. R. and Faloutsos, C. ,”Density Biased Sampling：An Improved Method for Data Mining and Clustering,” Carnegie Mellon University, pp.99-113, May 1999.
[10]Crabtree, D. , Andreae, P. and Xiaoying Gao, “Query Directed Web Page Clustering,” Web Intelligence, 2006. WI 2006. IEEE/WIC/ACM International Conference , pp.202-210, Dec. 2006.
[11]Xing, D., Xue, G. R., Yang, Q. and Yu, Y., “Deep Classifier: Automatically Categorizing Search Results into Large-Scale Hierarchies , ” Proceedings of the international conference on Web search and web data mining, pp.139-148, Feb., 2008.
[12]Cutting, D. R., Karger, D.R., Pedersen, J. O. and Tukey, J. W., “Scatter/Gather: A Cluster-Based Approach to Browsing Large Document Collections,” Proceedings of the 15th annual international ACM SIGIR conference on Research and development in information retrieval, pp.318-329, 1992. 
[13]Ethen. A , Introduction to Machine Learning , the MIT press, Oct. 2004.
[14]Geraci, F., Pellegrini M., Maggini M., and Sebastiani, F., “Cluster Generation and Cluster Labelling for Web Snippets: A Fast and Accurate Hierarchical Solution,” Internet Math, vol.3,no 4, pp.413-443, Feb 2006.
[15]Demartini, G. , Chirita, P. A. , Brunkhorst, I. and Nejdl, W. , “Ranking Catagories for Web Search , ” Lecture Notes in Computer Science, vol.4956 , pp.564-569, 2008.
[16]http://vivisimo.com/
[17]http://www.dmoz.org/
[18]http://www.eecs.iu-bremen.de/wiki/index.php/Smart_System
[19]Zeng, H. J.,He, Q. C.,Chen, Z.,Ma, W. Y. and Ma, J., “Learning to Cluster Web Search Results,” Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, pp.210-217, July 2004.
[20]Liu, X. and Croft, W. B., “Cluster-Based Retrieval Using Language Models,” Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, pp.186-193, 2004.
[21]Tan, P. N. , Steinbach, M. and Kumar, V. ,Introduction to Data Mining ,  Addison Wesley , 2006.
[22]Ferragina, P. and Gulli, A., “A Personalized Search Engine Based on Web-Snippet Hierarchical Clustering,” Special interest tracks and posters of the 14th international conference on World Wide Web, pp.801-810, May 2005.
[23]Salton.G, Wong .A, Yang .C .S, “A Vector Space Model for Automatic Indexing,” Communications of the ACM, vol 18, issue 11, pp.613-620, Nov., 1975.
[24]Shayler P.J. ,Goodman M. and Ma,T.,”The exploitation of neural network in automotive engine management systems,” Engineering Applications of Artificial Intelligence, pp.147-157,2000.
[25]Soumen, C. , “Mining The Web,” Morgan – Kaufmann Publisher , 2005.
[26]Sven Meyer, Zu Eissen, and Benno Stein, “Analysis of Clustering Algorithms forWeb-Based Search,” Lecture Notes in Computer Science , Springer-Verlag Berlin Heidelberg, vol. 2569, pp.168-178, 2002.
[27]Van Rijsbergen,C. J. and Croft W. B, “Document Clustering an Evaluation of Some Experiments with the Cranfield 1400 Collection,” Information Processing & Management ,no. 11, pp.(171-182), 1975.