4.3.4.2Dynamic fuzzy linear discriminant analysis (DFLDA) dimensionality reduction model

DFLDA is based on LDA. The basic idea is to find some vectors that can best distinguish the classes in the DF concept space. That is, we seek to maximize the class-space metric and minimize the intra-class distance measure. The high-dimensional data can be classified into subspaces by mapping them into low-dimensional sub-spaces. Suppose that, given a dynamic fuzzy training set S, the total number of samples is N, the total number of concept classes is C, and the total number of samples in each category is $N_i,i=1,2,\mathrm{...},c,{\displaystyle \sum _{i=1}^c{N}_i=N.}$ The dynamic fuzzy dispersion matrix in the DF concept class is

$S_W=\frac{1}{N}{\displaystyle \sum _{i=1}^C{\displaystyle \sum _{j=1}^N\left(\left({\overleftarrow{x}}_{ij},{\stackrel{\rightharpoonup }{x}}_{ij}\right)-\overline{\left({\overleftarrow{x}}_i,{\stackrel{\rightharpoonup }{x}}_i\right)}\right){\left(\left({\overleftarrow{x}}_{ij},{\stackrel{\rightharpoonup }{x}}_{ij}\right)-\overline{\left({\overleftarrow{x}}_i,{\stackrel{\rightharpoonup }{x}}_i\right)}\right)}^T.\left(4.18\right)}}$

The inter-class dispersion matrix for the DF concept is

$S_B=\frac{1}{N}{\displaystyle \sum _{j=1}^C{N}_i\left(\overline{\left({\overleftarrow{x}}_i,{\stackrel{\rightharpoonup }{x}}_i\right)}-\overline{\left(\overleftarrow{x},\stackrel{\rightharpoonup }{x}\right)}\right){\left(\overline{\left({\overleftarrow{x}}_i,{\stackrel{\rightharpoonup }{x}}_i\right)}-\overline{\left(\overleftarrow{x},\stackrel{\rightharpoonup }{x}\right)}\right)}^T},\left(4.19\right)$

where $\overline{\left(\stackrel{\leftharpoonup }{x},\stackrel{\rightharpoonup }{x}\right)}$ is the dynamic fuzzy mean vector of all attributes, $\overline{\left({\stackrel{\leftharpoonup }{x}}_i,{\stackrel{\rightharpoonup }{x}}_i\right)}$ is the dynamic fuzzy mean vector of the i th attribute, and $\left({\stackrel{\leftharpoonup }{x}}_{ij},{\stackrel{\rightharpoonup }{x}}_{ij}\right)$ is the j th sample of the i th dynamic fuzzy attribute.

Therefore, according to Fisher’s linear discriminant method, get the discriminant function:

$J\left(W\right)=\frac{\left|W^T{S}_{B}W\right|}{\left|W^T{S}_{W}W\right|}.\left(4.20\right)$

If SW is a nonsingular matrix, then an orthogonal matrix can be obtained that maximizes the ratio of the matrix determinants of the interdisciplinary dispersion matrix to those of the intra-class dispersal distribution matrix:

$W_{opt}^{*}=\left[w_1,w_2,\dots ,w_p\right]=\underset{w}{\arg \max }\frac{\left|W^T{S}_{B}W\right|}{\left|W^T{S}_{W}W\right|},\left(4.21\right)$

where {wi = 1, 2, . . ., p} is the generalized eigenvector of (4.20), corresponding to the p largest maximum eigenvalues of (4.20), which is

$S_B{w}_i={\lambda }_i{S}_w{w}_i.\left(4.22\right)$

As the rank of the inter-class scatter matrix SB of the DF concept is less than or equal to C − 1 generalized nonzero eigenvalues. W∗ opt is the best projection transformation matrix.

According to the eigenvector corresponding to the largest eigenvalue (the number of elements in the eigenvector is the number of attributes), all the attributes in the eigenvectors with values above a certain threshold $\left(\stackrel{\leftharpoonup }{\delta },\stackrel{\rightharpoonup }{\delta }\right)\left(\left(\stackrel{\leftharpoonup }{0}.\stackrel{\rightharpoonup }{0}\right)<\left(\stackrel{\leftharpoonup }{\delta },\stackrel{\rightharpoonup }{\delta }\right)<\right)$$\left(\stackrel{\leftharpoonup }{1},\stackrel{\rightharpoonup }{1}\right))$ are selected as attributes of the new training samples.

4.4.1.1Batch algorithms

Batch processing algorithms to generate a concept lattice generally have two steps: First, the grid nodes are generated; second, the grid nodes are used to establish a direct precursor/direct successor relationship. According to the task order, there are two main generation methods, namely, the task partitioning model (as developed by Chein, Ganter and other algorithms) and the task cross-building model (such as Bordat’s algorithm).

The Chein algorithm [7] constructs the concept lattice from bottom to top. The algorithm iteratively generates a collection of all concepts starting with the most ubiquitous, such as the concept of an object. The algorithm starts at the L1 level and contains a set of pairs ({x}, f(x)) for all objects x in all object sets. It constructs a new set of pairs of Lk + 1 layers by combining any pair of Lk layers. The merging process considers the two pairs of intersection sets for the Lk layer and tests whether the intersection already exists, depending on the result. If the upper layer appears, it indicates that the upper layer is not completely correct and is marked as such, so that the end of this layer operation will be deleted. The algorithm is simple and clear, but the practical application will produce a large number of redundant pairs in the same layer and in lower layers. In the algorithm, the same concept will be generated at different times by different concepts. This is the main drawback of this algorithm. The algorithm itself does not generate a Hasse graph, but this layer-by-layer grid-node generation method is useful for identifying links between grid nodes.

In the Bordat algorithm [8], the concept lattice L is constructed from the topmost node. For each node, the child nodes are generated and the link between child nodes and parent node is completed. The process is then called recursively for the resulting child nodes. The basic idea of the algorithm is that if the current node is (O1, D1), where O is the object set and D is the attribute set, we find the attribute subset D2 = D such that D2 can maintain the complete binary property on O1. This is the largest expansion and constitutes the current node of the subnode’s content. The algorithm is also very simple, intuitive, and easy to run in parallel. The disadvantage is that the same node is generated multiple times. In practical applications, each node is duplicated to generate its parent node several times. However, this is one of the most effective algorithms.

The Ganter algorithm [9] uses the eigenvectors representing X sets to enumerate X sets of cells. The length of each vector is the cardinality of the attribute set. The corresponding bit is set to 1 if an attribute value is present in the vector, and to 0 otherwise. The feature vectors are sorted in lexicographic order. Given a vector X = {x1, x2, ..., x m}, it finds the next X vector. The way to do this is to set the property bit in order and test whether it is a complete pair. The algorithm is initialized with {0, 0, ..., 0}. The vectors produced in this way are ordered. The list is sorted according to the containing topology of the X set. The algorithm does not generate Hasse graphs.

In contrast to the other algorithms, the Nourine [10] algorithm generates a concept lattice using the concept of epitaxial complement as the basic operating units. The algorithm is divided into two parts. First, the extension set of all the individual attributes forms a base B, and the set of clusters generated in B is $F=\left\{{}_{\stackrel{U}{D\subset K}}|K\subset B\right\}.$ The purpose of this step is to generate F from the base as a lexical-order tree representation. Each path of the tree represents an element in F. Operations with the same prefix share the same partial path. The root is an empty set. The overlay of F is then calculated. The covering relation between two elements is defined in the algorithm, and the condition whereby the elements in the lexical-order tree satisfy the covering relation is derived to determine the corresponding algorithm. It has been shown that the algorithm is less complex than those of Bordat and Ganter et al.

4.4.1.2Incremental algorithms

The basic idea of increment algorithms is to present the object to be inserted and place all the concepts in the intersection of the lattice according to the results of different treatments. It is assumed that the first i objects in the formal context have generated subsets of the concept nodes and sublattices of the concept lattice. This step is repeated until the final cell structure is generated. Obviously, it is easy to apply this strategy to attributes, which can be generated incrementally based on attributes rather than objects. Typical algorithms include Godin’s algorithm [11], Capineto’s algorithm [12], and Ho’s algorithm [13]. The property-based incremental construction algorithm is similar to the basic idea of Godin’s algorithm. The difference is that the algorithm adds to the concept lattice one by one.

Given the concept lattice L corresponding to the background B: (X, Y, I) and the new object X∗, the concept lattice L∗ corresponding to the formal context B∗ = (X ∪{X∗}, Y, I) is given. There are three main problems in the process of generating the concept lattice: (1) generation of all new nodes, (2) avoiding the repetition of existing lattice nodes, and (3) updating the edges. Therefore, for each node in the original concept lattice, different types are defined according to the relation between them and the connotation description of the new object.

Definition 4.20 If a lattice node C satisfies Internt(C) ⊆ f({x∗}), C is called a replacement node. Obviously, if C is a replacement node, then C should be replaced by Extent(C) ⊆ {X∗}, Intent(C)) in L∗.

Definition 4.21 If the given node Ci = (Oi, Ai) satisfies the following: (1) the intersec tion of connotations (f({x∗}) between the concept node and new node is not equal to the connotation of any node in the lattice; (2) the intersection of connotations (f({x∗}) between the concept node and new node is also not equal to Intent(C)∩Cj(f({x∗}), where Cj is any node that satisfies Cj > C in L; then Ci is called an extended subgrid node.

Obviously, replaceable nodes cannot be generated with the same node because $D_i\cap f\left(\left\{x^{*}\right\}\right)=D_i.$ If a node in lattice L is neither a replacement node nor a generatable node, it is called an invariant node.

For any node C in L∗: If there is no node C′ in L satisfying Intent(C′) = Intent(C′), C is called a new node; otherwise, it is called an inheritance node. If C = is an extended ′ subgrid node, node Extent(C′), Internt(C′) ∪ {X∗}) is obviously a new node in L∗. This is called a newborn node generated by C′.

Theorem 4.4 Given the concept lattice L and the new object x∗, the node C∗ in L is a generating subgrid node if and only if (1) $\neg \left(Internt\left(c_1\right)\subseteq f\left\{X^{*}\right\}\right)and\left(2\right)\neg \left(\exists C_2\right)\in$BeforeC1IntentC2 = IntentC1, where Before(C1) denotes the set of all lattice nodes that are accessed before C1 and all the newborn lattices generated before C1. The order of access here is given by the L grid nodes in accordance with the meaning of small to large access to the order. This ensures that the C1 predecessor node is accessed first to satisfy the definition of generating the child nodes.

Theorem 4.5 If C1 is a subgrid node and its corresponding newborn node is Cnew, then L satisfies the concept of Intent(C2) ⊇ Intent(Cnew), and C2 must satisfy Intent(C2) ⊇ Intent(C1).

It can be seen from Theorem 4.5 that, for a new node, none of the old nodes can be its subnode except for its subgrid node.

Theorem 4.6 For two new nodes Cnew1 and Cnew2, if Intent(Cnew1) ⊂ Intent(Cnew2), then Cnew1 must be generated before Cnew2 and cannot become its subgrid node.

4.4.2.1Delamination of DF concept lattice

In the concept lattice of DF, the hierarchical structure of a concept is defined by attributes. Therefore, the hierarchical concept lattice is defined by the length of the attribute set. We now introduce the DF concept lattice.

Definition 4.22 In the concept lattice of DF, if the longest distance between the concept of $\left(\left(\stackrel{\leftharpoonup }{0},\stackrel{\rightharpoonup }{0}\right),\left(\stackrel{\leftharpoonup }{A},\stackrel{\rightharpoonup }{A}\right)\right)$ and the largest element in the lattice is N, then we say that DF concept $\left(\left(\stackrel{\leftharpoonup }{0}.\stackrel{\rightharpoonup }{0}\right),\left(\stackrel{\leftharpoonup }{A},\stackrel{\rightharpoonup }{A}\right)\right)$ is in the Nth layer of the DF concept lattice.

Definition 4.23 In the DF concept lattice, we assume that $\left(\left({\stackrel{\leftharpoonup }{0}}_i,{\stackrel{\rightharpoonup }{0}}_i\right),\left({\stackrel{\leftharpoonup }{A}}_i,{\stackrel{\rightharpoonup }{A}}_i\right)\right)\ge \left(\left({\stackrel{\leftharpoonup }{0}}_j,\right)\right)$$\stackrel{\rightharpoonup }{0}),\left({\stackrel{\leftharpoonup }{A}}_j,{\stackrel{\rightharpoonup }{A}}_j\right))$ and if the longest chain length of $\left(\left({\stackrel{\leftharpoonup }{0}}_i{\stackrel{\rightharpoonup }{0}}_i\right),\left({\stackrel{\leftharpoonup }{A}}_i,{\stackrel{\rightharpoonup }{A}}_i\right)\right)\text{to}\left(\left({\stackrel{\leftharpoonup }{o}}_j,{\stackrel{\rightharpoonup }{0}}_j\right)\right),$$\left(\left({\stackrel{\leftharpoonup }{A}}_i,{\stackrel{\rightharpoonup }{A}}_i\right)\right)\text{is}l\left(l\in Z^{+}\right),\text{then}\left(\left({\stackrel{\leftharpoonup }{0}}_i,{\stackrel{\rightharpoonup }{0}}_i\right),\left({\stackrel{\leftharpoonup }{A}}_i,{\stackrel{\rightharpoonup }{A}}_i\right)\right)$ is the l-layer ancestor of $\left(\left({\stackrel{\leftharpoonup }{0}}_j,{\stackrel{\rightharpoonup }{0}}_j\right)\right),$$\left({\stackrel{\leftharpoonup }{A}}_j,{\stackrel{\rightharpoonup }{A}}_j\right)).$

Obviously, there is no overlay between two nodes on the same layer and there is no connection line in the DF concept lattice. The high-level nodes at different layers are covered by at least one lower node.

Definition 4.24 If concepts $\left({\stackrel{\leftharpoonup }{c}}_i,{\stackrel{\rightharpoonup }{c}}_i\right)\text{and}\left({\stackrel{\leftharpoonup }{c}}_j,{\stackrel{\rightharpoonup }{c}}_j\right)\text{satisfy}\left({\stackrel{\leftharpoonup }{c}}_i,{\stackrel{\rightharpoonup }{c}}_i\right)\le \left({\stackrel{\leftharpoonup }{c}}_j,{\stackrel{\rightharpoonup }{c}}_j\right),$ then $\left({\stackrel{\leftharpoonup }{c}}_i,{\stackrel{\rightharpoonup }{c}}_i\right)$ is a subconcept of $\left({\stackrel{\leftharpoonup }{c}}_j,{\stackrel{\rightharpoonup }{c}}_j\right),\text{and}\left({\stackrel{\leftharpoonup }{c}}_j,{\stackrel{\rightharpoonup }{c}}_j\right)$ is a superconcept of $\left({\stackrel{\leftharpoonup }{c}}_j,{\stackrel{\rightharpoonup }{c}}_j\right).$

If there is no concept $\left({\stackrel{\leftharpoonup }{c}}_k,{\stackrel{\rightharpoonup }{c}}_k\right)$ in the concept lattice such that $\left({\stackrel{\leftharpoonup }{c}}_i,{\stackrel{\rightharpoonup }{c}}_i\right)\le$$\left({\stackrel{\leftharpoonup }{c}}_k,{\stackrel{\rightharpoonup }{c}}_k\right)\le \left({\stackrel{\leftharpoonup }{c}}_j,{\stackrel{\rightharpoonup }{c}}_j\right)$ holds, then we call $\left({\stackrel{\leftharpoonup }{c}}_j,{\stackrel{\rightharpoonup }{c}}_j\right)$ the parent node of $\left({\stackrel{\leftharpoonup }{c}}_i,{\stackrel{\rightharpoonup }{c}}_i\right)$ and $\left({\stackrel{\leftharpoonup }{c}}_i,{\stackrel{\rightharpoonup }{c}}_i\right)$ is the child node of $\left({\stackrel{\leftharpoonup }{c}}_j,{\stackrel{\rightharpoonup }{c}}_j\right)$ There is an edge between $\left({\stackrel{\leftharpoonup }{c}}_i,{\stackrel{\rightharpoonup }{c}}_i\right)$ and

Definition 4.25 Except for the minimum element, the DF concept lattice can be divided into $T_{\max }=\stackrel{\max }{\left(\stackrel{\leftharpoonup }{x},\stackrel{\rightharpoonup }{x}\right)}\in {\left(\stackrel{\leftharpoonup }{x},\stackrel{\rightharpoonup }{x}\right)}^{\left\{\left|\left(\stackrel{\leftharpoonup }{x},\stackrel{\rightharpoonup }{x}\right)\right|\right\}}$ layers, among which $\left|\left(\stackrel{\leftharpoonup }{x},\stackrel{\rightharpoonup }{x}\right)\right|$ is the number of attributes of the object.

4.4.2.2Algorithm for constructing the DF concept lattice layer by layer

Construction of the DF lattice algorithm from top to bottom (DFCL_Layer) is as follows:

All of the temporary children of the second layer are generated iteratively according to this algorithm.

Processing operations on temporary subnodes: The (N + 1)th temporary subgrid node is $\left(\left({\stackrel{\leftharpoonup }{0}}_{N+1,1},{\stackrel{\rightharpoonup }{0}}_{N+1,1}\right),\left({\stackrel{\leftharpoonup }{A}}_{N+1,1},{\stackrel{\rightharpoonup }{A}}_{N+1,1}\right)\right)\left(\left({\stackrel{\leftharpoonup }{0}}_{N+1,2},{\stackrel{\rightharpoonup }{0}}_{N+1,12}\right),\left({\stackrel{\leftharpoonup }{A}}_{N+1,2},\stackrel{\rightharpoonup }{A}{}_{N+1,2}\right)\right),$$\mathrm{...}\mathrm{...}\left(\left({\stackrel{\leftharpoonup }{o}}_{N+1,q},{\stackrel{\rightharpoonup }{o}}_{N+1,q}\right),\left({\stackrel{\leftharpoonup }{A}}_{N+1,q},{\stackrel{\rightharpoonup }{A}}_{N+1,q}\right)\right)$ Sort these according to the number of objects covered by the node, i.e. $\mathrm{...}\mathrm{...}|\left({\stackrel{\leftharpoonup }{o}}_{N+1,i},{\stackrel{\rightharpoonup }{o}}_{N+1,i}\right)\ge |\left({\stackrel{\leftharpoonup }{o}}_{N+1,i},{\stackrel{\rightharpoonup }{o}}_{N+1,i}\right)|\mathrm{...}\mathrm{...},$ where $1\le i,j\le q,and,i\ne j$ Finally, the neighbouring temporary sublattice nodes are examined in turn. If $\left({\stackrel{\leftharpoonup }{0}}_{N+1,i},{\stackrel{\rightharpoonup }{0}}_{N+1,i}\right)\supseteq \left({\stackrel{\leftharpoonup }{0}}_{N+1,j},{\stackrel{\rightharpoonup }{0}}_{N+1,j}\right),$ then delete the temporary subnode $<\left({\stackrel{\leftharpoonup }{0}}_{N+1,i},{\stackrel{\rightharpoonup }{0}}_{N+1,i}\right),\left({\stackrel{\leftharpoonup }{A}}_{N+1,i},{\stackrel{\rightharpoonup }{A}}_{N+1,i}\right)>$ and judge the sorted temporary subgrid nodes until all subgrid nodes of the (N + 1)th layer have been determined.

The algorithm is simple and clear and is fully dependent on the dynamic fuzzy processing background. The construction of a dynamic fuzzy concept lattice is faster than in other algorithms.

4.4.2.3A critical hierarchical construction algorithm for DF concept lattice

The DF concept lattice critical layer construction algorithm (DFCL_BorderLayer) is the first to find all critical concepts. According to a list of properties, the algorithm then constructs the DF concept lattice. The definition of the critical concept is realized by the intersection of the connotation and the union of the extension of the concept of DF. The algorithm is a bottom-up hierarchical construction algorithm.