In this paper a new incremental algorithm for computing nconcepts is proposed. The time complexity of the algorithm is O(jIj2 In jBnj), where jIj is the size of a context (an n-ary relation), In = jK1jjBn 1j is the input, where K1 is a set corresponding to an added dimension and Bn 1 is the set of (n 1)-concepts. The output Bn of the algorithm is a set of n-concepts. The algorithm creates n-concepts (i.e. elements in Bn) by merging sequentially (n 1)-concepts from Bn 1 with the corresponding elements from the n-th dimension (i.e. set K1).
Mining of closed itemsets are widely used in many practical applications of
data mining. Introduced by Rudolf Wille in 1982, formal concepts (i.e. dyadic
closed itemsets) was expanded later to the triadic [
The large number of algorithms has been proposed for computing formal
concepts. For a comparative study of algorithms see [
In this paper, we propose an algorithm for computing n-concepts sequentially from (n 1)-concepts.
The paper is organized as follows. In Section 2 we describe the proposed approach and present the algorithm. In Section 3 we prove its properties. The time complexity is discussed in Section 4. Section 5 brie y concludes.
In this section we provide the main de nitions and the idea of the algorithm.
Let us consider an n-ary context K = (K1; K2; :::; Kn; In). KK1=a K denotes a subcontext with xed value a 2 K1 , i.e. a context with the following relation IKn1=a = ffa; k2; :::; kng j k2 2 K2; :::; kn 2 Kn; (a; k2; :::; kn) 2 Ing. A subcontext where elements from the several dimensions are xed is denoted in the same way. For example, a context where only elements aj 2 Kj and ai 2 Ki are xed is denoted by IKni=ai;Kj=aj = ffk1; :::; ki 1; ai; ki+1; :::; kj 1; aj; kj+1; :::; kng j k1 2 K1; ki 1 2 Ki 1; ki+1 2 Ki+1; :::; kj 1 2 Kj 1; kj+1 2 Kj+1; kn 2 Kn; (k1; :::; ki 1; ai; ki+1; :::; kj 1; aj; kj+1; :::; kn) 2 Ing.
A set of n-concepts corresponding to the context K is denoted by Bn. Bnxi 1 denotes a set of (n 1)-concepts of KK1=xi . KK1=xi can be represented as an n-ary context where the rst dimension consists of a single element, thus Bnfag = B(KK1=fag) = f(fag; X2; :::; Xn) j (X2; :::; Xn) 2 Bna 1g. A set of n-concepts that corresponds to a subcontext KK1=fx1;x2;:::;xig, is denoted by Bnfx1;x2;:::;xig. Example Let us consider a context given on Fig.1 (a). The context is comprised of the following sets: K1 = f1; 2; 3; 4g, K2 = fa; b; c; dg, K3 = f ; ; ; g.
Subcontext KK1=2 corresponds to the dyadic relation given in Fig. 1 (b).The set of dyadic concepts is B22 = f f ) .
( ag; f ; g); (fa; b; cg; f g); (fb; cg; f ; ; g g
The set of triadic concepts for subcontext KK1=f1;2g given on Fig. 1 (c) is following:
B2f1;2g = f(f1; 2g; fag; f ; g); (f1g; fdg; f ; g); (f1g; fa; dg; f g); (f2g; fa; b; cg; f g); (f2g; ffb; cg; f ; ; g))g:
A subcontext with xed elements from two dimensions in the triadic case takes the following form: KK1=2;K2=b = f ; ; g.
During the recursive descent in step 8 of Algorithm 2 a particular value a 2 Ki form the next dimension i 2 [1; 2; :::; n 2] is xed. At the end of the descent, for a subcontext KK1=a1;:::;Kn 2=an 2 , any algorithm for computing formal concepts can be applied.
During the recursive ascent (see step 9 of Algorithm 2) (n 1)-concepts from Bna 1, a 2 K1 are merged. In the recursive ascent on the i-th level the algorithm builds (n i + 1)-concepts (the set of the concepts is denoted by Bn in Algorithm 2) using computed during the recursive descent (n i)-concepts corresponding to a particular value a 2 K1. With the introduced notation, the fx1g (derived from states of Bn in Algorithm 2 is changed as follows: Bnf;g, Bn Bnx1 1), Bn fx1;x2;:::;xjK1jg (the fx1;x2g (derived by merging Bnx1 1 and Bnx2 1), ..., Bn
xj , where j 2 fx1; x2; :::; xjK1jg). result of the sequential merging of Bn 1
Algorithm 3 iteratively constructs n-concepts by merging n-concepts from Bnfx1;x2;:::;xi 1g with (n 1)-concepts from Bnxi 1. On each call a new set of (n 1)concepts, corresponding to a particular value xi 2 K1, is added to a set of nconcepts. To add (n 1)-concepts to a set of n-concepts, each (n 1)-concept (a) A triadic context 1 2 X = (X2; :::; Xn) 2 Bnxi 1 is expanded to X = (fxig; X2; :::; Xn) (see step 3 of Algorithm 3). A function mark assigns a binary label to a concept, a function isF ull(Y1) checks whether Y1 K1 contains all already considered elements a 2 K1.
Set-wise inclusion/exclusion relations between the corresponding sets A2, ..., An of concepts from Bnxi 1 and Bn are used to reduce the number of operations and to avoid the redundant concept computation.
Algorithm 4 checks whether an n-ary itemset Z1; :::; Zn is closed by iterating over dimensions. For the selected dimension dim it iterates over elements from Kdim n Zdim and checks elements from Zi, i 2 f1; :::; ng n fdimg. It stops when an empty entry is found in the context for the rst time or when all the dimensions dim are checked.
Algorithm 5 works with a trie. The trie stores concept (A1; :::; An) as a sequence of lexicographically ordered elements from A1, ... An. A sequence of sets Ai is xed, i.e. elements of Ai are closer to the root than elements of Aj for all i < j and elements from each dimension i are lexicographically ordered within set Ai. To ensure the uniqueness of (A1; :::; An) it is su cient to check the sequence of the lexicographically ordered elements from A1 to An 1.
Algorithm 1: CreateSubcontext 1 begin 2 return KK1=a = (K2; :::; Kn; IKn1=a)
Data: a 2 K1; K = (K1; K2; :::; Kn; In) Result: a subcontext KK1=a consisted of a set of (n f(k2; k3; :::; kn) j (a; k2; k3; :::; kn) 2 Ing 1) tuples Example Let us consider how the algorithm works using a context from the running example. The algorithm consecutively computes triconcepts from the formal concepts corresponding to the following contexts: KK1=1, KK1=2, KK1=3, KK1=4. Parameters and results of the function \getNConcepts" in the execution order are given in Table 1.
Algorithm 2: ComputeConcepts
Data: K = (K1; K2; :::; Kn; In)
Result: the set Bn = ffA1; A2; :::; Ang jAi 1 begin 2 if n = 2 then 3 return ComputeF ormalConcepts(K) Proof Let us assume that Y is marked, but Y 2= Bnfx1;:::;xig. Then 9Z(Z 2 Bnfx1;:::;xig), such that Y Z. Therefore, (Y1 [ fxig) Z1 ) xi 2 Z1, Z2
Input Bn ;
a Bn 1
Output
Bn (fag;f ; g), (f1g;fag;f ; g), (fdg;f ; g), (f1g;fdg;f ; g), (fa;dg;f g) (f1g;fa;dg;f g)
(f1;2g;fag;f ; g), (f1g;fag;f ; g), (fag;f ; g), (f1g;fdg;f ; g), (f1g;fdg;f ; g), (fb;cg;f ; ; g), (f1g;fa;dg;f g), (f1g;fa;dg;f g) (fa;b;cg;f g) (f2g;fb;cg;f ; ; g), (f2g;fa;b;cg;f g) (f1;2g;fag;f ; g), (f1g;fdg;f ; g), (fc;dg;f g), (fb;cg;f ; g), (f2g;fa;b;cg;f g) (f1g;fa;dg;f g), (f2g;fb;cg;f ; ; g), (fcg;f ; ; g), (f3g;fc;dg;f g), (fa;b;cg;f g) (f2g;fb;cg;f ; ; g), Value in K1 1 2 3 (f1;2g;fag;f ; g), (f1g;fdg;f ; g), (f1g;fa;dg;f g), (f2;3g;fa;b;cg;f g), (f3g;fc;dg;f g), (f1;2;3g;fag;f g), (f2;3g;fb;cg;f ; g), (f3g;fcg;f ; ; g) 4 (f2g;fb;cg;f ; ; g), (fdg;f g) X2; :::; Zn Xn. Due to the assumption (Y Z) and steps 14 and 25 of Algorithm 3, X2 Z2; :::; Xn Zn. These relations holds i X2 = Z2; :::; Xn = Zn.
fx1;:::;xi 1g, namely, the closedness and This is contrary to the properties of Bn uniqueness of elements, thus our assumption is wrong, i.e. Y is closed.
If, in addition, Y1 = fx1; :::; xi 1g, then any other concepts Z = (Z1; :::; Zn) 2 Bnfx1;:::;xi 1g are met the following conditions: Z1 Y1 [ fxig and there exists Zj such that Yj Zj. Since Zl \ Xl Xl = Yl, one can not obtain (Z1 [ fx1g; Z2 \ X2; :::Zn \ Xn) 6 (Y1 [ fx1g; X2; :::; Xn). It was required to prove. Property 2. If Z = (Z1; X2; :::; Xn) has been updated in step 22 (and added in fx1;:::;xig. step 31), then Z 2 Bn
fx1;:::;xig, i.e. it is not closed and 9Y = Proof Let us assume that Z 2= Bn (Y1; :::; Yn) (Y 2 Bnfx1;:::;xig), such that Z Y . Since (X2; :::; Xn) 2 Bnxi 1, then Z is not closed i 9y(y 2 Y1), such that y 2= Z1. The last inference is impossible, since Algorithm 3 ensures presence of all elements y 2 Y1, such that X2 Y2; :::; Xn Yn. We get the contradiction (i.e. y 2 Z1) to the assumption fx1;:::;xig. that Z is unclosed. It is wrong and Z 2 Bn Property 3. The modi cations in step 26 produce a concept (i.e. closed itemset): Proof Let us assume that we have updated Y , i.e. we have got Y mod = (Y1 [ fx1;:::;xi 1g, but Y mod = xi; Y2; :::; Yn) (in the listing xi is denoted by a) and Y 2 Bn 2 Bnfx1;:::;xig. Hence, Y mod = Y1, that contradicts to our assumption and Y mod 2 fx1;:::;xig.
Bn Property 4. If Y 2 Btemp, constructed in steps 35-43, then Y is closed and unique.
The closedness and uniqueness of concepts is checked implicitly by Algorithms 4 and 5, respectively.
As it was shown before, the algorithm produces n-ary itemsets which are closed. Property 5 claims that the algorithm computes all concepts and does not miss any closed itemsets.
Property 5. Algorithm 3 computes all n-concepts and only them, i.e. X 2 Bn , X 2 B(K).
Proof It has been proved above that X 2 Bn ) X 2 B(K).
Let us prove that X 2 B(K) ) X 2 Bn by the mathematical induction. Basis: For any xed values k1; k2; :::; kn 2 from the corresponding subcontext KK1=k1;K2=k2;:::;Kn 2=kn 2
K we get for all X 2 B2k1;k2;:::;kn 2 ) X 2 B(KK1=k1;K2=k2;:::;Kn 2=kn 2 ), since a correct algorithm for formal concepts is used.
Inductive step: Show that if for any x 2 K1 and the subcontext KK1=x K it is true that 8x8X(x 2 K1) (X 2 B(KK1=x)) ) X 2 Bnx 1, then 8Z (Z 2 B(K)) ) Z 2 Bn.
Accordingly to the algorithm, 8x9Z(x 2 K1)(Z 2 Bn), such that x 2 Z1 and all concepts of B(KK1=x) present in Bn with maximal possible set X1.
The intersection X 2 Bnxi 1 with each elements of Bnfx1;:::;xi 1g (closed concepts of the previous step) results in the creation of all possible combinations of (X2; :::; Xn) with other already existed elements. Since on each iteration a new fx1;:::;xi 1g, we will get all possible combinations element xi 2 K1 is added to Bn (Y2; :::; Yn) for all possible subsets of fx1; :::; xig K1. As the result, we obtain all maximal Z 2 Bn. 4
In this section the time complexity of Algorithm 3 is discussed. The input of the algorithm is a set f(fag; A2; :::; An) j a 2 K1g with the space complexity inp = O(jK1jjBn 1j), the output is Bn with the space complexity O(jBnj), and jBnj jK1jjBn 1j.
It should be noted here that as in [
The number of pairwise intersections of (n 1) elements of Bn and Bna 1 is reduced by utilizing mark labels, CMP. The absence of unclosed and non-unique elements is ensured by applying Algorithm 4 and 5 to a subset of generated concepts.
The closedness veri cation (Algorithm 4) for an itemset (A1; :::; An) takes at most O(jK1 n A1jjA2j:::jAnj + jA1jjK2 n A2j:::jAnj + ::: + jA1jjA2j:::jKn n Anj), more generally, O(njK1jjK2j:::jKnj).
Thus, the time complexity of the algorithm is
p|airwise compa{rzison of itemset}s
O(jK1jjK2j:::jKnjjBnjjBn 1j(CV + U V + T P )); where CV = jK1jjK2j:::jKnj, U V = jK1jjK2j:::jKn 1j, T U = jK1jjK2j:::jKn 1j correspond to the number of operations for the closedness validation, the uniqueness validation and the trie update.
In terms of the input (p = jK1jjBn 1j) and the output (K = jBnj) the complexity takes the following form: O(jK2j:::jKnj p K (CV + U V + T U )), or, more generally, O(jInj2p K). 5
In this paper we have proposed a new incremental algorithm for computing nconcepts. The algorithm can be based on any algorithm for computing formal concepts. The algorithm recursively computes k-concepts, where k 2 f3; :::; ng and iteratively merges k 1-concepts to derive k-concepts. It has O(jInj2pK) time complexity, p = jK1jjBn 1j and K = jBnj are the size of the input and the output, respectively.
An important direction for future work is to compare the proposed algorithm with other algorithms for generating concepts of dimension n 3. Sections 1, 2 were made by T. Makhalova and supported by the Russian Science Foundation under grant 17-11-01294 and performed at National Research University Higher School of Economics, Russia. The work of Lhouri Nourine was supported by ANR project Graphen ANR-15-CE40-0009.