The order and arrangement of dimensions (variates) is crucial for the effectiveness of a large number of visualization techniques such as parallel coordinates, scatterplots, recursive pattern, and many others. In this paper, we describe a systematic approach to arrange the dimensions according to their similarity. The basic idea is to rearrange the data dimensions such that dimensions showing a similar behavior are positioned next to each other. For the similarity clustering of dimensions we need to define similarity measures which determine the partial or global similarity of dimensions. We then consider the problem of finding an optimal one-or twodimensional arrangement of the dimensions based on their similarity. Theoretical considerations show that both, the one-and the two-dimensional arrangement problem are surprisingly hard problems, i.e. they are NP-complete. Our solution of the problem is therefore based on heuristic algorithms. An empirical evaluation using a number of different visualization techniques shows the high impact of our similarity clustering of dimensions on the visualization results. Visualization techniques are becoming increasingly important for the analysis and exploration of large multidimensional data sets, which is also called data mining [Kei 97]. A major advantage of visualization techniques over other (semi-)automatic data mining techniques (from statistics, machine learning, artificial intelligence, etc.) is that visualizations allow a direct interaction with the user and provide an immediate feedback as well as user steering, which is difficult to achieve in most non-visual approaches. The practical importance of visual data mining techniques is therefore steadily increasing, and basically all commercial data mining systems try to incorporate visualization techniques of one kind or the other (usually rather simple ones) [KDD]. There are, however, also a number of commercial data mining products which use advanced visualization technology to improve the data mining process. A large number of visualization techniques used in those systems, however, suffer from a well-known problem -the incidental arrangement of the data dimensions 1 in the display. The basic problem is that the data dimensions have to be positioned in some one-or two-dimensional arrangement on the screen, and this is usually done more or less by chance -namely in the order in which the dimensions happen to appear in the database. The arrangement of dimensions, however, has a major impact on the expressiveness of the visualization. The basic idea of our approach for finding an effective order of dimensions is to arrange the dimensions according to their similarity. For this purpose, we first have to define similarity measures which determine the similarity of two dimensions. These similarity measures may be based on a partial or global similarity of the considered dimensions (cf. sections 2). For determining the similarity, a simple Euclidean or more complex (e.g., Fourier-based) distance measures may be used. Based on the similarity measure, we then have to determine the similarity arrangement of dimensions. After formally defining the one-and two-dimensional arrangement problems (cf. subsection 3.1), in subsection 3.2 we show that all variants of the arrangement problem are computationally hard problems which are NP-complete. For solving the problems, we therefore have to use heuristic algorithms (cf. subsection 3.3). Section 4 contains an experimental evaluation of our new idea, showing its impact for the parallel coordinates, circle segments, and recursive pattern technique. The problem of determining the similarity of dimensions (variates) may be characterized as follows: The database containing N objects with d-dimensions can be described as d arrays A i , each containing N real numbers , . We are interested in defining a similarity measure S, which maps two arrays to a real number (S: ). All meaningful similarity measures S must have the following properties: where . 1. In the context of this paper, we use the term data dimension exchangable with the term variates (statistics termiology) and attributes (database termiology).
Aiming at dimension reordering, Ankerst et al. REF presented a method based on similarity clustering of dimensions, placing similar dimensions close to each other.
Similarity clustering of dimensions for an enhanced visualization of multidimensional data
Proceedings IEEE Symposium on Information Visualization (Cat. No.98TB100258)
Proceedings IEEE Symposium on Information Visualization (Cat. No.98TB100258)
Computer Science