One-Class Clustering in the Text Domain

Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing, pages 41–50, Honolulu, October 2008. c⃝2008 Association for Computational Linguistics One-Class Clustering in the Text Domain Ron Bekkerman HP Laboratories Palo Alto, CA 94304, USA ron.bekkerman@hp.com Koby Crammer University of Pennsylvania Philadelphia, PA 19104, USA crammer@cis.upenn.edu Abstract Having seen a news title “Alba denies wedding reports”, how do we infer that it is primar- ily about Jessica Alba, rather than about wed- dings or reports? We probably realize that, in a randomly driven sentence, the word “Alba” is less anticipated than “wedding” or “reports”, which adds value to the word “Alba” if used. Such anticipation can be modeled as a ratio between an empirical probability of the word (in a given corpus) and its estimated proba- bility in general English. Aggregated over all words in a document, this ratio may be used as a measure of the document’s topicality. As- suming that the corpus consists of on-topic and off-topic documents (we call them the core and the noise), our goal is to determine which documents belong to the core. We pro- pose two unsupervised methods for doing this. First, we assume that words are sampled i.i.d., and propose an information-theoretic frame- work for determining the core. Second, we relax the independence assumption and use a simple graphical model to rank documents according to their likelihood of belonging to the core. We discuss theoretical guarantees of the proposed methods and show their useful- ness for Web Mining and Topic Detection and Tracking (TDT). 1 Introduction Many intelligent applications in the text domain aim at determining whether a document (a sentence, a snippet etc.) is on-topic or off-topic. In some appli- cations, topics are explicitly given. In binary text classification, for example, the topic is described in terms of positively and negatively labeled docu- ments. In information retrieval, the topic is imposed by a query. In many other applications, the topic is unspecified, however, its existence is assumed. Examples of such applications are within text sum- marization (extract the most topical sentences), text clustering (group documents that are close topi- cally), novelty detection (reason whether or not test documents are on the same topic as training docu- ments), spam filtering (reject incoming email mes- sages that are too far topically from the content of a personal email repository), etc. Under the (standard) Bag-Of-Words (BOW) rep- resentation of a document, words are the functional units that bear the document’s topic. Since some words are topical and some are not, the problem of detecting on-topic documents has a dual formulation of detecting topical words. This paper deals with the following questions: (a) Which words can be con- sidered topical? (b) How can topical words be de- tected? (c) How can on-topic documents be detected given a set of topical words? The BOW formalism is usually translated into the generative modeling terms by representing doc- uments as multinomial word distributions. For the on-topic/off-topic case, we assume that words in a document are sampled …

Content truncated to 500 words