机器学习基础算法理解和总结
KNN算法
理解
KNN其实是最好理解的算法之一,其实就是依次和空间中的每个点进行距离比较,取距离最近的N个点,看这N个点的类别,那么要判断的点的类别就是这N个点中类别占比最大的点的类别了(投票表决),这就是暴力的KNN方法。还有一种是通过构造kd树的方式实现。kd树算法并没有从一开始就去计算测试样本和训练样本之间的距离,而是先去训练构造一个kd树,然后用kd树对测试样本进行预测(平衡二叉树)。
实现步骤
对于分类问题,实现步骤为
- 不需要训练,需要提供超参数k
- 取样本空间D中离测试样本最近的k个点
- 投票决定测试样本的类别
对于回归问题,实现步骤为
- 不需要训练,需要提供超参数k
- 取样本空间D中离测试样本最近的k个点
- 取k点的均值为预测值
补充
关于距离:
- 欧式距离
- Mahalanobis距离:给定向量x、y以及矩阵S,其定义为
当S为单位矩阵的时候,其距离描述的就是欧式距离,为了求出矩阵S,引出了距离度量学习。(S也可以由样本的协方差矩阵得到,但准确率可能不一样)。 - Bhatlacharyya距离:
,其中 xi和yi为取某一值的概率。
代码实验
# -*- coding: utf-8 -*-
"""
Created on Sun Oct 7 13:24:30 2018
@author: ar45
"""
from sklearn.model_selection import train_test_split
from sklearn import datasets
from sklearn.neighbors import KNeighborsClassifier
import numpy as np
iris = datasets.load_iris()#加载训练集
X = iris.data#数据集
y = iris.target#结果
X_train,X_test,y_train,y_test = train_test_split(X,y,test_size = 0.3)#测试集和训练集划分
#print(X_train[1:3,:])
knn = KNeighborsClassifier(4,weight="uniform")
#加载分类器,让k=4,分配权重方式为uniform,也就是权重相等,weights = 'distance'表示的是权重与距离成反比
knn.fit(X_train,y_train)# 开始训练
result = knn.predict(X_test)# 在测试集上预测结果
print(np.mean(result==y_test))#对比测试集的结果和预测结果,得到准确率
'''
输出结果
0.9777777777777777
'''
决策树
理解
决策树其实是基于信息论的算法,通过递归实现训练决策的节点。我只学习了ID3、C4.5和CART算法,所以会记录这三种算法,刚学了概率论,对这里的理解更深了。
先验知识
ID3算法
信息熵
就这么一个公式,其中pi代表是结果的概率。
信息增益
定义条件熵为:
那么前者信息熵与条件熵的差值就是信息增益,表征的是信息的该变量。
C4.5算法
信息增益率
用信息增益率来表征信息变化的多少
CART算法
Gini指数
其中pk指的是结果中第k个类别的概率。公式表征的是不纯度大小,越纯Gini指数越小。
这里是针对离散量的也就是分类问题的loss度量公式,如果是回归问题就要用均方误差来衡量了。具体的不讨论。
学习过程
- 先用样本构造根节点,找到用哪个label怎么分,使得信息增益或者不纯度更小(为不纯度的时候,得到分别的不纯度,也就是左右子树不纯度按照样本数量权重求和),并设计阈值,小于阈值并且最小的分裂方式就最为最佳分裂方式,否则就不分裂。
- 将样本集划分为左右子树,分别将左右叶节点设为本节点在训练样本中出现最大的子类。
- 递归进行分裂,直到不纯度都小于阈值停止迭代,训练完成。
剪枝
决策树算法很容易再训练集上过拟合,所以我们采用剪枝的方法来防止其过拟合。
假设我们已经完成了上面的学习过程生成了一颗决策树,下面我们将对其进行剪枝操作:
- 在上面的决策树基础上生成所有可能的剪枝后的决策树(说白了就是一个一个剪掉或者留下这样试),从叶节点开始自下而上进行考察。
- 通过交叉验证的方法在数据集上进行验证,看看剪枝后的该节点处验证准确率是否有提升
- 如果有提升,则保留剪枝后的树;如果有下降,则保留原节点。循环对所有节点进行上面操作。
预测过程
很好理解,就是树状分类器满足一定条件往哪个方向分,相当于if then的结构。
代码实验
# -*- coding: utf-8 -*-
"""
Created on Sun Oct 7 13:24:30 2018
@author: ar45
"""
from sklearn.model_selection import train_test_split
from sklearn import datasets
from sklearn import tree
import numpy as np
import graphviz
digits = datasets.load_digits()
X = digits.data
y = digits.target
X_train,X_test,y_train,y_test = train_test_split(X,y,test_size = 0.3)
cls = tree.DecisionTreeClassifier()
cls.fit(X_train,y_train)
r = cls.predict(X_test)
print(np.mean(r==y_test))
dot_data = tree.export_graphviz(cls,out_file="e:/A.dot")#输出到A.dot
'''
输出结果:
8462962962962963
'''
可视化代码:
dot -Tpdf a.dot -o output.pdf
可视化结果:
朴素贝叶斯
朴素贝叶斯主要是利用贝叶斯公式通过特征进行预测的方法,其假设是各个特征之间是相互独立的。
朴素贝叶斯利用的贝叶斯公式为
,其中条件概率公式为
实现步骤
1. 求先验概率
利用极大似然估计法证明和求解(离散数据利用频数处以总数直接求频率),连续数据一般假设服从正态分布,求出u和σ,并且加入平滑项(拉普拉斯平滑),保证在某些类别在样本中没出现的时候,公式中概率不为0.
2. 朴素贝叶斯推断过程
朴素贝叶斯推断是根据后验概率公式,分别求各类的推断的概率,最后投票选取概率最大的类别进行输出。
3.代码实验
# -*- coding: utf-8 -*-
"""
Created on Sun Oct 7 13:24:30 2018
@author: ar45
"""
from sklearn.model_selection import train_test_split
from sklearn import datasets
from sklearn.naive_bayes import GaussianNB
import numpy as np
wine = datasets.load_wine()
X = wine.data
y = wine.target
X_train,X_test,y_train,y_test = train_test_split(X,y,test_size = 0.3)
cls = GaussianNB()
cls.fit(X_train,y_train)
r = cls.predict(X_test)
print(np.mean(r==y_test))
'''
这里假设概率服从的是高斯分布。
输出结果:
0.9629629629629629
'''
Logistic回归
理解
logistic 回归,虽然名字里有 “回归” 二字,但实际上是解决分类问题的一类线性模型。
逻辑函数
,可以将结果映射到(0,1)的区间上去,相当于输出了一个概率值(概率映射)。
公式过程理解
- 对n个label下的样本集,用W矩阵表示学习的权重,用wTx矩阵相乘之后可以得到每个样本对应的估计值,将逻辑函数中的x替换成wTx + b,结果就被映射成了概率。
- 由于结果被映射成了一个概率值,我们就可以通过极大似然估计的方法,使得在每个样本集的条件下对应真实输出的概率最大,求得此时的参数估计W。
- 由于我们将h(x)的结果映射成了P(y=1|x)的概率值,y的取值不是0就是1,那就简单了,可以写成这样的形式:
,其表示的是每个样本对应每个类别的概率。 - 由于样本之间相互独立,样本训练集的似然函数为
,求他的对数似然函数的最大值,转化为求其相反数的最小值,就又转化为了一个凸优化问题。 - 对于凸优化问题,我们就可以用传统的梯度下降法来求解这个问题了。
代码实验
# -*- coding: utf-8 -*-
"""
Created on Sun Oct 7 13:24:30 2018
@author: ar45
"""
from sklearn.model_selection import train_test_split
from sklearn import datasets
from sklearn.linear_model.logistic import LogisticRegression
import numpy as np
iris = datasets.load_iris()
X = iris.data
y = iris.target
X_train,X_test,y_train,y_test = train_test_split(X,y,test_size = 0.3)
cls = LogisticRegression()
cls.fit(X_train,y_train)
print(cls.score(X_test,y_test))
# 代码都是一样的。。。
'''
0.9777777777777777
'''