Soft Comput (2008) 12:647–655
DOI 10.1007/s00500-007-0242-3

FOCUS

An empirical comparison of min–max-modular k-NN with different
voting methods to large-scale text categorization
Ke Wu · Bao-Liang Lu · Masao Utiyama ·Hitoshi Isahara

Published online: 16 October 2007
© Springer-Verlag 2007

Abstract Text categorization refers to the task of assigning
the pre-defined classes to text documents based on theircontent. k-NN algorithm is one of top performing classifiers on text data. However, there is little research work on
the use of different voting methods over text data. Also,
when a huge number of training data is available online,
the response speed slows down, since a test document has toobtain the distance with each training data. On the other hand,min–max-modular k-NN (M3 -k-NN) has been applied tolarge-scale text categorization. M3 -k-NN achieves a good
performance and has faster response speed in a parallel computing environment. In this paper, we investigate five different voting methods for k-NN and M3 -k-NN. The
experimental results and analysis show that the Gaussian
voting method can achieve the best performance among all
voting methods for both k-NN and M3 -k-NN. In addition,
The work of K. Wu and B. L. Lu was supported in part by the National
Natural Science Foundation of China under the grants NSFC
60375022 and NSFC 60473040, and the Microsoft Laboratory forIntelligent Computing and Intelligent Systems of Shanghai Jiao Tong
University.
K. Wu · B.-L. Lu (B)Department of Computer Science and Engineering,
Shanghai Jiao Tong University, 800 Dong Chuan Road,
Shanghai, 200240, Chinae-mail: wuke@sjtu.edu.cn
B.-L. Lue-mail: bllu@sjtu.edu.cn
M. Utiyama · H. Isahara
Knowledge Creating Communication Research Center,
National Institute of Information and Communications Technology,
3-5 Hilaridai, Seika-cho, Soraku-gun, Kyoto, 619-0289, Japane-mail: mutiyama@nict.go.jp
H. Isaharae-mail: isahara@nict.go.jp

M3 -k-NN uses less k-value to achieve the better performance
than k-NN, and thus is faster than k-NN in a parallel computing environment.
Keywords Text categorization · k-NN algorithm ·Min–max-modular k-NN · Parallel computing

1 Introduction
The ever-increasing Web documents are available over Internet, which makes it difficult to manage these documents andto retrieve useful information from these documents. Text
categorization has become one of the most important techniques to handle the problem. Text categorization aims toautomatically assign documents into some predefined categories. Many machine learning methods (Yang and Chute1994; Joachims 1997; Joachims 1998; Nigam et al. 1999;
Yang and Liu 1999; Sebastiani 2002) have been proposed tothis end. Among these methods, k-NN algorithm has been
widely used as a basic algorithm for text categorization,
since it is simple yet efficient. In Yang (1999), Bergo (2007),
Sebastiani(2002), it shows that although not perfect, k-NN isthe best overall performing system on diverse sets. Despite its
good performance, k-NN, however, has not been employedas widely in applications where very large high-dimensional
data are involved. One main reason is the computational complexity of distance computation in high-dimensional space,often regarded as prohibitive.
On the other hand, parallel processing is an effective technique for scaling up the learning algorithm. Lu and Ito (1999)
proposed a min–max-modular (M3 ) network for solving
large-scale and complex multi-class classification problems
effortlessly and efficiently. And the network model has been

123

648

applied to learning large-scale, real world multi-classproblems such as part-of-speech tagging and classification ofhigh-dimensional, single-trial electroencephalogram signals(Lu et al. 2004b). Recently, Lu et al. (2004a) have proposed a part-versus-part task decomposition method and a newmodular support vector machine, called min–max-modular
support vector machine (M3 -SVM), which was developed
for solving large-scale pattern classification problems (Wanget al. 2005; Fan and Lu 2005; Liu et al. 2005a; Lian et al.
2005; Yang and Lu 2006; Luo and Lu 2006). Meanwhile,
Zhao and Lu (2004, 2006) combined k-NN with M3 -networkand obtained a comparable yet efficient performance to k-NN
based on the Euclidean distance metric.
The k-NN classifier tries to estimate the conditional classprobabilities from samples in a local region of the data space.
Usually, the majority voting method and Euclidean distancemetric is used. However, majority voting method simply
assumes the k nearest neighbors of a data point to be contained in a region of relatively small volume, so that sufficiently
good resolution in the estimation of different conditional densities can be obtained. Unfortunately, this is not the case. To
estimate different conditional densities, some other voting
methods need to be explored. To our best knowledge, few
literature investigates k-NN with different voting methods
on the text data, which are high-dimensional and sparse. In
addition, M3 -k-NN is a parallel ensemble of multiple k-NN
classifiers, which boost the test speed in parallel computing
environments. Therefore, we are interested in applicationof different voting methods to M3 -k-NN. In the paper, we
introduce some voting techniques other than majority voting
method into M3 -k-NN to investigate the effect of performance on M3 -k-NN.
The remainder of this paper is organized as follows. Section 2 gives a brief introduction to min–max-modular kNN. Section 3 introduces k-NN classifier and four voting
methods in detail. Experiments and discussions are presented in Sect. 4. Section 5 concludes this paper.

K. Wu et al.

2.1 Task decomposition
Let T be the training set for an M-class classification problem,L,T = (X l , Yl )l=1(1)where X l ∈ X ⊂ Rn is the input vector, Yl ∈ Y ⊂ R M isthe desired output, and L is the total number of training data.
It has been suggested that an M-class problem can be divided into M(M − 1) relatively smaller two-class subproblems
based on the class relations among training data (Lu and Ito1997). However, in these M(M − 1) two-class subproblems,
we can observe that half of subproblems need to be learned
and another half of subproblems are the same as the previous
ones from the point of view of pattern classification. The
training set for each of the two-class subproblems is given
by
( j)

(i)

L

Li
j
∪ {(X l , −1)}l=1
Ti j = {(X l , +1)}l=1

for i = 1, 2, . . . , M and j = i + 1, . . . , M
( j)

(i)

where X l ∈ Xi and X l ∈ X j are the training inputs
belonging to class Ci and class C j respectively, Xi is theset of training inputs belonging to class Ci , X j is the set oftraining inputs belonging to class C j , L i and L j denotes theMnumbers of data in Xi and X j , respectively, i=1
Xi = X ,M
and i=1 L i = L.
If some of the two-class problems defined by Eq. 2 are stilllarge and hard to be learned, such problems can be further
broke into many two-class problems as small as the user
expects (Lu and Ito 1999). Assume that Xi is partitioned into
Ni (1 ≤ Ni ≤ L i ) subsets in the form
 ( j)
(i j) L i
Xi j = X l
for j = 1, . . . , Ni
l=1

and i = 1, . . . , M,
2 Min–max-modular k-NN
In this section, we give a brief introduction to the min–max-modular k-Nearest Neighbor (M3 -k-NN). M3 -k-NN isa framework that divides a complex classification problem
into many relatively smaller independent two-class subproblems, construct sub-classifers by k-NN algorithm, and thenintegrates these smaller k-NN classifiers according to two
module combination rules, namely the minimization principle and the maximization principle (Lu and Ito 1997; Lu
and Ito 1999). The model has three basic components: task
decomposition, concurrent learning, and module combination. Since k-NN is an algorithm with little learning, we only
focus on task decomposition and module combination.

123

(2)

(3)

 i
Xi j = Xi .
where Nj=1
According to the above partition of Xi , the two-class problem Ti j defined by Eq. 2 can be divided into Ni × N j relatively smaller and simpler two-class subproblems. The training
set for each of the two-class subproblems is given by
(u,v)

Ti j

=



(iu)

Xl

 L (u)  L (v)
i
j
( jv)
, +1
∪ X l , −1
l=1

for u = 1, . . . , Ni , v = 1, . . . , N j ,l=1

i = 1, . . . , M and j = i + 1, . . . , M.
(iu)

jv

(4)

∈ Xiu and X l ∈ X jv are the training inputs
where X lbelonging to class Ci and class C j

An empirical comparison of min–max-modular k-NN with different voting methods to large-scale TC

From Eqs. 2 and 3, we see that an M-class problem can M−1  M
be decomposed into
j=i+1 Ni × N j two-classi=1
subproblems. This decomposition process is simple anddomain-specific knowledge concerning the problem decomposition is not required. Therefore, any large-scale problem
can be easily decomposed into a number of two-class subproblems as small as a user needs.
For ease of description, we assume that each class has thesame number of training data J . Let L be the total numberof training data for an M-class classification problem, and
L = M × J . If an M-class problem is decomposed into M
2
two-class subproblems, the number of training data for eachof the two-class subproblems is 2 × J .
 M−1
If an M-class problem is decomposed into
i=1
M
N
×
N
two-classsubproblems,
thenumber
of
traii
j
j=i+1
ning data for each of the two-class subproblems is about
J/Ni  + J/N j (5)where z denotes the smallest integer greater than or equal
to z.
Since each of the two-class subproblems can be treated ascompletely independent problems in the training phase, allof the problems can be learned in parallel.

649

3 Voting methods for k-NN
3.1 k-NN algorithm
The k-NN algorithm has been introduced by Fix and Hodges(Fix and Hodges 1951) and has since become well-known
in the pattern recognition literature. Also, it is one of top
performing methods of automatic text categorization (Yangand Liu 1999; Sebastiani 2002; Lewis et al. 2004; Liu et al.
2005b). In text categorization, k-NN algorithm typically isused as follows. Given a test document d, the system finds thek nearest neighbors among training documents, and exploit
their classes to weight class candidates. The similarity scoreof each nearest neighbor document to the test document isused as the weight of the classes of the neighbor document.
If more than one of k nearest neighbors share a class, theseweights of that class are added together, and the resulting
weighted sum is used as the likelihood score of that classregarding the test document. Consequently, a ranked classlist is obtained for the test document by sorting the scores ofeach possible classes. The decision rule can be formulated
as follows:score(d, ci ) =Sim(d, d j )δ(d j , ci )(7)d j ∈kNN(d)2.2 Module combination
These completely independent modules need to be combinedin a reasonable and elegant way. Consequently, M3 model has
proposed a simple yet effective way to perform it. After training each module which is assigned to learn associated subproblems, all of the individual trained modules can be easily
integrated into an M3 network according to the minimization
principle and the maximization principle.
Specifically, these submodules are integrated into a M3 (u)network with L i MIN units and one MAX unit according
to two combination principles (Lu and Ito 1997; Lu and Ito
1999; Lu and Ichikawa 2000) as follows:
(v)

Li

(x)
Biuj (x) = min Bi(u,v)
j
v=1

and
(u)

Li

Bi j (x) = max Biuj (x)

(6)

u=1

(u,v)

where Bi j(x) denotes the output function of the classifier(u,v)

corresponding to the two-class subproblem Ti j , Biuj (x)denotes the transfer function of a combination of multiple
classifiers integrated by the MIN unit and Bi j (x) denotes theresulting output of a combination of multiple MIN units by
MAX principle.

where kNN(d) indicates the set of k nearest neighbors of
document d; δ(d j , ci ) is 1 if document d j belongs to class ci
and 0 otherwise and Sim(d, d j ) denotes the similarity metricbetween d and d j . For test document d, it is assigned the classwith the highest score.
3.2 Different voting methods
A k-NN classifier tries to estimate the conditional class probabilities from samples in a local region of the data space.
Typically, we apply a majority voting method to k-NN, which
regards each neighbor in its neighbors equally. However, wemight want to weight nearer neighbors more heavily. Coverand Hart (1967) have proved that as the number N of samples
and k tend to infinity in such a manner that k/N → 0, theerror rate of the k-NN rule approaches the optimal Bayes
error rate. However, in the finite sample case, the majorityvoting k-NN rule is not guaranteed to be optimal way of
exploited the information provided by the neighborhood of
unclassified patterns, since it simply assume that the sufficiently good resolution in the estimated different conditional
densities in a region of relatively small volume. In practice,since the number of samples is finite, the closest neighbors
do not provide the sufficient information about the different
conditional densities. Thus, the distance between x and oneof its closest neighbors may provide more clues for the estimation of the conditional densities.

123

650

K. Wu et al.

Dudani (1976) proposed three different methods. The firstis referred to linear voting method, in which the nearest
neighbor gets a weight of 1, the furthest neighbor a weightof 0, and the other weights are scaled linearly to the intervalin between. The method can be formalized as follows:dk −d jdk −d1 ,wj =if dk = d1
if dk = d1

1,

(8)

where d j is the distance to the query of the jth nearest neighbor, d1 is the nearest neighbor, and dk is the furthest (or kth)neighbor.
The second is the inverse distance, that is, the neighbors ofa query are assigned the weight reciprocally to the distance tovote for the predicted class. In text categorization, this voting
policy is the variant of the method, since a similarity measureis the converse of a distance function. In pattern recognition
community, the distances between a query and samples intraining set are calculated, while in text categorization, similarities between a query and samples in training set are used.
Usually, similarity metric is the reciprocal of distance metric.
For clarity, we use distance metric in this paper. The inverse
distance method can be formulated as follows:
wj =

1
dj

Category# dataTraining# of subsets

Test

c1

Events

31354

98

2714

c2

Core industry

39608

124

3363

c3

Environment

21247

67

1371

c4

Culture

3344

11

357

c5

Food

19645

62

1992

c6

Labor

5757

18

317

c7

Fishery

320

1

17

c8

Diplomacy

767

3

43

c9

Music

2274

8

164

c10

Social security
total

3654

12

226

127970404

10564

Here ‘# of subsets’ indicates the number of sub-modules randomly
divided by M3 -k-NN when the size of a module is 320

4 Experiments(9)

The third is the rank voting method. Its basic idea is toconsider the ranking position according to the ranked list of
the distances between a query and samples in training set andthen to weight more the sample with high rank. We formulate
the method as follows.
wj = k − j + 1(10)

In this paper, Gaussian voting method was also investigated, since a lot of events conform to Gaussian distribution. It
is also based on the same idea as three aforementioned voting
methods that a training sample closer to the test sample will
have a higher influence on the final classification compared
to a sample that is further away from the test sample. However, various methods employ difference descending function.
Gaussian voting method uses the following equation:22
1
exp−d j /2δ
wj = √
2π δ(11)Now, to generalize k-NN algorithm with different voting
methods, we reformulate Eq. 7 as follows:W(dis(d, d j )δ(d j , ci ))(12)d j ∈kNN(d)where dis(d, d j ) denotes the distance between document d
and document d j , and W denotes the weight function.

123#

4.1 Experimental setup

if d j = 0score(d, ci ) =Table 1 Distributions of training and test data of the extracted subset
from Yomiuri news corpus

In the section, we present our results on Yomiuri News Corpus, which is the largest corpus currently consisting of
2,190,512 documents in the full collections from the years
1987 to 2001. Since the simulations are conducted on a PC
machine with Pentium D 2.8 GHz CPU and 2.0 GB memory,time spent on a very large amount of corpus is large and thus
we extract one subset of the corpus, which contains 127,970
training samples and 10,564 test samples. The details aredescribed in Table 1.
In all the experiments, we use 5000 features for whichχ 2 statistical method was applied and adopt tf-idf weighting scheme to weight each feature. Additionally, each vector
representation is L2-normalized to a unit vector. In the simulations, according  to Eq. 2, the text categorization problem isdivided into 10
2 = 45 two-class subproblems. From Table 1
and the definition of the two-class subproblems, we see thatthe number of training data for the smallest two-class subproblem T78 is 1,087, while the largest two-class subproblem T12
is 71,062. Although these two-class subproblems are smaller
than the original problem, they are not adequate for massively parallel computation. In order to speed-up response ofk-NN algorithm during recognition phase, we should further
decompose each of the bigger two-class subproblems into a
number of relatively smaller and simpler two-class subproblems. By using the decomposition method, each of the training sets for the bigger two-class subproblems is randomly
divided into a number of relatively smaller subsets according
to Eq. 4.

An empirical comparison of min–max-modular k-NN with different voting methods to large-scale TC
0.85

0.68
majority
linearinverserank
Gaussian

0.8
0.75

majority
linearinverserank
Gaussian

0.66
0.64
0.62

0.7

Macro−F1

Micro−F1

651

0.65

0.6
0.58
0.56
0.54

0.6

0.52
0.55
0.5
0.5

0

5

10

15

0.48

20

0

5

K Value

10

15

20

15

20

K Value

0.81

0.68

0.805

0.67

0.8
0.66
0.79

Macro−F1

Micro−F1

0.795

0.785
0.78

0.64
0.63

majority
linearinverserank
Gaussian

0.775
0.77
0.765
0.76

0.65

0

5

10

15

majority
linearinverserank
Gaussian

0.62
0.61

20

0.6

0

K Value

5

10
K Value

Fig. 1 Micro-F1 and Macro-F1 results of different weighted-distance methods with Euclidean distance. The first row shows the results of
M3 -k-NN, and the second row shows the results of k-NN

In the simulation, the size of the modular is taken as320, since the number of the smallest class in training set
is 320. The samples in each class are divided approximately equally. In addition, two distance metrics were used.
One is Euclidean distance metric, which is a common metricused in pattern recognition community. Another is cosine
distance metric, which is typically used to measure the similarity between documents. However, for a voting method, it
is typically based on distance metric, which is dissimilarity
between documents. Therefore, for a uniform presentation,
we used angular distance metric as another metric in our
experiments. Specifically, the angular distance corresponds
to the arc cosine between two documents.

recall and precision in the following way:F1 =2 × Recall × Precision
Recall + Precision

For convenience, we summarize the F1 scores over thedifferent categories by the macro-average of F1 scores andover all the samples by the micro-average F1 scores. The two
measures are called Macro-F1 and Micro-F1, respectively.
Macro-F1 emphasizes the performance of the system on rarecategories, while Micro-F1 embody the performance of thesystem on major categories since they contain more samples.
In addition, Macro-recall is defined to be average recall
over categories and Macro-precision is defined to be average
precision over categories.

4.2 Performance measure
4.3 Results and discussion
To evaluate the effectiveness of a text categorization system,
we use the standard recall, precision and F1 measure. Recall
is defined to be the ration of the number of the correctly assigned documents to the number of positive samples. Precision
is the ratio of the number of the correct documents in thepositively assigned documents. The F1 measure combines

The experimental results of k-NN and M3 -k-NN using
Euclidean distance metric are shown in Figs. 1 and 2. The
results of k-NN and M3 -k-NN using angular distance metricare shown in Figs. 3 and 4. When Gaussian voting method
is used for k-NN and M3 -k-NN based on Euclidean distance

123

652

K. Wu et al.
0.71

0.65
majority
linearinverserank
Gaussian

0.69

majority
linearinverserank
Gaussian

0.6
Macro Recall

Macro Precision

0.7

0.68

0.55

0.67
0.5
0.66

0.65

0

5

10

15

0.45

20

0

5

K value
0.86

0.82
0.8

20

majority
linearinverserank
Gaussian

0.63
0.62
0.61
Macro Recall

Macro Precision

15

0.64
majority
linearinverserank
Gaussian

0.84

0.78
0.76
0.74

0.6
0.59
0.58

0.72
0.7

0.57

0.68

0.56

0.66

10
K value

0

5

10

15

20

0.55

0

5

K value

10

15

20

K value

Fig. 2 Micro-precision and Macro-recall results of different weighted-distance methods with Euclidean distance. The first row shows the resultsof M3 -k-NN, and the second row shows the results of k-NN

metric, δ value was taken 1.0 empirically. In addition, whenangular distance metric was used, δ value was set to 0.4
empirically.

• We can observe that M3 -k-NN and k-NN can achievealmost the same best performance on both Micro-F1 andMacro-F1 . It is worthwhile to notice that the Macro-F1of M3 -k-NN is higher than k-NN, when angular distancemetric is applied. Although data decomposition makes
data more sparse, M3 -network structure results in a comparatively good performance.
• M3 -k-NN uses less k value to achieve its peak performance on both Micro-F1 and Macro-F1 than traditional
k-NN. Multiple parallel modules lead to more samples
involved in the final decision and thus a small k value isneeded to achieve the optimal performance.
• When we use Euclidean distance metric, Macro-precision
is raised with k value increasing. However, an opposite
case occurs when angular distance metric is used. Thismay be because angular distance metric is more appropriate for text data than Euclidean distance.

123• Linear voting method is superior to the other methods atlarger values of k and its best performance is better thanother methods.
In order to have a close look to the five different voting
methods, these methods are depicted in Fig. 5. The linear
voting method is an adaptive voting method which adapt
the effective size of the neighborhood to the local properties of the data and thus often can achieve a good performance in all experiments. In contrast, inverse distance voting
method makes a global assumption about the relevance gradient, which leads to a comparatively poor performance. In
addtion, since √ 1 is a constant after δ is assigned, Guassian
2πδvoting function just uses exp−d j /2δ with δ=1 for illustration.
For Guassian voting method, an assumption is made that therelation between a distance and its voting weight conforms to
Guassian distribution. In Euclidean space, sparse and highdimensional characteristics of text data results in large distance between a query and training samples and thus its practical performance is similar to the majority voting method.
From Fig. 5, we can see that the weight is a number close
0 when the distance is greater than 2. That is, the nearest22

An empirical comparison of min–max-modular k-NN with different voting methods to large-scale TC

653

0.76
0.87
0.75
0.865

0.74
Macro−F1

Micro−F1

0.86
0.855
0.85
0.845

0.72
0.71
major
linearinverserank
Gaussian

0.7
majority
linearinverserank
Gaussian

0.84
0.835
0.83

0.73

0

5

0.69
0.68
10
K Value

15

0.67

20

0

5

10
K Value

15

20

0.755

0.875

majority
linearinverserank
Gaussian

0.75

0.87

0.745
0.865
Macro−F1

Micro−F1

0.74
0.86
0.855
majority
linearinverserank
Gaussian

0.85
0.845

0.735
0.73
0.725
0.72
0.715

0.84

0.71
0

5

10
K Value

15

20

0

2

4

6

8
10
K Value

12

14

16

18

Fig. 3 Micro-F1 and Macro-F1 results of different weighted-distance methods with the angular distance metric. The first row shows the resultsof M3 -k-NN, and the second row shows the results of k-NN
0.8

0.86
majority
inverselinearrank
Gaussian

Macro Precision

0.76
0.74

0.84
0.82

Macro Recall

0.78

0.72
0.7

0.8
0.78
majority
inverselinearrank
Gaussian

0.68
0.76
0.66
0.74

0.64
0.62

0

5

10

15

0.72

20

0

5

K Value
0.73

0.88

0.725

0.86

15

20

0.84

0.715

Macro Recall

Macro Precision

0.72

0.71
0.705
majority
inverselinearrank
Gaussian

0.7
0.695
0.69
0.685

10

K Value

0

5

0.82
0.8
0.78

majority
inverselinearrank
Gaussian

0.76
0.74

10

K Value

15

20

0.72

0

5

10

15

20

K Value

Fig. 4 Micro-precision and Macro-recall results of different weighted-distance methods with the angular distance metric. The first row shows theresults of M3 -k-NN, and the second row shows the results of k-NN

123

654
1.5

1.5

1

1

weightweightFig. 5 Illustration of four
different voting methods. Left
top is linear voting method;
right top is inverse distancevoting method; left bottom is
Gaussian voting method; andright bottom is rank voting
method. Here d1 denotes the
distance of the nearest neighborand dk denotes the distance ofthe furthest (kth) nearest
neighbor, and red line indicatesmajority voting method

K. Wu et al.

0.5

0

0.5

0

d1

2

4

dk
distance

6

0

8

0

2

4

6

8

3

4

distance

1.5

4

3

weightweight

1
2

0.5
1

0

0

2

4

6

0

8

0

1

2

distanceneighbors with the distance greater than 2 are treated equally.
However, its overall performance is the best over micro-F1
measure among the five methods in a comparatively compact
distance space. It benefits from the narrow interval of angulardistance ([0, π/2]). In addition, rank voting method is also an
adaptive method, but it ignores the length of the distance andfocuses on the rank of the distance. Therefore, it does notproduce an expected performance. As for majority voting
method, it is a common method for voting. Although for
k-NN, a comparatively poor performance is produced, forM3 -k-NN based on the angular method, the best macro-F1
value is generated.
To compare M3 -k-NN with k-NN, the best performancefor each voting method is summarized in Table 2. From
this table, we can see that Guassian voting method basedon angular distance achieves the best micro-F1 performanceover both k-NN and M3 -k-NN. In addition, for k-NN, linear
voting method obtains the best macro-F1 performance, while
for M3 -k-NN, simple majority voting method gets the best
macro-F1 performance.
4.4 Time complexity analysis
For an M-class problem, we suppose that the number of all
training samples is N . Predication for one new query will
be done in O(N ), since k-NN needs to retrieval all training
samples to acquire k nearest neighbors. When M3 -k-NN is123

K Value

Table 2 The best performance and the corresponding k value of different voting methods based on two distance metrics
VotingmethodM3 -k-NN (%)

k-NN (%)
Micro-F1 k

Majority 79.31
86.53
Linear
79.94
87.07
Inverse 78.99
86.79
Rank
79.17
87.00
Gaussian 78.92
87.13

13
11
17
17
13
13
17
15
13
13

Macro-F1 k

Micro-F1 k Macro-F1 k

66.20
73.61
67.53
74.53
66.20
74.35
65.58
74.50
66.20
74.50

78.59
86.31
79.20
86.53
78.59
84.51
79.09
84.77
78.59
87.02

3
3
7
11
3
5
5
5
3
5

1 64.72
3 76.04
5 66.56
7 75.04
1 64.72
5 72.50
3 65.01
7 72.12
1 64.72
5 75.44

1
3
5
5
1
1
3
5
1
5

For each voting method, the data in the first row is based on Euclidean
distance metric, and the data in the second row is based on angulardistance metricused in the simulations for an M-class problem, the M-classproblem is first decomposed into M(M − 1)/2 two-classproblem and then each two-class problem is handled via M3 k-NN. Although it seems to increase computational load, thecomputation can be done in a parallel way. When M3 -k-NN
is not used in a parallel environment, the computation canbe done in about 2N /M. If we apply M3 -k-NN to each twoclass problem in a parallel way, the computational time will
be sharply down with the decrease of each modular size. In
the extreme case, if the number of positive samples is M1

An empirical comparison of min–max-modular k-NN with different voting methods to large-scale TC

and the number of negative samples is M2 in each smaller
modular classifier, the computation will be done in 2N /(M ×
M1 × M2 ).

5 Conclusion
In this paper, we have compared several voting methods for
k-NN and M3 -k-NN. The experimental results show that the
majority voting method can achieve the best macro-F1 performance when M3 -k-NN is applied to text categorization,
while linear voting method can obtain the best macro-F1
performance when k-NN is used. In addition, the Gaussian
voting method can achieve the best micro-F1 performancefor both k-NN and M3 -k-NN. From the experiment results,
we can see that M3 -k-NN has two important advantages overtraditional k-NN. 1) M3 -k-NN can use less k value to achieve
peak performance than k-NN, and 2) M3 -k-NN can spend lesstime to complete prediction than k-NN in a parallel computing environment. As to future work, we will use a combination of several distance-weighted policies for M3 -k-NN,
since different methods have complementary performance
when k value is small, and improve the Gaussian voting
method by automatically adjusting its δ parameter.
References
Bergo A (2007) Text categorization and prototypes. (In: http://www.illc.
uva.nl/Publications/ResearchReports/MoL-2001-08.text.pdf)
Cover T, Hart P (1967) Nearest neighbor pattern classification. IEEE
Trans Inform Theory IT-13(1):21–27
Dudani S (1976) The distance-weighted k-nearest-neighbor rule. IEEE
Trans Syst Man Cybern SMC-6:325–327
Fan ZG, Lu BL (2005) Multi-view face recognition with min–max
modular svms. In: ICNC (2), pp 396–399
Fix E, Hodges J (1951) Discriminatory analysis, nonparametric discrimination: consistency properties. Technical report, USAF Schollof aviation and medicine, Randolph Field 4
Joachims T (1997) A probabilistic analysis of the Rocchio algorithmwith TFIDF for text categorization. In: Fisher DH (ed) Proceedingsof ICML-97, 14th international conference on machine learning,
Morgan Kaufmann Publishers, San Francisco, USA, pp 143–151
Joachims T (1998) Text categorization with support vector machines:
learning with many relevant features. In: Nédellec C, Rouveirol C(eds) Proceedings of ECML-98, 10th European conferenceon machine learning, Springer, Heidelberg, DE, pp 137–142(Published in the “Lecture Notes in Computer Science” series,
number 1398)
Lian HC, Lu BL, Takikawa E, Hosoi S (2005) Gender recognition using
a min–max modular support vector machine. In: ICNC (2), pp 438–
441

655

Lewis DD, Yang Y, Rose TG, Li F (2004) Rcv1: A new benchmark collection for text categorization research. J Mach Learn Res 5:361–
397
Liu FY, Wu K, Zhao H, Lu BL (2005a) Fast text categorization withmin–max modular support vector machines. In: IEEE international
joint conference on neural networks, vol 1, pp 570–575
Liu TY, Yang Y, Wan H, Zhou Q, Gao B, Zeng HJ, Chen Z, Ma WY(2005b) An experimental study on large-scale web categorization.
In: WWW ’05: special interest tracks and posters of the 14th international conference on World Wide Web, ACM Press, New York,NY, USA, pp 1106–1107
Lu BL, Ichikawa M (2000) A Gaussian zero-crossing discriminat function for min–max modular neural networks. In: Proceedings of
5th international conference on knowledge-based intelligent information engineering systems and allied technologies (KES’01),
pp 298–302
Lu BL, Ito M (1997) Task decomposition based on class relations: a
modular neural network architecture for pattern classification. In:
Mira J, Moreno-Diaz R, Cabestany J (eds) Biological and artificial
computation: from neuroscience to technology, Lecture Notes in
Computer Science, vol 1240. Springer, Heidelberg, pp 330–339
Lu BL, Ito M (1999) Task decomposition and module combination
based on class relations: A modular neural network for patternclassification. IEEE Trans Neural Netw 10(5):1244–1256
Lu BL, Wang KA, Utiyama M, Isahara H (2004a) A part-versus-part
method for massively parallel training of support vector machines.
In: Proceedings of 2004 IEEE international joint conference onneural networks, pp 735–740
Lu BL, Shin J, Ichikawa M (2004b) Massively parallel classification of
single-trial EEG signals using a min–max-modular neural network.
IEEE Trans Biomed Eng 3(51):551–558
Luo J, Lu BL (2006) Gender recognition using a min–max modular
support vector machine with equal clustering. In: ISNN (2), pp
210–215
Nigam K, Lafferty J, McCallum A (1999) Using maximum entropy for
text classification. In: IJCAI-99 workshop on machine learning for
information filtering, pp 61–67
Sebastiani F (2002) Machine learning in automated text categorization.
ACM Comput Surv 34(1):1–47
Wang K, Zhao H, Lu BL (2005) Task decomposition using geometric
relation for min–max-modular svms. In: ISNN (1), pp 887–892
Yang Y (1999) An evaluation of statistical approaches to text categorization. Inf Retrieval 1(1/2):69–90
Yang Y, Chute CG (1994) An example-based mapping method for text
categorization and retrieval. ACM Trans Inf Syst 12(3):252–277
Yang Y, Liu X (1999) A re-examination of text categorization methods.
In: Hearst MA, Gey F, Tong R (eds) Proceedings of SIGIR-99,
22nd ACM international conference on research and development
in information retrieval, ACM Press, New York, USA, pp 42–49
Yang Y, Lu BL (2006) Prediction of protein subcellular multi-locations
with a min–max modular support vector machine. In: ISNN (2),
pp 667–673
Zhao H, Lu BL (2004) A modular k-nearest neighbor classification
method for massively parallel text categorization. In: International
symposium on computational and information sciences (CIS’04),
LNCS, vol 3314, pp 867–872
Zhao H, Lu BL (2006) A modular reduction method for k-nn algorithmwith self-recombination learning. In: ISNN (1), pp 537–544

123