机器学习 _ 基于距离的算法 KNN 与 K-Means 1. 距离的量度 1) 距离 距离的定义是一个宽泛的概念：只要满足非负、自反、三角不等式就可以称之为距离。其中非负是指任意两个相异点的距离为正；自反是 Dis(y,x)=Dis(x,y)；三角不等式是 Dis(x,z)<=Dis(x,y)+Dis(y,z) 2) 马氏距离（闵可夫斯基距离） 其中 d 是维数，p 是阶数，也称为 p 范数。 当 p=1 时，是曼哈顿距离 当 p=2 时，是欧氏距离 当 p→∞时，是切比雪夫距离 当 p=0 时，是海明距离 3) 欧氏距离 两点间的直线距离（一般用两条竖线||w||代表 w 的 2 范数）代入公式： 4) 曼哈顿距离（城市街区距离） 各坐标数值差的和，就像汽车只能行驶在横平竖直的街道上，代入公式： 5) 切比雪夫距离 各坐标数值差的最大值，当马氏距离的 p→∞时，最终的结果取决于距离最大的维度上的距离： Dis∞=maxj|xj-yj| 在二维的情况下：c=max(a,b) 6) 海明距离 L0 范数并不是一个真正的范数，它主要被用来度量向量中非零元素的个数。 7) 总 ...

机器学习 _SVM 支持向量机 1. 介绍 SVM 支持向量机属于广义的线性模型，先回忆一下线性模型：可依据平面（多维）或直线（一维/二维）来理解模型。简单地说，可用一条线将两类分开，如下图所示。 能将两类分开的直线不止一条（左图），我们希望找到离两组数据都最远的那条线（正中间那条线），以便更好地泛化。这就是右图中所示的极大边距分类器，一般把中间的直线称为决策面，把离决策面最近的那些点（训练实例）称为支持向量，也就是右图中紫圈中的点。 有时会遇到无法用直线分类的情况，如左图所示，但可以用圆环划分，右图展示了同样的数据，各个特征值取原始值的平方，变换到新的特征空间后，数据变成了线性可分。将数据从线性不可分转成线性可分的函数称为核函数，转换的方法称为核技巧（这里是取平方的操作，核函数一般将低维数据映射到高维）。由于需要把原始模型转换成线性模型，再进一步操作，我们叫它“广义线性模型”。 这就是一般意义上的支持向量机 SVM，它有两个重点：一个是考虑分类时的最大边距，另一个是使用核函数把线性不可分的变成线性可分的。 原理并不难，但具体实现涉及数学较多，如果嫌麻烦，请跳过“求解线性方程”部分 ...

机器学习 _ 统计模型之（一）贝叶斯公式 1. 贝叶斯法则   先举个例子：比如事件 X 是努力，事件 Y 是成功，能成功的基本都努力了（条件Ｙ成立时，Ｘ必然成立）；但是努力不一定都能成功（条件 X 成立时，Y 不是一定成立）。也就是说，X 与 Y 之间的关系不对等，但 X 和 Y 又确实有关系。贝叶斯法则就是用来描述这种关系的。   所有要是有人说“成功源于努力，所以努力必能成功”，那是心灵鸡汤。正确的说法是努力能把成功的可能性提高一点。 2. 贝叶斯公式   事件Ｘ发生的概率，称为边缘概率，记作 P(X)。   事件 Y 在事件 X 已经发生条件下的发生概率，称为条件概率，记为 P(Y|X)。   事件 X,Y 共同发生的概率称为联合概率，记为 P(XY) 或者 P(X,Y)。 有公式：  P(XY) = P(Y)P(X|Y)=P(X)P(Y|X)  P(Y|X)=P(XY)/P(X)=P(Y) P(X|Y)/P(X)   还用上面的例子，稍作调整：假设有 50% 的人努力了，即 P(X)=50%；有 20% 的人成功了 P(Y)=20%；且知道成功的人 75% 都努力了 P(X| ...

机器学习 _ 统计模型之（三）朴素贝叶斯 1. 条件独立假设 条件独立假设简单的说就是特征 x1 和 x2 没有关系，比如说兔子的特征中，尾巴短和爱吃萝卜这两个特征它们分别和兔子相关，但两特征彼此之间无关，不是说尾巴短的都爱吃萝卜。所以有 p(x2|x1)=p(x2)，即无论 x1 是什么，x2 的概率都不变。朴素贝叶斯就是以条件独立假设为基础的。 2. 概率的乘法 两个独立事件都发生的联合概率等于两个事件发生概率的乘积。 当 P(A) 与 P(B) 无关时，P(B)=P(B|A)，所以 P(A,B)=P(A)|P(B|A)=P(A)P(B) 比如：目标是判断该动物是不是兔子，有三个属性：长耳朵 P(A)=70%，短尾巴 P(B)=50%，爱吃萝卜 P(C)=60%，当三个条件都为真时: P(A,B,C)=P(A) * P(B) * P(C)=70% * 50% * 60% = 21%， 奇怪，三个条件都为真，结果概率却小了？概率小不小主要看跟谁比，再看看三个条件都不成立时： (1-P(A)) * (1-P(B)) * (1-P(C))=30% * 50% * 40%=6%， 对比这两 ...

机器学习 _ 统计模型之（二）贝叶斯网络 1. 贝叶斯网络   贝叶斯网络 (Bayesian network)，又称信念网络 (Belief Network)，或有向无环图模型。它用网络结构代表领域的基本因果知识。   贝叶斯网络中的节点表示命题（或随机变量），认为有依赖关系（或非条件独立）的命题用箭头来连接。   令 G = (I,E) 表示一个有向无环图 (DAG)，其中 I 代表图形中所有的节点的集合，而 E 代表有向连接线段的集合，且令 X = (Xi)，i ∈ I 为其有向无环图中的某一节点 i 所代表的命题，则节点 X 的联合概率可以表示成：   其中 Pa(i) 是 i 的父结点，是 i 的因。联合概率可由各自的局部条件概率分布相乘得出：  p(x1,…,xk)=p(xk|x1,….,xk-1)…p(x2|x1)p(x1)   这里顺便说一下朴素贝叶斯，由于其中各个变量 x 相互独立 p(x2|x1)=p(x2)，得出：  p(x1,…,xk)=p(xk)…p(x2)p(x1)   因此说朴素贝叶斯是贝叶斯网络的一种特殊情况。 2. 例程 (1) 功能  eBay 的 ...

机器学习 _ 用 SVD 奇异值分解给数据降维   本想把 PCA 和 SVD 写在一起，可上篇 PCA 还没写清楚就已经 4 页 word 了。再把 SVD 和特征工程的内容加上，实在是太长了，一下说太多也记不住，于是重开一篇。  SVD 用到的原理和 PCA 非常相似，就不再此赘述了，如果对特征值、特征向量相关问题不清楚请参见前篇 《机器学习_用PCA主成分分析给数据降维》 1. 原理   先回忆一下特征值分解：把向量 x 往特征向量方向上分解，然后每个方向上做伸缩，最后再把结果加起来即可。也可以理解为将向量 x 转到正交坐标系，在各个坐标轴的方向上缩放后，再转换回原来的坐标系。只有方阵才能做特征值分解，因此我们在 PCA 中不是直接对数据做分解，而是对参数的协方差矩阵做分解。   我们知道，任何矩阵都可以分解为三个矩阵的乘积 A=U * Sigma * VT，也就是奇异值分解．其中 U 和 VT 均是酉阵 (正交阵在复数域的推广)，而 Sigma 为增广对角阵。从直观上讲，U 和 VT 可视为旋转操作，Sigma 可视为缩放操作。因此奇异值分解的含义就是说，若将矩阵看做一个变换， ...

机器学习 _ 用 PCA 主成分分析给数据降维 有时我们的数据中包括很多属性，有些是没意义的，有些是重复的，有些组合后意义更明显。此时，我们需要简化属性节约算力，去噪，去冗余，求取更典型的属性，同时又希望不损失数据本身的意义。 主成分分析（Principal Component Analysis，PCA），是一种统计方法。通过正交变换将一组可能存在相关性的变量转换为一组线性不相关的变量，转换后的这组变量叫主成分。数据分析中常使用 PCA 给数据降维，它能在指定的损失范围内最大的简化属性。本篇将介绍 PCA 的原理，Python 实现及应用场景。 1 1. 特征值与特征向量 PCA 的核心算法是：协方差矩阵和特征值分解，先来看看特征值分解相关的知识点。 1.1 基 我们无时无刻不用到基，十进制就是以 10 为基底的描述，一个小时 60 分钟，60 就是基底，再说复杂一点，傅里叶变换中，余弦 (或正弦) 波是基底，小波变换中小波是基底，可以把它理解成一种基本的参照，比如 1 公斤，1 海里，1 升… 一个点在宇宙中本没有坐标，但只要定义了基，它就能被描述。任何的东西都可以借助基来描述。但不 ...

机器学习 _ 用树回归方法画股票趋势线   本篇的主题是分段线性拟合，也叫回归树，是一种集成算法，它同时使用了决策和线性回归的原理，其中有两点不太容易理解，一个是决策树中熵的概念，一个是线性拟合时求参数的公式为什么是由矩阵乘法实现的。如需详解，请见前篇： 《机器学习_决策树与信息熵》 《机器学习_最小二乘法，线性回归与逻辑回归》 1. 画出股票的趋势线   我们常在股票节目里看到这样的驱势线：   比如说平台突破就可以买入了，几千支股票，能不能用程序的方式筛选哪支突破了呢？需要解决的主要问题是：怎么判断一段时间内股票的涨/跌/横盘，以及一段趋势的起止点和角度呢？   这里我们使用分段线性拟合，图中蓝色的点是某支股票每日的收盘价，红色的直线为程序画出的趋势线。稍做修改，还可以轻松地画出每段趋势所在的箱体，阻力线和支撑线，以及判断此前一般时间的趋势。下面我们就来看看原理和具体算法。 2. 线性回归   先看看线性回归（Linear regression），线性回归是利用数理统计中回归分析，来确定两种或两种以上变量间相互依赖的定量关系的一种统计分析方法。简单地说，二维中就是画一条直线，让 ...

机器学习 _ 最小二乘法，线性回归与逻辑回归 1. 线性回归   线性回归是利用数理统计中回归分析，来确定两种或两种以上变量间相互依赖的定量关系的一种统计分析方法。   直观地说，在二维情况下，已知一些点的 X,Y 坐标，统计条件 X 与结果 Y 的关系，画一条直线，让直线离所有点都尽量地近（距离之和最小），用直线抽象地表达这些点，然后对新的 X 预测新的Ｙ。具体实现一般使用最小二乘法。 线性回归   线性回归的优点是理解和计算都相对简单，缺点是无法解决非线性问题。 2. 最小二乘法 1) 原理   最小二乘法（ordinary least squares，简称 OLS）的核心就是保证所有数据偏差的平方和最小（“平方”的在古时侯的称谓为“二乘”）。   我们用直线拟合一些点，直线方程是 y’=ax+b，每点偏差是 y-y’，其中 y 是实际值，y’是估计值。sum((y-y’)^2) 最小时，直线拟合最好。上试代入 y’，可得 M=sum((y-(ax+b))^2)，对它求导取极值。此时，x,y 是已知的，未知的是 a 和 b，所以分别求 M 对 a 和 b 的偏导，解出的 a, ...

机器学习 _ 决策树与信息熵 1. 决策树   决策树 (Decision Tree）是一种预测模型；它是通过一系列的判断达到决策的方法。下面是一个判断是否买房的例子，一共 15 个实例，有 Age, Has_job, Own_house, Credit_rating 四个属性，树的各个分叉是对属性的判断，叶子是各分枝的实例个数。 决策树   这是个很简单的例子，只用了两层，每个叶子节点就得到了一致的结果（如 2/2），如果不一致，则会使用其它属性递归地划分，直到属性用完，或分支下得到一致的结果，或者满足一定停止条件。对于有歧义的叶子节点，一般用多数表决法。   决策树的优点是复杂度低，输出结果直观，对中间值缺失不敏感；缺点是可能过拟合，有时用到剪枝的方法避免过拟合。   决策树的原理看起来非常简单，但在属性值非常多，实例也非常多的情况下，计算量是庞大的，我们需要采用一些优化算法：先判断哪些属性会带来明显的差异，于是引出了信息量的问题。 2. 信息量 意外越大，越不可能发生，概率就越小，信息量也就越大，也就是信息越多。比如说“今天肯定会天黑”，实现概率 100%，说了和没说差不多 ...