Finding Strong Associations

A substantial part of the KDD literature deals with finding strong statistical associations (or correlations) between data elements in the collection (e.g. Toivonen et al 1995; Kloesgen 1995a; Feldman et al, 1996). Such associations were used for various applications, including:
• Supermarket shopping list: finding correlations between user purchase preferences
• Identifying telecommunications alarm rules, as associations between system attributes and faults.
In the KDT context, we are interested in finding statistical associations between
various keywords. For example, we may identify the economical topics which are
highly associated with a certain country. The comparative approach of the previous section
enables us to focus on associations that are likely to be interesting, i.e. those associations that deviate from a baseline model. For example, we will give a higher rank to an association between a country and a topic only if this association is not typical for other countries as well.


Previous                                     Next

Distribution Comparison

So far we have seen that the ability to specify keyword co-occurrence distributions provides the user with a useful mechanism for exploring subsets of documents. Taking a
KDD perspective, we are interested not only in displaying an entire distribution to the user
but also in identifying specific points in a distribution which are likely to be “interesting”.
We suggest to quantify the degree of “interest” of some data by comparing it to a
given, or an “expected”, model. For example, we may want to compare the data regarding IBM to a model constructed by some averaging of the data regarding other
computer manufacturers. Alternatively, we may want to compare the data regarding IBM
in the last year to a model constructed from the data regarding IBM in previous years.
In our case, we use keyword distributions to describe the data. We therefore need a
measure for comparing the distribution defined by the data to a model distribution.
We chose to use the relative entropy measure (or Kullback-Leibler (KL) distance), defined in information theory, though we plan to investigate other measures as well. The
KL-distance seems to be an appropriate measure for our purpose since it
measures the amount of information that we lose if we model a given distribution p by
another distribution q. Denoting the distribution of the data by p and the model
distribution by q, the distance from p(x) to q(x) measures the amount of “surprise”
in seeing p while expecting q. Formally, the relative entropy between two probability
distributions p(x) and q(x) is defined as:

The relative entropy is always non-negative and is 0 if and only if p=q.
According to this view, interesting distributions will be those with a large
distance to the model distribution. Interesting data points will be those that make a big
contribution to the distance between the given distribution and the model (i.e., x’s
whose contribution to the sum is large). The following sections show how various
interesting patterns can be identified by measuring the relative entropy distance
between a distribution and different baselinemodels.


Previous                                     Next

Keyword Co-Occurrence Distributions

All KDD operations supported by the KDT system are based on an analysis of the
keywords that annotate the articles in the collection. More specifically, KDT
computes the distribution of daughter terms relative to their siblings for all keywords in
the hierarchy. For example, the annotations of documents with daughters of the
keyword node computers may be distributed as follows: mainframes: 0.1;
work-stations: 0.4; PCs: 0.5. In formal terms, we set a node C in the hierarchy to
specify a discrete random variable whose values are denoted by its daughters, where
each occurrence of a daughter provides a data point. We denote the distribution of the
random variable by P(C=c), where c ranges over all daughters of C. The event C=c
corresponds to the annotation of a document with the daughter category c.
P(C=ci) is the proportion of annotations of documents with ci among all annotations of
documents with any daughter of C. In the example above we would say that
P(C=mainframes)=0.1, where C denotes the random variable which corresponds to
the node computers. In KDT we are most interested in conditional keyword distributions of the form P(C=c|x), where x is a conditioning event which denotes some other category
keyword. Such distributions describe the co-occurrence of the category x with all
daughters of C. Figure B shows an example for such a distribution, where C stands for the node topics and x stands for Argentina. In other words, the figure presents the distribution of topic keywords (i.e., keywords that are daughters of the topics node) in articles that are annotated also with the keyword Argentina. In Figure B the distribution is presented as a pie-chart, along with the absolute frequency of each slice in the pie:
12 articles among all articles of Argentina are annotated with sorghum, 20 with corn,
32 with grain, etc. The KDT system presents distributions in several forms,
graphical (e.g. bar-chart) or alphanumeric (see Figure C), listing absolute frequencies
or probabilities (percentage). More generally, a keyword cooccurrence distribution may be conditioned by the joint occurrence of several category keywords, and not just one. For example, Figure C displays the distribution P(C=c|x,y), where C stands for topics, x
for UK, and y for USA. In other words, this is the distribution of topics in articles that
deal with both UK and USA. The distribution is presented in the lower right
window of the screen. By letting the user specify and display
conditional keyword co-occurrence distributions, as in Figure 2 and Figure C,
the KDT system provides a powerful browsing mechanism for large subsets of
documents. A traditional document retrieval system enables the user to ask for all
documents containing the keywords UK and USA, but then presents the entire set of
matching documents without describing its internal structure. Typically, the documents
will be sorted by either relevance score, which would be determined in this case by
the frequency and position of the given keywords in the document, or by
chronological order. The KDT system, on the other hand, enables the user to
investigate the contents of this document set by sorting it according to the daughter
distribution of any node in the hierarchy, such as topics, countries, companies etc.
Once the documents are sorted, and the distribution is displayed, the user can
access the specific documents of each subgroup. In Figure C, for example, the
user chose to click on the 24 documents annotated with trade, which led to the
display of all titles of these documents (those annotated by UK, USA, and trade) in
the upper window of the screen.

Previous                                     Next

The Text Collection

As mentioned above, the KDT system expects as input documents which are
annotated with category labels, where annotation might be achieved either
manually or automatically. In the experiments described here we used the
Reuters-22173 text categorization test collection, containing about 22,000 articles,
totaling 25 megabytes. The documents in this collection appeared on the Reuters
news wire in the late 1980’s, and were assembled and indexed with categories by
personnel from Reuters Ltd. and Carnegie Group, Inc. Further formatting and data file
production was done in 1991 and 1992 by David D. Lewis and Peter Shoemaker.
The categories in this collection are classified only to five types of tags:
countries, topics, people, organizations and stock exchanges. These five types provided
us the skeleton of the keyword hierarchy, where each of the 5 types serves as an intermediate node in a two level hierarchy. We then enriched the hierarchy with some
additional sub-types of categories, such as agriculture and metals as daughters of the
topics node, and various international organizations (taken from the CIA Factbook on the Internet) as daughters of the countries node.


Previous                                     Next

Keyword Tagging and the Keyword Hierarchy

Applying KDD operations to texts requires that documents will be represented in some
structured way. We chose to base the current version of the system on the very simple
representation scheme of annotating (or tagging) each document with a set of
category label keywords. Category labels are commonly used in commercial and scientific
text collections and information feeds, and provide a high level summary for the content
of the document. For example, articles in hitech domains may be annotated with sets of
keywords such as {IBM, product announcement, Power PC} and {Motorola,
patent, cellular phone}. The annotation of documents with category labels may be either
manual or automatic. Automatic text categorization has recently been the focus of
substantial research in the IR and text processing communities (e.g. Apte et al
1994; Finch 1994; Iwayama and Tokunaga 1994). Altogether, we assume that having the
documents of the collection annotated with category labels is a reasonable pre-requisite
for the KDT system, which would hold for many text collections in the market. KDT also requires that the category keywords would be organized in a hierarchical structure. This keyword hierarchy is a directed acyclic graph (DAG) of terms, where each of the terms is identified by a unique name. Figure 1 shows a portion of an example keyword hierarchy, the one used in our work with the Reuters data (see below), which will serve as a running example throughout this paper. In such a hierarchy an arc from A to B denotes that A is a more general term than B (i.e., countries → G7 → Japan). We use a general DAG rather then a tree structure so that a keyword may belong to several parent nodes (e.g. Germany is both a European-Community and a G7 country).
It should be emphasized that the sole purpose of the keyword hierarchy is to enable generalizations and partitioning of KDD findings over sibling nodes. The structure of the hierarchy is typically simple, and reflects the basic generalizations common for the domain of interest. Such keyword hierarchies are commonly used by information providers
(e.g. the Dialog service of Knight Ridder Information Inc. or the First service of
Individual Inc.), and resemble in their form to a “subject index” in a yellow pages book.
Rich hierarchies have been developed for several professional domains, such as the
Medical Subject Heading (MeSH) hierarchy, and have been used to assist and
augment free-text searching. The task of constructing, obtaining and modifying such
hierarchies is thus relatively easy, and should not be confused with the task of
constructing a semantically rich structure, such as a semantic network or a taxonomy
in the “knowledge representation” sense. The KDT system provides a simple GUI for
constructing and editing the hierarchy, supporting additions, deletions and modifications of nodes and links (Figure A is a screen dump of the hierarchy maintenance editor).

Previous                                     Next

Introduction

Our general KDT framework was initially presented in (Feldman and Dagan 1995). The current paper both extends the KDT framework and its set of operations, and presents our interactive prototype system, which was implemented in Visual Prolog under Microsoft MS-Windows (all subsequent figures are screen dumps of this system). The system’s mode of operation involves three major steps:
1. Load input documents, annotated with keywords selected from a pre-existing
hierarchy of meaningful category labels.
2. Compute the various co-occurrence frequencies of these keywords within the documents in the collection (typically performed as a pre-processing step).
3. Provide interactive tools that allow access to documents, discover patterns across documents, and perform other similar KDD operations, based on the co-occurrence frequencies computed in the previous step.

Previous                                     Next

Introduction

2. Comparing Document Distributions: KDT can compare the distributions of keywords in two collections of documents containing similar keywords and display the results using tables and graphs.
3. Trend Analysis: KDT can compare the distributions of keywords in documents from different points in time and display the results using tables and graphs.
4. Association Discovery: KDT can search for several types of associations (e.g. Toivonen et al, 1995) between classes of documents.
5. Further, KDT includes a browsing facility in which the user can click on any discovered pattern and get the list of documents that contributed to the pattern.

These operations can assist users that have to analyze and assimilate information
spanning over a large number of documents, such as in business intelligence and economical analysis. For example, using the system an analyst can find out quickly the
most active economical areas for certain countries, or major products of companies.
Furthermore, the analyst can compare such a company “profile” to profiles of other
companies in the same business area, and discover distinguishing aspects in the activity
of the company. In business intelligence applications, the user may be interested in
comparing profiles of different companies to identify relatively weak and strong areas in
their activity, while in marketing applications an analyst may want to compare country
profiles when looking for appropriate international markets for a product. Other
types of KDT queries can answer questions like “find economical areas which are
dominant in the economies of some (unspecified) countries”, or “find economical
areas in which activity has increased or decreased in a specified period of time”.
Investigation of issues such as mentioned above is not supported directly in
conventional information retrieval systems, and typically requires a lot of manual effort
in retrieving and analyzing a large number of documents. It should be kept in mind that the answers to all KDT queries rely on document frequencies in some information source (such as a newswire or a professional magazine), which may introduce quantitative biases with respect to the real situation described in the texts. For example, an interesting story, from the media’s point of view, may be covered in a large number of articles, inflating the statistics of some items. To support verification of KDT’s finding, and for gaining further insights into them, the system provides a direct link from the results of each query to the documents which support that result.

 Previous                                     Next

Introduction

Traditional database query tools allow a user to retrieve records based on the content of each record in isolation. In a hospital database, for example, a user might request all records for hospital stays that are less than one day with a cost greater than $10,000. Each retrieved record is selected because the information in that record, independent of any other record, satisfies the user's query. In contrast, KDD work provides tools for accessing information based onpatterns appearing across records. For example, KDD tools might provide a user the ability to ask for records of patients whose medical care for some illness is much higher than typical (where "typical" is implicitly defined by the values of other records in the database), or to investigate if there exist some statistical patterns relating the length of patients’ hospital stay and their family circumstances (whether the patient is married, how many children the patient has,
etc.). Although the goal of KDD work is to provide access to patterns and information in online information collections, most efforts have focused on knowledge discovery in
structured databases. However, a tremendous amount of online information
appears only in collections of unstructured text. Most research in Information Retrieval
(IR) has developed methods for providing access to documents based on the information
contained in a document in isolation (analogous to what traditional database query tools provide for databases). In this case, it is assumed that the user knows in advance the
topic of documents of interest. Clustering methods were used to impose structure over a
collection of documents, enabling the user to browse through the collection and select clusters of documents of interest (e.g. Salton 1989; Cutting et al, 1993). Visualization
methods were also used for presenting some additional structures hidden in a document or a set of documents (Williamson and Shneiderman, 1992; Hearst 1995). However,
there has been little work on providing KDDstyle tools for browsing and analyzing text
collections based on information appearing across documents. Applying such tools to
texts means that the system would take an active role in suggesting topics of interest to
the user, as well as supply new browsing methods that rely on inter-document
information. A KDD framework for texts may thus be viewed as an intermediate point
between user-specified retrieval queries and unsupervised document clustering: the user
typically provides some guidance to the system about the type of patterns of interest,
but then the system makes unsupervised decisions in finding specific statistically
motivated patterns. This paper describes the Knowledge Discovery in Texts (KDT) system, which applies a novel knowledge discovery framework to textual databases. Our goal is to provide similar types of KDD operations previously provided for structured databases. To do so, we rely on a text-categorization paradigm where each document is labeled with sets of keywords, where each keyword comes from a hierarchy of terms. Unlike in traditional IR work, where keywords (category labels) are used in specification of retrieval (or routing) queries, KDT allows a user to access documents and recognize
patterns across them based on the observed co-occurrence distributions of keywords in
documents of the collection. A key insight in this work is that keyword co-occurence
frequencies (or distributions) can provide the foundation for a wide range of KDD
operations on collections of textual documents, including:

1. Summarization and Browsing: KDT allows the user to view the frequency of occurrence of keywords from some category in a collection of documents that contain particular keywords from some other category, and to browse the collection of documents based on these frequencies.


Previous                                     Next

Introduction

Traditional databases store large collections of information in the form of structured records, and provide methods for querying the database to obtain all records whose
content satisfies the user's query. More recently, however, researchers in Knowledge Discovery in Databases (KDD) have provided a new family of tools for accessing information in databases (e.g. Brachman etal, 1993; Frawley et al, 1991; Kloesgen,
1992; Kloesgen, 1995b; Ezawa and Norton, 1995). The goal of KDD has been defined as "the nontrivial extraction of implicit, previously unknown, and potentially useful
information from given data" (Piatetsky- Shapiro and Frawley 1991). Work in this area includes applying machine-learning and statistical-analysis techniques towards the automatic discovery of patterns in databases, as well as providing user-guided environments for exploration of data.

 Next

Keyword Analysis of Large

Abstract
Knowledge Discovery in Databases (KDD) focuses on the computerized exploration of large amounts of data and on the discovery of interesting patterns within them. While most work on KDD has been concerned with structured databases, there has been little work on handling the huge amount of information that is available only in unstructured textual form. This paper describes the KDT system for Knowledge Discovery in Texts. It is built on top of a text-categorization paradigm where text articles are annotated with keywords organized in a hierarchical structure. Knowledge discovery is performed by analyzing the co-occurrence frequencies of keywords from this hierarchy in the various documents. We show how this termfrequency approach supports a range of KDD operations, providing a general framework for knowledge discovery and exploration in collections of unstructured text.