Towards a Unified Taxonomy of Biclustering Methods
Dmitry I. Ignatov$^{1
Being an unsupervised machine learning and data mining technique, biclustering and its multimodal extensions are becoming popular tools for analysing object-attribute data in different domains. Apart from conventional clustering techniques, biclustering is searching for homogeneous groups of objects while keeping their common description, e.g., in binary setting, their shared attributes. In bioinformatics, biclustering is used to find genes, which are active in a subset of situations, thus being candidates for biomarkers. However, the authors of those biclustering techniques that are popular in gene expression analysis, may overlook the existing methods. For instance, BiMax algorithm is aimed at finding biclusters, which are well-known for decades as formal concepts. Moreover, even if bioinformatics classify the biclustering methods according to reasonable domain-driven criteria, their classification taxonomies may be different from survey to survey and not full as well. So, in this paper we propose to use concept lattices as a tool for taxonomy building (in the biclustering domain) and attribute exploration as means for cross-domain taxonomy completion. \keywords{Biclustering, taxonomy, concept lattices, attribute exploration
BicTax.tex

%%%%%%%%%%%%%%%%%%%%%%% file typeinst.tex %%%%%%%%%%%%%%%%%%%%%%%%%
%
% This is the LaTeX source for the instructions to authors using
% the LaTeX document class 'llncs.cls' for contributions to
% the Lecture Notes in Computer Sciences series.
% http://www.springer.com/lncs       Springer Heidelberg 2006/05/04
%
% It may be used as a template for your own input - copy it
% to a new file with a new name and use it as the basis
% for your article.
%
% NB: the document class 'llncs' has its own and detailed documentation, see
% ftp://ftp.springer.de/data/pubftp/pub/tex/latex/llncs/latex2e/llncsdoc.pdf
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\documentclass[letter]{llncs}


%\usepackage[T2A]{fontenc}
%\usepackage[cp1251]{inputenc}
%\usepackage[english,russian]{babel}

%\usepackage[T1]{fontenc}
%\usepackage[utf8]{inputenc}
%\usepackage[russian]{babel}

\usepackage{amssymb}
\setcounter{tocdepth}{3}
\usepackage{graphicx}
\usepackage{enumerate}
%\usepackage{paralist}
\usepackage{hyperref}
\usepackage{url}
\usepackage{color,colortbl}
\definecolor{Gray}{gray}{0.9}

\usepackage{pdflscape}


%\usepackage[ruled,section]{algorithm}
%\usepackage[noend]{algorithmic}
\usepackage[ruled,vlined]{algorithm2e}

\usepackage{amssymb}
\usepackage{fca}
\usepackage{amsmath}
%,amsthm}
\usepackage{amsfonts}
\usepackage{alltt}


\usepackage{url}
\usepackage{amsmath}
\urldef{\mailsa}\path|dignatov@hse.ru|
\newcommand{\keywords}[1]{\par\addvspace\baselineskip
\noindent\keywordname\enspace\ignorespaces#1}


\newcommand{\K}{\mathbb{K}}


\usepackage{fca}


\begin{document}

\mainmatter  % start of an individual contribution

\titlerunning{Towards a Unified Taxonomy of Biclustering Methods}
%
\authorrunning{Dmitry I. Ignatov \and Bruce W. Watson}


% first the title is needed
\title{Towards a Unified Taxonomy of Biclustering Methods}


% the name(s) of the author(s) follow(s) next
%
% NB: Chinese authors should write their first names(s) in front of
% their surnames. This ensures that the names appear correctly in
% the running heads and the author index.
%
\author{Dmitry I. Ignatov$^{1}$ \and Bruce Watson$^{2}$}
%
\authorrunning{}
% (feature abused for this document to repeat the title also on left hand pages)

% the affiliations are given next; don't give your e-mail address
% unless you accept that it will be published
\institute{$^{1}$National Research University Higher School of Economics, Moscow, Russia\
\mailsa\\
$^{2}$Stellenbosch University, South Africa
%\url{http://www.hse.ru}
}

%
% NB: a more complex sample for affiliations and the mapping to the
% corresponding authors can be found in the file "llncs.dem"
% (search for the string "\mainmatter" where a contribution starts).
% "llncs.dem" accompanies the document class "llncs.cls".
%

\toctitle{}
\tocauthor{}
\maketitle


\begin{abstract}
Being an unsupervised machine learning and data mining technique, biclustering and its multimodal extensions are becoming popular tools for analysing object-attribute data in different domains. Apart from conventional clustering techniques, biclustering is searching for homogeneous groups of objects while keeping their common description, e.g., in binary setting, their shared attributes. In bioinformatics, biclustering is used to find genes, which are active in a subset of situations, thus being candidates for biomarkers. However, the authors of those biclustering techniques that are popular in gene expression analysis, may overlook the existing methods. For instance, BiMax algorithm is aimed at finding biclusters, which are well-known for decades as formal concepts. Moreover, even if bioinformatics classify the biclustering methods according to reasonable domain-driven criteria, their classification taxonomies may be different from survey to survey and not full as well. So, in this paper we propose to use concept lattices as a tool for taxonomy building (in the biclustering domain) and attribute exploration as means for cross-domain taxonomy completion.

\keywords{Biclustering, taxonomy, concept lattices,	attribute exploration}
\end{abstract}

\section{Introduction}

Biclustering is a popular family of data analysis techniques within cluster-analysis. Previously biclustering was known under the names direct clustering or subspace clustering \cite{Hartigan:1972}. The term biclustering was proposed by Boris Mirkin in \cite{Mirkin:1996}, p. 296:

\noindent \textit{The term biclustering refers to simultaneous clustering
of both row and column sets in a data matrix. Biclustering addresses the problems of aggregate representation of the basic features of interrelation
between rows and columns as expressed in the data.} 


 
The main advantage of biclustering technique lies in its ability to keep similarity of grouped objects in terms of their common attributes. So, biclustering is able to capture object similarity (homogeneity) expressed only by a subset of attributes, which allows an analyst to clearly see why certain objects were grouped together.


In the previous decade biclustering methods became extremely popular for gene expression analysis analysis in bioinformatics. Here, genes which demonstrate similar properties only in a subset of observable situations are considered to be within a bicluster along with those situations. The first rather comprehensive survey in the field was done in \cite{Madeira:2004}. Even though the survey was limited only to biclustering in bioinformatics, the field came to its maturity to have its own classification of the methods. The authors classified biclustering techniques according to several properties: biclustering type, biclustering structure, the way of bicluster generation, and the algorithmic strategy.


As it often happens, researchers from the bioinformatics domain overlooked or even rediscovered biclustering methods which have been known for decades. Thus, the notion of formal concept was known since the early 80-s \cite{wille:1982}, it corresponds to maximal inclusion unit submatrices in Boolean matrices \cite{Ganter:1999,Barkow:2006,Kaytoue:2009}. The idea of closed sets from Formal Concept Analysis and from frequent itemset mining were not considered in the bioinformatics domain. However, there are numerous efficient algorithms and applications, which can be treated as special cases of biclustering-based ones. To the best of our knowledge there is no any biclustering technique mentioned in bioinformatics which exploits ordered bicluster hierarchies.  Thus, in Formal Concept Analsis, biclusters (formal concepts) are hierarchically ordered by the relation ``be more general concept than'', which proved its helpfulness for data exploration and taxonomy building in different domains.

The aim of this work is two-fold: on the one hand, we are going to shed light on neighbouring domains where biclustering is actively used, and on the other hand build lattice-based taxonomies using the existing classifications of biclustering algorithms in the literature. The main open question in this work is as follows: How to build a unified taxonomy of the biclustering techniques.  


The rest of the paper is organised as follows. In Section \ref{sec:prev}, we shortly review previous work on biclustering, taxonomies of algorithms, and related fields. In Section \ref{sec:basics} we give basic definitions of FCA and biclustering (in the most general form). In Section \ref{sec:multi} we outline several existing biclustering extensions under the the name of multimodal clustering.
 Section \ref{sec:tax} is the main part of the paper which provides examples of different taxonomies of biclustering algorithms obtained from the literature. 


\section{Previous work}\label{sec:prev}


Construction of taxonomies of algorithms in Computer Science is not new. Thus, in \cite{Cleophas:2005,Cleophas:2006} a taxonomy of string matching algorithms was built guided by domain experts according to TABASCO methodology. In those papers, it was shown that concept lattices can be a good visualisation tool paired with interactive abilities of modern computer software. Moreover, concept lattices were successfully used for epistemic taxonomy building \cite{Roth:2008} combining multiple inheritance feature with compact graphical representation.


In addition to the existing term biclustering, there are several others like co-clustering or simultaneous clustering. 
Triclustering, Triadic FCA, multimodal clustering, clustering of Boolean tensors, closed n-sets, relational clustering and several other techniqes are all examples of possible biclustering extensions.  

\section{Basic definitions and models}\label{sec:basics}

\subsection{Formal Concept Analysis}\label{ssec:FCA}



\begin{definition} A \textbf{formal context} $\context=(G,M,I)$ consists of two sets $G$ and $M$ and a relation  $I$ between $G$ and $M$. The elements of $G$ are called the \textbf{objects} and the elements of  $M$ are called the \textbf{attributes }of the context. The notation $gIm$ or $(g,m) \in I$ means that the object $g$ has attribute $m$. 
\end{definition} 

\begin{definition} 
	
	For $A \subseteq G$, let
	
	$$A^\prime := \{m \in M | (g,m) \in I \mbox{ for all } g \in A\}$$
	
	and, for $B \subseteq M$, let  
	
	$$B^\prime := \{ g \in G | (g,m) \in I \mbox{ for all } m \in B\}.$$
	
	These operators are called \textbf{derivation operators} or \textbf{ concept-forming operators} for $\context=(G,M,I)$. 
	
\end{definition} 



\begin{proposition} Let $(G,M,I)$ be a formal context, for subsets $A, A_1, A_2 \subseteq G$ and $B\subseteq M$ we have
	\label{primeprop}
	\begin{enumerate}
		\item $A_1 \subseteq A_2$ iff $A_2^\prime \subseteq A_1^\prime$,
		\item $A \subseteq A^{\prime\prime}$,
		\item $A = A^{\prime\prime\prime}$ (hence, $A'''' = A''$),
		\item $(A_1 \cup A_2)' = A'_1 \cap A'_2$,
		\item $A\subseteq  B'\Leftrightarrow B\subseteq A' \Leftrightarrow A\times B \subseteq I$.
	\end{enumerate}
	
	Similar properties hold for subsets of attributes.
	
\end{proposition}



\begin{definition}
	
	A \textbf{closure operator} on set $S$ is a mapping $\varphi \colon 2^S \to 2^S$ with the following properties:
	
	\begin{enumerate}
		\item[1.] ${\varphi{\varphi X}} = {\varphi X}$ (\textbf{idempotency})
		
		\item[2.] $X\subseteq {\varphi X}$ (\textbf{extensity})
		
		\item[3.] $X\subseteq Y\Rightarrow {\varphi X}\subseteq {\varphi Y}$ (\textbf{monotonicity})
	\end{enumerate}
	
	For a closure operator $\varphi$ the set  $\varphi X$ is called \textbf{closure} of $X$.
	
	A subset $X\subseteq G$ is called \textbf{closed} if ${\varphi X} = X$.
	
\end{definition}

Let $(G,M,I)$ be a context, one can prove that operators
	$$(\cdot)''\colon 2^G\to 2^G,\ (\cdot)''\colon 2^M\to 2^M$$
	are closure operators. 

\begin{definition} 
	A \textbf{formal concept} of a formal context $\context=(G,M,I)$ is a pair $(A,B)$ with $A \subseteq G$,
	$B \subseteq M$, $A^\prime = B$ and $B^\prime = A$. The sets $A$ and $B$ are called the extent and the intent
	of the formal concept $(A,B)$, respectively. The \textbf{subconcept-superconcept relation} is
	given by $(A_1,B_1) \leq (A_2,B_2)$ iff $A_1 \subseteq A_2$ ($B_1 \subseteq B_2$).
\end{definition} 

This definition says that every formal concept has two parts, namely, its extent and
intent. This follows an old tradition of the \textit{Logic of Port Royal (1662)}, and is in line with the International Standard ISO 704 that formulates the following definition: ``A concept is considered to be a unit of thought constituted of two parts: its extent and its intent.''

\begin{definition} The set of all formal concepts of a context $\context$ together with the order relation $I$ forms a complete lattice, called the \textbf{concept lattice } of $\context$ and denoted by $\BV(\context)$.
\end{definition} 


\begin{definition}
\textbf{Implication} $A\to B$, where $A, B\subseteq M$ holds in context $(G,M,I)$ if
$A'\subseteq B'$, i.e., each object having all attributes from
$A$ also has all attributes from  $B$.
\end{definition}

\subsection{Biclustering}\label{ssec:bic}

In the first survey on biclustering techniques \cite{Madeira:2004}, bicluster is defined as a submatrix of an input object-attribute matrix. That is for a given matrix $A \in \mathbb{R}^{m\times n}$, a bicluster $b$ is a pair $(X,Y)$, where $X \subseteq \{1,\cdots,m \}$ and $Y \subseteq \{1,\cdots, m \}$. The bicluster should fulfil a certain homogeneity property, which varies from method to method, e.g., it may be allowed to contain only 1s inside the corresponding submatrix (bicluster) in Boolean case. 



For instance, for analysing large markets of context advertisement, we propose the following FCA-based definition of a bicluster \cite{Ignatov:2010,Ignatov:2012b}.

\begin{definition}\label{def:bicl}
	If $(g,m)\in I$, then $(m',g')$ is called an object-attribute or \emph{OA-bicluster}
	with density $\rho(m',g')=\frac{|I\cap (m'\times g')|}{|m'|\cdot|g'|}$.
	
\end{definition}

Here are some basic properties of oa-biclusters.


\begin{proposition}\label{proposition:bicl}
	
\
	
	1. $0\leq \rho\leq 1$.
	
	2. oa-bicluster $(m',g')$ is a formal concept iff $\rho = 1$.
	
	3. if $(m',g')$ is a oa-bicluster, then $(g'',g')\leq (m',m'')$.
	
\end{proposition}


\begin{figure}[h]
	\begin{center}
		\includegraphics[scale=0.5]{./pics/Bicluster}
		\vskip -0.1in
		\caption{OA-bicluster based on object and attribute closures}\label{fig:Bicl}
	\end{center}
	\vskip -0.1in
\end{figure}

In figure \ref{fig:Bicl} you can see the example of the oa-bicluster for a particular pair $(g,m) \in I$ of a certain context $(G,M,I)$. In general, only the regions $(g'',g')$ and $(m',m'')$ are full of non-empty pairs, i.e. have maximal density $\rho=1$, since they are object and attribute formal concepts respectively. Some black cells indicate non-empty pairs which one may found in such a bicluster. Therefore, the density parameter $\rho$ is a bicluster quality measure which shows how many non-empty pairs the bicluster contains.



\begin{definition}\label{def:dense}
	Let  $(A,B) \in 2^G \times 2^M$ be a oa-bicluster and  $\rho_{min}$ be a nonnegative real number, such that $0 \leq \rho_{min} \leq 1$, then $(A,B)$ is called  \emph{dense} if it satisfies the constraint $\rho(A,B)\geq \rho_{min}$.
\end{definition}


\section{Existing taxonomies and their analysis}\label{sec:tax}

Since formal concept is a natural notion of bicluster for Boolean data and was rediscovered or reused in bioinformatics, one may suppose that the taxonomy of FCA algorithms is a part of the taxonomy of biclustering algorithms. In fact, paper \cite{Kuznetsov:2002} proposed such a taxonomy (see fig.\ref{fig:tax2002}).



The classification properties of the concept lattice building algorithms encoded as follows: 

\begin{itemize}

\item  $m1$ means incremental approach;
\item $m2$ means that an algorithm uses canonicity based on the lexical order;
\item $m3$ means that an algorithm divides the set of concepts into several parts; 
\item $m4$ designates that an algorithm uses hashing;
\item $m5$ means that an algorithm maintains an auxiliary tree structure; 
\item $m6$ means usage of attribute cache; 
\item $m7$ encodes that an algorithm computes intents by subsequently computing intersections of object intents (i.e., $\{g\}' \cap \{h\}'$);
\item  $m8$ means that an algorithm computes intersections of already generated intents; 
\item $m9$ encodes that an algorithm computes intersections of non-object intents and object intents;
\item $m10$ means that an algorithm uses supports of attribute sets.

\end{itemize}

\begin{figure}
	\centering
	\includegraphics[width=1.00\textwidth]{pics/tax2001}
	\caption{The line diagram of concept lattice for FCA algorithms}
	\label{fig:tax2002}
\end{figure}


We formed a context based on Table II
``Overall comparison of the biclustering algorithms'' \cite{Madeira:2004} and build its concept-based taxonomy in Fig.˜\ref{fig:tax2004}.

Originally, the authors used several criteria to classify the existing (reviewed) biclustering algorithm: type of bicluster, structure of biclusters, type of bicluster discovery, and algorithmic strategy. 

Thus, with respect to the definition of bicluster (its type) the authors differentiate between 1) biclusters with constant values, 2) biclusters with constant values on rows or columns, 3) biclusters with coherent values, and 4) biclusters with coherent evolutions.


The biclusters were classified into one of 9 classes according to their structure.

\begin{itemize}
	\item[a)] Single Bicluster
	\item[b)] Exclusive row and column biclusters (rectangular diagonal blocks after row and column reorder).
	\item[c)] Non-Overlapping biclusters with checkerboard structure.
	\item[d)] Exclusive-rows biclusters.
	\item[e)] Exclusive-columns biclusters.
	\item[f)] Non-Overlapping biclusters with tree structure.
	\item[g)] Non-Overlapping non-exclusive biclusters.
	\item[h)] Overlapping biclusters with hierarchical structure. 
	\item[i)] Arbitrarily positioned overlapping biclusters.
\end{itemize}




Different biclustering methods pursue different goals in terms of the number of discovered biclusters. Thus, they may identify one bicluster at a time or be targeted to discovering one set of biclusters at a time, or they can follow simultaneous bicluster identification, which means that the biclusters are discovered all at the same time. All the three types are possible values of Discovery type attribute in the proposed taxonomy.

Since in many cases the biclustering enumeration is a hard task (the corresponding counting problem may belong to $\#P$ complexity class), different algorithmic enumeration strategies were proposed. Thus, Madeira and Oliviera sort out several categories: 1) Iterative Row and Column Clustering Combination, 2) Divide and Conquer, 3) Greedy Iterative Search, 4) Exhaustive Bicluster Enumeration, and 5) Distribution Parameter Identification.

\begin{landscape}
	
	\begin{figure}
		\centering
		\includegraphics[width=1.8\textwidth]{pics/tax2004}
		\caption{The line diagram of concept lattice for the biclustering taxonomy of Madeira and Oliveira (2004)}
		\label{fig:tax2004}
	\end{figure}
	
\end{landscape}

One of the reasonable questions here is: Why should we build diagrams instead of looking at tables? The answer is we need two complementary views, object-attribute descriptions in tables and ordered clusters of objects such that the objects inside a particular cluster (formal concept) share the same attributes. It is not easy to find such clusters with respect to permutations of rows and columns manually even for small contexts. Moreover, by examining the concept lattice of a certain taxonomy we can find useful attribute dependencies, which can help to discover the underlying taxonomy's domain.



The previous classification done by Madeira and Oliviera was extended and completed almost 11 years later in \cite{Pontes:2015}. We build the corresponding line diagram in Fig.˜\ref{fig:tax2015}.

In fact, the number of classified methods were extended to 47 from 16.


The authors slightly redesigned the proposed classification criteria.  Thus, they split the analysed methods into two categories: metric-based and non-metric based. We counted this split as two corresponding attributes in the related formal context. However, we also decided to include all the mentioned evaluation metrics into our analysis like ``Measure:MSR'' meaning Mean Squared Residue.


The remaining criteria have been changed or extended by the authors. For instance, instead of bicluster types, now eight patterns has been proposed:
\begin{enumerate}
\item Constant;
\item Constant columns;
\item Coherent values;
\item Additive coherent values;
\item Multiplicative coherent values;
\item Simultaneous coherent values;
\item Coherent evolutions;
\item Negative correlations.
\end{enumerate}

The sub-taxonomy based on bicluster structure now contains only six criteria: row exhaustive, column exhaustive, non-exhaustive, row exclusive, column exclusive, and non-exclusive.
 
By means of terms ``exhaustive'' and ``exclusive'' it is possible to describe the desired structure. Thus, exhaustive means where all genes (conditions) should belong to some bicluster, i.e. to be covered by it. Exclusive means whether a gene (condition) has to belong no more than one bicluster; e.g., in non-exclusive case overlapping is allowed.


The attribute algorithmic strategy has been altered in its original form from \cite{Madeira:2004}. The attribute Discovery from \cite{Madeira:2004} has been renamed to Strategy, but the values remain the same: one bicluster at a time, set of biclusters at a time, and simultaneous bicluster identification.


\begin{landscape}
	
	\begin{figure}
		\centering
		\includegraphics[width=1.8\textwidth]{pics/tax2015}
		\caption{The line diagram of concept lattice for the biclustering taxonomy of Pontes et al. (2015)}
		\label{fig:tax2015}
	\end{figure}
	
\end{landscape}


In the beginning of 2000s it was unusual that data analysts and biologists can miss existing biclustering methods (like FCA), which were not applied in the bioinformatics domain yet. However, later FCA was successfully applied in the domain of gene expression analysis \cite{Besson:2005,Kaytoue:2008,Motameny:2008,Kaytoue:2009,Kaytoue:2011}, formal concepts were rediscovered by \cite{Barkow:2006,Prelic:2006} in bioinformatics, approximate greedy \cite{Mirkin:2011} and fast \cite{Ignatov:2008,Ignatov:2012b} methods for dense bicluster discovery in Boolean setting appeared.

However, even the recent taxonomy from \cite{Pontes:2015} does not include any of them. 

To overcome incompleteness caused by the bioinformatics domain view restriction, an attempt to extend the taxonomy of Madeira and Oliveira was done in \cite{Ignatov:2010}. 




	\begin{figure}
		\centering
		\includegraphics[width=1\textwidth]{pics/tax2010}
		\caption{The line diagram of concept lattice for the biclustering taxonomy of Ignatov (2010)}
		\label{fig:tax2010}
	\end{figure}

In addition to the existing criteria, the attribute bicluster values type was added taking two values: binary and numeric. The former shows whether the method is able to find patterns in Boolean object-attribute tables and the latter indicates whether the input entries from $\mathbb{R}$ can be processed by an algorithm. Another important criteria is whether an algorithm based on the notion of closure (operator) from FCA and Closed Frequent Itemset Mining, implicitly or explicitly. The corresponding formal context is given below.

\begin{center}
	\begin{cxt}%
		\cxtName{FCA-related biclustering}%
		\atr{Type:const}
		\atr{Type:const with exceptions}
		\atr{Struct:Arbitr. overl.}
		\atr{Value type:binary}
		\atr{Closure:explicit}
		\atr{Closure:implicit}
		\atr{Val.type:numeric}
		\obj{X.XX.X.}{BiMax}
		\obj{X.XX.XX}{Box biclustering}
		\obj{X.XXX..}{FCA}
		\obj{X.XXX..}{Freq. Closed Itemsets}
		\obj{X.XXX..}{Association rules}
		\obj{XXXX.X.}{Fault-tolerant concepts}
		\obj{XXXXX..}{OA-biclusters}			
	\end{cxt}
\end{center}


In Fig.\ref{fig:tax2010} we show only those objects (biclustering algorithms)  which were not included in the taxonomy of Madeira and Oliveira. By so doing, we considered three general approaches (Formal Concept Analysis, Frequent Closed Itemsets, and Association Rules) and particular modifications of formal concepts (box biclusters \cite{Mirkin:2011}, fault-tolerant concepts \cite{Pensa:2005}, OA-biclusters \cite{Ignatov:2010,Ignatov:2012b}).
	
	
In \cite{Ignatov:2010} it was noted that every association rule of the form $A \rightarrow B$ corresponds to the bicluster $(A' \cup B', A \cup B)$ or $(A' \cap B', A \cup B)$, hence it is possible to consider association rules as a biclustering technique.
	
	
Later, the taxonomical issues of biclustering were discussed in \cite{Flores:2013}; the authors sorted out binary, integer, and real-valued biclustering approaches. Frequent itemset mining algorithms, BiMax, Association Rules and several others were included into a recent survey on pattern-based biclustering algorithms  \cite{Henriques:2015}. Even though the idea of closure was mentioned by the survey authors, they did not use closedness property of the studied patterns as a taxonomical attribute.	Moreover, even though the authors cited several FCA-based papers ob biclustering, they do not treat relationship of this discipline with biclustering. However, as we have mentioned, such relationships were studied on a solid mathematical and experimental level; for example, in \cite{Kaytoue:2014} it was shown that biclustering of numerical data is possible by means of triclustering of the corresponding binary relation.

Implications and Attribute Exploration can help to find hidden attribute dependencies and extend the built taxonomy by new (counter)examples.

Below we provide the reader with top-10 (w.r.t. support measure) implications of Duquenne-Gigues base \cite{Guigues:1986} derived from the formal context of the taxonomy from \cite{Pontes:2015}.

\begin{itemize}
\item   $\{ \mbox{Metric-based, Struct:Non-exclusive} \} \rightarrow \{ \mbox{Struct:Non-Exhaustive} \}$, $sup= 26$
\item  $\{\mbox{Type:Additive coherent val.} \} \rightarrow \{ \mbox{Struct:Non-Exhaustive}\}$,  $sup= 20$
\item $\{\mbox{Measure:MSR} \} \rightarrow \{ \mbox{Metric-based, Struct:Non-Exhaustive}\}$, $sup= 18$ 
\item  $\{\mbox{Type:Additive coherent val., Struct:Non-Exhaustive, Struct:Non-exclusive} \} \rightarrow \{ \mbox{Metric-based}\}$, $sup= 18$
\item  $\{\mbox{Strategy:One} \} \rightarrow \{ \mbox{Struct:Non-Exhaustive, Struct:Non-exclusive}\}$, $sup= 17$
\item $\{\mbox{Type:Coherent values, Struct:Non-Exhaustive} \} \rightarrow \{ \mbox{Struct:Non-exclusive}\}$, $sup= 15$
\item  $\{\mbox{Strategy:One set} \} \rightarrow \{ \mbox{Struct:Non-Exhaustive}\}$, $sup= 13$ 
\item  $\{\mbox{Measure:Var} \} \rightarrow \{ \mbox{Metric-based, Struct:Non-Exhaustive, Struct:Non-exclusive}\}$, $sup= 8$
\item $\{\mbox{Type:Negative correlations} \} \rightarrow \{ \mbox{Struct:Non-Exhaustive, Struct:Non-exclusive}\}$,  $sup= 7$
\item  $\{\mbox{Metric-based, Struct:Non-Exhaustive, Strategy:Simult} \} \rightarrow$

 $ \{ \mbox{Type:Additive coherent val., Struct:Non-exclusive}\}$, $sup= 7$ 
\end{itemize}

Since we deal with implications, their confidence measure is equal to 1. The size of the whole set of implications in Duquenne-Gigues base is 105.

If we start attribute exploration for the same context, then the first question in a row is the following:

Is it true, that when biclustering technique has attribute ``Strategy:One set'', that it also has attribute ``Struct:Non-exhaustive''?

An expert can either agree with the implication  $\{ \mbox{Strategy:One set} \to \mbox{Struct:Non-exhaustive}\}$ or disagree. In the latter case, (s)he needs to provide a counterexample: a biclustering technique which follows discovery strategy ``one set of biclusters at a time'' but does not result in biclusters of the structure type ``exhaustive''. There is also an option to stop Attribute Exploration process at every step.


\section{Multimodal clustering and closed n-sets}\label{sec:multi}

Since the field of biclustering is a subdomain of multimodal or relational clustering, the taxonomy can be extended by applying similar criteria to n-ary relation and tensor clustering algorithms.

Thus, the notion of formal concept was generalised for triadic \cite{Lehmann:1995} and polyadic case \cite{Voutsadakis:2002}. There are efficient algorithms to find triconcepts \cite{Jaschke:2006} and poliadic concepts (closed n-sets) \cite{Cerf:2009}. There exist relaxations of triconcept and poliadic concept notions, triclusters and n-clusters, which allow for certain entries inside such n-dic concept to be zeros \cite{Mirkin:2011,Ignatov:2013,Cerf:2013}; the theoretical and experimental comparison is done in \cite{Ignatov:2015ml}.  There are also methods for mining closed patterns in n-ary relations \cite{Spyropoulou:2014}. Two biclustering approaches can be used for mining two formal contexts simultaneously, which shares either set of attributes or objects; this results in pseudotriclusters \cite{Gnatyshak:2012}. As for purely biological applications of triclustering we may suggest reading, for example, \cite{Zhao:2005} and \cite{Li:2009}.


	
\section{Conclusion and future work}


Even though the taxonomy building of a particular subfield of Data Analysis or Computer Science is not as laborious as devising Carl Linnaeus' pre-phylogenetic taxonomy, this is not an easy task to merge several such existing taxonomies and build a unified one. Similarly to new species discovery, new algorithms can be proposed and since they can contain new specific features, new classification attributes may be needed.

One of the possible schemes of taxonomy maintaining here could be done in terms of Attribute Exploration \cite{Ganter:1999}.

At a certain moment the group of expert fixes the set of existing biclustering methods and proposes suitable criteria for their classification. A person or a team which has proposed a new biclustering method should classify the method according to the chosen scheme, then it should be validated by experts. Such a team can propose an extra criterion for method classification. If a person or a team is going to propose a new method for an unexplored combination of classification attributes, it is possible to run attribute exploration to see which prospective types of methods are missing to date.  By means of Object Exploration, it may become clear that some attributes are missing, e.g. it is evident that formal concepts or Boolean biclusters is only a particular case of bicluster type with constant values and we need at least one new attribute, Boolean entry values.

Since a taxonomy may be used not only for classification itself, but as a search index for potential users, we may suggest using several ways of interactive visualisation: tree-based (TABASCO-like), concept lattice based (line diagrams), object-attribute tables, and nested line diagrams. The latter can help when someone is interested in a special main set of attributes, which should be shown in the outer taxonomy on the line diagram; the inner taxonomy can be shown if the method-seeker needs a finer level granularity or more detailed description inside of the selected node from the outer taxonomy. 

It is important to note that taxonomies can be considered as a special case of ontologies, and here FCA was successfully used both for ontology merging and completion \cite{Ganter:03,Sertkaya:2010}.

 
There are two main tasks for our future studies: 1) unifying the existing bicluster taxonomies, and 2) creation a taxonomy of multimodal clustering techniques. Even though there are several good tools for building and managing concept lattices like Concept Explorer, we need to rely on more flexible tools with extensible components. In particular we hope that FCART can become our tool of choice in the near future \cite{Neznanov:2014}.

\subsubsection*{Acknowledgements.}
We would like to thank  Sergei Obiedkov and Derrick Kourie for a piece of advice and their earlier work on the topic. This work was supported by the Basic Research Program at the National Research University Higher School of Economics in 2015-2016 and performed in the Laboratory of Intelligent Systems and Structural Analysis. The first author was also supported by Russian Foundation for Basic Research (grant \#13-07-00504).

\bibliographystyle{splncs}

\bibliography{bictax}
\end{document}


BicTax.bbl
\begin{thebibliography}{10}

\bibitem{Hartigan:1972}
Hartigan, J.A.:
\newblock {Direct Clustering of a Data Matrix}.
\newblock Journal of the American Statistical Association \textbf{67}(337)
  (1972)  123--129

\bibitem{Mirkin:1996}
Mirkin, B.:
\newblock Mathematical Classification and Clustering.
\newblock Kluwer, Dordrecht (1996)

\bibitem{Madeira:2004}
Madeira, S.C., Oliveira, A.L.:
\newblock Biclustering algorithms for biological data analysis: A survey.
\newblock IEEE/ACM Trans. Comput. Biology Bioinform. \textbf{1}(1) (2004)
  24--45

\bibitem{wille:1982}
Wille, R.:
\newblock Restructuring lattice theory: An approach based on hierarchies of
  concepts.
\newblock In Rival, I., ed.: Ordered Sets. Volume~83 of NATO Advanced Study
  Institutes Series.
\newblock Springer Netherlands (1982)  445--470

\bibitem{Ganter:1999}
Ganter, B., Wille, R.:
\newblock Formal Concept Analysis: Mathematical Foundations.
\newblock Springer, Berlin/Heidelberg (1999)

\bibitem{Barkow:2006}
Barkow, S., Bleuler, S., Prelic, A., Zimmermann, P., Zitzler, E.:
\newblock Bicat: a biclustering analysis toolbox.
\newblock Bioinformatics \textbf{22}(10) (2006)  1282--1283

\bibitem{Kaytoue:2009}
Kaytoue, M., Duplessis, S., Kuznetsov, S., Napoli, A.:
\newblock Two fca-based methods for mining gene expression data.
\newblock In FerrГ©, S., Rudolph, S., eds.: Formal Concept Analysis. Volume
  5548 of Lecture Notes in Computer Science.
\newblock Springer Berlin Heidelberg (2009)  251--266

\bibitem{Cleophas:2005}
Cleophas, L.G., Watson, B.W.:
\newblock Taxonomy-based software construction of {SPARE} time: a case study.
\newblock {IEE} Proceedings - Software \textbf{152}(1) (2005)  29--37

\bibitem{Cleophas:2006}
Cleophas, L.G., Watson, B.W., Kourie, D.G., Boake, A., Obiedkov, S.A.:
\newblock {TABASCO:} using concept-based taxonomies in domain engineering.
\newblock South African Computer Journal \textbf{37} (2006)  30--40

\bibitem{Roth:2008}
ROTH, C., OBIEDKOV, S., KOURIE, D.G.:
\newblock On succinct representation of knowledge community taxonomies with
  formal concept analysis.
\newblock International Journal of Foundations of Computer Science
  \textbf{19}(02) (2008)  383--404

\bibitem{Ignatov:2010}
Ignatov, D.:
\newblock Models, Algorithms, and Software Tools of Biclustering Based on
  Closed Sets.
\newblock PhD thesis, State University Higher School of Economics, Moscow
  (2010)

\bibitem{Ignatov:2012b}
Ignatov, D.I., Kuznetsov, S.O., Poelmans, J.:
\newblock {Concept-Based Biclustering for Internet Advertisement}.
\newblock In: Data Mining Workshops (ICDMW), 2012 IEEE 12th International
  Conference on. (Dec 2012)  123--130

\bibitem{Kuznetsov:2002}
Kuznetsov, S.O., Obiedkov, S.A.:
\newblock {Comparing performance of algorithms for generating concept
  lattices}.
\newblock J. Exp. Theor. Artif. Intell. \textbf{14}(2-3) (2002)  189--216

\bibitem{Pontes:2015}
Pontes, B., Gir{\'a}ldez, R., Aguilar-Ruiz, J.S.:
\newblock Biclustering on expression data: A review.
\newblock Journal of Biomedical Informatics \textbf{57} (2015/12/28)  163--180

\bibitem{Besson:2005}
Besson, J., Robardet, C., Boulicaut, J., Rome, S.:
\newblock Constraint-based concept mining and its application to microarray
  data analysis.
\newblock Intell. Data Anal. \textbf{9}(1) (2005)  59--82

\bibitem{Kaytoue:2008}
Kaytoue-Uberall, M., Duplessis, S., Napoli, A.:
\newblock Using formal concept analysis for the extraction of groups of
  co-expressed genes.
\newblock In Le~Thi, H., Bouvry, P., Pham~Dinh, T., eds.: Modelling,
  Computation and Optimization in Information Systems and Management Sciences.
  Volume~14 of Communications in Computer and Information Science.
\newblock Springer Berlin Heidelberg (2008)  439--449

\bibitem{Motameny:2008}
Motameny, S., Versmold, B., Schmutzler, R.:
\newblock Formal concept analysis for the identification of combinatorial
  biomarkers in breast cancer.
\newblock In Medina, R., Obiedkov, S., eds.: Formal Concept Analysis. Volume
  4933 of Lecture Notes in Computer Science.
\newblock Springer Berlin Heidelberg (2008)  229--240

\bibitem{Kaytoue:2011}
Kaytoue, M., Kuznetsov, S.O., Napoli, A., Duplessis, S.:
\newblock Mining gene expression data with pattern structures in formal concept
  analysis.
\newblock Information Sciences \textbf{181}(10) (2011)  1989 -- 2001 Special
  Issue on Information Engineering Applications Based on Lattices.

\bibitem{Prelic:2006}
Prelić, A., Bleuler, S., Zimmermann, P., Wille, A., Bühlmann, P., Gruissem,
  W., Hennig, L., Thiele, L., Zitzler, E.:
\newblock A systematic comparison and evaluation of biclustering methods for
  gene expression data.
\newblock Bioinformatics \textbf{22}(9) (2006)  1122--1129

\bibitem{Mirkin:2011}
Mirkin, B., Kramarenko, A.:
\newblock Approximate bicluster and tricluster boxes in the analysis of binary
  data.
\newblock In Kuznetsov, S., Ślęzak, D., Hepting, D., Mirkin, B., eds.: Rough
  Sets, Fuzzy Sets, Data Mining and Granular Computing. Volume 6743 of Lecture
  Notes in Computer Science.
\newblock Springer Berlin Heidelberg (2011)  248--256

\bibitem{Ignatov:2008}
Ignatov, D.I., Kuznetsov, S.O.:
\newblock Concept-based recommendations for internet advertisement.
\newblock In Belohlavek, R., Kuznetsov, S.O., eds.: Proc. of The Sixth
  International Conference Concept Lattices and Their Applications (CLA'08),
  Palacky University, Olomouc (2008)  157–--166

\bibitem{Pensa:2005}
Pensa, R.G., Boulicaut, J.:
\newblock Towards fault-tolerant formal concept analysis.
\newblock In: AI*IA. (2005)  212--223

\bibitem{Flores:2013}
Flores, J.L., Inza, I., Larrañaga, P., Calvo, B.:
\newblock A new measure for gene expression biclustering based on
  non-parametric correlation.
\newblock Computer Methods and Programs in Biomedicine \textbf{112}(3) (2013)
  367 -- 397

\bibitem{Henriques:2015}
Henriques, R., Antunes, C., Madeira, S.C.:
\newblock A structured view on pattern mining-based biclustering.
\newblock Pattern Recognition \textbf{48}(12) (12 2015)  3941--3958

\bibitem{Kaytoue:2014}
Kaytoue, M., Kuznetsov, S.O., Macko, J., Napoli, A.:
\newblock Biclustering meets triadic concept analysis.
\newblock Ann. Math. Artif. Intell. \textbf{70}(1-2) (2014)  55--79

\bibitem{Guigues:1986}
Guigues, J.L., Duquenne, V.:
\newblock Familles minimales d'implications informatives résultant d'un
  tableau de données binaires.
\newblock Mathématiques et Sciences Humaines \textbf{95}(1) (1986)  5--18 In
  French.

\bibitem{Lehmann:1995}
Lehmann, F., Wille, R.:
\newblock A triadic approach to formal concept analysis.
\newblock In: Conceptual Structures: Applications, Implementation and Theory,
  Third International Conference on Conceptual Structures, {ICCS} '95, Santa
  Cruz, California, USA, August 14-18, 1995, Proceedings. (1995)  32--43

\bibitem{Voutsadakis:2002}
Voutsadakis, G.:
\newblock Polyadic concept analysis.
\newblock Order \textbf{19}(3) (2002)  295--304

\bibitem{Jaschke:2006}
J{\"{a}}schke, R., Hotho, A., Schmitz, C., Ganter, B., Stumme, G.:
\newblock {TRIAS} - an algorithm for mining iceberg tri-lattices.
\newblock In: Proceedings of the 6th {IEEE} International Conference on Data
  Mining {(ICDM} 2006), 18-22 December 2006, Hong Kong, China. (2006)  907--911

\bibitem{Cerf:2009}
Cerf, L., Besson, J., Robardet, C., Boulicaut, J.:
\newblock Closed patterns meet \emph{n}-ary relations.
\newblock {TKDD} \textbf{3}(1) (2009)

\bibitem{Ignatov:2013}
Ignatov, D.I., Kuznetsov, S.O., Poelmans, J., Zhukov, L.E.:
\newblock Can triconcepts become triclusters?
\newblock Int. J. General Systems \textbf{42}(6) (2013)  572--593

\bibitem{Cerf:2013}
Cerf, L., Besson, J., Nguyen, K., Boulicaut, J.:
\newblock Closed and noise-tolerant patterns in n-ary relations.
\newblock Data Min. Knowl. Discov. \textbf{26}(3) (2013)  574--619

\bibitem{Ignatov:2015ml}
Ignatov, D., Gnatyshak, D., Kuznetsov, S., Mirkin, B.:
\newblock Triadic formal concept analysis and triclustering: searching for
  optimal patterns.
\newblock Machine Learning (2015)  1--32

\bibitem{Spyropoulou:2014}
Spyropoulou, E., Bie, T.D., Boley, M.:
\newblock Interesting pattern mining in multi-relational data.
\newblock Data Min. Knowl. Discov. \textbf{28}(3) (2014)  808--849

\bibitem{Gnatyshak:2012}
Gnatyshak, D., Ignatov, D.I., Semenov, A., Poelmans, J.:
\newblock Gaining insight in social networks with biclustering and
  triclustering.
\newblock In: Perspectives in Business Informatics Research - 11th
  International Conference, {BIR} 2012, Nizhny Novgorod, Russia, September
  24-26, 2012. Proceedings. (2012)  162--171

\bibitem{Zhao:2005}
Zhao, L., Zaki, M.J.:
\newblock Tricluster: An effective algorithm for mining coherent clusters in 3d
  microarray data.
\newblock In: Proceedings of the {ACM} {SIGMOD} International Conference on
  Management of Data, Baltimore, Maryland, USA, June 14-16, 2005. (2005)
  694--705

\bibitem{Li:2009}
Li, A., Tuck, D.:
\newblock An effective tri-clustering algorithm combining expression data with
  gene regulation information.
\newblock Gene regulation and systems biology \textbf{3} (2009)  49--64

\bibitem{Ganter:03}
Ganter, B., Stumme, G.:
\newblock Creation and merging of ontology top-levels.
\newblock In: Conceptual Structures for Knowledge Creation and Communication,
  11th International Conference on Conceptual Structures, {ICCS} 2003 Dresden,
  Germany, July 21-25, 2003 Proceedings. (2003)  131--145

\bibitem{Sertkaya:2010}
Sertkaya, B.:
\newblock A survey on how description logic ontologies benefit from {FCA}.
\newblock In: Proceedings of the 7th International Conference on Concept
  Lattices and Their Applications, Sevilla, Spain, October 19-21, 2010. (2010)
  2--21

\bibitem{Neznanov:2014}
Neznanov, A., Parinov, A.:
\newblock {FCA} analyst session and data access tools in {FCART}.
\newblock In Agre, G., Hitzler, P., Krisnadhi, A.A., Kuznetsov, S.O., eds.:
  Artificial Intelligence: Methodology, Systems, and Applications - 16th
  International Conference, {AIMSA} 2014, Varna, Bulgaria, September 11-13,
  2014. Proceedings. Volume 8722 of Lecture Notes in Computer Science.,
  Springer (2014)  214--221

\end{thebibliography}
