ID3決策樹(shù)是以信息增益作為決策標(biāo)準(zhǔn)的一種貪心決策樹(shù)算法

成都創(chuàng)新互聯(lián)專(zhuān)注于嶺東企業(yè)網(wǎng)站建設(shè),響應(yīng)式網(wǎng)站開(kāi)發(fā),購(gòu)物商城網(wǎng)站建設(shè)。嶺東網(wǎng)站建設(shè)公司,為嶺東等地區(qū)提供建站服務(wù)。全流程定制制作，專(zhuān)業(yè)設(shè)計(jì)，全程項(xiàng)目跟蹤，成都創(chuàng)新互聯(lián)專(zhuān)業(yè)和態(tài)度為您提供的服務(wù)

# -*- coding: utf-8 -*-


from numpy import *
import math
import copy
import cPickle as pickle


class ID3DTree(object):
  def __init__(self): # 構(gòu)造方法
    self.tree = {} # 生成樹(shù)
    self.dataSet = [] # 數(shù)據(jù)集
    self.labels = [] # 標(biāo)簽集


  # 數(shù)據(jù)導(dǎo)入函數(shù)
  def loadDataSet(self, path, labels):
    recordList = []
    fp = open(path, "rb") # 讀取文件內(nèi)容
    content = fp.read()
    fp.close()
    rowList = content.splitlines() # 按行轉(zhuǎn)換為一維表
    recordList = [row.split("\t") for row in rowList if row.strip()] # strip()函數(shù)刪除空格、Tab等
    self.dataSet = recordList
    self.labels = labels


  # 執(zhí)行決策樹(shù)函數(shù)
  def train(self):
    labels = copy.deepcopy(self.labels)
    self.tree = self.buildTree(self.dataSet, labels)


  # 構(gòu)件決策樹(shù)：穿件決策樹(shù)主程序
  def buildTree(self, dataSet, lables):
    cateList = [data[-1] for data in dataSet] # 抽取源數(shù)據(jù)集中的決策標(biāo)簽列
    # 程序終止條件1：如果classList只有一種決策標(biāo)簽，停止劃分，返回這個(gè)決策標(biāo)簽
    if cateList.count(cateList[0]) == len(cateList):
      return cateList[0]
    # 程序終止條件2：如果數(shù)據(jù)集的第一個(gè)決策標(biāo)簽只有一個(gè)，返回這個(gè)標(biāo)簽
    if len(dataSet[0]) == 1:
      return self.maxCate(cateList)
    # 核心部分
    bestFeat = self.getBestFeat(dataSet) # 返回?cái)?shù)據(jù)集的最優(yōu)特征軸
    bestFeatLabel = lables[bestFeat]
    tree = {bestFeatLabel: {}}
    del (lables[bestFeat])
    # 抽取最優(yōu)特征軸的列向量
    uniqueVals = set([data[bestFeat] for data in dataSet]) # 去重
    for value in uniqueVals: # 決策樹(shù)遞歸生長(zhǎng)
      subLables = lables[:] # 將刪除后的特征類(lèi)別集建立子類(lèi)別集
      # 按最優(yōu)特征列和值分隔數(shù)據(jù)集
      splitDataset = self.splitDataSet(dataSet, bestFeat, value)
      subTree = self.buildTree(splitDataset, subLables) # 構(gòu)建子樹(shù)
      tree[bestFeatLabel][value] = subTree
    return tree


  # 計(jì)算出現(xiàn)次數(shù)最多的類(lèi)別標(biāo)簽
  def maxCate(self, cateList):
    items = dict([(cateList.count(i), i) for i in cateList])
    return items[max(items.keys())]


  # 計(jì)算最優(yōu)特征
  def getBestFeat(self, dataSet):
    # 計(jì)算特征向量維，其中最后一列用于類(lèi)別標(biāo)簽
    numFeatures = len(dataSet[0]) - 1 # 特征向量維數(shù)=行向量維數(shù)-1
    baseEntropy = self.computeEntropy(dataSet) # 基礎(chǔ)熵
    bestInfoGain = 0.0 # 初始化最優(yōu)的信息增益
    bestFeature = -1 # 初始化最優(yōu)的特征軸
    # 外循環(huán)：遍歷數(shù)據(jù)集各列，計(jì)算最優(yōu)特征軸
    # i為數(shù)據(jù)集列索引：取值范圍0~(numFeatures-1)
    for i in xrange(numFeatures):
      uniqueVals = set([data[i] for data in dataSet]) # 去重
      newEntropy = 0.0
      for value in uniqueVals:
        subDataSet = self.splitDataSet(dataSet, i, value)
        prob = len(subDataSet) / float(len(dataSet))
        newEntropy += prob * self.computeEntropy(subDataSet)
      infoGain = baseEntropy - newEntropy
      if (infoGain > bestInfoGain): # 信息增益大于0
        bestInfoGain = infoGain # 用當(dāng)前信息增益值替代之前的最優(yōu)增益值
        bestFeature = i # 重置最優(yōu)特征為當(dāng)前列
    return bestFeature



  # 計(jì)算信息熵
  # @staticmethod
  def computeEntropy(self, dataSet):
    dataLen = float(len(dataSet))
    cateList = [data[-1] for data in dataSet] # 從數(shù)據(jù)集中得到類(lèi)別標(biāo)簽
    # 得到類(lèi)別為key、 出現(xiàn)次數(shù)value的字典
    items = dict([(i, cateList.count(i)) for i in cateList])
    infoEntropy = 0.0
    for key in items: # 香農(nóng)熵： = -p*log2(p) --infoEntropy = -prob * log(prob, 2)
      prob = float(items[key]) / dataLen
      infoEntropy -= prob * math.log(prob, 2)
    return infoEntropy


  # 劃分?jǐn)?shù)據(jù)集： 分割數(shù)據(jù)集； 刪除特征軸所在的數(shù)據(jù)列，返回剩余的數(shù)據(jù)集
  # dataSet : 數(shù)據(jù)集； axis: 特征軸； value: 特征軸的取值
  def splitDataSet(self, dataSet, axis, value):
    rtnList = []
    for featVec in dataSet:
      if featVec[axis] == value:
        rFeatVec = featVec[:axis] # list操作：提取0~（axis-1）的元素
        rFeatVec.extend(featVec[axis + 1:])
        rtnList.append(rFeatVec)
    return rtnList
  # 存取樹(shù)到文件
  def storetree(self, inputTree, filename):
    fw = open(filename,'w')
    pickle.dump(inputTree, fw)
    fw.close()

  # 從文件抓取樹(shù)
  def grabTree(self, filename):
    fr = open(filename)
    return pickle.load(fr)

分享題目：python實(shí)現(xiàn)ID3決策樹(shù)算法-創(chuàng)新互聯(lián)
文章源于：http://vcdvsql.cn/article44/jehee.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供企業(yè)建站、全網(wǎng)營(yíng)銷(xiāo)推廣、域名注冊(cè)、關(guān)鍵詞優(yōu)化、網(wǎng)頁(yè)設(shè)計(jì)公司、網(wǎng)站改版

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)