现在的位置: 首页 > 综合 > 正文

决策树之ID3算法实现(python) 决策树之ID3算法实现(python) 怒写一个digit classification(不断更新中)

2017年09月30日 ⁄ 综合 ⁄ 共 10560字 ⁄ 字号 小 中 大 ⁄ 评论关闭
 

决策树之ID3算法实现(python)

分类： python 算法2013-09-27
11:40 107人阅读 评论(0) 收藏 举报
算法decision
treemachine
learning

决策树的概念其实不难理解，下面一张图是某女生相亲时用到的决策树：

基本上可以理解为：一堆数据，附带若干属性，每一条记录最后都有一个分类（见或者不见），然后根据每种属性可以进行划分（比如年龄是>30还是<=30）,这样构造出来的一棵树就是我们所谓的决策树了，决策的规则都在节点上，通俗易懂，分类效果好。

那为什么跟节点要用年龄，而不是长相？这里我们在实现决策树的时候采用的是ID3算法，在选择哪个属性作为节点的时候采用信息论原理，所谓的信息增益。信息增益指原有数据集的熵-按某个属性分类后数据集的熵。信息增益越大越好（说明按某个属性分类后比较纯），我们会选择使得信息增益最大的那个属性作为当层节点的标记，再进行递归构造决策树。

首先我们构造数据集：

[python] view
plaincopy

  1. def createDataSet():  
  2.     dataSet = [[1,1,'yes'],[1,1,'yes'],[1,0,'no'],[0,1,'no'],[0,1,'no']]  
  3.     features = ['no surfacing','flippers']  
  4.     return dataSet,features  

构造决策树：（采用python字典来递归构造，一些代码看看就能看懂）

[python] view
plaincopy

  1. def treeGrowth(dataSet,features):  
  2.     classList = [example[-1] for example in dataSet]  
  3.     if classList.count(classList[0])==len(classList):  
  4.         return classList[0]  
  5.     if len(dataSet[0])==1:# no more features  
  6.         return classify(classList)  
  7.   
  8.     bestFeat = findBestSplit(dataSet)#bestFeat is the index of best feature  
  9.     bestFeatLabel = features[bestFeat]  
  10.     myTree = {bestFeatLabel:{}}  
  11.     featValues = [example[bestFeat] for example in dataSet]  
  12.     uniqueFeatValues = set(featValues)  
  13.     del (features[bestFeat])  
  14.     for values in uniqueFeatValues:  
  15.         subDataSet = splitDataSet(dataSet,bestFeat,values)  
  16.         myTree[bestFeatLabel][values] = treeGrowth(subDataSet,features)  
  17.     return myTree  

 

当没有多余的feature，但是剩下的样本不完全是一样的类别是，采用出现次数多的那个类别：

[python] view
plaincopy

  1. def classify(classList):  
  2.     ''''' 
  3.     find the most in the set 
  4.     '''  
  5.     classCount = {}  
  6.     for vote in classList:  
  7.         if vote not in classCount.keys():  
  8.             classCount[vote] = 0  
  9.         classCount[vote] += 1  
  10.     sortedClassCount = sorted(classCount.iteritems(),key = operator.itemgetter(1),reverse = True)  
  11.     return sortedClassCount[0][0]  

 

寻找用于分裂的最佳属性：（遍历所有属性，算信息增益）

[python] view
plaincopy

  1. def findBestSplit(dataset):  
  2.     numFeatures = len(dataset[0])-1  
  3.     baseEntropy = calcShannonEnt(dataset)  
  4.     bestInfoGain = 0.0  
  5.     bestFeat = -1  
  6.     for i in range(numFeatures):  
  7.         featValues = [example[i] for example in dataset]  
  8.         uniqueFeatValues = set(featValues)  
  9.         newEntropy = 0.0  
  10.         for val in uniqueFeatValues:  
  11.             subDataSet = splitDataSet(dataset,i,val)  
  12.             prob = len(subDataSet)/float(len(dataset))  
  13.             newEntropy += prob*calcShannonEnt(subDataSet)  
  14.         if(baseEntropy - newEntropy)>bestInfoGain:  
  15.             bestInfoGain = baseEntropy - newEntropy  
  16.             bestFeat = i  
  17.     return bestFeat  

 

选择完分裂属性后，就行数据集的分裂：

[python] view
plaincopy

  1. def splitDataSet(dataset,feat,values):  
  2.     retDataSet = []  
  3.     for featVec in dataset:  
  4.         if featVec[feat] == values:  
  5.             reducedFeatVec = featVec[:feat]  
  6.             reducedFeatVec.extend(featVec[feat+1:])  
  7.             retDataSet.append(reducedFeatVec)  
  8.     return retDataSet  

计算数据集的熵：

[python] view
plaincopy

  1. def calcShannonEnt(dataset):  
  2.     numEntries = len(dataset)  
  3.     labelCounts = {}  
  4.     for featVec in dataset:  
  5.         currentLabel = featVec[-1]  
  6.         if currentLabel not in labelCounts.keys():  
  7.             labelCounts[currentLabel] = 0  
  8.         labelCounts[currentLabel] += 1  
  9.     shannonEnt = 0.0  
  10.   
  11.     for key in labelCounts:  
  12.         prob = float(labelCounts[key])/numEntries  
  13.         if prob != 0:  
  14.             shannonEnt -= prob*log(prob,2)  
  15.     return shannonEnt  

下面根据上面构造的决策树进行数据的分类：

[python] view
plaincopy

  1. def predict(tree,newObject):  
  2.     while isinstance(tree,dict):  
  3.         key = tree.keys()[0]  
  4.         tree = tree[key][newObject[key]]  
  5.     return tree  
  6.   
  7. if __name__ == '__main__':  
  8.     dataset,features = createDataSet()  
  9.     tree = treeGrowth(dataset,features)  
  10.     print tree  
  11.     print predict(tree,{'no surfacing':1,'flippers':1})  
  12.     print predict(tree,{'no surfacing':1,'flippers':0})  
  13.     print predict(tree,{'no surfacing':0,'flippers':1})  
  14.     print predict(tree,{'no surfacing':0,'flippers':0})  

结果如下：

决策树是这样的：

{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}

四个预测：

yes
no
no
no

和给定的数据集分类一样（预测的数据是从给定数据集里面抽取的，当然一般数据多的话，会拿一部分做训练数据，剩余的做测试数据）

 

归纳一下ID3的优缺点：

优点：实现比较简单，产生的规则如果用图表示出来的话，清晰易懂，分类效果好

缺点：只能处理属性值离散的情况（连续的用C4.5），在选择最佳分离属性的时候容易选择那些属性值多的一些属性。

[置顶] 怒写一个digit classification(不断更新中)

分类： python 算法2013-09-12
16:11 151人阅读 评论(0) 收藏 举报
digit
classificationknnsvmnaive
bayesdecision
tree

最近开始学习machine learning方面的内容，大致浏览了一遍《machine learning in action》一书，大概了解了一些常用的算法如knn,svm等具体式干啥的。

在kaggle上看到一个练手的项目：digit classification,又有良好的数据，于是打算用这个项目把各种算法都跑一遍，加深自己对各算法的研究，该文会不断更新。。。。。。

我们的数据集是mnist，链接：http://yann.lecun.com/exdb/mnist/

mnist的结构如下，选取train-images

TRAINING SET IMAGE FILE (train-images-idx3-ubyte):

[offset] [type]          [value]          [description] 
0000     32 bit integer  0x00000803(2051) magic number 
0004     32 bit integer  60000            number of images 
0008     32 bit integer  28               number of rows 
0012     32 bit integer  28               number of columns 
0016     unsigned byte   ??               pixel 
0017     unsigned byte   ??               pixel 
........ 
xxxx     unsigned byte   ??               pixel

呐，由于智商比较拙急，看了这个形式居然没看明白，所以特此写出要注意的点，送给同样没看明白的童鞋。

首先该数据是以二进制存储的，我们读取的时候要以'rb'方式读取，其次，真正的数据只有[value]这一项，其他的[type]等只是来描述的，并不真正在数据文件里面。

由offset我们可以看出真正的pixel式从16开始的，一个int 32字节，所以在读取pixel之前我们要读取4个 32 bit integer，也就是magic number,number of images,number of rows,number of columns,读取二进制文件用struct比较方便，struct.unpack_from('>IIII',buf,index)表示按照大端方式读取4个int.

虽然数据集网站写着“Users of Intel processors and other low-endian machines must flip the bytes of the header.”，而我的电脑就是intel处理器，但是我尝试了一把还是得用大端方式读，读出来才是“2051 60000 28 28”，用小端方式读取就不正确了，这个小小实验一把就行。


下面先把数据文件直观的表现出来，用matplotlib把二进制文件用图像表现出来。具体如下：


[python] view
plaincopy

  1. # -*- coding:utf-8  
  2. import numpy as np   
  3. import struct  
  4. import matplotlib.pyplot as plt   
  5.   
  6. filename = 'train-images.idx3-ubyte'  
  7. binfile = open(filename,'rb')#以二进制方式打开  
  8. buf = binfile.read()  
  9.   
  10. index = 0  
  11. magic, numImages, numRows, numColums = struct.unpack_from('>IIII',buf,index)#读取4个32 int  
  12. print magic,' ',numImages,' ',numRows,' ',numColums  
  13. index += struct.calcsize('>IIII')  
  14.   
  15.   
  16. im = struct.unpack_from('>784B',buf,index)#每张图是28*28=784Byte,这里只显示第一张图  
  17. index += struct.calcsize('>784B' )  
  18.   
  19. im = np.array(im)  
  20. im = im.reshape(28,28)  
  21. print im  
  22.   
  23. fig = plt.figure()  
  24. plt.imshow(im,cmap = 'binary')#黑白显示  
  25. plt.show()  

结果如下（很明显式一个5字）：

好，既然能够图形化表示数字，基本上该数字的feature我们都能拿到，一下就是用各种机器学习算法来做digit classification。

以上是显示一个图片，而我们的各种学习算法一定是处理多个图片的，那么有必要单独写一个文件来处理数据问题，即

ReadData.py:(代码和上面不少相似，这里只给链接)

https://github.com/wangyuquan/MachineLearning/blob/master/digitClassification/ReadData.py

（1）KNN：

      KNN可以说是最简单的分类器了。首先给予训练数据，并且给予这些训练数据的类别，然后当有一个新的数据进来的时候，根据最临近的k个节点的分类情况，例如k=5,就

取离新数据最近的5个点，假设3个类别是A,2个是B,按照多数服从少数的原则，将新数据赋予类别A.

具体代码如下：

[python] view
plaincopy

  1. from sklearn import neighbors  
  2. from ReadData import *  
  3. import datetime  
  4. startTime = datetime.datetime.now();  
  5. trainImage = getTrainImage()  
  6. trainLabel = getTrainLabel()  
  7. testImage = getTestImage()  
  8. testLabel = getTestLabel()  
  9. knn = neighbors.KNeighborsClassifier(algorithm = 'auto',leaf_size = 30,n_neighbors=3,warn_on_equidistant = True,weights = 'uniform')  
  10. knn.fit(trainImage,trainLabel)  
  11. match = 0;  
  12. for i in xrange(len(testLabel)):  
  13.     predictLabel = knn.predict(testImage[i])[0]  
  14.     print i,' ',  
  15.     print predictLabel,' ', testLabel[i]  
  16.     if(predictLabel==testLabel[i]):  
  17.         match += 1  
  18.   
  19. endTime = datetime.datetime.now()  
  20. print 'use time: '+str(endTime-startTime)  
  21. print 'error rate: '+ str(1-(match*1.0/len(testLabel)))  

效果如下：

错误率为3.91%，这里我的k选的是3，接下来我会尝试不同的k,来看不同k带来的不同影响。

优点：简单易懂，实现方便（指具体算法实现，当然我们在用的时候都是直接调用库啦：））

缺点：算法复杂度为K*M（train data的大小）*N（test data的大小），耗时较长，因为每个新数据都要与所以training data计算下距离，大数据情况下可能吃不消

（2）SVM:

svm可以写的还真的挺多的，这里只写一些比较重要的，并且需要记住的几点

首先svm本质上是一个二元分类器，但是也可以扩展来出来多元分类（先一分为二，剩下的再分，还有DAG等方法）。svm可以处理线性可分或者不可分的数据：线性可分的话，举个例子在二维平面数据可以被一条直线一分为二，主要工作就是找这条直线（维数多了就是超平面），然后通过优化方法找到直线或者超平面，使得margin最大（margin指点到分割面的最短距离），对于线性不可分的数据来说，采用升维的方法，也就是大家指的核函数，把数据变成基本可分，引入松弛变量来处理某些噪声点，也就是所谓的离群点，用惩罚因子来代表我们对离群点的重视度，越大越重视。至今还没真正理解svm的算法复杂度，等待进一步的学习。以下代码还是直接调用库函数，有空自己写一个简单版的.（这个没有进行多种调参，因为只是想学习svm的原理）

具体代码如下：

[python] view
plaincopy

  1. from sklearn import svm  
  2. from ReadData import *  
  3. import datetime  
  4. startTime = datetime.datetime.now();  
  5. trainImage = getTrainImage()  
  6. trainLabel = getTrainLabel()  
  7. testImage = getTestImage()  
  8. testLabel = getTestLabel()  
  9. clf = svm.SVC(kernel='rbf')  
  10. clf.fit(trainImage,trainLabel)  
  11. match = 0  
  12. for i in range(len(testImage)):  
  13.     predictResult = int(clf.predict(testImage[i])[0])  
  14.     if(predictResult==testLabel[i]):  
  15.         match += 1  
  16.     print i,' ',predictResult ,' ',testLabel[i]  
  17.   
  18. endTime = datetime.datetime.now()  
  19. print 'match:',match  
  20. print 'use time: '+str(endTime-startTime)  
  21. print 'error rate: '+ str(1-(match*1.0/len(testImage)))  

结果如下：

3：Navie Bayes

贝叶斯分类器均建立在贝叶斯公式上：P（x|y) = P(y|x)*P(x)/P(y)

在分类问题中，x代表类别，y代表特征向量，P（x|y)很难求，但是可以通过等号后面几者来求，P(y)是确定的，可以忽略，求某个特征向量最可能属于哪个类是，只要比出哪个类的概率最大就行，在比较是分母都一样，所以可以忽略，只需要求 P(y|x)*P(x)，P（x)表示类别的概率， P(y|x)表示该类下特征向量是y的概率，这个有点难求。但是朴素贝叶斯假定，每个feature之间相互无关，即 P(y|x) = P（y1|x)*P(y2|x)****P(yn|x),这样就能求得该变量，该假设十分简单有效。

具体代码如下：

[python] view
plaincopy

  1. <pre name="code" class="python">from sklearn.naive_bayes import MultinomialNB  
  2. from ReadData import *  
  3. import datetime  
  4. startTime = datetime.datetime.now();  
  5. trainImage = getTrainImage()  
  6. trainLabel = getTrainLabel()  
  7. testImage = getTestImage()  
  8. testLabel = getTestLabel()  
  9. mnb = MultinomialNB()  
  10. mnb.fit(trainImage,trainLabel)  
  11. match = 0  
  12. for i in range(len(testImage)):  
  13.     predictResult = int(mnb.predict(testImage[i])[0])  
  14.     if(predictResult==testLabel[i]):  
  15.         match += 1  
  16.     print i,' ',predictResult ,' ',testLabel[i]  
  17.   
  18. endTime = datetime.datetime.now()  
  19. print 'match:',match  
  20. print 'use time: '+str(endTime-startTime)  
  21. print 'error rate: '+ str(1-(match*1.0/len(testImage)))</pre><br><br>  

结果如图：


错误率较高，原因很明显，我们将每个像素作为feature，这些feature之间肯定是有关的，不能假设为独立

navie bayes适合各个feature独立的分类：）

（4）：decision tree

决策树是一个很能直观理解的分类过程。不需要额外的参数。具体怎么构造决策树，选取哪个feature作为决策点，主要算法有ID3和C4.5。

具体代码如下：

[python] view
plaincopy

  1. from sklearn import tree  
  2. from ReadData import *  
  3. import datetime  
  4. startTime = datetime.datetime.now();  
  5. trainImage = getTrainImage()  
  6. trainLabel = getTrainLabel()  
  7. testImage = getTestImage()  
  8. testLabel = getTestLabel()  
  9. clf = tree.DecisionTreeClassifier()  
  10. clf.fit(trainImage,trainLabel)  
  11. match = 0  
  12. for i in range(len(testImage)):  
  13.     predictResult = int(clf.predict(testImage[i])[0])  
  14.     if(predictResult==testLabel[i]):  
  15.         match += 1  
  16.     print i,' ',predictResult ,' ',testLabel[i]  
  17.   
  18. endTime = datetime.datetime.now()  
  19. print 'match:',match  
  20. print 'use time: '+str(endTime-startTime)  
  21. print 'error rate: '+ str(1-(match*1.0/len(testImage)))  

结果如下：

结果也不是特别令人满意，原因和上一个差不多，我们构造的feature不太适合用决策树来分类。

（5）TODO：

返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞