A web search engine usually returns a long list of documents and it may be difficult for users to navigate through this collection and find the most relevant ones. We present an approach to post-retrieval snippet clustering based on pattern structures construction on augmented syntactic parse trees. Since an algorithm may be too slow for a typical collection of snippets, we propose a reduction method that allows us to construct a reduced pattern structure and make it scalable. Our algorithm takes into account discourse information to make clustering results independent of how information is distributed between sentences.
Introduction and related works The document clustering problem was widely investigated in many applications of text mining. One of the most important aspects of the text clustering problem is a structural representation of texts. A common approach to the text representation is a vector space model (Salton et al., 1975) , where the collection or corpus of documents is represented as a term-document matrix. The main drawback of this model is its inability to reflect the importance of a word with respect to a document and a corpus. To tackle this issue the weighted scheme based on tf-idf score has been proposed. Also, a term-document matrix built on a large texts collection may be sparse and have a high dimensionality. To reduce feature space, PCA, truncated SVD (Latent Semantic Analysis), random projection and other methods have been proposed. To handle synonyms as similar terms the general Vector Space Model (Wong et al., 1985; Tsatsaronis and Panagiotopoulou, 2009 ), topic-based vector model (Becker and Kuropka, 2003) and enhanced topic-based vector space model (Polyvyanyy and Kuropka, 2007) were introduced. The most common ways to clustering term-document matrix are hierarchical clustering, k-means and also bisecting k-means. Graph models are also used for text representation. Document Index Graph (DIG) was proposed by Hammouda (2004) . Zamir and Etzioni (1998) use suffix tree for representing web snippets, where words are used instead of characters. A more sophisticated model based on n-grams was introduced in Schenker et al. (2007) . In this paper, we consider a particular application of document clustering, it is a representation of web search results that could improve navigation through relevant documents. Clustering snippets on salient phrases is described in (Zamir and Etzioni, 1999; Zeng et al., 2004) . But the most promising approach for document clustering is a conceptual clustering, because it allows to obtain overlapping clusters and to organize them into a hierarchical structure as well (Cole et al., 2003; Koester, 2006; Messai et al., 2008; Carpineto and Romano, 1996) . We present an approach to selecting most significant clusters based on a pattern structure (Ganter and Kuznetsov, 2001 ). An approach of extended representation of syntactic trees with discourse relations between them was introduced in (Galitsky et al., 2013) . Leveraging discourse information allows to combine news articles not only by keyword similarity but by broader topicality and writing styles as well. The paper is organized as follows. Section 2 introduces a parse thicket and its simplified representation. In section 3 we consider approach to clustering web snippets and discuss efficiency issues. The illustrative example is presented in section 4. Finally, we conclude the paper and discuss some research perspectives. 2 Clustering based on pattern structure Parse Thickets Parse thicket (Galitsky et al., 2013) is defined as a set of parse trees for each sentence augmented with a number of arcs, reflecting inter-sentence relations. In present work we use parse thickets based on limited set of relations described in (Galitsky et al., 2013) : coreferences (Lee et al., 2012) , Rhetoric structure relations (Mann and Thompson, 1992) and Communicative Actions (Searle, 1969) . Pattern Structure with Parse Thickets simplification To apply parse thickets to text clustering tasks we use pattern structures (Ganter and Kuznetsov, 2001 ) that is defined as a triple (G, (D, ) , δ), where G is a set of objects, (D, ) is a complete meet-semilattice of descriptions and δ : G → D is a mapping an object to a description. The Galois connection between set of objects and their descriptions is also defined as follows: A := g ∈ A δ (g) d := {g ∈ G|d δ (g)} for A ⊆ G, for d ∈ D A pair A, d for which A = d and d = A is called a pattern concept. In our case, A is the set of news, d is their shared content. We use AddIntent algorithm (van der Merwe et al., 2004) to construct pattern structure. On each step, it takes the parse thicket (or chunks) of a web snippet of the input and plugs it into the pattern structure. A pattern structure has several drawbacks. Firstly, the size of the structure could grow exponentially on the input data. More than that, construction of a pattern structure could be computationally intensive. To address the performance issues, we reduce the set of all intersections between the members of our training set (maximal common sub-parse thickets). Reduced pattern structure Pattern structure constructed from a 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 the common description of texts in the concept is. The higher the difference of text fragments from each other, the lower their shared content is. Thus, meaningfulness criterion of the group of texts is Score max A, d := max chunk∈d Score (chunk) Score avg A, d := 1 |d| chunk∈d Score (chunk) The score function Score (chunk) estimates chunks on the basis of parts of speech composition. Average and Minimal Pattern Score loss Average and minimal pattern score loss describe how much information contained in text is lost in the description with respect to the source texts. Average pattern score loss expresses the average loss of shared content for all texts in a concept, while minimal pattern score loss represents a minimal loss of content among all texts included in a concept. ScoreLoss min A, d := min g∈A Score max g, d g ScoreLoss avg A, d := 1 |d| g∈A Score max g, d g We propose to use a reduced pattern structure. There are two options in our approach. The first one -construction of lower semilattice. This is similar to iceberg concept lattice approach (Stumme et al., 2002) . The second option -construction of concepts which are different from each other. Thus, for arbitrary sets of texts A 1 and A 2 , corresponding descriptions d 1 and d 2 and candidate for a pattern concept A 1 ∪ A 2 , d 1 ∩ d 2 criterion has the following form Score max A 1 ∪ A 2 , d 1 ∩ d 2 ≥ θ Score * A 1 ∪ A 2 , d 1 ∩ d 2 ≥ µ 1 min {Score * A 1 , d 1 , Score * A 2 , d 2 } Score * A 1 ∪ A 2 , d 1 ∩ d 2 ≤ µ 2 max {Score * A 1 , d 1 , Score * A 2 , d 2 } The first constraint provides the condition for the construction of concepts with meaningful content, while two other constrains ensure that we do not use concepts with similar content. Experiments In this section we consider the proposed clustering method on 2 examples. The first one corresponds to the case when clusters are overlapping and distinguishable, the second one is the case of non-overlapping clusters. User Study In some cases it is quite difficult to identify disjoint classes for a text collection. To confirm this, we conducted experiments similar to the experiment scheme described in (Zeng et al., 2004) . We took web snippets obtained by querying the Bing search engine API and asked a group of four assessors to label ground truth for them. We performed news queries related to world's most pressing news (for example, "fighting Ebola with nanoparticles", "turning brown eyes blue", "F1 winners", "read facial expressions through webcam", "2015 ACM awards winners") to make labeling of data easier for the assessors. In most cases, according to the assessors, it was difficult 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 sufficiently large number of classes consisting of 1-2 snippets. More than that, for the same set of snippets we obtained quite different partitions. We used the Adjusted Mutual Information score to estimate pairwise agreement of nonoverlapping clusters, which were identified by the people. To demonstrate the failure of the conventional clustering approach we consider 12 short texts on news query "The Ebola epidemic". Tests are available by link 1 . Assessors identify quite different nonoverlapping clusters. The pairwise Adjusted Mutual Information score was in the range of 0,03 to 0,51. Next, we compared partitions to clustering results of the following clustering methods: k-means 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 different clustering methods is represented in Figure 1 . Curves correspond to the different partitions that have been identified by people. As it was mentioned earlier, we obtain incon-1 https://github.com/anonymously1/ CNS2015/blob/master/NewsSet1 Figure 1 : Classification accuracy of clustering results and "true" clustering (example 1). Four lines are different news labeling made by people. The y-axis values for fixed x-value correspond to classification accuracy of a clustering method for each of the four labeling sistent "true" labeling. Thereby the accuracy of clustering differs 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-off 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 different clusters. News 10, 11 should be simultaneously in several clusters (1-st, 5-th and 2-nd,3-rd respectively). Examples of pattern structures clustering To construct hierarchy of overlapping clusters by the proposed methods, we use the following constraints: θ = 0, 25, µ 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 differently, the higher θ, the closer should be the general intent of clusters. µ 1 and µ 2 determine the degree of dissimilarity of the clusters on different 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 first one was described above, it corresponds to the case of overlapping clusters, the second one is the case when clusters are nonoverlapping and distinguishable. Texts of the sec-ond example are available by link 2 . Three clusters are naturally identified in this texts. The cluster distribution depending on volume are shown in Table 1 . We got 107 and 29 clusters for the first and the second example respectively. Text number Clusters number Example 1 Example 2  1  12  11  2  34  15  3  33  3  4 20 0 5 7 0 6 1 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 Figure 2 : The cluster structure (example 2). The node on the top corresponds to the "dummy" cluster, high level nodes correspond to the big clusters with quite general content, while the clusters at lower levels correspond to more specific news. Clustering based on pattern structures provides well interpretable groups. The upper level of hierarchy (the most representative clusters for example 1) consists of the clusters presented in Table 2 We also consider smaller clusters and select those for which adding of any object (text) dramatically reduces the M axScore {1, 2, 3, 7, 9} and {5, 6}. For other nested clusters significant 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 significantly improves text browsing. Conclusion 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 texts set for users. Introduced indices Score and ScoreLoss both improve computing efficiency 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.
1 3 4 4.1 4.2 5
Introduction and related works Reduced pattern structure Experiments User Study Examples of pattern structures clustering Conclusion
Reduced pattern structures constraints
ScoreLoss A1 A2 d1 d2
pattern structure reduced pattern structure without reduction with 1 and
ScoreLoss A1 A2 d1 d2
pattern structure reduced pattern structure without reduction with 1 and