The paper presents an utilization of formal concept analysis in input data preprocessing for machine learning. Two preprocessing methods are presented. The first one consists in extending the set of attributes describing objects in input data table by new attributes and the second one consists in replacing the attributes by new attributes. In both methods the new attributes are defined by certain formal concepts computed from input data table. Selected formal concepts are so-called factor concepts obtained by boolean factor analysis, recently described by FCA. The ML method used to demonstrate the ideas is decision tree induction. The experimental evaluation and comparison of performance of decision trees induced from original and preprocessed input data is performed with standard decision tree induction algorithms ID3 and C4.5 on several benchmark datasets.
Formal concept analysis (FCA) if ofted proposed to be used as a method for data
preprocessing before the data is processed by another data mining or machine
learning method [
The paper presents a data preprocessing method utilizing formal concept
analysis in a way that certain formal concepts are used to create new attributes
describing the original objects. Selected formal concepts are so-called factor
concepts obtained by boolean factor analysis, recently described by means of FCA
in [
There have been several attempts to transform the attribute space in order
to improve the results of data mining and machine learning methods. From
the variety of these methods we focus on decision tree induction. The most
relevant to our paper is are methods known as constructive induction or feature
construction [
Interestingly, we have not found any paper solely on this subject utilizing
formal concept analysis. There have been several FCA-based approaches on
construction of a whole learning model, commonly called lattice-based or
conceptbased machine learning approaches, e.g. [
The remainder of the paper is organized as follows. The next section contains preliminaries from FCA and introduction to boolean factor analysis, including the necessary tranformations between attribute and factor spaces. The main part of the paper is section 3 demonstrating the above sketched ideas on selected machine mearning method – decision tree induction. An experimental evaluation on selected data mining and machine learning benchmark datasets is provided in section 4. Finally, section 5 draws the conclusion. 2 2.1
Formal Concept Analysis
In this section we summarize basic notions of FCA. For further information we
refer to [
A↑ = {y ∈ Y | for each x ∈ A : hx, yi ∈ I}, B↓ = {x ∈ X | for each y ∈ B : hx, yi ∈ I}. That is, A↑ is the set of all attributes from Y shared by all objects from A (and similarly for B↓). A formal concept in hX, Y, Ii is a pair hA, Bi of A ⊆ X and B ⊆ Y satisfying A↑ = B and B↓ = A. That is, a formal concept consists of a set A (so-called extent) of objects which are covered by the concept and a set B (so-called intent) of attributes which are covered by the concept such that A is the set of all objects sharing all attributes from B and, conversely, B is the collection of all attributes from Y shared by all objects from A. Formal concepts represent clusters hidden in object-attribute data.
A set B(X, Y, I) = {hA, Bi | A↑ = B, B↓ = A} of all formal concepts in hX, Y, Ii can be equipped with a partial order ≤. The partial order models a subconcept-superconcept hierarchy, e.g. dog ≤ mammal, and is defined by hA1, B1i ≤ hA2, B2i iff A1 ⊆ A2 (iff B2 ⊆ B1).
B(X, Y, I) equipped with ≤ happens to be a complete lattice, called the concept
lattice of hX, Y, Ii. The basic structure of concept lattices is described by the
so-called basic theorem of concept lattices, see [
Boolean Factor Analysis
Boolean factor analysis is a matrix decomposition method which provides a
representation of an object-attribute data matrix by a product of two different
matrices, one describing objects by new attributes or factors, and the other
describing factors by the original attributes [
Recall that a binary (or boolean) matrix is a matrix whose entries are 0 or 1. A boolean matrix product A ◦ B of binary matrices A and B is defined by k (A ◦ B)ij = _ Ail · Blj , l=1 where W denotes maximum and · is the usual product. The interperetations of matrices A and B is: Ail = 1 means that factor l applies to object i and Blj = 1 means that attribute j is one of the manifestations of factor l. Then A ◦ B says: “object i has attribute j if and only if there is a factor l such that l applies to i and j is one of the manifestations of l”. As an example, 1 1 0 0 0 1 0 0 1 1 1 0 0 0 1 1 0 0 1 1 0 1 0 0 0 1 1 0 . 1 1 1 1 0 = 1 1 0 0 ◦ 1 0 0 0 1
1 0 0 0 1 0 0 1 0 0 1 0 0 0
The (solution to the) problem of decomposition binary matrices was recently
described by means of formal concept analysis [
F = {hA1, B1i, . . . , hAk, Bki} ⊆ B(X, Y, I), then for the n × k and k × m matrices AF and BF defined in such a way that the l-th column (AF ) l of AF consists of the characteristic vector of Al and the l-th row (BF )l of BF consists of the characteristic vector of Bl the following universality theorem holds: Theorem 1. For every I there is F ⊆ B(X, Y, I) such that I = AF ◦ BF .
Moreover, decompositions using formal concepts as factors are optimal in that they yield the least number of factors possible: Theorem 2. Let I = A ◦ B for n × k and k × m binary matrices A and B. Then there exists a set F ⊆ B(X, Y, I) of formal concepts of I with
|F | ≤ k
I = AF ◦ BF . such that for the n × |F | and |F | × m binary matrices AF and BF we have
Formal concepts F in the above theorems are called factor concepts. Each
factor concept determines a factor. For the constructive proof of the last theorem,
examples and further results, we refer to [
Transformations between attribute and factor spaces For every object i we can consider its representations in the m-dimensional Boolean space {0, 1}m of original attributes and in the k-dimensional Boolean space {0, 1}k of factors. In the space of attributes, the vector representing object i is the i-th row of the input data matrix I, and in the space of factors, the vector representing i is the i-th row of the matrix A.
Natural transformations between the space of attributes and the space of factors is described by the mappings g : {0, 1}m → {0, 1}k and h : {0, 1}k → {0, 1}m defined for P ∈ {0, 1}m and Q ∈ {0, 1}k by
m (g(P ))l = ^ (Blj → Pj ), (1) j=1 k (h(Q))j = _(Ql · Blj ), (2)
l=1 for 1 ≤ l ≤ k and 1 ≤ j ≤ m. Here, → denotes the truth function of classical implication (1 → 0 = 0, otherwise 1), · denotes the usual product, and V and W denote minimum and maximum, respectively. (1) says that the l-th component of g(P ) ∈ {0, 1}k is 1 if and only if for every attribute j, Pj = 1 for all positions j for which Blj = 1, i.e. the l-th row of B is included in P . (2) says that the j-th component of h(Q) ∈ {0, 1}m is 1 if and only if there is factor l such that Ql = 1 and Blj = 1, i.e. attribute j is a manifestation of at least one factor from Q.
For results showing properties and describing the geometry behind the
mappings g and h, see [
The machine learning method which we use in this paper to demonstrate the ideas presented in section 1 is decision tree induction. 3.1
Decision Trees
Decision trees represent the most commonly used method in data mining and
machine learning [
Each non-leaf tree node of a decision tree is labeled by an attribute, called a splitting attribute for this node. Such a node represents a test, according to which objects covered by the node are split into v subcollections which correspond to v possible outcomes of the test. In the basic setting, the outcomes are represented by values of the splitting attribute. Leaf nodes of the tree represent collections of objects all of which, or the majority of which, have the same class label. An example of a decision tree is depicted in Fig. 4.
Many algorithms for the construction of decision trees were proposed in the
literature, see e.g. [
Remark 1. In machine learning, and in decision trees at particular, the input
data attributes are very often categorical attributes. To utilize FCA with the
input data, we need to transform the categorical attributes to binary attributes
because, in its basic setting, FCA works with binary attributes. A
transformation of input data which consists in replacing non-binary attributes into binary
ones is called conceptual scaling in FCA [
Throughout this paper, we use input data from Fig. 1 (top) to illustrate the data preprocessing. The data table contains sample animals described by attributes body temperature, gives birth, fourlegged, hibernates, and mammal, with the last attribute being the class. After an obvious transformation (nominal scaling) of the input attributes, we obtain the data depicted in Fig. 1 (bottom). Boolean factor analysis which we use in our method is applied on data which we obtain after such transformation. For illustration, the decision tree induced from the data is depicted in Fig. 4 (left).
Extending the collection of attributes The first approach proposed in our data preprocessing method is the extension of the collection of attributes by new attributes which are created using boolean factor analysis. In praticular, the new attributes are represented by factors obtained from the decomposition of input data table.
Let I ⊆ X × Y be input data table describing objects X = {x1, . . . , xn} by binary attributes Y = {y1, . . . , ym}. Considering I as a n × m binary matrix, we find a decomposition I = A ◦ B of I into the n × k matrix A describing objects by factors F = {f1, . . . , fk} and k × m matrix B explaining factors F by attributes. The decomposition of example data table in Fig. 1 is depicted in Fig. 2. The new collection of attributes Y ′ is then defined to be Y ′ = Y ∪ F and the extended data table I′ ⊆ X × Y ′ is defined by I′ ∩ (X × Y ) = I and I′ ∩ (X × F ) = A. Hence the new collection of attributes is the union of original attributes and factors and the extended data table is the apposition of original data table and the table representing the matrix describing objects by factors. Fig. 3 depicts the extended data table.
The key part is the decomposition of the original data table. In the decomposition of binary matrices the aim is to find the decomposition with the number of factors as small as possible. However, since the factors, as new attributes, are used in the process of decision tree induction in our application, we are looking B0 00 11 00 11 10 01 01 10 C1 B0 0 0 1 0 0 1 1 B0 10 01 01 10 11 00 11 00 C1 BB 1 0 1 0 0 1 0 1 CC = BB 00 00 01 10 01 00 CCC ◦ BB 0 1 0 1 0 0 0 0 CC
B@ 01 10 10 01 11 00 11 00 CA B@ 10 01 00 00 00 00 CA B@BB 010 101 010 101 100 011 001 110 CACC
also for the factors which have a good “decision ability”, i.e. that the factors are
good candidates to be splitting attributes. To compute the decomposition we
can use the algorithms presented in [
The new criterion function c : 2X×Y → [
E(class|A) · 1 |X| − log2 |V (class|A)| + |X \ A| |X| ·
E(class|X \ A)
1 − log2 |V (class|X\A)| where V (class|A) is the set of class labels assigned to objects A and E(class|A) is the entropy of objects A based on the class defined as usual by:
X
l∈V (class|A)
E(class|A) = −
p(l|A) · log2 p(l|A),
where p(l|A) is the fraction of objects A with assigned class label l. The value
1
of − log2 |V (class|A)| in (4) is the maximal possible value of entropy of objects A
in the case the class labels V (class|A) are assigned to objects A evenly and the
purpose of it is to normalize the value of cB to the interval [
Now, having the extended data table I′ ⊆ X × (Y ∪ F ) containing new attributes F , the decision tree is induced from the extended data table instead of the original data table I. The class labels assigned to objects remain unchanged, see Fig. 3. For ilustration, the decision tree induced from data table in Fig. 3 is depicted in Fig. 4 (right). We can see that the data can be decided by a single attribute, namely, factor f3 the manifestations of which are original attributes bt warm and gb yes. Factor f3, as the combination of the two attributes, is a better splitting attribute in decision tree induction than the two attributes alone. ! , (4) (5) no no
warm gives birth body temp. yes yes cold no
1 yes f3 0 no
The resulted decision tree is used as follows. When classifying an object x described by original attributes Y as a vector Px ∈ {0, 1}m in the (original) attribute space, we first need to compute the description of the object by new attributes/factors F as a vector g(Px) ∈ {0, 1}k in the factor space. This is accomplished by (1) using the matrix B explaining factors in terms of original attributes. The object described by concatenation of Px and g(Px) is then classified by the decision tree in a usual way.
For instance, an object described by original attributes Y as vector (10011010)Y is described by factors F as vector (010000)F . The object described by concatenation of these two vectors is classified by class label no by the decision tree in Fig. 4 (right). 3.3
Reducing the collection of attributes The second approach consits in the replacement of original attributes by factors, i.e. discarding the original data table. Hence the new collection of attributes Y ′ is defined to be Y ′ = F and the new data table I′ ⊆ X × Y ′ is put to I′ = A, where A is the n × k binary matrix describing objects by factor resulting from the decomposition I = A ◦ B of input data table I. Hence the new reduced data table for example data in Fig. 1 is a table depicted in Fig. 3 restricted to attributes f1, . . . , f6.
Since the number of factors is usually smaller than the number of attributes,
see [
Consider the relation ker(g) (the kernel relation of g) describing such a situation. The class [x]ker(g) ∈ X/ker(g) for an object x ∈ X contains objects represented in (original) attribute space which are mapped to the same object x represented in factor space. The class label assigned to each object x ∈ X in the new data table I′ is the majority class label for the class [x]ker(g) ∈ X/ker(g) defined as follows: a class label l is a majority class label for [x]ker(g) if l is assigned to the most of objects from [x]ker(g), i.e. if l = class(x1) for x1 ∈ [x]ker(g) such that for each x′ ∈ [x]ker(g) it holds: |{x2 ∈ [x]ker(g) | class(x2) = l}| ≥ |{x2 ∈ [x]ker(g) | class(x2) = class(x′)}|.
Finally, the decision tree is induced from the transformed data table I′ ⊆ X × F , where class labels assigned to each object x ∈ X is the majority class label for the class [x]ker(g) ∈ X/ker(g). Similarily as in the first approach in section 3.2, when classifying an object x described by original attributes Y as a vector Px ∈ {0, 1}m in the (original) attribute space, we first compute the description of the object by factors F as a vector g(Px) ∈ {0, 1}k in the factor space. The object described by g(Px) is classified by the decision tree. In our example, the decision tree induced from reduced data table (the table in Fig. 3 restricted to attributes f1, . . . , f6) is the same as the tree induced from the extended data table, i.e. the tree depicted in Fig. 4 (right).
We performed series of experiments to evaluate our data preprocessing method.
The experiments consist in comparing the performance of created machine
learning models (e.g. decision trees) induced from original and preprocessed input
data. In the comparison we used reference decision tree algorithms ID3 and
C4.5 [
The experiments were done on selected public real-world datasets from UCI Machine Learning Repository. The selected datasets are from different areas (medicine, biology, zoology, politics, games). All the datasets contain only categorical attributes with one class label attribute and the datasets were cleared of objects containing missing values. Basic characteristics of the datasets are depicted in Tab. 1. The numbers of attributes are of original categorical attributes and, in brackets, of binary attributes after nominal scaling (see remark 1). The experiments were done using the 10-fold stratified cross-validation test. The following results are of averaging 10 execution runs on each dataset with randomly ordered records.
Due to the limited scope of the paper we show only the results of data
preprocessing by reducing the original attributes to factors and the results for
adding the factors to the collection of attributes are postponed to the full version
of the paper. The results are depicted in Tab. 2. The tables show ratios of
the average percentage rates of correct classifications for preprocessed data and
original data, i.e. the values indicate the increase factor of correct classifications
for preprocessed data. The values are for both training (upper number in the
table cell) and testing (lower number) datasets for each algorithm and dataset
being compared, plus the average over all datasets. In the case of top table the
1 Waikato Environment for Knowledge
http://www.cs.waikato.ac.nz/ml/weka/
Analysis,
available
at
criterion of optimality of generated factors (3) was set to the original criterion
function of the “cover ability” of factor concept, i.e. the original criterion used
in the algorithms from [
We can see that while not inducing worse learning model at average on training datasets the methods have better performance at average on testing dataset for input data preprocessed by our methods (with the exception of dataset zoo which has more than two values of class attribute). For instance, ID3 method has better performance by 3.8 % (5.4 % without zoo) for criterion of optimality of generated factors being the original criterion function of the “cover ability” of factor concept, while for criterion of optimality of generated factors being the function of the “decision ability” the performance is better by 5.1 % (6.5 % without zoo). The results for adding the factors to the collection of attributes are very similar, with ±1 % difference to the results for reducing the original attributes to factors, with the exception of dataset zoo, where the difference was +4 %.
We presented two methods of preprocessing input data to machine learning based on formal concept analysis (FCA). In the first method, the collection of attributes describing objects is extended by new attributes while in the second method, the original attributes are replaced by the new attributes. Both methods utilize boolean factor analysis, recently described by FCA, in that the new attributes are defined as factors computed from input data. The number of factors is usually smaller than the number of original attributes. The methods were demonstrated on the induction of decision trees and an experimental evaluation indicates usefullness of such preprocessing of data: the decision trees induced from preprocessed data outperformed decision trees induced from original data for two entropy-based methods ID3 and C4.5.