臺灣博碩士論文加值系統

網際網路已成為資訊傳播與溝通的主要媒介，人們都經由瀏覽網站，或者利用搜尋服務來找尋所想要的資訊。在資訊搜尋的過程中，使用者所輸入的查詢字，可決定資料的搜尋範圍，但也同時影響了其與欲找尋的資料之間的適切性，所以查詢字與欲查詢資料內容之間的誤差，儼然已成為重要的課題。針對此問題，我們以關聯式索引典來提供互動式查詢擴展。為了建構關聯式索引典，我們首先假設某些點選的網頁即使並非該使用者真正所想要，但每一筆使用者查詢歷史紀錄中的點選網頁仍皆互有語意關係；接著我們採用關聯式規則技術，來探勘使用者查詢歷史紀錄中的點選網頁，試圖從中找到字與字的非對稱性相互關聯來達成建構之目的。而這種互動式擴展查詢功能，僅使用資料庫的結構化查詢語言，即可從關聯式索引典中找尋候選擴展字供使用者選擇。如果因所蒐集的使用者查詢歷史紀錄不完整，而造成某些查詢的候選擴展字太少，我們可運用自我組織型映射(SOM)類神經網路模型中的合作機制概念，來延伸候選擴展字。實驗結果證實，從使用者查詢歷史紀錄中探勘出字與字的關聯性是可行的；不過，關聯式索引典的品質與完整性，很明顯地受限於使用者查詢歷史紀錄的蒐集。我們將上述之實驗結果，實際運用在線上學習之課程軟體代理人的查詢精靈，以增進其搜尋的能力。

World Wide Web has become a major medium for information publication and communication. People either browse or use the search service when they want to find specific information on the web. The popular way to find desired information is using major search engines. Vocabulary problem are raised on information retrieval issues. Our approach to these problems is to provide users with query expansion based on association thesaurus. To construct association thesaurus, association rule mining is employed to generate asymmetric relationship between terms by relevance feedback. It is basis of assuming that rated web pages on every search result are correlated even though some rated web pages are not desired for the user. Hence, rated web pages are transferred to user-interested terms based on terms co-occurrence by ATF-DF measure we propose. Then these list of user-interested terms are mined to produce association rules. Interactive query expansion uses structural query language to respond candidate expansion terms for user selecting from association thesaurus. In addition, novel method whose idea comes from cooperative process of self-organizing map expands candidate expansion terms when rare candidate expansion terms. Experimental results show that query logs are used to transfer to knowledge is feasible. The quality and completeness of association thesaurus depend on the query logs collection greatly. We apply interactive query expansion with association thesaurus to the Query Agent on the Coursebot which is web-based intelligent recommendation system for e-learning. The Query Agent has improvement of retrieval effectiveness on the Coursebot. It can increase precision rate of search without poor recall rate.

Chapter 1 Introduction
1.1 Motivation1
1.2 Limitations of Thesaurus for Query Expansion
1.3 Our Goal and Design
1.4 Outline of the Thesis
Chapter 2 Background
2.1 Intelligent Software Agents
2.2 Multi-Agent Systems
2.3 Coursebot
2.4 Data Mining
2.5 Association Rule
2.6 Related Work
2.6.1 Relevance Feedback
2.6.1.1 Automatic Query Expansion (AQE)
2.6.1.2 Interactive Query Expansion (IQE)
2.6.2 Thesaurus
Chapter 3 Generation of Association Thesaurus
3.1 Query Logs Collection
3.2 Pre-processing
3.3 Terms Selection
3.4 Terms Correlation Mining
Chapter 4 Query Agent
4.1 Overview
4.2 Interactive Query Expansion
4.3 Search Procedure
Chapter 5 Experiments
5.1 Association Thesaurus
5.1.1 Experimental Design
5.1.2 Examples of Expanding terms
5.2 Interactive Query Expansion
5.2.1 Experimental Design
5.2.2 Results and Analysis
Chapter 6 Discussion and Conclusion
6.1 Dataset Criteria
6.2 Conclusion
6.3 Further Work
References
APPENDIX A. Stop Words List

[1]R. Agrawal and R. Srikant, “Fast Algorithms for Mining Association Rule,” Proceeding of the 20th International Conferene on Very Large Databases, Jun. 1994, pp. 487-499.
[2]R. Agrawal, T. Imielinki, and A. Swami, “Mining Association Rule Between Sets of Items in Large Database,” Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, 1993, pp. 207-216
[3]R. Agrawal, T. Imielinski, A. Swami, “Database Mining: A Performance Perspective,” IEEE Transactions on Knowledge and Data Engineering, Special Issue on Learning and Discovery in Knowledge-Based Databases, 5(6), Dec. 1993, pp. 914-925.
[4]A. T. Arampatzis, Th.P.van der Weide, C.H.A. Koster, and P.van Bommel, “Term Selection for Filtering based on Distribution of Term over Time,” Proceedings of RIAO’2000, April. 2000.
[5]S. Bechhofer and C. Goble, “Thesaurus Construction Through Knowledge Representation,” Data & Knowledge Engineering, 37, pp.25-45, 2001.
[6]J. Borges and M. Levene. “Mining Association Rule in Hypertext Databases,” Proceedings of the 4th International Conference on Knowledge Discovery and Data Mining, Aug. 1998, pp. 149-153.
[7]S. Brin, R. Motwani, J. D.Ullman, and S. Tsur, “Dynamic Itemset Counting and Implication Rules for Market Basket Data,” Proceedings of the International ACM SIGMOD Conference, May. 1997, pp.255-264.
[8]A.G. Büchner and M.D. Mulvenna, “Discovering Internet Marketing Intelligence through Online Analytical Web Usage Mining,” ACM SIGMOD Record, 27(4), pp. 54-61, 1998.
[9]A. Caglayan and C. Harrison, AGENT souorcebook, Wiley Computer Publishing, 1997.
[10]S. Chakrabarti, “Data Mining for Hypertext: A Tutorial Survey,” ACM SIGKDD Explorations, 1(2), pp. 1-11, 2000.
[11]C.S. Chang and A.L.P. Chen, “Supporting Conceptual and Neighborhood Queries on the World Wide Web,” IEEE Transactions on System, Man, and Cybernetics-Part C: Applications and Reviews, 28(2), pp.300-308, May 1998.
[12]M.S. Chen and J. Han, “Data mining: An Overview from a Database Perspective,” IEEE Transactions on Knowledge and Data Engineering, 8(6), pp. 866-883, 1996.
[13]H. Chen, B. Schatz, T. Ng, J. Martinez, A. Kirchhoff, and C. Lin, “A Parallel Computing Approach to Creating Engineering Concept Spaces for Semantic Retrieval: The Illinois Digital Library Initiative Project,” IEEE Transactions on Pattern Analysis and Machine Intelligence, 18(8), August. 1996.
[14]W. B. Croft, “What Do People Want from Information Retrieval?,” D-Lib Magazine, Nov. 1995. Available at http://www.dlib.org/dlib/november95/11croft.html.
[15]C.J. Crouch, “An Approach to the Automatic Construction of Global Thesauri,” Information Processing & Management, 26(5), pp.629-640, 1990.
[16]T.E. Dunning, “Accurate Methods for the Statistics of Surprise and Coincidence,” Computational Linguistics, 19(1), pp. 61-74, 1993.
[17]E.N. Efthimiadis, “A User-centred Evaluation of Ranking Algorithms for Interactive Query Expansion,” Proceedings of the 16th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, 1993, pp.146-159.
[18]K. Eguchi, H. Ito, A. Kumamoto, and Y. Kanata, “Adaptive and Incremental Query Expansion for Cluster-based Browsing,” Proceedings of 1999 International Conference on the 6th Database Systems for Advanced Applications, 1999, pp. 25-34.
[19]E. Erwin, K. Obermayer, and K. Schylten, “II: Self-organizing maps: Ordering, convergence properties and energy functions,” Biological Cybernetics, 67, pp. 35-45, 1992.
[20]R. Fano, Transmission of Information, MIT Press, Cambriddge, Ma, 1961.
[21]C. Fellbaum, An Electronic Lexical Database, MIT Press, Cambridge, Mass., 1998.
[22]G.W. Furnas, T.K. Landauer, L.M. Gomez, and S.T. Dumais, “The Vocabulary Problem in Human-System Communication,” Communications of the ACM, 30, pp. 964-971, Nov. 1987.
[23]G. Grefenstette, “Use of Syntactic Context to Produce Term Association Lists for Retreival,” Proceedings of the 15th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, 1992, pp. 89-97.
[24]J. Han, M. Kamber, Data mining Concepts and Techniques, Morgan Kaufmann Publishers. 2000.
[25]J. Han, J. Pei, and Y. Yin, “Mining Frequent Patterns without Candidate Generation,” Proceedings of 2000 ACM SIGMOD International Conference on Management of Data, May 2000.
[26]J. Hipp, U. Guntzer, and G. Nakhaeizadeh, “Algorithms for Association Rule Mining — A General Survey and Comparison,” Proceedings of the 6th Annual International ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2000, pp. 58-64.
[27]B. Jansen and A. Spink, “Methodological Approach in Discovering User Search Patterns Through Web Log Analysis,” Bulletin of the American Society for Information Science and Technology, 27(1), pp. 15-17, 2000.
[28]B. Jansen, A. Spink, and T. Saracevic, “Real life, real users, and real needs: A study and analysis of user queries on the web,” Information Processing and Management, 36(2), pp. 207-227, 2000.
[29]K. Jarvelin, J. Kristensen, T. Niemi, E. Sormunen, and H. Keskustalo, “A Deductive Data Model for Query Expansion,” Proceedings of the 19th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, 1996, pp. 235-243.
[30]Y. Jing and Croft W.B., “An Association Thesaurus for Information Retrieval,” Technical Report 94-17, Boston, Umass.
[31]Sparck-Jones K, “Notes and References on Early Classification Work,” SIGIR Forum, 25(1), pp. 10-17, 1991.
[32]J. Koenemann and N.J. Belkin, “A Case for Interaction: A Study of Interactive Information Retrieval Behavior and Effectivess,” Proceedings of CHI96 International Conference on Human Computer Interaction, 1996, pp. 205-212.
[33]R. Kosala and H. Blockeel, “Web Mining Research: A Survey,” SIGKDD Explorations, 2(1), Jun. 2000.
[34]Steve Lawrence, “Context in Web Search,” IEEE Data Engineering Bulletin, 23(3), pp. 25-32, 2000.
[35]E. Lesk, “Word-word Association in document retrieval systems,” American Documentation, 20(1), pp. 27-38, 1969.
[36]Wen-Syan Li, and D. Agrawal, “Supporting Web Query Expansion Efficiently Using Multi-Granularity Indexing and Query Processing,” Data & Knowledge Engineering, 35, pp. 239-257, 2000.
[37]S.H. Lin, M.C. Chen, J.M. Ho, M.T. Ko, and Y.M. Huang, “ACIRD: Intelligent Internet Documents Organization and Retrieval,” Workshop on Research Issues in Data Mining and Knowledge Discovery, ACM SIGMOD Conference, Jun. 1998.
[38]H. Liu, and R. Setiono, “Some Issue on Scalable Feature Selection,” Expert Systems with Applications, 15, pp. 333-339, 1998.
[39]Z.-P. Lo, M. Fujita, and B. Bavarian, “Analysis of neighborhood interaction in Kohonen neural networks,” Proceedings of 6th International Parallel Processing Symposium, 1991, pp.247-249.
[40]M. Magennis and C.J. van Rijsbergen, “The Potential and Actual Effectiveness of Interactive Query Expansion,” Proceedings of the 20th Annual International ACM SIGIR Conference on Research and Development in information Retrieval, 1997, pp.324-332.
[41]J. McDonald, W. Ogden, and P. Foltz, “Interactive Information Retrieval using Term Relationship Networks,” Proceedings of the 6th Text Retrieval Conference, 1997.
[42]G.A. Miller, “WordNet: A Lexical Database,” Comm. ACM, 38(11), 1993, pp. 39-41.
[43]J. Minker, G.A. Wilson, and B.H. Zimmerman, “An Evaluation of Query Expansion by the Addition of Clustered terms for a Document Retrieval System,” Information Storage and Retrieval, 8(6), 1972, pp. 329-348.
[44]Tom Mitchell, Machine Learning, McCraw Hill, 1996.
[45] S. Miyamoto and K. Nakayama, “Fuzzy Information Retrieval Based on a Fuzzy Pseudothesaurus,” IEEE Trans. Syst., Man, Cybern., 16(2), pp. 278-282, 1986.
[46]B. Mobasher, R. Cooley and J. Srivastava, “Web Mining: Information and Pattern Discovery on the World Wide Web,” Proceedings of the 9th IEEE International Conference on Tools with Artificial Intelligence, Nov. 1997.
[47]B. Mobasher, N. Jain and E. Han and J. Srivastava, “Web Mining: Pattern Discovery from World Wide Web Transactions,” Technical Report TR96-050, Department of Computer Science, University of Minnesota, 1996.
[48]D.I. Moldovan and R. Mihalcea, “Using WordNet and Operators to Improve Inernet Searches,” IEEE Internet Computing, Jan and Feb. 2000.
[49]H. Ouahid and A. Karmouch, ”Converting Web Pages into Well-formed XML Documents,” IEEE International Conference on Communications, 1999, pp. 676-680.
[50]G. Piatetsky-Shapiro and W.J. Frawley, “Knowledge Discovery in Database,” AAAI/MIT Press, 1991.
[51]A. Pretschner, and S. Gauch, “Ontology Based Personalized Search,” Proceedings of the 11th IEEE International Conference on Tools with Artificial Intelligence, 1999, pp. 391-398.
[52]Y. Qiu and H.P. Frei, “Applying a Similarity Thesaurus to a Large Collection for Information Retrieval,” Technical Report. Dept. Computer Science, Swiss Federal Institute of Technology (ETH), Jan 1995.
[53]Y. Qiu and H.P. Frei, “Concept Based Query Expansion,” Proceedings of the 16th ACM SIGIR International Conference on Research and Development in Information Retrieval, 1993, pp. 160-169.
[54]H. Ritter, T. Martinetz, and K. Schulten, “Neural Computation and Self-Organizing Maps: An Introduction,” Reading, MA: Addison-Wesley, 1992.
[55]K. Rodden, “About 23 million documents match your query…,” Proceedings of the conference on CHI 98 summary: human factor in computing systems, 1998, pp. 64-65.
[56]J.J. Rocchio, “Relevance feedback in information retrieval,” In the SMART Retrieval System-- Experiments in Automatic Document Processing, pp. 313-323, Englewood Cliffs, NJ, 1971. Prentice Hall, Inc.
[57]G. Ruge, “Experiments on Linguistically-Based Term Associations,” Information Processing & Management, 28(3), 1992, pp. 317-332.
[58]A. Rungsawang, A Tangpong, P. Laohawee, and T. Khampachua, “Novel Query Expansion Technique using Apriori Algorithm,” Proceedings of the 8th Text REtrieval Conference (TREC-8), 1999.
[59]G. Salton and C. Buckley, “Improving Retrieval Performance by Relevance Feedback,” Journal of the American Society for Information Science, 41(4), pp. 288-297, 1990.
[60]G. Salton, Automatic Text Processing: The Transformation, Analysis, and Retrieval of Information by Computer, Addison Wesley, 1989.
[61]G. Salton and M. J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, 1983.
[62]G. Slaton, A. Wong, and C. Yang, “A Vector Space Model for Information Retrieval,” Communications of the ACM, 18(11), pp. 613-620, Nov. 1975.
[63]G. Salton and M.E. Lesk, “Computer Evaluation of Index and Text Processing,” in The SMART Retrieval System: Experiments in Automatic Document Processing, G. Salton,ed., Prentice Hall, Englewood Cliffs, N.J., 1971, pp. 143-180.
[64]A. Savasere, E. Omiecinski, and S. Navathe, “An Efficient Algorithm for Mining association Rules in Large Databases,” Proceedings of the 21th Conference on Management of Data, Jun. 1998, pp. 432-443.
[65]B.R. Schatz, E.H. Johnson, and P.A. Cochrane, “Interactive Term Suggestion for Users of Digital Libraries: Using Subject Thesauri and Co-occurrence Lists for Information Retrieval,” Proceedings of the 1st ACM International Conference on Digital Libraries, 1996, pp. 126-133.
[66]F. Sebastiani, “Interactive Query Expansion with Automatically Generated Category-Specific Thesauri,” Text Databases and Document Management: Theory and Practice, Idea Group Publishing, 2001.
[67]F. Sebastiani, “Automated Generation of Category-Specific Thesauri for Interactive Query Expansion,” Proceedings of the 9th International Databases Conference on Heterogeneous and Internet Databases, 1999, pp. 429-432.
[68]C. Silverstein, M. Henzinger, H. Marais, and M. Moricz, “Analysis of a Very Large AltaVista Query Log,” Technical Report 014, Systems Research Center, USA, 1998.
[69]A. Singhal, M. Mitra, C. Buckley, “Learning Routing Queries in a Query Zone,” Proceedings of SIGIR ''97, Aug. 1997, pp. 25-32.
[70]K. Sparck-Jones and E.B. Barber, “What makes an effective?” J. of the ASIS, 18, 1983, pp.166-175.
[71]A. Spink, “Term Relevance Feedback and Query Expansion: Relation to Design,” Proceedings of the 17th Annual International ACM SIGIR Conference on Research and Development in information Retrieval, 1994, pp. 81-90.
[72]R. Srikant, Q. Vu, and R. Agrawal, “Mining Association Rule with Item Constraints,” Proceedings of the 3rd International Conference on KDD and Data Mining, Aug. 1997, pp. 67-73.
[73]K. Sycara, “MultiAgent systems,” AI Magazine, 19(2), pp. 69-78, 1998.
[74]Suh-Ying Wur and Yungho Leu, “An Effective Boolean Algorithm for Mining Association Rule in Large Databases,” Proceedings of the 6th International Conference on Database Systems for Advanced Applications, 1998.
[75]Y. Yang and J.O. Pedersen, “A Comparative Study on Feature Selection in Text Categorization,” Proceedings of the 14th International Conference on Machine Learning, 1997.
[76]O. Yasushi, M. Hiroko, N. Masumi, and H. Sakiko, “Structuring and Expanding Queries in the Probabilistic Model,” Proceedings of the 9th Text Retrieval Conference, 2000.
URL List:
[77]Altavista, Available at http://www.altavista.com
[78]ANSI Online, Available at http:// www.ansi.org
[79]Ho Tu Bao, “Knowledge Discovery and Data Mining Techniques and Practice,” Available at http://203.162.7.85/unescocourse/knowlegde/knowlegd.htm
[80]Bonnie Bills, WWW: Web World Wide, CNET, Available at http://www.cnet.com
[81]DVL/Verity Stop Word List, Available at http://dvl.dtic.mil: 8100/stop_list.html
[82]Excite, Available at http://www.excite.com
[83]Google, Available at http://www.google.com
[84]IREX, Available at http://www.cs.nyu.edu/cs/projects/proteus/irex/index-e.html
[85]ResearchIndex, Available at http://citeseer.nj.nec.com/cs
[86]The Coursebot system, Available at http://coursebot.et.ntust.edu.tw
[87]The Emerging Digital Economy, Available at http://www.ecommerce.gov
[88]WordNet, Available at http://www.cogsci.princeton.edu/~wn
[89]World Wide Web Consortium, Hypertext Markup Language Specification, Available at http://www.w3.org.