知识点5：分类的评判指标
准确率和召回率广泛用于信息检索和统计分类领域
1）准确率（precision rate）：提取出的正确信息条数/提取出的信息条数
2）召回率（recall rate）：提取出的正确信息条数/样本中的信息条数
ROC和AUC是评价分类器的指标
3）ROC曲线：
ROC关注两个指标
True Positive Rate ( TPR，真正率 ) = TP / [ TP + FN] ，TPR代表预测为正实际也为正占总正实例的比例
False Positive Rate( FPR，假正率 ) = FP / [ FP + TN] ，FPR代表预测为正但实际为负占总负实例的比例
在ROC 空间中，每个点的横坐标是FPR，纵坐标是TPR
4）AUC：AUC（Area Under Curve）
被定义为ROC曲线下的面积，显然这个面积的数值不会大于1。又由于ROC曲线一般都处于y=x这条直线的上方，所以AUC的取值范围在0.5和1之间。使用AUC值作为评价标准是因为很多时候ROC曲线并不能清晰的说明哪个分类器的效果更好，而AUC作为数值可以直观的评价分类器的好坏，值越大越好。
5）如何避免过拟合？
过拟合表现在训练数据上的误差非常小，而在测试数据上误差反而增大。其原因一般是模型过于复杂，过分得去拟合数据的噪声和outliers。
常见的解决办法是正则化是：增大数据集，正则化
正则化方法是指在进行目标函数或代价函数优化时，在目标函数或代价函数后面加上一个正则项，一般有L1正则与L2正则等。规则化项的引入，在训练（最小化cost）的过程中，当某一维的特征所对应的权重过大时，而此时模型的预测和真实数据之间距离很小，通过规则化项就可以使整体的cost取较大的值，从而在训练的过程中避免了去选择那些某一维（或几维）特征的权重过大的情况，即过分依赖某一维（或几维）的特征。
L1正则与L2正则区别：
L1：计算绝对值之和，用以产生稀疏性（使参数矩阵中大部分元素变为0），因为它是L0范式的一个最优凸近似，容易优化求解；
L2：计算平方和再开根号，L2范数更多是防止过拟合，并且让优化求解变得稳定很快速；
所以优先使用L2 norm是比较好的选择。
知识点6：二叉树（前、中、后遍历）
（这里的前中后是指的根节点的遍历次序）
1）前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树；
2）中序遍历（LDR），首先遍历左子树，然后访问根结点，最后遍历右子树；
3）后序遍历（LRD），首先遍历左子树，然后访问遍历右子树，最后访问根结点。
知识点7：几种基本排序算法
1）冒泡排序（Bubble Sort）
冒泡排序方法是最简单的排序方法。这种方法的基本思想是，将待排序的元素看作是竖着排列的“气泡”，较小的元素比较轻，从而要往上浮。
冒泡排序是稳定的。算法时间复杂度是O(n^2)。
2）插入排序（Insertion Sort）
插入排序的基本思想是，经过i-1遍处理后，L[1..i-1]己排好序。第i遍处理仅将L[i]插入L[1..i-1]的适当位置，使得L[1..i]又是排好序的序列。
直接插入排序是稳定的。算法时间复杂度是O(n^2)。
3）堆排序
堆排序是一种树形选择排序，在排序过程中，将A[n]看成是完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。
堆排序是不稳定的。算法时间复杂度O(nlog n)。
4）快速排序
快速排序是对冒泡排序的一种本质改进。快速排序通过一趟扫描，就能确保某个数（以它为基准点吧）的左边各数都比它小，右边各数都比它大。
快速排序是不稳定的。最理想情况算法时间复杂度O(nlog2n)，最坏O(n ^2)。
将此文发送给你的好友，或分享到朋友圈，和小伙伴一起成长，秒变数据分析高手！
QQ 交流群：338490777，期待你的加入。实时互动，百人在线讨论。
【长按】或【扫描】二维码加入该群。
