4Concept learning based on dynamic fuzzy sets

This chapter is divided into seven sections. Section 4.1 introduces the relationship between dynamic fuzzy sets and concept learning. In Section 4.2, we present the representation model of dynamic fuzzy concepts. In Section 4.3, we introduce the dynamic fuzzy (DF) concept learning space model. Section 4.4 presents the concept learning model based on DF lattice. In Section 4.5, we provide the concept learning model based on dynamic fuzzy decision tree (DFDT). In Section 4.6, we introduce the application examples and analysis. The summary of this chapter is in Section 4.7.

4.1Relationship between dynamic fuzzy sets and concept learning

Concept learning is one of the main methods in the field of machine learning for generalizing and abstracting general rules or patterns from massive data sets. The key problem in concept learning is to give a set of samples, determine whether each sample belongs to a certain concept of membership, and automatically infer the general definition of the concept. In other words, the problem is to approximate the objective function of the concept from the sample set and effectively predict the concept labels of unknown concept categories in test samples to provide intelligent decision support.

Each concept can be thought of as a collection of objects or events. Categorization is the process of selecting a subset from a larger set, such as selecting birds from a collection of animals or defining the objective function from a larger set. Traditional concept learning is based on Boolean functions. However, the concept of human contact in the real world has the character of dynamic fuzzy universality. To truly reveal the laws of human understanding, scientists need to develop an actual theoretical model that provides a better approximation of the real-life objective function. Dynamic fuzzy sets are a very promising tool, so this chapter studies concept learning using dynamic fuzzy sets.

4.2Representation model of dynamic fuzzy concepts

Dynamic fuzzy concepts are defined in an instance space. The concept or function to be learned is called the target concept, denoted as C. When learning the objective function, it is necessary to provide a set of training examples. Each sample is an instance (x↼,x⇀) in(X↼,X⇀) and its target concept value the sample is a positive example. When c((x↼,x⇀))≤(λ↼,λ⇀),, the sample is a counter example. (λ↼,λ⇀) is a given dynamic fuzzy threshold. The two-tuple <(x↼,x⇀),c((x↼,x⇀))> contains the target concept value <(x↼,x⇀), of instance (x↼,x⇀).

Tab. 4.1: Examples of dynamic fuzzy data background.

Definition 4.1 A dynamic fuzzy information system can be formalized as a dynamic fuzzy dyadic group ((0↼,0⇀),(A↼,A⇀)), where(0↼,0⇀) is a set of nonempty finite dynamic fuzzy instances (objects) and (A↼,A⇀) is a set of finite dynamic fuzzy attributes with nonempty attributes. There is a mapping f|(α↼,α⇀):(0↼,0⇀)→(V↼,V⇀)(α↼,α⇀), where ∀(α↼,α⇀)∈(A↼,A⇀),(V↼,V⇀)(α↼,α⇀) is the set of values of (α↼,α⇀).

Definition 4.2 It is known that the dynamic fuzzy form background is B:(X, Y, I), where X is the set of dynamic fuzzy objects X={(x↼1,x⇀1),(x↼2,x⇀2),...,(x↼R,x⇀R)}, Y is the identification set of dynamic fuzzy attributes Y={(y↼1,y⇀1),(y↼2,y⇀2)},..., (y↼R,y⇀R)},I=ϕ(X×Y) is defined as a dynamic fuzzy (DF) membership function on X × Y and ((x↼,x⇀),(y↼,y⇀))∈I has the membership value μ((x↼,x⇀),(y↼,y⇀)). This value satisfies μ((x↼,x⇀),(y↼,y⇀))→[(0↼,0⇀),(1↼,1⇀)] where (x↼,x⇀)∈(X↼,X⇀),(y↼,y⇀)∈(Y↼,Y⇀)). The DF membership function can be a general dynamic fuzzy function.

There are many dynamic fuzzy background data in real life. Table 4.1 presents a dynamic fuzzy form of background data in table frame form.

Definition 4.3 In the dynamic fuzzy background, the truncation operation is defined as follows: for each (y↼,y⇀)∈D, define (λ↼(y↼,y⇀),λ⇀(y↼,y⇀)) and(0↼,0⇀)≤(λ↼(y↼,y⇀),)(λ⇀(y↼,y⇀))≤(1↼,1⇀). The truncation of the dynamic fuzzy background is (λ↼,λ⇀)K((X↼,X⇀),(Y↼,Y⇀),(I↼(λ↼,λ⇀),I(λ↼.λ⇀))), where(X↼,X⇀),(Y↼,Y⇀) is the same as in Definition 4.2, namely:

(I←(A←,A⇀),I←(A←,A⇀))((x←,x⇀),(y←,y⇀)) ={I((x←,x⇀),(y←,y⇀))   if I((x←,x⇀),(y←,y⇀))≥(λ←(y←t,y⇀t),λ←(λ←t,y⇀t))                (4.1)           (0←,0⇀)             if I((x←,x⇀),(y←,y⇀))≥(λ←(y←t,y⇀t),λ←(λ←t,y⇀t))

Definition 4.4 In the dynamic fuzzy background B, the dynamic fuzzy concept (c↼i,c⇀i)=((X↼i,X⇀i),(Y↼i,Y⇀i)) is defined. (X↼i,X⇀i) and(Y↼i,Y⇀i) define the two maps f and g as follows:

∀(X←i,X⇀i)⊆X:f((x←i,x⇀i))={(y←,y⇀)|∀(x←i,x⇀i)                                                             ∈(X←i,X⇀i),I(λ←,λ⇀)((x←,x⇀),(y←,y⇀))}

∀(Y←i,Y⇀i)⊆Y:g((y←j,y⇀i))={(y←,y⇀)|∀(y←,y⇀)                                                           ∈(Y←i,Y⇀i),I(λ←,λ⇀)((x←,x⇀),(y←,y⇀))}

I(λ↼,λ⇀)((x↼,x⇀),(y↼,y⇀)) is read as the object (x↼,x⇀) that has property (y↼,y⇀). Functions f and g are called the DFGalois connection between the power set of X and the power set of Y.

Definition 4.5 If the two-tuple (c↼i,c⇀i)=((X↼i,X⇀i),(Y↼i,Y⇀i)) satisfies (X↼i,X⇀i)=g((Y↼i,Y⇀i)) and(Y↼i,Y⇀i)=f((X↼i,X⇀i)), then this two-tuple is called a dynamic fuzzy concept of B, where (X↼i,X⇀i) and (Y↼i,Y⇀i) are called the extension and con notation of dynamic fuzzy concept (c↼i,c⇀i), respectively. The set of all dynamic fuzzy concepts of B is denoted by DFCB(B). The internal structure of DFCB(B) is generated by generalization and specialization.

In dynamic fuzzy concept learning theory, the connotation of a concept refers to the common attribute set of all objects. The extension of a dynamic fuzzy concept refers to the largest dynamic fuzzy object set that can be determined by the connotation of a dynamic fuzzy concept. A dynamic fuzzy concept is a complete dynamic fuzzy sequence. A dynamic fuzzy concept that contains all objects is called a complete dynamic fuzzy concept. A concept that can contain all dynamic fuzzy attributes is called a dynamic fuzzy empty concept.

4.3DF concept learning space model

In this section, we discuss the conceptual learning model and its learning algorithm based on dynamic fuzzy set (DFS) theory, which is based on the classical structure theory.

4.3.1Order model of DF concept learning

With the increasing development of the machine learning domain, we study concept learning from different perspectives and have different model structures. Mitchell proposed a good framework for the study of concept learning theory, and its related theoretical algorithms include the FIND-S algorithm [1], list elimination algorithm, and candidate elimination algorithm [2].

The definition of dynamic fuzzy concept in an instance space (X↼,X⇀): given a set of samples (S↼,S⇀)⊆(X↼,X⇀) and whether each sample (x↼,x⇀)⊆(X↼,X⇀) belongs to a concept, analysis tools can be used to summarize the definition of the target concept. This is the training process of DF concept learning. This process can also be viewed as a search process over a particular space, which is the entire space implied by the conceptual assumption. This ultimately leads to the highest degree of fit between the hypothesis space of the search and the sample space. Under normal circumstances, the use of hypothetical space is a common structure of the natural order to conduct a quick search.

4.3.1.1Sequence structure of DF hypothesis space

According to the “general to special” partial order structure, processing can occur in a limited hypothesis space.

Definition 4.6 For functions hi, hj on (X↼,X⇀), we say that hi is equal to or greater than hj if and only if

(∀(x←,x⇀)∈(X←,X⇀))[(hi((x←,x⇀))=(α←,α⇀))→(hj((x←,x⇀))=(β←,β⇀))].

That is, (α↼,α⇀)≤(β↼,β⇀) is recorded as hi ≥ hj, where (x↼,x⇀) is given as an example. We denote that hi is strictly greater than hj as hi > hj.

Consider the scenario depicted in Fig. 4.1: How do hp, hq, and hr relate to the relationship defined by ≥g? By definition, hq is more general than hp, and so the instances that satisfied hp also satisfied hq, but there is no such relationship between hp and hr. The reason is that, although the subsets of instances satisfying the two hypotheses have intersections, neither instance subset exactly contains the other. Note here that the definitions ≥g, >g are independent of the target concept and are relevant only to instances that satisfy these two hypotheses, regardless of the classification of instances according to the target concept. The relation ≥g defines a partial order structure on the hypothesis space H.

Fig. 4.1: DF concept learning space mapping diagram.

4.3.1.2FIND-S algorithm and candidate elimination algorithm

Definition 4.7 Overlay: When a hypothesis can correctly divide a positive example, the positive case is said to be covered by the hypothesis.

FIND-S algorithm steps:

(1)Initialize h as the most specific assumption in H.

(2)For each positive case (x↼,x⇀) and for each attribute constraint (a↼i,a⇀i) of h, if (x↼,x⇀) satisfies(a↼i,a⇀i), nothing is done; otherwise, replace (a↼i,a⇀i) in h with the next most general constraint that satisfied by (x↼,x⇀).

(3)Output hypothesis h.

Algorithm features: If the correct target concept is contained in H and the training data are correct, the FIND-S algorithm can guarantee that the output is the most specific hypothesis in H that is consistent with the positive examples. However, the convergence of the learning process is poor, and convergence to the correct objective function cannot be guaranteed. In addition, the robustness to noise is weak, and, for a number of special assumptions, the algorithm becomes powerless.

To overcome the deficiencies of the FIND-S algorithm, we extend it using the following definition.

Definition 4.8 A hypothesis h is consistent with the set D of training samples if and only if there is some h((x↼,x⇀))=c((x↼,x⇀)) for each sample<(x↼,x⇀),c((x↼,x⇀))> in D.

DFConsistent(h,D)≡(∀<(x←,x⇀),c((x←,x⇀))>εD)h(x←,x⇀)=c((x←,x⇀))

A sample (x↼,x⇀) satisfies hypothesis h at h((x↼,x⇀))≥(λ↼,λ⇀),, regardless of whether (x↼,x⇀) is a positive or negative example of the DF target concept. However, whether this sample is consistent with hypothesis h is related to the concept of the target.

Definition 4.9 The general boundary G of the hypothesis space and the training data D is the set of maximal general members in D that correspond to D in H.

G={g∈H|Consistent(g,D)∧(¬∃g′∈H)[(g′>gg)∧Consistent(g′,D)]}

Definition 4.10 The special boundary S about the hypothesis space H and the training example D is the set of very large special members that coincide with D in H

S≡{Consistent(s,D)∧(¬∃s′∈H)[(s>sg′)∧Consistent(s′,D)]}

Theorem 4.1 Representation theorem for DF variant space: Let (X↼,X⇀) be an arbitrary set of instances and H be a set of dynamic fuzzy hypotheses on (X↼,X⇀). Let c :(X↼,X⇀)→[(0↼,0⇀),(1↼,1⇀)] be any of the target concepts defined on (X↼,X⇀) and let D be any training set {<(x↼,x⇀),c((x↼,x⇀))>}. For all (X↼,X⇀), there are some H, c, D, and well-defined S and G such that

VSH,D={h∈H|(∃s∈S)(∃g∈G)(g≥gh≥gs)}.

The candidate elimination algorithm proceeds as follows:

(1)Initialize the G-set to the maximum general assumption in H;

(2)The S-set is initialized to the extreme special assumption in H;

(3)For each training example d:

If d is a positive example, remove the hypotheses that are not consistent with d; for each hypothesis s in S that is not consistent with d, remove s from S and add all the minimal generalized h of s to S, where h is consistent with d and some member of G is more general than h; all such hypotheses are removed from S; this is more general than the other assumption in S.

If d is a counter example, all assumptions inconsistent with d are removed from S, g is assumed to be inconsistent with d in g, and g is removed from G. All the minimal specializations h of g are added to G, where h satisfies that h is consistent with d, and some member of S is more specialized than h. Remove all such hypotheses from G, which is more specialized than the other assumption in G.

Algorithm features: The algorithm will output a set of all hypotheses consistent with the training examples. The algorithm is biased and can be generalized to the training examples. As a set of general and special boundaries is formed, it is easy to compute the variational space formed by all the assumptions of the training examples in the entire partial order structure. If the training data are noisy, the two boundaries S and G converge to an empty variant space, so the robustness to noise is weak.

4.3.2DF concept learning calculation model

To quantitatively analyse learning algorithms and evaluate learning performance, DF concept learning also follows commonly used computational learning theory. We must consider how many training examples are needed to successfully learn the target concept under the given learning model, how many errors will occur before learning the target concept, and so on. Two definitions of such problems are given below.

Definition 4.11 DF concept sample complexity: The number of training examples required for the learning model to converge successfully to a hypothesis.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
3.12.151.154