유사한 인기도 추세를 갖는 웹 객체들의 클러스터링 = Clustering of Web Objects with Similar Popularity Trends

다국어 초록 (Multilingual Abstract)

Huge amounts of various web items such as keywords, images, and web pages are being made widely available on the Web. The popularities of such web items continuously change over time, and mining temporal patterns in popularities of web items is an important problem that is useful for several web applications. For example, the temporal patterns in popularities of search keywords help web search enterprises predict future popular keywords, enabling them to make price decisions when marketing search keywords to advertisers. However, presence of millions of web items makes it difficult to scale up previous techniques for this problem. This paper proposes an efficient method for mining temporal patterns in popularities of web items. We treat the popularities of web items as time-series, and propose gapmeasure to quantify the similarity between the popularities of two web items. To reduce the computation overhead for this measure, an efficient method using the Fast Fourier Transform (FFT) is presented. We assume that the popularities of web items are not necessarily following any probabilistic distribution or periodic. For finding clusters of web items with similar popularity trends, we propose to use a density-based clustering algorithm based on the gap measure. Our experiments using the popularity trends of search keywords obtained from the Google Trends web site illustrate the scalability and usefulness of the proposed approach in real-world applications.

국문 초록 (Abstract)

인터넷이 광범위하게 활용됨에 따라 검색 키워드, 멀티미디어 객체, 웹 페이지, 블로그 등의 다양한 웹 객체들이 크게 증가하고 있다. 이러한 웹 객체들의 인기도는 시간에 따라 변화하며, 그러한 웹 객체 인기도의 시간적 패턴에 대한 마이닝이 여러 가지 웹 응용에 필요한 중요한 연구 과제가 되고 있다. 예를 들어, 검색 키워드에 대한 인기도 패턴의 분석은 앞으로 인기가 높아질 키워드를 미리 예측할 수 있게 하여 광고주들에게 키워드를 판매하기 위한 가격을 결정하는 데에 중요한 자료가 될 수 있다. 하지만, 웹 객체 인기도가 시간에 따라 변화하고 웹 객체의 개수가 매우 방대하다는 특성으로 인하여 웹 객체 인기도에 대한 분석은 매우 어려운 문제이다. 본 논문에서는 웹 객체 인기도의 시간적 패턴을 마이닝하기 위한 효율적인 알고리즘을 제안한다. 본 논문은 웹 객체 인기도를 시계열로 표현하고, 두 웹 객체 인기도 간의 유사성을 측정하기 위하여 gap 척도를 제안한다. gap 척도의 효율적인 계산을 위하여 FFT를 활용한 알고리즘을 제안하고, 밀도기반 클러스터링 알고리즘을 이용하여 유사한 인기도 추세를 갖는 웹 객체들의 클러스터를 생성한다. 본 논문에서는 웹 객체 인기도가 특정 분포를 따르거나 주기적이라고 가정하지 않는다. Google Trends 웹 사이트로부터 구한 검색 키워드 인기도를 이용한 실험을 통하여, 제안된 알고리즘이 실세계 응용에서 유용함을 보인다.

참고문헌 (Reference)

• 1 R. Kosala, "Web Mining Research: A Survey" 2 (2): 1-15, 2000
• 2 M. R. Henzinger, "Web Information Retrieval–An Algorithmic Perspective" 1-8, 2000
• 3 C. Elkan, "Using the Triangle Inequality to Accelerate k-Means" 147-153, 2003
• 4 C. Ratanamahatana, "Three Myths about Dynamic Time Warping Data Mining" 506-510, 2005
• 5 M. Nanni, "Speeding-Up Hierarchical Agglomerative Clustering in Presence of Expensive Metrics" 378-387, 2005
• 6 J. McQueen, "Some Methods for Classification and Analysis of Multivariate Observation" 281-297, 1967
• 7 S. Chien, "Semantic Similarity between Search Engine Queries Using Temporal Correlation" 2-11, 2005
• 8 M. G. Elfeky, "Periodicity Detection in Time Series Databases" 17 (17): 875-887, 2005
• 9 E. J. Keogh, "On the Need for Time Series Data Mining Benchmarks: A Survey and Empirical Demonstration" 102-111, 2002
• 10 M. Ankerst, "OPTICS: Ordering Points To Identify the Clustering Structure" 49-60, 1999
• 11 W. H. Press, "Numerical Recipes in C: The Art of Scientific Computing" Cambridge University Press 1992
• 12 R. Baeza-Yates, "Modern Information Retrieval" Addison Wesley 1999
• 13 P. J. Carrington, "Models and Methods in Social Network Analysis" Cambridge University Press 2005
• 14 E. J. Keogh, "LB_Keogh Supports Exact Indexing of Shapes under Rotation Invariance with Arbitrary Representations and Distance Measures" 882-893, 2006
• 15 J. Lin, "Iterative Incremental Clustering of Time Series" 106-122, 2004
• 16 M. Vlachos, "Indexing Multi-Dimensional Time-Series with Support for Multiple Distance Measures" 216-225, 2003
• 17 M. Vlachos, "Identifying Similarities, Periodicities and Bursts for Online Search Queries" 131-142, 2004
• 18 Y.-S. Moon, "General Match:A Subsequence Matching Method in Time-Series Databases Based on Generalized Windows" 382-393, 2002
• 19 B.-K. Yi, "Fast Time Sequence Indexing for Arbitrary Lp Norms" 385-394, 2000
• 20 C. Faloutsos, "Fast Subsequence Matching in Time-Series Databases" 419-429, 1994
• 21 E. J. Keogh, "Exact Indexing of Dynamic Time Warping" 406-417, 2002
• 22 R. Agrawal, "Efficient Similarity Search in Sequence Databases" 69-84, 1993
• 23 B.-K. Yi, "Efficient Retrieval of Similar Time Sequences Under Time Warping" 201-208, 1998
• 24 Y.-S. Moon, "Duality-Based Subsequence Matching in Time-Series Databases" 263-272, 2001
• 25 J. G. Proakis, "Digital Signal Processing" Prentice Hall 2006
• 26 R. C. Gonzalez, "Digital Image Processing" Prentice Hall 2002
• 27 J. Han, "Data Mining: Concepts and Techniques" Morgan Kaufmann 2005
• 28 T. Zhang, "BIRCH: An Efficient Data Clustering Method for Very Large Databases" 103-114, 1996
• 29 Y. Sakurai, "AutoLag: Automatic Discovery of Lag Correlations in Stream Data" 159-160, 2005
• 30 J. Lin et al., "An MPAA-Based Iterative Clustering Algorithm Augmented by Nearest Neighbors Search for Time-Series Data Streams" 333-342, 2005
• 31 A. N. Langville, "A Survey of Eigenvector Methods of Web Information Retrieval" 47 (47): 15-191, 2005
• 32 M. Ester, "A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise" 226-231, 1996