Connecting Segments for Visual Data Exploration and Interactive Mining of Decision Rules

Connecting Segments for Visual Data Exploration and Interactive Mining of Decision Rules Francisco J. Ferrer–Troyano (Computer Science Dept., Univ. of Seville, Spain [email protected]) Jes´us S. Aguilar–Ruiz (Computer Science Dept., Univ. Pablo de Olavide, Spain [email protected]) Jos´e C. Riquelme (Computer Science Dept., Univ. of Seville, Spain [email protected]) Abstract: Visualization has become an essential support throughout the KDD process in order to extract hidden information from huge amount of data. Visual data exploration techniques provide the user with graphic views or metaphors that represent potential patterns and data relationships. However, an only image does not always convey high–dimensional data properties successfully. From such data sets, visualization techniques have to deal with the curse of dimensionality in a critical way, as the number of examples may be very small with respect to the number of attributes. In this work, we describe a visual exploration technique that automatically extracts relevant attributes and displays their ranges of interest in order to support two data mining tasks: classification and feature selection. Through different metaphors with dynamic properties, the user can re-explore meaningful intervals belonging to the most relevant attributes, building decision rules and increasing the model accuracy interactively. Key Words: Data Mining, Visual Data Exploration, Connecting Segments Category: E.1, E.2, H.4 1 Introduction Visualization techniques provide an important support to extract knowledge from huge amounts of data by incorporating ingenuity, analytic capability, and experience of the user, which makes easier to steer the KDD process. From visual metaphors giving graphic representations of a query or data set, visual data exploration allows the user to achieve an interactive search and identify interesting data relationships, from which new hypotheses and conclusions can be drawn. Such hypotheses can be later verified by learning algorithms. Therefore, visual data exploration ought to facilitate getting an insight into data distribution by means of different detail level views in order to reduce the space complexity and obtain simpler that improve the interpretation of results. Journal of Universal Computer Science, vol. 11, no. 11 (2005), 1835-1848 submitted: 1/9/05, accepted: 1/10/05, appeared: 28/11/05 © J.UCS (a) Parallel Coordinates from the most relevant attributes obtained by VETIS.(b) Connecting segments obtained by VETIS. Figure 1: Wave–form data set (5000 examples, 40 attributes, and 3 class labels). An important issue in multidimensional data visual exploration is to avoid different entities overlapping on the screen. A graphic entity usually represents a data aggregation given in the form of items, examples, or relationships among attribute values. The reason for this is that, 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 does not clearly convey important data properties and the exploration becomes a difficult task. In the case of very–large numerical data sets, the number of different values is higher than the screen resolution, making some visualization approaches have indirectly restricted to data size, with respect either the number of examples or the number of attributes. As an example, Figure 1(a) shows the Wave–form data set, displayed using the well–known Parallel Coordinates method [10]. Because of the high dimensionality of this data set, individual examples cannot be clearly seen from this display, also preventing the detection of relevant patterns and attributes. Since it is not easy to provide clear information about attribute relevance unless the method can automatically extract a relevant subset of them, a more useful approach can be to display as few graphic entities as possible in order to represent as large amount of data as possible. The smaller the number of graphical entities containing higher amount of information, the easier and more meaningful the interpretation of results. Based on this approach, in this paper we describe VETIS (Visual Exploration Through Interactive Segmentation), a visual exploration technique that indirectly approaches two mining task: classification and feature selection. VETIS extracts and segments the most relevant attributes, displaying those intervals meaningful for the user. From a complex data structure that provides additional information about relationships among attributes and examples, the graphical entities displayed by VETIS have been named connecting segments. 1836 Ferrer-Troyano F.J., Aguilar-Ruiz J.S., Riquelme J.C.: Connecting Segments ... A segment represents the class distribution for a group of examples with consecutive values in a dimension. Each segment can be re-displayed both in Parallel Coordinates and as several segments belonging to new dimensions, giving data views in different exploration levels. In addition, connecting segments can be taken as logic conditions to build decision rules from them in parallel. In order to show the usefulness of our proposal, in this paper we include quite a few figures obtained from multidimensional UCI data sets [5] that describe by themselves the interactive support to the two above mentioned mining task, traditionally achieved with batch learning algorithms. This paper is organized as follows. Section 2 outlines the state of the art related with visual data exploration. In Section 3, we describe our approach, putting emphasis on the data structure that supports the method and the algorithm, which is divided in three simple steps. Interactive mining examples with VETIS are shown in Section 4, where graphical outputs are displayed together with realted rules interactively built. Finally, in Section 5, the most important conclusions and future work are summarized. 2 Related Work According to Keim’s taxonomy [12], visual exploration techniques can be classified using three orthogonal criteria: –The data type to be visualized: one–dimensional [15], two–dimensional [16], multidimensional [1, 13], text & hypertext [15], hierarchies & graphs [4, 6], and algorithms & software [8]. –The data representation: standard 2D/3D displays [16], geometrically transformed displays [9, 10], icon–based displays [7], dense pixel displays [13], stacked displays [11], and hybrid techniques. –The user interaction way: dynamic projection [3], interactive filtering [16], zooming [14], distortion,andlinking & brushing. With respect to the data type, VETIS visualizes multidimensional data sets with numerical attributes. Regarding to the second dimension, our proposal belongs to standard 2D techniques. Each graphic entity in VETIS means a meaningful interval belonging to a relevant attribute. These intervals are displayed as multi–colored bars in which the degree of impurity with respect to the class membership can be easily perceived. According to the third category, VETIS displays involve a dynamic projection in which the user can apply zooming and filtering to detect and validate relevant attributes and potential patterns. Dimensionality reduction has been dealt by different visual approaches [2]. VETIS reduces the dimensionality in an interactive manner so as to find meaningful subdomains according to user measures. 1837 Ferrer-Troyano F.J., Aguilar-Ruiz J.S., Riquelme J.C.: Connecting Segments ... 3 Connecting Segments Within the supervised learning, the problem of classification is generally defined as follows. An input finite data set Tof ntraining examples is given. Every training example is a pair e=( −→ x,y), where −→ xis a vector of mattribute–values (each of which may be numeric or symbolic), and y∈Yis a nominal class–value named label. Under the assumption there is an underlying mapping function f so that y=f(−→ x), the goal is to obtain a model of Tthat approximates fas ˆ fin order to classify non–labelled test examples, so that ˆ fmaximizes the prediction accuracy. VETIS approaches the classification of multidimensional data sets with numerical attributes by visual building of decision rules from meaningful intervals belonging to the most relevant attributes. A decision rule is a logic predicate of the form: if antecedent then label. The antecedent is a conjunction of conditions Attribute|=Values, where |= is an operator that states a relationship between a particular attribute Ajand values of its domain D(Aj). In rule learning, an example e=( −→ x,y) is said covered by a rule rif −→ xfulfills or is described by the conditions belonging to the antecedent of r, whatever the label associated with ris. VETIS allows the user to obtain rules associated with several labels, which are interactively formed from intervals belonging to different attributes. For every meaningful interval is displayed the distribution of labels within it and the relationship with other intervals. Thus, the elemental unit of graphic information in VETIS is called connecting segment, described next. Definition 1 (Connecting Segment) A connecting segment Sassociated with an attribute Ajis a data structure consisting of three elements (I,H,IH): –Interval:I=[l, u)is a left–closed, right–open interval in R. –Histogram:H={H1,...,Hz}is a histogram with the number of examples for each label in Y={y1;...;yz}that are covered by I.Anexampleeiis covered by an interval Iassociated with the attribute Ajif the attribute–value (xij)belongs to the interval I. –Overlaps:IH is a set of m-1 elements, one per each attribute Ak=Aj. Each element of this set is composed by a set of pairs (k;Hk), related to segments for other attribute Akcontaining examples covered by I. The element kis the index of a segment Sk,andHkis the histogram of class labels for examples in the intersection I∩I k. The purpose of this structure is to compute the minimal set of segments efficiently from which data label distribution can be clearly visualized. This process is illustrated in Algorithm 1 and divided into three steps: 1838 Ferrer-Troyano F.J., Aguilar-Ruiz J.S., Riquelme J.C.: Connecting Segments ... Algorithm 1 VETIS - computing the minimal set of segments INPUT T: Set of nexamples and matributes; δ, γ: integer OUTPUT MS: Minimal Set of Segments begin Build the initial set of segments IS [Step–1] Join consecutive initial segments JS [Step–2] Build the minimal set of segments MS [Step–3] end 1. First, an initial set of segments is computed (step 1); 2. Second, the segments are analyzed in order to refine them by means of joins that preserve a measure of impurity γ(step 2); 3. Third, the minimal set of segments is generated according to γtogether with a measure of coverage β(step 3). Every set can be displayed in order to get an insight into the potential complexity of the final segments. 3.1 Initializing segments This first phase builds minitial sets ISj, one per attribute Aj.EachsetISj is formed by αjconnecting segments and provide the user with insight about the label distribution of input data. The different values of αare calculated by means of projections, i.e., the number of intervals that contain examples for an only class label. Every two adjacent intervals have different class. At least, there will be zinitial segments per attribute, where zis the number of different labels (Y={y1,...,y z}). This situation is ideal, and it happens when it is possible to obtain zsegments, each one of them containing all the examples of that class. In the worst case, there will be as much segments as n, with nbeing the number of examples. In that case, each segment contains only one example. The initial sets of segments are built by one only scan, previously generating αempty segments for each attribute with Hp=0(p∈{1; ...;z})andIHk= 0. Then every example ei=(xi;yi) updates the class labels histogram of the segment Sthat covers xi(increasing by one the Hpassociated with the label yi), and the relationships IHkamong such updated segments. The complexity of this step is mainly determined by the sort algorithm and the method to generate the cutpoints. The latter one takes linear time, therefore the overall complexity is Θ(m2lg(m)). The simplest way to obtain the cutpoints consists in fixing a new interval every time a change of label is found. Consecutive values associated with the same label will compose a common segment whereas a value for which there are several examples of different labels will most likely generate a segment where I=l=u. 1839 Ferrer-Troyano F.J., Aguilar-Ruiz J.S., Riquelme J.C.: Connecting Segments ... Algorithm 2 VETIS - Step–1 INPUT T: Set of nexamples and matributes OUTPUT IS: Initial Set of Segments begin for all attribute Ajin Tdo Sort attribute values for all change of label in Ajdo Set a new interval Calculate histograms for each class and each segment end The fist step of the overall process is shown in Algorithm 2, whose purpose is to initialize the data structure that supports the final display. The additional cost required to compute the relationships among segments is not expensive since the index kof a segment Sassociated with the attribute–value xij can be calculated directly with the following expression: k=norm(xij)×α;norm(xij)= xij −MINj MAXj−MINj (1) where MINjand MAXjare the lower and upper bounds of the attribute range D(Aj), and αjis the number of segments for attribute Aj. Furthermore, VETIS can incrementally reduce the number of segments by joining consecutive segments with equal distribution. Let Saand Sbbe two consecutive segments with associated histograms Haand Hb, respectively. They are grouped if: |H a p| support(Sa)=|H b p| support(Sb);∀p∈{1,...,z} Alternatively, initial segments can be computed using the same α–value in all the attributes (Figure 2). By this option, αequal–width empty intervals are generated for every attribute so that histograms are incrementally completed according to Equation 1. In addition, segments can be displayed in the form of both regular bar charts and equal–width bar charts (Figure 3). As pointed out in [13], the advantage of equal–height bar charts is a better use of the available screen space, but this comes at the disadvantage that the presented items are harder to compare. Although VETIS displays seem very similar to Keim & Hao’s Hierarchical Pixel Bar Charts [13], our approach does not belong to pixel–based techniques since the main goal is not to represent input data directly. Contrary, VETIS is based on data aggregation in order to provide interactive rule mining from different graphic entities. VETIS provides displays of the eight options in order to get an insight into the potential complexity of the final minimal set (see Figures 2 and 3). 1840 Ferrer-Troyano F.J., Aguilar-Ruiz J.S., Riquelme J.C.: Connecting Segments ... (a) Different α–value option (α7= 652, α12 = 516, and α17 = 531). (b) Equal α–value option (α=100). Figure 2: Wave–form data set. Initial segments in three attributes (x7, x15, and x16) displayed as equal–width bars. (a) Attribute x5. Fixed α–value equal to 200 (181 segments). (b) Attribute x10. Dynamic α–value (532 segments). Figure 3: Wave–form data set: initial segments in attributes x5 and x10 displayed separately as regular bars. 3.2 Joining segments In the second phase, previous initial segments are refined in order to obtain m smaller sets JSj, one per each initial set ISj(j∈{1,...,m}). The new segments are obtained by union of consecutive initial segments from a measure of impurity biassing in favour of the attributes with least number of segments and smaller intersection among them. Some definitions related to this step are provided next. Definition 2 (Pure Segment) A pure segment Srepresents an interval Iof the jth attribute Ajfor which all the examples are associated with the same class label: ei,e i∈T ·xij ∈I∧xij∈I∧yi=yi 1841 Ferrer-Troyano F.J., Aguilar-Ruiz J.S., Riquelme J.C.: Connecting Segments ... Algorithm 3 VETIS - Step–2 INPUT IS: Set of Initial Segments; δ, γ: integer OUTPUT JS: Set of Joint Segments begin for all attribute Ajdo repeat Sbest ←∅ for all pair of consecutive impure segments (Sa,Sb)∈ISjdo S←S a∪S b if purity(S)≥δand support(S)>support(Sbest)then Sbest ←S  if Sbest =∅then Replace Saand Sbwith Sbest until Sbest =∅ for all segment Sjin ISjdo if support(Sj)≥γand purity(Sj)≥δthen JSj←JSj∪{S j} end Definition 3 (Impure Segment) An impure segment Srepresents an interval Iof the jth attribute Ajfor which there are examples associated with different class labels: ∃ei,e i∈T ·xij ∈I∧xij∈I∧yi=yi Definition 4 (Support) The support of a segment Sis the number of examples covered by S: support(S)= z  p=1 |H p| Definition 5 (Purity) The purity of a segment Sis the percentage of examples covered by Swith a majority label with respect to its coverage: purity(S)= z max p=1 |H p| support(S) Definition 6 (Minimum Support δ)The minimum support δis the lowest support that a segment must surpass to belong to the Minimal Set of Connecting Segments (MS). Definition 7 (Minimum Purity γ)The minimal purity γis the lowest percentage of examples with a majority label with respect to the number of examples covered by an impure segment in order to belong to MS. 1842 Ferrer-Troyano F.J., Aguilar-Ruiz J.S., Riquelme J.C.: Connecting Segments ... (a) Joint segments in regular bars using β= 100 and γ=0.5. (b) Joint segments in grey scale using β= 1 and γ=0.4. Figure 4: Wave–form data set. Joint segments in x7, x15, and x16. The JS sets are built by an iterative procedure (see Alg. 3). For each attribute Aj,VETIS searches the ISjfor consecutive impure segments whose 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 minimum purity γ. The user can set both parameters δand γinitially. The parameter δcontrols indirectly the size of the segment (number of examples included in the segment). The parameter γdeals with the distribution of classes within segments. By default, δis set to 1, because user can be interested in any valid segment, and γto 95% as pure segments are preferred. If the parameters δ and γexceed the coverage and purity values, respectively, for a specific segment that has been recently joined, then both segments can be definitely joined. 3.3 Building the minimal set In the last phase, the goal is to find the least number of segments from which to visualize the label distribution, transforming thousands of examples with dozens of attributes into few intervals that can be clearly separated in the display. An iterative procedure adds joined segments from the JS to the MS (see Alg. 4). In each iteration, only a new segment is included in the MS: the one with the largest number of examples that are not yet covered by other segments already included in the MS set. 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 non–covered by the MS set. The number of new examples Δassociated with an attribute Ajthat a segment Sj∈JSjcan provide for the MS set is computed by the intersection among IHjand all the histograms Hassociated with the segments Salready included in the MS set. Smay not be necessarily associated with Aj. 1843 Ferrer-Troyano F.J., Aguilar-Ruiz J.S., Riquelme J.C.: Connecting Segments ...