Usually web search results are represented as long list of document snippets. It is di cult for users to navigate through this collection of text. We propose clustering method that uses pattern structure constructed on augmented syntactic parse trees. In addition, we compare our method to other clustering methods and demonstrate the limitations of the competitive methods.
Document clustering problem has been widely investigated in many applications
of text mining. One of the most important aspects of a text clustering problem is
a structured representation of text. The common approach to text representation
is the Vector Space Model [
However, a term-document matrix built on a large texts collection may be
sparse and have high dimensionality. To reduce the feature space one may use
PCA, truncated SVD (Latent Semantic Analysis), random projection and other
methods. To handle synonyms as similar terms a Generalized Vector Space
Model [
Graph models are also used for text representation. Document Index Graph
(DIG) was proposed by Hammouda [
In this paper, we consider a particular application of document clustering:
representation of web search results that could make it easier for users to nd the
information they are looking for [
Parse Thickets Parse thicket [
FCA A formal context is a triple (G; M; I), where G and M be sets, called the set of objects and attributes, respectively. Let I be a relation I G M between objects and attributes, i.e. (g; m) 2 I if the object g has the attribute m. The derivation operator ( )0 are de ned for A G and B M as follows: A0 = fm 2 M j8g 2 A : gImg
B0 = fg 2 Gj8m 2 B : gImg
A0 is the set of attributes common to all objects of A and B0 is the set of objects
sharing all attributes of B. The double application of ( )0 is a closure operator,
i.e., ( )00 is extensive, idempotent and monotone. Sets (A)00 and (B)00 are said to
be closed. A formal concept is a pair (A; B), where A G, B M and A0 = B,
B0 = A. A and B are called the formal extent and the formal intent, respectively.
Pattern Structure and Projections Pattern Structures are generalization of
formal contexts, where objects are described by more complex structures, rather
than a binary data. A pattern structure [
G d := fg 2 Gjd v
(g)g for d 2 D A pair (A; d) for which A = d and d = A is called a pattern concept.
A projection is a kernel operator, i.e. it is monotone (x v y ) (x) v (y)), contractive ( (x) v x), and idempotent ( ( (x)) = (x)). The mapping : D ! D is used to replace (G; (D; u) ; ) by (G; (D ; u ) ; ), where D = fd 2 Dj9d0 2 D : (d0) = dg.
In our case, an original paragraph of text and parse thickets constructed from this paragraph correspond to an object and a description of pattern concepts respectively. To improve e ciency and decrease time complexity we use projection instead of a parse thicket itself. Projection on a parse thicket is de ned as a set of its maximal sub-trees and the intersection operator takes the form of pairwise intersection of elements within noun and verb phrase groups. 3
A pattern structure constructed from the collection of short texts usually has a huge number of concepts. To reduce the computational costs and improve the interpretability of pattern concepts we introduce several metrics that are described below.
Average and Maximal Pattern Score The average and maximal pattern score indices are meant to assess how meaningful is the common description of texts in the concept. The higher the di erence of text fragments from each other, the lower their shared content is. Thus, meaningfulness criterion of a pattern concept hA; di is
Scoremax hA; di :=
max Score (chunk) chunk2d Scoreavg hA; di := 1 X jdj chunk2d
Score (chunk)
The score function Score (chunk) estimates description d using its weights for di erent parts of speech.
Average and Minimal Pattern Loss Score This scores estimate how much information contained in the description of a text is lost with respect to the original text. The average pattern loss score calculates the average loss of a cluster content with respect to texts in this cluster, while minimal pattern score loss represents a minimal loss of content among all texts included in a concept.
ScoreLossmin hA; di := 1
ming2A Scoremax hg; dgi
ScoreLossavg hA; di := 1
jd1j Pg2A Scoremax hg; dgi
We use a reduced pattern structure. We propose to create exactly meaningful pattern concepts. For arbitrary sets of texts A1 and A2, corresponding descriptions d1, d2 and candidate for a pattern concept hA1 [ A2 ; d1 \ d2i need to satisfy the following constrains
Score hA1 [ A2 ; d1 \ d2i
The rst constraint provides condition for the construction of concepts with meaningful content, while two other constrains ensure that we do not use concepts with similar content. 4
In this section we consider two examples for the proposed clustering method. The rst one corresponds to the case when clusters are overlapping and distinguishable, the second one is the case of non-overlapping clusters. 4.1
User Study
In the most cases it is quite di cult to identify disjoint classes for a text collection
[
According to the experts, it was di cult to determine partitions, while overlapping clusters naturally stood out. As a result, in the case of non-overlapping clusters we usually got a small number of large classes or a su ciently large number of classes consisting of 1-2 snippets. More than that, for the same set of snippets we obtained quite di erent partitions.
We used the Adjusted Mutual Information score to estimate pairwise agreement of non-overlapping clusters, which were identi ed by the experts. This metric allows one to estimate agreement of two clustering results with correction for randomness partition.
M Iadj =
M I (U; V ) E [M I (U; V )] max (H(U ); H(V )) E [M I (U; V )] where U and V are partitions of the news set, M I(U; V ) - the mutual information between them and E [M I (U; V )] is the expected mutual information between two random clusterings.
To study the behavior of the conventional clustering approach we consider 12 short texts on news query \The Ebola epidemic". Tests are available by link 1.
Experts identify quite di erent non-overlapping clusters. The pairwise Adjusted Mutual Information score was in the range of 0,03 to 0,51. Next, we 1 https://drive.google.com/file/d/0B7I9HM34b_62TEFtUTRqdzdqWjA/view?usp= sharing compared partitions to clustering results of the following clustering methods: kmeans clustering based on vectors obtained by truncated SVD (retaining at least 80% of the information), hierarchical agglomerative clustering (HAC), complete and average linkage of the term-document matrix with Manhattan distance and cosine similarity, hierarchical agglomerative clustering (both linkage) of tf-idf matrix with Euclidean metric. In other words, we turned an unsupervised learning problem into the supervised one. The accuracy score for di erent clustering methods is represented in Figure 1. Curves correspond to the di erent partitions that have been identi ed by people.
As it was mentioned earlier, we obtain inconsistent \true" labeling. Thereby the accuracy of clustering di ers from labeling made by evaluators. This approach doesn't allow to determine the best partition, because a partition itself is not natural for the given news set. For example, consider clusters obtained by HAC based on cosine similarity (trade-o between high accuracy and its low variation): 1-st cluster: 1,2,7,9; 2-nd cluster: 3,11,12; 3-rd cluster: 4,8; 4-th cluster: 5,6; 5-th cluster: 10.
Almost the same news 4, 8, 12 and 9, 10 are in the di erent clusters. News 10, 11 should be simultaneously in several clusters (1-st, 5-th and 2-nd,3-rd respectively). 4.2
Examples of pattern structures clustering To construct hierarchy of overlapping clusters by the proposed methods, we use the following constraints: = 0; 75, 1 = 0; 1 and 2 = 0; 9. The value of limits the depth of the pattern structure (the maximal number of texts in a cluster), put di erently, the higher , the closer should be the general intent of clusters.
1 and 2 determine the degree of dissimilarity of the clusters on di erent levels of the lattice (the clusters are prepared by adding a new document to the current one).
We consider the proposed clustering method on 2 examples. The rst one was described above, it corresponds to the case of overlapping clusters, the second one is the case when clusters are non-overlapping and distinguishable. Texts of the second example are available by link 2. Three clusters are naturally identi ed in this texts.
The cluster distribution depending on volume are shown in Table 1. We got 107 and 29 clusters for the rst and the second example respectively.
Text number 1 2 3 4 5 6 Example 1 12 34 33 20 7 1
Example 2 11 15 3 0 0 0
In fact, this method is an agglomerative hierarchical clustering with overlapping clusters. Hierarchical structure of clusters provides browsing of texts with similar content by layers. The cluster structure is represented on Figure 2. The top of the structure corresponds to meaningless clusters that consist of all texts. Upper layer consists of clusters with large volume.
(a) pattern structure without reduction (b) reduced pattern structure
MaxScore Cluster (extent) MaxScore Cluster (extent) MaxScore Cluster (extent) 7,8 f3, 11, 12g 3,8 f1, 2, 3, 7, 9g 3,2 f3, 9, 11g 4,1 f4, 8, 11g 3,3 f2, 4, 11g 2,8 f3, 10g 3,8 f1, 5, 11g 3,3 f2, 11g 2,4 f1, 2, 6, 9, 10g 3,8 f1, 11g 3,3 f5, 6g 2,3 f1, 5, 6g
We also consider smaller clusters and select those for which adding of any object (text) dramatically reduces the M axScore f1; 2; 3; 7; 9g and f5; 6g. For 2 https://drive.google.com/file/d/0B7I9HM34b_62czFlZ29zZl9kblk/view?usp= sharing other nested clusters signi cant decrease of M axScore occurred exactly with the an expansion of single clusters.
For the second example we obtained 3 clusters that corresponds to \true" labeling.
Our experiments show that pattern structure clustering allows to identify easily interpretable groups of texts and signi cantly improves text browsing. 5
In this paper, we presented an approach that addressed the problem of short text clustering. Our study shows a failure of the traditional clustering methods, such as k-means and HAC. We propose to use parse thickets that retain the structure of sentences instead of the term-document matrix and to build the reduced pattern structures to obtain overlapping groups of texts. Experimental results demonstrate considerable improvement of browsing and navigation through a texts set for users. Introduced indices Score and ScoreLoss both improve computing e ciency and tackle the problem of redundant clusters.
An important direction for future work is to take into account synonymy and to compare the proposed method to similar approach that use key words instead of parse thickets.
The project is being developed by the \Methods of web corpus collection, analysis and visualisation" research and study group under guidance of prof. B.Mirkin (grant 15 - 05 - 0041 of Academic Fund Program).