2.1 Web mining

One of the biggest sources of XML documents is the Internet. The Web has become a distributed data and service repository, which holds such vast amounts of information, that it requires dedicated solutions for management and processing. Structural clustering enables effective detection of similarities between documents gathered on the Internet. This information can be applied to solve a variety of Web mining problems, such as document source recognition or structural analysis of websites. XML clustering can also be used to form groups of similar web pages which later can serve as Web wrappers, that is, programs that extract data from HTML pages, and transform them into a machine-processable format. By combining structural clustering and Web wrappers, financial data published by several specialized websites only in HTML can be constantly extracted and processed for mining purposes. Similarly, data delivered on the Web by thematic communities can be extracted and integrated via structural XML clustering (Crescenzi et al., Reference Crescenzi, Mecca and Merialdo2001, Reference Crescenzi, Merialdo and Missier2005).

2.2 XML data integration

XML is prevalent among standards for exchanging and integrating data between websites as well as other data-oriented applications. One of the most significant steps of data integration is identifying structurally and semantically similar documents (Lee et al., Reference Lee, Yang, Hsu and Yang2002; Viyanon et al., Reference Viyanon, Madria and Bhowmick2008). Such an analysis can be performed to find the same pieces of information presented in different forms or to identify human errors, which occurred during the creation of documents.

2.3 Bioinformatics

Natural sciences, such as biology and chemistry, use the XML standard as a means of representing hierarchies and relationships. As XML can be easily exchanged among several research groups, it has been used in collaborative environments for pedigree data management (Achard et al., Reference Achard, Vaysseix and Barillot2001). Another example of structural clustering in biology is the discovery of homologous proteins, that is, sets of proteins sharing similar structures. Other applications in this field include gene clustering (Andreopoulos et al., Reference Andreopoulos, An, Wang and Schroeder2009) and DNA/protein sequence clustering (Sankoff & Kruskal, Reference Sankoff and Kruskal2000; Somervuo & Kohonen, Reference Somervuo and Kohonen2000). The use of structural algorithms in these areas is especially beneficial as real-world biological data sets are extremely large and require lightweight processing.

2.4 Spatial data management

The hierarchical nature of XML is often used to represent documents describing spatial data. XML grammars, such as the Geographical Markup Language (Pospech, Reference Pospech2009) or the Keyhole Markup Language (Wernecke, Reference Wernecke2008), are used as modeling languages and Web service interchange formats. In these languages, spatial information like areas that include lakes, rivers, wells, or farms can be represented as tree structures. Furthermore, XML is also used to describe waypoints, tracks, and routes on maps. Structural clustering of spatial objects and routes can help to identify similar geographic objects, for example, large areas with similar lake-forest spatial arrangements (Wilson et al., Reference Wilson, Cobb, McCreedy, Ladner, Olivier, Lovitt, Shaw, Petry and Abdelguerfi2003; Zhu et al., Reference Zhu, Ji and Sun2010) or tourist travel patterns (Zheng et al., Reference Zheng, Li, Zha and Chua2011).

In all of the above scenarios, XML clustering by structure plays a crucial role in processing large volumes of data. It is worth noting that, although the described applications differ in the expected outcome and objective, the clustering process itself remains the same and can be formulated into a general XML clustering methodology.

3.1 Feature extraction

Before input objects can be grouped or even compared, they have to be transformed into a representation that allows for effective processing. If one is to cluster news articles from different content providers, he/she has to extract essential information from those articles and represent it in a form that will facilitate article comparison. In the field of XML clustering, this step is especially important as XML documents contain not only textual but also structural information and can grow fairly large in size. Therefore, the developers of XML clustering algorithms should aim at using descriptive yet compact representations. The most popular XML document representations include graphs, trees, vectors, and sets of paths. These and more possible representations will be discussed in detail in Section 4.

3.2 Similarity evaluation

Once the documents are represented in a concise format they can be compared according to a chosen similarity measure. If the first step of the presented clustering methodology was meant to extract interesting features from input objects, then the aim of the second step is to determine which of the selected features, and to what extent, decide whether two objects are similar. As we can only use the features available in the transformed objects, it becomes apparent that the selected object representation has a huge impact on similarity evaluation. Following our example, depending on the representation we selected to encode news articles, we can choose to calculate their similarity according to section titles, keywords, section–subsection hierarchy, or even the number of paragraphs. Typical XML structural similarity measures, including tree-edit distance, vector distance, and other measures, will be discussed in Section 5.

3.3 Clustering

After comparing the input objects we can use the obtained knowledge to group them into clusters. The information about which pairs of objects are alike is usually stored in a similarity matrix, which contains data describing the distances between all documents in the data set. There are many clustering algorithms which use the results of similarity evaluation to group documents. For the purposes of this paper we divide the clustering algorithms into two main groups of methods: hierarchical and flat. The most popular examples of these approaches in the context of XML clustering will be discussed in Section 6.

As clustering is a form of unsupervised learning from data, it requires automatic evaluation methods rather than supervised training. For this reason, many clustering methods restart the analysis after evaluating the obtained results—a situation depicted with a feedback loop in Figure 2. In this case, clustering algorithms use evaluation methods, also called validation indices, which consider factors like intra-cluster document similarity, dissimilarity of documents from different clusters, or coverage of the data set. Validation indices are required to ensure that obtained clusters are of practical value and are especially needed when dealing with high dimensional data, where clusters cannot be easily visualized and verified. Regarding the example of clustering news articles, depending on the selection of a clustering algorithm and evaluation measure, the user can obtain groups of articles which are very dissimilar between groups or, in contrast, groups that overlap. Section 7 discusses the most popular evaluation methods used in XML clustering.

In the following sections, we discuss common approaches to each step of the presented clustering methodology. Although the approaches will be discussed separately for each step, it should be remembered that in order to create a successful clustering algorithm the selected methods should be carefully matched. As XML is popular among many domain-specific applications, structural clustering algorithms work best when tailored to the needs of the end-user. Therefore, no single combination of the presented approaches is best for all applications and end-requirements should be taken into account when designing new XML clustering algorithms.

4.1 Tree

One of the most common representations of an XML document is a rooted labeled tree defined as a four-tuple $$T=(N_{T} ,E_{T} ,L_{T} ,\alpha )$$ , where:

• ∙ $$N_{T} =\{ n_{{root}} ,n_{2} ,...,n_{n} \} $$ is a finite set of uniquely identified nodes, where $$n_{{root}} $$ represents the root node;

• ∙ $$E_{T} =\{ (n_{i} ,n_{j} ):n_{i} ,n_{j} \in N_{T} \} $$ is a finite set of edges, where $$n_{i} $$ is the parent node of $$n_{j} $$ ;

• ∙ $$L_{T} $$ is a set of node labels corresponding to element and attribute names from an XML document;

• ∙ $$\alpha :N_{T} \to L_{T} $$ is a function mapping each node into a label.

This representation is often further restricted with a left-to-right order among siblings. When such order is provided, the tree is called ordered. Figure 4 illustrates the structure of an XML document represented as a rooted ordered labeled tree.

Figure 4

Tree representation

In an XML document tree we can distinguish several relationships among the elements:

• ∙ parent–child: a relationship between each element node and its direct subelement/attribute;

• ∙ ancestor–descendant: a relationship between each element node and its direct or indirect subelement/attribute;

• ∙ order: a relationship between siblings.

It is worth mentioning that, although there are in fact two node types (elements and attributes), in the vast majority of existing approaches they are treated equivalently.

4.2 Vector

The tree representation is the most natural and informative for XML documents, but often requires complex computations. Decomposing a tree into smaller parts is usually accompanied by information loss, however, it may reduce the complexity of similarity evaluation. The information loss involves reducing the number of relationships between tree nodes. Depending on the extent of reduction we can obtain paths, edges, or, after reducing all node relationships, individual tags.

A path is a list of consecutive nodes in a tree according to the parent–child relationship. A path beginning with a root node and ending with a leaf is called a full path. If we focus only on the direct relations between tree nodes, we can represent a document as a group of edges. This way the parent–child relationships remain, but the complexity reduction is very high. Finally, we can remove all relationships between the nodes, leaving only node labels.

As described above, the vector representation may reduce the structural information to a varied extent. Several approaches based on this representation have been proposed (Yoon et al., Reference Yoon, Raghavan, Chakilam and Kerschberg2001; Theobald, Reference Theobald2003; Tran et al., Reference Tran, Nayak and Bruza2008; Lesniewska, Reference Lesniewska2009) and most of them use a full path decomposition. Each XML document is modeled as a vector $$\vec {\upsilon }\in {\cal R} ^{m} $$ , where m is the number of different full paths in the data set and each element v _i the frequency of a single full path in that document. Together, all document vectors produce a two-dimensional matrix m×n representing the whole data set, where n is the number of all documents. An example of such a representation is shown in Table 1, where D1 is the sample document from Figure 3 and D2 and D3 are other documents in the data set.

Table 1

Vectors of full path frequencies

This approach can be slightly modified by limiting the maximal length of the paths. Naturally, such a modification further reduces the structural information in the documents, however, it may aid the process of similarity computation, because shorter paths are more likely to co-occur in the compared documents. An example of a vector representation with path length limited to 1 (tag-only approach) is presented in Table 2.

Table 2

Vectors of label frequencies

4.3 Other

A structure which decomposes documents in a similar way in which the vector representation does, is the set representation. In this approach, a document is also broken down into parts, such as paths or edges, however, it is not encoded into a numerical vector. Conversely, a set (or a multiset) consisting of these parts constitutes the representation. In this way, even though some structural information is lost during the decomposition, it is still possible to directly compare the parts of the documents when evaluating their similarity. Such a comparison is impossible when documents are encoded into numerical vectors. Figure 5 shows the sample document D1 represented as a set of paths.

Figure 5

Set of paths representation

The structure of an XML document may also be transformed into a graph. An example of a graph representation is the s-graph (Lian et al., Reference Lian, Cheung, Mamoulis and Yiu2004). Given an XML document d, an s-graph of d, sg(d)=(N, E), is a directed graph such that N is the set of all the elements and attributes in d and E is the set of all edges in d. An s-graph based on our sample XML document D1 is depicted in Figure 6.

Figure 6

S-graph representation

An XML document can also be represented as a time series where each occurrence of a tag corresponds with an impulse (Flesca et al., Reference Flesca, Manco, Masciari, Pontieri and Pugliese2005). In this case, node labels are completely omitted and only the element nesting is taken into account. To better explain this representation, one can visualize an XML document rotated by 90° with a line drawn following the document’s indentation (the higher the node level in a document tree the bigger the indentation). Figure 7 shows the sample XML document D1 represented as a time series.

Figure 7

Time series representation

Another approach, one of the most lightweight representations of XML, relies on transforming each document into a single numeric value, called a feature (Lesniewska & Primke, Reference Lesniewska and Primke2008). This number represents some general structural characteristic of a document, for example, number of nodes, number of leaves, number of distinct labels, number of distinct full paths, or maximal path length. While highly efficient, this representation significantly reduces the information collected from the documents and is insufficient for most XML clustering applications. Nevertheless, it may be used for preliminary analysis of very large data sets.

5.1 Tree

The most natural and widely used representation of XML is the rooted ordered labeled tree, as it fully preserves the hierarchical nature of the documents. If one intends to utilize this information for similarity evaluation, one has to use a measure which is capable of comparing tree representations. The most widely used method for computing the distance between trees is called tree-edit distance and is calculated as the minimal number of predefined operations required to transform one tree into another. Such a procedure computes the similarity between entire documents, not just their parts.

The tree-edit distance is associated with three atomic edit operations conducted on nodes of a rooted ordered labeled tree: deletion, insertion, and relabeling. Let t ₁ and t ₂ be a pair of rooted ordered labeled trees. A tree-edit sequence is a sequence of tree operations that transforms t ₁ into t ₂. If we assign a cost to every operation, the tree-edit distance between t ₁ and t ₂ will be the minimum cost of all possible tree-edit sequences that transform t ₁ into t ₂. Below we present selected tree-edit distance methods chosen based on their novelty in terms of allowed edit operations and applicability in XML processing.

One of the earliest approaches to evaluating similarity between trees using sequences of simple edit operations was introduced by Selkow (Reference Selkow1977). This solution, however, restricted the insertion and deletion operations to the leaf nodes exclusively and had an exponential complexity. The first non-exponential approach to solving this problem was introduced by Tai (Reference Tai1979). The author presented an algorithm of polynomial complexity $$O( \mid \! t_{1} \!\!\mid\ \mid \! t_{2} \! \mid \! depth(t_{1} )depth(t_{2} ))$$ , where $$ \! \mid \! t_{i} \! \mid \! $$ is the number of nodes and depth(t _i) the depth of the ith tree. Furthermore, this solution lacked the restriction on edit operations, allowing for insertion and deletion of any nodes in the tree. Currently, the most efficient tree-edit distance algorithm allowing for edit operations to appear anywhere in a tree is the RTED, proposed by Pawlik and Augsten (Reference Pawlik and Augsten2011).

One of the first tree-edit distance measures specific to the XML format was proposed by Chawathe (Reference Chawathe1999). In this approach, the author reestablished the restriction on insert and delete operations to leaf nodes exclusively. He claimed that insert and delete operations in the middle of an XML document tree are unnatural, as they are followed by the children nodes transfer and, therefore, not only the nodes change but also the relationships between them. The proposed restriction reduced the algorithm complexity to $$O( \mid \! t_{1} \! \mid \ \! \mid \! t_{2} \! \mid )$$ without decreasing the quality of the results. Nierman and Jagadish (Reference Nierman and Jagadish2002) proposed a solution in which they allow for restricted insertions and deletions of whole subtrees. A subtree s can be inserted into a tree t only if the root node of s will become a child node of one of the leaf nodes in t. A subtree s can be deleted from a tree t only if the leaf nodes of s are also the leaf nodes of t. This solution presents a slightly higher complexity than Chawate’s approach, however, it outperforms his algorithm in terms of clustering quality.

In Table 3, we have summarized the most important tree-edit distance approaches in the context of XML similarity. The table presents the algorithms along with their supported operations and complexities.

Table 3

Summary of most relevant approaches to tree-edit distance

*Operations restricted to leaves.

5.2 Vector

The vector representation has two main advantages. First, the values in the vector may correspond to a wide variety of features, like subtrees, paths, edges, tags, XPath queries, etc. Second, there already exist many different measures designed for computing similarity between two vectors.

Given two XML documents d ₁ and d ₂ represented as binary vectors, the distance between these documents may be defined as follows:

$$Dist(d_{1} ,d_{2} )=\mathop{\sum}\limits_{i=1}^n \! \mid \! v_{1} [i]{\minus}v_{2} [i] \! \mid \! $$

where v ₁ and v ₂ denote documents d ₁ and d ₂ represented as binary vectors and n is the number of all distinct features in the data set. This simple distance measure illustrates the number of features which are different in the compared documents, and may also be presented as a normalized similarity measure:

$$Sim(d_{1} ,d_{2} )=1{\minus}{{\mathop{\sum}\nolimits_{i=1}^n { \! \mid \! v_{1} [i]{\minus}v_{2} [i] \! \mid \! } } \over {\mathop{\sum}\nolimits_{i=1}^n {v_{1} [i]\,\oplus\,v_{2} [i]} }}$$

where $\,\oplus\,$ is a bitwise or operation performed on each pair of corresponding vector cells. This measure shows the percentage of common features shared between two documents.

If we represent two XML documents d ₁, d ₂ as real vectors v ₁ and v ₂ (e.g. by including the quantity of feature occurrences or by weighting features) we may use metric distances. The most commonly used metric for computing distances between two vectors is the Minkowski distance, calculated as:

$$L_{p} (v_{1} ,v_{2} )=\root p \of {\mathop{\sum}\limits_{i=1}^n \! \mid \! v_{1} [i]{\minus}v_{2} [i] \! \mid ^{p} } $$

where n is the number of all distinct features in the documents, and $$p\in \cal R _{{\plus}} $$ a user-defined metric parameter. Thanks to this parameter, the Minkowski distance is in fact an infinite family of metrics. The best known and commonly used metrics from the Minkowski family are the Euclidean distance (L ₂) and the Manhattan distance (L ₁). Figure 8 presents some examples of Minkowski distances.

Figure 8

Examples of Minkowski distances. The figures mark an equal distance from the center point for each metric

The distances calculated with the Euclidean metric can be easily analyzed because the subsequent values in a vector may be considered as co-ordinates of a point in n-dimensional space, where n is the size of the vector. In the context of XML, however, where elements often appear multiple times in a single document, the cosine distance is a more popular choice. Instead of measuring the Euclidean distance between points in n-dimensional space, the cosine distance measures an angle between the vectors. This way, although the information about multiple label occurrences is preserved, it has a smaller impact on the result. The cosine distance between two XML documents represented as real vectors is defined as:

$$Sim_{{{\rm cos}}} (d_{1} ,d_{2} )={{v_{1} \cdot v_{2} } \over { \mid \mid \!v_{1} \! \mid \mid \ \mid \mid \!v_{2} \!\mid \mid }}$$

Another metric used for measuring similarity between vectors is the Tanimoto measure. This measure is a vector version of the Jaccard coefficient, which is used for measuring similarity between sets. The following equation presents the definition of the Tanimoto measure:

$$Sim_{{{\rm tan}}} (d_{1} ,d_{2} )={{v_{1} \cdot v_{2} } \over { \mid \mid \!v_{1} \!\mid \mid ^{2} {\plus} \mid \mid \!v_{2} \!\mid \mid ^{2} {\minus}v_{1} \cdot v_{2} }}$$

5.3 Other

The tree and vector representations are the most common and widely used in the XML domain. However, as presented in Section 4, many other interesting approaches exist, which also require specific measures for similarity evaluation. For instance, given two XML documents d ₁ and d ₂ represented as sets $s^{{T_{1} }} $ and $$s^{{T_{2} }} $$ , the aforementioned Jaccard coefficient may be used:

$$Sim_{{Jac}} (d_{1} ,d_{2} )={{ \! \mid \! s^{{T_{1} }} {\cap}s^{{T_{2} }} \! \mid \! } \over { \! \mid \! s^{{T_{1} }} {\cup}s^{{T_{2} }} \! \mid \! }}$$

Another measure, similar to the Jaccard coefficient, was proposed to compute distances between graphs (Lian et al., Reference Lian, Cheung, Mamoulis and Yiu2004). Before calculating this measure, the compared documents are first transformed into s-graphs (sg _i), described earlier in Section 4.3. Next, during the similarity computation each graph is treated as the set of edges it contains. Thus, the similarity measure is defined as follows:

$$Sim_{{SG}} (d_{1} ,d_{2} )={{ \! \mid \! sg_{1} {\cap}sg_{2} \! \mid \! } \over {max\{ \mid \! sg_{1} \! \mid \! , \ \mid \! sg_{2} \! \mid \} }}$$

When two XML documents are represented as time series, the similarity computation requires additional operations. First, the documents can have different lengths, therefore, the time series may require stretching, shrinking, cutting, or other adjustments. In addition, the corresponding signals can be shifted, thus, in order to acquire an accurate comparison, further adjustments may be necessary. These concerns led to the adoption of the discrete Fourier transform (DFT), which addresses the presented issues (Flesca et al., Reference Flesca, Manco, Masciari, Pontieri and Pugliese2002). A distance measure based on this notion uses an interpolation of DFT ( $$D\hat{F}T$$ ) with respect to the frequencies appearing in both documents, and is defined as follows:

$$Dist_{{DFT}} (d_{1} ,d_{2} )=\mathop{\sum}\limits_{k=1}^{M/2} ( \mid \!\! [D\hat{F}T(h_{1} )](k) \! \mid \! {\minus} \! \mid \! [D\hat{F}T(h_{2} )](k) \! \! \mid )^{2} $$

where M is the number of tags appearing in both documents, and h _i the ith document encoded as a time series.

One of the most efficient approaches to computing similarity between XML documents is based on entropy (Helmer, Reference Helmer2007). This solution originates from the normalized information distance (NID), which utilizes the notion of the Kolmogorov complexity. The Kolmogorov complexity K(o) of an object o measures the size of a minimal program required to obtain this object. The NID between objects o ₁ and o ₂ is defined as follows:

$$NID(o_{1} ,o_{2} )={{{\rm max}\{ K(o_{1} \! \mid \! o_{2} ),K(o_{2} \! \mid \! o_{1} )\} } \over {{\rm max}\{ K(o_{1} ),K(o_{2} )\} }}$$

where $$K(o_{1} \! \mid \! o_{2} )$$ is the minimal size of a program producing object o ₁ with the input given as object o ₂.

The Kolmogorov complexity is a theoretical concept, therefore, the NID cannot be used to compute similarity between objects. However, algorithmic complexity can be approximated with data compression algorithms. In such an approach, documents are compressed in a lossless manner and saved as files. The lengths of these files are later compared in order to obtain the normalized compression distance (NCD). Given C(d) as a compressed XML document d and C(d ₁d ₂) as a compressed concatenation of two documents d ₁ and d ₂, NCD is defined as follows:

$$NCD(d_{1} ,d_{2} )={{C(d_{1} d_{2} ){\minus}{\rm min}\{ C(d_{1} ),C(d_{2} )\} } \over {\max \{ C(d_{1} ),C(d_{2} )\} }}$$

As described in Section 3, in the last step of the clustering methodology documents are grouped according to their similarity. In the next section, we present some of the most important clustering techniques that can be used in the final step of the clustering methodology.

6.1 Hierarchical clustering

Hierarchical clustering algorithms are divided into two main families of methods: agglomerative (bottom-up) and divisive (top-down). These methods rely on iterative merging/splitting of single clusters until an algorithm-specific stop condition is reached. The result of this process is a tree chart called a dendrogram, which illustrates the order in which clusters were merged/split. It also shows to what extent the clusters are related to one another.

The first advantage of hierarchical clustering methods is their intuitiveness. They are easy to implement and easy to follow during the execution. The main advantage, however, lies in the output dendrogram as it enables researchers to analyze the relationships between the clusters as well as the order in which they were created. Furthermore, dendrograms facilitate automatic detection of the optimal number of output clusters. This can be achieved by collecting the distances between the clusters divided/merged in each step and computing their standard deviation σ. The number of output clusters may be defined by the first distance exceeding the 3σ threshold. Another benefit of hierarchical approaches is the fact that they are to some extent immune to imbalanced data sets and oddly shaped (non-spherical) clusters.

Despite many advantages and the intuitiveness of the method, hierarchical clustering has also a few drawbacks. The most important drawback is that the assignment of an object to a cluster is final, therefore, once the decision is made it cannot be changed. Another drawback originates from the iterative nature of this method and it is the algorithm’s quadratic complexity, which is high compared with other approaches. The final disadvantage of hierarchical methods is their lack of a global goal function. This property, together with the fact that the object-to-cluster assignment is final, increases the danger of falling into local optimum.

The most popular method for hierarchical clustering is the agglomerative hierarchical clustering algorithm (AHC) (Johnson, Reference Johnson1967), which iteratively joins pairs of clusters based on their similarity. The similarity of two clusters is evaluated based on the distances between their documents. The simplicity of this algorithm and the fact that it can cope with any type of data makes it a very popular choice for XML clustering.

Another well-known method for hierarchical clustering is CURE (Guha et al., Reference Guha, Rastogi and Shim1998). This algorithm partitions the data set into a fixed number of initial clusters and later agglomerates them in a hierarchical fashion, shifting the centroids of the initial clusters toward the centroids of the agglomerated clusters. This mixture of hierarchical and partition-based approaches assures lower complexity than the AHC algorithm. Furthermore, it copes well with imbalanced data, non-spherical clusters, and outliers. However, studies have shown that the parameter setting has a significant influence on the results (Han, Reference Han2005), so, in order to assure high clustering quality, the values of the parameters have to be carefully selected. Moreover, this method is not applicable to categorical data. That is why, in the context of XML clustering, a variation of the CURE algorithm is used, called ROCK (Guha et al., Reference Guha, Rastogi and Shim2000), which is capable of dealing with categorical data.

6.2 Flat clustering

The second family of clustering approaches is constituted by flat methods. In these approaches, unlike the hierarchical methods, in subsequent steps of algorithm execution objects can be relocated between clusters until reaching an algorithm-specific stop condition. The ability to relocate objects between clusters is one of the biggest benefits of flat approaches. Another advantage of flat clustering over hierarchical approaches is lower complexity, because the number of iterations is dictated by the desired accuracy, not the number of objects in the data set. The main disadvantage of non-hierarchical clustering methods is that they usually begin with a random partition, which is only further improved. This leads to a risk of falling into a local optimum as the algorithm tries to improve the partition in each consecutive step.

The most important representative of the flat approaches is the k-means algorithm (Hartigan & Wong, Reference Hartigan and Wong1979). The algorithm forms k initial clusters around randomly chosen points and iteratively improves them. The main drawback of this approach is that centroids are calculated based on the positions of all objects in each cluster. As a result, this method is highly sensitive to outliers. Moreover, due to the fact that objects are assigned to clusters based on their centroids, k-means does not cope well with non-spherical clusters and clusters with different densities. Nevertheless, this method is still a popular choice in the context of XML clustering.

The problem of spherically shaped clusters is eliminated in density-based algorithms. In these approaches, clusters are formed based on the density of objects in a given neighborhood, rather than their distances to cluster means. In addition, these methods usually require only a single full data set scan. The most important representatives of density-based clustering algorithms are DBSCAN (Ester et al., Reference Ester, Kriegel, Sander and Xu1996) and OPTICS (Ankerst et al., Reference Ankerst, Breunig, Kriegel and Sander1999). Among other popular flat clustering algorithms that are used in the context of XML are: EM (Dempster et al., Reference Dempster, Laird and Rubin1977)—useful with imbalanced data sets, and CLOPE (Yang et al., Reference Yang, Guan and You2002)—useful when treating XML documents as transactions (e.g. binary vector of frequent items may be considered as a transaction).

8.1 Tree-edit distance approaches

Out of several tree-edit distance algorithms (Selkow, Reference Selkow1977; Zhang & Shasha, Reference Zhang and Shasha1989; Chawathe et al., Reference Chawathe, Rajaraman, Garcia-Molina and Widom1996; Chawathe, Reference Chawathe1999) Nierman and Jagadish (Reference Nierman and Jagadish2002) put forward an algorithm designed specifically for XML documents. In their approach, the authors propose to represent XML documents as a labeled ordered trees where inner nodes are tags and leaf nodes are tags or attributes. The algorithm allows three basic edit operations: relabeling, leaf insertion, and leaf deletion. In contrast to many other tree-edit distance methods, the authors propose two additional operations: subtree insertion and subtree deletion. Subtree insertions and deletions are limited only to subtrees that are already contained in the source/destination tree, that is, if all nodes of the inserted/deleted subtree occur in the source/destination tree with the same parent–child relationships and the same sibling order (Nierman & Jagadish, Reference Nierman and Jagadish2002). Using the proposed tree-edit distance measure, the authors calculate dissimilarities between XML documents and cluster them with a hierarchical agglomerative algorithm.

An approach that also utilizes the edit distance, called binary branch distance, was put forward by Yang et al. (Reference Yang, Kalnis and Tung2005). Although originally proposed for XML query similarity search, the binary branch distance is a dissimilarity measure which is also suited for clustering algorithms. In this method, Yang et al. propose to transform each XML document into a normalized binary tree. Each node from the original document tree has exactly two children in the binary tree: the left child in the binary tree corresponds to a child in the original tree while the right child corresponds to the right sibling in the original tree. If a node has no child or sibling, a special node ϵ is added. Next, the number of occurrences of each unique triplet (node, left child, right child) is encoded in a vector called the binary branch vector. By subtracting corresponding positions of two binary branch vectors one can calculate the dissimilarity of two documents, called the binary branch distance. Yang et al. stated and proved that the binary branch distance forms a lower bound for tree-edit distance. In contrast to tree-edit distance, the binary branch distance can be calculated in linear time and is one of the most efficient ways of comparing full tree structures.

Dalamagas et al. (Reference Dalamagas, Cheng, Winkel and Sellis2006) proposed to summarize XML tree structures by eliminating the nesting of identical subtrees and the repetition of full paths. The resulting document representation, similar to the data guide structure (Goldman & Widom, Reference Goldman and Widom1997), considerably simplifies document processing. The authors propose to compare summarized documents using the edit distance algorithm proposed by Chawathe (Reference Chawathe1999) and cluster them with a single-link hierarchical method. Moreover, Dalamagas et al. present a way to adopt the C-index (Hubert & Levin, Reference Hubert and Levin1976) in a hierarchical clustering procedure to estimate the optimal number of clusters.

More recently, Tekli and Chbeir (Reference Tekli and Chbeir2012) put forward an XML clustering algorithm that employs a technique similar to that proposed by Nierman and Jagadish. The authors propose a tree-edit distance measure that allows for subtree deletions and insertions. To perform a subtree operation, the algorithm requires the presence of the analyzed subtree in both documents. However, in contrast to the approach proposed by Nierman and Jagadish, the subtrees found in both documents do not need to be identical. This way, when a subtree insertion or deletion is performed, its cost is proportional to the similarity of the two analyzed subtrees, which is calculated as a weighted average of their structural commonality and semantic resemblance. Structural commonality takes into account nodes with the same label, depth, and relative order in both subtrees, while semantic resemblance makes use of the WordNet thesaurus and the cosine measure. By calculating subtree similarity, in contrast to finding contained-in relations like Nierman and Jagadish, the described approach is able to detect a wider set or similarities and, thus, possibly produce more accurate clusters. The proposed tree-edit distance was used with a single-link hierarchical clustering method.

8.2 Substructural similarity approaches

A compromise between fast tag-based methods and accurate edit distance approaches is provided by algorithms that use XML paths for clustering. For example, the PBClustering algorithm (Leung et al., Reference Leung, Chung, fai Chan and Luk2005) describes each XML document as a set of XPath queries from root to leaf. As there can be a large number of such queries, the authors propose to use only the maximal frequent ones, called Common XPaths (CXP). A frequent path is defined as a path that occurs minSup or more times in a data set, where minSup is a user-defined minimum support level. A maximal path is defined as a path which, in a given data set, does not have any superpaths. After extracting all CXPs, each document is encoded as a bit vector. Each bit in this vector corresponds to a CXP and is set to 1 if a document contains that CXP or 0 otherwise. Finally, a similarity matrix is created by comparing each pair of bit vectors and clustering is performed with an agglomerative algorithm.

Another path-based XML clustering algorithm was proposed by Rafiei et al. (Reference Rafiei, Moise and Sun2006). In this algorithm, for each document all paths beginning at the root node are extracted. A set consisting of these paths constitutes a representation for each document. Next, pairwise similarity between all documents is computed. The authors suggest to use one of the existing similarity measures dedicated for sets, like the Jaccard coefficient. Finally, after computing the similarity between all documents in the data set, documents are clustered using the AHC algorithm.

Costa et al. (Reference Costa, Manco, Ortale and Tagarelli2004) proposed an algorithm, called XRep, which also calculates similarity between trees with Jaccard coefficient using sets of tags or paths. In this approach, every cluster has a representative that summarizes this cluster. This representative is a tree which has the lowest distance from all trees in the cluster. Its lower bound is an intersection of all documents in the cluster and its upper bound is their union. Clustering is performed with the AHC algorithm with inter-cluster similarity calculated based on the cluster representatives.

Vercoustre et al. (Reference Vercoustre, Fegas, Gul and Lechevallier2006) proposed a family of path-based representations suited for both, structure and structure and content analysis. In each of these representations, paths are encoded into vectors of term frequencies. When defining paths, the authors consider four options: limiting their length, using different start and end nodes, including their textual content and attribute nodes, or finally, using only textual nodes. Each representation also holds the number of occurrences of each term. After transforming a data set into a chosen representation, the authors reduce the number of paths and resolve any possible dependencies between them. The reduction is performed on two levels: textual—stemming, stop lists, removing words shorter than four; and structural—tag generalization. Path dependencies, that is, superpaths and subpaths, are resolved by decomposing the superpaths into smaller paths. Clustering is performed with the k-means algorithm, where each document is represented as a term frequency vector scaled with the inverse document frequency. Centroids are computed as a sum of all vectors in a given cluster and similarity is evaluated using the Euclidean distance.

Two similar approaches were proposed in Tran et al. (Reference Tran, Nayak and Bruza2007) and Kutty et al. (Reference Kutty, Tran, Nayak and Li2007). The authors utilize a two-phase approach with each document represented as a set of full paths (Tran et al., Reference Tran, Nayak and Bruza2007) or a set of subtrees (Kutty et al., Reference Kutty, Tran, Nayak and Li2007). In the first phase, documents are clustered incrementally into k′ clusters, where k′>k. Each document is compared with every existing cluster and is assigned to the most similar cluster, given that the similarity exceeds a user-defined threshold μ. If not, then the document forms a separate cluster and becomes its representative. In the second phase, the obtained k′ clusters are further merged according to their similarity, until they form k clusters. The similarity between the documents and the cluster representatives is handled differently in these approaches. The authors in Kutty et al. (Reference Kutty, Tran, Nayak and Li2007) use the Jaccard coefficient, while the authors in Tran et al. (Reference Tran, Nayak and Bruza2007) propose an original measure, which calculates the joint similarity of all paths in both documents.

A different approach, called S-GRACE, was proposed by Lian et al. (Reference Lian, Cheung, Mamoulis and Yiu2004). In this solution, documents are summarized into graph structures, called s-graphs, which contain all edges but only distinct nodes from the original document tree. Next, all s-graphs are encoded as bit vectors, where each position in a vector reflects the presence or absence of a corresponding edge in a given s-graph. As one s-graph may correspond to many documents, each vector is additionally associated with a list of documents corresponding to a given s-graph. Such a structure representing the whole data set is called SG. After constructing the SG, all pairs of s-graphs are compared using a distance measure based on the percentage of common edges between them. The result of such a comparison (e.g. a distance matrix) may be used by any applicable clustering algorithm. However, the authors propose to use the ROCK algorithm (Lian et al., Reference Lian, Cheung, Mamoulis and Yiu2004), owing to the fact that binary values in SG should be considered as categorical rather than numerical. The algorithm starts with each s-graph representing a separate cluster. In each consecutive step, a pair of closest clusters is merged. The closeness of two clusters is calculated based on the number of common neighbors of all s-graphs from these clusters; the neighborhood is defined by a user-specified maximal distance threshold between two s-graphs. Based on these notions, s-graphs are grouped until reaching the desired number of clusters.

An approach similar to S-GRACE was presented by Aïtelhadj et al. (Reference Aïtelhadj, Boughanem, Mezghiche and Souam2012). The authors propose to transform XML documents into tree summaries by merging all repeating elements at each level of a document into a single node. After the initial transformation, the summaries are further processed as sets of full paths and are clustered with an iterative algorithm. The first document forms the first cluster. Afterwards, each new document is either assigned to one of the existing clusters or constitutes a new one if it does not fit to any of the existing clusters. The document fits into a cluster if it achieves a given threshold of similarity with that cluster’s centroid, that is, the most representative document chosen as the one with the highest similarity with all other documents in this cluster. The similarity between two document trees is computed as a weighted sum of similarity between all of their paths starting at the root node. Such a clustering procedure ensures that new documents do not require recalculating the centroids of all clusters.

Another interesting approach was introduced in the XProj framework (Aggarwal et al., Reference Aggarwal, Ta, Wang, Feng and Zaki2007). The authors propose a clustering algorithm that uses frequent substructures (tree edges) as patterns. Initially, the document set is randomly divided into k partitions of equal size. Next, sets of frequent edges (cluster representatives) are mined from these partitions and later used for defining similarity among documents. A distance between a document and a set of representatives is defined as the fraction of edges in the document which also occur in any of the representatives. According to the computed distances, documents are reassigned to clusters with the most similar representatives. In subsequent iterations, the algorithm mines for new frequent edges and repeats the clustering process until it converges or reaches the maximum number of iterations.

Another method which utilizes frequent substructures was proposed by Brzezinski et al. (Reference Brzezinski, Lesniewska, Morzy and Piernik2011). In their algorithm, the authors propose a three-step pattern-based approach. First, the algorithm mines the whole data set for maximal frequent subtrees, which serve as patterns. Later, the patterns are grouped into k clusters using the AHC algorithm, with the number of common documents as a similarity measure. Finally, each document is assigned to its proper cluster based on the number of common patterns. This approach was tested and further generalized into a generic pattern-based framework called XPattern (Piernik et al., Reference Piernik, Brzezinski and Morzy2014). The framework formalizes four main steps of a pattern-based clustering methodology: document transformation, pattern mining, pattern clustering, and document assignment. This approach does not imply any particular representation or pattern definition. However, the authors tested several different pattern representations and the results of the study suggest that frequent paths provide a good balance between information saturation and efficiency.

8.3 Level similarity approaches

Tag-based methods are considered to be the simplest and least accurate algorithms for clustering XML documents by structure. However, Nayak proposed a new tag-based approach, called XCLS, in which the author included additional information about the level of each tag in the document tree (Nayak, Reference Nayak2008). Therefore, the method incorporated more structural information than regular tag-based approaches, yet preserved their simplicity. In this method, each document is represented as a LevelStructure—a vector whose cells correspond to consecutive levels in the document tree. In each cell, there is a vector containing distinct tags, which appear in the document at the corresponding level. The author also proposed a weighted similarity measure which measures the co-occurrences of elements at corresponding levels, where a certain weight is associated with each level. With the given similarity measure, clusters are formed in an iterative manner. Each new XML document is placed in a cluster which contains the most similar documents.

The XCLS algorithm was enhanced by Alishahi et al. (Reference Alishahi, Naghibzadeh and Aski2010), who identified two main problems of the algorithm. The first problem concerns comparing two trees when the root node label of one tree does not appear anywhere in the other tree and vice versa. This always results in a similarity equal 0 even if all other nodes match. The second problem is the lack of information about parent–child connections. Both problems were addressed in an improved version of the XCLS method called XCLS+ (Alishahi et al., Reference Alishahi, Naghibzadeh and Aski2010).

An approach complementary to XCLS and XCLS+ was proposed by Antonellis et al. in an algorithm called XEdge (Antonellis et al. Reference Antonellis, Makris and Tsirakis2008). In XEdge, the authors propose to represent XML documents as LevelEdges, structures similar to the LevelStructure (Nayak, Reference Nayak2008). In contrast to LevelStructures, LevelEdges contain information about edges on each level of an XML document. This way, in addition to containing information about nodes, a LevelEdge encapsulates information about parent–child relationships between them. Such an approach can help to distinguish groups of similar documents not only in heterogeneous, but also homogeneous data sets. To further adapt XEdge to process both homogeneous and heterogeneous data sets, the authors propose two separate similarity measures. To compare documents from homogeneous sources, XEdge uses a measure which calculates a weighted sum of common edges on each level divided by a weighted sum of all unique edges on each level. For the differentiation of heterogeneous documents, the authors propose a measure analogous to that proposed in Nayak (Reference Nayak2008), which tries to match similar levels of two compared documents and calculate a weighted sum of common edges. To cluster a data set of XML documents, XEdge uses a modified version of k-means which utilizes LevelEdge similarity to calculate the distance between two documents. As cluster representatives, the authors propose to use yet another leveled structure, in which each level contains all distinct edges in the corresponding level of all document representations in a given cluster.

In an attempt to minimize the processing time and memory requirements, Hadzic et al. (Reference Hadzic, Hecker and Tagarelli2011) proposed to transform XML documents into a structure called document structure model (DSM). A DSM is a string vector that allows to encode the structure of documents from a given data set in a concise and easily comparable manner. To achieve this, each document in a data set is first pre-order traversed and string encoded using an algorithm proposed by Zaki (Reference Zaki2002). Next, the obtained flat document representations are ‘aligned’ so that a position in the DSM corresponds to exactly the same level and position in each XML document in the data set. The authors positively evaluated the proposed method against a tree-edit distance approach and have shown that almost any similarity measure and clustering approach can be used with the DSM representation.

8.4 Other approaches

A different vector-based approach for clustering XML documents was proposed by Candillier et al. (Reference Candillier, Tellier and Torre2006). The authors suggest to summarize each document with a set of attribute-value pairs. The attributes correspond to distinct features extracted from the documents: parent–child relations, next–sibling relations, paths, tags, and absolute node positions. The value of each attribute is the number of occurrences of the corresponding feature in a given document. After calculating feature vectors for all documents, clustering is performed with a variation of the expectation–maximization algorithm (Moon, Reference Moon1996). As the number of attributes for a data set can grow fairly large, the authors propose to carry out feature selection. To perform this, for each cluster, attributes are weighted by the ratio between local and global standard deviations of attribute values. Afterward, only a user-defined number of highest weighted attributes is kept for further processing.

Hagenbuchner et al. put forward an algorithm called SOM-SD (Hagenbuchner et al., Reference Hagenbuchner, Sperduti, Tsoi, Trentini, Scarselli and Gori2006), which extends Kohonen’s self-organizing map (SOM) (Kohonen, Reference Kohonen1989) and clusters XML documents in an unsupervised fashion. For each document in a data set, SOM-SD processes document tree nodes one at a time and maps them on the SOM neuron grid. A node is represented by a vector containing the node’s label and the neuron grid co-ordinates of that node’s direct offspring. For this reason, SOM-SD processes XML documents from leaf nodes to root nodes. After introducing all the documents to the SOM, similar documents are displayed at the same or close co-ordinates on the neuron grid. Apart from putting forward a clustering algorithm, the authors also propose evaluation measures suitable for documents mapped on the SOM grid. Furthermore, the same paper introduces a more general algorithm called CSOM-SD, which can be used to cluster XML documents with links or represented as graphs, for example, s-graphs (Lian et al., Reference Lian, Cheung, Mamoulis and Yiu2004).

One of the most original approaches to clustering XML by structure was proposed by Flesca et al. (Reference Flesca, Manco, Masciari, Pontieri and Pugliese2005). In their solution, the authors omit not only the values of elements and attributes, but also their labels, leaving only the information about the order and depth of the nodes. Hence, this approach transforms each document into a time series, where a signal in a given moment in time corresponds to the depth of a node appearing at a particular position in the document tree. After the transformation, all documents are compared using DFT. The product of this comparison may be utilized by any applicable clustering algorithm.

Wang et al. put forward a method dedicated for very large XML data sets (Wang et al., Reference Wang, Liu, Lin, Sun and Ahmad2006). The authors propose to transform each document into a set of paths and later encode each path as a single number. A set of such numbers becomes a document representation. A distance measure based on this representation calculates an absolute difference between all values of the compared documents. The documents are clustered with the k-means algorithm, according to the defined distance measure. In order to reduce the probability of the solution falling into a local optimum, the authors propose a modification of the k-means algorithm. After achieving convergence, random objects are relocated between the clusters and centroids are recalculated.

One of the more efficient XML clustering methods is the entropy-based clustering algorithm (Helmer, Reference Helmer2007; Helmer et al., Reference Helmer, Augsten and Böhlen2012). The main idea behind this approach is to compress structural information about documents, compare the lengths of the compressed files, and calculate the NCD between each pair of documents. The calculated distances can be used by any similarity-based clustering algorithm. Moreover, this algorithm can work with any type of document representation. The definition of NCD allows such flexibility, as it is based on an approximation of the Kolmogorov complexity, which can be defined for any data object (Bennett et al., Reference Bennett, Gacs, Li, Vitanyi and Zurek1998). Although the algorithm can use any type of document representation, clustering results will differ depending on the selected representation. For this reason, the author analyzes four methods of extracting structural information—tags, pairs of tags, paths, and whole document trees. Compared with simple tag and edit distance algorithms, the entropy-based approach requires less time and achieves similar or better clustering accuracy, depending on the selected representation and compression algorithm.

Hwang and Ryu (Reference Hwang and Ryu2004, Reference Hwang and Ryu2010) proposed to model XML documents as transactions, where transaction items are frequent paths found in the documents. With such a representation, the authors use a modified version of the CLOPE algorithm (Yang et al., Reference Yang, Guan and You2002). To assign documents to clusters, CLOPE uses the rate of common paths to determine cluster allocation profit. To confirm that the cluster allocation profit ensures high cluster cohesion, the authors propose to weigh frequent structures according to their support and a user-specified value. It is worth noting that this approach does not require pairwise document comparisons and, therefore, can be used for large, schema-less data sets.