Multi-View Meets Average Linkage: Exploring the Role of Metadata in Document Clustering

Multi-View Meets Average Linkage: Exploring the Role of Metadata in Document Clustering

Divya Teja Ravoori (Department of Computer Science, University of Nebraska at Omaha, Omaha, NE, USA) and Zhengxin Chen (Department of Computer Science, University of Nebraska at Omaha, Omaha, NE, USA)
Copyright: © 2015 |Pages: 17
DOI: 10.4018/IJIRR.2015040102
OnDemand PDF Download:
$37.50

Abstract

Inspired by the success of a recently developed algorithm MVSC-IR, the authors embed the idea of Multi-Viewpoint Based Similarity Measure for clustering (MVSC) into a hierarchical clustering method, i.e., average linkage clustering, to overcome the problem of initiation with random seeds, resulting in a new algorithm, referred to as MVSC-HAC. The improved performance of this new algorithm encouraged us to further explore the impact of metadata in document clustering. In this paper, after reviewing two existing algorithms, the authors describe their new algorithm and present experimental results on various sizes of data sets at two different levels: the one using the entire context of documents and the one using existing meta tags of the documents. The result shows MVSC-HAC excels at both levels. The authors analyze the results, and provide a discussion based on other observation on the role of metadata in document clustering.
Article Preview

1. Introduction

As a popular data mining technique, clustering is the process of finding intrinsic structures among large quantities of unordered data and organizing them into meaningful subgroups that can be used for further study and analysis. Cluster analysis can thus provide significant insight for the important knowledge hidden in the data. In particular, document clustering provides an effective means for revealing hidden knowledge behind the words. In fact, document clustering is even more critical than data clustering, because grouping similar documents together opens the door for the potential realization of “letting documents talk to each other,” so that it we may have an opportunity to integrate semantic information contained in the documents in the same cluster. Due to their relative efficiency, methods using partitioning approach have received a lot of attention. For example, a resent research (known as MVSC-IR) using Multi-Viewpoint Based Similarity Measure for clustering (MVSC) has shown promising results for clustering quality over the conventional single viewpoint (which makes use of centroids). Nevertheless, as a partitioning method, it suffers from the problem of randomly selected seeds to start with. Yet, we have observed that the merit of MVSC is not necessarily restricted to partitioning methods. In this paper, we propose a new algorithm which embeds MVSC to a hierarchical clustering method, the average linkage clustering, to overcome the problem of initiation with random seeds. The new algorithm is referred to as MVSC-HAC (for Hierarchical Agglomerative Clustering). Experiments have shown improved results when compared with other two algorithms in terms of various measures specifically, F-score, Accuracy and NMI (see Experiment section for a brief review of these measures). In addition to presenting a new algorithm, we also want to explore the power of using metadata alone. Although earlier research has suggested the potential of using metadata for ontology development, comparative studies in our experiments have shown the significant differences between using meta-tags alone in the documents versus using the entire documents. We provide an analysis based on our experiments and offer suggestions for exploring ontologies and document clustering and related studies. A little more explanation follows.

There have been many clustering algorithms published every year and are developed using totally different approaches and techniques. These cluster algorithms are sensitive to various parameters like initialization of clusters, number of clusters expected, threshold value, similarity measure used. Basically, there is an implicit assumption that the true intrinsic structure of data could be correctly described by the similarity formula defined and embedded in the clustering criterion function (Nguyen et al., 2012).

The similarity measure used to form clusters can be defined in many ways. Euclidean distance is one of the most popular similarity measures that uses sum of the squared error. Cosine similarity is used instead of Euclidean distance for sparse and high dimensional data like text documents, which is in fact more suitable. Similarity of an object w.r.to a cluster can be considered from two different perspectives (Nguyen et al, 2012). The popular approach is using centroid of the cluster, which may be referred to as the single viewpoint. As one of the top 10 data mining algorithms (Wu et al., 2007), the well-known k-means algorithm follows single view point based similarity. In particular, cosine similarity (CS) is used directly to calculate the distance between document and cluster centroid. In contrast, the multi-viewpoint based similarity (MVS) (Nguyen et al., 2012) uses different viewpoints, which are concerned with objects assumed to not be in the same cluster with the two objects being measured. When we look a pair of points from different viewpoints which are objects outside the cluster, we can have more accurate assessment of how close or distant pair of points are. MVSC-IR algorithm uses multi view point based similarity.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 7: 4 Issues (2017)
Volume 6: 4 Issues (2016)
Volume 5: 4 Issues (2015)
Volume 4: 4 Issues (2014)
Volume 3: 4 Issues (2013)
Volume 2: 4 Issues (2012)
Volume 1: 4 Issues (2011)
View Complete Journal Contents Listing