Attenuation characteristics analysis of concept tree

3.1.1 The node characteristics of concept tree

Definition 6. In formal context K = (G, M, I), ∀m ∈ M. The number of sub trees owned by attribute node m is called the degree of the node and is recorded as # d (m).

Definition 7. In formal context K = (G, M, I), ∀m ∈ M, its concept tree is Tree = r (T₁, T₂, T₃, . . . , T _n ), if # d (m) =0, then the node m is called leaf node; if # d (m) ≠0, then the node m is called branch node.

Definition 8. In the concept tree Tree = r (T₁, T₂, T₃, . . . , T _n ), the path formed when the node m is reached is <ω, m>, where l ∈ M and # d (l) =0. If the node m is the leaf node, the path formed by the node m is <ω _i , m >  ^Leaf , where ω_i = (r, . . . , m), i ∈ {1, . . . , n}, n is the number of paths with node m. If the node m is the branch node, the path formed by the node m is <ω _i , m > ^Branch, where ω _i  = (r, . . . , m, . . . , l), i ∈ {1, . . . , n}, n is the number of paths with node m, l is the leaf node in path ω _i .

Property 1. In the concept tree Tree = r (T₁, T₂, T₃, . . . , T _n ), an attribute m can be both leaf node and branch node.

Proof: From Definition 7 and Definition 8, In the concept tree Tree = r (T₁, T₂, T₃, . . . , T _n ), the path through node m is <ω _i , m>, where ω_i = (r, . . . , m) or ω _i  = (r, . . . , m, . . . , l), # d (m) =0 or # d (m) ≠0. Therefore, the attribute m can be both leaf node and branch node.

In the concept tree shown in Fig. 1(b), the two paths formed by the leaf node d are <ω₁, d> and <ω₂, d>, where ω₁ = (r, b, a (d)) and ω₂ = (r, e, b, a (d)), the three paths formed by the branch node e are <ω₁, e>, <ω₂, e> and <ω₃, e>, where ω₁ = (r, e, b, a (d)), ω₂ = (r, e, b, c) and ω₃ = (r, e, a).

Definition 9. In the concept tree Tree = r (T₁, T₂, T₃, . . . , T _n ), it is specified that the layer number of root node r is the first layer, and the layer number of node is the k _m layer. Then the path length from r to the k _m layer node is recorded as L ( < ω i , m > ) = k m - 1 .(6)

As shown in Fig. 1(b), in path <ω₁, a> and ω₁ = (r, e, a), node a is in the third layer, and the path length from root node to node a is L < ω₁, m >  ^Leaf  = 2.

For a particular formal context, the concept lattice is unique. Each node represents a concept in the concept lattice. Concept tree is a subset of concept lattice. In concept tree Tree = r (T₁, T₂, T₃, . . . , T _n ), each node represents a concept, which is defined as follows:

Definition 10. All concepts in the concept tree Tree = r (T₁, T₂, T₃, . . . , T _n ) are expressed as B ( K T ) . All concepts in path <ω _i , m> are B ( K < ω , m > ) , where ( A 1 , B 1 ) , . . . , ( A n , B n ) ∈ B ( K < ω , m > ) , n is the number of nodes in the path except r, the corresponding concept of node m is (A _m , B _m ).

Property 2. In formal context K = (G, M, I), ( A , B ) ∈ B ( K ) , m _i , m _j  ∈ M and g (m _i ) = g (m _j ). If m _i  ∈ B, then m _j  ∈ B.

Proof: For g _i , g _j  ∈ G and f (g _i ) = f (g _j ), if g _i  ∈ A, then g _j  ∈ A. Therefore, the same reason can be obtained. For ( A , B ) ∈ B ( K ) and g (m _i ) = g (m _j ) satisfy m _i  ∈ B, then m _j  ∈ B.

In the concept tree, the degree of coupling of different nodes is different, and the degree of coupling between different nodes is analyzed according to the concept of nodes, as defined below:

Definition 11. The node coefficient of the node m is recorded as ψ ( m ) = # ( A m ) # ( ⋃ i n A i )(7) where A _m is the extension of the node m corresponding concept, ⋃ i n A i is the integration of all concept extensions in path <ω _i , m>, # (·) is the size of the set, n is the number of nodes except root node in path <ω _i , m>, ψ (m| < ω _i , m >  ^Leaf ) is the leaf node coefficient, ψ (m| < ω _i , m >  ^Branch ) is the branch node coefficient.

Definition 12. In formal context K = (G, M, I),∀m ∈ M, its concept tree is Tree = r (T₁, T₂, T₃, . . . , T _n ). The coupling of node m in path <ω _i , m> is ξ m K = ∑ j = 1 X ψ ( m | < ω i , m > Leaf ) ( λ 1 L < ω i , m > Leaf ) + ∑ j = 1 Y ψ ( m | < ω i , m > Branch ) ( λ 2 L < ω i , m > Branch )(8)ψ (m| < ω _i , m >  ^Leaf ) represents the leaf node coefficient, ψ (m| < ω _i , m >  ^Branch ) represents the branch node coefficient. L (< ω _i , m >  ^Leaf ) shows the path length of leaf node. L (< ω _i , m >  ^Branch ) shows the path length of branch node. λ₁ and λ₂ are given coefficients, where 0 < λ₁ < λ₂ < 1. X is the number of paths when the path of node m is a leaf node, Y is the number of paths when the path of node m is a branch node, j ∈ {1, . . . , N}.

According to the analysis of node coupling in the concept tree, the less coupling of nodes represents the smaller the correlation between the node and other nodes. Therefore, the smaller the coupling is, the earlier the node deletes. The nodes are sorted according to the coupling, and then enter the attenuation process. The attenuation of attributes is represented by the deletion of nodes in the concept tree. Therefore, the first node to be deleted in the concept tree is the node with the minimum coupling.

When a node in the concept tree is deleted, the formal context will be updated, and the coupling of each node will also be updated. Therefore, there are the following definitions:

Definition 13. In formal context K = (G, M, I),∀m ∈ M, its concept tree is Tree = r (T₁, T₂, T₃, . . . , T _n ). The formal context after the attenuation of the node m is updated to K ⁱ  = (G ⁱ , M ⁱ , I ⁱ ), where G^i +1 = G ⁱ , Mⁱ⁺¹ = M ⁱ  - {m}, I^i +1 = I ⁱ  ∩ (G^i +1 × Mⁱ⁺¹), i ∈ {0, 1, . . . , n}, n is the number of attributes in the formal context K, i represents the number of node attenuations in the concept tree, i = 0 correspond to the original form context K = (G, M, I).

Definition 14. In formal context K ⁱ  = (G ⁱ , M ⁱ , I ⁱ ), the node coupling after the ith deletion of nodes in the concept tree is expressed as ξ m K i . The node with the minimum coupling is represented as m = { m ∈ M | ξ m ′ K i = min { ξ m K i } }(9)

3.2.1 Deletion rule of leaf node

During the attenuation of the concept tree, the leaf node is deleted when the leaf node with the minimum coupling in the concept tree. The deletion rule of leaf node is discussed below.

Definition 15. In formal context K = (G, M, I),∀m ∈ M, its concept tree is Tree = r (T₁, T₂, T₃, . . . , T _n ). Par (m) represent the parent node of the node m in path <ω _i , m>, where ω_i = (r, . . . , m, . . . , l). At this point, ω_i = (r, . . . Par (m) , m, . . . , l).

Property 2. In formal context K = (G, M, I), ( A , B ) ∈ B ( K ) and m _i  ∈ M. If m _i  ∈ B, then Par (m _i ) ⊂ B.

Proof: For g _i , g _j  ∈ G, if g _i  ∈ A, then Par (g _i ) ⊂ A, Therefore, the same reason can be obtained. For ( A , B ) ∈ B ( K ) and m _i  ∈ M satisfy m _i  ∈ B, then Par (m _i ) ⊂ B.

According to definition 7 and definition 15, leaf node is located at the end of a path. As can be seen from the relationship between leaf nodes and other nodes in the concept tree, the leaf node is only associated with its parent node and do not affect other concept structures. Therefore, the Property 3 can be obtained.

Property 3. In formal context K = (G, M, I), ∀m ∈ M, its concept tree is Tree = r (T₁, T₂, T₃, . . . , T _n ). The deletion of leaf node m is represented by deleting the leaf node m, its immediate predecessor.

Proof: For the leaf node m, # d (m) =0, the path of node m is expressed as ω _i  = (r, . . . , Par (m) , m). After node m is deleted, the path is updated to ω _i  = (r, . . . , Par (m)). By Par (m) → m, therefore, the deletion of leaf node m is represented by deleting the leaf node m, its immediate predecessor.

When the deleted node is a leaf node, the concept tree update principle is such as Algorithm 1.

Algorithm 1. Update of concept tree when leaf node is deleted.

Input: K = (G, M, I), Tree = r (T₁, T₂, T₃, . . . , T _n ), m ∈ M and # d (m) =0

Output: Tree ^″′

Step 1: Delete the leaf node m and its immediate predecessor, get the concept tree Tree^″′, perform Step 2;

Step 2: The formal context is updated from K = (G, M, I) to K ⁱ  = (G ⁱ , M ⁱ , I ⁱ ), perform Step 3;

Step 3: Output Tree^″′.

In the implementation of the above algorithm, the complexity of the algorithm is O(n _att ), where n _att is the size of the set M.

In the current formal context, when the node with the minimum coupling in the concept tree is the leaf node, the leaf node is deleted. First delete the node and its immediate predecessor, then update the formal context, and finally get the updated concept tree.

For the original concept tree shown in Fig. 1(b), calculate the coupling of the nodes in the concept. Let λ₁ = 0.75, λ₂ = 0.85, the coupling of the resulting nodes are ξ a K = 1 . 64 , ξ b K = 1 . 81 , ξ c K = 0 . 14 , ξ d K = 0 . 52 and ξ e K = 2 . 55 . Therefore, the node coupling is minimal for the node c. According to the Definition 7, node c is a leaf node. Therefore, the node are deleted according to the Algorithm 1 and the concept tree is updated. As shown in Fig. 3(a), mark the leaf node c and its immediate predecessor in red, and underline the node in the concept tree. The concept tree after the node c is deleted is shown in Fig. 3(b), with a formal context updated from K = (G, M, I) to K¹ = (G¹, M¹, I¹).

OPEN IN VIEWER

Fig. 3

Process of updating concept tree after deleting leaf node c.

During the attenuation of the concept tree, the branch node is deleted when the leaf node with the minimum coupling in the concept tree. The deletion rule of branch node is discussed below.

Definition 16. In formal context K = (G, M, I), its concept tree is Tree = r (T₁, T₂, T₃, . . . , T _n ). Let m _j as the node connected after r. There is M _p  = {m _j  ∈ M|r → m _j }. Then M _p is the set of nodes connected after r.

Definition 17. In formal context K = (G, M, I), its concept tree is Tree = r (T₁, T₂, T₃, . . . , T _n ). For M p m j ⊆ M , there is M p m j = { m j ∈ M p | r = m j } . Then M p m j is the set of nodes connected after the root node m _j .

Definition 18. In formal context K = (G, M, I), its concept tree is Tree = r (T₁, T₂, T₃, . . . , T _n ), where M _p  ⊆ M, m ∈ M _p . If m ∈ M p p = m , then the tree with the root node m _p is the association sub trees fornode m.

Property 4. In formal context K = (G, M, I), ∀m ∈ M, is the sub trees for node m is Tree = m (T_m1, T_m2, T_m3, . . . , T _mn ). Let all concept in Tree is B ( K T ) , where ( A , B ) ∈ B ( K T ) . Delete the branch node m and its immediate predecessor and sub trees, then get Tree′. The growth of sub trees in Tree′ is as follows:

If g _{K ⁱ}  (B - m) = A, then the sub tree in Tree where the original concept (A, B) is located will be deleted. There will be a new sub tree of the new concept (g _{K ⁱ}  (B - m){B - m}) after node Par (m).

Proof: 1) The concept before node m deletion is (A, B), and the concept after node deletion is (g _{K ⁱ}  (B - m){B - m}). After deleting node m, the concept is updated. The original concept is deleted, and a new concept is generated. That is, the sub tree in the concept tree where the original concept is located is removed.

2) The concept before node m deletion is (A, B), and the concept after node deletion is (g _{K ⁱ}  (A - m){A - m}). After deleting node m, if there is no sub tree of the same concept in the original concept tree, the sub tree of the concept is grown directly.

When the deleted node is a branch node, the concept tree update principle is such as Algorithm 2.

Algorithm 2. Update of concept tree when leaf node is deleted.

Input: K = (G, M, I), Tree = r (T₁, T₂, T₃, . . . , T _n ), m ∈ M and # d (m) ≠0

Output: Tree^″′

Step 1: Calculating M _p in Tree, perform Step 2;

Step 2: In concept tree Tree, m _j  ∈ M _p , if m ∉ M p m j , then delete the node m _j and its immediate predecessor and sub trees, then get the association sub tree Tree′, perform Step 3;

Step 3: Delete the node m and its immediate predecessor and sub trees in concept tree Tree′, then get the concept tree Tree″, perform Step 4;

Step 4: Calculate all the concepts B ( K T ″ ) in the Tree″, where ( A , B ) ∈ B ( K T ″ ) , perform Step 5;

Step 5: In concept tree Tree′, if g _{K T′}  (B - m) = A, then the sub tree where the original concept (A, B) is located will be deleted. There will be a new sub tree of the new concept (g _{K ^T′}  (B - m){B - m}) after node Par (m), perform Step 6; else, perform Step 6 directly;

Step 6: In concept tree Tree′, if g _{K T′}  (B - m) ≠ A, there will be a new sub tree of the new concept (g _{K ^T′}  (B - m){B - m}) after node Par (m) directly, then get the concept tree Tree^″′, perform Step 7;

Step 7: The formal context is updated from K = (G, M, I) to K ⁱ  = (G ⁱ , M ⁱ , I ⁱ ), perform Step 8;

Step 8: Output Tree^″′.

In the implementation of the above algorithm, the complexity of the algorithm is O(n _att ), where n _att is the size of the set M.

In the formal context, branch node is deleted when the node with the minimum coupling in the concept tree is a branch node. First analyze the correlation between the node and other nodes in the concept tree, clarify the association sub tree of the node. Then determine the growth of the other nodes after the node is deleted at the node, and update the formal context. Finally get the updated concept tree.

Figure 4(a) is the concept tree after the node is first deleted during the attenuation process. The formal context updates to K¹ = (G¹, M¹, I¹), where M¹ = {a, b, d, e}. Calculate the coupling of the nodes are ξ a K 1 = 1 . 64 , ξ b K 1 = 1 . 33 , ξ d K 1 = 0 . 52 and ξ e K 1 = 1 . 70 . Therefore, the node coupling is minimal for the node d. According to the Definition 7, node d is a leaf node. Therefore, the node are deleted according to the Algorithm 1 and the updated concept tree is shown in Fig. 4(b). The formal context is update to K² = (G², M², I²), where M² = {a, b, e}. The node of the minimum coupling is the branch node b. As shown in Fig. 4(c), mark the branch node b and its immediate predecessor in green, and underline the node in the concept tree. Delete the node b according to Algorithm 2. The growth of the sub tree in the concept tree after deleting the node b is shown in Fig. 4(d), the gray node and its immediate predecessor represent the same part of the original concept and the new concept in the now concept tree. Delete the same concept shown in gray in Fig. 4(d), and get the updated concept tree as shown in Fig. 4(e). The formal context is update from K² = (G², M², I²) to K³ = (G³, M³, I³).

OPEN IN VIEWER

Fig. 4

Process of updating concept tree with deleting node d and node b. The leaf nodes and its immediate predecessor are marked in red, the branch nodes and its immediate predecessor in green, and the same parts of current concept tree in gray.