English | 简体中文 | 繁體中文 | Русский язык | Français | Español | Português | Deutsch | 日本語 | 한국어 | Italiano | بالعربية
Principe de l'arbre de décision
L'arbre de décision est une structure en arbre où les attributs des échantillons sont utilisés comme nœuds et les valeurs des attributs comme branches.
Le nœud racine de l'arbre de décision est l'attribut ayant la plus grande quantité d'information dans tous les échantillons. Le nœud intermédiaire de l'arbre de décision est l'attribut ayant la plus grande quantité d'information dans le sous-ensemble d'échantillons du sous-arbre raciné par ce nœud. Les nœuds feuilles de l'arbre de décision sont les valeurs de catégories des échantillons. L'arbre de décision est une forme de représentation des connaissances, qui est une haute généralisation de tous les échantillons de données. L'arbre de décision peut reconnaître avec précision toutes les catégories des échantillons et identifier efficacement les catégories des nouveaux échantillons.
L'algorithme de l'arbre de décision ID3L'idée de base est :
Tout d'abord, trouver l'attribut le plus discriminant, diviser les exemples en plusieurs sous-ensembles, puis choisir l'attribut le plus discriminant pour le classement dans chaque sous-ensemble, jusqu'à ce que tous les sous-ensembles ne contiennent que des données du même type. En fin de compte, on obtient un arbre de décision.
Le travail de J.R. Quinlan consiste principalement à introduire le gain d'information de la théorie de l'information, qu'il appelle gain d'information (information gain), en tant que mesure de la capacité de discrimination de l'attribut, et à concevoir un algorithme récursif pour construire un arbre de décision.
Prenez un exemple pour mieux comprendre :
Pour le problème de classification du climat, l'attribut est :
Météo (A1) Les valeurs sont : ensoleillé, nuageux, pluie
Température (A2Les valeurs sont : froid, modéré, chaud
Humidité (A3) Valeur : haut, normal
Vent (A4) Valeur : avec vent, sans vent
Chaque exemple appartient à une catégorie différente, dans cet exemple, il n'y a que deux catégories,分别为P, N. Les exemples de la catégorie P et N sont respectivement appelés exemples positifs et exemples négatifs. Mettez ensemble des exemples positifs et négatifs connus pour obtenir le jeu de données d'entraînement.
par ID3L'algorithme obtient un arbre de décision qui classe correctement chaque exemple du jeu de données d'entraînement, comme dans l'image suivante.
Les feuilles de l'arbre de décision sont les noms de catégories, c'est-à-dire P ou N. Les autres nœuds sont constitués des attributs des exemples, chaque valeur différente de l'attribut correspond à une branche;
Pour classer un exemple, à partir de la racine de l'arbre, effectuez des tests en fonction des valeurs de l'attribut pour bifurquer vers les noeuds inférieurs, testez ce noeud, et continuez ainsi jusqu'aux noeuds feuilles, l'exemple est jugé appartenir à la catégorie marquée par le noeud feuille.
Actuellement, utilisons un graphique pour juger d'un exemple spécifique,
La description du climat un matin d'une certaine journée est :
Météo : nuageux
Température : froide
Humidité : normale
Vent : sans vent
Alors, à quelle catégorie de climat appartient-il ?63;-------------peut être déterminé à partir du graphique que le type de l'exemple est P.
ID3doit construire un arbre de décision tel que celui-ci à partir du jeu de données d'entraînement. En fait, il peut y avoir plusieurs arbres de décision qui peuvent classer correctement le jeu de données d'entraînement. L'ID de Quinlan3L'algorithme peut obtenir un arbre de décision avec le moins de nœuds.
ID3Algorithme :
1. Pour l'ensemble d'exemples actuel, calculez le gain d'information de chaque attribut;
2. Choisissez l'attribut Ak avec le plus grand gain d'information;
3. Réunissez les exemples qui prennent la même valeur pour l'attribut Ak dans le même sous-ensemble, le nombre de valeurs de Ak donne le nombre de sous-ensembles;
4. Pour les sous-ensembles contenant à la fois des exemples positifs et négatifs, appelez récursivement l'algorithme de construction d'arbre;
5. Si le sous-ensemble ne contient que des exemples positifs ou négatifs, marquez la branche correspondante avec P ou N et retournez à l'appel précédent.
En règle générale, lorsqu'il s'agit de la construction d'un arbre, il est souvent nécessaire d'utiliser la récursion.
Pour le problème de classification du climat, les calculs spécifiques sont les suivants:
1、 calcul de l'entropie de l'information: où S est l'ensemble des exemples, P(ui) est la probabilité d'apparition de la catégorie i:
|S| représente le nombre total d'exemples dans l'ensemble d'exemples S, |ui| représente le nombre d'exemples de la catégorie ui. Pour9exemples positifs et5exemples inversés :
P(u1)=9/14
P(u2)=5/14
H(S)=(9/14)=log(14/9)+(5/14)=log(14/5)=0.94bit
2、 calcul de l'information gain:
où A est l'attribut, Value(A) est l'ensemble de valeurs de l'attribut A, v est une valeur de l'attribut A, Sv est l'ensemble des exemples dans S où la valeur de A est v, | Sv | est le nombre d'exemples dans Sv.
avec l'attribut A1par exemple, selon l'équation de calcul de l'information gain, l'attribut A1l'information gain est
S=[9+,5-] //Il y a au total14exemples,9exemples positifs,5exemples inversés
S_ciel_clair=[2+,3-]//l'attribut A1Des exemples avec des valeurs de ciel clair sont au total5de2positif,3inversé
S_nuageux=[4+,0-] //l'attribut A1Des exemples avec des valeurs de nuageux sont au total4de4positif, 0 inversé
S_pluie=[3+,2-] //l'attribut A1Des exemples avec des valeurs de ciel clair sont au total5de3positif,2inversé
donc
3、 le résultat est
l'attribut A1l'information gain est le plus grand, donc il est sélectionné comme noeud racine.
4、 construire la racine et les feuilles de l'arbre de décision
ID3L'algorithme choisit l'attribut météorologique avec la plus grande information gain comme racine de l'arbre, en14个例子中对天气的3个取值进行分枝,3 个分枝对应3 个子集,分别是:
其中S2中的例子全属于P类,因此对应分枝标记为P,其余两个子集既含有正例又含有反例,将递归调用建树算法。
5、递归建树
分别对S1和S3子集递归调用ID3算法,在每个子集中对各属性求信息增益.
(1)对S1,湿度属性信息增益最大,以它为该分枝的根结点,再向下分枝。湿度取高的例子全为N类,该分枝标记N。取值正常的例子全为P类,该分枝标记P。
(2)对S3,风属性信息增益最大,则以它为该分枝根结点。再向下分枝,风取有风时全为N类,该分枝标记N。取无风时全为P类,该分枝标记P。
二、PYTHON实现决策树算法分类
本代码为machine learning in action 第三章例子,亲测无误。
1、计算给定数据shangnon数据的函数:
def calcShannonEnt(dataSet): #calculate the shannon value numEntries = len(dataSet) labelCounts = {} for featVec in dataSet: #create the dictionary for all of the data currentLabel = featVec[-1] if currentLabel not in labelCounts.keys(): labelCounts[currentLabel] = 0 labelCounts[currentLabel] +)}= 1 shannonEnt = 0.0 for key in labelCounts: prob = float(labelCounts[key])/numEntries shannonEnt -= prob*log(prob,2) #get the log value return shannonEnt
2. 创建数据的函数
def createDataSet(): dataSet = [[1,1'] [1,1, 'yes'], [1,0,'no'], [0,1'] [0,1'] labels = ['no surfacing','flippers'] return dataSet, labels
3.diviser l'ensemble de données en fonction de l'attribut donné
def splitDataSet(dataSet, axis, value): retDataSet = [] for featVec in dataSet: if featVec[axis] == value: #abstract the fature reducedFeatVec = featVec[:axis] reducedFeatVec.extend(featVec[axis+1:]) retDataSet.append(reducedFeatVec) return retDataSet
4.sélection du meilleur mode de division de l'ensemble de données
def chooseBestFeatureToSplit(dataSet): numFeatures = len(dataSet[0])-1 baseEntropy = calcShannonEnt(dataSet) bestInfoGain = 0.0; bestFeature = -1 for i in range(numFeatures): featList = [example[i] for example in dataSet] uniqueVals = set(featList) newEntropy = 0.0 for value in uniqueVals: subDataSet = splitDataSet(dataSet, i , value) prob = len(subDataSet)/float(len(dataSet)) newEntropy +=prob * calcShannonEnt(subDataSet) infoGain = baseEntropy - newEntropy if(infoGain > bestInfoGain): bestInfoGain = infoGain bestFeature = i return bestFeature
5.création récursive de l'arbre
fonction utilisée pour trouver le nom de la catégorie apparaissant le plus souvent
def majorityCnt(classList): classCount = {} for vote in classList: if vote not in classCount.keys(): classCount[vote] = 0 classCount[vote] +)}= 1 sortedClassCount = sorted(classCount.iteritems(), key=operator.itemgetter(1, reverse=True) return sortedClassCount[0][0]
Code de fonction utilisé pour créer un arbre
def createTree(dataSet, labels): classList = [example[-1] for example in dataSet] #le type est le même, donc arrêtez de classer if classList.count(classList[0]) == len(classList): return classList[0] #parcourir toutes les caractéristiques et choisir la caractéristique la plus fréquente if (len(dataSet[0]) == 1) : return majorityCnt(classList) bestFeat = chooseBestFeatureToSplit(dataSet) bestFeatLabel = labels[bestFeat] myTree = {bestFeatLabel:{}} del(labels[bestFeat]) #obtenir la liste qui atteint toutes les propriétés featValues = [example[bestFeat] for example in dataSet] uniqueVals = set(featValues) for value in uniqueVals: subLabels = labels[:] myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels) return myTree
Ensuite, entrez la commande suivante dans l'invite de commande de python :
myDat, labels = trees.createDataSet() myTree = trees.createTree(myDat, labels) print myTree
Résultat :
{'no surfacing': {0: 'non', 1: {'flippers': {0: 'non', 1: 'oui'}}}}
6.fonction实用决策树分类
def classify(inputTree, featLabels, testVec): firstStr = inputTree.keys()[0] secondDict = inputTree[firstStr] featIndex = featLabels.index(firstStr) for key in secondDict.keys(): if testVec[featIndex] == key: if type(secondDict[key]).__name__ == 'dict': classLabel = classify(secondDict[key], featLabels, testVec) else: classLabel = secondDict[key] return classLabel
Dans l'invite de commande Python, tapez :
trees.classify(myTree,labels,[1,0])
Résultat obtenu :
'non'
Félicitations. Oh yeah. Vous avez réussi.!!!
Voici la totalité du contenu de cet article, j'espère qu'il vous sera utile dans vos études, et que vous souteniez davantage le tutoriel à cri
Déclaration : le contenu de cet article est tiré d'Internet, propriété intellectuelle de son auteur respectif. Le contenu est fourni par les utilisateurs d'Internet de manière volontaire et téléversé. Ce site ne détient pas de propriété, n'a pas été édité par l'homme et n'assume aucune responsabilité juridique. Si vous trouvez du contenu présumé enfreignant les droits d'auteur, veuillez envoyer un e-mail à : notice#oldtoolbag.com (veuillez remplacer # par @ lors de l'envoi d'un e-mail pour signaler une violation, et fournir des preuves pertinentes. Une fois vérifié, ce site supprimera immédiatement le contenu présumé enfreignant les droits d'auteur.)