回归、分类与聚类：三大方向剖解机器学习算法的优缺点
转自：http://blog.csdn.net/starzhou/article/details/72614795
在本教程中，作者对现代机器学习算法进行一次简要的实战梳理。虽然类似的总结有很多，但是它们都没有真正解释清楚每个算法在实践中的好坏，而这正是本篇梳理希望完成的。因此本文力图基于实践中的经验，讨论每个算法的优缺点。而机器之心也在文末给出了这些算法的具体实现细节。
对机器学习算法进行分类不是一件容易的事情，总的来看，有如下几种方式：生成与判别、参数与非参数、监督与非监督等等。
然而，就实践经验来看，这些都不是实战过程中最有效的分类算法的方式。因为对于应用机器学习而言，开发者一般会在脑海中有一个最终目标，比如预测一个结果或是对你的观察进行分类。
因此，我们想介绍另一种对算法进行分类的路数，其基于机器学习任务来分类。
没有免费午餐定理
在机器学习中，有个定理被称为「没有免费的午餐」。简而言之，就是说没有一个算法可以完美解决所有问题，而且这对于监督学习（即对预测的建模）而言尤其如此。
举个例子，你不能说神经网络就一定任何时候都比决策树优秀，反过来也是。这其中存在很多影响因素，比如你数据集的规模和结构。
所以，当你使用一个固定的数据测试集来评估性能，挑选最适合算法时，你应该针对你的问题尝试多种不同的算法。
当然，你所使用的算法必须要适合于你试图解决的问题，这也就有了如何选择正确的机器学习任务这一问题。做个类比，如果你需要打扫你的房子，你可能会用吸尘器、扫帚或者是拖把，但是你绝不会掏出一把铲子然后开始挖地。
机器学习任务
在本次梳理中，我们将涵盖目前「三大」最常见机器学习任务：
回归方法
分类方法
聚类方法
说明：
本文的梳理不会涵盖具体领域的问题，比如自然语言处理。
本文也不会对每个算法都进行梳理。因为现有太多算法，而且新的算法也层出不穷。然而，这份清单将向读者展现对每个任务而言目前具有代表性的算法概览。
1、回归方法
回归方法是一种对数值型连续随机变量进行预测和建模的监督学习算法。使用案例一般包括房价预测、股票走势或测试成绩等连续变化的案例。
回归任务的特点是标注的数据集具有数值型的目标变量。也就是说，每一个观察样本都有一个数值型的标注真值以监督算法。
1.1线性回归（正则化）
线性回归是处理回归任务最常用的算法之一。该算法的形式十分简单，它期望使用一个超平面拟合数据集（只有两个变量的时候就是一条直线）。如果数据集中的变量存在线性关系，那么其就能拟合地非常好。
在实践中，简单的线性回归通常被使用正则化的回归方法（LASSO、Ridge和Elastic-Net）所代替。正则化其实就是一种对过多回归系数采取惩罚以减少过拟合风险的技术。当然，我们还得确定惩罚强度以让模型在欠拟合和过拟合之间达到平衡。
优点：线性回归的理解与解释都十分直观，并且还能通过正则化来降低过拟合的风险。另外，线性模型很容易使用随机梯度下降和新数据更新模型权重。
缺点：线性回归在变量是非线性关系的时候表现很差。并且其也不够灵活以捕捉更复杂的模式，添加正确的交互项或使用多项式很困难并需要大量时间。
Python实现：http://scikit-learn.org/stable/modules/linear_model.html
R实现：https://cran.r-project.org/web/packages/glmnet/index.html
1.2回归树（集成方法）
回归树（决策树的一种）通过将数据集重复分割为不同的分支而实现分层学习，分割的标准是最大化每一次分离的信息增益。这种分支结构让回归树很自然地学习到非线性关系。
集成方法，如随机森林（RF）或梯度提升树（GBM）则组合了许多独立训练的树。这种算法的主要思想就是组合多个弱学习算法而成为一种强学习算法，不过这里并不会具体地展开。在实践中RF通常很容易有出色的表现，而GBM则更难调参，不过通常梯度提升树具有更高的性能上限。
优点：决策树能学习非线性关系，对异常值也具有很强的鲁棒性。集成学习在实践中表现非常好，其经常赢得许多经典的（非深度学习）机器学习竞赛。
缺点：无约束的，单棵树很容易过拟合，因为单棵树可以保留分支（不剪枝），并直到其记住了训练数据。集成方法可以削弱这一缺点的影响。
随机森林python实现：http://scikit-learn.org/stable/modules/ensemble.html#random-forests
随机森林R实现：https://cran.r-project.org/web/packages/randomForest/index.html
梯度提升树Python实现：http://scikit-learn.org/stable/modules/ensemble.html#classification
梯度提升树R实现：https://cran.r-project.org/web/packages/gbm/index.html
1.3深度学习
深度学习是指能学习极其复杂模式的多层神经网络。该算法使用在输入层和输出层之间的隐藏层对数据的中间表征建模，这也是其他算法很难学到的部分。
深度学习还有其他几个重要的机制，如卷积和drop-out等，这些机制令该算法能有效地学习到高维数据。然而深度学习相对于其他算法需要更多的数据，因为其有更大数量级的参数需要估计。
优点：深度学习是目前某些领域最先进的技术，如计算机视觉和语音识别等。深度神经网络在图像、音频和文本等数据上表现优异，并且该算法也很容易对新数据使用反向传播算法更新模型参数。它们的架构（即层级的数量和结构）能够适应于多种问题，并且隐藏层也减少了算法对特征工程的依赖。
缺点：深度学习算法通常不适合作为通用目的的算法，因为其需要大量的数据。实际上，深度学习通常在经典机器学习问题上并没有集成方法表现得好。另外，其在训练上是计算密集型的，所以这就需要更富经验的人进行调参（即设置架构和超参数）以减少训练时间。
Python资源：https://keras.io/
R资源：http://mxnet.io/
1.4最近邻算法
最近邻算法是「基于实例的」，这就意味着其需要保留每一个训练样本观察值。最近邻算法通过搜寻最相似的训练样本来预测新观察样本的值。
而这种算法是内存密集型，对高维数据的处理效果并不是很好，并且还需要高效的距离函数来度量和计算相似度。在实践中，基本上使用正则化的回归或树型集成方法是最好的选择。
2、分类方法
分类方法是一种对离散型随机变量建模或预测的监督学习算法。使用案例包括邮件过滤、金融欺诈和预测雇员异动等输出为类别的任务。
许多回归算法都有与其相对应的分类算法，分类算法通常适用于预测一个类别（或类别的概率）而不是连续的数值。
2.1Logistic回归（正则化）
Logistic回归是与线性回归相对应的一种分类方法，且该算法的基本概念由线性回归推导而出。Logistic回归通过Logistic函数（即Sigmoid函数）将预测映射到0到1中间，因此预测值就可以看成某个类别的概率。
该模型仍然还是「线性」的，所以只有在数据是线性可分（即数据可被一个超平面完全分离）时，算法才能有优秀的表现。同样Logistic模型能惩罚模型系数而进行正则化。
优点：输出有很好的概率解释，并且算法也能正则化而避免过拟合。Logistic模型很容易使用随机梯度下降和新数据更新模型权重。
缺点：Logistic回归在多条或非线性决策边界时性能比较差。
Python实现：http://scikit-learn.org/stable/modules/linear_model.html#logistic-regression
R实现：https://cran.r-project.org/web/packages/glmnet/index.html
2.2分类树（集成方法）
与回归树相对应的分类算法是分类树。它们通常都是指决策树，或更严谨一点地称之为「分类回归树（CART）」，这也就是非常著名的CART的算法。
简单的随机森林
优点：同回归方法一样，分类树的集成方法在实践中同样表现十分优良。它们通常对异常数据具有相当的鲁棒性和可扩展性。因为它的层级结构，分类树的集成方法能很自然地对非线性决策边界建模。
缺点：不可约束，单棵树趋向于过拟合，使用集成方法可以削弱这一方面的影响。
随机森林Python实现：http://scikit-learn.org/stable/modules/ensemble.html#regression
随机森林R实现：https://cran.r-project.org/web/packages/randomForest/index.html
梯度提升树Python实现：http://scikit-learn.org/stable/modules/ensemble.html#classification
梯度提升树R实现：https://cran.r-project.org/web/packages/gbm/index.html
2.3深度学习
深度学习同样很容易适应于分类问题。实际上，深度学习应用地更多的是分类任务，如图像分类等。
优点：深度学习非常适用于分类音频、文本和图像数据。
缺点：和回归问题一样，深度神经网络需要大量的数据进行训练，所以其也不是一个通用目的的算法。
Python资源：https://keras.io/
R资源：http://mxnet.io/
2.4支持向量机
支持向量机（SVM）可以使用一个称之为核函数的技巧扩展到非线性分类问题，而该算法本质上就是计算两个称之为支持向量的观测数据之间的距离。SVM算法寻找的决策边界即最大化其与样本间隔的边界，因此支持向量机又称为大间距分类器。
支持向量机中的核函数采用非线性变换，将非线性问题变换为线性问题
例如，SVM使用线性核函数就能得到类似于logistic回归的结果，只不过支持向量机因为最大化了间隔而更具鲁棒性。因此，在实践中，SVM最大的优点就是可以使用非线性核函数对非线性决策边界建模。
优点：SVM能对非线性决策边界建模，并且有许多可选的核函数形式。SVM同样面对过拟合有相当大的鲁棒性，这一点在高维空间中尤其突出。
缺点：然而，SVM是内存密集型算法，由于选择正确的核函数是很重要的，所以其很难调参，也不能扩展到较大的数据集中。目前在工业界中，随机森林通常优于支持向量机算法。
Python实现：http://scikit-learn.org/stable/modules/svm.html#classification
R实现：https://cran.r-project.org/web/packages/kernlab/index.html
2.5朴素贝叶斯
朴素贝叶斯（NB）是一种基于贝叶斯定理和特征条件独立假设的分类方法。本质上朴素贝叶斯模型就是一个概率表，其通过训练数据更新这张表中的概率。为了预测一个新的观察值，朴素贝叶斯算法就是根据样本的特征值在概率表中寻找最大概率的那个类别。
之所以称之为「朴素」，是因为该算法的核心就是特征条件独立性假设（每一个特征之间相互独立），而这一假设在现实世界中基本是不现实的。
优点：即使条件独立性假设很难成立，但朴素贝叶斯算法在实践中表现出乎意料地好。该算法很容易实现并能随数据集的更新而扩展。
缺点：因为朴素贝叶斯算法太简单了，所以其也经常被以上列出的分类算法所替代。
Python实现：http://scikit-learn.org/stable/modules/naive_bayes.html
R实现：https://cran.r-project.org/web/packages/naivebayes/index.html
3、聚类
聚类是一种无监督学习任务，该算法基于数据的内部结构寻找观察样本的自然族群（即集群）。使用案例包括细分客户、新闻聚类、文章推荐等。
因为聚类是一种无监督学习（即数据没有标注），并且通常使用数据可视化评价结果。如果存在「正确的回答」（即在训练集中存在预标注的集群），那么分类算法可能更加合适。
3.1K均值聚类
K均值聚类是一种通用目的的算法，聚类的度量基于样本点之间的几何距离（即在坐标平面中的距离）。集群是围绕在聚类中心的族群，而集群呈现出类球状并具有相似的大小。聚类算法是我们推荐给初学者的算法，因为该算法不仅十分简单，而且还足够灵活以面对大多数问题都能给出合理的结果。
优点：K均值聚类是最流行的聚类算法，因为该算法足够快速、简单，并且如果你的预处理数据和特征工程十分有效，那么该聚类算法将拥有令人惊叹的灵活性。
缺点：该算法需要指定集群的数量，而K值的选择通常都不是那么容易确定的。另外，如果训练数据中的真实集群并不是类球状的，那么K均值聚类会得出一些比较差的集群。
Python实现：http://scikit-learn.org/stable/modules/clustering.html#k-means
R实现：https://stat.ethz.ch/R-manual/R-devel/library/stats/html/kmeans.html
3.2AffinityPropagation聚类
AP聚类算法是一种相对较新的聚类算法，该聚类算法基于两个样本点之间的图形距离（graphdistances）确定集群。采用该聚类方法的集群拥有更小和不相等的大小。
优点：该算法不需要指出明确的集群数量（但是需要指定「samplepreference」和「damping」等超参数）。
缺点：AP聚类算法主要的缺点就是训练速度比较慢，并需要大量内存，因此也就很难扩展到大数据集中。另外，该算法同样假定潜在的集群是类球状的。
Python实现：http://scikit-learn.org/stable/modules/clustering.html#affinity-propagation
R实现：https://cran.r-project.org/web/packages/apcluster/index.html
3.3层次聚类（Hierarchical/Agglomerative）
层次聚类是一系列基于以下概念的聚类算法：
最开始由一个数据点作为一个集群
对于每个集群，基于相同的标准合并集群
重复这一过程直到只留下一个集群，因此就得到了集群的层次结构。
优点：层次聚类最主要的优点是集群不再需要假设为类球形。另外其也可以扩展到大数据集。
缺点：有点像K均值聚类，该算法需要设定集群的数量（即在算法完成后需要保留的层次）。
Python实现：http://scikit-learn.org/stable/modules/clustering.html#hierarchical-clustering
R实现：https://stat.ethz.ch/R-manual/R-devel/library/stats/html/hclust.html
3.4DBSCAN
DBSCAN是一个基于密度的算法，它将样本点的密集区域组成一个集群。最近还有一项被称为HDBSCAN的新进展，它允许改变密度集群。
优点：DBSCAN不需要假设集群为球状，并且它的性能是可扩展的。此外，它不需要每个点都被分配到一个集群中，这降低了集群的异常数据。
缺点：用户必须要调整「epsilon」和「min_sample」这两个定义了集群密度的超参数。DBSCAN对这些超参数非常敏感。
Python实现：http://scikit-learn.org/stable/modules/clustering.html#dbscan
R实现：https://cran.r-project.org/web/packages/dbscan/index.html
结语
本文从回归问题、分类问题和聚类问题三个角度下初步了解了各个算法的优缺点，也基本了解了那些算法到底是什么。但以上每一个算法都有更多的概念和细节没有展现出来，我们不能知道它们的损失函数是什么、训练目标是什么、权重更新策略是什么等等一些列问题。因此我们希望能从机器之心历来文章中搜寻一些，为有兴趣的读者提供这些算法的具体细节。
线性回归：
初学TensorFlow机器学习：如何实现线性回归？（附练习题）
从头开始：用Python实现带随机梯度下降的线性回归
决策树（集成方法）：
从头开始：用Python实现随机森林算法
从头开始：用Python实现决策树算法
支持向量机：
详解支持向量机（附学习资源）
深度学习：
深度神经网络全面概述：从基本概念到实际模型和硬件基础
深度学习与神经网络全局概览：核心技术的发展历程
聚类算法：
机器理解大数据的秘密：聚类算法深度详解
最后，不论是基本概念还是具体算法，最重要的就是实践。不实践这些算法就永远不能发现哪些地方没有掌握，因此希望本文能有助于各位读者实践自己的算法。
KNN算法，K聚类的优缺点
KNN适用数据范围:数值型和标称型（目标变量的结果只在有限目标集中取值，如真与假，标称型目标变量主要用于分类)
优点
①简单，易于理解，易于实现，无需参数估计，无需训练;②对异常值不敏感（个别噪音数据对结果的影响不是很大）;③适合对稀有事件进行分类;④适合于多分类问题(multi-modal,对象具有多个类别标签)，KNN要比SVM表现要好;
缺点
①对测试样本分类时的计算量大，内存开销大，因为对每一个待分类的文本都要计算它到全体已知样本的距离，才能求得它的K个最近邻点。目前常用的解决方法是事先对已知样本点进行剪辑，事先去除对分类作用不大的样本;②可解释性差，无法告诉你哪个变量更重要，无法给出决策树那样的规则;③K值的选择：最大的缺点是当样本不平衡时，如一个类的样本容量很大，而其他类样本容量很小时，有可能导致当输入一个新样本时，该样本的K个邻居中大容量类的样本占多数。该算法只计算“最近的”邻居样本，某一类的样本数量很大，那么或者这类样本并不接近目标样本，或者这类样本很靠近目标样本。无论怎样，数量并不能影响运行结果。可以采用权值的方法（和该样本距离小的邻居权值大）来改进;④KNN是一种消极学习方法、懒惰算法。
算法步骤：1、计算已知类别数据集中的点与当前点之间的距离；2、按照距离递增次序排序；3、选取与当前点距离最小的k个点；4、确定k个点所在类别的出现频率；（K用于选择最近邻的数目，K的选择非常敏感。K值越
Chameleon变色龙聚类算法小结
原文链接：https://blog.csdn.net/qiu1440528444/article/details/80725142推荐代码（java代码，亲测能用）：https://github.com/kstanisz/chameleon-clustering
前言Chameleon，变色龙算法，属于层次聚类算法领域。一种层次聚类算法，它采用动态建模来确定一对簇之间的相似度。它可以自动地、适应地合并簇，对各种奇葩的形状也能应对自如。
1.Chameleon算法原理一张图大致了解整个算法的思想。 1)首先由数据集构造一个k-最近邻图Gk； 2)再通过一种图的划分算法，将Gk图划分成大量较小的子图，每个子图代表一个初始的子簇； 3)最后使用凝聚层次聚类算法，基于子簇的相似度反复合并子簇。
下面再看看定义的一些概念，为了引出变色龙算法的一些定义，这里先说一下以往的一些聚类算法的不足之处，如图。 1)如图4所示：忽略簇与簇之间的互连性。 如果只看最近邻的链接，即只看近似性，则算法会倾向于合并c和d而不是a和b，但实际上a、b的临接区域较大，距离也不远（相对于a、b内部），即互连性更好，所以应该属于同一个cluster簇。 2)如图5所示：忽略簇与簇之间的近似性。就是过分强调临接区域的大小，倾向于合并a、c，而不是a、b。
Chameleon算法正好弥补了这2点要求，兼具互连性和近似性。下面用公式来描述这2个概念。
2.概念：互连性和近似性簇的互连性，同时考虑两个簇之间的距离和簇内各元素之间的距离，用相对互联度（RI）来量化得衡量：RI(Ci,Cj)=∣EC(Ci,Cj)∣∣EC(Ci)∣+∣EC(Cj∣2RI(C_i,C_j)=frac{|EC(C_i,C_j)|}{frac{|EC(C_i)|+|EC(C_j|}{2}}RI(Ci,Cj)=2∣EC(Ci)∣+∣EC(Cj∣∣EC(Ci,Cj)∣
其中，EC(Ci,Cj)EC(C_i,C_j)EC(Ci,Cj)表示将簇CCC划分为两个子簇EC(Ci)EC(C_i)EC(Ci)和EC(Cj)EC(C_j)EC(Cj)割边的权重;EC(Ci)EC(C_i)EC(Ci)表示将CiC_iCi划分为大致相等的两部分的割边的权重
簇的近似性，考虑更多的是簇与簇之间的近似性，用相对近似度（RC）指标量化：RC(Ci,Cj)=Sˉ∣EC(Ci,Cj)∣∣Ci∣∣Ci∣+∣Cj∣SˉEC(Ci)∣+∣Cj∣∣Ci∣+∣Cj∣∣SˉEC(Cj∣RC(C_i,C_j)=frac{ar{S}|EC(C_i,C_j)|}{frac{|C_i|}{|C_i|+|C_j|}ar{S}EC(C_i)|+frac{|C_j|}{|C_i|+|C_j|}|ar{S}EC(C_j|}RC(Ci,Cj)=∣Ci∣+∣Cj∣∣Ci∣SˉEC(Ci)∣+∣Ci∣+∣Cj∣∣Cj∣∣SˉEC(Cj∣Sˉ∣EC(Ci,Cj)∣
其中，SˉEC(Ci,Cj)ar{S}EC(C_i,C_j)SˉEC(Ci,Cj)表示将簇CCC划分为两个子簇EC(Ci)EC(C_i)EC(Ci)和EC(Cj)EC(C_j)EC(Cj)割边的平均权重，SˉEC(Ci)ar{S}EC(C_i)SˉEC(Ci)表示将CiC_iCi划分为大致相等的两部分的割边的平均权重，
定义度量公式RI(Ci,Cj)∗RC(Ci,Cj)αRI(C_i,C_j)*RC(C_i,C_j)^alphaRI(Ci,Cj)∗RC(Ci,Cj)α
其中α为是用来调节两个参量的比重的参数，α>1,更重视相对近似性，α
k均值聚类算法的优缺点
k均值聚类算法的优点很明显，那就是原理简单、易于操作，并且执行效率非常高，因此该算法得到了广泛的应用。但它也有不足，大体上有以下四点。
1)k值需要事先给出通过对k均值聚类算法的流程分析，不难看出，在执行该算法之前需要给出聚类个数（簇个数）。然而，在实际工作场景中，对于给定的数据集要分多少个类，用户往往很难给出合适的答案。此时，人们不得不根据经验或其他算法的协助来给出簇个数。这样无疑会增加算法的负担。在一些场景下，获取k的值要比实施算法本身付出的代价还大。
《k均值聚类算法核心》一节中的公式所示的误差函数，有一个很大的陷阱：随着簇个数的增加，误差函数趋近于0，最极端的情况是每个样本各为一个单独的簇，此时样本的整体误差为0，但是这样的聚类结果显然不是我们想要的。通常，我们可以引入结构风险，对模型的复杂度进行惩罚。
2)聚类质量对初始簇中心的选取有很强的依赖性在k均值聚类算法运行的开始阶段，要从数据集中随机地选取出k个数据样本，作为初始簇中心，然后通过不断的迭代得出聚类结果，直到所有样本点的簇归属不再发生变化。k均值聚类算法的目标函数通常将各个点到簇中心之间的距离平方和最小化，目标函数是一个非凸函数，往往会导致聚类出现很多局部最小值，进而导致聚类陷入局部距离最小而非全局距离最小的局面。显然这样的聚类结果是难以令人满意的。
3)对噪音数据比较敏感，聚类结果容易受噪音数据的影响在k均值聚类算法中，需要通过对每个簇中的数据点求均值来获得簇中心。如果数据集中存在噪音数据，那么在计算均值点（簇中心）时，会导致均值点远离样本密集区域，甚至出现均值点向噪音数据靠近的现象。自然，这样的聚类效果是不甚理想的。
4)只能发现球形簇，对于其他任意形状的簇无能为力k均值聚类算法常采用欧式距离来度量不同点之间的距离，这样只能发现数据点分布较均匀的球形簇。在聚类过程中，将距离平方和作为目标，是为了令目标函数能够取到极小值，算法会趋向于将包含数据较多的类分解为包含数据较少的类。一种极端情况是，算法把一个数据点视为一个类，这时数据点就是簇中心，距离误差达到最小（为0），这种算法偏好也会导致聚类效果不甚理想。
k均值聚类算法常采用欧式距离来度量不同点之间的距离，这样只能发现数据点分布较均匀的球形簇。在聚类过程中，将距离平方和作为目标，是为了令目标函数能够取到极小值，算法会趋向于将包含数据较多的类分解为包含数据较少的类。一种极端情况是，算法把一个数据点视为一个类，这时数据点就是簇中心，距离误差达到最小（为0），这种算法偏好也会导致聚类效果不甚理想。
尽管k均值聚类算法有各种“不尽如人意”的小毛病，但算法简单，容易实现，瑕不掩瑜，它依然被广泛用在各种场景下。