数据挖掘工程师笔试、面试题
一、笔试
1、过拟合和欠拟合怎么判断，如何解决？
答：主要可以通过训练误差和测试误差入手判断是否过拟合或欠拟合。一般而言训练误差很低，但是测试误差较高，过拟合的概率较大，如果训练误差和测试误差都很高，一般是欠拟合。过拟合可以从增加样本量，减少特征数，降低模型复杂度等方面入手，实际的例子比如线性回归中，对于几十个样本的数据点就没必要用几十个变量去拟合。欠拟合则反之，需要考虑模型是否收敛，特征是否过少，模型是否过于简单入手。另外还有L1，L2正则化用于限制权重以及dropout用在神经网络中使得每次训练的网络结构多样。L1正则化其实就是讲权值的绝对值和加入损失函数，使得权值中0值比重增大，因此得到的权值较为稀疏。L2正则化则是将权重的平方和加入损失函数，使得权值分布更加平均，所以权值较为平滑。
2、特征如何构造？
答：其实特征主要针对业务来构造，业务则对应数据，举个例子，时间特征可能在交通预测方面有效，但是对于文本挖掘可能无效。因此可以考虑从数据统计分析入手，结合业务场景构造特征，后期可考虑细化特征或组合特征等。
3、逻辑回归的含义和推导？逻辑回归和线性回归的区别？
答：含义不多说，这个算法原理是最基本的。推导可以从损失函数最小化或最大似然方向入手。二者的区别曾经在面试阿里的时候被问到，当时脱口而出一个是分类一个是回归，但深层的含义或许是一个是迭代求解，一个是直接求解。望指教
4、模型怎么优化？怎么评估模型好坏？
答：模型优化主要从数据和模型两方面入手，根据具体问题来，比如过拟合且数据量太少的话可以考虑增加数据量。模型评估指标包括分类和回归，分类比如准确率，AUC值，或和业务相关的加权计算公式。这里强调下ROC曲线的AUC值是比较重要的内容，要能知道具体ROC曲线是怎么画出来的。回归的话比如MSE，RMSE或和业务相关的加权计算公式等。
5、数据如何清洗，怎么处理缺失值？
答：数据清洗主要还是通过分析数据的统计信息、分布情况、缺失情况等来定，在数据质量较好的前提下尽可能保留更多数据。缺失值的处理方法较多，也是根据具体特征和业务来定，可以随机填充、均值填充、或采用简单算法如KNN，聚类进行填充。当然，如果某些特征或某些样本的缺失率太大，可以考虑直接舍弃，是具体情况而定。
6、bagging，boosting的含义？
答：bagging主要和随机森林关联，采用有放回的抽样，所以某个样本可能出现在多棵树的训练集中也可能一次也没出现，可以并行。另外每棵树用的特征集也是从原始特征集中随机选择部分特征集作为分裂集合。boosting主要和adaboosting关联，每棵树都是根据前一棵树训练的残差作为输入的，所以一般是串行跑的，每棵树的训练集都是整个样本集，另外对特征也没做选择。
7. 欠拟合和过拟合的原因分别有哪些？如何避免？
过拟合：又叫高偏差，就是模型太过复杂，力求覆盖每个数据，对训练集预测效果非常好！但是，泛化能力不好，一旦用测试集测试，预测结果却并不好！！！线性回归和logistic回归都存在欠拟合和过拟合的问题。
原因：（1）变量多（2）数据少缺乏代表性样本（3）函数（模型）过于复杂
避免：（1）减少特征数量，人工选择特征或自动选择（2）正则化
欠拟合：又叫高方差，指不能很好地拟合数据
原因：（1）模型过于简单（2）特征较少（3）数据量不够
避免：（1）增加模型的复杂度（2）增加特征数量（3）增加样本数量
8. 决策树的父节点和子节点的熵的大小？请解释原因。
父节点的熵更大，因为熵是用来衡量事物的无序性和混乱状态的度量，熵越大表示事物越无序和混乱，而决策树的父节点的类别较子节点类别要多，因此父节点的熵值较大。
9. 衡量分类算法的准确率，召回率，F1值。
准确率：预测正类中的实际正类的比例
召回率：实际正类中的预测正类比例
F1=2*召回率*准确率/（准确率+召回率），原则上F1表示召回率和精度的调和平均值
10. 举例序列模式挖掘算法有哪些？以及他们的应用场景。
AprioriAll算法、GSP算法、FreeSpan算法、PrefixSpan算法
应用场景：Apriori类算法在稀疏数据集的应用中比较合适，不适合稠密数据集的应用。对于有约束条件（例如相邻事务的时间间隔约束）序列模式挖掘，GSP更适用。FreeSpan和PrefixSpan在两种数据集中都适用，而且在稠密数据集中它们的优势更加明显。两者相比，PrefixSpan的性能更好一些。在实际应用中，在挖掘过程的不同阶段，数据集的特点，数据规模等因素可能不同，如果根据各阶段的特点，选择与之相应的算法，则序列模式挖掘能达到更好的效果。
此外由于Apriori类算法使用较简单，FreeSpan和PrefixSpan虽然效率高，但实现起来难度大。所以，现在大多数应用都是采用Apriori类算法的改进算法，以克服Apriori类算法执行效率不高的缺点。
11.相似性与相异性度量（欧氏距离、曼哈顿距离、Jaccard相似系数、余弦相似度、皮尔森相关系数）的计算
（1）欧氏距离：
（2）曼哈顿距离：
（3）Jaccard相似系数：
（4）余弦相似度：
（5）皮尔森相关系数：
12.朴素贝叶斯分类、ID3算法、关联规则
机器学习面试
前言：
找工作时（IT行业），除了常见的软件开发以外，机器学习岗位也可以当作是一个选择，不少计算机方向的研究生都会接触这个，如果你的研究方向是机器学习/数据挖掘之类，且又对其非常感兴趣的话，可以考虑考虑该岗位，毕竟在机器智能没达到人类水平之前，机器学习可以作为一种重要手段，而随着科技的不断发展，相信这方面的人才需求也会越来越大。
纵观IT行业的招聘岗位，机器学习之类的岗位还是挺少的，国内大点的公司里百度，阿里，腾讯，网易，搜狐，华为（华为的岗位基本都是随机分配，机器学习等岗位基本面向的是博士）等会有相关职位，另外一些国内的中小型企业和外企也会招一小部分。当然了，其中大部分还是百度北京要人最多，上百人。阿里的算法岗位很大一部分也是搞机器学习相关的。另外本人有幸签约了网易杭州研究院的深度学习算法岗位，打算从事机器学习领域至少5年。非常感谢小易收留了我！
下面是本人在找机器学习岗位工作时，总结的常见机器学习算法（主要是一些常规分类器）大概流程和主要思想，希望对大家找机器学习岗位时有点帮助。实际上在面试过程中，懂这些算法的基本思想和大概流程是远远不够的，那些面试官往往问的都是一些公司内部业务中的课题，往往要求你不仅要懂得这些算法的理论过程，而且要非常熟悉怎样使用它，什么场合用它，算法的优缺点，以及调参经验等等。说白了，就是既要会点理论，也要会点应用，既要有点深度，也要有点广度，否则运气不好的话很容易就被刷掉，因为每个面试官爱好不同。
目录：
1、朴树贝叶斯
2、决策树
3、Logistic回归
4、线性回归
5、KNN算法
6、SVM
7、Boosting
8、聚类
9、推荐系统
10、pLSA
11、LDA
12、GBDT
13、Regularization
14、异常检测
15、EM算法
16、Apriori
17、FP Growth
1、朴素贝叶斯：
有以下几个地方需要注意：
1. 如果给出的特征向量长度可能不同，这是需要归一化为通长度的向量（这里以文本分类为例），比如说是句子单词的话，则长度为整个词汇量的长度，对应位置是该单词出现的次数。
2. 计算公式如下：
其中一项条件概率可以通过朴素贝叶斯条件独立展开。要注意一点就是 ，而由朴素贝叶斯的前提假设可知，
=
，因此一般有两种，一种是在类别为ci的那些样本集中，找到wj出现次数的总和，然后除以该样本的总和；第二种方法是类别为ci的那些样本集中，找到wj出现次数的总和，然后除以该样本中所有特征出现次数的总和。
3. 如果 中的某一项为0，则其联合概率的乘积也可能为0，即2中公式的分子为0，为了避免这种现象出现，一般情况下会将这一项初始化为1，当然为了保证概率相等，分母应对应初始化为2（这里因为是2类，所以加2，如果是k类就需要加k，术语上叫做laplace光滑, 分母加k的原因是使之满足全概率公式）。
朴素贝叶斯的优点：
对小规模的数据表现很好，适合多分类任务，适合增量式训练。
缺点：
对输入数据的表达形式很敏感。
2、决策树：
决策树中很重要的一点就是选择一个属性进行分枝，因此要注意一下信息增益的计算公式，并深入理解它。
信息熵H(X)
信息增益=H(D)-H(Y|X)
信息增益率=gain(x)/H(x)
Gini系数=1-sum（pk^2）
基尼系数就是熵在x=1的地方一阶泰勒展开得到f(x)=1-x
所以gini=sum[x(1-x)]=1-sum(x^2)
信息熵的计算公式如下:
其中的n代表有n个分类类别（比如假设是2类问题，那么n=2）。分别计算这2类样本在总样本中出现的概率p1和p2，这样就可以计算出未选中属性分枝前的信息熵。
现在选中一个属性xi用来进行分枝，此时分枝规则是：如果xi=vx的话，将样本分到树的一个分支；如果不相等则进入另一个分支。很显然，分支中的样本很有可能包括2个类别，分别计算这2个分支的熵H1和H2,计算出分枝后的总信息熵H’=p1*H1+p2*H2.，则此时的信息增益ΔH=H-H’。以信息增益为原则，把所有的属性都测试一边，选择一个使增益最大的属性作为本次分枝属性。
决策树的优点：
计算量简单，可解释性强，比较适合处理有缺失属性值的样本，能够处理不相关的特征；
缺点：
容易过拟合（后续出现了随机森林，减小了过拟合现象）；
3、Logistic回归：
Logistic是用来分类的，是一种线性分类器，需要注意的地方有：
1. logistic函数表达式为：
其导数形式为：
2. logsitc回归方法主要是用最大似然估计来学习的，所以单个样本的后验概率为：
到整个样本的后验概率：
其中：
通过对数进一步化简为：
3. 其实它的loss function为-l(θ)，因此我们需使loss function最小，可采用梯度下降法得到。梯度下降法公式为:
Logistic回归优点：
1、实现简单；
2、分类时计算量非常小，速度很快，存储资源低；
缺点：
1、容易欠拟合，一般准确度不太高
2、只能处理两分类问题（在此基础上衍生出来的softmax可以用于多分类），且必须线性可分；
4、线性回归：
线性回归才是真正用于回归的，而不像logistic回归是用于分类，其基本思想是用梯度下降法对最小二乘法形式的误差函数进行优化，当然也可以用normal equation直接求得参数的解，结果为：
而在LWLR（局部加权线性回归）中，参数的计算表达式为:
因为此时优化的是：
由此可见LWLR与LR不同，LWLR是一个非参数模型，因为每次进行回归计算都要遍历训练样本至少一次。
线性回归优点：
实现简单，计算简单；
缺点：
不能拟合非线性数据；
5、KNN算法：
KNN即最近邻算法，其主要过程为：
1. 计算训练样本和测试样本中每个样本点的距离（常见的距离度量有欧式距离，马氏距离等）；
2. 对上面所有的距离值进行排序；
3. 选前k个最小距离的样本；
4. 根据这k个样本的标签进行投票，得到最后的分类类别；
如何选择一个最佳的K值，这取决于数据。一般情况下，在分类时较大的K值能够减小噪声的影响。但会使类别之间的界限变得模糊。一个较好的K值可通过各种启发式技术来获取，比如，交叉验证。另外噪声和非相关性特征向量的存在会使K近邻算法的准确性减小。
近邻算法具有较强的一致性结果。随着数据趋于无限，算法保证错误率不会超过贝叶斯算法错误率的两倍。对于一些好的K值，K近邻保证错误率不会超过贝叶斯理论误差率。
注：马氏距离一定要先给出样本集的统计性质，比如均值向量，协方差矩阵等。关于马氏距离的介绍如下：
KNN算法的优点：
1. 思想简单，理论成熟，既可以用来做分类也可以用来做回归；
2. 可用于非线性分类；
3. 训练时间复杂度为O(n)；
4. 准确度高，对数据没有假设，对outlier不敏感；
缺点：
1. 计算量大；
2. 样本不平衡问题（即有些类别的样本数量很多，而其它样本的数量很少）；
3. 需要大量的内存；
6、SVM：
要学会如何使用libsvm以及一些参数的调节经验，另外需要理清楚svm算法的一些思路：
1. svm中的最优分类面是对所有样本的几何裕量最大（为什么要选择最大间隔分类器，请从数学角度上说明？网易深度学习岗位面试过程中有被问到。答案就是几何间隔与样本的误分次数间存在关系： ，其中的分母就是样本到分类间隔距离，分子中的R是所有样本中的最长向量值），即：
经过一系列推导可得为优化下面原始目标：
2. 下面来看看拉格朗日理论：
可以将1中的优化目标转换为拉格朗日的形式（通过各种对偶优化，KKD条件），最后目标函数为：
我们只需要最小化上述目标函数，其中的α为原始优化问题中的不等式约束拉格朗日系数。
3. 对2中最后的式子分别w和b求导可得：
由上面第1式子可以知道，如果我们优化出了α，则直接可以求出w了，即模型的参数搞定。而上面第2个式子可以作为后续优化的一个约束条件。
4. 对2中最后一个目标函数用对偶优化理论可以转换为优化下面的目标函数：
而这个函数可以用常用的优化方法求得α，进而求得w和b。
5. 按照道理，svm简单理论应该到此结束。不过还是要补充一点，即在预测时有：
那个尖括号我们可以用核函数代替，这也是svm经常和核函数扯在一起的原因。
6. 最后是关于松弛变量的引入，因此原始的目标优化公式为：
此时对应的对偶优化公式为：
与前面的相比只是α多了个上界。
SVM算法优点：
可用于线性/非线性分类，也可以用于回归；
低泛化误差；
容易解释；
计算复杂度较低；
缺点：
对参数和核函数的选择比较敏感；
原始的SVM只比较擅长处理二分类问题；
7、Boosting：
主要以Adaboost为例，首先来看看Adaboost的流程图，如下：
从图中可以看到，在训练过程中我们需要训练出多个弱分类器（图中为3个），每个弱分类器是由不同权重的样本（图中为5个训练样本）训练得到（其中第一个弱分类器对应输入样本的权值是一样的），而每个弱分类器对最终分类结果的作用也不同，是通过加权平均输出的，权值见上图中三角形里面的数值。那么这些弱分类器和其对应的权值是怎样训练出来的呢？
下面通过一个例子来简单说明。
书中（machine learning in action）假设的是5个训练样本，每个训练样本的维度为2，在训练第一个分类器时5个样本的权重各为0.2. 注意这里样本的权值和最终训练的弱分类器组对应的权值α是不同的，样本的权重只在训练过程中用到，而α在训练过程和测试过程都有用到。
现在假设弱分类器是带一个节点的简单决策树，该决策树会选择2个属性（假设只有2个属性）的一个，然后计算出这个属性中的最佳值用来分类。
Adaboost的简单版本训练过程如下：
1. 训练第一个分类器，样本的权值D为相同的均值。通过一个弱分类器，得到这5个样本（请对应书中的例子来看，依旧是machine learning in action）的分类预测标签。与给出的样本真实标签对比，就可能出现误差(即错误)。如果某个样本预测错误，则它对应的错误值为该样本的权重，如果分类正确，则错误值为0. 最后累加5个样本的错误率之和，记为ε。
2. 通过ε来计算该弱分类器的权重α，公式如下：
3. 通过α来计算训练下一个弱分类器样本的权重D，如果对应样本分类正确，则减小该样本的权重，公式为：
如果样本分类错误，则增加该样本的权重，公式为：
4. 循环步骤1,2,3来继续训练多个分类器，只是其D值不同而已。
测试过程如下：
输入一个样本到训练好的每个弱分类中，则每个弱分类都对应一个输出标签，然后该标签乘以对应的α，最后求和得到值的符号即为预测标签值。
Boosting算法的优点：
低泛化误差；
容易实现，分类准确率较高，没有太多参数可以调；
缺点：
对outlier比较敏感；
8、聚类：
根据聚类思想划分：
1. 基于划分的聚类:
K-means, k-medoids(每一个类别中找一个样本点来代表),CLARANS.
k-means是使下面的表达式值最小：
k-means算法的优点：
（1）k-means算法是解决聚类问题的一种经典算法，算法简单、快速。
（2）对处理大数据集，该算法是相对可伸缩的和高效率的，因为它的复杂度大约是O(nkt)，其中n是所有对象的数目，k是簇的数目,t是迭代的次数。通常k<<n。这个算法通常局部收敛。
（3）算法尝试找出使平方误差函数值最小的k个划分。当簇是密集的、球状或团状的，且簇与簇之间区别明显时，聚类效果较好。
缺点：
（1）k-平均方法只有在簇的平均值被定义的情况下才能使用，且对有些分类属性的数据不适合。
（2）要求用户必须事先给出要生成的簇的数目k。
（3）对初值敏感，对于不同的初始值，可能会导致不同的聚类结果。
（4）不适合于发现非凸面形状的簇，或者大小差别很大的簇。
（5）对于”噪声”和孤立点数据敏感，少量的该类数据能够对平均值产生极大影响。
2. 基于层次的聚类：
自底向上的凝聚方法，比如AGNES。
自上向下的分裂方法，比如DIANA。
3. 基于密度的聚类：
DBSACN,OPTICS,BIRCH(CF-Tree),CURE.
4. 基于网格的方法：
STING, WaveCluster.
5. 基于模型的聚类：
EM,SOM,COBWEB.
以上这些算法的简介可参考聚类（百度百科）。
9、推荐系统：
推荐系统的实现主要分为两个方面：基于内容的实现和协同滤波的实现。
基于内容的实现：
不同人对不同电影的评分这个例子，可以看做是一个普通的回归问题，因此每部电影都需要提前提取出一个特征向量(即x值)，然后针对每个用户建模，即每个用户打的分值作为y值，利用这些已有的分值y和电影特征值x就可以训练回归模型了(最常见的就是线性回归)。这样就可以预测那些用户没有评分的电影的分数。（值得注意的是需对每个用户都建立他自己的回归模型）
从另一个角度来看，也可以是先给定每个用户对某种电影的喜好程度（即权值），然后学出每部电影的特征，最后采用回归来预测那些没有被评分的电影。
当然还可以是同时优化得到每个用户对不同类型电影的热爱程度以及每部电影的特征。具体可以参考Ng在coursera上的ml教程：https://www.coursera.org/course/ml
基于协同滤波的实现：
协同滤波（CF）可以看做是一个分类问题，也可以看做是矩阵分解问题。协同滤波主要是基于每个人自己的喜好都类似这一特征，它不依赖于个人的基本信息。比如刚刚那个电影评分的例子中，预测那些没有被评分的电影的分数只依赖于已经打分的那些分数，并不需要去学习那些电影的特征。
SVD将矩阵分解为三个矩阵的乘积，公式如下所示：
中间的矩阵sigma为对角矩阵，对角元素的值为Data矩阵的奇异值(注意奇异值和特征值是不同的)，且已经从大到小排列好了。即使去掉特征值小的那些特征，依然可以很好的重构出原始矩阵。如下图所示：
其中更深的颜色代表去掉小特征值重构时的三个矩阵。
果m代表商品的个数，n代表用户的个数，则U矩阵的每一行代表商品的属性，现在通过降维U矩阵（取深色部分）后，每一个商品的属性可以用更低的维度表示（假设为k维）。这样当新来一个用户的商品推荐向量X，则可以根据公式X\’*U1*inv(S1)得到一个k维的向量，然后在V’中寻找最相似的那一个用户（相似度测量可用余弦公式等），根据这个用户的评分来推荐（主要是推荐新用户未打分的那些商品）。具体例子可以参考网页：SVD在推荐系统中的应用。
另外关于SVD分解后每个矩阵的实际含义可以参考google吴军的《数学之美》一书（不过个人感觉吴军解释UV两个矩阵时好像弄反了，不知道大家怎样认为）。或者参考machine learning in action其中的svd章节。
10、pLSA:
pLSA由LSA发展过来，而早期LSA的实现主要是通过SVD分解。pLSA的模型图如下：
公式中的意义如下：
具体可以参考2010龙星计划：机器学习中对应的主题模型那一讲
11、LDA：
主题模型，概率图如下：
和pLSA不同的是LDA中假设了很多先验分布，且一般参数的先验分布都假设为Dirichlet分布，其原因是共轭分布时先验概率和后验概率的形式相同。
12、GDBT：
GBDT(Gradient Boosting Decision Tree) 又叫 MART（Multiple Additive Regression Tree)，好像在阿里内部用得比较多（所以阿里算法岗位面试时可能会问到），它是一种迭代的决策树算法，该算法由多棵决策树组成，所有树的输出结果累加起来就是最终答案。它在被提出之初就和SVM一起被认为是泛化能力（generalization)较强的算法。近些年更因为被用于搜索排序的机器学习模型而引起大家关注。
GBDT是回归树，不是分类树。其核心就在于，每一棵树是从之前所有树的残差中来学习的。为了防止过拟合，和Adaboosting一样，也加入了boosting这一项。
关于GDBT的介绍可以可以参考：GBDT（MART） 迭代决策树入门教程 | 简介。
13、Regularization:
作用是（网易电话面试时有问到）：
1. 数值上更容易求解；
2. 特征数目太大时更稳定；
3. 控制模型的复杂度，光滑性。复杂性越小且越光滑的目标函数泛化能力越强。而加入规则项能使目标函数复杂度减小，且更光滑。
4. 减小参数空间；参数空间越小，复杂度越低。
5. 系数越小，模型越简单，而模型越简单则泛化能力越强（Ng宏观上给出的解释）。
6. 可以看成是权值的高斯先验。
14、异常检测：
可以估计样本的密度函数，对于新样本直接计算其密度，如果密度值小于某一阈值，则表示该样本异常。而密度函数一般采用多维的高斯分布。如果样本有n维，则每一维的特征都可以看作是符合高斯分布的，即使这些特征可视化出来不太符合高斯分布，也可以对该特征进行数学转换让其看起来像高斯分布，比如说x=log(x+c), x=x^(1/c)等。异常检测的算法流程如下：
其中的ε也是通过交叉验证得到的，也就是说在进行异常检测时，前面的p(x)的学习是用的无监督，后面的参数ε学习是用的有监督。那么为什么不全部使用普通有监督的方法来学习呢（即把它看做是一个普通的二分类问题）？主要是因为在异常检测中，异常的样本数量非常少而正常样本数量非常多，因此不足以学习到好的异常行为模型的参数，因为后面新来的异常样本可能完全是与训练样本中的模式不同。
另外，上面是将特征的每一维看成是相互独立的高斯分布，其实这样的近似并不是最好的，但是它的计算量较小，因此也常被使用。更好的方法应该是将特征拟合成多维高斯分布，这时有特征之间的相关性，但随之计算量会变复杂，且样本的协方差矩阵还可能出现不可逆的情况（主要在样本数比特征数小，或者样本特征维数之间有线性关系时）。
上面的内容可以参考Ng的https://www.coursera.org/course/ml
15、EM算法：
有时候因为样本的产生和隐含变量有关（隐含变量是不能观察的），而求模型的参数时一般采用最大似然估计，由于含有了隐含变量，所以对似然函数参数求导是求不出来的，这时可以采用EM算法来求模型的参数的（对应模型参数个数可能有多个），EM算法一般分为2步：
E步：选取一组参数，求出在该参数下隐含变量的条件概率值；
M步：结合E步求出的隐含变量条件概率，求出似然函数下界函数（本质上是某个期望函数）的最大值。
重复上面2步直至收敛。
公式如下所示：
M步公式中下界函数的推导过程：
EM算法一个常见的例子就是GMM模型，每个样本都有可能由k个高斯产生，只不过由每个高斯产生的概率不同而已，因此每个样本都有对应的高斯分布（k个中的某一个），此时的隐含变量就是每个样本对应的某个高斯分布。
GMM的E步公式如下（计算每个样本对应每个高斯的概率）：
更具体的计算公式为：
M步公式如下（计算每个高斯的比重，均值，方差这3个参数）：
关于EM算法可以参考Ng的cs229课程资料 或者网易公开课：斯坦福大学公开课 ：机器学习课程。
16、Apriori:
Apriori是关联分析中比较早的一种方法，主要用来挖掘那些频繁项集合。其思想是：
1. 如果一个项目集合不是频繁集合，那么任何包含它的项目集合也一定不是频繁集合；
2. 如果一个项目集合是频繁集合，那么它的任何非空子集也是频繁集合；
Aprioir需要扫描项目表多遍，从一个项目开始扫描，舍去掉那些不是频繁的项目，得到的集合称为L，然后对L中的每个元素进行自组合，生成比上次扫描多一个项目的集合，该集合称为C，接着又扫描去掉那些非频繁的项目，重复…
看下面这个例子：
元素项目表格：
如果每个步骤不去掉非频繁项目集，则其扫描过程的树形结构如下：
在其中某个过程中，可能出现非频繁的项目集，将其去掉（用阴影表示）为：
上面的内容主要参考的是machine learning in action这本书。
17、FP Growth:
FP Growth是一种比Apriori更高效的频繁项挖掘方法，它只需要扫描项目表2次。其中第1次扫描获得当个项目的频率，去掉不符合支持度要求的项，并对剩下的项排序。第2遍扫描是建立一颗FP-Tree(frequent-patten tree)。
接下来的工作就是在FP-Tree上进行挖掘。
比如说有下表：
它所对应的FP_Tree如下：
然后从频率最小的单项P开始，找出P的条件模式基，用构造FP_Tree同样的方法来构造P的条件模式基的FP_Tree，在这棵树上找出包含P的频繁项集。
依次从m,b,a,c,f的条件模式基上挖掘频繁项集，有些项需要递归的去挖掘，比较麻烦，比如m节点，具体的过程可以参考博客：Frequent Pattern 挖掘之二(FP Growth算法)，里面讲得很详细。
另外说一些几个相关岗位侧重点：
1、算法工程师
这个岗位的工作内容根据不同公司而定，不过一般都离不开模型算法，但是这个算法可能是图像、语音、文本或者其他业务产品的建模。所以具体准备方向也看具体的岗位要求，以图像算法为例，如今深度学习的火热不用我说，所以基本的卷积神经网络算法，图像分类，图像检测等最近几年比较有名的paper都应该读一读。有条件的话像Caffe，TensorFlow框架都要用用。
2、机器学习工程师
这个岗位基本上是和算法差不多的，而且主要服务于公司内部的一些交易数据或流量数据的建模。所以基本的机器学习算法，优化方法等理论你要清楚，再搭配一些项目或比赛的实战经验就更好了。另外有Spark的使用经验会有加分。
3、大数据平台工程师
这个岗位侧重平台开发，比如你的公司要开发这样的一个平台，以后公司的机器学习工程师跑模型都在这个平台上跑，涉及分布式系统会更多一点，算法方面不多。
4、数据挖掘工程师
这个岗位主要还是看公司，有些公司里面可能做建模工作，有些公司做数据分析或者ETL工作，所以面试的时候一定要问清楚。
5、数据分析工程师
从title也看出来主要是做数据统计分析的一些工作，老实说建模前很重要的一个工作就是需要你对自己的数据有充分的理解，不过一般机器学习岗位可以做数据分析的工作，要不处理一个问题分太多步着实麻烦。准备的话可以从比如R语言还有一些数据分析统计和可视化角度入手。算法方面的东西应该涉及不多。
6、ETL工程师
这个岗位很多公司都需要，主要是做数据的前期处理，包括数据清洗，整理，校验等等，很繁琐，但是很重要。可以从SQL等语言入手。