# WeatherFusionNet: Predicting Precipitation from Satellite Data

Jiří Pihrt
Faculty of Information Technology
Czech Technical University in Prague
<EMAIL_ADDRESS>
&Rudolf Raevskiy
Faculty of Information Technology
Czech Technical University in Prague
<EMAIL_ADDRESS>
&Petr Šimánek
Faculty of Information Technology
Czech Technical University in Prague
<EMAIL_ADDRESS>
&Matej Choma
Meteopress spol s.r.o.
Faculty of Information Technology
Czech Technical University in Prague
<EMAIL_ADDRESS>

###### Abstract

The short-term prediction of precipitation is critical in many areas of life.
Recently, a large body of work was devoted to forecasting radar reflectivity
images. The radar images are available only in areas with ground weather
radars. Thus, we aim to predict high-resolution precipitation from lower-
resolution satellite radiance images. A neural network called WeatherFusionNet
is employed to predict severe rain up to eight hours in advance.
WeatherFusionNet is a U-Net architecture that fuses three different ways to
process the satellite data; predicting future satellite frames, extracting
rain information from the current frames, and using the input sequence
directly. Using the presented method, we achieved 1st place in the NeurIPS
2022 Weather4cast Core challenge. The code and trained parameters are
available at https://github.com/Datalab-FIT-CTU/weather4cast-2022.

##  1 Introduction

Reliably predicting precipitation is a challenge with societal impact,
especially the prediction of extreme weather. The Weather4Cast 2022 [IARAI, ]
competition allowed us to work on the nowcasting problem for areas with no or
unreliable access to weather radar data. Using only satellite data to forecast
extreme precipitation is a very challenging task, and it complements our
present effort to master radar prediction. Weather4Cast 2022 follows the
previous challenge of Herruzo et al. [2021].

The joint team of Meteopress and Czech Technical University in Prague aims to
develop the best possible approach for precipitation prediction. We want to
overcome the limitations of the current optical methods by applying machine
learning. We currently work on improving nowcasting based on weather radar
data with very accurate results as presented by Choma et al. [2022]. In the
past, we used a basic U-Net Ronneberger et al. [2015] and later PredRNN
architecture [Wang et al., 2022] to solve this challenging task. We further
improved the models, but we later found it necessary to include more prior
physical knowledge in the architecture. The PhyDNet of Guen and Thome [2020]
demonstrated superior performance in radar prediction (in both storm structure
and movement) while increasing the interpretability of the model and also the
physical trustworthiness. We further improved the physical part of PhyDNet
[Choma et al., 2022].

In the Weather4Cast, the task is even more challenging than radar prediction.
We decided to apply our good experience with PhyDNet and enrich the model with
other architectural choices and fusion. We call the resulting model
WeatherFusionNet as it fuses three different ways to process the satellite
data; predicting future satellite images, extracting rain information from the
current frames, and using the input sequence directly.

##  2 Used data

The task of this competition was to predict 32 ground-radar (1 channel)
images, which is responsible for the next 8 hours, based on 4 satellite images
(1 hour). The entire dataset was provided by the organizers of the
Weather4cast competition. It covers areas of 7 European regions and contains
satellite and radar images for years 2019 and 2020. The satellite images are
composed of 2 visible (VIS), 2 water vapor (WV), and 7 infrared (IR) bands.
Each image has a size of $252\times 252$ and has a temporal resolution of 15
minutes. Satellite patch pixel corresponds to 12x12 square kilometers. The
target rain rate in the sequence to be predicted have higher spatial
resolution and 1 pixel corresponds to a spatial area of about 2x2 square
kilometers.

Training sequences are generated with a sliding window, using the provided
data loader, generating a total of 228928 samples. The validation set contains
predefined sequences, 840 in total.

Static data with latitude, longitude, and topological height were also
provided, but were not used in our model.

The competition was designed as a binary classification task. The rain
threshold was specified as 0.2 during the second stage.

##  3 Model Architecture

Our model consists of three modules, which are all trained separately, looking
at the data from different angles.

Figure 1: Diagram of the model architecture. The dimensions in parentheses
denote the temporal and channel dimension sizes, respectively.

Firstly, we use a module that we call sat2rad. This network is trained to
estimate the rainfall at the current time step of a single satellite frame. By
training it this way, we believe it can efficiently extract information about
the current rain situation in the input sequence, without having to predict
the future. This module is realized by a U-Net [Ronneberger et al., 2015] with
11 input channels and 1 output channel. In the overall model, it is applied to
all 4 input satellite input frames independently, generating 4 channels in
total. We take advantage of the spatial invariance feature of a convolutional
network, to predict the rainfall for the entire satellite area, even though we
only have radar data for a smaller area. More details on that, as well as the
specific U-Net architecture, are described later in this section.

Secondly, we use a recurrent convolutional network PhyDNet [Guen and Thome,
2020]. PhyDNet aims to disentangle physical dynamics from other complementary
visual information. Its architecture consists of two branches. One branch is
responsible for the physical dynamics, and features a recurrent physically
constrained cell called PhyCell, for performing PDE-constrained prediction in
latent space. The second branch extracts other residual information required
for future prediction, such as visual appearance and details, using ConvLSTM
cells [Shi et al., 2015].

Although PhyDNet is designed to work with radar frames, it was difficult to
apply it to this competition in a straightforward way, because of the
combination of relatively small spatial area and long prediction timeframe,
and the fact that we don’t have accurate input radar data during inference.
Instead, we trained PhyDNet only on the satellite data, which do not have
these limitations. Essentially, we used PhyDNet to extend the input sequence
of satellite frames. We decided to limit the output sequence length to 10,
based on our memory limitations and past experience with PhyDNet.

Finally, the outputs from the previously described two modules are
concatenated, along with the input sequence, and fused by another U-Net to
generate the final prediction. This U-Net has a total of 158 input channels
and 32 output channels. However, similarly, as in the sat2rad module, the
prediction covers the entire $3024\times 3024$ square kilometer area. But we
only need to predict and have the data for, the center $504\times 504$ square
kilometer area. Because of that, we crop the center part ($42\times 42$
pixels) of the prediction, and then upscale it back to the target $252\times
252$ resolution, as shown in Figure 1. We believe this approach can take more
advantage of the spatial invariance feature of a convolutional network such as
U-Net, than simply forcing it to cover the smaller spatial area directly. We
also use this approach when training the sat2rad module.

The upscale operation is realized simply by an Upsample layer with bilinear
interpolation and a scale factor of 6. We tried more sophisticated approaches
during the first stage of the competition, but we did not observe any
significant improvements. There is room for more research on this part.

For both of the U-Net modules in our architecture, we use the following
version;

  * •

filter sizes of 32, 64, 128, 256, 512,

  * •

each 3x3 convolution is followed by a BatchNorm layer and a ReLU,

  * •

downscaling is realized by 2x2 max pooling with stride 2

  * •

and upscaling is realized by Upsample layers with a scale factor of 2 and
bilinear interpolation.

One limitation of U-Net is that it only works with images of sizes divisible
by 32. To get around this, we pad the input images by 2 pixels (with padding
mode set to replicate) on each side to increase the size to 256x256, right
before inputting them to both U-Nets we use. Then we crop the output back to
252x252.

##  4 Training Procedure

As described in the previous section, the sat2rad module was not trained on
sequences, but on individual frames. To achieve this, we simply set the input
and output sequence length to 1 and subtracted 1 from the output indexes so
that they match the input. No further modifications were required. It was
trained with a batch size of 32, and the loss function used was
BCEWithLogitsLoss. Other hyperparameters are listed in Table 1.

Learning rate | 1e-3
---|---
Weight decay | 1e-2
Optimizer | AdamW
Model precision | 32
Positive weight | 2.58
Table 1: U-Net hyperparameters

The Satellite PhyDNet module is trained only using satellite data. We set the
satellite sequence length to 14 and then split it into 4 input and 10 output
frames. Because the provided validation set was not designed for longer
sequences, we used part of the training set as a validation split.
Specifically, the first 150000 samples were used for training, and the rest
was used to generate validation sequences, using a sliding window with a
stride of 32 samples. PhyDNet was trained with a loss function $L=L1+L2$. We
used teacher forcing, starting with probability of 1, decreased by 5e-5 every
step. Hyperparameters are listed in Table 2.

ConvLSTMCell |
---|---
Input dimension | 64
Hidden dimensions | [128, 128, 64]
Kernel size | (3, 3)
PhyCell |
Input dimension | 64
Hidden dimensions | [49]
Kernel size | (7, 7)
Optimizer | Adam
Learning rate | 1e-3
Batch Size | 16
Table 2: PhyDNet hyperparameters

The final U-Net model requires outputs from the previous two modules, but
during training they were frozen (their weights were not updated). This model
was also trained with BCEWithLogitsLoss, batch size 16, and other
hyperparameters listed in Table 1. No learning rate scheduling was used. The
evolution of CSI, F1, IoU metrics and loss on the validation dataset is
presented in Figure 3. The models have been trained using a single NVIDIA
A100-40GB.

##  5 Results

In this section, we show the empirical results of our model. We also compare
it to a baseline U-Net model, which has exactly the same hyperparameters and
training procedures, but it does not include the inputs from sat2rad and
PhyDNet modules. It is difficult to explain why the WeatherFusionNet performed
worse on the Transfer IoU without access to the test and heldout dataset.

Model | Validation IoU | Core Heldout IoU |  Transfer Heldout IoU
---|---|---|---
UNet | 0.2988 | 0.2950 | 0.2567
WeatherFusionNet | 0.3212 | 0.3162 | 0.2488
Table 3: IoU metric on the validation set and from the final competition
leaderboards. Figure 2: IoU metric over time computed on the validation set.

Figure 2 shows how the IoU metric varies in time over a prediction. Figure 4
demonstrates a prediction of a satellite image sequence by PhyDNet. Figure 5
shows results of sat2rad U-Net module. Figure 6 presents a sample
WeatherFusionNet prediction.

Figure 3: Evolution of the validation loss, IoU, F1, and CSI metric during
training. Compared WeatherFusionNet with plain UNet. Figure 4: Satellite
PhyDNet prediction example. Each row is a different satellite channel, first
two columns are input data, and further columns show PhyDNet prediction of the
satellite for up to 150 minutes. Figure 5: sat2rad U-Net module prediction
examples. Each row illustrates one sample time instance, first three columns
show input satellite data (three different channels). The black/white square
highlights the target radar area. The fourth column presents predicted rain
probability and the last column is the target radar image. Figure 6:
WeatherFusionNet prediction example. The first row is the evolution of the
target radar image in 8 hours, the second row is the predicted probability and
the last row is the final prediction.

##  6 Conclusion

We presented our approach to forecasting precipitation in high resolution
based only on low-resolution satellite data. The method is called
WeatherFusionNet and was used as a solution to the Weather4cast challenge. The
model ingests three different sources of data, i.e. from satellite prediction,
sat2rad, and the satellite image. The model proved to be working well by
winning the Weather4cast 2022 Core challenge.

The current model is not trained end-to-end, mostly due to memory
requirements, but it would be interesting to try it in the future. Special
attention should be also paid to the upscaling part of the model. The
upscaling is not critical in the current setting but would be if we would try
to solve a regression task instead of classification. Especially to model the
storm with a reasonable structure which is a very difficult task for the
current deep-learning methods. Also, we may add static data that has not been
used in this paper.

The model is also well prepared for another source of data, especially if the
radar data are available, we can skip the sat2rad model.

## References

  * Choma et al. [2022] Matej Choma, Jakub Bartel, and Petr Šimánek.  Precipitation nowcasting by deep physics-constrained neural networks.  Technical report, Copernicus Meetings, 2022.
  * Guen and Thome [2020] Vincent Le Guen and Nicolas Thome.  Disentangling physical dynamics from unknown factors for unsupervised video prediction.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 11474–11484, 2020.
  * Herruzo et al. [2021] Pedro Herruzo, Aleksandra Gruca, Llorenç Lliso, Xavier Calbet, Pilar Rípodas, Sepp Hochreiter, Michael Kopp, and David P. Kreil.  High-resolution multi-channel weather forecasting – first insights on transfer learning from the weather4cast competitions 2021.  In _2021 IEEE International Conference on Big Data (Big Data)_ , pages 5750–5757, 2021.  doi: 10.1109/BigData52589.2021.9672063.
  * [4] IARAI.  Weather4cast – multi-sensor weather forecast competition.  URL https://www.iarai.ac.at/weather4cast/.
  * Ronneberger et al. [2015] Olaf Ronneberger, Philipp Fischer, and Thomas Brox.  U-net: Convolutional networks for biomedical image segmentation.  In _International Conference on Medical image computing and computer-assisted intervention_ , pages 234–241. Springer, 2015.
  * Shi et al. [2015] Xingjian Shi, Zhourong Chen, Hao Wang, Dit-Yan Yeung, Wai-Kin Wong, and Wang-chun Woo.  Convolutional lstm network: A machine learning approach for precipitation nowcasting.  _Advances in neural information processing systems_ , 28, 2015.
  * Wang et al. [2022] Yunbo Wang, Haixu Wu, Jianjin Zhang, Zhifeng Gao, Jianmin Wang, Philip Yu, and Mingsheng Long.  Predrnn: A recurrent neural network for spatiotemporal predictive learning.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 2022.


# A New Algorithm based on Extent Bit-array for Computing Formal Concepts
111The authors are supported by NSF grant of Anhui Province(No.1808085MF178),
China.

Jianqin Zhou1 , Sichun Yang1, Xifeng Wang1 and Wanquan Liu2 222Corresponding
author. Email<EMAIL_ADDRESS>

1Department of Computer Science,
Anhui University of Technology, Ma’anshan 243002, China

2School of Intelligent Systems Engineering,
Sun Yat-sen University, Shenzhen 518000, China

> The emergence of Formal Concept Analysis (FCA) as a data analysis technique
> has increased the need for developing algorithms which can compute formal
> concepts quickly. The current efficient algorithms for FCA are variants of
> the Close-By-One (CbO) algorithm, such as In-Close2, In-Close3 and In-
> Close4, which are all based on horizontal storage of contexts. In this
> paper, based on algorithm In-Close4, a new algorithm based on the vertical
> storage of contexts, called In-Close5, is proposed, which can significantly
> reduce both the time complexity and space complexity of algorithm In-Close4.
> Technically, the new algorithm stores both context and extent of a concept
> as a vertical bit-array, while within In-Close4 algorithm the context is
> stored only as a horizontal bit-array, which is very slow in finding the
> intersection of two extent sets. Experimental results demonstrate that the
> proposed algorithm is much more effective than In-Close4 algorithm, and it
> also has a broader scope of applicability in computing formal concept in
> which one can solve the problems that cannot be solved by the In-Close4
> algorithm.
>
> Keywords: Formal Concept Analysis; Fast CbO algorithm; In-Close2; In-Close4
>
> Mathematics Subject Classification 2010: 68T30, 68T35

##  1 Introduction

Among data analysis techniques, Formal Concept Analysis (FCA) is a useful
knowledge representation framework for describing and summarizing data. As the
crucial data structure of FCA, concept lattice is an effective tool for
knowledge discovering, which can depict the generalization and specification
between formal concepts in a hierarchical structure. Concept lattice has been
widely used in many areas, such as data mining, machine learning, information
retrieval and so on [4, 9, 17, 16, 23, 24]. The main research contents of
concept lattice include lattice construction [14, 1, 2, 8, 15, 21, 19, 20],
rule extraction [11, 12, 13, 18] and lattice reduction [13, 10, 22].

A challenging problem in computing these formal concepts is that a typical
data set may have a great number of formal concepts. It is well known that the
number of formal concepts can be increased exponentially in associated with
the size of the input context and the problem of determining this number is
#P-complete [7].

In FCbO algorithm, Outrata and Vychodil [14] introduced an idea in which a
concept is closed before its descendants are computed, thus allowing the
descendants to fully inherit the attributes of the parent. With the spirit of
‘best-of-breed’ research, this idea was integrated into the In-Close2
algorithm [1].

Considering the formal context as a matrix, a row is all the attributes of an
object and a column is all the objects of an attribute. Further, all the
objects of a formal concept is called extent and all the attributes of a
formal concept is called intent. Within In-Close2, In-Close3 or In-Close4
algorithms [1, 2, 3], intents are stored in a linked list tree structure.
Extents are stored in a linearised 2-dimensional array. The context is stored
as a horizontal bit-array for optimising for RAM and cache memory. This also
allows multiple context cells to be processed by a single 32-bit or 64-bit
operator.

Suppose that one row of context is $(1,1,1,1,1,1,1,1$, $0,0,0,0,0,0,0,0,$
$0,0,0,0,$ $0,0,0,0$, $0,0,0,0$, $0,0,0,0)$, it is stored as $31$ in In-
Close2, In-Close3 or In-Close4 algorithms, where the first bit means $2^{0}$,
the second bit means $2^{1}$, the third bit means $2^{2}$ and so on. The main
shortcoming of these algorithms is that the extent of a concept is not stored
as a 32-bit-array (or 64-bit-array), thus they process the intersection of the
extent of a concept and a column of context only one object at a time.

A crucial improvement in our algorithm is that both context and extent of a
concept are stored as a vertical bit-array for optimising for RAM and cache
memory, which can significantly reduce both the time complexity and space
complexity. Suppose that one column of context or the extent of a concept is
$(1,1,1,1,1,1,1,1$, $0,0,0,0,0,0,0,0,$ $0,0,0,0,$ $0,0,0,0$, $0,0,0,0$,
$0,0,0,0)$, it is stored as $31$ in our algorithm. Thus multiple context cells
are processed by a single 32-bit or 64-bit operator when finding the
intersection of the extent of a concept and a column of context.

The second important improvement is the following. The core procedure in In-
Close2 algorithm is ComputeConceptsFrom((A,B),y), which uses a queue of local
array [1, 2]. In most cases, the local queues are empty, thus the space
complexity is not efficient. In our algorithm, the queue is optimised and used
as one global queue, which would greatly reduce the space complexity of the
core procedure.

This paper illustrates, after a brief description of formal concepts, how
formal concepts are computed via In-Close2 algorithm. Using a simple example,
the basic recursive process of In-Close2 algorithm is shown, line-by-line.
Using the same notation and style, we present a new variant called the In-
Close5. The key differences between the algorithms are then compared to
highlight where efficiencies occur.

The paper is organized as follows. In Section 2, we review the necessary
notions concerning formal concepts and their basic properties. In Section 3,
we study how formal concepts are computed using In-Close2 algorithm. In
Section 4, we present the In-Close5 algorithm and give experiment results with
In-Close2 algorithm, In-Close4 algorithm and In-Close5 algorithm. Finally the
paper is concluded in Section 5.

##  2 Basic notions and properties

In this section, we will review some basic notions and properties of FC
involved in this paper. The definitions of a formal context and its operators
are given first as follows.

Definition 1. [5] Let $(G,M,I)$ be a formal context, where
$G=\\{x_{1},x_{2},\ldots,x_{m}\\}$, $M=\\{a_{1},a_{2},\ldots,a_{n}\\}$, and
$I$ is a binary relation between $G$ and $M$. Here each $x_{i}(i\leq m)$ is
called an object, and each $a_{j}(j\leq n)$ is called an attribute. If an
object $g$ has an attribute $m$, we write $gIm$ or $(g,m)\in I$.

Definition 2. [5] Let $(G,M,I)$ be a formal context. For any $A\subseteq G$
and $B\subseteq M$, a pair of positive operators are defined by:

${}^{*}:P(G)\rightarrow P(M)$, $A^{*}=\\{m\in M|\forall g\in A,(g,m)\in I\\}$

${}^{*}:P(M)\rightarrow P(G)$, $B^{*}=\\{g\in G|\forall m\in B,(g,m)\in I\\}$

Based on the above operators, formal concepts and concept lattices are defined
as follows.

Definition 3. [5] Let $(G,M,I)$ be a formal context. For any $A\subseteq G$,
$B\subseteq M$, if $A^{*}=B$ and $B^{*}=A$, then $(A,B)$ is called a formal
concept, where $A$ is called the extent of the formal concept, and $B$ is
called the intent of the formal concept. For any
$(X_{1},A_{1}),(X_{2},A_{2})$, one can define the partial order as follows:

$(X_{1},A_{1})\leq(X_{2},A_{2})\Leftrightarrow X_{1}\subseteq
X_{2}\Leftrightarrow A_{2}\subseteq A_{1}$

The family of all formal concepts of $(G,M,I)$ is a complete lattice, and it
is called a concept lattice and denoted by $L(G,M,I)$.

Let $(G,M,I)$ be a formal context. For any $A_{1},A_{2},A\subseteq G$,
$B_{1},B_{2},B\subseteq M$, the following properties hold:

(1) $A_{1}\subseteq A2\Rightarrow A^{*}_{2}\subseteq A^{*}_{1}$, $\
B_{1}\subseteq B_{2}\Rightarrow B^{*}_{2}\subseteq B^{*}_{1}$;

(2) $A\subseteq A^{**}$, $\ B\subseteq B^{**}$;

(3) $A^{*}=A^{***}$, $\ B^{*}=B^{***}$;

(4) $A\subseteq B^{*}\ \Leftrightarrow\ B\subseteq A^{*}$;

(5) $(A_{1}\cup A_{2})^{*}=A^{*}_{1}\cap A^{*}_{2},\ (B_{1}\cup
B_{2})^{*}=B^{*}_{1}\cap B^{*}_{2}$;

(6) $(A_{1}\cap A_{2})^{*}\supseteq A^{*}_{1}\cup A^{*}_{2},\ (B_{1}\cap
B_{2})^{*}\supseteq B^{*}_{1}\cup B^{*}_{2}$;

Typically a table of $0$ or $1$ is used to represent a formal context, with
$1$s indicating binary relations between objects (rows) and attributes
(columns). The following is a simple example of a formal context:

Table 1: Formal context $K=(G,M,I)$ $G$ | $\ \ \ \ a_{1}\ \ \ \ \ $ | $\ \ \ \ a_{2}\ \ \ \ \ $ | $\ \ \ \ a_{3}\ \ \ \ \ $ | $\ \ \ \ a_{4}\ \ \ \ \ $ | $\ \ a_{5}$
---|---|---|---|---|---
1 | 0 | 1 | 1 | 0 | 0
2 | 1 | 1 | 0 | 0 | 0
3 | 1 | 0 | 0 | 0 | 0
4 | 0 | 0 | 0 | 0 | 1
5 | 0 | 0 | 0 | 1 | 1
6 | 0 | 0 | 1 | 1 | 1

The formal concepts in Table 1 can be calculated as given in the following
Table 2:

Table 2: Formal concepts in Table 1 |  | $C_{0}=(\\{1,2,3,4,5,6\\},\emptyset)$ |
---|---|---|---
$C_{4}=(\\{2,3\\},\\{a_{1}\\})$ | $C_{3}=(\\{1,2\\},\\{a_{2}\\})$ | $C_{2}=(\\{1,6\\},\\{a_{3}\\})$ | $C_{1}=(\\{4,5,6\\},\\{a_{5}\\})$
| $C_{5}=(\\{2\\},\\{a_{1},a_{2}\\})$ | $C_{6}=(\\{1\\},\\{a_{2},a_{3}\\})$ | $C_{7}=(\\{5,6\\},\\{a_{4},a_{5}\\})$
|  |  | $C_{8}=(\\{6\\},\\{a_{3},a_{4},a_{5}\\})$
|  | $C_{9}=(\emptyset,\\{a_{1},a_{2},a_{3},a_{4},a_{5}\\})$ |

Formal concepts in a table of $0$ or $1$ can be visualised as closed
rectangles of $1$s, where the rows and columns in the rectangle are not
necessarily contiguous. Suppose we define the cell of the $i$th row and $j$th
column as $(i,j)$. Thus in Table 1, $(5,4)$, $(5,5)$, $(6,4)$ and $(6,5)$ form
the concept $C_{7}$, and $C_{7}$ is a rectangle of height $2$ and width $2$.
Similarly $(6,3)$, $(6,4)$ and $(6,5)$ form the concept $C_{8}$, and $C_{8}$
is a rectangle of height $1$ and width $3$. $(1,3)$ and $(6,3)$ form the
concept $C_{2}$, and $C_{2}$ is a rectangle of height $2$ and width $1$, here
$(1,3)$ and $(6,3)$ are not contiguous.

In fact, it is not easy to compute the formal concepts given a formal context.
Next we will address this problem.

##  3 Computation of formal concepts

A formal concept can be obtained by applying the ∗ operator to a set of
attributes to get its extent, and then applying the ∗ operator to the extent
to get the intent.

For example, from the context in Table 1, $\\{a_{4}\\}^{*}=\\{5,6\\}$ and
$\\{5,6\\}^{*}=\\{a_{4},a_{5}\\}$. So $(\\{5,6\\},\\{a_{4},a_{5}\\})$ is
concept $C_{7}$ in Table 2 .

If this procedure is applied to every possible subset of
$\\{a_{1},a_{2},a_{3},a_{4},a_{5}\\}$, then all the concepts in the context
can be obtained. However, the number of formal concepts can be exponential in
terms of the size of the input context and the problem of determining this
number is #P-complete [7]. So an efficient algorithm is crucial and required
to compute all the formal concepts in a formal context.

By taking the advantages of algorithm In-Close and algorithm FCbO, In-Close2
is very efficient [1, 2]. The In-Close2 algorithm, given below, is invoked
with an initial $(A,B)=(X,\emptyset)$ and an initial attribute $y=n-1$, where
there are $n$ columns in the formal context.

Line 1 – Iterate across the context, from starting attribute $y$ down to
attribute 0 (the first column).

Line 2 – Skip attributes already in $B$, as intents now inherit all of their
parent’s attributes.

Line 3 – Form an extent $C$, by intersecting the current extent $A$ with the
next column of objects in the context.

Line 4 and Line 5 – If the extent formed, $C$, equals the extent, $A$, of the
concept whose intent is currently being processed, then add the current
attribute $j$ to the intent being processed, $B$.

Line 7 – Otherwise, check whether $\\{j\\}^{*}$ is contained in any new
concept in the queue.

Line 8 – If $\\{j\\}^{*}$ is not contained, place the new extent C and the
location where it was found, $j$, in a queue for later processing.

Lines 13 – The queue is processed by obtaining each new extent C and the
associated location from the queue.

Line 14 – Each new partial intent, $D$, inherits all the attributes from its
completed parent intent, $B$, along with the attribute, $j$, where its extent
was found.

Line 15 – Call ComputeConceptsFrom to compute child concepts from $j-1$ and to
complete the intent $D$.

As the extent of a concept is not stored as a 32-bit-array (or 64-bit-array),
thus in Line 3 of ComputeConceptsFrom, the algorithm processes the
intersection of the extent of a concept and a column of context only one
object at a time, which increases the time complexity of In-Close2 greatly.
This is the main disadvantage of In-Close2 algorithm.

For example, apply In-Close2 algorithm to the formal context in Table 1, we
have results in Table 2. In the first call ComputeConceptsFrom,
$\\{a_{5}\\}^{*}$, $\\{a_{3}\\}^{*}$, $\\{a_{2}\\}^{*}$ and $\\{a_{1}\\}^{*}$
passed through IsCannonical() test. As
$\\{a_{4}\\}^{*}\subset\\{a_{5}\\}^{*}$, where
$\\{a_{4}\\}^{*}=\\{5,6\\},\\{a_{5}\\}^{*}=\\{4,5,6\\}$, so $\\{a_{4}\\}^{*}$
failed IsCannonical() test.

In the second call ComputeConceptsFrom, $\\{0\\}^{*}$ passed through
IsCannonical() test, we got concept $C_{5}$ as the child concept of $C_{3}$.
Similarly, we got concept $C_{6}$ as the child concept of $C_{2}$, $C_{7}$ as
the child concept of $C_{1}$ and $C_{8}$ as the child concept of $C_{7}$.

By swapping the fourth column and the fifth column in Table 1, we have the
following Table 3.

Table 3: Formal context  $G$ | $\ \ \ \ a_{1}\ \ \ \ \ $ | $\ \ \ \ a_{2}\ \ \ \ \ $ | $\ \ \ \ a_{3}\ \ \ \ \ $ | $\ \ \ \ a_{4}\ \ \ \ \ $ | $\ \ a_{5}$
---|---|---|---|---|---
1 | 0 | 1 | 1 | 0 | 0
2 | 1 | 1 | 0 | 0 | 0
3 | 1 | 0 | 0 | 0 | 0
4 | 0 | 0 | 0 | 1 | 0
5 | 0 | 0 | 0 | 1 | 1
6 | 0 | 0 | 1 | 1 | 1

Apply In-Close2 algorithm to the formal context in Table 3, we have results in
Table 4.

In the first call ComputeConceptsFrom, all $\\{a_{5}\\}^{*}$,
$\\{a_{4}\\}^{*}$, $\\{a_{3}\\}^{*}$, $\\{a_{2}\\}^{*}$ and $\\{a_{1}\\}^{*}$
passed through IsCannonical() test.

When call ComputeConceptsFrom with $A=\\{5,6\\}$ and $B=\\{a_{5}\\}$, we got
$A=A\cap\\{a_{4}\\}^{*}$, where $\\{a_{4}\\}^{*}=\\{4,5,6\\}$, thus
$B\leftarrow B\cup\\{a_{4}\\}$.

Similarly, we got concept $C_{6}$ as the child concept of $C_{4}$, $C_{7}$ as
the child concept of $C_{3}$ and $C_{8}$ as the child concept of $C_{1}$.

Table 4: Formal concepts in Table 3 |  | $C_{0}=(\\{1,2,3,4,5,6\\},\emptyset)$ |  |
---|---|---|---|---
$C_{5}=$ | $C_{4}=$ | $C_{3}=$ | $C_{2}=$ | $C_{1}=$
$(\\{2,3\\},\\{a_{1}\\})$ | $(\\{1,2\\},\\{a_{2}\\})$ | $(\\{1,6\\},\\{a_{3}\\})$ | $(\\{4,5,6\\},\\{a_{4}\\})$ | $(\\{5,6\\},\\{a_{5},a_{4}\\})$
| $C_{6}=(\\{2\\},\\{a_{1},a_{2}\\})$ | $C_{7}=(\\{1\\},\\{a_{2},a_{3}\\})$ |  | $C_{8}=(\\{6\\},\\{a_{3},a_{4},a_{5}\\})$
|  | $C_{9}=(\emptyset,\\{a_{1},a_{2},a_{3},a_{4},a_{5}\\})$ |  |

In Figure 1, one can see the call tree of ComputeConceptsFrom. From the graph
theory, the number of vertices is equal to the number of edges plus one. Here
one edge means a ComputeConceptsFrom call from the queue and one vertex means
an implementation of ComputeConceptsFrom. One can see that during the first
implementation of ComputeConceptsFrom, 5 function calls from the queue are
launched. It is obvious that during the implementation of ComputeConceptsFrom,
one function call from the queue is launched averagely.

Specifically, the local queue of ComputeConceptsFrom is implemented as the
following. First int Bchildren[MAX_COLS] is used to store the location of the
attribute that will spawn new concept. Second int Cnums[MAX_COLS] is used to
store the concept number of the spawned concept, where MAX_COLS$=5,000$. One
can see that the efficiency of the local queue is very low.

Figure 1. The call tree of ComputeConceptsFrom

In line 3 of ComputeConceptsFrom, if the extent formed, $C$, is empty, then
store the current attribute $j$, which can be ignored in concepts of
subsequent levels. This is the main improvement from In-Close2 to In-Close3.
Further In-Close4 is a 64 bit version, and it can build and output concept
trees in JSON format, where JSON stands for Java Script object notation, is a
lightweight data representation method.

##  4 In-Close5 algorithm

Within In-Close2, In-Close3 or In-Close4 algorithms [1, 2, 3], extents are
stored in a linearised 2-dimensional array. A concept of $k$ objects will
occupy $k$ integers. Furthermore, in ComputeConceptsFrom, the core procedure
of In-Close2, intersecting the current extent $A$ with the next column of
objects in the context is the most time-consuming operation. It inspires us to
store both context and extents of concepts as a vertical bit-array.

Technically, let $m$ rows in a context be divided into
$\lfloor(m-1)/32+1\rfloor$ blocks, where $\lfloor x\rfloor$ is the largest
number that is less than or equal to $x$. We only store the rows with objects
(or nonzero block value) by block number and block value.

For example, the column $(1,1,1,1,1,1,1,1$, $0,0,0,0$, $0,0,0,0$, $0,0,0,0$,
$0,0,0,0$, $0,0,0,0$, $0,0,0,0,0,0,0,0,0,0,0,0)$ is divided into 2 blocks. The
first block value is $31$, where the first bit means $2^{0}$, the second bit
means $2^{1}$, the third bit means $2^{2}$ and so on. Thus the column is
stored as $\\{0,31\\}$, namely block number is $0$ and block value is $31$. We
do not store the second block, as the second block value is $0$.

In the case of In-Close4 algorithm, suppose that
$(1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,$ $0,0,0,0,$
$0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0)$ are the objects of a concept, then
they will stored as $\\{0,1,2,3,4,5,6,7\\}$, namely $8$ integers indicate the
locations of all objects (or the locations of all $1$s ).

In the best case of In-Close5, a concept of $k$ objects only occupy $k/16$
integers, and one bitwise logic and operation may process 32 objects when
stored as 32-bit integers. In the worst case of In-Close5, the column
$(1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,$ $0,0,0,0,$ $0,0,0,0,0,0,0,0,0,0,0,0$ is
stored as $\\{0,1\\}$, while In-Close4 the same column is stored as $\\{0\\}$.

With In-Close2 or In-Close4 algorithm to process mushroom data [6], extents of
all concepts will occupy $20,372,788$ bytes of memory. In contrast, In-Close5
algorithm only needs $4,963,900$ bytes of memory when stored as 32-bit
integer, and $3,505,526$ bytes of memory when stored as 64-bit integer. From
the results above, the space complexity of In-Close5 is much better than that
of In-Close2 and In-Close4.

The core procedure in In-Close2 algorithm is ComputeConceptsFrom((A,B),y),
which uses a queue of local array [1, 2]. Specifically, use int
Bchildren[MAX_COLS] to store the location of the attribute that will spawn new
concept, and int Cnums[MAX_COLS] to store the concept number of the spawned
concept, where MAX_COLS$=5,000$. In fact, the number of times that the
function is called is equal to the number of concepts. Thus in most cases the
queue is empty. This inspires us to link all the local queue together as one
global queue, and use the concept number as the index of the queue. Thus we
only need to store the location of the attribute where the new extent $C$ was
found.

The In-Close5 algorithm is presented as the following, which is invoked with
an initial $(A,B)=(X,\emptyset)$, an initial attribute $y=n-1$, where there
are $n$ columns in the formal context, and an initial empty Bparent.

Line 1 – Bparent contains $B$ and the attribute that can be ignored in
concepts of subsequent levels. The child concept inherits attributes from the
parent.

Line 2 – Iterate across the context, from starting attribute $y$ down to
attribute 0 (the first column).

Line 3 – Skip attributes already in Bchild.

Line 4 – Form an extent $C$, by intersecting the current extent $A$ with the
next column of objects in the context. It is implemented in C language as the
following.

unsigned int* Ac = startA[c]; //pointer to start of current extent

unsigned int* aptr = startA[highc]; //pointer to start of next extent to be
created

int sizeAc = startA[c+1]-startA[c]; //calculate the size of current extent

/* iterate across objects in current extent to find them in current column */

for(int i = sizeAc/2; i >0; i–)$\\{$

if(context0[*Ac][j] & *(Ac+1))$\\{$

*aptr = *Ac; //add object block number to new extent (intersection)

aptr++;

*aptr = context0[*Ac][j] & *(Ac+1); //add object block value to new extent

aptr++;

$\\}$

Ac+=2; //move to next object block

$\\}$

Line 5 and Line 6 – If the extent formed, $C$, is empty, then put $j$ in
Bchild, which can be ignored in concepts of subsequent levels.

Line 8 and Line 9 – If the extent formed, $C$, equals the extent, $A$, of the
concept whose intent is currently being processed, then add the current
attribute $j$ to the intent being processed, $B$ and also put $j$ in Bchild.

Line 11 – Otherwise, check whether $\\{j\\}^{*}$ is contained in any new
concept in the queue.

Line 12 – If $\\{j\\}^{*}$ is not contained, place the location $j$ in a
global queue for later processing. It is implemented as the following.

Bchildren[highc-1] = j; //note where (attribute column) it was found,

nodeParent[highc] = c; //note the parent concept number and

startA[++highc] = aptr; //note the start of the new extent in A.

Lines 18 – The queue is processed by obtaining each new extent $C$ and
associated location from the queue.

Line 19 – Each new partial intent, $D$, inherits all the attributes from its
completed parent intent, $B$, along with the attribute, $j$, where its extent
was found and attributes that can be ignored in concepts of subsequent levels.

Line 20 – Call ComputeConceptsFrom to compute child concepts from $j-1$ and to
complete the intent $D$.

Lines 18, Lines 19 and Lines 20 are implemented in C language as the
following.

// here numchildrenStart is stored as highc-1 at the beginning of

//ComputeConceptsFrom

for( $i$ = highc-2; $i$ $\geq$ numchildrenStart ; $i$–)$\\{$

startB[$i$+1] = bptr; //set the start of the intent in B tree

// note that $i+1$ is the number of new extent $C$

ComputeConceptsFrom($i+1$, Bchildren[$i$]-1, Bchild);

$\\}$

As both context and extent of a concept are stored as a vertical bit-array,
when form an extent $C$ in Line 4, at most 32 (64) context cells can be
processed by a single 32-bit ( 64-bit) and operation. In the case of In-
Close3, the extent of a concept is not stored as a 32-bit-array (or 64-bit-
array), thus In-Close3 processes context only one cell at a time. In Line 12,
we only place the location $j$ in a global queue for later processing, while
In-Close3 has many local empty queues. The time complexity and space
complexity is greatly reduced, however the logic structure of In-Close5
algorithm is almost the same as that of In-Close3 algorithm, so please refer
to [2] for the correctness of In-Close5 algorithm.

Considering the formal context as a matrix, when transpose the matrix, the
concepts of the new matrix should be symmetric to that of the original matrix.
However, there are 8124 columns in transposed mushroom data, thus the depth of
recursive calls of ComputeConceptsFrom is greatly increased and so does the
complexity.

For In-Close5 algorithm, with one global queue, it is capable to process
transposed mushroom data but with much longer time. In contrast, as local
queues use too much memory, In-Close4 algorithm can not process transposed
mushroom data.

Some experiments are done to compare the time complexity of In-Close2
algorithm, In-Close4 algorithm and In-Close5 algorithm. The experiment results
are given in Table 5. Here mushroom data and nursery data are from [6]. The
experiments are carried out using a laptop computer with an Intel Core
i5-2450M 2.50 GHz processor and 8GB of RAM.

Table 5: Comparison of In-Close2, In-Close4 and In-Close5 | Mushroom | Nursery | Transposed Mushroom | Transposed Nursery
---|---|---|---|---
$|G|\times|M|$ | $8,124\times 115$ | $12,960\times 30$ | $115\times 8,124$ | $30\times 12,960$
#concepts | 233,101 | 154,055 | 233,101 | 154,055
In-Close2 | 0.424 | 0.123 | $\times$ | $\times$
In-Close4 | 0.388 | 0.132 | $\times$ | $\times$
In-Close5 | 0.195 | 0.073 | 102.536 | 105.531

From Table 5, one can see that for Mushroom data of $8,124\times 115$, In-
Close4 is faster than In-Close2 and In-Close5 is the fastest. For Nursery data
of $12,960\times 30$, In-Close4 has no advantage over In-Close2 as 30 is much
less than 64. As local queues use too much memory, both In-Close2 and In-
Close4 can not process transposed mushroom data.

##  5 Conclusions and future work

Within In-Close2, In-Close3 or In-Close4 algorithms, intents are stored in a
linked list tree structure and extents are stored in a linearised
2-dimensional array. The data structure is very simple and effective. A
crucial improvement in our algorithm is that both context and extents of
concepts are stored as a vertical bit-array to optimise for RAM and cache
memory, which also significantly reduces the time for processing extents of
concepts.

Object oriented concept lattice is a more extensive concept lattice [25]. It
is more difficult to construct object oriented concept lattices. In the
future, we will apply the data structure and technique in these algorithms to
object oriented concept lattices, attribute oriented concept lattices and so
on.

## References

  * [1] S. Andrews, In-close2, a high performance formal concept miner. S. Andrews, S. Polovina, R. Hill, B. Akhgar (Eds.), Conceptual Structures for Discovering Knowledge – Proceedings of the 19th International Conference on Conceptual Structures (ICCS), Springer (2011), pp. 50-62
  * [2] S. Andrews, A ‘Best-of-Breed’ approach for designing a fast algorithm for computing fixpoints of Galois Connections, Information Sciences, 295 (20) (2015) 633–649.
  * [3] S. Andrews, In-Close4 Program, 2017, https://sourceforge.net/projects/inclose/files/In-Close/.
  * [4] V.G. Blinova, D.A. Dobrynin, V.K. Finn, S.O. Kuznetsov, E.S. Pankratova, Toxicology analysis by means of the jsm-method,  Bioinformatics. 19(10) (2003) 1201–1207.
  * [5] B. Ganter, R. Wille, Formal Concept Analysis: Mathematical Foundations, Springer-Verlag, New York, 1999.
  * [6] A. Frank, A. Asuncion, UCI Machine Learning Repository, 2010, http://archive.ics.uci.edu/ml.
  * [7] S.O. Kuznetsov, On computing the size of a lattice and related decision problems, Order, 18 (4) (2001) 313-321
  * [8] S.O. Kuznetsov, S.A. Obiedkov, Comparing performance of algorithms for generating concept lattices,J. Exp. Theor. Artif. Intell. 14(2–3) (2002) 189–216.
  * [9] S.O. Kuznetsov, Machine learning and formal concept analysis, in: Concept Lattices, Proceedings of the Second International Conference on Formal Concept Analysis, ICFCA 2004, Sydney, Australia, February 23-26, 2004, pp.287-312.
  * [10] S.O. Kuznetsov, S.A. Obiedkov, C. Roth, Reducing the representation complexity of lattice-based taxonomies, in: Conceptual Structures: Knowledge Architectures for Smart Applications, Proceedings of the 15th International Conference on Conceptual Structures, ICCS 2007, Sheffield, UK, July 22-27, 2007, pp.241–254.
  * [11] J. Li, C. Mei, Y. Lv, Incomplete decision contexts: approximate concept construction, rule acquisition and knowledge reduction, Int. J. Approx. Reason. 54(1) (2013) 149–165.
  * [12] J. Li, C. Mei, L. Wang, J. Wang, On inference rules in decision formal contexts, Int. J. Comput. Intell. Syst. 8(1) (2015) 175–186.
  * [13] J. Li, C. Mei, J. Wang, X. Zhang, Rule-preserved object compression in formal decision contexts using concept lattices, Knowl.-Based Syst. 71 (2014) 435–445.
  * [14] J. Outrata, V. Vychodil, Fast algorithm for computing fixpoints of Galois connections induced by object-attribute relational data, Information Sciences, 185 (1) (2012) 114-127
  * [15] P. Osicka, Algorithms for computation of concept trilattice of triadic fuzzy context, in: Advances in Computational Intelligence -Proceedings of the 14th International Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems, IPMU 2012, Catania, Italy, July 9-13, 2012, pp.221-230 (Part III).
  * [16] N. Pasquier, Y. Bastide, R. Taouil, L. Lakhal, Efficient mining of association rules using closed itemset lattices, Inf. Syst. 24(1) (1999) 25–46.
  * [17] J. Poelmans, D.I. Ignatov, S. Viaene, G. Dedene, S.O. Kuznetsov, Text mining scientific papers: a survey on FCA-based information retrieval research, in:Advances in Data Mining. Applications and Theoretical Aspects -Proceedings of the 12th Industrial Conference, ICDM 2012, Berlin, Germany, July 13-20, 2012, pp.273-287.
  * [18] Z. Pei, D. Ruan, D. Meng, Z. Liu, Formal concept analysis based on the topology for attributes of a formal context, Information Sciences, 236 (2013) 66–82.
  * [19] J. Qi, W. Liu, L. Wei, Computing the set of concepts through the composition and decomposition of formal contexts, in: International Conference on Machine Learning and Cybernetics, Proceedings, ICMLC 2012, Xian, Shaanxi, China, July 15–17, 2012, pp.1326–1332.
  * [20] J. Qi, T. Qian, L. Wei, The connections between three-way and classical concept lattices, Knowl.-Based Syst. 91 (2016) 143–151.
  * [21] J. Qi, L. Wei, Z. Li, A partitional view of concept lattice, in: Rough Sets, Fuzzy Sets, Data Mining, and Granular Computing, Proceedings of the 10th International Conference, RSFDGrC 2005, Regina, Canada, August 31–September 3, 2005, pp.74–83 (Part I).
  * [22] R. Ren, L. Wei, The attribute reductions of three-way concept lattices, Knowl.-Based Syst. 99 (2016) 92–102.
  * [23] M. Shao, H. Yang, W. Wu, Knowledge reduction in formal fuzzy contexts, Knowl.-Based Syst. 73 (2015) 265–275.
  * [24] Q. Wan, L. Wei, Approximate concepts acquisition based on formal contexts, Knowl.-Based Syst. 75 (2015) 78–86.
  * [25] Y. Y. Yao, Concept lattices in rough set theory, Processing Nafips 04 IEEE Meeting of the the Fuzzy Information, Canada: IEEE, September 27,2004: 796-801.