Explication détaillée de l'algorithme d'élimination des candidats implémenté en Python

L'algorithme d'élimination des candidats est un algorithme d'apprentissage automatique basé sur un raisonnement inductif qui est utilisé pour apprendre un concept à partir de données d'entraînement données. Son objectif est de résumer toutes les instances des données de formation dans la description de concept la plus générale, c'est-à-dire le processus « d'apprentissage de concepts ».

L'idée de base de l'algorithme d'élimination des candidats est d'initialiser une description de concept la plus spécifique et une description de concept la plus générale, puis de les réviser progressivement jusqu'à obtenir finalement la description de concept la plus générale, qui est le concept souhaité.

Plus précisément, les étapes de l'algorithme sont les suivantes :

1. Initialiser la description de concept la plus spéciale et la description de concept la plus générale :

La description de concept la plus spéciale S0 : Initialiser toutes les valeurs d'attribut ​​​​à "?" , indiquant une incertitude ;

La description du concept la plus générale G0 : initialiser toutes les valeurs d'attribut à "∅", indiquant qu'elle ne contient aucune valeur d'attribut.

2. Pour chaque instance de formation, effectuez le traitement suivant :

① Si l'instance est un exemple positif (appartenant au concept souhaité), mettez à jour la description du concept la plus particulière S et la description du concept la plus générale G. :

Pour chaque attribut dans S, si la valeur de l'attribut dans l'instance est différente de la valeur de l'attribut correspondante dans S, changez la valeur de l'attribut dans S en "?";

Pour chaque attribut dans G, si l'instance Si la valeur d'attribut dans G est différente de la valeur d'attribut correspondante dans G, alors remplacez la valeur d'attribut dans G par la valeur d'attribut dans l'instance.

②Si l'instance est un contre-exemple (n'appartient pas au concept souhaité), mettez à jour uniquement la description du concept la plus générale G :

Pour chaque attribut dans G, si la valeur de l'attribut dans l'instance est la même que l'attribut correspondant dans G Si les valeurs sont les mêmes, remplacez la valeur de l'attribut dans G par "?".

La description de concept la plus générale finalement obtenue est le concept souhaité.

Ce qui suit utilise un exemple simple pour illustrer le processus d'application de l'algorithme d'élimination des candidats. Supposons que nous souhaitions apprendre un concept à partir des 5 exemples de formation suivants :

Selon les étapes de l'algorithme, nous initialisons d'abord la description du concept la plus spécifique et la description du concept la plus générale :

S0 :

G0 :

Puis pour chaque instance de formation, procédez comme suit :

Par exemple 1 : Il appartient au concept souhaité, donc mettez à jour S et G :

S1 :

G1 :

Par exemple 2 : il appartient au concept requis, donc mettez à jour S et G :

S2 :

G2 :

Par exemple 3 : il n'appartient pas au concept requis, donc seul G est mis à jour :

S3 :

G3 :

Par exemple 4 : il n'appartient pas au concept requis, donc seul G est mis à jour :

S4 :

G5 :

La description de concept la plus générale finalement obtenue est :

, c'est-à-dire "animaux aquatiques"".

Ce qui suit est le code Python pour implémenter l'algorithme d'élimination des candidats :

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

Ce qui précède sont les idées de base et les exemples d'application de l'algorithme d'élimination des candidats. J'espère qu'il sera utile à tout le monde de comprendre et d'apprendre l'élimination des candidats. algorithme.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!