算法介绍（Introduction）

C4.5

C4.5是机器学习中的一个分类决策树（Decision Tree）算法，它是决策树的一个核心，ID3的改进算法。因此想要构造C4.5的结构，只需要了解决策树的构造方法即可实现大半。而总的来说就是每次选择一个好的特征以及分裂点作为当前节点的判断条件（树的分岔路口）。

C4.5相比于ID3改进的方面包括：

  • 使用了信息增益率作为选择节点的标准。

    • 传统的ID3算法使用了信息增益(Information Gain)作为衡量节点优异度的标准，也就是熵值（Entropy）的变化程度，而这个情况往往会导致选择属性的时候偏向选择取值多的属性。例如同样是跑步，一个人的速度为5m/s，另一个人的速度为3m/s，之后两人分别加速到了10m/s和6m/s。如果利用信息增益来评估两人的速度变化，那么显然前者的信息增益更强（10-5 > 6-3）。然而如果使用信息增益率来说两人的加速度是一致的((10-5) / 5 = (6-3) / 3)。

  • 在构建决策树的过程中对分支进行了修剪。

    • 剪去那些只有几个节点的分支，因为选择方式少而单一，容易造成Overfitting。

  • 能够处理不完整的数据。

The K-means Algorithm(K-means)

K-means算法在机器学习中属于一个聚类算法，它是把n个对象根据他们的属性差异（Feature维度空间中的距离）来将彼此分成K群。它与处理混合正态分布的最大期望类似，因为都是试图找到数据中的聚类中心。
K-means计算假设对象属性来自于空间向量，并且目标是使各个群组内部的误差最小化。

Support Vector Machine（SVM）

支持向量机是一种监督式学习的方法，被广泛应用在分类和回归的分析中。它的原理是将空间中的向量映射到一个更高纬度的空间中，然后在空间中找到一个最大间隔超平面。通俗的来说就是在原有的维度空间中无法分割的情况下，我们先提高向量表示的维度空间，然后在高纬度空间中找到一个超平面，能够将不同类别的向量集合分割开来。我们在这个超平面两侧各取两个平行的超平面，然后最大化这两个平面的距离。

The Apriori algorithm

Apriori算法是一种最有影响力关联法则应用算法。其核心是结合了关联法则和递归的思想，我们会定义一个最小支持度（minimum support）来生成我们的频繁数据集。
首先从所有数据中计算出频繁项集L1，之后再利用L1生成L2项集，以此类推最后能够得到频繁k项集。每次检索需要扫描所有数据一次。

关联度分析的基本概念

  • 支持度

    • 关联规则 A->B 的支持度（Support）= P（AB），指的是A和B同时发生的概率

  • 置信度

    • A对B的置信度（confidence）= P（B | A）= P（AB）/ P（A），指的是A发生的情况下B发生的概率

最大期望（EM）算法

在统计计算中，最大期望算法是在概率模型中寻找最大似然估计或者最大后验估计的算法，其中概率模型依赖于无法观测的隐性变量（Latent Variable）。

举个例子就是：

  • 两个人分食物，我们没有必要利用十分精确的仪器来将食物分成完全相等的两份，而是先随便将食物分成两群，然后观察是否一样多，把比较多的那一份取出一部分到少的那一群。久而久之两群的差距就会越来越小最后收敛。

PageRank

PageRank，又称网页排名，是一种根据相互的超链接计算关联度的技术。它通过网页的外部链接和内部链接的数量和质量来衡量网站的价值。PageRank背后的机制是投票，也就是每一次访问网页的链接都是对该页面的一次投票，票数越多代表网站的权重越高。

假设有一个4个对象组成的小团体A，B，C，D。如果所有对象都提到A，那么A的PageRank值就是B，C，D三个PageRanks的总和。
即:

如果此时B有提到C，D也有提到A，B，C。由于一个页面不能出现两次，因此权重会被一个权重分配：

AdaBoost

AdaBoost是一种迭代的算法，其核心思想是针对同一个训练集训练不同的分类器，也叫作弱分类器。然后通过把这些弱分类器整合起来，构造出一个最终的强分类器。
AdaBoost算法本身是通过动态改变数据的分布情况来实现的，根据每次训练样本的正确与否，以及上次分类的准确率，来调整每个样本的权重比例。然后再将结果送给下一次分类器的迭代中进行训练，以此类推。

K-nearest neighbor classification(KNN)

KNN算法可以用于分类和回归问题，然而我们更常将其被用于解决分类问题上。KNN能够存储所有的案例，通过对比周围K个样本中的大概率情况，从而决定新的对象应该分配在哪一个类别。新的样本会被分配到它的K个最近最普遍的类别中去，因此KNN算法也是一个基于距离函数的算法。

Naive Bayes

在所有的分类模型中，应用最为广泛的无非是两种分类模型了，它们分别是决策树模型和朴素贝叶斯（Naive Bayes）模型。在结构上，Naive Bayes所需估计的参数较少，对缺失数据不太敏感，算法也比较简单。
Naive Bayes模型假设属性之间相互独立。通俗来说，一个朴素贝叶斯分类器假设分类的特性和其他特性不相关。朴素贝叶斯模型容易创建，而且在非监督式学习的大型数据样本集中非常有用，虽然简单，却能超越复杂的分类方法。其基本思想就是：对于给出的待分类项，求解在此项出现的条件下各个目标类别出现的概率，哪个最大，就认为此待分类项属于哪个类别。

CART（分类与回归树）

Classification and Regression Trees是在分类树下面总结两个关键的思想。一个是关于递归的划分自变量空间，第二个是用验证数据对树结构进行剪枝。
我们知道分类树的输出是样本的类别标签。回归树的输出则是一个固定的数值。而CART包含了上述的两种决策树。它的结构是一棵二叉树，且每个非叶子节点都有两个Child，所以叶子节点数总是比非叶子节点数多1。
CART中用于选择变量的不纯性度量标准是用Gini指数来处理的，也就是说树内部的属性越杂乱，Gini指数就越大。如果目标变量是离散的，并且具有两个以上的类别，则CART可能考虑将这些目标类别进行合并，最终合并成两个超类别（这个过程叫做双化）。如果目标变量是连续的，则CART会找出一组基于树的回归方程来预测目标变量的结果。