Multidimensional Data Visual Exploration by Interactive Information Segments

Multidimensional Data Visual Exploration by Interactive Information Segments Francisco J. Ferrer-Troyano, Jes´us S. Aguilar-Ruiz, and Jos´e C. Riquelme Department of Computer Science, University of Seville Avenida Reina Mercedes s/n, 41012 Seville, Spain {ferrer,aguilar,riquelme}@lsi.us.es Abstract. Visualization techniques provide an outstanding role in KDD process for data analysis and mining. However, one image does not always convey successfully the inherent information from high dimensionality, very large databases. In this paper we introduce VSIS (Visual Set of Information Segments), an interactive tool to visually explore multidimensional, very large, numerical data. Within the supervised learning, our proposal approaches the problem of classification by searching of meaningful intervals belonging to the most relevant attributes. These intervals are displayed as multi–colored bars in which the degree of impurity with respect to the class membership can be easily perceived. Such bars can be re–explored interactively with new values of user–defined parameters. A case study of applying VSIS to some UCI repository data sets shows the usefulness of our tool in supporting the exploration of multidimensional and very large data. 1 Introduction Visualization techniques provide an important support to extract knowledge from huge amounts of data incorporating ingenuity, analytic capability, and experience of the user in order to steer the KDD process [15]. From graphic representations of a query or data set, the user carries out an interactive visual exploration from which interesting subsets and data relationships can be identified, and new hypotheses and conclusions can be drawn. Such hypotheses can be later verified by data mining techniques. Through a visual exploration, the user can intuitively have a good idea of the result interpretation. Different graphic views of the same data set can give the user a better understanding about it, and an easy way to detect patterns, outliers, and noise. In addition, visualization tools can be also used to reduce the search space and therefore, to obtain simpler models for complex sub–domains. An important concern for multidimensional data visualization techniques is to avoid different entities overlapping on the screen. These individual entities can be data–items or examples, data–values or attribute–values, or data aggregations based on the former ones. If the values are directly displayed, they usually are a significantly small portion of the entire available data. Otherwise, it is likely that the resulting image cannot convey the data properties appropriately and the Y. Kambayashi et al. (Eds.): DaWaK 2004, LNCS 3181, pp. 239–248, 2004. c Springer-Verlag Berlin Heidelberg 2004 240 Francisco J. Ferrer-Troyano, Jes´us S. Aguilar-Ruiz, and Jos´e C. Riquelme Fig. 1. Wave–Form database (40 attributes, 5000 examples, 3 class labels) in Parallel Coordinates. exploration becomes a difficult task. As an example, Figure 1 shows the Wave– form data set displayed using the well–known Parallel Coordinates technique [11]. Because of the high width and depth of this data set, individual examples cannot be clearly seen from this display, also preventing the detection of relevant patterns and attributes. We think it is more interesting to display as few graphic entities as possible in order to represent as large amount of data as possible. The smaller number of graphical entities containing higher number of examples, the easier and more meaningful interpretation of results. In addition, many visualization techniques have restrictions regarding the data size, with respect either to the number of examples or the number of attributes. In this paper we introduce VSIS (Visual Set of Information Segments), an interactive tool to explore multidimensional and very large databases. Handling enormous amount of data might seem risky to graphically represent every different value in only one image, not only because of the screen limitations, but also the human ability to understand a complex image. Therefore, our goal is also to incorporate user’s constraints, so the display can become more significant for the expert. 2 VSIS: Visual Set of Information Segments Within the supervised learning, the problem of classification is generally defined as follows. An input finite data set of training examples is given. Every training example is a pair e=(x, y)wherexis a vector of mattribute values (each of which may be numeric or symbolic) and yis a class discrete value named label. The goal is to obtain a model y=f(x) to classify or decide the label for new non–labelled test examples named queries. VSIS supports the problem of classification with numerical attributes by displaying only the most relevant Multidimensional Data Visual Exploration 241 attributes with only the most meaningful intervals. The set of intervals is as small as possible depending on the user demand. For each interval is displayed the distribution of labels within it and the relationship with other intervals. We name these graphic entities information segments. Henceforth, the next notation is used to describe VSIS. Let mbe the number of continuous attributes (A1,...,Am). Let Y={y1,...,y z}be the set of class labels from one nominal attribute previously selected by the user. Let Tbe the training set so that: T={e1,...,e n};ei=(xi,y i); xi∈R m;yi∈Y;i∈ {1,...,n};m, n ∈N. Definition 1 (Empty Segment) An empty segment Sj,k represents an interval Iof the jth attribute Ajfor which no training example has a value within I: ∀ei∈T ·xij /∈I. Definition 2 (Pure Segment) ApuresegmentSj,k represents an interval I of the jth attribute Ajfor which all the training examples are associated with the same class label: ei,e i∈T ·xij ∈I∧xij∈I∧yi=yi. Definition 3 (Impure Segment) An impure segment Sj,k represents an interval Iof the jth attribute Ajfor which there are training examples associated with different class labels: ∃ei,e i∈T ·xij ∈I∧xij∈I∧yi=yi. Thesegmentsaredisplayedascoloredbars. The color represents the class label and it is previously selected by the user. Empty segments are not displayed, pure segments are displayed with one color and impure segments are displayed with a number of colors. Every color takes up an area inside a rectangle which is proportional to the number of examples with the label associated to such a color in the respective information segment. The process is divided into two steps: first, an initial set of segments is calculated; second, the minimal set of segments meaningful for the user is obtained. Both sets are displayed and can be interactively re–explored. 2.1 ISIS: Initial Sets of Information Segments This first phase builds minitial sets ISISj(j∈{1,...,m}), one per attribute. Each set ISISjis formed by αinformation segments and provide the user with insight about the label distribution of input data. αis a user parameter (integer) which splits the continuous attributes of Tinto αequal–width intervals. The higher value for α, the higher accuracy is obtained. Each information segment Sj,k (k∈{1,...,α}) is composed by three elements: –Ij,k =[lj,k,u j,k) is a left–closed, right–open interval in R, such that uj,k = lj,k+1 (∀k<α). –Hj,k ={Hj,k1,...,H j,kz}is a histogram with the number of examples for each label that are covered by Sj,k.Anexampleeiis covered by a segment Sj,k if the jth attribute value of the example (xij ) belongs to the interval Ij,k. 242 Francisco J. Ferrer-Troyano, Jes´us S. Aguilar-Ruiz, and Jos´e C. Riquelme Fig. 2. Diagram of the data structure used to build the initial sets of information segments (α= 25). –IHj,k is a set of m−1elementsSIHj,k,j, one per each attribute Ajdifferent to Aj.EachelementSIHj,k,jis composed by a set of pairs (k,H∩ k), related to segments for other attributes containing examples covered by Sjk.The element kis the index of a segment Sj,k,andH∩ kis the histogram of class labels for examples in the intersection Hj,k ∩Hj,k. The purpose of this data structure is to compute the minimal set of segments in the next phase. The initial sets of segments are built by one only scan, previously generating αempty segments Sj,k for each attribute with Hj,kp=0(p∈{1,...,z})and IHjk =∅. Then every example ei=(xi,y i) updates the class–labels histogram Hjk of the segment Sjk that covers xi(increasing by one Hjkyi), and the relationships IHjk among such updated segments. The computational cost of the process is not expensive since the index kof the segment Sjk associated to a value xij can be calculated directly: k=norm(xij )·α;norm(xij )= xij −MINj MAXj−MINj;MINj=lj1;MAXj=ujα Figure 2 shows a diagram of the data structure used to build the initial set of information segments, using α= 25 initial intervals and 4 class labels (Y={A, B, C, D}). For each attribute Aj,eachISISjhas 25 equal–width segments. The last segment of the last attribute (Sm,25) is associated to the real interval [0,0.24]. This interval covers 17 examples, 9 of them with label A, 3 with label C, and 5 with label D. These 17 examples are covered by three segments in the attribute 1 (S1,1,S1,8and S1,25). The first segment, S1,1, covers 7 examples (4 with class A, 0 with class B, 1 with class C and 2 with class D), 2 the second and 8 the third one. When all the examples have been processed, all the empty segments are removed. Next, every pair of consecutive segments with equal label distribution is joined ( |Hj,k−1p| z p=1 |Hj,k−1p|=|Hj,kp| z p=1 |Hj,k|,∀p∈{1,...,z}). Given Sj,k−1and Sj,k as consecutive segments, Hj,k−1and IHj,k−1are updated with Hj,k and IHj,k,respectively, and the right segment Sj,k is removed. Finally, when all the attributes have been examined, a ranking of them is obtained as a function of the number of pure segments, the number of impure ones, and the impurity level of them, by means of the next heuristic: Weight(Aj)=n−nsj nsj  k=1 (z max p=1 |Hj,kp|) Multidimensional Data Visual Exploration 243 Fig. 3. Wave–Form database. Initial segments for the three most significant attributes (x7, x15, and x16), using α= 25. There are not empty segments in any attribute. Fig. 4. Wave–Form database. Initial segments using α= 200. There are empty segments in every attribute: x7 (32 segments), x15 (25), and x16 (29). where nis the number of training examples, zis the number of different class labels and nsjis the number of non–empty initial segments in Aj. Figures 3 and 4 show the initial segments obtained from Wave-form data set, for the three most significant attributes according to the above heuristic: x7, x15 and x16. Attributes are graphically shown in order of relevance, from top to bottom. The display shows similarities among attributes -when two or more of them have similar shapes- and their relevance -when the distribution is homogeneous, that is, intervals are impure-. The higher value for α,thegreater number of empty intervals are displayed. That is the reason why in Figure 4 the number of initial segments are not equal to the number of initial intervals. Having a look to the images, we can know the label distribution and the overlap level inside the attributes. It is interesting the correlation between attributes x15 and x16 (two at the bottom of figure on the left). That correlation is stronger when the class orange is present, and we can observe that shapes for class green are different for these two attributes from the middle of the attribute until the right bound. In addition, the initial segments provide the user with an insight about the potential complexity of the Minimal Set of Information Segments. 2.2 MSIS: Minimal Set of Information Segments In the second phase, consecutive segments belonging to the attributes selected in the first phase are joined, trying to take advantage of attributes with least number of segments and smaller intersection among them. The goal now is to find the least number of segments from which to describe the label distribution, transforming thousands of examples with dozens of attributes into several colored segments clearly separated in the image. Definition 4 (Support) The support of a segment Sj,k is the number of examples covered by Sj,k. 244 Francisco J. Ferrer-Troyano, Jes´us S. Aguilar-Ruiz, and Jos´e C. Riquelme Definition 5 (Purity) The purity of a segment Sj,k isthepercentageofexamples covered by Sj,k with a majority label with respect to its support. Definition 6 (Minimal Support γ)The minimal support γis the lowest support that a segment must surpass to belong to the MSIS. Definition 7 (Minimal Purity δ)The minimal purity δis the lowest percentage of examples with a majority label with respect to the number of covered examples that an impure segment must surpass for to it be a part of the MSIS. Therefore, a pure segment Sj,k takes δj,k = 100 whereas an impure segment Sj,ktakes δj,k= 100maxz p=1(|Hj,kp|) z p=1 |Hj,kp|.γand δare two user parameters. The MSIS is built from the ISISjsets by two iterative procedures. For each attribute Aj, the algorithm looks for the two consecutive impure segments in ISISjwhose union is possible and whose resulting support is the highest. Two consecutive impure segments can be joined if the resulting purity is greater than or equal to the minimal purity δ. Next, another iterative procedure adds joined segments from the ISISjsets to MSIS. In each iteration, a new segment is included in the MSIS: the one with the largest number of examples that are not yet covered by another segments already included in the MSIS. Thus, the first segment to be included will be the one with the highest support. The procedure ends when either all the examples have been covered or there is no segment that covers examples uncovered by the MSIS. The number ∆of examples that a segment Sj,k in ISISjcan provide for the MSIS is computed by the intersection among IHj,k and the histograms H∩ k associated with the segments Sj,kalready included in the MSIS, according to the equation 1: ∆=( z  p=1 |Hj,kp|)−|  ∀Sjk∈MSIS (SIHj,k,j,H j,k)|(1) In each new iteration, the number of examples uncovered by non–included segments may change with respect to the earlier iteration, and every segment is re–visited again. If a segment Sj,k ∈ISISjdoes not contain examples uncovered by MSIS, then it is removed from ISISjso that the next iteration will have lower computational cost. When the above procedure ends, the MSIS is displayed. For each attribute with at least one information segment, a horizontal attribute–bar shows its segments in increasing order of values, from left to right. Every attribute–bar is equal in size, both in width and height. To the left of each bar, the name of the associated attribute is displayed, along with the total number of examples covered by the segments belonging to such an attribute, and the total number of exclusive examples that all the segments provide. We allow interactive capability to VSIS tool so that the user can keep on exploring the examples belonging to impure segments (both in ISIS and MSIS) until finding a meaningful visual description, through both Parallel Coordinates technique and new segments over different dimensions with higher purity. Multidimensional Data Visual Exploration 245 10 x16 [0.0, 0.36] Majority label: ORANGE Goodness: 70.48% 505 own examples about 1406 covered: 308 examples for labelBLUE 991 examples for label ORANGE 107 examples for label GREEN 1 conect. in x5 1 conect. in x6 1 conect. in x7 1 conect. in x9 1 conect. in x13 1 conect. in x15 10 75 Fig. 5. Wave–Form data set. To the left, first exploration level using α=25, γ=1000 and δ=70. To the right, second exploration level after selecting one segment from the image to the left, using α=25, γ=10 and δ=75. An example of this capability of VSIS is shown in Figure 5. To the left, we try to get more insight from Figure 3. To select the most significant segments we set γ=1000, so only segments containing at least 1000 examples will be displayed. In addition, as the label distribution provides many impure segments, we will relax the criterion by setting δ=70, so only segments containing at least 70% of examples with the same label must be displayed. Only four attributes were selected by the algorithm (x6, x13, x15 and x16), and one segment for each one. Attribute x7 appeared in Figures 3 and 4, but not in Figure 5, because the new intervals offer fewer intervals with better label distribution. Now we are interested in the last attribute x16 (bottom), so we can click on it and set new values for δand γ. This means we are going to analyze only that segment, and therefore, the examples covered by it (exploration level = 2). The new values for δand γare 75 and 10, respectively. The result is shown on the right, where more segments are displayed due to the reduction of the value of γ(only 10 examples). However, the purity has been increased up to 75. New attributes appear in this image (x4, x5, x6, x9, x10, x11, x13, x15, x17, x18, x19 and x38), and also new segments (some of them were already in the exploration level =1 ), which provide more insight about the data, as this might mean that x6 and x13 are decisive for class green and x15 for class orange. Re–exploring impure segments gives a powerful insight of data, as we can achieve a higher accuracy on a specific domain. In this way VSIS cedes the control to the user in order to find, group and validate decision rules with the detail level needed. When a segment is explored, the new segments represent sub– domains satisfying new user specifications. Each new exploration level gives a new description of one attribute condition in a decision rule, since when we decide to explore a segment, the subset defined by that attribute condition is visualized. The process is completely interactive, reducing the support and increasing the accuracy every time. 3 Displaying Very Large Databases We have selected two databases from the UCI repository [5] to show the usefulness of our tool for visualizing great amount of data: one with large number of 246 Francisco J. Ferrer-Troyano, Jes´us S. Aguilar-Ruiz, and Jos´e C. Riquelme Fig. 6. Covtype database (581012 examples, 54 attributes, and 7 class labels). Initial segments for the best five attributes according to ranking: a01, a12, a14, a36, a37 (α=50). Fig. 7. Covtype database: MSIS using α= 50, γ= 1000 and δ= 70. Fifteen information segments (5 pure segments and 10 impure segments). examples (Covtype) and another one with large number of attributes (Isolet). Figures 6 and 7 show two visualization examples of Covtype database. Such displays represent the manner to explore and detect significant sub–domains and irrelevant attributes, and to validate patterns or rules extracted by learning algorithms. These displays also give a good estimate with respect to accuracy and complexity of the model to be extracted by a learning algorithm. In Isolet database, the high degree of overlapping among different class labels (most of segments are impure with a very low purity) shows the difficulty to obtain both a non–complex and accurate knowledge model for (Figures 8 and 9). To tackle 617 attributes and 26 class labels is computationally expensive for many visualization techniques, however VSIS performance is satisfactory. 4 Related Work In [15], Information Visualization and Visual Data Mining techniques are classified according to three criteria: –Thedatatypetobevisualized:one–dimensional data [19], two–dimensional data [20], multidimensional data [16], text & hypertext [19], hierarchies & graphs [6,4], and algorithms & software [8]. –The data representation: standard 2D/3D displays [20], geometrically transformed displays [1,10,11], icon–based displays [7], dense pixel displays [14], stacked displays [12], and hybrid techniques. –The user interaction way: projection [3], filtering [20], zooming [17], spherical & hyperbolic distortions,andlinking & brushing. According to the data type, our proposal VSIS can visualize multidimensional data sets with numerical attributes. With respect to the second group, VSIS Multidimensional Data Visual Exploration 247 Fig. 8. Isolet database (7797 examples, 617 continuous attributes, and 26 class labels). Initial segments for the best seven attributes using α= 200. Fig. 9. Isolet database: MSIS using α= 200, γ=10andδ= 50. belongs to standard 2D techniques. Regarding the third category, VSIS provides data projections to the user, zooming and filtering to detect and validate relevant and meaningful attributes and subdomains. Dimensionality reduction has been dealt by three major approaches: Principal Component Analysis (PCA) [13], Multidimensional Scaling (MDS) [18], and Kohonen’s Self Organizing Maps (SOM) [9]. Recently, new dimensionality reduction techniques have been proposed to process very large data sets with high dimensionality [2]. VSIS reduces the dimensionality in an interactive manner so as to find meaningful subdomains according to user measures. 5 Conclusions and Future Work VSIS is a visualization tool to explore multidimensional numerical data. Through visual interaction and feedback, the user decides how many examples and what level of purity a segment must fulfil to be considered representative of a significant subdomain. The information segments can be seen as decision rules with a number of disjunctions equals the number of exploration levels, whose support is greater than or equal to the last value of γ, and whose purity is greater than or equal to the last value of δ. This representation helps the user with the identification of the most relevant attributes. Results are very interesting as the tool is very flexible and allows the user to go into the level of exploration needed. We are currently improving VSIS by using dense pixel approach to display segments with variable color intensity degree in such a way the support of the segments can be easily perceived. Several similarity measures are being addressed to re–order segments on the display regarding the number of shared examples, making the graphical information understandability easier.