KNN分类
K-近邻算法，把数据集分为训练数据集和测试数据集，用训练数据集导入KNN，对于一个数据向量，计算此数据跟所有训练集的距离，取出K个距离最小的训练集，在这k个数据中占比最多的label类别为输出结果。把测试集的数据计算上述的过程，并比较结果，得出测试结果
优点
精度高/对异常值不敏感/无数据输入假定
缺点
计算复杂度高/空间复杂度高
适用数据范围
数值型和标称型
归一化
公式：newValue = (oldValue-min)/(max-min)
由于每个特征的取值范围都不一样，导致范围大的特征会让KNN更偏重于这些特征，为了让每个特征尽量的公平，可以对每个特征进行归一化处理
ID3决策树
对于训练集的每个特征，计算它们的不确定性（使用香农信息熵），对他们的不确定性排序，把越能确定结果的排在树的顶部，把越不能确定的特征放在树的底部，递归上述过程，就得到了一颗决策树
ML-decisionTree
香农信息熵
ml-loga
信息量（不确定性）：
l(x)=p(x)*log(p(x))
从公式可以看到p(x)越接近0.5，代表越不能确定，l(x)会以指数形式越大，p(x)越接近0或1，代表越确定，l(x)越小
信息量期望
ml-decisionTree-ent
信息增量（ID3算法）
I = H(D) - x*H(D|x)
例如15个样本D，其中9个输出为1,6个输出为0。样本中有特征A，取值为A1，A2，A3。在取值为A1的样本的输出中，有3个输出为1，2个输出为0，取值为A2的样本中，2个输出为1，3个输出为0，在取值为A3的样本中，4个输出为1，1个输出为0
ml-id3
信息增量的意义是，选取一个特征分类，选完后，信息不确定性减少得最多的作为此节点的特征选取。是一种贪心算法
优点
计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据
缺点
无法处理连续特征
没考虑过拟合问题
没考虑缺失值问题
偏重于类别多的特征
每个特征只参与一次分割
熵的计算比较复杂
适用数据类型
数值型和标称型
朴素贝叶斯
优点
在数据少的情况下仍然有效，可以处理多类别问题
缺点
对于输入数据的准备方式较为敏感
适用数据类型
标称型数据
公式
p(c|w) = p(w|c)*p(c)/p(w)
有若干个特征w，有目标结果c，有一组训练集合（从w到c的映射），p(c)为训练集结果c的占比，p(w)=p(w1)*p(w2)...为训练集特征w的出现的占比，p(w|c)=p(w1|c)*p(w2|c)....，分别对特征w1/w2...计算预定结果c的情况下的占比。p(c|w)为当出现特征w向量，出现c结果的概率，
所以公式为
p(c|w1,w2...wn)=p(w1|c)*p(w2|c)...p(wn|c)*p(c)/p(w1)*p(w2)....*p(wn)
由于p(wi)有可能为0或者非常小，导致乘积发生下溢，所以采用对数的方式计算
log(p(c|w))=log(p(w|c))+log(p(c))-log(p(w))
通过计算p(c1|w)和p(c2|w)比较两个的值，最大那个概率为预测的结果c
Logistic回归
ml-logistc
优点
计算代价不高，易于理解和实现
缺点
容易欠拟合，分类精度可能不高
适用数据类型
数值型和标称型数据
判断0-1分类函数
-
海 维 塞 德 阶 跃 函数
在跳跃点从0瞬间到1，导致导数为无穷大，会令优化函数求导非常难处理
-
Sigmoid函数
ml-sigmoid
ml-sigmoid-pic
z = w0*x0 + w1*x1 ... + wn*xn
x为特征输入，w为系数，是训练的对象
梯度上升法
x = x + a * f(x,y)'/x'
y = x + a * f(x,y)'/y'
a为学习率，通过逐步修改x,y的值，让f(x,y)不断增大逼近局部最大值
梯度下降法
x = x - a * f(x,y)'/x'
y = x - a * f(x,y)'/y'
a为学习率，通过逐步修改x,y的值，让f(x,y)不断减少逼近局部最小值
随机梯度上升/下降算法
由于学习的样本巨大，导致一次迭代无法把所有的训练集在内存中计算，所以通过随机取样的方式，加载一部分数据进行梯度计算
损失函数
P(y=1|x,w) = sigmoid(z)
P(y=0|x,w) = 1- sigmoid(z)
P(y|x,w) = (sigmoid(z)^y) * (1 - sigmoid(z))^(1-y)
log(P(y|x,w)) = log((sigmoid(z)^y) * (1 - sigmoid(z))^(1-y))
= y*log(sigmoid(z)) + (1-y)*log(1 - sigmoid(z))
要让P(y|x,w)逼近1，则取最大值
L(w) = -log(P(y|x, w))
L(w) = -(log(P(y1|x1, w)) + log(P(y2|x2,w)... + log(P(ym|xm,w)))/m
m为样本数
损失函数为L(w)，逼近0，取最小值
使用梯度下降算法，对L(w)进行迭代运算，最终得出
学习率的优化
a = 4/(1.0+ i) + 0.01
i为迭代次数，随着迭代次数的增加，学习率会不断变小，这样有利于在接近局部最值时，收敛的更谨慎
分割线
sigmoid(z)的分割线是0.5，那么就是z=0，而z = w1*x1+w2*x2 + b = 0
所以分割线是一条直线
支持向量机SVM
Adaboost
公式
ml-adaboost
w代表权重，exp(-yF(x))为损失值，当学习函数多次判断x失败时，w会越来越大，相反多次判断x为正确时，w会越来越小，这会使得越后面的迭代G(x)的学习会越看重失败的x，而忽略正确的x，w等于前一个权重乘以损失。
y=1或者-1
为什么Loss对a求导为0：因为Loss的曲线是U性的，所以Loss求最小值，导数为0
为什么每增加一个G(x)会让Loss递减：因为Loss(x) = exp(-y(F(x) + aG(x)))，让a=0，则代表Loss为上一次迭代的Loss，而a是等于导数为0的值，代表当a不为0时，Loss取更小的值。
简述
每次新增的迭代会对上一轮判断失败的x增强学习，通过权重控制
最终汇总每个学习G，给予响应的权重，最终得出最后的判断
单层决策树
假设有n个特征，程序会遍历所有的特征，并从特征的最小值开始，并以步长step，去遍历，并计算特征的lt，rt左右损失值，并选取最小损失值得一个点，把数据以一条直线切开左右两边，例如x=4.5。
非均衡数据
ml-data
正确率=真正例/（真正例+伪正例）
召回率=真正例/（真正例+伪反例）
ROC
ml-roc
真阳率=真正例/（真正例+伪正例）
假阳率=伪正例/（伪正例+真反例）
ROC的目的，是让矩阵最大化对角线的值，最小化非对角线上的值
线性回归
y=w*x+b
损失函数
Z = (y-wx)^2
对w求导并导数等于0取最小值，等到w的值
w=(XT*X)^-1*XT*y
对X和X转置的乘积求逆有可能无解
可以使用递归下降算法求近似值
或者使用岭回归
w=(XT*X+u*I)^-1*XT*y
I为一个在对角线全是1，其他全是0的举证，u为输入小数
这样通过加一个矩阵，就保证了求逆肯定有解
缺点
- 数据集必须线性可分
- 全量数据集计算
决策树之CART算法
支持分类树和回归树
分类树采用GINI值作为节点分裂的依据
回归树采用MSE均方误差作为节点分裂依据
思想
以二叉树的结果来组织决策，每个节点选取最优的一个特征把数据集一分为二，两个子节点分别处理分裂后的数据集，叶子节点为预测节点。
回归树
MSE计算公式
mean= sum(target)/totalNumber
mse = sum((target-mean)^2)
分裂依据
对每个特征按小到大排序，遍历数据集的每个特征的每个值，把数据集一分为二计算以下值，并取最小值
计算左孩子left_mse
计算右孩子right_mse
切割后的mse=left_mse+right_mse
选择最小的切割
终止条件
超参数max_depth和min_leaf_mse
- depth>=max_depth
- current_mse < min_leaf_mse
- 没有特征可以分裂
叶子节点取值
mean
leaf_value = mean(target)
ml-cart-mean
线性回归
leaf_value = w*x+b
ml-cart-line
裁剪
分类树
采用基尼系数代替信息增量比来作为树分裂的依据，由于基尼系数的图像跟信息量相似，而且计算量更小
相对于ID3决策树，CART分类树采用二叉树来分裂特征，而不是多叉树
ml-gini
公式
Gini(p) = sum(p*(1-p))
分裂后：
Gini(after_p) = sample1_p*gini(sample1) + sample2_p*gini(sample2)
取Gini(after_p)最小值
叶子节点
取概率最大的类别为预测类别
决策树小结
优点
- 简单直观
- 基本不需要预处理，不需要归一化和处理缺失值
- 预测复杂度为O(logm)
- 可以处理连续值和离散值
- 可以回归和分类
- 交叉验证减枝，提高泛化能力
- 对异常点容错能力好，健壮性高
缺点
- 容易过拟合，导致泛化能力不高，可以通过设置节点最少样本数和限制决策树深度来改进
- 决策树会因为样本发生一点改动，而导致树的结果剧烈变化，可以通过集成学习来改善
- 有些复杂关系很难学习，例如异或。可以用神经网络分类来解决
- 如果某些样本比例大，生成树会偏向这些特征，可以通过调节样本权重来改善
k-means算法
- 有数据集
- 定义超参数k，代表把数据集分为k类
- 在数据集上随机打k个点
- 对于每个数据点计算跟这k个点的距离
- 取最近的一个点
- 然后这个点的位置为mean(选取此点为中心的数据集)
- go to step 4
- 最终这k个点会到达一个局部最优值
优点
易于实现
缺点
可能收敛于局部最小值，大规模数据集收敛慢
距离计算
曼哈顿距离
z = sum(|x2-x1|)
欧几里得距离
z = (sum((x2-x1)2))0.5
切比雪夫距离
z =max(|x2-x1|,....)
闵尔科夫斯基距离
z = (sum((x2-x1)p))(1/p)
马氏距离
汉明距离
z = sum(x2<>x1?1: 0)
余弦相似度
cos(O) = A*B/|A|*|B|
杰卡德距离
杰卡德相似系数用于度量两个集合之间的相似性，定义为两个集合交集集合元素的个数比上并集集合元素的个数
Z = A交B/A并B
皮尔森相关系数
是两个变量线性相关程度的统计量，皮尔森相关系数的绝对值越大则相关性越强
z = sum((x-mean)*(y-mean))/(var(x)*n)2*(var(y)*n)2
编辑距离
指两个字符串，需要编辑多少次，需要编辑一个字符串多少次，可以转变成另外一个字符串
K-L散度
D(P||Q) = P(i)log(P(i)/Q(i))
解决收敛局部最小
原因
由于初始k个点随机的，导致某些族类的数据集到中心点的距离总和比其他族类的距离要大很多，如图
ml-k-means
二分k-means
- 设置超参数k
- 把数据集归为一族类
- 计算均值，确定一个中心点
- 计算所有族类的数据集到中心点的距离总和，选择最大的一个族类，对族类进行2-means的计算，并最终收敛为2类
- go to step 4 直到把族类的总数为k
Apriori
ml-apriori
- 有一组物品数据
- 统计所有单个物品出现的次数，并过滤掉低于阈值的物品
- 由过滤后的单个物品进行排列组合，组成两个物品，并统计此组合出现的次数，并过滤掉次数低于阈值的组合
- 组成3个物品，以此类推
- 计算P(ABC|AB) = AB出现的次数/ABC出现的次数，得出如果用户购买了AB，那么再买C的可能
FP-Growth
Aprior的算法可以看出，在计算频繁项（出现的次数）非常慢，每次计算一个组合都需要遍历所有的数据集，如果数据量大，会导致算法相当低效
FP-Growth是一种计算频繁项的算法，可以有效的降低计算的复杂度，然后再结合P(ABC|AB) = AB出现的次数/ABC出现的次数，计算出结果
ml-fp-growth
- 第一遍计算出每个物品的频繁度
- 按照频繁度从大到小排序
- 过滤频繁度小于阈值的单个物品
- 对数据集的每行记录通过频繁度按高到低排序
- 遍历数据集，构建FP数
ml-fp-pre-data
ml-fp-afterdata
网友评论