Attenuation characteristics analysis of concept tree

Abstract

Dynamic Concept-cognitive Learning (CCL) is an active field in cognitive computing. Decremented concept cognition is an important topic in dynamic CCL. As an important feature of the dynamic CCL, attenuation characteristics have been successfully visualized by concept lattice and three-dimensional attribute topology. However, the existing attenuation characteristic analysis method has limitations to the description of interaction between attributes. A method of attenuation characteristics analysis of concept tree is proposed. The coupling between nodes is discussed from the concept tree, the nodes are decremented according to the coupling relationship, and the corresponding node attenuation rules are discussed according to the different types of nodes. In this paper, the news attention is the research object. The experimental results show that the attenuation characteristic analysis scheme of the concept tree is feasible. In the process of attenuation, the effect of attribute attenuation on the concept structure can be clearly demonstrated. At the same time, the concept tree can better visualize the process of decremented news attention than the concept lattice and three-dimensional attribute topology.

Keywords

Concept-cognitive learning formal concept analysis concept tree decremented concept cognition attenuation characteristics

1 Introduction

Cognitive computing is viewed as an emerging computing paradigm modeled on the human brain. As far as we know, it has been investigated by simulating human thought processes, such as learning [5, 28, 29], activation [18], and memory [19]. As time progresses, cognitive learning, as a useful mathematical tool for the realization of cognitive computing, has absorbed many effective methods of psychology, information theory, and mathematics [13]. Concepts are regarded as the most fundamental units of human cognition and play a major role in cognitive tasks such as learning, memorizing and reasoning [25]. Role of human cognition in contextual information retrieval was discussed by Tian, Du, Hu, and Li [23]. A concept is defined as a cognitive unit to describe a real-world concrete entity and a perceived world abstract subject [9, 30]. CCL, as a new cross-research field, is induced by rough analysis [4], rule acquisition [24], knowledge discovery [8], attribute reduction [6], and granular computing [1].

FCA presented by Wille [14 –16] is a discipline that studies the hierarchical structures induced by a binary relation between the set of objects and attributes. As the core of a mathematical theory of FCA, all formal concepts or the formal concept lattice can be used to represent relationships between objects and attributes or conceptual hierarchies, which are inherent in data [2]. FCA starts with a formal context, more general, called information systems, which are a tabular form of an object-attribute value relationship [11]. Binary relation between the objects and attribute pairs in FCA is analogous to the way that the object categories are formed in human brain [17]. Ch. Aswani Kumar [3] have made use of FCA, a mathematical framework for data and knowledge processing, to represent memories and to perform some of the cognitive functions of human brain.

Since the data actually obtained is often dynamic, dynamic conceptual learning is closer to the actual cognitive learning and data processing. Dynamic concept-cognitive learning is an active field in cognitive computing [7, 12]. Decremented conceptual cognition is currently the main research direction. Zhang et al. [10] studies and puts forward the asymptotic algorithm of subtracting some attributes on the basis of the original concept lattice, and quickly gets the new concept lattice after the selected attribute is deleted. Ma et al. [26] gives a method to obtain the concept lattice of the new background quickly and effectively on the basis of the original concept lattice when reducing multiple attributes on the basis of literature.

Dynamic concept learning is one of the active issues in the field of concept-cognitive learning. According to the dynamic direction, it can be divided into incremental concept learning and decrement concept learning [22]. Decrement concept learning focuses on the attenuation characteristics of concept structure in dynamic data. On the basis of dynamic concept learning, this paper proposes tree attenuation in the formal context of decrement form from the perspective of concept tree. With the exploration of the field of concept cognitive computing application, the research of attenuation analysis has been paid more and more attention. At present, there is a research on the attenuation characteristics of the three-dimensional attribute topology [20, 21]. In this paper, combined with the subtraction problem in concept tree and CCL, a method of attenuation characteristic analysis of concept tree is proposed. The CCL process is more intuitive by analyzing the changes of nodes and tree structure sits through the correlation between nodes in the concept tree. The attenuation characteristic of concept tree is applied to the visual analysis of news attention reduction, which clearly explains the process of news attention change. At the same time, compared with the attenuation of the concept tree and the concept lattice, the concept tree can have a clearer and more intuitive embodiment of attenuation.

2 Basic notions

Attribute topology (AT) and attribute partial ordering graph belong to the framework of formal structure analysis, which is a graph description for formal context. Formal context, which acts as the research object and data representation, is an important basic aspect in FCA. Here are a few notions about formal context.

Definition 1. [29] A formal context can be expressed as K = (G, M, I), where G represents a set of all objects in formal context, M represents a set of all the attributes in the formal context, I ⊆ G × M represents the relationship between objects and attributes, and G × M represents the Cartesian product of G and M.

Definition 2. [27] In context K = (G, M, I), A ⊆ G, B ⊆ M, $f (A) = {m \in M | for all g \in A, (g, m) \in I}$ (1) $g (B) = {g \in G | for all m \in B, (g, m) \in I}$ (2)

If f (A) = B and g (B) = A, then the pair (A, B) is a formal concept. Set A is the extension of (A, B) and set B is the intension of (A, B). The set of all concepts in K = (G, M, I) is denoted by $B (G, M, I)$ or $B (K)$ .

From the perspective of graph theory, AT shows a weighted graph that depicts the relationships between attribute pairs. Thus the storage method of the graph can be borrowed. This section carries out a description of adjacency matrix of AT from the perspective of inclusive relationship of attribute pairs.

Definition 3. In formal context K = (G, M, I), the adjacency matrix representation of an AT can be expressed as AT = (V, Edge), where V = G is the vertex set of the AT, Edge is the set of attribute topological edges called the adjacency matrix of the AT, Edge represents the following:

$\begin{matrix} Edge (m_{i}, m_{j}) = \\ {\begin{matrix} Ø & g (m_{i}) \cap g (m_{j}) = g (m_{i}) \neq g (m_{j}) \\ g (m_{i}) \cap g (m_{j}) & others \end{matrix} \end{matrix}$ (3)

Here are a few notions about concept tree.

Definition 4. In formal context K = (G, M, I), the concept tree is expressed as $Tree = r (T_{1}, T_{2}, T_{3}, . . ., T_{n})$ (4) where n ⩾ 0, r is the root of concept tree Tree = r (T₁, T₂, T₃, . . . , T_n), T₁, T₂, T₃, . . . , T_n are disjoint subsets, T₁, T₂, T₃, . . . , T_n are called the sub tree of the root node r of concept tree Tree.

Definition 5. In formal context K = (G, M, I), the concept tree is expressed as $Tree = m (T_{m 1}, T_{m 2}, T_{m 3}, . . ., T_{mn})$ (5) where m is the root of concept tree Tree = m (T_m1, T_m2, T_m3, . . . , T_mn).

For a formal context as Table 1, its AT is shown in Fig. 1(a), its concept tree is shown in Fig. 1(b), and its concept lattice is shown in Fig. 1(c).

Table 1

An example of formal context

	a	b	c	d	e
1	×				×
2	×	×		×	×
3		×	×		×
4	×	×		×

Fig. 1

AT, concept tree and concept lattice of Table 1.

AT mainly describes the relationship between each attributes in the two-dimensional space, but the description of the strength of attributes has limitations. Three-dimensional AT extends the original definition of traditional AT, and mainly describes the strength characteristics in attenuation. Concept tree structure originates from but not limited to the structure of AT. AT, three-dimensional AT and concept tree are all visual tools to represent formal context. Concept tree is more intuitive than other concept trees in concept-cognitive learning. In this paper, concept tree is chosen as a visual form to analyze the attenuation characteristics of concept tree.

3 Attenuation characteristics analysis of concept tree

The attenuation characteristics analysis of concept tree is shown in Fig. 2. First, we discuss the node reduction of the concept tree, and by calculating the node coupling, select the node with the minimum coupling in the concept tree for deletion. Second, the attenuation rule of the concept tree is discussed, and for the abridged rule considered from the two categories of leaf node and branch node. Finally, attenuation characteristics analysis of concept tree is analyzed, and the attenuation order of nodes in the concept tree and the interaction between the attributes in the attenuation process are obtained.

Fig. 2

Flowchart for attenuation characteristics analysis of concept tree.

3.1 Node deletion 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.

3.1.2 Node attenuation of concept tree

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}) \in 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) \in 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) \in 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) = \frac{# (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 $\begin{matrix} ξ_{m}^{K} = \sum_{j = 1}^{X} ψ (m | < ω_{i}, m >^{Leaf}) (λ_{1}^{L < ω_{i}, m >^{Leaf}}) + \\ \sum_{j = 1}^{Y} ψ (m | < ω_{i}, m >^{Branch}) (λ_{2}^{L < ω_{i}, m >^{Branch}}) \end{matrix}$ (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 \in M | ξ_{m^{'}}^{K^{i}} = min {ξ_{m}^{K^{i}}}}$ (9)

3.2 Attenuation rules of concept tree

The type of node in the concept tree is different, and the structure of the concept tree after removing the attribute node is also different. Therefore, this section starts with two categories, leaf node and branch node, and analyzes the different types of node coupling and changes in the concept tree structure after deleting the node. For ease of description, the top-to-bottom connection path between two property nodes in the concept tree is represented by “→”.

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) \in 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) \in 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¹).

Fig. 3

Process of updating concept tree after deleting leaf node c.

3.2.2 Deletion rule of branch node

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}} \subseteq M$ , there is $M_{p}^{m_{j}} = {m_{j} \in 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 \in 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) \in 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).

If g_{K
ⁱ} (B - m) ≠ A, there will be a new sub tree of the new concept (g_{K
ⁱ} (B - m){B - m}) after node Par (m) directly.

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 \notin 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) \in 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³).

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.

3.3 Attenuation rules of concept tree

Based on the above discussion on the coupling of nodes and the deletion rules of different types of nodes, the overall flow chart of the algorithm is shown in the Fig. 5: First, by calculating the node coupling, select the node with the minimum coupling in the concept tree for deletion. Second, for the deletion rule from the leaf node and branch node two categories to consider. Finally, the attenuation order of the nodes in the concept tree and the interaction among the attributes in the attenuation process are obtained.

Fig. 5

The overall flow chart of the node deletion algorithm.

For the nodes in the concept tree, analyze the coupling of the nodes, obtain the node with the minimum coupling, and delete it until the concept tree is empty.

For the concept tree shown in Fig. 6(a), the formal context after node attenuation is updated to K³ = (G³, M³, I³), where M³ = {a, e}. As shown in Fig. 6(a), the coupling of the nodes are $ξ_{a}^{K^{1}} = 1.13$ , $ξ_{e}^{K^{1}} = 0.85$ , the node coupling is minimal for the node e. According to the Definition 7, node e is a leaf node. As shown in Fig. 6(a), mark the branch node e and its immediate predecessor in green, and underline the node in the concept tree. Delete the node e according to Algorithm 2. The growth of the sub tree in the concept tree after deleting the node e is shown in Fig. 6(b), 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. 6(b), and get the updated concept tree as shown in Fig. 6(c). The formal context is update from K³ = (G³, M³, I³) to K⁴ = (G⁴, M⁴, I⁴). Figure 6(d) is the concept tree corresponding to the formal context K⁴ = (G⁴, M⁴, I⁴), where M⁴ = {a}. There is only one node a in the formal context K⁴ = (G⁴, M⁴, I⁴), therefore the node a is deleted. Node a is deleted as shown in Fig. 6(e).

Fig. 6

Process of updating concept tree with deleting node e and node a.

By analyzing the attenuation characteristics of the concept tree corresponding to the formal context K = (G, M, I) shown in Table 1, it is concluded that the attenuation order of each node is c, d, b, e, a in turn. The process of attenuation of nodes is clearly described by analyzing the attenuation characteristics of the concept tree.

4 Experiment

In this section, we will use concept tree and lattice to visualize the change of actual clicks of various news in different news media platform, that is, the change of attention of news. On the one hand, it will verify the feasibility of the concept tree attenuation algorithm, on the other hand, we introduce concept tree into the field of news data analysis based on big data, and provide new ideas for the follow-up research on news data processing.

First, we recorded a total of 9,531 news about large scale temperature drop reported from eight news media platforms, including People’s Daily, Sina Microblog, and Renren between December 13 and 19, 2019, and divided them into eight categories, which are expressed as a, b, c, d, e, f, g, h. Table 2 is the result of sorting out news on December 13, 2019, where each row represents the clicks of each new on this media platform and the meaning of each attribute in the attribute column is shown in Table 3. Then, in order to convert it into a binary formal context that can be used in this paper, we do the following: Calculate the average clicks of each news in the eight news platforms, the original clicks greater than or equal to the average clicks of the news are expressed as 1, and the rest are expressed as 0, and the formal context shown in Table 4 is obtained. Second, the decremented characteristic of the formal context is analyzed by decremented algorithm of concept tree, and the decremented process is visualized by the structural change of concept tree. At the same time, the decremented order of news and its corresponding concept tree are obtained.

Table 2
Formal context of attention of news on December 13.2019

a b c d e f g h

Sohu News 343,600 919,600 1,853,400 456,300 1,563,200 1,236,400 363,500 233,600

Baidu News 756,300 452,100 1,732,400 965,400 956,200 913,600 596,300 564,400

Sina Microblog 456,500 654,500 1,035,600 853,600 842,600 1,059,900 635,800 662,500

Renren 655,200 762,300 893,700 459,800 953,600 789,600 663,300 352,200

Phoenix News 223,900 531,200 763,700 567,800 1,613,900 1,013,900 451,200 411,200

Tencent News 95,500 101,200 1,234,700 102,400 736,900 689,800 463,100 369,600

People’s Daily 486,300 123,400 1,567,900 853,600 752,600 986,300 336,900 358,700

Xinhua News Agency 569,600 145,700 863,400 867,800 723,500 894,100 259,800 225,900

	a	b	c	d	e	f	g	h
Sohu News	343,600	919,600	1,853,400	456,300	1,563,200	1,236,400	363,500	233,600
Baidu News	756,300	452,100	1,732,400	965,400	956,200	913,600	596,300	564,400
Sina Microblog	456,500	654,500	1,035,600	853,600	842,600	1,059,900	635,800	662,500
Renren	655,200	762,300	893,700	459,800	953,600	789,600	663,300	352,200
Phoenix News	223,900	531,200	763,700	567,800	1,613,900	1,013,900	451,200	411,200
Tencent News	95,500	101,200	1,234,700	102,400	736,900	689,800	463,100	369,600
People’s Daily	486,300	123,400	1,567,900	853,600	752,600	986,300	336,900	358,700
Xinhua News Agency	569,600	145,700	863,400	867,800	723,500	894,100	259,800	225,900

Table 3

Attributes information

Attributes	Most concise descriptions
a	Birth rate
b	Sales of cotton clothes
c	A wide range of cold air
d	Widespread snowfall
e	Traffic jam
f	Traffic accident
g	Medical disputes
h	Inflation of prices

Table 4

Binary formal context after processing

	a	b	c	d	e	f	g	h
1	0	1	1	0	1	1	0	0
2	0	0	1	1	0	1	1	1
3	0	0	0	0	0	1	1	1
4	0	0	0	0	0	0	1	0
5	0	0	0	0	1	1	0	1
6	1	1	1	1	0	0	0	0
7	0	1	1	1	0	0	0	0
8	0	0	0	1	0	0	0	0

Based on the above formal context, the attenuation analysis of attributes is carried out. In this experiment, attenuation analysis in days. According to the definition 12, the coupling of nodes are calculated, In this experiment, λ₁ = 0.75, λ₂ = 0.85. Assuming that one attribute is deleted every day, Table 5 shows the coupling degree of each attribute over time. Table 5 is marked in parentheses with the minimum coupling node in the concept tree corresponding to the current formal context.

Table 5

Coupling of nodes at different times

	a	b	c	d	e	f	g	h
K	0.08(a)	0.83	1.92	0.99	0.54	2.55	0.85	0.90
K1	–	0.81	1.92	0.99	0.54(e)	2.55	0.85	0.90
K2	–	0.81(b)	1.89	1.05	–	1.70	0.85	0.90
K3	–	–	1.59	0.99	–	1.70	0.85(g)	0.90
K4	–	–	1.59	0.96	–	1.70	–	0.54(h)
K5	–	–	1.53	0.96	–	0.85(f)	–	–
K6	–	–	1.17	0.85(d)	–	–	–	–
K7	–	–	0.75(c)	–	–	–	–	–

As can be seen from Table 5, the order in which nodes are deleted is a, e, b, g, h, f, d, c. In the original concept tree, the coupling of node a is the minimum and is deleted next time. After node a is deleted, the coupling of node e is minimal in the concept tree, so node e is deleted the next time. After node e is deleted, the coupling of node b is minimal in the concept tree, so node b is deleted the next time. After node b is deleted, the coupling of node g is minimal in the concept tree, so node g is deleted the next time. After node g is deleted, the coupling of node h is minimal in the concept tree, so node h is deleted the next time. After node h is deleted, the coupling of node f is minimal in the concept tree, so node f is deleted the next time. After node f is deleted, the coupling of node d is minimal in the concept tree, so node d is deleted the next time. After node d is deleted, the coupling of node c is minimal in the concept tree, so node c is deleted the next time. Node c is deleted and an empty concept tree is obtained. The process of the node deletion in turn is shown in Fig. 7(a)–7(i).

The concept tree corresponding to the original formal context is shown in Fig. 8(a), the concept lattice corresponding to the original formal context is shown in Fig. 8(b). The concept trees after deleting node a and node e in turn are shown in Fig 8(c) and Fig. 8(e), the concept lattices after deleting node a and node e in turn are shown in Fig 8(d) and Fig. 8(f). By comparing concept tree with concept lattice, we can see that the position of node a can be clearly reflected in the concept tree. When deleting node a, we can clearly see the impact of deleting node a on the concept structure. When node e is deleted, the impact on other nodes and the whole concept structure is also clearly reflected. However, the deletion of nodes is not obvious in concept lattice. The attenuation analysis method of concept tree is compared with the concept lattice method, and it is concluded that the method proposed in this manuscript can better visualize the attenuation process. Concept tree is better than concept lattice in visualizing the process of news attention reduction.

Fig. 7

The process of the node deletion in turn in concept tree Concept.

Fig. 8

The process of the node a and node e deletion in turn in concept tree and concept lattice.

For sake of verifying the feasibility of decremented algorithm of concept tree in news attention analysis, we recorded actual clicks of eight kinds of news on eight news media platforms in a week and recorded the average clicks in Table 6. In addition, we verified the consistency between the attenuation characteristics based on AT and the trend of data changes based on actual clicks through comparative experiments. Figure 9 shows the comparison between the mean of actual clicks values and the calculated theoretical values in different days. What needs to be explained is that, the values in Fig. 9 are 1/100000 of the actual clicks values to make a more intuitive comparison between the two types of data. The actual value represents the attenuation order. For example, a is deleted first, “1” represents the theoretical value of a, e is then deleted, then “2” represents the theoretical valueof e.

Table 6

Average actual clicks of different news on eight news media platforms at different time periods

	a	b	c	d	e	f	g	h
Dec. 13,2019	448,363	461,250	1,243,100	640,838	1,017,813	947,950	471,238	397,263
Dec. 14,2019	239,005	447,931	927,337	563,920	731,806	693,509	330,971	279,338
Dec. 15,2019	97,486	434,478	517,974	317,446	151,791	172,923	120,984	110,072
Dec. 16,2019	83,582	173,060	231,184	191,936	98,800	142,317	140,183	103,974
Dec. 17,2019	60,075	98,129	137,648	103,707	55,890	89,473	63,112	60,379
Dec. 18,2019	18,921	31,864	50,441	39,991	30,037	35,932	19,187	27,736
Dec. 19,2019	4,208	7,963	19,730	18,415	6,724	10,009	4,219	8,321

Fig. 9

The comparison between the actual clicks value and the calculated theoretical value.

As can be seen from Fig. 9, the two results echo each other and show about the same trend overall. In the actual news attention reduction process node a the lowest attention. In the theoretical value obtained from the analysis of the attenuation characteristics of the concept tree, it also shows the first decay. Due to the lack of individual differences, there are some deviations between the actual values and the results obtained by the attenuation characteristic analysis of concept tree, but the overall trend is basically consistent.

The attenuation analysis method of concept tree is compared with the original concept lattice method, and it is concluded that the method proposed in this manuscript can better visualize the attenuation process as the overall trend between the analysis results of attenuation characteristics of concept tree and the actual results of news attention reduction is basically the same. This paper still has one-sidedness to the results of the decremented news attention to the experiment, such as natural, environmental impact and other factors. There also need to combine more research subjects for validation. Therefore, the attenuation analysis of concept tree with large data volume will be one of the research directions in the future.

5 Conclusion

In this paper, we propose a decremented CCL method based on concept tree. The coupling among nodes is discussed from the concept tree, the nodes are decremented according to the coupling relationship, and the corresponding node attenuation rules are discussed according to different types of nodes. The influence of node attenuation on concept tree is explored through experiments. The attenuation analysis method of concept tree is compared with the concept lattice method, and it is concluded that the method proposed in this manuscript can better visualize the attenuation process. The attenuation of concept tree is clearer than that of concept lattice. At the same time, taking the reduction of news attention as the research object, when analyzing the attribute attenuation, the expression form of concept tree makes the attenuation of news attention more visible.

The attenuation characteristics of concept tree are applied to the visual analysis of news attention reduction. The analysis results of attenuation characteristics of concept tree are basically consistent with the overall trend of the actual results of news attention reduction. It can be seen that the attenuation characteristic analysis of the concept tree is basically in line with the laws of human cognition, easy to understand, operable and visual. Through the attenuation characteristics analysis of the concept tree, the process of decremented concept learning is described intuitively and clearly, which provides a way of thinking and method for the reduction concept learning analysis. In the next study, we consider adding the stability study of CCL based on the concept tree, and further explore the stability of the concept tree.

References

Fan

B.J.

, Tsang

E.C.C.

, Xu

W.H.

, et al., Attribute-oriented cognitive concept learning strategy: a multi-level method, International Journal of Machine Learning and Cybernetics 10(9) (2019), 2421–2437.

Kumar

C.A.

, Dias

M.S.

and Vieira

N.J.

, Knowledge reduction in formal contexts using non-negative matrix factorization, Mathematics and Computers in Simulation 109 (2014), 46–63.

Kumar

C.A.

, Ishwarya

M.S.

and Loo

C.K.

, Formal concept analysis approach to cognitive functionalities of bidirectional associative memory, Biologically Inspired Cognitive Architectures 12 (2015), 20–33.

Wang

C.Z.

, Huang

, Shao

M.W.

, et al., Fuzzy rough set-based attribute reduction using distance measures, Knowledge-Based Systems 164(15) (2019), 205–212.

H. CH.

, Hou

; Fan

J.F.

, et al., The unordered time series fuzzy clustering algorithm based on the adaptive incremental learning, Journal of Intelligent & Fuzzy Systems 38 (2020), 3783–3791.

Chen

, Mi

, Xie

and Lin

, A fast attribute reduction method for large formal decision contexts, International Journal of Approximate Reasoning 106 (2019), 1–17.

J.H.

, Mi

Y.L.

and Liu

W.Q.

, Incremental cognition of concepts: Theories and methods, Chinese Journal of Computers 42(9) (2019), 1–19.

J.Y.

, Wu

W.Z.

and Xu

Y.T.

, Attribute reduction in inconsistent formal decision contexts based on congruence relations, International Journal of Machine Learning and Cybernetics 8(1) (2017), 81–94.

K.W.

, Shao

M.W.

and Wu

W.Z.

, A data reduction method informal fuzzy contexts, International Journal of Machine Learning and Cybernetics 8(4) (2017), 1145–1155.

10.

Zhang

, Zhang

H.L.

, Yin

L.H.

and Han

D.J.

, Theory and Algorithms of Attribute Decrement for Concept Lattice, Journal of Computer Research and Development 50(2) (2013), 248–259.

11.

Valtchev

, Missaoui

and Lebrun

, A partition-based approach towards constructing Galois (concept) lattices, Discrete Mathematics 256(3) (2002), 801–829.

12.

Godin

, Missaoui

and Alaoui

, Incremental concept formation algorithms based on Galois (concept) lattices, Computational Intelligence 11(2) (1999), 246–267.

13.

Shivhare

, Cherukuri

A.K.

and Li

, Establishment of Cognitive Relations Based on Cognitive Informatics, Cognitive Computation 9 (2017), 721–729.

14.

Wille

, Lattices in data analysis: how to draw them with a computer, Algorithms and Order. Springer Netherlands, 33 (1989).

15.

Wille

, Line diagrams of hierarchical concept systems, Knowledge Organization 11(2) (1984), 77–86.

16.

Wille

, Restructuring the lattice theory: an approach based on hierarchies of concepts, International Conference on Formal Concept Analysis, (2009), 314–339.

17.

Rumbell

, Self Organisation and Hierarchical Concept Representation in Networks of Spiking Neurons, 2013.

18.

Nisheeth

and Edward

, A simple model of recognition and recall memory, In, Neural Information Processing Systems 30 (2017), 292–300.

19.

Shivhare

and Cherukuri

A.K.

, Three-way conceptual approach for cognitive memory functionalities, International Journal of Machine Learning and Cybernetics 8(1) (2016), 21–34.

20.

Zhang

, Liu

M.Q.

and Rong

, Analysis of Attenuation Characteristics of Three-Dimensional Attribute Topology, Journal of Chinese Computer Systems 40(10) (2019), 2113–2118.

21.

Zhang

, Li

H.H.

, Liu

M.Q.

, et al., Incremental Concept-cognitive Learning Based on Attribute Topology, International Journal of Approximate Reasoning 118 (2020), 173–189.

22.

Zhang

, Liu

M.Q.

and Liu

W.Y.

, The Causality Research between Syndrome Elements by Attribute Topology, Computational & Mathematical Methods in Medicine 2018(2018), 1–12.

23.

Tian

, Du

, Hu

, et al., Modeling individual cognitive structure in contextual information retrieval, Computers and Mathematics with Applications 57(6) (2009), 1048–1056.

24.

W.Z.

, Qian

Y.H.

, Li

T.J.

and Gu

S.M.

, On rule acquisition in incomplete multi-scale decision Tables, Information Sciences 378 (2017), 282–302.

25.

X.L.

, Wei

and She

T.H.

, L-fuzzy concept analysis for three-way decisions: basic definitions and fuzzy inference mechanisms, International Journal of Machine Learning and Cybernetics 9(11) (2018), 1857–1867.

26.

and Ma

W.S.

, Construction of Multi-Attributes Decrement for Concept Lattice, Journal of Software 26(12) (2015), 3162–3173.

27.

, Zeng

Z.W.

and Chi

C.Y.

, Formal Concept and Its New Development, BeiJing: Science press, 2011.

28.

Lin

Y.J.

, Hu

Q.H.

, Liu

I.H.

, et al., Streaming Feature Selection for Multi-label Learning Based on Fuzzy Mutual Information, IEEE Transactions on Fuzzy Systems 25(6) (2017), 1491–1507.

29.

Y.L.

, Li

J.H.

, Liu

W.Q.

and Lin

, Research on Granular Concept Cognitive Learning System Under Map Reduce Framework, Acta Electronica Sinica 46(2) (2018), 289–297.

30.

Wang

Y.X.

, On concept algebra for computing with words (cww), International Journal of Semantic Computing 4(3) (2010), 331–356.

	a	b	c	d	e	f	g	h
1	0	1	1	0	1	1	0	0
2	0	0	1	1	0	1	1	1
3	0	0	0	0	0	1	1	1
4	0	0	0	0	0	0	1	0
5	0	0	0	0	1	1	0	1
6	1	1	1	1	0	0	0	0
7	0	1	1	1	0	0	0	0
8	0	0	0	1	0	0	0	0

	a	b	c	d	e	f	g	h
1	0	1	1	0	1	1	0	0
2	0	0	1	1	0	1	1	1
3	0	0	0	0	0	1	1	1
4	0	0	0	0	0	0	1	0
5	0	0	0	0	1	1	0	1
6	1	1	1	1	0	0	0	0
7	0	1	1	1	0	0	0	0
8	0	0	0	1	0	0	0	0

	a	b	c	d	e	f	g	h
1	0	1	1	0	1	1	0	0
2	0	0	1	1	0	1	1	1
3	0	0	0	0	0	1	1	1
4	0	0	0	0	0	0	1	0
5	0	0	0	0	1	1	0	1
6	1	1	1	1	0	0	0	0
7	0	1	1	1	0	0	0	0
8	0	0	0	1	0	0	0	0