淡江大學覺生紀念圖書館 (TKU Library)
進階搜尋


下載電子全文限經由淡江IP使用) 
系統識別號 U0002-1706200915332900
中文論文名稱 以GAAC分群法提升中文檢索排名之研究
英文論文名稱 Using the GAAC Clustering Method to Improve the Ranking of Chinese Retrieval Systems
校院名稱 淡江大學
系所名稱(中) 資訊管理學系碩士班
系所名稱(英) Department of Information Management
學年度 97
學期 2
出版年 98
研究生中文姓名 周建榮
研究生英文姓名 Chien-Jung Chou
電子信箱 elvispresley40@gmail.com
學號 696630440
學位類別 碩士
語文別 中文
第二語文別 英文
口試日期 2009-06-07
論文頁數 112頁
口試委員 指導教授-魏世杰
委員-謝文恭
委員-蕭育如
委員-李鴻璋
中文關鍵字 GAAC聚合法  TFIDF向量空間檢索系統  Google Desktop Search 
英文關鍵字 Group Average Agglomerative Clustering  TFIDF Vector Space Retrieval System  Google Desktop Search 
學科別分類 學科別社會科學管理學
學科別社會科學資訊科學
中文摘要 傳統桌面檢索引擎,包括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.
論文使用權限
  • 同意紙本無償授權給館內讀者為學術之目的重製使用,於2009-07-22公開。
  • 同意授權瀏覽/列印電子全文服務,於2009-07-22起公開。


  • 若您有任何疑問,請與我們聯絡!
    圖書館: 請來電 (02)2621-5656 轉 2281 或 來信