# Distributed Learning over Massive XML Documents in ELM Feature Space

Authors: Xin Bi; Xiangguo Zhao; Guoren Wang; Zhen Zhang; Shuang Chen
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

With the exponentially increasing volume of XML data, centralized learning solutions are unable to meet the requirements of mining applications with massive training samples. In this paper, a solution to distributed learning over massive XML documents is proposed, which provides distributed conversion of XML documents into representation model in parallel based on MapReduce and a distributed learning component based on Extreme Learning Machine for mining tasks of classification or clustering. Within this framework, training samples are converted from raw XML datasets with better efficiency and information representation ability and taken to distributed learning algorithms in Extreme Learning Machine (ELM) feature space. Extensive experiments are conducted on massive XML documents datasets to verify the effectiveness and efficiency for both classification and clustering applications.


---

## Body

## 1. Introduction

Classification and clustering are two major problems of XML documents mining tasks. One of the most important parts of mining XML documents is to convert XML documents intorepresentation model. Most traditional representation models are designed for plain text mining applications, taking no account of structural information of XML documents. Vector Space Model (VSM) [1] is one of the most classic and popular representation models of plain text. Previous work proposed some approaches to solve the problem of considering both semantic and structural information for XML document classification, among which Structured Link Vector Model (SLVM) [2] extends VSM to generate a matrix by recording the attribute values of each element in an XML document. Reduced Structured Vector Space Model (RS-VSM) proposed in [3] achieves a higher performance due to its feature subset selection method. Different weights are assigned to different elements according to their priority and representation ability. Distribution based Structured Vector Model (DSVM) [4] further improves the calculation of traditional Term Frequency Inverse Document Frequency (TFIDF) values and takes two factors into consideration, namely, Among Classes Discrimination and Within Class Discrimination.Extreme Learning Machine (ELM) was proposed by Huang et al. in [5, 6] based on generalized single-hidden layer feedforward networks (SLFNs). With its variants [7–11], ELM achieves extremely fast learning capacity and good generalization capabilities usually in many application fields, including text classification [12], multimedia recognition [13–15], bioinformatics [16], and mobile objects [17]. Recently, Huang et al. in [18] pointed out that (1) the maximal margin property of Support Vector Machine (SVM) [19] and the minimal norm of weights theory of ELM are consistent; (2) from the standard optimization method point of view, ELM for classification and SVM are equivalent. Furthermore, it is proved in [20] that (1) ELM provides a unified learning platform with a widespread type of feature mappings; (2) ELM can be implemented in regression and multiclass classification applications in one formula directly. ELM can be linearly extended to SVMs [18] and SVMs can apply ELM kernel to get better performance due to itsuniversal approximation capability [10, 11, 21] andclassification capability [20].It is generally believed that all the ELM based algorithms consist of two major stages [22]: (1) random feature mapping and (2) output weights calculation. The first stage generating feature mapping randomly is the key concept in ELM theory which differs from other feature learning algorithms. In view of the good properties of the ELM feature mapping, most existing ELM based classification algorithms can be viewed assupervised learning in ELM feature space. While, in [23], theunsupervised learning in ELM feature space is studied, drawing the conclusion that the proposed ELM k-Means algorithm and ELM NMF (nonnegative matrix factorization) clustering can get better clustering results than traditional algorithms in original feature space.Recently, the volume of XML documents keeps explosively increasing in various kinds of web applications. Since the larger the training sample is, generally the better the learning model will be trained [24], it is a great challenge to implement distributed learning solutions to process massive XML datasets in parallel. MapReduce [25], introduced by Google to process parallelizable problems across huge datasets on clusters of computers, provides tremendous parallel computing power without concerns for the underlying implementation and technology. However, MapReduce framework requiresdistributed storage of the datasets andno communication among mappers or reducers, which brings challenges to (1) converting XML datasets into global representation model and (2) implementing learning algorithms in ELM feature space.To our best knowledge, this paper is thefirst to discuss massive XML documents mining problems. We present a distributed solution to XML representation and learning in ELM feature space. Since the raw XML datasets are stored on distributed file system, we propose algorithm DXRC to convert the XML documents into training samples in the form of XML representation model using a MapReduce job. With the converted training samples, we apply PELM [26] and POS-ELM [27] to realize supervised learning and propose a distributed k-Means in ELM feature space based on ELM k-Means proposed in [23]. The contributions can be summarized as follows.(1)
Adistributed representing algorithm is proposed to convert massive XML documents into XML representation model in parallel.
(2)
Existingdistributed supervised learning algorithms in ELM feature space are implemented to make comparison of massive XML documents classification performance, including PELM and POS-ELM.
(3)
Adistributed unsupervised learning algorithm is proposed based on ELM k-Means [23] to realize distributed clustering over massive XML documents inELM feature space.
(4)
Empirical and extensive comparison experiments are conducted on clusters to verify the performance of our solution.The remainder of this paper is structured as follows. Section2 introduces XML documents representation models and proposes a distributed converting algorithm to represent XML documents stored on distributed file system. Extreme Learning Machine feature mapping is presented in Section 3. Section 4 presents classification algorithms based on distributed ELMs and proposes a distributed clustering algorithm in ELM feature space based on MapReduce. Section 6 makes performance comparison among distributed classification algorithms and evaluates the proposed distributed clustering algorithm. Section 7 draws conclusions of this paper.


## 2. Distributed XML Representation

In this section, we first introduce representation model of XML documents and then propose a distributed converting algorithm, which is able to generate global feature vectors for all the XML documents stored on distributed file system.


### 2.1. XML Representation Model

For learning problems of texts, such as XML and plain documents, the first important task is to convert original documents into representation model. Vector Space Model (VSM) [1] is often used to represent plain text documents, which takes term occurrence statistics as feature vectors. However, representing an XML document in VSM directly will lose the structural information. Structured Link Vector Model (SLVM) is proposed in [2] based on VSM to represent semistructured documents, which contains both semantic and structural information. SLVM is defined as(1)
d
s
l
v
m
=
d
1
,
…
,
d
n
,where d
i is a feature vector of the ith XML element calculated as(2)
d
i
=
∑
i
‍
T
F
w
i
,
d
o
c
.
e
j
×
ɛ
j
I
D
F
w
i
,where w
i is the ith term and ɛ
j is a unit vector corresponding to the element e
j.In SLVM, eachd
s
l
v
m is a feature matrix R
n
×
m, which is viewed as an array of VSMs. d
i consists of the feature terms corresponding to the same XML element, which is an m-dimensional feature vector in each element unit.Based on SLVM, in [3], we proposed Reduced Structured Vector Space Model (RS-VSM), which not only inherits the advantages of representing structural information of SVLM, but also achieves a better performance due to the feature subset selection based on information gain. We also proposed Distribution Based Structured Vector Model (DSVM) in [4] to further strengthen the ability of representation. Two improved interact factors were designed, including Among Classes Discrimination (ACD) and Within Class Discrimination (WCD). Revised IDF was also introduced to indicate the importance of a feature term in other classes more precisely.d
u
i
j
k is the kth term feature described as(3)
d
u
i
j
k
=
∑
j
=
1
m
‍
T
F
w
k
,
d
o
c
.
e
j
·
ɛ
j
·
I
D
F
e
x
w
k
,
c
·
ρ
C
D
,where m is the number of elements in document d
o
c, d
o
c
.
e
j is the jth element e
j of d
o
c, and ɛ
j, which is the unit vector of d
o
c
.
e
j in SLVM, is now the dot product of s-dimensional unit vector and s-dimensional weight vector. I
D
F
e
x
(
w
i
,
c
) is the revised IDF. The factor ρ
C
D is the distribution modifying factor, which equals the reciprocal of arithmetic product of WCD and ACD. The detailed calculation of d
u
i
j
k can be found in [4].


### 2.2. Distributed Converting Algorithm

In this section, we propose a distributed converting algorithm, named Distributed XML Representation Converting (DXRC), to calculate TFIDF [28] values of DSVM based on MapReduce. Since the volume of XML documents is so large that the representation model cannot be generated on a single machine, DXRC realizes the representation of XML documents in the form of DSVM in parallel. The map function and reduce function of DXRC are presented as Algorithms 1 and 2, respectively.Algorithm 1:Mapper of DXRC.
Input: 〈docID, content〉
Output: 〈term, 〈docID, element, times, sum〉
〉
(1) Initiate HashMap mapEle;
(2)foreach  e
l
e
m
e
n
t
∈
c
o
n
t
e
n
t  do
(3)  Initiate sum = 0;
(4)  Initiate HashMap mapEleTF;
(5)foreach  t
e
r
m
∈
e
l
e
m
e
n
t  do
(6)    sum++;
(7)if  m
a
p
E
l
e
T
F
.
c
o
n
t
a
i
n
s
K
e
y
(
t
e
r
m
)  then
(8)     mapEleTF.put(term, mapEleTF.get(term) + 1);
(9)else
(10)     mapEleTF.put(term, 1);
(11)  mapEle.put(element, mapEleTF);
(12)foreach  i
t
r
E
l
e
∈
m
a
p
E
l
e  do
(13)  element = itrEle.getKey();
(14)foreach  i
t
r
E
l
e
T
F
∈
i
t
r
E
l
e
.
g
e
t
V
a
l
u
e
(
)  do
(15)    term = itrEleTF.getKey();
(16)    times = itrEleTF.getValue();
(17)    emit(term,〈docID, element, times, sum〉);Algorithm 2:Reducer of DXRC.
Input: 〈term, list(〈docID, element, times, sum〉
)
〉
Output: training samples matrix in the form of 〈position, tfidf〉
(1) Initiate HashMap mapDocEleTF;
(2) Initiate HashMap mapTDocs;
(3)N = DistributedCache.get(“totalDocsNum”);
(4) weights = DistributedCache.get(“elementWeightsVector”);
(5)foreach  i
t
r
∈
l
i
s
t  do
(6)  weightedDocEleTF = weights[docId, element]  * itr.times/itr.sum;
(7)  mapDocEleTF.put(〈docId, element〉, weightedDocEleTF);
(8)if  m
a
p
T
D
o
c
s
.
c
o
n
t
a
i
n
s
K
e
y
(
d
o
c
I
d
)  then
(9)    newTimes = mapTF.get(docId) + irt.getValue().times;
(10)    mapTDocs.put(docID, newTimes);
(11)else
(12)    mapTDocs.put(docID, itr.getValue().times);
(13) docsNumber = mapTDocs.size();
(14) idf =log
⁡
(mapTDocsSize/
N
);
(15)foreach  i
t
r
D
o
c
E
l
e
T
F
∈
m
a
p
D
o
c
E
l
e
T
F  do
(16)  position = itrDocEleTF.getKey();
(17)  tfidf = itrDocEleTF.getValue()× idf;
(18)  emit(position, tfidf);The map function in Algorithm1 accepts key-value pairs and the MapReduce job context as input. The key of key-value pairs is the XML document ID and the value is the corresponding XML document content. A HashMap m
a
p
E
l
e (Line 1) is used to cache all the elements of one XML document (Lines 2–11), using element name as key and another HashMap m
a
p
E
l
e
T
F (Line 4) as value. The m
a
p
E
l
e
T
F caches the TF values of all the words in one element (Lines 5–10). That is, for each XML document, the numbers of m
a
p
E
l
e items and XML elements are the same; for each element, there are as many items in m
a
p
E
l
e
T
F as there are distinct words in this element. Each item in m
a
p
E
l
e and m
a
p
E
l
e will be emitted as output in the form of 〈
t
e
r
m
,
〈
d
o
c
I
D
,
e
l
e
m
e
n
t
,
t
i
m
e
s
,
s
u
m
〉
〉 (Lines 12–17).After the〈
t
e
r
m
,
〈
d
o
c
I
D
,
e
l
e
m
e
n
t
,
t
i
m
e
s
,
s
u
m
〉
〉 pairs are emitted by map function, all the key-value pairs with the same key, which are also the key-value pairs of the same word in XML documents, are combined and passed to the samereduce function in Algorithm 2 as input. For each key-value pair processed by reduce function, two HashMaps m
a
p
D
o
c
E
l
e
T
F (Line 1) and m
a
p
T
D
o
c
s (Line 2) are initiated. The HashMap m
a
p
D
o
c
E
l
e
T
F is to cache the t
f values of a word in each element in the corresponding XML document and m
a
p
T
D
o
c
s is to cache the number of documents containing this word. The total number of documents N (Line 3) and the vector w
e
i
g
h
t
s (Line 4), which indicates the weights of all the elements in each XML document, are obtained through distributed cache defined in MapReduce job configuration. Since reduce now has all the t
f values grouped by XML elements along with their weights, weighted t
f values (Line 6) and the number of documents containing each word are calculated and cached in m
a
p
D
o
c
E
l
e
T
F and m
a
p
T
D
o
c
s, respectively (Lines 5–12). Then the i
d
f value can be calculated (Line 14) and multiplied by each item in m
a
p
D
o
c
E
l
e
T
F. The output of reduce is the 〈
p
o
s
i
t
i
o
n
,
t
f
i
d
f
〉 pairs, of which p
o
s
i
t
i
o
n is 〈
d
o
c
I
D
,
e
l
e
m
e
n
t
〉 indicating the index of DSVM matrix and t
f
i
d
f is the value of the matrix. Finally, the XML representation DSVM can be built by this matrix and factor ρ
C
D, uploaded onto distributed file system, and used as the input of the training model.


## 2.1. XML Representation Model

For learning problems of texts, such as XML and plain documents, the first important task is to convert original documents into representation model. Vector Space Model (VSM) [1] is often used to represent plain text documents, which takes term occurrence statistics as feature vectors. However, representing an XML document in VSM directly will lose the structural information. Structured Link Vector Model (SLVM) is proposed in [2] based on VSM to represent semistructured documents, which contains both semantic and structural information. SLVM is defined as(1)
d
s
l
v
m
=
d
1
,
…
,
d
n
,where d
i is a feature vector of the ith XML element calculated as(2)
d
i
=
∑
i
‍
T
F
w
i
,
d
o
c
.
e
j
×
ɛ
j
I
D
F
w
i
,where w
i is the ith term and ɛ
j is a unit vector corresponding to the element e
j.In SLVM, eachd
s
l
v
m is a feature matrix R
n
×
m, which is viewed as an array of VSMs. d
i consists of the feature terms corresponding to the same XML element, which is an m-dimensional feature vector in each element unit.Based on SLVM, in [3], we proposed Reduced Structured Vector Space Model (RS-VSM), which not only inherits the advantages of representing structural information of SVLM, but also achieves a better performance due to the feature subset selection based on information gain. We also proposed Distribution Based Structured Vector Model (DSVM) in [4] to further strengthen the ability of representation. Two improved interact factors were designed, including Among Classes Discrimination (ACD) and Within Class Discrimination (WCD). Revised IDF was also introduced to indicate the importance of a feature term in other classes more precisely.d
u
i
j
k is the kth term feature described as(3)
d
u
i
j
k
=
∑
j
=
1
m
‍
T
F
w
k
,
d
o
c
.
e
j
·
ɛ
j
·
I
D
F
e
x
w
k
,
c
·
ρ
C
D
,where m is the number of elements in document d
o
c, d
o
c
.
e
j is the jth element e
j of d
o
c, and ɛ
j, which is the unit vector of d
o
c
.
e
j in SLVM, is now the dot product of s-dimensional unit vector and s-dimensional weight vector. I
D
F
e
x
(
w
i
,
c
) is the revised IDF. The factor ρ
C
D is the distribution modifying factor, which equals the reciprocal of arithmetic product of WCD and ACD. The detailed calculation of d
u
i
j
k can be found in [4].


## 2.2. Distributed Converting Algorithm

In this section, we propose a distributed converting algorithm, named Distributed XML Representation Converting (DXRC), to calculate TFIDF [28] values of DSVM based on MapReduce. Since the volume of XML documents is so large that the representation model cannot be generated on a single machine, DXRC realizes the representation of XML documents in the form of DSVM in parallel. The map function and reduce function of DXRC are presented as Algorithms 1 and 2, respectively.Algorithm 1:Mapper of DXRC.
Input: 〈docID, content〉
Output: 〈term, 〈docID, element, times, sum〉
〉
(1) Initiate HashMap mapEle;
(2)foreach  e
l
e
m
e
n
t
∈
c
o
n
t
e
n
t  do
(3)  Initiate sum = 0;
(4)  Initiate HashMap mapEleTF;
(5)foreach  t
e
r
m
∈
e
l
e
m
e
n
t  do
(6)    sum++;
(7)if  m
a
p
E
l
e
T
F
.
c
o
n
t
a
i
n
s
K
e
y
(
t
e
r
m
)  then
(8)     mapEleTF.put(term, mapEleTF.get(term) + 1);
(9)else
(10)     mapEleTF.put(term, 1);
(11)  mapEle.put(element, mapEleTF);
(12)foreach  i
t
r
E
l
e
∈
m
a
p
E
l
e  do
(13)  element = itrEle.getKey();
(14)foreach  i
t
r
E
l
e
T
F
∈
i
t
r
E
l
e
.
g
e
t
V
a
l
u
e
(
)  do
(15)    term = itrEleTF.getKey();
(16)    times = itrEleTF.getValue();
(17)    emit(term,〈docID, element, times, sum〉);Algorithm 2:Reducer of DXRC.
Input: 〈term, list(〈docID, element, times, sum〉
)
〉
Output: training samples matrix in the form of 〈position, tfidf〉
(1) Initiate HashMap mapDocEleTF;
(2) Initiate HashMap mapTDocs;
(3)N = DistributedCache.get(“totalDocsNum”);
(4) weights = DistributedCache.get(“elementWeightsVector”);
(5)foreach  i
t
r
∈
l
i
s
t  do
(6)  weightedDocEleTF = weights[docId, element]  * itr.times/itr.sum;
(7)  mapDocEleTF.put(〈docId, element〉, weightedDocEleTF);
(8)if  m
a
p
T
D
o
c
s
.
c
o
n
t
a
i
n
s
K
e
y
(
d
o
c
I
d
)  then
(9)    newTimes = mapTF.get(docId) + irt.getValue().times;
(10)    mapTDocs.put(docID, newTimes);
(11)else
(12)    mapTDocs.put(docID, itr.getValue().times);
(13) docsNumber = mapTDocs.size();
(14) idf =log
⁡
(mapTDocsSize/
N
);
(15)foreach  i
t
r
D
o
c
E
l
e
T
F
∈
m
a
p
D
o
c
E
l
e
T
F  do
(16)  position = itrDocEleTF.getKey();
(17)  tfidf = itrDocEleTF.getValue()× idf;
(18)  emit(position, tfidf);The map function in Algorithm1 accepts key-value pairs and the MapReduce job context as input. The key of key-value pairs is the XML document ID and the value is the corresponding XML document content. A HashMap m
a
p
E
l
e (Line 1) is used to cache all the elements of one XML document (Lines 2–11), using element name as key and another HashMap m
a
p
E
l
e
T
F (Line 4) as value. The m
a
p
E
l
e
T
F caches the TF values of all the words in one element (Lines 5–10). That is, for each XML document, the numbers of m
a
p
E
l
e items and XML elements are the same; for each element, there are as many items in m
a
p
E
l
e
T
F as there are distinct words in this element. Each item in m
a
p
E
l
e and m
a
p
E
l
e will be emitted as output in the form of 〈
t
e
r
m
,
〈
d
o
c
I
D
,
e
l
e
m
e
n
t
,
t
i
m
e
s
,
s
u
m
〉
〉 (Lines 12–17).After the〈
t
e
r
m
,
〈
d
o
c
I
D
,
e
l
e
m
e
n
t
,
t
i
m
e
s
,
s
u
m
〉
〉 pairs are emitted by map function, all the key-value pairs with the same key, which are also the key-value pairs of the same word in XML documents, are combined and passed to the samereduce function in Algorithm 2 as input. For each key-value pair processed by reduce function, two HashMaps m
a
p
D
o
c
E
l
e
T
F (Line 1) and m
a
p
T
D
o
c
s (Line 2) are initiated. The HashMap m
a
p
D
o
c
E
l
e
T
F is to cache the t
f values of a word in each element in the corresponding XML document and m
a
p
T
D
o
c
s is to cache the number of documents containing this word. The total number of documents N (Line 3) and the vector w
e
i
g
h
t
s (Line 4), which indicates the weights of all the elements in each XML document, are obtained through distributed cache defined in MapReduce job configuration. Since reduce now has all the t
f values grouped by XML elements along with their weights, weighted t
f values (Line 6) and the number of documents containing each word are calculated and cached in m
a
p
D
o
c
E
l
e
T
F and m
a
p
T
D
o
c
s, respectively (Lines 5–12). Then the i
d
f value can be calculated (Line 14) and multiplied by each item in m
a
p
D
o
c
E
l
e
T
F. The output of reduce is the 〈
p
o
s
i
t
i
o
n
,
t
f
i
d
f
〉 pairs, of which p
o
s
i
t
i
o
n is 〈
d
o
c
I
D
,
e
l
e
m
e
n
t
〉 indicating the index of DSVM matrix and t
f
i
d
f is the value of the matrix. Finally, the XML representation DSVM can be built by this matrix and factor ρ
C
D, uploaded onto distributed file system, and used as the input of the training model.


## 3. ELM Feature Mapping

Extreme Learning Machine (ELM) randomly generates parameters of the single-hidden layer feedforward networks without iteratively tuning to gain extremely fast learning speed. The output weights can be calculated by matrix multiplication after the training samples are mapped intoELM feature space.GivenN arbitrary samples (
x
i
,
t
i
)
∈
R
n
×
m, ELM is modeled as(4)
∑
i
=
1
L
‍
β
i
G
w
i
,
b
i
,
x
=
β
h
x
,where L is the number of hidden layer nodes, β
i is the output weight from the ith hidden node to the output node, w
i
=
[
w
i
1
,
w
i
2
,
…
,
w
i
n
]
T is the input weight vector, and b
i is the bias of ith hidden node. G
(
x
) is the activation function to generate mapping neurons, which can be any nonlinear piecewise continuous functions [22], including Sigmoid function (5) and Gaussian function (6), as follows:(5)
G
S
i
g
m
o
i
d
w
,
b
,
x
=
1
1
+
e
x
p
-
w
T
x
+
b
,
(6)
G
G
a
u
s
s
i
a
n
w
,
b
,
x
=
e
x
p
-
b
x
-
a
.Figure1 shows the structure of ELM with multiple output nodes and the feature mapping process. The three layers of ELM network are input layer, hidden layer, and output layer. The n input nodes correspond to the n-dimensional data space of original samples, while L hidden nodes correspond to the L-dimensionalELM feature space. With the m-dimensional output space, the decision function outputs the class label of the samples.Figure 1
ELM structure and ELM feature mapping.TheELM feature mapping denoted by H is calculated as(7)
H
=
h
x
1
⋮
h
x
N
=
G
w
1
,
b
1
,
x
1
⋯
G
w
L
,
b
L
,
x
1
⋮
⋯
⋮
G
w
1
,
b
1
,
x
N
⋯
G
w
L
,
b
L
,
x
N
N
×
L
.


## 4. Distributed Classification in ELM Feature Space

In this section, we introduce the learning procedure of classification problems in ELM feature space and distributed implementations based on two existing representative distributed ELM algorithms, which are PELM [26] and POS-ELM [27].


### 4.1. Supervised Learning in ELM Feature Space

Most of the existing ELM algorithms aim at supervised learning, that is, classification and regression. In supervised learning applications, ELM is to minimize the training error and the norm of the output weights [5, 6], that is,(8)
Minimize:
H
β
-
T
2
,
β
,where T
=
t
1
T
,
…
,
t
L
T
m
×
L
T is the vector of class labels.The matrixβ is the output weight, which is calculated as(9)
β
=
H
†
T
,where H
† is the Moore-Penrose inverse of H.ELM for classification is presented as Algorithm3.Algorithm 3:Extreme Learning Machine for classification.
(1)for  i
=
1 to L  do
(2)Randomly assign input weight w
i and bias b
i;
(3) Calculate ELM feature spaceH;
(4) Calculateβ
=
H
†
T;The output weight of ELM can also be calculated as(10)
β
=
H
T
I
C
+
H
H
T
-
1
T
,where, according to the ridge regression theory [29], the diagonal of a symmetric matrix can be incremented by a biasing constant 1
/
C to gain better stability and generalization performance [18].For the case in which the number of training samples is much larger than the dimensionality of the feature space, considering the computation cost, the output weight calculation equation can be rewritten as(11)
β
=
I
C
+
H
T
H
-
1
H
T
T
.


### 4.2. Distributed Implementations

Some existing works have introduced distributed implementations of various ELM algorithms. The original ELM was parallelized by PELM in [26]; Online Sequential ELM (OS-ELM) was implemented on MapReduce as POS-ELM in [27].


#### 4.2.1. Parallel ELM

In the original ELM algorithm, in the case that the number of training samples is much larger than the dimensionality of ELM feature space andH
T
H is nonsingular, the major cost is the calculation of Moore-Penrose generalized inverse of matrix H, where the orthogonal projection method is used as (11). Thus the matrix multiplication U
=
H
T
H and V
=
H
T
T can be calculated by a MapReduce job. In map function, each term of U and V can be expressed as follows [26]:(12)
U
i
j
=
∑
k
=
1
N
‍
H
k
i
×
H
k
j
,
V
i
j
=
∑
k
=
1
N
‍
H
k
i
×
T
k
j
.In reduce function, all the intermediate results are merged and added up according to the corresponding elements of the result matrix. Since the training input matrixX is stored by sample on different machines, the calculation can be parallelized and executed by the MapReduce job. The calculation procedure is demonstrated as Figure 2.Figure 2
Parallel ELM.


#### 4.2.2. Parallel Online Sequential ELM

The basic idea of Parallel Online Sequential ELM (POS-ELM) is to calculateH
1
,
…
,
H
B in parallel. By taking advantages of the calculation of partial ELM feature matrix H
i with a chunk of training data of OS-ELM, POS-ELM calculates its H
i with its own data chunk in the map phase on each machine. The reduce function collects all the H
i and calculates β
k
+
1 as(13)
β
k
+
1
=
β
k
+
P
k
+
1
H
k
+
1
T
T
k
+
1
-
H
k
+
1
β
k
,where(14)
P
k
+
1
=
P
k
-
P
k
H
k
+
1
T
I
+
H
k
+
1
P
k
H
k
+
1
T
-
1
H
k
+
1
P
k
.The calculation procedure of POS-ELM is shown in Figure3.Figure 3
Parallel Online Sequential ELM.


## 4.1. Supervised Learning in ELM Feature Space

Most of the existing ELM algorithms aim at supervised learning, that is, classification and regression. In supervised learning applications, ELM is to minimize the training error and the norm of the output weights [5, 6], that is,(8)
Minimize:
H
β
-
T
2
,
β
,where T
=
t
1
T
,
…
,
t
L
T
m
×
L
T is the vector of class labels.The matrixβ is the output weight, which is calculated as(9)
β
=
H
†
T
,where H
† is the Moore-Penrose inverse of H.ELM for classification is presented as Algorithm3.Algorithm 3:Extreme Learning Machine for classification.
(1)for  i
=
1 to L  do
(2)Randomly assign input weight w
i and bias b
i;
(3) Calculate ELM feature spaceH;
(4) Calculateβ
=
H
†
T;The output weight of ELM can also be calculated as(10)
β
=
H
T
I
C
+
H
H
T
-
1
T
,where, according to the ridge regression theory [29], the diagonal of a symmetric matrix can be incremented by a biasing constant 1
/
C to gain better stability and generalization performance [18].For the case in which the number of training samples is much larger than the dimensionality of the feature space, considering the computation cost, the output weight calculation equation can be rewritten as(11)
β
=
I
C
+
H
T
H
-
1
H
T
T
.


## 4.2. Distributed Implementations

Some existing works have introduced distributed implementations of various ELM algorithms. The original ELM was parallelized by PELM in [26]; Online Sequential ELM (OS-ELM) was implemented on MapReduce as POS-ELM in [27].


### 4.2.1. Parallel ELM

In the original ELM algorithm, in the case that the number of training samples is much larger than the dimensionality of ELM feature space andH
T
H is nonsingular, the major cost is the calculation of Moore-Penrose generalized inverse of matrix H, where the orthogonal projection method is used as (11). Thus the matrix multiplication U
=
H
T
H and V
=
H
T
T can be calculated by a MapReduce job. In map function, each term of U and V can be expressed as follows [26]:(12)
U
i
j
=
∑
k
=
1
N
‍
H
k
i
×
H
k
j
,
V
i
j
=
∑
k
=
1
N
‍
H
k
i
×
T
k
j
.In reduce function, all the intermediate results are merged and added up according to the corresponding elements of the result matrix. Since the training input matrixX is stored by sample on different machines, the calculation can be parallelized and executed by the MapReduce job. The calculation procedure is demonstrated as Figure 2.Figure 2
Parallel ELM.


### 4.2.2. Parallel Online Sequential ELM

The basic idea of Parallel Online Sequential ELM (POS-ELM) is to calculateH
1
,
…
,
H
B in parallel. By taking advantages of the calculation of partial ELM feature matrix H
i with a chunk of training data of OS-ELM, POS-ELM calculates its H
i with its own data chunk in the map phase on each machine. The reduce function collects all the H
i and calculates β
k
+
1 as(13)
β
k
+
1
=
β
k
+
P
k
+
1
H
k
+
1
T
T
k
+
1
-
H
k
+
1
β
k
,where(14)
P
k
+
1
=
P
k
-
P
k
H
k
+
1
T
I
+
H
k
+
1
P
k
H
k
+
1
T
-
1
H
k
+
1
P
k
.The calculation procedure of POS-ELM is shown in Figure3.Figure 3
Parallel Online Sequential ELM.


## 4.2.1. Parallel ELM

In the original ELM algorithm, in the case that the number of training samples is much larger than the dimensionality of ELM feature space andH
T
H is nonsingular, the major cost is the calculation of Moore-Penrose generalized inverse of matrix H, where the orthogonal projection method is used as (11). Thus the matrix multiplication U
=
H
T
H and V
=
H
T
T can be calculated by a MapReduce job. In map function, each term of U and V can be expressed as follows [26]:(12)
U
i
j
=
∑
k
=
1
N
‍
H
k
i
×
H
k
j
,
V
i
j
=
∑
k
=
1
N
‍
H
k
i
×
T
k
j
.In reduce function, all the intermediate results are merged and added up according to the corresponding elements of the result matrix. Since the training input matrixX is stored by sample on different machines, the calculation can be parallelized and executed by the MapReduce job. The calculation procedure is demonstrated as Figure 2.Figure 2
Parallel ELM.


## 4.2.2. Parallel Online Sequential ELM

The basic idea of Parallel Online Sequential ELM (POS-ELM) is to calculateH
1
,
…
,
H
B in parallel. By taking advantages of the calculation of partial ELM feature matrix H
i with a chunk of training data of OS-ELM, POS-ELM calculates its H
i with its own data chunk in the map phase on each machine. The reduce function collects all the H
i and calculates β
k
+
1 as(13)
β
k
+
1
=
β
k
+
P
k
+
1
H
k
+
1
T
T
k
+
1
-
H
k
+
1
β
k
,where(14)
P
k
+
1
=
P
k
-
P
k
H
k
+
1
T
I
+
H
k
+
1
P
k
H
k
+
1
T
-
1
H
k
+
1
P
k
.The calculation procedure of POS-ELM is shown in Figure3.Figure 3
Parallel Online Sequential ELM.


## 5. Distributed Clustering in ELM Feature Space

In this section, in order to improve the efficiency of clustering massive XML datasets, we also propose a parallel implementation of ELMk-Means algorithm, named Distributed ELM k-Means (DEK) in this section.


### 5.1. Unsupervised Learning in ELM Feature Space

It is believed that transforming nonlinear data into some high dimensional feature space increases the probability of the linear separability. However, many Mercer kernel based clustering algorithms are usually not efficient for computation, since the feature mapping is always implicit and cannot be guaranteed to satisfy the universal approximation condition. Thus, [23] holds that explicit feature mapping like ELM feature mapping is more appropriate.Generally,k-Means algorithm in ELM feature space, as ELM k-Means for short, has two major steps: (1) transform the original data into ELM feature space and (2) implement traditional clustering algorithm directly. Clustering in the ELM feature space is much more convenient than kernel based algorithms.


### 5.2. Distributed ELMk-Means

For the applications of massive XML documents clustering, implementation of unsupervised learning methods to MapReduce is a key part of the problem. Since ELM feature mapping is extremely fast with good generalization performance and universal approximation ability, in this section, we propose Distributed ELMk-Means (DEK) based on ELM k-Means [23].In DEK algorithm, the training samples of XML documents are distributedly stored on distributed file system. Each(
x
i
,
T
i
) represents a training sample x
i
in ELM feature space with its corresponding class label T
i. With a set of initiated k cluster centroids, in themap phase, the distances between each centroid and each training sample stored on its own site are calculated. Then the sample is assigned to the centroid with the shortest distance. In thereduce phase, all the samples assigned to the same centroid are collected in the same reducer. Then a new centroid of each cluster is calculated, with which the set of k cluster centroids are updated. That is, a round of MapReduce job updates the set of k cluster centroids once. In the next round of MapReduce job, the updated set of centroids is updated again and this procedure will be repeated until convergence or up to maximum number of iterations (Figure 4).Figure 4
Distributed ELMk-Means.Algorithm4 presents the map function of DEK. For each sample stored on this mapper (Line 1), the distance between the sample and each cluster centroids is calculated (Lines 2, 3). Then each sample is assigned to the cluster whose centroid is the nearest to this sample (Line 4). The intermediate key-value pair is emitted in the form of 〈
c
m
a
x
,
x
i
〉 (Line 5), in which x
i is the specific sample and c
m
a
x is the assigned cluster of x
i.Algorithm 4:Mapper of DEK.
Input: Training samples X, k centroids C
Output: 〈centroid c
max
⁡, sample x
i
〉
(1)foreach  x
i
∈
X  do
(2)foreach  c
j
∈
C  do
(3)Calculate distance d
i
j between x
i and c
j;
(4)  Assignx
i to the cluster c
max
⁡ with max
j
⁡
(
d
i
j
);
(5)  Emit〈
c
max
⁡
,
x
i
〉;Algorithm5 presents the reduce function of DEK. We add up the sum distance in Euclidean space of all the samples x
i in l
i
s
t
(
x
) (Lines 1, 2) and then calculate the mean value to represent the new version of the centroid c
j
u
p
d
a
t
e
d of cluster c
j (Line 3). When all the k cluster centroids are updated in this MapReduce job, if this version of centroids is the same as the older one, or if the maximum number of iterations is reached, DEK holds that the clustering job is done; otherwise, DEK continues to the next iteration of MapReduce job until convergence.Algorithm 5:Reducer of DEK.
Input: 〈centroid c
j, samples list(
x
)
〉
Output: Updated set of centroids C
updated
(1)foreach  x
i
∈ list(x)  do
(2)  Addx
i to squared sum S;
(3) Calculatec
j
updated of cluster c
j as c
j
updated
=
S
/
list
(
x
)
.
l
e
n
g
t
h;


## 5.1. Unsupervised Learning in ELM Feature Space

It is believed that transforming nonlinear data into some high dimensional feature space increases the probability of the linear separability. However, many Mercer kernel based clustering algorithms are usually not efficient for computation, since the feature mapping is always implicit and cannot be guaranteed to satisfy the universal approximation condition. Thus, [23] holds that explicit feature mapping like ELM feature mapping is more appropriate.Generally,k-Means algorithm in ELM feature space, as ELM k-Means for short, has two major steps: (1) transform the original data into ELM feature space and (2) implement traditional clustering algorithm directly. Clustering in the ELM feature space is much more convenient than kernel based algorithms.


## 5.2. Distributed ELMk-Means

For the applications of massive XML documents clustering, implementation of unsupervised learning methods to MapReduce is a key part of the problem. Since ELM feature mapping is extremely fast with good generalization performance and universal approximation ability, in this section, we propose Distributed ELMk-Means (DEK) based on ELM k-Means [23].In DEK algorithm, the training samples of XML documents are distributedly stored on distributed file system. Each(
x
i
,
T
i
) represents a training sample x
i
in ELM feature space with its corresponding class label T
i. With a set of initiated k cluster centroids, in themap phase, the distances between each centroid and each training sample stored on its own site are calculated. Then the sample is assigned to the centroid with the shortest distance. In thereduce phase, all the samples assigned to the same centroid are collected in the same reducer. Then a new centroid of each cluster is calculated, with which the set of k cluster centroids are updated. That is, a round of MapReduce job updates the set of k cluster centroids once. In the next round of MapReduce job, the updated set of centroids is updated again and this procedure will be repeated until convergence or up to maximum number of iterations (Figure 4).Figure 4
Distributed ELMk-Means.Algorithm4 presents the map function of DEK. For each sample stored on this mapper (Line 1), the distance between the sample and each cluster centroids is calculated (Lines 2, 3). Then each sample is assigned to the cluster whose centroid is the nearest to this sample (Line 4). The intermediate key-value pair is emitted in the form of 〈
c
m
a
x
,
x
i
〉 (Line 5), in which x
i is the specific sample and c
m
a
x is the assigned cluster of x
i.Algorithm 4:Mapper of DEK.
Input: Training samples X, k centroids C
Output: 〈centroid c
max
⁡, sample x
i
〉
(1)foreach  x
i
∈
X  do
(2)foreach  c
j
∈
C  do
(3)Calculate distance d
i
j between x
i and c
j;
(4)  Assignx
i to the cluster c
max
⁡ with max
j
⁡
(
d
i
j
);
(5)  Emit〈
c
max
⁡
,
x
i
〉;Algorithm5 presents the reduce function of DEK. We add up the sum distance in Euclidean space of all the samples x
i in l
i
s
t
(
x
) (Lines 1, 2) and then calculate the mean value to represent the new version of the centroid c
j
u
p
d
a
t
e
d of cluster c
j (Line 3). When all the k cluster centroids are updated in this MapReduce job, if this version of centroids is the same as the older one, or if the maximum number of iterations is reached, DEK holds that the clustering job is done; otherwise, DEK continues to the next iteration of MapReduce job until convergence.Algorithm 5:Reducer of DEK.
Input: 〈centroid c
j, samples list(
x
)
〉
Output: Updated set of centroids C
updated
(1)foreach  x
i
∈ list(x)  do
(2)  Addx
i to squared sum S;
(3) Calculatec
j
updated of cluster c
j as c
j
updated
=
S
/
list
(
x
)
.
l
e
n
g
t
h;


## 6. Performance Evaluation

All the experiments are conducted to compare the performance in the following aspects:(i)
scalability evaluation of proposed Distributed XML Representation Converting (DXRC),
(ii)
scalability comparison between PELM and POS-ELM in massive XML documents classification problem,
(iii)
supervised learning performance of PELM and POS-ELM in massive XML documents classification problem,
(iv)
scalability evaluation of proposed Distributed ELM k-Means (DEK),
(v)
unsupervised learning performance of DEK in massive XML documents clustering problem.


### 6.1. Experiments Setup

#### 6.1.1. Environment

All the experiments on distributed XML representation converting and distributed learning in ELM feature space are conducted on a Hadoop (Apache Hadoop,http://hadoop.apache.org/) cluster of nine machines, which consists of one master node and eight slave nodes. Each machine is equipped with an Intel Quad Core 2.66 GHZ CPU, 4 GB of memory, and CentOS 5.6 as operating system. All the computers are connected via a high speed Gigabit network. The MapReduce framework is configured with Hadoop version 0.20.2 and Java version 1.6.0_24.


#### 6.1.2. Datasets

Three datasets of XML documents are used as original datasets, which areWikipedia XML Corpus provided by INEX,IBM DeveloperWorks (http://www.ibm.com/developerworks/) articles, andABC News (http://abcnews.go.com/).Wikipedia XML Corpus is composed of around 96,000 XML documents classified into 21 classes. We also fetched RSS feeds of news and articles in the format of XML fromIBM DeveloperWorks andABC News official web sites. Each XML document of the RSS feeds is composed of elements of title, author, summary, publish information, and so forth. In order to compare the performance of the algorithms over different datasets, we choose the same numbers of XML documents out of all the three datasets, which are 6 classes and 500 documents in each class.


#### 6.1.3. Parameters

According to the universal approximation conditions and classification capability of ELM, a large number of hidden nodes guarantee that the data can be linearly separated [23], especially for the learning problems on high-dimensional training samples like XML documents. Thus, after a set of experiments for parameter setting, the only parameter of learning algorithms in ELM feature space, that is, the number of hidden nodes L, is set to 800.


#### 6.1.4. Evaluation Criteria

To clearly evaluate the performance, three sets of evaluation criteria are utilized.(1)
For scalability evaluation, we compare the criteria of speedup, sizeup, and scaleup.Speedup indicates the scalability when increasing the number of running machines, which is measured as(15)
S
p
e
e
d
u
p
m
=
r
u
n
n
i
n
g
t
i
m
e
o
n
1
m
a
c
h
i
n
e
r
u
n
n
i
n
g
t
i
m
e
o
n
m
m
a
c
h
i
n
e
s
.
Sizeup indicates the scalability when increasing the data size, which is measured as(16)
S
i
z
e
u
p
m
=
r
u
n
n
i
n
g
t
i
m
e
o
v
e
r
m
u
n
i
t
s
o
f
d
a
t
a
r
u
n
n
i
n
g
t
i
m
e
o
v
e
r
o
n
e
u
n
i
t
o
f
d
a
t
a
.
Scaleup is to measure the scalability of processing m-times larger data on an m-times larger cluster, which is calculated as(17)
S
c
a
l
e
u
p
m
=
r
u
n
n
i
n
g
t
i
m
e
o
v
e
r
o
n
e
u
n
i
t
o
f
d
a
t
a
o
n
o
n
e
m
a
c
h
i
n
e
r
u
n
n
i
n
g
t
i
m
e
o
v
e
r
m
u
n
i
t
s
o
f
d
a
t
a
o
n
m
m
a
c
h
i
n
e
s
.
(2)
For classification problems, accuracy, recall, andF-measure are used to evaluate the performance of supervised learning performance in ELM feature space.Accuracy indicates the overall ratio of correctly classified samples, which is measured as(18)
A
c
c
u
r
a
c
y
=
T
r
u
e
P
o
s
i
t
i
v
e
+
T
r
u
e
N
e
g
a
t
i
v
e
T
o
t
a
l
s
a
m
p
l
e
s
n
u
m
b
e
r
.
Recall is the ratio of the samples with a specific class label to the ones classified into this class, which is measured as(19)
R
e
c
a
l
l
=
T
r
u
e
P
o
s
i
t
i
v
e
T
r
u
e
P
o
s
i
t
i
v
e
+
F
a
l
s
e
.
F
-measure is to measure the overall performance considering both accuracy and recall, which is calculated as(20)
F
-
m
e
a
s
u
r
e
=
2
×
a
c
c
u
r
a
c
y
×
r
e
c
a
l
l
a
c
c
u
r
a
c
y
+
r
e
c
a
l
l
.
(3)
For clustering problems, since each sample in the datasets we used in our experiments is assigned with a class label, we treat this class label as the cluster label. Thus, the same evaluation criteria are used for clustering problems as for classification problems.


### 6.2. Evaluation Results

#### 6.2.1. Scalability of DXRC

The scalability of representation converting algorithm DXRC is first evaluated. Figure5(a) demonstrates the speedup of DXRC. As the number of the slave nodes varies from one to eight, the speedup tends to be approximately linear at first, but the growth slows down due to the increasing cost of network communications among more and more working machines. But, in general, DXRC gains good speedup. Figure 5(b) presents the sizeup of DXRC. The x-axis denotes the percentage against the whole datasets. That is, 1 is the full size of original dataset; 0.5 indicates half of the original dataset, in which the samples are randomly chosen. With a fixed number of slave machines, which is eight, the evaluation result shows good sizeup of DXRC. Since the scaleup in distributed implementation cannot stick to 1 in practice, in Figure 5(c), the scaleup of DXRC drops slowly when the number of slave nodes and the size of dataset increase, which indicates a good scaleup of DXRC.Figure 5
Scalability of DXRC.
(a)
Speedup
(b)
Sizeup
(c)
ScaleupNote that the representation ability and performance influence on XML documents classification of DSVM applied in DXRC can be found in our previous work [4].


#### 6.2.2. Scalability of Massive XML Classification in ELM Feature Space

With the training samples converted by algorithm DXRC, a classifier of massive XML documents can be trained based on MapRedcue. The speedup comparison between PELM and POS-ELM on three datasets is presented in Figure6.Figure 6
Comparison of speedup between PELM and POS-ELM.
(a)
Dataset Wiki
(b)
Dataset IBM
(c)
Dataset ABC NewsAlgorithm PELM, which implements original ELM on MapReduce, requires calculating the inverse of ELM feature space matrix, while PEO-ELM makes use of the idea of online sequential processing to realize parallel computation without communication and requires calculating output weightβ and the auxiliary matrix P iteratively in a single reducer. The centralized calculation reduces the scalability of both PELM and POS-ELM to some degree, especially for POS-ELM. Thus, the speedup of PELM is better than POS-ELM.Figure7 demonstrates the sizeup comparison between PELM and POS-ELM. From this figure, we find that the sizeup of PELM is better than POS-ELM on all the three datasets.Figure 7
Comparison of sizeup between PELM and POS-ELM.
(a)
Dataset Wiki
(b)
Dataset IBM
(c)
Dataset ABC NewsFor the scaleup comparison, Figure8 demonstrates that both PELM and POS-ELM have good scaleup performance, and PELM outperforms POS-ELM on each of the three datasets.Figure 8
Comparison of scaleup between PELM and POS-ELM.
(a)
Dataset Wiki
(b)
Dataset IBM
(c)
Dataset ABC NewsIn summary, both PELM and POS-ELM have good scalability for massive XML documents classification applications, but PELM has better scalability than POS-ELM.


#### 6.2.3. Performance of Massive XML Classification in ELM Feature Space

The parallel implementation of both PELM and POS-ELM does not invade the computation theory of original ELM and OS-ELM, respectively; that is, the classification performances of PELM and POS-ELM are nearly the same as their corresponding centralized algorithms, respectively. The classification results are shown in Table1.Table 1
Classification performance comparison between PELM and POS-ELM.
Datasets
PELM
POS-ELM
Accuracy
Recall
F-measure
Accuracy
Recall
F-measure
Wikipedia
0.7886
0.7563
0.7721
0.7923
0.7745
0.7833
IBM DeveloperWorks
0.7705
0.8145
0.7919
0.7711
0.7863
0.7891
ABC News
0.8681
0.8517
0.8598
0.8517
0.8335
0.8425From the table we can see that PELM slightly outperforms POS-ELM, because the iterative matrix operations of output weightβ in POS-ELM cause loss of calculation accuracy. However, for massive XML documents classification applications, since both the extraction and reduction of XML document features are complicated, both PELM and POS-ELM provide satisfactory classification performance.


#### 6.2.4. Scalability of Massive XML Clustering in ELM Feature Space

In this set of experiments, we evaluate the proposed distributed clustering algorithm in ELM feature space, that is, distributed ELMk-Means. In theory, the scalability of distributed k-Means in ELM feature space and in original feature space is the same, since the only difference is the feature space of the training samples, which has no influence on the computation complexity. Thus, we only present the scalability of DEK without comparison with distributed k-Means in original feature space.The scalability of DEK is evaluated on all the three datasets in terms of speedup in Figure9(a), sizeup in Figure 9(b), and scaleup in Figure 9(c). The experimental results all demonstrate good scalability of DEK for massive XML documents clustering applications.Figure 9
Scalability of DEK.
(a)
Speedup
(b)
Sizeup
(c)
Scaleup


#### 6.2.5. Performance of Massive XML Clustering in ELM Feature Space

Clustering performance comparison between distributed clustering in ELM feature space and clustering in original feature space is made for massive XML documents clustering applications in this set of experiments. Note that, since the manual relabeling of the massive XML dataset is infeasible, we only evaluate the clustering quality with the original number of classes, which is six. The comparison results on three different datasets are presented in Table2. It can be seen from the comparison results that DEK gets better clustering performance due to its ELM features mapping.Table 2
Clustering performance of DEK compared with parallelk-Means.
Dataset
Parallelk-Means
DEK
Accuracy
Recall
F-measure
Accuracy
Recall
F-measure
Wikipedia
0.7602
0.7426
0.7513
0.7737
0.7648
0.7692
IBM DeveloperWorks
0.7985
0.8268
0.8126
0.8124
0.8277
0.8200
ABC News
0.8351
0.8125
0.8201
0.8529
0.8192
0.8357


## 6.1. Experiments Setup

### 6.1.1. Environment

All the experiments on distributed XML representation converting and distributed learning in ELM feature space are conducted on a Hadoop (Apache Hadoop,http://hadoop.apache.org/) cluster of nine machines, which consists of one master node and eight slave nodes. Each machine is equipped with an Intel Quad Core 2.66 GHZ CPU, 4 GB of memory, and CentOS 5.6 as operating system. All the computers are connected via a high speed Gigabit network. The MapReduce framework is configured with Hadoop version 0.20.2 and Java version 1.6.0_24.


### 6.1.2. Datasets

Three datasets of XML documents are used as original datasets, which areWikipedia XML Corpus provided by INEX,IBM DeveloperWorks (http://www.ibm.com/developerworks/) articles, andABC News (http://abcnews.go.com/).Wikipedia XML Corpus is composed of around 96,000 XML documents classified into 21 classes. We also fetched RSS feeds of news and articles in the format of XML fromIBM DeveloperWorks andABC News official web sites. Each XML document of the RSS feeds is composed of elements of title, author, summary, publish information, and so forth. In order to compare the performance of the algorithms over different datasets, we choose the same numbers of XML documents out of all the three datasets, which are 6 classes and 500 documents in each class.


### 6.1.3. Parameters

According to the universal approximation conditions and classification capability of ELM, a large number of hidden nodes guarantee that the data can be linearly separated [23], especially for the learning problems on high-dimensional training samples like XML documents. Thus, after a set of experiments for parameter setting, the only parameter of learning algorithms in ELM feature space, that is, the number of hidden nodes L, is set to 800.


### 6.1.4. Evaluation Criteria

To clearly evaluate the performance, three sets of evaluation criteria are utilized.(1)
For scalability evaluation, we compare the criteria of speedup, sizeup, and scaleup.Speedup indicates the scalability when increasing the number of running machines, which is measured as(15)
S
p
e
e
d
u
p
m
=
r
u
n
n
i
n
g
t
i
m
e
o
n
1
m
a
c
h
i
n
e
r
u
n
n
i
n
g
t
i
m
e
o
n
m
m
a
c
h
i
n
e
s
.
Sizeup indicates the scalability when increasing the data size, which is measured as(16)
S
i
z
e
u
p
m
=
r
u
n
n
i
n
g
t
i
m
e
o
v
e
r
m
u
n
i
t
s
o
f
d
a
t
a
r
u
n
n
i
n
g
t
i
m
e
o
v
e
r
o
n
e
u
n
i
t
o
f
d
a
t
a
.
Scaleup is to measure the scalability of processing m-times larger data on an m-times larger cluster, which is calculated as(17)
S
c
a
l
e
u
p
m
=
r
u
n
n
i
n
g
t
i
m
e
o
v
e
r
o
n
e
u
n
i
t
o
f
d
a
t
a
o
n
o
n
e
m
a
c
h
i
n
e
r
u
n
n
i
n
g
t
i
m
e
o
v
e
r
m
u
n
i
t
s
o
f
d
a
t
a
o
n
m
m
a
c
h
i
n
e
s
.
(2)
For classification problems, accuracy, recall, andF-measure are used to evaluate the performance of supervised learning performance in ELM feature space.Accuracy indicates the overall ratio of correctly classified samples, which is measured as(18)
A
c
c
u
r
a
c
y
=
T
r
u
e
P
o
s
i
t
i
v
e
+
T
r
u
e
N
e
g
a
t
i
v
e
T
o
t
a
l
s
a
m
p
l
e
s
n
u
m
b
e
r
.
Recall is the ratio of the samples with a specific class label to the ones classified into this class, which is measured as(19)
R
e
c
a
l
l
=
T
r
u
e
P
o
s
i
t
i
v
e
T
r
u
e
P
o
s
i
t
i
v
e
+
F
a
l
s
e
.
F
-measure is to measure the overall performance considering both accuracy and recall, which is calculated as(20)
F
-
m
e
a
s
u
r
e
=
2
×
a
c
c
u
r
a
c
y
×
r
e
c
a
l
l
a
c
c
u
r
a
c
y
+
r
e
c
a
l
l
.
(3)
For clustering problems, since each sample in the datasets we used in our experiments is assigned with a class label, we treat this class label as the cluster label. Thus, the same evaluation criteria are used for clustering problems as for classification problems.


## 6.1.1. Environment

All the experiments on distributed XML representation converting and distributed learning in ELM feature space are conducted on a Hadoop (Apache Hadoop,http://hadoop.apache.org/) cluster of nine machines, which consists of one master node and eight slave nodes. Each machine is equipped with an Intel Quad Core 2.66 GHZ CPU, 4 GB of memory, and CentOS 5.6 as operating system. All the computers are connected via a high speed Gigabit network. The MapReduce framework is configured with Hadoop version 0.20.2 and Java version 1.6.0_24.


## 6.1.2. Datasets

Three datasets of XML documents are used as original datasets, which areWikipedia XML Corpus provided by INEX,IBM DeveloperWorks (http://www.ibm.com/developerworks/) articles, andABC News (http://abcnews.go.com/).Wikipedia XML Corpus is composed of around 96,000 XML documents classified into 21 classes. We also fetched RSS feeds of news and articles in the format of XML fromIBM DeveloperWorks andABC News official web sites. Each XML document of the RSS feeds is composed of elements of title, author, summary, publish information, and so forth. In order to compare the performance of the algorithms over different datasets, we choose the same numbers of XML documents out of all the three datasets, which are 6 classes and 500 documents in each class.


## 6.1.3. Parameters

According to the universal approximation conditions and classification capability of ELM, a large number of hidden nodes guarantee that the data can be linearly separated [23], especially for the learning problems on high-dimensional training samples like XML documents. Thus, after a set of experiments for parameter setting, the only parameter of learning algorithms in ELM feature space, that is, the number of hidden nodes L, is set to 800.


## 6.1.4. Evaluation Criteria

To clearly evaluate the performance, three sets of evaluation criteria are utilized.(1)
For scalability evaluation, we compare the criteria of speedup, sizeup, and scaleup.Speedup indicates the scalability when increasing the number of running machines, which is measured as(15)
S
p
e
e
d
u
p
m
=
r
u
n
n
i
n
g
t
i
m
e
o
n
1
m
a
c
h
i
n
e
r
u
n
n
i
n
g
t
i
m
e
o
n
m
m
a
c
h
i
n
e
s
.
Sizeup indicates the scalability when increasing the data size, which is measured as(16)
S
i
z
e
u
p
m
=
r
u
n
n
i
n
g
t
i
m
e
o
v
e
r
m
u
n
i
t
s
o
f
d
a
t
a
r
u
n
n
i
n
g
t
i
m
e
o
v
e
r
o
n
e
u
n
i
t
o
f
d
a
t
a
.
Scaleup is to measure the scalability of processing m-times larger data on an m-times larger cluster, which is calculated as(17)
S
c
a
l
e
u
p
m
=
r
u
n
n
i
n
g
t
i
m
e
o
v
e
r
o
n
e
u
n
i
t
o
f
d
a
t
a
o
n
o
n
e
m
a
c
h
i
n
e
r
u
n
n
i
n
g
t
i
m
e
o
v
e
r
m
u
n
i
t
s
o
f
d
a
t
a
o
n
m
m
a
c
h
i
n
e
s
.
(2)
For classification problems, accuracy, recall, andF-measure are used to evaluate the performance of supervised learning performance in ELM feature space.Accuracy indicates the overall ratio of correctly classified samples, which is measured as(18)
A
c
c
u
r
a
c
y
=
T
r
u
e
P
o
s
i
t
i
v
e
+
T
r
u
e
N
e
g
a
t
i
v
e
T
o
t
a
l
s
a
m
p
l
e
s
n
u
m
b
e
r
.
Recall is the ratio of the samples with a specific class label to the ones classified into this class, which is measured as(19)
R
e
c
a
l
l
=
T
r
u
e
P
o
s
i
t
i
v
e
T
r
u
e
P
o
s
i
t
i
v
e
+
F
a
l
s
e
.
F
-measure is to measure the overall performance considering both accuracy and recall, which is calculated as(20)
F
-
m
e
a
s
u
r
e
=
2
×
a
c
c
u
r
a
c
y
×
r
e
c
a
l
l
a
c
c
u
r
a
c
y
+
r
e
c
a
l
l
.
(3)
For clustering problems, since each sample in the datasets we used in our experiments is assigned with a class label, we treat this class label as the cluster label. Thus, the same evaluation criteria are used for clustering problems as for classification problems.


## 6.2. Evaluation Results

### 6.2.1. Scalability of DXRC

The scalability of representation converting algorithm DXRC is first evaluated. Figure5(a) demonstrates the speedup of DXRC. As the number of the slave nodes varies from one to eight, the speedup tends to be approximately linear at first, but the growth slows down due to the increasing cost of network communications among more and more working machines. But, in general, DXRC gains good speedup. Figure 5(b) presents the sizeup of DXRC. The x-axis denotes the percentage against the whole datasets. That is, 1 is the full size of original dataset; 0.5 indicates half of the original dataset, in which the samples are randomly chosen. With a fixed number of slave machines, which is eight, the evaluation result shows good sizeup of DXRC. Since the scaleup in distributed implementation cannot stick to 1 in practice, in Figure 5(c), the scaleup of DXRC drops slowly when the number of slave nodes and the size of dataset increase, which indicates a good scaleup of DXRC.Figure 5
Scalability of DXRC.
(a)
Speedup
(b)
Sizeup
(c)
ScaleupNote that the representation ability and performance influence on XML documents classification of DSVM applied in DXRC can be found in our previous work [4].


### 6.2.2. Scalability of Massive XML Classification in ELM Feature Space

With the training samples converted by algorithm DXRC, a classifier of massive XML documents can be trained based on MapRedcue. The speedup comparison between PELM and POS-ELM on three datasets is presented in Figure6.Figure 6
Comparison of speedup between PELM and POS-ELM.
(a)
Dataset Wiki
(b)
Dataset IBM
(c)
Dataset ABC NewsAlgorithm PELM, which implements original ELM on MapReduce, requires calculating the inverse of ELM feature space matrix, while PEO-ELM makes use of the idea of online sequential processing to realize parallel computation without communication and requires calculating output weightβ and the auxiliary matrix P iteratively in a single reducer. The centralized calculation reduces the scalability of both PELM and POS-ELM to some degree, especially for POS-ELM. Thus, the speedup of PELM is better than POS-ELM.Figure7 demonstrates the sizeup comparison between PELM and POS-ELM. From this figure, we find that the sizeup of PELM is better than POS-ELM on all the three datasets.Figure 7
Comparison of sizeup between PELM and POS-ELM.
(a)
Dataset Wiki
(b)
Dataset IBM
(c)
Dataset ABC NewsFor the scaleup comparison, Figure8 demonstrates that both PELM and POS-ELM have good scaleup performance, and PELM outperforms POS-ELM on each of the three datasets.Figure 8
Comparison of scaleup between PELM and POS-ELM.
(a)
Dataset Wiki
(b)
Dataset IBM
(c)
Dataset ABC NewsIn summary, both PELM and POS-ELM have good scalability for massive XML documents classification applications, but PELM has better scalability than POS-ELM.


### 6.2.3. Performance of Massive XML Classification in ELM Feature Space

The parallel implementation of both PELM and POS-ELM does not invade the computation theory of original ELM and OS-ELM, respectively; that is, the classification performances of PELM and POS-ELM are nearly the same as their corresponding centralized algorithms, respectively. The classification results are shown in Table1.Table 1
Classification performance comparison between PELM and POS-ELM.
Datasets
PELM
POS-ELM
Accuracy
Recall
F-measure
Accuracy
Recall
F-measure
Wikipedia
0.7886
0.7563
0.7721
0.7923
0.7745
0.7833
IBM DeveloperWorks
0.7705
0.8145
0.7919
0.7711
0.7863
0.7891
ABC News
0.8681
0.8517
0.8598
0.8517
0.8335
0.8425From the table we can see that PELM slightly outperforms POS-ELM, because the iterative matrix operations of output weightβ in POS-ELM cause loss of calculation accuracy. However, for massive XML documents classification applications, since both the extraction and reduction of XML document features are complicated, both PELM and POS-ELM provide satisfactory classification performance.


### 6.2.4. Scalability of Massive XML Clustering in ELM Feature Space

In this set of experiments, we evaluate the proposed distributed clustering algorithm in ELM feature space, that is, distributed ELMk-Means. In theory, the scalability of distributed k-Means in ELM feature space and in original feature space is the same, since the only difference is the feature space of the training samples, which has no influence on the computation complexity. Thus, we only present the scalability of DEK without comparison with distributed k-Means in original feature space.The scalability of DEK is evaluated on all the three datasets in terms of speedup in Figure9(a), sizeup in Figure 9(b), and scaleup in Figure 9(c). The experimental results all demonstrate good scalability of DEK for massive XML documents clustering applications.Figure 9
Scalability of DEK.
(a)
Speedup
(b)
Sizeup
(c)
Scaleup


### 6.2.5. Performance of Massive XML Clustering in ELM Feature Space

Clustering performance comparison between distributed clustering in ELM feature space and clustering in original feature space is made for massive XML documents clustering applications in this set of experiments. Note that, since the manual relabeling of the massive XML dataset is infeasible, we only evaluate the clustering quality with the original number of classes, which is six. The comparison results on three different datasets are presented in Table2. It can be seen from the comparison results that DEK gets better clustering performance due to its ELM features mapping.Table 2
Clustering performance of DEK compared with parallelk-Means.
Dataset
Parallelk-Means
DEK
Accuracy
Recall
F-measure
Accuracy
Recall
F-measure
Wikipedia
0.7602
0.7426
0.7513
0.7737
0.7648
0.7692
IBM DeveloperWorks
0.7985
0.8268
0.8126
0.8124
0.8277
0.8200
ABC News
0.8351
0.8125
0.8201
0.8529
0.8192
0.8357


## 6.2.1. Scalability of DXRC

The scalability of representation converting algorithm DXRC is first evaluated. Figure5(a) demonstrates the speedup of DXRC. As the number of the slave nodes varies from one to eight, the speedup tends to be approximately linear at first, but the growth slows down due to the increasing cost of network communications among more and more working machines. But, in general, DXRC gains good speedup. Figure 5(b) presents the sizeup of DXRC. The x-axis denotes the percentage against the whole datasets. That is, 1 is the full size of original dataset; 0.5 indicates half of the original dataset, in which the samples are randomly chosen. With a fixed number of slave machines, which is eight, the evaluation result shows good sizeup of DXRC. Since the scaleup in distributed implementation cannot stick to 1 in practice, in Figure 5(c), the scaleup of DXRC drops slowly when the number of slave nodes and the size of dataset increase, which indicates a good scaleup of DXRC.Figure 5
Scalability of DXRC.
(a)
Speedup
(b)
Sizeup
(c)
ScaleupNote that the representation ability and performance influence on XML documents classification of DSVM applied in DXRC can be found in our previous work [4].


## 6.2.2. Scalability of Massive XML Classification in ELM Feature Space

With the training samples converted by algorithm DXRC, a classifier of massive XML documents can be trained based on MapRedcue. The speedup comparison between PELM and POS-ELM on three datasets is presented in Figure6.Figure 6
Comparison of speedup between PELM and POS-ELM.
(a)
Dataset Wiki
(b)
Dataset IBM
(c)
Dataset ABC NewsAlgorithm PELM, which implements original ELM on MapReduce, requires calculating the inverse of ELM feature space matrix, while PEO-ELM makes use of the idea of online sequential processing to realize parallel computation without communication and requires calculating output weightβ and the auxiliary matrix P iteratively in a single reducer. The centralized calculation reduces the scalability of both PELM and POS-ELM to some degree, especially for POS-ELM. Thus, the speedup of PELM is better than POS-ELM.Figure7 demonstrates the sizeup comparison between PELM and POS-ELM. From this figure, we find that the sizeup of PELM is better than POS-ELM on all the three datasets.Figure 7
Comparison of sizeup between PELM and POS-ELM.
(a)
Dataset Wiki
(b)
Dataset IBM
(c)
Dataset ABC NewsFor the scaleup comparison, Figure8 demonstrates that both PELM and POS-ELM have good scaleup performance, and PELM outperforms POS-ELM on each of the three datasets.Figure 8
Comparison of scaleup between PELM and POS-ELM.
(a)
Dataset Wiki
(b)
Dataset IBM
(c)
Dataset ABC NewsIn summary, both PELM and POS-ELM have good scalability for massive XML documents classification applications, but PELM has better scalability than POS-ELM.


## 6.2.3. Performance of Massive XML Classification in ELM Feature Space

The parallel implementation of both PELM and POS-ELM does not invade the computation theory of original ELM and OS-ELM, respectively; that is, the classification performances of PELM and POS-ELM are nearly the same as their corresponding centralized algorithms, respectively. The classification results are shown in Table1.Table 1
Classification performance comparison between PELM and POS-ELM.
Datasets
PELM
POS-ELM
Accuracy
Recall
F-measure
Accuracy
Recall
F-measure
Wikipedia
0.7886
0.7563
0.7721
0.7923
0.7745
0.7833
IBM DeveloperWorks
0.7705
0.8145
0.7919
0.7711
0.7863
0.7891
ABC News
0.8681
0.8517
0.8598
0.8517
0.8335
0.8425From the table we can see that PELM slightly outperforms POS-ELM, because the iterative matrix operations of output weightβ in POS-ELM cause loss of calculation accuracy. However, for massive XML documents classification applications, since both the extraction and reduction of XML document features are complicated, both PELM and POS-ELM provide satisfactory classification performance.


## 6.2.4. Scalability of Massive XML Clustering in ELM Feature Space

In this set of experiments, we evaluate the proposed distributed clustering algorithm in ELM feature space, that is, distributed ELMk-Means. In theory, the scalability of distributed k-Means in ELM feature space and in original feature space is the same, since the only difference is the feature space of the training samples, which has no influence on the computation complexity. Thus, we only present the scalability of DEK without comparison with distributed k-Means in original feature space.The scalability of DEK is evaluated on all the three datasets in terms of speedup in Figure9(a), sizeup in Figure 9(b), and scaleup in Figure 9(c). The experimental results all demonstrate good scalability of DEK for massive XML documents clustering applications.Figure 9
Scalability of DEK.
(a)
Speedup
(b)
Sizeup
(c)
Scaleup


## 6.2.5. Performance of Massive XML Clustering in ELM Feature Space

Clustering performance comparison between distributed clustering in ELM feature space and clustering in original feature space is made for massive XML documents clustering applications in this set of experiments. Note that, since the manual relabeling of the massive XML dataset is infeasible, we only evaluate the clustering quality with the original number of classes, which is six. The comparison results on three different datasets are presented in Table2. It can be seen from the comparison results that DEK gets better clustering performance due to its ELM features mapping.Table 2
Clustering performance of DEK compared with parallelk-Means.
Dataset
Parallelk-Means
DEK
Accuracy
Recall
F-measure
Accuracy
Recall
F-measure
Wikipedia
0.7602
0.7426
0.7513
0.7737
0.7648
0.7692
IBM DeveloperWorks
0.7985
0.8268
0.8126
0.8124
0.8277
0.8200
ABC News
0.8351
0.8125
0.8201
0.8529
0.8192
0.8357


## 7. Conclusion

This paper addresses the problem of distributed XML documents learning in ELM feature space, which has no previous work to our best knowledge. Parallel XML documents representation converting problem based on MapReduce is discussed by proposing a distributed XML representation converting algorithm DXRC. The problem of massive XML documents classification in ELM feature space is studied by implementing PELM and POS-ELM, while, for the problem of massive XML documents clustering in ELM feature space, a distributed ELMk-Means algorithm DEK is proposed. Experimental results demonstrate that the distributed XML learning in ELM feature space shows good scalability and learning performance.



---

*Source: 923097-2015-05-27.xml*