XML Document Clustering: An Algorithmic Perspective

Introduction

The wide acceptance of the Web as a means of information and data exchange combined with the growth of native XML databases has designated the problem of efficient data mining techniques on semistructured data. Traditional approaches have proven inefficient as they are mainly oriented to well- structured data, like relational databases, while Web data and XML databases are based on semistructured formats.

Clustering (Jain & Dubes, 1988) is a major exploratory task in data mining which uses an unsupervised learning approach to divide a set of items into subsets (called clusters) so that items in the same cluster are similar in some sense. As an advanced statistical data analysis approach, clustering has been widely adopted in several applications and research contexts, including machine learning, pattern recognition, image analysis and bioinformatics. An important step in every clustering approach is to define a notion of proximity between the items to be clustered. Proximity functions include both distance and similarity measures, such as the well-known Euclidean distance and Manhattan distance (typically used in geometrical data spaces), the cosine similarity (particularly suitable for clustering high dimensional data, including text data), and the Hamming distance, which measures the minimum number of substitutions required to change one item into another (see Chapter “XML Similarity Detection and Measures”).

The Jardine and van Rijsbergen cluster hypothesis (1971) states that documents that are clustered together have a similar relevance to a given query. If the cluster hypothesis holds, and if a suitable clustering can be achieved, then a clustering solution will minimise the number of clusters that need to be searched to satisfy any given query. If only a small fraction of clusters (hence documents) need to be searched for, then the throughput of an information retrieval system will be greatly improved. Documents belonging to the same cluster will likely refer to same topic or contain similar text information. Although there exist various measures for computing the proximity between a pair of documents, such measures are always defined on the text content within each document. Most existing document clustering approaches rely on the Vector Space Model (VSM) representation, and hence use an appropriate similarity measure between the vectorial representations of the documents (for example, the cosine similarity).

With the rapid growth of the size of XML information exchanged, data management and processing issues, such as storage, mining and retrieval of large collections of XML documents have also arisen. Clustering of XML documents improves the process of management and retrieval as it organizes the massive amounts of XML documents into groups without prior knowledge. This grouping may boost the process of querying by applying the user queries only to related groups of XML documents.

Unlike the clustering of text documents, XML document clustering is an intricate process which introduces some new challenges. The new challenges can be summarized as follows:

• •

  XML documents contain structural features (that is, element tags/attributes and their nesting therein) as well as their text data (content features). Regarding the application domain, either the structural features or the content features may be important. However, there are cases in which both the structure and the contents should be considered during clustering in order to achieve meaningful results. Traditional clustering algorithms are tuned for clustering text documents, thus they cannot be straightforwardly generalized in order to capture structural features as well.

• •

  The structural features of a set of XML documents usually have high dimensionality, due to different tags and nesting relationships. In such cases, techniques for reducing the number of dimensions should be used in order to efficiently cluster the corresponding XML documents.

• •

  Most clustering algorithms rely on the idea of “cluster representative”, which represents all the objects belonging to the underlying cluster. The objects are checked against the cluster representatives in order to be assigned to the most appropriate cluster. Defining a cluster representative of a set of XML documents, which should summarize all the structural or/and content features of the corresponding XML documents, is not obvious.

• •

  Due to the wide variety and heterogeneity of data sources used to generate XML information, each data source may utilize different structures and contents. Markup tags, which play a basic role to impose the structure of a document, reflect subjective factors that brand the authorship in coding information. As a consequence, differently annotated XML data may be “semantically related” at a certain degree.