动态规划解决背包问题

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

隐马尔科夫链HMM详解

隐马尔科夫链HMM广泛用于语音识别，中文分词等序列标注领域等领域，通过平稳性设定，引入随机过程在时间维度上独立性，HMM一种生成式模型，具有较好拟合性。隐马尔科夫链一般涉及评估问题、解码问题、学习问题三种类型的解决方案。
常规算法

利用均匀分布生成其他分布随机数、蒙特卡罗方法原理

需要利用计算机生成指定连续分布的随机数，比如指数分布、正态分布、伽马分布等，一般我们会用相同数量的[0,1]之间均匀分布的随机数去生成其他形式连续分布随机量，而针对生成正态随机数我们有中心极限定理的存在，可以更方便的生成。
数学建模

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

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

Apriori算法、朴素贝叶斯分类

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

利用线性空间、子空间实现线性回归问题

线性回归有许多建模方法可以解决，比如最小二乘法、神经网络等，本篇介绍基于线性代数利用向量、空间概念快速求解线性回归问题，掌握本章知识点后可以利用有些结论解决如函数逼近问题。
数学建模

多项式逼近连续函数

拓展子空间的概念，空间的元素是函数称之为函数空间，这个空间里面有我们熟悉的各种函数以及这些函数的线性组合。函数空间里的子空间是一系列性质相似的函数集合，比如三角函数可以组成一个子空间，由数学分析知道利用三角函数可以实现傅里叶变换，将其他函数表示为三角函数线性组合成的级数形式。本文中选取的空间是一个多项式空间，即其空间里基是x0,x1,x2,x3,...xn...等多项式，需要将其他函数投影到这个子空间里，其运用的知识还是来自于线性代数
数学建模

函数梯度与隐函数

梯度是函数的定义域中的一个向量，该向量指向的方向是函数值变大的最快方向，相应的梯度的反方向则是函数变小的最快方向，与梯度配合使用的是函数的等值线，从几何角度来说，梯度是两条等值线之间指向最短距离的一条向量，最优化问题中常需要使用梯度来求函数的最值，从算法角度来说深刻理解梯度有着重要的意义
数学建模

傅里叶变换

傅立叶变换，表示能将满足一定条件的某个函数表示成三角函数（正弦和/或余弦函数）或者它们的积分的线性组合，傅里叶变换的核心是从时域到频域的变换，信号处理、偏微分方程、热力学、概率统计等领域都有重要的应用。
数学建模

基变换、线性变换与pca主成分分析

pca全称是Principle component analysis，译为主成分分析，比如我们描述一个人信息时会用体重、身高、发型、爱好、收入、职业等信息，而将一个人按性别分类时体重、身高、发型基本可以确定一个人是男是女。例如我们说一个女孩子是假小子，可能这个女孩有一个板寸头，身材很高，我们从众多属性中选取一两个，而无需其他属性作为参考就确定了一个分类，pca就是这样一个处理数据常用手段，即利用较少的属性对一组数据产生分类，很明显pca是一个降维的数据处理手段
数学建模

信息熵、交叉熵、相对熵原理与softmax函数的应用

信息熵在人工智能领域有着举足轻重的作用，尤其在分类的算法中，可利用其特性设计损失函数推导出最优数学模型；softmax函数是一种处理数据手段，一般会出现在模型，比如各种神经网络的最后一层，经过softmax函数处理后即可把任意数据（一般表现为向量） 处理成概率形式，从而可以用交叉熵的方法得到与真实分布之间损失，进而优化模型参数。
数学建模

决策树(上)-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可用于分类也可以用于回归。
常规算法

EM期望最大化算法

EM(Expectation-maximization algorithm)翻译为期望最大化算法，是数据挖掘的十大算法之一，主要解决的是当含有隐含变量时，如何利用最大似然法求解未知参数。现实中会遇到多个数据混杂在一起，这个多个类别数据虽然是一个概率分布，但数学期望或方差不同，每次取得一个数据时也不知道这个数据是哪个类别下，每个数据属于哪个类别的信息是一个隐含变量，遇到这种情况时我们不能直接用最大似然法。EM算法中文名称中就已经说明了算法过程，即先求出数学期望的函数，然后求其最大值，逐步求出未知参数
数学建模

Bagging集成算法

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

单纯形法

单纯形法是线性规划问题数值求解的流行技术，转轴操作是单纯形法中的核心操作，其作用是将一个基变量与一个非基变量进行互换，可以将转轴操作理解为从一个凸集上的一个顶点走向另一个顶点，单纯形法的基本思想是先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解，再鉴别；若仍不是，则再转换，按此重复进行。
数学建模

一维搜索

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

KKT条件

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