The proliferation of Web applications based on short texts represents both an opportunity and a challenge to text mining algorithms, because of sparse representations and lack of shared context. To address this problem, we investigate a term expansion approach based on analyzing the relationships between the term concepts present in the concept lattice associated with the document corpus. We define five term concept association measures: proximity, concept similarity, connection strength, damping-weighted proximity, proximity&strength. By means of two case studies, we evaluate the effectiveness of these measures for expansion-enhanced K-NN classification and K-Means clustering of short texts. The results suggest that the five measures are highly competitive, with the best measure showing a clear improvement over the corresponding unenhanced K-NN and K-Means algorithms, as well as over two alternative term expansion enhancements (i.e., based on Wordnet and on pseudo-relevance feedback).
The increasingly important role played by short texts in the modern means of
Web communication and publishing, such as Twitter messages, blogs, news feeds,
and customer reviews, opens new application avenues for text mining techniques
but it also raises new scientific challenges. Although text classification and
clustering are well established techniques (e.g., [
There are two main approaches to address the problems raised by short texts.
Either we try to define new semantic similarity functions by means of external
knowledge sources, without changing the underlying document representation
(e.g., [
We investigate a method for text expansion that exploits the features of the concept lattice built from the document-term matrix. We model the similarity between two terms as function of the relationships between the corresponding term concepts in the the concept lattice. In particular, we define five term concept association measures: proximity, concept similarity, connection strength, strength-weighted proximity, proximity&strength. These measures take advantage of both the local statistical co-occurrence of terms and the global structural relationships between overlapping documents, as encoded in the concept lattice. They have an intuitive meaning and are mostly easily computable. We show that the full set of term-term similarities can be generated efficiently from the concept lattice by exploring the nearest concepts of single term concepts.
We study the use of concept lattice-based term expansion with the five association functions to enhance classification and clustering of short texts. We present two experimental studies, using two classical algorithms, namely K-NN and K-Means, on two collections of short texts, namely the Reuters-21578 news data set and the ODP-239 data set (extracted from the ODP Web directory). We evaluate the effectiveness of the unenhanced algorithms and of the same algorithms enhanced with the five variants of concept lattice-based term expansion. We also include, as a reference of comparison, two additional enhanced versions of the basic algorithms using two existing expansion methods based, respectively, on WordNet and pseudo-relevance feedback. We show that classification and clustering with concept lattice-based expansion may be much more accurate than competing methods across a range of evaluation measures, especially using some term concept association functions.
The remainder of the paper has the following organization. We first provide some introductory remarks on the use of term-term associations for semantic document similarity. Then we describe the five term concept association measures and present an efficient algorithm for finding all pairwise term similarities. In the next section we describe our implementation of the expansion methods based on WordNet and pseudo-relevance feedback. The following two sections are dedicated to the experiments performed with the K-NN classifiers and KMeans clusterers on the Reuters and ODP data sets, respectively. We end the paper by discussing related work and we finally provide our conclusions and some directions for future work. 2
In text mining, a set of documents is usually represented as an n-by-m documentterm matrix D, where n is the number of documents and m is the number of unique terms in the document collection. Each row of the matrix D corresponds to a document di and the value of element D(i, j) denotes the importance (weight) of term j in document i (e.g., computed by the term frequency - inverse document frequency scheme).
Classification and clustering algorithms typically rely on a similarity function between pairs of documents. The most common approach is to apply a simple (syntactic) similarity measure to the document term vectors (called bag of words representations); e.g., using the inner product:
T
SimDOC (d1, d2) = hd1, d2i = d1 d2
For short or very short texts, rather than using Equation 1 with the original sparse input terms, it may be more convenient to consider a linear mapping of the document vectors φ(d) = d S. The matrix S typically encodes pairwise term similarities, thus implying that the mapping φ(d) = d S allows us to represent each document not only by its original terms but also by the terms that are related to each of them. In this case, the similarity function between documents becomes:
SimDOC (d1, d2) = d1 S ST d2T
By varying the matrix S one can obtain different transformations of the
document feature space. Term-term associations can be computed using various
methods discussed in [
Let C(G, M, I; ≤) be the concept lattice of the context (G, M, I).1 A particular type of concepts relevant to us are attribute concepts. The attribute concept of an attribute m ∈ M is the concept (m′, m′′), where m′ is the attribute extent {g ∈ G | gIm}. The attribute concept of m is thus the smallest concept with m in its intent.
The order relation ≤ induces the notion of nearest neighborhood. Let (X1, Y1) and (X2, Y2) be two concepts in C(G, M, I; ≤). We say that (X1, Y1) is a nearest neighbor of (X2, Y2) if and only if (X1, Y1) ≤ (X2, Y2) or (X2, Y2) ≤ (X1, Y1), and there does not exist (X3, Y3) ∈ C(G, M, I; ≤) such that (X1, Y1) ≤ (X3, Y3) ≤ (X2, Y2) or (X2, Y2) ≤ (X3, Y3) ≤ (X1, Y1).
We now define five association measures between a pair of attribute concepts. The measures take into account the topological structure of the lattice, the concept descriptions, or both. We assume that the association between two attribute concepts is stronger when they are more similar, when they are closer, and when they are connected with more similar concepts.
Concept similarity. This is a very straightforward measure because it is based only on the description of attribute concepts, regardless of how they are connected. The similarity (CSim) between two attribute concepts (m1, m′1′), ′ (m′2, m2 ), is the average of the similarities of their extents and intents, as mea′′ sured by the Dice coefficient: 1 We assume that the reader is familiar with the basic notions and terminology of formal concept analysis.
CSim = 1 2|m′1 ∩ m′2| 2|m′1′ ∩ m′2′| |m′1 ∩ m′2| |m′1′ ∩ m′2′| 2 ( |m′1| + |m′2| + |m′1′| + |m′2′| ) = |m′1| + |m′2| + |m′1′| + |m′2′| (3)
We consider both the extents and intents, although these features are not independent, to better account for the relative sizes of the set of objects and attributes, and we used the Dice coefficient (rather than e.g., the Jaccard coefficient) because it works well even with a small number of shared elements (as a portion of all non-zero elements). The CSim value is not equal to zero if and only if the two attributes co-occur in at least one object, while the contribution of the intent similarity is greater than zero if and only if one attribute is perfectly associated with the other (i.e., when their mutual information is maximum).
Proximity. The association between two attribute concepts can be determined
using the length of their shortest connecting path (topological distance) in the
concept lattice. The closer the two attributes are to each other, the greater their
semantic relation due to the properties of near concepts [
P rox = 1 −
SD − min(SD) max(SD) − min(SD) = 1 −
SD max(SD) (4) because min(SD) = 0 (i.e., when the two attributes coincide).
Connection strength. Using the length of shortest paths alone is not enough because some paths are weaker than others. For instance, if a concept happens to cover many objects and a nearest neighbor concept covers few objects, the association between the attributes in the first concept and the attributes in the second concept is weak. This aspect can be taken care of by looking at the connection strength (Str) of two attribute concepts (m1, m′1′), (m2, m′2′), defined ′ ′ as the average of the concept similarities (CSim) of the pairs of consecutive concepts along the shortest connecting path between (m1, m′1′), (m2, m′2′). When ′ ′ (m′1, m′1′), (m2, m′2′), are nearest neighbor concepts, the connection strength is ′ equal to the concept similarity CSim.
P roximity&strength. Proximity and connection strength can be combined in a single measure in various ways. We define the proximity&strength (P rox&Str) of two attribute concepts as a linear combination of the proximity P rox and the connection strength Str:
P rox&Str = α P rox + (1 − α) Str
The parameter α allows us to control the relative importance of extents and intents (the default value is 0.5). Note that the Str value in Equation 5 is computed after finding the shortest path connecting the two attribute concepts. A tighter combination of P rox and Str, formulated as a shortest weighted path problem, leads to the following measure.
Damping-weighted proximity. Let Damp = 1 − Str be the connection damping between two nearest neighbor concepts. The damping-weighted proximity (DampW−P rox) of two attribute concepts is an inverse function of the normalized shortest weighted distance (SWD) of the two attribute concepts, according to the nearest neighbor relation weighted with the connection damping: DampW−P rox = 1 −
SWD − min(SWD) max(SWD) − min(SWD) (6)
As an illustration, consider the simple context for vertebrate animals shown
in Figure 1, first introduced in [
x x x x x x x x x x
In Figure 2 we report the shortest distance between any pair of attributes (left), derived from the concept lattice in Figure 1 after the removal of its top and bottom element, and their degree of association, computed from the shortest paths and from the connection strength values using Equation 5 (α = 0.5). For instance, for the attribute pair ‘has wings’ (e), ‘is viviparous’ (g), the shortest path is {(1 2 5), (has wings)} − > {(1 2), (has wings, can fly)} − > {(1), (has wings, can fly, is viviparous)} − > {(1 3), (is viviparous)}, P rox = 1 − 3/10 = 0.7, Str = (0.73 + 0.73 + 0.583)/3 = 0.681, P rox&Str = (0.7 + 0.681)/2 = 0.69.
The associations shown in Figure 2 are meaningful. Each attribute is more strongly associated with the attributes which co-occur with it, but it is also transitively related to the other attributes in the data set. Consider for example ‘breathes in water’ (a). The degree of association between ‘breathes in water’ and the other attributes is shown in the first row of the left matrix. The three most associated attributes are ‘lives in water’ (f), ‘produces light’ (h), and ‘has beak’ (c), all of which co-occur with (a). The association ranking of the other (non co-occurring) attributes is the following: ‘has wings’ (e), ‘can fly’ (b), ‘is viviparous’ (g), ‘has hands’ (d). 4
For text mining applications, objects are documents and attributes are terms. There are three main computational steps involved in the construction of the term similarity matrix S: text pre-processing, construction of the concept lattice from the document-term matrix built in the earlier step, and determination of pairwise term similarities using the term concept association measures defined above.
Text pre-processing consists of text segmentation, punctuation removal,
conversion of upper to lower case, and stop-wording. We also remove all the words
that appear only in one document because they have a negligible effect on
retrieval performance. We do not perform any stemming and we use strict
singleword indexing. To build the document lattice, we use the NextNeighbors
algorithm, described in [
Our algorithm for finding the pairwise similarities efficiently is the following. We map each term onto the concept lattice to find the corresponding term concept. This operation takes constant time using an appropriate data structure; e.g., a trie or a hash table. Then, for each term concept, an exhaustive breadthfirst search through the lattice is performed, without generating the concepts that have already been encountered. Term concepts are collected along the way as soon as they are encountered. This requires at most one pass over the concept lattice, and thus the computational time complexity of finding all pairwise term similarities reduces to O(|M ||C|). In practice, it is not necessary to explore the whole lattice. We halt the search at a fixed depth value, because this is much more efficient and it may also improve performance due to noise reduction. From preliminary tests on the Reuters data set, we found that the performance reaches a peak for a small depth value (i.e., usually 2 or 3), after which it declines. Using this cut off value, only a small fraction (less than 5%) of all theoretically possible pairs obtained a nonzero value in the term-term similarity matrix. In the experiments reported in this paper, we set the cut off value to 2. 5
We have implemented, as a reference of comparison, two other text expansion
methods relying on standard term-term association techniques. One is based
on WordNet synsets. To look up synonyms defined by WordNet, we used a
package provided by Lucene2, and then we selected only those synsets terms
related to more than one original term for improving disambiguation. The
resulting binary expanded representation was used to compute pairwise document
similarities with Equation 1. The second expansion method, based on pseudo
relevance feedback, consists of selecting the terms which mostly contribute to
the Kullback-Leibler divergence (KLD) between the top ranked documents
retrieved in response to the original text from a corpus and the corpus itself. To
find KLD-weighted expansion terms, we used the query expansion facility
offered by the Terrier platform [
Text categorization is one of the most successful data mining technique. Among
many existing classifiers, the K-NN algorithm usually delivers top performance,
unless fairly little training data is available [
3 http://terrier.org/
K training documents that are nearest to it in the document space (usually by means of a simple majority vote). For our purposes, the most important thing is that K-NN explicitly computes pair-wise document similarities as a central step of its algorithm. We used cosine similarity of the binary document vectors as a similarity measure. In expansion-enhanced K-NN, the similarity between documents was computed by Equation 2 rather than by Equation 1.
We now describe the experimental setting. We used the ten most numerous classes of the well known Reuters-21578 news dataset, totaling about 8,000 documents. As we were interested in short or very short texts, we considered only the news headlines (i.e., the title field of each news item) as input documents and applied the pre-processing steps listed in Section 4. We randomly split the data set into two subsets, for training and test, then we built the concept lattice associated with the training subset, which contained 14,760 concepts and was rather wide and flat.
We ran seven versions of the K-NN classifier, one unenhanced (denoted as KNN), four enhanced with concept lattice-based expansion (one for each term concept association measure except for DampW-Prox due to computational reasons), and two enhanced respectively with WordNet (KNN-WN) and pseudorelevance feedback (KNN-KLD). To evaluate the performance, we used the recall (R), precision (P ), and F-measure, i.e. F = 2P R/(P + R). In Table 1 we report the results obtained by each method for recall, precision, and F-measure, averaged over the set of classes (the best values are in bold). NA stands for not available, due to computational issues.
In general, all five concept lattice-based versions did very well. The version with Prox&Str achieved the overall best results. Compared to the baseline, it was worse on precision, markedly superior on recall, and better on the combined F-measure. It was better than the other lattice-based association measures for all data points. and much better than KNN-WN and KNN-KLD (except for precision, where its result is nearly equal to that of KLD). On the other hand, KNN-WN and KNN-KLD did not compare favorably to the baseline: KNN-KLD improved over the baseline only in one case, while KNN-WN achieved the worst performance for all evaluation measures. The large increase in recall due to the use of Prox&Str is especially noteworthy because in many domains (e.g., legal, medical, patent decisions) an incorrect assignment could be easily discarded by an expert, whereas missing a relevant category could have serious consequences.
Clustering is another well known and long standing data mining technique. It is
being increasingly applied to various types of short texts present on the
Internet, including web pages, news, blogs, news feed, and Twitter data (see [
We used the ODP-239 test collection,4 first introduced in [
We ran eight versions of the K-Means algorithm on the test collection (rather
than seven). Given the very limited size of each data set and concept lattice,
we were able to compute the DampW-Prox term-term association matrix using
the Dijkstra algorithm for finding the shortest weighted distance for any pair
of terms. To evaluate performance, we assessed how successful the K-Means
clusterers were at recovering the known subtopics (classes) of each ODP-239
topic. We used the purity and normalized mutual information (N M I) measures.
To compute purity, each document is assigned to the class which is most frequent
in the cluster, and then the number of correctly assigned documents is counted
and divided by the number of documents. By contrast, NMI is an information
theoretic measure that allows us to trade off the quality of the clustering against
the number of clusters (for its precise definition see e.g., [
These findings confirm, to a larger extent, the main results of the classification experiment, namely the improvement of all the methods enhanced with concept lattice-based expansion over the baseline, as well as their superiority over the other expansion methods. A topic-by-topic analysis showed that they achieved
the best purity and NMI results for all classes, with a uniformly distributed gain across topics. Among the five concept lattice-based versions, one striking result is the good performance of CSim, given its simplicity. Note that using the CSim measure, only the pairs of terms that co-occur in at least one document will receive a nonzero similarity value. In this respect, the transitive closure of the initial document description is restricted to few terms and hidden similarities cannot be discovered. On the other hand, as in the ODP-239 the initial texts are considerably longer than the Reuters title and there is a much smaller number of documents, this simple criterion may be more effective than considering explicitly the expansion terms that are implied by transitivity. 8
There has been a certain amount of work on using text expansion for improving
classification and clustering. The expansion features can be extracted from a
knowledge source, or they can be generated by analyzing a corpus. The former
techniques include compiling WordNet concepts into the document
representation [
Another relevant area is the application of concept lattices to information
retrieval and information science, discussed in e.g. [
It is also relevant to this paper the work done on concept similarity. In an
attempt to go beyond simple edge counting, some recent approaches tried to
combine the structural relationships of concepts with their specific descriptions;
e.g., using sibling concepts [
In this paper we studied the use of five term concept association measures to drive text expansion prior to performing classification and clustering of short texts. The main results of our case studies are the following.
– Through a range of evaluation measures, we showed that the K-NN classifier and the K-Means clusterer, enhanced with expanded formal term concepts, were, in general, remarkably more effective than both the unenhanced algorithms and the algorithms enhanced with two different expansion techniques. – The term-term similarity matrix can be computed efficiently from the concept lattice associated with the document corpus. – Among the various term concept association measures tested in the experiments, the linear combination of proximity and connection strength exhibited the best classification accuracy, with no additional computational costs. 10
We would like to thank Giambattista Amati for helping with the Terrier-based experiments and three anonymous reviewers for their comments and suggestions.