决策树算法总结
优点：计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据。
缺点：可能会产生过度匹配问题。
适用数据类型：数值型和标称型。
算法工作原理：
为了找到决定性特征值，划分出最好的结果，我们必须评估每个特征。完成测试后，原始数据集被划分为几个数据子集。这些数据子集会分布在第一个决策点的所有分支上。如果某个数据分支下的数据属于同一类型，则当前无需进一步对数据集进行分割。如果数据子集内的数据不属于同一类型，则需要重复划分数据子集的过程。如果划分数据子集的算法和划分原始数据集的方法相同，直到所有具有相同类型的数据均在一个数据子集内。
伪代码（函数createBrabch（））：
If so return 类标签；
else
寻找划分数据集的最好特征
划分数据集
创建分支节点
for 每个划分的子集
调用函数createBrabch并增加返回结果到分支节点中
return 分支节点
构建过程（使用Python语言）：
一．在构造决策树时，我们需要解决的第一个问题：
当前数据集上哪个特征在划分数据分类时起决定性作用
为了解决这个问题，我们先引入几个概念：
1. 信息：如果待分类的事务可能划分在多个分类之中，则符号
的信息定义为
其中
是选择该分类的概率。
2. 香农熵（简称为熵）：信息的期望值。为了计算熵，我们需要计算所有类别所有可能的值包含的信息期望值，通过下面公式可以得到
其中n是分类的数目。
3. 信息增益：数据集划分前后信息发生的变化。
程序清单1： 计算给定数据的香农熵
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
二．在学习了如何度量数据集的无序程度后，还要划分数据集，度量划分数据集的熵，以便确定当前是否正确地划分了数据集。我们将对每个特征划分数据集的结果计算一次信息熵，然后判断哪个特征划分数据集是最好的划分方式。
程序清单2: 按照给定特征划分数据集
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
三个输入参数分别为：待划分数据集，划分数据集的特征，特征的返回值。
注意：extend()和append()方法的使用。
程序清单3： 选择最好的数据集划分方式
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
遍历整个数据集，循环计算香农熵和splitDataSet()函数，找到最好的特征划分方式。
三．学习了从数据集构造决策树算法所需的子功能模块后，开始构建决策递归树，其工作原理如下：得到原始数据，然后基于最好的属性值划分数据集，由于特征值可能有多余两个，因此可能存在大于两个分支的数据集划分。第一次划分后，数据将被传递到树分支下一个节点，在这个节点上，我们可以再次划分数据。因此我们可以采用递归的原则处理数据集。
递归结束的条件是：遍历完所有划分数据集的属性，或者每个分支下的所有实例都具有相同的分类。如果所有实例具有相同的分类，则得到一个叶子节点或者终止块。任何到达叶子节点的数据必然属于叶子节点的分类。
程序清单4： 选择出现次数最多的分类
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]
程序清单5： 创建决策树
def createTree (dataSet, labels) :
classList = [example[-1] for example in dataSet]
if classList.count(classList[0]) == len(classList) :
print 'classList are same'
return classList[0]
if len(dataSet[0]) == 1 :
print 'no feature'
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
递归函数的第二个结束条件是使用完了所有特征，仍然不能数据集划分为仅包含唯一类别的分组，因此使用出现次数最多的分类作为返回值。
到这里一颗决策树就构建完成了。
第二篇：算法总结
算法学习报告
学习总结：
对于算法这门课，要善于给出算法的形式化表示，学会用一些算法分析的数学基础，原来的时间复杂度的分析，一般是采用一些数学的方法，有的时候计算起来比较繁琐，对于形如T(n)=a*T(n/b)+f(n)的递归方程，主定理的使用，只需要比较f(n)与n^longba的量级即可，可以快捷地求出时间复杂度的量级，同时我们还得到了如何改进有关算法的一些提示，当n^longba起主导作用时，可以从减少子问题的个数和减小子问题的规模两个方面来考虑，而当f(n)起主导作用时，这时候要着重改善子问题分解组合时的处理方法。
算法常用的技术有分治法，贪心法，周游法，回朔法，动态规划法，分支定界法。
分治法的要领就是将一个规模较大的问题分解为若干个规模较小的子问题，这些子问题与原问题同类。其分治法的精髓就是分、治、合。利用分治法可以解决求第k小元素问题，其主要思想是当元素个数小于50时可以用堆排序找到，但是当元素个数大于50时，五分化中项的中项m,将数组分成三部分，比它大的，比它小的以及与它相等的。寻找最近点对的问题，采用分治法的方法是将点对平分到两个部分，分治求出左半部分的最近点对，右半部分的最近点对，再求出点位于左半和右半的最近点对，为了减少比较的次数用到了检查落到带状区域内的每一个点检查其后的4个点。
动态规划法与分治法类似，但是有着不同，动态规划法解决的问题通常具有以下几个特点：最有子结构和高度的重复性。动态规划的指导思想是：在做每一步决策时，列出各种可能的局部解，之后依据某种判定条件，舍弃那些肯定不能得到最优解的局部解。这样，在每一步都经过筛选，以每一步都是最优的来保证全局是最优的。筛选相当于最大限度地有效剪枝（从搜索角度看），效率会十分高。但它又不同于贪心法。贪心法只能做到局部最优，不能保证全局最优，因为有些问题不符合最优性原理。如果二维数组中有相当一部分元素在整个计算过程中都没有用到则可以采用动态规划的变形—备忘录的方法，比如说是求解LCS问题；其他的一些动态规划问题比如说矩阵连乘、最优二分搜索树无需计算的子问题只有少部分或全部都要计算，采用递推的方式比较好。
平摊分析收益手法（聚集方法，会计方法和势能方法）的引入，从整体上考虑时间复杂度而不是逐一的考虑每条指令的执行所需要的时间复杂度，聚集方法的关键在于找到如何分类，分别计算每类的耗费，再将耗费相加。会计方法的切入点一旦找到，计算起来非常方便，难点在于如何找到，而势能方法的切入角度比较好找：数据结构和势函数。
集合操作中的一些讲解给出了一些思想的启示，内部名外部名的使用，减少了改名的次数，更是惊叹于脱线MIN问题的解决思路，用集合名（数字）来表示删除i的E指令序号，其关键在于Find指令和Union指令的使用。为了求出各点在原先树的正确深度，又使时
间复杂度较小，需要采取具有路径压缩的Find指令，同时需要一些辅助手段来保证深度计算的正确性。Link指令在D森林中使用是为了减少时间复杂度2-3树上定义的一些操作都是在时间复杂度O（longn）时间完成的。需要掌握的有平衡树，字典，可并堆，可连接队列，以及2—3树的插入与删除。
随机算法中舍伍德算法不是万能的，有时也会遇到这样的情况，即所给的确定性算法无法直接改造成舍伍德型算法。此时可借助于随机预处理技术，不改变原有的确定性算法，仅对其输入进行随机洗牌，同样可收到舍伍德算法的效果。对于前面提到的寻找第K小元素的问题可以采用随机算法，只不过是将原来的中位数用随机数生成而已，体现了随机算法的优点。用Las Vegas，Monte Carlo，KMP算法判断某个字符串是不是另一个字符串的子串。对于素数的判定问题，主要讲解了miller和rabin的对于素数判定所做的贡献，miller-rabin的理论基础以及其主要思路。
计算模型一章丘奇图灵论题的内容以及提出的意义，还介绍了RAM,RASP，TM之间在两种耗费标准下的相互关系。与DTM不同的是，NDTM的每一步动作允许有若干个选择，对于给定的Q×Tk的一个元素（qi, a1, a2,?, ak），它的δ转移函数值不是对应于一个Q×(T×{L,R,S})k中的一个元素，而是对应于Q×(T×{L,R,S})k中的一个子集。 与DTM不同的是，DTM的 ID序列是线性的: ID0├ ID1├ ID2├ ┅├ IDm， 而NDTM的ID序列通常是用树来描述的 （因为在每个格局都可能有多个选择）。
最后算法给出P,NP,NP-C,NP-hard类语言和问题。NP-hard问题在P≠NP的假定之下，可以分成4类：有FPTAS（e.g.Knapsack），有PTAS而没有FPTAS（e.g. k-Knapsack），没有PTAS，但有绝对近似比为常数的近似算法(Bin-Packing)，没有绝对近似比为常数的近似算法(e.g. TSP)。然后介绍了伪多项式时间的算法，并且分析了动态规划法的背包问题。
学习心得：
1. 有些问题看似不可能寻找到解决的可能，花了很大的力气不一定可以得到很好的效果，有时候需要换一种角度再重新认识这个问题，尽力打破思维定势。
2. 在学习的过程中，若开始就看算法导论那本书，难免会觉得看不懂和迷茫，在老师的讲解结束时，这时候在仔细研读算法导论这本书，觉会觉得豁然开朗。
3. 在学习的过程中，诚然需要一个人的钻研，但有时需要走出一个人的世界，大家相互交流思想，开阔自己的思路，避免自己一个人走进死胡同或者处于一种狭隘的世界。
4. 把握学习的主动性，而不是被动的接受，否则会把自己置身于一种消极的状态下，每次的任务除了完成必要的要求以外，自己也要在此基础上扩张性的去学习，将学习的范围加大，这样会渐进的增加知识储备。
5. 在学习的过程中注重问题解决思路的培养
教学建议：
鉴于算法的抽象性，故在讲解的过程中可以结合一些具体的例子，举一些案例加以分析，侧重于问题解决的分析能力和解决能力的培养，如果可以应用于解决一些实际问题更好，这样可以更好地理解，达到触类旁通的效果。