<figure><img src="image_1.png" /></figure>

HAL
open science

# Text Classification Using Association Rules, Dependency Pruning and Hyperonymization

Yannis Haralambous, Philippe Lenca

► To cite this version:

Yannis Haralambous, Philippe Lenca. Text Classification Using Association Rules, Dependency Pruning and Hyperonymization. DMNLP 2014: Workshop on Interactions between Data Mining and Natural Language Processing, Sep 2014, Nancy, France. pp.65-80. hal-01058330

HAL Id: hal-01058330

https://hal.science/hal-01058330

Submitted on 11 Oct 2022

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Text Classification Using Association Rules,
Dependency Pruning and Hyperonymization

Yannis Haralambous and Philippe Lenca

Institut Mines Telecom, Telecom Bretagne, UMR CNRS 6285 Lab-STICC
Technopôle Brest Iroise CS 83818, 29238 Brest Cedex 3, France
<surname>.<name>@telecom-bretagne.eu

**Abstract.** We present new methods for pruning and enhancing item-sets for text classification via association rule mining. Pruning methods are based on dependency syntax and enhancing methods are based on replacing words by their hyperonyms of various orders. We discuss the impact of these methods, compared to pruning based on tfidf rank of words.

Introduction

Automatic text classification is an important text mining task, due to the huge
number of text documents that we have to manage daily. Text classification has
a wide variety of applications such as Web document and email classification.
Indeed, most of the Web news services daily provide a large number of articles
making them impossible to be organized manually [14]. Automatic subject clas-
sification [9] and SPAM filtering [18] are two additional examples of the interest
of automatic text classification.

Automatic text classification can be defined as below. Given a set of docu-
ments such that each document is labeled with a class value, learn a model that
assigns a document with unknown class to one or more particular classes. This
can also be done by assigning a probability value to each class or by ranking the
classes.

A wide variety of classical machine learning techniques have been used for
text classification. Indeed, texts may be represented by word frequencies vectors,
and thus most of the quantitative data methods can be used directly on the
notorious “bag-of-words” model (cf. [27,3]).

Choosing a classifier is a multicriteria problem. In particular one has often
to make a trade-off between accuracy and comprehensibility. In this paper, we
are interested in both criteria with a deeper interest in comprehensibility. We
are thus interested in rule-based approaches and especially in class association
rules algorithms. Several studies have already successfully considered association
rule-based approaches in text mining (e.g., [4], [29], [7], [25]). This framework is
suitable for considering some statistical characteristics (e.g., high-dimensionality,
sparsity...) of the bag-of-words model where a document is represented as a set
of words with their associated frequency in the document.
However a text is more than a set of words and their frequencies. Enhancing the bag-of-words approach with linguistic features has also attracted several works (e.g., [12,11,13,22], [23,16,10], [21,6]).

We here propose a class association rules based approach enriched by linguistic knowledge. The paper is organized as follows: after introducing the techniques we are going to use (class association rules § 1.1, dependencies § 1.2, hyperonymization § 1.3) we describe our main algorithms (for training § 2.1, classifying § 2.2 and evaluating § 2.3); follows the experimental section, where we give results obtained by tfidf pruning § 3.2, dependency-based pruning § 3.3 and hyperonymization § 3.4, and, finally, we end up by a conclusion and perspectives for future work § 4.

# 1 Proposed model for text classification

Let a corpus be a set $\mathbf{C} = \{D_1, \dots, D_n\}$ of documents. Let $\mathcal{C}$ be a set of classes. An annotated corpus is a pair $(\mathbf{C}, \text{class})$ where class : $\mathbf{C} \to \mathcal{C}$ is a function that maps each document $D_i$ to a (predefined) class of $\mathbf{C}$.

A document $D \in \mathcal{C}$ is a set of sentences $S$. The corpus $\mathbf{C}$ can be considered as a set of sentences $\mathbf{S} = \{S_1, \dots, S_m\}$ if we go through the forgetful functor (which forgets the document to which the sentence belongs). Repeated sentences in the same document, or identical sentences in different documents are considered as distinct, i.e., there is a function $\iota: \mathbf{S} \to \mathcal{C}$ which restores the forgotten information. We extend the class function to $\mathbf{S}$ by class($S$) := class($\iota(S)$).

A sentence $S$ is a sequence of words $w$ (sometimes we will consider $S$ simply as a set, without changing the notation). Let $\mathcal{W} = \bigcup_{S \in \mathcal{S}} \bigcup_{w \in S} \{w\}$ be the set of all words of $\mathbf{C}$.

## 1.1 Class association rules and text classification

Let $\mathcal{I}$ be a set of objects called items and $\mathcal{C}$ a set of classes. A transaction $T$ is a pair $(\{i_1, \dots, i_n\}, c)$, where $\{i_1, \dots, i_n\} \subseteq \mathcal{I}$ and $c \in \mathcal{C}$. We denote by $\mathcal{T}$ the set of transactions, by items($T$) the set of items (or “itemset”) of $T$ and by class($T$) the class of $T$.

Let $\mathcal{I}$ be an itemset. The support of $\mathcal{I}$ is defined by

$$ \text{supp}(\mathcal{I}) := \frac{\#\{T \in \mathcal{T} | I \subseteq \text{items}(T)\}}{\#\mathcal{T}}. $$

Let $\sigma \in [0, 1]$ be a value called minimum support. An itemset $\mathcal{I}$ is called frequent if its support exceeds $\sigma$.

The confidence of a transaction $t$ is defined as

$$ \text{conf}(t) := \frac{\#\{T \in \mathcal{T} | \text{items}(t) \subseteq \text{items}(T) \land \text{class}(t) = \text{class}(T)\}}{\#\{T \in \mathcal{T} | \text{items}(t) \subseteq \text{items}(T)\}}. $$

Let $\kappa \in [0, 1]$ be a value called minimum confidence. A class association rule (or “CAR”) $r = (\{i_1, \dots, i_n\}, c)$ [15] is a transaction with frequent itemset and a confidence exceeding $\kappa$.
To classify text with CARs, we consider words as being items, documents as being itemsets and pairs of documents and classes as being transactions. The advantage of this technique is that CARs can be easily understood and hence potentially improved by the user, especially if the classifier is tuned so that it produces humanly reasonable number of rules. Once the classifier is trained, to classify a new sentence we first find all CARs whose items are contained in the sentence, and then use an aggregation technique to choose a predominant class among those of the CARs we found.

An important issue of CARs is that the complexity is exponential with respect to the itemset size, and hence we need to keep it bounded in specific ranges, independently of the size of documents to classify. Using entire documents as transactions is computationally out of reach, therefore pruning techniques play an important rôle. Our approach consists in (a) restricting CARs to the sentence level, (b) prune sentences by using morphosyntactic information (cf. § 1.2) and modifying itemsets using semantic information (cf. § 1.3).

## 1.2 Itemset pruning using dependencies

One can prune sentences either by using word frequencies (cf. § 3.2) or by using information obtained by morphosyntactic parsing (cf. § 3.3). In this paper we introduce the latter approach, in the frame of dependency grammar.

*Dependency grammar* [28,19] is a syntactic theory, alternative to *phrase-structure analysis* [8] which is traditionally taught in primary and secondary education. In phrase-structure syntax, trees are built by grouping words into “phrases” (with the use of intermediate nodes NP, VP, etc.), so that the root of the tree represents the entire sentence and its leaves are the actual words. In dependency grammar, trees are built using solely words as nodes (without introducing any additional “abstract” nodes). A single word in every sentence becomes the *root* (or *head*) of the tree. An oriented edge between two words is a *dependency* and is tagged by a representation of some (syntactic, morphological, semantic, prosodic, etc.) relation between the words. For example in the sentence “John gives Mary an apple,” the word “gives” is the head of the sentence and we have the following four dependencies:

<figure><img src="image_3.png" /></figure>

where tags nsubj, dobj, iobj, det denote “noun subject,” “direct object,” “indirect object” and “determinant.”

Let $S$ be a sentence and $\mathcal{D}$ be the set of dependency tags: {nsubj, ccomp, prep, dobj, ...} A *dependency* is a triple $(w_1, w_2, d)$ where $w_1, w_2 \in S$ and $d \in \mathcal{D}$. Let $\text{Dep}(S)$ denote the set of dependencies of $S$ and $\text{root}(S)$ the head of $S$.
Pruning will consist in defining a *morphosyntactic constraint* $\phi$ i.e. a condition on dependencies (and POS tags) of words, the fulfillment of which is necessary for the word to be included in the itemset.

But before describing pruning algorithms and strategies, let us first present a second technique used for optimizing itemsets. This time we use semantic information. We propose to replace words by their hyperonyms, expecting that the frequencies of the latter in the itemsets will be higher than those of the former, and hence will improve the classification process.

## 1.3 Hyperonymization

The WordNet lexical database [20] contains sets of words sharing a common meaning, called *synsets*, as well as semantic relations between synsets, which we will use to fulfill our goal. More specifically, we will use the relations of *hyperonymy* and of *hyperonymic instance*. The graph having synsets as nodes, and hyperonymic relations as edges, is connected and rooted: starting with an arbitrary synset, one can iterate these two relations until attaining a sink. Note that in the case of nouns it will invariably be the synset 00001740 {entity} while for verbs there are approx. 550 different verb sinks.

Let $W$ be the WordNet lexical database, $s \in W$ a synset and $h: W \to 2^W$ the hyperonymic or hyperonymic instance relation. We define an *hyperonymic chain* CH($s$) as a sequence $(s_i)_{i \ge 0}$ where $s_0 = s$ and $s_i \in h(s_{i-1})$, for all $i \ge 1$. Hyperonymic chains are not unique since a given synset can have many hyper-onyms. To replace a word by the most pertinent hyperonym, we have to identify the most significant hyperonymic chains of it.

The *wn-similarity* project [24] has released synset frequency calculations based on various corpora. Let $lf(s)$ denote the logarithmic frequency of synset $s$ in the BNC English language corpus [2] and let us arbitrarily add infinitesimally small values to the frequencies so that they become unique ($s \neq s' \Rightarrow lf(s) \neq lf(s')$). We use frequency as the criterion for selecting a single hyperonymic chain to represent a given synset, and hence define the *most significant hyperonymic chain* MSCH($s$) as the hyperonymic chain $(s_i)_{i \ge 0}$ of $s$ such that $s_i = \arg\max_{s \in h(s_{i-1})} lf(s)$, for all $i \ge 1$. The chain MSCH($s$) is unique thanks to the uniqueness of synset frequencies.

Our CARs are based on words, not synsets. Hence we need to extend MSCHs to words. Let $w$ be a lemmatized word. We denote by Synsets($w$) $\subset W$ the set of synsets containing $w$. If the cardinal $|(Synsets(w))| > 1$ then we apply a standard disambiguation algorithm to find the most appropriate synset $s_w$ for $w$ in the given context. Then we take $(s_i)_{i = MSCH(s_w)}$ and for each synset $s_i$ in this chain we define $h_i(w) = \text{proj}_1(s_i)$ ($i > 0$), that is the projection of $s_i$ to its first element, which by WordNet convention is the most frequent word in the synset. The function vector $h_* : W \to W$ (with $h_0 = \text{Id}$) is called *hyperonymization*, and $h_i(w)$ is the $i$-th order hyperonym of $w$.
**Algorithm 1: Training**

**Data:** An annotated corpus **C**, values of minimum support $\sigma$ and minimum confidence $\kappa$

**Result:** A set of CARs $\mathcal{R} = \{\{R_1, \dots, R_N\}, \text{conf}\}$ where $\text{items}(R_i) \subset \mathcal{W}$, $\text{class}(R_i) \in \mathcal{C}$, and $\text{conf}(R_i)$ is the confidence of rule $R_i$

**Train(C, $\sigma$, $\kappa$):**
$$ \begin{array}{l} \text{S} := \text{forgetful}(C); \text{S}' := \emptyset; \\ \text{for } S \in \mathcal{S} \text{ do} \\ \quad \text{S}' := \text{Hyperonymize (Prune (Lemmatize (S)))); \\ \quad \text{class}(S') := \text{class}(\iota(S)); \\ \quad \text{S}' := \text{S}' \cup \{S'\}; \\ \text{end} \\ \mathcal{R} := \text{Apriori (S', $\sigma$, $\kappa$)}; \\ \end{array} $$

## 2 Operational implementations for document classification

Our text classifier operates by first training the classifier on sentences and then classifying the documents by aggregating sentence classification. These two procedures are described in Sections 2.1 and 2.2 respectively. Specific evaluation procedure is presented in Section 2.3.

### 2.1 Training

The *Train* algorithm (cf. Alg. 1) takes as input an annotated corpus **C** and values of minimum support $\sigma$ and minimum confidence $\kappa$. It returns a set of CARs together with their confidence values.

The first part of the algorithm consists in processing the corpus, to obtain efficient and reasonably sized transactions. Three functions are applied to every sentence:

1. **Lemmatize** is standard lemmatization: let $\mathcal{P}$ be the set of POS tags of the *TreeTagger* system [26] (for example, NP stands for “proper noun, singular”, VVD stands for “verb, past tense”, etc.), and let $\mathcal{W}'$ be the set of lemmatized forms of $\mathcal{W}$ (for example, “say” is the lemmatized form of “said”); then we define $\lambda: \mathcal{W} \to (\mathcal{W} \cup \mathcal{W}') \times \mathcal{P}$, which sends a word $w$ to the pair $(w', p)$ where $w'$ is the lemmatized form of $w$ (or $w$ itself, if the word is unknown to *TreeTagger*) and $p$ is its POS tag.

2. **Prune** is a function which prunes the lemmatized sentence so that only a small number of (lemmatized) words (and POS tags) remains. Several sentence pruning strategies will be proposed and compared (cf. § 3.2 and 3.3).

3. **Hyperonymize** is a function which takes the words in the pruned itemset and replaces them by the members of their most significant hyperonymic chains. Several strategies will also be proposed and compared (cf. § 3.4).
**Algorithm 2: Classification**

**Data:** A set of CARs $\mathcal{R}$, a document $D_0$

**Result:** The predicted class $\text{predclass}(D_0)$, variety $\beta$, dispersion $\Delta$

**Classify**($\mathcal{R}$, $D_0$):

$$
\begin{aligned}
& \text{for } S \in D_0 \text{ do} \\
& \quad \text{if } \exists r \in \mathcal{R} \text{ such that } \text{items}(r) \subset S \text{ then} \\
& \quad \quad R_S := \arg \max_{r \in \mathcal{R} \land \text{items}(r) \subset S} \text{conf}(r); \\
& \quad \text{end} \\
& \text{end} \\
& \text{predclass}(D_0) := \arg \max_{c \in \mathcal{C}} \sum_{\substack{S \in D_0 \\ \text{class}(R_S)=c}} \text{conf}(R_S); \\
& \beta := \#\{c \in \mathcal{C} \mid (\text{class}(R_S) = c) \land (\text{conf}(R_S) > 0)\}; \\
& \Delta := \max_{c \in \mathcal{C}} \sum_{\substack{S_i \in D_0 \\ \text{class}(R_{S_i})=c}} \text{conf}(R_{S_i}) - \min_{c \in \mathcal{C}} \sum_{\substack{S_i \in D_0 \\ \text{class}(R_{S_i})=c}} \text{conf}(R_{S_i}); \\
& \text{end}
\end{aligned}
$$

The second part of Alg. 1 uses the *apriori* algorithm [5] with the given values of minimum support and minimum confidence and output restrictions so as to generate only rules with item $c \in \mathcal{C}$ in the consequent. It returns a set $\mathcal{R}$ of CARs and their confidence.

It should be noted that this algorithm operates on individual sentences, hereby ignoring the document level.

## 2.2 Classification

The *Classify* algorithm (cf. Alg. 2) uses the set of CARs produced by *Train* to predict the class of a new document $D_0$ and furthermore provides two values measuring the quality of this prediction: variety $\beta$ and dispersion $\Delta$.

The first part of the algorithm takes each sentence $S$ of the document $D_0$ and finds the most confident CAR that can be applied to it (i.e., such that the itemset of the rule is entirely contained in the itemset of the sentence). At this stage we have, for every sentence: a rule, its predicted class and its confidence.

Our basic unit of text in *Train* is sentence, therefore CARs generated by Alg. 1 produce a class for each sentence of $D_0$. An aggregation procedure is thus needed in order to classify the document. This is done by taking class by class the sum of confidence of rules and selecting the class with the highest sum.

Although this simple class-weighted sum decision strategy is reasonable, it is not perfect and may lead to wrong classification. This strategy will be *optimally* sure and robust if (a) the number of classes is minimal, and (b) the values when summing up confidence of rules are sufficiently spread apart. The degree of fulfillment of these two conditions is given by the parameters *variety* $\beta$ (the number of classes for which we have rules), and *dispersion* $\Delta$ (the gap between the most confident class and least confident one). These parameters will contribute to comparison among the different approaches we will investigate.
**Algorithm 3: Evaluation**

**Data:** An annotated corpus $\mathbf{C}$, initial values of minimal support $\sigma_0$ and confidence $\kappa_0$, standard number of rules $\rho_0$

**Result:** Values of average precision $\bar{P}$, recall $\bar{R}$, F-measure $\bar{F}$. Values of average number of rules $\rho$, variety $\beta$ and dispersion $\Delta$

**SingleEvaluate**($\mathbf{C}$, $\sigma$, $\kappa$):
(C₁, ..., C₁₀) := Partition (Shuffle (C), 10); /* tenfold cross validation */
for I ∈ {1, ..., 10} do
  (R_I, β_I, Δ_I) := Train (C \ C₁, σ, κ);
  for D ∈ C_I do
    predclass(D) := Classify (R_I, D);
    end
    for c ∈ C do
      R_I(c) := # {d ∈ C_I | (predclass(d)=c) ∧ (class(d)=c)} / # {d ∈ C_I | class(d)=c};
      P_I(c) := # {d ∈ C_I | (predclass(d)=c) ∧ (class(d)=c)} / # {d ∈ C_I | predclass(d)=c};
      F_I(c) := 2 * R_I(c) * P_I(c) / (R_I(c) + P_I(c));
    end
  end
end
for c ∈ C do
  (R(c), P(c), F(c)) := 1/10 ∑ 10 I = 1 (R_I(c), P_I(c), F_I(c));
end
(ρ, β, Δ) := 1/10 ∑ 10 I = 1 (#R_I, β_I, Δ_I);
(\bar{R}, \bar{P}, \bar{F}) := 1/\#C ∑ c ∈ C (R(c), P(c), F(c));
end
Evaluate(C, σ₀, κ₀, ρ₀):
  (σ, κ) := FindOptimal(C, σ₀, κ₀, ρ₀);
  (\bar{R}, \bar{P}, \bar{F}, ρ, β, Δ) := SingleEvaluate(C, σ, κ);
end

## 2.3 Evaluation

We evaluate the classifier (Alg. 3), by using 10-fold cross validation to obtain average values of recall, precision, F-measure, variety and dispersion. This is done by algorithm **SingleEvaluate**, once we specify values of minimal support and minimal confidence.

Comparing rule-based classification methods is problematic because one can always increase F-measure performance by increasing the number of rules, which results in overfitting them. To avoid this phenomenon and compare methods in a fair way, we fix a number of rules $\rho_0$ (we have chosen $\rho_0 = 1,000$ in order to produce a humanly reasonably readable set of rules) and find values of minimal support and confidence so that F-measure is maximal under this constraint.

Function **FindOptimal** will launch **SingleEvaluate** as many times as necessary on a dynamic grid of values $(\sigma, \kappa)$ (starting with initial values $(\sigma_0, \kappa_0)$), so that, at the end, the number of rules produced by **Train** is as close as possible to $\rho_0$ (we have used $\#\mathcal{R} \in [\rho_0 - 2, \rho_0 + 2]$) and $\bar{F}$ is maximal.
<caption>**Algorithm 4:** Tfidf-based corpus pruning</caption>

**Data:** An annotated corpus (considered as a set of sentences) S
**Result:** The pruned corpus S'
**Prune(S, N):**
S' := ∅;
for S ∈ S do
    for w ∈ S do
        Tfidf<sub>S</sub>(w) := freq<sub>S</sub>(w) · log(\#{S∈C} / \#{S∈C|w∈S})
    end
    S' := ∅; S<sub>0</sub> := S;
    for i ∈ {1, ..., N} do
        w' := arg max<sub>S<sub>0</sub></sub> Tfidf<sub>S</sub>(w);
        S<sub>0</sub> := S<sub>0</sub> \ {w'}; S' := S' ∪ {w'};
    end
    S' := S' ∪ {S'};
end
end

3 Experimental results on Reuters corpus

In this section, we investigate three methods: (a) pruning through a purely frequentist method, based on tfidf measure (§ 3.2); (b) pruning using dependencies (§ 3.3); (c) pruning using dependencies followed by hyperonymic extension (§ 3.4).

3.1 Preliminaries

In the Reuters [1] corpus we have chosen the 7 most popular topics (GSPO =
sports, E12 = monetary/economic, GPOL = domestic politics, GVIO = war,
civil war, GDIP = international relations, GCRIM = crime, law enforcement,
GJOB = labor issues) and extracted the 1,000 longest texts of each.

The experimental document set is thus a corpus of 7,000 texts of length
between 120 and 3,961 words (mean 398.84, standard variation 169.05). The
texts have been analyzed with the Stanford Dependency Parser [17] in collapsed
mode with propagation of conjunct dependencies.

3.2 Tfidf-based corpus pruning

Tfidf-based corpus pruning consists in using a *classical Prune* function as defined in Alg. 4. It will be our baseline for measuring performance of dependency- and hyperonymy-based methods.

Note that this definition of the tfidf measure diverges from the legacy one by
the fact that we consider not documents but sentences as basic text units. This
is because we compare tfidf-generated CARs to those using syntactic informa-
tion, and syntax is limited to the sentence level. Therefore, in order to obtain a
fair comparison, we have limited term frequency to the sentence level and our “document frequency” is in fact a sentence frequency.

Having calculated $Tfidf_S(w)$ for every $w \in S \in \mathbf{S}$, we take $N$ words from each sentence with the highest tfidf values, and use them as transaction items. The performance of this method depends on the value of $N$. On Fig. 1 the reader can see the values of three quantities as functions of $N$:

1. F-measure: we see that F-measure increases steadily and reaches a maximum value of 83.99 for $N = 10$. Building transactions of more than 10 words (in decreasing tfidf order) deteriorates performance, in terms of F-measure;

2. variety: the number of predicted classes for sentences of the same document progressively increases but globally remains relatively low, around 3.1, except for $N = 12$ and $N = 13$ where it reaches 4.17;

3. dispersion: it increases steadily, with again a small outlier for $N = 12$, probably due to the higher variety obtained for that value of $N$.

<figure><img src="image_4.png" /><figcaption>**Fig. 1.** F-measure, variety and dispersion of tfidf-based pruning methods as a function of the number of words kept in the corpus</figcaption></figure>

Furthermore, each investigated method will generate transactions of various sizes. It is fair to compare them with tfidf-based methods with similar transactions sizes. Therefore we will use the results displayed in Fig. 1 to compare the performance of subsequent methods with the one of the tfidf-based method of similar transaction size. Table 1 presents the results obtained by applying the tfidf-based pruning method, with a single word per transaction ($N = 1$).

<table><caption>**Table 1.** Tidy-based pruning, keeping a single word per transaction</caption><thead><tr><th></th><th>E12</th><th>GCRIM</th><th>GDIP</th><th>GJOB</th><th>GPOL</th><th>GSPO</th><th>GVIO</th><th>AVG</th></tr></thead><tbody><tr><th>Recall</th><td>69.30</td><td>44.48</td><td>55.44</td><td>45.75</td><td>52.54</td><td>82.90</td><td>67.98</td><td>59.77</td></tr><tr><th>Precision</th><td>70.09</td><td>77.81</td><td>71.25</td><td>79.76</td><td>71.62</td><td>80.78</td><td>73.35</td><td>74.95</td></tr><tr><th>F-measure</th><td>69.69</td><td>56.60</td><td>62.36</td><td>58.15</td><td>60.61</td><td>81.83</td><td>70.56</td><td>65.69</td></tr></tbody></table>

MinSupp=0.006, MinConf=67.6, Var.=1.36, Disp.=21.53, AvgTransSize=1.00

## 3.3 Methods based on dependencies

In this section we investigate several strategies using the dependency structure of sentences. Our general approach (cf. Alg. 5) keeps only words of $S$ that fulfill
**Algorithm 5: Dependency-based corpus pruning**

**Data:** An annotated corpus **S** and a morphosyntactic constraint

$$ \phi: S \to \{\text{true, false}\} $$

**Result:** The pruned corpus **S'**

Prune(**S**, *φ*):

$$ \begin{array}{l} S' := \emptyset; \\ \text{for } S \in \mathbf{S} \text{ do} \\ \quad S' := \emptyset; \\ \quad \text{for } w \in \mathbf{S} \text{ do} \\ \quad \quad \text{if } \phi(w) = \text{true} \text{ then} \\ \quad \quad \quad | S' := S' \cup \{w\} \\ \quad \quad \text{end} \\ \quad \text{end} \\ S' := S' \cup \{S'\}; \\ \text{end} \\ \text{end} \end{array} $$

<table><caption>**Table 2a.** Strategy I₀: Pruning by keeping only heads of sentences</caption><thead><tr><th></th><th>E12</th><th>GCRIM</th><th>GDIP</th><th>GJOB</th><th>GPOL</th><th>GSPO</th><th>GVIO</th><th>AVG</th></tr></thead><tbody><tr><td>Recall</td><td>38.54</td><td>57.46</td><td>26.88</td><td>17.43</td><td>31.06</td><td>88.49</td><td>51.90</td><td>44.54</td></tr><tr><td>Precision</td><td>49.13</td><td>66.18</td><td>49.61</td><td>65.73</td><td>39.07</td><td>42.18</td><td>60.31</td><td>53.17</td></tr><tr><td>F-measure</td><td>43.19</td><td>61.51</td><td>34.87</td><td>27.55</td><td>34.61</td><td>57.13</td><td>55.79</td><td>44.95</td></tr></tbody></table>

MinSupp=0.004, MinConf=36.6, Var.=2.14, Disp.=47.84, AvgTransSize=1.00

<table><caption>**Table 2b.** Strategy I₁: Pruning by keeping only nsubj → head dependencies</caption><thead><tr><th></th><th>E12</th><th>GCRIM</th><th>GDIP</th><th>GJOB</th><th>GPOL</th><th>GSPO</th><th>GVIO</th><th>AVG</th></tr></thead><tbody><tr><td>Recall</td><td>70.55</td><td>60.44</td><td>66.97</td><td>58.27</td><td>63.22</td><td>78.76</td><td>69.92</td><td>66.88</td></tr><tr><td>Precision</td><td>73.05</td><td>80.84</td><td>72.87</td><td>86.98</td><td>71.71</td><td>85.29</td><td>76.29</td><td>78.15</td></tr><tr><td>F-measure</td><td>71.78</td><td>69.17</td><td>69.80</td><td>69.79</td><td>67.19</td><td>81.89</td><td>72.97</td><td>71.80</td></tr></tbody></table>

MinSupp=0.007, MinConf=60.4, Var.=1.43, Disp.=41.71, AvgTransSize=1.04

a given morphosyntactic constraint *φ*. The following strategies correspond to various definitions of *φ*.

**Strategy I₀** Our first strategy will be to keep only the head of each sentence (which, incidentally, is a verb in 85.37% of sentences of our corpus). This corresponds to the constraint $\phi(w) \equiv (w = \text{root}(S))$. Results are given on Table 2a.

Although the recall of GSPO is quite high (a possible interpretation could be that sports use very specific verbs), F-measure is quite low when we compare it to the one of the tfidf-based method of the same average itemset length, namely 65.69%.

**Strategy I₁** The second strategy consists in keeping words connected to the head by a (single) dependency of type nsubj (= nominal subject). This occurs in
<table><caption>**Table 2c.** Strategy $I_1$: Pruning by keeping only ccomp → head dependencies</caption><thead><tr><th></th><th>E12</th><th>GCRIM</th><th>GDIP</th><th>GJOB</th><th>GPOL</th><th>GSPO</th><th>GVIO</th><th>AVG</th></tr></thead><tbody><tr><th>Recall</th><td>57.33</td><td>33.82</td><td>25.31</td><td>16.96</td><td>21.74</td><td>47.62</td><td>59.60</td><td>37.48</td></tr><tr><th>Precision</th><td>37.83</td><td>47.55</td><td>38.50</td><td>42.06</td><td>34.62</td><td>57.05</td><td>54.17</td><td>44.54</td></tr><tr><th>F-measure</th><td>45.59</td><td>39.53</td><td>30.54</td><td>24.17</td><td>26.71</td><td>51.91</td><td>56.75</td><td>39.31</td></tr></tbody></table>

MinSupp=0.008, MinConf=34.4, Var.=1.97, Disp.=19.59, AvgTransSize=1.15

<table><caption>**Table 2d.** Strategy $I_2$: Pruning by keeping only nouns at distance 1 from head</caption><thead><tr><th></th><th>E12</th><th>GCRIM</th><th>GDIP</th><th>GJOB</th><th>GPOL</th><th>GSPO</th><th>GVIO</th><th>AVG</th></tr></thead><tbody><tr><th>Recall</th><td>80.75</td><td>75.92</td><td>73.24</td><td>68.59</td><td>70.59</td><td>95.55</td><td>77.96</td><td>77.51</td></tr><tr><th>Precision</th><td>73.21</td><td>83.51</td><td>75.35</td><td>89.86</td><td>73.67</td><td>80.52</td><td>77.36</td><td>79.07</td></tr><tr><th>F-measure</th><td>76.80</td><td>79.53</td><td>74.28</td><td>77.80</td><td>72.09</td><td>87.39</td><td>77.66</td><td>77.94</td></tr></tbody></table>

MinSupp=0.016, MinConf=51.6, Var.=2.43, Disp.=244.82, AvgTransSize=2.70

<table><caption>**Table 2e.** Strategy $I_2'$: Pruning by keeping only verbs at distance 1 from head</caption><thead><tr><th></th><th>E12</th><th>GCRIM</th><th>GDIP</th><th>GJOB</th><th>GPOL</th><th>GSPO</th><th>GVIO</th><th>AVG</th></tr></thead><tbody><tr><th>Recall</th><td>54.32</td><td>62.50</td><td>44.37</td><td>20.41</td><td>27.58</td><td>91.39</td><td>67.68</td><td>52.61</td></tr><tr><th>Precision</th><td>49.58</td><td>65.98</td><td>48.44</td><td>78.39</td><td>46.69</td><td>43.57</td><td>63.84</td><td>56.64</td></tr><tr><th>F-measure</th><td>51.84</td><td>64.19</td><td>46.32</td><td>32.39</td><td>34.68</td><td>59.01</td><td>65.70</td><td>50.59</td></tr></tbody></table>

MinSupp=0.019, MinConf=30, Var.=4.00, Disp.=175.41, AvgTransSize=2.01

79.84% of sentences of our corpus. The constraint is then $\phi(w) \equiv (\exists(w, \text{root}(S)), \text{nsubj}) \in \text{Dep}(S))$. Results are given on Table 2b.

Note that the slightly higher than 1 transaction size is probably due to the rare cases where there are more than one nsubj dependencies pointing to the head. The scores rise dramatically when compared to those of the strategy based only on the head of the sentence. The average F-measure (71.80%) is significantly higher than the tfidf-based performance for the same average transaction size (65.69%). This shows that using a dependency property to select a word is a better choice than the one provided by the frequentist tfidf-based method. Note that the case of nsubj is unique: if we take ccomp (= clausal complement) instead of nsubj, the performance falls even below the level of strategy $I_0$ (Table 2c).

**Strategy $I_2$** The third strategy considers all nouns (POS tags starting with N) at distance 1 from the head in the dependency graph. Such dependencies occur in 59.24% of the sentences of our corpus. This corresponds to $\phi(x) \equiv ((\exists(x, \text{root}(S)), d) \in \text{Dep}(S)) \wedge (\text{POS}(x) = \text{N}*)$. Results are given on Table 2d.

The result seems better than the one of strategy $I_1$ (Table 2b). However, if we take transaction size into account, it is in fact merely equivalent to—and hence not better than, as it was the case for $I_1$—the tfidf-based method with the same transaction size. Once again we see a very high recall rate for the sports category.
**Algorithm 6: Corpus hyperonymization**

**Data:** A dependency-pruned corpus $S'$, an hyperonymic function
MSCH: $W \to W^N$, the hyperonymic order $N$

**Result:** The hyperonymically extended corpus $S''$

Hyperonymize($S'$, MSCH, $N$):
$$ \begin{array}{l} S'' := \emptyset; \\ \text{for } S' \in S' \text{ do} \\ \quad S'' := \emptyset; \\ \quad \text{for } w \in S' \text{ do} \\ \quad \quad \text{if } \text{proj}_N(\text{MSCH}(w)) \neq \emptyset \text{ then} \\ \quad \quad \quad \mid S'' := S'' \cup \{\text{proj}_N(\text{MSCH}(w))\} \\ \quad \quad \text{else} \\ \quad \quad \quad \mid S'' := S'' \cup \{w\} \\ \quad \quad \text{end} \\ \quad \text{end} \\ S'' := S'' \cup \{S''\} \\ \text{end} \\ \text{end} \end{array} $$

One could be tempted to check the performance of taking verbs (instead of nouns) at distance 1 from the head. Indeed, verbs at that position are more frequent than nouns: they occur in 62.94% of the sentences of our corpus. Nevertheless, the results are not as good (Table 2e). This shows that despite their high frequency, verbs contain less pertinent information than nouns at the same distance from the head.

## 3.4 Methods based on dependencies and hyperonyms

In this section we add semantic information by the means of hyperonyms, using the hyperonymization function $h$ (§ 1.3). The preprocessing is done by Alg. 6: $h_i(w)$ is an $N$-th order hyperonym of $w$, if it exists in WordNet. In case there is no $N$-th order hyperonym, the word remains unchanged. We call $N$ the *hyperonymic factor* of our itemset transformation.

**Strategy II<sub>1</sub>** This strategy considers hyperonymic factor $N = 1$. We thus first apply strategy $I_1$ and then hyperonymization $h_1$. Results are presented on Table 3a.

The performance is globally inferior to the one of Strategy $I_1$ (in which, F-measure attained 71.80%). It is interesting to note that the recall of class GJOB has decreased significantly (48.96% vs. 58.27%): in other words, using hyperonyms when dealing with labor issues results into failure to recognize 9.31% of the documents as belonging to the domain; one could say that terms used in GJOB lose their “labor specificity” already at first-order hyperonymization. On the other hand, the (already high in $I_1$) recall of GSPO has increased even more, compared to $I_1$ (from 78.76% to 82.20%): it seems that sports terminology remains in the domain even after hyperonymization, and replacing specific terms
<table><caption>**Table 3a.** Strategy II₁: I₁ followed by first-order hyperonymization</caption><thead><tr><th></th><th>E12</th><th>GCRIM</th><th>GDIP</th><th>GJOB</th><th>GPOL</th><th>GSPO</th><th>GVIO</th><th>AVG</th></tr></thead><tbody><tr><th>Recall</th><td>72.39</td><td>56.04</td><td>71.32</td><td>48.96</td><td>59.02</td><td>82.20</td><td>70.42</td><td>65.76</td></tr><tr><th>Precision</th><td>66.21</td><td>75.42</td><td>64.33</td><td>82.21</td><td>67.71</td><td>73.20</td><td>70.73</td><td>71.40</td></tr><tr><th>F-measure</th><td>69.16</td><td>64.30</td><td>67.64</td><td>61.37</td><td>63.07</td><td>77.44</td><td>70.57</td><td>67.65</td></tr></tbody></table>

MinSupp=0.010, MinConf=44.8, Var.=1.92, Disp.=78.47, AvgTransSize=1.04

<table><caption>**Table 3b.** Strategy II₂: I₁ followed by second-order hyperonymization</caption><thead><tr><th></th><th>E12</th><th>GCRIM</th><th>GDIP</th><th>GJOB</th><th>GPOL</th><th>GSPO</th><th>GVIO</th><th>AVG</th></tr></thead><tbody><tr><th>Recall</th><td>69.02</td><td>52.78</td><td>71.97</td><td>47.77</td><td>54.24</td><td>80.80</td><td>65.67</td><td>63.18</td></tr><tr><th>Precision</th><td>64.94</td><td>74.57</td><td>61.23</td><td>80.64</td><td>65.81</td><td>69.96</td><td>72.33</td><td>69.93</td></tr><tr><th>F-measure</th><td>66.92</td><td>61.81</td><td>66.16</td><td>60.00</td><td>59.47</td><td>74.99</td><td>68.84</td><td>65.46</td></tr></tbody></table>

MinSupp=0.008, MinConf=44.8, Var.=1.85, Disp.=70.51, AvgTransSize=1.04

by more general ones has increased their frequency as items, and hence improved recall. We have the same phenomenon with the recall of GDIP (which increased from 66.97% to 71.32%), and also slightly with the recalls of E12 and GVIO.

**Strategy II₂** This strategy is similar to strategy II₁ but uses hyperonymic factor $N = 2$. Results are presented on Table 3b.

The performance is globally inferior to the one of II₁ (where we used first-order hyperonyms), with two minor exceptions: the recall of GDIP that increased by 0.65% and the precision of GVIO that increased by 1.6%. What is noteworthy however, is the fact that the recalls of GDIP and GSPO are still higher than the ones of strategy I₁ (no hyperonyms).

To better understand the behavior of the system when climbing the hyperonymic chain by replacing words by hyperonyms of increasingly higher order (and returning to the original word when there are no hyperonyms left) we calculated the performance for N-th order hyperonyms for $1 \le N \le 12$. Note that when $N > 12$ the amount of remaining hyperonyms is negligible and the strategy is similar to strategy I₁ (no hyperonyms). On Fig. 2, the reader can see the evolution of recall (black), precision (red) and F-measure (blue) for the average of all class, and then specifically for GSPO and for GDIP. Dashed lines represent the recall, precision and F-measure of strategy I₁.

In the average case, the effect of hyperonymization of orders 1-4 is to decrease performance. After $N = 5$, the global number of hyperonyms available in WordNet rapidly decreases so that the situation gradually returns to the one of I₁ (no hyperonyms) and we see curves asymptotically converging to I₁ lines from underneath.

Not so for GSPO, the GSPO recall curve of which is above the I₁ value for most $N$ ($N = 1, 2, 6-8$ and $10-12$).

The phenomenon is even better illustrated in the case of GDIP: as the reader can see on the figure, the *complete* GDIP recall curve is located above the I₁ one. It seems that in these two cases (GDIP and, to a lesser extent, GSPO),
<figure><img src="image_5.png" /><figcaption>**Fig. 2.** F-1 measure for hyperonymization of orders 1 ≤ *N* ≤ 12: the average case, class GSPO, class GDIP</figcaption></figure>

hyperonyms of all orders have a positive impact on the classifier. Unfortunately
this impact only concerns recall and is compensated by bad precision, so that
F-measure is still inferior to the I₁ case.

4 Conclusion and future work

In this paper we have investigated the use of association rules for text classifica-
tion by applying two new techniques: (a) we reduce the number of word features
through the use of morphosyntactic criteria in the framework of dependency syn-
tax; for that we keep words dependent from the head by specific dependencies
and/or having specific POS tags (b) we replace words by their hyperonyms of
different orders, which we have calculated out of WordNet using frequencies and,
in some cases, disambiguation. We have obtained positive results for case (a), in
particular when we compare dependency-based single-item rules with tfidf-based
ones. In case (b) the results we share in this paper are less efficient but still in-
teresting, especially we found classes for which hyperonymization significantly
improves recall.

This work opens several perspectives, among which:

— examine why these particular classes are favorable to hyperonymization,
whether this is related to the structure of WordNet or to linguistic properties of
the domain;

— explore *partial hyperonymization* i.e., is it possible to hyperonymize only specific items according to the needs of the classifier?<fnref n="1" /> How do we choose, on the word level, if we should rather keep the original word (to increase precision) or switch to some hyperonym (to increase recall)?

— we have used only recall and precision as quality measures of our rules,
and our evaluation is strongly dependent on these measures since the selection
of the 1,000 rules we keep is entirely based upon them. There are other quality

<footnote n="1">¹ Indeed, by hyperonymizing all words one wins on one side and loses on the other: for example “dalmatian” and “poodle” will both be replaced by “dog”, but “dog” occurrences will be replaced by “canid”. It would be more preferable to keep the word “dog” in the second case, so that we have a real increase in frequency.</footnote>
measures available, how do they apply and how can they be compared and
combined? How robust are the results?

— and finally: how can we optimize the distinctive feature of association rules, namely the fact of being intelligible by the user? How can the user's experience (and linguistic knowledge) be incorporated in the enhancement of rules to obtain the best possible result from his/her point of view?

References

1. Reuters corpus, volume 1, english language, 1996-08-20 to 1997-08-19, http://about.reuters.com/researchandstandards/corpus/statistics/index.asp

2. British National Corpus (1994), http://www.natcorp.ox.ac.uk

3. Aggarwal, C.C., Zhai, C.: A Survey of Text Classification Algorithms, chap. 6, pp. 163–222. Mining Text Data, Springer

4. Ahonen, H., Heinonen, O., Klemettinen, M., Verkamo, A.I.: Applying data mining techniques in text analysis. TR C-1997-23, Department of Computer Science, University of Helsinki (1997)

5. Borgelt, C.: Efficient implementations of apriori and eclat. In: Workshop of Frequent Item Set Mining Implementations (FIMI 2003), Melbourne, FL, USA (2003)

6. Ferrer i Cancho, R., Solé, R.V., Köhler, R.: Patterns in syntactic dependency networks. Physical Review E 69, 1–8 (2004)

7. Cherfi, H., Napoli, A., Toussaint, Y.: A Conformity Measure Using Background Knowledge for Association Rules: Application to Text Mining, pp. 100–115. IGI Global (2009)

8. Chomsky, N.: Syntactic structures. Mouton (1957)

9. Cohen, W.W.: Learning rules that classify e-mail. In: AAAI Spring Symposium on ML and IR (1996)

10. Curran, J.R., Moens, M.: Scaling context space. In: Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics. pp. 231–238 (2002)

11. Do, T.N.Q.: A graph model for text analysis and text mining. Master Thesis, Université de Lorraine, (2012)

12. Jaillet, S., Laurent, A., Teisseire, M.: Sequential patterns for text categorization. Intell. Data Anal. 10(3), 199–214 (2006)

13. Kovacs, L., Baksa-Varga, E.: Dependency-based mapping between symbolic language and Extended Conceptual Graph. In: 6th International Symposium on Intelligent Systems and Informatics. pp. 1–6 (2008)

14. Lang, K.: Newsweeder: Learning to filter netnews. In: International Conference on Machine Learning. pp. 331–339. Morgan Kaufmann (1995)

15. Liu, B., Hsu, W., Ma, Y.: Integrating classification and association rule mining. In: Proc. of the Int. Conf. on Knowledge Discovery and Data Mining (New York). pp. 80–86 (1998)

16. Lowe, W.: Towards a theory of semantic space. In: Proceedings of the Twenty-Third Annual Conference of the Cognitive Science Society. pp. 576–581 (2001)

17. de Marneffe, M.C., MacCartney, B., Manning, C.D.: Generating typed dependency parses from phrase structure parses. In: LREC 2006. pp. 449–454 (2006)

18. Mehran Sahami, Susan Dumais, D.H., Horvitz, E.: A bayesian approach to filtering junk email. In: AAAI Workshop on Learning for Text Categorization. AAAI Technical Report WS-98-05 (1998)
19. Mel'čuk, I.A.: Dependency syntax : theory and practice. Albany: State University Press of New York (1987)

20. Miller, G.A.: WordNet: A lexical database for English. Communications of the ACM 38(11), 39–41 (1995)

21. Nivre, J.: Dependency Grammar and Dependency Parsing. MSI report 05133. School of Mathematics and Systems Engineering, Växjö University, (2005)

22. Ordoñez-Salinas, S., Gelbukh, A.: Information Retrieval with a Simplified Conceptual Graph-Like Representation 6437(Chapter 9), 92–104 (2010)

23. Padó, S., Lapata, M.: Dependency-based construction of semantic space models. Computational Linguistics 33(2), 161–199 (2007)

24. Pedersen, T.: Information content measures of semantic similarity perform better without sense-tagged text. In: Proceedings of the 11th Annual Conference of the North American Chapter of the Association for Computational Linguistics (NAACL HLT 2010). pp. 329–332 (2010)

25. Roche, M., Azé, J., Matte-Tailliez, O., Kodratoff, Y.: Mining texts by association rules discovery in a technical corpus. In: Intelligent Information Processing and Web Mining. pp. 89–98. Advances in Soft Computing, Springer Verlag (2004)

26. Schmid, H.: Probabilistic part-of-speech tagging using decision trees. In: Proceedings of International Conference on New Methods in Language Processing, Manchester, UK (1994)

27. Sebastiani, F.: Machine learning in automated text categorization. ACM Comput. Surv. 34(1), 1–47 (2002)

28. Tesnière, L.: Éléments de syntaxe structurale. Klincksieck (1959)

29. Zaïane, O.R., Antonie, M.L.: Classifying text documents by associating terms with text categories. In: Australasian Database Conference. CRPIT, vol. 5. Australian Computer Society (2002)