# An Optimal Classification Method for Biological and Medical Data

Authors: Yao-Huei Huang; Yu-Chien Ko; Hao-Chun Lu
Journal: Mathematical Problems in Engineering
 (2012)

---

## Abstract

This paper proposes a union of hyperspheres by the mixed-integer nonlinear program to classify biological and medical datasets. A classifying program with nonlinear terms uses piecewise linearization technique to obtain a global optimum. The numerical examples illustrate that the proposed method can obtain the global optimum more effectively than current methods.


---

## Body

## 1. Introduction

Classification techniques have been widely applied in the biological and medical research domains [1–5]. Either objects classification or patterns recognition for biological and medical datasets necessarily demands an optimum accuracy for saving patients’ lives. However, cancer identification with the supervised learning technique does not take a global view in identifying species or predicting survivals. The improvement should cover the whole scope to give implications instead of only considering the efficiency for diagnosis. This research aims to extract features from whole datasets in terms of induction rules.In the given dataset with several objects, in which each object has some attributes and belongs to a specific class, classification techniques are used to find a rule of attributes that appropriately describes the features of a specified class. The techniques have been studied over the last four decades, including decision tree-based methods [6–11], hyperplane-based methods [12–14], and machine learning-based methods [14–17].To assess the effects of these classifying techniques, three criteria are used for evaluating the quality of inducing rules based on the study of Li and Chen [3].(i)
Accuracy. The rule fitting a class should not cover the objects of other classes. The accuracy of a rule should be the higher the better.(ii)
Support. A good rule of fitting a class should be supported by most of the objects of the same class.(iii)
Compact. A good rule should be expressed in a compact way. That is, the fewer the number of rules, the better the rules are.This study proposes a novel method to induce rules with high rates of accuracy, support, and compactness based on global optimization techniques, which have become more and more useful in biological and medical researches.The rest of this paper is organized as follows. Section2 gives an overview of the related literatures. Two types of mathematical models and a classification algorithm are proposed in Section 3. The numerical examples demonstrate the effectiveness of the proposed method in Section 4. Finally, the main conclusions of this study and future work are drawn in Section 5.


## 2. Literature Review

Currently, two well-known methods are used to induce classification rules. The first method is the decision tree-based method, which has been developed in the last few decades [6–10]. It is widely applied to fault isolation of an induction motor [18] to classify normal or tumor tissues [19], skeletal maturity assessment [20], proteomic mass spectra classification [21], and other cases [22, 23]. Although the decision tree-based method assumes that all classes can be separated by linear operations, the inducing rules will suffer if the boundaries between the classes are nonlinear. In fact, the linearity assumption prohibits practical applications because many biological and medical datasets have complicated nonlinear interactions between attributes and predicted classes.Consider the classification problem with two attributes as shown in Figure1, where “○” represents a first-class object, and “●” represents a second-class object. Figure 1 depicts a situation in which a nonlinear relationship exists between the objects of two classes. Decision tree method focuses on inducing classification rules for the objects, as shown in Figure 1(b), in which the decision tree method requires four rectangular regions to classify the objects.Classifying the objects of two classes.
(a)
Nonlinear dataset(b)
Classify by decision tree methodThe second is the support vector hyperplane method, which conducts feature selection and rule extraction from the gene expression data of cancer tissue [24]; it is also applied in other applications [12–14, 25]. The technique separates observations of different classes by multiple hyperplanes. As the number of decision variables is required to express the relationship between each training datum and hyperplane, and the separating hyperplane is assumed a nonlinear programming problem, the training speed becomes slow for a large number of training data. Additionally, similar hypersphere support vector methods have been developed by Lin et al. [26], Wang et al. [27], Gu and Wu [28], and Hifi and M’Hallah [29] for classifying objects. In classification algorithms, they partition the sample space using the sphere-structured support vector machine [14, 30]. However, these methods need to form a classification problem as a nonlinear nonconvex program, which makes reaching an optimal solution difficult. Taking Figure 1 as an example, a hyperplane-based method requires four hyperplanes to discriminate the objects, as shown in Figure 2.Figure 2
Classify by hyperplane method method.As previously mentioned, many biological and medical datasets have complicated boundaries between attributes and classes. Both decision tree-based methods and hyperplane-based methods find only the rules with high accuracy, which either cover only a narrow part of the objects or require numerous attributes to explain a classification rule. Although these methods are computationally effective for deducing the classifications rules, they have two limitations as follows.(i)
Decision tree-based methods are heuristic approaches that can only induce feasible rules. Moreover, decision tree-based methods split the data into hyperrectangular regions using a single variable, which may generate a large number of branches (i.e., low rates of compactness).(ii)
Hyperplane-based methods use numerous hyperplanes to separate objects of different classes and divide the objects in a dataset into indistinct groups. The method may generate a large number of hyperplanes and associated rules with low rates of compactness.Therefore, this study proposes a novel hypersphere method to induce classification rules based on a piecewise linearization technique. The technique reformulates the original hypersphere model by a piecewise linearization approach using a number of binary variables and constraints in the number of piecewise line segments. As the number of break points used in the linearization process increases, the error in linear approximation decreases, and an approximately global optimal solution of the hypersphere model can be obtained. That is, the proposed method is an optimization approach that can find the optimal rules with a high rate of accuracy, support, and compactness. The concept of the hypersphere method is depicted in Figure3, in which only one circle is required to classify the objects. All objects of class “●” are covered by a circle, and those not covered by this circle belong to class “○.”Figure 3
Classify by hypersphere.


## 3. The Proposed Models and Algorithm

As the classification rules directly affect the rates of accuracy, support, and compactness, we formulate two models to determine the highest accuracy rate and support rate, respectively. To facilitate the discussion, the related notations are introduced first:ai,j:
j′th attribute value of the i′th object,ht,k,j:
j′th center value of the k′th hypersphere for class t,rt,k:
radius of thek′th hypersphere for class t,n(t):
number of objects for classt,ci:
i′th object belonging to class ci∈{1,2,…,g},m:
number of attributes,Rt:
a rule describing classt.Based on these notations, we propose two types of classification models as follow.


### 3.1. Two Types of Classification Models

Considering the objectxi and hypersphere St,k, and normalizing ai,j (i.e., to express its scale easily), we then have the following three notations.Notation 1.
Normalization rescales allai,j as ai,j′. The following is a normalizing formula:
(3.1)ai,j′=ai,j-a̲ja̅j-a̲j,
where 0≤ai,j′≤1, a̅j is the largest value of attribute j, and a̲j is the smallest value of attribute j.Notation 2.
A general form for expressing an objectxi is written as
(3.2)xi=(ai,1′,ai,2′,…,ai,m′;ci),
where ci is the class index of object xi.Notation 3.
A general form for expressing a hypersphereSt,k is written as
(3.3)St,k=(ht,k,1,ht,k,2,…,ht,k,m;rt,k),
where St,k is the k’th hypersphere for class t.
We use two and three dimensions (i.e., two attributes and three attributes) as visualizations to depict clearly a circle and a sphere, respectively (Figure4). Figure 4(a) denotes the centroid of the circle as (ht,k,1,ht,k,2) and the radius of the circle as rt,k. They are extended to three dimensions called sphere (Figure 4(b)); in m dimensions (i.e., m attributes), m>3, which are then called hyperspheres.
To find each center and the radius of the hypersphere, the following two nonlinear models are considered. The first model looks for a support rate as high as possible while the accuracy rate is fixed to 1, as shown in Model1.The concept of hypersphere method.
(a)
Two dimensions(b)
Three dimensionsModel 1.
One has the following:(3.4)Maximize∑i∈I+ut,i,ksubjectto∑j=1m(ai,j′-ht,k,j)2≤(1-ut,i,k)M+rt,k2,∀i∈I+,∑j=1m(ai′,j′-ht,k,j)2>rt,k2,∀i′∈I-,ut,i,k∈{0,1}∀i∈I+,rt,k≥0,andMis big enough constant,
where I+ and I- are the two sets for all objects expressed, respectively, by
(3.5)I+={i∣i=1,2,…,n,whereobjecti∈classt},(3.6)I-={i′∣i′=1,2,…,n,whereobjecti′∉classt}.
Referring to Li and Chen [3], the rates of accuracy and support of Rt in Model 1 can be specified by the following definitions.Definition 3.1.
The accuracy rate of a ruleRt for Model 1 is AR(Rt)=1.Definition 3.2.
The support rate of a ruleRt for Model 1 is specified as follows.(i)
If∑k∈Kut,i,k≥1 for all i belonging to class t, then Ut,i=1; otherwise Ut,i=0, where K indicates the hypersphere set for class t.(ii)
(3.7)SR(Rt)=∑i∈classtUt,in(t),
where n(t) indicates the number of objects belonging to class t.
The second model looks for an accuracy rate as high as possible while the support rate is fixed to 1, as shown in Model2.Model 2.
One has the following:(3.8)Maximize∑i′∈I-vt,i′,ksubjectto∑j=1m(ai,j′-ht,k,j)2≤rt,k2,∀i∈I+,∑j=1m(ai′,j′-ht,k,j)2>(vt,i′,k-1)M+rt,k2,∀i′∈I-,vt,i′,k∈{0,1},∀i′∈I-,rt,k≥0,
where I+ and I- are the two sets expressed by (3.5) and (3.6), respectively.
Similarly, the rates of accuracy and support ofRt in Model 2 can be considered as follows.Definition 3.3.
The accuracy rate of a ruleRt of Model 2 is denoted as AR(Rt) and is specified as follows.(i)
If∑k∈Kvt,i′,k=0 belongs to class t, then Vt,i′=1 for all i′; otherwise, Vt,i′=0, where K represents the hypersphere set for class t.(ii)
(3.9)AR(Rt)=‖Rt‖-∑i′∈classtVt,i′‖Rt‖,
where ∥Rt∥ represents the number of total objects covered by Rt.Definition 3.4.
The support rate of a ruleRt of Model 2 is denoted as SR(Rt), and SR(Rt)=1.Definition 3.5.
The compactness rate of a set of rulesR1,…,Rg, denoted as CR(R1,…,Rg), is expressed as follows:
(3.10)CR(R1,…,Rg)=g∑t=1gUSt,
where USt means the number of hyperspheres and unions of hyperspheres for class t.A union of hyperspheres indicates that the object is covered by different hyperspheres, as shown in Figure 5. Take Figure 5 for an example, in which there are two classes. The objects of class “○” are covered by two unions of the circles (i.e., S1,1∪S1,2∪S1,3 and S1,4∪S1,5), and the objects of class “●” are covered by one circle (i.e., S2,1). Therefore, US1=2, US2=1, and CR(R1,R2)=2/3.
Moreover, Models1 and 2 are separable nonlinear programs solvable to find an optimal solution by linearizing the quadratic terms ht,k,j2. The piecewise linearization technique is discussed as follows.Figure 5
Classify by hypersphere method.Proposition 3.6 (referring to Beale and Forrest [31]).
Denote approximate functionL(f(x)) as a piecewise linear function (i.e., linear convex combination) of  f(x), where  bl,  l=1,2,…,q represents the break points of  L(f(x)).  L(f(x)) is expressed as follows:
(3.11)f(x)≅L(f(x))=∑l=1qf(bl)wl,(3.12)x=∑l=1qwlbl,(3.13)∑l=1qwl=1,
where  wl≥0, and  (3.13) is a special-ordered set of type 2 (SOS2) constraint  (reference to Beale and Forrest [31]).
Note that the SOS2 constraint is a set of variables in which at most two variables may be nonzero. If two variables are nonzero, they must be adjacent in the set.Notation 4.
According to Proposition3.6, let f(x)=ht,k,j2. f(x) is linearized by the Proposition 3.6 and is expressed as L(ht,k,j2).


### 3.2. Solution Algorithm

A proposed algorithm is also presented to seek the highest accuracy rate or the highest support rate, as described as follows.Algorithm 3.7.
Step 1.
Normalize all attributes (i.e., rescaleai,j′=(ai,j-a̲j)/(a̅j-a̲j) to be 0≤ai,j′≤1).Step 2.
Initialization:t=1 and k=1.Step 3.
Solve Model1 (or Model 2) to obtain the k′th hypersphere of class t. Remove the objects covered by St,k from the dataset temporarily.Step 4.
Letk=k+1, and resolve Model 1 (or Model 2) until all objects in class t are assigned to the hyperspheres of same class.Step 5.
Letk= 1 and t= t+ 1, and reiterate Step 3 until all classes are processed.Step 6.
Check the independent hyperspheres and unions of hyperspheresSt,k in the same class t.Step 7.
Calculate and record the number of independent hyperspheres and unions of hyperspheres inUSt, and iterate t until all classes are done.According to this algorithm, we can obtain the optimal rules to classify objects most efficiently. The process of the algorithm is depicted in Figure 6.Figure 6
Flowchart of the proposed algorithm.


### 3.3. Operation of a Simple Example

Consider a datasetT in Table 1 as an example, which has object i, two attributes (ai,1,ai,2), and an index of classes (ci) for i=1,2,…,15. The dataset T is expressed as T={xi∣(ai,1,ai,2;ci)∀i=1,2,…,15}. There are the domain values of ci∈{1,2,3}. As there are only two attributes, these 15 objects can be plotted on a two-dimensional space after normalizing them, as shown in Figure 7(a).Table 1
Dataset of Example 1.
Objectai,1ai,2ciObjectai,1ai,2ciObjectai,1ai,2cix1681x212201x31381x41812.51x524191x62414.51x717.517.52x822172x922152x1030112x1133.57.52x1224.53.53x1326.583x1423.57.53x156303(Symbols ofci) 1: ○ 2: △ 3: ×.Visualization of Example 1.
(a)
Normalized data for Example 1(b)
Classified by the hypersphere method for Example 1This example can be solved by the proposed algorithm as follows.Step 1.
Normalize all attributes (i.e.,ai,1′=(ai,1-6)/(33.5-6) and ai,2′=(ai,2-3.5)/(30-3.5)).Step 2.
Initialization:t= 1 and k= 1.Step 3.
The classification model (i.e., Model1) is linearly formulated as follows:
(3.14)Maximize∑i∈I+ut,i,ksubject to∑j=1m(ai,j′2-2ai,j′ht,k,j+L(ht,k,j2))≤(1-ut,i,k)M+rt,k2,∀i∈I+,∑j=1m(ai′,j′2-2ai′,j′ht,k,j+L(ht,k,j2))>rt,k2,∀i′∈I-,ut,i,k∈{0,1},rt,k2≥0,where I+={x1,x2,…,x6} and I-={x7,x8,…,x15}. The optimal solution of the (ht,k,1,ht,k,2,rt,1)= (0.047,0.265,0.15749) for S1,1, where S1,1 covers objects 1–4. We then temporarily remove these objects covered by S1,1.Step 4.
k=k+ 1: the optimal solution of the (ht,k,1,ht,k,2,rt,k) = (0.736,0.5,0.0138) for S1,2, where S1,2 covers objects 5-6. Class 1 is then done.Step 5.
Ast=t+1,k=1, and Steps 3 and 4 are iterated, we then, respectively, have optimal solutions for St,k as follows. The results are shown in Figure 7(b).(i)
(h2,1,1,h2,1,2,r2,1)=(0.514,0.469,0.0127), where S2,1 covers objects 7–9.(ii)
(h2,2,1,h2,2,2,r2,2)=(0.929,0.210,0.0251), where S2,2 covers objects 10-11.(iii)
(h3,1,1,h3,1,2,r3,1)=(0.583,0.188,0.0436), where S3,1 covers objects 12–14.Step 6.
Check and calculate the unions of hypersphereSt,k for all k in class t (i.e., Initial t=1).Step 7.
Ast=t+1, mark the number of unions of class t into USt and iterate Step 6 until t=g.


## 3.1. Two Types of Classification Models

Considering the objectxi and hypersphere St,k, and normalizing ai,j (i.e., to express its scale easily), we then have the following three notations.Notation 1.
Normalization rescales allai,j as ai,j′. The following is a normalizing formula:
(3.1)ai,j′=ai,j-a̲ja̅j-a̲j,
where 0≤ai,j′≤1, a̅j is the largest value of attribute j, and a̲j is the smallest value of attribute j.Notation 2.
A general form for expressing an objectxi is written as
(3.2)xi=(ai,1′,ai,2′,…,ai,m′;ci),
where ci is the class index of object xi.Notation 3.
A general form for expressing a hypersphereSt,k is written as
(3.3)St,k=(ht,k,1,ht,k,2,…,ht,k,m;rt,k),
where St,k is the k’th hypersphere for class t.
We use two and three dimensions (i.e., two attributes and three attributes) as visualizations to depict clearly a circle and a sphere, respectively (Figure4). Figure 4(a) denotes the centroid of the circle as (ht,k,1,ht,k,2) and the radius of the circle as rt,k. They are extended to three dimensions called sphere (Figure 4(b)); in m dimensions (i.e., m attributes), m>3, which are then called hyperspheres.
To find each center and the radius of the hypersphere, the following two nonlinear models are considered. The first model looks for a support rate as high as possible while the accuracy rate is fixed to 1, as shown in Model1.The concept of hypersphere method.
(a)
Two dimensions(b)
Three dimensionsModel 1.
One has the following:(3.4)Maximize∑i∈I+ut,i,ksubjectto∑j=1m(ai,j′-ht,k,j)2≤(1-ut,i,k)M+rt,k2,∀i∈I+,∑j=1m(ai′,j′-ht,k,j)2>rt,k2,∀i′∈I-,ut,i,k∈{0,1}∀i∈I+,rt,k≥0,andMis big enough constant,
where I+ and I- are the two sets for all objects expressed, respectively, by
(3.5)I+={i∣i=1,2,…,n,whereobjecti∈classt},(3.6)I-={i′∣i′=1,2,…,n,whereobjecti′∉classt}.
Referring to Li and Chen [3], the rates of accuracy and support of Rt in Model 1 can be specified by the following definitions.Definition 3.1.
The accuracy rate of a ruleRt for Model 1 is AR(Rt)=1.Definition 3.2.
The support rate of a ruleRt for Model 1 is specified as follows.(i)
If∑k∈Kut,i,k≥1 for all i belonging to class t, then Ut,i=1; otherwise Ut,i=0, where K indicates the hypersphere set for class t.(ii)
(3.7)SR(Rt)=∑i∈classtUt,in(t),
where n(t) indicates the number of objects belonging to class t.
The second model looks for an accuracy rate as high as possible while the support rate is fixed to 1, as shown in Model2.Model 2.
One has the following:(3.8)Maximize∑i′∈I-vt,i′,ksubjectto∑j=1m(ai,j′-ht,k,j)2≤rt,k2,∀i∈I+,∑j=1m(ai′,j′-ht,k,j)2>(vt,i′,k-1)M+rt,k2,∀i′∈I-,vt,i′,k∈{0,1},∀i′∈I-,rt,k≥0,
where I+ and I- are the two sets expressed by (3.5) and (3.6), respectively.
Similarly, the rates of accuracy and support ofRt in Model 2 can be considered as follows.Definition 3.3.
The accuracy rate of a ruleRt of Model 2 is denoted as AR(Rt) and is specified as follows.(i)
If∑k∈Kvt,i′,k=0 belongs to class t, then Vt,i′=1 for all i′; otherwise, Vt,i′=0, where K represents the hypersphere set for class t.(ii)
(3.9)AR(Rt)=‖Rt‖-∑i′∈classtVt,i′‖Rt‖,
where ∥Rt∥ represents the number of total objects covered by Rt.Definition 3.4.
The support rate of a ruleRt of Model 2 is denoted as SR(Rt), and SR(Rt)=1.Definition 3.5.
The compactness rate of a set of rulesR1,…,Rg, denoted as CR(R1,…,Rg), is expressed as follows:
(3.10)CR(R1,…,Rg)=g∑t=1gUSt,
where USt means the number of hyperspheres and unions of hyperspheres for class t.A union of hyperspheres indicates that the object is covered by different hyperspheres, as shown in Figure 5. Take Figure 5 for an example, in which there are two classes. The objects of class “○” are covered by two unions of the circles (i.e., S1,1∪S1,2∪S1,3 and S1,4∪S1,5), and the objects of class “●” are covered by one circle (i.e., S2,1). Therefore, US1=2, US2=1, and CR(R1,R2)=2/3.
Moreover, Models1 and 2 are separable nonlinear programs solvable to find an optimal solution by linearizing the quadratic terms ht,k,j2. The piecewise linearization technique is discussed as follows.Figure 5
Classify by hypersphere method.Proposition 3.6 (referring to Beale and Forrest [31]).
Denote approximate functionL(f(x)) as a piecewise linear function (i.e., linear convex combination) of  f(x), where  bl,  l=1,2,…,q represents the break points of  L(f(x)).  L(f(x)) is expressed as follows:
(3.11)f(x)≅L(f(x))=∑l=1qf(bl)wl,(3.12)x=∑l=1qwlbl,(3.13)∑l=1qwl=1,
where  wl≥0, and  (3.13) is a special-ordered set of type 2 (SOS2) constraint  (reference to Beale and Forrest [31]).
Note that the SOS2 constraint is a set of variables in which at most two variables may be nonzero. If two variables are nonzero, they must be adjacent in the set.Notation 4.
According to Proposition3.6, let f(x)=ht,k,j2. f(x) is linearized by the Proposition 3.6 and is expressed as L(ht,k,j2).


## 3.2. Solution Algorithm

A proposed algorithm is also presented to seek the highest accuracy rate or the highest support rate, as described as follows.Algorithm 3.7.
Step 1.
Normalize all attributes (i.e., rescaleai,j′=(ai,j-a̲j)/(a̅j-a̲j) to be 0≤ai,j′≤1).Step 2.
Initialization:t=1 and k=1.Step 3.
Solve Model1 (or Model 2) to obtain the k′th hypersphere of class t. Remove the objects covered by St,k from the dataset temporarily.Step 4.
Letk=k+1, and resolve Model 1 (or Model 2) until all objects in class t are assigned to the hyperspheres of same class.Step 5.
Letk= 1 and t= t+ 1, and reiterate Step 3 until all classes are processed.Step 6.
Check the independent hyperspheres and unions of hyperspheresSt,k in the same class t.Step 7.
Calculate and record the number of independent hyperspheres and unions of hyperspheres inUSt, and iterate t until all classes are done.According to this algorithm, we can obtain the optimal rules to classify objects most efficiently. The process of the algorithm is depicted in Figure 6.Figure 6
Flowchart of the proposed algorithm.


## 3.3. Operation of a Simple Example

Consider a datasetT in Table 1 as an example, which has object i, two attributes (ai,1,ai,2), and an index of classes (ci) for i=1,2,…,15. The dataset T is expressed as T={xi∣(ai,1,ai,2;ci)∀i=1,2,…,15}. There are the domain values of ci∈{1,2,3}. As there are only two attributes, these 15 objects can be plotted on a two-dimensional space after normalizing them, as shown in Figure 7(a).Table 1
Dataset of Example 1.
Objectai,1ai,2ciObjectai,1ai,2ciObjectai,1ai,2cix1681x212201x31381x41812.51x524191x62414.51x717.517.52x822172x922152x1030112x1133.57.52x1224.53.53x1326.583x1423.57.53x156303(Symbols ofci) 1: ○ 2: △ 3: ×.Visualization of Example 1.
(a)
Normalized data for Example 1(b)
Classified by the hypersphere method for Example 1This example can be solved by the proposed algorithm as follows.Step 1.
Normalize all attributes (i.e.,ai,1′=(ai,1-6)/(33.5-6) and ai,2′=(ai,2-3.5)/(30-3.5)).Step 2.
Initialization:t= 1 and k= 1.Step 3.
The classification model (i.e., Model1) is linearly formulated as follows:
(3.14)Maximize∑i∈I+ut,i,ksubject to∑j=1m(ai,j′2-2ai,j′ht,k,j+L(ht,k,j2))≤(1-ut,i,k)M+rt,k2,∀i∈I+,∑j=1m(ai′,j′2-2ai′,j′ht,k,j+L(ht,k,j2))>rt,k2,∀i′∈I-,ut,i,k∈{0,1},rt,k2≥0,where I+={x1,x2,…,x6} and I-={x7,x8,…,x15}. The optimal solution of the (ht,k,1,ht,k,2,rt,1)= (0.047,0.265,0.15749) for S1,1, where S1,1 covers objects 1–4. We then temporarily remove these objects covered by S1,1.Step 4.
k=k+ 1: the optimal solution of the (ht,k,1,ht,k,2,rt,k) = (0.736,0.5,0.0138) for S1,2, where S1,2 covers objects 5-6. Class 1 is then done.Step 5.
Ast=t+1,k=1, and Steps 3 and 4 are iterated, we then, respectively, have optimal solutions for St,k as follows. The results are shown in Figure 7(b).(i)
(h2,1,1,h2,1,2,r2,1)=(0.514,0.469,0.0127), where S2,1 covers objects 7–9.(ii)
(h2,2,1,h2,2,2,r2,2)=(0.929,0.210,0.0251), where S2,2 covers objects 10-11.(iii)
(h3,1,1,h3,1,2,r3,1)=(0.583,0.188,0.0436), where S3,1 covers objects 12–14.Step 6.
Check and calculate the unions of hypersphereSt,k for all k in class t (i.e., Initial t=1).Step 7.
Ast=t+1, mark the number of unions of class t into USt and iterate Step 6 until t=g.


## 4. Numerical Examples

This study shows how the experimental results evaluate the performance, including accuracy, support, and compactness rates, and compares the proposed model with different methods using CPLEX [32]. All tests were run on a PC equipped with an Intel Pentium D 2.8 GHz CPU and 2 GMB RAM. Three datasets were tested in our experiments as follows:(i)
Iris Flower dataset introduced by Sir Ronald Aylmer Fisher (1936),(ii)
European barn swallow (Hirundo rustica) dataset obtained by trapping individual swallows in Stirlingshire, Scotland, between May and July 1997 [1, 3],(iii)
the highly selective vagotomy (HSV) patient dataset of F. Raszeja Memorial Hospital in Poland [3, 33, 34].


### 4.1. Iris Flower Dataset

The Iris Flower dataset contains 150 objects. Each object is described by four attributes (i.e., sepal length, sepal width, petal length, and petal width) and is classified by one of three classes (i.e., setosa, versicolor, and virginica). By solving the proposed method, we induced six hyperspheres (i.e.,S1,1∈Class1, S2,1,S2,2,S2,3∈Class2, and S3,1,S3,2∈Class3). The induced classification rules are reported in Table 2. Table 2 also lists a hypersphere and two unions (i.e., S1,1, S2,1∪S2,2∪S2,3, and S3,1∪S3,2) of hyperspheres with centroid points and radii.Table 2
Centroid points for the Iris data set by the proposed method.
Rule numberUnion of spheresSt,kht,k,1ht,k,2ht,k,3ht,k,4rt,kR1S1,1S1,10.3660.8070.0000.0000.6205R2S2,1∪S2,2∪S2,3S2,10.5570.3200.2050.4600.2540S2,20.5750.5810.6260.5150.0612S2,30.4230.2610.3520.4900.1388R3S3,1∪S3,2S3,10.2480.0002.2262.1514.8087S3,20.3290.1870.6500.6130.0330RuleR1 in Table 2 contains a hypersphere S1,1, which implies that(i)
“if(ai,1′-0.366)2+(ai,2′-0.807)2+(ai,3′-0)2+(ai,4′-0)2≤0.6205, then object xi belongs to class 1.”RuleR2 in Table 2 contains a union of three hyperspheres (i.e., S2,1∪S2,2∪S2,3) which implies that(i)
“if(ai,1′-0.557)2+(ai,2′-0.32)2+(ai,3′-0.205)2+(ai,4′-0.46)2≤0.254, then object xi belongs to class 2,” or(ii)
“if(ai,1′-0.575)2+(ai,2′-0.581)2+(ai,3′-0.626)2+(ai,4′-0.515)2≤0.0612, then object xi belongs to class 2,” or(iii)
“if(ai,1′-0.423)2+(ai,2′-0.261)2+(ai,3′-0.352)2+(ai,4′-0.49)2≤0.1388, then object xi belongs to class 2.”RuleR3 in Table 2 contains a union of two hyperspheres (i.e., S3,1∪S3,2), which implies that(i)
“if(ai,1′-0.248)2+(ai,2′-0)2+(ai,3′-2.226)2+(ai,4′-2.151)2≤4.8087, then object xi belongs to class 3,” or(ii)
“if(ai,1′-0.329)2+(ai,2′-0.187)2+(ai,3′-0.65)2+(ai,4′-0.613)2≤0.033, then object xi belongs to class 3.”Comparing the proposed method with both decision tree [3] and hyperplane methods [35] in deducing the classification rules for the Iris Flower dataset, Table 3 lists the experimental result.Table 3
Comparing results for the Iris flower data set (R1,R2,R3).
ItemsProposed methodDecision treeHyperplane support vectorAR(R1,R2,R3)(1,1,1)(1,0.98,0.98)(1,0.98,0.96)SR(R1,R2,R3)(1,0.98,0.98)(1,0.98,0.98)(1,0.96,0.98)CR10.50.1875The accuracy rates of (R1,R2,R3) in the proposed method are (1,1,1), as Model 1 has been solved. This finding indicates that none of objects in class 2 or class 3 are covered by S1,1, none of objects in classes 1 or 3 are covered by S2,1∪S2,2∪S2,3, and none of the objects in classes 1 or 2 are covered by S3,1∪S3,2. The support rate of (R1,R2,R3) in the proposed method is (1,0.98,0.98), indicating that all objects in class 1 are covered by S1,1, 98% of the objects in class 2 are covered by S2,1, S2,2, and S2,3, and 98% of the objects in class 3 are covered by S3,1 and S3,2. The compactness rate of rules R1, R2, and R3 is computed as CR(R1,R2,R3)=3/3=1. Finally, we determine the following.(i)
Although all three methods perform very well in the rates of accuracy and support, the proposed method has the best performance for the accuracy of classes 2 and 3 (i.e.,R2 and R3).(ii)
The proposed method has the best compactness rate.


### 4.2. Swallow Dataset

The European barn swallow (Hirundo rustica) dataset was obtained by trapping individual swallows in Stirlingshire, Scotland, between May and July 1997. This dataset contains 69 swallows. Each object is described by eight attributes, and it belongs to one of two classes (i.e., the birds are classified by the gender of individual birds).Here, we also used Model1 to induce the classification rules. Table 4 lists the optimal solutions (i.e., centroid and radius) for both rules R1 and R2.Table 4
Centroid points for the Swallow data set by the proposed method.
Rule numberUnion of spheresSt,kht,k,1ht,k,2ht,k,3ht,k,4ht,k,5ht,k,6ht,k,7ht,k,8rt,kR1S1,1∪S1,2∪S1,3∪S1,4S1,10.6070.1100.8060.0000.0000.4061.0771.1631.780S1,20.4830.0000.2360.3280.0000.7930.2800.9310.948S1,30.5880.0001.1790.0000.0000.6531.0370.9821.879S1,40.4140.0000.6580.0000.2270.0850.5631.2241.197R2S2,1∪S2,2∪S2,3∪S2,4∪S2,5S2,10.3580.6670.3711.4030.3601.5300.6340.1142.825S2,20.1981.1020.6970.0000.0001.7340.1100.5952.632S2,30.5320.4220.3231.6761.0090.0000.1800.0202.458S2,40.5280.0000.4300.8760.5790.4610.4350.0400.694S2,50.6591.4080.5160.0000.3820.0000.1730.0641.570The result of the decision tree method, which is referred to in Li and Chen [3], is listed in Table 5, where AR(R1,R2)=(0.97,1), SR(R1,R2)=(0.97,1), and CR=0.3.Table 5
Comparing results for the Swallow data set (R1,R2).
ItemsProposed methodDecision treeHyperplane support vectorAR(R1,R2)(1, 1)(0.97,1)(0.97,1)SR(R1,R2)(1, 0.97)(0.97,1)(0.97,1)CR10.30.1The result of the hyperplane method, referred to in Chang and Lin [35], is also listed in Table 5, whereAR(R1,R2)=(0.97,1), SR(R1,R2)=(0.97,1), and CR=0.1.We compared the three methods in Table5 to show that the proposed method can induce rules with better or equivalent values of AR and SR. In fact, the proposed method also has the best compactness rate.


### 4.3. HSV Dataset

The HSV dataset contains 122 patients classified into four classes, with each patient having 11 preoperating attributes. To maximize the support rate with respect to the proposed method (i.e., Model1), the proposed method generated seven hyperspheres and three unions of hyperspheres. The centroids and radii of the hyperspheres are reported in Table 6, and a comparison with other methods is reported in Table 7.Table 6
Centroid points for the HSV data by the proposed method.
Rule numbersUnion of spheresSk,lht,k,1ht,k,2ht,k,3ht,k,4ht,k,5ht,k,6ht,k,7ht,k,8ht,k,9ht,k,10ht,k,11rt,kR1S1,1∪S1,2…∪S1,8S1,10.5040.5280.3660.2880.8500.8480.351−0.2820.4050.2340.3131.576S1,20.4690.3950.3120.133−0.274−0.3090.1340.5900.8131.000−0.8473.044S1,30.2870.8670.4580.1890.9770.2670.017−0.8460.462−1.0001.0004.249S1,40.586−0.4000.6050.467−0.167−0.6310.2681.0000.5261.0000.1203.365S1,50.296−0.511−1.0000.536−0.2630.5520.9540.635−0.117−1.0000.6004.608S1,60.7750.678−0.0920.3400.3660.4550.4511.0000.4220.2950.4701.560S1,70.5250.2960.1940.124−0.945−0.4670.1271.0000.097−0.8970.6544.113S1,80.0000.1400.1090.2500.1930.1680.0630.1420.1810.1190.0820.089R2S2,1S2,10.5130.0560.1430.0780.5330.4390.1800.167−0.284−0.4640.7491.450S2,2S2,20.5330.3810.1390.568−0.373−0.0050.0800.8310.2930.2150.3691.293S2,3S2,30.000−0.4500.7090.5530.8961.0000.157−0.4470.068−0.5801.0003.579S2,4S2,40.0000.8620.543−0.0660.3890.4510.1060.394−0.0040.042−0.0140.409R3S3,1∪S3,2S3,10.6240.507−1.0000.1470.8401.0000.827−0.5850.1990.831−0.3804.277S3,20.5340.483−0.0880.365−0.3640.2700.4370.7850.7860.682−1.0003.003S3,3S3,30.0000.2100.6300.750−1.0000.2440.3881.0000.474−0.6040.4753.162R4S4,1∪S4,2∪S4,3S4,10.5510.3740.6370.2560.8650.9440.315−0.831−0.485−0.6760.9794.330S4,20.7170.2540.548−0.7180.1180.730−0.5470.498−0.580−0.4640.8213.287S4,30.5271.0000.5330.089−0.152−1.0000.3660.0460.5470.947−0.4362.943S4,4S4,40.4890.625−0.2090.5220.6440.5820.6151.0000.306−0.4010.9312.059S4,5S4,5−0.0110.491−0.4090.155−0.766−0.227−0.1071.0000.303−0.680−0.1852.843Table 7
Comparing results for the HSV data set (R1,R2,R3,R4).
ItemsProposed methodDecision treeHyperplane support vectorAR(R1,R2,R3,R4)(1,1,1,1)(0.93,0.81,0.7,0.71)(0.9,1,1,0.9)SR(R1,R2,R3,R4)(0.99,1,1,1)(0.93,0.72,0.78,0.71)(0.9,0.72,0.67,0.69)CR0.40.170.09Using the decision tree method in the HSV dataset generates 24 rules. In addition, the hyperplane method deduces 45 hyperplanes for the HSV dataset. Table7 also shows that the proposed method can find rules with the highest rates (i.e., AR, SR, and CR) compared with the other two methods.


### 4.4. Limitation of the Proposed Method

The hypersphere models are solved by one of the most powerful mixed-integer program software CPLEX [32] running in a PC. Based on optimization technique, the results of the numerical examples illustrate that the usefulness of the proposed method is better than that of the current methods, including the decision tree method and the hyperplane support vector method. As the solving time of the hypersphere model, which is linearized, mainly depends on the number of binary variables and constraints, solving the reformulated hypersphere model from the proposed algorithm takes about one minute for each dataset (i.e., in Sections 4.1 and 4.3), in which using eight piecewise line segments linearizes the nonlinear nonconvex term (i.e., L(ht,k,j2)) of Model 1.The computing time for solving a linearized hypersphere program grows rapidly as the numbers of binary variables and constraints increase. Also, the computing time of the proposed method is slower than that of the decision tree method and hyperplane method, especially for large datasets or a great number of piecewise line segments. In the further study, utilizing a mainframe-version optimization software [36–38], integrating meta-heuristic algorithms, or using distributed computing techniques can enhance solving speed to conquer this problem.


## 4.1. Iris Flower Dataset

The Iris Flower dataset contains 150 objects. Each object is described by four attributes (i.e., sepal length, sepal width, petal length, and petal width) and is classified by one of three classes (i.e., setosa, versicolor, and virginica). By solving the proposed method, we induced six hyperspheres (i.e.,S1,1∈Class1, S2,1,S2,2,S2,3∈Class2, and S3,1,S3,2∈Class3). The induced classification rules are reported in Table 2. Table 2 also lists a hypersphere and two unions (i.e., S1,1, S2,1∪S2,2∪S2,3, and S3,1∪S3,2) of hyperspheres with centroid points and radii.Table 2
Centroid points for the Iris data set by the proposed method.
Rule numberUnion of spheresSt,kht,k,1ht,k,2ht,k,3ht,k,4rt,kR1S1,1S1,10.3660.8070.0000.0000.6205R2S2,1∪S2,2∪S2,3S2,10.5570.3200.2050.4600.2540S2,20.5750.5810.6260.5150.0612S2,30.4230.2610.3520.4900.1388R3S3,1∪S3,2S3,10.2480.0002.2262.1514.8087S3,20.3290.1870.6500.6130.0330RuleR1 in Table 2 contains a hypersphere S1,1, which implies that(i)
“if(ai,1′-0.366)2+(ai,2′-0.807)2+(ai,3′-0)2+(ai,4′-0)2≤0.6205, then object xi belongs to class 1.”RuleR2 in Table 2 contains a union of three hyperspheres (i.e., S2,1∪S2,2∪S2,3) which implies that(i)
“if(ai,1′-0.557)2+(ai,2′-0.32)2+(ai,3′-0.205)2+(ai,4′-0.46)2≤0.254, then object xi belongs to class 2,” or(ii)
“if(ai,1′-0.575)2+(ai,2′-0.581)2+(ai,3′-0.626)2+(ai,4′-0.515)2≤0.0612, then object xi belongs to class 2,” or(iii)
“if(ai,1′-0.423)2+(ai,2′-0.261)2+(ai,3′-0.352)2+(ai,4′-0.49)2≤0.1388, then object xi belongs to class 2.”RuleR3 in Table 2 contains a union of two hyperspheres (i.e., S3,1∪S3,2), which implies that(i)
“if(ai,1′-0.248)2+(ai,2′-0)2+(ai,3′-2.226)2+(ai,4′-2.151)2≤4.8087, then object xi belongs to class 3,” or(ii)
“if(ai,1′-0.329)2+(ai,2′-0.187)2+(ai,3′-0.65)2+(ai,4′-0.613)2≤0.033, then object xi belongs to class 3.”Comparing the proposed method with both decision tree [3] and hyperplane methods [35] in deducing the classification rules for the Iris Flower dataset, Table 3 lists the experimental result.Table 3
Comparing results for the Iris flower data set (R1,R2,R3).
ItemsProposed methodDecision treeHyperplane support vectorAR(R1,R2,R3)(1,1,1)(1,0.98,0.98)(1,0.98,0.96)SR(R1,R2,R3)(1,0.98,0.98)(1,0.98,0.98)(1,0.96,0.98)CR10.50.1875The accuracy rates of (R1,R2,R3) in the proposed method are (1,1,1), as Model 1 has been solved. This finding indicates that none of objects in class 2 or class 3 are covered by S1,1, none of objects in classes 1 or 3 are covered by S2,1∪S2,2∪S2,3, and none of the objects in classes 1 or 2 are covered by S3,1∪S3,2. The support rate of (R1,R2,R3) in the proposed method is (1,0.98,0.98), indicating that all objects in class 1 are covered by S1,1, 98% of the objects in class 2 are covered by S2,1, S2,2, and S2,3, and 98% of the objects in class 3 are covered by S3,1 and S3,2. The compactness rate of rules R1, R2, and R3 is computed as CR(R1,R2,R3)=3/3=1. Finally, we determine the following.(i)
Although all three methods perform very well in the rates of accuracy and support, the proposed method has the best performance for the accuracy of classes 2 and 3 (i.e.,R2 and R3).(ii)
The proposed method has the best compactness rate.


## 4.2. Swallow Dataset

The European barn swallow (Hirundo rustica) dataset was obtained by trapping individual swallows in Stirlingshire, Scotland, between May and July 1997. This dataset contains 69 swallows. Each object is described by eight attributes, and it belongs to one of two classes (i.e., the birds are classified by the gender of individual birds).Here, we also used Model1 to induce the classification rules. Table 4 lists the optimal solutions (i.e., centroid and radius) for both rules R1 and R2.Table 4
Centroid points for the Swallow data set by the proposed method.
Rule numberUnion of spheresSt,kht,k,1ht,k,2ht,k,3ht,k,4ht,k,5ht,k,6ht,k,7ht,k,8rt,kR1S1,1∪S1,2∪S1,3∪S1,4S1,10.6070.1100.8060.0000.0000.4061.0771.1631.780S1,20.4830.0000.2360.3280.0000.7930.2800.9310.948S1,30.5880.0001.1790.0000.0000.6531.0370.9821.879S1,40.4140.0000.6580.0000.2270.0850.5631.2241.197R2S2,1∪S2,2∪S2,3∪S2,4∪S2,5S2,10.3580.6670.3711.4030.3601.5300.6340.1142.825S2,20.1981.1020.6970.0000.0001.7340.1100.5952.632S2,30.5320.4220.3231.6761.0090.0000.1800.0202.458S2,40.5280.0000.4300.8760.5790.4610.4350.0400.694S2,50.6591.4080.5160.0000.3820.0000.1730.0641.570The result of the decision tree method, which is referred to in Li and Chen [3], is listed in Table 5, where AR(R1,R2)=(0.97,1), SR(R1,R2)=(0.97,1), and CR=0.3.Table 5
Comparing results for the Swallow data set (R1,R2).
ItemsProposed methodDecision treeHyperplane support vectorAR(R1,R2)(1, 1)(0.97,1)(0.97,1)SR(R1,R2)(1, 0.97)(0.97,1)(0.97,1)CR10.30.1The result of the hyperplane method, referred to in Chang and Lin [35], is also listed in Table 5, whereAR(R1,R2)=(0.97,1), SR(R1,R2)=(0.97,1), and CR=0.1.We compared the three methods in Table5 to show that the proposed method can induce rules with better or equivalent values of AR and SR. In fact, the proposed method also has the best compactness rate.


## 4.3. HSV Dataset

The HSV dataset contains 122 patients classified into four classes, with each patient having 11 preoperating attributes. To maximize the support rate with respect to the proposed method (i.e., Model1), the proposed method generated seven hyperspheres and three unions of hyperspheres. The centroids and radii of the hyperspheres are reported in Table 6, and a comparison with other methods is reported in Table 7.Table 6
Centroid points for the HSV data by the proposed method.
Rule numbersUnion of spheresSk,lht,k,1ht,k,2ht,k,3ht,k,4ht,k,5ht,k,6ht,k,7ht,k,8ht,k,9ht,k,10ht,k,11rt,kR1S1,1∪S1,2…∪S1,8S1,10.5040.5280.3660.2880.8500.8480.351−0.2820.4050.2340.3131.576S1,20.4690.3950.3120.133−0.274−0.3090.1340.5900.8131.000−0.8473.044S1,30.2870.8670.4580.1890.9770.2670.017−0.8460.462−1.0001.0004.249S1,40.586−0.4000.6050.467−0.167−0.6310.2681.0000.5261.0000.1203.365S1,50.296−0.511−1.0000.536−0.2630.5520.9540.635−0.117−1.0000.6004.608S1,60.7750.678−0.0920.3400.3660.4550.4511.0000.4220.2950.4701.560S1,70.5250.2960.1940.124−0.945−0.4670.1271.0000.097−0.8970.6544.113S1,80.0000.1400.1090.2500.1930.1680.0630.1420.1810.1190.0820.089R2S2,1S2,10.5130.0560.1430.0780.5330.4390.1800.167−0.284−0.4640.7491.450S2,2S2,20.5330.3810.1390.568−0.373−0.0050.0800.8310.2930.2150.3691.293S2,3S2,30.000−0.4500.7090.5530.8961.0000.157−0.4470.068−0.5801.0003.579S2,4S2,40.0000.8620.543−0.0660.3890.4510.1060.394−0.0040.042−0.0140.409R3S3,1∪S3,2S3,10.6240.507−1.0000.1470.8401.0000.827−0.5850.1990.831−0.3804.277S3,20.5340.483−0.0880.365−0.3640.2700.4370.7850.7860.682−1.0003.003S3,3S3,30.0000.2100.6300.750−1.0000.2440.3881.0000.474−0.6040.4753.162R4S4,1∪S4,2∪S4,3S4,10.5510.3740.6370.2560.8650.9440.315−0.831−0.485−0.6760.9794.330S4,20.7170.2540.548−0.7180.1180.730−0.5470.498−0.580−0.4640.8213.287S4,30.5271.0000.5330.089−0.152−1.0000.3660.0460.5470.947−0.4362.943S4,4S4,40.4890.625−0.2090.5220.6440.5820.6151.0000.306−0.4010.9312.059S4,5S4,5−0.0110.491−0.4090.155−0.766−0.227−0.1071.0000.303−0.680−0.1852.843Table 7
Comparing results for the HSV data set (R1,R2,R3,R4).
ItemsProposed methodDecision treeHyperplane support vectorAR(R1,R2,R3,R4)(1,1,1,1)(0.93,0.81,0.7,0.71)(0.9,1,1,0.9)SR(R1,R2,R3,R4)(0.99,1,1,1)(0.93,0.72,0.78,0.71)(0.9,0.72,0.67,0.69)CR0.40.170.09Using the decision tree method in the HSV dataset generates 24 rules. In addition, the hyperplane method deduces 45 hyperplanes for the HSV dataset. Table7 also shows that the proposed method can find rules with the highest rates (i.e., AR, SR, and CR) compared with the other two methods.


## 4.4. Limitation of the Proposed Method

The hypersphere models are solved by one of the most powerful mixed-integer program software CPLEX [32] running in a PC. Based on optimization technique, the results of the numerical examples illustrate that the usefulness of the proposed method is better than that of the current methods, including the decision tree method and the hyperplane support vector method. As the solving time of the hypersphere model, which is linearized, mainly depends on the number of binary variables and constraints, solving the reformulated hypersphere model from the proposed algorithm takes about one minute for each dataset (i.e., in Sections 4.1 and 4.3), in which using eight piecewise line segments linearizes the nonlinear nonconvex term (i.e., L(ht,k,j2)) of Model 1.The computing time for solving a linearized hypersphere program grows rapidly as the numbers of binary variables and constraints increase. Also, the computing time of the proposed method is slower than that of the decision tree method and hyperplane method, especially for large datasets or a great number of piecewise line segments. In the further study, utilizing a mainframe-version optimization software [36–38], integrating meta-heuristic algorithms, or using distributed computing techniques can enhance solving speed to conquer this problem.


## 5. Conclusions and Future Work

This study proposes a novel method for deducing classification rules, which can find the optimal solution based on a hypersphere domain. The optimization technique for finding classification rules is approached to optimal. Results of the numerical examples illustrate that the usefulness of the proposed method is better than that of the current methods, including the decision tree method and the hyperplane method. The proposed method is guaranteed to find an optimal rule, but the computational complexity grows rapidly by increasing the problem size. More investigation and research are required to enhance further the computational efficiency of globally solving large-scale classification problems, such as running mainframe-version optimization software, integrating meta-heuristic algorithms, or using distributed computing techniques.



---

*Source: 398232-2012-04-02.xml*