动态规划解决背包问题


背包问题(Knapsack problem)是一种组合优化的NP完全(NP-Complete,NPC)问题。问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。NPC问题是没有多项式时间复杂度的解法的,但是利用动态规划,我们可以以伪多项式时间复杂度求解背包问题。
常规算法

梯度法、模式搜索法求解最优化问题


​最优化问题中常常需要求解目标函数的最大值或最小值,比如SVM支持向量机算法需要求解分类之间最短距离,神经网络中需要计算损失函数的最小值,分类树问题需要计算熵的最小或最大值等等。根据目标函数是否可求导将算法相应的分成两类,如果目标函数可求导常用梯度法,如果不能求导时一般选用模式搜索方式,一般来说梯度法较为快速且收敛较快,本篇还是会结合具体程序来讨论这两种方法
常规算法

Apriori算法、朴素贝叶斯分类


概率学分为两大学派分别是频率派也称为古典概率学和贝叶斯学派,频率派认为一个事件发生的频率等于其概率,这在许多场合下是正确的,并且根据大数定律可以描述为事件发生的频率依概率收敛于一个数值,这说明频率派认为概率是一个具体数值,比如扔一枚硬币在次数足够多的情况下硬币为正面的概率等于硬币为正面频率;而贝叶斯学派认为概率是一个分布,这个分布依赖于观察值而变化
常规算法

决策树(上)-ID3与C4.5


决策树是利用可视化的树实现数据的分类或回归,分类是指根据训练集、测试集实现有限类分类,比如银行根据收入、职业、婚姻状况、年龄等属性了解客户的贷款是否能按期偿还,其分类分为“是”或“否”;而回归则是为了得到具体数值,比如根据年龄、身高、性别得到目标数据的体重。可以看出决策树是一个监督学习,是利用已经标记的数据生成树的模型
常规算法

决策树(下)-CART树分类、回归、剪枝实现 


ID3,C4.5是多叉树,CART树是一个完全二叉树,CART树不仅能完成分类也能实现回归功能,所谓回归值目标是一个连续的数值类型,比如体重、身高、收入、价格等,在介绍ID3,C4.5其核心是熵的应用,而在实际应用中熵的运算会涉及大量的对数运算,其复杂度还是相当高的。CART树采用了一个与熵近似的概念'基尼系数',不同于熵来自于物理学,而基尼系数​来自于经济学范畴,原本是用来衡量收入是否平均,当基尼系数为0时代表收入平均,而大于0.5时代表贫富差异显著
常规算法

集成算法AdaBoosting原理


Bagging和Boosting是两种典型集成算法,Bagging的典型算法是随机森林,是利用多种模型进行分类,最后取一个平均值得到最终分类结果,Bagging而言多个模型可以是不同的,Bagging模型的基本原理是平均值可以减小方差,另外一个注意点是Bagging模型适用于小样本的情形,具体Bagging算法会在之后随机森林中详细介绍,本篇主要介绍Boosting算法,主要是选择Boosting中典型AdaBoosting,即提升的Boosting算法。
常规算法

梯度提升决策树-GBDT


GBDT全称梯度下降树,是一种迭代的决策树算法,GBDT可以发现多种有区分性的特征以及特征组合,在传统机器学习算法里面是对真实分布拟合的最好的几种算法之一,GBDT可用于分类也可以用于回归。
常规算法

Bagging集成算法


Bagging算法全程叫做Bootstrap aggregating,引导聚集算法。这个缩写含有袋子的意思,也可以理解为放回袋中算法,即每次随机抽取样本测试某一个模型的准确率,然后样本放回袋中下次可能还会被抽中测试另外一个模型,最后将多个模型取其平均值或利用投票原则得出一个综合的预测结果
常规算法

一维搜索


求解一元函数最优解的过程称为一维搜索,一维搜索常通过试探法和函数逼近法实现,一维搜索是解多维最优化问题的重要支柱,在很多非线性规划求解过程中需要使用一维搜索。
常规算法

KKT条件


Karush-Kuhn-Tucker (KKT)条件是非线性规划(nonlinear programming)最佳解的必要条件。KKT条件将Lagrange乘数法(Lagrange multipliers)所处理涉及等式的约束优化问题推广至不等式。在实际应用上,KKT条件(方程组)一般不存在代数解,许多优化算法可供数值计算选用。
常规算法

惩罚函数


惩罚函数主要用于将有约束的优化问题变为无约束的优化问题,转化为无约束的优化问题后即可不用考虑可行区方向的移动,惩罚函数可以分为外点法和内点法,其中外点法使用的较多,原因是外点法对初始点没有要求,而内点法要求初始点必须是可行点,且内点法只能解决不等式约束的优化问题。
常规算法

SVM支持向量机详解 


支持向量机(support vector machines, SVM)是一种二分类模型,它的基本模型是定义在特征空间上的间隔最大的线性分类器, 线性分类器也称为超平面,SVM的的学习策略就是超平面间隔最大化,从而具备很好的泛化功能,引入核函数后,将特征空间映射成高维度向量,SVM也可以实现对非线性数据分类。
常规算法

逻辑回归详解


逻辑回归又称logistic回归分析,是一种广义的线性回归分析模型,常用于数据挖掘,疾病自动诊断,经济预测等领域。逻辑回归从本质来说属于二分类问题。
常规算法

NMF非负矩阵分解


NMF是在矩阵中所有元素均为非负数约束条件之下的矩阵分解方法,一方面科学研究中的很多大规模数据的分析方法需要通过矩阵形式进行有效处理,而NMF思想则为人类处理大规模数据提供了一种新的途径;另一方面,NMF分解算法相较于传统的一些算法而言,具有实现上的简便性、分解形式和分解结果上的可解释性,以及占用存储空间少等诸多优点。通过矩阵分解,将描述问题的矩阵的维数进行削减,实现对大量的数据进行压缩和提取主要特征。
常规算法