Mining Package Documentation
NYSOL Package version: 1.2,2.0

Revision history:
October 6, 2014 : Addition of mbonsai,mgpmetis.rb commands
January 17, 2014 : first release

July 27, 2015c
Copyright ⃝2013
by NYSOL CORPORATION

Contents
1 Introduction
1.1 Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Installation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5672 Mining Manuals
2.1 burst.rb - Burst Detection Command . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 mnb.rb Naı̈ve Bayesian Classifier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3 mbonsai Decision Tree Generated from Sequence Data . . . . . . . . . . . . . . . . . . . . . . . .
2.4 mgpmetis.rb Graph Partitioning Command . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9
10
15
19
31

3

Chapter 1

Introduction

5

6

1.1

CHAPTER 1. INTRODUCTION

Abstract

Data mining is the initial process in knowledge discovery to discover meaningful patterns from large data sets
by applying data analysis technique such as statistics, pattern recognition, and artificial intelligence. Examplesof data mining techniques includes extraction of association rules in ”enumeration of frequent patterns”, predict
data category with the use of ”classification”, prediction of real value using ”regression analysis”, and classification of similar data with ”clustering”. This set data mining commands allow users to apply the mentioned
approach in data analysis. In addition, a Ruby extension library is provided for processing of large-scale CSV
data in Ruby, which reads input data in CSV format as it is done in MCMD.

1.2. INSTALLATION

1.2

7

Installation

M-Command supports the following operating system architectures.
• Mac OS X 10.7.5(Lion)• Ubuntu Linux 12.04(32bit, 64bit)
Installation packages are available. Users would be able to install MCMD on systems with slight variation of
the OS versions listed above. The software can be compiled and installed from the source code for installationin other OS.

1.2.1

Mac OS X

The mining gem package is included within the NYSOL package which can be downloaded from http://www.
nysol.jp/en/home.

1.2.2

Ubuntu Linux

Download the latest NYSOL rpm package from http://www.nysol.jp/en/home.

1.2.3

Install from Source CodeThe mining package is included within the NYSOL package. Follow the steps in the installation page to compile
the program from source. http://www.nysol.jp/en/home/install.

Chapter 2

Mining Manuals

910

CHAPTER 2. MINING MANUALS

2.1

burst.rb - Burst Detection Command

Detection of burst state is used for analyzing a given series of data, Hidden Markov Model (HMM) is used as
the algorithm. The phenomenon assumes probability distributions are used to describe the state transitions in
two modes, namely steady-state and burst states, and returns the likelihood that maximizies all possible state
sequences for the given data. Diﬀerent types of probability distributions can be specified, such as Exponential
distribution, Poisson distribution, Normal distribution, and Binomial distribution. Details is shown in the next
section.
The input data shown in Table 2.8 is a numerical sequenced data (val item). Other fields (such as id) are notused for burst detection. Since the burst column from the input data is included in the output data (Table 2.2),
thus, only include necessary items in the input data.
Table
Input
id
a01
a02
a03
a04
a05
a06
a07
a08
a09
a10
a11
a12
a13
a14
a15
a16
a17
a18
a19
a20
a21

2.1: Table 2.2: Poisson distribution Table 2.3: Exponential distri- Table 2.4: Normal distribution
burst
bution burst
burst
val
1
1
4
1
1
10
7
4
5
8
12
1
1
1
6
8
2
8
2
3
4

id
a01
a02
a03
a04
a05
a06
a07
a08
a09
a10
a11
a12
a13
a14
a15
a16
a17
a18
a19
a20
a21

val
1
1
4
1
1
10
7
4
5
8
12
1
1
1
6
8
2
8
2
3
4

burst
0
0
0
0
0
1
1
0
0
1
1
0
0
0
0
1
0
1
0
0
0

id
a01
a02
a03
a04
a05
a06
a07
a08
a09
a10
a11
a12
a13
a14
a15
a16
a17
a18
a19
a20
a21

val
1
1
4
1
1
10
7
4
5
8
12
1
1
1
6
8
2
8
2
3
4

burst
1
1
1
1
1
0
0
0
0
0
0
1
1
1
0
0
0
0
0
0
0

id
b01
b02
b03
b04
b05
b06
b07
b08
b09
b10
b11
b12
b13
b14
b15
b16
b17
b18
b19
b20
b21

value
1
-4
-2
1
1
10
7
2
5
8
10
1
1
1
7
-8
-3
5
1
1
1

burst
0
0
0
0
0
0
0
0
0
1
1
0
0
0
0
-1
-1
0
0
0
0

Assume that the number of events in this data series is measured based on time factor (for example, thenumber email arrived per hour), burst detection can be generated from Poisson distribution (Table 2.2). In
addition, given intervals between events (For example, the interval of seconds of arrivals of mail), burst detection
is typically generated from a exponential distribution (Table 2.3). Furthermore, given an error series (such as
stock price trends), burst detection could be generated from normal distribution (Table 2.4). Thus, it is possible
to use the same input data to carry out diﬀerent burst detections depending on the distribution methods. The
choice of distribution method is determined by the application to the problem.

Formatburst.rb i= f= dist= [o=] [d=] [s=] [p=] [param=] [pf=] [n=] [nf=] [v=] [nv=] [--help]
Note 1
There are three ways to define parameters of distribution at steady-state as follows.
1. Specify the value at param=.

2.1. BURST.RB - BURST DETECTION COMMAND
i=
o=
d=
dist=
f=
param=
pf=
s=
p=
n=
nf=
v=
nv=
--help11: Input file name [required paramenter]: Output file name [optional: to standard output by default ]: Debug information file [optional]: Type of distribution (exp:exponential distribution,poisson:Poisson distribution,gauss:normal distribution,binom:binomial distribution) [required parameter]: Numeric field name of the target for burst detection (field names in i=) [required parameter]: Parameters of distribution at steady-state. See note 1 [optional]: Field name(s) of the parameters of distribution at steady-state (field names in i=) See note 1 [optional]: Burst scale (extreme burst can be detected if this value is increased. See note 1 for details)[optional : default value=2.0]: Probability of same state transition (it is diﬃcult to transition to a diﬀerent state by increasing this value.
See note 2 for details) [optional : default value =0.6]: Number of trials when dist=binom [Specify n= or nf=]
: Field name of the number of trials when dist=binom: Variance value when dist=gauss (if the value is not specified, the default value is estimated from the data
where the fields is defined at f= ): Field name of the variance when dist=gauss: Display help information

2. Use the value from the field specified at pf=. This assumes that the time dependent on the parameter isdiﬀerent.
3. If para= and pf= is not specified, the calculation is automatically derived from the value specified in f=.
The method of calculation from the data as mentioned in the third method above diﬀers according to diﬀerent
distribution. Nevertheless, S is the value specified by s=, n= is the number of data, xi is the i-th row of valueof the item specified by f=.
Distributionexp
poisson
gauss
binom

Probability (density) function
f (x) = λe−λxx −Γ
ef (x) = λ x!
22
f (x) = √ 1 2 e−(x−µ) /2σ
2πσf (x) = n Cx px (1 − p)n−x

Parameter (par)λ:Average number of events
λ:Average number of eventsµAveragep:Success probability∑

2

Steady-state∑ par
λ0 = N/ i xi∑
λ0 = N1x∑i iµ0 = N1x∑i ip0 = N1n i xi **Burst state parλ1 = Sλ0
λ1 = Sλ0√µ± = µ0 ± S σ 2 *0
p1 = S/( 1−p+ S)p0(xi −m)2*σ =N −1**n is specified by n=.

Note 2
When p is assumed as the probability specified by p=, the probability of state transition is set as follows.
Table 2.5: State transition probability of exp, poisson,
binom
steady-state
burst

steady-state
p
1−p

burst
1−p
p

Table 2.6: State transition probability of ingaussburststeady-state
burst+

burstp1(1 − p)2
1(1 − p)3

Steady-state2(1 − p)3
p2(1 − p)3

burst+
1(1 − p)3
1(1 − p)2

pExplanation
Formulation
HMM (Hidden Malkov Model) is a probabilistic model that is built on the assumption of Markov process withhidden state that can not be observed directly. HMM is comprised of stochastic state transition model and data
generation model. The observed data series follow the data generation model in hidden state.

12

CHAPTER 2. MINING MANUALSTime t observed in data xt will be modelled according to the probability distributionp(xt |zt ; ϕ) that is defined
hidden state zt ∈ {1, 2, · · · , K}. ϕ is the vector parameter of generation model, with the assumption that it isconstant and does not depend on t. Furthermore, hidden state zt transitions depend on the previous state zt−1 ,the probability distribution is shown in p(zt |zt−1 ; A).
A = {ai,j |i, j = 1, 2, · · · , K} is the transition probability
table from state i to j with the assumption that it∑
is constant and does not depend on t. However, in j ai,j = 1.0, the initial state z1 is assumed to follow the
probability vector π.
From the above, the joint probability of the observed data series X = x1 , x2 , · · · , xN and state series Z =z1 , z2 , · · · , zN are given by the formula (2.1).[1]
[N
] N
∏
∏
p(zi |zi−1 ; A)p(X, Z; π, A, ϕ) = p(z1 ; π)i=2p(xj |zj ; ϕ)

(2.1)

j=1

In burst detection, K = 2, i.e. assuming two states: steady state and burst, the observable data series can beobtained from the same probability distribution with diﬀerent parameters in each state.
In the burst detection problem, given the parameter π, A, ϕ, find Z∗ to maximize the joint probability shownin the formula(2.1) at the time of observing the data series X (formula(2.2)).
Z∗ = argmax p(X, Z; π, A, ϕ)

(2.2)

Z

Burst detection example of email
Corresponding to the above formula, the following example explains burst detection in relation to the numberof emails arrived (Table 2.8). The objective here is to seek the hidden state sequence Z = z1 , z2 , · · · , zN
(zi ∈ {0, 1|0issteady−state, 1isburststate}) from the numeric sequence X = 1, 1, 4, · · · shown in Table 2.8.
Consider the number of email arrivals as random variable, it will be appropriate to assume as Poisson distribution. Poisson distribution takes the average number of arrivals λ as parameter, and the probability function
represent by the formula (2.3).

f (x) =

λx e−Γ
x!

(2.3)

The parameter λ0 in steady-state is defined by the command parameters at param= or pf=. When the parameters
are not specified, the parameter is specified by the average arrivals from the data specified at i=. The calculation
result of the average value of the field val in Table 2.8 is λ0 = 4.29. Further, the parameter λ1 in burst stateis set as 2 times the normal state (8.58) unless otherwise specified. The value can be changed by defining thevalue at s=.
From the above, the probability distribution of the state of the parameter vector is ϕ = (4.29, 8.58). Table 2.7
shows the probability of the numeric value of data series X from each state. The probability of steady-state fornumeric value ”1” and ”4” is high, and the probability of burst state for ”10” is high.
Next, let’s consider state transition probability p(zi |zi−1 ; A). There are four combinations of transition in thetwo state. In this command, it is possible to provide the same probability values for the transition probabilities
between the same states, the default value is 0.6 unless otherwise stated. In other words, a0,0 , a1,1 = 0.6.
Further, the transition probabilities of diﬀerent states are calculated by a0,1 , a1,0 = 0.4. The state transition
probability A is shown in the formula below (2.4).
(
A=

a0,0 = 0.6
a1,0 = 0.4

a0,1 = 0.4
a1,1 = 0.6

)
(2.4)

2.1. BURST.RB - BURST DETECTION COMMAND

13

Table 2.7: Probability of each state in Poisson distribution
id
a01
a02
a03
a04
a05
a06
a07
a08
a09
a10
a11
a12
a13
a14
a15
a16
a17
a18
a19
a20
a21

val
1
1
4
1
1
10
7
4
5
8
12
1
1
1
6
8
2
8
2
3
4

steady-state(λ = 4.29)
0.05900.05900.19350.05900.05900.00790.07250.19350.16580.03890.00110.05900.05900.05900.11850.03890.12640.03890.12640.1806
0.1935burst(λ = 8.58)
0.00160.00160.04260.00160.00160.11170.12780.0426
0.07300.13690.06220.00160.00160.00160.10430.13690.00700.13690.00700.01990.0426

The probability vector of the initial state at the end is π = (1.0, 0.0), assuming that the initial state is a steadystate. From the above, the parameters A, ϕ, π of the formula(2.1) are met. Next, find out the series of stateZ∗ to maximize the formula(2.1).
Given the size of the data series X is 21, there are about 221 = 2million combinations of state sequences forconsideration. The optimal solution of long sequences can not be solved by brute force. Viterbi algorithm isa dynamic programming method for finding the most likely sequence of hidden states. Refer to specialized
textbooks for detailed theoretical explanation, however this method generates state sequence as shown in Table
2.2.

ExamplesExample 1 Example from the ”Explanation” section above-----------------------------------------------# inp1.csv
id,val
a01,1
a02,1
a03,4
a04,1
a05,1
a06,10
a07,7
a08,4
a09,5
a10,8
a11,12
a12,1

14
a13,1
a14,1
a15,6
a16,8
a17,2
a18,8
a19,2
a20,3
a21,4
$ burst.rb i=inp1.csv f=val dist=poisson o=out1.csv# out1.csv
id,val,burst
a01,1,0
a02,1,0
a03,4,0
a04,1,0
a05,1,0
a06,10,1
a07,7,1
a08,4,0
a09,5,0
a10,8,1
a11,12,1
a12,1,0
a13,1,0
a14,1,0
a15,6,0
a16,8,1
a17,2,0
a18,8,1
a19,2,0
a20,3,0
a21,4,0------------------------------------------------

CHAPTER 2. MINING MANUALS

2.2. MNB.RB NAÏVE BAYESIAN CLASSIFIER

2.2

15

mnb.rb Naı̈ve Bayesian Classifier

Build a probability classifier model by applying Bayes’ theorem using supervised learning. The probability of theclass variable is calculated based on the presence of a particular feature of the item, and returns the predictedclass from the test data in the output. The model used Multinomial Naive Bayes to handle the frequency
distribution of the item. However, the probability becomes zero if the new item only appeared during validation
stage. The problem can be avoided by applying Laplace smoothing. Table 2.8 shows an excerpt of training
data which is used as input data. ”Transaction ID” is used to identify each transaction, and each transaction
must contain ”item”, ”frequency” and ”class information”. In Table 2.8, the transaction fields correspond to”id”, ”word”, ”freq”, ”class”. Table 2.9 shows an example of validation (testing) data. In the validation data,
the class field is not included, the class is predicted from the Naive Bayes model constructed with the training
data.
Table
2.8:
data(train.csv)
id
1
1
2
2
2
4
4
4
5
6
6

word
w1
w2
w1
w2
w3
w1
w2
w3
w1
w1
w2

Training
freq
2
4
1
2
3
3
3
2
1
2
1

class
M
M
M
M
M
M
M
M
F
F
F

Table
2.9:
data(test.csv)
id
3
3
7
7

word
w2
w3
w1
w2

Validation
freq
8
2
1
3

Formatmnb.rb k= f= w= c= i= o= [I=] [O=] [-c] [-debug] [--help]
i=
o=
k=
f=
w=
c=
I=
O=
-c
-debug: File name of training data [required parameter].
: Output file name [required parameter].
: Field name of transaction ID (i= & I=on field name) [required parameter].
: Field name (i= & I=on field name) [required parameter].
: Field name of weight (i= & I=on field name) [required parameter].
: Field name of class (class information) [required parameter].
: File name of testing data [optional].
: Output file name of testing data [required parameter].
: Execute with ComplementBayes [optional].
: Debug mode (Returns the detailed message in output, current output of work file is not removed).

Noten1
The field names in the training data and the test data must be specified at k=, f=, w=.

Comment
Naı̈ve Bayes model is a probability model based on Bayes’ theorem with independence assumptions. Consider
the vector with particular features w = (w1 , w2 , · · · , wn )⊤ where the appearance of the feature is represented

16

CHAPTER 2. MINING MANUALS

by the value wi = 0, 1. The probability p(c|w) of each class c, with the presence of feature expressed in w isrepresented in the Bayes’ theorem formula shown in (2.5) .
p(c|w) =p(w|c)p(c)
p(w)

(2.5)

The denominator p(w) is constant regardless of the value of variable c. Therefore, looking at the numerator,p(c) is the posterior probability of class c. The posterior probability p(c|w) is updated when this probabilityof occurrence of the feature vector for the specific class has the likelihood of p(w|c). This refers to the Bayes’
Theorem.
If there are more dimensions of w, it becomes diﬃcult to estimate the joint probability p(w|c) for a single
character. As shown in the formula (2.6), naive Bayes method calculates p(w|c), with the naive assumptions
that the occurrence of all words is independent of each other.
∏p(w|c) =p(wi |c)(2.6)
From the above, p(c|w) is represented by the formula (2.7). In order to build a classifier using Maximum-aPosterior (MAP) probability decision rule which adopts the most plausible hypothesis, the estimated class ĉ
can be determined by the formula (2.8).
p(c|w) ∝∑iĉ = argmax p(c)ln p(wi |c)∑cln p(wi |c)

(2.7)
(2.8)

i

When the naive Bayes classifier is applied in practice, words or items are used as feature vectors. These
include cases with frequency information such as occurrences of the number of words and the number of items
purchased.
Therefore, assuming that the element fi of the vector with particular feature vector f has a frequency ofoccurrence with a feature value of i, each estimated class ĉ is shown in the equation (2.9), calculated bymultiplying the frequency of likelihood fi . The above is known as Multinomial Naı̈ve Bayes model.
ĉ = argmax p(c)c∑fi ln p(wi |c)

(2.9)

i

Problem of Zero Frequency
If the combination of the class and feature value is not present in the training examples, the probability
estimation becomes zero, consequently, the product used for multiplication becomes zero. In order to avoid the
problem of zero frequency, modify the estimated probability value with smoothing, and adjust the probability
values of all combinations so that it will not become zero. In this case, Laplacian smoothing is applied byadding 1 to the number of occurrences to the feature value.
Complement Naı̈ve Bayes
In Naive Bayes classifier, Complement Naive Bayes refers to an extension to learn a the model by using acomplementary set that does not belong to any particular class. When predicting a class using the vector withfeatures which do not belong to any class, the probably of the unclassified vector will be assigned to the lowest
class. When classifying two values, it is not meaningful since the same result will be returned, however, theeﬀect is more prominent when there are a lot of class dispersion in a multi-class classification problem. If -c
option is specified, it is executed as Complement Naı̈ve Bayes.

2.2. MNB.RB NAÏVE BAYESIAN CLASSIFIER

17

An Example to Determine the Gender Author
This example uses the above data to determine the single character gender information contained in the author’s
proposal submission data.
Table 2.8 shows the vectors containing the feature ”word” in the training data, and build a naive Bayes model
to determine the gender as specified in the ”class” field, and the objective is to predict whether the class is M
or F for each unique id in the validation data in Table 2.9.
When running the command (mnb.rb) below with train.csv and test.csv, 2 files namely out.csv and test out.csv
will be returned as output. The prediction probabilities of F and M are contained in field names F,M corresponding to each id in out.csv. The class with higher probability value is returned as the predicted class(predictCls) in the output.
In this example, class and PredictCls are in complete agreement, thus, the accuracy rate of the training data is
100%. The resulting naive Bayes model is built as shown in nb test out.csv, Table 2.9 shows the predicted class(predictCls) obtained from the feature ”word” from each vector. Both vectors with id 3 and 7 has a predictedclass as M (Male).
-----------------------------------------------$ more train.csv
id,word,freq,class
1,w1,2,M
1,w2,4,M
2,w1,1,M
2,w2,2,M
2,w3,3,M
4,w1,3,M
4,w2,3,M
4,w3,2,M
5,w1,1,F
6,w1,2,F
6,w2,1,F$ more test.csv
id,word,freq,class
3,w2,8,M
3,w3,2,M
7,w1,1,F
7,w2,3,F$ mnb.rb i=train.csv I=test.csv O=test_out.csv o=out.csv k=id f=word w=freq c=class#MSG# naiveBayes start; 2013/12/31 23:59:59#END# nb.rb i=train.csv I=test.csv O=test_out.csv o=out.csv k=id f=word w=freq c=class; 2013/12/31 23:59:5$ more out.csv
id,F,M,class,predictCls
1,0.4689127516,0.5310872483,M,M
2,0.4296687087,0.5703312913,M,M
4,0.4748995053,0.5251004949,M,M
5,0.5353401796,0.4646598204,F,F
6,0.5309945758,0.4690054242,F,F$ more test_out.csv
id,F,M,predictCls
3,0.3993866359,0.6006133641,M
7,0.4451382443,0.5548617557,M

18------------------------------------------------

CHAPTER 2. MINING MANUALS

2.3. MBONSAI DECISION TREE GENERATED FROM SEQUENCE DATA

2.3

19

mbonsai Decision Tree Generated from Sequence Data

This command builds a decision tree model based on sequence patterns. Analysis of the sequence data can beapplied in a variety of applications such as order of brands purchased by customers, sales floor cyclic patterns indepartment stores and supermarkets, the onset order of injuries. The original idea of this command, BONSAI[4],was developed by a research team from Kyushu University and Kyushu Institute of Technology. This technique
is applied for the analysis of amino acid sequences in molecular biology. Similarly, this command implemented
several improvements for the application of sequence analysis in business data with the following features.
• Transform patterns from numerical and categorical sequence data into classication conditions.
• Use alphabet indexing as data reduction technique for sequence data.
• Process multiple variables of sequence data, numerical and categorical variables as predictors.
• Allow cost sensitive learning approach to account for dierential misclassification costs.
• Allow separate training and testing of decision tree models.
• Allow two or more classes in target variable for classification.
• Allow cross-validation for assessing performance of predictive model.
First, the example below illustrates how to obtain an intuitive understanding of this command. A data set
contains purchase sequences of brand a,b,c by customers from a retail store, and the corresponding churnstatus of the customer is shown in Table 2.10. Under the hypothesis of which purchase order of the brand isrelated to the estrangement of the customer, we will build a decision tree model with partial pattern of brandpurchasing order as explanatory variable, and the churn status as target variable (Refer to the next section
on details of the definition of patterns that is considered partial string, such as ”ab”, ”cbb”). Pattern used as
explanatory variables is referred to as candidate pattern, the pattern generated (More details on this method isavailable in the next section) will contribute to the accuracy of the model, afterwards, the patterns are converted
to 0-1 variable (Table 2.11). Decision tree is constructed in a conventional manner from this data set consistingof candidate patterns. The actual decision tree created with this command is shown in Figure 2.12.
Table 2.11: The BrandSequence column is extracted
Table 2.10: Example of sequence data. Each line corre- from Table 2.10 and matched against partial purchasesponds to one customer, with the target variable indi- patterns as explanatory variables (referred to as candicating the status of continual purchase of the customer. date patterns). All samples are matched,, the presence
The alphabetic characters a, b, c, shown in ”BrandSe- of patterns is converted to 0-1 formatted data. In thisquence” column represents the brand purchased by the example, the first record contains the partial pattern
customer in the respective order as shown.
”a”, ”b”, ”c”, ”ab” in the sequence, however, aa and
BrandSequence Churncc is not included.
bcaba
bcabcaaaaabac
caa
cca
cacbc
bcc
acca

yes
yes
yes
yes
no
no
no
no

a
1
1
1
1
1
1
0
1

b
1
1
1
0
0
1
1
0

c
1
1
1
1
1
1
1
1

aa
0
1
1
1
0
0
0
0

ab
1
1
1
0
0
0
0
0

cc
0
0
0
0
1
0
1
1

···

···

Churn
yes
yes
yes
yes
no
no
no
no

A notable feature of the BONSAI is the function to group elements (known as alphabet) that make up the
pattern automatically. The grouping of each alphabet is referred to as index.
For example, there are three ways to group the 3 brands a,b,c into two index (a and bc, b and ac, c and ab),each grouping is replaced with the matching index. Three decision trees are built with the above described
procedure, the best decision tree is selected based on classification accuracy.

20

CHAPTER 2. MINING MANUALS!"#$!"#$&'($%&%&'()*+*,$-.$!""$!"#$&'($-.$%&%&'()/+/,$%&%-.)0+0,$

Table 2.12: Example of Building Customer Churn
Model with BONSAI

Table 2.13: Example of Building Customer Churn
Model with BONSAI

Decision tree built in this manner is shown in Figure 2.13. The result of grouping with index increases theaccuracy of the classification model, further more, useful knowledge could also be obtained from the result.

2.3.1

Details

The details concerning the construction of the decision tree are explained as follows.

Regular pattern
Given, n character string constants π1 , π2 , ..., πn on alphabet Σ, with any of the n+1 character string x0 , x1 , ..., xn ,regular pattern (also referred to as sequence pattern) is represented in the format x0 π1 x1 π2 x2 · · · πn xn . This
technique is easier to understand when the concept of wildcard is applied to the field of data retrieval (“*” isused instead of xi as wildcard). In this command, besides the definition of regular pattern described above, thatis x0 πx1 , the regular pattern can be handled by restricting to the substring π (hereinafter referred to as ”string
pattern”). The use of string pattern and sequence pattern is specified in the second parameter at p=.

Begin / End Match
It is possible to specify the matching of beginning and ending string as matching rule for regular pattern ofeach sample of sequence data. This can be specified in the fourth (match beginning), and fifth (match ending)parameters of p=. Based on this specification, the position of the alphabet of the beginning (or ending) of regularpattern, the beginning (or ending) of sequence data is matched within the specified number of characters. For
example, given the sequence data aabccd, when matched with character substring pattern ab from the left, if
the matching sequence only contains 1 character, it is not considered as match, if the beginning of the sequence
contains first two characters of the substring pattern, it is considered as match. If the sequence pattern is madeup of ab, it is possible to match the first charter in the beginning. If this parameter is not specified, it operates
without restriction of matching as described above.

Alphabetical Order
This command can deal with order structure that contains alphabets. The key diﬀerence of order structure is
the rules for creating the index. Given the alphabet set {a1 , a2 , . . . , an }, with the relationship of a1 ≺ a2 ≺. . . ≺ an for any three consecutive alphabet ai , ai+1 , ai+2 , an index is generated to satisfy the relationship of
ψ(ai ) = ψ(ai+2 ) ⇒ ψ(ai ) = ψ(ai+1 ). Here, ψ(a) represents an index to be associated with the alphabet a.
This means that the alphabets belonging to a group for indexing must always follow consecutive order. For

2.3. MBONSAI DECISION TREE GENERATED FROM SEQUENCE DATA

21

example, given three consecutive alphabet a ≺ b ≺ c, {a, b}and{c} is grouped together, but {a, c}and{b} is not.
Consecutive alphabet can be specified in the third parameter of p=.

Local Search and Search Space of Optimal Alphabet Index
Given n number of alphabet(s), the number of cases to be grouped into m or less indexes is not certain, butwhen m = 2 is set as limit, the number can be presented in mn−1 ways. If both the value of m, n are small, it ispossible to construct a decision tree for all cases, and if the value is large, the local search method of searching in
subspace is applied. Initially, the random index is set to corresponding alphabet, the corresponding relationshipchanges bit by bit when building the decision tree, and continue to change until there is no improvements inclassification accuracy (Refer to literature [4] for details). Thus, sometimes the results may diﬀer depending on
the initial value of the corresponding relationship between the index and the alphabet. In order to obtain thesame results from the initial value and select the best model (multi-start), the initial value can be specified atiter= in this command. The default value is iter=1.

Method of Generating Candidate Patterns
Candidate patterns as shown in Table 2.11 are generated from the updated alphabet index by local search. The
generation of the classification rules for the candidate patterns is based on the nodes of the decision tree. In thiscommand, candidate patterns are enumerated by the heuristics method described below. First, the index forthe regular pattern with length 1 is constructed, and is stored in the priority queue. Precedence in the priority
queue is determined by ascending order (see below) of the entropy of a regular pattern Afterwards, select theregular pattern with the lowest entropy in the priority queue, an index is added to the selected regular pattern,
regular pattern with length of 2 is created, and stored in priority queue again. Repeat the above steps suchthat, regular pattern with length n is selected, and regular pattern with length n + 1 is stored in the priority
queue. However, the index cannot be added when n is greater than 5 (the upper size limit of the regular pattern
can be specified in the sixth parameter of p=). In addition, the process will terminate if the size is greaterthan the number of candidates (specified by cand=) specified by the user. Entropy is used to evaluate regularpatterns and is also used in the selection of the splitting rules at the nodes of the decision tree, the value ofentropy becomes smaller as the regular patterns are classified into extreme distribution classes. Entropy ent(π)
of regular pattern π is defined in Equation 2.10.

ent(π) = −q m(π)

c
c
∑
∑
m(π)
m(π)
u(π)
u(π)
pi
log pi− q u(π)
pi log pi
i=1

m(π)

(2.10)i=1u(π)

Here, c represents the number of classes, pi(pi
represents the composition ratio of class i that matches∑c m(π)(or unmatch) with the sample in the regular pattern π expressed as ( i pi
= 1). In addition, q m(π) (q u(π) )represents the composition ratio of matching (or unmatch) with regular patterns π out of all samples (q m(π) +q u(π) = 1).

Other Types of Variables
In this command, besides sequence data, numerical and categorical variables can be specified as an explanatory
variable. By doing so, it is possible to construct decision tree rule that includes regular patterns with categoricaland numerical rules. The creation of branch rules based on category and numbers is similar to that in C4.5
[5]. In this command, columns with sequence, numeric, and categorical data can be defined at p=,n=,d=parameters.

22

CHAPTER 2. MINING MANUALS

Selection of Splitting Rule
This command adopts a top down greedy method for the splitting of branches. In other words, splitting rules
at the node of the tree is determined according to the evaluation criteria from the information in the node. The
evaluation criteria is based on the selection of branching rules which maximizes the entropy gain. For samples
that have been classified into certain nodes, the∑c probability (composition ratio) of class i is represented by pi ,the entropy at node is calculated by ent = − i=1 pi log pi . At node pi , number of samples n are classified intoclass i, the ratio of classified sample ni can be calculated by ni /n. Equation 2.10 shows the entropy gain fromthe diﬀerence of entropy ent(π) after splitting the regular pattern π. It means by splitting the regular patternπ, how much entropy is reduced. The procedure is repeated until all samples are classified into respective classes
at the node, and the tree can no longer be grown bigger. This type of decision tree is referred to as maximaltree.

Pruning
Construct a maximum tree Tmax according to the method shown in the previous section, but since the tree sizeis larger than normal tree, the training data tends to overfit the model, where the classification accuracy of
training data is high (misclassification rate decreases), but prediction accuracy of test data decreases. In order
to avoid this problem, a small section (including the root node) of the maximal tree is removed during pruningthat may be based on noisy or erroneous data.
In consideration to the set of nodes t from decision tree T , where the maximal tree is denoted by Tmax ={t1 , t2 , . . . , tk }, node t and root node of the subtree is represented by Tt , the subtree
of node t ∈ P to root node∪is pruned (replaced with leaf node) from the decision tree expressed as Tmax − t∈P Tt +P . The misclassification
rate of decision tree T is denoted by R(T ), the pruning is based on the selection of subtree T ∗ with the lowest
misclassification rate on unknown data. It is not possible to determine the actual misclassification rate forunknown data of T , instead, it is estimated based on the training data. Given the prediction amount is C(T ),the formula of pruning is expressed in the formula 2.11.
P ⊆Tmax C(Tmax −∪Tt + P )(2.11)t∈P

To solve this problem, this command applies the cost-complexity pruning method [6]. This method is comprisedof two key phases. First, a series of subtrees T1 ⊃ T2 ⊃ . . . ⊃ Tk is selected which is nested from the maximal treebuild from the training data (here T1 is the maximal tree, Tk is the root node). Next, the accuracy of these trees
is estimated by test sample using cross-validation, the tree with highest prediction accuracy is selected.
When selecting the series of subtree, the evaluation function of decision tree T measuring the cost complexity
is defined as Rα (T ) = R(T ) + α|T̃ |, the decision tree model is considered better if the value is smaller. Thisequation is obtained by balancing the misclassification rate of decision tree R(T ), and the tradeoﬀs of decision
tree complexity |T̃ | (number of leaf nodes in T ) where the complexity parameter is α(≥ 0). In the training data,when the tree size grows larger, the misclassification rate R(T ) decreases monotonically, and yet, the complexity|T̃ | increases monotonically. When α is adjusted, the priority of misclassification rate and complexity is also
adjusted accordingly. Here, α is fixed as a single value, the pruning process find the subtree T (α) that minimizes
the function Rα (T ). Further, T (α) continues to minimize the tree when α increases, it is possible to enumerate
α corresponding to T (α), as a result, the nested subtree T1 ⊃ T2 ⊃ . . . ⊃ Tk is created (Refer to [6] formore details). Here, the subtree Ti consist of the smallest size decision tree with the minimal cost complexityα ∈ (αi , αi+1 ] . In the above series of nested subtree, the corresponding cost complexity parameter α1 , α2 , . . . , αkcan be obtained.
Next, among the series of subtree obtained from the above method, select the optimal subtree T̂ ∗ with theminimum prediction misclassification rate when applied to unknown data. In this command, users can selectbetween test sample method (specified by ts=) or cross-validation (specified by cv=). In test sample method,training data D is partitioned into two sets D1 , D2 at a ratio of1 : 2. Then, the maximal tree based on D2
training data is built, based on the complexity parameter α1 , α2 , . . . , αk obtained from the previous phase, the2.3. MBONSAI DECISION TREE GENERATED FROM SEQUENCE DATA

23

corresponding subtree is selected. From this subtree, D1 is used as the set of unknown data to predict thevalue of misclassification rate. In cross-validation method, training data D is partitioned equally into n sets as
D1 , D2 , . . . , Dn . First, D1 is treated as unknown data for prediction, similarly, this applies to other training datausing the test sample method. Similar process is applied n times to the remaining test data D1 , D2 , . . . , Dn , then
all training data D is applied as one set for validation. Thus, the average misclassification rate is obtained by thismethod. From the results obtained above, complexity parameter α1 , α2 , . . . , αk for decision tree T1 , T2 , . . . , Tk ,the optimal decision tree with the lowest misclassification rate is selected. In addition, the smallest tree whose
estimated mean error rate is within one standard error of the estimated mean error rate of the best tree selected(this is called 1 SE rule ).
Nevertheless, pruning can be done by directly specifying the α value without using the cross-validation or test
sample method. A decision tree can be built at high speed without having to process calculations for prediction,
but the drawback is that the specified α value is arbitrary.
Actual Pruning
In the model building mode, pruning can be done by specifying any of the parameters ts=, cv=, alpha= in
this command. When cv= or ts= is specified, test data is used for prediction, the model with the minimum
misclassification rate is selected. In addition, when alpha= is specified, the pruned model corresponding to thespecified α value is selected. The selection of the model based on the evaluation of the decision tree model issaved in model.txt and model_info.txt. However, regardless of any specification, all α corresponding to the
maximal tree is calculated internally, at prediction mode (-predict), if alpha= is specified, it is possible that
diﬀerent models are used for prediction.
Learning Cost Considerations
When applying classification model, instead of increasing classification accuracy (percentage of correct answers),
there are many instances when it is useful to minimize the cost of misclassification. Cost is used when predicting
customer churn, there are various considerations when implementing cost sensitivity, such as consideration of
the cost of customer who stayed who is predicted as customer who left. Construction of model that takes misclassification costs into consideration is known as cost sensitive learning. Various methods have been proposed,
the method proposed by Breiman et al [6] is used in this case. This method is used for the calculation of the
branch rule, probability pi of class i in the sample is therefore modified by assigning cost calculation. Now, thecost∑ of class j that is predicted as class i expressed as c(i|j), given the sum of costs of class i is expressed asj c(i|j), weight is added to class i and probability pi is updated. If the total cost of class i is large, it means
the number of samples are inflated (oversampling), sensitive model based on information of class i is built. The
class file in CSV format is shown in Table 2.14, actual class (real), the corresponding predicted class (predict)and its cost (cost) is displayed in the same row. Given the combination of actual class and predicted class is
not specified, and the cost file is not defined, when actual class and predicted class is the same, the cost is 0,
otherwise, 1 is set.
Table 2.14: Example of specifying the cost in churn model. In first row, thechurn class yes in the actual sample is predicted as no, the cost is set to 2. In
the second row, when the churn class no is predicted as yes, the cost is set to
5. The column name can be pre-defined, but must be arranged in the order ofactual class, predicted class, and cost.
real
yes
no

predict
no
yes

cost
2
5

24

CHAPTER 2. MINING MANUALS

2.3.2

Output Data

The output of various data files from this command are summarized in Table 2.15.
Table 2.15: List of output data from model building mode in mbonasi
File namemodel.pmml

Content
The decision tree model represented by PMMLa

alpha_list.csv

Other model information of the complexity parameter αSummary of pruned model with minimum classification prediction error
Summary of pruned model with the same 1SE rule
Summary of pruned model for the specified αvalue
Various information of pruned model with minimum classification prediction error
Various information of pruned model with thesame 1SE rule
Summary of pruned model for the specified α
The prediction information of pruned model withminimum classification prediction error
The prediction information of pruned model withthe same 1SE rule
The prediction pruned model for the specified α
List of execution parametersmodel_min.txt
model_1se.txt
model.txt
model_info_min.csv
model_info_1se.csv
model_info.csv
predict_min.csv
predict_1se.csv
predict.csv
param.csv

Remarks
Records pruning information for maximum tree.
Prediction mode is selected when -predict is
specified.
Series of α corresponding to the model such as thesize and accuracy of the model.
Created when cv= or ts= is specified.
Created when cv= or ts= is specified.

Created when cv= or ts= is specified.
Created when cv= or ts= is specified.

Created when cv= or ts= is specified.
Created when cv= or ts= is specified.

Returns the pair of keyword-value for the specified
parameters

a Predictive Model Markup Language is an industry standard to describe data mining and mathematical models represented in
XML-based file format. Note that this specific command uses an extended tag of the PMML standard.

model.pmml Based on the maximal tree of the decision tree created, complexity penalty attribute is shownfor each node, the branch will be pruned when α is greater than the value of complexity penalty. Since themaximal tree and pruning information is recorded in PMML, α is specified for the execution of prediction model,
it is possible that the corresponding value will be used to predict the decision tree model.
:<Node id="0" score="yes" recordCount="8" ><Extension extender="KGMOD" name="complexity penalty" value="0.500000"/>:

model min.txt,model 1se.txt,model.txt Unlike PMML data, a summary of pruned model is saved intext format. The section [alphabet-index] shows the alphabet corresponding to the index. In the following
example, alphabet c corresponds to index 1, while b,a corresponds to index 2. The branching rule of thepattern shown in the decision tree is indicated by index symbol.
[alphabet-index]
Field Name: BrandSequence
Index[1]={c}Index[2]={b,a}The section [decision tree] shows the decision tree in text format, information such as model size (thenumber of leaf nodes) and number of layers of the deepest leaf is shown below the tree.
[decision tree]
if($BrandSequence has 22)

2.3. MBONSAI DECISION TREE GENERATED FROM SEQUENCE DATA

25

then $Churn=yes (hit/sup)=(4/4)
else $Churn=no (hit/sup)=(4/4)
number of leaves: 2
deepest level: 1
The section [Confusion Matrix by Training] shows the prediction classification results of decision tree modelusing training data. In addition, classification table by cost, prediction accuracy by class, overall prediction
accuracy is also shown.
The section [Confusion Matrix by Estimation] is shown when ts= or cv= is specified. The same format
applies to [Confusion Matrix by Training] section, the result of test data will be shown diﬀerently.

26

CHAPTER 2. MINING MANUALS[Confusion Matrix]## TRAINING DATA #### By countPredicted As ...
yes
no
Total
yes
4
0
4
no
0
4
4
Total
4
4
8
## By cost
Predicted As ...
yes
no
Total
yes
0
0
0
no
0
0
0
Total
0
0
0
## Detailed accuracy by classclass,recall,precision,FPrate,F-measure
yes,1,1,0,1
no,1,1,0,1## Summary
accuracy=1
totalCost=0
Finally, the section [Selected Alpha] shows the value of the complexity parameters used for pruning.
[Selected Alpha]alpha: 0

predict min.txt,predict 1se.txt,predict.txt The prediction results is added to the training data used forbuilding the decision tree model in CSV format. The prediction results, as described below, output the highest
prediction probability in the predict column, and the prediction accuracy for each class (yes and no as shown
below). When ts= is specified, it returns the prediction results of test data, when cv= is specified, it returns theprediction results by all test data using cross validation. In addition, when alpha= is specified, the prediction
result of the training data is returned.
Brand Sequence,Churn,predict,yes,nobcaba,yes,yes,1,0
bcabcaa,yes,yes,1,0
aaabac,yes,yes,1,0caa,yes,yes,1,0
cca,no,no,0,1
cacbc,no,no,0,1
bcc,no,no,0,1
acca,no,no,0,1

model info min.csv,model info 1se.csv,model info.csv These files store the model information in CSV
format. The column nobs refer to the number of records in training data, alpha= refers to the value of pruning
complexity parameter, accuracy,totalCost refer to the percentage of correct answers in the test model andthe total cost.
nobs,alpha,accuracy,totalCost
8,0,1,0alpha list.csv Display the error rate, standard error, error rate ± standard error corresponding to the α valueof pruning complexity parameter for the pruned decision tree.
alpha,leafSize,errorRate,SE
,up
,lo
0
,102
,0.0082,0.0015 ,0.0098 ,0.0066
8.15e-05 , 98
,0.0085,0.0016 ,0.0101 ,0.0069
9.41e-05 , 91
,0.0091,0.0016 ,0.0108 ,0.0074
0.000124 , 82
,0.0100,0.0017 ,0.0118 ,0.0083
:
:
:
:
:
:

2.3. MBONSAI DECISION TREE GENERATED FROM SEQUENCE DATA
0.035669 ,1.79e+308,

2
1,0.0878,0.139927,0.0049 ,0.0927 ,0.0828,0.0060 ,0.1460 ,0.1339

param.csv Various parameter values used when building the model is stored in CSV format.

2.3.3

Format 1: Model building mode

mbonsai i= [p=] [n=] [d=] c= O= [delim=] [cost=] [seed=] [cand=] [iter=] [cv=|ts=][leafSize=] [--help]
i=
p=

n=
d=
c=
O=
delim=
cost=
seed=
cand=
iter=
leafSize=alpha=
ts=
cv=--help: Training data file name: Column name of pattern (multiple fields can be specified): Specify up to five parameters after the column name, each separated by a colon.
: p=column_name:is:seq:ordered:head:tail:rs: is: Size of the index: When the parameter is not specified, an index is not generated, instead, original alphabet of the pattern is used.
: seq: Type of pattern: true: Partial sequence pattern: false: Partial string pattern (default): ordered: Arrangement in alphabetical order when generating the index.
:(this parameter is ignored when is is not specified): true: Ordered, group alphabet above / below the threshold value.
: false: Unordered(default): head: Match string or numeric characters from the beginning (default: start of string is not considered for matching): tail: Match string or numeric characters from the end (default: end of string is not considered for matching): rs: Upper size limit of regular pattern (default: 5): Column name with numerical data (multiple fields can be specified): Column name with categorical data (multiple fields can be specified): Column name of class: Output directory name (text, PMML model, and model statistics): Delimiter character of pattern (default: empty character, that is 1 byte character is regarded as 1 alphabet): Name of cost file
: Seed of random number (default=-1: time dependent): Number of patterns as explanatory variable (default=30,range:1〜256): Iterations of local search (default=1): Lower limit of the number of samples in one leaf (default: no limit): Specify the degree of pruning. However, when cv= or ts= is specified,
this parameter is disabled. Default=0.01.
: Specify the percentage of test data partitioned using the test sample method. When ”ts=” is not specified, the default v: Specify partition of data by cross-validation method. When ”cv=” is not specified, the default value is set as 10.
: If either ts=,cv= is not specified, default value of alpha=0.01 will be applied.
: Even when alpha=,ts=,cv=, is specified, pruning degree of maximum tree is recorded in PMML,: the value of alpha could change in prediction mode.
: Show help

28

2.3.4

CHAPTER 2. MINING MANUALSFormat 2: Prediction mode
mbonsai -predict i= I= o= [alpha=] [--help]-predicti=I=o=alpha=

delim=--help2.3.5: Operate in prediction mode. This parameter is required for prediction mode.
: Input data [required]: The column names must be the same as the columns that was used for building the model.
: Destination directory path for model building mode [required]: File required are as follows.
: bonsai.pmml: pmml containing the decision model: Output file name containing prediction result: The ”predict” column is added to the input data in output.
: Columns must be the same as columns that was used in building the model.
: Specify pruning complexity parameter.
: Accepts real number greater than 0, as well as the following two symbols with special functions.
: min: α value that corresponds to pruned model which minimizes the estimated misclassification rate.
: 1se: Alpha value that corresponds to the pruned model with the same 1SE rule.
: Designation of the two symbols is eﬀective only when ts= or cv= is specified when building the model.
: Default behavior:: If ts= or cv= is specified when building the model, min is used.
: If you specify alpha= when building the model, the specified value is applied.
: Delimiter character of pattern (default: empty character, that is 1 byte character is regarded as 1 alphabet): Show help

ExamplesExample 1 An example of building a model
In this example, since ts=,cv=,alpha= parameters are not specified, pruning is carried out when alpha=0.01,
the result is saved to the file model.txt.
$ more input.csv
BrandSequence,Churnbcaba,yes
bcabcaa,yes
aaabac,yes
caa,yes
cca,nocacbc,nobcc,noacca,no$ mbonsai p=BrandSequence:2 c=Churn i=input.csv O=result1$ more result1/model.txt[alphabet-index]
Field Name: BrandSequence
Index[1]={a}Index[2]={b,c}[decision tree]
if($BrandSequence has 11)
then $Churn=yes (hit/sup)=(3/3)
else if($BrandSequence has 2212)
then $Churn=yes (hit/sup)=(1/1)
else $Churn=no (hit/sup)=(4/4)
numberOfLeaves=3
deepestLevel&=& 2[Confusion Matrix by Training]## By countPredicted As \ldots

2.3. MBONSAI DECISION TREE GENERATED FROM SEQUENCE DATA

yes
no
Total

yes
4
0

no
0
4
4

4

Total
4
4
8

## By cost
Predicted As \ldots
yes
no
Total
yes
0
0
0
no
0
0
0
Total
0
0
0
## Detailed accuracy by classclass,recall,precision,FPrate,F-measure
yes,1,1,0,1
no,1,1,0,1## Summary
accuracy=1
totalCost=0$ more result1/model.pmml<?xml version="1.0" encoding="UTF-8"?><PMML version="4.0"><Header copyright="KGMOD"><Application name="mclassify" version="1.0"/><Timestamp>2014/07/20 23:00:13</Timestamp></Header><DataDictionary numberOfFields="2"><DataField name="BrandSequence" optype="categorical" dataType="string"><Value value="b"/><Value value="c"/><Value value="a"/></DataField><DataField name="Churn" optype="categorical" dataType="string"><Value value="yes"/><Value value="no"/></DataField></DataDictionary><TreeModel functionName="classification" splitCharacteristic="binarySplit"><MiningSchema><MiningField name="BrandSequence"><Extension extender="KGMOD" name="alphabetIndex"><alphabetIndex alphabet="b" index="2"/><alphabetIndex alphabet="c" index="1"/><alphabetIndex alphabet="a" index="2"/></Extension></MiningField><MiningField name="Churn" usageType="predicted"/></MiningSchema><Node id="0" score="yes" recordCount="8"><Extension extender="KGMOD" name="pruning" value="0.000000"/><True/><ScoreDistribution value="yes" recordCount="4"/><ScoreDistribution value="no" recordCount="4"/><Node id="1" score="yes" recordCount="4"><Extension extender="KGMOD" name="pruning" value="0.000000"/><Extension extender="KGMOD" name="patternPredicate" value="substring"><SimplePredicate field="BrandSequence" operator="contain"><index seqNo="1" value="2"/><index seqNo="2" value="2"/></SimplePredicate></Extension><ScoreDistribution value="yes" recordCount="4"/><ScoreDistribution value="no" recordCount="0"/></Node><Node id="2" score="no" recordCount="4"><Extension extender="KGMOD" name="pruning" value="0.000000"/><Extension extender="KGMOD" name="patternPredicate" value="substring"><SimplePredicate field="BrandSequence" operator="notcontain"><index seqNo="1" value="1"/><index seqNo="2" value="1"/></SimplePredicate>

29

30

CHAPTER 2. MINING MANUALS</Extension><ScoreDistribution value="yes" recordCount="0"/><ScoreDistribution value="no" recordCount="4"/></Node></Node></TreeModel></PMML>

Example 2 Predict unknown data with the model from example 1
This example predict unknown data (using training data and unknown data in the following) based on thedecision tree model constructed. The prediction result includes prediction accuracy of each class (yes,nocolumn), class name with the highest accuracy (predict column) is returned.
$ more unknown.csv
BrandSequence
bcaba
bcabcaaaaabac
caa
cca
cacbc
bcc
acca
$ mbonsai -predict i=unknown.csv I=result1 o=predict.csv$ more predict.csv
BrandSequence,predict,yes,nobcaba,yes,1,0
bcabcaa,yes,1,0
aaabac,yes,1,0caa,yes,1,0
cca,no,0,1
cacbc,no,0,1
bcc,no,0,1
acca,no,0,1

2.4. MGPMETIS.RB GRAPH PARTITIONING COMMAND

2.4

31

mgpmetis.rb Graph Partitioning Command

This command allows users to easily execute the graph partitioning software METIS developed by Universityof Minnesota (http://glaros.dtc.umn.edu/gkhome/metis/metis/overview). Given an undirected graph,
METIS partitions into finite elements (referred to as clusters below) containing the same number of nodes,
while minimising the number of branch cut required. In the data structure for direct handling by METIS, nodeis represented as integer, however, it can be represented by any character in this command. In addition, graphdata do not require a special format, edge and node data can be saved in CSV data. The CSV data will be
converted internally by mgpmetis command into a format which can be handled by METIS. It is also possible
to apply gpmetis command for data conversion into METIS format.
Input data is shown in Table 1, each row corresponds to an edge containing a node pair saved as CSV data.
There are no isolated nodes in the input data, when the weight (please refer to details below) of node is not
specified, only branch data is created. The corresponding graph is shown in Figure 1. For example, users can
execute the following command in order to partition the graph into two parts.
$ mgpmetis.rb kway=2 ef=node1,node2 ptype=rb ei=input.csv o=output.csv
The result is shown in 2, where the output contains the node name and the corresponding cluster number.
Figure 2 shows that the graph is partitioned into two parts by cutting the minimum number of edges.
Table 2.16: Input data (input.csv)
node1
a
a
a
b
b
c
c
d
d
e
f

node2
b
c
e
c
d
d
e
f
g
f
g

Table 2.17:
put.csv)

Partition output data (outnode
a
b
c
d
e
f
g

cluster
1
1
1
0
1
0
0

e!

e!

f!

a!

f!

a!

c!

c!

g!

g!
b!

b!

d!

d!

Figure 2.2: Results of two partition after minimum cut. Since there are 7
Figure 2.1: Graph of partition
nodes, partition closest to equal division is 4:3 partition, thus, this figure
targetshows minimally, 3 edges are removed to create the partitions.

2.4.1

Formatmgpmetis.rb kway= [ptype=rb|kway] ei= [ef=] [ew=] [ni=] [nf=] [nw=] [o=][balance=] [ncuts=] [dat=] [map=] [-noexe] [--help]

32

CHAPTER 2. MINING MANUALS

ei=
ef=
ew=
ni=
nf=
nw=
o=
kway=
ptype=
balance=ncuts=
dat=map=-noexe--help2.4.2: File name of branch (node pairs) [required]: Field name of node pair (two columns) in edge file [default: ”node1,node2”]:Field name of weight in edge file [optional: weight is 1 when this is not specified]: Weight must be specified as an integer.
: File name of node [optional]: Field name of node (1 column) in node file [default: ”node”]: Field name of weight in node file (multiple fields can be specified) [optional: weight is 1 when this is not specified]: Weight must be specified as an integer.
: Output file name [optional: default uses standard output ]: Number of divisions [required]: Partition algorithm [default: kway]: Balanced partition parameter [default: when ptype=rb 1.001, when ptype=kway is 1.03 ]: Specify the β value as shown in equation 2.
: The number of trials for initial value in partition phase [option: default=1]: File name of the data used for gpmetis command.
: File name of the mapping data of node number corresponding to node name specified in i= parameter used for gpmetis co: Do not execute gpmetis. This is used when only output data at dat=,map= parameters.
: Show help

Algorithm

gpmetis is a graph partition algorithm that can be divided into three processes namely 1) coarsening, 2)
partitioning 3) uncoarsening. During coarsening, the process of integrating multiple nodes connected by edges,
and reduces to small graphs consisting of hundreds of nodes. In the coarsened graph, it is possible to obtainbalanced partitions (with consideration of number of integrated nodes), while minimising the number of cut onedges. Finally, the uncoarsened process revert all partitioned nodes back to integrated nodes 3.
The features of gpmetis algorithm are as follows.
It becomes diﬃcult to solve a NP complete graph partitioning problem when the graph size increases. Therefore,
gpmetis avoid the bottleneck by applying coarsening during preprocessing to reduce the size of the graph.
However, since coarsening reduces the flexibility of diﬀerent ways to partition the graph, the general partition
accuracy (objective function that describes the minimisation of edge cut is described later) is decreased. Notethat the algorithm in gpmetis is an approximation algorithm, thus optimal solution is not guaranteed.

Figure 2.3: Conceptual diagram of multi-level graph partitioning (Refer to literature [2] of Figure 1). In
coarsening process, when the number of nodes reached several hundreds, original graph is reduced by merging
the nodes to build condensed, smaller graphs. The reduced graphs have uniform number of nodes, with minimal
number of edge cut for partition. In the uncoarsening process, the merged nodes are revert back to original. At
that time, the nodes between partitions are replaced to improve the minimum cut. In the figure, G2 and G′2
consists the same node set, yet the cut edge set is diﬀerent for partition purposes.

2.4. MGPMETIS.RB GRAPH PARTITIONING COMMAND

33

Problem Setting
In undirected graph G = (V, E), node set V has k number of partitions into V1 , V2 , . . . , Vk . In this case, the edges
attached to partition is minimized (minimize edge cut), the nodes belong to each partition are divided equally.
Generally, vertex u, v extends edge to (u, v) ∈ E with weight w(u, v) ≥ 0, weight of node v is represented as wv ,the function to minimize edge cut is represented in equation 1. In addition, by introducing constraints to unify
parameter β ≥ 1.0 allows creation of uniform partitions (equation 2). Balancing partitions corresponds to theratio of average number of nodes (weight) in partition to the biggest number of nodes (weight), thus a larger β
value allows for more unbalanced partition. β can be specified by balance= parameter in the command.
∑
V1 ,V2 ,...,Vkw(u, v)(2.12)≤β(2.13)(u,v)∈E∧u∈Vi ∧v∈Vj ∧i̸=jmaxi

subject to

∑
v∈Vi

∑k ∑
1
k

i=1

wv

v∈Vi

wv

Recursive bisection and k-way split
gpmetis adopt an algorithm suitable for NP-complete graph partition problem, instead of finding the optimal
solution, it is possible to apply multi-level partitioning, thereby making it possible to calculate increase ingraph size at real time. Multi-level partitioning generally follows several phases of the constructed algorithm.
By contracting the original graph (referred to as coarsening), graph is divided when it is at a suﬃciently small
size. Afterwards, when partition accuracy is improved (minimize edge cut), uncoarsening process will returnthe graph to original size.
gpmetis command comprised of two partition algorithm namely multi-level recursive bisection and multi-levelk-way partition. When a node set V is divided into k partitions, recursive bisection partition the original graphinto two subgraphs through “coarsening, partition, uncoarsening” phases, and recursively divides each of thepartition 1 .
Recursively bisection is shown in Algorithm1. On the other hand, in k-way split method, the graph is directly
partitioned into k parts after coarsening, and the process ends with uncoarsening. k-way partition is shownin Algorithm2. Either method provides excellent way of partition, in terms of execution time, k-way partition
method is superior since it does not perform recursive partition2 .
Algorithm 1 k split graph partition algorithm: Recursive bisection
1: function Bisect(G, P )2:
G : P artitiontargetgraph, P : P artitionset
3:
if size of G is 1/k then4:
P = P ∪ {G}
5:
else
6:
C=Coarsen(G)7:
C1 , C2 = 2wayPartition(C)8:
G1 , G2 = Uncoarsen(C1 , C2 )9:
P =Bisect(G1 , P )10:
P =Bisect(G2 , P )11:
end if12:
return P
13: end function▷ Coarsening▷ Coarsen graph bisection▷ Uncoarsen▷ G1 in recursion▷ G2 in recursion

1 Recursive partition do not multiply k by power of 2, weight of partitions are deliberately unbalanced so that it is possible todivide uniformly as a whole. For example, with |V | = 9, k = 3, it is initially partitioned into two parts at ratio of 3:6, afterwards,
the 6 graphs are recursively partitioned into 3:3. The details are not shown in Algorithm1.
2 Given k = 256, it is reported that it is 3 to 4 times faster [3].

34

CHAPTER 2. MINING MANUALS

Algorithm 2 k split graph partition algorithm: k-way partitioning method
1: function Kway(G)2:
G : P artitiontargetgraph
3:
C=Coarsen(G)4:
C1 , C2 , . . . , Ck = KwayPartition(C)5:
G1 , G2 , . . . , Gk = UncoarsenKway({C1 , C2 , . . . , Ck })6:
return {G1 , G2 , . . . , Gk }7: end function▷ Coarsening▷ Partition coarsened graph into k splits▷ k split during uncoarsening

In the following, Algorithm1,2 shows each sample function, Coarsen(), 2WayPartition(), KwayPartition(), Uncoarsen(), UncoarsenKway() with summary below. Please refer to [2] for details.

Coarsen function)
The purpose of coarsening is to reduce the size of the graph in order to perform partition eﬃciently. Coarsening
algorithm is common to both recursive bisection and k-way partition. The coarsening phase finds out maximal
matching M from the original graph G0 = (V0 , E0 ), each element (edge) is merged with new node if matched,
to create new graph G1 = (V1 , E1 ). Where graph G = (V, E) matches M , and subset of edge set E (M ⊆ E),
the vertices of any 2 edges e1 , e2 ∈ M does not share the same edge set with each other. When matching M , if
no more branches can be added, it is known as maximal matching. The above operation is applied recursively
until the node size is at several hundred, a series of coarsened graphs G1 , G2 , . . . , Gm are created. The details
on finding maximal matching algorithm is not described in gpmetis. However, note that this method is basedon a heuristic method using random numbers.

2WayPartition function, KwayPartition function)
Below details 2 way partition for the coarsened graph G = (V, E). Division of k number of partitions can beachieved by recursively applying bisection method. The bisection algorithm employed in gpmetis is very simple
and emphases on eﬃciency. First, select the initial node randomly from the node set V , and connect withanother added node, the process ends when only half a node (total weight) is added. When the node is added to
the node set, it is represented as P , there are two methods for P to add node v ∈ V \ P , they are GGP(Graph
Grawing Algorithm) andGGGP(Greedy Graph Growing Algorithm). GPP selects node v randomly. Yet in
GGGP, P is connected to V \ P at which node v has the greatest diﬀerence. Equation w(v, u) shows theedge extension weight between node v and u. GGGP use greedy algorithm to reduce the number of cut whenselecting node v. GGGP is applied in gpmetis by default, GGP is used when the weight constraints of node are
specified more than once.
gv =∑w(v, u) −(v,u)∈E∧u∈(P )∑w(v, u)(2.14)(v,u)∈E∧u∈(V \P )Uncoarsen function, UncoarsenKway function)
A series of coarsened graphs G1 , G2 , . . . , Gm are obtained through the coarsen process. The reverse direction(Gm , Gm−1 , . . .) returns the combined nodes and edges to the original state. Partition process Gm divides
into k partitions, if the partition is optimal, when Gm is returned to Gm−1 , it may become less than optimal
partitioning. Some of the nodes may be moved between partitions to improve partition accuracy (minimize
edge cut). The above process is repeated until G0 is obtained, which is the final solution of partition.

2.4. MGPMETIS.RB GRAPH PARTITIONING COMMAND

35

Other parameters
The coarsening, partition, uncoarsening algorithm use random number, diﬀerent result may be obtained bya series of random number. Therefore, when ncuts= parameter is specified, the process of coarsening to
uncoarsening is executed multiple times, thus it is possible to choose the best split. Recursive bisection method
repeats the number of times specified in line 6,7,8 of Algorithm1, and line 3, 4, 5 of Algorithm2.
In gpmetis, there are a number of parameters that can be used to control partitioning other than those fromthe mentioned algorithm. This command can handle some of the parameters. If you want to set parametersthat cannot be handled by this command, users can process data directly with METIS and create its processing
data with this command. Specify the output data used by METIS at dat= (node number is shown as integer
in data).

2.4.3

ExamplesExample 1. Example of the above illustration
Partition into two parts using recursive bisection method(ptype=rb). If the field name is not specified at ef=
in this command, field names of edge data is designated as node1,node2 by default.
$ more input.csv
node1,node2
a,b
a,c
a,e
b,c
b,d
c,d
c,e
d,f
d,g
e,f
f,g
$ mgpmetis.rb ei=input.csv o=output.csv kway=2 ptype=rb$ more output.csv
node,cluster
a,1
b,1
c,1
d,0
e,1
f,0
g,0

Example 2 . Specify node and edge weight
Use of weight in column v in edge.csv file, and column v in node.csv file.
$ more edge.csv
n1,n2,v
a,b,1
a,c,1
a,e,1
b,c,1
b,e,1
b,g,2
c,d,3
c,g,1
d,e,1
e,f,1
$ more node.csv
n,v
a,1
b,1
c,3

36

CHAPTER 2. MINING MANUALS

d,1
e,1
f,1
g,3
$ mgpmetis.rb ni=node.csv ei=edge.csv o=rsl.csv ptype=rb kway=2 ef=n1,n2 nf=n nw=v ew=v
$ more rsl.csv
n,cluster
a,1
b,1
c,0
d,0
e,1
f,1
g,1

Bibliography[1] C.M. ビショップ著, 元田浩, 栗田多喜夫, 樋口知之, 松本裕治, 村田昇（編）, Patten Recognition and Machine
Learning（II）：Statistical Prediction by Bayes Theory, Chapter 13, pp.323–370, 2008.
[2] Karypis, G. and Kumar, V., ”A fast and high quality multilevel scheme for partitioning irregular graphs”,
SIAM Journal on Scientific Computing 20 (1), pp.359–392, 1999.
[3] Karypis, G. and Kumar, V., ”Multilevel k-way Partitioning Scheme for Irregular Graphs”, Journal of Paralleland Distributed Compupting 48, pp.96–129, 1998.
[4] S. Shimozono, A. Shinohara, T. Shinohara, S. Miyano, S. Kuhara and S. Arikawa, Knowledge Acquisition
from Amino Acid Sequences by Machine Learning System BONSAI, Trans. Information Processing Societyof Japan, Vol. 35, pp. 2009-2018, 1994.
[5] J. R. Quinlan, C4.5: Programs for Machine Learning, San Meteo: Morgan Kaufmann, 1993.
[6] L. Breiman, J. Friedman, R. Olshen, C. Stone Classification and regression trees, Wadsworth: Belmont, CA,
1984.

37