Detailed explanation of candidate elimination algorithm implemented in Python

The candidate elimination algorithm is a machine learning algorithm based on inductive reasoning that is used to learn a concept from given training data. Its purpose is to summarize all instances in the training data into the most general concept description, that is, the process of "concept learning".

The basic idea of ​​the candidate elimination algorithm is to initialize a most specific concept description and a most general concept description, and then gradually modify them until the most general concept is finally obtained. Description, the concept sought.

Specifically, the steps of the algorithm are as follows:

1. Initialize the most special concept description and the most general concept description:

The most special concept description S0: Initialize all attribute values ​​​​to "?", indicating uncertainty;

The most general concept description G0: Initialize all attributes The values ​​are all initialized to "∅", which means they do not contain any attribute values.

2. For each training instance, perform the following processing:

①If the instance is a positive example (belongs to the desired concept), update The most special concept description S and the most general concept description G:

For each attribute in S, if the attribute value in the instance is different from the corresponding attribute value in S, then S Change the attribute value in G to "?";

For each attribute in G, if the attribute value in the instance is different from the corresponding attribute value in G, then the attribute value in G will be changed. The attribute value is changed to the attribute value in the instance.

② If the instance is a counterexample (does not belong to the required concept), only update the most general concept description G:

For G in For each attribute, if the attribute value in the instance is the same as the corresponding attribute value in G, then change the attribute value in G to "?".

The most general concept description finally obtained is the desired concept.

The following uses a simple example to illustrate the application process of the candidate elimination algorithm. Suppose we want to learn a concept from the following 5 training examples:

According to the algorithm steps, we first initialize the most specific concept description and the most general concept description:

S0:

G0:

Then for each training For example, proceed as follows:

For example 1: it belongs to the required concept, so update S and G:

S1:

G1:

For instance 2: it belongs to the required concept, so update S and G:

##S2:

G2:

For instance 3: It does not belong to the required concept, so only G is updated:

S3:

G3:

For example 4: It does not belong to the required concept, so only G is updated:

##S4:

G4:

For instance 5: it belongs to the required concept, so update S and G ：

##S5:

G5:

The most general concept description finally obtained is:

##

That is, " aquatic".

The following is the Python code to implement the candidate elimination algorithm:

import numpy as np

def candidate_elimination(examples):
    # 初始化最特殊概念描述和最一般概念描述
    S = np.array(['?' for _ in range(len(examples[0]) - 1)])
    G = np.array(['∅' for _ in range(len(examples[0]) - 1)])
    # 对于每个训练实例，进行如下处理
    for i, example in enumerate(examples):
        x, y = example[:-1], example[-1]
        if y == '是':  # 正例
            # 更新最特殊概念描述S和最一般概念描述G
            for j in range(len(x)):
                if S[j] != '?' and S[j] != x[j]:
                    S[j] = '?'
                G[j] = x[j] if S[j] == '?' else S[j]
        else:  # 反例
            # 只更新最一般概念描述G
            for j in range(len(x)):
                if S[j] != '?' and S[j] != x[j]:
                    G[j] = S[j]
        # 打印每次迭代的结果
        print(f'第{i+1}次迭代：S={S}, G={G}')
    # 最终得到的最具一般性的概念描述即为所求概念
    concept = G if G[0] != '∅' else S
    return concept

The above is the basic idea and application examples of the candidate elimination algorithm. I hope it can help everyone understand and learn the candidate elimination algorithm. Helps.

The above is the detailed content of Detailed explanation of candidate elimination algorithm implemented in Python. For more information, please follow other related articles on the PHP Chinese website!