Dimensionality Reduction for Interactive Visual Clustering: A Comparative Analysis

Introduction

The interactive clustering methods allow a user to partition a dataset into clusters that are appropriate for their tasks and interests. Even though a large number of clustering algorithms (Jain, Murty & Flynn, 1999) have been developed, only a small number of cluster visualization tools (Cook, et. al, 1995) are available to facilitate users understanding of the clustering results. Visualization techniques could enhance the current knowledge and data discovery methods by increasing the user involvement in the interactive process. The existing visual approaches use the result of clustering algorithm as the input for visualization system. Current visual cluster analysis tools can be improved by allowing users to incorporate their domain knowledge into visual displays that are well coordinated with the clustering result view (Tory & Moller, 2004; Hinnerburg, Keim & Wawryniuk, 1999).

Existing tools for cluster analysis (Jain, Murty & Flynn, 1999) are already used for multidimensional data in many research areas including financial, economical, sociological, and biological analyses. One of the troubles with cluster analysis is that evaluating how interesting a clustering result is to researchers is subjective, application-dependent, and even difficult to measure. This problem generally gets worse when dimensionality and number of items grows.

All feature selection algorithms broadly fall into two categories: (i) the filter approach and (ii) the wrapper approach (Dy & Broadly, 2000). The filter approach basically pre-selects the dimensions and then applies the selected feature subset to the clustering algorithm. The wrapper approach incorporates the clustering algorithm in the feature search and selection. There has been a wide variety of feature selection procedures proposed in recent years (Dy & Broadly, 2004; Pierre, 2004).

VISTA, an interactive visual cluster rendering system, is known to be an effective model, which invites human into the clustering process (Chen & Liu, 2004). When the dimensionality of the dataset increases, identification of the dominating dimensions for visual tuning and visual distance computation process becomes tedious. One common approach to solve this problem is dimensionality reduction. This study compares the performance of three proposed feature selection methods for interactive visual clustering system. The first method called Entropy Weighting Feature Selection (EWFS) is a wrapper approach in which the relevant dimensions are obtained by identifying the weight entropy of dimensions during the automatic clustering process, for instance K-Means (Alagambigai, Thangavel & Karthikeyani Vishalakshi, 2009).

The second method namely Outlier Score based Feature Selection (OSFS) is a filter method which is independent of clustering algorithm (Alagambigai & Thangavel, 2009). In this approach, the relevant features are identified by exploring individual features of the given dataset in boxplot model. The features that have maximum outlier score are considered as irrelevant features and they are eliminated. The identified relevant features are then used in the visual cluster rendering system. The third method, Contribution to the Entropy based Feature Selection (CEFS) works with “filter” approach (Thangavel, Alagambigai & Devakumari, 2009). In this approach, the relevant features are identified for visual tuning according to its contribution to the entropy (CE) which is calculated on a leave-one-out basis. The experiments are carried out for various datasets of UCI machine learning data repository in order to achieve the efficiency of the feature selection methods.

The rest of the paper is organized as follows. In section 2, the background and related works are described. The issues and challenges are discussed in section 3. The proposed work is discussed in section 4. The experimental analysis is explored in section 5. Section 6 concludes the paper with direction for future research work.