유사한 인기도 추세를 갖는 웹 객체들의 클러스터링
Clustering of Web Objects with Similar Popularity Trends
2
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
인터넷이 광범위하게 활용됨에 따라 검색 키워드, 멀티미디어 객체, 웹 페이지, 블로그 등의 다양한 웹 객체들이 크게 증가하고 있다. 이러한 웹 객체들의 인기도는 시간에 따라 변화하며, 그러한 웹 객체 인기도의 시간적 패턴에 대한 마이닝이 여러 가지 웹 응용에 필요한 중요한 연구 과제가 되고 있다. 예를 들어, 검색 키워드에 대한 인기도 패턴의 분석은 앞으로 인기가 높아질 키워드를 미리 예측할 수 있게 하여 광고주들에게 키워드를 판매하기 위한 가격을 결정하는 데에 중요한 자료가 될 수 있다. 하지만, 웹 객체 인기도가 시간에 따라 변화하고 웹 객체의 개수가 매우 방대하다는 특성으로 인하여 웹 객체 인기도에 대한 분석은 매우 어려운 문제이다. 본 논문에서는 웹 객체 인기도의 시간적 패턴을 마이닝하기 위한 효율적인 알고리즘을 제안한다. 본 논문은 웹 객체 인기도를 시계열로 표현하고, 두 웹 객체 인기도 간의 유사성을 측정하기 위하여 gap 척도를 제안한다. gap 척도의 효율적인 계산을 위하여 FFT를 활용한 알고리즘을 제안하고, 밀도기반 클러스터링 알고리즘을 이용하여 유사한 인기도 추세를 갖는 웹 객체들의 클러스터를 생성한다. 본 논문에서는 웹 객체 인기도가 특정 분포를 따르거나 주기적이라고 가정하지 않는다. Google Trends 웹 사이트로부터 구한 검색 키워드 인기도를 이용한 실험을 통하여, 제안된 알고리즘이 실세계 응용에서 유용함을 보인다.
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.
참고문헌 (32)
- R. Agrawal, "Efficient Similarity Search in Sequence Databases", In Proc. Int’l Conf. on Foundations and Data Organization and Algorithm (FODO),, pp.69~84 (1993)
- M. Ankerst, "OPTICS: Ordering Points To Identify the Clustering Structure", In Proc. Int’l Conf. on Management of Data, ACM SIGMOD,, pp.49~60 (1999)
- R. Baeza-Yates, "Modern Information Retrieval" (1999), Addison Wesley
- P. J. Carrington, "Models and Methods in Social Network Analysis" (2005), Cambridge University Press
- S. Chien, "Semantic Similarity between Search Engine Queries Using Temporal Correlation", In Proc. Int’l Conf. on World Wide Web (WWW),, pp.2~11 (2005)
- M. G. Elfeky, "Periodicity Detection in Time Series Databases", IEEE Trans. on Knowledge and Data Engineering (TKDE), 17(7), pp.875~887 (2005)
- C. Elkan, "Using the Triangle Inequality to Accelerate k-Means", In Proc. Int’l Conf. on Machine Learning (ICML),, pp.147~153 (2003)
- M. Ester, "A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise", In Proc. Int’l Conf. on Knowledge Discovery and Data Mining (KDD), pp.226~231 (1996)
- C. Faloutsos, "Fast Subsequence Matching in Time-Series Databases", In Proc. Int’l Conf. on Management of Data, ACM SIGMOD,, pp.419~429 (1994)
- R. C. Gonzalez, "Digital Image Processing" (2002), Prentice Hall
- J. Han, "Data Mining: Concepts and Techniques" (2005), Morgan Kaufmann
- M. R. Henzinger, "Web Information Retrieval–An Algorithmic Perspective", In Proc. Annual European Symposium (ESA), pp.1~8 (2000)
- E. J. Keogh, "Exact Indexing of Dynamic Time Warping", In Proc. Int’l Conf. on Very Large Data Bases (VLDB),, pp.406~417 (2002)
- E. J. Keogh, "On the Need for Time Series Data Mining Benchmarks: A Survey and Empirical Demonstration", In Proc. Int’l Conf. on Knowledge Discovery and Data Mining, ACM SIGKDD, pp.102~111 (2002)
- E. J. Keogh, "LB_Keogh Supports Exact Indexing of Shapes under Rotation Invariance with Arbitrary Representations and Distance Measures", In Proc. Int’l Conf. on Very Large Data Bases(VLDB),, pp.882~893 (2006)
- R. Kosala, "Web Mining Research: A Survey", SIGKDD Explorations, 2(1), pp.1~15 (2000)
- A. N. Langville, "A Survey of Eigenvector Methods of Web Information Retrieval", The SIAM Review, 47(1), pp.15~191 (2005)
- J. Lin, "Iterative Incremental Clustering of Time Series", In Proc. Int’l Conf. on Extending Database Technology (EDBT), pp.106~122 (2004)
- J. Lin et al., "An MPAA-Based Iterative Clustering Algorithm Augmented by Nearest Neighbors Search for Time-Series Data Streams", In Proc. Pacific-Asia Conf. on Advances in Knowledge Discovery and Data Mining (PAKDD),, pp.333~342 (2005)
- J. McQueen, "Some Methods for Classification and Analysis of Multivariate Observation", In Proc. Berkeley Symp. on Mathematical Statistics and Probability, pp.281~297 (1967)
- Y.-S. Moon, "Duality-Based Subsequence Matching in Time-Series Databases", In Proc. Int’l Conf. on Data Engineering (ICDE), pp.263~272 (2001)
- Y.-S. Moon, "General Match:A Subsequence Matching Method in Time-Series Databases Based on Generalized Windows", In Proc. Int’l Conf. on Management of Data, ACM SIGMOD, pp.382~393 (2002)
- M. Nanni, "Speeding-Up Hierarchical Agglomerative Clustering in Presence of Expensive Metrics", In Proc. Pacific-Asia Conf. on Advances in Knowledge Discovery and Data Mining (PAKDD),, pp.378~387 (2005)
- W. H. Press, "Numerical Recipes in C: The Art of Scientific Computing" (1992), Cambridge University Press
- J. G. Proakis, "Digital Signal Processing" (2006), Prentice Hall
- C. Ratanamahatana, "Three Myths about Dynamic Time Warping Data Mining", In Proc. SIAM International Data Mining Conference (SDM),, pp.506~510 (2005)
- Y. Sakurai, "AutoLag: Automatic Discovery of Lag Correlations in Stream Data", In Proc. Int’l Conf. on Data Engineering(ICDE),, pp.159~160 (2005)
- M. Vlachos, "Indexing Multi-Dimensional Time-Series with Support for Multiple Distance Measures", In Proc. Int’l Conf. on Knowledge Discovery and Data Mining, ACM SIGKDD, pp.216~225 (2003)
- M. Vlachos, "Identifying Similarities, Periodicities and Bursts for Online Search Queries", In Proc. Int’l Conf. on Management of Data, ACM SIGMOD, pp.131~142 (2004)
- B.-K. Yi, "Efficient Retrieval of Similar Time Sequences Under Time Warping", In Proc. Int’l Conf. on Data Engineering (ICDE), pp.201~208 (1998)
- B.-K. Yi, "Fast Time Sequence Indexing for Arbitrary Lp Norms", In Proc. Int’l Conf. on Very Large Data Bases(VLDB),, pp.385~394 (2000)
- T. Zhang, "BIRCH: An Efficient Data Clustering Method for Very Large Databases", In Proc. Int’l Conf. on Management of Data, ACM SIGMOD, pp.103~114 (1996)