2018-10-17 00:18:58 qq_39736559 阅读数 311
  • 机器学习--线性回归数学推导视频教学

    线性回归数学推导是机器学习的基石,是人工智能的算法基础, 可以被广泛的应用在在工作和学习。本节课就带领同学们从零开始一步一步的推导线性回归。课程内容包括矩阵转换、误差值分析、似然函数、小二乘、结果推导。 任务作业: 设计并实现一个三层架构的员工管理系统。要求: 1、数据库及其表自行设计,遵循数据库及表设计的一般命名规则 2、要求有管理员的登录功能及对员工信息的增删改查 3、功能的实现严格采用三层架构的设计框架,注意命名的一般规范 4、采用B/S架构,界面大方美观 5、思考下三层架构与MVC框架有什么区别 (温馨提示: 注意 作业需写在CSDN博客中,请把作业链接贴在评论区,老师会定期逐个批改~~)

    3970 人正在学习 去看看 陆永剑

KNN算法概述

KNN(k-nearest neighbor)算法属于机器学习中的有监督分类算法,主要用于分类,是最简单的机器学习算法之一顾名思义,其算法主体思想就是根据距离相近的邻居类别,来判定自己的所属类别。

KNN算法思路

1、计算测试对象与训练集中所有对象的距离,一般采用欧式距离。
2、找出与计算对象距离最近的K个对象,作为测试对象的邻居;
3、找出这K个对象中出现频率最高的类别,该类别即为测试对象的所属类别。

一个简单的例子

在二维坐标轴中,有四个点(即训练集),分别是a1(1,1),a2(1,2),b1(3,3),b2(3,4)。其中a1,a2为A类,b1,b2为B类。
在这里插入图片描述
现在,有一个新的点c(2,1)(即测试对象),我们想要判断这个点属于A类还是B类。
在这里插入图片描述
此时我们可以采用KNN算法进行求解
1、计算测试对象与训练集中所有对象的距离,即点c与a1,a2,b1,b2的距离
在这里插入图片描述
2、将计算出来的距离进行升序排序

序号 点标签 点类别 与c点距离
1 a1 A 1.0
2 a2 A 1.4
3 b1 B 2.2
4 b2 B 3.1

3、找出与计算对象距离最近的K个对象
一般情况下K的值取3(即取K=3)

序号 点标签 点类别 与c点距离
1 a1 A 1.0
2 a2 A 1.4
3 b1 B 2.2

4、找出这K个对象中出现频率最高的类别,测试对象便属于该类别
由上表可知,在所取的K对象中,f(A)=2/3,f(B)=1/3,频率最高的为A类,即点c属于A类。

手写数字识别系统

下面我们将构造使用K邻近分类器(即KNN算法)搭建的手写数字识别系统,并用测试集测试分类正确率
1、准备数据
首先下载手写数字数据集,数据集分为训练集(trainingDigits)和测试集(testDigits),训练集中有100个样本,测试集中有50个样本,每个样本的格式如下图所示
在这里插入图片描述
2、载入数据
为了便于计算图像与图像间的欧式距离,我们需要将图像格式化为一个向量。由于图像为32x32的二进制图像,所以我们需要将之转化为1x1024的向量。为了便于操作,我们首先编写Load_Data函数,用于读取指定目录下的所有样本,并将对每个样本进行向量化操作。

def Load_Data(file_dir):
    data = []  # 数据列表
    label = []  # 标签列表
    
    file_list = os.listdir(file_dir)  # 当前目录下所有样本列表
    for name in file_list:  # 读取当前目录下所有文件并转化成行向量
        vector = np.zeros((1, 1024))
        file_name = file_dir + "/" + name  # 样本路径
        f = open(file_name)
        for i in range(32):  # 转化成行向量
            line = f.readline()
            for j in range(32):
                vector[0, i*32 + j] = int(line[j])
        data.append(vector)  # 数据加入数据集
        label.append([int(name.split('_')[0])])  # 标签加入标签集合

    return np.array(data), np.array(label)

加载的训练数据结果如下

>>> train_data, train_label = Load_Data(trian_file_dir)
>>> train_data
array([[[0., 0., 0., ..., 0., 0., 0.]],

       [[0., 0., 0., ..., 0., 0., 0.]],

       [[0., 0., 0., ..., 0., 0., 0.]],

       ...,

       [[0., 0., 0., ..., 0., 0., 0.]],

       [[0., 0., 0., ..., 0., 0., 0.]],

       [[0., 0., 0., ..., 0., 0., 0.]]])
>>> train_label.T
array([[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2,
        2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4,
        4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6,
        6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8,
        8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9]])

3、KNN算法的实现
由上面提到的KNN算法思路
①计算距离
②找出K个距离最近的对象
③取K个对象中类别出现频率最大一类
可写出以下分类代码

def KNN(inX, data, label, k):
    """
    :param inX: 测试对象
    :param data: 训练数据
    :param label: 训练数据的标签
    :param k: 取前k个最小值
    :return: 
    """

    # 计算输入向量与其他样本之间的距离
    squre = (data - inX)**2
    SumFunction = lambda x: x.sum()
    distance_squre = np.apply_along_axis(SumFunction, 2, squre)
    distance = np.sqrt(distance_squre)

    # 计算前K个最小值频率最高的标签
    sorted_index = np.argsort(distance.T)
    class_count = {}
    for i in range(k):
        votelabel = label[sorted_index][0][i][0]
        class_count[votelabel] = class_count.get(votelabel, 0) + 1
    sorted_class_count = sorted(class_count.items(), key=lambda x: x[1], reverse=True)

    return sorted_class_count[0][0]

4、进行手写识别系统的测试
加载训练集和测试集中的所有样本,对手写识别系统进行测试,将测试集中的每一个样本的分类结果与它的原始结果作对比,从而得到此次手写识别系统的正确率。

def HandWritingTest():
    trian_file_dir = "../手写识别数据/trainingDigits"
    test_file_dir = "../手写识别数据/testDigits"
    train_data, train_label = Load_Data(trian_file_dir)  # 训练集
    test_data, test_label = Load_Data(test_file_dir)  # 测试集

    count = 0
    for i in range(len(test_data)):
        prdict = KNN(test_data[i], train_data, train_label, 3)
        print("The predict label is->%s, the true label is->%s" % (prdict, test_label[i][0]))
        if prdict == test_label[i][0]:
            count += 1
    print("The accuracy is ", count / len(test_data))

测试结果如下

The predict label is->0, the true label is->0
The predict label is->0, the true label is->0
The predict label is->0, the true label is->0
The predict label is->0, the true label is->0
The predict label is->0, the true label is->0
The predict label is->1, the true label is->1
The predict label is->1, the true label is->1
The predict label is->1, the true label is->1
The predict label is->1, the true label is->1
The predict label is->1, the true label is->1
The predict label is->2, the true label is->2
The predict label is->2, the true label is->2
The predict label is->2, the true label is->2
The predict label is->2, the true label is->2
The predict label is->2, the true label is->2
The predict label is->3, the true label is->3
The predict label is->3, the true label is->3
The predict label is->3, the true label is->3
The predict label is->3, the true label is->3
The predict label is->3, the true label is->3
The predict label is->4, the true label is->4
The predict label is->4, the true label is->4
The predict label is->4, the true label is->4
The predict label is->4, the true label is->4
The predict label is->4, the true label is->4
The predict label is->5, the true label is->5
The predict label is->5, the true label is->5
The predict label is->5, the true label is->5
The predict label is->5, the true label is->5
The predict label is->5, the true label is->5
The predict label is->6, the true label is->6
The predict label is->6, the true label is->6
The predict label is->6, the true label is->6
The predict label is->6, the true label is->6
The predict label is->6, the true label is->6
The predict label is->7, the true label is->7
The predict label is->7, the true label is->7
The predict label is->7, the true label is->7
The predict label is->7, the true label is->7
The predict label is->7, the true label is->7
The predict label is->8, the true label is->8
The predict label is->8, the true label is->8
The predict label is->8, the true label is->8
The predict label is->8, the true label is->8
The predict label is->8, the true label is->8
The predict label is->9, the true label is->9
The predict label is->9, the true label is->9
The predict label is->9, the true label is->9
The predict label is->9, the true label is->9
The predict label is->9, the true label is->9
The accuracy is  1.0

本次结果的正确率为100%,可以说是相当不错了
以上及为KNN算法的全部过程及代码

2016-05-22 15:47:54 BaiHuaXiu123 阅读数 77113
  • 机器学习--线性回归数学推导视频教学

    线性回归数学推导是机器学习的基石,是人工智能的算法基础, 可以被广泛的应用在在工作和学习。本节课就带领同学们从零开始一步一步的推导线性回归。课程内容包括矩阵转换、误差值分析、似然函数、小二乘、结果推导。 任务作业: 设计并实现一个三层架构的员工管理系统。要求: 1、数据库及其表自行设计,遵循数据库及表设计的一般命名规则 2、要求有管理员的登录功能及对员工信息的增删改查 3、功能的实现严格采用三层架构的设计框架,注意命名的一般规范 4、采用B/S架构,界面大方美观 5、思考下三层架构与MVC框架有什么区别 (温馨提示: 注意 作业需写在CSDN博客中,请把作业链接贴在评论区,老师会定期逐个批改~~)

    3970 人正在学习 去看看 陆永剑

这里写图片描述

摘要

之前一直对机器学习很感兴趣,一直没时间去研究,今天刚好是周末,有时间去各大技术论坛看看,刚好看到一篇关于机器学习不错的文章,在这里就分享给大家了.
机器学习无疑是当前数据分析领域的一个热点内容。很多人在平时的工作中都或多或少会用到机器学习的算法。这里IT经理网为您总结一下常见的机器学习算法,以供您在工作和学习中参考。
这里写图片描述
机器学习的算法很多。很多时候困惑人们都是,很多算法是一类算法,而有些算法又是从其他算法中延伸出来的。这里,我们从两个方面来给大家介绍,第一个方面是学习的方式,第二个方面是算法的类似性。
这里写图片描述

学习方式

根据数据类型的不同,对一个问题的建模有不同的方式。在机器学习或者人工智能领域,人们首先会考虑算法的学习方式。在机器学习领域,有几种主要的学习方式。将算法按照学习方式分类是一个不错的想法,这样可以让人们在建模和算法选择的时候考虑能根据输入数据来选择最合适的算法来获得最好的结果。

监督式学习:

这里写图片描述

在监督式学习下,输入数据被称为“训练数据”,每组训练数据有一个明确的标识或结果,如对防垃圾邮件系统中“垃圾邮件”“非垃圾邮件”,对手写数字识别中的“1“,”2“,”3“,”4“等。在建立预测模型的时候,监督式学习建立一个学习过程,将预测结果与“训练数据”的实际结果进行比较,不断的调整预测模型,直到模型的预测结果达到一个预期的准确率。监督式学习的常见应用场景如分类问题和回归问题。常见算法有逻辑回归(Logistic Regression)和反向传递神经网络(Back Propagation Neural Network)

非监督式学习:

这里写图片描述

在非监督式学习中,数据并不被特别标识,学习模型是为了推断出数据的一些内在结构。常见的应用场景包括关联规则的学习以及聚类等。常见算法包括Apriori算法以及k-Means算法。

半监督式学习:

这里写图片描述

在此学习方式下,输入数据部分被标识,部分没有被标识,这种学习模型可以用来进行预测,但是模型首先需要学习数据的内在结构以便合理的组织数据来进行预测。应用场景包括分类和回归,算法包括一些对常用监督式学习算法的延伸,这些算法首先试图对未标识数据进行建模,在此基础上再对标识的数据进行预测。如图论推理算法(Graph Inference)或者拉普拉斯支持向量机(Laplacian SVM.)等。

强化学习:

这里写图片描述

在这种学习模式下,输入数据作为对模型的反馈,不像监督模型那样,输入数据仅仅是作为一个检查模型对错的方式,在强化学习下,输入数据直接反馈到模型,模型必须对此立刻作出调整。常见的应用场景包括动态系统以及机器人控制等。常见算法包括Q-Learning以及时间差学习(Temporal difference learning)

在企业数据应用的场景下, 人们最常用的可能就是监督式学习和非监督式学习的模型。 在图像识别等领域,由于存在大量的非标识的数据和少量的可标识数据, 目前半监督式学习是一个很热的话题。 而强化学习更多的应用在机器人控制及其他需要进行系统控制的领域。

算法类似性

根据算法的功能和形式的类似性,我们可以把算法分类,比如说基于树的算法,基于神经网络的算法等等。当然,机器学习的范围非常庞大,有些算法很难明确归类到某一类。而对于有些分类来说,同一分类的算法可以针对不同类型的问题。这里,我们尽量把常用的算法按照最容易理解的方式进行分类。

回归算法:

这里写图片描述

回归算法是试图采用对误差的衡量来探索变量之间的关系的一类算法。回归算法是统计机器学习的利器。在机器学习领域,人们说起回归,有时候是指一类问题,有时候是指一类算法,这一点常常会使初学者有所困惑。常见的回归算法包括:最小二乘法(Ordinary Least Square),逻辑回归(Logistic Regression),逐步式回归(Stepwise Regression),多元自适应回归样条(Multivariate Adaptive Regression Splines)以及本地散点平滑估计(Locally Estimated Scatterplot Smoothing)

基于实例的算法

这里写图片描述

基于实例的算法常常用来对决策问题建立模型,这样的模型常常先选取一批样本数据,然后根据某些近似性把新数据与样本数据进行比较。通过这种方式来寻找最佳的匹配。因此,基于实例的算法常常也被称为“赢家通吃”学习或者“基于记忆的学习”。常见的算法包括 k-Nearest Neighbor(KNN), 学习矢量量化(Learning Vector Quantization, LVQ),以及自组织映射算法(Self-Organizing Map , SOM)

正则化方法

这里写图片描述

正则化方法是其他算法(通常是回归算法)的延伸,根据算法的复杂度对算法进行调整。正则化方法通常对简单模型予以奖励而对复杂算法予以惩罚。常见的算法包括:Ridge Regression, Least Absolute Shrinkage and Selection Operator(LASSO),以及弹性网络(Elastic Net)。

决策树学习

这里写图片描述

决策树算法根据数据的属性采用树状结构建立决策模型, 决策树模型常常用来解决分类和回归问题。常见的算法包括:分类及回归树(Classification And Regression Tree, CART), ID3(Iterative Dichotomiser 3), C4.5, Chi-squared Automatic Interaction Detection(CHAID), Decision Stump, 随机森林(Random Forest), 多元自适应回归样条(MARS)以及梯度推进机(Gradient Boosting Machine, GBM)

贝叶斯方法

这里写图片描述

贝叶斯方法算法是基于贝叶斯定理的一类算法,主要用来解决分类和回归问题。常见算法包括:朴素贝叶斯算法,平均单依赖估计(Averaged One-Dependence Estimators, AODE),以及Bayesian Belief Network(BBN)。

基于核的算法

这里写图片描述

基于核的算法中最著名的莫过于支持向量机(SVM)了。 基于核的算法把输入数据映射到一个高阶的向量空间, 在这些高阶向量空间里, 有些分类或者回归问题能够更容易的解决。 常见的基于核的算法包括:支持向量机(Support Vector Machine, SVM), 径向基函数(Radial Basis Function ,RBF), 以及线性判别分析(Linear Discriminate Analysis ,LDA)等

聚类算法

这里写图片描述
聚类,就像回归一样,有时候人们描述的是一类问题,有时候描述的是一类算法。聚类算法通常按照中心点或者分层的方式对输入数据进行归并。所以的聚类算法都试图找到数据的内在结构,以便按照最大的共同点将数据进行归类。常见的聚类算法包括 k-Means算法以及期望最大化算法(Expectation Maximization, EM)。

关联规则学习

这里写图片描述
关联规则学习通过寻找最能够解释数据变量之间关系的规则,来找出大量多元数据集中有用的关联规则。常见算法包括 Apriori算法和Eclat算法等。

人工神经网络

这里写图片描述
人工神经网络算法模拟生物神经网络,是一类模式匹配算法。通常用于解决分类和回归问题。人工神经网络是机器学习的一个庞大的分支,有几百种不同的算法。(其中深度学习就是其中的一类算法,我们会单独讨论),重要的人工神经网络算法包括:感知器神经网络(Perceptron Neural Network), 反向传递(Back Propagation), Hopfield网络,自组织映射(Self-Organizing Map, SOM)。学习矢量量化(Learning Vector Quantization, LVQ)

深度学习

这里写图片描述

深度学习算法是对人工神经网络的发展。 在近期赢得了很多关注, 特别是百度也开始发力深度学习后, 更是在国内引起了很多关注。 在计算能力变得日益廉价的今天,深度学习试图建立大得多也复杂得多的神经网络。很多深度学习的算法是半监督式学习算法,用来处理存在少量未标识数据的大数据集。常见的深度学习算法包括:受限波尔兹曼机(Restricted Boltzmann Machine, RBN), Deep Belief Networks(DBN),卷积网络(Convolutional Network), 堆栈式自动编码器(Stacked Auto-encoders)。

降低维度算法

这里写图片描述

像聚类算法一样,降低维度算法试图分析数据的内在结构,不过降低维度算法是以非监督学习的方式试图利用较少的信息来归纳或者解释数据。这类算法可以用于高维数据的可视化或者用来简化数据以便监督式学习使用。常见的算法包括:主成份分析(Principle Component Analysis, PCA),偏最小二乘回归(Partial Least Square Regression,PLS), Sammon映射,多维尺度(Multi-Dimensional Scaling, MDS), 投影追踪(Projection Pursuit)等。

集成算法:

这里写图片描述
集成算法用一些相对较弱的学习模型独立地就同样的样本进行训练,然后把结果整合起来进行整体预测。集成算法的主要难点在于究竟集成哪些独立的较弱的学习模型以及如何把学习结果整合起来。这是一类非常强大的算法,同时也非常流行。常见的算法包括:Boosting, Bootstrapped Aggregation(Bagging), AdaBoost,堆叠泛化(Stacked Generalization, Blending),梯度推进机(Gradient Boosting Machine, GBM),随机森林(Random Forest)。

结束

在之后的时间里我会给大家一一介绍这些算法的具体实现.敬请大家期待,大家想一起跟我交流技术,可以关注我的个人公众号.
源码下载地址:

源码下载地址

2019-09-23 13:14:35 java_java38 阅读数 38
  • 机器学习--线性回归数学推导视频教学

    线性回归数学推导是机器学习的基石,是人工智能的算法基础, 可以被广泛的应用在在工作和学习。本节课就带领同学们从零开始一步一步的推导线性回归。课程内容包括矩阵转换、误差值分析、似然函数、小二乘、结果推导。 任务作业: 设计并实现一个三层架构的员工管理系统。要求: 1、数据库及其表自行设计,遵循数据库及表设计的一般命名规则 2、要求有管理员的登录功能及对员工信息的增删改查 3、功能的实现严格采用三层架构的设计框架,注意命名的一般规范 4、采用B/S架构,界面大方美观 5、思考下三层架构与MVC框架有什么区别 (温馨提示: 注意 作业需写在CSDN博客中,请把作业链接贴在评论区,老师会定期逐个批改~~)

    3970 人正在学习 去看看 陆永剑

title: 机器学习-KNN算法
date: 2019-08-16 15:17:00
categories:

  • 技术
    tags:
  • 机器学习
  • Numpy

KNN算法的理解。

定义

如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别,则该样本也属于这个类别。
本文采用欧式距离,即两点之间的直接距离。

思想

通过你的邻居,判断你是哪种类型

KNN算法流程总结

1)计算已知类别数据集中的点与当前点之间的距离
2)按距离递增次序排序
3)选取与当前点距离最小的k个点
4)统计前k个点所在的类别出现的频率
5)返回前k个点出现频率最高的类别作为当前点的预测分类
from sklearn.neighbors import KNeighborsClassifier

# achieve data
x = [[1],[2],[3],[-1],[-4]]
y = [1,1,1,0,-1]

estimator = KNeighborsClassifier(n_neighbors=3)
estimator.fit(x,y)
result = estimator.predict([[-3]])
print(result)
[-1]

问题一:距离选取

1.距离公式,除了欧式距离,还有哪些距离公式可以使用?

(1)欧式距离(两点距离问题):两个点在空间中的距离。
(2)曼哈顿距离(城市街区问题):在曼哈顿街区要从一个十字路口开车到另一个十字路口,驾驶距离显然不是两点间的直线距离。这个实际驾驶距离就是“曼哈顿距离”。曼哈顿距离也称为“城市街区距离”(City Block distance)。
    d(i,j)=|X1-X2|+|Y1-Y2|
(3)切比雪夫距离 (Chebyshev Distance):国际象棋中,国王可以直行、横行、斜行,所以国王走一步可以移动到相邻8个方格中的任意一个。国王从格子(x1,y1)走到格子(x2,y2)最少需要多少步?这个距离就叫切比雪夫距离。在公式里体现就是某个维度上的最大距离。
(4)闵可夫斯基距离(Minkowski Distance):闵氏距离不是一种距离,而是一组距离的定义,是对多个距离度量公式的概括性的表述。
两个n维变量a(x11,x12,…,x1n)与b(x21,x22,…,x2n)间的闵可夫斯基距离定义为:
其中p是一个变参数:
当p=1时,就是曼哈顿距离;
当p=2时,就是欧氏距离;
当p→∞时,就是切比雪夫距离。
根据p的不同,闵氏距离可以表示某一类/种的距离

小结:

1 闵氏距离,包括曼哈顿距离、欧氏距离和切比雪夫距离都存在明显的缺点:
e.g. 二维样本(身高[单位:cm],体重[单位:kg]),现有三个样本:a(180,50),b(190,50),c(180,60)。

a与b的闵氏距离(无论是曼哈顿距离、欧氏距离或切比雪夫距离)等于a与c的闵氏距离。但实际上身高的10cm并不能和体重的10kg划等号。

闵氏距离的缺点:

 (1)将各个分量的量纲(scale),也就是“单位”相同的看待了;
​ (2)未考虑各个分量的分布(期望,方差等)可能是不同的。

改进

标准化欧氏距离 (Standardized EuclideanDistance):标准化欧氏距离是针对欧氏距离的缺点而作的一种改进。
思路:既然数据各维分量的分布不一样,那先将各个分量都“标准化”到均值、方差相等。

其他距离

(1)余弦距离(Cosine Distance):
几何中,夹角余弦可用来衡量两个向量方向的差异;机器学习中,借用这一概念来衡量样本向量之间的差异。
(2)汉明距离(Hamming Distance):
两个等长字符串s1与s2的汉明距离为:将其中一个变为另外一个所需要作的最小字符替换次数。
(3)杰卡德距离(Jaccard Distance):
杰卡德相似系数(Jaccard similarity coefficient):两个集合A和B的交集元素在A,B的并集中所占的比例,称为两个集合的杰卡德相似系数,用符号J(A,B)。
杰卡德距离(Jaccard Distance):与杰卡德相似系数相反,用两个集合中不同元素占所有元素的比例来衡量两个集合的区分度
(4)马氏距离(Mahalanobis Distance):马氏距离是由印度统计学家马哈拉诺比斯提出的,表示数据的协方差距离。它是一种有效的计算两个位置样本集的相似度的方法。马氏距离也可以定义为两个服从同一分布并且其协方差矩阵为∑的随机变量的差异程度:如果协方差矩阵为单位矩阵,马氏距离就简化为欧式距离;如果协方差矩阵为对角矩阵,则其也可称为正规化的欧式距离。
马氏距离特性:

    1.量纲无关,排除变量之间的相关性的干扰;

    2.马氏距离的计算是建立在总体样本的基础上的,如果拿同样的两个样本,放入两个不同的总体中,最后计算得出的两个样本间的马氏距离通常是不相同的,除非这两个总体的协方差矩阵碰巧相同;

    3 .计算马氏距离过程中,要求总体样本数大于样本的维数,否则得到的总体样本协方差矩阵逆矩阵不存在,这种情况下,用欧式距离计算即可。

    4.还有一种情况,满足了条件总体样本数大于样本的维数,但是协方差矩阵的逆矩阵仍然不存在,比如三个样本点(3,4),(5,6),(7,8),这种情况是因为这三个样本在其所处的二维空间平面内共线。这种情况下,也采用欧式距离计算。

问题二:K值的选取

2.选取K值的大小?

K值过小:
容易受到异常点的影响
k值过大:
受到样本均衡的问题

解决方法

参考:

K值选择问题,李航博士的一书「统计学习方法」上所说:

1) 选择较小的K值,就相当于用较小的领域中的训练实例进行预测,“学习”近似误差会减小,只有与输入实例较近或相似的训练实例才会对预测结果起作用,与此同时带来的问题是“学习”的估计误差会增大,换句话说,K值的减小就意味着整体模型变得复杂,容易发生过拟合;

2) 选择较大的K值,就相当于用较大领域中的训练实例进行预测,其优点是可以减少学习的估计误差,但缺点是学习的近似误差会增大。这时候,与输入实例较远(不相似的)训练实例也会对预测器作用,使预测发生错误,且K值的增大就意味着整体的模型变得简单。

3) K=N(N为训练样本个数),则完全不足取,因为此时无论输入实例是什么,都只是简单的预测它属于在训练实例中最多的类,模型过于简单,忽略了训练实例中大量有用信息。

在实际应用中,K值一般取一个比较小的数值,例如采用交叉验证法(简单来说,就是把训练数据在分成两组:训练集和验证集)来选择最优的K值。

近似误差:

对现有训练集的训练误差,关注训练集.

如果近似误差过小可能会出现过拟合的现象,对现有的训练集能有很好的预测,但是对未知的测试样本将会出现较大偏差的预测。

模型本身不是最接近最佳模型。

估计误差:

理解为对测试集的测试误差,关注测试集。

估计误差小说明对未知数据的预测能力好。

模型本身最接近最佳模型。

鸢尾花代码实现

"""
1.获取数据集
2,数据基本处理
3. 特征工程
4. 机器学习(模型训练)
5. 模型评估
"""

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier

# 1.获取数据集
iris = load_iris()
# 2,数据基本处理
# 2.1 数据分割
x_train, x_test, y_train, y_test = train_test_split(iris.data, iris.target, random_state=23, test_size=0.1)

# 3. 特征工程
# 3.1 实例化一个转化器
transfer = StandardScaler()
# 3.2 调用fit_transform方法
x_train = transfer.fit_transform(x_train)
x_test = transfer.fit_transform(x_test)

# 4. 机器学习(模型训练)
# 4.1 实例化一个估计器
estimator = KNeighborsClassifier(n_neighbors=5)
# 4.2 模型训练
estimator.fit(x_train,y_train)
# 5. 模型评估
# 5.1 输出预测值
y_pre = estimator.predict(x_test)
print("预测值是:\n", y_pre)

# 5.2 输出准确率
ret = estimator.score(x_test, y_test)
print("准确率:\n", ret)

KNN 算法总结

优点
  • 简单有效
  • 重新训练代价低
  • 适合类域交叉样本:KNN方法主要靠周围有限的邻近的样本,而不是靠判别类域的方法来确定所属类别的,因此对于类域的交叉或重叠较多的待分样本集来说,KNN方法较其他方法更为适合。
  • 该算法比较适用于样本容量比较大的类域的自动分类,而那些样本容量较小的类域采用这种算法比较容易产生误分。
缺点
  • 惰性算法
  • 类别评分不是规格化
  • 对不均衡的样本不擅长
    当样本不平衡时,如一个类的样本容量很大,而其他类样本容量很小时,有可能导致当输入一个新样本时,该样本的K个邻居中大容量类的样本占多数。该算法只计算“最近的”邻居样本,某一类的样本数量很大,那么或者这类样本并不接近目标样本,或者这类样本很靠近目标样本。无论怎样,数量并不能影响运行结果。可以采用权值的方法(和该样本距离小的邻居权值大)来改进。
  • 计算量较大
    目前常用的解决方法是事先对已知样本点进行剪辑,事先去除对分类作用不大的样本。

【引入】交叉验证&网格搜索

交叉验证

交叉验证:将拿到的训练数据,分为训练和验证集。以下图为例:将数据分成4份,其中一份作为验证集。然后经过4次(组)的测试,每次都更换不同的验证集。即得到4组模型的结果,取平均值作为最终结果。又称4折交叉验证。

目的:为了让被评估的模型更加准确可信
为了让从训练得到模型结果更加准确。做以下处理

训练集:训练集+验证集
测试集:测试集

avater

网格搜索

通常情况下,有很多参数是需要手动指定的(如k-近邻算法中的K值),这种叫超参数。但是手动过程繁杂,所以需要对模型预设几种超参数组合。每组超参数都采用交叉验证来进行评估。最后选出最优参数组合建立模型。

atater

代码实现
sklearn.model_selection.GridSearchCV(estimator, param_grid=None,cv=None)
estimator -- 选择了哪个训练模型
param_grid -- 需要传递的超参数
cv -- 几折交叉验证
"""
1.获取数据集
2,数据基本处理
3. 特征工程
4. 机器学习(模型训练)
5. 模型评估
"""

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split, GridSearchCV
from sklearn.preprocessing import StandardScaler
from sklearn.neighbors import KNeighborsClassifier

# 1.获取数据集
iris = load_iris()
# 2,数据基本处理
# 2.1 数据分割
x_train, x_test, y_train, y_test = train_test_split(iris.data, iris.target, test_size=0.2)

# 3. 特征工程
# 3.1 实例化一个转化器
transfer = StandardScaler()
# 3.2 调用fit_transform方法
x_train = transfer.fit_transform(x_train)
x_test = transfer.fit_transform(x_test)

# 4. 机器学习(模型训练)
# 4.1 实例化一个估计器
estimator = KNeighborsClassifier(n_neighbors=1)

# 4.2 调用交叉验证网格搜索模型
param_grid = {"n_neighbors": [1, 3, 5, 7, 9]}
estimator = GridSearchCV(estimator, param_grid=param_grid, cv=10, n_jobs=4)

# 4.3 模型训练
estimator.fit(x_train, y_train)
# 5. 模型评估
# 5.1 输出预测值
y_pre = estimator.predict(x_test)
print("预测值是:\n", y_pre)

# 5.2 输出准确率
ret = estimator.score(x_test, y_test)
print("准确率:\n", ret)

# 5.3 其他平均指标
print("最好的模型:\n", estimator.best_estimator_)
print("最好的结果:\n", estimator.best_score_)
print("整体模型结果:\n", estimator.cv_results_)

2017-09-05 16:06:02 iloveyousunna 阅读数 655
  • 机器学习--线性回归数学推导视频教学

    线性回归数学推导是机器学习的基石,是人工智能的算法基础, 可以被广泛的应用在在工作和学习。本节课就带领同学们从零开始一步一步的推导线性回归。课程内容包括矩阵转换、误差值分析、似然函数、小二乘、结果推导。 任务作业: 设计并实现一个三层架构的员工管理系统。要求: 1、数据库及其表自行设计,遵循数据库及表设计的一般命名规则 2、要求有管理员的登录功能及对员工信息的增删改查 3、功能的实现严格采用三层架构的设计框架,注意命名的一般规范 4、采用B/S架构,界面大方美观 5、思考下三层架构与MVC框架有什么区别 (温馨提示: 注意 作业需写在CSDN博客中,请把作业链接贴在评论区,老师会定期逐个批改~~)

    3970 人正在学习 去看看 陆永剑

机器学习之KNN算法python实现

一. 理论基础

1. 距离度量

特征空间中两个实例点的距离是两个实例点相似程度的反映。一般采用欧氏距离,但也可以是其他距离,如cosine距离,曼哈顿距离等.

2. k值选择


  • k值越大,意味着模型越简单,学习近似误差大,估计误差小,欠拟合;
  • k值越小,意味着模型越复杂,学习近似误差小,估计误差大,过拟合,而且对近邻的实例点敏感.

通常采取交叉验证选取最优的k值。

3. 分类决策规则

多数表决,即由输入实例的K个近邻的多数类决定输入实例的类别。

4. kd树

高效实现k近邻,类似于二分查找,只不过是在高维的二分查找。
kd树更适用于训练实例数远大于空间维数时的k近邻搜索,当空间维数接近训练实例数时,它的效率会迅速下降,几乎接近线性扫描。

二. python实现

实现了knn的暴力搜索,也实现了kd-tree搜索,但是kd-tree只能找最近邻,即k=1,当k>1时,还未实现,初步想法:可以考虑k次搜索kd-tree,每次搜索后将最近邻节点删除,继续搜索,就找到了top k近邻搜索;这样的话就得实现kd-tree的删除插入。

1. 代码

knn.py

#encoding=utf-8

'''
implement the knn algorithm
'''

import numpy as np
import pandas as pd
from sklearn.model_selection import train_test_split
from scipy.stats import mode
import matplotlib.pyplot as plt

class KNN:

    def __init__(self):
        pass

    def predict(self, x_train, y_train, x_test, k=3):
        self.k = k
        m_train = x_train.shape[0]
        m_test = x_test.shape[0]
        x_train = np.mat(x_train)
        y_train = np.mat(y_train)
        x_test = np.mat(x_test)

        #1. get the distances between each sample in train samples and each sample in test samples,
        #the distances matrix's shape is (m_test, m_train).
        dists = self.__distance__(x_train, x_test)
        #2. sort the distances by row, and get the sort index
        sort_idx = np.argsort(dists, axis=1)
        #3. get the x index and y index, which is top k distance sample index
        x_idx = np.tile(np.mat(range(m_test)).T, [1, self.k])
        y_idx = sort_idx[:, 0 : self.k]
        #4. get the top k distance labels, and the matrix's shape is (m_test, k)
        labels = np.tile(y_train.T, [m_test, 1])
        p_labels = labels[x_idx, y_idx]
        #5. get the mode of each row, which means the most labels
        y_predict = np.mat(mode(p_labels, axis=1)[0])
        return y_predict

    def __distance__(self, x_train, x_test):
        '''
        force compute to get the distance between each sample in train samples and each sample in test samples
        '''
        m_train = x_train.shape[0]
        m_test = x_test.shape[0]
        dists = np.zeros((m_test, m_train))
        count = 0
        for test in x_test:
            test =  np.tile(test, [m_train, 1])
            distance = np.sum(np.multiply(x_train - test, x_train - test), axis=1)
            dists[count] = distance.T
            count += 1
        return dists

    def create_kd_tree(self, datalist):
        '''
        create KD tree
        Args:
            data: data list
        '''
        root = KDNode()
        self.build_tree(root, datalist)
        self.kd_tree = root
        return root

    def build_tree(self, parent, datalist):
        '''
        recursive build tree function
        Args:
            parent: parent node
        '''
        m = datalist.shape[0]
        #if the length of data is equal to 1, the node is a leaf node
        if m == 1:
            parent.data = datalist
            return

        #compute the best split demension by the variance of each demension of the data
        demension = np.argmax(np.var(datalist, axis=0))
        #sort the data by the chosen demension
        sorted_index = np.argsort(datalist[:, demension], axis=0)
        #get the index of the middle value in the datalist
        middle = m / 2
        #get the left data
        l_data = datalist[np.squeeze(sorted_index[0 : middle].getA()), :]
        #get the right data
        r_data = datalist[np.squeeze(sorted_index[middle + 1 : ].getA()), :]

        #assign the property of the parent node
        parent.data = datalist[np.squeeze(sorted_index[middle, :].getA())]
        parent.demension = demension
        parent.split_value = datalist[np.squeeze(sorted_index[middle, :].getA()), demension]

        #recursive build the child node if the length of rest data is not equal to zero
        if len(l_data) != 0:
            l_node = KDNode()
            parent.left = l_node
            self.build_tree(l_node, l_data)

        if len(r_data) != 0:
            r_node = KDNode()
            parent.right = r_node
            self.build_tree(r_node, r_data)

    def __distance_by_kd_tree__(self, x_test):
        '''
        get nearest neighbors matrix by kd_tree search
        '''
        m = x_test.shape[0]
        dists = np.zeros((m, 1))
        count = 0
        for x in x_test:
            dists[count] = self.__find_neighbor__(x, self.kd_tree)
            count += 1
        return np.mat(dists)


    def __find_neighbor__(self, x, node):
        '''
        recursive find the neighbor of x in kd-tree
        Args:
            the root node of current child tree

        steps:
            1. if the current is leaf node, return the data in the node as the nearest neighbor
            2. if the value of x is less than the split value, take the neighbor of left child
               tree as nearest neighbor. And then check if another child tree has the more nearest
               neighbor;
               if the value of x is more than the split value, do it as like mentioned above;
            3. check if the current node and x has more nearest distance
        '''

        if node.demension == None: 
            return node.data

        if (x[0, node.demension] <= node.split_value) and node.left:
            neighbor = self.__find_neighbor__(x, node.left)
            if node.right \
                and (np.abs(x[0, node.demension] - node.split_value) < self.__euclidean_distance__(x, neighbor)) \
                and (self.__euclidean_distance__(self.__find_neighbor__(x, node.right), x) < self.__euclidean_distance__(x, neighbor)):
                    neighbor = self.__find_neighbor__(x, node.right)
        elif (x[0, node.demension] > node.split_value) and node.right:
            neighbor = self.__find_neighbor__(x, node.right)
            if node.left \
                and (np.abs(x[0, node.demension] - node.split_value) < self.__euclidean_distance__(x, neighbor)) \
                and (self.__euclidean_distance__(self.__find_neighbor__(x, node.left), x) < self.__euclidean_distance__(x, neighbor)):
                    neighbor = self.__find_neighbor__(x, node.left)
        else:
            # this happens as like:
            # x = 6, node = 5
            #         5
            #        /
            #       4
            neighbor = node.data

        if self.__euclidean_distance__(x, node.data) < self.__euclidean_distance__(x, neighbor):
            neighbor = node.data
        return neighbor

    def __euclidean_distance__(self, x1, x2):
        '''
        compute the euclidean distance
        '''
        return np.sum(np.multiply(x1 - x2, x1 - x2))

class KDNode:
    def __init__(self, data=None, demension=None, split_value=None, left=None, right=None):
        self.data = data
        self.demension = demension
        self.split_value = split_value
        self.left = left
        self.right = right

def main():
    '''
    KNN test unit
    '''

    #1. load data
    print "1. loading data..."
    data = pd.read_csv('/home/LiuYao/Documents/MarchineLearning/multi_data.csv')
    data['label'] = data['label'] + 1
    x_train, x_test, y_train, y_test = train_test_split(
                                                    data.values[:, 0:2], 
                                                    data.values[:, 2], 
                                                    test_size=0.2, 
                                                    random_state=0
                                                    )

    x_train = np.mat(x_train)
    x_test = np.mat(x_test) 
    y_train = np.mat(y_train).T
    y_test = np.mat(y_test).T

    #2. predict
    print '2. predicting...'
    knn = KNN()
    y_predict = knn.predict(x_train, y_train, x_test, k=1)

    #3. show the results
    print '3. show the results...'
    plt.scatter(x_train.getA()[:, 0], x_train.getA()[:, 1], c=y_train.T.getA()[0], marker='o')
    plt.scatter(x_test.getA()[:, 0], x_test.getA()[:, 1], c=y_predict.T.getA()[0], marker='*')
    plt.show()



def test_build_tree():
    '''
    test building the kd tree
    '''
    datalist = np.mat([[3, 1, 4],
                       [2, 3, 7],
                       [2, 1, 3],
                       [2, 4, 5],
                       [1, 4, 4],
                       [0, 5, 7],
                       [6, 1, 4],
                       [4, 3, 4],
                       [5, 2, 5],
                       [4, 0, 6],
                       [7, 1, 6]])
    knn = KNN()
    tree = knn.create_kd_tree(datalist)
    res = knn.__find_neighbor__(np.mat([[3,1,5]]), tree)
    print res

if __name__ == '__main__':
    main()

2. 结果

图中五角星表示预测数据,圆点表示训练数据,可能需要将图片放大才能看清楚。

knn_results

3. 数据

x,y,label
14.7,17.85,0
17.45,17.45,0
18.85,15.15,0
17.25,13.7,0
13.9,12.5,0
10.5,15.65,0
8.4,20.5,0
11.1,21.85,0
17.6,21.65,0
23.0,19.75,0
24.45,12.4,0
16.25,3.3,0
8.85,5.05,0
5.55,8.8,0
6.05,11.75,0
26.45,6.9,0
28.95,6.6,0
21.75,8.35,0
21.05,10.95,0
23.9,17.05,0
19.7,18.2,0
12.4,19.3,0
9.25,18.4,0
10.3,8.95,0
16.65,8.6,0
37.3,15.1,0
32.5,10.0,1
33.05,11.45,1
25.75,17.1,1
20.15,17.8,1
12.85,20.75,1
12.8,8.65,1
14.65,5.6,1
24.2,6.3,1
24.1,11.45,1
22.05,10.85,1
17.2,12.85,1
13.7,15.55,1
6.4,19.45,1
8.1,11.5,1
14.9,10.35,1
10.05,12.65,1
25.3,1.55,1
16.5,3.8,1
17.0,6.25,1
17.85,7.35,1
23.75,9.7,1
21.65,16.3,1
16.3,19.8,1
13.9,19.85,1
13.1,14.35,1
16.55,17.9,1
16.3,18.15,1
15.3,17.7,1
13.35,18.3,1
12.8,17.5,1
13.9,15.65,1
15.65,16.5,1
31.35,7.2,1
31.35,6.95,1
29.45,5.6,1
27.15,4.85,1
26.6,5.2,1
27.8,7.35,1
28.7,8.35,1
28.8,10.25,1
5.65,11.25,1
7.8,9.7,1
7.5,11.9,1
3.55,14.45,1
3.5,13.65,1
5.1,10.95,1
5.1,11.05,1
18.65,9.1,2
19.4,10.95,2
20.1,12.7,2
17.25,14.85,2
14.6,15.25,2
14.8,11.75,2
13.5,6.4,2
14.75,5.25,2
18.05,4.05,2
21.25,3.3,2
23.75,3.85,2
32.65,5.5,2
33.65,7.05,2
32.15,13.2,2
30.8,15.25,2
30.15,16.5,2
24.7,18.0,2
22.05,19.45,2
20.1,21.5,2
20.0,22.05,2
26.8,22.45,2
29.7,21.8,2
30.95,21.35,2
30.85,19.15,2
28.4,18.7,2
26.35,19.65,2
26.5,19.9,2
30.05,19.35,2
32.75,16.35,2
33.95,14.65,2
34.05,14.6,2
30.05,18.3,3
27.65,20.6,3
25.05,21.85,3
24.1,18.2,3
23.8,15.3,3
25.6,14.45,3
28.1,12.4,3
29.35,10.95,3
29.85,8.25,3
30.55,14.1,3
28.45,15.7,3
31.85,18.15,3
18.2,19.3,3
16.85,19.8,3
7.45,9.35,3
13.35,13.9,3
32.4,9.75,3
23.8,1.05,3
30.75,4.05,4
30.5,5.3,4
30.35,5.95,4
28.9,9.0,4
27.7,9.9,4
24.75,11.4,4
21.65,13.8,4
19.75,17.45,4
23.4,20.05,4
18.2,21.75,4
9.65,18.4,4
5.6,13.45,4
8.8,9.75,4
11.25,11.2,4
5.35,15.95,4
6.1,16.0,4
24.25,15.95,4
31.55,17.0,4
32.45,14.0,4
24.05,12.4,4
12.3,12.85,4
7.15,19.3,4
21.35,22.4,4
27.95,17.65,4
24.3,7.7,4
17.5,3.6,4
12.7,6.95,4
11.25,10.7,4
9.0,15.2,4
7.05,19.15,4
17.45,13.4,4
16.0,10.75,4
16.75,12.0,4
18.25,11.5,4
18.15,9.15,4
17.1,9.5,4
17.0,10.25,4
12.8,7.75,4
17.0,6.7,4
21.15,8.5,4
20.35,9.35,4
19.45,10.0,4
18.45,10.05,4
18.0,8.0,4
20.15,8.0,4
21.45,6.65,4
19.2,6.45,4
15.25,8.4,4
14.8,9.5,4
14.45,7.7,4
16.45,6.6,4
18.0,5.85,4
18.85,5.7,4
19.6,6.1,4
29.9,14.15,6
31.4,15.8,6
32.15,15.3,6
33.25,13.65,6
33.8,11.95,6
33.85,10.9,6
33.9,10.35,6
32.6,10.75,6
32.1,12.55,6
34.15,12.55,6
35.35,11.8,6
35.15,10.4,6
34.65,9.1,6
34.3,8.9,6
35.55,9.25,6
36.35,12.45,6
37.75,9.4,6
37.75,8.5,6
36.4,8.2,6
35.0,8.05,6
35.65,7.15,6
37.55,6.4,6
39.2,7.1,6
36.5,9.85,0
36.8,9.35,0
37.5,7.7,0
34.05,9.8,0
20.2,20.3,0
26.45,21.1,0
27.9,20.65,0
27.15,16.9,0
25.5,13.1,0
24.05,10.2,0
23.45,5.3,0
20.8,10.95,0
18.95,14.65,0
17.15,16.25,0
11.3,17.0,0
11.65,11.1,0
15.95,4.8,0
21.45,3.25,0
13.9,3.05,0
10.75,6.2,0
9.3,16.85,0
10.25,19.5,0
12.7,15.95,0
13.3,14.3,0
15.7,11.45,0
16.1,10.9,0
14.1,14.2,0
14.35,13.65,0
15.3,14.1,0
15.65,14.7,0
15.75,15.85,0
15.75,15.85,0
19.2,18.4,0
19.2,17.05,0
19.3,15.6,0
20.45,14.1,0
21.4,11.65,0
26.3,11.85,2
20.5,18.75,2
17.55,19.95,2
13.1,16.65,2
9.55,12.7,2
7.85,15.65,2
7.75,16.8,2
9.1,10.35,2
21.25,8.6,2
22.65,5.0,2
11.75,10.7,1
11.05,14.55,1
13.85,8.45,1
11.7,6.65,1
10.75,4.95,1
10.95,3.75,1
6.85,8.35,1
11.35,5.7,1
13.25,4.6,1
7.45,7.95,1
15.7,13.35,1
16.85,14.3,1
13.55,10.4,1
9.55,7.3,1
34.3,8.0,1
28.15,8.45,1
25.15,8.75,1
22.3,14.6,1
29.5,15.55,1
28.2,14.1,1
32.95,10.15,1
29.15,11.4,1
20.85,18.95,1
22.0,17.8,1
12.5,2.35,2
7.25,14.5,3
6.1,18.25,3
8.85,20.5,3
7.55,22.25,3
15.8,19.2,3
16.2,18.0,3
16.95,17.45,3
17.35,18.2,3
18.25,17.45,3
17.85,17.15,3
18.25,16.25,3
19.75,16.15,3
20.85,16.95,3
21.8,17.95,3
22.75,19.0,3
24.2,19.15,3
25.05,18.55,3
25.25,17.45,3
13.95,11.1,3
15.7,10.0,3
14.3,9.85,3
14.3,10.65,3
14.85,11.1,3
10.9,7.9,3
9.1,8.5,3
11.55,16.5,2
11.05,18.5,2
20.4,7.5,1
19.95,8.7,1
27.55,2.05,4
26.6,2.5,4
27.05,3.65,4
28.65,4.1,4
30.6,11.8,4
29.55,12.35,4
29.0,13.05,4
30.5,13.4,4
31.6,14.05,4
31.55,14.9,4
28.6,17.1,4
30.35,17.75,4
34.7,12.25,4
31.0,11.75,4
16.0,12.7,4
8.8,17.95,4
14.45,3.7,4
28.6,4.75,4
29.7,10.85,4
24.15,14.2,4
14.85,12.0,4
6.9,11.05,4
2016-05-01 15:45:22 chenchunyue11 阅读数 4919
  • 机器学习--线性回归数学推导视频教学

    线性回归数学推导是机器学习的基石,是人工智能的算法基础, 可以被广泛的应用在在工作和学习。本节课就带领同学们从零开始一步一步的推导线性回归。课程内容包括矩阵转换、误差值分析、似然函数、小二乘、结果推导。 任务作业: 设计并实现一个三层架构的员工管理系统。要求: 1、数据库及其表自行设计,遵循数据库及表设计的一般命名规则 2、要求有管理员的登录功能及对员工信息的增删改查 3、功能的实现严格采用三层架构的设计框架,注意命名的一般规范 4、采用B/S架构,界面大方美观 5、思考下三层架构与MVC框架有什么区别 (温馨提示: 注意 作业需写在CSDN博客中,请把作业链接贴在评论区,老师会定期逐个批改~~)

    3970 人正在学习 去看看 陆永剑

机器学习中常见的一些优化算法的总结,以最直接的方式理解。

注:梯度下降法图片来自Rachel-Zhang的博客


机器学习常见的优化算法

不是所有的方程都具有解析解,因此可采用优化的方法寻找其最有解,在机器学习中常见的算法有梯度下降法、牛顿法和拉格朗日对偶性。

1、梯度下降法

具有一阶连续的偏导数的目标函数,以Andrew Ng老师的课件简要说明。采用线性回归算法来说明,回归函数为:

目标函数和优化条件


让参数沿着梯度下降的方向走,并迭代地不断减小J(theta0,theta1),达到稳定状态。


初始化theta0,theta1,然后根据梯度下降的方向优化目标值theta0和theta1,使代价函数逐渐收敛到一定的值,一般是指代价函数的偏导数小于某一个值。



在线性回归中梯度下降对参数有两种更新方法,其中一种是同时对参数进行更新;另一种是没更新一个直接用到下一个参数的更新中。以下图为例,左侧的符合本次线性回归函数要求同时更新,右侧的是更新完一个参数将新更新的参数用到下个参数更新的计算过程中。


alpha为梯度下降的学习率,也称步长。



其最终效果为


以上为梯度下降的简单描述,其中梯度下降中的学习率alpha是可以变化的,可以选择每次使代价函数最小的alpha,即可以修改学习率。


2、牛顿法(拟牛顿法)

牛顿法是常用来解决方程求解和最优化问题,求解问题通常是利用一阶导数求解方程为0的解,优化问题通常是利用二阶导数求解一阶导数为0的解。
(1)求解方程的牛顿法
参考Andrew Ng的Machine Learning 的讲义,求解方程法f(theta)=0,利用f(theta) = f(theta0) + (theta1-theta0)*f'(theta0),可通过迭代算法实现。

牛顿方法实现过程如下图所示:

当f(theta)-f(theta0)<a时,theta约等于theta0。
(2)牛顿方法求最优化问题
牛顿法求解最优化问题,即求法l(theta)的极大极小值问题,该问题可转化为求解l'(theta)=0 问题,此时可将问题转换为第一部分求解方程问题。因此,

其中,l''(theta) = H。因此

其中,H的形式如下,将x替换为theta即可。

李航统计学习基础中的理解偏理论些,从另一方面更好理解为x(k+1)-x(k)=f'/H,即H(x(k+1)-x(k))=f'。




(3)拟牛顿算法
在牛顿法中,需要计算H的逆,这一过程比较复杂,因此构造矩阵G来逼近H的逆阵,降低计算量。这是拟牛顿法的基本思想。
x(k+1)-x(k)=(f'(k+1)-f'(k))/H,因此,G满足x(k+1)-x(k)=G*(f'(k+1)-f'(k))。因此该条件为称为拟牛顿法。按照牛顿条件,在每次迭代中可以选择更新矩阵G(k+1)=G(k)+(delta)G(k)。

理解不是很深刻,待理解后详解:
采用BFD算法,G的更新公式为

其中,




3、拉格朗日对偶性


参考文献与博客:

1.  http://blog.csdn.net/abcjennifer/article/details/7700772

2. Andrew Ng 在Machine Learning的课件

3. 李航.统计学习基础

机器学习之简介

阅读数 553

机器学习算法比较

阅读数 255

没有更多推荐了,返回首页