Multiclass Visual Classiﬁer Based onBipartite Graph Representation ofDecision Tables⋆
Kazuya Haraguchi1, Seok-Hee Hong2, and Hiroshi Nagamochi3
1 Faculty of Science and Engineering, Ishinomaki Senshu University, Japankazuyah@isenshu-u.ac.jp2 School of Information Technologies, University of Sydney, Australiashhong@it.usyd.edu.au3 Department of Applied Mathematics and Physics,Graduate School of Informatics, Kyoto University, Japannag@amp.i.kyoto-u.ac.jp
Abstract. In this paper, we consider K-class classiﬁcation problem, asigniﬁcant issue in machine learning or artiﬁcial intelligence. In this prob-lem, we are given a training set of samples, where each sample is rep-resented by a nominal-valued vector and is labeled as one of the prede-ﬁned K classes. The problem asks to construct a classiﬁer that predictsthe classes of future samples with high accuracy. For K = 2, we havestudied a new visual classiﬁer named 2-class SE-graph based classiﬁer(2-SEC) in our previous works, which is constructed as follows: We ﬁrstcreate several decision tables from the training set and extract a bipar-tite graph called an SE-graph that represents the relationship betweenthe training set and the decision tables. We draw the SE-graph as a two-layered drawing by using an edge crossing minimization technique, andthe resulting drawing acts as a visual classiﬁer. We can extend 2-SECto K-SEC for K > 2 naturally, but this extension does not considerthe relationship between classes, and thus may perform badly on somedata sets. In this paper, we propose SEC-TREE classiﬁer for K > 2,which decomposes the given K-class problem into subproblems for fewerclasses. Following our philosophy, we employ edge crossing minimizationtechnique for this decomposition. Compared to previous decompositionstrategies, SEC-TREE can extract any tree as the subproblem hierarchy.In computational studies, SEC-TREE outperforms C4.5 and is compet-itive with SVM especially when K is large.
1Introduction
1.1Background
We consider a mathematical learning problem called classiﬁcation, a signiﬁ-cant research issue from classical statistics to modern research ﬁelds on learn-ing theory and data analysis [1]. For positive integers m, m′ (m ≤ m′), let
⋆ This work is partially supported by Grant-in-Aid for Young Scientists (Start-up,20800045) from Japan Society for the Promotion of Science (JSPS).
Table 1. A training set S = S1∪S2 with S1 = {s1, s2, s3, s4} and S2 = {s5, s6, s7} overthree attributes with D1 = {yes, no}, D2 = {high, med}, and D3 = {high, med, low}
Att. 1Att. 2Att. 3
(headache)(temperature)(blood pressure)
S1 (malignant)
yeshighhigh
yesmedmed
yeshighhigh
nohighmed
S2 (benign)
nomedhigh
yeshighmed
nomedlow
[m] = {1, 2, . . ., m} and [m, m′] = {m, m + 1, . . . , m′}. A sample s is representedby an n-dimensional nominal vector for n attributes and belongs to one of thepredeﬁned K classes. We denote the domain of attribute i ∈ [n] by Di, and theset of K classes by C = {c1, . . . , cK}. In classiﬁcation, we are given a training setS = S1 ∪ · · · ∪ SK of available samples, where Sk (k ∈ [K]) is the set of availablesamples belonging to the class ck. Table 1 shows an example of training set forK = 2. A classiﬁer is a function from the sample space S = D1 × · · · × Dn tothe class set C. The aim of classiﬁcation is to construct a classiﬁer that predictsthe class of a future sample s′ ∈ S with high accuracy, where s′ is possibly notin the training set, i.e., s′ ̸∈ S.In our previous research, we have worked on developing a new visual classiﬁerwhich can provide us with insights into data, beyond a mathematical function.Our main idea is to construct a classiﬁer by good visualization of a graph ex-tracted from the abstract data.Visualization plays an important role as an eﬀective analysis tool for hugeand complex data sets in many application domains such as ﬁnancial market,computer networks, biology and sociology [2]. Due to its popular application forvisualization, graph drawing has been extensively studied over the last twentyyears [3]. To draw graphs automatically and nicely, we need to give a mathemat-ical deﬁnition of aesthetic criteria (e.g., the number of edge crossings) for 2D and3D drawings. In our companion papers [4, 5], we proposed a new mathematicalmeasurement of occlusion for 2.5D drawing [6] of pairwise trees, and observedthat, when the samples and the attribute values are represented by pairwisetrees, the minimum occlusion drawing supports visual analyses of classiﬁcationand clustering. Independently, it was shown that algorithms for reducing edgecrossings in graph drawings can be used in such data analyses as rank aggre-gation [7]. Based on these, we hypothesize that good visualization (e.g., visualobjects with low visual complexity) itself can discover essential or hidden struc-ture of data without relying on data analysis techniques, which can lead to anovel learning technique.For 2-class classiﬁcation (i.e., K = 2), we designed a prototype visual clas-siﬁer and demonstrated its eﬀectiveness by empirical studies in our preliminary
Table 2. Decision tables T1 = (A1, ℓ1), T2 = (A2, ℓ2) and T3 = (A3, ℓ3) with attributesets A1 = {1, 2}, A2 = {1, 3} and A3 = {3}
T1 = (A1, ℓ1)T2 = (A2, ℓ2)T3 = (A3, ℓ3)
v ∈ D1 × D2
v ∈ D1 × D3
v ∈ D3
yes, high
yes, high
yes, med
yes, med
no, high
yes, low
no, med
no, high
no, med
no, low
research [8, 9]. Recently, we found that our visual classiﬁer is a visualization of2-class generalized majority vote (2-GMV) of multiple decision tables [10, 11].Table 2 shows three decision tables for the training set in Table 1. Formally, adecision table T = (A, ℓ) is a classiﬁer deﬁned by a subset A = {i1, . . . , iq} ⊆ [n]of n attributes and a label function ℓ : Di1 × · · · × Diq → C. The label ℓ isoften deﬁned by decision table majority [12] in the literature, and in this paper,we do not assume any particular deﬁnition of ℓ. For a future sample s ∈ S, adecision table estimates its class as the label ℓ(v) of the matched entry v = s|A(where s|A denotes the projection of s onto A). For example, (no, high, high)is classiﬁed as c1 by T1, c2 by T2 and c1 by T3. Let T = {T1, . . . , TN} denote aset of N decision tables. One can use T as a single classiﬁer by applying suchensemble technique as majority vote (MV). The MV classiﬁes a future sampleas the majority class among the N outputs given by the N decision tables in T .For example, MV with T = {T1, T2, T3} in Table 2 classiﬁes (no, high, high) asc1. GMV is a generalization of MV, and will be mentioned in Sect. 2.For given S, T and its 2-GMV, our visual classiﬁer in [10, 11] is built on abipartite graph called sample-entry graph (SE-graph). In SE-graph, one nodeset corresponds to the samples in S, the other set corresponds to the entries ofthe decision tables in T , and a sample s and an entry v are joined by an edgeif and only if s matches v. See Fig. 1(a) for an example of SE-graph drawn astwo-layered drawing. The layout of SE-graph is deﬁned by permutations on thesamples and the entries. We ﬁx the permutation of the entry nodes along withthe 2-GMV, and perform edge crossing minimization technique to compute thepermutation on the sample nodes. We then divide the sample nodes into c1 andc2 sides by choosing a suitable threshold θ. (See θ dividing the sample nodes inFig. 1(b).) A future sample s′ will be judged as c1 or c2 by which side it falls on.We call this visual classiﬁer 2-class SE-graph based classiﬁer (2-SEC).
1.2New Contribution
In this paper, we extend 2-SEC to K-SEC for K-class problems (K > 2). Theextension itself is not a hard task due to the following two reasons: One reasonis that 2-GMV, the base classiﬁer of 2-SEC, can be extended to K-GMV for
similarity with c   ≤ 1/2similarity with c   > 1/2
class cclass c
Entries
Samples
Fig. 1. Construction of 2-class SEC: (a) A natural SE-graph (b) The SE-graph obtainedby edge crossing minimization
K-class problems naturally. We can visualize K-GMV as K-SEC, and its de-tails are described in Sect. 2. The other reason is that we already know somegeneral frameworks to extend any 2-class classiﬁer to multiclass one. One mayﬁnd the following three methods in the literature, one-to-all, one-to-one, anderror correcting output codes [13]. These frameworks hardly take into accountthe structural relationships of classes, although it must be smarter to decom-pose the entire problem into subproblems for fewer classes in some applicationdomains.
There are some studies that attempt to extract hierarchical structure ofclasses, which we call a class tree. Most of the previous works concentrate onextracting a binary tree as the class tree to decompose a K-class problem into2-class subproblems (e.g., [14, 15]). In a class tree, there are K leaves, and eachleaf corresponds to one of the K classes. (Figure 2 shows a class tree of Glassdata set from UCI Repository [16].) Each inner node corresponds to a meta-class, representing the set of its descendant classes (i.e., leaves). Let K′ ≤ Kdenote the number of children of an inner node. For this inner node, K′-classclassiﬁer is constructed, where each child constitutes one class. Starting fromthe root, a future sample is passed to one of the K′ children, which is decidedby the K′-class classiﬁer of the current node. This procedure is repeated untilthe sample reaches a leaf. Finally, the sample is classiﬁed into the class of thereached leaf.
Window glassNon-window Glass
Containers(13)Tableware(9)Headlamps(29)
FloatNon-float
Building(70)
Vehicle(17)
Building(76)
Vehicle(0)
Fig. 2. Hierarchical structure of classes in Glass data set: a leaf corresponds to a classand an integer represents the number of samples belonging to each class.
Note that one should extract a nice class tree and decompose the given K-class problem into easier subproblems. In the context of class tree, K-SEC can beregarded as a star (i.e., a tree consists only of the root and the K leaves), whereno decomposition is made, in the sense that K classes are treated homogeneouslyin classiﬁer construction. However, K-SEC does not seem to work well on suchdata sets that have structural relationships between classes. On the other hand,binary tree based approaches do not always work well because binary tree is notthe universal structure of classes.
In this paper, we propose a new multiclass visual classiﬁer, named SEC-TREE, that can extract any tree as a class tree. To extract a class tree, weemploy edge crossing minimization on two-layered drawing of a bipartite graph,following our philosophy described in the previous subsection. We can controlthe structure of the resulting class tree by tuning the newly introduced param-eter. In the extracted class tree, we use K′-SEC as the classiﬁer of an innernode with K′ children. When the number K of classes is large, in the sense ofclassiﬁcation performance (i.e., error rate), SEC-TREE is superior to C4.5 [17],a standard decision tree classiﬁer, and is competitive with well-tuned supportvector machines (SVMs) for multiclass problems.
The paper is organized as follows. In Sect. 2, we introduce K-SEC and review2-SEC as a special case of K-SEC. We describe how to construct SEC-TREE inSect. 3. We present computational results in Sect. 4. Besides comparison of errorrates, we show that our new method can capture a good class tree and discussthe eﬀects of the controlling parameter.
Throughout this paper, we assume that a set T of decision tables is given.We do not focus on how to construct it in this paper. (In the experiments ofSect. 4, we utilize the decision tables generated by Weka [18].) This issue will beaddressed in our future papers.
2SE-graph Based Classiﬁer (SEC)
Assume that a set T = {T1, . . . , TN} of N decision tables is given. We denoteTj = (Aj, ℓj) (j ∈ [N]) and the set of all entries of Tj by Dj, i.e., Dj is theCartesian product of the domains of the attributes in Aj. For K ≥ 2, K-GMVis deﬁned by a tuple (λ1, . . . , λN) of N similarity functions for the N decisiontables. A similarity function λj is such a function λj : Dj × C → [0, 1] thatrepresents “similarity” or “closeness” between each entry v ∈ Dj and class ck ∈C. For any entry v ∈ Dj, we assume �Nk=1 λj(v, ck) = 1. For a future samples ∈ S, K-GMV classiﬁes s into the class ck if barycenter β(s, ck) for ck isthe largest among all K classes c1, . . . , cK, which is deﬁned based on similarityfunctions as follows.
β(s, ck) = 1
j=1λj(s|Aj, ck).(1)
One can readily see that K-MV is a special case of K-GMV as follows; for each(v, ck) ∈ Dj × C, set λj(v, ck) = 1 if ℓj(v) = ck, and λj(v, ck) = 0 otherwise.Let us focus on K = 2. Since λj(v, c1)+λj(v, c2) = 1, it holds that β(s, c1)+β(s, c2) = 1. Whether s is classiﬁed into c1 or c2 is determined by whetherβ(s, c2) ≤ 0.5 or not. However, we do not need to stick to this threshold 0.5, andcan replace it with any threshold θ ∈ [0, 1]. For K = 2, let us deﬁne 2-GMV bya tuple (λ1, . . . , λN, θ).Now we review 2-SEC, which serves as a visualization of 2-GMV [10, 11]. Letus denote the union of all Dj’s by D = D1 ∪ · · · ∪ DN. A sample-entry graph(SE-graph) is a bipartite graph G = (S, D, E), which is deﬁned as follows.
– S and D are node sets in the bipartite graph. Each sample s ∈ S and eachentry v ∈ D are nodes in a topological sense.– For each j ∈ [N], a sample s ∈ S and an entry v ∈ Dj are joined by anedge (s, v) if and only if s matches the entry v. Thus the edge set is givenby E = E1 ∪ E2 ∪ · · · ∪ EN such that Ej = {(s, v) ∈ S × Dj | s|Aj = v}.
We consider the two-layered drawing of SE-graph in a 2D plane, i.e., one layerfor S and the other for D, as shown in Fig. 1. We order the entries from the samedecision table consecutively, and take the permutation of the N decision tablesarbitrarily. We deﬁne a layout of SE-graph by (σ, π1, . . . , πN), where σ : S → [|S|]is an ordering on the samples in S, and πj : Dj → [|Dj|] (j ∈ [N]) is an orderingon the entries in Dj.Let Gj = (S, Dj, Ej) denote the subgraph of G induced by S and Dj. We saythat two edges (s, v), (s′, v′) ∈ Ej cross if and only if (σ(s) > σ(s′) and πj(v) <πj(v′)) or (σ(s) < σ(s′) and πj(v) > πj(v′)). We deﬁne x(G; σ, π1, . . . , πN) asthe sum of the edge crossings over all the N induced subgraphs;
x(G; σ, π1, . . . , πN) =
��{(s, s′) ∈ S × S | σ(s) < σ(s′), πj(s|Aj) > πj(s′|Aj)}��.
From the viewpoint of good visualization, we should determine the lay-out so that x(G; σ, π1, . . . , πN) is minimized. (We do not need to consider thecrossings between edges from diﬀerent Dj’s since its number becomes a con-stant, but the reason is omitted due to space limitation.) We can computethe layout along with a given 2-GMV (λ1, . . . , λN, θ). Consider the one-sidededge crossing minimization problem (1CM) that asks to decide σ that mini-mizes x(G; σ, π1, . . . , πN), where π1, . . . , πN are ﬁxed in the nondecreasing or-der of similarity function values, i.e., by denoting Dj = {v1, v2, . . . , vB} andλj(v1, c2) ≤ λj(v2, c2) ≤ · · · ≤ λj(vB, c2), we assign πj(v1) = 1, πj(v2) = 2, . . . ,πj(vB) = B.Since the 1CM problem is NP-hard [19], we utilize barycenter heuristic [20].This heuristic permutes S in the nondecreasing order of barycenter β(s, c2) forclass c2. Computing its layout by barycenter heuristic, we assert that the SE-graph achieves a good visualization of the 2-GMV in the following sense:
(i) The number of edge crossings is (approximately) minimized. Indeed, barycen-ter heuristic has been recognized as an eﬀective approximation algorithm inpractice (e.g., [21]).(ii) The resulting drawing can enable some meaningful analysis on 2-GMV.For example, the computed string of samples is split into two substringsaccording to whether barycenter is larger than θ or not. The samples in theformer (resp., latter) substring are estimated as c2 (resp., c1) by the 2-GMV.
What we call 2-SEC is the visual classiﬁer consisting of 2-GMV and its SE-graph.For K > 2, a K-GMV (λ1, . . . , λN) is visualized as K-SEC in a similar way.We construct K copies G1, . . . , GK of the SE-graph G = (S, D, E), one for eachclass ck ∈ C. We draw each Gk by two-layered drawing in a 2D plane. The layoutof Gk is computed as follows: The entries v’s from decision table Tj are orderedby λj(v, ck), and the samples s’s are ordered by barycenter heuristic based onβ(s, ck).
3SEC-TREE for Multiclass Classiﬁcation
Let U denote any set of elements and 2U denote its power set. A family U ⊆ 2U
is called laminar if, for any two sets X, Y ∈ U, at least one of the three setsX \ Y , Y \ X, X ∩ Y is empty. It is obvious that a laminar family U can bevisualized by a tree, where a node corresponds to X ∈ U and an edge representsthe inclusion relationship. In the sequel, we may refer to a laminar family U asa tree and an X ∈ U as a node if no confusion arises.To construct a class tree for the given K-class problem, we compute a laminarfamily C ⊆ 2C of subsets of the class set C, and utilize C as the class tree. Weinclude a subset X ⊆ C in C if our criteria say that X should be treated as ameta-class in a 2-class (or at least fewer-class) subproblem. For this, we test ifthe samples of the classes in X and the samples of the classes in ¯X = C \ X canbe separated “eﬀectively” by 2-SEC.
Entries
Classes
v1v1v2v2v3v3v4v4
c1c1c2c2c3c3c4c4c5c5
Fig. 3. Two-sided edge crossing minimization (2CM) on CE-graphs
To test the separability, we introduce class-entry graph (CE-graph), ˆG =(C, D, E), which is obtained from SE-graph G = (S, D, E) by contracting eachSk ⊆ S (k ∈ [K]) into a node ck ∈ C. We deﬁne a layout of CE-graph by(ˆσ, π1, . . . , πN), where ˆσ : C → [|C|] is an ordering on the class set and πj :Dj → [|Dj|] (j ∈ [N]) is an ordering on the entry set Dj. The number of edgecrossings of CE-graph in the layout (ˆσ, π1, . . . , πN) is deﬁned analogously withthe case of SE-graph (see (2)).Recall that 2-SEC is obtained as a result of performing 1CM on SE-graph.We consider two-sided edge crossing minimization (2CM) on CE-graph that asksto compute the layout (ˆσ, π1, . . . , πN) to minimize the edge crossings. See Fig. 3.In this simple example, we assume the number K of classes to be 5 and focuson one decision table with 4 entries. However, the discussion can be generalizedeasily. For convenience, let ˆσ(c1) = 1, . . . ˆσ(cK) = K.In the ﬁgure, we can expect that the samples of the classes in X = {c1, c2}and the samples of the classes in ¯X = {c3, c4, c5} can be separated by an appro-priate construction of 2-SEC. This expectation comes from the observation thatthere are few crossings between edges from X and ¯X, which may suggest theseparability between X and ¯X, and that there are more edge crossings in insideof X, which may suggest that the samples of the classes in X match the similarentries (and thus take close values for barycenter).Now let us formalize our criteria to decide whether X ⊆ C should be includedas a node in the class tree. For k ∈ [K] and t ∈ [K − k] ∪ {0}, let Xk,t ={ck, ck+1, . . . , ck+t} denote a consecutive subset of C. We deﬁne χ(k, t) to bethe number of crossings between edges from Xk,t and ¯Xk,t, and deﬁne η(k, t) asfollows;
η(k, t) =
�0if t = 0,max[k′,t′]⊊[k,t]χ(k,t)
χ(k′,t′)otherwise.(3)
One can see that, if η(k, t) is small, then the crossings between edges from Xk,tand ¯Xk,t are relatively fewer than the edge crossings inside Xk,t.Our algorithm to construct a class tree is described in Algorithm 1. Thesmallness of ηk,t is decided by a positive parameter δ > 0. In line 1, since the2CM problem is NP-hard [22], we employ iterative application of barycenterheuristic in the experiments of Sect. 4, i.e., repeat ﬁxing one side and permutingthe other side by barycenter heuristic until no change is made on both sides. In
line 2, we can compute all η(k, t)’s eﬃciently by dynamic programming. However,the details are omitted due to space limitation.
Algorithm 1 ConstructClassTree
1: Compute the layout (ˆσ, π1, . . . , πN) of CE-graph by 2CM.2: For each k ∈ [K] and t ∈ [K − k] ∪ {0}, compute η(k, t) by (3).3: X ←˘Xk,t ⊆ C | η(k, t) < δ, k ∈ [K], t ∈ [K − k] ∪ {0}¯.We denote X = {Xk1,t1, . . . , Xkb,tb}, where η(ka, ta) ≤ η(ka+1, ta+1) (∀a ∈ [b− 1]).4: C ← ∅.5: for a ← 1, 2, . . . , b do6:if C ∪ {Xka,ta} is laminar then7:C ← C ∪ {Xka,ta}.8:end if9: end for10: Output C.
For leaves of the class tree, the output C always includes singletons X1,0 ={c1}, . . . , XK,0 = {cK} for any δ > 0 since η(k, 0) = 0 < δ by (3). It is possiblethat C contains more than one maximal subset, i.e., more than one class tree. Insuch a case, we have to choose the class tree used for classifying a future sample,but we omit the details due to space limitation. (In our preliminary experiments,we hardly observed such a case.)The parameter δ eventually controls the structure of the output class tree.Intuitively, if δ → 0 (resp., +∞), then less (resp., more) subsets are likely to beincluded in C, and thus the class tree is close to a star (resp., a binary tree). Henceit is expected that a larger δ decomposes the given K-class problem into moresubproblems for fewer classes. We will observe the eﬀects of δ in the experimentsdescribed in Sect. 4.For the computed class tree C, let us mention how K′-SEC is constructed foran inner node X ∈ C (|X| ≥ 2) with K′ children. Let Y1, . . . , YK′ ∈ C denote thechildren of inner node X. For each decision table Tj ∈ T , let mj(v, Yk) denotethe number of the samples matching entry v ∈ Dj whose class is in Yk, and letMj(v) = �K′
k=1 mj(v, Yk). Then we employ the similarity function λj(v, Yk) withthe following deﬁnition;
λj(v, Yk) =
�0if Mj(v) = 0,mj(v,Yk)
Mj(v)otherwise.
When K′ = 2, recall that we are free to choose the threshold θ ∈ [0, 1].Aiming at improving the prediction performance, we set the threshold θ to thevalue that minimizes the error rate on the training set. Further, we employ two-stage 2-SEC as follows; we construct the ﬁrst 2-SEC (λ1, . . . , λN, θ) from thetraining set S, and the second 2-SEC (λ′1, . . . , λ′N, θ′) from the subset S′ ⊆ S,where S′ is the subset of samples falling “near” the threshold θ of the ﬁrst 2-SEC.A future sample is classiﬁed by the second 2-SEC if it falls near θ.
Table 3. Data sets from UCI Repository
DataClasses (K)SamplesTestAttributes(Num) (Nom) → (Binary)
Lenses324(10-CV)04-Iris3150(10-CV)406.7Wine3178(10-CV)1305.8Balance3625(10-CV)4016.0Cmc31473(10-CV)2749.1Car41728(10-CV)06-Nursery512960(10-CV)08-Bridges6105(10-CV)11015.6Dermatology6366(10-CV)13312.1Anneal679810063227.0Sat64435200036050Zoo7101(10-CV)017-Glass7214(10-CV)9014.4Yeast101484(10-CV)8038.5Soybean19307376035-Audiology2420026069-
Finally, SEC-TREE is the visual classiﬁer consisting of the class tree C andthe K′-SEC’s for the inner nodes. Let us emphasize that our class tree is con-structed based on edge crossing minimization on CE-graph.
4Computational Experiments
4.1Experimental Settings
In the experiments, we use 16 data sets from UCI Machine Learning Repository[16]. Table 3 shows the summary of the data sets. We construct a classiﬁer fromthe training set and evaluate it by the error rate on the test set. Anneal, Sat,Soybean and Audiology have their own test sets, and we use them for theevaluation. (For these data sets, the column “Test” shows the number of samplesin the test set.) For the other data sets, we perform 10-fold cross validation [23]to generate training and test sets.The columns “(Num)” and “(Nom)” show the numbers of numerical andnominal attributes, respectively. SEC-TREE is formulated on nominal data sets,and it cannot handle a data set with numerical attributes; we need to transformthe data set into nominal one by an appropriate algorithm. For this, we employthe algorithm proposed in our previous work [24], which extracts a set of binaryattributes from a data set with numerical attributes. An extracted binary at-tribute may take 1 (resp., 0) if some numerical attribute value is (resp., is not)larger than a computed threshold. We extract a set of binary attributes fromthe training set, and then construct SEC-TREE from the binarized training set.The test set is also binarized by the same set of binary attributes, and is used for
classiﬁer tests. The rightmost column “(Binary)” shows the number of extractedbinary attributes, where the fractional number represents its average in 10-foldcross validation. Some data sets contain only nominal attributes (which are in-dicated by hyphen). For such data sets, we can construct SEC-TREE withoutbinarization.Let us describe how to construct a set T = {T1, . . . , TN} of N decision tables.We use N = 10, 20 and 30. We generate the attribute set Aj of each decisiontable Tj = (Aj, ℓj) by DecisionTable package of Weka [18]. This packagegenerates a “good” attribute set by local search. By choosing the initial solutionat random, we can generate diﬀerent attribute sets. See [12, 18] for the details.
4.2Validity of Obtained Class Tree
In this subsection, we illustrate that our new method can ﬁnd a class tree thatis close to the one inherent in Glass data set. In this data set, a sample corre-sponds to a type of glass, the attribute values represent information on chemicalingredients, and the class represents the object where the glass is used. Themanual of the data set says that the 7 classes form a hierarchy, as shown inFig. 2.For simplicity, we concentrate on constructing binary class trees; the param-eter δ is set to +∞ here. We investigate if the constructed class tree has eitherof the two meta-classes, “Window glass” and “Non-window glass.” The class“Vehicle” under “Non-ﬂoat” is ignored, since no sample belongs to the class.For comparison, we introduce two types of binary class trees constructedin diﬀerent ways. One is called equally sized class tree, which is constructedby partitioning the ordered class set (which is obtained by 2CM on CE-graph)recursively so that the diﬀerence in the number of the samples between the twochildren becomes so small as possible. The other is random class tree, which isconstructed by partitioning the ordered class set at random recursively.When N = 10 (resp., 20 and 30), our method ﬁnds either cluster by 66%(resp., 74% and 69%), while the equally sized class tree ﬁnds either one by 44%(resp., 40% and 45%) and the random class tree does by 25% (resp., 26% and26%), which tells that our method succeeds in capturing nontrivial approxima-tion of the true hierarchy.For error rates, we cannot observe signiﬁcant diﬀerence among the three classtrees in our preliminary experiments. However, they are diﬀerent in the depthsof the nodes where misclassiﬁcation occurs. We assert that misclassiﬁcation in ashallow node costs more than one in a deep node because, in the former case, wemay have to improve not only the K′-SEC’s of the misclassifying inner nodes butalso the class tree structure. Figure 4 shows the distribution of the misclassiﬁedsamples for the depth diﬀerence between the misclassifying inner node and theleaf of the true class. In the proposed class tree, misclassiﬁed samples are moredistributed on small diﬀerences than the others. Hence it is expected that SEC-TREE of the proposed class tree can be improved further by detailed tuning onlyon deeper nodes, which is left for future work. We remark that this phenomenon
Proposed class treeEqually sized class treeRandom class tree
Depth difference between
Ratio of samples (%)
the misclassifying node and the true leaf
Fig. 4. Distribution of misclassiﬁed samples in test sets
Training set
∞0123δ∞
Test set
Error rate (%)
AUDIOLOGY
SOYBEAN
Error rate (%)
Fig. 5. Change of error rate along with δ (left: training set, right: test set)
is also observed in the cases of N = 20 and 30, and in most of the other datasets.
4.3Parameter Eﬀects
The parameter δ controls the degree to which the given K-class problem isdecomposed. In Fig. 5, we observe the eﬀects of δ in terms of error rate. The leftﬁgure shows the change of error rate on the training set of Glass, Soybean,and Audiology. We use N = 20 here. As shown, SEC-TREE with a larger δ(where the problem is decomposed into more subproblems for fewer classes) ﬁtsto the training set better than a smaller δ, which may meet one’s intuition. Onthe other hand, the right ﬁgure shows the change of error rate on the test set.When δ becomes large, the error rate for Audiology increases rapidly, whichshows overﬁtting, while the error rates for the other two data sets are improvedby 2 to 3%. How the problem should be decomposed must depend on data sets,and we have to decide the value of δ carefully.
4.4Comparison with Other Classiﬁers
We compare SEC-TREE with other classiﬁers, C4.5 [17], LibSVM [25] andMCSVM [26], in terms of error rate on test sets. All the classiﬁers have sometunable parameters. We try some combinations of parameter values for eachclassiﬁer, and evaluate it by the smallest error rate. For SEC-TREE, we set δ toε, 1.0, 1.1, 1.2, 1.5, 2.0, 3.0 and +∞, where ε is a suﬃciently small positive num-ber. For C4.5, we test 8 combinations of parameter values: we set confidencerate to 1%, 25% (default), 50% or 99%, binary split option to true or false(default), and the other parameters to the default values. For LibSVM, we test16 combinations: we use 2-class C-SVM and RBF kernel, and set C = 0.5, 1.0(default), 2.0 or 4.0, γ = 0.0 (default), 0.5, 1.0 or 2.0, and the other param-eters to the default values. Note that LibSVM employs one-to-one frameworkto extend 2-class C-SVM to multiclass one. Since MCSVM is an extension of2-class C-SVM, LibSVM and MCSVM have similar parameters in common. ForMCSVM, we test the same 16 combinations as LibSVM.We show the results in Table 4. Boldface for each data set shows the smallest(i.e., best) error rate among all classiﬁers. A sign ∗ on SEC-TREE indicatesthat the error rate is smaller than C4.5. The eﬀectiveness of SEC-TREE isoutstanding when K is large; for K ≥ 7, SEC-TREE outperforms C4.5 forall data sets and becomes more competitive with SVMs. In particular, SEC-TREE is much better than the other classiﬁers for Audiology, which has thelargest K among the used data sets. For larger K, we may have to decomposeK-class problem more carefully. The experimental results indicate that SEC-TREE succeeds in extracting class trees which are eﬀective in decreasing errorrates.Let us describe computation time brieﬂy. We evaluate the actual time neededto construct a classiﬁer and to classify a test set. All experiments are conductedby our PC with 2.83GHz CPU. C4.5 takes at most 2 seconds for all data sets.For SVMs and SEC-TREE, we observe Nursery data set as an extreme case,since it has the largest number of samples. The computation time of SVMsheavily depends on parameter values; both LibSVM and MCSVM take from 10to 350 seconds. We observe that the error rates of SVMs are also sensitive toparameter values. It must be exhaustive to search appropriate parameter values.On the other hand, SEC-TREE takes about 21 (resp., 35 and 73) seconds whenN = 10 (resp., 20 and 30) regardless of δ. We note that more than 95% ofthe computation time is devoted to generation of T , for which we use Weka as asubroutine. We expect that the computation time can be improved by developinga faster algorithm to generate T .
5Concluding Remarks
In this paper, we proposed a new multiclass visual classiﬁer SEC-TREE as anextension of our previous 2-class classiﬁer 2-SEC. SEC-TREE can extract anytree as the class tree by tuning the parameter δ. We presented computationalresults to show the eﬀectiveness of the proposed method.
Table 4. Error rates (%) of SEC-TREE, C4.5, LibSVM and MCSVM
DataClasses (K)
SEC-TREEC4.5LibSVMMCSVM
N = 102030
Lenses3
20.3320.0020.1716.6621.660.00Iris3
5.805.805.804.663.994.67Wine3
10.4710.6910.749.089.059.05Balance3
∗13.55 ∗13.23 ∗13.1320.168.639.17Cmc3
∗45.25 ∗45.10 ∗44.9045.4144.0545.43Car4
3.303.353.462.830.341.24Nursery5
0.970.730.730.620.040.03Bridges6
42.7141.0540.4239.0938.1839.27Dermatology6
∗14.33 ∗14.27 ∗14.3214.9912.5312.50Anneal6
7.907.807.906.006.004.00Sat6
∗15.71 ∗15.03 ∗15.0116.7012.1512.40Zoo7
∗0.00 ∗0.00∗0.001.001.000.00Glass7
∗29.47 ∗28.28 ∗27.3732.7225.1725.36Yeast10
∗41.48 ∗40.98 ∗40.6441.9140.2242.50Soybean19
∗10.77∗9.23∗9.7612.767.449.19Audiology24
∗15.00 ∗12.69 ∗11.9215.3834.6123.08
Our main future work is described as follows: (i) We have assumed that a setT of decision tables is given and generated it by Weka in the experiments. Weneed to develop a faster algorithm to generate a better T . (ii) In the experiments,we used a binarization algorithm to deal with a data set with numerical attributessince our formulation is limited to nominal data sets. We should consider anextended formulation that can treat numerical attributes directly. (iii) We alsohave to ﬁnd application areas where our visual classiﬁer is eﬀective for dataanalysis and knowledge discovery.
References
1. Friedman, J.H.:Recent advances in predictive (machine) learning.Journal ofClassiﬁcation 23 (2006) 175–1972. Ware, C.:Information Visualization: Perception for Design. 2nd edn.MorganKaufman (2004)3. Battista, G.D., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithmsfor the Visualization of Graphs. Prentice Hall (1999)4. Haraguchi, K., Hong, S., Nagamochi, H.: Visual analysis of hierarchical data using2.5D drawing with minimum occlusion. poster session at IEEE PaciﬁcVis 2008.5. Haraguchi, K., Hong, S., Nagamochi, H.: Visual analysis of hierarchical data using2.5D drawing with minimum occlusion. Technical Report 2009-010, Departmentof Applied Mathematics and Physics, Graduate School of Informatics, Kyoto Uni-versity, Japan (2009)6. Ware, C.: Designing with a 2 1/2D attitude. Information Design Journal 10(3)(2001) 171–182
7. Dwork, C., Kumar, R., Naor, M., Sivakumar, D.: Rank aggregation methods forthe web. In: WWW10, ACM (2001) 613–6228. Haraguchi, K., Hong, S., Nagamochi, H.: Classiﬁcation by ordering data samples.RIMS Kokyuroku 1644 (2009) 20–34 ISSN 1880-2818.9. Haraguchi, K., Hong, S., Nagamochi, H.: Classiﬁcation via visualization of sample-feature bipartite graphs. Technical Report 2009-011, Department of Applied Math-ematics and Physics, Graduate School of Informatics, Kyoto University, Japan(2009)10. Haraguchi, K., Hong, S., Nagamochi, H.: Visualization can improve multiple deci-sion table classiﬁers. In: Proc. MDAI. (2009) to appear.11. Haraguchi, K., Hong, S., Nagamochi, H.: Bipartite graph representation of multipledecision table classiﬁers. In: Proc. SAGA. Volume 5792 of LNCS., Springer (2009)46–6012. Kohavi, R.:The power of decision tables.In: ECML. Volume 912 of LNAI.,Springer (1995) 174–18913. Dietterich, T.G., Bakiri, G.:Solving multiclass learning problems via error-correcting output codes. Journal of Artiﬁcial Intelligence Research 2 (1995) 263–28614. Kumar, S., Ghosh, J., Crawford, M.M.: Hierarchical fusion of multiple classiﬁersfor hyperspectral data analysis. Pattern Analysis and Applications 5(2) (2002)210–22015. Cheng, L., Zhang, J., Yang, J., Ma, J.: An improved hierarchical multi-class sup-port vector machine with binary tree architecture. Proc. International Conferenceon Internet Computing in Science and Engineering (2008) 106–10916. Asuncion, A., Newman, D.:UCI Machine Learning Repository, Universityof California, Irvine, School of Information and Computer Sciences (2007)http://www.ics.uci.edu/∼mlearn/MLRepository.html.17. Quinlan, J.R.: C4.5: Programs for Machine Learning. Morgan Kaufmann (1993)18. Witten, I.H., Frank, E.:Data Mining: Practical machine learning toolsandtechniques.2ndedn.MorganKaufmann,SanFrancisco(2005)http://www.cs.waikato.ac.nz/ml/weka/.19. Eades, P., Wormald, N.C.: Edge crossings in drawings of bipartite graphs. Algo-rithmica 11 (1994) 379–40320. Sugiyama, K., Tagawa, S., Toda, M.: Methods for visual understanding of hierar-chical system structures. IEEE Transactions on Systems, Man, and CyberneticsSMC-11(2) (1981) 109–12521. J¨unger, M., Mutzel, P.: 2-layer straightline crossing minimization: Performanceof exact and heuristic algorithms. Journal of Graph Algorithms and Applications1(1) (1997) 1–2522. Garey, M.R., Johnson, D.S.: Crossing number is NP-complete. SIAM Journal onAlgebraic and Discrete Methods 4 (1983) 312–31623. Weiss, S.M., Kulikowski, C.A.: Computer Systems that Learn: Classiﬁcation andPrediction Methods from Statistics, Neural Nets, Machine Learning, and ExpertSystems. Morgan Kaufmann (1991)24. Haraguchi, K., Nagamochi, H.: Extension of ICF classiﬁers to real world data sets.In: IEA/AIE. Volume 4570 of LNAI., Springer (2007) 776–78525. Chang, C.C., Lin, C.J.: LIBSVM: a library for support vector machines. (2001)Software available at http://www.csie.ntu.edu.tw/∼cjlin/libsvm.26. Crammer, K., Singer, Y.: On the algorithmic implementation of multiclass kernel-based vector machines. Journal of Machine Learning Research 2 (2001) 265–292