臺灣博碩士論文加值系統

社交多媒體網路近年來已成為一個即時且有效的溝通平台。無論
新聞、自然災害或是節慶等消息，人們常藉由社交多媒體網路來分享
並進行資訊的傳播。更由於手持式裝紙的普及與蓬勃發展，人們可以
更即時的藉由社交多媒體平台發布即時訊息，也因此社交多媒體上的
資訊更能直接反映時事。然而，由於巨量的資訊被發布於社交多媒體
平台，對使用者而言，要將所有的訊息街進行瀏覽是相當耗時且費力
的。因此，如何有效地探勘這些巨量的資料或提供這些一目了然的資
訊摘要，便成為一極具潛力的研究方向(例如焦點新聞探索、交通狀
況監測以及自然災害監控)。另一方面，雖然名人、公司行號與各種
組織常透過社交多媒體網路來與其粉絲或客戶進行互動，但由於資
料量過於龐大且會隨時間增加。為了要能夠有效分析這些訊息，藉
由各種不同的，在本論文中，我們首先提出一個超連結探勘方法(簡
稱SURLMINE)來協助找出多媒體網路中值得注意的超連結。有別於以
往的尋找方式，超連結由於沒有語言上的限制，可以使得訊息來源更
加完整與全面。此外，根據我們實驗中所發現的結果，目前Twitter上
以英文發表之資料量淤占總資料量的35%，意即透過超連結的方式來
提供訊息，不但可以提高訊息的完整度，亦可以減少因為不同語言翻
譯所帶來的誤差，因而更有效率的達到即時推薦訊息的效果。此外，
為了能夠有效的掌握訊息串流的概要，我們另外提出一增益式摘要彙
總法，讓使用者能夠一目了然知道整個訊息串流的概要。透過真實資
料實驗，超連結探勘能以高達92%的準確度找出重要的超連結，而增
益式摘要叢集法也能有效找出重要的叢集，並且能夠將離群資料有效
排除。

Social media platforms have emerged as a powerful and real-time means of communication recently. People are using social media to share and
exchange information about any events, ranging from breaking news stories to natural disasters and information about local festivals. With the help of rapid development of mobile technologies, messages posted in social media can typically reflect these events as they happen. However, since the dramatic growth of the social media data, it becomes infeasible for users to read all posts or comments. Therefore, mining and summarizing rich user generated content in social media can present great opportunities for developing many potential applications (e.g., breaking news discovery, traffic monitoring, and natural disaster monitoring.) On the other hand, the celebrities, corporations, and organizations also set up social pages to interact with their fans and the public. Although it is important for them to understand how their fans and customers reacting to certain topics and content, the volume and the rapidly increment nature of social media make it time-consuming to get the overview of a comment stream. Therefore, in this dissertation, we first propose a significant URL mining approach (named SURLMINE) to rank the URL on social media based on various features. Note that URL is a global language without language dependency. It is also worthy to know that only 35\% of tweets on Twitter are posted in English. In other words, mining social media content through URL is able to involve more data from different languages. Most of all, it is efficient and there is no lost in translation. On the other hand, to summarize the comment stream, we propose a real-time incremental short
text summarization on comment streams (abbreviated as IncreSTS) to provide an at-a-glance presentation that users can easily and rapidly understand the main points of similar comments. Our experiments conducted on real datasets show that the SURLMINE can reach up to 92\% of precision based on YouTube datasets and the increSTS possesses the advantages of high efficiency, high scalability, and better handling outliers on the target problem.

口試委員會審定書 i
致謝 iii
中文摘要 v
Abstract vii
1 Introduction 1
1.1 Motivation and Overview of the Dissertation 1
1.1.1 SURLMINE 3
1.1.2 IncreSTS 3
1.1.3 Organization of the Dissertation 4
2 SURLMINE: Significant URLs Mining for Large-Scale and Real-time Social
Streams 5
2.1 Introduction 5
2.2 Related Work 7
2.3 Data Crawling and Pre-processing 9
2.3.1 Real-time Crawling 10
2.3.2 URL Statistics 10
2.4 Significant URLs Mining 12
2.4.1 Characteristic Features of Social Messages 13
2.4.2 Follower-Friend Ratio 13
2.4.3 Language Distribution 13
2.4.4 Duration and Period 14
2.4.5 Decay Model 15
2.4.6 SURLMINE Algorithm 15
2.5 Experiments 17
2.5.1 Experimental Design 17
2.5.2 Precision and Efficiency Issues 18
2.6 Summary 20
3 IncreSTS: Towards Real-Time Incremental Short Text Summarization on
Comment Streams from Social Network Services 21
3.1 Introduction 21
3.2 Preliminaries 25
3.2.1 Problem Description and System Model26
3.2.2 Related Works 27
3.2.3 Distinguishing Features of IncreSTS 32
3.3 Term Vector Model Representation of Comments 34
3.4 Definitions of Clustering Details 35
3.5 Incremental Short Text Summarization 38
3.5.1 BatchSTS Algorithm: Batch Version 38
3.5.2 IncreSTS Algorithm: Incremental Version 40
3.5.3 Visualization Interface 44
3.6 Performance Evaluation 46
3.6.1 Experimental Design 46
3.6.2 Efficiency Issues 48
3.6.3 Effectiveness Issue49
3.6.4 Effects of Parameters 54
3.6.5 Enhancement of Data Structure Design 55
3.6.6 Case Study and Discussion 56
3.7 Summary 58
4 Conclusion 59
4.1 Conclusion and Future Work 59
Bibliography 61

[1] S. Yardi and D. Boyd, “Tweeting from the town square: Measuring geographic local networks.,” in ICWSM, pp. 194–201, 2010.
[2] H. Becker, M. Naaman, and L. Gravano, “Beyond trending topics: Real-world event identification on twitter.,” ICWSM, vol. 11, no. 2011, pp. 438–441, 2011.
[3] A. Tumasjan, T. O. Sprenger, P. G. Sandner, and I. M. Welpe, “Predicting elections with twitter: What 140 characters reveal about political sentiment.,” ICWSM, vol. 10, no. 1, pp. 178–185, 2010.
[4] E. Khabiri, J. Caverlee, and C.-F. Hsu, “Summarizing User-Contributed Comments,” Proc. of the 5th International AAAI Conference on Weblogs and Social Media (ICWSM’11), pp. 534–537, 2011.
[5] J. Chen, R. Nairn, L. Nelson, M. Bernstein, and E. H. Chi, “Short and Tweet: Experiments on Recommending Content from Information Streams,” Proc. of the ACM SIGCHI Conference on Human Factors in Computing Systems (CHI’10), pp. 1185– 1194, 2010.
[6] H. Takamura, H. Yokono, and M. Okumura, “Summarizing a Document Stream,” Proc. of the 33rd European Conference on IR Research on Advances in Information Retrieval (ECIR’11), pp. 177–188, 2011.
[7] D. Chakrabarti and K. Punera, “Event Summarization Using Tweets,” Proc. of the 5th International AAAI Conference on Weblogs and Social Media (ICWSM’11), pp. 66–73, 2011.
[8] H. Becker, M. Naaman, and L. Gravano, “Selecting Quality Twitter Content for Events,” Proc. of the 5th International AAAI Conference on Weblogs and Social Media (ICWSM’11), pp. 442–445, 2011.
[9] B. Sriram, D. Fuhry, and M. Demirbas, “Short Text Classification in Twitter to Improve Information Filtering,” Proc. of the 33rd International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR’10), pp. 841– 842, 2010.
[10] K. D. Rosa, R. Shah, B. Lin, A. Gershman, and R. Frederking, “Topical Clustering of Tweets,” Proc. of the ACM SIGIR’s 3rd Workshop on Social Web Search and Mining (SWSM’11), 2011.
[11] F. Perez-Tellez, D. Pinto, J. Cardiff, and P. Rosso, “On the Difficulty of Clustering Company Tweets,” Proc. of the 2nd International Workshop on Search and Mining User-Generated Contents (SMUC’10), pp. 95–102, 2010.
[12] “TweetFeel,” http://www.tweetfeel.com/.
[13] N. A. Diakopoulos and D. A. Shamma, “Characterizing Debate Performance via Aggregated Twitter Sentiment,” Proc. of the ACM SIGCHI Conference on Human Factors in Computing Systems (CHI’10), pp. 1195–1198, 2010.
[14] C.-T. Li, C.-Y. Wang, C.-L. Tseng, and S.-D. Lin, “MemeTube: A Sentiment-based Audiovisual System for Analyzing and Displaying Microblog Messages,” Proc. of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies (ACL-HCT’11), pp. 32–37, 2011.
[15] J. Bollen, H. Mao, and A. Pepe, “Modeling Public Mood and Emotion: Twitter Sentiment and Socio-Economic Phenomena,” Proc. of the 5th International AAAI Conference on Weblogs and Social Media (ICWSM’11), pp. 450–453, 2011.
[16] A. Tumasjan, T. O. Sprenger, P. G. Sandner, and I. M. Welpe, “Predicting Elections with Twitter: What 140 Characters Reveal about Political Sentiment,” Proc. of the 4th International AAAI Conference on Weblogs and Social Media (ICWSM’10), pp. 178–185, 2010.
[17] H. Kwak, C. Lee, H. Park, and S. Moon, “What is twitter, a social network or a news media?,” in Proceedings of the 19th international conference on World wide web, pp. 591–600, ACM, 2010.
[18] A. Nagpal, S. Hangal, R. R. Joyee, and M. S. Lam, “Friends, romans, countrymen: lend me your urls. using social chatter to personalize web search,” in Proceedings of the ACM 2012 conference on Computer Supported Cooperative Work, pp. 461–470, ACM, 2012.
[19] J. Chen, R. Nairn, L. Nelson, M. Bernstein, and E. Chi, “Short and tweet: experiments on recommending content from information streams,” in Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, pp. 1185–1194, ACM, 2010.
[20] A. I. Schein, A. Popescul, L. H. Ungar, and D. M. Pennock, “Methods and metrics for cold-start recommendations,” in Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, pp. 253–260, ACM, 2002.
[21] Y. Duan, L. Jiang, T. Qin, M. Zhou, and H.-Y. Shum, “An empirical study on learning to rank of tweets,” in Proceedings of the 23rd International Conference on Computational Linguistics, pp. 295–303, Association for Computational Linguistics, 2010.
[22] J. Sankaranarayanan, H. Samet, B. E. Teitler, M. D. Lieberman, and J. Sperling, “Twitterstand: news in tweets,” in Proceedings of the 17th acm sigspatial international conference on advances in geographic information systems, pp. 42–51, ACM, 2009.
[23] A. Dong, R. Zhang, P. Kolari, J. Bai, F. Diaz, Y. Chang, Z. Zheng, and H. Zha, “Time is of the essence: improving recency ranking using twitter data,” in Proceedings of the 19th international conference on World wide web, pp. 331–340, ACM, 2010.
[24] M. Mathioudakis and N. Koudas, “Twittermonitor: trend detection over the twitter stream,” in Proceedings of the 2010 ACM SIGMOD International Conference on Management of data, pp. 1155–1158, ACM, 2010.
[25] J. Kleinberg, “Bursty and hierarchical structure in streams,” Data Mining and Knowledge Discovery, vol. 7, no. 4, pp. 373–397, 2003.
[26] J. Allan, J. G. Carbonell, G. Doddington, J. Yamron, and Y. Yang, “Topic detection and tracking pilot study final report,” 1998.
[27] Y. Yang, T. Pierce, and J. Carbonell, “A study of retrospective and on-line event detection,” in Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, pp. 28–36, ACM, 1998.
[28] C. Castillo, M. Mendoza, and B. Poblete, “Information credibility on twitter,” in Proceedings of the 20th international conference on World wide web, pp. 675–684, 2011.
[29] S. K. L. Al Mamunur Rashid, G. Karypis, and J. Riedl, “Clustknn: a highly scalable hybrid model-& memory-based cf algorithm,” Proceeding of WebKDD, 2006.
[30] B. M. Sarwar, G. Karypis, J. Konstan, and J. Riedl, “Recommender systems for large-scale e-commerce: Scalable neighborhood formation using clustering,” in Prceedings of the fifth international conference on computer and information technology, vol. 1, 2002.
[31] F. Maggi, A. Frossi, S. Zanero, G. Stringhini, B. Stone-Gross, C. Kruegel, and G. Vigna, “Two years of short urls internet measurement: security threats and countermeasures,” in Proceedings of the 22nd international conference on World Wide Web, pp. 861–872, ACM, 2013.
[32] M. Cha, H. Haddadi, F. Benevenuto, and P. K. Gummadi, “Measuring user influence in twitter: The million follower fallacy.,” Icwsm, vol. 10, no. 10-17, p. 30, 2010.
[33] “YouTube,” http://www.youtube.com/.
[34] “Facebook,” http://www.facebook.com/.
[35] A. Marcus, M. S. Bernstein, O. Badar, D. R. Karger, S. Madden, and R. C. Miller,“TwitInfo: Aggregating and Visualizing Microblogs for Event Exploration,” Proc. of the ACM SIGCHI Conference on Human Factors in Computing Systems (CHI’11), pp. 227–236, 2011.
[36] J. Sankaranarayanan, H. Samet, B. E. Teitler, M. D. Lieberman, and J. Sperling, “TwitterStand: News in Tweets,” Proc. of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM-GIS’09), pp. 42–51, 2009.
[37] J.-Y. Weng, C.-L. Yang, B.-N. Chen, Y.-K. Wang, and S.-D. Lin, “IMASS: An Intelligent Microblog Analysis and Summarization System,” Proc. of the ACL/HLT Systems Demonstrations (ACL-HLT’11), pp. 133–138, 2011.
[38] “Amazon,” http://www.amazon.com/.
[39] “TripAdvisor,” http://www.tripadvisor.com/.
[40] “HotelClub,” http://www.hotelclub.com/.
[41] Y. Lu, C. Zhai, and N. Sundaresan, “Rated Aspect Summarization of Short Comments,”Proc. of the 18th International Conference on World Wide Web (WWW’09), pp. 131–140, 2009.
[42] B. Liu, M. Hu, and J. Cheng, “Opinion Observer: Analyzing and Comparing Opinions on the Web,” Proc. of the 14th International Conference on World Wide Web(WWW’05), pp. 342–351, 2005.
[43] B. Sharifi, M.-A. Hutton, and J. K. Kalita, “Experiments in Microblog Summarization,”Proc. of the 2nd IEEE International Conference on Social Computing (Social-Com’10), pp. 49–56, 2010.
[44] S. Harabagiu and A. Hickl, “Relevance Modeling for Microblog Summarization,”Proc. of the 5th International AAAI Conference on Weblogs and Social Media (ICWSM’11), pp. 514–517, 2011.
[45] M. Hu, A. Sun, and E.-P. Lim, “Comments-Oriented Blog Summarization by SentenceExtraction,” Proc. of the 16th ACM International Conference on Information and Knowledge Management (CIKM’07), pp. 901–904, 2007.
[46] M. Hu, A. Sun, and E.-P. Lim, “Comments-Oriented Document Summarization: Understanding Documents with Readers’ Feedback,” Proc. of the 31st International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR’ 08), pp. 291–298, 2008.
[47] Z. Yang, K. Cai, J. Tang, L. Zhang, Z. Su, and J. Li, “Social Context Summarization,” Proc. of the 34th International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR’11), pp. 255–264, 2011.
[48] K. Dave, S. Lawrence, and D. M. Pennock, “Mining the Peanut Gallery: Opinion Extraction and Semantic Classification of Product Reviews,” Proc. of the 12th International Conference on World Wide Web (WWW’03), pp. 519–528, 2003.
[49] M. Hu and B. Liu, “Mining and Summarizing Customer Reviews,” Proc. of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’04), pp. 168–177, 2004.
[50] L. Zhuang, F. Jing, and X.-Y. Zhu, “Movie Review Mining and Summarization,” Proc. of the 15th ACM International Conference on Information and Knowledge Management (CIKM’06), pp. 43–50, 2006.
[51] S. Baccianella, A. Esuli, and F. Sebastiani, “Multi-facet Rating of Product Reviews,” Proc. of the 31st European Conference on IR Research on Advances in Information Retrieval (ECIR’09), pp. 461–472, 2009.
[52] N. K. Gupta, “Extracting Descriptions of Problems with Product and Services from Twitter Data,” Proc. of the ACM SIGIR’s 3rd Workshop on Social Web Search and Mining (SWSM’11), 2011.
[53] A. Hassan, D. Radev, J. Cho, and A. Joshi, “Content Based Recommendation and Summarization in the Blogosphere,” Proc. of the 3rd International AAAI Conference on Weblogs and Social Media (ICWSM’09), pp. 34–41, 2009.
[54] E. M. Daly, M. Muller, D. R. Millen, and L. Gou, “Social Lens: Personalization Around User Defined Collections for Filtering Enterprise Message Streams,” Proc. of the 5th International AAAI Conference on Weblogs and Social Media (ICWSM’11), pp. 113–120, 2011.
[55] F. Liu, Y. Liu, and F. Weng, “Why is ”SXSW” trending? Exploring Multiple Text Sources for Twitter Topic Summarization,” Proc. of the ACL/HLT Workshop on Language in Social Media (ACL-LSM’11), pp. 66–75, 2011.
[56] M. S. Bernstein, B. Suh, L. Hong, J. Chen, S. Kairam, and E. H. Chi, “Eddi: Interactive Topic-based Browsing of Social Status Streams,” Proc. of the 23nd Annual ACM Symposium on User Interface Software and Technology (UIST’10), pp. 303– 312, 2010.
[57] B. O’Connor, M. Krieger, and D. Ahn, “TweetMotif: Exploratory Search and TopicSummarization for Twitter,” Proc. of the 4th International AAAI Conference on Weblogs and Social Media (ICWSM’10), pp. 384–385, 2010.
[58] M. Michelson and S. A. Macskassy, “Discovering Users’ Topics of Interest on Twitter: A First Look,” Proc. of the 4th Workshop on Analytics for Noisy Unstructured Text Data (AND’10), pp. 73–79, 2010.
[59] H. Becker, M. Naaman, and L. Gravano, “Learning Similarity Metrics for Event Identification in Social Media,” Proc. of the 3rd ACM International Conference on Web Search and Data Mining (WSDM’10), pp. 291–300, 2010.
[60] J. Weng and B.-S. Lee, “Event Detection in Twitter,” Proc. of the 5th International AAAI Conference on Weblogs and Social Media (ICWSM’11), pp. 401–408, 2011.
[61] H. Sayyadi, M. Hurst, and A. Maykov, “Event Detection and Tracking in Social Streams,” Proc. of the 3rd International AAAI Conference on Weblogs and Social Media (ICWSM’09), pp. 311–314, 2009.
[62] B. Pang and L. Lee, “Opinion Mining and Sentiment Analysis,” Foundations and Trends in Information Retrieval, pp. 1–135, 2008.
[63] J. A. Hartigan and M. A. Wong, “A k-means clustering algorithm,” Journal of the Royal Statistical Society. Series C (Applied Statistics), vol. 28, no. 1, pp. 100–108, 1987.
[64] L. Kaufman and P. J. Rousseeuw, “Finding groups in data: An introduction to cluster analysis (partition around medoids),” 1990.
[65] M. Ester, H.-P. Kriegel, J. Sander, and X. Xu, “A density-based algorithm for discovering clusters in large spatial databases with noise,” Proc. of the 2nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD ’96), pp. 226–231, 1996.
[66] M. Ankerst, M. M. Breunig, H.-P. Kriegel, and J. Sander, “Optics: Ordering points to identify the clustering structure,” Proc. of the 1999 ACM SIGMOD International Conference on Management Of Data (SIGMOD ’99), vol. 28, no. 2, pp. 49–60, 1999.
[67] K. C. Gowda and G. Krishna, “Agglomerative clustering using the concept of mutual nearest neighbourhood,” Pattern Recognition, vol. 10(2), vol. 10, no. 2, pp. 105–112, 1978.
[68] T. Zhang, R. Ramakrishnan, and M. Livny, “Birch: An efficient data clustering method for very large databases,” vol. 25, no. 2, pp. 103–114, 1996.
[69] D. Comaniciu and P. Meer., “Mean shift: A robust approach toward feature space analysis,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 24, no. 5, pp. 603–619, 2002.
[70] J. Allan, J. Carbonell, G. Doddington, J. Yamron, and Y. Yang, “On-line new event detection and tracking,” Proc. of the 21th annual international ACM SIGIR conference on Research and development in information retrieval(SIGR ’98), pp. 37–45, 1998.
[71] T. P. Y. Yang and J. Carbonell, “A study on retrospective and on-line event detection,” Proc. of the 21st annual international ACM SIGIR conference on Research and development in information retrieval(SIGIR ’98), pp. 28–36, 1998.
[72] D. T. Pham, S. S. Dimov, and C. D. Nguyen, “An incremental k-means algorithm,” Proc. of the Institution of Mechanical Engineers, Part C: Journal of Mechanical Engineering Science, vol. 218, no. 7, pp. 783–795, 2004.
[73] M. Ester, H.-P. Kriegel, J. Sander, M. Wimmer, and X. Xu, “Incremental clustering for mining in a data warehousing environment,” Proc. of the International Conference on Very Large Databases (VLDB ’98), vol. 98, pp. 323–333, 1998.
[74] N. Sahoo, J. Callan, G. D. R. Krishnan, and R. Padman, “Incremental hierarchical clustering of text documents,” Proc. of the 15th ACM International Conference on Information and Knowledge Management (CIKM ’06), pp. 357–366, 2006.
[75] J.-P. Mei and L. Chen, “Sumcr: A new subtopic-based extractive approach for text summarization,” Knowledge and Information Systems, vol. 31, no. 3, pp. 527–545, 2012.
[76] X. Wan and J. Yang, “Multi-document summarization using cluster-based link analysis,” Proc. of the 31st International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR ’08), pp. 299–306, 2008.
[77] V. Hatzivassiloglou, J. L. Klavans, M. L. Holcombe, R. Barzilay, M.-Y. Kan, and K. R. McKeown, “Simfinder: A flexible clustering tool for summarization,” Proc. of NAACL Workshop on Automatic Summarization, pp. 41–49, 2001.
[78] W. Xu, X. Liu, and Y. Gong, “Document clustering based on non-negative matrix factorization,” Proc. of the 26th International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR ’03), pp. 267–273, 2003.
[79] M. F. Porter, “An Algorithm for Suffix Stripping,” Program, pp. 130–137, 1980.
[80] D. M. Blei, A. Y. Ng, and M. I. Jordan, “Latent Dirichlet Allocation,” The Journal of Machine Learning Research, vol. 3, pp. 993–1022, 2003.
[81] T. Griffiths, “Gibbs Sampling in the Generative Model of Latent Dirichlet Allocation,” Technical Report, 2002.
[82]“Experimental Demo Page,” http://140.109.21.214/public/ IncreSTS/index.htm.