머 신 러 닝 입문 - 의사 결정 트 리 (1)

15882 단어 기계 학습 입문
지난 글 에서 kNN 알고리즘 을 배 웠 는데 많은 분류 임 무 를 완성 할 수 있 지만 가장 큰 단점 은 데이터 의 내부 적 의 미 를 제시 하지 못 하 는 것 이다. 이에 비해 결정 트 리 의 장점 은 바로
  • 데이터 형식 은 이해 하기 쉽다
  • 분류 기 를 지속 화 할 수 있 고 kNN 은 분류 할 때마다 다시 배 워 야 한다
  • 결정 트 리 역시 흔히 볼 수 있 는 기계 학습 알고리즘 으로 그 목적 은 주어진 훈련 데이터 세트 에서 모델 을 배 워 서 새로운 예 시 를 분류 하 는 것 이다.의사 결정 트 리 알고리즘 은 주로 ID3, CART, C 4.5 등 이 있다.각 알고리즘 이 견본 집합 에 대한 구분 준칙 을 토론 하기 전에 먼저 정 의 를 가 져 옵 니 다.
    정보 엔트로피
  • 정보 엔트로피 (information entropy) 는 도량형 견본 의 집합 순도 에 가장 자주 사용 되 는 기준 으로 현재 견본 집합 D 에서 k 류 견본 이 차지 하 는 비율 이 pk 라 고 가정 하면 D 의 정보 엔트로피 는 Ent (D) = - > p (xk) log (2, p (xk) (k = 1, 2,.. n)
  • 로 정의 된다.
  • 정보 엔 트로피 를 계산 할 때 if p = 0 = > p * log (2, p) = 0
  • 정보 이득
  • 데이터 세트 를 구분 하기 전에 정보 가 발생 하 는 변화 가 정보 이득
  • 이 된다.
  • 분 산 된 속성 a 가 V 개의 가능 한 값 {a1, a2,..., av} 이 있다 고 가정 하면 a 를 사용 하여 견본 집 D 를 구분 하면 V 개의 분기 결산 점 이 생 길 수 있 습 니 다. 그 중에서 v 의 분기 결산 점 은 D 중의 모든 속성 a 에서 av 의 견본 을 포함 하고 Dv 로 기록 하 며 서로 다른 분기 결산 점 에 가중치 | Dv | / | D | 를 부여 하기 때문에 속성 a 가 견본 집 D 를 구분 하여 얻 은 것 을 계산 할 수 있 습 니 다."정보 이득" Gain (D, a) = Ent (D) - ∑ | Dv | / | D | * Ent (Dv)
  • 일반적으로 정보 이득 이 클 수록 속성 a 를 사용 하여 소득 의 순 도 를 나 누 는 것 을 의미한다
  • .
  • 취 할 수 있 는 수치 가 많은 속성 을 선 호한 다
  • 이득 률
  • Gain_ratio(D,a)=Gain(D,a)/IV(a)
  • 그 중에서 IV (a) = - ∑ (| Dv | / | D | * log 2 (| Dv | / | D |) 는 a 의 "고유 값"
  • 이 라 고 부른다.
  • 취 할 수 있 는 수치 가 적은 속성 을 선 호한 다
  • 지 니 야.
  • 데이터 세트 D 의 순 도 는 지 니 값 으로 평가 할 수 있다. 지 니 (D) = 1 - ∑ pk ^ 2 (k = 1, 2,...) 직관 적 으로 말 하면 지 니 (D) 는 D 에서 두 개의 견본 을 무 작위 로 추출 하 는데 그 유형 표시 가 일치 하지 않 을 확률 을 나타 내 므 로 지 니 (D) 가 작 을 수록 데이터 세트 D 의 순도 가 높다
  • .
  • 속성 a 의 지 니 지 수 는 Gini index (D, a) = ∑ (| Dv | / | D | * Gini (Dv) 로 정의 한다.
    그래서 방금 언급 한 세 가지 결정 트 리 알고리즘 이 선택 한 구분 준칙 은 ID3 – 정보 이득, C 4.5 – 이득 율, CART – 지 니 지수 와 관련 된 결정 트 리 는 보통 가지치기 처리, 연속 값 처리, 결여 값 처리, 다 변수 결정 트 리 등 문제 와 관련 되 는데 이 문 제 는 결정 트 리 (2) (3) 에 놓 일 것 이다.학습 분석 을 가 져 옵 니 다. 오늘 의 실전 의 중점 은 ID3 입 니 다. 관련 소스 코드 와 테스트 샘플 이 github 에서 github 링크 주소 입 니 다.
    계산 정보 엔트로피
    def calcShannonEnt(dataSet):
        numEntries=len(dataSet)
        labelCounts={}
        for featVec in dataSet:
            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)
        return shannonEnt

    설명: dataset 는 다음 과 같은 특징 을 가 진 데이터 입 니 다.
    dataSet = [[1, 1, 'yes'],
               [1, 1, 'yes'],
               [1, 0, 'no'],
               [0, 1, 'no'],
               [0, 1, 'no']]
    

    특정한 특징 값 을 선택 하여 데이터 세트 를 구분 하 다.
    #axis                ,value               
    def splitDataSet(dataSet,axis,value):
        retDataSet=[]
        for featVec in dataSet:
            if featVec[axis]==value:
                reducedFeatVec=featVec[:axis]
                reducedFeatVec.extend(featVec[axis+1:])
                retDataSet.append(reducedFeatVec)
        return retDataSet

    가장 좋 은 구분 속성 선택
    def chooseBestFeatureToSplit(dataSet):
        #the number of feature attributes that the current data packet contains
        numFeatures=len(dataSet[0])-1
    
        # entropy  
        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

    목록 을 지정 하여 가장 많이 나타 난 요 소 를 되 돌려 줍 니 다.
    def majorityCnt(classList):
        classCount={}
        for vote in classList:
            if vote not in classCount.keys():
                classCount[vote]=0
            classCount[vote]+=1
        sortedClassCount=sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
        return sortedClassCount[0][0]

    재 귀 구조 결정 트 리 (사전 형식 으로 표시)
    def createTree(dataSet,labels):
        classList=[example[-1] for example in dataSet]
        #             
        if classList.count(classList[0]) == len(classList):
            return classList[0]
        #                   
        if len(dataSet[0])==1:
            return majorityCnt(classList)
    
        bestFeat=chooseBestFeatureToSplit(dataSet)
        bestFeatLabel=labels[bestFeat]
        mytree={bestFeatLabel:{}}
        del(labels[bestFeat])
        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

    단순 한 사전 형식 이 직관 적 이지 못 하 다 고 생각한다 면, matplotlib 를 통 해 그 릴 수도 있다.
    # coding=utf-8
    from matplotlib.font_manager import FontProperties
    import matplotlib.pyplot as plt
    from math import log
    import operator
    
    decisionNode=dict(boxstyle="sawtooth",fc="0.8")
    leafNode=dict(boxstyle="round4",fc="0.8")
    arrow_args=dict(arrowstyle=")
    
    def plotNode(nodeTxt, centerPt, parentPt, nodeType):
        createPlot.ax1.annotate(nodeTxt, xy=parentPt,  xycoords='axes fraction',
                 xytext=centerPt, textcoords='axes fraction',
                 va="center", ha="center", bbox=nodeType, arrowprops=arrow_args )
    
    # def createPlot():
    #     fig = plt.figure(1, facecolor='white')
    #     fig.clf()
    #     createPlot.ax1 = plt.subplot(111, frameon=False) #ticks for demo puropses 
    #     plotNode('    ', (0.5, 0.1), (0.1, 0.5), decisionNode)
    #     plotNode('   ', (0.8, 0.1), (0.3, 0.8), leafNode)
    #     plt.show()
    
    def createPlot(inTree):
        fig=plt.figure(1,facecolor='white')
        fig.clf()
        axprops=dict(xticks=[],yticks=[])
        createPlot.ax1=plt.subplot(111,frameon=False,**axprops)
        plotTree.totalW=float(getNumLeafs(inTree))
        plotTree.totalD=float(getTreeDepth(inTree))
        plotTree.xOff=-0.5/plotTree.totalW
        plotTree.yOff=1.0
        plotTree(inTree,(0.5,1.0),'')
        plt.show()
    
    def getNumLeafs(myTree):
        numleafs=0
        firstStr=next(iter(myTree))
        sencondDict=myTree[firstStr]
        for key in sencondDict.keys():
            if type(sencondDict[key]).__name__=='dict':
                numleafs+=getNumLeafs(sencondDict[key])
            else:
                numleafs+=1
        return numleafs
    
    def getTreeDepth(myTree):
        maxDepth=0
        firstStr=next(iter(myTree))
        secondDict=myTree[firstStr]
        for key in secondDict.keys():
            if type(secondDict[key]).__name__=='dict':
                thisDepth=1+getTreeDepth(secondDict[key])
            else:
                thisDepth=1
            if thisDepth>maxDepth:
                maxDepth=thisDepth
        return maxDepth
    
    def plotMidText(cntrPt,parentPt,txtString):
        xMid = (parentPt[0]-cntrPt[0])/2.0 + cntrPt[0]                               
        yMid = (parentPt[1]-cntrPt[1])/2.0 + cntrPt[1]
        createPlot.ax1.text(xMid,yMid,txtString)
    
    def plotTree(myTree,parentPt,nodeTxt):
        numLeafs=getNumLeafs(myTree)
        depth=getTreeDepth(myTree)
        firstStr=next(iter(myTree))
        cntrPt=(plotTree.xOff+(1.0+float(numLeafs))/2.0/plotTree.totalW,plotTree.yOff)
        plotMidText(cntrPt,parentPt,nodeTxt)
        plotNode(firstStr,cntrPt,parentPt,decisionNode)
        secondDict=myTree[firstStr]
        plotTree.yOff=plotTree.yOff-1.0/plotTree.totalD
        for key in secondDict.keys():
            if type(secondDict[key]).__name__=='dict':
                plotTree(secondDict[key],cntrPt,str(key))
            else:
                plotTree.xOff=plotTree.xOff+1.0/plotTree.totalW
                plotNode(secondDict[key],(plotTree.xOff,plotTree.yOff),cntrPt,leafNode)
                plotMidText((plotTree.xOff,plotTree.yOff),cntrPt,str(key))
        plotTree.yOff=plotTree.yOff+1.0/plotTree.totalD

    어떻게 의사 결정 트 리 를 통 해 분류 합 니까?
    #        
    def classify(inputTree,featlabels,testVec):
        firstStr=next(iter(inputTree))
        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

    설명 하 다.
    featlabels    :['no surfacing','flippers']
    testVec    : [0,1]
    

    txt 의 데이터 세트 에 따 른 실전 분류
    def lensesClassify():
        fr=open('lenses.txt','r')
        lenses=[inst.strip().split('\t') for inst in fr.readlines()]
        lensesLabels = ['age', 'prescript', 'astigmatic', 'tearRate']
        lensesTree=createTree(lenses,lensesLabels)
        tp.createPlot(lensesTree)
  • 좋은 웹페이지 즐겨찾기