Information on the hierarchical nature of XML data is essential in tasks of learning from XML document structures. Within this view, XML documents can be regarded as multi-represented data, which is the case when multiple representations of the document correspond to the generation of features at each structure level of the document separately. This chapter raises the importance of using fuzzy approaches to clustering XML document structures, since these approaches are shown to be effective in combining the information coming from different document representations that correspond to different hierarchy levels. For this purpose, we overview fuzzy encoding and similarity methods and present fuzzy clustering approaches which are particularly suited for being extended to handle XML document structures. We propose two different scenarios of fuzzy clustering of XML structures, which aim to either encode the document structure hierarchy using a fuzzy bag model or to specifically handle the multi-representation of the documents.
TopIntroduction
XML documents are complex data objects having hierarchical structure. Therefore, it is not possible to apply conventional similarity measures directly to the analysis of XML document structures. One approach to address this issue is to analyse the structural similarity of XML documents by means of dedicated (tree-based) similarity measures (Nayak, 2008; Dalamagas, Cheng, Winkel, & Sellis, 2004; Nierman & Jagadish, 2002). Another approach consists in encoding the XML structure predominantly into the form of a feature vector and then analysing these feature vectors by means of a conventional similarity measure. This approach includes such encoding methods as bit encoding (Lian, Cheung, Mamoulis, & Yiu, 2004; Yoon, Raghavan, Chakilam, & Kerschberg, 2001), signal encoding (Flesca, Manco, Masciari, & Pugliese, 2005), and fuzzy encoding (Ceravolo, Nocerino, & Viviani, 2004). Some of the encoding methods here mentioned will be described in detail in this chapter. Moreover, since the focus of this chapter is not to review existing clustering approaches and methods for XML clustering (the interested reader can refer to Chapter “The Role of Schema and Document Matchings in XML Source Clustering” and Chapter “XML Document Clustering: An Algorithmic Perspective ”), we make just a mention here of some of those methods by distinguishing them from a clustering strategy viewpoint. In this respect, existing XML clustering methods have been developed based on the following main approaches: agglomerative hierarchical (Nayak, 2008; Nayak & Tran, 2007; Dalamagas, Cheng, Winkel, & Sellis, 2006; Nayak & Iryadi, 2006; Costa, Manco, Ortale, & Tagarelli, 2004; Nierman & Jagadish, 2002), frequent-itemset-based hierarchical (Tagarelli & Greco, 2010), partitional (Tagarelli & Greco, 2010, 2006; Antonellis, Makris, & Tsirakis, 2008; Wang, Liu, & Wang, 2005), tree-partitioning (Bordawekar & Shmueli, 2004), and self-organizing maps (Hagenbuchner, Sperduti, Tsoi, Trentini, Scarselli, & Gori, 2006), and fuzzy (Kozielski, 2007).
XML documents can be regarded as multi-represented data because each document can have several representations when we consider features at each structure level separately. To cluster multi-represented data, information having different representations may be combined at the level of similarity matrices by means of some arithmetic operations or fuzzy aggregation operations. The resulting partition (clustering solution) can also be determined as a particular combination of the partitions derived for each representation separately.
Essentially, multi-represented data clustering consists in combining different types of information during the clustering process. One algorithm of this type is the density-based method DBSCAN that was modified in order to handle the multi-represented nature of the data (Kailing, Kriegel, Pryakhin, & Schubert, 2004). Union and intersection operations were introduced into the algorithm in order to verify if the chosen data objects are dense in any or all the representations that are analysed. This method was also used in the OPTICS algorithm (Achtert, Kriegel, Pryakhin, & Schubert, 2005), which is based on the DBSCAN algorithm but is less sensitive to the values of the parameters required by the method.