机器学习大数据分析主流算法汇总
作者：探码科技， 原文链接： http://www.tanmer.com/blog/407
智能推荐系统算法
基于流行度的算法非常简单粗暴，类似于各大新闻、微博热榜等，根据PV、UV、日均PV或分享率等数据来按某种热度排序来推荐给用户。
这种算法的优点是简单，适用于刚注册的新用户。缺点也很明显，它无法针对用户提供个性化的推荐。基于这种算法也可做一些优化，比如加入用户分群的流行度排序，例如把热榜上的体育内容优先推荐给体育迷，把政要热文推给热爱谈论政治的用户。
协同过滤算法(Collaborative Filtering, CF)是很常用的一种算法，在很多电商网站上都有用到。CF算法包括基于用户的CF(User-based CF)和基于物品的CF(Item-based CF)。
基于用户的CF原理如下：
1）分析各个用户对item的评价（通过浏览记录、购买记录等）；
2）依据用户对item的评价计算得出所有用户之间的相似度；
3）选出与当前用户最相似的N个用户；
4）将这N个用户评价最高并且当前用户又没有浏览过的item推荐给当前用户。
基于物品的CF原理大同小异，只是主体在于物品：
1）分析各个用户对item的浏览记录。
2）依据浏览记录分析得出所有item之间的相似度；
3）对于当前用户评价高的item，找出与之相似度最高的N个item；
4）将这N个item推荐给用户。
利用word2vec一类工具，可以将文本的关键词聚类，然后根据topic将文本向量化。如可以将德甲、英超、西甲聚类到“足球”的topic下，将lv、Gucci聚类到“奢侈品”topic下，再根据topic为文本内容与用户作相似度计算。
综上，基于内容的推荐算法能够很好地解决冷启动问题，并且也不会囿于热度的限制，因为它是直接基于内容匹配的，而与浏览记录无关。然而它也会存在一些弊端，比如过度专业化(over-specialisation)的问题。这种方法会一直推荐给用户内容密切关联的item，而失去了推荐内容的多样性。
基于模型的方法有很多，用到的诸如机器学习的方法也可以很深，这里只简单介绍下比较简单的方法——Logistics回归预测。我们可以通过分析用户的行为与使用记录得到用户的记录表，从而得到用户属性与行为的非强关联关系，通过大量测试与经验，我们可以调整属性的组合，拟合出最准确的回归函数。
基于模型的算法由于快速、准确，适用于实时性比较高的业务如新闻、广告等，而若是需要这种算法达到更好的效果，则需要人工干预反复的进行属性的组合和筛选，也就是常说的Feature Engineering。而由于新闻的时效性，系统也需要反复更新线上的数学模型，以适应变化。
现实应用中，其实很少有直接用某种算法来做推荐的系统。在一些大的网站如Netflix，就是融合了数十种算法的推荐系统。我们可以通过给不同算法的结果加权重来综合结果，或者是在不同的计算环节中运用不同的算法来混合，达到更贴合自己业务的目的。
智能分类系统算法
朴素贝叶斯分类是基于贝叶斯定理与特征条件独立假设的分类方法，发源于古典数学理论，拥有稳定的数学基础和分类效率。它是一种十分简单的分类算法，当然简单并不一定不好用。通过对给出的待分类项求解各项类别的出现概率大小，来判断此待分类项属于哪个类别，而在没有多余条件的情况下，朴素贝叶斯分类会选择在已知条件下，概率最大的类别。
朴素贝叶斯算法在执行文本分类等工作是会有很好的效果，比如朴素贝叶斯算法常被使用于垃圾邮件的过滤分类中。
- SVM算法
支持向量机（Support Vector Machine，常简称为 SVM）是一种监督式学习的方法，可广泛地应用于统计分类以及回归分析。支持向量机属于一般化线性分类器，它能够同时最小化经验误差与最大化几何边缘区，因此支持向量机也被称为最大边缘区分类器。
同时支持向量机将向量映射到一个更高维的空间里，在这个空间里建立有一个最大间隔超平面。在分开数据的超平面的两边建有两个互相平行的超平面，分隔超平面使两个平行超平面的距离最大化。假定平行超平面间的距离或差距越大，分类器的总误差越小。
SVM 算法虽然存在难以训练和难以解释的问题，但是在非线性可分问题上的表现十分优秀，在非线性可分问题中常选择 SVM 算法。
- 基于KNN的算法
K - 近邻算法，简称 KNN（k-Nearest Neighbor），它同样是一个比较简单的分类、预测算法。对选取与待分类、待预测数据的最相似的 K 个训练数据，通过对这 K 个数据的结果或者分类标号取平均、取众数等方法得到待分类、待预测数据的结果或者分类标号。
KNN 算法相比其他算法也更加简单，并且易于理解、实现，无需估计参数与训练。适合对稀有事件进行分类和多分类方面的问题，在这类问题方面 KNN 算法的表现比 SVM 更好。
人工神经网络，简称神经网络或类神经网络，是一种模仿生物神经网络结构和功能的数学模型或计算模型，用于对函数进行估计或近似。神经网络由大量的人工神经元联结进行计算。大多数情况下人工神经网络能在外界信息的基础上改变内部结构，是一种自适应系统。
人工神经网络在语音、图片、视频、游戏等各类应用场景展现出了优异的性能，但是存在需要大量的数据进行训练来提高准确性的问题。
回归算法
它是广泛为人所知的模型技术之一。线性回归常被选用在线性预测模型中，在这个模型中，因变量是连续的，自变量可以是连续或离散的，回归线的性质是线性的。
线性回归使用最佳拟合直线建立因变量(Y)和一个或多个独立变量(X)之间的关系(也成为回归线)
它是被方程式：Y = a + b*X + e 所表示，这里 a 为截距，b 为斜率和 e 为误差项。这个方程式能基于给定的预测变量来预测目标变量的值。
逻辑回归用于发现事件的概率=成功和事件的事件=失败。当因变量是二进制（0/1，True / False，是/否）时，我们应该使用逻辑回归。这里，Y的值的范围从0到1，并且它可以由以下等式表示。
odds= p/(1-p) = probability of event occurrence / probability of not event occurrence
ln(odds) = ln(p/(1-p))
logit(p) = ln(p/(1-p)) = b0+b1X1+b2X2+b3X3….+bkXk
上面，p是有特征存在的概率。你应该问的是“为什么我们在方程中使用log？”。
因为我们这里用二项分布（因变量），我们需要选择最适合这种分布的链接函数。并且，它是logit函数。在上面的等式中，选择参数用来最大化这些观察样本的似然值，而不是最小化平方误差的和（类似于普通回归）。
如果自变量的幂大于1，则回归方程是多项式回归方程。
在这种回归技术中，最佳拟合线并不是直线。它是一条拟合数据点的曲线。
当我们处理多个自变量时常使用这种形式的回归。在这种技术中，独立变量的选择是借助于自动过程完成的，其不用涉及到人类干预。
它的专长是通过观察统计值，如R平方，t统计和AIC度量来辨别重要变量。逐步回归基本上适合回归模型，通过基于指定标准一次一个地添加/删除共变量。
该建模技术的目的是利用最小数量的预测变量来最大化预测能力。它是处理更高维度数据集的方法之一。
- Ridge回归
Ridge回归是当数据受多重共线性（自相关变量高度相关）时常使用的技术。在多重共线性中，即使最小二乘估计（OLS）是无偏的，它们的方差很大，这偏离了观察值远离真实值。通过对回归估计增加一定程度的偏差，Ridge回归减小了标准误差。
- Lasso回归
与Ridge回归类似，Lasso（最小绝对收缩和选择算子）也惩罚回归系数的绝对大小。此外，它能够减少变化性和提高线性回归模型的准确性。Lasso回归与Ridge回归的区别在于，它使用的是绝对值惩罚函数而不是平方惩罚函数。这使惩罚（或等价地约束估计的绝对值的和）值导致一些参数估计精确地为零。使用更大的惩罚会让估计进一步的收缩到绝对零。这导致在给定的n个变量中作变量选择。
ElasticNet是Lasso和Ridge回归技术的混合模型。它是用L1和L2作为正则化训练的。当有多个相关的特征时，Elastic-net是有用的，Lasso可能随机选择其中一个，Elastic-net很可能选择两个。
在Lasso和Ridge之间折衷的实际优点是它允许Elastic-Net继承一些Ridge的稳定性。
自然语言处理算法
隐马尔可夫模型原本是通信领域一个著名的模型。用于通信的编解码上。
我们发现，隐马尔可夫模型中，观察层只与对应的一个隐含层有关系，实际情况往往并非如此，比如词性标注，翻译，句法分析等，某一个观察层的状态往往与多个隐含层以及相邻观察层的状态有关。条件随机场便是能处理这种复杂seqToseq的模型。
每个隐马尔可夫模型都可以转化为条件随机场模型。隐马尔可夫模型主要用于语音识别等方面，其他方面用条件随机场效果较好。
聚类算法
- k-means聚类算法
算法步骤：
1）首先我们选择一些类/组，并随机初始化它们各自的中心点。中心点是与每个数据点向量长度相同的位置。这需要我们提前预知类的数量(即中心点的数量)。
2）计算每个数据点到中心点的距离，数据点距离哪个中心点最近就划分到哪一类中。
3）计算每一类中中心点作为新的中心点。
4）重复以上步骤，直到每一类中心在每次迭代后变化不大为止。也可以多次随机初始化中心点，然后选择运行结果最好的一个。
均值漂移聚类是基于滑动窗口的算法，来找到数据点的密集区域。这是一个基于质心的算法，通过将中心点的候选点更新为滑动窗口内点的均值来完成，来定位每个组/类的中心点。然后对这些候选窗口进行相似窗口进行去除，最终形成中心点集及相应的分组。
具体步骤：
1）确定滑动窗口半径r，以随机选取的中心点C半径为r的圆形滑动窗口开始滑动。均值漂移类似一种爬山算法，在每一次迭代中向密度更高的区域移动，直到收敛。
2）每一次滑动到新的区域，计算滑动窗口内的均值来作为中心点，滑动窗口内的点的数量为窗口内的密度。在每一次移动中，窗口会想密度更高的区域移动。
3）移动窗口，计算窗口内的中心点以及窗口内的密度，知道没有方向在窗口内可以容纳更多的点，即一直移动到圆内密度不再增加为止。
4）步骤一到三会产生很多个滑动窗口，当多个滑动窗口重叠时，保留包含最多点的窗口，然后根据数据点所在的滑动窗口进行聚类。
与均值漂移聚类类似，DBSCAN也是基于密度的聚类算法。
具体步骤：
1）首先确定半径r和minPoints. 从一个没有被访问过的任意数据点开始，以这个点为中心，r为半径的圆内包含的点的数量是否大于或等于minPoints，如果大于或等于minPoints则改点被标记为central point,反之则会被标记为noise point。
2）重复1的步骤，如果一个noise point存在于某个central point为半径的圆内，则这个点被标记为边缘点，反之仍为noise point。重复步骤1，知道所有的点都被访问过。
使用高斯混合模型（GMM）做聚类首先假设数据点是呈高斯分布的，相对应K-Means假设数据点是圆形的，高斯分布（椭圆形）给出了更多的可能性。我们有两个参数来描述簇的形状：均值和标准差。所以这些簇可以采取任何形状的椭圆形，因为在x，y方向上都有标准差。因此，每个高斯分布被分配给单个簇。
所以要做聚类首先应该找到数据集的均值和标准差，我们将采用一个叫做最大期望(EM)的优化算法。下图演示了使用GMMs进行最大期望的聚类过程。
具体步骤：
1）选择簇的数量（与K-Means类似）并随机初始化每个簇的高斯分布参数（均值和方差）。也可以先观察数据给出一个相对精确的均值和方差。
2）给定每个簇的高斯分布，计算每个数据点属于每个簇的概率。一个点越靠近高斯分布的中心就越可能属于该簇。
3）基于这些概率我们计算高斯分布参数使得数据点的概率最大化，可以使用数据点概率的加权来计算这些新的参数，权重就是数据点属于该簇的概率。
4）重复迭代2和3直到在迭代中的变化不大。
层次聚类算法分为两类：自上而下和自下而上。凝聚层级聚类(HAC)是自下而上的一种聚类算法。HAC首先将每个数据点视为一个单一的簇，然后计算所有簇之间的距离来合并簇，知道所有的簇聚合成为一个簇为止。
具体步骤：
1）首先我们将每个数据点视为一个单一的簇，然后选择一个测量两个簇之间距离的度量标准。例如我们使用average linkage作为标准，它将两个簇之间的距离定义为第一个簇中的数据点与第二个簇中的数据点之间的平均距离。
2）在每次迭代中，我们将两个具有最小average linkage的簇合并成为一个簇。
3）重复步骤2知道所有的数据点合并成一个簇，然后选择我们需要多少个簇。
当我们的数据可以被表示为网络或图是，可以使用图团体检测方法完成聚类。在这个算法中图团体（graph community）通常被定义为一种顶点(vertice)的子集，其中的顶点相对于网络的其他部分要连接的更加紧密。
具体步骤：
1）首先初始分配每个顶点到其自己的团体，然后计算整个网络的模块性 M。
2）第1步要求每个团体对（community pair）至少被一条单边链接，如果有两个团体融合到了一起，该算法就计算由此造成的模块性改变 ΔM。
3）第2步是取ΔM出现了最大增长的团体对，然后融合。然后为这个聚类计算新的模块性 M，并记录下来。
4）重复第1步和第2步——每一次都融合团体对，这样最后得到ΔM的最大增益，然后记录新的聚类模式及其相应的模块性分数 M。
5）重复第1步和第2步——每一次都融合团体对，这样最后得到 ΔM 的最大增益，然后记录新的聚类模式及其相应的模块性分数 M。
相识度度量算法
这个基本上是最常用的，最初用在计算文本相似度效果很好，一般像tf-idf一下然后计算，推荐中在协同过滤以及很多算法中都比其他相似度效果理想。
由于余弦相似度表示方向上的差异，对距离不敏感，所以有时候也关心距离上的差异会先对每个值都减去一个均值，这样称为调整余弦相似度
基本上就是两个点的空间距离，下面这个图就能很明显的说明他和余弦相似度区别，欧式距离更多考虑的是空间中两条直线的距离，而余弦相似度关心的是空间夹角。所以欧氏距离能够体现个体数值特征的绝对差异，所以更多的用于需要从维度的数值大小中体现差异的分析，如使用用户行为指标分析用户价值的相似度或差异。
余弦距离更多的是从方向上区分差异，而对绝对的数值不敏感，更多的用于使用用户对内容评分来区分兴趣的相似度和差异，同时修正了用户间可能存在的度量标准不统一的问题（因为余弦距离对绝对数值不敏感）。
其实这个就是前面讲的调整的余弦相似度，因为在推荐系统中均值分为用户的均值和物品的均值，这里相当于是物品的均值。这个也是比较常用的。
斯皮尔曼等级相关（Spearman’s correlation coefficient for ranked data）主要用于解决称名数据和顺序数据相关的问题。适用于两列变量，而且具有等级变量性质具有线性关系的资料。由英国心理学家、统计学家斯皮尔曼根据积差相关的概念推导而来，一些人把斯皮尔曼等级相关看做积差相关的特殊形式。
