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

HAL
open science

# Short Text Feature Extension Based on Improved Frequent Term Sets

Huifang Ma, Lei Di, Xiantao Zeng, Li Yan, Yuyi Ma

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

## To cite this version:

Huifang Ma, Lei Di, Xiantao Zeng, Li Yan, Yuyi Ma. Short Text Feature Extension Based on Improved Frequent Term Sets. 9th International Conference on Intelligent Information Processing (IIP), Nov 2016, Melbourne, VIC, Australia. pp.169-178, 10.1007/978-3-319-48390-0_18. hal-01614992

HAL Id: hal-01614992

https://inria.hal.science/hal-01614992

Submitted on 11 Oct 2017

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_3.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Short Text Feature Extension based on Improved
Frequent Term Sets

Huifang Ma*, Lei Di*, Xiantao Zeng*, Li Yan*, Yuyi Ma*

*College of Computer Science,
Northwest Normal University
Lanzhou Gansu,China

mahuifang@yeah.net

**Abstract.** A short text feature extension algorithm based on improved frequent word set is proposed. By calculating support and confidence, the same category tendencies of frequent term sets are extracted. Correlations based frequent term sets are defined to further extend the term set. Meanwhile, information gain is introduced to traditional TF-IDF, better expressing the category distribution information and the weight of word for each category is enhanced. All term pairs with external relations are extracted and the frequent term set is expanded. Finally, the word similarity matrix is constructed via the frequent word set, and the symmetric non-negative matrix factorization technique is applied to extend the feature space. Experiments show that the constructed short text model can improve the performance of short text clustering.

**Keywords:** Term Weighing, Information Gain, Frequent term set, Correlation, Non-negative Matrix Factorization

# 1 Introduction

In recent years, with the development of technology in Web 2.0, short texts, such as short messages, microblogs, and news comments, increase in a geometrical ratio. Unlike traditional texts, some inherent characteristics of short texts, such as extremely feature sparsity and highly unbalancing samples, hinder the traditional approaches for long texts being easily applied.

To extend short text feature, the most recent popular researches have been mainly focused on three aspects. Firstly, some researchers try to use language models, grammar and syntax analysis method to obtain more specific semantic information[1-3]. Secondly, some researchers take advantage of statistical approaches, such as global term context vectors, coupled term-term relations for short text extension[4,5]. Lastly, both semantic information obtained from a hierarchical lexical database and statistical information contained in the corpus are involved for short text extension [6].
This paper proposes a short text feature extension strategy based on improved frequent term sets. We mainly focus on news titles and take news content as background knowledge. The feature extension algorithm is designed to extract frequent term sets and build the word similarity matrix, based on which to extend feature space of short text. The overview of our framework is shown in Fig 1. Firstly, by calculating support and confidence, double term sets with co-occurring relation and identical class orientation are extracted from long text corpus. Then we extend these frequent term sets with external association. Meanwhile, the information gain is introduced to traditional TF-IDF, better expressing the category distribution information and the weight of words for each category is enhanced. Finally, the word similarity matrix is constructed via the frequent word sets, and symmetric non-negative matrix factorization (SNMF) technique is used to extend the feature space.

<figure><img src="image_4.png" /><figcaption>Figure 1. Algorithm framework</figcaption></figure>

## 2 Frequent term sets extraction

We briefly introduce some concepts and notations employed in frequent term sets extraction in table 1. Support is defined as the number of documents which contain term set T dividing the total number of documents in data set while confidence is defined as the number of documents containing t in class c dividing the number of all documents involving t[7].

To select frequent term sets efficiently, several other concepts are needed:

**Definition 1 (Co-occurring relation)** If the support of term set T surpasses the threshold $\alpha$ ($0 < \alpha < 1$), T is considered as a frequent term set and all terms in T have a Co-occurring relation.

**Definition 2 (Class orientation)** For term t and class c ∈ C, if conf(t,c) surpasses the threshold $\beta(0.5 \le \beta<1)$, term t has a class orientation to c, formulated as $\text{Tendency}(t) = c$.
**Definition 3 (Identical Class Orientation)** For two terms t1 and t2, if there is a class c, $Tendency(t1) = c$ and $Tendency(t2) = c$, then t1 and t2 have an Identical Class Orientation.

In order to obtain more semantic information, we extract frequent term sets with both co-occurring relation and identical class orientation.

<table><caption>Table 1. Notation Definition</caption><thead><tr><th>Notation</th><th>meaning</th></tr></thead><tbody><tr><td>D={d<sub>1</sub>,d<sub>2</sub>,...,d<sub>M</sub>}</td><td>D: the collection of training set<br>d<sub>i</sub>: the ith document in D<br>M: total number of documents in D</td></tr><tr><td>N</td><td>the number of words appearing one and only one time in D</td></tr><tr><td>W, W<sub>e</sub></td><td>W: the expression matrix of D<br>W<sub>e</sub>: documents matrix after extension</td></tr><tr><td>T={t<sub>1</sub>,t<sub>2</sub>,...,t<sub>n</sub>}</td><td>T: a term set in background knowledge-base<br>t<sub>i</sub>: a feature term in T</td></tr><tr><td>S, P</td><td>S: words similarity matrix<br>P: matrix factorized by S<br>C: the set of categories</td></tr><tr><td>C={c<sub>1</sub>,c<sub>2</sub>,...,c<sub>L</sub>}</td><td>C<sub>i</sub>: the ith category in C<br>L: total number of categories</td></tr><tr><td>R, R<sub>e</sub></td><td>R: the original frequent couple term set<br>R<sub>e</sub>: frequent couple term sets after extension</td></tr><tr><td>K</td><td>the number of words appearing one and only one time in R</td></tr></tbody></table>

As co-occurring relation can perfectly represent semantic association between terms, while terms with identical class orientation can be potentially from the same or close topic, feature extension of these terms is expected to have better discriminative ability. Considering that there are often 2 words for most of Chinese phases, this paper focuses on extracting double frequent term sets. The algorithm is described in Table 2[7], and the feature set F represents the collection of words in background knowledge.

# 3 Word similarity matrix construction

## 3.1 Improved Term weighing scheme

The training set is taken as a whole in the calculation of IDF, which ignores the distribution information of feature terms among categories. Thus, an improved term-weighting scheme is applied in our work.
<table><caption>Table 2. Double Frequent Term Sets Extraction Algorithm</caption>
  <caption>Algorithm1. Double frequent term sets extraction algorithm</caption>
  <tbody>
    <tr>
      <td>Input:</td>
      <td>Feature set F, Support α, Confidence β, and the collection C of class.</td>
    </tr>
    <tr>
      <td>Output:</td>
      <td>Frequent couple term set R, total number K of words in R</td>
    </tr>
    <tr>
      <td>1:</td>
      <td>Initialize R as empty, K = 0</td>
    </tr>
    <tr>
      <td>2:</td>
      <td>For every term t<sub>i</sub> in F, if Support(t<sub>i</sub>) and conf(t<sub>i</sub>, c<sub>j</sub>) is no less than α and β respectively, then add t<sub>i</sub> into class c<sub>j</sub></td>
    </tr>
    <tr>
      <td>3:</td>
      <td>For every class in the category collection,calculate the Support between any two terms in this class,if Support ≡ α, then put this pair of terms into R,and K should increase corresponding number.</td>
    </tr>
    <tr>
      <td>4:</td>
      <td>Return R,K.</td>
    </tr>
  </tbody>
</table>

Assuming that X={x1:p1,x2:p2,...,xn:pn} is the information probability space, the information entropy of X is formulated as[8]:

$$
H(X) = H(p_1, p_2, \dots, p_n) = - \sum_{i=1}^{n} p_i \log_2 p_i \quad (1)
$$

Information gain is the difference between information entropy, represented as:

$$
I(X, y) = H(X) - H(X|y) \tag{2}
$$

where H(X) is the entropy without information of y, H(X|y) is the conditional en-
tropy, representing the incertitude degree of X with the information of y obtained.

From the aspect of information theory, the essential part of the improved term
weighting scheme is: for a training set with certain probability distribution, word cat-
egorical information mostly depends on information gain. With this consideration, the
improved term-weighting is define as:

$$
Q_{ij} = \text{TF}(t_j) \times \log\left(\frac{k}{n_i} + 0.01\right) \times \text{IG} \quad (3)
$$

Here Qij is the weight of tj in ci , ni is the total number of words in ci .

3.2 Word similarity calculation

With the improved term-weighting scheme, we can construct the word similarity ma-
trix. For two terms t<sub>i</sub> and t<sub>j</sub>, in frequent term sets, the semantic similarity between
them is derived according to Jaccard similarity [9] as follows:

$$
\mathrm{CoR}(t_i, t_j) = \frac{1}{|\bar{C}|} \times \sum_{x \in |\bar{C}|} \frac{Q_{xi} Q_{xj}}{Q_{xi} + Q_{xj} - Q_{xi} Q_{xj}} \quad (7)
$$

Since the frequent term sets extraction is based on categories, x here stands for a
category and Qₓᵢ is the improved term weight of tᵢ in cₓ. C̄ is a subset of collec-
tion C, satisfying C̄ = {x | (Qₓᵢ ≠ 0) ∪ (Qₓⱼ ≠ 0)}. And when C̄ is emp-
ty, CoR(tᵢ, tⱼ) = 0.

We then normalize the semantic similarity as:

$$
\mathrm{IaR}(t_i, t_j) = \begin{cases} 1 & i = j \\ \frac{\mathrm{CoR}(t_i, t_j)}{\sum_{i=1, i \neq j}^{N} \mathrm{CoR}(t_i, t_j)} & i \neq j \end{cases} \quad (8)
$$
However, in the whole term set there may be the case that co-occurring relations and identical class orientations might exist between one term and other terms. For example, { (computer, mouse), (computer, keyboard), (mouse, keyboard), (cellphone, computer), (cellphone, Internet) } is a frequent term set, in which ‘keyboard’ and ‘mouse’ are not only co-occurred but also linked by ‘computer’. Similarly, we can also relate ‘computer’ to ‘Internet’ by ‘cellphone’, though they are not co-occurred directly. Thus, we define another relation to strengthen semantic association of these words.

**Definition 4(inter-relation)** Terms $t_i$ and $t_j$ are defined to be inter-related, if there exists at least one term $t_k$, which is the linking term inter-related with both $t_i$ and $t_j$.

<figure><img src="image_5.png" /><figcaption>Figure 2. External Relation</figcaption></figure>

As is shown in Fig 2, $t_i$ and $t_k$ are co-occurred as well as $t_j$ and $t_k$. Therefore, we believe that there is semantic relation between $t_i$ and $t_j$, though they are not co-occurred directly.

All term pairs with external relations are extracted and added into $R$, the extended frequent couple term sets $R_e$ is formed. Moreover, words in $R_e$ are strongly related with each other, which provides solid foundation to word similarity matrix construction.

It is necessary to take measures to quantify for external relations before word similarity matrix construction.

$$R_{\text{IeR}}(t_i, t_j | t_k) = \min(\text{IaR}(t_i, t_k), \text{IaR}(t_j, t_k)) \quad (9)$$

where $\text{IaR}(t_i, t_k)$ and $\text{IaR}(t_j, t_k)$ represents the semantic similarity between $t_i$ and $t_k$, $t_j$ and $t_k$ respectively. In the quantification for external relations, we assume that the semantic similarity between $t_i$ and $t_j$ is at least valued as the minimization in all semantic similarities, which is feasible in fact.

The final external relation between $t_i$ and $t_j$ is calculated with all the linking terms of $t_i$ and $t_j$. After normalization, the inter-relation is formalized as:

$$\text{IeR}(t_i, t_j) = \begin{cases} 0 & i = j \\ \frac{1}{|L|} \sum_{t_k \in L} \text{IeR}(t_i, t_k | t_k) & i \neq j \end{cases} \quad (10)$$

Here $L = \{t_k | ((\text{IaR}(t_i, t_j) > 0) \cap (\text{IaR}(t_k, t_j) > 0))\}$, $|L|$ is the total number of terms. If the set of $L$ is empty, the inter-relation between $t_i$ and $t_j$, formulated as $\text{IeR}(t_i, t_j)$ is zero. And if $t_i$ and $t_j$ indicates the same word, We regard $\text{IeR}(t_i, t_j)$ as zero, too. Besides, when $t_i$ is different from $t_j$, there may be one or more linking terms relating them together, which are the elements in set $L$, taking the influence of all linking terms into consideration.
Word similarity matrix S is constructed based on frequent term sets, in which Sij denotes the semantic similarity and is defined as follows:

$$S_{ij} = \begin{cases} 1 & i = j \\ (1 - \gamma) \cdot \text{IaR}(t_i, t_j) + \gamma \cdot \text{IeR}(t_i, t_j) & i \neq j \end{cases} \quad (11)$$

Where $\gamma \in [0,1]$ is an important parameter deciding the weight of inter-relations. In our work, we set $\gamma$ as 0.5.

At this point, word similarity matrix S is constructed successfully, where semantic similarity of word represents not only co-occurring relation but also extended inter-relation, therefore, semantic associations are further enhanced.

## 4 Short text feature extension based on semantic similarity matrix

The non-negative factorization method was first proposed by Lee in Nature in 1999[10]. Different from original non-negative factorization algorithm, the symmetric non-negative factorization (SNMF) is pretty special, whose duty is to factor a non-negative matrix into a product of a non-negative matrix and its transposed matrix. More specifically, for a given non-negative matrix $Z_{n \times n}$, a non-negative matrix factor $Y_{n \times K}$, satisfying:

$$Z \approx YY^T, Y \ge 0 \quad (12)$$

Since the semantic similarity matrix S is obviously symmetric, SNMF aims to factor S into P and the transposed matrix of P. Each element in P is calculated iteratively as follows:

$$P_{i,j} = \frac{1}{2} \left[ P_{i,j} \left( 1 + \frac{(SP)_{ij}}{(PP^T P)_{ij}} \right) \right] \quad (13)$$

We build the original feature space W with TF-IDF and factor S into $S_{K \times K} = P_{K \times N} \times P_{N \times K}^T$. Then, the matrix $W_e$ extended is obtained.

$$W_e = W P^T \quad (14)$$

As the transposed matrix $P^T$ is factored by S, each one in $P^T$ is certainly not equals to 0. Meanwhile, W is the original matrix where each row represents a document, it is impossible to be 0 in rows, too. Therefore, the new extended feature space $W_e$ is no more sparse than before, which is vital to the construction of short text model. Furthermore, word similarity and categorical information as well as word semantic information W are assimilated into the new feature space $W_e$, which is favor of the similarity calculation of short text.

## 5 Experiments

In this section, we conduct a series of experiments to evaluate the performance of our algorithm and analyze these experiments and the results.
## 5.1 Data set

Experiments are conducted on two datasets: 20-Newsgroups[13] and Sougou corpus[14]. 20-Newsgroups is composed of 20 different news groups and 20000 short text snippets. Sougou corpus is a data set of news pages from Sohu news provided by Sougou lab, including 18 categories such as International, Sports, Society, Entertainment, etc. Each page has its page URL, page ID, page title and body content.

Short text refers to the title, the news contents and the description of short text are used for background knowledge extraction. All Chinese documents were pre-processed by word segmentation using ICTCLAS. After pre-processing, we select 10 categories from 20-Newsgroups and each category contains 200 documents. We also choose 9 categories from Sougou corpus, 2000 pages in total. The traditional K-means algorithm is employed to verify our experiment performance.

## 5.2 Experiment results

As $\alpha$ and $\beta$ are the most important parameters in our algorithm, we first vary their values to testify the performance of double term set extraction. Then, the performance of the original frequent term set and improved frequent term set with external relations are compared. Finally, we make a comparison of five short text representation method for clustering using Purity and F-measure as evaluation criteria.

The extraction of double term sets is significant to word similarity matrix construction, which greatly relies on the number of support and confidence restraints. The support guarantees the co-occurring relation of terms while the confidence determines whether the terms have identical class orientation. We extract the couple term sets using different parameter settings: $\alpha$=1.0%, 1.5%, 2.0%, 2.5%, 3.0% and $\beta$= 0.5, 0.6, 0.7, 0.8, 0.9 respectively, and the results are listed in Table 3(a).

<table><caption>Table 3(a) Double Frequent Term Sets Distribution with Different Support and Confidence</caption><thead><tr><th rowspan="2">α / %</th><th colspan="5">β</th></tr><tr><th>0.5</th><th>0.6</th><th>0.7</th><th>0.8</th><th>0.9</th></tr></thead><tbody><tr><td>1.0</td><td>9117</td><td>7648</td><td>5315</td><td>2754</td><td>1231</td></tr><tr><td>1.5</td><td>5383</td><td>2114</td><td>973</td><td>518</td><td>374</td></tr><tr><td>2.0</td><td>2854</td><td>811</td><td>574</td><td>430</td><td>292</td></tr><tr><td>2.5</td><td>659</td><td>443</td><td>207</td><td>161</td><td>144</td></tr><tr><td>3.0</td><td>530</td><td>336</td><td>132</td><td>25</td><td>9</td></tr></tbody></table>

As is shown in Table 3(a), the number of extracted double term sets decreases dramatically with the increase of support and confidence. It is understandable that higher support means more co-occurring relations and the constrains will be more strict when confidence increases. This shows that when support and confidence are set to be high, the information for background knowledge is too rare to have essential influence on the original feature space. Therefore, we choose $\alpha$=1.0%, $\beta$=0.5 to construct our background knowledge in the following experiment.

What's more, we define external relation based on traditional frequent term sets to further extend term sets, obtaining more semantic information. With the parameter of
support fixed and external relations taken into account, the number of extracted frequent term sets is demonstrated in Table 3(b).

<table><caption>Table 3(b) Double Frequent Term Sets Distribution with External Relation</caption><thead><tr><th rowspan="2">α / %</th><th colspan="5">β</th></tr><tr><th>0.5</th><th>0.6</th><th>0.7</th><th>0.8</th><th>0.9</th></tr></thead><tbody><tr><td>1.0</td><td>10942</td><td>9301</td><td>6378</td><td>2904</td><td>1377</td></tr><tr><td>1.5</td><td>6459</td><td>2737</td><td>1167</td><td>569</td><td>392</td></tr><tr><td>2.0</td><td>3467</td><td>962</td><td>638</td><td>473</td><td>306</td></tr><tr><td>2.5</td><td>790</td><td>511</td><td>228</td><td>177</td><td>151</td></tr><tr><td>3.0</td><td>609</td><td>389</td><td>145</td><td>25</td><td>9</td></tr></tbody></table>

From Table 3(b), frequent term sets with external relation and original algorithm are different in quantity, though the distributions of them are the same. It is obvious that the number of extracted term sets with external relation is much more than that of original algorithm. As we can observe, when α=1.0%, β=0.5, the original frequent term sets is 9117 while the number of term sets with external relation is 10942 which increases about 20%. The growth ratio decreases with the increase of parameter. Besides, the double frequent term sets with external relation is in favor of more semantic information.

Finally, we conduct experiments to compare clustering performances of five methods on two different data sets. The experiment results on two evaluation index --- Purity and F-measure are presented in Figure 3.

<figure><img src="image_6.png" /><figcaption>Figure 3. Clustering results of different methods on 20-Newsgroups (left) and Sougou corpus (right)</figcaption></figure>

In Fig 3, it is clear that different performance potentially depends on different data set. And the proposed method performs much better than any other methods. Furthermore, the result of the Sougou corpus is a little superior than that of 20-newsgroups in our experiment. As is depicted in Fig 3, results of these five methods can be roughly divided into 3 levels. The traditional TF-IDF performs the worst, obviously blaming on ignoring semantics in model construction. The performances of coupled term-term relations method and the improved term-weighting method are similar, which are still worse than that of method based on frequent term sets. This phenomenon can be explained: the coupled term-term relations method extract inner and inter relation of word with co-occurring relation to enhance semantic information,
while the improved term-weighting method considers information gain and statistical
information. They are both unfortunately one-sided considered.

Extending the extracted semantic information to short text space, the original frequent term sets method to some extent releases the problem of high dimension sparsity in short texts. However, as is shown in the above Fig 3, the best scheme for short text representation is the improved frequent term sets method. The superior of this method are summarized as follows: additional semantic information is first revealed with external relation. Then the word similarity matrix is built via improved term-weighting scheme and word categorical information. Finally, the symmetric non-negative matrix factorization technique is used to extend the feature space, which alleviates the problem of high-dimensional sparsity.

6 Conclusion

This paper discusses a short text feature extension algorithm based on improved frequent word sets. The external relation is proposed based on frequent term sets, further enhancing associations of words. Considering the distribution information of categories, an improved term-weighting scheme using information gain is presented, which efficiently remained the categorical information. What is more, all term pairs with external relations are extracted and the frequent term set is expanded. Finally, the word similarity matrix is constructed via the frequent term set, and the symmetric non-negative matrix factorization technique is used to extend the feature space. Experiments show that the constructed short text model can significantly improve the performance of clustering and effectiveness.

Acknowledgement.

This work is supported by the National Natural Science Foundation of China
(No.61363058), Youth Science and technology support program of Gansu Province
(145RJZA232, 145RJYA259, 1606RJYA269), 2016 Provincial College Students
Innovation and entrepreneurship training program (No.201610736040,
201610736041) and 2016 annual public record open space Fund Project
(No.1505JTCA007).

References

1. Alexander P, Patrick P. Twitter as a corpus for sentiment analysis and opinion mining[C]// Proceeding of the Seventh International Conference on Language Resources and Evaluation. Valletta, Malta, 2010:19-21.
2. Zhang W, Yoshida T, Tang X. Text classification based on multi-word with support vector machine[J]. Knowledge-Based Systems, 2008, 21(8):879-886.

3. Sun A. Short text classification using very few words[C]// Proceedings of the 35th international ACM SIGIR conference on Research and development in information retrieval. New York, USA, 2012:1145-1146.

4. Kalogeratos A, Likas A. Text document clustering using global term context vectors[J]. Knowledge and information systems, 2012, 31(3):455-474.

5. Cheng X, Miao D Q, Wang C, et al. Coupled Term-Term Relation Analysis for Document Clustering[C]//Proceedings of Neural Networks International Joint Conference on Artificial Intelligence (IJCNN).Dallas TX USA, IEEE, 2013: 1-8.

6. Liu W, Quan X, Feng M, et al. A short text modeling method combining semantic and statistical information[J]. Information Sciences, 2010, 180(20):4031-4041.

7. Yuan M. Feature Extension for Short Text Categorization Using Frequent Term Sets[J]. Procedia Computer Science, 2014, 31:663-670.

8. Qinghua H U, Guo M Z, DaRen amp Y U. Information entropy for ordinal classification[J]. SCIENCE CHINA, 2010, 53(6):1188-1200.

9. Bollegala D, Matsuo Y, Measuring semantic similarity between words using web search engines[C]//Proceedings of the Workshop on Social and Collaborative Construction of Structured Knowledge at the 16th International World Wide Conference (WWW2007), New York, USA, ACM, 2007:757-786.

10. Lee D D, Seung H S. Learning the parts of objects by non-negative matrix factorization[J]. Nature, 1999, 401(6755):788-791.

11. Lang K, Newsweeder. Learning to filter netnews[C]// Proceedings of the Twelfth International Conference on Machine Learning. Tahoe City, California, Morgan Kaufmann.1995: 331-339.

12. Sougou lib. http://www.Sogou.com/labs/dl/c.html,(2012-09-01) [2012-04-30].