4.4.5.1Examples of algorithms

For example, suppose that the dynamic fuzzy background after feature extraction is as presented in Tab. 4.2. According to BorderLayerDFCL algorithm, the dynamic fuzzy processing background is given in Tab. 4.3.

First, we calculate the threshold of the dynamic fuzzy attributes according to Tab. 4.2 and obtain the dynamic fuzzy processing background (Tab. 4.3) after reduction, which improves the precision of constructing the dynamic fuzzy concept lattice. Second, the dynamic fuzzy concept lattice is constructed according to the algorithm, as shown in Fig. 4.2.

For example, assume that the threshold $\left(\stackrel{\leftharpoonup }{\theta },\stackrel{\rightharpoonup }{\theta }\right)\text{of}\left(\stackrel{\leftharpoonup }{\alpha },\stackrel{\rightharpoonup }{\alpha }\right)\text{is}\left(0.\stackrel{\leftharpoonup }{7},\stackrel{\rightharpoonup }{0}.7\right)$ and the threshold $\left(\stackrel{\leftharpoonup }{\gamma },\stackrel{\rightharpoonup }{\gamma }\right)\text{of}\left(\stackrel{\leftharpoonup }{\delta },\stackrel{\rightharpoonup }{\delta }\right)\text{is}\left(0.\stackrel{\leftharpoonup }{3},\stackrel{\rightharpoonup }{0}.3\right).$ Then, the frequent nodes in the dynamic fuzzy concept lattice are ({12345}, {d1d2d7}), ({2345}, {d1d2d3d4d6}), ({78}, {d1d2d4d6}), ({8}, {d1d2d3d4d6}) <. The dynamic fuzzy support degree is $\left(0.\overleftarrow{7},0.\overrightarrow{7}\right)$ and the dynamic fuzzy confidence degree is $\left(0.\overleftarrow{9}5,0.\overrightarrow{9}5\right).$ The dynamic fuzzy candidate double tuples are $<\left(\left\{12345\right\},\left\{d_1{d}_2{d}_7\right\}\right),\left(\left\{2345\right\},\left\{d_1{d}_2{d}_7{d}_8\right\}\right)>$ and $<\left(\left\{78\right\},\left\{d_1{d}_2{d}_4{d}_6\right\}\right),\left(\left\{8\right\},\left\{d_1{d}_2{d}_3{d}_4{d}_6\right\}\right)>.$ The dynamic fuzzy association rules can then be extracted. According to $d_i=\left({\stackrel{\leftharpoonup }{y}}_i,{\stackrel{\rightharpoonup }{y}}_i\right)i=1,2,\mathrm{...9},$ the dynamic fuzzy association rules listed in Tab. 4.4 are obtained.

Tab. 4.2: Dynamic fuzzy form backgrounds.

Tab. 4.3: Dynamic fuzzy processing background.

Tab. 4.4: Generated partial DF rules.

4.4.5.2Experimental comparison

The following experiments compare the run times of DFCL_BorderLayer and DFCL_Layer algorithm with those of several algorithms with good performance, including Godin’s algorithm, Bordat’s algorithm, and Norris’ algorithm. The test platform configuration used an Intel 2.79 GHz processor with 512 MB memory. The experiment used randomly generated data with a total of 100 attributes.

It can be seen from Fig. 4.3 that the performance of DFCL_Layer and DFCL_BorderLayer increases with an increase in the data size. This verifies the validity of the proposed method.

4.5.2.1DF attribute selection metric

1) Information gain standard

The key problem in constructing a DF concept tree algorithm is how to select the best classification attributes. The choice is usually based on “information gain”, which measures the ability of a given set of attributes.

Given the DF target concept training set S, the entropy in the classical Boolean type is defined as

$\text{Entropy}\left(S\right)\equiv -p_{\oplus }{\log }_2{p}_{\oplus }-p_{\oplus }{\log }_2{p}_{\oplus }.\left(4.30\right)$

This can be written in the following form:

$\text{Entropy}\left(S\right)={\displaystyle \sum _{i=1}^c-p_i{\log }_2{p}_i,\left(4.31\right)}$

where pi represents the ratio of the number of samples labelled as i in sample set S to the total number of samples in S; c is the total number of labelled samples.

$\text{Gain}\left(S,A\right)\equiv \text{Entropy}{\displaystyle \sum _{v\in Values\left(A\right)}\frac{\left|S_v\right|}{\left|S\right|}\mathrm{Entropy}\left(S_v\right)},\left(4.32\right)$

where Values(A) is a possible set of values for attribute A and Sv is a subset of the values v of attribute A in S.

Because the dynamic fuzzy attribute is a nonclassical data value, the relevant parameters in the definition of information entropy should be adjusted. We consider two options for this, and choose one of them to achieve.

The first scheme finds the DF membership in the DF concept sample by setting a dynamic fuzzy 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)<\left(\stackrel{\leftharpoonup }{1},\stackrel{\rightharpoonup }{1}\right)\right).p_{\oplus }$ is the ratio of positive cases of DF membership degree in S that are greater than the threshold $\left(\stackrel{\leftharpoonup }{\delta },\stackrel{\rightharpoonup }{\delta }\right).p_{\oplus }$ is the ratio of counter-cases of DF membership degree in S that are smaller than the threshold $\left(\stackrel{\leftharpoonup }{\delta },\stackrel{\rightharpoonup }{\delta }\right).$ The other does not change.

The second scheme takes the training sample S that generates the DF concept, and obtains the sum of the DF memberships of all samples in this description. This process is repeated for the membership of each description in the intersection of the DF concept and the positive and negative examples. p⊕ is the ratio of the sum of positive cases of DF membership degree in S and DF membership degree in the DF concept in the sum of the two classes. p⊕ is the ratio of the sum of counter-cases of DF membership degree in S and DF membership degree in the DF concept in the sum of the two classes. The other does not change.

The higher the information gain of the DF attribute, the better the partitioning ability. Therefore, the information gain is often applied to the candidate attribute set to select the best classification attributes.

2) Gini index standard

The Gini index standard is based on distance measurement. The distance refers to the ratio distribution distance of the concept class. Assuming there are m DF concept classes in the training sample set S, Gini(S) is defined as follows:

$Gini\left(S\right)=1.0-{\displaystyle \sum _{i=1}^m{p}_i^2,\left(4.33\right)}$

where pi is the probability of the i th class appearing in the training sample set. Assuming that S is divided into two classes S1 and S2, Gini(S) is

$\mathrm{Gini}\left(S\right)=\frac{n_1}{n}Gini\left(S_1\right)+\frac{n_2}{n}Gini\left(S_2\right).\left(4.34\right)$

The smaller the Gini index of the DF attribute, the better the partitioning ability of the sample set. The advantage of this method is that the Gini index ensures the attribute contain a lot of useful information; the disadvantage is that the attribute selection becomes worse as the number of concept categories increases.

3) Relief standard

Kira and Rendell proposed the Relief standard in 1992. The basic idea of the algorithm is to randomly extract an instance and measure the dependency between attributes by the distance between the instance and the attribute value of the neighbour instance. The algorithm defines an attribute evaluation value $W\left[\left(\stackrel{\leftharpoonup }{A},\stackrel{\rightharpoonup }{A}\right)\right]$ of the sample set S. The initial state is 0. We randomly select m instances from the sample set S. For each record $\left({\stackrel{\leftharpoonup }{x}}_{c_i},{\stackrel{\rightharpoonup }{x}}_{c_i}\right),$ select the same category $\left({\stackrel{\leftharpoonup }{x}}^{\text{'}}{}_{c_i},{\stackrel{\rightharpoonup }{x}}^{\text{'}}{}_{c_i}\right)$ and the closest different categories $\left({\stackrel{\leftharpoonup }{x}}^{"}{}_{c_j},{\stackrel{\rightharpoonup }{x}}^{"}{}_{c_j}\right).$ Check each attribute value $\left(\stackrel{\leftharpoonup }{A},\stackrel{\rightharpoonup }{A}\right).$ If the values of two instances in different classes are the same, add one value; otherwise, subtract one value. The formula is as follows:

$\begin{array}{l}W\left[\left(\overleftarrow{A},\stackrel{\rightharpoonup }{A}\right)\right]=W\left[\left(\overleftarrow{A},\stackrel{\rightharpoonup }{A}\right)\right]-diff\left(\left(\overleftarrow{A},\stackrel{\rightharpoonup }{A}\right),\left({\overleftarrow{x}}_{C_l},{\stackrel{\rightharpoonup }{x}}_{C_t}\right),\left({\overleftarrow{x}}_{C_l}^{\prime },{\stackrel{\rightharpoonup }{x}}_{C_l}^{\prime }\right)\right)\\ +diff\left(\left(\overleftarrow{A},\stackrel{\rightharpoonup }{A}\right),\left({\overleftarrow{x}}_{C_t},{\stackrel{\rightharpoonup }{x}}_{C_l}\right),\left({\overleftarrow{x}}_{C_j}^n,{\stackrel{\rightharpoonup }{x}}_{C_j}^{\prime \prime }\right)\right),\left(4.35\right)\end{array}$

where the attribute is a classification type, and the value of $diff\left(\left(\stackrel{\leftharpoonup }{A},\stackrel{\rightharpoonup }{A}\right),\left(\stackrel{\leftharpoonup }{I},\stackrel{\rightharpoonup }{I}\right)\right),$$\left({\stackrel{\leftharpoonup }{I}}_2,{\stackrel{\rightharpoonup }{I}}_2\right))$ is

$\begin{array}{l}diff\left(\left(\overleftarrow{A},\stackrel{\rightharpoonup }{A}\right),\left({\overleftarrow{I}}_1,{\stackrel{\rightharpoonup }{I}}_1\right),\left({\overleftarrow{I}}_2,{\stackrel{\rightharpoonup }{I}}_2\right)\right)=\\ \{\begin{array}{l}0\left|DFvalue\left(\left(\overleftarrow{A},\stackrel{\rightharpoonup }{A}\right),\left({\overleftarrow{I}}_1,{\stackrel{\rightharpoonup }{I}}_1\right)\right)-DFvalue\left(\left(\overleftarrow{A},\stackrel{\rightharpoonup }{A}\right),\left({\overleftarrow{I}}_2,{\stackrel{\rightharpoonup }{I}}_2\right)\right)\right|<\left(\overleftarrow{\epsilon },\stackrel{\rightharpoonup }{\epsilon }\right),\\ 1otherwise\end{array}\\ \left(4.36\right)\end{array}$

where $\left(\stackrel{\leftharpoonup }{\epsilon },\stackrel{\rightharpoonup }{\epsilon }\right)$ is the smaller positive dynamic fuzzy threshold that is divided into discrete attributes. The larger the value of $W\left[\left(\stackrel{\leftharpoonup }{A},\stackrel{\rightharpoonup }{A}\right)\right]$ between the attributes, the better the classification performance. We select the attributes that give the best classification.

Each of the three attribute selection strategies has its own characteristics. If the properties of the sample set S are very different, then the information gain or Gini criterion should be used. If there are dependencies among the attributes of the sample set S, the Relief criterion is the most appropriate.

4.5.2.2Discretization of DFD

The dynamic fuzzy concept tree generation algorithm selects the value of the best classification property to expand the branch. In general, there are several values for each branch. If the value of the property is continuous, then the input data should be discretized. Namely, we need to divide the numerical values in the data set into several sub-intervals. This process is called the discretization of numerical data [19]. According to differences in the classification information, discretization is divided into unsupervised discretization and supervised discretization. Unsupervised discretization may destroy the completeness of the information and the usefulness of the data in the learning process. Supervised discretization takes the class attribute information into account and has a high accuracy rate in the learning process. Commonly used discretization strategies include the split strategy, adaptive strategy, equal frequency interval strategy, and class information entropy division strategy [20].

Suppose the condition attribute set of the instance set is $\left(\stackrel{\leftharpoonup }{C},\stackrel{\rightharpoonup }{C}\right)=\left\{\left({\stackrel{\leftharpoonup }{A}}_1,{\stackrel{\rightharpoonup }{A}}_1\right)\right\},$$\left({\stackrel{\leftharpoonup }{A}}_2,{\stackrel{\rightharpoonup }{A}}_2\right),\mathrm{...},\left({\stackrel{\leftharpoonup }{A}}_n,{\stackrel{\rightharpoonup }{A}}_n\right)\}.$ The value range of attribute $\left({\stackrel{\leftharpoonup }{A}}_i,{\stackrel{\rightharpoonup }{A}}_i\right)\in \left(\stackrel{\leftharpoonup }{C},\stackrel{\rightharpoonup }{C}\right)\text{is}\left({\stackrel{\leftharpoonup }{V}}_{{\stackrel{\leftharpoonup }{A}}_i},{\stackrel{\rightharpoonup }{V}}_{{\stackrel{\leftharpoonup }{A}}_i}\right)$ and the discretization scheme for the single numeric attribute $\left({\stackrel{\leftharpoonup }{A}}_i,{\stackrel{\rightharpoonup }{A}}_i\right)$ is a partition $\left({\stackrel{\leftharpoonup }{\pi }}_i,{\stackrel{\rightharpoonup }{\pi }}_i\right)\text{of}\left({\stackrel{\leftharpoonup }{V}}_{{\stackrel{\leftharpoonup }{A}}_i},{\stackrel{\rightharpoonup }{V}}_{{\stackrel{\rightharpoonup }{A}}_i}\right).$

The instance set $\left({\stackrel{\leftharpoonup }{\pi }}_i,{\stackrel{\rightharpoonup }{\pi }}_i\right)$ after the attribute filter is recorded as $\left({\stackrel{\leftharpoonup }{U}}_N,{\stackrel{\rightharpoonup }{U}}_N\right).$$\left({\stackrel{\leftharpoonup }{A}}_i,{\stackrel{\rightharpoonup }{A}}_i\right)$ is any condition attribute of $\left({\stackrel{\leftharpoonup }{U}}_N,{\stackrel{\rightharpoonup }{U}}_N\right),$ and is of numeric type. The discretization of $\left({\stackrel{\leftharpoonup }{U}}_N,{\stackrel{\rightharpoonup }{U}}_N\right)$ is a multiple-attribute discretization.

Suppose that $\left({\stackrel{\leftharpoonup }{\pi }}_1,{\stackrel{\rightharpoonup }{\pi }}_1\right)=\left\{\left({\stackrel{\leftharpoonup }{\pi }}^1{}_1,{\stackrel{\rightharpoonup }{\pi }}^1{}_1\right),\left({\stackrel{\leftharpoonup }{\pi }}^1{}_2,{\stackrel{\rightharpoonup }{\pi }}^1{}_2\right),\mathrm{...},\left({\stackrel{\leftharpoonup }{\pi }}^1{}_n,{\stackrel{\rightharpoonup }{\pi }}^1{}_n\right)\right\}\mathrm{and}\left({\stackrel{\leftharpoonup }{\pi }}_2,{\stackrel{\rightharpoonup }{\pi }}_2\right)=$$\left\{\left({\stackrel{\leftharpoonup }{\pi }}^2{}_1,{\stackrel{\rightharpoonup }{\pi }}^2{}_1\right),\left({\stackrel{\leftharpoonup }{\pi }}^2{}_2,{\stackrel{\rightharpoonup }{\pi }}^2{}_2\right),\mathrm{...},\left({\stackrel{\leftharpoonup }{\pi }}^2{}_n,{\stackrel{\rightharpoonup }{\pi }}^2{}_n\right)\right\}$ are two discretization schemes of $\left({\stackrel{\leftharpoonup }{U}}_N,{\stackrel{\rightharpoonup }{U}}_N\right),$ where $\left({\stackrel{\leftharpoonup }{\pi }}^1{}_i,{\stackrel{\rightharpoonup }{\pi }}^1{}_i\right)$ is the discretization scheme of attribute $\left({\stackrel{\leftharpoonup }{\pi }}_i,{\stackrel{\rightharpoonup }{\pi }}_i\right),$ and $\left({\stackrel{\leftharpoonup }{\pi }}^2{}_j,{\stackrel{\rightharpoonup }{\pi }}^2{}_j\right)$ is the discretization scheme of attribute $\left({\stackrel{\leftharpoonup }{A}}_i,\stackrel{\rightharpoonup }{A}\right)\text{in}\left({\stackrel{\leftharpoonup }{\pi }}^2{}_j,{\stackrel{\rightharpoonup }{\pi }}^2{}_j\right).$

As ${\stackrel{\leftharpoonup }{\pi }}^1{}_i$ is a discretization scheme for attribute $\left({\stackrel{\leftharpoonup }{A}}_j,{\stackrel{\rightharpoonup }{A}}_j\right),$ the partial order relation in the discretization is defined as $\left({\stackrel{\leftharpoonup }{\pi }}_i,{\stackrel{\rightharpoonup }{\pi }}_i\right)\le \left({\stackrel{\leftharpoonup }{\pi }}_j,{\stackrel{\rightharpoonup }{\pi }}_j\right)$ if and only if each attribute $\left({\stackrel{\leftharpoonup }{A}}_k,{\stackrel{\rightharpoonup }{A}}_k\right)$ in the instance set $\left({\stackrel{\leftharpoonup }{U}}_N,{\stackrel{\rightharpoonup }{U}}_N\right)\text{satisfies}\left({\stackrel{\leftharpoonup }{A}}^i{}_k,{\stackrel{\rightharpoonup }{A}}^i{}_k\right)\le \left({\stackrel{\leftharpoonup }{A}}^j{}_k,{\stackrel{\rightharpoonup }{A}}^j{}_k\right),k=1,2,\mathrm{...},n,$ where $\left({\stackrel{\leftharpoonup }{\pi }}^i{}_k,{\stackrel{\leftharpoonup }{\pi }}^i{}_k\right)$ is the division of $\left({\stackrel{\leftharpoonup }{V}}_{{\stackrel{\leftharpoonup }{A}}_k},{\stackrel{\rightharpoonup }{v}}_{{\stackrel{\rightharpoonup }{A}}_k}\right)\text{in}\left({\stackrel{\leftharpoonup }{\pi }}_i,{\stackrel{\rightharpoonup }{\pi }}_i\right).\le$ defines the degree between the discretization scheme as a partial order relationship.

In the value of attribute $\left({\stackrel{\leftharpoonup }{A}}_k,{\stackrel{\rightharpoonup }{A}}_k\right)$ is divided into an interval. Then, the partition of attribute $\left({\stackrel{\leftharpoonup }{A}}_k,{\stackrel{\rightharpoonup }{A}}_k\right)\text{in}\left({\stackrel{\leftharpoonup }{\pi }}_j,{\stackrel{\rightharpoonup }{\pi }}_j\right)$ must belong to the same interval. Two or more adjacent segmentation intervals of the value of attribute $\left({\stackrel{\leftharpoonup }{A}}_k,{\stackrel{\rightharpoonup }{A}}_k\right)\text{in}\left({\stackrel{\leftharpoonup }{\pi }}_i,{\stackrel{\rightharpoonup }{\pi }}_i\right)$ are combined into one partition interval of the value of attribute $\left({\stackrel{\leftharpoonup }{A}}_k,{\stackrel{\rightharpoonup }{A}}_k\right)\text{in}\left({\stackrel{\leftharpoonup }{\pi }}_j,{\stackrel{\rightharpoonup }{\pi }}_j\right)$ Because $\left({\stackrel{\leftharpoonup }{\pi }}_i,{\stackrel{\rightharpoonup }{\pi }}_i\right)\le \left({\stackrel{\leftharpoonup }{\pi }}_j,{\stackrel{\rightharpoonup }{\pi }}_j\right),\left({\stackrel{\leftharpoonup }{\pi }}_i,{\stackrel{\rightharpoonup }{\pi }}_i\right)$ is said to be the refinement of $\left({\stackrel{\leftharpoonup }{\pi }}_j,{\stackrel{\rightharpoonup }{\pi }}_j\right).$