Chapter 2

Concepts and Terminology
2.1

Machine Learning and Data Mining

We will describe a high-level abstract on machine learning and data mining (alsoadditionally bioinformatics), introducing key terms to be used. These terms are
explained later more. Readers, particularly entry-level machine learners, are recommended to go through this chapter without thinking to understand the terms
fully within this chapter.
Two terms, Machine Learning and Data Mining, can be considered interchangeably, like that they are synonyms. We then use the term “machine learning” mainly, while data mining are more application-oriented, and we use eitherof these two terms, depending on situations.
Data, input of machine learning, are a set of records, each being called an
instance, example or sample. We use the “instance” among them through thisbook. One instance has features, variables or variates, where these features arevisible and unchanged (during learning) and so called observable variables.
Occasionally instances can be classiﬁed into more than one categories, typicallytwo (binary). Here are two examples:
Example 1: Mobile phone customers of some company can be segmented into
at least the following two: current subscribers and former subscribers (thoughcurrent subscribers might be categorized into more details, due to the risk ofleaving. Also promising subscribers among totally non-subscribers would be also
a possible, important category for mobile phone companies).
Example 2: Regarding some disorder, patients and healthy people (also patientswould be categorized into more, due to the seriousness of the disorder).
As such, when instances can be segmented into categories, each category iscalled a class, and each of the above current subscribers, former subscribers, patients and healthy people, etc. is called a label. The label is the name of a class,and if there are ﬁve labels, this means there exist ﬁve classes. Here are more

CHAPTER 2. CONCEPTS AND TERMINOLOGY

4

examples:Example 3: A customer is an instance, where the evaluation by one customer
against some item is a label. Also even if a customer buys an item, this is alreadya label, to ﬁll the corresponding part of the data.
Example 4: A gene is an instance, where its function can be a label.
In Example 3, the evaluation can be binary or some moderate-size number,
like a ﬁve-stage, while in Example 4, the functions of genes cannot be even bysuch a small number but a larger number. These two examples imply that labels
would not be necessarily assigned to all instances (or functions are not necessarily
assigned to all genes), implying that assigning labels or functions to genes would
be a possible problem setting. This means that a label is a value of one feature
which should be predicted in machine learning.
Again all instances do not necessarily have labels, because obtaining labels is
expensive. For example, in Example 3, we need to ask customers to give someevaluation against some item. Also we need some biological experiments to annotate functions to genes in life sciences, which needs cost and also time, which
in some cases might not be good enough if it is really hard to ﬁnd functions ofgenes.
Thus in machine learning we have a paradigm which do not assume classes
and labels. This setting is called unsupervised learning, where the objective is tounderstand the data distribution or more generally to summarize data. A typicalapproach for summarizing data is clustering, where instances are grouped into
several clusters. Clusters are diﬀerent from observable variable like features andvariables where their values can be trained from given data. Thus this variable iscalled a latent variable. Estimating latent variables means clustering.
On the other hand, we call learning using labels supervised learning, where
inputs are features of instances and estimate a function to predict the label. Thisfunction is called a hypothesis, model, classiﬁer or predictor. Note that model is
not only the concept for supervised learning but also for estimating distributionin unsupervised learning. This function has parameters, where the values of parameters are trained (learned or estimated) by using input data, and the trained
hypothesis is used to predict labels of unknown instances (or data). The ﬁrst
input data are called training data and the second is called test data.
Estimating a model from given training data means, for example, to keep thevalues given by the model closest to those of training data. Thus we can set
up an objective function, for example, in supervised learning, being consistent
with the error of the model from training data, i.e. an error function or loss
function. We can then minimize the objective function, which turns into an
optimization problem, like minimizing the error function. The optimization interms of training data only causes overﬁtting of the model to the training data.
Avoiding that, the model needs to be generalized, which is called generalization
or regularization. In practice, we add one or more constraints to the objectivefunction, where the constraints are, mathematically, terms, called regularizers or

CHAPTER 2. CONCEPTS AND TERMINOLOGY

5

Table 2.1: Data in life sciences.

gene

proteinchemical compound(e.g. drug)
glycandata types
vectorsequence (string)node in graphsequence (string)node in graph(molecular) graphnode in graphtree

examplesgene expression
nucleic acid sequence
gene regulatory network
amino acid sequence
protein-protein interaction network
chemical structure
metabolic pathway
sequence structure

regularization terms. Thus to solve some problem, we can set up an objectivefunction with regularizers, which we often call problem formulation. Usually inmachine learning model formulation, model parameters to be estimated are ineither the objective function or regularizers. Also model formulation sometimes
has hyperparameters, which are given arbitrary by users or decided empirically but
not trained from input data. For example, in model formulation, the coeﬃcientsof regularizers, called regularization coeﬃcients are one typical hyperparameter.
We call values, which are clearly diﬀerent from the data distribution, an outlier.
Now let’s get back to Example 3, where the situation is an E-commerce site.
It would not be the case that an customer has bought almost all items in the
E-commerce site, while usually most customers bought only just a few goods inthe site. Thus the data from E-commerce, i.e. a matrix of users (rows) and items(columns) has only a small number of elements, ﬁlled by some values, showing thegoods evaluation by customers or just the user purchase history. More concretely
the row vectors or users have only a few number of values, with others being
missing information. This situation of data is called sparse data, and interestingly
sometimes this data sparsity is useful to solve the problem eﬃciently even if thegiven matrix is huge.

2.2

Bioinformatics: Connections to Data Types

Bioinformatics is the study on data in life sciences, particularly molecular biology,
so the focus being placed on molecules working in cells, such as genes, proteins,chemical compounds, etc. We can describe data formats of those molecules which
are regarded as multiple ways even for one single molecule type, depending on
situations.
Gene is the most attention-paid term in life sciences. Recent so-called highthroughput techniques allow to measure the expression of thousands of genes incells simultaneously. The measurement can be performed under many diﬀerent
conditions, which results in numerical vectors of genes. At the same time, physically genes are nucleic acids, consisting of four bases (represented by four letters:

CHAPTER 2. CONCEPTS AND TERMINOLOGY

6

A, T, C, G), which are building blocks of nucleic acid sequences. Simply speaking
they are sequences or strings of four letters. Proteins can be generated, following
the expression of genes, by which the term “gene” is used in most cases, insteadof protein. For example, gene function means the function of the corresponding
protein. Physically proteins are also sequences, while building blocks of proteinsare 20 diﬀerent types of amino acids, by which sequences of proteins are aminoacid sequences or strings of 20 letters. Another aspect of genes is gene regulation,
which are eventually represented by a graph, called gene regulatory network, inwhich nodes are genes and an edge shows that a gene is regulated by anothergene. Similarly one aspect of proteins is three-dimensional binding between two
or more proteins, which are called protein-protein interactions, also usually being
represented by a graph with nodes of proteins and edges of interactions.
Glycans are called the third molecule in cells, next to nucleic acids and proteins.
Building blocks of glycans are monosaccharides, and glycan sequences are generated by the connection of monosaccharides. The diﬀerence of glycan sequencesfrom gene sequences is that glycans allow to have branches (but no cycles) in theirsequences, which results in glycan trees.
Nucleic acids of genes, amino acids of proteins and monosaccharides of glycans
are all chemical compounds, and so molecules. The chemical structure of molecules
are graphs, so-called molecular graph, meaning that chemical compounds can bepresented by graphs. On the other hand, for example, metabolic network is a collection of chemical reactions in cells and shows the process of generating chemicalcompounds from other compounds. Thus chemical compounds can be nodes in
the graph of metabolic network.
Table 2.1 shows the summary of molecules in cells and their possible data
formats. As you can see from this table, bioinformatics data can be ﬁve types.
When we think about general applications of machine learning and data mining,
we can add one more data type, sets, to them, resulting in six types: vectors,
sets, sequences (strings), trees, graphs and nodes in a graph. These data types
are explained in more detail in the next section.

2.3

Six Types of Data

Data can be categorized into six types, partially according to the observation on
the life science data. This book is organized according to the six data types, soeach chapter being for each data type, as follows:
Chapter 3: Vectors
Chapter 4: Sets
Chapter 5: Sequences (strings)
Chapter 6: Trees
Chapter 7: Graphs
Chapter 8: Nodes in a graphCHAPTER 2. CONCEPTS AND TERMINOLOGY

Instance 1
Instance 2...

Feature 1
A
A

Feature 2
B
C

Feature 3
CC

7
Feature 4
DC

Figure 2.1: Instances, each being a vector, are a matrix.

Instance 1: {A, B, C, D},

Instance 2: {D, C, B, A}

Figure 2.2: Two instances, each being a set.
Chapter 9 is then on machine learning for data integration.

2.3.1

Vectors

When each instance has multiple features, the simplest and most frequent data inmachine learning and data mining is vectors, where each instance has always a certain number of features. Fig. 2.1 shows an illustrative example of vectors (calledfeature vectors) for each instance, resulting in a matrix for multiple instances.
Here are features, terminology and examples:
Building blocks: are feature values, which can be either discrete or continuous.
Fixed length and order: The length of a vector is ﬁxed, and also a sort offeature values are ordered, meaning that for example, if Feature 1 in Fig.
2.1 is ﬁxed to be a binary taking A or B, all ﬁrst values of instances in thisdataset must be A or B.
Example 1: demographic data: One instance is an individual, where features
are age, gender, etc.
Example 2: gene expression: One instance is a gene, and features are experimental conditions, under which expression of the corresponding gene aremeasured. Each matrix element is the expression value of the corresponding gene and the corresponding experimental condition.

2.3.2

Sets

Each instance is a set, and input data is a set of sets. Sets are the most ﬂexible
machine learning data type. One set, i.e. an instance, can have an arbitrary
number of elements, without any order. Fig. 2.2 shows an illustrative examplesof sets. Here are features, terminology and examples:
Building blocks: One set has elements, which can be discrete or continuous
values.

CHAPTER 2. CONCEPTS AND TERMINOLOGY

Instance 1: DCBA,

8

Instance 2: ADBCA

Figure 2.3: Two instances, each being a sequence.
No order in elements: We focus on discrete values for elements. Elements haveno order, and so for example, in Fig. 2.2, {A, B, C, D} and {D, C, B, A}
are the same.
No ﬁxed size of elements: Each instance has its own size. We can say thatsets are more general than vectors, and vectors are a special case of sets, inthe sense that the size and order of features in sets are both ﬁxed in vectors.
Example: Market basket: One typical example is market basket, which is aset of items bought by one customer at a department store, a convenience
store or an E-commerce site per time. By focusing on a certain number of
items, one set can be a vector. In general the number of items is always
very large, while each user buys only a few number of items, which makes
the data very sparse. In fact elements of a matrix of users vs. items aremostly missing.

2.3.3

Sequences and Strings

When elements in one set are ordered, the set becomes a sequence. In particularelements are a ﬁnite number of letters, such as the alphabet, the sequence is astring (see below in some more detail). The size of elements in a set, i.e. thelength of a sequence, is changeable over diﬀerent instances.
Thus again the sequence is a special case of a set, while the length of eachsequence is not ﬁxed, meaning that a vector is a further special case of a sequence. Fig. 2.3 shows an illustrative example of sequences. Below we describe
the deﬁnition and terminology of sequences.
Discrete element for sequences: Discrete elements of sequences are called letters or characters. The set of letters is called the alphabet. A sequence ofletters is called a string.
Subsequence and substring: A consecutive part of a sequence is called a subsequence. Also a consecutive part of a string is called a substring. For
example, in Instance 1 of Fig. 2.3, DC and DCB are substrings, while DCA,
i.e. the ﬁrst, second and fourth letters, is not a substring.
Example 1: natural language: Typical sequence examples are natural language, which are the main data of computational linguistics, natural language processing and speech recognition, etc., which are classical applications of machine learning.

CHAPTER 2. CONCEPTS AND TERMINOLOGY9%,QVWDQFH'&,QVWDQFH

$

$

&

%

$

'

%

Figure 2.4: Two instances, each being a tree.
Example 2: gene sequence: A nucleic acid sequence can be a string of four
letters (corresponding to four types of nucleic acids). Similarly an aminoacid sequence can be a string of twenty letters (corresponding to twenty
amino acids). The length of one sequence/string can be diﬀerent.

2.3.4

Trees

Each instance is a tree, and so the input data is a set of trees. Description oftrees can be easier if graphs are already deﬁned, and so suppose that graphs are
already deﬁned, trees are graphs without any cycling edges (or cycles).
Fig. 2.4 shows illustrative examples of trees, where Instance 1 has a branchfrom C to B and also to A, and similarly Instance 2 has a branch from B to C
and A. Here are more terminology and features of trees:
Building blocks: A tree consists of nodes and edges.
Cycles: No cycles of edges in trees. This discriminates trees from graphs.
Labels: A tree with labels is called a labeled tree. For example, in Fig. 2.4, A,
B, C and D are labels. We consider labeled trees.
Root: In general, any node of a tree can be a root, while a tree is called a rooted
tree, if one node of the tree is ﬁxed as the root. For example, D of Instance
1 is ﬁxed as the root, and A of Instance 2 is ﬁxed as the root. We focus onrooted trees, and so we consider labeled rooted trees.
Leaves and internal nodes: In the rooted tree, except the root, we regard allnodes with only one edge as leaves. Nodes except leaves and the root are
called internal nodes.
Ordered tree: For a rooted tree, nodes can be ordered from the root to leaves,and the tree is an ordered tree. Ordered trees are generated by allowing
branches in sequences. In other words, sequences are a special case of ordered trees, by not allowing any branches.
Parent-children: In the rooted tree, for two nodes connected by an edge, thenode closer to the root is called parent and the other node is called a child.
Comparing with sequences, a feature of trees is a parent can have more than
one children, while in sequences (and strings), a parent can have only one.
Also the root cannot have a parent. In ordered trees, the parent to childdirection is regarded as the order.

CHAPTER 2. CONCEPTS AND TERMINOLOGY

10
&

'
%

,QVWDQFH'$,QVWDQFH

$

%

%
$

'

Figure 2.5: Two instances, each being a graph.
Siblings, ancestors and descendants: Nodes with the same parent are called
siblings. For a child, its parent and any node of the parent side are allancestors. Similarly for a parent, its children and any node of the children
side are all descendants.
Depth: The number of edges from the root is called the depth. Usually the depthof the root is zero. The nodes with the same depth are called nodes at thesame layer. On the other hand, the number of edges from a leaf is called
the height. Usually the height of an leaf is zero.
Direction of edge: In ordered trees, usually the direction is from the root toleaves.
Subtree: We explain regular deﬁnition of subtree below, while in frequent subtree mining, subtree means any connected part of a tree. This deﬁnition
is diﬀerent from the regular deﬁnition (see Section 6.3 for more detail). In
fact the regular deﬁnition is based on the deﬁnition of subsequence in sequences/strings, while the above deﬁnition (any part of a tree) is derived
from the deﬁnition of subgraph in graphs.
A subtree, a part of a tree, has some node (of the original tree) as the root(of this subtree) and also all nodes and edges of the leaf side of the root. For
example, in Instance 2 of Fig. 2.4, if the root is the most left-hand side A,
CB and AD of the most right-hand side can be subtrees, while BAD cannot
be a subtree, because if B is speciﬁed as the root of a subtree, the subtree
must be B(AD)CB.
Example: glycan (carbohydrate sugar chain): Building blocks of glycans
are around 10 to 15 types of monosaccharides, which can be letters (labels). Glycan is generated by the connection (binding) of these monosaccharides, and the connection allows branches, resulting in trees with labelsof monosaccharides. Glycans will be explained more in Section 6.4.

2.3.5

Graphs

One instance is a graph and input data are a set of graphs. Fig. 2.5 shows
illustrative examples of graphs. Comparing with trees, one important feature ofgraphs is that graphs have cycles. For example, in Instance 1 of Fig. 2.5, two D

CHAPTER 2. CONCEPTS AND TERMINOLOGY

11

and B are connected each other in the left-hand side, which turns into a cycle.
This is not allowed in a tree, and trees are a special case of graphs. Below arefeatures, terminology and examples of graphs:
Building blocks: A graph consists of nodes and edges connecting nodes.
Degree: The number of edges connecting to one node is called the degree of thenode.
Labels: A graph with labels is called a labeled graph. Instances in Fig. 2.5 are
two labeled graphs.
Direction of edges: If edges have some direction, the graph is called a directed
graph, while if no directions, the graph is called an undirected graph.
Cycles: In graphs, any connection is allowed, and so it is possible to start withsome node and come back to the same node along with edges. This is calleda cycle. Also the cycle allows to go from a node to another node by using
more than one routes (edge connections). Again graphs with no cycles aretrees, meaning that there is always only one route in a tree if going from
one node to another.
Subgraph: A part of a graph is called a subgraph. If all nodes and edges areconnected each other in a subgraph, the subgraphs is called a connected
subgraph. We consider only connected subgraphs as subgraphs.
Spanning tree: A tree with all nodes of a undirected graph is called a spanning
tree. This is an important concept to deal with a graph eﬃciently.
Isomorphism: If two graphs have the same structure in terms of nodes and edge
connectivity, they are called isomorphic.
Example: chemical structure of chemical compounds: The types of (physical) elements of chemical compounds are limited and so can be labels. Thenthe chemical structure (called a molecular graph) of a chemical compound
can be regarded as a labeled graph.

2.3.6

Nodes in a Graph

Input data is a graph, and one instance is a node in the graph. Fig. 2.6 showsa simple, illustrative example. Nodes are instances, meaning that nodes are all
unique (Note that this does not mean that labels of nodes are all diﬀerent). Also
all nodes in one graph is a set of all instances.
Example 1: social network: A social network is a graph with nodes for individuals and edges for some relationship between the individuals connectedby the corresponding edges. Note that nodes are all unique, and they canbe assigned by a limited number of labels, such as a male or a female.

CHAPTER 2. CONCEPTS AND TERMINOLOGY

12

Example 2: gene regulatory network: A gene regulatory network is a collection of molecular-level biological knowledge on gene regulations, such asthat gene A is regulated by gene C. Regarding gene regulations as binary
relations, i.e. two nodes connected by one edge, a graph with all binary
relations of gene regulations is a gene regulatory network, where nodes are
all unique genes. Again in this case also, genes can be with a limited numberof labels, such as gene functions.

2.3.7

Notes on Data Types

Structured and Semi-structured Data
The most typical data in machine learning, i.e. vectors, are called structured data,
while others are called semi-structured data. We think that the term structured
data are derived from the fact that vectors can be organized well into a matrix
with lows for instances and columns for features. However, sometimes even inmachine learning and data mining publications, these two terms, i.e. structured
and semi-structured data, are used in diﬀerent ways, such as structured data forgraphs. Thus you can be careful when you come across the term “structured
data”.
Structured data or vectors were long-time the major data in machine learning,
while semi-structured data are relatively new in machine learning, except for
sequences and strings (which have been used in applications of machine learning,such as speech recognition, natural language processing and bioinformatics).
Inclusion Relations among Data Types
Let SV , SS , SQ , ST and SG be all possible data of vectors, sets, sequences, trees
and graphs, respectively.
If elements of a set are ordered, the elements become a sequence (or a string),and so sequences are part of sets. Also the size (length) of elements in a set(sequence) is ﬁxed over all instances, vectors are part of sets (sequences). Thisobservation leads to the following inclusion relations:S S ⊇ SQ ⊇ SV

(2.1)

Trees are graphs without cycles, indicating that trees are a special case ofgraphs. Ordered trees are a subset of trees. Sequences are ordered trees without
any branches, meaning that sequences are a special case of ordered trees. Thusin summary the following relations come out:
SG ⊇ ST ⊇ SOT ⊇ SQ ,(2.2)

where SOT is all data of ordered trees.
Data Transformation
In the above relations, when one data type, say A, can be deﬁned by some constraint on another data type, say B, if the constraint is removed, A becomes B.

CHAPTER 2. CONCEPTS AND TERMINOLOGY

13

For example, if the order of elements in sequences is removed, the sequences canbe sets. More practically, two sequences, ATCG and ACGT, can be the same set{A, C, G, T} if we remove the order of letters in sequences,
In general however this type of transformation are not performed, because
clearly this transformation loses some important information. For example, in
the above toy example, originally ATCG and ACGT are diﬀerent, and the orderof letters is deﬁnitely good information to discriminate them.
Thus simply speaking some appropriate machine learning method should be
developed for each data type.
Machine Learning for Diﬀerent Data Types
However machine learning algorithms for some data type with less constraints canbe applied to another data type with more constraints rather easily sometimes.
On the other hand, applying some algorithm with more constraints to those withless constraints is not easy or impossible. For example, an algorithm for graphs
can be applied to ordered trees or sequences just by considering the order of nodesof simpler graphs, while an algorithm for trees or sequences cannot be applied tographs so easily.
Also even if one algorithm can be applied to another data type, like that analgorithm for graphs can be applied to sequences, this would never be the best,
because the algorithm for sequences can be designed as a more eﬃcient one usually.
Thus again, thinking about the method most proper for each data type would be
an important aspect of machine learning and data mining.

2.4

Structure of This Book

Machine learning and data mining methods/ algorithms are summarized for eachof the above six data types, and so there are six chapters on vectors, sets, sequences, trees, graphs and nodes on a graph. Then after the six chapters, wehave one chapter which focuses on more than one data types, which are calledby many ways in machine learning, such as data fusion, multiview learning, etc.
On the other hand, we call all methods for data integration and machine learning
data-integrative machine learning methods.

CHAPTER 2. CONCEPTS AND TERMINOLOGY

14