Trend-based Document Clustering for Sensitive and Stable Topic Detection

Trend-based Document Clustering for Sensitive and Stable Topic Detection * Yoshihide Sato a, Harumi Kawashima b, Hidenori Okuda b, and Masahiro Oku b a NTT West Corporation b NTT Cyber Solutions Laboratories, NTT Corporation 1-1, Hikarino-oka, Yokosuka, Kanagawa, 239-0847 Japan y.sato@west.east.ntt.co.jp, {kawashima.harumi, okuda.hidenori, oku.masahiro}@labs.ntt.co.jp Abstract. The ability to detect new topics and track them is important given the huge amounts of documents. This paper introduces a trend-based document clustering algorithm for analyzing them. Its key characteristic is that it gives scores to words on the basis of the fluctuation in word frequency. The algorithm generates clusters in a practical time, with O(n) processing cost due to preliminary calculation of document distances. The attribute allows the user to settle on the best level of granularity for identifying topics. Experiments prove that our algorithm can gather relevant documents with F measure of 63.0% on average from the beginning to the end of topic lifetime and it largely surpasses other algorithms. Keywords: trend, clustering, gradient model, word frequency 1. Introduction Due to the information explosion on the WWW, the cost of catching up with the latest trends has risen. Consumer Generated Media (CGM), such as weblogs and social networking service (SNS), are only accelerating this explosion. The best approach to recognizing trends from among the huge number of documents being created is to analyze the topics in them. The goal of Topic Detection and Tracking (TDT) is to find state-of-the-art events in a stream of broadcast news stories (Allan et al., 1998). The study defines segmentation, new event detection, and event tracking as the major tasks. Segmentation proceeds by automatically dividing a text stream into topically homogeneous blocks. New event detection identifies stories in several continuous news streams that pertain to new or previously unidentified events. Event tracking identifies any and all subsequent stories describing the same event as sample instances of stories describing the event. Document clustering is an efficient approach to find topics in many documents. In the tasks, new event detection is intimately related to clustering, and involves the functions of retrospective detection and on-line detection. The input to retrospective detection task is the entire corpus, and it is desired to divide them into event-specific groups. The input to on-line detection is a chronologically ordered document stream, and the change point of topics should be found. On the WWW, where documents are numerous and increasing hourly, our goal is to provide an environment that supports users on finding and tracking the topics. In particular, sensitive detection of new topics is needed there. Then, our research is categorized as both on-line event detection and event tracking in TDT. As a matter of fact, both aspects are essential for adequately grasping the topics. This paper introduces a trend-based document clustering algorithm that enables the detection of topic occurrence at the earliest possible stage and the observation of topic transition. The remainder of this paper is organized as follows: Section 2 describes related work; Section 3 describes our clustering algorithm; Section 4 describes …

Content truncated to 500 words