• 我们先带着大家过一遍传统机器学习算法,基本思想和用途。把问题解决思路和方法应用建议提前到这里的想法也很简单,希望能提前给大家一些小建议,对于某些容易出错的地方也先给大家打个预防针,这样在理解后续相应...

    作者:寒小阳
    时间:2016年1月。
    出处:http://blog.csdn.net/han_xiaoyang/article/details/50469334
    声明:版权所有,转载请联系作者并注明出处

    1.引言

    提起笔来写这篇博客,突然有点愧疚和尴尬。愧疚的是,工作杂事多,加之懒癌严重,导致这个系列一直没有更新,向关注该系列的同学们道个歉。尴尬的是,按理说,机器学习介绍与算法一览应该放在最前面写,详细的应用建议应该在讲完机器学习常用算法之后写,突然莫名奇妙在中间插播这么一篇,好像有点打乱主线。
    老话说『亡羊补牢,为时未晚』,前面开头忘讲的东西,咱在这块儿补上。我们先带着大家过一遍传统机器学习算法,基本思想和用途。把问题解决思路和方法应用建议提前到这里的想法也很简单,希望能提前给大家一些小建议,对于某些容易出错的地方也先给大家打个预防针,这样在理解后续相应机器学习算法之后,使用起来也有一定的章法。

    2.机器学习算法简述

    按照不同的分类标准,可以把机器学习的算法做不同的分类。

    2.1 从机器学习问题角度分类

    我们先从机器学习问题本身分类的角度来看,我们可以分成下列类型的算法:

    • 监督学习算法

    机器学习中有一大部分的问题属于『监督学习』的范畴,简单口语化地说明,这类问题中,给定的训练样本中,每个样本的输入xxx都对应一个确定的结果yyy,我们需要训练出一个模型(数学上看是一个x→yx → yxy的映射关系fff),在未知的样本x′x'x给定后,我们能对结果y′y'y做出预测。

    这里的预测结果如果是离散值(很多时候是类别类型,比如邮件分类问题中的垃圾邮件/普通邮件,比如用户会/不会购买某商品),那么我们把它叫做分类问题(classification problem);如果预测结果是连续值(比如房价,股票价格等等),那么我们把它叫做回归问题(regression problem)。

    有一系列的机器学习算法是用以解决监督学习问题的,比如最经典的用于分类问题的朴素贝叶斯、逻辑回归、支持向量机等等;比如说用于回归问题的线性回归等等。

    • 无监督学习

    有另外一类问题,给我们的样本并没有给出『标签/标准答案』,就是一系列的样本。而我们需要做的事情是,在一些样本中抽取出通用的规则。这叫做『无监督学习』。包括关联规则和聚类算法在内的一系列机器学习算法都属于这个范畴。

    • 半监督学习

    这类问题给出的训练数据,有一部分有标签,有一部分没有标签。我们想学习出数据组织结构的同时,也能做相应的预测。此类问题相对应的机器学习算法有自训练(Self-Training)、直推学习(Transductive Learning)、生成式模型(Generative Model)等。

    总体说来,最常见是前两类问题,而对应前两类问题的一些机器学习算法如下:

    机器学习算法

    2.2 从算法的功能角度分类

    我们也可以从算法的共性(比如功能,运作方式)角度对机器学习算法分类。下面我们根据算法的共性去对它们归个类。不过需要注意的是,我们下面的归类方法可能对分类和回归有比较强的倾向性,而这两类问题也是最常遇到的。

    2.2.1 回归算法(Regression Algorithms)

    回归算法
    回归算法是一种通过最小化预测值与实际结果值之间的差距,而得到输入特征之间的最佳组合方式的一类算法。对于连续值预测有线性回归等,而对于离散值/类别预测,我们也可以把逻辑回归等也视作回归算法的一种,常见的回归算法如下:

    • Ordinary Least Squares Regression (OLSR)
    • Linear Regression
    • Logistic Regression
    • Stepwise Regression
    • Locally Estimated Scatterplot Smoothing (LOESS)
    • Multivariate Adaptive Regression Splines (MARS)

    2.2.2 基于实例的算法(Instance-based Algorithms)

    基于实例的算法
    这里所谓的基于实例的算法,我指的是我们最后建成的模型,对原始数据样本实例依旧有很强的依赖性。这类算法在做预测决策时,一般都是使用某类相似度准则,去比对待预测的样本和原始样本的相近度,再给出相应的预测结果。常见的基于实例的算法有:

    • k-Nearest Neighbour (kNN)
    • Learning Vector Quantization (LVQ)
    • Self-Organizing Map (SOM)
    • Locally Weighted Learning (LWL)

    2.2.3 决策树类算法(Decision Tree Algorithms)

    决策树类算法
    决策树类算法,会基于原始数据特征,构建一颗包含很多决策路径的树。预测阶段选择路径进行决策。常见的决策树算法包括:

    • Classification and Regression Tree (CART)
    • Iterative Dichotomiser 3 (ID3)
    • C4.5 and C5.0 (different versions of a powerful approach)
    • Chi-squared Automatic Interaction Detection (CHAID)
    • M5
    • Conditional Decision Trees

    2.2.4 贝叶斯类算法(Bayesian Algorithms)

    贝叶斯类算法
    这里说的贝叶斯类算法,指的是在分类和回归问题中,隐含使用了贝叶斯原理的算法。包括:

    • Naive Bayes
    • Gaussian Naive Bayes
    • Multinomial Naive Bayes
    • Averaged One-Dependence Estimators (AODE)
    • Bayesian Belief Network (BBN)
    • Bayesian Network (BN)

    2.2.5 聚类算法(Clustering Algorithms)

    聚类算法
    聚类算法做的事情是,把输入样本聚成围绕一些中心的『数据团』,以发现数据分布结构的一些规律。常用的聚类算法包括:

    • k-Means
    • Hierarchical Clustering
    • Expectation Maximisation (EM)

    2.2.6 关联规则算法(Association Rule Learning Algorithms)

    关联规则算法
    关联规则算法是这样一类算法:它试图抽取出,最能解释观察到的训练样本之间关联关系的规则,也就是获取一个事件和其他事件之间依赖或关联的知识,常见的关联规则算法有:

    • Apriori algorithm
    • Eclat algorithm

    2.2.7 人工神经网络类算法(Artificial Neural Network Algorithms)

    人工神经网络类算法
    这是受人脑神经元工作方式启发而构造的一类算法。需要提到的一点是,我把『深度学习』单拎出来了,这里说的人工神经网络偏向于更传统的感知算法,主要包括:

    • Perceptron
    • Back-Propagation
    • Radial Basis Function Network (RBFN)

    2.2.8 深度学习(Deep Learning Algorithms)

    深度学习
    深度学习是近年来非常火的机器学习领域,相对于上面列的人工神经网络算法,它通常情况下,有着更深的层次和更复杂的结构。有兴趣的同学可以看看我们另一个系列机器学习与计算机视觉,最常见的深度学习算法包括:

    • Deep Boltzmann Machine (DBM)
    • Deep Belief Networks (DBN)
    • Convolutional Neural Network (CNN)
    • Stacked Auto-Encoders

    2.2.9 降维算法(Dimensionality Reduction Algorithms)

    降维算法
    从某种程度上说,降维算法和聚类其实有点类似,因为它也在试图发现原始训练数据的固有结构,但是降维算法在试图,用更少的信息(更低维的信息)总结和描述出原始信息的大部分内容。
    有意思的是,降维算法一般在数据的可视化,或者是降低数据计算空间有很大的作用。它作为一种机器学习的算法,很多时候用它先处理数据,再灌入别的机器学习算法学习。主要的降维算法包括:

    • Principal Component Analysis (PCA)
    • Principal Component Regression (PCR)
    • Partial Least Squares Regression (PLSR)
    • Sammon Mapping
    • Multidimensional Scaling (MDS)
    • Linear Discriminant Analysis (LDA)
    • Mixture Discriminant Analysis (MDA)
    • Quadratic Discriminant Analysis (QDA)
    • Flexible Discriminant Analysis (FDA)

    2.2.10 模型融合算法(Ensemble Algorithms)

    模型融合算法
    严格意义上来说,这不算是一种机器学习算法,而更像是一种优化手段/策略,它通常是结合多个简单的弱机器学习算法,去做更可靠的决策。拿分类问题举个例,直观的理解,就是单个分类器的分类是可能出错,不可靠的,但是如果多个分类器投票,那可靠度就会高很多。常用的模型融合增强方法包括:

    • Random Forest
    • Boosting
    • Bootstrapped Aggregation (Bagging)
    • AdaBoost
    • Stacked Generalization (blending)
    • Gradient Boosting Machines (GBM)
    • Gradient Boosted Regression Trees (GBRT)

    2.3 机器学习算法使用图谱

    scikit-learn作为一个丰富的python机器学习库,实现了绝大多数机器学习的算法,有相当多的人在使用,于是我这里很无耻地把machine learning cheat sheet for sklearn搬过来了,原文可以看这里。哈哈,既然讲机器学习,我们就用机器学习的语言来解释一下,这是针对实际应用场景的各种条件限制,对scikit-learn里完成的算法构建的一颗决策树,每一组条件都是对应一条路径,能找到相对较为合适的一些解决方法,具体如下:

    sklearn机器学习算法使用图谱

    首先样本量如果非常少的话,其实所有的机器学习算法都没有办法从里面『学到』通用的规则和模式,so多弄点数据是王道。然后根据问题是有/无监督学习和连续值/离散值预测,分成了分类聚类回归维度约减四个方法类,每个类里根据具体情况的不同,又有不同的处理方法。

    3. 机器学习问题解决思路

    上面带着代价走马观花过了一遍机器学习的若干算法,下面我们试着总结总结在拿到一个实际问题的时候,如果着手使用机器学习算法去解决问题,其中的一些注意点以及核心思路。主要包括以下内容:

    • 拿到数据后怎么了解数据(可视化)
    • 选择最贴切的机器学习算法
    • 定位模型状态(过/欠拟合)以及解决方法
    • 大量极的数据的特征分析与可视化
    • 各种损失函数(loss function)的优缺点及如何选择

    多说一句,这里写的这个小教程,主要是作为一个通用的建议和指导方案,你不一定要严格按照这个流程解决机器学习问题。

    3.1 数据与可视化

    我们先使用scikit-learn的make_classification函数来生产一份分类数据,然后模拟一下拿到实际数据后我们需要做的事情。

    #numpy科学计算工具箱
    import numpy as np
    #使用make_classification构造1000个样本,每个样本有20个feature
    from sklearn.datasets import make_classification
    X, y = make_classification(1000, n_features=20, n_informative=2, 
                               n_redundant=2, n_classes=2, random_state=0)
    #存为dataframe格式
    from pandas import DataFrame
    df = DataFrame(np.hstack((X, y[:, None])),columns = range(20) + ["class"])
    

    我们生成了一份包含1000个分类数据样本的数据集,每个样本有20个数值特征。同时我们把数据存储至pandas中的DataFrame数据结构中。我们取前几行的数据看一眼:

    df[:6]
    

    前6行

    不幸的是,肉眼看数据,尤其是维度稍微高点的时候,很有可能看花了也看不出看不出任何线索。幸运的是,我们对于图像的理解力,比数字好太多,而又有相当多的工具可以帮助我们『可视化』数据分布。

    我们在处理任何数据相关的问题时,了解数据都是很有必要的,而可视化可以帮助我们更好地直观理解数据的分布和特性

    数据的可视化有很多工具包可以用,比如下面我们用来做数据可视化的工具包Seaborn。最简单的可视化就是数据散列分布图和柱状图,这个可以用Seanborn的pairplot来完成。以下图中2种颜色表示2种不同的类,因为20维的可视化没有办法在平面表示,我们取出了一部分维度,两两组成pair看数据在这2个维度平面上的分布状况,代码和结果如下:

    import matplotlib.pyplot as plt
    import seaborn as sns
    #使用pairplot去看不同特征维度pair下数据的空间分布状况
    _ = sns.pairplot(df[:50], vars=[8, 11, 12, 14, 19], hue="class", size=1.5)
    plt.show()
    

    pair_plot下数据分布状况

    我们从散列图和柱状图上可以看出,确实有些维度的特征相对其他维度,有更好的区分度,比如第11维和14维看起来很有区分度。这两个维度上看,数据点是近似线性可分的。而12维和19维似乎呈现出了很高的负相关性。接下来我们用Seanborn中的corrplot来计算计算各维度特征之间(以及最后的类别)的相关性。代码和结果图如下:

    import matplotlib.pyplot as plt
    plt.figure(figsize=(12, 10))
    _ = sns.corrplot(df, annot=False)
    plt.show()
    

    各位特征相关性

    相关性图很好地印证了我们之前的想法,可以看到第11维特征和第14维特征和类别有极强的相关性,同时它们俩之间也有极高的相关性。而第12维特征和第19维特征却呈现出极强的负相关性。强相关的特征其实包含了一些冗余的特征,而除掉上图中颜色较深的特征,其余特征包含的信息量就没有这么大了,它们和最后的类别相关度不高,甚至各自之间也没什么先惯性。

    插一句,这里的维度只有20,所以这个相关度计算并不费太大力气,然而实际情形中,你完全有可能有远高于这个数字的特征维度,同时样本量也可能多很多,那种情形下我们可能要先做一些处理,再来实现可视化了。别着急,一会儿我们会讲到。

    3.2 机器学习算法选择

    数据的情况我们大致看了一眼,确定一些特征维度之后,我们可以考虑先选用机器学习算法做一个baseline的系统出来了。这里我们继续参照上面提到过的机器学习算法使用图谱
    我们只有1000个数据样本,是分类问题,同时是一个有监督学习,因此我们根据图谱里教的方法,使用LinearSVC(support vector classification with linear kernel)试试。注意,LinearSVC需要选择正则化方法以缓解过拟合问题;我们这里选择使用最多的L2正则化,并把惩罚系数C设为10。我们改写一下sklearn中的学习曲线绘制函数,画出训练集和交叉验证集上的得分:

    from sklearn.svm import LinearSVC
    from sklearn.learning_curve import learning_curve
    #绘制学习曲线,以确定模型的状况
    def plot_learning_curve(estimator, title, X, y, ylim=None, cv=None,
                            train_sizes=np.linspace(.1, 1.0, 5)):
        """
        画出data在某模型上的learning curve.
        参数解释
        ----------
        estimator : 你用的分类器。
        title : 表格的标题。
        X : 输入的feature,numpy类型
        y : 输入的target vector
        ylim : tuple格式的(ymin, ymax), 设定图像中纵坐标的最低点和最高点
        cv : 做cross-validation的时候,数据分成的份数,其中一份作为cv集,其余n-1份作为training(默认为3份)
        """
        
        plt.figure()
        train_sizes, train_scores, test_scores = learning_curve(
            estimator, X, y, cv=5, n_jobs=1, train_sizes=train_sizes)
        train_scores_mean = np.mean(train_scores, axis=1)
        train_scores_std = np.std(train_scores, axis=1)
        test_scores_mean = np.mean(test_scores, axis=1)
        test_scores_std = np.std(test_scores, axis=1)
    
        plt.fill_between(train_sizes, train_scores_mean - train_scores_std,
                         train_scores_mean + train_scores_std, alpha=0.1,
                         color="r")
        plt.fill_between(train_sizes, test_scores_mean - test_scores_std,
                         test_scores_mean + test_scores_std, alpha=0.1, color="g")
        plt.plot(train_sizes, train_scores_mean, 'o-', color="r",
                 label="Training score")
        plt.plot(train_sizes, test_scores_mean, 'o-', color="g",
                 label="Cross-validation score")
    
        plt.xlabel("Training examples")
        plt.ylabel("Score")
        plt.legend(loc="best")
        plt.grid("on") 
        if ylim:
            plt.ylim(ylim)
        plt.title(title)
        plt.show()
    
    #少样本的情况情况下绘出学习曲线
    plot_learning_curve(LinearSVC(C=10.0), "LinearSVC(C=10.0)",
                        X, y, ylim=(0.8, 1.01),
                        train_sizes=np.linspace(.05, 0.2, 5))
    

    学习曲线1

    这幅图上,我们发现随着样本量的增加,训练集上的得分有一定程度的下降,交叉验证集上的得分有一定程度的上升,但总体说来,两者之间有很大的差距,训练集上的准确度远高于交叉验证集。这其实意味着我们的模型处于过拟合的状态,也即模型太努力地刻画训练集,一不小心把很多噪声的分布也拟合上了,导致在新数据上的泛化能力变差了。

    3.2.1 过拟合的定位与解决

    问题来了,过拟合咋办?
    针对过拟合,有几种办法可以处理:

    • 增大样本量

    这个比较好理解吧,过拟合的主要原因是模型太努力地去记住训练样本的分布状况,而加大样本量,可以使得训练集的分布更加具备普适性,噪声对整体的影响下降。恩,我们提高点样本量试试:

    #增大一些样本量
    plot_learning_curve(LinearSVC(C=10.0), "LinearSVC(C=10.0)",
                        X, y, ylim=(0.8, 1.1),
                        train_sizes=np.linspace(.1, 1.0, 5))
    

    学习曲线2

    是不是发现问题好了很多?随着我们增大训练样本量,我们发现训练集和交叉验证集上的得分差距在减少,最后它们已经非常接近了。增大样本量,最直接的方法当然是想办法去采集相同场景下的新数据,如果实在做不到,也可以试试在已有数据的基础上做一些人工的处理生成新数据(比如图像识别中,我们可能可以对图片做镜像变换、旋转等等),当然,这样做一定要谨慎,强烈建议想办法采集真实数据。

    • 减少特征的量(只用我们觉得有效的特征)

    比如在这个例子中,我们之前的数据可视化和分析的结果表明,第11和14维特征包含的信息对识别类别非常有用,我们可以只用它们。

    plot_learning_curve(LinearSVC(C=10.0), "LinearSVC(C=10.0) Features: 11&14", X[:, [11, 14]], y, ylim=(0.8, 1.0), train_sizes=np.linspace(.05, 0.2, 5))
    

    特征选择后

    从上图上可以看出,过拟合问题也得到一定程度的缓解。不过我们这是自己观察后,手动选出11和14维特征。那能不能自动进行特征组合和选择呢,其实我们当然可以遍历特征的组合样式,然后再进行特征选择(前提依旧是这里特征的维度不高,如果高的话,遍历所有的组合是一个非常非常非常耗时的过程!!):

    from sklearn.pipeline import Pipeline
    from sklearn.feature_selection import SelectKBest, f_classif
    # SelectKBest(f_classif, k=2) 会根据Anova F-value选出 最好的k=2个特征
    
    plot_learning_curve(Pipeline([("fs", SelectKBest(f_classif, k=2)), # select two features
                                   ("svc", LinearSVC(C=10.0))]), "SelectKBest(f_classif, k=2) + LinearSVC(C=10.0)", X, y, ylim=(0.8, 1.0), train_sizes=np.linspace(.05, 0.2, 5))
    

    自动特征选择

    如果你自己跑一下程序,会发现在我们自己手造的这份数据集上,这个特征筛选的过程超级顺利,但依旧像我们之前提过的一样,这是因为特征的维度不太高。
    从另外一个角度看,我们之所以做特征选择,是想降低模型的复杂度,而更不容易刻画到噪声数据的分布。从这个角度出发,我们还可以有(1)多项式你和模型中降低多项式次数 (2)神经网络中减少神经网络的层数和每层的结点数 ©SVM中增加RBF-kernel的bandwidth等方式来降低模型的复杂度。
    话说回来,即使以上提到的办法降低模型复杂度后,好像能在一定程度上缓解过拟合,但是我们一般还是不建议一遇到过拟合,就用这些方法处理,优先用下面的方法:

    • 增强正则化作用(比如说这里是减小LinearSVC中的C参数)
      正则化是我认为在不损失信息的情况下,最有效的缓解过拟合现象的方法。
    plot_learning_curve(LinearSVC(C=0.1), "LinearSVC(C=0.1)", X, y, ylim=(0.8, 1.0), train_sizes=np.linspace(.05, 0.2, 5))
    

    调整正则化参数

    调整正则化系数后,发现确实过拟合现象有一定程度的缓解,但依旧是那个问题,我们现在的系数是自己敲定的,有没有办法可以自动选择最佳的这个参数呢?可以。我们可以在交叉验证集上做grid-search查找最好的正则化系数(对于大数据样本,我们依旧需要考虑时间问题,这个过程可能会比较慢):

    from sklearn.grid_search import GridSearchCV
    estm = GridSearchCV(LinearSVC(), 
                       param_grid={"C": [0.001, 0.01, 0.1, 1.0, 10.0]})
    plot_learning_curve(estm, "LinearSVC(C=AUTO)", 
                        X, y, ylim=(0.8, 1.0),
                        train_sizes=np.linspace(.05, 0.2, 5))
    print "Chosen parameter on 100 datapoints: %s" % estm.fit(X[:500], y[:500]).best_params_
    

    在500个点得到的结果是:{‘C’: 0.01}
    使用新的C参数,我们再看看学习曲线:
    C取0.01的学习曲线

    对于特征选择的部分,我打算多说几句,我们刚才看过了用sklearn.feature_selection中的SelectKBest来选择特征的过程,也提到了在高维特征的情况下,这个过程可能会非常非常慢。那我们有别的办法可以进行特征选择吗?比如说,我们的分类器自己能否甄别那些特征是对最后的结果有益的?这里有个实际工作中用到的小技巧。

    我们知道:

    • l2正则化,它对于最后的特征权重的影响是,尽量打散权重到每个特征维度上,不让权重集中在某些维度上,出现权重特别高的特征。
    • 而l1正则化,它对于最后的特征权重的影响是,让特征获得的权重稀疏化,也就是对结果影响不那么大的特征,干脆就拿不着权重。

    那基于这个理论,我们可以把SVC中的正则化替换成l1正则化,让其自动甄别哪些特征应该留下权重。

    plot_learning_curve(LinearSVC(C=0.1, penalty='l1', dual=False), "LinearSVC(C=0.1, penalty='l1')", X, y, ylim=(0.8, 1.0), train_sizes=np.linspace(.05, 0.2, 5))
    

    使用l1正则化

    好了,我们一起来看看最后特征获得的权重:

    estm = LinearSVC(C=0.1, penalty='l1', dual=False)
    estm.fit(X[:450], y[:450])  # 用450个点来训练
    print "Coefficients learned: %s" % est.coef_
    print "Non-zero coefficients: %s" % np.nonzero(estm.coef_)[1]
    

    得到结果:

    Coefficients learned: [[ 0.          0.          0.          0.          0.          0.01857999
       0.          0.          0.          0.004135    0.          1.05241369
       0.01971419  0.          0.          0.          0.         -0.05665314
       0.14106505  0.        ]]
    Non-zero coefficients: [5 9 11 12 17 18]
    

    你看,5 9 11 12 17 18这些维度的特征获得了权重,而第11维权重最大,也说明了它影响程度最大。

    3.2.2 欠拟合定位与解决

    我们再随机生成一份数据[1000*20]的数据(但是分布和之前有变化),重新使用LinearSVC来做分类。

    #构造一份环形数据
    from sklearn.datasets import make_circles
    X, y = make_circles(n_samples=1000, random_state=2)
    #绘出学习曲线
    plot_learning_curve(LinearSVC(C=0.25),"LinearSVC(C=0.25)",X, y, ylim=(0.5, 1.0),train_sizes=np.linspace(.1, 1.0, 5))
    

    环形数据的学习曲线

    简直烂出翔了有木有,二分类问题,我们做随机猜测,准确率都有0.5,这比随机猜测都高不了多少!!!怎么办?

    不要盲目动手收集更多资料,或者调整正则化参数。我们从学习曲线上其实可以看出来,训练集上的准确度和交叉验证集上的准确度都很低,这其实就对应了我们说的『欠拟合』状态。别急,我们回到我们的数据,还是可视化看看:

    f = DataFrame(np.hstack((X, y[:, None])), columns = range(2) + ["class"])
    _ = sns.pairplot(df, vars=[0, 1], hue="class", size=3.5)
    

    环形数据可视化

    你发现什么了,数据根本就没办法线性分割!!!,所以你再找更多的数据,或者调整正则化参数,都是无济于事的!!!

    那我们又怎么解决欠拟合问题呢?通常有下面一些方法:

    • 调整你的特征(找更有效的特征!!)
      比如说我们观察完现在的数据分布,然后我们先对数据做个映射:
    # 加入原始特征的平方项作为新特征
    X_extra = np.hstack((X, X[:, [0]]**2 + X[:, [1]]**2))
    
    plot_learning_curve(LinearSVC(C=0.25), "LinearSVC(C=0.25) + distance feature", X_extra, y, ylim=(0.5, 1.0), train_sizes=np.linspace(.1, 1.0, 5))
    

    平方映射后的准确度
    卧槽,少年,这准确率,被吓尿了有木有啊!!!所以你看,选用的特征影响太大了,当然,我们这里是人工模拟出来的数据,分布太明显了,实际数据上,会比这个麻烦一些,但是在特征上面下的功夫还是很有回报的。

    • 使用更复杂一点的模型(比如说用非线性的核函数)
      我们对模型稍微调整了一下,用了一个复杂一些的非线性rbf kernel:
    from sklearn.svm import SVC
    # note: we use the original X without the extra feature
    plot_learning_curve(SVC(C=2.5, kernel="rbf", gamma=1.0), "SVC(C=2.5, kernel='rbf', gamma=1.0)",X, y, ylim=(0.5, 1.0), train_sizes=np.linspace(.1, 1.0, 5))
    

    rbf核SVM学习曲线

    你看,效果依旧很赞。

    3.3 关于大数据样本集和高维特征空间

    我们在小样本的toy dataset上,怎么捣鼓都有好的方法。但是当数据量和特征样本空间膨胀非常厉害时,很多东西就没有那么好使了,至少是一个很耗时的过程。举个例子说,我们现在重新生成一份数据集,但是这次,我们生成更多的数据,更高的特征维度,而分类的类别也提高到5。

    3.3.1 大数据情形下的模型选择与学习曲线

    在上面提到的那样一份数据上,我们用LinearSVC可能就会有点慢了,我们注意到机器学习算法使用图谱推荐我们使用SGDClassifier。其实本质上说,这个模型也是一个线性核函数的模型,不同的地方是,它使用了随机梯度下降做训练,所以每次并没有使用全部的样本,收敛速度会快很多。再多提一点,SGDClassifier对于特征的幅度非常敏感,也就是说,我们在把数据灌给它之前,应该先对特征做幅度调整,当然,用sklearn的StandardScaler可以很方便地完成这一点。

    SGDClassifier每次只使用一部分(mini-batch)做训练,在这种情况下,我们使用交叉验证(cross-validation)并不是很合适,我们会使用相对应的progressive validation:简单解释一下,estimator每次只会拿下一个待训练batch在本次做评估,然后训练完之后,再在这个batch上做一次评估,看看是否有优化。

    #生成大样本,高纬度特征数据
    X, y = make_classification(200000, n_features=200, n_informative=25, n_redundant=0, n_classes=10, class_sep=2, random_state=0)
    
    #用SGDClassifier做训练,并画出batch在训练前后的得分差
    from sklearn.linear_model import SGDClassifier
    est = SGDClassifier(penalty="l2", alpha=0.001)
    progressive_validation_score = []
    train_score = []
    for datapoint in range(0, 199000, 1000):
        X_batch = X[datapoint:datapoint+1000]
        y_batch = y[datapoint:datapoint+1000]
        if datapoint > 0:
            progressive_validation_score.append(est.score(X_batch, y_batch))
        est.partial_fit(X_batch, y_batch, classes=range(10))
        if datapoint > 0:
            train_score.append(est.score(X_batch, y_batch))
        
    plt.plot(train_score, label="train score")
    plt.plot(progressive_validation_score, label="progressive validation score")
    plt.xlabel("Mini-batch")
    plt.ylabel("Score")
    plt.legend(loc='best')  
    plt.show()                     
    

    得到如下的结果:
    SGDClassifier学习曲线

    从这个图上的得分,我们可以看出在50个mini-batch迭代之后,数据上的得分就已经变化不大了。但是好像得分都不太高,所以我们猜测一下,这个时候我们的数据,处于欠拟合状态。我们刚才在小样本集合上提到了,如果欠拟合,我们可以使用更复杂的模型,比如把核函数设置为非线性的,但遗憾的是像rbf核函数是没有办法和SGDClassifier兼容的。因此我们只能想别的办法了,比如这里,我们可以把SGDClassifier整个替换掉了,用多层感知神经网来完成这个任务,我们之所以会想到多层感知神经网,是因为它也是一个用随机梯度下降训练的算法,同时也是一个非线性的模型。当然根据机器学习算法使用图谱,也可以使用**核估计(kernel-approximation)**来完成这个事情。

    3.3.2 大数据量下的可视化

    大样本数据的可视化是一个相对比较麻烦的事情,一般情况下我们都要用到降维的方法先处理特征。我们找一个例子来看看,可以怎么做,比如我们数据集取经典的『手写数字集』,首先找个方法看一眼这个图片数据集。

    #直接从sklearn中load数据集
    from sklearn.datasets import load_digits
    digits = load_digits(n_class=6)
    X = digits.data
    y = digits.target
    n_samples, n_features = X.shape
    print "Dataset consist of %d samples with %d features each" % (n_samples, n_features)
    
    # 绘制数字示意图
    n_img_per_row = 20
    img = np.zeros((10 * n_img_per_row, 10 * n_img_per_row))
    for i in range(n_img_per_row):
        ix = 10 * i + 1
        for j in range(n_img_per_row):
            iy = 10 * j + 1
            img[ix:ix + 8, iy:iy + 8] = X[i * n_img_per_row + j].reshape((8, 8))
    
    plt.imshow(img, cmap=plt.cm.binary)
    plt.xticks([])
    plt.yticks([])
    _ = plt.title('A selection from the 8*8=64-dimensional digits dataset')
    plt.show()
    

    数字示意图

    我们总共有1083个训练样本,包含手写数字(0,1,2,3,4,5),每个样本图片中的像素点平铺开都是64位,这个维度显然是没办法直接可视化的。下面我们基于scikit-learn的示例教程对特征用各种方法做降维处理,再可视化。

    随机投射
    我们先看看,把数据随机投射到两个维度上的结果:

    #import所需的package
    from sklearn import (manifold, decomposition, random_projection)
    rp = random_projection.SparseRandomProjection(n_components=2, random_state=42)
    
    #定义绘图函数
    from matplotlib import offsetbox
    def plot_embedding(X, title=None):
        x_min, x_max = np.min(X, 0), np.max(X, 0)
        X = (X - x_min) / (x_max - x_min)
    
        plt.figure(figsize=(10, 10))
        ax = plt.subplot(111)
        for i in range(X.shape[0]):
            plt.text(X[i, 0], X[i, 1], str(digits.target[i]),
                     color=plt.cm.Set1(y[i] / 10.),
                     fontdict={'weight': 'bold', 'size': 12})
    
        if hasattr(offsetbox, 'AnnotationBbox'):
            # only print thumbnails with matplotlib > 1.0
            shown_images = np.array([[1., 1.]])  # just something big
            for i in range(digits.data.shape[0]):
                dist = np.sum((X[i] - shown_images) ** 2, 1)
                if np.min(dist) < 4e-3:
                    # don't show points that are too close
                    continue
                shown_images = np.r_[shown_images, [X[i]]]
                imagebox = offsetbox.AnnotationBbox(
                    offsetbox.OffsetImage(digits.images[i], cmap=plt.cm.gray_r),
                    X[i])
                ax.add_artist(imagebox)
        plt.xticks([]), plt.yticks([])
        if title is not None:
            plt.title(title)
    
    #记录开始时间
    start_time = time.time()
    X_projected = rp.fit_transform(X)
    plot_embedding(X_projected, "Random Projection of the digits (time: %.3fs)" % (time.time() - start_time))
    

    结果如下:
    2方向随机投射图

    PCA降维
    在维度约减/降维领域有一个非常强大的算法叫做PCA(Principal Component Analysis,主成分分析),它能将原始的绝大多数信息用维度远低于原始维度的几个主成分表示出来。PCA在我们现在的数据集上效果还不错,我们来看看用PCA对原始特征降维至2维后,原始样本在空间的分布状况:

    from sklearn import (manifold, decomposition, random_projection)
    #TruncatedSVD 是 PCA的一种实现
    X_pca = decomposition.TruncatedSVD(n_components=2).fit_transform(X)
    #记录时间
    start_time = time.time()
    plot_embedding(X_pca,"Principal Components projection of the digits (time: %.3fs)" % (time.time() - start_time))
    

    得到的结果如下:
    PCA后的可视化

    我们可以看出,效果还不错,不同的手写数字在2维平面上,显示出了区域集中性。即使它们之间有一定的重叠区域。

    如果我们用一些非线性的变换来做降维操作,从原始的64维降到2维空间,效果更好,比如这里我们用到一个技术叫做t-SNE,sklearn的manifold对其进行了实现:

    from sklearn import (manifold, decomposition, random_projection)
    #降维
    tsne = manifold.TSNE(n_components=2, init='pca', random_state=0)
    start_time = time.time()
    X_tsne = tsne.fit_transform(X)
    #绘图
    plot_embedding(X_tsne,
                   "t-SNE embedding of the digits (time: %.3fs)" % (time.time() - start_time))
    

    非线性降维手写数字分布图

    我们发现结果非常的惊人,似乎这个非线性变换降维过后,仅仅2维的特征,就可以将原始数据的不同类别,在平面上很好地划分开。不过t-SNE也有它的缺点,一般说来,相对于线性变换的降维,它需要更多的计算时间。也不太适合在大数据集上全集使用。

    3.4 损失函数的选择

    损失函数的选择对于问题的解决和优化,非常重要。我们先来看一眼各种不同的损失函数:

    import numpy as np
    import matplotlib.plot as plt
    # 改自http://scikit-learn.org/stable/auto_examples/linear_model/plot_sgd_loss_functions.html
    xmin, xmax = -4, 4
    xx = np.linspace(xmin, xmax, 100)
    plt.plot([xmin, 0, 0, xmax], [1, 1, 0, 0], 'k-',
             label="Zero-one loss")
    plt.plot(xx, np.where(xx < 1, 1 - xx, 0), 'g-',
             label="Hinge loss")
    plt.plot(xx, np.log2(1 + np.exp(-xx)), 'r-',
             label="Log loss")
    plt.plot(xx, np.exp(-xx), 'c-',
             label="Exponential loss")
    plt.plot(xx, -np.minimum(xx, 0), 'm-',
             label="Perceptron loss")
    
    plt.ylim((0, 8))
    plt.legend(loc="upper right")
    plt.xlabel(r"Decision function $f(x)$")
    plt.ylabel("$L(y, f(x))$")
    plt.show()
    

    得到结果图像如下:

    损失函数对比

    不同的损失函数有不同的优缺点:

    • **0-1损失函数(zero-one loss)**非常好理解,直接对应分类问题中判断错的个数。但是比较尴尬的是它是一个非凸函数,这意味着其实不是那么实用。
    • hinge loss(SVM中使用到的)的健壮性相对较高(对于异常点/噪声不敏感)。但是它没有那么好的概率解释。
    • **log损失函数(log-loss)**的结果能非常好地表征概率分布。因此在很多场景,尤其是多分类场景下,如果我们需要知道结果属于每个类别的置信度,那这个损失函数很适合。缺点是它的健壮性没有那么强,相对hinge loss会对噪声敏感一些。
    • 多项式损失函数(exponential loss)(AdaBoost中用到的)对离群点/噪声非常非常敏感。但是它的形式对于boosting算法简单而有效。
    • **感知损失(perceptron loss)**可以看做是hinge loss的一个变种。hinge loss对于判定边界附近的点(正确端)惩罚力度很高。而perceptron loss,只要样本的判定类别结果是正确的,它就是满意的,而不管其离判定边界的距离。优点是比hinge loss简单,缺点是因为不是max-margin boundary,所以得到模型的泛化能力没有hinge loss强。

    4. 总结

    全文到此就结束了。先走马观花看了一遍机器学习的算法,然后给出了对应scikit-learn的『秘密武器』机器学习算法使用图谱,紧接着从了解数据(可视化)选择机器学习算法定位过/欠拟合及解决方法大量极的数据可视化损失函数优缺点与选择等方面介绍了实际机器学习问题中的一些思路和方法。本文和文章机器学习系列(3)_逻辑回归应用之Kaggle泰坦尼克之灾都提及了一些处理实际机器学习问题的思路和方法,有相似和互补之处,欢迎大家参照着看。

    展开全文
  • 弱人工智能近几年取得了重大突破,悄然间,已经成为每个人生活中必不可少的一部分。以我们的智能手机为例,看看到底温...传统的机器学习算法包括决策树、聚类、贝叶斯分类、支持向量机、EM、Adaboost等等。这篇文章将对

    弱人工智能近几年取得了重大突破,悄然间,已经成为每个人生活中必不可少的一部分。以我们的智能手机为例,看看到底温藏着多少人工智能的神奇魔术。

    下图是一部典型的智能手机上安装的一些常见应用程序,可能很多人都猜不到,人工智能技术已经是手机上很多应用程序的核心驱动力。

    图解十大经典的机器学习算法

    图1 智能手机上的相关应用

    传统的机器学习算法包括决策树、聚类、贝叶斯分类、支持向量机、EM、Adaboost等等。这篇文章将对常用算法做常识性的介绍,没有代码,也没有复杂的理论推导,就是图解一下,知道这些算法是什么,它们是怎么应用的。

    人工智能领域知识面广泛,推荐专注于人工智能在线教育的平台—深蓝学院。深蓝学院由中科院自动化所毕业博士团队创建,虽成立半年,但在业界已颇具口碑。

    决策树

    根据一些 feature(特征) 进行分类,每个节点提一个问题,通过判断,将数据分为两类,再继续提问。这些问题是根据已有数据学习出来的,再投入新数据的时候,就可以根据这棵树上的问题,将数据划分到合适的叶子上。

    图解十大经典的机器学习算法

    图2 决策树原理示意图

    随机森林

    在源数据中随机选取数据,组成几个子集:

    图解十大经典的机器学习算法

    图3-1 随机森林原理示意图

    S矩阵是源数据,有1-N条数据,A、B、C 是feature,最后一列C是类别:

    图解十大经典的机器学习算法

    由S随机生成M个子矩阵:

    图解十大经典的机器学习算法

    这M个子集得到 M 个决策树:将新数据投入到这M个树中,得到M个分类结果,计数看预测成哪一类的数目最多,就将此类别作为最后的预测结果。

    图解十大经典的机器学习算法

    图3-2 随机森林效果展示图

    逻辑回归

    当预测目标是概率这样的,值域需要满足大于等于0,小于等于1的,这个时候单纯的线性模型是做不到的,因为在定义域不在某个范围之内时,值域也超出了规定区间。

    图解十大经典的机器学习算法

    图4-1 线性模型图

    所以此时需要这样的形状的模型会比较好:

    图解十大经典的机器学习算法

    图4-2

    那么怎么得到这样的模型呢?

    这个模型需要满足两个条件 “大于等于0”,“小于等于1” 。大于等于0 的模型可以选择绝对值,平方值,这里用指数函数,一定大于0;小于等于1 用除法,分子是自己,分母是自身加上1,那一定是小于1的了。

    图解十大经典的机器学习算法

    图4-3

    再做一下变形,就得到了 logistic regressions 模型:

    图解十大经典的机器学习算法

    图4-4

    通过源数据计算可以得到相应的系数了:

    图解十大经典的机器学习算法

    图4-5

    图解十大经典的机器学习算法

    图4-6 LR模型曲线图

    支持向量机

    要将两类分开,想要得到一个超平面,最优的超平面是到两类的 margin 达到最大,margin就是超平面与离它最近一点的距离,如下图,Z2>Z1,所以绿色的超平面比较好。

    图解十大经典的机器学习算法

    图5 分类问题示意图

    将这个超平面表示成一个线性方程,在线上方的一类,都大于等于1,另一类小于等于-1:

    图解十大经典的机器学习算法

    点到面的距离根据图中的公式计算:

    图解十大经典的机器学习算法

    所以得到total margin的表达式如下,目标是最大化这个margin,就需要最小化分母,于是变成了一个优化问题:

    图解十大经典的机器学习算法

    举个例子,三个点,找到最优的超平面,定义了 weight vector=(2,3)-(1,1):

    图解十大经典的机器学习算法

    得到weight vector为(a,2a),将两个点代入方程,代入(2,3)另其值=1,代入(1,1)另其值=-1,求解出 a 和 截矩 w0 的值,进而得到超平面的表达式。

    图解十大经典的机器学习算法

    a求出来后,代入(a,2a)得到的就是support vector,a和w0代入超平面的方程就是support vector machine。

    朴素贝叶斯

    举个在 NLP 的应用:给一段文字,返回情感分类,这段文字的态度是positive,还是negative:

    图解十大经典的机器学习算法

    图6-1 问题案例

    为了解决这个问题,可以只看其中的一些单词:

    图解十大经典的机器学习算法

    这段文字,将仅由一些单词和它们的计数代表:

    图解十大经典的机器学习算法

    原始问题是:给你一句话,它属于哪一类 ?通过bayes rules变成一个比较简单容易求得的问题:

    图解十大经典的机器学习算法

    问题变成,这一类中这句话出现的概率是多少,当然,别忘了公式里的另外两个概率。例子:单词“love”在positive的情况下出现的概率是 0.1,在negative的情况下出现的概率是0.001。

    图解十大经典的机器学习算法

    图6-2 NB算法结果展示图

    K近邻算法

    给一个新的数据时,离它最近的 k 个点中,哪个类别多,这个数据就属于哪一类。

    例子:要区分“猫”和“狗”,通过“claws”和“sound”两个feature来判断的话,圆形和三角形是已知分类的了,那么这个“star”代表的是哪一类呢?

    图解十大经典的机器学习算法

    图7-1 问题案例

    k=3时,这三条线链接的点就是最近的三个点,那么圆形多一些,所以这个star就是属于猫。

    图解十大经典的机器学习算法

    图7-2 算法步骤展示图

    K均值算法

    先要将一组数据,分为三类,粉色数值大,黄色数值小 。最开始先初始化,这里面选了最简单的 3,2,1 作为各类的初始值 。剩下的数据里,每个都与三个初始值计算距离,然后归类到离它最近的初始值所在类别。

    图解十大经典的机器学习算法

    图8-1 问题案例

    分好类后,计算每一类的平均值,作为新一轮的中心点:

    图解十大经典的机器学习算法

    图8-2

    几轮之后,分组不再变化了,就可以停止了:

    图解十大经典的机器学习算法

    图解十大经典的机器学习算法

    图8-3 算法结果展示

    Adaboost

    Adaboost 是 Boosting 的方法之一。Boosting就是把若干个分类效果并不好的分类器综合起来考虑,会得到一个效果比较好的分类器。

    下图,左右两个决策树,单个看是效果不怎么好的,但是把同样的数据投入进去,把两个结果加起来考虑,就会增加可信度。

    图解十大经典的机器学习算法

    图9-1 算法原理展示

    Adaboost 的例子,手写识别中,在画板上可以抓取到很多features(特征),例如始点的方向,始点和终点的距离等等。

    图解十大经典的机器学习算法

    图9-2

    training的时候,会得到每个feature的weight(权重),例如2和3的开头部分很像,这个feature对分类起到的作用很小,它的权重也就会较小。

    图解十大经典的机器学习算法

    图9-3

    而这个alpha角就具有很强的识别性,这个feature的权重就会较大,最后的预测结果是综合考虑这些feature的结果。

    图解十大经典的机器学习算法

    图9-4

    神经网络

    Neural Networks适合一个input可能落入至少两个类别里:NN由若干层神经元,和它们之间的联系组成。 第一层是input层,最后一层是output层。在hidden层和output层都有自己的classifier。

    图解十大经典的机器学习算法

    图10-1 神经网络结构

    input输入到网络中,被激活,计算的分数被传递到下一层,激活后面的神经层,最后output层的节点上的分数代表属于各类的分数,下图例子得到分类结果为class 1;同样的input被传输到不同的节点上,之所以会得到不同的结果是因为各自节点有不同的weights 和bias,这也就是forward propagation。

    图解十大经典的机器学习算法

    图10-2 算法结果展示

    马尔科夫

    Markov Chains由state(状态)和transitions(转移)组成。例子,根据这一句话 ‘the quick brown fox jumps over the lazy dog’,要得到markov chains。

    步骤,先给每一个单词设定成一个状态,然后计算状态间转换的概率。

    图解十大经典的机器学习算法

    图11-1 马尔科夫原理图

    这是一句话计算出来的概率,当你用大量文本去做统计的时候,会得到更大的状态转移矩阵,例如the后面可以连接的单词,及相应的概率。

    图解十大经典的机器学习算法

    图11-2 算法结果展示

    上述十大类机器学习算法是人工智能发展的践行者,即使在当下,依然在数据挖掘以及小样本的人工智能问题中被广泛使用。


    展开全文
  • 摘要之前一直对机器学习很感兴趣,一直没时间去研究,今天刚好是...这里IT经理网为您总结一下常见的机器学习算法,以供您在工作和学习中参考。 机器学习的算法很多。很多时候困惑人们都是,很多算法是一类算法,而有

    这里写图片描述

    摘要

    之前一直对机器学习很感兴趣,一直没时间去研究,今天刚好是周末,有时间去各大技术论坛看看,刚好看到一篇关于机器学习不错的文章,在这里就分享给大家了.
    机器学习无疑是当前数据分析领域的一个热点内容。很多人在平时的工作中都或多或少会用到机器学习的算法。这里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)。

    结束

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

    源码下载地址

    展开全文
  • 机器学习算法与Python实践之(一)k近邻(KNN)zouxy09@qq.comhttp://blog.csdn.net/zouxy09 机器学习算法与Python实践这个系列主要是参考《机器学习实战》这本书。因为自己想学习Python,然后也想对一些机器学习...

    机器学习算法与Python实践之(一)k近邻(KNN)

    zouxy09@qq.com

    http://blog.csdn.net/zouxy09

     

           机器学习算法与Python实践这个系列主要是参考《机器学习实战》这本书。因为自己想学习Python,然后也想对一些机器学习算法加深下了解,所以就想通过Python来实现几个比较常用的机器学习算法。恰好遇见这本同样定位的书籍,所以就参考这本书的过程来学习了。

     

    一、kNN算法分析

           K最近邻(k-Nearest Neighbor,KNN)分类算法可以说是最简单的机器学习算法了。它采用测量不同特征值之间的距离方法进行分类。它的思想很简单:如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别,则该样本也属于这个类别。

            比如上面这个图,我们有两类数据,分别是蓝色方块和红色三角形,他们分布在一个上图的二维中间中。那么假如我们有一个绿色圆圈这个数据,需要判断这个数据是属于蓝色方块这一类,还是与红色三角形同类。怎么做呢?我们先把离这个绿色圆圈最近的几个点找到,因为我们觉得离绿色圆圈最近的才对它的类别有判断的帮助。那到底要用多少个来判断呢?这个个数就是k了。如果k=3,就表示我们选择离绿色圆圈最近的3个点来判断,由于红色三角形所占比例为2/3,所以我们认为绿色圆是和红色三角形同类。如果k=5,由于蓝色四方形比例为3/5,因此绿色圆被赋予蓝色四方形类。从这里可以看到,k的值还是很重要的。

           KNN算法中,所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。由于KNN方法主要靠周围有限的邻近的样本,而不是靠判别类域的方法来确定所属类别的,因此对于类域的交叉或重叠较多的待分样本集来说,KNN方法较其他方法更为适合。

           该算法在分类时有个主要的不足是,当样本不平衡时,如一个类的样本容量很大,而其他类样本容量很小时,有可能导致当输入一个新样本时,该样本的K个邻居中大容量类的样本占多数。因此可以采用权值的方法(和该样本距离小的邻居权值大)来改进。该方法的另一个不足之处是计算量较大,因为对每一个待分类的文本都要计算它到全体已知样本的距离,才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑,事先去除对分类作用不大的样本。该算法比较适用于样本容量比较大的类域的自动分类,而那些样本容量较小的类域采用这种算法比较容易产生误分[参考机器学习十大算法]。

           总的来说就是我们已经存在了一个带标签的数据库,然后输入没有标签的新数据后,将新数据的每个特征与样本集中数据对应的特征进行比较,然后算法提取样本集中特征最相似(最近邻)的分类标签。一般来说,只选择样本数据库中前k个最相似的数据。最后,选择k个最相似数据中出现次数最多的分类。其算法描述如下:

    1)计算已知类别数据集中的点与当前点之间的距离;

    2)按照距离递增次序排序;

    3)选取与当前点距离最小的k个点;

    4)确定前k个点所在类别的出现频率;

    5)返回前k个点出现频率最高的类别作为当前点的预测分类。

     

    二、Python实现

           对于机器学习而已,Python需要额外安装三件宝,分别是Numpy,scipy和Matplotlib。前两者用于数值计算,后者用于画图。安装很简单,直接到各自的官网下载回来安装即可。安装程序会自动搜索我们的python版本和目录,然后安装到python支持的搜索路径下。反正就python和这三个插件都默认安装就没问题了。

           另外,如果我们需要添加我们的脚本目录进Python的目录(这样Python的命令行就可以直接import),可以在系统环境变量中添加:PYTHONPATH环境变量,值为我们的路径,例如:E:\Python\Machine Learning in Action

     

    2.1、kNN基础实践

           一般实现一个算法后,我们需要先用一个很小的数据库来测试它的正确性,否则一下子给个大数据给它,它也很难消化,而且还不利于我们分析代码的有效性。

          首先,我们新建一个kNN.py脚本文件,文件里面包含两个函数,一个用来生成小数据库,一个实现kNN分类算法。代码如下:

    #########################################
    # kNN: k Nearest Neighbors
    
    # Input:      newInput: vector to compare to existing dataset (1xN)
    #             dataSet:  size m data set of known vectors (NxM)
    #             labels: 	data set labels (1xM vector)
    #             k: 		number of neighbors to use for comparison 
                
    # Output:     the most popular class label
    #########################################
    
    from numpy import *
    import operator
    
    # create a dataset which contains 4 samples with 2 classes
    def createDataSet():
    	# create a matrix: each row as a sample
    	group = array([[1.0, 0.9], [1.0, 1.0], [0.1, 0.2], [0.0, 0.1]])
    	labels = ['A', 'A', 'B', 'B'] # four samples and two classes
    	return group, labels
    
    # classify using kNN
    def kNNClassify(newInput, dataSet, labels, k):
    	numSamples = dataSet.shape[0] # shape[0] stands for the num of row
    
    	## step 1: calculate Euclidean distance
    	# tile(A, reps): Construct an array by repeating A reps times
    	# the following copy numSamples rows for dataSet
    	diff = tile(newInput, (numSamples, 1)) - dataSet # Subtract element-wise
    	squaredDiff = diff ** 2 # squared for the subtract
    	squaredDist = sum(squaredDiff, axis = 1) # sum is performed by row
    	distance = squaredDist ** 0.5
    
    	## step 2: sort the distance
    	# argsort() returns the indices that would sort an array in a ascending order
    	sortedDistIndices = argsort(distance)
    
    	classCount = {} # define a dictionary (can be append element)
    	for i in xrange(k):
    		## step 3: choose the min k distance
    		voteLabel = labels[sortedDistIndices[i]]
    
    		## step 4: count the times labels occur
    		# when the key voteLabel is not in dictionary classCount, get()
    		# will return 0
    		classCount[voteLabel] = classCount.get(voteLabel, 0) + 1
    
    	## step 5: the max voted class will return
    	maxCount = 0
    	for key, value in classCount.items():
    		if value > maxCount:
    			maxCount = value
    			maxIndex = key
    
    	return maxIndex	

           然后我们在命令行中这样测试即可:

    import kNN
    from numpy import * 
    
    dataSet, labels = kNN.createDataSet()
    
    testX = array([1.2, 1.0])
    k = 3
    outputLabel = kNN.kNNClassify(testX, dataSet, labels, 3)
    print "Your input is:", testX, "and classified to class: ", outputLabel
    
    testX = array([0.1, 0.3])
    outputLabel = kNN.kNNClassify(testX, dataSet, labels, 3)
    print "Your input is:", testX, "and classified to class: ", outputLabel

           这时候会输出:

    Your input is: [ 1.2  1.0] and classified to class:  A
    Your input is: [ 0.1  0.3] and classified to class:  B

    2.2、kNN进阶

           这里我们用kNN来分类一个大点的数据库,包括数据维度比较大和样本数比较多的数据库。这里我们用到一个手写数字的数据库,可以到这里下载。这个数据库包括数字0-9的手写体。每个数字大约有200个样本。每个样本保持在一个txt文件中。手写体图像本身的大小是32x32的二值图,转换到txt文件保存后,内容也是32x32个数字,0或者1,如下:

           数据库解压后有两个目录:目录trainingDigits存放的是大约2000个训练数据,testDigits存放大约900个测试数据。

            这里我们还是新建一个kNN.py脚本文件,文件里面包含四个函数,一个用来生成将每个样本的txt文件转换为对应的一个向量,一个用来加载整个数据库,一个实现kNN分类算法。最后就是实现这个加载,测试的函数。

    #########################################
    # kNN: k Nearest Neighbors
    
    # Input:      inX: vector to compare to existing dataset (1xN)
    #             dataSet: size m data set of known vectors (NxM)
    #             labels: data set labels (1xM vector)
    #             k: number of neighbors to use for comparison 
                
    # Output:     the most popular class label
    #########################################
    
    from numpy import *
    import operator
    import os
    
    
    # classify using kNN
    def kNNClassify(newInput, dataSet, labels, k):
    	numSamples = dataSet.shape[0] # shape[0] stands for the num of row
    
    	## step 1: calculate Euclidean distance
    	# tile(A, reps): Construct an array by repeating A reps times
    	# the following copy numSamples rows for dataSet
    	diff = tile(newInput, (numSamples, 1)) - dataSet # Subtract element-wise
    	squaredDiff = diff ** 2 # squared for the subtract
    	squaredDist = sum(squaredDiff, axis = 1) # sum is performed by row
    	distance = squaredDist ** 0.5
    
    	## step 2: sort the distance
    	# argsort() returns the indices that would sort an array in a ascending order
    	sortedDistIndices = argsort(distance)
    
    	classCount = {} # define a dictionary (can be append element)
    	for i in xrange(k):
    		## step 3: choose the min k distance
    		voteLabel = labels[sortedDistIndices[i]]
    
    		## step 4: count the times labels occur
    		# when the key voteLabel is not in dictionary classCount, get()
    		# will return 0
    		classCount[voteLabel] = classCount.get(voteLabel, 0) + 1
    
    	## step 5: the max voted class will return
    	maxCount = 0
    	for key, value in classCount.items():
    		if value > maxCount:
    			maxCount = value
    			maxIndex = key
    
    	return maxIndex	
    
    # convert image to vector
    def  img2vector(filename):
     	rows = 32
     	cols = 32
     	imgVector = zeros((1, rows * cols)) 
     	fileIn = open(filename)
     	for row in xrange(rows):
     		lineStr = fileIn.readline()
     		for col in xrange(cols):
     			imgVector[0, row * 32 + col] = int(lineStr[col])
    
     	return imgVector
    
    # load dataSet
    def loadDataSet():
    	## step 1: Getting training set
    	print "---Getting training set..."
    	dataSetDir = 'E:/Python/Machine Learning in Action/'
    	trainingFileList = os.listdir(dataSetDir + 'trainingDigits') # load the training set
    	numSamples = len(trainingFileList)
    
    	train_x = zeros((numSamples, 1024))
    	train_y = []
    	for i in xrange(numSamples):
    		filename = trainingFileList[i]
    
    		# get train_x
    		train_x[i, :] = img2vector(dataSetDir + 'trainingDigits/%s' % filename) 
    
    		# get label from file name such as "1_18.txt"
    		label = int(filename.split('_')[0]) # return 1
    		train_y.append(label)
    
    	## step 2: Getting testing set
    	print "---Getting testing set..."
    	testingFileList = os.listdir(dataSetDir + 'testDigits') # load the testing set
    	numSamples = len(testingFileList)
    	test_x = zeros((numSamples, 1024))
    	test_y = []
    	for i in xrange(numSamples):
    		filename = testingFileList[i]
    
    		# get train_x
    		test_x[i, :] = img2vector(dataSetDir + 'testDigits/%s' % filename) 
    
    		# get label from file name such as "1_18.txt"
    		label = int(filename.split('_')[0]) # return 1
    		test_y.append(label)
    
    	return train_x, train_y, test_x, test_y
    
    # test hand writing class
    def testHandWritingClass():
    	## step 1: load data
    	print "step 1: load data..."
    	train_x, train_y, test_x, test_y = loadDataSet()
    
    	## step 2: training...
    	print "step 2: training..."
    	pass
    
    	## step 3: testing
    	print "step 3: testing..."
    	numTestSamples = test_x.shape[0]
    	matchCount = 0
    	for i in xrange(numTestSamples):
    		predict = kNNClassify(test_x[i], train_x, train_y, 3)
    		if predict == test_y[i]:
    			matchCount += 1
    	accuracy = float(matchCount) / numTestSamples
    
    	## step 4: show the result
    	print "step 4: show the result..."
    	print 'The classify accuracy is: %.2f%%' % (accuracy * 100)

           测试非常简单,只需要在命令行中输入:

    import kNN
    kNN.testHandWritingClass()

           输出结果如下:

    step 1: load data...
    ---Getting training set...
    ---Getting testing set...
    step 2: training...
    step 3: testing...
    step 4: show the result...
    The classify accuracy is: 98.84%

    展开全文
  • K最近邻(k-Nearest Neighbor,KNN),是一种常用于分类的算法,是有成熟理论支撑的、较为简单的经典机器学习算法之一。该方法的基本思路是:如果一个待分类样本在特征空间中的k个最相似(即特征空间中K近邻)的样本中的...

    K最近邻(k-Nearest Neighbor,KNN),是一种常用于分类的算法,是有成熟理论支撑的、较为简单的经典机器学习算法之一。该方法的基本思路是:如果一个待分类样本在特征空间中的k个最相似(即特征空间中K近邻)的样本中的大多数属于某一个类别,则该样本也属于这个类别,即近朱者赤,近墨者黑。显然,对当前待分类样本的分类,需要大量已知分类的样本的支持,因此KNN是一种有监督学习算法。


    k-最近邻算法是基于实例的学习方法中最基本的,先介绍基于实例学习的相关概念。

    一、基于实例的学习

    1. 已知一系列的训练样例,很多学习方法为目标函数建立起明确的一般化描述;但与此不同,基于实例的学习方法只是简单地把训练样例存储起来。
      从这些实例中泛化的工作被推迟到必须分类新的实例时。每当学习器遇到一个新的查询实例,它分析这个新实例与以前存储的实例的关系,并据此把一个目标函数值赋给新实例。
    2. 基于实例的方法可以为不同的待分类查询实例建立不同的目标函数逼近。事实上,很多技术只建立目标函数的局部逼近,将其应用于与新查询实例邻近的实例,而从不建立在整个实例空间上都表现良好的逼近。当目标函数很复杂,但它可用不太复杂的局部逼近描述时,这样做有显著的优势。
    3. 基于实例方法的不足
      • 分类新实例的开销可能很大。这是因为几乎所有的计算都发生在分类时,而不是在第一次遇到训练样例时。所以,如何有效地索引训练样例,以减少查询时所需计算是一个重要的实践问题。
      • 当从存储器中检索相似的训练样例时,它们一般考虑实例的所有属性。如果目标概念仅依赖于很多属性中的几个时,那么真正最“相似”的实例之间很可能相距甚远。

    二、k-最近邻法算法简介

            K最近邻(K-Nearest Neighbor,KNN)算法,是著名的模式识别统计学方法,在机器学习分类算法中占有相当大的地位。它是一个理论上比较成熟的方法。既是最简单的机器学习算法之一,也是基于实例的学习方法中最基本的,又是最好的文本分类算法之一。

           如果你要了解一个人,可以从他k个最亲近的朋友去推测他是什么样的人。k是一个超参数。k表示最近的k个邻居,是表示个数,不是表示距离。

    超参数k的作用:

                           

                            左图中“?”处绿点是一个待分类的样本,
                            也就是说“?”到底是红色三角形,还是
                            蓝色正方形,暂时还不知道。
                            若令k=3,则“?”被分类为红色三角形。
                            若令k=5,则“?”被分类蓝色正方形。

     

    超参数k对算法的影响:

          k越大,就需要找出越多的邻居,计算量越大。K越大,则相当于做分类时的样本数越多,所以统计意义会更强。但是,如果这k个邻居离待分类样本太远的话,则统计意义就反而变弱了。所以,实践中不宜把k值取得太大。

    K值的选择:(借鉴李航--统计学习方法)

    K值的选择会对K近邻算法的结果产生重大的影响。

    K值较小:就相当于用较小的领域中的训练实例进行预测,“学习”近似误差会减小K值的减小就意味着整体模型变得复杂,容易发生过拟合; 

    K值较大:就相当于用较大领域中的训练实例进行预测,其优点是可以减少学习的估计误差,但缺点是学习的近似误差会增大。这时候,与输入实例较远(不相似的)训练实例也会对预测器作用,使预测发生错误,且K值的增大就意味着整体的模型变得简单。k很大,那么可以减少干扰数据的影响,但是此时就导致了系统性偏差(K值太小会造成过度拟合),比如如果取k为总的训练数据数,那么每次投票肯定都是训练数据中多的类别胜利。显然训练数据的系统性偏差会影响结果。 

    通常情况下,我们需要对 k 经过多种尝试,来决定到底使用多大的 k 来作为最终参数。k通常会在3~10直接取值,或者是k等于训练数据的平方根。比如15个数据,可能会取k=4。 

    在实际应用中,一般采用交叉验证法(简单来说,就是一部分样本做训练集,一部分做测试集)来选择最优的K值。 

    三、K近邻算法的原理

    首先,K近邻算法的推导实在是过于简单,这里就只描述下算法的设计流程。

    kNN分类算法的具体步骤如下:
    1)计算待分类样本点与所有已标注样本点之间的距离(如果样本多将非常耗时、耗空间)
    2)按照距离从小到大排序(对于每一个待分类的样本点,都要排序。耗时、耗空间)
    3)选取与待分类样本点距离最小的k个点
    4)确定前k个点中,每个类别的出现次数
    5)返回次数最高的那个类别

    这里要注意,距离的计算方法。

    由于sklearn中有现成的算法,这里根据算法中的参数来进行说明,我们使用sklearn.neighbors.KNeighborsClassifier就可以是实现上小结,我们实现的k-近邻算法。

    KNeighborsClassifier函数一共有8个参数

    class sklearn.neighbors.KNeighborsClassifier(n_neighbors=5weights='uniform'algorithm='auto'leaf_size=30p=2

    metric='minkowski'metric_params=Nonen_jobs=1**kwargs)

    KNneighborsClassifier参数说明:

    • n_neighbors:默认为5,就是k-NN的k的值,选取最近的k个点。
    • weights:默认是uniform,参数可以是uniform、distance,也可以是用户自己定义的函数。uniform是均等的权重,就说所有的邻近点的权重都是相等的distance是不均等的权重,距离近的点比距离远的点的影响大。用户自定义的函数,接收距离的数组,返回一组维数相同的权重。
    • algorithm:快速k近邻搜索算法,默认参数为auto,可以理解为算法自己决定合适的搜索算法。除此之外,用户也可以自己指定搜索算法ball_tree、kd_tree、brute方法进行搜索brute是蛮力搜索,也就是线性扫描当训练集很大时,计算非常耗时kd_tree,构造kd树存储数据以便对其进行快速检索的树形数据结构,kd树也就是数据结构中的二叉树。以中值切分构造的树,每个结点是一个超矩形,在维数小于20时效率高ball tree是为了克服kd树高纬失效而发明的,其构造过程是以质心C和半径r分割样本空间,每个节点是一个超球体。
    • leaf_size:默认是30,这个是构造的kd树和ball树的大小。这个值的设置会影响树构建的速度和搜索速度,同样也影响着存储树所需的内存大小。需要根据问题的性质选择最优的大小。
    • metric:用于距离度量,默认度量是minkowski,也就是p=2的欧氏距离(欧几里德度量)。
    • p:距离度量公式。在上小结,我们使用欧氏距离公式进行距离度量。除此之外,还有其他的度量方法,例如曼哈顿距离。这个参数默认为2,也就是默认使用欧式距离公式进行距离度量。也可以设置为1,使用曼哈顿距离公式进行距离度量。
    • metric_params:距离公式的其他关键参数,这个可以不管,使用默认的None即可。
    • n_jobs:并行处理设置。默认为1,临近点搜索并行工作数。如果为-1,那么CPU的所有cores都用于并行工作。

    闵可夫斯基距离:minkowski

    闵可夫斯基距离(Minkowski distance)是衡量数值点之间距离的一种非常常见的方法,假设数值点 P 和 Q 坐标如下:

    那么,闵可夫斯基距离定义为:

    该距离最常用的 p 是 2 和 1, 前者是欧几里得距离(Euclidean distance),后者是曼哈顿距离(Manhattan distance)。假设在曼哈顿街区乘坐出租车从 P 点到 Q 点,白色表示高楼大厦,灰色表示街道:

    绿色的斜线表示欧几里得距离,在现实中是不可能的。其他三条折线表示了曼哈顿距离,这三条折线的长度是相等的。

    其中,在计算距离的过程中,有几下几点需要特别注意:

    • 对于类别性变量,在计算之前需要先进行独热编码,转化为距离计算可以理解的数字型变量
    • 对于连续性变量,可以进行无量纲化的处理。

    四、KNN算法实现

    4.1 KNN算法蛮力实现

    首先我们看看最想当然的方式。

           既然我们要找到k个最近的邻居来做预测,那么我们只需要计算预测样本和所有训练集中的样本的距离,然后计算出最小的k个距离即可,接着多数表决,很容易做出预测。这个方法的确简单直接,在样本量少,样本特征少的时候有效。但是在实际运用中很多时候用不上,为什么呢?因为我们经常碰到样本的特征数有上千以上,样本量有几十万以上,如果我们这要去预测少量的测试集样本,算法的时间效率很成问题。因此,这个方法我们一般称之为蛮力实现。比较适合于少量样本的简单模型的时候用

       既然蛮力实现在特征多,样本多的时候很有局限性,那么我们有没有其他的好办法呢?有!这里我们讲解两种办法,一个是KD树实现,一个是球树实现。

    4.2 KD树实现原理

           KD树算法没有一开始就尝试对测试样本分类,而是先对训练集建模建立的模型就是KD树建好了模型再对测试集做预测。所谓的KD树就是K个特征维度的树,注意这里的K和KNN中的K的意思不同。KNN中的K代表特征输出类别,KD树中的K代表样本特征的维数。为了防止混淆,后面我们称特征维数为n。

      KD树算法包括三步,第一步是建树,第二部是搜索最近邻,最后一步是预测

    KD树的建立:

       我们首先来看建树的方法。KD树建树采用的是从m个样本的n维特征中,分别计算n个特征的取值的方差,用方差最大的第k维特征n_{k}来作为根节点。对于这个特征,我们选择特征n_{k}的取值的中位数n_{kv}对应的样本作为划分点,对于所有第k维特征的取值小于n_{kv}的样本,我们划入左子树,对于第k维特征的取值大于等于nkvnkv的样本,我们划入右子树,对于左子树和右子树,我们采用和刚才同样的办法来找方差最大的特征来做根节点递归的生成KD树。

    比如我们有二维样本6个,{(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)},构建kd树的具体步骤为:

       1)找到划分的特征。6个数据点在x,y维度上的数据方差分别为6.97,5.37,所以在x轴上方差更大,用第1维特征建树。

       2)确定划分点(7,2)。根据x维上的值将数据排序,6个数据的中值(所谓中值,即中间大小的值)为7,所以划分点的数据是(7,2)。这样,该节点的分割超平面就是通过(7,2)并垂直于:划分点维度的直线x=7;(很显然,中位数为6 ,这里选择(5,4)或者(7,2)都是可以的。这种情况任选一个即可)

       3)确定左子空间和右子空间。 分割超平面x=7将整个空间分为两部分:x<=7的部分为左子空间,包含3个节点={(2,3),(5,4),(4,7)};另一部分为右子空间,包含2个节点={(9,6),(8,1)}。

       4)用同样的办法划分左子树的节点{(2,3),(5,4),(4,7)}和右子树的节点{(9,6),(8,1)}。最终得到KD树。

        最后得到的KD树如下:

    KD树搜索最近邻

          当我们生成KD树以后,就可以去预测测试集里面的样本目标点了。对于一个目标点,我们首先在KD树里面找到包含目标点的叶子节点。目标点为圆心,以目标点到叶子节点样本实例的距离为半径,得到一个超球体最近邻的点一定在这个超球体内部。然后返回叶子节点的父节点,检查另一个子节点包含的超矩形体是否和超球体相交,如果相交就到这个子节点寻找是否有更加近的近邻,有的话就更新最近邻。如果不相交那就简单了,我们直接返回父节点的父节点,在另一个子树继续搜索最近邻。当回溯到根节点时,算法结束,此时保存的最近邻节点就是最终的最近邻。

       从上面的描述可以看出,KD树划分后可以大大减少无效的最近邻搜索,很多样本点由于所在的超矩形体和超球体不相交,根本不需要计算距离。大大节省了计算时间。

      我们用3.1建立的KD树,来看对点(2,4.5)找最近邻的过程。

      先进行二叉查找,先从(7,2)查找到(5,4)节点,在进行查找时是由y = 4为分割超平面的,由于查找点为y值为4.5,因此进入右子空间查找到(4,7),形成搜索路径<(7,2),(5,4),(4,7)>,但 (4,7)与目标查找点的距离为3.202,而(5,4)与查找点之间的距离为3.041,所以(5,4)为查询点的最近点; 以(2,4.5)为圆心,以3.041为半径作圆,如下图所示。可见该圆和y = 4超平面交割,所以需要进入(5,4)左子空间进行查找,也就是将(2,3)节点加入搜索路径中得<(7,2),(2,3)>;于是接着搜索至(2,3)叶子节点,(2,3)距离(2,4.5)比(5,4)要近,所以最近邻点更新为(2,3),最近距离更新为1.5;回溯查找至(5,4),直到最后回溯到根结点(7,2)的时候,以(2,4.5)为圆心1.5为半径作圆,并不和x = 7分割超平面交割,如下图所示。至此,搜索路径回溯完,返回最近邻点(2,3),最近距离1.5。

    对应的图如下:

    4.3 球树实现原理

           KD树算法虽然提高了KNN搜索的效率,但是在某些时候效率并不高,比如当处理不均匀分布的数据集时,不管是近似方形,还是矩形,甚至正方形,都不是最好的使用形状,因为他们都有角。一个例子如下图:

             如果黑色的实例点离目标点星点再远一点,那么虚线圆会如红线所示那样扩大,导致与左上方矩形的右下角相交,既然相 交了,那么就要检查这个左上方矩形,而实际上,最近的点离星点的距离很近,检查左上方矩形区域已是多余。于此我们看见,KD树把二维平面划分成一个一个矩形,但矩形区域的角却是个难以处理的问题。

      为了优化超矩形体导致的搜索效率的问题,牛人们引入了球树,这种结构可以优化上面的这种问题。

      我们现在来看看球树建树和搜索最近邻的算法。

    球树的建立

    球树,顾名思义,就是每个分割块都是超球体,而不是KD树里面的超矩形体。

    我们看看具体的建树流程:

      1) 先构建一个超球体,这个超球体是可以包含所有样本的最小球体。

      2) 从球中选择一个离球的中心最远的点,然后选择第二个点离第一个点最远,将球中所有的点分配到离这两个聚类中心最近的一个上,然后计算每个聚类的中心,以及聚类能够包含它所有数据点所需的最小半径。这样我们得到了两个子超球体,和KD树里面的左右子树对应。(PS:这里选择两个点后,就以这两个点来聚类,所以先确定的是以这两个点为中心来计算其他点到该中心的距离。当所有点都确定自己的中心后,再重新计算一次该超球体的半径和球心。

        3)对于这两个子超球体,递归执行步骤2). 最终得到了一个球树。

        可以看出KD树和球树类似,主要区别在于球树得到的是节点样本组成的最小超球体,而KD得到的是节点样本组成的超矩形体,这个超球体要与对应的KD树的超矩形体小,这样在做最近邻搜索的时候,可以避免一些无谓的搜索。

    五、KNN算法小结

      KNN算法是很基本的机器学习算法了,它非常容易学习,在维度很高的时候也有很好的分类效率,因此运用也很广泛,这里总结下KNN的优缺点。

      KNN的主要优点有:

      1) 理论成熟,思想简单,既可以用来做分类也可以用来做回归

      2) 可用于非线性分类

      3) 训练时间复杂度比支持向量机之类的算法低,仅为O(n)

      4) 和朴素贝叶斯之类的算法比,对数据没有假设,准确度高,对异常点不敏感

      5) 由于KNN方法主要靠周围有限的邻近的样本,而不是靠判别类域的方法来确定所属类别的,因此对于类域的交叉或重叠较多的待分样本集来说,KNN方法较其他方法更为适合

      6)该算法比较适用于样本容量比较大的类域的自动分类,而那些样本容量较小的类域采用这种算法比较容易产生误分

      KNN的主要缺点有:

      1)计算量大,尤其是特征数非常多的时候

      2)样本不平衡的时候,对稀有类别的预测准确率低

      3)KD树,球树之类的模型建立需要大量的内存

      4)使用懒散学习方法,基本上不学习,导致预测时速度比起逻辑回归之类的算法慢

      5)相比决策树模型,KNN模型可解释性不强

    六、适用场合

    1. kNN是一个有监督算法,需要有标注好的样本。
    2. 从算法复杂度的角度来看,更适合特征个数较少,已标注样本数量不是过多的场合。
    3. kNN的可解释性较差。无法给出决策树那样的规则,也无法象逻辑回归那样对数据给出整齐的划分。事实上,kNN更适合处理一些分类规则相对复杂的问题。

    参考资料:

    https://blog.csdn.net/qq_36330643/article/details/77532161

    http://cuijiahua.com/blog/2017/11/ml_1_knn.html

    https://www.cnblogs.com/pinard/p/6061661.html

     

    展开全文
  • 一、聚类算法的简介
  • 机器学习算法集锦

    2017-02-20 22:52:42
    机器学习机器学习(Machine Learning, ML)是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、算法复杂度理论等多门学科。专门研究计算机怎样模拟或实现人类的学习行为,以获取新的知识或技能,重新组织已有...
  • 本文总结一下常见的机器学习算法,以供参考。机器学习的算法很多,很多算法是一类算法,而有些算法又是从其他算法中延伸出来的。这里从两个方面进行总结,第一个方面是学习的方式,第二个方面是算法的类似性。 一、...
  • 机器学习算法地图

    2019-10-21 14:29:12
    其它机器学习、深度学习算法的...文章《机器学习算法地图》系SIGAI原创,仅供个人学习使用,未经允许,不得转载,不能用于商业目的。如需获取原版PDF全文,可搜索关注VX公众号SIGAICN。(https://0x9.me/dxRg5) ...
  • 机器学习算法与Python实践之(四)支持向量机(SVM)实现zouxy09@qq.comhttp://blog.csdn.net/zouxy09 机器学习算法与Python实践这个系列主要是参考《机器学习实战》这本书。因为自己想学习Python,然后也想对一些...
  • 机器学习算法之分类

    2018-05-24 19:35:32
    机器学习算法是一类能从数据中自动分析获得规律,并利用规律对未知数据进行预测的算法 [1]。机器学习(Machine Learning)是人工智能(AI)中很重要的一部分,因为在目前的实践过程中,大多数人工智能问题是由机...
  • 写这篇文章的目的,就是希望它可以让有志于从事数据科学和机器...我也会写下对于各种机器学习算法的一些个人理解,并且提供R和Python的执行代码。读完这篇文章,读者们至少可以行动起来亲手试试写一个机器学习的程序。
  • K-NN算法
  • 在本指南中,我们将通过现代机器学习算法进行实用,简洁的介绍。虽然存在其他这样的列表,但它们并没有真正解释每种算法的实际权衡,我们希望在这里做。我们将根据我们的经验讨论每种算法的优缺点。 对机器学习算法...
  • 机器学习算法太多了,分类、回归、聚类、推荐、图像识别领域等等,要想找到一个合适算法真的不容易,所以在实际应用中,我们一般都是采用启发式学习方式来实验。通常最开始我们都会选择大家普遍认同的算法,诸如SVM...
  • 机器学习(1) —- 机器学习算法综述 个人博客,欢迎参观: http://www.ioqian.top/about/ 本着拓展知识的态度看了机器学习的一个视频,把自己的理解做个总结,分为3部分 1.机器学习算法分类,主要看分类,...
  • 机器学习算法实战教程,包括各种常用机器学习算法,该课程教学视频以手写形式+普通话授课(类似斯坦福大学授课方式),+Python代码。经典算法进行原理推导与案例实战双管齐下,具体课程内容包括K-Means算法、KNN算法...
  • 我应该使用哪种机器学习算法? 该资源主要面向初学者到中级数据科学家或分析师,他们有兴趣识别和应用机器学习算法来解决他们感兴趣的问题。 当面对各种各样的机器学习算法时,初学者提出的一个典型问题是“我应该...
  • 机器学习算法虽多,却没有什么普适的解决方案。决策树、随机森林、朴素贝叶斯、深度网络等等等等,是不是有时候觉得挑花了眼呢?福利来啦~本文将教你慧眼识精,快速挑选出满意的算法!机器学习既是一门科学,也是一...
  • 机器学习算法与Python实践之(五)k均值聚类(k-means)zouxy09@qq.comhttp://blog.csdn.net/zouxy09 机器学习算法与Python实践这个系列主要是参考《机器学习实战》这本书。因为自己想学习Python,然后也想对一些...
1 2 3 4 5 ... 20
收藏数 114,626
精华内容 45,850