关键词：分类·监督学习 原理：基于特征的信息比重，进行规则提取。进而用于决策。 简单来讲：存在一个样本数据集合（训练集），样本中的每一条数据都存在一个标签（所属分类）。预测数据集合是仅有特征数据没有标签的数据集合。 我们首先对样本集合的数据进行分析，构造出一颗树，树的叶子节点为标签（终止节点），非叶子节点为特征（判断模块）。 首先，选取一个特征作为判断模块，该特征能“足够好”的将原集合划分成若干较小的集合。对划分后的较小集合，如果集合中的元素均属同一类别（或者 没有特征可以继续划分），则终止，该终止节点的属性为该类别（或者集合中最多的类别）；否则对较小集合进行继续选取剩余特征，划分，递归下去。 最终形成一个树。当拿到预测集合的数据时，从根节点（最重要节点）的特征进行匹配，依次往下，直到到达所属分类，即为预测分类。 优缺点：计算复杂度不高，结果易于理解，对中间值缺失不敏感，可处理不相关特征数据。适用于专家系统。 但可能会产生overfitting
函数名称：
createTree(dataSet,labels)
函数说明：
递归创建决策树
输入参数：
dataSet : 训练集（特征向量+类别） ： array
labels : 特征向量名称 ： list
返回参数：
返回构造的决策树 ： dict
def createTree(dataSet,labels):
#获取训练集样本的类别
classList = [example[-1] for example in dataSet]
#集合是否属于一类：
if classList.count(classList[0]) == len(classList):
return labels
#判断是否只剩下一个特征：
if len(dataSet[0]) == 1:
return majorityCnt(classList)
#均不是以上两种情况，选取最好特征进行分类
bestFeatIndex = chooseBestFeatureToSplit(dataSet)
bestFeatLabel = labels[bestFeatIndex]
#构建一个决策模块
myTree = {bestFeatLabel:{}}
del(labels[bestFeatIndex])
#获取决策模块的分支情况
featValues = [example[bestFeatIndex] for example in dataSet]
uniqueVals = set(featValues)
#创建该节点下的所有分支
for value in uniqueVals:
#Python传引用，避免破坏，clone一份
subLabels = labels[:]
#创建其中一个value对应的分支
myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet,bestFeat,value),subLabels)
return myTree
-------------------------------------------------------------------------------------------------------------------------
函数名称：
classify(inputTree,featLabels,testVec)
函数说明：
递归的寻找最有可能的分类标签
输入参数：
inputTree : 构建的决策树 ： dict
featLabels : 预测数据的特征名称 ： list
teseVec : 预测数据的特征值（与featLabels对应） ： list
返回参数：
预测的分类
def classify(inputTree,featLabels,testVec):
#获取根判断模块的feature
firstStr = inputTree.keys()[0]
#获取判决模块下的森林（集合）
secondDict = inputTree[firstStr]
#获取预测数据的对应的该判决模块在featLabels中的位置，便于取值
featIndex = featLabels.index(firstStr)
#遍历森林，找对应的树
for key in secondDict.keys():
if key == testVec[featIndex]:
#该value对应的是一颗树（未到分类节点），继续递归
if type(secondDict[key]).__name__ == "__dict__":
classLabel = classify(secondDict[key],featLabels,testVec)
#否则到达分类节点
else:
classLabel = secondDict[key]
return classLabel
-------------------------------------------------------------------------------------------------------------------------
划分数据集合的大原则：将无序的数据变得更加有序。这也就用到了Information Theory（信息论）上的知识：
entropy（熵）和 information gain（信息增益）
这里通俗的阐述一下相关的概念：
首先介绍关于信息的度量问题。信息是存在于消息（必须非假）之中，信息的作用在于消除我们对未知的不确定性。
这种消息出现的可能性越小，所承载的信息量就越大。比如，现在当前阳光明媚，在你看来丝毫没有变天的可能，但是气象台告知等会将要下雨。
那么这条消息所含的信息量是极大的。对于某个事件的信息量，我们描述它的话，就要综合这个事件所有可能发生情况（对于会不会下雨这个事件，
考虑的集合空间就只有两种：下 or 不下），将所有可能情况的信息量加权平均。---就得到了熵。
现在阳光明媚，晴空万里，没有丝毫下雨迹象，你也不知道下一时刻，会不会下雨，还是依旧阳光明媚（假设两种情况出现的可能均为一半）。
这时候计算出一个关于“是否下雨”事件的熵。一会之后，飘来一大片乌云，开始起风，这时候再计算熵，值肯定下降。那么前后两个熵的差值即为
信息增益。也就是说这大片乌云，大大增加了下雨的可能性，天平往一边倾斜啦，不确定性下降了。
扯了那么多，对于决策树的挑选特征，我们怎么运用呢？回到大原则，我们挑选特征，就是为了能够将一个“无序”（里面的东西不是属于一个类别的
）通过某个特征分成不同的小集合，然后各个小集合尽可能的变得“有序”（里面的东西属于一个类别），降低不确定度，达到最大的信息增益。这样
就是 ID3算法所使用的贪心策略：能获得最高信息增益的特征就是最好特征。
当然还有另一种度量方式：基尼不纯度。以后讨论
用代码说话：
函数名称：
calcShannonEntropy(dataSet)
函数功能：
计算香农熵
输入参数：
dataSet : 训练集数据（特征+标签） : array
返回参数：
香农熵
def calcShannonEntropy(dataSet):
numEntries = len(dataSet)
labelsCount = {}
#统计各种情况出现次数
for featVec in dataSet:
currentLabel = featVec[-1]
if currentLabel in labelsCount:
labelsCount[currentLabel] += 1
else:
labelsCount[currentLabel] = 0
#计算香农熵
shannonEntropy = 0.0
for key in labelsCount:
prob = labelsCount[key]/numEntries
shannonEntropy -= prob * log(prob,2)
return shannonEntropy
-------------------------------------------------------------------------------------------------------------------------
在进行特征选择时，需要根据不同的特征，对数据集合进行划分，给出划分模块 函数名称： splitDataSet(dataSet,axis,value) 函数功能： 根据特征值划分数据集合，返回符合特征值的特征集合，会消耗特征 输入参数： dataSet : 预测集合（特征+类别） : array axis : 划分坐标轴（特征序号） : int value : 特征值 : str 返回参数： 返回dataSet中axis代表的feature值为value的sub-dataSet def splitDataSet(dataSet,axis,value): retDataSet = [] for featVec in dataSet: if featVec[axis] == value: reducedFeatVec = featVec[:axis] reducedFeatVec.extend(fectVec[axis+1:]) retDataSet.append(reducedFeatVec) return retDataSet -------------------------------------------------------------------------------------------------------------------------
这里采用的是ID3算法，因此每次特征选择之后，会消耗特征。 函数名称： chooseBestFeatureToSplit(dataSet) 函数功能： 根据信息增益，选择最好特征划分数据集合 输入参数： dataSet : 预测集合（特征+类别） ： array 返回参数： 返回最好特征 str def chooseBestFeatureToSplit(dataSet): numFeature = len(dataSet[0]) - 1 baseEntropy = calcShannonEntropy(dataSet) bestFeatureIndex = -1 bestInfoGain = 0.0 for i in range(numFeature): #获取第i个特征的所有可能情况 featureValueList = [example[i] for example in dataSet] featureValueSet = set(featureValueList) #计算每种情况的熵 newEntropy = 0.0 for key in featureValueSet: subDataSet = splitDataSet(dataSet,i,key) prob = len(subDataSet)/float(len(dataSet)) newEntropy += (prob * calcShannonEntropy(subDataSet)) #计算分割之后的信息增益 infoGain = baseEntropy - newEntropy #更新 if infoGain > baseInfoGain: bestInfoGain = infoGain bestFeatureIndex = i return bestFeatureIndex -------------------------------------------------------------------------------------------------------------------------
当特征消耗完，属于一个子集的实体仍旧不是同一个分类，这时候就要挑选出出现次数最多的分类作为判决节点。
函数名称：
majorityCnt(classList)
函数功能：
选择出现次数最多的类别
输入参数：
classList : 类别列表 : list
返回参数：
出现次数最多的分类
def majorityCnt(classList):
classCount = {}
for vote in classList:
#classCount[vote] = classCount.get(vote,0) + 1
if vote in classCount.key():
class[vote] += 1
else:
class[vote] = 0
sortedClassCount = sorted(classCount.iteritems(),key = operator.itemgetter(1),reverse = True)
return sortedClassCount[0][0]
-------------------------------------------------------------------------------------------------------------------------
构建决策树（以及其他分类器）都是一个相当耗费资源以及时间的过程，如何将学到分类器存储起来，便涉及到一个非常重要的技术： 对象序列化 对象的序列化，简单来讲，就是将对象保存在外部存储器上，需要的时候再读取出来。 通过这项技术，我们可以实现决策树的持久化 在Python中，通过使用pickle模块序列化对象。 函数名称： storeTree(inputTree,filename): 函数功能： 将决策树，持久化的保存到文件中 输入参数： inputTree : 决策树 : dict filename : 保存到的文件 : str 返回参数： 无 def storeTree(inputTree,filename): import pickle fw = open(filename,"w") pickle.dump(inputTree,fw) fw.close() --------------------- 函数名称： grabTree(filename) 函数功能： 将决策树对象从文件读取到内存，还原对象 输入参数： filename : 决策树保存的文件 ：str 返回参数： 决策树对象 ： dict def grabTree(filename): import pickle fr = open(filename,"r") return pickle.load(fr) -------------------------------------------------------------------------------------------------------------------------
Welcome to contact me,the friends who like Machine-Learning and Data-Mining.
03 Nov 2014
