以GAAC分群法提升中文檢索排名之研究

Using the GAAC Clustering Method to Improve the Ranking of Chinese Retrieval Systems

周建榮(Chien-Jung Chou)

指導教授 ： 魏世杰

淡江大學/管理學院/資訊管理學系碩士班/碩士(2009年)

https://doi.org/10.6846/TKU.2009.00589

摘要

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

關鍵字

GAAC聚合法 ； TFIDF向量空間檢索系統 ； Google Desktop Search

並列摘要

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.

並列關鍵字

Group Average Agglomerative Clustering ； TFIDF Vector Space Retrieval System ； Google Desktop Search

參考文獻

[2]宋永杰， 以聚合法(AGNES)提升檢索效果之研究-以中文新聞為例，淡江大學，2007。

[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.

[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.